[OS] 프로세스 스케줄링(CPU 스케줄링, 스케줄링 알고리즘)

1. 스케줄러 / 스케줄링이란?

---

 작업 관리자를 실행해 본 적이 있다면 아래와 같은 화면을 본 적이 있을 것이다.

[그림 1] 작업 관리자에서 프로세스 상태

 위 그림과 같이 여러개의 프로세스의 정보를 확인 할 수 있다. 여기서 프로세스란, 운영체제에서 실행되는 프로그램의 최소 단위, 실행되고 있는 프로그램이라 이해하면 된다.

 

 이 프로세스들은 어디에서 어떻게 실행되는 걸까? 답은, 컴퓨터의 두뇌라 하는 CPU의 코어에서 실행되고 있다. 옛날에는 일반 소비자용 CPU의 경우 1개의 코어를 가지는 것이 대부분이었다. 이 말은 CPU가 한 번에 한 개의 연산을 수행한다는 것인데, 도대체 그 시절에는 인터넷을 하면서 음악을 듣고 동시에 게임도 할 수 있었던 걸까?

 

 바로 컨텍스트 스위칭(Context switching)이라는 기술 때문에 가능하다. 컴퓨터에서 프로그램이 실행될 때 겉으로는 프로그램이 연속적으로 작동하는 것처럼 보이지만 실제로는 그렇지 않다.

 

[그림 2] 코어 하나에서 프로그램의 실행 모습

 위 그림과 같이 프로그램이 하나만 쭈욱 작동하는 것이 아닌, 프로그램 하나가 잠시 실행되었다가 다시 다른 프로그램으로 스위칭 되는 것을 볼 수 있다. 이렇게 스위칭되면서 작업되는 것이 우리 눈에는 여러 개의 프로그램이 동시에 실행되는 것처럼 보이는 것이다.

 

 그렇다면 어떤 기준으로 스위칭 되는 것 일까? 이 기준을 운영체제의 스케줄러(scheduler)가 결정하고 기준에는 여러가지 알고리즘들이 있다.

 

 

 

2. 스케줄링 방식

---

 스케줄링에는 크게 선점형(Preemptive) 스케줄링과 비선점형(Non-Preemptive) 스케줄링 2가지 방식으로 나뉜다.

 

2.1) 선점형(Preemptive) 스케줄링

 프로세스가 CPU를 할당받아 실행 중이더라도 I/O나 인터럽트가 발생한 것도 아니고 모든 작업을 끝내지도 않았는데, 다른 프로세스가 CPU를 강제로 빼앗을 수 있는 방식이다.

 

 CPU 처리 시간이 매우 긴 프로세스가 CPU 사용 독점을 막을 수 있어 효율적인 운영이 가능하지만 잦은 스위칭으로 오버헤드가 많이 발생한다.

 

 

2.2) 비선점형(Non-Preemptive) 스케줄링

 선점형과 반대로, 프로세스가 CPU를 점유하고 있다면 이를 빼앗을 수 없는 방식이다. 한 프로세스가 CPU를 점유했다면, I/O나 인터럽트가 발생 또는 프로세스가 종료될 때까지 다른 프로세스가 CPU를 점유하지 못하는 것이다.

 

 필요한 스위칭만 일어나기 때문에 오버헤드가 상대적으로 적지만 프로세스 배치에 따라 효율성 차이가 많이 난다.

 

 

 

3. 스케줄링 종류

---

3.1) First-Come, First-Served(FCFS)

 FCFS는 비선점형(Non-Preemptive) 스케줄링으로, 먼저 온 프로세스가 먼저 CPU를 점유하는 방식이다.

Process	Burst Time(msec)
P1	15
P2	6
P3	3

 

 프로세스가 차례대로 P1, P2, P3 순서대로 들어왔다고 가정하고 평균 대기시간을 계산하면 아래와 같다.

 

 ● Average Waiting Time:  (0+15+21) / 3= 12msec

 

만약, 프로세스가 들어온 순서가 P3, P2, P1이라면 아래처럼 바뀔 것이다.

 

● Average Waiting Time:  (0+3+9) / 3= 4 msec

 

 프로세스가 끝난 시간은 24 msec로 동일하지만, 평균 대기시간으로는 많은 차이를 보인다. 즉, 들어온 순서에 따라 효율성의 차이가 크게 생길 수 있다.

 

