Song song hóa thuật toán Lamport trong loại trừ tương hỗ phân tán

Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
Song song hóa thuật toán Lamport trong
loại trừ tương hỗ phân tán
Đặng Hùng Vĩ1, Lê Văn Sơn1, Nguyễn Xuân Huy2
1 Trường Đại học Sư phạm, Đại học Đà Nẵng
2 Viện Công nghệ Thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt Nam
Tác giả liên hệ: Đặng Hùng Vĩ, dhungvi@ued.udn.vn
Ngày nhận bài: 05/04/2019, ngày sửa chữa: 04/12/2019, ngày duyệt đăng: 04/12/2019
Định danh DOI: 10.32913/mic-ict-research-vn.v2019.n2.848
Biên tập lĩnh vực điều phối phản biện và quyết định nhận đăng: PGS.TS. Trần Minh Quang
Tóm tắt: Hệ phân tán là hệ thống cung cấp tài nguyên dùng chung với quy mô lớn. Hệ phân tán sử dụng cơ chế truyền
thông điệp để hợp lực trong môi trường truyền thông. Trong hợp lực, nhiều tiến trình cùng tương tranh tài nguyên dùng
chung dễ dẫn đến bế tắc trong cung cấp tài nguyên. Loại trừ tương hỗ phân tán cho phép chỉ có một tiến trình duy nhất
được thực thi trong miền găng tại một thời điểm đối với một tài nguyên để giải quyết bế tắc. Để đạt được loại trừ tương
hỗ phân tán, các tiến trình phải được gắn dấu đồng hồ lô-gic để xác lập trật tự và loại trừ các tiến trình gây ra bế tắc.
Bài báo trình bày giải pháp song song hóa thuật toán Lamport trong loại trừ tương hỗ phân tán. Kết quả giải pháp là xác
lập giá trị đồng hồ lô-gic dựa trên song song hóa thuật toán Lamport và xác định các tiến trình thực thi trong đảm bảo
tính nhất quán và gắn bó trong hệ phân tán.
Từ khóa: Hệ phân tán, đồng hồ lô-gic, thuật toán Lamport, loại trừ tương hỗ phân tán, truyền thông điệp.
Title: A Parallelization of the Lamport Algorithm for Distributed Mutual Exclusion
Abstract: A distributed system is a complex system in which the shared resources are allocated at a large scale. Such a system
uses the message passing mechanism over the communication environment to coordinate the system’s entities. During
coordination, multiple concurrent processes might request the same resources, leading to deadlock in resource allocation.
In order to resolve this deadlock, distributed mutual exclusion allows only one process to be executed in the critical
section at a time for each shared resource. To this end, each process is assigned a timestamp to establish an order, and the
processes that cause deadlock are eliminated. There are several proposed distributed mutual exclusion algorithms such
as by Lamport, Ricart–Agrawala, Raymond, and Suzuki–Kasami. In this paper, we develop a parallelization of Lamport
algorithm for distributed mutual exclusion. Our solution establishes a global state and determines the implementation
process in the critical section to ensure consistency and coherence in discrete systems.
Keywords: Distributed system, logical clock, Lamport algorithm, mutual exclusion distributed, message passing.
I. GIỚI THIỆU
Hiện nay, các ứng dụng lớn trên môi trường điện toán
đám mây được triển khai trong hệ phân tán để đáp ứng số
lượng người dùng cực đại. Theo nghiên cứu trong [1], đám
mây là một hệ thống song song và hệ phân tán bao gồm
một tập hợp các máy chủ được kết nối và ảo hóa, được
cung cấp động và được xử lý dưới dạng một hoặc nhiều
tài nguyên tính toán hợp nhất dựa trên các thỏa thuận cấp
dịch vụ được thiết lập thông qua thỏa thuận giữa nhà cung
cấp dịch vụ và người dùng. Điện toán đám mây là một giải
pháp toàn diện cung cấp hạ tầng, dịch vụ công nghệ thông
tin. Đây là một giải pháp điện toán dựa trên internet cung
cấp tài nguyên dùng chung thông qua hệ phân tán.
Hệ phân tán, được biểu diễn trên hình 1, là một tập hợp
các máy chủ kết nối qua môi trường truyền thông trong
cung cấp tài nguyên dùng chung. Nếu xét hoạt động mỗi
máy chủ một cách độc lập, không có sự phối hợp để chia
sẻ tài nguyên dùng chung thì đây là hệ tập trung. Nếu xét
các máy chủ hợp lực để chia sẻ tài nguyên dùng chung thì
đây là hệ phân tán. Sự hợp lực các máy chủ là sự phối hợp
giữa các máy chủ với nhau thông qua môi trường truyền
thông để cung cấp tài nguyên dùng chung cho người sử
dụng. Khác biệt giữa hệ tập trung và hệ phân tán là các
đặc tính như: tính gắn bó, khả năng chịu lỗi, sự mở rộng,
cân bằng tải, v.v. Các nghiên cứu, triển khai hệ phân tán để
cung cấp tài nguyên dùng chung tập trung vào giải pháp
đảm bảo gắn bó dữ liệu [2]. Giải pháp gắn bó dựa trên
83
Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
Hình 1. Mô hình kết nối trong hệ phân tán cung cấp tài nguyên
dùng chung.
sự hợp lực của các máy chủ trong hệ phân tán thông qua
cơ chế truyền thông điệp [3]. Hệ phân tán không có đồng
hồ dùng chung, do đó, giải pháp của bài báo cải tiến thuật
toán Lamport để giải quyết loại trừ tương hỗ phân tán trong
cung cấp tài nguyên dùng chung.
Nội dung chính của bài báo được tổ chức như sau. Phần II
trình bày các nghiên cứu liên quan. Phần III đề xuất giải
pháp song song hóa thuật toán Lamport trong loại trừ tương
hỗ phân tán. Phần IV trình bày hiệu năng thực thi song song
hóa thuật toán Lamport. Phần V đưa ra kết luận.
Trong toàn bộ bài báo, chúng tôi ký hiệu là số máy
chủ, là độ trễ của quá trình đồng bộ hóa và là thời
gian thực thi miền găng.
II. CÁC NGHIÊN CỨU LIÊN QUAN
Các nghiên cứu trong [4, 5] trình bày về truyền thông
trong hệ phân tán đề cập đến cơ chế truyền multicast. Trong
cơ chế này, gói tin vào và ra một máy chủ không tuân
thủ nguyên tắc về lưu lượng như truyền unicast. Truyền
multicast là sự kết hợp đặc biệt từ các máy chủ kết nối với
máy chủ phát thông tin truyền.
Cơ chế hợp lực sử dụng truyền multicast cho phép các
máy chủ kết nối với nhau thông qua môi trường truyền
thông truyền thông điệp qua lại nhằm xác định các tiến trình
di chuyển trong hệ phân tán [3]. Trong quá trình hợp lực,
nhiều tiến trình cùng tương tranh tài nguyên dùng chung
dễ dẫn đến bế tắc trong cung cấp tài nguyên [6–9].
Theo nghiên cứu của Singhal trong [10], quá trình bế tắc
diễn ra khi hai hay nhiều tiến trình chiếm giữ tài nguyên
dùng chung được giới hạn và đồng thời tiếp tục phát đi yêu
cầu tài nguyên khác đang bị chiếm giữ. Các quá trình này
tạo ra một vòng tròn khép kín làm cho các tiến trình kẹt
chéo lẫn nhau dẫn đến bế tắc trong cung cấp tài nguyên
theo mô tả trong hình 2.
Nhiều giải pháp xử lý phân tán liên quan đến việc chia
sẻ tài nguyên dùng chung giữa các tiến trình khác nhau
Hình 2. Đồ thị cung cấp tài nguyên.
đòi hỏi tài nguyên phải được cung cấp duy nhất cho một
tiến trình tại một thời điểm. Do đó, loại trừ tương hỗ là
giải pháp trong các hệ phân tán cung cấp tài nguyên dùng
chung [3, 4, 11]. Giải pháp loại trừ tương hỗ được giải
quyết dựa trên đồng bộ hóa tiến trình truy cập vào các tài
nguyên dùng chung để đảm bảo tính nhất quán và gắn bó
trong hệ phân tán. Quá trình đồng bộ hóa bằng cách truyền
thông điệp giữa các máy chủ dựa vào môi trường truyền
thông. Loại trừ tương hỗ phân tán tuân thủ các yêu cầu sau:
1) Cho phép một tiến trình duy nhất được thực thi trong
miền găng tại một thời điểm đối với một tài nguyên;
2) Nếu không có tiến trình nào trong miền găng, tiến
trình yêu cầu vào miền găng phải được phép vào và
thực thi trong khoảng thời gian cho phép;
3) Khi có nhiều tiến trình yêu cầu vào miền găng, việc
cho phép có thể bị trì hoãn đến khi được cấp phép;
4) Tiến trình xử lý trong miền găng trong không bị chặn
bởi các tiến trình khác.
Theo thuật toán loại trừ tương hỗ phân tán, Kshemkalyani
và Singhal trình bày quá trình một máy chủ vào và ra khỏi
miền găng, được mô tả như trong hình 3 [4, Mục 9.3, 9.4].
Thông điệp có cấu trúc và chứa một trong ba giá trị: REQ-
CS (yêu cầu vào miền găng), REP-CS (phản hồi chấp nhận
của máy chủ cho phép vào miền găng), và REL-CS (giải
phóng khỏi miền găng). Một máy chủ được phép vào miền
găng khi máy chủ đó tiếp nhận đủ thông điệp REP-CS sau
thông điệp REQ-CS. Máy chủ 푆1 phát thông điệp yêu cầu
REQ-CS vào miền găng tại thời điểm 1. Đến thời điểm 8,
푆1 nhận đầy đủ thông điệp phản hồi REP-CS chấp nhận
và vào miền găng cho đến thời điểm 10 phát thông điệp
REL-CS rời khỏi miền găng sau khi xử lý xong. Trật tự
từng phần trên các máy chủ thể hiện qua bảng I.
Xét truyền thông điệp theo hình 3, nếu một máy chủ
bị sự cố trong quá trình truyền thông điệp, ví dụ đối với
trường hợp truyền thông điệp REP-CS từ máy chủ 푆2 đến
máy chủ 푆1 tại thời điểm 6, 푆1 phải chờ đợi vào miền
găng với khoảng thời gian không xác định. Ngoài ra, thông
điệp trong quá trình truyền có thể bị phân mảnh, thất lạc,
nghẽn, v.v. Các vấn đề này dẫn đến hiệu năng của hệ phân
tán giảm trong quá trình hợp lực. Cụ thể, [4] trình bày hiệu
84
Tập 2019, Số 2, Tháng 12
Hình 3. Quá trình máy chủ vào và ra miền găng [4, Mục 9.3, 9.4].
Bảng I
HOẠT ĐỘNG DIỄN RA TRÊN CÁC MÁY CHỦ TRONG TRẬT TỰ TỪNG PHẦN
Đồng hồ Máy chủ 1 Máy chủ 2 Máy chủ 3
1
푆1 → 푆2: REQ-CS,1,1
푆1 → 푆3: REQ-CS,1,1
2
푆2 → 푆1: REQ-CS,2,2
푆2 → 푆3: REQ-CS,2,2
3 푆2 → 푆1: REQ-CS,2,2 푆1 → 푆2: REQ-CS,1,1 푆2 → 푆3: REQ-CS,2,2
4 푆3 → 푆2: REP-CS,4,3
5 푆3 → 푆2: REP-CS,4,3 푆1 → 푆3: REQ-CS,1,1
6 푆3 → 푆1: REP-CS,6,3
7 푆2 → 푆1: REP-CS,5,2
8 Máy chủ 푆1 vào miền găng
9 푆1 → 푆2: REP-CS,9,1
10
푆1 → 푆2: REL-CS,10,1 푆1 → 푆2: REP-CS,9,1
푆1 → 푆3: REL-CS,10,1
11 Máy chủ 푆2 vào miền găng
năng loại trừ tương hỗ được xác định dựa trên các tham số:
độ phức tạp thông điệp, độ trễ quá trình đồng bộ hóa, thời
gian hồi đáp và thông lượng hệ thống. Bên cạnh đó, hiệu
năng loại trừ tương hỗ dựa trên điều kiện của tải trong hệ
thống. Trong đó tải được xác định bởi tỷ lệ thông điệp đến
yêu cầu thực thi miền găng. Đối với tải thấp, số lượng tiến
trình phải đợi chờ để vào miền găng là rất thấp. Đối với
tải cao, luôn có tiến trình yêu cầu thực thi miền găng phải
chờ trong hàng đợi.
Có hai nhóm giải pháp chính trong loại trừ tương
hỗ. Nhóm thứ nhất là phương pháp tiếp cận dựa
trên token: Ricart-Agrawala [12], Suzuki-Kasami [13],
Mizuno-Neilsen-Rao [14], Neilsen-Mizuno [14], Helary-
Plouzeau-Raynal [15], Raymond [16], Singhal [17], Naimi-
Trehel [18], Mishra-Srimani [19], và Nishio [20]. Nhóm
thứ hai là phương pháp tiếp cận dựa trên quyền: Lam-
port [21], Ricart-Agrawala [22], Carvalho-Roucairol [23],
Raynal [24], Maekawa [25], Sanders [26], Agrawal-El Ab-
badi [27], và Singhal [28]. Hiệu năng của các thuật toán
trong nhóm thứ hai, tính theo số thông điệp cần được truyền,
được khảo sát bởi Velazquez [29] và tóm tắt trong bảng II.
Một so sánh khác được trình bày bởi Yadav và cộng sự
trong [30]. Trong đó, hai giải pháp tiếp cận cho loại trừ
tương hỗ phân tán là giải pháp dựa trên nội dung và giải
pháp dựa trên điều khiển. Giải pháp dựa trên nội dung sử
dụng thuật toán trật tự nhãn thời gian lô-gic và thuật toán
bầu chọn. Giải pháp dựa trên điều khiển sử dụng cấu trúc
cây, cấu trúc truyền broadcast và cấu trúc mạng vòng [31].
Yadav và cộng sự phân tích, so sánh hiệu năng của các
thuật toán loại trừ tương hỗ phân tán. Kết quả được thể
hiện trong bảng III.
85
Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
Bảng II
HIỆU NĂNG CỦA THUẬT TOÁN DỰA TRÊN QUYỀN [29]
Thuật toán Tổng số thông điệp
Lamport [21] 3( − 1)
Ricart-Agrawala [22] 2( − 1)
Carvalho-Roucairol [23] 0 đến 2( − 1)
Raynal [24] 2( − 1)2
Maekawa [25] 3
√
 đến 5
