Tiểu luận Môn học Lập trình Mạng nâng cao
ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA
  
BÁO CÁO MÔN HỌC
LẬP TRÌNH MẠNG
ĐỀ TÀI :
TRIỂN KHAI CÔNG TƠ SỰ KIỆN PHÂN TÁN TRÊN N
SERVER (N>=2) VÀ XÁC ĐỊNH GIÁ TRỊ “ẢNH” CỦA
CÁC CÔNG TƠ SỰ KIỆN TRÊN MỖI TRẠM
Giáo viên hướng dẫn:
PGS. TS. LÊ VĂN SƠN
Học viên thực hiện:
Huỳnh Anh Tuấn
Lớp: Khoa học Máy tính – K24
Đà Nẵng, 5/2012
MỤC LỤC
LẬP TRÌNH MẠNG 1
GV hướng dẫn: PGS. TS. Trần Văn Sơn Trang 1/30
Tiểu luận Môn học Lập trình Mạng nâng cao
TRIỂN KHAI CÔNG TƠ SỰ KIỆN PHÂN TÁN TRÊN N SERVER (N>=2) VÀ
XÁC ĐỊNH GIÁ TRỊ “ẢNH” CỦA CÁC CÔNG TƠ SỰ KIỆN TRÊN MỖI
TRẠM 1
Giáo viên hướng dẫn: 1
PGS. TS. LÊ VĂN SƠN 1
Học viên thực hiện: 1
Lớp: Khoa học Máy tính – K24 1
1
Đà Nẵng, 5/2012 1
MỤC LỤC 1
LỜI GIỚI THIỆU 3

tài liệu để em có thể hoàn thành tiểu luận này.
Học viên thực hiện
Huỳnh Anh Tuấn
GV hướng dẫn: PGS. TS. Trần Văn Sơn Trang 3/30
Tiểu luận Môn học Lập trình Mạng nâng cao
YÊU CẦU CỦA ĐỀ TÀI
Vấn đề:
Ta triển khai công tơ sự kiện phân tán trên N Server (N≥2). Giả sử rằng trong thời gian
đầu các trạm hoạt động rất ổn định và ta cài đặt trên mỗi trạm một công tơ sự kiện cục
bộ. Hãy cho biết làm thế nào một trạm có thể có giá trị "ảnh" của các công tơ sự kiện trên
mỗi trạm.
Mục tiêu:
1. Giải quyết bài toán đồng bộ hóa và gắn bó dữ liệu
2. Viết chương trình cho biết giá trị “ảnh” của các công tơ.
GV hướng dẫn: PGS. TS. Trần Văn Sơn Trang 4/30
Tiểu luận Môn học Lập trình Mạng nâng cao
CHƯƠNG I: TỔNG QUAN VỀ HỆ PHÂN TÁN VÀ LẬP TRÌNH MẠNG
I.1. Hệ thống tin học
Hệ thống tin học (Informatics System) là hệ thống bao gồm hai phần cơ bản là
phần cứng (hardware) hay là phần vật lý và phần mềm (software) là phần logic hay là
chương trình gắn bó hữu cơ với nhau và có khả năng xử lý thông tin. Hệ thống tin học
gồm ba thực thể: phần cứng, phần mềm, dữ liệu.
I.2. Hệ tin học phân tán
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 các 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.
Hệ tin học phân tán là hệ thống không chia sẻ bộ nhớ và đồng hồ. Điều đó cho phép
phân biệt với một xu hướng tin học khác về phân tán các tính toán trên nhiều bộ xử lý
hay vi xử lý của hệ thống đa bộ xử lý.

 Mỗi phần là một tập hợp các đối tượng.
 Duy trì các bản sao của toàn bộ tập hợp các đối tượng trên một vài máy.
Ví dụ: Web Proxy Server: cung cấp một bộ nhớ cache chia xẻ cho các máy client tại
một site hoặc băng qua một vài site khác nhau
I.4.2. Mô hình tương tác trong hệ phân tán
 Thực hiện truyền thông:
