BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG
 
BÁO CÁO TIỂU LUẬN
HỆ TIN HỌC PHÂN TÁN
TÀI NGUYÊN VÀ CHIẾN LƯỢC CUNG CẤP TÀI NGUYÊN
THUẬT TOÁN LOMET VÀ MANASCE
GVHD : PGS. TS. LÊ VĂN SƠN
Học viên : NGUYỄN MINH QUỲNH
Lớp : KHMT.K26
Đà Nẵng, 06/2013
ĐỀ TÀI :
MỞ ĐẦU

Hệ tin học phân tán là một hệ thống xử lý thông tin bao gồm nhiều
bộ xử lý, bộ vi xử lý với bộ nhớ và đồng hồ nhịp độc lập.

Để khai thác có hiệu quả cao nhất của hệ thống thông tin, vấn đề
hàng đầu là phải tính đến các chiến lược cung cấp, khai thác, sử
dụng tài nguyên.
Phần 1: Tài nguyên
và các chiến lược cung cấp tài nguyên

Tài nguyên

Các chiến lược cung cấp tài nguyên
1.1.Tài nguyên_Một số khái niệm

Tài nguyên như là 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ế

Phân tán theo thời gian các yêu cầu tạo ra nó.

Bế tắc (hay gọi là khóa 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.

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.

Ví dụ về sự bế tắc:
1.1.Tài nguyên_Một số khái niệm
T1
T2
T4
T3
Tr1 Tr2 Tr3
1.2.Chiến lược cung cấp tài nguyên

Chiến lược cung cấp tài nguyên duy nhất

Truy cập bằng một tiến trình

Truy cập bằng các tiến trình tương tranh

Chiến lược cung cấp một tập hợp các tài nguyên

Các phương pháp sử dụng trong hệ tập trung


Tr1
S2
Tr2
Sn
Trn

T
KiÓm tra truy
cËp
1.2.2.Cung cấp một tập hợp các tài nguyên

Các phương pháp sử dụng trong hệ tập trung:
A.Phương pháp dự phòng
Các tài nguyên được sắp xếp theo các nhóm con, một tiến
trình nào đó chỉ có thể thu hồi các tài nguyên của nhóm nếu
trước đó nó đã thu hồi tất cả tài nguyên của nhóm cần thiết cho
nó.
B.Phương pháp phát hiện và chữa trị:
Sử dụng đồ 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. Khi phát hiện bế tắc thì vấn đề chữa trị
được đặt ra.
1.2.2.Cung cấp một tập hợp các tài nguyên

Phân tán chức năng cung cấp(mỗi bộ cung cấp chỉ quản lý các đối
tượng cục bộ của mình)
A.Duy trì tính duy nhất của trạng thái tài nguyên:
Tài nguyên được chia sẻ bởi tập hợp các bộ cung cấp và chúng 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 được luân phiên
đóng vai trò của bộ cung cấp các tài nguyên mà mình đang chịu trách nhiệm
quản lý.

Một quan hệ gọi là phụ thuộc thế năng giữa 2 giao dịch Tj và Tk, kí
hiệu Tj>Tk, nghĩa là tồn tại ít nhất một tài nguyên bị cài then bởi Tj
và là thành phần thuộc thông điệp của Tk.

Một quan hệ gọi là chặn thế năng giữa 2 giao dịch Tj và Tk , kí hiệu
Tj <> Tk, 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 Tk đều bị cài then bởi Tj .

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 Tj và Tk là sự nhận thông điệp yêu cầu
cung cấp tài nguyên của Tj và Tk đúng vào cùng một thời điểm. Nếu
ta ký hiệu D là khoảng cách giữa thời điểm nhận thông điệp Tj và Tk
thì sự xung đột sẽ xãy ra khi D = 0.
2.1.2. Thuật toán
2.1.3. Ví dụ minh họa

Xét ba giao dịch T1, T2, T3 sử dụng ba tài nguyên R1, R2, R3, các tài
nguyên được bố trí trên ba trạm tương ứng S1, S2, S3.

Giả sử v_chia_se_th() là phép toán cài then có tính chia sẻ,
v_loai_tru_th() là phép toán cài then có tính loại trừ và a_th() là yêu
cầu cung cấp tài nguyên e hay là phép toán thông điệp:
2.1.3. Ví dụ minh họa

Tại trạm S1 có đồ thị G1:

Tại trạm S2 có đồ thị G2:

thực hiện
t12
:
v_loai_tru_th(R3), v_chia_se_th(R1)
Trong đó có
v_loai_tru_th(R3)
yêu cầu này vào xung đột với thông cáo
a_th(R3)
thực hiện bởi
T2
. Như vậy, cung
T2-R3-T1
đượ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
T1>>T2.

Yêu cầu
t22: v_chia_se_th(R1)
được chấp nhận, vì tài nguyên này được
T1
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
t32: v_loai_tru_th(R2)
bị từ chối vì nó tạo ra vòng lặp trên
S2
.
(Nhưng nếu trật tự giao dịch theo dạng

2.2.1. Các khái niệm

Giả sử
Tk
là một giao dịch bị chặn:

Tập hợp các chặn của
Tk
, ký hiệu:
E(Tk).

Tập hợp các giao dịch bị chặn do
Tk
, kí hiệu:
B(Tk)


Đồ thị các xung đột hữu hiệu chứa vòng lặp nếu và chỉ nếu tồn
tại giao dịch
Tk
mà tập hợp chặn của nó chứa một giao dịch bị
chặn bởi
T
k:

∃ k: B(Tk) ∩ E(Tk) ≠ ∅

{Tồn tại vòng lặp}
Ví dụ: Cho đồ thị các xung đột hữu hiệu như sau:
Các giao dịch không bị chặn là T3, T4, T5.Ta có:

trạm nguồn của giao dịch
Tk
. Việc cập nhật
E(Tk)

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(Tk).
sử
Tk
là một giao dịch bị chặn:

Giả sử Tk đã yêu cầu một tài nguyên e của trạm Si nào đó.

Trên trạm này ta thực hiện các phép toán sau đây:

2.2.2. Thuật toán
Khi nhận một thông điệp (j,k) trên một trạm S, ta thực hiện các động
tác:
1. Trên trạm S(Tj) nguồn của giao dịch chặn Tj, ta thêm Tk vào tập hợp B(Tj) và
kiểm tra rằng không phát sinh bế tắc, nghĩa là:
B(Tj)
∩
E(Tj) =
∅

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 Tl và Tj để cho
phép các trạm S(Tl) cập nhật E(Tl), B(Tl) của các giao dịch bị chặn bởi Tl. Song song
với tác động trên, các thông điệp (l,k) được gửi về trạm nguồn của các giao dịch Tk để
cập nhật E(Tk) của các giao dịch chặn Tk.

T1
T2
T3