[운영체제론] 스케줄링 알고리즘 1 / 2021.12.06

* 참고 자료 : 운영체제론 한빛아카데미

 

스케줄링 알고리즘이란?

스케줄링 알고리즘이란 실행 시 어떤 프로세스가 언제, 얼마 동안 실행할지 결정하는 것이다.

이때 여러 요인을 고려해야 한다.

- 선점/비선점 여부

- 우선순위

- 실행 시간

- 완료 시까지 남은 시간

- 공평성

- 기타 프로세스 특성

 

1. 선입선출 스케줄링 (FIFO)

가장 간단한 스케줄링 알고리즘이다. 프로세스들은 준비 큐에 도착한 순서에 따라 프로세서를 할당받는다. FIFO는 비선점 방식이다. 현대 시스템에서는 주요 스케줄링 정책으로 거의 사용하지 않는다.

 

선입선출 스케줄링

 

1. FIFO 스케줄러를 사용하는 시스템에서 무기한 연기가 발생할 수 있는가? 모든 프로세스가 도중에 무한 루프에 빠지거나 하지 않고 결국은 실행을 완료함을 전제로 답하라.
답 : 아니다. 무기한 연기가 발생할 수 없다. 도착하는 프로세스는 큐의 뒤로 들어가야 하는데, 이는 앞서 도착해 대기하고 있는 프로세스를 방해할 수 없음을 의미한다.
2. FIFO 스케줄링은 현대 시스템에서는 거의 찾아보기 어렵다.
답 : 거짓. FIFO는 주요 정책으로는 사용하지 않지만, 많은 현대 스케줄링 알고리즘에서 사용한다. 예를 들어, 우선순위가 같은 여러 프로세스를 처리해야 할 때는 FIFO 순서로 처리한다.

 

2. 라운드로빈 스케줄링 (RR)

라운드로빈 스케줄링에서는 프로세스를 FIFO 순서로 디스패치하지만 타임 슬라이스(퀀텀)라는 제한된 프로세서 시간 안에서만 수행한다. 어떤 프로세스가 자신의 퀀텀이 만료될 때까지 작업을 마치지 못하면, 시스템은 해당 프로세스로부터 프로세서를 선점해 다음 대기 프로세스에 할당한다. 

라운드로빈 방식은 대기 프로세스를 메인 메모리에 유지해 선점에 의해 발생하는 오버헤드를 최소화해야 한다. 

FIFO 방식과 같이 라운드로빈 방식도 주요 스케줄링 정책으로 거의 사용하지 않고, 복잡한 스케줄링 알고리즘 내부에서 찾아볼 수 있다.

 

라운드로빈 스케줄링

3. 이기적인 라운드로빈 스케줄링 (SRR)

이기적인 라운드로빈은 시간이 지남에 따라 프로세스의 우선순위를 높이는 에이징 기법을 사용한다. 이 방식은 각 프로세스가 시스템에 진입하면 먼저 보류 큐에 들어간다. 그리고 오래 돼서 활성 큐에 들어갈만한 우선순위가 될 때까지 여기서 대기한다. 우선순위가 높아지면 활성 큐에 위치해, 큐에 있는 다른 프로세스들과 함께 라운드로빈 방식으로 스케줄링된다. 스케줄러는 활성 큐에 있는 프로세스만 디스패치한다. 따라서 먼저 온 오래된 프로세스를 선호한다.

 

- 보류 큐 : a, 활성 큐 : b (a, b : 우선순위가 올라가는 비율)

- a>b 이면, 시간이 지남에 따라 보류 큐에 있는 프로세스가 활성 큐에 있는 프로세스와 비교해 우선순위가 같거나 높아지면 활성 큐에 들어간다.

- a>>b 이면, 보류 큐에서 시간을 거의 소비하지 않아 라운드 로빈 방식과 유사해진다.

- a=b 이면, RR과 동일하다.

 

- 퀀텀 크기 : q

- 매우 큰 퀀텀 크기 -> 프로세스가 작업을 마칠 정도의 크기 (FIFO 방식처럼 동작)

- 매우 작은 퀀텀 크기 -> 프로세서 사이클의 대부분을 문맥 전환 오버헤드에 사용

- 리눅스에서 기본 퀀텀은 10ms 이지만 10~200ms 범위를 가진다. 우선순위가 높고 입출력 중심 프로세스가 우선순위가 낮고 프로세서 중심 프로세스보다 퀀텀이 크다.

- 윈도우에서 기본 퀀텀은 20ms 이다. 그러나 이 값도 프로세스가 포그라운드, 백그라운드에서 실행되는지에 따라 다르다.

 

