요즘 현대시대에 멀티프로세서가 기본으로 사용하는 시대이다.
컴퓨터가 빨라지고 대중적으로 보급된 원인에는 CPU 코어가 하나의 침에 내장된 멀티코어 프로세스가 존재한다고 본다.
우리가 아는 공부한 컴퓨터의 기초적인 이론 내용을 기반으로한 전통적인 응용프로그램은 오직 하나의 CPU만 사용한다.
더 많은 CPU를 추가해도 더 빨리 실행되지 않는다. 이 문제를 해결하려면 응용 프로그램을 병렬(parallel)로 실행되도록 다시 작성해야한다.
보통 쓰레드를 많이 이용하는데, 멀티 쓰레드 응용 프로그램은 작업을 여러 CPU에 할당하며, 따라서 더 많은 수의 CPU가 주어지면 더 빠르게 실행된다.
배경 : 멀티 프로세서 구조
먼저 근본적인 싱글 프로세서와의 차이를 알아야한다.
다수의 프로세서간에 데이터의 공유, 하드웨어 캐시의 사용방식에서 근본적인 차이가 발생한다.
너무 깊게 들어가면 어지러우니 기본만 봐보자.
더 배우고 싶으면 컴퓨터 구조 전공책을 사서 뜯어봐야한다.
단일 CPU 시스템에는 하드웨어 캐시 계층이 존재한다. 이 캐시는 프로그램을 빠르게 실행하기 위해 존재한다. 캐시는 메인 메모리에서 자주 사용되는 데이터의 복사본을 저장하는 작고 빠른 메모리이다.
예전에 공부했을지는 모르지만 캐시 계층구조를 봐보면 편할 것이다.
메인 메모리는 모든 데이터를 저장하지만 느리다. 자주 접근 되는 데이터를 캐시에 임시로 가져다 둠으로써 시스템은 크고 느린 메모리를 빠른 메모리 처럼 보이게 한다.
예를 들어, load 명령어를 수행하는 프로그램과 하나의 CPU만 있는 간간한 시스템을 생각해보자.
CPU는 작은 캐시 와 큰 메인 메모리를 갖고 있다.
프로그램이 처음 이 load 명령어를 실행할 때, 데이터가 메인 메모리에 존재하므로, 다시 사용될 것으로 예상한 프로세서는 읽은 데이터의 복사본을 CPU 캐시에 저장한다. 캐시에 존재하는지 검사한다.
캐시에 존재하기 때문에 데이터는 기존보다 훨씬 빨리 접근되고 프로그램은 빨리 실행된다.
이런 이유는 캐시 지역성(locality)에 기반한다. 지역성에는 시간 지역성과 공간 지역성의 두 종류가 있다. 시간적 지역성의 기본 아이디어는 데이터가 한번 접근되면 가까운 미래에 다시 접근 하기 쉽다는것.
루프에서 여러번 반복해서 접근되는 변수 또는 명령어 자체가 자주 접근되는 것.
공간적 지역성의 기본 아이디어는 프로그램이 주소 x의 데이터를 접근하면 x 주변의 데이터가 접근되기 쉽다는 것 이라고 생각하고 넘기자.....
이거는 단순하게 싱글 프로세서에서 생각하면 쉽게 생각되지만 멀티프로세서가 되면 조금 헷갈린다.
위처럼 멀티프로세서 시스템에서 캐시를 사용하는 것은 훨씬 복잡하다.
예를 들어 각각 실행 중인 CPU1,CPU2가 있다고 하자.
두 개의 메인 메모리에서 데이터를 가져온다고 하면 메모리 A가 CPU1에 없어서 가져와서 일단 캐시에 둔다. 메인 메모리 갱신은 나중에한다. 그러는중 CPU2가 A에 접근한다. 그러면 값이 갱신되지 않아 캐시 일관성 문제가 일어난다.
해결책은 하드웨어에 의해 제공된다.
하드웨어는 메모리 주소를 계속 감시하고 항상 올바른 순서로 처리되도록 시스템을 관리한다.
특히, 여러 개의 프로세스들이 하나의 메모리에 갱신할 때에는 항상 공유되도록 한다. 특히, 여러 개의 프로세스들이 하나의 메모리에 갱신할 때에는 항상 공유되도록한다.
버스 기반 시스템에서는 버스 스누핑(Bus snooping)이라는 오래된 기법을 사용한다. 캐시는 자신과 메모리를 연결하는 버스의 통신 상황을 계속 모니터링한다. 캐시 데이터에 대한 변경이 발생하면, 자신의 복사본을 무효화(invalidate) 시키거나, 갱신 한다. 나중쓰기 캐시는 메인 메모리에 쓰기 연산이 지연되기 떄문에 캐시 일관성 유지 문제를 훨씬 복잡하게 만든다. 그러나 기본 기법이 어떻게 동작하는지 대략 상상할 수 있을 것이다.
동기화를 잊지말자
일관성 유지에 대한 모든 일을 캐시가 담당한다면, 프로그램 또는 운영체제 자신은 공유 데이터를 접근할 때 걱정할 필요가 있을까?
정답은 맞다.... 이거는 이전에 공부했던 락에 관해서 이야기하는 것과 같다.
이를 병행성이라고 하는데 나중에 깊숙하게 배워야하니 지금은 걱정하지말자....
CPU들이 동일한 데이터 또는 구조체에 접근할 때(특히, 갱신), 올바른 연산 결과를 보장하기 위해 락과 같은 상호 배제를 보장하는 동기화 기법이 많이 사용된다. 락-프리(lock-free) 데이터 구조 등의 다른 방식은 복잡할 뿐 아니라 특별한 경우에만 사용하는 것이 좋다.
여러 CPU가 동시에 사용하는 공유 큐가 있다고 가정해보자.
캐시의 일관성을 보장하는 프로토콜이 존재하다 하더라도 락이 없이는 항목의 추가나 삭제가 제대로 동작하지 않을 것이다.
typedef struct__Node_t {
int value;
struct __Node_t *next;
}Node_t;
int List_Pop() {
Node_t *tmp = head;
int value = head->value;
head = head->next;
free(tmp);
return value;
}
위는 리스트 삭제 코드인데 간단하게 봐보자.
만약 쓰레드가 해당 코드를 따로 따로 실행하면 free를 2번 실행해서 해제된 데이터를 또 해제하여 오류가 나타난다.
이때 락을 사용하여 올바르게 동작하게 해야한다.
CPU의 개수가 증가할수록 동기화 된 자료구조에 접근하는 연산이 느려지게 된다.
마지막 문제점 : 캐시 친화성
멀티 프로세서 캐시 스케줄러에서의 마지막 문제점은 캐시 친화성(cache affinity)이다.
CPU에서 실행될 때 프로세스는 해당 CPU 캐시와 TLB에 상당한 양의 상태 정보를 올려놓게 된다.
다음 번에 프로세스가 실행 될 떄 동일한 CPU에서 실행되는 것이 유리하다.
해당 CPU 캐시에 일부 정보가 이미 존재하고 있기 때문에 더 빨리 실행될 것이기 때문이다.
다른 CPU에서 부르면 다른 CPU 캐시에 올려야하기 때문에 성능이 더 느려지게 된다.
하드웨어의 캐시 일관성 프로토콜 덕분에 다른 CPU에서 실행되더라도 프로그램이 제대로 실행 될 것이다.
가능한 한 프로세스를 동일한 CPU에서 실행하려고 노력하는 방향으로 결정해야한다.
단일 큐 스케줄링
단일 프로세스 스케줄링의 기본 프레임워크를 그대로 사용하는 단일 큐 스케줄링(single queue multiprocessor scheduling)이라고 부른다.
장점은 뭐.... 단순하다.
기본 정책을 다수 CPU에서 동작하도록 하는데는 많은 변경이 필요하지 않다.
그렇기 때문에 명백한 단점이 있다.
첫번 째는 확장성 결여이다.
스케줄러가 다수의 CPU에서 제대로 동작하게 하기 위해 코드에 일정 형태의 락을 삽입한다.
근데 락은 성능 저하를 초래한다.
단일 락에 대한 경쟁이 늘어나면 CPU 효울이 안나오게 된다.
두번째 문제는 캐시 친화성이다.
한 큐에서 여러 CPU의 작업을 나열해서 CPU 작업에 캐시 입장에서 비효율적이다.
이 문제를 해결하기 위해 SQMS 스케줄러는 가능한 한 프로세스가 동일한 CPU에서 재 실행될 수 있도록 시도한다.
다른 작업들은 오버헤드를 균등하게 하기 위해 여러 군데로 분산시키는 정책을 사옹한다.
CPU들끼리 처리할 프로세스를 이동시켜 구조를 맞추게 하는 방법도 있는데 이거는 구현이 복잡하다.
멀티 큐 스케줄링
단일 큐 스케줄러로 인한 문제로 때문에 일부 시스템은 멀티 큐, 예를 들어 CPU마다 큐를 하나씩 둔다.
이 방식을 멀티 큐 프로세서 스케줄링(Multi-queue muliprocessor scheduling) MQMS 라 부른다.
각 큐는 아마 랄운드 로빈 같은 특정 스케줄링 규칙을 따를 것이다. 다른 스케줄링 방법도 된다.
배치될 큐의 결정은 적당한 방법을 따른다.그 후에는 각각이 독립적으로 스케줄 되기 떄문에 단일 큐 방식에서 보았던 ㅈ어보의 공유 및 동기화 문제를 피할 수 있다.
MQMS가 SQMS에 비해 가지는 명확한 이점은 확장성이 좋다는 것이다.
CPU 개수가 증가할 수록 큐의 개수도 증가하므로 락과 캐시 경합(cache contention)이 더 이상 문제가 되지 않는다.
그리고 캐시 친화적이게 변화한다.
CPU 하나가 따로 관리해서 프로세스를 돌리기 때문에 캐시 친화적이다.
근데 멀티 큐 기반 방식은 근본적인 워크로드의 불균형(load imbalance) 가 존재한다.
예를 들어, 2개의 CPU와 A,B,C,D 4개의 작업이 시스템에 존재한다고 가정하자.
CPU1에서 A,C 그리고 CPU2가 B,D를 처리하고 있는데 C가 종료되면 CPU2는 두개를 처리하고 만약 A마저 더 빨리 끝나게 되면 CPU1이 놀게 된다.
이런 불균형을 어떻게 극복할 수 있을까?
우리는 이 기술을 이주(migration)로 처리한다. 즉 처리할 프로세스를 다른 CPU의 실행큐로 옮기는 것이다.
간단하게 생각해보면 쉽지만 생각보다 이주는 난해하다.
왜냐하면 C가 종료되고 CPU1이 A 하나만을 CPU2가 B,D를 처리하면 CPU1가 A를 처리하다가 D를 처리할때 B가 CPU1로 이주해온다. 그리고 다시 A를 처리할때 B가 CPU2로 이주된다.
또 여기서 깊게 생각해본다.
이주 필요 여부를 어떻게 결정할까?
한 가지 기본적인 접근 방식은 작업 훔치기(work strealing)라는 기술이다.
작업 훔치기에선느 작업의 개수가 낮은 큐가 가끔 다른 큐에 훨씬 많은 수의 작업이 있는지 검사한다. 대상 큐가 소스 큐 보다 가득 차있다면 워크로드의 균형을 맞추기 위해 소스는 대상에서 하나 이상의 작업을 가져온다.
멀티 프로세서에서는 확장성이 가장 중요하기 때문에 너무 자주 검사하면 오버헤드로 확장성 문제가 생긴다. 그렇다고 너무 검사를 안하면 워크로드 불균형이 생긴다. 적절한 값을 찾아 내는게 중요하지만 마법의 영역이다.....
Linux 멀티 프로세서 스케줄러
Linux 커뮤니티에서는 멀티프로세서 스케줄러를 위한 단일화된 방식이 존재하지 않았다.
세 가지 스케줄러가 등장했는데 O(1) 스케줄러, Completely Fair Scheduler(CFS) 및 BF 스케줄러(BFS)가 그것이다.
O(1), CFS는 멀티 큐를 BFS는 단일 큐를 사용하기 때문에 두 방식 모두 실제 시스템에서 성공적으로 사용할 수 있다.
O(1) 스케줄러는 우선순위 기반 스케줄러로서 프로세스의 우선순위를 시간에 따라 변경하여 우선순위가 가장 높은 작업을 선택하여 다양한 목적을 만족시킨다.
특히 상호 작용을 가장 우선시 한다.
반면에 CFS는 결정론적(deteministic) 비례배분(proportional share) 방식이다. BFS는 셋 중에서 유일하게 유일한 단일 큐 방식이고 비례 배분 방식이다.
요약
단일 큐 방식은 구현이 용이 하고 워크로드의 균형을 맞추기 용이하지만 많은 개수의 프로세서에 대한 확장성이 낮고 캐시 친화성이 좋지 못하다. 멀티 큐 방식은 확장성이 좋고 캐시 친화성을 잘 처리하지만 워크로드 불균형 문제가 있고 구현이 복잡하다. 어떤 방식을 채택하든 쉬운 답은 없다.
1. 애초에 CPU 스케줄러는 사소한 코드 수정으로 시스템의 동작이 엄청나게 바뀌기 때문에 모든 경우에 다 잘 동작하는 범용 스케줄러를 구현하는 것은 매우 어렵다.
2. 멀티 프로세서를 캐싱하는 것의 흥미로운 점은 다중 CPU를 사용하는 것이 하나의 프로세서 사용하는 것보다 작업을 처리하는 속도가 보다 더 빠를 수 있다는 것이다.
3. 구체적으로 N개의 CPU를 사용하면 어떤 경우에는 속도가 N배 상승하기도 한다. 이를 보고 초선형스피드(super-linear-speedup)이라 한다.
'OS' 카테고리의 다른 글
| [TIL 42일차] 리눅스 디렉토리 표준 (0) | 2024.09.10 |
|---|---|
| [TIL 39일차]비례 배분 스케줄링 (1) | 2024.08.27 |
| [TIL 38일차] OS의 스케줄링 (0) | 2024.08.25 |