6. 프로세스 스케줄링

---

 

 

1. 스케줄링의 이해

1.1) 스케줄링 개념

스케줄링이란, 여러 프로세스가 번갈아 사용하는 자원을 어떤 시점에 어떤 프로세스에 할당할 것인지를 결정하는 것이다.

다중 프로그래밍을 가능하게 하는 동작 기법으로, 프로세스에 컴퓨터 자원을 적절히 배치하여 시스템 성능을 개선하는 역할을 한다.

즉, 다중 프로그래밍에서 프로세서를 할당할 프로세스를 선택할 때 필요한 전략을 스케줄링이라고 할 수 있다.

 

1.2) 프로세서 스케줄링

프로세서 자원에 대한 스케줄링을 프로세서 스케줄링이라고 부른다.

다중 프로그래밍 시스템에서 시스템의 목표를 달성할 수 있도록 프로세서를 할당하는 일련의 과정이다.

프로세스들에게 프로세서를 효율적으로 할당, 시스템의 작업 처리 능력을 향상하며 응답 시간을 최소화하는 것이 목적이다.

스케줄링이 불필요한 프로세스

• 인터럽트 처리, 오류 처리, 사용자의 시스템 호출 등의 사전 처리 프로세스 등

스케줄링이 필요한 프로세스

• 사용자 프로세스, 시스템 호출로 발생하는 시스템 프로세스 등

 

1.3) 스케줄링의 목적 

자원에 대한 스케줄링의 목적은 다음과 같다. 

• 자원 할당의 공정성 보장
• 단위 시간당 처리량 최대화
• 적절한 반환 시간 보장
• 예측 가능성 보장
• 과부하 방지
• 자원 사용의 균형 유지
• 반환 시간과 자원 활용도 간의 균형 유지
• 무기한 연기 방지
• 우선순위에 따른 처리
• 서비스 사용 기회 확대
• 서비스 수 감소 방지

 

1.4) 스케줄링의 기준 요소

스케줄링 목적을 달성하기 위해서는 프로세스 동작을 고려해야 한다.

프로세스는 시작 ~ 종료까지 실행과 입출력 대기를 순환 반복한다.

• 프로세서 버스트: 프로세스가 프로세서를 차지하고 명령어를 실행하는 단계
• 입출력 버스트: 프로세스가 CPU를 반환하고 입출력을 대기하는 단계

입출력이 성공적으로 이루어졌으면, 프로세서 버스트로 복귀한다.

프로세서 버스트 차이에 따라 프로세서 중심 프로세스와 입출력 중심 프로세스로 나눠진다.

시스템 성능 향상을 위해서는 2가지 유형이 적절하게 혼합될 수 있도록 스케줄링해야 한다.

 

1.5) 프로세서 중심 프로세스

프로세서 중심 프로세스(Processor-Bound Process)는 프로세서 버스트가 매우 길다.

즉, 프로세서를 1번 차지하면, 점유 시간이 매우 길다.

 

1.6) 입출력 중심 프로세스

입출력 중심 프로세스(I/O Bound Process)는 프로세서 버스트가 짧다.

즉, 프로세서를 1번 차지하면, 점유 시간이 짧다.

 

1.7) 스케줄링 버스트 분포

스케줄링 버스트 분포는 적절한 프로세서 스케줄링 알고리즘을 선택하는 데 중요한 기준이 된다.

위의 버스트 분포 그래프를 보면, 짧은 프로세서 버스트 작업이 초반에 다수 이루어진다.

짧은 프로세서 버스트 작업이 끝난 이후부터는 긴 프로세서 버스트 작업이 매우 낮은 빈도수로 이루어진다.

이를 바탕으로 추측해보면, 입출력 중심 프로세서를 먼저 처리한 뒤, 그 이후에 프로세서 중심 프로세스들이 처리된다는 것을 알 수 있다.

 

1.8) 프로세스 스케줄링의 단계

1단계 스케줄링이란, 수행 빈도가 낮은 장기 스케줄링(Long-Term Scheduling)으로, 시스템 자원을 사용할 작업을 결정하는 작업 스케줄링이다.