√
Sanders [26] | 푖 − {푖}| + 2|푅푖 − {푖}|
Agrawal-El Abbadi [27] (log )
Singhal [28] ( − 1) đến 3( − 1)/2
Bảng III
PHÂN TÍCH, SO SÁNH HIỆU NĂNG CỦA CÁC
THUẬT TOÁN LOẠI TRỪ TƯƠNG HỖ [30]
Thuật Thời gian Độ trễ Th. điệp Th. điệp
toán hồi đáp đồng bộ tải thấp tải cao
[21] 2 + 3( − 1) 3( − 1)
[22] 2 + 2( − 1) 2( − 1)
[13] 2 + 
[16] log + ( log )/2 log 4
Hướng nghiên cứu của bài báo là song song hóa thuật
toán Lamport trong loại trừ tương hỗ phân tán để giảm độ
phức tạp thông điệp, thời gian hồi đáp và độ trễ đồng bộ.
Cụ thể là đồng bộ hóa các tiến trình dựa trên song song hóa
thuật toán Lamport đạt được trật tự tổng quát chặt chẽ với
độ phức tạp thông điệp 3( −1). Sau đó, các máy chủ hợp
lực để vào miền găng thời điểm sớm hơn trong thuật toán
loại trừ tương hỗ phân tán với thời gian hồi đáp là −1+ ,
độ phức tạp thông điệp là − 1 và độ trễ đồng bộ = 0.
III. SONG SONG HÓA THUẬT TOÁN LAMPORT
1. Trật tự tổng quát chặt chẽ dựa trên song song hóa
thuật toán Lamport
Nhãn thời gian lô-gíc được xây dựng dựa trên thuật toán
Lamport trình bày trong [32]. Thuật toán Lamport cho phép
ghi lại các sự kiện của hệ phân tán. Thuật toán tập trung
vào nguyên lý sau: mỗi máy chủ 푆 đều có trang bị công
tơ với các giá trị nguyên gọi là 푆푖 . Đó chính là đồng hồ
lô-gíc tăng lên giữa hai sự kiện kế tiếp. Máy chủ 푒 phát
thông điệp ghi dấu của mình dựa trên giá trị hiện hành của
 푆푒 . Khi nhận được thông điệp, máy chủ nhận cập nhật
