BỘ GIÁO DỤC VÀ ĐÀO TẠO
BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG
ĐẠI HỌC ĐÀ NẴNG


VAI TRÒ CỦA TRẬT TỰ HÓA VÀ
VAI TRÒ CỦA TRẬT TỰ HÓA VÀ
VẤN ĐỀ GẮN BÓ DỮ LIỆU
VẤN ĐỀ GẮN BÓ DỮ LIỆU
BÁO CÁO TiỂU LUẬN
BÁO CÁO TiỂU LUẬN
HỆ TIN HỌC PHÂN TÁN
HỆ TIN HỌC PHÂN TÁN
Thực hiện : Phan Thị Thanh Tuyền
Giảng dạy: TS. LÊ VĂN SƠN
Đà Nẵng, 07- 2014
ĐỀ TÀI :
Vai trò của trật tự dữ liệu
Vai trò của trật tự dữ liệu
Giả sử rằng xác định một trật tự giữa các sự
kiện của HPT nhờ vào quan hệ kí hiệu là  gọi là
“có trước” hay “ở ngay trước”.
Thỏa mãn các ràng buộc sau:
+ Nếu A và B là hai sự kiện của cùng một
trạm và nếu A được thực hiện trước B thì theo trật
tự của trạm ta có: AB.
+ Nếu A là phát thông điệp và B là thu của
thông điệp này thì ta có: AB.
Vai trò của trật tự dữ liệu
Vai trò của trật tự dữ liệu


Ví dụ 1
Ví dụ 1
A1
A2
A3
A4
A5
B1
B2
B3
B4
B5
t
Trật tự biểu diễn:
Trật tự từng phần:
A1A2A3A4A5
B1B2B3B4
Trao đổi thông điệp
A1B2 và B3A4
Chuyển qua
A1A2B2B3B4
B1B2 B3 A4A5
A1A2B2B3A4 A
5
1.2 Trật tự hoá các tác động
Cho một tập các giao dịch M = (T1, T2, ,Tn) được thực
hiện bởi các tiến trình độc lập p1, p2, , pn.
Thực hiện tuần tự là:
+ Thực hiện các giao dịch của M theo kiểu nối đuôi

nhau và tuân thủ một trật tự nào đó.
+ Sự gắn bó dữ liệu của hệ được bảo toàn bằng việc
thực hiện riêng biệt từng giao dịch.
+ Trật tự nội tại của từng giao dịch gồm tất cả các
tác động tạo nên giao dịch M; một tác động chỉ xuất hiện
một lần.
Một dãy các tác động như vậy được gọi là trật tự hóa
của tập hợp các giao dịch M.

Ví dụ 2: Quản lý các tài khoản tại một ngân hàng.
Ví dụ 2: Quản lý các tài khoản tại một ngân hàng.


Mỗi một người mở tài khoản tại ngân hàng sẽ được lưu trữ
Mỗi một người mở tài khoản tại ngân hàng sẽ được lưu trữ
trong một bản ghi của CSDL. Tài khoản luôn luôn lớn hơn hoặc
trong một bản ghi của CSDL. Tài khoản luôn luôn lớn hơn hoặc
bằng 0
bằng 0
- Phép toán chuyển khoản thể hiện bằng cách trừ đi một giá trị P
- Phép toán chuyển khoản thể hiện bằng cách trừ đi một giá trị P
nào đó (P=500) ở một tài khoản và cộng chính giá trị đó vào tài
nào đó (P=500) ở một tài khoản và cộng chính giá trị đó vào tài
khoản khác.
khoản khác.
- Kí hiệu: - A là số dư TK bị trừ đi (A=1000)
- Kí hiệu: - A là số dư TK bị trừ đi (A=1000)


- B là số dư TK cộng vào (B=2000).

- B là số dư TK cộng vào (B=2000).


- U: giao dịch mới
- U: giao dịch mới


- T: các giao dịch chuyển khoản
- T: các giao dịch chuyển khoản


- t: tỉ lệ lợi nhuận tiền gửi (t=0.01)
- t: tỉ lệ lợi nhuận tiền gửi (t=0.01)




