Tiểu luận môn Hệ tin học phân tán Trang
Đề số 5:
I. Giải quyết vấn đề nhiều bản sao.
II. Bài toán này dựa vào thuật toán Herman.
Với thuật toán ở phần VI.4.2.2 (theo hệ ổn định), bây giờ, ta chấp nhận
rằng các NSD có thể thực hiện toàn bộ các giao dịch đã nêu.
Hãy cho biết sơ đồ tuần tự của các xử lý sau :
1. Các thao tác đọc.
2. Các thao tác cập nhật.
LỜI NÓI ĐẦU
Những năm gần đây, các thành tựu mới nhất của hệ thống tin học về phần
cứng, phần mềm và các hệ dữ liệu ổn định, tin cậy đã góp phần đáng kể cho sự
phát triển của toàn xã hội nói chung, ngành công nghệ thông tin nói riêng. Xu
hướng toàn cầu hoá thông tin dẫn đến nhu cầu xử lý thông tin ngày một tăng. Hệ
dữ liêu tập trung không còn đáp ứng được hết các yêu cầu đặt ra. Như thương mại
điện tử, chính phủ điện tử. Hệ phân tán đã ra đời để đáp ứng những nhu cầu xử lý
thông tin trên các hệ thống ứng dụng có quy mô rộng lớn đó.
Hiện nay, các chuyên gia công nghệ thông tin đang rất quan tâm đến hệ
phân tán là hệ thống tin học hiện đại, đa dạng, phức tạp và đang trên đà phát triển
nhanh chóng. Việc nghiên cứu hệ đòi hỏi phải có phương pháp hợp lý, mang tính
khả thi cao và được chia cắt thành các phương diện tiếp cận khác nhau. Mỗi
phương diện đều phải có mục tiêu, phương pháp và đối tượng nghiên cứu tương
đối độc lập nhau trên cơ sở nhất quán với mục đích chung của hệ.
Trong giới hạn của một báo cáo tiểu luận kết thúc môn học “Hệ tin học
phân tán”, báo cáo này trình bày những nội dung sau:
I. Giải quyết vấn đề nhiều bản sao
II. Bài toán này dựa vào thuật toán của Herman, theo hệ ổn định. Bây giờ,
ta chấp nhận rằng các người sử dụng có thể thực hiện toàn bộ các giao dịch đã
nêu.
Hãy cho biết sơ đồ tuần tự xử lý các thao tác đọc, các thao tác cập nhật
Được sự giúp đỡ, hướng dẫn tận tình của Thầy giáo PGS.TS Lê Văn Sơn và

Trong hệ phân tán, 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. Ta giả sử rằng, thời hạn đó đủ lớn so sánh với hệ tập

2
Tiểu luận môn Hệ tin học phân tán Trang
trung, là địa lượng biến thiên và ở cặp máy này khác với ở cặp máy khác. Từ đó ta
có hai 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ửu đ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 đinh đượ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 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 mạng 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.
I.2 Hệ thống nhiều bản sao
Trong hệ phân tán, quá trình tổ chức, vận hành các hệ thống cho phép đăng
ký từ xa, từng hệ thống cục bộ đều có lưu trữ một bản sao của tất cả các thông tin
liên quan đang có ở tất cả các hệ thống cục bộ.
Ưu điểm nổi bật của kiểu tổ chức này là:
i) Dễ dàng thực hiện việc truy cập thông tin cần thiết cho các yêu cầu ngay

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ệt 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.

4
Tiểu luận môn Hệ tin học phân tán Trang
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 trang 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
iii) 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 đến được các bộ cung cấp khác nhau theo một trật tự duy
nhất được cố định từ trước.
Nội dung của các bản sao trên các trạm của hệ có thể phản ảnh như sau:
- Tập hợp tất cả các tài nguyên còn chưa được cung cấp
- Tập hợp các tài nguyên đã cung cấp
- Đối tượng đang chiếm giữ tài nguyên
- Kiểu sử dụng

Cập nhật thông tin
An toàn cho các bản sao
Sử dụng các bộ nhớ, đĩa
Chuyển các bản loại bỏ vào vùng có thể khôi phục
Trong các nội dung nêu trên, vấn đề quan trọng nhất là cập nhật tự động
thông tin vào các bản sao.
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
Khi nghiên cứu về hệ phân tán chúng ta thấy rằng, thời gian truy cập trung
bình vào thông tin trong hệ phân tán có thể được rút ngắn, trong một số trường
hợp, nhờ vào phương pháp nhân nhiều bản và được gọi là nhiều bản sao của một
đối tượng thông tin.
Ta cần phân biệt hai trường hợp khác nhau được thể hiện sau đây:
Trường hợp 1
a) Đa xử lý với bộ nhớ chung:

