[Algorithm] 철학자들의 만찬 - 다익스트라 제안 알고리즘

다익스트라 제안 알고리즘 - 개 념

다익스트라를 비롯한 개념없는 철학자들의 한정된 포크를 공유하는 기아상태 유발의 식사 행태

 

I. 다익스트라가 제안한 기아상태가 가능한 철학자의 식사

 

가. 철학자의 식사의 개요

• 다익스트라를 비롯한 개념없는 철학자들의 한정된 포크를 공유하는 기아상태 유발의 식사 행태

 

나. 철학자 식사의 테이블 구성도

 

철학자 식사의 테이블 구성도

 

II. 철학자 식사의 문제와 해결 구조

 

가. 철학자의 식사의 기본조건

 

구분	설명	실환경
환경	원탁에서 둥글게 앉아서 사이에 포크를 공유 한다.	공유자원 선형조건
행위	철학자는 먹거나 사색한다.	대기와 실행
행위조건	반드시 2개의 포크로 식사를한다. 다른 상대의 포크는 뺏을수 없다. 왼쪽 포크를 항상 먼저집는다. 하나를 가지면 하나를 기다린다. 아무도 식사에 간섭하지 않는다. 식사를 마치면 포크를 내려놓는다.	취득후 실행 상호배제 점유대기 비선점

 

나. 식사 상황의 문제점

• 한번에 2명만 식사를 할수 있다.
• 누가 어떤 포크를 가졌는지 신경쓰지 않고 자기 생각만 한다.
• 5명 모두 기아상태가 발생할 가능성이 있다.

반응형

 

다. 해결방안

 

구분	설명	실환경
예방	철학자를 4명만 앉힌다. 포크를 5개 더 놓는다. 포크 하나로만 먹게 만든다.	4가지 상태의 부정
회피	포크에 인식표를 붙인다. 양쪽다 포크가 있을때만 동시에 집는다. 홀수번째 철학자는 왼쪽을 짝수번째 철학자는 오른쪽 포크를 먼저 집는다.	세마포어 뱅커스
발견	모두 왼쪽 포크를 들고 있는건 아닌지 주위를 살펴본다. 1분이상 기다리면 혹시? 하고 들었던 포크 내려놓는다.	자원할당그래프
복구	가장오래 기다렸던 철학자가 오른쪽에 앉은 철학자 포크를 뺏는다.	자원선점

 

라. 철학자 식사의 기아상태 고려사항

• 포크에 인식표 등을 활용하여 교착상태는 회피 할수 있지만 기아상태가 해결되는 것은 아니다.
• 다른 네명이 먹는동안 한번도 못먹는 철학자는 굶어죽는다.

 

III. 해결 방법을 구현한 알고리즘

 

가. 철학자의 식사 문제의 교착상태 예방 세마포어 알고리즘

해결 방법을 구현한 알고리즘

 

나. 다익스트라가 제안한 해결책

• 각각의 철학자를 라고 하고
• 각 철학자의 왼쪽 포크를 라고 하자.
• P5를 제외한 네 명은 먼저 Fn를 집은 후 를 집는 방식
• P5는 이와 반대로, F1를 먼저 집은 후 를 집는다.
• 이것은 원래 방식의 대칭성을 제거하고, 따라서 교착 상태를 막을 수 있다.

 

다. 유사한 문제들 (생산자 소비자) (독자 저자의 문제)

• 유한한 개수의 물건(데이터)을 임시로 보관하는 보관함(버퍼)에 여러 명의 생산자들과 소비자들이 접근한다.
• 생산자는 물건이 하나 만들어지면 그 공간에 저장한다.
• 이때 저장할 공간이 없는 문제가 발생할 수 있다.
• 소비자는 물건이 필요할 때 보관함에서 물건을 하나 가져온다.
• 이 때는 소비할 물건이 없는 문제가 발생할 수 있다.
• 독자 저자도 같은개념임

 

[용어/개념] 보안 시스템/솔루션 및 클라우드/인공지능/개발 보안 용어 정리

[용어/개념] 보안 시스템/솔루션 및 클라우드/인공지능/개발 보안 용어 정리

 

[AWS] Network - CloudFront

[AWS] Network - CloudFront