# 基于共享内存的生产者消费者模式的无锁队列的实现

## 1 整体设计

### 1.1 总的流程如下：
1.  入队操作：队列向内存管理器申请一块内存，内存管理器从内存的自由分配区分配一块内存返回给队列。
2.  出队操作：队列向内存管理器发去释放内存的请求，内存管理器释放该内存块以供下次使用。

### 1.2 共享内存的的划分
Queue对象内部记录了队列头和队列尾的位置，通过它们自然可以找到每个队列节点的位置。但是Queue对象自己也在共享内存里面，第一个创建Queue对象的进程自然知道Queue对象的位置，但是必须让其他的进程也知道Queue对象的位置，所以就约定一个规则把Queue对象放在一个大家都知道的位置，这里选择了共享内存的起始位置。内存管理器不会对这块区域进行操作，在此之后的那块内存自由分配区才是内存管理器管理的区域。如下图：


![](./共享队列综合设计.png)

## 2 无锁队列（Free Lock）的实现
无锁队列是用细粒度的原子锁实现的，多进程操作时无阻塞并发性能高。网上有五花八门的相关算法实现。我对比了一下，决定采用下面的这个。这个算法性能好是一方面，它同时也解决了队列为空时并发操作可能出现的问题，以及ABA的问题。

![](./linked-lock-free-code.png)

## 3 生产者消费者之间的协作

> 以下说明不包括无等待和超时的情况


生产者消费者之间的相互协作时通过信号实现的，信号量slots代表队列空闲的数量，信号量items代表已插入队列的数量。队列初始化时，slots等于队列的最大长度，items等于0。入队时slots减一，items加1。出队时items减一，slots加1。队列已满时slots的量必然等于0，生产者进入等带状态，有空闲位置的时候会恢复执行。队列为空时items的量必然为0,消费者进入等待状态，有新成员入队的时候会恢复执行。具体协作关系如下图：
![生产者消费者模型](./生产者消费者模型.png)


## 4 内存管理器

要实现对内存的管理，就要记录每个已分配块和空闲块的信息。这些信息就记录在每个块的头部和尾部。这些信息包括块的大小（Block size）, 是否已分配（a表示已分配，f表示空闲），其中空闲块比已分配块还多了两个信息（前驱节点指针predecessor, 后继节点指针successor），分别指向前一个和后一个空闲块的指针。如下图：

![](./malloc_node.png)

Head_listp是一个保留块，里面记录了指向第一个空闲块的指针。每个空闲块又都有前驱节点指针和后继节点指针，这样就形成了一个空闲块双向链表，如图C所示。当用户申请内存的时候，会从Head_listp开始向下遍历，直到找到一个合适大小的空闲块，把该块标记为已分配并移出链表。如果找到的空闲块大于要求的大小太多，空闲块会被分割，一块还留在空闲链表里，一块分配出去使用。初始化的时候有且只有一个大的空闲块，后面对内存的申请都是在这个大块之上不断的切割出来的。这样随着请求的不断产生，内存不断被切割，就会产生太多碎片。所以在释放内存的时候，就应该查看自己的左右相邻的块是否也是空闲的，如果是就应该先合并，再放回空闲块链表。查看自己的左右相邻的块是否是空闲的也很简单，因为该块的左边是左边一个块的Footer,右边是右边一个块的Header，所以很容易找到他们的记录信息。

![](./malloc_list.png)