[운영체제][프로세스관리] CPU Scheduling #2 스케줄링 알고리즘(Scheduling Algorithm), FCFS, SJF

학습목표
1. 선입 선처리 스케줄링에 대해서 학습
2. 최단 작업 우선 스케줄링에 대해서 학습

 

CPU 스케줄링은 준비 완료 큐에 있는 어느 프로세스에게 CPU를 할당할 것인지를 결정하는 문제를 다룹니다. 이때 어느 프로세스를 선택할 것인지는 CPU 스케줄링 알고리즘에 따라 다릅니다. CPU 스케줄링 알고리즘들은 다음과 같은 종류가 있습니다.

• 선입 선처리 스케줄링(First-Come, First-Served Scheduling)
• 최단 작업 우선 스케줄링(Shortest-Job-First Scheduling)
• 우선순위 스케줄링(Priority Scheduling)
• 라운드 로빈 스케줄링(Round-Robin Scheduling)
• 다단계 큐 스케줄링(Multilevel Queue Scheduling)
• 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)

 

1. 선입 선처리 스케줄링(First-Come, First-Served Scheduling)

선입 선처리 스케줄링 방법은 매우 간단합니다. 먼저 요청하는 프로세스가 CPU를 먼저 할당받습니다. 이러한 정책은 선입선출(FIFO) 큐 자료구조로 쉽게 관리할 수 있습니다. 즉, 선입 선처리 스케줄링은 선입선출 큐 자료구조에서 제일 앞에 있는 프로세스부터 처리하는 스케줄링 알고리즘입니다.

 

하지만 선입 선처리 스케줄링의 문제점은 평균 대기 시간이 매우 길수 있습니다. 다음 그림은 시간 0에 프로세스 3개가 도착하였고 버스트 시간에 따른 총 대기 시간과 평균 대기 시간을 나타낸 것입니다.

아래 그림은 만약 수행시간이 짧은 순서로 P2,P3,P1이 도착하였을때 대기시간을 계산한 그림입니다.

위 그림을 보시면 수행시간이 짧은 순서로 온 프로세스부터 먼저 처리하니 평균 대기시간이 짧아진것을 볼 수 있습니다.

 

아래의 그림은 이번에는 선입 선처리 스케줄링 정책에서 총 처리시간을 계산한 경우입니다.

위 그림을 보시면 수행시간이 긴 프로세스가 먼저 와버려서 수행시간이 짧은 프로세스들은 긴시간을 대기하여야 하고 총 처리 시간도 높은 것을 볼 수 있습니다.

 

이번에는 프로세스의 수행시간이 짧은 순서로 왔다고 가정하고 총처리 시간을 계산하였습니다.

수행시간이 짧은 것이 먼저 처리되었기 때문에 대기 시간이 줄어들어 총 처리 시간도 줄어든 것을 볼 수 있습니다.

 

위와 같은 결과를 보고 알 수 있는 사실은 선입 선처리 스케줄링 알고리즘에서 평균 대기시간에 영향을 미치는 요인은 프로세스가 도착한 순서라는 것을 알 수 있습니다. 만약 수행시간이 긴 프로세스가 먼저 도착한다면 뒤에 아무리 프로세스 수행시간이 짧은 프로세스가 오더라도 선입선처리 정책때문에 수행시간이 짧은 프로세스는 긴 프로세스가 끝날때까지 대기하여야 하는 것을 볼 수 있었습니다. 이와 같은 문제는 CPU의 효율화를 떨어뜨립니다. 이와 같은 현상을 호송 효과(Convoy Effect)라고 합니다.

 

선입 선처리 스케줄링 알고리즘은 비선점형(Non-Preemptive)입니다. 일단 CPU가 한 프로세스에게 할당되면 그 프로세스가 종료하든지 또는 입/출력 처리를 요구하든지 하여 CPU를 방출할때까지 CPU를 점유합니다.

 

2. 최단 작업 우선 스케줄링(Shortest-Job-First Scheduling)

