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을 한 장에 닫습니다.
기술사 답안 포인트
관련 용어
관련 토픽
CA/OS
교착상태
서로 가진 자원을 기다리며 멈추는 교착의 네 조건과 예방·회피·탐지·복구를 가르고, 은행가 알고리즘의 안전 상태를 정리합니다.
CA/OS
세마포어(Semaphore) - 모니터/뮤텍스와 비교
세마포어(Semaphore): 에츠허르 다익스트라(Dijkstra, 1965)가 제안한 동기화 도구 — 정수 변수 S와 이를 원자적으로 조작하는 두 연산 P(wait, down)·V(signal, up)로 임계 구역 상호 배제와 프로세스 간 실행 순서
CA/OS
우선순위 역전(Priority Inversion, 해결기법 포함)
우선순위 역전(Priority Inversion): 우선순위 기반 선점 스케줄링에서 높은 우선순위 태스크(H)가 낮은 우선순위 태스크(L)가 가진 공유 자원(락)을 기다리는 동안, 중간 우선순위 태스크(M)가 L을 선점해 실행되면서 결과적으로 H가 M