교착 상태 탐지(Deadlock Detection) 시스템이 교착 상태 예방 혹은 방지 알고리즘을 사용하지 않는 경우 다음 2가지 알고리즘들을 반드시 지원해야 한다. 교착 상태가 발생했는지 결정하기 위해 시스템의 상태를 검사하는 알고리즘 교착 상태로부터 회복하는 알고리즘 탐지와 회복 방법은 필요한 정보를 유지하고 탐지 알고리즘을 실행 시간 비용이 든다. 또한, 교착 상태로부터 회복할 때 내재하는 가능한 손실을 포함하는 오버헤드가 필요 각 지원 유형이 한 개씩 있는 시스템 대기 그래프(wait-for graph) 해당 경우, 대기 그래프를 사용해서 교착 상태 알고리즘을 정의 대기 그래프(wait-for graph) : 자원 할당 그래프의 변형 대기 그래프를 얻는 방법 자원 할당 그래프로부터 자원 유형의 노..

교착 상태 회피(Deadlock Avoidance) 교착 상태 예방의 단점 장치의 이용률이 저하됨 시스템 총 처리율(throughput)이 감소 교착 상태 회피 원리 자원이 어떻게 요청될지에 대한 추가 정보를 제공하도록 요구하는 것 각 스레드의 요청과 방출에 대한 완전한 순서를 미리 안다면, 각 요청에 대해 스레드가 대기해야 하는지의 여부를 결정할 수 있다. → 각 요청에서 발생할 수 있는 교착 상태를 피할 수 있다. 스레드 대기 여부를 결정하기 위해, 여러 가지 정보를 고려해야 한다. 현재 가용 자원 현재 각 스레드에 할당된 자원 각 스레드가 앞으로 요청하거나 방출할 자원 교착 상태 회피 알고리즘 각 스레드가 자신이 필요로 하는 각 유형의 자원마다 최대 수를 선언하도록 요구하는 것 → 가장 단순하고 제..

교착 상태(DeadLock) 교착 상태(Dead Lock) : 대기 중인 스레드들이 다시는 그 상태를 변경할 수 없는 경우 한 스레드 집합 내의 모든 스레드가 그 집합 내의 다른 스레드에 의해 발생될 수 있는 이벤트를 기다린다면, 이는 교착 상태임 요청한 자원들이 다른 스레드에 의해 점유되어 있고, 그들도 다 대기 상태에 있기 때문 한 스레드가 자원을 요청했을 때, 그 시각에 요청한 자원을 사용할 수 없는 상황 → 해당 스레드는 대기 상태로 들어간다. 교착 상태가 없는 프로그램을 설계하는 것은 전적으로 프로그래머의 책임 시스템 모델(System model) 시스템은 경쟁 스레드들 사이에 분배되어야 할 유한한 수의 자원들로 구성됨 시스템 자원은 다수의 유형 혹은 클래스로 분할된다. 자원 유형 예시 : CP..

식사하는 철학자들(The Dining-Philosophers) 문제 규칙 가정 5명의 철학자가 원형 테이블을 공유하는 상황 테이블 중앙에는 밥이 있고, 테이블에는 5개의 젓가락이 존재 철학자가 생각(행동) 할 때, 다른 동료들과 상호작용하지 않음 밥을 먹을 때의 규칙 자신에게 가장 가까이 있는 2개의 젓가락을 집으려고 시도 옆 사람이 들고 있는 젓가락은 집을 수 없다. 가까이 있는 2개의 젓가락 → 자신과 자신의 왼쪽 철학자, 그리고 오른쪽 철학자 사이에 있는 젓가락을 뜻함 철학자는 한 번에 한 개의 젓가락만 집을 수 있음 배고픈 철학자가 동시에 젓가락 2개를 집는 경우 젓가락을 놓지 않고 식사를 한다. 식사를 마치면 2개의 젓가락 모두 내려놓고 다시 대기한다. 식사하는 철학자 문제의 의의 고전적인 동기..

