프로세스 관리

프로세스의 개념 병행 프로세스 및 동기화 교착 상태 스케줄링

프로세스 정의 프로세스의 상태 프로세스(process:동적 개념) 실행 중인 프로그램(program:정적 개념) 정적인 프로그램에 자원(기억장치, CPU 등)을 할당 프로세스 관리를 위해 프로세스마다 PCB(Process Control Block)을 가짐 프로세스의 상태 프로세스 완료 Run dispatch IO, 기타 서비스 시간한도 경과 (interrupt) Ready Blocked IO 종료 프로세스

프로세스의 상태 프로세스 제어 블록(PCB) 실행 상태 준비 상태 대기 상태 프로세스가 현재 CPU를 차지하고 실행중인 상태 준비 상태 프로세스가 CPU에서 실행할 모든 준비가 되어 있는 상태 대기 상태 I/O, 기타 이벤트 처리를 위해 대기하는 상태 프로세스 제어 블록(PCB) 운영체제가 프로세스를 관리하기 위해 필요한 일체의 정보 수록

인터럽트와 문맥교환 인터럽트(interrupt) 문맥 교환(context switching) 컴퓨터 시스템에서 아무 때나 발생할 수 있는 사건을 신속히 처리해 주기 위한 기법 문맥 교환(context switching) CPU에서 실행되는 프로세스를 교체하는 작업

스레드(thread) 프로세스 스레드 : 경량 프로세스(lightweight process) 전체 시스템(CPU+모든 자원들) 이용의 주체 모든 자원에 대한 정보가 필요 스레드 : 경량 프로세스(lightweight process) CPU 이용의 주체(CPU에 대한 정보만 필요, 정보량이 훨씬 적음) 문맥교환 시 overhead가 훨씬 적다 한 개의 프로세스는 여러 개의 스레드를 가질 수 있다

스레드 특징 장점 한 프로세스에 속한 스레드들은 CPU를 제외한 프로세스의 자원들을 공동 소유 각 스레드는 한 프로세스에만 소속되며 프로세스를 떠나서는 스레드가 존재할 수 없다 각 스레드는 독립적인 CPU control로 구현(stack, program counter 등 독자 소유) 장점 스레드들은 자원을 공유하므로 스레드 간의 정보 교환, 문맥 교환은 빠르고 효율적이다

병행 프로세스(concurrent process)의 정의 독립적 병행 프로세스 상호간 제어를 사전에 약속하지 않고 병행 실행하는 프로세스들 예) mouse 인터럽트와 응용 프로그램 아무때나 서로 발생 협동적 병행 프로세스 상호간 제어를 사전에 정의해 놓고 병렬 실행하는 프로세스들 예) Web browser와 Web server program 정의된 방식으로만 협력

독립적 병행(asynchronous concurrent) 프로세스의 동기화 데이터의 무결성(integrity) 문제 여러 프로세스들이 병행적으로 실행하며 데이터를 동시에 접근 예) 두 프로세스의 독립 병행 수행 경쟁 상태 발생 - 연산 결과가 프로세스 시간에 따라 달라짐 예방책 – 동기화(synchronization) 프로세스들이 한번에 한 프로세스씩 순차적으로 액세스하도록 함 P1 P2 memory var X (P1) 공유 데이터 (P2) X=10 read R0, X read R1, X inc R0 inc R1 write R0, X X=11 write R1, X

독립적 병행(asynchronous concurrent) 프로세스의 동기화 상호 배제(mutual Exclusion) 공유 데이터를 update한다면 한 순간에 한 프로세스만 공유 데이터를 액세스하도록 허락하는 기법 한 프로세스가 공유 데이터를 변경하는 동안 다른 프로세스는 데이터 액세스를 위해 기다려야 함 상호 배제를 위한 기법 소프트웨어적인 해결 Dekker 알고리즘 Peterson 알고리즘 하드웨어적인 해결 인터럽트 enable/disable 방법 test_and_set 명령어

독립적 병행(asynchronous concurrent) 프로세스의 동기화 프로세스 동기화 세마포어(semaphore) Dijkstra 에 의해 고안된 프로세스 간의 상호 배제 및 동기화 문제 해결 도구 구현 방식 busy-wait - 세마포어 값을 계속 점검하여 기다림 - 기다리는 동안 CPU와 메모리 사이클을 계속 사용 - 기다리는 시간이 짧을 경우에 사용 block-&-wakeup - 세마포어 값을 기다려야 한다면 즉시 자신을 block 시키는 방식 - 나중에 세마포어 값을 바꾸는 다른 프로세스가 block 중인 프로세스를 wakeup

교착 상태의 개념 프로세스들이 서로 남의 프로세스가 자원 내어주기를 기다리면서 영원히 block되어 있는 상태 Process A와 Process B가 Resource 1과 Resource 2를 할당받기 위해 교착상태에 빠짐 R1 R2 P1 P2 Requested Allocated

