CPU를 효율적으로 사용하기 위한 스케줄링

스케줄링(Scheduling) 🔥

 

프로세스는 생성, 준비, 실행, 대기, 종료의 5가지 상태(5-State)를 바탕으로 실행됩니다. 그리고 프로세스는 각 상태를 프로세스 자신이 바꾸는 것이 아닌, CPU 스케줄러라는 것에 의해서 관리되고 전환됩니다. 이렇게 스케줄러가 프로세스에 CPU를 할당하는 작업을 스케줄링이라 하며, 프로세스의 현재 상황을 보면서 CPU를 어떻게 할당해야 시스템 자원을 효율적으로 사용할 수 있을지 결정합니다.

프로세스를 잘 골라서 효율적으로 운영해야 하는 스케줄러

스케줄링은 프로세스 관리 범주에 따라 다음과 같이 나뉩니다.

• 고수준: 시스템 자원을 할당받기 위한 프로세스의 수를 결정하는 단계
• 중간수준: 시스템 상황에 따라 실행 중인 프로세스를 중지하거나 활성화하는 단계
• 저수준: 준비 중인 프로세스에게 CPU를 할당하거나, 할당된 프로세스를 대기 상태로 변경하는 단계

 

그리고 스케줄러는 다음의 목적들을 위해 존재합니다.

• 공평성: 모든 프로세스는 공평하게 CPU를 할당받아 실행되어야 한다.
• 효율성: 시스템 자원을 유휴시간 없이 효율적으로 사용할 수 있어야 한다.
• 안정성: 시스템 자원을 독점하거나 파괴하는 프로세스를 방지해야 한다.
• 확장성: 프로세스가 증가하더라도 기존과 동일하게 동작할 수 있어야 한다.

 

특정 목적을 좀 더 확실하게  달성하기 위해 다른 목적을 어느 정도 희생하는 경우도 있습니다 👏

 

 

 

스케줄링 알고리즘 ⏰

 

스케줄링 알고리즘은 선점형(Preemptive)과 비선점형(Non-preemptive) 방식으로 나뉩니다. 비선점형은 어떤 프로세스가 CPU를 할당 받아 작업을 진행 중이면, 중간에 뺏을 수 없는 방식을 말합니다. 이 방식은 일괄 처리 방식에 어울리며, 컨텍스트 스위칭이 잦게 일어나지는 않지만, 기다리는 프로세스가 많기에 작업 처리율이 떨어집니다. 반대로 선점형은 실행되고 있는 프로세스가 언제든지 중간에 다른 프로세스에게 CPU 할당을 넘겨줄 수 있는 방식입니다. 이 방식은 시분할 처리 방식에 어울리며, 프로세스를 돌아가면서 사용하기 때문에, 처리율은 높아집니다. 하지만 잦은 컨텍스트 스위칭이 발생하기 때문에, 이로 인한 오버헤드가 많다는 단점이 있습니다.

 

각 방식의 알고리즘은 장단점이 존재하는데, 그렇다면 효율성은 어떻게 체크할 수 있을까요? 🤔

 

일반적으로 CPU 사용률, 처리량, 대기 시간, 응답 시간, 반환 시간을 평가 지표로 고려할 수 있습니다. 하지만 CPU 사용률과 처리량은 계산하기 어렵기 때문에, 보통 나머지 지표를 바탕으로 평균 대기 시간을 구해 효율성을 평가합니다. 각 시간 지표간의 관계를 그림으로 표현해보면 다음과 같습니다.

실행 시간이라는 것이 추가되었는데, 각 지표들의 의미는 다음과 같습니다.

• 대기 시간: 프로세스가 생성된 후 실행되기 전까지 대기하는 시간
• 응답 시간: 첫 작업을 시작한 후 결과를 반환하기까지 걸린 시간
• 실행 시간: CPU를 할당받아 시작되고, 종료하기까지 걸린 시간
• 반환 시간: 대기 시간을 포함하여, 실행이 종료되기까지 걸린 시간

 

평균 대기 시간은 각 프로세스의 대기 시간을 더한 후, 그 수로 나누면 됩니다.

 

 

 

비선점형 알고리즘

 

FCFS 스케줄링

