随想录（为什么循环队列具有先天的并行性）

【声明：版权所有，欢迎转载，请勿用于商业用途。  联系信箱：feixiaoxing @163.com】

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

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

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

#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <pthread.h>

struct QUEUE
{
	int* buffer;
	int count;
	int start;
	int end;
};

#define STATUS int
#define TRUE   1
#define FALSE  0

struct QUEUE* alloc_queue(int count)
{
	struct QUEUE* p_queue;

	if(0 == count)
	{
		goto error1;
	}

	p_queue = (struct QUEUE*)malloc(sizeof(struct QUEUE));
	if(NULL == p_queue)
	{
		goto error1;
	}
	memset(p_queue, 0, sizeof(struct QUEUE));
	p_queue->count = count;
	
	p_queue->buffer = (int*)malloc(sizeof(int)* count);
	if(NULL == p_queue->buffer)
	{
		goto error2;
	}

	memset(p_queue->buffer, 0, sizeof(int) * count);
	return p_queue;

error2:
	free(p_queue);

error1:
	return NULL;
}


STATUS add_data_into_queue(struct QUEUE* p_queue, int data)
{
	if(NULL == p_queue)
	{
		return FALSE;
	}

	if(p_queue->end == (p_queue->start + 1) % p_queue->count)
	{
		return FALSE;
	}

	p_queue->buffer[p_queue->start] = data;
	p_queue->start = (p_queue->start +  1) % p_queue->count;
	return TRUE;
}


STATUS get_data_from_queue(struct QUEUE* p_queue, int* p_data)
{
	if(NULL == p_queue || NULL == p_data)
	{
		return FALSE;
	}

	if(p_queue->start == p_queue->end)
	{
		return FALSE;
	}

	p_data[0] = p_queue->buffer[p_queue->end];
	p_queue->end = (p_queue->end + 1) % p_queue->count;
	return TRUE;
}


static void* set_func(void* args)
{
	int index = 1;

	if(NULL == args)
	{
		goto end;
	}

	while(1)
	{
		while(FALSE == add_data_into_queue((struct QUEUE*)args, index));
		printf("set data %d\n", index ++);
		sleep(1);
	}

end:
	return NULL;
}


static void* get_func(void* args)
{
	int data;

	if(NULL == args)
	{
		goto end;
	}

	while(1)
	{
		while(FALSE == get_data_from_queue((struct QUEUE*)args, &data));
		printf("find data %d\n", data);
		sleep(3);
	}

end:
	return NULL;
}


int main(int argc, char* argv[])
{
	pthread_t pid1, pid2;
	struct QUEUE* p_queue;

	p_queue = alloc_queue(10);
	if(NULL == p_queue)
	{
		goto end;
	}

	if(pthread_create(&pid1, NULL, set_func, p_queue))
	{
		goto end;
	}

	if(pthread_create(&pid2, NULL, get_func, p_queue))
	{
		goto end;
	}

	while(1)
	{
		sleep(0);
	}

end:
	return 1;
}