프론트엔드Explorer

교착 상태, dead lock은 다중 프로그래밍 시스템에서 프로세스 or 스레드가 결코 일어나지 않을 일을 무한정으로 기다리는 상태를 말합니다. 

시스템에서 dead lock은 프로세스가 요구하는 자원이 엉켜서 더 이상 작업을 실행할 수 없는 상태를 의미합니다. 

아래 자동차(프로세스)들이 현재 위치한 길(자원)을 점유함과 동시에 다른 차가 사용하는 길을 사용하려고 대기하고 있지만, 다른 길을 사용할 수 없으며 현재 길에서 벗어나지도 못하는 상태와 같습니다. 

즉, dead lock이란 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황을 말합니다. 

교착 상태의 발생 조건

언제 dead lock이 발생할까요? 

dead lock이 발생하기 위해서는 아래 네 가지 조건이 충족되어야 합니다. 

이 네 가지 중 하나라도 충족되지 않으면 dead lock이 발생하지 않습니다. 

1. 상호배제(Mutual Exclusion) - 한 번에 한 프로세스만 자원을 사용할 수 있어야 합니다. 사용중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 다 사용되고 해제될 때까지 기다려야 합니다. 
2. 점유와 대기(Hold and Wait) - 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 합니다. 
3. 비선점(Non Preemption) - 자원을 선점할 수 없는 조건, 누군가가 자원을 가지고 있을 때 뺏을 수 없습니다. 
4. 순환 대기(Circle Wait) - 프로세스가 여러 개 있을 때 자원의 점유와 요청의 관계가 순환되는 조건을 말합니다. 

아래의 그림은 순환 대기를 나타낸 것 입니다. 

프로세스 3개를 각각 P1, P2, P3라 할 때, P1이 P2의 자원을 요청하고, P2가 P3의 자원을 요청하고, P3가 P1의 자원을 요청하고 그 자원은 요청한 자원을 얻을 수 있을 때까지 반환할 수 없습니다. 

세 가지 프로세스는 자신이 요청한 자원을 얻지 못하기 때문에 계속해서 요청하며 위 사이클을 무한정 순환하게 됩니다. 

교착상태의 해결법

dead lock의 해결법은 크게 3가지로 분류할 수 있습니다. 

(1) dead lock 예방(prevention)하기 

위에서 살펴본 dead lock의 발생 조건 4가지 중 하나라도 발생하지 않게 하는 것이 dead lock을 예방하는 방법입니다. dead lock 발생 가능성을 차단하는 것입니다. 

• 자원의 상호 배제 방지: 한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 합니다. 그러나 추후 동기화 관련 문제가 발생할 수 있다. 
• 점유와 대기 방지: 프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할 때까지 작업을 보류해서, 나중에 또 다른 자원을 점유하기 위한 대기 조건을 성립하지 않도록 한다. 
• 비선점 방지: 이미 다른 프로세스에게 할당된 자원이 선점권이 없다고 가정할 때, 높은 우선수위의 프로세스가 해당 자원을 선점할 수 있도록 한다. 
• 순환 대기 방지: 자원을 순환 형태로 대기하지 않도록, 일정한 한쪽 방향으로만 자원을 요구하도록 한다. 

물론 이렇게 데드락을 예방할 수 있지만, 시스템의 처리량이나 효율성을 떨어뜨리는 단점이 있습니다. 

(2) dead lock 회피(avoidance)

dead lock 회피는 dead lock 예방보다는 조금 덜 제한적인 방법으로 dead lcok 예방의 단점을 일부 해결할 수 있습니다. 

시스템의 프로세스들이 요청하는 모든 자원을 데드락을 발생시키지 않으면서 차례로 모두에게 할당해줄 수 있다면, 안정 상태(safe state)에 있다고 말합니다. 

반면, 불안정 상태는 안정 상태가 아닌 상황을 말한다. 데드락 발생 가능성이 있는 상황이며, 데드락은 불안정 상태일 때 발생할 수 있다. 

회피 알고리즘은 자원을 할당한 후에도 시스템이 항상 safe state에 있을 수 있도록 할당을 허용하자는 게 기본 특징이다. 이러한 특징을 살린 알고리즘으로 유명한 것이 은행원 알고리즘이다. 

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

: 다익스트라가 제안한 기법, 어떤 자원의 할당을 허용하는지에 관한 여부를 결정하기 전에 미리 결정된 모든 자원들의 최대 가능한 할당량을 가지고 시뮬레이션해 safe state에 들 수 있는지 여부를 검사한다. 

즉, dead lock 가능성을 미리 조사하는 것이다. 

(시물레이션 예시)

위처럼 은행원 알고리즘을 사용해 자원 할당량을 사전에 파악하고, 데드락을 회피할 수 있도록 하면 된다. 

그러나 은행원 알고리즘의 경우, 미리 최대 자원 요구량을 알아야 하고, 할당할 수 있는 자원 수가 일정해야 하는 등 사용에 있어 제약 조건이 많고, 그에 따른 자원 이용도 하락하는 등 단점도 존재한다. 

(3) 데드락 탐지(detection) 및 회복(recovery)

시스템이 데드락 예방이나 회피를 사용하지 않았을 때, 데드락이 발생할 수 있으니 데드락을 탐지하고 회복하는 알고리즘을 사용한다. 

탐지 기법

• Allocation, Request, Available 등으로 시스템에 데드락이 발생했는지 여부를 탐색한다. 
• 은행원 알고리즘에서 했던 방식과 유사하게 현재 시스템의 자원 할당 상태를 가지고 파악한다. 
• 이외에도 자원 할당 그래프를 통해 탐지하는 방법도 있다. 

