[OS] Synchronization II

동기화의 고전 문제 3가지

1. Bounded-Buffer Problem 
2. Readers and Wrtiers Problem
3. Dining Philosophers Problem

 

Bounded-Buffer Problem (생상자-소비자 문제)

• N개의 Item을 저장할 수 있는 버퍼(Buffer)에 여러 생산자(Producer)와 소비자(Consumer)가 접근
• 생산자(Producer): 하나의 Item을 생산해 Buffer에 저장
  • Race Condition
    • 공유 데이터에 대해 여러 Process가 동시에 접근, 변경을 시도하는 상황
    • = 한 Buffer에 대해 여러 Producer가 동시에 item을 추가하려는 상황
•  소비자(Consumer): Buffer에서 하나의 Item을 가져옴
  • 동작 조건: Buffer의 상태가 Empty면 대기
• 요약: 크기가 고정된(Bounded) 창고(Buffer)를 사이에 두고, 데이터를 넣는 사람과 쓰는 사람이 서로 꼬이지 않고, 넘치거나 부족하지 않게 조율하는 문제

한 생산자가 buffer에 접근할 때, 다른 생산자나 소비자가 buffer에 접근하지 못하도록 함

 

Bounded-Buffer Problem 구현

• Buffer의 구현
  • 1차원 배열로 구현
  • boolean buffer[n]; 으로 선언
  • 초기화
    • buffer[0 ... n-1] = empty;
• 생산자 Operation
  • Buffer 배열 중, empty인 index를 찾아 full로 바꿈
  • buffer[m] = full;
• 소비자 Operation
  • Buffer 배열 중, full인 index를 찾아 empty로 바꿈
  • buffer[m] = empty;

 

Bounded-Buffer Problem 해결을 위한 세마포어

• 세마포어를 사용하여 동기화를 관리

문제 해결을 위한 세마포어

세마포어	역할	초기값
Empty	버퍼 내에 저장할 공간이 있음을 표시 (생산자 진입 관리)	n (버퍼의 크기)
Full	버퍼 내에 소비할 아이템이 있음을 표시 (소비자 진입 관리)	0
Mutex	버퍼 접근 관리 (버퍼 상태값 변경을 위한 Mutual Exclusion)	1

• empty(버퍼 내 저장할 수 있는 공간)가 0이 아니라면 empty를 깎으며 입장
• critical section에 들어가기 위해 mutex가 풀릴 때까지 대기
  • 결국 critical section에서는 동기화가 확실하게 이루어짐
• Data 수정
• critical sectino에서 빠져 나와 mutex 풀어줌
• full을 증가 시켜 버퍼에 아이템이 하나 추가 되었다는 것을 알림

• full(소비할 아이템)이 0이 아니라면 full을 깎으며 입장
• mutex 대기 및 획득
• Data 수정
• critical section에서 빠져 나와 mutex 풀어줌
• empty 증가시켜 버퍼에 아이템이 하나 추가 되었다는 것을 알림

 

Readers-Writers Problem(독자-저자 문제)

• 여러 독자(Readers)와 저자(Writers)가 하나의 공유 데이터에 접근하는 문제
• Readers: 공유 데이터를 읽기만 함
  • 여러 Reader는 동시에 데이터에 접근하여 읽기 가능
• Writers: 공유 데이터에 쓰기(수정)를 함
  • Writer가 데이터를 수정하기 위해서는, Reader 혹은 Writer가 작업을 하고 있지 않아야 함

 

• 문제 해결을 위한 자료구조와 세마포어
  • int Readcount: 버퍼에 현재 몇 개의 Reader가 접근 중인지 표시
  • Semaphore Wrt: Writers 사이의 동기화 관리
  • Semaphore Mutex: Readcount와 Wrt에 접근이 원자적으로 수행됨을 보장하기 위한 세마포어
• 초기값
  • Mutex = 1
  • wrt = 1
  • Readcount = 0
• Writer 입장에서 reader에게 우선 순위를 주면 starvation 문제 발생

Writer

reader

 

문제점

• Writer의 Starvation
  • readcount==0 일 때만 V(wrt)가 수행되어 p(wrt)로 대기하고 있던 Writer가 수행할 수 있음
  • 첫 번째 Reader(readcount==1)가 P(wrt)만 통과하면, 다른 Reader들은 P(mutex)만 기다리면 언제든지 수행할 수 있기 때문에 Writer와 상관없이 진입할 수 있음
  • 여러 Reader 들이 계속해서 진입할 경우, readcount는 0까지 않고, Writer는 진입하지 못함
• Writer의 Starvation을 예방하는 Solution
  • Writer process에 우선순위를 부여

Writer에 우선순위를 부여하여 Starvation 해결

• writecount 변수 생성
  • Writer도 자신의 숫자를 셈
• S2 세마포어 추가
  • Writer들이 writecount 변수를 공유하기 때문에, 이 변수에 동시 접근을 막기 위해 S2(Mutex) 추가
  • Reader 쪽의 S1과 같은 역할
