1. CPU Scheduling

1.1 CPU Scheduling

• process들에게 CPU를 할당해주는 작업

  왜 cpu scheduling이 필요할까?

1. CPU 이용률(utilization)을 최대화하기 위해
2. Throughout 단위 시간당 완료되는 process수를 증가시키기 위해
3. Turnaround Time(시작해서 끝나는 시간), process 실행되는 시간을 줄이기 위해
4. Waiting Time process가 ready queue에서 대기하는 시간을 최소화하기 위해
5. Response Time 프로그램의 응답시간을 최소화하기 위해

• Turnaround Time: 처음에 요청돼서 끝날때까지의 시간
• Waiting Time: 처음에 요청돼서 끝날때까지의 시간 사이에 ready process에서 대기했던 시간
• Response Time: 처음으로 CPU를 가져오는데 소모되는 시간
  🎈 수행시간 = Turnaround Time - Waiting Time 🎈

1.2 OS의 CPU Scheduler?

• memory에 load된 process들 중, 어떤 process에 할당할지 선정하는 역할
  즉, process의 status를 관리하는 역할을 한다.

1.3 Process의 수행 cycle

• process는 CPU burst (CPU를 사용하는 시간: running)와 I/O burst (waiting to ready)가 번갈아 가면서 이루어진다.

• CPU-burst가 많은 process는 CPU bound, I/O-burst가 많은 process I/O bound라고 한다.

• CPU-bound가 많은지 I/O bound가 많은지에 따라 Scheduling의 효율성이 달라진다.

1.4 Preemptive / Non-preemptive

• Preemptive (선점)
  실행중인 process들이 scheduler에 의해 강제적으로 종료되는 것

• Non-preemptive (비선점)
  process 스스로 CPU 사용 권한을 내려놓는 것

1. Switches from running to waiting // Non-preemptive
2. Terminates // Non-preemptive
3. Switches from running to ready // Preemptive
4. Switches from waiting to ready // Preemptive

1.5 OS의 Dispatcher

• Scheduler에 의해 선택된 process를 실제로 context switching 해주는 OS 모듈

• dispatcher은 빠르면 빠를수록 좋다
  dispatch latency: 실행중인 한 process가 종료하는 순간부터 다른 process가 시작하는 순간까지의 시간

1.6 CPU Scheduling Algorithms

1. FCFS (First-Come, First-Served) Scheduling

• ready queue에 들어온 순서대로 CPU 할당
• queue를 이용해 쉽게 구현할 수 있다.
  

Turnaround time = completion time - arrival time

• Wating Time: P1 = 0, P2 = 24, P3 = 27
• Average Wating Time: (0 + 24 + 27) / 3 = 17
• Turnaround Time: P1 = 24, P2 = 27, P3 = 30
• Average Turnaround time: (24 + 27 + 30) / 3 = 27

- Waiting Time과 Turnaround time을 줄일 방법은 없을까?
> Arrival Time을 역순으로 바꿔보았다

Turnaround time = completion time - arrival time

• Wating Time: P1 = 6, P2 = 0, P3 = 3
• Average Wating Time: (6 + 0 + 3) / 3 = 3
• Turnaround Time: P1 = 30, P2 = 3, P3 = 6
• Average Turnaround time: (30 + 3 + 6) / 3 = 13

>> 즉, FCFS는 작업의 순서에 따라 Waiting Time과 Turnaround Time이 바뀜

• 하나의 CPU-bound와 여러개의 I/O bound process가 존재하고, CPU-bound가 가장 먼저 자원할당을 요청한 경우라면?
  -> CPU-bound(CPU burst가 긴 process)의 작업이 다 끝날때 까지 I/O bound들이 대기해야 하는 Convoy Effect가 발생한다.
  CPU burst가 짧은 process를 먼저 처리하면 문제를 해결 할 수 있다!
  convoy effect란: 소요시간이 긴 프로세스가 먼저 도달하여 시간을 잡아먹고 있는 부정적인 현상을 의미한다.

2. SJF (Shortest-Job-First)

• CPU burst가 작은 순서대로 CPU 할당
  

위와 같이 Arrival Time이 같을 때, Waiting Time과 Turnaround Time은 다음과 같다.

• Waiting Time: P1 = 3, P2 = 16, P3 = 9, P4 = 0
• Average Wating Time: (3 + 16 + 9 + 0)/4 = 7
• Turnaround Time: P1 = 9, P2 = 24, P3 = 16, P4 = 3
• Average Turnaround Time: (9 + 24 + 16 + 3)/4 = 13

> SJF는 작업의 순서에 따라 Average Waiting Time이 최적임이 증명됐다.

위와 같이 Arrival Time이 다를 때, Waiting Time과 Turnaround Time은 다음과 같다.
Waiting Time: P1 = 0, P2 = 24, P3 = 27
Average Wating Time: (0 + 24 + 27)/3 = 17
Turnaround Time: P1 = 24, P2 = 25, P3 = 27
Average Turnaround Time: (24 + 25 + 27)/3 = 25.3

STJ는 preemptive와 Non-preemptive 두 경우가 있다.

3. STCF (Shortest Time-To-Completion First)

• STJ의 preemptive scheduling 방식
• ready queue의 CPU burst가 running중인 remain CPU burst보다 작으면 선점

동의어로 다음과 같은 것들이 더 있다!

• PSJF - (Also Known as Preemptive SJF)
• shortest Remaing-Time First (SRTF)

>> 위와 같을 때, Waiting Time과 Turnaround Time은 다음과 같다.

• Waiting Time: P1 = 6, P2 = 0, P3 = 2
• Average Wating Time: (6 + 0 + 2)/3 = 2.6
• Turnaround Time: P1 = 30, P2 = 3, P3 = 5
• Average Turnaround Time: (30 + 3 + 5)/3 = 12.7

CPU burst가 적은 프로세스가 계속 들어오게 되면, CPU burst값이 큰 프로세스들은 Starvation 문제가 있게 됩니다.

4. RR (Round-Robin)

• 시간 단위로 preemptive 하는 FCFS
• Time quantum의 시간 단위 🔔

>> 다음 두가지 경우가 발생 할 수 있음
1. CPU burst <= time quantum
- time quantum이 끝나기 전에 process 실행이 완료되므로 ready queue에 있던 다음 process가 실행됨
2. CPU burst > time quantum
- time quantum이 끝나면 running state의 process는 ready queue로 이동하고 다음 process가 CPU를 할당 받는 context switching이 발생한다.

>> Time quantum이 2일 때, Response Time과 Turnaround Time은 다음과 같다.

• Response Time: P1 = 0, P2 = 2, P3 = 4
• Average Response Time: (0 + 2 + 4)/3 = 2
• Turnaround Time: P1 = 14, P2 = 20, P3 = 24
• Average Turnaround Time: (14 + 20 + 24)/3 = 19.3

> Time quantum이 작으면 작을수록 Response Time이 빠른 것이 장점이다.
다만 Time quantum이 작으면, 위와 같이 context switch가 많이 일어나게 되고 overhead가 발생해 효율이 떨어질 수 있다.