 Tiểu luận Lập trình mạng nâng cao
BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG

BÁO CÁO TIỂU LUẬN
LẬP TRÌNH MẠNG NÂNG CAO
Đề tài (số 03 - Danh mục đề tài tiểu luận) :
ViẾt chương trình cài đặt thuẬt toán sẮp xẾp theo kiỂu đóng dẤu
1. Nghiên cỨu bẢn chẤt cỦa phương pháp đóng dẤu vào thông điỆp trước
khi gỬi đi cho tẤt cẢ các server qua hỆ thỐng đường truyỀn
2. Xây dỰng hỆ thỐng đa server
3. Xây dựng chương trình monitoring quan sát trường dấu trong hàng đợi các
thông điệp tại các server nhận
HỌC VIÊN : NGUYỄN THANH BÌNH
LỚP : CAO HỌC KHÓA 11
NGÀNH : KHOA HỌC MÁY TÍNH
GVHD : PGS TS. LÊ VĂN SƠN
Đà nẵng, 03/2010
LỜI MỞ ĐẦU
- 1 -
 Tiểu luận Lập trình mạng nâng cao

Trong số những phát minh vĩ đại nhất của thế kỉ trước, thì mạng máy tính
(Computer Network) là một hệ thống đem lại nhiều lợi ích to lớn nhất cho nhân
loại; Điển hình nhất là mạng Internet, hiện nay đang cho phép hàng tỉ máy tính
trên toàn cầu kết nối và làm việc với nhau với tốc độ cao (từ vài chục đến hàng
nghìn kbps).
Điều kỳ diệu trên đang ngày càng phát triển mạnh mẽ, vững chắc là nhờ
các nền tảng cơ sở lí thuyết cho chúng đã được nghiên cứu; Một trong những cơ
sở lý thuyết nền tảng ấy, chính là những lí thuyết nghiên cứu liên quan đến hệ
phân tán. Nhờ có lí thuyết hệ phân tán, mà các bộ vi xử lí đơn lẻ, mà chúng ta

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.
Đặc điểm cần nhấn mạnh của hệ phân tán 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.
Các thao tác chuẩn của hệ phân tán :
1: Tiếp nhận và ghi yêu cầu chỉ dẫn.
2: Dịch yêu cầu để có các thông tin cần thiết. Thực hiện một số công
việc của hệ thống cục bộ như kiểm tra quyền truy cập thông tin, lập hóa
đơn dịch vụ.
3: Gửi kết quả cho hệ thống đã phát yêu cầu.
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 năng cơ bản nhất là đảm bảo cung cấp cho người sử dụng khả năng truy
cập có kết quả đến các tài nguyên vốn có và rất đa dạng của hệ thống như tài
nguyên dùng chung.
Việc định nghĩa các tài nguyên của hệ như tài nguyên dùng chung sẽ
mang đến cho hệ những hiệu năng tốt trong khai thác ứng dụng.
- 3 -
 Tiểu luận Lập trình mạng nâng cao
Các ưu điểm của tài nguyên dùng chung trong hệ phân tán :

các kênh thuộc hệ thống viễn thông.
- 4 -
 Tiểu luận Lập trình mạng nâng cao
CHƯƠNG 3 Bài toán bãi đỗ xe ô tô:
Để 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 1.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ô.
BV
BVBV
BV
BV
BV
BAI
DO XE
VT VT VT VT
VT VT VT VT
VT VT VT VT
VT VT VT VT
VT VT VT
VT VT VT
VT VT
VT VT
VT VT
VT VT
Hình 1.1 Mô phỏng bãi đỗ xe
3.1.1.1. Các tình huống cần quan tâm của bài toán:

3.1.1.2. Ví dụ về không gắn bó:
Để thấy được tầm quan trọng mang tính quyết định của trình tự xử lý
thông điệp đối với yêu cầu gắn bó của hệ, ta hãy tiếp tục xem xét một trường
hợp về không gắn bó của bài toán bãi đỗ xe:
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 BV để có thông tin đó, trạng thái của hệ lúc này là gắn bó. Ba
trong số họ phát đi thông tin cho ở Bảng 1.1 và trình tự phát các thông điệp của
họ được biểu diễn như Hình 1.2:
- 6 -
Bảng 1.1 Thứ tự & nội dung phát thông tin
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
1
2
3
4
100
100
M2
M3
M1
100 100
98
100
99 101
Hình 1.2. Sơ đồ trình tự

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
3 M2 98 M3 99 M2 100 M1 101
Bảng 1.2. Kết quả của sự không gắn bó giữa 4 người bảo vệ
 Tiểu luận Lập trình mạng nâng cao
CHƯƠNG 4 Vấn đề đồng bộ giữa các tiến trình :
Trong các hệ tin học tập trung, vấn đề đồng bộ hóa được giải quyết thông
qua cơ chế loại trừ tương hỗ. Cơ chế này cho phép xác lập trật tự hoàn toàn các
sự kiện.
Trong hệ phân tán, việc đồng bộ hóa chủ yếu yêu cầu 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ự đó có thể thể hiện thông qua
việc trao đổi các thông điệp với nhau.
Một tiến trình nào đó cần sử dụng tài nguyên để phát triển công việc của
mình, phải yêu cầu bộ cung cấp một cách hợp thức bằng cách gửi thông điệp
yêu cầu. Như thế, một tiến trình có nhu cầu tài nguyên sẽ bị treo chừng nào tài
nguyên đó còn chưa được giải phóng hay chưa được cung cấp cho nó.
4.1.1.1. Miền găng
Miền găng: đoạn chương trình mà truy cập vào tài nguyên dùng chung.
Vấn đề miền găng: các sự truy cập chồng lên nhau có thể dẫn đến các kết
quả khác với truy cập tuần tự. Do đó làm thế nào bảo đảm rằng các tiến trình thi
hành miền găng một cách tuần tự chứ không phải là đồng thời; hay nói cách
khác là làm thế nào tuân theo giải thuật loại trừ tương hỗ.
4.1.1.2. Phân nhóm các thuật toán truy cập loại trừ tương hỗ
Truy cập vào miền găng dựa trên sự xác nhận (contention based): Mỗi
tiến trình xác nhận yêu cầu của nó để truy cập vào miền găng. Hay nói cách
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

đi vào miền găng, nó thường sẽ được cấp quyền ngay lập tức sau khi thi
hành thuật toán loại trừ tương hỗ. Đối với trường hợp hợp tải cao hoặc
nặng, luôn luôn có các yêu cầu miền găng phải chờ đợi. Ngay khi một trạm
kết thúc miền găng của mình, nó sẽ có thể cố gắng khởi tạo miền găng
khác.
Nếu gọi E là thời gian trung bình thi hành một miền găng, và T là độ trễ
thông điệp trung bình, thì trong hầu hết các thuật toán, thời gian cho trường
hợp tốt nhất có cận trên là (2T + E). Điều này cho phép trao đổi thông điệp
vòng tròn cộng với sự thi hành miền găng. Thời gian cho trường hợp xấu
nhất là rất nhiều.
4.1.1.3. Sắp xếp kiểu đóng dấu
a. Khái niệm đồ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.
- 9 -
 Tiểu luận Lập trình mạng nâng cao
b. 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”:
Trật tự các sự kiện được xác định dựa trên các nguyên tắc sau:
i. Nếu a và b là hai sự kiện của cùng một trạm P và a xảy ra trước b thì ta
có a→b (trật tự cục bộ).
ii. Nếu a là phát thông điệp từ một trạm P đến trạm Q nào đó và b là nhận

Hình 1.5. ( a→ c): trật tự bắc cầu
 Tiểu luận Lập trình mạng nâng cao
Hình 1.6 Sơ đồ của quan hệ “có trước”:
a → b có nghĩa: chúng ta có thể đi từ a đến b theo sơ đồ bằng cách di
chuyển về phía trước theo thời gian dọc theo các đường tiến trình và thông điệp,
ví dụ p1 → r4
Chúng ta nói rằng a tác động nhân quả đến b
Hai sự kiện là hợp lực nếu chúng có tác động nhân quả với nhau, ví dụ p3
và q3 là hợp lực.
Cho dù q3 xảy ra tại thời điểm vật lý sớm hơn p3, tiến trình P không biết
tiến trình Q đã làm gì tại thời điểm q3 cho đến khi nó nhận được thông điệp tại
thời điểm p4.
c. Gắn thời gian Logic 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:
Để 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.
4.1.1.4. Đồng hồ 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.
- 11 -
∀ sự kiện a,b: nếu a
→
b thì C(a) < C(b)
Điều kiện đồng hồ
 Tiểu luận Lập trình mạng nâng cao
a. Cấu trúc trật tự tổng quát chặt chẽ (Lamport)

Hình 1.7 Minh họa cho dạng thông điệp theo trật tự chặt chẽ
b. 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 Cs đó chính là đồng hồ logic, hoạt động theo các qui tắc sau:
- Gia tăng C
i
thêm một trị số giữa hai sự kiện kế tiếp
- 12 -
P1 P2 P3 P4
0 0 0 0
(a,1,1)
(b,1,4)
3
2
2
3
2
2
•
a
C
i
C
i
+1
 Tiểu luận Lập trình mạng nâng cao
- 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