Ba trật tự hóa có thể là S1, S2, và S3
Ba trật tự hóa có thể là S1, S2, và S3
Vai trò của trật tự dữ liệu
Vai trò của trật tự dữ liệu
Giao dịch loại T
A:=A-P
A:=(1+t)xA
B:=(1+t)*B
B:=B+P
Giao dịch loại U
Giao dịch loại T
A:=A-P
A:=(1+t)xA

B:=(1+t)*B
B:=B+P
Giao dịch loại U
Giao dịch loại T
A:=A-P
A:=(1+t)xA
B:=(1+t)*B
B:=B+P
Giao dịch loại U
TT
S1
S2
S3
A:=500
A:=505
B:=2020
B:=2520
A:=500
A:=505
B:=2500
B:=2525
A:=500
B:=2500
A:=505
B:=2525
Trật tự hóa S2 có tác dụng tương đương
với trật tự hóa tuần tự S3, trong khi đó trật tự
hóa S1 lại khác.
Tóm lại: Vai trò của trật tự dữ liệu
-

Xác định trật tự giữa các sự kiện trong hệ
-
Tránh tương tranh
-
Tránh xung đột
- Tránh bế tắc.
-
Điều khiển tốc độ đường truyền
2. SỰ GẮN BÓ THÔNG TIN
2. SỰ GẮN BÓ THÔNG TIN
Điều kiện giả định
Điều kiện giả định
-
-
Một tập thông tin có thể được truy cập bởi một
Một tập thông tin có thể được truy cập bởi một
tập các tiến trình.
tập các tiến trình.
- Số lượng thông tin có thể truy cập được và các
- Số lượng thông tin có thể truy cập được và các
tiến trình có nhu cầu thông tin là cố định.
tiến trình có nhu cầu thông tin là cố định.
Hệ này phát triển rời rạc theo thời gian có thể
Hệ này phát triển rời rạc theo thời gian có thể
nhận biết được trạng thái thực của chúng,
nhận biết được trạng thái thực của chúng,
SỰ GẮN BÓ THÔNG TIN
SỰ GẮN BÓ THÔNG TIN
Các điêù
Các điêù



kiện giả định này so với hệ thực tế khác
kiện giả định này so với hệ thực tế khác
nhau như sau:
nhau như sau:
Các
Các
đố
đố
i t
i t
ượng
ượng
và tiến trình thông qua hệ thống
và tiến trình thông qua hệ thống
viễn thông có thể:
viễn thông có thể:
+ Được tạo lập
+ Được tạo lập
+ Được hủy bỏ
+ Được hủy bỏ
+ Được phân tán trên các trạm khác nhau
+ Được phân tán trên các trạm khác nhau
Do vậy ta không xác định được trạng thái của hệ
Do vậy ta không xác định được trạng thái của hệ
-
Hệ thống viễn thông và các tiến trình là các đối
Hệ thống viễn thông và các tiến trình là các đối



tượng có thể xảy ra sự cố kỹ thuật
tượng có thể xảy ra sự cố kỹ thuật
2.2 Tác động và giao dịch
2.2 Tác động và giao dịch
Các đối tượng của hệ quan hệt với nhau bởi tập
Các đối tượng của hệ quan hệt với nhau bởi tập
hợp các quan hệ (ràng bộc toàn vẹn), trạng thái của
hợp các quan hệ (ràng bộc toàn vẹn), trạng thái của
hệ thoả mãn tập hợp các ràng buộc toang vẹn là trạng
hệ thoả mãn tập hợp các ràng buộc toang vẹn là trạng
thái gắn bó.
thái gắn bó.
Vi
Vi
ệc thực hiện các tiến trình phải duy trì cho được
ệc thực hiện các tiến trình phải duy trì cho được
hệ trong trạng thái gắn bó
hệ trong trạng thái gắn bó
(lưu ý rằng trạng thái của hệ chỉ xác định ở mức
(lưu ý rằng trạng thái của hệ chỉ xác định ở mức
quan sát cho trước)
quan sát cho trước)

Ta quan tâm đến hai mức quan sát
Ta quan tâm đến hai mức quan sát
:
:
Stt Mức Giải thích
1 NSD

