ĐẠ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

hoạch.
Xin cám ơn cha, mẹ, các anh, chị em trong gia đình đã hỗ trợ, lo lắng và động
viên. Đồng thời, xin cám ơn tất cả các đồng nghiệp đã ủng hộ, giúp đỡ học viên trong
quá trình thực hiện.
Dù đã có nhiều cố gắng nhưng chắc chắn sẽ không tránh khỏi những thiếu sót,
học viên rất mong nhận được sự đóng góp ý kiến của các Thầy giáo, Cô giáo và các
bạn học để bài thu hoạch được hoàn thiện hơn.
Xin chân thành cảm ơn!
Tp Hồ Chí Minh, tháng 07 năm 2013
Học viên Nguyễn Vĩnh Kha

- 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
- 3 -

Mục lục
Chương I. Giới thiệu chung 4
Chương II. Mô hình tính toán lưới căn bản 5
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 6
III.1. Các thuật toán lập lịch 6
III.1.1. Thuật toán lập lịch HRN 6
III.1.2. Phân phối nút sử dụng thuật toán lập lịch ORC (Optimal Resource
Constraint) 7
III.1.3. Lập lịch phân cấp (Hierarchical Job Scheduling - HJS) cho các cụm máy
trạm 7
III.1.4. RCSTD: Lập lịch các tác vụ có tính phụ thuộc thông qua thuật toán đồng
phân phối tài nguyên 8
III.1.5. Mô hình lập lịch SFBAJG (Scheduling Framework for Bandwidth-Aware
Job Grouping-Based) 9

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

trọng tâm ở phần lập lịch tác vụ.
Với mong muốn tìm hiểu vấn đề quản lý tài nguyên và lập lịch tác vụ trong môi
trường điện toán lưới, học viên đã đọc hiểu tài liệu “A Survey of Job Scheduling and
Resource Management in Grid Computing” đồng thời tham khảo một số tài liệu liên
quan, từ đó xin đúc kết ra bài thu hoạch bao gồm bốn chương như sau:
- Chương I. Giới thiệu chung
- Chương II. Mô hình tính toán lưới căn bản: Đề cập đến các khái niệm căn bản
cũng như các thành phần cốt yếu của mô hình tính toán lưới.
- Chương III. Các thuật toán quản lý tài nguyên và lập lịch trong tính toán lưới:
Giới thiệu một số nghiên cứu gần đây xoay quanh vấn đề lập lịch và quản lý tài
nguyên dành riêng cho môi trường điện toán lưới.
- Chương IV. Đánh giá: Đưa ra các khảo sát và so sánh hiệu năng của các giải
thuật, mô hình.
- Chương V. Kết luận.
Mặc dù đã có nhiều cố gắng trong quá trình làm bài thu hoạch, học viên vẫn không
tránh khỏi những sai sót do khả năng có hạn của bản thân, rất mong nhận được sự đóng
góp ý kiến của 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
- 5 -

Chương II. Mô hình tính toán lưới căn bản
Về tổng thể, mô hình tính toán lưới căn bản bao gồm một lượng nhất định các máy
chủ, mỗi máy chủ có một lượng tài nguyên tính toán riêng. Các tài nguyên trong mô
hình điện toán lưới có thể là đồng nhất hay không đồng nhất tùy vào điều kiện thực tế.
Bốn nhân tố cơ bản của mô hình lưới là người dùng (user), bộ phận phân chia tài
nguyên (resource broker), bộ phận thông tin lưới (grid information service - GIS) và tài
nguyên còn thừa (lastly resources). Mỗi khi người dùng yêu cầu thực thi một công việc
với tốc độ cao, công việc này sẽ được được gởi đến bộ phận phân chia tài nguyên. Bộ
phận này chia tách công việc thành các tác vụ khác nhau đồng thời cấp phát một lượng

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 phân phối một lượng các bộ xử lý dựa trên độ ưu tiên của bản thân công việc và
khả năng đáp ứng của bộ xử lý. Mô hình hoạt động này thích ứng với cả các công việc
cục bộ cũng như từ xa mà không gây ra bất kỳ sự giảm sút nào về hiệu năng, đồng thời
tỏ ra rất phù hợp đối với môi trường lưới. Dưới đây, ta xem xét qua các ưu và nhược
điểm chính của thuật toán.
Ưu điểm:
 HRN hoạt động theo cơ chế phân phối ưu tiên cho phép tận dụng hiệu quả
