Process Synchronization(2)_운영체제(6)

Mutex

• OS가 지원하는 lock object이다.
• lock spinning을 예방하기 위해서 만들어졌다.
• mutex_lock : acquire / lock permission을 얻는다. 누군가 lock을 가지고 있다면 다음 온 process는 lock이 release될 때까지 block한다. / system call이다.
• mutex_unlock : release / 다 쓴 뒤 lock을 반납한다. 다 쓴 뒤 기다리고 있는 process를 OS가 waiting queue에서 wake up 해준다.
• block() : 호출한 process는 wake up할 때까지 기다린다.
• wakeup(int pid) : block되어 있는 process를 깨운다.

Semaphores

• lock보다 higher level인 synchronization 방법
• busy waiting을 피하는 방법이다.
• 상태(state)를 나타내는 integer value를 가지고 있는 object이다. - 여러 값을 가질 수 있다.
• State는 직접적으로 user에 의해 접근하면 안되고 semaphore operation을 이용하여 상태를 바꿔야한다.

S_wait()

• 자원을 가져가는 것
• 현재 object의 상태값을 decrement
• -1한 값이 음수가 되면 value >= 0 이 될 때까지 wait한다.
• P(), down(), sem_wait()..

S_signal()

• 자원을 반납하는 것
• +1한 값이 음수라면 wait하고 있는 것을 wake up
• 현재 object의 상태값을 increment
• V(), up(), sem_post()...

• 1, 2 상황에서 interrupt가 발생하면 여러 자원을 한번에 가져가버릴 수 있으니 lock(spin lock.., interrupt disabled)을 사용해야한다.
• kernel에서 value 값 확인을 통해 Queue에 몇 개의 process가 대기하고 있는지 알 수 있다.

Types of Semaphores

Binary Semaphore

• mutex와 동일하게 사용하는 방식
• value의 초기값을 1로 설정한다.
• mutex는 초기값이 0으로 했다가 lock을 하면 1로 바꾸지만 semaphore는 자원의 개수를 나타내는 value 변수이기 때문에 초기값이 1이다.

Counting semaphore

• value 값을 N으로 초기화하는 방식
• 자원이 여러개 있어 N개의 process가 사용할 수 있고, value가 음수가 되었을 때 wait하게 된다.

Bounded Buffer Problem(Producer consumer problem)

• 제한된 원소를 가지는 buffer에 producer는 write, consumer는 read를 하는 예시이다.
• producer는 buffer에 resource insert, consumer는 buffer에 resource remove
• producer와 consumer는 서로 동작하는 속도가 다를 수 있다.

Readers-Writers Problem

• shared lock / exclusive lock의 문제
• multiple readers / one writer
• writing을 하는 중에 read할 수 없다. / read를 하는 중에 write할 수 없다.
• readcount : reading object thread의 수
• mutex : critical에 접근을 제어하는 binary semaphore
• rw : exclusive write : binary semaphore

Dining Philosophers Problem – semaphore & deadlock example

• 모두 왼쪽(오른쪽)의 fork를 잡은 경우? : deadlock 상황
• deadlock : 스스로 해결할 수 없는 무한 대기 상황

• fork를 binary semaphore로 설정
• if pickup에서 왼쪽, 오른쪽을 얻으면 eat()
• 작동하다가 deadlock 상황에 빠질 수 있다.

• 홀수는 왼쪽 먼저, 짝수는 오른쪽 먼저 잡는 방식으로 해결을 가능하다.
• 하지만 계속해서 자원에 대한 경쟁도가 높아지게 되어서 성능이 낮아질 수 있다.
• 예시에서는 deadlock free 방식으로 맨 마지막 사람만 오른쪽을 먼저 잡는 방식으로 해결한 것이다.

Semaphore Pros & Cons

• Pros
  • critical section에서 유용하게 사용한다. race condition 예방.
• Cons
  • 일종의 global variables 형태로 사용하는데, 어디서든 사용가능하기 때문에 program을 복잡하게 만들 수 있다.
  • semaphore와 semaphore가 보호하는 자원 사이의 관계가 명확하지 않다.
  • 사용하는데 있어서 절차가 보장되어있지 않아 bug가 생길 수 있다.

Condition Variables

• event를 기다리는 mechanism을 제공
• condition queue를 만들어 대기하도록 한다.

operation

• wait(c, mutex)
  • mutex를 반납하고 waiting한다.
• signal(c)
  • condition queue의 제일 앞에 있는 process가 wake-up한다.
  • 다른 process가 실행해서 다른 process를 깨우는 것이다.
  • signal을 한 thread가 mutex를 반납하고 받아야 queue에서 thread가 나오는 것이다.
  • signal을 했는데 queue에 아무도 없으면 아무 일도 일어나지 않고 signal이 lost된다.
  • wait operation과 짝이 맞을 필요 없다. (semaphore는 짝이 맞아야한다.)
• broadcast(c)
  • 모든 waiting process를 wake-up시킨다.
  • 주로 memory allocation 상황에 사용된다.

CV Semantics

Mesa semantics

• 조건이 만족해서 깨어났을 때 다른 thread가 끼어들어서 조건이 깨어질 수도 있다.
• 돌아갈 때 조건을 recheck하는 방법
• OS입장에서 부담이 없다.

Hoare semantics

• 조건이 만족해서 깨어났을 때 그 thread에게 다른 thread가 끼어들지 못하게 signal이 발생하자마자 바로 scheduling을 하는 방법
• 주로 timing이 중요한 hard realtime system에서 사용하는 방식

examples

• while을 사용 : 깨어났을 때 조건을 다시 recheck한다.
• mesa semantic을 사용한 방식

Using Broadcast

• 다른 threads에게 memory를 할당할 때 사용
• byteleft : 할당할 수 있는 남은 byte → 여러 자원이 확인하기 때문에 mutex

Semaphores vs Mutex + CV

• system call(block, wakeup)을 사용하지 않고 CV를 사용하여 semaphore를 구현한 코드

Monitors

• programming language가 제공하는 shared data에 접근을 제어해주는 구조
• compiler가 자동으로 코드를 생성해서 삽입해준다.
• shared data structure, procedures, synchronization을 캡슐화하고 있는 software module
• 오직 procedure를 통해서만 data에 접근한다.
• x, y : condition variable 기능
• entry queue : mutex와 같은 역할
• Mutual exclusion을 지원한다.
  • 오직 1개의 process만 inside로 실행, 다른 프로세스가 떠날 때 까지 block 상태
• system으로 실행하기 때문에 concurrency, performance는 떨어질 수 있다.

Monitor Example

• programmer는 우측의 코드와 같이 작성하고, 실제로는 compiler가 좌측의 코드를 실행하며 mutex를 실행한다.

Synchronized – Java

• 배타적으로 작동된다.
• synchronized 메소드끼리만 mutual exclusion이 되고 다른 method는 되지 않는다.
• 각 개체 당 implicit하게 cv가 생성된다.
• Wait, Notify, Notifyall 의 operation이 제공된다.