事務(wù)存儲結(jié)構(gòu)的實現(xiàn)

(2) 讀00地址(十六進(jìn)制地址)中的數(shù)據(jù)到寄存器r1中，00地址對應(yīng)數(shù)據(jù)塊的讀(R)標(biāo)志位置1表示此數(shù)據(jù)被讀。

(3) 將寄存器r2中數(shù)據(jù)(這里假設(shè)為56)存入c0地址中，由于c0地址中存在原始數(shù)據(jù)34，將c0地址和該原始數(shù)據(jù)一起根據(jù)LogBase中的日志入口地址存入日志中，并將LogPtr指針后移，指向用于存放下個數(shù)據(jù)的地址位，同時將c0地址對應(yīng)塊的寫(W)標(biāo)志位置1，代表一次寫操作的完成，其他的狀態(tài)不變。

(4) 讀取40地址中數(shù)據(jù)到寄存器r3中，然后r3中數(shù)據(jù)加1，并將執(zhí)行后的r3數(shù)據(jù)存回40地址中，該操作對40地址對應(yīng)塊執(zhí)行了一次讀操作和一次寫操作，將讀(R)和寫(W)標(biāo)志位置1，然后將原始40地址對應(yīng)塊中數(shù)據(jù)存入日志中，存入LogPtr指向的地址中，同時將LogPtr指針后移。

(5) 事務(wù)提交后狀態(tài)——將與本事務(wù)相關(guān)的各個數(shù)據(jù)塊對應(yīng)讀寫標(biāo)志位清0，將LogPtr置位到LogBase，TMcount置0。(本例僅針對單事務(wù)執(zhí)行，如果是嵌套事務(wù)的執(zhí)行，LogTM結(jié)構(gòu)會更加復(fù)雜，具體支持嵌套事務(wù)的LogTM實現(xiàn)，請參考[2])

(6) 事務(wù)回滾后狀態(tài)——事務(wù)在執(zhí)行或提交過程中如果出錯需要回滾，則將日志中記錄的原始數(shù)據(jù)按照地址映射關(guān)系重新加載到對應(yīng)cache數(shù)據(jù)塊中，同時將各個塊對應(yīng)讀寫標(biāo)志位清0，LogPtr重置并且TMcount置0。

圖 4 事務(wù)版本管理過程——成功提交和回滾

2.2 沖突管理(Contention Management)

LogTM采用積極的沖突管理模式，而沖突管理中的一個重要概念目錄，就是在內(nèi)存中開辟的一片用來記錄共享數(shù)據(jù)索引和相關(guān)狀態(tài)信息的區(qū)域，也稱為目錄表。此沖突管理以目錄為橋梁，通過目錄的分析和消息轉(zhuǎn)發(fā)機(jī)制來完成多處理機(jī)間的沖突檢測。具體的實現(xiàn)步驟概括起來為：①請求操作的處理機(jī)發(fā)出一致性請求到目錄；②目錄響應(yīng)請求并可能將請求轉(zhuǎn)發(fā)到其他一個或多個處理機(jī)上；③每個響應(yīng)請求的處理機(jī)檢查自身狀態(tài)看是否發(fā)生沖突；④每個響應(yīng)請求的處理機(jī)給出應(yīng)答信號，包括沖突應(yīng)答(nack)和非沖突應(yīng)答(ack)；⑤發(fā)出請求的處理機(jī)解決沖突。

事務(wù)發(fā)生沖突后的替換行為須依據(jù)目錄中有效的MOESI狀態(tài)(MOESI 狀態(tài)：Modified(M)，Owned(O)， Exclusive(E)，Shared(S) or Invalidate(I))而定。

下面結(jié)合圖5中的沖突檢測實例對沖突管理的具體行為進(jìn)行說明。

圖 5 LogTM沖突檢測實例

(1)事務(wù)開始——處理機(jī)P開始執(zhí)行事務(wù)，TMcount增1；此時僅目錄中存放的cache塊信息有效。

(2)處理機(jī)P向目錄請求數(shù)據(jù)信息——步驟①：P在自身的cache中找不到某數(shù)據(jù)，馬上發(fā)送獨占請求(GETX)到目錄。步驟②：目錄收到請求后根據(jù)相應(yīng)數(shù)據(jù)的索引找到“老”版本數(shù)據(jù)傳給處理機(jī)P，當(dāng)“老”版本數(shù)據(jù)達(dá)到P時，P將此數(shù)據(jù)更為“新”版本數(shù)據(jù)同時將本機(jī)此數(shù)據(jù)塊對應(yīng)讀/寫標(biāo)志位置1。步驟③：P接受數(shù)據(jù)完畢后，發(fā)送應(yīng)答信號給目錄表示已經(jīng)成功接受數(shù)據(jù)。與此同時目錄中的狀態(tài)信息為M@P(Modified by P)，表示此數(shù)據(jù)正在被處理機(jī)P更改。

