Tiểu luận môn học Hệ phân tán
BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG
TIỂU LUẬN MÔN HỌC
HỆ PHÂN TÁN
ĐỀ TÀI:
I. Tài nguyên và chiến lược cung cấp tài nguyên
II. Cho hai loại tài nguyên: tài nguyên truy cập theo kiểu loại
trừ và tài nguyên truy cập theo kiểu chia sẻ. Trình bày thuật toán
Lomet và Menasce nhằm xử lý việc cung cấp tài nguyên của hai
nhóm tài nguyên nêu trên.
Giảng viên hướng dẫn: PGS.TS. Lê Văn Sơn
Học viên thực hiện: Nguyễn Nương Quỳnh
Lớp: Khoa học Máy tính - K24 Quảng Bình
Quảng Bình, tháng 12 năm 2012
Học viên: Nguyễn Nương Quỳnh
1
Tiểu luận môn học Hệ phân tán
LỜI MỞ ĐẦU
Hệ thống tin học hiện đại ngày nay đóng một vai trò quan trọng không thể
thiếu trong sự phát triển của toàn xã hội. Một thành tựu nổi bật nhất trong hệ thống
công nghệ thông tin là sự phát triển các phần mềm cơ sở nhằm trực tiếp làm tăng
khả năng điều hành, khai thác hiệu quả tất cả các tài nguyên của hệ thống thông tin.
Hệ thống tin học nói chung là hệ thống bao gồm hai phần cơ bản là phần cứng
và phần mềm được gắn bó một cách hữu cơ với nhau để thực hiện có hiệu quả cao
nhất về xử lý thông tin. Hệ tin học phân tán (hay nói gọn hệ phân tán) cũng là một
hệ thống xử lý thông tin nhưng bao gồm nhiều bộ xử lý hoặc bộ vi xử lý nằm tại các
vị trí khác nhau và được liên kết với nhau thông qua phương tiện viễn thông dưới sự
điều khiển thống nhất của một hệ điều hành. Có thể xem hệ phân tán như là một tập
hợp bao gồm các bộ xử lý, bộ vi xử lý với bộ nhớ và đồng hồ nhịp độc lập (tức là hệ
phân tán không chia sẻ bộ nhớ và đồng hồ). Do vậy, hệ tin học phân tán đòi hỏi hệ

