Mutual Exclusion

Syncronization Algorithms 동기화 알고리즘은 병행 시스템에서 **상호 배제(Mutual Exclusion)**를 보장하기 위한 핵심 메커니즘이다. 데커 알고리즘 (Dekker’s Algorithm) 목적: 2개 프로세스의 상호 배제 메커니즘: flag 배열(진입 의사) + turn 변수(진입 순서) 교착 상태 방지를 위한 플래그 재설정과 턴 변경 예시: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class DekkerLock: def __init__(self): # 각 프로세스의 진입 시도를 나타내는 플래그 self.flag = [False, False] # 현재 임계 영역을 사용할 차례인 프로세스 번호 self.turn = 0 def lock(self, process_id): other = 1 - process_id # 다른 프로세스의 ID # 진입 시도 표시 self.flag[process_id] = True # 다른 프로세스가 진입 시도 중이면 대기 while self.flag[other]: if self.turn != process_id: # 자신의 차례가 아니면 진입 시도 포기 self.flag[process_id] = False # 자신의 차례가 될 때까지 대기 while self.turn != process_id: pass # 다시 진입 시도 self.flag[process_id] = True def unlock(self, process_id): # 차례를 다른 프로세스에게 넘김 self.turn = 1 - process_id # 진입 시도 표시 해제 self.flag[process_id] = False 피터슨 알고리즘 (Peterson’s Algorithm) 목적: 2개 프로세스의 간단한 상호 배제 메커니즘: ...

Mutex Mutex(Mutual Exclusion) 는 공유 자원에 대한 접근을 동기화하는 객체. 한 번에 하나의 스레드만이 Mutex 를 소유할 수 있으며, 소유권 개념이 있어 Mutex 를 획득한 스레드만이 이를 해제할 수 있다. Source: https://www.geeksforgeeks.org/std-mutex-in-cpp/ 주요 특징 두 가지 상태 (잠김/열림) 를 가집니다. 한 번에 하나의 스레드만 소유할 수 있습니다. 소유한 스레드만이 잠금을 해제할 수 있습니다. Mutex 의 종류 일반 Mutex (Normal Mutex) 가장 기본적인 형태의 Mutex. 단순한 상호 배제 기능을 제공하며, 재진입이 불가능하다. 가장 빠른 성능을 제공하지만 우선순위 상속과 같은 고급 기능은 지원하지 않는다. ...

원자적 연산 (Atomic Operation) 원자적 연산(Atomic Operation)은 멀티스레딩 환경에서 데이터의 일관성과 안전성을 보장하기 위한 중요한 개념으로, 상호 배제(Mutual Exclusion)를 구현하는 데 중요한 역할을 한다. 원자적 연산이란, 더 이상 쪼개질 수 없는 최소 단위의 연산을 의미하는데 중단되거나 간섭받지 않고 완전히 실행되는 연산을 말한다. 이는 마치 물리학에서 원자가 더 이상 쪼개질 수 없는 가장 작은 단위인 것처럼, 컴퓨터 과학에서도 더 이상 분할할 수 없는 가장 작은 실행 단위를 의미한다. 주요 특징 불가분성: 원자적 연산은 중간에 중단되거나 다른 프로세스에 의해 간섭받지 않는다. 일관성: 연산이 성공적으로 완료되거나 아예 실행되지 않는다. 가시성: 다른 스레드에서 원자적 연산의 결과를 즉시 확인할 수 있다. 원자적 연산의 중요성 데이터 무결성 보장: 여러 스레드가 동시에 같은 데이터에 접근할 때 발생할 수 있는 경쟁 조건(Race Condition)을 방지한다. 동기화 구현: 원자적 연산은 복잡한 동기화 메커니즘의 기본 구성 요소이다. 성능 향상: 락(Lock)과 같은 고수준의 동기화 메커니즘보다 더 가볍고 빠르다. 원자적 연산의 예시 읽기-수정-쓰기(Read-Modify-Write) 연산: ...

Monitor 프로세스 동기화에서 **모니터(Monitor)**는 공유 자원에 대한 안전한 접근을 보장하기 위한 상위 수준의 동기화 도구이다. 모니터는 공유 데이터와 해당 데이터를 조작하는 연산을 하나의 모듈로 캡슐화하여, 다중 스레드 환경에서의 경쟁 조건(Race Condition)을 방지한다. 모니터는 고수준의 동기화 추상화로, 복잡한 뮤텍스/세마포어 관리 없이 안전한 병행 프로그래밍을 가능하게 한다. 현대 언어에서는 모니터 패턴이 내장되어 있어(synchronized, lock), 데드락과 경쟁 조건을 효과적으로 방지한다. 다만 저수준 시스템 프로그래밍에서는 뮤텍스나 세마포어가 더 유연할 수 있다. 정의 모니터는 **뮤텍스(Mutex)**와 **조건 변수(Condition Variable)**를 결합한 추상화된 동기화 메커니즘이다. ...

