고전적인 동기화 문제
- 많은 클래스의 병행 제어(concurrency control) 문제에 대한 것
- 해당 문제들로 새로운 동기화 방법을 검증할 수 있음
유한 버퍼 문제(The Bounded-Buffer Problem)
- 해당 문제는 동기화 프리미티브(primitive)들의 능력을 설명하기 위해 사용
프리미티브 : 프로그래밍 관점에서 해석
- 이용 가능한 가장 작은 processing의 단위
- 언어에서 표현의 원자 요소
- 예 : 덧셈, 뺄셈 → 가장 단순하기 때문에 primitive operation라고 함
소비자와 생산자가 공유하는 자료구조
int n; // n개의 버퍼로 구성된 풀(pool)
semaphore mutex = 1; // 상호배제 기능 제공
semaphore emtpy = n; // 비어 있는 버퍼의 수
semaphore full = 0; // 꽉찬 버퍼의 수
int n : n개의 버퍼로 구성된 pool
- 각 버퍼는 한 항목(item)을 저장할 수 있다고 가정
semaphore mutex : 풀에 접근하기 위한 세마포어
- 이진 세마포이기 때문에 상호 배제 기능 제공
- 1로 초기화됨
semaphore empty : 비어 있는 버퍼의 수
- 처음에는 모든 n개의 버퍼가 비어있다. → n로 초기화
semaphore full : 꽉 찬 버퍼의 수
- 처음에는 채워져 있는 버퍼가 없다 → 0으로 초기화
생산자와 소비자의 프로세스 구조
/* 생산자 프로세스의 구조 */
while(true){
...
// next_produced에 아이템을 생산
...
wait(empty); // empty 세마포가 하나라도 있어야함
wait(mutex);
...
// 생산된 아이템(next_produced)을 버퍼에 추가
...
signal(mutex);
signal(full);
}
/* 소비자 프로세스의 구조 */
while(true){
wait(full); // full 세마포가 하나라도 있어야함
wait(mutex);
...
// 버퍼에서 next_consumed으로 아이템을 제거(옮김)
...
signal(mutex);
signal(empty);
...
// next_consumed 안에 있는 아이템을 소비
...
}
- 생산자와 소비 코드 간의 대칭성이 존재
- 생산자는 소비자를 위해 꽉 찬 버퍼를 생산
- 소비자는 생산자를 위해 비어 있는 버퍼를 생산
Readers-Writers 문제
Readers와 Writers의 정의와 관계
- 가정 : 하나의 데이터베이스가 병행 프로세스 간에 공유되는 상황
readers : 데이터베이스의 내용을 읽는 것만을 원하는 프로세스들writers : 데이터베이스의 내용을 쓰는 것(읽기 포함)을 원하는 프로세스들
- readers 프로세스 여러 개가 동시에 공유데이터에 접근 → 문제 발생 X
- 하나의 writer 프로세스와 다른 스레드가 동시에 공유 데이터에 접근 → 문제 발생 O
- 여기서 다른 스레드 → 다른 reader 혹은 writer 프로세스를 뜻함
- 이러한 문제가 발생하지 않도록 보장해야 함
readers-writers 문제 : writer가 쓰기 작업동안 공유 데이터에 대한 배타적 접근 권한을 갖게 하는 것
- 배타적 접근 권한 : 동시에 한 명만 사용할 수 있는 권한
- 이러한 문제는 거의 모든 새로운 동기화 프리미티브(primitive)를 시험하기 위해 사용
Readers-writers 문제 방식
- 2가지 방법을 제시 → 모두 우선순위와 연관된 방식들
기아 상태(Starvation) : 특정 프로세스의 우선순위가 낮아서 원하는 자원을 계속 할당받지 못하는 상태
- writer가 공유 객체를 사용할 수 있는 허가가 없다면, 어떤 readers도 기다릴 수 없다.
- 가장 간단한 방식
- 우선순위 : readers > writers
- writer가 기다리고 있기 때문에, 다른 reader들은 writer가 끝날 때까지 기다리면 안 된다.
- writer가 기아 상태에 빠질 수 있다.
- 일단 writer가 준비되면, 최대한 빨리 쓰기를 수행할 것을 요구
- writer가 객체에 접근하려고 기다리고 있다면, 새로운 reader들은 읽기를 시작하지 못함
- reader가 기아 상태에 빠질 수 있다.
- 우선순위 : writers > readers
1번 방식에서 발생하는 기아 상태의 해결책
semaphore rw_mutex = 1; : 이진 세마포
- 해당 세마포는 reader와 writer가 모두 공유
- 사용하는 방식
- writer들을 위한 상호 배제 세마포
- 임계구역에 진입하는 첫 번째 reader와, 임계구역을 빠져나오는 마지막 reader에 의해 사용
- But, 다른 reader들이 임계구역 안에 있는 동안,
임계구역을 드나드는 readers는 해당 세마포를 사용하지 않음
semaphore mutex = 1; : 이진 세마포
- read_count를 갱신할 때 상호 배제를 보장하기 위해 사용
- 1로 초기화됨
- reader 프로세스들이 공유하는 자료구조
int read_count = 0; : 현재 객체를 읽고 있는 프로세스의 개수
/* Writer 프로세스의 구조 */
while(true){
// writer을 위한 이진 세마포 rw_mutex 획득 될때까지 기다림
wait(rw_mutex);
// rw_mutex를 얻으면 쓰기 수행
...
/* 쓰기 수행 */
...
signal(rw_mutex); // rw_mutex를 깨워, 다른 프로세스 수행
}
/* Reader 프로세스의 구조 */
while(true){
wait(mutex); // read_count 상호 배제를 위해 mutex 기다림
// 키를 얻은 경우
read_count++; // 객체를 읽을 것이기 때문에 read_count + 1
// 1개의 reader만 임계구역에 들어가기 위해 read_count 체크
// read_count == 1 은 rw_mutex에 들어갈 프로세스(readers에서 가장 첫번째)
if(read_count == 1)
wait(rw_mutex); // writer와의 상호 배제를 위해 rw_mutex 기다림
signal(mutex); // mutex락을 방출하여 다음 reader 프로세스 수행
...
/* 읽기 수행 */
...
wait(mutex); // 읽기 수행 후, read_count에 접근하기 위해 mutex 락을 기다림
read_count--; // 임계 구역 밖으로 빠져나왔기 때문에 read_count-1;
// 임계 구역에 reader 프로세스가 하나도 없는 경우
// 즉, mutex 큐에 대기 중인 reader 프로세스들이 없는 경우
// readers를 다 써야 writers를 쓸 수 있음
if(read_count == 0)
signal(rw_mutex); // rw_mutex를 깨워 다음 writer를 깨움
signal(mutex); // read_count 임계구역 탈출
- 가정 : writer가 임계구역에 있고 n개의 reader가 기다리고 있는 상황
- 1개의 reader만 rw_mutex와 관련된 큐에 삽입
→ 나머지 n-1개의 reader들은 mutex와 관련된 큐에 삽입됨
- writer가
signal(rw_mutex) 수행 시
- 대기 중인 여러 개의 readers 혹은 1개의 writer의 수행이 재개됨
reader-writer 락(lock)
- Readers-writers 문제와 해결안들은 일반화되어 몇몇 시스템에서는 read-writer 락 제공
- Reader-writer 락을 획득할 때
- 읽기(read)인지 또는 쓰기(write)인지 모드를 지정해야 함
- 예시
- 프로세스가 공유 데이터를 읽기만 원하는 경우 → 읽기 모드의 reader-writer 락 요청
- 프로세스가 공유 데이터의 수정을 원하는 경우 → 쓰기 모드의 reader-writer 락 요청
- 읽기 모드의 reader-writer 락은 여러 개의 프로세스에서 동시 획득 가능
- 쓰기 모드의 reader-writer 락은 오직 하나의 프로세스만이 획득 가능
← Writer는 공유 데이터를 배타적으로 접근해야 하기 때문
- Reader-writer 락이 유용한 상황
- 공유 데이터를 읽기만 하는 프로세스와 쓰기만 하는 스레드가 식별하기 쉬운 응용
- Writer보다 reader의 개수가 더 많은 응용
- reader-writer 락을 설정하는데 드는 오버헤드가 세마포나 상호 배제 락보다 큼
→ 동시에 여러 reader가 읽게 하여 병형생을 높임으로써 오버헤드 상쇄 가능