- 论坛徽章:
- 0
|
本帖最后由 doofy 于 2010-03-29 18:25 编辑
现在纠结于一些基本的问题，有经验的过来帮忙澄清：
双向循环链表作为全局的数据结构，设置head_index和tail_index, 一个线程作为生产者，插入一个元素后，head_index自增，一个线程作为消费者，从队列中取出一个元素处理，tail_index自增；
问题：
这种模型下，能不能采取无锁设计?
欢迎拍砖~
补充：
我词不达意，我写了个demo，看下我的代码就应该明白我的意思了，不过这里确实是没什么好锁的, 两个线程只是读对方的index，改自己的index， 都是隔壁那个i++;++i ；i = i+1 害的！- #include <stdlib.h>
- #include <stdio.h>
- #include <pthread.h>
- #include <string.h>
- #include <sys/types.h>
- #include <unistd.h>
- #define MAX_LEN 10
- #define OFF 0x0
- #define ON ~OFF
- #define unlikely(x) __builtin_expect(!!(x), 0)
- struct node {
- struct node *pre, *next;
- u_int32_t state;
- };
- struct _block {
- u_int32_t insert_index;
- u_int32_t remove_index;
- struct node list[MAX_LEN];
- } block;
- void init_list(struct node *list, int num)
- {
- int i;
- memset(list, 0, sizeof(*list) * num);
- for(i = 1; i < MAX_LEN - 1; i++) {
- list[i].next = &list[i+1];
- list[i].pre = &list[i-1];
- }
- list[0].next = &list[1];
- list[0].pre = &list[MAX_LEN - 1];
- list[MAX_LEN - 1].next = &list[0];
- list[MAX_LEN - 1].pre = &list[MAX_LEN - 2];
- }
- void * producer_func(void *param)
- {
- while(1) {
- if(block.insert_index == block.remove_index \
- && block.list[block.insert_index].state == ON) {
- continue;
- }
- block.list[block.insert_index].state = ON;
- if(unlikely(++block.insert_index == MAX_LEN))
- block.insert_index = 0;
- }
- }
- void * customer_func(void *param)
- {
- while(1) {
- if(block.insert_index == block.remove_index \
- && block.list[block.remove_index].state == OFF) {
- continue;
- }
- block.list[block.remove_index].state = OFF;
- if(unlikely(++block.remove_index == MAX_LEN))
- block.remove_index = 0;
- }
- }
- int main(void)
- {
- pthread_t tid1, tid2;
- block.insert_index = block.remove_index = 0;
- init_list(block.list, MAX_LEN);
- pthread_create(&tid1, NULL, customer_func, NULL);
- pthread_create(&tid2, NULL, producer_func, NULL);
- while(1)
- sleep(10);
- return 0;
- }
|
|
免费注册
发表于 2010-03-29 16:46
发表于 2010-03-29 16:53
我本来的意思就是一个定长数组用来组织双向循环链表，整个过程中不会添加、删除节点！