đồng hồ 푆 riêng của mình bằng giải thuật rút gọn [32]:
If 푆 ≤ then
 푆 := + 1;
EndIf.
(1)
Một sự kiện (sk ) sinh ra trong máy chủ 푖 (푆푖) và được
đánh dấu bởi đồng hồ cục bộ gọi là 푆푖 ( ). Nếu sk và
Hình 4. Nhãn thời gian của thông điệp không theo trật tự.
Hình 5. Hoạt động cấp giá trị đồng hồ lô-gic theo thuật toán 1.
sk là hai sự kiện được gửi từ cùng máy chủ 푆푖 đến 푆 푗 , ta
luôn luôn có quan hệ xác định như sau:
sk → sk ⇔ 푆푖 ( ) < 푆 푗 ( ), (2)
trong đó sk → sk thể hiện sự kiện gửi cho sự kiện ,
 푆푖 ( ) < 푆 푗 ( ) thể hiện giá trị đồng hồ máy chủ nhỏ
hơn giá trị đồng hồ cục bộ máy chủ , ký hiệu → biểu thị
phép kéo theo và ký hiệu ⇔ biểu thị phép tương đương.
Tuy nhiên, các nhãn đồng hồ này phải được cập nhật và
nhất quán trên tất cả các máy chủ. Nếu giá trị không được
cập nhật thì việc xử lý thông điệp sẽ bị sai và hoạt động
của hệ sai trật tự theo lý thuyết trật tự như hình 4.
Khi các thông điệp di chuyển qua các máy chủ, giá trị
gửi và nhận có giá trị khác nhau. Chính vì giá trị đồng hồ
sai lệch, khi một máy chủ phát lệnh xử lý đồng thời trên
các máy chủ sẽ dẫn đến sai lệch về các tiến trình được triệu
gọi để xử lý. Do đó, dữ liệu không nhất quán trên tất cả
các máy chủ.
Các máy chủ hoạt động nhận và gửi thông điệp dựa trên
đồng hồ cục bộ của mình theo cơ chế truyền unicast. Do
đó, các máy chủ chỉ biết được trật tự từng phần trên máy
chủ của mình và không nhận biết được các hoạt động trên
máy chủ khác. Trật tự từng phần ảnh hưởng đến hoạt động
tổng quát trong hệ phân tán. Hai vấn đề cơ bản là: (i) giá trị
đồng hồ lô-gic trên các máy chủ không nhất quán; (ii) tiến
trình yêu cầu vào đoạn găng phải chờ đợi cho đến khi nhận
đủ thông điệp có thể gây ảnh hưởng đến các máy chủ khác
hoặc sai lệch khi tiến hành cập nhật dữ liệu. Để giải quyết
bài toán trật tự từng phần, nghiên cứu của bài báo là song
song hóa thuật toán Lamport để xây dựng trật tự tổng quát
chặt chẽ trên các máy chủ theo thuật toán 1.
86
Tập 2019, Số 2, Tháng 12
Thuật toán 1: Song song hóa thuật toán Lamport
Dữ liệu vào:
• Máy chủ 푆푖 ;
• Giá trị đồng hồ lô-gic 푆푖 ;• Hành động act; và
• Sự kiện sk.
Dữ liệu ra: Giá trị đồng hồ lô-gic 푆푖 đã cấp.
1 Khởi tạo hoạt động 푆local = 0;
2 Biến đếm count = 0;
3 count 푆[푆푖 , sk] = 0;
4 Số lượng máy chủ 푆 = ;
5 Lắng nghe sự kiện act;
6 if act = REQ-LAMPORT then
7 푆푖 = 푆local + 1;
8 act = REQ;
9 Thiết lập thông điệp yêu cầu cung cấp giá trị đồng hồ  ...  → 푆3: REL-CS,8,1
Hình 7. Mô tả các tiến trình hoạt động trong miền găng.
Hình 8. Số lượng thông điệp hợp lực đáp ứng các tiến trình để
vào miền găng.
Lamport được xác định dựa trên số lượng thông điệp yêu
cầu trên một máy chủ cho mỗi thực thi miền găng. Đối với
song song hóa thuật toán Lamport yêu cầu −1 thông điệp
REQ, − 1 thông điệp REP, − 1 thông điệp ACC, do
đó, thuật toán yêu cầu 3( − 1) thông điệp. Đối với thuật
toán cải tiến loại trừ tương hỗ của bài báo yêu cầu − 1
thông điệp REQ-CS và không xét thông điệp REP-CS và
REL-CS trong quá trình nhận, do đó, thuật toán yêu cầu
 − 1 thông điệp khi vào miền găng.
