[운영체제] 프로세스 스케줄링

Process Scheduling

---

• 실질적인 스케줄링 객체는 스레드이다. (리눅스는 스레드 단위로 스케줄링을 함)
• 왜 프로세스 스케줄링이 필요하지?
  1. CPU 활용을 최대한으로 하기 위해서 (CPU utilization)
  2. 실행시간을 공평하게 분배하기 위해 (Fairness)
  3. 프로세스의 빠른 응답을 위해 (Responsiveness)

 

CPU Scheduler

---

• CPU가 비가동 상태일 때 CPU 스케줄러에 의해서 ready 큐로부터 한 개의 프로세스를 선택한다.
• 스케줄링 결정을 해야 할 때
  1. 프로세스가 running state에서 waiting state로 바뀔 때 (CPU가 I/O 상태로 바뀔 때)
  2. 프로세스가 running state에서 ready state로 바뀔 때 (프로세스가 running 큐에서 ready 큐로 들어가는 게 아님. 그저 프로세스의 상태가 바뀐 것임)
  3. 프로세스가 waiting state에서 ready state로 바뀔 때
  4. 프로세스가 종료할 때
• Nonpreemtive 스케줄러일 때, 1번과 4번인 경우에만 스케줄링을 한다.

 

Preemtive Scheduling

---

• Issues
  1. Race condition의 잠재적 원인
     • 한 프로세스가 공유된 데이터를 업데이트하는 도중에 preempt 된다면?
       
       • 다른 프로세스가 모순된 데이터를 읽는다.
  2. 커널 디자인에 대한 복잡성
     • System call을 핸들링하는 도중에 preempted 된다면?
       • 커널 자료구조가 모순된 상태로 빠질 수 있다.

 

Scheduling Criteria

---

• CPU utilization
  • 의미 있는 작업으로 CPU를 100% 사용한다.
  • 실제로는 30~40%밖에 되지 않음.
• Throughput
  • 시간당 처리되는 작업의 개수를 최대화한다.
• Turnaround time
  
  • 작업이 요청되고 완료되기까지의 시간을 최소화한다.
• Waiting time
  • Ready 큐 안에서 소요되는 시간의 총합을 최소화한다.
• Response time
  • 작업이 요청되고 첫 번째 응답이 올 때까지의 시간을 최소화한다.
• Fairness
  • 각 프로세스가 CPU를 평등하게 분배하도록 한다.

 

FCFS Scheduling (First-come, first-served)

---

• 먼저 온 프로세스를 먼저 처리한다.
• Nonpreemptive 하다. (스케줄링 동안에 강제로 preempt 하지 않는다.)
• 간단하고 구현하기 쉽다.
• 단점
  • Convoy effect가 발생할 수 있다.
    • Burst time이 매우 긴 프로세스가 오면 나중에 오는 프로세스가 점점 쌓이는 현상

FCFS 스케줄링의 예제

프로세스의 순서를 바꿨을 때의 FCFS 스케줄링. Average waiting time이 3ms로 줄었다.

 

SJF Scheduling (Shortest-job first)

---

• CPU burst가 가장 짧은 프로세스부터 먼저 처리한다.
• 최소의 평균 waiting time을 가지는데 최적화된 알고리즘이다.
• 대개 long-term scheduling 상황에서 사용된다.
• Short-term scheduling 상황에서는 프로그램을 실행하기 전이기 때문에 CPU burst의 길이를 알기 어렵다. 따라서 Approximation을 사용한다.

SJF 스케줄링의 예제

• SJF는 preemtive일 수도 있고, nonpreemtive일 수도 있다.
  • 만약 preemtive상태일 때, 새로운 프로세스가 ready 큐로 들어오고, 현재 프로세스의 길이보다 짧다면 현재 프로세스를 preempt 한다.
• Shortest-remaining-time-first scheduling (Preemptive 한 SJF 스케줄링)

Shortest-remaining-time-first 스케줄링 예제

 

Priority Scheduling

---

• 각 프로세스마다 우선순위가 할당되고, 스케줄러는 가장 높은 우선순위의 프로세스부터 선택한다.
• SJF 스케줄링은 priority 스케줄링의 특별한 예이다.
  • CPU burst가 짧을수록 우선순위가 높아진다.
• FCFS 스케줄링은 모든 프로세스의 우선순위가 동일한 priority 스케줄링의 특별한 예이다.

Priority 스케줄링의 예. SJF처럼 보일 수 있지만, P4를 보면 priority가 5인 것을 확인할 수 있다.

 

Starvation Problem

---

• Priority 스케줄링의 문제 (SJF, FCFS 스케줄링 포함)
  • Starvation
    • 우선순위가 낮은 프로세스가 절대로 스케줄링되지 않을 가능성이 있는 문제
    • 우선순위가 높은 프로세스가 계속해서 들어오면 우선순위가 낮은 프로세스는 실행되지 않는다.
• Solution
  • Aging policy
    • 시간이 지나면서 점진적으로 프로세스의 우선순위를 증가시킨다.

 

Round-Robin Scheduling

---

• Time-sharing 시스템을 위해 고안되었다.
• FCFS와 유사하지만, preemption이 추가되었다.
  • FCFS 스케줄링은 동등한 우선순위를 가지고 있는 nonpreemptive 한 round-robin 스케줄링이라고 할 수 있다.
• Time quantum의 개념이 추가되었다.
• Ready 큐를 FIFO로 생각하고, 새로운 프로세스는 큐의 tail에 추가된다.

Round-Robin 스케줄링의 예

• Time quantum이 매우 길다면(무한하다면), FCFS 스케줄링이다.
  • Nonpreemptive 하다고 할 수 있다. 따라서 평균 waiting time이 optimal하지 않다.

• Time quantum이 매우 짧다면 CPU burst동안 context switch의 비중이 너무 많아져 오버헤드가 증가한다.
  • 이상적으로 Round-robin의 time quantum은 context switch time보다 충분히 길어야 한다.