Chapter 7: Synchronization Examples

이 글은 고려대학교 김민호 교수님의 운영체제강의를 토대로 작성한 글입니다.
This post is based on the operating system lecture by Prof. Minhoe Kim of Korea University.

 
#7.Synchronizaition Examples

 
 

❖ 생산자 - 소비자 문제 (다중)
     • n개의 버퍼가 있으며 각 버퍼는 하나의 아이템을 저장할 수 있습니다.
     • 세마포어 'mutex'는 초기 값 1로 초기화됩니다.
     • 세마포어 'full'은 채워진 슬롯의 수를 나타내며, 초기 값은 0입니다.
     • 세마포어 'empty'는 빈 슬롯의 수를 나타내며, 초기 값은 n입니다.
 
❖ 스케줄링 제약 조건
     • 생산자는 버퍼가 가득 차 있으면 생산할 수 없습니다 → 'empty > 0' 인지 확인합니다.
     • 소비자는 버퍼가 비어 있으면 소비할 수 없습니다  → 'full > 0' 인지 확인합니다.

 
생산자 프로세스의 구조
 • 임계 영역에 진입
 • 버퍼가 가득 찼는지 확인
 • 임계 영역을 벗어남
 • 하나의 아이템이 생성됨
 

 
소비자 프로세스의 구조
 • 임계 영역에 진입
 • 버퍼가 비어 있는지 확인
 • 임계 영역을 벗어남
 • 하나의 아이템이 소비됨
 
 

Readers-Writer Problem

❖ 데이터 집합이 여러 동시 프로세스 간에 공유됩니다.
     • Readers: 데이터 집합을 읽기만 하며, 업데이트는 수행하지 않습니다.
     • Writers: 데이터 집합을 읽고 쓸 수 있습니다.
 
❖ 문제 정의
     • 여러 Readers가 동시에 읽을 수 있도록 허용해야 합니다.
     • 단일 작가만이 동시에 공유 데이터를 액세스 할 수 있어야 합니다.
 
❖ 공유 데이터
     • 데이터 집합
     • 세마포어 'rw_mutex'는 1로 초기화
     • 세마포어 'mutex'는 1로 초기화
     • 정수형 변수 'read_count' 는 0으로 초기화

Reader Process 동작 설명
1. Reader가 읽기를 시작할 때, 'mutex' 세마포어를 사용하여 'read_count'를 증가시킵니다.
2. 첫 번째 Reader가 읽기를 시작할 때 'rw_mutex'를 획득하여 Writer 가 쓰는 것을 방지합니다.
3. 'read_count'를 업데이트한 후 'mutex' 세마포어를 해제합니다.
4. Reader가 읽기를 마치면, 'mutex' 세마포어를 사용하여 'read_count'를 감소시킵니다.
5. 마지막 Reader가 읽기를 종료할 때 'rw_mutex'를 해제하여 작가가 쓸 수 있도록 합니다.

문제의 변형

❖ 기본 Readers-Writers 문제의 변형에서는 다음과 같은 요구사항이 추가됩니다:
     • Writer가 준비되면 가능한 한 빨리 작성을 수행해야 합니다.
     • Writer가 객체에 접근하기 위해 기다리고 있는 경우, 새로운 Reader는 읽기를 시작할 수 없습니다.
     • 이로 인해 Readers이 Starve 상태에 빠질 수 있습니다.
 

❖ Dining-Philosophers Problem 문제 설명:
     • 철학자들은 평생 동안 생각과 식사를 번갈아가며 생활합니다.
     • 철학자들은 이웃과 상호작용하지 않으며, 가끔씩 식사를 하기 위해 두 개의 가까운 젓가락을 집어 들려고 시도합니다. (젓가락은 5개)
     • 식사를 하기 위해서는 양쪽 젓가락이 모두 필요하며, 식사를 마치면 두 젓가락을 모두 내려놓습니다.
 
