精易论坛

标题: 转载 多线程的那点儿事（之无锁链表） [打印本页]
作者: Cand    时间: 2012-6-27 11:26
标题: 转载 多线程的那点儿事（之无锁链表）
前面，为了使得写操作快速进行，我们定义了顺序锁。但是顺序锁有个缺点，那就是处理的数据不能是指针，否则可能会导致exception。那么有没有办法使得处理的数据包括指针呢？当然要是这个链表没有锁，那就更好了。
    针对这种无锁链表，我们可以初步分析一下，应该怎么设计呢？   
    （1）读操作没有锁，那么怎么判断读操作正在进行呢，只能靠标志位了；
    （2）写操作没有锁，那么读操作只能一个线程完成；
    （3）写操作中如果是添加，那么直接加在末尾即可；
    （4）写操作中如果是删除，那么应该先删除数据，然后等到当前没有操作访问删除数据时，释放内存，但是首节点不能删除。

    普通链表的结构为，
  1. typedef struct _LINK   
  2. {   
  3.     int data;   
  4.     struct _LINK* next;   
  5. }LINK;  
复制代码
假设此时有32个线程在访问链表，那么可以定义一个全局变量value，每一个bit表示一个thread，读操作怎么进行呢
  1. void read_process()   
  2. {   
  3.     int index = get_index_from_threadid(GetThreadId());   
  4.     InterLockedOr(&value, 1 << index);   
  5.     /* read operation */   
  6.     InterLockedAnd(&value, ~(1<< index));      
  7. }  
复制代码
那么，写操作怎么进行呢，
  1. void write_process_add(LINK* pHead, LINK* pLink)   
  2. {   
  3.     /* add link to the tail of list */   
  4. }   
  5.    
  6. void write_process_del(LINK* pHead, LINK* pLink)   
  7. {   
  8.     delete_link_from_list(pHead, pLink);   
  9.     while(1){   
  10.         if(0 == value)   
  11.             break;   
  12.          Sleep(100);   
  13.     }   
  14.    
  15.     free(pLink);   
  16. }  
复制代码
其中链表的删除操作为，
  1. [cpp] view plaincopyprint?/*  
  2. *  From:   
  3. *    ->   a  ->  b -> c -> d  
  4. *  
  5. *  To:  
  6. *        -----------------  
  7. *        |               V  
  8. *    ->  a        b  ->  c ->d   
  9. *                                 
  10. */  
复制代码
总结：     （1）这种无锁链表有很多局限：多读少写、注意使用原子操作、不能删除头结点、数据只能添加到尾部、注意删除顺序和方法、读线程个数有限制等等；
    （2）写操作在操作前需要等待所有的读操作，否则有可能发生异常；
    （3）写操作不能被多个线程使用；
（4）无锁链表应用范围有限，只是特殊情况下的一种方案而已。
作者: ㄣ负二代    时间: 2012-7-11 06:15
必须支持C#此板块！{:3_232:}



欢迎光临 精易论坛 (https://125.confly.eu.org/) Powered by Discuz! X3.4