처리할 수 있는 양보다 많은 수의 작업이 들어왔을 때, 어떤 작업에 자원을 얻고자 경쟁하도록 만들 것인지를 결정한다.

임의의 시간에 시스템에 존재하는 프로세스 총 수를 지정한다.

일괄 처리(Batch Processing)하는 대형 메인 프레임 등에서 사용된다.

작업 스케줄링(Job Scheduling) 또는 승인 스케줄링(Admission Scheduling) 등이 있다.

2단계 스케줄링이란, 수행 빈도가 중간인 중기 스케줄링(Medium-Term Scheduling)으로, 시스템 오버헤드에 따라 일시 중지/재개할 프로세스를 결정하는 작업 스케줄링이다.

어떤 프로세스가 프로세서를 얻으려고 경쟁할 수 있는지를 결정한다.

시스템 부하 변동에 따라 활성화/일시 정지할 프로세스를 선정한다.

3단계 스케줄링이란, 수행 빈도가 매우 높은 단기 스케줄링(Short-Term Scheduling)으로, 준비 상태의 프로세스에 프로세서를 할당하기 위한 작업 스케줄이다.

준비 상태의 프로세스들 중에서 프로세서를 할당할 프로세스를 결정한다.

프로세서 스케줄링이 이루어진다.

 

1.9) 스케줄러의 종류와 역할

단기 스케줄러는 준비 큐에 저장된 프로세스들 중, 어떤 프로세스에 프로세서를 할당할 것인지를 결정한다.

실행할 프로세스를 수시로 선택하므로, 스케줄러 속도가 매우 빨라야 한다.

장기 스케줄러는 시스템 자원이 필요하다고 요청하여 준비 큐에 들어가게 될 프로세스들을 스케줄링한다.

시스템에 새로운 작업이 분 단위로 들어오므로, 단기 스케줄러에 비해 상대적으로 드물게 수행된다.

디스패처는 프로세서 스케줄러(단기 스케줄러)에 포함된 요소이다.

단기 스케줄러가 선택한 프로세스에 실질적으로 프로세서를 할당하는 역할을 수행한다.

PCB에 저장된 프로세스의 레지스터 값을 프로세서에 적재(문맥 교환)한다.

시스템 상태에서 사용자 상태로 전환한다.

디스패처는 자주 실행되므로, 처리 속도가 매우 빨라야 한다.

중기 스케줄러는 다중 프로그래밍의 정도(메모리에 있는 프로세스의 수)를 낮추어서 시스템 부하를 조절한다.

프로세스를 일시 정지시켜 메모리에서 제거한다. (스왑 아웃)

일시정지 프로세스가 다시 메모리를 차지하면, 중단되었던 지점부터 실행된다. (스왑 인)

프로세서 중심/입출력 중심 프로세스의 혼합 비율 조정에도 이용된다.

 

1.10) 준비 큐와 다양한 입출력 장치 큐

스케줄링은 작업을 하기 위해 줄을 서 있는 작업 목록들을 관리하는 것을 의미한다.

작업 목록 리스트를 관리하기 위해서는 다음과 같은 큐(Queue)가 필요하다.

• 준비 상태가 돼서 CPU 차지를 대기하는 준비 큐
• 대기 상태인 프로세스들을 나타낼 수 있는 각 장치별 입출력 장치 큐
  

각각의 큐들은 PCB 리스트로 구성된다.

 

---

 

2. 선점 스케줄링과 비선점 스케줄링

2.1) 선점 스케줄링 (Preemptive Scheduling)

프로세스가 프로세서를 할당받아 실행하는 도중에 시스템이 프로세서를 강탈할 수 있다.

1개의 프로세스가 장시간 프로세서를 독점하는 상황을 방지한다.

대화식 시분할 시스템에서 빠른 응답 시간을 가능하게 한다.

우선순위가 높은 프로세스가 긴급한 처리를 요청할 때 유용하다.

프로세스를 중단하고 교환하는 과정에서 오버헤드가 발생한다.

 

2.2) 비선점 스케줄링 (Non-Preemptive Scheduling)

프로세스가 프로세서를 할당받아 실행하는 도중에 시스템이 프로세서를 강탈할 수 없다.

모든 프로세스들을 공정하게 관리한다.

