2011-03-14 28 views
1

我有一個有1024個地址的內存地址池。在程序中有16個線程運行,它們訪問這些內存位置,執行讀取或寫入操作。該程序的輸出是一系列四倍其DEFN是這樣設計一個報告資源衝突的數據結構

四Q1的形式:(線程沒有,存儲器地址,讀/寫,時間)

例如Q1 =(12578中,r ,2t),q2 =(16,578,w,6t)

我想設計一個程序,它將四重流作爲輸入,並報告如果超過2個線程嘗試訪問相同的內存資源時發生的所有衝突在5t秒的時間間隔內進行至少一次寫操作。

我有幾種解決方案,但我不確定他們是否是解決此問題的最佳解決方案。我正在從設計和數據結構的角度尋找解決方案。

回答

1

所以這裏的基本問題是碰撞檢測。我通常會尋找一種將元素添加到某種關聯集合中的解決方案。由於即將添加新元素,您需要能夠判斷集合是否已經包含類似的元素,表明發生了碰撞。在這裏你似乎需要一個允許重複元素的集合類型,比如STL multimap。 Quadraple(quadruple?)顯然是關聯集合中的值類型,關鍵字類型將包含確定兩個元素是否表示衝突(即內存地址和時間)所必需的數據。爲了使用像STL multimap這樣的標準關聯集合,你需要通過爲鍵類型定義運算符<來定義鍵的一些排序(我假設C++在這裏,你沒有指定)。您將衝突定義爲兩個元素,其中內存位置相同,時間值相差少於某個閾值量。密鑰類型的排序必須使得表示衝突的兩個密鑰在排序中等同出現。在<操作下等效表示爲< b爲假且b <一個是假的一樣,所以訂貨會由該運營商定義:

bool operator<(Key const& a, Key const& b) { 
    if (a.address == b.address) { 
     if (abs(a.time - b.time) < threshold) { 
      return false; 
     } 
     return a.time < b.time; 
    } 
    return a.address < b.address; 
} 

有這種設計的一個問題,由於事實上兩個密鑰在<下可能是等效的,而不相等。這意味着兩個不同但相似的四元組,即兩個相互碰撞的值將被存儲在集合中的相同密鑰下。你可以在一個輕鬆的使用排序

bool operator<(Key const& a, Key const& b) { 
    if (a.address == b.address) { 
     return a.time < b.time; 
    } 
    return a.address < b.address; 
} 

在此排序定義的簡單的定義,碰撞元素結尾相鄰的有序關聯容器(但在不同的密鑰),所以你能找到他們後處理步驟全部添加到集合後。