multiprocessor scheduling

multiprocessor

multicore
: 여러개의 CPU 코어가 하나의 칩에 내장

응용 프로그램을 병렬로 실행해야함
-> 보통은 multi thread를 이용

멀티 프로세서 스케줄링은 어떻게 하는가 문제 발생

차이점

• 하드웨어 캐시의 사용방식

  캐시

  메인 메모리에서 데이터를 가져오게 되면 오랜 시간이 걸리기 때문에 다시 사용될 것으로 예상되는 데이터를 프로세서가 CPU 캐시공간에 저장해둠

  locaity (지역성)

  • temporal (시간)
    데이터가 한번 접근되면 가까운 미래에 다시 접근할 가능성 높음
  • spatial (공간)
    접근된 데이터 주변 주소의 데이터 접근 가능성 높음

  만약 프로세서가 여러개라면 cache coherence(캐시 일관성 문제)가 발생할 가능성이 생김
  ex) 프로세서 A가 특정 메모리의 값을 변경하는 데 시간이 걸리므로
  A가 값을 변경한 후 B가 같은 메모리의 값에 접근했을 때 변경전 메모리값을 가져올 수 있다.

  -> 하드웨어로 해결 가능

  프로그램에서는 동기화 기법 사용 (lock)

  cache affinity (캐시 친화성)

  가능한 한 동일한 프로세스는 같은 CPU에서 실행하는 것이 효율이 좋다
  (CPU에서 이미 정보가 존재한다면 더 빠르게 실행되기 때문)

• 다수의 프로세서간의 데이터 공유

single queue multiprocessor scheduling (SQMS)

기본 프레임워크를 그대로 사용하는 단순한 멀티 프로세서의 스케줄러

단점

• scalability (확장성) 결여
  실행할 다음 큐를 찾을 때 락을 건다
  -> 성능이 저하됨

• 캐시 친화성 저하
  큐의 특성상 순서대로 돌면서 cpu를 방문하게 되므로 ..

  SQMS의 해결법

  특정 작업 cpu개만큼은 캐시 친화성에 맞게 같은 CPU에서 실행되도록 하고, 나머지는 오버헤드를 균등하게 하기 위해 분산시킴

  multi-queue multiprocessor scheduling (MQMS)

  SQMS와 달리 여러개의 스케줄링 큐로 구성

  작업이 들어오면 특정 큐 하나에 배치됨
  그 후 각각 독립적으로 스케줄함
  -> 확장성 좋아지고 캐시 친화적

  단점 : load imbalance (워크로드 불균형)
  -> 프로세스를 이주시켜서 해결

  ---

  이주는 언제 될지 어떻게 아는가..?
  work stealing (작업 훔치기) 방식을 통해 간간히 작업의 개수가 적은 큐가 많은 큐를 검사하고 한개 이상의 작업을 가져온다 (간간히가 얼마나인지는 알아서,,,)

  ---