6
Tiểu luận môn Hệ tin học phân tán Trang
Mỗi một bộ xử lý đều có bộ nhớ cục bộ của mình, hay còn gọi là cache,
được dùng để sao chép lại các vùng đang làm việc của bộ nhớ chung. Một chương
trình thể hiện thuật toán thay thế đảm nhận nhiệm vụ làm mới các bộ nhớ cục bộ.
Trường hợp có nhiều bộ xử lý muốn truy cập vào cùng một đối tượng, ta sử dụng
như là sự tham chiếu đến phiên bản của đối tượng tìm thấy trong bộ nhớ chung.
b) Hệ truy cập từ xa thông qua một máy server duy nhất:

7
L
B
ch

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.
Các trường hợp thể hiện trong hình 1 và 2 xét theo chức năng là giống
nhau. Đó là trường hợp một bản duy nhất của đối tượng là một đặc quyền.
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.

8
Tiểu luận môn Hệ tin học phân tán Trang
Tại đây, tất cả các bản đóng vai trò đối xứng. Công việc được tiến hành
theo kiểu này cho phép rút ngắn thời gian truy cập, nếu số lần truy cập để đọc lớn
hơn số lần truy cập để cập nhật và vì lý do thuận lợi sử dụng theo nghĩa có sẵn để
dùng.
Tình hình nêu trên đặt ra cho chúng ta nhiều vấn đề cần phải giải quyết. Đó
chính là các lần cập nhật thông tin hay nói cách một cách tổng quát là cập nhật các
bản sao. Từ đó, ta rút ra các đặc điểm quan trọng sau đây :
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:

9

II.2 Th
uậ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 tiền định
như loại trừ tương hỗ, luật đọc, hiệu chỉnh thông tin,…
Nếu quyền được thừa nhận thì đối tượng bị cài then bởi giao dịch. Nếu
không, tiến trình giao dịch bị khoá và đối tượng không bị cài then.
Cơ chế cài then cho phép một giao dịch có thể giải phóng đối tượng mà nó
đã cài then.
II.2.1.1 Loại trừ tương hỗ
Một trong những giải pháp giản đơn để đạt được trật tự hoá gắn bó thể hiện
ở chỗ bắt buộc phải sử dụng trật tự hoá tuần tự, toàn bộ giao dịch được đặt trong

10
Tiểu luận môn Hệ tin học phân tán Trang
cặp hàm nguyên thuỷ mo_giaodich và dong_giaodich. Đây là sự đảm bảo cho việc
loại trừ tương hỗ giữa các giao dịch.
II.2.1.2 Then cài chọn lựa các đối tượng
Một giao dịch thay đổi giá trị của đối tượng phải loại trừ tất cả các đối
tượng khác muốn truy cập, ngược lại thì việc truy cập được tiến hành theo kiểu
tương tranh
Để đảm bảo điều đó luôn luôn được thực hiện, người ta cho phép tiến hành
cài then một đối tượng trước khi việc sử dụng nó có hiệu lực
Một giao dịch có thể thực hiện trên ba hàm nguyên thuỷ trên đối tượng e:
SốTT Tên hàm Thuyết minh
1 v_doc(e) Sử dụng khi muốn có được quyền đọc e theo kiểu chia sẻ

ij
với 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 với
k=1 q, trong đó k là trạm
q là số trạm được mắc nối
Các ràng buộc trên các bản sao:

12
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
3
t
t
1
t
2
t

Hình 4. Ba giai đoạn của một giao dịch
Hình 4. Ba giai đoạn của một giao dịch
Tiểu luận môn Hệ tin học phân tán Trang
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 các ràng buộc
toàn vẹn là:
b1=b2= =bn
Trên các bản sao của toàn bộ các đối tượng:

b11=b21= =bn1
b12=b22= =bn2b1m=b2m= =bnm
Gọi M là cực đại của các cập nhật có thể diễn ra đồng thời, thì M có thể
tính theo công thức M=n x m.
Căn cứ vào nội dung thông tin cần phải đảm bảo sự gắn bó mà người ta
chia ra hai loại giải thuật:
+ Giải thuật gắn bó mạnh
+ Giải thuật gắn bó yếu
Hệ thống viễn thông là đối tượng có thể diễn ra các sự cố kỹ thuật và ùn tắt
đường truyền, ta có số lần truy cập bản sao trên thực tế sẽ lớn hơn M rất nhiều;
hiệu năng hoạt động của hệ trong trường hợp này sẽ bị giảm.
Cách đầu tiên được áp dụng là then cài. Giả sử với trường hợp có n bản sao
b
1
, b
2
, …, b
n

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. Việc xác định yêu cầu không được tiến hành ngay tức khắc vì nguyên do ta
không thể biết chắc chắn yêu cầu nào là lâu nhất. Yêu cầu lâu nhất có thể đang
truyền trên đường. Tính không chắc chắn này xuất hiện có điều kiện với giả thiết
về hệ viễn thông. Khi trạm i truyền các thông điệp cho trạm j, Trật tự nhận các
thông điệp tại j là hoàn toàn giống với trật tự của các thông điệp phát đi. Giả thiết
này được kiểm tra trong các mạng thông thường. Việc xác định các yêu cầu cần xử
lý trên một trạm là hoàn toàn có thể.
Có hai trường hợp cần xem xét:
1) Tập hợp các yêu cầu ghi khi chờ chứa các yêu cầu từ tất cả các trạm khác.
Trong trường hợp này các yêu cầu đi qua, nếu chúng tồn tại, là mới hơn so
với các yêu cầu đã đi qua. Nói cách khác, yêu cầu lâu nhất chính là yêu cầu
đang chờ.
2)
Tồn tại các trạm mà không có bất kỳ yêu cầu nào được truyền đến. Ta được đưa
các trường hợp trước đây bằng cách truyền cho tất cả các trạm một thông điệp yêu
cầu và bắt buột phải xác nhận. Do vây, sau một khoảng thời gian, theo giả thiết về
độ ổn định, ta sẽ nhận hoặc là các yêu cầu đi qua, hoặc là các trả lời cho thông
điệp yêu cầu. Lúc này, ta có được các thông điệp đến từ tất cả các trạm.

14
Tiểu luận môn Hệ tin học phân tán Trang
II.2.3.3 Các hành vi bên ngoài của chế độ bình thường
Hai vấn đề mở rộng hơn đối với thuật toán này cho phép rút ra hay chèn

sẽ lớn hơn số lần tính theo lý thuyết rất nhiều; hiệu năng hoạt động của hệ trong
trường hợp này sẽ bị giảm.
Một trong những giải pháp khắc phục vấn đề vừa nêu là áp dụng kỹ thuật
đánh dấu bản điều khiển và căn cứ vào hệ thống tín hiệu này, người ta có thể chọn
các giải thuật cập nhật thích hợp, rút ngắn được tốc độ cập nhật bình quân.
Việc lựa chọn giải thuật cập nhật được tiến hành trên cơ sở truy cập vào cấu
trúc phân tầng. Cấu trúc này được mô tả trong hình vẽ 6.

16
Tiu lun mụn H tin hc phõn tỏn Trang
ng vi mi mt loi truy cp, ngi ta cú th hoc l ỏp dng cỏc gii
thut ang cú ó c kim nghim hoc l phi nghiờn cu cỏc gii thut phự
hp hn nhm khai thỏc ti a kh nng ca k thut v cụng ngh mi.
K thut ỏnh du bn iu khin gi tt l TOMCP (Technique Of
Marking the Control Panel)
Chng trỡnh qun lý TOMCP c xõy dng di dng th tc tin ớch
vi chc nng ch yu l kim tra tớnh hp thc ca vic truy cp vo bn, dũ tỡm

17
W R
WS S
L G
AL P
T NT
GT
1
GT
2
GT
m

thế nào là tối ưu nhất.
Mỗi khi cập nhật, thay vì phải kích hoạt một trình điều khiển như mô hình
Client/Server chứa sẵn trên Server và gửi toàn bộ các yêu cầu thay đổi, thì kỹ thuật
này cho phép chỉ gửi những chi tiết cần thay đổi là đủ.
Việc làm tươi thông tin trong bản điều khiển sẽ do các trạm thực hiện tự
động căn cứ vào dữ liệu mà nó có được. Những thông tin này có khối lượng không
lớn và được các trạm trao đổi với nhau bằng thông điệp.

18
Hình 8. Sơ đồ hệ thống bản điều khiển
Tiểu luận môn Hệ tin học phân tán Trang
Để tránh bế tắc diễn ra trong quá trình truy cập bản điều khiển theo kiểu 2
pha, thông thường giải pháp gắn bó mạnh của Herman được sử dụng.
Hai trạm quan trọng trong tiến trình truy cập bản để đọc và cập nhật bản là
trạm gửi thông điệp (trạm yêu cầu) và trạm nhận thông điệp (trạm đáp ứng yêu
cầu).
Cấu trúc của các thông điệp trao đổi giữa các trạm có thể mô tả trong hình
vẽ 9 dưới đây.
START SOURCE TARGET CODE INFORMATION CONTROL END
Các trường của thông điệp trao đổi là:
1 START Bắt đầu Giá trị 8 bit cho phép bắt đầu thông điệp
2 SOURCE Địa chỉ nguồn Địa chỉ trạm gửi thông điệp với độ dài
từ 8 bit đến 16 bit đủ để biểu diễn số
lượng địa chỉ của các trạm trong các hệ
thống lớn
3 TARGET Địa chỉ đích Địa chỉ của trạm nhận với độ dài của
trường từ 8 bit đến 16 bit
4 CODE Mã Mã sử dụng để nhận biết phép toán trên
bảng với độ dài là 8 bit. Ý nghĩa các bit
được trình bày trong hình 10

