分布式操作系統(tǒng)(編輯修改稿)
2025-08-14 10:34 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 布式管理時(shí) ， 每個(gè)資源由位于不同結(jié)點(diǎn)上的資源管理共同來(lái)管 ， 每個(gè)資源管理在決定分配它管理的資源以前 ， 必須和其他資源管理者協(xié)商 。 必須設(shè)計(jì)一個(gè)算法 ， 各資源管理者按此算法共同協(xié)商資源的分配 。 分布式進(jìn)程同步 (2) ? 算法應(yīng)滿足：資源分配的互斥性 、 不產(chǎn)生餓死現(xiàn)象 、 且各資源管理者處于平等地位而無(wú)主控者 。 ? 通常把這種資源分配算法稱(chēng)分布式同步算法 ， 由同步算法構(gòu)成的機(jī)制稱(chēng)分布式同步機(jī)制 。 ? 進(jìn)程間通過(guò)網(wǎng)絡(luò)通信聯(lián)系會(huì)有延遲 。 ? 必須要解決對(duì)不同計(jì)算機(jī)中發(fā)生的事件進(jìn)行排序的問(wèn)題 ， 再設(shè)計(jì)出性能優(yōu)越的分布式同步算法 。 1 事件排序 (1) ?進(jìn)程同步的實(shí)質(zhì)是對(duì)多個(gè)進(jìn)程在執(zhí)行順序上的規(guī)定，為此，應(yīng)對(duì)系統(tǒng)中所發(fā)生的事件進(jìn)行排序。 ?定義一個(gè)關(guān)系稱(chēng)作 “ 先發(fā)生 ” ，表達(dá)為 “ a→b ”讀作 “ a在 b之前發(fā)生 ” ，意思是指系統(tǒng)中所有進(jìn)程認(rèn)為事件 a先于事件 b發(fā)生。 事件排序 (2) 三種情況會(huì)產(chǎn)生先發(fā)生關(guān)系 情況 (1)：如果 a和 b是同一進(jìn)程中的兩個(gè)事件 ， 且 a發(fā)生在 b之前 ， 則 a→b 為真； 情況 (2)：如果 a是一個(gè)進(jìn)程發(fā)送消息事件 ， b為另一個(gè)進(jìn)程接收該消息事件 ，則 a→b 為真； 情況 (3)：存在某個(gè)事件 c， 若有 a→c 并且 c→b ， 則 a→b 為真 。 事件排序 (3) 定義事件的 “ 先發(fā)生 ” 關(guān)系后， ?同一進(jìn)程中兩個(gè)事件的先后關(guān)系可以被明確確定， ?不同進(jìn)程中發(fā)生的事件間的先后關(guān)系，有一部分可以被確定，而另一部分則不能確定。 事件排序 (5) 例如，三個(gè)進(jìn)程 P P2和 P3，分別發(fā)生以下事件： ?事件 a ： P1 發(fā)送消息給 P2 ； ?事件 b ： P2 接收來(lái)自 P1 的消息； ?事件 c ： P2 接收到 P1 的消息后發(fā)消息給 P3； ?事件 d ： P3 接收來(lái)自 P2 的消息； 事件排序 (6) 顯然有： a→b→c→d ； 然而，如果 P2在事件 b之前發(fā)生過(guò)某事件 f，例如，打印輸出，盡管可以確定： f→b ， f→c ， f→d 但 a和 f間的先后關(guān)系無(wú)法確定。 事件排序 (7) 如果兩個(gè)事件 x和 y發(fā)生在不同進(jìn)程中，且這兩個(gè)進(jìn)程也不交換信息，那么 x→y 和y→x 都不成立，這兩個(gè)事件就稱(chēng)為并發(fā)事件，無(wú)法確定這兩個(gè)事件誰(shuí)先誰(shuí)后。 事件排序 (8) 定義邏輯時(shí)鐘 (時(shí)間戳 ) ? 定義邏輯時(shí)鐘的實(shí)質(zhì)是把一個(gè)系統(tǒng)中的事件映射到一個(gè)正整數(shù)集合上的一個(gè)函數(shù) C， 并滿足：若事件 a先發(fā)生于事件 b，則 C(a)小于 C(b)。 系統(tǒng)中的每個(gè)進(jìn)程都擁有自己的邏輯時(shí)鐘 。 ? 邏輯時(shí)鐘的定義指出 ， 如果事件 a先發(fā)生于事件 b， 則 a的邏輯時(shí)鐘小于 b的邏輯時(shí)鐘 。 反之不然 ， 因?yàn)?， 兩個(gè)并發(fā)事件的邏輯時(shí)鐘的大小沒(méi)有定義 ， 所以 ， 邏輯時(shí)小的事件不見(jiàn)得先發(fā)生 事件排序 (9) 邏輯時(shí)鐘函數(shù)的構(gòu)造 (1) ?定義在某系統(tǒng)集合上的邏輯時(shí)鐘函數(shù) C如下： (1)對(duì)任一進(jìn)程 P中的非接收消息事件 ej， 若 ej 是 P的第 1個(gè)事件 ， 則 C(ej)=1 若 ej是 P的第 j個(gè)事件 ， 而第 j1個(gè)事件是 ej1 ， 則 C(ej)=C(ej1)+1 事件排序 (10) 邏輯時(shí)鐘函數(shù)的構(gòu)造 (2) (2)對(duì)任一進(jìn)程 P中的接收消息事件 er ， 若 er 是 P的笫 1個(gè)事件 ， 則 C(er)=1+C(es’ ) 此處 ， es’ 是進(jìn)程 P’發(fā)送這個(gè)消息的事件 。 若 er是 P的笫 r個(gè)事件 ，而第 r1個(gè)事件是 er1， 則 C(er)=1+max[c(er1)， C(es’)] 事件排序 (11) ?由 n個(gè)進(jìn)程組成的網(wǎng)絡(luò)系統(tǒng)，邏輯時(shí)鐘可用于對(duì)由消息傳輸所組成的事件進(jìn)行排序。 ?事件排序規(guī)則：對(duì)來(lái)自站點(diǎn) i的消息 x和來(lái)自站點(diǎn) j的消息 y，說(shuō)事件 x先發(fā)生于事件 y，如果： (1)Ti Tj 或 (2)如果 Ti = Tj 并且 i j 事件排序 (12) Lamport算法校正時(shí)鐘 0 6 12 18 24 30 36 42 48 54 60 0 8 16 24 32 40 48 56 64 72 80 0 10 20 30 40 50 60 70 80 90 100 D A B C P0 P1 P2 (a) 0 6 12 18 24 30 36 42 48 70 76 0 8 16 24 32 40 48 61 69 77 85 0 10 20 30 40 50 60 70 80 90 100 D A B C P0 P1 P2 (b) (a)三個(gè)進(jìn)程 ， 各有自己的時(shí)鐘 (b)Lamport算法校正時(shí)鐘 事件排序 (13) 時(shí)間戳算法的操作例子 P1 時(shí)間 P2 P3 0 1 4 5 2 3 6 0 1 6 7 0 4 2 5 6 (a, 1, 1) (b, 5, 1) (j, 5, 3) (x,3,2) 事件排序 (14) 時(shí)間戳算法的操作另一個(gè)例子 P1 時(shí)間 P2 P3 0 1 1 2 2 0 0 2 3 (a, 1, 1) (q, 1, 4) 3 P4 0 2 分布式同步算法 (1) (1)Lamport算法 (1) ? 分布式系統(tǒng)由 N個(gè)結(jié)點(diǎn)組成，每個(gè)結(jié)點(diǎn)建立數(shù)據(jù)結(jié)構(gòu) (一個(gè)數(shù)組，也叫隊(duì)列 )，用來(lái)記錄該結(jié)點(diǎn)最近收到的消息和該結(jié)點(diǎn)自己產(chǎn)生的消息。假定每個(gè)結(jié)點(diǎn)只有一個(gè)進(jìn)程和僅負(fù)責(zé)控制一種臨界資源，并
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1