Deadlock

동기화 문제 중 Deadlock에 대해 학습한 내용입니다.

Deadlock(교착상태)

정의

→ 교착상태를 일컫는 말로, 둘 이상의 프로세스가 대기 프로세스 중 하나에 의해서만 발생할 수 있는 이벤트를 무한정 기다리는 상황을 말합니다.

예를 들어봅시다. P0과 P1이 있는데 다음과 같은 순서로 각자 한번씩 번갈아가면 명령어를 수행한다고 가정해봅시다.

P0 → wait(S) → wait(Q) →

P1 → wait(Q) → wait(S) →

이 상황에서 P0과 P1이 한번씩 번갈아가면서 실행되면 P0은 S를 차지하게 되고 P1은 Q를 차지하게 됩니다. 그 다음 P0이 다시 wait(Q)를 실행하려고 할 때 Q를 이미 P1이 사용하고 있기 때문에 대기하게 됩니다. P1은 그 다음 필요 자원인 S를 획득해야만 본인이 가지고 있는 Q를 되돌려놓는데 S가 이미 P0의 손에 쥐어져 있어서 S를 획득하기도 불가능합니다. 그래서 P0과 P1 모두 waiting 상태에 빠지게 됩니다. 이렇듯 두 프로세스 다 어떠한 자원도 얻을 수 없게 되는 상황을 교착상태라고 표현합니다.

Deadlock의 4요소

→ Deadlock을 만족하기 위해선 총 4가지 요소가 충족되어져야 합니다. 하나라도 없으면 데드락이 걸리지 않게 됩니다.

• Mutual Exclusion
  • 간섭이 불가능합니다.
• Hold and Wait
  • 자원을 쥐고 있는 상태로 다음 자원을 기다립니다.
• No preemption
  • 비선점형입니다.
• Circular wait
  • 자원을 얻기위한 움직임이 원을 이뤄야합니다.

여러 문제들

Bounded buffer problem

→ 대표적인 Producer-Consumer problem입니다.

• Producer process

do {
	// do something
	wait(empty); // 버퍼에 적어도 하나의 공간이 생기기를 기다림
	wait(mutex); // critical section에 진입하기 위해 기다림
	// do something
	// produce an item in nextp
	next = (next + 1) % N;

	signal(mutex); // critical section에서 빠져나옴을 알림
	signal(full);  // buffer에 item이 있음을 알림
} while(true) ;

• Consumer process

do {
	wait(full); // buffer에 적어도 하나의 item이 채워지길 기다림.
	wait(mutex);
	// do something
	// remove an item from buffer;
	nextc = (nextc + 1) % N;
	// do something
	signal(mutex);
	signal(empty); // buffer에 하나 빈공간 생긴 것을 알림
} while(true);

Readers_Writers Problem

• 프로세스 종류
  • Reader : 읽는 사람 → 동시에 여러 명의 접근을 허용합니다.
  • Writer : 데이터를 쓰는 사람 → 누구의 방해도 없이 한 번에 한 명의 접근만 허용합니다. = ‘Mutual Exclusion’
• 두 가지의 경우 존재 가능
  • Writer starvation : reader 중 누구도 writer가 올 시간을 주지 않을 경우
  • Reader starvation : writer가 다음 대기자인 writer에게만 순서를 내어줄 경우

• Writer process

    while(true) {
    	wait (rw_mutex);
    		// writing is performed
    		signal(rw_mutex); // 이때 다음 writer에게 줄지, reader에게 줄지 scheduler가 정함
    }
  

• reader process

    while(true) {
    	wait(mutex);
    	readcount++; // reader의 수 + 1
    	if(readcount == 1) // reader가 한 명만 존재해도 writer의 접근을 막음
    		wait(rw_mutex);
    	signal(mutex); // readcount에 대한 mutex 사용의 끝을 알림, 왜 벌써 mutex를 해제하나?
    	// Reader들은 한 번에 여러명이 read 수행 가능, 다만 read_count를 update할 때 mutual exclusion이 필요하기 때문
      	
    	// reading is performed
      	
    	wait(mutex);
    	readcount--;
    	if(readcount == 0) // reader가 한 명도 없으면 write 가능, 단, reader가 한 명이라도 계속 있다면 writer는 starvation 현상을 겪을 수 있음
    		signal(rw_mutex);
    	signal(mutex);
    }
  

• writer의 ‘starvation’을 없애기 위한 solution

    // entry section
    wait(wmutex); // wmutex = writercount를 위한 mutex
    	writecount++;
    	if(writecount==1)  // writer가 한 명이라도 대기 중이면
    		wait(read); // reader가 그 순간부터 대기 -> reader들의 무한 진입을 막음
    	signal(mutex);
    	wait(wrt); // critical section 안에 writer가 있으면 대기 <- writer는 한 번에 여럿이서 데이터 사용 불가능
    	// writing is performed
    // exit section
    	signal(wrt); // 작업중인 writer이 끝을 알림
    	wait(wmute);
    		writecount--;
    		if(writecount == 0) // 여기서 동일한 이유로 reader에게 starvation 현상이 발생할 수 있음
    			signal(read);
    	signal(wmutex);
  

