[OS] Scheduling

Basic Concepts

• 멀티프로그래밍의 목적
  • 다수의 프로세스가 계속 돌아가게하는 것
  • CPU utilization을 최대화 하는것
• CPU Bound & I/O Bound
  • CPU Bound는 CPU burst가 크다, I/O Bound는 그 반대.
  • CPU Bound는 I/O Bound의 경우 보다 적게 일어난다.
  • CPU burst는 실제로 CPU가 동작하는 시간이고, I/O burst는 입력을 기다리는 시간이다.
• CPU scheduler
  • Ready 상태의 프로세스 중, CPU를 할당해주는 것.
  • Ready 상태의 프로세스 대기열은 Priority Queue로 생성한다.
• Preemptive & Non-preemptive
  • Preemptive scheduling은 선점하고 있는 프로세스 쫓아 내고 CPU의 자원을 선점 할 수 있고, 우선 순위에 따라서 제공된다. 아래의 모든 일련 과정을 거친다.
  • Non-preemptive sheduling은 interrupt와 exit에서만 스케줄링이 필요하다. 즉 종료되거나 자발적인 I/O request에 의해 대기할 때 까지 실행된다. → scheduler 호출 빈도가 낮고 Context switching overhead가 적다.
  • 대부분 시분할 선점형 스케줄링을 사용하며, 비선점의 경우 작업이 끝날 때 까지 실행되기에 멀티프로세스 환경에서 응답성을 기대할 수 없다.
  
• Dispatcher
  • Process에게 CPU를 할당해주는 모듈
  • running상태를 ready or wait로 돌리면서 Context Switching을 해준다.
  • 유저모드로의 스위칭을 해준다.
  • jumping to the proper location to resume the user program
  • scheduler는 선택. Dispatcher는 행동.
  • Dispatcher latency - PCB0를 저장하고, PCB1을 로드하는 시간.

Scheduling Criteria

• CPU utilization : CPU가 얼마나 바쁘게 움직이는지
• Throughput : 얼마나 많은 프로세스를 완료했는지
• Turnaround time : 하나의 프로세스가 종료까지 얼마나 시간이 걸리는지
• Waiting time : 프로세스가 Ready Queue에서 대기 시간이 얼마인지
• Response time : 얼마나 빠르게 반응하는지(ex UI)

Scheduling Algorithms

• Ready Queue에 있는 프로세스 중 어떤 프로세스에게 CPU를 할당해줄것인가?
  • RR : Round - Robin 시분할해서 사용.
  • Priority-based : 다음 프로세스에 우선순위로 선택 하는 법
  • MLQ : Queue를 여러개 쓴다.
  • MLFQ : 다양한 큐를 feedback하며 프로세스가 여러 큐를 옮겨 감
  • FCFS : 먼저 요청한 프로세스, 먼저 할당해준다.
• Convoy Effect
  • 뒤에 I/O-bound가 CPU-bound 하나에 막혀있는 경우. FCFS 사용할 경우 빈번히 발생.
  • SJF로 짧은 업무부터 우선 할당한다.
• SJF
  • CPU burst를 측정해서 어떤게 짧은 업무인지 확인 할 방법이 없다.
  • 과거에 썼던 기록을 토대로 지수평균법을 사용해 예측을 한다.
• SRTF
  • 선점형 SJF 알고리즘
  • shortest-Remaining-Time-First: Preemptive SJF scheduling
  • 새로 도착한 프로세스가, 현재 동작하고 있는 프로세스보다 짧으면 선점해준다. SJF는 기다려줌
• RR Scheduling
  • preemptive FCFS with a time quantum
  • Circle-Queue사용
  • 쪼갠시간 보다 더 빨리 끝나면 자동으로 나오고, 더 길다면 interrupt가 일어나서 빠져나온다.
  • 다양한 알고리즘이랑 섞어쓴다.
  • 적절한 time quantum을 찾아야한다.
• Priority-base Scheduling
  • 우선순위가 높은 프로세스에게 자원을 우선 할당해줌.
  • starvation problem 발생 → aging으로 해결
  • RR과 combine하여 활용
• Multi-Level Queue(MLQ) Scheduling
• 
• Multi-Level Feedback Queue(MLFQ) Scheduling
• 

Thread Scheduling

• 현대의 운영 환경
  • kernel threads만 관리해주면된다.
  • user threads는 라이브러리가 관리해준다.
• Scheduling in Real-Time Operating System
  • Soft Realtime
  • Hard Realtime