Tiểu luận Các chiến lược cung cấp tài nguyên trong hệ tin học phân tán
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
KHOA CÔNG NGHỆ THÔNG TIN

TIỂU LUẬN MÔN HỌC
HỆ TIN HỌC PHÂN
TÁN

Đề tài:
CÁC CHIẾN LƯỢC CUNG
CẤP TÀI NGUYÊN
GVHD : PGS. TS. Lê Văn Sơn
HVTH : Trần Quốc Huy
Lớp : KHMT K10(2012-2014)
Trang 1
Đà Nẵng, tháng 7/2014
Tiểu luận Các chiến lược cung cấp tài nguyên trong hệ tin học phân tán
LỜI MỞ ĐẦU
Ngày nay, với sự phát triển thần kỳ, ngành công nghệ thông tin đã đem đến
cho loài người rất nhiều tiện ích trong công việc và trong cuộc sống. Dù ở bất cứ
nơi đâu, chúng ta đều có thể giao tiếp, chia sẽ thông tin, tài liệu thông qua các hệ
thống thông tin .Các thành tựu mới được phát minh ra nối tiếp nhau, trong đó
phải kể đến các phần mềm tăng khả năng điều hành, khai thác hiệu quả các tài
nguyên của hệ thống tin học. Đặc biệt, các nhà nghiên cứu và các lập trình viên
chuyên nghiệp rất quan tâm đến việc nghiên cứu và ứng dụng hệ thống tin học
phân tán.
Trong phạm vi của đề tài, tôi chủ yếu trình bày Các chiến lược cung cấp
tài nguyên trong hệ thống tin học phân tán.
Tôi xin chân thành cảm ơn thầy giáo PGS- TS Lê Văn Sơn đã nhiệt tình
giảng dạy và giúp tôi hoàn thành tiểu luận này. Tôi cũng xin cảm ơn các bạn lớp
Khoa học máy tính khoá K10 2008 – 2010 Đại học Đà Nẵng đã nhiệt tình góp ý

vừa yếu về chức năng phục vụ.
Và theo thời gian, con người đã xây dựng nên các chương trình trợ giúp có
tính chất hệ thống như chương trình dịch từ hợp ngữ sang ngôn ngữ máy, chượng
trình soạn thảo theo dòng,…do đó làm giảm nhẹ công việc lập chương trình.
I.1.3. Các hệ thống tin học thế hệ thứ 2
Vào cuối những năm 50, đầu những năm 60, con người đã xay dựng các
chương trình monitor thường trú cho phép liên kết hợp các công việc lại với nhau
và thực hiện một lần. Việc liên kết ấy có ý nghĩa rất lớn trong tự động hoá và các
hoạt động của hệ tin học.
Trang 3
Tiểu luận Các chiến lược cung cấp tài nguyên trong hệ tin học phân tán
Năm 1960, chương trình BPS( Batch processing system) được xây dựng
thành công nhằm vào các thiết bị phần cứng nhằm sử dụng hết hiệu năng của bộ
xử lý và bước đầu triển khai cơ chế bảo vệ
Năm 1969, hệ điều hành UNIX được xây dựng bởi ông Ken Thompson cho
phép người sử dụng làm việc theo kiểu chia sẽ thời gian trong hệ thống đa nhiệm.
I.1.4. Các hệ thống tin học thế hệ thứ 3
Thế hệ này được đặc trưng bởi các sự kiện lớn sau:
Vào những năm 70, các máy tính cá nhân ra đời với sự tiện ích cao, khả
năng vượt trội, và đặc biệt là giá cả hợp lý đã nhanh chóng chinh phục mọi người
và mở ra một trang mới trong việc phát triển ngành tin học.
Tiếp theo là sự xuất hiện của hệ thống song song cho phép cải tiến các máy
vốn sử dụng một bộ xử lý hay bộ vi xử lý duy nhất thành hệ thống đa bộ xử lý
nhằm tăng độ tin cậy của hệ thống.
Vào những năm 80. Hệ thống mạng cục bộ Ethernet và Token Ring được
phát minh là những mạng tiêu biểu cả về lý thuyết lẫn triển khai ứng dụng.
Hệ tin học phân tán đòi hỏi phần cứng của mình phải trang bị bộ nhớ cục
bộ, các bộ xử lý trao đổi thông qua các hệ thống đường truyền khác nhau như cáp
chuyên dụng, bus trao đổi, đường điện thoại, đường cáp quang, mạng điện chiếu
sáng cao và hạ thế.’…

