TW200305105A - Semaphore system based on process events - Google Patents

Description

(i) 200305105 ^、發明說明 (χ月况月應敘明··發明所屬之技術領域、先前技術、内容、實施方式及圖式簡單說

版權公告 W 此專利文件之揭示的一部分含有接受版權保護的事物。 者不反對由任一專利文件或專利揭示傳真複製成 $利與商標事務所的專利檔案或記錄，但是此外保留所 2任何版權。以下的公告適用於到此為止說明於下及圖 利的軟體與資料：版權觸丨’英特爾公司，保留所有權 技術領域 本發明大體上係關於平行程序，特 系統資源之存取的信號。 /、用的 先前技術 執行平行處理的系統包括同時執 之一普遍的問題係保護共用資源的内容。使用千仃處理 軟之：：知方式係使用，信號，其大體上係硬體或 變數。它用：：系統中’ ^號係指示共用資源的狀態之 對^ =1在使用的資源°—需要資源的程序核 R “判疋資源的狀態，然後決 其他潛在的使用者指示—㈣或其他資源正在使用中ΐ 防止由多於一的程序存取。 且 …、而田複數程序需要存取一共用資源時 =:/或死鎖的問題。叙餓發生在當防止一或 子/、用貝源時，而死鎖可能發生在當 相鎖定而停止執行時。 飞更夕耘序互 (2) 200305105 發喃說明續頁 義.....> ;-：>'；：iti.: ..^-^^v'i-.'r'：--"ϊ :%； /當有複數資源時，此更加複雜。解決此問題的古典方法

係實施-用於各資源的信號。然而，資源的數 ；I 此解決方案並不很有效。 風很大 發明内容 且本發明之—特點係—種用於管理共享系統資源之存取的 =公正性之信號系統。方法包括請求一資源，然後判定 。亥貝源是否正由其他程序請求，， ^ ^ 口亥貝源疋否由其他程序 鎖疋。如果它由其他程序請求，則 古 ^便口亥貝源^供至具有較 问優先権的程序。如果該資源由直 貝7田兵他私序鎖定，則不准許 该程序存取該資源。 古t!形與不同的實施例中，信號系統可能包括及使用一 :十時器7G件及一具有總體優先權方塊的總體仲裁器之任何 桊發明包含各種操作 十奴乃的裸作可以

體π件執行，或能以機器可執行的指令實施，财A ::用於促使一通用目的或特殊目的處理器或是以心: 式b的邏#電路執行操作。或者，操作可 的組合執行。 又股/、軟體 ^發明可以提供成為電腦程式產品，其可以包含哭 可讀的媒體’其上儲存可以用於將電腦（或其他電- 程式化以執行依據本發明的程序之指令。機器 可以包含（但不限於）軟碑 σ 貝、’、體 神、 ）軟碟7b碟、CD-R〇Ms(唯讀光碟記憔 體）、域光碟、R〇Ms(唯讀記憶體）、_(隨心 聰MS(可抹除可程式唯讀記憶體）、職s(電磁除 (3) (3)200305105 可程式唯讀記憶體）、磁卡哎弁風 田认妙+ + 下―飞光學卡、快閃記憶體、或適 用於儲存電子指令的其他型戎 主式的媒體/機器可讀媒體。 此外，本發明也可以下載成兔 軟战為電腦程式產品，其中程式 可以藉由載體波或其他傳播^每 爾铄體灵施的貧料信號，經由通 訊鏈接（例如，數據機或網路連接），自遠方電腦（例如，祠 服器）傳送至提出請求的電腦（例如，用戶）。因此，在此處， 載體波將視為包括機器可讀媒體。 實施方式 圖1緣示一系統100,其中可以實施本發明的實施例。它 包括至少一（CPU)中央處理單元102(只顯示其一）、至少一記 憶體104(只顯示其一）、及一匯流排1〇6，中央處理單元觀 與記憶體104經由匯流排106互相作用。記憶體1〇4包括複數 資源108(只顯示其一）及複數信號11〇(只顯示其一），且中央 處理單元102包括複數程序ιΐ2(只顯示其一）。 圖2繪示一先前技術系統200，其能夠在圖1的系統丨⑻中 實施。在系統200中，中央處理單元1〇2包括複數程序2〇2、 204、206及複數資源208、210、212、214，其中各資源208、 210、212、214 具有一對應的信號 216、218、220、222，用於 管理資源208、210、212、214之共享的存取。或者，各資源 208、210、212、214可以對應於由單一信號物件224代表之 信號216、218、220、222的信號功能，而非分離的信號物件 216 、 218 、 220 、 222 。 在先前技術實施例中，當第一程序202、204、206想要存 取資源 208、210、212、214 時，第一程序 202、204、206 藉由 200305105 (4) ---- 發明說明續頁 透過系統匯流排106送出讀取命令至資源2〇8、21〇、212、214 之對應信號216、218、220、222，以核對所欲的資源2〇8、21〇、 212、214之狀態。如果所欲的資源2〇8、21〇、2ΐ2、η*係可 用，則第一程序202、204、206送出寫入命令至對應信號216、 218、220、222，以將信號216、218、22〇、222的狀態自未鎖 定改為鎖定。 在本發明的實施例中說明一系統，其中信號關聯於—程 序而非一諸。當一信號鎖㈣，它指示一特定資源不可 用於L號的對應权序。當信號未鎖定時，它指示它的對應 程序目前未使用任何資源。 信號可以由於一或更多肖它的對應程序關聯t事件的發 生而改變。n系統偵測這些事件的發纟，且控制信號 的狀態。在一實施例中，信號系統係自含式，其中一第一 l 5虎系統藉由與-代表第二程序參加仲裁的第二信號通訊 而：表第一程序芩加仲裁。纟另一實施例中，信號系統仲 裁匕們的個另"王序，但是依賴一用於衝突仲裁處理的總體 仲裁器。進一步說明這些實施例如下。 自含式信號 在本發明之一實施例中，如圖3的系統3〇〇所示，中央處 理單元102包括複數程序302、綱、3〇6,且記憶體刚包括 设數資源綱、31〇、312、314及信號系統316、318、32〇。在 系、、先300中，各程序3〇2、3〇4、3〇6具有—對應的信號系統316、 训、320」用於管理資源期、⑽、312、训之共享的存取。 或者，單一信號系統324可以由所有程序共享。 200305105 (5) 發明說明續頁 在以下的說明中，程序302、304、信號系統316、318與資 源308的繪示係說明二程序及它們的用於一已知資源308之 對應信號糸統的仲裁程序。然而，一般專精於此技術的人 了解，該說明適用於程序306、信號系統320、資源310、312、 314及可能界定但是此處未緣示或討論的任何其他程序、 信號系統與資源。 包括區域優先權方塊的信號 圖4繪示具有對應的信號系統316、318之程序302、304。 各信號系統316、318包括一指示資源之可用與不可用的信 號400、及一嘔域仲裁器402，區域仲裁器402藉由監視它的 對應程序302、304之事件以判定信號4〇〇的狀態，代表它的 對應程序302、304仲裁一已知資源308的存取。 在一實施例中，一信號系統316、318可以額外包括一區 域優先權方塊404 ’其對於它的對應程序302、304具有固定 優先權。指定一固定優先權予各程序3〇2、3〇4，使第一程 序具有比第二程序更高或更低的優先權。如果多於一的程 序302、304請求相同的資源3〇8，則區域仲裁器4〇2藉由將資 源308提供至具有較高優先權的程序3〇2、3〇4而解決衝突。 例如’如果程序P1的優先權=1且程序p2的優先權=2，其中 1係比2南的優先權，如果程序ρι與p2同時請求一已知資源 R，則區域仲裁器402准許程序P1存取資源R，因為ρι具有 比P2高的優先權。 圖5繪示上述實施例的方法。它開始於方塊5⑻，且繼續 進行至方塊5〇2，在該處判定程序ρι與程序p2之間對於資源 (6) 200305105 Λ * s 、 發明說明續頁 R是否有衝突（即，P1的請求I D·是否等於p2的請求I D. ?)。 如果有衝突，則在方塊504判定P1的區域優先權是否大於？2 的區域優先權。如果P1的區域優先權大於p2的區域優先 權，則在方塊508准許P1存取。否則，在方塊512拒絕pl存 取。

如果/又有衝突，則在方塊5〇6判定資源R是否由p2鎖定 (胃即，如果P1的請求LD·不等於P2的請求LD.，mpi的請求LD. 疋否等於P2之目前鎖定的I D· ?)，及在方塊51〇判定p2是否 已釋放匕對於R的鎖定。如果R由p2鎖定，且已釋放它 2於R的鎖定，則在方塊5〇8准許ρι存取資源&。如果r係鎖 疋且P2尚未釋放它對於尺的鎖定，則在方塊5丨2拒絕η存取 女果/又有衝大，且資源R未由p2鎖定，則在方塊5〇8准 許P1存取資源R。方法結束於方塊514。

包括區域仲裁器加上計時器元件的信號 。在又-實施例中，如圖6所示，信號系統316、318可包一 區或仲裁夯402 ’加上一計時器元件_。、各信號系統316 π 乂匕括如上述的區域優先權方塊404及一計時器 件6〇0；、計時器元件_追縱它的對應程序302、304已等待 已知貝源308而未鎖定它的信號之時間。 ^ 只施例中，5十時器600純粹基於時間，它計算自； 鎖定以來已經過的時脈循環數目。在另-實施例中 5卞h器600係計數器，复刻 ，、爿疋那些其他程序已獲准存取: 中 ；序正在請求者相同的共享資源。在後-實施> 。^ _在每t另_程序獲准存取時增量，且當 -11 - 200305105 本身的程序獲准存取時重置（例如，重置為 在此實施例中’如果第一程序已比第二程序等待更久， 則區域仲裁器402准許第一## 、 认知产 罘私序存取。例如，如果優先權 的私序P1已比優先權=2的程序p2等待 、鱼π w — ❹序P24#更久’則區域仲裁器 WP1存取。如果程序P2已比第：程糾等待更 =，則區域仲裁器准許第二程序P2存取。如果二程序已等 ^目同的時間’則區域仲裁器衫何程序具有較高的優先 崔’且准許具有較高的優先權之程序存取。在此狀況，立 係程序P1。 八 :闡釋此實施例的方法繪示於圖7的流程圖。用於程序P1 的信⑽統之方法開始於方塊·，絲續進行至方塊观， =該處它判定程序P1與程序P2之間對於f源以否有衝 犬如果有衝犬，則它在方塊704判定P1與P2是否已等待相 同的時間。如果無衝突，則它在方塊寫判定資源是否由 程序P2鎖定。 如果有衝犬，且P1與P2已等待相同的時間，貝^它在方塊 712判定P1的區域優先權是否大㈣的區域優先權。如果ρι 的區域優先權大於P2的區域優先權，則在方塊714准許？1存 取。否則，在方塊716拒絕P1存取。 如果有衝突，且^與！^尚未等待相同的時間，則它在方 塊708判定P1等待資源尺是否比p2更久。如果ρι等待資源尺 比P2更久，則在方塊714准許P1存取資源尺。否則，在方塊716 拒絕P1存取資源R。 如果無衝突，則它在方塊706判定資源以是否由P2鎖定， -12- (8) (8)200305105 發f說明續頁 2方塊™判定Ρ2是否已釋放它對於R的鎖定。如果 m>2已釋放它對於R的鎖定，則在方塊7i4准許㈣ 取貧源R。如果R係鎖定，且P2尚未釋放它對於尺的鎖定， 則在方塊7i6拒絕？1存取資源R。如果無衝突，1資源 ㈣敎，則在方塊714准許ρι存取f❹。方法結束於方 塊 718。 ΑΑϋ體仲裁器的率絲 在本發明的另一實施例中，如圖8所示，系統_包括一 中央處理單元及一記憶體，中央處理單元具有複數程序 302、304、306，記憶體包括複數資源3〇8、31〇、312、314及 複數程序302、304、廳。在系統300中，各程序3〇2、綱、3〇6 具有一對應的信號系統316、318、32〇，用於管理資源3〇8、 310、312、314之共享的存取。或者，單一信號系統324可 以由所有私序共享。此外，系統8〇〇包括一用於解決衝突 的總體仲裁器802。 在以下的說明中，處理器302、3〇4、信號系統316、318 與資源308的繪示係說明用於二程序的仲裁程序及它們的 用於一已知資源308之對應信號系統。然而，一般專精於 此技術的人了解，該說明適用於程序3〇6、信號系統32〇、 貧源310、312、314及可能界定但是此處未繪示或討論的任 何其他程序、信號系統與資源。 如圖9所示，總體仲裁器8〇2可能包括一具有登錄9〇2、 904、906、908、910、912、914、916 的佇列 900 (此後稱為「總 體優先權佇列」），其中各登錄對應於一優先權，且各登 -13 - (9) 200305105

L j值唯#私序（或者’各登錄可以對應於唯—的程 〜且登錄值指示該程序的優先權)。起初，將 二二仔？之具有優先權值的登錄(其中登錄值係程 2^')。U許各程序存取―資源時，它移動 的底°卩，俾使它具有最低優先權。 =編觀可能包括一用於所有資源的仔列，俾使 二有程序P2而獲准存取的第—程序P1接著具有對於 而言比P2低的優先權’或者，總體仲裁器_ 二括讀㈣，各㈣對應ϋ源，俾使優先 ==Γ的第一程序P1接著具有對於已知資源二 曰比P2低的優先權。 般專精 為了闡釋，討論二實例中的後一實例。然而 於此技術的人必須了解’任一實例係可行的。 只包括區域仲裁器的信號 在一實施例中，如圖10所示，信號系統3i6、318可以勺 =區域仲裁器402，且指定一在總體仲裁器8〇2之總體優：

^宁列_中的初始優先權予各程序3〇2、綱。當程序 存取資源308時，排行改變。 X 用於第一程序的區域仲裁器402與用於第二程序的區超 :裁器術通訊’以判定是否有衝突。如果有衝 ： 體仲裁器鶴由提供資料具有較高總體優㈣ 的總體優先權佇列900判定—的程序，而解決衝突。例如y 如果程序P1具有在總體優先㈣列中比程序？2高的 權’如果料PmP2同”求1知„、R，則總 -14- 200305105 (ίο) 發明說明讀頁 器准許P1存取資源R。 一例繪示於圖11，其中五（5)程序P1、P2、P3、柯與朽在 各種場合競爭一已知資源R1。假設總體優先權佇列初始 化，俾使P1具有最高優先權，且P5起初具有最低優先權（步 驟1)。在步驟2，P1與P2同時競爭幻。因為ρι具有比打高^ 優先權，所以P1獲准存取，且在步驟3移動至佇列的底部。

