多线程队列——锁

             最近看了一篇关于多线程队列的文章（http://www.parallellabs.com/2010/10/25/practical-concurrent-queue-algorithm/）觉得很不错，但是对其中有一些地方还不是很懂，于是决定自己根据《C++
Primer 4》的队列模版来实现一个队列。

        代码如下：

#pragma once
#define _AFXDLL
#include<iostream>
#include <pthread.h>
#include<afxmt.h>
template<class type> class Line;
template<class type>
class LineItem
{
public:
	friend class Line<type>;
	LineItem():item( ),next(0){}
	LineItem(const type&t):item(t),next(0){}
	~LineItem(){}
	type item;   
	LineItem *next;
};
template<class type>
class Line
{
public:
	Line(void):head(0),tail(0),num(0),h_lock(FALSE, __T("head lock"), NULL),
		t_lock(FALSE, __T("tail lock"), NULL){InitializeCriticalSection(&cs);}
	Line(Line&l):head(0),tail(0)
	{copy_elems(l);}
	Line& operator=(Line& line)
	{
		if(line.isempty())
		  return *this;
		LineItem<type> *p=line.front();
		LineItem<type> *pt=this->front();
	   while(p->next!=NULL)
	   { 
		  pt->item=p->item;
		  pt=pt->next=new LineItem<type>;	
		  p=p->next;
	   }
	  p->item=pt->item;
	  p->next=NULL;
	  tail=p;
	  num=line.count();
	  return *this;
	}
	~Line(void){destroy();}
	LineItem<type>* front()
	{
		if(num==0)
		{
			return 0;
		}
		if(num==1)
		{	
			return head;
		}
		else
		{			
			return head;			
		}
	}
	LineItem<type>* back(){return tail;}
	void push(const type& item)
	{
		  t_lock.Lock();
		  LineItem<type> *p=new LineItem<type>(item);
		  if(tail==0)
			  head=tail=p;
		  else
		  {
			 tail->next=p;
			 tail=p;
		  }
		  EnterCriticalSection(&cs);
		  ++num;
		  LeaveCriticalSection(&cs); 
		  t_lock.Unlock();
	}
	void pop()
	{		
		if (num==1)
		{
			 t_lock.Lock();
			 head=tail=0;
			 head=0;
			 EnterCriticalSection(&cs);
			 --num;
			 LeaveCriticalSection(&cs); 
			 t_lock.Unlock();
		}
		else
		{
			h_lock.Lock();
			if (head==0)
			{
			   h_lock.Unlock();
			   return;
			}
			LineItem<type> *p=head;
			head=head->next;
			delete p;
			EnterCriticalSection(&cs);
			--num;
			LeaveCriticalSection(&cs);  			
		}
		h_lock.Unlock();
	}
	bool isempty() const
	{
		return head==0;
	}
	std::size_t count()
	{
	   if(isempty())
		 return 0;
	   LineItem<type> *p=head;
	   std::size_t n=0;
	   while(p)
	   {
		 ++n;
		 p=p->next;
	   }
	  return n;
	}

	void clear()
	{
		destroy();
	}

private:
	LineItem<type> *head;
	LineItem<type> *tail;
	int num;
	CMutex h_lock,t_lock;
	CRITICAL_SECTION cs;
	void destroy()
	{
		while(!isempty())
		pop();
		num=0;
	}
	void copy_elems(Line& l)
	{
		for(LineItem<type> *p=l.front();p;p=p->next)
		 push(p->item);
		num=l.count();
	}
};

          本文针对的是队列的pop 和 push 操作，其他问题没有考虑到，所以这个队列仅供分析pop和push 的并发操作。

           这个模版用了两个锁，一个队列头锁h_lock 和一个队列尾锁t_lock ，为什么要用两个锁呢，因为，当一个队列在push操作时，队列里可能不止一个元素，这时，如果只用一个锁，其他线程只能等待，到你push完后，其他线程才能执行操作；如果用两个锁的话，可以让两个线程一起分别针对头尾进行操作，因为他们没有用到相同的资源，所以没必要互斥，这样效率会跟高。

            如果，队列是空的或者只有一个元素，会发生什么情况呢？先看代码：

void pop()
	{		
		if (num==1)
		{
			 t_lock.Lock();
			 head=tail=0;
			 head=0;
			 EnterCriticalSection(&cs);
			 --num;
			 LeaveCriticalSection(&cs); 
			 t_lock.Unlock();
		}
		else
		{
			h_lock.Lock();
			if (head==0)
			{
			   h_lock.Unlock();
			   return;
			}
			LineItem<type> *p=head;
			head=head->next;
			delete p;
			EnterCriticalSection(&cs);
			--num;
			LeaveCriticalSection(&cs);  			
		}
		h_lock.Unlock();
	}
void push(const type& item)
	{
		  t_lock.Lock();
		  LineItem<type> *p=new LineItem<type>(item);
		  if(tail==0)
			  head=tail=p;
		  else
		  {
			 tail->next=p;
			 tail=p;
		  }
		  EnterCriticalSection(&cs);
		  ++num;
		  LeaveCriticalSection(&cs); 
		  t_lock.Unlock();
	}

           如果队列为空，头尾指针没有指向相同的空间，因为头尾指针都为空 （head=tail=Null，它们的值相同） 这时，如果两个线程一个要push ，一个要pop，他们是不会发生互斥的，因为它们可以分别判断头尾指针是否为0 ，如果为0 ，就分别释放头尾两个锁。

          如果队列只有一个元素，这时两个线程分别执行push 和 pop 操作时，就会发生死锁，因为头指针和尾指针都指向同一个元素，这样会降低效率。（这时，前面介绍的那篇文章的解决方法是，在队列头前再加入一个元素，做头指针，当队列为空时，队列只有一个头元素，具体情况请看那篇文章。）我的方法是，根据计数器（num）的值来判断要用一个锁，还是用两个锁，当队列只有一个元素时，即num==1时，push
和 pop 操作只用一个锁，即t_lock； 当队列不止一个元素时，就用两个锁。具体看上面代码。计数器num是用来判断用多少个锁的依据。谢谢！

          参考：http://www.parallellabs.com/2010/10/25/practical-concurrent-queue-algorithm/