🙇🏻‍♂️

Philosophers

Created

2022/02/17 10:02

Updated

2022/03/07 05:14

Intro

옛날 언제적인가, 철학자에 관한 얘기를 들은 적이 있다.

게임으로인지 다른 방식으로인지 접했던 경험이 있는데 정확히 기억은 나지 않는다.

이 이야기로 서두를 채우는 이유는 뜬금 없이 프로젝트 과제 이름이 철학자(들)(Philosophers) 이기 때문이다.

갑자기 철학자가 프로젝트 이름으로 선정 된 이유와 이 과제 내용이 내가 어렴풋이 알고 있는 철학자 이야기와 같은지 궁금했다.

Philosophers

이 문제를 처음 제시한 사람은 에츠허르 다익스트라(Edsger Wybe Dijkstra) 이다.

우리에게 조금 익숙한 이 컴퓨터 과학자는 운영체제의 교착상태(Deadlock)를 설명하기 위해 이 문제를 만들었다.

Dining philosophers problem이라고 불리는 이 철학자 문제는 다음과 같다.

5명의 철학자가 원탁에 앉아서 식사를 한다. 철학자들 사이에는 포크가 하나씩 놓여있고, 다음 과정을 통해 식사를 한다.

→ 배치 예시

→ 식사 과정

일정 시간 생각을 한다.
왼쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
오른쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
양쪽 손 모두 포크를 집어들면 일정 시간만큼 식사를 한다.
오른쪽 포크를 내려놓는다.
왼쪽 포크를 내려놓는다.

큰 문제가 없어보이는 식사 과정이지만, 만약 모든 철학자가 동시에 자신의 왼쪽에 있는 포크를 집어들었을 때

그 후 모든 철학자는 동시에 자신의 오른쪽 포크가 사용 가능해질 때까지 무한정 대기한다.

식사 과정 중 2번까지는 진행 가능하지만 3번에서 영원히, 무한 대기가 발생한다.

이 현상을 교착 상태(Deadlock)라고 한다.

Deadlock

교착 상태(Deadlock)란 두 개 이상의 작업이 서로 상대방의 작업이 끝나기를 기다리고 있는 상태를 말한다.

결과적으로 아무 것도 완료되지 못하는 상태를 가리키는 교착 상태는 다중 프로그래밍 환경에서 흔히 발생할 수 있는 문제이다.

E. G. 코프만 교수가 제시한 교착 상태 발생의 네 가지 필요 조건

조건	설명
상호배제(Mutual exclusion)	프로세스들이 필요로 하는 자원에 대해 배타적인 통제권 요구. → 한 번에 한 프로세스만이 공유 자원 사용
점유대기(Hold and wait)	할당 된 자원을 갖고 있는 프로세스가 다른 프로세스가 사용 중인 자원을 기다림.
비선점(No preemption)	자원에 대해 프로세스가 작업을 끝낼 때까지 그 자원을 사용할 수 없다.
순환대기(Circular wait)	공유 자원을 사용하기 위해 대기하는 프로세스들이 환형으로 대기. 자신의 자원을 점유하며 앞 또는 뒤의 프로세스에 대한 자원을 요구

교착 상태의 관리 방법

1. 예방(Prevention)

상호 배제, 점유 대기, 비 선점, 순환 대기 조건 중 하나라도 미리 차단하는 방법.

→ 상호 배제 조건 제거

상호 배제 조건은 자원을 공유하지 않는 비 공유 성질을 가진다.

따라서 공유 성질을 가진 읽기 전용 파일과 같은 공유 자원을 사용하여 배타적 접근의 제거로 인해 교착 상태를 방지할 수 있다.

→ 점유 대기 조건 제거

점유 대기 조건 시 교착 상태가 발생하는 이유는 프로세스가 자원 점유 중 다른 자원을 사용하기 위해 대기하기 때문이다.

점유 대기 조건이 발생하지 않도록 하기 위해서는 프로세스 실행 전 필요한 자원을 모두 요청 및 할당하면 된다.

그 후 자원이 점유 되지 않을 때에만 다른 프로세스에서 요구할 수 있게 한다.

최대 자원 할당으로 인해 한 프로세스가 자원을 과다하게 사용할 수 있는 효율성 문제가 나타날 수 있다.

프로세스가 자원을 점유하고 있지 않을 때에만 다른 자원을 요청할 수 있기 때문에 기아 문제가 발생할 수 있다.

→ 비선점 조건 제거

비선점 조건은 자원에 대해 먼저 할당 받는 프로세스가 배타적 권리를 갖는 것을 말한다.

이 비선점 조건을 제거하기 위해서는 자원에 대한 배타적 권리를 제거하면 된다.

