정보통신실습 및 특강(5) 2009.05 passwd74@cherub.sungkyul.edu http://cherub.sungkyul.edu/~web 2009.05

목차 프로세스(Process)의 개념 프로세스 상태 프로세스 제어 블록(PCB : Process Control Block) 문맥교환(Context Switch) CPU스케줄링 및 알고리즘

프로세스(Process) 개념 프로세스(Process)란? 실행중인 상태의 프로그램(=Task) 능동적인 실체 비동기적 행위 다음에 실행할 명령어를 지정하는 프로그램카운터 갖는다 비동기적 행위 프로세서가 할당되는 개체

프로세스(Process) 상태 프로세스(Process)상태 생성(new) : 프로세스 생성 실행(running) : process가 CPU를 차지하고 있는 상태 준비상태(ready) : process가 CPU에게 할당되기를 기다리는 상태(CPU를 할당 받을 수 있는 상태) 대기상태(waiting) : process가 I/O가 완료되기를 기다리는 상태 종료상태(terminated) : 프로세스의 실행 종료 준비상태 (ready) 대기상태 (waiting) 실행상태 (running) 종료 (terminated) 생성 (new) dispatch timer run out wake-up block

프로세스(Process) 상태 프로세스 상태전이(state transition) 준비상태 (ready) 대기상태 실행상태 (waiting) 실행상태 (running) 종료 (terminated) 생성 (new) dispatch timer run out wake-up block dispatch (ready running) : ready상태의 여러 프로세스들 중 스케줄러에 의해 CPU를 할당 받아 실행상태로 되는 것. timer run out (running ready) : process가 CPU내에서 일정시간 빠져 나가지 못할 경우, 인터럽트를 통해 제어를 OS에게 넘겨줌 block (running waiting) : 시간 할당량(time quantum) 이전에 I/O장치에 요청을 보내고, 그 요청이 완료될 때까지 기다리는 것. wake-up(waiting ready) : 기다리고 있던 사건이 완료되면(ex- I/O완료) waiting상태에서 다시 CPU를 할당 받기 위해 ready상태로 되는 것.

프로세스 제어 블럭(PCB) 프로세스 제어 블록(PCB : Process Control Block) 프로세스에 대한 중대한 여러 가지 정보를 저장하는 기억장소 프로세스 생성시 만들어 짐 모든 프로세스는 각기 고유의 PCB를 갖는다. 포인터 프로세스 상태 프로세스 번호 프로그램 카운터(PC) 레지스터 메모리 한계 개방 파일들의 리스트 ▪ [프로세스 제어 블록] 프로세스의 현재상태(Process state) - 생성(new), 준비(ready), 실행(running), 대기(waiting), 종료(terminated) 프로그램 카운터(program counter) - 프로세스가 실행할 다음 명령어의 주소를 가리킴 중앙처리장치 레지스터들(CPU registers) 중앙처리장치 스케줄링 정보(CPU scheduling information) 메모리 관리 정보(Memory-management information) 계정정보(accounting information) - CPU가 사용된 시간의 양, 계정번호, 작업 또는 프로세스 번호 등 입출력 상태 정보(I/O status information) - 입출력 요구들, 입출력 장치들, 개방된 파일의 목록 등

문맥 교환(Context Switch) 문맥교환(Context Switch) 이전의 프로세스의 상태를 저장하고 새로운 프로세스의 저장된 상태를 적재(load)하는 작업 CPU가 새로운 프로세스로 전환할때, Kernel은 이전 process의 상태를 저장하고, 저정된 새로운 process의 상태를 load 문맥교환의 시간 : overhead (H/W지원에 따라 크게 좌우됨)

중앙처리장치 스케줄링 중앙처리장치 스케줄링(CPU Scheduling) 스케줄링의 목적 공정한 스케줄링 응답 시간 최소화 작업 반환 시간 예측 가능 균형 있는 자원 사용 우선 순위가 높은 프로세스가 먼저 실시

중앙처리장치 스케줄링 중앙처리장치 입출력 버스트 주기(Burst cycle) 프로세스 실행 짧은 CPU burst가 많다(약 2ms간격) 긴 CPU burst는 적다 짧은 CPU burst : I/O작업을 중심으로하는 프로그램 (예, 워드) 긴 CPU burst : CPU 중심의 프로그램 (예, for루프)

