Phương pháp đánh giá hiệu năng hệ thống sử dụng mạng Stochastic Petri

Chia sẻ: Nguyễn Văn Chiến | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

290
lượt xem 62
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đối với các hệ thống phức tạp do khả năng hạn chế trong việc biểu diễn các quan hệ tương tranh (concurrency), đồng bộ (synchronization) cũng như các hoạt động nội tại của server nên phương pháp sử dụng mạng hàng đợi không đáng tin cậy. Trong bối cảnh đó, phương pháp sử dụng mạng Petri để mô phỏng hệ thống, sau đó, trên cơ sở phân tích cây trạng thái (được thể hiện thông qua tập hình trạng của mạng) để rút ra các kết quả đánh giá hiệu năng cả về định tính và định......

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Phương pháp đánh giá hiệu năng hệ thống sử dụng mạng Stochastic Petri

Phương pháp đánh giá hiệu năng hệ thống sử dụng mạng Stochastic Petri A System Performance Evaluation Method Using Stochastic Petri Net Tạ Hải Tùng chi phí thấp, việc mô phỏng đơn giản, trở nên rất hữu Abstract: Nowadays, Performance Evaluation is one of the most important fields of information technology. Hence, dụng đối với các hệ thống không phức tạp, đòi hỏi độ it has been widely studied in recent years. This paper chính xác của kết quả phân tích không cao. Đối với presents the performance evaluation method using các hệ thống phức tạp do khả năng hạn chế trong việc Stochastic Petri Net. With the capability of simulating biểu diễn các quan hệ tương tranh (concurrency), complex systems and mapping to Markov chain, this đồng bộ (synchronization) cũng như các hoạt động method is powerful widely used in many systems, especially nội tại của server nên phương pháp sử dụng mạng in computer and communication systems. hàng đợi không đáng tin cậy. Trong bối cảnh đó, phương pháp sử dụng mạng Petri để mô phỏng hệ I. ĐẶT VẤN ĐỀ thống, sau đó, trên cơ sở phân tích cây trạng thái Đánh giá hiệu năng thông qua mô phỏng hệ thống (được thể hiện thông qua tập hình trạng của mạng) để là một phương pháp hiệu quả và đặc biệt hữu ích đối rút ra các kết quả đánh giá hiệu năng cả về định tính với các nhà thiết kế, xây dựng hệ thống. Nền tảng của và định lượng, được coi như một giải pháp dung hoà phương pháp là: hai phương pháp trên, trong đó, kết hợp khả năng mô − Mô phỏng hệ thống: mô hình hoá cấu trúc phỏng phức tạp của phương pháp thứ ba với khả năng (structure) và mô tả hành vi (behaviour) của hệ phân tích đơn giản, hiệu quả của phương pháp đầu. thống. Phương pháp dùng mạng Petri có thể áp dụng đối với − Phân tích, đánh giá hiệu năng trên mô hình mô các hệ thống có hoạt động phức tạp với đầy đủ các mối quan hệ giữa các thành phần trong hệ thống. phỏng hệ thống. Hiện nay, có ba phương pháp đánh giá hiệu năng Mô hình mạng Petri được Carl Adam Petri đề xuất thông qua mô phỏng hệ thống [1], đó là: phương pháp vào năm 1962, trải qua hơn 40 năm phát triển, từ một sử dụng Mạng hàng đợi (Queue Network - QN) [1,2], mạng Petri đơn giản ban đầu, những người quan tâm phương pháp sử dụng Mạng Petri (Petri Net - PN) [3] nghiên cứu đã cho ra đời một loạt các loại mạng Petri và phương pháp sử dụng Chương trình máy tính được mức cao (Coloured Petri Net, Predicate Petri Net, thiết kế đặc thù chỉ để mô phỏng cho một hệ thống [1]. Stochastic Petri Net...) có thể mô phỏng cũng như Trong đó, phương pháp cuối cùng tuy cho kết quả với phân tích hiệu năng cho các hệ thống từ đơn giản đến độ tin cậy và chính xác cao nhưng phải trả giá về sự phức tạp. Trong đó, mạng Stochastic Petri (SPN) [1,4] đòi hỏi và chiếm dụng tài nguyên rất lớn, vì vậy, do khả năng quy tương đương về chuỗi Markov đã tạo phương pháp này thường ít được sử dụng trong đánh ra một ưu thế vượt trội trong đánh giá hiệu năng định giá hiệu năng. Phương pháp sử dụng mạng hàng đợi, lượng và trở thành một hướng nghiên cứu nhiều hứa với nền tảng là lý thuyết xếp hàng và luật Little, do hẹn. PN nói chung và SPN nói riêng là những vấn đề
tương đối phức tạp, vì vậy, trong giới hạn ngắn gọn đỉnh là: các place đại diện bởi các hình tròn, các của bài báo chúng tôi tập trung vào việc ứng dụng transition đại diện bởi các hình chữ nhật: hình chữ SPN trong đánh giá hiệu năng, các khía cạnh chuyên nhật đen là transition tức thời (immediate transition – sâu có thể được tìm hiểu thêm trong các tài liệu tham i-transition), hình chữ nhật trắng là các transition gắn khảo [1,3,4,6]. thời gian (timed transition – t-transition). Các đỉnh khác loại nối với nhau bởi các cung, đối với đỉnh là II. PHƯƠNG PHÁP ĐÁNH GIÁ HIỆU NĂNG transition tương ứng có các cung vào (input arc), cung HỆ THỐNG SỬ DỤNG MẠNG STOCHASTIC ra (output arc), cung ức chế (inhibitor arc) phân biệt PETRI bởi đoạn thằng có hình tròn ở đầu. Mỗi place có chứa các token, được biểu diễn bởi các hình tròn đen (do Hình1 chỉ rõ các bước của phương pháp (mỗi bước vấn đề ngữ nghĩa nên trong bài báo này vẫn sử dụng ứng với một cung, bước tương ứng với cung đứt nét nguyên gốc các thuật ngữ: place, transition, token). có thể được thực hiện nhiều lần để mang lại kết quả Một sự phân bố các token tại mỗi place là một hình tối ưu): trạng (marking) của SPN Bước 1: Mô phỏng hệ thống thành một SPN. Về mặt hình thức, SPN được định nghĩa như sau: Bước 2: Xây dựng cây trạng thái của hệ thống Định nghĩa 1: Một SPN được biểu diễn bởi: thông qua việc xây dựng tập hình trạng của SPN. SPN = (P, T, Pr, I, O, H, W, m0) Bước 3: Tiến hành phân tích hiệu năng định tính. Trong đó: P: tập các place (|P| = np). Hệ thống mong đợi Diễn giải, T: là tập các transition (|T| = nt). xây dựng Mô phỏng Pr: tập ưu tiên gắn với mỗi transition. Với lưu ý một i- hệ thống (1) transition luôn có giá trị ưu tiên lớn hơn bất kỳ một t- (6) transition nào. Kết quả đánh SPN giá hiệu năng I, O, H: Các tập trọng số tương ứng với cung vào, cung Xây dựng ra, cung ức chế. Phân tích cây W:T→ R+ là một hàm liên kết với mỗi transition t. Đối định lượng trạng thái Phân tích (5) (2) định tính với t-transition thì W(t) là tốc độ kích hoạt (firing rate). (3) Cây trạng thái CTMC m0 ∈ N mP là hình trạng ban đầu. Xây dựng CTMC (4) Bộ nhớ CPU sẵn sàng Hình 1: Sơ đồ ứng dụng SPN trong đánh giá hiệu năng p1 p2 Bước 4: Trên cơ sở cây trạng thái, xây dựng chuỗi t1 CPU bắt đầu xử lý lệnh Markov thời gian liên tục (Continuous Time Markov p3 CPU đang xử lý Chain - CTMC) đại diện cho hệ thống. lệnh Bước 5: Tiến hành phân tích hiệu năng định lượng. t2 CPU kết thúc xử lý lệnh Bước 6: Từ kết quả đánh giá hiệu năng tiến hành xây dựng hệ thống (bước này không được đề cập do Hình 2: Mạng Stochastic Petri ngoài phạm vi bài báo). Trong hình 2: Các mục tiếp sau sẽ đi vào cụ thể của từng bước. P = {p1,p2,p3}; T = {t1,t2}; m0 = (1,2,0) 1. Mô phỏng hệ thống về SPN Nét đặc thù của SPN là sự liên kết yếu tố thời gian a) SPN (tuân theo phân bố xác suất mũ) với sự kích hoạt của Mô hình SPN là một đồ thị có hướng. Trong đó các t-transition trong SPN thông qua tốc độ kích hoạt W(t-
transition). Định nghĩa 3: Hình trạng m tồn tại một i-transition có khả năng kích hoạt được gọi là hình trạng vô hình Ngoài các thành phần cơ bản trên, hiện nay để mô (vanishing marking). Ngược lại, ta có hình trạng hữu phỏng các hệ thống phức tạp, người ta còn thêm vào hình (tangible marking). một số thành phần mở rộng tạo nên mạng Stochastic Reward (SRN) [6,7] Một transition có khả năng kích hoạt t được chọn kích hoạt sẽ trải qua một khoảng thời gian trễ tuân − Ý nghĩa các thành phần của SPN trong mô phỏng hệ theo phân bố hàm mũ (nếu là i-transition thì thời gian thống: trễ bằng 0) trước khi kích hoạt. Khi kích hoạt, t sẽ loại Place: Đại diện cho tài nguyên hay tình trạng của khỏi các place vào (kết nối với t thông qua cung vào) tài nguyên. số lượng token tương ứng với trọng số của cung liên Transition: Đại diện cho một sự kiện trong chuỗi sự kết và đưa ra place ra (kết nối với t thông qua cung kiện xảy ra trong quá trình hoạt động của hệ thống. ra) số token tương ứng với trọng số của cung liên kết. i-transition: Đại diện cho sự kiện xảy ra tức thời khi Trong hình 3 , chúng ta sẽ xem xét sự biến đổi hình mà điều kiện kích hoạt được thoả mãn. trạng của SPN khi kích hoạt t. t-transition: Đại diện cho sự kiện cần trải qua thời gian trễ trước khi kích hoạt. kích hoạt t 3 3 2 2 Cung: Đại diện cho luồng vào và luồng ra của hệ t t thống. 2 2 Token: Bản thân token không có ý nghĩa bằng số (a) (b) lượng token. Số lượng token đại diện cho số lượng tài M = (4,1,2,1,0) M’ = (1,0,0,3,1) nguyên, số lượng yêu cầu... Số lượng token kết hợp với các place và các cung cấu thành điều kiện để kích Hình 3: Sự lưu chuyển token trong SPN hoạt một transition (cấu thành một sự kiện). Sự lưu Khi trong một hình trạng có nhiều hơn một chuyển token thể hiện hoạt động của hệ thống. Sự transition có khả năng kích hoạt thì luật sau sẽ được phân bố các token đại diện cho các trạng thái của hệ áp dụng để chọn ra một transition được kích hoạt [4]: thống. Một transition trong số các i-transition có khả năng Xuất phát từ ý nghĩa trên chúng ta thấy được rằng: kích hoạt (nếu tồn tại) sẽ được chọn đầu tiên theo xác − Cấu trúc của hệ thống có thể được mô phỏng bởi sự W(t) biểu diễn về mặt hình học các thành phần của SPN suất: p = . Với W là tổng độ phức tạp của các W (place, transition, token, cung). i-transition có khả năng kích hoạt. − Hoạt động của hệ thống có thể được mô phỏng bởi Nếu không tồn tại i-transition có khả năng kích sự lưu chuyển các token (chính là sự biến đổi các hoạt, một t-transition sẽ được chọn theo một trong hai trạng thái của hệ thống) giữa các đỉnh của SPN chiến lược: thông qua sự kích hoạt của các transition (hay sự xuất hiện của các sự kiện). Đây chính là quá trình 1. Chiến lược “chạy đua” (race policy) mô tả hành vi trong mô phỏng hệ thống. Trong chiến lược này thì t-transition nào có tốc độ Định nghĩa 2: Một transition t gọi là có khả năng lớn nhất (hay thời gian trễ nhỏ nhất) trong số các t- kích hoạt (enabled) trong một hình trạng m khi mà transition có khả năng kích hoạt sẽ được chọn kích mọi place đầu vào của t chứa số token không nhỏ hơn hoạt trước. Chính vì vậy, nảy sinh một vấn đề: So trọng số của cung liên kết và mọi place đầu vào ức sánh thời gian trễ giữa các t-transition có gốc thời gian chế có số lượng token nhỏ hơn trọng số của cung ức khác nhau. Trong bối cảnh đó có hai phương pháp: chế liên kết. − Phương pháp khởi tạo lại từ đầu (resampling): Khi
xét chọn transition kích hoạt thì đồng thời khởi tạo 2. Xây dựng cây trạng thái lại gốc thời gian đối chứng. Nghĩa là không hề xét Cây trạng thái của hệ thống được thể hiện thông đến các yếu tố lịch sử. qua tập hình trạng của SPN, với mỗi hình trạng đại − Phương pháp nhớ (memory policy) được bổ sung diện cho một trạng thái. Gọi: thêm vào chính sách để lưu lại các thông tin lịch sử RS (Reachability Set) là tập hình trạng của hệ kích hoạt, phương pháp nhớ gồm các phương pháp thống. con sau: NM (New Marking) là tập hình trạng mới chưa Phương pháp nhớ mức thấp: Trong phương pháp được xét. này, tại hình trạng hiện tại, nếu transition ti vẫn tiếp Et(m) là tập các transition có khả năng kích hoạt tại tục giữ khả năng kích hoạt có được từ các nhịp trước hình trạng m. nhưng tại đó không được chọn kích hoạt thì sẽ không Ta có thuật toán xây dựng cây trạng thái với tư phải khởi tạo lại gốc thời gian khi đem so sánh với các tưởng của thuật toán là: Xuất phát từ hình trạng ban transition có khả năng kích hoạt khác. đầu, ta xác định các transition có khả năng kích hoạt Phương pháp nhớ mức cao: Phương pháp này, (chính là các sự kiện có thể xảy ra trong hệ thống), lần ngoài khả năng lưu vết các transition vẫn tiếp tục giữ lượt kích hoạt các transition để tạo ra các hình trạng khả năng kích hoạt, còn có khả năng lưu vết một mới (trạng thái mới của hệ thống), đồng thời lưu trữ transition khi nó không có khả năng kích hoạt ở nhịp các thông tin về phép chuyển đổi hình trạng đó để tạo sau, để đến khi nó lại có khả năng này ở một nhịp nào ra ma trận Q' (với m, m' là chỉ số hàng và cột, W(t,m) đó trong tương lai thì gốc thời gian không phải khởi là giá trị của phần tử tương ứng). Công việc được tiếp tạo lại. tục lặp lại với các hình trạng mới (theo nghĩa không có trong tập các hình trạng đã có), đến khi không thể 2. Chiến lược lựa chọn trước (preselection policy) nảy sinh ra một hình trạng mới nào. Trong đó t-transition sẽ được chọn với xác suất 1. input {P,T,PR,I,O,H,W,m0} W(t) p= . Với W là tổng tốc độ kích hoạt của các t- 2. NM := {m0}; RS := {m0} W while NM ≠ ∅ 3. transition có khả năng kích hoạt. 4. begin b) Các bước mô phỏng hệ thống let m ∈ NM 5. Bước 1: Xác định các hoạt động, chuỗi sự kiện của 6. NM := NM - {m} hành động và tài nguyên cần thiết cho quá trình hoạt for all t ∈ Et(m) 7. động của hệ thống. 8. begin Bước 2: Sắp đặt các hoạt động theo mối quan hệ let m →t m' 9. nhân quả xác định trước (hoạt động nào kéo theo 10. store_Q’(m,m',W(t,m)) hoạt động nào) 11. if m' ∉ RS Bước 3: Mỗi hoạt động hoặc sự kiện sẽ được đại 12. then NM := NM ∪ {m'} diện bởi một transition. 13. RS := RS ∪ {m'} Bước 4: Các tài nguyên cần thiết, các trạng thái 14. else mark(m’) trải qua trong quá trình hoạt động của tài nguyên 15. end được đại diện bởi các place. 16. end Bước 5: Xác định hình trạng ban đầu của hệ thống. 17. p(0) = (1,0,...,0) 18. Output RS,Q’,p(0) Bước 6: Chọn lựa chiến lược hoạt động (một trong Với đầu vào là SPN trải qua thuật toán trên chúng ta hai chiến lược: chạy đua hay lựa chọn trước)
thu được tập hình trạng của SPN, đồng thời thu được d) Tính khôi phục ngược (Reversible) ma trận Q’ có số chiều bằng số trạng thái trong hệ Định nghĩa 7: Hệ thống được gọi là có khả năng thống và xác suất thời điểm ban đầu p(0) phục vụ cho khôi phục ngược nếu trong quá trình hoạt động có khả quá trình xây dựng CTMC sau này. năng quay lại trạng thái ban đầu. Thuật toán trên chỉ dừng khi số lượng trạng thái của Trong SPN, tính chất này sẽ được phân tích thông hệ thống là hữu hạn. Đối với các hệ thống mà việc qua việc tìm kiếm hình trạng ban đầu tại các node xuất hiện các trạng thái mới là vô hạn thì cây trạng khác node gốc của tập hình trạng. thái cũng có số nút không thể xác định được và thuật 4. Xây dựng CTMC toán không dừng, đó chính là hiện tượng bùng nổ CTMC – Continuous Time Markov Chain – được trạng thái (state explosion). Phương pháp đánh giá xác định theo quan hệ sau: hiệu năng đề cập trong bài báo này chỉ quan tâm đến Pr{Xn+1=xn+1/Xn=xn,...,X0=x0} = Pr{Xn+1=xn+1/Xn=xn} (1) các hệ thống hữu hạn trạng thái. Với Xi∈Τ là trạng thái tại thời điểm ti, Τ là tập 3. Phân tích hiệu năng định tính trạng thái, t0
nguyên: t2 2 → 3 với t2 là i-transition với µ2 ∞ U [P ] = ∑ Pr (# P = k ) (8) t3 3 → 1 với t3 là t-transition với tốc độ kích hoạt λ. k =1 Các phần tử đường chéo của Q được tính theo công Trong đó: thức: pm: Xác suất trạng thái tương ứng hình trạng m tại q i ,i = − ∑ q i , j (3) giai đoạn bền vứng. i≠ j m0: Hình trạng ban đầu. 5. Phân tích định lượng R(m0): Tập hình trạng của SPN. Nền tảng của phân tích định lượng là việc tính xác #P: Số lượng token tại place P. suất trạng thái p của hệ thống tại giai đoạn bền vững (steady-state). III. ỨNG DỤNG Giai đoạn bền vững là giai đoạn mà tại đó xác suất Mục này đề cập đến việc ứng dụng SPN trong đánh để hệ đạt đến một trạng thái trong không gian trạng giá hiệu năng hệ thống FileServer được thực hiện thái không phụ thuộc vào yếu tố thời gian (Chú ý: Từ thông qua SPNBuilder - phần mềm được chúng tôi state trong steady-state nên hiểu là “giai đoạn” thay vì xây dựng dựa trên nền tảng lý thuyết được trình bày “trạng thái” do nó không phải là một trạng thái nằm trong mục 2 và cách tiếp cận đề xuất trong [5]. trong không gian trạng thái của hệ thống). 1. Phần mềm SPNBuilder p được xác định thông qua việc giải hệ phương Phần mềm gồm các chức năng chính sau: trình: − Xây dựng SPN trực quan (Graphic Editor): Cung ∑p pQ = 0, =1 (4) i cấp sẵn các thành phần mạng để người sử dụng có ψ i∈ thể xây dựng SPN cho hệ thống của mình. ψ: Không gian trạng thái. − Trình diễn sự lưu chuyển token mô phỏng hoạt động (các phương pháp kinh điển có thể áp dụng: Gauss, của hệ thống (Token Game). Jacobi, Gauss-Seidel, SOR ...) − Phân tích hiệu năng định tính. Công đoạn này đơn giản nhưng đòi hỏi nhiều tài − Phân tích hiệu năng định lượng. nguyên. Phương pháp tiếp cận song song được trình bày trong [7] là một giải pháp hữu ích đối với các hệ − Phần mềm được xây dựng bằng ngôn ngữ Java, yêu thống phức tạp, có số trạng thái lớn (tương ứng số cầu bản JDK từ 1.3 trở lên. phần tử của Q lớn). 2. Đánh giá hiệu năng hệ thống File Server Từ xác suất p, các thông số hiệu năng định lượng sẽ Xét hệ thống gồm có 3 Client và 1 FileServer kết được tính theo các công thức sau: nối trong môi trường mạng sử dụng phương pháp truy − Xác suất để place có đúng k token: cập đường truyền TokenRing với các điều kiện sau Pr{# P = k} = ∑p (5) (hình 5): m m∈R ( m0 ), # P ( m ) = k − Các Client có cấu hình giống hệt nhau. − Số lượng token trung bình tại một place: − Một Client chỉ phát sinh yêu cầu khi yêu cầu ở nhịp ∞ E [P ] = ∑ k Pr{# P = k } trước đã được phục vụ. (6) k =0 − Thông lượng tại transition t: ∑ W(t, m) p Xt = (7) m m∈R ( m0 ),t∈Et ( m ) − Hiệu suất tại một place hay hiệu suất sử dụng tài
Khi NetworkToken đến đại diện bởi một token trong A_CapNToken. Sẽ có hai trường hợp xảy ra: Nếu không có yêu cầu trong bộ đệm thì lập tức NetworkToken sẽ được chuyển sang trạm kế tiếp, ở đây là FileServer, sau một khoảng thời gian di chuyển được xác định bởi tốc độ kích hoạt của A_RelNToken. Nếu có yêu cầu trong bộ đệm thì sau một khoảng thời gian được xác định bởi tốc độ kích hoạt của A_TranReq, yêu cầu sẽ được chuyển đến cho FileServer (tại S_GetReq), đồng thời A chuyển sang trạng thái đợi trả lời A_WaitReply và giải phóng NetworkToken cho trạm kế tiếp. − Mô phỏng SuperClient Hình 5: Sơ đồ hệ thống FileServer − FileServer phục vụ theo chiến lược FIFO với mỗi SuperClient về cơ bản giống với ClientA chỉ khác lần truy cập đường truyền chỉ để gửi trả lời cho một khi Network Token đến trạm này thì trước khi được Client. chuyển sang trạm kế tiếp phải quay vòng với số lần − Thông lượng đường truyền: 10Mbit/s. bằng đúng số Client mà nó đại diện. Công việc đếm − Chiều dài đoạn cáp: 2000m. này được thực hiện bởi N-1_Count. Hơn nữa, tốc độ − Số bit trung bình một gói tin yêu cầu: 1000bpp. kích hoạt của N-1IssueReq phụ thuộc vào số token − Số bit trung bình một gói tin trả lời: 32000bpp. trong N-1_Idle nghĩa là phụ thuộc vào số Client rỗi − Số bit biểu diễn Token: 24bit (còn có khả năng ra yêu cầu). − Thời gian trung bình một trạm phát sinh yêu cầu : 11.11ms. − Mô phỏng FileServer − Thời gian trung bình xử lý một yêu cầu tại server: 2ms. Yêu cầu đến FileServer được xếp hàng tại a) Mô phỏng hệ thống S_GetReq. Sau khoảng thời gian được xác định bởi Để mô phỏng chúng ta chia hệ thống ra thành 3 tốc độ kích hoạt của S_IssueReply, yêu cầu được xử phần: Client A, FileServer và SuperClient. Trong đó, lý và FileServer phát ra bản tin trả lời được lưu tại SuperClient đại diện cho tất cả các Client giống nhau S_WaitNToken. Khi NetworkToken đến bản tin trả còn lại với mục đích làm giảm số lượng place, lời sẽ được chuyển đến đúng trạm đang đợi tùy theo transition đại diện . Các thành phần này sẽ lần lượt tình trạng (số lượng token) tại A_WaitReply (đại diện được mô phỏng và tập hợp lại tạo nên SPN của toàn cho yêu cầu đến từ A), N-1_WaitReply (đại diện cho hệ thống (hình 6). các yêu cầu đến từ SuperClient sau yêu cầu từ A đến − Mô phỏng ClientA FileServer), N-1_WaitBefore (đại diện cho các yêu Ban đầu ClientA ở trạng thái rỗi được đặc trưng bởi cầu đến trước yêu cầu từ A): một token nằm trong A_Idle. Sau một khoảng thời gian được xác định thông qua tốc độ kích hoạt của Nếu place N-1_WaitBefore rỗng, nghĩa là không có A_IssueReq thì A phát sinh yêu cầu, yêu cầu được yêu cầu nào xếp hàng trước yêu cầu đến từ A, thì trả lưu tại vùng đệm A_WaitNToken. lời sẽ được gửi về A.
S_TranReply = β = 0.31 Nếu place N-1_WaitBefore không rỗng (có A_RelNToken = S_RelNToken = γ = 204.8 SPNToken trong đó), nghĩa là tồn tại yêu cầu đến trước yêu cầu A. Do hệ thống hoạt động FIFO, nên bản tin trả lời sẽ trả về cho SuperClient. Nếu A_WaitReply rỗng nghĩa là yêu cầu đến từ A đã được phục vụ thì các yêu cầu đến từ SuperClient ngay sau A, đang được xếp hàng tại place N-1_WaitReply sẽ được chuyển tất cả (ký hiệu bới trọng số các cung tương ứng là F) sang N- 1_WaitBefore thông qua việc kích hoạt transition Merge . Sau khi bản tin trả lời được gửi đi, NetworkToken sẽ được giải phỏng, gửi đến trạm kế tiếp (Super Client). Hình 6: SPN của hệ thống FileServer Từ các thông số của hệ thống đã N-1_TranNToken = γ = 204.8 cho, ta tính được Đơn vị: số lần kích hoạt / ms tốc độ kích hoạt cho từng t-transition: b) Kết quả phân tích định tính System has 551 states. A_IssueRq có tốc độ: λ = 0.09 Including 277 vanishing states, 274 tangible states. N-1_IssueRq = m(N-1_Idle)*0.01, với m(N-1_Idle) *** SYSTEM IS 3-BOUNDED *** là số SPNToken của N-1_Idle tại hình trạng m. *** SYSTEM IS LIVE *** S_IssueReply = η = 0.5 A_TranRq = N-1_TranRq = µ = 10.
*** SPN IS NOT CONSERVATIVE *** cho các hệ thống Client-Server có hoạt động phức tạp hơn, phản ánh được sự phong phú, đa dạng, đặc thù *** SYSTEM IS NOT REVERSIBLE *** của các ứng dụng trong thực tế. c) Kết quả phân tích định lượng Các tính chất của hệ thống cũng như các thông số Chúng ta thu được các thông số: đưa ra mang lại cái nhìn sâu sắc hơn về hệ thống và Pr(A_Idle = 1) = α = 36.194% đặc biệt hữu ích đối với các nhà thiết kế và quản trị E(S_CapNToken) = 0.090 mạng. U(N-1_CapNToken) = 19.586% IV. KẾT LUẬN Từ việc tính U cho các place ta có thể vẽ được biểu đồ hiệu suất sử dụng tài nguyên như hình 8. Bài báo trình bày về phương pháp đánh giá hiệu năng sử dụng mạng Stochastic Petri. Phương pháp có các ưu điểm lớn trong khả năng: − Mô phỏng hệ thống ở cấp độ phức tạp cao. − Thực hiện các phân tích hiệu năng định tính và định lượng đáng tin cậy. Tuy nhiên, phương pháp này cũng bộc lộ những nhược điểm cơ bản sau: − Nguy cơ bùng nổ trạng thái (state explosion) đối với các hệ thống quá phức tạp dẫn đến việc phân tích hiệu năng khó thực hiện (do đòi hỏi tài nguyên lớn). − Khó khăn trong việc biểu diễn hệ thống về SPN do trình độ mô phỏng của người sử dụng (bao gồm: nhận thức về hệ thống và kiến thức về SPN). Hình 7: Cây trạng thái − Yếu tố thời gian trong SPN phải tuân theo phân bố mũ, trong khi, trên thực tế có nhiều hệ thống tồn tại các phân bố thời gian khác nhau không có khả năng chuyển đổi về chuỗi Markov, các hệ thống non- Markovian [4]. Để SPN thực sự trở thành một phương pháp hữu hiệu trong đánh giá hiệu năng, hướng nghiên cứu trong thời gian tới đây của chúng tôi là: − Vận dụng những ưu điểm của các PN khác như: Coloured Petri Net, Abstract Datatype Petri Net... để có thể mô phỏng hệ thống một cách chính xác hơn. − Xây dựng các hệ thống tính toán song song để tăng Hình 8: Biểu đồ hiệu suất sử dụng tài nguyên hiệu năng tính toán giúp cho việc phân tích các hệ thống có số trạng thái lớn. d) Đánh giá kết quả − Xây dựng phần mềm có khả năng xây dựng SPN Sử dụng SPN đã mô phỏng được các hoạt động cơ thông qua mô tả của người sử dụng theo một bản nhất của hệ thống. Trong đó quan trọng nhất là phương thức đơn giản nhất. mô phỏng được chiến lược phục vụ FIFO của − Nghiên cứu, phát triển các phương pháp, các giải FileServer. Từ mô phỏng này chúng ta có thể mở rộng
Models”, (invited) Carl Meyer and R. J. Plemmons thuật mới có thể đối phó đối với các hệ thống có số (eds.), IMA Volumes in Mathematics and its lượng trạng thái là không giới hạn (Ví dụ: SPN Applications, Vol. 48, pp. 145-191, Springer-Verlag, không giới hạn trạng thái – Infinite SPN [1]). Heidelberg, 1993. TÀI LIỆU THAM KHẢO [7] SUSANN ALLMAIER, DAVID KREISHE, “Parallel [1] B.R.HAVERKORT, Performance of Computer Approaches to the Numerical Transient Analysis of Communication Systems, John Wiley & Sons, 1998. Stochastic Reward Nets”, In Proc. Parallel Computing [2] NEIL J.GUNTHER, The Practical Performance Proc. IEEE 20th Int. Conf. on Application and Theory Analyst, McGraw-Hill, 1998. of Petri nets (ICATPN'99), Williamsburg, USA, 1999. [3] F.DICESARE,..., “Practice of Petri Nets in Manufactoring”, Chapman & Hall, 1994. [8] Website: Petri Nets World: Online Services for the [4] K.S.TRIVEDI,..., “The Evolution of Stochastic Petri International Petri Nets Community, Net”, In Proc.World Congress on Systems Simulation , http://www.daimi.au.dk/PetriNets. Singapore, Sept. 1-3, 1997. [5] O.C.IBE,..., “Performance evaluation of client-server Ngày nhận bài: 09/07/2003 systems”, IEEE Transactions on Parallel and Distributed Systems, 4(11) 1993. [6] G.CIADO,..., “Automated generation and analysis of Markov reward models using Stochastic Reward Nets, Linear Algebra, Markov Chains, and Queueing SƠ LƯỢC TÁC GIẢ TẠ HẢI TÙNG Sinh ngày 26 tháng 10 năm 1980 tại Hà Nội. Tốt nghiệp Đại học Bách khoa Hà Nội ngành Công nghệ thông tin, năm 2003. Hiện công tác tại Khoa Công nghệ Thông tin Đại học Bách khoa Hà Nội Hướng nghiên cứu: Đánh giá hiệu năng, truyền thông và mạng máy tính Email: tungth@it-hut.edu.vn