P1, P2, P3 순서로 들어온 것을 Convoy Effect라고 하는데, 이는 CPU 시간을 오래 사용하는 프로세스가 먼저 수행하는 동안 나머지 프로세스들은 그만큼 오래 기다리는 것을 일컫는다. 이는 FCFS의 단점 중 하나다.

 

3.2) Shortest-Job-First(SJF)

 SJF는 가장 짧게 수행되는 프로세스가 가장 먼저 수행되는 방식을 말한다.

SJF는 선점형(Preemptive)과 비선점형(Non-Preemptive) 방식 모두 가능하다.

Process	Burst Time(msec)
P1	15
P2	6
P3	3

● Average Waiting Time:  (0+3+9) / 3= 4 msec

 

간단하게, FCFS방식에서 가장 CPU 사용시간이 낮은 시간 순서대로 들어온다고 생각하면 된다.

수학적으로 어떤 방식보다 평균 대기시간이 짧다고 할 수 있는데. 그렇다면 SJF가 가장 효율적인 스케줄링 방식일까? 사실 이 스케줄링 방법은 매우 비현실적이다.

 

 현실적인 컴퓨터 환경에서는 프로세스의 CPU 점유 시간을 알 수 없을뿐더러 프로세스가 실행 중에는 많은 변수가 존재하기 때문에 CPU 점유 시간을 알려면 실제로 수행하여 측정하는 수밖에 없다. 하지만 이는 큰 오버헤드를 발생시키므로 잘 사용되지 않는다.

 

3.3) Priority

 Priority 스케줄링은 우선순위가 높은 프로세스 먼저 선택되는 스케줄링 알고리즘이다.

Priority 스케줄링은 역시, 선점형(Preemptive)과 비선점형(Non-Preemptive) 방식 모두 가능하다.

Priority가 낮을수록 우선순위가 높다고 가정하자.

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

 

● Average Waiting Time:  (0+1+2+12) / 4= 3.75 msec

 

 우선순위를 정하는 방법에는 크게 내부적인 요소와 외부적인 요소로 나뉜다.

• Internal: Time limit, Memory Requirement, I/O to CPU burst(I/O 작업은 길고, CPU 작업은 짧은 프로세스 순)

• External: Amount of funds being paid, Political Factors 등

 Priority 스케줄링의 문제점은 Starvation(기아)이 있다. Starvation은 프로세스가 CPU 점유를 오랫동안 하지 못하는 현상을 일컫는데, 우선순위가 매우 낮은 프로세스가 대기하고 있다고 가정해보자. 이 프로세스는 아무리 오래 기다려도 CPU를 점유하지 못할 가능성이 매우 크다.

실제 컴퓨터 환경에서도 새로운 프로세스가 끊임없이 들어오고, 이러한 프로세스가 모두 우선순위가 높다면 이미 기다리고 있던 우선순위가 낮은 프로세스는 하염없이 기다리게 된다.

 

 이를 해결하는 방법으로 Aging이 있는데 우선순위가 낮은 프로세스가 기다리는 동안 일정 시간이 지나면 우선순위를 일정량 높여주는 방식이다. 이렇게 한다면 우선순위가 낮더라도 시간이 지나면 우선순위가 높아지므로 수행될 가능성이 높아진다.

 

 

3.4) Round-Robin(RR)

 Round-Robin(RR)은 일정 시간을 정하여 각각의 프로세스가 이 시간 동안만 수행하고 다시 대기 상태로 돌아가는 방식을 말한다. Round-Robin은 기본적으로 선점형(Preemptive)이다. 일정 시간이 끝나면 다른 프로세스로 CPU를 넘겨주기 때문이다.

 

(Time Quantum = 3 msec)

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

 위에서 말한 일정 시간을 Time Quantum(Time Slice)이라 부른다. Time Quantum은 일반적으로 10~100 msec 사이의 범위를 갖는다. 위의 예는 Time Quantum이 3 msec이고 해당 단위별로 CPU를 점유하는 것을 볼 수 있다.

 

● Average Waiting Time:  (0+3+6+6) / 3= 5 msec

 

RR방식은 Time Quantum의 크기에 따라 매우 의존적인 것을 알 수 있다.

Time Quantum 크기를 무한에 가깝게 설정한다면 FCFS와 동일하게 동작하고. 반대로, 매우 작게 설정하면 스위칭 오버헤드가 매우 커서 비효율 적이다. 즉 Time Quantum 값을 적당한 크기로 설정해줘야 한다.

 

 

참고 및 출처

---

https://modoocode.com/269

https://velog.io/@codemcd/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9COS-6.-CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81