[운영체제]멀티프로세서 스케줄링-2

문제점 : 동기화

메모리와 캐시의 일관성 유지에 대한 모든 일을 캐시가 담당한다면, 프로그램 또는 운영체제는 공유 데이터를 접근할 때 걱정할 필요가 있을까? 있다. CPU들이 동일한 데이터에 접근할 때, 올바른 연산 결과를 보장하기 위해 락과 같은 상호 배제를 보장하는 동기화 기법이 많이 사용된다. 락-프리 데이터 구조 등의 다른 방식은 복잡할 뿐만 아니라 특별한 경우에만 사용된다. 예를 들어 여러 CPU가 사용하는 공유 큐가 있다고 가정하자. 캐시의 일관성을 보장하는 프로토콜이 존재한다 하더라도 락이 없이는 항목의 추가나 삭제가 제대로 동작하지 않을 것이다. 데이터를 갱신하기 위해서는 락이 필요하다.

//리스트의 삭제
typedef struct __node_t{
	int value;
    struct __node_t * next;
}Node_t;

int List_Pop(){
	Node_t * temp = head;
    int value = head->value;
    free(temp);
    return value;
}

 

두 CPU의 쓰레드가 동시에 이 루틴에 접근한다고 해보자. 쓰레드1도 temp에 head값을 저장하고 반환한다. 쓰레드2도 temp에 head값을 저장하고 반환한다. 결국 같은 값을 두번 저장하고 두번 반환하는 문제가 발생한다.

해결책은 락을 사용하여 올바르게 동작하도록 하는 것이다. 루틴의 시작에 락을 걸고, 마지막에 언락을 걸면 된다. 하지만 이런 방식에 문제가 없는 것은 아니다. 성능 측면에서 문제가 있다. CPU의 개수가 증가할수록 동기화된 자료 구조에 접근하는 연산은 매우 느리게 된다.

 

문제점 : 캐시 친화성

CPU에서 실행될 때 프로세스는 해당 CPU 캐시와 TLB(변환 우선참조 버퍼)에 상당한 양의 상태 정보를 올려 놓는다. 해당 CPU 캐시에 일 부 정보가 이미 있기 때문에 해당 CPU에서 다시 실행하는 것이 속도 측면에서 유리하다. 반면 매번 다른 CPU에서 실행하면 정보를 다시 탑재해야 하니 속도가 느리다. 그래서 캐시 친화성이란 이전에 한번 실행되었던 CPU를 다시 사용하는 방법이다. 스케줄러는 캐시 친화성을 고려해 동일한 CPU에서 실행하도록 노력해야 한다.

 

단일 큐 스케줄링

단일 프로세서 스케줄링의 기본 프레임워크를 이용해 멀티프로세서 스케줄러를 개발해보자.

단일 큐 멀티프로세서 스케줄링(SQMS)의 장점은 단순함이다. CPU가 2개라면 실행할 작업 2개를 선택한다.

하지만 단점은 확장성 결여이다. 스케줄러가 다수의 CPU에서 제대로 동작하기 위해 락을  삽입한다. 락은 SQMS 코드가 단일 큐를 접근할 때 올바른 결과가 나오도록 한다. 하지만 락은 성능을 저하시킬 수 있다. 단일 락에 대한 경쟁이 증가할수록 시스템은 락에 더 많은 시간을 쓰게 된다.

두번 째 문제는 캐시 친화성에 있다. 예를 들어 5개의 작업(A,B,C,D,E)이 있고 4개의 프로세서가 있다고 가정하자.

스케줄링 큐는 다음과 같이 순서가 정해진다.

 

 

각 작업들은 타임 슬라이스만큼 작업을 실행하고 다음 작업에 CPU를 넘겨준다.

각 CPU마다 작업 스케줄은 다음과 같다.

 

 

각 CPU는 공유  큐에서 다음 작업을 선택하게 된다. 첫번째 타임 슬라이스에서 A,B,C,D가 진행 되었으니 두번째 타음 슬라이스에서 CPU0은 E를 진행하게 된다. 이렇게 작업을 각기 다른 CPU에서 진행하게 되면 캐시 친화성이 떨어진다.

