Nghiên cứu đánh giá hiệu năng của các thuật toán lập lịch trong điện toán đám mây

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (4.65 MB, 22 trang )

Trang 1<div class="page_container" data-page="1">

HỒNG DUY ĐƠNG

NGHIÊN CỨU ĐÁNH GIÁ HIỆU NĂNG CỦA CÁC THUẬT TOÁN LẬP

LỊCH TRONG ĐIỆN TOÁN ĐÁM MÂY

Chuyên ngành: Kỹ thuật Viễn thông

Mã số: 60.52.02.08

HÀ NỘI - 2015

</div>Trang 2<div class="page_container" data-page="2">

Luận văn được hoàn thành tại:

Người hướng dẫn khoa học: TS. NGUYEN CHIEN TRINH

Phản biện 1: TS. NGUYEN QUÝ SY

Phản biện 2: PGS.TS. ĐÀO TUẦN

Luận văn đã được bảo vệ trước Hội đông châm luận văn thạc sĩ tại Học viện

Cơng nghệ Bưu chính Viễn thơng

Vào lục: ic ngay 20 thang 9 nam 2015

Có thê tìm hiéu luận văn tại:

- Thu viện của Học viện Cơng nghệ Bưu chính Viễn Thơng

</div>Trang 3<div class="page_container" data-page="3">

MỞ ĐẦU

Điện tốn đám mây hiện nay là xu hướng cơng nghệ mới dang phát trién mạnh mẽ. Điện toán đám mây cung cấp khả năng mở rộng tài nguyên ảo tự động thông qua các dịch vụ Internet dé sử dung theo yêu cầu, và cũng phát triển cao hơn điện toán phân tán, điện toán song song và điện tốn lưới. Ưu điểm chính của điện tốn đám mây là có thé giảm nhanh các chi phí phần cứng và tăng khả năng tính tốn và khả

năng lưu trữ, người sử dụng có thể truy cập dịch vụ chất lượng cao với mức chỉ phí

Lập lịch là một phần rất quan trọng trong điện tốn đám mây, nó là một cơ chế

sắp xếp các nhiệm vụ người dùng tới nguồn tài nguyên thích hợp dé thực thi. Hiệu qua

của nó ảnh hưởng trực tiếp đến hiệu suất của tồn bộ mơi trường điện tốn đám mây.

Bang cách sử dụng kỹ thuật ảo hóa, tat cả các tài nguyên vật ly được ảo hóa và mang

lại nhiều tiện ích cho người sử dụng.

Mục tiêu trong luận văn này sẽ nghiên cứu, phân tích và đưa ra đề xuất nhằm đánh giá hiệu năng năng lượng của một số thuật toán lập lịch. Cụ thê hơn nữa là đưa ra

một chính sách hướng tới tiết kiệm năng lượng cho việc vận hành những server farm

với ba mơ hình phân bố tài ngun áp dụng đối với server ảo (mơ hình tải cao nhất, mơ hình tải thấp nhất, mơ hình tải ưu tiên), hướng tới việc giảm tiêu thụ năng lượng đối với các hạ tầng thông tin và viễn thông và qua đó giảm được giá thành năng lượng đối với các nhà cung cấp và triển khai dịch vụ điện toán đám mây.

Luận văn này đã được xây dựng với những nội dung chính như sau:

Chương 1: Trình bày tổng quan về khái niệm, kiến trúc, mơ hình, cũng như co

chế lập lịch trong điện toán đám mây và xu hướng nghiên cứu lập lịch hiện nay

Chương 2: Trình bày một số thuật toán lập lịch truyền thống, các tham số đánh giá hiệu năng, so sánh hiệu năng của một số thuật tốn lập lịch qua đó dé xuất thuật toán lập lịch cho các server ảo nhằm sử dụng hiệu quả năng lượng.

Chương 3: Trình bày quy trình tiến hành mơ phỏng khảo sát hiệu năng chú trọng yếu tố hiệu quả năng lượng, đánh giá và nhận xét kết quả mô phỏng.

</div>Trang 4<div class="page_container" data-page="4">

CHƯƠNG 1

TONG QUAN VE ĐIỆN TOÁN DAM MAY VÀ LẬP LICH TRONG DIEN TOAN DAM MAY

1.1 Tổng quan về điện toán đám mây

1.1.1 Khái niệm về điện toán dam may

Điện toán đám mây [1] được định nghĩa như là một kiểu tính tốn trong đó tải

ngun có khả năng mở rộng một cách mêm dẻo và thường được ảo hóa một cách tựy Ụ ì 0 ộ :

