CPU 스케줄링

I. CPU의 효율적 사용, CPU 스케줄링

가. CPU 스케줄링의 개념

• 프로세스 작업 수행을 위해 언제, 어느 프로세스에 CPU를 할당할 것인지 결정하는 작업

나. CPU 스케줄링 기법 종류

구분	기법	설명
선점	RR	– 초기 FCFS, 환형 순환구조 뒤로 보냄
	SRT	– 가장 짧게 남은 시간
	MLQ	– 여러 개 큐 이용
	MLFQ	– 서로 다른 타임 슬라이스의 큐 이용
비선점	Priority	– 우선순위 높은 순서대로 처리
	FCFS	– 대기 큐에 도착한 순서에 따라 할당
	SJF	– 수행시간(버스트시간) 짧게 판정 먼저
	HRN	– 우선순위=(대기 + 버스트) / 버스트 시간

• 스케줄러 동작 시점, Time Slice, 프로세스 생성/소멸 시, 프로세스 Block 상태 변경 시
• 스케줄러가 운영체제에 많이 관여-선점, 적게 관여-비선점

 

II. SJF(Shortest Job First), SRT(Shortest Remaining Time)

가. SJF(Shortest Job First)

개념
설명	– 비선점 방식 (non-preemptive) – 대기 작업 중 수행시간이 짧게 판정된 작업 수행 – 짧은 작업 먼저 수행이 오버헤드 측면에서 유리
문제점	– 작업 수행시간을 사전에 정확히 판정 어려움

나. SRT(Shortest Remaining Time)

개념
설명	– 선점 방식 (preemptive) – SJF 기법에 선점방식을 도입/변형 방식 – 실행 중 작업이라도 처리시간이 더 짧은 작업이 생기면 선점
문제점	– 각 작업에 대한 실행 시간 추적 보유(오버헤드) – 긴 작업은 SJF 보다 대기 시간 오래 소요

 

III. SJF와 SRT의 평균 대기시간 및 평균 반환시간

프로세스	도착 시간	실행 시간
P1	0	6
P2	1	3
P3	2	1
P4	3	4

가. SJF 기법 계산

프로세스 자원점유 그래프
프로세스 시간 테이블	항목 P1 P2 P3 P4 도착 시간 0 1 2 3 실행 시간 6 3 1 4 종료 시간 6 10 7 14 반환 시간 6 9 5 11 대기 시간 0 6 4 7
평균 대기	평균 대기시간 = (0 + 6 + 4 + 7) / 4 = 4.25
평균 반환	평균 반환시간 = (6 + 9 + 5 + 11) / 4 = 7.75

나. SRT 기법 계산

프로세스 자원점유 그래프
프로세스 시간 테이블	항목 P1 P2 P3 P4 도착 시간 0 1 2 3 실행 시간 6 3 1 4 종료 시간 14 5 3 9 반환 시간 14 4 1 6 대기 시간 8 1 0 2
평균 대기	평균 대기시간 = (8 + 1 + 0 + 2) / 4 = 2.75
평균 반환	평균 반환시간 = (14 + 4 + 1 + 6) / 4 = 6.25

• 대기시간: 작업이 대기 큐에서 대기한 시간, 반환시간: 작업이 제출된(도착) 시간부터 완료까지 시간
• 프로세스 자원 점유 변경 시 문맥 교환이 일어나므로 빈번한 자원 점유 변경 시 오버헤드 증가에 따른 성능 감소