CPU 스케줄링 알고리즘

CPU 스케줄링 알고리즘이란?

---

CPU core가 하나라면 한 번에 하나의 프로세스만 실행 가능합니다. 이 때 필요한 것이 CPU 스케줄링입니다.

즉, CPU 스케줄링은 언제 어떤 프로세스에 CPU를 할당할지 결정하는 작업입니다. 이 알고리즘은 CPU 이용률은 높게, 주어진 시간에 많은 일을 하게, 준비 큐에 있는 프로세스는 적게, 응답시간은 짧게 설정하는 것을 목표로 합니다.

• Windows: chrome.exe 와 같은 형태의 실행 가능한 파일
• macOS: chrome.app 와 같은 형태의 실행 가능한 디렉토리 (실행 파일, 애플리케이션의 리소스 포함)

면접 예상 질문

---

1. CPU 스케줄러는 언제 스케줄링을 결정하나요?

1) 실행(running) 상태에서 대기(waiting) 상태로 전환(switching)될 때

2) 실행(running) 상태에서 준비(ready) 상태로 전환(switching)될 때 

3) 대기(waiting) 상태에서 준비(ready) 상태로 전환(switching)될 때

4) 종료(Terminated)될 때

-> 1번과 4번 상황에서만 스케줄링이 발생하는 것을 비선점형(non-preemptive) 스케줄링이라고 합니다.
이외의 모든 스케줄링은 선점형(preemptive) 스케줄링이라고 합니다.

2. 비선점형 방식은 무엇이며, 어떤 것이 있나요?

어떤 프로세스가 CPU를 점유하고 있다면 이를 뺏을 수 없는 방식 (스스로 CPU 소유권을 포기하는 방식) 입니다. 강제로 프로세스를 중지하지 않습니다. 따라서 문맥 교환(Context Switching)으로 인한 부하가 상대적으로 적지만 프로세스의 배치에 따라 효율성 차이가 많이 나게 됩니다.

비선점형 스케줄링의 종류

---

FCFS
가장 먼저 온 것을 가장 먼저 처리하는 알고리즘입니다.

단점: 길게 수행되는 프로세스 때문에 '준비 큐에서 오래 기다리는 현상'이 발생하는 단점이 있습니다.

SJF
실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘입니다.
긴 시간을 가진 프로세스가 실행되지 않는 현상이 일어나며 평균 대기 시간이 가장 짧습니다.

단점: 하지만 실제로는 실행 시간을 알 수 없기 때문에 과거의 실행했던 시간을 토대로 추측해서 사용합니다.

우선순위
오래된 작업일수록 '우선순위를 높이는 방법(aging)'을 통해 'SJF'의 단점을 보완한 알고리즘입니다.

우선순위 스케줄링의 특징

• 자발적 양보
• 우선순위 부여
• 우선순위 인버전
  ex) 실시간 시스템이나 중요한 작업이 우선적으로 처리되어야 하는 상황

3. 선점형 방식은 무엇이며, 어떤 것이 있나요?

현대 운영체제가 사용하고 있는 방식으로, 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 이를 강제로 중단시키고 다른 프로세스에 CPU를 할당하는 방식입니다.

처리 시간이 매우 긴 프로세스의 CPU 사용 독점을 막을 수 있어 효율적인 운영이 가능하지만 잦은 컨텍스트 스위칭으로 인해 오버헤드(Overhead)가 커질 수 있습니다.

선점형 스케줄링의 종류

---

라운드 로빈 (RR, Round Robin)

현대 컴퓨터가 쓰는 스케줄링인 우선순위 스케줄링의 일종으로 각 프로세스는 동일한 할당 시간을 부여해서 해당 시간동안안 CPU를 이용합니다. 그 시간 안에 끝나지 않으면 강제 중단 후 다시 준비 큐(ready queue)의 뒤로 가는 알고리즘입니다.

SRF

'SJF'는 중간에 실행 시간이 더 짧은 작업이 들어와도 기존 짧은 작업을 모두 수행하고 그 다음 짧은 작업을 이어나가는데, SRF(Shortest Remaining Time First)는 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행하는 알고리즘입니다.

다단계 큐
다단계 큐는 우선순위에 따른 준비 큐를 여러 개 사용하고, 큐마다 라운드 로빈이나 FCFS 등 다른 스케줄링 알고리즘을 적용한 것을 말합니다.
큐 간의 프로세스 이동이 안되므로 스케줄링 부담이 적지만 유연성이 떨어지는 특징이 있습니다.

다단계 큐의 특징

• 우선순위 관리
• 다양한 스케줄링 정책 사용
• 자원 공정 분배
• 사용자와 시스템 프로세스 분리
  ex) 실시간 시스템에서 중요한 작업이 우선적으로 처리되어야 할 때