Synchronization : Advanced

※ Using Semaphores to Coordinate Access to Shared Resources

 

Basic idea : 스레드는 세마포어 작업을 사용하여 다른 스레드에 일부 조건이 참임을 알린다.

• counting semaphores 을 사용하여 리소스 상태를 추적하고 다른 스레드에 알림
• mutex 를 사용하여 리소스에 대한 액세스 보호

Two classic exmaples :

• The Producer-Consumer Problem
• The Readers-Writers Problem

 

※ Producer-Consumer Problem

 

 

Common synchronization pattern :

• 생산자는 빈 슬롯을 기다렸다가 버퍼에 아이템을 삽입하고 소비자에게 알린다.
• 소비자가 아이템을 기다렸다가 버퍼에서 제거하고 생산자에게 알린다.

Examples

• Multimedia processing :
  
  • 프로듀서가 MPEG 비디오 프레임을 만들고 소비자가 이를 렌더링한다.
• Event-driven graphical user interfaces :
  
  • 마우스 클릭, 마우스 이동, 키보드 적중 등을 감지하여 해당 이벤트를 버퍼에 삽입한다.
  • 소비자가 버퍼에서 이벤트를 검색하고 디스플레이를 색칠한다.

 

 

※ procuder-Consumer on an n-element Buffer

 

뮤텍스와 두 개의 counting semaphores 가 필요하다.

• mutex: 버퍼에 대한 상호 배타적 액세스를 적용한다.
• slots: 버퍼에서 사용 가능한 슬롯 수
• items: 버퍼에서 사용 가능한 아이템 수

sbuf 라는 공유 버퍼 패키지를 사용하여 구현된다.

 

typedef struct {
    int *buf;          /* Buffer array */
    int n;             /* Maximum number of slots */
    int front;         /* buf[(front+1)%n] is first item */
    int rear;          /* buf[rear%n] is last item */
    sem_t mutex;       /* Protects accesses to buf */
    sem_t slots;       /* Counts available slots */
    sem_t items;       /* Counts available items */
} sbuf_t;
/* $end sbuft */

void sbuf_init(sbuf_t *sp, int n);
void sbuf_deinit(sbuf_t *sp);
void sbuf_insert(sbuf_t *sp, int item);
int sbuf_remove(sbuf_t *sp);

 

sbuf 패키지의 정의인 코드다.

int * 타입의 buf 과 n 을 통해 buf 는 n 사이즈 만큼 원소들을 담을 수 있다는 것으로 이해할 수 있다.

front, rear 을 통해 item 을 삽입하거나 제거할 수 있으며 mutex, slots, items 을 통해 버퍼에 여러 쓰레드 간에 정상적으로 operation 이 이뤄지도록 할 수 있다.

 

void sbuf_init(sbuf_t *sp, int n)
{
    sp->buf = Calloc(n, sizeof(int));
    sp->n = n;                       /* Buffer holds max of n items */
    sp->front = sp->rear = 0;        /* Empty buffer iff front == rear */
    Sem_init(&sp->mutex, 0, 1);      /* Binary semaphore for locking */
    Sem_init(&sp->slots, 0, n);      /* Initially, buf has n empty slots */
    Sem_init(&sp->items, 0, 0);      /* Initially, buf has zero data items */
}

void sbuf_deinit(sbuf_t *sp)
{
    Free(sp->buf);
}

 

 

n = 4 라고 가정할 때, front = 0, rear = 0 일 경우 현재 버퍼에 아이템이 비어있는 상태이다.

그리고 mutex 는 1 으로 설정하여 Binary semaphore 이고 slots 은 n, items 은 0 으로 Counting semaphore 임을 알 수 있다.

 

void sbuf_insert(sbuf_t *sp, int item)
{
    P(&sp->slots);                          /* Wait for available slot */
    P(&sp->mutex);                          /* Lock the buffer */
    sp->buf[(++sp->rear)%(sp->n)] = item;   /* Insert the item */
    V(&sp->mutex);                          /* Unlock the buffer */
    V(&sp->items);                          /* Announce available item */
}

 

삽입 함수의 과정은 다음과 같다.

 

1. 버퍼에 아이템을 채워야 하므로 슬롯의 갯수를 1 감소시킨다.
2. critical section 에 접근하므로 binary semaphore 인 mutex 를 1 감소시킨다.
3. 버퍼에 아이템을 채워준다.
4. critical section 에 대한 operation 이 끝났으므로 mutex 를 1 증가시킨다.
5. 버퍼에 아이템이 채워졌으므로 1 증가시킨다.

 

