[운영체제] 프로세스 스케줄링 알고리즘 정리

프로세스의 개념과 스케줄링에 관한 기본기가 부족하다면, 

아래 포스팅 먼저 복습하고 오자.

 

[운영체제] 프로세스 개념 정복하기
[운영체제] 프로세스 생성과 종료 / 요약 정리
[운영체제] 프로세스 스케줄링 개념 정리

 

프로세스 스케줄링 알고리즘

1. FCFS (First-Come, First-Served), 선입 선처리

Ready queue를 FIFO로 구현하여 들어온 순서대로 CPU를 할당한다.

구현이 제일 간단하고, 이해하기 쉽다. 

비선점 스케줄링으로 Ready queue에 있는 프로세스 입장에서는 평균 대기시간이 길어질 수 있다.

 

* 비선점 스케줄링 : 현재 실행 중인 프로세스가 자발적으로 CPU 사용을 중단하는 경우에만 CPU 스케줄링을 수행하는 방법

* 선점 스케줄링 : 운영체제의 판단에 따라 현재 실행 중인 프로세스를 강제로 중단시키고, CPU 스케줄링을 수행하는 방법

 

<예>

 

FCFS 스케줄링

	대기 시간	평균 대기 시간
큐 도착 순서 : P1, P2, P3	P1 = 0, P2 = 24, P3 = 27	(0+24+27)/3 =17
큐 도착 순서 : P2, P3, P1	P1 = 6, P2 = 0, P3 = 3	(6+0+3)/3 = 3

똑같은 프로세스를 스케줄링을 하는데도 큐가 어떻게 구성되느냐에 따라 결과가 완전히 달라진다.

=> 좋은 스케줄링 방식이 아니다.

 

2. SJF (Shortest-Job First), 최단 작업 우선

Ready queue에 들어온 순서와는 상관없이 다음번 프로세스의 CPU 사용 시간(CPU burst time)이 가장 짧은 것을 먼저 빼서 실행한다.

평균 대기시간 측면에서 최적의 스케줄링 알고리즘이나 프로세스의 다음 CPU 사용시간을 예측해야하는 어려움이 있다.

다음번 CPU 실행이 짧은 것에 우선순위를 부여하는 우선순위 스케줄링이라고도 할 수 있다.

 

<예>

SJF 스케줄링

P1, P2, P3, P4 순으로 queue에 있을 때	대기시간	평균 대기 시간
SJF 스케줄링	P1 = 3, P2 = 16, P3 = 9, P4 = 0	(3+16+9+0)/4 = 7
FCFS 스케줄링	P1 = 0, P2 = 6, P3 = 14, P4 = 21	(0+6+14+21)/4 = 10.25

 

<참고> Shortest Remaining Time First 스케줄링
현재 CPU가 실행하고 있는 프로세스보다 Ready Queue에 도착한 새로운 프로세스의 CPU burst 시간이 작다면 이 프로세스를 CPU에 할당한다. (선점 스케줄링) 

 

3. 우선 순위

Ready queue 내에서 가장 높은 우선순위를 가진 프로세스에게 CPU를 할당한다.

우선 순위가 동일한 경우 FCFS 스케줄링 적용한다.

낮은 우선순위의 프로세스가 무한히 대기하는 경우가 발생할 수 있다 (Infinite blocking, starvation)

해결책 : aging 기법 => Ready queue에서 오래 대기하는 프로세스의 우선순위를 점진적으로 증가시켜 실행이 안되는 경우가 없게 한다. 

 

<예>

우선순위 스케줄링

P1, P2, P3, P4, P5 순으로 queue에 있을 때	대기 시간	평균 대기 시간
우선순위 스케줄링	P1 = 6, P2 = 0, P3 = 16, P4 = 18, P5 = 1	(6+0+16+18+1)/5 = 8.2

 

4. 라운드 로빈 (Round-Robin)

CPU의 시간을 잘게 쪼개서 그것을 각 프로세스에게 나누어준다

매 Time Slice (Time Quantum) 마다 프로세스에 Timer Interrupt 가 발생하고 이때 프로세스 스케줄링을 수행하는 선점 스케줄링이다.

Ready queue는 Circular FIFO queue로 구현한다.

일반적으로 SJF 보다 평균 총 실행 시간이 길지만 응답시간이 짧다.

 

<예>

라운드 로빈 스케줄링

	대기 시간	평균 대기 시간
라운드 로빈 스케줄링	P1 = 10-4, P2 = 4, P3 = 7	(6+4+7)/3 = 5.66

=> 시분할 (Time-Sharing) 시스템의 스케줄링 알고리즘으로, 멀티태스킹의 근본이 되는 스케줄링이다.

 

* Time Quantum (Time Slice) 를 어떻게 결정할 것인가?

If Time quantum이 매우 크다면	If Time quantum이 매우 작다면,
FCFS 스케줄링과 같아진다.	1. 프로세스의 응답성이 좋아지지만 잦은 문맥 교환(Context Switch) 으로 Overhead 발생한다. 2. CPU Burst 보다 작아지면 평균 총 실행 시간이 길어진다.

경험에 의한 법칙으로, Time quantum은 CPU burst의 80%보다 커야 한다고 한다...

실제 운영체제에서는 수ms ~ 수십ms 정도로 사용하고 있다고 한다.

 

5. 다단계 큐 (Multilevel Queue)

컴퓨터에서 프로세스들은 서로 다른 특성을 가지고 있어 각자에게 잘 맞는 스케줄링 방법이 다를 것이다.

(응답 시간이 빨라야 하는 프로세스도 있을 것이고, 진득하게 CPU를 차지하는게 더 적합 프로세스도 있을 것이고~)

때문에 여러개의 Ready queue를 두고 각 큐마다 다른 스케줄링 알고리즘을 적용하는 방식이 다단계 큐다.

 

<예> 

- Foreground 프로세스 : Round-Robin 사용 (빠른 응답 시간을 위해)

- Background 프로세스 : FCFS 사용 (진득하게 CPU를 쓸 수 있도록)

 

하지만 CPU는 결국 1개이기 때문에 특성에 따라 큐를 분리하여 묶어두되 큐 사이에서 스케줄링을 할 필요가 생긴다.

<참고> 큐 스케줄링 방법
1. 고정 우선순위 스케줄링 
2. 라운드 로빈처럼 time sharing 방식을 쓰되, 각 큐마다 정해진 비율의 시간을 할당하는 방법

<예>
- Foreground Ready queue : 80% 
- Background Ready queue : 20%
=> 이렇게 하면, Foreground Ready queue에 있는 프로세스가 좀더 CPU를 차지할 확률이 높다.

 

6. 다단계 피드백 큐 (Multilevel Feedback Queue)

한 큐에 있던 프로세스가 다음번 Ready queue로 들어갈 때, 피드백을 통해 더 적합한 다른 큐로 들어갈 수 있는 걸 허용하는 것이다.

=> 가장 복잡하지만, 스케줄링의 유연성이 높아 실제 운영체제 스케줄러에 적용되는 알고리즘이다.