TIL

🌱 난 오늘 무엇을 공부했을까?

📌 프로세스 동기화 , 상호배제

📍 Process Synchronization (동기화)

• 다중 프로그래밍 시스템
  • 여러 개의 프로세스들이 존재
  • 프로세스들은 서로 독립적으로 동작(동시에)
  • 공유 자원 또는 데이터가 있을 때, 문제 발생 가능
    • 공유 자원에 동시에 접근하게 될 때 발생하는 문제를 동기화를 통해 피한다.
• 동기화 (Synchronization)
  • 프로세스 들이 대화를 하는 것
  • 프로세스 들이 서로 동작을 맞추는 것
  • 프로세스 들이 서로 정보를 공유 하는 것

📍 Asynchronous and Concurrent Process

• 비동기적(Asynchronous)
  • 프로세스들이 서로에 대해 모름
• 병행적 (Concurrent)
  • 여러 개의 프로세스들이 동시에 시스템에 존재
• 병행 수행중인 비동기적 프로세스들이 공유자원에 동시 접근 할 때 문제가 발생 할 수 있음
  • 동시에 작업을 하는데 서로 모르기 때문에

📍 Race Condition

• 공유 자원에 대해 여러 프로세스가 동시에 접근할 때, 결과값에 영향을 줄 수 있는 상태

  동시 접근 시 자료의 일관성을 해치는 결과가 나타남

🔗 Race Condition 발생하는 경우

1. 커널 모드로 수행 중 인터럽트가 발생하는 경우
   • 문제점 : 커널모드에서 데이터를 로드하여 작업을 수행하다가 인터럽트가 발생하여 같은 데이터를 조작하는 경우
   • 해결법 : 커널모드에서 작업을 수행하는 동안, 인터럽트를 disable 시켜 CPU 제어권을 가져가지 못하도록 한다.
2. 프로세스가 시스템 콜을 호출해서 커널 모드로 수행 중인데 Context switch가 발생하는 경우
   • 문제점 : 프로세스1이 커널모드에서 데이터를 조작하는 도중, 시간이 초과되어 CPU 제어권이 프로세스2로 넘어가 같은 데이터를 조작하는 경우 ( 프로세스2가 작업에 반영되지 않음 )
   • 해결법 : 프로세스가 커널모드에서 작업을 하는 경우 시간이 초과되어도 CPU 제어권이 다른 프로세스에게 넘어가지 않도록 함
3. 멀티 프로세서에서 공유 메모리 내의 커널 데이터에 접근하는 경우
   • 문제점 : 멀티 프로세서 환경에서 2개의 CPU가 동시에 커널 내부의 공유 데이터에 접근하여 조작하는 경우
   • 해결법 : 커널 내부에 있는 각 공유 데이터에 접근할 때마다, 그 데이터에 대한 lock/unlock을 하는 방법

📍 Terminologies

• Shared data (공유데이터 or Critical data) : 여러 프로세스들이 공유하는 데이터
• Critical section (임계 영역) : 공유 데이터를 접근하는 코드 영역(code segment)
• Mutual exclusion (상호배제) : 둘 이상의 프로세스가 동시에 critical section에 진입하는 것을 막는 것

• 한번 실행하면 멈추지 않고 실행 되는 것

• 번역결과
  

• 명령어 수행 과정에 따라 결과가 달라질 수 있다.

📍 Mutual Exclusion Methods

• Mutual exclusion primitives(기본 연산)
  • enterCS() primitive
    • Critical section 진입 전 검사
    • 다른 프로세스가 critical section 안에 있는지 검사
  • exitCS() primitive
    • Critical section을 벗어날 때의 후처리 과정
    • Critical section을 벗어남을 시스템이 알림

📍 Requirements for ME primitives(요구 조건)

• Mutual exclusion (상호배제) == Mutex

  • Critical section (CS) 에 프로세스가 있으면, 다른 프로세스의 진입을 금지

• Progress (진행)

  • CS 안에 있는 프로세스 외에는, 다른 프로세스가 CS에 진입하는 것을 방해 하면 안됨
  • 안에 아무것도 없으면 진입이 가능해야 함.

