---

Process Synchronization

데이터의 접근

• 누가 먼저 접근하냐에 따라서 문제 발생 가능성 (Synchronization)

Race Condition

• 여러 주체들이 하나의 데이터에 동시에 접근하려고 할 때 Race Condition 발생 가능성

• 멀티프로세서에서 메모리 공유시 Race Condition문제 발생 가능성

OS에서의 Race Condition

• 1. 커널 모드로 수행 중에 인터럽트 발생
     

     1. 본래의 의도는 ++, --가 모두 바년되어 count가 초기값이 유지되는 것이다
     2. 만약 Load이후 인터럽트 발생 시 인터럽트 이후의 결과는 반영되지 않고 count++만 반양
     3. 커널 모드의 수행이 끝나기 전에는 인터럽트를 받지 않도록 하는 (disable / enable)로 문제 해결 가능

• 2. 프로세스가 시스템 콜을 호출해서 커널 모드로 수행 중인데 Context switch가 발생
     

     해결법 : 커널 모드를 수행 중일 땐 CPU가 preempt되지 않도록 유지하고, 커널모드에서 유저 모드로 돌아갈 때 preempt

• 3. 멀티 프로세서에서 공유 메모리 내의 커널 데이터에 접근하는 경우
     
     race condition : 어떤 CPU가 마지막으로 Count를 저장했는가?

싱글 프로세스인 경우 인터럽트 disable / enable방법으로는 해결 가능하지만, 멀티 프로세서는 인터럽트 제어로는 해결 불가능

방법 1 : 한 번에 한 CPU만 커널에 들어갈 수 있도록 하는 방법
- 비효율적이다.
- 만약에 두 프로세서가 서로 다른 데이터에 접근하여 Race Condition 가능성이 없어도, 한 번에 한 CPU만 커널에 들어갈 수 있기 때문이다.
방법 2 : 커널 내부에 있는 공유 데이터에 접근할 때 마다 해당 데이터에 lock / unlock를 한다

프로세스 Race Condition 해결책

Critical section : 공유 데이터를 건들이는 공간 (중요)
해당 세션은 lock을 걸고(entry section), 풀고(exit section)하는 작업이 필요.

Critical section 해결 조건

1. 상호 배제 (Mutual Exclusion)
   • 동시에 들어가면 안됨
2. 진행 (Progress)
   • 아무도 들어가 있지 않은 상태에서, 들어가고자 하는 것이 있으면 통과 시켜줘야 한다
3. 유한 대기 (Bounded Waiting)
   • 대기시간은 유한해야한다

Algorithm 1

1. 위 코드가 P0, 밑줄 친 turn={i}의 코드에서 0과 1이 바뀐 것을 P1이라고 가정

2. turn이라는 Synchronization variable을 두고, critical section에 들어가기전에, 이번엔 누구 차례인지 알아낸다 (한번씩 번갈아가며)

3. 특정 프로세스가 더 들어가야하거나 상대방이 아예 안들어간다면, 즉 원하지 않는데 번갈아 들어가야한다는 단점이 존대

Algorithm 2

1. 깃발을 두어 누가 들어가고 싶은지 보는 방법.

2. 자신의 깃발(flag[i])을 올리고, 상대방의 깃발(flag[j])를 확인한 뒤에 critical section에 입장

3. 동시에 들어가는 방법은 깃발을 통해 방지하지만, '진행'에 있어서 문제가 있다.

