4주차. CPU Scheduling (3) - Multi level Queue

Multi-level Queue

Ready Queue를 한줄이 아니라 여러줄로 분할한다.

• (예시)
• foreground Queue (interative)
• background Queue (batch - no human interaction)
• 등등

각 큐는 독립적인 스케줄링 알고리즘을 가질 수 있다.

• (예시)
• foreground Queue - RR 스케줄링
• background Queue - FCFS 스케줄링

큐에 대한 스케줄링이 필요하다. 두가지 방식이 존재

• 방법 1) Fixed priority scheduling
  • 무조건 foreground에 먼저 service를 제공하고, 그다음에 가능할 때 background에 제공한다.
  • → 우선순위를 무조건 지키는 형태로 Starvation을 유발할 수 있다.

• 방법 2) Time slice
  • 각 큐에 CPU time을 적절한 비율로 할당한다.
  • 예를들어 80%를 foreground Queue의 RR에, 20%를 background Queue의 FCFS에 할당하는 것.

 

구조

• process별로 우선순위가 배정되어있는 구조이다.
• 우선순위가 높은 큐부터 빠지고, 해당 큐가 비어야 다음 큐에서 CPU를 점유할 차례가 된다.
• 한번 정해진 우선순위는 변경되지 않는다. 우선순위가 낮은 프로세스는 항상 낮음.

---

Multi-level Feedback Queue

• 프로세스가 다른큐로 이동이 가능한 multi level 큐
• Starvation을 방지하는 Aging 기법을 이와 같은 방식으로 구현할 수 있다.

multi level feedback queue의 scheduler를 정의하는 매개변수

• Queue의 수 (몇 단계의 큐?)
• 각 큐의 Scheduling 알고리즘
• Process를 상위 큐로 보내는 기준
• Process를 하위 큐로 보내는 기준
• Process가 CPU 서비스를 받으려 할 때, 들어갈 큐를 결정하는 기준

 

구조

CPU의 service를 받고자하는 프로세스가 오게 되면

1. Quantum time이 8인 RR 스케줄링의 큐에 들어간다
2. 해당 시간내에 처리되지 못하면 다음 q time이 16인 RR 큐에 들어간다
3. 위에서도 처리되지 못한 프로세스는 FCFS의 큐에 들어간다

즉, Q(0) 에서 8초를 주고, 처리를 못하면 Q(1)에서 기다리고, 그러다 CPU를 받게되면 16초 동안 CPU를 점유하고, 이후에도 처리를 못하면 FCFS로 가서 처리를 하게 된다 (timer 이내 동안)

---

그 외 다양한 CPU Scheduling 기법

Multiple-Processor Scheduling

• CPU가 여러개인 경우의 스케줄링.
• 간단하게 화장실에 칸이 여러개, 음식점에 종업원이 여러명인 상황이라 가정 할 수 있다.

Homogeneous(동종) Processor 인 경우

• Queue에 한줄로 세워서 각 프로세서가 알아서 CPU를 가져가게 할 수 있다.
• 반드시 특정 프로세서에서 수행되어야하는 프로세스가 있는 경우에는 추가적인 구현이 필요하다.

Load Sharing

• 일부 프로세서에 Job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘이 필요하다.
• 별개의 큐를 두는 방법 (각각 서기) vs 공동 큐를 사용하는 방법 (한줄 서기)

Symmetric Multi-Processing (SMP, 동등한 멀티 프로세싱)

• 각 프로세서가 각자 알아서 스케줄링을 결정한다

Asymmetric Multi-Processing (동등하지 못한 멀티 프로세싱)

• 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따른다.

 

Real-Time Scheduling

Hard real-time Systems

• job이 정해진 시간안에 반드시 끝나도록 스케줄링을 하는 방법.
• 네비게이션, 원자력 시설 등

Soft real-time Computing

• job이 일반 프로세스에 비해 높은 Priority를 갖도록 한다.
• 동영상 서비스 등

 

Thread Scheduling

Local Scheduling

• User level thread의 경우 사용자 수준의 thread libray에 의해 어떤 thread에게 CPU를 줄지 스케줄링을 결정하게 된다
  • (커널이 쓰레드의 존재를 모르는 경우)

Global Scheduling

• Kenel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread에게 CPU를 줄지 스케줄링한다
  • (커널이 쓰레드를 관리하는 경우)

---

Algorithm Evaluation

• 어떤 스케줄링 알고리즘이 좋은건지 판단하는 척도

여기서 server는 CPU

• arrival rate : 도착률
• service rate : 처리율

Queueing models

• 확률 분포로 주어지는 arrival rate와 service rate를 통해 각종 performance index 값을 계산
• 이론적으로 계산하는 것

Implementation (구현) & Measurement (성능측정)

• 시스템에 알고리즘을 구현하여 작업(workload)에 대해서 성능을 측정 비교
• 실제 환경을 구현해서 테스트하는 것

Simulation

• 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교