Bài giảng Mô hình hóa và mô phỏng mạng - Mô hình hóa phân tích (Phần 1) - Nguyễn Đức Tài

Nội dung text: Bài giảng Mô hình hóa và mô phỏng mạng - Mô hình hóa phân tích (Phần 1) - Nguyễn Đức Tài

1. TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN TPHCM MÔ HÌNH HÓA VÀ MÔ PHỎNG MẠNG Mô hình hóa phân tích Phần (1) 1 TS. Nguyễn Đức Tài
2. ĐẶC TÍNH HTHĐ M/M/1 Sử dụng phương pháp giá trị trung bình hoặc mô hình Markov, có thể nhận được những công thức sau để tính các giá trị trung bình: Thời gian đợi trung bình của yêu cầu: Thời gian ở trung bình của yêu cầu: Chiều dài hàng đợi của yêu cầu: Số lượng yêu cầu trong hệ thống (trong hàng đợi và đang trong phục vụ): 2
3. ĐẶC TÍNH HTHĐ M/G/1 Thời gian phục vụ phân bố theo luật bất kỳ với giá trị trung bình b và hệ số biến thiên . Thời gian đợi trung bình được xác định theo công thức Pollacheck-Khinchine: Thời gian ở trung bình trong hệ thống Điểm đặc biệt:  Giá trị trung bình của các đặc tính phục vụ yêu cầu chỉ phụ thuộc vào 2 thời điểm ban đầu của thời gian phục vụ yêu cầu mà không phụ thuộc vào các thời điểm bậc cao hơn (không cần thiết phải biết luật phân bố của thời gian phục vụ yêu cầu – mà chỉ cần 2 thời điểm ban đầu là đủ).  Với HTHĐ với luồng yêu cầu đơn giản nhất, để tính thời điểm thứ k của đặc tính phục vụ thì cần cho (k+1) thời điểm 3 ban đầu của thời gian phục vụ yêu cầu.
4. ĐẶC TÍNH HTHĐ G/M/1 Kết quả cuối cùng ở dạng công thức toán học cho việc tính toán thời gian đợi là không thể. Thời gian đợi trung bình không những phụ thuộc vào hai thời điểm ban đầu trong phân bố giữa các khoảng thời gian mà các yêu cầu đi vào, mà còn phụ thuộc vào những thời điểm ở cấp độ cao hơn nữa, nghĩa là phụ thuộc vào toàn bộ phân bố đó. Thời gian đợi trung bình của yêu cầu trong hàng đợi Trong đó – nghiệm duy nhất của phương trình Trong đó – biến đổi Laplace của hàm mật độ phân bố của những khoảng thời gian đến giữa các yêu cầu đi vào hệ thống: Mức độ ảnh hưởng của những thời điểm tương ứng là giảm cùng với sự tăng cấp độ của thời điểm đó. 4
5. ĐẶC TÍNH HTHĐ G/G/1 Trên thực tế khi nghiên cứu những hệ thống thực rất hiếm khi biết trước (cho trước) được luật phân bố của những biến các khoảng thời gian giữa các yêu cầu và thời gian phục vụ. Thường khi mô tả tiến trình đi vào hệ thống của các yêu cầu và thời gian phục vụ của chúng thì giới hạn một vài thời điểm ban đầu của những phân bố tương ứng đó, và thường là – 2 thời điểm đầu tiên: giá trị trung bình và hệ số biến thiên của biến ngẫu nhiên. Tất cả các kết quả nhận được ở dạng phân tích khi cho biết 2 thời điểm đầu tiên của khoảng thời gian giữa các yêu cầu và thời gian phục vụ là những kết quả gần đúng. Công thức gần đúng Langenbach-Belz thành công nhất Hệ số biến thiên của luồng yêu cầu ra có thể được tính bằng công thức gần đúng sau (công thức 5 Marshall K.T.
6. PHÂN TÍCH TÍNH CHẤT HTHĐ 1 KÊNH Thời gian đợi trung bình của yêu cầu trong hàng đợi là nhỏ nhất khi thời gian phục vụ yêu cầu là không đổi (định trước, deterministic), khi mà hệ số biến thiên của thời gian đợi bằng 0 và tăng khi tăng hệ số biến thiên (độ ly tán, độ tản mát) của thời gian phục vụ (không tuyến tính). Thời gian đợi trung bình của yêu cầu phụ thuộc đáng kể vào tải ngoài (hay tải trong ) của hệ thống Thời gian đợi trung bình các yêu cầu theo LIFO sẽ là giống với khi phục vụ FIFO, nhưng độ phân tán thời gian đợi sẽ lớn hơn so với FIFO. 6
7. ĐẶC TÍNH HTHĐ NHIỀU KÊNH M/M/K Trong đó P – xác suất mà tất cả K thiết bị đều bận phục vụ các yêu cầu. – xác suất không làm việc của HTHĐ nhiều kênh, có nghĩa là xác suất mà trong hệ thống không có yêu cầu 7
8. PHÂN TÍCH TÍNH CHẤT HTHĐ NHIỀU KÊNH Khi tăng số lượng thiết bị phục vụ Khi tăng số lượng thiết bị phục vụ K, thì tổng hiệu suất (tốc độ làm K, thì tổng hiệu suất (tốc độ làm việc) của hệ thống thay đổi việc) của hệ thống không thay đổi Ví dụ trong trường hợp này là máy tính A với 1 vi xử lý mạnh so với máy tính B có nhiều vi xử lý nhưng tốc độ tổng cộng Để bảo toàn hiệu suất của hệ thống nên thời gian phục vụ bằng tốc độ của máy tính A, hãy thử đánh giảm tỷ lệ thuận với số lượng giá? thiết bị 8 Ưu điểm của hệ thống nhiều kênh là độ tin cậy (reliability) cao
9. ĐẶC TÍNH HTHĐ 1 KÊNH VỚI LUỒNG KHÔNG ĐỒNG NHẤT M/G/1/H Thời gian phục vụ yêu cầu của lớp k phân bố theo luật bất kỳ với các giá trị trung bình và hệ số biến thiên Quy luật phục vụ không có độ ưu tiên - tổng tải trong của hệ thống 9
10. Phân tích tính chất HTHĐ M/G/1/H với Quy luật phục vụ không có độ ưu tiên Thời gian đợi trung bình các yêu cầu các lớp khác nhau khi sử dụng quy tắc phục vụ không có độ ưu tiên là như nhau ; Thời gian đợi trung bình của yêu cầu trong hàng đợi là nhỏ nhất khi thời gian phục vụ yêu cầu là không đổi (định trước, deterministic), khi mà hệ số biến thiên bằng 0, và tăng khi tăng hệ số biến thiên (độ tản mát) của thời gian phục vụ. 10 Các đường cong có hình dạng tương tự như thời gian ở tương ứng với các lớp khác nhau.
11. Phân tích tính chất HTHĐ M/G/1/H với Quy luật phục vụ không có độ ưu tiên Đối với quy luật phục vụ là trật tự luân phiên thì thời gian đợi trung bình các yêu cầu các lớp khác nhau, nói chung là, không như nhau Sự khác nhau này phụ thuộc vào tỷ lệ giữa tham số của luồng và tham số phục vụ yêu cầu các lớp khác nhau . Trong một vài trường hợp thì quy luật phục vụ theo trật tự luân phiên cho kết quả tổng chiều dài các hàng đợi là nhỏ hơn 11 so với quy luật phục vụ theo trật tự đến.
12. QUY TẮC PHỤC VỤ CÓ ƯU TIÊN TƯƠNG ĐỐI Các tổng tải trong, được tạo ra bởi các yêu cầu có ưu tiên không thấp hơn (k-1) và k tương ứng Phân tích tính chất:  Giảm thời gian đợi của các yêu cầu có độ ưu tiên cao của lớp đầu tiên (ưu tiên cao nhất) và làm tăng thời gian đợi của những yêu cầu có ưu tiên thấp  Thời gian đợi trung bình các yêu cầu tăng một cách đơn điệu khi tăng độ ưu tiên 12
13. QUY TẮC PHỤC VỤ CÓ ƯU TIÊN TƯƠNG ĐỐI Đối với các yêu cầu có độ ưu tiên cao đảm bảo chất lượng phục vụ (QoS, quality of service) tốt: thời gian đợi không lớn ngay cả khi xuất hiện việc quá tải: Y>1 Tính chất này được gọi là tính bảo vệ từ việc quá tải, được bảo đảm bằng việc từ chối phục vụ những yêu cầu có độ ưu tiên thấp, thời gian đợi của chúng lúc đó tăng đột ngột. 13
14. QUY TẮC PHỤC VỤ CÓ ƯU TIÊN TƯƠNG ĐỐI 14
15. QUY TẮC PHỤC VỤ CÓ ƯU TIÊN TUYỆT ĐỐI Yêu cầu bị ngắt có thể bị mất hoặc quay trả lại thiết bị lưu trữ để chờ đợi được phục vụ sau đó. Đối với trường hợp sau cùng thì có 2 khả năng khi phục vụ lại yêu cầu bị ngắt:  Phục vụ lại từ đầu, nghĩa là yêu cầu bị ngắt sẽ được phục vụ lại từ đầu;  Phục vụ từ thời điểm (vị trí) bị ngắt. Trong tương lai, khi không nói ra, thì mặc định được hiểu là phục vụ từ thời điểm bị ngắt. 15
16. PHÂN TÍCH TÍNH CHẤT Biểu thức có 2 thành phần , biểu thị cho thời gian đợi trung bình lúc bắt đầu phục vụ và thời gian đợi trung bình trong trạng thái bị ngắt tương ứng. Thời gian đợi yêu cầu lớp k chỉ phụ thuộc vào giá trị tham số của các lớp 1,2, ,k, nghĩa là các lớp có ưu tiên cao hơn hoặc bằng, và không phụ thuộc vào tham số các lớp yêu cầu k+1, ,H Đối với yêu cầu lớp 1, có độ ưu tiên tuyệt đối cao nhất, thì đảm bảo được thời gian đợi nhỏ nhất khi so với tất cả các QLPV khác. Điều này được giải thích bởi việc trong trường hợp QLPV có ưu tiên tuyệt đối các yêu cầu lớp 1 được phục vụ như thể là riêng lẽ, 16 không phụ thuộc vào các yêu cầu các lớp khác.
17. PHÂN TÍCH TÍNH CHẤT 17
18. ĐỊNH LUẬT BẢO TOÀN Định luật bảo toàn cho thời gian đợi (với bất cứ quy luật phục vụ nào) Định luật bảo toàn thời gian đợi được thực thi trong khi đạt được những giả định sau:  Hệ thống không bị mất – tất cả các yêu cầu đều được phục vụ;  Hệ thống chỉ không làm việc khi trong nó không có yêu cầu nào;  Khi có mặt việc ngắt thì thời gian phục vụ của các yêu cầu bị ngắt là phân bố theo luật mũ;  Tất cả các luồng yêu cầu đi vào là đơn giản nhất, và thời gian phục vụ không phụ thuộc vào cường độ 18 luồng yêu cầu.
19. ĐỊNH LUẬT BẢO TOÀN Giá trị const trong định luật bảo toàn có thể được xác định như sau. Vì định luật bảo toàn đúng với mọi QLPV mà thỏa mãn các giả định trên, thì nó cũng đúng với QLPV không có độ ưu tiên Định luật bảo toàn thời gian đợi là phổ quát và đúng cho tất cả các QLPV. Được sử dụng để đánh giá độ tin cậy của các kết quả gần đúng mà nhận được khi nghiên cứu các QLPV phức tạp và khi thực thi mô hình hóa mô phỏng, và được sử dụng khi giải những bài toán tổng hợp. 19
20. CHỈNH SỬA ĐỊNH LUẬT BẢO TOÀN Luật bảo toàn cho thời gian ở Xét trường hợp khi mà những thời gian phục vụ trung bình của các yêu cầu của các lớp khác nhau là bằng nhau: Nếu thời gian phục vụ trung bình yêu cầu của các lớp khác nhau là như nhau thì sự thay đổi QLPV không dẫn đến sự thay đổi tổng chiều dài hàng đợi L yêu cầu của tất cả các lớp. 20
21. KIỂM TRA ? Pr=80% 21