intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Tóm tắt Luận án tiến sĩ Khoa học Máy tính: 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

Chia sẻ: Tỉ Thành | Ngày: | Loại File: PDF | Số trang:27

Thêm vào BST
Báo xấu
28
lượt xem 2
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục đích cơ bản của luận án này là đề 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận án tiến sĩ Khoa học Máy tính: 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. ĐẠ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
  2. 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. Trường Đại học Sư phạm, Đại học Đà Nẵng. 2. PGS.TS. Nguyễn Mậu Hân. Trường Đại học Khoa học, Đại học Huế. Phản biện 1: PGS.TS. Trần Đình Quế, Học viện Công nghệ Bưu chính Viễn thông. Phản biện 2: PGS.TS. Hồ Sỹ Đàm, Đại học Hòa Bình, Hà Nội. Phản biện 3: TS. Hoàng Bảo Hùng. Trường Cao Đẳng Công nghệ Thông tin hữu nghị Việt Hàn, Đà Nẵng. 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: Trung tâm Thông tin - Thư viện trường Đại học Khoa học, Đại học Huế.
  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 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
  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 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
  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 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
  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 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
  7. 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
  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 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
  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 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) = (2.1) 0 nếu tại phút x, tài nguyên r không được sử dụng. 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: y M X X cj Scost (x) = × α(j, k, x) (2.2) j=1 k=1 D C Trong đó, M là số tài nguyên trong R, y = p với: N X C= 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: y M X X Scycle (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) x=ai di X Scycle (x) ≥ wi (2.8) 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 (2.9) 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
  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 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 (2.11)  ijx  d − (a + U )nếu a − a < wi và d − a < D  l i iljx l i sijx l i wi Trong đó: Uiljx = sijx + 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
  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 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 foreach thj ∈ T H do 3 foreach ti ∈ T do
  14. w i
  15. 4 Tính số lượng của tài nguyên đầu tiên r1 ∈ gj cho ti : sli :=
  17. ; (di − ai ) × s1
  18. 5 if wi > (di − ai ) × s1 và |gj | = 1 then 6 sli := sli + 1; 7 else 8 if wi > (di − ai ) × s1 then 9 Tính số lượng các tài nguyên còn lại của nhóm gj cho ti ; 10 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
  19. 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 ; /* tập các yêu cầu chưa lập lịch */ • Mảng Result ; /* 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 6 ti := P OP () ; /* Lấy ti từ ngăn xếp */  7 Tìm Ti := tl |dl ≥ di và al < di ; 8 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  l i il l i sijx l i 9 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 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; 10 if tìm thấy tl then 11 P U SH(tl ); U ST := U ST \ {tl }; 12 ST := ST ∪ {tl → Result [k, l]}; 13 else 14 Lặp lại bước 2 để tìm yêu cầu tiếp theo; 15 else 16 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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

TL.01: Bộ Tiểu Luận Triết Học
207 tài liệu
1474 lượt tải
THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2