Tài liệu Luận văn 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...
76 trang |
Chia sẻ: hunglv | Lượt xem: 1190 | Lượt tải: 0
Bạn đang xem trước 20 trang mẫu tài liệu Luận văn 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, để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trê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
7
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
cậy trong các hệ thống tính toán tình nguyện. Các kĩ thuật này đều đưa ra các tiêu
chí để chọn một máy trạm phù hợp nhất để thực thi một nhiệm vụ. Kĩ thuật đầu tiên
quan tâm đến chọn một máy trạm đang có khả năng có độ tin cậy cao nhất và khả
năng thực hiện tốt nhất. Kĩ thuật thứ hai thì chọn máy trạm sao cho khi nhiệm vụ
được thực hiện bởi nó thì độ tin cậy của nhiệm vụ sẽ tăng lên, Bằng việc sử dụng bộ
mô phỏng VCSIM để thực hiện mô phỏng các thuật toán lập lịch, tôi đã chỉ ra rằng
kĩ thuật được đưa ra có thể giúp giảm bớt thời gian thực thi của toàn bộ hệ thống so
với kĩ thuật lập lịch Round Robin tương ứng.
Phần còn lại của luận văn này được tổ chức như sau:
• Chương 1. Giới thiệu tổng quan: Trình bày về các hệ thống tính toán phân
tán, tính toán lưới, tính toán ngang hàng, tính toán tình nguyện, BOINC, và
khảo sát qua các thuật toán lập lịch trong tính toán tình nguyện.
• Chương 2. Lý thuyết cơ bản lập lịch dựa trên độ tin: Trình bày về các mô
hình cơ bản của hệ thống và các giả định, các kĩ thuật chịu lỗi chuyền thống,
chịu lỗi dựa trên độ tin cậy và khảo sát một số giản đồ lập lịch chịu lỗi dựa
trên độ tin cậy.
• Chương 3. Giản đồ lập lịch dựa trên độ tin cậy: Mô tả các đề xuất của chúng
tôi về giản đồ lập lịch dựa trên độ tin cậy.
• Chương 4. Kết quả thực nghiệm: Giới thiệu kịch bản mô phỏng và thảo luận
về các kết quả mô phỏng.
• Chương 5. Kết luận: Tóm tắt lại những công việc đã đạt được, những công
việc chưa làm được và hướng phát triển trong tương lai.
8
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Chương 1. TỔNG QUAN
Ngày nay, với sự phát triển vượt bậc của khoa học kỹ thuật và công nghệ, đã xuất
hiện những bài toán trong nhiều lĩnh vực đòi hỏi sức mạnh tính toán mà một máy
tính riêng lẻ không thể đảm trách. Xuất phát từ những nhu cầu đó, các kỹ thuật tính
toán song song, tính toán phân tán đã được đề xuất và đã phần nào đáp ứng được
các yêu cầu này. Tuy nhiên, tham vọng của con người không dừng lại ở đó. Họ
muốn một sức mạnh tính toán lớn hơn, với khả năng chia sẻ tài nguyên giữa mọi
người trên phạm vi toàn cầu, khả năng tận dụng các phần mềm cũng như tài nguyên
vật lý phân tán cả về mặt địa lý. Các tổ chức giải quyết vấn đề này bằng hai cách:
• Đầu tư thêm trang thiết bị, cơ sở hạ tầng tính toán (mua thêm máy chủ, máy
trạm, siêu máy tính, cluster...). Tuy nhiên cách làm này hết sức tốn kém.
• Có một cách làm khác hiệu quả hơn đó là phân bố lại hợp lý các nguồn tài
nguyên trong tổ chức hoặc thuê thêm các nguồn tài nguyên từ bên ngoài (tất
nhiên là với chi phí rẻ hơn nhiều so với việc đầu tư cho cơ sở hạ tầng tính toán).
Thực tế cho thấy có một phần lớn các nguồn tài nguyên của chúng ta đang được sử
dụng lãng phí: các máy để bàn công sở thường chỉ hoạt động khoảng 5% công suất,
ngay cả các máy chủ cũng có thể chỉ phải hoạt động với 20% công suất. Việc tận
dụng hiệu quả các nguồn tài nguyên này có thể mang lại một sức mạnh tính toán
khổng lồ. Cách giải quyết thứ hai này chính là mục tiêu của tính toán lưới và tính
toán tình nguyện.
1.1 Tính toán lưới
Tính toán lưới hướng đến việc chia sẻ và sử dụng hiệu quả các nguồn tài nguyên
thuộc về nhiều tổ chức trên một quy mô rộng lớn (thậm chí là quy mô toàn cầu).
Chính các công nghệ mạng và truyền thông phát triển mạnh mẽ trong những năm
qua đã biến những khả năng này dần trở thành hiện thực. Các nghiên cứu về tính
toán lưới đã và đang được tiến hành là nhằm tạo ra một cơ sở hạ tầng lưới cho phép
dễ dàng chia sẻ và quản lý các tài nguyên đa dạng và phân tán trong môi trường
9
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
lưới. Như vậy, tính toán lưới, hiểu một cách đơn giản là một dạng của tính toán
phân tán. Mục đích là tạo ra một máy tính ảo lớn mạnh từ một tập lớn các hệ thống
không đồng nhất nhằm nâng cao khả năng tính toán, chia sẻ các tài nguyên khác
nhau.
Một ví dụ về dự án tính toán lưới là dự án Avian Flu Grid[24], dự án này nhằm sử
dụng lưới PRAGMA[25] và các cơ sở hạ tầng tính toán hiệu năng cao để phát triển
một mô hình cho hợp tác toàn cầu đấu tranh chống lại sự đe dọa dịch lớn của cúm
avian và các bệnh dịch lây nhiễm nghiêm trọng khác. Hệ thống lưới PRAGMA, mà
trung tâm HPCC-HUT (Trung tâm tính toán hiệu năng cao của trường Đại Học
Bách Khoa Hà Nội) là một thành viên, được tạo ra nhằm duy trì các hoạt động cộng
tác và thúc đẩy sử dụng các kĩ thuật lưới trong các ứng dụng khoa học tiên tiến giữa
các viện hàng đầu trong các nước có đường biên giới nằm trên biển thái bình
dương.
Hình 1-1. Minh họa về tính toán lưới
Hình 1-1 là một ví dụ về lưới, như một mạng liên kết các tài nguyên phân tán về
mặt địa lý, các tài nguyên rất phong phú, đa dạng, bao gồm tập các siêu máy tính,
các thiết bị truyền thông vệ tinh, các kho lưu trữ, các cluster tính toán hiệu năng cao
10
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
, các tổ chức ảo liên kết trong lưới. Người dùng trong lưới cũng hết sức đa dạng, từ
các người dùng thông thường, cho tới các người dùng chuyên dụng, có kiến thức
sâu về chuyên môn như các nhà nghiên cứu, các nhà khoa học... Và lưới chính là sự
tập hợp, chia sẻ, chọn lựa các nguồn tài nguyên này thông qua một chính sách thống
nhất, phân phối các siêu máy tính và các hệ cluster để đạt hiệu năng tốt hơn.
Các thách thức mà công nghệ tính toán lưới đang phải giải quyết bao gồm:
• Các tài nguyên hết sức đa dạng, không đồng nhất. Tài nguyên ở đây được hiểu
theo nghĩa hết sức tổng quát. Đó có thể là các tài nguyên phần cứng: tài nguyên
tính toán, tài nguyên lưu trữ, các thiết bị đặc biệt khác...; các tài nguyên phần
mềm: các CSDL, các phần mềm đặc biệt và đắt giá...; các đường truyền mạng...
Các tài nguyên này có thể rất khác nhau về mặt kiến trúc, giao diện, khả năng xử
lý... Việc tạo ra một giao diện thống nhất cho phép khai thác và sử dụng hiệu
quả các nguồn tài nguyên này là hoàn toàn không dễ dàng. Ban đầu tính toán
lưới được đặt ra chủ yếu là để tận dụng các nguồn tài nguyên tính toán nhưng
hiện nay mục tiêu của nó đã được mở rộng sang rất nhiều nguồn tài nguyên khác
như đã kể trên.
• Các tài nguyên không chỉ thuộc về một tổ chức mà thuộc về rất nhiều tổ chức
tham gia lưới. Các tổ chức phải tuân thủ một số quy định chung khi tham gia
vào lưới còn nhìn chung là hoạt động độc lập tức là các tài nguyên này đều có
quyền tự trị. Các tổ chức khác nhau thường có chính sách sử dụng hay cho thuê
tài nguyên của họ khác nhau và do vậy cũng gây khó khăn cho việc quản lý.
• Các tài nguyên phân tán rộng khắp về mặt địa lý do vậy phải có các cơ chế quản
lý phân tán.
• Đảm bảo an toàn thông tin cho một môi trường phức tạp như môi trường lưới là
rất khó khăn trong khi đây là một trong những điểm ưu tiên hàng đầu.
Theo Ian Foster, một hệ thống lưới là hệ thống có 3 đặc điểm chính sau:
• Phối hợp các tài nguyên phân tán từ nhiều miền quản trị khác nhau.
• Sử dụng các giao diện và giao thức chuẩn mở.
• Mang lại cho người dùng chất lượng dịch vụ không tầm thường.
11
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Riêng điểm thứ 2 là một điểm rất đáng lưu ý. Vì lưới là một môi trường thu hút
nhiều tổ chức tham gia nên không thể coi nhẹ vai trò của các chuẩn mở và các giao
thức mở, cũng giống như việc sử dụng các chuẩn này đã giúp cho mạng Internet
bùng nổ mạnh mẽ trong những năm 90 của thế kỉ trước.
Khái niệm tổ chức ảo cũng là một khái niệm rất quan trọng trong tính toán lưới. Tổ
chức ảo là một tổ chức được lập ra động để giải quyết một vấn đề nào đó. Thành
phần của tổ chức ảo bao gồm rất nhiều tài nguyên thuộc về nhiều tổ chức (thực)
khác nhau trong môi trường lưới và cùng hoạt động vì một mục tiêu chung. Tùy
theo mức độ của vấn đề cần giải quyết mà các tổ chức ảo có thể rất khác nhau về
quy mô, phạm vi hoạt động, thời gian sống. Hình 1.2 dưới đây là một minh họa về
tổ chức ảo. Có một người dùng cần giải một bài toán lớn về dự báo thời tiết, anh ta
thành lập l tổ chức ảo bằng cách thuê một số nguồn tài nguyên khác nhau từ một vài
tổ chức khác nhau. Tương tự như vậy, một người dùng cần giải một bài toán về dự
báo tài chính, anh ta cũng thành lập một tổ chức ảo để giải quyết bài toán này.
Hình 1-2. Tổ chức ảo
12
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
1.2 Tính toán ngang hàng
Mạng ngang hàng là một mô hình truyền thông ở đó mọi nút trong mạng thực hiện
giống nhau. Đối nghịch với mô hình chủ khác, ở đây một nút cung cấp các dịch vụ
và các nút khác sử dụng các dịch vụ.
Hình 1-3. Mô hình mạng ngang hàng
Tính toán ngang hàng là một dạng của tính toán phân tán, nó bao gồm một số lớn
các nút tịnh toán tự trị (các máy ngang hàng) hoạt động chia sẻ tài nguyên và các
dịch vụ [2]. Tính toán ngang hàng là chia sẻ các tài nguyên và các dịch vụ bằng điều
hướng chuyển đổi giữa các hệ thống. Những tài nguyên và dịch vụ này bao gồm
chuyển đổi thông tin, các chu kì xử lý, lưu trữ đệm, và lưu trữ trên đĩa cho các file.
Tính toán ngang hàng sử dụng tốt sức mạnh tính toán của các máy tính để bàn đang
tồn tại và kết nối mạng. Các máy ngang hàng có trách nhiệm như nhau đồng thời có
các chức năng vừa là máy chủ vừa là máy khách cho dịch vụ và chia xẻ tài nguyên.
Lợi ích của việc sử dụng tính toán ngang hàng là: Giảm cân bằng tải trên các máy
chủ, cho phép các máy chủ thực thi các dịch vụ đặc biệt hiệu quả hơn, có thể giảm
các yêu cầu cho các tổ chức IT để tăng các phần cơ sở hạ tằng của họ để hỗ trợ các
dịch vụ như là lưu trữ sao lưu, tạo ra sức mạng tính toán không tốn nhiều chi phí,
băng thông, lưu trữ …
Một số thuận lợi của tính toán ngang hàng đó là không có điểm trung tâm lỗi, khả
năng mở rộng lớn vì mọi máy ngang hàng là giống nhau do đó có thể thêm nhiều
máy ngang hàng đến hệ thống. Điểm không thận lợi của tính toán ngang hàng chính
là sự điều phối không tập trung, tất cả các nút được tạo ra là không giống nhau về
sức mạng tính toán, băng thông …
13
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Trong tính toán ngang hàng, các ứng dụng được phân tách vào ba loại chính đó là:
• Tính toán phân tán
• Chia sẻ file
• Các ứng dụng cộng tác
Ba loại này phục vụ các mục đích khác nhau và vì vậy chúng có các yêu cầu phát
triển riêng. Các ứng dụng tính toán phân tán thường yêu cầu phân tích vấn đề lớn
vào các vấn đề song song nhỏ, các ứng dụng chia sẻ file yêu cầu tìm kiếm hiệu quả
theo các mạng diện rộng và các ứng dụng cộng tác yêu cầu cập nhập các kĩ thuật để
cung cấp tính nhất quán trong môi trường đa người dung.
Các ứng dụng phổ biến nhất trong tính toán ngang hàng [22] là chia sẻ nội dung và
file điển hình như là Napster, Gnutella, Mojo Nation, eDonkey and Freenet. Napster
là hệ thống lớn đầu tiên có thể trao đổi hướng và chia sẻ nội dung. Trong khi sự trao
đổi nội dung thực tế trong Napster là giữa các máy tính ngang hàng thì việc khám
phá các máy tính ngang hàng vẫn tập trung (như lưu trữ trong thư mục trung tâm).
Gnutella cung cấp một giải pháp chia sẻ file phân tán rõ ràng không sử dụng nút
trung tâm. Hạn chế của Gentella không phải là một ứng dụng mà là một giao thức
dùng để tìm kiếm và chia sẻ file. Để tìm nội dung và một máy ngang hàng khác một
người dùng phải biết địa chỉ IP của ít nhất một nút Gnutella khác. Một nút sẽ đưa ra
một câu truy vấn cho một file bằng việc gửi nó đến tất cả các nút khác nó biết. Nếu
một nút không phục vụ được yêu cầu nó có thể truyền đến các nút khác. Câu truy
vấn sẽ đi hết các nút trong mạng Gnutella cho đến khi file được tìm thấy hoặc thời
gian sống của nó đã hết. Kĩ thuật khám phá này sẽ làm lụt mạng và đây chính là
nguyên nhân cho các vấn đề về quy mô mạng. Một vấn đề khác trong Gnutella là
những người điều khiển tự do, ví dụ là những người không phân bố nội dung nhưng
lại lấy nội dung từ người dùng khác. Mojo Nation là ứng dụng trao đổi nội dung
ngang hàng, nó giới thiệu một sự lưu hành ảo để đếm những người điều khiển tự do.
Sư lưu hành ảo này dùng để khuyến phân bố các tài nguyên (như là không gian lưu
trữ và nội dung). Các máy trạm trong mạn Mojo Nation có thể có các vai trò khác
nhau. Nội dung được phân tách vào thành các khối và được phân bố trên toàn bộ
14
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
mạng Mojo. Do đó, máy chủ lưu giữ chỉ một phần nội dung các host chứ không
phải toàn bộ file. Một hệ thống chia sẻ file phổ biến khác là eDonkey. Đặc điểm đặc
biệt của eDonkey là nó xác minh các file sử dụng thuật toán MD4 dựa trên giá trị
mảng băm và kích cỡ file. Phương thức này cho phép xác định các file với nội dung
giống nhau nhưng tên file khác nhau. Nó cũng có thể tải nội dung từ các file nguồn
khác và vì vậy tăng tỉ lệ tải mạng. Freenet cũng là một hệ thống chia sẻ nội dung/
file. Mục đích chính của Freenet là làm cho nó có thể sử dụng với người vô danh.
Các yêu cầu của người dùng không phải của Freenet hoặc các file đang được đặc
trong những nơi khác trong Freenet có thể được xác định. Xa hơn, một người điều
khiển của một nút Freenet không thể xác minh dữ liệu gì được lưu trữ trên đĩa cục
bộ của nó. Freenet đã phân tán hoàn chỉnh và biểu diễn mạng ngang hàng theo mẫu
của riêng nó.
1.3 Tính toán tình nguyện
1.3.1 Khái niệm
Tính toán tình nguyện là một mô hình tính toán song song mới cho phép người
dùng tình nguyện trên toàn mạng phân bổ các tài nguyên tính toán nhàn rỗi của họ
để hỗ trợ cho tính toán song song có phạm vi rộng lớn [1], [2], [3], [20]. Không
giống như các hệ thống tính toán lưới phổ biến [4], [5], các hệ thống tính toán tình
nguyện chứa đựng nhiều các máy tính từ các cá nhân (được gọi là những người tình
nguyện) người mà muốn chia sẻ các tài nguyên của họ cho các dự án nghiên cứu
mang tính cộng đống như là SETI@home [2] tìm kiếm 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, Climateprediction.net@Home [7] dùng để
dự đoán khí hậu trên trái đất ... Khi tham gia vào dự án, những người tình nguyện
được giữ bí mật về tên tuổi cùng các thông tin cá nhân khác. Mặc dù khi đăng ký
tham gia dự án họ phải cung cấp email cũng như một số thông tin, tuy nhiên dự án
không thể làm ảnh hưởng đến đời sống thực của họ. Và vì thế, họ không phải chịu
bất kỳ trách nhiệm nào về dự á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
15
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
công của dự án SETI@home với tổng số host 2,138,226 tổng số lượng người dùng
904,956 với tổng 252 quốc gia tham gia, các phép toán con trỏ động trung bình cho
mỗi giây 51,103.68 GigaFLOPS (51.104 TeraFLOPS).
Một hệ thống tình nguyện điển hình bao gồm hàng trăm đến hàng nghìn máy tính
tình nguyện và một trung tâm tính toán (trung tâm này có thể bao gồm nhiều các
máy chủ trung tâm cho cân bằng tải). Các máy chủ của trung tâm tính toán quản lý
các công việc tính toán song song được yêu cầu, phân chia chúng vào các nhiệm vụ
nhỏ hơn và đặt chúng đến các máy tính tình nguyện để thực thi. Mỗi máy tính tình
nguyện thực thi các nhiệm vụ được chỉ định và rồi gửi các kết quả quay trở lại đến
các máy chủ trung tâm. Các máy chủ trung tâm sẽ tập hợp những kết quả đó và làm
một vài các công việc thêm như là kiểm tra kết quả và trả về kết quả cuối cùng đến
người dùng cuối của hệ thống.
Hình 1-4. Mô hình tính toán tình nguyện
1.3.2 BOINC
1.3.2.1 Khái niệm
BOINC (Berkeley Open Infrastructure for Network Computing) là một hệ thống
phần mềm trung gian cho tính toán tình nguyện. BOINC đang được sử dụng bởi
một số các dự án bao gồm: SETI@home [2], Einstein@Home [6],
Climateprediction.net@Home [7]... Những người tình nguyện tham gia hệ thống
bằng cách chạy phần mềm khách BOINC trên máy tính của họ (hoặc các máy trạm).
16
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Họ có thể tham gia mỗi máy trạm đến một tập các dự án, và có thể điều khiển chỉ
định các tài nguyên giữa các dự án.
Một dự án dựa trên BOINC cung cấp trên các máy chủ của nó. Các máy trạm tải các
chương trình thực thi ứng dụng và các file dữ liệu từ máy chủ, thực hiện các nhiệm
vụ (bằng cách chạy các ứng dụng theo các file dữ liệu đặc tả), và tải lên các file đầu
ra đến máy chủ. Phần mềm BOINC bao gồm các thành phần phía máy chủ, như là
các chương trình lập lịch và tiến trình để quản lý phấn bố và tập hợp các nhiệm vụ
[12], và giao diện dựa trên web cho những người tình nguyện và các nhà quản trị dự
án.
Hình 1-5. Mô hình cơ bản của BOINC
1.3.2.2 Các đặc trưng cơ bản của BOINC [23]
• Tính độc lập của dự án: Có nhiều dự án khác nhau đều sử dụng BOINC, tuy
nhiên các dự án độc lập hoàn toàn với nhau. Mỗi dự án có máy chủ và cơ sở dữ
liệu riêng, không có thư mục trung tâm cho tất cả các dự án. Điểm chung của
chúng là đều lấy BOINC làm nền phần mềm
• Tính linh hoạt trong sử dụng: Những người tình nguyện có thể tham gia vào
nhiều dự án; họ kiểm soát những dự án ấy, quản lý và phân chia tài nguyên cho
các dự án. Khi một dự án kết thúc hay không làm việc, tài nguyên dành cho nó
sẽ được thu hồi và phân chia cho các dự án khác.
17
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
• Linh hoạt trong phát triển: Các ứng dụng viết bằng C, C++ hay Fortran có thể
chạy các ứng dụng BOINC mà không cần cải biên hay cải biên rất ít. Một ứng
dụng có thể bao gồm nhiều file (đa chương trình). Những phiên bản mới của ứng
dụng có thể được tự động triển khai, cập nhật.
• Tính bảo mật: BOINC bảo vệ để chống lại các kiểu tấn công có thể xảy ra. Ví
dụ chữ ký số dựa trên mã hoá khoá công khai chống lại sự phân phối của
virus…
• Tính thực thi và khả chuyển: Phần mềm máy chủ BOINC vô cùng hiệu quả.
Vì thế, 1 máy chủ trung tâm có thể gửi đi và điều khiển hàng triệu công việc
trong 1 ngày. Kiến trúc máy chủ còn có khả năng biến đổi cao, làm cho nó dễ
dàng tăng khả năng máy chủ hoặc sẵn sàng tăng thêm nhiều máy.
• Mã nguồn mở: Bản thân BOINC được cung cấp dưới dạng mã nguồn mở, cả
BOINC máy chủ và BOINC khách. Tuy vậy các ứng dụng của BOINC không
nhất thiết phải là nguồn mở.
• Khả năng tính toán với lượng dữ liệu lớn: BOINC hỗ trợ các ứng dụng tạo ra
hay sử dụng một số lượng lớn dữ liệu, hoặc cần dùng nhiều bộ nhớ. Sự phân
phối và tập hợp dữ liệu có thể được chia ra trên nhiều máy chủ. Những người
tham gia trao đổi lượng dữ liệu lớn một cách kín đáo. Những người sử dụng có
thể chỉ rõ giới hạn về bộ nhớ hay băng thông. Công việc chỉ gửi đến những máy
có khả năng hoàn thành.
• Platform đa dạng: phiên bản BOINC dành cho máy trạm có sẵn cho hầu hết các
platform thông dụng (Mac OS X, Windows, Linux và các hệ thống Unix khác
như Ubuntu, Fedora, Redhat…). Máy trạm có thể sử dụng nhiều CPU.
• Kiến trúc phần mềm dễ mở rộng: Những thành phần quan trọng của BOINC
đều được tài liệu hoá và công bố rộng rãi; nhờ đó các nhà phát triển ở hãng thứ 3
có thể dễ dàng tạo phần mềm và website mở rộng BOINC.
• Tính cộng đồng người tình nguyện: BOINC cung cấp các công cụ trên web
như bảng tin nhắn, thông tin cá nhân những người tình nguyện và tin nhắn riêng;
18
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
điều đó giúp những người tình nguyện dễ dàng hình thành những cộng đồng trực
tuyến để trao đổi, giúp đỡ lẫn nhau.
1.3.2.3 Kiến trúc BOINC
BOINC bao gồm các thành phần chủ và khách (Xem trong hình 1.5). BOINC khách
chạy các ứng dụng dự án. Các ứng dụng được liên kết với hệ thống thời gian chạy,
các chức năng của hệ thống này bao gồm điều khiển xử lý, điều khiển điểm kiểm
tra, và các đồ thị [13]. Máy khách thực thi lập lịch CPU(được thực thi trên đỉnh của
bộ lập lịch của hệ điều hành cục bộ, tại mức hệ điều hành, BOINC chạy các ứng
dụng tại mức độ ưu tiên 0). Nó có thể chiếm giữ các ứng dụng hoặc bằng cách trì
hoãn chúng(và rời chúng vào trong bộ nhớ) hoặc bằng cách chỉ dẫn chúng để thoát.
BOINC chủ thực hiện việc cung cấp các ứng dụng và các đơn vị công việc, xử lý
các kết quả tính toán, quản lý sự phân phối và tập hợp dữ liệu.
Hình 1-6. Kiến trúc BOINC
Tất cả các kết nối mạng trong BOINC được khởi tạo bởi các máy khách. Một máy
khách giao tiếp với một máy chủ gán nhiệm vụ của dự án [12] theo HTTP. Yêu cầu
là một file dữ liệu XML trong đó bao gồm các miêu tả về phần cứng và khả năng
thực hiện, một danh sách công việc đã hoàn thành, và một yêu cầu cho một số lượng
chắc chắn (diễn tả giới hạn thời gian CPU) công việc thêm. Thông điệp phản hồi
19
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
bao gồm một danh sách các công việc mới(mỗi công việc được miêu tả bởi một
thành phân XML mà liệt kê ứng dụng, các file đầu vào đầu ra, bao gồm vị trí các
máy chủ dữ liệu từ mỗi file có thể được tải về). Đôi khi các máy khách có các kết
nối vật lý bị trục trặc. Như là cách máy tính có thể kết nối một ít hàng ngày. Trong
khoảng thời gian kết nối mạng, BOINC cố gắng tải đủ công việc để giữ cho máy
tính bận cho đến lần kết nối kế tiếp. Hình vẽ bên dưới chỉ định trình tự thực hiện
giữa máy trạm và máy chủ.
Hình 1-7. Sự tương tác giữa máy trạm và máy chủ
1.3.3 Lập lịch trong tính toán tình nguyện
Theo như khái niệm về hệ thống tính toán tình nguyện ở trên thì một hệ thống tính
toán tình nguyện bao gồm nhiều máy trạm kết nối đến máy chủ, trong đó máy trạm
kết nối đến máy chủ để lấy công việc và thực hiện rồi trả về kết quả cho máy chủ,
còn máy chủ thì thực thi lựa chọn các máy trạn để gán nhiệm vụ. Vì vậy quá trình
xử lý lấy và thực thi các công việc này bao gồm bốn chính sách liên quan [14], [15]:
• Lập lịch CPU : Của các việc có thể chạy hiện nay, công việc nào có thể chạy.
• Lấy công việc : Khi nào để nghị một dự án cho nhiều công việc, dự án nào
được đề nghị và đề nghị bao nhiêu công việc.
• Gửi công việc : Khi một dự án nhận được một yêu cầu công việc, nó lên gửi
công việc nào.nó lên gửi công việc nào.
• Ước lượng thời gian hoàn thành : Ước lượng thời gian CPU duy trì công việc
như thế nào.
20
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Lập lịch trong hệ thống tính toán tình nguyện có vai trò hết sức quan trọng nó giúp
nâng cao toàn bộ thời gian thực thi của hệ thống. Với máy trạm nó giúp cho lập lịch
CPU và lấy công việc. Với máy chủ lập lịch giúp cho tối đa hóa được số công việc
được thực thi và giảm thời gian thực thi cua hệ thống.
1.3.3.1 Lập lịch phía máy trạm
Lập lịch phía máy trạm đó là các chính sách lập lịch CPU và lấy công việc, vấn đề
lập lịch phía may trạm phải quan tâm đến các đầu vào: Trước tiên đó là các đặc
điểm phần cứng của máy trạm như là số lượng bộ vi xử lý. Máy trạm theo dõi các
đặc điểm ứng dụng đa dạng như là phân số thực thi(phân số của thời gian chạy và
được phép làm tính toán), và các thống kê về các kết nối mạng của nó. Thứ hai đó là
sự ưu tiên của người dùng. Sự ưu tiên nay bao gồm : Tài nguyên chia sẻ cho mỗi
dự án, giới hạn về sử dụng bộ vi sử lý (điều kiện để tính toán trong khi máy đang
trong sử dụng, số lượng tối đa CPU được dùng, và phân số thời gian CPU được
dùng lớn nhất), khoảng kết lối(thời gian tối thiểu giưa các giai đoạn hoạt động của
mạng, điều nay dùng để cung cấp một gợi ý các máy trạm kết nối thường mạng
thường xuyên như thế nào)…. Cuối cùng mỗi công việc có một số lượng các tham
số đặc tả cho dự án, bao gồm ước lượng của số lượng các toán tử con trỏ động của
dự án và thời gian cuối cùng để máy trạm báo cáo công việc.
1.3.3.2 Lập lịch phía máy chủ
Lập lịch phía máy chủ là phải sử dụng tối ưu được nguồn tài nguyên tình nguyện.
Vấn đề lập lích phía máy chủ đó là gửi công việc và ước lượng thời gian hoàn thành
công việc. Có rất nhiều các nghiên cứu về lập lịch phía máy chủ để tối ưu hóa được
nguồn tài nguyên tình nguyện. Chính sách lập lịch sử dụng phổ biến trong BOINC
là đến trước phục vụ trước, trong chính sách lập lịch này sẽ gán các công việc có
khả năng đầu tiên đến các máy trạm yêu câu công việc đầu tiên đáp ứng được các
tiêu chí về sự dư thừa đồng nhất cho việc phân bố nhiều công việc HR (HR phân bố
các công việc giống nhau đến các máy trạm có khả năng tính toán như nhau nghĩa là
chúng có hệ điều hành giống nhau và có bộ vi xử lý thuộc cùng nhà sản xuất).
Trong [19], các tác giả đã đưa ra một chính sách lập lịch dựa trên ngưỡng, chính
21
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
sách này thiết lập hai ngưỡng một cho khả năng thực hiện công việc của máy trạm
và một cho sự tin cậy của máy trạm và sử dụng những ngưỡng này để xác minh các
công việc phân bố đến máy trạm. Nó sẽ không phân bố công việc đến máy trạm có
tỉ lệ độ tin cậy và khả năng thực hiện công việc thấp hơn giá trị ngưỡng định nghĩa.
Những ngưỡng này thuộc trong khoảng tử 0 đến 1. Khi một máy trạm yêu cầu một
công việc mới, máy chủ sẽ tính toán tỉ lệ khả năng thực hiện công việc và tỉ lệ tin
cậy của máy trạm dựa trên lịch sử thực hiện công việc của máy trạm. Nếu đồng thời
hai tỉ lệ này lớn hơn ngưỡng đã định nghĩa thì máy trạm được gán công việc nếu
không thi máy trạm không được gán công việc. Việc tính khả năng thực hiện của
máy trạm dựa vào tổng số công việc được phân bố đến máy trạm và số công việc
mà máy trạm đã hoàn thành cho đến thời điểm hiện tại (nó chính bằng tỉ số giữa số
công việc đã hoàn thàng trên tổng số công việc được giao), còn độ tin cậy của máy
trạm chính là tỉ số giữa các công việc hoàn thành cho kết quả đúng trên số công việc
hoàn thành của máy trạm.
1.3.3.3 Lập lịch chịu lỗi dựa trên độ tin cậy
Cơ bản, một hệ thống tính toán tình nguyện cho phép truy xuất rộng rãi từ công
chúng, vì vậy một vấn đề đang tăng lên là bảo vệ hệ thống như thế nào từ sự phá
hoại của nhiều người dùng ác ý đệ trình các kết quả giả mạo. Trong [17], các tác giả
đã đưa ra một kĩ thuật lịch dựa trên tính chính xác, trong kĩ thuật này sử dụng sự dư
thừa trong thực hiên công việc để gán đến một nhóm máy trạm, việc nhóm các máy
trạm thực hiện theo ba bước sau: (1) Ước lượng tỉ lệ tin cậy của các nút trạm độc
lập, (2) Sử dụng các tỉ lệ tin cậy của các máy trạm đã được ước lượng để tính toán
tính khả thi chính xác (LOC) của các nhóm có thể. (3) Nhóm các máy trạm cho việc
gán các nhiệm vụ dựa trên LOC để ước lượng số tối đa các đầu vào và tỉ lệ thành
công hoàn thành nhiệm vụ. Trong [8], tác giả đã thảo luận về nhiều các kĩ thuật chịu
đựng lỗi để bảo vệ các hệ thống chống lại những người tình nguyện ác ý như là biểu
quyết, kiểm tra điểm, dò vết trở lại và danh sách đen. Đặc biệt, tác giả đã giới thiệu
định nghĩa độ tin cậy và đề xuất một kĩ thuật chịu đựng lỗi dựa trên độ tin cậy mới.
Trong kĩ thuật mới này, độ tin cậy của một kết quả được ước lượng như là sác xuất
22
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
điều kiện để mà kết quả chính xác. Thực thi của một nhiệm vụ sẽ được lập lại trên
các máy tính nhiều lần cho đến khi kết quả cuối cùng đạt được độ tin cậy đủ cao.
Nó chứng minh rằng kĩ thuật chịu đựng lỗi dựa trên độ tin cậy được đề xuất có thể
thực thi nhanh hơn các kĩ thuật truyền thống khác như là biểu quyết và kiểm tra
điểm bên dưới các yêu cầu về tỉ lệ lỗi là giống nhau.
Trong [10], tác giả đã mở rộng công việc của Sarmenta vào nhiều các trường hợp
phổ biến bằng cách giải quyết các hệ thống tính toán song song chứa đựng nhiều
các máy tính nguyện hơn số lượng các nhiệm vụ. Vì trong trường hợp này, một
nhiệm vụ lên được làm lại trong nhiều các máy tính nguyện để sử dụng tốt các tài
nguyên dư thừa. Nhận thấy rằng các kĩ thuật chịu lỗi dựa trên độ tin cậy đang tồn tại
không hiệu quả cho các ứng dụng song song loại này bởi vì chúng không quan tâm
đến trường hợp một nhiệm vụ giống nhau được thực hiện lại trên nhiều máy tình
nguyện tại cùng một thời điểm. Dẫn đến kết quả, thuật toán dựa trên độ tin cậy đang
tồn tại đạt được hiệu năng tính toán thấp trong giới hạn thời gian thực thi. Tác giả
đã đề xuất một thuật toán lập lịch dựa trên độ ưu tiên theo khả năng thưc thi của các
máy tình nguyện cho trường hợp này. Nó đã chứng minh được việc áp dụng thuật
toán này đã làm tăng hiệu năng cho kĩ thuật chịu lỗi dựa trên độ tin cậy trong trường
hợp có nhiều máy tình nguyện hơn số lượng nhiệm vụ.
Tuy nhiên, cần chú ý rằng kĩ thuật chịu đựng lỗi được đề xuất bởi Sarmenta và kĩ
thuật lập lịch dựa trên độ ưu tiên của tác giả chưa quan tâm đến độ tin cậy của các
máy trạm và của các nhiệm vụ đang được thực hiện, vì vậy thuật toán dựa trên độ
tin cậy chưa đạt được hiệu năng tốt nhất trong giới hạn thời gian thực thi. Trong
luận văn này, tôi tập trung vào việc kết hợp giữa khả năng tính toán và độ tin cậy
của máy trạm với độ tin cậy của các nhiệm vụ đang được thực thi để cải thiện toàn
bộ hiệu năng trong giới hạn thời gian thực thi trong khi vẫn đảm bảo được yêu cầu
độ tin cậy và đề xuất ra một thuật toán lập lịch hiệu quả được gọi là “Lập lịch
Round Robin dựa trên độ ưu tiên về độ tin cậy và khả năng thực hiện”. Tính hiệu
quả của thuật toán sẽ được xác minh bởi các mô phỏng ở phần 5.
Hiện tại để đánh giá độ tin cậy của các thuật toán lập lịch tình nguyện có thể sử
23
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
dụng các bộ mô phỏng như SIMBA, SIMBOINC nhưng do quá trình liên hệ với các
tác giả để xin mã nguồn chương trình các bộ mô phỏng có khó khăn và chỉ nhận
được mã nguồn bộ mô phỏng SIMBA của tác giả Derrick Kondo sau khi đã sử dụng
bộ mô phỏng VCSIM và xây dựng mô phỏng xong. Do thời gian không còn đủ để
tôi thử nghiệm thêm các kết quả mô phỏng trên bộ mô phỏng SIMBA vì vây trong
luận văn của mình tôi đã sử dụng bộ mô phỏng VCSIM để mô phỏng các thuật toán
đã đề xuất.
1.3.4 So sánh với tính toán lưới và tính toán ngang hàng
1.3.4.1 Tính toán lưới
Tính toán lưới và Tính toán tình nguyện giống nhau ở chỗ cùng sử dụng nhiều máy
tính kết nối với nhau để thực hiện một công việc chung. Tuy nhiên, tính toán lưới
không có một máy chủ tập trung mà được phân thành các cụm nhỏ, mỗi cụm nhỏ ấy
có thể lại được phân chia nhỏ hơn và đơn vị nhỏ nhất là các PC thông thường, với
nhiệm vụ là tính toán và trả về kết quả. Liên tưởng tính toán lưới với sự tham chiếu
tới việc chia sẻ những tài nguyên tính toán bên trong và giữa các tổ chức.
- Mỗi tổ chức có thể đóng vai trò là người sản xuất hoặc khách hàng của tài
nguyên (giống như trong lưới điện, các công ty điện năng có thể mua hoặc bán
năng lượng từ các công ty khác, phù hợp với yêu cầu biến đổi).
- Các tổ chức chịu trách nhiệm qua lại, nếu 1 tổ chức cư xử không đúng, những tổ
chức khác có thể từ chối hợp tác, chia sẻ tài nguyên với họ và ngược lại.
Như vậy, tính toán lưới có tính đến trách nhiệm và không có tính che giấu. Những
người tham gia phải chịu trách nhiệm về các kết quả, các xung đột, sai sót… (điểm
khác nhau cơ bản với tính toán tình nguyện).
1.3.4.2 Tính toán ngang hàng
Điểm khác nhau cơ bản nhất là tính toán ngang hàng không hề có server. Nó chỉ
đơn thuần gồm các PC kết nối với nhau và không có cái nào làm chủ. Trong đó, các
file và dữ liệu khác được trao đổi giữa các “máy ngang hàng” (ví dụ như các PCs)
mà không liên can gì tới máy chủ trung tâm. Nó khác với tính toán tình nguyện:
24
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
- Tính toán tình nguyện có những máy chủ trung tâm. Điển hình là không có
truyền thông ngang hàng.
- Tính toán ngang hàng mang lại lợi ích cho những người tham gia. Ở đó không
có khái niệm 1 dự án mà tài nguyên được cung cấp miễn phí.
- Tính toán ngang hàng thật sự bao gồm sự tích trữ và lấy lại, không phải tính
toán.
25
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Chương 2. LÝ THUYẾT CƠ BẢN VỀ LẬP LỊCH DỰA TRÊN
ĐỘ TIN CẬY
Trong phần này, tôi tóm tắt lại mô hình cơ bản và các giả định, các kĩ thuật chịu lỗi
truyền thống, các kĩ thuật chịu lỗi dựa trên độ tin cậy cho tính toán tình nguyên và
khảo sát một số giản đồ lập lịch chịu lỗi dựa trên độ tin cậy.
2.1 Mô hình cơ bản và các giả định
Mô hình tính toán. Trong luận văn này, tôi giả sử một mô hình chủ khách dựa trên
hàng đợi công việc, mô hình này được dùng trong tất cả các hệ thống tính toán tình
nguyện thực tế hiện nay, thêm vào đó là trong nhiều các hệ thống lưới, các hệ thống
metacomputing, và toàn bộ các hệ thống tính toán song song dựa trên mạng diện
rộng khác. Trong mô hình này một tính toán được chia vào thành vào một dãy các
lô, mỗi lô bao gồm nhiều các đối tượng công việc độc lập nhau [1]. Tại thời điểm
bắt đầu của mỗi lô, những đối tượng công việc này được đặt vào trong một hàng đợi
công việc bởi nút chủ, và sau đó được phân phối đến các nút máy trạm đã đăng kí
gia nhập vào máy tính tình nguyện để thực thi chúng song song và rồi trả về kết quả
của chúng đến máy chủ khi chúng kết thúc nhiệm vụ tính toán. Khi máy chủ đã tập
hợp được các kết quả cho tất cả các đối tượng công việc, nó sẽ tạo ra một lô các đối
tượng công việc tiếp (có thể dùng dữ liệu từ các kết quả của lô hiện tại), đặt chúng
vào trong hàng đợi công việc, và lập lại điều này cho toàn bộ xử lý. Trong mô hình
này, tôi cũng giả sử rằng mọi nhiệm vụ có kích cỡ giống nhau.
Một giải thích cho mô hình này được chỉ đinh trong hình 2-1.
26
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Hình 2-1. Mô hình chủ khách
Tỉ lệ lỗi. Chúng ta định nghĩa tỉ lệ lỗi, , là tỉ số của các kết quả lỗi hoặc các lỗi so
với các kết quả cuối cùng được chấp nhận tại cuối của nhóm. Cách thứ hai, chúng ta
cũng có thể định nghĩa nó là xác suất của từng kết quả cuối cùng riêng biệt là lỗi,
như vậy về trung bình, số lượng các lỗi được mong đợi trong một nhóm N các kết
quả được cho bởi . Để đơn giản, tôi giả sử rằng các nhóm công việc là độc lập
lẫn nhau, do đó các lỗi trong một nhóm không ảnh hưởng lẫn nhau. Xa hơn, trong
thiết kế các kĩ thuật của tôi, tôi giả sử rằng có một tỉ lệ lỗi chấp nhận được là khác
không, , và nhằm làm cho tỉ lệ lỗi thấp hơn nó. Một vài thuật toán “chịu lỗi tự
nhiên” như là các thuật toán di truyền, xuất video, và một vài các ứng dụng thống
kê có thể cho phép có một phân số lớn liên quan (1% hoặc nhiều hơn) các kết quả
cuối cùng là lỗi, và vì vậy có tỉ lệ lỗi chấp nhận cao. Trong các ứng dụng khác
không cho phép bất cứ lỗi nào tại tất cả các kết quả, phải được thiết lập để làm
cho xác suất lấy được bất cứ nỗi nào tại tất cả các kết quả cuối cùng là tương đối
nhỏ. Cho ví dụ, Giả sử rằng một tính toán có 10 lô mỗi lô có 100 đối tượng công
việc riêng biệt và mỗi lô này phụ thuộc vào nhau do đó một kết quả lỗi trong bất cứ
nhóm nào trong 10 lô sẽ là nguyên nhân của toàn bộ tính toán sai. Trong trường hợp
này, để làm cho xác suất của toàn bộ tính toán là lỗi, P (lỗi), kém hơn 1%, tỉ lệ lỗi ,
tỉ lệ xác suất của một kết quả riêng biệt bị lỗi, phải không lớn hơn:
27
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Kẻ phá hoại. Chúng ta giả sử rằng một phân số mắc lỗi, f, của toàn bộ máy trạm, P,
là các kẻ phá hoại. Nút chủ (nút mà chúng ta giả sử là tin cậy) có thể không biết giá
trị thực sự của f, nhưng được cho phép giả định một cận trên của nó, do đó không có
sự đảm bảo cần được làm nếu phân số mắc lỗi thực lớn hơn cận trên giả định.
Để đơn giản, chúng ta giả định rằng tất cả các máy trạm, bao gồm cả các máy phá
hoại, chạy chính xác với tốc độ giống nhau, để mà các đối tượng công việc là giống
nhau và được phân bố ngẫu nhiên giữa các máy trạm và các máy phá hoại. Vì vậy,
mỗi kết quả chúng ta nhận được là bằng giống như là đến từ bất cứ máy trạm nào, tỉ
lệ lỗi gốc - nghĩa là tỉ lệ lỗi được mong đợi mà không phải chịu đựng lỗi đơn giản là
f.
Tỉ lệ phá hoại và sự cấu kết. Cho đơn giản, chúng ta làm mỗi máy phá hoại theo
phương thức Bernoulli với một xác suất s cho một kết quả lỗi, và chúng ta giả sử
rằng s, được gọi là tỷ lệ phá hoại, là một hằng số theo thời gian và giống nhau cho
tất cả các máy phá hoại.
Chú ý rằng trong giả sử này, các máy trạm và phá hoại là độc lập lẫn nhau và không
giao tiếp với nhau. Đặc biệt, trong trường hợp ở đó các máy phá hoại không luôn
cho kết quả sai, chúng ta giả sử rằng các máy phá hoại không tán thành cho kết quả
sai, nhưng quyết định làm là độc lập.
Tuy nhiên, nếu hai hoặc nhiều máy phá hoại xuất hiện quyết định cho kết quả sai
cho một thực thể công việc đặc biệt, chúng ta sẽ giả sử rằng các trả lời sai của
chúng phù hợp, trừ trường hợp đã định khác. Điều này cho phép các máy phá hoại
biểu quyết cùng nhau, và điều này không chỉ là một giả định có từ trực quan, chúng
ta có thể mong đợi tỉ lệ lỗi cuối cùng thấp hơn nếu các máy phá hoại không thể biểu
quyết cùng nhau.
Sự dư thừa và sự châm chễ. Thông thường, một kĩ thuật chịu lỗi mới đưa ra một
vài thời gian tính toán thêm để thực thi lại các nhiệm vụ. Để đánh giá hiệu năng và
hiệu quả của một kĩ thuật chịu lỗi, chúng ta quan tâm đến sự dư thừa và sự chậm
chễ. Sự dư thừa được định nghĩa là tỉ số giữa số lượng tổng trung bình của các đối
tượng công việc thực sự được gán đến các máy trạm trong một lô khi dùng kĩ thuật,
28
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
và số lượng gốc của các thực thể công việc, N. Sự chậm chễ được định nghĩa
tương tự là tỉ số giữa các lần chạy của sự tính toán có và không có dùng kĩ thuật.
Thông thường, sự dư thừa sẽ hướng tới một sự chậm chễ tương ứng, từ khi chúng ta
giả sử rằng các đối tượng công việc nhiều hơn gấp nhiều lần các máy, để mà không
có các máy trạm nhàn rỗi trong hầu hết các thời gian. Cho ví dụ, một kĩ thuật làm
trung bình tất cả các công việc gấp hai lần sẽ mất thời gian gấp đôi.
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
Tuy nhiên chú ý rằng, trong một vài trường hợp – đặc biệt khi máy trạm có thể gia
nhập, dời đi hoặc cho vào danh sách đen trong giai đoạn giữa của lô – sự chậm chễ
có thể khác so với sự dư thừa. Nếu máy trạm dời đi, cho ví dụ, thì các máy trạm còn
lại phải lấy quá các công việc của chúng. Điều này tăng sự chậm chễ, thậm chí
xuyên suất tổng số lượng của công việc, và vì vậy độ dư thừa là giống nhau.
2.2 Các kĩ thuật chịu lỗi truyền thống.
Thông thường, các kĩ thuật chịu lỗi nhằm vào (thứ tự ưu tiên): (1) tối thiểu tỉ lệ lỗi
cuối cùng là nhỏ nhất có thể, hoặc giảm nó ít nhất đến một mức chấp nhận, (2) tối
thiểu sự dư thừa, và (3) tối thiểu sự chậm chễ.
Cơ bản các kĩ thuật chịu lỗi dùng các kĩ thuật truyền thống như là biểu quyết, kiểm
tra điểm hoặc danh sách đen để tăng độ tin cậy của các hệ thống tính toán tình
nguyện. Trong kĩ thuật biểu quyết, mỗi nhiệm vụ được thực thi nhiều lần và kết quả
tốt nhất được lựa chọn xuyên suốt một xử lý biểu quyết. Có hai cách biểu quyết:
biểu quyết theo số đông và biểu quyết m đầu tiên. Trong cách biểu quyết đầu tiên,
kết quả có số lượng biểu quyết giống nhau cao nhất được lựa chọn là kết quả cuối
cùng, trong cách thứ hai, sự thực thi một nhiệm vụ được lập lại cho đến khi nút chủ
29
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
tập hợp đủ m kết quả giống nhau. Trong kĩ thuật kiểm tra điểm, máy chủ kiểm tra
tính hợp lệ của máy trạm bằng cách cho ngẫu nhiên máy trạm một công việc được
đánh dấu là kết quả chính xác đã thực sự được biết ở một nơi khác (ví dụ. Các công
việc được đánh dấu đã được thực thi trên máy chủ hoặc trên một vài máy tính tình
nguyện đáng tin cậy). Nếu kết quả trả về không đúng, nút chủ có thể từ bỏ kết quả
hiện tại hoặc thậm chí quay lại kiểm tra lại tất cả các kết quả nhận được từ máy trạm
đó. Trong trường hợp kĩ thuật danh sách đen, máy chủ có thể thêm các máy trạm
nguy hiểm đã được dò tìm vào trong danh sách đen để ngăn chặn không cho chúng
đệ trình các kết quả sai lại nhiều lần nữa.
2.2.1 Biểu quyết theo số đông
Chúng ta có thể dễ dàng thực thi giản đồ biểu quyết theo số đông truyền thống bằng
cách dùng một hàng đợi công việc tham lam được thay đổi [11] được chỉ định trong
hình 2-2. Ở đây, máy chủ tiếp tục đi xuyên suất các thực thể công việc trong hàng
đợi công việc theo phương thức Rough-Robin, cho đến khi tất cả các cờ được làm
của tất cả các thực thể công việc được thiết lập. Cờ được làm của mỗi thực thể công
việc được dời không thiết lập cho đến khi chúng ta tập hợp được m kết quả phù hợp
đầu tiên cho thực thể công việc đó, kết quả thực thi một giản đồ biểu quyết m đầu
tiên. Giản đồ này có một sự dư thừa được mong đợi là , và một tỉ lệ lỗi
giảm theo hàm mũ với m, được chỉ định trong hình 2-3 [8]. Tỉ lệ lỗi giảm theo hàm
mũ nghĩa rằng các công việc được biểu quyết rất tốt trong các hệ thống với f nhỏ, và
xa hơn, các công việc biểu quyết lấy tăng lên tốt hơn là f giảm. Vì vậy, trong hệ
thống với tỉ lệ lỗi rất thấp để bắt đầu, như là hệ thống phần cứng, nó không lấy
nhiều sự dư thừa để giảm tỉ lệ lỗi đến các mức vô cùng thấp.
30
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
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]
Tuy nhiên biểu quyết cũng có các khó khăn của nó. Trước tiên nó không hiệu quả
khi f không nhỏ. Được chỉ trong hình 2-3, cho ví dụ, tại f = 20%, làm tất cả các công
việc ít nhất m = 6 lần vẫn còn một tỉ lệ lỗi lớn hơn 1%. Thứ hai và quan trọng hơn,
nó có một sự dư thừa tối thiểu 2 ít liên quan đến f và tỉ lệ lỗi mục tiêu, . Vì
những lý do này biểu quyết chỉ được thực hiện thực tế trong các trường hợp ở đó:
(1) f là nhỏ (ví dụ, ) và (2) hoặc (a) chúng ta có đủ các nút nhàn rỗi hoặc dư
thừa để lấy thêm công việc mà không là nguyên nhân tạo thêm sự chậm chễ hoặc
(b) sự chậm chễ của ít nhất hai (hoặc thông thường m) dường như là một cái giá
chấp nhận được để trả cho việc giảm tỉ lệ lỗi.
2.2.2 Kiểm tra điểm
Trong trường hợp ở đó hoặc f là lớn, hoặc là tỉ lệ lỗi chấp nhận được lớn nhất của
chúng ta là không quá nhỏ, chúng ta có thể sử dụng một lựa chọn mới gọi là kiểm
tra điểm. Trong kiểm tra điểm, nút chủ không quay lại làm tất cả các đối tượng
công việc hai hoặc nhiều lần, nhưng thay vào đó cho ngẫu nhiên một máy trạm một
công việc giám sát, công việc mà kết quả đúng đã được biết trước hoặc sẽ được biết
bằng việc kiểm tra nó trong một vài cách thức sau này.Sau đó nếu một máy trạm
được bắt cho một kết quả tồi, máy chủ quay lại dò tất cả các kết quả nó đã nhận
31
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
được từ máy trạm đó và loại bỏ tất cả chúng. Máy chủ cũng có thể có danh sách đen
máy phá hoại được bắt để mà ngăn chặn nó đệ trình các kết quả lỗi trong tương lai.
Bởi vì kiểm tra điểm không bao gồm thực hiện lại tất cả các đối tượng công việc,
nên nó có độ dư thừa thấp hơn nhiều với biểu quyết. Nếu chúng ta giả sử rằng máy
chủ kiểm tra điểm mỗi máy trạm với một xác suất Bernoulli q, được gọi là tỉ lệ kiểm
tra điểm, thì dư thừa, về trung bình, sẽ chỉ là . Cho ví dụ, nếu q = 10%,
thì 10% của công việc máy chủ cho là công việc giám sát. Điều này có nghĩa rằng
về trung bình, máy chủ cho ra bên ngoài các đối tượng
công việc trong xuất tiến trình công việc của một lô với N các đối tượng công việc
thực sự.
2.2.2.1 Kiểm tra điểm dùng danh sách đen
Tuy nhiên, thậm chí với sự dư thừa thấp này, kiểm tra điểm có thể vẫn đạt được các
tỉ lệ lỗi rất thấp. Xem điều này, quan tâm đến trường hợp ở đó các máy phá hoại bị
bắt ở trong danh sách đen và không bao giờ cho phép quay trở lại hoặc tất cả các
công việc nhiều hơn (ít nhất là trong lô hiện tại). Trong trường hợp này, các lỗi chỉ
có thể đến từ các máy phá hoại mà tồn tại đến tận cuối của lô. Giả sử rằng một máy
phá hoại được cho một tổng n đối tượng công việc, bao gồm cả các công việc giám
sát, trong một lô. Ở đây n là phần được phân của máy phá hoại trong tổng công
việc, ví dụ, N/P, thêm vào đó là sự dư thừa của kiểm tra điểm và tải thêm
để mà các máy trạm duy trì lấy khi một máy trạm được lấy vào danh sách đen), vì
vậy tỉ lệ lỗi cuối cùng trung bình với kiểm tra điểm có danh sách đen, , có thể
được tính là:
ở đây s là tỉ lệ lỗi của một máy giả mạo, f là phân số của toàn bộ máy gốc mà là các
máy phá hoại, là xác suất của một máy phá hoại tồn tại trong xuất n
vòng, và mẫu số biểu diễn phân số của toàn bộ máy trạm gốc tồn tại đến cuối cùng
của lô, bao gồm đồng thời các máy trạm tốt và xấu. Phân tích kĩ hơn của hàm này
32
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
[11] chỉ ra rằng nó có giá trị lớn nhất xấp xỉ và giá trị
này bị giới hạn như sau:
Trực quan, điều này nghĩa rằng nếu một máy phá hoại biết n trước đó, thì nó thiết
lập tỉ lệ lỗi phá hoại là , khi tỉ lệ lỗi cao hơn dẫn đến máy phá hoại đang được
bắt cũng nhanh hơn, trong khi có một tỉ lệ lỗi thấp dẫn đến ít lỗi trong phần cuối của
lô. Tuy nhiên thậm chí nếu các máy phá hoại tối ưu tỉ lệ phá hoại bằng cách này,
phương trình (2) chỉ rằng tỉ lệ lỗi trung bình không thể lớn hơn . Đó là, kiểm
tra điểm giảm tuyến tính tỉ lệ lỗi trung bình trong trường hợp tồi nhất với n (cho f là
hằng số). Vì vậy để giảm tỉ lệ lỗi, máy chủ phải làm các lô dài hơn để n lớn hơn.
2.2.2.2 Kiểm tra điểm không dùng danh sách đen
Không may mắn, danh sách đen không phải luôn luôn có thể có hiệu lực. Mặc dù
chúng ta có thể có danh sách đen các máy phá hoại dựa trên địa chỉ thư, thì cũng
không quá khó cho các máy phá hoại tạo một địa chỉ thư mới và máy tình nguyện
đó sẽ trở thành máy tình nguyện mới. Danh sách đen theo địa chỉ IP cũng không
làm việc được bởi nhiều người sử dụng các nhà cung cấp dịch vụ ISP mà cấp cho
họ địa chỉ động sau mỗi lần họ quay số. Yêu cầu nhiều mẫu xác minh để thẩm định
như là địa chỉ nhà và số điện thoại có thể cấm máy phá hoại, nhưng cũng có thể cấm
nhiều máy tình nguyện có ý tốt.
Kĩ thuật này thì rất hữu ích khi quan tâm đến hiệu quả của kiểm tra điểm khi danh
sách đen không có hiệu lực. Không may mắn, trong trường hợp này, các máy phá
hoại có thể tăng đáng kể tỉ lệ lỗi bằng việc dời đi sau khi chỉ làm một giới hạn số
lượng công việc, l, và sau đó quay lại gia nhập với một nút mới. Chúng ta có thể
chỉ [8] rằng điều này sẽ thay đổi cận trên trong trường hợp tỉ lệ lỗi trung bình
trường hợp tồi nhất đến . Điều này kém hơn trước đó. Bởi vì không giống
phương trình (2), tỉ lệ này không giảm nghịch đảo với n. Vì vậy không thể mong
đợi giảm với chiều dài của lô. Điều tốt nhất máy chủ có thể làm trong trường hợp
này là có gắng ép buộc các máy phá hoại ở lâu hơn (tăng l) bằng cách làm công việc
33
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
khó đối với chúng để chúng khó tiến tới một nhận dạng mới hoặc bằng cách đánh
lừa chễ công việc.
Nếu các lô của chúng ta không quá dài thì chúng ta có thể đưa ra một quy tắc đó là
người dùng mới không được phép gia nhập cho đến tận lô tiếp theo, để mà một máy
trạm không thể lấy được bất cứ công gì khi dời đi sớm. Trong trường hợp này tỉ lệ
lỗi là giống như trong phần 3.2.1.Tuy nhiên, giản đồ này không có ích nếu lô quá
dài, khi đó nó sẽ lãng phí nguồn tài nguyên tiềm năng của các máy tình nguyện tốt
vì bị ép buộc phải đợi lô kế tiếp.
2.3 Chịu lỗi dựa trên độ tin cậy
Trong phần này, chúng ta biểu diễn một ý tưởng mới được gọi là chịu lỗi dựa trên
độ tin cậy, ý tưởng này không chỉ giải quyết lỗi của danh sách đen mà quan trọng
hơn nó cung cấp một khung làm việc cho việc kết hợp lợi ích của biểu quyết, kiểm
tra điểm và các kĩ thuật khác tốt có thể.
Hình 2-4. Hàng đợi công việc lập lịch tham lam nâng cao độ tin cậy [8]
2.3.1 Tổng quan
Ý tưởng chính trong chịu lỗi dựa trên độ tin cậy đó là nguyên lý ngưỡng tin cậy:
Nếu chúng ta chỉ đồng ý một kết quả cho một thực thể công việc khi xác suất điều
34
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
kiện của kết quả đang đúng đó là lớn hơn một vài ngưỡng ,thì xác suất đồng ý một
kết quả đúng, trung bình của tất cả các thực thể công việc, phải lớn hơn .
Nguyên lý này ám chỉ rằng nếu chúng ta có thể tính toán bằng cách này hay cách
khác xác suất điều kiện, cho đến tận thời điểm kết quả tốt nhất cuối cùng tốt nhất
của thực thể công việc là chính xác, thì chúng ta có thể đảm bảo toán học rằng tỉ lệ
lỗi (về trung bình) sẽ kém hơn một vài được mong đợi, bằng cách chuyển đổi
đơn giản cờ được làm không được thiết lập cho đến khi xác suất điều kiện của kết
quả tốt nhất đạt đến ngưỡng .
Để thực hiện ý tưởng này, chúng ta thêm các giá trị tin cậy đến các đối tượng khác
nhau trong hệ thống, được chỉ trong hình 2-1. Ở đây độ tin cậy của một vài đối
tượng X, được viết là , được định nghĩa là xác suất điều kiện để X cho một
kết quả tốt. Có bốn loại độ tin cậy: Độ tin cậy của một máy trạm, độ tin cậy của kết
quả, độ tin cậy của một nhóm kết quả (một nhóm chứa đựng các kết quả giống
nhau) và độ tin cậy của một thực thể công việc. Độ tin cậy của một máy trạm phụ
thuộc vào các hành vi quan sát được của nó như là tính chính xác của kết quả, số
lượng điểm kiểm tra mà nó đã vượt qua... Độ tin cậy của một kết quả thì bằng độ tin
cậy của máy trạm trả về kết quả đó. Độ tin cậy của một nhóm các kết quả là xác
suất có điều kiện để kết quả là chính xác. Cuối cùng độ tin cậy của một thực thể
công việc là độ tin cậy của nhóm tốt nhất được xác minh qua quá trình xử lý biểu
quyết.
Trong suốt quá trình chạy một lô song song, độ tin cậy của các đối tượng trong hệ
thống thay đổi hoặc là: (1) các máy trạm qua được các kiểm tra điểm (vì vậy tăng
độ tin cậy các kết quả của chúng và các nhóm chúng tham gia) (2) các kết quả ánh
xạ được nhận cho thực thể công việc giống nhau (vì vậy hình thành kết quả nhóm),
(3) hoặc máy trạm có thể bị bắt (vì các kết quả chúng không hợp lệ, và giảm độ tin
cậy của nhóm các kết quả liên quan đến chúng ). Giả sử có đủ các máy trạm tốt, độ
tin cậy của mỗi thực thể công việc W thậm chí hướng đến ngưỡng như máy chủ thu
thập đủ kết quả ánh xạ cho một thực thể công việc W, hoặc các máy phân giải các
kết quả trong W đủ qua các kiểm tra điểm để làm cho các độ tin cậy cảu các kết quả
35
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
của chúng tăng lên hoặc đồng thời. Khi điều này xảy ra, thực thể công việc được
đánh dấu được là và máy chủ dùng quay lại gán các công việc đến các máy trạm.
Điều này tiếp tục xảy ra cho tất cả các thực thể công việc chưa được làm cho đến
tận khi tất cả các thực thể công việc hướng đến ngưỡng được mong đợi
, tại điểm nào đó, cuối của lô. Tại điểm này, giả sử rằng các độ tin cậy
của chúng ta là các ước lượng của các xác suất có điều kiện tốt, phân số của các kết
quả cuối cùng, kết quả sẽ là chính xác, nên lớn hơn và vì vậy tỉ lệ lỗi hầu hết tại
.
Chú ý rằng giản đồ này tự động cân đối hiệu năng cho tính chính xác. Nó tương tự
như biểu quyết ngoại trừ rằng ở đây, m không được xác minh trước, nhưng được
xác minh động, bằng làm điều chỉnh lớn như là nó yêu cầu cho một thực thể công
việc. Tuy nhiên không giống như biểu quyết truyền thống, chúng ta không phải
quay lại làm một thực thể công việc nhiều lần (hoặc tất cả) nếu kết quả của nó được
làm bởi một máy trạm đã được kiểm tra điểm nhiều lần và vì vậy có một độ tin cậy
rất cao. Theo cách này, một thực thể công việc chỉ lặp lại một số lần để đạt được
mức độ quan tâm mong đợi, nhưng không nhiều. Điều này làm cho chịu lỗi dựa trên
độ tin cậy rất hiệu quả, và được chỉ trong phần 4.3, cho phép nó đạt được tỉ lệ lỗi rất
thấp với độ dư thừa ít.
2.3.2 Tính toán độ tin cậy
Quyết định chính trong kĩ thuật này là tính toán các giá trị độ tin cậy là chính xác.
Thông thường, có nhiều các giá trị độ tin cậy có thể, tương ứng đối với các cách
quan sát trạng thái hiện thời của hệ thống khác nhau, thêm vào đó là các cách tính
toán khác nhau hoặc ước lượng xác suất điều kiện của tính chính xác dựa trên các
quan sát. Trong phần này chúng ta sẽ biểu diễn các giá trị đặc biệt mà chúng ta nhận
thấy là hiệu quả.
Độ tin cậy của một máy trạm không có kiểm tra điểm là:
Độ tin cậy của một máy trạm có kiểm tra điểm và danh sách đen, giả sử nó đã qua k
36
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
lần kiểm tra là:
Độ tin cậy của một máy trạm có kiểm tra điểm và không có danh sách đen được ước
lượng là:
Nếu một thực thể công việc có g nhóm, thì độ tin cậy của nhóm a, cho ,
là xác suất có điều kiện để mà tất cả các kết quả trong nhóm a là đúng, giả sử rằng
kết quả các nhóm khác là sai. Xác suất này có thể được ước lượng là:
Tính độ tin cậy độ tin cậy của một vài đối tượng cho các trường hợp khác nhau
được tính toán
ở đây P(Ga tốt) là xác suất để tất cả các kết quả của là tốt:
Và ở đây P(Ga xấu) là xác suất để tất cả các kết quả là xấu:
Cuối cùng, độ tin cậy của một thực thể công việc là độ tin cậy của nhóm có độ tin
cậy cao nhất.
2.3.3 Ứng dụng sự tin cậy
2.3.3.1 Kết hợp biểu quyết và kiểm tra điểm
Mặc dù chịu lỗi dựa trên độ tin cậy có thể được dùng với biểu quyết hoặc kiểm tra
điểm một mình, nhưng tốt nhất dùng tích hợp biểu quyết và kiểm tra điểm cùng
37
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
nhau. Trong trường hợp này, chúng ta bắt đầu với tất cả các máy trạm hiệu quả có
một độ tin cậy và bắt đầu tập hợp các kết quả. Nếu ngưỡng độ tin cậy là đủ
thấp, và các lô là dài, thì bằng thời điểm chúng ta đi một vòng hàng đợi công việc
quay tròn, các máy trạm có thể giành được đủ độ tin cậy bằng việc vượt qua các
kiểm tra điểm để làm cho các kết quả của chúng được chấp nhận. Trong trường hợp
này chúng ta không cần làm biểu quyết và chúng ta có thể hướng tới tỉ lệ lỗi mong
đợi với chỉ độ dư thừa bởi các công việc giám sát. Nếu là cao, thì kiểm
tra điểm không đủ, do đó chúng ta quay lại gán công việc, tâp hợp các kết quả dư
thừa, và biểu quyết.
Nếu chúng ta không dùng kiểm tra điểm, chúng ta thậm chí hướng đến ngưỡng sau
một sự chậm chễ tương ứng xấp xỉ là . Tuy nhiên kiểm tra
điểm giảm hiệu quả thuật toán này, , tuyến tính với thời gian, và vì vậy
cho ta hướng tới ngưỡng mong đợi ít thời gian hơn nhiều so với biểu quết một
mình.
Một thuận lợi khác của việc dùng độ tin cậy đó là nó vẫn làm việc tốt thậm chí
chúng ta không dùng danh sách đen. Bằng việc dùng giá trị độ tin cậy từ phương
trình 6, chúng ta đã làm mất tác dụng một cách hiệu quả ảnh hưởng của các máy
phá hoại chỉ làm một ít công việc và rồi sau đó gia nhập nút mới.
2.3.3.2 Kiểm tra điểm bằng biểu quyết
Mặc dù dùng độ tin cậy với biểu quyết và kiểm tra điểm thực sự làm việc khá tốt,
chúng ta vẫn có thể thu được nhiều hiệu năng hơn bằng việc dùng biểu quyết cho
kiểm tra điểm.
Từ giờ trở đi, chúng ta giả sử rằng một máy chủ kiểm tra điểm một máy trạm bằng
cách cho nó một loại công việc mà kết quả chính xác đã thực sự biết. Bởi vậy điều
này ám chỉ rằng hoặc máy chủ bản thân nó, hoặc một vài máy trạm có đầy đủ độ tin
cậy, phải làm các công việc để xác minh kết quả chính xác, chúng ta thường giả sử
rằng yêu cầu là nhỏ (nghĩa là kém hơn 10%). Bởi vì xấp xỉ là , điều này giới
hạn tỉ lệ tại đó độ tin cậy tăng vì vậy giới hạn hiệu năng.
38
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
May mắn, chúng ta có thể đạt tới hiệu năng tốt hơn nhiều bằng việc dùng biểu quyết
dựa trên độ tin cậy như là một kĩ thuật kiểm tra điểm. Đó là, bất cứ khi nào các
nhóm kết quả của một thực thể công việc hướng đến ngưỡng, chúng ta tăng giá trị k
của các máy trạm đã thực hiện kết quả trong nhóm chiến thắng trong khi đó chúng
ta đối xử với các máy trạm khác trong nhóm thất bại như là chúng bị trượt trong
kiểm tra điểm (nghĩa là chúng ta sẽ gỡ bỏ chúng từ hệ thống và làm mất hiệu lực
các kết quả khác của chúng).
Nếu chúng ta giả sử rằng chúng ta phải làm tất cả các công việc ít nhất hai lần, điều
này ám chỉ rằng tất cả các kết quả trả về bởi một máy trạm sẽ phải tham gia vào quá
trình biểu quyết, thì dùng những biểu quyết này để kiểm tra điểm một máy trạm ám
chỉ rằng một máy trạm sẽ lấy kiểm tra điểm ít nhất lần – có nghĩa lần
nhiều hơn trước. Điều này muốn chỉ ra rằng tỉ lệ lỗi tỉ lệ nghịch với độ tin cậy của
các máy trạm tốt, máy được quay vòng để cho phép biểu quyết thực hiện nhanh
hơn. Chú ý rằng kĩ thuật này chỉ có thể được làm bằng dùng độ tin cậy dựa trên biểu
quyết để bắt đầu. Tin tưởng dùng biểu quyết theo số đông truyền thống để kiểm tra
điểm các máy trạm là nguy hiểm bởi vì thay đổi của các máy phá hoại thắng phiếu
các máy tốt và vì vậy chúng bị cho vào trong danh sách đen, điều này là đáng kể
nếu f không nhỏ. Biểu quyết dựa trên độ tin cậy làm việc bởi vì nó đảm bảo rằng
chúng ta không biểu quyết cho đến khi xác suất để biểu quyết đúng là đủ cao. Vì
vậy, nó giới hạn xác suất của các máy trạm tốt đang thắng phiếu đến một giá trị rất
nhỏ. Tuy nhiên chú ý rằng một vài “bootstraping” được yêu cầu ở đây. Đó là, chúng
ta không thể bắt đầu dùng biểu quyết cho kiểm tra điểm cho đến khi các nhóm kết
quả thực sự chi bắt đầu hướng đến ngưỡng và biểu quyết. Điều này ám chỉ rằng: (1)
Kiểm tra điểm bằng biểu quyết chỉ có lợi khi sự dư thừa thực sự nhỏ hơn 2, và (2)
chúng ta cần duy trì bình thường kiểm tra điểm (ít nhất cho một vài lô đầu tiên) để
cho phép các máy trạm thu được đủ độ tin cậy để hướng đến ngưỡng đủ sớm.
2.4 Khảo sát một số giản đồ lập lịch.
Trong phần này, tôi sẽ khảo sát một số giản đồ lập lịch sử dụng trong các hệ thống
tính toán tình nguyện sử dụng kĩ thuật chịu lỗi. Trước tiên tôi sẽ khảo sát giản đồ
39
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Round Robin thông thường dùng bởi hàng đợi công việc lập lịch tham lam[8]. Tiếp
đó tôi sẽ thảo luận giản đổ Round Robin dựa trên sự ưu tiên về khả năng thực hiện
công việc.
2.4.1 Lập lịch Round Robin
Trong công việc trước, Sarmenta đã đề xuất hàng đợi công việc lập lịch tham lam
cái mà làm việc theo cách thức Round Robin (RR). Trong giản đồ này, các nhiệm
vụ được đặt vào một hang đợi công việc. Với mỗi máy trạm, máy chủ sẽ tiếp tục
cho một điểm kiểm tra với tỉ lệ s. Tại thời điểm bắt đầu, mọi máy trạm có độ tin cậy
là 1− f (phương trình. 4.1). Ngay khi máy chủ nhận một kết quả, nó sẽ tính toán độ
tin cậy của kết quả đó. Nếu độ tin cậy không lớn hơn ngưỡng được định nghĩa trước
thì nhiệm vụ sau đó sẽ được gửi quay trở lại hàng đợi để thực hiện lại. Ngược lại,
nhiệm vụ được hoàn thành. Xử lý sẽ tiếp tục cho đến khi không còn nhiệm vụ nào
trong hàng đợi công việc. Nhận thấy rằng độ tin cậy của các nhiệm vụ tăng lên theo
thời gian bởi vì nhiệm vụ (1) được thực hiện bởi một vài máy trạm đã thực sự vượt
qua được một vài điểm kiểm tra hoặc (2) nhiệm vụ được thực hiện nhiều lần trên
một máy trạm tốt, vì vậy độ tin cậy của thực thể kết quả có thể được tăng lên bằng
cách dùng của kĩ thuật biểu quyết (3) thậm chí các nhiệm vụ được thực thi trên một
vài máy trạm không tốt, nhưng phân số phá hoại f thì rất nhó, vì vậy độ tin cây của
máy đó vẫn tăng bởi kĩ thuật biểu quyết cơ bản. Theo thời gian, tất cả các nhiệm vụ
sẽ có kết quả vượt qua ngưỡng và quá trình tính toán được kết thúc.
Tôi có thể tóm tắt giản đồ lập lịch Round Robin được dùng bởi hàng đợi công việc
tham lam dựa trên độ tin cậy như sau.
Mã giả lập của giản đồ Round Robin
Đẩy các nhiệm vụ vào trong hàng đợi nhiệm vụ;
Đẩy các máy trạm vào trong hàng đợi máy trạm;
Làm song song (Kiểm tra điểm):
While (Không dừng) do
Kiểm tra điểm mỗi máy trạm với tỉ lệ s;
If (Máy trạm vượt qua được kiểm tra điểm)
40
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Quay lại tính độ tin cậy của máy trạm theo phương
trình 2.2 hoặc2.3;
Else
Lưu vào danh sách đen các máy trạm;
EndIf
EndWhile;
Làm song song (Gán nhiệm vụ):
While (Không dừng) do
Lấy một nhiệm vụ và một máy trạm có khả năng;
Gán nhiệm vụ đến máy trạm;
EndWhile
Làm song song (Kiểm tra độ tin cậy):
On (Nhận một kết quả) do
Begin
Đẩy máy trạm đến hàng đợi máy trạm ;
Tính độ tin cậy của kết quả Cr theo phương trình 2.4, 2.5,
2.6;
If (Cr > )
Đánh dấu nhiệm vụ đã hoàn thành;
Else
Đẩy nhiệm vụ lại hàng đợi nhiệm vụ;
Elseif
End
Thuật toán trên không đề cập về thứ tự mà chúng ta gán một nhiệm vụ cho một máy
trạm. Đấy là bởi vì nó giả sử rằng mọi tính toán tình nguyện có khả năng giống
nhau, vì vậy thứ tự thực thi là không quan trọng cho hiệu năng của toàn bộ hệ
thống. Tôi quan tâm nhiều hơn đến kịch bản thực tế ở đó mỗi máy tính tình nguyện
có một khả năng tính toán khác nhau. Tôi vẫn giả sử rằng mọi nhiệm vụ có kích cỡ
giống nhau. Vì vậy thời gian thực thi trên các máy tính nhanh hơn thì nhỏ hơn trên
41
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
các máy tính chậm hơn. Bây già quan tâm đến hai trường hợp:
(1) Số lượng nhiệm vụ nhỏ hơn nhiều so với số lượng các máy tính.
(2) Số lượng nhiệm vụ lớn hơn nhiều so với số lượng máy tính.
Trong trường hợp thứ nhất, một nhiệm vụ sẽ được sao ra và thực thi trên một vài
máy tính tại thời điểm giống nhau. Giả sử rằng một nhiệm vụ được thực hiện lại bởi
k bản sao qua k máy tính và thời gian thực thi của nhiệm vụ này trên k máy tính là
t1≤ t2 ≤...≤ tk, tương ứng.
Có nghĩa là thời gian tời điểm kiểm tra bị lãng phí (ví dụ. thời gian
mà chúng phải đợi từ thực thi bản sao đầu tiên cho đến thực thi bản sao cuối cùng
để thực hiện kiểm tra độ tin cậy). Chú ý rằng nếu các nhiệm vụ được lập lịch để mà
giảm thời gian điểm kiểm tra lãng phí, thì độ tin cậy của kết quả sẽ chẳng bao lâu
đạt đến ngưỡng tin cậy, vì vậy thời gian thực thi chung có thể được giảm đi
Cũng cần chú ý rằng khái niệm thời gian điểm kiểm tra lãng phí không tồn tại trong
trường hợp thứ hai. Đấy là bởi vì có nhiều nhiệm vụ hơn số lượng máy tính, vì vậy
mỗi nhiệm vụ được thực thi chỉ trên một máy tính tại một thời điểm theo cách thức
RR. Trong trường hợp này, một nhiệm vụ không phải đợi cho bản sao của nó được
thực thi.
Từ nhận xét nay, [10] tác giả đã đề xuất một giản đồ lập lịch mới cho kịch bản thứ
nhất được goi là lập lịch Round Robin(dựa trên khả năng thực thi của các máy
trạm), Giản đồ này nhóm các máy tính có khả năng tương tự nhau để giảm thời gian
thực thi toàn bộ.
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
Kĩ thuật lập lịch Round Robin dựa trên sự ưu tiên đó là lấy ra các máy trạm có khả
năng thực hiện các công việc tốt nhất, ứng với các trường hợp thực tế cụ thể của các
hệ thống tính toán tình nguyện đang được triển khai, bằng cách đưa ra các tiêu chí
để chọn ra các máy trạm.
Ý tưởng chính của lập lịch Round Robin dựa trên sự ưu tiên về khả năng tính toán
là giảm thời gian kiểm tra đợi của độ tin cậy của một kết quả. Điều này có thể được
42
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
làm bằng cách nhóm các máy tính tình nguyện vào các nhóm có khả năng tương tự
nhau (ví dụ. thời gian tính toán của một nhiệm vụ đã cho là giống nhau). Trong giản
đồ này, tôi giả sử rằng với một tính toán được cho, mỗi máy tính i ( 0 ≤ i < P ) được
biểu thị bởi một số ước lượng thực ti biểu diễn ước lượng thời gian thực thi của một
nhiệm vụ. Ước lượng này có thể được làm nếu nút máy chủ biết thông tin về các
máy tính tình nguyện như là tốc độ CPU, không gian đĩa rỗi, băng thông của kết nối
mạng… Những thông tin này được cung cấp khi một máy tính tình nguyện đăng kí
vào hệ thống [9].
Giả sử rằng có N nhiệm vụ và P máy trạm và N << P (ví dụ P = X.N). Để nhóm các
máy trạm có khả năng tương tự nhau, tôi áp dụng một sắp xếp tăng theo ti và đặt
mọi máy trạm vào hàng đợi ưu tiên. Mỗi khi máy trạm có khả năng, nó được thêm
vào hàng đợi ưu tiên. Khi một nhiệm vụ cần được thực thi, X máy trạm có khả năng
tính toán lớn nhất(thời gian thực thi nhỏ nhất) trên đỉnh của hàng đợi được lấy ra và
gán cho nhiệm vụ này. Khi nút máy chủ nhận về được kết quả từ tất cả các máy
trạm, nó sẽ thực thi một kiểm tra về độ tin cậy để xác minh nếu kết quả của nhiệm
vụ này là đủ tốt. Nếu độ tin cậy đủ cao, thì nhiệm vụ kết thúc. Mặt khác nhiệm vụ
này được gán lại cho các máy tính tình nguyên. Xử lý này sẽ tiếp tục cho đến khi tất
cả các nhiệm vụ được hoàn thành. Mã giả lập của giản đồ lập lịch này được chỉ định
như sau.
Mã giả lập giản đồ Round Robin dựa trên khả năng thực hiện
Đẩy các nhiệm vụ vào trong hàng đợi nhiệm vụ;
Đẩy các máy trạm vào trong hàng đợi máy trạm;
Làm song song (Kiểm tra điểm):
While (Không dừng) do
Kiểm tra điểm mỗi máy trạm với tỉ lệ s;
If (Máy trạm vượt qua được kiểm tra điểm)
Quay lại tính độ tin cậy của máy trạm theo phương
trình 2.2 hoặc 2.3;
Else
43
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Lưu vào danh sách đen các máy trạm;
EndIf
EndWhile;
Làm song song (Gán nhiệm vụ):
While (Không dừng) do
Lấy một nhiệm vụ chưa kết thúc và X máy trạm có khả
năng;
Gán nhiệm vụ đến X máy trạm;
EndWhile
Làm song song (Kiểm tra độ tin cậy):
On (Nhận một kết quả) do
Begin
Đẩy máy trạm đến hàng đợi máy trạm ;
Tính độ tin cậy của kết quả Cr theo phương trình 2.4, 2.5,
2.6;
If (Cr > )
Đánh dấu nhiệm vụ đã hoàn thành;
Else
Đẩy nhiệm vụ lại hàng đợi nhiệm vụ;
Elseif
End
Chú ý rằng giản đồ lập lịch này chỉ hiệu quả trong trường hợp có nhiều máy trạm
hơn các nhiệm vụ. Mặc dù giản đồ này có thể làm việc cho các trường hợp khác
nhưng hiệu năng sẽ không được cải thiện so với giản đồ Round Robin thông
thường. Tôi nhận thấy rằng trong giản đồ này và giản đồ Round Robin đều chưa
quan tâm đến việc sử dụng độ tin cậy của mỗi máy trạm khi thực thi. Từ nhận xét
trên tôi đã nghiên cứu và đề xuất ra một số thuật toán chịu lỗi dựa trên độ tin cậy
bằng cách kết hợp giưa độ tin cậy và khả năng tính toán.
44
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Chương 3. GIẢN ĐỒ LẬP LỊCH ROUND ROBIN DỰA TRÊN
ĐỘ TIN CẬY
Trong chương 2 chúng ta đã khảo sát một số giản đồ lập lịch như là giản đồ lập lịch
Round Robin và giản đồ lập Round Robin dựa trên sự ưu tin về khả năng tính toán
và nhận thấy rằng các giản đồ trên đều chưa quan tâm đến độ tin cậy của các máy
trạm khi thực thi vì vậy có thể chưa tối ưu được thời gian tính toán của hệ thống.
Trong chương này tôi sẽ trình bày về các giản đồ lập lịch dựa trên độ tin cậy cùng
với việc kết hợp với khả năng tính toán của các máy trạm để tối ưu được thời gian
tính toán của hệ thống.
3.1 Giản đồ lập lịch Round Robin dựa trên sự ưu tiên về độ tin cậy
Ý tưởng chính của giản đồ lập lịch này là chọn ra máy có độ tin cậy cao nhất để
thực thi công việc. Trong giản đồ này, với mỗi tính toán được cho, mỗi máy tính i (
0 ≤ i < P ) được biểu thị bởi một độ tin cậy . Tại thời điểm bắt đầu, mọi máy
trạm có độ tin cậy là 1− f (phương trình. 3). Để thực hiện việc lấy máy trạm có độ
tin cậy cao nhất, tôi áp dụng một sắp xếp theo , nếu bằng nhau ta sẽ sắp xếp
theo độ ưu tiên khả năng thực hiện. Và đặt các máy trạm vào hàng đợi ưu tiên. Một
khi máy trạm có khả năng nó sẽ được thêm vào hàng đợi ưu tiên. Khi một nhiệm vụ
cần được thực thi, máy trạm có độ tin cậy cao nhất trên đỉnh của hàng đợi sẽ được
lấy ra và gán cho nhiệm vụ. Với mỗi máy trạm, máy chủ sẽ tiếp tục cho một điểm
kiểm tra với tỉ lệ q. Ngay khi máy chủ nhận một kết quả, nó sẽ tính toán độ tin cậy
của kết quả đó. Nếu độ tin cậy không lớn hơn ngưỡng được định nghĩa trước thì
nhiệm vụ sau đó sẽ được gửi quay trở lại hàng đợi để thực hiện lại. Mặt khác, nhiệm
vụ được hoàn thành. Xử lý sẽ tiếp tục cho đến khi không còn nhiệm vụ nào trong
hàng đợi công việc. Theo thời gian, tất cả các nhiệm vụ sẽ có kết quả vượt qua
ngưỡng và quá trình tính toán được kết thúc.
Dưới đây là một ví dụ đơn giản về việc áp dụng thuật toán này.
Cho một hệ thống tính toán tình nguyện bao gồm 10 máy trạm và 5 công việc cần
45
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
thực hiện bởi hệ thống. Biết rằng hệ thống sử dụng kĩ thuật kiểm tra điểm bằng biểu
quyết, tỉ lệ lỗi chấp nhận được của hệ thống là , phân số mắc lỗi ,
tỉ lệ phá hoại và các thông số về độ tin cậy và thời gian thực hiện nhiệm
vụ của các máy trạm được cho như hình 4.1. Giả sử máy trạm 3 và 6 là các máy phá
hoại.
Crw = 0
Công việc 1
Crw = 0
Công việc 2
Crw = 0
Công việc 3
Crw = 0
Công việc 4
Crw = 0
Công việc 5
Công việc chưa được làm tiếp
Hình 3-1. Mô tả hệ thống tính toán tình nguyện
Dưới đây là sơ đồ hình vẽ các bước thực hiện thuật toán:
Worker P1
K 0
Cr 0.8
T 0.5
Worker P2
K 0
Cr 0.8
T 1
Worker P3
K 0
Cr 0.8
T 1.5
Worker P4
K 0
Cr 0.8
T 2
Worker P5
K 0
Cr 0.8
T 2.5
Worker P6
K 0
Cr 0.8
T 3
Worker P7
K 0
Cr 0.8
T 3.5
Worker P8
K 0
Cr 0.8
T 4
Worker P9
K 0
Cr 0.8
T 4.5
Worker P10
K 0
Cr 0.8
T 5
46
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
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
47
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
48
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
49
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
50
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Hoàn thành
Crw = 0.99902
Công việc 1
Crw = 0.92753
Công việc 2
Hoàn thành
Crw = 0.99992
Công việc 3
Crw = 0.94117
Công việc 4
Crw = 0.94117
Công việc 5
Crc = 0.99902
pid Crg
P1 0.80000
0.94117P2
Worker P1
K 23
Công việc chưa được làm tiếp
Crc = 0.92753
pid Crg
P3 0.80000
0.94117P4
Crc = 0.99992
pid Crg
P5 0.80000
0.44445P6
Crc = 0.94117
pid Crg
P7 0.80000
0.94117P8
Crc = 0.94117
pid Crg
P9 0.80000
0.94117P10
Cr 0.99166
T 0.5
Worker P2
K 14
Cr 0.98666
T 1
Worker P3
K 0
Cr 0.8
T 1.5
Worker P4
K 0
Cr 0.8
T 2
Worker P5
K 4
Cr 0.95999
T 2.5
Worker P6
K 0
Cr 0.8
T 3
Worker P7
K 0
Cr 0.8
T 3.5
Worker P8
K 0
Cr 0.8
T 4
Worker P9
K 0
Cr 0.8
T 4.5
Worker P10
K 0
Cr 0.8
T 5
SLOWDOWN = 5
P1 0.98461
0.99610P2
0.99902P21
P1 P2 P7 P8 P9 P10 P7 P8 P1 P1
Danh sách máy trạm có khả năng
P3 0.76190
0.92753P4
P1 0.76190
0.99605P2
P1 0.99992P3 -
-P4
P5 -
-P6
P1 -
-P2
10
51
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
52
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
53
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Mã giả lập của giản đồ lập lịch này được chỉ định như sau.
54
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Mã giả lập của giản đồ Round Robin dựa trên độ tin cậy
Đẩy các nhiệm vụ vào trong hàng đợi nhiệm vụ;
Đẩy các máy trạm vào trong hàng đợi máy trạm;
Làm song song (Kiểm tra điểm):
While (không dừng) do
Kiểm tra điểm mỗi máy trạm với tỉ lệ s;
If (máy trạm vượt qua được kiểm tra điểm)
Quay lại tính độ tin cậy của máy trạm theo phương
trình 4.2 hoặc4.3;
Else
Lưu vào danh sách đen các máy trạm;
EndIf
EndWhile;
Làm song song (Gán nhiệm vụ):
While (không dừng) do
Lấy một nhiệm vụ và một máy trạm có độ tin cậy cao
nhất;
Gán nhiệm vụ đến máy trạm;
EndWhile
Làm song song (Kiểm tra độ tin cậy):
On (Nhận một kết quả) do
Begin
Đẩy máy trạm đến hàng đợi máy trạm ;
Tính độ tin cậy của kết quả Cr theo phương trình 4.4, 4.5,
4.6;
If (Cr > )
Đánh dấu nhiệm vụ đã hoàn thành;
Else
Đẩy nhiệm vụ lại hàng đợi nhiệm vụ;
55
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Elseif
End
Trong sơ đồ hình vẽ các bước của giản đồ lập lịch dựa trên độ tin cậy hình 4.2, ta
nhận thấy rằng độ tin cậy của các công việc 2 và 3 bị giảm đi khi máy phá hoại trả
về kết quả sai như được chỉ trong bước 6 và bước 7, vì độ tin cậy của một thực thể
công việc là độ tin cậy của nhóm có độ tin cậy lớn nhất. Trong bước 8 sau khi các
máy trạm 3 và 4 đã thực hiện xong nhiệm vụ máy 2, vì độ tin cậy của nhiệm vụ
chưa đạt tới ngưỡng tin cậy chấp nhận được do đó nó được quay lại gán cho một số
máy trạm thực hiện. Ở trong bước 8 của giản đồ lập lịch thì nhiệm vụ 2 được thực
hiện lại bởi hai máy trạm 3 và 4 tiếp vì máy 3 bây giờ đang cho kết quả giả mạo vì
vậy làm cho độ tin cậy của nhiệm vụ 2 tiếp tục giảm xuống và lại tăng lên khi máy
trạm 4 thực hiện xong nhiệm vụ. Ta nhận thấy rằng có thể thay thế máy 3 bằng một
máy trạm tin cậy khác để tăng độ tin cậy của nhiệm vụ 2 ví dụ như máy trạm 5
trong tình huống trên và từ đó giảm thời gian tính toán của nhiệm vụ 2 từ đó có thể
dẫn đến giảm thời gian tính toán của toàn bộ hệ thống. Từ quan sát này, tôi đã
nghiên cứu và đề xuất ra một thuật toán mới gọi là giản đồ lập lịch kiểm thử dựa
trên độ tin cậy để có thể chọn ra máy trạm tốt nhất để thực thi công việc. Bằng cách
kết hợp giữa độ ưu tiên về độ tin cậy và khả năng thực hiện. Giản đồ này sẽ lấy ra
các máy tính có khả năng tính toán và độ tin cậy tốt nhất để giảm thời gian thực thi
của toàn bộ hệ thống.
3.2 Giản đồ lập lịch Round Robin dựa trên kiểm thử độ tin cậy
Vì độ tin cậy của một thực thể công việc là độ tin cậy của nhóm có độ tin cậy lớn
nhất vì vậy việc chọn một máy tính để tiếp tục thực hiện một thực thể công việc để
giúp cho tăng độ tin cậy của nhóm là vô cùng quan trọng. Trong giản đồ lập lịch
Round Robin dựa trên sự ưu tiên về độ tin cậy khi một thực thể công việc chưa đạt
tới ngưỡng tin cậy thì nó sẽ lấy một máy trạm có khả năng và có độ tin cậy lớn nhất
để thực thi công việc nhưng có một vấn đề là có thể máy trạm có độ tin cậy lớn nhất
đấy lại có thể cho kết quả giả mạo và làm giảm độ tin cậy của thực thể công việc,
chính từ nhận xét này mà tôi đã đề xuất ra giản đồ lập lịch Round Robin dựa trên
56
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
kiểm thử độ tin cậy. Ý tưởng chính của giản đồ này là chọn ra một máy trạm phù
hợp nhất để thực thi nhiệm vụ sao cho tăng độ tin cậy của nhiệm vụ. Trong giản đồ
này, với mỗi nhiệm vụ được cho T ta có Cr là độ tin cậy của nhiệm vụ, ta có là
độ tin cậy được ước lượng của nhiệm vụ T khi máy tính i (0 ≤ i < P ) thực hiện
nhiệm vụ, Av(i) là khả năng thực hiện nhiệm vụ của máy i. Tại thời điểm ban đầu,
mọi máy trạm i đều có độ tin cậy là 1− f (phương trình. 3). Khi các nhiệm vụ cần
được thực thi, với mỗi nhiệm vụ ta sẽ chọn ra một máy trạm phù hợp nhất để thực
thi, nếu không chọn được một máy trạm phù hợp thì ta sẽ đẩy nhiệm vụ đó vào lại
hàng đợi nhiệm vụ để trờ thêm một số máy trạm khác nhàn rỗi để lựa chọn, và lấy
nhiệm vụ khác trong hàng đợi để tìm máy trạm phù hợp. Với mỗi máy trạm, máy
chủ sẽ tiếp tục cho một điểm kiểm tra với tỉ lệ q. Ngay khi máy chủ nhận một kết
quả, nó sẽ tính toán độ tin cậy của kết quả đó. Nếu độ tin cậy không lớn hơn
ngưỡng được định nghĩa trước thì nhiệm vụ sau đó sẽ được gửi quay trở lại hàng
đợi để thực hiện lại. Mặt khác, nhiệm vụ được hoàn thành. Xử lý sẽ tiếp tục cho đến
khi không còn nhiệm vụ nào trong hàng đợi công việc. Theo thời gian, tất cả các
nhiệm vụ sẽ có kết quả vượt qua ngưỡng và quá trình tính toán được kết thúc.
Để thực hiện lấy máy trạm phù hợp nhất để thực hiện nhiệm vụ, máy chủ sẽ thực
hiện các so sánh về độ tin cây và khả năng tính toán .Trước tiên máy chủ sẽ chỉ lấy
các máy trạm có Cri > Cr (*). Trong số các máy tram đã lấy đó nếu tồn tại một
nhóm các máy trạm có (**) thì máy chủ sẽ lấy một máy trạm trong
số đó. Trong số các máy trạm thỏa mãn (**) máy chủ sẽ lấy ra máy trạm có khả
năng thực hiện nhiệm vụ là tốt nhất. Trong trường hợp không tồn tại máy trạm i nào
thỏa mãn (**) thì máy chủ sẽ lấy máy trạm trong nhóm thỏa mãn (*) và không thỏa
mãn (**). Việc lấy máy trạm trong nhóm này thì phụ thuộc vào tiêu chí lấy, máy
chủ có thể lấy máy trạm có gần nhất hoặc máy trạm có khả năng tính
toán tốt nhất trong số các máy trạm đó. Nếu trong trường hợp không có máy trạm
nào thỏa mãn (*) thì máy chủ sẽ không chọn máy trạm nào mà đợi thêm một số máy
trạm mới để chọn.
57
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Vì phụ thuộc vào kết quả thực hiện nhiệm vụ của máy trạm i là đúng hay sai.
Do đó trong quá trình tính toán , với các máy phá hoại i máy chủ cần phải ước
đoán được kết quả trả về của máy trạm i. Để ước đoán kết quả trả về của máy phá
hoại i là đúng hay sai, máy chủ sẽ dựa vào tỉ lệ lỗi s của máy trạm i để giả định kết
quả. Nếu s ≥ 0.5 thì máy chủ coi như máy phá hoại i trả về kết quả sai, trường hợp
còn lại là kết quả đúng. Nếu trong trường hợp thực tế một nút mạng mới lần đầu
tham gia vào hệ thống tình nguyện và chưa rõ giá trị của s thì máy chủ coi như kết
quả trả về của máy trạm đó khi thực hiện nhiệm vụ T là chính xác để thực hiên tính
. Dưới đây là minh họa cho thuật toán này bằng ví dụ trong phần 4.1 với hệ
thống tính toán tình nguyện được cho trong hinh 4.1. Các bước 1, 2, 3, 4, 5, 6, 7
tương tự trên hình 3.2.
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
58
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Hoàn thành
Crw = 0.99902
Công việc 1
Crw = 0.92753
Công việc 2
Hoàn thành
Crw = 0.99992
Công việc 3
Crw = 0.94117
Công việc 4
Crw = 0.80000
Công việc 5
Crc = 0.99902
pid Crg
P1 0.80000
0.94117P2
Worker P1
K 23
Công việc chưa được làm tiếp
Crc = 0.92753
pid Crg
P3 0.80000
0.94117P4
Crc = 0.99992
pid Crg
P5 0.80000
0.44445P6
Crc = 0.94117
pid Crg
P7 0.80000
0.94117P8
Crc = 0.80000
pid Crg
P9 0.80000
0P10
Cr 0.99166
T 0.5
Worker P2
K 14
Cr 0.98666
T 1
Worker P3
K 0
Cr 0.8
T 1.5
Worker P4
K 0
Cr 0.8
T 2
Worker P5
K 4
Cr 0.95999
T 2.5
Worker P6
K 0
Cr 0.8
T 3
Worker P7
K 0
Cr 0.8
T 3.5
Worker P8
K 0
Cr 0.8
T 4
Worker P9
K 0
Cr 0.8
T 4.5
Worker P10
K 0
Cr 0.8
T 5
SLOWDOWN = 4.5
P1 0.98461
0.99610P2
0.99902P21
P3 P6 P1 P9 P5 P6 P7 P8 P1 P1
Danh sách máy trạm có khả năng
P3 0.76190
0.92753P4
P1 0.76190
0.99605P2
P1 0.99992
-P2
P4 -
-P5
P7 -
-P8
9
Hoàn thành
Crw = 0.99902
Công việc 1
Crw = 0.92753
Công việc 2
Hoàn thành
Crw = 0.99992
Công việc 3
Crw = 0.94117
Công việc 4
Crw = 0.94117
Công việc 5
Crc = 0.99902
pid Crg
P1 0.80000
0.94117P2
Worker P1
K 23
Công việc chưa được làm tiếp
Crc = 0.92753
pid Crg
P3 0.80000
0.94117P4
Crc = 0.99992
pid Crg
P5 0.80000
0.44445P6
Crc = 0.94117
pid Crg
P7 0.80000
0.94117P8
Crc = 0.94117
pid Crg
P9 0.80000
0.94117P10
Cr 0.99166
T 0.5
Worker P2
K 14
Cr 0.98666
T 1
Worker P3
K 0
Cr 0.8
T 1.5
Worker P4
K 0
Cr 0.8
T 2
Worker P5
K 4
Cr 0.95999
T 2.5
Worker P6
K 0
Cr 0.8
T 3
Worker P7
K 0
Cr 0.8
T 3.5
Worker P8
K 0
Cr 0.8
T 4
Worker P9
K 0
Cr 0.8
T 4.5
Worker P10
K 0
Cr 0.8
T 5
SLOWDOWN = 5
P1 0.98461
0.99610P2
0.99902P21
P3 P6 P1 P9 P2 P10 P7 P8 P1 P1
Danh sách máy trạm có khả năng
P3 0.76190
0.92753P4
P1 0.76190
0.99605P2
P1 0.99992P4 -
-P5
P7 -
-P8
10
P1 -
-P2
59
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Hoàn thành
Crw = 0.99902
Công việc 1
Crw = 0.92753
Công việc 2
Hoàn thành
Crw = 0.99992
Công việc 3
Crw = 0.94117
Công việc 4
Hoàn thành
Crw = 0.99947
Công việc 5
Crc = 0.99902
pid Crg
P1 0.80000
0.94117P2
Worker P1
K 26
Công việc chưa được làm tiếp
Crc = 0.92753
pid Crg
P3 0.80000
0.94117P4
Crc = 0.99992
pid Crg
P5 0.80000
0.44445P6
Crc = 0.94117
pid Crg
P7 0.80000
0.94117P8
Crc = 0.99947
pid Crg
P9 0.80000
0.94117P10
Cr 0.99259
T 0.5
Worker P2
K 14
Cr 0.98666
T 1
Worker P3
K 0
Cr 0.8
T 1.5
Worker P4
K 0
Cr 0.8
T 2
Worker P5
K 4
Cr 0.95999
T 2.5
Worker P6
K 0
Cr 0.8
T 3
Worker P7
K 0
Cr 0.8
T 3.5
Worker P8
K 0
Cr 0.8
T 4
Worker P9
K 0
Cr 0.8
T 4.5
Worker P10
K 0
Cr 0.8
T 5
SLOWDOWN = 5.5
P1 0.98461
0.99610P2
0.99902P21
P3 P6 P1 P9 P10 P10 P7 P8 P1 P1
Danh sách máy trạm có khả năng
P3 0.76190
0.92753P4
P1 0.76190
0.99605P2
P1 0.99992P4 -
-P5
P7 -
-P8
11
P1 0.99947
-P2
60
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Hoàn thành
Crw = 0.99902
Công việc 1
Hoàn thành
Crw = 0.99979
Công việc 2
Hoàn thành
Crw = 0.99992
Công việc 3
Crw = 0.94117
Công việc 4
Hoàn thành
Crw = 0.99947
Công việc 5
Crc = 0.99902
pid Crg
P1 0.80000
0.94117P2
Worker P1
K 32
Công việc chưa được làm tiếp
Crc = 0.99979
pid Crg
... ...
0.98084P4
Crc = 0.99992
pid Crg
P5 0.80000
0.44445P6
Crc = 0.94117
pid Crg
P7 0.80000
0.94117P8
Crc = 0.99947
pid Crg
P9 0.80000
0.94117P10
Cr 0.99393
T 0.5
Worker P2
K 14
Cr 0.98666
T 1
Worker P3
K 0
Cr 0.8
T 1.5
Worker P4
K 18
Cr 0.98947
T 2
Worker P5
K 10
Cr 0.98181
T 2.5
Worker P6
K 0
Cr 0.8
T 3
Worker P7
K 0
Cr 0.8
T 3.5
Worker P8
K 0
Cr 0.8
T 4
Worker P9
K 0
Cr 0.8
T 4.5
Worker P10
K 0
Cr 0.8
T 5
SLOWDOWN = 7
P1 0.98461
0.99610P2
0.99902P21
P3 P6 P1 P9 P10 P2 P4 P5 P1 P1
Danh sách máy trạm có khả năng
P5 0.99514
0.99979P1
P1 0.76190
0.99605P2
P1 0.99992P2 -
P7 -
-P8
13
P1 0.99947
Hoàn thành
Crw = 0.99902
Công việc 1
Hoàn thành
Crw = 0.99514
Công việc 2
Hoàn thành
Crw = 0.99992
Công việc 3
Crw = 0.99610
Công việc 4
Hoàn thành
Crw = 0.99947
Công việc 5
Crc = 0.99902
pid Crg
P1 0.80000
0.94117P2
Worker P1
K 32
Công việc chưa được làm tiếp
Crc = 0.99979
pid Crg
... ...
0.98084P4
Crc = 0.99992
pid Crg
P5 0.80000
0.44445P6
Crc = 0.99610
pid Crg
P7 0.80000
0.94117P8
Crc = 0.99947
pid Crg
P9 0.80000
0.94117P10
Cr 0.99393
T 0.5
Worker P2
K 14
Cr 0.98666
T 1
Worker P3
K 0
Cr 0.8
T 1.5
Worker P4
K 18
Cr 0.98947
T 2
Worker P5
K 10
Cr 0.98181
T 2.5
Worker P6
K 0
Cr 0.8
T 3
Worker P7
K 0
Cr 0.8
T 3.5
Worker P8
K 0
Cr 0.8
T 4
Worker P9
K 0
Cr 0.8
T 4.5
Worker P10
K 0
Cr 0.8
T 5
SLOWDOWN = 8
P1 0.98461
0.99610P2
0.99902P21
P3 P6 P7 P9 P10 P8 P4 P5 P1 P1
Danh sách máy trạm có khả năng
P5 0.99514
0.99979P1
P1 0.76190
0.99605P2
P1 0.99992
P7 0.98461
0.99610P8
14
P1 0.99947
-P1
P2 -
61
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Hoàn thành
Crw = 0.99902
Công việc 1
Hoàn thành
Crw = 0.99514
Công việc 2
Hoàn thành
Crw = 0.99992
Công việc 3
Crw = 0.99997
Công việc 4
Hoàn thành
Crw = 0.99947
Công việc 5
Crc = 0.99902
pid Crg
P1 0.80000
0.94117P2
Worker P1
K 37
Công việc chưa được làm tiếp
Crc = 0.99979
pid Crg
... ...
0.98084P4
Crc = 0.99992
pid Crg
P5 0.80000
0.44445P6
Crc = 0.99997
pid Crg
P7 0.80000
0.94117P8
Crc = 0.99947
pid Crg
P9 0.80000
0.94117P10
Cr 0.99473
T 0.5
Worker P2
K 14
Cr 0.98666
T 1
Worker P3
K 0
Cr 0.8
T 1.5
Worker P4
K 18
Cr 0.98947
T 2
Worker P5
K 10
Cr 0.98181
T 2.5
Worker P6
K 0
Cr 0.8
T 3
Worker P7
K 10
Cr 0.98181
T 3.5
Worker P8
K 10
Cr 0.98181
T 4
Worker P9
K 0
Cr 0.8
T 4.5
Worker P10
K 0
Cr 0.8
T 5
SLOWDOWN = 8
P1 0.98461
0.99610P2
0.99902P21
P3 P6 P7 P9 P10 P8 P4 P5 P1 P1
Danh sách máy trạm có khả năng
P5 0.99514
0.99979P1
P1 0.76190
0.99605P2
P1 0.99992
P7 0.98461
0.99610P8
15
P1 0.99947
0.99997P1
P2 -
Hoàn thành
Dưới đây là mã mô phỏng giản đồ này.
Mã giả lập giản đồ lập lịch Round Robin dựa trên kiểm thử độ tin cậy
Đẩy các nhiệm vụ vào trong hàng đợi nhiệm vụ;
Đẩy các máy trạm vào trong hàng đợi máy trạm;
Làm song song (Kiểm tra điểm):
While (Không dừng) do
Kiểm tra điểm mỗi máy trạm với tỉ lệ s;
If (Máy trạm vượt qua được kiểm tra điểm)
Quay lại tính độ tin cậy của máy trạm theo phương
trình 2.2 hoặc 2.3;
Else
Lưu vào danh sách đen các máy trạm;
EndIf
EndWhile;
62
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Làm song song (Gán nhiệm vụ):
While (Không dừng) do
Lấy một nhiệm vụ;
Lấy máy trạm có khả năng;
If (không lấy được máy trạm)
Đẩy nhiệm vụ lại vào hàng đợi nhiệm vụ;
Else
Gán nhiệm vụ đến máy trạm;
EndIf
EndWhile
Làm song song (Kiểm tra độ tin cậy):
On (Nhận một kết quả) do
Begin
Đẩy máy trạm đến hàng đợi máy trạm ;
Tính độ tin cậy của kết quả Cr theo phương trình 4, 5, 6;
If ( )
Đánh dấu nhiệm vụ đã hoàn thành;
Else
Đẩy nhiệm vụ lại hàng đợi nhiệm vụ;
EndIf
End
Mã giả lập lấy máy trạm có khả năng
Đầu vào: Nhiệm vụ muốn thực hiện T, Tiêu chí lấy máy trạm
Type
Đầu ra : Trả về máy trạm có khả năng thực hiện
If (Không có máy trạm) Return NULL;
If (Nhiệm vụ được thực hiện lần đâu tiên)
63
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Lấy máy có thời gian thực hiện ngắn nhất;
Trả về máy lấy được;
EndIf
//Thiết lập máy trạm tốt nhất lấy trong trường hợp
// với Cri là lại độ tin cậy của nhiệm vụ khi có thêm máy trạm i
Thiết lập bWorker;
// Thiết lập máy trạm tốt nhất lấy trong trường hợp
Thiết lập gWorker;
Lấy độ tin cậy ban đầu của nhiệm vụ Cr;
For (i = 0; i < P; i++)
Ước lượng kết quả thực hiện của máy trạm i với nhiệm
vụ;
Tính lại độ tin cậy của nhiệm vụ khi có thêm máy trạm i
( );
If ( >= Cr)
If ( )
// Khả năng thực hiện của máy trạm i là
Av(i)
If
bWorker = i;
EndIf
ElseIf (Tồn tại bWorker)
//Ưu tiên độ tin cậy
If (Type )
If
64
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
((
gWorker = i;
EndIf
Else
//Ưu tiên theo khả năng tính toán
If
gWorker = i;
EndIf
EndIf
Endif
Endif
EndFor
If (Tồn tại bWorker)
return bWorker;
EndIf
If (Tồn tại gWorker)
return gWorker;
EndIf
Return NULL;
Tiếp theo tôi sẽ xác định lại tính khả dụng của các giản đồ lập lịch dựa trên độ tin
cậy bằng các kết quả mô phỏng trong phần 5.
65
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Chương 4. KẾT QUẢ THỰC NGHIỆM
Trong phần này sẽ giới thiệu về chương trình mô phỏng, kịch bản mô phỏng và thảo
luận về các kết quả mô phỏng.
4.1 Chương trình mô phỏng
Trong phần này, tôi xin trình bày về chương trình mô phỏng được dùng trong luận
văn của tôi, chương trình mô phỏng VCSIM. VCSIM được xây dựng trên mô hình
hướng sự kiện. Đây là mô hình sử dụng trong BOINC. VCSIM mô phỏng việc tạo
và phân bố các nhiệm vụ được thực thi trong môi trường có sự thay đổi cao, không
đồng nhất và phân tán. Thêm vào đó nó còn tập hợp và đánh giá hiệu quả của các
nhiệm vụ hoàn thành. VCSIM được viết bằng ngôn ngữ lập trình C.
VCSIM được thiết kế gồm các mô đun chính là: Mô đun quản lý máy trạm, mô đun
quản lý công việc, mô đun mô phỏng. Mô đun quản lý máy trạm thực hiện nhiệm vụ
tạo ra danh sách các máy trạm có độ tin cậy ban đầu giống giau, có thời gian tính
toán khác nhau, tạo ra các máy giả mạo, quản lý các máy trạm như lấy máy trạm từ
hàng đợi theo các tiêu chí lập lịch, đẩy máy trạm vào hàng đợi …Mô đun quản lý
công việc thực hiện nhiệm vụ tạo ra danh sách các nhiệm vụ, gán nhiệm vụ cho các
máy trạm, quản lý hàng đợi công việc, tính độ tin cậy của các nhiệm vụ…Mô đun
mô phỏng thực hiện nhiệm vụ quản lý danh sách các tham số mô phỏng như số lần
mô phỏng, số máy trạm thực hiện, số công việc được thực hiện, phân số lỗi, tỉ lệ lỗi
chấp nhận được, số lần thực hiện lại của các nhiệm vụ, tỉ lệ phá hoại, giản đồ lập
lịch thực hiện, tỉ lệ kiểm tra điểm, tham số hỗ trợ danh sách đen hay không, tham số
hỗ trợ kiểm tra điểm theo biểu quyết hay không …. Thực hiện mô phỏng, hỗ trợ các
hàm hiển thị và đưa ra kết quả.
4.2 Kịch bản mô phỏng
Trong phần này, tôi xác định hiêu quả của giản đồ lập lịch được đề xuất bởi các mô
phỏng. Trong mô phỏng của tôi, một tính toán chứa đựng một danh sách của N các
66
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
nhiệm vụ độc lập có kích cỡ giống nhau và một danh sách P các máy tính tình
nguyện (các máy trạm). Để mô phỏng sự phá hoại của các máy xấu, một phân số f =
0.2 của các máy trạm được lựa chọn ngẫu nhiên là phá hoại. Có hai trường hợp về
số lượng nhiệm vụ và máy trạm được quan tâm.
Trong trường hợp thứ nhất (N > P), có 1500 nhiệm vụ và 500 máy trạm, trong
trường hợp thừ hai (N < P ), có 500 và 1500 máy trạm. Giả sử rằng chính sách danh
sách đen không được áp dụng (ví dụ. máy trạm có thể đệ trình kết quả thậm chí sau
khi nó được dò tìm là một kẻ phá hoại), kĩ thuật kiểm tra điểm dựa trên biểu quyết
được sử dụng trong quá trình mô phỏng. Bởi vì hiệu năng của giản đồ lập lịch dựa
trên độ tin cậy được đánh giá theo tham số sự chậm chễ (ví dụ. tỉ số giữa thời gian
chạy của quá trình tính toán với hoặc không dùng kĩ thuật chịu đựng lỗi), tôi có thể
giả sử rằng thời gian thực thi của một nhiệm vụ trên một máy trạm là một số ngẫu
nhiên giữa 1 đến 5 đơn vị thời gian. Mục đích chính của mô phỏng này là so sánh
hiệu năng của các giản đồ lập lịch: Round Robin RR, lập lịch Round Robin dựa trên
sự ưu tiên về khả năng thực hiện PRR(Av), lập lịch Round Robin dựa trên sự ưu
tiên độ tin cậy PRR(Cr), Lập lịch Round Robin dựa trên kiểm thử tin cậy với tiêu
chí ưu tiên độ tin cậy CRR(Cr) và ưu tiên khả năng thực hiện CRR(Av). Để đảm
bảo độ tin cậy của kết quả mô phỏng tôi sẽ thực hiện mô phỏng mỗi trường hợp 5
lần và lấy giá trị trung bình.
4.3 Kết quả
Hình 4-1, 4-2, 4-3, 4-4
Các file đính kèm theo tài liệu này:
- 000000104513R.pdf