[OS 6-2편] Process Synchronization

2편의 내용은 총 5개로 진행됩니다.

 

1. Semaphore

2. 동기화의 전통적인 문제

3. Monitor

4. Deadlock

5. Deadlock 처리

 

---

 

✔️ Semaphore

• 2개의 atomic한 연산을 통해 접근이 가능.
  • P 연산: 획득 연산
  • V 연산: 반환 연산
• 세마포어를 통해 접근이 가능한 지 확인.
• Block and Wake up Implementation
  • Block: 커널은 block을 요청하는 프로세스를 suspend 시킴. 이 프로세스를 PCB의 Waiting Queue에 넣음.
  • Wake up: Block된 프로세스를 Wake up 시킴. 이 프로세스를 PCB Ready Queue로 옮김.
• Block and Wake up VS Busy Waiting
  • 길이가 긴 경우, Block and Wake up이 적당.
  • 길이가 짧은 경우, block and wak up 보다 busy waiting 오버헤드가 작을 수 있다.
• Semaphore의 종류
  • Counting Sempahore
    • 도메인이 0 이상인 임의의 정수.
    • resource counting에 사용.
  • Mutex
    • 0 또는 1 semaphore
    • 자원에 lock 걸면서 동기화 해결
    • 상호 배제 개념을 이용해 임계 구역에 들어간 스레드가 단독으로 활동할 수 있도록 함.
• Semaphore의 문제점
  • Deadlock
    • 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 상황.
  • Starvation
    • indefinite blocking:프로세스가 suspend 된 이유에 해당하는 Semaphore가 큐에서 못 나가는 현상.
• Sempahore와 Mutex의 차이

	Semaphore	Mutex
동기화 대상	n	1
자원소유여부	자원 소유 불가	자원 소유 가능
unlock 가능	lock 걸지 않은 스레드도 가능.	lock 건 스레드만 가능.
프로세스 범위	시스템 범위(파일)	프로세스 범위(terminate 시 cleanup)

 

✔️ 동기화의 전통적 문제

• Bound buffer problem(Producer-Consumer Problem)
  • 공유데이터: buffer, empty/full 버퍼 위치
  • 동기화 변수: mutex(shared data의 mutual exclusion), resource count(empty, full 버퍼의 수 표시)
  • 세마포어 사용하여 해결
    • semaphore full = 0, empty = n, mutex = 1
    • P와 V 연산 실행.
• Reader-Writer Problem
  • 한 프로세스가 DB에서 작성 중 일 때 다른 프로세스는 접근하지 못하게 함.
  • Read는 동시에 가능.
  • Solution
    • Writer가 DB 허가를 아직 받지 못한 상태에서는 모든 대기 중인 Reader들이 DB에 접근 가능하게 함.
    • Writer들은 Reader가 없을 때 접근 허용.
    • 일단, Writer가 DB에 접근 중이면, Reader들은 접근 금지.
    • Writer가 DB에서 나가야지 Reader 허용.
  • 공유 데이터: DB 자체, readcount(DB에 접근 중인 reader의 수)
  • 동기화 변수: mutex(Readcount를 mutual exlcusion), DB
• Dining Philiosopher Problem
  • 문제
    • 일정 시간 생각
    • 왼쪽 포크 사용가능할 때 까지 대기. (사용 가능하면 들기)
    • 오른쪽 포크 사용가능할 때 까지 대기. (사용 가능하면 들기)
    • 양쪽 포크 둘다 얻으면 식사 시작.
    • 오른쪽 내려두기.
    • 왼쪽 내려두기.
    • 1번으로 돌아가기.
  • Deadlock
    • 이 환경에서 Deadlock 발생 가능함.
    • mutual exclusion: 젓가락은 한 번에 한 철학자만 사용 가능.
    • 점유 및 대기: 왼쪽 젓가락을 들고 있는 상태에서 오른쪽 젓가락을 기다림.
    • 비선점: 이미 누가 가지고 있는 것을 강제로 빼앗을 수 없다.
    • 환형 대기: 모든 철학자가 오른쪽에 앉은 사람이 놓기를 기다림.
  • 해결법
    • 모두 젓가락을 내려두고 일정 시간이 흐른 다음 식사. (기아 발생 가능)
    • mutex 
      • 공유 자원에 여러 스레드의 접근을 막음.
      • 식사할 수 있는 상황을 하나의 key로 관리.
      • 오직 하나의 스레드 만이 동일한 시점에 mutex를 얻어 임계 영역에 들어올 수 있다.
      • 오직 이 스레드 만이 나갈 때 lock을 해제할 수 있음.
      • Ciritical Section을 가진 스레드들이 Running Time이 서로 겹치지 않게 따로 실행하는 기술.
    • Semaphore
      • signalling mechanism : 현재 공유 자원에 접근 할 수 있는 스레드, 프로세스의 수를 나타내는 값을 두어 상호 배제 달성.
      • lock을 걸지 않은 스레드도 signal을 보내 unlock 가능.

 

✔️ Monitor

• Semaphore의 문제점
  • 코딩이 어려움.
  • 정확성 입증이 어려움.
  • 자발적 협력이 필요함.
  • 한 번의 실수가 큰 영향.
• 동시 수행 중인 프로세스 사이에서 ADT의 안전한 공유를 보장하기 위한 high-level Synchronization 구조체.
• 내부적인 operation만으로 shared data 접근 가능.
  • 모니터가 알아서 처리.
  • lock 처리가 없는 것이 장점.
