[운영체제/OS] CPU Scheduling_ Multilevel Queue, Multilevel Feedback Queue 스케줄링

[운영체제 OS] - [운영체제/OS] CPU Scheduling_비선점, 선점, FCFS, SJF, Priority, RR 스케줄링

[운영체제/OS] CPU Scheduling_비선점, 선점, FCFS, SJF, Priority, RR 스케줄링

앞서서 CPU 스케줄링 네 가지 알고리즘들을 알아보았어요.

라운드로빈(RR)과 선입선처리(FCFS) 스케줄링을 알아야 이번 게시글을 이해하기 편하므로 먼저 이전 게시글을 보고 오시는 걸 추천드릴게요!

 

Multilevel Queue Scheduling 

프로세스들을 중요도에 따라 여러 종류의 그룹으로 나누어 여러 개의 큐에 다양한 알고리즘을 적용한 스케줄링입니다.

 

Ready Queue는 여러 큐로 나뉘어요. (프로세스가 많을 수록 선택시간이 오래 걸립니다)

우선순위가 높은 애들은 foreground(interactive 대화형)

우선순위가 낮은 애들은 background(batch 배치식)에 대기해요.

 

프로세스들은 모두 일시적으로 큐에 존재하고

foreground에는 RR 스케줄링, 

background에는 FCFS 스케줄링을 활용하는데 섞어 써도 됩니다.

 

이 알고리즘은 고정적 우선순위 스케줄링으로 (foreground에서 background까지 모두 돌음) starvation의 가능성이 있어요. 우선순위가 낮은 애들은 아예 CPU 할당을 못 가지는 문제가 발생할 수 있어요.

모든 큐는 일정 time slice의 CPU time을 가져서 예를 들어 foreground의 RR에는 80%, background의 FCFS에는 20%가 가요.

 

 

Multilevel Feedback Queue

가장 많이 활용되고 unfixed 하게 동적 방식 으로 runtime을 반영합니다.

큐를 여러 개 둬서 들어올때 일단 우선순위 높은 애들에게 먼저 RR방식으로 CPU 할당을 해주고,

time quantum 만에 빨리 끝나면 I/O 사용자랑 interaction 많은 애들은 앞에서 우선순위 높은 상태로 계속 유지하고 

(왜냐하면 time quantum 만에 끝나면 우선순위가 안 떨어져 있음)

time quantum 다 썼는데도 못 끝난 애들은 다른 애들것까지 독식할 가능성이 있으므로 낮은 큐로 차근차근 내려줍니다. 이는 FCFS방식인데 starvation 가능성이 있어 이 또한 OS가 해결해주어야 합니다. 

 

Multilevel feedback queue 스케줄러는 다음 요소들을 고려해야합니다

-큐의 개수

-각 큐의 스케줄링 알고리즘

-프로세스 업그레이드하는 방식

-프로세스 강등하는 방식 

-어떤 큐를 먼저 CPU에게 프로세스 할당할지

 

다음 그림은 3개의 큐- Q0, Q1, Q2 가 있을 때

Q0은 8 ms time quantum의 RR

Q1은 16ms time quantum의 RR

Q2은 FCFS

입니다.

 

만약 Q0이 8ms안에 작업을 끝내지 못했다면, 선점하게(preempted) 작업은 Q1 큐로 이동합니다.

Q1이 RR작업을 할 때, 16ms을 더 받습니다.

만약 이 안에 Q1이 작업을 못 끝내면, 선점하게(preempted) Q2로 이동합니다.

 

 

 

Multiprocessor Scheduling

CPU 스케줄링을 여러 CPU(코어)를 활용합니다. 병렬 시스템이라고도 부릅니다.

 

Asymmetric(비대칭) multiprocessing(ASMP): 잘 사용하지 않는 형태로, 하나의 프로세서만 시스템 자료구조에 접근이 가능해서 그 프로세스가 작업량이 너무 많아 병목점으로 속도가 저하되는 문제가 생깁니다. 장점은 여러 프로세스의 상황을 판단하고 고려하여 로드밸런싱(분산 작업)이 정확해집니다.

Symmetric(대칭) multiprocessing (SMP): 각 프로세서가 직접 스케줄링하여 모든 프로세스들은 ready queue에 있거나, 각 private 큐에서 ready queue에 있습니다. 

 

어떤 프로세스를 할당하느냔 문제에 추가적으로 어떤 프로세서에 프로세스를 할당할지라는 문제를 또 고민해야합니다.

 

SMP를 일반적으로 구현하는 방법 두 가지인데

(a) 방법은 하나의 큐를 사용한 것으로 

첫번째 문제는 병목점이 발생할 수 있고 두번째 문제는 모두가 접근할 수 있으므로 우연의 일치로 문제가 생기면 일관성의 문제가 생깁니다.

 

(b)방법은 여러 큐를 사용한 것으로, 일반적으로 사용되는 방법인데요

첫번째 문제는 하나의 큐만 바쁠 수 있어서 작업 분산 유지가 어렵습니다. (각자 자기꺼만 보이고 자기일만 하는 것)

