Đăng ký Đăng nhập
Trang chủ 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...

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

.PDF
118
355
79

Mô tả:

ĐẠ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 LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH HUẾ - NĂM 2016 ĐẠ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 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 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu do tôi thực hiện, dưới sự hướng dẫn khoa học của PGS.TS. Lê Văn Sơn và PGS.TS. Nguyễn Mậu Hân. Các số liệu và kết quả trình bày trong luận án là trung thực, chưa được công bố bởi bất kỳ tác giả nào hay ở bất kỳ công trình nào khác. Nghiên cứu sinh Nguyễn Hoàng Hà i 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 LỜI CẢM ƠN Trong quá trình thực hiện đề tài “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”, Tôi đã nhận được rất nhiều sự giúp đỡ, tạo điều kiện của tập thể Ban Giám hiệu, Phòng Đào tạo Sau Đại học, Khoa Công nghệ Thông tin, giảng viên, cán bộ các phòng chức năng Trường Đại học Khoa học, Đại học Huế. Tôi xin bày tỏ lòng cảm ơn chân thành về sự giúp đỡ đó. Tôi xin bày tỏ lòng biết ơn sâu sắc tới PGS.TS. Lê Văn Sơn và PGS.TS. Nguyễn Mậu Hân là những thầy giáo trực tiếp hướng dẫn và chỉ bảo cho Tôi hoàn thành luận án này. Tôi xin chân thành cảm ơn bạn bè, đồng nghiệp của Tôi đang công tác tại Khoa Công nghệ Thông tin và gia đình đã động viên, khích lệ, tạo điều kiện và giúp đỡ Tôi trong suốt quá trình thực hiện và hoàn thành luận án này. TÁC GIẢ LUẬN ÁN Nghiên cứu sinh Nguyễn Hoàng Hà ii MỤC LỤC Lời cam đoan Lời cảm ơn Danh mục các từ viết tắt Danh mục các ký hiệu Danh mục bảng biểu Danh mục hình vẽ Mở đầu 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.2 Đặc điểm của tính toán đám mây . . . . . . . . . . . . . . . . . 1.1.3 Kiến trúc của tính toán đám mây . . . . . . . . . . . . . . . . . 1.1.4 Các mô hình trên tính toán đám mây . . . . . . . . . . . . . . . 1.1.5 Các thách thức trên tính toán đám mây . . . . . . . . . . . . . 1.2 Công cụ mô phỏng trên tính toán đám mây . . . . . . . . . . . . . . . 1.2.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.2 Một số công cụ mô phỏng trên tính toán đám mây . . . . . . . 1.2.3 Công cụ mô phỏng CloudSim . . . . . . . . . . . . . . . . . . . 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.2 Mô hình tổng quát để lập lịch trên các trung tâm dữ liệu . . . . 1.3.3 Sự khác nhau giữa lập lịch trên TTĐM so với các hệ thống khác 1.3.4 Các phương pháp lập lịch . . . . . . . . . . . . . . . . . . . . . 1.3.5 Mô hình kinh tế cho bài toán lập lịch . . . . . . . . . . . . . . . 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 . . . . . 1.4.1 Lập lịch tĩnh và động . . . . . . . . . . . . . . . . . . . . . . . . 1.4.2 Lập lịch heuristic . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.3 Lập lịch luồng công việc . . . . . . . . . . . . . . . . . . . . . . 1.4.4 Lập lịch công việc thời gian thực . . . . . . . . . . . . . . . . . 1.5 Mục tiêu và nội dung của luận án . . . . . . . . . . . . . . . . . . . . . 1.6 Tiểu kết Chương 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Mô hình các máy tham gia lập lịch . . . . . . . . . . . . . . . . 2.1.2 Mô hình công việc . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.3 Mô tả mục tiêu của bài toán . . . . . . . . . . . . . . . . . . . . iii i ii iv v vi vii 1 5 5 5 7 8 8 10 11 11 11 12 15 15 16 18 19 20 24 24 25 26 27 28 29 30 30 31 31 32 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 2.2 Mô hình lập lịch công việc thời gian thực . . . . . . . . . . . . . . . . . 2.2.1 Mô tả bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Mô hình toán học cho bài toán . . . . . . . . . . . . . . . . . . 2.2.3 Mục tiêu tối ưu về chi phí . . . . . . . . . . . . . . . . . . . . . 2.2.4 Mục tiêu tối ưu về thời gian . . . . . . . . . . . . . . . . . . . . 2.3 Mô hình tối ưu về kinh tế . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Thuật toán lập lịch trên 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 . . . . . . . . . . . . . . 2.4.1.1 Thuật toán CT O . . . . . . . . . . . . . . . . . . . . . 2.4.1.2 Thuật toán M IN C . . . . . . . . . . . . . . . . . . . . 2.4.1.3 Phân tích thuật toán CT O và M IN C . . . . . . . . . 2.4.1.4 Mô phỏng và đánh giá thuật toán . . . . . . . . . . . . 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 . . . . . . . . . . . . . . . . . . . . . 2.4.2.2 Mô phỏng và đánh giá thuật toán . . . . . . . . . . . 2.5 Tiểu kết Chương 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chương 3. Lập lịch công việc theo hướng tối ưu đa mục tiêu trong 32 33 35 37 37 37 39 39 40 43 45 46 50 51 53 56 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 . . . . . . . 3.1.1 Mô hình người dùng . . . . . . . . . . . . . . . . . . 3.1.2 Mô hình nhà cung cấp IaaS . . . . . . . . . . . . . . 3.1.3 Mô hình nhà cung cấp SaaS . . . . . . . . . . . . . . 3.1.4 Mô hình nhà cung cấp PaaS . . . . . . . . . . . . . . 3.2 Xây dựng bài toán theo hướng tối ưu đa mục tiêu . . . . . . 3.2.1 Tối ưu hóa đàn kiến (ACO) . . . . . . . . . . . . . . 3.2.2 Tối ưu hóa bầy đàn (P SO) . . . . . . . . . . . . . . 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 . . . . . . . . . . . . . . . . . . . 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 . . . . . . . . . . . . 3.3.2.2 Thuật toán M prof it . . . . . . . . . . . . 3.3.2.3 Phân tích thuật toán ACACO và M prof it 3.3.2.4 Mô phỏng và đánh giá thuật toán . . . . . 3.3.3 Thuật toán lập lịch tối ưu đa mục tiêu về thời gian . 3.3.3.1 Thuật toán ACT ACO . . . . . . . . . . . . 3.3.3.2 Áp dụng thuật toán M prof it . . . . . . . . 3.3.3.3 Mô phỏng và đánh giá thuật toán . . . . . . 3.4 Thuật toán lập lịch tối ưu đa mục tiêu dựa trên P SO . . . . 3.4.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . 3.4.2 Thuật toán tối ưu ACP SO . . . . . . . . . . . . . . 58 58 59 60 61 61 63 64 68 73 73 74 74 76 77 78 83 84 85 85 88 89 89 iv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 3.4.2.1 Thuật toán ACP SO . . . . . . . . . . . . . 3.4.2.2 Áp dụng thuật toán M prof it . . . . . . . . 3.4.2.3 Phân tích thuật toán ACP SO . . . . . . . 3.4.2.4 Mô phỏng và đánh giá thuật toán . . . . . . 3.5 Tiểu kết Chương 3 . . . . . . . . . . . . . . . . . . . . . . . Kết luận Danh mục các công trình khoa học của tác giả liên quan đến Tài liệu tham khảo v . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 91 91 92 95 97 luận án 99 100 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 DANH MỤC CÁC TỪ VIẾT TẮT Viết tắt Dạng đầy đủ Diễn giải ý nghĩa ACACO Admission Control by using ACO Kiểm soát đầu vào bằng cách sử dụng ACO ACO Ant Colony Optimization Tối ưu hóa đàn kiến ACPSO Admission Control by using PSO Kiểm soát đầu vào bằng cách sử dụng PSO API Application Programming Inter- Giao diện lập trình ứng dụng face CIS Cloud Information Services Các dịch vụ thông tin trên đám mây CTO Cost-Time Optimization Tối ưu về thời gian và chi phí EDF Earliest Deadline First Ưu tiên về thời hạn sớm nhất GA Genetic Algorithm Thuật toán di truyền GIS Geographical Information System Hệ thống thông tin địa lý IaaS Infrastructure as a Service Cơ sở hạ tầng như một dịch vụ MCT Minimum Completion Time Thời gian hoàn thành nhỏ nhất MET Minimum Execution Time Thời gian thực hiện nhỏ nhất MI Million Instructions Triệu chỉ thị MIPS Million Instructions Per Second Triệu chỉ thị trên một giây Mprofit Maximum Profit Lợi nhuận lớn nhất OLB Opportunistic Load Balancing Cân bằng tải cơ hội PaaS Platform as a Service Nền tảng như một dịch vụ PSO Particle Swarm Optimization Tối ưu hóa bầy đàn QoS Quality of Service Chất lượng dịch vụ SaaS Software as a Service Phần mềm như một dịch vụ SLA Service Level Agreement Thỏa thuận dịch vụ TCO Time-Cost Optimization Tối ưu về chi phí và thời gian TSP Travelling Salesman Problem Bài toán người du lịch VMs Virtual Machines Các máy ảo vi 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 DANH MỤC CÁC KÝ HIỆU Ký hiệu Diễn giải ý nghĩa R Tập tài nguyên T Tập các yêu cầu người dùng X Tập các nhà cung cấp tài nguyên trên IaaS γ Mục tiêu của bài toán Cmin Mục tiêu chi phí nhỏ nhất Tmin Mục tiêu thời gian thực hiện nhỏ nhất F Hàm cực tiểu η Thông tin heuristic τ Mùi để lại của các con kiến P Xác suất pos Vị trí của mỗi cá thể fcost (ti ) Hàm mục tiêu về chi phí cho yêu cầu ti ftime (ti ) Hàm mục tiêu về thời gian cho yêu cầu ti Fcost (pos) Hàm thích nghi về chi phí tại vị trí pos Ftime (pos) Hàm thích nghi về thời gian tại vị trí pos Scost (x) Hàm tính tổng chi phí tại phút thứ x Scycle (x) Hàm tính tổng chu kỳ thực hiện tại phút thứ x P best Vị trí tối ưu cục bộ Gbest Vị trí tối ưu toàn cục vmjx Máy ảo thứ j của nhà cung cấp x vii 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 DANH MỤC BẢNG BIỂU 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 Chi phí và tốc độ ban đầu của các tài nguyên . . . . . . . . . . . . . . Chi phí và tốc độ của các tài nguyên sau khi phân nhóm theo tốc độ . Chi phí và tốc độ của các tài nguyên sau khi sắp xếp theo chi phí . . . Mảng kết quả xác định số lượng tài nguyên cho mỗi yêu cầu của CT O Các thông số mô phỏng trên CloudSim . . . . . . . . . . . . . . . . . . Chi phí và tốc độ ban đầu của các tài nguyên . . . . . . . . . . . . . . Chi phí và tốc độ của các tài nguyên khi phân nhóm theo chi phí . . . Chi phí và tốc độ của các tài nguyên sau khi sắp xếp theo tốc độ . . . Mảng kết quả được đưa ra bởi thuật toán T CO . . . . . . . . . . . . . viii 41 41 41 43 47 52 52 52 53 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 DANH MỤC HÌNH VẼ 1.1 1.2 1.3 1.4 1.5 1.6 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14 3.15 3.16 3.17 3.18 3.19 3.20 Mối quan hệ giữa các hệ thống phân tán với TTĐM . . . . . . . . . . Kiến trúc của TTĐM . . . . . . . . . . . . . . . . . . . . . . . . . . . . Biểu đồ lớp trong CloudSim . . . . . . . . . . . . . . . . . . . . . . . . Mô hình lập lịch trên CloudSim . . . . . . . . . . . . . . . . . . . . . . Mô hình hệ thống để lập lịch trên TTĐM . . . . . . . . . . . . . . . . Các phương pháp lập lịch . . . . . . . . . . . . . . . . . . . . . . . . . Ánh xạ đồng thời t1 và t2 vào tài nguyên r1 và r3 . . . . . . . . . . . . Ánh xạ đồng thời t1 và t2 vào tài nguyên r1 và r2 . . . . . . . . . . . . So sánh tổng thời gian của 3 thuật toán khi thay đổi số yêu cầu . . . . So sánh tổng chi phí của 3 thuật toán khi thay đổi số yêu cầu . . . . . So sánh tổng thời gian thực hiện của 3 thuật toán khi thay đổi ρ . . . So sánh tổng chi phí của 3 thuật toán khi thay đổi ρ . . . . . . . . . . So sánh tổng chi phí của 3 thuật toán khi thay đổi số yêu cầu . . . . . So sánh tổng thời gian của 3 thuật toán khi thay đổi số yêu cầu . . . . So sánh tổng chi phí của 3 thuật toán khi thay đổi ρ . . . . . . . . . . So sánh tổng thời gian thực hiện của 3 thuật toán khi thay đổi ρ . . . Mô hình tổng quát của các thành phần trong TTĐM. . . . . . . . . . . Mô hình tổng quát của thuật toán ACO . . . . . . . . . . . . . . . . . Minh họa P SO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Thuật toán P SO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tổng chi phí của các thuật toán khi cố định số lượng yêu cầu . . . . . . Tổng số yêu cầu bị phạt của các thuật toán khi cố định số lượng yêu cầu Tổng yêu cầu bị phạt của các thuật toán khi thay đổi số lượng yêu cầu. Tổng chi phí của các thuật toán khi thay đổi số lượng yêu cầu. . . . . . Tổng chi phí của các thuật toán khi thay đổi số lượng máy ảo. . . . . . Tổng thời gian của các thuật toán khi thay đổi số lượng máy ảo. . . . . So sánh tổng thời gian của 4 thuật toán khi cố định số yêu cầu. . . . . So sánh tổng chi phí của 4 thuật toán khi cố định số yêu cầu. . . . . . So sánh tổng số yêu cầu bị phạt của 3 thuật toán khi cố định số yêu cầu. So sánh tổng thời gian của các thuật toán khi thay đổi số yêu cầu . . . Tổng chi phí của các thuật toán khi thay đổi số yêu cầu. . . . . . . . . So sánh tổng số yêu cầu bị phạt khi thay đổi số yêu cầu . . . . . . . . Tổng chi phí của các thuật toán khi cố định số yêu cầu. . . . . . . . . . Tổng lợi nhuận của các thuật toán khi cố định số yêu cầu. . . . . . . . Tổng chi phí của các thuật toán khi thay đổi số yêu cầu. . . . . . . . . Tổng lợi nhuận của các thuật toán khi thay đổi số yêu cầu. . . . . . . . ix 6 8 13 15 17 20 35 35 48 48 50 50 54 54 55 56 59 65 69 70 80 81 81 82 82 83 86 86 87 88 88 89 93 93 94 95 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 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ế, các tổ chức, cơ quan và doanh nghiệp đều đối mặt với những thử thách như sau: (1) Khối lượng dữ liệu xử lý lớn, như các công ty lưu trữ thông tin địa lý (GIS), thông tin về biến đổi khí hậu trên một khu vực, các công ty tài chính, chứng khoán, v.v.; (2) Tính toán nhiều (computation intensive), như các công ty phân tích về thị trường, phân tích về không gian, phân tích mạng cần thời gian tính toán nhanh, v.v.; (3) Chi phí trang bị phần mềm cao, nhất là đối với các cá nhân và tổ chức nhỏ mong muốn phát triển bằng các công nghệ phần mềm thương mại mới. Do đó, các tổ chức này cần tìm ra các giải pháp mới có 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 như mua thêm máy chủ, máy trạm, siêu máy tính, các phần mềm cài trên các thiết bị, v.v.. Rõ ràng cách này cần đầu tư một chi phí lớn và tốn nhiều nguồn nhân lực để điều hành các hệ thống này. • 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 xem phần cứng, phần mềm như là các dịch vụ, thông qua Internet người dùng có thể chia sẻ tài nguyên (đám mây cộng đồng) hoặc thuê tài nguyên thông qua các dịch vụ và trả tiền khi sử dụng (đám mây công cộng). Việc sử dụng dịch vụ của TTĐM giống như dùng dịch vụ của lưới điện, người dùng cứ cắm điện vào dùng và trả tiền theo số KW tiêu thụ. Chính các công nghệ mạng và truyền thông phát triển mạnh mẽ trong những năm qua đã giúp cho việc sử dụng dịch vụ trên TTĐM dần trở thành hiện thực. 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 có 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 1 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 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, giảm thiểu thời gian hoạt độ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ế. Mục tiêu của hướng này 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ố vấ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 TTĐM là môi trường có qui mô hoạt động rất lớn, 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 SaaS, nhà cung cấp PaaS và nhà cung cấp IaaS, mỗi tác nhân có các chức năng và nhiệm vụ khác nhau. 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. Luận án tập trung nghiên cứu mô hình của nhà cung cấp 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 Chúng tôi tập trung tiếp cận trên một số phương pháp chính: • Phương pháp tổng hợp và mô hình hóa: tìm kiếm, thu thập tài liệu 2 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 về các công trình nghiên cứu đã được công bố, các bài báo đăng ở các hội thảo và tạp chí lớn để xây dựng mô hình toán học cho các thành phần trên TTĐM. • Phương pháp hệ thống hóa: dựa trên mô hình toán học của các thành phần trên TTĐM và các ràng buộc của người dùng để xây dựng bài toán. Từ đó, đề xuất các thuật toán lập lịch công việc thời gian thực và các thuật toán tối ưu đa mục tiêu nhằm thỏa mãn mục tiêu cụ thể của người dùng và nhà cung cấp dịch vụ. • Phương pháp thực nghiệm khoa học: sử dụng công cụ CloudSim để cài đặt mô phỏng, phân tích và đánh giá các thuật toán đề xuất với các thuật toán đã công bố. 4. Ý nghĩa khoa học và thực tiễn Ý nghĩa khoa học Những đóng góp chính của luận án về 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 các sinh viên đại học 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 3 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 Ngoài phần mở đầu và kết luận, luận án được chia thành 3 chương: • Chương 1: tổng quan về các vấn đề lập lịch trên tính toán đám mây. Trình bày tổng quan về các vấn đề liên quan mật thiết đến luận án như tổng quan về TTĐM, các công cụ mô phỏng, phân tích và đánh giá các công trình nghiên cứu về bài toán lập lịch cũng như các loại lập lịch trên TTĐM. Từ đó, xác định mục tiêu và nội dung nghiên cứu của luận án. • Chương 2: lập lịch công việc thời gian thực trong tính toán đám mây. Chương này tập trung xây dựng mô hình cho 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. Sau đó, xây dựng các thuật toán lập lịch công việc thời gian thực và sử dụng công cụ mô phỏng CloudSim để cài đặt, phân tích và so sánh với các thuật toán lập lịch EDF hiện có. • 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. Chương này xây dựng mô hình và bài toán lập lịch công việc việc theo hướng tối ưu đa mục tiêu. Sau đó, xây dựng các thuật toán lập lịch và sử dụng công cụ mô phỏng CloudSim để cài đặt, phân tích và so sánh với các thuật toán lập lịch khác. Các kết quả của luận án được công bố trong 8 công trình khoa học được đăng trong các hội nghị và tạp chí chuyên ngành trong và ngoài nước. Trong đó có 02 bài đăng trong kỷ yếu hội thảo quốc gia, 01 bài đăng ở hội thảo quốc tế, 02 bài đăng ở tập chí Khoa học và Công nghệ, 03 bài đăng ở các tạp chí chuyên ngành. 4 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 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 Tính toán đám mây (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 [50]. Tùy theo mục đích sử dụng mà hiện nay có nhiều định nghĩa khác nhau về TTĐM. Đứng về khía cạnh người dùng: “TTĐM là môi trường tính toán dựa trên Internet mà ở đó tất cả phần cứng, phần mềm, dữ liệu (gọi chung là tài nguyên) được cung cấp cho người dùng theo nhu cầu (tương tự như mạng điện).” Đứng về khía cạnh khoa học kỹ thuật, Rajkumar Buyya và Ian Foster định nghĩa TTĐM như sau: • Theo Rajkumar Buyya: “TTĐM là một loại hệ thống phân tán và xử lý song song gồm các máy tính ảo kết nối với nhau và được cung cấp động cho người dùng như một hoặc nhiều tài nguyên đồng nhất dựa trên sự thỏa thuận dịch vụ giữa nhà cung cấp và người sử dụng.” • Theo Ian Foster: “TTĐM là một mô hình tính toán phân tán có tính co giãn lớn mà theo hướng co giãn về mặt kinh tế, là nơi chứa các sức mạnh tính toán, kho lưu trữ, các nền tảng và các dịch vụ được trực quan, ảo hóa và co giãn linh động, sẽ được phân phối theo nhu cầu cho các khách hàng bên ngoài thông qua Internet.” Cả hai định nghĩa của Rajkumar Buyya và Ian 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. TTĐM khác với mô hình truyền thống ở một số điểm: • Khả năng mở rộng rất lớn. 5 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 • Nó được phát triển trên mô hình kinh tế. • Các dịch vụ có thể được cấu hình một cách tự động (thông qua ảo hóa hoặc phương pháp khác) và phân phối các dịch vụ theo yêu cầu của người dùng. Về lịch sử phát triển, TTĐM phát triển từ tính toán lưới kết hợp với Web 2.0 như thể hiện ở Hình 1.1. Vào thập niên 60, siêu máy tính bắt đầu xuất hiện và phát triển rất nhanh chóng. Khi mạng bắt đầu phát triển và để tiết kiệm chi phí, tăng khả năng tính toán người ta nối các máy tính lại với nhau và tạo ra các cụm máy tính. Cụm máy tính thương mại đầu tiên ra đời năm 1977 có tên là ARC. Cho đến những năm 1990, Ian Foster và Carl Kesselman mới đưa ra khái niệm tính toán lưới. Tính toán lưới phát triển mạnh nhất từ năm 2001 đến 2008, trong khoảng thời gian này các dự án lớn ra đời và áp dụng rất rộng rãi ngoài thực tế như TeraGrid(2001), Gid5000(2003), EGEE(2004), BeinGRID(2006),v.v. Hình 1.1: Mối quan hệ giữa các hệ thống phân tán với TTĐM Thuật ngữ TTĐM ra đời giữa những năm 2007 không phải để nói về một trào lưu mới, mà để khái quát lại các hướng đi của cơ sở hạ tầng thông tin vốn đã và đang diễn ra từ nhiều thập kỷ qua. Ian Foster cho rằng việc sử dụng TTĐM giống như mạng lưới điện, nơi người dùng có thể cắm vào lưới điện, sử dụng dịch vụ và trả tiền theo KW 6 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 số tiêu thụ. Salesfore là công ty đầu tiên phát triển ứng dụng trên môi trường TTĐM. Sau đó, cùng với sự phát triển mạnh mẻ của Web 2.0, ngày nay có rất nhiều công ty phát triển ứng dụng trên môi trường này như Amazon (2006), IBM Blue Cloud (2007), Google App Engine (2008), Sun Open Cloud (2009), Hp Service Automation (2010), Open Networking Foundation (2011), v.v. 1.1.2. Đặc điểm của tính toán đám mây Các dịch vụ cung cấp trên TTĐM có những đặc điểm chung như sau [1], [12]: • Giá rẻ: cơ sở hạ tầng được cung cấp bởi các nhà cung cấp trên TTĐM. Vì vậy, các doanh nghiệp không cần đầu tư, xây dựng cơ sở hạ tầng, thay vào đó họ chỉ cần thuê tài nguyên trên các trung tâm dữ liệu. • Khả năng co giãn: khả năng này cho phép tự động mở rộng hoặc thu nhỏ hệ thống tùy theo nhu cầu của người dùng. Khi nhu cầu tăng, hệ thống sẽ tự động mở rộng bằng cách thêm tài nguyên vào. Khi nhu cầu giảm, hệ thống sẽ tự động giảm bớt tài nguyên. Khả năng co giãn giúp cho nhà cung cấp sử dụng tài nguyên một cách hiệu quả, tận dụng triệt để tài nguyên dư thừa và phục vụ được nhiều khách hàng. Đối với người sử dụng dịch vụ, khả năng co giãn giúp họ giảm chi phí vì họ chỉ trả phí cho những tài nguyên thực sự dùng. • Độ tin cậy: số lượng tài nguyên trên các trung tâm dữ liệu là rất lớn. Vì vậy, đảm bảo tính liên tục trong kinh doanh và khôi phục dữ liệu khi gặp thất bại. • Dùng chung tài nguyên và độc lập vị trí: tài nguyên của nhà cung cấp dịch vụ được dùng chung, phục vụ cho nhiều người dùng. Người sử dụng không cần quan tâm tới việc cài đặt hoặc không cần phải biết chính xác vị trí của các tài nguyên sẽ được cung cấp. • Ảo hóa: nhờ có công nghệ ảo hóa mà có nhiều nguồn tài nguyên có thể kết hợp và cung cấp cho người dùng. Người dùng có thể xây dựng một ứng dụng mới trong vài phút thay vì vài ngày hay vài tuần. Người dùng truy cập vào các nguồn tài nguyên thông qua cổng thông tin và đưa vào sử dụng ngay lập tức. • Truy cập diện rộng: TTĐM cung cấp các dịch vụ chạy trên môi trường Internet, vì vậy khách hàng chỉ cần kết nối được với Internet là có thể sử dụng được các dịch vụ. • Dùng bao nhiêu trả bấy nhiêu: người dùng có thể sử dụng dịch vụ theo yêu cầu và trả phí khi sử dụng. Người dùng có thể hủy dịch vụ khi cần. 7 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 • Độc lập thiết bị: người sử dụng có thể sử dụng các dịch vụ bằng nhiều loại thiết bị khác nhau như: laptop, smartphone, tablet, v.v. với điều kiện là các thiết bị kết nối được mạng Internet. • Nhiều người thuê: tài nguyên trong hệ thống có thể được chia sẻ để nhiều người sử dụng. Tại một thời điểm sẽ có nhiều người sử dụng tài nguyên một cách đồng thời và nhà cung cấp sẽ được lợi về mức đầu tư hệ thống còn người sử dụng sẽ được thừa hưởng những hạ tầng tính toán hiệu năng cao. 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 [25] chia thành 4 tầng như Hình 1.2. Hình 1.2: Kiến trúc của TTĐM • Tầng tác chế (Fabric): bao gồm các tài nguyên phần cứng như các tài nguyên tính toán, tài nguyên lưu trữ và tài nguyên mạng. • Tầng tài nguyên hợp nhất (Unified Resource Layer): bao gồm các tài nguyên được ảo hóa để có thể giao tiếp với tầng tác chế và người dùng cuối như các tài nguyên hợp nhất. Ví dụ như các máy ảo, các cụm ảo, v.v.. • Tầng nền tảng (Platform Layer): cung cấp các thông tin tài nguyên, các công cụ chuyên dụng, các middleware và các dịch vụ để xây dựng, phát triển hay triển khai một ứng dụng của người dùng. Ví dụ như dịch vụ lập lịch, dịch vụ Web hosting, v.v.. • Tầng ứng dụng (Application Layer): chứa các ứng dụng có thể chạy trên TTĐM. Nó cung cấp các tài nguyên phần mềm khi người dùng có yêu cầu. 1.1.4. Các mô hình trên tính toán đám mây Theo NIST [58], TTĐM bao gồm 3 mô hình dịch vụ và 4 mô hình triển khai. Ba mô hình dịch vụ bao gồm: 8 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 • SaaS (Software as a Service): là mô hình cung cấp phần mềm, trong đó các ứng dụng được truy cập bởi một giao diện đơn giản, chẳng hạn như một trình duyệt web trên Internet. Người sử dụng không quan tâm đến cơ sở hạ tầng trên TTĐM như mạng, máy chủ, hệ thống điều hành, lưu trữ, nền tảng, v.v.. • PaaS (Platform as a Service): là mô hình cung cấp một môi trường tích hợp ở mức cao để xây dựng, kiểm tra, triển khai và tạo máy chủ cho khách hàng. • IaaS (Infrastructure as a Service): là mô hình cung cấp khả năng xử lý, lưu trữ, mạng và các tài nguyên tính toán cơ bản khác cho người dùng. Người sử dụng IaaS có thể triển khai ứng dụng, phần mềm, hệ điều hành trên cơ sở hạ tầng một cách tùy ý. Các cơ sở hạ tầng trên TTĐM được ảo hóa một cách linh hoạt để đáp ứng yêu cầu của người dùng. TTĐM được triển khai trên các mô hình khác nhau, tùy thuộc vào phạm vi sử dụng của các tổ chức. Hiện nay, có 4 mô hình triển khai chính trên TTĐM như sau: • Đám mây công cộng (Public Cloud): cơ sở hạ tầng của TTĐM được một tổ chức sỡ hữu và cung cấp dịch vụ rộng rãi cho tất cả các khách hàng thông qua hạ tầng mạng Internet hoặc các mạng công cộng diện rộng. Các ứng dụng khác nhau chia sẻ chung tài nguyên tính toán, mạng và lưu trữ. Do vậy, cơ sở hạ tầng được thiết kế để đảm bảo cô lập về dữ liệu giữa các khách hàng và tách biệt về truy cập. • Đám mây riêng (Private Cloud): cơ sở hạ tầng của TTĐM được sở hữu bởi một tổ chức và phục vụ cho người dùng của tổ chức đó. Đám mây riêng có thể được vận hành bởi một bên thứ ba và hạ tầng đám mây có thể được đặt bên trong hoặc bên ngoài tổ chức sở hữu. Với mô hình đám mây riêng, các doanh nghiệp có thể tối ưu được cơ sở hạ tầng của mình, nâng cao hiệu quả sử dụng và trực tiếp quản lý việc cấp phát hoặc thu hồi tài nguyên. • Đám mây cộng đồng (Community Cloud): cơ sở hạ tầng đám mây được chia sẻ bởi một số tổ chức cho cộng đồng người dùng. Các tổ chức này chia sẻ chung một hạ tầng TTĐM để nâng cao hiệu quả đầu tư và sử dụng. • Đám mây lai (Hybrid Cloud): là mô hình kết hợp với đám mây công cộng và đám mây riêng. Mô hình đám mây lai cho phép chia sẻ cơ sở hạ tầng hoặc đáp ứng nhu cầu trao đổi dữ liệu. 9
- Xem thêm -

Tài liệu liên quan