Round - Robin Scheduling

round - robin scheduling은 프로세스 마다 time quantum을 둔다.

※Time Quantum = 프로세스마다 CPU를 점유할 수 있는 시간을 정해 두는 것.

실행중이던 프로세스가 타임퀀텀에 의해 종료되면 Ready Queue의 제일 뒤쪽으로 옮겨진다.

Time Quantum이 너무 클 경우에는 FCFS Scheduling과 같은 알고리즘이 되고, 반면에 Time Quantum이 너무 작을 때에는 너무 잦은 Context-switch가 일어나 오버헤드가 발생, Time Quantum이 Context-switch보다 작을 때는 프로세스환경을 셋팅하다가 타임퀀텀이 끝나버려서 정작 프로세스의 실행을 하지 못하고 다시 CPU를 반환해야 한다.

일반적으로 Time Quantum = CPU Burst time 의 80%를 기준으로 한다.

만약 Ready Queue에 N개의 프로세스가 있고 Time Quantum 을 p라 한다면, 프로세스가 CPU를 점유하기 위한 최대 시간은 (N-1)*q이다. 

Priority Scheduling

Priority Scheduling는 각각의 프로세스마다 우선순위를 부여한 후에 우선순위가 가장 높은 프로세스를 먼저 실행시키는 알고리즘이다.

Nonpreemptive / Preemptive 둘다 가능하다.

SJF (Shortest - Job - First)

SJF의 기본적인 알고리즘은 CPU burst time이 짧은 것부터 실행시키는 것이다.

SJF는 Preemptive / Nonpreemptive 둘다 가능하다.

Nonpreemptive SJF는 현재 시점에 대기중인 프로세스 중 CPU burst time이 가장 짧은 것을 실행시킨 후에, 프로세스가 종료되거나 wait상태가 되기 전까지 실행한 후에 다시 Ready Queue를 보고 가장 짧은 burst time을 가진 프로세스를 실행시키는 방법이다.

이와 같이 burst time이 가장짧은 P4 -> P1 -> P3 -> P2 순으로 실행시킨다.

이때의 평균 대기시간은 3 + 16 + 9 + 0 /4 = 7s 이다.

Preemptive SJF는 프로세스 실행중 남아있는 burst time보다 적은 burst time을 가진 프로세스가 들어오면, 현재 실행하고 있던 프로세스를 Ready Queue에 넣고 더적은 burst time을 가진 프로세스를 실행하는 것이다.

맨처음에 도착한 P1을 실행하던 도중 P2가 도착한다. 이때 P1의 Burst time = 7 , P2의 Burst time = 4이므로 CPU는 P2를 실행하게 된다. 그러던 도중 P3가 들어오지만 P2의 Burst time이 더 적으므로 계속 P2를 실행시킴. P2의 실행이 끝나고 난 뒤 각각의 프로세스의 Burst time을 보면,

P1 = 7 ,P2 = 0(종료) ,P3 = 9 ,P4 = 5 이므로 CPU는 P4를 실행하게 된다.

이때의 Trunaround time(대기시간 + 실행시간)

P1 = 9 + 8 = 17

P2 = 0 + 4 =4

P3 = 15 + 9 = 24

P4 = 2 + 5 = 7