Process Scheduling

What is Process Scheduling?

• OS가 Ready Queue에서 다음 수행할 프로세스를 결정하는 것
• Multi-Programmed OS의 기본이 되는 기능
• "CPU Scheduling" 또는 "Job Scheduling"이라고도 불린다.
• Response Time, Throughput, Fairness 등의 기준을 만족하는 방법으로 CPU에서 실행할 프로세스를 할당하는 것이 Process Scheduling의 목표이다.

Which "Scheduling" is Best?

• 다양한 Key Scheduling 기준
  • User-Oriented: Turnaround Time, Response Time, Deadline 등
  • System-Oriented: Throughput, Processor Utilization 등
  • Fairness, Balancing Resources, Enforcing Priority 등
    ⠀⠀
• 이러한 다양한 기준을 한 번에 만족시키는 것은 불가능하다.

Scheduling Criteria

CPU Utilization

• CPU를 최대한 바쁘게, 효율적으로 사용하는 정도. 성능적인 측면에서 최대화 하는 것이 좋다.

Throughput

• 단위 시간당 작업 수행량. Response Time과 연관이 있지만 다르다. Throughput 역시 최대화하는 것이 좋고, 이를 위해서 Overhead를 최소화하거나 CPU나 메모리 같은 자원을 효율적으로 사용하는 방법이 있다.

Turnaround Time

• 프로세스가 처음 도착해서 끝나기까지 걸리는 시간. 대기 시간과 CPU 수행 시간, 입출력 작업 시간이 모두 포함된 시간이다. 성능적 측면에서 최소화하는 것이 좋다.

Waiting Time

• 프로세스가 Ready Queue에 대기하는 시간의 합. Waiting Time은 Turnaround Time과 Response Time에도 영향을 준다. 따라서 줄이는 것이 좋다.

Response Time

• 명령이 들어오고 나서 첫 번째 응답이 생성될 때까지의 시간. Response Time은 User Experience에 직접적인 영향을 끼친다. 최소화하는 것이 성능 측면에서 좋다.

Fairness

• CPU를 공평한 방식으로 공유하는 정도. 위의 기준들과는 다르게 정해진 기준이 없다. Fairness를 추구한다고 해서 모든 프로세스에 CPU 권한을 균등분배하는 것이 아니라, 권한이나 Running 상태를 한 번도 못 받는 프로세스가 없도록 하는 것이다.

Three Separate Functions

Long-Term Scheduling

• 어떤 프로그램이 Admit될 지, 즉 New 상태의 프로그램 중에서 Ready나 Blocked 상태로 바뀔 프로그램이 무엇인지를 결정하는 것이다.

Mid-Term Scheduling

• 어떤 프로세스가 Swapping될 지, 즉 Blocked 상태의 프로세스 중에서 Blocked/Suspend 상태로 바뀔 프로세스가 무엇인지를 결정하는 것이다.

Short-Term Scheduling

• 어떤 프로세스가 Dispatch될 지, 즉 Ready 상태의 프로세스 중에서 Running 상태로 바뀔 프로세스가 무엇인지를 결정하는 것이다. 가장 빈번하게 발생하고 Ready Queue에서 발생하여 셋 중에 가장 중요하다고 할 수 있다.

Terminology for Scheduling

Non-Preemptive(Cooperative) Scheduling

• 프로세스가 Running 상태가 되면 CPU를 자발적으로 해제할 때까지 CPU를 사용한다.
  • ex) 종료, 입출력을 통한 자체 차단, System Call 등
    ⠀⠀
• 장점: Context Switch Overhead가 적다.
• 단점: 우선순위가 자주 바뀌거나 Average Response Time이 길어진다.

Preemptive Scheduling

• CPU는 실행 중인 프로세스와 관계없이 다른 프로세스에 Preemptive 될 수 있다.
  ⠀⠀
• OS Kernel 설계에 영향을 미칠 수 있다.
  ⠀⠀
• 장점: 유연성, 적응성, 성능이 증가한다.
• 단점: Context Switch Overhead가 크다.

Workload Assumptions

1. 모든 작업의 수행 시간은 동일하다.
2. 모든 작업은 같은 시간에 도착한다.
3. 모든 작업은 CPU만 사용하여 수행된다.
4. 모든 작업의 수행 시간을 알고 있다.
5. 모든 작업은 중단 없이 진행된다.

Scheduling Metrics: Turnaround Time

First In, First Out (FIFO)

• Example
  • 프로세스가 도착한 순서는 A → B → C 이지만 모두 $t=0$일 때 도착하였다.
  • 모든 프로세스는 10초의 Runtime을 가진다.

$Average$⠀$Turnaround$⠀$Time =$ $\frac{10 + 20 + 30}{3}$ $= 20$ $sec$

If Runtime Is Different

• 1번 가정이 만족하지 않을 때를 고려해보면 다음과 같은 경우가 나올 수 있다.
  ⠀⠀
• Example
  • 프로세스가 도착한 순서는 A → B → C 이지만 모두 $t=0$일 때 도착하였다.
  • A의 Runtime은 100초이고 B, C의 Runtime은 10초이다.