회복 기법

• 데드락 탐지 기법을 통해 데드락을 발견했다면, 순환 대기에서 벗어나 데드락으로부터 회복하기 위한 방법을 사용한다. 
• 단순히 프로세스 1개 이상을 중단시키기
  • 교착 상태에 빠진 모든 프로세스를 중단시키는 방법: 계속 연산중이던 프로세스들도 모두 일시에 중단되어 부분 결과가 폐기될 수 있는 부작용이 발생할 수 있음
  • 프로세스를 하나씩 중단시킬 때마다 탐지 알고리즘으로 데드락을 탐지하면서 회복시키는 방법: 매번 탐지 알고리즘을 호출 및 수행해야하므로 부담이 되는 작업일 수 있음
• 자원 선점하기 
  • 프로세스에 할당된 자원을 선점해서, 데드락을 해결할 때까지 그 자원을 다른 프로세스에 할당해주는 방법

동시성과 병렬성은 혼동하기 쉬운 개념입니다. 

그래서 둘을 비교해 정리해보도록 하겠습니다. 

먼저, 표를 통해 비교해보겠습니다. 

표로 봐도 차이가 있지만, 그림으로 더 확실히 차이를 보겠습니다. 

Sequential은 일들이 순차적으로 처리되고 있습니다. 하나의 일이 끝나면 다음으로 넘어가고, 그 다음으로 넘어가는 방식입니다. 

Concurrent는 파란색과 빨간색 두 개의 작업이 동시에 실행되는 것처럼 보이지만, 실은 번갈아가면서 작업을 수행중입니다. 

Parallel은 파란색과 빨간 색 두 개의 작업이 실제로 동시에 실행중입니다. 

그림을 하나 더 보도록 하겠습니다. 싱글 코어와 멀티 코어에서 동작을 비교하는 그림입니다. 

싱글 코어에서는 T1과 T2, 2개의 작업을 동시에 실행되는 것처럼 보이게 하기 위해 번갈아가면서 작업을 수행중입니다. 

이 때, 다른 작업으로 바꾸어 실행할 때 내부적으로 Context Switch가 일어납니다. 

멀티 코어는 실제로 T1과 T2가 동시에 수행중입니다. 

이제 감을 잡았으니, 동시성과 병렬성을 다시 정리해봅시다. 

동시성

• 싱글 코어에서 멀티 스레드를 동작시키기 위한 방식
• 멀티 태스킹을 위해 여러 개의 스레드가 번갈아가면서 실행되는 성질
• 동시에 실행되는 것처럼 보이는 것
• 싱글 코어에서 멀티 스레드를 이용해 동시성을 구현하는 일부 케이스에 대한 내용, 멀티 코어에서 멀티 스레드를 이용하여 멀티 스레드를 이용하여 동시성을 만족할 경우에는 실제 물리적 시간으로 동시에 실행된다. 

병렬성

• 멀티 코어에서 멀티 스레드를 동작시키는 방식
• 한 개 이상의 스레드를 포함하는 각 코어들이 동시에 실행되는 성질
• 병렬성의 핵심은 물리적인 시간에 동시에 수행되는 것, 멀티 코어에 포커스가 맞춰져서는 안 된다.
• 네트워크 상의 여러 컴퓨터에게 분산 작업을 요청하는 분산 컴퓨팅

운영체제는 컴퓨터를 제대로 실행 및 사용하게 해주는 프로그램입니다. 

마우스를 움직이는 것부터 프로그램 실행과 종료까지 운영체제가 하는 역할은 매우 많고 없으면 컴퓨터를 사용할 수 없습니다. 

이러한 운영체제와 시스템 콜은 어떤 관계가 있을까요? 

시스템 콜(System Call)이란 프로세스가 운영체제(system)에게 운영체제 기능을 요청(call)하는 것입니다. 

즉, 프로세스가 컴퓨터를 관리하는 시스템인 운영체제에게 어떤 기능(서비스)를 사용하게 해달라고 요청할 때 사용하는 방법입니다. 

컴퓨터의 대부분의 활동은 운영체제를 통해 실행 및 관리됩니다. 

실행중인 프로그램인 프로세스도 운영체제를 통해 실행되고 관리됩니다.  

운영체제가 회사 관리자면, 프로세스는 말단 직원입니다. 

예를 들어, 프로세스 A라는 직원이 자신의 프로그램 외 특정 파일의 데이터를 필요로 한다고 해봅시다.

이럴 때, 프로세스 A가 독자적으로 파일 데이터를 읽어들일 수 있을까요? 그럴 수 없습니다. 

기본적으로 파일을 읽고, 메모리에 데이터를 올리는 것은 운영체제의 역할입니다. 

프로세스 A는 관리자인 운영체제에게 허락을 요청(call)해야 합니다. 

파일 뿐 아니라 운영체제가 관리하는 모든 자원(네트워크, 디스크, 메모리 등)이 필요할 때, 프로세스는 system call을 사용해야 합니다. 

파일을 여는 것(open), 기존 프로세스를 다른 프로그램으로 바꾸는 것(exec), 똑같은 프로세스를 하나 더 만드는 것(fork), 다른 프로세스에 어떤 행위를 지시하는 시그널을 보낼 때(kill) 등 운영체제가 관리하고 있는 자원이라면 system call을 사용해야 합니다. 

아래는 실제 리눅스, 유닉스에서 사용하는 System Call입니다. 

참고한 글의 링크입니다. 

https://mamu2830.blogspot.com/2021/01/whatIsSystemCall.html