기술 면접 대비 CS 핵심 요약 - 프로세스 동기화, 교착 상태

2023.09.07 - [CS] - 기술 면접 대비 CS 핵심 요약 - 프로세스의 생성

기술 면접 대비 CS 핵심 요약 - 프로세스의 생성

2023.09.08 - [CS] - 기술 면접 대비 CS 핵심 요약 - 프로세스 상태, 멀티 프로세스 vs 멀티 스레드

기술 면접 대비 CS 핵심 요약 - 프로세스 상태, 멀티 프로세스 vs 멀티 스레드

 

 

📕본 포스팅은 "기술면접 대비 CS 전공 핵심 요약집" 책을 공부하면서 정리한 내용입니다.

---

1.2.7 프로세스 동기화 ( 중요도 ★★★ )

 

경쟁 상태(race condition)

여러 프로세스 또는 스레드에서 하나의 공유 자원에 접근하는 경우, 자원에 접근하는 순서에 따라 결과값이 달라질 수 있다

이러한 공유 자원에 동시에 접근해 경쟁하는 상태를 경쟁 상태라 함

 

우유 문제(too much milk problem)

냉장고에 우유가 다 떨어져서 새로 사야하는 상황을 가정하자.

• 엄마, 아빠 : 프로세스
• 냉장고 : 공유자원

경쟁 상태 예시

 

1. 엄마가 냉장고를 열어 우유가 없는 것을 확인
2. 엄마가 우유를 사러 슈퍼마켓에 감
3. 엄마가 우유를 사서 집에 돌아오는 길에 아빠가 냉장고에 우유가 없는 것을 확인
4. 아빠가 우유를 사러 슈퍼마켓에 감
5. 아빠가 우유를 사서 집에 돌아옴

 

우유가 0개에서 1개가 되길 기대했지만, 2개가 되는 이런 문제를 해결하려면 프로세스 동기화가 이뤄져야 함

 

---

 

임계 영역(critical section)

• 공유 자원에 접근할 수 있고 접근 순서에 따라 결과가 달라지는 코드 영역
• 냉장고에 우유 유무를 판단하고, 우유를 추가하는 부분이 임계 영역에 해당.

임계 영역에서 경쟁 상태가 발생하는 걸 방지하려면 여러 프로세스가 공유 자원에 접근해도 데이터의 일관성이 유지되도록 프로세스 동기화(process synchronization)를 해야함

 

• 상호배제 기법(mutual exclusive) : 어떤 프로세스가 임계영역을 실행 중일 때 다른 프로세스가 임계 영역에 접근할 수 없다.
  • ex) 뮤텍스 세마포어
• 진행(progress) : 임계 영역을 실행 중인 프로세스가 없을 때 다른 프로세스가 임계영역을 실행
• 한정된 대기(bounded waiting) : 임계 영역에 접근을 요청했을때 무한한 시간을 기다리지 않는다.

 

---

 

뮤텍스(mutex)

 

뮤텍스는 락(lock)을 가진 프로세스만이 공유 자원에 접근할 수 있게 하는 방법

 

화장실(toilet example)

화장실과 화장실 열쇠가 하나 뿐인 식당이 있다고 가정하자.

• 화장실 : 공유자원을 포함한 임계 영역
• 열쇠 : 락
• A, B : 공유 자원에 접근하려는 프로세스

뮤텍스 예

1. 식당에는 화장실 하나 칸과 화장실 문을 열 수 있는 열쇠가 한 개 있다.
2. A가 열쇠를 가지고 화장실에 간다.
3. 화장실에 가려던 B는 열쇠가 없어서 기다린다.
4. A가 화장실에서 나와 열쇠를 반납하면, 기다리던 B가 열쇠를 가지고 화장실에 간다.

 

임계 영역에 먼저 접근한 프로세스가 임계 영역에 락을 걸면 달느 프로세스들은 해당 프로세스가 락을 해제하기 전까지 대기해야 함.

 

• 락킹 매커니즘 (locking mechanism) : 임계 영역에 접근한 프로세스가 임계 영역에 락을 건다
• 스핀락(spinlock) : 임계 영역에 접근하지 못한 프로세스는 락을 얻기 위해 기다리는 동안 락이 풀렸는지 반복문을 돌면서 확인하면서 기다린다. - 바쁜 대기(busy waiting)의 종류

 

바쁜 대기 : 프로세스가 공유 자원에 접근할 수 있는권한을 얻을 때 까지 확인하는 과정

 

---

 

세마포어(semaphore)

공유 자원에 접근할 수 있는 프로세스의 수를 정해 접근을 제어하는 방법

 

화장실(toilet example)

• 화장실 : 공유자원을 포함한 임계 영역
• 화장실 개수(열쇠 개수) : 공유 자원에 접근할 수 있는 프로세스 수를 제어하기 위한 정수 변수
• A, B, C, D : 공유 자원에 접근하려는 프로세스

세마포어 예

