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ẴNGVAI 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

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:=(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
-
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


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ơ

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

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

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ì

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.