10. Multiprocessor Scheduling (Advanced)

HOW TO SCHEDULE JOBS ON MULTIPLE CPUs?!

 

10.1 Background: Multiple Architecture

 - 싱글 CPU와 멀티플CPU의 차이

Single CPU With Cache	Multiple(two, in this case) CPUs With Caches sharing Memory
출처 : Operating Systems_Three Easy Pieces	출처 : Operating Systems_Three Easy Pieces

 - 캐시 : locality 특성

temporal locality(시간)	spatial locality(공간)
특정 데이터에 대한 접근이 있었다면, 가까운 미래에 그 데이터에 대한 접근이 있을 것이라고 예측(예_loop)	특정 데이터에 대한 접근이 있었다면, 그 데이터 주변 데이터에 대한 접근을 예측(예_배열)

 - 하나의 메모리를 공유하는 multiple processor같은 경우 무슨 문제가 발생할까?(Figure 10.2)

  : 하나의 캐시에서 변경한 데이터가 다른 캐시에서는 반영되지 않는 문제

  : 일명, cache coherence

 - 해결책 : bus snooping (각각의 캐시가 bus(캐시와 메인메모리 연결)를 주시)

 

10.2 Don't Forget Synchronization

 - 여러 CPU간의 공유 데이터가 있는 경우 lock을 걸고 푸는 등의 상호배제를 실현해야 함

 

10.3 One Final Issue: Cache Affinity

 - CPU와 Cache의 긴밀도(?)

 - 프로세스가 작업 수행 중 time slice마다 계속해서 다른 CPU를 할당 받는다면, performance는 낮아지게 됨(동일 CPU이어야 cache의 빠른 수행 장점이 실현되므로)

 

10.4 Single-Queue Scheduling(SQMS)

 - Single-Queue Multiprocessor Scheduling

 - 장점 : 구현이 쉬움

 - 단점

  : 1. scalability(CPU 개수가 늘어날수록, 상호배제를 위한 lock의 횟수가 늘어나게 되고 그에 따른 오버헤드 증가)

  : 2. cache affinity 문제(아래 그림에서와 같은 작업 수행이 이루어지면, 캐싱 효과 줄어들게 됨)

출처 : Operating Systems_Three Easy Pieces

 - 해결책

출처 : Operating Systems_Three Easy Pieces

  : E를 제외한 모든 작업은 동일 CPU에서만 작업이 이루어지므로 캐싱으로 인한 작업 수행 효율을 누림

 

10.5 Multi-Queue Scheduling(MQMS)

 - CPU개수와 큐의 개수 동일(각각의 CPU에서는 각각의 스케줄링 방식 선택. 예_RR,...)

 - 장점 : 싱클 큐에서의 scalability 문제 해결

 - 단점 : 로드 언밸런싱

출처 : Operating Systems_Three Easy Pieces

  : 위의 예에서처럼 A가 B와 D에 비해 두 배의 CPU타임을 할당받는 unfair한 현상이 일어나거나, 혹은

출처 : Operating Systems_Three Easy Pieces

  : 다음과 같은 자원 낭비 발생

 

 - 해결책 : migration

 

-출처-

<OPERATING SYSTEMS three easy pieces>

 

REMZI H. ARPACI-DUSSEAU

ANDREA C. ARPACI-DUSSEAU

UNIVERSITY OF WISCONSIN-MADISON