使用Epoch-Based Reclamation(EBR,特定域回收的一种方法)修改 lazy-list

article/2025/8/27 12:40:15

如前文所说，lazy-list最大的隐患莫过于逻辑删除，而没有物理删除问题，因此EBR首先就把这个问题给他solve了。

一.EBR修改部分

int parse_delete(intset_l_t *set, val_t val) {node_l_t *pred, *curr;int result, validated, isVal;while(1) {//Initpred = set->head;curr = get_unmarked_ref(pred->next);//Unmark and lock each nodewhile (curr->val < val) {pred = curr;curr = get_unmarked_ref(curr->next);}LOCK(&pred->lock);LOCK(&curr->lock);
/*
* Mark Phase: 
* Start from the root set to find all memory block references, and then mark the referenced memory block (mark)
*///check its validated and curr->val whether equals valvalidated = parse_validate(pred, curr);isVal = val == curr->val;result = validated && isVal;//only meeting at same time, make pred->next = newnodeif (result) {curr->next = get_marked_ref(curr->next);pred->next = get_unmarked_ref(curr->next);}//UNLOCK curr and predUNLOCK(&curr->lock);UNLOCK(&pred->lock);
/*
* Sweep Phase:
* All memory blocks that are not marked are considered garbage and can be recycled
*///find memory blocks that are not marked, setting a mark bit to 1result = result && parse_find(curr,isVal);//wait until pred and curr meet the validate conditions, exit this loopif(validated){//free the elementfree(curr);return result;}}
}

二.前后性能比较

original:
在这里插入图片描述
unsafe:

原始版实现2个线程完成从1到10个读数，而不安全的版本是5个线程拿到50个作业，终端显示时间几乎一样。

与以前相比，现有性能具有以下优点。

首先，程序的效率大大提高，真正发挥多核CPU的优势，达到充分利用CPU的目的。然后，它可以防止阻塞并促进整个程序模型的建立。非常适合多个相同线程处理同一个资源的情况。并且，同步收集比以前快得多，也更灵活。

三.构建人工环境体现不安全性

前面都说了，改之后是不安全版本，那么不安全在哪呢？
counting时，单线程可能正确，但多线程错误
因为多线程操作只会看到它当前的线程情况，所以改变变量的顺序是不固定的。
这里用java多线程的方式来展现下结果

public class jthread {public static void main(String[] args) {//Test 3 people in multithread conditionWebTickets w = new WebTickets();Thread t = new Thread(w,"Alan");t.start();Thread t1 = new Thread(w,"Mike");t1.start();Thread t2 = new Thread(w,"Jay");t2.start();}}class WebTickets extends Thread{private int ticketNums = 99;// from ticket = 99 to 0, 3 people buy these ticketspublic void run(){while(true) {//when ticket<=0, stopif(ticketNums<=0) {break;}try {Thread.sleep(200);} catch (InterruptedException e) {e.printStackTrace();}//sout the consquenceSystem.out.println(Thread.currentThread().getName()+"-->"+ticketNums--);}}
}

在这里插入图片描述
如图，java编写的抢票小程序，最后无法停下，抢到0以下的票。

所以实现同步机制需要注意以下几点： 安全性高，性能低，多线程使用。高性能，低安全性，用于单线程。

不要同步线程安全类的所有方法，只同步那些会改变共享资源的方法。

class WebTickets implements Runnable{//create static keystatic Object str = "str"; //Random valueprivate int ticketNums = 99;// from ticket = 99 to 0, 3 people buy these tickets@Overridepublic void run(){while(true) {//when ticket<=0, stopsynchronized(str){ //use lockif(ticketNums<=0) {break;}try {Thread.sleep(200);//rest 0.2 seconds} catch (InterruptedException e) {e.printStackTrace();}System.out.println(Thread.currentThread().getName()+"-->"+ticketNums--);}}}
}