우선순위에 영향을 받지 않기 때문에, 응답 시간 예측에 용이하다.

일괄 처리(Batch Processing) 시스템에 유용하다.

우선순위가 높은 프로세스(또는 짧은 프로세스)들이 우선순위가 낮은 프로세스(또는 긴 프로세스)가 끝나기를 오랫동안 기다리는 경우가 발생할 수 있다.

 

---

 

3. 스케줄링 알고리즘 선택 기준

3.1) 프로세서 사용률

A, B 프로세스 중에서 어떤 프로세스를 먼저 실행해야 하는가?

CPU가 도착한 프로세스 중 A 프로세스를 먼저 실행한다면?

• A를 5칸 실행 후 I/O를 위해 대기
• B가 1칸 실행 후 I/O를 위해 대기
• CPU가 1칸 휴먼 상태에 빠짐
• A를 1칸 실행 후 종료
• CPU가 3칸 휴먼 상태에 빠짐
• B를 2칸 실행 후 종료

CPU가 도착한 프로세스 중 B 프로세스를 먼저 실행한다면?

• B가 1칸 실행 후 I/O를 위해 대기
• A가 5칸 실행 후 I/O를 위해 대기
• B가 2칸 실행 후 종료
• A가 1칸 실행 후 종료

이처럼 어떤 프로세스를 먼저 실행하느냐에 따라서 CPU 사용 효율이 달라질 수 있다.

 

3.2) 프로세스 반환시간, 대기시간, 반응시간

3개의 프로세스 A, B, C가 동시에 도착해 시분할로 실행되는 경우, 각각의 실행 시간은 다음과 같다.

• A 프로세스 실행 시간: 4
• B 프로세스 실행 시간: 2
• C 프로세스 실행 시간: 4

프로세스 C의 경우, 반환 시간, 대기 시간, 반응 시간은 다음과 같다.

• 반환 시간(도착~프로세스 처리 종료): 10
• 대기 시간(해당 프로세스가 다시 실행되기까지 걸리는 시간): 6
• 반응 시간(최초 응답까지 걸리는 시간): 2

 

3.3) 스케줄링 알고리즘 비교할 때 사용하는 기준들

프로세서 사용률(Processor Utilization)

• 프로세서의 유휴 시간을 줄여 프로세서 사용률을 높인다.

처리율(Throughput)

• 단위 시간당 완료되는 작업 수를 최대화한다.

반환 시간(Turnaround Time)

• 작업 제출 후, 완료까지의 소요 시간을 최소화한다.
• 반환 시간은 큐 대기 시간, 실행 시간, 입출력 시간 등을 모두 포함한다.

대기 시간(Waiting Time)

• 프로세스가 준비 큐에서 대기하는 시간을 최소화한다.

반응 시간(Response Time)

• 작업 요청부터 반응 시작(1번째 응답)까지의 시간 간격을 최소화한다.

대화식 작업에서는 반응 시간 최소화가 중요하다.

 

---

 

4. 스케줄링 알고리즘

프로세서 스케줄러는 스케줄링 알고리즘에 따라 프로세서를 할당하는 역할을 한다.

여기서는 단일 프로세서 시스템을 중심으로 스케줄링 알고리즘을 다룬다.

원칙적으로는 1개의 프로세스가 여러 프로세서 버스트를 가진다.

여기서는 간략하게 프로세서 버스트 1개의 길이를 프로세스 길이, 또는 프로세스 실행 시간이라고 칭한다.

 

4.1) 선입 선처리 스케줄링 (FCFS, First-Come First-Served Scheduling)

준비 큐에 도착한 순서대로 프로세서를 할당하는 알고리즘을 선입 선처리 스케줄링이라고 부른다.

비선점형 스케줄링(Non-Preemptive Scheduling) 방식이다.

프로세서 스케줄링 알고리즘 중 가장 단순한 방법으로 알고리즘이 간단하다.

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

준비 큐의 모든 프로세스가 결국은 실행되므로, 기아 상태가 없는 공정한 정책이다.

비선점형(Non-Preemptive) 스케줄링이므로, 대화식 프로세스에는 부적합하다.

