申请会员ID：billhong1998

1、申 请 I D ：                                     billhong1998
2、个人邮箱：service@52pojie.cn     xw0323@126.com
3、原创技术文章： 无锁环形队列读写网络数据的一种算法

1、 技术关键点：基于环形队列数据结构，实现一种单线程读、单线程写并发模式下的无锁读写网络数据方法。2、 所属技术领域：涉及网络数据读写和处理领域，是一种使用无锁环形队列来缓存和处理网络数据的方法。3、 背景技术：Linux内核kfifo是最接近本算法的一种操作环形队列的算法，采用先进先出（First In First Out, FIFO）的数据进出机制，队列构建于固定大小的连续内存空间（数组）之上，队列首尾两个位置逻辑上相互毗邻，队列的最后一个位置的下一个位置是队列的第一个位置，队列的第一个位置的前一个位置是队列的最后一个位置，逻辑上形成了一个环形，被称作环形队列或环形缓冲区，数据结构如下图所示：

该算法内部维护着环形队列当前的读位置和写位置，当有数据被写入后，写位置发生变化，当有数据被读出后，读位置发生变化，数据在这个环形队列中以先进先出的方式不断地被生产出来和被消费掉，在单一生产者和单一消费者并发模式下可实现对环形队列的无锁读写。该算法是操作系统实现同步机制和数据一致性的重要保证，是包括Linux在内的各种操作系统（含嵌入式）的重要核心算法之一，在各类应用软件中也有着广泛的应用。1、 背景技术的缺点：第一个缺点就是要求队列的大小必须为2的整数次幂(2^n)，在很多应用场合中不应该有这种限制的，也是不合理，会造成内存空间的浪费，比如，在只需要513个字节队列的情况下，kfifo会强制使用最少1024个字节的队列空间，会浪费511个字节，在队列空间要求较多的场合浪费更加明显。kfifo代码遵循GPL（GNU GPL，GNU General Public License，通用公共许可协议）协议，直接使用或修改kfifo代码后再使用都需要遵循该协议。 2、 目的：针对kfifo算法要求队列的大小必须为2的整数次幂的缺点进行改进，数据结构上取消该限制，队列大小可以是任意大于0的值；构建新算法的同时也继承了kfifo使用环形队列数据结构和使用无符号整数来计数的优点（环形队列和无符号整数运算是纯数学上的智力活动方法，不受GPL协议或其它专利权限制）。采用单线程读和单线程写的并发模式来同时收取和处理网络数据包，实现无锁读写环形队列。3、 技术方案：为实现目标，首先在共享内存中初始化一个环形队列，数据结构和kfifo算法中的环形队列类似（去掉了原算法中的mask，增加了内部计算必要的增补偏移量等），队列首尾两个位置逻辑上相互毗邻，在逻辑上形成一个环。具体参数包括内部缓冲区的写位置和读位置、内部缓冲区大小、内部缓冲区数组等,内部缓冲区数组是真正存储数据的地方，初始化时内部缓冲区数组的大小必须和内部缓冲区大小参数相匹配。缓冲区大小不再像kfifo算法那样限制为必须为2的整数次幂，而可以是任何大于0的值。写位置和读位置参数初始化为相同的值即可（两值相同时表示内部缓冲区为空，也就是队列为空）。建立一个网络连接，此后接收和发送网络数据都基于此连接。创建单独且唯一的数据消费者线程，只要环形队列里有数据，该线程就及时将需要长度的数据取出并发送给网络连接的另一端（对端）。取数据的方法命名为read，带三个参数，分别是环形队列指针、接收数据的内存指针和需要读取数据的长度，返回实际读取长度，read方法会调整环形队列内部读位置从而腾出更多的空闲空间，读位置也指示出队列中最老（最旧）的数据从哪里开始。创建单独且唯一的网络数据读取线程作为环形队列数据的生产者，环形队列的数据均来自于该线程从网络连接对端读取到的数据。一旦有数据，立即将数据读出并放入到环形队列当中。写入数据的方法命名为write，带三个参数，分别是环形队列指针、提供数据的内存指针和需要存入的数据的长度，返回实际写入长度，write方法会调整环形队列内部写位置从而指示有更多的数据进入到了环形队列当中（同时也说明空闲空间减少了），写位置指出下一次写入操作将从队列的哪一个空闲位置开始。read和write分别是单一消费者线程和单一生产者线程调用的读取数据和写入数据的方法，也是本算法最主要的两个方法，它们在多CPU或CPU多核并行运行模式下不需要加锁，从而实现了基于环形队列的无锁读写。由于消除了kfifo算法内部缓冲区大小必须为2的整数次幂的限制，原算法中的mask已经没有意义，就去掉了，但增加了新算法需要用到的增补偏移量。计算缓冲区空闲及已占空间大小和计算下一个读、写位置等算法也都做了相应的调整，同时也继承了kfifo算法使用无符号整数来计数和使用加减算数运算来替代取模运算（%）等所有高效率特点，使得本算法和kfifo算法在运行效率上是一致的。以下是环形队列里面有5个数据的示意图：

