Abstract: Nowadays, Performance Evaluation is one of
the most important fields of information technology. Hence,
it has been widely studied in recent years. This paper
presents the performance evaluation method using
Stochastic Petri Net. With the capability of simulating
complex systems and mapping to Markov chain, this
method is powerful widely used in many systems, especially
in computer and communication systems.
I. ĐẶT VẤN ĐỀ
Đánh giá hiệu năng thông qua mô phỏng hệ thống
là một phương pháp hiệu quả và đặc biệt hữu ích đối
với các nhà thiết kế, xây dựng hệ thống. Nền tảng của
phương pháp là:
−
Mô phỏng hệ thống: mô hình hoá cấu trúc
(structure) và mô tả hành vi (behaviour) của hệ
thống.
− Phân tích, đánh giá hiệu năng trên mô hình mô
phỏng hệ thống.
Hiện nay, có ba phương pháp đánh giá hiệ
u năng
thông qua mô phỏng hệ thống [1], đó là: phương pháp
sử dụng Mạng hàng đợi (Queue Network - QN) [1,2],
phương pháp sử dụng Mạng Petri (Petri Net - PN) [3]
và phương pháp sử dụng Chương trình máy tính được
thiết kế đặc thù chỉ để mô phỏng cho một hệ thống [1].
Trong đó, phương pháp cuối cùng tuy cho kết quả với

mạng Petri đơn giản ban đầu, những người quan tâm
nghiên cứu đã cho ra đời một loạt các loại mạng Petri
mức cao (Coloured Petri Net, Predicate Petri Net,
Stochastic Petri Net ) có thể mô phỏng cũng như
phân tích hiệu năng cho các hệ thống từ đơn giản đến
phức tạp. Trong đó, mạng Stochastic Petri (SPN) [1,4]
do khả năng quy tương đương về chuỗi Markov đã tạo
ra một ưu thế vượt trội trong đánh giá hiệu năng định
lượng và trở thành một hướng nghiên cứu nhiều hứa
hẹn. PN nói chung và SPN nói riêng là những vấn đề
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
tương đối phức tạp, vì vậy, trong giới hạn ngắn gọn
của bài báo chúng tôi tập trung vào việc ứng dụng
SPN trong đánh giá hiệu năng, các khía cạnh chuyên
sâu có thể được tìm hiểu thêm trong các tài liệu tham
khảo [1,3,4,6].
II. PHƯƠNG PHÁP ĐÁNH GIÁ HIỆU NĂNG
HỆ THỐNG SỬ DỤNG MẠNG STOCHASTIC
PETRI
Hình1 chỉ rõ các bước của phương pháp (mỗi bước
ứng với một cung, bước tương ứng vớ
i cung đứt nét
có thể được thực hiện nhiều lần để mang lại kết quả

transition tương ứng có các cung vào (input arc), cung
ra (output arc), cung ức chế (inhibitor arc) phân biệt
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
vấn đề ngữ nghĩa nên trong bài báo này vẫn sử dụng
nguyên gốc các thuật ngữ: place, transition, token).
Một sự phân bố các token tại mỗi place là một hình
trạng (marking) của SPN
Về mặt hình thức, SPN được định nghĩa như sau:
Định nghĩa 1: Một SPN được biểu diễn bởi:

SPN = (P, T, Pr, I, O, H, W, m
0
)

Trong đó: P: tập các place (|P| = n
p
).
T: là tập các transition (|T| = n
t
).
Pr: tập ưu tiên gắn với mỗi transition. Với lưu ý một i-
transition luôn có giá trị ưu tiên lớn hơn bất kỳ một t-
transition nào.
I, O, H: Các tập trọng số tương ứng với cung vào, cung
ra, cung ức chế.
W:T
→
R


p
2

t
2
CPU kết thúc
xử lý lệnh
t
1
CPU bắt đầu
xử lý lệnh

p
3
CPU đang xử lý
lệnh
CPU sẵn sàng

p
1

Mô phỏng
(1)

