1. Bounded-Buffer Problem
buffer - 임시로 데이터 저장하는 공간
⇒ shared data 환경 + 크기가 유한한 환경에서 생산자-소비자 문제 발생
생산자는 버퍼에 데이터를 생성하여 집어넣고
소비자는 버퍼에서 데이터를 가져가는 역할
발생 가능한 문제 상황)
여러 생산자가 동시에 비어있는 공유 버퍼에 데이터 집어넣으려고 할 때/여러 소비자가 동시에 빼가려고할 때
생산자와 소비자는 동시에 공유 버퍼에 접근하지 못하도록 Lock/unlock 사용
: 다른 프로세스들이 접근하지 못하게 lock , 끝나면 unlock
유한한 버퍼 =>
버퍼가 가득 찬 상태에서 생산자가 데이터를 집어넣으려고 할 때,
버퍼가 빈 상태에서 소비자가 꺼내가려고 할 때
세마포어(Semaphore)를 사용하여 버퍼의 상태 추적
- 버퍼가 가득 차있다면 생산자는 세마포어를 통해 대기
- 버퍼가 비어있다면 소비자는 세마포어를 통해 대기
세마포어
생산자가 데이터를 생성하여 버퍼에 집어넣을 때:
세마포어 변수를 사용하여 비어있는 버퍼의 개수를 나타내는 값을 1 감소 (P 연산).
소비자가 버퍼에서 데이터를 가져갈 때:
세마포어 변수를 사용하여 내용이 들어있는 버퍼의 개수를 나타내는 값을 1 증가 (V 연산).
세마포어를 사용하여 버퍼의 상태를 추적하면서, 생산자와 소비자는 세마포어 연산을 통해 동기화!
mutex)
상호 배제를 위해 사용되는 이진 세마포어(binary semaphore)
두 개의 상태 (0과 1) - 0은 잠금(lock) 상태, 1은 잠금 해제(unlock) 상태
생산자의 동작:
- P 연산을 사용하여 empty 버퍼가 있는지 확인.
- 만약 empty 버퍼가 없다면 (0인 경우), 대기
- P 연산을 사용하여 empty 버퍼가 있다면 mutex 값을 0으로 만들고 임계 구역(critical section)에 진입
이렇게 함으로써 다른 생산자가 버퍼에 접근하지 못하게 lock - 버퍼에 데이터를 입력
- V 연산을 사용하여 mutex 값을 1로 만듦.
다른 생산자가 버퍼에 접근할 수 있도록 unlcok. - V 연산을 사용하여 full 버퍼를 1 증가시키고 임계 구역에서 나옴
소비자의 동작:
- P 연산을 사용하여 full 버퍼가 있는지 확인
만약 full 버퍼가 없다면 (0인 경우), 대기
P 연산을 사용하여 full 버퍼가 있다면 mutex 값을 0으로 만들고 임계 구역에 진입(lock) - 버퍼에서 데이터를 가져갑니다.
- V 연산을 사용하여 mutex 값을 1로 만듦(unlock)
- V 연산을 사용하여 empty 버퍼를 1 증가시키고 임계 구역에서 나옴
2. Readers and Writers Problem
- 한 프로세스가 DB에 write 중일 때 다른 프로세스가 접근하면 안 된다.
- read는 동시에 여러 명이 해도 되는 상황
해결 방법)
Writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기 중인 Reader들을 다 DB에 접근 가능
Writer는 대기 중인 Reader가 하나도 없을 때 DB 접근이 허용
일단 Writer가 DB에 접근 중이면 Reader들은 접근이 금지
Writer가 DB에서 빠져 나가야만 Reader의 접근이 허용
Reader 프로세스
- P(mutex)를 통해 readCount 상호 배제 처리 => 동시에 readCount에 접근 방지
- 아무도 read 작업 X , 현재 read 작업을 실행하려는 프로세스가 나 혼자라면,
공통 데이터베이스에 lock을 걸어서 Writer의 접근을 막음 : P(db)- V 연산을 통해 임계 구역에서 빠져나옴.
- 원하는 만큼 데이터베이스를 읽음.
- read 작업을 마치고 데이터베이스 접근을 종료한 후,
- 다른 Reader들 readCount 접근 방지 위해 P 연산을 사용하여 상호 배제: P(mutex)
- 마지막으로 read 작업을 그만두고 나가려는 프로세스가 나 혼자라면,
공통 데이터베이스의 lock을 해제 V(db) => writer 접근 가능하도록- V 연산을 통해 임계 구역에서 빠져나와 다른 reader들이 접근 가능하도록 함
Writer 프로세스
- P 연산을 통해 공통 데이터베이스에 lock이 걸려있는지 확인 => 세마포어 값을 확인
만약 lock이 걸려 있지 않다면, 공통 데이터베이스에 lock을 걸고 임계 구역에 진입- 쓰기 작업 수행
- V 연산을 통해 공통 데이터베이스의 lock을 해제. 임계 구역에서 빠져나옴
동시에 도착한 Reader와 Writer에 대해서는
Reader가 우선권을 가지고 읽기 작업을 진행할 수 있어야 함.
하지만 이로 인해 Writer는 오랜 시간 동안 접근을 기다려야 할 수 있어 Starvation 문제 발생 가능 => 우선순위 큐 방식
3. Dining-Philosophers Problem
해결하려면?
상호 배제 (Mutual Exclusion): 젓가락은 한 번에 한 철학자만 사용할 수 있어야 함.
다른 철학자가 이미 젓가락을 사용 중인 경우, 대기해야 함.
교착 상태 방지 (Deadlock Avoidance): 철학자가 젓가락을 기다리면서 무한히 대기하는 교착 상태를 방지해야 함
기아 상태 방지 (Starvation Avoidance): 모든 철학자가 공평하게 식사할 수 있어야 함.
어떤 철학자가 항상 다른 철학자들보다 우선순위를 가지는 상황을 방지해야 함.
앞의 solution의 문제점
- Deadlock 가능성
- 모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버린 경우 - 무한 대기 상태
해결 방안
- 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다.
한 명의 철학자는 식사를 하지 않는 상태로 남게끔 조정- 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.
하나의 젓가락만 사용 가능한 경우, 철학자는 다른 철학자가 해당 젓가락을 사용할 때까지 기다리도록- 비대칭
- 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록
→ 하나의 젓가락이 우선순위가 높아서 순환 대기 상태를 방지 가능
- State 배열: 철학자들의 상태(thinking, hungry, eating)
- self : 각 철학자가 젓가락 2개를 모두 들 수 있는지 여부를 판단하기 위한 세마포어
초기값은 0으로 설정. 젓가락을 들 수 있는 상태가 되면 1로 변경 - mutex 세마포어: state 배열에 대한 상호 배제를 위해 사용 - 동시 접근 막음
pickup 함수: 철학자가 젓가락을 집기 위한 동작을 수행
mutex 세마포어로 state 배열의 상호 배제를 구현
- 한 번에 한 철학자만이 state 배열을 변경할 수 있도록 설정
그 후, 철학자의 상태를 hungry로 변경,
test 함수를 호출 현재 철학자가 젓가락 들 수 있는지 상태인지 확인(if 조건) ->
가능하다면 식사를 시작(state를 eating) - V(self[i])
그렇지 않다면 self[i] 세마포어로 젓가락을 기다리는 상태 전환. P(self[i])
putdown 함수: 철학자가 식사를 마치고 젓가락을 내려놓는 동작을 수행
mutex 세마포어로 state 배열의 상호 배제를 구현
철학자의 상태를 thinking으로 변경 후,
test를 통해 양 옆의 철학자들의 상태를 확인하여 식사 가능한 상태인지 검사
가능하다면 해당 철학자에게 self[i] 세마포어를 통해 식사를 시작하게 함.
V(mutex) 연산을 통해 임계 구역을 탈출
test 함수: 철학자가 젓가락을 들 수 있는지 확인하는 동작을 수행
왼쪽과 오른쪽 젓가락이 사용되지 않고,
자신의 상태가 hungry인 경우에만 식사를 시작.
self[i] 세마포어를 통해 젓가락을 들 수 있는 상태로 변경 - V(self[i])
Monitor
세마포어의 문제점
코딩하기 힘들다.
정확성의 입증이 어렵다.
자발적 협력이 필요하다.
한 번의 실수가 모든 시스템에 치명적인 영향을 끼친다.
올바른 상호 배제를 위해 P(mutex)를 임계 영역에 진입하기 전에 호출하고, V(mutex)를 임계 영역을 벗어날 때 호출해야 함.
모니터: 프로그래밍 언어 차원에서 동기화 문제를 해결할 수 있는 고수준 동기화 도구
공유 데이터에 접근하기 위해서는
모니터에 정의된 프로시저를 통해서만 접근 가능하다.
다른 프로세스는 해당 모니터에 진입할 수 있는 권한이 없음.
대기 중인 프로세스들은 모니터의 entry queue에서 순서대로 대기,
모니터에 진입할 수 있는 시점은
현재 모니터 내부에서 활동 중인 프로세스가 모니터를 빠져나간 후
- 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능
- 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요 없음
- 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable 사용
- condition variable: 프로세스의 동작을 제어하기 위해 사용
wait 연산:
자원이 없어서 조건이 충족되지 않을 경우 프로세스를 잠들게 함
다른 프로세스가 signal 연산을 호출하기 전까지 기다림.
즉, 조건을 충족하지 못한 상태에서 대기 상태
signal 연산:
모니터에 접근하고 빠져나갈 때 signal 연산을 호출
signal 연산은 정확히 하나의 잠들어 있는 프로세스를 깨우는 것.
잠들어 있는 프로세스가 없을 경우 아무 일도 일어나지 않음.
signal 연산을 통해 대기 중인 프로세스들이 조건을 충족하고 모니터에 접근
- produce 함수: 버퍼에 값을 추가하는 역할
만약 빈 버퍼가 없다면(there is no empty buffer),
프로세스는 empty 조건 변수의 wait 연산을 호출하여 잠들도록.
값을 버퍼에 추가한 후 full 조건 변수에 신호를 보냄
- consume 함수: 버퍼에서 값을 소비하는 역할
만약 버퍼가 비어있다면(full 버퍼가 없다.),
프로세스는 full 조건 변수의 wait 연산을 호출하여 잠들게 됨
값을 버퍼에서 꺼내고 소비한 후 empty 조건 변수에 신호를 보냄
상태 변수(state): 철학자들의 상태 관리
조건 변수(condition): wait, signal 등의 동작 수행
-
철학자가 식사 시작을 위해 "pickup" 프로시저 호출
철학자 상태 변경 (hungry)및 주변 철학자 상태 검사(test)
식사 시작이 불가능하면 wait 큐에서 대기
식사 가능 상태가 되면, eating 상태 변경. 조건 변수에서 깨어남 signal() -
식사가 끝난 후 "putdown" 프로시저 호출
철학자 상태 변경(thinking) 및 주변 철학자 상태 검사
test() 함수를 통해 식사가 가능한지 판단
주변 철학자가 식사 가능 상태가 되면 깨움 signal() -
"test" 프로시저: 철학자의 상태를 확인하고, 식사가 가능한지 여부를 판단
주변 철학자들이 식사 중이지 않고, 현재 철학자가 배고픈 상태인 경우 식사 시작
해당 철학자의 조건 변수를 사용하여 깨운다. signal()
