Luận án Mô hình cung cấp tài nguyên phân tán giải quyết bài toán bế tắc trong hệ thống phân tán máy chủ ảo không thuần nhất

¸ t­c trong mô h¼nh P-out-of-Q gọi là b¸ t­c toàn cục. Điều ki»n ph¡t hi»n
b¸ t­c thº hi»n sự tồn t¤i cõa chu kỳ hoặc nút th­t trong đồ thị tranh ch§p
(WFG) [1] [5] [6]. Tuy nhi¶n, tr¶n thực t¸ khó có thº ph¡t hi»n và gi£i quy¸t
tri»t để b¸ t­c hơn so với mô h¼nh AND và mô h¼nh OR. Cho đ¸n nay, ½t có c¡c
nghi¶n cùu, đề xu§t thuªt to¡n ng«n chặn và thuªt to¡n gi£i quy¸t b¸ t­c têng
qu¡t theo mô h¼nh P-out-of-Q. C¡c thuªt to¡n đề xu§t thường sû dụng c¡c kỹ
thuªt Khu¸ch t¡n - t½nh to¡n, trong đó mët ti¸n tr¼nh (đưñc gọi là khởi t¤o) s³
gûi thông b¡o và mët ti¸n tr¼nh kh¡c s³ thu thªp thông điệp và tr£ lời. Ti¸n
tr¼nh khởi t¤o døng thực hi»n khi t§t c£ ti¸n tr¼nh k· theo cho ph²p thi¸t lªp đồ
thị réi. Dựa tr¶n quy¸t định b¸ t­c s³ đưa ra c¡c thông tin trong thông b¡o c¡o
ph£n hồi.
 Thuªt to¡n ph¡t hi»n b¸ t­c được chia thành hai lo¤i: thuªt to¡n tªp trung
dựa vào đồ thị cung c§p tài nguy¶n (RAG) và thuªt to¡n ph¥n t¡n dựa vào đồ
thị tranh ch§p (WFG). Trong c¡c thuªt to¡n tªp trung, ti¸n tr¼nh khởi t¤o s³
tªp hñp c¡c thông tin được thu tªp l¤i để x¡c định có hay không b¸ t­c t¤i tr¤m,
trong khi đó thuªt to¡n ph¥n t¡n y¶u c¦u thông tin được ph£i lan truy·n tr¶n
c¡c tr¤m.
 Thuªt to¡n ph¡t hi»n b¸ t­c trong mô h¼nh cung c§p tài nguy¶n P-out-of-Q
dựa tr¶n ti¸p cªn ph¡t hi»n tr¤ng th¡i toàn cục, gồm hai pha giao dịch: pha qu²t
thông điệp ra ngoài tø ti¸n tr¼nh khởi t¤o và pha thu thªp thông tin b¶n ngoài
gûi v· ti¸n tr¼nh khởi t¤o (pha qu²t vào trong). Trong đồ thị tranh ch§p luôn tồn
t¤i sự đối lªp c¡c thông b¡o được gûi ra theo hai hướng cõa c¤nh trong đồ thị
 41
tranh ch§p (qu²t ra ngoài hoặc t§t c£ c¡c thông b¡o được gûi ngược l¤i). Trong
pha qu²t ra ngoài, c¦n ph£i ghi l¤i thông tin tùc thời cõa tr¤ng th¡i đồ thị tranh
ch§p ph¥n t¡n. Trong pha qu²t vào trong, đồ thị tranh ch§p ph¥n t¡n ghi l¤i ch¿
là mët ph¦n cõa đồ thị tranh ch§p (WFG), đã được c­t bỏ. Ph¦n ghi l¤i này cho
ph²p x¡c định nút khởi t¤o có bị b¸ t­c hay không. C£ hai pha qu²t ra ngoài và
qu²t vào trong được thực hi»n đồng thời. Nhược điểm cõa kỹ thuªt này là hai
pha qu²t có thº chồng ch²o l¶n nhau t¤i cùng mët thời điểm.
H¼nh 2.1 Đồ thị tranh ch§p WFG trước và sau khi sû dụng thuªt to¡n ph¡t hi»n b¸
t­c Kshemkalyani-Singhal [6].
Trong h¼nh 2.1, nút A s³ gûi thông điệp ph¡t tràn (flood) li¶n tục đến c¡c nút
B và nút C. Khi nút C nhªn được thông điệp tø nút A, s³ gûi thông đi»p li¶n
tục đến c¡c nút D, E và F. N¸u nút x¡c nhªn ho¤t động (active) khi nhªn được
thông điệp, nó gûi tr£ l¤i mët thông điệp và thực hi»n xóa c¤nh, do vªy s³ thu
gọn đồ thị tranh ch§p WFG. Gi£ sû nút H gûi tr£ v· thông điệp ph£n hồi l¤i
cho nút D khi nhªn được thông điệp tø ch½nh nút D th¼ c¤nh DH được c­t gi£m
tương tự cho c¡c nút I và nút G. Khi đó nút F tự động c­t gi£m c¤nh DF v¼ nút
F nhªn được thông điệp sau khi nhªn được thông điệp tø nút C cùng với nút D
và nút E. Khi mët nút nhªn được thông điệp, nó không ph£i chờ c¤nh nèi với
nút gûi thông điệp bị xóa.
 42
