CPU 스케줄러

여러 프로세스의 상황을 고려하여 CPU와 시스템 자원의 배정을 결정

고소준 스케줄링: 시스템 내의 전체 작업 수를 조절, 어떤 작업을 시스템이 받아들일지 또는 거부할지를 결정
중간 수준 스케줄링: 시스템에 과부화가 걸려서 전체 프로세스 수를 조절해야 한다면 이미 활성화된 프로세스 중 일부를 보류 상태로 보냄
저수준 스케줄링: 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정

CPU 스케줄링의 목적

공평성, 효율성, 안정성, 확장성, 반응 시간 보장, 무한 연기 방지

프로세스 스케줄링 이용 시 -> CPU 이용률 증가, (오버헤드, 응답시간, 반환시간, 대기시간) 감소

선점형 스케줄링
(강제로 프로세스의 작업을 중단시킬 수 있으면 선점형)

비선점형 스케줄링
(프로세스의 할 일이 끝나기 전까지 중단시킬 수 없으면 비선점형)

CPU 스케줄링 시 우선순위

프로세스는 준비 상태에 들어올 때마다 자신의 우선순위에 해당하는 큐의 마지막에 삽입

스케줄링 알고리즘의 평가 기준

대기 시간: 프로세스가 생성된 후 실행되기 전까지 대기하는 시간 (작업 시작 시간 – 도착 시간 or 작업 시작 시간 – 작업 중지 시간의 합)
응답 시간: 첫 작업을 시작한 후 첫 번째 출력이 나오기까지의 시간
실행 시간: 프로세스의 작업이 시작된 후 종료되기까지의 시간 (작업 완료 시간 – 작업 시작 시간)
반환 시간: 대기 시간을 포함하여 실행이 종료될 때까지의 시간 (작업 완료 시간 – 도착 시간)
(시간은 짧을수록 좋음)

스케줄링 동작 방식 비교

1. FCFS 스케줄링의 동작 방식

준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식

평균 대기 시간: (0+27+42)/3 = 23밀리초

p2 입장에서는 3 밀리초 에 시작해야 되는데 이미 작업 중인 p1때문에 30 밀리초 (p1끝나는 시간)에 시작함 -> 30-3=27 밀리초 기다림

p3 입장에서는 6 밀리초 에 시작해야 될 것을 이미 작업 중인 p1과 대기중인 p2 때문에 48 밀리초 (p2끝나는 시간)에 시작함 -> 48-6=42 밀리초 기다림

FCFS 스케줄링의 평가

2. SJF 스케줄링의 동작 방식

준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식

평균 대기 시간: (0+24+36)/3 = 20밀리초

p2 입장에서는 3분에 시작해야 되는데 이미 작업 중인 p1 때문에 최소 30밀리초 뒤 시작해야 됨. 그런데 30 밀리초 지나고 대기열을 보니 가장 작업 시간이 큼 -> p3가 끝나고 작업 가능 -> 30 + 9밀리초 뒤 시작 -> 36밀리초 대기

P3 입장에서는 6 밀리초 에 시작해야 되는데 이미 작업 중인 p1 때문에 최소 30 밀리초 뒤 시작해야 됨. 그런데 30 밀리초 지나고 대기열을 보니 가장 작업 시간이 짧음 -> 바로 작업 가능 -> 30 밀리초 뒤 시작 -> 24 밀리초 대기

SJF 스케줄링의 성능

에이징 (아사 현상의 완화 방법)

3. HRN 스케줄링

준비 큐에 있는 프로세스 중에서 우선순위가 가장 큰 작업부터 CPU를 할당하는 비선점형 방식

평균 대기 시간: (0+24+36)/3=20밀리초

HRN 스케줄링의 평가

4. 라운드 로빈(RR) 스케줄링의 동작 방식

총 대기 시간: 0(p1)+7(p2)+14(p3)+19(p1)+19(p2)+8(p1)=67 밀리초
평균 대기 시간: 67/3 =22.33 밀리초

타임 슬라이스가 큰 경우
하나의 작업이 끝난 뒤 다음 작업이 시작되는 것처럼 보여 FCFS 스케줄링과 다를게 없음

타임 슬라이스가 작은 경우
문맥 교환이 너무 자주 일어나 문맥 교환에 걸리는 시간이 실제 작업 시간보다 상대적으로 커지며, 문맥 교환에 많은 시간을 낭비하여 실제 작업을 못하는 문제가 발생

5. SRT 스케줄링의 동작 방식

총 대기 시간: 0(P1)+4(P3)+16(P2)+27(P1)=47밀리초
평균 대기 시간: 47/3=15.66밀리초
(최대 10밀리초 끝나고 남은 시간이 가장 짧은 프로세스 선택)

우선순위 스케줄링