động được cung cấp như một dịch vụ thơng qua Internet. Điện tốn đám mây trở thành

xu hướng công nghệ quan trọng và nhiều chuyên gia kỳ vọng rằng điện toán đám mây sẽ thay đổi hình dạng cơng nghệ thơng tin, các quy trình và thị trường cơng nghệ thơng tin. Với cơng nghệ điện tốn đám mây, người dùng có thể sử dụng các thiết bị

khác nhau như PC, laptop, smartphones, và PDA dé truy cập các chương trình, kho lưu

trữ, nền tảng phát triển ứng dụng thông qua Internet, thông qua các dịch vụ được cung

câp bởi nhà cung câp điện tốn đám mây.

1.1.2 Kiến trúc hệ thống

Về cơ bản tồn bộ hệ thống có thể phân chia thành các lớp lõi và lớp quản lý. Trong lớp lõi được chia làm 3 phần: Tài nguyên, nền tảng và ứng dụng.

{ Analytical } ( Transactional ) { Interactive }{ Browsing |

Application Capability Components

{ Webserver } | AppServer ) § Reporting | | ESB )

</div>Trang 5<div class="page_container" data-page="5">

1.13 Các mơ hình triển khai

Đám mây được triển khai theo các cách khác nhau, tùy thuộc vào phạm vi sử dụng. Có bốn mơ hình triển khai điện tốn đám mây chính:

- Pam mây công cộng (Public Cloud)- Dam mây riêng tu (Privare Cloud)- Đám mây lai (Hybrid Cloud)

- Dam mây tập thé (Community Cloud)

1.1.4 Cac dich vụ trong điện toán dam mây

- Phan mềm đám mây đóng vai trị dịch vụ (SaaS)

- Cơ sở hạ tầng đám mây đóng vai trị dich vụ (laaS) - Nén tảng đám mây đóng vai trị dịch vụ (PaaS)

1.15 Đặc điểm của điện toán đám mây

Lập lịch [19] là cơ chế cho phép các yêu cầu của người sử dụng được thực thi chính xác nhất, tối ưu nhất theo một tiêu chí nào đó đã được định trước về hiệu năng

như thời gian thực thi nhỏ nhất, thời gian trễ truyền thông nhở nhất và mức độ sử dụng tài nguyên lớn nhất. Tập các tiêu chí được áp dụng để lập lịch cho các yêu cầu, công

việc được quy định sẵn do người quan tri, diéu hanh viéc cung cap dich vụ va được gọi

là các chính sách. Người quản trị sẽ thơng qua các chính sách áp dung dé xác định mục tiêu của ứng dung và từ đó xác định và thực thi thuật tốn lập lịch đối với cơng việc dé dat được yêu cầu đầu ra mong muốn.

Quá trình lập lịch là q trình quyết định sẽ thực thi cơng việc tại một nguồn tài nguyên cụ thé nào và vào thời điểm nao là thích hợp nhất do đó sẽ ảnh hưởng rat lớn đến hiệu năng hoạt động của hệ thống.

</div>Trang 6<div class="page_container" data-page="6">

1.2.2 Các vấn đề trong lập lịch

Lập lịch là vấn đề của các yếu tố ánh xạ từ các tập khác nhau, điều này được chính thức thê hiện như một bộ ba (E, S, O), trong đó:

- E là tập hợp các mẫu, mỗi mẫu trong số đó là một đối tượng của vấn đề.

- _ là tập hợp các giải pháp khả thi cho mỗi mẫu.

- _ Ó là mục tiêu của vấn đề.

Vấn đề lịch có thé được tiếp tục phân loại thành hai loại tùy thuộc vào mục tiêu O: van đề tối wu hóa và van dé quyết định.

Mỗi thuật toán là một tập hợp các hướng dẫn đơn giản cho việc tìm kiếm một giải

pháp cho một vấn đề. Bao gồm ba phần: Đầu vào, phương pháp, đầu ra. Đầu vào là

một tập các tham số cần được xử lý. Phương pháp bao gồm việc mô tả, kiểm soát và

các thủ tục lặp lại dé thực hiện mục tiêu băng cách sử dụng các thông số đầu vào. Đầu ra là kết qua của van dé. Đặc biệt đối với lập lịch, thuật toán là một phương pháp mà nhờ nó những tác vụ được truy cập, ánh xạ, hoặc phân bố cho các bộ vi xử lý. Nói

chung, khơng có thuật tốn lập lịch hồn tồn hồn hảo tồn tại, vì các mục tiêu lập lịch

