[OS] CPU Scheduling 알고리즘, 평가 척도

CPU 스케쥴링 알고리즘

mem 내에서는 어느 시점이 지나서 p1 -> p2 ... 이렇게 돌아가는데 그렇게 메인 메모리 내에서 process 의 switching이 일어나는 것을 context switching이라고 한다.

CPU 스케쥴링 용어

Ready Queue 에서 어떤 프로세스를 선택해서 cpu에게 보내줄지를 계산하여 결정하는 것. 순서대로 하는 것이 가장 쉽기야 하겠지만, 그보다 더 효율적인 경우가 있을지를 계산하여 순서를 결정한다. 그 업무를 담당하는 프로그램을 OS 내 cpu 스케쥴러 라고 한다.

시나리오를 보자.

1. context switching가 일어나야함 : p1 -> p2로 작업이 변경되어야한다.
   • context switching : CPU에서 작업할 프로세스가 교환되는것
2. p1이 현재상태 mmu_base, mmu_limit, ,... 등의 값들을 pcb1에 저장한다.
3. p2를 실행시킨다
4. cpu가 p1를 (re-store 되어있는 pcb1의 정보를) 다시 불러온다.

OS에서 이러한 일을 담당하는 프로그램을 dispatcher라고 한다.

이를 context switching 오버헤드라고도 한다. 왜냐하면, p1 -> p2작업을 변경하기 위해서 추가로 드는 시간이므로. 그래서 특히나 이런 dispatch 프로그램은 효율이 굉장히 좋아야 하므로, 어셈블러로 코딩하여 오버헤드를 최대한 줄여야한다.

 

---

CPU 스케쥴링

CPU가 현재 작업이 끝나고 CPU 가 다음으로 어떤 작업을 하게 할 것인가? 그 관련되어 여러가지 스케쥴링 방식을 배워본다. 그리고 그 기준들에 대하여 배운다.

우선, 프로세스를 어떠한 방식으로 종료시킬지에 대해 두가지로 구분이된다. CPU스케쥴링에서 preemptive방식으로 구현하거나, non-preemptive 방식으로 구현하거나.. 이렇게 나뉜다.

Preemptive(선점) vs Non-preemptive(비선점)

• Preemptive : 아직 프로그램이 끝나지 않았는데 강제로 쫓아내고 새로운 프로세서를 실행시키는 것
• Non-preemprive : 어떤 프로그램이 끝나거나 I/O를 만나기 전에는 절대 프로세서를 종료시키지 않는 것

Scheduling Criteria

스케쥴링 방식의 평가에 따른 척도를 Scheduling Criteria라고 한다. 그 평가 기준에는 여러가지가 있다.

• CPU Utilization(CPU 이용률) [%]
  : 최대한 CPU가 쉬지않게 일했는지?
• Throughput(처리율) [jobs/s]
  : 1s 동안 몇개의 작업이 끝?
• Turnaround time(반환 시간)
  : 작업이 ready Queue(main mem내)로 들어가서 ~ 다 처리되고 나오는데 걸리는 시간 ~~I/O를 만나면 device Queue로 들어갔다가 끝나면 다시 Ready Queue로 오고...
• Waiting Time(대기 시간)
  : 작업을 받기 위해 Ready Queue에서 얼마나 기다렸는지
• Response Time(응답 시간)
  : 대부분 interactive system (대화형 시스템을 사용하는 컴퓨터)에서 응답하는데 걸리는 시간. ex. 엔터키 치고, 응답나오는데 걸리는 시간

어느 방식으로 하니까 대기시간이 늘어나고,, 했는지 위 척도를 이용해서 판단할 것임.

 

---

CPU Scheduling Algorithms

• FCFS(First Come First Served)
• SJF(Shortest-Job First)
• Priority
• RR(Round Robin)
• Multilivel Queue
• Multilevel Feedback Queue

의 방법이 있다. 좀 더 자세하게 알아볼 것 임!!

 

 

 

