Semaphore 란?


공유자원에 여러 프로세스가 동시에 접근하면서 문제가 발생할 수 있다. 이때 공유자원의 데이터는 한 번에 하나의 프로세스만 접근할 수 있도록 제한을 줘야한다.

Semaphore 는 멀티 프로그래밍 환경에서 공유자원에 대한 접근을 제한하는 방법이다.

임계 구역

여러 프로세스가 데이터를 공유하며 작업을 수행할 때, 각 프로세스에서 공유자원을 접근하는 프로그램 코드 부분을 의미한다.

한 프로세스가 임계 구역을 수행할 때, 다른 프로세스가 접근하지 못하도록 해야 한다.

Semaphore P, V 연산

  • P(S) - 임계 구역에 들어가기 전에 수행
  • V(S) - 임계 구역에서 나올 때 수행

Mutex 란?


Mutual Exclusion, Mutex 는 임계 구역을 가진 스레드들의 실행시간이 서로 겹치지 않고 단독으로 실행되게 하는 기술을 의미한다.

해당 접근을 조율하기 위해 lockunlock 을 사용한다.

  • lock - 현재 임계 구역에 들어갈 권한을 얻어온다.
  • unlock - 현재 임계 구역을 모두 사용했음을 알린다.

Semaphore 와 다르게 lock 을 획득한 프로세스만 lock 을 반환할 수 있다.

Mutex 알고리즘


Dekker 알고리즘

flagturn 변수를 통해 임계 구역에 들어갈 스레드를 결정하는 방식이다.

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

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

References