Tuyển tập Báo cáo “Hội nghị Sinh viên Nghiên cứu Khoa học” lần thứ 6 Đại học Đà Nẵng - 2008

279
THỜI GIAN LOGIC VECTOR VÀ VẤN ĐỀ ĐỒNG BỘ
HÓA CÁC TIẾN TRÌNH TRONG BÀI TOÁN BÃI ĐỖ XE
NHIỀU CỔNG
LOGIC VECTOR TIME AND SYNCHRONIZATION OF PROCESSES IN PARK
WITH DISTRIBUTED STATIONS

SVTH: NGŨ PHÚC HUY
Lớp 04CCT01, Trường Đại Học Sư Phạm.
GVHD: PGS.TSKH. TRẦN QUỐC CHIẾN
Khoa Tin học, Trường Đại Học Sư Phạm.
TÓM TẮT
Ngày nay, một trong những hướng nghiên cứu quan trọng trong hệ thống phân tán đó là vấn
đề đồng bộ hóa các tiến trình sử dụng tài nguyên dùng chung. Để đạt được điều đó thì chúng
ta phải đảm bảo được trật tự như nhau các thông điệp yêu cầu tài nguyên ở tất cả các
trạm/máy chủ có trong hệ. Đề tài tập trung nghiên cứu vấn đề đồng bộ hóa các tiến trình của
bài toán bãi đỗ xe nhiều cổng với hệ thống thời gian vector (Vector time) của Fidge, Mattern và
Schmuck. Giải pháp này có thể đảm bảo được trật tự nhân quả chặt chẽ của các sự kiện diễn
ra trong hệ thống phân tán, đảm bảo các tiến trình trong bài toán hoạt động hoàn toàn ăn khớp
với nhau và đạt được trạng thái gắn bó tài nguyên thông tin dùng chung.
ABSTRACT
Nowadays, synchronization of processes in distributed system is very important and this
requires people to guarantee the same order among messages sent and received by servers.
This research paper concentrates on vector time invented by Fidge, Mattern and Schmuck,
and synchronization of processes in park with distributed stations. This method can lead to
complete causal order between events, and can satisfy the synchronization of processes and
common information resources in distributed system.
1. Đặt vấn đề
Một hệ thống phân tán bất kỳ nào cũng được cấu tạo từ n thành phần. Các thành phần này

i
(i là số thứ tự của trạm S
i
trong hệ, 1≤ i ≤n , n là số
trạm có trong hệ).
H
i
[j] cho thấy hiểu biết mới nhất của S
i
về thời gian cục bộ của trạm S
j
. Như vậy thời gian
vector cho ta thấy toàn cảnh của thời gian logic giữa các trạm.
2. Cập nhật đồng hồ logic
Các quy luật để một trạm S
i
cập nhật lại đồng hồ logic vector của mình:
 Trước khi thực hiện một sự kiện bất kỳ, S
i
cập nhật lại thời gian logic của nó như sau:
H
i
[i]=H
i
[i] + d
(Với d là một số gia)
 Trước khi gửi một thông điệp m đi, trạm S
i
sẽ gán nhãn thời gian cho thông điệp ấy
theo thời gian t mới nhất của trạm S

<H
2
nếu H
1
≤H
2
và not (H
1
=H
2
).
H
1
||H
2
nếu not (H
1
<H
2
) and not (H
2
<H
1
).
4. Xác lập thứ tự nhân quả giữa hai sự kiện
Việc xác lập trật tự nhân quả của hai sự kiện e
1
và e
2
bất kỳ được thực hiện dựa trên những

.
Quy tắc 3: Nếu hai sự kiện e
1
, e
2
xảy ra trên hai trạm S
i
, S
j
bất kỳ trong hệ (i, j là số
thứ tự của trạm) thì ta có e
1
e
2
 H
i
(e
1
)<H
j
(e
2
).
Quy tắc 4 :Nếu hai sự kiện e
1
, e
2
ta có e
1
||e

