Lập trình bộ tuần tự tuần hoàn trên vòng tròn ảo
ĐẠI HỌC ĐÀ NẴNG
ĐẠI HỌC BÁCH KHOA
KHOA CÔNG NGHỆ THÔNG TIN

TIỂU LUẬN MÔN
LẬP TRÌNH MẠNG
Giáo viên hướng dẫn : PGS.TS. Lê Văn Sơn
Nhóm thực hiện nhóm 6 : Trương Văn Hiệu
Trần Thị Hà Khuê
Lớp : KHMT - K11
Nhóm 6: Trương Văn Hiệu – Trần Thị Hà Khuê Trang 1
Đà Nẵng, 03/2010
Lập trình bộ tuần tự tuần hoàn trên vòng tròn ảo
MỤC LỤC
MỤC LỤC 2
LỜI MỞ ĐẦU 3
PHẦN I CƠ SỞ LÝ THUYẾT 4
CHƯƠNG I TỔNG QUAN VỀ BỘ TUẦN TỰ TUẦN HOÀN 4
I.1Khái niệm bộ tuần tự tuần hoàn 4
I.2Ấn phong 4
I.3Vòng tròn ảo 5
II.1Ấn phong bằng biến trạng thái 6
II.2Jecton tuần hoàn 7
CHƯƠNG II GIỚI THIỆU VỀ CÁC PHƯƠNG ÁN CÓ SỰ CỐ 8
II.1 Giới thiệu về bộ tuần tự trên kênh lan truyền 8
II.2 Thuật toán khai phép toán Ticket() 9
II.2.1Hoạt động của hệ thống không có sự cố 9
II.2.2Xử lý trong trường hợp có sự cố 9
II.3 Thuật toán bầu cử trong mạng Ring 10
II.3.1Giới thiệu chung 10

cấu hình của các biến trạng thái và quay trên vòng tròn ảo luôn luôn theo một chiều
xác định. Để vòng tròn có thể hoạt động tốt, thì cần thiết phải xây dựng lại vòng tròn
khi có một trạm nào đó bị sự cố. Phép xử lý này gọi là cấu hình lại bao gồm cả việc
cập nhật lại các giá trị của suc[i] và pred[i] của các trạm hàng xóm của trạm bị sự
cố.
Việc nghiên cứu, phát triển xây dựng một hệ thống phân tán dựa trên vòng tròn
ảo. Các phương pháp đảm bảo gắn bó dữ liệu trong môi trường phân tán đến nay đã
có một số thành công đáng kể. Tuy nhiên, trong quá trình triển khai lập trình và vận
hành các hệ thống đăng ký, vấn đề gắn bó dữ liệu trong các cơ sở dữ liệu khi hệ thống
bị sự cố đang đặt ra như là vấn đề quan trọng và có ý nghĩa sống còn trong việc phát
triển toàn hệ nói chung.
Nói tóm lại, sự cố trong các hệ thống nói chung, hệ thống đăng ký nói riêng có
thể xảy ra và là nguyên nhân dẫn đến hệ thống cơ sở dữ liệu không thể đảm bảo tính
gắn bó được nữa. Vì vậy, cần phải có một hệ cho biết trạng thái của các server dựa
trên chu kì của vòng tròn. Còn gọi là bộ tuần tự tuần hoàn dựa trên vòng tròn ảo.
Đây cũng chính là vấn đề sẽ được nghiên cứu và giải quyết trong phạm vi tìm hiểu của
tiểu luận môn học « Lập trình mạng » - Do Tiến sĩ. Lê Văn Sơn hướng dẫn.
Cám ơn TS. Lê Văn Sơn đã giảng dạy, hướng dẫn, cung cấp tài liệu để cho tôi
nắm vững được kiến thức môn học này.
Nhóm 6: Trương Văn Hiệu – Trần Thị Hà Khuê Trang 3
Lập trình bộ tuần tự tuần hoàn trên vòng tròn ảo
PHẦN I CƠ SỞ LÝ THUYẾT
CHƯƠNG I TỔNG QUAN VỀ BỘ TUẦN TỰ TUẦN HOÀN
I.1 Khái niệm bộ tuần tự tuần hoàn
Bộ tuần tự được giới thiệu nhằm mục đích đánh số thứ tự, sắp xếp các sự
kiện của hệ và tránh được một số nhược điểm mà một số phương khác đã mắc
phải.
Bộ tuần tự là đối tượng đồng bộ hóa cung cấp cho mỗi yêu cầu một số có
giá trị nguyên dương (hay còn gọi là một tíc kê) nhằm xác lập trật tự. Hai yêu
cầu kế tiếp nhau được thể hiện bởi hai số nguyên liên tiếp, trong đó giá trị 0