• 최종 solution

  • 수행을 기다리는 reader, writer를 분리해서 표시합니다.

    → 어떤 작업이 수행 중이어도 모두 대기 가능합니다. 대기 중인 작업이 있는 경우 해당 작업을 수행합니다 → 기아현상(’starvation’)을 방지합니다.

  • writer의 동작

    → writer들의 수행이 끝나면 대기하던 read를 전부 작업합니다.

  • reader의 동작

    → writer가 수행 or 대기 중이면 기다리고, 대기하던 reader를 모두 수행했으면 대기하고 있던 writer를 하나 수행합니다.

Dining philosophers problem

▲ Dining philosophers

→ 가장 고전적인 동기화 문제로, 5명의 철학자들이 한 테이블에 앉아있고 식사를 하기 위해서는 양 옆에 있는 젓가락이 모두 필요합니다. 철학자들은 식사를 마친 뒤에야 젓가락을 내려놓고 모두 자신의 옆에 있는 젓가락들만 사용할 수 있습니다.

Deadlock 발생

→ 철학자들이 모두 자신의 오른쪽에 위치한 젓가락을 집으려 하면 어떻게 될까요?

⇒ 각자 자신의 오른쪽에 위치한 젓가락을 집을 경우 모두 한 쪽의 젓가락만 가지고 있기 때문에 누구도 식사를 진행할 수 없게 됩니다. 이러한 경우

• Mutual Exclusion : 하나의 젓가락은 한 명의 철학자만 사용할 수 있습니다.
• Hold and Wait : 자신에게 있는 젓가락(자원)을 쥐고 있는 상태에서 다음 젓가락을 얻기 위해 대기합니다.
• Circular wait : 전체적으로 젓가락(자원)을 얻기 위한 흐름이 원형을 이룹니다.
• No preemption : 다른 철학자가 쥐고 있는 젓가락을 빼았을 수는 없습니다.

다음과 같이 Deadlock의 4요소를 모두 만족하기 때문에 Deadlock이 발생합니다.

Solutions for deadlock

1. 최대 4명의 학자만 앉히자! → 자원이 항상 한개가 남습니다.
2. 젓가락의 상태를 미리 체크하고, 두 개를 집을 수 있을 때만 집기를 수행합니다.
3. 철학자에게 번호를 부여하여 홀수는 왼쪽을 짝수는 오른쪽을 먼저 집도록 합니다.

⇒ 이러한 방법들은 모두 starvation 현상까지 해결할 수는 없으며, starvation을 해결하기 위해 각각의 해결책에 따로 처리를 해줘야합니다. 예를 들면 한 차례 굶은 철학자에게 우선권을 주는 것과 같은 방식입니다.

2번 해결책의 구현

→ 우리는 젓가락의 상태를 미리 체크하고, 두 개를 모두 집을 수 있을 때 젓가락을 잡는 방식을 구현해보겠습니다.

• 사용되는 자료구조 ⇒ state[5]: 각 철학자들의 상태 (THINK, HUNGRY, EATING)
• 사용된 semaphore
  • mutex : 젓가락을 집거나 놓기위해 수행 ( inital: 1)
  • self[5] : 젓가락 두 개를 잡기를 기다리는 semaphore
    • i 철학자가 Hungry 여도 다른 한쪽의 젓가락을 집지 못하는 상황이면 waiting을 하기 위한 semaphore

• philosopher process

    test(int i)
    {
    	if(state[i]==HUNGRY && state[LEFT]!=EATING && state[RIGHT]!=EATING)
    	{
    		state[i]=EATING;
    		signal(self[i]);
    	}
    }
      
    take_chopsticks(int i)
    {
    	wait(mutex);
    	state[i] = HUNGRY;
    	test(i); // 양쪽 철학자 상태 확인
    	signal(mutex);
    	wait(self[i]); // 먹을 차례 대기
    }
      
    put_chopsticks(int i)
    {
    	wait(mutex);
    	state[i]=THINK;
    	test(LEFT);
    	test(RIGHT); // 양철학자의 상태를 확인
    	signal(mutex); // 먹을 차례인 철학자에게 signal() => starvation 방지
    }
      
    do {
    // ... think
    take_chopsticks(i); // i=철학자 번호 => P(S)와 같음
    // critical section : eat
    put_chopsticks(i); // V(S)
    } while (true);
  

Considerations for synchronization algo.

• Data Consistency (데이터 일관성) 확보
• Deadlock 발생 유무
• Starvation 가능성
• Concurrency 제공 정도

맨 위로 이동 ↑