ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA
TIỂU LUẬN MÔN HỌC
LẬP TRÌNH MẠNG
Đề tài :
VIẾT CHƯƠNG TRÌNH CÀI ĐẶT
VIẾT CHƯƠNG TRÌNH CÀI ĐẶT
THUẬT TOÁN LAMPORT TRÊN n
THUẬT TOÁN LAMPORT TRÊN n
SERVER, n>3
SERVER, n>3
GVHD: PGS.TS LÊ VĂN SƠN
HVTH: Trần Ngọc Chinh
LỚP: KHMT – K17
GVHD: PGS.TS LÊ VĂN SƠN
HVTH: Trần Ngọc Chinh
LỚP: KHMT – K17
2
Nội dung trình bày

Yêu cầu bài toán
Yêu cầu bài toán

Hướng giải quyết bài toán
Hướng giải quyết bài toán

Thuật toán loại trừ tương hỗ
Thuật toán loại trừ tương hỗ

Thuật toán Lamport cải tiến (Ricart-
Thuật toán Lamport cải tiến (Ricart-

đổi giữa các server.

Xây dựng đoạn chương trình sắp xếp các
Xây dựng đoạn chương trình sắp xếp các
thông điệp đến căn cứ vào giá trị đồng hồ
thông điệp đến căn cứ vào giá trị đồng hồ
Lamport.
Lamport.

Xây dựng chương trình quan sát trình tự
Xây dựng chương trình quan sát trình tự
sắp xếp tại các server trên màn hình.
sắp xếp tại các server trên màn hình.
4
Hướng giải quyết

Sử dụng thuật toán loại trừ tương
Sử dụng thuật toán loại trừ tương
hỗ.
hỗ.

Sử dụng thuật toán Lamport cải
Sử dụng thuật toán Lamport cải
tiến (Ricart-Agrawala)
tiến (Ricart-Agrawala)

Xây dựng cấu trúc thông điệp trao
Xây dựng cấu trúc thông điệp trao
đổi giữa các Server
đổi giữa các Server

có
thể không giống như trật tự phát.
thể không giống như trật tự phát.

Nếu
Nếu
có nhiều thông điệp đến cùng
có nhiều thông điệp đến cùng
một lúc
một lúc
thì việc sắp xếp chúng phải
thì việc sắp xếp chúng phải
theo kiểu
theo kiểu
loại trừ trương hỗ
loại trừ trương hỗ
trong
trong
hàng đợi cục bộ của trạm có chứa
hàng đợi cục bộ của trạm có chứa
chương trình cung cấp.
chương trình cung cấp.
6

Giới thiệu thuật toán
Giới thiệu thuật toán

Ricart-Agrawala là một thuật toán để loại trừ lẫn nhau trên
một hệ phân tán.


P2
P3
Request(P1,8)
Request(P1,8)
Request(P1,8)
1
1
1
Request(P2,12)
Request(P2,12)
Request(P2,12)
2
2
2
Tiến trình P1 yêu cầu tài nguyên
Tiến trình P2 yêu cầu tài nguyên
9
Thuật toán Ricart-Agrawala (tt)

Khi Pi yêu cầu tài nguyên
Khi Pi yêu cầu tài nguyên
P1
P2
P3
1
1
1
2
2
2

Khi giải phóng tài nguyên
P1
P2
P3
2
2
Release(is OK)
12
Cách xác định giá trị đồng hồ logic

Bước 1
Bước 1
:
:
Tất cả các trạm (
Tất cả các trạm (
tiến trình - P
tiến trình - P
i
i
) sử dụng
) sử dụng
một bộ đếm (
một bộ đếm (
đồng hồ - C
đồng hồ - C
i
i
) với giá trị khởi tạo là
) với giá trị khởi tạo là

i
= C
= C
i
i
+ d (
+ d (
d>0, thường d=1
d>0, thường d=1
)
)

Bước 3
Bước 3
:
:
Mỗi thông điệp mang giá trị đồng hồ
Mỗi thông điệp mang giá trị đồng hồ
của tiến trình gửi nó tại thời điểm gửi. Khi Pi
của tiến trình gửi nó tại thời điểm gửi. Khi Pi
nhận một thông điệp với timestamp C
nhận một thông điệp với timestamp C
msg
msg
, nó xử
, nó xử
lý như sau:
lý như sau:
1. C
i

7
8
9 10
7
Thời gian vật lý
n
Giá trị đồng hồ.
timestamp
Thông điệp
0
1
2
3
4
6
8
7
Các sự kiện logic đồng thời
14
Xây dựng cấu trúc các loại thông điệp

Thiết kế cấu trúc chung của các thông điệp
Thiết kế cấu trúc chung của các thông điệpLamport @$ ServerRecei "|" ServerSend "|” CodeMess "|” Data $@
Trong đó:
Lamport: Trường giá trị của đồng hồ Lamport
ServerRecei: Trường tên Server nhận dữ liệu
ServerSend: Trường tên Server gửi dữ liệu

năng phát và nhận thông điệp.

Cài đặt chương trình sắp xếp các thông điệp đến căn cứ
vào giá trị của đồng hồ lamport

Giám sát trình tự sắp xếp tại các server.
17
Kết luận

Hạn chế
Hạn chế

Chưa khắc phục được hiện tượng tràn bộ nhớ khi hoạt
động ở chế độ tự động.

Chưa kiểm soát tối ưu các thông điệp đến và đi khi đồng
thời có nhiều thông điệp phát sinh.

Hướng phát triển
Hướng phát triển
Khắc phục những hạn chế trên.

Nghiên cứu thêm các thuật toán tối ưu để đồng bộ hóa các
tiến trình.

Đề tài này làm cơ sở để có thể xây dựng các chương trình
ứng dụng về hệ phân tán vào thực tế.