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 - 8

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.

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

Có thể bạn quan tâm!

• Kiểm Tra Điểm Không Dùng Danh Sách Đen
• Lập Lịch Round Robin Dựa Trên Sự Ưu Tiên Về Khả Năng Tính Toán
• Giản Đồ Lập Lịch Round Robin Dựa Trên Kiểm Thử Độ Tin Cậy
• 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 - 9
• 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 - 10

Xem toàn bộ 83 trang tài liệu này.

Hoàn thành
Crw = 0.99902
Công việc 1

Crw = 0.92753
Công việc 2

Crw = 0.80000

Công việc 5

P1

0.80000

P2

0.94117

P1

0.98461

P2

0.99610

Crc = 0.94117
pid	Crg
P7	0.80000
P8	0.94117
P7	-
P8	-

Crc = 0.80000
pid	Crg
P9	0.80000
P10	0

P2

P2

P2

P1 0.99902

P4

P5

-

-

Worker P1

Worker P2

Worker P3

Worker P4

Worker P5

Worker P6

Worker P7

Worker P8

Worker P9

Worker P10

K

23

K

14

K

0

K

0

K

4

K

0

K

0

K

0

K

0

K

0

Cr

0.99166

Cr

0.98666

Cr

0.8

Cr

0.8

Cr

0.95999

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

9

Công việc chưa được làm tiếp

SLOWDOWN = 4.5

Hoàn thành

Crw = 0.99992

Crw = 0.94117

Công việc 3

Công việc 4

Crc = 0.99902

Crc = 0.92753

Crc = 0.99992

pid

Crg

pid

Crg

pid

Crg

P3

0.80000

P5

0.80000

P4

0.94117

P6

0.44445

P3

0.76190

P1

0.76190

P4

0.92753

P2

0.99605

P1

0.99992

P2

-

10

Công việc chưa được làm tiếp

SLOWDOWN = 5

Hoàn thành

Crw = 0.99992

Crw = 0.94117

Công việc 3

Công việc 4

Danh sách máy trạm có khả năng

P3

P6

P1

P9

Hoàn thành
Crw = 0.99902
Công việc 1

Crw = 0.92753
Công việc 2

Crw = 0.94117

Công việc 5

Crc = 0.99902
pid	Crg
P1	0.80000
P2	0.94117
P1	0.98461
P2	0.99610
P1	0.99902

Crc = 0.92753
pid	Crg
P3	0.80000
P4	0.94117
P3	0.76190
P4	0.92753
P4	-
P5	-

Crc = 0.99992
pid	Crg
P5	0.80000
P6	0.44445
P1	0.76190
P2	0.99605
P1	0.99992

Crc = 0.94117
pid	Crg
P7	0.80000
P8	0.94117
P7	-
P8	-

Crc = 0.94117
pid	Crg
P9	0.80000
P10	0.94117
P1	-
P2	-

Worker P1

Worker P2		Worker P3		Worker P4		Worker P5		Worker P6		Worker P7		Worker P8		Worker P9		Worker P10
K	23	K	14	K	0	K	0	K	4	K	0	K	0	K	0	K	0	K	0
Cr	0.99166	Cr	0.98666	Cr	0.8	Cr	0.8	Cr	0.95999	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

P2

P2

P2

Danh sách máy trạm có khả năng

P3

P6

P1

P9

P2

P10

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.99947

Công việc 5

Worker P1

Worker P2		Worker P3		Worker P4		Worker P5		Worker P6		Worker P7		Worker P8		Worker P9		Worker P10
K	26	K	14	K	0	K	0	K	4	K	0	K	0	K	0	K	0	K	0
Cr	0.99259	Cr	0.98666	Cr	0.8	Cr	0.8	Cr	0.95999	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

P2

P2

P2

0.99610

P1

0.80000

P3

0.80000

P5

0.80000

P7

0.80000

P9

0.80000

P2

0.94117

P4

0.94117

P6

0.44445

P8

0.94117

P10

0.94117

P1

0.98461

P3

0.76190

P1

0.76190

P7

-

P1

0.99947

P2

P4

0.92753

P2

0.99605

P8

-

P2

-

P1

0.9990

2

P4

-

P1

0.99992

P5

-

11

Công việc chưa được làm tiếp

SLOWDOWN = 5.5

Hoàn thành

Crw = 0.99992

Crw = 0.94117

Công việc 3

Công việc 4

Crc = 0.99902

Crc = 0.92753

Crc = 0.99992

Crc = 0.94117

Crc = 0.99947

pid

Crg

pid

Crg

pid

Crg

pid

Crg

pid

Crg

Danh sách máy trạm có khả năng

