CPU Scheduling, 스케줄링

CPU Scheduling

운영체제가 수행하는 스케줄링 중에서 CPU 스케줄링이 우리에게 익숙한 스케줄링이다.

 

우리가 사용하는 컴퓨터는 여러 개의 프로그램이 돌아갈 수 있고, 이에 따라 동시성, 병렬성이라는 특성을 가지고 여러 프로세스를 한꺼번에 돌리는 것이 CPU의 역할이다. 이때 CPU는 스케줄링을 통해 다음에 돌아갈 프로세스를 선택한다.

 

❓ CPU Scheduling

CPU 스케줄링이란, 운영체제에서 CPU를 사용할 수 있는 프로세스를 선택하고, CPU를 할당하는 작업
이다. 프로세스의 우선 순위, 작업량 등을 고려하여 효율적으로 선택한다.

 

---

Preemptive VS Non-preemptive

우선 스케줄링의 방식은 선점방식과 비선점 방식으로 나뉜다.

Preemptive, 선점

Preemptive(선점)는 프로세스가 CPU를 점유하고 있는 동안 모든 작업을 끝내지도 않았는데 다른 프로세스가 CPU를 강제로 빼앗을 수 있는 방식이다. 즉, 프로세스가 정상적으로 수행 중인 가운데 다른 프로세스가 CPU를 강제로 점유하여 실행할 수 있다.

Non-preemptive, 비선점

Non-preemptive(비선점)은 말 그대로 선점 방식과 반대이다. 한 프로세스가 한 번 CPU를 점유했다면, I/O 발생 또는 프로세스가 종료될 때까지 다른 프로세스가 CPU를 점유하지 못하는 것이다.

---

Scheduling criteria, 스케줄링의 척도

Scheduling criteria는 스케줄링의 효율을 분석하는 기준들이다.

CPU Utilization, 이용률, %	CPU가 수행되는 비율
Throughput, 처리율, jobs/sec	단위 시간 당 처리하는 작업의 수(처리량)
Turnaround time, 반환 시간	프로세스 처음 시작 시간부터 모든 작업을 끝내고 종료하는 데 걸린 시간(CPU, waiting, I/O 등 모든 시간을 포함)으로 짧을수록 좋다
Waiting Time, 대기 시간	CPU를 점유하기 위해서 Ready Queue에서 기다린 시간(다른 큐는 제외)
Response Time, 응답 시간	일반적으로 대화형 시스템에서 입력에 대한 반응 시간

---

CPU Scheduling Algorithms

이러한 CPU 스케줄링은 작업의 우선순위, CPU 사용률 등을 고려하여 다양한 방식으로 스케줄링을 수행할 수 있다.

---

FCFS, First-Come, First-Served - non-preemptive

먼저 온 프로세스가 먼저 CPU를 점유하는 방식이다.

 

이는 매우 단순하고 많이 사용하는 방법이지만, 모든 부분에서 효율적이지는 않다.

한계점

❓ Convoy Effect, 호위 효과

CPU 시간을 오래 사용하는 프로세스가 먼저 수행하는 동안 나머지 프로세스들은 그만큼 오래 기다려야 하는 것을 말한다.

 

예를 들어 다음과 같이 세 개의 프로세스가 존재하고, CPU를 사용한 시간(burst time)이 다음과 같이 걸린다고 가정하자.

Process	CPU 사용 시간(msec)
P1	24
P2	3
P3	3

 

만약 P1, P2, P3 순서대로 들어왔고, FCFS 방식을 사용하면 평균 대기 시간은 다음과 같다.

 

만약 프로세스가 들어온 순서가 P3, P2, P1 라면 다음과 같다.

 

두 예제 모두 모든 프로세스가 끝난 시간은 30msec로 같지만, 평균 대기 시간은 14msec나 차이가 난다. 즉, CPU의 수행시간이 긴 프로세스가 먼저 실행된다면, FCFS 방식은 매우 비효율적임을 알 수 있다.

---

SJF, Shortest-Job-First

가장 짧게 수행되는 프로세스가 가장 먼저 수행되는 방식이다.

 

FCFS에서 보았듯이, 수행 시간이 짧은 프로세스가 먼저 오는 것이 평균 대기 시간이 짧은 것을 알 수 있었다. 이를 이용한 것이 바로 SJF이다.

 

증명

SJF는 평균 대기 시간이 가장 짧은 알고리즘이다

 

아래와 같은 프로세스가 있다고 가정하자.

Process	Burst Time(msec)
P1	6
P2	8
P3	7
P4	3

 

FCFS 방식을 사용하여 P1, P2, P3, P4의 평균 대기 시간을 계산해보자.

 

SJF 방식을 사용하여 P4, P1, P3, P2 순서대로 평균 대기 시간을 계산해보자.

 

