1. CPU 스케줄링 개요
CPU 스케줄러
CPU 스케줄링은 여러 개의 프로세스가 CPU를 공유하는 상황에서 CPU를 효율적으로 사용하기 위해 수행할 프로세스를 선택하는 작업
스케줄링은 운영체제에서 수행되며, 프로세스의 상태를 감시하고 우선순위를 결정하여 다음에 수행될 프로세스를 선택
스케줄링 단계
고수준 스케줄링 : 시스템 내의 전체 작업 수 조절, 작업을 시스템이 받아들일지 결정, 시스템 내 동시 실행 가능한 프로세스 총 개수 정해짐
저수준 스케줄링 : 어떤 프로세스에 CPU를 할당할지, 대기 상태로 보낼지 등 결정, 아주 짧은 시간에 일어남
중간 수준 스케줄링 : 중지와 활성화로 전체 시스템의 활성화된 프로세스 수를 조절하여 과부하 막음, 일부 프로세스를 중지 상태로 옮겨 나머지 프로세스가 원만하게 작동하도록 지원, 저수준 스케줄링이 원만하게 이루어지도록 완충
CPU 스케줄링의 목적
2. 선점형 비선전형
선점형 스케줄링
- 운영체제가 필요하다고 판단하면 실행 상태에 있는 프로세스의 작업을 중단시키고 새로운 작업을 시작할 수 있는 방식
- 하나의 프로세스가 CPU를 독점할 수 없기 때문에 대화형 시스템, 시분할 시스템에 적합
- 저수준 스케줄러는 선점형 스케줄링 사용
비선점형 스케줄링
- 어떤 프로세스가 실행 상태에 들어가 CPU를 사용하면 그 프로세스가 종료되거나 대기 상태에 들어가기 전까지 계속 실행
- 선점형보다 스케줄러 작업량이 적고 문맥 교환에 의한 낭비도 적음
- CPU 사용 시간이 긴 프로세스 때문에 CPU 사용 시간이 짧은 여러 프로세스가 오랫동안 기다리게 되어 전체 시스템의 처리율 떨어짐
- 과거의 일괄 작업 시스템에서 사용하던 방식
프로세스 우선순위
- 커널 프로세스의 우선순위가 일반 프로세스보다 높음
- 시스템에 다양한 우선순위 프로세스가 공존하며 우선순위가 높은 프로세스가 CPU를 먼저 더 오래 차지
CPU 집중 프로세스
- CPU를 많이 사용하는 프로세스, CPU 버스트 많음
입출력 집중 프로세스
- 저장장치에서 데이터를 복사하는 일과 같이 입출력을 많이 사용하는 프로세스로 입출력 버스트가 많은 프로세스
우선 배정
- 스케줄링 시 입출력 집중 프로세스의 우선순위를 CPU 집중 프로세스보다 높이면 시스템 효율 향상
전면 프로세스
- GUI를 사용하는 운영체제에서 화면의 맨 앞에 놓인 프로세스
- 현재 입력과 출력을 사용하는 프로세스
- 사용자와 상호작용이 가능
후면 프로세스
- 사용자와 상호작용 없는 프로세스
- 사용자의 입력 없이 작동
- 전면 프로세스의 우선순위가 더 높음
3. 준비상태의 다중 큐
준비상태의 다중 큐
- 프로세스는 준비 상태에 들어올 때마다 자신의 우선순위에 해당하는 큐의 마지막에 삽입
- CPU 스케줄러는 우선순위가 가장 높은 큐(0번 큐)의 맨 앞에 있는 프로세스 6에 CPU 할당
프로세스의 우선순위 배정 방식
고정 우선순위 방식
- 운영체제가 프로세스에 우선순위 부여하면 프로세스가 끝날 때까지 바뀌지 않음
- 효율성 떨어짐
변동 우선순위 방식
- 프로세스 생성 시 부여 받은 우선순위가 프로세스 작업 중간에 변하는 방식
- 작업 효율성 높아짐
다중 큐
준비 큐 : 한 번에 하나의 프로세스 꺼내어 CPU 할당
대기 큐 : 여러 개의 프로세스 제어 블록을 동시에 꺼내어 준비 상태로 옮김
4. 스케줄링 알고리즘
평가 기준
FCFS 스케줄링
동작방식
- 준비 큐에 도착한 순서대로 CPU 할당하는 비선점형 방식
- 한 번 실행되면 그 프로세스가 끝나야만 다음 프로세스 실행 가능
- 큐가 하나라 모든 프로세스는 우선순위가 동일
FCFS : First Come First Served
성능
평가
- 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다려 시스템의 효율성이 떨어짐
- 현재 작업 중인 프로세스가 입출력 작업을 요청하는 경우 CPU가 작업하지 않고 쉬는 시간이 많아져 작업 효율 떨어짐
SJF 스케줄링
동작방식
- 준비 큐에 있는 프로세스 중 실행 시간이 가장 짧은 작업부터 CPU 할당하는 비선점형 방식
- 최단 작업 우선 스케줄링이라고도 함
성능
평가
- 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어려움
- 작업 시간이 길다는 이유만으로 계속 뒤로 밀려 공평성이 현저히 떨어짐 => 아사현상
HRN 스케줄링
동작방식
- 아사 현상 해결하기 위해 만들어진 비선점형 알고리즘
- 최고 응답율 우선 스케줄링
- 서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 스케줄링 하는 방식
- 프로세스의 우선순위 결정 기준
성능
평가
- 실행 시간이 짧은 프로세스의 우선순위를 높게 설정하면서도 대기 시간을 고려하여 아사 현상 완화
- 대기 시간이 긴 프로세스의 우선순위를 높임으로써 CPU 할당받을 확률 높임
- 공평성이 위배되어 많이 사용되지 않음
라운드 로빈 스케줄링
동작방식
- 한 프로세스가 할당받은 시간(타임 슬라이스) 동안 작업을 하다가 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례 기다리는 방식
- 선점형 알고리즘 중 가장 단순하고 대표적인 방식
- 프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행
성능
타임 슬라이스는 되도록 작게 설정하되 문맥 교환에 걸리는 시간을 고려하여 적당한 크기로 함
SRT 스케줄링
동작방식
- 기본적으로 라운드 로빈 스케줄링을 사용하지만 CPU를 할당받을 프로세스를 선택할 때 남아 있는 작업 시간이 가장 적은 프로세스 선택
성능
평가
- 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고 남은 시간이 더 적은 프로세스와 문맥 교환해야하므로 SJF에 없는 작업 추가
- 운영체제가 프로세스의 종료 시간 예측하기 어렵고 아사 현상 일어나기에 잘 사용하지 않음
우선순위 스케줄링
- 프로세스의 중요도에 따른 스케줄링 알고리즘
SJF : 작업 시간이 짧은 프로세스에 높은 우선순위 부여
HRN : 작업 시간이 짧거나 대기 시간이 긴 프로세스에 높은 우선순위 부여
SRT : 남은 시간이 짧은 프로세스에 높은 우선순위 부여
고정 우선순위
- 한 번 우선순위 부여받으면 종료될 때까지 고정
- 구현 방식 단순, 현재 상황 반영 못해 효율성 떨어짐
변동 우선순위
- 일정 시간마다 우선순위가 변하여 우선순위 새로 계산하고 반영
- 복잡하지만 시스템 상황 반영하여 효율적
평가
- 준비 큐의 프로세스 순서 무시하고 우선순위 높은 프로세스에 먼저 CPU 할당하므로 공평성 위배하고 아사 현상 일으키며 우선순위를 매번 바꿔야하므로 오버헤드 발생하여 시스템 효율성 떨어뜨림
다단계 큐 스케줄링
- 우선순위에 따라 준비 큐 여러 개 사용
- 프로세스는 운영체제로부터 부여받은 우선순위에 따라 해당 우선순위의 큐에 삽입
- 우선순위는 고정형 우선순위 사용
- 상단의 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업 시작
동작방식
- 프로세스가 CPU를 한 번씩 할당받아 실행될 때마다 프로세스의 우선순위를 낮춤으로써 다단계 큐에서 우선순위가 낮은 프로세스의 실행이 연기되는 문제 완화
- 우선순위가 낮아져도 커널 프로세스가 일반 프로세스의 큐에 삽입되지 않음
- 우선순위에 따라 타임 슬라이스 크기 다름
- 우선순위가 낮아질수록 CPU 얻을 확률 적어짐 -> CPU 잡을 때 낮은 우선순위의 타임 슬라이스를 크게 함
- 마지막 큐에 있는 프로세스는 무한대의 타임 슬라이스 얻음
- 마지막 큐는 들어온 순서대로 작업 마치는 FCFS 스케줄링 방식으로 동작
