All
스케줄링 단계
상위단계 스케줄링 (Long-term Scheduling)
•
디스크에 있는 프로세스 중 어떤 프로세스를 메모리(Ready Queue)로 올릴지 결정
•
실행할 프로세스의 수를 조절하여 CPU 및 시스템의 부하를 관리
중간단계 스케줄링 (Medium-term Scheduling)
•
메모리 관리 기법 중 스와핑(Swapping)을 통해 일시적으로 실행 중인 프로세스를 메모리에서 제거(중단)하고 다시 실행할 프로세스를 선택
•
CPU가 과부하 상태일 때 메모리 점유를 줄이기 위한 목적
하위단계 스케줄링 (Short-term Scheduling)
•
CPU를 사용할 프로세스를 선택하여 실행하는 단계
•
실행 중인 프로세스가 종료되거나 인터럽트가 발생할 때 새로운 프로세스를 선택
스케줄링 목표
•
공정성(Fairness): 모든 프로세스가 공정하게 CPU를 할당받도록 함
•
균형: 시스템 자원이 충분히 활용될 수 있게 함
운영체제의 유형에 따른 스케줄링 목표
•
일괄처리 운영체제 : 처리량 극대화, 반환 시간 최소화, CPU 활용의 극대화
•
시분할 운영체제 : 빠른 응답시간, 과다한 대기시간 방지
•
실시간 운영체제: 처리기한 맞춤
스케줄링 정책
선점 스케줄링 (Preemptive Scheduling)
•
실행 중인 프로세스에 인터럽트를 걸어 CPU를 다른 프로세스에 할당할 수 있는 방식.
•
운영체제가 우선순위가 높은 프로세스를 실행하기 위해 현재 실행 중인 프로세스를 중단할 수 있음.
•
SRT, RR, 다단계 피드백 큐
비선점 스케줄링 (Non-preemptive Scheduling)
•
실행 중인 프로세스가 스스로 종료되거나 I/O 작업을 수행할 때까지 CPU를 계속 점유하는 방식.
•
실행 중인 프로세스를 중간에 강제로 중단할 수 없음.
•
FCFS, SJF, HRN..
문맥(Context)
•
현재 실행 중인 프로세스의 CPU 레지스터, 프로그램 카운터, 스택 정보 등의 상태.
•
프로세스가 실행을 멈추고 다시 실행될 때 이전 상태를 복원할 수 있도록 관리됨.
Context Switching (문맥 교환)
•
CPU가 실행 중인 프로세스를 변경할 때 발생하는 과정으로, 이전 프로세스의 문맥을 저장하고 새로운 프로세스의 문맥을 복원하는 작업.
•
오버헤드(Overhead)가 발생하여 너무 잦은 Context Switching은 성능 저하를 유발할 수 있음.
스케줄링 평가 기준
평균 대기 시간(Average Waiting Time)
•
프로세스가 CPU를 할당받기까지 준비 큐에서 대기한 총 시간의 평균값
•
평균 반환 시간(Average Turnaround Time)
•
프로세스가 처리 완료되기까지 걸린 총 시간(대기 시간 + 실행 시간)
•
주요 스케줄링 알고리즘
1. FCFS (First Come First Serve) - 선입선출
•
준비 큐에 도착한 순서대로 CPU를 할당하는 방식 (비선점)
•
단점: 실행 시간이 긴 프로세스가 먼저 도착하면 기다리는 프로세스의 대기 시간이 증가
도착 순서: P1(8ms), P2(4ms), P3(2ms)
실행 순서: P1 → P2 → P3
2. SJF (Shortest Job First) - 최단 작업 우선
•
실행 시간이 가장 짧은 프로세스를 먼저 실행하는 방식 (비선점)
•
일괄처리 환경에서 구현하기 쉬우나, 실행 시간이 긴 프로세스는 무한정 대기할 수도 있음
실행 순서: P3(2ms) → P2(4ms) → P1(8ms)
. SRT (Shortest Remaining Time) - 최단 잔여 시간 우선
•
SJF의 선점형 버전으로, 남은 실행 시간이 가장 짧은 프로세스를 우선 실행
•
새로운 프로세스가 도착하면 실행 중인 프로세스보다 실행 시간이 짧으면 교체됨
•
SJF보다 평균대기시간이나 평균반환시간에서 효율적이나 SJF 보다 오버헤드가 큼
실행 순서: P3(도착) → P2(남은 시간 짧음, 교체) → P1
4. RR (Round Robin) - 라운드 로빈
•
각 프로세스에 일정한 **시간 할당량(Time Quantum)**을 적용하여 실행 (선점)
•
Time Quantum이 너무 작으면 Context Switching이 빈번하게 발생하여 성능 저하
5. HRN (Highest Response Ratio Next) - 최고 응답 비율 우선
•
응답 비율(Response Ratio)이 가장 높은 프로세스를 우선 실행 (비선점).
•
•
실행 시간이 짧은 프로세스와 오래 기다린 프로세스를 균형 있게 실행 가능.
대기 시간 10ms, 실행 시간 2ms → 응답 비율 = (10+2)/2 = 6 (높은 값이 우선)
6. 다단계 피드백 큐 (Multilevel Feedback Queue)
•
여러 개의 우선순위 큐를 사용하여 프로세스를 관리 (선점).
•
처음에는 높은 우선순위의 큐에서 실행하며, 일정 시간을 초과하면 낮은 우선순위 큐로 이동.
•
I/O 중심 프로세스(짧은 작업)가 CPU 중심 프로세스(긴 작업)보다 우선권을 갖도록 설계.
1.
짧은 작업 → 높은 우선순위 큐에서 실행.
2.
오래 실행된 작업 → 낮은 우선순위 큐로 이동.
정리
알고리즘 | 방식 | 특징 |
FCFS | 비선점 | 먼저 온 순서대로 실행 |
SJF | 비선점 | 실행 시간이 가장 짧은 작업 우선 |
SRT | 선점 | 남은 실행 시간이 가장 짧은 작업 우선 |
RR | 선점 | 일정 시간(Time Quantum) 단위로 실행 |
HRN | 비선점 | 응답 비율이 높은 프로세스 우선 |
다단계 피드백 큐 | 선점 | 우선순위 큐를 사용하여 관리 |