Semaphore 란?
공유자원에 여러 프로세스가 동시에 접근하면서 문제가 발생할 수 있다. 이때 공유자원의 데이터는 한 번에 하나의 프로세스만 접근할 수 있도록 제한을 줘야한다.
Semaphore 는 멀티 프로그래밍 환경에서 공유자원에 대한 접근을 제한하는 방법이다.
임계 구역
여러 프로세스가 데이터를 공유하며 작업을 수행할 때, 각 프로세스에서 공유자원을 접근하는 프로그램 코드 부분을 의미한다.
한 프로세스가 임계 구역을 수행할 때, 다른 프로세스가 접근하지 못하도록 해야 한다.
Semaphore P, V 연산
- P(S) - 임계 구역에 들어가기 전에 수행
- V(S) - 임계 구역에서 나올 때 수행
Mutex 란?
Mutual Exclusion, Mutex 는 임계 구역을 가진 스레드들의 실행시간이 서로 겹치지 않고 단독으로 실행되게 하는 기술을 의미한다.
해당 접근을 조율하기 위해 lock 과 unlock 을 사용한다.
lock- 현재 임계 구역에 들어갈 권한을 얻어온다.unlock- 현재 임계 구역을 모두 사용했음을 알린다.
Semaphore 와 다르게 lock 을 획득한 프로세스만 lock 을 반환할 수 있다.
Mutex 알고리즘
Dekker 알고리즘
flag 와 turn 변수를 통해 임계 구역에 들어갈 스레드를 결정하는 방식이다.
Peterson 알고리즘
Dekker 와 유사하지만, 상대 스레드에게 진입 기회를 양보하는 것에 차이가 존재한다.
Bakery 알고리즘
여러 스레드에 대한 처리가 가능한 알고리즘이다. 가장 작은 수의 번호표를 가지고 있는 프로세스가 임계 구역에 진입한다.
Semaphores
- A tool that can be used to enforce mutual exclusion
- Is a protected variable with methods for restricting access to
critical resources - A binary semaphore takes values 0 and 1
- A counting semaphore takes 0 ~ infinity
- Is a protected variable with methods for restricting access to
Producer-Consumer Problem
- It is a classical example of a multi-process synchronization problem
- Also known as the Bounded-Buffer Problem
- Occurs when a critical section is
not mutually exclusive - It can be solved by enforcing mutual exclusion
Problem using semaphore - Deadlock
- Permanent blocking of a set of processes that either compete for the system resources
- Deadlock only occurs in a system where all 4 conditions are met
- Conditions
- Mutual Exclusion: Only one process can use a resource at a time
- Hold and Wait: Processes already holding resources may request new resources
- No Preemption: No resource can be forcibly removed from a process holding it
- Circular Wait: Two or more processes form a circular chain where each process waits for a resource that the next process in the chain holds
- Dining Philosopher Problem is a famous example of deadlock
- It explains the solution by introducing binary semaphore as a waiter
Monitor
- Improved version of multi-process synchronization
- Provided through OOP languages
- Enforces one process at a time to ensure mutual exclusion
Problem using semaphore - Starvation
- The process is perpetually denied necessary resources
- Solution
- Use a scheduling algorithm with a priority queue that also uses the aging technique