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á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ổ