2.1.2. Mô h¼nh cung c§p tài nguy¶n ph¥n t¡n M VM-out-
 of-1PM
 Dựa tr¶n mô h¼nh cung c§p tài nguy¶n ph¥n t¡n P-out-of-Q [6] và mô h¼nh
cung c§p tài nguy¶n theo y¶u c¦u [54], trong ph¦n này luªn ¡n đề xu§t mô h¼nh
c£i ti¸n cung c§p tài nguy¶n theo y¶u c¦u cho c¡c m¡y £o: Mô h¼nh cung c§p
tài nguy¶n ph¥n t¡n M VM-out-of-1PM (VM là m¡y £o, PM là m¡y vªt lý ) đã
được tr¼nh bày t¤i công bè sè (9) và mô h¼nh cung c§p tài nguy¶n ph¥n t¡n
M VM-out-of-NPM đã được tr¼nh bày t¤i công bè sè (9). Mô h¼nh ph¥n t¡n
M VM-out-of-1PM mô t£ M m¡y £o được cư trú t¤i mët m¡y vªt lý PM. Tài
nguy¶n m¡y vªt lý PM, bao gồm c¡c nguồn tài nguy¶n như: CPU, RAM, HDD
và c¡c tài nguy¶n m·m được ph¥n chia logic cho c¡c m¡y £o VM sû dụng.
 H¼nh 2.2 Mô h¼nh cung c§p tài nguy¶n ph¥n t¡n M -out-of-1PM.
 Trong mô h¼nh cung c§p tài nguy¶n m¡y chõ £o, sè lượng c¡c thông điệp y¶u
c¦u n¬m trong hàng đñi ch½nh b¬ng sè lượng c¡c m¡y £o được t¤o ra và mùc độ
chi ti¸t trong y¶u c¦u cung c§p ch½nh là c¡c thành ph¦n tài nguy¶n (v½ dụ: CPU,
RAM, HDD). Để cung c§p tèi ưu tài nguy¶n, bë cung c§p tài nguy¶n đưa ra c¡c
 43
ch½nh s¡ch, quy¸t định tài nguy¶n nào s³ được ph¥n bê, bao nhi¶u tài nguy¶n s³
được ph¥n bê cho m¡y £o, do vªy n¥ng cao hi»u qu£ cõa c¡c ùng dụng. Do đó
c¦n có mô h¼nh y¶u c¦u tài nguy¶n, cho ph²p thi¸t k¸ thuªt to¡n cung c§p tài
nguy¶n theo y¶u c¦u tài nguy¶n c¡c m¡y £o tr¶n mët m¡y chõ vªt lý.
 Trong mô h¼nh y¶u c¦u tài nguy¶n này, chúng ta c¦n c¥n đối hñp lý giúa y¶u
c¦u tài nguy¶n và kh£ n«ng cung c§p tài nguy¶n, để có được ch§t lượng dịch vụ
tèt nh§t, đòi hỏi khai th¡c tèi ưu c¡c nguồn tài nguy¶n hi»n có m¡y vªt lý. Lưu
ý r¬ng tài nguy¶n cõa m¡y chõ vªt lý thường giới h¤n.
 Kh£ n«ng cung c§p tài nguy¶n cõa h» tªp trung được x¡c định theo công
thùc như sau [32]:
 n m
 CPU CPU X X CPU
 E = A + Cij (2.1)
 i=1 j=1
 Trong đó: ECPU : Têng sè tài nguy¶n cõa CPU; ACPU : Sè tài nguy¶n cõa CPU
 CPU
