[운영체제] 스케줄링 알고리즘

[한빛아카데미] 운영체제 책으로 학습한 내용을 정리한 것입니다.

 

* 선입선처리 스케줄링(FCFS, First Come First Served)

- 선입선출 스케줄링(FIFO, First In First Out)이라고도 함 

- 프로세서를 요청하는 순서대로 프로세서를 할당하며, 선입선출 큐로 구현함

- 비선점 스케줄링

장점	- 스케줄링의 이해와 구현이 단순함 - 준비 큐에 있는 모든 프로세스가 결국 실행되므로 기아 없는 공정한 정책임 - 프로세서가 지속적으로 유용한 프로세스를 수행하여 처리율이 높음
단점	- 비선점식이므로 대화식 프로세스(작업)에는 부적합함 - 장기 실행 프로세스가 뒤의 프로세스(작업)를 모두 지연시켜 평균 대기시간이 길어져 최악의 대기시간이 됨 - 긴 프로세스(작업)가 실행되는 동안 짧은 프로세스(작업)가 긴 대기시간으로 호위 효과가 발생할 수 있음

 

* 최소작업 우선 스케줄링(SJF, Shortest Job First)

- 각 작업의 프로세서 실행 시간을 이용하여 프로세서가 사용 가능할 때 실행 시간이 가장 짧은 작업에 할당하는 방법

- 선점/비선점 스케줄링

장점	- 항상 실행 시간이 짧은 작업을 신속하게 실행하므로 평균 대기시간이 가장 짧음
단점	- 초기의 긴 작업을 짧은 작업을 종료할 때까지 대기시켜 기아가 발생함 - 기본적으로 짧은 작업이 항상 실행되도록 설정하므로 불공정한 작업을 실행함 - 실행 시간을 예측하기가 어려워 실용적이지 못함

 

* 우선순위 스케줄링(Priority Scheduling)

- 프로세스가 준비 큐에 도착하면, 도착한 프로세스의 우선순위와 현재 실행 중인 프로세스의 우선순위를 비교하여 우선순위가 가장 높은 프로세스에 프로세서를 할당함

- 우선순위가 동일한 프로세스들은 선입선처리 순서로 스케줄링함

- 실행 준비는 했으나 우선순위가 높은 프로세스가 계속 들어오면 우선순위가 낮은 프로세스는 무한정 기다려야 하는 문제는 에이징으로 해결 가능함

(참고) 에이징(Aging) : 시스템에서 오래 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 방법으로, 시간이 지나면 점차 프로세스의 우선순위가 높아짐

- 선점/비선점 스케줄링

장점	- 각 프로세스의 상대적 중요성을 정확히 정의할 수 있음 - 다양한 반응으로 실시간 시스템에 사용 가능
단점	- 높은 우선순위 프로세스가 프로세서를 많이 사용하면 우선순위가 낮은 프로세스는 무한정 연기되는 기아 발생 가능성 있음

 

* 라운드 로빈 스케줄링(Round-Robin Scheduling)

- 시분할 시스템을 위해 설계함

- 작은 단위의 시간인 규정 시간량 또는 시간 할당량을 정의된 만큼 한 번에 한 프로세스에 프로세서를 제공

- 선점 스케줄링

장점	- 모든 프로세스가 프로세서의 동일한 점유율과 제한된 대기시간으로 공정하며 기아가 발생하지 않음 - 실행 큐에 프로세스 수를 알고 있을 때 구현 용이 - 강한 상호작용과 프로세스의 짧은 응답시간, 특히 프로세스 최악의 응답시간을 알 수 있음 - 작업 길이가 다양할 때는 이전 작업을 마친 후보다 규정 시간량을 마치고 다음 작업으로 이동하기 때문에 평균 대기시간이 선입선처리와 최소작업 우선 스케줄링보다 적음
단점	- 성능은 규정 시간량의 길이에 따라 달라지므로 작업이 비슷한 길이가 좋음 - 너무 길면 선입선처리로 변하고, 너무 짧으면 많은 문맥 교환으로 비용 부담이 큼 - 하드웨어 타이머가 필요함 - 미완성 작업은 각 규정 시간량을 마친 후 프로세서를 기다리므로 평균 처리 시간이 높음

 

* 다단계 큐 스케줄링(MLQ, MultiLevel Queue)

- 각 작업을 서로 다른 묶음으로 분류할 수 있을 때 사용함

- ex. 전면 작업/후면 작업: 전면 작업은 후면 작업에 비해 우선순위가 높음

- 선점 스케줄링

장점	- 응답이 빠름
단점	- 여러 준비 큐와 스케줄링 알고리즘 때문에 추가 오버헤드 발생함 - 우선순위가 낮은 큐의 프로세스는 무한정 대기하는 기아가 발생할 수 있음

 

* 다단계 피드백 큐 스케줄링(MLQ, MultiLevel Feedback Queue)

- 다단계 큐 스케줄링과 다르게 큐 사이를 이동할 수 있음

- 요청하는 프로세서 실행 시간이 길면 작업을 낮은 단계 큐로 옮김

- 선점 스케줄링

장점	- 매우 유연하여 스케줄러를 특정 시스템에 맞게 구성할 수 있음  - 자동으로 입출력 중심과 프로세서 중심 프로세스를 분류함 - 적응성이 좋아 프로세스의 사전 정보가 없어도 최소작업 우선 스케줄링의 효과를 보여줌
단점	- 설계와 구현이 매우 복잡함

 

* HRN 스케줄링(Highest Response-ratio Next Scheduling)

- SJF과 FIFO의 단점인 기아현상 문제를 보완한 스케줄링

- 우선순위 스케줄링의 다른 예시임

- HRN 스케줄링 우선순위 = (서비스를 받을 시간 + 대기한 시간) / 서비스를 받을 시간

- HRN 스케줄링 시스템 응답시간 = 서비스를 받을 시간 + 대기한 시간

- 비선점 스케줄링

장점	- 자원을 효율적으로 활용함 - 기아가 발생하지 않음
단점	- 메모리와 프로세서 낭비로 인해 오버헤드가 높을 수 있음

 

* 다중 프로세서 스케줄링

- 각 프로세서에 서로 독립된 준비 큐를 제공하거나 공동의 준비 큐를 사용하여 모든 작업이 이용 가능한 프로세서 큐로 가도록 스케줄링해야 함 

- 방법 1. 공통의 준비 상태 큐에서 실행할 프로세스 하나를 프로세서 자신이 스스로 스케줄링함

- 방법 2. 비대칭 다중 처리(AMP, Asymmetric MultiProcessing)는 한 프로세서를 다른 모든 프로세서의 스케줄러로 지정하고, 주종 구조(Master/Slave)를 보임

 

* 스레드 스케줄링

- 스레드를 이용하여 응용 프로그램을 동일한 주소 공간에서 동시에 실행하고 협동하는 스레드들로 구현함

- 부하 공유, 갱 스케줄링, 전용 프로세서 할당, 동적 스케줄링 등

 

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

- 최대 응답시간이 1초라는 제약 조건에서 프로세서 이용률

- 평균 반환시간이 전체 실행 시간에 선형적으로 비례하는 처리율