bao gồm bốn thực thể như hình 1 bên dưới.
Cấu hình phần cứng của mạng có thể bao gồm các bộ xử lý có cấu tạo hoàn
toàn khác nhau về khả năng, tốc độ và được thiết kế cho các chức năng không
giống nhau. Chúng có thể là các bộ xử lý, các trạm làm việc, các máy tính trung và
các máy tính điện tử vạn năng lớn.
Bên cạnh hệ thống phần cứng, phần mềm, dữ liệu, hệ phân tán còn có hệ
thống truyền thông. Nhưng điều cơ bản để phân biệt hệ tin học phân tán với mạng
máy tính và hệ điều hành mạng chính là nguyên tắc xây dựng hệ được liệt kê như
bản dưới đây:
Trang 5
Các hệ
thống phần
mềm
Hệ thống dữ
liệu
Các hệ
thống phần
cứng
Hệ thống
truyền
thông
Hình 1: Bốn thực thể của hệ tin học phân tán.
Tiểu luận Các chiến lược cung cấp tài nguyên trong hệ tin học phân tán
Stt Tên gọi Thuyết minh
1.
Chia sẽ tài
nguyên
Thực tế phát triển mạng máy tính đặt ra một vấn đề lớn là cần
phải dùng chung tài nguyên. Một tiến trình trên một trạm nào đó
có thể cung cấp tài nguyên dùng chung ở một trạm khác.

Trong cấu trúc tập trung, ta có hệ thống máy trung tâm để cho phép lưu trữ
toàn bộ thông tin, người sử dụng có thể truy cập vào đó để xử lý thông tin của
mình. Giải pháp này dễ dàng triển khai và được ứng dụng rộng rãi trong thập niên
60 và 70.
I.2.3.2. Giao thức
Khi nhiều người sử dụng liên lạc với nhau trong mạng để thực hiện công
việc nào đó thông qua kênh truyền hình bằng cách sử dụng giao diện của mình,
giao thức là tập hợp những quy tắc cần thiết cho các dịch vụ tầng có thể thực hiện
được và cho phép việc nhận và gửi thông tin đến tầng tương ứng.
Trang 6
Tiểu luận Các chiến lược cung cấp tài nguyên trong hệ tin học phân tán
I.2.3.3. Thông điệp
Người sử dụng có thể chia cắt thông tin truyền theo các kiểu khác nhau,
song, chung quy có thể có hai kiểu là chia cắt logic và chia cắt vật lý.
Chia cắt logic thường khi các thông điệp bao gồm tập hợp thông tin gắn bó
với nhau theo một logic nào đó như bản ghi, tập tin, do đó kích cỡ của thông điệp
thường không phải là đại lượng cố định, để truyền các thông điệp này người ta
phải có thêm những thông tin điều khiển như giá trị số chỉ kích cỡ, tín hiệu bắt đầu
và kết thúc một thông điệp.
Chia cắt vật lý thông thường được phân nhóm nhằm thoả mãn những ràng
buộc đường truyền hoặc ràng buộc về mặt lưu trữ. Những thông điệp này thường
là những gói thông tin có kích cỡ cố định. Trước khi phát thông tin vào đường
truyền, trạm phát phải chia thông tin thành các gói theo những quy ước chặt chẽ.
Quá trình này được tiến hành tự động ở các tầng thấp và người sử dụng không thể
nhận biết được quá trình đó.
I.3. Các đặc trưng của hệ tin học phân tán
Đối tượng nghiên cứu của môn học hệ tin học phân tán là xử lý các vấn đề
đặt ra một cách tương đối chi tiết.
Các khía cạnh của hệ tin học phân tán chỉ dừng lại ở các vấn đề cơ bản có
tính chất nguyên lý .

