6. CPU 스케줄링

다중 프로그래밍의 목적은 항상 실행할 수 있는 프로세스가 있도록 하여 CPU 사용 효율을 극대화하는 데 있다. 

프로세스는 실행되는 동안 CPU 실행과 입출력 대기 두 주기를 반복한다. 

CPU-bound process : 적은 수의 매우 긴 CPU 버스트

I/O-bound process : 많은 수의 짧은 CPU 버스트

짧은 CPU 버스트의 빈도가 많고, 8ms 이상의 CPU 버스트는 거의 없다. 

CPU 성능이 발달할 수록 프로세스는 입출력 중심 프로세스가 되는 경향이 높아진다. 

CPU가 유휴상태가 되면 ready queue에 있는 프로세스를 하나 선택해서 실행한다. 이 선택은 CPU 스케줄러가 한다. 

CPU 스케줄링 결정의 4가지 상황

running -> waiting (입출력 요청)

running -> ready (인터럽트 발생)

waiting -> ready (입출력 완료)

terminated (프로세스 종료) 

비선점 스케줄링 방식 : 프로세스가 CPU에 할당되면, 그 프로세스가 종료되거나 대기중인 상태로 전환될 때 까지 CPU를 점유한다. 

(상황 1, 4에서만 스케줄링이 일어나면 비선점 방식)

선점 스케줄링 방식 : 어떤 조건이 만족되면 현재 실행중인 프로세스의 의사와 상관없이 그것의 실행을 중단하고 다른 프로세스를 CPU에 할당!

스케줄러가 선택한 프로세스를 CPU에 할당해주는 요소를 dispatcher라 한다. 

dispatcher는 문맥 전환(context switch)과 모드 전환의 임무를 갖는다. 

디스패처가 하나의 프로세스를 중단하고 다른 프로세스를 실행하기까지 소요되는 시간을 디스패치 지연이라 한다. 

CPU 스케줄링 알고리즘을 선택할 때 고려되는 기준

- CPU 사용 효율(CPU utillization) : 가능한 CPU가 계속 유용한 작업을 하도록 해야 한다.

- 처리율(throughput) : 시간당 완료되는 프로세스의 수

- 반환시간(turnaround time) : 하나의 프로세스가 제시된 시점에서 그 프로세스가 종료될 때까지 걸린 시간(종료 시간-도착 시간)

- 대기시간(waiting time) : 한 프로세스가 준비완료 큐에서 대기한 총 시간

- 응답시간(response time) : 서비스를 요청한 후에 그 서비스에 대한 첫 반응이 나오기까지 걸린 시간

사용자 관점 (반환시간, 응답시간 등) - 시스템 관점(CPU사용효율, 처리율) 

CPU 사용효율과 처리율은 최대화하고, 반환시간, 대기시간, 응답시간은 최소화하는 알고리즘이 가장 이상적이다.

스케줄링 알고리즘.. 퀴즈에 백퍼나올것같다. 

FCFS (First-Come First-Served) : 먼저 요청한 프로세스 순으로 스케줄링 (비선점) 

—> 단점으로 호위 효과(convoy effect-하나의 큰 프로세스가 CPU를 양보할 때 까지 다른 모든프로세스가 기다리는 현상)의 발생가능성 있음 

SJF (Shortest-Job-First) : CPU 버스트 시간이 가장 짧은 프로세스 순으로 스케줄링 

버스트 시간이 같으면 FCFS 정책을 따른다. 

—> 프로세스의 다음 CPU 버스트 시간을 예측하기 어렵다. 보통 다음 CPU 버스트 시간은 이전의 CPU 버스트들의 길이를 지수 평균(exponential average) 하여 구한다. 

선점 SJF 알고리즘은 다른 말로 SRTF(Shortest-Remaining-Time-First) 알고리즘이라고도 하는데, 새 프로세스가 레디큐에 도착하면 이 프로세스의 다음 버스트 시간과 현재 수행중인 프로세스의 남은 버스트 시간을 비교하여 소요 시간이 적은 프로세스를 우선 할당한다. 

우선순위 스케줄링은 우선순위가 높은 프로세스에게 먼저 CPU를 할당한다. 우선순위가 같다면 FCFS 정책으로 할당한다. 

선점 우선순위 방식에서는 SRTF 방식과 마찬가지로 도착한 프로세스가 현재 수행중인 프로세스보다 우선순위가 높으면 현재 프로세스는 중단되고 새 프로세스가 CPU에 할당되어 실행된다. 

—> 우선순위 알고리즘의 문제는 영구 대기(indefinite blocking) 또는 starvation 현상이 발생할 수 있다는 것이다. 우선순위가 낮은 프로세스는 평생 실행되지 않을 수 있다. 

—> 이것을 극복하기 위해 aging 기법(대기하는 프로세스의 우선순위를 점진적으로 증가시킴)을 사용한다. 

RR(Round-Robin) 스케줄링 알고리즘은 시분할 시스템에서 사용하는 알고리즘! 기본적으로 선점 방식이다

시간조각(time quantum)이라고 하는 작은 시간을 정의하여 이 시간이 경과될 때마다 현재 프로세스를 중단하고 다음 프로세스를 실행한다. 

RR문제점..  다중레벨 큐 스케줄링, 다중 프로세서 스케줄링, 실시간 스케줄링 알고리즘 평가, 프로세스 스케줄링 모델 추가학습..