-
💻 [OS 오퍼레이팅시스템] #9 | Process Scheduling 3 | 다중프로세서 스케쥴링, SQMS, MQMSCS/OS 2022. 6. 12. 00:34
💻 다중 프로세서 스케쥴링
- 단일 프로세서 스케쥴링
언제(when) 어떤(which) 작업이 실행될지 결정한다.
- 다중 프로세서 스케쥴링
언제(when)뿐만 아니라 어디(where)에서 작업이 실행될지 결정 -> 어떤 CPU에게 작업을 할당할지 결정한다.- Issue
ready queue를 어떻게 유지할 것인지affinity를 어떻게 정의하고 활용할 것인지
applications를 어떻게 다중 프로세서에게 할당할 것인지
이질적 조합의 프로세서를 어떻게 관리할 것인지
프로세서들 간의 workload를 어떻게 균형을 맞출 것인지
- HW Issue : Cache Affinity 캐시 친화적 - SW Issue : Concurrency 병행성 캐시 효과로 인해(Memory에서 필요한 정보를 Cache로 가져오는 과정이 필요하지 않기 때문에) 어떤 작업이 다시 실행될 때, 이전에 실행되었던 CPU와 같은 CPU에서 실행되었을 때 더 좋은 성능을 보인다. CPU간에 공유 자원을 접근할 때, 정확성을 보장하기 위해 상호 배제(mutual exclusion)를 사용해야 한다.
임계영역을 lock과 unlock으로 보호한다.멀티프로세서 스케쥴러가 캐시 친화력을 고려하여 프로세스는 가능한 같은 CPU에서 실행되도록 해야한다. 다른 CPU 접근 -> 블락 -> 대기 : lock과 unlock 사용 
💻 SQMS
- Single Queue Multiprocessor Scheduling
단일 큐 이용.심플하게 각 CPU가 globally shared queue(하나의 큐)로부터 다음에 실행할 작업을 고른다.
단일 프로세서 스케쥴링 방법의 기본 뼈대를 재사용
장점 단점 단순하다. 캐시 효과 X
공유자원 상호배제를 적용해야 함 -> 확장성 떨어짐
💻 MQMS
- Multi-Queue Multiprocessor Scheduling
기본 스케쥴링 프레임워크는 다중 스케줄링 큐를 포함한다. 큐가 분리되어 있다.
어떤 작업이 시스템에 들어가면, 이 작업은 반드시 하나의 스케줄링 큐에만 들어간다. (CPU 실행 뒤 다시 그 큐에 들어간다.)
분리된 각각의 큐는 별도의 스케쥴링 정책 사용 가능하다. (CPU 별도 접근)
장점 단점 1. 동기화(synchronization) 문제를 해결 1. 부하 불균등 문제(load imbalance) 2. 확장성(scalability)과 캐시 효과(cache affinity)를 제공 
- MQMS migration
pull migration : busy한 곳에서 가져온다.
push migration : idle한 곳으로 보낸다.
많이 하면 high overhead, 덜 하면 load imbalances 겪을 수 있다.
💻 O(1) scheduler
- O(1) shceduler
우선순위 기반 스케쥴러. 우선순위 높은 거에 스케쥴링한다.
각 실행 큐는 우선순위를 위한 linked list를 가지고 있다. (숫자 작을 수록 우선순위 높음)
* why O(1)? : 고정된 상수의 배열의 크기만 순회해도 되기 때문에. 프로세스의 수에 상관하지 않고 배열 크기만 보면 된다. -> 상수타임
각 코어(CPU)마다 큐가 2개 set로 있다.
우선순위 큐가 하나 더 있다. 하나는 active 큐, 또 다른 하나는 expired 큐
task가 있는 곳만 1로 표시되는 방식인 Bitmap.
Unsigned long(32비트) 5개가 필요하다. (140비트니까)
- O(1) shceduler 알고리즘
스케쥴러는 각 실행 가능한 작업들을 active run 큐에 넣는다.
task에 time slice 다 소진하면 run queue에서 제거하고, expired run 큐에 넣는다. (starvation 방지)
active run 큐가 다 써지고 empty되면 expired run 큐와 포인터를 바꾼다. -> empty run queue가 expired run queue가 된다.
* why O(1)? : 가장 높은 우선순위의 프로세스를 선택하는 것과 task의 추가와 삭제가 프로세스의 수와 상관없이 상수타임에 수행되기 때문
- 배경과 이후
듀얼코어(멀티프로세서) 등장, 프로세스의 수가 증가하면서 확장성에 대한 요구사항을 해결하기 위해 위의 O(1)이 사용되었다.
2000년대 중반에 패러다임(안드로이드 폰 도입, SNS, 멀티미디어에 대한 요구사항->서비스 질에 관심)
-> CPU 사용시간 보장(bandwidth), 고정된 우선순위는 확장성과 자유도에 제약을 준다는 배경에서 proportional share scheduling이 나오게 되었다.
💻 Proportional Share Scheduling
- Proportional Share Scheduling
기본 원리 : 각 프로세스에 가중치를 할당한다. 이 가중치에 따라 프로세스에 CPU가 할당된다. (가중치에 비례해서 정확히 CPU 할당)
* Fair queueing : 네트워크 분야의 packet 스케쥴링에 사용됨 e.g. WFQ(Weighted fair queueing)
* Proportional share : OS 분야의 프로세스 스케쥴링에 사용됨 e.g. CFS, Lottery and Stride Scheduling
- 최적화 기준(Optimization Criteria)
Proportional Fairness Accuracy : 얼마나 그 가중치에 비례해서 fairness를 정확하게 할 수 있을지
- Service Time Error :
- W(t1,t2) : 실제로 할당된 시간 (during t1~t2)
- S(t1,t2) : 이론적으로 할당 받아야 하는 시간 (during t1~t2)
- E(t1,t2) : 서비스 타임 에러 (during t1~t2)
Service Time Error - Scheduling Overhead : 스케쥴링 알고리즘의 수행시간
- WFQ(Weighted fair queueing) 예시
virtual time이 가장 작은 task를 선택한다.
task : A, B, C, D로 4개
weight : A:B:C:D = 4:3:2:1 -> 실제 서비스 받은 시간의 비율은 역수
* virtual time : 어떤 프로세스 t 시간까지의 누적 수행시간을 정규화한 것
* timeslice로 분배하는 WRR과의 차이점 : WRR은 마지막에는 균등해보이지만, 특정시간에서 균등해보이지 않는다.
WFQ 예시 - CFS(Completely Fair Scheduler)
Linux의 2.6.23, 다중 큐이며 WFQ랑 비슷한 디자인이다.
virtual runtime이 가장 작은 task를 선택한다. -> 레드블랙트리로 구현되어 균형을 맞춰줘서 최악의 경우에도 O(log n)수행시간
모든 task에게 최소값(leftmost task)가 될 기회가 주어진다. -> starvation X
* 각 코어마다 아래 사진과 같은 run queue가 있다.
💻 Linux Multiprocessor Schedulers
- 3개의 스케쥴러
O(1) Scheduler
CFS(Completely Fair Scheduler)
BFS(BF Scheduler)
스케쥴러 O(1) CFS BFS 큐 다중 큐(확장성 문제 해결) 다중 큐(확장성 문제 해결) 싱글 큐 접근 우선순위 기반 가중치 비례 가중치 비례 * O(1) : active 큐와 expired 큐 swapping
* CFS : 프로세스마다 weight 정의, 이거에 기반해서 CPU의 bandwidth를 정확히 맞춤, Virtual runtime필드 사용, 내부적으로 최솟값 구하기 위해 레드블랙트리 사용
* 리눅스의 현재는 CFS
'CS > OS' 카테고리의 다른 글