[Chapter 5. CPU 스케줄링] 비선점 스케줄링 FCFS,SJF,우선순위

본 정리는 운영체제(Operating System: Concepts) 9th edition과 22학년도 1학기 건국대학교 운영체제 수업을 바탕으로 하고 있습니다.

 

비선점 스케줄링 (Non-preemptive Scheduling)

프로세스가 종료하거나 대기 상태로 전환해 CPU를 자진 반납할 때까지 CPU에 의한 실행을 보장해주는 스케줄링

작업 실행 시간 전체 또는 한 번의 CPU 배당에 대해 적용된다.

 

• 선입 선처리 스케줄링 (FCFS)
• 최단 작업 우선 스케줄링 (SJF) - 선점형으로도 가능
• 우선순위 스케줄링 - 선점형으로도 가능

 

FCFS (선입 선처리 스케줄링 First Come First Served ) 

프로세스 도착순으로 CPU에 배정하는 스케줄링 알고리즘

 

실행 중에 입출력을 요구하면 다시 다음 준비 큐에서 FCFS가 적용된다.

 

즉, 준비큐가 우리가 흔히 아는 FIFO 형태의 큐가 되는 것이다. FIFO 형태의 준비 큐 덕에 먼저 들어온 프로세스를 먼저 실행시키게 된다.

 

수행 중인 긴 작업을 여러 개의 짧은 작업이 기다리는 Convey effect(호위 효과)의 문제가 생길 수 있다.

 

---

작업 도착 순서	버스트타임
1	24
2	3
3	3

 

다음과 같이 작업이 도착한다고 할때, SJF의 간트차트로 프로세스 수행이 어떻게 진행되는지 알아보자.

 

* CPU 버스트 타임 : CPU를 할당 받아 I/O가 일 어나기 전까지 CPU를 사용하는 시간

* 간트차트 : 참여한 각 프로세스의 시작 시간과 종료 시간을 포함하여 특정 스케줄 기법을 도시하는 막대형 차트

 

다음과 같이 되고,

 

평균 반환 시간은 (24+27+30)/3 = 27

평균 대기 시간은 (0+24+27)/3 = 17 이 되어, 비교적 짧은 시간이 걸리는 작업인 2와 3이 긴시간이 걸리는 1을 오랫동안 기다리게 되어 효율적이지 못하다.

 

* 평균 반환 시간 : 프로세스가 생성되어 작업을 마치고 종료될 때까지 의 걸리는 시간의 평균

* 평균 대기 시간 : 프로세스가 생성되어 작업을 마치고 종료될 때까지 큐에서 기다리는 시간

 

 

 

최단 작업 우선 ( Shortest Job First )

대기하는 작업 중 CPU 버스트 타임이 가장 작은 작업에 CPU를 할당하는 기법.

 

평균 대기 시간에 있어서 가장 최적의 알고리즘이다.

 

---

다음의 예를 보자

 

작업 도착 순서	버스트타임
1	6
2	3
3	8
4	7

SJF는 가장 짧은 버스트 타임을 갖는 프로세스에 우선권을 주므로, 2 1 3 4의 순서로 실행되게 된다.

위와 같은 간트차트를 갖게 되고,

평균반환시간은 (3+9+16+24)/4 = 13

평균대기시간은 (3+0+16+9)/4 = 7이 된다.

 

 

---

위 예에서는 도착 시점이 모두 0으로 같은데,

실상은 새로운 프로세스가 생성되고, 또 대기 상태에 있는 프로세스가 들어오기도 하는 등 도착 시점이 다양하다.

 

 

도착시점을 고려하여 보자.

 

Process	Arrival Time	Burst Time
P1	0	7
P2	2	4
P3	4	1
P4	5	4

우선 준비 큐에 P1만 있으므로, P1이 먼저 실행되고 비선점 스케줄링이기 때문에 P1이 모두 실행된 후에야 다른 프로세스들이 실행될 수 있다.

7초 이후에는 모든 프로세스들이 준비 큐에 있으므로 버스트 타임이 짧은 순으로 P3 P2 P4가 실행된다.

 

평균대기시간은 (0 + 6 + 3 + 7)/4 = 4 (도착시점부터 실행될 때까지의 시간을 잰다. P1 P2 P3 P4 순)이고,

평균 반환 시간은 (7 + 10 + 4 + 11)/4 = 8 (도착 시점부터 끝날 때까지의 시간을 잰다.P1 P2 P3 P4 순)이 된다.

 

 

 

 

---

SJF 알고리즘은 시분할 시스템의 선점 스케줄링에도 적용 가능하다 다음의 예시를 보자.

 

*타임 슬라이스는 2라고 가정

Process	Arrival Time	Burst Time
P1	0	7
P2	2	4
P3	4	1
P4	5	4

 

우선 준비 큐에 P1만 있으므로, P1이 먼저 실행되고, 타임 슬라이스가 소진되서(타임 슬라이스 소진 시 실행 중이던 프로세스가 준비 상태가 된다.) 다시 준비 큐의 프로세스들 중 스케줄링을 한다.

 