int sbuf_remove(sbuf_t *sp)
{
    int item;
    P(&sp->items);                          /* Wait for available item */
    P(&sp->mutex);                          /* Lock the buffer */
    item = sp->buf[(++sp->front)%(sp->n)];  /* Remove the item */
    V(&sp->mutex);                          /* Unlock the buffer */
    V(&sp->slots);                          /* Announce available slot */
    return item;
}

 

삭제 함수의 과정은 다음과 같다.

 

1. 버퍼에 아이템을 제거해야 하므로 아이템의 갯수를 1 감소시킨다.
2. critical section 에 접근하게 되므로 binary semaphore 인 mutex 를 1 감소시킨다.
3. 아이템을 꺼내오는 작업을 실행한다.
4. critical section 에서의 작업이 종료되었으므로 1 증가시킨다.
5. 아이템이 제거되었으므로 슬롯의 갯수를 1 증가시킨다.

 

 

※ Readers-Writers Problem

 

Generalization of the mutual exclusion problem

Problem statement :

• Reader 스레드는 객체만 읽는다.
• Writer 스레드가 객체를 수정한다.
• Writers 는 객체에 대한 독점적으로 접근 권한이 있어야 한다. (reader 는 접근 x)
• 객체에 접근할 수 있는 readers 수 제한이 없음

다음과 같은 예로 실제 시스템에서 자주 발생한다. 

• 온라인 항공 예약 시스템
• 다중 스레드 캐싱 웹 프록시

 

 

※ Variants of Readers-Writers

 

First readers-writers problem (favors readers)

• writer 에게 객체 사용 권한이 이미 부여되지 않은 경우 reader 를 기다리게 해서는 안 된다.
• 대기 중인 writer 가 writer 보다 우선권을 얻은 후 도착하는 reader 

Second readers-writers problem(favors writers)

• writer 는 일단 쓸 준비가 되면, 가능한 한 빨리 쓰기를 수행한다.
• writer 뒤에 도착한 reader 는 writer 가 기다리고 있더라도 기다려야 한다.

두 경우 모두 Starvation(스레드가 무기한으로 대기)가 가능하다.

 

첫 번째 상황의 경우 writer 뒤에 여러 reader 가 writer 보다 더 우선순위가 높을 경우 writer starvation 문제가 발생한다. 

두 번째 상황의 경우 reader 는 writer 가 긴 시간동안 write 하는 경우 접근하지 못하므로 reader starvation 문제가 발생한다.

 

 

※ Solution to First Readers-WRiters Problem

 

int readcnt;    /* Initially = 0 */
sem_t mutex, w; /* Both initially = 1 */

void reader(void)
{
    while (1) {
        P(&mutex);
        readcnt++;
        if (readcnt == 1) /* First in */
            P(&w);
        V(&mutex);

        /* Critical section */
        /* Reading happens  */

        P(&mutex);
        readcnt--;
        if (readcnt == 0) /* Last out */
            V(&w);
        V(&mutex);
    }
}

 

초기의 readcnt 값은 0으로 설정하고 mutex와 w 는 1로 설정한다.

mutex 는 오직 하나의 reader 만 critical section 에 접근하기 위한 용도이고 w 는 오직 writer 만이 critical section 에 접근하기 위한 용도로 설정된 것이다.

위 코드의 플로우를 살펴보도록 하자.

 

1. 다른 reader 가 접근하지 못하도록 mutex 값을 1 감소시킨다. (현재 mutex = 0)
2. readcnt 값을 1 증가시킨다. 이때 readcnt 값이 1 인 경우 두 가지 케이스가 존재한다.
   1. writer가 write 하지 않는 경우(w = 1) : P(&w) 를 호출하여 writer가 write 하지 못하도록 방지한다.
   2. writer가 write 하는 경우(w = 0) : P(&w) 를 호출하여 wait 상태로 변경되고 writer가 계속해서 write 하게 된다. writer 가 write 를 종료하게 되면 wait 상태에 빠져나오게 된다. 
3. 다른 reader 가 접근하도록 mutex 값을 1 증가시킨다. (현재 mutex = 1)
4. reader 는 reading 을 한다.
5. 다른 reader 가 접근하지 못하도록 mutex 값을 1 감소시킨다. (현재 mutex = 0)
6. readcnt 값을 1 감소시킨다. 이때 blocking 된 writer 는 V(&w) 를 호출하여 wake up 상태가 된다.
7. 다른 reader 가 접근하도록 mutex 값을 1 증가시킨다. (현재 mutex = 1)

 