Xây dựng
cây
trạng thái
(
2

một số thành phần mở rộng tạo nên mạng Stochastic
Reward (SRN) [6,7]
− Ý nghĩa các thành phần của SPN trong mô phỏng hệ
thống:
Place: Đại diện cho tài nguyên hay tình trạng của
tài nguyên.
Transition: Đại diện cho một sự kiện trong chuỗi sự
kiện xảy ra trong quá trình hoạt động của hệ thống.
i-transition:
Đại diện cho sự kiện xảy ra tức thời khi
mà điều kiện kích hoạt được thoả mãn.
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.
Cung: Đại diện cho luồng vào và luồng ra của hệ
thống.
Token: Bản thân token không có ý nghĩa bằng số
lượng token. Số lượng token đại diện cho số lượng tài
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
hoạt một transition (cấu thành một sự kiện). Sự lưu
chuyển token thể hiện hoạt động của hệ thống. Sự
phân bố các token đại diện cho các trạng thái của hệ
thống.
Xuất phát từ ý nghĩa trên chúng ta thấy được rằng:
− Cấu trúc của hệ thống có thể được mô phỏng bởi sự

biểu diễn về mặt hình học các thành phần của SPN
(place, transition, token, cung).
− Hoạt động của hệ thống có thể được mô phỏng bởi


Hình 3: Sự lưu chuyển token trong SPN
Khi trong một hình trạng có nhiều hơn một
transition có khả năng kích hoạt thì luật sau sẽ được
áp dụng để chọn ra một transition được kích hoạt [4]:
Một transition trong số các i-transition có khả năng
kích hoạt (nếu tồn tại) sẽ được chọn đầu tiên theo xác
suất:
W
W(t)
=p
. Với W là tổng độ phức tạp của các
i-transition có khả năng kích hoạt.
Nếu không tồn tại i-transition có khả năng kích
hoạt, một t-transition sẽ được chọn theo một trong hai
chiến lược:
1. Chiến lược “chạy đua” (race policy)
Trong chiến lược này thì t-transition nào có tốc độ
lớn nhất (hay thời gian trễ nhỏ nhất) trong số các t-
transition có khả năng kích hoạt sẽ được chọn kích
hoạt trước. Chính vì vậ
y, nảy sinh một vấn đề: So
sánh thời gian trễ giữa các t-transition có gốc thời gian
khác nhau. Trong bối cảnh đó có hai phương pháp:
− Phương pháp khởi tạo lại từ đầu (resampling): Khi
2

2
3


Phương pháp nhớ mức cao: Phương pháp này,
ngoài khả năng lưu vết các transition vẫn tiếp tục giữ
khả năng kích hoạt, còn có khả nă
ng lưu vết một
transition khi nó không có khả năng kích hoạt ở nhịp
sau, để đến khi nó lại có khả năng này ở một nhịp nào
đó trong tương lai thì gốc thời gian không phải khởi
tạo lại.
2. Chiến lược lựa chọn trước (preselection policy)
Trong đó t-transition sẽ được chọn với xác suất
W
W(t)
=p . Với W là tổng tốc độ kích hoạt của các t-
transition có khả năng kích hoạt.
b) Các bước mô phỏng hệ thống
Bước 1
: Xác định các hoạt động, chuỗi sự kiện của
hành động và tài nguyên cần thiết cho quá trình hoạt
động của hệ thống.
Bước 2
: Sắp đặt các hoạt động theo mối quan hệ
nhân quả xác định trước (hoạt động nào kéo theo
hoạt động nào)
Bước 3
: Mỗ
i hoạt động hoặc sự kiện sẽ được đại
diện bởi một transition.
Bước 4
: Các tài nguyên cần thiết, các trạng thái
trải qua trong quá trình hoạt động của tài nguyên

có trong tập các hình trạng đã có), đến khi không thể
nảy sinh ra một hình trạng mới nào.
1. input {P,T,PR,I,O,H,W,m
0
}
2. NM := {m
0
}; RS := {m
0
}
3. while NM
≠

∅

4. begin
5. let m
∈
NM
6. NM := NM - {m}
7. for all t
∈
E
t
(m)
8. begin
9. let m
→
t
m'

