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

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
Nội dung trích xuất từ tài liệu:
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ỔNGTuyể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 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àycó thể là các tiến trình hoặc các trạm, các nút hoặc các máy Server không dùng bộ nhớ chungvà liên lạc với nhau bằng cách duy nhất là trao đổi thông điệp. Mỗi một thành phần như thếhoạt động như một otomat có nghĩa là nó triển khai các phép toán có khả năng thay đổi trạngthái của mình và của toàn hệ thống. Các phép toán thực hiện bằng một trong những thành phần vừa nêu phải được sắp xếp mộtcách tự nhiên theo những trình tự diễn ra. Nếu một tiến trình nào đó cho phép chứa nhiềuluồng, trên hệ thống đơn bộ xử lý, đó chính là trật tự thực hiện các lệnh trên bộ xử lý này.Chính bộ xử lý này đảm nhận vai trò sắp xếp các sự kiện. Việc xác định trật tự các sự kiện trên hệ thống đa bộ xử lý là một vấn đề phức tạp liênquan đến những khó khăn trong việc duy trì một thời gian tuyệt đối gắn bó. Đối với hệ tin họcphân tán, việc thống nhất các giá trị của đồng hồ vật lý để đồng bộ hóa các sự kiện là việc làmkhông khả thi vì những lý do sau đây: Độ trễ của truyền thông. Sự không thống nhất các đồng hồ vật lý theo một chuẩn nhất định. Xử lý không theo thời gian thực.2. Thời gian logic vector 1. Giới thiệu 279Tuyể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 Hệ thống đồng hồ vector được Fidge, Mattern và Schmuck đề xuất. Mỗi đồng hồ là mộtvector n chiều thể hiện bởi n phần tử không âm. Mỗi trạm Si nắm giữ một vector Hi [1..n], vớiHi được gọi là đồng hồ cục bộ của trạm Si (i là số thứ tự của trạm Si trong hệ, 1≤ i ≤n , n là sốtrạm có trong hệ). Hi[j] cho thấy hiểu biết mới nhất của Si về thời gian cục bộ của trạm Sj. Như vậy thời gianvector 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 Si 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ỳ, Si cập nhật lại thời gian logic của nó như sau: Hi[i]=Hi[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 Si 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 Si vào thời điểm gửi. Trạm Sj khi nhận được thông điệp sẽ cập nhật lại đồng hồ logic của nó theo công thức: Hj = sup( Hj ,t); Với sup(u,v)=w; w[i]=max(u[i],v[i]) (u, v, w là các vector n chiều; 1≤i≤n; 1≤i≤n) 3. So sánh hai vector Cho hai vector H1, H2 với kích thước thước n, chúng có thể được so sánh với nhau theo công thức sau đây: H1≤H2 nếu H1[i]≤H2[i] với 1≤i≤ n H ...