[운영체제] 프로세스 동기화와 데드락

Q) race condition이 무엇이며 언제 일어날 수 있나요?
A) race condition은 두개의 연산이 동시에 공유 자원에 접근할 때 결과가 일관성을 보장 받지 못하는 상태를 말합니다.


Q) race condition이 발생할 수 있는 상황과 해결법을 알려주세요.
A) race condition은 세가지 경우에 일어납니다.
첫번째로 커널 작업을 수행하는 중에 인터럽트가 발생하는 상황입니다. 커널 모드에서 데이터를 로드하여 수행하다 인터럽트가 발생하여 같은 데이터에 접근하는 경우입니다. 해결을 위해서는 중요한 데이터에 접근하고 있을 때는 인터럽트를 바로 처리하지 않고 해당 작업 이후에 처리하는 방법을 사용합니다.

두번째는 프로세스가 시스템 콜을 하여 커널 모드 수행 중인데 문맥 교환이 일어나는 경우입니다. 커널 모드에서는 커널 주소 공간의 데이터를 사용하기 때문에 race condition이 발생할 수 있는 것입니다. 해결법은 커널 모드에서 수행 중일 때는 CPU를 빼앗기지 않고 사용자 모드로 돌아갈 때 빼앗기는 것입니다.

세번째는 여러개의 CPU가 같은 데이터에 접근할 때입니다. 해결법은 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 lock/unlock을 거는 방법입니다.


Q) Critical section이 무엇인가요?
A) 동시에 공유 자원에 접근하는 작업을 수행하는 연산을 critical section이라 합니다. 문제 해결을 위한 기본 조건 3가지가 있습니다. Mutual Exclusion(상호 배제) 조건은 한 프로세스에서 critical section이 시행중이면 다른 프로세스에서는 critical section이 시행되는 것을 막아야 한다는 조건입니다. Progress 조건은 critical section에서 시행중인 프로세스가 없다면 critical section에 들어가게 해줘야 한다는 것입니다. Bounded Wating 조건은 특정 프로세스가 무한대로 기다리지 않도록 critical section에 진입하는 횟수에 제한을 두어야 한다는 것입니다.


Q) 위의 조건들을 만족하면서 문제를 해결할 수 있는 방법은 무엇인가요?
A) 추상화시키는 방법인 세마포어 방법이 존재합니다. 세마포어는 P, V 연산을 가지고 있습니다. P연산은 임계 구역에 들어가기 전에 수행되고, V연산은 임계구역에서 나올 때 수행됩니다. P는 공유자원을 획득하는 과정으로, P연산 시 자원이 하나 소모되고 V연산은 자원을 반납하는 과정으로, V연산 시 자원이 하나 증가합니다.
자원의 개수를 S 변수로 나타내는데 P 연산 시 S가 0 이하면 무한 루프를 돌다가 S가 0보다 커지면 하나를 빼서 그 자원을 사용합니다.


Q) 뮤텍스mutex 는 무엇인가요?
A) 세마포어 변수 S가 1인 경우입니다. P연산을 해주면 S는 0이 되고(lock), V연산을 해주면 S는 1이 됩니다(unlock). 뮤텍스를 이진 세마포어라고 부르기도 합니다.


Q) Busy-wait과 block/wakeup 방식은 무슨 차이인가요?
A) Busy-wait 방식은 while문의 조건을 계속 체크하느라 CPU 할당시간을 무의미하게 낭비한다는 문제가 있습니다. 이러한 과정들을 줄이고자 block/wakeup 방식에서는 세마포어 변수를 누가 사용 중이면 세마포어를 blocked 상태로 두고 wait queue에 넣습니다. 이후 누가 세마포어 변수를 반납하면 wait queue에서 프로세스 하나를 가져옵니다.


Q) 데드락이 무엇이며 발생 조건이 무엇인가요?
A) 프로세스1과 2가 자원1,2를 모두 얻어야 한다고 가정해봅시다. 프로세스1이 자원1을 가지고 프로세스2가 자원2을 가지고 있다면 두 프로세스는 서로의 자원만을 기다리며 무한히 기다리게 됩니다. 이런 현상을 deadlock이라합니다.
데드락(DeadLock) 발생 조건은 4가지가 있으며 4가지 모두 성립해야 데드락 발생합니다. (하나라도 성립하지 않으면 데드락 문제 해결 가능)
상호 배제(Mutual exclusion) : 자원은 한번에 한 프로세스만 사용할 수 있습니다.
점유 대기(Hold and wait) : 가지고 있는 자원을 내놓지 않으며 추가적인 자원을 기다립니다.
비선점(No preemption): 프로세스가 가진 자원을 강제로 빼앗을 수 없습니다.
순환 대기(Circular wait): 자원을 기다리는 프로세스간에 사이클이 형성됩니다.


Q) 이러한 데드락을 어떻게 해결할 수 있나요?
A) 예방, 회피, 탐지&회복, 무시 총 4가지 대처법이 있습니다.
예방(prevention)은 교착 상태 발생 조건 중 하나를 제거하면서 해결합니다. (자원 낭비 엄청 심함)
상호 배제 부정 : 여러 프로세스가 공유 자원을 사용하도록 합니다.
점유 대기 부정 : 프로세스 실행전 모든 자원을 할당하거나 자원이 필요한 경우 모든 자원을 내려놓고 다시 요청합니다.
비선점 부정 : 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원을 빼앗을 수 있게 합니다.
순환대기 부정 : 자원에 고유번호 할당 후 순서대로 자원을 요구하도록 합니다.

회피(avoidance)는 교착 상태 발생 시 피해나가는 방법입니다. 공유 자원에 대한 부가정보를 사전에 입력받고 그걸로 미리 계산하여 데드락이 발생하는 상황을 피합니다. 보통 각 프로세스가 시작될 때 각 자원의 최대 사용량을 사전에 입력받아 계산하여, 데드락이 발생할 수 있다면 자원을 내주지 않습니다.
* 은행원 알고리즘(Banker's Algorithm)
은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래함. 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피. 안정 상태면 자원 할당, 아니면 다른 프로세스들이 자원 해지까지 대기

탐지 & 회복(detection and recover)는 교착 상태가 되도록 허용한 다음 회복시키는 방법입니다.
자원 할당 그래프를 통해 cycle 존재 여부를 조사하여 교착 상태를 탐지합니다. 자원 요청 시, 탐지 알고리즘을 실행시켜 cycle 여부를 조사하는데 그에 대한 오버헤드 발생합니다.
회복 시에는 교착 상태의 프로세스를 모두 중지하거나 교착 상태가 제거될 때까지 하나씩의 프로세스를 중지하는 방법을 사용합니다. 또는 교착상태의 프로세스가 점유하고 있는 자원을 빼앗아 다른 프로세스에게 할당해줍니다. 이때는 우선순위가 낮은 프로세스의 자원을 먼저 뺏습니다.


Q) 기아상태를 설명하는 식사하는 철학자 문제에 대해 설명해보세요.
A) 교착 상태 해결책은 다음과 같습니다.
n명이 앉을 수 있는 테이블에서 철학자를 n-1명만 앉힙니다.
한 철학자가 젓가락 두개를 모두 집을 수 있는 상황에서만 젓가락 집도록 허용합니다.
왼쪽 젓가락을 먼저 집지 않고 오른쪽 젓가락을 먼저 집도록 허용합니다.