[운영체제] 07. Synchronization Examples

Classical Problems of Synchoronization

• Bounded-Buffer Problem
• Readers and Writers Problem
• Dining-Philosophers Problem

Bounded-Buffer Problem

원형 버퍼 문제

한줄 요약 : 생산자와 소비자가 고정 크기의 버퍼를 안전하게 공유하며 오버플로우나 언더플로우를 방지하는 고전적인 동기화 문제

• 버퍼의 개수가 N개 있다고 가정합니다.
  • 새 항목이 도착했습니다.
    • 비어 있는 버퍼가 있습니까? 채우십시오. 꽉 찬 버퍼를 만듭니다.
    • 그렇다면, 그러나...
      • 공유 변수(Shared variabe)를 지금 접근할 수 있습니까?
  • 소비자
    • 꽉 찬 버퍼가 존재합니까? 가져가십시오. 비어 있는 버퍼를 만듭니다.
    • 그렇다면, 그러나...
      • 공유 변수를 지금 접근할 수 있습니까?
  • 공유 변수: 버퍼
  • 리소스 카운트:
    • 꽉 찬 버퍼(N_full-buf)
    • 비어 있는 버퍼(N_empty-buf)
  • 공유 변수 접근에는 바이너리 세마포어가 필요합니다.
  • 리소스 카운트에는 카운팅 세마포어가 필요합니다.

 

• 생산자 : 버퍼가 비어 있습니까?
  • item을 버퍼에 삽입합니다. (임계 구역, critical section)
• 소비자 : 버퍼가 가득 찼습니까?
  • item을 버퍼에서 삭제합니다. (임계 구역)
• 필요한 세마포어
  • S_mutex: 버퍼 풀 접근을 위한 mutual exclusion(상호 배제), 초기값 1.
  • N_empty-buf: 비어 있는 버퍼의 수, 초기값 N.
  • N_full-buf: 꽉 찬 버퍼의 수, 초기값 0.
    •  

 

참고)

1. P (Proberen): 세마포어 값을 1 감소시키는 연산입니다. 값이 0 이상인 경우 바로 감소시키고, 값이 음수인 경우 세마포어 값이 양수가 될 때까지 대기합니다.
2. V (Verhogen): 세마포어 값을 1 증가시키는 연산입니다. 값이 0 이상인 경우 바로 증가시키고, 값이 음수인 경우 대기 중인 스레드 중 하나를 깨웁니다.

생산자 (Producer)

1. 항목을 생산합니다:
   • 생산자는 새로운 항목을 생산합니다.
2. P(N_empty-buf):
   • 생산자는 버퍼에 빈 공간이 있는지 확인하기 위해 빈 버퍼의 세마포어(N_empty-buf)를 기다립니다. 빈 버퍼가 하나 이상 있을 때까지 대기합니다.
3. P(S_mutex):
   • 생산자는 버퍼에 접근하기 위해 상호 배제 세마포어(S_mutex)를 기다립니다. 이는 버퍼에 접근하는 동안 다른 프로세스가 버퍼에 접근하지 못하게 합니다.
4. 항목을 버퍼에 삽입합니다:
   • 생산자는 생산한 항목을 버퍼에 삽입합니다.
5. V(S_mutex):
   • 생산자는 상호 배제 세마포어(S_mutex)를 해제하여 다른 프로세스가 버퍼에 접근할 수 있도록 합니다.
6. V(N_full-buf):
   • 생산자는 꽉 찬 버퍼의 세마포어(N_full-buf)를 증가시켜 버퍼에 새로운 항목이 있음을 나타냅니다.
7. ...:
   • 생산자는 이 과정을 반복합니다.

소비자 (Consumer)

1. ...:
   • 소비자는 반복적인 작업을 수행합니다.
2. P(N_full-buf):
   • 소비자는 버퍼에 항목이 있는지 확인하기 위해 꽉 찬 버퍼의 세마포어(N_full-buf)를 기다립니다. 버퍼에 항목이 하나 이상 있을 때까지 대기합니다.
3. P(S_mutex):
   • 소비자는 버퍼에 접근하기 위해 상호 배제 세마포어(S_mutex)를 기다립니다. 이는 버퍼에 접근하는 동안 다른 프로세스가 버퍼에 접근하지 못하게 합니다.
4. 항목을 버퍼에서 삭제합니다:
   • 소비자는 버퍼에서 항목을 삭제합니다.
5. V(S_mutex):
   • 소비자는 상호 배제 세마포어(S_mutex)를 해제하여 다른 프로세스가 버퍼에 접근할 수 있도록 합니다.
6. V(N_empty-buf):
   • 소비자는 빈 버퍼의 세마포어(N_empty-buf)를 증가시켜 버퍼에 빈 공간이 있음을 나타냅니다.
7. 항목을 소비합니다:
   • 소비자는 버퍼에서 삭제한 항목을 소비합니다.

이 구조는 생산자와 소비자가 동시에 버퍼를 효율적으로 사용할 수 있도록 하며, 데이터의 손실이나 동시 접근으로 인한 문제를 방지합니다.

---

Readers-Writers Problem

읽기-쓰기 문제

• 데이터 세트가 여러 동시 프로세스에 의해 공유됩니다.
  • 읽기 프로세스 - 데이터 세트를 읽기만 합니다.
  • 쓰기 프로세스 - 데이터 세트를 읽고 씁니다.
• 문제점
  • 여러 읽기 프로세스가 동시에 읽을 수 있습니다.
  • 단 하나의 쓰기 프로세스만이 동시에 공유 데이터를 접근할 수 있습니다.