Scheduling Criteria 최대화 : CPU 이용률, 처리율 최대화 최소화 : 반환시간, 대기시간, 응답시간 스케줄링 평가 기준 중앙처리장치 이용률(CPU utilization) 가능한 CPU를 최대 이용 처리율(Throughput) 단위 시간 당 실행을 완료할 수 있는 프로세스의 개수 반환시간(Turnaround time) 어떤 특정 프로세스가 실행을 시작해서 끝날 때까지의 걸린 시간 메모리에 들어가는 시간 + ready 큐에서 대기하는 시간 + CPU에서 실행하는 시간 + I/O시간 대기시간(Waiting time) 어떤 프로세스가 lifetime 동안 ready queue에서 대기해야 하는 총 시간 보통 프로세스가 실행 or I/O를 실행하는 동안에는 실제 시간의 양에 영향을 미치지 못함 응답시간(Response time) 프로세스가 어떤 요청을 운영체제에게 한 후 그에 대한 첫 응답을 받을 때까지 걸린 시간. 그 요청에 대한 서비스가 완료될 때까지의 시간이 아님! 최대화 : CPU 이용률, 처리율 최대화 최소화 : 반환시간, 대기시간, 응답시간

스케줄링 스케줄링 1단계 스케줄링 2단계 스케줄링 3단계 스케줄링 작업(job) 스케줄링, 장기(long-term) 스케줄링 어느 작업을 선택해서 시스템의 자원을 이용할게 할 것인가를 결정 (즉, 어느 작업을 메모리로 불러들일 것인가?) 2단계 스케줄링 작업프로세스들 중에서 어느것을 활성화 시키고, 보류할 것인가를 결정 활성화된 프로세스 : 주기억장치 보류된 프로세스 : 디스크공간 3단계 스케줄링 CPU 스케줄링, 단기(short-term) 스케줄링 주기억장치 내의 프로세스들 중에서 어느 process에게 CPU를 할당할 것인가 결정 디스패처(Dispatcher)

CPU 스케줄러 CPU 스케줄러의 기본동작 메모리에 있는 ready 상태의 프로세스들 중 하나를 선택 프로세스 입장에서 CPU scheduling을 당하게 되는 시점 process가 실행상태에서 대기상태로 전환될 때 (예, 입출력 요청) – Non Preemptive(비선점) process가 실행상태에서 준비상태로 전환될 때 (예, 인터럽트 발생할 때) – Preemptive(선점) process가 대기상태에서 준비상태로 전환될 때 (예, 입출력이 종료될 때) - Preemptive(선점) process가 종료할 때 - Non Preemptive(비선점)

CPU스케줄링 선점(preemptive) 스케줄링 비선점(Non-Preemptive) 스케줄링 선점 : 한 프로세스가 CPU를 차지하고 있을 때, 다른 프로세스가 현재의 프로세스를 중지시키고, CPU를 차지할 수 있도록 하는 방법 긴급을 요하는 우선순위를 갖는 시분할 처리, 실시간 처리에 유용 비선점(Non-Preemptive) 스케줄링 비선점 : 일단 CPU가 한 process에 할당되면, process가 종료하던가, 또는 대기상태로 전환해 CPU를 해제할 때까지 CPU를 점유하는 방법 모든 process에 대해서 공정한 처리가 가능 긴급 응답을 요하는 작업에는 좋지 못함. 짧은 작업이 긴 작업이 끝날 때까지 기다림

CPU 스케줄링 알고리즘 문제점: Starvation 해결책: Aging 우선순위(Priority) Scheduling Algorithms 각 process에게 우선순위를 부여해서 가장 높은 우선 순위를 갖는 프로세스에게 CPU가 할당됨.(smallest integer  highest priority). Process가 ready큐에 도착 => 현재 실행중인 process와 우선순위 비교 선 점 우선순위 알고리즘 : 우선순위가 높은 process가 CPU점유 비선점 우선순위 알고리즘 : ready 큐의 head부분에 새로운 process를 넣는다. 문제점: Starvation 낮은 우선 순위의 프로세스가 계속 CPU를 할당 받지 못하는 현상. 해결책: Aging 메모리에 들어와 있는 시간이 길어질수록 우선 순위를 높여줌으로써 기아 상태를 방지.

CPU 스케줄링 알고리즘 P2 P3 P1 2ㅊ 7 17 평균대기시간 : (0+2+7)/3 =3 2ㅊ 7 17 평균대기시간 : (0+2+7)/3 =3 평균 반환시간(Turnaround time) : (2+7+17)/3 = 8.66

CPU 스케줄링 알고리즘 선입 선처리(FCFS : First-Come, First-served) 스케줄링 알고리즘 P1 P2 Ready큐에 들어온 순서대로 CPU를 할당 process Burst시간 P1 P2 P3 24 3 P1 P2 P3 24 27 30 Waiting time for P1 = 0; P2 = 24; P3 = 27 Average waiting time: (0 + 24 + 27)/3 = 17

