Tài liệu Nghiên cứu một số vấn đề lập lịch trên môi trường tính toán đám mây (tt)

ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN HOÀNG HÀ NGHIÊN CỨU MỘT SỐ VẤN ĐỀ LẬP LỊCH TRÊN MÔI TRƯỜNG TÍNH TOÁN ĐÁM MÂY CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ: 62.48.01.01 LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH Người hướng dẫn khoa học: 1. PGS.TS. Lê Văn Sơn 2. PGS.TS. Nguyễn Mậu Hân HUẾ, NĂM 2016 Công trình được hoàn thành tại: Trường Đại học Khoa học, Đại học Huế. Người hướng dẫn khoa học: 1. PGS.TS. Lê Văn Sơn. 2. PGS.TS. Nguyễn Mậu Hân. Phản biện 1: .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... Phản biện 2: .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... Phản biện 3: .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... Luận án sẽ được bảo vệ tại Hội đồng chấm luận án cấp Đại học Huế họp tại: .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... Vào hồi ... giờ ... ngày ... tháng ... năm ...... Có thể tìm hiểu luận án tại thư viện: .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... Nghiên cứu một số thuật toán lập lịch trên môi trường tính toán đám mây MỞ ĐẦU 1. Lý do chọn đề tài Tính toán đám mây (TTĐM) ra đời xuất phát từ nhu cầu tính toán và yêu cầu dịch vụ với chi phí thấp của người sử dụng. Thực tế, để giải quyết công việc các tổ chức cần tìm ra năng lực tính toán mạnh mẽ và chi phí thấp hơn. Hiện nay có 2 cách cơ bản để giải quyết vấn đề này. Thứ nhất: nâng cấp cơ sở hạ tầng để tính toán, cách này sẽ tốn chi phí và nhân lực lớn; Thứ hai: tận dụng nguồn tài nguyên nhàn rỗi trong các tổ chức hoặc thuê các nguồn tài nguyên từ bên ngoài. Cách giải quyết thứ hai này chính là mục tiêu của TTĐM. TTĐM là sự phát triển của tính toán phân tán, vì vậy nó gặp phải nhiều thách thức lớn cần phải giải quyết. Hiện nay, ngày càng nhiều nhà cung cấp dịch vụ trên TTĐM, mỗi nhà cung cấp có chính sách quản lý tài nguyên khác nhau. Các tài nguyên này rất đa dạng, không đồng nhất và khác nhau về mặt kiến trúc, giao diện, khả năng xử lý, v.v.. Sử dụng hiệu quả các nguồn tài nguyên này hoàn toàn không dễ dàng. Tại mỗi thời điểm có thể có rất nhiều người dùng yêu cầu dịch vụ trên TTĐM, mỗi người dùng có các yêu cầu về ràng buộc khác nhau. Vì vậy, làm sao để đưa ra một lịch trình tối ưu cho người dùng và đem lại lợi ích lớn nhất cho nhà cung cấp là một thách thức lớn cần phải giải quyết. Bài toán lập lịch trên TTĐM phức tạp hơn nhiều so với bài toán lập lịch truyền thống vì việc lập lịch trên TTĐM phải xét trong môi trường phân tán, động, các tài nguyên từ nhiều nhà cung cấp khác nhau, các yêu cầu của người dùng có các ràng buộc chất lượng dịch vụ khác nhau, v.v.. Mô hình ứng dụng trong TTĐM cũng đa dạng hơn rất nhiều so với các mô hình tính toán truyền thống, do đó phải nghiên cứu những thuật toán cụ thể để đáp ứng nhu cầu cho những dạng ứng dụng cụ thể. Chính vì vậy, bài toán kiểm soát đầu vào và lập lịch cho yêu cầu người dùng trên TTĐM là một bài toán khó, chúng ta phải tìm ra các thuật toán tối ưu để giải quyết các bài toán này. Các nghiên cứu trước đây chủ yếu nghiên cứu lập lịch công việc theo hướng hiệu năng về hệ thống, nhằm mục đích tận dụng tối đa hiệu năng của hệ thống. Trên TTĐM, các nhà nghiên cứu tập trung nghiên cứu lập lịch công việc theo hướng hiệu năng về kinh tế nhằm đem lại lợi nhuận cho nhà cung cấp, thời gian thực hiện nhỏ nhất cho người dùng đồng thời phải thỏa mãn các ràng buộc đặt ra của nhà cung cấp và người dùng. Các thuật toán lập lịch trên TTĐM thường là các thuật toán lập lịch động. Vì vậy, làm sao tối ưu thời gian đưa ra lịch trình là vấn đề mà các nhà khoa học hiện nay đang quan tâm và nghiên cứu. Xuất phát từ việc tìm hiểu, nghiên cứu các đặc điểm và các thách thức về các vấn đề lập lịch trên TTĐM, chúng tôi chọn đề tài “Nghiên cứu một số thuật 1 Nghiên cứu một số thuật toán lập lịch trên môi trường tính toán đám mây toán lập lịch trên môi trường tính toán đám mây”. 2. Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu: các tác nhân và hệ thống lập lịch trong TTĐM. Phạm vi nghiên cứu: luận án tập trung nghiên cứu mô hình của tác nhân PaaS và xây dựng các thuật toán kiểm soát đầu vào và lập lịch ở mức nền tảng. 3. Phương pháp nghiên cứu Luận án sử dụng 3 phương pháp: phương pháp tổng hợp và mô hình hóa, phương pháp hệ thống hóa, phương pháp thực nghiệm khoa học. 4. Ý nghĩa khoa học và thực tiễn Ý nghĩa khoa học • Đề xuất các thuật toán lập lịch công việc thời gian thực áp dụng cho lớp các bài toán song song trên TTĐM. Luận án đưa thêm tham số chi phí, kết hợp việc phân nhóm tài nguyên và xử lý song song để đưa ra lịch trình tối ưu về chi phí và thời gian cho các yêu cầu người dùng. • Xây dựng mô hình toán học cho nhà cung cấp PaaS và đề xuất các thuật toán kiểm soát đầu vào và lập lịch theo hướng tối ưu đa mục tiêu trên TTĐM. Áp dụng 2 heuristic ACO và PSO, luận án xây dựng công thức để tính thông tin heuristic và xác xuất của mỗi con kiến; xây dựng hàm thích nghi, vị trí tối ưu cục bộ của mỗi cá thể và vị trí tối ưu toàn cục của cả bầy đàn. Từ đó, xây dựng bài toán và đề xuất các thuật toán kiểm soát đầu vào và lập lịch theo hướng tối ưu đa mục tiêu về chi phí và thời gian. Ý nghĩa thực tiễn: kết quả nghiên cứu nếu được áp dụng trên thực tế sẽ đem lại lợi nhuận cho nhà cung cấp SaaS, tổng thời gian thực hiện thấp và thỏa mãn các ràng buộc QoS của người dùng. Luận án có thể được sử dụng làm tài liệu tham khảo cho sinh viên và học viên cao học ngành Công nghệ Thông tin thực hiện đề tài về lập lịch công việc trong hệ phân tán và nghiên cứu các heuristic về bầy đàn. 5. Bố cục của luận án Luận án được trình bày trong 107 trang, ngoài phần mở đầu (4 trang), kết luận (2 trang), danh mục các công trình khoa học của tác giả liên quan đến luận án (1 trang) và tài liệu tham khảo (8 trang), luận án được chia thành 3 chương. Chương 1 (25 trang) trình bày tổng quan về các vấn đề lập lịch trên tính toán đám mây. Chương 2 (28 trang) xây dựng bài toán và các thuật toán lập lịch công việc thời gian thực trên tính toán đám mây áp dụng cho lớp bài toán song song. Chương 3 (39 trang) xây dựng mô hình, bài toán và thuật toán lập lịch công việc theo hướng tối ưu đa mục tiêu trong tính toán đám mây. 2 Nghiên cứu một số thuật toán lập lịch trên môi trường tính toán đám mây Chương 1. TỔNG QUAN VỀ CÁC VẤN ĐỀ LẬP LỊCH TRÊN TÍNH TOÁN ĐÁM MÂY 1.1. Tổng quan về tính toán đám mây 1.1.1. Giới thiệu TTĐM là sự phát triển của tính toán phân tán, tính toán song song và tính toán lưới. R. Buyya và I. Foster đều định nghĩa TTĐM là một hệ phân tán, cung cấp các dạng tài nguyên ảo dưới dạng các dịch vụ theo nhu cầu của người dùng trên môi trường Internet. 1.1.2. Đặc điểm của tính toán đám mây Các dịch vụ trên TTĐM có những đặc điểm chung như sau: giá rẻ, khả năng co giãn lớn, độ tin cậy cao, dùng chung tài nguyên và độc lập vị trí, khả năng ảo hóa, truy cập diện rộng, dùng bao nhiêu trả bấy nhiêu, độc lập thiết bị và nhiều người thuê. 1.1.3. Kiến trúc của tính toán đám mây Kiến trúc TTĐM được Ian Foster chia thành 4 tầng bao gồm: tầng tác chế, tầng tài nguyên hợp nhất, tầng nền tảng và tầng ứng dụng. 1.1.4. Các mô hình trên tính toán đám mây Theo NIST, TTĐM bao gồm 3 mô hình dịch vụ: SaaS, PaaS và SaaS và 4 mô hình triển khai: đám mây công cộng, đám mây riêng, đám mây cộng đồng và đám mây lai. 1.1.5. Các thách thức trên tính toán đám mây Bên cạnh những lợi ích to lớn, TTĐM hiện nay gặp một số thách thức về bảo mật, lập lịch công việc và tắt nghẽn mạng khi lượng khách hàng lớn. 1.2. Công cụ mô phỏng trên tính toán đám mây 1.2.1. Giới thệu Các nhà nghiên cứu thường sử dụng công cụ mô phỏng để giảm chi phí cũng như tùy biến trong quá trình nghiên cứu. 1.2.2. Một số công cụ mô phỏng trên tính toán đám mây Hiện nay, các nhà nghiên cứu đã xây dựng 4 công cụ mô phỏng trên TTĐM như sau: DCSim, CloudSim, GroudSim và TeachCloud. Theo đánh giá của Rahul Malhotra và Parveen Kumar thì CloudSim là công cụ tổng quát nhất, giúp cho người dùng tự xây dựng một đám mây hoàn chỉnh. 3 Nghiên cứu một số thuật toán lập lịch trên môi trường tính toán đám mây 1.2.3. Công cụ mô phỏng CloudSim CloudSim là bộ công cụ mô phỏng có khả năng mở rộng rất cao. CloudSim cung cấp các công cụ để tạo ra cơ sở hạ tầng, các dịch vụ, các sự kiện điều khiển, v.v. Người lập trình có thể hoàn toàn tạo ra đám mây theo mục đích của mình. 1.3. Bài toán lập lịch trên tính toán đám mây 1.3.1. Giới thiệu Theo P. Brukner lớp các bài toán lập lịch là một bộ ba < R, T, γ >, trong đó: R, T , γ là tập tài nguyên, yêu cầu và tiêu chí tối ưu của bài toán. Một lịch trình được xác định bởi hàm f : T → R, trong đó mỗi yêu cầu ti ∈ T được ánh xạ vào tài nguyên rj ∈ R. 1.3.2. Mô hình tổng quát để lập lịch trên các trung tâm dữ liệu Mô hình tổng quát để lập lịch trên TTĐM bao gồm các tác nhân và hệ thống lập lịch. Các tác nhân bao gồm người dùng, nhà cung cấp dịch vụ SaaS, PaaS và IaaS. Hệ thống lập lịch bao gồm các chức năng ở mức ứng dụng và ở mức nền tảng. 1.3.3. Các phương pháp lập lịch Bài toán lập lịch được giải quyết bằng bốn phương pháp: phương pháp liệt kê, phương pháp heuristic, phương pháp nới giảm tham số và phương pháp xấp xỉ. 1.3.4. Mô hình kinh tế cho bài toán lập lịch Trong mô hình kinh tế, chủ yếu tập trung lập lịch trên hai chiến lược: dựa trên thị trường (market-based) và lập lịch dựa trên đấu giá (auction-based). 1.4. Các nghiên cứu liên quan đến lập lịch trên tính toán đám mây Lập lịch trong các hệ phân tán như tính toán lưới và TTĐM có hai cách tiếp cận chính: hướng hiệu năng về hệ thống và hướng đến hiệu năng về kinh tế. Y. Chawla đã chia lập lịch công việc trên TTĐM thành các 5 loại: lập lịch tĩnh, lập lịch động, lập lịch heuristic, lập lịch luồng công việc và lập lịch công việc thời gian thực. 1.4.1. Lập lịch tĩnh và động Năm 2010, S. Pandey đã đề xuất thuật toán lập lịch cho các bài toán có khối lượng công việc lớn. Tuy nhiên, các thuật toán này bỏ qua chi phí tính toán chỉ quan tâm đến chi phí truyền thông. Năm 2013, S.Nagadevi đã liệt kê các kỹ thuật lập lịch tĩnh, các kỹ thuật này chỉ áp dụng cho các yêu cầu độc lập, các máy ảo chỉ thực hiện tuần tự và thời gian sẵn sàng của mỗi máy ảo được cập nhật sau khi yêu cầu được hoàn thành. Năm 2012, Z. Lee và M. Choudhary đã đề xuất các thuật toán lập lịch ưu tiên động, các thuật toán xem xét trên cả nhà cung cấp dịch vụ, nhà cung cấp tài nguyên và khách hàng để đưa ra thuật toán nhằm đem lại thời gian và chi phí nhỏ nhất nhưng không xem xét trên các ràng buộc thời hạn và ngân sách của các yêu cầu. Từ năm 2010 đến 2013, J. Deng, Lee và HanZhao đã đưa ra mô hình lập lịch cho các yêu cầu trên TTĐM với mục 4 Nghiên cứu một số thuật toán lập lịch trên môi trường tính toán đám mây tiêu đem lại lợi nhuận cho nhà cung cấp dịch vụ nhưng chỉ xem xét đến chi phí tính toán, chưa xem xét đến chi phí truyền thông và thời gian gối đầu giữa các yêu cầu. 1.4.2. Lập lịch heuristic Từ năm 2010 đến 2012, R. Buyya và các đồng sự đã đề xuất các thuật toán lập lịch các công việc trên TTĐM theo hướng hiệu năng về hệ thống. Nhóm tác giả đã kết hợp với xử lý song song, heuristics động và P SO để xử lý các công việc với khối lượng lớn. Tuy nhiên các thuật toán chỉ áp dụng cho các lớp bài toán có khối lượng lớn, thời gian truyền dữ liệu lớn hơn nhiều so với thời gian tính toán. K. Li (2011) và S. Zhan (2012) sử dụng các heuristic về bầy đàn để đưa ra lịch trình tối ưu về thời gian thực hiện, không quan tâm đến ràng buộc QoS của người dùng. Để tối ưu về thời gian thực hiện, K. Liu (2009), X. Song(2011), Z. Bo(2011), V. D. Bossche (2012) sử dụng các heuristic ACO, GA nhằm đưa ra lịch trình với mục tiêu đem lại thời gian hoàn thành nhỏ nhất cho hệ thống nhưng vẫn thỏa mãn ràng buộc QoS của người dùng. Các nghiên cứu này chỉ tập trung vào ràng buộc về thời gian, không quan tâm đến chi phí của hệ thống. 1.4.3. Lập lịch luồng công việc Năm 2008, Z. Yu đề xuất thuật toán lập lịch trên đa luồng. Thuật toán này lập lịch cho các yêu cầu dựa trên độ ưu tiên của mỗi yêu cầu nhưng không xem xét đến ràng buộc QoS của người dùng. Năm 2012, S. K. Jayadivya tập trung lập lịch trên đa luồng, dựa vào ràng buộc QoS của người dùng. Các thuật toán này đưa ra lịch trình có thời gian thực hiện và chi phí thấp nhưng không quan tâm đến ngân sách của các yêu cầu. 1.4.4. Lập lịch công việc thời gian thực Từ năm 2010 đến 2011, S. Liu, Y.Gu và Zhu tập trung lập lịch trên các công việc thời gian thực thỏa mãn các ràng buộc QoS của người dùng. Tuy nhiên, các thuật toán này chưa áp dụng kỹ thuật xử lý song song để tận dụng hết khả năng của máy ảo, chưa tận dụng được khoảng thời gian gối đầu giữa các yêu cầu để tiết kiệm chi phí. Năm 2013, N. Ramkumar nghiên cứu lập lịch trên các yêu cầu thời gian thực đã sử dụng hàng đợi ưu tiên để ánh xạ yêu cầu vào tài nguyên nhưng chỉ tập trung lập lịch để giải quyết công việc một cách nhanh nhất thỏa mãn thời hạn của yêu cầu mà không quan tâm đến chi phí và ngân sách của nó. 1.5. Mục tiêu của đề tài Mục tiêu nghiên cứu chính của luận án: xây dựng mô hình và bài toán để lập lịch công việc thời gian thực áp dụng cho lớp bài toán song song; xây dựng mô hình và bài toán lập lịch công việc trên nhà cung cấp PaaS theo hướng tối ưu đa mục tiêu về chi phí và thời gian; đề xuất các thuật toán lập lịch công việc thời gian thực áp dụng cho lớp bài toán song song và các thuật toán kiểm soát đầu vào và lập lịch công việc theo hướng tối ưu đa mục tiêu. 5 Nghiên cứu một số thuật toán lập lịch trên môi trường tính toán đám mây Chương 2. LẬP LỊCH CÔNG VIỆC THỜI GIAN THỰC TRONG TÍNH TOÁN ĐÁM MÂY 2.1. Mô hình lập lịch truyền thống Các nghiên cứu trước đây, bài toán lập lịch giả thuyết rằng số lượng các công việc và số lượng các máy tham gia tính toán là cố định. M. L. Pinedo đã đưa ra mô hình của bài toán lập lịch bao gồm 3 thành phần: mô hình các máy tham gia lập lịch, mô hình công việc và mục tiêu của bài toán. 2.2. Mô hình lập lịch công việc thời gian thực Mục tiêu chính của lập lịch công việc thời gian thực là tăng công suất, tận dụng tối đa hiệu năng của hệ thống sao cho thỏa mãn thời hạn cho các công việc. Luận án xây dựng bài toán lập lịch với các ràng buộc của người dùng trong các ứng dụng song song và xem xét việc lựa chọn tài nguyên theo hai mục tiêu: thời gian hoàn thành các công việc là nhỏ nhất nhưng vẫn thỏa mãn thời hạn và ngân sách của các yêu cầu; chi phí thực hiện là nhỏ nhất nhưng thỏa mãn ràng buộc QoS cho các yêu cầu. 2.2.1. Mô tả bài toán Ứng dụng bao gồm tập các yêu cầu T , mỗi yêu cầu ti ∈ T có thời điểm đến là ai , thời hạn là di (chỉ rõ bằng phút) và ngân sách (budget) là bi (chỉ rõ bằng $) và khối lượng công việc là wi . Khối lượng công việc của mỗi yêu cầu được song song hóa vào các đơn vị nhỏ hơn (yêu cầu con), kích cỡ nhỏ nhất của yêu cầu con là p. R là tập tài nguyên có sẵn và có thể thực hiện song song. Mỗi tài nguyên rj ∈ R có tốc độ tính toán sj và tương ứng chi phí cj để thuê máy ảo. Tốc độ sj là số chu kỳ của tài nguyên có thể hoàn thành trên phút. Người dùng trả chi phí cj để thuê tài nguyên rj trong khoảng D phút liên tục, D là đơn vị nhỏ nhất để thuê. Bài toán thứ nhất có thể mô tả như sau: “Tìm một ánh xạ từ tập yêu cầu T vào một tập con của tập tài nguyên R để tối thiểu tổng thời gian thực hiện trong khi vẫn thỏa mãn thời hạn và ngân sách của các yêu cầu trong T ”. Bài toán thứ 2: “Tìm một ánh xạ từ tập yêu cầu T vào một tập con của tập tài nguyên R để nhỏ nhất toàn bộ chi phí trong khi vẫn thỏa mãn thời hạn và ngân sách của các yêu cầu trong T ” 2.2.2. Mô hình toán học cho bài toán Luận án mở rộng mô hình của K.H. Kim và K. Kumar, ngoài thời hạn chúng ta phải xem xét ngân sách của các yêu cầu, đảm bảo các yêu cầu được thực hiện trước thời hạn và không vượt quá ngân sách của nó. Gọi R = {r1 , r2 , ..., rM } là tập M tài nguyên tính toán, 6 Nghiên cứu một số thuật toán lập lịch trên môi trường tính toán đám mây các tài nguyên này có thể thực hiện song song. Mỗi tài nguyên rj ∈ R là bộ , trong đó sj là tốc độ tính toán tính trên phút, cj là chi phí để thuê tài nguyên trong khoảng thời gian D phút. Các tài nguyên này là nguồn tính toán cho N yêu cầu độc lập, được biểu diễn bởi tập T = {t1 , t2 , . . . , tN }, mỗi yêu cầu ti ∈ T là một bộ 4 . Gọi amin , dmax là thời điểm đến nhỏ nhất và thời hạn lớn nhất của tất cả các yêu cầu. Ký hiệu α(j, k, x) để thể hiện việc chọn tài nguyên:  1 nếu tại phút x, tài nguyên rj được sử dụng từ 1 đến k lần. α(j, k, x) = 0 nếu tại phút x, tài nguyên r không được sử dụng. (2.1) j Tổng chi phí của các tài nguyên tại phút thứ x (x = amin ..dmax ) được tính như sau: Scost (x) = y M X X cj j=1 k=1 D Trong đó, M là số tài nguyên trong R, y = C= C p N X × α(j, k, x) (2.2) với: wi (2.3) i=1 p = min{sj , j = 1..M } (2.4) Tổng số chu kỳ thực hiện tại phút thứ x được xác định như sau: Scycle (x) = y M X X sj × α(j, k, x) (2.5) j=1 k=1 2.2.3. Mục tiêu tối ưu về chi phí Để đạt được mục tiêu nhỏ nhất về chi phí thì phải tìm cực tiểu tổng chi phí: dX max Scost (x) → min (2.6) x=amin Để đạt mục tiêu như công thức (2.6) thì phải thỏa mãn hai ràng buộc của yêu cầu ti ∈ T : di X Scost (x) ≤ bi (2.7) Scycle (x) ≥ wi (2.8) x=ai di X x=ai 2.2.4. Mục tiêu tối ưu về thời gian Để đạt được mục tiêu tối ưu về thời gian thực hiện cho các yêu cầu thì phải tìm cực đại tổng số chu kỳ: dX max Scycle (x) → max x=amin Để đạt được mục tiêu trên thì phải thỏa mãn hai ràng buộc ở (2.7) và (2.8). 7 (2.9) Nghiên cứu một số thuật toán lập lịch trên môi trường tính toán đám mây 2.3. Tối ưu về kinh tế Mỗi máy ảo của nhà cung cấp IaaS được thuê trong D-phút và nhà cung cấp SaaS phải trả một chi phí cố định trong D-phút được thuê, nếu họ không sử dụng hết D-phút thì họ cũng phải trả chi phí cho toàn bộ D-phút. Luận án tận dụng khoảng thời gian còn hiệu lực trong vòng D-phút được thuê của yêu cầu này để thực hiện cho yêu cầu khác nhằm đem lại lợi nhuận cao nhất cho nhà cung cấp SaaS. Gọi Ti là tập các yêu cầu trong cùng một nhà cung cấp với yêu cầu ti và gối đầu lên yêu cầu ti , các yêu cầu này có thể chia sẻ cùng 1 máy ảo. Ti được xác định như sau:  Ti = tl |dl ≥ di và al < di (2.10) Gọi tiljx là thời gian còn hiệu lực để tính toán cho yêu cầu tl sau khi đã thực hiện xong yêu cầu ti trên máy ảo vmjx . tiljx được xây dựng như sau:   min(D − Uiljx , dl − al ) nếu al − ai ≥ swijxi    tiljx = D − Uiljx nếu al − ai < swi và dl − ai ≥ D ijx    d − (a + U )nếu a − a < wi và d − a < D l Trong đó: Uiljx = wi sijx i iljx l i l sijx (2.11) i + max(al − di , 0) và sijx là tốc độ của vmjx được ánh xạ vào ti . Nếu xét trên một nhà cung cấp IaaS thì công thức (2.11) được xây dựng lại như sau:   min(D − Uilj , dl − al ) nếu al − ai ≥ swiji    tilj = D − Uilj nếu al − ai < swi và dl − ai ≥ D (2.12) ij    d − (a + U )nếu a − a < wi và d − a < D l i ilj l i sij l i 2.4. Thuật toán lập lịch trên các hệ thống thời gian thực 2.4.1. Thuật toán lập lịch tối ưu về thời gian Các thuật toán này được sử dụng để giải quyết bài toán thứ nhất. 2.4.1.1. Thuật toán CT O Các bước của Thuật toán CT O được mô tả ở Thuật toán 2.1 Nhận xét: mặc dù thuật toán CT O tối ưu về thời gian, đảm bảo các yêu cầu hoàn thành trước thời hạn của nó, nhưng thuật toán này còn một số hạn chế: thuật toán CT O chỉ xem xét số tài nguyên (máy ảo) trên một nhà cung cấp, nếu xét trên nhiều nhà cung cấp thì độ phức tạp của thuật toán sẽ lớn; các yêu cầu luôn hoàn thành trước thời hạn nhưng có thể không thỏa mãn ngân sách của nó; thời gian thuê tài nguyên là D phút nhưng có thể có nhiều yêu cầu không sử dụng hết D phút. 2.4.1.2. Thuật toán M IN C Để khắc phục các hạn chế của thuật toán CT O, chúng tôi xây dựng thuật toán M IN C nhằm tận dụng khoảng thời gian còn hiệu lực giữa các yêu cầu với mục tiêu tối ưu về chi 8 Nghiên cứu một số thuật toán lập lịch trên môi trường tính toán đám mây Thuật toán 2.1: CTO Đầu vào: • T = {t1 , t2 , . . . , tN }, ∀ti ∈ T là một bộ 4 < ai , di , bi , wi >; • R = {r1 , r2 , ..., rM }, ∀rj ∈ R là bộ Đầu ra : Mảng kết quả Result chứa số lượng các tài nguyên cho mỗi yêu cầu; Phương pháp: 1 Chọn ngưỡng ρ ∈ N : 1 ≤ ρ ≤ p, p được xác định như công thức (2.4); 2 Sắp xếp các tài nguyên theo thứ tự giảm dần của tốc độ; 3 Dựa vào ngưỡng ρ để nhóm các tài nguyên theo tốc độ; 4 G :=số nhóm tài nguyên nhóm được; 5 RG := {g1 , g2 , ..., gG }, gl ∈ G chứa các tài nguyên của nhóm; 6 Trên mỗi nhóm, sắp xếp các tài nguyên theo thứ tự tăng dần của chi phí; 7 Result:= CalculateParallel(RG,T ); Function CalculateParallel(RG,T ) 1 Tạo G luồng (thread) chạy đồng thời: T H := {th1 , th2 , ..., thG }, thj ∈ T H tìm kiếm tài nguyên tương ứng trên nhóm gj ∈ RG; 2 3 foreach thj ∈ T H do foreach ti ∈ T do 4     w i ; Tính số lượng của tài nguyên đầu tiên r1 ∈ gj cho ti : sli :=  (di − ai ) × s1  5 if wi > (di − ai ) × s1 và |gj | = 1 then 6 7 8 9 10 sli := sli + 1; else if wi > (di − ai ) × s1 then Tính số lượng các tài nguyên còn lại của nhóm gj cho ti ; Result[j, i] := Số lượng và tên tài nguyên trong gj được thực hiện cho ti ; phí. Thuật toán M IN C bao gồm các bước được mô tả ở Thuật toán 2.2. 2.4.1.3. Phân tích thuật toán CT O và M IN C • Đầu vào của thuật toán CT O và M IN C: tập R được xác định vì tại thời điểm lập lịch dựa vào thông tin của hệ thống ta có thể xác định được số lượng tài nguyên trên trung tâm dữ liệu. Sự hình thành của tập T và U ST trong thuật toán CT O và M IN C được giới hạn vì các yêu cầu được lập lịch theo lô và theo một chu kỳ. • Đối với thuật toán CT O: sau khi thực hiện từ câu lệnh 1 đến câu lệnh 6, ta có G nhóm tài nguyên độc lập, các tài nguyên đầu tiên của mỗi nhóm sẽ có chi phí thấp 9 Nghiên cứu một số thuật toán lập lịch trên môi trường tính toán đám mây Thuật toán 2.2: MINC Đầu vào: • U ST := T ; • Mảng Result ; /* tập các yêu cầu chưa lập lịch */ /* Mảng kết quả là đầu ra của thuật toán CT O. */ Đầu ra : ST là lịch trình để ánh xạ các yêu cầu vào các tài nguyên; Phương pháp: 1 ST := ∅; 2 if tìm thấy ti ∈ U ST thỏa mãn thời hạn và ngân sách trong Result then 3 k:= vị trí của dòng trên Result tìm thấy ti ; 4 P U SH(ti ); U ST := U ST \ {ti }; ST := ST ∪ {ti → Result [k, i]}; 5 while (U ST 6= ∅) do ti := P OP () ;  Tìm Ti := tl |dl ≥ di và al < di ; 6 7 /* Lấy ti từ ngăn xếp */ Tính tilj trên tài nguyên cuối cùng được ánh xạ bởi yêu cầu ti như công thức  wi    min (D − Uilj , dl − al ) nếu al − ai ≥ sij ; (2.12): tilj := D − Uilj nếu al − ai < swiji và dl − ai ≥ D    d − (a + U ) nếu a − a < wi và d − a < D 8 l i il l i sijx l i Dựa trên tilj tính được trong Ti để cập nhật lại khối lượng cho các yêu cầu 9 trong Ti và tìm ra yêu cầu tl ∈ Ti có khoảng thời gian gối đầu lớn nhất vừa thỏa mãn thời hạn và ngân sách; if tìm thấy tl then 10 11 P U SH(tl ); U ST := U ST \ {tl }; 12 ST := ST ∪ {tl → Result [k, l]}; else 13 Lặp lại bước 2 để tìm yêu cầu tiếp theo; 14 15 16 else Thông báo các yêu cầu ti ∈ U ST bị từ chối; nhất so với các tài nguyên còn lại của nhóm và các tài nguyên của nhóm đầu tiên sẽ có tốc độ lớn nhất. Vì G nhóm tài nguyên này độc lập nên ta có thể áp dụng mô hình lập trình chia xẻ bộ nhớ để tạo ra G luồng chạy đồng thời, mỗi luồng sẽ tính toán tài nguyên trên mỗi nhóm tương ứng. Trên mỗi luồng sẽ ưu tiên ánh xạ yêu cầu vào tài nguyên đầu tiên của mỗi nhóm, điều này sẽ làm giảm chi phí cho cả hệ thống. Vì thuật toán sử dụng G luồng chạy đồng thời nên sẽ tối ưu thời gian đưa ra các lịch trình của thuật toán. • Thời gian thuê tài nguyên là D-phút, do đó có thể một yêu cầu nào đó hoàn thành 10 Nghiên cứu một số thuật toán lập lịch trên môi trường tính toán đám mây công việc của mình với thời gian ít hơn D-phút nhưng phải trả chi phí trong vòng D-phút. Thuật toán M IN C tận dụng khoảng thời gian còn hiệu lực này để thực hiện cho yêu cầu tiếp theo, điều này dẫn đến chi phí thực hiện cho cả hệ thống giảm xuống và đem lại lợi ích cho nhà cung cấp SaaS. • Độ phức tạp của thuật toán CT O là O(max(M × log2M , G, N × M )). Nếu N > log2M thì độ phức tạp của CT O là O(N × M ), ngược lại thì độ phức tạp của CT O là O(M × log2M ). Độ phức tạp của thuật toán M IN C là O(max(N 2 , N × G)), trường hợp xảy ra nhiều nhất là N > G thì độ phức tạp của M IN C là O(N 2 ), ngược lại thì độ phức tạp của M IN C là O(N × G). 2.4.1.4. Mô phỏng và đánh giá thuật toán Các thuật toán được cài đặt mô phỏng bằng công cụ CloudSim 2.0, sử dụng 1 DataCenter, 2 host, 50 máy ảo, số yêu cầu thay đổi từ 100 đến 250. Lịch trình đưa ra của thuật toán CT O và M IN C được so sánh với thuật toán tham lam EDF . (a) So sánh tổng thời gian của 3 thuật toán khi thay(b) So sánh tổng chi phí của 3 thuật toán khi thay đổi số yêu cầu đổi số yêu cầu (c) So sánh tổng thời gian thực hiện của 3 thuật toán(d) So sánh tổng chi phí của 3 thuật toán khi thay khi thay đổi ρ đổi ρ Hình 2.1: So sánh tổng chi phí và thời gian khi thay đổi số yêu cầu và ngưỡng Phân tích tổng thời gian và chi phí thực hiện khi thay đổi số yêu cầu 11 Nghiên cứu một số thuật toán lập lịch trên môi trường tính toán đám mây Hình 2.1(a) và (b) trình bày tổng thời gian thực hiện và tổng chi phí của các thuật toán khi ρ = 5, D = 60, sử dụng 50 máy ảo và các yêu cầu thay đổi từ 100 đến 250. Phân tích tổng thời gian và tổng chi phí khi thay đổi số ngưỡng ρ Chúng tôi thay đổi ngưỡng ρ từ 1 đến 5, D = 60, sử dụng 250 yêu cầu và 50 máy ảo, kết quả của các thuật toán được thể hiện ở Hình 2.1(c) và Hình 2.1(d). 2.4.2. Thuật toán lập lịch tối ưu về chi phí 2.4.2.1. Thuật toán T CO Các bước của Thuật toán T CO được mô tả trong thuật toán 2.3. Thuật toán 2.3: TCO Đầu vào: • T = {t1 , t2 , . . . , tN }, ∀ti ∈ T là một bộ 4 < ai , di , bi , wi >; • R = {r1 , r2 , ..., rM }, ∀rj ∈ R là bộ Đầu ra : Mảng Result để xác định số lượng các tài nguyên cho mỗi yêu cầu; Phương pháp: 1 Chọn ngưỡng ρ ∈ (0, 1] ; 2 Sắp xếp các tài nguyên theo thứ tự tăng dần của chi phí; 3 Dựa vào ngưỡng ρ để nhóm các tài nguyên theo chi phí; 4 G := số nhóm tài nguyên nhóm được; 5 RG := {g1 , g2 , ..., gG }, gl ∈ G chứa các tài nguyên của nhóm; 6 Trên mỗi nhóm, sắp sếp các tài nguyên theo thứ tự giảm dần của tốc độ; 7 Result:= CalculateParallel(RG, T ); 2.4.2.2. Mô phỏng và đánh giá thuật toán Giống như thuật toán CT O, thuật toán T CO được cài đặt mô phỏng bằng công cụ CloudSim 2.0, sử dụng 1 DataCenter, 2 host, 50 máy ảo, số yêu cầu thay đổi từ 100 đến 250. Lịch trình đưa ra của thuật toán T CO và M IN C được so sánh với thuật toán tham lam EDF . Phân tích tổng chi phí và thời gian thực hiện khi thay đổi số yêu cầu Hình 2.2 (a) và (b) trình bày tổng chi phí và tổng thời gian thực hiện của 3 thuật toán T CO, M IN C và EDF khi ρ=0.5, D=60, sử dụng 50 máy ảo và các yêu cầu thay đổi từ 100 đến 250. Phân tích tổng chi phí và tổng thời gian khi thay đổi ngưỡng ρ Hình 2.2 (c) và (d) trình bày kết quả của các thuật toán khi thay đổi ngưỡng ρ từ 0.1 đến 0.5, D = 60, sử dụng 200 yêu cầu và 50 máy ảo. 12 Nghiên cứu một số thuật toán lập lịch trên môi trường tính toán đám mây (a) So sánh tổng chi phí của 3 thuật toán khi thay(b) So sánh tổng thời gian của 3 thuật toán khi thay đổi số yêu cầu đổi số yêu cầu (c) So sánh tổng chi phí của 3 thuật toán khi thay(d) So sánh tổng thời gian thực hiện của 3 thuật toán đổi ρ khi thay đổi ρ Hình 2.2: So sánh tổng chi phí và thời gian khi thay đổi số yêu cầu và ngưỡng 2.5. Tiểu kết Chương 2 Chương này tập trung mô tả và xây dựng mô hình cho bài toán lập lịch thời gian thực trong các ứng dụng song song. Kết hợp với xử lý song song và phân nhóm, luận án đưa ra 3 thuật toán CT O, M IN C và T CO để giải quyết 2 bài toán: • Bài toán lập lịch trên các hệ thống thời gian thực theo hướng tối ưu về thời gian. • Bài toán lập lịch trên các hệ thống thời gian thực theo hướng tối ưu về chi phí. 13 Nghiên cứu một số thuật toán lập lịch trên môi trường tính toán đám mây Chương 3. LẬP LỊCH CÔNG VIỆC THEO HƯỚNG TỐI ƯU ĐA MỤC TIÊU TRONG TÍNH TOÁN ĐÁM MÂY 3.1. Mô hình lập lịch theo hướng tối ưu đa mục tiêu Trong TTĐM, mỗi tác nhân đều có yêu cầu dịch vụ hoặc cung cấp dịch vụ với các mục tiêu khác nhau như nhà cung cấp SaaS cần đem lại lợi ích lớn nhất cho mình; nhà cung cấp PaaS cần tận dụng tài nguyên một cách hiệu quả, v.v. 3.1.1. Mô hình người dùng Luận án mở rộng mô hình người dùng của R. Buyya bằng cách phát triển thêm các thuộc tính như thời hạn, ngân sách, v.v. Xét trên N yêu cầu dịch vụ T = {t1 , t2 , . . . , tN }, mỗi yêu cầu ti ∈ T là một bộ 7 < ai , di , bi , αi , wi , ini , outi >, trong đó: ai : thời điểm đến của yêu cầu; thời hạn di ; ngân sách bi ; tỉ lệ lãi suất phạt αi ; khối lượng công việc wi ; kích cỡ file đầu vào và đầu ra của yêu cầu: ini và outi 3.1.2. Mô hình nhà cung cấp IaaS Xem xét trên Y nhà cung cấp IaaS: X = {1, 2, .., Y }. Mỗi nhà cung cấp x ∈ X cung cấp Mx máy ảo cho các nhà cung cấp SaaS, được biểu diễn bởi tập V Mx = {vm1x , vm2x , . . . , vmMx x }. Theo mô hình IaaS của R. Buyya, mỗi máy ảo vmjx ∈ V Mx là một bộ 5 < tjx , pjx , sjx , dtpjx , dtsjx >, trong đó: thời gian khởi tạo tjx ; giá pjx ; tốc độ xử lý sjx ; giá tính theo dung lượng truyền dtpjx ; tốc độ truyền dtsjx 3.1.3. Mô hình nhà cung cấp PaaS Luận án đề xuất mô hình nhà cung cấp PaaS là bộ ba: < R, npmtn, Cmin > và < R, npmtn, Tmin >. Trong đó, R là tập các nhà cung cấp IaaS độc lập và tài nguyên trong các nhà cung cấp có thể thực hiện song song, npmtn là tập N yêu cầu độc lập không theo thứ tự ưu tiên (non-preemptive). Mục đích của chúng tôi là lập lịch cho các yêu cầu người dùng trên tập tài nguyên của các nhà cung cấp IaaS theo hướng tối ưu về chi phí và tối ưu về thời gian nghĩa là phải tìm ra Cmin và Tmin . Gọi Cijx là chi phí để xử lý yêu cầu ti ∈ T trên máy ảo vmjx ∈ V Mx . Theo mô hình của người dùng và mô hình của nhà cung cấp IaaS, chi phí Cijx được tính như sau: Cijx = CPijx + CT Dijx + CIijx + CRijx , trong đó: wi CPijx = pjx × sjx CT Dijx = dtpjx × ini + outi dtsjx CIijx = tijx × pijx 14 (3.1) (3.2) (3.3) Nghiên cứu một số thuật toán lập lịch trên môi trường tính toán đám mây CRijx = αi × βijx (3.4) Gọi Tijx là thời gian để xử lý yêu cầu ti ∈ T trên máy ảo vmjx ∈ V Mx : Tijx = CTijx + DTijx + T Iijx + βijx (3.5) Trong đó: wi sjx (3.6) ini + outi dtsjx (3.7) CTijx = DTijx = T Iijx : thời gian khởi tạo máy ảo đã có. βijx : thời gian vượt thời hạn. Hàm mục tiêu về chi phí cho yêu cầu ti ∈ T được biểu diễn như sau: fcost (ti ) = min x=1..Y, j=1..Mx {Cijx } (3.8) và mục tiêu của nhà cung cấp SaaS là tìm cực đại của tổng lợi nhuận: N X (bi − fcost (ti )) → max (3.9) i=1 và thỏa mãn 2 ràng buộc cho yêu cầu ti : Cijx < bi (3.10) Tijx ≤ di + βijx (3.11) Hàm mục tiêu về thời gian cho yêu cầu ti ∈ T được biểu diễn như sau: ftime (ti ) = min x=1..Y, j=1..Mx {Tijx } và mục tiêu của người dùng là tìm cực tiểu tổng thời gian thực hiện: N X (ftime (ti )) → min (3.12) (3.13) i=1 và thỏa mãn 2 ràng buộc ở công thức (3.10) và (3.11). 3.2. Xây dựng bài toán theo hướng tối ưu đa mục tiêu Trong phần này chúng tôi nghiên cứu các phương pháp heuristic ACO và P SO để xây dựng bài toán nhằm đạt được mục tiêu cho người dùng và nhà cung cấp SaaS. 3.2.1. Tối ưu hóa đàn kiến (ACO) Thuật toán ACO dựa trên hành vi của đàn kiến trong tự nhiên được Marco Dorigo giới thiệu, để áp dụng thuật toán ACO vào bài toán cụ thể, luận án xây dựng các thông tin: hàm cực tiểu F , thông tin heuristic η, cập nhật lại mùi và xác suất P như sau: Với mục tiêu tối ưu về chi phí, hàm cực tiểu F và thông tin heuristic để yêu cầu ti ∈ T tìm ra máy ảo vmx ∈ V Mx được xác định như sau: F (ti ) = min x=1..Y, j=1..Mx 15 {Cijx } (3.14) Nghiên cứu một số thuật toán lập lịch trên môi trường tính toán đám mây ηijx = 1 Cijx (3.15) Với mục tiêu tối ưu về thời gian, hàm cực tiểu F và ηijx được xác định như sau: F (ti ) = min x=1..Y, j=1..Mx ηijx = {Tijx } 1 Tijx Cập nhật lại mùi để lại khi kiến đi qua: τijx = (1 − ρ)τijx + ∆τijx Xác suất để yêu cầu ti ∈ T chọn máy ảo vmjx ∈ V Mx : τijx ηijx Pijx = PY PMx x=1 j=1 τijx ηijx (3.16) (3.17) (3.18) (3.19) Với mục tiêu tối ưu về chi phí, xác suất để ti ∈ T chọn vmjx ∈ V Mx được tính như sau:   1 (1 − ρ)τijx + F1−ρ (ti ) Cijx  (3.20) Pijx = P PMx  Y 1−ρ 1 (1 − ρ)τ + ijx x=1 j=1 F (ti ) Cijx Với mục tiêu tối ưu về thời gian, xác suất để ti ∈ T chọn vmjx ∈ V Mx :   1 (1 − ρ)τijx + F1−ρ (ti ) Tijx  Pijx = P PMx  Y 1−ρ 1 (1 − ρ)τ + ijx x=1 j=1 F (ti ) Tijx (3.21) 3.2.2. Tối ưu hóa bầy đàn (P SO) Thuật toán P SO dựa trên kinh nghiệm của bầy đàn được đề xuất bởi Eberhart và Kennedy. Để áp dụng thuật toán P SO vào bài toán cụ thể, luận án xây dựng các thông tin: vị trí, vận tốc, hàm thích nghi, vị trí tối ưu cục bộ của từng cá thể và vị trí tối ưu toàn cục của cả bầy đàn như sau: M.Clerc đã đưa ra công thức để cập nhật lại vị trí và vận tốc sau mỗi thế hệ như sau:
vxj+1 = K ωvxj + c1 z1 (P bestx − posjx ) + c2 z2 (Gbest − posjx ) (3.22) posj+1 = posjx + vxj+1 x (3.23) Trong đó: K là hệ số hội tụ, posjx : vị trí hiện tại của cá thể thứ x tại chiều j; posj+1 x : vị trí của cá thể x tại chiều j + 1; c1 ,c2 : hệ số gia tốc; z1 ,z2 : là số ngẫu nhiên giữa 0 và 1; vxj : vận tốc của cá thể x tại chiều j; P bestx : vị trí cục bộ tốt nhất của cá thể x; Gbest: vị trí tốt nhất toàn cục của toàn bộ bầy đàn. Hàm thích nghi về chi phí để cá thể x chọn máy ảo vmjx ∈ V Mx cho yêu cầu ti ∈ T : 1 Fcost (posjix ) = (3.24) Cijx Vị trí tối ưu cục bộ về chi phí của cá thể x tại chiều j + 1 cho ti được xác định: 16 Nghiên cứu một số thuật toán lập lịch trên môi trường tính toán đám mây ( pbj+1 ix = j pbj+1 nếu Fcost (posj+1 ix ix ) ≥ Fcost (posix ) và Cijx ≤ bi và Tijx ≤ di + βijx pbjix ngược lại (3.25) Vị trí tối ưu cục bộ (P bestx ) được xác định: P bestx = max x=1..Y, j=1..Mx {pbjix } (3.26) Vị trí tối ưu toàn cục của cả đàn (Gbest) xác định như sau: Gbest = max {P bestx } x=1..Y (3.27) 3.3. Thuật toán lập lịch tối ưu đa mục tiêu dựa trên ACO 3.3.1. Phát biểu bài toán Ứng dụng bao gồm N yêu cầu dịch vụ, được biểu diễn bởi tập T = {t1 , t2 , . . . , tN }, mỗi yêu cầu ti ∈ T là một bộ 7 < ai , di , bi , αi , wi , ini , outi > được gửi lên nhà cung cấp SaaS bao gồm các thuộc tính và các ràng buộc QoS như thể hiện ở phần 3.1.1. Nhà cung cấp SaaS thuê các tài nguyên từ Y nhà cung cấp IaaS. Mỗi nhà cung cấp x (x = 1..Y ) cung cấp Mx máy ảo, mỗi máy ảo vmjx ∈ V Mx là một bộ 5 < tjx , pjx , sjx , dtpjx , dtsjx > như thể hiện ở phần 3.1.2. Khi nhận được tập các yêu cầu của người dùng, nhà cung cấp PaaS tiến hành tính toán chi phí và thời gian thực hiện như mô hình ở phần 3.1.3. Từ đó, ra quyết định từ chối hay chấp nhận yêu cầu người dùng. Nếu yêu cầu nào được chấp nhận thì bộ lập lịch sẽ ánh xạ vào tài nguyên hợp lý. 3.3.2. Thuật toán lập lịch tối ưu đa mục tiêu về chi phí 3.3.2.1. Thuật toán ACACO Mục tiêu của thuật toán ACACO nhằm đem lại lợi ích lớn nhất cho nhà cung cấp SaaS. Các bước của thuật toán được mô tả trong Thuật toán 3.1. 3.3.2.2. Thuật toán lập lịch M P rof it Thuật toán M P rof it tận dụng khoảng thời gian còn hiệu lực trong vòng D-phút được thuê của các yêu cầu nằm trong cùng một nhà cung cấp để đem lại lợi nhuận cao nhất cho nhà cung cấp SaaS. Các bước của thuật toán M prof it được mô tả ở thuật toán 3.2. 3.3.2.3. Phân tích thuật toán ACACO và M prof it • Thomas Stutzle, Marco Dorigo đã chứng minh tính hội tụ của thuật toán ACO điều này đảm bảo tính hội tụ của thuật toán ACACO đề xuất. • Giống như thuật toán CT O, tại thời điểm lập lịch tập dữ liệu đầu vào X, V Mx và T hoàn toàn được xác định. • Thuật toán ACACO ánh xạ yêu cầu ti ∈ T vào máy ảo vmjx ∈ V Mx dựa vào xác suất Pijx như công thức (3.20). Vì vậy, khi chi phí của máy ảo vmjx càng bé thì 17 Nghiên cứu một số thuật toán lập lịch trên môi trường tính toán đám mây Thuật toán 3.1: ACACO Đầu vào: • T = {t1 , t2 , . . . , tN }, ∀ti ∈ T là một bộ 7 < ai , di , bi , αi , wi , ini , outi > ; • X = {1, 2, ..., Y }, V Mx = {vm1x , vm2x , . . . , vm(M x)x }, ∀x ∈ X; Đầu ra : Một lịch trình S = {ti → vmjx , ti ∈ T, vmjx ∈ V Mx }; Phương pháp: 1 S := ∅; 2 foreach ti ∈ T do 3 si := T est(ti , X, V Mx ); 4 if si = ∅ then Thông báo cho người dùng yêu cầu đã bị từ chối ; 5 6 else S := S ∪ {si }; 7 8 return S; Function Test(ti ∈ T, X, V Mx ) 1 ST := ∅; 2 foreach con kiến thứ k do 3 foreach nhà cung cấp x ∈ X do Tính thông tin heuristic cho yêu cầu ti trên các máy ảo vmjx : 4 ηijx := 1 ; CPijx +CT Dijx +CIijx +CRijx 5 Tìm ra giá trị của mùi hiện tại: τijx ; 6 Tính thời gian thực hiện của ti trên các máy ảo vmjx như công thức (3.5): Cập nhật lại mùi: như công thức (3.18): τijx := (1 − ρ)τijx + 1−ρ ; F (ti ) 7 Tính xác suất để ti ánh xạ vào vmjx như công thức (3.20); 8 Dựa vào xác suất tính được để tìm ra máy ảo vmjx có xác suất lớn nhất và thỏa mãn các ràng buộc như công thức (3.10) và (3.11); if tìm thấy vmjx then 9 ST := ST ∪ {ti → vmjx } ; 10 11 if ti ∈ / ST then 12 return ∅; 13 14 else Tìm ra giải pháp có thể tối ưu nhất si bằng cách phân tích các con kiến trong danh sách lập lịch ST ; 15 return si 18