为什么循环队列具有先天的并行性

蔚落 2022-08-20 13:16 65阅读 0赞

循环队列是很多人喜欢用的一种数据结构。本着先来先服务的特性，循环队列是一种十分简单、健壮的数据结构。不像链表、二叉树，如果使用不慎，就会造成很大的麻烦，但是在循环队列上面则没有这个烦恼。

同样而言，循环队列具有很强的并行性，如果服务的数据比较少，那么完全可以利用两个线程进行数据的保存和处理工作。只要注意在编写队列的时候不要引入公共参数，那么几乎不会有任何的并行烦恼。这其中的原因就在于，循环队列没有公共变量，所以不存在对公共变量的修改问题。队列是否为空或者是否为满，完全可以由队列的start和end这两个参数决定，而这两个参数的修改是分开来的，不可能在一个线程上面解决，这就是队列并行的本质原因。

同学们可以自己编写一个简单的双线程代码，验证自己的想法，同时可以不断加深自己对多线程代码的分析和理解能力。下面就是一段在linux上编写的队列处理代码，欢迎大家多提宝贵意见。编译的方法十分简单，即gcc queue.c -g -o queue -lpthread，这里加上-g主要是为了调试使用。

**\[cpp\]**  [view plain][]  [copy][view plain]

1.  \#include <stdio.h>  
2.  \#include <malloc.h>  
3.  \#include <string.h>  
4.  \#include <pthread.h>  
5.    
6.  **struct** QUEUE  
7.  \{  
8.      **int**\* buffer;  
9.      **int** count;  
10.     **int** start;  
11.     **int** end;  
12. \};  
13.   
14. \#define STATUS int  
15. \#define TRUE   1  
16. \#define FALSE  0  
17.   
18. **struct** QUEUE\* alloc\_queue(**int** count)  
19. \{  
20.     **struct** QUEUE\* p\_queue;  
21.   
22.     **if**(0 == count)  
23.     \{  
24.         **goto** error1;  
25.     \}  
26.   
27.     p\_queue = (**struct** QUEUE\*)malloc(**sizeof**(**struct** QUEUE));  
28.     **if**(NULL == p\_queue)  
29.     \{  
30.         **goto** error1;  
31.     \}  
32.     memset(p\_queue, 0, **sizeof**(**struct** QUEUE));  
33.     p\_queue->count = count;  
34.       
35.     p\_queue->buffer = (**int**\*)malloc(**sizeof**(**int**)\* count);  
36.     **if**(NULL == p\_queue->buffer)  
37.     \{  
38.         **goto** error2;  
39.     \}  
40.   
41.     memset(p\_queue->buffer, 0, **sizeof**(**int**) \* count);  
42.     **return** p\_queue;  
43.   
44. error2:  
45.     free(p\_queue);  
46.   
47. error1:  
48.     **return** NULL;  
49. \}  
50.   
51.   
52. STATUS add\_data\_into\_queue(**struct** QUEUE\* p\_queue, **int** data)  
53. \{  
54.     **if**(NULL == p\_queue)  
55.     \{  
56.         **return** FALSE;  
57.     \}  
58.   
59.     **if**(p\_queue->end == (p\_queue->start + 1) % p\_queue->count)  
60.     \{  
61.         **return** FALSE;  
62.     \}  
63.   
64.     p\_queue->buffer\[p\_queue->start\] = data;  
65.     p\_queue->start = (p\_queue->start +  1) % p\_queue->count;  
66.     **return** TRUE;  
67. \}  
68.   
69.   
70. STATUS get\_data\_from\_queue(**struct** QUEUE\* p\_queue, **int**\* p\_data)  
71. \{  
72.     **if**(NULL == p\_queue || NULL == p\_data)  
73.     \{  
74.         **return** FALSE;  
75.     \}  
76.   
77.     **if**(p\_queue->start == p\_queue->end)  
78.     \{  
79.         **return** FALSE;  
80.     \}  
81.   
82.     p\_data\[0\] = p\_queue->buffer\[p\_queue->end\];  
83.     p\_queue->end = (p\_queue->end + 1) % p\_queue->count;  
84.     **return** TRUE;  
85. \}  
86.   
87.   
88. **static** **void**\* set\_func(**void**\* args)  
89. \{  
90.     **int** index = 1;  
91.   
92.     **if**(NULL == args)  
93.     \{  
94.         **goto** end;  
95.     \}  
96.   
97.     **while**(1)  
98.     \{  
99.         **while**(FALSE == add\_data\_into\_queue((**struct** QUEUE\*)args, index));  
100.         printf("set data %d\\n", index ++);  
101.         sleep(1);  
102.     \}  
103.   
104. end:  
105.     **return** NULL;  
106. \}  
107.   
108.   
109. **static** **void**\* get\_func(**void**\* args)  
110. \{  
111.     **int** data;  
112.   
113.     **if**(NULL == args)  
114.     \{  
115.         **goto** end;  
116.     \}  
117.   
118.     **while**(1)  
119.     \{  
120.         **while**(FALSE == get\_data\_from\_queue((**struct** QUEUE\*)args, &data));  
121.         printf("find data %d\\n", data);  
122.         sleep(3);  
123.     \}  
124.   
125. end:  
126.     **return** NULL;  
127. \}  
128.   
129.   
130. **int** main(**int** argc, **char**\* argv\[\])  
131. \{  
132.     pthread\_t pid1, pid2;  
133.     **struct** QUEUE\* p\_queue;  
134.   
135.     p\_queue = alloc\_queue(10);  
136.     **if**(NULL == p\_queue)  
137.     \{  
138.         **goto** end;  
139.     \}  
140.   
141.     **if**(pthread\_create(&pid1, NULL, set\_func, p\_queue))  
142.     \{  
143.         **goto** end;  
144.     \}  
145.   
146.     **if**(pthread\_create(&pid2, NULL, get\_func, p\_queue))  
147.     \{  
148.         **goto** end;  
149.     \}  
150.   
151.     **while**(1)  
152.     \{  
153.         sleep(0);  
154.     \}  
155.   
156. end:  
157.     **return** 1;  
158. \}  
159.

[view plain]: http://blog.csdn.net/feixiaoxing/article/details/7883714#