동기화의 고전적인 문제 3가지
Bounded-Buffer problem(버퍼가 한정적)
- starvation, Deadlock 둘다 없음
생산자(하나의 아이템을 생산해 버퍼에 저장)
- Race Condition
공유 데이터에 대해 여러 프로세스가 동시 변경, 접근을 시도할때 락을 걸어
소비자(버퍼에서 하나의 아이템을 가져옴)
세마포어 관점
Empty
- 생산자의 경우 버퍼 내에 저장할 공간이 있나 표시
Full
- 소비자의 경우 버퍼 내에 아이템이 있나 표시.
Mutex
- 버퍼자체에 대한 락을 걸어줌
- 여러 생산자가 동시에 값을 쓰거나, 값이 반영되지 않았는데 가져가거나 방지.
하나의 생산자 소비자만 접근할 수 있도록함
Readers and Writers problem
Readers(공유 데이터를 읽음)
- 앞에서의 소비자는 꺼내서 썼지만, 얘는 그냥 읽기만함.
- 여러 Reader는 동시에 공유 데이터를 읽을 수있음
- Reader가 읽을때 Writer는 접근 불가
Writers(공유 데이터를 씀)
- Writer가 데이터를 수정하기 위해서는 Reader 나 Writer가 작업 안해야함
해결방안
Int Readcount
- 몇개의 리더가 접근중인지 개수셈
(writer 할때 모든 Reader 블락해야함으로 개수 알아야해)
세마포어 Wrt
- Writer 들 사이의 동기화를 관리하기 위함
세마포어 Mutex
- Readcount와 wrt 라는 공유 세마포어에 대해서 한번에 하나의 프로세스만 접근이 가능하도록 감시용 세마포어를 둠
Readers and Writers 문제점
Writer의 Starvation
- Readcount ==0 일때만 V(wrt)가 수행되어 P(wrt) 로 대기중인 Writer가 수행될 수 있음
- 여러 Reader들이 계속해서 진입할 경우 Readcount는 0까지 안떨어져서 Writer가 접근하지 못하게됨
Dining Philosophers problem
- 모든 철학자(프로세스)가 자신의 오른쪽 젓가락(접근해야하는 자원)을 집었을 경우 => 데드락과 starvation 모두 발생
솔루션 1
단순히 젓가락을 집는 것에 대한 동기화를 부여하는 방법
- 모든 철학자가 자신의 왼쪽 또는 오른쪽 젓가락부터 집게 한다
데드락 해결방안
- 한번에 최대 4명의 철학자만 식탁에 앉도록 한다. 철학자 한명 뻄
- 양쪽의 젓가락이 모두 사용 가능할때만 젓가락을 집도록함.
- 번호를 부여해 홀수인 철학자는 왼쪽을, 짝수인 철학자는 오른쪽 젓가락을 집는다. => 모두 오른쪽 잡아서 생기는 Deadlock 방지
데드락은 해결되지만, Starvation은 해결되지 않음
=> 한 차례 굶은 철학자에게 우선권을 주는 방안도 생각해야함
솔루션 2
- 핵심: 왼쪽 친구와 오른쪽 친구가 먹고 있지 않을 때 Critical Section에 진입함
- 식사를 마치면, 좌우 철학자한테 test() 함수 실행시켜서 대기중인(wait()) 옆에 애들 배고프면 쓰라고 함.
양 쪽의 젓가락을 한번에 집는 방법 구현
- 젓가락 상태를 미리 검사해 양쪽 젓가락이 모두 사용 가능할때만 집음
사용되는 자료구조
- 철학자의 상태(Thinking,Hungry, Eating) 을 기록해 starvation 방지
세마포어
- mutex: 젓가락을 집거나 놓는 수행들을 Critical 섹션으로 관리하기 위한 세마포어. =>젓가락을 동시에 잡는(context switching) 이 발생하는걸 방지.
체크할 내용들
Data Consistency(일관성)가 확보되었는지
데드락이 발생하는지
Starvation의 가능성이 있는지
기존에는 공유데이터에 대해 접근을 하는데만 급급함...
이를 다 만족된다면
Concurrency(병렬성)를 얼마나 제공하는지
- 공유데이터에 접근하는 프로세스들을 최대한 얼마나 동시에 수행할 수 있게 해줄건지.
=> Reader들의 성능을 향상시킬 수 있음