thông điệp này sẽ được nhận bởi các tiến trình nhận tạị trạm nhận và đưa vào hàng đợi cục bộ
của nó.
Phân tích bài toán bãi đỗ xe ở trên, chúng ta nhận thấy việc sắp xếp các thông điệp được phát
ra từ các trạm là điều cực kỳ quan trọng để đảm bảo tính đồng bộ của dữ liệu nhằm quản lý tốt
các dòng xe vào và ra. Vấn đề này đặt ra yêu cầu phải duy trì một thời gian tuyệt đối đồng bộ.

4. Giải pháp cho bài toán bãi đỗ xe nhiều cổng
Việc đồng bộ hóa các tiến trình vào và ra trong bài toán bãi đỗ xe được thực hiện nhờ
giải thuật loại trừ tương hỗ phân tán nhờ dấu trên cơ sở thời gian vector.
Gọi n là số trạm trong hệ, m
1
là thông điệp yêu cầu vào bãi, m
2
là thông điệp trả lời của tiến
trình P
j
cho tiến trình P
j
khi nhận được thông điệp yêu cầu từ tiến trình P
i
, m
3
là thông điệp yêu
cầu ra khỏi bãi của tiến trình P
i
. Với i, j là số thứ tự của các trạm trong hệ, 1≤ i ≤n, 1≤ j ≤n, H
1
,
H
2

bằng thông điệp m
2
.
 Tại P
i
sau khi nhận được thông điệp trả lời (từ tất cả các trạm) rồi dựa trên sự
xem xét yêu cầu của nó xem có tiếp tục vào bãi không.
Tiến trình P
i
muốn ra khỏi bãi:
 P
i
gửi thông điệp yêu cầu ra m
3
cho tất cả các tiến trình khác trong mạng.
 Xóa yêu cầu vào tương ứng của nó trong hàng đợi cục bộ.

5. Kết luận
Đề tài nhằm tập trung nghiên cứu về thời gian vector và vận dụng thời gian nhằm tiến hành
đồng bộ hóa các tiến trình trong bài toán Bãi đỗ xe nhiều cổng và đạt được những kết quả sau:
- Mô phỏng bài toán bãi đỗ xe là một hệ thống đa Server trong hệ phân tán.
- Xác lập trật tự nhân quả chặt chẽ của các thông điệp trên cơ sở thời gian vector.
- Dựa vào trật tự nhân quả chặt chẽ giữa các thông điệp, xây dựng giải pháp đồng bộ hóa
dữ liệu giữa các trạm.
- Kết quả thu được cho thấy sự hợp lực chính xác giữa các bảo vệ của các trạm bằng
cách trao đổi thông điệp đã đảm bảo điều khiển chính xác các dòng xe vào và ra.
Những kết quả mà bài toán bãi đỗ xe đạt được là rất đáng khích lệ bởi vì nó có thể phát
triển để giải quyết những bài toán tương tự đặt ra trong thực tế như bài toán đặt vé máy bay,
đặt nơi du lịch, hoặc các ứng dụng lớn như thương mại điện tử, giáo dục điện tử…Đây là
những bài toán cần phân tán các chức năng của nó trên các trạm để thời gian trả lại có kết quả

System, University of Texas.
[8] M.Raynal, M.Singhal (1995), Logical Time: A way to capture Causality in Distributed
System, Institut National de Recherche en infomatique et en automatiue.
[9] Michel Raynal, Mukesh Singhal, Capturing Causality in Distributed Systems, University
of Rennes, Ohio State University.
[10] J.Wetch (1998), Distributed Algorithms and Sysrtem, A&M University.
[11] Friedmann Mattern, VirtualTime and Global State of Distributed Systems, University of
Kaiserslautern, Germany.
[12] William Grosso (2001), Java RMI, O’Relly.
[13] John O
’
Donahue (2002 , Java Database Programming Bible, Wiley.
[14] Chris Adamson, Joshua Marinacci (2002), Swing Hacks, O’Relly.
[15] Dick Steflik, Prashant Sridharan, Richard Steflik (2003), Advanced Java Networking,
O’Relly.
[16] www.javavietnam.org
[17] www.ddth.com