o Sự tiềm ẩn (Latency):
 Sự trì hoãn lan truyền: thời gian cần thiết để một bit đầu tiên của một
thông điệp truyền đến được đích.
 Sự trì hoãn truyền: là khoảng thời gian giữa sự truyền bit đầu tiên và
bit sau cùng của một thông điệp.
 Sự trì hoãn xử lý: là thời gian cần để hệ điều hành xử lý/gửi/nhận
thông điệp.
 Sự trì hoãn xếp hàng: thời gian cần để một thông điệp xếp hàng ở
cuối máy chủ hoặc ở các node trung gian đợi để truyền đi.
o Băng thông (bandwidth): Tổng số thông tin có thể được truyền đi trong
một thời gian đã cho.
o Sự biến đống tạp (Jitter): thời gian khác nhau giữa các sự trì hoãn ảnh
hưởng bởi các thông điệp khác nhau.
 Đồng hồ và thứ tự các sự kiện:
o Không có khái niệm toàn cục của thời gian.
o Nhịp độ đồng hồ trôi: nhịp độ tương đối ở một đồng hồ máy tính trôi
dạt ra khỏi từ một đồng hồ tham chiếu hoàn hảo.
o Đồng bộ hóa đồng hồ:
GV hướng dẫn: PGS. TS. Trần Văn Sơn Trang 7/30
Tiểu luận Môn học Lập trình Mạng nâng cao
o Hệ thống định vị toàn cầu (GPS): một ít máy tính có thể sử dụng máy
thu radio để nhận thời gian đọc từ GPS với độ chính xác là 1 micro-
giây. Chúng có thể gửi các thông điệp thời gian đến các máy tính khác
trong mạng tương ứng của chúng.

1 Các bộ cung cấp bắt buộc phải thực hiện cùng một giải thuật
2 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
3
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.
Qui tắc cuối, nhấn mạnh đến sự thiết yếu phải có một trật tự duy nhất trên tập hợp
các thông điệp của hệ. Trật tự này có thể được thực hiện thông qua việc hợp lực của các
tiến trình cung cấp. Ở phần sau chúng ta nghiên cứu một số phương pháp sắp xếp nhằm
xác lập một trật tự đảm bảo cho yêu cầu đồng bộ hóa.
II.1.2. Vấn đề gắn bó dữ liệu
Gắn bó dữ liệu là quá trình khi thực hiện trao đổi thông tin qua lại với nhau vào tại
một thời điểm t nào đó thì giá trị các tiến trình phải giống nhau. Để hiểu rõ hơn về gắn bó
dữ liệu ta xét bài toán bãi đỗ xe như sau:
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 ra vào.
Trong bài toán này chúng ta nhận thấy :
• Bãi đậu xe chính là tài nguyên
GV hướng dẫn: PGS. TS. Trần Văn Sơn Trang 9/30
VT
VT
VT
VT
VT
VT
VT
VT
VT
VT

định như trong hình vẽ trên.
- Trên thực tế một người bảo vệ nào đó tin rằng không còn chỗ trống nữa, trong
khi một người bảo vệ khác lại vừa mới cho ra khỏi bãi một số xe mà anh ta
chưa kịp báo cho các người bảo vệ khác. Cũng có thể diễn ra trường hợp là
cùng một lúc các người bảo vệ giải quyết các xe vào cùng một vị trí trong bãi
do vì họ thiếu thông tin.
- Như vậy các người bảo vệ phải hợp lực với nhau để phân phối chính xác các
chổ trong bãi, đặc biệt là số lượng chổ còn trống càng ít thì vai trò của hợp lực
còn quan trọng. Đây chính là sự không gắn bó dữ liệu ở bãi đậu xe ô tô
- Để hiểu rõ hơn vấn đề đồng bộ hoá ta xét ví dụ cụ thể như sau : Giả sử rằng ở
thời điểm cho trước ta có 4 ngưòi bảo vệ và có 100 chỗ còn trống. Tất cả các
người bảo vệ đều có thông tin đó. Trạng thái lúc này của hệ là gắn bó. Ba
trong số họ phát đi các thông tin sau :
GV hướng dẫn: PGS. TS. Trần Văn Sơn Trang 10/30
Tiểu luận Môn học Lập trình Mạng nâng cao
Nếu ta không có ràng buộc nào đối với trình tự xử lý các thông điệp nhận được của
các người bảo vệ thì các 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ông
điệp
Giá
Trị
Thông
điệp
Giá
Trị

