philosophers(1) - 스레드, 동기화, 임계 영역, 교착상태

이전 포스트인 pipex에선 프로세스와 프로세스 간 통신인 IPC에 대해 배웠습니다.
이번 philosophers 프로젝트는 스레드와 스레드 동기화 방법, 그리고 운영체제의 교착상태에 대해 설명하겠습니다.

📌 스레드

• 프로세스 내에서 실행되는 여러 흐름의 단위로 하나의 프로세스는 여러 개의 스레드로 구성이 가능합니다.

• 하나의 프로세스를 구성하는 스레드들은 프로세스에 할당된 메모리, 자원 등을 공유합니다.

• 각 스레드 별로 자신만의 스택과 레지스터를 가집니다.

• 프로세스와 같이 실행, 준비, 대기 등의 실행 상태를 가지며, 실행 상태가 변할 때마다 스레드 문맥 교환(context switching)을 수행합니다.

스레드 장점

1. 문맥 교환 (context switching) 시간이 짧음

2. 메모리 공유로 인하여 시스템 자원 소모 줄어듦

3. 응답시간 단축

스레드마다 스택을 독립 할당하는 이유

1. 각각의 스레드는 위 그림과 같이 각자의 스택과 PC 레지스터 값을 가짐

2. 스택 메모리 공간이 독립적 => 독립적인 함수 호출이 가능하고, 독립적인 실행 흐름이 가능

프로세스와 스레드의 차이

프로세스 : 운영체제로부터 자원을 할당받는 작업의 단위

스레드 : 프로세스가 할당받은 자원을 이용하는 실행의 단위

프로세스는 실행 중인 프로그램으로
디스크로부터 메모리에 적재되어 CPU의 할당을 받을 수 있는 것을 말합니다.
하지만 프로세스 생성은 많은 시간과 자원을 소비합니다.

스레드는 프로세스의 실행 단위라고 할 수 있습니다.
한 프로세스 내에서 동작되는 여러 실행 흐름으로
프로세스 내의 주소 공간이나 자원을 공유할 수 있습니다.
이 경우 각각의 스레드는 독립적인 작업을 수행해야 하기 때문에 각자의 스택과 PC 레지스터 값을 갖고 있습니다.

📌 스레드 동기화 방법의 종류

Mutex / Semaphore / Monitor
공통점은 세가지 모두 운영체제의 동기화 기법입니다.
동시성 프로그래밍의 가장 큰 숙제는 공유자원 관리라고 생각합니다.
공유자원을 안전하게 관리하기 위해서는 상호배제(Mutual exclusion)를 달성하는 기법이 필요합니다.

뮤텍스와 세마포어는 공유자원 관리를 위해 고안된 기법으로 서로 다른 방식으로 상호배제를 달성합니다.

뮤텍스(Mutual Exclusion)

스레드의 동시 접근을 허용하지 않는다는 의미.
뮤텍스의 스레드 동기화 방법은 임계 영역에 들어가기 위해 이 뮤텍스를 가지고 있어야 들어갈 수 있습니다. 즉, 일종의 자물쇠와 같은 역할을 합니다.
임계 영역에 들어간 스레드가 뮤텍스를 이용해 임계 영역에서 본인이 나올 때까지 다른 스레드가 못 들어오게 내부에서 자물쇠로 닫습니다.

세마포어(Semaphore)

세마포어 역시 뮤텍스와 비슷한 역할을 합니다.
그러나, 세마포어는 동시 접근 동기화가 아닌 접근 순서 동기화에 더 관련 있습니다.

모니터(Monitor)

Mutex(Lock)와 Condition Variables(Queue라고도 함)을 가지고 있는 Synchronization 메카니즘입니다.

📌 동기화 방법간 차이점

우선 뮤텍스 / 모니터 / 세마포어는 개념적으로 차이가 있습니다.

뮤텍스와 모니터는 상호 배제를 함으로써 임계 영역에 하나의 스레드만 들어갈 수 있습니다.

세마포어는 하나의 스레드(binary semaphore)만 들어가거나
혹은 여러 개의 스레드(counting semaphore)가 들어가게 할 수도 있습니다.

Q. 뮤텍스와 모니터의 차이는?

• 가장 큰 차이는 뮤텍스는 다른 프로세스(애플리케이션) 간에 동기화를 위해 사용한다.
• 반면 모니터는 하나의 프로세스(애플리케이션) 내에 다른 스레드 간에 동기화할 때 사용한다.
• 또한, 뮤텍스는 보통 운영체제 커널 의해서 제공되는 반면에 모니터는 프레임워크나 라이브러리 그 자체에서 제공된다.
• 따라서 뮤텍스는 무겁고(heavy-weight) 느리며(slower)모니터는 가볍고(light-weight) 빠르다(faster).

Q. 세마포어와 모니터의 차이는?

• Java에서는 모니터를 모든 객체에게 기본적으로 제공하고 있는 반면 C에서는 모니터를 사용할 수 없다.
• 세마포어는 카운터라는 변수값으로 프로그래머가 상호 배제나 정렬의 목적으로 사용 시매번 값을 따로 지정해 줘야 하는 등 조금 번거롭다.
• 반면, 모니터는 이러한 일들이 캡슐화 되어 있어서(encapsulation) 개발자는 카운터 값을 1 또는 0으로 주어야 하는 고민을 할 필요 없이 synchronized, wait(), notify() 등의 키워드를 이용해 좀 더 편하게 동기화할 수 있다.