하지만 조건 제거 시 다른 프로세스가 자원을 요구 할 때 자원을 반납하여 작업 내용을 잃을 수 있다.

→ 환형 대기 조건 제거

자원에 고유 할당 번호(우선순위)를 부여 후 번호에 맞게 자원을 요구하게 한다. 자원 낭비 문제점이 발생할 수 있다.

2. 회피(Avoidance)

예방 시 발생하는 자원 낭비 문제, 비효율적인 문제를 해결하기 위해 나타난 방법이다.

교착 상태 발생 시 탐지 후 회피하여 해결한다. 그 후 순환 대기가 발생하지 않도록 자원 할당 상태를 검사한다.

항상 안전한 상태에서만 자원 요청을 받아들이고 할당한다.

> Safe state & Unsafe state

운영 체제는 교착 상태가 발생할 수 있는 상태를 검사하고 가능 성이 있는 경우를 Unsafe state, 가능성이 낮은 경우를 Safe state로 구분한다.

그 후 Safe state를 유지할 수 있는 요청만 수락하고 Unsafe state한 요청은 Safe state를 만족 할 때까지 거부한다.

→ Safe state

프로세스의 요청에 대해 교착 상태를 발생 시키지 않고 정상적으로 차례대로 모두에게 자원을 할당해 줄 수 있는 상태.

이 때 교착 상태를 발생 시키지 않는 자원 할당 순서를 안전 순서(Safe sequence)라고 한다.

→ Unsafe state

프로세스의 자원 할당 요청에 대해 교착 상태가 나타날 수 있는 불안전한 상태.

하지만 Unsafe state가 곧 교착 상태를 의미하지는 않는다.

은행원 알고리즘

교착 상태 회피의 특성을 잘 녹여낸 알고리즘이다.

교착 상태를 관리 하기 위해 Safe state에 있는 요청의 적절한 Safe sequence를 찾아 자원을 할당한다.

은행원 알고리즘을 사용하기 위해서는 몇 개의 필수 조건이 필요하다.

조건 1. 할당할 수 있는 자원의 수 일정 2. 사용자 수 일정 3. 최대 자원 요구량 미리 알아두어야 함 4. 일정 시간 내에 자원 사용 후 반납해야 함

예를 들어 시스템에 자원이 총 12개가 있다고 가정 했을 때 각각의 프로세스(P0, P1, P2)에 대해 최대 자원 요구량(Max), 현재 할당량(Allocation), 필요량(Need)는 다음과 같다.

여기서 필요량(Need)는 Max - Allocation 값이다.

그리고 현재 시스템에 남아 있는 자원은 12 - (5 + 2 + 2) = 3개 다.

Process	Max	Allocation	Need
P0	10	5	5
P1	4	2	2
P2	9	2	7

이 상황에서 기대할 수 있는 Safe sequence는 P1 → P0 → P2 순이다.

먼저 3개의 자원 중 2개를 P1이 사용 후 모두 반납한다.

시스템 자원 → 3(남아있던 시스템 자원) - 2(P1의 Need) + 4(P1의 모든 반납 자원) = 5개

그 후 5개를 모두 P0에 할당 후 다시 모두 반납 받는다.

시스템 자원 → 5(남아있던 시스템 자원) - 5(P0의 Need) + 10(P0의 모든 반납 자원) = 10개

마지막으로 10개 중 2개를 P2에 할당 후 모두 반납 받는다.

시스템 자원 → 10(남아있던 시스템 자원) - 7(P2의 Need) + 9(P2의 모든 반납 자원) = 12개

결과적으로 Safe sequence를 따라 자원을 모든 프로세스의 요구에 따라 할당 후 반납 받은 것을 볼 수 있다.

하지만 자원 요구량 또는 Max가 변경 되었을 경우 그에 따른 Safe sequence의 재탐색 등으로 인한 이용도가 하락하는 단점도 생겨날 수 있다.

자원 할당 그래프 알고리즘

자원 타입 당 사용 할 수 있는 인스턴스가 하나일 경우 사용할 수 있는 알고리즘.

시스템은 프로세스와 자원의 상태를 아래의 그래프와 같이 유지하며 프로세스의 요청에 대해 순환 대기 상태가 발생하지 않는 경우에만 자원을 프로세스에 할당한다.

R1(Resource)에서 P1(Process)로 뻗어나가는 화살표를 할당 화살표(Request edge)

P2(Process)에서 R1(Resource)로 뻗어나가는 화살표를 요청 화살표(Assignment edge)

각 프로세스(P1, P2)에서 R2(Resource)로 뻗어나가는 점선 화살표를 예약 화살표(Claim edge)

이라고 한다.

할당 화살표는 Resource가 Process에 할당 되었다는 개념을 의미한다.

요청 화살표는 Process가 Resource의 할당 요청을 하는 개념을 의미한다.