bị mất trong quá trình chuyển tải, các thông điệp có thể được truyền kép và hệ thống
có thể rơi vào sự cố bất cứ lúc nào. Mặt khác, một hay nhiều máy tính cấu thành của
hệ phân tán cũng có thể xảy ra sự cố và hoạt động của hệ sẽ trở nên đình trệ, kém
hiệu quả. Do đó, việc bảo vệ tính vẹn toàn dữ liệu, quản lý tài nguyên, cung cấp tài
nguyên và sử dụng tài nguyên là vấn quan trọng hàng đầu. Chiến lược cung cấp tài
nguyên và các biện pháp khắc phục tình trạng bế tắc là nội dung được trình bày
trong tiểu luận này.
Với một lĩnh vực kiến thức còn khá mới, đa dạng và phức tạp cho nên việc
nghiên cứu của tôi còn nhiều hạn chế, rất mong được sự góp ý và định hướng của
Thầy Lê Văn Sơn và các anh chị cùng lớp để tôi có thể tiếp tục nghiên cứu và đạt
được kết quả tốt hơn trong thời gian tới.
Xin chân thành cảm ơn Thầy 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.
Học viên: Nguyễn Nương Quỳnh
3
Tiểu luận môn học Hệ phân tán
MỤC LỤC
A.
Học viên: Nguyễn Nương Quỳnh
4
Tiểu luận môn học Hệ phân tán
Chương 1
HỆ TIN HỌC PHÂN TÁN
1. Quá trình phát triển hệ thống tin học
Hệ tin học có thể bao gồm các thành phần cơ bản như phần cứng, hệ điều
hành, các chương trình ứng dụng và người sử dụng…Các thiết bị phần cứng bao
gồm bộ xử lý trung tâm, bộ nhớ, và các thiết bị ngoại vi đóng vai trò là một trong
hai loại tài nguyên cơ sở của hệ thống tin học. Các chương trình ứng dụng là thành
phần tiếp theo sau hệ điều hành ví dụ như các phần mềm ứng dụng.
Người sử dụng có thể là các nhà chuyên môn, các máy tính, các hệ tự động

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ế.’…
Hệ thống thời gian thực với hệ điều hành tiêu biểu là hệ tự động hoá điều
khiển lò luyện thép.
Vào năm 1974, xuất hiện mạng Internet toàn cầu là mạng ARPANET với giao
thức NCP. Tuy nhiên, khi giao thức TCP/IP được xây dựng bởi Vint Cert và Robert
Kahn thì khái niệm mạng của các mạng mới được hình thành. Và đến năm 1990 thì
mạng Internet phát triển vượt bậc với những kết quả mà chúng ta có được như ngày
hôm nay.
2. Hệ tin học phân tán
2.1. Khái niệm hệ tin học phân tán
Hệ tin học phân tán hay gọi tắt là hệ phân tán là một hệ thống xử lý thông tin
bao gồm nhiều bộ xử lý hoặc các bộ vi xử lý được đặt ở xa tại các vị trí khác nhau
và được liên kết với nhau thông qua các phương tiện viễn thông dưới sự thống nhất
của hệ điều hành
Hệ tin học phân tán là một hệ thống không chia sẽ bộ nhớ và đồng hồ. Các
tính toán trong hệ tin học phân tán có thể được thực hiện trên nhiều bộ xử lý hay vi
xử lý của hệ thống đa bộ xử lý. Do đó hệ thống tin học phân tán đòi hỏi hệ thống
của mình phải trang bị bộ nhớ cục bộ. Các bộ xử lý trao đổi thông tin thông qua các
đường truyền khác nhau như cáp mạng chuyên dụng, bus trao đổi, đường điện thoại,
cáp quang hoặc có thể là sóng…
Không như các máy tính đơn lẽ, mạng máy tính là tập hợp các thiết bị đầu
cuối được nối với nhau bởi hệ thống đường truyền, những đường truyền nối với các

3. Tin cậy
Một trạm trong hệ bị sự cố không làm cho toàn hệ ảnh
hưởng mà ngược lại, công việc đó được phân cho các
trạm khác đảm nhận. Ngoài ra, trạm bị sự cố có thể tự
động phục hồi lại trạng thái ban đầu trước khi có sự cố
hay trạng thái ban đầu của nó
4. Tăng tốc
Đây là khái niệm mới về phân tán tải. Một tính toán lớn
nào đó nếu chỉ sử dụng một trạm thì thời gian cho kết
quả lâu. Tính toán này được chia nhỏ và thực hiện song
song trên các trạm. Điều này cũng cần thiết đối với các
trạm quá tải
Một trong những tư tưởng lớn của hệ phân tán là phân tán hoá các quá trình xử
lý thông tin và thực hiện công việc đó trên các trạm xa nhau. Đó là những cơ sở căn
Học viên: Nguyễn Nương Quỳnh
7
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 môn học Hệ phân tán
bản cho việc xây dựng các ứng dụng lớn như thương mại điện tử, giáo dục điện tử,

