18_스케줄링 알고리즘 -선입 선처리 스케줄링과 최단 작업 우선 스케줄링

18_스케줄링 알고리즘

• 선입 선처리 스케줄링과 최단 작업 우선 스케줄링

 

CPU 스케줄링은 준비 완료 큐에 있는 어느 프로세스에게 CPU를 할당할 것인지를 결정하는 문제를 다룬다.

 

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

선입 선처리(FCFS)스케줄링은 CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당 받는 방식으로 선입 선처리 정책의 구현은 선입선출(FIFO) 큐로 쉽게 관리 할 수 있다.

 

요청 및 처리 순서는 다음과 같다

1. 프로세스가 준비 완료 큐에 진입
2. 프로세스의 프로세스 제어블록(PCB)을 큐의 끝에 연결
3. CPU가 유휴 상태가 되면 준비 완료 큐의 앞 부분에 있는 프로세스에게 할당
4. 실행 상태의 프로세스는 준비 완료 큐에서 제거

 

선입 선처리 정책은 코드 작성이 쉽고 이해하기 쉬우나 선입 선처리 정책 때문에 평균 대기 시간이 길어 질 수가 있다.

다음의 예를 살펴 보자.

프로세스	버스트 시간
P1	24
P2	3
P3	3

 

위의 표와 같이 프로세스 실행 순서로 서비스를 받는 다면 다음과 같은 Gantt 차트를 확인 할 수 있다.

프로세스 P1의 대기 시간은 0이며 P2의 대기시간은 24, P3는 27이다. 이들의 평균 대기 시간은 (0 + 24 + 27) / 3 = 17 이다.

 

다음과 같이 P2, P3, P1이 서비스되면 어떨까?

프로세스 P2의 대기 시간은 0이며 P3의 대기시간은 3, P1의 대기시간은 6이다. 이들의 평균 대기 시간은 (0 + 3+ 6) / 3 = 3 이다. 이러한 감소는 상당히 큰 것이다.

 

위의 그림을 통해서 선입 선처리 정책의 평균 대기 시간은 최소 시간이 아니며 프로세스 CPU 버스트 시간이 크게 변할 경우 평균 대기 시간도 크게 변할 수 있다.

 

모든 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것을 호위 효과(convoy effect)라 한다. 이 효과는 짧은 프로세스들이 먼저 처리되도록 허용 될 때 보다 CPU와 장치 이용률이 저하되는 결과를 초래 한다.

 

선입 선처리 스케줄링 알고리즘은 비선점형이다. 일단 CPU가 한 프로세스에 할당되면 그 프로세스가 종료하든지 입/출력 처리를 요구하든지 하여 CPU를 방출할 때까지 CPU를 점유 한다. 선입 선처리 알고리즘은 특히 시분할 시스템에서 문제가 되는데 그 이유는 시분할 시스템에서는 각 사용자가 규칙적인 간격으로 CPU의 몫을 얻는 것이 매우 중요하기 때문이다. 한 프로세스가 지나치게 오랜 시간 동안 CPU를 점유하는 것은 매우 큰 손실 이다.

 

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

최단 작업 우선(SJF) 알고리즘은 각 프로세스에 다음 CPU 버스트의 길이를 연관 시킨다. CPU가 이용 가능해지면 가장 작은 다음 CPU 버스트를 가진 프로세스에게 할당 한다. CPU가 이용 가능해 지면 가장 작은 다음 CPU 버스트를 가진 프로세스에 할당 한다. 두 프로세스가 동일한 길이의 CPU 버스트를 가지면 선입 선처리 스케줄링 방식을 적용 한다.

 

프로세스	버스트 시간
P1	6
P2	8
P3	3
P4	7
P5	3

 

SJF 스케줄링을 적용한 간트 차트를 만들어 보자.

 

평균 대기 시간은 (0 + 3 + 6 + 12 + 19) / 5 = 8 이다. 최단 작업 우선 스케줄링은 프로세스의 전체 길이가 아니라 다음 CPU 버스트의 길이에 의해 스케줄이 되기 때문에 다음CPU 요청의 길이를 파악하는 것이 중요하다.

 

일괄 처리 시스템에서 장기 스케줄링을 위해서는 사용자가 작업을 제출 할 때 지정한 프로세스 시간 제한 길이를 이용 할 수 있다. 그러므로 사용자들이 프로세스 시간 제한을 정확하게 예상하도록 하는 동기가 된다. SJF 스케줄링은 장기 스케줄링에 자주 사용 된다.

 

SJF 알고리즘이 최적이긴 하지만 다음 CPU의 버스트 길이를 알 수 있는 방법이 없기 때문에 단기 CPU 스케줄링 수준에서는 구현 할 수 없다.

한 가지 접근 방식은 SJF 스케줄링과 비슷한 방법을 사용 하는 것으로 다음 CPU 버스트의 길이를 알 수는 없으나 다음의 버스트가 이전의 CPU 버스트와 길이가 비슷하다고 기대하여 예측 하는 것이다. 그러므로 다음 CPU 버스트 길이의 근사값을 계산해 가장 짧은 예상 CPU 버스트를 가진 프로세스를 선택 한다.

 

SJF는 선점형 또는 비선점형일 수 있다. 앞의 프로세스가 실행 되는 동안 새로운 프로세스가 준비 완료 큐에 도착하면 선택이 발생 한다. 새로은 프로세스가 현재 실행되고 잇는 프로세스의 남은 시간보다도 더 짧은 CPU 버스트를 가질 수도 있다. 선점형 SJF 알고리즘은 현재 실행하는 프로세스를 선점할 것이고 반면에 비선점형 SJF 알고리즘은 현재 실행하고 있는 프로세스가 자신의 CPU 버스트를 끝내도록 허용 한다.

 

선점형 SJF는 최소 잔여 시간 우선(shortest remaining time first) 스케줄링 이라고 불린다.

프로세스	도착시간	버스트 시간
P1	0	8
P2	1	4
P3	2	9
P4	3	5

 

선점형 SJF의 평균 대기 시간은 ((10-1) + (1-1) + (17-2) + (5-3)) / 4 = 6.5 이다.

비선점형 SJF 평균 대기 시간은 7.75 이다.