예약 화살표는 Process가 Resource에 언젠가는 자원 요청을 할 수도 있음을 나타낸다.

만약 P2(Process)가 R2(Resource)에 대해 자원 할당 요청을 하여도 시스템은 R2가 현재 유휴 상태임에도 불구하고 P2에 할당하지 않고 대기한다.

그 이유는 바로 R2(Resource)가 예약 화살표(Claim edge)로 연결 되어 있기 때문인데, 위에서 설명 한 바와 같이 Claim edge로 연결 되어 있으면 해당 Process는 Resource에 대해 언제든지 할당 요청을 할 수 있는 상태이기 때문이다.

예를 들어 시스템이 대기하지 않고 R2에 대한 P2의 요청을 받아들여 아래와 같은 상태가 되었다.

그 직후 P1이 R2에 대해 자원 할당 요청을 하지만 R2는 P2에 이미 할당 된 상태여서 P1은 무한정 대기를 할 수 밖에 없다. 따라서 순환 대기 상태가 발생한다.

따라서 시스템은 애초에 P2의 요청을 거부하여 교착 상태를 회피한다.

3. 탐지(Detection) & 회복(Recovery)

탐지(Detection)

교착 상태 발생 시 회복(Recovery)을 수행하기 위해서는 우선, 탐지(Detection)를 해야한다.

Sequence : Detection algorithm → Recovery algorithm

대기 그래프(Wait-for graph)

(a) : 자원 할당 그래프(Resource allocation graph) (b) : (a)에 대응하는 대기 그래프(Wait-for graph)

자원 할당 그래프의 변형으로, 각 자원 유형의 단위 자원이 하나일 경우 사용한다.

자원 할당 그래프에서 자원 노드를 제거 후 프로세스 간의 간선으로 표현한 그래프이다.

기존 (a)에서 Pi → Rq → Pj 로 표시 할 때 간선이 두 개가 필요했지만, (b)에서는 Pi → Pj로 직접 연결하며 간선이 한 개만 존재한다. Pj가 사용 중인 자원을 Pi가 대기중임을 의미.

Resource allocation graph에서와 마찬가지로 대기 그래프에서의 순환 형태는 교착 상태를 나타낸다.

따라서 이 알고리즘은 대기 그래프를 유지하고 주기적으로 순환 형태가 존재하는지를 탐색해야 한다.

Shoshani & Coffman Algorithm (Detection algorithm)

각 자원 유형의 단위 자원이 여러 개일 경우 사용한다.

은행원 알고리즘에서 볼 수 있었던 자료 구조인 Available, Allocation, Request를 사용한다.

Available : 각 형태별로 사용 가능한 자원 수를 표시하는 길이가 m인 벡터

Allocation : 현재 각 프로세스에 할당되어 있는 각 형태의 현재 할당량을 표시한 n*m 행렬. 만약 Allocation[i, j] = k 이면, 프로세스 Pi는 자원 Rj를 k개 할당 받고 있다는 의미.

Request : 각 프로세스의 현재 요청을 표시하는 n*m 행렬 만약 Request[i, j]일 때 프로세스 Pi에 필요한 개수(Need)가 k개라면 Pi는 Rj를 k개 더 요청한다.

→ 동작 순서

# Work와 Finish는 각각 길이가 m과 n인 벡터이다
# Work = Available로 초기화, Allocation[i]가 0이 아니면 Finish[i] = False 아니면 True
Work = Available
if Allocation[i] != 0:
	Finish[i] = False
else:
	Finish[i] = True

# Finish[i] == False, Request[i] <= Work[i]를 만족하는 i를 찾는다.
do find i where Finish[i] == False and Request[i] <= Work[i]

if i:
	Work[i] = Work[i] + Allocation[i]
	Finish[i] = True
	do find next i
else:
	if Finish[i] == False:
		System and Process Pi is now deadlock
Python
복사

→ 예제

Step 1 ( 초기화 )

Available = (0, 0, 0) , Work = (0, 0, 0)

Allocation 순회 중 0인 값이 없기 때문에 Finish = (False, False, False, False, False)

Step 2 ( 조건 탐색 )

P0의 Allocation[0] = (0, 1, 0)으로 할당되어 있다. 그리고 Request[0] = (0, 0, 0)으로 Request[i] ≤ Work[i]이므로 P0은 실행 할 수 있다.

Step 3 ( 실행 )

P0의 실행 후 자원 반납 시 Work = Work(0, 0, 0) + Allocation[0](0, 1, 0) 으로 Work = (0, 1, 0) 이다. 그리고 P0이 끝났기 때문에 Finish = (True, False, False, False, False) 이 된다.

Step 2 ( 조건 탐색 )

