06. Process Scheduling(2)

Scheduling Criteria

• CPU utilzation
  • CPU를 바쁘게 유지시킨다.
• Throughput
  • 단위 시간당 완료된 프로세스의 개수
• Turnarount time
  • 프로세스의 제출 시간과 완료 시간의 간격
• Waiting time
  • ready queue에서 대기하면서 보낸 시간의 합
• Response time
  • 응답이 시작되는 데까지 걸리는 시간

---

FCFS/FIFO

• CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는 스케줄링 알고리즘.
• Typically, non-preemptive(비선점형)
• no starvation
• FIFO(선입선출)큐로 쉽게 관리할 수 있다.

• Problem : Convoy effect(호위 효과)
• 모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것.
• 이 효과는 CPU와 I/O device 이용률이 저하되는 결과를 낳는다.

---

Preemptive Scheduling

• Non-preemptive scheduling(비선점형)

  • 스케줄러는 실행중인 job이 자발적으로 CPU를 양보할때까지 기다린다.
  • job should be cooperative

• Preemptive scheduling(선점형)

  • 스케줄러가 작업을 중단하고 강제로 context switching할 수 있다.

---

SJF

• Shortest Job First
  • 가장 작은 CPU burst길이를 할당한다.
  • 최적 평균 wating time을 보장한다.
  • Non-preemptive(비선점형)
  • Priority scheduling
    • Priority = the inverse of preidicated next CPU burst time

• Can potentially starve
• 다음 CPU burst의 길이를 알 수 없다.
  • 그 값을 예측할수는 있다.
  • 이전의 CPU burst들의 길이를 지수평균한 것으로 예측.

---

Starvation

• 다른 job이 필요한 resource를 계속 보유하고 있기 때문에 작업이 진행되지 못하는 상황
  • The resource could be the CPU or a lock
• 잘못된 스케줄링 policy는 starvation을 야기시킨다.
  • 우선순위가 높은 작업이 끝없이 공급되는 경우 우선순위가 낮은 작업이 실행되지 않을 수 있다.

---

STCF

• Shortest Time-to-Completion First
• SJF의 preemptive version
• 새로운 job의 runtime이 현재 job의 runtime보다 적으면, 선점한다.

---

RR

• Round Robin
• 시스템이 프로세스들 사이를 옮겨 다닐 수 있도록 선점이 추가된다.
• 각 job은 timeslice라고 하는 작은 단위의 시간 또는 scheduling quantum이 있다.
• 각 job을 timeslice까지만 수행하고 next job으로 switch한다.

• Preemptive
• No starvation
• Improve response time: great for time-sharing
• Waiting time, turnaround time에 대해선 안좋을 수 있다.

---

Priority Scheduling

• 각 job은 우선순를 가진다.
• CPU는 가장 높은 priority를 가진 job에 할당된다.
  • Can be preemptive or non-preemptive
• SJF 알고리즘은 단순한 priority algorithm이다.

• CPU burst가 클수록 우선순위가 낮으며, 그 역도 성립한다.
• Starvation problem
  • priority scheduling algorithm의 주요 문제이다.
  • 실행 준비는 되어 있으나 낮은 priority를 가진 프로세스들이 CPU를 무한히 대기하는 경우가 생긴다.(높은 priority를 가진 프로세스들이 꾸준히 들어오는 경우)
  • Solution: aging or priority boosting
  • aging은 오래동안 시스템에서 대기하는 프로세스들의 priority를 점진적으로 증가시킨다.

---

Priority Inversion

• 시스템에 여러 작업에서 동시에 사용할 수 없는 리소스가 있다고 가정하자.
• low-priority task가 resource를 가지고 있다.
• high-priority task도 그 리소스를 필요로 한다.
  • low-priority task가 resource를 해제할 때까지 blocked된다.
• intermediate-priority task이 실행할 준비가 됨.
• intermediate-priority task는 high-priority task를 preept한다.

• 우선순위가 가장 높은 Bus management task을 task1이라 하고, 우선순위가 가장 낮은 Meteorological data gathering task을 task3, 중간 우선순위를 task2라 하자.
• 스케쥴러에 의해 task1이 수행된다.
• task1은 task3이 갖고 있는 resource를 획득하기 위해 기다린다.(waiting)
• 스케줄러에 의해 다시 task3이 수행됨.

• 이 때 resource와 관련 없는 중간 우선순위를 가진 task2가 task3보다 우선순위가 높아 스케줄러에 의해 실행된다.
• 그러면서 task3의 완료가 뒤로 밀리며, 가장 높은 우선순위를 가진 task1이 결국 가장 늦게 실행됨(priority inversion)

기본적으로, nonsharable resource와 priority-based scheduling policy를 사용하는 모든 system은 이러한 시나리오에 취약하다.

---

Solution for Priority Inversion

• Priority inheritance protocol(PIP)
  • 우선순위가 높은 작업은 리소스를 가지고 있는 우선순위가 낮은 작업에게 priority를 기부한다.
  • 리소스를 보유하고 있는 작업의 우선순위를 일시적으로 높인다.
    • 리소스를 해제하면 원래 우선순위로 돌아가야 한다.
• Priority ceiling protocol(PCP)
  • 우선순위가 낮은 스레드의 priority는 resource를 얻는 즉시 priority를 높인다.
  • priority의 상한값은 미리 정해져야 한다.

---