reference. 캄란 아미니 - 전문가를 위한 C
[멀티프로세서 유닛]
- 컴퓨터 시스템에 코어가 하나뿐인 CPU 처럼 프로세서 유닛이 하나만 있을 때, 메인 메모리의 특정 주소에 접근하려는 작업들은 주소가 CPU 코어에 캐시되어 있더라도 언제나 최신 값을 읽는다.
(단일 코어에선 하나의 프로세서만 존재하므로 모든 프로세스나 스레드가 같은 캐시를 사용하기 때문에 매번 갱신되는 캐시의 내용을 읽음으로써 캐시의 일관성이 유지된다.
즉, 멀티 코어 환경에서 한 코어의 데이터를 수정했지만, 다른 코어는 오래된 데이터를 참조하여 잘못된 연산을 수행하는 데이터 불일치 문제나 프로그램 실행 결과가 프로세서의 스케줄링이나 실행 순서에 따라 달라질 수 있어, 예측하기 어려운 결과를 초래하는 결과의 비일관성 문제가 발생하지 않는다는 뜻이다)
일반적으로 CPU 코어 내부에 있는 특정 메모리 주솟값은 지역 캐시(local cache)에 저장하며 해당 주소에 대한 변경 사항도 캐시 내에 유지한다. 이 방식은 메인 메모리에서 읽기 및 쓰기 작업의 횟수를 줄여서 성능을 향상한다. 특정 이벤트에서 CPU 코어는 캐시와 메인 메모리가 동기화되도록 지역 캐시에 있는 변경 사항을 다시 메인 메모리로 전파한다.
캐시 메모리 간단 설명 -> 캐시 메모리 (tistory.com)
이러한 지역 캐시들은 프로세서 유닛이 두 개 이상일 때도 존재하는데 바로 두 개 이상의 코어가 있는 CPU (멀티코어) 나 코어의 수와 상관없이 CPU 가 여러 개인 것(멀티 프로세스)을 의미한다. 참고로 모든 CPU 코어는 고유한 지역 캐시를 가진다.
그러므로 두 작업이 서로 다른 두 CPU 코어에서 실행되고 메인 메모리의 같은 주소에서 작업을 할 때, 각 CPU 코어는 자신의 지역 캐시에 같은 메모리 주소값을 저장한다. 만약 한 작업이 공유된 메모리 주소에 쓰기 작업을 할 때는 지역 캐시에만 변경 사항이 적용되며, 메인 메모리나 다른 CPU 코어의 지역 캐시에는 적용되지 않는다는 의미다
(각각의 캐시가 같은 메인 메모리의 주소값을 저장하더라도, 별개의 객체이기 메인 메모리 자체를 바꾸지 않는 이상 한 쪽의 캐시 메모리의 내용이 바뀌어도 다른 쪽의 캐시 메모리는 영향이 없다는 것이다)
이는 반대로 말하면 다른 CPU 코어에서 실행 죽인 작업들이 공유된 메모리 주소에서 최신 값을 읽으려 할 때, 이 작업들은 최신 값을 갖지 않은 자신의 지역 캐시에서 읽기 떄문에 최신 값을 알 수 없다
(위에서 언급한 데이터 불일치 문제가 발생한다)
위처럼 지역 캐시로 인해 생기는 문제는 CPU 코어 간 메모리 일관성 프로토콜(memory coherence protocol) 을 도입해 해결한다. 일관성 프로토콜을 따르면 다른 CPU 코어에서 실행 중인 모든 작업은 CPU 코어 중 하나가 값을 변경할 때 자신들의 지역 캐시에서 같은 값을 볼 수 있다. 메모리 일관성 프로토콜을 따르면 다른 프로세서 유닛에서 실행 중인 모든 작업에 메모리 가시성(memory visibility) 이 도입된다. 캐시 일관성과 메모리 가시성은 두 개 이상의 프로세서 유닛에서 실행되는 동시 시스템에서 고려해야 할 중요한 요인들이다.
------------------------------------------------------------------------[ 여담 ]------------------------------------------------------------------------
위에서 '메모리 일관성 프로토콜' 이라고 설명이 되어있지만 조금 더 세밀하게 보자면 '메모리 일관성 모델(memory consistency model)' 과 '캐시 일관성 프로토콜(cache coherence protocol)' 을 통칭해서 설명했다고 볼 수 있다.
메모리 일관성 모델 - 멀티프로세서 시스템에서 메모리 연산(읽기 및 쓰기)이 어떻게 수행되어야 하는지에 대한 이론적인 규칙과 원칙을 정의한다. 이 모델은 프로세서들 사이에서 메모리 접근 순서를 어떻게 보장할지, 특히 메모리 연산의 가시성과 순서를 어떻게 처리할지 결정한다. 대표적인 메모리 일관성 모델로는 순차적 일관성(Sequential Consistency), 릴랙스 일관성(Relaxed Consistency), 강력 일관성(Strong Consistency) 등이 있다.
메모리 연산의 가시성(memory operation visibility) : 한 프로세서(또는 코어)에서 수행된 메모리 연산(읽기 및 쓰기)이 다른 프로세서에 언제 어떻게 "보여지는"(감지될 수 있는)지를 정의
캐시 일관성 프로토콜 - 메모리 일관성 모델을 실제 하드웨어 시스템에서 구현하는 방법이다. 이 프로토콜은 특히 멀티코어 프로세서에서 각 코어의 로컬 캐시 간에 발생할 수 있는 데이터 불일치를 해결하기 위해 설계되었고, MESI, MOESI와 같은 프로토콜은 캐시 라인의 상태를 관리하여 모든 캐시가 최신의 데이터를 유지하도록 보장한다.
MESI : Modified, Exclusive, Shared, Invalid
MOESI : Modified, Owner, Exclusive, Shared, Invalid
---------------------------------------------------------------------------------------------------------------------------------------------------------
다음 잠자기/알림 메커니즘을 적용시키고, <A를먼저 출력한 다음 B를 출력> 의 제약 조건을 가진 의사 코드를 통해 설명을 이어가고자 한다.
동시 시스템
{
공유 상태
{
완료 : 불리언 = 거짓
}
작업 P
{
1.1. 'A'를 출력
1.2. 완료 = 참
1.3. 작업 Q에 알림
}
작업 Q
{
2.1. 완료가 아닌 동안
{
2.2. 완료가 거짓이라면 잠자기 모드에 돌입 //원자적
}
2.3. 'B'를 출력
}
}
작업 P와 작업 Q가 다른 PCU 코어에서 실행 중이라고 할 때, 각 CPU 코어는 자신의 지역 캐시에 공유 변수 '완료' 에 대한 진입점(entry point)이 있다.
작업 P가 명령어 1.2 를 실행하고서 잠자고 있을 작업 Q에 알리는 인터리빙이 예로 들때 작업 P는 지역 캐시에 있는 '완료' 값을 업데이트 하지만, 메인 메모리에 다시 쓰거나 다른 CPU 코어에 있는 지역 캐시를 업데이트 한다는 의미는 아니다.
또한 메인 메모리와 작업 Q의 지역 캐시에서 변화를 확인할 수 있다는 보장이 없기 때문에 작업 Q가 CPU를 확보해 지역 캐시를 읽을 때, '완료' 는 거짓 값을 가지며 작업 Q가 잠자기 모드로 들어간 상태에서 작업 P는 완료 되어 알림 신호를 보내고 끝남으로써 해당 신호가 작업 Q의 캐시에 도달하지 않기 때문에 작업 Q는 영원히 잠들어 반교착 상태가 발생한다.
이 문제를 해결하려면 메모리 장벽을 사용해야 한다. 메모리 장벽은 실행(전달) 시 방벽과 같은 역할을 하는 명령어로, 하나의 지역 캐시에 있는 모든 값은 메모리 및 다른 지역 캐시로 전파된다. 이들은 다른 CPU코어에서 실행 중인 모든 작업이 볼 수 있다. 즉, 메모리 장벽은 CPU 코어의 지역 캐시와 메인 메모리를 동기화한다.
메모리 장벽을 정용시킨 의사 코드를 확인해보자
동시 시스템
{
공유 상태
{
완료 : 불리언 = 거짓
}
작업 P
{
1.1. 'A'를 출력
1.2. 완료 = 참
1.3. 메모리 장벽
1.4. 작업 Q에 알림
}
작업 Q
{
2.1. 수행
{
2.2. 메모리 장벽
2.3. 완료가 거짓이라면 잠자기 모드에 돌입 //원자적
}
2.4. 완료가 거짓이 아닌동안
2.5. 'B'를 출력
}
}
이렇게 메모리 장벽을 도입해 공유 변수 '완료' 의 모든 업데이트를 작업 Q에서 볼 수 있다.
참고로 작업 생성 및 세마포어데 대한 잠금과 해제는
'메모리 장벽으로서의 역할, 모든 CPU 코어의 지역 캐시와 메엔 메모리를 동기화, 최근 변경 사항을 공유 상태로 전파'
같은 세 가지 작업에 해당한다.
이번에 뮤텍스를 사용해서 잠자기 모드로 들어가고, 잠금 해제가 거짓인 명령어를 원자적으로 정의하여 구상해보고자 한다.
뮤텍스는 오직 하나의 작업만 임계 구역에 있도록 하며, 세마포어와 비슷하게 잠금과 해제는 메모리 장벽으로 작용할 수 있다.
동시 시스템
{
공유 상태
{
완료 : 불리언 = 거짓
M : 뮤텍스
}
작업 P
{
1.1. 'A'를 출력
1.2. 잠금: Lock(M)
1.3. 완료 = 참
1.4. 잠금 해제: Unlock(M)
1.5. 작업 Q에 알림
}
작업 Q
{
2.1. 잠금: Lock(M)
2.2. 완료가 아닌 동안
{
2.3. 잠자기 모드로 들어가고 잠금 해제: Unlock(M) //원자적
2.4. 잠금: Lock(M)
}
2.5. 잠금 해제: Unlock(M)
2.6. 'B'를 출력
}
}
명령어 Lock(M) 과 Unlock(M) 은 모든 작업에 메모리 가시성을 보장하는 메모리 장벽으로 작용한다. 참고로 Lock(M) 과 Unlock(M) 각 작업에서 임계 구역으로 간주된다.
작업이 뮤텍스(또는 세마포어) 로 잠글 때, 뮤텍스가 자동으로 해제되는 경우가 있기 때문에 주의하여야 한다.
- 작업이 Unlock 명령어를 사용하면 뮤텍스가 해제된다.
- 작업이 완료되면 모든 잠긴 뮤텍스가 해제된다.
- 작업이 잠자기 모드가 되면 잠겼던 뮤텍스가 해제된다.
(마지막 항목은 일반적으로 참이 아니다. 만약 뮤텍스가 보호하는 임계 구역에서 작업이 특정 시간만큼 잠들고자 한다면, 뮤텍스를 해제하지 않고도 잠들 수 있다. 그래서 명령어 2.3 을 원자적으로 정의했으며, 여기에 Unlock(M)을 더한 것이다. 이 시나리오를 완전히 이해하려면 조건 변수를 살펴봐야 한다)
따라서 명령어 2.3 이 원자 명령어로 실행되면 잠겨 있던 뮤텍스 M이 해제된다. 작업이 다시 알림을 받으면 명령어 2.4를 이용해 다시 잠기고, 그 뒤에 다시 임계 구역으로 들어갈 수 있다.
작업이 뮤텍스을 잠궜을 때, 작업이 다시 뮤텍스를 잠글 수는 없으며 여기서 잠그려고 하면 대개 교착상태가 된다. 재귀적인 뮤텍스(recursive mutex) 만 작업 하나로 여러 번 잠글 수 있다. 참고로 몇 번 잠겼든지 간에 재귀적 뮤텍스가 잠금 상태일 때 다른 모든 작업이 이를 잠그려고 한다면 차단된다. 잠금과 해제 작업은 언제나 쌍으로 존재하며, 따라서 작업이 재귀적 뮤텍스를 두 번 잠근다면 해제도 두 번 해야된다.
[스핀락(spinlock)]
- 위의 의사코드에 뮤텍스와 바쁜 대기를 사용해 스핀란 알고리즘이 탑재된 뮤텍스를 사용하는 해결 방법을 살펴보자. 뮤텍스는 메모리 장벽 역할을 하며, 따라서 메모리 가시성 문제는 없고, '완료' 공유 플래그에 대해 작업 P와 Q를 효과적으로 동기화 한다.
동시 시스템
{
공유 상태
{
완료 : 불리언 = 거짓
M : 뮤텍스
}
작업 P
{
1.1. 'A'를 출력
1.2. 스핀락: SpinLock(M)
1.3. 완료 = 참
1.4. 스핀락 해제: SpinUnlock(M)
}
작업 Q
{
2.1. 스핀락: SpinLock(M)
2.2. 완료가 아닌 동안
{
2.3. 스핀락 해제: SpinUnlock(M)
2.4. 스핀락: SpinLock(M)
}
2.5. 스핀락 해제: SpinUnlock(M)
2.6. 'B'를 출력
}
}
이 의사코드는 POSIX 스레딩 API 를 사용해 유효한 C 코드로 작성할 수 있는 첫 번째 해결 방법이다. 이전의 의사코드는 모두 실제 프로그램으로는 작성할 수 없다. 구현하기에는 너무 추상적이거나, 멀티프로세서 유닛 시스템에서 실행하는 특정한 경우에 문제가 되기 때문이다. 하지만 이 의사코드는 동시성을 지원하는 모든 프로그래밍 언어에 이식될 수 있다.
이 코드에서는 스핀락을 사용하는데, 스핀락은 바쁜 대기 알고리즘이다. 스핀락 뮤텍스를 잠글 때마다 뮤텍스를 사용할 수 있을 때까지 바쁜 대기 루프에 들어가고 나서 그 다음을 계속 진행한다.
이 의사코드의 내용은 명령어 2.3 과 2.4 를 제외하면 따라 구현하기 쉽다. 루프 안의 이 명령어들은 이상한 연속적인 잠금 및 해제 명령어이다. 작업 Q가 CPU 코어를 가지는 동안, 스핀락 뮤텍스 M을 잠그고 해제 하는 일이 연속해서 진행 중이다.
명령어 2.3 과 2.4 가 없다면 명령어 2.1 에서 잠금은 명령어 2.5 가 될 때까지 뮤텍스가 잠긴 상태가 되도록 한다. 이는 작업 P가 공유 플래그 완료에 접근할 기회를 찾지 못한다는 의미이다. 이러한 잠금과 해제 명령어는 작업 P가 접근 기회를 찾고 명령어 1.2 를 통해 플래그 '완료'를 업데이트하도록 한다. 그렇지 않으면 뮤텍스는 계속 작업 Q가 갖게 되며, 그러한 작업 P는 명령어 1.2로 진행할 수 없어 반교착 상태가 된다.
(위의 의사 코드에서 Q작업이 한 번만 루프를 돌리고, 하필 이 때 루프 내의 두 가지 명령어가 교환일 일으킨다면 어떻게 될까? 즉, 작업 Q가 실행되고 spinlock 처리 후 루프 실행을 했는데 문맥 교환으로 인해 다시 spinlock 을 시도하고, 이후 spinunlock 을 시도한 후 루프를 탈출할 때 한 번 더 spinunlock 을 하게되는 인터리빙에서의 문제점이 없을까란 생각을 해볼 수도 있을껀데 이렇게 spinlock 을 연달아 시도하거나 spinunlock 을 연달아 시도하게 되면 이미 처리된 spinlock/spinunlock 에 대한 재호출 명령어는 무시되게 된다. 명령어 자체가 버려진다는 것이다. 이런 방식을 통해 연달아 호출시에도 데드락에 빠지지 않게 되는 것이다)
참고로 이벤트 발생 비율에 비교해 작업을 잠자기 모드로 두는 것이 매우 비싼 고성능 시스템에서는 스핀락이 아주 일반적인 방식이다. 스핀락을 사용할 때 작업은 가능한 한 빨리 뮤텍스를 해제할 수 있는 방식으로 작성해야 한다. 그러려면 임계 구역은 매우 작아야 한다. 코드에서 볼 수 있듯 임계 구역에 불리언 검사 (루프 조건)는 하나만 있다.
[조건 변수]
- 프로그래밍으로는 작업을 잠자기 모드로 만들거나 다른 작업에 알리는 방법을 모르기 때문에 작업을 대기키기고 그에 따라 알림을 받는 데 도움이 되는 새로운 개념인 조건 변수(condition variable)를 알아보고자 한다.
조건 변수는 쉽게 말해 변수(또는 객체)이며, 작업을 잠자기 모드로 만들거나 다른 잠든 작업에 알리고 깨울 수 있다. 참고로 여기서 설명하는 잠자기 모드란 지연을 발생시켜서 몇 초 또는 몇 밀리초 동안 잠자는 것과는 다르다. 이는 특히 작업이 더 이상 CPU 공유를 받지 않는다는 의미이다. 임계 구역을 보호하기 위해 사용된 뮤텍스와 마찬가지로, 조건 변수는 서로 다른 작업 간에 신호 전달을 하는 데 사용된다.
잠금과 해제 작업과 관련한 뮤텍스처럼 조건 변수는 잠자기 및 알림 작업이 있다. 하지만 모든 프로그래밍 언어에는 고유한 용어가 있으니 잠자기/알림 대신 대기(wait)/신호(signal) 라고 칭하기도 한다.
조건 변수는 반드시 뮤텍스와 함계 사용해야 한다. 뮤텍스 없이 조건 변수만을 사용한 해결 방법에는 상호 배제(mutual exclusion) 속성이 없다. 조건 변수가 도움이 되려면 여러 작업에서 공유되어야 하며, 이 공유 자원에 대해 동기화된 접근이 필요하니 유의해야 한다. 이는 임계 구역을 보호하는 뮤텍스로 충족시킬 수 있다.
다음 의사코드는 일반적으로 특정 조건 또는 이벤트를 기다리는 조건 변수 및 뮤텍스를 사용하는 방법이다.
동시 시스템
{
공유 상태
{
완료 : 불리언 = 거짓
CV : 조건 변수
M : 뮤텍스
}
작업 P
{
1.1. 'A'를 출력
1.2. 스핀락: Lock(M)
1.3. 완료 = 참
1.4. 알리기: Notify(CV)
1.5. 잠금 해제: Unlock(M)
}
작업 Q
{
2.1. 잠금: Lock(M)
2.2. 완료가 아닌 동안
{
2.3. 잠자기: Sleep(M, CV)
}
2.4. 잠금 해제: Unlock(M)
2.5. 'B'를 출력
}
}
이 해결 방법은 동시 시스템애서 두 명령어 간 엄격한 순서를 구현하기 위해 조건 변수를 사용한 방식이다.
명령어 1.4 와 명령어 2.3 은 조건 변수 CV 를 상요한다. 작업 Sleep 은 뮤텍스 M 과 조건 변수 CV 에 대해 둘 다 알아야 한다. 작업 Q가 잠들 때는 잠금을 해제해야 하고, 작업 Q가 알림을 받았을 때는 잠금을 획득해야 하기 때문이다.
작업 Q가 알림을 받으면 Sleep 작업 내부에 있는 로직을 계속해서 M을 다시 잠근다는 점을 참고해야한다. 명령어 1.4 또한 M에 대한 잠금을 획득했을 때만 작동하며, 잠금을 획득하지 않았다면 경쟁 상태가 발생한다. 가능한 인터리빙에 대해 살펴보고, 앞의 뮤텍스와 조건 변수가 항상 명령어 1.1 과 2.5 사이에 원하는 순서를 지키도록 하는 법을 알아보면 좋다.
뮤텍스 객체와 조건 변수를 일반적으로 모니터링 객체(monitor object) 라고 한다. 또한 동시성과 관련된 설계 패턴도 모니터 객체라고 하는데, 어떤 동시 작업에서 명령어의 순서를 다시 정하기 위해 위의 기술을 사용하는 것과 관련된다.