긴 프로세스가 뒤의 프로세스들을 지연시키는 경우, 평균 대기 시간이 길어지고, 시스템 전체 자원 사용률도 떨어진다.

긴 프로세스가 실행되는 동안, 짧은 프로세스의 대기 시간이 길어져 호위 효과가 발생할 수 있다.

호위 효과란, 긴 프로세스 1개가 프로세서를 떠나는 것을 짧은 프로세스 여러 개가 오랫동안 기다리는 현상을 말한다.

선입 선처리 스케줄링 동작 예시는 다음과 같다.

P1의 경우, 가장 먼저 도착했으므로 10초 동안 실행되고 반환한다.

즉, 반환 시간은 10이며 대기 시간은 0이다.

P2의 경우, 1초에 도착해 P1이 도착할 때까지 기다린 뒤 실행되고 반환한다.

도착한 시간 1초, 종료 시간 38초이므로, 반환 시간은 38 - 1 == 37이다.

대기 시간은 시작 시간 10초, 도착 시간 1초이므로, 10 - 1 == 9이다.

선입 선처리 스케줄링 성능을 분석해보면 다음과 같다.

동적인 상황이며, CPU 중심 프로세스 1개, 입출력 중심 프로세스 3개로 가정한다.

CPU 중심 프로세스가 CPU를 할당받아 실행되는 동안 입출력 중심 프로세스는 I/O를 마치고 준비 큐로 이동한다.

이때, 입출력 장치는 휴먼 상태이다.

CPU 중심 프로세스가 CPU 사용을 마친 후, 입출력 장치로 이동한다.

입출력 중심 프로세스가 CPU를 잠깐 사용한 뒤, 곧바로 입출력 장치 준비 큐로 이동한다.

이때, CPU는 휴먼 상태이다.

CPU 중심 프로세스가 프로세서를 오랫동안 사용하고 있을 때, 나머지 입출력 중심 프로세스 3개는 프로세서 진입을 대기한다.

CPU 중심 프로세스가 입출력 장치에 들어갔을 때, 입출력 중심 프로세스 3개는 아주 짧은 시간 동안만 프로세서를 사용한 뒤, 다시 입출력 장치 진입을 대기한다.

이를 보면 입출력 중심 프로세서 3개는 실행보다 준비 큐 대기에 시간을 더 많이 소모한다는 것을 알 수 있다.

즉, 작업이 진행되는 동안 정체되는 상황이 자주 발생하여 효율적이지 못하다.

 

4.2) 최소 작업 우선 스케줄링 (SJF: Shortest Job First Scheduling)

실행 시간이 가장 짧은 프로세스에 프로세서를 할당하는 알고리즘을 최소 작업 우선 스케줄링이라고 부른다.

일괄 처리 시스템에서 Job Scheduling(1단계 스케줄링)에 주로 사용된다.

준비 큐의 머리(Head)에 있는 PCB가 가장 먼저 프로세서를 점유한다.

새로운 프로세스가 유입되면, 프로세서 버스트 시간을 비교해 준비 큐에서 위치를 결정한다.

프로세서 버스트가 짧은 프로세스가 준비 큐의 머리에 가장 가까우며, 프로세서 버스트가 길수록 꼬리에 가까워진다.

항상 실행 시간이 짧은 작업을 신속하게 실행하므로, 평균 대기 시간이 항상 짧다.

짧은 작업이 항상 우선 실행되도록 설정하므로 불공정하다. (기아 상태 발생 가능)

실행 시간을 예측하기가 어려워 실용적이지 않다.

최소 작업 우선 스케줄링의 총 대기 시간을 계산해보면 다음과 같다.

어떤 프로세스를 먼저 수행하냐에 따라서 총 대기 시간이 달라질 수 있다.

일반적으로 짧은 작업을 우선 처리하면, 다음과 같이 평균 대기시간을 줄일 수 있다.

 

4.3) 비선점형 최소 작업 우선 스케줄링 (Non-Preemptive SJF)

시분할 시스템에 부적합하다.

프로세스가 일단 실행 중이라면, 실행 시간이 더 짧은 프로세스가 도착해도 종료까지 강탈당하지 않는다.

 

4.4) 선점형 최소 작업 우선 스케줄링 (Preemptive SJF)

