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ốngmáychủảo....................... 37
1.5. KẾTLUẬNCHƯƠ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 MVM-out-of-1PM 42
2.1.3. Mô hình cung cấp tài nguyên phân tán MVM-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ẾTLUẬNCHƯƠ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ÁYCHỦẢ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ầnnhấ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 MVM-out-of-1PM . . . . . . . 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 MVM-out-of-1PM ......... 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 MVM-out-of-NPM....... 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