ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
KHOA KHOA HỌC MÁY TÍNH
BỘ MÔN TÍNH TOÁN LƯỚI


Bài thu hoạch
Các thuật toán lập lịch và quản lý tài nguyên trong môi
trường tính toán lưới
GVHD: PGS.TS Nguyễn Phi Khứ
Học viên: Nguyễn Vĩnh Kha – CH1101096
TP.HCM, tháng 07/2013

- Bài thu hoạch bộ môn Tính toán lưới -
Các thuật toán lập lịch và quản lý tài nguyên trong môi trường tính toán lưới
- 2 -

LỜI CẢM ƠN
Học viên xin bày tỏ lòng biết ơn sâu sắc đến PGS.TS Nguyễn Phi Khứ, trưởng
phòng Hợp tác Quốc tế và Sau Đại học, trường Đại học Công Nghệ Thông Tin, Đại học
Quốc gia TP. Hồ Chí Minh đã tận tình hướng dẫn, cung cấp kiến thức, truyền đạt
những kinh nghiệm quí báu giúp học viên hoàn thành tốt bài thu hoạch này.
Xin cám ơn các Thầy, Cô trường Đại học Công Nghệ Thông Tin, Đại học Quốc
gia TP. Hồ Chí Minh đã hướng dẫn, cung cấp kiến thức giúp học viên thực hiện bài thu

III.1.6. Thuật toán lập lịch GFJS (Grouping-based Fine-grained Job Scheduling) 9
III.1.7. Mô hình lập lịch dựa trên môi trường lưới JSMB (Job Schedule Model
Based) 10
III.2. Quản lý tài nguyên 11
III.2.1. Hệ quản lý tài nguyên động và lập lịch RNDRM 11
III.2.2. Hệ quản lý tài nguyên dựa trên tác tử cùng với giải pháp luân phiên
ABRMAS 12
III.2.3. Cơ chế nhận biết tài nguyên với giải pháp dựa trên tác tử NRMNS 12
III.2.4. IRP2P: Hướng tiếp cận tìm kiếm tài nguyên sử dụng mô hình P2P 13
III.2.5. Lưới điện toán ảo sử dụng vùng chứa tài nguyên VCGRP 14
Chương IV. Khảo sát và đánh giá 15
IV.1. Khảo sát chung và mô phỏng. 15
IV.2. Các so sánh mang tính đánh giá trên các thuật toán lập lịch 17
IV.2.1. Các so sánh mang tính đánh giá trên các thuật toán quản lý tài nguyên 18
Chương V. Tổng kết 19
Danh sách các mô hình, bảng biểu và biểu đồ 20
Tài liệu tham khảo 21
- Bài thu hoạch bộ môn Tính toán lưới -
Các thuật toán lập lịch và quản lý tài nguyên trong môi trường tính toán lưới
- 4 -

Chương I. Giới thiệu chung
Ngày nay, lưới điện toán được xem như một trong những xu hướng hàng đầu trong
việc phát triển các hệ thống phân tán. Một trong những đặc tính ưu việt nhất của lưới
điện toán là khả năng hỗ trợ quản lý các nguồn tài nguyên động, không đồng nhất và
phân tán về mặt địa lý. Đối với các ứng dụng tính toán lưới, quản lý tài nguyên và lập
lịch được xem như những vấn đề then chốt bậc nhất bởi chúng ảnh hưởng trực tiếp đến
hiệu năng của toàn hệ thống. Trong những năm gần đây, giới nghiên cứu đã đề xuất một
số thuật toán lập lịch được sử dụng trong lĩnh vực tính toán lưới. Với các đặc tính của
mình, những thuật toán này được áp dụng để phân bổ tài nguyên lưới cho hệ thống đặt

tài nguyên nhất định cho chúng trên cơ sở các yêu cầu của người dùng và lượng tài
nguyên khả dụng. Trong mô hình này, GIS đóng vai trò nắm giữ thông tin trạng thái
của tất cả tài nguyên trong hệ thống, hỗ trợ bộ phân chia tài nguyên tiến hành lập lịch.
Dưới đây là sơ đồ mô phỏng một hệ thống tính toán lưới căn bản.

