process의 execution은 CPU execution과 I/O wait의 사이클로 이루어진다.
Process execution은 CPU burst로 시작하고, 그 이후에는 I/O burst, CPU burst, ...의 과정이 반복된다. 마지막으로 system이 execution terminate을 요청하면 final CPU burst가 끝난다.
CPU burst의 지속시간은 케바케이지만, frequency curve는 아래 그림을 따라가는 경향이 있다.
즉, 긴 CPU burst는 적고, 짧은 CPU burst는 많은 것을 알 수 있다.
예를 들어, I/O-bound program은 많은 short CPU burst를 가지고, CPU-bound program은 적은 long CPU burst를 가질 것이다.
CPU-scheduling function에 포함된 또 다른 요소로 dispatcher가 있다.
dispatcher : CPU scheduler로 인해 선택된 프로세스에 CPU의 core를 할당해 주는 module이다. 기능은 다음과 같다 :
dispatcher는 매 context switch마다 실행되므로 가능한 한 빨라야 한다. 한 process를 멈추고 다른 프로세스를 실행시키는 데 까지 걸리는 시간을 dispatch latency라고 부른다.
리눅스에서는 vmstat 명령어를 통해서 context switch의 수를 확인할 수 있다. cat /proc/{process_num}/status를 통해서도 알 수 있다.
shortest-job-first(SJF) scheduling algorithm : 각 프로세스의 다음 CPU burst와 associate한다.
CPU가 available할 때, next CPU burst가 가장 작은 프로세스에게 할당된다. 만약 next CPU burst가 동일하다면 FCFS를 이용하여 처리한다.
SJF 스케줄링의 예시
- Gantt chart는 다음과 같다.
- waiting time : -> 3ms, -> 16ms, -> 9ms, -> 0ms
- average waiting time : 7ms
- average waiting time by FCFS : 10.25ms
확실히 average waiting time을 minimize시킨다. 하지만 실제 CPU scheduling에서는 다음 CPU burst가 얼마나 길지 모르기 때문에 구현할 수 없다.
해결 방법? 시도?
approximate SJF scheduling : next CPU burst를 이전 CPU burst의 길이들을 이용해서 예측한다. -> 그것을 바탕으로 예측된 가장 적은 CPU burst를 가진 프로세스를 선택하면 된다.
예측하는 방법 : 이전 CPU bursts의 측정된 길이의 exponential average를 사용한다.
예측 공식
아래는 = 1/2, = 10인 경우이다.
모든 들을 전개해서 값을 구할 수 있다.
당연히 는 1보다 작고, 그러면 결국 (1 - )또한 1보다 작으므로 항이 이어질수록 계수는 점점 작아지게 된다.
SJF 알고리즘은 preemptive일 수도, nonpreemptive일 수도 있다.
이전 process가 실행되는 도중에 새로운 프로세스가 ready queue에 추가되었을 경우 둘 중에 어느방식으로 할 것인지 선택해야 한다.
새로 추가된 process의 next CPU burst값이 현재 실행중인 프로세스의 남은 시간보다 더 짧은 경우가 생긴다. 이 때, preemptive SJF algorithm은 preempt할것이고, nonpreemptive SJF algorithm은 현재 프로세스가 CPU burst가 끝나기까지 기다릴 것이다.
Preemptive SJF scheduling : shortest-remaining-time-first scheduling이라고도 불린다.
예시)
- Gantt chart는 다음과 같다 :
- 프로세스 별 waiting time : = 9ms, = 0ms, = 15ms, = 2ms
- 평균 waiting time : 6.5ms
- Nonpreemptive SJF scheduling : 7.75ms
나머지는 이어서....