# Outline:

• 1. Examples
• 2. Basic Concepts
• 3. Scheduling Criteria
• 4. Scheduling Algorithms
• 5. Multiple-Processor Scheduling
• 6. Thread Scheduling
• 7. Linux Scheduling
• 8. Algorithm Evaluation

1.Examples

2.Basic Concepts:

Alternating Sequence of CPU and I/O bursts:

General rule of Scheduling:

give higher priorities to I/O bound processes thatn CPU-bound processes -> waiting-time을 최소하는데 효과적이다.

CPU scheduler:

selects from the processes in memory thar are ready to execute, and dispatcher allocates the CPU to one of them

CPU scheduler decision may take place when a process:

1. Switches from running to waiting state
2. Terminates (from running to termination)
3. Switches from running to ready state.
4. Switches from waiting to ready state. (ready로 전환된 프로세스의 우선순위가 현재 실행중인 프로세스의 우선순위보다 높을수있기때문에)

-> 1,2 : non-preemptive scheduling.
-> 3,4 : preemptive scheduling.

Preemption in the kernel

3.Scheduling Criteria:

1. cpu utilization:

   • keep the cpu as busy as possible

2. throughout

   • #of processes that complete their execution per time unit

   -> 1,2 is applied to the entire system

3. turnaround time

   • completion of process

4. waiting time

   • amount of time a process has been waiting in the ready queue

5. response time

   • amount of time it takes from when a request was submitted until the first response is produced.

   -> 3,4,5 from the point of view of a particular process

4.Scheduling Algorithms

1. First-come,Fisrt-served(FCFS) scheduling:

• Convoy effect: cpu burst length가 짧은 process가 긴 process 뒤에 스케쥴링되면 average waiting time을 증가시킨다.

2. Shortest-Job-First (SJF) Scheduling:

• 가장 Optimal(average wating time을 줄이는) 한 스케쥴링 알고리즘이다.
• 다음에 실행할 남은 프로세스 중 가장 짧은 프로세스를 결정하는 것이 필요하다.

why optimal?

SJF(Non-preemptive)

SJF(preemptive)

다음에 실행할 프로세스의 CPU Burst length를 구하는것은 실용적이지 않다.

• Next CPU Burst를 예측할수있어야한다.
• Exponential averaging을 사용한다.
• 두 가지 기준으로 예측한다.
  1. history cpu burst
  2. recent history
  
  
• 알파값은 자유롭게 줄수있다.

3. Priority Scheduling

• 낮은 priority number를 가질수록 높은 prioiry를 가진다.
• 문제점:
  • Starvation(indefinite blocking)
    • low priority processes may never execute
  • solution:
    • aging기법: 긴 시간 동안 레디큐에서 대기한 프로세스의 우선순위를 점차적으로 증가시키는것.
• static priority: priority number is fixed
• dynamic priority: priority number can change

4. Round-robin Scheduling

• time quantum만큼 실행되고 번갈아가면서 스케쥴링하는 알고리즘
• Preemptive한 스케쥴링이다.
• time quantum이 크면 FIFO 구조가 된다.(fairness가 약해진다.)
• time quantum이 작으면 context switch가 빈번하게 발생해 overhead가 너무 크다.

5. Multilevel Queue

• 총 세번의 스케쥴링이 필요하다
  1. 프로세스가 어떤 큐에 들어갈지
  2. 각 큐에서 어떤 프로세스를 선택할지
  3. 큐 간에 프로세스를 선택하는 것

• 큐 간에 스케쥴링은 두 가지 방법이 존재한다
  1. Fixed priority scheduling
  2. Time slice

Multilevel FeedBack Queue

• 큐간의 프로세스 이동을 허용한다.

5.Multiple-Processor Scheduling

• CPU가 여러개 있을때 CPU 사이의 관계는 2가지가 있다.

  1. Symmetric: 모든 프로세스가 동일한 관계
  2. Asymmetric: CPU 사이에 master-slave 관계가 있다.

• 위 관계를 기반으로 CPU 스케쥴링은 두가지 방법이 있다.
  1. Symmetric Multi-Scheduling

  2. Asymmetric Multi-Scheduling

  CPU Scheduling issue

1. Process affinity:
   - 프로세스가 실행될때 프로세스는 특정 프로세서에 affinity를 가지고 있다.
   
   - affinity도 2가지로 나뉘는데
   1. soft affinity: affinity를 해주려고 하나, 보장은 못해준다.
   2. hard affinity: 무조건 affinity를 보장해주는것.(리눅스에서는 시스템콜을 명시적으로 호출하여 hard affinity를 보장해줄수있다.)
   
2. Load Balancing
   1. push migration:
      • 프로세서의 work-load를 체크해주는 별도의 프로세스가 있다.
      • 그 프로세스가 할당된 프로세스가 많은 프로세서의 프로세스들을 널널한 프로세서들에게 push해준다.
        
   2. pull migration:
      • 커널에서 널널한 프로세서엑 바쁜 CPU의 task를 pull 해서 가져옴.
        

6.Thread Scheduling

• 각 클래스내에서 특정 알고리즘에 의해 스케쥴링(prioiry,cfs)이 발생하고,
• 큐 간에 스케쥴링(priority)이 일어난다.

• 각 프로세스들은 3개의 클래스로 나뉘어진다.

1. Real-time FIFO classes: prioriy+FIFO 구조

• 우선순위가 동일한 프로세스가 큐에 있으면 먼저 들어온 프로세스를 먼저 스케쥴링한다.

2. Real-time RR classes: prioriy+Roubd-robin 구조

• 우선순위가 동일한 프로세스가 큐에 있으면 각각의 process들은 time-quantum만큼 실행하고 큐의 마지막부분으로 간다.-> 번갈아가면서 스케쥴링된다.

3. Conventional classes: CFS(Completely Fair Sharing) 방식

• 리눅스 2.6.23부터, CFS는 Conventional class들의 디폴트 스케쥴러 방식이 되었다.

• 특정시간에 1개의 process만 실행할수 있기 때문에 현실불가능한 방법이다.

• 대안으로,

• 위 방식을 사용한다. 어떤 시점에서 보더라도 proportion을 보장해준다.
• 리눅스는 CFS를 아래와 같이 실행한다.

• 가장 작은 vruntime을 가진 task를 선택한다.

• 즉 위의 방식으로 실행하면 어떤 시점에서 보더라도 proportion을 보장해준다.

7.Linux Scheduling

8.Algorithm Evaluation

1. Deterministic modeling:

특정한 프로세스와 프로세스의 burst time을 미리 정하고 gant chart를 이용해서 average waiting time, response time을 구하여 알고리즘을 평가한다.

2. Queueing models:

3. Queueing models:

4. Implementation: