Posted on 2009-02-17 11:30
ZelluX 閱讀(631)
評(píng)論(0) 編輯 收藏 所屬分類:
System
今年的ASPLOS '09上zhou yuanyuan也有一篇關(guān)于如何concurrent program中發(fā)現(xiàn)隱藏的atomicity violation bugs的paper，里面提到了這篇paper
2008-11-30
OSDI '08上MSR發(fā)的paper，針對(duì)并發(fā)編程中難以發(fā)現(xiàn)的bug問(wèn)題。
paper的內(nèi)容主要分兩大塊。
一是如何在發(fā)現(xiàn)bug的時(shí)候記錄下線程的運(yùn)行先后(thread
interleaving)，途徑是在線程API和用戶程序多寫(xiě)一層wrapper
functions，這里還有一些其他的問(wèn)題，比如只記錄下了thread interleaving的話出現(xiàn)data race怎么解決等。
另外一塊內(nèi)容是如何遍歷出給定程序運(yùn)行后所能產(chǎn)生的結(jié)果的集合，加入這個(gè)能實(shí)現(xiàn)的話那就能把所有隱藏的bug都找出來(lái)了。但是這個(gè)搜索空間很大，是
指數(shù)級(jí)的，的一個(gè)結(jié)論就是：給定一個(gè)程序有n個(gè)的線程，所有線程共完成k條指令，那么c次占先調(diào)度后線程的排列情況數(shù)的復(fù)雜度是
的，所以在實(shí)現(xiàn)遍歷代碼的時(shí)候必須有效的降低k和c的值。