[OS] CPU 스케줄러 개념과 스케줄링 알고리즘 종류

CPU 스케줄러 및 스케줄링 알고리즘 

CPU는 코어 1개마다 하나의 프로세스만 실행할 수 있고 동시에 여러개의 프로세스를 실행할 수 없다.
 
우리는 평소 여러개의 프로그램을 동시에 실행하며 컴퓨터를 하기에, 하나의 코어에 여러개의 프로세스를 동시에 실행하는 것 처럼 보이지만
 
이는 CPU가 Context Switching을 통해 여러개의 프로세스를 아주 짧은 시간 동안 번갈아가며 동시에 실행되는 것 처럼 보이게 하는 것이다.  (코어가 2개 이상이고 프로세스가 서로 다른 코어에서 실행된다면 실제로 동시 실행된다 할 수 있다.)
 
즉, 동일 코어 내에서 특정 시점에는 하나의 프로세스만 CPU를 할당받는다.

 
이렇게 CPU는 여러 작업을 조금씩 나눠서 실행해야 하기 때문에 Ready Queue라는 대기열을 만들고 프로세스를 넣어두고, 프로세스들을 우선순서를 두어서 실행시키게 된다. 
 
이때, 각 프로세스들에게 적절히 CPU를 할당하지 못하면 특정 프로세스는 다음 작업을 너무 오래 기다리는 등의 문제가 생길 것이다. 
 
이러한 문제를 해결하기 위해 Ready Queue에 있는 프로세스들 중 어떤 프로세스에게 다음 CPU를 할당할 것인지를 스케줄링 알고리즘을 통해 결정하는데, 이 역할을 수행하는 것이 CPU 스케줄러이다. 
 
CPU 스케줄러는 적절한 스케줄링 알고리즘을 사용해서 어떤 프로세스에게 CPU를 할당할 지 결정하고, Dispatcher가 실제 CPU를 할당하게 된다.
 
스케줄링 알고리즘은 CPU의 선점 방식에 따라 비선점(Nonpreemptive) 방식과 선점(preemptive) 방식으로 나뉘게 된다.
 
비선점 방식은 프로세스가 자발적으로 CPU 자원을 반납할 때까지 대기하다가 다른 프로세스에게 CPU 자원을 할당하는 방식이라면,
 
선점 방식은 할당에 대한 우선순위가 더 높은 프로세스가 ready queue에 들어온 경우, 자원을 강제로 뺏어서 새로운 프로세스에게 할당하는 방식이다. 

 

비선점형 방식

비선점형 알고리즘은 프로세스가 자발적으로 running 상태에서 terminated, waiting, ready 상태로 변경한 이후 다른 프로세스에게 CPU를 할당하는 방식이다.
 
CPU 자원을 강제로 뺏지 않고, 프로그램 레벨에서 서로 협력해야만 CPU를 번갈아 사용할 수 있기 때문에 신사적 또는 협력적인 스케줄링 방법이다. 
 
컨텍스트 스위칭으로 인한 부하가 적다는 장점이 있지만, 특정 프로세스가 너무 오래 CPU 자원을 가진다면 다른 프로세스는 오래 기다려야 한다는 단점이 있다. 
 
비선점형 방식의 알고리즘으로는 크게 FCFS, SJF, HRN 알고리즘이 있다. 

 

FCFS

FCFS (First Come, First Served) 알고리즘은 큐에 가장 먼저 저장된 프로세스를 먼저 처리하는 알고리즘이다. 
 
해당 알고리즘은 작업을 길게 수행되는 프로세스가 있는 경우 뒤에 기다리고 있는 프로세스가 준비 큐에서 오래 기다리는 현상(convoy effect)가 발생한다는 단점이 있다.

 

SJF

SJF (Shortest Job First) 알고리즘은 ready queue에서 CPU burst가 가장 짧은 프로세스부터 실행하는 알고리즘이다. 

<참고>
CPU burst : 프로세스가 CPU에서 한번에 연속적으로 실행되는 시간
I/O burst : 프로세스가 운영체제에 I/O 작업을 요청하고 대기하는 시간 
CPU bound process : CPU burst가 I/O burst보다 더 많은 프로세스 (ex) 동영상 편집 프로그램)
I/O bound process : I/O burst가 CPU burst보다 더 많은 프로세스 (ex) 백엔드 API 서버)

 
이 알고리즘은 실행 시간이 긴 프로세스가 실행되지 않는 기아현상(Starvation)이 발생할 수 있다.

