Tài liệu 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

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