按順序一致但不是靜態一致的執行示例

根據Maurice Herlihy和Nir Shavit（第3章）的多處理器編程技術，在併發程序正確性的情況下，順序一致性比靜態一致性更強。在3.4.1中也提到，有順序一致的執行不是靜態一致的。我不明白如何。有人可以投光或提供樣品執行嗎？按順序一致但不是靜態一致的執行示例

來源

2013-10-06 Trojosh

考慮一個queue (FIFO)你排隊和出隊的元素。

從this dissertation約併發，我讀取（第20頁）：

被允許在順序一致性模型和在靜止一致性模型不允許在圖2.1中示出的場景的一個例子。兩個進程共享併發隊列數據結構。第一個進程隊列x。在一些非重疊的後續間隔中，第二個進程排隊y。最後，第二個進程執行一個出列並接收y。這個例子是順序一致的，但是並不是靜止一致的，假設排隊操作之間的時間落在靜止時間間隔之外。

圖2.1：
T1: --- enq(x) --------------------------- 
T2: ------------- enq(y) ---- deq():y ---- 
該歷史被順序一致性允許的，可以是允許或靜止的一致性禁止任一，並且通過線性化一致性禁止的。

如果您假設兩個隊列之間的隊列是靜止的，那麼T2應該看到來自T1的變化，並且出列應該返回x。如果您假設兩個隊列之間沒有靜態間隔，那麼可以按照您的意願對兩個隊列進行重新排序，並且deq（）：y是一致的。

來源

2013-10-07 12:50:00 ewernli

以下執行是否可以是「靜態一致但不是順序一致」的示例？ T1： - enq（x）--------- enq（y）------------________________________________________________ T2：------- deq（y）--- ----------- | ---- deq（x）-_______________________________________________這種執行顯然不是順序一致的。但是，如果我們在** | **方便地採取靜態間隔，那麼我們可以重新排序T1的兩個enq（）s，並且它將靜態一致。 @ewernli，你認爲這個解釋有意義嗎？ – Trojosh

我認爲是這樣，基於我對靜止一致性的理解。但是這對我來說也是一種新的一致形式，我昨天已經知道了:) – ewernli

@ewernli是認爲順序一致性的原因：enq（y）deq（）：y enq（x）是一個可能的順序執行順序嗎？ I.E在程序順序中仍然有效。 – William

按順序一致但不是靜態一致的執行示例

回答

相關問題