• Bounded waiting (한정대기)

  • 프로세스의 CS 진입은 유한시간 내에 허용되어야 함

📌 Mutual Exclusion Solutions

• SW solutions

  • Dekker’s algorithm (Peterson’s algorithm)
  • Dijkstra’s algorithm, Knuth’s algorithm, Eisenberg and McGuire’s algorithm, Lamport’s algorithm

• HW solution

  • TestAndSet (TAS) instruction

• OS supported SW solution

  • Spinlock
  • Semaphore
  • Eventcount/sequencer

• Language-Level solution

  • Monitor

📍 SW Solutions

• Dekker’s algorithm
  - flag와 turn 변수를 통해 임계 구역에 들어갈 프로세스/스레드를 결정하는 방식

• Peterson’s algorithm
  - 데커와 유사하지만, 상대방 프로세스/스레드에게 진입 기회를 양보하는 것에 차이가 있음

  • 둘 다 들어가야 하는 상황에는 턴을 확인하고 그게 아니면 그냥 들어간다.
    

• SW solution들의 문제점

  • 속도가 느림
  • 구현이 복잡하다
  • Mutual Exclusion primitive 실행 중 preemption 될 수 있음
    • 공유 데이터 수정 중은 interrupt를 억제 함으로서 해결 가능
      • Overhead 발생
  • Busy waiting

📍 HW solution

• TestAndSet (TAS) instruction
  • Test 와 Set을 한번에 수행하는 기계어
  • 데이터를 읽으면서 동시에 쓰는 행동을 한번에 한다.
  • Machine instruction
    • Atomicity, Indivisible
    • 실행 중 interrupt를 받지 않음 (preemption 되지 않음)

• 장점

  • 구현이 간단

• 단점

  • Busy waiting
    • 원하는 자원을 얻기 위해 기다리는 것이 아니라 권한을 얻을 때까지 확인하는 것
    • 권한 획득을 위해 많은 CPU를 낭비
    • 비효율적

• Busy waiting 문제를 해소한 상호배제 기법

  • Semaphore
    • 대부분의 OS들이 사용하는 기법

📍 OS supported SW solution

• SW Solutions, HW solution의 문제점을 보완하기 위해서 발전.

🔗 Spinlock

• 초기화, P(), V() 연산으로만 접근 가능

  • 위 연산들은 indivisible (or atomic) 연산
    • OS support가 P와 V가 한번에 되도록 보장한다.
    • 전체가 한 instruction cycle에 수행 됨

• P() : 자물쇠를 건다.

• V() : 자물쇠를 푼다.
  
  

• 단점

  • 멀티 프로세서 시스템에서만 사용 가능
  • Busy waiting

🔗 Semaphore

• SW에서 해야하는 연산을 추상화시킴
• 1965년 Dijkstra가 제안
• Busy waiting 문제 해결
• 음이 아닌 정수형 변수(S)
  • 초기화 연산, P(), V()로만 접근 가능
    • P : Probern (검사)
    • V : Verhogen (증가)
• 임의의 S 변수 하나에 ready queue 하나가 할당 됨

🔗 Semaphore 종류

• Binary semaphore

  • S가 0과 1 두 종류의 값만 갖는 경우
  • Mutual exclusion나 프로세스 동기화의 목적으로 사용

• Counting semaphore

  • S가 0이상의 정수값을 가질 수 있는 경우
  • Producer-Consumer 문제 등을 해결하기 위해 사용
  • 생산자-소비자 문제

• 초기화 연산

  • S 변수에 초기값을 부여하는 연산

  • P() 연산, V() 연산

    

    S에 할당된 대기실(ready Queue)에서 대기

• 모두 indivisible 연산

  • OS support
  • 전체가 한 instruction cycle에 수행 됨

• Semaphore로 해결 가능한 동기화 문제들

  • Mutual exclusion
  • process synchronization problem
  • producer-consumer problem
  • Reader-writer 문제
  • Dining philosopher problem
  • 기타

🔗 Semaphore의 가장 큰 특징

• No busy waiting

  • 기다려야 하는 프로세스는 block(asleep)상태가 됨