sự kiện mà các tiến trình của nó cần phải đồng bộ là vấn đề cần phải quan tâm giải quyết.
Trong các hệ thống phân tán, việc đồng bộ hoá chỉ đặt ra duy nhất vấn đề thiết lập
một trật tự giữa các sự kiện. Giữa các trạm khác nhau, trật tự đó chỉ có thể hiện được
thông qua việc trao đổi các thông điệp với nhau.
Giả sử rằng ta có thể xác định một trật tự giữa các sự kiện của hệ phân tán nhờ vào
quan hệ được ký hiệu là → và gọi là “có trước” hay “ở ngay trước”.
Quan hệ này tối thiếu phải thoã mãn được ràng buộc thể hiện trong bảng sau đây :
Hình vẽ sau đây cho ta một ví dụ về trật tự hoá từng phần của các sự kiện trong hệ
thống.
Theo hình vẽ trên, ta có thể biểu diễn trật tự như sau :
 Trật tự từng phần của các sự kiện
A
1
→ A
2
→ A
3
→ A
4
→ A
5
B
1
→ B
2
→ B
3
→ B
4
 Trao đổi thông tin

A
1
→ A
2
→ B
2
→ B
3
→ B
4
B
1
→ B
2
→ B
3
→ A
4
→ A
5
A
1
→ A
2
→ B
2
→ B
3
→ A
4

Một trạm trong các trạm đều có thể liên lạc với các trạm còn
lại trong hệ
2 H2
Không có lỗi truyền thông tin và không mất thông điệp
3 H3
Trật tự nhận trên trạm j của dãy các thông điệp cũng giống
như chính tại trạm I là giống với trật tự của nơi phát
4 H4
Sự cố hay gián đoạn vật lý tại một trạm nào đó được phát
hiện sẽ lập tức thông báo đến tất cả các trạm có ý định liên lạc
với nó.
Trước hết, trong đề tài này nghiên cứu sự hoạt động của hệ không có sự cố, rồi sau
đó sẽ chỉ ra hiệu ứng của sự cố hay việc phục hồi lại một trạm. Đó là trường hợp đã nêu
lên trong H4 ở trên. Ngoài ra còn giả sử rằng hiện tượng gây sự cố trên một trạm chỉ làm
GV hướng dẫn: PGS. TS. Trần Văn Sơn Trang 13/30
Tiểu luận Môn học Lập trình Mạng nâng cao
cho trạm đó không liên lạc được với mạng mà hoàn toàn không ảnh hưởng đến sự hoạt
động của các trạm còn lại hoặc ít nhất là một nhóm các trạm khác.
II.1.5. Trật tự tổng quát chặt chẽ
Trong một số trường hợp cần phải sắp xếp toàn bộ theo kiểu chặt chẽ các sự kiện
của hệ liên quan trực tiếp đến việc cung cấp các tài nguyên. Nguyên lý của vấn đề được
khái quát như sau. Một tiến trình nào đó gởi thông điệp để yêu cầu sử dung tài nguyên;
một tiến trình sử dụng xong tài nguyên nào đó truyền một thông tin giải phóng khi nó
ngừng chiếm dụng.
 Cung cấp tập trung :
