13.1 멀티프로세서 구조
멀티프로세서와 단일 프로세서의 차이
- 단일 CPU 시스템: 캐시를 사용하여 메모리 접근 속도를 높임.
- 시간 지역성: 자주 사용하는 데이터는 다시 접근할 가능성이 높음.
- 공간 지역성: 특정 데이터와 인접한 데이터도 함께 접근될 가능성이 높음.
- 멀티프로세서 시스템: 여러 CPU와 하나의 공유 메모리를 사용.
- 캐시 일관성 문제: 각 CPU의 캐시와 메인 메모리 데이터가 불일치할 수 있음.
- 해결 방법:
- 버스 스누핑 (Bus Snooping): 캐시가 메모리 버스를 모니터링하며 데이터를 갱신하거나 무효화.
- 하드웨어 프로토콜: 캐시의 데이터 상태를 추적하여 일관성 유지.
13.2 동기화 문제
공유 데이터 동기화
- 여러 CPU가 동일한 데이터/구조체를 동시에 갱신하면 데이터 손상이 발생.
- 해결책:
- 락 (Lock): 작업 중인 데이터를 보호.
- Mutex 사용 예시: pthread_mutex를 사용하여 공유 데이터 접근 보호.
성능 문제
- 락 사용 시 CPU 개수가 증가할수록 성능 저하.
- 동기화된 데이터 구조에 접근하는 데 시간이 오래 걸림.
- 병렬성에 영향을 미침.
13.3 캐시 친화성
캐시 친화성의 중요성
- 캐시 친화성: 프로세스가 동일한 CPU에서 실행될 때 성능 향상.
- 이미 CPU 캐시에 적재된 데이터를 재사용 가능.
- 문제: 프로세스가 다른 CPU에서 실행되면 캐시 재적재로 성능 저하.
해결 방법
- 캐시 친화적 스케줄링: 프로세스가 최대한 동일한 CPU에서 실행되도록 시도.
- 일정 작업은 동일 CPU에 할당, 일부 작업은 분산.
13.4 단일 큐 멀티프로세서 스케줄링 (SQMS)
개념
- 단일 큐를 사용하여 여러 CPU에서 작업을 스케줄링.
- 장점: 단일 프로세서 스케줄링 구조를 재사용 가능 → 간단한 구현.
단점
- 확장성 부족:
- 단일 큐 접근 시 락 사용으로 성능 저하.
- CPU 개수가 증가하면 락 경쟁이 심화.
- 캐시 친화성 문제:
- 프로세스가 여러 CPU로 옮겨다니며 캐시 효율성 감소.
해결 방법
- 친화성 기반 스케줄링:
- 가능한 프로세스가 동일한 CPU에서 실행.
- 일부 프로세스는 다른 CPU로 이동시켜 형평성을 유지.
SQMS의 장단점 요약
장점
- 단일 큐를 사용하여 구현이 단순.
- 기존 단일 CPU 스케줄러 구조를 활용 가능.
단점
- 확장성 부족 (락 경쟁으로 인한 성능 저하).
- 캐시 친화성 문제로 인해 성능 저하 가능.
멀티프로세서 스케줄링은 캐시 일관성과 캐시 친화성을 고려해야 하며, 이를 위해 복잡한 정책 설계와 최적화가 필요하다.
13.5 멀티 큐 스케줄링 (MQMS)
개념
- 멀티 큐 스케줄링: CPU마다 독립적인 스케줄링 큐를 사용하여 확장성과 캐시 친화성을 향상.
- 작업은 하나의 큐에 배치되고, 각 큐는 독립적으로 작동.
장점
- 확장성:
- 각 큐가 독립적으로 작동하므로 락 사용이 최소화되어 확장성 향상.
- 캐시 친화성:
- 프로세스가 동일한 CPU에서 계속 실행되므로 캐시 재사용 가능.
문제점
- 워크로드 불균형:
- 일부 큐는 작업이 많고, 다른 큐는 유휴 상태가 될 수 있음.
- 결과적으로 CPU 자원이 효율적으로 사용되지 않음.
- 이주 (Migration) 필요:
- 워크로드를 균등하게 분배하기 위해 작업을 다른 큐로 이동해야 함.
Migration 구현
- 간단한 경우:
- 유휴 상태의 CPU로 작업을 이동.
- 복잡한 경우:
- 작업을 지속적으로 이동하며 워크로드 균형 유지.
- 예: 타임 슬라이스 단위로 작업을 교환.
워크로드 균형 방법
- 작업 훔치기 (Work Stealing):
- 작업이 적은 큐가 작업이 많은 큐에서 작업을 가져오는 방식.
- 문제점:
- 큐를 자주 검사하면 오버헤드 증가.
- 너무 적게 검사하면 워크로드 불균형이 악화.
13.6 Linux 멀티프로세서 스케줄러
주요 스케줄러
- O(1) 스케줄러:
- 특징:
- 멀티 큐 기반.
- 우선순위 기반 스케줄러.
- MLFQ와 유사하게 우선순위를 동적으로 변경.
- 장점: 상호작용 중심의 작업에 유리.
- 특징:
- Completely Fair Scheduler (CFS):
- 특징:
- 멀티 큐 기반.
- 비례 배분 방식 (Proportional Share).
- 보폭 스케줄링과 유사.
- 장점: 작업 간 공정성 제공.
- 특징:
- Brain Fuck Scheduler (BFS):
- 특징:
- 단일 큐 기반.
- EEVDF(Earliest Eligible Virtual Deadline First) 방식 사용.
- 장점: 단일 큐 기반의 단순한 설계.
- 특징:
