سلام.
دوستان این سوال مربوط به کنکور آی‌تی ۹۱ مربوط به تأمین همروندی فرایندها با SWAP هست.
کتاب دکتر حقیقت در توضیحات٬ استفاده از SWAP را همراه با نقض شرط پیشرفت معرفی کرده.
کلید سازمان سنجش هم گزینه‌ی ۲ رو به عنوان کلید معرفی کرده (و کلید هم تغییر نکرده)
اما مشکلی که هست اینه که:
خودِ دکتر حقیقت برای این تست٬ این کد رو درست فرض کردند. به نظر شما استفاده از SWAP در تأمین همروندی نقض شرط پیشرفت رو داره؟ چون به نظر هیچ‌یک از فرایندها نوبت فرایند دیگر را رعایت نمیکنند...
سؤال را پیوست کردم.
ممنون میشم راهنمایی کنید.
متن سؤال:
[attachment=7939]
پاسخ دکتر حقیقت:
[attachment=7940]
با فرض اینکه swap اتمیک باشه مسلمه الگوریتم درسته همون الگوریتم تعویض هستش، تو کتاب استالینگز فکر کنم از دستور تویض exchange استفاده کرده ، به هر حال هردو در صورت اتمیک بودن دستور مباله کلید و فضای مشترک انحصار متقابل رو تامین می کنه.
اما در مورد شرط پیشرفت، خوب این الگوریتم شرط پیشرفت رو نقض نمی کنه، یعنی شرط Progress رعایت میشه و تضمین می کنه حتما فرآیند بعد از مدت زمان مشخصی وارد ناحیه بحرانی خواهد شد، پس اگه swap اتمیک باشه یا نباشه این شرط رو داره. اما اگه اتمیک نباشه مسلما انحصار متقابل رعایت نمیشه و همزمان چند فرآیند می تونن تو ناحیه بحرانی وارد بشن(به هر حال وارد میشن). الگوریتم انتظار نا محدود هم نداره،همه بعد طی یک مدت نامشخصی اما حتمی وارد ناحیه میشن یعنی به هر حال هر کسی که lock رو false دید وارد ناحیه بحرانی میشه و مقدار lock رو هم true می کنه، در انتهای cs هم lock رو false می کنه تا دیگران انتظار نا محدود نکشن و بتونن وارد بشن.
پس گزینه ۱ درسته.
در کتاب دکتر حقیقت ذکر شده در الگوریتم swap شرط انتظار محدود رعایت نمیشه و اتفاقا ذکر شده شرط پیشرفت رعایت میشه
اما این الگوریتم و الگوریتم مشابه اون یعنی TSL شرط انتظار محدود رعایت نمیکنند چون هیچ کنترل کننده ای برای نوبت دهی به فرایند ها وجود نداره و امکان قحطی وجود داره و همونطور که خودتون هم گفتید فرایندها نوبت را رعایت نمیکنند که این میشه رعایت نشدن شرط انتظار محدود نه شرط پیشرفت.
اتفاقا وقتی فرایندها برای ورود یکدیگر به ناحیه بحرانی دخالت بیش از حد داشته باشند (به عنوان مثال الگوریتم اولین تلاش) شرط پیشرفت رعایت نمیشه.
من فکر میکنم با فرض اتمیک بودن دستور swap گزینه ۳ درسته.
من این بخش از کتاب حقیقت رو نخوندم، اما یعنی چی swap شرط انتظار محدود رو رعایت نمی کنه، اگه نکنه که یه راهکار مناسب برای انحصار متقابل نیست که !!!!!!
این روش یه روش کاملا کلاسیک و درسته و به علت سادگی در الگوریتم و زمان اجرای مطلوب پیاده سازی شده و یک فراخوان سیستمی اتمیک این رو پیاده سازی می کنه پس حتما در صورت اتمیک بودن دستور swap انحصار متقابل رعایت میشه، انتظار محدود هم نداره، به هر حال هر کی وارد cs میشه بعد یه مدتی بیرون میاد دیگه، وقتی انتظار نامحدود داریم که یه فرآیندی با هیچ فرضی نتونه دیگه وارد چرخه اجرا بشه و تا ابد منتظر صف cs می مونه.
واسه درک اینکه انتظار نا محدود چیه به الگوریتم های اولین تا ۴ مین تلاش یه نیگاه بنداز تو کتاب استالینگز
دقیقا در الگوریتم اولین تلاش انتظاز نامحدود رعایت نمیشه و مثال خوبی برای درک شرط انتظار نامحدود هست
البته انحصار متقابل با انتظار محدود فرق داره یعنی ممکنه انتظار محدود رعایت نشه اما انحصار متقابل رعایت بشه
انتظار محدود حتما این نیست که فرایند نتونه هیچ وقت وارد ناحیه بحرانی بشه. در واقع اگر الگوریتم طوری طراحی شده باشه که یه فرایند بتونه حق یه فرایند دیگه رو ضایع کنه در او صورت ممکنه که این ضایع شدن حق به مدت نا معلومی ادامه پیدا کنه.
از اونجا که این الگوریتم شرطی برای جلوگیری از ورود فرایندی که نوبتش نیست نداره ممکنه یه فرایند بعد از خروج دوباره بلا فاصله نیاز به ناحیه پیدا کنه و دوباره وارد شه. و این روند میتونه تکرار شه. پس در این الگوریتم انتظار محدود رعایت نشده!
تمام الگوریتم های یعنی دکر،پترسون، TSL، swap به علت انتظار مشغولی هیچ فرضی در مورد انتظار نا محدود نداره چون به روند اجرای فرآیند ها بستگی داره و اونهارو دائم مشغول تست ورود به ناحیه نگه میداره.
الگوریتم مشکلی نداره و شرط انتظار به انتظار مشغول و ترتیب اجرای فرآیند ها بستگی داره که همه الگوریتم هایی که شرط While دارن انتظار رو دارن.