FCFS와 SJF를 비교했을 때 SJF가 더 짧은 것을 볼 수 있다. 이는 수학적으로도 증명되어 있으며, 어떤 경우에도 SJF가 평균 대기 시간은 가장 짧다.

 

두 가지 방식의 SJF : preemptive / non-preemptive

보통 비선점 방식을 일반 SJF라 하고, 선점 방식의 SJF를 남은 시간이 더 짧은 프로세스를 먼저 실행하는 Shortest-Remaining-Time-First(최소 잔여 시간 우선) 스케줄링 방식이라 말한다.

 

아래는 위 예제와 달리 도착 시간이 추가되었다.

Process	Arrival Time(msec)	Burst TIme(msec)
P1	0	8
P2	1	4
P3	2	9
P4	3	5

non-preemptive 방식: 빼앗을 수 없다.

 

가장 먼저 도착한 P1이 수행되는 동안, P2, P3, P4 모두 도착한다. P1보다 P2, P4의 수행 시간이 더 짧지만 non-preemptive이므로 이미 수행 중인 프로세스가 끝날 때까지 기다려야 한다. 따라서 평균 대기 시간은 다음과 같다.

preemptive 방식: 수행 시간이 더 짧으면 빼앗는다.

이번에는 preemptive 이므로, 프로세스가 도착할 때마다 어느 프로세스가 가장 시간이 짧은 작업인지 선택해야 한다. 위에서는 P1 프로세스가 진행 중에 P2 프로세스가 도착했을 때, 현재 남은 burst time 중 가장 짧은 프로세스가 P2이므로, P1의 수행을 멈추고 P2가 수행을 시작한다.

 

한계점

이렇게만 보면 SJF 방식을 사용할 수 있겠지만, 사실 이 방식은 매우 비현실적이다. 왜냐하면 현실적인 컴퓨터 환경에서는 프로세스의 CPU 점유 시간(burst time)을 알 수 없기 때문이다. 한 프로세스가 실행되는 중에는 굉장히 많은 변수가 있기 때문에, CPU 점유 시간을 정확히 측정하려면 실제로 수행하는 수밖에 없다. 실제 측정한 시간으로 예측해서 SJF를 사용할 수도 있지만, 이는 오버헤드가 매우 큰 작업으로 잘 사용되지 않는다.

---

Priority

우선순위가 높은 프로세스가 먼저 선택된다

 

일반적으로 운영체제에서 우선순위는 정수 값으로 나타내며, 작은 값이 우선순위가 높다(Unix/Linux 기준)

동작

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

 

우선순위대로 수행하면 다음과 같다.

preemption : 프로세스가 새로 들어올 때마다 우선순위를 비교하여 빼앗을 수 있다.

non-preemption : 동시에 들어온 프로세스에 대해서만 우선순위를 비교하여 실행한다.

 

둘 다 가능하다.

 

우선순위를 정하는 방법

내부적인 요소

• time limit
• memory requirement
• I/O, CPU burst
  • I/O 작업은 길고, CPU 작업은 짧은 프로세스 우선 등

외부적인 요소

• amount of funds being paid
• political factors

 

한계점 : Starvation(기아현상) ⇒ aging

❓ Starvation, 기아현상

CPU 점유를 오랫동안 하지 못하는 현상

 

Priority 스케줄링 방식에서 우선순위가 매우 낮은 프로세스가 ready queue에 대기하고 있다고 가정해보자. 이 프로세스는 아무리 오래 기다려도 CPU를 점유하지 못할 가능성이 매우 크다.

 

실제 컴퓨터 환경에서는 새로운 프로세스가 자주 ready queue에 들어오며, 이러한 프로세스 모두 우선순위가 높은 상태라면 이미 기다리고 있던 우선순위가 낮은 프로세스는 하염없이 기다리고만 있는 상태로 남아있을 수 있다.

해결 방법 : aging

 

이 방식은 ready queue에서 기다리는 동안 일정 시간이 지나면 우선순위를 일정량 높여주는 것이다. 그러면 우선순위가 매우 낮은 프로세스라 하더라도, 기다리는 시간이 길어질수록 우선순위도 계속 높아지므로 수행될 가능성이 커진다.

---

RR, Round-Robin - preemptive

원 모양으로 모든 프로세스가 돌아가며 특정 시간 동안 수행되는 방식을 말한다.

 

이는 시분할 시스템에서 주로 사용하는 방식이다.

 

❓ 시분할 시스템, Time-sharing

여러 명의 사용자가 사용하는 시스템에서 컴퓨터가 사용자들의 프로그램을 번갈아가며 처리해줌으로써 각 사용자에게 독립된 컴퓨터를 사용하는 느낌을 주는 것을 말한다.

 

