Skip to content

Instantly share code, notes, and snippets.

@chenshuo
Last active April 23, 2024 10:02
Show Gist options
  • Save chenshuo/6430925 to your computer and use it in GitHub Desktop.
Save chenshuo/6430925 to your computer and use it in GitHub Desktop.
A handful of implementations of Waiter class for discussion.
#include <boost/noncopyable.hpp>
#include <pthread.h>
#include <stdlib.h>
// a superfluous check for pedantic people
inline void CHECK_SUCCESS(int ret)
{
if (ret != 0)
{
abort();
}
}
// Implementaion base for init-destroy mutex_ and cond_
class WaiterBase : boost::noncopyable
{
protected:
WaiterBase()
{
CHECK_SUCCESS(pthread_mutex_init(&mutex_, NULL));
CHECK_SUCCESS(pthread_cond_init(&cond_, NULL));
}
~WaiterBase()
{
CHECK_SUCCESS(pthread_mutex_destroy(&mutex_));
CHECK_SUCCESS(pthread_cond_destroy(&cond_));
}
pthread_mutex_t mutex_;
pthread_cond_t cond_;
};
// Version 1: orininal from the book, NOT MY BOOK
// Incorrect, could lose signal
class Waiter1 : private WaiterBase
{
public:
void wait()
{
CHECK_SUCCESS(pthread_mutex_lock(&mutex_));
CHECK_SUCCESS(pthread_cond_wait(&cond_, &mutex_));
CHECK_SUCCESS(pthread_mutex_unlock(&mutex_));
}
void signal()
{
CHECK_SUCCESS(pthread_cond_signal(&cond_));
}
};
// Version 2: signal in lock
// Incorrect, could lose signal
class Waiter2 : private WaiterBase
{
public:
void wait()
{
CHECK_SUCCESS(pthread_mutex_lock(&mutex_));
CHECK_SUCCESS(pthread_cond_wait(&cond_, &mutex_));
CHECK_SUCCESS(pthread_mutex_unlock(&mutex_));
}
void signal()
{
CHECK_SUCCESS(pthread_mutex_lock(&mutex_));
CHECK_SUCCESS(pthread_cond_signal(&cond_));
CHECK_SUCCESS(pthread_mutex_unlock(&mutex_));
}
};
// Version 3: add a boolean member
// Incorrect, spurious wakeup
class Waiter3 : private WaiterBase
{
public:
void wait()
{
CHECK_SUCCESS(pthread_mutex_lock(&mutex_));
if (!signaled_)
{
CHECK_SUCCESS(pthread_cond_wait(&cond_, &mutex_));
}
CHECK_SUCCESS(pthread_mutex_unlock(&mutex_));
}
void signal()
{
CHECK_SUCCESS(pthread_mutex_lock(&mutex_));
signaled_ = true;
CHECK_SUCCESS(pthread_cond_signal(&cond_));
CHECK_SUCCESS(pthread_mutex_unlock(&mutex_));
}
private:
bool signaled_ = false;
};
// Version 4: wait in while-loop
// Correct, signal before unlock
class Waiter4 : private WaiterBase
{
public:
void wait()
{
CHECK_SUCCESS(pthread_mutex_lock(&mutex_));
while (!signaled_)
{
CHECK_SUCCESS(pthread_cond_wait(&cond_, &mutex_));
}
CHECK_SUCCESS(pthread_mutex_unlock(&mutex_));
}
void signal()
{
CHECK_SUCCESS(pthread_mutex_lock(&mutex_));
signaled_ = true;
CHECK_SUCCESS(pthread_cond_signal(&cond_));
CHECK_SUCCESS(pthread_mutex_unlock(&mutex_));
}
private:
bool signaled_ = false;
};
// Version 5: wait in while-loop
// Correct, signal after unlock
class Waiter5 : private WaiterBase
{
public:
void wait()
{
CHECK_SUCCESS(pthread_mutex_lock(&mutex_));
while (!signaled_)
{
CHECK_SUCCESS(pthread_cond_wait(&cond_, &mutex_));
}
CHECK_SUCCESS(pthread_mutex_unlock(&mutex_));
}
void signal()
{
CHECK_SUCCESS(pthread_mutex_lock(&mutex_));
signaled_ = true;
CHECK_SUCCESS(pthread_mutex_unlock(&mutex_));
CHECK_SUCCESS(pthread_cond_signal(&cond_));
}
private:
bool signaled_ = false;
};
// Note: version 4 is as efficient as version 5 because of "wait morphing"
// Version 6: signal before set boolean flag
// Correct or not?
class Waiter6 : private WaiterBase
{
public:
void wait()
{
CHECK_SUCCESS(pthread_mutex_lock(&mutex_));
while (!signaled_)
{
CHECK_SUCCESS(pthread_cond_wait(&cond_, &mutex_));
}
CHECK_SUCCESS(pthread_mutex_unlock(&mutex_));
}
void signal()
{
CHECK_SUCCESS(pthread_mutex_lock(&mutex_));
CHECK_SUCCESS(pthread_cond_signal(&cond_));
signaled_ = true;
CHECK_SUCCESS(pthread_mutex_unlock(&mutex_));
}
private:
bool signaled_ = false;
};
// Version 7: broadcast to wakeup multiple waiting threads
// Probably the best version among above.
class Waiter7 : private WaiterBase
{
public:
void wait()
{
CHECK_SUCCESS(pthread_mutex_lock(&mutex_));
while (!signaled_)
{
CHECK_SUCCESS(pthread_cond_wait(&cond_, &mutex_));
}
CHECK_SUCCESS(pthread_mutex_unlock(&mutex_));
}
void broadcast()
{
CHECK_SUCCESS(pthread_mutex_lock(&mutex_));
signaled_ = true;
CHECK_SUCCESS(pthread_cond_broadcast(&cond_));
CHECK_SUCCESS(pthread_mutex_unlock(&mutex_));
}
private:
bool signaled_ = false;
};
// Version 8: modify signaled_ without lock
// Incorrect, data-race and could lose signal
class Waiter8 : private WaiterBase
{
public:
void wait()
{
CHECK_SUCCESS(pthread_mutex_lock(&mutex_));
while (!signaled_)
{
CHECK_SUCCESS(pthread_cond_wait(&cond_, &mutex_));
}
CHECK_SUCCESS(pthread_mutex_unlock(&mutex_));
}
void signal()
{
signaled_ = true;
CHECK_SUCCESS(pthread_cond_signal(&cond_));
}
private:
bool signaled_ = false;
};
@coldear
Copy link

coldear commented Sep 4, 2013

i think version 6 is correct. as long as the flag is set with the protection of a mutex.

@dma1982
Copy link

dma1982 commented Sep 4, 2013

Yes, V7 is better; two key points:

  • for broadcast, reference the difference between notify & notifyAll in Java
  • for while loop, reference Java book about threads; we should check the condition again when got the signal

@tjliupeng
Copy link

It is better to provide a sample to use the waiter class.

@sladewang
Copy link

I agree with coldear that version 6 is correct. Because with the protection of mutex, when pthread_cond_wait function return, the flag signaled_ must have been set to be true.

@llhe
Copy link

llhe commented Sep 10, 2013

one essential fact is lock/unlock a mutex enforces memory barrier.

@selfboot
Copy link

《APUE》 Figure 11-15 just the same with Version 5

@BOT-Man-JL
Copy link

👍
After thinking for a while, I realized that the problem of Solution1&2 was waiting without a condition!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment