Operating Systems - 5. CPU Scheduling - (2)

 

Round Robin (RR) Scheduling

라운드 로빈 스케쥴링은 시분할 시스템을 위해서 설계된 스케쥴링으로 각 프로세스에게 작은 양의 CPU 시간(time quantum)을 할당해준다.

이를 위해선 타이머 인터럽트를 사용하고, 실행 프로세스는 할당된 CPU 시간 경과 후 ready queue 의 맨 끝으로 이동한다. 

 

 

만약 n개의 프로세스가 ready queue 에 존재하고, time quantum 이 q라면, 각 프로세스는 최대 (n-1)q 시간을 기다릴 것이다. 

q가 길다면 성능은 FIFO (FCFS) 와 같게 되고, q가 작다면 q는 context switch time 에 비해서는 커야 한다.

그렇지 않다면 switching 오버헤드가 너무 커지기 때문이다.

보통 전체 CPU burst time 의 80% 정도가 quantum time 보다 짧도록 정한다. 

 

 

 

RR의 성능은 SJF 보다는 평균 총 처리시간(turnaround time) 이 더 크지만, 응답시간은 더 짧다.

또한 q가 반드시 context switch 시간보다는 커야한다.

 

 

 

총 처리 시간은 time quantum 크기에 따라 달라지는데, 크기가 증가한다고 평균 총처리시간이 반드시 개선되는 것은 아니다. 

 

 

 

Multilevel Queue Scheduling

다단계 큐 스케쥴링은 ready queue 가 여러 개의 큐로 분할되며, 각 큐는 자신의 스케줄링 알고리즘을 사용한다. 

