Chapter 05. CPU Scheduling

1. CPU 스케줄링 이란?

CPU를 멀티프로그래밍에 있어 프로세스 간에 교환을 시켜 CPU를 최대한 효율적으로 쓰게 하는 것.

즉, 어떤 프로세스가 대기할 경우 회수해서 다른 프로세스에 할당함

(최신 운영체제에서는 프로세스가 아닌 커널 수준 스레드를 한다.)

 

 

2. CPU I/O Burset Cycle

프로세스는 CPU Burst로 시작하고 뒤이어 I/O Burst가 나온다.

이를 지속적으로 사이클을 통해 반복한다.

 

<I/O Bound Job과 CPU Bound Job의 Cycle Graph>

I/O Bound Job은 burst duration 즉 프로세서가 할당하는 시간이 짧지만 빈도수가 매우 잦다.

반면에, CPU Bound Job은 프로세서가 할당하는 시간은 길지만 빈도수가 적다. 

 

 

3. CPU Scheduler

CPU가 아무것도 하지 않을 때 OS에서 Ready Queue(CPU는 raedy 상태에 있는 프로세스만 CPU에 줘야 함)에 있는

프로세스 중 하나를 실행해야 한다.

그러나 어떤 프로세스를 먼저 실행시켜야 할지 CPU는 고민할 것이고 우리는 가장 효율적인 방법으로 CPU의 자원을 이용해야 한다.

이때 필요한 것이 CPU Scheduler이다.

이러한 CPU Scheduling 방식에는 4가지가 존재한다.

이러한 방식을 알아보기 전에 먼저 Preemptive and Nonpreemptive Scheduling(선점 및 비선점 스케줄링)에 대해서 알고 가면 좋을 것 같다.

 

비선점 스케줄링이란 한 프로세스가 실행되면 실행된 프로세스가 종료(terminate) or 대기(waiting) 상태로 전환될 때까지 CPU를 점유하는 것이다.(1,4번)

 

선점 스케줄링이란 cpu가 할당받은 시간 안에 프로세스가 다 끝나지 않았거나, 인터럽트, 시스템 호출 종료 시 더 높은 우선순위 프로세스가 발생했을 경우 현재 프로세스의 CPU 점유를 강제로 회수해서 우선순위가 높은 프로세스에 할당하는 것이다. (2,3번)

 

1. Switches from running to waiting state(I/O 발생)

2. Switches from running to ready state(Interrupt 발생)

3. Switches from  waiting to ready state(I/O 종료)

4. Terminates(프로세스 종료)

<Process 진행>

 

4. Dispatcher

디스패처란 CPU 스케줄러에 따라서 CPU의 Control을 프로세스에게 할당하는 모듈이다.

• 두 프로세스 간의 문맥을 교환하는 일(Switiching Context)
• 사용자 모드로 전환하는 일(Switching to User Mode)
• 프로그램 재시작을 위해 사용자 프로그램의 적절한 위치로 이동하는 일(JUMP)

디스패처가 하나의 프로세스를 정지하고 다른 프로세스를 수행시키는데 소요되는 시간을 Dispatch Latency라고 한다.

<Dispatcher의 역할>

PCB) Process Control Block을 의미하는데 Process id, 메모리 관리 정보, 중간값(다음 실행할 명령어, 연산) 등 Process에 대한 MetaData를 저장하는 것이다. PCB는 프로세스를 구분, 관리할 수 있는 역할을 한다.

즉 Context Switching이 발생하면 수행 중인 Task의 MetaData를 PCB에 저장하고 교환된 Task를 수행한다. 이를 마치고 PCB에 저장되어 있던 이전 Task의 MetaData를 불러와서 해당 Task를 수행한다.

 

Preemptive Scheduling = 선점 스케줄링 = 자발적 문맥 교환

Non Preemptive Scheduling = 비선점 스케줄링 = 비자발적 문맥 교환

 

5. Scheduling Criteria

Criteria는 기준을 의미한다. 우선순위를 정할 때 다양한 기준이 있을 것이고 CPU입장에서는 이러한 기준에 따라서 Task(Process, Thread)를 할당해야 할 것이다. 비교 기준은 아래와 같다.