Semaphore 멀티스레딩 환경에서 공유 자원에 대한 접근을 제어하는 동기화 도구. 세마포어는 네덜란드의 컴퓨터 과학자 Edsger Dijkstra 가 1965 년에 소개한 개념으로, 여러 프로세스나 스레드가 공유 자원에 동시에 접근하는 것을 제어하는 변수 또는 추상 데이터 타입. 세마포어는 간단한 정수 값을 사용하여 자원의 가용성을 나타낸다. 주요 특징 동기화 메커니즘: 세마포어는 여러 프로세스나 스레드 간의 실행 순서와 타이밍을 제어한다. 자원 관리: 한정된 수의 자원 (예: 프린터, 데이터베이스 연결) 에 대한 접근을 제어한다. 원자적 연산: 세마포어 조작은 중단되지 않는 단일 연산으로 수행된다. 대기 큐: 자원을 기다리는 프로세스들을 대기 큐에 저장한다. 세마포어의 종류 이진 세마포어 (Binary Semaphore): ...

데커 알고리즘 (Dekker’s Algorithm) 데커 알고리즘(Dekker’s Algorithm)은 두 프로세스 간 **상호 배제(Mutual Exclusion)**를 보장하기 위해 1965년 네덜란드의 수학자 Theodorus Dekker가 개발한 최초의 소프트웨어 상호 배제(mutual exclusion) 알고리즘이다. 이 알고리즘은 두 개의 프로세스가 공유 자원에 동시에 접근하는 것을 방지하여 경쟁 상태(race condition)를 해결하는 방법을 제시한다. 공유 자원에 대한 안전한 접근을 위해 **플래그(flag)**와 턴(turn) 변수를 활용하며, 하드웨어적 명령어 없이 소프트웨어만으로 구현 가능하다. 데커 알고리즘은 상호 배제 문제 해결의 역사적 중요성을 가지지만, 현대 시스템에서는 **세마포어(Semaphore)**나 **뮤텍스(Mutex)**와 같은 더 효율적인 동기화 기법이 주로 사용된다. ...

램포트의 빵집 알고리즘 (Lamport’s Bakery Algorithm) 램포트의 빵집 알고리즘(Lamport’s Bakery Algorithm)은 N개 프로세스의 상호 배제(Mutual Exclusion) 문제를 해결하기 위한 소프트웨어 기반 알고리즘이다. 1974년 레슬리 램포트(Leslie Lamport)가 제안했으며, 빵집에서 번호표를 받아 순서대로 서비스받는 방식에서 아이디어를 얻었다. 램포트의 빵집 알고리즘은 병행 프로그래밍의 이론적 토대를 제공했지만, 현대 시스템에서는 주로 하드웨어 지원 동기화 기법이 사용된다. 단, 분산 시스템이나 임베디드 환경에서는 여전히 연구 및 적용 사례가 존재한다. 핵심 원리 번호표 시스템 각 프로세스는 임계 영역 진입 전 고유한 번호표를 받는다. 번호표는 단조 증가(monotonically increasing) 방식으로 발급되며, 동시 접근 시 프로세스 ID로 우선순위 결정한다. 단조 증가(monotonically increasing)란 함수나 수열이 항상 증가하거나 일정한 값을 유지하는 성질을 의미한다. 즉, 감소하는 구간 없이 유지되거나 증가하는 경우를 말한다. ...

피터슨 알고리즘 (Peterson’s Algorithm) 피터슨 알고리즘(Peterson’s Algorithm)은 두 프로세스의 **상호 배제(Mutual Exclusion)**를 보장하기 위한 소프트웨어 기반 동기화 알고리즘이다. 1981년 개리 피터슨(Gary L. Peterson)이 제안한 이 알고리즘은 간결성과 이론적 엄밀성으로 운영체제 및 병행 프로그래밍 분야에서 널리 연구된다. 피터슨 알고리즘은 이론적 완결성을 인정받지만, 현대 시스템에서는 주로 하드웨어 기반 동기화 기법(예: TAS, CAS)이 사용됩니다. 그러나 병행 프로그래밍의 근본 원리를 이해하는 데 여전히 핵심적인 역할을 한다. 핵심 구성 요소 플래그 배열(flag) 각 프로세스의 임계 영역 진입 의사 표시 (flag, flag 초기값 False) 턴 변수(turn) 임계 영역 진입 순서 결정 (0 또는 1 값을 가짐) 동작 원리 진입 의사 표시: 프로세스 i가 임계 영역 진입 전 flag[i] = True 설정. ...