Concurrency-and-Parallelism

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. 단순한 상호 배제 기능을 제공하며, 재진입이 불가능하다. 가장 빠른 성능을 제공하지만 우선순위 상속과 같은 고급 기능은 지원하지 않는다. ...

조건 변수 (Condition Variable) 조건 변수 (Condition Variables) 는 프로세스 동기화에서 중요한 역할을 하는 동기화 기본 요소로, 스레드가 특정 조건이 충족될 때까지 대기하도록 하는 메커니즘을 제공한다. 스레드가 특정 조건이 만족될 때까지 대기하고, 조건이 충족되면 다른 스레드가 대기 중인 스레드를 깨우는 데 사용된다. 뮤텍스와의 연관 조건 변수는 일반적으로 뮤텍스와 함께 사용된다. 뮤텍스는 조건을 원자적으로 검사하고 변경할 수 있도록 보장한다. 주요 연산 wait(): 스레드가 조건이 충족될 때까지 대기하도록 한다. signal()/notify_one(): 대기 중인 단일 스레드를 깨운다. broadcast()/notify_all(): 해당 조건 변수에서 대기 중인 모든 스레드를 깨운다. 사용 패턴 조건을 보호하는 뮤텍스를 획득한다. 조건을 테스트한다. 조건이 거짓이면 wait() 를 호출하여 대기한다. 조건이 참이면 작업을 수행하고 뮤텍스를 해제한다. 가짜 깨우기 (Spurious Wakeup) 가짜 깨우기는 조건 변수 (Condition Variable) 를 사용할 때 발생할 수 있는 현상이다. 스레드가 실제로 signal 이나 broadcast 를 받지 않았는데도 wait 상태에서 깨어나는 현상을 말한다. ...

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

상호 배제 (Mutual Exclusion) 여러 프로세스나 스레드가 공유 자원에 동시에 접근하는 것을 방지하는 동기화 메커니즘. 한 번에 하나의 프로세스나 스레드만 임계 영역(critical section)에 진입할 수 있도록 보장하는 기법이다. 필요한 이유: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 # 상호 배제가 없는 경우의 문제점 class BankAccount: def __init__(self): self.balance = 1000 def withdraw(self, amount): # 다음 세 줄의 작업이 원자적이지 않음 current_balance = self.balance # 잔액 읽기 current_balance = current_balance - amount # 계산 self.balance = current_balance # 결과 저장 # 두 스레드가 동시에 실행되면 문제가 발생할 수 있음 account = BankAccount() # 스레드 1: withdraw(500) # 스레드 2: withdraw(500) # 예상 잔액: 0, 실제 잔액: 500 (잘못된 결과) 목적 데이터 무결성 유지: 여러 프로세스가 동시에 공유 데이터를 수정하는 것을 방지한다. 경쟁 조건(Race Condition) 예방: 프로세스 실행 순서에 따른 결과 불일치를 막는다. 교착 상태(Deadlock)와 기아 상태(Starvation) 방지: 자원 할당의 효율성을 높인다. 구현 방법 잠금(Lock) 가장 기본적인 동기화 메커니즘으로, 한 번에 하나의 스레드만 임계 영역에 접근할 수 있게 한다. ...

