ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA
TIỂU LUẬN
Môn: HỆ PHÂN TÁN

Đề tài: VẤN ĐỀ NHIỀU BẢN SAO VÀ
CÁC THAO TÁC ĐỌC, CÁC THAO TÁC CẬP NHẬT

Giáo viên hướng dẫn: PGS.TS LÊ VĂN SƠN
Học viên thực hiện : Trần Đình Truyền
03/23/15
Chương I. Mở đầu về hệ tin học phân tán
I.1 Giới thiệu hệ tin học phân tán
I.1.1 Định nghĩa
I.1.2 Vấn đề trỏ thông tin
I.2 Hệ thống nhiều bản sao
I.2.1 Thuật toán cung cấp cho hệ phân tán
I.2.2 Sắp xếp kiểu đóng dấu
I.2.3 Phân tán biểu hiện trạng thái và chức
năng cung cấp
Chương II. Giải quyết vấn đề nhiều bản sao
II.1 Vấn đề nhân bản các đối tượng dữ liệu

II.2 Sơ lược thuật toán quản lý nhiều bản sao
II.2.1 Cơ chế then cài
II.2.2 Xử lý các sự cố
II.2.3 Thuật toán đảm bảo sự gắn bó yếu nhờ dấu

+ 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.
+ Cơ sở căn bản cho việc xây dựng các ứng dụng:
=>thương mại điện tử, giáo dục điện tử,
I.1.2 Vấn đề trỏ thông tin
- Thời hạn truyền một thông điệp là hiệu số giữa thời điểm
nhận và thời điểm truyền - là đại lượng biến thiên.
- Ở cặp máy này khác với ở cặp máy khác. Từ đó ta có 2 hệ
quả sau đây:
1) Ở một thời điểm cho trước, một bộ xử lý đang thực hiện
trên một máy chỉ có thể biết được trạng thái gần đúng của các
máy khác.
2) Trật tự nhận các thông điệp trên các máy nhận có thể
không giống trật tự phát của chính các thông điệp đó.

Các máy trên mạng có thể bị sự cố và các thông điệp có
thể bị mất. Giải pháp cho vấn đề này là máy phát đánh số
thứ tự tất cả các gói thông tin gửi đi kèm theo các số đó cho
máy nhận. Nếu máy phát không đánh số thì máy nhận sẽ
không xác định được. Ta có hệ quả ba là:
3) Hai máy giống nhau chứa thông tin hoàn toàn giống
nhau lại không bao giờ giống nhau về mặt trạng thái.
Từ những vấn đề nêu trên, ta rút ra các đặc tính tổng
quát của hệ phân tán:
i) Thời gian truyền thông điệp là một biến với các giá trị
khác nhau, giá trị này có thể rất lớn.
ii) Tần suất xuất hiện các sự cố trong khi vận hành lớn.
iii)Việc truy cập tài nguyên, kích hoạt các tiến trình trong
mạng không thể thực hiện bởi một thiết bị duy nhất, mà chức
năng này phải được phân tán trên nhiều máy trên mạng.

Vì sự ổn định và hiệu quả mà ta phải phân tán chức năng
cung cấp trên nhiều trạm khác nhau. Sự hoạt động gắng bó với
nhau giữa các chương trình cung cấp là rất cần thiết để bảo
đảm cho hoạt động cung cấp được hoàn toàn chính xác.
Một sự hoạt động gắn bó dữ liệu của các chương trình cung
cấp phân tán quản lý trên cùng một tập hợp các tài nguyên chỉ
đạt được nếu tuân thủ các nguyên tắc sau:
i) Các bộ cung cấp bắt buộc phải thực hiện cùng một giải thuật
ii) Các bộ cung cấp đều nhận tất cả các thông điệp phát đi từ
các tiến trình.
iii) Các thông điệp phải được xử lý cùng một trật tự như nhau
trong các chương trình cung cấp. Trật tự duy nhất trên tập
hợp các thông điệp của hệ, và trật tự được thực hiện thông qua
việc hợp lực giữa các tiến trình cung cấp hay tiến trình phát
thông điệp.I.2.2 Sắp xếp kiểu đóng dấu
Trạm phát được gắn một giá trị gọi là dấu. Giá trị này có
tính chất thời điểm cho trạm phát thông tin và dựa vào đồng
hồ lô gích cục bộ của chính trạm.
I.2.3 Phân tán biểu hiện trạng thái và chức năng cung cấp.
Phân tán biểu hiện trạng thái và chức năng cung cấp, có các giải
pháp có thể:
i) 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.
ii) 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á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.

cb
B
cb
L
Bé xö lý
Bé nhí côc bé
Bé nhí chung
(e)
(e)
HÖ thèng viÔn th«ng
L
M¸y client
M¸y server
Trong trường hợp này, một
đối tượng được đưa vào trên
một trạm xác định và được
quản lý bởi một server cục bộ
trên trạm này. Khi một tiến
trình ở xa muốn sử dụng đối
tượng, nó phải bắt đầu bằng
yêu cầu server cho một bản sao
thông qua hệ thống viễn thông.
Sau khi sử dụng xong, tiến trình
phải gửi lại cho server một
phiên bản đã được sửa đổi của
đối tượng
Hệ truy cập từ xa thông qua máy server

