PE Notes · CA/OS
OS 스케줄링 알고리즘(SJF/SRT/SSTF/SLTF, RM vs EDF)
스케줄링(Scheduling): 한정된 자원(CPU·디스크 등)을 여러 요청에 어떤 순서로 배정할지 결정하는 OS 기능
스케줄링(Scheduling): 한정된 자원(CPU·디스크 등)을 여러 요청에 어떤 순서로 배정할지 결정하는 OS 기능. 이 토픽의 범위:.
구조와 칸
| 기준 | SJF | SRT |
|---|---|---|
| 선점 | 비선점 | 선점 |
| 평균 대기(위 예) | 7(동시 도착 예) | 6.5(도착 시각 상이 예) |
| 문맥 교환 | 적음 | 많음 |
| 공통 문제 | 실행 시간 예측·기아 | 실행 시간 예측·기아 |
예: 모두 시각 0 도착, 실행 시간 P1 = 6, P2 = 8, P3 = 7, P4 = 3. 순서: P4(03) → P1(39) → P3(916) → P2(1624). 대기 시간: P4 0, P1 3, P3 9, P2 16 → 평균 = 28 ÷ 4 = 7. 비교 FCFS(P1→P2→P3→P4): 0 + 6 + 14 + 21 = 41 ÷ 4 = 10.25.
SJF vs SRT
| 기준 | SSTF | SLTF |
|---|---|---|
| 최적화 대상 | 탐색 시간(실린더 간 이동) | 회전 지연(같은 실린더 내 섹터) |
| 적용 단계 | 실린더 선택 | 실린더 내 섹터 순서 |
| 기아 | 발생 가능 | 거의 없음(한 바퀴 내 처리) |
| 기준 | RM | EDF |
|---|---|---|
| 우선순위 | 정적(주기 짧을수록 높음) | 동적(데드라인 가까울수록 높음) |
| 스케줄 가능 이용률 | ≤ n(2^(1/n) − 1) 충분, RTA로 정확 판정 | ≤ 1 필요충분 |
| 구현 | 단순(고정 우선순위) | 복잡(실행 중 우선순위 재계산) |
| 과부하 시 | 낮은 우선순위 태스크만 실패(예측 가능) | 여러 태스크 연쇄 실패(도미노) |
| 적용 | 상용 RTOS·AUTOSAR | ·연구 |
SJF·SRT 개념: 배치 시스템, 리눅스 CFS·EEVDF는 공정성 기반이지만 짧은 작업 응답성 고려. HDD 스케줄링: SSTF·LOOK 계열, 펌웨어 에서 탐색·회전 통합 최적화. RM: 대부분의 상용 RTOS·AUTOSAR OS(고정 우선순위 선점).
답안은 OS 스케줄링 알고리즘(SJF/SRT/SSTF/SLTF, RM vs EDF)의 정의, 칸, 비교 축을 한 장에 닫습니다.
기술사 답안 포인트
관련 용어
관련 토픽
CA/OS
우선순위 역전(Priority Inversion, 해결기법 포함)
우선순위 역전(Priority Inversion): 우선순위 기반 선점 스케줄링에서 높은 우선순위 태스크(H)가 낮은 우선순위 태스크(L)가 가진 공유 자원(락)을 기다리는 동안, 중간 우선순위 태스크(M)가 L을 선점해 실행되면서 결과적으로 H가 M
CA/OS
스레싱(Thrashing)
스레싱(Thrashing): 프로세스에 할당된 프레임이 작업 집합(Working Set)보다 적어 페이지 폴트가 과도하게 발생하고, CPU가 실제 연산보다 페이지 교체(디스크 I/O)에 대부분의 시간을 쓰는 상태
CA/OS
세마포어(Semaphore) - 모니터/뮤텍스와 비교
세마포어(Semaphore): 에츠허르 다익스트라(Dijkstra, 1965)가 제안한 동기화 도구 — 정수 변수 S와 이를 원자적으로 조작하는 두 연산 P(wait, down)·V(signal, up)로 임계 구역 상호 배제와 프로세스 간 실행 순서