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

알고리즘 종류

7개 각 스케줄링의 [ 작동 방식 , 특징 및 장단점 ] 을 위주로 알아두면 된다.

 

1. 선입 선처리

2. 최단 작업 우선

3. 라운드 로빈

4. 최소 잔여 시간 우선

5. 우선순위

6. 다단계 큐

7. 다단계 피드백 큐 스케줄링

 

 

---

● 선입 선처리

- First Come , First Served 스케줄링

- 단순히 준비 큐에 삽입된 순서대로 처리

- 비선점 스케줄링 (앞에 먼저 온 애가 CPU 쓸 때 못 뺏어오니까

 

단점 : 프로세스들이 기다리는 시간이 매우 길어질 수 있다.= 효위 효과     // 공정하지만 효율성을 떨어진다.

A가 기다리는 시간 : 0

B가 기다리는 시간 : 17

C가 기다리는 시간 : 22

 

---

---

● 최단 작업 우선 

- Shortest Job First 

- 위에 생겼던 호위효과를 방지하기 위해 생겨난 스케줄링 방법 // 

  호위효과 :( 모든 프로세스들이 그 앞의 프로세스가 CPU(쓰려고 하는 자원)를 다 쓸 때까지 기다리는 것)

 

CPU 사용 시간이 가장 짧은 프로세스부터 처리하는 스케줄링 방식

주로 비선점형으로 구현된다. 

C가 기다리는 시간 : 0 

B가 기다리는 시간 : 2

A가 기다리는 시간 : 7

 

---

---

● 라운드 로빈

Round Robin 스케줄링

: 선입 선처리 스케줄링 + 타임 슬라이스

 

타임 슬라이스 = 각 프로세스가 CPU를 사용할 수 있는 정해진 시간

 

큐에 들어온 순서대로 실행하고, 정해진 시간만큼만 쓰게 한다.

※ 풋살장 예약이랑 똑같이 생각하면 됨.

 

정해진 시간동안 프로세스가 완료되지 않았다면 , 큐의 맨 뒤에 삽입 // 이 때 문맥 교환이 이루어진다.

 

 

정해진 시간보다 적게 쓰는 건 가능, 더 쓰면 죽여버림

 

[ 특징 ]

 

● 타임 슬라이싱을 신경써야한다.

- 타임 슬라이스가 너무 크면 : 선입선출이랑 다를 게 없어짐

- 타임 슬라이스가 너무 작으면 : 문맥교환에서 생기는 오버헤드가 많아진다.

 

 

---

---

● 최소 잔여 시간 우선

Shortest Remaining Time

: 최단 작업 우선 + 라운드 로빈

 = 작업 시간이 가장 적은 프로세스 선택  ▶  정해진 시간만큼 CPU 사용 

 

---

---

● 우선순위 

: 프로세스들에 우선순위를 부여하여, 높은 프로세스부터 실행

  + 같은 우선 순위라면, 선입 선처리로 처리

 

[ 최단 작업 우선 , 최소 잔여 시간 ] 둘 다 우선순위 스케줄링의 한 종류

 

- Starvation

: 먼저 준비 큐에 들어왔는데도 우선순위가 낮은 프로세스는 실행이 계속 밀리고

  우선순위가 높은 프로세스만 실행하는 현상

 

→ 해결법 : Aging

 : 오랫동안 대기한 프로세스의 우선순위를 조금씩 높이는 방식

    = 시간이 지나면서 우선순위가 높아짐 

 

---

---

● 다단계 큐 스케줄링

= Multilevel queue 스케줄링

 

: 우선순위 스케줄링의 발전된 형태

  = 우선순위별로 여러 개 준비 큐를 사용

 

- 단점 : 프로세스가 큐와 큐 사이에서 이동 X 

        ▶ 그럼 우선순위가 낮은 큐에서도 낮은 우선순위에 있는 프로세스들은 실행기다리며 허송세월

        ▶ 또 Starvation 현상 발생

 

큐 별로 스케쥴링을 달리 할 수 있다.

우선순위 0 번 큐 : 선입선출

우선순위 1번 큐 : 최소 잔여 시간

우선순위 2번 큐 : 라운드 로빈

 

우선 0번 큐를 먼저 실행 → 선입선출로 안에 있는 프로세스들을 처리 → 0번 큐 모두 처리 다 함

→ 1번 큐로 넘어옴 → 1번 큐는 최소 잔여 시간 스케줄링으로 프로세스들 처리 → 모두 처리 다 함

→ 2번 큐로 넘어옴 → 2번 큐는 라운드 로빈 스케줄링으로 프로세스들 처리 → 처리 끝

 

끝

 

 

---

---

● 다단계 피드백 큐 스케줄링

= Multilevel feedback queue 스케줄링

 

: 다단계 큐 스케줄링의 발전된 형태

  = 다단계 큐 + 큐 간의 프로세스 이동이 가능!

 

 

새로 준비 상태가 된 프로세스를 가장 높은 우선 순위인 큐에 둔다.

▶ 실행 시킨다.

▶ 실행이 안 끝났다면? ) 우선순위가 다음으로 높은 큐에 둔다

▶ ...

 

CPU를 많이 사용해야하는 프로세스일수록 우선순위를 낮춘다.

입출력 집중 프로세스의 우선순위는 상대적으로 높아진다.  ( 왜냐? 금방 끝나니까 )

 

 

+ 여기에서도 aging 기법을 사용할 수 있다.

 

[ 다단계 피드백 큐 스케줄링 요약 ]

 

 

 

(출처)

유튜브 한빛미디어