chưa c§p ph¡t; Cij : Tài nguy¶n cõa CPU đang bị n ti¸n tr¼nh kh¡c chi¸m giú.
 Dựa tr¶n công tr¼nh nghi¶n cùu cõa t¡c gi£ Lasdon v· lý thuy¸t tèi ưu cho
h» thèng lớn [34] và công tr¼nh nghi¶n cùu cõa t¡c gi£ Yixuan Song [54], luªn
¡n đề xu§t mô h¼nh cung c§p tài nguy¶n tèi ưu cho mô h¼nh M VM-out-of-1PM
đã được tr¼nh bày chi ti¸t t¤i danh mục công tr¼nh t¡c gi£ (9).
 C¡c ký hi»u sau được sû dụng:
 - M là sè lượng c¡c m¡y £o VM cư trú t¤i mët m¡y chõ.
 - Eit là têng c¡c nguồn tài nguy¶n (CPU, c¡c tài nguy¶n kh¡c) s®n sàng cung
 c§p c¡c m¡y £o.
 - Dit là y¶u c¦u tài nguy¶n cõa m¡y £o VMi t¤i thời điểm t.
 - Qit mùc độ đáp ùng y¶u c¦u.
 - SPi là độ ưu ti¶n tĩnh cõa c¡c y¶u c¦u tài nguy¶n cõa m¡y £o thù i.
 - Φi ngưỡng ch§t lưñng cõa c¡c y¶u c¦u tài nguy¶n cõa m¡y £o thù i.
 44
 - Ci là tài nguy¶n đã cung c§p cho VMi. Ð đây sû dụng ngưỡng tài nguy¶n
 tèi thiºu Ci để tr¡nh sự tương tranh c¡c m¡y £o khi cùng tương tranh cùng
 CPU
 mët nguồn tài nguy¶n. V½ dụ: Cij là tài nguy¶n CPU tèi thiºu để cung
 c§p cho m¡y £o VMi.
Hàm Ft x¡c định ch§t lưñng đáp ùng c¡c y¶u c¦u, tương ùng với độ ưu ti¶n tĩnh
cõa c¡c y¶u c¦u tài nguy¶n.
 M
 X Qit
 F = × SP (2.2)
 t Φ i
 i=1 i
Trong công thùc 2.2 mùc độ đáp ùng c¡c y¶u c¦u Qit phụ thuëc vào têng nguồn
tài nguy¶n trong h» thèng và y¶u c¦u tài nguy¶n t¤i thời điểm t có thº x¡c định
theo công thùc Qit sau:
 Qit = fi(Eit;Dit) (2.3)
Vªy công thùc (2.2) được vi¸t l¤i như sau:
 M M
 X Qit X fi(Eit;Dit)
 F = × SP = × SP (2.4)
 t Φ i Φ i
 i=1 i i=1 i
 V§n đ· cung c§p tài nguy¶n dịch vụ h¤ t¦ng (IaaS) là làm th¸ nào kiºm so¡t
được vi»c cung c§p tài nguy¶n cho c¡c m¡y £o mët c¡ch hi»u qu£, kh­c phục
h¤n ch¸ tài nguy¶n cõa m¡y chõ vªt lý. V¼ vªy, c¦n ph£i tèi ưu ch§t lượng đáp
ùng y¶u c¦u:
 M
 F = min P fi(Eit;Dit) × SP
 t Φi i
 i=1
 8 M
 P (2.5)
 Eit ≤ E
 i=1
 >
 : Eit ≥ Ci(i = 1; 2; :::; M)
 Trong công thùc (2.5) chúng tôi đưa ra trong điều ki»n l½ tưởng và dựa vào
cơ sở cõa công thùc (2.1). Têng y¶u c¦u tài nguy¶n đối với c¡c m¡y £o t¤i thời
 45
điểm t luôn luôn không thº lớn hơn tài nguy¶n m¡y chõ vªt lý E và không thº
nhỏ hơn gi¡ trị Ci ngưỡng tài nguy¶n tèi thiºu có thº cung c§p cho m¡y £o thù
i.
 Dựa tr¶n công thùc (2.5) t½nh to¡n mùc độ cung c§p tài nguy¶n theo mô h¼nh
