OS 정리-Chap 6-프로세스 스케줄링

Aug 10, 2022

1. 스케줄링의 이해
   • 1 스케줄링의 개념
   • 2 스케줄링의 목적
   • 3 스케줄링의 기준 요소
   • 4 스케줄링의 단계
   • 5 스케줄링 큐
   • 6 스케줄링과 스케줄러
   • 7 선점 스케줄링과 비선점 스케줄링
   • 8 스케줄링 알고리즘의 선택 기준
2. 스케줄링 알고리즘
   • 1 선입선처리(FIFO, First In First Out) 스케줄링
   • 2 최소작업 우선 스케줄링
   • 3 우선순위 스케줄링
   • 4 라운드 로빈 스케줄링
   • 5 다단계 큐 스케줄링
   • 6 다단계 피드백 큐 스케줄링
   • 7 HRN 스케줄링
   • 8 다중 프로세서 스케줄링
   • 9 스레드 스케줄링

6. 프로세스 스케줄링

🗣️ 출처

IT COOK BOOK 운영체제 (개정 3판, 구현회 저, 한빛 아카데미) 보안 확인 : 외부링크
"https://www.hanbit.co.kr/store..."로 ? 를 정리한 내용입니다.

스케줄링의 이해

1 스케줄링의 개념

스케줄링(scheduling)은 다음을 의미한다.

• 다중 프로그래밍 환경에서 프로세서를 할당할 프로세스를 선택할 때의 전략

• 여러 프로세스가 번갈아 사용하는 자원(보통 프로세서)을 어떤 시점에 어떤 프로세스에 할당할 지 결정하는 것

이를 통해 프로세서 이용률, 처리율 증가, 응답시간 감소 등의 성능적 이득을 얻을 수 있다.

단일 처리 시스템에서는 스케줄링의 개념이 없어 입출력 등을 처리하기 위해 프로세서가 유휴 상태가 되어 비효율적인 경우가 많이 생긴다.

스케줄링에 대상이 되는 프로세스는 자원의 공유 순서나 일정이 중요한 사용자 프로세스나 시스템 프로세스이며, 즉시 사전 처리되는 인터럽트 처리, 오류 처리, 사용자의 시스템 호출 등은 대상이 아니다.

2 스케줄링의 목적

스케줄링의 목적은 다음과 같다.

• 자원 할당의 공정성 보장 : 모든 프로세스가 공평하게, 무한한 연기 없이 처리됨

• 단위 시간당 처리량 최대화 : 단위시간당 유효 시간을 줄이고 프로세서의 처리량을 최대화하여 가능한 많은 프로세스에 서비스 제공

• 적절한 반환시간 보장 : 느려도 2~3초 내의 적절 시간 내에 응답 요구

• 예측 가능성 보장 : 작업을 시스템 부하와 관계 없이 유사한 시간과 비용에 실행 보장

• 오버헤드 최소화 : 오버헤드는 성능 향상을 위해 필요하지만 과하면 반대로 성능 감소

• 자원 사용의 균형 유지 : 모든 시스템 자원의 최대 활용을 위한 지원 제공

• 반환 시간과 자원의 활용 간에 균형 유지 : 반환 시간과 자원 활용은 서로 반비례 관계인 경우가 많으므로 적절한 균형 유지가 필요 (ex : 실시간 시스템은 반환 시간이 빠른게 중요, 다른 형태 시스템은 자원의 활용도도 중요)

• 실행 대기 방지 : 실행의 무한 연기를 막기 위해 에이징 방법 등을 활용

• 우선순위 : 우선순위가 높은 프로세스에게 자원 배려

• 서비스 사용 기회 확대 : 페이지 부재율이 적은 프로세스에 더욱 자주 서비스 제공

• 서비스 수 감소 방지 : 시스템 과부하에 의한 서비스 수 감소 방지

3 스케줄링의 기준 요소

프로세서 버스트(burst)는 프로세스를 프로세서에서 실행하는 기간을 의미한다.

프로세서 버스트는 크게 사용자의 입출력을 기다리는 입출력 버스트와 작업이 처리되는 프로세서 버스트로 나뉘며 버스트 간에는 프로세스가 준비 큐(ready queue)로 이동하여 기다린다.

주로 그림 6-1 예시처럼 입출력 버스트와 프로세서 버스트의 순환, 특히 프로세서 버스트로 시작해 프로세서 버스트로 끝나는 경우가 많다.

프로세스 버스트는 빈도가 많은 작업들은 짧은 경향이 많으며, 반대로 빈도가 적은 작업들은 긴 경향이 있다.

