Cơ bản về hệ điều hành phân tán (Phần 1) - Chương 5

lập lịch quá trình phân tán Ph-ơng tiện TT và đồng bộ là các thành phần hệ thống thiết yếu hỗ trợ việc thực hiện đồng thời các QT t-ơng tác. Tr-ớc khi thực hiện, QT cần phải đ-ợc lên lịch (lập lịch) và định vị tài nguyên. Mục đích chính của lập lịch là nâng cao độ đo hiệu năng tổng thể hệ thống, chẳng hạn thời gian hoàn thành QT và tận dụng bộ xử lý. Việc tồn tại các nút xử lý phức trong hệ phân tán làm nảy sinh vấn đề thách thức cho lập...
Nội dung trích xuất từ tài liệu:
Cơ bản về hệ điều hành phân tán (Phần 1) - Chương 5 Bµi gi¶ng HÖ ®iÒu hµnh ph©n t¸n (PhÇn 1) Hµ Quang Thôy ch−¬ng V. lËp lÞch qu¸ tr×nh ph©n t¸n Ph−¬ng tiÖn TT vµ ®ång bé lµ c¸c thµnh phÇn hÖ thèng thiÕt yÕu hç trî viÖc thùc hiÖn ®ång thêi c¸c QT t−¬ng t¸c. Tr−íc khi thùc hiÖn, QT cÇn ph¶i ®−îc lªn lÞch (lËp lÞch) vµ ®Þnh vÞ tµi nguyªn. Môc ®Ých chÝnh cña lËp lÞch lµ n©ng cao ®é ®o hiÖu n¨ng tæng thÓ hÖ thèng, ch¼ng h¹n thêi gian hoµn thµnh QT vµ tËn dông bé xö lý. ViÖc tån t¹i c¸c nót xö lý phøc trong hÖ ph©n t¸n lµm n¶y sinh vÊn ®Ò th¸ch thøc cho lËp lÞch QT trªn c¸c bé xö lý vµ ng−îc l¹i. LËp lÞch kh«ng chØ ®−îc thùc hiÖn côc bé trªn mçi nót mµ trªn toµn bé hÖ thèng. C¸c QT ph©n t¸n cã thÓ ®−îc thùc hiÖn trªn c¸c nót xö lý tõ xa vµ cã thÓ di tró tõ nót nµy tíi nót kh¸c ®Ó ph©n bè t¶i nh»m t¨ng hiÖu n¨ng. Môc ®Ých thø hai cña lËp lÞch lµ thÑc hiÖn trong suèt ®Þnh vÞ vµ hiÖu n¨ng b»ng lËp lÞch QT ph©n t¸n. VÊn ®Ò lËp lÞch QT (hay c«ng viÖc) ®· ®−îc kh¶o s¸t réng r·i ®èi víi nghiªn cøu ®iÒu hµnh. §· cã nhiÒu kÕt qu¶ lý thuyÕt vÒ ®é phøc t¹p cña lËp lÞch bé ®a xö lý. Tuy nhiªn, lËp lÞch QT trong hÖ ph©n t¸n cÇn ®Ò cËp c¸cλ chó ý thùc tÕ th−êng bÞ bá qua trong ph©n tÝch lËp lÞch ®a xö lý truyÒn thèng. Trong hÖ ph©n t¸n, tæng phÝ TT lµ ®¸ng kÓ, t¸c dông cña h¹ tÇng c¬ së kh«ng thÓ bá qua vµ tÝnh “®éng” cña hÖ thèng ph¶i ®−îc ®Þnh vÞ. C¸c thùc tÕ nµy gãp phÇn t¹o thªm sù phøc t¹p cña lËp lÞch QT ph©n t¸n. Ch−¬ng nµy ®−a ra m« h×nh nh»m ®¹t ®−îc hiÖu qu¶ h¹ tÇng TT vµ hÖ thèng khi lËp lÞch. LËp lÞch QT ph©n t¸n ®−îc tæ chøc thµnh hai néi dung: lËp lÞch QT tÜnh, vµ chia sÎ vµ c©n b»ng t¶i ®éng. Thi hµnh thuËt to¸n lËp lÞch ph©n t¸n ®ßi hái thùc hiÖn tõ xa vµ/hoÆc n¨ng lùc di tró QT trong hÖ thèng. Mét sè vÊn ®Ò thi hµnh thùc hiÖn tõ xa vµ di tró QT ®−îc ®Ò cËp. KÕt thóc ch−¬ng giíi thiÖu hÖ thèng thêi gian thùc ph©n t¸n, trong ®ã lËp lÞch lµ kho¶ng tíi h¹n thêi gian vµ xøng ®¸ng ®−îc quan t©m ®Æc biÖt. 5.1. M« h×nh hiÖu n¨ng hÖ thèng C¸c thuËt to¸n song song vµ ph©n t¸n ®−îc m« t¶ nh− tËp QT phøc ®−îc chi phèi b»ng c¸c quy t¾c ®iÒu chØnh t−¬ng t¸c gi÷a c¸c QT. ¸nh x¹ thuËt to¸n vµo mét kiÕn tróc ®−îc xem xÐt nh− bé phËn cña thiÕt kÕ thuËt to¸n hoÆc ®−îc xem xÐt mét c¸ch riªng biÖt nh− bµi to¸n lËp lÞch ®èi víi mét thuËt to¸n cho tr−íc vµ mét kiÕn tróc hÖ thèng cho tr−íc. Ch−¬ng 3 sö dông m« h×nh ®å thÞ ®Ó m« t¶ TT QT vµ t¹i ®©y xem xÐt t−¬ng t¸c QT theo m« t¶ tæng qu¸t nhÊt theo thuËt ng÷ ¸nh x¹. H×nh 5.1 cho vÝ dô ®¬n gi¶n vÒ mét ch−¬ng tr×nh tÝnh to¸n gåm cã 4 QT ®−îc ¸nh x¹ tíi mét hÖ thèng m¸y tÝnh kÐp víi 2 bé xö lý. T−¬ng t¸c QT ®−îc biÓu diÔn kh¸c nhau theo ba m« h×nh. Trong m« h×nh QT ®i tr−íc ë h×nh 5.1 (a), tËp QT ®−îc biÓu diÔn b»ng mét ®å thÞ ®Þnh ph−íng phi chu tr×nh (DAG-Directed Acycle Graph). Cung cã h−íng biÓu thÞ quan hÖ ®i tr−íc gi÷a c¸c QT vµ chÞu tæng phÝ truyÒn th«ng nÕu c¸c QT kÕt nèi víi nhau b»ng mét cung ®−îc ¸nh x¹ tíi 2 bé xö lý kh¸c nhau. M« h×nh nµy ®−îc øng dông tèt nhÊt cho c¸c QT ®ång thêi ®−îc sinh ra do c¸c cÊu tróc ng«n ng÷ ®ång thêi nh− cobegin/coend hay fork/join. Mét ®é ®o h÷u dông cho lËp lÞch tËp QT nh− vËy lµ lµm gi¶m thêi gian hoµn thµnh bµi to¸n xuèng møc tèi thiÓu, bao gåm c¶ thêi gian tÝnh to¸n vµ TT. M« h×nh QT TT trong h×nh 5.1 (b) m« t¶ mét kÞch b¶n kh¸c, trong ®ã QT ®−îc t¹o ra ®Ó cïng tån t¹i vµ truyÒn th«ng dÞ bé. Cung v« h−íng trong m« h×nh QT TT chØ m« t¶ nhu cÇu truyÒn th«ng gi÷a c¸c QT. Do thêi gian thùc hiÖn trong m« h×nh lµ kh«ng râ rµng nªn môc tiªu lËp lÞch lµ tèi −u tæng gi¸ truyÒn th«ng vµ tÝnh to¸n. Bµi to¸n ®−îc chia theo ph−¬ng ph¸p nh− vËy lµm gi¶m ®Õn møc tèi thiÓu chi phÝ truyÒn th«ng liªn- - 125- Bµi gi¶ng HÖ ®iÒu hµnh ph©n t¸n (PhÇn 1) Hµ Quang Thôy bé xö lý vµ gi¸ tÝnh to¸n cña QT trªn c¸c bé xö lý. M« h×nh cña QT ®i tr−íc vµ truyÒn th«ng lµ c¸c m« h×nh QT t−¬ng t¸c. b) M« h×nh QT truyÒn th«ng c) M« h×nh QT kh«ng kÕt nèi H×nh 5.1. Ph©n lo¹i qu¸ tr×nh M« h×nh QT ®éc lËp ë h×nh 5.1(c), t−¬ng t¸c QT lµ ngÇm ®Þnh, vµ gi¶ sö r»ng c¸c QT cã thÓ ch¹y mét c¸ch ®éc lËp vµ ®−îc hoµn thµnh trong thêi gian h÷u h¹n. C¸c QT ®−îc ¸nh x¹ tíi c¸c bé xö lý sao cho tËn dông ®−îc c¸c bé xö lý mét c¸ch tèi ®a vµ lµm gi¶m thêi gian quay vßng c¸c QT xuèng ®Õn møc nhá nhÊt. Thêi gian quay vßng c¸c QT ®−îc x¸c ®Þnh nh− tæng thêi gian thùc hiÖn vµ xÕp hµng do ph¶i chê c¸c QT kh¸c. Trong tr−êng hîp ®éng, cho phÐp QT “di tró” gi÷a c¸c bé xö lý ®Ó ®¹t hiÖu qu¶ trong chia xÎ vµ c©n b»ng t¶i. NÕu QT ®−îc phÐp di tró tõ nót cã t¶i lín ®Õn nót cã t¶i nhá th× ®Þnh vÞ ban ®Çu c¸c QT lµ ch−a tíi h¹n. H¬n n÷a, hiÖu n¨ng ®−îc c¶i tiÕn ®¸ng kÓ do lÞch c¸c QT trë nªn thÝch øng víi sù thay ®æi t¶i hÖ thèng. Chia xÎ vµ c©n b»ng t¶i kh«ng h¹n chÕ c¸c QT ®éc lËp. NÕu QT truyÒn th«ng víi mét QT kh¸c th× chiÕn l−îc “di tró” nªn chó ý c©n b»ng c¸c thay ®æi trong c¸c nhu cÇu truyÒn th«ng gi÷a c¸c bé xö lý do thay ®æi bé xö lý vµ lîi Ých tõ chia xÎ t¶i. Ph©n ho¹ch bµi to¸n thµnh nhiÒu QT ®Ó gi¶i lµm thêi gian hoµn thµnh bµi to¸n nhanh h¬n. T¨ng tèc ®−îc coi nh− ®é ®o hiÖu n¨ng lµ môc tiªu ®¸ng quan t©m trong thiÕt kÕ c¸c thuËt to¸n song song vµ ph©n t¸n. T¨ng tèc tÝnh to¸n lµ mét hµm cña thiÕt kÕ thuËt to¸n vµ hiÖu qu¶ cña thuËt to¸n lËp lÞch ¸nh x¹ thuËt to¸n vµo kiÕn tróc hÖ thèng h¹ tÇng. D−íi ®©y ®−a ra mét m« h×nh t¨ng tèc m« t¶ vµ ph©n tÝch mèi quan hÖ gi÷a thuËt to¸n, kiÕn tróc hÖ thèng vµ lÞch thùc hiÖn. Trong m« h×nh nµy, hÖ sè t¨ng tèc S lµ hµm cña thuËt to¸n song song, kiÕn tróc cña hÖ thèng vµ lÞch thùc hiÖn, ®−îc biÓu diÔn theo c«ng thøc: S = F(thuËt to¸n, hÖ thèng, lÞch). S cã thÓ ®−îc viÕt nh− sau: OCPTiedal OSPT OSPT S= = = S i xS d ...