hiệu năng đề cập trong bài báo này chỉ quan tâm đến
các hệ thống hữu hạn trạng thái.
3. Phân tích hiệu năng định tính
Phân tích hiệu năng định tính đem lại câu trả lời về
các tính chất, thuộc tính của hệ thống. Dưới đây sẽ
định ngh
ĩa một số thuộc tính tiêu biểu của hệ thống
cũng như cách phân tích nó trong SPN.
a) Tính dừng
Định nghĩa 4: Hệ thống được gọi là dừng nếu trong
quá trình hoạt động hệ thống đạt tới “điểm chết”
(deadlock) (điểm tại đó không có sự kiện tiếp theo xảy
ra và hệ thống sẽ giữ trạng thái mà nó đạt được đến
khi nào có tác động c
ủa môi trường bên ngoài).
Ngược lại ta có hệ thống “sống” (live)
Tính chất này được phân tích trong SPN dựa vào
tập hình trạng của hệ thống: Nếu tồn tại hình trạng
không có khả năng kích hoạt một transition nào, ta kết
luận: hệ thống dừng.
b) Tính giới hạn (Bounded)
Định nghĩa 5
: Một hệ thống được gọi là giới hạn
nếu số lượng trạng thái của nó là giớ
i hạn.
Trong SPN, khái niệm giới hạn được gắn với số
lượng token tại mỗi place: Nếu tồn tại một place có số
lượng token tăng lên không ngừng vượt quá một giới
hạn định trước thì coi hệ thống là không giới hạn. Nếu
hệ thống có số lượng token tại mỗi place luôn nhỏ hơn

} = Pr{X
n+1
=x
n+1
/X
n
=x
n
}
(1)
Với X
i
∈
Τ
là trạng thái tại thời điểm t
i
,
Τ
là tập
trạng thái, t
0
<t
1
< <t
n+1
. Do thời gian là liên tục mà
không gian trạng thái lại rời rạc, nên khi đạt đến một
trạng thái thì CTMC sẽ “ở” trạng thái đó trong một
khoảng thời gian gọi là thời gian trễ (residence time)
tuân theo phân bố xác suất mũ với hàm phân bố:

21
1
t
→ với t
1
là t-transition với tốc độ kích hoạt
µ
1.
λ
Q =

µ
2
µ
1
1
3
2
-
µ
1
µ
2
µ
1
µ
2

λ
-

,,
(3)
5. Phân tích định lượng
Nền tảng của phân tích định lượng là việc tính xác
suất trạng thái p của hệ thống tại giai đoạn bền vững
(steady-state).
Giai đoạn bền vững là giai đoạn mà tại đó xác suất
để hệ đạt đến một trạng thái trong không gian trạng
thái không phụ thuộc vào yếu tố thời gian (Chú ý: Từ
state trong steady-state nên hiểu là “giai đoạn” thay vì
“trạ
ng thái” do nó không phải là một trạng thái nằm
trong không gian trạng thái của hệ thống).
p được xác định thông qua việc giải hệ phương
trình:

∑
∈
==
ψ
i
i
ppQ 1,0
(4)

ψ
: Không gian trạng thái.
(các phương pháp kinh điển có thể áp dụng: Gauss,
Jacobi, Gauss-Seidel, SOR )
Công đoạn này đơn giản nhưng đòi hỏi nhiều tài

kkPE
(6)
− Thông lượng tại transition t:

∑
∈∈
=
)(),(
0
m)W(t,
mEtmRm
mt
t
pX
(7)
− Hiệu suất tại một place hay hiệu suất sử dụng tài
nguyên:

[]
()
∑
∞
=
==
1
#Pr
k
kPPU
(8)
Trong đó:

Các Client có cấu hình giống hệt nhau.
−
Một Client chỉ phát sinh yêu cầu khi yêu cầu ở nhịp
trước đã đượ
c phục vụ.

Hình 5: Sơ đồ hệ thống FileServer
−
FileServer phục vụ theo chiến lược FIFO với mỗi
lần truy cập đường truyền chỉ để gửi trả lời cho một
Client.
− Thông lượng đường truyền: 10Mbit/s.
− Chiều dài đoạn cáp: 2000m.
− Số bit trung bình một gói tin yêu cầu: 1000bpp.
− Số bit trung bình một gói tin trả lời: 32000bpp.
−
Số bit biểu diễn Token: 24bit
−
Thời gian trung bình một trạm phát sinh yêu cầu :
11.11ms.
− Thời gian trung bình xử lý một yêu cầu tại server:
2ms.
a) Mô phỏng hệ thống
Để mô phỏng chúng ta chia hệ thống ra thành 3
phần: Client A, FileServer và SuperClient. Trong đó,
SuperClient đại diện cho tất cả các Client giống nhau
còn lại với mục đích làm giảm số lượng place,