FCFS

First Come First Served. 가장 먼저 온 애 먼저 처리해준다. 가장 간단.

• ❓[Example]
  Process P1, P2, P3의 순서대로 작업이 들어오고, 각각 24, 3, 3msec을 Burst Time으로 한다. 이 때 Find Average Waiting Time은?

• ❗️[Solution]

Gantt Chart(간트 차트)

•  

  P1은 안기다림(0), P2는 P1이 끝날때까지 기다렸음(24), P3는 P1, P2가 끝날때까지 기다렸음(27)
  AWT = (0 + 24 + 27)/3 = 17 msec.

  하지만, P3, P2, P1의 순서대로 작업이 들어왔다면 끝나는 시간은 30ms로 같겠지만!
  P1은 P2, P3이 끝날때까지(6), P2는 P3이 끝날때까지(3), P3는 안기다림(0) 하여
  AWT = (6 + 3 + 0)/3 = 3 msec.

  척도를 대기시간으로 보았을 경우 후자의 경우처럼 P3, P2, P1순서로 작업을 처리하는 것이 더 좋다.

• [FCFS의 단점]
  Convoy Effect(호위 효과) 워딩 그대로, cpu 실행시간을 많이 소모하는 프로세스가 앞에 있다면, 나머지 프로세스들이 뒤에서 시중들듯 따라와야만 하므로 이렇게 P1, P2, P3 프로세스가 들어오는 경우를 convoy effect 라고 한다.

• Non-preemprive : 어떤 프로그램이 끝나거나 I/O를 만나기 전에는 절대 프로세서를 종료시키지 않는다.

 

 

SJF

• Shortest-Job First. 짧은 프로세스를 먼저 실행시킨다.

• 수학적으로 증명해보니, Provably optimal! SJF가 가장 좋다.
  하지만, 비 현실적이다.(not realistic). 이론적으로는(우리가 문제를 풀 떄) P1: Burst Time: 6msec, P2 : 8 ... 이렇게 주어지지만 실제로는 프로세서가 cpu time을 얼마나 사용할지 알지 못하기때문에 비 현실적이다. 그래서 얼마나 사용할지 prediction해야하는데, 이 계산을 하는데 또 오버헤드가 생김.. 그래서 이 방법을 사용하기 현실적으로는 어렵다는 결론에 도달.

• Preemptive || Non-preemptive 두가지로 만들 수 있다. 계산해보자.

  • ❓[Example] preemptive / Non-preemptive SJF

    Process	Arrival Time	Burst Time
    P1	0	8
    P2	1	4
    P3	2	9
    P4	3	5

    각 Process 가 ${ArrivalTime}초에 ${BurstTime}을 실행시간으로 갖는 차트.

  • ❗️[Solution] Preemptive

Gantt Chart(간트 차트). Ready Queue의 모습.

• 어떤 프로그램이 끝나거나 I/O를 만나기 전에 종료 able

  • preemptive SJF 를 Shortest-Remaining-Time-First(최소잔여시간 우선).
    남아있는 것 중 가장 짧은 것을 가장 먼저 실행한다. 라고도 한다.

• ❗️[Solution] Non-Preemptive

  어떤 프로그램이 끝나거나 I/O를 만나기 전에는 종료 절대 x

 Gantt Chart(간트 차트). Ready Queue의 모습.

 

Priority

• 누가 더 우선되느냐?
• 일반적으로 우선순위는 정수값으로 표현한다. (integer number). 숫자가 작은게 우선순위가 더 높음.
• preemptive, non-preemptive 모두 구현 가능하다.
• ❓[Example]

   

  Process	Burst Time	Priority
  P1	10	3
  P2	1	1
  P3	2	4
  P4	1	5
  P5	5	2

• ❗️[Solution]

Gantt Chart(간트 차트). Ready Queue의 모습.