Tài nguyên được định nghĩa như một đối tượng mà trong đó các quy tắc sử
dụng và chia sẽ được kết hợp với nhau, đó là vấn đề quyền truy cập loại trừ hay
truy cập chia sẽ, có hạn chế số lượng người sử dụng hay không.
Khái niệm giao dịch là một thực thể sử dụng chẳng hạn như người sử dụng
các tài nguyên thường được sử dụng trong hệ tin học phân tán. Giao dịch là phép
toán hợp thành một logic hoàn chỉnh mà việc triển khai nó có thẻ dẫn đến thực
hiện một tiến trình duy nhất hay nhiều tiến trình được định vị trên các trạm khác
nhau.
Một tiến trình nào đó cần sử dụng tài nguyên để phát triển công việc của
mình phải yêu cầu bộ cung cấp một cách hợp thức bằng cách gởi thông điệp yêu
cầu. Thông điệp yêu cầu này được gọi ngắn gọn là yêu cầu. Như vậy, một tiến
trình có nhu cầu tài nguyên sẽ bị treo chừng nào đó tài nguyên đó còn chưa được
giải phóng hay chưa được cung cấp cho nó.
Bộ cung cấp có thể áp dụng nhiều kiểu cung cấp khác nhau như tiến trình
duy nhất, tập hợp các tiến trình, tập hợp các thủ tục,…Các thông điệp yêu cầu sử
dụng tài nguyên cũng có thể có các dạng khác nhau như gọi thủ tục, thông báo,
thực hiện các lệnh đặc biệt…
Thuật ngữ tải là tập hợp các yêu cầu tuân theo các quy tắc của một bộ cung
cấp với các tham số đặc trưng : số lượng các yêu cầu được cung cấp tài nguyên,
bản chất của các vấn đề , phân tán theo thời gian các yêu cầu tạo ra nó.
Một yêu cầu được thoả mãn bởi bộ cung cấp tài nguyên cho tiến trình đề
nghị với điều kiện là yêu cầu đó phải tuân thủ các quy định nhất định.
Có hai điều kiện cho tiến trình mất khả năng sử dụng tài nguyên đã được
cung cấp là :
Trang 8
Tiểu luận Các chiến lược cung cấp tài nguyên trong hệ tin học phân tán
• Giải phóng: là tiến trình phát tín hiệu ngừng sử dụng tài nguyên.
• Thu hồi: là sự lấy lại tài nguyên đã được cung cấp cho tiến trình. Bộ
cung cấp tài nguyên sẽ tiến hành công việc này.
Hoạt động của một tập hợp các tiến trình trên một tập hợp các tài nguyên

chờ tài nguyên
T
2
được giải phóng bởi Tr
1
và Tr
3
. Thêm vào đó tiến trình Tr1 chờ tiến trình Tr
2
giải phóng T
1
.
Thiếu tài nguyên vĩnh viễn là sự chờ đợi bất tận của một tiến trình mà yêu
cầu của nó trễ đến mức không thể xác định được. Nguyên nhân của hiện tượng này
có nhiều nhưng chúng ta có thể chỉ ra ví dụ thường gặp là do sử dụng luật ưu tiên
để cung cấp tài nguyên.
Một chiến lược cung cấp tài nguyên tồi cũng có thể là nguồn gốc huỷ hoại
hiệu năng hoạt động của hệ do các hiện tượng sốc làm tăng các yêu cầu mà không
Trang 9
T
T
3
3
T
T
1
1
T
T
2

II.2. Cung cấp tài nguyên duy nhất
Vấn đề cung cấp tài nguyên duy nhất trên một trạm trong hệ phân tán liên
quan đến việc phân phối tài nguyên này cho một tập hợp các tiến trình trên cơ sở
quy tắc: truy cập loại trừ hay chia sẽ, có hệ số ưu tiên, không được mất,…Các tiến
trình có thể đề nghị sử dụng tài nguyên ngay tại trạm có tài nguyên mà cũng có thể
ở các trạm khác từ xa.
Việc quản lý các truy cập đến một tài nguyên duy nhất có thể được thực
hiện theo hai cách sau:
 Truy cập bằng một tiến trình duy nhất.
 Truy cập bằng các tiến trình tương tranh
