• New, Running, Waiting, Ready, Termiate → 상태에 따라 CPU가 큐에 넣어 관리
• CPU, I/O burst: CPU가 alternate하는 가운데 어떤 부분을 더 많이 점유하는가에 따라서 intensive 부분이 달라짐
• CPU 스케줄러는 프로세스의 어떤 상태를 컨트롤할 수 있느냐에 따라 비선점형/선점형 스케줄러로 구별
• 스케줄링 알고리즘을 판단하는 기준 중 Waiting time → throughput, turnaround 모두 영향

CPU 스케줄링 알고리즘

FCFS

• First Come First Served
• 선착순 알고리즘

각 프로세스가 기다린 시간이 대기 시간이 된다. 어떻게 정렬하느냐에 따라서 평균 대기 시간이 매우 달라지게 된다!

• Contoy effect: burst time이 긴 프로세스부터 처리하게 되면 이후 프로세스가 대기 시간에 있어서 비용이 크게 됨. 응답성 저하의 주요 원인

SJF

• Shortest-Job-First
• 더 짧은 작업부터 큐에 넣는 스케줄링 알고리즘
• optimal한 알고리즘 → 각 작업의 종료 시간을 사전에 알고 있어야 한다는 조건
• 프로세스가 ready 큐에 계속 들어 있는 게 아닐 수 있음

Shortest-remaining-time-first

• 도착 시간 및 선점(preemptive)을 고려한 컨셉
  
• 해당 시점에서 "앞으로 남은 시점"이 가장 짧은 프로세스를 큐에 먼저 삽입하는 알고리즘

선점과 비선점의 차이가 매우 크다! 매 순간마다 큐에 들어 있는 프로세스 처리 시간을 비교해서 판단한다!

Priority scheduling

• 우선순위 기반 스케줄링: 각 CPU가 우선순위를 할당받음. 높은 우선순위일 수록 작은 수의 우선순위 할당
• SJF: CPU burst time이 짧을 수록 더 높은 우선순위를 할당받는 알고리즘
• Starvation: 낮은 우선순위 프로세스는 실행되지 않는다는 문제
• Aging: 시간이 지날 수록 남아 있는 낮아 있는 우선순위 프로세스의 우선순위를 점차 높여주기 → 일정 시간 이상 기다리지 않도록 방지하는 방법

Round Robin

• 각 프로세스가 CPU 시간을 점유하는 유닛을 가짐
• 유닛이 끝난 뒤 프로세스가 선점되고 ready 큐 마지막으로 다시 들어감
• time quantum: 스케줄링의 최소 텀 - HW의 타이머 인터럽트가 커널 모드에 진입하도록 인터럽트 실행. quantum마다 스케줄링 여부를 결정하게 됨
• time slice: 한 라운드 내에 프로세스에게 할당된 시간
• performance: (1). large time slice - 컨텍스트 스위칭 주기가 짧음 (2). Small time slice - 응답성이 높지만 낮은 퍼포먼스.
• 타임 슬라이스는 컨텍스트 스위칭에 비해 커야 함. 오버헤드가 매우 높기 때문
• 주어진 타임 슬라이스 안에서 프로세스 실행 시간이 종료된 경우 곧바로 라운드를 넘긴다.

Multilevel Queue

• Ready 큐가 여러 개의 큐로 구성되는 스케줄링 알고리즘
• foregound / background 형태로 분리
• 각 큐마다의 스케줄링 알고리즘 존재
• 스케줄링은 큐 사이에서 이루어짐: Fixed priority scheduling - foreground부터 background까지 동일한 우선순위이기 때문에 starvation 위험. time slice = 각 큐는 서로 다른 시간 할당을 받아서 starvation 문제 해결

Multilevel feedback Queue

• 우선순위 고정 X
• 프로세스: 여러 큐 이동 가능
• 큐의 개수, 각 큐의 스케줄링 알고리즘, 프로세스를 더 높은/낮은 우선순위를 가진 큐로 옮기는 기준 등 고려