Nghiên cứu và ứng dụng các thuật toán lập lịch vào môi trường tính toán lưới

Tăng Cẩm Nhung Tạp chí KHOA HỌC & CÔNG NGHỆ 65(03): 134 - 138 
134 
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  
NGHIÊN CỨU VÀ ỨNG DỤNG CÁC THUẬT TOÁN LẬP LỊCH 
VÀO MÔI TRƯỜNG TÍNH TOÁN LƯỚI 
Tăng Cẩm Nhung 
Trường Đại học Kỹ thuật Công nghiệp – ĐH Thái Nguyên 
TÓM TẮT 
Nhờ có nhiều tiến bộ trong công nghệ mạng và các nguồn tài nguyên máy tính phong phú, công 
nghệ tính toán lưới đã ra đời và hiện nay là một lĩnh vực nghiên cứu khá hiệu quả. Một đặc điểm 
nổi bật của tính toán lưới đó là có thể kết hợp các nguồn tài nguyên phân tán rộng khắp và cung 
cấp số lượng dịch vụ không nhỏ cho người sử dụng. Để đạt được các mục tiêu đó, hệ thống lập 
lịch hiệu quả là một phần thiết yếu của lưới. Bài báo nghiên cứu và ứng dụng thuật toán lập lịch 
trong mô hình tính toán lưới với mục đích làm giảm thiểu thời gian hệ thống cần thiết để hoàn tất 
các ứng dụng. Một số thuật toán được nghiên cứu đó là: OLB, MCT, Min-Min, Max-Min, 
Sufferage; đồng thời trong bài báo này đưa ra kết quả so sánh về tính hiệu quả giữa các thuật toán 
này khi được áp dụng vào mô hình cụ thể. 
Từ khóa: Tính toán lưới, lập lịch,OLB, MET,MCT,Max-Min, Min – Min, Sufferage, xSufferage 
*ĐẶT VẤN ĐỀ 
Cũng như các công nghệ tính toán khác, tính 
toán lưới (Grid Computing) ra đời xuất phát từ 
nhu cầu tính toán của con người. Thực tế, càng 
ngày càng có nhiều bài toán lớn và phức tạp 
hơn được đặt ra và do đó các tổ chức cũng cần 
phải có những năng lực tính toán mạnh mẽ hơn. 
Có thể giải quyết vấn đề này bằng hai cách: 
Thứ nhất: Đầu tư thêm trang thiết bị, cơ sở hạ 
tầng tính toán (mua thêm máy chủ, máy trạm, 
siêu máy tính, cluster...). Rõ ràng là cách làm 
này hết sức tốn kém. 
Thứ hai: Một cách thực hiện hiệu quả hơn là 
phân bố lại hợp lý các nguồn tài nguyên trong tổ 
chức hoặc thuê thêm các nguồn tài nguyên từ 
bên ngoài (dĩ nhiên là với chi phí rẻ hơn nhiều 
so với việc đầu tư cho cơ sở hạ tầng tính toán). 
Đây là mục tiêu chính của tính toán lưới 
Môi trường lưới cho phép kết hợp các hệ thống 
xử lý lại với nhau để giải quyết một cách hiệu 
quả các nhu cầu ngày càng cao của con người 
[6]. Đặc biệt, đây là một công nghệ có khả năng 
kết hợp các nguồn tài nguyên từ những tổ chức 
khác nhau, phân tán trên phạm vi địa lý rộng và 
đặc biệt là không đòi hỏi các nguồn tài nguyên 
phải tương đồng về cấu trúc [7]. 
 Bài toán lập lịch là một trong những vấn đề 
quan trọng được nghiên cứu trong các môi 
trường tính toán, đặc biệt là các môi trường 
*
 Tel: 0988724824; Email: 
