🎛️ 운영체제 - 6. Process Synchronization

출처 : http://www.kocw.net/home/cview.do?lid=af8e05c97c6d60de

---

🎛️ 데이터의 접근 

---

🎛️ Race Condition

---

🎛️ OS에서의  Race Condition

< OS에서  Race Condition이 발생하는 경우 >

1. kernel 수행 중 인터럽트 발생 시
2. Process가 system call을 하여 kernel mode로 수행 중인데 context switch가 일어나는 경우
3. Multi processor에서 shared memory 내의 kernel data

1. kernel 수행 중 인터럽트 발생 시

커널 모드에서 인터럽트가 발생하면 인터럽트 핸들러가 실행되면서 카운터 값을 변경하고 이때 Race Condition이 발생

 

2. Process가 system call을 하여 kernel mode로 수행 중인데 context switch가 일어나는 경우

시스템 콜(system call)이 실행되면 커널 주소 공간의 데이터를 공유하게 되는데, 이때 선점이 발생하면서 문제 Race Condition이 발생

 

3. Multi processor에서 shared memory 내의 kernel data

CPU가 커널 모드로 들어갈 때 데이터에 대한 접근이 동시에 발생하면 Race Condition이 발생

 

+ 이를 방지하기 위해 락(lock)과 언락(unlock)을 사용

---

🎛️ Process Synchronization 문제

공유 데이터 (shared data)의 동시 접근(concurrent access)은 데이터의 불일치 문제(inconsistency)를 발생

일관성(consistency) 유지를 위해서는 협력 프로세스(cooperating process)간의 실행 순서(orderly execution)를 정
해주는 메커니즘 필요

Race condition
- 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
- 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에따라 달라짐

race condition을 막기 위해서는 concurrent process는 동기화(synchronize)되어야 함

---

🎛️The Critical-Section Problem

임계구역 문제 ( 임계구역 : 공유 데이터를 접근하기 원하는 코드 부분)

 

< n 개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우>

- 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재

=> 하나의 프로세스가 critical section 에 있을때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 함!

---

🎛️ 프로그램적 해결법의 충족 조건

Mutual Excluion
- 프로세스 Pi 가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안 됨

 

Progress
- 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 함

 

Bounded Waiting
- 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 함

가정
- 모든 프로세스의 수행 속도는 0보다 큼
- 프로세스들 간의 상대적인 수행 속도는 가정하지 않음

---

🎛️ 프로세스 동기화와 상호배제(mutual exclusion)에 관한 문제 해결을 위한 다양한 알고리즘

• 알고리즘 1:
  • int turn 변수를 사용하여 두 프로세스가 서로의 차례를 지키며 크리티컬 섹션에 들어갈 수 있도록 함
  • 이는 상호배제는 만족하지만 진행률(progress requirement)을 만족하지 않을 수 있다는 단점이 있음
• 알고리즘 2:
  • 알고리즘 2는 boolean flag[2] 변수를 사용
  • 각 프로세스는 플래그를 통해 크리티컬 섹션에 들어갈지 여부를 결정하며, 이는 상호배제는 만족하지만 여전히 진행률 문제가 발생할 수 있음
• 알고리즘 3 (피터슨 알고리즘):
  • 알고리즘 1과 2를 결합하여 상호배제, 진행률, 그리고 제한된 리소스를 사용하는 문제를 모두 해결
  • 플래그와 turn 변수를 사용하여 두 프로세스 간의 충돌을 방지하며, 특정 프로세스가 계속 대기(busy waiting)하는 것을 막음

---

🎛️ Semaphore

• Semaphore Implementation (P() and V()):
  • P(S)는 세마포어의 값을 감소, 값이 0 이하인 경우 프로세스를 블럭
  • V(S)는 세마포어의 값을 증가시켜 블럭된 프로세스를 깨움

---

🎛️ Block/wakeup

• Busy-wait vs. Block/wakeup:
  • Busy-wait는 프로세스가 계속해서 자원을 점
  • Block/wakeup은 필요할 때만 자원을 사용하도록 설계되어 효율적
  • 크리티컬 섹션이 짧은 경우 Busy-wait가, 긴 경우 Block/wakeup이 더 적합

---

🎛️ Semaphore 의 classical problems

동기화 문제들은 운영체제와 멀티스레딩 환경에서 자주 발생하는 이슈

이를 해결하기 위해 다양한 동기화 기법과 세마포어, 뮤텍스 등이 사용

교착 상태와 기아를 방지하고 효율적인 프로세스 동기화를 위해 사용

 

 

Bounded-Buffer 문제(Producer-Consumer 문제):

- 프로듀서가 데이터를 생성하고 컨슈머가 데이터를 소비하는데, 버퍼의 한계로 인해 발생할 수 있는 동기화 문제

 

프로듀서는 데이터가 비어있는 버퍼에 추가하고, 컨슈머는 데이터가 있는 버퍼에서 가져감

-> 빈 버퍼 또는 꽉 찬 버퍼에 대한 처리가 필요

 

세마포어와 뮤텍스(mutex)를 사용하여 상호배제와 동기화를 관리

empty, full, mutex 세마포어는 버퍼의 상태를 나타내며, mutex는 상호배제를 유지하기 위해 사용

 

 

Readers and Writers 문제:

- 데이터베이스나 파일과 같은 공유 리소스에 대해 여러 프로세스가 읽기(read)와 쓰기(write) 작업을 동시에 수행하려고 할 때 발생할 수 있는 동기화 문제

 

여러 프로세스가 동시에 읽기 작업을 수행할 수 있지만, 쓰기 작업은 하나의 프로세스만 가능해야 함

-> Readers와 Writers 간의 동기화를 유지하면서 동시에 다수의 프로세스가 리소스에 접근하는 것을 관리

 

뮤텍스(mutex)를 사용하여 상호배제를 보장하고, readcount와 db 변수를 사용하여 동기화를 관리

readcount는 현재 읽기 작업을 수행 중인 프로세스의 수를 나타내며, db는 쓰기 작업을 위한 뮤텍스 역할을 함

 

+ starvation가 발생할 수 있음

 

 

Dining-Philosophers 문제:

아무도 밥을 먹을 수 없는(deadlock) 철학자 식탁

 

chopstick이라는 세마포어를 사용합니다. 각 세마포어는 젓가락을 나타내며, 값이 1일 때 접근할 수 있음

철학자들은 식사하기 전에 각자의 양쪽에 있는 젓가락을 들어야 함

철학자가 젓가락을 들면 세마포어 값을 감소시키고, 식사를 마치면 세마포어 값을 증가

 

deadlock(교착 상태) 방지:

철학자 중 4명만이 동시에 젓가락을 들 수 있게 하거나,

젓가락을 두 개 다 들지 못할 경우에 하나만 들 수 있게 하는 방법 

짝수 철학자만이 오른쪽 젓가락부터 들도록 하는 방법

등

---

하.,..

7. deadlock 까지 공부했단말입니다.

왜...6까지 시험범위인겁니까

교수님 강계엔 7까지였지않습니까...

좋은데..

화납니다