cung c§p tài nguy¶n M VM-out-of-1PM, luªn ¡n đề xu§t ¡p dụng thuªt to¡n c£i
ti¸n song song ph¡t hi»n b¸ t­c PDDA được tr¼nh bày ở mục 3.2.1 chương 3. Khi
ch¤y đồng thời trong qu¡ tr¼nh cung c§p tài nguy¶n, n¸u ph¡t hi»n hi»n được
chu tr¼nh b¸ t­c, th¼ h» thèng gûi thông đi»p cho c¡c ti¸n tr¼nh kh¡c bi¸t t¼nh
tr¤ng y¶u c¦u tài nguy¶n thời điểm này. Trong khi đó, t¤i trung t¥m h» thèng
s³ khôi phục c¡c tài nguy¶n đã c§p ph¡t trước đó. Điều này làm cho vi»c cung
c§p tài nguy¶n trở hñp lý hơn. Có thº th§y vi»c cung c§p tài nguy¶n theo y¶u
c¦u cho c¡c m¡y chõ £o ch¤y tr¶n m¡y chõ vªt lý trở n¶n hi»u qu£ và ti¸t ki»m
được thời gian. Trong thuªt to¡n này, luªn ¡n dựa vào đồ thị có hướng cung c§p
tài nguy¶n (RAG) để ph¡t hi»n b¸ t­c, khi t¼m được chu tr¼nh kh²p k½n trong
đồ thị tranh ch§p.
2.1.3. Mô h¼nh cung c§p tài nguy¶n ph¥n t¡n M VM-out-
 of-N PM
 Mô h¼nh cung c§p tài nguy¶n ph¥n t¡n M VM-out-of-N PM. Mô h¼nh ph¥n
t¡n M VM-out-of-N PM mô t£ M m¡y £o được cư trú t¤i N m¡y vªt lý PM,
trong đó m¡y £o có thº cùng mët lúc sû dụng c¡c tài nguy¶n ở nhi·u hơn mët
m¡y chõ vªt lý. Mô h¼nh tèi ưu tài nguy¶n được tr¼nh bày t¤i công tr¼nh công bè
cõa t¡c gi£ sè (9).
 Tø công thùc (2.1) được tr¼nh bày ở ph¦n tr¶n, ta có thº ph¡t triºn công thùc
cung c§p tài nguy¶n trong cung c§p tài nguy¶n ph¥n t¡n cho h» thèng m¡y chõ
£o như sau:
 N Mi n Mi
 CPU X X CPU X X CPU
 E = ( Aj + Cij ) (2.6)
 Mi=1 j=1 i=1 j=1
Trong công thùc (2.6) c¡c ký hi»u đưñc gi£i th½ch như sau:
 46
 H¼nh 2.3 Mô h¼nh cung c§p tài nguy¶n ph¥n t¡n M VM-out-of-N PM.
 - N sè lượng c¡c m¡y chõ vªt lý ph¥n t¡n.
 CPU
 - Cij là kh£ n«ng tèi thiºu cõa tài nguy¶n j cung c§p cho VMi. V½ dụ: Ci
 là tài nguy¶n CPU tèi thiºu có thº cung c§p cho m¡y £o VMi.
 - E là têng c¡c nguồn tài nguy¶n như CPU hoặc c¡c tài nguy¶n kh¡c có s®n
 cung c§p cho t§t c£ c¡c m¡y £o dựa tr¶n tài nguy¶n N m¡y chõ vªt lý.
 Có thº mở rëng công thùc (2.5) x¡c định hàm mục ti¶u cho mô h¼nh nhi·u
m¡y chõ £o được ra ra tø mët m¡y vªt lý, luªn ¡n s³ đưa ra hàm mục ti¶u
tèi ưu cho mô h¼nh nhi·u m¡y chõ £o được t¤o ra tr¶n nhi·u m¡y vªt lý (M
VM-out-of-N PM ).
 Ta có c¡c ký hi»u sau:
 - M là sè lượng c¡c m¡y £o, cư trú tr¶n N m¡y chõ ph¥n t¡n.
 - Dit là y¶u c¦u tài nguy¶n cõa m¡y £o VMi t¤i thời điểm t.
 - Qit là mùc độ đáp ùng y¶u c¦u cung c§p tài nguy¶n cho c¡c m¡y £o VMi
 t¤i thời điểm t.
 - Oit là ch§t lưñng cõa c¡c y¶u c¦u được đáp ùng.
 47
 - SPij là ch½nh s¡ch ưu ti¶n tĩnh cõa c¡c ùng dụng.
 - Φij là ngưỡng ch§t lượng cõa c¡c ùng dụng.
 - ENijt là nguồn tài nguy¶n s®n có để cung c§p cho m¡y £o VMij tø m¡y
 chõ vªt lý Ni.
 x
 - EOijt là sè lượng tài nguy¶n tø m¡y chõ vªt lý x điều ki»n (1 ≤ x ≤ N), x
 là m¡y chõ ở xa cung c§p cho m¡y £o VMij.
 Dựa tr¶n công thùc (2.2) v· hàm mục ti¶u tèi ưu cho mô h¼nh nhi·u m¡y chõ
