[Chapter 5. CPU 스케줄링] 비선점/선점 스케줄링과 스케줄링 알고리즘(FCFS, SJF, 우선순위)

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다.

 

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

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

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

 

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

 

선점 스케줄링 (Preemptive Scheduling)

(1) 시분할 시스템에서 타음 슬라이스가 소진되었거나,

(2) 인터럽트 또는 시스템 호출 종료 시 그 여파로 현재 실행 중인 프로세스보다 높은 우선순위의 프로세스가 나타나는 경우

현 프로세스로부터 CPU를 강제로 회수하여 높은 우선순위의 프로세스를 실행하는 스케줄링

 

• 라운드 로빈 스케줄링 (RR)
• 다단계 큐 스케줄링
• 다단계 피드백 큐 스케줄링

 

스케줄링 알고리즘

---

* 간트 차트 (Gantt Chart)

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

 

P1, P2, P3은 프로세스(작업)

 

선입 선처리 스케줄링 (FCFS Scheduling)

FCFS : First-Come, First-Served

 

가장 간단한 CPU 스케줄링 알고리즘이다.

CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받으며, 실행 중 입출력을 요구하면 다시 다음 준비 상태에서 FCFS를 적용한다.

 

기준 : 도착 순서

 

구현 : 선입선출(FIFO) 큐

프로세스가 준비 큐에 진입하면 프로세스의 PCB를 큐의 끝에 연결한다.

CPU가 유휴 상태가 된다면 준비 큐의 앞부분에 있는 프로세스에게 CPU를 할당해준다. (비선점형 스케줄링)

 

장기 스케줄러(하드 디스크로부터 메모리로 어느 프로그램을 적재할지 결정하는 스케줄러)에서 사용 가능하며,

- 배치(batch) 작업 등

 

시분할 시스템에서는 타임 슬라이스를 적용하지 않는 프로세스에 대해 사용 가능하다.

- 백그라운드 / 실시간 프로세스 등

 

단점 : 평균 대기 시간이 굉장히 길어질 수 있으며, 호위 효과(Convoy Effect) 문제가 발생한다.

호위 효과란, 모든 다른 프로세스들이 하나의 긴 프로세스(CPU-bound)가 CPU를 방출하기를 기다리는 것을 말한다.

 

---

다음 두 예제를 보자.

 

3개의 프로세스가 각각 다음의 CPU 버스트 타임을 갖는다.

* CPU burst time : CPU 할당 후 입출력을 요구할 때까지의 시간

 

프로세스	CPU Burst Time
P1	24
P2	3
P3	3

 

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

* 대기 시간 : 준비 큐에서 대기하면서 보낸 시간의 합

 

 

(예제 1) 도착 순서 : 1, 2, 3일 경우 FCFS 스케줄링을 수행했을 때의 간트 차트

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

평균 대기 시간 = (0 + 24 + 27) / 3 = 17

 

 

(예제 2) 도착 순서 : 2, 3, 1일 경우 FCFS 스케줄링을 수행했을 때의 간트 차트

평균 반환 시간 = (3 + 6 + 30) / 3 = 13

평균 대기 시간 = (6 + 0 + 3) / 3 = 3

 

---

두 예제를 통해 도착 순서에 따라 평균 반환 시간과 평균 대기 시간에 큰 차이가 발생하는 것을 확인할 수 있다.

왜 이런 결과가 나왔을까?

 

예제마다의 도착 순서 특징을 보면

예제 1은 버스트 타임이 긴 것부터 나열한 것이고, 예제 2는 버스트 타임이 짧은 것부터 나열한 것임을 알 수 있다.

 

대기 중인 프로세스들은 CPU의 할당을 기다리는 시간이 계속해서 누적되기 때문에,

버스트 타임이 긴 것부터 CPU가 할당된다면 평균 반환 시간과 대기 시간이 훨씬 늘어날 수밖에 없다. (호위 효과 발생)

 

 

스케줄링에서 가장 기본이 되는 방법이지만

도착 순서 말고 우선순위를 정하는 데에 특별히 추가되는 정보가 없을 경우, 할 수 없이 사용하는 방법이다.

 

최단 작업 우선 스케줄링 (SJF Scheduling)

SJF : Shortest Job First

정확히는 최단 다음 CPU 버스트(Shortest-Next-CPU-Burst) 알고리즘이다.

 

CPU 이용이 가능해지면, 대기하는 프로세스들 중에서 CPU 버스트 타임이 가장 작은 프로세스에게 CPU를 할당한다.

만약 모든 프로세스의 CPU 버스트 타임이 동일한 길이를 가졌다면 FIFO 스케줄링과 동일해진다.

 

기준 : CPU Burst Time (CPU를 사용하는 시간)

 

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

두번째로 수행되는 프로세스가 가장 짧은 시간을 대기하려면 첫 번째 작업이 전체 프로세스들 중에서 가장 짧은 CPU 버스트 타임을 가져야 한다. 이를 세번째, 네 번째,... 프로세스들에도 적용하게 된다면 SJF 스케줄링과 다름이 없게 된다.

 