(REQ, C
i
, i): Một yêu cầu cho việc truy cập vào miền găng CS của tiến
trình Pi. Yêu cầu này được phát đi cho tất các các tiến trình khác.
(REP, C
i
, i): Hồi âm từ tiến trình Pi cho tiến trình Pj khi Pi nhận được
yêu cầu từ Pj.
- 13 -
•
a
C
i
C
i
+1
(T
m
= C
e
(a))
•
P
j
C
r
C
r
= T
m

Thuật toán:
Khi một tiến trình tại trạm S
i
muốn thi hành đoạn găng, nó sẽ gửi thông
điệp REQ có đánh dấu thời gian cho tất cả các trạm trong hệ thống kể có
trạm S
i
.
Mỗi trạm, S
i
, duy trì một hàng đợi chứa các thông điệp yêu cầu được sắp
xếp theo trật tự các dấu thời gian; các đồng hồ logic và quan hệ trật tự toàn
bộ được sử dụng để gắn các dấu thời gian.
Khi một trạm nhận được yêu cầu, nó sẽ đưa thông điệp đó vào hàng đợi
yêu cầu của nó theo thứ tự dấu thời gian và gửi một thông điệp trả lời REP.
Nếu cần, quan hệ trật tự toàn bộ được sử dụng để phá vỡ các sự ràng buộc.
Ý tưởng chung là một tiến trình không thể thi hành đoạn găng của nó
cho đến khi nó nhận được trả lời từ tất cả các trạm khác.
Tóm lại, 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 từ tất cả các trạm còn lại và
 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ận thấy:
- Hoạt động: 3(N-1) thông điệp cần thiết cho mỗi miền găng được thi
hành. (N-1) thông điệp REQ, (N-1) thông điệp REP và (N-1) thông điệp
REL.

i
nhận được thông điệp ACK từ tất cả các
tiến trình khác.
Phần thu của P
i
khi nhận được thông điệp REQ từ P
j
:
a. Nếu P
i
không muốn truy cập vào miền găng CS
i
của nó (nó chưa gửi
đi thông điệp REQ), thì P
i
trả lời với thông điệp ACK.
b. Nếu P
i
đang ở trong miền găng CS
i
thì Pi hoãn lại việc hồi âmcho
đến khi nó rời khỏi miền găng CS
i
.
c. Nếu Pi muốn truy cập vào miền găng CS
i
(nó đã gửi cho tất cả các
tiến trình khác thông điệp REQ), thì P
i
so sánh thời gian lôgic t

j
đang ở trong CS
i
và CS
j
tại
cùng một thời điểm. Đồng thời, giả sử là thời gian lôgic t
i
của yêu cầu mới
nhất của P
i
nhỏ hơn t
j
, thời gian lôgic của yêu cầu mới nhất của P
j
.
- Không đói: Thỏa mãn.
c. Một số Thuật toán khác
Thuật toán tập trung (Assertion Based):
- Có một trạm là trạm điều khiển đảm nhiệm việc cung cấp tài nguyên.
- Các trạm khác khi yêu cầu miền găng sẽ gửi các thông điệp đến trạm
điều khiển.
- Trạm điều khiển duy trì một hàng đợi chứa các yêu cầu và cấp cho mỗi
trạm quyền truy cập vào miền găng theo lần lượt.
- Yêu cầu: 3 thông điệp trên miền găng CS: Request, Grant, Release
- Sd (trễ đồng bộ) = 2T: Release, Grant permission
- Thông lượng: 1/(2T + E)
Thuật toán Token Based:
Một thuật toán dựa trên token sử dụng một token (thông điệp) duy nhất để
xác định tiến trình nào là ở trong miền găng của nó. Chỉ một tiến trình duy nhất