최소 잔여시간 우선(SRTF: Shortest Remaining Time First) 스케줄링이라고도 한다.

새로 도착한 프로세스 길이가 실행 중인 프로세스의 남은 실행 시간보다 짧으면, 새로 도착한 프로세스가 프로세서를 차지한다.

문맥 교환으로 인한 오버헤드가 증가한다.

 

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

우선순위가 가장 높은 프로세스에 프로세서를 할당하는 알고리즘.

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

우선순위가 높은 프로세스일수록 준비 큐 헤드에 가까우며, 새로운 프로세스가 유입되면 우선순위를 비교해 큐에서 위치를 결정한다.

최소 작업 우선 스케줄링은 일종의 우선순위 스케줄링이다.

즉, 짧은 프로세스일수록 우선순위가 높다.

우선순위는 내부적 또는 외부적으로 정의되며, 일정 범위의 수로 표현된다. (0~7 또는 0~4095)

내부적으로 정의된 우선순위는 제한 시간, 기억 장소 요구량, 사용 파일 수, 평균 프로세서 버스트에 대한 평균 입출력 버스트의 비율 등을 기반으로 결정된다.

외부적으로 정의된 우선순위는 프로세스의 중요성, 사용료를 많이 낸 사용자, 작업을 지원하는 부서 등 시스템 외적인 요인으로 결정한다.

우선순위 스케줄링은 각 프로세스의 상대적 중요성을 정확히 정의할 수 있다.

실시간 시스템에서 사용 가능하다.

무기한 연기(기아 상태)가 발생할 수 있다.

우선순위가 높은 프로세스들이 계속 들어오면 우선순위가 낮은 프로세스는 무기한 대기에 빠진다.

무기한 연기 문제 해결하려면 에이징 기법을 사용하면 된다.
(에이징 기법: 시스템에서 오래 대기한 프로세스 우선순위를 점진적으로 증가시킴)

 

4.6) 비선점형 우선순위 스케줄링(Non-Preemptive Priority Scheduling)

새로 도착한 프로세스 우선순위가 아무리 높아도 프로세서 강탈이 불가능하다.

대신 준비 큐 머리 부분에 삽입하여 바로 다음 실행이 가능하게 한다.

 

4.7) 선점형 우선순위 스케줄링

준비 큐에 새로 도착한 프로세스의 우선순위가 현재 실행 중인 프로세스의 우선순위보다 높으면 프로세서 강탈이 가능하다.

 

4.8) 라운드-로빈 스케줄링 (Round-Robin scheduling)

시분할 시스템을 위해 설계된 알고리즘을 라운드-로빈 스케줄링이라고 부른다.

Time Quantum 또는 Time Slice라고 부르는 작은 시간 할당량(규정 시간량)을 정의한다.

프로세스는 1번에 Time Quantum 동안만 프로세서를 차지할 수 있도록 한다.

선점형 스케줄링(Preemptive Scheduling) 방식이다.

즉, 프로세스가 Time Quantum보다 긴 실행 시간을 필요로 하면 프로세서를 강탈해 다음 프로세스에 할당이 가능하다.

모든 프로세스가 프로세서의 동일한 점유율, 대기 시간을 가지므로 공정하다.

기아 상태가 발생하지 않는다.

응답 시간이 짧다.

Time Quantum 크기에 따라 성능이 달라지므로, 적절한 크기 결정이 필요하다.

하드웨어 타이머가 필요하다.

준비 큐는 선입선출(First-In First-Out) 큐로 구현한다.

스케줄러는 준비 큐 맨 앞 프로세스(머리 프로세스)를 프로세서에 할당한다.

프로세스 실행 시간이 Time Quantum보다 긴 경우, Timer 인터럽트가 발생한다.

Timer 인터럽트가 발생하면 실행 중인 프로세스는 프로세서를 빼앗기고 준비 큐 맨 뒤에 삽입된다.

프로세스의 실행 시간이 Time Quantum보다 짧은 경우, Timer 인터럽트가 발생하지 않는다.

Time Quantum 내에 프로세스 실행을 마치므로, 프로세서를 자발적으로 반납한다.