Priority

우선순위 (Priority) 알고리즘은 SJF의 기아현상을 보완하기 위해 나온 알고리즘으로 오래된 작업일수록 우선순위를 높이는 방법을 적용한 알고리즘입니다. 
 
SJF가 단순히 실행 시간만 고려해서 CPU burst가 짧은 순서대로 CPU를 할당하는 알고리즘이라면, Priority은 실행 시간과 대기시간을 같이 고려해서 CPU를 할당하는 알고리즘입니다. 

 

선점형 방식

선점 방식은 스케줄러가 현재 실행중인 CPU의 프로세스에 개입해서, 다른 프로세스에게 CPU 자원을 할당 하는 방식이다.
 
ready queue에 알고리즘 별 우선순위가 더 높은 프로세스가 들어오면, CPU 자원을 해당 프로세스에게 할당하고 실행중이던 프로세스를 ready queue에 넣는다. 
 
스케줄러가 강제로 프로세스에 개입해서 CPU 자원을 할당하기 때문에 프로세스 간의 전환이 빠르다는 장점이 있지만, 프로세스 간 데이터 일관성 문제가 발생할 수 있다. 
 
선점형 방식의 알고리즘에는 크게 라운드 로빈, SRTF, MLQ(Multi Level Queue)가 있다.

 

라운드 로빈 

라운드 로빈 알고리즘은 현대 운영체제가 사용하고 있는 스케줄링 알고리즘으로, 프로세스에게 CPU의 최소 단위 시간인 타임 슬라이스 동안 CPU를 할당한다. 
 
그리고 타임 슬라이스가 지나면 강제로 다음 프로세스에게 CPU를 할당하고, 만약 프로세스가 작업을 완료되지 못했다면 준비 큐의 맨 마지막으로 대기하게끔 하는 알고리즘이다.

 
라운드 로빈 알고리즘는 타임슬라이스를 적절히 설정하는 것이 중요하다. 
 
만약 너무 짧은 시간을 설정한다면 컨텍스트 스위칭이 많이 발생하기 때문에 오버헤드가 커질 것이고, 그렇다고 너무 길게 설정하면 FCFS 알고리즘과 같이 뒤에 기다리고 있는 프로세스가 너무 오래 대기할 수 있다
 

SRTF

SRTF(Shortest-Remaining-Time-First) 알고리즘은 프로세스가 CPU를 할당받아 수행되는 중간에 CPU burst가 더 짧은 작업이 들어오는 경우, 수행중이던 프로세스를 중단하고 새로 들어온 프로세스를 수행하도록 하는 알고리즘으로 SJF에 preemtive가 적용 된 알고리즘이다.
 
SRTF는 라운드로빈 스케줄링을 기반으로 동작하는데, 다음 CPU를 할당받을 프로세스를 선택할 때 라운드 로빈은 순차적으로 할당하는 반면 SRTF는 가장 작업 시간이 짧은 프로세스를 선택한다는 차이가 있다.

 

Multi Level Queue

우선순위에 따라 여러개의 Ready Queue를 만들어서 각 Queue마다 라운드로빈, FCFS 등 독자적인 스케줄링 알고리즘을 사용해 우선순위를 부여하는 방식이다. 
 
기존의 작업시간과 대기시간만 고려하는 단순한 우선순위 할당 방법보다 프로세스 작업 자체의 우선순위를 고려하는 고도화된 스케줄링 기법이다.
 
이 알고리즘 또한 선점형 방식이기 때문에 실행중인 프로세스보다 우선순위가 높은 프로세스가 들어오면, 현재 실행중인 프로세스를 종료하고 해당 프로세스에게 CPU를 할당한다.
 

 

참고

• https://velog.io/@chappi/OS%EB%8A%94-%ED%95%A0%EA%BB%80%EB%8D%B0-%ED%95%B5%EC%8B%AC%EB%A7%8C-%ED%95%A9%EB%8B%88%EB%8B%A4.-6%ED%8E%B8-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%813-%EC%84%A0%EC%A0%90%ED%98%95-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Round-Robin-SRT-%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%EB%B0%A9%EC%8B%9D-Multilevel-Queue
• https://m.blog.naver.com/adamdoha/222023047160
• https://lotuus.tistory.com/92
• https://mikiplace.tistory.com/10 
• https://www.youtube.com/watch?v=LgEY4ghpTJI&list=PLcXyemr8ZeoT-_8yBc_p_lVwRRqUaN8ET&index=17