• CPU 이용률(Utilization): 어느 기간 동안 또는 특정 SNAPSHOT에서의 CPU의 이용률.
• 처리량(Throughput): 단위 시간당 완료된 프로세스의 개수.
• 총 처리 시간(Turnaround Time): 프로세스의 제출 시간과 완료 시간의 간격 = 총 처리 시간
• 대기 시간(Waiting Time): 프로세스가 Ready Queue에서 대기하면서 보낸 시간의 합.
• 응답 시간(Response Time): 하나의 Request를 제출한 후 첫 번째 Response가 나올 때까지의 시간이다.

이용률, 처리량을 높이고 대기시간, 처리시간, 응답 시간을 낮추는 알고리즘이 좋은 알고리즘이다.

 

6. Scheduling Algorithms

알고리즘을 통해서 어떤 task에 프로세서를 할당할 건지 문제를 해결해 볼 수 있다.

FCFS(First Come First Served), SJF(Shortest Job First), SRTF(Shortest Remaining Time First), Priority Scheduling, RR(Round Robin), Mulitilevel Queue, Multilevel Feedback Queue 등이 존재한다.

 

<FCFS> 

Example of FCFS

  정직하게 먼저 요청한 task부터 처리해준다. 프로세스가 종료될 때까지 다른 프로세스는 간섭할 수 없기에 비선점형이다. 효율성이 매우 떨어진다. Convoy Effect에 의해서 처리 시간이 짧은 task일지라도 앞에 있는 task의 처리시간이 길면 대기 시간이 길어진다.

은행에서 줄 기다리는 것을 생각해보면 이해가 쉽다.

 

<SJF>

Example of SJF

 

Example of Non Preemptive SJF

SJF는 CPU 버스트의 길이 즉 처리시간이 짧은 것부터 먼저 처리하는 것이다. 그리디 알고리즘 문제를 풀어본 적이 있다면 위와 비슷한 문제를 풀어본 적이 있을 것이다. 평균 대기 시간이 최솟값임을 보장해준다.

그러나, 문제점이 있는데 각 task의 cpu 버스트 길이를 알 수 있는 방법이 없다. 따라서 우리는 cpu 버스트 길이를 예측해야 한다.

SJF는 선점형 혹은 비선점형 둘 다 될 수 있다.

Non Preemtive SJF의 경우 waiting time을 task의 arrival time을 기준으로 측정한다.

즉 P3의 경우는 실제로 4에 도착했으므로 P1 프로세스가 종료되는 7 시점을 기준으로 봤을 때 3만큼 기다린 것이다.

 

위에서 CPU의 버스트 길이를 예측해야 한다고 했다.

이때 나오는 것이 Exponential Averaging이다.

 

Exponential Averaging)

이는 이전의 History 들을 이용해서 미래 값을 예측하는 것이다.

CPU의 경우에는 이전 프로세스들의 CPU버스트 값을 통해서 예측한다.

위와 같은 공식을 따른다.

이때 a의 값이 커질수록 최근의 데이터에 비중이 높아지고 a의 값이 낮아질수록 이전에 쌓여온 누적 데이터의 비중이 커진다.

 

<SRTF>

SRTF는 쉽게 생각하면 SJF에 선점 정책을 도입한 것이다.

우선 SJF의 경우 P1이 실행되면 P1 프로세스가 끝날 때까지 다른 프로세스는 실행할 수 없다.

그러나 SRTF 프로세스 실행 중에도 cpu 버스트 타임이 더 짧은 프로세스가 들어오면 Context Switiching을 통해서 해당 프로세스를 먼저 수행한다.

 

<Priorirty Scheduling>

해당 알고리즘은 우선순위가 각 프로세스들에 연관이 되어 있고 cpu 코어는 우선순위가 가장 높은 프로세스가 할당된다.

우선순위 스케줄링 알고리즘의 주요 문제는 무한 봉쇄(indefinite blocking) 또는 기아 상태(starvation)이다.

• 실행 준비는 되어 있으나 CPU를 사용하지 못하는 프로세스는 CPU를 기다리면서 봉쇄된 것으로 간주할 수 있다. (Blocking)
• 부하가 과중한 컴퓨터 시스템에서는 높은 우선순위의 프로세스들이 꾸준히 들어와서 낮은 우선순위의 프로세스들이 CPU를 얻지 못하게 될 수 도 있다. (Starvation)