các tài nguyên hiện có cũng như hoàn thành tất cả các công việc nhanh hơn
thuật toán FCFS.
 HRN khắc phục được một số yếu điểm của cả hai thuật toán SJF (Shortest
Job First) và FCFS (First Come First Serve).
Nhược điểm:
 Không phù hợp khi phải thực hiện phân phối tài nguyên cho nhiều công việc,
do bản chất quá trình tính toán độ ưu tiên rất mất thời gian.
 Thời gian xoay vòng cao hơn các thuật toán SJF và FCFS.
 Thuật toán gây ra sự lãng phí CPU và bộ nhớ.
- 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
- 7 -

III.1.2.Phân phối nút sử dụng thuật toán lập lịch ORC (Optimal Resource
Constraint)
Thuật toán lập lịch ORC (Optimal Resource Constraint) thực hiện phân phối công
việc dựa trên khả năng đáp ứng của các bộ xử lý. Đây là thuật toán có cùng chiến lược
với Round Robin (RR) với mục đích cuối cùng là phân phối công việc đến các bộ xử lý
khả dụng – các bộ xử lý chưa được cấp phát. Trong bài nghiên cứu “Node Allocation In
Grid Computing Using Optimal Resource Constraint (ORC) Scheduling” [3],
K.Somasundaram và cộng sự đã tiến hành so sánh ORC với các thuật toán lập lịch phổ
biến như FCFS, SJF và RR; kết quả cho thấy ORC có hiệu suất cao hơn các thuật toán
truyền thống khi giảm thiểu thời gian xoay vòng và thời gian đợi trung bình của cá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 -


Ưu điểm:
 Giảm thiểu thời gian xoay vòng tổng thể cũng như tận dụng hệ thống đến
mức tối đa đáp ứng cho nhu cầu tải nạp hệ thống ở mức cao.
 Đối với vấn đề tải nạp hệ thống ở mức cao, cho phép duy trì độ trễ của việc
lập lịch ở mức toàn cục thông qua việc sử dụng đa hàng đợi.
Nhược điểm:
 Việc áp dụng SJF trong HJS có thể gây ra độ trễ lớn đối với các công việc có
thời gian thực thi kéo dài, đồng thời sẽ gây ra hiện tượng thiên kiến đối với
các công việc lớn, dễ dẫn đến hiện tượng không được cấp phát tài nguyên
trong thời gian dài.
 Có khả năng sử dụng không hết tài nguyên của hệ thống lưới.
 Thuật toán không xem xét đến đặc tính động của tài nguyên lưới.
III.1.4.RCSTD: Lập lịch các tác vụ có tính phụ thuộc thông qua thuật toán
đồng phân phối tài nguyên
Năm 2008, thuật toán mang tên đồng phân phối tài nguyên được Diana Moise ,
Izabela Moise , Florin Pop và Valentin Cristea đưa ra khi công bố tài liệu
“Resource CoAllocation for Scheduling Tasks with Dependencies, in Grid” [5]. Thuật
toán đề ra chiến lược lập lịch tác vụ có tính phụ thuộc trong môi trường lưới, được áp
dụng cả bên trong một cluster cũng như giữa các cluster với nhau. Trong mỗi bước của
mình, thuật toán tiến hành thao tác kết hợp hay hợp nhất các cluster (có thể là các tác vụ
bên trong cluster hay các cluster với nhau) dựa trên sự phụ thuộc lẫn nhau của các
cluster. Theo cách này, các cluster được kêt hợp lại nếu tồn tại bất cứ sự phụ thuộc nào
giữa chúng. Mục đích chính của thuật toán là tăng khả năng cân bằng tải cũng như cực
tiểu hóa thời gian thực thi tác vụ. Dưới đây là các ưu và nhược điểm của thuật toán.
Ưu điểm:
 Giảm thiểu thời gian thực thi tác vụ đến mức tối đa.
 Thuật toán có đặc tính động bởi trong một cluster các tác vụ được phân phối
cho một lượng tài nguyên thích hợp mà trên đó nó có thể được lên lịch hoạt
động trong thời gian sớm nhất.

 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

