[OS] 3. CPU Scheduling

1. 기본 개념

다중 프로그래밍의 경우에는 항상 실행할 수 있는 프로세스가 있도록 하여 CPU의 사용률를 극대화 하는데에 있다.

따라서 CPU의 스케줄링은 OS 성능에 있어서 중요한 이슈중에 하나이다.

 

스케줄링의 종류로는 2가지가 있다.

1. 선점: 조건이 만족되면 기존에 실행되는 프로세스를 중단하고 다른 프로세스를 CPU에 할당하는 것
2. 비선점: 프로세스가 CPU에 할당되면 종료 / 대기 상태가 될 때까지 CPU를 점유하는 것

여기서 스케줄러가 선택한 프로세스를 CPU에 할당해주는 역할을 dispatcher라고 부른다.

 

2. 스케줄링 알고리즘

FCFS(First Come First Service) 알고리즘

이름 그대로 먼저 요청된 프로세스를 먼저 처리해주는 알고리즘이다.

출처: https://tutorialbit.com/

FCFS의 단점으로는 "호위 효과(Convoy effect)"가 발생할 수 있다.

호위효과
하나의 큰 프로세스가 CPU를 양보할 때까지 다른 모든 프로세스가 기다리는 현상

 

SJF(Shortest Job First) 알고리즘

위 알고리즘도 이름에서 볼 수 있듯, 가장 짧은 것을 먼저 실행해주는 프로세스이다.

출처: https://tutorialbit.com/

SJF 알고리즘의 단점으로는 "기아(Starvation)"이 발생할 수 있다.

또한, CPU의 사용시간을 미리 알기도 어렵다는 점도 있다.

Starvation
오래 걸리는 프로세스는 너무 늦게 CPU를 할당 받는 현상

 

우선순위 스케줄링

프로세스에 우선순위를 부여하여, 그 우선순위대로 프로세스를 실행하는 것이다.

이 우선순위 스케줄링의 경우에도 SJF 알고리즘과 비슷하게 기아 현상이 발생할 수 있다.

 

하지만, 우선순위 스케줄링은 이를 극복하기 위한 방법으로 "aging 기법"을 사용한다.

aging 기법
대기하는 프로세스의 우선순위를 점진적으로 증가

 

Round-Robind(RR) 알고리즘

현재의 운영체제들은 RR 알고리즘에 기반한 스케줄링 기법을 사용하고 있다.

이 알고리즘은 time quantum을 이용해서 특정 시간을 정의하고, 프로세스를 정해둔 시간이 지나게 되면, 다음 프로세스로 전환하는 방법의 알고리즘이다.

 

출처: 위키백과

 

다중레벨 큐 알고리즘

system process, interactive process, interactive editing process, batch process, student process 등 여러 단계의 queue로 나눈 뒤 순서대로 우선 순위에 맞게 대기하는 알고리즘이다.