[OS] Synchronization Tools - part1

Background

---

• Cooperating process
  • share a logical address space → thread
  • share data → share memory or msg passing
• 프로세스가 동시에 돌아가며 데이터를 공유하려면?
  • 데이터의 일관성이 유지되야함
  • 실행 순서가 지켜져야 데이터가 유지된다
• 데이터의 값이 모호해지는 경우
  • Concurrent execution : 프로세스가 작동 중에 다른 프로세스에게 넘기는 경우
  • Parallel execution : 분리된 CPU에서 프로세스가 동시에 돌아가는 경우
• concurrently한 동작의 문제점(P-C모델의 비동기 상태)
  • 기계어 과정으로 생각하면, 위의 과정이 순서대로 일어나지 않는다 . context switch는 끝까지 기다리지 않는다.
  • 그렇기에 interrupt가 일어날 때, 값이 올바르게 수정되지 않는다.
• 

둘 이상의 입력의 타이밍이나 순서 등이 결과 값에 영향을 미치는 상황 → Race condition

Race Condition을 해결하는 것 → synchronization

 

The Critical Section Problem

---

'한 프로세스가 critical section으로 정의된 부분에 접근을했을 때, 다른 프로세스가 접근을 못하면 race-condition이 안일어나지 않을까' 에 대한 가정을하면 일어나는 것들

• 프로세스들이 동작 할 때 동기화 상태가 된다.
• 공유된 데이터가 cooperatively하게 된다.

Critical-section의 분류

• entry-section : critical-section의 입장 부분
• critical-section : 정의된 부분
• exit-section : 크리티컬 섹션이 반납되는 부분
• remainder-section : 나머지 부분

Critical-section 방법의 요구사항

• Mutual Exclusion : 한 프로세스가 크리티컬 섹션에 들어왔을 때, 접근을 못하게 해라
• Progress: avoid deadlock
• Bounded Waiting : avoid starvation

Single-core environment에서의 간단한 해결법

• 변수를 공유 하고 있는 동안 인터럽트를 막는다. → multiprocessor환경에서의 비효율성이 너무 크다.

Non-Preemptive & Preemptive

• Non-Preemptive : 경쟁 상태 문제가 잘 발생하지 않는다.
• Preemptive : 어려운 문제를 해결하더라도 반응성이 좋기에 선택하여 쓴다.

 

Peterson's Solution

---

• 피터슨 솔루션 이외에 Dekker's, Eisenberg and McGuire's, Bakery 알고리즘 등이 있다.
• flag를 중심으로 임계부분을 티키타카 하는 방식
• 제대로 동작한다는 보장이 없다.
• 하지만, 개념적으로 완벽하고, mutual exclusion, progress, bounded waiting의 요구사항을 전부 만족한다.

 

Hardware Support for Synchronization

---

Hardware instructions that provide

• 임계문제를 지원해준다.
• 하드웨어가 인스트럭션에 적용되면 직접적으로 동기화한다.
• 이 외 더 효율적인 방법이 있다.
  • memory barriers
  • hardware instruction
  • atomic variable

Atomic

• 더 이상 나눌 수 없는(인터럽트가 불가능한) 단위의 동작, 상호배제성 해결 중심
• Special hardware instruction을 만들기
  • 값을 체크 하고 바꿔주는 과정을 기계어 기준 3clock을 1clock으로 줄이면서 기존의 Context Switch가 중간에 안 일어나도록 방지한다. 즉, test and modify, test and swap 과정을 하나의 단위로 묶어버린다.
• Atomic Variable
  • 상호배제성을 위해 single variable에 race condition으로 만들자(ex count++, count—)