Tiến trình là một dãy thực hiện các giao dịch
Giao dịch đó là chương trình duy nhất được thực
hiện từ một trạng thái gắn bó này dẫn hệ đến một
trạng thái gắn bó khác.
2 Hệ thống
Mỗi giao dịch được cấu tạo từ một dãy các
tác động được thể hiện như sau.
Nếu 2 tác động A và B thuộc hai giao dịch
khác nhau được thực hiện bởi hai tiến trình thì
hiệu ứng tổng quát của chúng sẽ là hiệu ứng của
dãy (A;B) hoặc là (B;A)
2.3 TRIỂN KHAI GIAO DỊCH TÔN TRỌNG SỰ
2.3 TRIỂN KHAI GIAO DỊCH TÔN TRỌNG SỰ
GẮN BÓ.
GẮN BÓ.
Cho một tập hợp giao dịch M={T1,T2…,Tn}.
Cho một tập hợp giao dịch M={T1,T2…,Tn}.
Một trật tự hóa của tập hợp là việc thực hiện hoàn
Một trật tự hóa của tập hợp là việc thực hiện hoàn
toàn các giao dịch.
toàn các giao dịch.
Một trật tự hóa gắn bó thành công khi áp dụng các
Một trật tự hóa gắn bó thành công khi áp dụng các
ràng buộc trên trật tự thực hiện các tác động.
ràng buộc trên trật tự thực hiện các tác động.
Nguyên lý của phương pháp :
Nguyên lý của phương pháp :
Làm chậm một tác động nào đó cho đến thời
Làm chậm một tác động nào đó cho đến thời
điểm mà sự thực hiện của nó không còn có nguy cơ

điểm mà sự thực hiện của nó không còn có nguy cơ
phá hủy sự gắn bó của trật tự hóa.
phá hủy sự gắn bó của trật tự hóa.
Phương pháp, cơ chế để đảm bảo các giao
Phương pháp, cơ chế để đảm bảo các giao
dịch tôn trọng sự gắn bó thông tin
dịch tôn trọng sự gắn bó thông tin
Cơ chế then cài.
Cơ chế then cài.
+ Then cài loại trừ tương hỗ.
+ Then cài loại trừ tương hỗ.
+ Then cài lựa chọn đối tượng.
+ Then cài lựa chọn đối tượng.
+ Giao dịch hai pha.
+ Giao dịch hai pha.
Giả
Giả
địn
địn
h các đối tượng được phân tán trên nhiều
h các đối tượng được phân tán trên nhiều
trạm nối với nhau qua hệ thống viễn thông, và có thể
trạm nối với nhau qua hệ thống viễn thông, và có thể
trao đổi các thông điệp.
trao đổi các thông điệp.
Giả sử các tiến trình và các phương tiện truyền
Giả sử các tiến trình và các phương tiện truyền
thông là các đối tượng có thể rơi vào sự cố.
thông là các đối tượng có thể rơi vào sự cố.
STT Cơ chế

1
Cho phép sắp xếp một cách tổng quát các tác
động của cùng một giao dịch trên các trạm khác
nhau.
2
Điều khiển các tranh chấp truy cập cục bộ vào
các đối tượng đảm bảo tôn trọng tính toàn vẹn
của các đối tượng truy cập cục bộ này.
3
Có khả năng xử lý các bế tắc và thiếu thốn vô
hạn, hậu quả của việc hủy bỏ các giao dịch.
4
Phục hồi các giao dịch đã hủy bỏ hay xử lý
các sự cố.
Một hệ quản lý tập hợp thông tin phân tán gồm:
Một hệ quản lý tập hợp thông tin phân tán gồm:
Cơ chế xử lý sự cố
Cơ chế xử lý sự cố
STT Phải thực hiện
1 Giao dịch T bắt buộc phải thực hiện
một cách trọn vẹn
2 Nếu có sự cố xảy ra thì phải quay lại
điểm xuất phát.
Muốn thực hiện
Muốn thực hiện
cơ chế xử lý sự cố
cơ chế xử lý sự cố


giao

