1. 병행성(동시성) vs 병렬성

	동시성(Concurrency)	병렬성(Parallelism)
정의	· 서로 다른 작업들이 동시에 처리하는 것처럼 보이게 하는 것 · 실제로는 번갈아가며 실행되며 서로 영향을 미침	· 여러 작업을 실제로 동시에 처리하는 것 · 작업들이 각각 독립적으로 실행되며 서로 영향을 주지 않음
동작 방식	싱글 코어에서 멀티 스레드를 동작	멀티 코어에서 멀티 스레드를 동작
개념적 차이	논리적 개념	물리적 개념

---

2. 프로세스 동기화(Synchronization)

• 2개 이상의 프로세스에 대한 처리순서를 결정하는 것

  🔎 예시
  프로세스 A가 어떤 작업을 처리한 후 프로세스 B가 이어서 처리해야 하는 코드가 있다면, 프로세스 B는 프로세스 A가 해당 작업의 처리를 마칠 때까지 특정 코드를 수행하지 않고 기다리도록 함

---

3. 임계영역(Critical Section)

• 2개 이상의 프로세스가 동시에 사용하면 안 되는 공유자원을 액세스하는 프로그램 코드 영역

  🔎 예시
  계좌의 잔고를 읽고 입금액을 더한 후, 더해진 액수를 계좌에 쓰는 입금과정에 해당하는 코드

3-1. 경쟁 상태(Race Condition)

• 여러 개의 프로세스가 공유자원에 동시에 접근할 때 실행 순서에 따라 결과값이 달라질 수 있는 현상
• 동기화로 해결 가능

3-2. 상호 배제 = 뮤텍스(Mutual Exclusion, Mutex)

3-2-1. 정의

• 멀티 프로그래밍에서 공유 불가능한 자원의 동시 사용을 피하기 위해 사용되는 알고리즘
  • 하나의 프로세스가 공유자원을 사용할 때 다른 프로세스의 접근을 막는 것
• 임계영역으로 불리는 코드 영역에 의해 구현
• 교착 상태와 기아 상태가 발생할 수 있음
• 멀티 프로세스나 멀티 스레드 동기화에 사용

3-2-2. 방법

• 임계영역을 가진 스레드의 Running time이 서로 겹치지 않게 단독적으로 실행되게 함
  • 임계영역에 하나의 스레드만 접근 가능(binary semaphore)
  • 상태가 0, 1 → 이진 세마포어
• 다중 프로세스들의 공유 리소스에 대한 접근을 조율하기 위해 Locking과 Unlocking 사용
  • 임계영역 진입시 lock, 나올 때 unlock

3-3. 세마포어(Semaphore)

• 임계영역에 하나의 스레드 혹은 복수개의 스레드 진입 가능
• wait와 signal을 통해 구현
  1. wait이 먼저 호출되어 임계영역에 들어갈 수 있는지 확인하거나, 먼저 실행되어야 하는 프로세스가 실행되는지 확인
  2. 조건을 만족하면 wait을 빠져나와 임계영역으로 진입
  3. 이후 signal이 호출되어 임계영역에서 빠져나왔음을 알림

3-4. 뮤텍스 vs 세마포어

	뮤텍스	세마포어
개념	· 자원을 점유한 프로세스나 스레드가 잠시 소유했다가 작업이 끝나면 반환 · 세마포어의 바이너리 값을 가짐	자원의 상태를 나타내는 일종의 변수(소유 X)
호환	X(세마포어가 될 수 없음)	O(뮤텍스가 될 수 있음)
생명주기	· 시스템 범위에 걸쳐있음 · 파일 시스템 상의 파일 형태로 존재	· 프로세스 범위를 가짐 · 프로그램이 종료될 때 자동으로 삭제
사용범위	동기화 대상이 하나일 때	동기화 대상이 여러개일 때

3-5. 모니터(Monitor)

• 하나의 프로세스 내의 다른 스레드 간 동기화에 사용
• 프레임워크나 라이브러리 그 자체에서 제공
• C언어에는 없고 Java에는 존재
• 일련의 동기화 작업들이 캡슐화되어 있어 키워드를 통해 편하게 동기화할 수 있음(ex. synchronized, wait(), notify())
  • wait, sifnal 설정 없이 함수 앞에 synchronized 키워드를 사용하기만 하면 상호배제하여 메서드 작업 수행

