ĐẠI HỌC ĐÀ NẴNG

TIỂU LUẬN LẬP TRÌNH MẠNG
ĐỀ tài: Áp dụng phương án (thuật toán) Le Lann đảm bảo
gắn bó dữ liệu trong CSDL phân tán
Tiểu luận môn học: Lập trình mạng GVHD: PGS.TS.Lê Văn Sơn
Giảng viên hướng dẫn
Giảng viên hướng dẫn
:
: PGS.TS Lê Văn Sơn
Sinh viên thực hiện
Sinh viên thực hiện: Đinh Thị Thiên Anh
: Đinh Thị Thiên Anh
Đỗ Văn Nhỏ
Đỗ Văn NhỏLớp
Lớp
: Khoa học máy tính
: Khoa học máy tính
Khoá
Khoá
: K11
: K11
Đà Nẵng, tháng 03 năm 2010
Đà Nẵng, tháng 03 năm 2010
Học viên thực hiện: Thiên Anh – Văn Nhỏ Trang 2

Tiểu luận môn học: Lập trình mạng GVHD: PGS.TS.Lê Văn Sơn
Giải thuật LeLann để lập trình cho các hệ phân tán gắn bó yếu
1.1 Khái niệm về gắn bó thông tin và các hình thức gắn bó trong hệ phân tán
Để thuận tiện trong việc mô tả khái niệm về gắn bó yếu, trước hết ta định nghĩa
gắn bó thông tin trong hệ phân tán là gì?
1.1.1 Gắn bó thông tin trong hệ phân tán
Các đối tượng khác nhau của hệ thống không phải là các đối tượng độc lập
nhau, chúng quan hệ với nhau bởi tập hợp các quan hệ gọi là các ràng buộc toàn vẹn.
Các ràng buộc này thể hiện sâu sắc các đặc tính riêng biệt của hệ.
Trạng thái của hệ thoả mãn một tập các ràng buộc toàn vẹn gọi là trạng thái
gắn bó.
Một cơ sở dữ liệu nào đó được gọi là gắn bó, nếu nó thỏa mãn một tập các ràng
buộc về toàn vẹn ngữ nghĩa.
Vậy gắn bó yếu là gì?
1.1.2 Gắn bó yếu
Gắn bó yếu cũng là một loại gắn bó thông tin. Khi thông tin của một hệ thống
nằm rải rác trên các nút mạng khác nhau đều đồng bộ với nhau tại mọi thời điểm thì đó
là gắn bó mạnh. Ngược lại, thông tin không được đồng bộ tại mọi thời điểm mà nó chỉ
đồng bộ theo 1 chu kỳ nhất định (có thể là chu kỳ thời gian) thì đó là gắn bó yếu. Tóm
Học viên thực hiện: Thiên Anh – Văn Nhỏ Trang 4
Trước khi cập nhật (thay đổi)
Trong khi cập nhật (thay đổi)
Sau khi cập nhật (thay đổi)
Gắn bó
Không gắn bó
Gắn bó
T
Tiểu luận môn học: Lập trình mạng GVHD: PGS.TS.Lê Văn Sơn
lại, với gắn bó yếu, thông tin không cần phải được cập nhật tức thời giữa các nút mạng
trong một hệ thống nào đó.

