موضوع مقاله: مسئله غذا خوردن فیلسوف‌ها | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مسئله غذا خوردن فیلسوف‌ها | مقدمه: در علوم کامپیوتر مسئله فیلسوفان پشت میز غذاخوری یک مسئله تمثیلی است مربوط به طراحی هم روندی الگوریتم‌ها، که معمولاً برای نشان دادن مشکلات و تکنیک‌های همگام سازی و روش حل آن‌ها استفاده می‌شود. | ## بخش 1: مسئله غذا خوردن فیلسوف‌ها | این مسئله در ابتدا در سال ۱۹۶۵ توسط آقای دیکسترا به عنوان یک تمرین امتحانی دانش آموزی طراحی شد و در رابطه با کامپیوترهایی ارائه شد که برای دسترسی به ابزارهای جانبی درایو نواری رقابت می‌کردند. با این حال، یک فیلسوف فقط زمانی می‌تواند ماکارونی بخورد که که هر دو چنگال سمت چپ و سمت راست را در اختیار داشته باشد. هر چنگال در هر لحظه فقط می‌تواند توسط یک فیلسوف استفاده شود و بنابراین، یک فیلسوف فقط زمانی می‌تواند از چنگال استفاده کند که چنگال توسط فیلسوف دیگر در حال استفاده نباشد. بعد از این که یک فیلسوف خوردنش تمام شد، باید هر دو چنگال را روی میز بگذارد تا بقیه از آن‌ها استفاده کنند. یک فیلسوف فقط می‌تواند چنگال سمت راست خود یا چنگال سمت چپ خود را، زمانی که موجود باشد، در اختیار بگیرد و نمی‌تواند قبل از در اختیار گرفتن هر دو چنگال خوردن را شروع کند. مقدار خوردن ارتباطی به حجم باقیمانده ماکارونی یا فضای معده افراد ندارد؛ به عبارتی، فرض بر این است که مقدار ماکارونی نامحدود است و مقدار خوردن نیز نامحدود است. مسئله این است که چگونه یک نظم رفتاری (الگوریتم همروندی) طراحی کنیم، به گونه‌ای که هیچ فیلسوفی گرسنه نماند؛ یعنی هر کدام بتواند به مدت نامتناهی و متناوباً بخورد و فکر کند. البته با فرض اینکه هیچ فیلسوفی نمی‌داند که چه زمانی سایر فیلسوفان قصد خوردن یا فکر کردن دارند. برای اینکه ببینیم راه حل این مسئله چندان آسان نیست، فرض بگیرید که هر فیلسوف باید مطابق با دستورالعمل زیر رفتار کند: تا زمانی که چنگال چپ موجود نشده، فکر کن. این راه حل وسوسه انگیز با شکست مواجه خواهد شد، زیرا به سیستم این امکان را می‌دهد که در وضعیت بن‌بست قرار بگیرد که در آن هیچ پیشرفتی امکان‌پذیر نیست. این وضعیت زمانی رخ می‌دهد که هر فیلسوف چنگال سمت چپ را برداشته است و منتظر است تا چنگال سمت راست موجود شود. با دستورالعمل‌های داده شده در بالا، احتمال ایجاد این وضعیت وجود دارد و زمانی که این وضعیت رخ دهد، هر فیلسوف باید منتظر فیلسوف دیگر در سمت راست بماند تا یک چنگال آزاد شود. اگر یک فیلسوف خاص به دلیل مشکل زمانبندی قادر نباشد تا هر دو چنگال را به دست آورد ممکن است قحطی منبع به‌صورت مستقل از بن‌بست نیز رخ دهد. برای مثال ممکن است یک قانون وجود داشته باشد که فیلسوف‌ها بعد از انتظار به مدت ۱۰ دقیقه برای موجود شدن چنگال دیگر، چنگالی را که در اختیار دارند، روی میز بگذارند و ۱۰ دقیقه دیگر صبر کنند و آنگاه مجدداً تلاش کنند. | ## بخش 2: مسئله غذا خوردن فیلسوف‌ها | این پروتکل باعث از بین رفتن احتمال بن‌بست می‌شود، زیرا سیستم همیشه می‌تواند به یک وضعیت متفاوت تغییر کند. اگر هر ۵ فیلسوف دقیقاً در یک لحظه وارد اتاق غذاخوری شوند و در یک لحظه هر کدام از آنها چنگال سمت چپ خود را بردارد، آنگاه فیلسوف‌ها ۱۰ دقیقه صبر می‌کنند و سپس تمام آنها همزمان چنگال‌های خود را روی میز می‌گذارند و سپس ۱۰ دقیقه دیگر صبر می‌کنند و مجدداً همه آنها چنگال‌ها را برمی‌دارند. فیلسوف‌های پشت میز غذاخوری در واقع یک سناریوی عمومی و انتزاعی کاربردی برای توصیف مشکلاتی از این دست را فراهم می‌کنند. با این حال، مشکلاتی که به وسیله مسئلهٔ فیلسوفان پشت میز غذاخوری شبیه‌سازی می‌شوند، در زمانی که چندین پروسه به داده‌هایی که در حال بروزرسانی هستند دسترسی پیدا می‌کنند، بسیار بیشتر رخ می‌دهد. سیستم‌های پیچیده نظیر کرنل‌های سیستم عامل از هزاران قفل و همگام سازی استفاده می‌کنند که نیازمند پیروی دقیق از روشها و پروتکل‌ها است تا مشکلاتی نظیر بن‌بست، قحطی، و خراب شدن داده به وجود نیاید. راه حل‌ها راه حل منبع سلسله مراتبی این راه حل، همان راه حلی است که در ابتدا توسط دیکسترا پیشنهاد شد. در این مورد اگر ۴ نفر از ۵ نفر به‌طور همزمان، چنگالی با عدد کوچکتر را بردارند، فقط چنگالی که بالاترین عدد را دارد روی میز باقی می‌ماند؛ بنابراین، چنگالی نصیب فیلسوف پنجم نخواهد شد. علاوه بر این، فقط یک فیلسوف به چنگالی که بالاترین عدد را دارد دسترسی دارد و بنابراین قادر خواهد بود تا با استفاده از دو چنگال غذا بخورد. اگر برنامه‌های کامپیوتر را که به تعداد زیادی از رکوردهای پایگاه داده دسترسی دارند ملزم کنیم تا قبل از دسترسی به یک رکورد جدید تمام رکوردهای دارای عدد بالاتر را رها کنند، آنگاه برنامه به خوبی کار نمی‌کند، و بنابراین این روش برای این هدف غیرعملی است. اگر فیلسوف ۱ دربرداشتن چنگال کند باشد، و اگر فیلسوف ۲ در فکر کردن و برداشتن چنگال‌ها سریع باشد، آنگاه فیلسوف ۱ هیچگاه قادر نخواهد بود تا هر دو چنگال را به‌دست آورد. راه‌حل منصفانه باید این تضمین را بدهد که هر فیلسوف بتواند تا ابد بخورد، حتی اگر سرعت آن در مقایسه با بقیه کندتر باشد. راه حل حکمیت روش دیگر این است که شرایطی ایجاد کنیم که یک فیلسوف در هر لحظه یا هر دو چنگال رو بردارد یا هیچ‌کدام را برندارد. تا زمانیکه فیلسوف‌ها هر دو چنگال مورد نیاز خود را بردارند، گارسون در هر لحظه فقط برای یک فیلسوف اجازه صادر می‌کند. این روش علاوه بر نیاز به یک ماهیت مرکزی جدید (گارسون)، می‌تواند منجر به کاهش موازی گرایی نیز شود: این کاهش، زمانی رخ می‌دهد که یک فیلسوف در حال خوردن باشد و یکی از فیلسوف‌های مجاور آن درخواست چنگال کند، در این حالت، تمام فیلسوفان دیگر باید منتظر بمانند تا این درخواست برآورده شود، حتی اگر چنگال برای آنها مهیا باشد. | ## بخش 3: مسئله غذا خوردن فیلسوف‌ها | مضافاً اینکه، این راه‌حل کاملاً توزیع شده‌است و نیاز به هیچ گونه مدیریت مرکزی بعد از شروع شدن ندارد. با این حال، در اینجا برخلاف قبل، فیلسوف‌ها می‌توانند با یکدیگر ارتباط برقرار کنند (به دلیل پیام‌های درخواست). برای هر جفت از فیلسوف‌ها که بر سر یک منبع رقابت می‌کنند، یک چنگال درست کنید و آن را به فیلسوفی بدهید که ID (n برای عامل P<sub>n) پایین‌تری دارد. برای تمام چنین چنگال‌هایی که فیلسوف مورد نظر ندارد باید یک پیغام درخواست بفرستد. زمانیکه یک فیلسوف که دارای یک چنگال است، یک پیغام درخواست دریافت می‌کند، اگر چنگالش تمیز باشد آن را نگه می‌دارد و اگر کثیف باشد آن را می‌دهد. اگر فیلسوف دیگری پیش از این در خواست یکی از این چنگال‌ها را کرده باشد، فیلسوفی که خوردن اش تمام شده‌است، چنگال را تمیز می‌کند و به وی می‌دهد. از این رو، این راه حل درجه بالایی از همه روندی را فراهم می‌کند و یک مسئله که به اندازه دلخواه بزرگ باشد، را حل می‌کند. برچسب تمیزی یا کثیفی به عنوان شیوه ای برای دادن ارجحیت به گرسنه‌ترین پروسه عمل می‌کند و برای پروسه‌هایی که تازه خوردن شان تمام شده‌است، خوب نیست. می‌توان هر کدام از این روش‌ها را با روشی مقایسه کرد که در آن، به فیلسوف‌ها اجازه داده نمی‌شود تا پشت سر هم دوبار بخورند و در عین حال در این بین به دیگران اجازه استفاده از چنگال‌ها را ندهند. آنها در آنالیز خود، یک سیستم سطوح ارجحیت را از توزیع چنگال‌ها و وضعیت تمیزی یا کثیفی آنها طراحی کردند. آن‌ها نشان دادند که این سیستم ممکن است یک گراف بدون حلقه جهت دار را نشان دهد و اگر چنین باشد، عملیات موجود در پروتکل آن‌ها نمی‌تواند گراف را تبدیل به یک گراف حلقوی کند. با این حال، اگر این سیستم در یک وضعیت کاملاً قرینه شروع شود، نظیر آنچه که در آن فیلسوف‌ها چنگال‌های سمت چپ خود را نگه داشته بودند، آنگاه گراف در شروع، حلقوی است و راه حل آنها مانع از بن‌بست نمی‌شود. | ## جمع‌بندی | شروع کردن سیستم به‌گونه‌ای که فیلسوف‌هایی که دارای شماره شناسایی پایین‌تری هستند، صاحب چنگال‌های کثیف باشند، موجب می‌شود تا گراف در ابتدا غیر حلقوی باشد.