I.3 Vòng tròn ảo
Để triển khai một ấn phong có kết quả, đầu tiên ta cần phải xác định hành
trình của nó trong mạng máy tính. Ta có thể xem các trạm được lắp đặt trên một
vòng tròn theo một chiều xác định. Mỗi trạm chỉ liên hệ được với hai trạm gần
nhất (hàng xóm bên trái và hàng xóm bên phải).
Xét một mạng gồm tập hợp N trạm được nối với nhau và một trạm bất kỳ
trong mạng có thể liên lạc với các trạm khác trong mạng một cách dễ dàng. Mỗi
trạm trong mạng được phân phối một lần một số duy nhất từ 0 đến N-1. Một
trạm i bất kỳ trong mạng sẽ có trạm hàng xóm bên phải (hay trạm kế tiếp sau)
mà số của trạm đó là suc[i] và trạm hàng xóm bên trái (hay trạm kề liền trước)
mà số của nó là pred[i]. Lúc này suc[i]=i+1 modulo N và pred[i]=i-1 modulo N.
Sự mô tả này kiến ta hình dung một vòng tròn ảo. Hình vẽ II.1 sau đây mô
phỏng vòng tròn ảo giữa các trạm.
Hình I.1. Mô phỏng vòng tròn ảo
Một số nguyên tắc được đặt ra:
− Ấn phong được cụ thể hóa trên một vài cấu hình của các biến trạng
thái và quay trên vòng tròn ảo luôn luôn theo một chiều xác định.
− Khi có sự cố xảy ra ở một trạm nào đó (giả sử trạm i) thì cần xây dựng
lại (cấu hình lại) vòng tròn để vòng tròn có thể hoạt động tốt. Tức là phải cập
nhật lại các giá trị của suc[i] và pred[i] của hàng xóm bên phải và bên trái của
trạm bị sự cố (với điều kiện trạm bị sự cố không phá hủy hoàn toàn liên kết lô
gích)
− Khi một trạm bị sự cố đã được khắc phục và hoạt động trở lại thì nó có
thể tham gia lại vào mạng thông qua phép chèn.
Nhóm 6: Trương Văn Hiệu – Trần Thị Hà Khuê Trang 5
4
2
1
07 3
6