có thê xung đột với nhau. Một kế hoạch lập lịch tốt thực hiện một sự thỏa hiệp phù

hợp, hoặc là áp dụng kết hợp các thuật toán lập lịch theo các ứng dụng khác nhau.

1.2.3 Kiến trúc lập lịch trong điện toán đám mây

</div>Trang 7<div class="page_container" data-page="7">

1.2 Xu hướng lập lịch hiện nay

Điện toán đám mây chỉ ra nhiều thách thức cho các nhà phát triển hệ thống, dịch

vụ, các kỹ sư, nhà quản trị mạng và nhà cung cấp dịch vụ. Vấn đề lập lịch đang hướng tới một số van đề sau:

- D6 tin cậy, tính bảo mật, tính riêng tư

- _ Chính sách lập lịch và chat lượng dịch vụ

- Su dụng năng lượng hiệu qua

- Quan lý tài nguyên ảo hóa như dữ liệu luồng

- Ứng dụng dịch vụ tăng cường trong mơi trường điện tốn dam mây

1.4 Kết luận chương

Các thuật toán lập lịch trong các hệ thống phân bố đóng góp vai trị trong việc

dàn trải tải trên các bộ xử lý và tối đa hoá sự sử dụng trong khi tối thiểu hoá thời gian

thực thi nhiệm vụ tổng thé. Lap lich nhiém vu dong vai tro chu chốt dé cải thiện các hệ

thống tin cậy và linh hoạt. Mục đích chính là để lập lịch các nhiệm vụ cho các tài nguyên thích ứng phù hợp với thời gian, bao gồm tìm ra một tuần tự hợp lý trong đó các nhiệm vụ có thê được thi hành.

</div>Trang 8<div class="page_container" data-page="8">

CHƯƠNG 2

CÁC THUẬT TỐN LẬP LỊCH TRONG MƠI TRƯỜNG ĐIỆN

TỐN DAM MAY

2.1 Một số thuật toán lập lịch truyền thống

2.1.1 Thuật toán di truyền GA (Genetic Algorithm) ([4], [31], [21])

Đối với giải thuật di truyền, các thơng số của bài tốn tìm kiếm phải được mã

hố thành một chuỗi hữu hạn các ký tự trên một tập hữu hạn các ký tự. Chuỗi này

tương tự như các chuỗi gen của các cơ thé sinh vật. Có rất nhiều cách dé mã hóa tập thơng số. Một cách đơn giản là chúng ta có thê mã hố thành các chuỗi bit trên tập ký

tự {0,1}. Mỗi một chuỗi đại diện cho một điểm tìm kiếm trong khơng gian. GA xuất

phát với một quần thé các chuỗi được khởi tạo một cách ngẫu nhiên sau đó sẽ sản sinh

các quan thé tiếp theo thông qua việc sử dụng lựa chọn ngẫu nhiên như một cơng cụ.

Nhờ đó giải thuật di truyền tìm kiếm trên nhiều điểm song song có khả năng leo lên nhiều cực trị cùng một lúc. Thơng qua các tốn tử của mình, giải thuật trao đơi thơng tin giữa các cực trị với nhau, từ đó làm giảm thiêu khả năng giải thuật kết thúc tại các

cực tri địa phương và bỏ qua mat cực tri toàn cục

</div>Trang 9<div class="page_container" data-page="9">

2.1.2 Thuật toán điều phối FCFS (First Come First Serve)

Trong thuật toán này, độ ưu tiên phục vụ tiến trình căn cứ vào thời điểm hình thành tiến trình. Hàng đợi các tiến trình được tơ chức theo kiểu FIFO. Moi tiến trình

đều được phục vụ theo trình tự xuất hiện cho đến khi kết thúc hoặc bị ngắt.

2.1.3 Thuật toán thời gian thực hiện tối thiểu (Minimum execution time) và thời gian hồn thành tơi thiểu (Minimum Completion Time)

MET (thời gian thực hiện tối thiểu) lập lịch mỗi tác vụ theo thứ tự tùy ý tới máy có thời gian thực hiện tính tốn tối thiêu cho tác vụ này. MET cũng rất đơn giản,

đưa máy tốt nhất tới mỗi công việc nhưng bỏ qua sự sẵn có của máy. MET gây nguy

hiểm cho cân bằng tải ở các máy khác.

MCT (thời gian hoàn thành tối thiểu) lập lịch mỗi tác vụ theo thứ tự tùy ý tới