---

4. 데드락(DeadLock)

4-1. 정의

• 두 개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태
• 교착 상태라고도 부름

4-2. 발생 조건

다음 조건을 모두 충족할 경우 발생

조건	설명
상호배제 (Mutual exclusion)	프로세스들이 필요로 하는 자원에 대해 배타적인 통제권을 요구함
점유대기 (Hold and wait)	프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다림
비선점 (No preemption)	프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없음
순환대기 (Circular wait)	각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있음

4-3. 관리

4-3-1. 사전 방지

4-3-1-1. 예방

✅ 방법

방법	설명
상호배제 조건 제거	· 교착 상태는 두 개 이상의 프로세스가 공유 가능한 자원을 사용할 때 발생 · 공유 불가능한, 즉 상호 배제 조건을 제거하면 교착 상태를 해결할 수 있음
점유와 대기 조건 제거	한 프로세스에 수행되기 전에 모든 자원을 할당시키고 나서 점유하지 않을 때는 다른 프로세스가 자원을 요구하도록 하는 방법
비선점 조건 제거	비선점 프로세스에 대해 선점 가능한 프로토콜을 만들어 줌
환형 대기 조건 제거	· 자원 유형에 따라 순서를 매김 · 대부분의 접근들은 이 조건을 막음으로써 동작함

✅ 문제점

• 자원 사용의 효율성이 떨어지고 비용이 많이 소모됨

4-3-1-2. 회피

• 자원 요청 방법에 대한 추가 정보를 제공하도록 요구
• 시스템에 순환 대기가 발생하지 않도록 자원 할당 상태 검사

✅ 자원 할당 그래프 알고리즘(Resource Allocation Graph Algorithm)

• 정의

  • 자원이 1개일 때 사용하는 알고리즘
  • 교착 상태를 보다 정확하게 설명하기 위한 방향성 그래프

• 자료 구조

  • 정점 집합 𝑉와 edge 집합 𝐸로 구성(G = (V, E))
    

    • 𝑉의 노드 유형

      노드 유형	설명
      𝑇 = {𝑇1, 𝑇2, ⋯, 𝑇𝑛}	시스템의 모든 활성 스레드 집합
      𝑅 = {𝑅1, 𝑅2, ⋯, 𝑇𝑚}	시스템의 모든 리소스 집합

    • directed edge

      유형	상태	설명
      request edge	Ti → Rj	스레드 Ti가 Rj의 인스턴스를 요청
      assignment edge	Rj → Ti	Rj의 인스턴스가 스레드 Ti에 할당

• 교착 상태 판별

  cycle 존재 여부	교착 상태
  X	없음
  O	있을 수도 있고 없을 수도 있음

• 단점

  • 각 리소스 타입의 여러 인스턴스가 있는 리소스 할당 시스템에는 적용할 수 없음