• 공유 데이터
  • 데이터 세트
  • integer readcount: 읽기 프로세스의 수.
  • semaphore mutex: readcount 접근을 위한 상호 배제.
  • semaphore wrt: 쓰기 프로세스를 위한 상호 배제.

 

• 쓰기 프로세스와 읽기 프로세스의 구조
  • 세마포어 mutex = 1, wrt = 1;
  • 정수 readcount = 0; 
    • •  

 

쓰기 프로세스 (Writer)

1. while (true):
   • 쓰기 프로세스는 계속 반복합니다.
2. P(wrt):
   • 쓰기 프로세스는 쓰기 세마포어(wrt)를 기다립니다. 이것은 현재 데이터에 다른 쓰기 또는 읽기 작업이 진행 중이지 않은 경우에만 통과됩니다.
3. // writing is performed:
   • 쓰기 작업이 수행됩니다. 공유 데이터에 대해 쓰기 작업을 합니다.
4. V(wrt):
   • 쓰기 작업이 끝나면 쓰기 세마포어(wrt)를 해제하여 다른 쓰기 또는 읽기 작업이 진행될 수 있도록 합니다.

읽기 프로세스 (Reader)

1. while (true):
   • 읽기 프로세스는 계속 반복합니다.
2. P(mutex):
   • 읽기 프로세스는 뮤텍스(mutex)를 기다립니다. 이것은 readcount에 접근하는 동안 다른 프로세스가 접근하지 못하게 합니다.
3. readcount++:
   • 읽기 프로세스는 readcount를 증가시킵니다. 이는 현재 읽기 프로세스의 수를 나타냅니다.
4. if (readcount == 1):
   • readcount가 1이면(첫 번째 읽기 프로세스가 들어옴) 쓰기 세마포어(wrt)를 기다립니다. 이는 쓰기 작업이 진행 중인 경우를 방지합니다.
     • readcount가 1이 되는 순간, 즉 첫 번째 읽기 프로세스가 데이터에 접근할 때, 쓰기 세마포어(wrt)를 획득하여 쓰기 프로세스가 데이터에 접근하지 못하게 합니다. 이는 여러 읽기 프로세스가 동시에 데이터를 읽을 수 있도록 허용하면서도 쓰기 프로세스가 데이터에 접근하는 것을 막아 데이터의 무결성을 유지합니다.
5. V(mutex):
   • 읽기 프로세스는 뮤텍스(mutex)를 해제하여 다른 프로세스가 readcount에 접근할 수 있도록 합니다.
6. // reading is performed:
   • 읽기 작업이 수행됩니다. 공유 데이터에 대해 읽기 작업을 합니다.
7. P(mutex):
   • 읽기 프로세스는 뮤텍스(mutex)를 다시 기다립니다. 이는 readcount에 접근하는 동안 다른 프로세스가 접근하지 못하게 합니다.
8. readcount--:
   • 읽기 프로세스는 readcount를 감소시킵니다. 이는 현재 읽기 프로세스의 수를 나타냅니다.
9. if (readcount == 0):
   • readcount가 0이면(마지막 읽기 프로세스가 나감) 쓰기 세마포어(wrt)를 해제합니다. 이는 쓰기 작업이 다시 시작될 수 있도록 합니다.
     • readcount가 0이 되면, 즉 마지막 읽기 프로세스가 데이터를 다 읽고 나가면, 쓰기 세마포어(wrt)를 해제하여 대기 중인 쓰기 프로세스가 데이터에 접근할 수 있게 합니다. 이는 쓰기 작업이 독점적으로 데이터를 쓸 수 있도록 보장합니다.
10. V(mutex):
    • 읽기 프로세스는 뮤텍스(mutex)를 해제하여 다른 프로세스가 readcount에 접근할 수 있도록 합니다.

 

쓰기 프로세스는 쓰기 세마포어를 기다렸다가 사용하고 쓰게 세마포어를 해제해주면 되지만,

 

읽기 프로세스는 1.1 readcount에 접근을 위해 mutex를 기다림1.2 readcount==1이면 쓰기 세마포어 기다림1.3 mutex 해제2.1 readcount에 접근을 위해 mutex를 기다림2.2 readcount==0이면 쓰기 세마포어 해제2.3 mutex 해제

 

요런 구조를 가지고 있다.

---

Dining-Philosophers Problem

식사하는 철학자 문제

• 다섯 명의 철학자가 생각하고 식사하고 있습니다.
  • 식사하려면 두 개의 젓가락을 들어야 합니다.
• 철학자 i의 구조
  • 밥 그릇 (데이터 세트)
  • 세마포어 젓가락[5]의 초기값은 1입니다. 

ex) 왼쪽 젓가락을 가지고 있고, 오른쪽 젓가락을 기다림

• Deadlock이 발생할 수 있다. (일어나지 않을 일을 무한정 기다림)

---

Linux Synchronization

리눅스 동기화

• 리눅스 제공 기능
  • 세마포어(semaphores)
    • 차단 및 깨우기(block&wakeup)
    • 긴 시간 동안의 잠금(lock)에 사용됩니다.
  • 스핀락(spinlocks)
    • 바쁜 대기(busy waiting)
    • 짧은 시간 동안의 잠금(lock)에 사용됩니다.
• 상황에 따른 사용
  • 다중 프로세서에서
    • 스핀락 Acquire/release
  • 단일 프로세서에서
    • 커널 선점(kernel preemption) 비활성화/활성화.