nhanh quá trình kết nối mạng, kết quả cuối cùng của mô hình là khả năng tăng cường
tốc độ truyền tải hay băng thông.
Ưu điểm:
 Tối thiểu sự lãng phí tài nguyên CPU.
 Gom nhóm các công việc được mịn hóa thành các nhóm mịn hóa (quá trình
thô hóa) giúp giảm độ trễ của mạng lưới.
 Giảm thiểu tổng thời gian thực thi.
Nhược điểm:
 Không xem xét đến các ràng buộc về kích thước bộ nhớ.
 Không mang đặc tính động về tài nguyên.
 Thời gian tiền xử lý cho việc gom nhóm công việc và lựa chọn tài nguyên
cao.
III.1.6.Thuật toán lập lịch GFJS (Grouping-based Fine-grained Job
Scheduling)
Sử dụng chiến lược gom nhóm, thuật toán dựa chủ yếu trên các đặc tính về tài
nguyên của hệ thống. Các công việc đã qua mịn hóa được nhóm lại thành các cụm cô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
- 10 -

việc, các cụm này sau đó được cấp phát cho một lượng tài nguyên nhất định tùy theo
năng lực xử lý (đo bằng MIPS) và băng thông (đo bằng Mb/s). Trong bài nghiên cứu
“Grouping-Based Fine-grained Job Scheduling in Grid Computing” [7], hai tác giả
Quan Liu và Yeqing Liao đã kết hợp thuật toán tham lam với thuật toán FCFS để nâng
cao khả năng xử lý các công việc đã qua mịn hóa.
Ưu điểm:
 Tận dụng tối đa tài nguyên hệ thống.
 Thời gian thực thi công việc được giảm thiểu.
 Giảm thiểu chi phí phát sinh khi thực hiện lập lịch mịn hóa thông qua việc
gom nhóm các công việc nhỏ trong suốt tiến trình lập lịch.

 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á

trình tìm kiếm một cụm tài nguyên thích hợp để đáp ứng một truy vấn xử lý trong hệ
thống, quá trình truyền thông có nhanh chóng và đáng tin hay không phụ thuộc rất
nhiều vào cơ chế quản lý tài nguyên. Tài nguyên trong một hệ thống lưới điện toán
hoàn chỉnh thường rất lớn với nhiều đơn vị riêng lẻ và không được tập trung hóa quản
lý, các tài nguyên này có thể được thêm vào hoặc gỡ ra khỏi hệ thống vào bất kỳ thời
điểm nào. Với những lý do đó, quản lý tài nguyên trong môi trường lưới có kích thước
lớn thực sự là một vấn đề mang tính thách thức cần phải được nghiên cứu sâu sát.
Trong phần này của tài liệu, ta sẽ tìm hiểu một số thuật toán, mô hình được công bố
trong các tài liệu gần đây để có cái nhìn rõ hơn về những tiến triển của giới nghiên cứu
xoay quanh vấn đề này.
III.2.1.Hệ quản lý tài nguyên động và lập lịch RNDRM
Trong tài liệu “Research on Novel Dynamic Resource Management and Job
Scheduling in Grid Compuing” [9] được công bố vào năm 2006, Fufang Li, Deyu Q và
các cộng sự đã đề xuất một mô hình quản lý tài nguyên dựa trên cây Heap Sort (HST)
dùng để tính ra năng lực tính toán khả dụng của các nút (ở đây là các tài nguyên) cũng
như của cả hệ thống lưới. Trong mô hình này, tài nguyên với năng lực tính toán khả
dụng lớn nhất được chọn làm nút gốc của cây HST và được xem như sẵn sàng để bộ lập
lịch gửi lên một công việc. Được thiết kế đặc biệt cho bài toán lập lịch, thuật toán tỏ ra
rất phù hợp cho môi trường lưới có tính phức tạp.
Ưu điểm:
 Hệ thống có khả năng mở rộng cao và linh hoạt hơn.
 Khả năng kháng lỗi cũng như hiệu năng của hệ thống được tăng cường.
 Chiến lược được đề nghị có khả năng duy trì thông tin trạng thái động của tài
nguyên, chiến lược này đặc biệt hữu hiệu trong môi trường lưới thay đổi
nhanh và khó dự đoán.
Nhược điểm:
 Thuật toán không có phản hồi khi việc đệ trình một công việc bị thất bại.
 Chiến lược có thể không tận dụng hết tài nguyên hệ thống.
 Thời gian chờ của một công việc cao.
 Môi trường lưới không mang tính động trong thời gian thự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
