ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC KỸ THUẬT
oOOo
TIỂU LUẬN
HỆ PHÂN TÁN

ĐỀ TÀI :
 Vấn đề đồng bộ hóa
GIÁO VIÊN GIẢNG DẠY: PGS TS. LÊ VĂN SƠN
Đà nẵng, tháng 06/2014
Đề số 18
I. Đồng bộ hóa nhờ dấu.
II. Tự mình đặt ra 1 bài toán (ví dụ giải phương trình bậc 2), lập trình giải trên máy đơn
bằng PASCAL và trên ASP. Hãy rút ra những kết luận quan trọng về phân tán.
LỜI MỞ ĐẦU
Cùng với sự phát triển ngày càng cao của công nghệ thông tin. Sự ra đời và
phát triển ồ ạt của máy vi tính và các phương tiện xử lý thông tin khác, cũng như
nhu cầu trao đổi thông tin trong mọi hoạt động xã hội loài người . Đòi hỏi sự phát
triển đồng bộ các phương pháp truyền thông . Mạng máy tính ra đời làm cho mọi
người trên thế giới trở nên gần nhau hơn . Hệ tin học phân tán ra đời nhằm phát triển
nhu cầu của công nghệ thông tin .
Hệ tin học phân tán hay nói ngắn gọn là hệ phân tán (Distributed System) là
hệ thống xử lý thông tin 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 phương tiện viễn thông dưới sự điều
khiển thống nhất của một hệ điều hành.
Để đảm bảo tính gắn bó của hệ, yêu cầu đặt ra trước hết là đồng bộ hóa các
tiến trình. Trình tự và đồng bộ các tiến trình trong hệ phân tán chỉ ra cho ta các vấn
đề đồng bộ có thể sẽ dẫn đến phải thiết chế một trật tự tổng quát của các sự kiện
diễn ra trong hệ . Cần phải xác định mối liên hệ trao đổi thông qua các thông điệp
với thời gian truyền khác nhau, những thông tin tạm thời trao đổi không có giá trị
tuyệt đối và trình tự tổng quát cần phải được thể hiện bằng phương tiện giải thuật

sát phần cứng, nó gắn kết chặt chẽ với phần thiết bị bởi một hệ thống các chương
trình, điều khiển và sắp xếp nhằm khai thác phần cứng phục vụ cho các chương trình
ứng dụng khác nhau của NSD khác nhau với kết quả và hiệu năng chấp nhận được .
Như vậy, hệ tin học bao gồm ba thực thể : phần cứng, phần mềm và dữ liệu ,
được mô tả ở hình I-2.
Vậy hệ thống tin học (Informatic System ) là một hệ thống bao gồm hai thành
phần cơ bản phần cứng (hardware) và phần mềm (software) gắn bó hữu cơ với nhau
và có khả năng xử lý thông tin.
I.2. Hệ tin học phân tán
I.2.1.Định nghĩa
Hệ tin học phân tán hay nói ngắn gọn là hệ phân tán (Distributed System) là
hệ thống xử lý thông tin 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 được liên kết với nhau thông qua phương tiện viễn thông dưới sự điều
khiển thống nhất của một hệ điều hành.
I.2.2. Các thực thể trong hệ phân tán
Hệ phân tán gồm 4 thực thể :
I.2.3. Đặc điểm của hệ phân tán :
Đặc điểm cần nhấn mạnh của hệ là các hệ xử lý thông tin thành phần :
• Không dùng chung hoặc chia sẻ bộ nhớ
• Không sử dụng chung đồng hồ xung nhịp
• Chúng liên lạc với nhau thông qua mạng truyền thông
• Mỗi hệ xử lý có bộ xử lý, bộ nhớ và hệ điều hành riêng của nó.
Thành phần của hệ phân tán bao gồm các hệ thống cục bộ trong đó mỗi một
hay nhiều hệ thống phát các yêu cầu thông tin còn các hệ khác trả lời các yêu cầu có
liên quan đến phần dữ liệu của mình. Nói một cách tổng quát là trong hệ luôn luôn
diễn ra việc thực hiện các công việc do các hệ thống yêu cầu. Các hệ thống truyền
thống như hệ rời rạc hay tập trung không thể đáp ứng nhanh chóng và chính xác các
yêu cầu thông tin từ xa với lưu lượng thông tin lớn.
I.2.4.Các ưu điểm của tài nguyên dùng chung trong hệ phân tán :
Hệ tin học phân tán thực hiện hàng loạt các chức năng phức tạp nhưng chức

