OS

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

noahkim_ 2024. 12. 12. 01:38

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

 

1. 스케줄링 단계

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

 

2. 저수준 스케줄링

종류

스케줄링 종류 설명 특징
선점형 스케줄링 OS가 실행 중인 프로세스의 CPU를 강제로 빼앗을 수 있는 방식
실행 중인 프로세스를 강제로 중단하고 다른 프로세스를 실행
(대부분의 저수준 스케줄러가 채택)
- 인터럽트 CPU가 OS로부터 인터럽트를 받으면 현재 실행 중인 작업을 중단하고 인터럽트부터 처리
완료 후 원래 작업으로 복귀
하드웨어나 소프트웨어 인터럽트 발생 시, 즉시 처리 후 이전 작업으로 복귀
비선점형 스케줄링 OS가 실행 중인 프로세스의 CPU를 강제로 빼앗을 수 없는 방식
과거 일괄 작업 시스템에서 사용
현재는 주로 배치 처리 시스템에서 사용

 

고려사항

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

 

알고리즘

알고리즘 종류 설명 특징
선택 기준    
- CPU 사용률 CPU가 사용된 시간  
- 처리량 단위 시간당 작업을 마친 프로세스의 수  
- 대기 시간 작업을 시작하기 전까지 대기하는 시간  
- 응답 시간
프로세스 시작 후 첫 번째 출력 또는 반응이 나올 때까지 걸리는 시간
 
- 실행 시간 작업이 시작된 후 종료되기까지 시간  
- 반환 시간
대기 시간을 포함하여 실행이 종료될 때까지의 시간
 
비선점형 알고리즘    
- FCFS
(First Come First Served)
준비 큐에 도착한 순서대로 CPU를 할당
일괄 처리 작업 시스템에서 사용
I/O call 시 context switch X
시스템 효율성 떨어짐
- SJF
(Shortest Job First)
준비 큐에 있는 프로세스 중 실행 시간이 가장 짧은 작업부터 CPU 할당
종료 시간을 예측하기 어려움
공평하지 못함
- HRN
(Highest Response
Ratio Next Scheduling)
SJF에서 발생할 수 있는 Starving 문제를 해결하기 위해 설계
응답률 우선 기준 사용
대기 시간이 길수록 실행 시간이 짧을수록 응답률 높아짐
Starving 현상 완화
여전히 공평성 부족
선점형 알고리즘    
- Round Robin 순환 순서 방식
각 프로세스가 time slice 동안 작업을 완료하지 못하면 준비 큐 맨 뒤로 가서 대기
모든 작업이 완료될 때까지 순환하며 실행
공정하고 예측 가능
- SRT
(Shortest Remaining Time)
SJF와 Round Robin 방식을 혼합
실행 시간이 짧은 프로세스를 먼저 처리
성능이 좋지 않음
종료 시간 예측 어려워 Starving 현상 발생
- 다단계 큐 우선순위에 따라 준비 큐를 여러 개 사용
각 큐에 Round Robin 방식 적용
상위 우선순위 큐의 작업이 끝나기 전까지 하위 큐 프로세스 작업 수행 불가
프로세스의 큐 이동 불가
타임 슬라이스 조절 가능
- 다단계 피드백 큐 우선순위를 동적으로 조정하는 방식
CPU 시간을 덜 사용한 프로세스는 승격됨
CPU 시간을 많이 사용한 프로세스는 강등됨
CPU 사용 후 프로세스의 우선순위가 낮아짐
우선순위가 낮은 프로세스에 불리한 문제 보완

 

3. 다중 큐

우선순위 부여 방식

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

 

상태

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

 

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