CPU 스케줄링

Minji·2022년 9월 11일

기술면접

목록 보기

4/11

CPU 스케줄링은 무엇이고 알고리즘 종류에 대해 설명하시오.

CPU 스케줄러는 CPU스케줄링 알고리즘에 따라서 프로세스에서 해야 하는 일을 스레드 단위로 CPU에 할당한다.

CPU 스케줄링

최고의 성능을 내기 위해서 자원을 어떤 프로세스에 얼마나 할당하는지 정책을 만드는 것
CPU 스케줄링 알고리즘의 목표는 CPU이용률은 높게, 주어진 시간에 많은 일을 하게, 준비 큐(ready queue)에 있는 프로세스는 적게, 응답 시간은 짧게 설정하는 것을 목표로 한다.

CPU 스케줄링 알고리즘

비선점형
- FCFS
- SJF
- 우선순위
선점형
- 라운드로빈
- SRF
- 다단계 큐

📌 비선점형(Non-preemmptive)

프로세스가 스스로 CPU 소유권을 포기하는 방식
강제로 프로세스를 중지하지 않는다.
컨텍스트 스위칭으로 인한 부하가 적다. (컨텍스트 스위칭 : PCB(Process Control Block)를 교환하는 과정인데 프로세스에 할당된 시간이 끝나거나 인터럽트에 의해 발생)

1. FCFS (First Come, First Served)

가장 먼저 온 것을 가장 먼저 처리하는 알고리즘
수행시간이 긴 프로세스는 준비큐에서 오래 기다릴 수도 있다는 문제점이 있습니다. 이 현상을 convoy effect라고 합니다.

2. SJF(Shortest Job First)

실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘
긴 시간을 가진 프로세스가 실행되지 않는 현상(starvation)이 발생하고 평균 대기 시간이 가장 짧습니다.
실제로는 실행 시간을 알기 어렵기 때문에 과거의 실행 시간을 토대로 추측해서 사용합니다.

3. 우선순위

오래된 작업일수록 우선순위를 높이는(aging)방법 을 통해서 SJF가 긴 실행 시간을 가진 프로세스가 실행되지 않는다는 단점을 보완한 알고리즘

📌 선점형(Preemptive)

현대 OS가 쓰는 방식
지금 사용하고 있는 프로세스를 알고리즘에 의해 중단시키고 강제로 다른 프로세스에 CPU소유권을 할당하는 방법
(즉, CPU가 어떤 프로세스에 의해 점유 중일 떄, 우선 순위가 높은 프로세스가 CPU를 차지할 수 있다.)
우선 순위가 높은 프로세스를 빠르게 처리해야할 경우에 유용하다.
선점이 일어날 경우, 오버헤드가 발생하며 처리시간을 예측하기 힘들다.

1. RR(RoundRobin)

우선순위 스케줄링의 일종
각 프로세스는 동일한 할당 시간을 주고 그 시간 안에 끝나지 않으면 다시 준비 큐의 뒤로 가는 알고리즘
할당 시간이 너무 클 경우 : FCFS알고리즘 처럼 작동한다.
할당 시간이 너무 짧을 경우 : 컨텍스트 스위칭이 잦아져서 오버헤드(비용이)가 커진다.