Nguyên nhân độ phức tạp thông điệp thuật toán loại trừ
tương hỗ thấp là khi áp dụng song song hóa thuật toán
Lamport, các thông điệp REP-CS và REL-CS đã được nhận
biết và đánh dấu khi yêu cầu giá trị đồng hồ lô-gic trên các
máy chủ. Do đó, máy chủ yêu cầu vào miền găng không
89
Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
cần phải đợi tiếp nhận đủ thông điệp REP-CS và REL-CS.
Ngoài ra, trong quá trình truyền thông điệp trong hệ thống,
thông điệp REP-CS và REL-CS bị phân mảnh hoặc thất lạc
không ảnh hưởng đến quá trình vào miền găng của máy
chủ. Theo kết quả hình 8, đối với số lượng tiến trình yêu
cầu vào miền găng lớn thì số lượng thông điệp hợp lực để
tiến trình vào miền găng càng lớn. Do đó, nếu giảm được
số lượng thông điệp hợp lực thì hiệu năng tiến trình vào
miền găng tăng.
Tham số độ trễ quá trình đồng bộ hóa được xác định
dựa trên khoảng thời gian yêu cầu sau khi máy chủ bắt đầu
phát thông điệp yêu cầu REQ-CS cho đến khi vào miền
Thuật toán 2: Cải tiến thuật toán loại trừ tương
hỗ Lamport
Dữ liệu vào: Tiến trình tt(start,jeton, lamport1,lamport2,
S_act,type,action,circle,content)
Dữ liệu ra: Trật tự tổng quát chặt chẽ tiến trình, tiến trình
vào miền găng và loại trừ tương hỗ nhờ dấu
1 action = tt.action;
2 if action = 1 then
3 sk = REQ-CS;
4 act = REQ-LAMPORT;
5 푆local = LAMPORT(푆local, act, sk);
6 tt(start,jeton, 푆local ,푙 표 푡2,푆local,type,action,
circle,content);
7 req_queue(tt);
8 multicast(RequestCriticalSection(sk,tt));
9 end
10 RequestCriticalSection(sk, 푡푡)
11 푆local = tt.lamport1;
12 푆푖 = tt.푆act;
13 if sk = REQ-CS, 푆푖 < 푆local then
14 sk = REP-CS;
15 act = REQ-LAMPORT;
16 푆local = LAMPORT(푆local, act, sk);
17 tt(start,jeton, 푆푖 , 푆local ,푆푖 ,type,action,circle,content);
18 else if sk = REP-CS, 푆푖 < 푆local then
19 sk = REP-CS;
20 act = REQ-LAMPORT;
21 푆local = LAMPORT(푆local, act, sk);
22 writelog(tt(start, jeton, 푆푖 , 푆local , 푆local, type, action,
circle, content));
23 end
24 return RequestCriticalSection(sk,tt);
25 CriticalSection(sk, tt)
26 content = tt.content;
27 process(content);
28 remove_req_queue(tt);
29 sk = REL-CS;
30 act = REQ-LAMPORT;
31 푆local = LAMPORT(푆local, act, sk);
32 tt(start, jeton, lamport1, 푆local , 푆푖 , type, action, circle,
content);
33 return multicast(NextCriticalSection());
34 NextCriticalSection()
35 if req_queue ≠ ∅ then
36 pop_req_queue(tt);
37 return CriticalSection(sk, tt);
38 end
găng hoặc máy chủ rời miền găng để nhường cho máy chủ
tiếp theo vào miền găng. Trong trường hợp tải cao, nghĩa là
các máy chủ yêu cầu vào miền găng đã nhận đủ thông điệp
phản hồi theo song song hóa thuật toán Lamport (dòng 52
của thuật toán 1) và trên hàng đợi của các máy chủ luôn có
tiến trình sẵn sàng vào miền găng. Máy chủ tiếp theo được
thực hiện tức thì trong miền găng trong trường hợp tải cao
sau khi máy chủ trước vừa rời khỏi miền găng, tham số độ
trễ quá trình đồng bộ hóa được xác định là = 0.
Tham số thời gian hồi đáp được xác định là khoảng
thời gian từ khi gửi yêu cầu vào miền găng cho đến khi
ra khỏi miền găng. Theo mô tả trong hình 7, được tính
bằng công thức sau [4]:
 = + , (3)
