📃 동기화와 데드락

동시성(Concurrency)과 병렬성(Parallelism)

• 동시성(Concurrency)은 빠르게 전환하며 여러 작업을 수행해 여러 작업이 동시에 실행되는 것처럼 보이게 수행하는 것이다. 한 개의 코어에서도 동시성이 일어나고 작업 간에 문맥교환이 일어난다.
• 동시성의 문제점은 동기화 문제가 발생할 수 있다.
• 병렬성(Parallelism)은 여러 코어에서 여러 작업을 동시에 수행하는 것이다. 코어가 하나라면 병렬성이 발생할 수 없다.
• 병렬성의 문제점은 여러 작업을 동시에 수행해서 Race Condition, 동기화 문제가 발생할 수 있다.
• 동시성과 병렬성은 동기화 문제가 발생할 수 있다는 공통점을 가지고 있다.

---

프로세스의 동기화

• 프로세스 동기화는 프로세스 사이의 수행 시기를 맞추는 것이다.
• 프로세스 동기화를 할 경우 실행 순서가 제어되고 상호 배제가 된다.

---

임계 구역(Critical Section)

• 접근해서는 안되는 공유 자원(파일, 입출력, 공유 데이터 등)에 접근하는 명령문 또는 코드의 일부 영역을 말한다.

---

레이스 컨디션(Race Condition)

• 잘못된 실행으로 인해 여러 프로세스가 동시에 임계 구역의 코드를 실행하여 공유 자원의 일관성을 헤치는 현상이다.
• 레이스 컨디션을 해결하는 방법은 대표적으로 상호 배제, 진행, 유한 대기를 통해서 해결할 수 있다.

상호 배제(Mutual Exclusion)

• 하나의 프로세스가 임계 구역에서 실행되고 있으면, 다른 프로세스는 임계 구역에서 실행될 수 없는 것이다. 공유가 불가능한 자원의 동시 사용을 피할 수 있다.

진행(Progress)

• 임계 구역에서 실행되고 있는 프로세스가 없을 경우, 임계 구역에 들어갈 적절한 프로세스를 선택하는 것이다.

유한 대기(Bounded Waiting)

• 프로세스의 기아를 방지하기 위해, 한 번 임계 구역에서 실행된 프로세스는 다음 실행에 제한을 두는 것이다.

---

상호 배제 방식(뮤텍스, 세마포어, 모니터)

뮤텍스(Mutual Exclusion)

• 뮤텍스(Mutual Exclusion)는 상호 배제를 위한 동기화 도구이다.

• 임계 구역에 진입하는 프로세스는 현재 임계 구역에 있음을 알리기 위해 락을 사용한다. 다른 프로세스는 임계 구역에 락이 걸려있으면 기다리고 락이 없다면 임계 구역에 진입할 수 있다.

• acquire 함수는 프로세스가 임계 구역에 진입하기 전에 호출하는 함수이다. 만약 임계 구역이 잠겨있다면 열릴 때 까지(lock이 false가 될 때까지) 임계 구역을 반복적으로 확인하고 임계 구역이 열려있다면 잠그는(lock을 true로 바꾸는) 함수이다.

• release 함수는 임계 구역에서 작업이 끝나고 호출하는 함수이다. 현재 잠긴 임계 구역을 열어주는(lock을 false로 바꾸는) 함수이다.

• acquire 함수는 임계 구역이 잠겨있을 경우 반복적을 lock을 확인하는데, 이것은 바쁜 대기(Busy Wait)라고 한다.

세마포어(Semaphore)

• 세마포어는 공유 자원이 여러 개 있는 상황에서 적용되는 동기화 도구이다. 사용하고 있는 프로세스의 수를 공통으로 관리하는 하나의 값을 이용해 상호 배제를 달성한다.
• 사용 가능한 공유 자원의 개수를 나타내는 전역 변수 S, 임계 구역에 들어갈지 말지 알려주는 wait 함수, 임계 구역 앞에서 기다리는 프로세스가 들어가도 괜찮다는 신호를 주는 signal 함수로 구성되어 있다.

뮤텍스와 세마포어의 차이??

• 동기화 대상의 개수에 차이가 있다. 뮤텍스는 동기화 대상이 1 개지만, 세마포어는 동기화 대상이 여러 개이다.

모니터(Monitor)