在步驟4, P4與P5競爭R1。因為P4具有比p5高的優先權， 所以P4獲准存取，且在步驟5移動至佇列的底部。在步驟6， P1與P4競爭R1。因為P1具有比p4高的優先權，所以ρι獲准 存取，且在步驟7移動至佇列的底部。在步驟8，^與ρι競 爭R1。因為P2具有比pi高的優先權，所以p2獲准存取，且 移動至佇列的底部。依此方式，顯然達成公正性，因為尚 未獲准存取R1的程序具有比已獲准存取的程序更高的優先 權0 以上討論的方法繪示於圖12的流程圖。用於程序ρι之信 號系統的方法開始於方塊12〇〇，且繼續進行至方塊12〇2， 在該處’它判定程序P1與程序P2之間對於資源R是否有衝 突。如果有衝突，則它在方塊12〇4判定pi的總體優先權是 否大於P2的總體優先權。如果ρι的總體優先權大於p2的總 體優先權’則在方塊1208准許P1存取。否則，在方塊1212 拒絕P1存取。 如果沒有衝突，則在方塊丨2〇6判定資源r是否由p2鎖定， 及在方塊1210判定P2是否已釋放它對於r的鎖定。如果r由 P2鎖定’且P2已釋放它對於R的鎖定，則在方塊12〇8准許pl -15- (11) 200305105 發輸胡續頁 、圬纖::翻海怒制!敗，：屮:::.·工 存取資源R。如果R係鎖定且P2尚未釋放它對於尺的鎖定， 則在方塊1212拒絕P1存取R。如果沒有衝突，且資源R未由 P2鎖定，則在方塊准許？1存取資μ。方法結束於方塊 1214。 包括區域仲裁器與計時器元件的信號 在另一實施例中，如圖13所示，信號系統:、318可包 括區域仲裁器402及-計時器元件_，計時器元件6()()追縱 它的對應程序已等待-已知t源而未鎖定之時間，如前 述。此外，各程序獲得總體仲裁器的總體優先權仔列_ 中之一登錄 當複數程序請求相„料，複數程序之第—程序_ 區域仲裁器4〇2解決P1與複數程序之第二程序P2之間的衝突 如下，其中Pi具有比P2高的優先權： •區域仲裁器402將准許已等待妒々 κ 士 判定—的程序存取；"已4待較久-由計時器元件_ 裁二果二？已等待相同的時間，則仲裁卸載予總體仲 裁m7 8 02，以解決衝突。 -旦仲裁已卸载予總體仲裁 總體優先權佇列900,以判…产』仲裁罐諮詢 ^ , 判疋二程序302、304中之何裎庠呈 有較高優先權。缺接⑽μ 7私序具