tính toán phân tán như môi trường tính toán 
lưới. Do đặc thù của môi trường lưới như: số 
lượng công việc và các nguồn tài nguyên 
thường rất lớn. Mặt khác các tài nguyên này 
còn nằm phân tán và hỗn tạp, mỗi nguồn tài 
nguyên có thể do một tổ chức riêng biệt quản 
lý, có các chính sách và chi phí hoạt động khác 
nhau, bên cạnh đó tải (load) và tính sẵn sàng 
(availability) của các hệ thống cũng rất khác 
nhau; do đó vấn đề lập lịch (scheduling) trong 
hệ thống lưới có nhiều khó khăn và thách thức 
hơn so với môi trường khác, hiện tại vẫn còn 
đòi hỏi nhiều công sức nghiên cứu [3] 
GIỚI THIỆU BÀI TOÁN LẬP LỊCH 
TRONG MÔI TRƯỜNG LƯỚI[1] 
Bài toán lập lịch là một trong những vấn đề 
quan trọng được nghiên cứu trong các môi 
trường tính toán, đặc biệt là các môi trường tính 
toán phân tán như môi trường tính toán lưới. 
Quá trình lập lịch là quá trình quyết định sẽ 
thực thi công việc tại một nguồn tài nguyên 
cụ thể nào và vào thời điểm nào là thích hợp 
nhất do đó sẽ ảnh hưởng rất lớn đến hiệu năng 
hoạt động của hệ thống. 
Có khá nhiều vấn đề được đặt ra và cần giải 
quyết khi nghiên cứu về quá trình lập lịch 
trong môi trường tính toán lưới: 
 Mối liên hệ và tác động lẫn nhau giữa 
các ứng dụng trong quá trình thực thi. 
 Những đòi hỏi, yêu cầu khác nhau 
của từng ứng dụng trong hệ thống. 
 Sự không đồng nhất và biến động của 
các nguồn tài nguyên trong môi trường. 
Tăng Cẩm Nhung Tạp chí KHOA HỌC & CÔNG NGHỆ 65(03): 134 - 138 
135 
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  
 Mô hình hoạt động và các chính sách 
về truy xuất, bảo mật  của hệ thống. 
CÁC THUẬT TOÁN ÁP DỤNG TRONG 
BÀI TOÁN LẬP LỊCH THEO HIỆU NĂNG 
CỦA HỆ THỐNG 
Mục đích của phương pháp này hướng đến 
mục đích giảm tối đa thời gian hệ thống cần 
thiết để hoàn tất các ứng dụng, thời gian này 
được gọi là makespan của hệ thống. Một số 
hướng tiếp cận được đề cập đến như OLB, 
MCT, Min-Min, Max-Min, Sufferage 
OLB (Opportunistic Load Balancing) 
Đây là chiến lược rất đơn giản, phân phối 
công việc cho tài nguyên có thời điểm sẵn 
sàng sớm nhất mà không quan tâm đến thời 
gian thực thi của công việc trên tài nguyên đó. 
MET (Minimum Execution Time)[3] 
Ngược lại với OLB, phân phối công việc 
vào các tài nguyên có khả năng thực thi 
công việc nhanh nhất, không quan tâm đến 
thời điểm bắt đầu và kết thúc của công việc 
trên tài nguyên đó. 
Giải thuật này thường có nhược điểm là 
không cân bằng tải vì hầu như các công việc 
đều được tập trung thực thi trên các tài 
nguyên có năng lực cao nhất 
Giả sử ta có 2 tác vụ cần thực thi là T1,T2. 
Các tác vụ lần lượt có kích thước T1=60, 
T2=120 [5]. Hệ thống có 2 máy tính cụm, mỗi 
máy tính cụm có 2 máy tính (host), năng lực 
lần lượt là: 
Cluster 1: H1=30, H2=60 
Cluster 2: H3=45, H4=50 
Gọi Eij = Ti/Hj là thời gian thực thi của tác vụ 
i trên host j, ta có: 
E11=T1/H1=2 E21=T2/H1=4 
E12=T1/H2=1 
(nhỏ nhất) 
E22=T2/H2=2 
(nhỏ nhất) 
E13=T1/H3=1.3 E23=T2/H3=2.6 
E14=T1/H4=1.2 E24=T2/H4=2.4 
Như vậy cả 2 tác vụ đều thực thi trên host H2, 
makespan của hệ thống = 1 + 2 = 3 
MCT (Minimum Completion Time) [3] 
Dựa trên khái niệm thời gian hoàn thành nhỏ 
nhất của tác vụ. Thời gian hoàn thành được 
tính bằng thời gian thực thi của tác vụ cộng 
với thời gian sẵn sàng của tài nguyên. 
Việc dựa trên thời gian hoàn thành nhỏ nhất 
sẽ giúp hệ thống cân bằng tải tốt hơn. 
Áp dụng với các số liệu tương tự như mục 
3.2, ta định nghĩa Cij = Bj + Eij với Cij là thời 
gian hoàn thành của tác vụ i trên host j, Bj là 
thời gian sớm nhất host j có thể thực thi tác 
vụ (thời gian sẵn sàng). 
C11= B1 + E11 
 = 0 + 2 = 2 
