管程
管程可以视为一个线程安全的数据结构，其内部提供了互斥与同步操作，向外提供访问共享数据的专用接口(接口被称为管程的过程)，通过管程提供的接口即可达成共享数据的保护与线程间同步。
使用管程，可以简化线程间互斥、同步的编码复杂度(否则需自己控制互斥、同步机制，并保证正确)，可以集中分散的互斥、同步操作代码，更容易验证、查错，也更可读(反之，信号量的PV操作可能分散到各个地方，验证、阅读相对麻烦)
管程的特点
- 共享数据仅能被管程的过程访问
- 线程通过调用管程的过程进入管程
- 任何时候仅能有一个线程在管程中执行，其他阻塞直到可用
- 管程内共享数据不可用时
- 需要共享数据的线程将阻塞并释放管程
- 其他线程可进入管程构造数据可用条件，并通知阻塞线程
- 管程内共享数据可用时， 被阻塞线程将在合适时间重新进入管程
管程分类
管程中仅能有一个线程在其中执行，根据发起通知时，被唤醒线程(T1)执行，还是唤醒线程(T2)继续执行，可将管程分为三种：
- Mesa管程(Lampson/Redell)：T2继续执行直到退出，T1进入入口队列，后面与其他线程公平竞争(由于不是立刻执行，所以当T1执行时，条件可能已经不满足，因此需循环检测条件是否仍旧达成)
- Hoare管程：T2立即阻塞并释放管程，T1马上执行，退出后T2恢复执行(多两次线程切换)
- Brinch Hanson管程：T2的通知操作仅允许在退出时发送通知，通知发送后T2结束，T1开始执行
管程的实现
根据前述管程特点，管程应该是一个对象，内部封装了资源，该对象实现了互斥及与阻塞、唤醒机制
使用锁，搭配条件变量来实现互斥及与阻塞、唤醒机制
下面简单介绍条件变量，后面的管程代码有一个小优化，涉及对条件变量实现的理解
条件变量
条件变量是同步原语，其内部有一个队列，用于存放被wait阻塞的线程，当另一个线程发起通知时，如果队列不为空，队头线程将被唤醒，否则，什么也不做。条件变量也可以一次性唤醒队列中的全部阻塞线程。
条件变量的一种实现
条件变量里有一个存储阻塞线程的队列。由于阻塞线程和唤醒通知线程都需要访问这同一队列，所以还有一个用于保护队列的锁，锁粒度不大，并且不需要线程切换，应为自旋锁
wait函数会将当前线程入队，并原子的进行锁释放与当前线程阻塞，阻塞直到另一线程通知才解除，解除后重新获取锁。锁释放与当前线程阻塞必须是原子的，否则，别的线程发出的唤醒通知，可能发生在当前线程阻塞之前，这会造成唤醒丢失
signal函数出队一个阻塞线程并唤醒他，当队列为空时，不做任何事情
broadcast函数将逐个唤醒队列中的所有阻塞线程
管程实现代码
下面实现了一个管程，同时符合mesa与hanson管程的定义，并且做了一些优化，取消掉了不必要的通知操作
#ifndef __MONITOR_H_
#define __MONITOR_H_
#include <list>
#include <mutex>
#include <utility>
#include <condition_variable>
template<typename T>
class Monitor{
public:
Monitor(): m_iMaxCount(100), m_bStop(false){
}
Monitor(int iMaxCount) : m_iMaxCount(iMaxCount), m_bStop(false){
}
~Monitor() = default;
void Enqueue(const T& data){
Append(data);
}
void Enqueue(T&& data){
Append(std::forward<T>(data)); //转发data的原属性，此处转发data的右值引用
}
void Dequeue(T& data){
std::unique_lock<std::mutex> lk(m_mMutex);
m_cvNotEmpty.wait(lk, [this](){return m_bStop || !IsEmpty(); });
if(m_bStop){
return;
}
bool bNeedNotify = IsFull();
data = m_listData.front();
m_listData.pop_front();
lk.unlock();
if(bNeedNotify){
m_cvNotFull.notify_one();
}
}
void Stop(){
{
std::lock_guard<std::mutex> lk(m_mMutex);
m_bStop = true;
}
m_cvNotEmpty.notify_all();
m_cvNotFull.notify_all();
}
private:
template<typename U>
void Append(U&& data){ //实现通用引用
std::unique_lock<std::mutex> lk(m_mMutex);
m_cvNotFull.wait(lk, [this](){return m_bStop || !IsFull(); });
if(m_bStop){
return;
}
bool bNeedNotify = IsEmpty();
m_listData.emplace_back(std::forward<U>(data)); //再次转发
lk.unlock();
if(bNeedNotify){
m_cvNotEmpty.notify_one();
}
}
bool IsFull(){
return static_cast<int>(m_listData.size()) == m_iMaxCount;
}
bool IsEmpty(){
return 0 == static_cast<int>(m_listData.size());
}
Monitor(const Monitor& rhs) = delete;
Monitor(Monitor&& rhs) = delete;
Monitor& operator=(const Monitor& rhs) = delete;
Monitor& operator=(Monitor&& rhs) = delete;
private:
int m_iMaxCount;
bool m_bStop;
std::mutex m_mMutex;
std::list<T> m_listData;
std::condition_variable m_cvNotEmpty;
std::condition_variable m_cvNotFull;
};
#endif //!__MONITOR_H_
- 代码中条件变量使用了带可调用对象作为参数的wait，它的实现是这样的
template<typename _Predicate>
void
wait(unique_lock<mutex>& __lock, _Predicate __p)
{
while (!__p())
wait(__lock);
}可调用对象返回true则什么都不做，否则，重复wait到满足条件，这可以避免虚假唤醒，同时也是Mesa管程的行为
- 进行队列不满、不空通知前，检查队列原状态 ，通过状态判断是否进行notify
- 在由满到不满，空到不空这两种状态变化下，才进行通知
- 根据上面的条件变量的signal函数实现可知，通知时会使用到锁，虽然锁粒度很小，并且是自旋锁，但是也存在较大的性能消耗，通过一个简单的判断，避免了通知，也就避免了锁
- 模板方法Append实现了通用引用，使得Append同时支持引用左值与右值，配合std::forward<>可将参数原属性(左值引用或右值引用)转发给另一个函数当参数
- 实现通用引用必须含有&&，并且需要发生类型推导，所以Append必须是不同的模板参数U，而不能和类模板Monitor一样为T(T的类型在模板实例化时固定，将不能发生类型推导)
- 一切变量都是左值(变量本身分配有内存空间，可以对其取地址)，所以在调用实现了通用引用函数时，应该std::forward<>一下，否则通用引用绑定的是变量本身(左值)，即得到左值引用
- std::forward<>靠引用折叠实现对原属性的转发：含左值引用折叠后为左值引用，否则为右值引用
template<typename _Tp>
constexpr _Tp&&
forward(typename std::remove_reference<_Tp>::type& __t) noexcept
{ return static_cast<_Tp&&>(__t); }
template<typename _Tp>
constexpr _Tp&&
forward(typename std::remove_reference<_Tp>::type&& __t) noexcept
{
static_assert(!std::is_lvalue_reference<_Tp>::value, "template argument"
" substituting _Tp is an lvalue reference type");
return static_cast<_Tp&&>(__t);
}- 参数_Tp若为type &(左值引用)
则static_cast<_Tp&&>为static_cast<type& &&>，折叠后为static_cast<type&>，
所以转发返回值仍为为左值引用- 参数_Tp若为type &&(右值引用)
则static_cast<_Tp&&>为static_cast<type&& &&>，折叠后为static_cast<type&&>，
所以转发返回仍为右值引用- Enqueue最好不要以通用引用方式实现，除非调用者明确知道使用std::forward<>(不用的代价为丢失右值语义)
同步队列
管程其实也是一种同步队列，现在
- 在管程的基础上添加Try类操作，Try类操作操作时，若条件无法满足，则立刻返回false，不阻塞
- 添加获取元素个数的方法
得到同步队列如下
代码
#ifndef __SyncQueue_H_
#define __SyncQueue_H_
#include <list>
#include <mutex>
#include <utility>
#include <condition_variable>
template<typename T>
class SyncQueue{
public:
SyncQueue() : m_iMaxCount(100), m_bStop(false){
}
SyncQueue(int iMaxCount) : m_iMaxCount(iMaxCount), m_bStop(false){
}
~SyncQueue() = default;
void Enqueue(const T& data){
Append(data);
}
void Enqueue(T&& data){
Append(std::forward<T>(data)); //转发data的原属性，此处转发data的右值引用
}
bool TryEnqueue(const T& data){
return TryAppend(data);
}
bool TryEnqueue(T&& data){
return TryAppend(std::forward<T>(data));
}
void Dequeue(T& data){
std::unique_lock<std::mutex> lk(m_mMutex);
m_cvNotEmpty.wait(lk, [this](){return m_bStop || !IsEmpty(); });
if(m_bStop){
return;
}
bool bNeedNotify = IsFull();
data = m_listData.front();
m_listData.pop_front();
lk.unlock();
if(bNeedNotify){
m_cvNotFull.notify_one();
}
}
bool TryDequeue(T& data){
std::unique_lock<std::mutex> lk(m_mMutex);
if(m_bStop || IsEmpty()){
return false;
}
bool bNeedNotify = IsFull();
data = m_listData.front();
m_listData.pop_front();
lk.unlock();
if(bNeedNotify){
m_cvNotFull.notify_one();
}
return true;
}
void Stop(){
{
std::lock_guard<std::mutex> lk(m_mMutex);
m_bStop = true;
}
m_cvNotEmpty.notify_all();
m_cvNotFull.notify_all();
}
int Size(){
std::lock_guard<std::mutex> lk(m_mMutex);
return static_cast<int>(m_listData.size());
}
private:
template<typename U>
bool TryAppend(U&& data){ //实现通用引用
std::unique_lock<std::mutex> lk(m_mMutex);
if(m_bStop || IsFull()){
return false;
}
bool bNeedNotify = IsEmpty();
m_listData.emplace_back(std::forward<U>(data)); //再次转发
lk.unlock();
if(bNeedNotify){
m_cvNotEmpty.notify_one();
}
return true;
}
template<typename U>
void Append(U&& data){ //实现通用引用
std::unique_lock<std::mutex> lk(m_mMutex);
m_cvNotFull.wait(lk, [this](){return m_bStop || !IsFull(); });
if(m_bStop){
return;
}
bool bNeedNotify = IsEmpty();
m_listData.emplace_back(std::forward<U>(data)); //再次转发
lk.unlock();
if(bNeedNotify){
m_cvNotEmpty.notify_one();
}
}
bool IsFull(){
return static_cast<int>(m_listData.size()) == m_iMaxCount;
}
bool IsEmpty(){
return 0 == static_cast<int>(m_listData.size());
}
SyncQueue(const SyncQueue& rhs) = delete;
SyncQueue(SyncQueue&& rhs) = delete;
SyncQueue& operator=(const SyncQueue& rhs) = delete;
SyncQueue& operator=(SyncQueue&& rhs) = delete;
private:
int m_iMaxCount;
bool m_bStop;
std::mutex m_mMutex;
std::list<T> m_listData;
std::condition_variable m_cvNotEmpty;
std::condition_variable m_cvNotFull;
};
#endif //!__SyncQueue_H_
参考资料
Monitors and Condition Variables
操作系统精髓与设计原理 原书第6版第五章第四节
Universal References in C++11 -- Scott Meyers