Giải pháp nâng cao hiệu quả của giản đồ lập lịch dựa trên độ tin cậy trong các hệ thống tính toán tình nguyện

BỘ GIÁO DỤC VÀ ĐÀO TẠO

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

---------------------------------------

LUẬN VĂN THẠC SĨ KHOA HỌC

GIẢI PHÁP NÂNG CAO HIỆU QUẢ CỦA GIẢN ĐỒ

LẬP LỊCH DỰA TRÊN ĐỘ TIN CẬY TRONG CÁC

HỆ THỐNG TÍNH TOÁN TÌNH NGUYỆN

NGÀNH: CÔNG NGHỆ THÔNG TIN

MÃ SỐ: ………………………………

Nguyễn Quang Hòa

Người hướng dẫn khoa học: TS. NGÔ HỒNG SƠN

Hà Nội – 2008

1

Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008

LỜI CAM ĐOAN

Tôi xin cam đoan bản Luận văn này là công trình nghiên cứu của riêng tôi.

Các dữ liệu và kết quả nêu trong Luận văn là hoàn toàn trung thực và có nguồn gốc

rõ ràng.

TÁC GIẢ

(Ký tên)

2

Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008

Chương 1.

LỜI CẢM ƠN

Trước hết, tôi xin được chân thành cảm ơn TS. Ngô Hồng Sơn đã tận tình

hướng dẫn, cung cấp tài liệu và kiến thức cần thiết giúp tôi hoàn thành Luận văn tốt

nghiệp này.

Tôi xin bày tỏ lòng biết ơn sâu sắc tới các thầy, cô giáo trong Khoa Công

nghệ thông tin cũng như các thầy, cô giáo trong trường Đại học Bách Khoa Hà Nội

đã truyền đạt cho tôi những kiến thức quan trọng trong suốt thời gian tôi học tập và

nghiên cứu tại trường.

Cuối cùng, tôi xin được nói lời cảm ơn đến gia đình và bạn bè, những người

luôn ở bên tôi, cổ vũ và động viên tôi trong suốt thời gian học tập và làm luận văn

tốt nghiệp.

Trong quá trình hoàn thành luận văn, do còn thiếu kinh nghiệm, sự ràng buộc

về thời gian và sự hạn chế về kiến thức nên chắc chắn không tránh khỏi những thiếu

sót. Vì vậy tôi rất mong nhận được sự đóng góp ý kiến và giúp đỡ của các thầy, các

cô và các bạn.

Hà Nội, ngày 20 tháng 11 năm 2008

Người thực hiện luận văn

3

Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008

MỤC LỤC

LỜI CAM ĐOAN .......................................................................................................1

LỜI CẢM ƠN .............................................................................................................2

MỤC LỤC...................................................................................................................3

DANH MỤC CÁC HÌNH VẼ VÀ ĐỒ THỊ ...............................................................5

MỞ ĐẦU.....................................................................................................................6

Chương 1. TỔNG QUAN .....................................................................................8

1.1 Tính toán lưới ................................................................................................8

1.2 Tính toán ngang hàng ..................................................................................12

1.3 Tính toán tình nguyện..................................................................................14

1.3.1 Khái niệm..............................................................................................14

1.3.2 BOINC ..................................................................................................15

1.3.2.1 Khái niệm.......................................................................................15

1.3.2.2 Các đặc trưng cơ bản của BOINC [23]..........................................16

1.3.2.3 Kiến trúc BOINC ...........................................................................18

1.3.3 Lập lịch trong tính toán tình nguyện.....................................................19

1.3.3.1 Lập lịch phía máy trạm ..................................................................20

1.3.3.2 Lập lịch phía máy chủ....................................................................20

1.3.3.3 Lập lịch chịu lỗi dựa trên độ tin cậy ..............................................21

1.3.4 So sánh với tính toán lưới và tính toán ngang hàng .............................23

1.3.4.1 Tính toán lưới.................................................................................23