环形队列里的读位置只被数据消费者线程改写，而写位置只被数据生产者线程改写。默认策略下，环形队列里的数据在没有被消费掉之前是不能被生产者线程的写操作覆盖掉的，但在某些情况下，尤其是内存空间小、实时性要求高的场合，如嵌入式最新日志存储，可以扩展本算法的方法，允许环形队列里的最老的数据被生产者线程用最新的数据覆盖。1、 本算法技术方案带来的有益效果：本算法继承了著名的kfifo算法所有的优点，同时也消除了该算法内部缓冲区大小必须为2的整数次幂的缺点，避免了内存空间的浪费，应用场景更加灵活多样，缓冲区大小几乎没有任何限制，只要大于0即可。本算法是高效队列算法之一，运行效率和kfifo是一样的，通过对kfifo算法层面上的修改使得根据本算法开发的代码不再受GPL协议限制。高效率队列是所有操作系统的核心算法之一，本算法可以应用于各类操作系统（含嵌入式操作系统）之中，在应用软件中使用也没有问题。2、 使用实例：一个简单的应用实例：接收网络数据并回发（echo）回去。本应用为一个网络服务，启动时将初始化一个环形队列，并将接收一个（为简化描述，限制为一个）来自网络的连接请求并与其建立TCP（Transport Control Protocol）网络连接；之后会创建一个单独的数据接收线程和一个单独的数据发送线程，数据接收线程不断地接收来自网络连接对端发送来的数据并存入到环形队列中，规定来自网络对端的一段数据最大长度不超过环形队列内部缓冲区的长度且数据都以回车符结束，当有数据存入环形队列后，数据接收线程就通过异步信号量的方式通知数据发送线程队列有数据了，数据发送线程被信号量唤醒后立刻读取环形队列中的内容并将其放到外部的临时缓冲区中，如果发现读取的内容中包括回车符，就将回车符及其以前的所有数据马上发送给对端，从效果上看就实现了将收到的数据回发（echo）回去的功能，如果把回发数据当作以回车符结尾的一句话的话，对端说什么话，本服务也回应同样的话给对端。回车符以后的内容仍然保留在临时缓冲区当中以方便和下一次从环形队列中读出的数据相拼接。就这样本应用服务不断地从网络对端读取数据并不断地回发回去。注意，在这个多线程（一个线程读、一个线程写）并发操作环形队列这个共享资源的情况下，不需要像往常那样用加锁机制来控制对共享资源的访问顺序，从而实现了高效读写环形队列效果，也就是本算法说的无锁读写网络数据的功能。应用的结束是靠判断结束符（回车符）来控制的，如果对端发来的数据只是结束符，应用服务将自行终止。S1：主线程（主进程所在的线程）创建一个环形队列初始化环形队列并指定其内部缓冲区大小为一个固定的、大于0的值，队列的写位置和读位置都被初始化为0，这时队列初始空闲空间大小就为那个固定值。S2：建立网络连接主线程监听本机IP（Internet Protocol）地址上的一个端口，一旦有来自网络的连接请求，就与其建立一个TCP连接（限制为一个TCP连接），并将该TCP连接注册到异步I/O（Input/Output）事件通知机制的EPOLL（Event Poll）实例中。S3：主线程创建并启动数据发送线程数据发送线程独立于主线程运行，当环形队列中没有数据时，就采用等待信号量的异步方式来接收来自下面将提到的数据接收线程的信号量通知，这个异步通知说明数据接收线程刚刚往环形队列里放入了数据，要求数据发送线程及时处理，收到通知后，数据发送线程使用read方法将环形队列的所有信息取出并放入到一个临时缓冲区中。数据发送线程进而将截止到回车符的收到的数据马上发送给TCP连接的对端，不含回车符的数据或回车符之后的数据暂不发送，仍然暂存于临时缓冲区当中，以备下一次拼接后续有回车符的数据做准备。如果数据一次发送不完，数据发送线程将在EPOLL异步I/O事件通知机制的配合下保证将数据全部发送出去。如果发送的数据是只是回车（结束符），数据发送线程将自行终止。S4：主线程创建并启动数据接收线程数据接收线程独立于主线程运行，通过监听异步I/O事件的EPOLL文件描述符来获知是否有网络连接对端发来的数据，一旦发现有数据，就检查环形队列是否有空闲空间，一旦有，就调用write方法尽可能多地读取网络数据并放入环形队列中并通过信号量异步通信方式方式通知数据发送线程可以处理数据了，如果环形队列没有空闲空间或空间不够，将保持剩余的数据仍然驻留在TCP连接的缓冲区中不取出以备下次读取，下次读取数据并放入环形队列的功能是在EPOLL异步I/O事件通知机制的配合下完成的。如果接收的数据是只是回车（结束符），数据接收线程将自行终止。S5：主线程等待发送和接收线程结束 主线程创建并启动了数据接收和发送线程操作之后，就执行join方法等待数据接收和发送线程终止，只有这两个线程都终止后，主线程才被唤醒继续执行。S6：主线程做清理工作并退出清理工作包括关闭网络连接和销毁环形队列等。

Hmily

抱歉，未能达到申请要求，申请不通过，可以关注论坛官方微信（吾爱破解论坛），等待开放注册通知。