전통적 동기화 문제와 데드락

데드락은 동시성 이슈에서 다루는 게 좋을 것 같았지만, 예시와 함께 정리해보려고 한다.

Produer-Consumer problem

소비자와 생산자가 유한한 버퍼를 갖는 상황에서  소비자와 생산자가 상호 배타적으로 접근하고, 소비자는 버퍼가 있으면 소비하고 , 생산자는 원소가 없으면 원소를 생성해야 한다.

위의 문제를 해결하려는 조건은 생산자가 우선 실행된 적이 있어야 하고, 생산자의 실행 횟수가 소비자보다 많아야 한다.

이를 해결하기 위해서 3가지 세마포를 사용한다 

• mutex라는 생산자 소비자 상호 배제를 위한 세마포
• slots이라는 비어있는 버퍼의 개수를 나타내는 세마포
• items라는 버퍼에 차있는 개수를 나타내는 세마포

여기서 주의할 점은 다음과 같이 코드를 작성해 버리면 데드락에 걸릴 수가 있다. mutex를 통해 락을 걸고 기다리는데 slot이 모두 차있는 상태라면 consumer로부터 신호를 기다릴 텐데 이미 writer에서 락을 걸고 있어서 consumer도 기다리는 상태일 수 있다. 따라서 slot, item과 mutex의 위치를 바꿔 줘야 한다

P(mutex)
P(slot)
/*
critical point
*/
V(items)
V(mutex)

Read-Writer problem

동시성 쓰레드들의 집합은 메인 메모리의 자료구조나 디스크 상의 데이터베이스 같은 공유 객체에 접근하고 있다.

일부 쓰레드는 쓰기만 하고 다른 쓰레드들은 이것을 수정만 한다. 읽는 쓰레드를 readers 쓰는 쓰레드를 writers라 한다.

writer는 배타적으로 접근해야 하지만, reader는 다른 reader들과 공유해야 할 수도 있다. 이런 상황의 실제 예시를 들어보면 온라인 항공 예약 시스템에서 수많은 고객들은 좌석 할당 상황을 동시에 조사할 수 있지만, 좌석을 예약하려는 고객은 데이터베이스에 배타적으로 접근해야 함. 또한 웹 프록시에서 기존 페이지를 공유 페이지 캐시에 가져올 수 있지만, 캐시에 새 페이지를 쓰는 모든 쓰레드는 배타적으로 접근해야 함(밑에서 코드를 봐보자)

여기서는 reader를 선호하는 방식으로 작성되었다.

int readcnt; //처음에는 0으로 선언
sem_t mutex, w; 둘다 1로 선언

void reader(void){
	while(1){
    	P(&mutex);
        readcnt++;
        if(readcnt==1)
        	P(&w);
        V(&mutex);
        
        
        /* Critical section */
        
        P(&mutex);
        readcnt--;
        if(readcnt==0)
        	V(&w);
        V(&mutex);
    }
 }
 
 
 void wirter(void){
 	while(1){
    	P(&w);
        
        /*critical section */
        
       	V(&w);
   	}
 }

여기서 봐야 할 점은 w세마포는 공유 객체를 접근하는 크리티컬 섹션으로의 접근을 제어한다. 뮤텍스 세마포는 readcnt변수로의 접근을 보호하며, 이것은 현재 크리티컬 섹션에 있는 reader 수를 센다 reader는 writer와 다르게 처음 들어가는 reader만 w를 잠그고,  크리티컬 섹션을 가장 마지막으로 떠나는 reader만이 이것을 풀어준다. reader 한 개가 w뮤 텍스를 가지고 있는 한 무수한 reader들이 크리티컬 섹션에 아무 방해받지 않고 들어갈 수 있다. 

또한 이 reader-writer 문제는 writer가 우선적으로 작성되든 reader가 우선으로 작성되든 starvation이 발생할 수 있다.

 

식사하는 철학자들 

이 문제는 책에는 따로 언급되지 않았지만 위의 두 문제와 같이 등장하는 워낙 유명한 문제여서 다뤄 보겠다.

5명의 철학자가 식사를 하고 다시 젓가락을 집어 드는 패턴으로 진행된다. 또한 식사하려면 2개의 젓가락이 필요하다.

철학자는 왼쪽 오른쪽 젓가락을 순서대로 집어 든다. 만약 위 같은 상황에서 한 사람이 두 젓가락을 다 가져간다면 나머지는 당연히 대기해야 한다. 또한 만약에 모든 사람이 왼쪽을 하나씩 갖게 된다면 교착상태에 빠질 수가 있다.

