[한권떼기] 운영체제 05번째. 멀티프로세서 스케쥴링

**본 글의 일부분은 서적 'Operating Systems: Three Easy Pieces by Remzi H.Arpaci-Dusseau, Andrea C.Arpaci-Dusseau', 'Operation System Concepts Abraham Silberschatz 외 2' 내의 이미지와 내용을 포함하고 있습니다

 

멀티프로세서 스케쥴링

멀티코어란 하나의 칩에 여러 개의 CPU(=프로세서)가 있는 것

단순히 멀티코어를 사용했다고 해서 성능이 향상되지는 않으며, 프로그램단에서 쓰레드를 이용해 병렬처리를 해야 성능이 좋아짐

 

 

캐시의 통일성(coherence) 문제

멀티코어 환경에서 캐시 불일치 문제가 아래와 같이 생길 수 있음

CPU0이 메모리에서 A를 읽어 캐시에 저장 -> 메모리에서 A가 A'로 바뀜 -> CPU1이 메모리에서 A'를 읽어 캐시에 저장 -> CPU0가 기록하는 것과 CPU1이 기록하는 것이 서로 다름 => 통일성이 깨짐 

 

해결법

Bus snooping을 이용하여 메모리 업데이트가 일어나는 것을 관찰함

CPU0가 캐시에 보관하고 있는 데이터에 업데이트가 일어나면 CPU0 캐시 데이터를 invalid하거나 세부적으로 업데이트 시킴

 

 

캐시 유사성 (Cache Affinity)

OS가 다수의 CPU가 있을 때 어떤 프로세스를 어떤 CPU에 할당시킬 건지 결정해야 함

이 때 CPU에는 캐시가 있기 때문에 가급적이면 이전에 프로세스를 처리했던 CPU에 할당해서 캐시를 활용해주는 것이 좋음 -> cache affinity

 

MQMS (Multi-queue Multiprocessor Scheduling)

 

각 큐에 프로세스들을 넣고, CPU0, CPU1을 큐와 연결해서 특정 큐에 있는 프로세스는 계속 특정 CPU에서만 수행되도록 함

 

문제점

하나의 큐에 있는 프로세스가 다 종료되어버리고, 다른 큐에는 프로세스가 꽉 차있다면 큐 간 프로세스 개수의 불균형이 생김

=> Migration을 이용하여 비어있는 큐에다가 다른 큐에 있는 프로세스를 넣어줌

하지만 Migration을 하기 위해 비어있는 큐를 찾고, 이걸 다른 곳으로 가져가는 작업은 오버헤드가 큼

 

문제점의 해결

큐가 비어있지 않도록 하기 위해서 time slice와 priority를 도입하여 다음과 같은 방식을 고안

O(1) scheduler

active array와 expired array를 두어 각 우선순위 큐별로 프로세스가 종료되면 active array에서 expired array로 옮김

이를 반복해서 한쪽 큐가 다 비면 expired array를 active array로 바꿔치기함

또한, priority가 높을수록 타임 퀀텀이 상수 차이만큼 time slice를 더 길게 줌

CFS (Complete Fair Scheduling)

O(1)과 비슷하지만, 우선 순위의 차에 따라서 time slice를 배분함