5.1. THUẬT TOÁN LAMPORT DỰA TRÊN ĐỒNG HỒ LOGIC:
CHƯƠNG 6 Đồng hồ Logic:
Đồng hồ logic Lamport dựa trên hai vấn đề sau:
1. Các sự kiện xảy ra trong cùng một bộ xử lý thì chúng luôn ở trong
trạng thái trật tự gắn bó bằng cách sử dụng đồng hồ hệ thống (thời gian
thực) vì giá trị của đồng hồ hệ thống luôn được tăng đều.
2. Các sự kiện xảy ra trong các bộ xử lý khác nhau thì sẽ gây ra tình
trạng không gắn bó trong thời gian truyền thông điệp, nhưng không lâu sau
chúng cũng gắn bó vì nếu bộ xử lý P
j
gửi thông điệp cho bộ xử lý P
k
vào
thời gian T thì P
k
không thể nhận thông điệp đó vào thời gian T hoặc trước
đó.
Tuy nhiên, vấn đề là thời gian thực trên mỗi hệ thống không đồng bộ,
đặc biệt trong hệ phân tán, nó khó giữ được đồng hồ hệ thống chung giữa tất cả
các tiến trình đang sắp xếp. 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, đồ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.
CHƯƠNG 7 Thuật toán Lamport
Đặt T là giá trị đồng hồ thực và C
j
(T) là giá trị của đồng hồ logic trong bộ
xử lý J tại thời gian T, đồng hồ logic hoạt động theo nguyên tắc sau:
1. Đánh dấu mỗi sự kiện bằng giá trị đồng hồ logic của bộ xử lý đó. (với
C
j

Phân tán thuật toán Lamport kéo theo việc phân tán các chức năng cung
cấp mà cần phải điều khiển hàng đợi trên trạm. Do vậy, một trạm chuyên cho
việc tiếp nhận các yêu cầu và các khuyến nghị giải phóng từ các trạm còn lại.
Một trật tự giống nhau trên các trạm chỉ đạt được, nếu ta áp dụng dấu trong
các thông điệp bởi các đồng hồ logic truyền và đánh số trạm. Quan hệ trật tự
toàn bộ được định nghĩa. Thêm vào đó, để cho một trạm có thể ra quyết định
bằng việc tham chiếu duy nhất vào hàng đợi của mình, nó còn cần phải được
nhận một thông điệp của từng trạm khẳng định rằng không có thông điệp nào
trước các thông điệp khác mà đang quá cảnh trên đường.
Giả sử :
1. Trạm i của mạng có thể gửi cho các trạm khác thông điệp có dạng
(T, H
i
, i), trong đó H
i
là dấu của thông điệp có nghĩa là đồng hồ logic
của nó và T có thể nhận một trong ba giá trị REQ, REL, và ACQ.
Ba giá trị này xác định bản chất của ba loại thông điệp khác nhau
STT Thông điệp Giải thích
1 REQ
Thông điệp REQ được phát đi cho tất cả các trạm,
khi trạm i muốn vào trong đoạn găng
2 REL
Thông điệp REL được phát đi cho tất cả các trạm,
khi trạm i đã rời khỏi đoạn găng
3 ACQ Thông điệp ACQ được gửi bởi trạm j cho trạm j đã
- 19 -
 Tiểu luận Lập trình mạng nâng cao
nhận được từ trạm i thông điệp REQ.
2. Khi có một thông điệp được gởi đi bởi trạm i đồng thời nó cũng được

Send M(T,H
j
,j) đến trạm i
INSERT(M
i
,hàngđợi)
End
+ Khi trạm đang vào đoạn găng: Trạm i nhận một thông điệp với đồng hồ
logic lớn hơn đồng hồ ở thời điểm hiện tại của trạm i và yêu cầu của trạm i đang
ở vị trí của hàng đợi yêu cầu của nó.
If (H>H
i
) and (Vị trí M

ở đầu của hàng đợi) then state=namgiu
+ Khi trạm không thực hiện gì cả
- 20 -
M
i
= (REL, H
init
, i)
M
i
= (REL, H
init
, i)
 Tiểu luận Lập trình mạng nâng cao
Xoá yêu cầu và gởi thông điệp giải phóng những trạm khác sẽ loại bỏ
yêu cầu tương ứng

public Lamport() {
c = 0;
- 21 -
 Tiểu luận Lập trình mạng nâng cao
}
public int getValue() {
return c;
}
public void tick() {
c = c + 1;
}
public void sendAction() {
c = c + 1;
}

public void receiveAction(int sentValue) {
if(sentValue > c)
c = sentValue + 1;
else
c = c + 1;
}
}
11.1.1.2. Message.java
Module chứa thông tin và các phương thức của các thông điệp trao đổi
giữa các Server.
import java.net.*;
import java.io.*;
public class Message implements Serializable{
// Method of message
private String method = "";

}
public void setPort(int port){
this.port = port;
}
public Lamport getLamport(){
return lamport;
}
public void setLamport(Lamport lamport){
this.lamport = lamport;
}
}
11.1.1.3. Sắp xếp thông điệp trong hàng đợi
// Sap xep cac message trong hang doi dua theo dong ho Lamport
private void sort(Vector queue){
Message tmp = new Message();
- 23 -
 Tiểu luận Lập trình mạng nâng cao
for(int i=0; i < queue.size() -1; i++)
for(int j=i+1; j < queue.size(); j++)
if(((Message)queue.get(j)).getLamport().getValue() >
((Message)queue.get(i)).getLamport().getValue())
{
tmp = (Message)queue.get(j);
queue.setElementAt(queue.get(i), j);
queue.setElementAt(tmp,i);
}
}
CHƯƠNG 12 Hướng dẫn demo chương trình
12.1.1.1. Yêu cầu hệ thống:
- Máy tính cài đặt Java version 1.5 hoặc mới hơn