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

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

1 정보통신실습 및 특강(5) 2009.05 passwd74@cherub.sungkyul.edu

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

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

4 프로세스(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

5 프로세스(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상태로 되는 것.

6 프로세스 제어 블럭(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) - 입출력 요구들, 입출력 장치들, 개방된 파일의 목록 등

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

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

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

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

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

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

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

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

15 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

16 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: ( )/3 = 17

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: ( )/3 = 3 Much better than previous case. Convoy effect : 하나의 큰 process가 CPU를 양도하기 위해 모든 다른 process들이 기다리는 것 P1 P3 P2 6 3 30

18 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 평균대기시간 : = 28 / 4 = 7 process Burst시간 P1 P2 P3 6 8 7 P4 3 ② ④ ③ ① P1 P3 P2 3 16 24 P4 9

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

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

21 CPU 스케줄링 알고리즘 선점 JSF스케줄링 P2 P4 P1 10 17 5 P3 26 1 2 3
평균대기시간 : / 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

22 CPU 스케줄링 알고리즘 비선점 JSF스케줄링 P2 P4 12 17 P1 8 P3 26 1 2 3
평균대기시간 : /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

23 CPU 스케줄링 알고리즘 라운드로빈(Round-Robin)스케줄링 대기시간 : P1=10-4 , P2=4, P3=7
준비큐에 대기한 프로세스가 순서대로 들어오는데, 일정한 시간(time slice)단위로 처리. 선입선출 스케줄링과 유사 Process들 간의 교환을 위해서 선점이 추가접수 대기시간 : P1=10-4 , P2=4, P3=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

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

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

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