동기화

Semaphore

• 두 개의 원자적 연산(atominc operation)을 가지는 정수 변수
• wait(), P() / signal(), V()
• P는 Critical Section 들어가기 전, V는 Critical Section 나온 후 실행
• P, V 연산: 독립적 + 원자젹 수행. 하나의 프로세스가 P를 수행하여 세마포어의 값을 수정하는 동안에는 다른 프로세스에서 P나 V를 수행해도 세마포어의 값을 수정하지 못함

Peterson Solution + Semaphore: ME, P, BW

• flag 필요 없음, process: 동일한 동작
  
• P를 통과하면 +, V를 통과하면 -가 되는 세마포어 (0, 1로 alternate)

1. Counting Semaphore

• 세마포어 값 범위 자유
• 초깃값은 가능한 자원 수로 결정
  

2. Binary Semaphore

• 세마포어 값 0, 1로 고정
• Counting Semaphore보다 간단한 구현

  바이너리를 통해 카운팅 세마포어를 구현할 수도 있다!

• Test & Set을 통해 구현 가능 → critical section 진입 프로세스 유무 확인
• P(S): while(testAndSet(&S));
• V(S): S = 0;
• 카운팅 값을 통해 현재 진입 여부를 계속 체크

Original Semaphore

• Busy Waiting: Critical Section 진입 조건이 만족될 때까지 계속해서 Loop를 돌면서 기다린다.
• 유니 프로세서 환경에서 CPU 사이클이 낭비
• 대기 프로세스에서는 누가 Critical Section에 진입할지 결정 X

Semaphore + Sleep Queue

• Sleep Queue 자료 구조 → CPU 점유 없이 사이클 낭비 막을 수 있음
• 큐에 어떤 프로세스를 넣고 어떻게 뺄 것인지 담당해야 하는 핸들러 필요
  

Semaphore - Limitation

• P, V 연산 분리 → 함께 관리 X

1. P(); → Critical Section → P();: V()가 없기 때문에 다른 프로세스가 critical section 진입 불가능
2. V(); → Critical Section → P();: lock을 걸어주는 P()가 없기 때문에 ME가 만족되지 않을 수 있음

• 하이 레벨 단계에서 동기화를 보장하는 방법이 필요함

Semaphore Implementation

• 세마포어가 어떻게 원자적으로 처리되는가?

1. 싱글 스레드 커널: 시스템 콜로 P(), V() 실행. 커널 내에서 세마포어 동작 구현. 커널 내 수행이 비선점, 커널 내 프로세스가 critical section에 들어간 것으로 간주됨
2. 멀티 스레드 커널: P(), V()를 시스템 콜로 실행. 커널 내에서 별도로 동기화를 해야 함

Deadlock

• 두 개 이상의 프로세스가 계속해서 기다리고 있는 상황

Partical Order

• 데드락 해결 방법
• P에 대한 binary relation - reflexive, antisymmetric, transitive 조건 만족

Monitor

• 세마포어는 사용자의 P(), V()를 명시적으로 순서대로 사용할 것을 요구
• 하이 레벨 단계에서의 동기화 방법 필요: Java 스레드의 동기화를 위한 Monitor 호출
• Synchronized: 동기화 영역을 지정할 수 있음
  
  
• Transaction: DB 단위에서 transaction 시작/종료를 체크, 원자적으로 수행됨