., …、灸，〜體仲裁器802准許具有較古# I 權的程序302、304存取。 L、有季乂阿優先 圖14繪示此程序。 士 a 用於私序P1之信號系統的方法門払认 方塊U00，且繼續進杆 開始於

,. 丁至方塊1402 ’在該處判定裎庑A 程序P2之間對於資源 ^序Π與 φ有衝犬。如果有衝突，則在方 -16- (12) (12)200305105 锋明鼻明續頁 塊1404判定Ρ1與Ρ2是否已等待相同的時間。如果沒有衝突， 則在方塊1406判定資源是否由Ρ2鎖定。 如果有衝突，且^與打已等待相同的時間，則它在方塊 1412判定Ρ1的總體優先權是否大於打的總體優先權。如果ρι 的總體優先權大於P2的總體優先權，則在方塊1414准許ρι 存取。否則，在方塊1416拒絕P1存取。 如果有衝突，且？1與！>2尚未等待相同的時間，則它在方 塊H08判定P1等待資源&是否比p2更久。如果ρι等待資源& 比P2更久，則在方塊1414准許P1存取資源汉。否則，在方塊 1416拒絕P1存取資源R。 如果沒有衝突，則在方塊1406判定資源尺是否由p2鎖定， 及在方塊1410判定P2是否已釋放它對於R的鎖定。如果r由 P2鎖定’且P2已釋放它對純的鎖定，則在方塊⑷4准許^ 存取資源R。如果R係鎖定且？2尚未釋放它對於尺的鎖定， 則在方塊14i6拒絕P1存取R。如果沒有衝突，且資源&未由 P2鎖定’則在方塊1414准許ρι存取資源尺。方法結束於方塊 1418 〇 圖15係用於實施本發明的實施例所述之區域仲裁器4〇2 的^本電路圖。元件1500與15〇2繪示用於判定是否有°任何 ，突存在的電路。元件15〇〇判定第一程序ρι與帛二程序Η 疋否正在晴求相同的資源R ’而元件漬判定程序ρι是否 :在請求P2已鎖定的資源。元件15〇4自總體優先權方塊接 ，以判定何程序具有較高優先權，巾元件1506自計 時器元件接受輸入，以判定何程序等待較久。 -17- 200305105 (13) 發明説明續頁. 例如，對於與程序P1對應的區域仲裁器402而言，如果 下列事項成立，則將准許存取資源R : • P1未請求與P2相同的資源，且P1未請求P2已鎖定的資 源。此係由圖15的電路代表如下： 如果元件1532係TRUE，則准許P1存取R。如果元件1532係 FALSE，則拒絕P1存取R。如果二元件1508與1530係TRUE， 則元件1532係TRUE。 如果P1與P2未請求相同的資源，則元件1508產生TRUE信 號。於是，如果P1的請求識別器不等於P2的請求識別器， 則在元件1508產生TRUE信號。 如果元件1526與1528二者皆產生FALSE信號，則元件1530 產生TRUE信號。如果元件1512或1514產生FALSE信號，則元 件1528產生FALSE信號。於是，例如，如果P1未請求P2已鎖 定的資源，則元件1512產生FALSE信號。類似地，如果元 件1510或1524產生FALSE信號，貝元件1526產生FALSE信號。 例如，如果P1未請求與P2所請求者相同的資源，則元件1510 產生FALSE信號-另言之，此產生元件1508的相反信號。 • P1未請求與P2相同的資源，P1請求P2已鎖定的資源， 但是P2釋放該鎖定。此由電路表示如下： 如果元件1532係TRUE，則准許P1存取R。如果元件1532係 FALSE，則拒絕P1存取R。如果元件1508與1530二者係TRUE， 則元件1532係TRUE。 如果P1與P2未請求相同的資源，則元件1508產生TRUE信 號。於是，如果P1的請求識別器不等於P2的請求識別器， 200305105 (14) I發明說明續頁 則在元件1508產生TRUE信號。 如果元件1512或1514產生FALSE信號，則元件1528產生 FALSE信號。於是，例如，如果元件1512產生TRUE信號（因 為P1請求P2已鎖定的資源），貝|丨元件1514必須產生FALSE信 號。如果P2釋放它的目前鎖定的識別器，則此發生。類似 地，如果元件1510或1524產生FALSE信號，則元件1526產生 FALSE信號。例如，如果P1未請求與P2相同的資源，則元 件1510產生FALSE信號-另言之，此產生元件1508之相反的 信號。 • P1請求與P2相同的資源，P1未請求P2已鎖定的資源（或 如果P1已請求P2已鎖定的資源，則P2已釋放該鎖定），且P1 已等待該資源比P2久。此由圖15的電路表示如下： 如果元件1530係TRUE，則准許P1存取R。如果元件1530係 FALSE，則拒絕P1存取R。如果元件1526與1528二者係FALSE， 則元件1530係TRUE。 如果元件1512或1514產生FALSE信號，則元件1528產生 FALSE信號。於是，例如，如果P1未請求P2已鎖定的資源， 則元件1512產生FALSE信號。而且，如果元件1512產生TRUE 信號（因為P1請求P2已鎖定的資源），則元件1514必須產生 FALSE信號。如果P2釋放它的目前鎖定的識別器，則此發 生。 因為如果P1已請求與P2相同的資源則元件1510產生TRUE 信號，所以元件1526在下列狀況產生FALSE信號。P1與P2尚 未等待相同的時間，促使元件1518產生FALSE信號，所以促 200305105 (15) 發明說明續頁 使元件1520產生FALSE信號。因為P2尚未等待比P1久，所以 元件1522產生FALSE信號。結果，元件1524產生FALSE信號， 且元件1526產生FALSE信號。結果，元件1530產生TRUE信號， 且准許P1存取R。 • P1請求與P2相同的資源，P1未請求P2已鎖定的資源（或 如果P 1已請求P2已鎖定的資源，則P2已釋放該鎖定），P1 已等待該資源與P2 —樣久，且P1的總體優先權大於P2的總 體優先權。此由圖15的電路表示如下： 如果元件1530係TRUE，則准許P1存取R。如果元件1530係 FALSE，則拒絕P1存取R。如果元件1526與1528二者係FALSE， 則元件1530係TRUE。 如果元件1512或1514產生FALSE信號，則元件1528產生 FALSE信號。於是，例如，如果P1未請求P2已鎖定的資源， 則元件1512產生FALSE信號。而且，如果元件1512產生TRUE 信號（因為P1請求P2已鎖定的資源），則元件1514必須產生 FALSE信號。如果P2釋放它的目前鎖定的識別器，則此發 生。 因為如果P1已請求與P2相同的資源則元件1510產生TRUE 信號，所以元件1526只有在元件1524產生FALSE信號時才產 生FALSE信號。P1與P2已等待相同的時間，促使元件1518產 生TRUE信號。因為元件1518係TRUE，所以元件1522必須係 FALSE。P2不具有比P1高的優先權，所以元件1516係FALSE 促使元件1520係FALSE。此促使元件1524係FALSE，元件1526 亦然。結果，元件1530產生TRUE信號，且准許P1存取R。 (16) (16)200305105 結論 於是，已針對一根播和& ^ _ RR ^ &序事件而非資源事件的作f卢系访 而巩明本發明。在一竇 t W 1。說糸統 ^4¾ 〇 . ^ ^ 、，，耘序事件係簡單的固定優 先權。 事牛係根據公正性的動態優 在前述說明中，已參考牯 亏特疋Μ施例而說明本發明。然而， …貝，、、>，可以進行各種修改盥 的拌站4 - * 一汉、，扁不會偏離本發明之寬廣 的精神和範疇。因此，筇 「、 "月曰/、圖式係闡釋性而非限制性。 圖式簡單說明 在附屬圖式的圖中舉例絡 牛巧、、、曰不本發明而不加以限制，圖中 相同的參考號碼標示類似的元件，其中： 圖1係繪示依據本發明的—般實施例之系統架構的方塊 圖〇 圖2係繪示一使用信號的先前技術系統之方塊圖。 圖係、”曰示系統之方塊圖，該系統具有依據本發明的 實施例之自含式信號系統。 圖4係緣示在本發明之_實施例中的自含式信號系統之 方塊圖。 圖5係繪示使用圖4的自含式信號系統之方法的流程圖。 圖6係繪示在本發明另一實施例中的具有一計時器元件 的自含式信號系統之方塊圖。 圖7係繪示使用圖6的自含式信號系統之方法的流程圖。 圖8係繪不一系統之方塊圖，該系統具有依據本發明的 κ方也例之與一總體仲裁器互相作用的信號系統。 -21 - (17) (17)200305105 圖9係繪示圖8的總體仲裁器之總體優先權佇列的方塊 圖0 圖ίο係繪示-信號系統之方塊圖，該系統與—依據本發 明的實施例之總體仲裁器互相作用。 圖11係圖8的總體仲裁器之總體優先權佇列如何操作的 樣本流程圖。 圖12係繪示用於圖1〇的信號系統之方法的流程圖。 圖13係繪示一信號系統之方塊圖，該系統具有_ 叶日守器 元件，且與本發明的實施例之總體仲裁器互相作用。 圖14係繪示用於圖13的信號系統之方法的流程圖。 圖15係方塊圖，繪示一用於依據本發明的一般實施例 信號系統之樣本邏輯電路。 <圖式代表符號說明> 100，300，800 系統 102 中央處理單元 104 記憶體 106 匯流排 108，208、210、212、214，308、 資源 310、312、314，R1 110，216、218、220、222，400 信號 112，202、204、206、302、304、 程序 306、PI、P2、P3、P4與P5 200 先前技術系統 224 信號物件 -22- 200305105 (18) 316、318、320、324 402 404 600 802 900 902、904、906、908、910、912、 914 、 916 1500 、 1502 、 1504 、 1506 、 1508 、 1510 、 1512 、 1514 、 1516 、 1518 、 1520、1524、1526、1528、1530、1532 發明說明續頁 信號系統 區域仲裁器 . 區域優先權方塊 計時器元件 總體仲裁器 總體優先權彳宁列 登錄 - 元件

-23-

Claims (1)

1. 200305105 拾、申請專利範圍 1. 一種方法，包括·· 一程序請求存取一共享 為具有第一區域優先權的第 資源； 該第二程〇 =以正在_請求絲料享資源， 担序具有弟二區域優先權；及 如果该第二程序正在同時請求 耸古方结 ％必，、予貝源，則；隹 〇 一俊先權與該第二優先權中之且有浐古厂A 權者存取。 之八有較间區域優先 2_如申凊專^彳範圍第1項之方法，1由 各第-與第二優先㈣中錢域優先權對於 3· 專利範圍第旧之方法，其中額外包括如果該第 -各：未同時請求存取該共享資源，則： 判疋该第二程序是否目前鎖定該共享資源； ★a果4第二程序目前鎖定該共享資源，則拒絕該第一 序存取該共享資源；及 果，亥第—私序未鎖定該共享:身源，則准許該第一程 序存取該共享資源。 4_ 一種方法，包括·· &為一具有第一區域優先權及第一等待時間的第一程序 請求存取一共享資源； 上=疋一第二程序是否正在同時請求存取該共享資源， 第一私序具有第二區域優先權及第二等待時間； 如果泫第二程序正在同時請求存取該共享資源，則准 200305105 許該第一優先權與該第 間者存取；及

   二優先權中之具有較長的等待時 第一優先權與該第二優 存取。 具有較高區域優先權者 5. 如申請專利範圍第4項之方法，其中該區域優先權對於 各第一與第二優先權而言係固定。 、 6. 如申請專利範圍第4項之方法，其中額外包括如果該第 二程序未同時請求存取該共享資源，則： 判定該结二程序是否目前鎖定該共享資源； 如果該第二程序目前鎖定該共享資源，則拒絕該第一 程序存取該共享資源；及 如果4第一程序未鎖定該共享資源，則准許該第-裎 序存取該共享資源。 7· —種方法，包括： 為具有在一總體仲裁器的總體優先權佇列之第一總 體優先權的第-程序請求存取-共享資源； 判定一第二程序是否正在同時請求存取該共享資源， 邊第二程序具有在該總體仲裁器的總體優先權仔列之第 一總體優先權；及 如果該第二程序正扃π全 在冋時睛求存取該共享資源，則准 口干5亥第一優先權盘古女楚- 權者存取。 〃 ^第一俊先權中之具有較高總體優先 8.如申請專利範圍第7 、 方法’其中該總體優先權仔列 200305105 且各總 係該總體仲裁器的複數個總體優先權佇列之 體優先權佇列對應於一已知的共享資源。 9.如申請專利範圍第7項之方法，其中額外包括如果該第 二程序未同時請求存取該共享資源，則： 判定該第二程序是否目前鎖定該共享資源； 如果該第二程序目前鎖定該共享資源，則拒絕該第一 程序存取該共享資源；及 如果該第二程序未鎖定該共享資源，則准許該第一程 序存取該共享資源。 10· —種方法，包括： 為一具有在總體仲裁器的總體優先權佇列之第一她體 優先權且具有第-等待時間的第—程序請求存取 資源； 〃 =疋—ΐ —程序是否正在同時請求存取該共享資源， ㈣二程序具有在該總體仲裁器的總體優先權仵 一總體優先權且具有第二等待時間； 如果該第二程序正在同時缚卡 .^ ^ 子°月求存取該共享資源，則准 間者存取；& 中之具有較長的等待時 如果該第一等待時間等於該 以 禾一等待時間，則准哞兮 弟一程序與該第二程序中之呈 隹序5亥 取。 〃有較高總體優先權者存 11·如申請專利範圍第10項之方法， H 其中該總體優先權佇列 糸该總體仲裁器的複數個總體 又％%仔列之一，且各她 V-* 、、、心 200305105 申請專利範圍ί續頁 體優先權佇列對應於—已知的共享資源。 12·如申請專利範 一 圍弟10項之方法，其中額外包括如果該第 同日$清求存取該共享資源，則： 判定該第二程序是否目前鎖定該共享資源； 如果該第二鞀& α、， 和十— 私序目丽鎖定該共享資源，則拒絕該第一 耘序存取該共享資源；及 :果該第二程序未鎖定該共享資源，則 序存取該共享資源。 枉 13. —種裝置，包括： 代表•應程序仲裁複數個資源之-的區域仲裁器； 一指示該對應程序的狀態之信號。 14. 如申請專利範圍第13 甘士 # ^ 先權方塊，以扑-料額外包括一區域優 曰不忒對應程序的區域優先權。 15·如申請專利範圍第13 元件，以判—封…、、置，，、中額外包括一計時器 疋μ對應程序的等待時間。 16. —種系統，包括： 一或更多共享資源；及 一或更多程序，各料 系統且有一卩怏从1 彳口琥系統，且各信號 八有區域仲裁器，以仲裁該丘I次、语士 資源的存取。 、予貝源中之-已知 17. 如申請專利範圍第16項之 外包括—具有對應於1應程序^—^信㈣統額 裁器方塊，且該區域仲裁;#之品域優先權的區域仲 域仲裁“由准許該對應料存取（如 200305105 申_專和範圍$頁_ 果該區域仲裁器的對應程序具有比一衝突的程序之區域 總體優先權），以仲裁該共享資源之一已知資源的存取。 18. 如申請專利範圍第口項之系統，其中該區域優先權係固 定。 19. 如申請專利範圍第17項之系統，其中該已知的信號系統 額外i括s十日守益元件，且該區域仲裁器藉由下列操作 而仲裁該共享資源之一已知資源的存取： 如果該對應程序等待該已知資源比該衝突的程序更 久’則准許該對應程序存取；及 如果該對應程序等待該已知資源的時間數量與該衝突 的程序相同，如果該對應程序具有比該衝突的程序更高 的區域優先權，則准許該對應程序存取。 20. 如;申請專利範圍第16項之系統，其中該區域仲裁器藉由 准許該對應程序存取（如果無衝突的程序），仲裁該共享 資源之一已知資源的存取。 2L如申請專利範圍第2G項之系統，其中㈣統額外包括一 具有總體優先權佇列的總體仲裁器，該總體仲裁器用 於： " 藉由移動已獲准存取-已知資源的程序至一在該總體 優先權佇列中之具有最低優先權的位置，修改程序優先 權；及 藉由准許第-程序與第二程序中之具有較高總體優先 權者存取，仲裁㈣-程序與該第：程序之間的衝突。 泣如申請專利範圍第16項之系統，其中該信號額外包括一 200305105 ΐ請專利範圍續頁 计日守器兀件，且該區域伸辨 古+ ^仲裁的精由下列操作而仲裁該共 子賁源之一已知資源的存取·· 如果該對應程序等彳吝今欠 、以已知貝源比一衝突的程序更 久，則准許該對應程序存取；及· 如果忒對應程序等待該已知^ ^ ^ ^ ^ ^ ^ 貝，愿的犄間數Ϊ與該衝突 的程序相同，則將該仲裁程戽 „ , , ^ ^ ^ *序卸载至一總體仲裁器。 23·如申請專利乾圍第22 ”22項之糸統’其中該系統額外包括一 具有總體優先權佇列的總體 伸裁杰，该總體仲裁器用 -V \ · 藉由移‘已獲准存取一已知 優先權狩列中之1有最低優序至—在該總體 權；及 之’、有取低優先杻的位置，修改程序優先 藉由准許第一程序盘第- ^ 序/、弟一轾序中之具有較高總體優先 核者存取，仲裁該第一程序盥 24 - 4# ^ 5| π-- 一〜弟一程序之間的衝突。 粗 β扣八产 匕储存代表指令序列的資 科，或‘令序列在由處理琴勃 操作： 為一具有第 σ執仃蛉促使處理器執行下列 一程序請求存取一共； 先 資源； 判疋弟一程序是否正在同時士主书 詨第二寇成目士— 仕^化5弓求存取該共享資源 X第一 #序具有弟二區域優先權，·及 如果該第二程序同時請求存取該乒 ^ /¾ 4t 子貝源’貝!/准許言J 弟一優先榷與該第二優先權中 存取。 之具有杈焉區域優先權者 200305105 專利範圍續頁 體’其中該區域 固定。 體，其中額外包 旱資源，則額外 執行時促使該處 資源； ’則拒絕該第一 則准許該第一程 25.如申請專利範圍第24項之機器可讀取媒 優先權對於各第一與第二優先權而言係 26·如申請專利範圍第24項之機器可讀取媒 括如果該第二程序未同時請求存取該共 包括指令序列，該指令序列在由處理器 理為執行下列操作： 判定該第二程序是否目前鎖定該共享 如果该第二程序目前鎖定該共享資源 程序存取該共享資源；及 如果该第二程序未鎖定該共享資源， 序存取該共享資源。 27· —種裝置，包括： 至少一處理器；及 機：可讀取媒體，其上具有編碼的指令，該指令在 由處理器執行時能夠指導處理器·· 資源· 〃有第區域優先權的第一程序請求存取一共享 判定一笛 一 ^ —裎序是否正在同時請求存取該共享資源， 弟一程序具有第二區域優先權；及 二第二程序同時請求存取該共享資源，則准許該 广①振與該第二優先權中之具有較高區域優先 存取。 28·如申請專利範图 々^ 圍弟27項之破置，其中該區域優先權對於 弟一與第二優先權而言係固定。 200305105 2:!:t利範圍第27項之裝置，其中如果該第二程序未 叫睛求存取該共享資源，則額外包括： 額外編石馬的指人，# 4匕人 處理器： π⑽曰々在由處理器執行時能夠促使 1疋及ί—程序是否目前鎖定該共享資源； 1^—程序目前鎖定該共享資源，難絕該 私序存取該共享資源；及 =該第二程序未鎖定該共享資源， 序存取該共享資源。 币 30. —種裝置，包括： 用於代表對應程序仲裁複數個資源之一的裝置；及 用於指示該對應程序的狀態之裝置。 、， 31·:申請專利範圍第3〇項之裝置，其中額外包括用於指示 忒對應程序的區域優先權之裝置。 、s 32.如申請專利範圍第3〇項之裝置，其中額外包括 一 該對應程序的等待時間之裝置。 、曰不