Tiểu luận môn học: Lập trình mạng GVHD: PGS.TS.Lê Văn Sơn
LeLann’s Algorithm
1.2.1.2.2 Di chuyển thông điệp (Message Passes)
Tổng số thông điệp di chuyển trên vòng Ring trong các trường hợp:
Trường hợp tốt nhất: n+n-1=2n-1
Trường hợp tồi nhất:
Trường hợp trung bình:
= n(1+
1.3 Áp dụng giải thuật LeLann để lập trình cho các hệ phân tán gắn bó yếu
1.3.1 Bài toán:
Áp dụng giải thuật LeLann để đồng bộ dữ liệu cho các Routers trên vòng Ring
theo chu kỳ thời gian T=30s.
Học viên thực hiện: Thiên Anh – Văn Nhỏ Trang 7
Tiểu luận môn học: Lập trình mạng GVHD: PGS.TS.Lê Văn Sơn
1.3.2 Giải thuật:
Repeat
send(nid); //Gửi thông tin theo chiều kim đồng hồ trên vòng Ring
receive(nid);
update(information); //Cập nhật thông tin
Delay(30s); //Tạm dừng 30s trước phát/nhận thông điệp
Until disconect
Học viên thực hiện: Thiên Anh – Văn Nhỏ Trang 8
Tiểu luận môn học: Lập trình mạng GVHD: PGS.TS.Lê Văn Sơn
Xây dựng hệ thống phân tán với một số Server có khả năng phát/nhận
thông điệp
1.4 Bài toán:
Xây dựng hệ thống đa server có khả năng phát/nhận thông điệp theo hình vẽ
dưới đây.
Nội dung thông điệp ở đây giả sử mang thông tin về độ ưu tiên của các Server,
thông điệp sẽ được phát/nhận theo chiều kim đồng hồ như giải thuật LeLann.

Xây dựng giải pháp gắn bó yếu trên CSDL
1.6 Giới thiệu hệ thống CSDL phân tán
Một cơ sở dữ liệu phân tán là tập hợp nhiều cơ sở dữ liệu có liên đới logic và
được phân bố trên một mạng máy tính.
Từ đó ta định nghĩa: Hệ quản trị cơ sở dữ liệu phân tán (DDMS) là một hệ
thống phần mềm cho phép quản lý các cơ sở dữ liệu phân tán và làm cho việc phân
tán trở nên “vô hình” đối với người sử dụng.
Môi trường của hệ cở dữ liệu phân tán được mô tả qua hình vẽ sau:
Vấn đề được đặt ra làm sao để đảm bảo gắn bó yếu đối với các hệ thống dữ liệu
này.
Hiện tại có rất nhiều giải thuật giải quyết vấn đề gắn bó yếu trên CSDL, chúng
ta sẽ tìm hiểu các giải thuật này ở phần tiếp theo.
1.7 Các thuật toán giải quyết vấn đề gắn bó yếu CSDL
1.7.1 Giải thuật LeLann:
Đã trình bày ở phần trên
Học viên thực hiện: Thiên Anh – Văn Nhỏ Trang 12
Tiểu luận môn học: Lập trình mạng GVHD: PGS.TS.Lê Văn Sơn
1.7.2 Thuật toán đảm bảo sự gắn bó yếu nhờ 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 của đồng hồ logic. Theo đó mỗi 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 được đả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 khác nhau.
Các giao dịch cần 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 rồi ghi, thao tác kiểm tra đọc tức thì trạng thái
hiện hành của một bản sao.
Mỗi một server tiếp nhận các yêu cầu ghi đến từ trạm cục bộ ở thời điểm cho
trước. Nó tiếp nhận các yêu cầu và tính toán trên cơ sở dấu theo tiêu chí lâu nhất. Việc
xác định yêu cầu không được tiến hành ngay tức khắc vì nguyên do ta không thể biết
chắc chắn yêu cầu nào là lâu nhất. Yêu cầu lâu nhất có thể đang truyền trên đường.

Khi một trạm đã có số, 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
duy trì một biến chứa số V được phối hợp với yêu cầu xử lý cuối cùng. Các yêu cầu
mang các số lớn hơn V+1 được lưu trữ trong khi chờ xử lý yêu cầu V+1.
Một trạm khi đã rút một lượng số cần phải được sử dụng hết khi nó đến lượt
tiếp theo tiếp nhận bộ tuần tự nếu không các trạm khác sẽ phải chờ.
1.8 Bài toán gắn bó yếu trên CSDL
1.8.1 Phát biểu bài toán
Giả sử trên một hệ thống mạng viễn thông có các thiết bị định tuyến (router),
mỗi thiết bị ban đầu chứa bảng (dữ liệu) định tuyến của mình. Lúc này các bảng định
tuyến chỉ chứa các địa chỉ mạng của các phần tử kế nối trực tiếp (connected) với chính
nó.
Học viên thực hiện: Thiên Anh – Văn Nhỏ Trang 14
Tiểu luận môn học: Lập trình mạng GVHD: PGS.TS.Lê Văn Sơn
Để tất cả các phần tử trên mạng có thể liên lạc được với nhau, các bảng định
tuyến trên các router phải được cập nhật liên tục. Bài toán đặt ra là xây dựng chương
trình mô phỏng việc cập nhật dữ liệu của các bảng định tuyến trên các router, cụ thể
như sau:
Dữ liệu đầu vào: thông tin các bảng định tuyến của các router được lưu ở file
connected routerX.txt
Trên router 1 có các mạng như sau: 192.168.1.0/30, 192.168.1.4/30,
192.168.1.8/30
Trên router 2 có các mạng như sau: 192.168.1.24/30, 192.168.1.28/30
Trên router 3 có các mạng như sau: 192.168.1.12/30, 192.168.1.16/30,
192.168.1.18/30
Dữ liệu đầu ra: thông tin định tuyến sau khi các router đã trao đổi thông tin với
nhau và được lưu ở file: routing table.txt
Học viên thực hiện: Thiên Anh – Văn Nhỏ Trang 15
Tiểu luận môn học: Lập trình mạng GVHD: PGS.TS.Lê Văn Sơn

[1] Hệ tin học phân tán – TS. Lê Văn Sơn, Nhà xuất bản Đại học quốc gia TP.
Hồ Chí Minh.
[2] Java lập trình mạng – Nguyễn Phương Lan, Hoàng Đức Hải, Nhà xuất bản
lao động – xã hội.
[3] Java™ 2:The Complete Reference, Fifth Edition
[4] Internet: Lê Văn Sơn Trường Đại họcc Sư phạm – Đại học Đà Nẵng, nghiên
cứu phát triển giải thuật quản lý nhiều bản sao cho các ứng dụng phức tạp (researching
to develop algorithm managing multicopies for complicated applications)
[5] Internet: LeLann’s algorithm
Học viên thực hiện: Thiên Anh – Văn Nhỏ Trang 18
Tiểu luận môn học: Lập trình mạng GVHD: PGS.TS.Lê Văn Sơn
Mục lục
ĐẠI HỌC ĐÀ NẴNG 1
1
TIỂU LUẬN LẬP TRÌNH MẠNG 1
Giải thuật LeLann để lập trình cho các hệ phân tán gắn bó yếu 4
Xây dựng hệ thống phân tán với một số Server có khả năng phát/nhận thông điệp 9
Xây dựng giải pháp gắn bó yếu trên CSDL 12
KẾT LUẬN 17
Học viên thực hiện: Thiên Anh – Văn Nhỏ Trang 19