Hình 10. Ý nghĩa các bit của trường CODE
Tiểu luận môn Hệ tin học phân tán Trang
6 Thống kê Biết được trạng thái cập nhật ở mọi thời điểm
III.2 Sơ đồ tuần tự xử lý các thao tác đọc, các thao tác cập nhật
Việc xử lý trạng thái điều khiển do trạm nhận tiến hành trên cơ sở tham
chiếu thông tin trong bản điều khiển và theo yêu cầu thể hiện trong hình 11.
Sau khi hoàn thành trọn vẹn công việc, trạm nhận tiến hành phát thông điệp
đến toàn bộ các trạm của hệ thống để cập nhật vào bản điều khiển, đồng thời tự
động cập nhật vào bản cục bộ của mình.
Sơ đồ tổng quát xử lý nhiều bản sao:

21
caithen(B)
Khãa b¶n ®iÒu khiÓn B
Thùc hiÖn viÖc cËp nhËt th«ng tin
trªn b¶n ®iÒu khiÓn B
Më khãa b¶n ®iÒu khiÓn
giaiphong(B)
Capnhat(B)
Hình 11. Trình tự thực hiện cập nhật bản điều khiển
Tiu lun mụn H tin hc phõn tỏn Trang
.
Khi cp nht, gii thut GT
l
, l=1 P c thc hin bi trm nhn trong c
ch then ci i vi cỏc phộp lm thay i thụng tin trong bn sao, ngc li, thỡ
thc hin theo kiu tng tranh.
Vic phỏt hin v x lý li trong quỏ trỡnh x lý c tin hnh ngay sau
khi trm nhn c yờu cu cp nht. Nu mi c gng sa li khụng th thc
hin cú kt qu, thỡ thụng ip s c phỏt i yờu cu trm gi phỏt li thụng

Tiểu luận môn Hệ tin học phân tán Trang
tin. Trong trường hợp công việc cập nhật kết thúc tốt đẹp, một thông điệp khẳng
định cũng được phát đi bởi trạm nhận. Sau khi phát đi thông điệp, trạm gửi chuyển
sang trạng thái chờ thông điệp mới, còn trạm nhận thông điệp chỉ chuyển sang
trạng thái chờ khi đã nhận đủ các thông điệp khẳng định.
Các bước thể hiện công việc xử lý thông tin điều khiển được tiến hành tuần tự như
trong hình 13 sau đây.

23
Hình 13. Các bước xử lý trạng thái điều khiển
Tiu lun mụn H tin hc phõn tỏn Trang
Thut toỏn kim tra v cp nht bn sao th hin bng cỏc khi trong hỡnh
v 14, trong ú mi khi cú th xõy dng mt th tc hoc hm chuyờn bit.

24
Bắt đầu
Truy cập thông
tin về cấu trúc
Tồn tai
Bản sao
xác định
độ dài của
information
Hợp thức
phát thông điệp
cho trạm gửi
Trạng thái
vật lý [o/c]
Thực hiện open
vật lý [kt1]

S
Đ
Hỡnh 14. S x lý v cp nht nhiu bn sao
Tiểu luận môn Hệ tin học phân tán Trang
III.3 Kết luận
Vấn đề cập nhật các bản sao thông tin của cùng một đối tượng dùng chung
trong môi trường phân tán đã được nghiên cứu khá rộng rãi và đã được ứng dụng
vào thực tế xây dựng các ứng dụng lớn như thương mại điện tử, chính phủ điện
tử Tuy vậy, trong khuôn khổ tiểu luận này chỉ nêu lên những vấn đề mang tính
nguyên lý. Thuật toán xử lý các thao tác đọc, các thao tác cập nhật trên không chỉ
chỉ đảm bảo hệ thống hoạt động với tốc độ bình quân chấp nhận được, ổn định, tin
cậy mà quan trọng hơn cả là phải đảm bảo tính gắn bó của dữ liệu trong các bản
sao.
Mô hình hệ thống quản lý nhiều bản sao giống nhau trên môi trường phân
tán và các giải thuật được nghiên cứu trên đã đáp ứng các yêu cầu của một hệ
thống phức tạp với lượng thông tin lớn cần phải xử lý. Nó được ứng dụng như là
các nguyên lý cơ bản cho các hệ thống tệp tin phân tán, các cơ sở dữ liệu phân tán
hiện nay.

25