Thuật toán lập lịch điều phối tài nguyên cho các tác vụ của luồng công việc trong môi trường điện toán đám mây

Trong bài viết này tác giả sẽ xây dựng một mô hình bài toán luồng công việc trong môi trường điện toán đám mây và đề xuất một thuật toán dựa trên thuật toán PSO để sắp xếp luồng công việc thực thi trên môi trường điện toán đám mây đảm bảo chi phí nhỏ nhất.
Nội dung trích xuất từ tài liệu:
Thuật toán lập lịch điều phối tài nguyên cho các tác vụ của luồng công việc trong môi trường điện toán đám mây NATIONAL ACADEMY OF EDUCATION MANAGEMENT DOI: 10.53750/jem22.v14.n3a.110 Journal of Education Management, 2022, Vol. 14, No. 10, pp. 100-110 This paper is available online at http://jem.naem.edu.vn THUẬT TOÁN LẬP LỊCH ĐIỀU PHỐI TÀI NGUYÊN CHO CÁC TÁC VỤ CỦA LUỒNG CÔNG VIỆC TRONG MÔI TRƯỜNG ĐIỆN TOÁN ĐÁM MÂY Phan Văn Tiến1, Phan Thanh Toàn2 Tóm tắt. Luồng công việc là một dãy có thứ tự các tác vụ cần phải thực thi để đạt được một mục đích, Bài toán lập lịch luồng công việc là bài toán sắp xếp các tác vụ cho thực thi trên một số máy xác định sao cho đạt hiệu quả tốt nhất, đây chính là bài toán quan trọng nhất tại các trung tâm điện toán đám mây. Trong bài báo này chúng tôi sẽ xây dựng một mô hình bài toán luồng công việc trong môi trường điện toán đám mây và đề xuất một thuật toán dựa trên thuật toán PSO để sắp xếp luồng công việc thực thi trên môi trường điện toán đám mây đảm bảo chi phí nhỏ nhất. Từ khóa: Lập lịch luồng công việc, ứng dụng luồng công việc , điện toán đám mây. 1. Đặt vấn đề Điện toán đám mây là sự tích hợp của nhiều công nghệ thuộc lĩnh vực công nghệ thông tin và truyền thông, trong mô hình điện toán đám mây mọi khả năng liên quan đến công nghệ thông tin đều được cung cấp dưới dạng dịch vụ cho phép người sử dụng truy cập đến các dịch vụ công nghệ (phần cứng và phần mềm) từ một nhà cung cấp dịch vụ, điện toán đám mây là sự tập hợp của nhiều máy tính được cấu hình để làm việc với nhau trên môi trường mạng internet và các ứng dụng khác nhau sẽ sử dụng sức mạnh của môi trường điện toán đám mây để thực thi các ứng dụng như trên một hệ thống duy nhất. Một trong số các ứng dụng phổ biến nhất trong môi trường điện toán đám mây là bài toán luồng công việc (từ đây viết tắt là workflow), hiệu năng của các trung tâm điện toán phụ thuộc rất nhiều vào việc sắp xếp các tác vụ trong luồng thực thi trên các máy tính trong môi trường đám mây để hoàn thành luồng công việc một cách “tối ưu” nhất. Nội dung của bài báo gồm những phần chính sau đây. Phần I giới thiệu bối cảnh thực tế tại trung tâm điện toán đám mây nơi cung cấp dịch vụ workflow. Phần II trình bày các công trình nghiên cứu liên quan và phương pháp tối ưu bày đàn PSO [1]. Phần III giới thiệu mô hình bài toán, hàm mục tiêu và các ràng buộc của bài toán lập lịch. Phần IV đề xuất một thuật toán lập lịch theo chiến lược PSO để giải quyết bài toán Lập lịch đã đề xuất. Trong phần V, để kiểm chứng hiệu năng của thuật toán đề xuất [11], chúng tôi đã thực hiện các thực nghiệm trên những ứng dụng workflow trong môi trường đám mây thông qua công cụ công cụ mô phỏng CloudSim [4,5,10]. Các kết quả được thu thập và so sánh với giải thuật PSO Heuristic và 2 giải thuật lập lịch cơ bản là giải thuật 2. Mô hình lí thuyết 1 Khoa Công nghệ thông tin, Học viện Quản lý giáo dục e-mail: phantien2000@gmail.com 2 Khoa Công nghệ thông tin, Học viện Quản lý giáo dục 100 THỰC TIỄN JEM., Vol. 14 (2022), No. 10 Giả sử cần sắp xếp lịch biểu cho một luồng công việc trong môi trường đám mây với các giả thiết như sau : - Luồng công việc được biểu diễn bởi đồ thị G=(V, E), với V là tập đỉnh của đồ thị, mỗi đỉnh biểu thị cho một tác vụ. - T ={T1, T2,…,TM} là tập các tác vụ, M là số lượng tác vụ của luồng công việc đang xét. - E là tập cạnh thể hiện mối quan hệ cha-con giữa các tác vụ. Cạnh (Ti, Tj)  E cho biết tác vụ Ti là cha của tác vụ Tj, dữ liệu đầu ra của Ti sẽ là dữ liệu đầu vào cho tác vụ Tj (xem Hình 1). - Tập máy chủ của đám mây ký hiệu là S = {S1, S2,….,SN}, N là số lượng máy chủ của đám mây. - Mỗi tác vụ có thể được thực thi trên một máy chủ bất kì, máy chủ đó phải thực hiện toàn bộ tác vụ từ đầu đến cuối. - Khối lượng tính toán (Workload) của tác vụ Ti kí hiệu là Wi với đơn vị đo là flop (floating point operations: phép tính trên số thực dấu phảy động). Wi được cho trước (i = 1,2, …M) - Tốc độ tính toán của máy chủ Si , đơn vị là MI/s (million instructions/second), được ký hiệu 1 2 3 4 5 Hình 1: Đồ thị biểu diễn một luồng công việc với 5 tác vụ bởi P(Si), là giá trị được cho trước (i = 1,2, …M) - Giữa hai máy chủ Si, Sj bất kỳ (1≤i,j≤N) có một đường truyền với băng thông, đơn vị là Megabit/s, được biểu thị bởi hàm hai biến B() được định nghĩa như sau: B: S×S → R+ (Si,Sj) → B(Si,Sj) - Giả thiết hàm băng thông B() thỏa mãn các điều kiện sau:  B(Si,Si) = ∞ : thời gian truyền tại chỗ bằng không  B(Si,Sj) = B(Sj,Si) : tốc độ truyền hai chiều bằng nhau  Giá trị B(Si,Sj) được cho trước (i,j). - Khối lượng dữ liệu do tác vụ Ti chuyển tới tác vụ Tj, kí hiệu là Dij với đơn vị là Megabit, là giá trị cho trước (i,j). - Mỗi phương án xếp lịch thực thi luồng công việc tương đương với một hàm f() f:T→S Ti → f(Ti) Trong đó f(Ti) là máy chủ chịu trách nhiệm thực thi tác vụ Ti Từ các giả thiết trên ta suy ra:  Thời gian tính toán của tác vụ Ti là: Wi (i=1,2, ... M) (3) P f Ti   Thời gian truyền dữ liệu giữa tác vụ Ti và tác vụ con Tj là Dij (4) B f Ti , f T j  101 Phan Văn Tiến, Phan Thanh Toàn JEM., Vol. 14 (2022), No. 10 - Bài báo này định ngh ...