Tài liệu Nghiên cứu thuật toán cấp phát máy ảo dựa trên bài toán cái túi

TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT KHOA CÔNG NGHỆ THÔNG TIN Tên đề tài: Xây Dựng Hệ Quản Trị Tài Nguyên Trên Điện Toán Đám Mây IaaS Mã số: Tên báo cáo chuyên đề: Nghiên cứu thuật toán cấp phát máy ảo dựa trên bài toán cái túi Chủ nhiệm đề tài: ThS. Bùi Thanh Khiết Người chủ trì thực hiện chuyên đề: ThS. Bùi Thanh Khiết Bình Dương, 20/05/2015 1 MỤC LỤC MỤC LỤC ................................................................................................................... i DANH MỤC CÁC CHỮ VIẾT TẮT ........................................................................ ii DANH MỤC BẢNG ................................................................................................. iii 1. Đặt vấn đề ...............................................................................................................1 2. Phương pháp nghiên cứu .........................................................................................1 3. Công nghệ ảo hóa máy chủ .....................................................................................2 3.1. Khái niệm ảo hóa máy chủ ................................................................................2 3.2. Phân loại ảo hoá máy chủ [1, 2, 4, 7, 8] ............................................................3 3.2.1. Ảo hóa hệ điều hành ....................................................................................3 3.2.2. Ảo hóa phần cứng (Full-virtualization) .......................................................4 3.2.3. Ảo hóa song song (Para-virtualization) .......................................................5 3.3. Lợi ích ảo hóa máy chủ .....................................................................................6 3.3. Mối quan hệ của ảo hóa máy chủ và điện toán đám mây .................................7 4. Nghiên cứu bài toán cái túi .....................................................................................7 4.1 Bài toán cái túi ....................................................................................................7 4.2 Bài toán cái túi dạng 0-1.....................................................................................8 4.3 Một số cách giải bài toán cái túi .........................................................................9 4.3 Nhận xét .............................................................................................................9 5. Xây dựng thuật toán cấp phát máy ảo trên IaaS .....................................................9 5.1 Giới thiệu ............................................................................................................9 5.2 Thuật toán sử dụng tối thiểu máy chủ vật lý ....................................................10 5.3 Thuật toán cân bằng tải máy chủ vật lý ............................................................11 5.4. Kết quả nghiên cứu ..........................................................................................13 6. Kết luận và kiến nghị ............................................................................................15 Phụ lục .......................................................................................................................17 i DANH MỤC CÁC CHỮ VIẾT TẮT Viết tắt Tiếng Anh Tiếng Việt IaaS Infrastructure as a Service Dịch vụ cơ sở hạ tầng VM Virtual Machine Máy ảo VMM Virtual Machine Monitor Giám sát máy ảo OS Operating System Hệ điều hành HA High Availability Sẵn sàng cao BW Bandwidth Băng thông MIPS Millions Instructions Per Second ARCH System architecture PEs processing elements Kiến trúc hệ thống ii DANH MỤC BẢNG Bảng 5. 1 Cấu hình máy chủ vật lý ...........................................................................13 Bảng 5. 2 Cấu hình máy ảo .......................................................................................14 Bảng 5. 3 Kết quả thực nghiệm .................................................................................14 Bảng 5. 4 Kết quả thực nghiệm chi tiết .....................................................................19 iii DANH MỤC HÌNH VẼ Hình 3. 1 Mô hình ảo hóa hệ điều hành ......................................................................3 Hình 3. 2. Mô hình ảo hóa phần cứng .........................................................................4 Hình 3. 3. Mô hình ảo hóa song song .........................................................................5 Hình 4. 1. Bài toán xếp ba lô một chiều ......................................................................8 iv 1. Đặt vấn đề Mô hình điện toán đám mây (ĐTĐM) dịch vụ cơ sở hạ tầng (Infrastruture as a Server – IaaS) cung cấp cho người dùng cơ sở hạ tầng như mạng, máy chủ, CPU, bộ nhớ, không gian lưu trữ và các tài nguyên tính toán khác thường dưới dạng máy ảo (VM) bằng công nghệ ảo hóa máy chủ. Công nghệ ảo hóa máy chủ cho phép tạo ra nhiều máy ảo trên một máy chủ vật lý, mỗi máy ảo cũng được cấp phát tài nguyên phần cứng như máy thật với RAM, CPU, card mạng, ổ cứng, hệ điều hành và các ứng dụng riêng. Trong ĐTĐM IaaS có chứa rất nhiều máy chủ vật lý, do đó vấn đề cấp phát máy ảo làm sao để sử dụng hiệu quả tài nguyên máy chủ vật lý và đáp ứng yêu cầu sử dụng tài nguyên đa dạng của người dùng, tiết kiệm được năng lượng sử dụng điện là vấn đề rất cần thiết nhất là triển khai ĐTĐM IaaS cho một phòng thí nghiệm của một trường đại học. Hiện nay có nhiều chiến lược cấp phát máy ảo trong IaaS, để làm tốt việc cấp phát máy ảo thì phụ thuộc rất nhiều vào môi, chiến lược cấp phát. Trong chuyên đề này, chúng tôi nghiên cứu 2 chiến lược chính trong cấp phát tài nguyên là: (i) sử dụng tối thiểu máy chủ vật lý nhằm giúp tiết kiệm tài nguyên (điện) của hệ thống; (ii) cân bằng tải trong việc sử dụng các máy vật lý đảm bảo chất lượng dịch vụ nhằm tránh tình trạng quá tải ở máy chủ vật lý. Từ đó, chúng tôi nghiên cứu 2 thuật toán cấp phát cho hai chiến lược trên dựa vào thuật toán tham lam và thuật toán RoundRobin, sau đó xây dựng và thực nghiệm thuật toán trên CloudSim toolkit [3] 2. Phương pháp nghiên cứu  Nghiên cứu lý thuyết về công nghệ ảo hóa máy chủ.  Nghiên cứu lý thuyết và cách giải bài toán cái túi.  Nghiên cứu thuật toán tham lam, thuật toán RoundRobin.  Ứng dụng cách giải bài toán cái túi để xây dựng giải thuật cấp phát tài nguyên cho điện toán đám mây IaaS. 1 3. Công nghệ ảo hóa máy chủ Ngày nay, hệ thống máy chủ ở các trung tâm dữ liệu thường hoạt động khoảng 10% tới 25% công suất. Nói cách khác, 75% tới 90% công suất của máy không được dùng đến. Một máy chủ dùng chưa hết công suất vẫn chiếm diện tích sử dụng và hao tổn điện năng, vì vậy chi phí hoạt động của một máy chủ không được sử dụng đúng mức cũng gần bằng với chi phí khi chạy hết công suất. Như vậy chúng ta đang lãng phí các tài nguyên của cả hệ thống. Với sự cải tiến không ngừng các đặc điểm hoạt động của phần cứng, máy tính trong năm tới sẽ có công suất gấp đôi máy tính của năm nay. Từ đó, phải có một cách nào đó hiệu quả hơn để công suất của làm việc của máy tương ứng với tỷ lệ sử dụng và đó là những gì mà ảo hóa có thể làm được –bằng việc dùng một phần cứng duy nhất để hỗ trợ cùng một lúc nhiều hệ thống. Ảo hóa máy chủ mang lại cơ hội cắt giảm chi phí bằng việc giảm số lượng máy chủ. Ít máy chủ hơn nghĩa là cần ít diện tích hơn, ít nhân viên hơn và giảm điện năng tiêu thụ. 3.1. Khái niệm ảo hóa máy chủ Ảo hóa máy chủ là công nghệ ứng dụng ảo hóa nhằm khai thác triệt để khả năng làm việc của các phần cứng trong một hệ thống máy chủ. Ý tưởng của ảo hóa máy chủ là tạo ra nhiều máy ảo trên một máy chủ vật lý, mỗi máy ảo cũng được cấp phát tài nguyên phần cứng như máy thật với RAM, CPU, card mạng, ổ cứng, hệ điều hành và các ứng dụng riêng. 2 3.2. Phân loại ảo hoá máy chủ [1, 2, 4, 7, 8] 3.2.1. Ảo hóa hệ điều hành Hình 3. 1 Mô hình ảo hóa hệ điều hành Hình 3.1 minh họa mô hình ảo hóa hệ điều hành, bao gồm các tầng sau:  Phần cứng của máy vật lý;  Hệ điều hành chia sẻ (Shared OS): hệ điều hành máy vật lý có khả năng chia sẻ phần cứng cho những hệ điều hành ảo;  Hệ điều hành khách: hệ điều hành của máy ảo;  Ứng dụng: thực thi trên hệ điều hành khách. Ảo hóa hệ điều hành là một dạng ảo hóa phần mềm. Hệ điều hành cho phép nhiều thể hiện của không gian khách hàng khác nhau có thể cùng thực thi. Những thể hiện đó chính là những hệ điều hành ảo đem đến cho người dùng cảm giác như một máy thật. Nhân hệ điều hành cung cấp tính năng quản lý tài nguyên cho phép cô lập các hệ điều hành ảo, nhằm tránh xung đột tài nguyên với nhau. Chi phí để thực hiện ảo hóa hệ điều hành tương đối thấp, với hiệu năng hệ thống cao, vì các ứng dụng trong hệ điều hành ảo chỉ đơn giản thực thi và gọi những lời gọi hệ thống như bình thường, không cần phải có một bộ giả lập hoặc máy ảo trung gian. Giải pháp cũng không đòi hỏi sự hỗ trợ từ phần cứng. Tuy nhiên 3 nhược điểm lớn nhất của ảo hóa hệ điều hành là kém linh hoạt, bởi hệ điều hành khách cũng chính là hệ điều hảnh chủ (hoặc có chung nhân như nhân linux) do đó ảo hóa hệ điều hành chỉ thích hợp với cấu hình thuần nhất. 3.2.2. Ảo hóa phần cứng (Full-virtualization) Hình 3. 2. Mô hình ảo hóa phần cứng Hình 3.2 minh họa mô hình ảo hóa phần cứng, bao gồm các tầng sau:  Phần cứng vật lý: bao gồm thiết bị nhập xuất, thiết bị lưu trữ, bộ vi xử lý;  Bộ giám sát máy ảo (Virtual Machine Monitor – VMM): cung cấp cho máy ảo tất cả các dịch vụ của hệ thống phần cứng bao gồm BIOS ảo, thiết bị ảo, quản lý bộ nhớ ảo;  Các máy ảo: sử dụng tài nguyên do VMM quản lý;  Hệ điều hành khách: thực thi trên nền các máy ảo này;  Ứng dụng: thực thi trên hệ điều hành khách. Phương pháp ảo hóa này dựa trên việc giả lập phần cứng máy tính. VMM mô phỏng phần cứng và liên lạc với các trình điều khiển thiết bị. Các trình điều khiển thiết bị phần cứng liên lạc trực tiếp đến phần cứng vật lý. Các máy ảo sử dụng tài nguyên do VMM quản lý. Máy ảo là một ảnh của toàn bộ hệ thống, bao gồm BIOS ảo, 4 không gian bộ nhớ ảo và các thiết bị ảo. Hệ điều hành khách không bị thay đổi và chúng hoạt động như trên phần cứng thật sự. Phương pháp này không chỉ hỗ trợ nhiều hệ điều hành mà còn hỗ trợ nhiều loại hệ điều hành khác nhau thực thi trên cùng một máy chủ. Mỗi hệ điều hành này có thể khác nhau về phiên bản thậm chí còn khác nhau hoàn toàn như Windows và Linux có thể thực thi đồng thời trên phần mềm ảo hóa phần cứng. Nhược điểm của mô phỏng phần cứng là nó ảnh hưởng đến khả năng hoạt động của hệ thống. Điều này khiến cho các ứng dụng trên các máy ảo thực thi chậm hơn bình thường. Các công ty cung cấp phần mềm ảo hóa phần cứng gồm có VMware (ở cả hai phiên bản VMware Server và ESX Server) và Microsoft. 3.2.3. Ảo hóa song song (Para-virtualization) Hình 3. 3. Mô hình ảo hóa song song Hình 3.3 minh họa mô hình ảo song song, bao gồm các tầng sau:  Phần cứng vật lý: bao gồm thiết bị nhập xuất, thiết bị lưu trữ, bộ vi xử lý và các thiết bị khác như các thiết bị mạng, vi xử lý đồ họa, âm thanh ...;  Giám sát máy ảo (Virtual Machine Monitor – VMM): chỉ mô phỏng một phần và cung cấp các dịch vụ để hệ điều hành khách tương tác với hệ thống phần cứng; 5  Các máy ảo: sử dụng tài nguyên do VMM quản lý.  Hệ điều hành khách: thực thi trên nền các máy ảo này, hệ điều hành này được đã tinh chỉnh.  Ứng dụng: thực thi trên hệ điều hành khách. Với phương pháp ảo hóa này, thay vì mô phỏng một môi trường phần cứng hoàn chỉnh, VMM chỉ mô phỏng một phần và cung cấp các dịch vụ để hệ điều hành khách tương tác với hệ thống phần cứng. Để có thể tương tác với hệ thống phần cứng thì hệ điều hành khách phải được tinh chỉnh, không phải là phiên bản giống như hệ điều hành gốc. Do đó, hệ điều hành khách thực thi ảo hóa song song với phần giả lập phần cứng. Điều này có nghĩa không phải hệ điều hành nào cũng có thể thực thi ảo hóa song song. Ảo hóa song song có hai ưu điểm. Thứ nhất, hiệu năng hệ thống cao hơn do không cần mô phỏng toàn bộ phần cứng vật lý. Thứ hai, không giới hạn trình điều khiển thiết bị trong phần mềm ảo hóa như ảo hóa phần cứng. Bởi vì ảo hóa song song sử dụng trình điều khiển thiết bị có trong hệ điều hành chủ, tận dụng được nhiều loại phần cứng. Sản phẩm nguồn mở XenServer xuất hiện trong các bản phân phối Linux là một ví dụ điển hình về para-virtualization. 3.3. Lợi ích ảo hóa máy chủ Triển khai nhanh: thay vì cài đặt máy chủ, chỉ cần cần khôi phục một bản sao lưu hoặc đơn giản là sao chép tập tin của máy ảo trong phần mềm ảo hóa. Đối với nhiều máy ảo, việc triển khai hàng loạt một cách tự động là điều có thể. Việc nâng cấp phần cứng được thực hiện nhanh chóng và đơn giản bằng các thủ tục phần mềm. Tăng khả năng khôi phục sau thảm họa: việc ảo hóa cô lập phần lớn các lỗi của máy ảo khỏi máy vật lý. Ngoài ra, nếu một máy vật lý bị sự cố thì các máy ảo sẽ được di chuyển đến máy chủ khác và có thể hoạt động lại ngay tức thì. Sao lưu và khôi phục dễ dàng hoàn toàn bằng phần mềm. Phân phối tài nguyên linh hoạt: với các công cụ quản lý từ xa các máy chủ và máy ảo ta sẽ thấy tình trạng toàn bộ hệ thống từ đó có chính sách nâng cấp máy vật lý 6 hoặc máy ảo đó hoặc di chuyển máy ảo đang quá tải đó sang máy chủ vật lý có cấu hình mạnh hơn, có nhiều tài nguyên còn trống hơn để hoạt động. Điều này giúp đối phó với những yêu cầu tăng tài nguyên một cách đột biến trong thời gian ngắn, do đó tài nguyên vật lý được tận dụng tối đa. Những máy chủ thường xuyên trao đổi thông tin với nhau có thể được di chuyển đến những vị trí vật lý gần nhau hơn để tăng cường hiệu năng liên kết. Tiết kiệm: thông thường, các máy chủ chỉ sử dụng rất ít tài nguyên của hệ thống, trong đó phần lới là bộ vi xử lý và bộ nhớ. Các nghiên cứu cho thấy trung bình doanh nghiệp chỉ sử dụng khoảng 10% đến 25% công suất máy chủ. 3.3. Mối quan hệ của ảo hóa máy chủ và điện toán đám mây Ảo hóa được xem là một phần xu hướng chung đối với các hệ thống thông tin cho doanh nghiệp. Xu hướng đó bao gồm cả điện toán tự trị (autonomic computing) mà trong đó môi trường điện toán có thể tự quản lý dựa trên thông tin theo dõi được từ hoạt động của chính nó và điện toán theo yêu cầu (ultility computing) khi mà năng lực xử lý của máy tính được xem như tiện ích mà khách hàng có thể chi trả theo nhu cầu sử dụng. Trong cả hai xu hướng, vai trò của ảo hóa rất quan trọng. Ảo hóa chính là chìa khóa của điện toán đám mây. Mặc dù không phải bắt buộc nhưng những mô hình điện toán đám mây sử dụng công nghệ ảo hóa sẽ có hiệu năng và tính linh hoạt cao nhờ khả năng chia sẽ các tài nguyên ảo thông qua hệ thống mạng. Bằng cách sử dụng ảo hóa, chi phí triển khai hệ thống sẽ giảm đáng kể và còn đảm bảo được tính hiệu quả trong việc sử dụng tài nguyên. 4. Nghiên cứu bài toán cái túi 4.1 Bài toán cái túi Bài toán cái túi hay còn gọi là bài toán xếp ba lô là một bài toán tối ưu hóa tổ hợp. Bài toán được đặt tên từ vấn đề chọn những gì quan trọng có thể cho vừa vào trong một cái túi (với giới hạn khối lượng) để mang theo trong một chuyến đi. Các bài 7 toán tương tự thường xuất hiện trong kinh doanh, toán tổ hợp, lý thuyết độ phức tạp tính toán, mật mã học và toán ứng dụng. Hình 4. 1. Bài toán xếp ba lô một chiều Ví dụ về một bài toán xếp ba lô giới hạn 1 chiều: chọn các hộp nào để làm cực đại lượng tiền trong khi giữ được tổng khối lượng dưới 15 kg? Bài toán đa chiều có thể xét đến khối lượng riêng và kích thước của các hộp, đó là bài toán xếp vali điển hình (packing problem). Ta có n loại đồ vật, x1 tới xn. Mỗi đồ vật xj có một giá trị pj và một khối lượng wj. Khối lượng tối đa mà ta có thể mang trong ba lô là C. 4.2 Bài toán cái túi dạng 0-1 Hạn chế số đồ vật thuộc mỗi loại là 0 (không được chọn) và 1 (được chọn). Bài xếp ba lô 0-1 có thể được phát biểu bằng toán học như sau: 8 Cực đại hóa sao cho 4.3 Một số cách giải bài toán cái túi a) Thuật toán trực tiếp (Brute-force): duyệt tất cả 2n khả năng đồ vào túi, tình cách chất có tổng giá trị lớn nhất có tổng trọng lượng các đồ vật không quá dung lượng cái túi b) Thuật toán tham lam: sắp xếp các đồ vật theo thứ tự không tăng giá trị. Lần lượt xét các đồ vật theo thứ tự đã sắp, chất đồ đang xét vào túi nếu như dung lượng còn lại của cái túi đó đủ chứa nó( tức là tổng trọng lượng của các đồ vật đã xếp vào túi và trọng lượng của các đồ vật đang xét không vượt quá khả năng của túi). 4.3 Nhận xét Đây là vấn đề khó và được xếp vào dạng NP-Hard nên thường được giải theo dạng heurictic. Cần phải xác định mục tiêu, chiến lược cụ thể khi giải. 5. Xây dựng thuật toán cấp phát máy ảo trên IaaS 5.1 Giới thiệu Trong cơ sở hạ tầng của điện toán đám mây IaaS, giả sử có M máy vật lý đồng nhất được thể hiện P={P1 , P2 , …, Pn}. Nhờ công nghệ ảo hóa, máy vật lý có thể triển khai máy ảo trên chính nó. Tất cả các máy vật lý có thể nhận yêu cầu máy ảo và tạo ra máy ảo đáp ứng yêu cầu của người dùng. Một yêu cầu máy ảo được thể hiện trong tập Ri = {r1 , r2 , …, rn} các máy ảo trong lần yêu cầu thứ i, trong đó một máy ảo sẽ được thể hiện là ri (m, c, d) với m là yêu cầu ram của máy ảo, c là yêu cầu số cpu của máy ảo, d là yêu cầu image của máy ảo; mỗi yêu cầu máy ảo độc lập nhau. 9 Việc cấp phát máy ảo như thế nào để có thể đảm bảo việc sử dụng tài nguyên hiệu quả cũng như việc sử dụng dịch vụ cơ sở hạ tầng IaaS ổn định là một vấn đề quan trọng, cần phải có chiến lược cấp phát tài máy ảo trong IaaS hợp lý. Ở đây, chúng tôi sẽ nghiên cứu thuật toán đáp ứng hai chiến lược[5, 6, 10, 11]: (i) sử dụng tối thiểu máy chủ vật lý; (ii) cân bằng tải trong việc sử dụng các máy vật lý. Chúng tôi đề xuất 2 thuật toán cho hai chiến lược cấp phát máy ảo nói trên phương pháp tham lam, phương pháp RoundRobin[9] và triển khai thực nghiệm trên CloudSim toolkit 3.0. 5.2 Thuật toán sử dụng tối thiểu máy chủ vật lý Để xác định khả năng phân phối tất cả các máy ảo của người dùng vào các máy đơn vật lý thì đầu tiên, thuật toán sẽ sắp xếp các máy đơn vật lý theo các tiêu chuẩn sau: 1) Đầu tiên, ưu tiên máy đơn vật lý nào có ít hợp đồng đang chạy nhất tại thời điểm t. 2) Nếu tiêu chuẩn (1) bằng nhau, so sánh dựa vào số lượng tài nguyên rảnh tại thời điểm t. Khi các máy đơn đã được sắp xếp, sử dụng thuật toán tham lam để phân phối tất cả các máy ảo. Thuật toán cố gắng phân phối càng nhiều máy ảo lên một máy đơn vật lý càng tốt. 10 Thuật toán 1: Phân phối tham lam - Greedy Input: R {Danh sách yêu cầu máy ảo} Output: Một cách phân phối R → P map ← empty dictionary P' ←sort(P) {Sắp xếp dựa theo chiến lược lựa chọn máy đơn đã nêu} cur_vm ← Máy ảo đầu tiên trong R for P' do p_done ← false while not p_done do if cur_vm có thể phân phối lên p then mapcur-vm ← p cur_vm ← Máy đơn tiếp theo trong R else p_done ← true end if end while end for return map 5.3 Thuật toán cân bằng tải máy chủ vật lý Cân bằng tải là một phương pháp phân phối khối lượng tải trên nhiều máy tính hoặc một cụm máy tính để có thể sử dụng tối ưu các nguồn lực, tối đa hóa thông lượng, giảm thời gian đáp ứng và tránh tình trạng quá tải trên máy chủ. Các lợi ích khi sử dụng phương pháp cân bằng tải:  Tăng khả năng đáp ứng, tránh tình trạng quá tải trên máy chủ, đảm bảo tính linh hoạt và mở rộng cho hệ thống.  Tăng độ tin cậy và khả năng dự phòng cho hệ thống:Sử dụng cân bằng tải giúp tăng tính HA (High Availability) cho hệ thống, đồng thời đảm bảo cho người dùng không bị gián đoạn dịch vụ khi xảy ra lỗi sự cố lỗi tại một điểm cung cấp dịch vụ. 11  Tăng tính bảo mật cho hệ thống:Thông thường khi người dùng gửi yêu cầu dịch vụ đến hệ thống, yêu cầu đó sẽ được xử lý trên bộ cân bằng tải, sau đó thành phần cân bằng tải mới chuyển tiếp các yêu cầu cho các máy chủ bên trong. Quá trình trả lời cho khách hàngcũng thông qua thành phần cân bằng tải, vì vậy mà người dùng không thể biết được chính xác các máy chủ bên trong cũng như phương pháp phân tải được sử dụng. Bằng cách này có thể ngăn chặn người dùng giao tiếp trực tiếp với các máy chủ, ẩn các thông tin và cấu trúc mạng nội bộ, ngăn ngừa các cuộc tấn công trên mạng hoặc các dịch vụ không liên quan đang hoạt động trên các cổng khác. Chúng tôi đề xuất dùng thuật toán Round Robin cho chiến lược cân bằng tải các máy chủ vật lý – đây gọi là thuật toán luân chuyển vòng, các máy chủ sẽ được xem ngang hàng và sắp xếp theo một vòng quay. Các truy vấn dịch vụ sẽ lần lượt được gửi tới các máy chủ theo thứ tự sắp xếp. Ví dụ: Cấu hình một cụm Cluster bao gồm 03 máy chủ: A, B, C.  Yêu cầu dịch vụ thứ nhất sẽ được gửi đến máy chủ A.  Yêu cầu dịch vụ thứ hai sẽ được gửi đến máy chủ B.  Yêu cầu dịch vụ thứ ba sẽ được gửi đến máy chủ C.  Yêu cầu dịch vụ thứ tư sẽ lại được gửi cho máy chủ A…. 12 Thuật toán 2: Phân phối cân bằng tải – Round Robin Input: R {Danh sách yêu cầu máy ảo} Output: Một cách phân phối R → P map ← empty dictionary cur_p {Máy chủ vật lý đầu tiên trong P} size ← {số lượng máy chủ vật lý trong P} for ∀ vm ∈ R do cur_p = cur_p%size if vm có thể phân phối lên cur_p then mapcur_node ← p cur_p ← Máy chủ vật lý tiếp theo trong R else end for return map 5.4. Kết quả nghiên cứu Chúng tôi xây dựng thuật toán và thực nghiệm trên công cụ CloudSim 3.0 toolkit. Chúng tôi xây dựng một datacenter có 5 host (máy chủ vật lý), với cấu hình của các host sau: Tham số Giá trị System architecture (arch) x86 Operating system (os) Linux Time zone this resource located (time_zone) 7 Virtual machine monitoring (vmm) Xen Ram 2048 Mb Strorage 100,000 Mb Bandwidth (bw) 10,000 (*) PEs 5 Bảng 5. 1 Cấu hình máy chủ vật lý (*) CloudSim Pe (Processing Element) class represents CPU unit, defined in terms of Millions Instructions Per Second (MIPS) rating. ASSUMPTION: All PEs under the same Machine have the same MIPS rating. 13 Với yêu cầu cấu hình máy ảo như sau Tham số Giá trị Image size (size) 10,000 Mb Ram 512 Mb MIPS (mips) 1000 Bandwidth (bw) 1000 vmm xen Number of cpus (pesNumber) 1 Bảng 5. 2 Cấu hình máy ảo Với hệ thống IaaS gồm 1 datacenter có 5 host, chúng tôi đã thực thi chương trình giả lập lần lượt là 5, 10, 15, 20, 25 máy ảo được gửi lên hệ thống và thu được kết qủa như bảng sau (có thể xem kết quả chi tiết trong phần phụ lục): Số VM yêu cầu cấp phát 5 10 15 20 25 Số VM cấp Số lượng Host sử dụng phát thành theo thuật toán 1 công Greedy 5 2 10 3 15 4 20 5 20 ( 5 VM bị lỗi) 5 Số lượng Host sử dụng theo thuật toán 2 – Round Robin 5 5 5 5 5 Bảng 5. 3 Kết quả thực nghiệm Host 6 5 4 Greedy 3 RoundRobin 2 1 0 5 10 15 20 25 VM Hình 5. 1 Số lượng host được sử dụng theo thuật toán Greedy và RoundRobin Với hệ thống IaaS ( 5 Host) trên chỉ có thể cấp phát tối đa 20 máy ảo cùng lúc vì hệ thống các Host không đủ tài nguyên để cấp phát thêm, cụ thể ở đây là Ram. 14 6. Kết luận và kiến nghị Trong chuyên đề này chúng tôi trình bày cơ sở lý thuyết về công nghệ ảo hóa máy chủ được phân làm ba loại gồm: ảo hóa hệ điều hành, ảo hóa ful-virtuatlization, ảo hóa para-virtuatlization. Thuật toán cấp phát máy ảo trong IaaS được nghiên cứu theo hai chiến lược:  (i) Sử dụng tối thiểu máy chủ vật lý. Được hiện thực dựa trên thuật toán phân phối tham lam.  (ii) Cân bằng tải trong việc sử dụng các máy vật lý. Được hiện thực dựa trên thuật toán RoudRobin. Hai thuật toán được cài đặt, thực nghiệm trên công cụ nguồn mở CloudSim toolkit 3.0 trên ngôn ngữ Java. Tùy vào mục tiêu của người khai thác IaaS mà có thể chọn chiến lược thích hợp, chẳng hạn sử dụng chiến lược (i) nếu muốn tiệt kiệm tài nguyên hệ thống đặc biệt là năng lượng, ngược lại nếu muốn tránh tình trạng quá tải của hệ thống có thể dùng chiến lược (ii). Tuy nhiên, để đạt được sự linh hoạt trong việc cấp phát tài nguyên cần phải nghiên cứu thêm các vấn đề về chia sẻ tài nguyên, định thời trong cấp phát tài nguyên, … 15