void writer(void)
{
    while (1) {
        P(&w);

        /* Critical section */
        /* Writing happens  */

        V(&w);
    }
}

 

writer 함수이다.

P(&w) 를 호출하여 w 의 값을 0으로 감소시켜 무언가를 작성하고 종료하면 V(&w) 를 호출한다.

 

 

※ Putting It All Together : Prethreaded Concurrent Server

 

 

#include "csapp.h"
#include "sbuf.h"
#define NTHREADS  4
#define SBUFSIZE  16

void echo_cnt(int connfd);
void *thread(void *vargp);

sbuf_t sbuf; /* Shared buffer of connected descriptors */

int main(int argc, char **argv)
{
    int i, listenfd, connfd;
    socklen_t clientlen;
    struct sockaddr_storage clientaddr;
    pthread_t tid;

    if (argc != 2) {
        fprintf(stderr, "usage: %s <port>\n", argv[0]);
        exit(0);
    }
    listenfd = Open_listenfd(argv[1]);

    sbuf_init(&sbuf, SBUFSIZE); //line:conc:pre:initsbuf
    for (i = 0; i < NTHREADS; i++)  /* Create worker threads */ //line:conc:pre:begincreate
        Pthread_create(&tid, NULL, thread, NULL);               //line:conc:pre:endcreate

    while (1) {
        clientlen = sizeof(struct sockaddr_storage);
        connfd = Accept(listenfd, (SA *) &clientaddr, &clientlen);
        sbuf_insert(&sbuf, connfd); /* Insert connfd in buffer */
    }
}

void *thread(void *vargp)
{
    Pthread_detach(pthread_self());
    while (1) {
        int connfd = sbuf_remove(&sbuf); /* Remove connfd from buffer */ //line:conc:pre:removeconnfd
        echo_cnt(connfd);                /* Service client */
        Close(connfd);
    }
}

 

 

※ Prethreaded Concurrent Server

 

#include "csapp.h"

static int byte_cnt;  /* Byte counter */
static sem_t mutex;   /* and the mutex that protects it */

static void init_echo_cnt(void)
{
    Sem_init(&mutex, 0, 1);
    byte_cnt = 0;
}

void echo_cnt(int connfd)
{
    int n;
    char buf[MAXLINE];
    rio_t rio;
    static pthread_once_t once = PTHREAD_ONCE_INIT;

    Pthread_once(&once, init_echo_cnt); //line:conc:pre:pthreadonce
    Rio_readinitb(&rio, connfd);        //line:conc:pre:rioinitb
    while((n = Rio_readlineb(&rio, buf, MAXLINE)) != 0) {
        P(&mutex);
        byte_cnt += n; //line:conc:pre:cntaccess1
        printf("thread %d received %d (%d total) bytes on fd %d\n",
               (int) pthread_self(), n, byte_cnt, connfd); //line:conc:pre:cntaccess2
        V(&mutex);
        Rio_writen(connfd, buf, n);
    }
}

 

 

※ Crucial concept : Thread Safety

 

스레드에서 호출된 함수는 thread-safe 해야 한다.

Def : 함수는 여러 동시 스레드에서 반복적으로 호출될 때 항상 올바른 결과를 생성하는 경우 thread-safe 하다.

thread-unsafe 함수의 클래스 :

• 클래스 1 : 공유 변수(global or static)를 보호하지 않는 함수
• 클래스 2 : 여러 호출에 걸쳐 상태를 유지하는 기능
• 클래스 3 : 정적 변수로 포인터를 리턴하는 함수
• 클래스 4 : thread-unsafe 함수를 호출하는 함수

 

 

※ Thread-Unsafe Functions (Class 1)

 

공유 변수를 보호하지 않는 함수에 대한 경우이다.

이를 해결하기 위해 P, V operation 을 사용하지만 동기화 처리로 인해 코드 속도가 느려지는 문제가 존재한다.

 

void *thread(void *vargp)
{
    long i, niters = *((long *)vargp);

    for (i = 0; i < niters; i++) {
        cnt++;
    }

    return NULL;
}

 

위 코드는 synchronization 을 하지 않은 코드이다.

우선 cnt 는 모든 쓰레드들이 공유할 수 있는 전역 변수로 Load, Update, Store 작업이 이뤄진다.

즉, atomic 하지 않은 operation 으로 다른 쓰레드들이 이러한 작업들 간에 충돌이 일어남으로써 예상하지 못한 결과가 나타나게 된다.