Algorithm 3 (Peterson's Algorithm)

1. 위 두가지 방법을 합친 방법이다.

2. 모든 조건을 만족하며 해결할 수 있다.

3. 내 깃발을 들고, 상대방 깃발이 들려있는지 && 상대방 차례면 -> 기다림!

4. 하지만 Busy Waiting(spin lock)이라는 문제 발생 가능성 있음.
   while을 빠져나갈려면 상대방이 turn을 줘야하는데, while때문에 CPU를 줄 수가 없다는 문제

소프트웨어적으로 Process Synchronization 해결
하드웨어적으로 Process Synchronization 해결

Synchronization Hardware

• critical section 접근 문제는 하드웨어적으로 Test & modify(set)을 atomic(나누지 말고 한번에)하게 수행하면 해결 가능.

• 하드웨어적으로 기능을 제공하기만 하면 문제 해결 가능
• 크리티컬 섹션에 들어가기 전에 lock
• 만약 lock이 0 이면 내가 lock 해서 1로 변경 후 입장

Semaphore

• Critical Section으로 들어가기 위한 작업을 추상화
• 추상 자료형
• object + operation
• 논리적으로 구성되는 것
• 변수는 정수값을 가질 수 있다.

사용 이유

• 공유 자원을 획득하고 반납
• p 연산 : lock 걸기 (자원 획득)
• v 연산 : lock 반납 (자원 반납)
• 정수형 변수 값 S : 자원의 개수
  

• race condition 문제를 쉽게 해결 가능

• 상대방이 V연산을 하기 전에 자신은 P만 진행하기 때문에 busy-wait을 해야한다.
  이를 해결하기 위해서 Block/Wakeup 방법을 사용하면 된다

Critical Section of n Process

• 프로그래머는 세마포어 방식을 사용시 편리
• busy-wait 는 효율성 낮음 (=spin lock)
• Block & Wake up 방식 (=sleep lock)

Block / Wakeup Implementation

• Sepaphore를 정의, 큐를 사용해 대기 상태로 줄세움
  
  락이 걸렸을 때 sleep을 하여 busy wait을 탈출

Implementation

Block/wakeup version of P() & V()

• P

  S.value -> 자원이 없는 상태
  자원이 생기면 block()이 생성

• V

  S.value() <= 0
  - 누군가가 자원을 기다리고 있다는 상황

어떤게 더 나을까?

Busy-wait vs Block/wakeup

• 1. Block/wakeup
     CPU를 의미있게 효율적으로 이용 가능
     

Two Types of Semaphores

Counting semaphore

• 도메인이 0 이상인 임의의 정수값
• 주로 resource counting에 사용

Binary semaphore(=mutex)

• 0 또는 1 값만 가질 수 있는 semaphore
• 주로 mutual exclusion (lock/unlock)에 사용

Deadlock and Starvation

순서를 바꿔서 Deadlock 해결

Classical problems of Synchronization

1. Bounded-Buffer Problem (Producer-Consumer Problem)

• 여러 개의 프로세스를 어떻게 동기화할 것인가
• 해결하는 것을 생산자-소비자 협동이라 하며, 버퍼가 동기화 되어 정상적으로 동작하는 상태.
• 이 문제를 해결하기 위해 세마포어를 활용.
  

프로세스

• Producer (생산자)

• Consumer

주황색 버퍼는 생산자가 데이터를 만들어서 집어놓은 상태
아니면 이미 만들어놓은 버퍼를 소비자가 사용한 경우

생길 수 있는 문제

• 공유버퍼에 대해 lock 을 걸었다가 풀어야 함

• 생산자 소비자 문제

1. 버퍼가 bounded 생산자가 한꺼번에 도착해서 버퍼가 다 채워졌을 때, 소비자는 안 오고 생산자는 계속 버퍼를 만든다
   • 사용할 수 있는 자원 부족 (소비자가 가져가야지만 버퍼를 사용 가능)
2. 생산자는 빈 버퍼가 생길 때 까지 대기.
   • 버퍼가 없으면 소비자가 기다려야 한다.
     

2. Readers-Writers Problem

• 여러 명의 Readers, Writers 가 하나의 저장 공간(버퍼)를 공유하며 이에 접근할 때 발생

  한 process 가 DB에 작성 중일 때 다른 precess가 접근하면 안된다 (동시 접근 x)
  read는 동시에 여럿이 해도 된다 (read는 동시에 해도 되는데 하나 밖에 못하게 하면 비효율적)
  

• Reader

  db lock 걸기
  readcount : 몇 명이 읽었는지
  최초의 reader -> lock 걸어야 함
  다음 reader들 -> 바로 읽는다
  db lock 풀기
  공유 변수 readcount를 위해 mutex에 lock을 걸 필요가 있음

3. Dining Philosophers Problem

생각, 배고픔 시간은 다르지만 젓가락은 하나

Deadlock 가능성

모두가 동시에 배고파졌을 때 -> 왼쪽 젓가락을 모두 들었을 때 발생

해결법

• 4명의 철학자만 테이블에 동시
• 젓가락 두 개 집을 수 있을 때만 젓가락을 집을 수 있게 한다.
• 비대칭
  - 짝수 철학자는 왼쪽 홀수 철학자는 오른쪽 부터 잡도록 한다.
  

semaphore self[5] = 0
- 5번 철학자는 두 개의 젓가락을 잡을 수 없다.

semaphore mutex = 1
- 공유 변수에 대해 동시 접근 막기 위해

Monitor

• semaphore 의 문제점

  1. 코딩 어려움
  2. 정확성 입증 어려움
  3. 자발적 협력 필요
  4. 한번의 실수가 모든 시스템에 치명적
     

• 동시 수행 중인 프로세스 사이에서 abstrac data type의 안전한 공유 보장을 위한 high-level synchronization construct

monitor는 동시접근이 기본으로 막아져 있기 때문에 lock 필요 없음

공유자원 선언, 프로시저, 초기화 코드가 포함된 병렬식 구조 -> lock필요없음

• 상태를 저장
• Signal 을 보낸다는 것은 해당 프로세스가 Lock 얻었음
• semaphore 변수처럼 condition vairable 변수

wait

• 자원이 없으면 프로세스가 줄을 서서 대기
• x.wait() 을 호출한 프로세스는 다른 프로세스가 x.signal() 을 호출하기 전까지 sleep

signal

• 모니터에 접근하고 빠져나갈 때 signal 연산을 호출해서 기다리는 프로세스가 모니터에 접근할 수 있도록 만듬.
• x.signal() 은 정확하게 하나의 잠이 든 프로세스를 깨운다.
• 잠이 든 프로세스가 없으면 아무 일도 일어나지 않는다.

Bounded Buffer Problem (semaphore)

Bounded Buffer Problem (monitor)

• condition variable -> empty, full

• wait

  자원이 없으면 프로세스가 줄을 서서 대기.
  x.wait() 을 호출한 프로세스는 다른 프로세스가 x.signal() 을 호출하기 전까지 sleep

• signal

  모니터에 접근하고 빠져나갈 때 signal 연산을 호출해서 기다리는 프로세스가 모니터에 접근할 수 있도록 한다.
  x.signal() 은 정확하게 하나의 잠이 든 프로세스를 깨운다.
  잠이 든 프로세스가 없으면 아무 일도 일어나지 않는다.

Dining Philosophers Problem

---