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 http://www.Lrc-tnu.edu.vn

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.