임계 영역 (Critical Section) 운영체제에서 임계 영역(Critical Section)은 여러 프로세스 또는 스레드가 공유하는 자원에 접근하는 코드 영역을 말한다. 이는 병렬 컴퓨팅 환경에서 중요한 개념으로, 데이터의 일관성과 무결성을 보장하기 위해 사용된다. 여러 프로세스가 동시에 임계 영역에 진입하면 데이터의 일관성이 깨질 수 있다. 1 2 3 4 5 6 7 8 9 10 # 임계 영역 예시 balance = 1000 # 공유 자원 def withdraw(amount): global balance # 임계 영역 시작 temp = balance temp = temp - amount balance = temp # 임계 영역 종료 임계 영역 문제의 해결 조건 상호 배제(Mutual Exclusion): 한 프로세스가 임계 영역에 있을 때 다른 프로세스는 진입할 수 없다. 진행(Progress): 임계 영역에 있는 프로세스가 없다면, 진입하려는 프로세스가 들어갈 수 있어야 한다. 한정된 대기(Bounded Waiting): 프로세스의 임계 영역 진입은 무한정 연기되어서는 안 된다. 임계 영역 관련 문제와 해결 방법 구분 데드락(Deadlock) 경쟁 상태(Race Condition) 기아 상태(Starvation) 라이브락(Livelock) 정의 두 개 이상의 프로세스가 서로의 자원을 기다리며 영구적으로 블록된 상태 여러 프로세스가 공유 자원에 동시 접근할 때 실행 순서에 따라 결과가 달라지는 상태 특정 프로세스가 필요한 자원을 계속 할당받지 못하는 상태 프로세스들이 서로에게 응답하며 상태는 변하지만 실제 진행은 없는 상태 발생 원인 상호 배제, 점유와 대기, 비선점, 순환 대기 조건이 동시 충족 공유 자원에 대한 동시 접근, 원자성 결여 부적절한 자원 할당 정책, 우선순위 역전 현상 프로세스들의 과도한 양보, 재귀적 회피 동작 결과 시스템 전체 또는 일부 프로세스의 완전한 정지 데이터 불일치, 예측 불가능한 결과 특정 프로세스의 실행 지연 또는 무한 대기 CPU 자원 소비, 실제 작업 진행 없음 특징 프로세스들이 움직이지 않고 완전히 멈춤 타이밍에 따라 결과가 비결정적 자원 할당의 불공정성 프로세스들이 활발히 상태 변경 해결 방법 프로세스 강제 종료, 자원 선점, 데드락 발생 조건 제거 동기화 메커니즘 사용(뮤텍스, 세마포어 등) 에이징(Aging) 기법 도입, 공정한 스케줄링 무작위 대기 시간 도입, 우선순위 조정 예방 기법 자원 할당 그래프 사용, 자원 순서화, 타임아웃 설정 임계 영역 설정, 원자적 연산 사용 자원 예약 시스템, 우선순위 조정 메커니즘 타임아웃 설정, 재시도 횟수 제한 탐지 방법 자원 할당 그래프 분석, 대기 사이클 검출 데이터 일관성 검사, 로그 분석 자원 할당 통계 모니터링 CPU 사용률 분석, 진행률 모니터링 영향 범위 전체 시스템 또는 관련 프로세스 그룹 공유 자원을 사용하는 프로세스들 특정 프로세스 또는 프로세스 그룹 상호 작용하는 프로세스 그룹 복구 방법 프로세스 재시작, 시스템 재부팅 트랜잭션 롤백, 상태 복원 우선순위 재조정, 자원 재할당 프로세스 재시작 또는 동작 패턴 변경 모니터링 방법 시스템 자원 모니터링, 프로세스 상태 감시 로그 분석, 데이터 정합성 검사 자원 할당 히스토리 분석 CPU 사용률 추적, 진행 상태 모니터링 해결 방법 상호 배제(Mutual Exclusion) 구현: ...

교착상태 (Deadlock) 둘 이상의 프로세스가 서로가 가진 자원을 기다리며 무한정 대기하는 상황 Source: https://www.geeksforgeeks.org/deadlock-system-model/ 교착상태를 시뮬레이션하는 예제: 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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 import threading import time class Resource: def __init__(self, name): self.name = name self.lock = threading.Lock() def acquire(self, process_name): print(f"{process_name}가 {self.name} 획득 시도") self.lock.acquire() print(f"{process_name}가 {self.name} 획득 성공") def release(self, process_name): print(f"{process_name}가 {self.name} 반환") self.lock.release() def process_task(process_name, first_resource, second_resource): """ 교착상태를 발생시키는 프로세스 작업을 시뮬레이션합니다. 각 프로세스는 두 개의 자원을 순차적으로 획득하려 시도합니다. """ try: # 첫 번째 자원 획득 first_resource.acquire(process_name) print(f"{process_name}가 작업 중…") time.sleep(1) # 다른 프로세스가 두 번째 자원을 획득할 시간을 줌 # 두 번째 자원 획득 시도 second_resource.acquire(process_name) print(f"{process_name}가 모든 자원 획득 성공") # 작업 수행 time.sleep(1) # 자원 반환 second_resource.release(process_name) first_resource.release(process_name) except Exception as e: print(f"{process_name} 오류 발생: {e}") def main(): # 두 개의 자원 생성 resource_A = Resource("Resource A") resource_B = Resource("Resource B") # 두 개의 프로세스 생성 # Process 1은 A -> B 순서로 자원 획득 시도 # Process 2는 B -> A 순서로 자원 획득 시도 process1 = threading.Thread( target=process_task, args=("Process 1", resource_A, resource_B) ) process2 = threading.Thread( target=process_task, args=("Process 2", resource_B, resource_A) ) # 프로세스 시작 process1.start() process2.start() # 프로세스 종료 대기 process1.join() process2.join() if __name__ == "__main__": print("교착상태 시뮬레이션 시작") main() print("시뮬레이션 종료") Deadlock이 발생하기 위한 필요 조건 Deadlock이 발생하기 위해서는 다음 네 가지 조건이 모두 충족되어야 한다: ...

