[운영체제] CPU 스케줄링 알고리즘

1. CPU 스케줄러

CPU 스케줄러는 운영체제의 핵심 구성 요소 중 하나로, 어떤 프로세스에게 CPU를 할당할지 결정하는 역할을 합니다. 다양한 스케줄링 알고리즘을 사용해 프로세스가 실행될 준비가 되었을 때 어떤 프로세스가 CPU를 사용할지 결정합니다.

2. CPU 스케줄러 알고리즘

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

크게 선점형 알고리즘과 비선점형 알고리즘을 나눌 수 있습니다.

 

2-1. 비선점형 알고리즘

현재 실행 중인 프로세스가 종료되거나 스스로 CPU를 반납할 때까지 다른 프로세스는 CPU를 사용할 수 없는 방식입니다. FCFS, SJF, 우선순위가 있습니다.

 

FCSF(First Come, First Served)

프로세스가 도착한 순서대로 CPU를 할당하는 방식입니다.

 

SJF(Shortest Job First)

실행 시간이 가장 짧은 프로세스에게 CPU를 먼저 할당하는 방식입니다.

 

우선순위 스케줄링(Priority Scheduling)

프로세스에 우선순위를 부여하고 우선순위가 높은 프로세스에게 먼저 CPU를 할당하는 방식입니다.

2-2. 선점형 알고리즘

현재 실행 중인 프로세스를 중단하고 다른 프로세스에게 CPU를 할당하는 방식입니다. 라운드로빈, SRF, 다단계 큐가 있습니다.

 

라운드로빈(Round Robin)

각각의 프로세스에게 동일한 시간동안 CPU를 할당하는 방식입니다. 할당 시간 내에 처리를 완료하지 못하면 강제 중단 후 다음 작업으로 넘어갑니다. 처리하지 못한 프로세스는 준비 큐(ready queue)의 뒤로 가게 됩니다.

준비 큐(ready queue)란? 운영체제 내에서 CPU를 할당받을 준비가 완료된 프로세스들이 대기하는 큐(queue) 자료구조입니다.

 

 

SRFT(Shortest Remaining Time First)

남은 실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당합니다. 만약 중간에 더 짧은 작업 작업이 들어오면 수행하던 프로세스는 중지하고 해당 프로세스를 수행합니다.

 

다단계 큐(Multilevel Queue Scheduling)

여러 개의 큐를 사용하여 프로세스를 관리합니다. 우선순위에 따른 준비 큐를 여러 개 사용하고 큐마다 라운드 로빈이나 FCFS 등 다른 스케줄링 알고리즘을 적용하는 것을 말합니다.