P3

P6

P1

P9

P10

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.99947
	Công việc 5

P1

0.80000

P2

0.94117

P1

0.98461

P2

0.99610

P1

0.99902

Crc = 0.99992
pid	Crg
P5	0.80000
P6	0.44445
P1	0.76190
P2	0.99605
P1	0.99992

Crc = 0.94117
pid	Crg
P7	0.80000
P8	0.94117
P7	-
P8	-

Crc = 0.99947
pid	Crg
P9	0.80000
P10	0.94117
P1	0.99947

Worker P1

Worker P2		Worker P3		Worker P4		Worker P5		Worker P6		Worker P7		Worker P8		Worker P9		Worker P10
K	32	K	14	K	0	K	18	K	10	K	0	K	0	K	0	K	0	K	0
Cr	0.99393	Cr	0.98666	Cr	0.8	Cr	0.98947	Cr	0.98181	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

P2

P2

P2

P5

0.99514

P1

0.99979

P2

-

13

Công việc chưa được làm tiếp

SLOWDOWN = 7

Crc = 0.99902

Hoàn thành

Crw = 0.99992

Crw = 0.94117

Công việc 3

Công việc 4

Crc = 0.99979

pid

Crg

pid

Crg

...

...

P4

0.98084

14

Công việc chưa được làm tiếp

SLOWDOWN = 8

Crc = 0.99610

pid Crg

P7 0.80000

P8 0.94117

P7 0.98461

P8 0.99610

P1 -

P2 -

Hoàn thành

Crw = 0.99992

Crw = 0.99610

Công việc 3

Công việc 4

Danh sách máy trạm có khả năng

P3

P6

P1

P9

P10

P2

P4

P5

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.99947

Công việc 5

Crc = 0.99902
pid	Crg
P1	0.80000
P2	0.94117
P1	0.98461
P2	0.99610
P1	0.99902

Crc = 0.99979
pid	Crg
...	...
P4	0.98084
P5	0.99514
P1	0.99979

Crc = 0.99992
pid	Crg
P5	0.80000
P6	0.44445
P1	0.76190
P2	0.99605
P1	0.99992

Crc = 0.99947
pid	Crg
P9	0.80000
P10	0.94117
P1	0.99947

Worker P1

Worker P2		Worker P3		Worker P4		Worker P5		Worker P6		Worker P7		Worker P8		Worker P9		Worker P10
K	32	K	14	K	0	K	18	K	10	K	0	K	0	K	0	K	0	K	0
Cr	0.99393	Cr	0.98666	Cr	0.8	Cr	0.98947	Cr	0.98181	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

P2

P2

P2

Danh sách máy trạm có khả năng

P3

P6

P7

P9

P10

P8

P4

P5

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.99947

Công việc 5

Crc = 0.99902
pid	Crg
P1	0.80000
P2	0.94117
P1	0.98461
P2	0.99610
P1	0.99902

Crc = 0.99979
pid	Crg
...	...
P4	0.98084
P5	0.99514
P1	0.99979

Crc = 0.99992
pid	Crg
P5	0.80000
P6	0.44445
P1	0.76190
P2	0.99605
P1	0.99992

Crc = 0.99947
pid	Crg
P9	0.80000
P10	0.94117
P1	0.99947

Worker P1

Worker P2		Worker P3		Worker P4		Worker P5		Worker P6		Worker P7		Worker P8		Worker P9		Worker P10
K	37	K	14	K	0	K	18	K	10	K	0	K	10	K	10	K	0	K	0
Cr	0.99473	Cr	0.98666	Cr	0.8	Cr	0.98947	Cr	0.98181	Cr	0.8	Cr	0.98181	Cr	0.98181	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

P2

P2

P2

15

Công việc chưa được làm tiếp

SLOWDOWN = 8

Crc = 0.99997

pid Crg

P7 0.80000

P8 0.94117

P7 0.98461

P8 0.99610

P1 0.99997

P2 -

Hoàn thành

Hoàn thành

Crw = 0.99992

Crw = 0.99997

Công việc 3

Công việc 4

Danh sách máy trạm có khả năng

P3

P6

P7

P9

P10

P8

P4

P5

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

EndIf EndWhile;

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ụ;

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

EndIf EndWhile

Gán nhiệm vụ đến máy trạm;

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;

End

Else

EndIf

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

Type

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

Đầ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)

EndIf

Lấy máy có thời gian thực hiện ngắn nhất; Trả về máy lấy được;

//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ụ;

();

Av(i)

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à

If

bWorker = i; EndIf

ElseIf (Tồn tại bWorker)

//Ưu tiên độ tin cậy If (Type )

If