고전적인 동기화 문제 많은 클래스의 병행 제어(concurrency control) 문제에 대한 것 해당 문제들로 새로운 동기화 방법을 검증할 수 있음 유한 버퍼 문제(The Bounded-Buffer Problem) 해당 문제는 동기화 프리미티브(primitive)들의 능력을 설명하기 위해 사용 프리미티브 : 프로그래밍 관점에서 해석 이용 가능한 가장 작은 processing의 단위 언어에서 표현의 원자 요소 예 : 덧셈, 뺄셈 → 가장 단순하기 때문에 primitive operation라고 함 소비자와 생산자가 공유하는 자료구조 int n; // n개의 버퍼로 구성된 풀(pool) semaphore mutex = 1; // 상호배제 기능 제공 semaphore emtpy = n; // 비어 있는 버퍼..

동기화 도구들은 임계 구역 문제인 상호 배제를 보장하고 라이브니스 문제를 해결하는데 효과적 락 없는(lock-free) 알고리즘 락 없는 알고리즘의 구현 락 없는 알고리즘을 구현하는 이유? → 락 오버헤드 없이 경쟁 조건으로부터 보호하기 위해 락 없는 알고리즘을 구현하기 위해 CAS 명령을 사용하는데 중점을 둠 CAS → compare and swap의 약어 장점 : 락 없는 설루션은 오버헤드가 낮고 확장성이 있기 때문에 인기가 있음 단점 : 알고리즘 자체가 개발 및 테스트가 어려운 경우가 많음 CAS 기반 접근 방식 CAS 기반 접근 방식이 낙관적으로 접근하는 과정 우선 낙관적으로 변수를 갱신 충돌 감지를 사용하여 다른 스레드가 변수를 병행하게 갱신 중인지 확인 갱신 중이라면, 충돌 없이 성공적으로 갱..

라이브니스(Liveness) 임계구역 접근을 위해 동기화 도구를 사용할 때 문제 임계구역에 들어가려고 시도하는 프로세스가 무기한 대기할 가능성이 생김 무기한 대기는 진행 및 한정된 대기 2개의 기준을 위반한다. 라이브니스와 라이브니스 실패 프로세스가 실행 수명주기 동안 진행되는 것을 보장하기 위해 시스템이 충족해야 하는 일련의 속성 무기한 대기하는 프로세스는 라이브니스 실패의 한 예시 다양한 형태의 라이브니스 실패 → 결과적으로 성능과 응답성이 나쁜 것이 특징 예시 무한 루프 바쁜 대기 루프 → 라이브니스 실패의 가능성이 있음 특히 프로세스가 임의로 오래 시간 동안 루프 돌고 있는 경우 가능성 높아짐 도구를 통해 상호 배제를 제공하려는 노력이 병행 프로그래밍 환경에선 실패 가능성 존재 도구를 통한 상호 ..

모니터를 사용하는 이유 세마포 또는 mutex 락을 이용하여 임계구역 문제를 해결할 때 문제점 → 프로그래머가 세마포를 잘못 사용할 시, 다양한 유형의 오류가 쉽게 발생할 수 있음 이러한 오류 처리를 위해 모니터 사용 전략 : 간단한 동기화 도구를 통합하여 고급 언어 구조물로 제공하는 것 → 모니터 모니터는 근본적인 고급 언어 구조물 중 하나 Java, C# 등의 많은 프로그래밍 언어들이 모니터의 개념을 편입시킴 모니터 사용법(Usage) ADT와 모니터 ADT(추상화된 데이터 형) : 데이터와 해당 데이터를 조작하는 함수들의 집합을 하나의 단위로 묶어 보호 이때 함수의 구현은 ADT의 특정한 구현과는 독립적 모니터 형 : 모니터 내부에 프로그래머가 정의한 일련의 연산자 집합을 포함하는 ADT 이때 모니..