Pseudo-code에 작성한 조건을 통해 프로세스의 수행 순서를 표기하면

P0(0, 1, 0) → P2(3, 1, 3) → P3(5, 2, 4) → P1(7, 2, 4) → P4(7, 2, 6)

Finish = (True, True, True, True, True) 의 결과를 나타낸다.

그 결과 교착 상태가 아닌 것을 탐지하였다.

하지만 만약 P2가 자원 C를 1개 더 요청했을 때 위의 표는 다음과 같다.

이 경우 P0는 조건에 맞아 수행 할 수 있지만, 그 후의 프로세스는 조건에 맞지 않아 어느 프로세스도 실행 할 수 없다. 따라서 이 경우 [ P1, P2, P3, P4 ]로 구성 된 교착 상태가 나타난다.

탐지 알고리즘의 사용

교착 상태 탐지는 언제 수행해야 할까? 자주 또는 드물게?

답은 교착 상태가 발생할 것으로 예상 되는 빈도와 교착 상태를 즉시 탐지하지 않을 경우 발생 할 수 있는 결과에 따라 달라질 수 있다.

즉시 할당할 수 없는 모든 자원을 할당 후에 교착 상태 감지 시

교착 상태에 최소한의 프로세스가 관여하면서 교착 상태를 즉시 감지할 수 있는 장점이 있다. 하지만 교착 상태를 너무 자주 검사하여 발생하는 성능저하로 오버헤드가 심하다는 단점이 있다.

CPU 사용률이 40%로 감소하거나 다른 수치 이하로 감소하는 것과 같이 교착 상태가 발생 했을 때 탐지

1번보다 적게 수행 된다는 장점이 있지만, 교착 상태와 관련 된 프로세스를 탐지 할 수 없게되어 복구가 더 복잡하고 더 많은 프로세스에 손상을 줄 수 있다.

교착 상태를 주기적으로 확인하고 1시간에 한 번 또는 CPU 사용량이 낮을 때 탐지

회복(Recovery)

탐지 알고리즘 실행 시 교착 상태를 발견하면 유휴 상태의 자원 낭비를 빠르게 방지할 수 있다.

시스템이 교착 상태를 처리하는 방법은 크게 두 가지가 있다.

첫 번째는 순환 대기 상태의 교착 상태의 프로세스 / 스레드 중 하나 이상을 중지 하는 것이고,

두 번째는 교착 상태의 하나 이상의 프로세스 / 스레드의 자원을 선점 하는 것이다.

프로세스 / 스레드 중지

중지를 하는 방법은 두 가지가 있다.

→ 교착 상태의 프로세스 / 스레드를 모두 중지

교착 상태를 제거하는 확실한 방법이지만, 프로세스 또는 스레드의 실행 & 연산 시간이 오래 되었을 경우

종료 시 유실 될 수 있는 작업 내용이 많을 수 있다. 따라서 손해를 볼 수 있는 비용이 커질 수 있다.

→ 교착 상태가 해결 될 때 까지 한 프로세스 / 스레드씩 중지

프로세스를 중지 할 때마다 교착 상태 탐지 프로세스를 실행하여 교착 상태의 여부를 탐지한다.

이 경우 상당한 오버헤드를 유발할 수 있는 단점이 있다.

⛺️ 자원 선점

교착 상태를 해결하기 위해 또 다른 방법은 교착 상태에 있는 프로세스의 자원을 선점하여 다른 프로세스에 넘겨 주는 것이다. 이 때 여러 고려 사항이 존재한다.

비선점(Non-preemptive) 과 선점(Preemptive) → 비선점(Non-preemptive)

A가 이미 사용중인 자원에 대해 사용권을 빼앗지 못하고 A가 다 사용할 때까지 기다리는 방식.

우선 순위에 따라 프로세스를 처리할 때 빠른 응답을 기대할 수 있다.

하지만 많은 오버헤드가 발생할 수 있는 단점을 갖고 있다. → 선점(Preemptive)

A가 이미 사용중인 자원에 대해 A의 사용권을 빼앗고 자원을 차지할 수 있는 방식.

응답 시간을 예측할 수 있고, 일괄 처리 방식에 적합하다.

우선 순위가 높은 작업의 처리가 뒤로 밀릴 수 있다.

→ 희생자 선택(Selection of a victim)

비용 최소화를 위해 선점 순서를 결정하는 것으로 어느 자원과 어느 프로세스들이 먼저 선점 될 것인지를 결정하는 고려사항이다.

대체로 프로세스가 점유하고 있는 자원의 수 그리고 프로세스가 지금까지 실행 된 시간을 고려하여 결정한다.

→ 후퇴(Rollback)

프로세스에 대한 자원 선점 시 해당 프로세스의 처리를 결정하는 사항이다.