Hình I. Mô hình tính toán lưới căn bản

- Bài thu hoạch bộ môn Tính toán lưới -
Các thuật toán lập lịch và quản lý tài nguyên trong môi trường tính toán lưới
- 6 -

Chương III. Các thuật toán quản lý tài nguyên và lập lịch
trong môi trường tính toán lưới
Hiện nay, vấn đề tối ưu hóa lập lịch và quản lý tài nguyên để mang lại hiệu năng
tính toán cao đang trở thành một trong những thách thức chính đối với điện toán lưới
bởi nó là yếu tố then chốt ảnh hưởng đến năng lực hoạt động của cả hệ thống. Trong
chương này ta tiến hành khảo sát một số thuật toán quản lý tài nguyên và lập lịch dành
riêng cho điện toán lưới đã được giới chuyên gia đưa ra trong thời gian gần đây.
III.1.Các thuật toán lập lịch
Về cơ bản, lập lịch là quá trình chỉ định một lượng tài nguyên vật lý trong hệ thống
cho các công việc phát sinh, đồng thời giảm thiểu đến mức tối đa các thành phần hao
tốn tài nguyên trong quá trình hoạt động. Đây có thể được xem là một bài toán thuộc
lớp NP-complete (lớp các bài toán quyết định). Trong phạm vi giới hạn của tài liệu, một
số thuật toán heuristics sẽ được khảo sát với mục đích cuối cùng là tìm ra một giải thuật
tối ưu hay cận tối ưu.
III.1.1.Thuật toán lập lịch HRN
Với kết quả nghiên cứu được đúc kết trong “Efficient Utilization of Computing
Resources using Highest Response Next Scheduling in Grid” [2] K.Somasundaram
và cộng sự đã đề xuất ra thuật toán lập lịch HRN (Highest Response Next) cho phép hệ
thống phản ứng tốt hơn với các yêu cầu về thời gian, bộ nhớ và CPU. Các công việc

công việc. Trong tài liệu, nhóm tác giả cũng chỉ ra rằng ORC hiệu quả hơn khi xét về
mặt cân bằng tải và khả năng tăng tính động của tài nguyên lưới. Ưu nhược điểm của
thuật toán bao gồm:
Ưu điểm:
 Khắc phục được các vấn đề phát sinh khi dùng FCFS và HRN vì ORC khá
phù hợp khi thực hiện phân phối tài nguyên cho nhiều công việc.
 Tối thiểu hóa độ phức tạp của quá trình phân phối tiến trình, giảm thiểu thời
gian xoay vòng và thời gian chờ trung bình của các công việc trong hàng đợi.
 Tránh được hiện tượng không được cấp phát tài nguyên trong thời gian dài.
Nhược điểm:
 Phát sinh truyền thông cao.
III.1.3.Lập lịch phân cấp (Hierarchical Job Scheduling - HJS) cho các cụm
máy trạm
Trong tài liệu “Hierarchical Job Scheduling for Clusters of Workstations” [4], nhóm
tác giả bao gồm J. Santoso, G.D. van Albada, B.A.A. Nazief và P.M.A. Sloot đã đưa
ra thuật toán lập lịch theo mô hình phân cấp. Cụ thể, mô hình bao gồm hai cấp độ: lập
lịch toàn cục và lập lịch địa phương. Thành phần lập lịch toàn cục sử dụng hàng đợi
đơn hoặc đa hàng đợi tách biệt dành cho các công việc thuộc các loại khác nhau, trong
một hàng đợi, ta có thể chọn sử dụng một chiến thuật lập lịch cụ thể (FCFS, SJF hay
First Fit - FF). Thành phần lập lịch toàn cục có một số chức năng chính mà một trong
số đó là khả năng so khớp tài nguyên do công việc yêu cầu với lượng tài nguyên khả
dụng hiện có. Một chức năng đáng lưu ý khác là tận dụng tối đa khả năng của các cụm
lập lịch địa phương. Thành phần lập lịch địa phương chỉ sử dụng một hàng đợi duy
nhất, với một chiến lược lập lịch duy nhất cho tất cả các công việc. Trong thuật toán
này, thành phần lập lịch địa phương chiu trách nhiệm điều phối một lượng tài nguyên
cụ thể cho các công việc phát sinh. Về tổng thể, bộ phận lập lịch ở hai cấp độ đều
hướng đến một giải pháp cân bằng tải tối ưu.
- Bài thu hoạch bộ môn Tính toán lưới -
Các thuật toán lập lịch và quản lý tài nguyên trong môi trường tính toán lưới
- 8 -

 Sử dụng chiến lược phi tập trung, thuật toán tỏ ra đáng tin cậy hơn so với các