S[i]≠S[i-1], cho i≠0
S[0]=S[N-1], cho i=0
b. Khi tiến trình Pi có ấn phong, thì nó phải bỏ ấn phong sau một
khoảng thời gian xác định và thay đổi trạng thái của nó.
S[i]:=S[i-1], nếu i≠0
S[i]:=S[i]+1 mod N, nếu i=0
Đây là trường hợp duy nhất mà tiến trình có thể cập nhật các giá trị của
mình. Quyền bình đẳng giữa các trạm được đảm bảo khi tất cả các tiến trình Pi
đều sử dụng thuật toán này. Mỗi tiến trình đều được nhận ấn phong khi đến
phiên mình và vì ấn phong trong mạng là duy nhất nên nếu một trạm sau khi
nhận được ấn phong nhưng lại không vào đoạn găng thì phải lập tức giải phóng
nó.
2. Xét khi có xảy ra sự cố ở một trạm nào đó trong mạng.
Cách khắc phục khi có một sự cố xảy ra trong mạng sẽ được trình bày ở
phần sau, phần này ta sẽ nghiên cứu cách đưa một trạm bị sự cố vào lại trong
mạng. Để đưa một trạm bị sự cố đã được khắc phục xong vào mạng, lúc này ta
phải định lại cấu hình của vòng tròn ảo. Sau đó, tiến trình cần phải khởi động lại
S[i], miễn là trạm j=suc[i] không được phép đọc biến S[j] của mình trong thời
gian vào đoạn găng. Có nghĩa là:
Nhóm 6: Trương Văn Hiệu – Trần Thị Hà Khuê Trang 6
Lập trình bộ tuần tự tuần hoàn trên vòng tròn ảo
Nếu j<i thì S[i]:=S[j] -1 mod K
Ngược lại S[i]:=S[j]
II.2 Jecton tuần hoàn
Ý tưởng: Thuật toán thứ hai [Le Lann], ấn phong được cụ thể hóa bằng một
thông điệp đặc biệt gọi là Jeton (thẻ bài) tuần hoàn trên vòng tròn. Như thế, việc
sự cố trên trạm có thể dẫn đến mất Jeton. Các biến trạng thái được duy trì trên
mỗi trạm cho phép tái sinh Jeton trong trường hợp bị mất.
Thuật toán được triển khai dựa trên ý tưởng này là:
1. Jeton mang giá trị là ν. Mỗi trạm j có một biến trạng thái S[j]. Trước

truyền duy nhất. Các trạm được nối với nhau bởi thiết bị truyền thông (TBTT).
Việc cạnh tranh truy cập đường truyền, việc xử lý các xung đột và việc nhận các
thông điệp được thực hiện thông qua TBTT. Và theo thiết kế, một lúc chỉ có một
thông điệp được truyền.
Ta giả sử rằng mỗi TBTT truyền các thông điệp vào đường truyền theo
trình tự mà trạm liên lạc với nó xác định và truyền lại trạm này các thông điệp từ
đường truyền, kể cả các thông điệp của chính nó. Ngoài ra, ta còn giả định là
đường truyền không hề làm mất mát thông điệp và các TBTT đều sắp xếp các
thông điệp theo một trật tự giống nhau.
Để thực hiện một bộ tuần tự phân tán S, trạm i nào đó cần phải duy trì công
tơ cục bộ và thực hiện cùng một thuật toán
Nhóm 6: Trương Văn Hiệu – Trần Thị Hà Khuê Trang 8
TBTT
K2
J3
K1
J2
I1
J1
Trạm I
I1
I2
TBTT
J1
J2
J3
Trạm J
K2
J3
K1