유일한 장점은 예상하지 못한 결과가 나타나는 반면에 코드 속도가 빠르다는 점이다.

 

void *thread(void *vargp)
{
    long i, niters = *((long *)vargp);

    for (i = 0; i < niters; i++) {
    	P(&mutex);
        cnt++;
        V(&mutex);
    }

    return NULL;
}

 

위 코드는 synchronization 을 처리한 코드이다.

P, V operation 을 통해 공유 변수 cnt 를 단 하나의 쓰레드 만이 접근 가능하도록 설정하였다.

이러한 locking, unlocking 을 통해 예상 가능한 결과가 도출되는 반면에 이러한 동기화 처리로 인해 약간 느려지는 단점이 존재한다.

 

 

※ Thread-Unsafe Functions (Class 2)

 

여러 함수에 걸쳐 지속적인 상태를 의존한다.

ex ) static 상태에 의존하는 난수 생성기가 존재한다.

static unsigned int next = 1;

/* rand: return pseudo-random integer on 0..32767 */ 
int rand(void)
{
	next = next*1103515245 + 12345;
	return (unsigned int)(next/65536) % 32768; 
}

/* srand: set seed for rand() */ 
void srand(unsigned int seed) 
{
	next = seed; 
}

 

공유 변수로 static 타입의 next 변수가 존재한다.

단일 스레드에서 rand() 함수를 사용하는 것은 문제가 없다. (서로 자원을 use 하는 경우가 없으므로)그렇다면 복수 스레드에서 rand() 함수를 사용하는 것은 문제가 생긴다.그 이유에 대해서 생각해보면 다음과 같다.

 

스레드 1, 스레드 2가 rand() 을 여러번 사용하는 상황이 발생했다고 생각해보자.

 

 

다음과 같은 순서로 위 그림을 이해해보도록 하자.

1. 스레드 1이 먼저 rand() 을 호출하고 스레드 2가 rand() 을 호출한다.
2. 스레드 1이 호출한 rand() 에 입장하여 next 연산을 통해 a 라는 값을 얻었다.
3. context switch 가 일어나서 스레드 2이 호출한 rand() 에 입장한다.
4. 스레드 2에서 next 연산을 통해 b 라는 값을 얻고 c 를 반환한다. (c = (b/65536) % 32768)
5. context switch 가 일어나서 c 를 반환한다. (c = (b/65536) % 32768)

 

여기서 발생한 문제점은 스레드 1에서 context switch 가 일어나서 스레드 2로 넘어가서 next 값을 한 번 더 연산을 하게 된다.

이로 인해 이전에 연산하였던 스레드 1에서 값을 반환할 때 한 번 더 연산된 값을 가지고 반환되는 것이다.

즉 의도하지 못한 함수로 Thread-unsafe 함수이다.

 

 

※ Thread-Safe Random Number Generator

 

인자의 일부로 상태를 전달하는 방법이다.

그리고 global 상태를 제거하는 것이다.

/* rand_r - return pseudo-random integer on 0..32767 */ 
int rand_r(int *nextp)
{
	*nextp = *nextp * 1103515245 + 12345; 
    return (unsigned int)(*nextp/65536) % 32768;
}

 

공유변수를 가지고 operation 을 하는 것이 아닌 각 스레드 별로 존재하는 스택의 변수를 가지고 해당 변수를 operation 함으로써 의도치 않은 프로그램을 방지할 수 있게 된다.

즉, thread-safe 한 함수가 되고 rand_r 을 사용하는 프로그래머는 시드를 유지해야 한다. 

 

 

※ Thread-Unsafe Functions (Class 3)

 

정적 변수로 포인터를 되돌리면 thread-unsafe 함수이다.

Fix 1. 호출자가 변수 주소를 전달하여 결과를 저장하도록 다시 쓰기 기능

• caller 및 callee 변경이 필요

Fix 2. Lock-and-copy

• caller의 단순 변경 필요(callee에는 없음)
• 그러나 호출자는 메모리를 확보해야 한다.

 

/* lock-and-copy version */
char *ctime_ts(const time_t *timep, char *privatep)
{
	char *sharedp;
    
	P(&mutex);
	sharedp = ctime(timep); 
	strcpy(privatep, sharedp); 
	V(&mutex);
	return privatep; 
}

 

 

※ Thread-Unsafe Functions (Class 4)

 

thread-unsafe 함수를 호출하는 경우

