[CS] {운영체제} CPU 스케줄링
1. CPU 스케줄링 개요
1) CPU 스케줄링이란?
: 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것
2) 프로세스 우선순위
- 입출력 작업이 많은 프로세스(=입출력 집중 프로세스)의 우선순위는
CPU작업이 많은 프로세스(=CPU 집중 프로세스)의 우선순위보다 높다
(입출력 집중 프로세스는 잠깐 실항하면 당분간 대기상태로 접어들기 때문에)
(1) 스케줄링 큐
a. 준비큐
b. 대기큐
(2) 선점형/비선점형 스케줄링
a. 선점형 스케줄링
- 위에서 설명한 스케줄링 방법이 보통 선점형 스케줄링
장점 : 어느 한 프로세스의 자원 독점을 막고 프로세스들에 골고루 자원을 배분할 수 있다.
단점 : 그만큼 문맥 교환 과정에서 오버헤드가 발생할 수 있다.
b. 비선점형 스케줄링
- 한 프로세스가 작업이 종료되기 전까지 끼어들 수 없음
장점 : 문맥교환에서 발생하는 오버헤드가 선점형보다 적다.
단점 : 모든 프로세스가 골고루 자원을 이용하기 어렵다.
2. CPU 스케줄링 알고리즘
1) 선입 선처리 스케줄링
=FCFS 스케줄링
- 단순히 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링
- 먼저 CPU를 요청한 프로세스부터 CPU 할당
단점 : 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 부작용 (= 호휘효과)
2) 최단 작업 우선 스케줄링
=SJF 스케줄링
- 호위 효과 방지
- CPU 사용이 긴 프로세스는 나중에 실행, CPU 사용 시간이 짧은 프로세스는 먼저 실행
- CPU 사용시간이 가장 짧은 프로세스부터 처리하는 스케줄링 방식
- 기본적으로 비선점형이지만 선점형도 가능
3) 라운드 로빈 스케줄링
=RR 스케줄링
- 선입 선처리 스케줄링 + 타임 슬라이스
* 타임슬라이스 : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
- 정해진 타임 슬라이스만큼의 시간동안 돌아가며 CPU를 이용하는 선점형 스케줄링
- 큐에 삽입된 프로세스들은 순서대로 CPU를 이용하되 정해진 시간만큼만 이용
- 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입(문맥교환)
4) 최소 잔여시간 우선 스케줄링
=SRT 스케줄링
- 최단작업 우선 스케줄링 + 라운드 로빈 스케줄링
- 최단 작업 우선 스케줄링 : 작업 시간이 짧은 프로세스부터 처리
- 라운드 로빈 스케줄링 : 정해진 타임 슬라이스만큼 돌아가며 사용
- 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는 남은 작업 시간이 가장 적은 프로세스 선택
5) 우선순위 스케줄링
- 프로세스들에 우선순위를 부여하고, 우선순위 높은 프로세스부터 실행
- 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링
- 최단 작업 우선 스케줄링, 최소 잔여시간 스케줄 => 우선순위 스케줄링
단점 : Starvation(기아 현상), 우선순위 높은 프로세스만 실행. 낮은 프로세스는 준비 큐에 먼저 삽입되었음에도 연기
-> 이를 방지하기 위한 기법 : 에이징
- 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식
- 대기중인 프로세스의 우선순위를 마치 나이 먹듯 점차 증가시키는 방법
6) 다단계 큐 스케줄링
= Multilevel queue 스케줄링
- 우선순위 스케줄링의 발전된 형태
- 우선순위별로 준비 큐를 여러개 사용하는 스케줄링 방식
- 우선순위가 가장 높은 큐에 있는 프로세스를 먼저처리
- 우선순위가 가장 높은 큐가 비어있으면 그 다음 우선순위 큐에 있는 프로세스 처리
7) 다단계 피드백 큐 스케줄링
= Multilevel feedback queue 스케줄링
- 다단계 큐 스케줄링의 발전된 형태
- 큐 간 이동이 가능한 다단계 큐 스케줄링
- 다단계 큐 스케줄링에서는 기본적으로 큐 간 이동 불가
- 우선순위 낮은 프로세스는 계속해서 실행 연기 우려
- 기아현상 발생가능
- 즉, 어떤 프로세스의 CPU 시간이 길면 우선순위가 낮아지고 낮은 우선순위 큐에서 너무 오래 기다리면 우선순위를 높이는 방식
- CPU 스케줄링 방식으로 알려져 있음