máy có thời gian hồn thành tối thiểu cho tác vụ này. Tuy nhiên, trong thuật tốn heuristic này, khơng phải tất cả tác vụ đều có thể có thời gian thực hiện tối thiêu

2.1.4 Thuật toán Round Robin [16]

Thuật toán cân bằng tải Round Robin cho phép phân phối các yêu cầu từ client

trên nhiều server. Thuật toán này cải thiện khả năng chịu lỗi của server và thời gian phản hồi đến người sử dụng. Cân bằng tải phân phối các yêu cầu của khách hàng trên nhiều máy chủ dé tối ưu hóa việc sử dụng tài nguyên

2.2 Các tham số đánh giá hiệu năng

-_ Thời gian trung bình tồn cục, thời gian đáp ứng nhanh nhất và nhỏ nhất cho tat

cả người sử dụng.

- Thời gian phân chia theo nhóm người sử dụng, được phân bố trong các vùng

địa lý.

- _ Thời gian xử lý tác vụ của người sử dụng tại các trung tam đữ liệu.

- Xác suất chặn các yêu cầu, xác suất từ chối dịch vụ.

- Mức tiêu thu năng lượng và toản nhiệt của các server vật lý.

- _ Tổng công suất tiêu thụ cho các server trong đám mây gây tiêu tốn đáng ké tới

chi phí kinh doanh.

</div>Trang 10<div class="page_container" data-page="10">

2.3 So sánh hiệu năng các thuật toán lập lịch truyền thống

Thuật toán di truyền GA

Đây là thuật toán tối ưu heristic đang được sử dụng hiện nay. Thuật toán này khơng những tìm ra kết quả chính xác mà cịn tìm ra những kết quả tương tự với độ lệch được giới hạn sẵn (thông qua hàm đột biến). Tuy nhiên thuật tốn khơng đảm bảo

sẽ tìm ra vấn đề trong khơng gian tìm kiếm (đánh giá theo hàm fitness).

Thuật toán điều phối FCES

Ưu điểm: của thuật toán này là giờ CPU khơng bị ngắt và chi phí thực hiện thấp nhất vì khơng thay đổi thứ tự ưu tiên phục vụ (thứ tự của tiễn trình trong hàng đợi).

Nhược điểm: của thuật toán này là thời gian trung bình chờ phục vu của các tiến trình là như nhau (khơng kể tiến trình ngắn hay dai), do đó dẫn đến:

-_ Thời gian chờ trung bình sẽ tăng vơ hạn khi hệ thống tiếp cận tới khả năng phục

vụ của mình.

- Nếu độ phát tán thời gian thực hiện tiến trình tăng thì thời gian chờ trung bình

cũng tăng theo.

- Khi có tiến trình dài, ít bị ngắt thì các tiến trình khác phải chờ đợi lâu hơn.

Thuật tốn thời gian thực hiện tối thiểu (MCT) và thời gian hồn thành tối thiểu

Tuy nhiên, trong các thuật tốn heuristic đơn giản này, khơng phải tất cả tác vụ

đều có thể có thời gian thực hiện tối thiểu và MET gây nguy hiểm cho cân bằng tải ở

các máy khác vì bỏ qua sự sẵn có của máy.

Thuật tốn Round Robin

Uu điểm:

- Cac quá trình sẽ được luân phiên xử lý nên thời gian chờ sé ít.

- Đối với quá trình liên quan tới xuất nhập, IO, người dùng thì rất hiệu quả.

- Viéc cài đặt không qua phức tạp.

Nhược điểm:

- Thoi gian chờ đợi trung bình dưới chính sách Round Robin thường là quá dai.

- _ Nếu thời gian định mức cho việc xử lý quá lớn thi Round Robin thành FIFO.

Nếu thời gian quá ngăn so với thời gian xử lý của một tiến trình trong danh sách hàng

đợi thì việc chờ đợi và xử lý sẽ luân phiên nhiêu lân.

</div>Trang 11<div class="page_container" data-page="11">

=> Các thuật toán lập lịch truyền thống chưa giải quyết được vấn đề hiệu suất sử dụng

và yêu tô hiệu quả năng lượng các server ảo trong mơi trường điện tốn đám mây.

2.4 Các thuật toán lập lịch cho các server ảo nhằm sử dụng hiệu quả năng lượng 2.4.1 Thuật toán cân bằng tải tăng cường tránh tắc nghẽn máy ảo

