1

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Nguyễn Ngọc Dung NGHIÊN CỨU 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 Điện tử
Mã số: 60.52.70

Người hướng dẫn khoa học: TS. Lê Nhật Thăng
TÓM TẮT LUẬN VĂN THẠC SĨ
HÀ NỘI - 2012

2

MỞ ĐẦU
Điện toán đám mây hiện nay là xu hướng công nghệ

là một khu vực server ảo có thể cung cấp các tài nguyên
điện toán khác nhau cho khách hàng. Người sử dụng hệ
thống này chỉ cần quan tâm đến dịch vụ điện toán được yêu
cầu. Dữ liệu và các dịch vụ cung cấp đặt tại các trung tâm
dữ liệu và có thể truy cập từ bất cứ một thiết bị nào có nối
mạng trên toàn thế giới.
Đặc điểm của Điện toán đám mây
Điện toán đám mây có nhiều ưu điểm:
- Tự khôi phục. Trong trường hợp lỗi hỏng ứng dụng,
luôn luôn tồn tại một backup nhanh cho ứng dụng, sẵn sàng
hoạt động mà không gây trì trệ
- Khả năng mở rộng tuyến tính. Môi trường đám
mây cho phép người sử dụng truy cập các tài nguyên
điện toán bổ sung theo yêu cầu đáp ứng với tải ứng
dụng ngày càng tăng.
- Hướng dịch vụ. Các hệ thống được xây dựng biệt
lập với các dịch vụ riêng lẻ khác. Nhiều dịch vụ đơn
lẻ độc lập nhau sẽ được phối hợp lại để tạo thành
4

một dịch vụ. Điều này cho phép tái sử dụng các dịch
vụ.
- Hướng SLA. Các dịch vụ điện toán đám mây có
tính chất đảm bảo SLA sao cho khi hệ thống chịu
nhiều tải, nó sẽ tự động điều chỉnh sao cho phù hợp
với các SLA.
- Ảo hóa. Các ứng dụng trong điện toán đám mây
hoàn toàn được tách biệt từ phần cứng tầng dưới.
Môi trường điện toán đám mây là một trường thực
sự ảo hóa. Một lượng lớn các tài nguyên điện toán có

Dịch vụ điện toán đám mây
Mặc dù điện toán đám mây là công nghệ mới, nhưng
đã có nhiều công ty đưa ra các dịch vụ điện toán đám mây.
Các công ty như Amazon, Google, Yahoo, IBM, Microsoft
đều tham gia vào công nghiệp dịch vụ điện toán đám mây.
Amazon là tiên phong với các dịch vụ như EC2 (Elastic
Compute) và S3 (Simple Storage Service).
Các loại đám mây
Các đám mây có thể được phân loại theo phương thức
quản lý và sở hữu, ta có thể phân ra thành Public Clouds,
Private Clouds, Hybrid Clouds và Community Clouds

6
Hình 1. Các loại đám mây
Các mô hình dịch vụ điện toán đám mây
Cơ sở hạ tầng đám mây đóng vai trò dịch vụ (IaaS)
Các khả năng được cung cấp đến khách hàng là việc
cung cấp sự xử lý, lưu trữ, các mạng lưới, và các tài nguyên
điện toán cơ bản trong đó khách hàng có thể triển khai và
chạy phần mềm, có thể bao gồm các hệ thống và các ứng
dụng. Khách hàng không quản lý hoặc điều khiển cơ sở hạ

trên cơ sở hạ tầng đám mây các ứng dụng khách hàng có
hoặc khách hàng tạo nên sử dụng các ngôn ngữ lập trình và
các công cụ hỗ trợ bởi nhà cung cấp. Khách hàng không
quản lý hay điều khiển cơ sở hạ tầng tầng dưới bao gồm
mạng, server, hệ thống vận hành, lưu trữ hoặc thậm chí các
khả năng ứng dụng đơn lẻ,…
Lập lịch
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ể. Lập lịch nhiệm vụ đóng vai trò chủ
chốt để 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.
8

CHƯƠNG II. CÁC THUẬT TOÁN LẬP LỊCH
Một số thuật toán lập lịch truyền thống
Genetic Algorithm - Thuật toán di truyền
Các thuật toán Genetic là các kỹ thuật phân bố dựa
trên cơ chế chọn lựa tự nhiên và di truyền học. Các thuật
toán di truyền là một phân loại cụ thể của thuật toán tiến hoá
có mục đích tìm ra phương án để tối ưu hoá vấn đề, chúng
được mã hoá theo chuỗi nhị phân và sử dụng tính đột biến
hoặc trao đổi đoạn để chỉnh sửa mật độ qua các thế hệ.
Trong toán học, vấn đề tối ưu hoá tìm kiếm để tối thiểu hoá
hoặc tối đa hoá một chức năng bằng cách chọn các giá trị
thích hợp cho các biến số. Các thuật toán di truyền bắt
nguồn từ khảo sát sự tiến hoá sinh học và dựa trên các hoạt

