LỜI CAM ĐOAN Tác giả xin khẳng định tất kết nghiên cứu trình bày luận án riêng tác giả, không chép từ công trình khác Nếu có điều 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 DANH MỤC BẢNG MỞ ĐẦU v vii Chương 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 hệ thống máy chủ ảo 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 bế tắc hệ điều hành 25 1.3.2 Giải bế tắc 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ô 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 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 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 mô 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 trung tâm liệu 62 2.5.2 Phân tích kết mô 64 2.6 KẾT LUẬN CHƯƠNG 68 Chương 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 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 thuật toán PDDA cải tiến 75 3.1.4 Phân tích kết mô 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 toán 78 3.2.2 Đồ thị Wait – For – Graph (WFG) 79 3.2.3 Thuật toán phát bế tắc tìm kiếm hai chiều dựa đồ 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 cung cấp tài nguyên tảng phân tán cho hệ thống máy chủ ảo không 83 3.2.6 Phân tích kết mô 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 toán 86 3.3.2 Giải pháp kỹ thuật ngăn chặn bế tắc 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 mô 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 toán 96 3.4.2 Thuật toán phát 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 mô 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 liệu DD Deadlock Detection Phát bế tắc DDU Deadlock Detection Unit Thành phần phát 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, 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 dịch vụ IP Internet Protocol Giao thức Internet IO Input Output Ngõ vào ngõ 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 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 đa ngõ 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 liệu (Data Center) S Máy chủ ảo trung tâm liệu Uβ Số lượng người sử dụng nhóm Ci Khả tài nguyên trung tâm liệu DCi Cp Khả yêu cầu tài nguyên tạo máy ảo tới trung tâm liệu Rgi Hàm mục tiêu phụ thuộc nhóm với trung tâm liệu j(CP U ) Số lượng tài nguyên CPU yêu cầu để tạo máy chủ ảo V Si j(RAM ) Số lượng tài nguyên RAM yêu cầu để tạo máy chủ ảo V Si xi j(HDD) 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ả 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 lớp hạ tầng dịch vụ cttg1 Trạng thái tiến trình Pi với cttg1 ∈ {out, trying, in} ti Thời gian tiến trình Pi vào miền găng li Thời gian logic tiến trình Pi wfi Đánh dấu tiến trình mà tiến trình Pi đợi cấp phép pdi Đánh dấu thông điệp cấp phép tiến trình Pi bli Xác nhận True, False tiến trình Pi nhận thông điệp xi xi v DANH MỤC HÌNH ẢNH 0.1 Thống kê Hiệp hội ĐTĐM châu Á (CloudAsia) năm 2016 1.1 Cấu trúc tổng quát hệ thống máy chủ ảo 10 1.2 Mô hình lớp kiến trúc điện toán đám mây 11 1.3 Ví dụ bế tắc cung cấp tài nguyên máy chủ ảo 24 1.4 Tình cung cấp tài nguyên gặp bế tắc 25 2.1 Đồ thị tranh chấp WFG trước sau sử dụng thuật toán phát 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 49 2.5 Đồ thị hệ thống cung cấp tài nguyên không 50 2.6 Đồ thị miêu tả truyền thông điệp ba tiến trình 53 2.7 Đồ thị miêu tả việc trao đổi thông điệp 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 trung tâm liệu (a) 66 2.10 Cung cấp tài nguyên máy chủ ảo trung tâm 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 phần tử ma trận Cij duyệt theo hàng cột lần thứ 3.4 74 Bước giảm phần tử ma trận Cij duyệt theo hàng cột lần thứ ba 74 3.5 So sánh tối ưu thời gian thuật toán PDDA 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 sử dụng thuật toán Two - Way 83 3.9 So sánh hiệu áp dụng thuật toán cải tiến phát bế tắc PDDA Two - Way 85 3.10 So sánh thời gian đáp ứng yêu cầu thuật RRAA thuật toán PDA 96 3.11 Cung cấp tài nguyên nhiều (M) VM máy chủ ảo 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 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 tối ưu theo nhóm người dùng so sánh theo thời gian đáp ứng yêu cầu 102 100 clocki ← max(clocki ,n); prioi ← (csstatei = in)∨ ((csstatei = trying)∧ ((lrdi , i) < (n, j))); Nếu (ni = NPM) gửi NOTUSED(NPM) tới pi Ngược lại (ni = NPM) gửi NOTUSED(NPM - ni ) cho pj permdelayedi ← permdelayedi ∪ j kết thúc kiểm tra } Khi nhận thông điệp cho phép (i,j) từ pj thực hiện: { N P Mi ← N P Mi \ j; Khi thông điệp NOTUSED(x) nhận từ tiến trình pi thực usedbyi [j]← usedbyi [j]−x; Kiểm tra điều kiện nếu((csstatei = trying)∧(usedbyi [j] = 0)∧(notsenttoi [j]) Thì gửi yêu cầu REQUEST(lrdi ,i) tới pj senttoi [j] ← true; usedbyi [j] ← NPM; Kết thúc kiểm tra điều kiện } } 3.4.3 Kiểm chứng thuật toán Mỗi lần lặp thuật toán cho phép giảm kích thước ma trận Do đó, phải max(m,n) bước lặp để phát bế tắc Các yêu cầu cung cấp dịch vụ điện toán đám mây mô tả thông qua thẻ dịch vụ điện toán đám mây (t) đầu vào cho phân cụm (cluster) Thẻ dịch vụ đám mây tương ứng với vector (uk ) hàm mục tiêu công thức (3.1) Giá trị cv tâm cụm dịch vụ điện toán đám mây, tính toán khoảng cách Euclide, công thức (3.1) Trong thực nghiệm liệu mẫu yêu cầu dịch vụ điện toán đám mây ghép thành nhóm Bảng 3.7 biểu thị giá trị thuộc tính yêu cầu cung cấp dịch vụ điện toán đám mây Hình 3.12 có thẻ thuộc tính từ T1 đến T10 101 Bảng 3.7 Thống kê liệu sau gộp nhóm Thuộc tính Task CSP 10 1 1 1 0 1 1 0 0 1 1 0 1 0 0 0 2 1 0 0 0 1 0 0 0 2 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 ID Ví dụ: Tính toán thuộc tính nhóm |1-1|+ |1-1|+|1-1|+|1-1|+|1-1|+|2-1|+|0-1|+|0-0|+|1-0|+|0-0|=4 |1-0|+|1-0|+|1-0|+|1-0|+|1-0|+|2-0|+|0-0|+|0-1|+|1-1|+|0-1|=14 |1-0|+|1-0|+|1-0|+|1-0|+|1-0|+|2-0|+|0-0|+|0-0|+|0-0|+|1-0|=13 Rút gọn giá trị nhóm tính số (J)=8.6 Đây nhóm tối ưu Phân loại nhóm theo giá trị sau: Group1: 1,2,3,7 Group2: 8,9,10 Group3: 4,5,6 Các giá trị tài nguyên yêu cầu tương ứng với vecter uk hàm mục tiêu công thức (3.1) Giá trị trung tâm cvi điều chỉnh, có thay đổi thành viên nhóm Quá trình phân cụm dựa vào hàm mục tiêu J dẫn tới trạng thái hội tụ Sau phân nhóm, nhà cung cấp dịch vụ điện toán đám mây giao cho nhóm cụ thể trường hợp A, B, C Dựa đó, nhà cung cấp dịch vụ điện toán đám mây thiết lập nhóm ảo, theo dịch vụ nhóm đáp ứng yêu cầu cung cấp dịch vụ điện toán đám mây 102 Hình 3.13 Tính toán phân loại nhóm sau phân tách theo nhóm phù hợp 3.4.4 Phân tích kết mô Dựa kết trình bày phần 3.4.3, thực nghiệm phương pháp cung cấp tài nguyên dựa vào phân nhóm tối ưu theo người dùng cải tiến thuật toán PDDA cài đặt CloudSim [18] [44] [61] Việc áp dụng tối ưu theo phân nhóm người dùng thuật toán phát tốt so với thuật toán cung cấp tài nguyên có trước Do kết luận tính đắn hiệu Hình 3.14 Biểu đồ đánh giá thuật toán PDDA cải tiến tối ưu theo nhóm người dùng so sánh theo thời gian đáp ứng yêu cầu 103 3.5 KẾT LUẬN CHƯƠNG Trong chương này, luận án trình bày thuật toán cải tiến PDDA, thuật toán cải tiến Two - Way thuật toán cung cấp tài nguyên tối ưu theo nhóm người dùng Để có sách hiệu cung cấp tài nguyên phân tán cho hệ thống máy chủ ảo, việc sử dụng phương pháp áp dụng thuật toán phát bế tắc hướng tiếp cận lập lịch lại cung cấp tài nguyên cho hệ thống máy chủ ảo điện toán đám mây cho phép nâng cao thời gian đáp ứng yêu cầu cung cấp tài nguyên ảo hóa tránh cố xung đột Thông qua kết đạt thực nghiệm thấy tính hiệu với hướng tiếp cận nghiên cứu đề xuất thuật toán phát tài nguyên bế tắc hệ thống máy chủ ảo phân tán không Với giải pháp này, làm tăng độ tin cậy người sử dụng thuê máy chủ ảo trung tâm liệu Người sử dụng thay đổi tảng hạ tầng giữ hiệu định Trong trình nghiên cứu, thấy nhiều vấn đề cần giải cho phép xây dựng hệ thống cung cấp tài nguyên tối ưu an toàn giữ trạng thái cân tải trung tâm liệu, nâng cao độ tin cậy trung tâm, tiết kiệm nguồn tài nguyên trung tâm liệu 104 KẾT LUẬN Luận án nghiên cứu giải pháp phòng chống bế tắc cung cấp tài nguyên phân tán cho hệ thống máy chủ ảo đạt kết chủ yếu sau: Cải tiến mô hình tính toán tối ưu liên quan tới cung cấp tài nguyên Đó mô hình tối ưu dựa chế lặp vòng (RTT), mô hình xếp theo nhóm người dùng mô hình tối ưu tài nguyên từ giải pháp thu hồi tài nguyên cung cấp cho tiến trình Xây dựng thuật toán cung cấp tài nguyên hiệu quả, dựa cải tiến thuật toán phát bế tắc Đưa thuật toán cải tiến cung cấp tài nguyên lớp hạ tầng IaaS tảng phân tán không Dựa cải tiến thuật toán song song phát bế tắc (PDDA) Đưa thuật toán cải tiến cung cấp tài nguyên lớp hạ tầng IaaS tảng phân tán không Dựa cải tiến thuật toán tìm kiếm hai chiều (Two Way) Đưa đánh giá so sánh thuật toán (PDDA), thuật toán cải tiến (PDDA) thuật toán cải tiến (Two Way) cung cấp tài nguyên lớp hạ tầng IaaS tảng phân tán không Trên sở kết đạt được, luận án đề xuất số hướng mở sau: Nghiên cứu mở rộng thuật toán Kshemkalyani-Singhal cho toán phân tán tài nguyên không đồng Nghiên cứu mở rộng mô hình cung cấp tài nguyên phân tán cho hệ thống máy chủ ảo Đồng thời, tiếp tục nghiên cứu mở rộng phương pháp mô thực nghiệm 105 DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ Nguyễn Hà Huy Cường (2012) Nghiên cứu giải pháp kỹ thuật ngăn chặn bế tắc cung cấp tài nguyên phân tán cho hệ thống máy chủ ảo, Tạp chí Khoa học Công nghệ, Viện Hàn Lâm Khoa học Công nghệ Việt Nam, 50(3E), pp 1324-1331 Nguyễn Hà Huy Cường, Lê Văn Sơn, Nguyễn Thanh Thủy (2013) Ứng dụng thuật toán Kshemkalyani-Singhal phát bế tắc cung cấp tài nguyên phân tán cho hệ thống máy chủ ảo, Hội nghị Quốc gia lần thứ VI Nghiên cứu ứng dụng Công nghệ thông tin (FAIR), Huế, 20 – 21/6/2013, NXB Khoa học Tự nhiên Công nghệ, Hà Nội, pp 602-608 Nguyễn Hà Huy Cường, Lê Văn Sơn (2013) Một sách hiệu cung cấp tài nguyên phân tán cho hệ thống máy chủ ảo, Kỷ yếu Hội thảo quốc gia “Một số vấn đề chọn lọc công nghệ thông tin Truyền thông”, Đà Nẵng, 14-15 tháng 11 năm 2013, NXB Khoa Học Tự Nhiên Kỹ Thuật, Hà Nội, pp 186-192 Nguyễn Hà Huy Cường, Lê Văn Sơn (2014) Kỹ thuật cung cấp tài nguyên cho lớp hạ tầng IaaS, Tạp chí Khoa học Công nghệ, Đại học Đà Nẵng, 7(80), pp 103-106 Ha Huy Cuong Nguyen, Van Son Le, Thanh Thuy Nguyen (2014) Algorithmic approach to deadlock detection for resource allocation in heterogeneous platforms,Proceedings of 2014 International Conference on Smart Computing, 3-5 November, HongKong, China, IEEE Computer Society Press, pp 97-103 Ha Huy Cuong Nguyen, Dac Nhuong Le,Van Son Le, Thanh Thuy Nguyen (2015) A new technical solution for resources allocation in heterogenenous distributed plaforms, Proceedings of 2015 The Sixth International Conference on the Applications of Digital Information and Web Technolo- 106 gies(ICADIWT2015), 10-12 Feb 2015, Macau, China, IOS Press, Volume 275, Issue 2, pp 184-194 Ha Huy Cuong Nguyen, Hung Vi Dang, Nguyen Minh Nhat Pham,Van Son Le, Thanh Thuy Nguyen (2015) Deadlock detection for resources allocation in heterogenenous distributed plaforms, Proceedings of 2015 Advances in Intelligent Systems and Computing, June 2015, Bangkok, Thailand, Spinger, Volume 361, Issue 2, pp 285-295 Ha Huy Cuong Nguyen (2016) Deadlock prevention for resource allocation in heterogeneous distributed platforms, Proceedings of 2016 7th International Conference on Applications of Digital Information and Web Technologies (ICADIWT2016), 29-31 March 2016, Macau, China, IOS Press, Volume 282, pp 40-49 Ha Huy Cuong Nguyen, Van Son Le, Thanh Thuy Nguyen (2016) Deadlock Prevention for Resource Allocation in model nVM-out-of-1PM, Proceedings of 2016 3th National Foundation for Science and Technology Development Conference on Information and Computer Science (NICS) , 14-16 September 2016, The University of Da Nang, Viet Nam, IEEE Computer Society Press, pp 247- 252 107 TÀI LIỆU THAM KHẢO Tiếng việt [1] Lê Văn Sơn (2002), Hệ tin học phân tán, Sách tham khảo, NXB Đại học Quốc Gia, Hồ Chí Minh [2] Nguyễn Văn Huân, Phạm Việt Bình (2010), Giáo trình Hệ sở liệu phân tán suy diễn, Lý thuyết thực hành,Giáo trình tham khảo, NXB Khoa học Kỹ thuật, Hà Nội [3] Phạm Thế Quế (2010), Giáo trình Cơ sở liệu phân tán, Giáo trình tham khảo, NXB Thông tin Truyền thông, Hà Nội Tiếng Anh [4] Addis, B., Ardagna, D., Panicucci, B (2010) Autonomic Management of Cloud Service Centers with Availability Guarantees In Proceedings of the 3th International Conference on Cloud Computing(CLOUD), 5-10 July 2010, Miami, FL, pp 220 - 227 [5] Ajay D Kshemkalyani, Mukesh Singhal (1999) A One-Phase Algorithm to Detect Distributed Deadlocks in Replicated Databases International journal IEEE Transactions on Knowledge and Data Engineering, 11(6), pp 880-895 [6] Ajay D Kshemkalyani, Mukesh Singhal (2008) Distributed Computing Principles, Algorithms, and Systems Cambridge University Press, UK [7] Anand Tumma, M.Laxman (2014) Allocation of Resources Dynamically Using Virtual Machines for Cloud Computing Services International journal of Computer Science and Mobile Applications, 2(9), pp 51-56 108 [8] Andreas Berl, Erol Gelenbe, Marco Di Girolamo, Giovanni Giuliani, Hermann De Meer, Minh Quan Dang, Kostas Pentikousis (2010) Energyefficient cloud computing The Computer Journal, 53(7), pp 1045-1051 [9] Baomin Xua, Chunyan Zhaob, Enzhao Hua, Bin Huc (2011) Job scheduling algorithm based on Berger model in cloud environment International journal of Advances in Engineering Software, 42(7), pp 419-425 [10] Borja Sotomayor Basilio (2010) Provisioning computational resources using virtual machines and leases Computer Science,The University of Chicago [11] Belik, F (2002) An efficient deadlock avoidance technique International journal IEEE Transactions on Computers, 39(7), pp 882-888 [12] Bing Wei, Chuang Lin and Xiangzhen Kong (2011) Dependability Modeling and Analysis for the Virtual Data Center of Cloud Computing In Proceedings of the 13th International Conference on High Performance Computing and Communications (HPCC) Banff, AB, IEEE, pp 784-789 [13] Borja Sotomayor, Rubén S Montero, Ignacio M Llorente, Ian Foster (2009) Virtual infrastructure management in private and hybrid clouds International journal IEEE of Internet Computing, 13(5), pp 14-22 [14] Bouyoucef, K., Limam-Bedhiaf, I., Cherkaoui, O (2010) Optimal allocation approach of virtual servers in cloud computing In Proceedings of the 6th International Conference on Next Generation Internet Networks(NGI), 2-4 June 2010, Paris, IEEE, pp 1-6 [15] Bracha, G., Toueg, S (1987) A distributed algorithm for generalized deadlock detection International journal of Distributed Computing, 2, pp 127138 [16] The Asia Cloud Computing Association’s Cloud Readiness Index 2016 [17] Cho, H., Kumar, T.K, and Wysk, R.A.(1995) Graph-Theoretic Deadlock Detection and Resolution for Flexible Manufacturing Systems.,” Interna- 109 tional journal of IEEE Transactions on Robotics and Automation, 11, pp 413–421 [18] CloudSim: Calheiros Rodrigo N., Rajiv Ranjan, Anton Beloglazov, César A F De Rose, and Rajkumar Buyya(2011) A toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms International journal of Distributed Computing, 41(1), pp 23-50 [19] Daji Ergu, Gang Kou, Yi Peng, Yong Shi, Yu Shi (2013) The analytic hierarchy process: task scheduling and resource allocation in cloud computing environment The Journal of Supercomputing, 64(3), pp 835-848 [20] Fumio Machida, Dong Seong Kim, Kishor S Trivedi (2013) Modeling and analysis of software rejuvenation in a server virtualized system with live VM migration International Journal of Performance Evaluation, 16(3), pp 212230 [21] Garg, S.K., Yeo, C.S., Anandasivam, A., Buyya, R (2011) Environment conscious scheduling of HPC applications on distributed cloud oriented data centers International journal of Parallel and Distributed Computing(JPDC), 71(6), pp 732-749 [22] Gligor V , Shattuck S (1980) Environment conscious scheduling of HPC applications on distributed cloud oriented data centers International journal of IEEE Transactions on Software Engineering, SE6(5), pp 435 - 440 [23] Greg N Frederickson (1987) Fast algorithms for shortest paths in planar graphs with applications SIAM Journal on Computing, 16(6), pp 10041022 [24] Ho G S., Ramamoorthy C V (1982) Protocols for deadlock detection in distributed database systems, International Journal IEEE Transactions on Software Engineering, 8(6), pp 554-557 110 [25] A Nico Habermann (1976) Introduction to Operation Systems Design, Science Research Associates [26] Jeff Chase, Laura Grit, David Irwin, Varun Marupadi, Piyush Shivam, Aydan Yumerefendi, Jeannie Albrecht (2007), Harnessing virtual machine resource control for job management, In Proceedings of the 1th International Conference on System level Virtualization for High Performance Computing (HPCVirt2007), pp 1–8 [27] Jiwei Huang, Chuang Lin, Xiangzhen Kong, Bing Wei, and Xuemin (Sherman) Shen (2014), Modeling and analysis of dependability attributes for services computing systems International Journal of IEEE Transactions on Services Computing (TSC), 7(4), pp 599–613 [28] Knapp,E (1987) Deadlock detection in distributed database systems International Journal of ACM Computing Surveys, 19(4), pp 303-327 [29] Krivokapi N , Kemper A , and Gudes E (1999) Deadlock detection in distributed database systems: a new algorithm and a comparative performance analysis The VLDB Journal 8(2), pp 79-100 [30] Lamport,L (1978) Time, Clocks, and the ordering of events in a distributed systems.International Journal of ACM Communications , 21(7), pp 558565 [31] Gunho Lee (2012) Resource allocation and scheduling in heterogeneous cloud environments Electrical Engineering and Computer Sciences, University of California at Berkeley, Doctor of Philosophy [32] Lee J J and Mooney V (2005) An O(min(m,n)) parallel deadlock detection algorithm International Journal of ACM Transactions on Design Automation of Electronic Systems, July 2005 10(3), pp 573-586 [33] Lee J J and Xiang Xiao (2008) A parallel deadlock detection algorithm 111 with O(1) overall run-time complexity International Journal of IEEE Computer Architecture Letters 7(2), pp 45-48 [34] Leon S Lasdon (1970) Optimization theory for large systems Macmillan Co., New York, US [35] Mark Stillwell, Frederic Vivien, Henri Casanova (2012) Virtual Machine Resource Allocation for Service Hosting on Heterogeneous Distributed Platforms Proceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium(IPDPS ’12),Washington, DC, USA, IEEE Computer Society pp 786-797 [36] Megha,T., Deepak, G (2012) Efficient method for Deadlock Detection and avoidance using two way search Computer science and engineering department,Tharpar university, Master of Engineering [37] Menase D.E and Muntz R (1979) Locking and deadlock detection in distributed databases.International Journal of IEEE transaction on software engineering.SE5(3), pp 195-202 [38] Misra J and Chandy K M (1982) A distributed graph algorithm: knot detection International Journal of ACM Transactions on Programming Language Systems 4(4), pp 678-686 [39] Mitchell D P and Merritt M J (1984) A distributed algorithm for deadlock detection and resolution In Proceedings of the ACM Symposium on Principles of Distributed Computing pp 282-284 [40] Nurmi, D , Wolski, R.,Grzegorczyk, C., Obertelli, G (2009) The Eucalyptus Open Source Cloud Computing System Proceedings of the 9th IEEE/ACM International Symposium on Cluster Computing and the Grid(CCGRID ’09), 18-21 May 2009 pp 124-131 [41] Obermarck R (1982) Distributed deadlock detection algorithm Interna- 112 tional Journal of ACM Transactions on Database Systems, 7(2), pp 187208 [42] Octavio J , Gutierrez-Garcia, Kwang Mong Sim (2012) A family of heuristics for agent based elastic Cloud bag of tasks concurrent scheduling International Journal of Future Generation Computer Systems pp 1-18 [43] Qiang Li, Qinfen Hao, Limin Xiao, Zhoujun Li (2009) Adaptive management of virtualized resources in Cloud Computing using feedback control Proceedings of the 1th Information Science and Engineering (ICISE), 26-28 Dec 2009, Nanjing, IEEE pp 99-102 [44] Rodrigo N Calheiros, Rajiv Ranjan, Anton Beloglazov, Cesar AF De Rose, Rajkumar Buyya(2011) CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms International Journal of Software: Practice and Experience 41(1), pp 23-50 [45] M Stillwell, D Schanzenbach, F Vivien, H Casanova, (2010) Resource Allocation Algorithms for Virtualized Service Hosting Platforms International Journal of Parallel and Distributed Computing (JPDC), 70(9), pp 962–974 [46] Tsafrir, D., Etsion, Y.,Feitelson, D.G (2007) Backfilling Using System Generated Predictions Rather than User Runtime Estimates International Journal of IEEE Transactions on Parallel and Distributed Systems 18(6), pp 789 - 803 [47] Vouk, M.A (2008) Cloud computing: Issues, research and implementations In Proceedings of the 30th International Conference on Information Technology Interfaces(ITI), 23-26 June 2008, pp 31-40 [48] Walsh, W.E.,Tesauro, G.,Kephart, J.O Das R (2004) Utility functions in autonomic systems Proceedings International Conference on Autonomic Computing, 17-18 May 2004, pp 70-77 113 [49] Warneke, D., Kao, O (2011) Exploiting dynamic resource allocation for efficient parallel data processing in the cloud International Journal of IEEE Transactions on Parallel and Distributed Systems 22(6), pp 985-997 [50] Wu, L., Garg, S.K., Buyya, R (2011) SLA-based resource allocation for a software as a service provider in cloud computing environments Proceedings of the 11th IEEE/ACM International Symposium on Cluster Computing and the Grid (CCGrid 2011), 23–26 May 2011, Los Angeles, USA , pp 195-204 [51] Xiaoming Nan, Yifeng He, Ling Guan (2012) Optimal allocation of virtual machines for cloud based multimedia applications Proceedings of the 14th IEEE Multimedia Signal Processing (MMSP), 17-19 Sept 2012, Banff, AB, IEEE pp 175-180 [52] Xing, K.Y, Hu, B.S, Chen, H.X (1996) Deadlock Avoidance Policy for PetriNet Modeling of Flexible Manufacturing Systems with Shared Resources International Journal of IEEE Transactions on Automatic Control 41(2), pp 289–295 [53] Yazir, Y.O., Matthews, C., Farahbod, R., Neville, S (2010) Dynamic resource allocation in Computing Clouds using distributed multiple criteria decision analysis Proceedings of the 3th Cloud Computing (CLOUD), 5-10 July 2010, Miami FL,IEEE pp 91-98 [54] Ying Song, Yuzhong Sun, Weisong Shi (2013) A two tiered on demand resource allocation mechanism for VM-based data centers International Journal of IEEE Transactions on services computing 6(1), pp 116-129 [55] Zhen Xiao, Weijia Song, Qi Chen (2013) Dynamic resource allocation using virtual machines for cloud computing environment International Journal of IEEE Transactions on Parallel and Distributed Systems 24(6), pp 11071117 [56] https://aws.amazon.com/ec2/ 114 [57] http://www8.hp.com/us/en/cloud/helion-eucalyptus-overview.html [58] http://www.nimbusproject.org/ [59] http://opennebula.org/ [60] https://www.vmware.com/support/pubs/ [61] https://www.cloudbus.org/cloudsim/ [62] https://sourceforge.net/projects/lpsolve/ [...]... đề: 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... 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: ... 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. .. Đố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 đề... 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á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ủ. .. 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,... cụm máy chủ ảo Linux Đây là một framework nghiên cứu tối ưu trong hệ thống tự trị tính toán phân tán [48] Trong [4], đề xuất giải pháp dựa trên máy ảo (VM-based) quản lý theo kiểu thích nghi các nguồn tài nguyên được ảo hóa trong điện toán đám mây Kiến trúc dựa trên máy ảo cho phép cung cấp thông tin tài nguyên trừu tượng giữa các ứng dụng khác nhau, chạy trong hệ thống tài nguyên ảo và cung cấp tài nguyên. .. giữ nguồn tài nguyên của máy vật lý S1 , trong khi đó máy ảo V M2 giữ tài nguyên của máy vật lí S2 Tại thời điểm này, V M1 gửi yêu cầu tài nguyên của máy vật 24 Hình 1.3 Ví dụ bế tắc trong cung cấp tài nguyên máy chủ ảo lý S2 và V M2 gửi yêu cầu tài nguyên của máy vật lý S1 Khi V M1 gửi yêu cầu đến S2 , hệ thống sẽ gặp bế tắc, vì V M2 không thể trả lại tài nguyên cho máy vật lý S2 hoặc máy vật lý... 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 ... 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Ệ... Chương 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 hệ thống máy chủ ảo ... P-out-of-Q hệ phân tán - Đưa khung lý thuyết tương đối hoàn chỉnh cung cấp tài nguyên phân tán cho hệ thống máy chủ ảo không - Giải toán phát hiện, phòng chống bế tắc cung cấp tài nguyên phân tán cho hệ