최단 작업 우선 스케줄링 알고리즘은 선입 선처리 스케줄링 알고리즘의 문제점을 개선하기 위한 알고리즘입니다. 이 알고리즘은 각 프로세스에 CPU 버스트 길이를 연관시킵니다. CPU가 이용 가능해지면, 가장 작은 다음 CPU 버스트를 가진 프로세스에게 할당시킵니다. 만약 길이가 동일하다면 선입 선처리 스케줄링을 적용합니다.

 

위의 결과를 보면 Burst Time이 짧은 순서대로 처리했을때 평균 대기시간과 평균 총처리 시간이 낮게 나온 것을 볼 수 있습니다.

 

SJF 알고리즘의 어려움

SJF 알고리즘의 어려움은 다음 CPU 요청의 길이를 파악하는 것입니다. 일괄 처리 시스템에서 장기 스케줄링을 위해서는 사용자가 작업을 제출할 때 지정한 프로세스 시간 제한 길이를 이용할 수 있습니다. 그러므로 사용자들이 프로세스 시간 제한을 정확하게 예상하는 동기가 됩니다. 왜냐하면, 더 낮은 값은 신속한 응답을 의미하기 때문입니다. 따라서 SJF 스케줄링은 장기 스케줄링에서 자주 사용됩니다.

 

SJF 알고리즘이 최적이긴 하지만, 단기 CPU 스케줄링 수준에서는 구현할 수 없습니다. 왜냐하면 CPU 버스트의 길이를 알 수 있는 방법이 없기 때문입니다. 하지만 SJF 스케줄링의 근사치를 구하기 위하여 다음 CPU의 길이를 예측하는 것은 가능할 것입니다. 그리고 예측한 CPU 버스트를 가지는 프로세스를 선택하면 됩니다.

 

다음 CPU 버스트를 예측하기 위해서는 이전 CPU 버스트의 측정된 길이의 지수 평균(Exponential Average)을 사용합니다.

• T_n : n번째 CPU 버스트의 길이
• T_n+1 : 다음 CPU 버스트의 예측된 값
• 0<=a<=1
• a : 확률을 의미함

a=1/2일때 CPU 버스트와 예측값의 결과입니다.

위의 결과를 보면 완전히 동일하지는 않더라도 대략적으로 비슷한 모습을 볼 수 있습니다.

 

선점형 SJF 스케줄링과 비선점형 SJF 스케줄링

SJF 스케줄링은 선점형이거나 또는 비선점형일 수 있씁니다. 앞의 프로세스가 실행되는 동안 새로운 프로세스가 준비 완료 큐에 도착하면 선택이 발생합니다. 새로운 프로세스가 현재 실행 되고 있는 프로세스의 남은 시간보다도 더 짧은 CPU 버스트를 가질 수도 있습니다. 선점형 알고리즘은 현재 실행하는 프로세스를 선점할 것이고, 반면에 비서점형 SJF 스케줄링은 현재 실행하고 있는 프로세스가 자신의 CPU 버스트를 끝내도록 허용할 것입니다. 선점형 SJF 스케줄링은 때때로 최소 잔여 시간 우선(shortest remaining time first) 스케줄링이라고 불립니다.

 

다음 그림은 선점형 SJF 스케줄링 정책으로 4개의 프로세스가 다음과 같이 도착하였을때 평균 대기시간과 평균 총처리 시간을 계산한 결과입니다.

위 그림에서 주목할 점은 선점형이기 때문에 P1이 먼저 도착했음에도 P2가 버스트시간이 더 짧으므로 P2와 P4가 P1을 선점한 것을 볼 수 있습니다.

 

다음 그림은 이번에는 비선점형 SJF 스케줄링을 했을때의 결과입니다.

위의 결과를 통해서 선점형 스케줄링이 비선점형 스케줄링보다 조금더 빠른 것을 알 수 있었습니다. 하지만 위 프로세스와는 다르게 다른 케이스로 프로세스의 도착시간과 버스트시간에 따라 비선점형 스케줄링이 더 좋을 수 있습니다.

 

Operating System Concepts, 7th Ed. feat. by Silberschatz et al.
[인프런] 운영체제 공룡책 강의