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

 

 

 

CPU 스케줄러는 프로세스에서 해야할 일을 스레드 단위로 CPU에 할당한다.

이 때 할당하는 규칙을 CPU 스케쥴링 알고리즘이라고 한다.

 

cpu 스케쥴링 알고리즘의 목표 : 

cpu 이용률은 높게 (주어진 시간에 많은 일을 하도록), 프로세스의 응답시간은 짧게 설정하는 것

 

 

 

CPU 스케쥴링 알고리즘은 우선 비선점형,선점형로 나눌 수 있다.

---

비선점형 non-preemptive

프로세스가 한번 cpu를 점유하면 끝날 때까지 나가지 않는다.

(프로세스가 running 과 terminate만 겪는다)

따라서 *컨텍스트 스위칭으로 인한 부하가 적다.

* 컨텍스트 스위칭 : CPU에 실행할 프로세스를 교체하는 기술

교착 상태가 일어날 수 있다.

 

FCFS : First Come First Served

가장 먼저 온것을 가장 먼저 처리하는 단순한 알고리즘

실행시간이 긴 프로세스 때문에 convoy 현상이 일어날 수 있다.

*convoy 현상 : cpu 사용시간이 짧은 프로세스들이 사용시간이 긴 프로세스를 계속 기다리게 되는 현상

 

SJF : Short Job First

실행시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘

Starvation(긴 실행시간을 가진 프로세스가 계속해서 실행되지 않는 현상)이 일어난다.

평균대기시간은 짧은 편.

하지만 여기서 생각해봐야할 점은, 사실 프로세스의 실행시간은 미리 알 수 없고 과거의 실행했던 시간을 추측해서 사용하므로 정확히 가장 짧은 프로세스가 먼저 실행되는 것은 아닐 수 도 있다는 점이다

 

우선순위  : Priority Scheduling or HRN (highest response-ratio next)

Aging 기법을 통해 SJF의 단점을 보완한 알고리즘

*Aging 기법 : 오래된 작업일수록 우선순위를 높이는 방법

HRN는 우선순위 = (대기시간+실행시간) / 실행시간

 

---

선점형 preemptive

멀티태스킹,인터럽트 처리 등의 이유로 운영체제가 현재 점유중인 프로세스를 컨텍스트 스위칭으로 중단시켜버리고, 강제로 다른 프로세스에 CPU 소유권을 할당하는 방식.

 

라운드 로빈 : Round Robin

 

시분할 알고리즘,우선순위 알고리즘

할당시간동안 실행하고 그 시간동안 끝나지 않으면 다시 준비 큐의 맨 뒤로 가는 알고리즘

할당 시간이 너무 크면 FCFS이 되고

할당 시간이 너무 작으면 컨텍스트 스위칭 비용이 커진다.

 

일반적으로 전체 작업시간은 길어지지만, 평균 응답시간은 짧아진다.

로드밸런서에서 트래픽 분산 알고리즘으로 사용됨

SRF : Shortest Remaining Time First

시분할 알고리즘 중에서 하나

SJF와 비슷하게

남아있는 작업시간이 가장 작은 프로세스를 고르는 것.

 

 

 

 

추가로 공부해보면 좋을 블로그

https://velog.io/@wejaan/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-Context-Switching-Process-Control-Block#:~:text=%EC%BB%A8%ED%85%8D%EC%8A%A4%ED%8A%B8%20%EC%8A%A4%EC%9C%84%EC%B9%AD%EC%9D%80%20CPU%EC%97%90,SP%EB%A5%BC%20%ED%86%B5%ED%95%B4%20%EB%8F%99%EC%9E%91%ED%95%9C%EB%8B%A4.

[운영체제] Context Switch

 

참고 도서

면접을 위한 CS 전공지식노트