[ 이화여대 운영체제 - 반효경 교수님 강의 ]
프로세스 Race Condition과 해결책
공유 데이터를 건드리는 중요한 공간을 Critical section 이라고 한다.
이 section에서는 아래와 같이 lock을 걸고(entry section)/풀고(exit section)하는 작업이 필요하다.
Critical section 해결 조건
- Mutual Exclusion (상호 배제)
- 동시에 들어가면 안된다.
- Progress (진행)
- 아무도 들어가 있지 않은 상태에서, 누군가 들어가고자 하면 통과 시켜줘야 한다.
- Bounded Waiting (유한 대기)
- 대기시간은 유한해야 한다
- 한 프로세스만 들어가고 계~속 사용하고 있다면?
- A,B,C 모두 들어가고 싶은데 A,B만 들어간다면 ?
Algorithm 1
위 코드가 P0의 코드,
밑줄 친 turn={i}의 코드에서 0과 1이 바뀐 것을 P1이라고 가정
turn이라는 Synchronization variable을 두고,
critical section에 들어가기전에, 이번엔 누구 차례인지 알아낸다.
(너 한번, 나 한번)
하지만, 이 방법은 과잉양보이다.
내 차례가 오기 전까지 계속 기다려야하는데, 만약 특정 프로세스가 '더' 빈번히 critical section에 들어가야한다면?
근데 상대방은 아예 들어가지도 않는다면?
즉, 원하지도 않는데 번갈아 들어가야한다는 것이다.
Algorithm 2
깃발을 두어 누가 들어가고 싶은지 보는 방법이다.
자신의 깃발(flag[i])을 올리고,
상대방의 깃발(flag[j])를 확인한 뒤에 critical section에 들어간다.
동시에 들어가는 방법은 깃발을 통해 방지한다.
하지만 '진행'에 있어서 문제가 있다.
여러 프로세스가 사용하겠다고 서로 '깃발을 들고 있는 상태'에서 CPU를 뺏긴다면?
Algorithm 3 (Peterson's Algorithm)
위 두가지 방법을 합친 방법이다.
모든 조건을 만족하며 해결할 수 있다.
내 깃발을 들고, 상대방 깃발이 들려있는지 && 상대방 차례면 -> 기다림!
하지만 이것도 Busy Waiting(spin lock!)이라는 문제가 있다.
while을 빠져나갈려면 상대방이 turn을 줘야하는데, while때문에 CPU를 줄 수가 없다는 문제가 있다...
⬆️ 소프트웨어적으로 Process Synchronization 해결
⬇️ 하드웨어적으로 Process Synchronization 해결
Synchronization Hardware
critical section 접근 문제는 하드웨어적으로 Test & modify(set)을 atomic(쪼개지지 않고 한번에)하게 수행하면 해결할 수 있다.
- 하드웨어적으로 기능을 제공하기만 하면 문제는 해결된다.
- 크리티컬 섹션에 들어가기 전에 lock 건다
- lock이 0 이면 내가 lock 해서 1로 만들고 들어간다
Semaphore
- Critical Section으로 들어가기 위한 작업을 추상화 하는 것
- 추상 자료형
- object + operation
- 논리적으로 구성되는 것
- 변수는 정수값을 가질 수 있다.
사용 이유
- 공유 자원을 획득하고 반납
- p 연산 : lock 거는 과정 (자원 획득)
- v 연산 : lock 반납 (자원 반납)
- 정수형 변수 값 S : 자원의 개수
race condition 문제를 쉽게 해결할 수 있다.
상대방이 V연산을 하기 전에 자신은 P만 진행하기 때문에 busy-wait을 해야한다는 단점이 있다.
이를 해결하기 위해서 Block/Wakeup 방법을 사용하면 된다
Critical Section of n Process
- 프로그래머는 세마포어 방식을 사용하면 편리
- busy-wait 는 효율적이지 못함 (=spin lock)
- Block & Wake up 방식의 구현 (=sleep lock)
Block / Wakeup Implementation
Sepaphore를 정의하여, 큐를 사용해 대기 상태로 줄세운다.
락이 걸렸을 때 sleep을 하여 busy wait을 탈출하는 방법이다.
Implementation
Block/wakeup version of P() & V()
P
- S.value -> 자원이 없는 상태
- 자원이 생기면 block()이 생겨남
V
- S.value() <= 0
- 누군가가 자원을 기다리고 있다는 상황을 나타냄
Which is better ?
Busy-wait vs Block/wakeup
Block/wakeup
- CPU를 의미있게 효율적으로 이용 가능
Two Types of Semaphores
Counting semaphore
- 도메인이 0 이상인 임의의 정수값
- 주로 resource counting에 사용
Binary semaphore(=mutex)
- 0 또는 1 값만 가질 수 있는 semaphore
- 주로 mutual exclusion (lock/unlock)에 사용
Deadlock and Starvation
순서를 바꿔서 Deadlock 해결
Classical problems of Synchronization
1. Bounded-Buffer Problem (Producer-Consumer Problem)
여러 개의 프로세스를 어떻게 동기화할 것인가에 관한 고전적인 문제
이 문제를 해결하는 것을 생산자-소비자 협동이라 하며, 버퍼가 동기화 되어 정상적으로 동작하는 상태를 뜻한다. 이 문제를 해결하기 위해 세마포어를 활용할 수 있다.
프로세스
-
Producer (생산자)
-
Consumer
주황색 버퍼는 생산자가 데이터를 만들어서 집어놓은 상태임
아니면 이미 만들어놓은 버퍼를 소비자가 사용한 경우
생길 수 있는 문제
-
공유버퍼에 대해 lock 을 걸었다가 풀어야 함
-
생산자 소비자 문제
- 버퍼가 bounded 생산자가 한꺼번에 도착해서 버퍼를 다 채웠을 때, 소비자는 안 오고 생산자는 계속 버퍼를 만들고 싶다 -> 사용할 수 있는 자원이 부족
- 소비자가 가져가야지만 버퍼를 사용 가능
- 생산자는 빈 버퍼가 생길 때 까지 기다려야 한다.
- 버퍼가 없으면 소비자가 기다려야 한다.
2. Readers-Writers Problem
여러 명의 Readers, Writers 가 하나의 저장 공간(버퍼)를 공유하며 이를 접근할 때 발생하는 문제
- 한 process 가 DB에 write중일 때 다른 precess가 접근하면 안됨 (동시 x)
- read는 동시에 여럿이 해도 됨
read는 동시에 해도 되는데 하나 밖에 못하게 하면 비효율적
write 독점적
-
Reader
- db lock 걸기
- readcount : 몇 명이 읽는지 나타냄
- 최초의 reader -> lock 걸어야 함
- 다음 reader들 -> 그냥 바로 읽으면 됨
- db lock 풀기
-
공유 변수 readcount 를 위해 mutex에 lock을 걸 필요가 있음
3. Dining Philosophers Problem
- 생각하거나 배고파지는 시간이 각각 다름
- 젓가락은 하나만 잡을 수 있음
Deadlock 가능성 있음
- 모두가 동시에 배고파졌을 때 -> 왼쪽 젓가락을 모두 들었을 때 발생
Solution
- 4명의 철학자만이 테이블에 동시에 앉게 한다.
- 젓가락 두 개 집을 수 있을 때만 젓가락을 집을 수 있게 한다.
- 비대칭
- 짝수 철학자는 왼쪽 홀수 철학자는 오른쪽 부터 잡도록 한다.
semaphore self[5] = 0
- 5번 철학자는 두 개의 젓가락을 잡을 수 없다.
semaphore mutex = 1
- 공유 변수에 대해 동시 접근 막기 위해
Monitor
semaphore 의 문제점
- 코딩 어려움
- 정확성 입증 어려움
- 자발적 협력 필요
- 한번의 실수가 모든 시스템에 치명적
Monitor
- 동시 수행 중인 프로세스 사이에서 abstrac data type의 안전한 공유를 보장하기 위한 high-level synchronization construct
monitor는 동시접근이 기본으로 막아져 있기 때문에 lock을 걸 필요 없음
- 공유자원 선언, 프로시저, 초기화 코드가 포함된 병렬식 구조 -> lock 걸 필요 x
- 상태를 저장
- Signal 을 보낸다는 것은 해당 프로세스가 Lock 을 얻었음을 의미
- semaphore 변수처럼 condition vairable 변수가 존재
wait
- 자원이 없으면 프로세스가 줄을 서서 기다리게 한다.
- x.wait() 을 호출한 프로세스는 다른 프로세스가 x.signal() 을 호출하기 전까지 잠들게 된다.
signal
- 모니터에 접근하고 빠져나갈 때 signal 연산을 호출해서 기다리는 프로세스가 모니터에 접근할 수 있도록 한다.
- x.signal() 은 정확하게 하나의 잠이 든 프로세스를 깨운다.
- 잠이 든 프로세스가 없으면 아무 일도 일어나지 않는다.
Bounded Buffer Problem (semaphore)
Bounded Buffer Problem (monitor)
condition variable -> empty, full
wait
- 자원이 없으면 프로세스가 줄을 서서 기다리게 한다.
- x.wait() 을 호출한 프로세스는 다른 프로세스가 x.signal() 을 호출하기 전까지 잠들게 된다.
signal
- 모니터에 접근하고 빠져나갈 때 signal 연산을 호출해서 기다리는 프로세스가 모니터에 접근할 수 있도록 한다.
- x.signal() 은 정확하게 하나의 잠이 든 프로세스를 깨운다.
- 잠이 든 프로세스가 없으면 아무 일도 일어나지 않는다.
Dining Philosophers Problem