1. 식당에 화장실 3칸, 화장실을 열 수 있는 열쇠 3개가 있다
2. A가 화장실 열쇠 하나를 가지고 화장실에 간다. 열쇠는 2개 남는다
3. B, C가 열쇠를 하나씩 가지고 화장실에 간다. 남은 열쇠가 없어서 D는 화장실에 가지 못한다.
4. C가 화장실에서 나와 열쇠를 돌려놓으면 D가 화장실에 간다.

 

임계 영역에 접근할 수 있는 키 n개를 지정하고 이 중 하나를 가진 프로세스만이 임계 영역에 접근하게 되는 방식

시그널링 매커니즘(signaling mechanism) : 공유 자원에 접근한 프로세스가 접근을 해제하면 다른 프로세스가 접근할 수 있도록 신호를 보낸다.

 

 

동기와 비동기(작업 순서에 대한 개념) vs 블로킹과 넌블로킹 (작업을 위한 대기를 구분하는 개념)

• 동기(synchronization) : 여러 작업을 처리할 때 작업 순서를 보장
• 비동기(asynchronization) : 여러 작업을 처리 할때 작업 순서를 보장하지 않음
• 블로킹(blocking) : 작업을 수행할 때 대기할 수 있다는 것을 의미, 작업 순서를 보장하지 않음
• 넌블로킹(non-blocking) : 작업을 시작하면 대기 없이 수행한다는 것을 의미

 

 

1.2.8 교착 상태(deadlock) ( 중요도 ★★★ )

 

상호 배제 기법때문에 2개 이상의 프로세스가 각각 자원을 가지고 있으면서 서로의 자원을 요구하며 기다리는 상태

 

필요 충분 조건 4가지

• 상호배제(mutual exclusion) : 하나의 공유 자원에 하나의 프로세스만 접근할 수 있다.
• 점유와 대기(hold and wait) :  프로세스가 최소 하나의 자원을 점유하고 있는 상태에서 추가로 다른 프로세스에서 사용 중인 자원을 점유하기 위해 대기한다.
• 비선점(non-preemption) : 다른 프로세스에 할당된 자원을 뺏을 수 없다.
• 환형 대기(circular wait) : 프로세스가 자신의 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구한다.

 

교착 상태를 막으려면 필요 충분 조건 4가지 중 한 가지를 제거하면 된다.

• 상호배제 부정 : 여러 프로세스가 동시에 하나의 공유 자원을 사용할 수 있게 한다.
• 점유와 대기 부정 : 프로세스가 실행되기 전에 필요한 모든 자원을 할당함으로써 프로세스 대기를 없앤다. 프로세스가 자원을 점유하지 않은 상태에서만 자원을 요구하게 한다.
• 비선점 부정 : 자원을 점유한 프로세스가 다른 자원을 요구할 때 점유한 자원을 반납하게 한다.
• 환형 대기 부정 : 자원을 선형 순서로 정렬해 고유 번호를 할당한다. 그리고 각 프로세스에서 요구할 수 있는 번호의 방향을 정해서 한쪽 방향으로만 자원을 요구하게 한다.

 

교착 상태의 필요 충분 조건을 외우는게 아니라 이해해야 한다!

 

각 프로세스를 사람이라고 생각하자. 프로세스 1이 자원 1을, 프로세스 2가 자원 2를 가지고 있는 상황에서 프로세스 1이 자원2가 필요하고, 프로세스2는 자원1이 필요해 교착상태가 발생한다.

 

교착 상태 개념

 

• 상호배제 - 하나의 공유 자원에 대해 하나의 프로세스만 사용할 수 있다는 개념. 만약 하나의 공유 자원을 여러 프로세스에서 공유할 수 있다면 위의 그림을 성립할 수 없다. 자원을 공유할 수 있게 되면 서로의 자원을 기다리는 상황을 예방할 수 있다.
• 점유와 대기 - 하나의 프로세스가 이미 자원을 가진 상태에서 다른 프로세스의 자원을 갖기 위해 기다리는 상황, 프로세스가 자원을 요구할 때 필요한 자원1과 자원2를 모두 주거나 가진 자원이 없는 경우에만 할당함으로써 문제를 해결할 수 있다.
• 비선점 - 다른 프로세스가 가지고 있는 자원을 뺏을 수없다는 개념. 프로세스 1이 프로세스 2의 자원을 뺏을 수 있게하면 서로의 자원을 가직 위해 대기하는 상황을 예방할 수 있다.
• 환형 대기 - 프로세스 1이 프로세스 2의 자원을 요구하고, 프로세스 2가 프로세스 1의 자원을 요구함으로써 발생, 그림과 같이 각자의 자원을 가진 상태에서 상대방의 자원을 요구하는 상황. 이때 작은 번호 프로세스가 큰 번호 프로세스의 자원을 요구하는 것만 가능하게 한다면 프로세스 2가 프로세스 1의 자원을 요구할 수 없게 되므로 환형 대기를 없앨 수 있다.