thuật toán tập trung do một điểm thất bại sẽ ảnh hưởng đến ít thành phần hơn.
 Khả năng cân bằng tải trên tài nguyên toàn hệ thống cao hơn theo góc độ các
tác vụ được lập lịch trên mỗi tài nguyên. - Bài thu hoạch bộ môn Tính toán lưới -
Các thuật toán lập lịch và quản lý tài nguyên trong môi trường tính toán lưới
- 9 -

Nhược điểm:
 Chi phí truyền thông bên trong một cluster cũng như giữa các cluster với
nhau cao hơn.
 Không định rõ các yêu cầu của một tác vụ.
III.1.5.Mô hình lập lịch SFBAJG (Scheduling Framework for Bandwidth-
Aware Job Grouping-Based)
Trong công bố mang tên “Scheduling Framework for Bandwidth-Aware Job
Grouping-Based in Grid Computing” [6] vào năm 2006, Ng Wai Keat, Ang Tan Fong
và các cộng sự đã đề nghị một thuật toán lập lịch chú trọng đến băng thông dành cho
môi trường điện toán lưới. Thuật toán theo đuổi một chiến lược chú trọng đến năng lực
tính toán và truyền thông của tài nguyên hệ thống. Sử dụng lượng băng thông của điểm
thắt cổ chai mạng, thuật toán triển khai tính toán độ ưu tiên của mỗi tài nguyên. Cách
tiếp cận này cũng được dùng để dựng nên một mô hình lập lịch trong đó bộ phận lập
lịch có khả năng rút trích thông tin về năng lực xử lý tài nguyên của hệ thống. Khi cần
thiết, bộ phận lập lịch tiến hành lựa chọn tài nguyên xuất hiện đầu tiên và gom nhóm
các công việc độc lập đã được mịn hóa dựa trên khả năng xử lý của tài nguyên vừa
được chọn. Quá trình gom nhóm được thiết kế để tận dụng tối đa tài nguyên được chọn.
Sau khi tất cả các công việc đã được gom nhóm, chúng được gửi đến các vùng tài
nguyên chỉ định. Điểm mạnh của thuật toán là cho phép các kết nối tới các tài nguyên
có thể kết thúc nhanh hơn thông thường. Tối thiểu hóa lượng yêu cầu được gởi đi, đẩy

 Giảm thiểu đáng kể độ trễ mạng.
 Tổng thời gian vận hành của hệ thống giảm xuống.
Nhược điểm:
 Không xem xét đến các ràng buộc về kích thước bộ nhớ.
 Thời gian tiền xử lý cho việc gom nhóm công việc cao.
III.1.7.Mô hình lập lịch dựa trên môi trường lưới JSMB (Job Schedule
Model Based)
Trong công bố mang tên “A Job Schedule Model Based on Grid Environment” [8],
Homer Wu, Chong-Yen Lee và các cộng sự đã đề xuất một mô hình lập lịch mà thuật
toán chủ đạo cho phép tận dụng tối đa tài nguyên CPU đồng thời cực đại hóa lưu lượng
dữ liệu xử lý (MPUT). Bên cạnh đó, giảm thiểu đến mức tối đa thời gian xoay vòng
cũng là một điểm đáng chú ý khác của thuật toán. Về tổng thể, mô hình đề nghị chia các
nút trong mạng ra thành các nút giám sát, nút giám sát dự phòng và các nút thực thi.
Ưu điểm:
 Sử dụng các nút dự phòng để giảm thiểu ảnh hưởng khi các nút chính gặp
