동기화 (컴퓨터 과학)

3. 요구사항

스레드 동기화는 여러 프로세스 또는 스레드가 임계 구역을 동시에 실행하지 않도록 보장하는 메커니즘이다.^[1] 임계 구역 접근은 동기화 기술을 사용하여 제어된다. 한 스레드가 임계 구역을 실행하기 시작하면 다른 스레드는 첫 번째 스레드가 종료될 때까지 기다려야 한다.

동기화는 다음 사항을 고려해야 한다.

• 포크 및 조인: 작업이 여러 하위 작업으로 분할되어 처리된 후 다시 합쳐지는 과정에서 모든 병렬 프로세스가 서로 대기해야 하므로 동기화가 필요하다.
• 생산자-소비자: 소비자 프로세스는 생산자 프로세스가 데이터를 생성할 때까지 대기해야 한다.
• 자원 배타적 사용: 여러 프로세스가 동시에 자원에 접근해야 하는 경우, 한 번에 하나의 프로세스만 접근하도록 보장해야 한다.

• 교착 상태: 여러 프로세스가 서로 자원을 기다리며 무한정 대기하는 상태.
• 기아 상태: 프로세스가 임계 구역에 진입하기 위해 무기한 대기하는 상태.
• 우선 순위 역전: 우선 순위가 높은 프로세스가 낮은 프로세스에 의해 중단되는 현상.

4. 동기화의 최소화

엑사스케일 컴퓨팅 알고리즘 설계에서 중요한 과제 중 하나는 동기화를 최소화하거나 줄이는 것이다. 특히 분산 컴퓨팅 환경에서 동기화는 계산보다 더 많은 시간을 소요할 수 있다.^[2] 컴퓨터 과학자들은 수십 년 동안 동기화 감소에 주목해 왔으며, 계산 능력 향상과 대기 시간 사이의 격차가 커짐에 따라 최근 이 문제는 더욱 중요해지고 있다. 분산 컴퓨터에서 동기화로 인한 (전역) 통신이 희소 반복 솔버의 지배적인 부분을 차지한다는 실험 결과도 있다.^[2] 이러한 문제는 상위 500대 슈퍼컴퓨터를 순위 매기기 위한 새로운 벤치마크 지표인 고성능 공액 기울기(HPCG)의 등장으로 더욱 주목받고 있다.^[3]

5. 고전적인 문제

동기화와 관련된 고전적인 문제들은 다음과 같다.

• 생산자-소비자 문제(제한된 버퍼 문제라고도 함)
• 읽기-쓰기 문제
• 철학자들의 식사 문제

6. 구현 방법

스핀락은 동기화를 구현하는 효과적인 방법 중 하나이다. 공유 리소스나 코드 조각에 접근하기 전에 각 프로세서는 플래그를 확인한다. 플래그가 재설정되어 있으면 프로세서는 플래그를 설정하고 스레드 실행을 계속한다. 그러나 플래그가 설정(잠금)되어 있다면, 스레드는 루프 안에서 계속 회전하면서 플래그가 설정되었는지 여부를 확인한다. 스핀락은 플래그가 낮은 사이클 동안 재설정되는 경우에만 효과적이며, 그렇지 않으면 많은 프로세서 사이클을 낭비하여 성능 문제를 일으킬 수 있다.^[12]

배리어는 구현이 간단하고 응답성이 좋다. 배리어는 동기화를 위해 대기 사이클을 구현하는 개념을 기반으로 한다. 예를 들어 배리어 1에서 시작하여 동시에 실행되는 세 개의 스레드가 있다고 가정해 보자. 시간 t 이후, 스레드 1은 배리어 2에 도달하지만, 올바른 데이터가 없기 때문에 스레드 2와 3이 배리어 2에 도달할 때까지 기다려야 한다. 모든 스레드가 배리어 2에 도달하면 모두 다시 시작한다. 시간 t 이후, 스레드 1은 배리어 3에 도달하지만, 스레드 2와 3의 올바른 데이터를 다시 기다려야 한다.

