資源描述：
《共享內(nèi)存中數(shù)據(jù)結(jié)構(gòu)淺析》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、共享內(nèi)存中數(shù)據(jù)結(jié)構(gòu)淺析增值業(yè)務(wù)部/林睿共享內(nèi)存以高速訪問特點，廣泛應(yīng)用于電信級系統(tǒng)中。我在此總結(jié)個人對共享內(nèi)存的使用心得，希望能對部分開發(fā)人員有所幫助。限于個人水平，本文中不準確之處也請大家見諒。程序為訪問共享內(nèi)存時，需將共享內(nèi)存地址空間映射程序的地址空間，不同程序或相同程序重啟后共享內(nèi)存映射的地址都各不同。所以在共享內(nèi)存中，通常以數(shù)組下標方式指示相關(guān)節(jié)點信息。共享內(nèi)存除為進程間通訊提供重要手段外，還常用來實現(xiàn)數(shù)據(jù)緩存匹配、數(shù)據(jù)快速檢索等功能。如何以數(shù)組方式構(gòu)造循環(huán)隊列、散列隊列、平衡二叉樹等數(shù)據(jù)結(jié)構(gòu)，下面
2、將做簡要介紹：1．循環(huán)隊列在共享內(nèi)存中，常采用該類型數(shù)據(jù)結(jié)構(gòu)構(gòu)造進程間通訊管道。structEnQueue{unsignedintuHead;//循環(huán)隊列頭節(jié)點數(shù)組下標unsignedintuTail;//循環(huán)隊列尾節(jié)點數(shù)組下標BodyaBody[QUEUESIZE];//隊列數(shù)據(jù)區(qū)域};循環(huán)隊列結(jié)構(gòu)中包括頭節(jié)點、尾節(jié)點和隊列數(shù)組三個部分。消費進程在隊列數(shù)組中從頭節(jié)點為下標開始讀取數(shù)據(jù)，讀取到以尾節(jié)點為下標時結(jié)束；而生產(chǎn)進程則在隊列數(shù)組中從尾節(jié)點為下標開始寫入數(shù)據(jù)，寫入到頭節(jié)點為下標結(jié)束。消費進程讀數(shù)據(jù)時，
3、頭節(jié)點值自增，生產(chǎn)進程寫數(shù)據(jù)時，尾節(jié)點值自增。隊列長度為QUEUESIZE，頭節(jié)點、尾節(jié)點若等于或超過該隊列長度，需要循環(huán)到數(shù)組頭，值置為0。?循環(huán)隊列示意圖1/10uHead==uTailluHead==uTaill示意圖1：空隊列uHeaduTail示意圖2：帶數(shù)據(jù)的隊列uTailuHead示意圖3：帶數(shù)據(jù)的隊列uTailuHead=uTail+1示意圖4：隊列滿uHead==uTaill示意圖5：初始化隊列?隊列初始化1）初始化數(shù)組隊列；2）uHead和uTail都置為0。?生產(chǎn)進程隊列操作流程2/1
4、0?消費進程隊列操作流程 0 ?線程安全性消費進程只更新頭節(jié)點，生產(chǎn)進程只更新尾節(jié)點，且數(shù)組中的任意節(jié)點在一個時刻內(nèi)只能是空節(jié)點或者是有效數(shù)據(jù)節(jié)點，兩類進程也不存在同時訪問相同節(jié)點的可能。所以若消費進程和生產(chǎn)進程都只有一個的情況下，該結(jié)構(gòu)是線程安全的，無需加互斥或信號量。2．散列隊列在共享內(nèi)存中，
5、常采用該類型數(shù)據(jù)結(jié)構(gòu)實現(xiàn)數(shù)據(jù)緩存及快速匹配。structHashQueue{unsignedintuFree;//空閑鏈表頭節(jié)點數(shù)組下標unsignedintuHead[HASHSIZE];//散列鏈表頭節(jié)點3/10數(shù)組下標unsignedintuHash[QUEUESIZE];//鏈表節(jié)點指向下一節(jié)點下標數(shù)組BodyaQueue[QUEUESIZE];//隊列數(shù)組};散列隊列結(jié)構(gòu)中包括空閑鏈表頭節(jié)點、散列鏈表頭節(jié)點數(shù)組、鏈表節(jié)點指向數(shù)組和隊列數(shù)組四個部分。其中散列值范圍為0－HASHSIZE，隊列數(shù)組長度
6、為QUEUESIZE，一般QUEUESIZE遠遠大于HASHSIZE。隊列數(shù)組主要存儲普通業(yè)務(wù)數(shù)據(jù)，鏈表節(jié)點指向數(shù)組存放在隊列數(shù)組中相同下標節(jié)點在鏈表中的下一節(jié)點下標。散列鏈表頭節(jié)點數(shù)組存在各個散列值的鏈表頭節(jié)點在隊列數(shù)組的下標。具體示意如下：uHash……72080475000000050000000……8040731727……uFree8052uHead……37723……在一個散列隊列中存在兩種類型鏈表隊列，其中一種為空閑節(jié)點鏈表隊列，由數(shù)據(jù)緩存進程從該隊列中獲取空閑節(jié)點，該隊列頭節(jié)點下標存放在uFre
7、e變量中；另一種為各散列值鏈表隊列，不同散列值分別構(gòu)建不同的鏈表隊列，各鏈表隊列頭節(jié)點下標存儲以散列值為下標的的uHead數(shù)組中。不論uFree、uHead數(shù)組節(jié)點或uHash數(shù)組節(jié)點值為QUEUESIZE，都表示沒有后續(xù)節(jié)點，如uFree＝QUEUESIZE，則表示散列隊列滿，沒有可分配空閑節(jié)點；如uHead[31]＝QUEUESIZE，則表示散列值為31隊列為空，沒有可匹配節(jié)點；如uHash[31]＝QUEUESIZE，則表示aQueue[31]的位于隊列尾，沒有后續(xù)節(jié)點。?散列隊列示意圖4/10空閑隊
8、列散列隊列01………………………HASHSIZE－1?隊列初始化1）初始化數(shù)組隊列；2）將所有節(jié)點都添加到空閑隊列中，即uFree置為0，uHash[i]=i+13）所有散列隊列都置為空，即將uHead數(shù)組中所有值都置為QUEUESIZE；?數(shù)據(jù)緩存進程隊列操作流程5/10開始判斷該散列鏈鏈表為空表是否為空鏈表不為空判斷該散列鏈表是否為空鏈表不為空計算散列值遍歷到該散列鏈表鏈表為空尾部新分配節(jié)點為鏈表互斥體或信號