giao
dịch phải có các đặc tính toàn vẹn như sau:
dịch phải có các đặc tính toàn vẹn như sau:
STT
Phải thực hiện
1
Nếu một tiến trình bị sự cố trước khi kết thúc T
nhưng lại sau các thao tác thay đổi cần thiết của T,
trạng thái của hệ là gắn bó.
2
Nếu một tiến trình bị sự cố trước khi diễn ra các
thay đổi của T, trạng thái của hệ là gắn bó.
3
Nếu một tiến trình bị sự cố giữa các thay đỏi của T,
trạng thái của hệ là không gắn bó.
CÁC THUẬT TOÁN ĐẢM BẢO SỰ GẮN
CÁC THUẬT TOÁN ĐẢM BẢO SỰ GẮN
BÓ THÔNG TIN
BÓ THÔNG TIN
Thuật toán duy trì sự gắn bó tránh bế tắc và thiếu thốn.
Thuật toán duy trì sự gắn bó tránh bế tắc và thiếu thốn.
Nguyên lý:
Nguyên lý:
+ Then cài ngầm định
+ Then cài ngầm định
+ Phát hiện các xung đột.
+ Phát hiện các xung đột.
+ Khẳng định
+ Khẳng định
Thuật toán quản lý nhiều bản sao

Thuật toán quản lý nhiều bản sao
+ Thuật toán đảm bảo sự gắn bó yếu nhờ dấu
+ Thuật toán đảm bảo sự gắn bó yếu nhờ dấu
+ Thuật toán đảm bảo sự gắn bó yếu nhờ bộ tuần tự tuần
+ Thuật toán đảm bảo sự gắn bó yếu nhờ bộ tuần tự tuần
hoàn
hoàn
+ Thuật toán đảm bảo sự gắn bó mạnh
+ Thuật toán đảm bảo sự gắn bó mạnh
PHẦN BÀI TẬP
PHẦN BÀI TẬP
Xét một hệ đa xử lý với bộ nhớ chung, trong đó mỗi một bộ xử lý được trang
bị một bộ nhớ cục bộ hoạt động theo nguyên tắc của bộ nhớ cache. Hệ này quản
lý 3 đối tượng là:
-
Các biến toàn cục, được truy cập bởi nhiều tiến trình
-
Các biến cục bộ chỉ được phép truy cập bởi một tiến trình có nhu cầu.
-
Các hằng chia sẻ được.
Mỗi ngăn nhớ của bộ nhớ chung hay cục bộ đều bao gồm một kí hiệu cho
phép nhận dạng kiểu của đối tượng chứa trong đó. Một đối tượng không thể
thay đổi kiểu. Ta có cơ chế đảm bảo việc loại trừ tương hỗ cho các truy cập vào
bộ nhớ chung.
Hãy cho biết nguyên lý được mô tả bởi thuật toán truy cập vào các loại đối
tượng khác nhau đó với điều kiện duy trì sự gắn bó bằng cách sử dụng ghi tức
thời.

Nguyên lý để đạt được trật tự hoá gắn bó là làm chậm
một tác động nào đó cho đến thời điểm mà sự thực

hiện của nó không còn có nguy cơ phá huỷ sự gắn bó
của trật tự hoá (bằng cách chặn các tiến trình hiện
hành)
Để giải quyết vấn đề này áp dụng thuật toán duy
trì sự gắn bó tránh bế tắc và thiếu thốn
dựa trên
dựa trên
nguyên lý sau:
nguyên lý sau:
Bước 1:
Bước 1:
Then cài ngầm định.
Then cài ngầm định.
Bộ điều khiển cục bộ trên mỗi trạm Si áp đặt cho
Bộ điều khiển cục bộ trên mỗi trạm Si áp đặt cho
các tác động khác nhau trên trạm và diễn biến theo
các tác động khác nhau trên trạm và diễn biến theo
một trật tự hoá hợp thức.
một trật tự hoá hợp thức.
Cần phải ngăn chặn giao dịch Tj (tiến trình Pji mà
Cần phải ngăn chặn giao dịch Tj (tiến trình Pji mà
tiến trình này đang thực hiện trên Si).
tiến trình này đang thực hiện trên Si).
Tất cả diễn ra trên một đối tượng được cài then bởi
Tất cả diễn ra trên một đối tượng được cài then bởi
một giao dịch sử dụng theo kiểu chia sẻ trước khi đọc,
một giao dịch sử dụng theo kiểu chia sẻ trước khi đọc,
theo kiểu loại trừ trước khi ghi.
theo kiểu loại trừ trước khi ghi.
Tất cả các mở then sau khi xong một giao dịch.