2.4. 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ý .
Học viên: Nguyễn Nương Quỳnh
8
Tiểu luận môn học Hệ phân tán
Vấn đề lập trình và thực hiện ứng dụng phân tán mô tả các phương pháp điều
khiển thực hiện chương trình phân tán, vấn đề định danh và đặc biệt là vấn đề cấu
trúc truy vấn tổng quát trong hệ.
Trình tự và đồng bộ các tiến trình chỉ ra cho ta các vấn đề đồng bộ có thể dẫn
đến phải thiết chế một trật tự tổng quát của các sự kiện diễn ra trong hệ.
Cung cấp tài nguyên cho thấy được những khó khăn đang gặp phải trong quá
trình phân tán dữ liệu và cung cấp các tài nguyên vật lý và logic. Trong không gian
phân tán ta có thể nắm bắt được ngay lập tức trạng thái tổng quát của việc cung cấp
tài nguyên và cũng khó có thể tránh được tình trạng bế tắc diễn ra.
Thời hạn truyền thông tin trong hệ không giống nhau. Các thông điệp có thể bị
mất trong quá trình chuyển tải, các thông điệp có thể truyền kép và hệ thống có thể
rơi vào sự cố.
Một hay nhiều máy tính cấu thành của hệ phân tán có thể bị sự cố và hoạt
động của toàn bộ hệ sẽ trở nên kém hiệu quả
Không có phương pháp xử lý duy nhất cho các vấn đề về độ tin cậy của hệ
phân tán, các phương pháp nhằm tăng độ tin cậy chủ yếu nhằm vào các vấn đề
chống dư thừa, tái lập cấu hình, phát hiện sự cố,….
Học viên: Nguyễn Nương Quỳnh
9
Tiểu luận môn học Hệ phân tán
Chương 2
TÀI NGUYÊN VÀ CHIẾN LƯỢC CUNG CẤP TÀI NGUYÊ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,…
Học viên: Nguyễn Nương Quỳnh
10
Tiểu luận môn học Hệ phân tán
1.3. Tải
Thuật ngữ tải là tập hợp các yêu cầu phục tùng các quy tắc của một bộ cung
cấp. Các tham số đặc trưng cho tải là:
1. Số lượng các yêu cầu được cung cấp tài nguyên.
2. Bản chất của các yêu cầu.
3. 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 theo các quy tắc nhất định.
Có hai điều kiện làm cho tiến trình mất khả năng sử dụng tài nguyên đã được
cung cấp trước đó. Đó là:
STT Tên gọi Điều kiện
1 Giải phóng Tiến trình phát tín hiệu ngừng sử dụng tài nguyên
2 Thu hồi
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.
Trong hệ phân tán, 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 dùng chung được xem là tuyệt vời, nếu không xảy ra bế tắc hay thiếu
thốn tài nguyên vĩnh viễn.
1.4. Bế tắc và vấn đề thiếu tài nguyên vĩnh viễn
Bế tắc (hay còn gọi là khoá tương hỗ) là sự kẹt chéo lẫn nhau có tính chất
sống còn của các tiến trình. Bế tắc diễn ra khi hai tiến trình đang sử dụng tài nguyên
lại phát yêu cầu về nhu cầu sử dụng tài nguyên mà tiến trình kia còn đang sử dụng.
Ví dụ xét đồ thị cung cấp tài nguyên như hình vẽ sau đây:

chờ tài nguyên T
3
được
giải phóng bởi Tr
1
trạm Tr
3
. Thêm vào đó, tiến trình Tr
1
chờ tiến trình Tr
2
giải phóng
T
1
. Ta có hai chu trình kín trong đồ thị trên là:
Học viên: Nguyễn Nương Quỳnh
11
Tiểu luận môn học Hệ phân tán
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 vừa nêu
có nhiều, như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.
2. Các chiến lược 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 hủy 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 được đáp ứng của một số tài nguyên (ví dụ như sự sụp đổ của hệ đa chương
trình). Để tránh hiện tượng đó, bộ cung cấp tài nguyên cần phải bảo đảm chức năng
điều khiển.
Cung cấp tài nguyên cho chúng ta thấy những khó khăn gặp phải trong quá
trình phân tán dữ liệu và cung cấp các tài nguyên vật lý và logic. Trong không gian

2
-Tr
3
-T
3
-Tr
1
Chu trình 2: Tr
3
-T
3
-Tr
2
-T
2
-Tr
3
Tiểu luận môn học Hệ phân tán
2.1. Chiến lược 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 và 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:
- 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.
Truy cập bởi 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 (client).

D
Sn

S2
S1