II.2.1. Truy cập bằng một tiến trình duy nhất.
Một tiến trình duy nhất hay còn gọi là server được giao nhiệm vụ quản lý
tài nguyên. Nó xử lý tất cả các yêu cầu truy cập từ các tiến trình và các khách. Sự
Trang 10
Tiu lun Cỏc chin lc cung cp ti nguyờn trong h tin hc phõn tỏn
loi tr truy cp c bo m bi tớnh duy nht ca server. Server ng thi cng
l chng trỡnh ỏnh thc.
Chng trỡnh cú th vit nh sau:
Vũng lp:
M:=cho_thong_diep(nil) {Treo}
<Chng trỡnh x lý cỏc yờu cu v gi tr kt qu>
Kt thỳc vũng lp
Do vy, s ny loi b tt c cỏc c tớnh song song truy cp vo ti
nguyờn. Tin trỡnh server cú th c lp trỡnh trin khai ton b chin lc
liờn quan n loi tr tng h ca cỏc yờu cu ( u tiờn, quyn truy cp ti
nguyờn).
II.2.2 Truy cp cỏc tng tranh cú iu kin
Trong trng hp ny ti nguyờn c truy cp bi nhiu server, thụng
thng cú s lng thay i. Cỏc server ny thc hin cỏc truy cp tng ng vi
cỏc yờu cu di dng thc hin cỏc th tc. Vic thc hin cỏc th tc ny c

ton hp thc thỡ ti nguyờn ny c giao cho p s dng. Ta núi rng ti nguyờn
ny ó c p ci then , nu khụng thỡ p b treo v tt nhiờn l p khụng ci then
c ti nguyờn ny.
Trong h phõn tỏn, ta s tp trung xem xột cỏc giao dch T
i
cú th s dng
cỏc ti nguyờn c nh v trờn cỏc trm. Mi mt giao dch c trin khai nh
mt tp hp cỏc tin trỡnh th hin l cỏc i din ca chỳng trờn cỏc trm cú th
thc hin song song. Nhm thu hi li ti nguyờn e trờn trm S
i
, giao dch thc
hin phộp toỏn V_loai_tru_th(e) thụng qua i din P
ij
ca mỡnh trờn trm ny.
Ngoi tr mt s trng hp c bit, vic cung cp ti nguyờn din ra
khụng cú thu hi. Mt ti nguyờn b khúa bi mt tin trỡnh khụng th rỳt nú tr
v c. Nh th nú cn c gii phúng mt cỏch tng minh bi tin trỡnh ny
nh phộp m then ci mo_then(e).
Nh vy cú th xy ra ri ro do b tc, khi cỏc tin trỡnh truy cp loi tr
c phõn phi m khụng cú kh nng thu hi cỏc tin trỡnh cn phi s dng
ng thi nhiu ti nguyờn.
Vớ d cú hai tin trỡnh p v q cựng s dng hai ti nguyờn e
1
v e
2
, chỳng
c mụ t trong on chng trỡnh nh sau:
Trang 12
S1
S2

thì tất yếu xảy ra vấn đề
chặn nhau giữa p và q. Lý do hiển nhiên là p
2
và q
2
không bao giờ được đáp ứng,
nếu e
1
và e
2
không được giải phóng.
Bế tắc có thể được giải quyết bằng cách dự báo và phòng tránh ( gọi là dự
phòng) có nghĩa là tài nguyên được cung cấp theo kiểu có đề phòng trường hợp bế
tắc. Một phương pháp khác có liên quan đến vấn đề này là phát hiện và chữa trị có
nghĩa là khi có sự cố thì quay trở về trạng thái trước đó.
Các thuật toán dự phòng, phát hiện và chữa trị đã được nghiên cứu cho
trường hợp là tất cả các tài nguyên đều được quản lý bởi bộ cung cấp duy nhất. Bộ
cung cấp này tiếp nhận tất cả các yêu cầu và biết rất rõ trạng thái của tất cả các tài
nguyên.
II.4. Phân tán chức năng cung cấp
Ví dụ rằng chức năng cung cấp tài nguyên không thể tin tưởng giao phó
hoàn toàn cho một bộ cung cấp duy nhất mà được phân tán thành một tập hợp các
bộ cung cấp trên các trạm khác nhau, trong đó mỗi bộ cung cấp chỉ quản lý các đối
tượng cục bộ của trạm đó mà thôi. Chúng ta có hai nhóm phương pháp cho vấn đề
đặt ra:
 Duy trì tính duy nhất của trạng thái tài nguyên