ống với ClientA chỉ khác
khi Network Token đến trạm này thì trước khi được
chuyển sang trạm kế tiếp phải quay vòng với số lần
bằng đúng số Client mà nó đại diện. Công việc đếm
này được thực hiện bởi N-1_Count. Hơn nữa, tốc độ
kích hoạt của N-1IssueReq phụ thuộc vào số token
trong
N-1_Idle
nghĩa là phụ thuộc vào số Client rỗi
(còn có khả năng ra yêu cầu).
− Mô ph
ỏng FileServer
Yêu cầu đến FileServer được xếp hàng tại
S_GetReq. Sau khoảng thời gian được xác định bởi
tốc độ kích hoạt của
S_IssueReply
, yêu cầu được xử
lý và FileServer phát ra bản tin trả lời được lưu tại
S_WaitNToken. Khi NetworkToken đến bản tin trả
lời sẽ được chuyển đến đúng trạm đang đợi tùy theo
tình trạng (số lượng token) tại A_WaitReply (đại diện
cho yêu cầu đế
n từ A),
N-1_WaitReply
(đại diện cho
các yêu cầu đến từ SuperClient sau yêu cầu từ A đến
FileServer), N-1_WaitBefore (đại diện cho các yêu
cầu đến trước yêu cầu từ A):
Nếu place
N-1_WaitBefore

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).
Từ các thông số
của hệ thống đã
cho, ta tính được
tốc độ kích hoạt cho từng t-transition:
A_IssueRq
có tốc độ:
λ
= 0.09
N-1_IssueRq
= m(N-1_Idle)*0.01, với m(N-1_Idle)
là số SPNToken của

*** SYSTEM IS LIVE ***
Hình 6: SPN của hệ thống FileServer
*** SPN IS NOT CONSERVATIVE ***
*** SYSTEM IS NOT REVERSIBLE ***
c) Kết quả phân tích định lượng
Chúng ta thu được các thông số:
Pr(A_Idle = 1) =
α
= 36.194%
E(S_CapNToken) = 0.090
U(N-1_CapNToken) = 19.586%
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.

Hình 7: Cây trạng thái

Hình 8: Biểu đồ hiệu suất sử dụng tài nguyên
d) Đánh giá kết quả
Sử dụng SPN đã mô phỏng được các hoạt động cơ
bản nhất của hệ thống. Trong đó quan trọng nhất là
mô phỏng được chiến lược phục vụ FIFO của
FileServer. Từ mô phỏng này chúng ta có thể mở rộng
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ù
của các ứng dụ
ng trong thực tế.
Các tính chất của hệ thống cũng như các thông số

−
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
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.
− Xây dựng phần mề
m có khả năng xây dựng SPN
thông qua mô tả của người sử dụng theo một
phương thức đơn giản nhất.
− Nghiên cứu, phát triển các phương pháp, các giải
thuật mới có thể đối phó đối với các hệ thống có số
lượng trạng thái là không giới hạn (Ví dụ: SPN
không giới hạn trạng thái – Infinite SPN [1]).
TÀI LIỆU THAM KHẢO
[1] B.R.HAVERKORT, Performance of Computer
Communication Systems, John Wiley & Sons, 1998.
[2] NEIL J.GUNTHER, The Practical Performance
Analyst, McGraw-Hill, 1998.
[3] F.DICESARE, , “Practice of Petri Nets in
Manufactoring”, Chapman & Hall, 1994.
[4] K.S.TRIVEDI, , “The Evolution of Stochastic Petri
Net”, In Proc.World Congress on Systems Simulation ,
Singapore, Sept. 1-3, 1997.
[5] O.C.IBE, , “Performance evaluation of client-server

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 tính
Email: [email protected]