• 모니터는 세마포어의 한계를 보완하고 고 차원적인 비동기 방법으로 상호 배제를 제공하는 동기화 도구이다.
• 세마포어는 wait함수와 signal함수를 매번 임계 구역 앞 뒤에 명시해야 한다. 그래서 프로그래머의 실수로 인해 함수의 순서 문제나 함수를 중복으로 사용하는 문제점이 발생할 수 있다.(wait → signal 순서를 지켜야함)
• 모니터는 공유 자원과 공유 자원에 접근하기 위한 인터페이스(통로)를 묶어 관리한다. 그리고 프로세스는 반드시 인터페이스를 통해서만 공유 자원에 접근하도록 한다.

---

데드락, 교착 상태

• 데드락은 두 개 이상의 프로세스가 서로 자원을 얻지 못해 진행을 못하고 무한히 다음 자원을 기다리는 상태를 말한다.
• 프로세스를 실행하기 위해서는 자원이 필요하기 때문이다.
• 데드락이 발생하는 조건은 대표적으로 상호 배제, 점유와 대기, 비선점, 원형 대기가 있다.
• 상호 배제는 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때 데드락이 발생할 수 있다.
• 점유와 대기는 프로세스가 어떠한 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다릴 때 데드락이 발생할 수 있다.
• 비선점은 어떤 프로세스도 다른 프로세스의 자원을 강제로 뺏지 못하기 때문에 데드락이 발생한다.
• 원형 대기는 자원 할당 그래프가 원의 형태로 그려지면 데드락이 발생한다. 하지만 원의 형태라고 해서 항상 교착 상태가 발생하는 것이 아니다.

데드락 회피 방법 3가지

데드락 조건 예방

• 데드락 발생 조건 4가지 조건 중 하나라도 발생하지 않게 하는 것이 데드락 예방 방법이다.

• 상호 배제 조건 방지는 한 번에 여러 프로세스가 고유 자원을 사용할 수 있게 하는 것이다. 하지만 동기화와 관련된 문제가 발생할 수 있다.

• 점유와 대기 조건 방지는 점유와 대기를 없애 운영체제가 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분하는 것이다. 하지만 자원의 활용율이 낮아진다.

• 비선점 조건 방지는 비선점 조건을 없앴을 때 자원을 이용 중인 프로세스로부터 해당 자원을 빼앗을 수 있는 것이다. 하지만 모든 자원이 항상 선점이 가능한 것이 아니다.

• 원형 대기 조건 방지는 모든 자원에 순서를 정해 오름차순으로 자원을 할당하여 원형 대기가 발생하지 않는 것이다. 하지만 수 많은 자원에 순서를 정하는 일은 많은 부담이 되고 특정 자원의 활용률이 떨어질 수 있다.

데드락 조건 회피

• 데드락 상태가 발생하지 않을 정도로 자원을 조금씩 할당하는 방식이다.
• 자원을 할당한 후에도 시스템이 항상 Safe State에 있을 수 있도록 할당을 허용하는 것이다.
• Safe State는 데드락이 발생하지 않고 모든 프로세스가 정상적을 자원을 할당받고 종료될 수 있는 상태를 말한다.
• Unsafe State는 안정 상태가 아닌 상태를 말한다.
• Safe Sequence는 데드락이 발생하지 않으면서 프로세스들에 자원을 할당할 수 있는 순서를 의미한다.
• 이러한 특징을 살린 대표적인 알고리즘이 은행원 알고리즘이다.
• 은행원 알고리즘을 통해 자원 할당량을 사전에 파악하고 데드락을 회피할 수 있다.
• 하지만 미리 최대 자원 요구량을 알아야하고, 할당할 수 있는 자원 수가 일정해야하는 등 사용에 있어 제약 조건이 많다.

데드락 탐지 후 회복

• 데드락이 발생한 후 회복하기 위해 사용하는 방식이다.
• 탐지 기법은 자원 할당 그래프를 통해 데드락을 탐지한다. 데드락을 탐지 기법을 통해 발견했다면, 순환 대기에서 벗어나 데드락으로부터 회복 하기 위한 방법을 사용한다.
• 회복 기법은 선점을 통한 회복하는 방식과 프로세스를 종료해 회복하는 방식이 있다.
• 선점을 통한 회복은 데드락이 해결될 때까지 다른 프로세스로부터 자원을 강제로 빼앗아 한 프로세스에 할당하는 방식이다.
• 프로세스를 종료해 회복하는 방식도 2가지로 나뉘는데, 먼저 데드락에 빠진 모든 프로세스를 중단하는 방법은 데드락을 한 번에 해결할 수 있지만 프로세스들의 작업 내용을 잃을 수 있다.
• 그 다음은 데드락이 없어질 때까지 한 프로세스씩 종료하는 방식으로 작업 내용을 잃는 것을 최대한 줄일 수 있지만 교착상태가 없어졌는지 여부를 확인하는 과정에서 오버헤드가 발생한다.