협력적 프로세스: 시스템 내에서 실행 중인 다른 프로세스의 실행에 영향을 주거나 받는 프로세스
race condition
동시에 여러 개의 프로세스가 동일한 자료를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황
the critical section problem
entry section
임계구역에 진입하는 허가를 요청하는 코드
critical section
이 안에서 다른 프로세서와 공유하는 데이터에 접근하고 갱신할 수 있다.
exit
임계구역을 나가면서 자료 조정
remainder
코드의 나머지 구역
mutual exclusion
프로세스가 자기의 임계구역에서 실행된다면, 다른 프로세스는 자신의 임계구역에서 실행될 수 없다.
progress
avoid deadlock
bounded waiting
avoid starvation
커널 코드(운영체제를 구현하는 코드)는 경쟁 조건이 발생하기 쉽다.
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형의 변수를 정의할 수있다. condition x,y x.wait(), x.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 문제
- writer가 접근 허가를 받지 못했다면 reader는 기다리지 않고 접근
- 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처럼 동작
함수형 언어