또한, 백그라운드 프로그램 같이 긴 프로세서 버스트가 많으면 입출력이 적다는 의미이므로 프로세서 중심 프로세스는 짧은 입출력 버스트를 가지는 경향이 있으며, 입출력 버스트가 잦으면, 그만큼 프로세스가 입출력을 기다리는 경우가 많다는 의미이므로 입출력 중심 프로세스는 짧은 프로세서 버스트를 많이 가지는 경향이 있다. 이는 그림 6-2에 묘사되어있다.

이러한 프로세서 중심 프로세스는 할당 받은 프로세서 시간이 완료 시간을 결정하고, 입출력 중심 프로세스는 입출력 완료 시간으로 완료시간이 결정되므로, 이 둘의 적절한 혼합을 위해 스케줄링 알고리즘을 잘 골라야한다.

• 혼합이 필요한 예를 들자면, 입출력 프로세스만 너무 많으면 준비 큐가 거의 비어있어 단기 스케줄러가 할일이 없어 비효율적이다. 반대로 프로세서 중심 프로세스만 많으면 입출력 준비 큐가 비어있으면서 프로세서들이 병목 현상을 겪을 것이다.

최근에는 프로세서의 발달로 프로세서 버스트가 짧아져 입출력 중심으로 바뀌고 있으며, 프로세서 중심과 입출력 중심이 서로 바뀌는 프로세스 또한 존재한다.

이때 입출력 중심 프로세스를 실행 뒤 프로세서 중심 프로세스로 바뀌면 짧은 지연이 생기며, 반대의 변화의 경우 긴 지연이 걸린다.

4 스케줄링의 단계

스케줄링은 아래 그림처럼 수행 단계에 따라 크게 3가지로 나뉜다. 중기 스케줄링을 제외한 단기와 장기 스케줄링은 6절에 자세히 알아보자.

1단계 작업 스케줄링 : 작업 선택 (장기 스케줄링)

• 실제 시스템 자원을 사용할 작업을 결정하는 작업 스케줄링

• 디스크에 있는 작업 중 프로세스화할 작업과 시스템에 들어갈 작업을 결정하는 과정

수행 빈도가 적어 장기 스케줄링에 해당한다.

2단계 작업 승인과 프로세서 결정 스케줄링 : 사용 권한 부여 (중기 스케줄링)

• 프로세서를 사용할 권한을 부여할 프로세스를 결정하는 작업 승인 및 프로세서 할당

• 작업 연기할 프로세스를 결정해 메모리에서 제거, 프로세스 수 관리

수행 빈도 기준 중기 스케줄링, 스와핑(swapping, 교체) 기능의 일부로 메모리 사용성을 높이고 작업 효율성이 향상시킴.

3단계 프로세서 할당 스케줄링 : 준비 상태의 프로세스에 프로세서 할당(디스패칭, 단기 스케줄링)

• 디스패처(분배기)가 준비 상태에 있는 프로세스 중에서 프로세서를 할당할 프로세스를 결정하는 프로세스 할당 스케줄링

수행 빈도 기준 단기 스케줄링

5 스케줄링 큐

스케줄링에서 사용하는 큐는 시스템에 단 하나 있는 준비 큐와 입출력 장치별로 하나씩 있는 입출력 장치 큐가 있다. 그림 6-4는 프로세스의 큐 이동 방향이다.

그림 6-5은 큐에 적재되어 있는 프로세스의 모습이다. 각 큐의 포인터로 head와 tail 포인터가 존재하며, 프로세스 제어 블록의 포인터 주소를 가르키고 있다. 테이프 드라이브나 시분할 단말기 같은 전용 장치는 큐에 단 하나의 프로세스만 존재 가능하지만, 디스크 같이 여러 프로세스가 줄을 서는 경우도 있다.

6 스케줄링과 스케줄러

스케줄러의 프로세스 변화과정에서의 역할과 종류를 알아보자.

6.1 큐잉 도표(queueing diagram)

큐잉 도표는 프로세스 스케줄링을 표현하는 방법이다.

• 큐는 사각형으로

• 자원은 원으로

• 프로세스의 흐름은 화살표로

표시한다.(그림 6-7 참조)

작업이 시스템에 들어오면 프로세스 제어 블록을 생성하고, 준비 큐에 들어간 뒤, 작업 종료까지 갱신된다. 프로세스가 준비 큐에 나와 프로세서가 할당된 뒤, 다음 사항중 하나가 일어난다.

• 프로세스가 입출력 요청을 보내고 입출력 큐에 들어감. (이후 대기 상태, 이후 준비 큐에서 준비 상태)