Rollback이란 단어에서 볼 수 있듯이 프로세스의 실행 지점을 이전으로 돌이키는 방법이다.

이전이라고 하는 시점은 교착 상태에서 탈출할 수 있는 안전한 지점을 말하는데, 가장 확실한 방법은 프로세스를 종료시킨 뒤에 재시작 하는 것이다.

→ 기아상태(Starvation)

프로세스 종료, 자원 선점 대상을 선정하는 데에는 위에서 언급한 바와 같이 선점하고 있는 자원의 수, 프로세스 실행 시간 등의 비용에 근거하여 처리한다.

이 때, 우선 순위가 뒤로 밀려 자원을 할당 받지 못하거나 항상 자원을 선점 당하는 프로세스가 발생할 수 있다.

이런 프로세스 / 스레드에 대한 기아 상태가 발생할 수 있기 때문에 프로세스에 대한 Aging 기법을 사용하여 우선 순위를 상승 시키거나 일정 시간 동안만 희생할 것을 보장 해야한다.

Aging 기아 상태를 방지하기 위해 낮은 우선 순위를 가진 프로세스의 우선 순위를 기다린만큼 높여주는 방법

4. 무시

데드락 발생 확률이 비교적 낮은 경우 별도 조치를 취하지 않는다.

Process

컴퓨터에서 연속적으로 실행되고 있는 컴퓨터 프로그램을 말한다.

메모리에 올라와 실행 되고 있는 프로그램의 인스턴스이며, 운영체제로부터 시스템 자원을 할당받는 작업의 단위이다.

Code, Data, Stack, Heap 구조인 독립된 메모리 영역을 할당 받으며 최소 1개의 스레드를 갖고 있다.

각 프로세스는 할당 받은 독립된 주소에서 실행되고, 다른 프로세스의 변수 또는 자료 구조에 접근할 수 없다.

Thread

실행 중인 프로세스 내에서 실제로 작업을 수행하는 주체 로 프로세스 내에서 실행 되는 여러 흐름이다.

프로세스가 운영체제로부터 할당 받은 시스템 자원을 활용하는 주체이다.

Code, Data, Stack, Heap의 메모리 영역을 할당 받은 프로세스에서 Stack만 따로 할당받고 Code, Heap, Data 영역은 공유한다.

한 프로세스 내의 여러 스레드들은 힙 영역을 공유하는데, 이를 읽고 쓸 수 있다.

한 스레드가 영역을 변경하면, 다른 스레드들도 그 결과를 바로 알 수 있다.

Mutex (Mutual exclusion)

쓰레드의 동기화 방법의 종류에는 Mutex , Semaphore , Monitor 로 크게 세 가지 기법이 있다.

그 중 Mutex는 상호 배제(Mutual exclusion)의 약자로 쓰레드간 동기화를 지원하고 임계 구역을 가지는 쓰레드들의 실행 시간이 서로 겹치지 않도록 해주는 기법이다.

쓰레드의 동시 접근을 허용하지 않음을 나타내며 쓰레드는 임계 영역(Critical Section)에 들어가기 위해 이 Mutex를 갖고 있어야만 한다.

세마포어와 뮤텍스의 차이는 공유 자원에 접근할 수 있는 대상의 개수 차이이다. 뮤텍스는 1개의 스레드만이 공유 자원에 접근할 수 있도록 지정한다.

뮤텍스가 사용하는 연산(개념)의 개수는 2개이며, Lock과 Unlock이다.

→ Lock

대상이 되는 임계 구역에 들어갈 권한을 얻는다. 만약 임계 구역을 다른 프로세스 또는 쓰레드가 사용중이라면 종료 할 때까지 대기한다.

→ Unlock

임계 구역 사용 종료를 알린다. 임계 구역 사용을 위해 대기 중인 다른 프로세스 또는 쓰레드가 임계구역을 사용할 수 있다.

Semaphore

세마포어(Semaphore)도 Mutex와 마찬가지로 여러 프로세스가 공유 자원에 접근하는 것을 막는 것을 말한다.

세마포어는 이 역할을 수행하기 위해 현재 공유 자원의 상태를 나타내는 카운터 변수를 사용한다. 각 프로세스는 이 변수를 확인, 변경 할 수 있다.

자원 할당을 기다리는 프로세스들은 이 상태값을 확인하여 사용 할 수 있으면 사용하고, 누군가가 공유 자원을 사용하고 있으면 반드시 일정 시간 대기 후에 사용한다.

뮤텍스와는 달리 0과 1 값의 이진수만을 가지는 것이 아닌 더 큰 값을 가질 수 있기 때문에 한 개의 자원에 한 개의 프로세스만 접근할 수 있는 것은 아니다. 세마포어는 카운터 변수의 값에 따라 이를 조정하며 접근할 수 있는 프로세스의 개수를 통제한다.