muốn truy cập vào tài nguyên dùng chung.
2) Các tiến trình của cùng một hệ ứng dụng hoạt động theo kiểu hợp lực để
giải quyết các bài toán đặt ra và cho kết quả nhanh chóng nhất. Điều này cho phép
tăng hiệu năng sử dụng thiết bị và hiệu quả hoạt động của chương trình. Hợp lực là
nguyên nhân chính của sự tác động tương hỗ được lập trình giữa các tiến trình nhằm
cho phép chúng tham gia vào các hành động chung.
Vì vậy, Sự tương tranh và hợp lực giữa các tiến trình đòi hỏi phải có trao đổi
thông điệp qua lại với nhau. Trong các hệ thống tập trung, điều đó được thực hiện
nhờ thuật toán loại trừ tương hỗ thông qua các biến cùng tác động trong một vùng
nhớ chung. Trong hệ tin học phân tán, các thông tin cần trao đổi thông qua các kênh
thuộc hệ thống viễn thông.
II.2 Bài toán bãi để xe ô tô.
II.2.1. Bài toán bãi để xe :
Để rút ra các vấn đề đang đặt ra trong hệ
phân tán về việc đồng bộ hóa các tiến trình. Ta
hãy nghiên cứu một ví dụ kinh điển, đó là bài
toán bãi để xe ô tô, với nội dung được nêu ra như
sau :
Hình II-1 mô phỏng bãi để xe ô tô hiện đại. Trong đó BV (người bảo vệ) có
nhiệm vụ phân phối chỗ cho các xe ô tô, VT(vị trí) cho từng xe ôtô cụ thể. Các mũi
tên hai chiều được sử dụng để mô tả dòng vào ra của ô tô.
Bài toán nêu ra một số tình huống sau:
Tình huống thứ 1:
Giả sử bãi để xe ô tô là loại bãi lớn có một cổng vào dưới sự kiểm soát của
một người bảo vệ (NBV) duy nhất. NBV chỉ biết được một phần trạng thái của bãi
để xe. Trong khi anh ta nghĩ rằng bãi xe đã bị đầy, khi đó lại có nhiều lái xe đang
cho xe chạy ra cổng. Vì suy nghĩ như vậy, trong trường hợp này, anh ta không giải
quyết cho các xe tiếp tục vào bãi nữa, mặc dù lúc này trong bãi đang có chỗ trống.
Như vậy, NBV không nắm được trạng thái hiện hành của bãi.
Tình huống thứ 2:

NBV sẽ có thông tin về số lượng chỗ trống khác nhau. Để bảo đảm các bản cập nhật
giống nhau thì trình tự cập nhật nhất thiết phải giống nhau trên tất cả các trạm.
trật tự
xử lý
Bảo vệ 1 Bảo vệ 2 Bảo vệ 3 Bảo vệ 4
Thôn
g điệp
giá
trị
Thông
điệp
giá trị Thông
điệp
giá
trị
Thông
điệp
giá
trị
100 100 100 100
1 M1 120 M1 120 M3 90 M2 90
2 M3 108 M2 110 M1 110 M3 81
Stt Ký hiệu Thông tin phát đi
1 M1 thêm 20 chỗ trống
2 M2 có 10 chỗ bị chiếm
3 M3 dành 10% chỗ trống để quét dọn bãi
Bảng II-1
3 M2 98 M3 99 M2 100 M1 101
Bảng II-2: Sự không gắn bó giữa 4 người bảo vệ
II.2.3 Qui tắc cho các thuật toán cung cấp trong hệ phân tán:

khác, các tiến trình cạnh tranh hay tranh giành nhau quyền truy cập vào miền
găng.
− Truy cập vào miền găng dựa trên (Token based): Việc truy cập vào
miền găng được điều khiển bởi một token. Người giữ token có quyền thi hành
đoạn găng của nó.
− Tổng quát
Một trạm bất kỳ trong hệ thống có thể
+ Yêu cầu miền găng
+ Thi hành miền găng
+ Hoặc không làm gì cả đối với miền găng (thi hành trong đoạn không phải
miền găng).
Các thuật toán nên thỏa mãn các yêu cầu: Không bế tắc, không thiếu, các yêu
cầu được thi hành theo thứ tự chúng được tạo, có thể vẫn hoạt động khi có sự cố tại
một hoặc nhiều trạm.
II.4 Sắp xếp kiểu đóng dấu:
Đóng dấu là hành vi gán giá trị nguyên cho một thông điệp nhằm ghi nhận
thời điểm truyền trên cơ sở tham chiếu đồng hồ lôgic. Tức là 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à
đưa vào đồng hồ lôgic cục bộ của chính trạm . Các đồng hồ này được lấy lại thông
tin qua hội thoại giữa các trạm.
II.4.1 Các khái niệm :
* Đồng hồ lôgic :
Đối với nhiều ứng dụng, các sự kiện không cần lập lịch hay đồng bộ đối với
thời gian thực. Nó chỉ là thứ tự sự kiện hoạt động liên quan. Trong trường hợp như
vậy, đồng hồ lôgic có thể được dùng để biểu thị thứ tự thông tin cho các sự kiện, đặc
biệt trong hệ phân tán, nó khó giữ được đồng hồ vật lý chung giữa tất cả các tiến
trình đang sắp xếp. Đồng hồ lôgic Lamport là khái niệm cơ bản để sắp xếp các tiến
trình và các sự kiện trong hệ phân tán.
Mỗi trạm s đều có trang bị công tơ với các giá trị nguyên gọi là H
s .

- Nếu A là phát thông điệp từ một trạm nào đó và B là nhận thông điệp thì ta
có A→B. (nhân-quả)
- Nếu A→B và B→C, thì A→C. (bắc cầu)
* Gắn thời gian lôgic với các sự kiện
- Các đồng hồ lôgic: gán một số cho mỗi sự kiện cục bộ.
- Hệ thống các đồng hồ lôgic phải chính xác :
Điều kiện đồng hồ :
∀ sự kiện a,b : nếu a → b thì H(a) < H(b)
- Để thực thi các đồng hồ thỏa mãn điều kiện đồng hồ, ta có thể áp dụng thuật
toán đóng dấu thời gian .
II.4.2 Đồng bộ theo trật tự tổng quát chặt chẽ (Lamport):
Trật tự từng phần chỉ có thể áp dụng cho một số hệ thống , điều này có nghĩa
là một số hệ thống có thể gắn bó được thông qua việc sắp xếp các sự kiện theo trật
tự bằng quan hệ “có trước”. Tuy nhiên có rất nhiều hệ phân tán các sự kiện không
thể sắp được bằng trật tự từng phần, do vậy phải cần đến trật tự chặt chẽ (=>)của
các sự kiện.
* Giải thuật đóng dấu thời gian của Lamport
Đồng hồ lôgic cho phép đóng dấu thời gian, nhằm xác lập trật tự cho từng sự
kiện trong hệ phân tán để với mỗi cặp sự kiện A và B ta có: nếu A có trước B (A →
B) thì đồng hồ lôgic của A nhỏ hơn đồng hồ lôgic của B.
Nguyên tắc thiết lập: Mỗi trạm S đều có trang bị công tơ với các giá trị
nguyên Hs đó chính là đồng hồ lôgic, hoạt động theo các qui tắc sau:
Gia tăng H
i
thêm một trị số giữa hai sự kiện kế tiếp
Trạm e phát thông điệp m , ghi dấu dấu thời gian cho các thông điệp m gửi đi,
T
m
= H
e