❖ 교착 상태(deadlock) 및 기아 상태(starvation)이 없이 어떻게 문제를 구현해야할까?

5명의 철학자에 대한 알고리즘
공유 데이터
     • 밥그릇 (데이터 집합)
     • 5개의 세마포어 'chopstick[5] (각각 1로 초기화)
 
❖ 위의 알고리즘은 두 인접한 철학자가 동시에 식사하지 않도록 보장합니다. 그러나 교착 상태를 발생시킵니다.
     • 만약 다섯 명의 철학자가 동시에 배가 고파져서 각자 오른쪽 젓가락을 집으면, 모든 젓가락이 사용중이게 됩니다.
     • 각 철학자가 왼쪽 젓가락을 집으려고 할 때, 계속 기다리게 되어 교착 상태가 발생합니다.
 
 

철학자 문제에 대한 데드락 해결 방법
 
문제 상황:
철학자들이 동시에 배고파져서 각자 오른쪽 젓가락을 먼저 집으려고 할 때, 모든 젓가락이 점유되면 모든 철학자가 왼쪽 젓가락을 집을 수 없어 영원히 대기하는 상황(데드락)이 발생할 수 있습니다.
데드락 없는 해결 방법
 
1. 최대 네 명의 철학자만 동시에 앉도록 허용:
     • 테이블에 최대 네 명의 철학자만 앉아있도록 제한하면 데드락을 방지할 수 있습니다.
     • 최소 한 명의 철학자는 반드시 먹을 수 있게 되므로 데드락이 발생하지 않습니다.
2. 젓가락 두 개가 모두 사용 가능할 때만 집도록 허용:
     • 철학자는 두 개의 젓가락이 모두 사용 가능할 때만 젓가락을 집을 수 있습니다.
     • 이를 통해 한쪽 젓가락을 집고 다른 쪽 젓가락을 기다리는 상황을 방지할 수 있습니다.
3. 비대칭 솔루션:
     • 홀수 번호의 철학자는 왼쪽 젓가락을 먼저 집고, 짝수 번호의 철학자는 오른쪽 젓가락을 먼저 집도록 합니다.
     • 이렇게 하면 데드락이 발생하지 않습니다.

작동 원리

• pickup(int i): 철학자 i가 젓가락을 집으려고 할 때 호출됩니다. 먼저 해당 철학자의 상태를 HUNGRY로 설정하고, test(i)를 호출하여 젓가락을 집을 수 있는지 확인합니다. 만약 젓가락을 집을 수 없다면 self[i].wait()를 호출하여 기다립니다.
• putdown(int i): 철학자 i가 젓가락을 내려놓을 때 호출됩니다. 상태를 THINKING으로 변경하고, 왼쪽((i + 4) % 5)과 오른쪽((i + 1) % 5) 철학자가 젓가락을 집을 수 있는지 테스트합니다.
• test(int i): 철학자 i가 젓가락을 집을 수 있는지 테스트합니다. 왼쪽 철학자와 오른쪽 철학자가 모두 식사 중이 아니고 자신이 배고프다면, i의 상태를 EATING으로 변경하고 self[i].signal()을 호출하여 기다리고 있는 철학자를 깨웁니다.
• initialization_code(): 모든 철학자의 초기 상태를 THINKING으로 설정합니다.

조건

• 철학자 i가 젓가락을 집을 수 있는 조건은 다음과 같습니다:

이 모니터 솔루션은 교착 상태를 피하면서도 철학자들이 젓가락을 집고 식사할 수 있도록 합니다. 각 철학자는 자신의 상태에 따라 적절하게 행동하며, 다른 철학자와의 충돌을 피할 수 있습니다.
 
 
 
 
 
 

❖ 각 철학자 i 는 다음 순서로 'pickup()' 및 'putdown()' 연산을 호출합니다:
이 순서로 호출하면 데드락은 피할 수 있지만, 기아(starvation) 현상이 발생할 수 있습니다.