Synchronization: The Reader Writer Problem

What is the Reader Writer Problem?

많은 스레드가 사용하는 Key-value map 자료구조가 있다고 생각해봅시다. 여러개의 스레드는 제공되어지는 자료구조가 써지고 있지 않을 때 찾아봐야 합니다. data corruption을 막기 위해서, 한 스레드만이 자료구조를 수정할 수 있어야 합니다(아무도 읽고있지도 않아야 합니다)

이것이 Reader Write Problem의 예입니다. 즉, 여러명의 reader와 write를 어떻게 효율적으로 동기화시키는지에 대한 문제입니다. 예를 들어 여러명의 reader가 같이 읽을 수는 있지만 writer는 독접적인 접근을 할 수 있게 해야합니다.

다음의 예는 정확하지 않은 시도를 보여주고 있습니다(lock은 pthread_mutex_lock의 줄임말입니다)

Attempt #1

read() { lock(&m) // do read stuff unlock(&m) }

write() { lock(&m) // do write stuff unlock(&m) }

적어도 첫 시도는 data corruption이 일어나지 않습니다.(reader는 writer가 쓰는동안 기다려야 하고, 그 반대도 마찬가지입니다) 하지만 reader가 다른 reader도 기다려야 합니다. 다른 시도를 해봅시다.

Attempt #2

read() { while(writing) {/*spin*/} reading = 1 // do read stuff reading = 0 }

write() { while(reading || writing) {/*spin*/} writing = 1 // do write stuff writing = 0 }

두 번째 시도는  race condition에 걸립니다. 두 스레드가 read와 write를 호출한다고 했을 때(또는 모두 WRITE를 호출), 두 스레드는 진행됩니다. 또, 여러명의 reader와 writer가 있다면 reader와 writer의 총 숫자를 알아야 합니다. 

Attempt #3

pthread_cond_wait이 3가지 행동을 한다는 것을 기억해야 합니다. 첫번째로 mutex를 unlock하고, sleep합니다.(pthread_cond_signal or pthread_cond_broadcast가 깨우기 전까지). 세번째로 스레드를 깨우고 return 하기 전에 mutex lock을 다시 얻어야 합니다. 이렇게 함으로써 한 스레드만  lock과 unlock으로 정의된 CS에 진입이 가능합니다.

아래의 #3 구현은 어떤 writer도 쓰고 있지 않을 때 cond_wait에 진입합니다.

read() {
    lock(&m)
    while (writing)
        cond_wait(&cv, &m)
    reading++;

/* Read here! */

    reading--
    cond_signal(&cv)
    unlock(&m)
}

하지만 mutex를 unlock하지 않기 때문에 한 번에 한 독자만 읽을 수 있습니다.

더 나은 방법은 reading 전에 unlock하는 것입니다.

read() {
    lock(&m);
    while (writing)
        cond_wait(&cv, &m)
    reading++;
    unlock(&m)
/* Read here! */
    lock(&m)
    reading--
    cond_signal(&cv)
    unlock(&m)
}

이렇게 하면 writer와 reader는 동시에 읽거나 쓸 수 없을까요? 아닙니다.

일단 cond_wait이 리턴되기 전에 mutex lock을 다시 얻는 과정이 필요합니다. 그러므로 한 번에 한 스레드만이 CS(**로 표시됨) 안의 코드를 실행할 수 있습니다.

read() {
    lock(&m);
**  while (writing)
**      cond_wait(&cv, &m)
**  reading++;
    unlock(&m)
/* Read here! */
    lock(&m)
**  reading--
**  cond_signal(&cv)
    unlock(&m)
}

Writer는 모두를 기다려야 합니다. lock으로 Mutual exclusion을 보장해주어야 합니다. 

write() {
    lock(&m);
**  while (reading || writing)
**      cond_wait(&cv, &m);
**  writing++;
**
** /* Write here! */
**  writing--;
**  cond_signal(&cv);
    unlock(&m);
}

위에 #3번도 하나의 스레드만 깨워주는 ptherad_cond_siganl을 사용합니다. 예를 들어, 많은 reader가 writer가 쓰기를 기다리고 있다면 한 명의 독자만이 잠에서 깨어납니다. reader와 writer는 cond_broadcast를 사용해 모든 스레드가 일어나 while-loop condition을 확인하도록 해야 합니다.

Starving writers

3번 후보는 starvation입니다. 만약 reader가 끊임없이 도착한다면 writer가 계속해서 진행할 수 없습니다(reading count가 0이 되지 않음). 이러한 상황을 starvation이라고 하고 heavy load인 상황에서 발견됩니다. 이러한 경우 해결책은 writer에게 bounded wait을 구현하는 것입니다. 만약 writer가 도착하면 여전히 reader가 존재해 기다리고 있어야 합니다. 하지만 그 이후에 오는 reader는 holding pen에 들어가 writer가 다 쓰기를 기다려야 합니다. holding pen은 변수와 condition variable(일단 writer가 다 쓰고나면 모든 스레드를 깨워야 하므로)로 구현될 수 있습니다. 

writer가 도착하면,  현재 독자들이 끝내는 것을 기다리기 전에 write할 것이라는 의도를 전달합니다(writer count 증가)

write() {
    lock()
    writer++

    while (reading || writing)
    cond_wait
    unlock()
  ...
}

그리고 나서 들어오는 reader들은 writer가 0이 아닐 동안 진입하지 못합니다.

writer는 writer가 도착했을음 의미하고, reading과 writing은 active reader나 writer가 있음을 의미합니다.

read() {
    lock()
    // readers that arrive *after* the writer arrived will have to wait here!
    while(writer)
    cond_wait(&cv,&m)

    // readers that arrive while there is an active writer
    // will also wait.
    while (writing) 
        cond_wait(&cv,&m)
    reading++
    unlock
  ...
}

Attempt #4

아래는 Reader-Writer problem에 대한 첫 해결책입니다. 만약 계속해서 Reader Writer problem에 대해 조사해 보면, writer에가 lock에 대한 접근 순위를 주어 Second Reader Writer problem을 해결했다는 것을 알 수 있을 것입니다. 이 해결책은 optimal하지는 않습니다. 하지만 원해 문제를 해결할 수 있습니다(N명의 active reader,  1명의 active writer, reader가 계속해서 있을 때 wrtier의 stavation방지)

아래 코드를 더 발전시킬 수 있겠습니까? 예를 들면, 한 명의 writer나 reader들을 깨우는 더 좋은 코드를 만들 수 있겠습니까?

reader() {
    lock(&m)
    while (writers)
        cond_wait(&turn, &m)
    // No need to wait while(writing here) because we can only exit the above loop
    // when writing is zero
    reading++
    unlock(&m)

  // perform reading here

    lock(&m)
    reading--
    cond_broadcast(&turn)
    unlock(&m)
}

writer() {
    lock(&m)  
    writers++  
    while (reading || writing)   
        cond_wait(&turn, &m)  
    writing++  
    unlock(&m)  
    // perform writing here  
    lock(&m)  
    writing--  
    writers--  
    cond_broadcast(&turn)  
    unlock(&m)  
}