- 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

tìm kiếm tài nguyên, vào năm 2008 Junyan Wang và cộng sự đã công bố tài liệu “New
Resource Discovery Mechanism with Negotiate Solution Based on Agent in Grid
Environments” [11]. Với ý định tăng cường cho ABRMAS, nhóm tác giả đề xuất bổ
sung thêm kiến trúc GRACE (Grid Architecture for Computational Economy) chứa
thành phần RPFM (Resource Pricing Fluctuation Manager) nhằm tăng hiệu năng quản
lý tài nguyên cho lưới điện toán. Trong hệ thống dựa trên tác tử mà nhóm tác giả đề
xuất, mô hình phản hồi đóng vai trò then chốt trong việc ứng phó với trạng thái thất bại
khi tìm kiếm 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
- 13 -

Ưu điểm:
 Hiệu suất quản lý tài nguyên có thể đạt đến mức tối đa.
 Khả năng phản hồi của RPFM có khả năng thích nghi tốt trong môi trường
lưới mang tính động cao.
 Kết quả mô phỏng cho thấy tỉ lệ phát hiện tài nguyên thành công tăng lên đến
10%.
Nhược điểm:
 Quá trình tìm kiếm tài nguyên bị ngắt khi tác tử cấp phát tài nguyên RPA
(Resource provider agent) không chấp nhận việc giảm sự hao tốn tài nguyên,
đây được xem là nhược điểm chính của thuật toán.
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
Vào năm 2006, Anju Sharma, và Seema Bawa công bố tài liệu “An Improved
Resource Discovery Approach Using P2P Model for Condor: A Grid Middleware”
[12]. Trong công bố của mình, nhóm tác giả đề cập đến IRP2P – một middleware dạng
lưới sử dụng kỹ thuật phi tập trung ngược với mô hình client-server truyền thống. Mục
đích chính của nghiên cứu là tìm ra một mô hình tăng cường hiệu năng cho middleware

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:

 Mô hình có tính hiệu quả về mặt chi phí
Nhược điểm:
 Tính tin cậy không cao do chỉ có một bộ phận quản lý trung ương và một ngõ
truy cập mạng duy nhất
 Do đây là mô hình thiên về tính hiệu quả của chi phí nên chất lượng dịch vụ
giảm sút.

- 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
- 15 -

Chương IV. Khảo sát và đánh giá
Trong chương này, tài liệu sẽ dẫn ra một số khảo sát và so sánh thực nghiệm đã
được tiến hành để xác định hiệu suất của các thuật toán, mô hình trong chương III. Các
độ đo khác nhau sẽ được áp dụng để đánh giá một cách toàn diện tất cả các thuật toán
và mô hình.
IV.1.Khảo sát chung và mô phỏng.
Trước tiên ta xem xét bảng khảo sát chung các thuật toán lập lịch và quản lý tài
nguyên dựa trên các tiêu chí: kiến trúc tổng thể của mô hình thuật toán (phân tán, phân
cấp, hay tập trung), môi trường thực thi (đồng nhất hay không đồng nhất), thời gian đáp
ứng, khả năng tận dụng tài nguyên, khả năng cân bằng tải, tính động.
Thuật toán
Kiến trúc
Môi
trường
Thời gian
đáp ứng
Khả năng
tận dụng
tài nguyên

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

trung bình
thấp
cao
cao
SFBAJG

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

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

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

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.
Dựa trên bảng khảo sát, ta có thể đưa ra những nhận xét ban đầu về hiệu năng của
các thuật toán đã được tìm hiểu. Tuy nhiên, để cụ thể hóa các tiên đoán ta cũng cần
triển khai các thực nghiệm đáng tin cậy trên từng thuật toán. Tài liệu sẽ trình bày một
- 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
- 16 -

số biểu đồ được ghi nhận thông qua quá trình sử dụng bộ công cụ mô phỏng GridSim
[14] với các thiết lập khác nhau về số lượng công việc trong hệ thống (dao động từ 50
đến 300). Các biểu đồ này cho phép ta đánh giá hiệu năng của từng thuật toán với độ đo
là tổng thời gian thực thi.

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
- 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
- 17 -


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
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

