[CS지식] CPU 스케줄링 알고리즘

[면접을 위한 CS 전공지식 노트] 도서를 읽고 정리한 글 입니다.
티스토리에 정리했던 내용을 벨로그로 옮겼어요!
https://kkomyoung.tistory.com/6

CPU 스케줄링

언제 어떤 프로세스에게 먼저 CPU의 사용권을 줄 것 인지를 결정하는 작업이다.

CPU 스케줄링 알고리즘을 어떻게 짰는지에 따라 CPU의 자원을 얼마나 효율적으로 사용하게 되는지가 결정된다.

CPU 스케줄링 알고리즘 분류 기준
"OS가 강제적으로 CPU 사용을 중단시키는가?"

NO : 비선점형 방식
YES : 선점형 방식

1.  비선점형 방식

프로세스가 스스로 CPU 소유권을 포기하는 방식이다.

OS가 강제로 프로세스를 중단시키지 않기 때문에, *컨텍스트 스위칭으로 인한 부하가 적다.

* 컨텍스트 스위칭(Context Switching) :
어떤 프로그램의 실현을 중단하고 다른 프로그램의 실행을 재개할 때, 그 프로그램의 재개에 필요한 환경을 다시 설정하는 것.

FCFS

FCFS (Fisrt Come, First Served)

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

• *기아 현상이 발생하지 않는다.
• 길게 수행되는 프로세스가 있으면 짧게 수행될 프로세스들이 준비큐에서 오래 기다리는 현상이 발생한다.

* 기아현상(starvation) : 프로세스가 자원을 할당받지 못하는 상태

SJF

SJF (Shortes Job First)

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

• 평균 대기 시간이 가장 짧다.
• 기아 현상 발생 : 우선순위가 낮은 프로세스는 자원을 할당받지 못하게 된다.
• 실제로는 실행 시간을 예측하기 어려워 실용적이지 못하다.

우선순위

우선순위가 가장 높은 프로세스에 자원을 할당하는 방식이다.

SJF 스케줄링의 단점을 보완한 알고리즘이다.

준비큐에 프로세스가 도착한다
-> 도착한 프로세스의 우선순위 vs 현재 실행중인 프로세스의 우선순위
-> 둘 중 우선순위가 높은 프로세스를 실행한다.

2.  선점형 방식

지금 사용하고 있는 프로세스를 강제로 중단시키고 다른 프로세스에게 CPU 소유권을 할당하는 방식이다.

현대 운영체제가 쓰는 방식이다.

라운드 로빈

RR (Round Robin)

우선순위 스케줄링의 일종이다.

각 프로세스에 동일한 할당 시간을 주고 그 시간 안에 끝나지 않으면 다시 준비 큐의 뒤로 가는 알고리즘 이다.

• 전체 작업 시간은 길어지지만 평균 응답 시간은 짧아진다.
• 할당 시간이 너무 크면 FCFS가 되고, 짧으면 컨텍스트 스위칭이 잦아져 비용이 커진다.

SRF

SRF (Shortest Remaining Time First)

중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행하는 알고리즘이다.

SJF와의 차이점:
SJF는 중간에 실행 시간이 더 짧은 작업이 들어와도 기존의 작업을 수행한 뒤에 그 다음 작업을 이어나간다.

다단계 큐

우선순위에 따른 준비 큐를 여러 개 사용하는 알고리즘이다.

큐마다 라운드 로빈이나 FCFS 등 다른 스케줄링 알고리즘을 적용한다.

• 큐 간의 프로세스 이동이 불가능하기 때문에 유연성이 떨어진다.