과제 때문에 정리한 내용인데 블로그 글로 좋은 것 같아서 올려본다. 이 내용은 Operating Systems: Three Easy Pieces - 10 Multiprocessor Scheduling을 요약한 것 이다.

멀티코어 프로세서등으로 인해 멀티 프로세서 시스템이 흔해졌다. 이에 따라, 멀티프로세서를 효율적으로 쓰기 위한 방법이 필요해졌다.

싱글 프로세서 시스템에서 멀티프로세서 시스템으로 갈 때 가장 중요한 것들은 하드웨어 캐시의 사용과 CPU간의 데이터 공유이다. 하드웨어 캐시는 메인 메모리에 비해 작은 대신 액세스가 빠른 메모리이다. 하드웨어 캐시는 locality 기반으로 작동한다. locality는 2가지가 있는데, temporal locality는 액세스 된 데이터는 오래 지나지 않아 다시 액세스 될 가능성이 높다는 점에서 착안한 것이고 spatial locality는 사용된 데이터의 주변에 있는 데이터를 사용할 가능성이 높다는 점에서 착안한 것이다. 이 시스템은 프로세서가 하나인 시스템에선 매우 단순하고, 성능을 개선해주지만, 멀티 프로세서 환경으로 가면 문제가 생긴다. 메인 메모리를 수정하는 것은 매우 느리기 때문에, CPU는 write operation을 수행할 때 메인 메모리의 값을 변경하는 대신 캐시의 값만 수정하고 메인 메모리는 나중에 업데이트하는데, 업데이트 되기 전에 다른 프로세서가 메인 메모리의 값을 읽으면 동시성 문제가 생긴다. 그래서 멀티 프로세서를 사용하는 프로그램을 짤 땐 lock을 거는 등 주의해서 짜야한다.

특정한 작업을 여러 개의 타임 슬라이스로 쪼개서 스케줄링할 때 같은 CPU를 사용하도록 하는 경우 다른 CPU를 사용하는 경우보다 캐시 등의 이유로 인해 더 빨라질 수 있다. 이를 cache affinity라고 한다. 커널은 성능을 위해 cache affinity를 고려해서 작업을 스케줄링해야 한다.

아주 간단한 스케줄링 알고리즘중 하나는 SQMS(single-queue multiprocessor scheduling)이다. 이는 구현이 간단한 대신 lock이 필요하기 때문에 프로세서가 많아지면 성능에 큰 문제가 생긴다. 또한, cache affinity 문제도 있는데, 모든 CPU가 한 개의 큐에서 작업을 가져오기 때문에 생기는 문제로, 작업이 여러 개의 CPU 사이를 왔다갔다하게 되기 때문에 성능이 나빠진다. 따라서 SQMS의 구현체는 대부분 cache affinity를 보존하기 위한 알고리즘을 포함한다.

싱글 큐 방식의 문제점을 극복하기 위해, 일부 시스템에서는 멀티 큐 방식을 사용한다. 이를 MQMS (multi-queue multiprocessor scheduling)이라고 한다. CPU 작업은 한 큐에만 추가되고, 각 큐의 작업들은 lock등을 피하기 위해 독립적으로 스케줄링된다. 이러한 점 때문에, MQMS 방식은 태생적으로 cache affinity를 잘 활용한다. 멀티 큐 방식에는 load imbalance 라는 근본적인 단점이 있다. 이는 특정 큐에 들어간 작업들만 오래 걸리는 경우, 다른 큐를 처리하는 CPU들이 놀게 되는 일이 생길 수 있다는 걸 의미한다. 이를 해결하기 위해 다른 CPU의 작업 큐에서 작업을 훔쳐올 수 있다. 이를 work stealing이라고 부른다.

리눅스의 경우엔 3가지 (O(1), CFS, BFS) 스케줄링 알고리즘이 있다. O(1)과 CFS는 MQMS고, BFS는 SQMS이다. O(1) 스케줄러는 interactivity에 집중한 스케줄러로, priority 기반인 반면 CFS와 BFS는 proportional-share 방식이다.