• 프로세스가 새로운 프로세스를 생성(fork)하고 생성한 프로세스의 종료 때까지 대기 상태로 기다리다 종료되면 준비 큐로 들어간다.

• 프로세스가 시간 할당량을 초과(시간 종료)하면 준비 큐에 들어감.

• 오류 등의 이유로 인터럽트 발생으로 인해 프로세서에서 제거된 프로세스는 다시 준비큐에 들어감.

6.2 스케줄러의 종류와 역할

스케줄러는 스케줄링을 통해 프로세스를 선택하며, 주로 장기 스케줄러와 단기 스케줄러가 있다.

그림 6-4와 같이 단순 큐잉 도표를 기준으로 역할을 알아보자

장기 스케줄러

작업 스케줄러라고도 하며, 스케줄링에 따라 디스크에서 메모리로 작업을 가져와 처리할 순서를 결정한다.

제출 시간, 작업 이름, 작업 길이, 메모리 사용량, 자원 등을 확인하고 프로세스 제어 블록을 생성해 메모리에 적재하여 프로세스를 준비 상태로 만든다. 이때, 메모리에 적재할 프로세스의 수를 통해 다중 프로그래밍 정도를 결정할수 있다.

실행 빈도가 분 단위로, 상대적으로 드물게 수행되며, 비교적 성능에 영향이 적다.

단기 스케줄러

메모리에 적재된 프로세스의 요청 중 자원을 만족하는 경우, 해당 프로세스에게 프로세서를 할당해 실행 상태가 되도록 스케줄링 알고리즘으로 결정한다.

실행 빈도가 비교적 수시로 일어나므로, 오버헤드를 최대한 작게 만들어야 한다.

프로세스의 실행 상태에서 대기 상태로, 또는 대기 상태에서 준비 상태로 변화하는 것을 처리

일부 단기 스케줄러는 그림 6-11처럼 디스패처를 가지고 있다. 디스패처의 역할은 다음과 같다.

• 단기 스케줄러가 준비 큐에서 선정한 프로세서에게 프로세서를 할당하는 모듈

• 프로세스의 레지스터를 적재(문맥 교환)

• 사용자 상태로 전환하고 다시 시작할 때, 사용자 프로세스가 올바른 위치를 찾도록 도와줌

중기 스케줄러

• 프로세스들이 프로세서를 두고 경쟁 시, 프로세스를 메모리에서 빼내 다중 프로그래밍 정도를 줄인다. (스왑 아웃)

• 이후, 메모리에서 빼낸 프로세스를 다시 메모리에 들이고, 실행이 중단된 곳부터 재실행한다. (스왑 인)

이 과정을 스왑이라고 하며, 작업의 혼합과 메모리 효율에 좋다.(그림 6-8)

메모리에 부분적으로 프로세스를 적재하고, 일시중지된 프로세서의 원인을 해결하면 다시 준비상태로 만듦.

프로세스 상태 변화와 스케줄러의 역할

프로세스 상태변화에 영향을 끼치는 스케줄러는 그림 6-9를 통해 알 수 있다.

실행에서 종료 상태로 변화하는 것은 장기 스케줄러와 단기 스케줄러가 처리한다.

7 선점 스케줄링과 비선점 스케줄링

선점은 실행 중인 작업의 자원을 다른 작업이 빼앗을 수 있음을 의미하며, 비선점은 반대로 빼앗을 수 없음을 의미한다.

선점 스케줄링은

• 프로세스 하나가 장시간 동안 프로세서를 독점한는 것을 방지하여 모든 프로세스에 서비스 기회를 줄 수 있고,

• 우선순위를 통해 실시간 시스템 같은 긴급, 인터럽트 처리를 하는데 유용하다.

• 선점 시 오버헤드가 커질 수 있어 메모리에 프로세스가 준비 상태로 있어야 효과적

• 우선순위를 의미있게 부여해야 함

비선점 스케줄링은

• 모든 프로세스가 공정하게 관리됨

• 우선순위에 연연하지 않으므로, 응답 시간 예측이 쉽다.

• 보통 구현이 더욱 용이하다.

8 스케줄링 알고리즘의 선택 기준

스케줄링 알고리즘은 프로세서 사용률과 처리율을 최대화하고, 반환시간, 대기시간, 응답시간을 최소화하는 것이 바람직하다.

그림 6-10을 보고 환경에 따른 시간의 정의를 알아보자.

• 프로세서 사용률 : 프로세서를 항상 실행 상태로 유지해 유휴 상태가 되지 않도록 함. 입출력 중심 작업보다는 프로세서 중심 작업을 실행으로 상승