được sắp xếp cùng với các yêu cầu khác.
- Trạm i xử lý tất cả các yêu cầu Ticket(S) đang có trong hàng đợi của
TBTT của nó. Mỗi khi có một yêu cầu đến từ một trong các trạm khác, thì trạm i
sẵn sàng tăng nội dung công tơ cục bộ của mình lên. Khi có một yêu cầu nào đó
đến từ một trong các tiến trình của chính trạm i thì tiến trình này nhận giá trị
hiện hành của công tơ cục bộ và công tơ này tăng lên một số gia.
II.2.2 Xử lý trong trường hợp có sự cố
- Sự cố hay gián đoạn vật lý tại một trạm nào đó được phát hiện sẽ ngay 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ạm bị sự cố sẽ
không lien lạc được với mạng). Chính vì vậy mà sự cố xảy ra với trạm chưa vào
được trong đoạn găng không làm rối loạn hoạt động của giải thuật với điều kiện
là nó gây ra việc truyền thông điệp vang_mat (vắng) cho việc chuyển tải ở tầng
giao vận. Do có trang bị như thế, việc vào đoạn găng trở nên không được nhanh
chóng và dễ dàng cho các trạm khác. Nếu trạm có sự cố đã gởi yêu cầu, thì nó
kết thúc với lý do trở thành trước đối với tất cả các trạm khác.
- Khi một trạm lại được đưa vào trong mạng sau khi đã khắc phục sự cố, nó
cần phải kiến tạo lại trạng thái hiện hành của các yêu cầu. Để đảm bảo điều đó,
nó phát đi thông điệp vao_lai (xin vào lại) và để trả lời, các trạm gởi hoặc thời
gian của yêu cầu cuối cùng của nó REQ không được thỏa mãn (nếu có tồn tại
một REQ) hoặc một thông điệp REL. Mạng cần phải bổ khuyết cho các trạm bị
sự cố bằng cách gởi thông điệp vang_mat. Khi nó đã nhận tất cả các trả lời cho
thông điệp vao_lai, trạm vừa đưa vào đó có thể bắt đầu lại bằng các yêu cầu
- Để có thể tự tham gia lại công việc trong mạng sau sự cố, trạm i phải gởi
yêu cầu vào lại cho một trạm nào đó trong số các trạm còn lại, ví dụ như j chẳng
hạn và đặt mình vào trạng thái lắng nghe đường truyền trong hàng đợi của
TBTT của mình. Trạm j sẽ gởi cho nó một thông điệp đồng bộ để cập nhật. Khi
thông điệp này xuất hiện trong hàng đợi của TBTT, thì:
1. Trạm j là trạm cần phải gởi thông điệp cho i hiểu rằng nó phải gởi giá trị
hiện hành của công tơ của nó.
2. Trạm i hiểu rằng nó có thể vào lại được trong mạng. Để cho việc đó, nó

bị mất chính vì vậy mà thật là cần thiết để xây dựng một thuật toán để khôi phục
lại Token đã bị mất.
II.3.2 Phạm vi
Thuật toán bầu cử người lãnh đạo được đặt ở lớp Medium Access Sub của
lớp liên kết dữ liệu trong mô hình mạng OSI, tuy nhiên ứng dụng của chúng có
lẻ phải trải qua các cuộc bầu cử ở hệ thống phân tán. Thuật toán đã được phát
triễn tùy thuộc vào các đặc tính tương ứng của mạng Ring. Xây dựng thuật toán
khi một node trong mạng Ring gặp sự cố trước, trong, sau quá trình bầu cử thì
mạng sẽ nhanh chóng bầu ra một node lãnh đạo.
II.3.3 Chọn leader
Nhóm 6: Trương Văn Hiệu – Trần Thị Hà Khuê Trang 10
Lập trình bộ tuần tự tuần hoàn trên vòng tròn ảo
Các node trong vòng ring phải chọn ra một node chủ (node được chọn,
elected,leader) để đảm nhiệm việc tính toán trong mạng. Khi một node đã được
chọn, tất cả các node còn lại đều ở trạng thái không được chọn (Non-elected) và
phải hoàn toàn tuân thủ theo node được chọn, cho đến khi một sự lựa chọn khác
xảy ra.
II.3.4 Đặc điểm của vòng ring
Một mạng hình thành một vòng ring nếu tồn tại một liên kết giữa hai node
P(i) và P(j) trong đó i =j+1 hoặc j=i+1 và không còn liên kết nào khác giữa các
node này. Nếu có sự liên hệ giữa node P đến (i+1) mod (P), thì vòng ring là theo
một hướng duy nhất. Thông thường, vòng ring có N node từ 0 đến N-1 và có N
cạnh. Mạng ring gắn liền với thuật ngữ số cạnh đến và số cạnh đi (incoming or
outgoing edges) của một node, luôn luôn bằng 2. Nó đối xứng và hai chiều.
Đường kính của một đồ thị là độ dài tối đa của đường đi ngắn nhất nối giữa hai
đỉnh. Các đỉnh là các node và các cung (arcs) là các kênh thông tin.
II.3.5 Kết quả chọn leader
Có hai vấn đề quan trọng trong việc chọn leader:
1. Đưa ra thông tin về một node được chọn làm leader hay slave.
2. Truyền thông tin về leader đến tất cả các node còn lại.