• 단점
  • starving : 너무 우선순위가 낮은 프로세스는 자기 차례를 기다리고있는데, cpu가 계속 해서 들어오게 되면 그 들어온 새로우 작업에 밀려 계속 일을 할 수 없게 될 수 있음.
    -> aging algorithm으로 해결! OS가 ready Queue를 조사해서 너무 오래 기다리고있다고 하면 점진적으로 우선순위를 높여주는 것
    -> aging은 점점 나이가 든다는 것 처럼 해준다. 는 의미이므로, 너무 오래 기다리고있다고 하면 프로세스의 우선순위를 높여주는 역할을 한다.

 

RR

• Round-Robin. Time Quantum(Slice)를 엄청 짧게 두어서 P1, P2, P3, P1, P2, P3 ... 일이 끝날때까지 반복하는 것.
• Preemptive Scheduling : 작업이 끝나지 않더라도 일정시간이 지나면 자동으로 다른 프로세스로 넘어감
• delta에 따라 성능이 크게 달라진다. 그리고 델타를 정하는 알고리즘이 OS내에 따로 탑재된 경우들이 많아, 최적의 delta를 구하기위해 여러번 계산하는 것 같다.
• ❓[Example]
  Time Quantum = 4msec일 때

  Process	Burst Time
  P1	24
  P2	3
  P3	3

• ❗️[Solution]

Gantt Chart(간트 차트). Ready Queue의 모습.

- 위에서는 AWT를 계산했지만, RR의 경우 ATT(Average Turnaround Time)로 표현할 수도 있다. ATT란 들어가서부터 나오는데까지 걸리는 시간!

• Time Quantum의 Size(TimeSlice횟수)에 굉장히 의존적이다.
  • if(TImeQuantum = infinite) : FCFS와 동일(들어온대로 나감)
  • if(TimeQuantum = 0) : process sharing. 굉장히 빈번하게 switching 이 일어나므로 동시에 여러개의 프로그램이 같이 공유하는 것 처럼 보인다. (사실 이 경우 TimeSlice에 의해 오버헤드가 계속 발생하므로 그렇게 좋지는 않다)

---

Multilevel Queue Scheduling

interactive process 는 무조건 즉각 빨리 처리되어야하는데 batch는 interaction을 하지 않으니까, 조금 느리게 처리돼도 괜츈하다.

이러한 맥락으로 보면, Ready Queue하나에 위의 다양한 프로세스들을 넣으면, 효율이 떨어진다. batch는 user와 interaction하지 않지만 interactive는 리얼타임이니 말이다! 각각 중요한게 매우 다름.

Multilevel Queue Scheduling

 

그래서, Ready Queue를 여러개를 두자! system Ready Queue, Interactive Ready Queue, Batch Ready Queue... 이렇게 여러개의 큐를 두겠다는 것이 Multilevel Queue Scheduling이라고 한다. 가장 중요한 것을 위부터 두어서, system , interactive, batch 순으로 두곤 한다.

정리하면, multilevel Queue Scheduling은 프로세스를 중요한 정도에 따라 여러 레벨 그룹으로 분류해 그 여러개의 큐의 기준에 따라 다양한 알고리즘을 적용하는 스케쥴링 기법이다.

• system processes : 가장 긴급하게 ! 처리되어야한다.
• interactive processes (Ex. 게임, interactive아닌거: batch process, compile)
• interactive editing process (Ex. word)
• batch processes (User와는 상관없이 돌아감. non-interactive. 일괄 처리)
• student processes

시나리오를 보자. 어떠한 프로세스가 들어오면 아래와 같은 방식으로 실행된다.

1. 어떤 프로세스가 들어온다
2. 각기 성격에 맞는 Queue에 줄세움
3. 그 Queue는 설정이 모두 다르게 되어있어 (성격에 맞도록) Ready Queue에서 기다리다 가 cpu의 처리를 받도록 함.

이 방식은 Single Ready Queue 가 -> Several separate Queue 가 되었다고 볼 수 있고