• 처리율 : 단위 시간당 완료하는 작업수, 인터럽트를 줄이거나 짧은 작업을 우선 처리하면 상승한다.

• 반환시간 : 작업이 메모리에 들어가기까지 걸리는 시간 + 준비큐에 머무는 시간 + 실행시간과 입출력 시간 등의 합이므로, 이들을 최소화해야 한다.

• 대기시간: 준비 큐에 머무는 시간. 사용자 수를 제한하면 상승한다.

• 반응시간 : 작업 요청부터 첫 응답까지의 시간 대화형 시스템에서 중요함.

스케줄링 알고리즘

단일 처리 시스템 기준으로 주요 스케줄링 알고리즘을 소개한다.

1 선입선처리(FIFO, First In First Out) 스케줄링

비선점 방법으로 큐 구조를 활용해 줄처럼 먼저 요청된 프로세스가 먼저 처리되는 방식이다.

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

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

그림 6-11처럼 시스템에 새로운 프로세스가 들어오면 해당 프로세스 제어 블록을 준비 큐의 마지막에 연결한다.

선입선처리는 대부분 성능이 좋지 않고 들쭉날쭉하며, 평균 대기 시간이 길다.

또한, 호위 효과라는 현상이 생기는데, 처리 속도가 빠른 프로세스들이 처리 속도가 느린 프로세스를 끝나기를 기다리며 몰려다니는 현상이다.(그림 6-12)

✍ 호위 효과 예시

1. 정상적인 시스템 상태

2. 프로세서를 차지하고 있는 느린 프로세스를 대기하면서 준비 큐에 빠른 프로세스들이 쌓인다.
   • 주로 느린 프로세스는 프로세서 중심 프로세스이며, 빠른 프로세스는 입출력 중심 프로세스이다.

3. 이번엔 입출력장치를 사용하고 있는 느린 프로세스 때문에 빠른 프로세스들이 입출력 장치 큐에 쌓이기 시작한다.

4. 2번과 같이 역시 프로세서를 사용하는 느린 프로세스를 기다리느라 빠른 프로세스들이 준비 큐에 쌓인다.

5. 이러한 상황이 계속 반복되면서 느린 프로세스 뒤로 빠른 프로세스들이 쌓이기 시작한다.

또한, 비선점식이므로 정기적으로 프로세서를 공유하는 시분할 시스템에서는 부적합하다.

2 최소작업 우선 스케줄링

최소작업 우선(SJF, Shortest Job First) 스케줄링은 각 작업의 프로세서 실행 시간을 이용해 프로세서가 사용가능 시 실행 시간이 가장 짧은 작업(프로세스)에 할당하는 방법이다. 만약, 실행 시간이 동일하다면 선입선처리 스케줄링을 적용한다.

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

가장 짧은 작업 먼저 실행하도록 한다면, 짧은 작업들의 대기 시간은 줄어들고 긴 시간의 작업들의 대기시간은 늘어나며, 보통 평균 대기시간을 줄일 수 있다.

• 만약 5, 11, 7, 3의 실행시간을 가지는 프로세스들($P_1,P_2,P_3,P_4$)이 순서대로 실행한다고 가정하자.

  선입 선출의 경우 평균 대기 시간은 다음과 같다.

  \[\displaylines{ \frac{W(P_1)+\dots+W(P_4)}{4}=\\ \frac{0 + 5 + (5+11) + (5+11+7) + (5+11+7+3)}{4}=11 }\]

  만약 최소작업 먼저 우선하여 스케줄링하였다면 순서는 $P_4,P_1,P_3,P_2$가 되며 평균 대기 시간은 다음과 같다.

  \[\displaylines{ \frac{W(P_4)+\dots+W(P_2)}{4}=\\ \frac{0 + 3 + (3+5) + (3+5+7) + (3+5+7+11)}{4}=6.5 }\]

물론 실제로는 가장 짧은 작업이 먼저 자원을 요청하지 않을 수 있으므로, 이상적인 상황이 나오진 않을 것이다.

최소 작업 우선 스케줄링은 선점과 비선점 방식 두 가지 방식으로 구현 가능하다.(그림 6-13)

✍ 프로세스 도착 시간 예시 그래프

프로세스	도착 시간	실행 시간
$P_1$	0	10
$P_2$	1	28
$P_3$	2	6
$P_4$	3	4
$P_5$	4	14

✍ 비선점 최소 작업 우선 스케줄링 VS 선점 최소 작업 우선 스케줄링

비선점 최소 작업 우선 스케줄링의 평균 반환시간은 26이며 평균 대기시간은 13.6이다.

