선점형 스케줄링 알고리즘
- 한 프로세스가 CPU를 사용 중일 때, 다른 프로세스가 CPU를 강제로 차지할 수 있는 방식
- 프로세스는 특정 조건(예: 타임 슬라이스 종료, 더 높은 우선순위의 프로세스 등장 등)에서 CPU를 선점당할 수 있음
- 컨텍스트 스위칭에 따른 부하가 있을 수 있음
1. 라운드로빈(Round Robin)
- 라운드로빈 스케줄링은 각 프로세스가 동일한 시간 단위(타임 슬라이스) 동안 CPU를 할당받아 실행
- 타임 슬라이스가 끝나면 프로세스는 준비 큐의 끝으로 이동하고 다음 프로세스가 CPU를 할당받음
- 공정성을 보장하며 특히
인터랙티브 시스템에서 자주 사용 - 타임 슬라이스가 너무 짧으면 컨텍스트 스위칭이 빈번해져 오버헤드가 발생할 수 있고 너무 길면 FCFS와 유사해질 수 있음
로드밸랜서에서 트래픽 분산 알고리즘으로 쓰임
2. SRTF(Shortest Remaining Time First)
- SRTF는 남은 실행 시간이 가장 짧은 프로세스를 먼저 실행하는 방식
- 새로운 프로세스가 도작할 때마다 남은 실행 시간이 가장 짧은 프로세스를 선택
- 평균 대기 시간이 최소화됨
- 긴 작업이 계속 뒤로 밀려나 기아(Startvation) 현상이 발생할 수 있음
3. 다단계 큐(Multilevel Queue Scheduling)
- 다단계 큐는 프로세스들을 여러 개의 큐로 나누고 각 큐는 다른 스케줄링 알고리즘을 사용
- 예를 들어, 시스템 프로세스는 높은 우선순위 큐에 사용자 인터랙티브 프로세스는 중간 우선순위 큐에 배치 프로세스는 낮은 우선순위 큐에 배치될 수 있음
- 각 큐 간의 우선순위가 있으며 높은 우선순위 큐가 비어있지 않다면 낮은 우선순위 큐의 프로세스는 실행되지 않음
HW + SW = 1