Biểu hiện duy nhất của trạng thái tài nguyên được chia sẽ bởi tập hợp
các bộ cung cấp. Biểu hiện này tuần hoàn giữa các trạm khác nhau dưới
dạng một thông điệp. Các trạm luân phiên đóng vai trò của bộ cung cấp tài
nguyên mà mình đang chịu trách nhiệm quản lý. Giải pháp này loại bỏ tất

5 Tập hợp các yêu cầu không được thỏa mãn
6 Tập hợp các thông điệp dành cho trường hợp đã được sử dụng
7 Tập hợp các thông điệp dành cho trường hợp thất bại
8 …………………….
Cung cấp tài nguyên chỉ được chấp thuận nếu trạng thái xuất phát từ việc
cung cấp đó được đánh giá là chấp nhận được theo thuật toán đã sử dụng. Trên cơ
sở thực hiện một thuật toán và có cùng thông tin , mỗi trạm ra quyết định cung cấp
căn cứ vào bản sao trạng thái cục bộ của nó. Việc cung cấp cho tiến trình đề nghị
sẽ thực hiện ngay trên trạm có tài nguyên.
Để cập nhật thông tin, mỗi tiến trình phát đi cho tập hợp nhất định các trạm:
 Các thông điệp của mình.
 Các yêu cầu của mình.
 Các thông điệp giải phóng của mình.
Trang 14
Tiểu luận Các chiến lược cung cấp tài nguyên trong hệ tin học phân tán
Các bản sao trạng thái tổng quát trên các trạm phải có cùng các bước
chuyển trạng thái. Để đảm bảo điều đó, cần phải xử lý các yêu cầu trong cùng một
trật tự trên tất cả các trạm. Trật tự này có thể khác với trật tự đến. Ta có thể sử
dụng các kỹ thuật đã được kiểm tra như dấu, bộ tuần tự tuần hoàn để giải quyết
vấn đề đồng bộ thông tin.
Khi thực hiện một giao dịch T
i
thì giao dịch này cần phải phát thông điệp
hợp thức của tập hợp các tài nguyên mà nó định sử dụng. Một tài nguyên chỉ có
thể thu hồi, nếu đó là một phần của thông điệp.
Ta định nghĩa một quan hệ là phụ thuộc thế năng giữa hai giao dịch T
J
và
T
k

và
e
3
. Ta ký hiệu a_loai_tru_th() là phép toán thông điệp.
Giả sử rằng các lệnh thực hiện theo trình tự t
11
, t
21
,t
31
, t
12
, t
22
, t
32
vào thời
điểm t sau khi thực hiện các lệnh này, đồ thị G có thể biểu diễn như sau. Bế tắc
không tránh khỏi được. Đồ thị G được biểu diễn trong hình vẽ 5 sau:
Trang 15
t
11
:a_loaûi_tru_th(e
1
,e
2
)t

3
)
Giao dëch T1 Giao dëch T
2
t
31
:a_loaûi_tru_th(e
3
,e
1
)t
32
:v_excl(e
3
)t
33
:v_loaûi_tru_th(e
1
)
Giao dëch T
3
T1
T
2

1
, S
2
v
S
3
. Nu trm S
i
ch nhn cỏc thụng cỏo tng ng vi ti nguyờn m nú qun lý thỡ
nú ch duy trỡ th G
i
l hỡnh nh thu nh ca G cho cỏc giao dch ó phỏt thụng
cỏo. Nh vy, sau khi ó thc hin t
32
, ta cú cỏc hỡnh nh nh hỡnh 6 sau:
Rừ rng thụng qua ba th trờn õy, ta khụng phỏt hin mch khộp kớn cú
th dn n tỡnh trng b tc. Nhng, nu h tp trung hay trng thỏi khụng phi
tng phn, ta cú th nh hỡnh 7 bờn di
Trang 16
T1
T
2
e2 e
1
e
3
T
3
Hỗnh 7 Voỡng troỡn kheùp kờn trón õọử thở
T