입출력 중심 프로세스만 있는 시스템에서 퀀텀 크기를 조절하는 다이얼을 돌린다고 하자. q=c인 지점 이후 퀀텀 크기를 늘리는 것은 시스템 성능에 거의 변화를 주지 않는다. c는 무엇을 나타내는가? 또한 q>c일 때 시스템 성능에 변화가 생기지 않는 이유는 무엇인가?
답 : 이 지점은 시스템에 있는 모든 프로세스의 입출력 요청 사이에서 가장 긴 시간일 것이다. q값이 c를 넘어선 후 증가할 때 어떤 프로세스에도 영향을 주지 않을 것이다. 각 프로세스는 자신의 퀀텀 기간이 만료되기 전에 블록되므로, 추가적인 프로세서 시간을 할당받아도 이점을 얻을 수 없기 때문이다.

 

4. 최단 프로세스 우선 스케줄링 (SPF)

최단 프로세스 우선 방식은 비선점형 스케줄링 규칙으로, 완료 시까지 실행 시간이 가장 짧을 것으로 예상하는 프로세스를 선택한다. FIFO 보다는 평균 대기 시간이 감소한다. 대기하는 프로세스의 수를 줄이고 긴 프로세스 뒤에 대기하는 프로세스 수를 최소화하기 때문이다. 

 

단점

- 부정확한 예상 실행 시간

- FIFO 방식보다 변량이 큼 (예측이 더욱 어려움)

- 단기 스케줄링에는 부적합

- 비선점 방식으로 적절한 반응 시간을 보장해야 하는 환경에서는 적용이 곤란

 

1. 시스템 처리량이 중요한 경우, SPF가 FIFO보다 바람직한 이유는 무엇인가?
답 : SPF는 평균 대기 시간을 줄여서 처리량을 높여준다.
2. SPF가 현대 운영체제의 저수준 스케줄링으로 부적절한 이유는 무엇인가?
답 : SPF는 프로세스에 빠른 응답 시간을 보장하지않는다.

 

5. 최고 응답률 우선 스케줄링 (HRRN)

최고 응답률 우선 스케줄리은 SPF의 약점을 보강한 스케줄링이다. (SPF는 실행시간이 긴 프로세스 차별, 짧은 프로세스 지나치게 우대) HRRN은 각 프로세스의 우선순위에서 서비스 시간 뿐만 아니라 서비스를 받으려고 대기하는 시간도 계산하는 비선점형 스케줄링 규칙이다. 프로세스가 일단 차례를 얻으면 해당 프로세스는 완료할 때까지 실행한다.

 

우선순위 공식

이 기법은 에이징 기법과 비슷하며, 특정 프로세스가 무기한 연기되는 일을 방지해준다.

 

1. HRRN 스케줄링을 사용할 때 짧은 프로세스는 항상 긴 프로세스보다 먼저 스케줄링한다.
답 : 거짓. 프로세스가 오래 대기할수록 짧은 프로세스보다 먼저 스케줄링될 가능성이 커진다.
2. 프로세스 P1은 서비스 시간으로 5초를 명시하고, 20초를 대기했다. 프로세스 P2는 서비스 시간으로 3초를 명시하고 9초를 대기했다. HRRN을 사용하는 시스템에서 어떤 프로세스를 먼저 실행하겠는가?
답 : 이 경우 프로세스 P1은 우선순위가 5고, P2는 우선순위가 4다. 따라서 P1을 먼저 실행한다.

 

6. 최소 잔여 시간 스케줄링 (SRT)

최소 잔여 시간 스케줄링은 SPF의 선점형 버전이다. SRT는 예상 완료 시까지 실행 시간이 가장 짧은 프로세스를 선택한다. (새로 도착하는 프로세스의 예상 실행 시간이 더 짧은 경우. 완료 시까지 실행 시간이 더 긴 프로세스를 선점한다. -> 실행 중인 프로세스의 경과 시간에 관한 정보의 유지가 필요하다.) 실행 시간이 긴 프로세스는 SPF보다 대기 시간이 길어질 수 있으며, 대기 시간의 변량이 크다. 또한 선점 오버헤드에 의해 성능 저하가 일어난다. (실행 중인 프로세스가 거의 완료되어갈 때 예상 서비스 시간이 아주 짧은 프로세스가 도착하는 경우, 새 프로세스의 예상 실행 시간이 실행 중인 프로세스보다 짧지만 그 차이가 아주 작은 경우)

 

 

스케줄링 알고리즘 2 :

https://cow-kite24.tistory.com/121

[운영체제론] 스케줄링 알고리즘 2 / 2021.12.06