trong đó là độ trễ quá trình đồng bộ hóa và là thời
gian thực thi miền găng. Đối với trường hợp áp dụng song
song hóa thuật toán Lamport, máy chủ được phép vào miền
găng ngay tại thời điểm máy chủ cuối cùng bắt đầu phản
hồi thông điệp REP-CS sau thông điệp REQ-CS. Như vậy,
thời gian hồi đáp được xác định như sau. Đối với trường
hợp chờ tiếp nhận máy chủ cuối cùng bắt đầu phát thông
điệp REP-CS, chúng ta có = −1, do đó = −1+ .
Đối với trường hợp đã tiếp nhận đủ thông điệp REP-CS
và đang nằm trong hàng đợi vào miền găng trong lượt tiếp
theo, chúng ta có = 0, do đó = .
Tham số thông lượng hệ thống ký hiệu là được xác
định dựa trên tỷ lệ mà hệ thống thực thi các yêu cầu trong
miền găng. được tính bằng công thức [4]:
 =
1
, (4)
trong đó là thời gian hồi đáp. Đối với trường hợp tải
thấp = − 1 thì = 1/( − 1) + . Đối với trường hợp
tải cao = 0 thì = 1/ .
Ký hiệu là số lượng trung bình thông điệp vào miền
găng trên các máy chủ. Đối với trường hợp tải cao, trên mỗi
máy chủ đều có ít nhất một tiến trình yêu cầu vào miền
găng. Một máy chủ cần phải phát − 1 thông điệp để yêu
cầu vào miền găng. Vì vậy, được xác định như sau:
 =
 − 1