hiện sự hình thành một vòng lặp bế tắc, nhưng trên một trạm cho trước nào đó, ta
lại không thể dự phòng bế tắc có kết quả được.
Ta sẽ thay thế điều kiện cung cấp trong đồ thị G không vòng một điều kiện
khác mạnh hơn nhưng được kiểm tra bằng các thông tin cục bộ trên từng trạm.
Để làm được điều đó, ta thêm vào cho từng đồ thì G
i
’ hình ảnh thu nhỏ cho
S
i
của đồ thị một quan hệ trật tự toàn bộ chặt chẽ được xác định trên tập hợp các
giao dịch. Quan hệ trật tự này có thể có được nhờ phương tiện dấu. Điều kiện cung
cấp tài nguyên là duy trì tình trạng không vòng lặp cho các đồ thị G
i
. Căn cứ theo
cấu trúc, điều kiện này có thể được kiểm tra cục bộ trên từng trạm.Ta sẽ được chỉ
ra G có được tình trạng không vòng lặp như thế nào. Để làm việc đó, ta bắt đầu chỉ
ra sự tồn tại của vòng trong G kéo theo sự tồn tại của vòng trong ít nhất một G
i
’
Ta ký hiệu T
J
>T
k
là quan hệ trật tự toàn phần chặt chẽ trên các giao dịch .
Lúc này, G
i
’ là hình ảnh thu nhỏ của trạm S
i
của đồ thị quan hệ >> xác định bởi
T

Nếu S là số của trạm chứa tài nguyên bị cài then bởi T
q
và thuộc quyền sở
hữu của thông báo của T
p
thì G
i
’ chứa vòng lặp.
 Thuật toán
