[42Seoul] Philosophers

 

설명에 들어가기 전 후기

사실 통과한지 약 3주가 넘었지만 이제야 후기를 쓰게 된다

식사하는 철학자 문제는 운영체제 수업에서 들었던 익숙한 문제여서 수월하게 접근할 수 있었다

구현에는 어렵지 않았지만 데이터레이스를 해결하기 위한 뮤텍스 사용, 그리고 뮤텍스를 남발할 때의 시간 밀림현상을 해결하는 것이 골치 아팠다

처음에는 각각의 변수에 뮤텍스를 하나씩 할당했지만, 그렇게 되면 시간이 밀려서 금방 죽게되기에 뮤텍스를 최대한 적게 사용하면서 데이터 레이스를 해결하도록 했다

밥 먹는 시간이나, 먹는 횟수를 잘못 설계해서 조금 바꾼 부분도 있었다  

원래 보너스는 잘 하지 않는데, 세마포어를 활용하는 이 문제의 보너스 만큼은 나중에 아우터에 가면 꼭 보너스까지 해봐야 겠다고 생각했다 

 

 

프로젝트 소개

철학자들은 둥근 테이블에 앉아있으며, 가운데에는 스파게티 그릇이 있고, 철학자의 수 대로 포크가 준비되어있음

한 명 이상의 철학자가 둥근 테이블에 앉아 먹기, 생각하기, 잠자기의 세 가지 중 한 행동을 함

철학자는 반드시 양 손에 포크를 쥐고 먹어야 함

철학자가 한 명이라도 사망하면 종료

 

해당 옵션을 인자로 가짐

• number_of_philosophers : 철학자의 수
• time_to_die : 철학자가 마지막으로 밥을 먹기 시작한 시점으로 부터 time_to_die 시간이 지나도록 밥을 먹지 않으면 사망
• time_to_eat : 밥을 먹는데 걸리는 시간
• time_to_sleep : 잠을 자는데 소모되는 시간
• number_of_times_each_philosopher_must_eat : 선택사항. 모든 철학자가 밥을 먹어야 하는 최소 횟수

 

사전 지식

스레드

스레드란?

프로세스 내에서 실행되는 흐름의 단위

 

프로세스 vs 스레드

프로세스

• 운영체제로부터 자원을 할당받는 작업의 단위
• 별도의 메모리 공간에서 실행

스레드

• 프로세스가 할당받은 자원을 이용하는 실행의 단위
• 한 프로세스 내에 여러개 생길 수 있음( = 멀티스레드 프로세스)
• 동일한 프로세스 내의 공유 메모리 공간에서 실행

 

스레드의 장단점

장점

• 스레드는 프로세스 내의 자원(코드, 데이터, 힙)을 공유하기 때문에, 자원 할당 비용이 적게 들고 문맥교환 비용도 적게 듬
• 다중 스레드일 때, 일부 스레드의 처리가 지연되어도 다른 스레드에서 작업 처리 가능
• 스레드는 공유 주소 공간(데이터, 힙)을 사용하여 데이터를 교환 가능
• 2개 이상의 CPU를 가진 컴퓨터에서 멀티스레드를 사용하면 다중 CPU가 멀티스레드를 동시에 처리해 프로세스 처리시간이 단축

 

단점

• 자원을 공유하기 때문에 동기화 문제가 발생 가능
• 하나의 스레드에서 발생한 문제가 프로세스 전반에 영향을 미칠 수 있음

 

*문맥교환(Context Switch) : 현재까지의 작업 상태나, 다음 작업에 필요한 각종 데이터를 저장하고 읽어오는 작업

*프로세스의 구조

• 코드 영역 : 프로그램 본문이 기술된 곳
• 데이터 영역 : 변수나 파일 등의 각종 데이터를 모은 곳
• 스택 영역 : 운영체제가 프로세스를 실행하기 위해 부수적으로 필요한 데이터를 모아놓은 곳
• 힙 영역 : 동적으로 할당되는 변수 영역

 

Race Condition(Data race, 경쟁 상태)

여러 프로세스들이 동시에 데이터에 접근하는 상황에서, 어떤 순서로 데이터에 접근하느냐에 따라 결과값이 달라질 수 있는 상황

이 문제를 해결하기 위해 동기화(Synchronized) 되어야 함

 

Race Condition 해결을 위한 조건

• Mutal Exclusion(상호 배제)
  • 어떤 프로세스가 임계 영역을 수행중이면, 다른 모든 프로세스들은 그 임계 영역에 들어가지 못하게 막음 
• Process(진행)
  • 임계 영역에 있는 프로세스 외에는 다른 프로세스가 임계 영역에 진입하는 것을 방해해서는 안됨
• Bounded Waiting(한정 대기)
  • 기아 상태를 방지하기 위해 프로세스가 임계 영역에 들어가려고 요청한 후 부터 다른 프로세스들이 임계 영역에 들어가는 횟수에 한계가 있어야 함

 

동기화(Process Synchronization)

여러 프로세스가 공유하는 자원의 일관성을 유지하는 것

 

뮤텍스(Mutual Exclusion)

스레드의 동시 접근을 허용하지 않음

임계영역에 들어가기 위해서는 뮤텍스를 가지고 있어야 들어갈 수 있음

임계영역에 들어간 스레드는 본인이 나올때 까지 다른 쓰레드가 들어오지 못하게 뮤텍스를 잠금

 

식사하는 철학자 문제

5명의 철학자 원탁에 앉아서 식사를 함

철학자들 사이에는 포크가 놓여있고, 다음의 동작을 하며 식사

1. 일정 시간 생각을 함
2. 왼쪽 포크가 사용 가능해질 때까지 대기. 만일 사용 가능하다면 집음
3. 오른쪽 포크가 사용 가능해질 때까지 대기. 만일 사용 가능하다면 집음
4. 양쪽의 포크를 잡으면 일정 시간만큼 식사
5. 오른쪽 포크를 내려놓음
6. 왼쪽 포크를 내려놓음
7. 1번으로 이동

 

5명이 모두 왼쪽 포크를 집는다면, 모든 철학자들이 자신의 오른쪽 포크가 사용가능해질 때까지 기다려야 함

이런 경우 교착상태(Deadlock) 상태에 걸려 무한히 대기하고, 결국 기아상태(Starvation)로 굶어죽음

 

교착상태란?

둘 이상의 프로세스가 다른 프로세가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상태

 

교착상태 발생의 4가지 조건

• 상호 배제
  • 한 번에 프로세스 하나만 해당 자원을 사용할 수 있음
  • 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 대기
• 점유와 대기
  • 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야함
• 비선점
  • 이미 할당된 자원을 강제로 뺏을 수 없음
• 환형 대기(= 순환 대기)
  • 대기 프로세스의 집합이 순환 형태로 자원을 대기

 

해결 방법

우선 철학자를 짝수 번째, 홀수 번째로 나눈 후 짝수를 잠시 대기시킨다

홀수는 왼쪽 먼저, 짝수는 오른쪽 먼저 먹게 한다

이는 교착상태에 빠지지 않게 하기 위함이다

 

밥을 다 먹고 잠을 자기 시작한 뒤 생각할 때, 생각하는 시간을 잠시 갖게 한다

철학자가 홀수일때 포크를 독점하여, 포크를 갖지 못하는 철학자가 굶어죽는 것을 막기 위함이다