Lập Lịch Round Robin Dựa Trên Sự Ưu Tiên Về Khả Năng Tính Toán

Else

EndIf EndWhile;

Quay lại tính độ tin cậy của máy trạm theo phương trình 2.2 hoặc2.3;

Lưu vào danh sách đen các máy trạm;

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;

End

Else

Elseif

Đẩy nhiệm vụ lại hàng đợi nhiệm vụ;

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

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

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

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;

End

Else

Elseif

Đẩy nhiệm vụ lại hàng đợi nhiệm vụ;

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.

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

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.

Worker P1

Worker P2		Worker P3		Worker P4		Worker P5		Worker P6		Worker P7		Worker P8		Worker P9		Worker P10
K	0	K	0	K	0	K	0	K	0	K	0	K	0	K	0	K	0	K	0
Cr	0.8	Cr	0.8	Cr	0.8	Cr	0.8	Cr	0.8	Cr	0.8	Cr	0.8	Cr	0.8	Cr	0.8	Cr	0.8
T	0.5	T	1	T	1.5	T	2	T	2.5	T	3	T	3.5	T	4	T	4.5	T	5