세마포어에도 뮤텍스와 마찬가지로 연산이 존재한다.

→ P 연산

프로세스의 진입 여부를 결정하는 연산으로, 임계 구역에 들어가기 전에 수행한다.

→ V 연산

자원 반납을 알리는 연산으로 임계 구역에서 나올 때 수행한다.

뮤텍스(Mutex) vs 세마포어(Semaphore)

뮤텍스는 이진 세마포어로 세마포어의 일종이다.

타입	세마포어(Semaphore)	뮤텍스(Mutex)
Basic	신호 전달 메카니즘	Locking 메카니즘
Existence	정수 형태	객체(Object) 형태
Function	한정된 리소스에 접근하는 multiple program thread를 허용	하나의 리소스에 접근하는 여러 스레드를 허용. 하지만 동시 접근은 비허용
Ownership	어느 스레드에 상관 없이 변경 되고 할당 될 수 있다.	하나의 프로세스 / 스레드만이 Lock, release 연산을 수행할 수 있다.
Categorize	Counting semaphore, binary semaphore로 구분 가능.	Categorize 할 수 없다.
Operation	Wait, Signal	Lock, Unlock
Resource Occupied	모든 리소스가 사용중이라면, 프로세스는 Semaphore count가 1이상일때까지 대기한다.	모든 자원이 사용중이라면 자원이 해제 될 때까지 대기

Function

fork

kill

memset

usleep

gettimeofday

pthread_create

pthread_detach

pthread_join

pthread_mutex_init

pthread_mutex_destroy

pthread_mutex_lock

pthread_mutex_unlock

waitpid

sem_open

sem_close

sem_post

sem_wait

sem_unlink

비교 대상

mutex_init ≈ sem_open mutex_lock ≈ sem_wait mutex_unlock ≈ sem_post mutex_destroy ≈ sem_unlink

Mandatory

철학자는 가운데 놓인 스파게티를 먹기 위해 철학자와 철학자 사이에 놓인 포크를 양 손에 들어야 한다.

→ 포크를 동시에 두 개를 집을 것인지, 하나씩 집을 것인지

철학자는 절대로 굶고 있으면 안된다.

→ 마지막으로 밥을 먹은지 time_to_die 시간이 지나거나, 프로그램 시작 후 time_to_die가 지나면 사망

모든 철학자는 먹어야 한다.

→ 적어도 한 번은 먹어야 한다.

철학자들은 서로와 대화 할 수 없다.

→ 서로의 상태를 알 수 없다

Parameter

Option	Description
number_of_philosophers	철학자와 포크 수
time_to_die	밀리 초 단위. 마지막 밥을 먹은 후 time_to_die만큼 시간 경과 프로그램 시작 후 time_to_die만큼 시간 경과 → 사망
time_to_eat	밀리 초 단위. 밥을 먹는 데 걸리는 시간. 반드시 두 개의 포크를 소유 하고 있어야 한다.
number_of_times_each_philosopher_must_eat	선택 입력. 모든 철학자가 이 값만큼 밥을 먹었다면 종료. 명시 되지 않았다면 기존 종료 조건 따름.

파싱

./philo arg1 arg2 arg3 arg4 [optional] 형태의 파라미터들은 메인의 char **argv를 통해 받아온다.

입력 형태는 숫자이지만 파라미터의 자료형을 보면 char ** 이다.

Parameter 표에 적어둔 것처럼 받아오는 인자들은 모두 숫자여야만 한다. 따라서 숫자를 제외한 문자들이 입력 되었을 때에는 모두 에러 처리 하였다.

다음은 음수에 대해서 생각을 해보았는데 철학자 수, 죽는 시간, 먹는 시간, 자는 시간, 최소한 먹는 수 는 모두

음수이면 안된다. 따라서 음수가 들어오면 에러 처리 하였다.

다음은 죽는 시간, 먹는 시간, 자는 시간은 0밀리초로 입력 받아도 되지만, 철학자 수와 선택 사항은 0이면 에러 처리 하였다.

Mutex

Mandatory 파트는 스레드(Thread)와 뮤텍스(Mutex)를 사용하여 과제를 수행한다.

동시성 프로그램의 큰 숙제인 공유 자원 관리를 해결하기 위해 뮤텍스를 사용한다.

→ 예제

#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>

int	cnt = 0;

void	*func_cnt(void *arg)
{
	char	*name = (char *)arg;
	
	printf("		|| %s enter func_cnt\n", name);
	while (cnt < 10)
	{
		printf("%s count : %d\n", name, cnt);
		cnt++;
		sleep(1);
	}
	return (NULL);
}