FCFS(First Come First Served) 스케줄링은 프로세스가 생성되어 대기하고 있는 준비 큐에 도착한 순서대로 CPU를 할당하는 방식으로 선입선출 스케줄링이라고도 합니다. 이 알고리즘은 준비 큐를 하나만 가지고 동작하고, 비선점형 방식이기에 실행 중인 프로세스가 끝나야 다음 프로세스가 실행됩니다. 모든 프로세스가 공평하게 CPU를 할당 받지만, 뒤에 대기 중인 프로세스를 실행하기까지 오래걸려 효율적이지 않습니다.

 

SJF 스케줄링

SJF(Shortest Job First) 스케줄링 역시 하나의 준비 큐를 가지고 동작합니다. 준비 큐에 있는 프로세스 중 가장 짧은 실행 시간을 가진 프로세스부터 CPU를 할당하는 알고리즘으로 구현되어 있습니다. FCFS 스케줄링에 비해 평균 대기 시간이 적어, 시스템의 효율성이 좋아지지만, 할당 받는 프로세스를 예측하기 힘들고, 공평하지 못합니다. 준비 큐에는 먼저 들어왔지만 실행 시간이 길다는 이유로, 그 프로세스는 실행이 무한하게 지연될 수 있습니다. 그렇기 때문에 이 스케줄링 방식은 잘 사용되지 않습니다.

 

HRN 스케줄링

HRN(Highest Reponse Ratio Next) 스케줄링은 SJF 스케줄링의 단점을 극복하기 위해 우선순위를 바탕으로 CPU를 할당합니다. 우선순위를 구하는 방식은 (대기시간 + CPU 사용시간) / CPU 사용시간으로 구할 수 있으며, 높은 값이 높은 우선순위를 뜻합니다. 실행 시간이 짧은 프로세스에게 높은 우선순위를 주면서도, 대기 시간까지 고려하기 때문에 좋아 보이지만, 여전히 공평성이 떨어집니다.

 

 

선점형 알고리즘

 

라운드 로빈 스케줄링

라운드 로빈(Round Robin) 스케줄링은 준비 큐에 들어온 프로세스에게 순서대로 CPU를 할당하지만, 타임 슬라이스(Time Slice)라는 것을 추가로 제공하여 정해진 시간동안만 실행될 수 있도록 합니다. 만약 정해진 시간 내에 작업을 마무리하지 못했다면, 해당 프로세스는 준비 큐의 마지막으로 이동되고, 모든 프로세스들이 작업을 완료할 때까지 이 작업은 반복됩니다. 가장 단순한 선점형 스케줄링 알고리즘이면서  공평하지만, 프로세스가 실행 상태로 넘어갈 때는 컨텍스트 스위칭까지 일어나기 때문에 이도 고려해야 합니다. 그렇기 때문에 적절한 타임 슬라이스 값(크기)을 설정하는 것이 중요합니다.

 

다단계 큐 스케줄링

다단계 큐(Multilevel Queue) 스케줄링은 우선순위에 따라 준비 큐를 여러 개 사용하는 방식이며, 프로세스는 운영체제로부터 우선순위를 부여 받아 준비된 큐에 배정됩니다. 준비 큐는 우선순위 단계별(1순위 준비 큐, 2순위 준비 큐, ...)로 준비되어 있으며, 각 준비 큐는 라운드 로빈 방식에 의해 돌아갑니다. 이 방식은 우선순위가 높은 준비 큐의 처리가 먼저 끝나야만, 후순위 준비 큐를 처리하기 때문에 우선순위가 낮은 프로세스는 실행이 연기된다는 단점이 있습니다.

 

다단계 피드백 큐 스케줄링

다단계 피드백 큐(Multilevel Feedback Queue)는 다단계 큐의 단점을 보완하기 위해 만들어진 알고리즘이며, 우선순위가 높은 준비 큐의 프로세스들이 먼저 라운드 로빈 방식으로 동작하는 것은 동일합니다. 하지만 타임 슬라이스 내에 작업을 끝내지 못한 프로세스를 한 단계 후순위 준비 큐의 맨 마지막으로 옮긴다는 차이가 있고, 각 준비 큐는 타임 슬라이스가 다르다는 점이 있습니다.

 

물론 정말 우선적으로 처리되어야 하는 커널 프로세스가 일반 프로세스의 준비 큐로 들어가지는 않습니다.

 

오늘날의 운영체제는 다단계 피드백 큐 스케줄링 알고리즘에 의해 프로세스를 관리합니다.