반면에 선점 최소 작업 우선 스케줄링의 평균 반환시간은 25이며 평균 대기시간은 12.6이다. 다만, 실제로는 문맥 교환에 의한 오버헤드를 고려해야한다.

비선점 방식은 실행시간이 짧더라도 이미 실행되고 있는 프로세스를 중단시킬 수 없으므로, 비선점 방식보다 대기시간이 긴경우가 많으며, 시분할 시스템에 사용하기 어렵다.

선점 방식은 문맥 교환 시간이 소요되므로 언제나 비선점형보다 유리하진 않으며, 따로 최소 잔여 시간 우선(SRTF, Shortest Remaining Time First) 스케줄링이라고도 부른다.

최소 작업 우선 스케줄링은 실행 시간을 예측하기 힘들고, 긴 작업들의 기아 상태를 유발시킬 수 있다는 단점이 있다.

따라서 장기 스케줄링에 많이 사용되지만 단기 스케줄링에서는 예측이 어려워 최소작업 우선 스케줄링의 근사치를 이용한다.

3 우선순위 스케줄링

우선순위 스케줄링(prioirty scheduling)은 준비 큐에 존재하는 프로세스들의 우선순위를 비교해 우선순위가 가장 높은 프로세스에 프로세서를 할당하는 알고리즘이다. 우선순위가 동일하다면 선입선출 순서로 스케줄링한다.

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

보통 우선순위의 기준은 예측된 다음 프로세서 버스트의 역이며, 실행 시간이 길수록 우선순위가 낮고, 짧을 수록 높으며, 보통 0~7 또는 0~4095 범위의 수를 사용한다. 단, 0을 최상위나 최하위로 정하지 않는다.

하지만 우선순위는따로 내부적, 또는 외부적 요인을 기준으로 정의할 수 있으며, 내부적 우선순위로는 제한 시간, 기억장소 요청량, 사용 파일 수, 입출력/프로세서 처리 비율 등이 있으며, 외부적 우선순위는 프로세스의 중요성, 고객 등급, 부서, 정책적인 요인 등이 있다.

우선순위 스케줄링 또한 선점과 비선점이 존재하며,

• 선점일 경우, 실행 중인 프로세스보다 방금 도착한 프로세스의 우선순위가 최고로 높다면 중단 뒤, 문맥교환이 일어난다.

• 비선점일 경우, 단순히 준비큐의 맨 앞 순번으로 해당 프로세스가 배치된다.

보통 그림 6-14처럼 우선순위 별로 준비큐를 가지고 있으며 높은 우선순위의 준비큐가 비면 다음 준비큐의 프로세스가 처리되는 방식이다.

우선순위 스케줄링의 주요 단점은 무한 정지와 기아이다. 실행 준비는 했으나 우선순위가 높은 프로세스가 계속 들어오면 우선순위가 낮은 프로세스는 무한정 기다려야한다.

이를 막기 위해 오래 대기하는 프로세스들의 우선순위를 점차 높이는 에이징(aging) 방법을 이용한다.

4 라운드 로빈 스케줄링

시분할 시스템을 위해 설계된 라운드 로빈(round-robin) 스케줄링은 작업을 규정 시간량(time quantum) 또는 시간 할당량(time slice)로 나누어 순환 큐(circular queue)에 존재하는 프로세스들을 돌아가며 한번에 한 프로세스에 정의된 규정 시간량만큼 프로세서를 제공하는 선점 방식이다.

장단	항목
장점	- 기아상태 발생하지 않음 - 실행 큐에 프로세스 수를 알고 있으면 구현이 쉬움 - 강한 상호작용과 프로세스의 짧은 응답시간, 특히 프로세스 최악의 응답시간을 예측 가능 - 작업 길이가 다양하면 작업을 마치지않고 규정 시간량을 마치고 다음 작업으로 이동하는 경우가 많아, 평균 대기시간이 선입선처리와 최소작업 우선 스케줄링보다 적음
단점	- 성능은 규정 시간량의 길이에 따라 달라짐, 너무 길면 선입선처리 성능, 너무 짧으면 문맥교환 오버헤드, 규정 시간량은 작업의 길이와 비슷해야 적절함 - 하드웨어 타이머 필요 - 미완성 작업은 각 규정 시간량을 마친 후 프로세서를 기다리므로 평균 처리 시간이 높음

보통 규정 시간량은 20밀리초~ 1000밀리초이며, 순환 큐인 준비 큐에는 선입선출 큐로 되어있어 새로 진입한 프로세스는 꼬리에 붙이게 된다.