하나의 프로세스가 특정 시간 동안 수행하고 다시 대기 상태로 돌아간다. 그리고 다음 프로세스가 역시 같은 시간 동안 수행 후 대기한다. 이러한 작업을 모든 프로세스가 돌아가면서 하며, 마지막 프로세스가 끝나면 다시 처음 프로세스로 돌아와 반복한다.

Time Quantum (Time Slice)

 

위에서 말한 일정 시간을 Time Quantum(Time Slice)라 부른다. Time Quantum은 일반적으로 10 ~ 100msec 사이의 범위를 갖는다.

preemptive

 

RR은 한 프로세스가 종료되기 전에 time quantum이 끝나면 다른 프로세스로 CPU를 넘겨주기 때문에 일반적으로 preemptive이다.

 

동작 과정

아래와 같은 프로세스가 있고, time quantum = 4msec이라 가정하자

 

Process	Burst Time(msec)
P1	24
P2	3
P3	3

 

1. P1이 0msec에 수행을 시작하여 종료되기 전에 time이 끝나, P2가 수행된다
2. P2가 4msec에 수행을 시작하여 time quantum이 끝나기 전에 7msec에 프로세스가 종료되고, P3가 이어서 수행된다
3. P3가 7msec에 수행을 시작하여 time quantum이 끝나기 전에 10msec에 프로세스가 종료되고, 다시 P1이 이어서 수행된다
4. P1만 남았기 때문에 time quantum이 끝나더라도 종료될 때까지 계속 수행한다.

 

주의할 점

RR의 성능은 time quantum에 의존적

 

RR 방식은 time quantum의 크기에 따라 AWT와 같은 스케줄링 척도가 바뀐다. 따라서 RR 방식은 time quantum에 매우 의존적인 것을 알 수 있다.

만약 time quantum의 크기를 무한에 가깝게 설정한다면, FCFS와 동일하게 동작한다. 반대로 time quantum의 크기를 0에 가깝게 설정한다면, switching overhead가 매우 증가하여 비효율적이다. 결론은 time quantum은 적당한 크기로 설정해주어야 하며, 일반적으로 10~100msec로 정한다.

---

Multilevel Queue

Multilevel Queue를 살펴보기 전에 프로세스 그룹에 대해 살펴보자. 프로세스는 기준에 따라서 여러 그룹으로 나눌 수 있다.

System processes	운영체제 커널 수준의 프로세스
Interactive processes	유저 수준의 대화형 프로세스
Interactive editing processes
Batch processes	대화형 프로세스의 반대인 것으로, 일정량을 한 번에 처리하는 프로세스(ex. 컴파일러)
Student processes

 

위와 같이 여러 성격에 따라 프로세스를 그룹으로 나눌 수 있는데, 이를 하나의 큐에 사용하는 것은 비효율적이라 판단하였다.

즉, 각 프로세스 그룹에 따라 큐를 두어 여러 개의 큐를 사용하는 방식이다.

이렇게 나뉜 큐는 각각 개별적으로 다양한 규칙을 정할 수 있다.

• 큐마다 우선순위 지정
  • System process는 커널 수준에서 중요한 작업이므로 우선순위가 높은 그룹이다. 반면에 Batch process는 운영체제의 개입이 매우 적으므로 우선순위가 가장 낮다.
• 큐마다 CPU 시간을 다르게 배정
• 큐마다 다른 스케줄링 방식 적용

---

Multilevel Feedback Queue

여러 개의 큐를 두고 대기 시간, 우선 순위 등에 따라 프로세스를 다른 큐로 옮기며 대기 시간을 조정한다.

먼저 모든 프로세스는 가장 위의 큐에서 CPU의 점유를 대기한다. 이 상태로 스케줄링이 진행되다가, 이 큐에서 기다리는 시간이 너무 길다면 아래의 큐로 프로세스를 옮긴다. 이와 같은 방식으로 대기 시간을 조정할 수 있다.

 

만약 우선순위 순으로 큐를 사용하는 상황에서 우선순위가 낮은 큐에 있는 프로세스에서 starvation이 발생한다면, 우선순위가 높은 큐로 옮길 수도 있다.

 

이 외에도 각 큐마다 다른 스케줄링, 다른 우선순위 등을 사용할 수 있다.

---

대부분의 상용 운영체제에서는 여러 개의 큐를 사용하고 각 큐마다 다른 스케줄링 방식을 적용한다. 프로세스 성격에 맞는 스케줄링 방식을 사용하여 최대한 효율을 높일 수 있는 방법을 선택한다.

---

참고자료

[운영체제(OS)] 6. CPU 스케줄링

 

<운영체제> 시분할 시스템이란