synchronization tool

공유 자원

• 프로세스 혹은 스레드가 공유하는 자원
  임계구역 critical section
• 동시에 실행 했을때 문제가 발생할 수 있는 코드
  - entry section: 임계 구역 진입 허가 코드
  - exit: 임계구역을 나가며 자료 조정
  - remainder: 코드의 나머지 구역

progress: avoid deadlock
bounded waiting: avoid starvation

race condition

• 동시에 여러 개의 프로세스가 동일한 자료에 접근하여 조작할 때, 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황
  - 커널 코드는 경쟁 조건이 발생하기 쉬움

  스레드 안전: 동시 접근이 이루어져도 실행에 문제가 없는 상태

동기화

• 실행 순서 제어: 프로세스 및 스레드를 올바른 순서로 실행
• 상호 배제: 동시에 접근하면 안 되는 자원에 하나의 프로세스 및 스레드만 접근

Peterson's Solution
현대 컴퓨터 구조가 load, store 같은 기본 기계어를 수행하는 방식 때문에 이러한 구조에서 올바르게 실행된다고 보장할 수는 없다

int turn 
Boolean flag[2]  
flag[i]=true, turn=j;
// flag[i]는 임계구역으로 진입할 준비가 됐다. 
// turn은 프로세스가 임계구역에서 실행 될 수 있다.

Hardware support for synchronization
Memory Barriers: 메모리의 변경 사항을 다른 모든 프로세서로 전파하는 명령어를 제공

• 다른 프로세서에서 실행 중인 스레드에 메모리 변경사항이 보이는 것을 보장

memory model

• 컴퓨터 아키텍처가 응용 프로그램에게 제공하는 메모리 접근 시 보장되는 사항을 결정한 방식
• 강한 순서: 한 프로세서의 메모리 변경 결과가 다른 프로세서에 즉시 보임
• 약한 순서: 한 프로세서의 메모리 변경 결과가 다른 프로세서에 즉시 보이지 않음

Hardware instruction: 한 워드의 내용을 검사하고 변경하거나, 두 워드의 내용을 원자적으로 교환할 수 있는 명령어, test_and_set, compare_and_swap

Atomic variables: 정수, 부울 등 기본 데이터 유형에 대한 원자적 연산을 제공한다. 상호 배제 보장 카운터 및 시퀀스 생성기와 같은 공유 데이터 한 개의 갱신에만 제한되는 경우가 많다.

Mutex Lock: 임계구역에 들어가기전에 acquire(), 빠져나올 때 release(). 바쁜 대기
위 유형을 spin lock 이라고도 한다.

semaphores: wait()-P, signal()-S, 바쁜대기

• 사용 가능한 자원의 개수를 나타내는 변수 존재
  - 이진 세마포 mutex lock 과 유사하다. 0과 1만 가능, 어떤 시스템에서는 mutex락 대신 쓴다.
  - 카운팅 세마포: 사용 가능한 자원 만큼 접근 가능
• 바쁜 대기 대신 세마포 값이 양수가 아닐 때 일시 중지 시키고 wait큐로 보낸다.
• signal을통해 프로세스를 wait에서 ready 큐로 옮긴다.

  SMP 시스템에서 원자적으로 실행하는 것을 보장하기 위해, CAS, spin lock 등 다른 기법 제공
  발견하기 어려운 타이밍 오류를 야기할 수 있다.

monitor: 모니터 형은 내부에서 상호배제가 보장되는 프로그래머가 정리한 일련의 연산자 집합을 포함한 ADT

• 조건 변수: 실행 순서 제어에 사용
  - condition x,y x.wait(), x.signal()
• wait/signal: 상호 배제

Signal and wait: p는 q가 모니터를 떠날 때 까지 기다리거나 다른 조건을 기다린다.
Signal and continue :Q는 P가 모니터를 떠날 때 까지 기다리거나 다른 조건을 기다린다.
Liveness:프로세스가 실행 수명 주기 동안 진행되는 것을 보장하기 위해 시스템이 충족해야 하는 일련의 속성
Priority Inversion: L, M, H. H가 필요한 세마포 S를 L이 쓰고 있고. M이 L을 선점했다면 H는 M이 끝나고 L이 끝나길 기다려야 한다.
priority-inheritance protocol: 더 높은 우선순위의 프로세스가 필요로 하는 자원을 가진 프로세스는 자원을 다 쓸 때 까지 더 높은 우선 순위를 갖는다.

synchronization example

The Bounded-Buffer Problem
n개의 버퍼로 구성된 pool, 각 버퍼는 한 아이템만 저장한다.
mutex 이진 세마포는 버퍼 풀에 접근하기 위한상호 배제 기능을 제공하며 1로 초기화된다.
empty와 full 세마포는 각각 비어 있는 버퍼의 수와 꽉 찬 버퍼의 수를 기록한다.
int n semaphore mutex=1, empty=n, full=0;

Readers-Writers 문제

1. writer가 접근 허가를 받지 못했다면 reader는 기다리지 않고 접근
2. writer는 기다리지 않고 쓴다. reader는 writer가 객체에 접근하려고 기다리고 있으면 읽기를 시작하지 못한다.

Read-Write Lock: 락을 획득할 때 읽기인지 쓰기인지 모드 지정.
공유 데이터를 읽기만 하는 프로세스와 쓰기만 하는 스레드를 식별하기 쉬운 응용
Writer 보다 Reader의 개수가 많은 응용

The Dining Philosophers Problem
각 젓가락을 세마포로 표현
최대 n-1 명의 철학자만을 테이블에 동시에 않도록 한다.
두 젓가락을 모두 집을 수 있을 때만 집도록 허용한다.
odd: left 먼저, even: right 먼저 집게 한다.
모니터: 양쪽을 집을 수 있을 때만 집기
enum{Thinking, Hungry, Eating} state[n]
(state[(i+n-1)%n] != Eating) &&(state[(i+1)%n] != Eating)

대체방안
Transaction Memory: 메모리 읽기와 쓰기 연산의 원자적인 연속적 순서
한 트랜잭션의 모든 연산이 완수되면 메모리 트랜잭션은 확정된다. 그렇지 않으면 모든 연산 취소 후 roll-back
Open MP: 어플리케이션 개발자가 경쟁조건을 발견해야 한다. mutex lock처럼 동작
함수형 언어