✅ 은행원 알고리즘(Banker's Algorithm)

• 정의

  • 자원이 여러개일 때 사용하는 알고리즘
  • 프로세스의 상태(안정/불안정)를 사전에 검사하여 교착 상태 회피

• 자료 구조

  유형	설명	예시
  Available (𝑨𝒗𝒂𝒊𝒍𝒂𝒃𝒍𝒆[𝒎])	사용 가능한 자원의 수	𝐴𝑣𝑎𝑖𝑙𝑎𝑏𝑙𝑒[𝑗] == 𝑘 → 𝑅𝑗의 𝑘개의 인스턴스 사용 가능
  Max (𝑴𝒂𝒙[𝒏 × 𝒎])	프로세스 별 최대 자원의 요구 개수	𝑀𝑎𝑥[𝑖][𝑗] == 𝑘 → 𝑇𝑖가 𝑅𝑗의 최대 𝑘개의 인스턴스 요청 가능
  Allocation (𝑨𝒍𝒍𝒐𝒄𝒂𝒕𝒊𝒐𝒏[𝒏 × 𝒎])	현재 프로세스 별 할당되어 있는 자원의 수	𝐴𝑙𝑙𝑜𝑐𝑎𝑡𝑖𝑜𝑛[𝑖][𝑗] == 𝑘 → 𝑇𝑖가 현재 𝑅𝑗의 𝑘개의 인스턴스를 할당받고 있음
  Need (𝑵𝒆𝒆𝒅[𝒏 × 𝒎])	프로세스 별 남아있는 자원의 수	𝑁𝑒𝑒𝑑[𝑖][𝑗] == 𝑘 → 𝑇𝑖가 𝑅𝑗의 인스턴스를 𝑘개 더 요청

• 알고리즘

  1. Safety Algorithm

     현재 system의 snapshot이 safety한가를 판별

     1. Work를 사용 가능한 자원으로 설정하고, 모든 작업을 '시작 안 함'으로 표시한다.
     2. 완료되지 않았고, 필요한 것보다 작업 자원이 많은 작업을 찾는다. 찾을 수 없을 경우 4단계를 진행한다.
     3. 찾은 작업의 자원을 추가하고 '완료됨'으로 표시한 후, 2단계를 다시 확인한다.
     4. 모든 작업이 '완료됨'이면 시스템이 안전하다고 판단한다.

  2. Resource-Request Algorithm

     1. 요청한 자원이 필요한 최대량을 초과하면 오류를 발생시키고, 초과하지 않으면 다음 단계를 진행한다.
     2. 요청한 자원이 사용 가능하면 다음 단계를 진행하고, 부족하면 대기한다.
     3. 요청한 자원을 할당한 것처럼 가정하고 자원 상태를 업데이트한다.
     4. 위의 과정이 끝나면 request를 받아줬다 치고 다시 safety algorithm을 수행한다.
     5. safety algorithm이 safe하면 승인하고, not safe하면 거절한다.

• 단점

  • Resource Allocation Graph보다 덜 효율적이고 복잡함

10-3-2. 발생 후 처리

10-3-2-1. 무시

• 예방이나 회피 기법은 성능에 큰 영향을 미칠 수 있음
• 데드락의 발생 확률이 비교적 낮은 경우 별다른 조치를 취하지 않음
• UNIX와 Windows를 포함한 대부분의 OS에서 사용하는 기법

✅ 방식

1. 문제를 무시하고 교착상태가 시스템에서 발생하지 않은 척 한다.
2. 성능이 저하되면 시스템이 중단된다.
3. 필요하다면 사용자가 직접 재부팅을 해준다.

10-3-2-2. 발견

• 감시/발견을 하는 detection 알고리즘
• Deadlock이 발생했는지 체크함
• 성능에 큰 영향을 미칠 수 있음

10-3-2-2-1. 유형

✅ single instance

• wait-for graph 유지

  💡 wait-for graph
  Resource Allocation Graph에서 변형된 형태

• 주기적으로 알고리즘을 실행하여 wait-for graph에서 cycle이 있는지 검사함(스레드간의 관계만 확인)
  

✅ multiple instances

• wait-for graph로 해결이 불가능함

• Banker's Algorithm과 흡사한 알고리즘을 적용함

• 자료 구조

  유형	설명	예시
  𝑨𝒗𝒂𝒊𝒍𝒂𝒃𝒍𝒆[𝒎]	사용 가능한 자원의 수	-
  𝑨𝒍𝒍𝒐𝒄𝒂𝒕𝒊𝒐𝒏[𝒏 × 𝒎]	현재 프로세스 별 할당되어 있는 자원의 수	-
  𝑹𝒆𝒒𝒖𝒆𝒔𝒕[𝒏 × 𝒎]	각 스레드의 현재 요청	𝑅𝑒𝑞𝑢𝑒𝑠𝑡[𝑖][𝑗] == 𝑘 → 𝑇𝑖가 𝑅𝑗의 인스턴스를 𝑘개 더 요청

• Detection Algorithm

  • 몇 가지 부분을 제외하고는 Banker's Algorithm과 동일
    • 데드락 발생 여부와 safety를 판별하지 않음