phối viên”.
Xét trường hợp mạng bị sự cố, hình vẽ sau đây mô phỏng một mạng Ring
có 4 node, tuy nhiên trong đó Node 2 bị sự cố
Mỗi node có ID của nó, node 2 bị lỗi hoặc chưa hoạt động, các node còn lại
đang hoạt động. Ta xét trường hợp khi node 1 khởi tạo sự bầu chọn node. Nó
đánh dấu nó là một người tham gia và gửi đi một thông điệp “bầu chọn” và ID
của nó đến node hàng xóm. Tuy nhiên vì node 2 không gửi trả lại phúc đáp, nó
gửi thông điệp đến node kế tiếp theo chiều kim đồng hồ. theo tuần tự các node
1-3-4.
Nhóm 6: Trương Văn Hiệu – Trần Thị Hà Khuê Trang 12
Hoạt động Hoạt động
Hoạt độngSự cố
12
22
32
42
← Vòng tròn logic
Hình II.2. Mạng Ring gồm 4 trạm (Trạm 2 bị sự cố)

CHƯƠNG 1: RMI VÀ KỸ THUẬT LẬP TRÌNH PHÂN TÁN ĐỐI
TƯỢNG
I.1 RMI và lập trình phân tán đối tượng
Thông thường các chương trình của chúng ta được viết dưới dạng thủ tục
hay hàm gọi và mã lệnh của hàm hay thủ tục được nạp thẳng vào ký ức và thực
thi ngay trên máy cục bộ. Điều mà hầu hết các nhà lập trình quan tâm là đối số
truyền cho hàm và kết qủa mà hàm trả về. Câu hỏi đặt ra là có cách nào nạp nội
dung ở một hàm hay một đối tượng ở một máy nào đó và gọi chúng ở một máy
khác hay không? Đó chính là nội dung của lập trình phân tán đối tượng. RMI
(Remote Method Invoke) có ý nghĩa là triệu gọi từ xa, là cách thức giao tiếp
giữa các đối Java có mã lệnh cài đặt (boa gồm các phương thức và các thuộc
tính) nằm trên các máy khác nhau có thể triệu gọi lẫn nhau. Mô hình triệu gọi
đối tượng phân tán được mô tả bởi hình vẽ sau:
Hình III.1. Mô hình triệu gọi các đối tượng từ xa.
Hai đối tượng A1 và A2 trên máy A gọi phương thức của nhau được gọi là
triệu gọi phương thức cục bộ (Local method Invoke), đây là cách mà lập trình
hướng đối tượng truyền thống vẫn sử dụng. Tương tự ba đối tượng C1, C2, C3
triệu gọi phương thức cục bộ.
Dựa vào giao thức tự gọi từ xa RMI nên đối tượng của Java có thể gọi
phương thức của đối tượng nằm trên một máy khác, ví dụ như ở mô hình trên ta
thấy A1 gọi C1, A2 gọi B1, C3 gọi B1.
Nhóm 6: Trương Văn Hiệu – Trần Thị Hà Khuê Trang 14
A2
C2
C3
C1
B1
Máy B
A1
Máy A

