PE Notes · CA/OS
OS 스케줄링 알고리즘
준비 큐에서 CPU를 고르는 SJF·SRT와 디스크의 SSTF·SLTF를 가르고, 실시간의 RM과 EDF 이용률 한계를 정리합니다.
준비 큐에 여러 프로세스가 서 있으면, 다음 양자에 누구를 올릴지가 스케줄입니다. 은 달리는 일을 끊고 바꿀 수 있고, 비선점은 그 일이 스스로 놓을 때까지 둡니다. 목표는 이용률·처리량·응답·공정이 한 줄로 서지 않는다는 점을 인정하는 일입니다.
CPU 칸: SJF와 SRT
FCFS는 도착 순입니다. 단순하고 기아는 없으나 긴 일이 짧은 일을 막습니다. 는 버스트가 가장 짧은 일을 고릅니다. 평균 대기가 이론상 최소에 가깝고, 긴 일은 굶을 수 있습니다. 는 남은 시간이 더 짧은 도착이 있으면 선점하는 SJF입니다. 우선순위 스케줄은 기아를 에이징으로 녹입니다. 라운드 로빈은 시간 할당량으로 공정하게 돌아가고, 다단계 피드백은 큐를 여러 층으로 쌓습니다.
| 이름 | 선점 | 고르는 값 |
|---|---|---|
| FCFS | 아니오 | 도착 |
| SJF | 아니오 | 최단 버스트 |
| SRT | 예 | 최단 잔여 |
| RR | 예 | 할당량 |
| 우선순위 | 둘 다 | 순위 |
짧은 일이 중간에 오면 SRT는 긴 일을 내려놓고 짧은 일을 끝낸 뒤 돌아갑니다. 예측이 틀린 버스트는 실측으로 보정합니다.
디스크 칸과 실시간 칸
헤드를 움직이는 시간은 CPU 버스트가 아닙니다. 는 지금 헤드에서 가장 가까운 트랙을 먼저 갑니다. 처리량은 오르고 가장자리는 굶을 수 있습니다. 는 회전 지연이 짧은 섹터를 고릅니다. SCAN은 엘리베이터처럼 한 방향으로 쓸고, C-SCAN은 되돌아올 때 서비스를 하지 않습니다. CPU의 SJF와 디스크의 SSTF는 “가장 짧은 것”이라는 말만 같고 대상이 다릅니다.
실시간은 기한을 지킵니다. 은 주기가 짧을수록 고정 우선순위가 높습니다. 이용률 상한은 n(2^(1/n)−1)로, 태스크가 많아지면 약 69%에 수렴합니다. 는 가장 가까운 기한을 동적으로 고르고, 이론 상한은 100%입니다. 주기가 고정되면 RM이 단순하고, 비주기가 섞이면 EDF가 맞습니다. 우선순위 역전 노트는 잠금이 이 순서를 깨는 경우입니다.
답안은 CPU·디스크·실시간을 세 표로 가르고, SJF≠SSTF, RM 공식과 EDF 1.0을 한 장에 닫습니다.