이처럼 여러 스레드의 배리어 동기화에서는 항상 다른 스레드를 기다리는 몇 개의 스레드가 발생한다. 이는 프로세스 성능을 심각하게 저하시킨다.^[13]

i번째 스레드의 배리어 동기화 대기 함수는 다음과 같이 나타낼 수 있다.

(Wbarrier)i = f((Tbarrier)i, (Rthread)i)

여기서 Wbarrier는 스레드의 대기 시간, Tbarrier는 도달한 스레드의 수, Rthread는 스레드의 도착률이다.^[14]

실험에 따르면 총 실행 시간의 34%가 다른 느린 스레드를 기다리는 데 소요된다.^[13]

세마포어는 하나 이상의 스레드/프로세서가 특정 구역에 접근하도록 허용하는 신호 메커니즘이다. 세마포어는 특정 고정 값을 갖는 플래그를 가지며, 스레드가 해당 구역에 접근하려 할 때마다 플래그 값을 감소시킨다. 마찬가지로, 스레드가 해당 구역을 벗어날 때 플래그는 증가한다. 플래그가 0이면 스레드는 해당 구역에 접근할 수 없으며, 대기하도록 선택하면 차단된다.

일부 세마포어는 코드 구역에 하나의 스레드 또는 프로세스만 허용한다. 이러한 세마포어를 이진 세마포어라고 하며, 뮤텍스와 매우 유사하다. 세마포어 값이 1이면 스레드 접근이 허용되고, 0이면 접근이 거부된다.^[15]

멀티태스킹이나 멀티스레딩 환경에서 동시에 병렬로 동작하는 프로세스나 스레드 간의 시계열적인 제어를 하는 것을 동기화라고 한다. 주로 임계 구역의 상호 배타적 처리를 보증하는 수단으로 다음과 같은 것들이 있다.

• 세마포어
• 뮤텍스(락)
• 이벤트, 모니터
• 비블로킹 동기화(Lock-free와 Wait-free 알고리즘)

7. 하드웨어 지원

많은 시스템은 임계 구역 코드에 대한 하드웨어 지원을 제공한다.^[7]

단일 프로세서 또는 단일 프로세서 시스템은 현재 실행 중인 코드를 선점 없이 실행하여 인터럽트를 비활성화할 수 있는데, 이는 다중 프로세서 시스템에서는 매우 비효율적이다.^[7] 다중 프로세서에서 동기화를 구현하는 데 필요한 핵심 기능은 메모리 위치를 원자적으로 읽고 수정할 수 있는 일련의 하드웨어 기본 요소이다. 이러한 기능이 없으면 기본적인 동기화 기본 요소를 구축하는 데 드는 비용이 너무 높아지고 프로세서 수가 증가함에 따라 증가할 것이다. 기본적인 하드웨어 기본 요소에는 원자적으로 위치를 읽고 수정하는 기능과 읽기 및 쓰기가 원자적으로 수행되었는지 알 수 있는 몇 가지 방법이 제공되는 여러 가지 대체 공식이 있다. 이러한 하드웨어 기본 요소는 잠금 및 배리어와 같은 광범위한 사용자 수준 동기화 작업을 구축하는 데 사용되는 기본 구성 요소이다. 일반적으로 아키텍트는 사용자가 기본적인 하드웨어 기본 요소를 사용할 것으로 기대하지 않고 대신 시스템 프로그래머가 기본 요소를 사용하여 동기화 라이브러리를 구축할 것으로 예상하며, 이 프로세스는 종종 복잡하고 까다롭다.^[8] 많은 최신 하드웨어는 이러한 원자적 명령어를 제공하며, 두 가지 일반적인 예로는 단일 메모리 워드에서 작동하는 test-and-set과 두 개의 메모리 워드의 내용을 교환하는 compare-and-swap이 있다.