• 리눅스의 경우 100밀리초, 윈도우 XP는 20밀리초이며, 우선순위 동작, 전면 작업, 백그라운드 작업에 따라 크기가 변한다.

준비큐 맨 앞의 프로세서가 할당된 프로세스는 두 가지 경우가 있다.

• 규정 시간안에 작업을 마친 경우, 준비큐의 다음 프로세스에게 넘긴다

• 현재 실행 중인 프로세스의 실행 시간이 규정 시간량보다 긴 경우, 규정 시간량이 지나면 운영체제에 의해 인터럽트가 발생하고 프로세스의 레지스터들은 해당 PCB에 저장되고 준비 큐의 꼬리에 입력된다. 이후 스케줄러는 다음 프로세스의 작업을 가져온다.

규정 시간량이 5인 라운드 로빈 스케줄링의 예시를 들어보자.(그림 6-15)

프로세스	도착 시간	실행 시간
$P_1$	0	10
$P_2$	1	28
$P_3$	2	6
$P_4$	3	4
$P_5$	4	14

✍ 라운드 로빈 스케줄링 예시

만약 더 이상 대기하는 프로세스가 없다면 인터럽트없이 연속해서 프로세스가 작업할 수 있다.

라운드 로빈의 평균 반환 시간은 36.8이며, 평균 대기 시간은 24.4이다.

라운드로빈은 규정 시간량을 넘길 경우 인터럽트 이후 다음 프로세스로 대치하므로 선점 스케줄링이며, 프로세스의 수를 n, 규정 시간량을 q라고 할 때, 각 프로세스는 대기 시간을 최대 $(n-1)\times q$ 이상 넘기지 않는다. 따라서 적절한 규정 시간량 설정은 성능에 크게 관여한다.

대부분의 대화식 프로세스는 입출력을 제외하면 규정시간량 이상 사용하지 않으며, 입출력 요청에 프로세서를 사용하고 대기한다. 따라서 규정 시간량은 입출력까지의 계산 시간 보다 커야 입출력 활용도가 극대화되고 반응 빠르다.

규정시간량이 매우 크면 작업을 완료할 충분한 시간을 얻게되므로, 선입선출 방식과 비슷한 성능을 가지게 되고, 너무 작으면 프로세서를 나누어 공유하는 것처럼 보이지만 오버헤드가 커진다. 또한 적어도 문맥 교환에 소요하는 시간보다는 커야 한다.

최적 규정 시간량은 시스템 특성, 오버헤드, 프로세스에 따라 다르며, 보통 대화식 프로세스가 적절한 시간에 반응을 보여주도록 보장하게 설정한다.

프로세스의 반환시간 또한 규정시간량에 영향을 받으며 보통 프로세스들이 단일 규정 시간 내에 작업을 끝마칠 수 있으면 반환시간이 줄어든다.

• 예를 들어 실행시간이 10인 프로세스 3개가 있을 경우, 규정시간이 1이면 평균 반환 시간은 29이지만, 규정시간이 10이면 평균 반환시간은 20이다.

5 다단계 큐 스케줄링

다단계 큐(MLQ, MultiLevel Queue) 스케줄링은 각 작업을 서로 다른 묶음으로 분류하여 분류하는 방식이다.

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

예를 들어 전면 작업(포어그라운드 작업, foreground task)과 후면 작업(백그라운드 작업, background task)는 두 유형의 요청 반응시간이 다르므로 서로 다르게 스케줄링되며 보통 전자가 우선순위가 높다.

다단계 큐 스케줄링은 준비 큐를 종류별로 여러개 분할해 둔뒤, 메모리 크기나 프로세스 형태에 따라 프로세스를 큐잉하며, 각 큐는 독자적인 스케줄링 알고리즘을 가질 수 있다.

예를 들어 전면 작업 큐는 즉각적인 반응을 위해 라운드로빈 알고리즘을, 후면 작업 큐는 선입선처리를 할 수 있다.

큐 사이의 스케줄링은 보통 선점 우선순위 스케줄링을 이용한다.(그림 6-15)

무조건 우선순위 높은 프로세스가 남아있는한 낮은 프로세스가 실행되지 않는 절대적인 우선순위 스케줄링이나 낮은 우선순위의 큐는 더 적은 시간을 할당받는 스케줄링도 가능하다.

6 다단계 피드백 큐 스케줄링

다단계 피드백 큐(MLFQ, MultiLevel Feedback Queue)에서는 다단계 큐에 작업이 큐 사이를 이동할 수 있어 융통성을 확보한 방식이며, 가장 일반적인 스케줄링 방식이다.

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

