Deadlock

• Mutual Exclusion: 접근 제한. 자원이 유한한 사용자와만 공유 가능
• No preemption: 자원 할당 → 다시 회수 X
• Hold and Wait: 여러 독립적 요청. 현재 자원을 잡고 있는 동안 다음 자원을 사용하기까지는 대기 필요
  
• Circular wait: 요청 그래프가 원형 형태일 때 데드락 발생할 수 있음.

데드락 방지

• 그래프 내 사이클 X → 데드락 X
• 그래프 내 사이클 O → 리소스 당 인스턴스만 있다면 데드락 발생. 그렇지 않으면 데드락 발생 가능성.
• 자원 요청 그래프 → partial ordering을 통해 방지 가능
  
• lock을 거는/얻는 순서를 명시함으로써 데드락을 방지하자는 의도 → 동시에 실행될 경우 데드락이 일어날 수도 있다는 위험

Order relation

1. Paritial Order: 집합 P 모든 원소 a, b, c에 대해 모든 조건 만족
2. Total order: 모든 S 소속 원소에 대해서 binary relation 구성 가능

Bounded Buffer Problem

• 버퍼 사이즈가 N으로 정해져 있는 문제. 동시에 생산자/소비자가 접근할 때 동기화를 제공해주어야 함
• 생산자: 한 번에 하나의 아이템을 생산, 버퍼에 저장. 버퍼가 가득 찼다면 대기
• 소비자: 버퍼에서 하나의 아이템을 소비. 버퍼가 비었다면 대기
• 생산자 ↔️ 소비자 충돌 X: 버퍼(Critical Section) 접근 가능
• 세마포어: (1). Empty (2). Full (3). Mutex - 버퍼 접근 관리. 생산자, 소비자가 empty, full 세마포 진입할 경우 버퍼 상태 값을 변경하기 위한 용도
• 세마포어 초깃값: (1). Empty: 버퍼에 empty인 엔트리 N개 (2). Full: 0 (3). Mutex: 1

1. 생산자 프로세스

• mutex를 Critical Section 진입 전/후에 사용

2. 소비자 프로세스

• 시그널을 통해 현재 버퍼에 아이템이 존재하는지, 빈 상태인지 체크

시그널, Mutex를 통해 생산자와 소비자가 자신의 상태를 서로에게 알려준다!

• 네트워크 상 패킷이 전달되는 과정을 이해할 때 Bounded Buffer Problem은 매우 중요: NIC이 패킷을 받을 때 버퍼에 패킷을 수신 → 커널이 NIC의 패킷을 소비, 메모리에 저장 → 유저가 커널에 저장된 패킷을 복사

동기화 알고리즘 구현 방법

1. 동기화 문제 서술
2. 세마포어 디자인(개수, 제어 상황)
3. 알고리즘 구현을 통한 데드락 고려
4. 초깃값과 Starvation 고려

Readers Writers Problem

• 저장 장치에 필요한 동기화 문제
• 여러 Reader, 여러 Writer가 하나의 공유 데이터에 접근하는 방법
• 읽기: 동시 읽기는 상관 X, 현재 쓰고 있다면 어떤 시점의 데이터를 읽어야 하는지 확인
• 쓰기: 동시 쓰기 상관 O.

Solution1

• readcount, semaphore wrt, semaphore mutex 자료구조 사용
• writer 동기화, readcount/wrt 접근 원자적으로 수행하기 위한 세마포어
  
  

읽는 건 많이 읽어도 된다. 하지만 쓰고 있다면, 읽을 수 없다!

Writer's Starvation

• Readcount가 0일 때에만 writer에게 시그널을 주고, wait로 대기하고 있던 writer가 수행할 수 있음. 첫 번째 reader가 wait를 통과하면 다른 reader들은 wait에 대한 signal만 통과하면 writer에 관계없이 진입 가능. 즉 여러 reader들이 진입할 경우 readcount는 0까지 떨어지지 않을 수 있다.

Solution2

• Writer의 수행이 시작될 때부터 reader의 진입을 막는 방법
• 이미 수행 중인 Reader 연산이 끝나면 Writer 수행 시작

Reader 진입으로 인한 Starvation을 막기에 적합한 솔루션! 하지만 계속해서 쓴다면... 역시 Starvation.

• readcount, semaphore wrt(writer들 간의 동기화 관리), semaphore read(reader들 진입 관리) semaphore Rmutex, Wmutex 자료구조 사용

Writer process

• Entry Section: wait(read) 수행함으로써 reader가 계속해서 진입하는 것을 방지. 진입한 reader들이 읽기를 마치면 writer 작업 수행
• Exit Section: signal(read)를 수행함으로써 reader들이 다시 진입할 수 있도록 함. writercount가 0으로 내려가지 않고 계속해서 writer가 쓰기 작업을 하려 한다면 reader의 startvation 문제.

Reader process

• Entry Section: 첫 부분에서 wait, signal 번갈아가면서 수행. 여러 개의 reader가 동시에 존재 가능. writer가 wait 수행하게 되면 signal이 수행하지 않기 때문에 reader 진입은 중단
• Exit Section: Reader가 진입을 하지 않기 때문에 readcount가 0이 되면 공유 데이터에 아무 reader, writer도 없다는 게 보장이 됨. signal을 통해 writer가 진입할 수 있도록 보장

Reader's Starvation

• Reader가 초깃값을 이용해 먼저 진입: reader가 연속해서 진입하다가 write 수행을 위해 wait에서 대기하면 signal(read) 하나가 writer의 wait를 풀게 된다. 이때 이미 진입한 reader가 모두 수행을 마치면 해당 writer가 수행되고, 다시 다음 writer로 수행이 넘어가면서 reader는 진입할 수 없게 된다.
• Writer가 초깃값을 이용해 먼저 진입: writer가 작업을 시작, 계속해서 writer 수행이 허용되기 때문에 signal read는 수행되지 않는다. 따라서 reader는 starvation 상태에 빠진다.

Writer의 Starvation은 해결했지만 정반대의 일 일어난다!

Soluton3

• 동기화 해결: Reader, Writer 모두 분리
• 특정 작업 수행 중에서 다른 Writer, Reader가 대기하는 구역에서 기다리는 수를 알 수 있다. 대기 중인 작업 여부를 확인해 Bounded Waiting을 해결한다.
• Writer: Writer는 어떤 작업이 수행되거나 대기 중인 Reader, Writer가 있다면 Writer가 허용될 때까지 대기. 그렇지 않으면 Write 가능. Write 수행되면 대기 중인 Reader는 모두 수행 가능. 대기 중인 Reader 없고 대기 중인 Writer 있다면 Write 수행.
• Reader: Writer가 대기 중이거나 Write 중이라면 대기. Reader 모두 수행되면 대기하고 있던 Writer 하나 수행