교착 상태가 일어나기 위한 4가지 조건 상호배제(mutual exclusion) 점유 및 대기(hold & wait) 자원은 한 번에 한 프로세스만 사용 점유 및 대기(hold & wait) 각 프로세스가 이미 자원을 갖고 있으면서 다른 자원을 더 요구 비선점(non preemption) 프로세스에 할당된 자원은 스스로 반납하기 전에는 빼앗지 못함 환형대기(circular wait) 프로세스 간의 자원 요구 형태를 추적해보면 결국 자기 자신으로 되돌아옴

교착 상태 해결 방안 교착 상태 예방(prevention) 교착 상태 회피(avoidance) 4가지 필요조건 중 하나를 발생하지 않도록 해서 교착 상태를 예방 자원의 낭비가 심하지만 그럼에도 불구하고 교착 상태가 원천적으로 봉쇄되지 않으면 안되는 응용에 사용 교착 상태 회피(avoidance) 교착 상태의 발생 가능성을 원천 봉쇄하기 보다는 이를 적절히 회피 Dijkstra의 Banker’s algorithm 교착 상태 탐지(detection) 및 복구(recovery) 교착 상태를 허용하고 교착 상태가 발생되면 이를 탐지(자원 할당 그래프) 관련된 프로세스를 중단, 관련된 자원을 강제로 빼앗아 교착 상태 발생 이전의 상태로 복구(rollback)

다중 프로그래밍에서의 스케줄링 A, B 두 프로세스가 있을 때 각 작업을 1초 동안 실행하고 1초 동안 기다리는 것을 60회 반복할 때 이 시스템의 효율은?

일괄처리 시스템에서는? 프로세스 A를 모두 처리한 후 B를 처리하는 경우 : 전체 4분 소요 실제 계산시간 2분, 쉬는 시간 2분, 프로세서 이용률은 50%

다중 프로그래밍 경우 A를 실행하고 1초 후 A가 기다릴 때 B를 실행 두 프로세스에 대한 실행시간 : 2분, 프로세서는 쉬지 않게 됨(효율증가) 프로세서 사용률은 50%에서 100%로 향상 A는 시간상의 절약이 없지만 B는 처리시간이 반으로 줄어들게 됨 프로세스 A 유휴; 입력 시작 프로세스 B 종료

스케줄링(scheduling) 정의 스케줄링시 고려 사항 프로세스들의 자원 사용 순서를 결정 입출력 위주(I/O bounded) 또는 연산 위주(Processor bounded)의 프로세스 인가? 대화형 프로세스인가 일괄 처리형 프로세스 인가? deadline이 주어졌는가 주어지지지 않았는가? 프로세스의 우선 순위가 있는가? 자원을 선점할 수 있는가 없는가?

CPU 스케줄링과 Job 스케줄링 CPU 스케줄러 작업(job) 스케줄러 CPU를 할당할지를 결정 단기 스케줄러(short term scheduler) : 매우 빈번히 수행 작업(job) 스케줄러 프로세스에게 메모리 공간을 할당하는 순서를 정해주는 스케줄러 장기 스케줄러(long term scheduler) 메모리 공간 Job 스케줄러 PA CPU PB CPU 스케줄러 PX PC PY

스케줄링 기법 선점 스케줄링(Preemptive Scheduling) 하나의 프로세스가 자원을 점유하고 있을 때 다른 프로세스가 이 자원을 빼앗을 수 있는 방법 특징 우선 순위가 높은 프로세스가 먼저 급하게 수행되어야 할 때 유용 대화식 시분할 시스템이나 실시간 시스템에 유용 오버헤드 초래 종류 RR (Round Robin) SRT (Shortest Remaining Time) MFQ (Multilevel Feedback Queue)

스케줄링 기법 비선점 스케줄링(Non-Preemptive Scheduling) 이미 할당된 자원을 임의로 빼앗지 않고, 그 프로세스의 사용이 끝난 후에 회수하는 방법 특징 프로세스의 응답 시간 예측 용이 짧은 작업이 긴 작업 뒤에 서게 된 경우 매우 오래 기다리게 되는 단점 종류 FCFS(First Come First Served) SJF(Shortest Job First) HRN(Highest Response ratio Next) Deadline Scheduling

1. 선입 선처리(First-Come, First-Served) 스케줄링 들어온 순서대로 처리 가장 간단히 방식 non-preemptive임(time-sharing에서는 곤란) FIFO queue : First-in<- tail, First-out<- head 호위 효과(convoy effect) 큰 job하나가 끝나기를 모두 기다림 CPU bound process가 끝나기를 I/O bounded process들이 기다림 길고 중요하지 않은 작업이 급하고 중요한 작업을 오래 기다리게 함 대화식 시스템에 부적합 FIFO(First In First Out) 스케줄링 이라고도 함