예를 들어 실행시간이 긴 작업은 평균 대기시간을 낮추기 위해 낮은 우선순위로 보내거나, 입출력이나 전면 작업같이 빠른 반응이 중요한 작업은 우선순위가 높은 큐에 보낼 수 있다.

기아상태를 방지하기 위한 에이징 또한 우선순위 큐를 높은 곳으로 옮기는 방법으로 구현할 수 있다.

또한 그림 6-16 처럼 우선순위가 높은 큐는 규정 시간량을 적게두고, 우선순위가 낮은 큐는 규정 시간량을 크게 두게 설정한다. 이를 통해 자원의 공정성을 어느 정도 해결한다.

프로세스	실행 시간
$P_1$	30
$P_2$	20
$P_3$	10

✍ 다단계 피드백 큐 예시

프로세스가 오랫동안 점유할 경우 큐가 이동됨에 따라 간트차트 아래 시간의 차이가 벌어진다.

다단계 피드백 큐의 평균 반환시간은 48.333이며, 평균 대기시간은 28.333이다.

보통 다단계 피드백 큐는 다음에 따라 정의한다.

• 큐 수

• 각 큐에 대한 스케줄링

• 높은 우선순위의 큐로 격상시키는 시기의 결정법

• 낮은 우선순위의 큐로 격하시키는 시기의 결정법

• 프로세스들이 어느 큐에 들어갈 것인지 결정하는 법

• 프로세스가 서비스를 받는 시기를 결정하는 법

단점은 설계와 구현이 복잡하다.

7 HRN 스케줄링

HRN(Highest Response-ratio Next) 스케줄링은 우선 순위를 서비스 시간과 대기 시간에 대한 함수로 계산하여 적용 하는 비선점 스케줄링 방식이다.

장단	항목
장점	- 자원을 효율적으로 활용한다. - 기아가 발생하지 않음
단점	오버헤드가 높을 수 있음

최소작업 우선 스케줄링의 약점인 긴 작업과 짧은 작업 간의 지나친 불평들을 보완하기 위해 만들어졌다.

\[우선순위=\frac{서비스\ 받을\ 시간 + 대기\ 시간}{서비스\ 받을\ 시간}\]

우선 순위는 위와 같은 함수를 통하여 결정되며 따라서 서비스 받을 시간이 길수록 우선순위가 낮으며, 대기시간이 길수록 우선순위가 차차 높아진다.

8 다중 프로세서 스케줄링

프로세서가 여러 개가 되면 스케줄링은 더욱 복잡해진다. 각 프로세서마다 독자적인 큐와 스케줄링이 있으므로 프로세서가 다르면 선택 가능한 프로세스가 제한되므로, 프로세서 별로 분류하고 스케줄링해야 한다.

예를 들어 IBM 시리즈/1에서는 Vax 어셈블리어로 작성한 프로그램이 돌아가지 않는다.

하나의 시스템에 종류가 같은 프로세서가 여러 개이면 부하 공유 문제가 생긴다. (9절 스레드 스케줄링 참조)

다중 프로세스 스케줄링 구조

단일 프로세서가 아닌 다중 프로세서 환경에서의 스케줄링 기법에 대해 알아보자.

준비큐 독립 구조

공유 부하를 프로세서 별로 준비 큐를 독립시켜 해결할 수 있다.

+ 각 프로세스는 각 프로세서의 큐에 분산되기 때문에 스케줄링 오버헤드가 적다.

• 프로세스가 40개이면 스케줄링 비용이 기하급수적으로 커지지만 이를 4개 프로세서가 10개씩 나누면 오버헤드가 줄어든다.

- 준비 큐 상황이 서로 달라, 어떤 프로세서는 준비 큐가 비어 유휴, 어떤 프로세서는 바쁠 수 있다.

공동 준비큐 구조

각 프로세서는 공통의 준비 상태 큐에서 실행할 프로세스를 유일하게 하나 선택하여 프로세스 큐로 보낸다.

+ 공통 준비큐는 강결합된 공유 메모리 구조에서는, 모든 프로세서가 모든 프로세스의 문맥 정보를 이용할수 있다.

+ 프로세스 큐의 존재로 인해 프로세스가 메모리에 적재되는 동안 다른 프로세서에서 작업을 실행할 수 있으며, 각 프로세서가 독립적인 스케줄링과 오버헤드를 가질 수 있다.

이때 스케줄링 방법은 크게 두 가지가 있다.

• 프로세서 자신이 스스로 스케줄링, 각 프로세서는 공동 큐에서 가져온 프로세스 하나를 겹치지 않게 가져오고, 단일 프로세서 스케줄링을 실시한다.

  - 이 방법은 스케줄링이 복잡하고 오버헤드가 증가할 수 있다.

