추가적으로 Scheduling Algorithm들을 더 기록해두려고 합니당😊

1.Priority Scheduling

앞서 이미 우선 순위 스케줄러의 예들을 봤습니다.
- SJF, STCF는 모두 우선 순위 스케줄러 입니다. (우선순위 = CPU Burst Time)

• 우선 순위 스케줄링 문제
  - Starvation: 우선 순위가 높은 작업이 CPU를 지배 할 수 있는 문제점

• 해결책
  - 프로세스 동작에 따라 설정
  - 대기 시간에 따라 설정
  ex) 준비 대기열에서 소요 된 시간

1.1 EDF (Earliest Deadline First)

• Preempt Algorithm
• Deadline 존재
  Deadline이 가장 가까운 것을 scheduling 한다
• Optimal Algorithm 이다.
  why? -> Preempt Scheduler일 때, EDF Scheduler로 만족시킬 수 없다면 다른 스케줄러로도 만족시킬 수가 없음
• 일반적으로 실시간 OS에서 사용함 - Deadline을 알아야 한다는 가정하에
  ex) 원자력 발전소, 우주선 등

1.2 MLQ (Multi-level Queue)

• Key idea - Divide the ready queue in two
  1. High priority Queue = interactive processes
  RR Scheduling
  2. Low priority Queue = CPU bound processes
  FCFS Scheduling

• 정적인 구성으로 되어 있음
  1. 각 프로세스에는 시작시 우선 순위가 지정됨
  2. 각 대기열에는 고정 된 양의 CPU 시간이 제공됨
  ex). High priority Queue = 80%
Low priority Queue = 20%

  

  

>> MLQ의 4가지 문제점
💧 1. 무엇이 High priority이고, Low priority인지 모른다는 점
💧 2. 대기열에 고정된 양의 CPU 시간을 제공하는데, 이에 대한 기준이 모호함
💧 3. High와 Low가 섞여있는 process들은 어떻게 처리할 것인가?
💧 4. Low에서 FCFS로 진행될텐데, 이때 convoy 문제는 어떻게 해결 할 것인가?
    ->우선순위가 낮은 queue는 Starvation 현상 발생 가능

1.3 MLFQ (Multi-level Feedback Queue)

1.3.1 MLQ와의 차이점

• MLFQ는 프로세스 Queue간 이동이 허용된 MLQ이다.
• 여러 우선순위 대기열 존재

1.3.2 목표

• Turnaround Time & Response Time을 최소화
• 프로세스 우선 순위를 동적으로 할당
  Burst time, 프로세스 동작에 대한 사전지식 필요 없음
  

1.3.3 MLFQ Rule

1. Priority A > B → A runs, B dosen't
2. Priority A = B → A & B run in RR
3. Process start at the highest priority
   I/O, CPU bound process 인지 알 수 없음
   일단, I/O라고 가정하고, 우선순위가 높은것을 실행하고, 아니면 우선순위를 낮춰감
4. 우선 순위 변경
   - 지정한 queue에서 time-slice를 다 사용하면 우선순위 낮춤
   - Time-slice를 끝내기전에 동작이 완료되면 우선순위 유지(I/O를 위한 것)

1.3.4 MLFQ Examples

1. CPU bound process가 들어오게 되면 일단 이게 I/O인지 CPU bound인지 알 수 없음, 따라서 일단 우선순위에 집어 넣어 실행한 뒤 우선순위를 점차 낮춰가는 방향으로 진행
2. I/O와 CPU Bound Processes가 섞여 있을 때, I/O는 Time-slice내에 끝나기 때문에 우선순위가 계속 유지됨

1.3.5 MLFQ Problem

1. Starvation - 우선순위가 높은 프로세스가 계속 들어오게 되면 우선순위가 낮은 프로세스는 실행을 못할수도 있음
2. Cheating - Time-slice가 끝나기전에 동작이 완료되면 우선순위 유지된다는 Rule을 악용하는 사례가 발생할 수 있음

>> 그래서 위와 같은 문제점을 해결하기 위해 새로운 Rule을 추가합니다.
1. Priority Boost (Starvation 문제점 해결) - 특정 시간(S)이 지나면, 모든 프로세스들을 제일 높은 우선순위로 변경
2. Cheat Prevention (Cheating 문제점 해결) - time-slice마다 얼마나 썼는지 check하는 것이 아닌, 현재 queue에서 CPU를 얼마나 사용했는가를 check 하는 방식으로 Rule 변경

1.3.6 구현하기 위해서는 여러가지 고민이 필요하다

• Queue를 몇개를 해야 되는가?
• 각 Queue의 CPU 할당의 퍼센티지
• Scheduling의 종류도 정해줘야함
• Time-slice / Quantum
  우선순위↑, time-slice↓
  우선순위↓, time-slice↑
• boost priority는 얼마나 자주?

2. Fair Share Scheduling

2.1 Lottery Scheduling

• Key idea - 각 프로세스에 티켓 제공, 타임 슬라이스마다 스케줄러가 추첨
  당첨 티켓을 보유한 프로세스가 실행됨
• Probabilistic Scheduling (확률적 스케줄링) - 시간이 지남에 따라 각 프로세스의 실행 시간은 올바른 값(즉, 보유한 티켓의 확률)으로 수렴

2.1.1 Implementation Advantages

1. 매우 빠른 스케줄러 실행
   - 스케줄러는 random()(난수 발생)을 실행하기만 하면 됨
2. 많은 상태를 저장할 필요가 없음
   - 티켓 넘버를 어디서부터 어디까지 갖고 있는지만 알고 있으면 됨
   
3. 프로세스간 CPU 시간을 자동으로 균형 조정
4. 프로세스의 우선 순위 지정 용이
   - 우선 순위가 높은 프로세스에 많은 티켓 제공
   - 우선 순위가 낮은 프로세스에 몇 개의 티켓 제공
   

2.1.2 Is Lottery Scheduling Fair?

• 수행시간이 짧으면 Fair 하지 않은 효과를 발생
• 수행시간이 길면 결국 확률적인 값(Fair)에 수렴하게 되어 있다.

Lottery Scheduling의 무작위성은 간단하고 대략적으로 공정한 스케줄러를 구축 가능하게 해주지만, 공정성이 보장되는 것은 아닙니다.
다음과 같은 스케줄러는 Lottery보다는 공정성이 보장되는 스케줄러입니다.

2.2 Stride Scheduling

• Stride(보폭) - 공배수를 아주 큰것을 하나 만들고, 만든 숫자를 tickets으로 나눈값을 stride라고 합니다.

2.2.1 Example

공배수를 10,000이라고 가정하고 각 프로세스의 Tickets들로 나누게 되면 그 값이 Stride이다. 따라서 P1 Stride = 100(10000/100), P2 Stride = 200(10000/50),
P3 Stride = 40(10000/250) 이다.
각 프로세서는 Arrival Time이 같기 때문에 랜덤으로 실행되지만 이번에는 P1 process가 먼저 실행된다는 가정하에 문제를 작성해봤다.

이 과정에서 새로운 processer가 왔을 때, pass값을 어떻게 줄것인가는 Stride Scheduler의 문제점입니다.

2.2.2 Lottery Scheduler vs Stride Scheduler

• 구현의 간단함 - Lottery Scheduler > Stride Scheduler
  Stride Scheduler는 Lottery Scheduler에 비해 여러가지 정보를 입력해야 합니다.
  또한 히스토리를 유지해야 하는 번거로움이 있습니다.

• 둘의 공통적인 문제 - 티켓을 얼마나 줘야할것인가는 두 스케줄러의 공통적인 문제입니다.