Luận án tiến sĩ Kỹ thuật: Giải pháp phòng chống bế tắc trong cung cấp tài nguyên phân tán cho hệ thống máy chủ ảo không thuần nhất

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

Thêm vào BST

Báo xấu

56
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận án hướng tới nghiên cứu các giải pháp kỹ thuật phòng chống bế tắc trong cung cấp tài nguyên phân tán cho hệ thống máy chủ ảo một cách hiệu quả và hỗ trợ giải quyết sự cố bế tắc một cách nhanh chóng kịp thời. Luận án sử dụng mô hình cung cấp tài nguyên không thuần nhất dựa trên mô hình P-out-of-Q trong hệ phân tán.

Chủ đề:

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

Lưu

Nội dung Text: Luận án tiến sĩ Kỹ thuật: Giải pháp phòng chống bế tắc trong cung cấp tài nguyên phân tán cho hệ thống máy chủ ảo không thuần nhất

LỜI CAM ĐOAN Tác giả xin khẳng định tất cả các kết quả nghiên cứu được trình bày trong luận án là của riêng tác giả, không sao chép từ bất kỳ một công trình nào khác. Nếu có điều gì không trung thực, tác giả xin chịu hoàn toàn trách nhiệm. Tác giả Nguyễn Hà Huy Cường
MỤC LỤC DANH MỤC CÁC THUẬT NGỮ VÀ TỪ VIẾT TẮT ii DANH MỤC CÁC KÝ HIỆU iv DANH MỤC HÌNH ẢNH v DANH MỤC BẢNG vii MỞ ĐẦU 1 Chương 1. TỔNG QUAN VỀ PHÒNG CHỐNG BẾ TẮC TRONG CUNG CẤP TÀI NGUYÊN PHÂN TÁN CHO HỆ THỐNG MÁY CHỦ ẢO 8 1.1. HỆ THỐNG MÁY CHỦ ẢO VÀ NHỮNG ĐẶC TRƯNG CƠ BẢN 8 1.1.1. Khái niệm về hệ thống máy chủ ảo . . . . . . . . . . . . . 8 1.1.2. Các phương pháp cung cấp tài nguyên . . . . . . . . . . . 10 1.2. BẾ TẮC TRONG CUNG CẤP TÀI NGUYÊN . . . . . . . . . . . 23 1.3. GIẢI QUYẾT BẾ TẮC TRONG CUNG CẤP TÀI NGUYÊN CỦA HỆ ĐIỀU HÀNH VÀ HỆ PHÂN TÁN . . . . . . . . . . . . 25 1.3.1. Giải quyết bế tắc trong hệ điều hành . . . . . . . . . . . . 25 1.3.2. Giải quyết bế tắc trong hệ thống phân tán . . . . . . . . . 26 1.4. CÁC VẤN ĐỀ TỒN TẠI VÀ TIẾP CẬN CỦA LUẬN ÁN . . . . 33 1.4.1. Tiếp cận Heuristic . . . . . . . . . . . . . . . . . . . . . . 34 1.4.2. Tiếp cận Mô phỏng . . . . . . . . . . . . . . . . . . . . . . 35 1.4.3. Tiếp cận phân tích hiệu suất cung cấp tài nguyên cho hệ thống máy chủ ảo . . . . . . . . . . . . . . . . . . . . . . . 37 1.5. KẾT LUẬN CHƯƠNG . . . . . . . . . . . . . . . . . . . . . . . . 37
Chương 2. MÔ HÌNH CUNG CẤP TÀI NGUYÊN PHÂN TÁN GIẢI QUYẾT BẾ TẮC CHO HỆ THỐNG MÁY CHỦ ẢO KHÔNG THUẦN NHẤT 39 2.1. MÔ HÌNH CUNG CẤP TÀI NGUYÊN PHÂN TÁN . . . . . . . 39 2.1.1. Mô hình cung cấp tài nguyên P-out-of-Q . . . . . . . . . . 39 2.1.2. Mô hình cung cấp tài nguyên phân tán M VM-out-of-1PM 42 2.1.3. Mô hình cung cấp tài nguyên phân tán M VM-out-of-N PM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.2. MÔ HÌNH CUNG CẤP TÀI NGUYÊN CHO HỆ THỐNG MÁY CHỦ ẢO DỰA TRÊN NỀN TẢNG PHÂN TÁN KHÔNG THUẦN NHẤT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.3. CUNG CẤP TÀI NGUYÊN PHÂN TÁN . . . . . . . . . . . . . 51 2.3.1. Khái niệm chương trình phân tán . . . . . . . . . . . . . . 52 2.3.2. Khái niệm tiến trình thực thi phân tán . . . . . . . . . . . 52 2.3.3. Mô hình truyền thông phân tán . . . . . . . . . . . . . . . 54 2.3.4. Trạng thái toàn cục của hệ thống phân tán . . . . . . . . . 55 2.4. GIẢI PHÁP CUNG CẤP TÀI NGUYÊN TẠI LỚP HẠ TẦNG NỀN TẢNG PHÂN TÁN KHÔNG THUẦN NHẤT . . . . . . . . 57 2.4.1. Giải pháp cung cấp tài nguyên cho lớp hạ tầng dịch vụ IaaS 57 2.4.2. Phân tích kết quả mô phỏng . . . . . . . . . . . . . . . . . 61 2.5. GIẢI PHÁP CUNG CẤP TÀI NGUYÊN CHO MÁY CHỦ ẢO TẠI CÁC TRUNG TÂM DỮ LIỆU . . . . . . . . . . . . . . . . . 62 2.5.1. Giải pháp cung cấp tài nguyên tại các trung tâm dữ liệu . 62 2.5.2. Phân tích kết quả mô phỏng . . . . . . . . . . . . . . . . . 64 2.6. KẾT LUẬN CHƯƠNG . . . . . . . . . . . . . . . . . . . . . . . . 68 Chương 3. GIẢI PHÁP PHÒNG CHỐNG BẾ TẮC TRONG CUNG CẤP TÀI NGUYÊN PHÂN TÁN CHO HỆ THỐNG MÁY CHỦ ẢO KHÔNG THUẦN NHẤT 70
3.1. THUẬT TOÁN CẢI TIẾN SONG SONG PHÁT HIỆN BẾ TẮC TRONG CUNG CẤP TÀI NGUYÊN PHÂN TÁN CHO HỆ THỐNG MÁY CHỦ ẢO . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.1.1. Thuật toán cải tiến song song phát hiện bế tắc PDDA . . 71 3.1.2. Kiểm chứng thuật toán . . . . . . . . . . . . . . . . . . . . 73 3.1.3. Đánh giá độ phức tạp của thuật toán PDDA cải tiến . . . 75 3.1.4. Phân tích kết quả mô phỏng . . . . . . . . . . . . . . . . . 76 3.2. THUẬT TOÁN PHÁT HIỆN VÀ TRÁNH BẾ TẮC CHO HỆ THỐNG MÁY CHỦ ẢO PHÂN TÁN KHÔNG THUẦN NHẤT . 78 3.2.1. Phân tích bài toán . . . . . . . . . . . . . . . . . . . . . . 78 3.2.2. Đồ thị Wait – For – Graph (WFG) . . . . . . . . . . . . . 79 3.2.3. Thuật toán phát hiện bế tắc tìm kiếm hai chiều dựa trên đồ thị tranh chấp WFG . . . . . . . . . . . . . . . . . . . 80 3.2.4. Kiểm chứng thuật toán . . . . . . . . . . . . . . . . . . . . 82 3.2.5. Thuật toán 3.3 tránh bế tắc trong cung cấp tài nguyên trên nền tảng phân tán cho hệ thống máy chủ ảo không thuần nhất . . . . . . . . . . . . . . . . . . . . . . . . . . 83 3.2.6. Phân tích kết quả mô phỏng . . . . . . . . . . . . . . . . . 84 3.3. THUẬT TOÁN NGĂN CHẶN BẾ TẮC TRONG CUNG CẤP TÀI NGUYÊN CHO MÔ HÌNH M VM-out-of-1 PM . . . . . . . 86 3.3.1. Phân tích bài toán . . . . . . . . . . . . . . . . . . . . . . 86 3.3.2. Giải pháp kỹ thuật ngăn chặn bế tắc trong cung cấp tài nguyên theo mô hình M VM-out-of-1 PM . . . . . . . . . 87 3.3.3. Phân tích kết quả mô phỏng . . . . . . . . . . . . . . . . . 88 3.4. THUẬT TOÁN NGĂN CHẶN BẾ TẮC TRONG CUNG CẤP TÀI NGUYÊN CHO MÔ HÌNH M VM-out-of-N PM . . . . . . . 96 3.4.1. Phân tích bài toán . . . . . . . . . . . . . . . . . . . . . . 96 3.4.2. Thuật toán phát hiện và ngăn chặn bế tắc sử dụng kỹ thuật cung cấp tài nguyên phân nhóm . . . . . . . . . . . 99
i 3.4.3. Kiểm chứng thuật toán . . . . . . . . . . . . . . . . . . . . 100 3.4.4. Phân tích kết quả mô phỏng . . . . . . . . . . . . . . . . . 102 3.5. KẾT LUẬN CHƯƠNG . . . . . . . . . . . . . . . . . . . . . . . . 103 KẾT LUẬN 104 DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ 105 TÀI LIỆU THAM KHẢO 107
ii DANH MỤC CÁC THUẬT NGỮ VÀ TỪ VIẾT TẮT Ký hiệu Tiếng Anh Tiếng Việt ALS Adaptive List Scheduling Lập lịch theo danh sách thích nghi AMMS Adaptive Min-Min Scheduling Lập lịch Min-Min thích nghi BA Banker’s Algorithm Thuật toán Banker CP Core Processor Lõi vi xử lí CPU Central Processing Unit Bộ xử lí trung tâm CSP Cloud Service Providers Cung cấp dịch vụ đám mây COD Cluster-On-Demand Cụm máy tính theo yêu cầu DA Deadlock Avoidance Tránh bế tắc DC Data Center Trung tâm dữ liệu DD Deadlock Detection Phát hiện bế tắc DDU Deadlock Detection Unit Thành phần phát hiện bế tắc DP Deadlock Prevention Ngăn chặn bế tắc EC2 Elastic Computing Cloud Điện toán đám mây co giãn FIFO First In, First Out Cơ chế vào trước, ra trước FMS Flexible Manufacturing Systems Hệ thống sản xuất linh hoạt GA Genetic Algorithm Thuật toán di truyền HDD Hard Disk Drive Ổ đĩa cứng IGA Interactive Genetic Algorithm Thuật toán di truyền tương tác IaaS Infrastructure as a Service Hạ tầng như là dịch vụ IP Internet Protocol Giao thức Internet IO Input Output Ngõ vào ngõ ra IS Interger Scheduler Bộ lập lịch số nguyên ISP Internet Service Provider Nhà cung cấp dịch vụ Internet LSA List Scheduling Algorithm Thuật toán lập lịch theo danh sách PDDA Parallel Deadlock Detection Algorithm Thuật toán song song phát hiện bế tắc
iii PBA Parallel Banker’s Algorithm Thuật toán Banker song song PM Physical Machine Máy vật lý MDR Multicast Distributed Routing Định tuyến phân tán đa chiều MMSA Min-Min Scheduling Algorithm Thuật toán lập lịch Min-Min MIMO Multiple-input and Multiple-output Đa ngõ vào và đa ngõ ra NA Node Agent Nút tác tử RAM Random Access Memory Bộ nhớ truy xuất ngẫu nhiên RAG Resource Allocation Graph Đồ thị cung cấp tài nguyên RTTs Round Trip Times Thời gian trễ trọn vòng SLA Service Level Agreement Thỏa thuận cấp độ dịch vụ SLO Service Level Objective Mục tiêu cấp độ dịch vụ SMP Symmetric Multiprocessing Đa xử lý đối xứng VM Virtual Machine Máy ảo VMM Virtual Machine Monitor Giám sát máy ảo WFG Wait - For Graph Đồ thị tranh chấp
iv DANH MỤC CÁC KÝ HIỆU Ký hiệu Ý nghĩa G Nhóm người sử dụng D Trung tâm dữ liệu (Data Center) S Máy chủ ảo tại trung tâm dữ liệu Uβ Số lượng người sử dụng trong nhóm Ci Khả năng tài nguyên của trung tâm dữ liệu DCi Cp Khả năng yêu cầu tài nguyên tạo máy ảo tới trung tâm dữ liệu Rgi Hàm mục tiêu phụ thuộc giữa nhóm với trung tâm dữ liệu j(CP U ) xi Số lượng tài nguyên CPU yêu cầu để tạo máy chủ ảo V Si j(RAM ) xi Số lượng tài nguyên RAM yêu cầu để tạo máy chủ ảo V Si j(HDD) xi Số lượng tài nguyên HDD yêu cầu để tạo máy chủ ảo V Si CjCP U ,CjRAM ,CjHDD Khả năng tài nguyên tối đa CPU, RAM, HDD rjCP U ,rjRAM ,rjHDD Tài nguyên CPU, RAM, HDD cung cấp UIaaS Tài nguyên hiệu quả tại lớp hạ tầng dịch vụ cttg1 Trạng thái của tiến trình Pi với cttg1 ∈ {out, trying, in} ti Thời gian của tiến trình Pi khi vào miền găng li Thời gian logic của tiến trình Pi wfi Đánh dấu các tiến trình mà tiến trình Pi đang đợi được cấp phép pdi Đánh dấu thông điệp được cấp phép của tiến trình Pi bli Xác nhận True, False khi tiến trình Pi nhận thông điệp
v DANH MỤC HÌNH ẢNH 0.1 Thống kê của Hiệp hội ĐTĐM châu Á (CloudAsia) năm 2016. . . 1 1.1 Cấu trúc tổng quát hệ thống máy chủ ảo . . . . . . . . . . . . . . 10 1.2 Mô hình 5 lớp trong kiến trúc điện toán đám mây . . . . . . . . . 11 1.3 Ví dụ bế tắc trong cung cấp tài nguyên máy chủ ảo. . . . . . . . . 24 1.4 Tình huống cung cấp tài nguyên gặp bế tắc . . . . . . . . . . . . . 25 2.1 Đồ thị tranh chấp WFG trước và sau khi sử dụng thuật toán phát hiện bế tắc Kshemkalyani-Singhal [6]. . . . . . . . . . . . . . . . . 41 2.2 Mô hình cung cấp tài nguyên phân tán M -out-of-1PM. . . . . . . 42 2.3 Mô hình cung cấp tài nguyên phân tán M VM-out-of-N PM. . . 46 2.4 Mô hình hệ thống cung cấp tài nguyên phân tán không thuần nhất. 49 2.5 Đồ thị hệ thống cung cấp tài nguyên không thuần nhất. . . . . . . 50 2.6 Đồ thị miêu tả truyền thông điệp giữa ba tiến trình. . . . . . . . . 53 2.7 Đồ thị miêu tả việc trao đổi các thông điệp giữa các tiến trình. . . 57 2.8 Mạng cung cấp tài nguyên máy chủ ảo. . . . . . . . . . . . . . . . 63 2.9 Cung cấp tài nguyên máy chủ ảo tại trung tâm dữ liệu (a). . . . . 66 2.10 Cung cấp tài nguyên máy chủ ảo tại trung tâm dữ liệu (b). . . . . 67 3.1 Sơ đồ thuật toán cải tiến PDDA. . . . . . . . . . . . . . . . . . . 71 3.2 Đồ thị cung cấp tài nguyên (RAG). . . . . . . . . . . . . . . . . . 73 3.3 Bước giảm các phần tử của ma trận Cij khi duyệt theo hàng và cột lần thứ nhất. . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 3.4 Bước giảm các phần tử của ma trận Cij khi duyệt theo hàng và cột lần thứ ba. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 3.5 So sánh tối ưu thời gian của thuật toán PDDA và thuật toán PDDA cải tiến. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
vi 3.6 Ví dụ đồ thị hệ thống tranh chấp tài nguyên WFG đơn giản . . . 79 3.7 Sơ đồ thuật toán cải tiến Two - Way . . . . . . . . . . . . . . . . 80 3.8 Chu trình tìm được khi sử dụng thuật toán Two - Way. . . . . . . 83 3.9 So sánh hiệu quả khi áp dụng thuật toán cải tiến phát hiện bế tắc PDDA và Two - Way. . . . . . . . . . . . . . . . . . . . . . . . . 85 3.10 So sánh thời gian đáp ứng yêu cầu của thuật RRAA và thuật toán PDA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 3.11 Cung cấp tài nguyên nhiều (M) VM máy chủ ảo trên nhiều máy chủ vật lý (N) PM phân tán. . . . . . . . . . . . . . . . . . . . . . 97 3.12 Giải pháp lựa chọn theo nhóm dịch vụ. . . . . . . . . . . . . . . . 98 3.13 Tính toán phân loại nhóm sau khi phân tách theo nhóm phù hợp. . 102 3.14 Biểu đồ đánh giá thuật toán PDDA cải tiến và tối ưu theo nhóm người dùng so sánh theo thời gian đáp ứng yêu cầu. . . . . . . . . 102
vii DANH MỤC BẢNG 1.1 Bảng thống kê các thuật toán phát hiện bế tắc . . . . . . . . . . . 30 1.2 So sánh các thuật toán phát hiện bế tắc . . . . . . . . . . . . . . . 32 2.1 Bảng số liệu kết quả mô phỏng với yêu cầu tạo 7 máy chủ ảo. . . 60 2.2 Bảng số liệu kết quả mô phỏng với yêu cầu tạo 9 máy chủ ảo. . . 60 2.3 Bảng số liệu kết quả mô phỏng với yêu cầu tạo 10 máy chủ ảo. . . 61 2.4 So sánh các thuật toán phát hiện bế tắc dựa vào trạng thái toàn cục. 68 3.1 So sánh thuật toán PDDA và PDDA cải tiến . . . . . . . . . . . . 77 3.2 Bảng dữ liệu đầu ra sử dụng thuật toán tìm kiếm hai chiều Two - Way. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 3.3 Bảng số liệu đầu ra sử dụng thuật toán yêu cầu tài nguyên thuần nhất (RRAA) (9). . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 3.4 Bảng số liệu đầu ra sử dụng thuật toán yêu cầu tài nguyên không thuần nhất (RRAA) (9). . . . . . . . . . . . . . . . . . . . . . . . 92 3.5 Bảng số liệu đầu ra sử dụng thuật toán ngăn chặn bế tắc (PDA) (9). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 3.6 Bảng thông kê số liệu so sánh hiệu quả giữa hai thuật toán. . . . . 95 3.7 Thống kê dữ liệu sau khi gộp nhóm. . . . . . . . . . . . . . . . . . 101
1 MỞ ĐẦU 1. Tính cấp thiết của Luận án Vấn đề cung cấp tài nguyên trong các hệ thống tính toán phân tán quy mô lớn như tính toán lưới, tính toán đám mây đã được nghiên cứu vài thập kỷ gần đây [1] [2] [6] [54]. Trong năm 2016 [16], theo đánh giá của Hiệp hội Điện toán Đám mây châu Á (CloudAsia) vấn đề cung cấp tài nguyên, một dịch vụ quan trọng trong điện toán đám mây trở thành yêu cầu chủ yếu trong các ứng dụng khoa học công nghệ và công nghiệp. Trong bảng số liệu thống kê năm 2016 [16] chỉ số sẵn sàng về dịch vụ điện toán đám mây của Việt Nam đứng thứ 14 so với các nước trong châu Á. HongKong có bước nhảy vọt khi vượt qua Japan và xếp đầu bảng xếp hạng, tăng 4 điểm, trong khi đó Japan bị giảm đi 4 điểm. Hình 0.1 Thống kê của Hiệp hội ĐTĐM châu Á (CloudAsia) năm 2016. Có thể thấy các giải pháp cung cấp tài nguyên chủ yếu tập trung vào các kỹ thuật, đáp ứng yêu cầu của dịch vụ, ít chú trọng đến vấn đề độ tin cậy của kỹ thuật được đề xuất [10]. Trong các kịch bản cung cấp tài nguyên, hầu hết các dịch vụ cơ sở hạ tầng sử dụng các chính sách rất đơn giản như: giao ngay lập tức (immediately) hoặc
2 dựa trên các tiêu chí hiệu quả tốt nhất (best – effect) [10] [13] [14] [51]. Trong phương pháp cung cấp tài nguyên theo kiểu giao ngay lập tức, nếu hạ tầng dịch vụ có đủ tài nguyên thì cung cấp ngay, còn không thì thông báo từ chối. Phương pháp cung cấp tài nguyên dựa vào tiêu chí hiệu quả tốt nhất dựa vào các yêu cầu đặt trong hàng đợi, thông thường phục vụ theo cơ chế vào trước ra trước FIFO (First In, First Out). Có thể thấy rằng cho đến nay vẫn chưa có một phương pháp kỹ thuật cung cấp tài nguyên điện toán đám mây nào đáp ứng một cách đầy đủ các yêu cầu tài nguyên, do nguyên nhân nguồn tài nguyên tại một thời điểm thường hữu hạn. Ngoài ra, trong một số trường hợp, yêu cầu tài nguyên chỉ mang tính tạm thời. Ví dụ, một nhà khoa học có thể yêu cầu một số lượng lớn các máy tính để chạy chương trình mô phỏng chỉ trong vài giờ và sau đó không sử dụng đến nó nữa; một giảng viên đại học có thể cần một cụm các máy tính phục vụ cho sinh viên thí nghiệm, khoảng vài lần trong một tuần, với một cấu hình tài nguyên phần cứng nhất định. Ở trường hợp khác, công ty viễn thông cần một cơ sở hạ tầng để tiến hành cung cấp tài nguyên cho một số cụm tính toán dữ liệu theo yêu cầu, nhưng nhu cầu bổ sung tài nguyên cho lớp cơ sở hạ tầng hướng dịch vụ IaaS (Infrastructure as a Service) này không thể dự kiến được, vì còn phải phụ thuộc vào tình trạng truy cập yêu cầu sử dụng tài nguyên tính toán tại các trạm trong cụm. Điều này đòi hỏi các dịch vụ cơ sở hạ tầng cần có nguồn tài nguyên luôn luôn sẵn sàng phục vụ khi có yêu cầu. Những trường hợp yêu cầu sử dụng tài nguyên tạm thời ở trên làm nảy sinh vấn đề cần nghiên cứu các giải pháp cấp phát tài nguyên một cách hiệu quả. Trong các nghiên cứu trước đây, các phương pháp cung cấp tài nguyên thường chỉ áp dụng cho trường hợp sử dụng cụ thể. Khi đánh giá về mức độ hiệu quả của hệ thống cung cấp tài nguyên, các nghiên cứu chủ yếu dựa vào thời gian chờ trong hàng đợi, băng thông, tốc độ truy cập hay tổng thời gian của một tiến trình đợi trước khi thực thi. Hệ thống máy chủ ảo được tạo ra từ các trung tâm dữ liệu DC (Data Center ). Các trung tâm dữ liệu được thiết lập từ hàng trăm máy chủ vật lí (gọi là dịch vụ cơ sở hạ tầng). Tài nguyên vật lí của máy chủ thường là: bộ xử lí trung tâm
3 CPU (Central Processing Unit), bộ nhớ RAM (Random Access Memory), ổ đĩa cứng HDD (Hard Disk Drive), gọi là tài nguyên phần cứng. Ngoài ra, các nguồn tài nguyên khác cũng có thể được xem xét như các trình ứng dụng, các gói phần mềm và cơ sở dữ liệu, gọi tài nguyên mềm. Việc tạo lập các chính sách cung cấp tài nguyên, đáp ứng các yêu cầu tài nguyên từ phía người sử dụng phụ thuộc vào khả năng của các lõi vi xử lí CP (Core Proccessor ) và bộ xử lí trung tâm CPU của máy chủ vật lí. Tại các trung tâm dữ liệu, các máy chủ ảo được tạo ra trên cơ sở trừu tượng hóa tài nguyên của các máy chủ vật lí, cho phép triển khai dịch vụ ảo hóa. Tuy nhiên, để khắc phục vấn đề thiếu thốn tài nguyên, giảm độ trễ trên đám mây và khả năng cải thiện hiệu suất mạng, các máy chủ ảo (theo yêu cầu của các nhóm người sử dụng) phải được tạo ra ở trung tâm dữ liệu thích hợp. Các nghiên cứu [10] [13] [14], chỉ ra rằng sự chậm trễ trong cung cấp tài nguyên có thể làm cho lưu lượng biến động. Do vậy, trong trường hợp xấu nhất sẽ gây ra sự mất ổn định của môi trường điện toán đám mây. Thêm vào đó, sử dụng hệ thống máy chủ vật lí sẽ tốn kém chi phí về vận hành, không tiết kiệm điện năng, tăng chi phí về nhân sự quản lí hệ thống. Giá cả hợp lý khi cung cấp dịch vụ máy chủ ảo cho thấy xu hướng người sử dụng chuyển sang sử dụng hệ thống máy chủ ảo tăng lên nhanh chóng. Để thực hiện và đáp ứng được điều này, nhiều nghiên cứu đã đề xuất các cách tiếp cận khác nhau, nhằm phát triển của công nghệ ảo hóa như trong các nghiên cứu [10] [13] [14] [50] [51] [53] [54] [55]. Trong các nghiên cứu [14] [53] [54] [55], nhiều vấn đề khác nhau trong cung cấp tài nguyên ảo hóa được trình bày. Tuy nhiên, trong các nghiên cứu này mới chỉ trung chủ yếu vào cải tiến các thuật toán lập lịch, sử dụng các mô hình cung cấp tài nguyên đơn giản, chưa đề cập tới các vấn đề khác như: tương tranh và bế tắc trong cung cấp tài nguyên trong môi trường điện toán đám mây. Phòng chống bế tắc trong quá trình cung cấp tài nguyên được quan tâm nhiều trong hệ điều hành [25], hệ thống phân tán [6]. Trong môi trường điện toán đám mây, yêu cầu tài nguyên phục vụ cho các nhu cầu của khách hàng ngày một tăng. Khách hàng được phép chia sẻ các nguồn tài nguyên thông qua hạ tầng
4 dịch vụ, dưới sự giám sát điều khiển của phần mềm hypervisor. Mỗi khách hàng có cách thức hoạt động và độ ưu tiên sử dụng tài nguyên cụ thể. Tuy nhiên, các tiến trình trong môi trường phân tán thường không thuần nhất và hoạt động rất phức tạp, tương tranh nhau về nguồn tài nguyên. Đây chính là một trong những nguyên nhân trực tiếp làm cho hệ thống bị bế tắc. Bế tắc xảy ra khi một bộ phận tiến trình bị khóa cứng (blocking) đợi cung cấp nguồn tài nguyên chia sẻ, trong khi đó nguồn tài nguyên này đang được cung cấp cho tiến trình khác sử dụng. Vì vậy, yêu cầu sử dụng tài nguyên sẽ không bao giờ được phục vụ, dẫn đến phải đợi vô hạn. Có thể nói, vấn đề chồng chéo, xung đột, tương tranh tài nguyên phát sinh trong mọi hệ thống cung cấp tài nguyên, đặc biệt trong môi trường điện toán đám mây. Bế tắc trong cung cấp tài nguyên là một vấn đề cơ bản, thường xuyên được quan tâm nghiên cứu giải quyết: phòng chống bế tắc trong hệ điều hành, phát hiên bế tắc trong hệ phân tán. Bế tắc là một vấn đề khó khăn nhất trong thiết kế và duy trì hoạt động của máy chủ ảo. Giải quyết bế tắc sẽ giúp cung cấp tài nguyên một cách hiệu quả, không tốn thời gian quay vòng lặp, khả năng sẵn sàng và đảm bảo độ tin cậy của hệ thống. Vấn đề này có thể được giải quyết ở các cấp độ khác nhau trong hệ thống máy chủ ảo như: thiết kế, lập lịch, lập kế hoạch và kiểm soát. Luận án sẽ quan tâm đi sâu giải quyết các vấn đề: phát hiện, phòng chống bế tắc trong cung cấp tài nguyên phân tán cho hệ thống máy chủ ảo giai đoạn lập lịch và kiểm soát tiến trình cung cấp tài nguyên hạ tầng như một dịch vụ. 2. Mục tiêu nghiên cứu của Luận án Luận án hướng tới nghiên cứu các giải pháp kỹ thuật phòng chống bế tắc trong cung cấp tài nguyên phân tán cho hệ thống máy chủ ảo một cách hiệu quả và hỗ trợ giải quyết sự cố bế tắc một cách nhanh chóng kịp thời. Luận án sử dụng mô hình cung cấp tài nguyên không thuần nhất dựa trên mô hình P-out-of-Q trong hệ phân tán. - Đưa ra được khung lý thuyết tương đối hoàn chỉnh về cung cấp tài nguyên
5 phân tán cho hệ thống máy chủ ảo không thuần nhất. - Giải quyết bài toán phát hiện, phòng chống bế tắc trong cung cấp tài nguyên phân tán cho hệ thống máy chủ ảo không thuần nhất. 3. Đối tượng và phạm vi nghiên cứu của Luận án Đối tượng nghiên cứu: Nghiên cứu giải pháp kỹ thuật phòng chống bế tắc trong cung cấp tài nguyên phân tán cho hệ thống máy chủ ảo. Để giải quyết vấn đề luận án tiến hành nghiên cứu các mô hình cung cấp tài nguyên, từ đây quy về bài toán quy hoạch tuyến tính để làm giảm độ trễ gói dữ liệu trong cung cấp tài nguyên cho hệ thống máy chủ ảo phân tán không thuần nhất. Đối tượng được phân thành các vấn đề chính sau đây: - Kiểm soát máy ảo, bao gồm giám sát và ngăn chặn các sự cố, chẩn đoán sự cố và cứu hộ khẩn cấp máy chủ vật lí. - Đánh giá độ tin cậy, xác định khả năng sẵn sàng phục vụ trong cung cấp tài nguyên. - Phát hiện và phòng chống được các bế tắc trong cung cấp tài nguyên. Phạm vi nghiên cứu: 1. Nghiên cứu mô hình cung cấp tài nguyên đã được sử dụng trong cung cấp tài nguyên môi trường điện toán đám mây. 2. Xây dựng mô hình cung cấp tài nguyên tối ưu giải quyết được các vấn đề tranh chấp, bế tắc trong cung cấp tài nguyên cho hệ thống máy chủ ảo nền tảng không thuần nhất và nền tảng phân tán không thuần nhất. 3. Đề xuất thuật toán cải tiến phát hiện bế tắc và thuật toán ngăn chặn trong cung cấp tài nguyên cho hệ thống máy chủ ảo nền tảng phân tán không thuần nhất. 4. Phương pháp nghiên cứu
6 Phương pháp nghiên cứu chính của luận án là: - Phương pháp nghiên cứu là khảo sát, phân tích đánh giá các nghiên cứu đã có từ đó đề xuất cách tiếp cận giải quyết vấn đề. - Nghiên cứu các mô hình tối ưu cung cấp tài nguyên, từ mô hình cung cấp tài nguyên qui về bài toán qui hoạch tuyến tính để làm giảm độ trễ gói dữ liệu trong hệ thống máy chủ ảo. - Phương pháp giải quyết vấn đề dựa trên lý thuyết đồ thị, đồ thị cung cấp tài nguyên là đồ thị có hướng. - Kết quả đánh giá luận án dựa vào phương pháp mô phỏng trên phần mềm mã nguồn mở CloudSim, sử dụng ngôn ngữ Java để lập trình thuật toán. - Các kết quả được kiểm chứng và công bố trên các tạp chí, hội nghị có phản biện độc lập. 5. Ý nghĩa khoa học và thực tiễn của luận án Các kết quả nghiên cứu của luận án có ý nghĩa khoa học và thực tiễn được thể hiện như sau: - Luận án đang giải quyết vấn đề ngăn chặn bế tắc trong cung cấp tài nguyên phân tán cho hệ thống máy chủ ảo nền tảng không thuần nhất và nền tảng phân tán không thuần nhất đây là vấn đề đang rất thời sự, có ý nghĩa khoa học và thực tiễn. - Luận án đề xuất thuật toán cải tiến song song phát hiện bế tắc trong cung cấp tài nguyên máy chủ ảo phân tán không thuần nhất có giá trị khoa học và tính ứng dụng cao mang lại hiệu đáp ứng nhanh chóng cho người dùng và tiết kiệm được thời gian chi phí . - Luận án đề xuất thuật toán ngăn chặn bế tắc theo mô hình cung cấp tài nguyên M VM-out-of-1 PM và mô hình cung cấp tài nguyên M VM-out- of-N PM có tính khoa học và tính ứng dụng rất cao.
7 6. Cấu trúc luận án Luận án bao gồm: Phần mở đầu, nội dung gồm ba chương và phần kết luận. Chương 1: trình bày tổng quan về phòng chống bế tắc trong cung cấp tài nguyên phân tán cho hệ thống máy chủ ảo. Nội dung cụ thể của chương bao gồm: khái niệm hệ thống máy chủ ảo, tổng quan các công trình nghiên cứu ứng với các phương pháp cung cấp tài nguyên hiện nay, tóm tắt các hướng tiếp cận khác nhau cho việc nghiên cứu cung cấp tài nguyên. Tiếp đến, trình bày khái niệm và tính chất cơ bản của bế tắc, phát hiện bế tắc, phòng tránh bế tắc, ngăn chặn bế tắc trong hệ điều hành, hệ thống phân tán v.v... Cuối chương đưa ra đánh giá các công trình nghiên cứu và đề xuất hướng tiếp cận thực hiện của luận án. Chương 2: trình bày mô hình cung cấp tài nguyên phân tán giải quyết bài toán bế tắc trong hệ thống phân tán máy chủ ảo không thuần nhất. Dựa trên mô hình cung cấp tài nguyên tổng quát nhất trong hệ phân tán P-out-of-Q, luận án đưa ra mô hình cung cấp tài nguyên M VM-out-of-1 PM, mô hình M VM- out-of-N PM trong đó VM là máy ảo và PM là máy vật lí và mô hình cung cấp tài nguyên không thuần nhất. Trong chương, mô hình toán cung cấp tài nguyên tối ưu dựa trên tiếp cận tối ưu tài nguyên và thời gian tránh lặp vòng cũng được trình bày. Chương 3: trình bày đề xuất, thuật toán cải tiến song song phát hiện bế tắc (PDDA) trong cung cấp tài nguyên máy chủ ảo không thuần nhất, thuật toán ngăn chặn bế tắc trong các mô hình cung cấp tài nguyên đề xuất ở chương 2 và phân tích đánh giá kết quả mô phỏng. Các kết quả chính của luận án được báo cáo và thảo luận tại các hội nghị, hội thảo khoa học; được đánh số và tham chiếu theo quy cách (1) -> (9) (trang 105 tới 106). Trong đó kết quả công bố (5), (6), (7), (8) đã được đánh chỉ số theo Scopus và hai kết quả (5), (7) đã được cập nhật là các kỷ yếu (ISI ). Các tài liệu tham khảo của luận án được đánh số và tham chiếu theo quy cách [xyz] được nêu trong các trang 107 - 114.
8 Chương 1 TỔNG QUAN VỀ PHÒNG CHỐNG BẾ TẮC TRONG CUNG CẤP TÀI NGUYÊN PHÂN TÁN CHO HỆ THỐNG MÁY CHỦ ẢO 1.1. HỆ THỐNG MÁY CHỦ ẢO VÀ NHỮNG ĐẶC TRƯNG CƠ BẢN 1.1.1. Khái niệm về hệ thống máy chủ ảo Hệ thống tính toán phân tán đã có sự thay đổi từ mô hình máy tính lớn đến mô hình máy khách - chủ. Ngày nay, người sử dụng khai thác các ứng dụng của điện toán với tài nguyên tính toán hoặc dữ liệu được đặt trong môi trường đám mây. Dịch vụ cơ sở hạ tầng trong điện toán đám mây sẽ cung cấp tài nguyên máy chủ ảo, được thiết lập dựa trên các trung tâm dữ liệu DC. Trung tâm dữ liệu được xây dựng từ một hay nhiều máy chủ vật lý phân tán. Khi đó, mạng viễn thông giữ vai trò phương tiện trao đổi thông tin, là phương tiện chia sẻ tài nguyên, là môi trường để các chương trình truy cập dữ liệu từ xa và thông tin thông báo. Nhiệm vụ của mạng viễn thông là truyền thông tin nhanh, chính xác, có chất lượng. Xu hướng hiện nay xây dựng lớp dịch vụ hạ tầng có tính năng vượt trội và khả năng mở rộng linh hoạt, khả năng phục hồi an ninh và tránh tắc nghẽn mạng. Phương pháp cung cấp tài nguyên sử dụng công nghệ ảo hóa, cho phép tập hợp và khai thác các nguồn tài nguyên vật lí một cách linh hoạt. Máy chủ ảo, ngày càng trở nên phổ biến kể từ khi VMware GSX Server ra mắt [60]. Các máy chủ ảo được thiết lập thông qua lớp hạ tầng dịch vụ, dưới sự điều khiển của hypervisor. Hypervisor là phần mềm chịu trách nhiệm chạy nhiều máy ảo, thực hiện việc liên lạc trực tiếp với nền tảng phần cứng vật lí phía dưới, quản lý và cung cấp tài nguyên cho các máy ảo chạy các hệ điều hành khác nhau
9 nằm trên nó. Đối với các máy chủ ảo, được cung cấp tài nguyên từ máy chủ vật lí các thành phần tài nguyên ảo này phụ thuộc vào nhu cầu của người sử dụng. Máy chủ ảo hoạt động hoàn toàn giống như một máy chủ vật lí truyền thống, trong đó người sử dụng được toàn quyền quản trị máy chủ ảo với quyền quản trị cao nhất, đảm bảo tính bảo mật cao. Có thể dùng máy chủ ảo để thiết lập máy chủ Web, máy chủ Mail cũng như các máy chủ ứng dụng khác và có thể cài đặt riêng theo nhu cầu cũng như dễ dàng chia sẽ dữ liệu, truyền dữ liệu. Các nhà cung cấp dịch vụ ISP (Internet Service Provider ) sẽ cung cấp dịch vụ máy chủ ảo, quản lí không gian lưu trữ, duy trì hoạt động, tạo thêm hoặc loại bỏ bớt khách hàng khi sử dụng một máy chủ ảo, công ty hay cá nhân có thể quản lý các thư mục tập tin riêng của họ. Người sử dụng có thể bổ sung tên miền, không cần thông qua nhà cung cấp dịch vụ ISP, cũng như quản lý các bản ghi, phân tích thống kê và duy trì hoạt động, thay đổi mật khẩu. Ngoài ra, người sử dụng máy chủ ảo không cần quản lý các khía cạnh phần cứng của một máy chủ, tuy họ phải trả chi trả phí thuê dịch vụ và phí đường truyền Internet. Hệ thống máy chủ ảo trong môi trường điện toán đám mây ra đời dựa trên nền tảng của các hệ thống tính toán như: tính toán phân tán, tính toán song song và tính toán lưới. Ngoài cơ chế chia sẻ tài nguyên như hệ thống phân tán, máy chủ ảo cho phép đảm bảo độ bảo mật cho các máy chủ vật lí, tách biệt với các vùng ảo hóa khác nhau, chạy hệ điều hành riêng và hoạt động độc lập. Hệ thống tính toán này như là một sự kết hợp của công nghệ máy tính với dịch vụ phát triển trong môi trường truyền thông. Tập các máy chủ ảo có thể chạy trên một hoặc nhiều máy chủ vật lí, trên cơ sở chương trình hypervisor cung cấp chương trình dịch vụ chạy máy chủ ảo. Có thể nói cho đến hiện tại các nhà cung cấp dịch vụ của VMware hay Microsoft Virtual Server đã cung cấp giải pháp tin cậy và thông minh trong quản lý tài nguyên điện toán đám mây. Về cơ bản, điện toán đám mây được chia ra thành năm lớp riêng biệt, có tác động qua lại lẫn nhau: - Lớp máy chủ vật lý bao gồm: phần cứng, phần mềm và phần hypervisor, được thiết kế và xây dựng đặc biệt để cung cấp các dịch vụ của đám mây.