SW solution

Dekker's Algorithm

사진출처 - https://youtu.be/lY43KR3IItw

• 프로세스가 두 개일 때 mutual exclusion을 보장하는 최초의 알고리즘

Peterson's Algorithm

사진 출처 - https://youtu.be/lY43KR3IItw

• 플래그를 드는 것은 같지만 양보를 함

N-Process Mutual Exclusion

• 다익스트라 Dijkstra
  • 최초로 프로세스 n개의 상호배제 문제를 소프트웨어적으로 해결
  • 실행 시간이 가장 짧은 프로세서 할당하는 세마포 방법, 가장 짧은 평균 대기시간 제공

사진 출처 - https://youtu.be/lY43KR3IItw

• want-in : 프로세스가 critical section에 들어가기 위한 첫번째 단계, 들어가고 싶은 의사를 밝히는 단계
• in-CS : 프로세스에 들어가기 직전의 단계

SW solution

• SW Solution들의 문제점
  • 속도가 느림
  • 구현이 복잡한
  • ME primitive 실행 중 preemption 될 수 있음
    • 공유 데이터 수정 중은 interrupt를 억제함으로서 해결 가능
      • Overhead 발생
  • Busy waiting
    • Inefficient

C 언어를 몰라서 잘 이해가 안간다..

HW solution

Synchronization Hardware

• TestAndSet (TAS) instruction
  • Test와 Set을 한번에 수행하는 기계어
  • Machine instruction
    • Atomicity, Indivisible
    • 실행 중 interrupt를 받지 않는 것이 보장된다. (preemption 되지 않음)
  • Busy waiting
    • Inefficient

사진 출처 - https://youtu.be/Zps0ckSvKys

• 한번에 수행된다.
• target이라는 인자를 받는다.
• target의 값을 temp에 넣고 target을 true로 만든다.

사진 출처 - https://youtu.be/Zps0ckSvKys

사진 출처 - https://youtu.be/Zps0ckSvKys

HW Solution

• 장점
  • 구현이 간단
• 단점
  • Busy waiting
    • Inefficient
• Busy waiting 문제를 해소한 상호배제 기법
  • Semaphore
    • 대부분의 OS들이 사용하는 기법

OS supported SW solution

Spinlock

• 정수형 변수
• 초기화,P(), V() 연산으로만 접근 가능
  • 위 연산들은 indivisible (or atomic) 연산
    • OS support
    • 전체가 한 instruction cycle에 수행 됨

사진 출처 - https://youtu.be/33OqgesF-mM

• 멀티 프로세서 시스템에서만 사용 가능
• Busy waiting!

Semaphore

• 1965년 Dijkstra가 제안
• Busy waiting 문제 해결
• 음이 아닌 정수형 변수 (S)
  • 초기화 연산, P(), V()로만 접근 가능
    • P: Probern (검사)
    • V: Verhogen (증가)
• 임의의 S 변수 하나에 ready queue 하나가 할당 됨
• Binary semaphore
  • S가 0과 1 두 종류의 값만 갖는 경우
  • 상호배제나 프로세스 동기화의 목적으로 사용
• Counting semaphore
  • S가 0 이상의 정수값을 가질 수 있는 경우
  • Producer-Consumer 문제 등을 해결하기 위해 사용
    • 생산자-소비자 문제
• 초기화 연산
  • S 변수에 초기값을 부여하는 연산
• P(), V() 연산
• 모두 indivisible 연산
  • OS support
  • 전체가 한 instruction cycle에 수행 됨

Semaphore로 해결 가능한 동기화 문제들

• 상호배제 문제
  • Mutual exclusion
• 프로세스 동기화 문제
  • process synchronization problem
    • process들의 실행 순서 맞추기
      • 프로세스들은 병행적이며, 비동기적으로 수행
• 생산자-소비자 문제
  • producer-consumer problem
    • 생산자(Producer) 프로세스
      • 메시지를 생성하는 프로세스 그룹
    • 소비자(Consumer) 프로세스
      • 메시지 전달받는 프로세스 그룹
• Reader-writer 문제
• Dining philosopher problem
• 기타

<참고>

• https://youtu.be/lY43KR3IItw
• https://youtu.be/Zps0ckSvKys
• https://youtu.be/33OqgesF-mM