C21= B1 + E21 
 = 0 + 4 =4 
C12= B2 + E12 
 = 0 + 1 = 1 
C22= B2 + E22 
 = 0 + 2 =2 
C13= B3 + E13 
 = 0 + 1.3 = 1.3 
C23= B3 + E23 
 = 0 + 2.6 = 2.6 
C14 =B4 + E14 
 = 0 + 1.2 = 1.2 
C24 = B4 + E24 
 = 0 + 2.4 = 2.4 
Tác vụ T1 theo thứ tự được chọn tài nguyên 
trước, sẽ chọn thực thi trên host H2 (thời gian 
hoàn thành thấp nhất). Thời gian bắt đầu B2 
được cập nhật thành 1, vì chỉ sau thời điểm 
này H2 mới có thể thực thi các tác vụ khác. 
Giá trị E22 thay đổi: B2=1 
C22 = B2 + E22= 1 + 2 = 3 > 2.4 
Như vậy tác vụ T2 sẽ thực thi trên Host H4 vì 
có C24 nhỏ nhất. Thời gian thực thi toàn hệ 
thống makespan = 2.4 vì T1, T2 chạy song 
song trên 2 host khác nhau. 
Chúng ta có thể thấy, dựa vào giá trị MCT hệ 
thống sẽ cân bằng hơn dựa vào giá trị MET. 
Giải thuật Min – Min [2] 
Giải thuật Min – Min sẽ tính toán thời gian 
hoàn thành của tất cả các tác vụ trên tất cả các 
tài nguyên hiện có. Tác vụ nào có giá trị MCT 
nhỏ nhất sẽ được phép chọn tài nguyên trước. 
Sau đó cập nhật thời gian sẵn sàng cho tài 
nguyên được chọn, tính toán lại thông số với 
tất cả các tác vụ chưa được điều phối. Quá 
trình lặp lại cho đến khi tất cả các tác vụ đều 
đã chọn được tài nguyên thực thi. 
Ta định nghĩa một số khái niệm: T là tập các 
tác vụ, Hj,k là máy (host) thứ k của cluster j. 
C(Ti,Hj,k) là thời gian hoàn thành tác vụ Ti 
trên host Hj,k. 
Gọi f là một ánh xạ từ Rn vào R, toán tử 
argmin được định nghĩa: 
))((min))(min(arg xfxff Rx
n
Rx
n
Chú thích: Giá trị C(Ti,Hj,k) là thời gian hoàn 
thành của tác vụ Ti trên host Hj,k. Lúc này 
Tăng Cẩm Nhung Tạp chí KHOA HỌC & CÔNG NGHỆ 65(03): 134 - 138 
136 
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  
nếu argminj, k (C(Ti,Hj,k))gồm 2 thành 
phần(
11, ii hc ) thì giá trị 
),( 11 , ii hci
HTC là nhỏ nhất . Host 1
ih 
trên cluster 
1
ic là host có khả năng hoàn tất 
tác vụ Ti sớm nhất. 
Giải thuật Min-Min: 
while(T≠ ) 
 foreach ( TTi ) 
 ( )),((minarg, ,,
11
kjikjii HTChc ) 
 endfor 
 s= )),((minarg 1,1 ihic
ii HTC 
 1,1 shsc
s HT 
 T=T-{T} 
 endwhile 
Áp dụng với các số liệu mục 2 
C11= B1 + E11 
 = 0 + 2 = 2 
C21= B1 + E21 
 = 0 + 4 =4 
C12= B2 + E12 
 = 0 + 1 = 1 (min) 
C22= B2 + E22 
 = 0 + 2 =2 (min) 
C13= B3 + E13 
 = 0 + 1.3 = 1.3 
C23= B3 + E23 
 = 0 + 2.6 = 2.6 
C14 =B4 + E14 
 = 0 + 1.2 = 1.2 
C24 = B4 + E24 
 = 0 + 2.4 = 2.4 
Giá trị MCT(T1)= C12 =1 , MCT(T2)=C22=2 
MCT(T1) nhỏ hơn, do đó tác vụ T1 được chọn 
host H1 để thực thi trước. 
Giá trị E22 thay đổi: B2=1, C22 = B2 + E22= 1 + 
2 = 3 > 2.4 
Như vậy tác vụ T2 sẽ thực thi trên Host H4 vì 
có C24 nhỏ nhất. Thời gian thực thi toàn hệ 
thống makespan = 2.4 vì T1, T2 chạy song 
song trên 2 host khác nhau. 
Giải thuật Max-Min [2] 
Tương tự như giải thuật Min-Min, tuy nhiên 
giải thuật Max-Min cho phép các tác vụ có 
MCT lớn hơn được ưu tiên chọn host để thực 
thi trước. Giải thuật này được đánh giá tốt và 
cân bằng hơn Min-Min vì trong khi các tác vụ 
dài hơn được ưu tiên chọn thiết bị tốt để thực 
thi trước, các tác vụ ngắn có thể luân phiên 
thực thi ở các thiết bị có năng lực yếu hơn. 
Các tác vụ dài không phải mất thời tác vụ 
ngắn hơn như ở giải thuật Min-Min. 
Toán tử argmax được định nghĩa tương tự 
toán tử argmin 
))((max))(max(arg xfxff Rx
n
Rx
n
Giải thuật Max-Min: 
while(T≠ ) 
 foreach( TTi ) 
 ( )),((minarg, ,,
11
kjikjii HTChc ) 
 endfor 
 s= )),((maxarg 1,1 ihic
ii HTC 
 1,1 shsc
s HT 
 T=T-{T} 
 endwhile 
Áp dụng với các số liệu như mục 2 
C11= B1 + E11 
 = 0 + 2 = 2 
C21= B1 + E21 
 = 0 + 4 =4 
C12= B2 + E12 
 = 0 + 1 = 1 (min) 
C22= B2 + E22 
 = 0 + 2 =2 (min) 
C13= B3 + E13 
 = 0 + 1.3 = 1.3 
C23= B3 + E23 
 = 0 + 2.6 = 2.6 
C14 =B4 + E14 
 = 0 + 1.2 = 1.2 
C24 = B4 + E24 
 = 0 + 2.4 = 2.4 
Giá trị MCT(T1)= C12 =1,MCT(T2)=C22=2 
Lúc này tác vụ T2 có MCT lớn hơn nên được 
phép chọn host thực thi trước. T2 sẽ thực thi 
trên host H2. 
Giá trị B2 = 2, 
C12 = B2 + E12 = 2 + 1 =3 > 1.2 
Như vậy, sau đó tác vụ T1 sẽ thực thi trên host 
H4 vì lúc này C14 =1.2 là nhỏ nhất 
Thời gian hoàn thành của hệ thống makespan 
= 2 vì T1, T2 chạy song song (nhỏ hơn với giải 
thuật Min-Min) 
Giải thuật Sufferage 
Suferage lấy ý tưởng từ giải thuật Min-Min và 
Max-Min đã đề ra trước đó[1]. 
Giải thuật Sufferage tính toán giá trị MCT 
thấp thứ nhất và thấp thứ hai đối với từng tác 
vụ trong hệ thống. Giá trị này được gọi là độ 
“thiệt hại” (suffering) của một tác vụ khi nó 
không được thực thi trên tài nguyên tốt nhất. 
Tác vụ có độ thiệt hại lớn nhất sẽ được ưu 
tiên chọn tài nguyên để thực thi trước. 
Giải thuật Suferage 
while(T≠ ) 
 foreach ( TTi ) 
 ( )),((minarg), ,,
11
kjikjii HTChc 
Tăng Cẩm Nhung Tạp chí KHOA HỌC & CÔNG NGHỆ 65(03): 134 - 138 
137 
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  
)),((minarg),( ,1,1
22
kji
ihkicj
ii HTChc 
 su
fi= )),(),( 1,12,2 ihic
i
ihic
i HTCHTC 
 endfor 
 S= )(maxarg ii suf 
 1,1 shsc
s HT 
 T=T-{T} 
 endwhile 
Giải thuật này đặc biệt hiệu quả nếu tính đến 
vấn đề vận chuyển dữ liệu đến nơi thực thi 
Giải thuật này đặc biệt hiệu quả nếu tính đến 
vấn đề vận chuyển dữ liệu nơi thực thi tác vụ. 
Nếu một tài nguyên đã có sẵn dữ liệu của một 
tác vụ, tác vụ nếu thực thi trên tài nguyên này 
sẽ tiết kiệm được thời gian rất nhiều so với 
khi thực thi trên một tài nguyên khác. Tác vụ 
trong trường hợp này sẽ có giá trị Sufferage 
cao nên được 
Áp dụng với các số liệu như mục 2 
Giá trị Suff (T1)= C14 – C12 = 0.2 
Giá trị Suff (T2)= C24 – C22 = 0.4 
Vì suff (T2) cao hơn nên tác vụ T2 được phép 
chọn host H2 để thực thi trước. 
Giá trị B2 = 2 
C12 = B2 + E12 = 2 + 1 = 3 > 1.2 
Như vậy, sau đó tác vụ T1 sẽ thực thi trên 
host H4 vì lúc này C14 = 1.2 là nhỏ nhất 
Thời gian hoàn thành của hệ thống makespan 
= 2 vì T1, T2 chạy song song. 
C11= B1 + E11 
 = 0 + 2 = 2 
C21= B1 + E21 
 = 0 + 4 =4 
C12= B2 + E12 
 = 0 + 1 = 1 (min) 
C22= B2 + E22 
 = 0 + 2 =2 (min) 
C13= B3 + E13 
 = 0 + 1.3 = 1.3 
C23= B3 + E23 
 = 0 + 2.6 = 2.6 
C14 =B4 + E14 
 = 0 + 1.2 = 1.2 
C24 = B4 + E24 
 = 0 + 2.4 = 2.4 
Ví dụ ở trên khá đơn giản, chỉ có chiều dài 
tác vụ ảnh hưởng đến thời gian thực thi của 
tác vụ nên trường hợp Sufferage khá giống 
Max – Min. 
Giải thuật XSufferage 
Do nhóm nghiên cứu Casanova đề ra, phát 
triển từ thuật toán Sufferage[1]. 
Các máy tính trong một Máy tính cụm thường 
có năng lực như nhau, do đó giá trị sufferage 
thường dần về 0. Điều này khiến một tác vụ 
Ti, khi rất cần chạy trên máy tính cụm j (ví dụ 
dữ liệu input của Ti đã nằm sẵn trên máy tính 
cụm j), nhưng trong trường hợp máy tính cụm 
này lại có 2 máy năng lực tương đương nhau 
khiến Suff(Ti) ≈ 0 nên Ti sẽ không có cơ hội 
chạy trên máy tính cụm j. Cải tiến ở đây là 
khái niệm Suf sẽ được tính ở mức cluster, 
không phải ở mức host. 
Giải thuật 
while(T≠ ) 
 foreach ( TTi ) 
 foreach clusterj 
 hi,j= )),((minarg ,kjik HTC 
 endforeach 
 )),((minarg
,,
1
jihjiji
HTCc 
 )),((minarg
,,1
2
jihji
icj
i HTCc 
 sufi= )),(),( 1,12,2 ihic
i
ihic
i HTCHTC 
 endforeach 
 s= )(maxarg ii suf 
1,
,1
scs
hsc
s HT 
 T=T-{T} 
 Endwhile 
KẾT LUẬN 
Bài báo đã nêu ra cái nhìn tổng quan nhất về 
vấn đề lập lịch trong môi trường lưới, và các 
thuật toán cụ thể được áp dụng cho lưới và 
các đặc điểm của giải thuật trên đó là: 
 Phải duyệt tất cả các máy trong mọi máy 
tính cụm có thể dẫn đến độ phức tạp rất lớn. 
 Ứng dụng rất lớn gồm nhiều tác vụ chạy 
song song, các tác vụ đóng vai trò như nhau. 
 Một tác vụ có thể chạy trên host bất kỳ, 
không có sự ràng buộc về địa điểm thực thi. 
Từ cơ sở lý thuyết của các thuật toán đó đã 
được áp dụng vào hệ thống lưới gồm có hai 
máy tính cụm để chứng minh về tính hiệu quả 
của từng thuật toán đã được nêu ra. 
Tăng Cẩm Nhung Tạp chí KHOA HỌC & CÔNG NGHỆ 65(03): 134 - 138 
138 
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  
TÀI LIỆU THAM KHẢO 
[1] Fangpeng Dong and Selim G. Akl, January 
2006, Scheduling Algorithms for Grid 
Computing:State of the Art and Open Problems, 
Technical Report No. 2006-504, 
[3] Kousalya.K and Balasubramanie.P, April 
2008, An Enhanced Ant Algorithm for Grid 
Scheduling Problem, IJCSNS International 
Journal of Computer Science and Network 
Security, VOL.8 No.4, 
[4] Saurabh Kumar Garg , Rajkumar Buyya and 
H. J. Siegel, 2009, Scheduling Parallel 
Applications on Utility Grids:Time and Cost 
Trade-off Management, Proc. 32nd Australasian 
Computer Science Conference (ACSC 2009), 
Wellington, New Zealand 
[5] Graham Ritchie and John Levine, A fast, 
effective local search for scheduling independent 
jobs in heterogeneous computing environments. 
[6] Ian Foster, C. Kesselman ,Computational 
Grids, Chapter 2 Of "The Grid:Blueprint For A 
New Computing Infrastructure", Morgan-
Kaufman, 1999. 
RESEARCH AND APPLY SCHEDULE ALGORITHMS TO GRID COMPUTING 
ENVIRONMENTS 
Tang Cam Nhung
2
Thai Nguyen University of Tecnology 
Thanks to advances in wide-area network technologies and the low cost of computing resources, Grid 
computing came into being and is currently an active research area. One motivation of Grid computing 
is to aggregate the power of widely distributed resources, and provide non-trivial services to users. To 
achieve this goal, an efficient Grid scheduling system is an essential part of the Grid. This paper refers 
to the scheduling problem of grid system and some of scheduling algorithms applied to grid computing 
model so may reduce the maximum system time needed to complete the application. The algorithms 
are: OLB, MCT, Min-Min, Max-Min, Sufferage and in this paper is to compare the results of efficiency 
between algorithms when the applied to specific models. 
Keywords: grid computing, schedule, Opportunistic Load Balancing, Minimum Execution Time, Minimum 
Completion Time, Max-Min, Min – Min, Sufferage, xSufferage 
2
 Tel: 0988724824; Email: