[운영체제 3기] 4주차 스터디 정리

Concurrency vs Parallelism

🔹병행성/동시성 (Concurrency)

동시에 실행되는 것처럼 보이는 것

• 논리적인 개념
• 싱글 코어 멀티 스레드
  • Time-sharing을 통해 CPU를 나누어 사용함으로서 동시성 구현
  • 병렬이 아닌 순차적인 동작
  • CPU가 1개이기 때문에 context switching 발생
• 멀티 코어 멀티 스레드

🔹병렬성 (Parallelism)

실제로 동시에 작업이 처리되는 것

• 물리적인 개념
• 멀티 코어 멀티 스레드
• 데이터 병렬성과 작업 병렬성
  • 데이터 병렬성: 같은 작업의 전체 데이터를 서브 데이터로 나누어 같은 작업을 동시에 처리
  • 작업 병렬성: 서로 다른 작업을 동시에 처리

🔹프로세스 동기화(Synchronization)

프로세스 동기화란 동시에 접근할 수 없는 자원에 하나의 프로세스만 접근하도록 하기 위해 프로세스의 실행 순서를 제어하여 데이터의 일관성을 유지하는 과정을 말한다.

이러한 프로세스 동기화는 프로세스 간 협력 방법(IPC) 중 하나인 공유 메모리(Shared Memory) 방식과 같이 서로 다른 프로세스 간 주소를 공유하여 데이터를 주고받는 상황에 꼭 필요하다.

그 이유는 아래 내용에 순차적으로 작성되어 있다.

🔹임계 영역(Critical Section)

임계 영역이란 둘 이상의 스레드가 동시에 접근해서는 안되는 공유 자원을 접근하는 코드의 일부를 의미한다.

다음과 같은 코드를 예로 들 수 있다. 아래 코드는 뮤텍스를 구현한 예시이다.

do {
      wait(mutex);   //입장 구역(entry section)
      임계 구역(critical section)
      signal(mutex); //퇴장 구역(exit section)
      나머지 구역(remainder section)
} while (1);

각 프로세스가 임계 영역에 진입하려면 진입 허가를 요청해야 하는데, 이 부분을 입장 구역(entry section)이라고 한다. 임계 영역에서 필요한 작업을 처리한 후 임계 영역을 나오면, 임계 영역을 퇴장했다는 것을 알려주는 코드인 퇴장 구역(exit section)이 있다.

 

프로세스가 임계 구역에 동시에 접근하게 되면 경쟁 상태(Race Condition)가 되어 자원의 일관성이 깨진다.

🔹경쟁 상태(Race Condition)

경쟁 상태(Race Condition)란 두 개 이상의 프로세스가 공유 자원을 병행적(Concurrently)으로 접근하여 읽기/쓰기 동작을 수행할 때, 공유 자원에 대한 접근 순서나 입력 또는 조작 타이밍에 따라 실행 결괏값이 달라지는 현상을 말한다.

 

🤨 경쟁 상태 문제를 어떻게 해결해야 하나?

경쟁 상태(Race Condition)을 막기 위해서는 상호 배제(Mutual Exclusion)가 필요하다.

🔹상호 배제(Mutual Exclusion)

상호 배제(Mutual Exclusion)란 둘 이상의 프로세스가 동시에 임계 영역(Critical Section)에 진입하는 것을 막는 것을 의미한다.

하나의 프로세스가 공유 자원을 사용하고 있으면 다른 프로세스들이 그 자원을 사용하지 못하도록 막으면 경쟁 상태(Race Condition) 문제를 피할 수 있다.

 

🥸 상호 배제 기본 연산 (Mutual Exclusion Primitive)

▪️ enterCS() primitive

• 임계 영역 진입 전 다른 프로세스가 임계 영역 안에 있는지 검사
• 임계 영역에 다른 프로세스가 있다면 비어 있을 때까지 대기

▪️ exitCS() primitive

• 임계 영역을 벗어날 때 후처리 과정
• 임계 영역을 벗어났음을 표시

😎 상호 배제 구현 조건

1. Mutual Exclusion (상호 배제)

• 임계 영역에 프로세스가 있을 경우, 다른 프로세스의 진입 금지

2. Progress (진행)

• 임계 영역에 다른 프로세스가 없을 경우 임계 영역 진입 가능

3. Bounded waiting (유한/한정 대기)

• 프로세스의 임계 영역 진입은 유한한 시간 내에 허용되어야 함
• 기아 상태(Starvation) 방지: 무한 대기 금지

🤓 상호 배제 구현 방법

상호 배제를 위한 프로세스 동기화 방식은 대표적으로 뮤텍스(Mutex), 세마포어(Semaphore)가 있다.

🔹뮤텍스(Mutex)

뮤텍스(Mutex)는 상호 배제를 위한 프로세스 동기화 방식 중 하나로 두 가지 연산을 제공하는데, Locking 방식을 사용하여 lock을 건 스레드만 임계 영역을 나갈 때 유일하게 unlock 할 수 있다.

lock: 현재 임계 영역에 들어갈 권한을 부여 받는다. 만일 다른 프로세스가 임계 영역을 사용 중이라면 종료할 때까지 대기한다.(entry section)

unlock: 대기 중인 다른 프로세스들이 임계 영역을 진입할 수 있도록 현재 임계 영역을 모두 사용했음을 알려준다.(exit section)

다음은 뮤텍스를 사용한 상호 배제 구현 예시 코드이다.

do {
      wait(mutex);   //입장 구역(entry section)
      임계 구역(critical section)
      signal(mutex); //퇴장 구역(exit section)
      나머지 구역(remainder section)
} while (1);

🔹세마포어(Semaphore)

세마포어(Semaphore)도 마찬가지로 상호 배제를 위한 프로세스 동기화 방식 중 하나로, 공유 자원에 여러 프로세스가 접근하는 것을 막는 것이다.

세마포어 종류

▪️ Binary semaphore (이진)

• S가 0과 1 두 종류의 값만 갖는 경우
• 상호 배제나 프로세스 동기화 목적으로 사용
• 이는 뮤텍스로도 사용 가능

▪️ Counting semaphore (카운터)

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

세마포어 연산

세마포어는 크게 초기화 연산 S와 P(), V() 연산이 있다.

모든 연산은 Atomic 연산이다. 즉, 연산이 완전히 수행되거나 전혀 수행되지 않아야 한다.

▪️ S - 세마포어 값

▪️ P() or wait() - 중요한 처리 부분 들어가기 앞서 P() 함수를 실행해 잠금 기능 수행

▪️ V() or signal() - 처리를 마치면 V() 함수를 실행해 잠금 해제

/* P(S) or wait(S) 연산 */
P(S) { /* 잠금 */
   if (S > 0)
      then S <- S - 1; // 자원 획득
      else wait on the queue Qs;
}

Critical Section Code /* 임계 영역 */

/* V(S) or signal(S) 연산 */
V(S) { /* 잠금 해제 */
   if (∃ waiting processes on Qs)
      then wakeup one of them;
      else S <- S + 1; // 자원 해제
}

 

스핀락(Spinlock)을 이용한 세마포어 방식은 다음과 같이 될 수 있다.

이 경우에는 스핀락의 특성상 Busy waiting 문제가 발생할 수 있다.

*. Busy waiting(바쁜 대기): 임계 영역에서 작업 중인 스레드 B를 기다리는 A는 임계 영역 들어갈 수 있을 때까지 아무런 작업을 하지 않고 임계 영역에 접근 가능한지 무한 검사만 하고 있는 상황

wait(S) {
  while (S <= 0);  // 자원이 없다면 while 루프를 돌며 대기를 함.
  S--;  // 자원을 획득함.
}

signal(S) {
  S++;  // 자원을 해제함.
}

🔹뮤텍스 vs 세마포어

첫 번째 차이점 : 허용되는 프로세스/스레드 수

세마포어: 하나의 프로세스/스레드만 들어가게 할 수도 있고, 여러개의 프로세스/스레드가 들어갈 수도 있다. 

뮤텍스: locking 방식을 사용하여 여러 프로세스/스레드의 접근을 막고 있기 때문에 두 개 이상의 프로세스/스레드가 동시에 사용할 수 없고 오직 한 번에 하나의 프로세스/스레드만이 공유 자원에 접근할 수 있다.

 

두 번째 차이점 : 카운팅 수

뮤텍스: 보통 0 또는 1의 이진 상태를 가지며, lock/unlock 상태를 제어하는 데 사용된다. 따라서, 이진 세마포어(Binary semaphore)는 뮤텍스로 사용할 수 있다.

세마포어: 보통 0 이상의 정수 값을 가지며, 허용되는 동시 접근 스레드 수를 나타내는 역할을 한다.

 

세 번째 차이점: 소유권

뮤텍스: lock을 건 스레드가 다시 lock을 해제하기 전까지는 다른 스레드가 해당 뮤텍스를 얻을 수 없다. 

세마포어: 소유 개념이 없다. 어떤 스레드든지 세마포어 값을 변경할 수 있다.

🔹모니터(Monitor)

세마포어는나 뮤텍스는 잘못 사용하였을 경우 timing error가 발생할 수 있다.

timing error는 주로 다음과 같은 상황에서 발생한다.

1. P()와 V() 연산의 순서가 바뀌었을 경우

2. P()나 V() 중 하나라도 누락이 되었을 경우

 

이를 해결하기 위한 high-level mechanism 중 하나가 모니터(Monitor)이다.

모니터(Monitor)란 상호 배제와 조건부 예외처리를 지원하기 위한 동기화 도구 중 하나이다. 모니터는 프로그래밍 언어의 일부로서, 고급 언어에서 제공되는 추상화된 동기화 개념이다.

 

모니터 특징

1. 모니터의 가장 큰 특징은 Information hiding(정보 은폐)이다. 이 의미는 공유 데이터(shared data)는 오직 모니터 내의 프로세스들만 접근이 가능하다는 것이다.

2. 또 다른 특징 중 하나는 한 시점에서 하나의 프로세스만 접근 가능하다는 것이다.

모니터에 대한 구조는 다음 그림을 참고해서 설명하겠다.

🖥️ 모니터 구성 요소

▪️ Mutual Exclusion Queue /  Entry Queue (상호 배제 큐, 진입 큐) : 모니터에 진입하려는 프로세스들의 큐

▪️ Shared Resource / Shared data (공유 자원 / 공유 데이터) : 모니터 내부에 존재하는 공유 자원, 여러 프로세스들이 순차적으로 접근하여 사용 가능

▪️ Procedure (프로시저) : 공유 자원에 접근하기 위한 접근 함수, 한 프로세스가 프로시저를 사용해 공유 자원을 사용하고 있다면 다른 프로세스들은 접근 불가

▪️ Initialization code (초기화 코드) : 공유 자원을 초기화해주는 코드

▪️ Condition variable (조건 변수) : 모니터에 접근하는 프로세스들의 순서를 보장하기 위한 동기화 변수로, wait()과 signal() 연산에 의해서만 접근 가능

 

아래 예제와 같이 monitor 블록 내부에 선언된 함수들은 모두 동기화 된다.

monitor {
    function p1(..){}
    function p2(..){}
    function p3(..){}
}

 

이때 모니터 자체적으로 동기화 처리하기는 어렵기 때문에 조건 변수(Condition Variable)를 정의하여 동기화 메커니즘을 제공해주어야 한다. 이러한 조건 변수(Condition Variable)도 모니터 내부에서만 접근 가능하다.

condition x y; // 조건 변수 선언
x.wait();
y.signal();

 

이때 조건 변수(Condition Variable) 별로 대기 큐(waiting queue)가 분리되어 동기화가 된다.

 

x.wait()

- 프로세스가 조건 x에서 대기해야 할 때 호출

- 호출한 프로세스를 조건 x와 관련된 대기 큐(waiting queue)에서 일시 중지(block)

 

y.signal()

- 프로세스가 조건 y의 변화를 발견했을 때 호출

- y.wait()에 의해 중지되어 있던 프로세스의 수행을 다시 재개

- 조건 y에서 중지된 프로세스가 여러 개일 경우: 이 중 하나 선택

- 조건 y에서 중지된 프로세스가 없을 경우: 아무 것도 하지 않음

- 일시 중지된 프로세스가 재개되면, signal을 보낸 프로세스는 반드시 wait을 해야 함

🔹교착 상태(Deadlock)

교착 상태(Deadlock)란 두 개 이상의 프로세스나 스레드가 서로 상대방이 가진 자원을 기다리고 있어서 더 이상 진행하지 못하는 상태를 말한다.

starvation과 deadlock 발생 지점

📌 교착 상태 발생 필요 조건

아래 4가지 조건을 모두 만족할 경우 교착 상태가 발생한다.

1. Exclusive use of resources (배타적 사용)

• 한 순간에 한 프로세스만 사용 가능한 자원

2. Non-preemptible resources (비선점 자원)

• 선점 당하면 이후 진행에 문제가 발생하는 자원
• 선점이 불가능한 자원

3. Hold and wait(Partial allocation) (점유 대기, 부분 자원 할당)

• 하나의 자원을 점유(hold)한 상태에서 다른 프로세스가 사용하는 자원을 대기(wait)

4. Circular wait (원형 대기)

• 자신의 자원은 보유한 채로 서로 상대방 자원을 요청할 때 원형 사이클이 생기는 현상

📌 교착 상태 막는 방법

1. Deadlock prevention (예방)

4개의 교착 상태 발생 필요 조건 중 하나를 제거하면 된다.