$Average$⠀$Turnaround$⠀$Time =$ $\frac{100 + 110 + 120}{3}$ $= 110$ $sec$

Shortest Job First (SJF)

• Convoy Effect - Runtime이 짧은 프로세스는 긴 프로세스의 뒤에 있을 때 대기 시간이 증가한다.
  ⠀⠀
• Shortest Job First(SJF) - Convoy Effect를 해결하기 위해 등장한 알고리즘.
  • 말그대로 Runtime이 짧은 프로세스부터 순차적으로 수행.
  • Non-Preemptive Scheduler
    ⠀⠀
• Example
  • 프로세스가 도착한 순서는 A → B → C 이지만 모두 $t=0$일 때 도착하였다.
  • A의 Runtime은 100초이고 B, C의 Runtime은 10초이다.

$Average$⠀$Turnaround$⠀$Time =$ $\frac{10 + 20 + 120}{3}$ $= 50$ $sec$

If Arrival Time is Different

• 2번 가정이 만족하지 않을 때를 고려해보면 다음과 같은 경우가 나올 수 있다.
  ⠀⠀
• Example
  • A는 $t=0$일 때 도착하였고 100초의 Runtime을 가진다.
  • B와 C는 B → C의 순서로 둘 다 $t=10$일 때 도착하였고 10초의 Runtime을 가진다.

$Average$⠀$Turnaround$⠀$Time =$ $\frac{10 + (110 - 10) + (120 - 10)}{3}$ $= 103.33$ $sec$

Shortest Time-to-Completion First (STCF)

• Shortest Time-to-Completion First는 SJF에 Preemption이 추가된 Scheduler
  ⠀⠀
• Scheduling은 프로세스의 전체 수행 시간이 아닌 완료까지 남은 시간에 따라 달라진다.
  ⠀⠀
• 여기서는 '수행 중인 작업은 완료될 때까지 멈추지 않는다'는 5번 가정의 내용도 만족하지 않음을 고려한다.
  ⠀⠀
• Example
  • A는 $t=0$일 때 도착하였고 100초의 Runtime을 가진다.
  • B와 C는 B → C의 순서로 둘 다 $t=10$일 때 도착하였고 10초의 Runtime을 가진다.

$Average$⠀$Turnaround$⠀$Time =$ $\frac{(120 - 0) + (20 - 10) + (30 - 10)}{3}$ $= 50$ $sec$

• 이 Scheduler를 사용한다면 긴 프로세스는 오랫동안 수행되지 못하는 Starvation이 발생할 수 있다.
  ⠀⠀
• 그리고 Runtime을 모두 알고 있다는 것 역시 가정이고 Runtime을 예측하는 것은 아주 어렵다.

가중 평균을 통한 프로세스 Runtime 예측 방법은 위와 같다.

Scheduling Metric: Response Time

Round Robin Scheduling

• Time Slicing Scheduling
  • 일정 시간 동안 작업을 실행한 후 작업이 완료될 때까지 실행 대기열의 다음 작업으로 전환한다.
  • 이것은 작업이 완료될 때까지 반복적으로 수행된다.
  • Time Slice의 길이는 Timer Interrupt 기간의 배수여야 한다.
    ⠀⠀
• Round Robin Scheduling은 공평하지만 Turnaround Time의 지표에서는 좋지 않은 성능을 나타낸다.
  ⠀⠀
• Example
  • 프로세스가 도착한 순서는 A → B → C 이지만 모두 $t=0$일 때 도착하였다.
  • 모든 프로세스는 5초의 Runtime을 가진다.

$Average$⠀$Turnaound$⠀$Time =$ $\frac{5 + 10 + 15}{3}$ $= 10$ $sec$

$Average$⠀$Response$⠀$Time =$ $\frac{0 + 5 + 10}{3}$ $= 5$ $sec$

$Average$⠀$Turnaound$⠀$Time =$ $\frac{13 + 14 + 15}{3}$ $= 14$ $sec$

$Average$⠀$Response$⠀$Time =$ $\frac{0 + 1 + 2}{3}$ $= 1$ $sec$

Length Of The Time Slice Is Critical

• Shorter Time Slice
  • Response Time 감소
  • Context Switch의 비용 증가
    ⠀⠀
• Longer Time Slice
  • Context Switch의 비용 감소
  • Response Time 증가
    ⠀⠀
• Time Slice 시간을 결정하는 것은 Trade-Off 문제를 고려해야 한다.

Incoporating I/O

• '모든 작업은 CPU만 사용하여 수행된다'는 3번 가정이 만족하지 않을 때를 고려해보면 다음과 같은 경우가 나올 수 있다.
  ⠀⠀
• Example
  • A와 B는 50ms의 CPU Runtime을 가진다.
  • A는 10ms마다 10ms의 입출력 작업이 발생한다.
  • B는 입출력 작업없이 CPU 작업만 50ms 수행된다.
  • Scheduler는 A → B의 순서로 수행한다.

Multi-Programming을 통해 CPU가 작업을 수행하지 않는 동안 B를 수행시켜 CPU Utilization을 높였다.