Xét đến các thuật toán và mô hình quản lý tài nguyên, ta nhận thấy RNDRM giúp hệ
thống có khả năng mở rộng cao và linh hoạt hơn, đồng thời nâng cao đặc tính kháng lỗi
và cân bằng tải của hệ thống. Trong khi đó, ưu điểm chính của VCGRP là khả năng tận
dụng tối đa tài nguyên mặc dù độ tin cậy không cao. Về phần mình, mô hình IRP2P
giúp tăng cường khả năng mở rộng, độ tin cậy cũng như năng lực vận hành của hệ
thống nhưng lại yêu cầu hệ thống phải có khả năng tự quản cao khi phải làm việc trong
môi trường không đồng nhất. Thuật toán ABRMAS tỏ ra hiệu quả khi đối phó với tình
huống tìm kiếm tài nguyên bị thất bại thế nhưng lại là một thuật toán không tường
minh. Cuối cùng là thuật toán NRMNS với các ưu điểm bao gồm khả năng thích ứng
tốt trong môi trường lưới, tỉ lệ thành công của quá trình tìm kiếm tài nguyên cao và khả
năng tận dụng tối đa tài nguyên đáng ghi nhận.
Dựa vào bảng I và biểu đồ II, dễ dàng nhận thấy RNDRM là giải pháp tốt nhất cho
vấn đề quản lý tài nguyên trong môi trường tính toán lưới.

- 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
- 19 -

Chương V. Tổng kết
Với sự phát triển không ngừng của mình, điện tóan lưới đang được các doanh
nghiệp, trường đại học và học viện khai thác triệt để nhằm tăng cường hạ tầng điện toán
sở tại. Để có được một hệ thống điện toán lưới mạnh mẽ và có khả năng mở rộng tốt,
việc tìm hiểu và khắc phục các điểm yếu trong quá trình lập lịch tác vụ và quản lý tài
nguyên là không thể tránh khỏi. Thông qua việc tìm hiểu các thuật toán, mô hình được
công bố trong thời gian gần đây, tài liệu đã góp phần đưa ra các đánh giá mang tính
khách quan và toàn diện đối với mười hai thuật toán khác nhau. Hy vọng đây sẽ là một
tài liệu có giá trị cho các bạn cùng học cũng như những ai quan tâm đến vấn đề tính
toán lưới.
Với mong muốn đào sâu thêm hiểu biết của bản thân về lĩnh vực tính toán lưới, học
viên đã rất cố gắng trong quá trình soạn thảo tài liệu, tuy nhiên do thời gian hạn hẹp

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

in Grid” 6 (5): 544-547, Asian Journal of Information Technology, 2007.
3. K.Somasundaram, S.Radhakrishnan, “Node Allocation In Grid Computing
Using Optimal Resource Constraint (ORC) Scheduling”, VOL.8 No.6,
IJCSNS International Journal of Computer Science and Network Security, June
2008.
4. J. Santoso; G.D. van Albada; B.A.A. Nazief and P.M.A. Sloot: “Hierarchical
Job Scheduling for Clusters of Workstations”, ASCI 2000, pp. 99-105. ASCI,
Delft, June 2000.
5. Diana Moise, Izabela Moise, Florin Pop,Valentin Cristea, “Resource
CoAllocation for Scheduling Tasks with Dependencies, in Grid”, The Second
International Workshop on High Performance in Grid Middleware HiPerGRID
2008.
6. Ng Wai Keat, Ang Tan Fong,Ling Teck chaw, Liew Chee Sun, “Scheduling
Framework for Bandwith-aware Job Grouping-based Scheduling in Grid
Computing”, Vol.19(2), Malaysian Journal of Computer Science, 2006.
7. Quan Liu, Yeqing Liao, “Grouping-Based Fine-grainedJob Scheduling in
Grid Computing”, Vol.1, pp. 556-559, IEEE First International Workshop on
Education Technology and Computer Science, 2009.
8. Homer Wu,Chong-Yen Lee, Wuu-Yee Chen, Tsang Lee, “A Job schedule
Model Based on Grid Environment”, IEEE Proceeding of the First International
- 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
- 22 -

Conference on Complex, Intelligent and Software Intensive System, CISIS’07
2007.
9. Fufang Li, Deyu Qi, Limin Zhang, Xianguang Zhang, and Zhili Zhang,
“Research on Novel Dynamic Resource Management and Job Scheduling in
Grid Compuing”, IEEE Proceedings of the First International Multi-
Symposiums on Computer and Computational Sciences, IMSCCS 2006.

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.