T
Hình 3: Đồ thị truy cập tài nguyên bằng một chương trình trực duy nhất
Các quy tắc này được khởi sự bằng hai cách bởi các tiến trình khách. Hình 3
cho thấy việc truy cập được tiến hành bằng một chương trình trực duy nhất.
Trong cách thứ hai, việc truy cập được tiến hành trực tiếp với các server và thể
hiện bằng hình 4 sau đây:
S1
Tr1
S2
Tr2
Sn
Trn

T
KiÓm tra truy
cËp
Hình 4: Truy cập trực tiếp vào các server
Trong hình 3, ta thấy một tiến trình đánh thức D duy nhất sau hàng đợi làm
nhiệm vụ phân phối các yêu cầu cho các server cục bộ. Các tiến trình khách không
biết server. Ngược lại trong hình 4, các máy server đều được các tiến trình khách
biết trước.
Việc triển khai đặc biệt đối với các server có liên quan đến việc phối hợp
chúng với các điểm của một mô-đun quản lý các tài nguyên như chương trình
monitor chẳng hạn.

then cài mo_then(e).
Như vậy, có thể xảy ra rủi ro do bế tắc, khi các tiến trình truy cập loại trừ được
phân phối mà không có khả năng thu hồi và các tiến trình cần phải sử dụng đồng
thời nhiều tài nguyên.
Ví dụ: Giả sử có hai tiến trình p và q cùng sử dụng hai tài nguyên e
1
và e
2
,
chúng được mô tả trong đoạn chương trình sau đây:
Tiến trình p Tiến trình q
p1: v_loai_tru_th(e1) q1:v_loai_tru_th(e2)
p2: v_loai_tru_th(e2) q2:v_loai_tru_th(e1)
Nếu các yêu cầu được thoả mãn theo trình tự p
1
, q
1
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ể giải quyết bằng cách dự báo và vòng tránh (gọi chung 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ế

. Như thế, trật tự duy nhất của việc thu hồi các tài
nguyên được xác định sẽ tránh bế tắc. Phương pháp này dẫn đến các tiến trình cần
thu hồi trước (tạm ứng) các tài nguyên của chúng và do vậy làm giảm khả năng thực
hiện song song của hệ.
Khi các tiến trình phát triển và thông báo trước về nhu cầu cực đại các tài
nguyên, thì các phương pháp mềm dẻo hơn có thể được sử dụng.
Phương pháp phát hiện và chữa trị
Phương pháp Holt sử dụng một đồ thị trạng thái định hướng mà các nút là các
tài nguyên hay tiến trình. Các cung tiến trình-tài nguyên biểu hiện các yêu cầu
không được thoả mãn, các cung tài nguyên-tiến trình thể hiện các cung cấp đã được
thực hiện. Nếu có sự hiện diện của vòng lặp khép kín trong đồ thị này thì đó chính
là biểu hiện của tình trạng bế tắc.
Sau khi đã phát hiện bế tắc, vấn đề chữa trị được đặt ra, nhưng các phương
pháp này rất phức tạp, tốn kém. Hiện nay, thuật toán chữa trị đang được các nhà
chuyên môn quan tâm nghiên cứu và phát triển.
Thực tế, trong các hệ điều hành người ta thường sử dụng:
- Hoặc là các phương pháp dự phòng đơn giản như cung cấp tổng quát tất cả
các tài nguyên hay phương pháp nhóm sắp xếp.
- Hoặc là các phương pháp phát hiện thường rất cồng kềnh, khắc phục nó đòi
hỏi phải loại bỏ hoàn toàn các tiến trình và khởi sự chúng trở lại từ đầu. Điều đó đòi
hỏi phải lưu trữ ngữ cảnh theo từng chu kỳ hết sức phức tạp và tốn kém bộ nhớ.
Việc phát triển các cơ sở dữ liệu (CSDL) đã làm cho hệ phân tán có thêm các
hoạt động mới về vấn đề bế tắc. Nhằm tăng khả năng thực hiện song song, các then
thường mang dữ liệu rất sơ đẳng. Điều đó làm tăng số lượng tài nguyên cần quản lý.
Một mặt, các phương pháp thông báo không phải lúc nào cũng sử dụng được bởi vì
các tài nguyên cần cho một giao dịch thông thường chỉ được xác định trong qúa
trình thực hiện.
Phương pháp đường tránh thường xuyên tỏ ra thích nghi được với CSDL đã
được giới thiệu bởi Chamberlin. Mỗi một giao dịch có một điểm check-point (điểm
không trở về), theo đó các cập nhật thông tin trên CSDL là không thể quay trở lại

STT
Giải pháp
1
Ta duy trì tại mỗi trạm một bản sao trạng thái tài nguyên tổng quát. Trong
trường hợp này, cần phải bảo đảm gắn bó hữu cơ của các bản sao.
2
Ta phân tán biểu hiện trạng thái trên các trạm, mỗi một trạm chỉ có trạng
thái của các tài nguyên cục bộ của mình. Các quyết định được đưa ra trên
các trạm khác nhau cần phải được phối hợp theo kiểu sao cho dữ liệu của
việc cung cấp phải được gắn bó với nhau.
3
Một phương pháp đầy ấn tượng là nhóm sắp xếp nhằm bảo đảm cho tất cả
các yêu cầu tài nguyên xuất phát từ các tiến trình đều được các bộ cung cấp
khác nhau theo một trật tự nhất định cố định từ trước.
Học viên: Nguyễn Nương Quỳnh
17
Tiểu luận môn học Hệ phân tán
Các phương pháp khác mang tính năng động cao cho phép ra các quyết định
cung cấp tài nguyên xuất phát từ quan điểm từng phần (ngược với toàn phần) của
trạng thái tài nguyên.
Các phương pháp cung cấp sử dụng trạng thái tổng quát
Vấn đề quan trọng được đặt ra là tại sao có thể áp dụng thuật toán dự phòng bế
tắc của hệ tập trung vào môi trường phân tán theo kiểu duy trì trên mỗi trạm một
bản sao trạng thái cung cấp của tất cả các tài nguyên.
Nội dung của các bản sao trên các trạm của hệ có thể phản ánh trong mỗi bảng
sau đây:
STT Nội dung của các bản sao
1 Tập hợp của tất cả các tài nguyên còn chưa được cung cấp
2 Tập hợp các tài nguyên đã được cung cấp
3 Đối tượng đang chiếm giữ tài nguyên

Ta định nghĩa một quan hệ gọi là phụ thuộc thế năng giữa hai giao dịch T
j
và
T
k
, ký hiệu là T
j
> T
k
, điều đó nói lên rằng T
j
chậm hơn T
k
. Nếu T
j
> T
k
nghĩa là tồn
tại ít nhất một tài nguyên bị cài then bởi T
j
và là thành phần thuộc thông điệp của
T
k
. Quan hệ này có thể biểu diễn bằng đồ thị G, biến thiên theo thời gian gọi là đồ
thị các xung đột thế năng. Tồn tại vòng lặp trong đồ thị này sinh ra bế tắc.
Ví dụ: Đánh giá ba giao dịch T
1
, T
2
, T

không tránh khỏi.
e2
T1
e1
e3
T3
T2
Hình 5: Vòng khép kín trên đồ thị
Để tránh bế tắc diễn ra, ta duy trì tại mỗi trạm một bản sao của đồ thị G, tài
nguyên chỉ được cung cấp nếu việc cung cấp đó không phát sinh vòng lặp trên đồ
thị này.
Mỗi một thông cáo, thông điệp hay khuyến nghị giải phóng đều nhận một dấu,
rồi phát ra cho tất cả các trạm. Để cập nhật bản sao của mình về đồ thị G, mỗi trạm
xử lý các thông điệp mà nó nhận được trong một trật tự chặt chẽ được xác định bởi
dấu căn cứ.
Học viên: Nguyễn Nương Quỳnh
t
11
: a_loai_tru_th(e1,
e2)
…
…
t12: v_loai_tru_th(e1)
…
…
t13: v_loai_tru_th(e
2
)
t21: a_loai_tru_th(e2,
e3)

, nghĩa là tồn tại ít nhất một tài nguyên bị cài then bởi T
j
và là thành phần
thuộc thông điệp của T
k
.
- Một quan hệ gọi là chặn thế năng giữa 2 giao dịch T
j
và T
k
, kí hiệu
T
j<>
T
k
, nghĩa là tất cả tài nguyên thuộc tập hợp theo yêu cầu của thông điệp T
k
đều bị cài then bởi T
j
. Hai quan hệ này có thể biểu diễn bằng đồ thị G, biến thiên
theo thời gian gọi là đồ thị các xung đột thế năng. Nếu tồn tại vòng lặp trong đồ
thị G này thì sẽ sinh ra bế tắc.
- Sự xung đột giữa hai giao dịch T
j
và T
k
là sự nhận thông điệp yêu cầu cung
cáp tài nguyên của T
j
và T

1
, R
2
và R
3
được bố trí trên các trạm tương
ứng S
1
, S
2
và S
3
. Nếu trạm S
i
chỉ nhận các thông cáo tương ứng với tài nguyên mà
nó quản lý, thì nó chỉ duy trì đồ thị Gi .
(G
i
hình ảnh thu được của G cho các giao dịch đã phát thông cáo).
Học viên: Nguyễn Nương Quỳnh
t
11
: a_th(R
3
, R
1
, R
2
)
…

: v_loai_tru_th(R
3
)
t
31
: a_th(R
2
, R
1
)
…
t
32
: v_loai_tru_th(R
2
)
…
t
33
: v_loai_tru_th(R
1
)
20
Tiểu luận môn học Hệ phân tán
Giả sử các lệnh thực hiện theo trình tự: t
11
- t
21 -
t
31 -

s
s
e
Tại trạm S
2
có đồ thị G
2
:
T3
T1R2
e
e
Tại trạm S
3
có đồ thị G
3
:
Rõ ràng, thông qua
ba đồ thị trên đây, ta
không phát hiện được
mạch khép kín có thể dẫn
đến tình trạng bế tắc.
Nhưng, nếu ở hệ tập trung
hay trạng thái không từng phần, ta có đồ thị sau:
Học viên: Nguyễn Nương Quỳnh
21
T1
T2
R3
e

của đồ thị một quan hệ 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ẽ chỉ ra G có được
tình trạng không vòng lặp như thế nào. Đầu tiên chúng ta bắt đầu chỉ ra sự tồn tại
của vòng lặp trong G kéo theo sự tồn tại của vòng lặp có trong ít nhất một G’
i
. Kí
hiệu T
j
>>T
k
hoặc T
j
<>
T
k
là quan hệ trật tự từng 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ệ >> hoặc
<>
xác định
bởi:

Giả sử rằng G có vòng lặp bao gồm một tập hợp của n giao dịch được đánh số

<>
T
k
hoặc
Tiểu luận môn học Hệ phân tán
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 cáo T
p
thì G’
i
chứa vòng lặp.
1.3. Thuật toán
Thuật toán dự phòng được triển khai như sau:
Bước Triển khai
1
Nhận yêu cầu cung cấp tài nguyên từ giao dịch T
i
. Phân biệt thông điệp đã nhận
là yêu cầu cung cấp tài nguyên theo kiểu loại trừ hay chia sẻ (tức là đã phân
nhóm giao dịch).
2 Kiểm tra khoảng cách D giữa hai giao dịch. (Nếu D=0 thì thông báo xung đột).
3
Kiểm tra tài nguyên theo yêu cầu của giao dịch và gởi thông điệp tương thích
cho giao dịch.
4
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

2
-R
3
-P
1
được thành lập trong G. Lúc này yêu cầu vẫn được
chấp nhận, vì giao dịch T
1
>>T
2
.
Yêu cầu t
22
: v_chia_se_th(R
1
) được chấp nhận, vì tài nguyên này được T
1
truy
cập theo kiểu chia sẻ nên hoàn toàn cho giao dịch khác truy cập chia sẻ.
Yêu cầu t
32
: v_loai_tru_th(R
2
) bị từ chối vì nó tạo ra vòng lặp trên S
2
.
(Nhưng cần lưu ý rằng nếu trật tự giao dịch theo dạng T
1
, T
2

2. Thuật toán phát hiện bế tắc - Thuật toán Menasce
Khi các tài nguyên được sử dụng bởi giao dịch được xác định theo kiểu động
trong quá trình thi hành giao dịch, các phương pháp dự phòng bế tắc dựa trên nền
tảng các thông điệp không còn phù hợp được nữa. Lúc này, ta phải sử dụng các
phương pháp phát hiện và chữa trị.
Phương pháp được mô tả bởi Menasce sẽ được trình bày ở đây. Phương pháp
này đặt ra vấn đề sử dụng một đồ thị các tranh chấp mà việc kiểm tra các tranh chấp
đó cho phép phát hiện bế tắc.
Tương tự như thuật toán Lomet vừa nêu, mỗi một trạm quản lý các tài nguyên
riêng của mình và việc phát hiện chỉ dựa vào thông tin cục bộ. Các trạm khởi sự các
giao dịch bị treo được đề phòng phát sinh bế tắc (mà bế tắc này có thể phát hiện tại
một trạm nào đó) cần phải đề ra các bịên pháp chữa trị cho mình.
2.1. Các định nghĩa
Ta cần xác định trong mọi thời điểm giữa hai giao dịch T
j
và T
k
quan hệ chặn
trực tiếp như sau:
T
j
>T
k
⇔ Tồn tại ít nhất một tài nguyên bị cài then bởi T
j
và
yêu cầu bởi T
k
nhưng không được đáp ứng.
Và quan hệ chặn hiệu lực là:

) là các giao dịch có nguồn gốc từ sự chặn từ T
k
.
Tại một thời điểm cho trước, đồ thị các xung đột hữu hiệu sinh ra các quan hệ
chặn tồn tại giữa các giao dịch của hệ. Ta ký hiệu B(T
k
) là tập hợp các giao dịch bị
chặn do T
k
, có nghĩa là các giao dịch có thể đạt được bằng cách chạy khắp các cung
xuất phát từ T
k
.
Ví dụ:
Học viên: Nguyễn Nương Quỳnh
24
Tiểu luận môn học Hệ phân tán
Cho đồ thị các xung đột hữu hiệu như sau: Với các giao dịch không bị chặn là
T
3
, T
4
, T
5
.
T1
T2
T3
T4
Ta có:

)
≠