1.3.4.2 Tính toán ngang hàng.....................................................................23

Chương 2. LÝ THUYẾT CƠ BẢN VỀ LẬP LỊCH DỰA TRÊN ĐỘ TIN CẬY

25

2.1 Mô hình cơ bản và các giả định...................................................................25

4

Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008

2.2 Các kĩ thuật chịu lỗi truyền thống. ..............................................................28

2.2.1 Biểu quyết theo số đông........................................................................29

2.2.2 Kiểm tra điểm .......................................................................................30

2.2.2.1 Kiểm tra điểm dùng danh sách đen................................................31

2.2.2.2 Kiểm tra điểm không dùng danh sách đen.....................................32

2.3 Chịu lỗi dựa trên độ tin cậy .........................................................................33

2.3.1 Tổng quan .............................................................................................33

2.3.2 Tính toán độ tin cậy ..............................................................................35

2.3.3 Ứng dụng sự tin cậy..............................................................................36

2.3.3.1 Kết hợp biểu quyết và kiểm tra điểm.............................................36

2.3.3.2 Kiểm tra điểm bằng biểu quyết......................................................37

2.4 Khảo sát một số giản đồ lập lịch. ................................................................38

2.4.1 Lập lịch Round Robin...........................................................................39

2.4.2 Lập lịch Round Robin dựa trên sự ưu tiên về khả năng tính toán ........41

Chương 3. GIẢN ĐỒ LẬP LỊCH ROUND ROBIN DỰA TRÊN ĐỘ TIN CẬY

44

3.1 Giản đồ lập lịch Round Robin dựa trên sự ưu tiên về độ tin cậy ................44

3.2 Giản đồ lập lịch Round Robin dựa trên kiểm thử độ tin cậy.......................55

Chương 4. KẾT QUẢ THỰC NGHIỆM ............................................................65

4.1 Chương trình mô phỏng...............................................................................65

4.2 Kịch bản mô phỏng......................................................................................65

4.3 Kết quả.........................................................................................................66

Chương 5. KẾT LUẬN .......................................................................................72

5.1 Những kết quả đạt được...............................................................................72

5.2 Những công việc chưa làm được.................................................................72

5

Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008

5.3 Hướng phát triển trong tương lai.................................................................73

TÀI LIỆU THAM KHẢO.........................................................................................74

DANH MỤC CÁC HÌNH VẼ VÀ ĐỒ THỊ

Hình 1-1. Minh họa về tính toán lưới..........................................................................9

Hình 1-2. Tổ chức ảo.................................................................................................11

Hình 1-3. Mô hình mạng ngang hàng .......................................................................12

Hình 1-4. Mô hình tính toán tình nguyện..................................................................15

Hình 1-5. Mô hình cơ bản của BOINC .....................................................................16

Hình 1-6. Kiến trúc BOINC......................................................................................18

Hình 1-7. Sự tương tác giữa máy trạm và máy chủ ..................................................19

Hình 2-1. Mô hình chủ khách ...................................................................................26

Hình 2-2. Hàng đợi công việc lập lịch tham lam với biểu quyết m đầu tiên ............28

Hình 2-3. Tỉ lệ lỗi của biểu quyết số đông với nhiều các giá trị m và f [8] ..............30

Hình 2-4. Hàng đợi công việc lập lịch tham lam nâng cao độ tin cậy [8] ................33

Hình 3-1. Mô tả hệ thống tính toán tình nguyện.......................................................45

Hình 3-2. Sơ đồ hình vẽ các bước của giản đồ lập lịch Round Robin dựa trên sự ưu

tiên về độ tin cậy .......................................................................................................46

Hình 3-3. Sơ đồ hình vẽ các bước của giản đồ lập lịch kiểm thử dựa trên độ tin cậy

...................................................................................................................................57

Hình 4-1. Biểu đồ so sánh sự chậm chễ của các giản đồ lập lịch với s= 0.25,N >P67

