انجمنصفحه اولجستجوی انجمن

[هاتف]

سلام
مسئله معروف تولید کننده_مصرف کننده که بارها توی کنکور اومده و در کتاب تنن بام ذکر شده، این مسئله در صفحه ۱۹۹ کتاب دکتر حقیقت هم اومده که یک روش اشتباه رو نشون میده! یاادآوری می کنم مشکل اینجا بود که با اومدن یک وقفه در زمان بد در مصرف کننده، می خوابید و تولید کننده کارش رو ادامه میداد تا بالاخره بافر پر میشد، در نهایت او هم می خوابید و کسی نبود که بیدارش کنه:

سوال

اگر در کد تولید کننده، شرط گذاشتن برای بیدار کردن مصرف کننده رو حذف کنیم، و در هر بار اجرای تولید کننده، مصرف کننده رو بیدار کنیم (یعنی در خط آخر if را برداریم و فقط wakeup بمونه) آنگاه این برنامه:

۱- غلطه چون پر هزینه است.
۲- غلطه چون قحطی داره.
۳-درسته ولی پر هزینه است.
۴-غلطه چون هنوز امکان بن بست هست

[narges_r]

در این الگوریتم کلا شرط انتظار محدود رعایت نمیشه و امکان قحطی یابن بست وجود داره و چه شرط if وجود داشته باشه و چه شرط if وجود نداشته باشه امکان قحطی وبن بست هست اما من فکر میکنم شرط if گذاشته شده تا از هدر رفتن بیخود سیگنال wake up جلو گیری کرد
تصور کنید این شرط نباشه هربار سیگنال فرستاده بشه درحالی که بافر نصفش پرباشه و اصلا احتیاجی نیست که سیگنال wake up فرستاده بشه این سیگنالها به هدر میرن چون فقط وقتی احتیاج به این سیگنال هست که مصرف کننده خواب باشه و وقتی مصرف کننده به خواب میره که بافر پر بشه

[pos]

گزینه چهار

[هاتف]

(۲۳ آذر ۱۳۹۰ ۰۹:۵۲ ب.ظ)narges_r نوشته شده توسط:  در این الگوریتم کلا شرط انتظار محدود رعایت نمیشه و امکان قحطی یابن بست وجود داره و چه شرط if وجود داشته باشه و چه شرط if وجود نداشته باشه امکان قحطی وبن بست هست اما من فکر میکنم شرط if گذاشته شده تا از هدر رفتن بیخود سیگنال wake up جلو گیری کرد

خوب قحطی بن بست نیست، اگر فقط قحطی داشته باشه می تونیم بگیم بهرحال برنامه درست کار می کنه.

برای ما هدر رفتن wakeup مهم نیست، می خواهیم از بن بست رهایی پیدا کنیم، یعنی کاری کنیم که مصرف کننده نخوابه که نتونه بعدا تولید کننده رو بیدار کنه، این کد جدید میگه هر باز چیزی تولید شد سریع مصرف کننده رو بیدار کن، و مدعی است که با اینکار مصرف کننده به خواب ابدی نمیره.

[narges_r]

اقای هاتف مسلمادر اینکه قحطی با بن بست فرق داره که شکی نیست‌! چون من گفتم شرط انتظار محدودو رعایت نمیکنه قحطی و بن بست باهم ذکر کردم.
اگر به پروسه ای که در اثر اون بن بسست اتفاق میفته دقت کنیم میبینیم که اتفاق بن بست بخاطر اون if یا غیره نیست بلکه بخاطر وقفه ساعت و دسترسی به بافر که یک ناحیه مشترک هست اتفاق میفته
پس اگر این شرطو حذف کنیم باز هم همون دلایل بن بست که وقفه ساعت و دسترسی به بافر مشترک هست وجود داره پس مشکل بن بست از بین نمیره و فقط تعدادی از سیگنالهای wake up هدر میره

[Mohammad-A]

ببخشید درباره این سوال من به یه موضوع دیگه (خارج از گزینه‌ها) رسیدم شاید غلط باشه.

اساس ایجاد سمافورها برای جلوگیری از به هدر رفتن سیگنال‌هایی مانند این بود همینطور این مسأله شدیداً به اندازه بافر وابسته هست.