이 문제의 해결을 위해 SQMS 스케줄러는 가능한 한 동일한 CPU에서 재실행될 수 있게 해야한다. 구체적으로 특정 작업들에 대해 캐시 친화성을 고려하여 스케줄링하고 다른 작업들은 오버헤드를 균등하게 여러 군데로 분산시켜 작업을 진행한다.

 

A,B,C,D 작업은 각자의 CPU에서 작업을 실행하고, E만 다른 프로세서로 이동한다. 이렇게 대부분의 작업은 캐시 친화성을 보존한다.

다음에는 E가 아닌 다른 작업을 이동시켜 형평성을 맞춘다.

이러한 기법은 구현이 복잡하고 확장성이 좋지않다.

 

멀티 큐 스케줄링(MQMS)

멀티 큐 스케줄링은 각자 CPU마다 큐를 하나 씩 두는 방식이다.

예를 들어 2개의 CPU와 A,B,C,D 네 개의 작업이 시스템에 존재한다고 가정하자. CPU는 각자 하나의 스케줄링  큐를 가지고 있으므로 운영체제는각 작업을 배치할 큐를 결정해야 한다. 

 

 

각 CPU에는 2개의 작업을 가지고 있다. RR로 스케줄링할 경우 다음과 같은 스케줄이 생성된다.

 

 

 

MQMS는 SQMS에 비해 확장성이 확실히 좋다. CPU 개수가 증가할수록 큐의 개수도 증가해 락과 캐시 경합은 더 이상 문제가 되지 않는다.

또한 MQMS는 본질적으로 캐시 친화적이다. 작업이 이미 같은 CPU 내에서 실행되기 때문이다.

하지만 멀티 큐 방식의 기본적인 문제는 워크로드의 불균형이다. 

위와 같은 상황에서 C 작업이 종료되었다고 가정해보자.

 

CPU의 사용은

 

A가 B,D 대비 2배이상 많은 점유율을 가진다. 이 후 A도 작업을 종료하게 되면

 

 

 

 

CPU0는 유휴 상태가 된다.

 

워크로드 불균형 대처법

이주(migration)만이 방법이다.

 

다시 위와 같은 상황에서 간단하게 B나 D를 다른 큐로 옮기면 된다.

하지만 

 

이럴 땐 뭐를 옮겨야 할지 모르겠다.

정답은 다음과 같이 번갈아 가면서 옮기는 방법이다.

 

 

A혼자 CPU0를 사용하다 몇번 B가 이주한다.  그러면서 A도 이주를 한다. 

근데 이주의 필요성은 어떻게 결정할까? 작업 훔치기의 방법을 알아보자. 작업 훔치기에서는 작업의 개수가 낮은 큐(Q0)가 다른 큐(Q1)에 휠씬 많은 작업이 있는지 확인한다. 균형을 맞추기 위해 개수가 적은 큐는 많은 큐에서 하나 이상의 작업을 가져온다.

너무 자주 확인을 하면 높은 오버헤드로 인해 확장성에서 문제가 발생한다. 확장성은 멀티 큐 스케줄링의 가장 중요한 목적이다.

반면 다른 큐를 자주 확인하지 않으면 심각한 워크로드 불균형을 초래한다. 적절한 값을 찾아내는 부두 상수를 알아내는건 마법에 가깝다.

 

리눅스 멀티 프로세서 스케줄러

리눅스에는 3가지 방식이 있다. O(1) 방식, CFS 및 BFS 방식.

O(1) 과 CFS는 멀티 큐, BFS는 싱글 큐를 사용한다. 큐의 개수 말고도 다른 분류 기준이 있다. 

O(1) 스케줄러는 우선순위 기반 스케줄러로 우선순위를 시간에 따라 변경하여 우선순위가 높은 작업을 선택하여 다양한 목적을 만족시킨다.

CFS는 결정론적 비례배분 방식이다. 

BFS는 단일 큐 비례배분 방식이다.