[쉽게 배우는 운영체제] 4-1. CPU 스케줄링: 스케줄링

조성호 님의 "쉽게 배우는 운영체제" 책을 정리한 포스팅 입니다

 

1. 스케줄링

• 한정된 CPU 자원을 공정하고 효율적으로 나눠 쓰게 하는 규칙과 과정

 

단계

스케줄링 단계	설명	주요 역할
고수준 스케줄링	전체 작업 수를 조절하고, 동시에 실행 가능한 프로세스의 총 개수를 제한하는 단계	실행 대기열에 추가할 프로세스 결정
중간 수준 스케줄링	시스템의 활성 프로세스 수를 조절하는 단계	- 활성 프로세스 수 조절 - 메모리 자원 관리 (스왑 처리)
저수준 스케줄링	준비 상태에 있는 프로세스 중에서 어떤 프로세스를 실행할지 결정하는 단계 ✅ 스케줄링 알고리즘을 사용함 ➡️ CPU 자원을 최적화함	- 준비 상태 프로세스 선택

 

2. 저수준 스케줄링

스케쥴링 고려사항

항목	설명	스케줄링 고려사항
전면 프로세스	사용자와 상호작용이 가능한 프로세스	- 즉각적인 반응이 필요  - 높은 우선순위 부여
후면 프로세스	사용자와 상호작용이 없는 프로세스	- 시스템 자원이 유휴 상태일 때 실행 - 낮은 우선순위 부여
프로세스 우선순위	CPU 스케줄러가 프로세스에 우선순위를 부여하여 실행 순서를 결정	- 사용자가 프로세스의 우선순위를 정할 수 있음
CPU 집중 프로세스	CPU를 많이 사용하는 프로세스	- 멀티코어 활용 가능성 높음  - 공정한 자원 분배 중요  - 예: RR, Priority-based Scheduling
I/O 집중 프로세스	입출력 작업을 많이 수행하는 프로세스	- 자주 대기 상태로 전환됨  - 빠르게 복귀할 수 있도록 스케줄링 필요  - 예: SJF, Multilevel Queue Scheduling

 

예시) CPU 집중 프로세스 - CPU 버스트

• 프로세스가 CPU를 할당받아 연속적으로 실행되는 시간 구간
• CPU 자원을 효율적으로 할당하려면 버스트를 고려하여 스케줄링

 

스케쥴링 평가 기준

항목	설명
CPU 사용률	전체 시간 중 CPU가 실제로 사용된 비율
처리량 (Throughput)	단위 시간당 완료된 프로세스 수
대기 시간 (Waiting Time)	준비 큐에서 CPU를 할당받기 전까지 대기한 시간
응답 시간 (Response Time)	프로세스 시작 후 첫 반응이 나오기까지의 시간
실행 시간 (Execution Time)	CPU에서 실제로 실행된 시간
반환 시간 (Turnaround Time)	프로세스 도착부터 종료까지 걸린 전체 시간(대기 시간 + 실행 시간)

 

종류

스케줄링 종류	설명	특징
선점형 스케줄링	OS가 실행 중인 프로세스의 CPU를 강제로 빼앗을 수 있는 방식	실행 중인 프로세스를 강제로 중단하고 다른 프로세스를 실행
비선점형 스케줄링	OS가 실행 중인 프로세스의 CPU를 강제로 빼앗을 수 없는 방식	과거 일괄 작업 시스템에서 사용

 

예시) 선점형 스케줄링 - 인터럽트

• CPU가 OS로부터 인터럽트를 받으면 현재 실행 중인 작업을 중단하고 인터럽트부터 처리함
• 즉시 처리 후 이전 작업으로 복귀함

 

3. 저수준 스케줄링 알고리즘

비선점형 알고리즘

구분	FCFS	SJF	HRN
기본 개념	먼저 도착한 프로세스부터 실행	실행 시간이 가장 짧은 프로세스 먼저 실행	응답률이 가장 높은 프로세스 실행
선택 기준	도착 순서	CPU 실행 시간	응답률
계산 기준	❌	실행 시간	(대기 시간 + 실행 시간) / 실행 시간
장점	구현이 단순함 오버헤드 적음	평균 대기 시간 최소	SJF의 Starvation 문제 완화
단점	응답 시간 김 ➡️ Convoy Effect 발생	실행 시간 예측 어려움 ➡️ Starvation 발생	계산 복잡 완전한 공평성은 아님
공평성	낮음	매우 낮음	중간
Starvation	발생 가능	발생	완화됨
사용 환경	일괄 처리 시스템	배치 처리 시스템	배치 처리 시스템

 

선점형 알고리즘

구분	Round Robin	SRT	다단계 큐	다단계 피드백 큐
기본 개념	동일한 타임 슬라이스로 순환 실행	남은 실행 시간이 가장 짧은 프로세스 우선	우선순위별 여러 준비 큐 사용	CPU 사용량에 따라 우선순위 동적 조정
선점 기준	타임 슬라이스 만료	더 짧은 작업 도착	상위 우선순위 큐 존재	우선순위 변경 규칙
우선순위	동일	실행 시간 기준	고정	동적
큐 이동	가능	가능	❌	✅
장점	공정성 보장 응답 시간 예측 가능	평균 대기 시간 감소	구조 단순 역할 분리	Starvation 완화
단점	타임 슬라이스 설정 민감	Starvation 발생 가능 예측 어려움	하위 큐 Starvation	설계·구현 복잡
Starvation	❌	✅	✅	거의 ❌
주요 목적	공정성, 응답성	성능 최적화	우선순위 관리	공정성 + 응답성
사용 환경	시분할 시스템	실험적/이론적	단순 우선순위 시스템	현대 운영체제

 

4. 다중 큐

우선순위 부여 방식

구분	설명
고정 우선순위 방식	프로세스의 우선순위가 시작 시점에 결정되며, 끝날 때까지 바뀌지 않음.
변동 우선순위 방식	프로세스 실행 중간에 우선순위가 변하는 방식.

 

상태

준비 상태

특징	설명
우선순위 큐 관리	프로세스 제어 블록(PCB)은 우선순위 큐로 관리됨.
큐에 삽입	준비 상태에 들어올 때마다 자신의 우선순위에 해당하는 큐의 마지막에 삽입됨.
CPU 할당	CPU 스케줄러는 우선순위가 가장 높은 큐의 맨 앞에 있는 프로세스에 CPU를 할당함.

 

블록 상태

특징	설명
입출력 장치 별 관리	입출력 장치별로 프로세스 처리 입출력 작업이 완료되면, 해당 프로세스를 준비상태로 옮길 수 있음 (한번에 여러개의 프로세스가 옮겨질 수 있음)