컴퓨터의 하드웨어는 일반적으로 클럭 동기 설계에 의해 전체가 동기하여 동작한다. 또한 결함 허용 시스템에서는 복수의 CPU로 동일한 처리를 동시에 (즉, 동기하여) 실행한다 (중복화). 멀티프로세서 시스템의 캐시 메모리는 MESI 프로토콜 등의 캐시 일관성 프로토콜을 사용하여 내용을 동기시켜 일관성을 유지한다.

8. 프로그래밍 언어 지원

자바에서 스레드 간섭 및 메모리 일관성 오류를 방지하는 한 가지 방법은 메서드 시그니처 앞에 `synchronized` 키워드를 붙이는 것이다. 이 경우 선언 객체의 잠금을 사용하여 동기화를 적용한다. 두 번째 방법은 코드 블록을 `synchronized(someObject){...}` 섹션으로 묶는 것으로, 더 세밀한 제어가 가능하다. 이렇게 하면 스레드가 포함된 블록을 실행하기 전에 `someObject`의 잠금을 획득해야 한다. 잠금은 잠금을 획득한 스레드가 이 블록을 벗어나거나 블록 내에서 대기 상태가 될 때 자동으로 해제된다. 스레드가 동기화된 블록에서 수행한 모든 변수 업데이트는 다른 스레드가 마찬가지로 잠금을 획득하고 블록을 실행할 때 다른 스레드에 표시된다. 두 가지 구현 모두 모든 자바 객체에는 인스턴스화 시 연결된 ''내부 잠금'' 또는 ''모니터 잠금''이 있으므로 잠금을 제공하는 데 모든 객체를 사용할 수 있다.^[9]

자바 `synchronized` 블록은 상호 배제 및 메모리 일관성을 활성화하는 것 외에도 신호—즉, 잠금을 획득하고 코드 블록을 실행 중인 스레드에서 블록 내에서 잠금을 기다리는 스레드로 이벤트를 보낼 수 있게 한다. 따라서 자바 `synchronized` 섹션은 뮤텍스와 이벤트의 기능을 결합하여 동기화를 보장한다. 이러한 구조를 동기화 모니터라고 한다.

.NET 프레임워크 역시 동기화 기본 요소를 사용한다.^[10] .NET의 동기화는 협력적으로 설계되었으며, 일관된 결과를 얻기 위해 보호된 리소스에 액세스하기 전에 모든 스레드가 동기화 메커니즘을 따라야 한다. 잠금, 신호, 경량 동기화 유형, 스핀웨이트 및 상호 잠금 작업은 .NET의 동기화와 관련된 메커니즘이다.^[11]

많은 프로그래밍 언어에서 동기화를 지원하며, 엄격하게 결정적인 동기화가 가장 중요한 임베디드 소프트웨어 개발을 위해 전체 특수 언어가 작성되었다.

멀티태스킹이나 멀티스레딩에서, 동시 병렬로 동작하는 프로세스나 스레드 사이에서 시계열적인 제어를 하는 것을 동기화라고 한다. 주로 임계 구역의 상호 배타적 처리를 보증하는 수단으로 다음과 같은 것들이 있다.

• 세마포어
• 뮤텍스(락)
• 이벤트, 모니터
• 비블로킹 동기화(Lock-free와 Wait-free 알고리즘)

9. 분산 트랜잭션

이벤트 기반 아키텍처에서 동기 트랜잭션은 요청-응답 패러다임을 사용하여 구현할 수 있으며, 두 가지 방식으로 구현할 수 있다.^[16]

• 요청과 응답을 위한 두 개의 별도 메시지 큐를 생성한다. 이벤트 생산자는 응답을 받을 때까지 대기해야 한다.
• 각 요청에 대해 전용의 임시 메시지 큐를 하나 생성한다.

10. 수학적 기초

동기화 기본 요소에 대한 추상적인 수학적 기초는 히스토리 모노이드에 의해 제공된다. 또한 히스토리 모노이드 위에 구축할 수 있는 프로세스 계산 및 페트리넷과 같은 많은 상위 수준의 이론적 장치가 있다.

11. 운영체제별 동기화 예시