경쟁 상태 (Race Condition) 여러 프로세스나 스레드가 공유 자원에 동시에 접근할 때, 접근의 타이밍이나 순서에 따라 결과가 달라질 수 있는 상황. 이는 프로그램의 실행 결과가 프로세스/스레드의 실행 순서에 따라 예측할 수 없게 달라지는 현상을 초래한다. Source: https://www.rapitasystems.com/blog/race-condition-testing 발생 조건 경쟁 상태가 발생하기 위한 조건은 다음과 같다: 두 개 이상의 포인터가 동시에 같은 데이터에 접근. 최소한 하나의 포인터가 데이터를 쓰기 위해 사용됨. 데이터 접근을 동기화하는 메커니즘이 없음. 해결책 및 방지책 동기화 메커니즘 사용: 뮤텍스(mutex), 세마포어, 락(lock) 등을 사용하여 공유 자원에 대한 접근을 제어한다. 원자적 연산 사용: 분할할 수 없는 단일 연산으로 처리하여 중간 상태를 방지한다. 스레드 안전 프로그래밍: 모든 함수를 스레드 안전하게 설계한다. 락프리 알고리즘: 고급 기법으로, 특정 동시성 작업을 최적화하는 데 사용된다. 트랜잭션 격리 수준 조정: 데이터베이스에서는 직렬화 가능한 트랜잭션 격리 수준을 사용하여 경쟁 상태를 방지할 수 있다. 실제 시스템에서의 예방책 정적 분석 도구 사용: 소스 코드나 컴파일된 바이너리를 분석하여 잠재적인 경쟁 상태를 탐지한다. 로그 분석 및 모니터링: 시스템 로그를 분석하여 경쟁 상태의 징후를 감지한다. 분산 추적 시스템: 분산 시스템에서 요청과 메시지의 흐름을 추적하여 타이밍 의존성을 식별한다. 일관성 검사 도구: 분산 노드 간의 데이터 일관성을 확인하여 경쟁 상태로 인한 이상을 탐지한다. 고려사항 및 주의사항 비결정적 특성: 경쟁 상태로 인한 버그는 재현하기 어려우므로 철저한 테스트가 필요하다. 성능 영향: 동기화 메커니즘의 과도한 사용은 성능 저하를 초래할 수 있으므로 균형이 필요하다. 데드락 주의: 락을 사용할 때는 데드락 발생 가능성에 주의해야 한다. 확장성 고려: 분산 시스템에서는 경쟁 상태 관리가 시스템의 확장성에 영향을 미칠 수 있다. 모범 사례 최소한의 임계 영역: 락으로 보호되는 코드 영역을 최소화하여 성능 저하를 방지한다. 세분화된 락: 전역 락 대신 세분화된 락을 사용하여 병렬성을 높인다. 불변성 활용: 가능한 경우 불변 객체를 사용하여 동시성 문제를 원천적으로 방지한다. 스레드 안전한 라이브러리 사용: 검증된 스레드 안전 라이브러리를 활용한다. 실제 시스템에서의 해결 전략 데이터베이스 트랜잭션: 데이터베이스 시스템에서는 ACID 속성을 갖는 트랜잭션을 사용하여 경쟁 상태를 관리한다. 분산 락: 분산 시스템에서는 Zookeeper나 etcd와 같은 도구를 사용하여 분산 락을 구현한다. 버전 관리: 낙관적 동시성 제어를 위해 데이터 버전을 관리하여 충돌을 감지하고 해결한다. 이벤트 소싱: 상태 변경을 이벤트로 기록하여 일관성을 유지하고 경쟁 상태를 해결한다. 경쟁 상태를 시연하고 해결하는 예제 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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 import threading import time # 경쟁 상태가 발생하는 예제 class BankAccount: def __init__(self): self.balance = 0 # 공유 자원 def deposit(self, amount): # 현재 잔액 읽기 current = self.balance # 시간 지연을 통한 경쟁 상태 시뮬레이션 time.sleep(0.1) # 잔액 업데이트 self.balance = current + amount def get_balance(self): return self.balance # 경쟁 상태가 해결된 버전 class SafeBankAccount: def __init__(self): self.balance = 0 self.lock = threading.Lock() # 상호 배제를 위한 락 def deposit(self, amount): with self.lock: # 임계 영역 보호 current = self.balance time.sleep(0.1) self.balance = current + amount def get_balance(self): with self.lock: return self.balance # 테스트 함수 def test_race_condition(): # 경쟁 상태가 있는 계좌 account = BankAccount() # 여러 스레드가 동시에 입금 threads = [] for _ in range(10): t = threading.Thread(target=account.deposit, args=(100,)) threads.append(t) t.start() # 모든 스레드 완료 대기 for t in threads: t.join() print(f"예상 잔액: 1000, 실제 잔액: {account.get_balance()}") # 안전한 계좌로 테스트 safe_account = SafeBankAccount() # 동일한 테스트 수행 threads = [] for _ in range(10): t = threading.Thread(target=safe_account.deposit, args=(100,)) threads.append(t) t.start() for t in threads: t.join() print(f"안전한 계좌 잔액: {safe_account.get_balance()}") if __name__ == "__main__": test_race_condition() 참고 및 출처

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

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