并發(fā)數(shù)據(jù)結(jié)構(gòu)及其在動(dòng)態(tài)內(nèi)存管理中的應(yīng)用.pdf

1、隨著多核處理器越來(lái)越廣泛的應(yīng)用，軟件如何改變傳統(tǒng)的串行設(shè)計(jì)理念以適應(yīng)并發(fā)的挑戰(zhàn)正變得越來(lái)越緊迫。作為應(yīng)用程序基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)首當(dāng)其沖，如何在保證數(shù)據(jù)結(jié)構(gòu)正確性的同時(shí)提供更高的并發(fā)度和擴(kuò)展性成為研究人員關(guān)注的重點(diǎn)問(wèn)題。在這種情況下，無(wú)鎖數(shù)據(jù)結(jié)構(gòu)應(yīng)運(yùn)而生。無(wú)鎖數(shù)據(jù)結(jié)構(gòu)擺脫了鎖的限制，能夠避免優(yōu)先級(jí)反轉(zhuǎn)問(wèn)題并承受線(xiàn)程的隨機(jī)故障退出，提供了更高的并發(fā)度和更好的擴(kuò)展性。但是，無(wú)鎖數(shù)據(jù)結(jié)構(gòu)所要應(yīng)對(duì)的是由多核處理器引入的更多的并發(fā)線(xiàn)程，以及隨之而來(lái)的更

2、大數(shù)量的動(dòng)態(tài)內(nèi)存消耗和對(duì)運(yùn)行時(shí)動(dòng)態(tài)內(nèi)存分配器的更加頻繁的訪(fǎng)問(wèn)，容易在高并發(fā)情況下形成瓶頸。
　　本文從負(fù)載均衡的角度考察無(wú)鎖數(shù)據(jù)結(jié)構(gòu)相關(guān)的動(dòng)態(tài)內(nèi)存管理問(wèn)題，將其抽象成“逆向”負(fù)載均衡問(wèn)題，基于負(fù)載均衡的思想提出了兩種并發(fā)隊(duì)列并將這兩種隊(duì)列用作線(xiàn)程本地緩沖區(qū)構(gòu)建了兩種供無(wú)鎖數(shù)據(jù)結(jié)構(gòu)使用的內(nèi)存池，來(lái)解決無(wú)鎖數(shù)據(jù)結(jié)構(gòu)的動(dòng)態(tài)內(nèi)存管理問(wèn)題，具體工作如下：
　?、俜治隽瞬l(fā)數(shù)據(jù)結(jié)構(gòu)領(lǐng)域的歷史和現(xiàn)狀，對(duì)該領(lǐng)域的各種常用技術(shù)和結(jié)構(gòu)做了研究，

3、指出了各自相對(duì)的優(yōu)缺點(diǎn)和在多核時(shí)代面臨的挑戰(zhàn)。
　?、趯?duì)共享內(nèi)存多核處理器環(huán)境下的并發(fā)內(nèi)存管理做了總結(jié)，分析了該領(lǐng)域的幾種通用技術(shù)，指出了研究人員對(duì)于無(wú)鎖數(shù)據(jù)結(jié)構(gòu)動(dòng)態(tài)內(nèi)存管理問(wèn)題特殊性的忽略，提出了用內(nèi)存池解決無(wú)鎖數(shù)據(jù)結(jié)構(gòu)的動(dòng)態(tài)內(nèi)存管理問(wèn)題。
　?、劢榻B了負(fù)載均衡思想在計(jì)算機(jī)系統(tǒng)任務(wù)調(diào)度領(lǐng)域的應(yīng)用，分析了任務(wù)竊取和任務(wù)分擔(dān)這兩種常用的調(diào)度策略，研究了幾種任務(wù)竊取相關(guān)數(shù)據(jù)結(jié)構(gòu)的原理、設(shè)計(jì)和實(shí)現(xiàn)，并用負(fù)載均衡的思想將無(wú)鎖數(shù)據(jù)結(jié)構(gòu)

4、的動(dòng)態(tài)內(nèi)存管理問(wèn)題抽象為“逆向”均衡問(wèn)題，提出用負(fù)載均衡的方法解決該問(wèn)題。
　　④提出了兩種支持竊取和/或歸還操作的并發(fā)隊(duì)列，并在這兩種隊(duì)列的基礎(chǔ)上分別構(gòu)建了兩種供無(wú)鎖數(shù)據(jù)結(jié)構(gòu)使用的內(nèi)存池。這兩種內(nèi)存池可以在運(yùn)行時(shí)通過(guò)在線(xiàn)程本地緩沖區(qū)之間執(zhí)行竊取和/或歸還操作以實(shí)現(xiàn)內(nèi)存資源在各線(xiàn)程間的均勻分布，以改善無(wú)鎖數(shù)據(jù)結(jié)構(gòu)的性能。
　　⑤將本文提出的兩種內(nèi)存池和普通內(nèi)存池分別應(yīng)用于無(wú)鎖數(shù)據(jù)結(jié)構(gòu)，并對(duì)它們的性能作了詳細(xì)的測(cè)量和對(duì)比，證明