[OS] 프로세스 스케줄러(Process Scheduler) 알고리즘 정리

 

1. 프로세스, 스케줄러란? 

 

프로세스란 실행 중인 프로그램으로 작업, 태스크, 잡이라는 말과 혼용이 된다. 폰 노이만 구조에 따라, 모든 프로그램의 코드는 먼저 메모리에 들어간 후 실행이 되어야 하고, CPU가 프로세스를 실행해 준다. 프로그램을 짤 때, 매끄러운 사용자 경험을 전달하기 위해서는 프로세스 실행에 필요한 자원들을 효율적으로 다루어야 하는데, 그걸 도와주는 게 바로 스케줄러(scheduler)다. 스케줄링이란, 프로세스를 어느 순서대로 실행할지 판단하는 일종의 계획이다. 프로그램이 실행되면 코드는 메모리에 들어가고, CPU에서 코드를 한 줄씩 읽으면서 프로세스를 실행하는데, CPU 자원은 한정되어 있고, 사람들은 여러 프로그램을 동시에 이용하길 원한다. 여러 프로세스 실행을 관리하기 위해 어떤 알고리즘을 사용해볼 수 있을지 정리해보았다. 

 

2. 시분할 시스템의 등장

 

옛날옛적 1960년, 1970년에 운영체제가 다양화되고 복잡해지기 이전에는 컴퓨터로 연산을 한 개 돌릴 때, 다른 프로그램을 실행시킬 수가 없었다. 상사가 프로그램을 돌리면 부하직원은 그 프로그램이 끝날 때까지 하염없이 야근을 해야 하는 셈이다. 이런 상황에서 한 프로그램이 끝나면 다음 프로그램을 자동으로 실행시켜 주는 '배치 처리 시스템'이 등장했으나, 문자 입력 1개에 대한 응답을 받기 위해 기존에 실행되고 있던 프로그램에서 파일 입출력을 하는 12시간이 지나길 기다려야 하는 문제는 개선될 수 없었다. 이를 개선하기 위해 '시분할'이라는 개념이 등장했다. 프로세스 a를 실행하다가 스케줄러가 일정 시간마다 분할하여 적당한 시기에 프로세스 b를 실행하도록 하여, 프로세스 a의 실행이 중단하는 시기에 프로세스 b를 실행하도록 하는 것이다. 시분할 시스템의 장점을 정리하면 다음과 같다. 

 

1. 프로세스 응답 시간 축소
2. CPU 활용도 높임
3. 사용자 경험 향상
...

 

그렇다면 프로세서 스케줄러가 채택할 수 있는 알고리즘이 어떤 것이 있는지 알아보자.

 

3. 가능한 스케줄러 알고리즘들

3-1. FIFO(First In First Out)

 

FIFO 방식 스케줄링

 

가장 간단한 형태의 스케줄러다. 전형적인 First come, first serve 형태고 기존의 배치 처리 시스템과 유사한 방식이다. 프로세스가 실행되는 순서대로 뽑혀서 CPU가 실행을 하는 것이다. 이 방식만 가지고는 쓸모없는 딜레이를 해결하지 못하나, 기본적으로 큐 자료구조를 따르기에 다른 방식과 결합하면 그럴듯한 스케줄러 알고리즘을 구성할 수 있다. 

 

3-2. 최단 작업 우선 (Short Job First)

 

SJF 방식 스케줄링

 

프로세스 실행시간이 짧은 것부터 실행하는 것이다. 이 방식은 현실적으로 모든 프로그램의 실행시간을 예측할 수 없기에 쉽지 않고, 이상적인 상황을 가정했을 때나 가능하다. 시간이 적게 걸리는 프로세스를 우선적으로 처리하기 때문에 쓸모없이 시간이 딜레이 되는 문제는 줄일 수 있지만, 각각의 실행시간을 알아야 하기 때문에 한계점은 있다.

 

3-3. 우선순위 기반 (Priority-based)

 

우선순위기반 스케줄링

 

프로세스별로 우선순위를 매겨, 높은 것부터 실행시키는 것이다. 여기에는 정적 우선순위와 동적 우선순위가 포함된다. 정적 우선순위를 채택할 경우, 회사 컴퓨터에서 카카오톡 프로세스는 우선순위를 낮게 설정하고, vscode의 우선순위는 높게 설정하는 예시를 들을 수 있겠다. 즉 프로세스마다 우선순위를 미리 지정해야 하는 것이다. 동적 우선순위의 경우, 상황에 따라 우선순위를 동적으로 변경하는 것이다. 

 

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

 

 

시분할을 가정하는 방식으로, 큐에 들어가는 프로세스들을 시간마다 무조건 다음 것으로 바꿔치기하고, 바꿔치기 당한 프로세스는 잠시 멈춘 상태로 큐의 마지막에 추가되는 방식이다. 매 시간마다 빙글빙글 도는 모양으로 표현할 수 있어 라운드 로빈이라고 부른다.

 

이와 같이 CPU의 활용률을 100%가 되도록 지향하는 이유는 초기 운영체제에서는 한 프로세스가 다른 프로세스의 실행이 끝날 때까지 아무것도 할 수 없었기 때문이다. 위에서 알아본 몇 가지의 스케줄러 알고리즘은 기본 중의 기본이며 최신 알고리즘은 훨씬 복잡하다. 다음 글에서는 프로세스 상태가 무엇인지 스케줄링이 될 때 어떤 상태가 되는지 정리해보려 한다.