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

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

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

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

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