Q. 뮤텍스와 세마포의 차이는?

• 세마포어는 뮤텍스가 될 수 있지만 뮤텍스는 세마포어가 될 수 없다.
• 예를 들어 Casting을 한다고 보면 (뮤텍스) 세마포어 –> 가능 / (세마포어) 뮤텍스 –> 불가능
• 세마포어는 소유할 수 없는 반면 뮤텍스는 소유할 수 있고 소유자가 이에 책임을 진다.
• 뮤텍스는 1개만 동기화가 되지만, 세마포어는 하나 이상을 동기화 할 수 있다.

뮤텍스 : 한 스레드, 프로세스에 의해 소유될 수 있는 Key🔑를 기반으로 한 상호배제 기법
세마포어 : Signaling mechanism. 현재 공유자원에 접근할 수 있는 스레드, 프로세스의 수를 나타내는 값을 두어 상호배제를 달성하는 기법

📌 교착상태(Dead Lock)와 임계 영역(Critical Section)

교착상태(Dead Lock) : 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태 즉, 자원 요청을 무한정 대기하고 있는 상태

임계 영역(Critical Section) : 공유 자원이 속해있어 교착상태가 발생할 수 있는 영역
경쟁 상태는 여러 프로세스(혹은 스레드)가 동시에 공유 자원에 접근하기 때문에 발생합니다.
그래서 우리는 공유 자원에 대하여 한 번에 하나의 프로세스만이 이에 접근할 수 있도록 통제해야 하는데, 그러한 통제가 필요한 영역을 임계 영역(Critical section)이라고 부릅니다.

임계 영역 문제를 해결하기 위한 방법

• 뮤텍스, 세마포어, 모니터 등이 있습니다.

• 상호 배제, 한정 대기, 진행, 융통성이라는 조건을 만족해야 합니다.

  1. 상호배제(Mutual Exclusion) : 한 순간에 한 프로세스만 임계영역에 진입할 수 있도록 제어합니다.
     이를 위해 락(lock), 세마포어(Semaphore), 모니터(Monitor) 등의 도구를 사용할 수 있습니다.

  2. 교착상태(Deadlock) 방지 : 교착상태는 두 개 이상의 프로세스가 서로 상대방이 점유한 자원을 기다리며 무한정 대기하는 상황을 말합니다.
     이를 방지하기 위해서는 교착상태가 발생하지 않도록 자원 할당 순서를 결정하거나, 타임아웃(timeout)을 사용하여 대기 시간을 제한하는 등의 방법을 사용할 수 있습니다.

  3. 진행(Progress) 보장 : 한 프로세스가 임계영역에 진입하려고 할 때, 다른 프로세스들이 계속해서 실행되도록 보장합니다.
     이를 위해 프로세스들이 번갈아가며 임계영역에 진입할 수 있도록 제어합니다.

  4. 공평성(Fairness) 보장 : 모든 프로세스가 임계영역에 동등하게 접근할 수 있도록 보장합니다.
     이를 위해 선착순(First-Come, First-Served) 기반으로 대기열을 관리하거나, 프로세스의 우선순위에 따라 접근 권한을 부여하는 등의 방법을 사용할 수 있습니다.

교착상태(Deadlock)가 발생조건

교착상태(Deadlock)가 발생하기 위해서는 다음 4가지 조건이 모두 충족되어야 합니다.

1. 상호배제(Mutual Exclusion) : 자원은 한 번에 하나의 프로세스만이 사용할 수 있습니다.

2. 점유와 대기(Occupy and Wait) : 하나의 프로세스가 자원을 점유한 상태에서 다른 프로세스가 점유한 자원을 대기하고 있습니다.

3. 비선점(No Preemption) : 다른 프로세스가 점유한 자원을 강제로 빼앗아 사용할 수 없습니다.

4. 순환 대기(Circular Wait) : 두 개 이상의 프로세스가 서로가 점유한 자원을 대기하고 있습니다.
   예를 들어, 프로세스 A가 자원 1을 점유하고, 프로세스 B는 자원 2를 점유하고 있으며, 프로세스 C는 자원 1을 대기하고, 프로세스 D는 자원 2를 대기하는 경우가 있습니다.

이 조건들이 모두 충족되면, 각 프로세스는 자원을 점유한 상태에서 다른 프로세스가 점유한 자원을 대기하며, 자원을 서로 요청하고 서로를 기다리는 순환 대기 상태가 발생하여 교착상태가 발생합니다.

데이터 레이스(Data race)

데이터 레이스(Data race) :데이터 레이스(Data race)는 멀티스레드 환경에서 발생하는 동시 접근 문제로, 두 개 이상의 스레드가 공유된 변수 또는 메모리 위치에 동시에 접근하면서 발생합니다. 이러한 상황에서는 스레드가 해당 변수나 메모리 위치의 값을 변경하려는 시도를 할 때, 다른 스레드가 이미 그 값을 변경한 상태이므로, 의도치 않은 결과가 발생할 수 있습니다.

예를 들어, A 스레드와 B 스레드가 동시에 변수 X의 값을 변경하려고 시도하는 경우를 생각해보겠습니다.
만약 A 스레드가 X의 값을 읽고 10을 더하고 저장하는 도중에 B 스레드가 X의 값을 읽고 20을 더하고 저장한다면, A 스레드가 X를 10 증가시켰지만, B 스레드가 먼저 저장한 값으로 인해 X가 20 증가할 수 있습니다. 이러한 상황을 데이터 레이스라고 합니다.