반응형
다익스트라 제안 알고리즘 - 개 념
다익스트라를 비롯한 개념없는 철학자들의 한정된 포크를 공유하는 기아상태 유발의 식사 행태
I. 다익스트라가 제안한 기아상태가 가능한 철학자의 식사
가. 철학자의 식사의 개요
- 다익스트라를 비롯한 개념없는 철학자들의 한정된 포크를 공유하는 기아상태 유발의 식사 행태
나. 철학자 식사의 테이블 구성도
II. 철학자 식사의 문제와 해결 구조
가. 철학자의 식사의 기본조건
구분 | 설명 | 실환경 |
환경 | 원탁에서 둥글게 앉아서 사이에 포크를 공유 한다. | 공유자원 선형조건 |
행위 | 철학자는 먹거나 사색한다. | 대기와 실행 |
행위조건 | 반드시 2개의 포크로 식사를한다. 다른 상대의 포크는 뺏을수 없다. 왼쪽 포크를 항상 먼저집는다. 하나를 가지면 하나를 기다린다. 아무도 식사에 간섭하지 않는다. 식사를 마치면 포크를 내려놓는다. |
취득후 실행 상호배제 점유대기 비선점 |
나. 식사 상황의 문제점
- 한번에 2명만 식사를 할수 있다.
- 누가 어떤 포크를 가졌는지 신경쓰지 않고 자기 생각만 한다.
- 5명 모두 기아상태가 발생할 가능성이 있다.
반응형
다. 해결방안
구분 | 설명 | 실환경 |
예방 | 철학자를 4명만 앉힌다. 포크를 5개 더 놓는다. 포크 하나로만 먹게 만든다. |
4가지 상태의 부정 |
회피 | 포크에 인식표를 붙인다. 양쪽다 포크가 있을때만 동시에 집는다. 홀수번째 철학자는 왼쪽을 짝수번째 철학자는 오른쪽 포크를 먼저 집는다. |
세마포어 뱅커스 |
발견 | 모두 왼쪽 포크를 들고 있는건 아닌지 주위를 살펴본다. 1분이상 기다리면 혹시? 하고 들었던 포크 내려놓는다. |
자원할당그래프 |
복구 | 가장오래 기다렸던 철학자가 오른쪽에 앉은 철학자 포크를 뺏는다. | 자원선점 |
라. 철학자 식사의 기아상태 고려사항
- 포크에 인식표 등을 활용하여 교착상태는 회피 할수 있지만 기아상태가 해결되는 것은 아니다.
- 다른 네명이 먹는동안 한번도 못먹는 철학자는 굶어죽는다.
III. 해결 방법을 구현한 알고리즘
가. 철학자의 식사 문제의 교착상태 예방 세마포어 알고리즘
나. 다익스트라가 제안한 해결책
- 각각의 철학자를 라고 하고
- 각 철학자의 왼쪽 포크를 라고 하자.
- P5를 제외한 네 명은 먼저 Fn를 집은 후 를 집는 방식
- P5는 이와 반대로, F1를 먼저 집은 후 를 집는다.
- 이것은 원래 방식의 대칭성을 제거하고, 따라서 교착 상태를 막을 수 있다.
다. 유사한 문제들 (생산자 소비자) (독자 저자의 문제)
- 유한한 개수의 물건(데이터)을 임시로 보관하는 보관함(버퍼)에 여러 명의 생산자들과 소비자들이 접근한다.
- 생산자는 물건이 하나 만들어지면 그 공간에 저장한다.
- 이때 저장할 공간이 없는 문제가 발생할 수 있다.
- 소비자는 물건이 필요할 때 보관함에서 물건을 하나 가져온다.
- 이 때는 소비할 물건이 없는 문제가 발생할 수 있다.
- 독자 저자도 같은개념임
[용어/개념] 보안 시스템/솔루션 및 클라우드/인공지능/개발 보안 용어 정리
반응형