• 모니터 내에는 한번에 하나의 프로세스만 활동 가능.
• 프로그래머가 동기화를 명시적으로 코딩하지 않아도 됨.
• 프로세스가 모니터 안에서 기다릴 수 있게 condition variable 사용함.
  • x.wait() -> 다른 프로세스가 signal 보낼 때까지 suspend.
  • x.signal() -> 하나의 suspend된 프로세스를 resume.
• condition variable은 값을 가지지 않고 자신의 큐에 프로세스를 달아서 sleep 시키거나 큐에서 프로세스를 깨우는 역할만 함.

 

✔️ Deadlock

• 일련의 프로세스들이 서로 자원을 기다리며 Block된 상태.
• Resource
  • HW, SW를 포함하는 개념
    • ex) I/O 디바이스, CPU 사이클, 메모리 공간, 세마포어
  • 프로세스가 자원을 사용하는 절차
    • ex) Request, Allocate, Use, Release
• Example
  • 시스템에 2개의 tape 드라이브 존재.
    • P1과 P2가 각각 한 개의 드라이브를 점유한 상태에서 하나를 더 기다림.
  • Binary Semaphore A and B
    • P1 -> P(A), P(B)
    • P2 -> P(B), P(A)
• Deadlock 발생 조건⚡️
  • Mutual Exclusion
    • 매 순간 하나의 프로세스만 자원 사용 가능.
  • No Preemption
    • 프로세스가 스스로 자원을 내어놓을 뿐, 강제로 빼앗지 못함.
  • Hold and Wait
    • 자원을 가진 프로세스가 다른 자원을 기다리며, 보유 자원은 내어놓지 않고 계속 가지고 있는 상태.
  • Circular Wait
    • 자원을 기다리는 프로세스 간 사이클 형성.
• Deadlock 처리
  • Deadlock Prevention
    • 자원 할당 시 deadlock 4가지 조건 중 어느 하나가 만족되지 않도록 하는 것.
  • Deadlock Avoidance
    • 자원요청에 대한 부가적인 정보를 이용해 deadlock의 가능성이 없는 경우에만 할당.
  • Deadlock Detection and Recovery
    • deadlock 발생은 허용하되, 그에 대한 detection routine을 두어 deadlock 발생 시 recovery.
  • Deadlock Ignorance
    • deadlock을 시스템이 책임지지 않음.
    • 대부분의 OS에서 채택하고 있음.

 

✔️ Deadlock 처리

• Deadlock Prevention
  • Mutual Exclusion: 공유해서는 안되는 자원의 경우 반드시 성립
  • Hold and Wait
    • 프로세스가 자원을 요청할 때는 다른 어떤 자원도 가지고 있으면 안된다.
    • 방법1. 프로세스 시작 시 모든 필요한 자원을 할당 받게 하는 법
    • 방법2. 자원이 필요한 경우 보유한 자원을 모두 놓고 다시 시작함.
  • No Preemption
    • 프로세스가 어떤 자원을 기다려야 하는 경우, 이미 보유한 자원은 선점.
    • 모든 필요한 자원을 얻을 수 있을 때 다시 시작.
    • state를 쉽게 save하고 store할 수 있는 자원에서 주로 사용. (CPU, 메모리)
  • Circular Wait
    • 모든 자원 유형에 할당 순서를 부여해 정해진 순서대로 할당.
  • Deadlock Prevention은 사용성 부분과 성능 부분에서 떨어진다.
• Deadlock Avoidance
  • 자원 요청에 대한 부가정보를 활용해 자원 할당이 deadlock으로부터 안전한 상태인지 동적으로 검사하여 안전한 상태에만 할당.
  • 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 용량을 미리 선언하는 것.
  • safe state
    • 시스템 내에 프로세스에 대한 safe sequence가 존재하는 상태.
  • safe sequence
    • 프로세스 시퀀스가 안전하려면, 해당 프로세스의 보유 자원과 모든 프로세스들의 보유 자원이 충족되어야 함.
  • 시스템이 safe state에 있다면, no deadlock.
  • 시스템이 unsafe state에 있다면, possibility of deadlock.
  • deadlock avoidance는 시스템이 unsafe 상태에 들어가지 않음을 보장.
  • 2가지 Avodiance 알고리즘
    • Single Instance ->  Graph
    • Multiple Instance -> Banker's Algorithm
  • Banker's Alogrithm
    • 은행은 한 사람을 더 빌려줄 만큼의 자금을 가지고 있어야 한다.
    • 프로세스가 자원을 요구할 때, 자원을 할당한 후에도 안전한 상태라면 자원을 할당하고, 그렇지 않다면 다른 자원이 해제될 때 까지 대기했다가 자원을 할당한다.
    • 가정
      • 모든 프로세스는 자원의 최대 사용량을 미리 명시.
      • 프로세스 요청 자원을 모두 할당 받은 경우, 유한 시간 안에 이들 자원을 다시 반납.
    • Sequence가 생성됨.
• Deadlock Detection and Recovery
  • Deadlock Detection
    • Single Instance의 경우 Cycle이 Deadlock
    • Multiple Instance인 경우, Bandker's Algorithm
  • Recovery
    • Process Termination
      • Deadlock에 걸린 프로세스 Abort.
      • 하나씩 Abort하면서 Deadlock이 풀릴 때까지 하기.
    • Resource Preemption
      • 비용을 최소화할 희생양 설정.
      • process restart해서 safe state로 rollback.
      • starvation 문제 - 같은 프로세스가 희생양이 되는 경우.
• Deadlock Ignorance