라운드-로빈 스케줄링 예시를 살펴보면 다음과 같다.

Time Slice는 5초로 가정한다.

P1의 경우,

• 실행 시간은 10''이므로, Time Slice보다 크다.
• 도착 시간은 0''이므로, 도착 즉시 가장 먼저 실행된다.
• 처음 5초간 실행되고, Timer 인터럽트에 의해 준비 큐 맨 뒤에 삽입된다.
• P1은 0''에 도착해서 29''에 작업을 마치므로, 반환 시간은 0 + 29 == 29이다.
• P1은 최초 실행되는 프로세스이지만, Time Slice보다 실행 시간이 크므로 대기 시간이 존재한다.
• P1의 대기 시간은 최초 실행을 마친 5초에서 2번째 실행 시작인 24초까지이므로, 24 - 5 == 19이다.

P2의 경우,

• 실행 시간은 28''이므로, Time Slice보다 크다.
• 도착 시간은 0''이므로, P1 이후에 실행된다.
• P1이 Timer 인터럽트에 걸렸을 때, 프로세서를 강탈하고 5초 때부터 실행된다.
• P2는 1초에 도착해서 62초 때 작업을 마치므로, 반환 시간은 62 - 1 == 61이다.
• P2의 대기 시간은 (5 - 1) + (29 - 10) + (40 - 34) + (49 - 45) == 33초이다.

P3의 경우,

• 실행 시간이 6''이므로, Time Slice보다 크다.
• 도착 시간은 2''이므로, P2 이후에 실행된다.
• P2가 Timer 인터럽트에 걸렸을 때, 프로세서를 강탈하고 10초 때부터 실행된다.
• P3는 2초에 도착해서 35초에 작업을 마치므로, 반환 시간은 35 - 2 == 33초이다.
• P3의 대기 시간은 (10 - 2) + (34 - 15) == 33초이다.

P4의 경우,

• 실행 시간이 4''이므로, Time Slice보다 작다.
• 도착 시간은 3''이므로, P3 이후에 실행된다.
• P3이 Timer 인터럽트에 걸렸을 때, 프로세서를 강탈하고 15초 때부터 실행된다.
• P4는 Time Slice 내에 실행을 마치므로, 프로세서를 자진 반납한다.
• P4는 3초에 도착해서 19초에 작업을 마치므로, 반환 시간은 19 - 3 == 16초이다.
• P4의 대기 시간은 15 - 3 == 12초이다.

P5의 경우,

• 실행 시간이 14''이므로, Time Slice보다 크다.
• 도착 시간은 4''이므로, P4 이후에 실행된다.
• P3이 프로세서를 자진 반납하므로, 19초 때부터 실행된다.
• P5가 Timer 인터럽트로 인해 프로세서가 강탈당하면, 실행 순서는 P1으로 되돌아간다.
• P5는 4초에 도착해서 49초에 작업을 마치므로, 반환 시간은 49 - 4 == 45초이다.
• P5의 대기 시간은 (19 - 4) + (35 - 24) + (45 - 40) == 31초이다.

문맥 교환 시간이 라운드-로빈 스케줄링에 미치는 영향을 살펴보면 다음과 같다.

Time Quantum이 작을수록, 문맥 교환 횟수는 증가한다.

문맥 교환 또한 오버헤드이므로, 시간을 잡아먹은 요소이다.

문맥 교환에 소요되는 시간보다 Time Quantum이 더 작을 경우, 오히려 비효율적인 스케줄링 방법이 될 수도 있다.

즉, 라운드-로빈 스케줄링의 효과를 보기 위해서는 문맥 교환 시간보다 Time Quantum이 충분히 커야 한다.

Time Quantum이 지나치게 큰 경우,

• 프로세서를 1번 차지하면 프로세스 실행을 완료할 충분한 시간을 얻으므로, 라운드-로빈 방식이 FCFS 방식이 되어버린다.
• 이 경우, 긴 프로세스 점유 시간 때문에 짧은 점유 시간 프로세스들의 대기 시간까지 길어지고, 이는 평균 대기 시간을 길어지게 만드는 결과를 낳는다.

Time Quantum이 지나치게 짧은 경우,

