1

私は現在、Reader-Writer問題の正しい実装に取り​​組んでいます（ここを参照）。

このソリューションは、セマフォとミューテックスを使用してリーダースレッドとライタースレッドの公平な処理を保証するQtドックで見つかりました。基本的なコードは次のとおりです。

sem_t semaphore_;
pthread_mutex_t lock_;

void PalindromeDatabase::initializeLocks()
{
    sem_init(&semaphore_, 0, NumberOfReaders_);
    pthread_mutex_init(&lock_, nullptr);
}

void PalindromeDatabase::lockReaders()
{
    sem_wait(&semaphore_);
}

void PalindromeDatabase::unlockReaders()
{
    sem_post(&semaphore_);
}

void PalindromeDatabase::lockWriters()
{
    pthread_mutex_lock(&lock_);
    {
        for (int i = 0; i < NumberOfReaders_; ++i)
            sem_wait(&semaphore_);
    }
    pthread_mutex_unlock(&lock_);
}

void PalindromeDatabase::unlockWriters()
{
    for (int i = 0; i < NumberOfReaders_; ++i)
        sem_post(&semaphore_);
}

これは非常にエレガントな解決策のようです。このSOの回答pthread_rwlock_*で詳しく説明されている動作よりも簡単で効率的です。

以下のこのコードは、リーダースレッドを優先するためのQtソリューションの正しい調整であるかどうか疑問に思いました。

int readersActive_;
sem_t semaphore_;
pthread_mutex_t lock_;
pthread_mutex_t readLock_;
pthread_cond_t wait_;

void PalindromeDatabase::initializeLocks()
{
    sem_init(&semaphore_, 0, numberOfReaders_);
    pthread_mutex_init(&lock_, nullptr);
    pthread_mutex_init(&readLock_, nullptr);
    pthread_cond_init(&wait_, nullptr);
}

void PalindromeDatabase::lockReaders()
{
    pthread_mutex_lock(&lock_);
    {
        pthread_mutex_lock(&readLock_);
        sem_wait(&semaphore_);
        pthread_mutex_unlock(&readLock_);

        ++readersActive_;
    }
    pthread_mutex_unlock(&lock_);
}

void PalindromeDatabase::lockReaders()
{
    pthread_mutex_lock(&lock_);
    {
        pthread_mutex_lock(&readLock_);
        sem_wait(&semaphore_);
        pthread_mutex_unlock(&readLock_);

        ++readersActive_;
    }
    pthread_mutex_unlock(&lock_);
}

void PalindromeDatabase::unlockReaders()
{
    sem_post(&semaphore_);

    pthread_mutex_lock(&lock_);
    {
        --readersActive_;

        if (readersActive_ == 0)
            pthread_cond_signal(&wait_);
    }
    pthread_mutex_unlock(&lock_);
}

void PalindromeDatabase::lockWriters()
{
    pthread_mutex_lock(&lock_);
    {
        if (readersActive_ != 0)
        {
            do
            {
                pthread_cond_wait(&wait_, &lock_);
            } while (readersActive_ != 0);
        }

        pthread_mutex_lock(&readLock_);
        for (int i = 0; i < numberOfReaders_; ++i)
            sem_wait(&semaphore_);
        pthread_mutex_unlock(&readLock_);
    }
    pthread_mutex_unlock(&lock_);
}

void PalindromeDatabase::unlockWriters()
{
    for (int i = 0; i < numberOfReaders_; ++i)
        sem_post(&semaphore_);
}
4

1 に答える 1

2

コードにはかなりの問題があります。

  1. セマフォはライターのみが使用するため、意味がありません。
  2. ライターをロックしている間はミューテックスを使用しますが、ロックを解除している間は使用しません。
  3. #readersがゼロになると、リーダーは変更された条件を通知し、ライターは条件変数の通知を待ちますが、条件をチェックしません。
  4. ライターをロックするときに、＃readersがすでにゼロの場合、実際にはロックされません。

簡単だという私の発言を考えた後、ロックはまだトリッキーです。私はそれについて考えました。正しい表記ではなく正しい順序に焦点を当てて、この擬似コードでそれを解読したいと思います。

void lockReader()
{
  lock(rdmutex);  // make sure Reader and Writer can't interfere during locking
  lock(wrmutex);  // lock mutex so waitfor can unlock
  while (writer_)
    waitfor(wrcv, wrmutex);  // no active writers

  ++readers_; // at least 1 reader present
  unlock(wrmutex);
  unlock(rdmutex);
}

void unlockReader()
{
  lock(rdmutex);
  bool noReaders = (--readers_ == 0);
  unlock(rdmutex);
  if (noReaders) signal(rdcv); // signal when no more readers
}

void lockWriter()
{
  lock(WritersLock);  // only 1 writer allowed
  lock(rdmutex);  // lock mutex so waitfor can unlock and no interference by lockReader
  while (readers_ != 0)
    waitfor(rdcv, rdmutex);  // wait until no more readers
  lock(wrmutex);
  writer_ = true;  // a writer is busy
  unlock(wrmutex);
  unlock(rdmutex);
  // WritersLock is still locked
}

void unlockWriter()
{
  lock(wrmutex);
  writer_ = false;
  unlock(wrmutex);
  signal(wrcv);  // no more writer (until WritersLock is unlocked)

  unlock(WritersLock);
}

結局のところ、Qtの実装は単純ですが、私のアルゴリズムでは、リーダーの最大数を事前に知る必要はありません。

于 2011-12-21T10:16:31.907 に答える