이를 migration 기법으로 해결하여 실행코어를 바꾸는데, 이러면 로드밸런싱 성능이 좋아집니다.

 

migration은 load balancing(로드밸런싱), 즉 작업 분산을 위한 것으로

Push migration - 바쁜(overloaded) 프로세서가 안 바쁜(idle)  프로세서한테 던지는 것

Pull migration - 안 바쁜(idle) 프로세서가 큐를 검사하는 것 (바쁜 프로세서로부터 작업 가져오는 것)

두 가지 종류가 있습니다. 

하지만, migration 또한 너무 많으면 성능이 저하됩니다. (비용이 비쌈)

 

 

 

Processor Affinity 프로세서 친화성

 

프로세스가 수행될 때는 CPU의 캐쉬에 올라가므로 migration은 비용이 상당히 커요.

 

프로세서에 친숙한 프로세스를 할당하는 방법을 프로세서 친화성이라고 하는데요

overhead를 줄이기 위해 사용합니다

 

약한 친화성(soft affinity) : 가급적 동일 프로세서에서 수행하는 것. migration 가급적 안함 

강한 친화성(hard affinity): 시스템 호출을 사용하여, 어떤 프로세스는 migration을 하지 않는다 명시도 함(금지가능) 

 

OS는 두 가지 모두 지원하는데, 뭐든 개발하기 나름이고 완벽한 정답은 없습니다.

 

 

 

 

NUMA(non uniform memory access system)

말그래도 uniform하지 않은 메모리 접근 시스템으로 (반대는 UMA)

극단적인 케이스로 메모리에서 가까운 애들은 빠르게 접근이 가능하지만 먼 애들은 접근이 어려워요.

프로세스끼리 거리에 따라 속도 차이가 큽니다.

 

 

 

Multicore Processors

멀티코어 프로세서는 여러 개의 작업을 효율적으로 처리하기 위해 여러 코어를 활용하는 회로입니다.

위의 multiprocessor scheduling은 처리방식이고 multicore processor는 회로입니다. 

하지만 multicore processor가 항상 multiprocessor scheduling 방식으로 사용되는 것은 아니에요.

multicore processor가 멀티 프로세싱 또는 독립적 프로세싱 방식 모두 사용 할 수 있어요.

 

 

Real-Time CPU Scheduling 실시간 CPU 스케줄링

실행될 모든 프로세스들이 정해진 시간clock내에 완료되어야 하는 시스템입니다.

priority-based, rate-monotonic, earliest deadline first 스케줄링으로 구분됩니다.

 

Soft real-time systems - 가급적 deadline내 

Hard real-time systems - 반드시 deadline 내 작업 수행 

두 가지로 나눌 수 있습니다. 

 

Latency에는 

Interrupt latency와 Dispatch latency 두 종류가 있어요.

 

 

 

Priority-based Scheduling 

선점형의 우선순위 스케줄링입니다. 

Periodic한 아이들이 CPU를 일정한 주기를 요구해요.

 

즉,

프로세싱시간 < deadline < 주기

 

 

 

Rate Monotonic Scheduling (RM)

정적 스케줄링 방식으로 선점 방식입니다.

주기가 짧을수록 우선순위가 올라가고,

주기가 길수록 우선순위가 낮아져서 deadline까지 시간여유가 있어요.

 

두 프로세스 P1, P2가 있을 때,

P1의 주기는 50, P2의 주기는 100이고

P1의 수행시간 t1은 20, P2의 수행시간 t2은 35일때

P1의 CPU 이용률은 20/50, P2는 35/100으로 총 75%입니다.

즉, 수행시간/주기가 CPU이용률이죠.

 

Deadline (CPU 이용률 상한)은 N(2^1/N -1) 입니다. (프로세스(코어)가 N개)

1개일땐 100%, 2개일땐 83%...이므로 

 

위의 P1과 P2는 75%로 83%보다 낮으므로 deadline내에 만족합니다

 

deadline 만족되지 못한 경우는 

P1의 주기가 50, 수행시간 t1은 25

P2의 주기가 80, 수행시간 t2는 35일 때,

CPU 이용률은 P1은 25/50, P2은 35/80 으로 각 50%와 44%로 합하면 94%이므로 deadline인 83%를 만족하지 못합니다.

 

 

Earliest Deadline First Scheduling (EDF)

RM 알고리즘과 다르게 동적스케줄링 방식으로

프로세스들이 주기적일 필요 없고 CPU할당 시간도 상수값으로 정해질 필요가 없습니다.

 

프로세스 deadline이 가까울수록 우선순위를 높게 부여하는 선점 방식입니다.

한 프로세스의 실행이 완료될 때 deadline이 가장 임박한 것을 찾아 스케줄링을 합니다.

동적 방식으로 효율적이지만 매번 스케줄링을 위한 계산을 해야하는 비용이 소요되요.

 

그리고 context switching 등의 overhead로 인해 정확한 deadline을 예측하기도 힘듭니다.