Starvation을 해결하는 방법 중 하나는 Aging 기법이다. 시스템에 오랫동안 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 것이다.

 

해당 알고리즘의 문제를 해결하는 또 다른 방법은 RR(Round Robin)과 결합하는 방법이다.

우선순위가 높은 것을 먼저 실행하고 우선순위가 동일할 경우 RR을 통해서 실행한다.

 

<Round Robin>

기본적으로 FCFS와 비슷하지만 시스템이 프로세스 사이를 이동할 수 있도록 선점이 추가된다.

이를 위해 Time Quantum이라고 불리는 작은 단위의 시간을 정의해야 한다.

위의 예시를 보면 Time Quantum이 4로 정의되어 있다. 즉 4만큼만 실행하면 프로세스의 종료 여부와 상관없이 문맥 교환을 한다.

Time Quantum이 매우 크면 본질적으로 FCFS와 다른 점이 없고 Time Quantum이 매우 작을 경우 매우 많은 문맥 교환을 발생시킨다.

 

<Multilevel Queue Scheduling>

 

다단계 큐 스케줄링 방법은 우선순위 스케줄링이 라운드 로빈과 결합한 스케줄링 알고리즘이다. 이 방식의 가장 일반적인 형태에서 우선순위가 각 프로세스에 정적으로 할당되며 프로세스는 실행시간 동안 동일한 큐에 남아 있다.

아래의 그림과 같이 프로세스 유형에 따라 프로세스를 여러 개의 개별 큐로 분할하기 위해 다단계 큐 스케줄링 알고리즘을 사용할 수도 있다.

각 큐에는 자체 스케줄링 알고리즘을 구현할 수 있다.

우선순위를 가진 큐 별로 CPU를 선점할 수도 있고, 큐들 사이에 CPU의 시간을 나누어서 사용할 수도 있다.

 

<Multilevel Feedback Queue Scheduling>

위의 다단계 큐 스케줄링에서는 하나의 큐에 하나의 프로세스들이 고정되는데 이와 다르게 해당 스케줄링의 경우 프로세스가 큐 사이를 이동하는 것이 허락된다. 위에서 아래로, 아래에서 위로 이동도 가능하다.

가장 널리 사용되는 cpu 알고리즘이지만 가장 복잡한 방법이다.

근본적으로 OS는 실행 중인 프로세스가 I/O Bound 인지 CPU Bound 인지 알지 못하지만, adaptively 하게 이동한다.

 

1.  시작은 항상 Queue0로 들어가는데 A의 Burst는 Time Quantum 8보다 짧다. 따라서 I/O 의 경우 wait 상태로 들어간다. 따라서 A는 Queue0에서 탈출한다.

8 - 8 = 0

2. B의 경우 우선 Queue0로 들어온다. Burst가 8보다 길다 따라서 interrupt로 인해서 ready 상태로 가고 Queue1으로 이동한다. B의 Time Quantum은 16 이므로 B의 프로세스를 모두 처리하고 B는 Queue1에서 나간다.

24 - 8 - 16 = 0 

3. C의 경우 Queue0로 들어오는데 종료 Burst가 40이므로 RR에 맞게 실행된 후 Queue2로 간다.

40 - 8 - 16 = 16 따라서 Queue2에서 16만큼 실행해야 한다.

7. Thread Scheduling

Contention Scope(경쟁 범위)

사용자 스레드와 커널 스레드의 연관 관계를 다대일과 다대다 모델로 구현하는 시스템에서는 Thread Library는 사용자 수준 스레드를 가용한 LWP(Light Weight Process)상에서 스케줄 한다. 이러한 기법은 동일한 프로세스에 속한 스레드들 사이에서 CPU를 경쟁하기 때문에 프로세스 경쟁 범위(process contention scope, PCS)로 알려져 있다.

CPU상에서 어느 커널 스레드를 스케줄 할 것인지를 결정하기 위해서 커널은 시스템 경쟁 범위(system contention scope, SCS)를 사용한다. SCS 스케줄링에서의 CPU에 대한 경쟁은 시스템상의 모든 스레드 사이에서 일어난다.

전형적으로 PCS는 우선순위에 따라 행해진다.