• rd 세마포어의 역할 변화 (핵심)
  • rd는 Reader들이 들어오는 출입문 역할을 하며 Writer가 이를 잠글 수 있게 됨
  • Reader Priority(기존): Writer는 Reader가 읽고 있으면 무조건 기다리며 Reader가 계속 들어오면 Writer는 Starvation에 빠짐
  • Writer Priority(Solution)
    1. 첫 번째 Writer(if writecount == 1)가 도착하면 wait(rd)를 통해 Reader들의 출입문인 rd를 잠가버림
    2. 새로운 Reader들은 wait(rd)에 막혀서 진입 불가
    3. 현재 읽고 있던 Reader들이 다 빠져나가면, Writer가 작업 시작
    4. 마지막 Writer(if writecount == 0)가 작업을 마치고 나갈 때, signal(rd)를 통해 다시 출입문을 열어줌
• wrtpending 세마포어 추가
  • reader들이 우르르 rd를 점유하러 가지 않고, 1명씩 wait(rd)를 하게끔 하여 writer와 1:1 경쟁을 하게 만들어줌
  • wrtpending이 없다면 10개의 reader가 wait(rd)를 한다고 가정하면, writer는 10:1로 경쟁해야 함 
• 완벽한 solution은 아니지만 기존 코드보다 starvation을 어느 정도 해결
• starvation을 해결하지만 부하는 늘어남 (trade-off)
• Writer가 계속해서 들어와서 writecount가 0이 되지 않으면 Reader가 Starvation에 빠질 수도 있음(Writer 우선 코드)

 

Dining-Philosophers Problem

• 고전적인 병행성(Concurency) 문제로 5명의 철학자가 원형 식탁에 앉아 식사를 하는 상황
• 젓가락이 5개뿐
  • 자신의 바로 옆 젓가락만 집을 수 있음
  • 두 젓가락을 모두 집어야 식사를 할 수 있음
  • 식사를 하고 난 다음에야 두 젓가락을 모두 내려놓을 수 있음
• Deadlock과 Starvation이 발생하는 경우
  • 모두 자신의 오른쪽 젓가락을 집었을 경우

 

Solution 1: 단순 동기화 시도 및 Deadlock

• 각 젓가락을 세마포어로 관리
• 단순히 젓가락을 집는 것에 대한 동기화 부여
  • 모든 철학자가 자신의 왼쪽 또는 오른쪽 젓가락부터 집도록 함
  • boolean waiting[n];
• 초기값은 모두 1

철학자 식사 로직

Starvation(2가 2번 식사), Deadlock(최종적으로 모두 대기) 발생

 

Dining-Philosophers Problem 개선안

• Deadlock의 해결 방안
  • 한 번에 최대 4명의 철학자만 식탁에 앉도록 함 >> 자원 때문에 사용자 수를 줄여버림
  • 젓가락의 상태를 미리 검사하여, 양 쪽의 젓가락을 모두 사용 가능할 때만 젓가락을 집도록 함
  • 철학자에게 번호를 부여하여 홀수인 철학자는 왼쪽의 젓가락을, 짝수는 오른쪽을 먼저 집도록 함
• 위의 해결방안들은 Starvation까지 해결해주지는 못함
  • 각각의 방안에 대해 Starvation에 대한 고려를 추가할 수 있음
  • ex) 한 차례 굶은 철학자에게 우선권을 줌
    
    
• 양 쪽의 젓가락을 한꺼번에 집는 방법
  • 젓가락의 상태를 미리 검사하여 양쪽의 젓가락이 모두 사용할 때만 젓가락을 집도록 하는 방법
  • 사용되는 자료구조
    • State[5]: 각 철학자의 상태를 기록(THINKING, HUNGRY, EATING)
  • 문제 해결을 위한 세마포어
    • mutex: 젓가락을 집거나 놓는 수행을 Critical Section으로 관리하기 위한 세마포어
      • 초기값: 1
    • Self[5]: 철학자 각각이 젓가락 두 개를 잡기를 기다리는 세마포어
      • 초기값: 모든 원소가 0
      • Self[i]: 철학자 i가 HUNGRY 상태이더라도, 다른 젓가락 하나를 사용할 수 없을 경우 Waiting을 하기 위한 세마포어

철학자 식사 로직

take & put chohpsticks 로직

test(int i) 로직

• test에서 철학자 i의 좌우 젓가락이 사용 가능할 때만 Critical Section에 진입함
  • i-1(LEFT)와 i+1(RIGHT) 철학자가 EATING 상태가 아니어야 함
• tes() 함수 안에서 조건이 만족하여 V(self[i])로 self[i]가 1이 되면 V(mutex)로 mutex를 풀어준 뒤, P(self[i])를 통과하여 식사를 진행함
• test()함수를 통과하지 못한 철학자들은 P(self[i])에서 대기하다가 다른 철학자가 test(LEFT)나 test(RIGHT)를 통해 test()를 해주고, 먹을 수 있는 상태라면 V(self[i])를 수행하게 되므로 동기화에 문제가 없음

 

동기화 체크 요소

• Data Consistency(일관성)가 확보되는지
• Deadlock이 발생하는지
• Starvation 가능성이 있는지
• Concurrency(동시성)를 얼마나 제공하는지
• 성능이 올라가려면 HW core 수를 늘리거나 SW process나 thread를 증가시켜야 함
  • 이때 consistency(일관성)가 깨질 수 있으므로 동기화가 필수적으로 요구됨