Tất cả các mở then sau khi xong một giao dịch.
Bước 2:
Bước 2:
Xác định động các xung đột
Xác định động các xung đột
.
.
Hành vi xung đột xảy ra khi có hai giao dịch
Hành vi xung đột xảy ra khi có hai giao dịch
thực hiện các tác động không tương thích vào một
thực hiện các tác động không tương thích vào một
đối tượng.
đối tượng.
Một xung đột được xác định khi có ý định truy
Một xung đột được xác định khi có ý định truy
cập bởi một giao dịch T2 vào một đối tượng đã
cập bởi một giao dịch T2 vào một đối tượng đã
khoá ngầm định bởi giao dịch T1 theo kiểu không
khoá ngầm định bởi giao dịch T1 theo kiểu không
tương thích.
tương thích.
Không nên để T2 chờ cho đến khi T1 kết thúc
Không nên để T2 chờ cho đến khi T1 kết thúc
mà phải huỷ bỏ một trong hai giao dịch này.
mà phải huỷ bỏ một trong hai giao dịch này.
Bước 3: Khẳng định.
Toàn bộ giao dịch theo hệ số ưu tiên có thể bị
huỷ bỏ, nên cần phải áp dụng có hệ thống một kỹ
thuật khẳng định.
Một giao dịch được huỷ bỏ thì

+ Tất cả các đối tượng mà nó đã được cài then
được mở then.
+ Tất cả các giá trị phải được thay đổi khôi phục
trở lại như cũ.
Trong trường hợp này chỉ có các phép ghi được
thực hiện trên các bản sao đối tượng.
.
.
Một giao dịch bị huỷ thì
Một giao dịch bị huỷ thì
+ Một thông điệp được gửi đi cho tất cả các trạm
+ Một thông điệp được gửi đi cho tất cả các trạm
chứa các đối tượng thay đổi và các bản sao bị huỷ
chứa các đối tượng thay đổi và các bản sao bị huỷ
bỏ.
bỏ.
Trường hợp Giao dịch kết thúc bình thường thì:
Trường hợp Giao dịch kết thúc bình thường thì:
+ Một thông điệp khẳng định được gửi cho tất cả
+ Một thông điệp khẳng định được gửi cho tất cả
các trạm và lúc này các bản sao đối tượng được
các trạm và lúc này các bản sao đối tượng được
phép thay thế các bản gốc.
phép thay thế các bản gốc.
Khi chặn các giao dịch trên các đối tượng chung
Khi chặn các giao dịch trên các đối tượng chung
hoặc bằng then cài ngầm định, ta có thể làm phát sinh
hoặc bằng then cài ngầm định, ta có thể làm phát sinh
các rủi ro và bế tắc.
các rủi ro và bế tắc.

Một bế tắc được loại bằng cách hủy bỏ hoàn
Một bế tắc được loại bằng cách hủy bỏ hoàn
toàn một trong các giao dịch gây nên xung đột, nhưng
toàn một trong các giao dịch gây nên xung đột, nhưng
nếu ta chọn theo kiểu ngẫu nhiên thì gặp rắc rối về kỹ
nếu ta chọn theo kiểu ngẫu nhiên thì gặp rắc rối về kỹ
thuật là một hay một số giao dịch nào đó sẽ rơi vào
thuật là một hay một số giao dịch nào đó sẽ rơi vào
trạng thái chờ vô hạn.
trạng thái chờ vô hạn.
Trong thiết kế hệ thống phân tán, thường sử dụng
Trong thiết kế hệ thống phân tán, thường sử dụng
hai chiến lược chọn lựa giao dịch. Một trong các
hai chiến lược chọn lựa giao dịch. Một trong các
phương pháp ấy gọi là
phương pháp ấy gọi là
phương pháp wait-die
phương pháp wait-die
system.
system.