First-Come, First-Served (FCFS) Scheduling

2. 최소 작업 우선(Shortest-Job-First) 스케줄링 Shortest Next CPU Burst Scheduling Non Preemptive 스케줄링 기법 다음 CPU burst 시간이 가장 짧은 프로세스에게 할당 최적(Optimal) 스케줄링 작업들의 평균 대기 시간이 최소 long-term scheduling에 좋음(프로세스 시간의 사용자 예측 치 이용) 단점 기아 상태(starvation) 발생 대화형 시스템에는 부적합 short-term scheduling 에는 나쁨(차기 CPU burst 시간 파악 어려움) 차기 CPU 버스트 시간 예측 모델

3. SRT(Shortest Remaining Time) 스케줄링 대기 중인 프로세스 중 남은 작업 시간이 가장 작은 프로세스에게 먼저 CPU 할당 특징 Preemptive 스케줄링 기법 SJF 스케줄링 기법보다 많은 오버헤드 발생

4. HRN(Highest Response ration Next) 스케줄링 Brinch Hansen이 SJF 기법의 길고 짧은 작업 간의 불평등을 보안한 기법 dynamic priority = (waiting time + service time) / (service time) 특징 Non-Preemptive 오래 기다린 프로세스는 waiting time이 증가하므로 priority 커지고 short process일수록 priority 커짐

Example of Non-Preemptive SJF

Example of Preemptive SRT

ready queue = priority queue equal-priority -> FCFS 로 해결 높은 우선 순위의 프로세스에게 할당 ready queue = priority queue equal-priority -> FCFS 로 해결 단순 우선 순위 알고리즘 : SJF(p =1/T (T = 차기 CPU 버스트 시간 예측 값)) priority요인 OS내부 시간 제한(time limits), 메모리 요구량, 오픈 화일 수, (average I/O burst)/(average CPU burst) 비율 등 OS외부 프로세스 중요도, 컴퓨터 사용료 형태와 금액, 작업 부서, 정치적 요인 등 preemptive or non-preemptive 문제점 = 무한 정지(indefinite blocking) 또는 기아 상태(starvation) CPU를 영원히 기다림 : 결국 실행되거나 system crash 때 사라짐 (예) IBM 7094 at MIT 1973, 1967 job 해결 -> aging : wait 시간 길어지면 priority 높여 줌

우선 순위 스케줄링 예 3 1 4 5 2 10 2 1 5 평균 대기시간 : 8.2 P1 p2 p3 p4 p5 프로세스 우선순위 버스트시간 3 1 4 5 2 10 2 1 5 평균 대기시간 : 8.2

6. 순환 할당(Round-Robin) 스케줄링 시분할 시스템을 위해 설계 FCFS + preemption time slice 마다 timer 인터럽트 ready queue = circular FIFO queue preemptive time sharing에서time quantum의 크기가 중요 1 time quantum > context switching time 80% CPU burst < 1 time quantum 대화식 시분할 시스템에 적합

Example: RR with Time Quantum = 20

작은 시간 할당량이 문맥 교환을 증가시킴

7. 다단계 큐(Multilevel Queue) 스케줄링 각 프로세스는 우선 순위가 다른 여러 개의 큐 중 하나에 영원히 할당 각 queue는 자신의 고유한 scheduling algorithm 가짐 foreground (interactive) queue : RR알고리즘 background (batch) queue : FCFS알고리즘 queue들 사이의 scheduling 고정 우선 순위 선점 스케줄링(fixed priority preemptive scheduling) 큐 사이의 CPU time slice 할당 예 80% for RR 20% for FCFS 스케줄링 부담 적으나 융통성이 적음

Multilevel Queue Scheduling

8. 다단계 피드백 큐(Multilevel Feedback Queue) 스케줄링 프로세스가 여러 큐 사이를 이동 짧은 프로세스(I/O bound, interactive processes)가 우선 긴 프로세스는 자꾸 낮은 큐로 이동 aging : 오래 기다리면 우선순위 높여 기아 상태 예방 preemptive (큐 사이) the most sophisticated, the most complex 가장 일반적 -> 해당 시스템에 맞게 설정해야(configure) 큐의 개수 각 큐의 스케줄링 알고리즘 높은 우선 순위로 올려 주는 시기 낮은 우선 순위로 내려 주는 시기 어느 큐에 들어갈 것인가

Multilevel Feedback Queues

9. 기한부(Deadline) 스케줄링 작업이 주어진 만료 시간(deadline) 안에 완료되도록 보장하는 기법 특징 스케줄링에 많은 오버헤드 주로 실시간 시스템에서 활용