23. CPU Scheduling(3)

안녕하세요. 오늘은 Multicore 스케쥴링 방식에 대해 알아볼까 합니다. 지난 포스팅까지는 Single CPU, Single Core를 가정하고 설명드렸습니다. FCFS, SJF, 우선순위, Round robin, Multilevel queue 스케쥴링에 대해 알아보았었는데요. 사실 Single core에서 Multicore로 넘어온지도 오래되었고(현재 쿼드코어 이상이 보편화되어 있습니다.) 최근에는 multiprocessor보다 multicore로 가는 경향이 있습니다. GPU(Graphical processing unit)를 AI에 사용하는 것도 멀티코어 스케쥴링에 대해 알아보아야 하는 중요한 이유 중 하나입니다. 불과 5년전에는 컴퓨터 화면의 렌더링을 효율적으로 하게하기 위한 하드웨어 accelerators 역할이였다면 최근에는 AI분야에서 활용하고 있습니다.(GPU의 수많은 코어를 AI 연산에서 병렬적으로 처리할 수 있는 행렬 계산에 활용합니다.) 멀티프로세서에 대해 추가적으로 말씀드리자면 2000년대까지도 멀티프로세서를 많이 하긴하였지만 관련 연구는 한계에 이르러 CPU내의 코어를 늘리는 추세입니다. 왜 한계에 이르렀을까요?

CPU는 clock을 계속 높일 수 없는 한계가 있습니다. 물리적 한계(열)때문입니다. 또 bus들이 computation 속도를 못 따라갑니다. 프로세스마다 cache가 있는데 coherence하게 동작해야 하는 것에 어려움을 느낀 것이죠. 그래서 scalability 측면에서 멀티코어가 유리합니다.

 

SMP & CMP

Symmetric multi-processing 멀티 프로세서 시스템 : 하나의 메인 메모리를 여러 cpu가 공유하는 시스템

Chip level multi-processing 멀티 코어 시스템 : 하나의 CPU에 여러 코어가 붙은 것

 

CPU : 코어를 포함하여 pc 레지스터 등을 다룰 수 있는 것. 코어 : 각 명령어를 수행하기 위한 ALU(Arithmetic Logic Unit), CU(control unit), 레지스터를 가지는 것.

 

SMP는 명령어를 병렬로 수행하고 CMP는 연산을 병렬로 수행하는 것이라고 볼 수 있습니다. 기술의 발전에 따라 코어의 연산도 조금 더 무거워졌고 이를 Simultaneous Multithreading이라고 하여 스레드 개념을 사용하였는데, 인텔 CPU에서 이를 하이퍼스레딩이라고 불렀습니다.(인텔에서 홍보하기 위해 만든 용어라고도 하던데.. 컴퓨터 구조과목에서 들어보신 분들도 있으실 것 같습니다.)

 

먼저 부하균등화와 친화성 개념을 살펴보겠습니다.

 

23.01. Load balancing

가장 중요한 것은 프로세스를 모든 코어에 적절하게 분배하는 것입니다. 전체적인 throughput을 높이기 위해서죠. 각각의 코어에 대해서는 Round Robin을 사용하지만 load balancing을 추가합니다. 이때 2가지 방식이 있습니다.

 

먼저, 코어마다 Ready queue를 두는 경우는 편리해 scalability 측면에서 유리하지만 일부 코어에 프로세스가 집중되지 않도록 해야 합니다. 즉, 각 queue들의 state를 알 수 있어야 합니다.

전체에 하나의 Ready queue를 사용하는 경우는 사용 가능한 코어에 차례대로 프로세스를 할당할 수 있다는 점에서 관리가 간단합니다. 하지만 프로세스의 수가 늘어나게 되면 queue를 접근하는 동기화를 하게 되는데 순서를 두고 처리를 해주어야 합니다.(여러 개의 프로세스가 동시에 queue에 접근하는 것을 어떻게 처리할 것인지 고민해야 합니다.) 현대의 OS에서는 Ready queue를 프로세서마다 분리하여 사용합니다.

 

23.01.1. 개별 Ready queue를 사용하는 system의 load balancing

Linux를 예로 들면 몇 ms마다 push migration 알고리즘과 ready queue가 비면 pull migration 알고리즘을 수행하여 부하 균등화를 시도합니다. push migration은 특정 task가 주기적으로 각 프로세서의 부하를 검사하여 과부하 프로세서의 프로세스들을 idle 또는 less-busy 프로세서로 migration 시킵니다. pull migration은 idle 프로세서가 busy 프로세서에서 대기중인 프로세스들을 자신에게 migration시키고 push migration과 exclusive한 알고리즘은 아닙니다. 

 

 

23.02. Affinity

