제 2 장 프로세스 관리 2.1 개요 프로세스 스케줄링은 준비완료(ready) 상태에 있는 프로세스들 중 어느 것을 중앙처리장치에 할당시킬 것인가를 결정 중앙처리장치 처리율(throughput)의 최대화와 반환 시간(turnaround time)의 최소화 2.2 프로세스 관리 프로세스 개념 실행(executing, running) 중인 프로그램 PCB(process control block)을 지닌 프로그램 프로그램 카운터(program counter)를 지닌 프로그램 능동적 개체(entity)로, 순차적으로 수행하는 프로그램 Slide 1 (of 22)
2.3 프로세스 구성 요소 운영체제의 프로세스 관리 관련 기능 사용자 프로세스와 시스템 프로세스의 생성과 삭제 프로세스의 일시 중지와 재 수행 프로세스 스케줄링 프로세스의 동기화 프로세스 간 통신 교착상태 처리 2.3 프로세스 구성 요소 프로세스는 코드(code) 영역, 데이터 영역, 스택 영역, 힙(heap)영역으로 구성 코드 영역: 프로그램의 코드 자체 데이터 영역: 프로그램의 전역 변수(global variable)나 정적 변수(static variable)의 할당을 위해 존재하는 공간 스택(stack) 영역: 지역 변수(local variable) 할당과 함수 호출 시 전달되는 인수(argument) 값 Slide 2 (of 22)
2.4 프로세스 상태 Slide 3 (of 22)
2.5 프로세스 제어 블럭 PCB의 구성 형태 프로세스의 현재 상태(실행, 준비완료, 대기 등) 프로세스의 고유 이름(identifier) 프로세스의 우선순위 프로세스가 적재된 기억장치의 주소를 가지는 포인터 할당된 자원(디바이스 등)을 가리키는 포인터 중앙처리장치의 각종 레지스터 상태를 저장하기 위한 공간 Slide 4 (of 22)
2.5 프로세스 생성 프로세스 생성 명령어 fork( ) Slide 5 (of 22)
fork() 명령어 프로그램 예 Slide 6 (of 22)
2.7 프로세스 스케줄링 2.7.1 스케줄링의 목적 및 기준 목적 공정성 처리 능력의 최대화 응답 시간의 최소화 예측 가능 오버헤드(overhead)의 최소화 자원 사용의 균형 응답과 이용간의 균형 유지 실행의 무한한 지연을 피할 것 우선순위제의 실시 주요 자원들을 차지하고 있는 프로세스에게 우선권을 주게 한다. 좀더 바람직한 동작을 보이는 프로세스에게 더 좋은 서비스를 제공한다. 과중한 부하를 완만히 줄인다. Slide 7 (of 22)
프로세스가 페이지 부재를 얼마나 자주 발생시키는가? 기준 입출력 위주의 프로세스인가? 연산 위주의 프로세스인가? 프로세스가 일괄 처리형인가 대화형인가? 긴급한 응답이 요구되는가? 프로세스의 우선순위 프로세스가 페이지 부재를 얼마나 자주 발생시키는가? 높은 우선순위를 지니는 프로세스에 의해서 얼마나 자주 프로세스가 선점(preempted) 되는가? 프로세스가 받은 실행 시간은 얼마나 되는가? 프로세스가 완전히 처리되는 데 필요한 시간은 얼마나 더 요구되는가? Slide 8 (of 22)
2.7.2 스케줄링 단계 2.7.3 방법 • 환경별 분류 선점/비선점(preemptive/nonpreemptive) 스케줄링 우선순위(priority) 스케줄링 마감시간(deadline) 스케줄링 다중 프로세서(Multiple Processor) 스케줄링 Slide 9 (of 22)
2.8 프로세스 스케줄링 알고리즘 2.8.1 FCFS(First-Come-First-Served) 스케줄링 프로세스들은 대기 큐에 도착한 순서에 따라 중앙처리장치를 할당받으며, 일단 프로세스가 중앙처리장치를 차지하면 완료될 때까지 CPU를 점유하며 수행된다. 예: 프로세스 버스트 시간(burst time) P1 P2 P3 21 3 6 P1 P2 P3 0 21 24 30 평균 반환 시간 = (21 + 24 + 30) / 3 = 25 평균 대기 시간 = (0 + 21 + 24) / 3 = 15 평균 반환 시간 = (24 + 3 + 30) / 3 = 19 평균 대기 시간 = (3 + 0 + 24) / 3 = 9 Slide 10 (of 22)
2.8.2 SJF(Shortest Job First) 스케줄링 기다리고 있는 프로세스 중에서 수행 시간이 가장 짧은 것을 먼저 수행하는 비선점 스케줄링 방식 예 프로세스 버스트 시간(burst time) P1 P2 P3 P4 7 8 3 6 P1 P3 P4 P2 0 3 9 16 24 FCFS 방식의 평균 반환 시간 : (7+15+18+24)/4=16 SJF 방식의 평균 반환 시간 : (3+9+16+24)/4=13 Slide 11 (of 22)
CPU 버스트 시간 예측 방법: 지수적 평균(exponential averaging) n+1=tn+(1-) n 여기서 0 1이다. Slide 12 (of 22)
2.8.3 우선순위(Priority) 스케줄링 우선순위가 각 프로세스에게 주어지며, 중앙처리장치는 가장 높은 우선순위를 가진 프로세스로 할당된다. 우선순위가 같은 프로세스들은 FCFS 순서로 스케줄 된다. 예 P1 8 2 P2 3 P3 1 P4 프로세스 버스트 시간 우선순위 P5 6 4 P3 P1 P2 P4 P5 0 1 9 11 13 19 평균 반환 시간 : (9+11+1+13+19)/5=10.6 평균 대기 시간 : (1+9+0+11+13)/5=6.8 Slide 13 (of 22)
2.8.4 라운드 로빈(RoundRobin) 스케줄링 FCFS + 선점(할당시간(time quantum) 마다) 예: time quantum=20 Slide 14 (of 22)
2.8.5 SRT(Shortest Remaining Time) 스케줄링 SRT(혹은 선점 SJF) 스케줄링 기법은 SJF 기법에 선점 방식을 도입한 변형된 방법으로서 시분할 시스템에서 유용하다. 예 P1 6 P2 4 1 P3 2 프로세스 버스트 시간 도착시간 P4 3 P1 P2 P3 P4 0 1 2 4 6 9 14 평균 반환 시간: P1=(14-0)=14, P2=(9-1)=8, P3=(4-2)=2, P4=(6-3)=3 이므로 (14+8+2+3)/4=6.75 평균 대기 시간: P1=0+(9-1)=8, P2=6-2=4, P3=0, P4=4-3=1 이므로 (8+4+0+1) /4=3.25 Slide 15 (of 22)
2.8.6 다단계 큐(Multilevel Queue) 스케줄링 다단계 큐 스케줄링 알고리즘은 준비 큐를 다수의 별개 큐로 나눈다. 기억장치의 요구량이나 프로세스의 우선순위 혹은 프로세스의 유형과 같은 프로세스의 특성에 근거해 프로세스들은 해당 큐에 할당된다. 각 큐는 자신의 스케줄링 알고리즘을 갖고 있다. 예 Slide 16 (of 22)
2.8.7 다단계 피드백 큐(Multilevel Feedback Queue) 스케줄링 새로운 프로세스는 큐잉 네트워크(queueing network)의 일단계 큐의 뒤쪽에 들어가며, 그 프로세스는 중앙처리장치를 차지할 때까지 큐를 통하여 FCFS에 의하여 이동된다. 만약 프로세스가 끝나기 전에 할당된 시간이 만료되었거나 입출력 혹은 어떤 돌발사건 등으로 인하여 중앙처리장치를 양도한다면 그 작업은 그 다음 하위 단계의 큐로 이동되어 재배치된다. 마지막 단계의 큐에서는 그 프로세스가 완료될 때까지 라운드 로빈으로 순환된다. Slide 17 (of 22)
2.8.8 HRN(High Response ratio Next) 스케줄링 우선순위 계산식은 다음과 같으며, 시스템 응답시간 값이 클수록 우선순위가 높아진다. 예 프로세스 대기 시간 버스트 시간 P1 P2 P3 P4 16 10 7 18 4 5 6 P1의 시스템 응답시간은 (16+4)/4 = 5가 되고, P2의 응답시간은 (10+5)/5 = 3이 되고, P3의 응답시간은 (7+7)/7 = 2가 되며, P4의 응답시간은 (18+6)/6 = 4가 된다. 우선순위는 P1이 가장 높으며, P4, P2, P3의 우선순위에 따라 CPU를 할당 받는다. Slide 18 (of 22)
2.8.9 마감시간 스케줄링 RM(Rate Monotonic) 알고리즘은 대표적인 정적 스케줄링 방식이며, 각 태스크 주기가 짧을수록 더 높은 우선순위를 부여한다. 즉 주기가 짧을수록 더 높은 우선순위를 부여한다. EDF(Earliest-Deadline First) 알고리즘은 대표적인 동적 스케줄링 방식이며, 임계 시간이 가장 근접한 태스크를 가장 먼저 수행하는 방식이다. RM의 예 Slide 19 (of 22)
EDF의 예 RM과 EDF의 비교 Slide 20 (of 22)
2.9 쓰레드(Thread) 쓰레드 특징 쓰레드와 프로세스 각 쓰레드는 서로 독립적이다 쓰레드의 실행/종료 순서는 예측할 수 없다. 쓰레드는 자신의 스택, 프로그램 카운터, 레지스터를 갖는다. 프로그램에 있는 쓰레드의 수는 다른 쓰레드에게 알려지지 않는다. 쓰레드는 프로그램의 외부에서는 보이지 않는다. 쓰레드는 서로 독립적이지만, 한 쓰레드가 취한 행동은 프로세스에 있는 다른 쓰레드에 영향을 미친다. 쓰레드는 프로세스의 일부분이기 때문에 데이터를 공유하기가 쉽다. 한 프로세스가 exit() 시스템 콜을 통해 종료한다면, 모든 쓰레드가 종료하게 된다. 쓰레드와 프로세스 Slide 21 (of 22)
쓰레드와 프로세스 포함정보 프로세스와 다중쓰레드 (a) 쓰레드당 항목 (b) 프로세스당 항목 쓰레드당 항목 프로세스당 항목 (a) 쓰레드당 항목 (b) 프로세스당 항목 쓰레드당 항목 프로세스당 항목 ․쓰레드 식별자 ․프로그램 카운터 ․스택 포인터 ․레지스터들 ․자식 쓰레드 ․쓰레드 상태 정보 ․주소공간 ․전역 변수 ․개방된 파일들 ․자식 프로세스 ․시그널 ․세마포어 ․계정 정보 프로세스와 다중쓰레드 Slide 22 (of 22)