[OS] 5-2. CPU Scheduling II

Chapter 5-2. CPU Scheduling II

앞서 살펴본 CPU Scheduling에 대한 구체적인 알고리즘을 살펴보겠다.

<Algorithm>

FCFS(First Come First Served)

먼저 온 사람에게 먼저 제공한다는 뜻으로 먼저 할당 요청을 한 프로세스에게 CPU를 할당한다.

즉, 먼저 요청한 순서대로 처리하는 단순한 알고리즘이다.

비선점형 스케줄링이며 효율적이지 않다.

여기서 Nonpreemptive(비선점형)하다는 것은 일단 CPU를 할당받으면 자신의 작업을 모두 마치기 전까지,

즉 CPU burst가 완료되기 전까지 CPU를 반환하지 않는다는 의미이다.

문제점

convoy effect 발생

convoy effetct 란 소요시간이 긴 프로세스가 먼저 도달하여 시간을 잡아먹고 있는 부정적인 현상을 의미한다.

SJF(Shortest - Job - First)

짧은 작업을 먼저 처리하는 방식으로 CPU burst time이 짧은 프로세스에게 CPU를 선할당하는 방식이다.

물론, 먼저 요청을 하면 당연히 다른 요청이 없으므로 그 요청에 응답를 한다.

이 방식은 기본적으로 Nonpreemptive 특성을 갖는다.

그리고 이로인해 발생하는 문제점을 해소하기 위해 Preemptive 특성을 추가하였다.

현재 수행 중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 갖는 프로세스가 도착하면,

이미 현재 수행 중인 프로세스에게서 CPU를 빼앗아 새로 도착한 프로세스에게 CPU를 할당한다.

이 특성이 추가된 SJF를 특별히 SRTF(Shortest Remaining Time First)라고 한다.

이 SRTF는 Optimal하다.

주어진 프로세스들에 대해 minimum average waiting time을 보장하기 때문이다.

하지만 새로운 프로세스가 도착할 때마다 스케줄링을 새로해줘야 한다.

문제점

Starvation 발생

물론, 효율성을 추구하는 것이 여러 작업을 처리하는데 있어서 가장 바람직하지만,

특정 프로세스가 지나치게 차별받는 문제는 발생하면 안된다.

이 스케줄링 방법은 극닥적으로 CPU burst time이 짧은 프로세스에게 집중되어 있다.

CPU burst time이 긴 프로세스는 영원히 CPU를 할당받을 수 없는 상황, starvation이 발생하게 된다.

스케줄링을 계속하므로 프로세스의 CPU burst time을 측정할 수 없다.

물론 그 프로세스의 과거 이력을 통해서 저번에는 어느 정도의 시간동안 사용했는지 알아볼 수는 있으나,

운영체제 입장에서 이는 자연스럽지 못하다.

Priority Scheduling

프로세스마다 우선순위를 정한 뒤, 우선순위가 높은 프로세스에게 CPU를 선 할당하는 방식이다.

우선순위란 정수로 표현하게 되고 작은 숫자가 우선순위가 높다고 하는 그런 기준을 말한다.

더 높은 우선순위의 프로세스가 도착하면 CPU를 뺏기므로 Preemptive한 성격을 갖고 있다.

SJF 또한 기준을 CPU burst time으로 설정한 우선순위 스케줄링으로 볼 수 있다.

이 방식 또한 starvation의 문제점을 갖고 있다.

그래서 이를 해결하기 위해 aging기법을 도입한다.

aging이란 as time progress increase the priority of the process로

아무리 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위를 높여주는 나이를 먹는 그런 느낌의 방식이다.

Round Robin

가장 현대적인  CPU 스케줄링 방식이다.

각 프로세스는 동일한 크기의 할당시간(time quantum)을 갖게 된다.

할당 시간이 지나면 프로세스는 CPU를 반환하고 ready queue의 맨 뒤로 돌아가 다시 대기하게 된다.

이 방식을 사용했을 때의 취할 수 있는 이점은 Response time이 짧아진다는 것이다.

사용자의 입장에서는 반응 시간이 짧으면 컴퓨터가 매우 빠른 것처럼 느껴진다.

반응 시간만 줄이더라도 사용자로에게 좋은 환경을 제공할 수 있는 것이다.

또 어떠한 프로세스도 (n-1)*q time unit 이상 기다리지 않는다.

어떻게든 일을 마칠 때까지 자기 차례가 돌아오기 때문이다.

매우 공정한 스케줄링이라고 할 수 있다.

이상적인 스케줄링을 위해서는 quantum을 설정하는데 있어서 유의해야 한다.

time quantum이 너무 커지게 되면, FCFS와 같은 방식으로 취급되어 같은 문제가 발생하게 된다.

또 time quantum이 너무 작아지게 되면, 정말 공정한 스케줄링이 되겠지만 계속되는 context switch로 overhead가 발생하게 된다.

라운드 로빈 알고리즘이 가능한 이유는 프로세스마다 context라는 것이 있고 상태를 저장할 수 있기 때문이다.

하지만 이렇게 진행 상황을 모조리 저장하고 다른 프로세스로 CPU를 넘긴다는 것은 상당히 overhead한 작업이다.

라운드 로빈은 CPU burst time이 랜덤한 프로세스들이 혼재했을 때 그 빛을 발한다.

