《缓冲区设计环形队列.docx》由会员分享，可在线阅读，更多相关《缓冲区设计环形队列.docx（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、缓冲区设计-环形队列在程序的两个模块间进展通讯的时候，缓冲区成为一个常常使用的机制。如上图，写入模块将信息写入缓冲区中，读出模块将信息读出缓冲区。这样使得：将程序清楚地划分模块，建立良好的模块化架构，使得写入和读出成为高聚合，低耦合的模块。对于写入和读出的处理可能产生的快慢不均匀的状况进展平衡，使得整个处理的速度趋于平滑的均匀状态，避开消灭读出模块处理的慢速使得写入模块等待使得响应速度下降的状况；同样，也避开写入模块的快慢不均匀，使得读出模块忙闲不一的状况。可以增加处理的并发性。由于写入和读出模块的良好设计和划分，可以使得它们彼此隔离和独立，从而，使用线程和进程产生不同的并发处理，并通过缓冲区
2、大小的调整，使得这个处理到达良好的匹配和运行状态。例如，写入模块可以有 N 个线程或进程，读出模块可以有M 个线程和进程，缓存冲区可以配置L 的大小。N、M、L 可以通过模拟试验设定适应具体应用的值。也可以建立一套自动调整的机制，固然，这样会造成设计的简洁性。缓冲区明显不适合下面的状况：数据的接收处理原本就是亲热相关，难以划分模块。处理中的模块间明显不存在处理不均匀的状况，或者不是主要问题。需要同步响应的状况。明显，写入端只是将信息 push 到队列中，并不能得到读出端的处理响应信息，只能适合于异步的信息传递的状况。缓冲区的设计：缓冲区是一个先进先出队列。写入模块将信息插入队列；读出模块将信息
3、弹出队列。写入模块与读出模块需要进展信息的协调和同步。对于多线程和多进程的写入或读出模块，写入模块间以及读出模块间需要进展临界区处理。队列使用环形队列，如上图。环形队列的特点是，不需要进展动态的内存释放和安排，使用固定大小的内存空间反复使用。在实际的队列插入和弹出操作中， 是不断穿插进展的，当push 操作时，head 会增加；而pop 操作时，tail 会增加。push 的速度快的时候，有可能追上 tail，这个时候说明队列已经满了，不能再进展 push 的操作了，需要等待 pop 操作腾出队列的空间。当 pop 的操作快，使得 tail 追上 head，这个时候说明队列已空了，不能再进展
4、pop 操作了，需要等待 push 进来数据。下面列出了一个环形队列类的的数据构造的源程序 。cpp view plainc opy1.2.3.4.5.6.7.8.9./* LoopQue.h Author: ZhangTaoDate: July 26, 2023*/# ifndef LoopQue_h# define LoopQue_h10. # include 11.12. namespace13.xtl14. template15. class LoopQue_impl 16. public:17. static int addsize(int max_size) 18. return
5、max_size * sizeof(_Tp);19.20.21.LoopQue_impl(int msize) : max_size(msize), _front(0), _rear(0), _s ize(0) 22.23._Tp& front return data_front; 24.25. void push(const _Tp& value) 26. data_rear = value;27. _rear = (_rear + 1) % max_size;28. _size+;29.30.31. void pop 32. _front = (_front + 1) % max_size
6、;33. _size-;34.35.36. int check_pop(_Tp& tv) 37. if ( empty )38. return -1; 39.40. tv = front;41. pop;42.43.44. int check_push(const _Tp& value) 45. if ( full )46. return -1; 47.48.push(value);49.50.51. bool full const return _size = max_size; 52. bool empty const return _size = 0; 53. int size cons
7、t return _size; 54. int capacity const return max_size; 55.56. private:57. int32_t _front; / front index58. int32_t _rear;/ rear index59. int32_t _size;/ queue data record number 60.61.const int32_t max_size; / queue capacity 62.63._Tp data0;/ data record occupy symbol64. ;65.66. template67. struct
8、LoopQue_allocate 68. LoopQue_impl& allocate(int msize)69. char *p = new charsizeof(LoopQue_impl) +70. LoopQue_impl:addsize(msize);71. return *(new (p) LoopQue_impl(msize);72. 73.74. void deallocate(void *p)75. delete (char *)p;76. 77. ; 78.79. template typename _Tp, typename Alloc = LoopQue_allocate
9、 80. class LoopQue81. public:82. typedef _Tp value_type; 83.84. LoopQue(int msize) : impl(alloc.allocate(msize) 85. LoopQue alloc.deallocate(void *)&impl); 86.87. value_type& front return impl.front; 88. const value_type& front const return impl.front; 89.90. void push(const value_type& value) impl.
10、push(value); 91.void pop impl.pop; 92.93.int check_pop(value_type& tv) return impl.check_pop(tv); 94.int check_push(const value_type& value) return impl.check_push( value); 95.96. bool full const return impl.full; 97. bool empty const return impl.empty; 98. int size const return impl.size; 99.100. p
11、rivate :101. Alloc alloc;102. LoopQue_impl& impl;103. ; 104.105. / end of 106.107. # endif / end of 108.程序里定义了两个类 LoopQue_impl 及 LoopQueue。前者定义了环形队列的根本数据构造和实现，后者又进展了一次内存安排包装。21 行的LoopQue_impl 的构造函数是以队列的空间大小作为参数创立这个类的。也就是说，在类创立的时候，就打算了队列的大小。63 行中定义的队列的数组空间为 _Tp data0。这似乎是一个惊异的事情。事实上，这个空间大小应当是 max_siz
12、e 个数组空间。 但由于 max_size 是在类创立的时候确定的，在这里，data0 只起到一个占位符的作用。所以，LoopQue_impl 这个类是不能直接使用的， 需要正确的安排好内存大小，才能使用，这也是需要里另外设计一个类LoopQueue 的重要缘由之一。或许您会惊异，为什么要这样使用呢？假设定义一个指针， 例如：_Tp *data， 然后在构造函数里面使用 data = new _Tpmax_size，不是很简洁吗？但是，不要遗忘了， 我们这个环形队列类有可能会是一个进程间共享类。 例如，一个进程 push 操作，另一个进程 pop 操作。这样，这个类是需要建立在共享内存中的。而
13、共享内存中的类的成员，假设包含有指针或者引用这样的类型， 将给内存安排带来很大的麻烦。而我们这样以这个占位符的方式设计这个类，将削减这种麻烦和简洁性。17 行的addsize 的类函数确定了LoopQue_impl 需要的另外的内存空间的大小。LoopQueue 显示了怎样使用 LoopQue_impl，解决内存安排问题的。从 79 行的模版参数中，我们看到， 除了缓冲区数据存放类型_Tp 的参数外，还有一个Alloc 类型。 这便是用于安排LoopQue_impl 内存空间使用的模版类。在 LoopQueue 的成员中，定义了LoopQue_impl 的一个引用 impl102 行。这个引用
14、便是指向使用Alloc 安排空间得来的 LoopQue_impl 的空间。Alloc 模版参数有一个缺省的定义值 LoopQue_allocate。从这个缺省的安排内存的类里，我们可以看到一个安排 LoopQue_impl 的实现样例，见 69 行：char *p = new charsizeof(LoopQue_impl) + LoopQue_impl:addsize(msize); return *(new (p) LoopQue_impl(msize);这里，先依据 msize 安排好了靠虑到了 datamsize的足够的内存，然后，再使用定位的 new 操作，将 LoopQue_imp
15、l 创立在这个内存区中。这样，LoopQue_impl 类就可以使用它其中的 _Tp data0 的成员。实际上，这个成员已经有 _Tp datamsize这样的空间了。这里，假设我们设计另外一个安排内存的类，例如，LoopQue_ShmAlloc。这个类是使用共享内存，并在其中建立 LoopQue_impl 类。这样我们就可以使用：LoopQue来创立一个可以在进程间共享而进展通讯的环形队列类了。至此，我们可以总结一下：环形队列的数据构造和根本操作都是相当简洁的。主要的操作就是 push 和 get。环形队列可能需要线程或者进程间共享操作。尤其是进程间的共享，使得内存安排成为了一个相对简洁的
16、问题。对于这个问题，我们将根底的数据构造定义为无指针和引用成员，适合于内存治理的类，然后又设计了一个代理的进展二次包装的类，将内存安排的功能作为模版可定制的参数。这里，我们设计并实现了环形队列的数据构造，并也为这个构造能够定制存放到共享内存设计好了方针策略。但下面的工作，将更富于挑战性：对于 push 的操作，需要操作前等待队列已经有了空间，也就是说队列没有满的状态。等到这个状态消灭了，才连续进展 push 的操作，否则，push 操作挂起。对于 get 的操作，需要操作前等待队列有了数据，也就是说队列不为空的状态。等到这个状态消灭了，才连续进展 get 的操作，否则，get 操作挂起。上面的
17、 push 操作/get 操作一般是不同的进程和线程。同时，也有可能有多个 push的操作和 get 操作的进程和线程。这些工作我们将在随后的设计中进展。且听下回分解。附件: LoopQue 的测试程序:cpp view plainc opy1.2. /* tst-loopque.cpp3. test program for class4. Author: ZhangTao5. Date: July 27, 20236. */7.12. int13. main(int argc, char *argv)14. 15.16.17.18.19.20.21.22.23.24.25.26.27.28.
18、29.30.31.32.33.34.35.36.37.38.39.40.41.42.43. intqsize = 0;if ( argc 1 )qsize = atol(argv1);if ( qsize 1 ) qsize = 5;xtl:LoopQuequeue(qsize);for ( int i = 0; i (qsize - 1); i+ ) queue.push(i);std:cout “Loop push:“ i “/n“;queue.check_push(1000);std:cout “Full:“ queue.full “ Size:“ queue.size “/n/n“;for ( int i = 0; i qsize; i+ )int val = queue.front;std:cout “Loop pop:“ val “/n“;queue.pop;std:cout “/nEmpty:“ queue.empty “ Size:“ queue.size “/n“;return 0;8. #include9. #include/ for function10. #11.include“xtl/LoopQue.h“