Process Synchronization
1. Synchronization
Synchronization 해결 충족 조건
Mutual Exclusion
- 어떤 프로세스가 critical section을 수행 중이면 다른 모든 프로세스는 critical section에 들어갈 수 없다
Progress
- 아무도 critical section에 있지 않은 상태일 경우 들어가게 해줘야 한다
Bounded Waiting
- critical section에 들어가기를 요청한 후 허용될 때까지 다른 프로세스가 들어가는 횟수는 한계가 있어야 한다
= 기다림이 유한해야 한다
소프트웨어적 해결
1) Algorithm 1
- critical section에 들어가기 전에 차례(turn)을 체크
- 내 차례(turn=0)가 아니면 계속 while을 돌음
- 내 차례가 되면 들어가서 처리 후 나오면서 turn을 상대방 차례(turn=1)로 변경
문제점
- 교대로 들어가야만 함 -> 한 쪽이 빈번하게 요청을 할 때 들어갈 수 없음 = Progress 불만족
- 상대가 turn을 변경해주므로 상대가 한 번 들어간 후 다시 요청하지 않으면 내 차례가 오지 않음
2) Algorithm 2
- 각자 flag를 가지고 있음
- flag로 들어가고자 하는 의사 표현
- 들어가고 싶으면 flag를 ture로 변경 후 상대방 flag를 체크
- 상대는 false라면 들어갔다 나온 후 flag를 false로 변경
문제점
- P1 : flag를 들자마자 CPU한테 뺏김 = 들어간다고 표시는 했는데 못들어감
- P2 : 상대도 들어가고 싶어서 flag를 들었는데 상대가 들어서 못들어감
- P1이 다시 CPU를 받았는데 상대(P2)가 flag를 들고 있어서 못들어감
- 결국 아무도 못들어감 = Progress 불만족
- 들어가야만 flag를 내릴 수 있음
3) Algorithm 3 (Peterson’s Algorithm)
- flag와 turn을 모두 사용
상대방이 깃발을 들고 있고(상대방 flag == true) && 상대방 차례(turn == 상대)이면 계속 while을 돌음- 그렇지 않으면 들어가서 나올 때 flag를 내리고 상대 turn으로 변경함
- 3가지 조건(Synchronization 해결 충족 조건)을 모두 만족
문제점
- Busy Waiting(=Spin Lock): CPU와 memory를 쓰면서 계속 들어갈 수 있는지 체크해야 함
하드웨어적 해결
Test and Set
- 뭔가를 처리하는 중에 CPU를 빼앗길 수 있어서 문제 발생했던 것
- 읽으면서 쓰는 작업을 동시에 작업하면(한 인스트럭션) 문제를 줄일 수 있음(한 명령어 작업 중에는 빼앗지 않으니) = atomic하게
- lock의 값을 읽으면서 동시에 값을 변경
- while(Test_and_Set(lock)) -> critical section -> lock = false
- 간편하게 lock을 걸 수 있음
2. Semaphores
- OS에서 지원하는 SW 방법
- 위의 방식들을 추상화시킴 -> 추상 자료형
- 정수(integer) 값을 가질 수 있음 -> 몇 명이 들어갈 수 있나
- P와 V 연산으로 접근
P 연산
- 공유 데이터를 획득하는 과정
- lock을 걸기
while(S<=0)으로 돌다가 S가 양수가 되면 자원을 가져감(S--)
V 연산
- 공유 데이터를 획득 후 내어놓는 과정
- lock을 풀기
S++
Critical Section
semaphore mutex;
do {
P(mutex)
critical section
V(mutex)
} while(1);- 추상화이므로 P와 V를 구현하는건 어떻게 구현할지는 구현할 시스템에서 고민할 문제
- busy wait을 함
-> Block & Wakeup 방식도 가능 (=sleep lock)
Block & Wakeup
- busy waiting을 방지하는 방법
- 세마포어를 획들할 수 없으면 필요한 프로세스를 block 시킴
- 세마포어 대기 큐에 달아놓음
- 누군가 세마포어를 반납하면 block된 프로세스를 wakeup 시킨 후 ready queue로 보냄
P(S)
S-- // 자원 획득
if (S < 0) { // 획득할 수 없으면 block으로 변경
block()
}P(V)
S++ // 자원 반납
if (S <= 0) { // 누군가에게 줄 수 있으면 wakeup해서 깨워줌
wakeup()
}S <= 0= 누군가 -1하고 잠들어 있다- 양수일 때가 누군가에게 줄 수 있다는 의미가 아님
- 음수일 때가 누군가 기다리고 있다는 의미
- S 자체가 자원의 개수를 나타내던 앞의 개념과는 다름
일반적으로 Block & Wakeup이 Busy-Wait보다 효율적
- 프로세스를 block <-> wakeup하는 오버헤드는 존재
- critical section이 매우 짧은 경우 오버헤드가 커질 수 있음
Semaphore의 종류
Counting Semaphores
- 0 이상의 임의의 정수 값
- 자원의 개수가 여러 개
- 남은 자원의 개수를 표현
- 여분이 있으면 가져다 쓸 수 있는 경우
Binary Semaphores
- 0 또는 1만 가짐
- 주로 mutext exclusion에 사용
Deadlock and Starvation
Deadlock
- P0: S와 Q가 필요 - S 세마포어를 얻음, Q를 기다림
- P1: S와 Q가 필요 - Q 세마포어를 얻음, S를 기다림
- 서로 영원히 기다려야 함
해결 방법
- 자원을 획득하는 순서를 정해놓기
- ex) Q를 획득하려면 S부터 얻어야 한다
Starvation
- 영원히 자원을 얻지 못하고 무한히 기다리는 현상
- 특정 프로세스들 끼리 자원을 가지고 나에겐 주지 않음
- Deadlock도 Starvation 처럼 해석할 수는 있음 ex) 식사하는 철학자들 문제
3. Synchronization 문제
1) 생산자 소비자 문제(Bounded Buffer Problem)
- 생산자(Producer) 프로세스: 공유 버퍼에데 데이터를 만들어서 저장하는 역할
- 소비자(Consumer) 프로세스: 공유 버퍼에서 데이터를 꺼내감
문제 상황
- 여러 생산자가 동시에 한 버퍼에 데이터를 쓸 때
- 여러 소비자가 동시에 한 버퍼에서 데이터를 가져갈 때
➡️ 공유 버퍼에 들어갈 때 lock을 걸고 풀어야 함
- 공유 버퍼는 유한하기 때문에 가득 찼을 때 생산자가 또 데이터를 쓰려고 할 때
--> 소비자가 꺼내주기 전까지 쓸 수 없음 - 데이터가 없는 경우에는 소비자가 데이터를 가져갈 수 없음
--> 생산자가 데이터를 저장하기 전까지 가져갈 수 없음➡️ 공유 버퍼에 들어가기 전 버퍼가 비었는지(찼는지) 확인하고 들어가야 함
자원의 개수를 셀 때(resource count), 자원에 접근할 때(mutext exclusion) 세마포어 변수가 필요
2) Reader-Writer 문제
- 한 프로세스가 DB에 write 중일 때 다른 프로세스가 접근하면 안 됨 -> write는 배타적
- read는 동시에 여럿이 해도 됨 --> 이미 read 중일 때 read는 접근해도 됨
- 읽을 때
readCount++하고 나갈 때readCount-- readCount역시 공유 변수이므로 변경할 때 lock을 걸어야 함- read할 때 write를 막는 lock을 걸음
- 만약
readCount가 1이 아니면 이미 누가 읽고 있던 것으로 lock을 안걸어도 됨 - 나갈 때
readCount == 0이면 아무도 읽고 있지 않으므로 lock을 해제 readCount와 db 접근 모두 binary 세마포어- 계속 reader가 오면 writer가 starvation이 발생할 수 있어 조건을 걸어줘야 함
3) 식사하는 철학자 문제
- 철할자 양 옆으로 하나씩의 젓가락만 있음
- 철학자의 일 = 생각하기 or 밥 먹기
- 언제 생각하고 언제 밥을 먹을지는 모름
- 밥을 먹기 위해서는 양쪽의 젓가락이 필요 -> 공유 자원
- 밥을 먹고 싶으면 한쪽을 잡고 한쪽이 없으면 기다렸다가 잡고 먹음 -> 다 먹으면 내려놓기
- 모두 왼쪽 젓가락을 잡으면 다 같이 기다리기만 하고 굶는 상황이 발생 = Deadlock
-> 식사할 때만 식탁에 앉기 하기
-> 양쪽 젓가락이 모두 가능한 경우에만 젓가락을 잡도록 하기
-> 젓가락 잡는 순서를 다르게 정해놓기
4. Monitor
세마포어의 문제점
- 코딩하기 힘들다
- 정확성 입증이 어렵다
- 자발적 협력이 필요하다
- 한 번의 실수도 모든 시스템에 치명적
➡️ 이런 문제를 보완
모니터
동시 수행 중인 프로세스 사이에서 안전한 데이터 공유를 위한 high-level 동기화 구조
- 동시 접근 문제를 monitor가 자동으로 해결해줘서 프로그래머의 부담 ⬇️
- 모니터 내에 한 번에 하나의 프로세스만 활동 가능 -> lock을 걸 필요가 없음
- 접근 코드를 모니터 내부에서 구현 -> 모니터가 알아서 접근을 제어해줌
- 조건을 만족하지 않은 프로세스가 모니터 안에거 기다리게 하기 위해
conditinal variable사용
- 조건 별로 다른 줄을 서서 기다리게 함
- wait: 프로세스를 잠들게 함
- signal: 잠들어 있는 프로세스를 깨워줌
모니터를 이용한 생산자-소비자
생산자
- 버퍼가 가득 차있어 생산자가 데이터를 저장하지 못함 -> empty.wait에서 대기하도록 함
- 생산자가 데이터를 저장하고 난 후 -> full.signal
소비자
- 버퍼가 비어있어 소비자가 데이터를 꺼내지 못함 -> full.wait으로 대기하도록 함
- 소비자가 데이터를 가져가고 난 후 -> empty.signal
5. Deadlock
교착 상태
일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
- 자원(Resource) : 하드웨어, 소프트웨어를 포함
ex) I/O 장치, CPU 사이클, 메모리 공간, 세마포어 등 - 자원을 사용하는 순서: 자원 요청 (Request) -> 자원 획득 (Allocate) -> 자원 사용 (Use) -> 자원 반납 (Release)
발생 조건
1. Mutual exclustion (상호 배제)
- 매 순간 하나의 프로세스만 자원을 사용할 수 있음
2. No Preemption (비선점)
- 프로세스가 자원을 내어놓아야 할 뿐 뺏기지 않음
3. Hold and wait (보유 대기)
- 자원을 가진 채 다른 자원을 기다릴 뿐 내어놓지 않음
4. Circular wait (순환 대기)
- 자원을 기다리는 프로세스 간 사이클이 형성
처리 방법
Deadlock Prevention - 예방
자원 할당 시 발생 조건 4가지 중 하나 이상이 만족되지 않도록 하기
Deadlock Avoidance - 회피
자원 요청의 부가 정보를 이용해 deadlock의 가능성이 없는 경우에만 자원을 할당하기
Deadlock Detection and recovery - 탐지와 회복
데드락 발생은 허용하되 그에 대한 detection 루틴을 두어 발견시 recover
Deadlock Ignorance - 무시
데드락을 시스템이 책임지지 않음 -> UNIX를 포함한 대부분의 OS가 채택
자주 발생하는 문제가 아니라 방지하는게 오버헤드일 수 있음
사용자가 처리하도록 미루기
1) Deadlock Prevention
- Mutual exclustion (상호 배제)
- 공유해선 안되는 자원은 반드시 성립해야 하므로 막기 어려움
- No Preemption (비선점)
- 프로세스가 자원을 기다릴 경우 이미 보유한 자원은 선점됨
- 필요한 자원을 모두 얻을 수 있을 때 프로세스가 다시 시작
- Hold and wait (보유 대기)
- 프로세스가 자원을 요청할 때 다른 자원을 가지고 있지 않도록 하기
- 방법 1) 프로세스 시작 시 모든 필요한 자원을 할당
-> 자원을 모두 할당해서 비효율성 - 방법 2) 자원이 필요한 경우 보유 자원을 모두 놓고 다시 요청
- Circular wait (순환 대기)
- 자원 할당 순서를 정하여 정해진 순서 대로만 자원을 할당
➡️ 생길지 모르는 데드락을 방지하기 위해 위와 같은 처리를 하는게 비효율적일 수 있음
2) Deadlock Avoidance
- 특정 프로세스가 평생 사용할 자원을 미리 알고 있다는 가정 하에 자원 요청을 했을 때 데드락 발생 가능성을 판단하여 자원의 할당 여부를 결정
Banker's 알고리즘
- 자원 별 개수
- 프로세스 별 평생 필요한 자원별 최대 개수(Max)
- 현재 할당 가능한 자원의 개수(Available)
- 최대 요청 가능량(Max) - 현재 할당량(Allocation) = 할당을 요구할 수 있는 최대량(Need)
- 현재 가능한 자원량(Available)에서 지금 요청한 자원량을 줘도 Need를 만족시킬 수 있는지 판단해서 자원을 할당
➡️ 자원이 남아도는데도 안주니까 비효율적, 최대량을 줄 수 없는 상황이라도 반드시 데드락이 발생하는게 아님
3) Deadlock Detection and recovery
- 일단 자원은 달란 대로 주고 데드락이 발생하는지 detect해서 있으면 recover하자
detection 방법
방법 1) 사이클을 찾기(자원이 하나씩일 때)
- 너비 우선 탐색
- 깊이 우선 탐색
-> O(n^)
방법 2) 다른 프로세스가 자원을 반납할 거라고 낙관적으로 생각하며 자원을 할당 - 정말 데드락인 경우만 찾기
- 가용 자원으로 더 이상의 요청을 받아드릴 수 없을 때 데드락
- Banker's 알고리즘과 비슷하지만 훨씬 낙관적
Recovery 방법
방법 1) 데드락과 관련된 모든 프로세스 죽이기
방법 2) 데드락과 관련된 프로세스 중 하나씩 자원을 빼앗으면서 해결되는지 확인
4) Deadlock Ignorance
- 데드락이 일어나든 말든 시스템에서는 책임지지 않음
- 프로세스가 정지되거나 느려짐을 사용자가 알게 되면 사용자가 처리하도록 방치
iOS Developer