Hiện tại, trong các hệ thống tập trung, mỗi một loại tài nguyên của hệ được quản lý
bởi một chương trình cung cấp duy nhất, goi là bộ cung cấp tài nguyên. Chương trình này
tiếp tục nhận tất cả các yêu cầu, khuyến nghị giải phóng và sắp xếp chúng trong một hàng
đợi xử lý theo kiểu loại trừ tương hỗ và xử lý chúng theo một trật tự nhất định của hàng
đợi này.

a
P
(a
→
b) - nhân quả -
•
b
Q
•
c
Tiểu luận Môn học Lập trình Mạng nâng cao
Vì lý do ổ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ắn bó với nhau giữa các chương trình cung cấp là rất cần
thiết để đảm bảo cho hoạt động cung cấp được hoàn toàn chính xác.
II.2.Sắp xếp kiểu đóng dấu
II.2.1. Đồng hồ logic
Đố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ồ logic 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ồ logic 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.
II.2.2. Minh họa trật tự từng phần
Trong thực tế một số hệ thống
khi đồng bộ hóa chỉ đòi hỏi trật tự từng
phần. Chính vì vậy, trật tự hóa từng
phần giữa các sự kiện mà tiến trình của
nó cần phải đồng bộ là vấn đề cần phải quan tâm .
Giả sử rằng ta có thể xác định một trật tự giữa các sự kiện của hệ phân tán nhờ vào
quan hệ “có trước” (→) hay “ở ngay trước”:

p3
p4
q1
q2
q3
q4
q5
q6
r1
r2
r3
r4
P RQ
∀ sự kiện a,b : nếu a → b thì C(a) < C(b)
Tiểu luận Môn học Lập trình Mạng nâng cao
Trong các hệ thống tập trung, mỗi loại tài nguyên được quản lý bởi một chương
trình cung cấp duy nhất. Chương trình này tiếp nhận tất cả các yêu cầu, khuyến nghị giải
phóng và sắp xếp chúng trong một hàng đợi xử lý theo kiểu loại trừ tương hỗ.
Trong các hệ phân tán, chương trình cung cấp nằm trên một trạm và các tiến trình
đề nghị từ các trạm khác. Các yêu cầu, khuyến nghị giải phóng được truyền cho chương
trình cung cấp thông qua hình thức thông điệp chuyển theo các kênh của hệ thống viễn
thông. Chính vì vậy, nhu cầu sắp xếp các yêu cầu này theo một trật tự nhất định nào đó
luôn được đặt ra.
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.
Nếu chỉ có một thông điệp đến chương trình cung cấp thì trật tự đến thể hiện một
trật tự chặt chẽ. Ngước lại, việc sắp xếp chúng phải theo kiểu loại trừ tương hỗ cho hàng
đợi cục bộ của trạm có chứa chương trình cung cấp. Điều đó cũng chi phép có được một

Tập hợp các sự kiện được sản sinh ra bỡi Pi có một tổng thứ tự được xác định bởi
dãy các sự kiện eix  eix+1
Chúng ta nói rằng eix xảy ra trước eix+1
Quan hệ xảy ra trước  có tính bắc cầu: eii  eij với mọi i<j.
 Các sự kiện xảy ra giữa hai tiến trình đồng thời nói chung không quan hệ,
ngoại trừ hai tiến trình đó có liên quan theo quan hệ như sau:
Đối với mỗi thông điệp m trao đỗi giữa hai tiến trình Pi và Pj, chúng ta có e
i
x
=
send(m), e
j
y
= receive(m) và e
i
x
 e
j
y
.
GV hướng dẫn: PGS. TS. Trần Văn Sơn Trang 18/30
P1 P2 P3 P4
0 0 0 0
(a,1,1)
(b,1,4)
3
2
2
3
2

Thứ tự các sự kiện tại của các tiến trình tại các trạm phát nhận
II.3.4. Những điều kiện đồng hồ:
 Trong một hệ thống các đồng hồ logic, các tiến trình riêng biệt có một đồng hồ