이 방법은 교착 상태가 절대 발생하지 않는다.

• Exclusive use of resources 조건 제거
  • 모든 자원 공유를 허용
  • 현실적으로 불가능
• Non-preemptible resources 조건 제거
  • 모든 자원에 대해 선점 허용
  • 현실적으로 불가능
• Hold and wait 조건 제거
  • 필요 자원 한 번에 모두 할당 (Total allocation)
  • 자원 낭비 발생 → 필요하지 않은 순간에도 가지고 있음
  • 무한 대기 현상 발생 가능
• Circular wait 조건 제거
  • Totally allocation을 일반화한 방식
  • 자원들에게 순서 부여
  • 프로세스는 오름차순 방향으로만 자원 요청 가능 → 자원 낭비 발생

2. Deadlock avoidance (회피)

Deadlock avoidance는 시스템 상태를 계속 감시하면서 deadlock 상태가 될 가능성이 있는 자원 할당 요청을 보류하는 것을 말한다.

즉, 시스템을 항상 safe state로 유지하는 것을 의미한다.

▪️ safe state: 모든 프로세스가 정상적으로 종료가 가능한 상태, deadlock 상태가 되지 않을 수 있음을 보장

▪️ unsafe state: deadlock 상태가 될 가능성이 있음, 반드시 발생한다는 의미는 아님

 

Deadlock avoidance 가정

- 프로세스 수가 고정됨

- 자원의 종류와 수가 고정됨

- 프로세스가 요구하는 자원 및 최대 수량을 알고 있음

- 프로세스는 자원 사용 후 반드시 반납

 

대표적인 알고리즘

• Dijkstra's algorithm - Banker's algorithm
• Habermann's algorithm

자원 요청에 대한 safe state을 확인하고 안전한 경우에만 자원을 할당한다.

즉, safe sequence(안전 상태를 유지하는 자원 할당 순서)가 있는 경우에만 할당한다.

 

3. Deadlock detection and deadlock recovery (탐지 및 복구)

Deadlock을 탐지하고, deadlock인 경우 해결하는 과정

 

Deadlock detection

- Deadlock 방지를 위한 사전 작업을 하지 않음 (Deadlock 발생 가능)

- 주기적으로 deadlock 발생 확인

• 시스템이 deadlock 상태인가?
• 어떤 프로세스가 deadlock 상태인가?

- Resource Allocation Graph (RAG) 사용하여 deadlock 탐지

• 주어진 RAG에서 간선(edge)를 하나씩 지워가는 방법
• 모든 간선이 제거될 경우 deadlock에 빠진 프로세스가 없는 것
• 지울 수 없는 간선이 존재하면 하나 이상의 프로세스가 deadlock 상태

Deadlock recovery

- Process termination(프로세스 종료): Deadlock 상태인 프로세스 중 일부 종료

- Resource preemption(자원 선점)

• Deadlock 상태 해결을 위해 선점할 자원 선택
• 해당 자원을 가지고 있는 프로세스를 종료시킴
  • Deadlock 상태가 아닌 프로세스가 종료될 수도 있음
  • 해당 프로세스는 이후 재시작됨

 

내 블로그: [운영체제 3기] 2주차 스터디 정리

https://nesoy.github.io/articles/2018-09/OS-Concurrency-Parallelism

https://memostack.tistory.com/49

https://www.robotstory.co.kr/raspberry/?vid=149

https://ko.wikipedia.org/wiki/%EC%9E%84%EA%B3%84_%EA%B5%AC%EC%97%AD

https://ko.wikipedia.org/wiki/%EA%B2%BD%EC%9F%81_%EC%83%81%ED%83%9C

https://iredays.tistory.com/125

https://yoongrammer.tistory.com/63

https://www.baeldung.com/cs/concurrency-vs-parallelism

https://yoongrammer.tistory.com/60

https://benlee73.tistory.com/11

https://velog.io/@octo__/%EB%AE%A4%ED%85%8D%EC%8A%A4Mutex

https://hpckoreatech.notion.site/Operating-System-CSE132-2023-b8aa98fe69cc4a8cb950051a04bc35ca

https://velog.io/@moonheekim0118/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%EB%AA%A8%EB%8B%88%ED%84%B0-Monitor

https://yonghwankim-dev.tistory.com/323

https://hyunah-home.tistory.com/entry/Monitor%EB%9E%80

https://coding-gongbu.tistory.com/47

https://blog.naver.com/kgr2626/222118655167

https://velog.io/@holim0/6.-%EA%B5%90%EC%B0%A9-%EC%83%81%ED%83%9CDeadlock