Hình 4-2. Biểu đồ so sánh sự chậm chễ của các giản đồ lập lịch với s= 0.5,N >P..68

Hình 4-3 Biểu đồ so sánh sự chậm chễ của các giản đồ lập lịch với s= 0.75,N >P.68

Hình 4-4. Biểu đồ so sánh sự chậm chễ của các giản đồ lập lịch với s= 1,N >P.....69

Hình 4-5. Biểu đồ so sánh sự chậm chễ của các giản đồ lập lịch với s= 0.25,N< P69

Hình 4-6. Biểu đồ so sánh sự chậm chễ của các giản đồ lập lịch với s= 0.5,N< P..70

Hình 4-7. Biểu đồ so sánh sự chậm chễ của các giản đồ lập lịch với s= 0.75,N< P70

Hình 4-8. Biểu đồ so sánh sự chậm chễ của các giản đồ lập lịch với s= 1,N< P.....71

6

Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008

MỞ ĐẦU

Tính toán tình nguyện là một mô hình tính toán song song hấp dẫn để xây dựng lên

các hệ thống tính toán có phạm vi rộng lớn từ số lượng lớn các máy tính tình

nguyện trên mạng. Trong những năm gần đây, đã có sự quan tâm tăng lên và nhanh

chóng trong các hệ thống tính toán tình nguyện. Hệ thống tính toán tình nguyện cho

phép người sử dụng từ bất cứ nơi nào trên mạng, đóng góp thời gian tính toán nhàn

rỗi của máy tính để hướng vào giải quyết các bài toán có thời gian tính toán lớn.

Tính toán tình nguyện giúp cho có thể xây dựng các mạng tính toán toàn cầu lớn rất

nhanh, điều này được chứng mình bởi sự thành công của dự án SETI@home[2], dự

án này đang triển khai hàng trăm nghìn máy tính tình nguyện để tìm kiếm số lượng

lớn dữ liệu đàm thoại radio cho tín hiệu của sự sống bên ngoài trái đất,

Einstein@Home [6] tìm kiếm các sao neutron xoay rất nhanh dùng dữ liệu từ các

nhà dò tìm sóng hấp dẫn LIGO và GEO hay Climateprediction.net@Home [7] dùng

để dự đoán khí hậu trên trái đất …

Trong hệ thống tính toán tình nguyện, khả năng chịu đựng lỗi là một vấn đề quan

trọng bởi vì có thể có nhiều những người dùng ác ý trên mạng phá hoại hệ thống

bằng việc cố ý đệ trình các kết quả sai. Để giải quyết yêu cầu đưa ra kết quả tốt

trong hệ thống tính toán tình nguyện mà có người dùng ác ý tham gia thì hệ thống

lập lịch tại máy chủ phải thực thi các chính sách lập lịch chịu lỗi. Do đó trong luận

văn này, tôi quan tâm đến vấn đề lập lịch nhiệm vụ phía máy chủ của hệ thống tính

toán tình nguyện thực thi các kĩ thuật chịu đựng lỗi. Mặc dù một số kĩ thuật chịu lỗi

đang tồn tại như là biểu quyết theo số đông, kiểm tra điểm, kết hợp biểu quyêt và

kiểm tra điểm, kiêm tra điểm bằng biểu quyết [8], hay giản đồ lập lịch Round Robin

dựa trên sự ưu tiên về khả năng tính toán [10] có thể đảm bảo các yêu cầu về độ tin

cậy cho các kết quả tính toán, tuy nhiên, các kĩ thuật này luôn luôn là nguyên nhân

làm cho hiệu năng giảm đi trong giới hạn của toàn bộ thời gian tính toán. Trong

luận văn này tôi đề xuất hai kĩ thuật lập lịch hiệu quả cho máy chủ được gọi là lập

lịch Round Robin dựa trên sự ưu tiên về độ tin cậy và lập lịch Round Robin dựa

trên kiểm thử độ tin cậy nhằm nâng cao hiệu quả của giản đồ lập lịch dựa trên độ tin