GVHD: PGS.TS Lê Văn S Trang 1





 
 !"#$
%&

 ' !"#!"$
%&
$ ' '%()*"+
,-( ' ./0.1./02
()*+,, /,0
 1

Hệ tin học phân tán là lĩnh vực còn khá mới mẽ, nhưng những ứng dụng của nó ngày càng
rộng rãi, giải quyết hiệu quả nhiều bài toán mà hệ tin học tập trung không đáp ứng được hoặc
chỉ đáp ứng được một phần.
Hiện tại, các nội dung mang tính lý thuyết nguyên lý của hệ tin học phân tán còn nhiều vấn
đề chưa được giải quyết triệt để và đang là mục tiêu khám phá của nhiều nhà nghiên cứu về công
nghệ thông tin.
Với mong muốn tìm hiểu nắm vững các nội dung nguyên lý của hệ tin học phân tán để có thể
triển khai được các ứng dụng phân tán trong thực tế, bài tiểu luận môn học "Hệ tin học phân tán"
là cơ hội tốt để cho ch@ng tôi tìm hiểu về lĩnh vực này.
Trong phạm vi tiểu luận của mình, ch@ng tôi trình bày được những vấn đề sau:
345!"6
Trong chương 1ch@ng tôi trình bày các khái niệm cơ bản và kiến thức chung của hệ tin
học phân tán.
Chương 2 ch@ng tôi trình bày thuật toán gắn bó trên cơ sở dấu

bao gồm nhiều bộ xử lý hoặc bộ vi xử lý nằm tại các vị trí khác nhau và được liên kết
với nhau thông qua hệ thống viễn thông dưới sự điều hành thống nhất của một hệ điều
hành.
Từ định nghĩa này, người ta có thể xem hệ phân tán như là một tập hợp bao
gồm các bộ xử lý hoặc bộ vi xử lý với bộ nhớ và đồng hồ nhịp độc lập. Điều này đồng
nghĩa với việc các bộ xử lý không sử dụng chung bộ nhớ và đồng hồ. Như vậy, mỗi
một hệ xử lý thông tin thành phần của hệ phân tán bao gồm một hay nhiều bộ xử lý và
bộ nhớ cục bộ. Hệ xử lý thông tin thành phần phải được thiết kế sao cho về cấu trúc,
số lượng và dung lượng có thể cho phép thực hiện một cách trọn vẹn các chức năng
mà nó đảm nhận.
Hệ phân tán được xây dựng nhằm mục đích 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. Đó là những cơ sở căn bản
cho việc xây dựng các ứng dụng lớn như thương mại điện tử, giáo dục điện tử, thư
viện điện tử số, xây dựng các cơ sở dữ liệu tìm kiếm…
Ta có thể nói hệ phân tán bao gồm 4 thực thể như hình vẽ.
?@A(*:BCDE<F>DGH:=I:J*K;*
HL@E<F>
 Chia xẻ tài nguyên: Chia xẻ tài nguyên trong hệ thống phân tán cung cấp
một cơ chế để chia xẻ tập tin ở vị trí xa, xử lý thông tin trong một cơ sở dữ liệu
phân tán, in ấn tại một vị trí xa, sử dụng những thiết bị ở xa để thực hiện các
thao tác…
 Tăng tốc độ tính toán: Hệ thống phân tán cho phép phân chia việc tính
toán trên nhiều vị trí khác nhau để tính toán song song.
GVHD: PGS.TS Lê Văn S Trang 3
 An toàn: Nếu một vị trí trong hệ thống phân tán bị hỏng, các vị trí khác
vẫn tiếp tục làm việc mà không ảnh hưởng đến toàn bộ hệ thống.
 Thông tin liên lạc với nhau: Có nhiều lúc, chương trình cần chuyển đổi
dữ liệu từ vị trí này sang vị trí khác. Khi các vị trí được nối kết với nhau trong
một hệ thống mạng, việc trao đổi dữ liệu diễn ra rất dễ.
MLN*D:O

2U7P*EQ:=K:V*+*:<Q@MW*XHY
GVHD: PGS.TS Lê Văn S Trang 4
* 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à:
<L 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 tại hệ
thống cục bộ của mình
<<L Cho kết quả truy cập một cách nhanh chóng.
Tuy nhiên, chỉ cho kết qủa tương đối chính xác và phụ thuộc rất nhiều vào phương
pháp và thời hạn cập nhật thông tin trong các CSDL cục bộ.
* Sự tồn tại nhiều bản sao trong một hệ phân tán trên nhiều hệ thống cục bộ khác
nhau có thể dẫn đến các hệ quả sau đây:
<L Cập nhật thông tin diễn ra do đăng ký gần hay từ xa hoặc sự thay đổi thông tin
cục bộ trên một hệ cục bộ nào đó cần phải được tiến hành cho tất cả các hệ thống cục
bộ và không được phép bỏ sót hệ thống nào cả. trong khoản thời gian làm tươi, thông
tin phải đảm bảo sao cho việc truy vẩn dữ liệu cho kết quả kịp thời hay đặt truy vấn
trong trạng thái treo.
<<L Cần phải tránh trường hợp các thao tác trên hai bản sao khác nhau nhưng chứa
cùng một thông tin được truy cập bởi hai hay nhiều yêu cầu dẫn đến không gắn bó.
Hai vấn đề vừa nêu trên xác định về các ràng buộc đối với vấn đề gắn bó dữ liệu. Để
đảm bảo sự gắn bó này điều kiện đủ là phải bắt buộc tuân thủ trình tự nào đó cho các
bản sao, các cập nhật thông tin.
Biện pháp hàng đầu nhằm thực hiện việc loại trừ tương hỗ tổng quát trên tập hợp các
bản sao khi đăng ký và thực hiện việc đăng ký trước khi trả lại bình thường. Biện pháp
này có mặt hạn chế là không cho phép các chương trình đăng ký thực hiện song song.
Tất cả các bản sao đều được khoá chặt trong lúc đăng ký.
2U2,:@ZKKY;*D@*+DPI'
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

nhận: hoặc là các yêu cầu đi qua, hoặc là trả lời các thông điệp yêu cầu. Lúc này, ta nói
được các thông điệp đến từ tất cả các trạm.
2.2.2U2 Các hành vi bên ngoài chế độ bình thường:
Có hai vấn đề mở rộng hơn đối với thuật toán này là cho phép rút ra hay chèn
vào tuỳ ý một trạm nào đó. Điều đó, dẫn đến hai vấn đề sau chúng ta cần phải tôn
trọng:
Vấn đề 1: Việc đột nhiên biến mất một trạm nào đó pahỉ được các trạm khác nhận biết
một cách tự động.
Vấn đề 2: việc phát đi một thông điệp là phép toán không thể chia cắt đi được nữa. Đó
là một thông điệp hoặc là tất cả các trạm đều phải nhận được hoặc là không một trạm
nào nhận được cả.
Vì vậy, nếu điều kiện đầu tiên được khống chế thì điều kiện thứ hai mới được đảm
bảo.
2U2U2:@ZKKY;*EW>MWYX`+[*M^aO@*:bMcK@d*K`K@d*:Y(*'
2U2U2,2 Nguyên lý: trước khi phát một yêu cầu một trạm nào đó cần phải kết hợp với
nó một số thứ tự được cấp từ bộ tuần tự tuần hoàn. Các yêu cầu được tiếp nhận tại mỗ
trạm theo cùng một trật tự thống nhất. Điều đó giúp ta có được một sự gắn bó yếu.
Điều chúng ta cần quan tâm ở đây là cơ chế phân phối các số dựa trên nền tảng tổ chức
các trạm theo kiểu vòng tròn ảo.
2U2U2.2 Triển khai hệ số ổn định: bộ tuần tự cung cấp cho mỗi yêu cầu số sắp tới còn
chưa dùng, giả sử dó là T. Khi đến phiên của trạm nhận bộ tuần tự, nó yêu cầu một số
GVHD: PGS.TS Lê Văn S Trang 6
lượng n số đúng bằng số lượng các yêu cầu cập nhật đang chờ trên trạm này. Các số
này là:
T, T + 1, T + 2, ….T + n – 1
Nó tiếp tục chuyển bộ tuần tự cho trạm kế tiếp liền sau nó và số sắp tới chưa dùng
đến T + n.
Khi một trạm đã có sự cố, nó phát yêu cầu cập nhật cùng vơi số này. Trên mỗi
trạm, các cập nhật được thực hiện bằng cách tiếp nhận các yêu cầu cùng các số liên
tiếp nhau( theo một trật tự). Để xác định yêu cầu sắp đến cần phải xử lý , mỗi một trạm

1 Nghỉ ngơi Trạm không thực hiện cập nhật nào cả
GVHD: PGS.TS Lê Văn S Trang 7
2 Hoạt động Trạm đãnhận một yêu cầu cập nhật cục bộ mà yêu cầu này
đã được truyền cho trạm khác để kiểm tra.
3 Thụ động Trạm đồng ý cho một cập nhật và chờ trật tự tương ứng.
4 Cập nhật Trạng đang trong tình trạng chuyển của cập nhật , trong
khi đó tất cả các yêu cầu khác truyền đến đều được lưu trữ.
Chúng sẽ được xử lý khi quay về một trong các trạng thái
khác.
Lúc khởi sự, tất cả các trạm đều ở trong trạng thái nghỉ ngơi.
Trạm khởi sự việc cập nhật , đầu tiên cần phải gửi một yêu cầu cho phép cập nhật,
nó chỉ làm được việc đó trong trạng thái nghỉ ngơi. Lúc này nó được nhận dấu và được
gửi vào vòng tròn trạm khởi sự chuyển từ trạng thái nghỉ ngơi sang trạng thái hoạt
động.
Nếu chỉ có một yêu cầu duy nhất được đưa vào vòng tròn, nó đi qua tất cả các
trạm để chuyển các trạm từ nghỉ ngơi sang thụ động. khi đó, nó trở về nơi khởi sự thì
việc thống nhất coi như hoàn tất. việc cập nhật nói riêng lúc này được gửi đi và mỗi
trạm sau khi thực hiện trở về trạng thái nghỉ ngơi.
Nếu có nhiều yêu cầu đưa ra đồng thời trong vòng tròn, thì tình hình đó dễ dàng
diễn ra xung đột. lúc này, ta phải chọn một yêu cầu có thời gian dấu lâu nhất. Để tiến
hành công việc đó, ta nêu bật vai trò của bộ chắn đường cho các trạm khởi sự. Một
trạm nào đó trong trạng thái nghỉ ngơi hay thụ động phải chuyển toàn bộ yêu cầu đã
đến nó, một trạm trong trạng thái hoạt động chỉ phải chuyển các yêu cầu có thời gian
lâu hơn các yêu cầu mà chính nó phát đi, các yêu cầu khác đều bị dừng lại và được lưu
trữ.
Các yêu cầu bị lưu trữ lại sẽ được gửi tiếp vào vòng tròn, khi trạm lưu trữ chúng
hoàn thành công việc cập nhật riêng của mình.
2U202U2 Hành vi ngoài chế độ bình thường: Các giao thức đặt lại cấu hình vòng tròn
theo kiểu tự động được sử dụng nhằm rút ra hay cho vào tùy ý một số trạm nhất định.
Các sự cố kỹ thuật là rất khó khăn phát hiện các chiến lược mà ở dó các yêu cầu không

xây dựng hệ điều hành. Ngoài ra, đây còn là một trong những vấn đề có tính chất cơ sở
cho các ứng dụng phức tạp.
Quản lý nhiều bản sao là giải pháp kỹ thuật bao gồm tập hợp các thông tin được nhân
bản từ một đối tượng thông tin và các chương trình quản lý chúng trong môi trường
phân tán.
Vấn đề truy cập và xử lý thông tin phân tán nói chung, quản lý nhiều bản sao nói
riêng được nghiên cứu trong hàng loạt các công trình của Herman, Ellis, Wilms và Le
Lann.
Thuật toán đảm bảo sự gắn bó yếu nhờ dấu, được trình bày trong các công trình
nghiên cứu của Herman.
Nội dung quản lý nhiều bản sao là các giải pháp cho phép tự động hóa các công
việc:
Kiểm tra tính hợp lệ của việc truy cập thông tin
Khôi phục thông tin
Cập nhật thông tin
An toàn dữ liệu 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.
GVHD: PGS.TS Lê Văn S Trang 9
"'66#h 45%&
2.2,24!3
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.
2.2.2ij
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

Vì vậy, việc tuân thủ hai điều kiện trên đặt ra cho chúng ta tình hình là nếu điều
kiện đầu tiên có thể được khống chế, thì điều kiện thứ hai rất khó đảm bảo.
1'
QM(<' Đây là một bài toán dựa vào thuật toán Mullery
Trong hệ thống phân tán giả định có độ ổn định tuyệt vời, ta muốn duy trì một sự gắn
bó mạnh giữa các bản sao của một đối tượng được định vị trên các trạm khác nhau.
Thuật toán dựa trên các nguyên lý sau:
Trước khi thực hiện cập nhật, một trạm nào đó cần phải yêu cầu và thống nhất với các
trạm khác.
Khi đã có sự thống nhất, tiến hành cập nhật; việc cập nhật được tiến hành trên tất cả
các bản sao; đối tương không thể truy nhập chừng nào các bản sao còn chưa cập nhật
hết.
Các xung đột giữa các trạm được giải quyết bằng một trật tự có hệ số ưu tiên giữa các
trạm, được cố định một lần lúc khởi tạo.
J@:S<'
1. Hỏi có bao nhiêu trạng thái khác nhau cần xem xét cho mỗi bản sao.
2. Hãy tr ình bày sơ đồ hoạt động của thuật toán (đồ thị phát triển).
3. Hãy đánh giá bằng hàm của số lượng bản sao, số lượng các thông điệp cần thiết để
thực hiện một cập nhật.
4. Ta phải sửa đổi thuật toán như thế nào để chịu đựng được sự cố trên một trạm (giả
sử hệ viễn thông hoạt động tốt).
RWlb<'
1. Có 4 trạng thái cần xem xét cho mỗi bản sao
2. Sơ đồ hoạt động của tuật toán
GVHD: PGS.TS Lê Văn S Trang 11
STT Trạng thái Giải thích
1 Nghỉ trạm không thực hiện cập nhật nào cả
2 Hoạt động chấp nhận yêu cầu cập nhật và yêu cấu này được truyền
đến các trạm khác để kiểm tra
3 Chờ Đồng ý cho cập nhật và chờ đến trạng thái ưu tiên

Cho i = 1 đến n thực hiện giai_phong(ei).
Như vậy, số lượng thông điệp để thực hiện cập nhật đối với một đối tượng là = 2.n
Với k đối tượng ta có số thông điệp là = k. 2n
Hệ thống có M trạm, vậy số thông điệp là : (M-1). k. 2n.
4. Giả sử hệ thống viễn thông hoạt động tốt, thuật toán phải được sửa đổi như thế
nào để chịu đựng được sự cố trên một trạm
Khi gửi thông điệp để cập nhật thì đồng thời kiểm tra phản hồi từ trạm và xác định
trạm có bị sự cố hây không.
TÀI LIỆU THAM KHẢO
GVHD: PGS.TS Lê Văn S Trang 13
1. $9*:; <!=>?@!A(BC+
D
2.  !"E5*FGHE!:*IJKLLK&"MEE)(: <!=>
A,
3.  NF&>!K  "FK)F  OC%K$F  (  NKFP  :  K%&K  C%!E%!&F;  JK(
N%EE)%&KQ)'>K&
4. :KKI' :YDl<m@>Y2DY>-DY@RXm-<*nY2I:Io<_pqr
5. R,6*ST<9"'
:KKI' <KI2:@K2m_@2A*-M]ml-DY@RXm-<*nY2I:Io<_pr0
6. NF&>!KF"FK)FKKK&':KKI' sss2<YI2YR+-tu-vY@R*Hl-%#t
7. 4&%!%L%&F&>!KF"FK)F':KKI' DY_m2+YY+lm2DY>-m_@-IHRHllml-_X_w
K@KYR<Hl2:K>l
8. !8%*U(1KF"FK)':KKI' _HKH2@KH2m_@-xRH>mX:-DXmeU/q-%.2:K>l
9. HK<()$EKF&>!KF"FK)F':KKI' IYRKHl2HD>2YR+-D<KHK<Y*2Dn>o
_Y<_pU./.e,2U./.q/
GVHD: PGS.TS Lê Văn S Trang 14