logic mà được áp dụng theo một giao thức.
 Mỗi sự kiện được gán một timestamp (thời gian đánh dấu) trong cách thức mà thõa
mãn điều kiện bền chặt đồng hồ: nếu e
1
 e
2
thì C(e
1
) < C(e
2
).
Trong đó: C(e
i
) là timestamp (thời gian đánh dấu) được gán cho sự kiện e
i
.
 Nếu giao thức thõa mãn các điều kiện theo sau nữa, thì đồng hồ được nói rằng bền
GV hướng dẫn: PGS. TS. Trần Văn Sơn Trang 19/30
Tiểu luận Môn học Lập trình Mạng nâng cao
chặt mạnh: nếu C(e
1
) < C(e
2
) thì e
1
 e
2

STT Mức Giải thích
1 NSD
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ó 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ừ nộ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
GV hướng dẫn: PGS. TS. Trần Văn Sơn Trang 21/30
Tiểu luận Môn học Lập trình Mạng nâng cao
ứ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)
Ở mức hệ thống, ta có thể nói rằng các tác động là phần tử nhỏ nhất không thể chia
cắt được nữa.
Cho một tập hợp giao dịch M={T1, T2…, Tn} lần lượt được thực hiện bởi các tiến
trình độc lập p1, p2,…,pn. Việc thực hiện tuần tự có nghĩa là thực hiện tất cả các giao
dịch của M theo kiểu nối đuôi nhau và tuân thủ một trật tự nào đó. Sự gắn bó của hệ được
bảo toàn theo định nghĩa là bằng việc thực hiện riêng biệt từng giao dịch. Do vậy, nó
cũng được bảo toàn trong chế độ thực hiện tuần tự của M.
Nếu vì lý do hiệu quả, nhiều giao dịch được thực hiện song song thì sự gắn bó
không còn đảm bảo được nữa.
Một yêu cầu khác nữa rất quan trọng là trong quá trình thực hiện hệ phải đảm bảo
cho các tác động không bị ngắt quãng.
III.2. Trật tự hóa các tác động
Trở lại với tập hợp giao dịch M = {T1, T2…, Tn} cho ở phần trước. Mỗi giao dịch
được cấu tạo từ một dãy các tác động. Bằng các tác động không chia sẻ được này, toàn
bộ sự việc thực hiện của tập hợp các giao dịch M bởi một tập hợp các tiến trình tương
tranh là tương đương với việc thực hiện một dãy S các tác động thuộc các giao dịch này,
như S = (a1, a2, , an) chẳng hạn. Trong trật tự tuân thủ trật tự nội tại của từng giao

cập được tiến hành theo kiểu tương tranh.
• Giao dịch hai pha: 1. Toàn bộ đối tượng bị cài then vẫn ở trong tình trạng
cài then cho đến cuối giao dịch và 2. Không có then cài nào có thể diễn ra
tiếp theo một then cài khác trong cùng một giao dịch.
Bây giờ ta tưởng tượng rằng các đối tượng được phân tán trên nhiều trạm khác nhau
và được nối với nhau thông qua hệ thống viễn thông và rằng các tiến trình diễn ra trên
các trạm khác nhau. Hệ thống viễn thông cho phép các tiến trình trên các trạm khác nhau
có thể trao đổi các thông điệp với nhau. Ta giả định rằng các tiến trình và các phương
tiện truyền thông là các đối tượng có thể rơi vào sự cố. Một hệ quản lý tập hợp thông tin
phân tán bao gồm:
STT Cơ chế
GV hướng dẫn: PGS. TS. Trần Văn Sơn Trang 23/30
Tiểu luận Môn học Lập trình Mạng nâng cao
1
Cơ chế 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, ngay cả khi các tác động này diễn ra trên các
trạm khác nhau.
2
Cơ chế đ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ơ chế 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 Cơ chế phục hồi các giao dịch đã hủy bỏ hay xử lý các 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 những điều vừa nêu ở trên, người ta đòi hỏi giao dịch phải có các