تا زمانی که S همه گره های گراف را در خود جای نداده است عملیات زیر را انجام می دهیم:
گره دلخواه v را که در S موجود نیست انتخاب می کنیم. عملیات جستجوی اول عمق را با شروع از v انجام می دهیم. در اجرای این جستجو، هر بار که الگوریتم، توسعه یک گره را در هنگام بازگشت خاتمه داد، گره مذکور را در S ثبت می کنیم.
گراف ترانهاده G را به دست می آوریم. G^T با معکوس کرده جهت همه لبه های G حاصل می شود.
تا زمانی که S خالی نشده:
عنصر بالای پشته را خوانده (v)، عملیات جستجوی اول عمق را با شروع از v انجام می دهیم. مجموعه گره هایی که در این پیمایش خوانده می شوند در یک زیر گراف همبند قوی با حضور v قرار دارند (SCC). این گره ها را ثبت کرده و آنها را از گراف G و همچنین پشته S حذف می کنیم.
به این ترتیب می توان حوزه های همبند قوی را در یک گراف جهت دار شناسایی نمود.
■
با اجرای این الگوریتم بر روی گراف ۴٫۲۱ می بینیم که همه گره ها عضو یک حوزه همبند قوی بوده و در نتیجه کل گراف همبند قوی می باشد. به این ترتیب شبکه پتری متناظر با آن یعنی مدل ۴٫۲۰ نیز همبند قوی خواهد بود.
با استناد به قضیه ۴، همبند قوی بودن مدل پتری ۴٫۲۰ و نیز حضور یک توکن در شبکه در وضعیت M₀، می توان نتیجه گرفت که شبکه مذکور live است.
۴٫۶٫۳٫۲٫ Safeness
با توجه به قضیه ۵، یک state machine که دارای خصوصیت liveness می باشد، در صورتی safe خواهد بود که در وضعیت M₀ دقیقا یک توکن در شبکه وجود داشته باشد. زیرا با توجه به اینکه وزن تمام لبه ها ۱ است و همه گزارها در شبکه نیز با هر بار اجرا شدن دقیقا یک توکن مصرف کرده و یک توکن ایجاد می کنند، تعداد توکن های قابل انتقال به یک موقعیت، هرگز بیش از ۱ نخواهد بود. پس شبکه ۱-bounded یا safe خواهد بود.
در شبکه ۴٫۲۰ در M₀ دقیقا یک توکن وجود دارد بنابراین این شبکه safe است.