vấn đề, từ đó nâng cao tính an toàn của hệ thống với khả năng cân bằng tải
đáng ghi nhận.
 Tận dụng tối đa tài nguyên CPU cũng như tối ưu hóa lưu lượng dữ liệu được
xử lý.
 Cực tiểu hóa thời gian xoay vòng.
Nhược điểm:
 Chi phí truyền thông phát sinh cao.
 Không xét đến ràng buộc của các công việc cũng như tài nguyên.

- Bài thu hoạch bộ môn Tính toán lưới -
Các thuật toán lập lịch và quản lý tài nguyên trong môi trường tính toán lưới
- 11 -

III.2.Quản lý tài nguyên
Trong lưới điện toán, quản lý tài nguyên hay còn gọi là lập lịch tài nguyên là quá


- Bài thu hoạch bộ môn Tính toán lưới -
Các thuật toán lập lịch và quản lý tài nguyên trong môi trường tính toán lưới
- 12 -

III.2.2.Hệ quản lý tài nguyên dựa trên tác tử cùng với giải pháp luân phiên
ABRMAS
Vào năm 2007, P.Muthuchelvi và V.Ramachandran công bố tài liệu “ABRMAS:
Agent Based Resource Management with Alternate Solution” [10] đề xuất một giải
pháp luân phiên được áp dụng khi quá trình tìm kiếm tài nguyên bị thất bại. Điểm chính
của thuật toán là xác định một cụm tài nguyên tương đương mà không ảnh hưởng đến
hiệu năng chung của hệ thống đồng thời tránh được các quá trình tìm kiếm tài nguyên
không cần thiết. Trong quá trình hoạt động của mạng điện toán lưới, thường xuất hiện
một số tác vụ cần sự liên tục về thời gian, quá trình tìm kiếm tài nguyên cho các tác vụ
này đôi khi kết thúc mà không tìm được nguồn tài nguyên tương thích nào ở trạng thái
khả dụng. Giải pháp luân phiên giảm thiểu chi phí phát sinh do sự chậm đáp ứng của hệ
thống trong quá trình chờ đợi nguồn tài nguyên tương thích đồng thời tăng cường hiệu
suất chung của hệ thống. Theo ghi nhận của hai tác giả, tỉ lệ thành công trên toàn hệ
thống tăng lên 30% khi cài đặt giải pháp luân phiên.
Ưu điểm:
 Giới hạn và điều chỉnh việc tìm kiếm theo hướng dự đoán trước nhờ đó quá
trình phát hiện tài nguyên tỏ ra hiệu quả hơn.
 Tỏ ra hữu hiệu trong cả hai trường hợp: quá trình tìm kiếm tài nguyên bị thất
bại hay xuất hiện nhiều giải pháp cùng lúc.
Nhược điểm:
 Đối với cấu trúc phân cấp tác tử lớn, có thể dẫn đến tình trạng phân rã thành
các cấu trúc phân cấp nhỏ hơn.
 Đây là một thuật toán không tường minh.
III.2.3.Cơ chế nhận biết tài nguyên với giải pháp dựa trên tác tử NRMNS
Cùng nghiên cứu về giải pháp luân phiên để ứng phó với trạng thái thất bại trong

