[운영체제] - 29강. CPU 스케줄링 알고리즘

이 글은 한빛미디어 '혼자 공부하는 컴퓨터 구조 + 운영체제'를 공부하고 정리한 내용입니다.

---

CPU 스케줄링 알고리즘에는 무엇이 있는가?

---

※ 스케줄링 알고리즘은 종류가 매우 다양하며 운영체제마다 사용하는 알고리즘도 제각각 다르다.
그중 책에선 7가지만 다룬다.

 

● 선입 선처리 스케줄링 (FCFS 스케줄링 : First Come First Served Scheduling)

- 준비 큐에 삽입된 순서대로 프로세스를 처리하는 비선점형 스케줄링 방식

- 가끔 프로세스들이 기다리는 시간이 길어질 수 있다는 단점이 있다.

 

ex) CPU 이용시간이 17ms인  프로세스 A, 5ms 프로세스 B, 2ms 프로세스 C가 있고, A->B->C의 순서대로 준비 큐에 들어갔다고 했을 때 프로세스 C는 2ms를 이용하기 위해 22ms(17+5)를 기다리는 상황이 발생. 이를 호위 효과(Convoy Effect)라고 한다.

선입 선처리 스케줄링 예시

---

 

● 최단 작업 우선 스케줄링 (SJF 스케줄링 : Shortest Job First Scheduling)

- 준비 큐에 삽입된 프로세스들 중 CPU 이용 시간 길이가 가장 짧은 프로세스부터 실행하는 비선점 스케줄링 방식.

- 기본적 분류를 비선점형 스케줄링 알고리즘이지만 선점형으로도 구현할 수 있는데 이를 구현한 것이 최소 잔여 시간 우선 스케줄링이다.

최단 작업 우선 스케줄링 예시

 

---

 

● 라운드 로빈 스케줄링 (Round Robin Scheduling)

- 선입 선처리 스케줄링에 타임 슬라이스라는 개념을 더한 선점형 스케줄링 방식

- 타임 슬라이스는 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미한다.

- 삽입된 순서대로 CPU를 이용하지만 정해진 시간이 있기에, 시간이 긴 프로세스는 작업을 완료하지 못하고, 문맥 교환 후큐의 맨 뒤로 이동하기 된다.

- 타임 슬라이스의 크기가 크다면 사용하는 의미가 없고, 작다면 빈번한 문맥교환이 일어나 오버헤드가 발생할 수 있다.

 

라운드 로빈 스케줄링 예

라운드 로빈 스케줄링 타임 슬라이스

---

 

● 최소 잔여 시간 우선 스케줄링 (SRT 스케줄링 : Shortest Remaining Time Schduling)

- 최단 작업 우선 스케줄링 알고리즘을 선점형으로 변경한 스케줄링 방식

- 최단 잔여시간을 우선적으로 처리하여, 준비 큐의 대기열을 빠르게 줄이고, 진행 중인 프로세스가 있어도, 잔여시간이 짧은 프로세스를 위해 sleep 시키고 짧은 프로세스를 먼저 할당한다.

- 선점형 SJF 스케줄링 이라고도 부른다.

 

SRT 스케줄링 준비 큐 상황

SRT 스케줄링 CPU 사용 상황

 

---

 

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

- 프로세스에 우선순위를 부여하고, 높은 우선순위의 프로세스부터 실행하는 선점형 스케줄링 방식

- SJF 스케쥴링(작업시간이 짧은 프로세스를 우선), SRT 스케줄링(남은 시간이 짧은 프로세스를 우선)은 넓은 의미로 우선순위 스케줄링의 일종이라고 볼 수 있다.

- 시간 제한, 메모리 요구량, 프로세스의 중요성, 자원 사용 비용 등에 따라 우선순위가 달라질 수 있다.

 

※ 우선순위 스케줄링은 기아(Starvation) 현상이라 하여, 우선순위가 낮은 프로세스가 높은 프로세스에 양보되며 실행이 계속 연기되는 상황이 발생하는데, 이를 해결하는 방법이 오랫동안 대기한 프로세스의 우선순위를 점차 높여주는 에이징(Aging) 기법이 있다.

 

---

 

● 다단계 큐 스케줄링 (MLQ 스케쥴링 : Multi Level Queue Scheduling)

- 우선순위 스케줄링의 발전된 형태로, 우선순위별로 준비 큐를 여러 개 사용하는 선점형 스케줄링 방식

- 우선순위가 높은 큐에서 대기중인 프로세스를 선처리하고 해당 큐가 비어있다면 다음 높은 큐의 프로세스를 처리한다.

- 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리해진다.

- 큐 별로 타임 슬라이스를 여러 개 지정할 수 있고, 큐마다 다른 스케줄링 알고리즘을 사용할 수도 있다.

 

다단계 큐 스케줄링

 

- 하지만 큐들 간의 프로세스 이동이 불가하기 때문에 스케줄링 부담이 적지만 유연성이 떨어지며, 우선순위가 낮은 프로세스가 오랫동안 CPU 할당을 기다리는 기아(Starvation) 현상이 발생할 수 있다.

 

---

 

● 다단계 피드백 큐 스케줄링 (MFQ 스케줄링 : Multi Level Feedback Queue Scheduling)

- 다단계 큐의 발전된 형태로, 프로세스들이 큐 사이를 이동하여 기아 현상을 보완한 선점형 스케줄링 방식.

- 오래 기다린 프로세스의 순위를 올리는 에이징 기법을 적용하여 순위가 오른 프로세스는 다시 해당 큐의 맨 뒤에서 대기한다.

- 어떤 프로세스의 CPU 이용 시간이 길면 낮은 우선순위 큐로 이동하고, 오래 기다린다면 높은 우선순위 큐로 이동한다.

 

다단계 피드백 큐 스케줄링

 

---

※ 참고자료

https://cocoon1787.tistory.com/123

[운영체제 OS] 스케줄링 알고리즘 - FCFS, RR, SJF, SRT, Priority, MLQ, MFQ 스케줄링

 

https://cocoon1787.tistory.com/124

[운영체제 OS] 다단계 큐 스케줄링(MLQ), 다단계 피드백 큐 스케줄링(MFQ)

 

https://reakwon.tistory.com/132

[운영체제] 스케줄링(Scheduling) 알고리즘(FIFO, SJF, 우선순위, Round-robin)

 

https://jwprogramming.tistory.com/17

Round-Robin(RR)이란? , CPU-Scheduling들