∅
{Tồn tại vòng lặp}
Nếu ta không muốn duy trì trên mỗi trạm một bản sao của đồ thị tổng quát thì
cần phải xây dựng một ảnh cục bộ cho phép đánh giá các điều kiện vừa nêu trên.
Điều đó sẽ được thực hiện trong giải thuật Menasce sau đây.
2.2. Thuật toán
Ta ký hiệu S(T
k
) là trạm nguồn của giao dịch T
k
. Để cho mỗi giao dịch T
k
,
trạm S(T
k
) duy trì các tập hợp B(T
k
) và E(T
k
). Việc cập nhật E(T
k
) cần phải được
biểu hiện trên tất cả các trạm nguồn của các giao dịch thuộc B(T
k
). Thực tế giao
dịch chặn T
k

1.Trên trạm S(T
j
) nguồn của giao dịch chặn T
j
, ta thêm T
k
vào tập hợp B(T
j
) và
kiểm tra rằng không phát sinh bế tắc, nghĩa là: B(T
j
)
∩
E(T
j
) =
∅

Ta gửi tiếp thông điệp (l,k) về phía các trạm nguồn của các giao dịch T
l
và T
j
nhằm cho phép các trạm S(T
l
) cập nhật các tập hợp E(T
l
), B(T
l
) của các giao dịch bị
Học viên: Nguyễn Nương Quỳnh