• 문맥 교환으로 인한 오버헤드가 과도하게 커져서 시스템 성능이 떨어진다.
• 즉, 대부분의 프로세서 시간을 프로세스 임무 수행 대신, 문맥 교환 과정에 허비하게 된다.

최적의 Time Quantum 크기는 시스템 특성, 문맥 교환 오버헤드, 프로세스 특성에 따라 달라진다.

Time Quantum을 적당하게 설정하되, 대부분의 입출력 중심 프로세스의 실행 시간보다는 큰 것이 좋다.

대화식 프로세스가 도착했을 때, 적절한 시간 내에 반응할 수 있도록 보장하는 것이 중요하다.

Time Quantum이 대화식 프로세스의 프로세서 버스트보다 커야 대화식 프로세스에 빠르게 반응할 수 있으며, 입출력 장치 사용률도 높일 수 있다.

라운드-로빈 스케줄링의 Time Quantum을 매우 작게 설정하면 마치 n개의 프로세서가 1/n 속도로 실행되는 것처럼 보이게 만들 수 있다.

Ex) CDC(Control Data Corporation)에서 하드웨어 1세트와 레지스터 10세트를 두어, 빠른 프로세서 1개가 아닌 느린 프로세서 10개를 이용해 처리하는 것과 같은 효과를 얻는다.

 

4.9) 다단계 큐 스케줄링 (Multi-Level Queue Scheduling)

프로세스들을 서로 다른 유형으로 분류할 수 있을 때 사용하는 알고리즘을 다단계 큐 스케줄링이라고 부른다.

준비 큐를 프로세스 종류별로 여러 단계로 분할하고, 프로세스를 특성에 따라 특정 큐에 지정한다.

각 큐는 자신만의 독자적인 스케줄링 알고리즘을 지닌다.

큐 사이에도 스케줄링이 필요하다.

여기서 사용되는 스케줄링 방식은 고정된 우선순위의 선점형 스케줄링 방식이다. (Preemptive Scheduling)

각 큐는 낮은 단계의 큐보다 우선순위가 높다.

위 사진에서 일괄 처리 프로세스를 실행하려면, 상위 큐 3개(시스템 프로세스, 대화식 프로세스, 대화식 편집 프로세스)가 비어야 한다.

일괄 처리 프로세스 실행 중에 시스템 프로세스가 도착하면, 일괄 처리 프로세스는 프로세서를 강탈당한다.

다단계 큐 스케줄링은 프로세스 특성에 맞는 스케줄링이 가능하다.

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

낮은 우선순위의 큐에 있는 프로세스들이 무기한 대기에 빠질 수 있다.

큐들 사이에 시간을 나누어 사용하면, 무기한 대기를 막을 수 있다.

즉, 각 큐는 프로세스 시간의 일정량을 할당받아서, 그 시간 내에 큐에 있는 프로세스들을 스케줄링하는 것이다.

프로세스가 시스템에 일단 진입하면, 특정 단계의 큐에 영구 고정된다.

이는 스케줄링 부담은 적으나, 융통성이 떨어지며, 프로세스 특성 변화를 반영하지 못한다.

 

4.10) 다단계 피드백 큐 스케줄링 (Multi-Level Feedback Queue Scheduling)

준비 큐를 프로세서 버스트 특성에 따라 여러 단계 큐로 분리하고, 프로세스가 큐 사이를 이동할 수 있도록 하는 알고리즘을 다단계 피드백 큐 스케줄링이라고 부른다.

입출력 중심 프로세스와 대화식 프로세스를 높은 우선순위 큐에 넣고, 프로세서 중심 프로세스는 낮은 우선순위 큐에 넣는다.

높은 우선순위 큐가 완전히 비어야, 낮은 우선순위의 큐에 있는 프로세스가 실행될 수 있다.

다단계 큐 스케줄링보다 융통성이 큰 방법이다.

프로세스의 특성을 파악하여 적절한 큐에 배치할 수 있고, 특성이 변해도 적절한 대처가 가능하다.

다단계 큐 스케줄링은 매우 유연하여 스케줄러를 시스템 특성에 맞게 구성할 수 있다.

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

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