CPU 스케줄링 알고리즘 The Gantt chart Waiting time for P1 = 6; P2 = 0; P3 = 3 process Burst시간 P2 P3 P1 3 24 The Gantt chart Waiting time for P1 = 6; P2 = 0; P3 = 3 Average waiting time: (6 + 0 + 3)/3 = 3 Much better than previous case. Convoy effect : 하나의 큰 process가 CPU를 양도하기 위해 모든 다른 process들이 기다리는 것 P1 P3 P2 6 3 30

CPU 스케줄링 알고리즘 최소 작업 우선(SJF : Shortest Job First)스케줄링 P1 P3 P2 3 16 24 각 process의 CPU burst 길이를 비교, 가장 작은 CPU burst를 가진 process에게 할당 동일 CPU burst 를 갖는 경우 : 선입선출 스케줄링 적용 대기시간 : p1 = 3, p2=16, p3=9, p4=0 평균대기시간 : 3 + 16 + 9 + 0 = 28 / 4 = 7 process Burst시간 P1 P2 P3 6 8 7 P4 3 ② ④ ③ ① P1 P3 P2 3 16 24 P4 9

CPU 스케줄링 알고리즘 선입선출 스케줄링을 적용한 경우 최소의 “평균대기시간”을 갖는다. (최적의 알고리즘으로 평가) 문제점 평균대기시간 : 0 + 6 + 14 + 21 / 4 = 10.25 최소의 “평균대기시간”을 갖는다. (최적의 알고리즘으로 평가) 문제점 실행해 보기전에 CPU Burst를 알기 어렵다 P1 P2 P3 P4 6 14 21 24

CPU 스케줄링 알고리즘 비선점 SJF알고리즘 선점 SJF알고리즘 (=최소잔여시간 알고리즘(Shortest Remaining Time First)) Process가 실행되는 동안 새로운 process가 ready큐에 들어왔을 때 새로운 process는 현재 실행되고 있는 process의 남은 시간보다 더 짧은 경우 (새로운 process의 CPU burst < 현재 process의 남은 CPU burst) 새로운 process가 현재 실행되고 있는 process를 선점

CPU 스케줄링 알고리즘 선점 JSF스케줄링 P2 P4 P1 10 17 5 P3 26 1 2 3 평균대기시간 : 9+0+15+2 / 4 = 6.5 process Burst시간 P1 P2 P3 8 4 9 P4 5 Ready큐에 도착시간 1 2 3 P2 P4 P1 10 17 5 P3 26 1 2 3

CPU 스케줄링 알고리즘 비선점 JSF스케줄링 P2 P4 12 17 P1 8 P3 26 1 2 3 평균대기시간 : 0+7+15+9/4=7.75 process Burst시간 P1 P2 P3 8 4 9 P4 5 Ready큐에 도착시간 1 2 3 P2 P4 12 17 P1 8 P3 26 1 2 3

CPU 스케줄링 알고리즘 라운드로빈(Round-Robin)스케줄링 대기시간 : P1=10-4 , P2=4, P3=7 준비큐에 대기한 프로세스가 순서대로 들어오는데, 일정한 시간(time slice)단위로 처리. 선입선출 스케줄링과 유사 Process들 간의 교환을 위해서 선점이 추가접수 대기시간 : P1=10-4 , P2=4, P3=7 평균대기시간 : 6+4+7 /3 = 5.66 process Burst시간 P1 P2 P3 24 3 Time quantum = 4로 가정 P1 P2 P3 P1 P1 P1 P1 P1 4 7 10 14 18 22 26 30

CPU 스케줄링 알고리즘 시간할당량(time slice)가 클때 시간할당량(time slice)가 작을 때 선입선출 방식과 동일 시간할당량(time slice)가 작을 때 문맥교환이 자주 발생하고, 응답 시간이 길며, 오버헤드도 커짐

CPU 스케줄링 알고리즘 다단계 큐(Multilevel Queue) Scheduling 하위(우선순위가 낮은것) queue가 에 있는 process는 수행되지 못함

CPU 스케줄링 알고리즘 다단계 피드백 큐(Multilevel feedback queue)스케줄링 I/O-bound job과 interactive job이 높은 우선순위 큐에 남는 경향이 생김. aging : time quantum안에 처리 못하는 경우 낮은 우선순위 queue로 이동시킴(starvation 해소 방안)