데커 알고리즘 (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 설정. ...
라이브락 (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 발생 조건 기아 상태가 발생하기 위한 주요 조건은 다음과 같다: 우선순위 기반 스케줄링: 높은 우선순위 프로세스가 계속 실행되면서 낮은 우선순위 프로세스가 실행되지 못함. 자원 부족: 시스템 자원이 제한적일 때 특정 프로세스가 지속적으로 자원을 얻지 못함. 비공정한 스케줄링 알고리즘: 공정성을 고려하지 않는 알고리즘이 낮은 우선순위 프로세스를 무시함. 임계 구역 점유: 특정 프로세스가 임계 구역을 오래 점유하여 다른 프로세스의 접근을 차단. 해결책 및 방지책 기아 상태를 해결하거나 방지하기 위한 방법은 다음과 같다: ...