CPU 스케줄링이란?

* 본 내용은 운영체제를 공부하며 추후 복습하기 위해 포스팅하는 게시물입니다.

 

운영체제는 메모리에 할당된 여러 프로세스에게 어떻게 CPU를 할당할지 결정해야한다.

이를 위해서 다양한 CPU 스케줄링은 사용하며 이번 게시물은 CPU 스케줄링이 어떤 것이 존재하는지 알아보며 이를 설명하기 위한 용어들을 알아보자

 

장기 스케줄링

 - 프로그램을 실행할 때 프로그램을 메모리에 할당할지 결정하는 방법

 - 현재 운영체제에서 사용되지 않는다

 

중기 스케줄링

 - 메모리가 부족하여 디스크의 일부를 메모리처럼 사용할 때 어떤 프로세스를 메모리에서 제거할지 결정하는 방법

 

단기 스케줄링

 - CPU를 Ready Queue에 존재하는 프로세스에게 어떻게 할당할지 결정하는 방법

 

CPU 스케줄링 

 - 단기 스케줄링을 의미

 

디스패처

 - CPU 스케줄링에 의해 결정된 프로세스에게 CPU의 제어권을 할당하여 실행

 

FCFS(First Come First Served) 

- 가장 먼저 Ready Queue

에 들어온 프로세스에게 CPU를 할당하는 알고리즘

- 가장 먼저 도착한 프로세스의 수행시간이 짧을수록 CPU를 할당받기 위한 평균 대기시간이 짧아지는 반면 수행시간이 길다면 평균 대기시간이 길어지는게 특징

 

SJF(Shortest Jop First)

- 우선순위를 기준으로 스케줄링하는 알고리즘의 일종

- 프로세스의 수행시간이 길이에 따라 우선순위가 결정된다.

- Ready Queue에 도착한 프로세스의 수행시간이 가장 짧으면 먼저 수행되는 알고리즘

- 비선점과 선점이 존재하며 비선점보다 선점이 평균 대기시간이 더 짧다

- CPU 스케줄링을 하기 위해 최적화된 알고리즘이지만 몇몇 문제점이 존재하여 구현이 불가능하다

- Starvation(기아)가 발생할 수 있으며, 프로세스의 수행시간을 정확하게 알 수 없음

- Aging기법을 통해 Starvation을 방지할 수 있으며 프로세스의 수행시간의 추정치를 구할 수 있음

 

* Starvation 이란?

- 우선순위를 기준으로 CPU 스케줄링 하기 때문에 특정 프로세스보다 우선순위가 높은 프로세스가 Ready Queue에 도착하여 먼저 실행되어 특정 프로세스가 실행될 수 없는 상황을 의미

- 이에 대한 해결책으로는 일정시간마다 프로세스의 우선순위를 높임으로써 해결할 수 있다

 

RR(Round Robin)

 - Ready Queue에 존재하는 프로세스에게 동일한 시간을 할당하는 알고리즘

 - 프로세스의 응답시간이 짧은게 특징

 - Ready Queue에 동일한 수행시간의 프로세스가 여러 개 존재한다면 프로세스들을 수행 후 종료하기까지 시간이 길어진다

 

MultiLevel Queue

 - 프로세스 특정에 맞춰 Ready Queue를 여러 개로 놓는 방식의 알고리즘

 - 프로세스가 생성할 때 어느 큐에 놓을지, 큐마다 사용해야하는 CPU 스케줄링이 어떤 것인지 등 고려해야할 점이 많음

 - 우선순위가 낮은 큐의 프로세스의 경우 Starvation이 발생할 수 있음

 

MultiLevel Feedback Queue

 - MultiLevel Queue를 보완한 방식의 알고리즘

 - Ready Queue 간의 승격/강등 같은 개념이 존재하여 프로세스가 큐를 이동할 수 있음

 - 우선순위에 따라 나눠진 Ready Queue에 우선순위 맞춰 시간을 할당함(첫번째 ReadyQueue는 8ms 등)

 - 할당된 시간안에 수행되지 못한다면 다음 큐로 강등되는 형식

 - 모든 프로세스가 첫 번째 Ready Queue에 놓인 후 수행되는 방시이기 때문에 수행시간이 짧은 프로세스는 수행이 완료되는게 특징