Operating System: 06. 멀티프로세서 스케줄링
멀티프로세서 스케줄링에 대한 새로운 문제점을 이해하기 위해서는
단일 CPU 하드웨어와 멀티 CPU 하드웨어의 근본적인 차이에 대한 이해가 필요하다.
멀티프로세서 구조에 따른 차이
다수의 프로세서간의 데이터 공유,하드웨어 캐시의 사용방식에서 근본적인 차이가 발생한다.
1. 캐시 일관성 문제(cache coherence)
- 캐시 일관성 문제를 살펴보기 전에, 캐시에 대해서 살펴본다.
- CPU에는 하드웨어 캐시 계층이 존재한다. 자주 접근되는 데이터를 캐시에 임시로 가져다 둠으로써 크고 느린 메모리를 빠른 메모리처럼 보이게 한다.
- 캐시는 지역성에 기반한다.
- 시간 지역성: 데이터가 한 번 접근되면 가까운 미래에 다시 접근되기 쉽다는 것이다.
- 공간 지역성: 프로그램이 주소 x의 데이터에 접근하면 x 주변의 데이터가 접근되기 쉽다는 것이다.
- 멀티 프로세서 시스템에서 CPU마다 캐시를 가지고 있다면 CPU1 캐시에 존재하는 데이터가 CPU2 캐시에는 존재하지 않아서 데이터 불일치 문제가 생긴다는 것이다.
기본적인 해결책
- 여러 개의 프로세스들이 하나의 메모리에 갱신할 때에는 항상 공유되도록 한다.
- 버스 기반 시스템에서는 버스 스누핑(bus snooping)이라고 한다.
- 캐시 데이터에 대한 변경이 발생하면, 자신의 복사본을 무효화시키거나(자신의 캐시에서 삭제), 갱신(새로운 값을 캐시에 기록)한다.
2. 동기화 문제
- 캐시에 일관성이 보장된다고 하더라도, 프로그램 또는 운영체제는 공유데이터에 접근할 때
동기화 기법을 사용해야 한다. - 이러한 상호배제를 보장하는 기법에선 락-프리(lock-free) 데이터 구조 등이 있다.
3. 캐시 친화성(cache affinity)
- 캐시 친화성이란 이전에 실행되었던 CPU에서 실행하는 것이 효율이 좋다. 그 이유는 프로그램이 실행될 때 프로세스는 해당 CPU 캐시와 TLB에 상당한 정보를 올려놓기 때문이다. 매번 다른 CPU에서 실행한다면 필요한 정보를 다시 탑재해야 하는 오버헤드가 발생한다.
4. 스케줄링 방식
1) 단일 큐 스케줄링(single queue multiprocessor scheduling, SQMS)
- CPU가 2개라면 실행할 작업 2개를 선택하는 것이고, 단순하다는 장점이 있다.
- 2가지 단점이 있다.
확장성(scalability) 결여 문제
- 스케줄러가 다수의 CPU에서 제대로 동작하기 위해서는
코드에 일정 형태의 락을 삽입한다.
- 단일 락에 대한 경쟁이 증가할수록 성능이 크게 저하된다.
캐시 친화성 문제
- 각 CPU는 공유 큐에서 다음 작업을 선택하기에 각 작업은 CPU를 옮겨 다니게 된다.
- SQMS 스케줄러는 가능한 한 프로세스가 동일한 CPU에서 재실행될 수 있도록 시도한다.
그러나 구현이 복잡해진다는 단점이 있다.
2) 멀티 큐 스케줄링(multi queue multiprocessor scheduling, MQMS)
- CPU마다 큐를 하나씩 두는 것이다.
- 확장성이 좋다. CPU 개수가 증가할수록, 큐의 개수가 증가하므로 락과 캐시 경합이 문제되지 않는다.
워크로드의 불균형(load mbalance)
- 작업이 한 CPU에게 쏠리는 현상을 방지하기 위해 분배가 필요하다.
- 작업 훔치기(work stealing)이라는 기술은 작업의 개수가
낮은 큐가 다른 큐에 작업이 많은지 검사하는 것이다.
작업이 많다면, 하나 이상의 작업을 가져와서 균형을 맞춘다.
5. Linux 멀티프로세서 스케줄러
1) O(1) 스케줄러
- 멀티 큐를 사용한다.
- 우선순위 기반 스케줄러(MLFQ와 유사)
- 우선순위가 가장 높은 작업을 선택한다.
2) Completely Fair Scheduler(CFS)
- 멀티 큐를 사용한다.
- 결정론적(deteministic) 비례배분(proportional share) 방식이다. (보폭 스케줄링과 유사)
3) BFS 스케줄러
- 단일 큐를 사용한다.
- 비례배분 방식이다.