CPU burst time이 모두 동일할 경우에는 바람직하지 못한 스케줄링 기법이 된다.

프로세스의 시작과 함께 그 종료도 함께 이루어지기 때문이다.

(하지만 이런 경우는 일반적이지 않다.)

지금까지의 알고리즘의 Ready queue가 한 줄이었다면 이제 여러 줄을 서서 CPU를 할당 받는 기법들을 살펴보자.

Multilevel Queue

Ready Queue를 여러 개로 분할한다.

이렇게 되면 프로세스가 어느 큐로 들어가서 대기할 것인지를 결정할 스케줄링이 하나 더 필요하게 된다.

그리고 각 큐는 큐 내에서 독립적인 스케줄링 알고리즘을 갖게 된다.

foreground - interactive = Round Robin

background - batch no human interaction = FCFS

즉 interactive한 프로세스들은 우선순위가 높고 그렇지 않은 프로세스들은 우선순위를 낮게 지정한다.

Fixed Priority Scheduling방법이다.

1단계에서 대기 상태인 프로세스가 있다면 1단계에서 대기하고 있는 프로세스에게 CPU를 할당해주고,

1단계에 아무 프로세스도 없어야 2단계에서 대기하고 있는 프로세스에게 CPU가 할당된다.

이렇게 되면 statvation문제가 발생하게 된다.

이 스케줄링에서는 해결책으로 Time Slice 방법을 사용한다.

각 큐에  CPU time을 적절한 비율로 할당하는 것이다.

예를 들면 80%는 foreground 큐에, 20%는 background 큐에 할당하는 것처럼 말이다.

서야 하는 줄이 생성과 함께 운명적으로 결정되었다면 이젠 서야하는 줄이 상황에 따라 바뀌는 알고리즘이다.

Multilevel Feedback Queue

프로세스가 다른 큐로 이동이 가능해진 방법이다.

이 방법에서 알고리즘을 형성하기 위해 사용되는 인자들이 여러 개 존재한다.

Queue의 수

각 큐의 Scheduling Algorithm

Process를 상위 큐로 보내는 기준

Process를 하위 큐로 내리는 기준

프로세스가 들어갈 큐를 결정하는 기준

이러한 것들을 결정해줘야 하는 것이다.

처음 들어오는 프로세스는 우선순위가 가장 높은 큐에 위치시켜준다.

그리고 각 큐마다 할당된 quantum이 정해져 있다. 하위 큐로 내려갈수록 그 값이 커진다.

quantum = 8인 큐에서 CPU를 할당, 이 단계에서 수행을 완료하면 나가고, 못하면 하위 큐로 이동한다.

quantum = 16인 큐에서 CPU를 할당, 이 단계에서 수행을 완료하면 나가고, 못하면 하위 큐로 이동한다.

...

그러다가 FCFS로 처리를 하게 된다.

CPU burst time이 짧은 프로세스를 먼저 완료시키는데 집중한 알고리즘이다.

지금까지 단일 코어였다면 이젠 여러 개의 CPU 

또는 여러 개의 Thread 멀티 코어 경우 

또는 시간적 제약조건이 포함된 알고리즘이다.

Multi Processor Scheduling

CPU가 여러 개가 되면 스케줄링은 더욱 복잡해진다.

Homogeneous Processor Scheduling

Queue에 한 줄로 세워서 프로세서가 알아서 꺼내가게 할 수 있다.

반드시 특정 프로세서에서 수행되어야 하는 프로세스가 존재하는 경우 문제가 복잡해진다.

Load Sharing

일부 프로세서에 Job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘이 필요하다.

CPU가 놀고 있으면 효율이 떨어진다.

별개의 큐를 두는 방법이 있고 공동 큐를 사용하는 방법이 있다.

Symmetric Multi Processor

각 프로세서가 각자 알아서 스케줄링을 결정하는 것이다.

모든 프로세서가 동등한 위치에 존재한다.

Asymmetric Multi Processor

하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 따르는 방식이다.

Real-Time sharing

hard real time system

정해진 시간안에 반드시 수행이 완료되도록 스케줄링 하는 방식이다.

soft real time computing

일반 프로세스에 비해 높은 Priority를 갖게 하여 알고리즘을 수행한다.

Thread Scheduling

Local Scheduling

Use level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄 할 지 결정한다.

프로세스 내부에서 어떤 쓰레드에 CPU를 할당할 지 결정한다.

OS가 하는 영역이 아니고 프로세스의 영역이다.

Global Scheduling

Kernel level thread 의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 스레드를 스케줄할 지 결정한다.

++

Algorithm Evaluation

Queueing Mdels

확률 분포로 주어지는 arrival rate(프로세스 도착률)와 service rate(CPU의 처리율)등을 통해 각종 performance index값을 계산한다.

Implementation & Measurement

실제 시스템에 알고리즘을 구현하여 실제 작업에 대해서 성능을 측정하고 비교한다.

Simulation

조금 더 쉬운 방법으로 실제로 돌리는 것이 아니라 보다 간단한 모의 실험을 하여 비교하는 방법이다.

알고리즘을 모의 프로그램으로 작성 후 trace를 입력하여 비교한다.

(trace : Simulation 프로그램에 들어갈 input data를 의미한다.)

Chapter 5-2. 끝

이 포스팅은 이화여대 반효경 교수님 강의를 듣고 요약한 내용을 담고 있습니다.