double r = Math.random();
if (r <neighbor.getValue()) {
output.collect (new IntWritable (neighbor.getKey()), individual);
}
}
return migrated;
}
Thuật toán 2: GAReducer
public void reduce(IntWritable deme_id, Interator<Chromosome> values,

outputCollector<Intwritable, Chromosome> output,
Reporter reporter)
throws I0Exception {
deme= demeParser.getDeme (deme_id.get());
demePopulation.clear();
matingPool.clear();
while (values.hasNext()) {
demePopulation.add(value.next()) ;
}
10

selection();
crossover();
mutation();
for (Chromosome offspring : matingPool)
output.collect(deme_id, offspring);
}
Các thuật toán MCT (Thời gian hoàn thành sớm nhất) và
MET (Thời gian thực thi sớm nhất)
Có hai loại phương thức sắp xếp, immediate mode và


=
∑





trong
đó n là số máy ảo chạy trên host.
Từ HL
i
, giá trị tải trung bình avgl và giá trị đánh giá
cân bằng tải B của môi trường điện toán đám mây có thể
định nghĩa như sau:


=
∑









(3.1)



,…,ℎ

}
và xếp theo thứ tự từ dưới lên
theo công suất xử lý.
Bước 2. Theo mô hình nhiệm vụ, tạo tập nhiệm vụ  =
{


,

,…,

}
. Trong quá trình này, bộ lập lịch mức thứ
nhất tạo mô tả máy ảo theo các đặc tính của nhiệm vụ, cung
cấp thông tin cấu hình cho việc gán tài nguyên và tạo máy
ảo.
Bước 3. Theo mô tả máy ảo của Nhiệm vụ 

∈ , chọn một
tài nguyên host h
j
có thể đạt được tài nguyên yêu cầu và tải
là nhỏ nhất. Nếu host tồn tại, tạo máy ảo và gán tài nguyên
yêu cầu cho nó, sau đó cập nhật tài nguyên khả dụng hFcap
của Host h
j
, nếu không nhiệm vụ t

dẫn đến tải của máy ảo nặng gây mất cân bằng tải, thì hoạt
động di chuyển động được sử dụng, giữ cân bằng tải trong
môi trường hiện tại.

Hình 2. Sự sử dụng tài nguyên
Lập lịch nhiệm vụ trong điện toán đám mây dựa
trên thuật toán GA cải tiến
Phần này sẽ nghiên cứu thuật toán lập lịch GA cải
tiến, trong đó các phương pháp lập lịch Min-Min và Max-
Min được sát nhập trong một thuật toán GA tiêu chuẩn. Các
kỹ thuật Min-Min, Max-Min và Genetic được phân tích
14

trong hiệu năng cuối cùng của thuật toán GA tiêu chuẩn và
có sự so sánh với GA cải tiến.
M
0

M
1

M
2
M
3

T
0

200 250 220 300

d. Chọn cá thể cho thế hệ tiếp theo;
5. End
Thuật toán di truyền cải tiến
1. Begin
2. Tìm phương thức bởi Min-Min và Max-Min
3. Tạo quần thể từ kết quả bước 2
4. Đánh giá mỗi ứng viên
15

5. Lặp lại cho đến (điều kiện hoàn thành)
a. Chọn bố mẹ
b. Phối hợp lại các đôi bố mẹ
c. Đánh giá ứng viên mới
d. Chọn cá thể cho thế hệ tiếp theo;
6. End
Mô phỏng và kết quả
Chúng ta sử dụng bộ công cụ mô phỏng Cloudsim để
kiểm tra hiệu năng của thuật toán cải tiến và thuật toán di
truyền tiêu chuẩn. Chúng ta xem các Máy ảo là tài nguyên
và các đám mây Cloudlet là nhiệm vụ/công việc. Trong
trường hợp thứ nhất ta cố định số máy ảo và thay đổi số
cloudlet, trong trường hợp thứ hai ta cố định số cloudlet và
thay đổi số máy ảo. Makespan mà thuật toán đưa ra được chỉ
ra trong bảng.
Trong trường hợp thứ nhất, chúng ta cố định số máy
ảo là 10 và thay đổi số cloudlet từ 10 đến 40 với độ chênh
lệch là 10. Chúng ta chạy mỗi thuật toán 10 lần.
Bảng 2. Cố định máy ảo và thay đổi Cloudlet
Số máy
ảo: 10

