[103] 운영체제 06차시 스케쥴링 알고리즘

1. 선입 선출, 최소 작업 우선 스케쥴링

가. 선입선출(FCFS, First Com First Served) 스케쥴링의 개념

비선점 방법으로 프로세서 스케쥴링 알고리즘 중 가장 단순

프로세서 요청하는 순서대로 프로세서 할당, 선입 선출 FIFO 큐로 구현

일괄 처리 시스템에서는 매우 효율적이나 빠른 응답을 요청하는 대화식 시스템에는 적합하지 않음.

도착하는 프로세스의 순서에 따라 평균 대기 시간과 평균 반환 시간에 차이가 있음.

나. FCFS 스케쥴링의 장점

스케쥴링의 이해와 구현이 단순함.

준비 큐에 있는 모든 프로세스가 결국 실행되므로 기아 없는 공정한 정책임.

프로세서가 지속적으로 유용한 프로세스를 수행하여 처리율이 높음.

다. FCFS 스케쥴링의 단점

비선점식이므로 대화식 프로세스에는 부적합함.

 

라. 비선점 최소작업 우선(SJF, Shortest Job First) 스케쥴링 개념

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

최단 작업 우선 스케쥴링이라고도 함.

마. SJF 스케쥴링의 장점

항상 실행 시간이 짧은 작업을 신속하게 실행하므로 평균 대기 시간이 가장 짧음

바. SJF 스케쥴링의 단점

초기에 들어온 긴 작업의 경우 보다 짧은 작업들을 위해 계속 대기하므로 기아가 발생함.

기본적으로 짧은 작업이 항상 실행되도록 설정하므로 불공정한 작업을 실행.

 

사. 선점 최소작업 우선(SRT, SRTF, Shortest Remaining Time First) 스케쥴링 개념

SJF의 선점형 버전

아. SRTF 스케쥴링의 장점

같은 상황일 경우, SJF보다 개선된 결과(평균 반환 시간, 평균 대기 시간)를 얻을 수 있음.

자. SRTF 스케쥴링의 단점

알고리즘 구현이 복잡함.

문맥교환이 일어나므로 오버헤드가 발생할 가능성이 있음.

2. 우선순위, 순환 할당 스케쥴링

가. 우선순위 스케쥴링(Priority Scheduling)의 개념

프로세스의 중요도에 따른 우선순위를 반영한 스케쥴링 알고리즘

우선순위 스케쥴링도 선점 또는 비선점 가능

우선순위는 0~7 또는 0~4,095 범위의 수를 사용, 0을 최상위로 할지 최하위로 할지 정하지는 않음.

1) 고정 우선순위 알고리즘

한 번 우선순위를 부여 받으면 종료될 때까지 우선순위가 고정

단순하게 구현할 수 있지만 시시각각 변하는 시스템의 상황을 반영하지 못해 효율성이 떨어짐.

2) 변동 우선순위 알고리즘

일정 시간마다 우선 순위를 새로 계산하고 이를 반영

복잡하지만 시스템의 상황을 반영하여 효율적인 운영 가능

나. 우선순위 스케쥴링의 문제점

1) 준비 큐에 있는 프로세스의 순서를 무시하고 우선순위가 높은 프로세스에 먼저 CPU를 할당하므로 공평성을 위배하고 기아 현상을 일으킴.

에이징으로 해결할 수 있음.

에이징이란 시스템에서 오래 대기하는 프로세스들의 우선순위를 점진적으로 증가시켜 시간이 지나면 점차 프로세스의 우선순위가 높아지게 하는 방법

다. 우선순위 스케쥴링의 장단점

1) 장점

각 프로세서의 상대적 중요성을 정확히 정의할 수 있음.

2) 단점

높은 우선순위 프로세스가 프로세서를 많이 사용하면 우선순위가 낮은 프로세스는 무한정 연기되는 기아가 발생할 수 있음.

 

라. 라운드 로빈(RR) 스케쥴링 개념

한 프로세스가 할당 받은 시간(타임슬라이스) 동안 작업을 하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식

프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행

https://ko.wikipedia.org/wiki/라운드_로빈_스케줄링

라운드 로빈 스케줄링 - 위키백과, 우리 모두의 백과사전

마. 라운드 로빈 스케쥴링의 장단점

1) 장점

시분할 방식의 시스템에서 효과적임

2) 단점

할당 시간이 크면 FCFS 방식과 같음

할당 시간이 작으면 자주 문맥교환이 발생하므로 오버헤드가 커짐.

3. 다단계 큐, HRN 스케쥴링

가. 다단계 큐 스케쥴링의 개념

우선순위에 따라 준비 큐를 여러 개 사용하는 방식

프로세스는 운영체제로부터 부여받은 우선 순위에 따라 해당 우선순위의 큐에 삽입

준비 상태 큐를 종류별로 여러 단계로 분할, 그리고 작업을 메모리의 크기나 프로세스의 형태에 따라 특정 큐에 지정

나. 다단계 큐 스케쥴링의 장단점

1) 장점

응답이 빠름

2) 단점

여러 준비 큐와 스케쥴링 알고리즘 때문에 추가 오버헤드가 발생

우선순위가 낮은 큐의 프로세스는 무한정 대기하는 기아가 발생할 수 있음.

다. 다단계 피드백 큐 스케쥴링의 개념

프로세스가 CPU를 한 번씩 할당 받아 실행될 때마다 프로세스의 우선순위를 낮춤으로써, 다단계 큐에서 우선 순위가 낮은 프로세서의 실행이 연기되는 문제를 완화

우선순위에 따라 타임슬라이스의 크기가 다름.

우선순위가 낮아질수록 CPU를 얻을 확률이 적어짐.

따라서 한 번 CPU를 잡을 때 많이 작업하기 위해 낮은 우선순위의 타임슬라이스를 크게 지정함.

라. 다단계 피드백 큐의 장단점

1) 장점

매우 유연하여 스케쥴러를 특정 시스템에 맞게 구성할 수 있음.

자동으로 입출력 중심 프로세스와 프로세서 중심 프로세스를 분류

적응성이 좋아 프로세서의 사전 정보가 없어도 최소 작업 우선 스케쥴링의 효과를 보여줌.

2) 단점

설계와 구현이 매우 복잡함.

마. HRN 스케쥴링의 개념

최소작업 우선 스케쥴링의 약점인 긴 작업과 짧은 작업 간의 지나친 불평등을 보완

비선점 스케쥴링이며 우선순위 스케쥴링의 또 다른 예

선입선처리 스케쥴링과 최소작업 우선 스케쥴링의 약점을 해결하기 위해 제안

서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 스케쥴링을 하는 방식

우선순위를 서비스를 받을 시간(실행 시간)과 대기한 시간을 더해 서비스를 받을 시간으로 나누어 계산

https://ko.wikipedia.org/wiki/HRRN_스케줄링

HRRN 스케줄링 - 위키백과, 우리 모두의 백과사전

바. HRN 스케쥴링의 장단점

1) 장점

실행 시간이 짧은 프로세스의 우선순위를 높게 설정하면서도 대기 시간을 고려하여 기아 현상을 완화

2) 단점

오버헤드가 높을 수 있음.(메모리와 프로세서 낭비)