£o được ra ra tø mët m¡y vªt lý, hàm mục ti¶u tèi ưu cho mô h¼nh nhi·u m¡y
chõ £o được t¤o ra tr¶n nhi·u m¡y vªt lý (MVM-out-of-NPM ) như sau:
 N Mi f (EN ;PM EOx ;D )
 F = min P P ij ijt x=1 ijt ijt × SP
 t Φij ij
 i=1 j=1
 8 N M
 P Pi
 > Eijt ≤ E
 >
 > i=1 j=1
 > (2.7)
 Eijt ≥ Cij (i = 1; 2; :::; N; j = 1; 2; :::; Mi)
 Mi Mi
 > P P x
 > ENijt + EOijt ≤ Ei
 > j=1 j=1
 >
 >
 : Eit ≥ Cij (i = 1; 2; :::; N; j = 1; 2; :::; Mi):
 Dựa tr¶n công thùc t½nh to¡n mùc độ cung c§p tài nguy¶n cho mô h¼nh y¶u
c¦u tài nguy¶n M VM-out-of-N PM luªn ¡n đề xu§t thuªt to¡n c£i ti¸n sû dụng
hai pha giao dịch t¼m ki¸m hai chi·u (Two - Way) ph¡t hi»n b¸ t­c, được tr¼nh
bày ở mục 3.3.3, cho ph²p ph¡t hi»n b¸ t­c trong môi trường nhi·u m¡y chõ
vªt lý, được tê chùc ph¥n t¡n. Trong thuªt to¡n này, luªn ¡n dựa vào đồ thị có
hướng tranh ch§p tài nguy¶n (WFG) để ph¡t hi»n b¸ t­c, khi t¼m được chu tr¼nh
kh²p k½n trong đồ thị tranh ch§p.
 48
2.2. MÆ HÌNH CUNG CẤP TÀI NGUYÊN CHO HỆ
 THÈNG MÁY CHỦ ẢO DỰA TRÊN NỀN TẢNG
 PHÂN TÁN KHÆNG THUẦN NHẤT
 Nëi dung v· cung c§p tài nguy¶n cho h» thèng m¡y chõ £o dựa tr¶n n·n t£ng
không thu¦n nh§t được công bè t¤i c¡c bài b¡o sè (5) , (7) trong danh mục
công tr¼nh cõa t¡c gi£. Trong mô h¼nh cung c§p tài nguy¶n không thu¦n nh§t
cõa t½nh to¡n lưới (Grid Computing), méi tài nguy¶n t½nh to¡n lưới được xem
là mët nút. Nút này có thº là mët h» thèng xû lý đơn, cụm đa xû lý đối xùng
SMP (Symmetric Multiprocessing), h» xû lý ph¥n t¡n với nhi·u m¡y t½nh, si¶u
m¡y t½nh song song hay cụm c¡c m¡y tr¤m. H» thèng t½nh to¡n lưới không ¡p
đặt nhúng h¤n ch¸ l¶n c¡c thành ph¦n trong h» thèng mà được t½ch hñp. Méi h»
thèng tài nguy¶n, hay t¤i méi nút t½nh to¡n, có đặc t½nh tài nguy¶n kh¡c nhau.
H» thèng truy·n thông gh²p c¡c nguồn tài nguy¶n không thu¦n nh§t. Th¶m vào
đó, t½nh to¡n lưới không ¡p h¤n ch¸ l¶n c§u trúc li¶n k¸t m¤ng và độ tr¹ thông
tin li¶n l¤c giúa c¡c nút. H¼nh 2.4 đưa ra mët mô h¼nh h» thèng không thu¦n
nh§t, với c¡c nút kh¡c nhau và mët m¤ng lưới thông tin li¶n l¤c không đồng
nh§t. Đây là mët mô h¼nh thu nhỏ cõa c¡c h» thèng t½nh to¡n lưới. Thực t¸ triºn
khai cơ sở h¤ t¦ng t½nh to¡n lưới, có thº gh²p tø hàng ngàn nguồn tài nguy¶n
đa d¤ng. Méi nút trong h¼nh 2.4, bao gồm mët hoặc nhi·u bë xû lý giao ti¸p với
bë vi xû lý kh¡c. C¡c nút có c¡c li¶n k¸t nëi bë nút và c¡c li¶n k¸t ngoài giúa
c¡c nút. Bë vi xû lý và c¡c li¶n k¸t b¶n trong méi nút cũng có thº không thu¦n
nh§t. Méi h» thèng t½nh to¡n lưới có thº được xem là mët cụm £o c¡c bë vi xû
lý, dành ri¶ng cho gi£i quy¸t mët ùng dụng nào đó.
 H» thèng không thu¦n nh§t có thº được biºu di¹n dưới d¤ng mët đồ thị vô