---

4개의 프로세스가 각각 다음의 CPU 버스트 타임을 가진다고 할 때, SJF 스케줄링을 수행했을 때의 결과는 다음과 같다.

 

프로세스	CPU Burst Time
P1	6
P2	3
P3	8
P4	7

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

평균 대기 시간 = (3 + 0 + 16 + 9) / 4 = 7

 

하지만 이 결과는 4개의 프로세스들이 모두 도착해있다고 가정했을 경우의 결과이다.

도착 시점(arrival time)까지 고려해보자.

 

프로세스	Arrival Time	CPU Burst Time
P1	0.0	7
P2	2.0	4
P3	4.0	1
P4	5.0	4

 

* 비선점형 SJF 스케줄링의 경우

평균 반환 시간 = (7 + 10 + 4 + 11) / 4 = 8

평균 대기 시간 = (0 + 6 + 3 + 7) / 4 = 4

 

가장 먼저 도착한 P1이 먼저 실행되며, P1의 실행이 끝났을 때에는 P2, P3, P4가 전부 도착하여 대기하고 있는 상태가 된다.

이때 CPU 버스트 타임이 가장 짧은 P3가 선택된다.

P3이 끝나고 난 뒤에 남아있는 P2와 P4는 CPU 버스트 타임이 4로 동일하기 때문에 더 일찍 도착한 P2가 선택된다. (FCFS 적용)

 

 

* 선점형 SJF 스케줄링의 경우 (비선점형의 확장)

선점형 SJF 스케줄링은 타임 슬라이스마다 스케줄링을 하여

해당 시점에서 가장 작은 CPU 버스트 타임을 가지는 프로세스에게 CPU를 할당해주는 것이다.

 

9에서는 P4의 남은 버스트 타임(2)이 P1의 남은 버스트 타임(5)보다 적기 때문에 P4가 선점당하지 않은 것이다.

 

평균 반환 시간 = (16 + 5 + 1 + 6) / 4 = 7

평균 대기 시간 = (9 + 1 + 0 + 2) / 4 = 3

 

P1 대기 시간 : 9 (2에서 11까지 기다린 시간)

P2 대기 시간 : 1 (4에서 5까지 기다린 시간)

P3 대기 시간 : 0 (3에 도착 → 바로 수행 → 종료)

P4 대기 시간 : 2 (5에서 7까지 기다린 시간)

 

 

평균 대기 시간은 타임 슬라이스를 도입하고 난 후 감소하였다!

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

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

 

---

SJF 스케줄링의 최대 문제점은 CPU 버스트 타임을 미리 파악하기가 어렵다는 것이다.

 

일괄처리 시스템에서 장기 스케줄링의 경우에는 사용자가 작업을 제출할 때 지정한 처리시간 제한을 이용할 수 있으나,

단기(CPU) 스케줄링에서는 다음 CPU 버스트 타임을 알 수 없기 때문에 구현이 불가능하다.

 

 

따라서 SJF 근사 방법을 사용한다.

측정된 이전의 CPU 버스트들의 길이를 지수 평균(exponential average)한 것으로 다음 버스트 시간을 예측해서 활용하는 것이다.

 

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

a와 (1-a)가 모두 1보다 작거나 같기 때문에 각 후속 항들은 그 전항보다 가중치가 작게 된다.

따라서 최근의 실측치는 더 많이, 예전의 실측치는 더 적게 반영할 수 있다.

 

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

자료가 쌓일수록 예측치가 실측치에 수렴하는 것을 볼 수 있다.

 

 

우선순위 스케줄링 (Priority Scheduling)

준비 큐에 들어있는 프로세스들 중 가장 높은 우선순위를 가진 프로세스에게 CPU를 할당하되,

우선순위가 같을 경우 선입 선처리(FCFS) 순서로 스케줄된다.

 

기준 : 우선순위

 

SJF 알고리즘은 우선순위 스케줄링 알고리즘의 특수한 형태이다.

SJF의 우선순위(p)는 다음 CPU 버스트 예상 시간의 역수이다. (p = 1/τ)

 

---

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

 

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

여기서는 낮은 수가 높은 우선순위를 나타낸다고 가정하도록 하자.

 

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

 

내부적 우선순위

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

외부적 우선순위

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

 

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

 

---

5개의 프로세스가 각각 다음의 CPU 버스트 타임과 우선순위를 가진다고 할 때, 우선순위 스케줄링을 수행했을 때의 결과는 다음과 같다.

(CPU 버스트 타임은 주어졌다고 가정하자)

 

프로세스	CPU Burst Time	Priority
P1	10	3
P2	1	1
P3	2	4
P4	1	5
P5	5	2

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

 

---

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

 

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

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

 

 

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

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

 

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

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

 

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