H
r
H
r
= T
m
+ 1
(m, T
m
,s)
Trật tự sự kiện toàn bộ: Một sự kiện a sinh ra trên trạm i được đánh dấu bởi
đồng hồ cục bộ H
i
, nến a và b là hai sự kiện trên hai trạm i và j ta quan hệ sau:
a ⇒ b ⇒ H
i
(a) < H
j
(b) hay H
i
(a) = H
j
(b) và i < j
II.4.3 Thuật toán loại trừ tương hỗ trên cơ sở đóng dấu của Lamport
Thuật toán này được Lamport đưa ra, nó sử dụng cơ chế đóng dấu thời gian
cho việc đồng bộ các đồng hồ lôgic.
-Các giả định:
Chúng ra giả định mô hình mạng kết nối hoàn toàn trong đó các tiến trình liên
lạc thông qua các kênh FIFO tin cậy. Tức là, các thông điệp không thể sắp xếp lại
theo trật tự khác.

Một trạm thi hành miền găng của nó khi:
Nhận được thông điệp trả lời ACQ từ tất cả các trạm còn lại .
Yêu cầu REQ của nó là ở trên đỉnh của hàng đợi cục bộ của nó.
Khi một trạm hoàn thành miền găng của nó, nó sẽ gửi khuyến nghị giải phóng
REL đến tất cả các trạm. Yêu cầu của nó được loại khỏi tất cả các hàng đợi tại thời
điểm này. Nếu các trạm khác đang chờ để thi hành miền găng của chúng, một trong
các trạm đó bây giờ có thể bắt đầu thực hiện miền găng của mình.
Như vậy:
Độ trễ đồng bộ: T (trong đó T thời gian trung bình truyền thông điệp) khi
nhận được thông điệp giải phóng, tiến trình tiếp theo có thể bắt đầu thi hành.
Loại trừ tương hỗ là đạt được: Các dấu thời gian là duy nhất, vì vậy tất cả các
hàng đợi sẽ giữ các yêu cầu trong cùng một thứ tự. Chỉ một tiến trình duy nhất sẽ
nằm ở đỉnh của các hàng đợi.
Các yêu cầu được cấp quyền dựa trên cơ sở của trật tự dấu thời gian và các
tiến trình gửi các thông điệp REL.
Ví dụ:
Xét một mạng bao gồm ba trạm, trong số đó có hai trạm 1 và 2 yêu cầu vào đoạn găng tại thời
điểm 2 của đồng hồ lo gics của chúng. Tập hợp các thông điệp được truyền giữa chúng với
nhau có thể mô tả trong hình vẽ sau:
Ta nhận thấy rằng:
- Trạm 1 vào đoạn găng tại H1 = 8
- Trạm 2 vào đoạn găng tại H2 = 11
Kết luận:
Các dấu được cung cấp bởi đồng hồ lô gích cho phép đánh dấu các sự kiện và xác định một trật
tự tổng quát chặt chẽ. Nhưng, tại đây ta không có quan hệ nào giữa các sự kiện và các giá trị
của dấu.
Trân một trạm cho trước, việc nhận một thông điệp có đóng dấu không thể cho nó biết được
còn sự kiện nào đến trước sự kiện đó đang ở trên đường. Như thế, ta còn phải nhận thông điệp
từ các trạm khác còn lại.
Trạm 1 Trạm 2 Trạm 3

REL,10,1
Loại trừ tương hỗ nhờ dấu