. User 1 : — User2 „ : Usern `

Hình 2.4. Cấu trúc đám mây trong quá trình cân bằng tải [18]

Thuật toán đề xuất

Bước 1: Trạng thái ban đầu của máy ảo sẽ bằng 0 trong tất cả các máy ảo rỗi.

Cloud Manager trong trung tâm dữ liệu duy trì một cau trúc dit liệu bao gồm

các ID công việc, ID máy ảo và các trạng thái máy ảo.

Bước 2: Khi có một hàng đợi các yêu cầu, Cloud Manager phân tích cau trúc

dữ liệu cho việc phân bó dé xác định máy ảo được sử dụng ít nhất. Nếu sự sẵn có của máy ảo là nhiều hơn thì máy ảo với hop time ít nhất sẽ được xem xét.

Bước 3: Cloud Manager cập nhật các cấu trúc đữ liệu tự động sau khi phân bó. Bước 4: Cloud Manager định kỳ giám sát trạng thái của các máy ảo để phân phối tải, néu một máy ảo quá tải được tìm thấy thì Cloud Manager di chuyền tải

của máy ảo quá tải cho máy ảo có mức tải thâp.

</div>Trang 12<div class="page_container" data-page="12">

- Bước 5: Quyét định lựa chon máy ảo có tải thấp sẽ được dựa trên hop time.

Máy ảo với hop time ít nhất sẽ được xem xét.

- Bude 6: Cloud Manager cập nhật cấu trúc dữ liệu bang cách sửa đổi các mục

dựa trên cơ sở time to time.

- Bước 7: Chu kỳ lặp đi lặp lại từ bước 2.

Trong thuật toán đề xuất Cloud Manager phân tích tính sẵn có của các máy ảo

tại thời điểm các công việc đến để cập nhật cấu trúc dữ liệu do đó có ít tốn kém hơn

trong việc duy trì cấu trúc đữ liệu so với thuật tốn gốc. Từ đó, thuật tốn cân bang tải

đề xuất phải mang lại thời gian phản hồi ít hơn. Như vậy, thời gian phản hồi ít hơn làm

giảm cơng việc bị từ chối và tăng hiệu quả kinh doanh.

2.4.2 Thuật toán cân bằng tải nhận biết năng lượng trong điện toán đám mây (thuật

toán PALB)

Algorithm PALB

for all active compute nodes j € [m] do

if all nị > 75% utilization //all available nodes are activeboot vm on most underutilized n;

Hinh 2.8. Thuat toan PALB [16]

Thuật tốn cân bằng tải PALB có thé được áp dụng cho các bộ điều khiển cụm của một đám mây cục bộ. Tùy thuộc vào kích thước yêu cầu của máy ảo, bộ cân bằng

tải được đặt trên một nút tính tốn đã được câp ngn nêu nút tính tốn đó có các

</div>Trang 13<div class="page_container" data-page="13">

nguồn tài ngun dé lưu trữ. Nếu khơng, một nút tính tốn dang tat sẽ được bật lên dé lưu trữ máy ảo. Trong thuật toán đặc biệt quan tâm đến việc tiết kiệm năng lượng bằng viéc tắt các nút tính tốn khơng được sử dụng. Thuật tốn sẽ duy trì việc sử dụng tất cả các nút tính tốn và phân phối các máy ảo theo cách có năng lượng hiệu quả. Mục tiêu

của thuật tốn này là duy trì tính sẵn có dé tính tốn các nút trong khi giảm tổng công suất được tiêu thụ bởi đám mây.

So sánh thuật toán PALB và Round Robin

Sự khác biệt hiệu năng chính giữa thuật tốn PABL và Round Robin là các nút tính

tốn dang rỗi sẽ sử dụng PALB dé tắt đi. Phương pháp Round Robin có hiệu quả trong

cân bằng tải qua các nút tính tốn sẵn có nhưng nó tiêu thụ một lượng lớn năng lượng

Hình 2.16. So sánh các yêu cầu máy ảo của thuật toán Round Robin

Khi đám mây có năm nút tính tốn và 20 máy ảo cỡ nhỏ được yêu cầu, PALB

tiêu thụ 11% năng lượng được tiêu thụ bởi Round Robin với cùng các thông số. Khi yêu cầu 20 máy ảo cỡ nhỏ trong khi có 20 nút tính tốn sẵn có, PALB chỉ sử dụng

2,8% năng lượng được tiêu thụ bởi Round Robin. Sử dụng các yêu cầu đối với máy ảo

cỡ cực lớn với năm nút tính tốn, PALB chỉ sử dụng 29,5% năng lượng được tiêu thụ

</div>