+ + ( − 1)
=
3 − 2
. (5)
Theo công thức (5), nếu số lượng các các chủ lớn ( →∞),
số lượng trung bình thông điệp trên các máy chủ xấp xỉ 3.
Trong khi đó thông số này cho thuật toán Lamport nguyên
thủy là xấp xỉ 7 và cho thuật toán Ricart–Agrawala là xấp
xỉ 5 với số lượng máy chủ tương tự.
Đối với việc áp dụng song song hóa thuật toán Lamport
trong thực thi miền găng, thời gian hồi đáp của tiến trình
yêu cầu miền găng và độ trễ quá trình đồng bộ hóa được
rút ngắn. Kết quả so sánh các thuật toán thể hiện trong
90
Tập 2019, Số 2, Tháng 12
Hình 9. Hiệu năng thực thi song song hóa thuật toán.
Bảng V
SO SÁNH HIỆU NĂNG CỦA THUẬT TOÁN LAMPORT
CẢI TIẾN TRONG LOẠI TRỪ TƯƠNG HỖ PHÂN TÁN
Thuật Thời gian Độ trễ Th. điệp Th. điệp
toán hồi đáp đồng bộ tải thấp tải cao
[21] 2 + 3( − 1) 3( − 1)
[22] 2 + 2( − 1) 2( − 1)
Cải tiến + − 1 − 1
bảng V. Thuật toán Lamport cải tiến khi áp dụng song
song hóa thuật toán Lamport đạt được hiệu năng loại trừ
tương hỗ cao so với thuật toán Lamport và Ricart-Agrawala.
Theo kết quả thực hiện trong hình 9, áp dụng song song
hóa thuật toán Lamport, tiến trình trên máy chủ 푆1 vào
miền găng tại thời điểm 6 và trên máy chủ 푆2 vào miền
găng tại thời điểm 8.
Tiến trình yêu cầu miền găng trên máy chủ 푆1 mô tả cho
trường hợp tải thấp: thời gian hồi đáp = 8 được xác định
từ thời điểm giá trị đồng hồ là 1 cho đến lúc phát thông
điệp rời khỏi miền găng tại thời điểm 8. So với hình 3,
푆1 phải đợi đủ thông điệp phản hồi từ các máy chủ còn
lại tại thời điểm 8 mới bắt đầu vào miền găng, do đó 푆1
có = 10.
Tiến trình yêu cầu miền găng trên máy chủ 푆2 mô tả cho
trường hợp tải cao: thời gian hồi đáp = 8 được xác định
từ thời điểm giá trị đồng hồ là 2 cho đến lúc phát thông
điệp rời khỏi miền găng tại thời điểm 10. Trong trường hợp
tải cao, tiến trình trên 푆2 đã nhận đủ thông điệp phản hồi
và chờ vào miền găng thì tại thời điểm 8 푆2 lập tức vào
miền găng. Đối với trường hợp này, 푆2 không phải chờ đợi
tiếp nhận thông điệp giải phóng khỏi miền găng từ 푆1 như
mô tả trong hình 3. Bên cạnh đó, theo mô tả trong hình 3
nếu thông điệp giải phóng từ 푆1 bị thất lạc hoặc phân mảnh
trong quá trình truyền thì 푆2 phải chờ đợi cho đến khi tiếp
nhận đầy đủ, điều này dẫn đến hiệu năng thực hiện bị giảm.
V. KẾT LUẬN
Trong bài báo này, nghiên cứu giải pháp song song hóa
thuật toán Lamport nhằm cải tiến thuật toán loại trừ tương
hỗ phân tán. Song song hóa thuật toán Lamport cho phép
thiết lập một trật tự tổng quát chặt chẽ và ghi dấu các sự
kiện diễn ra trên các máy chủ. Thuật toán cải tiến gán dấu
cho sự kiện yêu cầu 3( − 1) thông điệp. Khi áp dụng
song song hóa thuật toán Lamport trong thuật toán loại trừ
tương hỗ, tiến trình đi vào miền găng yêu cầu − 1 thông
điệp. Do đó, giải pháp cải tiến của bài báo đạt hiệu năng
cao trong cải tiến thuật toán loại trừ tương hỗ phân tán thể
hiện trong bảng V. Tuy nhiên, để đạt được hiệu năng cao,
độ phức tạp thông điệp song song hóa thuật toán Lamport
để gắn dấu cho tiến trình yêu cầu 3( − 1) thông điệp và
độ dài thông điệp lớn hơn so với các thuật toán gắn dấu
khác. Do đó, đối với hệ thống tải cao thì song song hóa
thuật toán Lamport phải xử lý với số lượng lớn các yêu cầu
giá trị đồng hồ lô-gic trong quá trình hợp lực. Vì vậy, giải
pháp để giải quyết tối ưu hệ thống trong hợp lực và truyền
thông cần được tiếp tục nghiên cứu.
TÀI LIỆU THAM KHẢO
[1] R. Buyya, “Market-oriented cloud computing: Vision, hype,
and reality of delivering computing as the 5th utility,” in
2009 Fourth ChinaGrid Annual Conf., 2009, pp. xii–xv.
[2] G. F. Coulouris and J. Dollimore, Distributed systems:
Concepts and design, 4th ed. Addison-Wesley, 2005.
[3] M. Raynal, Distributed Algorithms for Message-Passing Sys-
tems. Springer, 2013.
[4] A. D. Kshemkalyani and M. Singhal, Distributed Com-
puting: Principles, Algorithms, and Systems. Cambridge
University Press, 2008.
[5] M. Raynal, A. Schiper, and S. Toueg, “The causal ordering
abstraction and a simple way to implement it,” Information
Processing Letters, vol. 39, no. 6, pp. 343–350, 1991.
[6] N. Sharma and A. Parikh, “Deadlock detection and removal
in distributed systems,” International Jour. Engineering and
Computer Science, vol. 2, no. 10, pp. 2900–2902, Oct. 2013.
[7] H. H. C. Nguyen, H. V. Dang, N. M. N. Pham, V. S.
Le, and T. T. Nguyen, “Deadlock detection for resource
91
Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
allocation in heterogeneous distributed platforms,” in Recent
Advances in Information and Communication Technology
2015. Springer, 2015, pp. 285–295.
[8] H. H. C. Nguyen, V. S. Le, and T. T. Nguyen, “Algorithmic
approach to deadlock detection for resource allocation in
heterogeneous platforms,” in International Conference on
Smart Computing, 2014, pp. 97–103.
[9] H. H. C. Nguyen, H. D. Tran, V. T. Doan, and V. T. P. Anh,
“Deadlock avoidance for resource allocation model V VM-
out-of-N PM,” in Context-Aware Systems and Applications.
Springer, 2017, pp. 172–182.
[10] M. Singhal, “Deadlock detection in distributed systems,”
Computer, vol. 22, no. 11, pp. 37–48, 1989.
[11] K. Erciyes and V. Adve, Distributed Graph Algorithms for
Computer Networks. Springer, 2013.
[12] G. Ricart and A. K. Agrawala, “Author’s response to ‘On
mutual exclusion in computer networks’ by Carvalho and
Roucairol,” Commun. of the ACM, pp. 147–148, 1983.
[13] I. Suzuki and T. Kasami, “A distributed mutual exclusion
algorithm,” ACM Transactions on Computer Systems, vol. 3,
no. 4, pp. 344–349, Nov. 1985.
[14] M. Mizuno, M. L. Neilsen, and R. Rao, “A token based dis-
tributed mutual exclusion algorithm based on quorum agree-
ments,” in 11th International Conference on Distributed
Computing Systems, 1991, pp. 361–368.
[15] J.-M. Helary, N. Plouzeau, and M. Raynal, “A distributed
algorithm for mutual exclusion in an arbitrary network,” The
Computer Journal, vol. 31, no. 4, pp. 289–295, 1988.
[16] K. Raymond, “A tree-based algorithm for distributed mutual
exclusion,” ACM Transactions on Computer Systems, vol. 7,
no. 1, pp. 61–77, 1989.
[17] M. Singhal, “A heuristically-aided algorithm for mutual
exclusion in distributed systems,” IEEE Transactions on
Computers, vol. 38, no. 5, pp. 651–662, 1989.
[18] N. Mohamed and T. Michel, “How to detect a failure and
regenerate the token in the Log(n) distributed algorithm for
mutual exclusion,” in Distributed Algorithms. Springer
Berlin Heidelberg, 1988, pp. 155–166.
[19] S. Mishra and P. K. Srimani, “Fault-tolerant mutual exclusion
algorithms,” Journal of Systems and Software, vol. 11, no. 2,
pp. 111–129, 1990.
[20] S. Nishio, K. F. Li, and E. G. Manning, “A resilient mutual
exclusion algorithm for computer networks,” IEEE Transac-
tions on Parallel and Distributed Systems, vol. 1, no. 3, pp.
344–356, 1990.
[21] L. Lamport, “Time, clocks, and the ordering of events in a
distributed system,” Communications of the ACM, vol. 21,
no. 7, pp. 558–565, 1978.
[22] G. Ricart and A. K. Agrawala, “An optimal algorithm for
mutual exclusion in computer networks,” Communications
of the ACM, vol. 24, no. 1, pp. 9–17, 1981.
[23] O. Carvalho and G. Roucairol, “On mutual exclusion in
computer networks,” Communications of the ACM, vol. 26,
no. 2, pp. 146–147, Feb. 1983.
[24] M. Raynal, “Prime numbers as a tool to design distributed
algorithms,” Information Processing Letters, vol. 33, no. 1,
pp. 53–58, 1989.
[25] M. Maekawa, “A Sqrt(N) algorithm for mutual exclusion
in decentralized systems,” ACM Transactions on Computer
Systems, vol. 3, no. 2, pp. 145–159, 1985.
[26] B. A. Sanders, “The information structure of distributed mu-
tual exclusion algorithms,” ACM Transactions on Computer
Systems, vol. 5, no. 3, pp. 284–299, 1987.
[27] D. Agrawal and A. E. Abbadi, “An efficient and fault-tolerant
solution for distributed mutual exclusion,” ACM Transactions
on Computer Systems, vol. 9, no. 1, pp. 1–20, 1991.
[28] M. Singhal, “A dynamic information-structure mutual exclu-
sion algorithm for distributed systems,” in 9th International
Conference on Distributed Computing Systems, 1989, pp.
70–78.
[29] M. G. Velazquez, “A survey of distributed mutual exclusion
algorithms,” Colorado State University, Tech. Rep., 1993.
[30] N. Yadav, S. Yadav, and S. Mandiratta, “A review of various
mutual exclusion algorithms in distributed environment,”
International Journal of Computer Applications, vol. 129,
no. 14, pp. 11–16, 2015.
[31] S. Naseera, “A distributed ring algorithm for coordinator
election in distributed systems,” ICTACT Journal on Com-
munication Technology, vol. 7, no. 3, pp. 1341–1344, 2016.
[32] L. V. Sơn, Hệ tin học phân tán. Nhà xuất bản Đại học
Quốc gia Tp. Hồ Chí Minh, 2002.
[33] D. H. Vĩ and L. V. Sơn, “Cung cấp tài nguyên truyền thông
cho hệ phân tán trong máy ảo,” Journal of Science and
Technology, The University of Danang, vol. 11, no. 108, pp.
90–94, 2016.
Đặng Hùng Vĩ sinh năm 1980 tại Đà
Nẵng. Tốt nghiệp đại học tại Trường Đại
học Bách khoa, Đại học Đà Nẵng năm 2003
chuyên ngành Công nghệ Thông tin. Nhận
bằng Thạc sỹ Khoa học Máy tính năm 2008
tại Đại học Đà Nẵng. Hiện đang là nghiên
cứu sinh chuyên ngành Khoa học máy tính
tại Đại học Đà Nẵng. Lĩnh vực nghiên cứu:
Mạng máy tính, mã mạng, hệ phân tán,
điện toán đám mây.
Lê Văn Sơn sinh năm 1948 tại Điện Bàn,
Quảng Nam. Tốt nghiệp Đại học năm 1978,
bảo vệ luận án Tiến sĩ năm 1997 tại Trường
Đại học Tổng hợp Donesk, Ukraina. Công
nhận Phó Giáo sư năm 2004. Hiện công tác
tại Hội tin học Đà Nẵng. Lĩnh vực nghiên
cứu: Hệ điều hành, mạng máy tính, hệ phân
tán, tính toán đám mây.
Nguyễn Xuân Huy sinh năm 1944 tại
Hải Phòng. Bảo vệ luận án Tiến sĩ năm
1978 chuyên ngành Toán-Tin tại Liên Xô.
Bảo vệ Tiến sĩ Khoa học năm 1988 thuộc
chuyên ngành Công nghệ Thông tin tại Liên
Xô. Công nhận Phó Giáo sư năm 1992.
Nguyên Chủ tịch Hội đồng Tư vấn Giáo
dục Microsoft Việt Nam, Nghiên cứu viên
cao cấp Viện Công nghệ thông tin, Viện Khoa học và Công
nghệ Việt Nam. Lĩnh vực nghiên cứu: Công nghệ phần mềm,
cơ sở dữ liệu.
92