CPU Scheduling

• 다중 프로세서 운영체제 설계의 핵심 : CPU 이용률 최대화
  • 항상 실행 중인 프로세스를 가지게 하는 것
  • Ex) 어떤 프로세스가 대기해야할 경우, 운영체제는 CPU를 해당 프로세스로부터 회수 + 다른 프로세스에 할당

CPU-I/O Burst Cycle

프로세스의 실행 : CPU Burst → I/O Burst → CPU Burst → I/O Burst → ♻️CYCLE

CPU Scheduler

Ready Queue에 있는 프로세스(실행 준비가 되어있는 Ready 상태) 중에 하나를 선택해 CPU 할당

• Q. Appropriate Ready Queue?
  • A. 우선순위 큐, 트리 등 FIFO 방식의 큐가 아니어도 가능

Dispatcher

CPU의 제어권을 CPU Scheduler가 선택한 프로세스에게 넘겨주는 모듈 (Context Switch; 문맥 교환)

Preemptive & Nonpreemptive Scheduling

• 선점 스케줄링 (Preemptive) : 현재 수행 중인 프로세스보다 더 높은 우선 순위 프로세스가 발생되면, 현 실행 프로세스로부터 강제로 CPU를 회수하는 것 (강제)
• 비선점 스케쥴링 (Nonpreemptive) : CPU가 한 프로세스에 할당되면 프로세스가 종료하든지, 또는 대기 상태로 전환해 CPU를 방출할 때까지 점유 (자진 반납)

• CPU 스케쥴링이 필요한 프로세스의 상태 변화
  1. I/O 발생 Running -> Blocked
  2. Interrupt 발생 Running -> Ready
  3. I/O 종료 Blocked -> Ready
  4. Terminate

Scheduling Criteria

CPU Scheduling Algorithm 선택(비교) 기준

	CPU Utilization	Throughput	Turnaround Time	Waiting Time	Response Time
좋은 알고리즘	↑	↑	↓	↓	↓

• CPU Utilization (CPU 이용률) : 특정 기간(or SNAPSHOT)에서의 CPU 이용률
• Throughput (처리량) : 단위 시간 당 완료된 프로세스의 개수
• Turnaround Time (총 처리 시간) : 특정 프로세스를 실행하기 위해 소요되는 시간 (완료 시간-시작 시간)
• Waiting Time (대기 시간) : 프로세스가 ready queue에서 대기하는 시간
• Response Time (응답 시간) : 하나의 request가 제출된 후, 첫번쨰 response가 나오기까지의 시간

Scheduling Algorithm

공통 질문 : Ready Queue에 있는 어느 프로세스에 CPU를 할당할 것인가?

FCFS

선입 선처리 (First Come First Served)

• CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받음
• 비선점형 알고리즘 : CPU가 한 프로세스에 할당되면, 프로세스가 종료하거나 I/O 처리를 요구하여 CPU를 방출할 때까지 CPU를 점유
• 단점 : 대기 시간이 길 수 있음 (대화형 시스템이 부적절)

SJF

최단 작업 우선 (Shortest Job First)

• 처리 시간이 짧은(CPU burst time이 가장 작은) 프로세스부터 CPU 할당
• Optimal : 주어진 프로세스들에 대해 minimum average waiting time을 보장
• 선점형/비선점형
• 단점 : 프로세스 별 CPU burst time을 직접 알 수 없어 예측(과거의 CPU burst time를 이용)하여 스케쥴링을 해야 함

Priority Scheduling

우선순위 스케줄링

• 각 프로세스 당 우선순위를 정해, CPU를 가장 높은 우선순위를 가진 프로세스에 할당
• 선점형/비선점형
• 단점 : 기아 상태(starvation) - 높은 우선순위의 프로세스들이 꾸준히 들어와서 낮은 우선순위의 프로세스들이 CPU를 얻지 못하는 상태
  • 해결 방법 : 노화(aging) - 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 것

Round Robin (RR)

FCFS와 유사! BUT 시스템이 프로세스들 사이를 옮겨 다닐 수 있도록 선점(preempted)이 추가됨

• 시간 할당량(time quantum) : 각 프로세스는 동일한 크기의 할당 시간을 가짐
• 할당 시간이 지나면 프로세스는 선점(preempted)당하고 ready queue의 제일 뒤로 이동
• n개의 프로세스가 ready queue에 있고, 할당 시간이 q time unit인 경우
  • 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻음
  • 어떤 프로세스도 (n-1) q time unit 이상 기다리지 않음

Multilevel Queue

Priority + RR → Multilevel Queue

• Ready queue를 여러 개로 분할 : foreground(interactive; RR Algorithm) + background(batch - no human interaciton, FCFS Algorithm)
• 큐에 대한 스케줄링이 필요
  • Fixed priority scheduling : foreground~backgroun; 기아 상태(starvation) 발생 가능
  • Time slice : 각 큐에 CPU time을 적절한 비율로 할당

Multilevel Feedback Queue

Multilevel Queue + 프로세스가 큐들 사이를 이동하는 것 허용 (Feedback) → Multilevel Feedback Queue

• aging을 이와 같은 방식으로 구현 가능
• 단점 : 스케줄러 동작을 위해 모든 파라미터를 선정해야 해서 복잡
  • 파라미터 : queue의 수, 각 queue의 scheduling algorithm, process를 상위/하위 큐로 보내는 기준, 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

Scheduling Type

Multiple-Processor Scheduling

CPU가 여러 개 -> 여러 thread 병렬 처리 가능 (부하 공유; load sharing) -> BUT 스케줄링 복잡

• Load Sharing
  • 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 매커니즘 필요
  • 별개의 큐를 두는 방법 vs. 공동 큐를 사용하는 방법

• 접근 방식
  • Symmetric Multiprocessing (SMP)
    • 각 프로세서가 각자 알아서 스케줄링 결정
  • Asymmetric Multiprocessing
    • 하나의 프로세스가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

Real-Time Scheduling

• 구분 방식
  • Hard real-time systems
    • 정해진 시간 안에 task를 반드시 끝내도록 보장
  • Soft real-time systems
    • 중요한 실시간 프로세스가 스케줄되는 시점에 대해 아무런 보장을 하지 않음 (일반 프로세스에 비해 높은 priority만 보장)

Thread Scheduling

• Local Scheduling
  • User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
• Global Scheduling
  • Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정

Algorithm Evaluation

1. Queueing models
   • 확률 분포로 주어지는 arrival rate와 service rate등을 통해 각종 performance index 값을 계산
2. Implementation & Measurement
   • 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교
3. Simulation
   • 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교