• Semaphore queue에 대한 wake-up 순서는 랜덤

  • Starvation problem : 운이 없으면 생긴다.

🔗 Semaphore의 Starvation problem를 해결하기 위한 방법 -> Eventcount/Sequencer

• 은행에서 번호표 순서로 처리하는 원리를 이용한 기법
• Sequencer
  • 정수형 변수이고 0으로 초기화 되어있으며, 발생 사건들의 순서를 유지해주는 역할을 함
  • Sequencer은 ticket() 연산으로만 접근 가능한데, ticket(S)은 현재까지 ticket() 연산이 호출된 횟수를 반환함
  • ticket() 연산은 원자성을 가짐
• Eventcount
  • 정수형 변수이고 0으로 초기화 되어있으며, 특정 사건의 발생 횟수를 기록함
  • read(E) 연산 : 현재 Eventcount값 반환
  • advance(E) 연산 : 다음 프로세스를 깨움(E=E+1)
  • await(E,v) 연산 : v는 도착한 고객의 번호이며, v>E이면 대기할 수 있도록 Queue에 프로세스를 push하거나 CPU scheduler을 호출함
• 이벤트 카운트를 활용하면 순서를 부여할 수 있어 세마포어의 무한 대기 문제, starvation을 해결할 수 있다.

🔗 Eventcount/Sequencer 특징

• No busy waiting
• No starvation
  • FIFO scheduling for QE
• Semaphore 보다 더 low-level control이 가능(세부적인 내용)

📌 deadlock(교착상태)

• 프로세스들이 서로가 가진 자원을 기다리며 block된 상태

📍 Resource(자원)

• 하드웨어, 소프트웨어 등을 포함하는 개념
• 프로세스가 자원을 사용하는 절차
  • Request, Allocate, Use, Release

📍 Deadlock 발생의 4가지 조건 - 1971년에 E. G. 코프만

• 상호배제(Mutual exclusion)
  • 매 순간 하나의 프로세스만 자원을 사용한다.
• 점유대기(Hold and wait)
  • 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.
• 비선점(No preemption)
  • 프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없다.
• 순환대기(Circular wait)
  - 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.
  - 자원을 기다리는 프로세스간에 사이클이 형성

  자원할당그래프

  • 그래프에 사이클이 없으면 deadlock이 아니다.
  • 그래프에 사이클이 있으면
    • 하나의 자원에 인스턴스가 1개라면 데드락이다
    • 인스턴스가 여러개면 데드락일수도 아닐수도 있다.
      

📍 Deadlock 처리방법

• 예방 : 교착 상태 발생 조건 중 하나를 제거하면서 해결한다 (자원 낭비 엄청 심함)
  • 상호배제 부정
  • 점유대기 부정
  • 비선점 부정
  • 순환대기 부정