• 이를 위한 해결책들이 몇 개 존재한다. 우선  os차원의 해결법으로는 한 사람이 젓가락을 잡는다면 반대쪽 젓가락을 잡을 때까지 행동권을 넘길 수 없게 하는 것이다 즉 CPU의 인터럽트를 무시하는 방식으로 구현하는 것이다.
• 하드웨어 아키텍처 차원에서 해결법은 한 번에 두 개의 젓가락을 잡게 만드는 것이다. 즉 원자성 인스트럭션을 만드는 것이다.
• 마지막으로 소프트웨어 차원의 해결법은 여러 가지가 있는데, 타임아웃을 설정하여 일정 시간 내에 두 개의 젓가락을 가져가지 못한다면 젓가락을 반납하게 하는 것이다. 또는 철학자 별로 젓가락을 집는 위치를 다르게 하는 것이다. 아니면 젓가락에 고윳값을 부여하여 고유값 순서대로 젓가락을 집게 한다. 해시를 사용하는데 두 젓가락 중 높은 것을 먼저 집는 것이다. 그럼 자연스럽게 겹치지 않고 자원을 가져갈 수 있다.

위의 문제는 아래 페이지를 참고함https://namu.wiki/w/%EC%8B%9D%EC%82%AC%ED%95%98%EB%8A%94%20%EC%B2%A0%ED%95%99%EC%9E%90%20%EB%AC%B8%EC%A0%9C

데드락

위에서 약간씩 언급한것 처럼, 두 프로세스가  무한히 대기하게 되는 상황을 이야기한다.

데드락의 성립 조건은 다음과 같다

• 상호 배제: 최소 하나의 자원이 비공유 모드로 점유
• 점유하며 대기: 하나의 자원을 점유하며 다른 자원을 얻기 위해 대기
• 비선점(preemption): 선점할 수 없다
• 순환 대기: 다수의 스레드가 원형으로 다른 쓰레드가 점유한 자원을 대기

위의 4개가 모두 만족해야 데드락이 발생한다.

자원 할당 그래프를 보면 쉽게 이해가 간다. 사이클을 포함한 그래프는 교착상태가 생길 수 있다. 단 자원이 여러 개라면 사이클이 있어도 교착 상태가 아닐 수 있다.

교착 상태 그래프

교착 상태를 처리하는 방법으로는 예방과 회피가 있다. 예방은 교착 상태의 필요조건 중 하나가 성립하지 않도록 보장한다. 회피는 스레드가 사용할 자원을 미리 공지하여 스케줄링한다.

먼저 예방를을 살펴보자

• 상호 배제 상황을 피한다는 것은 애초에 공유할 자원이 없다는 건데 우리는 공유할 자원이 있는 경우를 고려하니 이건 피할 수가 없으니 즐겨야 한다.
• 점유하며 대기는 점유한 상태에서 다른 자원을 요청하여 생기는 문제이다. 자원이 모두 확보된 다음에 스레드가 구동되거나 자원을 점유하면 다른 자원을 요청할 수 없음 하지만 좋지 않음
• 다른 프로세스가 점유한 자원을 뺏을 수가 없다. 우선순위를 정해 선점한다면 나아질 수 있다.
• 대기가 꼬리를 물고 사이클이 되어 있음 이것도 우선순위를 두면 해결할 수 있다 가장 현실 적이다.

예방 방법들은 이용률이 저하되고 성능이 하락되는 단점이 있다 다음으로 회피를 알아보자.

회피는 각 프로세스의 자원 요청을 미리 파악하고 미래의 교착을 피할 수 있도록 스레드 대기를 결정하는 것이다.

간단하게 예시를 볼 텐데 일단 안전 상태를 유지할 수 있는 은행원 알고리즘을 알아보자 

자원별로 여러 개의 인스턴스가 있을 때  시작 단계에서 스레드가 가져야 할 자원의 최대 개수를 신고하고 쓰레드가 자원을 요청하면 안전 상태에 머무를 때에만 수락한다.

 

위의 상황을 보면 12개의 자원이 있고 현재 9개가 사용 중이고 3개가 가용 상태이다. 이때 p1에 2개를 할당해서 끝내면 가용상태가 7개가 되니까 다시 p0에 할당하고 마지막 p2에 할당한다.  

하지만 만약 밑에와 같은 상황이라면 unsafe 한 상황이 된다.