운영체제 3강 :: 스케쥴링, 스케쥴링 알고리즘

운영체제에서 기억하고 싶은 내용

 

 

프로세스 스케쥴링

프로세스 순서 결정

 

스케쥴링
여러 작업의 처리 순서를 결정
예시) 프로세스 스케쥴링, 디스크 스케쥴링

 

 

스케쥴링 단계

상위단계 스케쥴링

시스템의 자원을 효율적으로 이용할 수 있도록

 

하위단계 스케쥴링

준비 큐에 있는 프로세스 선택해서 사용 가능한 CPU를 할당(디스패치)

수행 주체: 디스패처

 

 

스케쥴링 기본적인 목표?

• 공정성: 모든 프로세스가 적정 수준에서 CPU 작업 할 수 있도록
• 균형: 시스템 자원을 충분히 활용

 

 

일괄처리 운영체제 목표

• 처리량의 극대화: 주어진 시간에 처리한 프로세스 수
• 반환시간 최소화: 생성 시점부터 종료 시점까지 소요 시간
• CPU 활용 극대화

 

 

시분할 운영체제의 목표

• 빠른 응답 시간: 용청한 시점부터 반응이 시작되는 시점
• 과다한 대기시간 방지: 프로세스 종료될 때까지 준비 큐에서 기다린 시간의 합

 

 

실시간 운영체제의 목표

처리기한 맞춤

 

 

스케쥴링 정책

1. 선점(preemptive) 스케쥴링 정책

• 실행 중인 프로세스에 인터럽트하고 다른 프로세스에 CPU 할당하는 방식
• 높은 우선순위 프로세스를 먼저 처리해야 하는 경우 좋다
• 문맥 교환에 대한 오버헤드 발생

 

 

문맥(context)
모든 레지스터와 기타 운영체제에 따라 요구되는 프로세스 상태

문맥 교환(context switching)
CPU가 현재 실행중인 프로세스의 문맥을 PCB에 저장하고,
다른 프로세스의 PCB로부터 문맥을 복원

 

2. 비선점(nonpreemptive) 스케쥴링 정책

• 실행 중인 프로세스를 준비상태로 바로 상태 변화를 할 수 없는 방식
• 강제적인 문맥 교환이 없어 강제적인 오버헤드가 발생하지 않는다
• 현재 프로세스가 길면 짧은 프로세스가 오래 기다린다

 

 

스케쥴링의 평가 기준은 어떻게 될까?

• 평균 대기 시간: 프로세스가 수행이 완료될 때까지 준비 큐에서 기다리는 시간의 합의 평균값
• 평균 반환 시간: 생성된 시점부터 완료된 시점까지 소요시간의 평균값

 

 

스케쥴링 알고리즘

 

 

FCFS(First Come First Served)

• 비선점 방식
• 준비 큐에 도착한 순서에 따라 디스패치

 

장점

간단한 기법

 

단점

• 짧은 프로세스가 긴 프로세스를 기다린다
• 중요한 프로세스가 나중에 수행될 수도 있다
• 시분할, 실시간 운영체제에서 부적합
• 도착 순서에 따라 평균 반환 시간이 크게 변한다

 

 

SJF(Shortest Job First)

• 비선점 방식
• 가장 짧다고 예상되는 것을 먼저 디스패치

 

장점

일괄처리 환경에서 구현 쉬움

 

단점

• 실제로 먼저 처리할 프로세스의 CPU 시간을 예상할 수 없다
• 새로 들어온 짧은 프로세스가 현재 진행중인 긴 프로세스를 기다린다
• 중요한 프로세스가 나중에 수행될 수 있다
• 시불할, 실시간 운영체제에 부적합

 

 

SRT(Shortest Remaining Time)

위의 SJF 알고리즘의 선점 방식!

준비 큐의 프로세스 중에 실행시간 짧을 것 같은 것부터 실행

 

장점

SJF보다 평균 대기시간과 평균 반환시간에서 효율

 

단점

프로세스 CPU 시간을 예상할 수 없다

실행시간 추적, 선점을 위한 문맥 교환 등 SJF보다 오버헤드 크다

 

 

RR(Round Robin)

• 선점 방식
• 기본적으로 준비 큐에 도착한 순서대로(FCFS) 디스패치 하지만,
• 정해준 시간 할당량 안에 못 끝내면 준비 큐 마지막에 배치

장점

CPU 독점없이 공평하게 사용

=> 시분할 운영체제에 적합

 

단점

• 시간 할당량을 너무 크게 잡으면 FCFS와 동일
• 시간 할당량이 너무 작게 잡으면 잦은 문맥 교환 발생 => 오버헤드 발생

 

 

HRN(Highest Response Ratio Next)

• 비선점 방식
• 준비 큐에서 기다리는 프로세스 중 응답비율이 가장 큰 것을 먼저 디스패치

응답비율 = (대기시간 / 예상 실행시간) + 1
=> 예상 실행시간이 짧을수록, 대기 시간이 길수록 응답 비율이 커진다

 

장점

• SJF 스케쥴링의 단점 보완
• 대기 시간이 길어질수록 먼저 실행될 수 있다

 

단점

• 예상 시간 계산 어려움

 

 

다단계 피드백 큐 스케쥴링

• 선점 방식
• I/O 중심 프로세스와 연산 중심 프로세스의 특성에 따라 다른 시간 할당량 부여

 

특징

• 입출력 위주 프로세스는 높은 우선권 유지
• 연산 위주의 프로세스는 낮은 우선권이지만 긴 시간 할당량 받는다