# Outline

• Background
• The Critical-Section Problem
• Peterson’s Solution
• Hardware support for synchronization
• Semaphores
• Monitors
• Liveness
• Synchronization examples

---

Background:

• 프로세스 간에 process synchronization이 꼭 필요하다.

[예시:Too much milk problem]

• 위와 같이 share resource에 대한 process synchronization가 없으면, race condition이 발생할수있다.

• 이를 대처하기 위해, locking mechanism을 사용

[race condition의 예시]

[locking mechanism]

• race condition이 주로발생할때(shared resource에 두개이상의 프로세스가 동시접근할때 발생):
  1. 멀티쓰레딩
  2. preemptive kernel
     • 시스템콜 호출시 발생
       

---

The Critical-Section Problem:

• critical section을 사용하기 위해 여러 조건이 필요하다

1. Mutual Exclusion: 어떠한 시점에서라도 critical section을 사용하는 프로세스는 1개여야한다.
2. Progress: critical section이 비어있고, critical section에 들어가고자 하는 프로세스가 1개 이상 존재할때, critical section에 반드시 진입해야한다.
3. Bounded Waiting: critical section에 기다린 순서대로 critical section에 들어가야한다.

---

Peterson’s Solution

• Peterson’s Solution은 위 세가지 critical section 특성을 지킨다.

1. Mutual Exclusion:

while 문에서 i프로세스는 탈출하지만, j프로세스는 탈출하지 못한다.
따라서 critical section에는 i프로세스만 접근하고 있으므로 Mutual Exclusion을 보장해준다.

2. Progress:

CS가 비어있는상태일때, j프로세스가 1번 혹은 2번 명령어를 실행하더라도 i프로세스는 CS에 접근가능하다. 즉, 비어있는 상태에는 1개의 프로세스가 접근이 가능하다.

3. Bounded Waiting:

실행순서를 결정된다.

• Critical section은 흡사 Bathroom과 같다.

---

Hardware support for synchronization

• 컴퓨터는 atomic hardware instructions(ex: test memory word and set value , swap)을 제공하여 synchronization을 보장할 수 있게 해준다.
• 하지만 mutual exclusion과 progress만 고려한다.

1. TestAndSet:

-> TestAndSet함수는 atomic operation이다.

만약 TestAndSet함수는 atomic operation이 아니라면, mutual exclusion이 보장되지 않는다.

2. Swap:

• 위 두가지 방법은 bounded waiting을 보장하지 않는다.

---

Semaphores

Semaphore:

• Semaphore은 정수이다.
• wait() / p() 와 signal() / V() 함수를 사용한다.

예시:

Semephore s;
wait(s);
c.s
signal(s);

• Mutual exclusion을 보장하려면 semaphore 값이 1이여야 한다.

• 위 방식은 busy waiting이 발생한다.(state가 ready라서 스케쥴러가 cpu를 계속 할당하고 있지만 하는건 없다.)

busy waiting없이 semaphore 실행하기.

• waitinglist를 활용하여 busy waiting 문제를 해결한다.
• Semaphore 값을 1로 설정해야 mutaul exclusion을 해결할수있다.

---

Monitors

---

Liveness

---

Synchronization examples

---