• Fix : thread-safe 함수만 호출하도록 함수를 수정하면 된다.

 

 

※  Reentrant Functions

 

Def: 함수가 여러 스레드에서 호출될 때 공유 변수를 통해 접근하지 않으면 reentrant 하다.

• thread-safe 함수의 중요한 부분 집합
  
  • 동기화 작업 필요 없음
  • 클래스 2 함수를 스레드 세이프하게 만드는 유일한 방법은 rand_r과 같이 reentrant 하게 만드는 것이다.

 

 

위와 같이 구성된 집합의 여러 케이스를 살펴보도록 하자.

int tmp;
int add(int a) {
	tmp = a;
    return tmp + 10;
}

위 코드는 쓰레드들이 전역변수인 tmp 변수를 공유하고 있으며 공유 변수를 통해 접근되고 있으므로 thread-safe 하지 않고 reentrant 하지 않다.

 

int tmp;
int add(int a) {
	tmp = a;
    return a + 10;
}

위 코드는 쓰레드들이 전역변수인 tmp 변수를 공유하고 있지만 공유 변수를 통해 접근되지 않으므로 reentrant 하지만 thread-safe 하지 않다.

 

thread_local int tmp;
int add(int a) {
	tmp = a;
    return tmp + 10;
}

thread_local 이 붙음으로써 thread-safe 하며 re-entrant 하지 않다.

thread_local 은 thread가 TLS 를 지원하기 위해서 C++11 부터 추가되었다.

TLS 이란 Thread Local Storeage 의 약자로 thread 별로 고유한 저장공간을 가질 수 있는 방법이다. 

 

int add(int a) {
	return a + 10;
}

thread safe 하며 reentrant 한 경우이다.

 

 

※ One worry : Races

 

프로그램의 정확도가 다른 스레드가 y 지점에 도달하기 전에 x 지점에 도달하는 스레드에 의존할 때 race 가 발생한다.

/* A threaded program with a race */
int main()
{
    pthread_t tid[N];
    int i;

    for (i = 0; i < N; i++)
        Pthread_create(&tid[i], NULL, thread, &i); //line:conc:race:createthread
    for (i = 0; i < N; i++)
        Pthread_join(tid[i], NULL);
    exit(0);
}

/* Thread routine */
void *thread(void *vargp)
{
    int myid = *((int *)vargp);  //line:conc:race:derefarg
    printf("Hello from thread %d\n", myid);
    return NULL;
}

 

N 개의 스레드들은 main 스레드의 로컬 변수 i 를 공유하고 있는 상태이다.쓰레드를 생성하면서 동시에 thread() 함수가 실행되는 것은 문제가 없어보인다.그러나, 쓰레드를 생성하면서 thread() 함수가 실행되지 않는다면 문제가 발생한다.

 

 

처음에 스레드를 생성되어 실행되면 myid 는 main 스레드에 존재하는 i 값을 역참조하여 0을 얻게 된다.

만약 생성된 스레드가 실행되지 않고 스레드가 한번 더 생성되면 다음과 같은 상황이 발생한다.

 

 

다른 스레드가 생성되면서 myid 값은 main 스레드의 i 값을 역참조하여 1이 된다.

그러나 이전에 만들어진 스레드 또한 myid 값은 main 스레드의 i 값을 역참조하여 1이 되버린다.

즉, 이러한 현상을 race 라고 한다.

 

 

※ Race Illustration

 

 

main 스레드에서 i의 증가와 peer 스레드에서 vargp 의 deref 사이의 race :

• i = 0 일 때 deref 가 발생하면 OK
• 그렇지 않으면 peer 스레드가 잘못된 ID 값을 가져오게 된다.

 

 

※ Experimental Results

 

 

단일 코어인 경우와 멀티 코어인 경우 race 의 차이가 심한 것을 볼 수 있다.

 

 

※ Race Elimination

 

int main()
{
    pthread_t tid[N];
    int i, *ptr;

    for (i = 0; i < N; i++) {
        ptr = Malloc(sizeof(int));                    //line:conc:norace:createthread1
        *ptr = i;                                     //line:conc:norace:createthread2
        Pthread_create(&tid[i], NULL, thread, ptr);   //line:conc:norace:createthread3
    } //line:conc:norace:endloop
    for (i = 0; i < N; i++)
        Pthread_join(tid[i], NULL);
    exit(0);
}

/* Thread routine */
void *thread(void *vargp)
{
    int myid = *((int *)vargp);
    Free(vargp);
    printf("Hello from thread %d\n", myid);
    return NULL;
}
/* $end norace */

 