از این موضوع اگر بگذریم٬ فرض کنید که تولیدکننده یک آیتم رو تولید میکنه و متغیر Count یکی بیشتر می‌شه. به نظرم یه مقدار راجع به موضوع زیر میتونه جای بحث باشه که:
در شرایطی که هر دو از فرایند بیدار هستند٬ پردازنده به فرایند مصرف‌کننده می‌رسه. مصرف‌کننده که (در این فرض) بعد یک بار اجرای کامل تولیدکننده اجرا شده٬ متغیر Count رو برابر ۱ می‌بینه٬ اما در همین حین با وقوع یک وقفه٬ دوباره پردازنده دست تولیدکننده می‌رسه و اینباره تولیدکننده مقدار Count رو به ۲ می‌رسونه در حالیکه در همین لحظه مصرف‌کننده مقدار ۱ رو در دست داره و مقدار Count با اجرای کامل فرایند مصرف‌کننده می‌تونه به صفر برسه. در اینصورت مشکل جدیدی به نظر شما به وجود نمیاد؟ یا من در حال اشتباه هستم؟

[هاتف]

(۲۳ آذر ۱۳۹۰ ۱۰:۳۳ ب.ظ)mam نوشته شده توسط:  در شرایطی که هر دو از فرایند بیدار هستند٬ پردازنده به فرایند مصرف‌کننده می‌رسه. مصرف‌کننده که (در این فرض) بعد یک بار اجرای کامل تولیدکننده اجرا شده٬ متغیر Count رو برابر ۱ می‌بینه٬ اما در همین حین با وقوع یک وقفه٬ دوباره پردازنده دست تولیدکننده می‌رسه و اینباره تولیدکننده مقدار Count رو به ۲ می‌رسونه

در این صورت که شما شرح دادید اگر برنامه رو trace کنید می بینید که یکی از تولیدات از بین میره، ولی بن بست رخ نمیده.
یعنی
- مصرف کننده پس از مصرف خانه اول مقدار ۱ را داخل رجیستر خودش میریزه
- تولید کننده اجرا میشه و یکی تولید می کنه و در خانه شماره ۱ میریزه و count رو ۲ می کنه
- مصرف کننده ادامه میده: مقدار count رو ۰ می کنه، یک آشغال مصرف می کنه
- تولید کننده کار رو ادامه میده و آیتم های بعدی رو پر می کنه

در اینجا یک محصول از بین رفت و یک آشغال مصرف شد!

می تونید یک مثال بزنید که با وجود اینکه هر بار تولید کننده، مصرف کننده رو بیدار می کنه، باز هم خطر مشکل قبلی (خواب ابدی هر دو) وجود داره؟

در این trace بله منجر به بن بست نشد اما عملکرد منطقی نداشت!

---

(۲۳ آذر ۱۳۹۰ ۱۰:۳۳ ب.ظ)mam نوشته شده توسط:  اساس ایجاد سمافورها برای جلوگیری از به هدر رفتن سیگنال‌هایی مانند این بود

البته این هدف نبود! اگر سیگنال به هدر بره و مشکلی پیش نیاد ما هم مشکلی با این اسراف نداریم!
اینکه سمافور اجازه به هدر رفتن سیگنال رو نمیده یک وسیله ای است که ما رو به هدف بالاتر یعنی همگام سازی رسوند

[Mohammad-A]

خب ببینید در این صورت٬ فرض کنید که مصرف‌کننده یکی رو مصرف کرده و تولیدکننده هم پیش از وقفه‌ی مورد بحث٬ یک آیتم تولید کرده. بنابراین مقدار count برابر صفر شده.

در این صورت٬ اگر تولیدکننده یک مورد جدید رو بخواد تولید کنه٬ count طبعاً برابر یک میشه درحالیکه ما دو مورد در بافر داریم و به نظرم این مورد میتونه عدم بهینگی این کد رو نشون بده.

---

از طرف دیگه٬ فرض کنید که پیش از اجرای فرایند تولیدکننده٬ فرایند مصرف‌کننده مقدار count رو برابر صفر می‌بینه اما در همین حین یک وقفه رخ میده و پردازنده بر اساس یک الگوریتم زمانبندی منحصر٬ به تولیدکننده میرسه تا مقدار بافر پر بشه.
مشخصاً در اینجا تعدادی سیگنال بیداری به هدر رفته. تولیدکننده مقدار count رو برابر N میبینه و به خواب میره.
در همین حین٬ همانطور که در بالا گفته شد٬ مصرف‌کننده که قبلاً مقدار count رو برابر صفر دیده بود هم به خواب میره.

بنابراین این شرط بن‌بست نیست؟

[pos]