Số
cloudlet:
10
Biến đổi số máy ảo
10 20 30 40
Phương
thức sử
dụng
Thuật
toán cải
tiến
113.5 33.2 17.1 10
Thuật
toán tiêu
chuẩn
146.8 84.7 54 44.8
Biểu đồ hiệu năng:

Hình 3.5 Biểu đồ makespan cho trường hợp cố
định Cloudlet
Các mô hình lập lịch cho IaaS theo yêu cầu
18

Xét một server farm với L server vật lý. Mỗi host vật
lý có tài nguyên (C
l
, M
l
), l=1,…,L trong đó C
l


.
Ta định nghĩa 

, = 1,…, là tốc độ đến của khách hàng
những người yêu cầu các máy ảo loại n với thời gian chờ
phân bố theo hàm mũ 1/

.
Gọi 
,
(

)
, = 1,…,, =1,…, là số máy ảo loại n
được cấp cho các khách hàng trên một server vật lý l tại thời
điểm t. Chúng ta có thể viết công thức liên quan đến giới
hạn tài nguyên của một server  ∈
{
1,…,
}
như sau:



,














≤


(3.6)

Hệ thống được mô tả bởi chuỗi Markov thời gian liên
tục Υ =

X

(
t
)
,…,X

(
t
)

trong đó X
l


(
t
)
,…,X

(
t
)

và X
l
(t) = (X
l,1
(t),…,X
l,N
(t))
Xác suất trạng thái ổn định được định nghĩa là:



=
lim

→
∞
Pr

(


=



,

,
…
,


,

−
1
,
…
,


,



,




;

=
1
,
…
,


Có hai loại chuyển tiếp giữa các trạng thái của chuỗi
Markov Υ: loại chuyển tiếp đầu tiên là do việc đến của các
yêu cầu và khi có một yêu cầu cụ thể đến, quyết định gán
20

yêu cầu cho máy m phụ thuộc vào mô hình gán cụ thể, do
đó, việc gán này tạo ra một chuyển tiếp.
Sự đến của một máy ảo loại n khi hệ thống ở trạng thái
 ∈ Θ tương ứng với sự chuyển tiếp từ trạng thái
(x
1
,…,x
l
,…,x
L
) sang trạng thái (

,…,
,





, = 1,…, khi mô hình dung
lượng tự do nhiều nhất (MF) được áp dụng.
Chú ý rằng l là chỉ số lớn nhất trong trường hợp có nhiều
server có cùng dung ượng CPU free lớn nhất bằng 

−
∑

,





- Nếu (
1
,…,
,
+
,…,

) ∈ Θ và 

−
∑

,

- Nếu (
1
,…,
,
+
,…,

) ∈ Θ và


,…,
,

,…,

 ∉ Θ∀ =  + 1,…,
21

Một khách hàng gán một máy ảo loại n, 1 ≤  ≤  trong
host l, 1 ≤  ≤ 
Bỏ qua việc sử dụng VM tương ứng với sự chuyển tiếp từ
trạng thái (x
1
,…,x
l
,…,x
L
)∈ Θ sang trạng thái
(





=




∈



Trong đó tập con  của Θ bao gồm các trạng thái sao
cho không có sự cấp phát máy ảo loại k đang đến nào là có
thể xảy ra.

22
a b c d
Hình 3.7 Minh hoạ một server farm với 6 server,


= .; 

= .

điện toán đám mây. Bằng cách sử dụng kỹ thuật ảo hóa, tất
cả các tài nguyên vật lý được ảo hóa và trong suốt đối với
người sử dụng. Luận văn đã thực hiện tìm hiểu một số thuật
24

toán lập lịch truyền thống như GA, FCFS và nghiên cứu các
thuật toán mới như GA cải tiến, thuật toán dựa trên cân bằng
tải… và đưa ra những so sánh, nhận xét qua mô phỏng thực
tế.
Tôi xin gửi lời chân thành cảm ơn đến TS. Lê
Nhật Thăng đã tận tình giúp đỡ tôi thực hiện luận văn
này. Do có sự hạn chế về thời gian nên bản luận văn
không tránh khỏi những thiếu sót. Tôi rất mong nhận
được sự góp ý của các thầy cô và các bạn.