위와 같은 코드로 int * 타입의 변수 ptr 을 선언하여 malloc 을 통해 힙 영역에 새로운 메모리 공간을 할당하여 이 공간에 값을 넣어줘서 스레드 마다 해당 공간을 참조하도록 하는 매커니즘이다.

 

 

위 그림과 같이 힙 영역에 i 값을 넣어주고 peer 스레드들은 힙 영역에 해당하는 주소를 매개변수로 받게 되어 해당 값을 myid 로 가져오고 힙 영역에 생성된 메모리 영역을 free 하여 memory leak 을 발생하지 않고 정상적으로 race 를 제거할 수 있게 된다.

 

 

※ Another worry : Deadlock

 

Def : 프로세스가 절대 참이 되지 않는 조건을 기다리고 있으면 deadlock 이 된다.

전형적인 시나리오로 다음과 같다.

1. 프로세스 1과 2를 계속하려면 두 개의 리소스(A 및 B)가 필요하다.
2. 프로세스 1이 A를 획득하고 B를 기다린다.
3. 프로세스 2가 B를 획득하고 A를 기다린다.
4. 둘 다 영원히 기다리게 된다.

 

 

※ Deadlocking with Semaphores

 

int main() {
	pthread_t tid[2];
	Sem_init(&mutex[0], 0, 1);  /* mutex[0] = 1 */ 
    Sem_init(&mutex[1], 0, 1);  /* mutex[1] = 1 */
	Pthread_create(&tid[0], NULL, count, (void*) 0);
	Pthread_create(&tid[1], NULL, count, (void*) 1);
	Pthread_join(tid[0], NULL);
	Pthread_join(tid[1], NULL); 
    printf("cnt=%d\n", cnt); 
    exit(0);
}

void *count(void *vargp) {
	int i;
	int id = (int) vargp;
	for (i = 0; i < NITERS; i++) {
		P(&mutex[id]); P(&mutex[1-id]); 
        cnt++;
		V(&mutex[id]); V(&mutex[1-id]); 
    }
	return NULL; 
}

 

 

Tid[0] 은 P(s0), P(s1) 을 순서대로 호출하고 Tid[1] 은 P(s1), P(s0) 을 호출하게 된다.

이를 다음과 같은 순서로 생각해보도록 하자.

 

 

1. 스레드 Tid[0] 가 P(s0) 을 호출하여 세마포어 s0 의 값이 0 으로 감소된 상태이다.

 

 

2. context switch 가 발생하여 스레드 Tid[1] 이 P(s1) 을 호출하여 세마포어 s1 의 값을 0 으로 감소되었다.

그 후에 P(s0) 을 호출하려고 했으나 세마포어 s0 의 값이 0 이므로 스레드 Tid[1] 은 sleep 상태에 빠진다.

 

 

3. Tid[1] 이 sleep 상태에 빠진 후 Tid[0] 스레드 또한 실행하지 못한 P(s1) 을 호출하려고 했으나 세마포어 s1 의 값이 0 이므로 스레드 Tid[0] 또한 sleep 상태에 빠진다.

 

두 쓰레드가 영원히 sleep 상태에 빠지는 상황이 되버린 상태이다.

이를 Deadlock(교착 상태) 에 빠졌다고 표현할 수 있다.

 

 

※ Deadlock Visualized in Progress Graph

 

 

잠금으로 인해 deadlock 이 발생할 수 있음 : 절대 참이 될 수 없는 조건을 기다리는 중

Deadlock region 에 진입하는 모든 궤적은 결국 deadlock 에 도달하여 s0 또는 s1이 0이 아니기를 기다린다.

다른 궤도는 운 좋게 deadlock region 에 빠진 영역을 벗어나게 된다.

불행한 사실은 deadlock 은 종종 non-deterministic 하다.

 

 

※ Avoiding Deadlock

 

void *count(void *vargp) 
{
	int i;
	int id = (int) vargp;
	for (i = 0; i < NITERS; i++) { 
    	P(&mutex[0]); P(&mutex[1]); 
        cnt++;
		V(&mutex[id]); V(&mutex[1-id]); 
    }
	return NULL;
}

 

 

위와 같이 Tid[1] 에서 P(s0), P(s1) 순으로 호출하게 될 경우 Deadlock 을 피할 수 있다.

 

 

궤도가 막힐 수 있는 방법이 없다.

프로세스에서 동일한 순서로 lock 을 획득하고 잠금 해제 순서는 중요하지 않다.