فرض کنین N=99 باشه و مصرف کننده در خط یکی مانده به آخر. خوب مصرف کننده در شرط مقدار count را می خواند ولی قبل از اینکه آن را چک کند و یا دستور wakeup را اجرا کند cpu به تولید کننده داده می شود. تولید کننده یک مقدار تولید می کنه و درج می کنه(حالا N میشه ۱۰۰). حالا cpu به مصرف کننده داده میشه و اون هم wakeup را صدا میزنه و چون تولید کننده بیدار هست این هم هدر میره. مجددا cpu را میدیم به تولید کننده. تولید کننده یک ایتم جدید تولید می کنه. سپس count را که برابر ۱۰۰ هست می خواند ولی قبل اینکه بخواد sleep را صدا بزنه cpu ازش گرفته میشه. حالا مصرف کننده میاد یک آیتم مصرف می کنه میشه ۹۹ تا. دوباره یکی مصرف می کنه میشه ۹۸ تا. حالا cpu را میدیم به تولید کننده. تولید کننده با اجرای sleep به خواب میره و مصرف کننده مجددا اجرا میشه. ۹۸ تا محصول باقیمانده را مصرف می کنه و بعد sleep میکنه. بن بست رخ میده.

[mamat]

اینجا گزینه ۴ صحیحه

دلیل:

اگر if حذف بشه به ظاهر مشکل بن بست رفع شده و مسئله بن بستی که تو کتاب دکتر حقیقت طرح شده رفع میشه اما باز اگه یک حالت رو در نظر بگیریم که امکانش کمه اما میشه در نظر گرفت (حالته دیگه خدا رو چه دیدی تو سیستم عامل همه چی ممکنه) اینه که تولید کننده با سرعت خیلی زیاد یعنی در یک Time Slice بتونه کل بافر رو پر کنه و به خواب بره اونوقت دیگه نمیشه مصرف کننده رو از وجود پر بودن بافر برای مصرق خبردار کرد.

[narges_r]

البته یک نکته ای هم اینجا هست که در اینجا بن بست وقتی ایجاد میشه که فقط دریک فرصت سیگنال فرستاده میشه اگر ازش استفاده بشه که بن بست رخ نمیده اما اگر ازش استفاده نشه به هر دلیلی بن بست رخ میده حالا اگر هربار این سیگنال تولید بشه امکان اینکه بن بست تولید بشه از بین میره
البته برای اینکه کامل بن بستو از بین ببریم باید همه if های قبل از wake up هارو برداریم نه فقط همین یه دونه if رو

[هاتف]

(۲۳ آذر ۱۳۹۰ ۱۱:۲۸ ب.ظ)mamat نوشته شده توسط:  اینجا گزینه ۴ صحیحه
دلیل:

اگر if حذف بشه به ظاهر مشکل بن بست رفع شده و مسئله بن بستی که تو کتاب دکتر حقیقت طرح شده رفع میشه اما باز اگه یک حالت رو در نظر بگیریم که امکانش کمه اما میشه در نظر گرفت (حالته دیگه خدا رو چه دیدی تو سیستم عامل همه چی ممکنه) اینه که تولید کننده با سرعت خیلی زیاد یعنی در یک Time Slice بتونه کل بافر رو پر کنه و به خواب بره اونوقت دیگه نمیشه مصرف کننده رو از وجود پر بودن بافر برای مصرق خبردار کرد.

بله، با این تغییر کد که در بالا ذکر شده بود، امکان بروز بن بست پائین میاد، هرچند هزینه بر هست، اما خوب بازم ممکنه بن بست رخ بده!
یعنی در حالتی که سرعت تولید کننده خیلی بالا باشه، وقفه در ابتدای کد مصرف کننده بیاد، چون مسائل باید general باشن، پس این راه حل هم به بن بست می خوره و غلطه
این اصلی ترین دلیلشه اما بهر حال ازین تکه کد شاید بشه بیشتر از اینها ایراد گرفت.

اگر ما بدونیم کجای برنامه وقفه بدیم تا Trace ما مشکل رو پیدا کنه، استاد این بحث هستیم! یعنی این سخت ترین قسمت کاره، می خواستم کمی این کد رو عمیق‌تر تحلیل کنیم، البته فکر کردم شاید سوال بشه چرا در الگوریتم یکجا شرط if با N-1 مقایسه شده یکجا با یک، که حتما روشن بوده برای همه

راستش سطح مانشتی‌ها بالاست، باید سوالات رو سخت‌تر طرح کرد! این کار منو مشکل کرده

[Mohammad-A]

پس میشه به این نتیجه رسید که با N-1 بار تولید (بعد از وقفه‌ای بحث‌برانگیزی که مصرف‌کننده داشته)٬ مسئله به بن‌بست می‌ره. یعنی شرط لازم برای اینکه به بن‌بست بره٬ وقوع وقفه در اون ناحیه‌ی بحث‌برانگیز هست و شرط کافی هم اجرای N بار تولیدکننده بعد از اون وقفه هست. درسته؟