Condor đã có trước đó. Một mô hình lai đã được đề xuất với việc sử dụng bốn
framework khác nhau nhưng đồng nhất về mặt mục đích theo hướng tiếp cận P2P. Mỗi
framework khắc phục một số giới hạn của Condor từ đó tăng cường sức mạnh, độ tin
cậy cũng như khả năng mở rộng của toàn hệ thống. Truyền thông mạng trở nên đơn
giản hơn khi nhóm tác giả cài đặt giao thức thành viên cho Condor. Bên cạnh đó, thuật
toán khởi tạo phủ được sử dụng trong mô hình mới mở ra khả năng thông tin giữa các
tiến trình với nhau, điều mà hệ thống Condor trước đó không thể thực hiện được.
Ưu điểm:
 Có sự độc lập đối với bộ phận quản lý toàn cục trung ương.
 Sử dụng DHT cùng với đặc tính đánh chỉ mục của mình, thuật toán có khả
năng phát hiện tài nguyên nhanh chóng.
 Có khả năng mở rộng.
 Chấp nhận các nguồn tài nguyên gián đoạn.
Nhược điểm:
 Đòi hỏi khả năng tự hành cao nhằm duy trì kiến trúc ổn định của hệ thống.
 Chi phí vận hành cao phát sinh từ sự hỗn độn của hệ thống.
- Bài thu hoạch bộ môn Tính toán lưới -
Các thuật toán lập lịch và quản lý tài nguyên trong môi trường tính toán lưới
- 14 -

III.2.5.Lưới điện toán ảo sử dụng vùng chứa tài nguyên VCGRP
Được Alpana Rajan, Anil Rawat cùng các cộng sự công bố vào năm 2008, tài liệu
“Virtual Computing Grid using Resource Pooling” [13] đề xuất một hệ thống lưới điện
toán dựa trên khái niệm liên kết cặp đôi lỏng. Trong tài liệu của mình, nhóm tác giả
định nghĩa lưới điện toán ảo là một hệ thống có khả năng lựa chọn một tài nguyên xác
định và cấp phát các tác vụ cho nó. Trong mô hình này, tài nguyên chính là một điểm
truy cập mạng duy nhất được biết đến dưới tên Ngõ vào Lưới điện toán Ảo (Virtual
Computing Grid Portal), còn Bộ Vận Hành Lưới điện toán Ảo (Virtual Computing
Grid Monitor) chính là thành phần quản lý tài nguyên tập trung của toàn hệ thống.
Ưu điểm:

Khả năng
cân bằng
tải
Tính động
HRN
phân tán
đồng nhất
cao
cao
cao
cao
ORC
phân tán
không
đồng nhất
cao
cao
cao
cao
HJS

đồng nhất
trung bình
cao
cao
cao
RCSTD
phân tán
không
đồng nhất

không
đồng nhất
cao
cao
cao
cao
ABRMAS

không
đồng nhất
cao
cao
trung bình
cao
NRMNS

không
đồng nhất
thấp
cao
trung bình
cao
IRP2P
phân tán
không
đồng nhất
cao
cao
trung bình
cao

bộ công cụ GrimSim
IV.2.Các so sánh mang tính đánh giá trên các thuật toán lập lịch
Theo đánh giá chung, thuật toán HRN có khả năng thích ứng cao trong môi trường
lưới nhưng lại không phù hợp khi có nhiều công việc xuất hiện trong môi trường mang
tính đồng nhất. Về phần mình, trong khi khắc phục được các nhược điểm của FCFS và
HRN đồng thời giảm thời gian xoay vòng và thời gian chờ của công việc, nhưng thuật
toán ORC lại phát sinh chi phí truyền thông đáng kể. Thuật toán HJS tỏ ra hiệu quả
trong việc giảm thiểu tổng thời gian xoay vòng và tận dụng tối đa hệ thống nhưng lại có
nhược điểm là gây ra lãng phí năng lực CPU. Trong trường hợp của RCSTD, một ưu
điểm đáng ghi nhận là khả năng tối thiểu hóa thời gian thực thi các tác vụ nhưng lại gia
tăng chi phí truyền thông bên trong một cluster cũng như giữa các cluster với nhau.
Thuật toán SFBAJG tối thiểu hóa sự lãng phí tài nguyên CPU đồng thời giảm thiểu độ
trễ mạng nhưng thời gian xử lý để gom nhóm công việc và lựa chọn tài nguyên lại khá
cao; thuật toán còn có một số nhược điểm khác cần phải lưu tâm như: không xem xét
các ràng buộc về kích thước bộ nhớ cũng như các đặc tính của tài nguyên động, chiến
lược chính của thuật toán không tận dụng hiệu quả các tài nguyên hệ thống. Trong
trường hợp của GFJS, nếu ưu điểm là khả năng giảm thiểu thời gian thực thi, độ trễ
mạng, cũng như tổng thời gian xử lý thì khuyết điểm chính là sự hao tốn thời gian cho
quá trình gom nhóm. Nếu như tận dụng tối đa tài nguyên CPU và cực tiểu hóa thời gian
- Bài thu hoạch bộ môn Tính toán lưới -
Các thuật toán lập lịch và quản lý tài nguyên trong môi trường tính toán lưới
- 18 -

