[ 운영체제 ] 11. Scheduling Algorithms

https://min-h-study-review.tistory.com/247

 

CPU Scheduling Algorithms은 크게 6가지가 있다.

 

◼ First-come, first-served (FCFS) scheduling
◼ Shortest-job-first (SJF) scheduling

◼ Round-robin scheduling
◼ Priority scheduling
◼ Multilevel queue scheduling

◼ Multiple feedback-queue scheduling

하나씩 분석해보자

 

First-Come, First-Served Scheduling
선입 선출식

특징)

- CPU 요청이 들어오는 순서대로 할당이 이루어진다.

- 가장 간단함

- 비선점형 = Interrupt가 없다.

 

 

단점)

- Average Waiting Time이 꽤 길어질수도 있다.

  ex) 먼저 온 프로세스가 엄청 오래 쓸 때

 

공리주의 적으론 별로다.

 

 

---

---

Shortest-Job-First Scheduling
오래 안 쓰는 Process 먼저

특징)

- CPU Burst Time이 가장 짧은 순서대로 할당이 이루어진다.

- 가장 Optimal하다.

- Interrupt가 있을 수도 , 없을 수도 있다.

 

단점)

- CPU Burst Time이 어떻게 될지 예측할 수가 없다.

 

 

 

그래도 예상하는 법은 있다고 함.

 

 

 

예전 값들을 기반으로 CPU Burst Time을 예상함.

 

예시▼

 

 

---

근데 만약에 BurstTime이 각각 다른 Process들이 다른 시간에 들어왔다면?

▶ Interrupt가 일어난다.

 

 

● [ 0 ~ 1 ] 

P1 밖에 없어서 얘 혼자 실행함

 

 

● [ 1~5 ] 

현재 도착한 프로세스 : P1 (8-1) , P2 (4)

P2가 Burst Time이 짧으니까 먼저 실행.

 

2초와 3초에 P3,P4가 오지만 P2의 우선순위가 더 높다.

 

 

● [ P2가 끝난 뒤 ~  ]

현재 도착한 프로세스 : P1 (7) , P3 (9) , P4 (5) 

Burst Time은 P4가 가장 적으므로, P4 실행

 

... P1 > P3 순서로 실행

 

 

요약 :
단점)

- CPU Burst Time이 어떻게 될지 예측할 수가 없다.

 

 

---

---

Round-Robin Scheduling
선입 선출 + Time Quantum(Interrupt)

특징)

- CPU 를 쓸 수 있는 시간이 Time Quantum으로 정해져있다.

- Time Quantum이 지나면 Interrupt 발생 .

- Ready Queue는 Circular queue로 되어있다.

 

 

한계점)

- Perfromanc가 Time Quantum에 지나치게 의존적이다.

- Context Switching 에 대한 overhead도 생각해야함.

 

 

 

Quantum = 4

먼저 왔다해도, 최대 4초만 쓰고 나갈 수 있음.

 

P1이 먼저 4초간 실행되고, 그 뒤에 P2가 들어온다.

 

= Turnaround time (소요 시간) Time Quantum이랑은 아무 연관이 없다는 뜻

 

 

 

---

---

Priority Scheduling
중요도에 따른 스케쥴링

특징)

- 중요도는 내부적으로도, 외부적으로도 정해질 수 있다.

- 선점이 될 수도, 비선점이 될 수도 있다.

   ▶ 선점이 되는 경우
       1) 우선순위가 같을 때 - Round Robin 적용.

       2) 실행되고 있는 중에 우선순위가 높은 Process가 들어왔을 때 - 그 Process로 Switch

 

문제점)

- Indefinite Blocking ( = Starvation ) : 중요도가 낮은 process는 계속 실행 안 될 수도 있음

 ▶ Aging 적용 : 기다리는 시간이 길수록 중요도를 올린다.  

 

 

 

 

[ P2,P3 ] , [ P1, P5 ] 의 우선순위가 같다.

이럴 땐 같은 우선순위끼리는 Round-Robin을 적용한다.

 

 

---

---

Multilevel Queue Scheduling

특징)

-  Process들을 각각 다른 그룹의 queue으로 나누고, 각 queue마다 Scheduling 알고리즘으로 나눈 것

 = Ready queue 여러 개가 있고 , 각각의 queue마다 Priority 가 정해져있다.

 

 

 

 

한계)

이러다 보면 밑에 있는 queue는 실행을 못할 수도 있다. 

 

 

 

---

---

Multilevel Feedback-Queue Scheduling

특징)

Multilevel Queue Scheduling + Queue 사이에 Process 이동 가능

 

 

Aging을 시키듯이.

 

Priority가 높은 Queue에서만 계속 실행될 수가 있음.

또한 거기에 있는 프로세스들이 

그럼 그 이외 Queue에 있는 Process 들은 실행되지 않고 계속 기다릴 것이다.

 

이를 해결하고자 다음과 같은 구조의 Scheduling을 한다.

 

Quantum 8일 때 실행 다 못하면

▶ Quantum 16인 queue로 보냄.

▶ 다 실행 못하면 FCFS queue로 보냄

 

= 프로세스들이 CPU 쓰는 시간을 내려갈수록 점점 더 많이 가질 수 있도록 한다.

   ( 일찍 끝나는 애들은 윗쪽에서 다 끝남 ) 

 

 

 

(출처)

한동대학교 고윤민교수님 - 운영체제