foreground - interactive (우선순위 높은 것 -RR 로 구현

background - batch (우선순위 낮은 것 - FCFS로 구현

 

 

스케쥴링은 큐들 간에도 있어야 하는데, 예로 고정 우선순위 스케쥴링은 foreground 작업을 모두 처리한 후에 background 작업을 수행한다던지 등의 방법으로 기아 상태(starvation) 의 가능성이 높다.

다음으로, Time slice 스케쥴링은 각 큐마다 CPU 사용량/비율을 정해서 할당하는 것으로 예

로 foreground 에 80% background 에 20% 할당하는 식으로 사용할 수 있다. 

 

 

 

Multilevel Feedback Queue

다단계 큐 스케쥴링은 프로세스 생성시 하나의 큐에 영구할당 되었다.

이를 개선한 다단계 피드백 큐 스케쥴링은 프로세스가 여러 큐들 사이를 이동하는 것을 허용한 것으로 aging 을 구현한다. 

 

-> I/O 사용이 빈번한 process 에 적합하다. 왜냐하면 I/O 프로세스는 time quantum 내에 수행할 가능성이 높아서, 높은 우선순위가 유지되기 때문이다.

 

따라서 스케쥴러는 다음과 같은 매개변수를 가진다.

- 큐 개수

- 각 큐에 대한 스케쥴링 알고리즘

- 큐 승급/강등 시점

- 진입할 큐 결정 방법

 

 

 

다단계 피드백 큐의 과정은 위 그림과 같다. 프로세스가 생성되면 가장 높은 우선순위로 배치되는데, 이 프로세스가 time quantum 안에 다 수행한다면 그 우선순위를 유지할 수 있다.

그러나 다 끝내지 못하면 우선순위가 강등된다. 또한 같은 우선순위의 작업들은 round-robin으로 수행된다.

낮은 우선순위에 있는 프로세스가 일정 시간 이상 방치된다면, aging 을 주어 우선 순위를 올려주는 boosting 현상으로 해결 한다. 

 

 

Multiprocessor Scheduling

여러 개의 CPU 가 있는 경우 CPU 스케줄링이 더 복잡해진다.

여기선 모든 프로세서가 동일한 시스템을 가정한다.

다중 프로세서 스케줄링을 접근 하는 방법에는 비대칭(Asymmetric) 다중 처리와 대칭(Symmetric) 다중처리가 존재한다. 

 

- 비대칭 다중 처리는 한 프로세서가 스케줄링, 입출력처리, 시스템 활동(운영체제 커널 수행) 등을 맡고, 나머지 프로세서들은 user code 만 수행하는 것이다. 자료 공유의 필요성이 없으므로 간단한 설계가 요구된다. 그러나, 하나의 스케쥴러에 병목현상이 생길 수 있으며, 제대로 작업분배가 이뤄지지 않을 수 있다. 

- 대칭 다중처리(SMP)는 각 프로세서가 독자적으로 스케줄링을 하는 것이다. 여기엔 공동의 ready queue 가 존재하는데 이는 모든 프로세서가 함께 사용하는 큐이다. 또한 프로세서마다 분리된 자신의 큐도 당연히 가지고 있다. 

 

대칭 다중처리에서 공통된 ready queue 를 사용하면 각 CPU 가 자신이 원하는 방법대로 ready queue 에서 작업을 가져올 수 있다.

그러나 여러 core 가 큐에 동시에 접근한다면, 병목 현상이 생기고 동기화를 하지 않을시 문제가 발생할 것이다. 

 

또한, CPU 마다 각자의 private 한 큐를 가진다고 하였는데, 각 CPU 는 자신의 큐만 확인하기 때문에 작업분배가 잘 되지 않을 수 있다. 이는 프로세스가 할당된 CPU 를 바꾸는 migration으로 해결할 수 있다. 

여기서 자신의 큐에서 프로세스를 다른 CPU 로 옮기는 것을 Push migration, 바쁜 CPU 로부터 waiting task를 받아오는 것을 Pull migration 이라 한다. 

 

 

프로세서 친화도

프로세스가 현재 실행 중인 프로세서에서 다른 프로세서로의 migration 을 피하고 다음 스케줄링에서도 현재 프로세서에서 계속 실행을 시도하는 상황이다.

프로세스가 수행될 때는 CPU 의 cache에 올라가므로, 프로세서를 이주하는 것은 상당히 비용이 많이 드는 작업이다. 

 

- 약한 친화성 : 가급적 동일 프로세서에서 수행하려 하나, 이주가 가능하다.

- 강한 친화성 : 시스템 호출을 사용하여, 어떤 프로세스는 프로세서를 이주하지 않는다고 명시할 수 있다. 

 

대부분의 운영체제가 두 가지 모두를 지원하고, linux 의 경우 sched_setaffinity() 시스템 콜을 제공한다.

 

NUMA 구조인 경우 프로세서 친화도를 좀 더 심도 있게 고려해야 한다.

UMA 구조는 모든 core가 메모리에 접근하는 시간이 모두 동일하며, 따라서 메모리 접근시 병목현상이 생길 수 있다.

반대로 NUMA 구조는 직접 CORE 에 연결된 메모리가 존재하여, 직접 연결된 메모리에 빠른 접근이 가능하고 다른 CPU 에 연결된 메모리 접근시 느린 접근이 사용된다. 

 

 

 

Multicore Processors

멀티 코어 프로세서는 같은 칩에 다수의 프로세서(multi-threaded) 코어를 보유한 프로세서이다.

프로세서가 메모리에 접근하는 동안, CPU 연산 장치를 다른 프로세서가 이용하기 때문에 CPU는 놀지 않고 계속해서 돌아가는 것이다.

 

 

멀티스레드 다중코어 시스템

하나의 코어에 여러 개의 하드웨어 스레드를 할당하는 것으로, 하나의 코어에 2개의 하드웨어 스레드를 할당하는 시스템은 총 8개의 논리 스레드가 운영체제에 존재하는 것이다.

 

 

 

 

Real-time CPU Scheduling

Soft real-time systems 은 가급적 deadline 을 맞춰야 한다. Hard real-time systems 는 반드시 deadline을 맞춰야 한다. 

 

- Priority-based Scheduling

Real-time 시스템은 선점형이고 우선순위 기반의 스케쥴링이 필요하다. 무조건 프로세스를 받는게 아니라 주기 안에 돌아갈 수 있는 프로세스들만 받는 것이다.

 

- Rate Monotonic Scheduling

정적 우선순위의 선점형 알고리즘으로, 우선순위는 주기에 반비례하여 할당되며, 짧은 주기의 작업이 높은 우선순위를 받게 된다.

즉, 자주 나타나는지 드물게 나타나는지 CPU 이용률에 따라 우선순위를 준다.

문제점은 수행시간의 예측이 정확하지 않아서 정확한 스케줄링이 어렵다는 것이다.

 

 

Rate Monotonic은 CPU 이용률에 한계가 있기 때문에 자원을 최대로 사용하는 것은 불가능이다.

따라서 CPU 이용률의 상한을 넘기지 않아야 deadline 을 지킬 수 있다.

밑의 경우에는 P2가 deadline을 만족하지 못한다. 

 

 

 

Earliest Deadline First scheduling

deadline 에 따라 동적인 스케쥴링을 하는 것으로, deadline 에 임박할 수록 우선순위가 높아진다.

이론적으로 EDF 는 최적으로 100% CPU 를 사용할 수 있지만,

동적으로 정확한 마감시간을 알기 어렵고, context switching 등의 overhead 로 100 % CPU 사용률을 불가능 하다. 

 

 

 

Proportional Share Scheduling

전체 프로세스들 간에 n만큼 나눠주는 스케줄링으로, 각 프로세스들에게 할당된 몫을 보장해준다. 만약 A가 50, B가 15, C가 20을 할당 받았을 때, D가 30을 요구하면 승인하지 않는다.