int	main(void)
{
	pthread_t thr1, thr2;

	pthread_create(&thr1, NULL, func_cnt, (void *)"thr1");
	pthread_create(&thr2, NULL, func_cnt, (void *)"thr2");

	printf("Create done\n");
	pthread_join(thr1, NULL);
	pthread_join(thr2, NULL);
	return (0);
}
C
복사

thr1과 thr2를 각각 쓰레드1, 쓰레드2라고 할 때 pthread_create 함수를 사용하여 쓰레드를 생성하면 지정한 func_cnt 함수가 수행 된다. func_cnt 함수는 전역 변수인 cnt를 1씩 증가시키며 해당 스레드의 문자열과 현재 cnt를 출력한다.

인터넷에 올라와있는 여러 예제들을 보아도 잘 이해가 안되어 스스로 한 번 짜보았는데, 주목 해야 할 부분이 있었다.

바로 || <process_str> enter func_cnt 구문이 출력 되는 시점이었는데, 먼저 생각 했을 때에는 쓰레드1이 생성이 먼저 되기 때문에 thr1 enter func_cnt → count 증가 → thr2 enter func_cnt 순으로 출력 될 것 같았지만, 그렇지 않고 thr1과 thr2의 진입 구문이 동시에 출력이 되었다.

쓰레드는 프로세스 내에서 실행 되는 여러 흐름이다. 각각의 흐름을 따라 함수를 수행 하는 특성으로 인해 위와 같은 결과가 나온다.

마찬가지로 Create done이 출력 되는 시점도 위와 같은 이유로 스레드의 수행 흐름, main의 흐름은 따로(동시에) 이루어진다.

위의 예제는 thr1 수행 및 완료 → thr2 수행 및 완료 혹은 thr2 수행 및 완료 → thr1 수행 및 완료 의 순서를 보장하지 않는다. thr1 또는 thr2가 cnt를 9까지 증가시키고 흐름을 다음 스레드에 넘기는 것이 아닌, 두 스레드가 모두 경쟁적으로 cnt를 증가시킨다.

본 과제에서는 cnt를 fork라고 생각 하면 쉬운데, 각 스레드는 양쪽에 놓여있는 포크의 사용 여부에 따라 기다리거나 식사가 가능하다.

위의 개념 설명 부분에서 언급한 바와 같이, 공유 자원의 선점(독점)을 보장하는 것은 뮤텍스와 세마포어가 있다. 따라서 본 예제에서 cnt의 증가를 스레드별로 완벽한 선점을 보장하기 위해서는 뮤텍스가 필요하다.

→ 뮤텍스 예제

#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>

int	cnt = 0;

pthread_mutex_t	mutex;
void	*func_cnt(void *arg)
{
	char	*name = (char *)arg;
	
	printf("		|| %s enter func_cnt\n", name);
	pthread_mutex_lock(&mutex);
	while (cnt < 10)
	{
		printf("%s count : %d\n", name, cnt);
		cnt++;
		sleep(1);
	}
	pthread_mutex_unlock(&mutex);
	return (NULL);
}

int	main(void)
{
	pthread_t thr1, thr2;

	pthread_mutex_init(&mutex, NULL);
	pthread_create(&thr1, NULL, func_cnt, (void *)"thr1");
	pthread_create(&thr2, NULL, func_cnt, (void *)"thr2");

	printf("Create done\n");
	pthread_join(thr1, NULL);
	pthread_join(thr2, NULL);
	return (0);
}
C
복사

이 예제 같은 경우는 mutex 라는 이름을 가진 뮤텍스를 통해 cnt를 증가시키는 while 부분을 선점(독점)하고 있다. 그 결과 thr1와 thr2가 동시에 func_cnt를 수행하지만 mutex를 먼저 선점한 thr1이 cnt를 증가시키는 것을 볼 수 있다.

thr1이 mutex를 unlock 시킨 후에는 thr2이 mutex를 lock 하고 cnt를 증가시키는데 공유 변수인 cnt는 이미 while의 조건에 부합하지 않기 때문에 thr2은 눈물을 머금고 mutex를 unlock 시킨다.

시간 (마이크로초 → 밀리초)

1,000 마이크로초(μs) = 1 밀리초(ms)

1,000,000 마이크로초(μs) = 1 초(s)

죽는 시간, 먹는 시간, 자는 시간은 모두 밀리초 단위로 계산 해야 한다.

usleep을 마이크로초 단위로 사용하기 때문에, usleep 안에 들어가는 파라미터의 자릿수가 길게 늘어나는 것보다 파라미터에 1,000씩 곱해주어 마이크로초로 변환하였다.

현재 시간은 gettimeofday() 함수를 사용하여 가져온다.

timeval 타입의 구조체 변수를 통해 초 단위의 시간과 마이크로 단위의 시간을 가져올 수 있다.