• 각각의 Queue 에 절대적인 우선순위 존재
• CPU time을 각각 Queue에 차등 배분
• 각 Queue는 독립된 scheduling 정책

을 특징으로 한다.

하지만 이 방식에 문제점이 있는데, 사실 multilevel Queue에서는 프로세스가 해당 큐에 줄을 서면 종료될 때 까지 다른 큐로 이동할 수 없다. 따라서, starvation이 발생해도 조치하기가 힘든것이다.

그래서 고안한 방식이 Queue끼리의 이동을 가능케하자는 의미에서, multilevel Feedback Queue라는 방식을 사용한다.

Multilevel Feedback Queue

Feedback이란, 뒤에서 다시 앞으로 오는 ! 의미를 가지고있다. 그래서 복수개의 Queue(각 정책이 다른)을 가지고있을 떄 한 큐에 머물러있지 않고 다른 Queue로 이동을 하는데, 아래와같이 위아래로 슉슉 이동한다.

• 모든 프로세스는 하나의 입구로 진입하여
• 너무 많은 CPU time 사용시 다른 Queue로이동
• starving 상태(너무 오래기다림)우려될 경우 우선순위 높은 Queue로이동
• 모든 프로세스는 기본적으로 줄 설때는, 가장 위의 큐에 줄을선다.

예를들어, Several Separate Queue를 사용하여 어떠한 BatchReadyQueue에서 기다리고있다가, 서비스를 받고 나가고,,,를 반복해도 그 해당 프로세스가 작업이 끝나지 않으면 (잘려서 처리되는경우도있으니) starving상태라고 판단하여
-> InteractiveReadyQueue 에서 처리,, 그래도 작업이 오랫동안 잘 안끝나면
-> SystemReadyQueue``BatchReadyQueue ... 이렇게 큐를 옮겨가며(정책 변경) 프로세스를 처리시키는 것을 말한다.

❓질문

Starving 상태 라는 것이 Priority Queue Scheduling 의 단점으로 뽑히며
starving : 너무 우선순위가 낮은 프로세스는 자기 차례를 기다리고있는데, cpu가 계속 해서 들어오게 되면 그 들어온 새로우 작업에 밀려 계속 일을 할 수 없게 될 수 있음.
일정시간동안 OS가 판단하기로, 왜이렇게 오래걸려! 하는 친구들을 말하는거.

그렇다면 우선순위가 높은 큐로 이동한다고 했는데, System Queue는 가장 높은 우선순위를 가질 것 같은데 거기서 잘 처리되지 않는 친구들은 그냥 sw interrupt 등을 통해 해당 프로세스를 종료시키는 것인가??

-> 모든 프로세스는 줄을 설 때 가장 위의 큐에 줄을 서다가, 가장 위의 quantum(실행 시간)안에 끝났을 경우 : 큐에서 나감, 그 이상 더 많은 실행시간이 필요한 경우 우선순위가 낮은 큐로 이동한다.
-> 만약 두번째 우선순위 큐에서도 끝나지 않는다면, 하위 큐로 더이상 진행되지 못한다.

Multilevel Feedback Queue의 스케쥴링을 정의하는 parameter

• Queue의 수
• 각 큐의 스케쥴링 알고리즘(RR, FCFS, SJF, priority)
• 프로세스를 상위, 하위큐로 보내는 기준
• 프로세스가 첫 cpu를 받으려 할 때 어느 큐에 넣을지의 기준

위와같이, multilevel feedback queue의 스케쥴링을 정의하는데 관여하는 여러 요소들이 있다. aging방식을 구성하여 우선순위가 높은 큐로 프로세스를 이동시킬 수 있기 때문에 starvation을 막을 수 있게 구현이 가능하다.

💭 그렇다면 윈도우와 리눅스는 실제로 어떠한 방식을 사용할까?

다양한 Queue를 두고 다양한 Queue Scheduling 정책을 두어 다양한 프로세스 처리를 한다.