环形队列解决TCP粘包问题

转自http://blog.csdn.net/u013898698/article/details/54846084

1、环形缓冲区的实现原理

环形缓冲区通常有一个读指针和一个写指针。读指针指向环形缓冲区中可读的数据，写指针指向环形缓冲区中可写的缓冲区。通过移动读指针和写指针就可以实现缓冲区的数据读取和写入。在通常情况下，环形缓冲区的读用户仅仅会影响读指针，而写用户仅仅会影响写指针。如果仅仅有一个读用户和一个写用户，那么不需要添加互斥保护机制就可以保证数据的正确性。如果有多个读写用户访问环形缓冲区，那么必须添加互斥保护机制来确保多个用户互斥访问环形缓冲区。

 

问题描述
    我在使用Socket接收消息时，将会触发一个接收函数。（BCB中的是ClientRead函数）所以我在此函数处接收信息，并做相应处理。那问题来了：由于传输的数据包都是我自定义的，我明确的知道长度为多多少。可实际效果却是，有时候接不够我期待的长度，而甚至有时候一次接收的数据包长度竟然比我预期的要长10个字节。当时只有设定条件将不满足我预期长度的数据包丢弃。

 

问题分析

看了上面描述，想必大家也明白我的错误在哪了吧？实际是我对Socket的接收机制理解有误。TCP/IP只保证发送包按顺序到达目的地，但可能由于网络状况他会自动分包发送，这样就导致接收端的接受函数每次提交时只有若干数据，不一定是我预期的一个完整的包。可以这样理解，发过来的实际是一个‘流’。

看来要很好的解决这个问题，那就只有先将接收的数据保存起来，再来做处理。

 

处理模型

为了要保存接收数据，我们首先就要建立一个缓冲区。那第一个问题来了：由于我们要接收的信息是不可预知的，那难道这个缓冲区要无限的扩容？

可我们的实际PC内存肯定是有限的，所以我们必须建立一套内存缓冲区可以被反复利用的机制 —— 环形队列。

我们用图来说明环形队列的工作原理：

 

 

图1 蓝色为写入的数据，绿色为已经读取处理的数据

看上图1，在正常状态下：Write指针在写入数据，而Read指针在Write指针之前，说明缓冲区后端还有空余空间。

在指针回滚状态下：Write指针在Read指针之前，说明缓冲区的前端已经有空闲的空间。

除了这两种状态外，我们不得不再考虑一种即将错误状态：

 

图2蓝色为写入的数据，棕红色为未处理的数据

看图2，无足够空间：当Write指针回滚，发现无足够空间，将和Read指针发生交集（虚点部分）这显然是不合理的。一部分未处理数据将被覆盖破环。所以我们必须重新调整整个缓冲区。

重新分配调整：当遇到空间不足，不能实现Write指针回滚的情况，我们只有重新开辟一个更大一点的缓冲区，并把未处理数据（棕红色）和写入数据（蓝色）按顺序复制到新的缓冲区内，并调整好Read和Write指针的位置。最后释放掉原来的缓冲区。

我们可以看到，经过这样一个过程，我们的缓冲区，将在Read指针处理速度较慢并在处理信息量增大时，逐渐扩容。但是，当扩容到一定程度，将达到一个平衡。因为信息量不可能无限增大，当需处理信息量达到最大值再结合Read指针的不断处理，缓冲区的大小也将稳定下来。

我们一开头就给此缓冲区命名为‘环形队列’。从以上的图和文字，我们可以形象的理解：由于缓冲区大小最终将稳定，Write和Read指针将无障碍的在缓冲区中不断循环回滚，其运行轨迹，将是一个环形。