Thuật toán dự phòng được triển khai như sau:
Bước1 : Việc cung cấp tài nguyên tại trạm S cho giao dịch T
i
được tiến hành nếu
việc cung cấp đó không tạo ra vòng lặp trong đồ thị G
i
’.
Bước 2: Trong trường hợp bị từ chối, tiến trình thực hiện giao dịch trên trạm S
được đưa vào hàng đợi cục bộ tại S.
Bước 3: Khi tài nguyên được giải phóng, tất cả các tiến trình của hàng đợi được
kiểm tra nếu các yêu cầu của chúng có thể được thỏa mãn.
Quá trình vận hành thuật toán được minh hoạ bởi ví dụ sau đây:
Ví dụ :
Xét lại thí dụ 1. Khi T
1
thực hiện T
12
: v_loai_tru_th(e
1
), yêu cầu này vào
xung đột với thông cáo a_loai_tru_th(e

2
. Tng t nh vy, yờu cu
t
32
:v_loai_tru_th(e
3
) b t chi bi vỡ nú to ra vũng lp trờn S
3
. Nhng ta cn lu ý
l nu trt t theo dng T
1
,T
2
, T
3
thỡ yờu cu va nờu cú th c chp nhn.
Thut toỏn ny t ra mt nguyờn tc tng t nh cỏc nhúm sp xp. Duy
ch cú khỏc nhau mt iu l nú trỏnh c s thiu thn vụ hn, bi vỡ trt t
tng quỏt c trin khai cho cỏc giao dch ch khụng phi cho cỏc ti nguyờn.
Mt giao dch tr nờn rt cn thit l giao dch cú thi gian ch di nht sau mt
khong thi gian xỏc nh, do vy nú tr thnh giao dch c u tiờn nht trờn tt
c cỏc trm m nú ó gi thụng ip.
Thut toỏn phỏt hin b tc.
Khi cỏc ti nguyờn c s dng bi giao dch c xỏc nh theo kiu
ng trong quỏ trỡnh thi hnh giao dch, cỏc phng phỏp d phũng b tc da trờn
nn tng cỏc thụng ip khụng cũn phự hp c na. Lỳc ny, ta phi s dng
cỏc phng phỏp phỏt hin v cha tr.
Phng phỏp ny c mụ t bi Menasce s c trỡnh by. Phng phỏp
ny t ra vn s dng mt th cỏc tranh chp m vic kim tra cỏc tranh
chp ú cho phộp phỏt hin b tc.

J
> T
k
tng ng tn ti ớt nht mt ti nguyờn b ci then bi T
J
v yờu
cu bi T
k
nhng khụng c ỏp ng.
Quan h ny c biu hin bng mt th gi l th cỏc xung t hu
hiu. S tn ti mt vũng lp trong th ny bỏo hiu cho ta bit s cú b tc din
ra. Mt giao dch khụng b chn cú ngha l trong th biu hin bng mt nỳt
m ti ú khụng cú cung no dn n.
Gi s rng T
k
l mt giao dch b chn. Tp hp tt c cỏc giao dch m cú
th t c bng cỏch chy khp cỏc cung xut phỏt t T
k
theo chiu ngc li
vi hng ca chỳng v gi l tp hp cỏc chn ca T
k
kớ hiu l R(T
k
). Cỏc giao
dch thuc vo R(T
k
) l cỏc giao dch cú ngun gc t s chn ca T
k
.
Ti mt thi im cho trc, th cỏc xung t hin hu hiu sinh ra cỏc

)= {T
1
,T
2
}
th cỏc xung t hu hiu cha vũng lp nu v ch nu tn ti giao dch T
k
m
tp hp chn ca nú cha mt giao dch b chn bi T
k
:
Tn ti k: B(T
k
) E(T
k
) khỏc 0 {tn ti vũng lp}
Nu ta khụng mun duy trỡ trờn mi trm mt bn sao ca th tng quỏt
thỡ cn phi xõy dng mt nh cc b cho phộp ỏnh giỏ cỏc iu kin va nờu
trờn.
ú l iu m ta thc hin trong gii thut sau õy:
Thut toỏn:
Ta ký hiu S(T
k
) l trm ngun ca giao dch T
k
. cho mi giao dch T
k
,
trm S(T
k

đã yêu cầu một tài nguyên e của trạm S
i
nào đó. Trên trạm
này, ta thực hiện các phép toán sau đây:
Bước 1: Nếu e là có sẵn để dùng, yêu cầu được thỏa mãn và ta ghi nhận là T
k
đang
có tài nguyên.
Bước 2: Nếu e đã được cung cấp cho giao dịch T
J
thì thông điệp T
J
chặn T
k
được
truyền cho trạm S(T
j
) và S(T
k
) . Sau này( j,k) chỉ một thông điệp như vậy.
Khi nhận một thông điệp (j,k) trên một trạm S nào đó, ta thực hiện các động
tác sau đây:
 Trên trạm S(T
j
) nguồn của giao dịch chặn T
k
ta thêm T
k
vào tập hợp
B(T

j
) giao E(T
k
) =0
Ta tiếp tục gởi thông điệp (j,m) về phía các trạm nguồn của các giao dịch
T
m
bị chặn bởi T
k
nhằm cho phép các trạm S(T
m
) cập nhật các tập hợp E(T
m
) của
các giao dịch chặn T
m
.
II.5. Điều khiển tải
Chức năng quan trọng nhất của việc điều khiển tải là duy trì một cách nhịp
nhàng các yêu cầu về tài nguyên của hệ trong một giới hạn chấp nhận được trên cơ
sở số lượng tài nguyên hiện hành và các thông số hiệu năng cần tuân thủ.
Vai trò của việc điều khiển tải trong hệ được thể hiện dưới hai phương diện
sau:
 Điều khiển tổng quát: Điều khiển tải một cách tổng quan trong hệ như
là người giữ nhịp cho các hoạt động cung cấp tài nguyên.
 Điều khiển phân tán: Phân tán tải cho các đối tượng có khả năng cung
cấp như là người điều khiển hợp lý việc phân bố các tài nguyên.
Trang 20
Tiểu luận Các chiến lược cung cấp tài nguyên trong hệ tin học phân tán
II.5.1.Điều khiển tải tổng quát.

Nguời ta phân chi ra hai loại chiến lược phân tán tải như sau:
 Chiến lược tĩnh: Việc phân tán các yêu cầu giữa các server được xác
định theo kiểu cố định
 Chiến lược thích nghi: là việc phân tán này được xác định như là chức
năng tải của hệ.
II.5.3.Triển khai quá trình điều khiển
Trong các hệ phân tán, việc điều khiển tải được tiến hành ở tầng giao vận,
nơi bao gồm nhiều tài nguyên phần cứng như các đường truyền thông tin hay các
bộ nhớ đệm trong các nút mạng.
Trong các ứng dụng khác, các trạm thông thường được chuyên môn hoá, do
vậy có rất ít cơ hội để thực hiện các công việc này.
*Kết luận:
Để chọn lựa phương án triển khai giải quyết vấn đề tải trong hệ phân tán,
người ta quan tâm hàng đầu đến độ tin cậy, ổn định và chi phí thực hiện của
chúng. Tuyệt đại bộ phận các giải thuật đã được nghiên cứu cho vấn đề tải đến nay
vẫn còn là những giải thuật tương đối chính xác có nghĩa là chưa có giải thuật nào
đạt đến mức độ hoàn hảo như mong muốn. Như vậy, trong trường hợp chọn đường
theo kiểu thích nghi như mạng Arpanet hay internet là giải pháp chấp nhận được.
.
Trang 22
Tiểu luận Các chiến lược cung cấp tài nguyên trong hệ tin học phân tán
PHẦN II: BÀI TẬP
Đề bài:
1. Hãy tưởng tượng là ta đang triển khai công tơ sự kiện phân tán trên N
trạm. Giả sử rằng trong thời gian đầu các trạm hoạt động rất ổn định và ta cài đặt
trên mỗi trạm một công tơ sự kiện cục bộ. Hãy cho biết làm thế nào một trạm có
thể có giá trị ảnh của công tơ sự kiện trên mỗi trạm. Hãy trình bày ý kiến của bạn
khi có một trạm bị sự cố.
2. Bây giờ ta cài đặt trên N trạm một ảnh của công tơ sự kiện phân tán,
được tăng một số gia truyền cho mỗi lần sự kiện đến. Bạn hãy cho biết các vấn đề

có sản phẩm vừa được sản xuất ( Receive (P)), trạm tiêu thụ C sẽ tăng giá trị công
tơ sự kiện N thêm một đơn vị (Increase(N)).
Sau mỗi lần tiêu thụ sản phẩm, trạm tiêu thụ C sẽ tăng biến N
C
thêm một
đơn vị (N
C
=N
C
+1) và gửi thông điệp thông báo cho trạm sản xuất P biết có sản
phẩm vừa được tiêu thụ ( Send(P)).
Sau khi nhận được thông báo từ trạm tiêu thụ C (Receive(C)), trạm sản xuất
P sẽ tăng giá trị của công tơ sự kiện N thêm một đơn vị (Increase(N)).
Như vậy, khi ta đặt trên mỗi trạm một công tơ sự kiện cục bộ. Để một trạm
có giá trị ảnh của công tơ sự kiện trên mỗi trạm ta dựa trên hệ thống nhiều bản sao
cho phép đăng ký từ xa. Hệ thống cục bộ đều có lưu trữ một bản sao của tất cả các
thông tin liên quan đang ở tất cả các hệ cục bộ bằng cách gửi và nhận thông điệp .
Khi một trạm bị sự cố:
Một trạm hoạt động có thể xảy ra rất nhiều sự cố khác nhau, đó có thể là
một sự cố về truyền thông, về giao dịch, về phần mềm hay phần cứng….Để một
trạm bị sự cố xảy ra mà không ảnh hưởng gì đến hoạt động của các trạm khác và
có thể thiết lập được trạng thái sau khi đã khắc phục để đưa vào trong mạng ta nên
dùng tệp nhật ký. Nhật ký là công cụ để chống lại tình trạng mất dữ liệu khi xảy ra
sự cố hệ thống. Nhật ký là bản ghi chép các thay đổi được thực hiện và tình trạng
của mỗi giao dịch .
Nếu một vị trí M phát hiện rằng N bị sự cố, M sẽ ghi sự kiện này vào nhật
ký. Khi N khôi phục, nó gửi thông báo đến mỗi vị trí. Nếu M nhận được thông báo
này, nó sẽ xem lại nhật ký và tìm lại điểm N gặp sự cố rồi gửi giá trị mới nhất của
các mục chung của M và N cho N
Đồng thời khi một trạm bị sự cố, mạng cần phải gởi thông điệp