(3)檢測到事務(wù)沖突——步驟①：處理機(jī)Q發(fā)出請求某共享數(shù)據(jù)的信號(GETS)給目錄。步驟②：由于目錄中此數(shù)據(jù)的狀態(tài)為M@P，目錄則根據(jù)請求轉(zhuǎn)發(fā)給處理機(jī)P。步驟③：P接受到請求后檢查自己的狀態(tài)，由于P中相應(yīng)數(shù)據(jù)塊的寫標(biāo)志位已置，表明P正在修改此數(shù)據(jù)，不能滿足Q的請求，發(fā)生沖突。這時處理機(jī)P直接發(fā)送沖突信號給Q，當(dāng)Q接受到?jīng)_突信號后進(jìn)行沖突處理。步驟④：處理機(jī)Q同時將沖突信號發(fā)送給目錄，表明此次請求失敗。

(4)事務(wù)溢出的處理——處理機(jī)P通知目錄要將修改后的數(shù)據(jù)存到內(nèi)存中(目前，內(nèi)存中存在的是對應(yīng)數(shù)據(jù)修改前的“臟”數(shù)據(jù))。步驟①：P發(fā)出PUTX請求給目錄。步驟②：目錄認(rèn)可后發(fā)送應(yīng)答信號給P，通知P可以發(fā)送。步驟③：P接收到此信號后將數(shù)據(jù)寫回內(nèi)存(WB_XACT)同時將溢出位置1(表明此數(shù)據(jù)已經(jīng)不在cache中)。這樣在寫回操作完成后，P中相關(guān)數(shù)據(jù)塊信息已置為無效，但是目錄中仍然保持著原先P持有數(shù)據(jù)時的狀態(tài)，內(nèi)存中對應(yīng)區(qū)域已為修改后的“干凈”數(shù)據(jù)，目錄中該數(shù)據(jù)相應(yīng)的狀態(tài)也由“老”變成了“新”，表明內(nèi)存中此數(shù)據(jù)已為更新后的數(shù)據(jù)。

(5)溢出數(shù)據(jù)的事務(wù)沖突檢測——步驟①：處理機(jī)Q重新發(fā)出請求數(shù)據(jù)信號給目錄，由于目錄中的狀態(tài)還沒有改變。步驟②：目錄根據(jù)當(dāng)前狀態(tài)再次將請求轉(zhuǎn)發(fā)給處理機(jī)P，而此時Q請求的數(shù)據(jù)塊已經(jīng)寫回內(nèi)存中去了，并不在P的cache中，P收到請求信號后檢查到自身的溢出位已經(jīng)置位，它認(rèn)為此數(shù)據(jù)可能由于某種原因不在cache中，但是仍然與它相關(guān)。比如：由于此數(shù)據(jù)塊大小大于cache規(guī)定塊大小而不能放下，但仍需操作。步驟③：P發(fā)出沖突信號(NACK)給Q，但是這個沖突并不是真正意義上的沖突，而是P假設(shè)的沖突。步驟④：Q收到?jīng)_突信號后處理沖突同時發(fā)送信號給目錄，表明此次請求再次失敗。

(6)目錄中數(shù)據(jù)狀態(tài)的懶惰(Lazy)更新——處理機(jī)P提交事務(wù)后將TMcount減1，將對應(yīng)cache塊的讀/寫標(biāo)志位和溢出標(biāo)志位清零，但此時目錄中的狀態(tài)仍然為M@P。步驟①：此時一旦處理機(jī)Q重新發(fā)出請求此數(shù)據(jù)信號。步驟②：該信號會再一次通過目錄轉(zhuǎn)發(fā)給處理機(jī)P，但此時P的溢出位已經(jīng)被清空。步驟③：P通過發(fā)送清除信息(CLEAN)給目錄通知目錄不必再轉(zhuǎn)發(fā)請求信息，目錄中的數(shù)據(jù)信息有效可以直接發(fā)送給請求的處理機(jī)Q。步驟④：目錄根據(jù)索引關(guān)系找到相關(guān)數(shù)據(jù)發(fā)送給處理機(jī)Q。步驟⑤：Q收到數(shù)據(jù)后進(jìn)行處理同時將應(yīng)答信號發(fā)送給目錄，表明請求成功同時將目錄對應(yīng)數(shù)據(jù)項狀態(tài)置E@Q，表示此時處理機(jī)Q獨占此數(shù)據(jù)資源。