다양한 운영체제에서 제공하는 동기화 메커니즘은 다음과 같다.

• 세마포어
• 뮤텍스(락)
• 이벤트, 모니터
• 비블로킹 동기화 (Lock-free와 Wait-free 알고리즘)

11. 1. 윈도우

• 인터럽트 마스크는 단일 프로세서 시스템에서 전역 리소스(임계 구역)에 대한 접근을 보호한다.
• 스핀락은 다중 프로세서 시스템에서 스핀락 스레드가 선점되는 것을 방지한다.
• 동적 디스패처는 상호 배제 락, 세마포어, 이벤트, 타이머와 같이 작동한다.

11. 2. 리눅스

• 세마포어
• 스핀락
• 배리어
• 뮤텍스
• 읽기-쓰기 잠금 - 매우 자주 접근하지만 자주 변경되지 않는 긴 코드 섹션용
• 읽기 복사 갱신(RCU)^[18]

11. 3. 솔라리스

• 세마포어
• 조건 변수
• 적응형 뮤텍스 – 조건에 따라 다르게 구현되는 이진 세마포어^[19]
• 읽기-쓰기 잠금
• 턴스타일 – 획득된 잠금을 대기 중인 스레드의 큐^[20]

11. 4. Pthreads

• 뮤텍스
• 조건 변수
• 리더-라이터 락
• 스핀락
• 배리어

12. 컴퓨터 네트워크에서의 동기화

컴퓨터 네트워크의 통신 프로토콜에는 동기 신호 등 다양한 동기 방식을 채택한 것이 있다. 예를 들어, HDLC는 프레임 동기형이다.

네트워크상의 컴퓨터 간에 시각 동기화를 시키는 프로토콜로 NTP나 SNTP가 있다. 더 나아가 다른 용법으로, 복수의 네트워크 기기 간에 콘텐츠 내용을 동일하게 유지하는 것을 "동기화"라고 한다(아이튠즈, 개인 정보 관리자, 파일 동기화 등 참조).

참조

_[1] 간행물 More than you ever wanted to know about synchronization: Synchrobench, measuring the impact of the synchronization on concurrent algorithms http://sydney.edu.au[...] ACM
_[2] 논문 Minimizing synchronizations in sparse iterative solvers for distributed supercomputers
_[3] 웹사이트 HPCG Benchmark http://hpcg-benchmar[...]
_[4] 서적 Operating System Concepts
_[5] 서적 Computer Organization and Design MIPS Edition: The Hardware/Software Interface (The Morgan Kaufmann Series in Computer Architecture and Design) Morgan Kaufmann
_[6] 서적 Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers Pearson
_[7] 서적 Operating System Concepts John Wiley & Sons. 2008-07-11
_[8] 서적 Computer Architecture: A Quantitative Approach Morgan Kaufmann 2011-09-30
_[9] 웹사이트 Intrinsic Locks and Synchronization https://docs.oracle.[...] Oracle 2023-11-10
_[10] 웹사이트 Overview of synchronization primitives https://learn.micros[...] Microsoft 2023-11-10
_[11] 웹사이트 Synchronization https://www.techoped[...] 2023-11-10
_[12] 서적 Embedded Software Development with ECos Pearson Education Inc
_[13] 논문 A speculative mechanism for barrier sychronization 2014
_[14] 서적 2012 International Conference on Informatics, Electronics & Vision (ICIEV)
_[15] 서적 Real-Time Concepts for Embedded Systems CMP Books
_[16] 서적 Fundamentals of Software Architecture: An Engineering Approach O'Reilly Media
_[17] 서적 Operating System Concepts John Wiley & Sons. 2012-12-07
_[18] 웹사이트 What is RCU, Fundamentally? [LWN.net] https://lwn.net/Arti[...]
_[19] 웹사이트 Adaptive Lock Probes https://docs.oracle.[...]
_[20] 웹사이트 Turnstiles and priority inheritance - SunWorld - August 1999 http://sunsite.uakom[...]