Multiprocessor

• 캐시

프로그램을 빠르게 실행하기 위해 존재
자주 접근되는 데이터를 캐시에 임시로 저장해 크고 느린 메모리를 빠른 메모리처럼 보이게 함
캐시는 시간지역성(temporal locality)과 공간지역성(spatial locality)에 기반

» 시간지역성

데이터가 한번 접근되면 가까운 미래에 다시 접근되기 쉬움
ex) 반복해서 접근되는 변수 또는 명령어

» 공간지역성

특정 주소의 데이터를 접근하면 주변 데이터를 접근하기 쉬움
ex) 전체 배열을 차례대로 접근하는 프로그램, 명령어코드(순차적으로 실행됨)

• 캐시 일관성(cache coherence) 문제

캐시 일관성(영어: cache coherence)이란 공유 메모리 시스템에서 각 클라이언트(혹은 프로세서)가 가진 로컬 캐시 간의 일관성을 의미

각 프로세서가 자신 만의 로컬 캐시를 가지고 다른 여러 프로세서와 메모리를 공유하고 있을 때, 캐시의 갱신으로 인한 데이터 불일치 문제가 발생

해결책

기본적인 해결책은 하드웨어에 의해 제공됨(올바른 순서로 처리되도록 시스템을 관리)

여러 프로세서들이 하나의 메모리를 갱신할때는 항상 공유되도록 버스 스누핑을 사용
캐시데이터가 변경되면 복사본을 무효화(write-invalidate)시키거나 갱신(write-update)함

• 동기화

캐시가 일관성 유지를 담당해 주더라도, 프로그램이나 운영체제는 동기화때문에 공유 데이터 접근에 신경을 써야함
주로 락과 같은 상호배제를 보장하는 기법사용
-> 성능문제, cpu갯수 많아질수록 느려짐

• 캐시 친화성(cache affinity)

캐시를 로드하는데 시간이 걸리므로, 같은 프로세스는 같은 cpu에서 계속 실행하는게 성능에 유리함

Multiprocessor scheduling

멀티 코어 프로세서가 대중화 되면서, 응용 프로그램이 멀티 스레드를 통해 병렬로 실행되도록 작성
멀티쓰레드는 작업을 여러 cpu에 할당하며 더 많은 cpu를 사용해 더 빠르게 실행,
이때 multi-cpu(multiprocessor) scheduling이 중요함

• SQMS (Single Queue Multiprocessor Scheduling)

단일 프로세서의 스케줄링 프레임워크를 그대로 사용, 하나의 큐에서 cpu에 분배할 작업을 선택
구현이 쉽고 워크로드의 균형을 맞추기 쉽지만, 확장성과 캐시친화성이 나쁨

» 확장성 문제

스케줄러가 여러 cpu에서 사용되므로 lock을 사용해야함
-> cpu갯수 늘어날 시 성능저하

» 캐시친화성 문제

위에서 볼 수 있듯 작업이 실행되는 cpu가 바뀌면서 캐시 친화성 문제가 생김
아래와 같은 방식 스케줄링하도록 하여 해결가능하나, 구현이 복잡해짐

• MQMS (Multi Queue Multiprocessor Scheduling)

cpu마다 que를 따로 둠
확장성과 캐시친화성이 좋지만, 구현이 복잡하고 워크로드 불균형이 발생

» 장점

확장성 좋음
cpu갯수 증가할 수록 queue의 갯수도 증가
-> lock으로 인한 성능저하 X

캐시 친화적
같은작업이 같은 cpu에서 계속 실행됨

» 단점

워크로드 불균형

해결책

지속적인 이주(migration, 작업을 이동시키는것을 의미)를 통해 워크로드 밸런스를 맞춤
작업훔치기(work stealing) 방식 사용
-> 일정 시간마다 작업의 개수가 낮은 큐가 다른 큐에 더 많은 작업이 있는지를 검사함