xoay vòng là những điểm nổi trội của JSMB, thì điểm trừ lại là chi phí truyền thông
phát sinh cao.
Dựa vào các xem xét khách quan trên tất cả các tiêu chí cũng như tham khảo các
đánh giá chung trong bảng I và kết quả mô phỏng ở biểu đồ I, có thể nhận thấy thuật
toán GFJS vượt trội hơn hẳn các thuật toán còn lại.
IV.2.1.Các so sánh mang tính đánh giá trên các thuật toán quản lý tài
nguyên

cũng như những hiểu biết của học viên còn chưa được sâu sát, có thể tài liệu vẫn còn
một số sai sót cần phải chỉnh sửa. Rất mong nhận được sự đóng góp, phản hồi từ các
thầy, cô và bạn học.
- Bài thu hoạch bộ môn Tính toán lưới -
Các thuật toán lập lịch và quản lý tài nguyên trong môi trường tính toán lưới
- 20 - Danh sách các mô hình, bảng biểu và biểu đồ

Hình I. Mô hình tính toán lưới căn bản 5
Bảng I. Mô tả tổng quát các thuật toán lập lịch và quản lý tài nguyên. 15
Biểu đồ I. Hiệu năng của các thuật toán lập lịch dưới sự mô phỏng của bộ công cụ
GrimSim 16
Biểu đồ II. Hiệu năng của các thuật toán quản lý tài nguyên dưới sự mô phỏng của bộ
công cụ GrimSim 17 - Bài thu hoạch bộ môn Tính toán lưới -
Các thuật toán lập lịch và quản lý tài nguyên trong môi trường tính toán lưới
- 21 - Tài liệu tham khảo

1. Raksha Sharma, Vishnu Kant Soni, Manoj Kumar Mishra, Prachet Bhuyan
(2010). “A Survey of Job Scheduling and Resource Management in Grid
Computing”, World Academy of Science, Engineering and Technology 40.
2. K.Somasundaram, S.Radhakrishnan, M.Gomathynayagam, “Efficient
Utilization of Computing Resources using Highest Response Next Scheduling

10. Ms.P.Muthuchelvi, Dr.V.Ramachandran, “ABRMAS: Agent Based Resource
Management with Alternate Solution,” IEEE, The Sixth International
Conference on Grid and Cooperative Computing, GCC 2007.
11. Junyan Wang, Yuebin Xu, Guanfeng Liu, Zhenkuan Pan, and Yongsheng Hao,
“New Resource Discovery Mechanism with Negotiate Solution Based on
Agent in Grid Environments”, IEEE The 3rd International Conference on
Grid and Pervasive Computing – Workshops, 2008.
12. Anju Sharma, and Seema Bawa, “An Improved Resource Discovery
Approach Using P2P Model for Condor: A Grid Middleware”, World
Academy of Science, Engineering and Technology, 2006.
13. Alpana Rajan, Anil Rawat, Rajesh Kumar Verma, “Virtual Computing Grid
using Resource Pooling”, IEEE, International Conference on Information
Technology , 2008.
14. R. Buyya and M. Murshed, GridSim, "A toolkit for themodeling and simulation
of distributed management and scheduling for grid computing", 2002.