4.1. 동기화 & 상호배제

- Process Synchronization (동기화)

• 다중 프로그래밍 시스템
  - 여러 개의 프로세스들이 존재
  - 프로세스들은 서로 독립적으로 동작
  - 공유 자원 또는 데이터가 있을 때, 문제 발생 가능

• 동기화 (Synchronization)
  - 프로세스들이 서로 동작을 맞추는 것
  - 프로세스들이 서로 정보를 공유하는 것

---

- Asynchronous and Concurrent P's

• 비동기적 (Asynchronous)
  - 프로세스들이 서로에 대해 모름

• 병행적 (Concureent)
  - 여러 개의 프로세스들이 동시에 시스템에 존재

• 병행 수행중인 비동기적 프로세스들이 공유 자원에 동시 접근 할 때 문제가 발생 할 수 있음

---

- Terminologies

1. Shared data (공유 데이터) or Critical data
   • 여러 프로세스들이 공유하는 데이터

2. Critical Section (임계 영역)
   • 공유 데이터를 접근하는 코드 영역(Code segment)

     

     

     • Race Condition : 순서에 따라 결과가 달라짐 -> 해결책 : 상호배제

3. Mutual Exclusion (상호배제)
   • 둘 이상의 프로세스가 동시에 Critical Section에 진입하는 것을 막는 것

---

- Mutual Exclusion Methods

• Mutual exclusion primitives (Primitive = 기본 연산)
  1. enterCS() primitive
  - Critical section 진입 전 검사
  - 다른 프로세스가 critical section 안에 있는지 검사

  2. exitCS() primitive
  - Critical section을 벗어날 때의 후처리 과정
  - Critical section을 벗어남을 시스템이 알림

  

---

- Requirements for ME primitives

1. Mutual exclusion (상호배제)
   • Critical section(CS)에 프로세스가 있으면, 다른 프로세스의 진입을 금지

2. Progress (진행)
   • CS 안에 있는 프로세스 외에는, 다른 프로세스가 CS에 진입하는 것을 방해하면 안됨

3. Bounded waiting (한정대기)
   • 프로세스의 CS 진입은 유한시간 내에 허용되어야 함

- Two Process Mutual Exclusion

---

- Mutual Exclusion Solutions

1. SW solutions
   • 2-Process Mutual Exclusion
     - Dekker's algorithm (peterson's algorithm)
     
     
   • N-Process Mutual Exclusion
     - Dijkstra's algorithm, knuth's algorithm, Eisenberg and McGurie's algirthm, Lamport's algorithm

2. HW solution
   • TestAndSet (TAS) instruction

3. OS supported SW solution
   • Spinlock
   • Semaphore
   • Eventcount/sequencer

4. Language-Level solution
   • Monitor

---

- 2-Process Mutual Exclusion

- Dekker's Algorithm

• Two process ME를 보장하는 최초의 알고리즘
  

- Peterson's Algorithm

• Dekkers' algorithm 보다 간단하게 구현
  

---

- N-Process Mutual Exclusion

1. 다익스트라(Dijkstra)
   • 최초로 프로세스 n개의 상호배제 문제를 소프트웨어적으로 해결
   • 실행 시간이 가장 짧은 프로세스에 프로세서를 할당하는 Semaphore1방법, 가장 짧은 평균 대기시간 제공
     
     
2. 크누스(Knuth)
   • 이전 알고리즘 관계 분석 후 일치하는 패턴을 찾아 패턴의 반복을 줄여서 프로세스에 프로세서 할당
   • 무한정 연기할 가능성을 배제하는 해결책을 제시했으나, 프로세스들이 아주 오래 기다려야함
     
     
3. 램포트(Lamport)
   • 사람들로 붐비는 빵집에서 번호표 뽑아 빵 사려고 기다리는 사람들에 비유해서 만든 알고리즘 (Bakery Algorithm)
   • 준비 상태 큐에서 기다리는 프로세스마다 우선순위를 부여하여 그 중 우선순위가 가장 높은 프로세스에 먼저 프로세서를 할당함
     
     
4. 핸슨(Brinch hHansen)
   • 실행 시간이 긴 프로세스에 불리한 부분을 보완하는 것
   • 대기시간과 실행 시간을 이용하는 모니터 방법
   • 분산 처리 프로세서 간의 병행성 제어 많이 발표

- Dijkstra's Algorithm

• Dijkstra 알고리즘의 flag[] 변수

flag[]의 값	의미
idel	프로세스가 임계 지역 진입을 시도하고 있지 않을 때
want-in	프로세스의 임계 지역 진입 시도 1단계일 때
in_CS	프로세스의 임계 지역 진입시도 2단계 및 임계 지역 내에 있을 때

- SW Solution들의 문제점

1. 속도가 느림
2. 구현이 복잡함
3. ME primitive 실행 중 preemption 될 수 있음
   • 공유 데이터 수정 중은 interrupt를 억제함으로서 해결 가능
     -> overhead 발생
4. Busy waiting -> Inefficient

---

1. 세마포어 : 에츠허르 데이크스트라가 고안한, 두 개의 원자적 함수로 조작되는 정수 변수로서, 멀티프로그래밍 환경에서 공유 자원에 대한 접근을 제한하는 방법으로 사용