بخشی از مقاله
از آنجایی که شبکههاي پتري قدرت توصیف بیشتري را در مقایسه با شبکههاي صف فراهم می نمایند و همچنین یک نمایش گرافیکی و واضح را از سیستم به همراه یک فرمالیسم ریاضی از آن ارائه می دهد، این شبکهها ارائه دهنده چارچوبی براي تحلیل، اعتبارسنجی و ارزیابی کارایی میباشند.
شبکههاي پتري ابزاري مناسب براي مدلسازي ریاضی و گرافیکی به حساب میآیند،بنابراین از این ابزار میتوان براي مدلسازي، توصیف، و تحلیل سیستمهایی که داراي ماهیتی همزمان، آسنکرون، توزیع شده، موازي، نامعین، و یا اتفاقی هستند استفاده نمود.
امروزه استفاده از ابزار فوق کاربرد وسیعی پیدا کرده و از آن براي مدلسازي انواع سیستم ها استفاده میشود. یکی دیگر از خصوصیات مهم شبکه پتري قابل اجرا بودن آنهاست که از همین خاصیت میتوان براي ارزیابی رفتار و کارایی یک سیستم بهره جست. در این مقاله به بررسی انواع شبکه هاي پتري و ارتباط آن با مدلسازي و ارزیابی کارایی نرمافزار پرداخته شده است.
واژههاي کلیدي: مدلسازي، شبکه هاي پتري، ارزیابی کارایی، مهندسی نرم افزار.
1
-1 مقدمه
مدل یعنی نمایشی ساده شده از یک پدیده که روي برخی از جنبههاي یک سیستم تاکید کند و از جنبه هاي دیگر چشم پوشی نماید. به همین دلیل مدل گاربرد گستردهاي در جنبه هاي مختلف زندگی انسـان پیـدا کـرده اسـت و نقـش بـه تصـویر کشـیدن تجریدهاي مختلف از موضوعات مطرح براي انسان را بر عهده دارد.
شبکههاي پتري ابزاري مناسب براي مدلسازي ریاضی و گرافیکی به حساب میآیند. از این ابزار میتوان براي مدلسازي، توصیف، و تحلیل سیستمهایی که داراي ماهیتی همزمان، آسنکرون، توزیع شده، موازي، نامعین، و یا اتفاقی هستند استفاده نمـود. در واقـع شبکههاي پتري جزء مدلهایی هستند که قادرند به صورت همزمان حالت و عملکرد یک سیستم را نشان دهند. امروزه اسـتفاده از ابزار فوق کاربرد وسیعی پیدا کرده و از آن براي مدلسازي انواع سیستم ها استفاده میشود.
یکی دیگر از خصوصیات مهم شبکه پتري قابل اجرا بودن آنهاست که از همین خاصیت میتوان براي ارزیابی رفتار و کارایی یـک سیستم بهره جست. امروزه نرم افزارهاي قوي شبیه سازي وجود دارند که بر اساس شبکههاي پتري کار مـیکننـد. ابزارهـاي فـوق قادرند با انواع پردازش، به بررسی مشکلات احتمالی سیستمها و تولید فضاي حالت پرداخته و عملکرد کلی سیستم را شـبیهسـازي نمایند.
-2 شبکه پتري
اساس شبکههاي پتري بر پایه گراف، بنا نهاده شده است. اگر بخواهیم یک توصیف غیر رسمی از آن داشته باشیم میتوان گفت که یک گراف جهتدار دو قسمتی است که از دو عنصر مکان و انتقال تشکیل شده است. یک توصیف رسـمی از شـبکههـاي پتـري بـه
شکل زیر میتواند باشد.
تعریف: شبکه پتري یک پنج تایی به شکل ( (P ,T ,I- ,I+ ,M0 است که:
1. P یک مجموعه متناهی از مکانها است.
2. T یک مجموعه متناهی از انتقالها است.
3. p∩T = Ф مجموعه مکانها و گذرها از هم جدا شده میباشند .
4. I- , I+ :P*T→N به ترتیب توابع تلاقی پیشرو و پسرو نامیده میشوند.
5. M0 :P→N0 تابع علامت گذاري اولیه نامیده میشود.
توابع I+,I- نمایش دهنده ارتباط میان مکانها و انتقالها هستند. اگر رابطه I-(P,T)>0 برقرار باشد در این صورت کمانی از مکـان P به انتقال T وجود دارد. در این حالت به مکان P، یک مکان ورودي گفته مـیشـود. اگـر رابطـه I+(P,T)>0 برقـرار باشـد در
اینصورت کمانی از انتقال T به مکان P وجود دارد. در این حالت به مکان P، یک مکان خروجی گفته میشود. توابع تلاقـی اعـداد طبیعی را به کمان ها گفته میشود. زمکانیکه هر مکان ورودي از انتقال T حداقل به تعداد وزن کمانی که آن را به انتقال T وصـل میکند حاوي مهره باشد، در اینصورت گفته میشود که انتقال T فعال است. یک انتقال فعال میتواند آتش شود. در چنین حـالتی انتقال مورد نظر به مقدار وزن هر یک از کمان هاي ورودي از هر یک از مکانهاي ورودي مهره برداشته و به مقدار وزن هـر یـک از مکان هاي خروجی در هر یک از مکان هاي خروجی مهره ایجاد میکند . تعداد اولیه مهرهها در شبکه با اسـتفاده از تـابع M0 کـه نشان دهنده تعداد مهرهها در هر مکان از شبکه است مشخص میشود. به تعداد مهره ها در شبکه علامتگذاري شبکه میگویند. بـه
M0 ،علامتگذاري اولیه میگویند. زمانی که یک انتقال آتش میشود ممکن است علامتگذاري شبکه تغییر کند. شکل 1 یک شبکه پتري را نشان میدهد که از 4 مکان و 2 انتقال تشکیل شده است. شکل مذکور شبکه پتري را قبل و بعد از آتش شـدن انتقـال t1
نشان میدهد ، بعد از آتش شدن انتقال t1، یک مهره از مکان P1 و P2 برداشد و یک مهره در مکان P3 ایجاد میشود.
2
شکل((1 یک شبکه پتري قبل و بعد از آتش شدن یک انتقال[1]
شبکههاي پتري بنا به تعریف مذکور گراف هاي دو قسمتی هستند. بنابراین رئوس آن را می توان به 2 بخش تقسیم کرد :
مکان: رئوسی که به شکل دایره هستند.
انتقال: رئوسی که به شکل میله هستند.
شبکههاي پتري جهتدار هستند. بنابراین کمانی که 2 رأس را به یکدیگر متصل میکند جهتدار است. کمان ها تنها میتوانند مکان ها را به انتقالها و یا انتقالها را به مکان ها متصل کنند.
انتقالها و مکانها: یک انتقال میتواند نشانگر یک پردازشگر رویداد، گام محاسباتی، الگوریتم، وظیفه و ... باشد. مکـانهـا بـه دو دسته مکانهاي ورودي و مکانهاي خروجی قابل تقسیم هستند. یک مکان ورودي میتواند نشانگر بافر، پیش شـرط، داده ورودي، منابع مورد نیاز، شرایط یا سیگنال هاي ورودي باشد. یک مکان خروجی میتواند نشانگر بافر، پس شرط، داده خروجـی، منـابع آزاد شده نتایج یا سیگنالهاي خروجی باشد.
کمانها: کمانها وسیله اتصال مکانها به انتقالها را دارند. زمانیکه از یک مکان به یک انتقال، کمانی وجـود داشـته باشـد مـی تواند نشانگر آن باشد که پردازشگر، نیاز به منبعی در بافر دارد. رویداد براي آنکه اتفاق بیفتد نیاز به پیش شرط دارد. الگوریتم، نیاز به داده ورودي دارد. وظیفه، نیاز به منبع دارد. زمانیکه از یک انتقال به یک مکان، کمانی وجـود داشـته باشـد مـی تـوان تعـابیري همچون پردازشگر، تولید کننده منبعی در بافر خروجی است. رویداد، بعد از آنکه رخ داد، پس شـرط را تولیـد مـی کنـد. الگـوریتم تولید کننده داده خروجی است. وظیفه، تولید کننده منبع است.
شبکههاي پتري علامت گذاري شده: شبکه پتري که شامل مهره باشد، شبکه پتري علامتگذاري شده است. مهرهها بـه صـورت نقطه (.) نمایش داده میشود و در مکان ها قرار میگیرند. یک علامتگذاري از یک شبکه پتري، نگاشتی است که یک عدد نامنفی صحیح (تعداد مهرهها) را به هر مکان در شبکه انتساب میدهد. علامتگذاري، توصیف کننده وضعیت شـبکه پتـري اسـت. در یـک شبکه پتري، مهرهها غیر قابل تمیز هستند. وجود یک یا چند مهره نشان دهنده در دسترس بودن منبع یا تکمیل شـرط اسـت. در حالیکه عدم حضور مهره مشخص کننده آن است که شرط برقرار نیست یا منبع در دسترس نمیباشـد. مکـان هـا و علامتگـذاري،
دربرگیرنده طبیعت توزیع شده سیستم است. علامتگذاري می تواند توسط یک مهره ارائه شود. علامتگذاري در شبکه پتري سـمت چپ شکل 1 به صورت M[1,1,0,0] میباشد.
مثال: در شکل 2 وقتی T4 شلیک میشود که حداقل دو مهره یکی در P1 و یکی در P2 وجود داشته باشد. همچنین T2 وقتـی شلیک میشود که حداقل 3 مهره در P6 وجود داشته باشد.
شکل (2) نمونهاي از شبکه پتري[1]
در این قسمت شبکه پتري به عنوان اساس دیگر مدلهاي قابل اجرا مورد بررسی قرار گرفت. اگر چه این نوع شبکه براي بررسی سیستمهایی با مؤلفههاي همزمان و داراي تعامل، مناسب است. اما این شبکه خود به خود نمیتواند به عنـوان مـدل قابـل اجـرا از معماري قرار بگیرد. دیگر شبکههایی که مورد بررسی قرار خواهد گرفت در واقع به نوعی نمونه توسعه یافتهاي از ایـن شـبکه مـی-
باشد.
3
-1-2 انواع شبکههاي پتري
در این بخش، انواع شبکههاي پتري معرفی میگردند.
-1-1-2 شبکههاي پتري تصادفی1
یکی از افزونهها بر شبکه پتري کلاسیک، شبکه پتري تصادفی است. آنچنان که از نام آن بر میآید، امکان اضافه کردن احتمال را ایجاد میکند. این شبکه بر اساس شبکه پتري کلاسیک ساخته میشود. با این تفاوت که لزوماً در یک حالت خاص، عملیات شلیک کردن، قطعی نیست و از یک احتمال پیروي میکند. این نرخ شلیک ممکن است تابعی از وضعیت کلی شبکه باشـد. شـکل 3 یـک نمونه از شبکه پتري تصادفی براي نشان دادن فرآیند روشن شدن لامپ را نشان میدهد. یک لامپ خاموش با فرآیند روشن شـدن لامپ را نشان میدهد. یک لامپ خاموش با یک احتمال و یک تاخیر تصادفی روشن میگردد. ممکن است که با یک احتمال لامپ دچار خرابی شده و روشن نشود. همین صحبت در مورد لامپ روشن هم وجود دارد.