준비 큐에는 P1 P2만 있으므로, P2와 P1의 burst 타임을 비교하여 P1은 5의 burst time이나 남았고, P2는 4의 burst time이 남았으므로, P2가 마저 실행되고 2초 후에 또 똑같이 타임 슬라이스가 소진되고, 다시 준비 큐의 프로세스들 중 스케줄링을 한다.

 

프로세스가 준비큐에 새롭게 도착하였을 때도 CPU를 선점하여 스케줄링이 일어난다.

 

위와 같은 프로세스를 반복하여 아래와 같은 간트차트가 나오게 된다.

평균 대기 시간은 (9 + 1 + 0 +2)/4 = 3이 된다.

 

평균 대기 시간은 비선점 스케줄링에 비해 타임 슬라이스를 도입하고 난 후 감소하게 되었다.

 

이는 타임 슬라이스 적용으로 인해서 스케줄링이 자주 일어나게 되어

뒤늦게 도착했지만 CPU 버스트 타임이 짧은 프로세스들에게 먼저 수행될 수 있는 기회가 주어졌기 때문이다.

 

---

지금까지 들었을 때, 이론적으로 가장 좋은 알고리즘 아닌가? 라는 생각이 들 것이다.

그러나 생각해보면 프로세스를 실행할 때 우리는 그 프로세스가 '몇초 정도 시간이 걸릴 것이다' 라고 정확히 판단할 수 없다.

 

즉, SJF 알고리즘의 문제점은 CPU 버스트 타임을 미리 알기 어렵다는 것이다.

 

이러한 문제를 해결하기 위해 이전 측정된 버스트 타임들을 통해 다음 버스트 시간을 예측해서 활용한다.

 

t n이 실제 n번째 CPU 버스트타임이고, τ n+1이 그 예상 값이라면 다음과 같이 정의한다.

즉, 최근에 측정된 버스트 타임에 더 많이 반영하고, 예전의 측정된 버스트 타임엔 분수의 n제곱을 하는 지수 평균을 내어 더 적게 반영하게끔 하여 다음의 버스트 타임을 예측하는 것이다.

 

 

아래의 그림에서 곡선 그래프는 CPU 버스트의 예측치이며, 선형 그래프는 실측치이다.

자료가 쌓일수록 예측치가 실측치에 수렴해나간다.

 

 

우선 순위 스케줄링 (priority scheduling)

각 프로세스의 우선순위가 정해지면, 우선순위가 제일 높은 프로세스에게 CPU를 할당하되, 우선순위가 같은 경우 FCFS를 적용하는 방법이다.

 

SJF도 CPU 버스트 시간의 역수를 우선순위로 하는 특수한 형태의 한 우선 순위 스케줄링이라고 볼 수 있다.

 

 

우선순위를 나타내는 데에는 일정 범위의 수가 사용된다.

 

시스템에 따라 낮은 값이 낮은 우선순위를 나타내는 경우가 있고, 낮은 값이 높은 우선순위를 나타내는 경우가 있다.

 

 

우선순위는 내부적 우선순위와 외부적 우선순위로 구별할 수 있다.

 

내부적 우선순위

     시간제한, 메모리 요구, 열린 파일의 수, 평균 입출력 버스트의 평균 CPU 버스트에 대한 비율 등 (측정 가능한 것들)

외부적 우선순위

     컴퓨터 사용을 위해 지불되는 비용의 타입과 양, 정책적인 변수 등 (운영체제의 외부적 기준에 의해 결정)

 

일반적으로는 CPU-bound 프로세스보다 I/O-bound 프로세스에게 높은 우선순위를 부여하여 대화성을 증진시킨다.

 

---

다음 예를 보자

 

 낮은 수가 높은 우선순위를 나타낸다고 가정

Process	Priority	Burst Time
P1	3	10
P2	1	1
P3	4	2
P4	5	1
P5	2	5

 

우선 순위순대로 P2 P5 P1 P3 P4가 실행된다.

평균 대기 시간  = (6 + 0 + 16 + 18 + 1) / 5 = 8.2

 

---

우선순위 스케줄링은 비선점형, 선점형 둘 다 구현 가능하다.

 

프로세스가 준비 완료 큐에 도착하면 새로 도착한 프로세스의 우선순위를 현재 실행 중인 프로세스의 우선순위와 비교한다.

선점형의 경우, 새로 도착한 프로세스의 우선순위가 현재 실행 중인 프로세스보다 높다면 CPU를 선점하게 되는 것이다.

 

 

우선순위 스케줄링의 문제점으로는 무한 봉쇄(Indefinite blocking), 기아 상태(Starvation)가 있다.

만약 우선순위가 높은 작업이 계속적으로 들어오게 된다면, 우선순위가 낮은 작업은 준비 상태에서 보장 없이 계속 머물게 된다.

 

이를 해결하기 위해서는 노화(에이징, Aging) 방법이 사용된다.

프로세스들이 시스템에 머무는 시간이 증가함에 따라 우선순위를 점진적으로 높여주는 것이다.

 

이렇게 해준다면 아주 낮은 우선순위의 프로세스라도 시간이 지나면서 조금씩이라도 우선순위가 높아지게 되고, 결국에는 CPU를 할당받아 실행될 수 있을 것이다.