struct timeval
{
    long tv_sec;       // 초
    long tv_usec;      // 마이크로초
}
C
복사

timeval 타입의 구조체 내용은 다음과 같다. tv_sec은 초, tv_usec은 마이크로초로 현재 시간을 초, 마이크로초로 표현한 것이 아닌 현재 시간을 초까지 변환한 것이 tv_sec에, 나머지 마이크로초는 tv_usec에 저장된다. 따라서 현재 시간을 마이크로초까지 표현하기 위해서는 초를 마이크로초로 변환하고 마이크로초를 더해주면 된다.

현재 시간(μs) = tv_sec * 1000000 + tv_usec

식사 순서

원탁에 둘러 앉은 철학자들은 옆 철학자와 자신 사이에 하나의 포크를 두고 있다.

철학자들이 동시에 밥을 먹기 시작하거나 순서대로 먹게 된다면 교착 상태 혹은 오랫동안 밥을 먹지 못하는 기아 상태가 발생할 수 있다. 해결 방법은 여러 가지가 있겠지만, 짝수 번째에 앉아 있는 철학자들이 먼저 식사 후 홀수 번째에 앉아 있는 철학자들이 식사 할 수 있게 설계하였다.

Bonus

Mandatory 파트의 과제는 스레드(Thread)와 뮤텍스(Mutex)를 사용하여 구현하였다.

Bonus 파트의 과제는 프로세스(Process)와 세마포어(Semaphore)를 사용하여 철학자 과제를 구현해야 한다.

Bonus 파트의 문제는 Mandatory 파트에서 주어진 조건과 조금 다르다.

임계 영역에 하나의 스레드만 접근할 수 있는 방식을 사용한 Mandatory와 달리 Bonus에서 사용할 수 있는 솔루션은 세마포어이다.

추가적으로 세마포어로 표현 되는 포크는 철학자와 철학자 사이에 하나씩 놓여진 것이 아닌, 테이블 가운데에 놓여져있다. 흔히 음식점에서 식기 통에 넣어져 있다고 생각하면 이해하기 쉽다.

세마포어는 정수로 표현되며 논리적으로 쉽게 생각할 수 있게 세마포어의 값이 0이면 철학자들은 포크의 수가 1 이상이 될 때 까지 기다려야 한다.

한 가지 특이한 부분이 있었다.

Each philosopher should be a process and the main process should not be a philosopher.

철학자는 프로세스로 이루어져야 하고 메인 프로세스가 철학자면 안된다는 지시였다.

결과적으로 프로세스는 fork 함수를 통해 자식 프로세스를 생성할 수 있는데 메인 프로세스인 부모 프로세스를 통해 철학자의 행동을 수행하지 않고 자식 프로세스(pid = 0)를 통해 철학자의 행동을 구현 하였다.

자식 프로세스를 생성하는 이유는 새로운 프로그램의 실행을 위한 것이다.

새로운 분기점을 만드는 자식 프로세스 생성은 완전히 새로운 프로세스를 생성하는 것이 아닌 부모의 물리 메모리의 사본을 만들어 참조한다.

부모 프로세스는 식사가 종료 되는 조건을 탐지하고 완료 후에 자식 프로세스의 종료를 기다린다.

Mandatory 파트에서는 짝수 → 홀수 철학자 순으로 식사를 진행하게끔 하였었는데 Bonus 파트는 순서는 따로 지정하지 않았다. 왜냐하면 테이블 가운데에 포크가 있는지 없는지만 확인하면 되기 때문이다. 물론, 먼저 함수에 진입하는 프로세스가 식사를 진행하긴 한다.

세마포어도 마찬가지로 임계구역의 보호를 위한 장치이다. 따라서 Mutex에 존재하는 pthread_mutex_lock 함수와 같이 세마포어의 개수를 줄이는 함수가 존재한다. 바로 sem_wait 함수이다.

이해하는 방식은 뮤텍스와 유사하다. 어느 뮤텍스가 Lock 상태에서 접근을 하면 그 뮤텍스가 Unlock 될 때 까지 대기한다. 세마포어는 개수가 많은 뮤텍스라고 생각하면 쉽다. sem_wait를 수행하면 정수로 표현 할 수 있는 세마포어의 개수가 줄어드는데, 만약 세마포어의 현재 개수가 0이라면 세마포어가 1 이상이 될 때 까지 프로세스 / 스레드는 대기한다.

반대로 철학자가 식사를 마쳤다면 테이블 위에 포크를 돌려놓아야 한다.

사용 함수는 sem_post로 인자로 받아오는 세마포어의 개수를 하나 증가시킨다.

Author	Created	Updated
mcha(Min-jae Cha)	2022. 02. 17.	2022. 03. 07.