OS
[쉽게 배우는 운영체제] 4-1. CPU 스케줄링: 스케줄링
noahkim_
2024. 12. 12. 01:38
조성호 님의 "쉽게 배우는 운영체제" 책을 정리한 포스팅 입니다
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를 할당함.
|
블록 상태
| 특징 | 설명 |
| 입출력 장치 별 관리 |
입출력 장치별로 프로세스 처리
입출력 작업이 완료되면, 해당 프로세스를 준비상태로 옮길 수 있음 (한번에 여러개의 프로세스가 옮겨질 수 있음) |