다단계 피드백 큐 스케줄링은 가장 일반적, 복잡한 프로세서 스케줄링 알고리즘이다.

하지만 설계 및 구현이 매우 어려우며, 상황에 따라 기아 상태가 발생할 수 있다.

특정 큐의 Time Quantum보다 프로세서 점유 시간이 더 긴 작업은 프로세서를 빼앗기고, 1단계 낮은 우선순위 큐로 이동한다.

낮은 우선순위 큐로 이동할 경우, Time Quantum이 증가되어 프로세스가 더 오래 실행할 수 있도록 한다.

낮은 우선순위의 큐에서 대기하는 작업은 기아 상태에 빠질 가능성이 있다.

이를 해결하기 위해서는 특정 큐에서 오래 대기한 프로세스의 우선순위를 높이면 된다.

이를 에이징(Aging) 기법이라고 부른다.

다단계 피드백 큐 스케줄링 알고리즘을 정의하는 요소는 다음과 같다.

• 큐의 개수
• 각 큐의 스케줄링 알고리즘
• 프로세스를 좀 더 높은 우선순위 큐로 올리는 시기 결정 방법
• 프로세스를 좀 더 낮은 우선순위 큐로 내리는 시기 결정 방법
• 프로세스가 어느 큐에 들어갈 것인가를 결정하는 방법

위의 요소들은 특정 시스템에 맞게 적용할 수 있다.

 

4.11) HRN 스케줄링 (Highest Response-Ratio Next Scheduling)

길이가 짧을수록, 대기 큐에서 대기하는 시간이 길수록 우선순위가 높아지는 스케줄링 방식이다.

최소 작업 우선(SJF) 기법의 약점이었던 긴 작업, 짧은 작업 간의 지나친 불평등을 어느 정도 보완했다.

일종의 비선점형 우선순위 스케줄링(Non-Preemptive Priority Scheduling)이다.

HRN 기법의 가변적 우선순위는 다음 식에 따라 계산된다.

대기한 시간이 같을 경우, 서비스를 받을 시간이 짧을수록 우선순위가 높다.

서비스를 받을 시간이 긴 작업도 대기한 시간이 길어지면 우선순위가 높아진다.

이 덕분에 기아 상태가 발생하지 않는다.

 

---

 

8. 다중 프로세서 스케줄링

8.1) 강 결합 다중 처리 시스템의 프로세서 스케줄링

강 결합 다중 처리 시스템이란, 여러 프로세서가 하나의 메모리를 공유하여 사용하는 시스템이다.

 

8.2) 대칭 다중처리 (SMP: Symmetric Multi Processing)

프로세서들이 준비 큐 1개를 공유한다.

각 프로세서가 각자 스케줄링 결정을 내린다.

 

8.3) 비대칭 다중처리 (AMP: Asymmetric Multiprocessing)

1개의 프로세서(Master Server)가 모든 스케줄링 결정을 내린다.

 

8.4) 다중 프로세서 스레드 스케줄링과 프로세서 할당 방법

• 부하 공유: 쉬고 있는 프로세서는 전역 큐에서 스레드 1개를 선택한다.
• 전용 프로세서 할당: 특정 스레드는 특정 프로세서에서만 실행되게 한다.
• 갱 스케줄링: 1개의 프로세스에 속한 스레드들이 동시에 실행될 수 있도록 프로세서 집합을 동시에 스케줄링한다.
• 동적 스케줄링: 프로세서 이용률을 높이기 위해 운영체제가 동적으로 부하를 조절한다. 즉, 각 프로세서 준비 큐 상 스레드 수 균형 조정을 위해 준비 큐 간 스레드 이동을 허용

 

---

 

9. 스케줄링 알고리즘 평가

스케줄링 알고리즘 평가는 다음과 같이 프로세스 5개가 있다고 가정할 때, 선입 선처리, 최소 작업 우선, 라운드-로빈 스케줄링의 평균 대기 시간을 조사해 평가한다.

 

9.1) 선입 선처리 스케줄링 (FCFS)

 

9.2) 최소 작업 우선 스케줄링 (SJF)

 

9.3) 라운드 로빈 스케줄링

이때, Time Quantum은 3이다.

 

---

 

---

수고하셨습니다!

---