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

iả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, chỉ định các kết quả thí nghiệm ứng với các trường hợp tỉ lệ lỗi khác nhau khi số lượng công việc lớn hơn số máy và Hình 4-5, 4-6, 4-7, 4-8 chỉ định các kết quả thí nghiệm ứng với các trường hợp tỉ lệ lỗi khác nhau khi số lượng công việc nhỏ hơn số máy trạm, lấy được từ mô phỏng cho đồng thời các giản đồ lập lịch, tôi vẽ biểu đồ giá trị của tham số sự chậm chễ (slowdown) so với các tham số khác bởi vì nó là một tham số hiệu năng quan trọng khi chấp nhận một giản đồ chịu lỗi dựa trên độ tin cậy trong hệ thống tính toán tình nguyện. Nhìn vào các kết quả của biều đồ so sánh tôi nhận thấy rằng các giản đồ lập lịch do tôi đề xuất đều giảm đáng kể thời gian thực thi so với giản đồ lập lịch Round Robin 67 Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008 tương ứng. Đặc biệt trong trường hợp trong cả hai trường hợp N > P hay N < P thì giản đồ lập lịch CRR giảm từ 40% - 60% so với giản đồ lập lịch RR tương tứng. Còn trong trường hợp trong cả hai trường hợp N > P hay N < P thì giản đồ lập lịch CRR giảm xấp xỉ 60% - 80% so với giản đồ lập lịch RR tương tứng. Trong trường hợp N > P, N < P thì giản giản đồ lập lịch CRR hiệu quả hơn PRR(Cr) và PRR(Av) ngoại trừ trường hợp N < P và và tỉ lệ lỗi của kết quả nhỏ hơn 0.001 . Còn giản đồ lập lịch PRR(Cr) thì hiệu quả hơn một chút so với PRR(Av) khi tỉ lệ lỗi nhỏ hơn 0.001. Còn lai là gần như tương đương nhau. Sở dĩ các giản đồ có các kết quả tốt như trên là do các giản đồ đã quan tâm đến việc chọn các máy trạm sao cho nâng cao được độ tin cậy của nhiệm vụ sau mỗi lần tính toán của máy trạm để cho độ tin cậy của nhiệm vụ nhanh hướng được tới ngưỡng tin cậy. 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 >P 68 Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008 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 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 69 Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008 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 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< P 70 Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008 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 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< P 71 Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008 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 72 Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008 Chương 5. KẾT LUẬN Trong luận văn này, chúng ta đã thảo luận về vấn đề lập lịch cho các hệ thống tính toán tình nguyện sử dụng kĩ thuật chịu lỗi dựa trên độ tin cậy. Như là các hệ thống yêu cầu quay lại thực thi một nhiệm vụ trên các máy tính tình nguyện để đảm bảo sự tin cậy của các kết quả và bảo vệ các hệ thống tử sự tấn công của các máy phá hoại. 5.1 Những kết quả đạt được Về mặt lý thuyết: Đã tìm hiểu tổng quan về hệ thống tính toán phân tán, tính toán lươi, tính toán ngang hàng và tính toán tình nguyện. Đã tìm hiểu được về các vấn đề lập lịch trong tính toán tình nguyện. Tìm hiểu được các kĩ thuật chịu lỗi truyền thống như là biểu quyết theo số đông, kiểm tra điểm. Tìm hiểu được chịu lỗi dựa trên độ tin cậy. Khảo sát được một số giản đồ lập lịch dành cho máy chủ trong hệ thống tính toán tình nguyện như là giản đồ lập lịch Round Robin và giản đồ lập dựa trên độ ưu tiên về khả năng tính toán. Đặc biệt là đề xuất ra hai giản đồ lập lịch dựa trên độ tin cậy đó là: Giản đồ lập lịch Round Robin dựa trên sự tin cậy và giản đồ lập lịch Round Robin dựa trên sự kiểm thử độ tin cậy. Về mặt thực nghiệm, luân văn đã mô phỏng thành công các giản đồ lập lịch đã đề xuất và đã đưa ra các kịch bản mô phỏng. Các kết quả mô phỏng chỉ ra rằng bằng việc áp dụng các kĩ thuật lập lịch được đề xuất đã giảm đáng kể thời gian tính toán của hệ thống so với lập Round Robin thông thường trong cả hai trường hợp. 5.2 Những công việc chưa làm được Tuy đã đưa ra được các giản đồ lập lịch mới và đã mô phỏng thành công các giản đồ lập lịch nhưng do thời gian còn hạn chế nên chưa tích hợp vào được hệ thống BOINC. 73 Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008 5.3 Hướng phát triển trong tương lai Trong tương lai tôi sẽ tiếp tục tích hợp các giản đồ lập lịch vào trong hệ thống BOINC. Và tôi sẽ tiếp tục nghiên cứu và đưa ra một vài giản đồ chịu lỗi dựa trên độ tin cậy cho các vấn đề lập lịch động tập trung vào độ tin cậy, khả năng thực hiện và tính sãn sàng của các máy tính tình nguyện hay độ tin cậy của các nhiệm vụ đang được thực thi. Phát triển một hệ thống tính toán tình nguyện ở Việt Nam: VN@Home 74 Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008 TÀI LIỆU THAM KHẢO 1. Sarmenta, L.F.G., Hirano, S.: Bayanihan: Building and studying volunteer computing systems using java. Future Generation Computer Systems 15 (1999) 675–686 2. (SETI@home, 3. Anderson, D.P.: Boinc: A system for public-resource computing and storage. In:Fifth IEEE/ACM International Workshop on Grid Computing. (2004) 4–10 4. Foster, I.: The grid: A new infrastructure for 21st century science. Physics Today (2002) 42–47 5. Foster, I., Iamnitchi, A.: On death, taxes, and the convergence of peer-to-peer and grid computing. In: 2nd International Workshop on Peer-to-Peer Systems (IPTPS’03), Berkeley, CA (2003) 6. (Enstein@home, 7. (Climateprediction.net, 8. Sarmenta, L.F.G.: Sabotage-tolerance mechanisms for volunteer computing systems. Future Generation Computer Systems 18 (2002) 561–572 9. Anderson, D.P., Fedak, G.: The computational and storage potential of volunteer computing. In: Sixth IEEE International Symposium on Cluster Computing and the Grid. (2006) 73–80 10. Son Hong Ngo, Ph.D: Priority Round Robin Scheduling Scheme for Reliable Volunteer Computing Systems. 4-8 11. L.F.G. Sarmenta, Volunteer Computing, Ph.D. thesis.Dept. of Electrical Engineering and Computer Science, MIT, Cambridge, MA, Dec., 2000. 111 - 130 12. Anderson, D.P., E. Korpela, and R. Walton. "HighPerformance Task Distribution for Volunteer Computing". 1st IEEE International Conference on e- Science and Grid Computing, Melbourne, Dec. 2005, pp. 196-203. 75 Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008 13. Anderson, D.P., C. Christensen, and B. Allen."Designing a Runtime System for Volunteer Computing", to appear in Supercomputing. 1 – 4, 6 14. David P. Anderson, John McLeod: “Local Scheduling for Volunteer Computing” 1-3 15. Derrick Kondo, David P. Anderson, John McLeod:” Performance Evaluation of Scheduling Policies for Volunteer Computing” 1-2 16. M. Taufer, A. Kerstens, T. P. Estrada, D. A. Flores, R. Zamudio, P. J. Teller, R. Armen, and C. L. Brooks: “Moving Volunteer Computing towards Knowledge-Constructed, Dynamically-Adaptive Modeling and Scheduling” 17. Jason Sonnek, Mukesh Nathan, Abhishek Chandra, and Jon Weissman” Reputation-Based Scheduling on Unreliable Distributed Infrastructures” November 21, 2005 4-7 18. Gheorghe Cosmin Silaghi, Alvaro E. Arenas, Luis Moura Silva: “Reputation- based trust management systems and their applicability to grids” 19. “The Effectiveness of Threshold-based Scheduling Policies in BOINC Projects” Trilce Estrada, David A. Flores, Michela Taufer, Patricia J. Teller, Andre Kerstens, David P. Anderson 3-4 20. “Volunteer Computing” by Luis F. G. Sarmenta 21. A. L. Beberg, J. Lawson, D. McNett, distributed.net, 22. “Peer-to-Peer Computing: Systems, Concepts and Characteristics” Andreas Mauthe, David Hutchison Computing Department Lancaster University Lancaster LA1 4YR UK 2-4 23. BOINC: 24. 25.