( اینجا فقط تکه ای از متن پایان نامه درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

همچنین با بررسی گراف پوشای مدل ۴٫۲۰، خواهیم دید که در هیچ یک از وضعیت های محتمل در گردش کنترل شبکه، تعداد توکن های موجود در موقعیت ها بیش از یک نمی شود. این امر نشان می دهد که تمام موقعیت های شبکه ۱-bounded و یا safe هستند. گراف پوشای این شبکه پتری در شکل ۴٫۲۲ آمده است.
شکل ۴٫۲۲٫ گراف پوشای کدل پتری ۴٫۲۰
۴٫۶٫۳٫۳٫ Reversibility
برای بررسی این خصوصیت لازم است به تعریف Reversibility توجه کنیم. با یاد آوری تعریف این مفهوم و نیز خاصیت Reachability از فصل ۲ داریم: شبکه پتری ()، Reversible خوانده می شود اگر برای هر وضعیت M، در دنباله قابل اجرا از (R())، از طریق M، reachable باشد.
با این تعریف، در شبکه های کوچک می توان با بررسی کلیه وضعیت های محتمل در شبکه، reachable بودن را از طریق آنها بررسی نمود. در صورتی که از طریق تک تک این وضعیت ها ( تا ) قابل دسترسی باشد این شبکه Reversible است. با توجه به اینکه این وضعیت ها تماما در گراف پوشای مدل منعکس می شوند می توان با بررسی یک به یک گره های گراف این حالات را بررسی نمود.
به کمک الگوریتم کزاراجو می توان نشان داد که گراف ۴٫۲۲ یک گراف همبند قوی است. این بدان معنی است که از هر گره به گره ی دیگر مسیر جهت داری وجود دارد. در نتیجه از هر گره Si به S0 مسیری وجود دارد. پس امکان بازگشت به M₀ از هر M_i در شبکه پتری مربوط به آن وجود دارد.
در نتیجه می توان گفت که شبکه پتری مذکور Reversible است.

تشریح ساختار سیستم ذخیره سازی در ESX
با تکیه بر مقدمات ارائه شده در فصل ۲، در این بخش به توضیح مفصل تری درباره ساختار ذخیره سازی در ESX خواهیم پرداخت تا در بخش های بعدی بتوانیم مدل فرمالی از آن تهیه کنیم.

تشریح ساختار سیستم ذخیره سازی
در این بخش به بررسی مدل چند لایه ای سیستم ذخیره سازی فایل ها در ESX و نحوه کار آنها خواهیم پرداخت ]۶۳[ و ]۷۳[.
با توجه به اینکه در یک دیتا سنتر به احتمال زیاد طیف متنوعی از دستگاه های ذخیره سازی در کنار منابع پردازشی مورد استفاده قرار می گیرد، لازم است این بخش در ESX انعطاف و قابلیت همکاری زیادی با این تجهیزات داشته باشد. شکل ۴٫۲۱ شمایی از مدل لایه ای معماری ذخیره سازی در ESX را نشان می دهد.
شکل ۴٫۲۳٫ نمای شماتیک مدل چند لایه ای سیستم ذخیره سازی در ESX ]63[
بخش های اصلی در شکل مذکور عبارتند از:
Virtual Machine Monitor (VMM)
Virtual SCSI Layer
VMware File System (VMFS)
SCSI Mid-Layer
HBA Device Drivers
Virtual Machine Monitor (VMM)
Virtual Machine Monitor (VMM)
وظیفه اصلی ماژول VMM مانیتور نمودن کلیه رفتار و فعالیت های ماشین مجازی در تمام سطوح است. این بخش ها شامل پردازنده، حافظه، ورودی / خروجی، و دیگر فعالیت ها و روابط آن با VMkernel می باشد. ماژول VMM شامل لایه ای است که دستگاه های SCSI را برای ماشین های مجازی شبیه سازی می کند. سیستم عامل ماشین مجازی دسترسی مستقیمی به تجهیزات ذخیره سازی ندارد زیرا زیر ساخت مجازی سازی به کمک ماژول ذخیره سازی، تنها یک رابط SCSI در اختیار این سیستم عامل قرار داده است. بنابراین بدون توجه به نوع سیستم عامل، از هر ماشین مجازی نرم افزارها تنها از طریق یک راه انداز SCSI به دیسک دسترسی دارند. ماشین های مجازی می توانند از راه انداز BusLogic یا LSI برای کار با دیسک های SCSI استفاده کنند. این راه اندازها امکان استفاده از SCSI HBA را برای ماشین های مجازی فراهم می کند.
BusLogic
استفاده از راه انداز BusLogic به این معنی است که شبیه ساز BT-958 در حال استفاده است. این شبیه ساز در واقع نمود پیاده سازی شده پروتکل SCSI-3 است که امکان Ultra SCSI را برای انتقال سریع با نرخ ۴۰MBs فراهم می کند. این شبیه ساز امکان پیکربندی خودکار SCSI را فراهم می کند که به عنوان SCAM^[191] شناخته می شود. این امکان به دیسک SCSI امکان می دهد که با یک شماره شناسه به طور خودکار پیکربندی شود. بنابراین مدیر سیستم نیازی به نسبت دادن دستی شناسه نخواهد داشت.
LSI Logic
استفاده از این راه انداز تعیین می کند که سیستم در حال استفاده از شبیه ساز LSI53C1030 می باشد. این شبیه ساز از تکنولوژی SCSI-320 استفاده می کند. از مزایای این تکنولوژی می توان به مصرف کم انرژی، اعتبار سنجی در دامنه SCSI در هنگام عملیات بر روی دیسک، همخوانی با تکنولوژی PCI-X و بهینه سازی در بررسی افزونگی اشاره کرد. در کنار این مزایا، این شبیه ساز از تکنولوژی TolerANT برای تحمل بیشتر نوسانات سیگنال استفاده می کند. از مزایای دیگر این راه انداز می توان به استفاده از منطق نفی فعال^[۱۹۲] بر روی راه انداز SCSI و فیلتر سازی سیگنال ورودی به دیسک برای بهبود وضعیت تمامیت داده ها اشاره کرد.
تمام مکانیزم ها و مزایای گفته شده برای نرم افزارهایی که از یک SAN برای ذخیره سازی اطلاعات خود استفاده می کنند بسیار مفید است. زیرا این نرم افزارها باید در مقابل مشکلات و اختلالات سیستم ذخیره سازی از جمله قطعی کابل ها، ترکیب بخش های مختلف یک SAN، یا مغایرت بخش های SAN که باعث اختلال در سیستم ذخیره سازی می شود مقاوت داشته باشند.
یک مزیت کلیدی دیگر در LSI53C1030 پشتیبانی زیر ساختی از تکنولوژی انتقال پیام ادغامی^[۱۹۳] است که به عنوان Fusion-MPT شناخته می شود. این معماری با فراهم کردن مکانیزم کارآمدی برای پردازنده سیستم میزبان، به کنترل گر ورودی/ خروجی در سیستم امکان می دهد تا با ارسال همزمان چندین پیام پاسخ به پردازنده در یک سیگنال وقفه، از تعداد context switch ها به نحو محسوسی بکاهد. این راهکارباعث افزایش نرخ انتقال تا ۱۰۰۰۰۰ IOPS بر حسب معیار Ultra320 SCSI می شود. این در حالی است که بار پردازشی سیستم و میزان مداخله تجهیزات جانبی در حداقل میزان ممکن است.
SCSI HBA^[194] مجازی به ماشین های مجازی امکان می دهد که به دستگاه های SCSI منطقی دقیقا مانند یک HBA فیزیکی متصل شود و به وی اجازه اتصال به دستگاه های ذخیره سازی فیزیکی را می دهد. اما بر خلاف HBA فیزیکی، HBA های مجازی به مدیر سیستم اجازه نمی دهد که به ماشین های فیزیکی دسترسی داشته باشند.
بر روی یک سیستم ESX، هر ماشین مجازی می تواند از یک تا چهار SCSI HBA مجازی داشته باشد. این آداپتورهای مجازی می توانند از کنترل کننده های BusLogic و یا LSI استفاده کنند. لازم به ذکر است که این دو راه انداز تنها انتخاب ماشین های مجازی برای کار با دیسک های SCSI است.