Trường hợp 2 Tính cân đối giữa các người sử dụng tài nguyên thông tin của mạng
L

1) Khi chỉ tồn tại một bản tập trung đặc quyền, ta có
thể đặt ra rằng việc thay đổi đối tượng thực hiện trên một
trong các bản sao sẽ được sao lại ngay lập tức vào bản
chính. Đó chính là trường hợp ghi tức thời và các cập
nhập đều gắn bó. Với các phương pháp ghi khác, ngược
lại, các thay đổi tương ứng của một bản sao đối tượng
cục bộ chỉ được sao lại trên bản chính khi thuật toán thay
thế được thực hiện nhằm cung cấp lại các bản ghi bị
chiếm bởi bản sao cục bộ đó.
2) Khi không tồn tại bản đặc quyền, ta có thể gặp các
trường hợp không gắn bó thông tin.
Trường hợp thứ hai làm phát sinh hai yêu cầu mới:

i) Toàn bộ giao dịch thay đổi bản sao của đối
tượng cần phải chép lại càng sớm càng tốt thay đổi đó
trên tất cả các bản sao khác. Trong khi thực hiện giao
dịch, không có bất kỳ sao chép nào khác được thực
hiện. Sau khi thực hiện xong, tất cả các bản sao hoàn
toàn giống nhau.
ii) Việc cập nhật tức thời (theo hệ tập trung) của
tất cả các bản sao là không cần thiết
II.2 Thuật toán quản lý nhiều bản sao
Thuật toán cho phép sao lại các thay đổi của một
đối tượng trên các bản sao khác nhau như sau:

II.2.1 Cơ chế then cài
Một giao dịch nào đó đang thực hiện phép then cài
trên một đối tượng muốn giành quyền sử dụng đối tượng
này theo một vài kiểu truy cập nhất định. Cơ chế then cài
gán hay không gán quyền truy cập này căn cứ vào quy tắc

II.2.2 Xử lý các sự cố
Một cơ chế cho phép duy trì gắn bó trong môi trường
phân tán có sự cố phải là:

i) Giao dịch T bắt buộc phải được thực hiện một cách
trọn vẹn
ii) Nếu có sự cố diễn ra thì bắt buộc nó phải quay trở lại
điểm xuất phát.
+ 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ó.
+ 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ó.
+ Nếu một tiến trình bị sự cố giữa các thay đổi T,
trạng thái của hệ là không gắn bó.
Các mô hình và giải thuật nghiên cứu phải đảm bảo các đặc
tính toàn vẹn dữ liệu của hệ và tuân thủ theo các giai đoạn thể
hiện trong hình vẽ sau:

Mô tả ba giai đoạn của một giao dịch:
Tr"íc cËp nhËt
Trong cËp nhËt
Sau cËp nhËt
Kh«ng
g¾n bã
G¾n bã
G¾n bã
I
II
1

2
S
n
b
n1
b
n2
b
nm
b
ij
: I =1 n, j=1 m,
trong đó : i chỉ server,
j chỉ bản sao
n là số lượng server được mắc
nối trong mạng.
m là số lượng các đối tượng dữ
liệu.
t
k
, k=1 q, k là trạm A và q là số
trạm được mắc nối.
Hình vẽ. Sơ đồ mô tả hệ thống nhiều bản sao

Những ràng buộc trên các bản sao:
Trên bản sao của một đối tượng:
Nếu ta có n bản sao b1, b2,…, bn của đối tượng b, một trong

)
<Thực hiện các cập nhật và chép chúng vào tất cả
các bản>
Để cho i:=1 đến n thực hiện giai_phong(b
i
)
Nhược điểm căn bản của giải pháp này là rất yếu về
song song giữa các phép toán cập nhật. Ta có thể áp dụng
các ràng buộc toàn vẹn yếu hơn.

II.2.3 Thuật toán đảm bảo sự gắn bó yếu nhờ dấu
II.2.3.1 Nguyên lý

Tập hợp các yêu cầu cập nhật được sắp xếp theo cùng một kiểu
trên tất cả các trạm nhờ cơ chế dấu.

Theo đó mỗi một yêu cầu được phát đi cho tập hợp các trạm.
Trên mỗi trạm, tồn tại một tiến trình Server đảm nhận nhiệm
vụ tiếp nhận các yêu cầu theo trật tự của dấu.

Điều đó cho phép có được một sự gắn bó yếu giữa các bản sao.
II.2.3.2 Triển khai hệ ổn định
Các giao dịch cần xét là các khả năng đọc, ghi hay cập nhật.
Cập nhật được xác định như là một dãy các thao tác đọc và
ghi, thao tác kiểm tra đọc tức thì trạng thái hiện hành của một
bản sao.
Mỗi một server tiếp nhận các yêu cầu ghi đến từ trạm cục
bộ ở thời điểm cho trước. Nó tiếp nhận các yêu cầu và tính
toán trên cơ sở dấu theo tiêu chí lâu nhất.