• 회피 : 교착 상태 발생 시 피해나가는 방법
  • 은행원 알고리즘(Banker's Algorithm)
• 탐지와 회복 : 교착 상태가 되도록 허용한 다음 회복시키는 방법
  • 탐지 : 자원 할당 그래프를 통해 교착 상태를 탐지(자원 요청 시 탐지 알고리즘을 실행시켜 그에 대한 오버헤드 발생함)
  • 회복 : 교착 상태 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복시키는 방법
• 무시 : Deadlock을 시스템이 책임지지 않음
  • UNIX를 포함한 대부분의 OS가 채택

📍 Deadlock Prevention

• 상호배재 부정 : 여러 프로세스가 공유 자원 사용(공유해서는 안되는 자원의 경우 반드시 성립해야 함)
• 점유대기 부정 : 프로세스가 자원을 요철할 때 다른 어떤 자원도 가지고 있지 않아야 한다.
  • 프로세스 실행전 모든 자원을 할당
  • 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청(자진해서 자원을 반납하는 방법)
• 비선점 부정 : 프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원을 빼앗아옴
  • 상태를 쉽게 저장하고 이어서 다시 시작할 수 있는 자원에서 주로 사용(CPU, Memory)
• 순환대기 부정 : 모든 자원 유형에 할당 순서를 정해서 정해진 순서대로만 자원을 할당
  • 순서가 3인 자원 R3을 보유 중인 프로세스가 순서가 1인 자원 R1을 할당받기 위해서는 우선 R3을 release해야 한다.
• 자원 이용률 저하 , 처리율 감소, starvation 문제

📍 Deadlock Avoidance

• 자원 요청에 대한 정보를 이용해서 자원 할당이 deadlock으로부터 안전한지를 동적으로 조사해서 안전한 경우에만 할당
• 가장 단순한 방법으로 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하는 방법도 있음
• Safe State
  • 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태
• safe sequence
  • "가용 자원 + 현재 프로세스의 보유자원" 이 프로세스들이 요청하는 최대의 자원들을 충족해야 하는 sequence

🔗 Resource Allocation Graph algorithm

• Resource Allocation Graph를 사용해 Process의 수행 순서를 결정함
• 인스턴스가 하나일 때 사용
• 미래에 사용할 자원을 나타내는 Claim Edge를 사용한다. (점선)
  • 요청할 때 점선이 실선으로 바뀜. 이 때 cycle이 생기지 않으면 자원을 할당함

• 위와 같은 상황에서 P2가 R2를 요청해 할당받게 되면 Cycle이 생기게 된다. 이러한 경우 Resource를 할당받지 않고 P1이 끝나기를 기다린다.

🔗 Banker's Algorithm

• 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래함
• 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피
• 안정 상태면 자원 할당, 아니면 다른 프로세스들이 자원 해지까지 대기
• 인스턴스가 여러개일 때 사용

• 사용되는 변수
  1. Available : 각 Resource 별로 할당할 수 있는 남은 인스턴스 수
  2. Max : Process가 하나의 타입의 resource에 최대로 요구하는 인스턴스 수
  3. Allocation : Process에 할당된 resource의 인스턴스 수
  4. Need : Process가 필요로 하는 resource의 인스턴스 수
• 최악의 상황을 가정해서 Available보다 Need가 많은 프로세스에게 할당하지 않고 Need를 비교해서 가장 안전한 프로세스부터 일을 처리하고 반환
• 현재 그림에서 안전한 시퀀스가 존재함으로 safe state

📍 Deadlock Detection and Recovery

🔗 Deadlock Detection

• 단일 인스턴스
  - 자원 할당 그래프를 기반으로 한 탐지
  
• -> Wait-for 그래프로 변환
  
• P1 => P2 => P3 => P4, 주기를 형성하고 있으므로 교착 상태

---

• 다중 인스턴스
  • Banker's Algorithm과 유사한 알고리즘을 사용
  • 탐지 알고리즘을 언제 호출 하나?
    • 1. 프로세스가 리소스를 요청할 때마다 탐지 알고리즘을 호출.
    • 2. 교착 상태 알고리즘을 주기적 간격으로 실행

🔗 Deadlock Recovery

• 프로세스 종료

1. 프로세스 종료
   • Deadlock을 담당하는 프로세스가 종료.
   • 운영 체제는 주로 더 이상 작동하지 않는 프로세스를 종료.
2. 모든 프로세스 종료
   • 모든 프로세스를 종료하는 것은 적절하지 않다. 그러나 중요한 상황이 발생하면 이 접근 방식이 적합할 수 있다.

• 자원 선점 : 자원을 뺏는 방법, safe state로 롤백
  • 동일한 프로레스가 계속 뺏기면 Starvation 문제 생김
  • rollback 횟수도 같이 고려해야 한다.

📍 Deadlock Ignorance

• Deadlock이 일어나지 않는다고 생각하고 조취를 취하지 않음.
  • Deadlock이 매우 드물게 일어나기 때문에 Deadlock에 대한 조취가 더 큰 overhead
  • Deadlock이 발생하면 사용자가 느끼고 판단
  • UNIX, Windows 등 대부분의 범용 OS가 채택

👍 iOS에서 Deadlock 해결법

---

https://www.youtube.com/playlist?list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN
https://core.ewha.ac.kr/publicview/C0101020140408134626290222?vmode=f
https://dongdd.tistory.com/63
https://www.codingninjas.com/codestudio/library/deadlock-detection-and-recovery
https://core.ewha.ac.kr/publicview/C0101020140415131030840772?vmode=f