Concurrency and Parallelism

상호 배제 (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() 참고 및 출처

라이브락 (Livelock) 멀티스레딩 환경에서 발생할 수 있는 문제 상황으로, 프로세스나 스레드가 계속 실행 중이지만 실제로는 유용한 작업을 수행하지 못하는 상태 라이브락의 특징: 진행 중 상태: 프로세스나 스레드가 ‘실행 중’ 상태를 유지한다. 무의미한 작업: 실제로는 어떠한 유용한 작업도 수행하지 못한다. 반복적 상태 변경: 특정 조건을 만족시키기 위해 상태를 계속 변경하지만 원하는 결과를 달성하지 못한다. 라이브락과 데드락의 차이: 데드락: 프로세스들이 서로의 자원을 기다리며 완전히 멈춘 상태 라이브락: 프로세스들이 계속 실행되지만 실제로는 진전이 없는 상태 라이브락의 예시: 복도에서 마주친 두 사람: 서로 지나가려고 같은 방향으로 계속 이동하지만 결국 지나가지 못하는 상황 프로세스 간 자원 경쟁: 프로세스 A가 자원 Y를 보유하고 X를 필요로 함 프로세스 B가 자원 X를 보유하고 Y를 필요로 함 두 프로세스가 서로의 자원을 기다리며 계속 상태를 변경하지만 진전이 없음 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 import threading import time class Philosopher: def __init__(self, name, left_fork, right_fork): self.name = name self.left_fork = left_fork self.right_fork = right_fork def try_eat(self): while True: # 계속해서 시도 if self.left_fork.acquire(timeout=1): # 왼쪽 포크 잡기 시도 print(f"{self.name}이(가) 왼쪽 포크를 집었습니다") if self.right_fork.acquire(timeout=1): # 오른쪽 포크 잡기 시도 print(f"{self.name}이(가) 식사를 시작합니다") time.sleep(1) # 식사하는 시간 self.right_fork.release() self.left_fork.release() print(f"{self.name}이(가) 포크를 내려놓고 다시 시도합니다") time.sleep(0.1) # 다른 철학자에게 기회를 주기 위한 대기 else: print(f"{self.name}이(가) 포크를 얻지 못해 다시 시도합니다") time.sleep(0.1) # 재시도 전 대기 # 테스트 코드 fork1 = threading.Lock() fork2 = threading.Lock() philosopher1 = Philosopher("철학자1", fork1, fork2) philosopher2 = Philosopher("철학자2", fork2, fork1) # 두 철학자가 동시에 식사하려 시도 t1 = threading.Thread(target=philosopher1.try_eat) t2 = threading.Thread(target=philosopher2.try_eat) t1.start() t2.start() 이 코드에서 두 철학자는 모두 활발히 행동하고 있지만(포크를 집었다 놨다 하면서), 실제로 식사는 하지 못하는 라이브락 상황이 발생할 수 있다. ...

기아 상태 (Starvation) 운영 체제 및 동시성 프로그래밍에서 중요한 문제로, 특정 프로세스가 필요한 자원을 지속적으로 얻지 못해 실행되지 못하는 상황. 자원 관리 문제로, 낮은 우선순위 프로세스가 높은 우선순위 프로세스에 의해 자원이 계속 점유되어 무기한 대기하는 상황으로 주로 우선순위 기반 스케줄링에서 발생하며, 시스템 성능과 공정성에 부정적인 영향을 미친다. Source: https://www.javatpoint.com/what-is-starvation-in-operating-system 발생 조건 기아 상태가 발생하기 위한 주요 조건은 다음과 같다: 우선순위 기반 스케줄링: 높은 우선순위 프로세스가 계속 실행되면서 낮은 우선순위 프로세스가 실행되지 못함. 자원 부족: 시스템 자원이 제한적일 때 특정 프로세스가 지속적으로 자원을 얻지 못함. 비공정한 스케줄링 알고리즘: 공정성을 고려하지 않는 알고리즘이 낮은 우선순위 프로세스를 무시함. 임계 구역 점유: 특정 프로세스가 임계 구역을 오래 점유하여 다른 프로세스의 접근을 차단. 해결책 및 방지책 기아 상태를 해결하거나 방지하기 위한 방법은 다음과 같다: ...