A2
Máy A
A1
C1 stub
C1_skel
C1
Máy C
C1_skel
Lập trình bộ tuần tự tuần hoàn trên vòng tròn ảo
về máy Computer A. Khi A1 trên máy computer A gọi C1 nó sẽ chuyển lời gọi
đến lớp C1_Stub. C1_Stub chịu trách nhiệm đóng gói tham số, chuyển tham số
qua mạng đến máy Computer C lớp nối C1_Skel nhận tham số chuyển vào vùng
không gian địa chỉ tương thích với đối tượng C1 sau đó gọi phương thức tương
ứng.
I.4 Cài đặt ứng dụng phân tán của RMI
Triệu gọi đối tượng RMI giữa Server 2 và đối tượng chủ Server 1. Đối
tượng Calculator/Server 2 sẽ được gọi bởi đối tượng CalculatorClient/Server 1.
Tìm hiểu cơ chế RMI Java
Cơ chế gọi hàm từ xa của các đối tượng RMI một cách tổng quát
1. Đối tượng cài đặt các phương thức và gọi hàm Naming.bind() để đăng
ký với Rmiregistry/Server chủ.
2. Đối tượng trên máy khách muốn gọi phương thức của đối tượng trên
máy chủ trước hết gọi hàm Naming.lookup() để truy tìm tham chiếu đến đối
tượng ở xa theo tên.
3. Bộ đăng ký Rmiregistry sẽ trả về tham chiếu đến đối tượng ở xa thông
qua giao tiếp interface mà đối tượng ở xa cung cấp.
4. Dựa vào interface đối tượng ở máy khách sẽ gọi các phương thức của
đối tượng ở trên máy chủ.
5. Khi một phương thức được gọi, lời gọi sẽ được chuyển tiếp đến lớp
trung gian _Stub. Xử lý chuyển tham số của phương thức gọi đến _Skel trên





Lập trình bộ tuần tự tuần hoàn trên vòng tròn ảo
CHƯƠNG 2: LẬP TRÌNH BỘ TUẦN TỰ TUẦN HOÀN TRÊN
MẠNG RING
II.1 Phân tích bài toán:
II.1 Phân tích bài toán:
Chương trình mô phỏng 4 Server được nối với nhau thành vòng tròn (mạng
Ring). Trong đó, Server 1 là Server khởi tạo. Sau khi Server 1 khởi động xong,
nó sẽ chờ để kết nối với Server 2. Kết nối giữa Server 1 và Server 2 thành công
sau khi Server 2 khởi động xong (OK). Để kiểm tra kết nối có thành công hay
không sau khi Server 1 sẽ gởi một message đến Server 2 là “Server 1 xin chào
Server 2”, sau Server 2 sau khi nhận tin từ Server 1 gởi đến thì nó cũng sẽ trả lời
bằng cách gởi tin nhắn sau đến Server 1 “Server 2 đã nhận tin từ Server 1” để
Server 1 biết rằng hai Server đã kết nối được với nhau.
Tương tự, Server 2 kết nối với Server 3; Server 3 kết nối với Server 4;
Server 4 lại kết nối với Server 1; và cứ tiếp tục như vậy 4 Server này nối với
nhau thành vòng tròn.
Sự cố xảy ra khi một Server gởi message đến Server kia mà không nhận
được message phúc đáp. Nếu phát hiện ra Server nào bị hỏng thì kết nối sẽ bỏ
qua và chuyển kết nối đến Server tiếp theo.
Với đoạn mã lệnh sau:
{
try {
LocateRegistry.createRegistry(port);
Naming.bind(host1,new Server1());
System.out.println ("Server 1 OK");
System.out.println ("Dang Cho ket noi voi Server

public static void connectServer3()
{
try {
client3=(InterfaceServer3)
Naming.lookup(host3);
Nhóm 6: Trương Văn Hiệu – Trần Thị Hà Khuê Trang 19
Lập trình bộ tuần tự tuần hoàn trên vòng tròn ảo
System.out.println (" + Da Ket Noi Voi Server 3");
connectServer3=true;
}catch (Exception ex) {
}
}
public static void connectServer4()
{
try {
client4=(InterfaceServer4)
Naming.lookup(host4);
System.out.println (" + Da Ket Noi Voi Server 4");
connectServer4=true;
}catch (Exception ex) {
}
}
}
II.2 Chương trình Demo
(giả lập các Server chỉ chạy trên một máy)
Màn hình sau khi khởi động Server 1
Màn hình sau khi khởi động Server 2
Nhóm 6: Trương Văn Hiệu – Trần Thị Hà Khuê Trang 20
Lập trình bộ tuần tự tuần hoàn trên vòng tròn ảo
Lúc này màn hình của Server 1 sẽ xuất hiện thêm message trả lời phúc đáp