hướng có trọng sè GH = (B, L), (gọi là đồ thị cõa h» thèng), bao gồm mët tªp
hñp c¡c đỉnh B = { b1; b2; :::; bng, tªp c¡c c¤nh L = { (bi; bj)jbi; bj 2 Bg, đại
di»n cho c¡c li¶n k¸t truy·n thông giúa c¡c bë vi xû lý. Méi bë xû lý (đỉnh ) b
có mët trọng sè ti¸n tr¼nh sb, biºu thị chi ph½. Méi li¶n k¸t (c¤nh) s³ có trọng
sè li¶n k¸t sb1b2 , biºu thị chi ph½ độ tr¹ truy·n thông (tr¶n mët đơn vị thông tin
 49
 H¼nh 2.4 Mô h¼nh h» thèng cung c§p tài nguy¶n ph¥n t¡n không thu¦n nh§t.
li¶n l¤c) giúa c¡c bë xû lý b1 và b2.
 Khi hai bë xû lý không k¸t nèi trực ti¸p, trọng sè li¶n k¸t cõa chúng là têng
nhỏ nh§t c¡c đường li¶n k¸t giúa chúng. V½ dụ, trong h¼nh 2.5, gi£ sû t§t c£ c¡c
nút có trọng sè 1 và t§t c£ c¡c li¶n k¸t nút 5, khi đó trọng sè cõa mët li¶n k¸t
giúa c¡c bë xû lý b0 (tương ùng với bë xû lý b0) và b7 là 19, dọc theo đường đi
b0, b1, b5, b7. C¡ch ti¸p cªn này cho ph²p x¡c định trọng sè li¶n k¸t trong đồ thị
đầy đủ cõa h» thèng. Dựa vào đó chúng ta có thº l§y được mët ma trªn chi ph½
truy·n thông, biºu thị chi ph½ thông tin li¶n l¤c giúa hai bë vi xû lý b§t kỳ trong
h» thèng. Khi có đë tr¹ theo c¡c hướng li¶n k¸t giúa hai bë vi xû lý s³ d¨n đến
ma trªn chi ph½ truy·n thông b§t đối xùng.
 Tø h¼nh 2.5 có thº x¡c định ma trªn trọng sè cung c§p tài nguy¶n không
thu¦n nh§t như sau:
 50
 H¼nh 2.5 Đồ thị h» thèng cung c§p tài nguy¶n không thu¦n nh§t.
 2 3
 0 5 6 6 6 6 19 19
 6 7
 6 7
 6 5 0 1 1 1 1 6 6 7
 6 7
 6 7
 6 6 1 0 1 1 1 6 6 7
 6 7
 6 7
 6 6 1 1 0 0 1 5 6 7
 6 7
 6 7
 6 6 1 1 0 1 1 6 6 7
 6 7
 6 7
 6 6 1 1 1 1 0 6 5 7
 6 7
 6 7
 619 6 6 6 6 6 0 197
 4 5
 19 6 6 6 6 5 19 0
 • Chi ph½ xû lý
 Khi g¡n cho đỉnh trong đồ thị mët lượng công vi»c xû lý, chi ph½ xû lý được
t½nh bởi công thùc:
 ρ ρ
 Wb = W × sb (2.8)
Ð đây:
 - Wρ là chi ph½ xû lý tøng y¶u c§u t½nh to¡n.
 - sb là trọng sè li¶n l¤c giúa c¡c bë xû lý.
 51
 Chi ph½ xû lý c¦n t½nh th¶m c£ lượng thời gian c¦n thi¸t để đỉnh b xû lý công
vi»c ρ. Ngoài ra, cán ph£i x²t tới chi ph½ truy·n thông thời gian c¦n thi¸t để
truy·n dú li»u giúa c¡c đỉnh trong tªp B. Mô h¼nh truy·n thông này, thº hi»n cơ
ch¸ tê chùc bë nhớ ph¥n t¡n, g­n với thông điệp gûi đi. Tương tự có thº sû dụng
cơ ch¸ tê chùc bë nhớ chung chia s´ cục bë. Điểm kh¡c bi»t là truy·n thông qua
bë nhớ chung. Để ph£n ¡nh phù hñp với c¡ch thưc tê chùc. Bë nhớ chia s´ cục
bë hay bë nhớ ph¥n t¡n, c¡c li¶n k¸t và khèi lượng xû lý ph£i được xem x²t mët
c¡ch hñp lý.
2.3. CUNG CẤP TÀI NGUYÊN PHÂN TÁN
 H» thèng t½nh to¡n ph¥n t¡n có thº h¼nh dung bao gồm mët tªp hñp c¡c ti¸n
tr¼nh được k¸t nèi thông qua m¤ng truy·n thông [6]. M¤ng truy·n thông này là
phương ti»n trao đổi thông điệp giúa c¡c ti¸n tr¼nh với nhau. Tuy nhi¶n, trong
thực t¸ luôn x£y ra tr¹ trong truy·n tin và không thº dự đoán trước được. Luªn
¡n gi£ định r¬ng môi trường truy·n thông là lý tưởng. Khi c¡c ti¸n tr¼nh không
chia s´ bë nhớ chung, c¡c giao ti¸p qua ti¸n tr¼nh thực hi»n thông qua trao đổi
thông điệp qua m¤ng truy·n thông theo mët trªt tự. Tuy nhi¶n thông điệp có
thº bị m§t, bị c­t x²n, sao ch²p. V¼ vªy, ph£i m§t thời gian chờ và truy·n l¤i.
Mặc kh¡c ti¸n tr¼nh có thº bị th§t b¤i khi y¶u c¦u tài nguy¶n hoặc đường truy·n
có thº bị ng­t qu¢ng.
 H» thèng cung c§p tài nguy¶n ph¥n t¡n có thº mô h¼nh hóa dưới d¤ng đồ
thị có hướng, trong đó đỉnh là c¡c ti¸n tr¼nh và c¡c cung biºu di¹n cho c¡c k¶nh
truy·n có hướng. Ngoài ra, h» thèng ph¥n t¡n cán phụ thuëc vào c¡c y¸u tè kh¡c
như k¶nh truy·n và thông điệp gûi và nhªn cõa c¡c ti¸n tr¼nh khi giao dịch với
nhau. Ký hi»u Kij là k¶nh truy·n tø ti¸n tr¼nh pi tới ti¸n tr¼nh pj và ký hi»u
mij là thông điệp đưñc gûi tø ti¸n tr¼nh pi tới pj. Ngoài đồ thị tr¶n thông tin
v· cung c§p tài nguy¶n ph¥n t¡n cán bao gồm c¡c thành ph¦n như sau: chương
tr¼nh ph¥n t¡n; ti¸n tr¼nh ph¥n t¡n; môi trường truy·n thông và tr¤ng th¡i têng
qu¡t cõa c¡c nút tham gia trong h» thèng.
 52
2.3.1. Kh¡i ni»m chương tr¼nh ph¥n t¡n
 Chương tr¼nh ph¥n t¡n có thº xem là tªp cõa c¡c ti¸n tr¼nh không đồng bë
p = fp1; p2; :::; png. C¡c ti¸n tr¼nh này trao đổi thông tin li¶n l¤c với nhau b¬ng
c¡ch gûi c¡c thông điệp qua m¤ng truy·n thông. Méi ti¸n tr¼nh có thº ch¤y dưới
sự điều khiºn cõa nhi·u bë xû l½ kh¡c nhau. C¡c ti¸n tr¼nh khi có thº thực thi
không đồng bë, mët c¡ch ng¨u nhi¶n tự động. Khi đã gûi thông điệp l¶n đường
truy·n, ti¸n tr¼nh s³ không kiºm so¡t thông điệp đó. Ti¸n tr¼nh gûi thông điệp
không nh§t thi¸t ph£i chờ đñi k¸t qu£ gûi thông điệp.
 Tr¤ng th¡i toàn cục cõa h» thèng t½nh to¡n ph¥n t¡n bao gồm mët tªp hñp
tr¤ng th¡i cõa c¡c ti¸n tr¼nh và tr¤ng th¡i k¶nh truy·n. Tr¤ng th¡i cõa ti¸n tr¼nh
được đặc trưng bởi tr¤ng th¡i cõa bë nhớ cục bë. Tr¤ng th¡i mët k¶nh truy·n
được đặc trưng bởi c¡c d¢y thông điệp truy·n trong k¶nh.
2.3.2. Kh¡i ni»m ti¸n tr¼nh thực thi ph¥n t¡n
 Ti¸n tr¼nh thực thi bao gồm tªp c¡c sự ki»n, c¡c ho¤t động tu¦n tự b¶n trong
ti¸n tr¼nh. Méi ho¤t động được coi là hành động nguy¶n tû (atomic) trong ti¸n
tr¼nh. Ho¤t động cõa ti¸n tr¼nh được chia làm ba lo¤i sự ki»n: sự ki»n cục bë, sự
 x
ki»n gûi thông điệp và sự ki»n nhªn thông điệp. K½ hi»u ei sự ki»n di¹n ra trong
ti¸n tr¼nh pi với x là thù tự c¡c sự ki»n cõa ti¸n tr¼nh pi. Ch¿ sè dưới, ch¿ sè tr¶n
có thº không có khi chúng không li¶n quan hoặc bị xóa.
 Khi sự ki»n xu§t hi»n, s³ làm thay đổi tr¤ng th¡i cõa ti¸n tr¼nh, tr¤ng th¡i
cõa k¶nh, g¥y ra hi»u ùng chuyºn đổi tr¤ng th¡i trong toàn h» thèng. Sự ki»n
cục bë làm thay đổi tr¤ng th¡i ti¸n tr¼nh khi thực thi. Sự ki»n gûi hoặc nhªn
thông điệp thay đổi tr¤ng th¡i cõa ti¸n tr¼nh gûi (hoặc ti¸n tr¼nh nhªn) thông
điệp và tr¤ng th¡i cõa c¡c k¶nh đã truy·n thông điệp được gûi (hoặc nhªn). C¡c
sự ki»n trong mët ti¸n tr¼nh được s­p x¸p theo thù tự tuy¸n t½nh. Khi thực thi
 1 2 x x+1
ti¸n tr¼nh pi s³ t¤o ra thù tự li¶n ti¸p cõa sự ki»n e = { ei ; ei ; :::; ei ; ei g, được
x¡c định bởi Hi: Hi = hi!i, ở đây hi là tªp cõa c¡c sự ki»n thực thi cõa ti¸n
tr¼nh pi và quan h» !i được định nghĩa bởi sự li¶n h» tuy¸n t½nh giúa c¡c sự
ki»n. Quan h» !i thº hi»n quan h» trước sau giúa c¡c sự ki»n trong ti¸n tr¼nh
 53
pi. Vi»c gûi và nhªn c¡c thông điệp t¤o ra c¡c !i thº hi»n dáng thông tin giúa
c¡c ti¸n tr¼nh t¤o ra quan h» phụ thuëc k²o theo giúa ti¸n tr¼nh gûi và ti¸n tr¼nh
nhªn.
 Với mët thông điệp m, k½ hi»u send(m) và rec(m) là ti¸n tr¼nh gûi và nhªn
thông điệp tương ùng. Li¶n h» !msg ghi l¤i phụ thuëc k²o theo v· sự thay đêi
thông điệp. Khi trao đổi thông điệp m giúa hai ti¸n tr¼nh ta có: send(m)!msgrec(m).
 H¼nh 2.6 Đồ thị mi¶u t£ truy·n thông điệp giúa ba ti¸n tr¼nh.
 Tr¶n h¼nh 2.6, đường ngang biºu thị ti¸n độ thực thi cõa ti¸n tr¼nh, với d§u
ch§m biºu thị cho sự ki»n, cán mũi t¶n xi¶n biºu thị chuyºn giao c¡c thông điệp
 2 4
giúa c¡c ti¸n tr¼nh. Ti¸n tr¼nh p1, có sự ki»n e1 gûi thông điệp, sự ki»n e1 là sự
ki»n nhªn thông điệp.
2.3.2.1. Quan h» trước sau giúa c¡c sự ki»n
 Thực thi ùng dụng ph¥n t¡n g­n với ho¤t động cõa c¡c sự ki»n trong c¡c ti¸n
tr¼nh. Công thùc (2.9) mi¶u t£ quan h» phụ thuëc trước sau giúa c¡c sự ki»n
trong thực thi ùng dụng ph¥n t¡n ta nói:
 8
 x y
 x y < ei !iej (i = j) ^ (x < y)
 ei ! ej , (2.9)
 x y
 : ei !msgej
 x y
 Quan h» ưu ti¶n trước sau ei ! ej ph£n ¡nh mèi li¶n h» giúa c¡c