• 비대칭 다중 처리(AMP, Asymmetric MultiProcessing): 프로세서 하나가 다른 모든 프로세서의 스케줄러를 지정하는 주종(Master/Slave) 구조

  시스템 호출, 핵심 커널 기능 등의 시스템 프로세스와 스케줄링은 주 프로세서가 담당, 사용자 프로세스는 나머지 종 프로세스가 담당. 사용자가 입출력 호출 등이 필요하면 주 프로세스에 종 프로세스가 요청

  + 기존의 단일 프로세서 다중 프로그래밍과 비슷한 방법

  + 주 프로세서가 자원 관리를 통해 자원 충돌 해결

  - 주 프로세서에 문제 생기시 전체 시스템 정지

  - 주 프로세서에 과중하게 오버헤드가 일어날 수 있음

9 스레드 스케줄링

동일한 주소 공간에 동시에 실행할 수 있는 스레드들로 응용 프로그램의 입출력과 프로세서 처리를 중첩할 수 있다.

스레드의 문맥교환은 프로세스 문맥 교환보다 오버헤드가 적어 성능을 항상시킬 수 있다.

멀티 프로세싱, 스레딩 좀더 알아보기!

부하 공유(load sharing)

부하 공유는 단일 프로세서 환경에서 주로 사용하며, 프로세서를 특정 프로세스(스레드들의 집합) 하나에 할당하지 않고 전역 큐에서 프로세서를 유지하며, 대기 중인 프로세서는 전역 큐에서 스레드 한개를 선택하는 방법이다.

장단	항목
장점	- 부하는 프로세서에 균등하게 분산하며, 실행 대기 중인 작업에는 분산하지 않음 - 스레드를 제어하는 중앙 제어 스케줄러 없이 사용할 때는 현재 작업을 진행한 프로세서에서 다음 작업을 선정 - 전역(공유) 큐는 선입선처리나 우선순위 방법을 이용하여 구성
단점	- 중앙 큐는 상호배제 방법으로 접근하는 메모리 영역으로, 많은 프로세서가 동시에 작업을 찾는다면 중앙 큐는 병목 지점이 될 수 있음 - 선점된 스레드들은 동일한 프로세서 상에서 실행 재개가 힘듬 - 프로그램의 스레드 사이에 밀접한 협조가 요청되면, 관련된 프로세스 문맥 교환은 성능을 심각하게 저하

갱 스케줄링(gang scheduling)

갱 스케줄링은 관련된 스레드의 집합을 일대일 대응 원칙에 따라 프로세서 집합에서 동시 실행하게 하는 스케줄링 방법이다. 즉, 단일 프로세스에 속한 스레드들을 한꺼번에 스케줄링한다.

주로 스레드들이 병행 실행되지 않으면 다른 스레드들이 기다려야 하는 프로그램에 사용한다. 또한 한 번의 스케줄링 결정이 다수의 프로세서와 프로세스에 영향을 주므로 오버헤드도 적다.

아래의 전용 프로세서 할당과 함께 프로세서 단편화 문제를 회피할 수 있다.

• 프로세서 단편화 : 대기하고 있는 프로세스의 요청을 받기에는 프로세서의 자원이 충분하지 않아 프로세서를 할당할 수 없는 단편화

전용 프로세서 할당

부화 공유와는 반대로 스레드들을 실행 점담 프로세서에 할당해 정의된 스케줄링을 제공하는 방법이다.

다중 스레드에서의 문제는 다음과 같다.

• 각 프로그램은 실행되는 동안 스레드와 동일한 수의 프로세서를 할당받으므로, 스레드 수가 적다면 프로세스가 낭비된다.

• 한 응용 프로그램의 스레드를 다른 스레드의 동기화나 입출력 대기 때문에 보류되면 해당 스레드의 프로세서가 쉬게 된다.

따라서 활성화된 스레드 수를 프로세서와 동일한 수로 제한해 효율성을 높인다.

효율적인 할당으로 프로세서 단편화 문제를 회피할 수 있다.

동적 스케줄링

동적 스케줄링은 스레드 수를 실행 도중 동적으로 변경하여 시스템 이용률을 높일 수 있도록 부하 조절을 허용하는 방법이다.

운영체제는 프로세서들을 각 프로세스에 할당하고 프로세스들은 스레드 처리를 위해 할당된 프로세서를 사용한다.

프로세스의 자원을 선점할때, 어느 스레드를 일시 중지할 것인지는 각 응용 프로그램 실행 라이브러리 루틴들이 결정한다.