Affinity 개념은 과거에 수행했던 코어에 프로세스를 할당하는 방법입니다. 과거에 수행했던 코어에 할당해서 남아있을지도 모르는 cache를 활용할 수 있습니다. 즉, 프로세서 친화성은 프로세스가 migration을 피하고 다음 스케쥴링에서도 현재 프로세서에서 계속 실행되도록 하는 것입니다. 만약 프로세서를 이동한다면 cache invalidation가 필요해 cost가 증가합니다. 이때 친화성을 soft인지 hard인지 나눌 수 있는데 hard affinity에서는 프로세서 집합을 설정하여 사용합니다.(메모리 구조 등 시스템 형태에 따라 프로세서 친화성과 집합을 결정합니다.) 참고로 앞서 살펴보았던 load balancing은 affinity의 장점과 충돌합니다.

 

 

23.03. Multiple-processor Scheduling

일단 여기서 모든 processor가 homogeneous system이라는 것을 가정하겠습니다.  Multiprocessor 스케쥴링에는 asymmetric 다중 처리와 symmetric 다중 처리가 있습니다. 위에서 살짝 언급한 SMP는 symmetric 다중 처리방식이라고 생각하시면 됩니다. 비대칭 다중처리는 master processor가 스케쥴링, I/O, 시스템 활동을 처리하면서 OS의 커널 역할을 수행하고 나머지 프로세서들은 user code만 수행하는 방식입니다. 자료 고유 필요성을 배제하기 때문에 간단히 설계할 수 있다는 점이 장점입니다. 

반면 대칭 다중처리에서는 각 프로세서가 독자적으로 스케쥴링 됩니다. 

 

 

23.04. Multithread-processor Scheduling

Multithread 프로세서는 하나의 물리적 프로세서(core)에 다수의 논리적 프로세서를 제공하는 프로세서입니다. 연산장치를 공유하는 것이라고 생각하시면 될 것 같습니다. 공유된 연산장치를 하드웨어가 별도의 레지스터 집합을 가진 논리 프로세서에게 물리 프로세서를 스케쥴링합니다.(별도의 레지스터 집합을 가져 빠른 context switching이 가능합니다.) 즉, 메모리 접근을 하는 스레드가 있다면 다른 스레드가 연산장치를 활용한다는 것입니다.

 

 

23.05. Multicore-processor Scheduling

멀티코어는 같은 chip에 multi threaded core를 보유한 프로세서를 말합니다. Multithreaded multicore processor는 아래와 같은 그림이 되겠군요.

OS가 스레드에게 hardware thread를 스케쥴링 : coarse-grained multithreading

coarse-grained의 뜻을 아시면 이해하기 편하실 수도 있습니다. 매 cycle이 아닌 큰 event가 발생하면 스케쥴링을 하는 것입니다.

 

CPU hardware가 haredware thread에게 core를 스케쥴링 : fine-grained multithreading

좀 쉬운말로 생각해보자면 매 cycle마다 다른 thread로 바뀔 수 있습니다. 즉, PC와 GPR(General purpose register)이 각 스레드마다 갖고 있기 때문에 dependency가 줄어듭니다. 또한 전체성능과 latency toerance가 향상됩니다. 다만, 하드웨어가 복잡해지고 single thread의 퍼포먼스가 내려가며 structual hazard resource issue가 있습니다.(스레드 switching 동작을 수행할 hardware logic이 추가로 필요하기 때문입니다. 즉, 프로세서 내에 레지스터 수를 충분히 보장한다면 context switching이 수행될 때, 레지스터에 대한 store/load를 줄이는 것입니다.)

 

최종적으로 살펴볼 기술은 SMT입니다. : Simultaneous Multithreading

SMT는 한 clock에 할 수 있는 모두를 가져옵니다. 따라서 bubble이 줄어듭니다. 스레드간 우선순위를 부여해서 필요한 job에 대해 먼저 처리를 한다면 위에서 살펴본 2개의 기술에 비해 single thread performance suffers도 줄일 수 있습니다. 물론 구현하기는 어렵습니다. 여러 policy가 있기 때문에 전체 성능과 single 스레드 성능을 모두 잡을 수는 있지만 추가적인 resource들이 필요해 cost가 높습니다.(AMD가 SMT를 포기했던 적도 있다는 이야기를 들은 적이 있습니다. 라이젠에는 SMT가 적용되었다고 들었습니다.)

 

 

오늘은 Multicore 스케쥴링 방식에 대해 알아보았습니다. 이 내용은 컴퓨터구조 과목을 배우신 분들이라면 약간 맛본 내용도 있으실거라고 생각합니다. 여러가지 하드웨어 이슈들도 있는만큼 컴퓨터구조 과목에 대한 깊은 이해가 필요한 topic이였습니다. 물론 실제로 사용하는 시스템의 스케쥴러들이 하나의 스케쥴링 방식만 사용한다고 단정지을 수는 없고 여러개의 스케쥴링 방식의 장점들을 따거나 환경에 따라 스케쥴링 정책을 실시간으로 바꾸는 경우도 있을 겁니다.(실시간 스케쥴링도 흥미로운 주제가 될 것 같습니다.) 마지막으로 질문과 오류지적은 언제나 환영이니 댓글로 남겨주시면 감사하겠습니다.