CPU Scheduling (2)

Multilevel Queue

⇒ 여러개의 Ready Queue를 사용하는 방식

Foreground Queue = Interactive한 작업을 하는 Process가 기다리는 Queue

Background Queue = Batch한 작업을 하는 Process가 기다리는 Queue

각 Queue마다 적용되는 알고리즘이 다르다!

Ex) Interactive한 작업을 하는 Foreground Queue = Round Robin 방식 => 반응시간이 좋아진다.

  Batch한 작업을 하는 Background Queue = FCFS 방식

Scheduling method between the queues

1. Fixed Priority Scheduling : 무조건 Foreground Queue먼저 처리하고, Background Queue는 나중에 처리한다 => Starvation이 일어날 수 있다.
2. Time Slice : CPU 사용시간을 Foreground Queue 80%, Background Queue 20% 이런식으로 나누어 사용한다. 이 비율은 정책에 따라 달라진다.

Multilevel Feedback Queue

→ Starvation을 방지, 해결하는 방법 / 프로세스가 다양한 Queue들을 옮겨다닐 수 있는 Aging 방식을 사용

Multilevel feedback queue scheduler는 다음과 같은 요소들에 의해 정의된다.

1. number of queue
2. 각 Queue의 알고리즘
3. 우선순위가 낮은 Queue로 Process를 내려보내는 demote방식
4. 우선순위가 높은 Queue로 Process를 올리는 upgrade방식
5. Process가 I/O 작업, Interrupt등이 필요한 작업에 들어갔을 때 어떻게 할 것인지?

Multiple-Processor Scheduling

Multi-Processor의 Scheduling은 Single-Processor보다 더욱 복잡해진다.

• Asymmetric Multiprocessing : 하나의 Processor는 master역할을, 나머지 Processor는 Slave역할을 한다.
• Master Processor가 Scheduling을 담당하고 Slave Processor들은 Scheduling을 하지 않고 Master Processor가 할당해 주는 일만을 한다. → 간단하다‼️
• Symmetric Multiprocessing : Homogeneous(동등한) Processor들이 각자 Scheduling을 한다.하지만 요즘 나오는 운영체제 : Windows, Linux, Mac OS X등은 SMP방식을 사용한다고 한다.
• 두개의 Processor가 같은 Process를 Scheduling하지 않도록, 또는 Process를 잃어버리지 않도록 주의해야 한다. → 복잡하다‼️

Processor affinity

Process가 계속 같은 CPU에서 처리되도록 Scheduling을 하는 것을 보장하는 정도에 따라 Soft와 Hard로 나뉜다.

Process P1이 CPU C1에서 처리된 뒤 I/O작업을 거쳐 다시 Ready Queue에서 CPU를 할당받을 차례가 되었을 때 C1의 Cache에는 P1을 처리하는데 유용한 Cache들이 남아있기 때문에 P1을 C1에 할당하는 것이 이득이다.

Hard affinity : P1이 C1으로 배정되는 것을 보장한다. (무조건)

Soft affinity : P1이 C1으로 배정되도록 노력하지만 보장되지는 않는다.

Thread Scheduling

CPU는 Kernel-level의 Thread만 처리하고 User-level의 Thread는 처리하지 않는다. -> User thread는 LWP( Light Weight Process ) 또는 Virtual Thread에 할당되어야만 한다.

• Local Scheduling : User-level Thread가 Virtual Thread나 Light Weight Processor에 할당되는 것.

*Light Weight Process = Virtual Process = Kernel Thread와 User Thread를 연결해주는 Thread.

• Global Scheduling : CPU가 Kernel Thread를 선택하는 것.

RealTime Scheduling

Hard Real-time Systems : 제 시간안에 끝나는 것을 보장.

Soft Real-time Systems : 제 시간안에 끝나는 것을 보장하지는 않지만…..노력할게…

여러가지 Operating Systems

Solaris

• Interactive, Time-Sharing 알고리즘을 사용한다.
• 우선순위가 높을수록 ⬆️ Time Quantum값이 작다 ⬇️ .
• 상대적으로 I/O가 끝난 Process의 우선순위가 높다.
• Interactive한 작업에는 Response Time이 좋고 CPU Bound 작업에는 Throughput(처리량)이 좋다.

Linux

• Time-Sharing 과 Real-Time 알고리즘을 사용한다.

Time-Sharing

• **Credit-based(신용도 기반)**으로 우선순위를 정한다. 신용도가 높을수록 ⬆️ 우선순위가 높다 ⬆️ .
• 한번 처리된 Process는 Credit이 차감된다.
• 모든 Process들의 Credit이 0이 되면 Recredit 과정이 진행된다. (다시 Credit을 주는 과정). 이 때, Priority와 History를 고려하여 Recredit을 한다.

Real-Time

• Soft Real-time systems을 사용한다.
• 우선순위가 높을수록 Quantum의 값이 크다 -> Soft Real-time
• Active Array와 Expired Array가 따로 있어 Active Array에서 처리된 Process는 Expired Array에 들어가게 된다.

Algorithm Evaluation

Scheduling 알고리즘을 평가하는 방법

• Deterministic Modeling : Gantt등을 사용하여 Waiting Time, Response등 여러 수치를 평가한다.
• Queuing ModelN = Ready Queue의 평균 길이W = Process가 기다리는 시간.
• λ = 평균적으로 Queue에 도착하는 비율 (avg. Arrival Time)
• N = λ * W
• Simulation model : Simulation을 진행하고 여러 수치를 계산한다.