[OS] Scheduling Algorithm - 2 (RR, Priority Scheduling, Multilevel Queue)

 

 

 

---

Scheduling Algorithm - 2

RR, Priority Scheduling, Multilevel Queue

---

 

 

 

 

1편에 이어서 Scheduling Algorithm에 대해서 계속 알아봅시다.

 

 

1. RR (Round Robin)

 

기본적으로 FCFS(First-Come First-Served)에서 preemptive가 추가되었다고 보면 됩니다.

Round Robin 알고리즘에서 가장 중요한 점은 모든 프로세스에 기본적으로 같은 시간을 준다는 것입니다.

실제로는 보통 0~100ms 정도의 시간을 준다고 하네요.

아무튼 미리 정해놓은 시간이 다 되면, CPU를 뺐기고, queue의 뒤로 가는 식으로 진행됩니다.

 

대신에, 이 time unit이 너무 크면 FCFS랑 같은 격이 되고, 너무 잦은 경우에는 너무 잦은 context switch때문에 오버헤드가 커지겠죠? 뭐든 적당한게 최고,,,

 

+) 실제로는 Round Robin과 SFJ를 합쳐서 쓴다고 합니다.(계산하는 것 대신에 그냥 시간제한을 거는 식으로)

 

- 특징

• 모두가 CPU를 쓸 수 있기 때문에, 응답시간이 빨라집니다. (response time, 처음 할당되는 시간)
• 최대 (n-1)q time unit만 기다리면 된다는 보장이 있음

- 예시

예시는 두 가지를 볼 것입니다. time unit이 4일때와 20일때로 나누어 볼 것입니다.

먼저 4일때를 봅시다.

 

 

4초씩 번갈아가면서 쓴다는 이야기겠죠?

 

 

p2와 p3은 비록 뒤에있었지만, convoy effect 없이 빨리 마무리한것을 볼 수 있습니다.

Average waiting time = ((10-4) + 4 + 7)/3 = 5.66

Average turnaround time = (30+7+10)/3 = 15.67

 

 

다음은 20일때입니다.

 

table을 봅시다

Average waiting time = [(121-40)+20+(134-40)+(117-20)]/4 = 73

네. 대충 같은데 이 경우에도 time unit을 4로 잡았으면 너무 난도질을 당했겠죠? 아무튼 적당히 설정하는게 중요하다는거.

참고로 실험한 결과가 있는데, 왠만하면 프로세스들이 한번에 프로세스를 다 끝낼수록 ATT가 짧아진다고 합니다.

 

 

아무튼 RR이 현실적으로 봤을 때 가장 의미있다는 것입니다. 실제로 OS를 구동시키면 burst time이 길고 짧은 것들이 마구 섞여있고, 실제 사용시간을 알기 어렵기 때문에 실제로 Round Robin을 자주 쓴다고 합니다.

 

 

2. Priority Scheduling

Priority Scheduling은 우선순위가 높은 프로세스부터 스케줄링입니다. 각 프로세스마다 우선순위 번호가 할당되어 있다고 가정합니다. 이 priority 자체는 추상적으로 정해져 있겠죠. 예를 들자면 SJF처럼 burst time을 하나의 단위로 둘 수 있겠죠.

 

이걸 크게 내부적(Internally), 그리고 외부적(Externally)로 나누는데, 이거는 쉽게 내부적인 요소는 원래 정해져 있는 값들(ex. 실행시간, 시간 limit, 파일을 여는 갯수, I/O burst의 비율 등등..)이고, 외부적 요소는 프로세스 자체와 별개로 주어지는 우선순위로 보면 되겠습니다.

 

선점형/비선점형 두 가지 버젼이 있는데, 이건 그냥 SJF와 똑같아서 생략하도록 하겠습니다.

선점형의 경우에는 RR도 적용시킨다는 점만 보면 될 것 같습니다.

 

- 단점

Starvation 발생 : 계속 자신보다 높은 우선순위의 프로세스들이 계속 들어오면 평생 실행이 안됨

해결 : Aging 도입(시간이 오래있으면 우선순위 더 높이기. 일종의 노인공경)

 

 

3. Multilevel Queue

 

그동안은 한줄로 세워서 누구부터 할까를 고민했다면, 이 방법은 아예 줄을 여러개로 나눈 경우입니다.

위로갈수록 우선순위가 높아지는 거고, 누구를 먼저 하지?가 아닌, 어떤 줄로 보내지? 로 바뀌는 알고리즘입니다.

 

 

일단 이런 방법의 문제는 priority를 매기는 것 자체에 비용이 소모되는 겁니다. n개가 들어온다면 n개를 확인해야하니 O(n)이 필요하죠.

그리고 두 번째 문제는 worst case에 대한 문제입니다. 기껏 queue를 여러개로 나누어놨더니 하나로만 다 몰린다면? 몰리지 않도록 방지하는 알고리즘도 필요하겠죠.

그래서 다음과 같이 나누어서 처리합니다.

 

• Ready Queue를 여러 개로 분할해서처리합니다.
  • foreground (interactive한 job)
  • background(batch - no human interaction)
• 각 큐는 독립적인 스케줄링 알고리즘을 가진다.
  • foreground - RR (응답시간을 짧게 하기 때문에, ex. realtime process)
  • background -FCFS (응답시간을 짧게 할 필요가 없어서)
• 큐 자체에 대한 스케줄링이 필요하다.
  • Fixed priority scheduling
  • : foreground에서 모두 스케줄링하고, background 스케줄링 -> starvation 발생
  • Time slice(ex. 80% 는 foreground걸 RR방식으로, 20%는 background걸 FCFS방식으로)
  • : 각 큐에 CPU Time을 적절한 비율로 할당 (starvation 방지)

 

3.1. Multilevel Feedback Queue

 

Multilevel Queue의 경우 starvation의 문제가 생기기 때문에, 이를 방지하기 위함

- queue간 이동이 가능

- 너무 오래 대기중이면 priority up

 

 

한가지 명심해야 하는 것은, multilevel queue scheduling은 queue의 수만 늘어난 것이지, 그 안의 queue 자체를 scheduling하는 알고리즘은 앞에서 배웠던 RR, FCFS 등등을 사용

 

생각할 것

• queue의 개수
• 각 queue의 scheduling algorithm
• upgrade할때 사용되는 척도
• demote할때 사용되는 척도
• 어떤 queue에 들어갈 것인지