مسئله غذا خوردن فیلسوف‌ها

در علوم کامپیوتر مسئله فیلسوفان پشت میز غذاخوری یک مسئله تمثیلی است مربوط به طراحی هم روندی الگوریتم‌ها، که معمولاً برای نشان دادن مشکلات و تکنیک‌های همگام سازی و روش حل آن‌ها استفاده می‌شود. این مسئله در ابتدا در سال ۱۹۶۵ توسط آقای دیکسترا به عنوان یک تمرین امتحانی دانش آموزی طراحی شد و در رابطه با کامپیوترهایی ارائه شد که برای دسترسی به ابزارهای جانبی درایو نواری رقابت می‌کردند.

بیان مسئله

Illustration of the dining philosophers problem.

پنج فیلسوف ساکت در اطراف یک میز قرار می‌گیرند. روی میز کاسه‌های ماکارونی وجود دارد. چنگال‌هایی مابین هر جفت از فیلسوف‌های کنار هم قرار داده شده‌است. هر فیلسوف باید به صورت متناوب فکر کند و بخورد. با این حال، یک فیلسوف فقط زمانی می‌تواند ماکارونی بخورد که که هر دو چنگال سمت چپ و سمت راست را در اختیار داشته باشد. هر چنگال در هر لحظه فقط می‌تواند توسط یک فیلسوف استفاده شود و بنابراین، یک فیلسوف فقط زمانی می‌تواند از چنگال استفاده کند که چنگال توسط فیلسوف دیگر در حال استفاده نباشد. بعد از این که یک فیلسوف خوردنش تمام شد، باید هر دو چنگال را روی میز بگذارد تا بقیه از آن‌ها استفاده کنند. یک فیلسوف فقط می‌تواند چنگال سمت راست خود یا چنگال سمت چپ خود را، زمانی که موجود باشد، در اختیار بگیرد و نمی‌تواند قبل از در اختیار گرفتن هر دو چنگال خوردن را شروع کند. مقدار خوردن ارتباطی به حجم باقیمانده ماکارونی یا فضای معده افراد ندارد؛ به عبارتی، فرض بر این است که مقدار ماکارونی نامحدود است و مقدار خوردن نیز نامحدود است. مسئله این است که چگونه یک نظم رفتاری (الگوریتم همروندی) طراحی کنیم، به گونه‌ای که هیچ فیلسوفی گرسنه نماند؛ یعنی هر کدام بتواند به مدت نامتناهی و متناوباً بخورد و فکر کند. البته با فرض اینکه هیچ فیلسوفی نمی‌داند که چه زمانی سایر فیلسوفان قصد خوردن یا فکر کردن دارند.

مشکلات

این مسئله با این هدف طراحی شد که چالش‌های پیشگیری از بن‌بست را نشان دهد. بن‌بست یک وضعیتی از سیستم است که در آن هیچ پیشرفتی امکان‌پذیر نیست. برای اینکه ببینیم راه حل این مسئله چندان آسان نیست، فرض بگیرید که هر فیلسوف باید مطابق با دستورالعمل زیر رفتار کند:

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

تا زمانی که چنگال راست موجود نشده‌است، فکر کن. و زمانی که موجود شد آن را بردار.

زمانی که هر دو چنگال را به دست آوردی، مدت زمان مشخصی بخور.

سپس چنگال راست را روی میز بگذار.

و سپس چنگال چپ را روی میز بگذار.

دوباره از ابتدا شروع کن.

این راه حل وسوسه انگیز با شکست مواجه خواهد شد، زیرا به سیستم این امکان را می‌دهد که در وضعیت بن‌بست قرار بگیرد که در آن هیچ پیشرفتی امکان‌پذیر نیست. این وضعیت زمانی رخ می‌دهد که هر فیلسوف چنگال سمت چپ را برداشته است و منتظر است تا چنگال سمت راست موجود شود. با دستورالعمل‌های داده شده در بالا، احتمال ایجاد این وضعیت وجود دارد و زمانی که این وضعیت رخ دهد، هر فیلسوف باید منتظر فیلسوف دیگر در سمت راست بماند تا یک چنگال آزاد شود.

اگر یک فیلسوف خاص به دلیل مشکل زمانبندی قادر نباشد تا هر دو چنگال را به دست آورد ممکن است قحطی منبع به‌صورت مستقل از بن‌بست نیز رخ دهد. برای مثال ممکن است یک قانون وجود داشته باشد که فیلسوف‌ها بعد از انتظار به مدت ۱۰ دقیقه برای موجود شدن چنگال دیگر، چنگالی را که در اختیار دارند، روی میز بگذارند و ۱۰ دقیقه دیگر صبر کنند و آنگاه مجدداً تلاش کنند. این پروتکل باعث از بین رفتن احتمال بن‌بست می‌شود، زیرا سیستم همیشه می‌تواند به یک وضعیت متفاوت تغییر کند. اما هنوز مشکل قفل زنده وجود دارد. اگر هر ۵ فیلسوف دقیقاً در یک لحظه وارد اتاق غذاخوری شوند و در یک لحظه هر کدام از آنها چنگال سمت چپ خود را بردارد، آنگاه فیلسوف‌ها ۱۰ دقیقه صبر می‌کنند و سپس تمام آنها همزمان چنگال‌های خود را روی میز می‌گذارند و سپس ۱۰ دقیقه دیگر صبر می‌کنند و مجدداً همه آنها چنگال‌ها را برمی‌دارند.

انحصار متقابل ایده اساسی مسئله است. فیلسوف‌های پشت میز غذاخوری در واقع یک سناریوی عمومی و انتزاعی کاربردی برای توصیف مشکلاتی از این دست را فراهم می‌کنند. مشکلاتی که این فیلسوف‌ها با آن مواجه می‌شوند، مشابه مشکلاتی است که در برنامه‌نویسی واقعی کامپیوتر (زمانی که چندین برنامه نیاز به دسترسی انحصاری به منابع مشترک دارند) رخ می‌دهد. این مشکلات در برنامه‌نویسی همروند مورد بحث قرار می‌گیرند. این مسئله در ابتدا مربوط به وسایل خارجی نظیر درایوهای نواری بود. با این حال، مشکلاتی که به وسیله مسئلهٔ فیلسوفان پشت میز غذاخوری شبیه‌سازی می‌شوند، در زمانی که چندین پروسه به داده‌هایی که در حال بروزرسانی هستند دسترسی پیدا می‌کنند، بسیار بیشتر رخ می‌دهد. سیستم‌های پیچیده نظیر کرنل‌های سیستم عامل از هزاران قفل و همگام سازی استفاده می‌کنند که نیازمند پیروی دقیق از روشها و پروتکل‌ها است تا مشکلاتی نظیر بن‌بست، قحطی، و خراب شدن داده به وجود نیاید.

راه حل‌ها

راه حل منبع سلسله مراتبی

این راه حل، همان راه حلی است که در ابتدا توسط دیکسترا پیشنهاد شد. در این راه حل یک ترتیب سهمی به منابع (در این مثال چنگال‌ها) اختصاص داده می‌شود و این قانون را اعمال می‌کند که تمام منابع باید به ترتیب درخواست شوند و اینکه هیچ دو منبع نامرتبط از نظر ترتیب، هیچ وقت توسط یک واحد کار منفرد، به‌طور همزمان استفاده نشوند. در اینجا منابع (چنگال‌ها) از ۱ تا ۵ شماره گذاری می‌شوند و هر واحد کار (فیلسوف) همیشه از بین دو چنگالی که قرار است استفاده کند، اول چنگال با عدد کوچکتر و سپس چنگال با عدد بزرگتر را برمی‌دارد. ترتیب قرار دادن چنگال‌ها روی میز توسط هر فیلسوف اهمیتی ندارد. در این مورد اگر ۴ نفر از ۵ نفر به‌طور همزمان، چنگالی با عدد کوچکتر را بردارند، فقط چنگالی که بالاترین عدد را دارد روی میز باقی می‌ماند؛ بنابراین، چنگالی نصیب فیلسوف پنجم نخواهد شد. علاوه بر این، فقط یک فیلسوف به چنگالی که بالاترین عدد را دارد دسترسی دارد و بنابراین قادر خواهد بود تا با استفاده از دو چنگال غذا بخورد.

اگرچه راه حل منبع سلسله مراتبی، مانع از بن‌بست می‌شود اما این راه حل همیشه عملی نیست، مثلاً زمانی که لیست منابع مورد نیاز از قبل کاملاً مشخص نیست. برای مثال، اگر یک واحد کار، منابع ۳ و ۵ را در اختیار بگیرد و سپس مشخص شود که نیاز به منبع ۲ دارد، آنگاه باید قبل از به دست آوردن منبع ۲، منبع ۵ و سپس۳ را آزاد کند و سپس باید منابع ۳ و ۵ را مجدداً به همان ترتیب به دست آورد. اگر برنامه‌های کامپیوتر را که به تعداد زیادی از رکوردهای پایگاه داده دسترسی دارند ملزم کنیم تا قبل از دسترسی به یک رکورد جدید تمام رکوردهای دارای عدد بالاتر را رها کنند، آنگاه برنامه به خوبی کار نمی‌کند، و بنابراین این روش برای این هدف غیرعملی است.

راه حل منبع سلسله مراتبی، منصفانه نیست. اگر فیلسوف ۱ دربرداشتن چنگال کند باشد، و اگر فیلسوف ۲ در فکر کردن و برداشتن چنگال‌ها سریع باشد، آنگاه فیلسوف ۱ هیچگاه قادر نخواهد بود تا هر دو چنگال را به‌دست آورد. راه‌حل منصفانه باید این تضمین را بدهد که هر فیلسوف بتواند تا ابد بخورد، حتی اگر سرعت آن در مقایسه با بقیه کندتر باشد.

راه حل حکمیت

روش دیگر این است که شرایطی ایجاد کنیم که یک فیلسوف در هر لحظه یا هر دو چنگال رو بردارد یا هیچ‌کدام را برندارد. برای این روش نیاز به یک حاکم مثلاً یک گارسون داریم. یک فیلسوف برای برداشتن چنگال‌ها باید از گارسون اجازه بگیرد. تا زمانیکه فیلسوف‌ها هر دو چنگال مورد نیاز خود را بردارند، گارسون در هر لحظه فقط برای یک فیلسوف اجازه صادر می‌کند. فیلسوفان همیشه اجازه دارند تا چنگال را روی میز بگذارند. گارسون را می‌توان با استفاده از یک mutex پیاده‌سازی کرد. این روش علاوه بر نیاز به یک ماهیت مرکزی جدید (گارسون)، می‌تواند منجر به کاهش موازی گرایی نیز شود: این کاهش، زمانی رخ می‌دهد که یک فیلسوف در حال خوردن باشد و یکی از فیلسوف‌های مجاور آن درخواست چنگال کند، در این حالت، تمام فیلسوفان دیگر باید منتظر بمانند تا این درخواست برآورده شود، حتی اگر چنگال برای آنها مهیا باشد.

راه حل Chaney و Misra

در سال ۱۹۸۴ Chandy و Misra یک راه حل متفاوت را برای مسئله فیلسوفان پشت میز غذاخوری پیشنهاد کردند. در این راه حل، برخلاف راه‌حل دیکسترا، به عوامل دلخواه (P₁, … , P_n) اجازه داده می‌شود تا برای تعداد دلخواهی از منابع رقابت کنند. مضافاً اینکه، این راه‌حل کاملاً توزیع شده‌است و نیاز به هیچ گونه مدیریت مرکزی بعد از شروع شدن ندارد. با این حال، در اینجا برخلاف قبل، فیلسوف‌ها می‌توانند با یکدیگر ارتباط برقرار کنند (به دلیل پیام‌های درخواست).

1. برای هر جفت از فیلسوف‌ها که بر سر یک منبع رقابت می‌کنند، یک چنگال درست کنید و آن را به فیلسوفی بدهید که ID (n برای عامل P_{n) پایین‌تری دارد. هر چنگال می‌تواند تمیز یا کثیف باشد. در ابتدا تمام چنگال‌ها کثیف هستند.}
2. زمانیکه یک فیلسوف می‌خواهد از مجموعه ای از منابع استفاده کند (یعنی بخورد)، باید چنگال‌ها را از رقیبان همسایه خود بگیرد. برای تمام چنین چنگال‌هایی که فیلسوف مورد نظر ندارد باید یک پیغام درخواست بفرستد.
3. زمانیکه یک فیلسوف که دارای یک چنگال است، یک پیغام درخواست دریافت می‌کند، اگر چنگالش تمیز باشد آن را نگه می‌دارد و اگر کثیف باشد آن را می‌دهد. اگر این فیلسوف بخواهد چنگال را بدهد، باید ابتدا آن را تمیز کند.
4. بعد از این که خوردن یک فیلسوف تمام شد، تمام چنگال‌های آنها کثیف می‌شود. اگر فیلسوف دیگری پیش از این در خواست یکی از این چنگال‌ها را کرده باشد، فیلسوفی که خوردن اش تمام شده‌است، چنگال را تمیز می‌کند و به وی می‌دهد.

از این رو، این راه حل درجه بالایی از همه روندی را فراهم می‌کند و یک مسئله که به اندازه دلخواه بزرگ باشد، را حل می‌کند.

همچنین مشکل قحطی را نیز برطرف می‌کند. برچسب تمیزی یا کثیفی به عنوان شیوه ای برای دادن ارجحیت به گرسنه‌ترین پروسه عمل می‌کند و برای پروسه‌هایی که تازه خوردن شان تمام شده‌است، خوب نیست. می‌توان هر کدام از این روش‌ها را با روشی مقایسه کرد که در آن، به فیلسوف‌ها اجازه داده نمی‌شود تا پشت سر هم دوبار بخورند و در عین حال در این بین به دیگران اجازه استفاده از چنگال‌ها را ندهند. راه‌حل Chandy و Misra در مقایسه با آن قابل انعطاف تر است، اما دارای یک عنصر است که به آن سو تمایل دارد.

آنها در آنالیز خود، یک سیستم سطوح ارجحیت را از توزیع چنگال‌ها و وضعیت تمیزی یا کثیفی آنها طراحی کردند. آن‌ها نشان دادند که این سیستم ممکن است یک گراف بدون حلقه جهت دار را نشان دهد و اگر چنین باشد، عملیات موجود در پروتکل آن‌ها نمی‌تواند گراف را تبدیل به یک گراف حلقوی کند. این وضعیت قطعاً موجب بن‌بست نخواهد شد. با این حال، اگر این سیستم در یک وضعیت کاملاً قرینه شروع شود، نظیر آنچه که در آن فیلسوف‌ها چنگال‌های سمت چپ خود را نگه داشته بودند، آنگاه گراف در شروع، حلقوی است و راه حل آنها مانع از بن‌بست نمی‌شود. شروع کردن سیستم به‌گونه‌ای که فیلسوف‌هایی که دارای شماره شناسایی پایین‌تری هستند، صاحب چنگال‌های کثیف باشند، موجب می‌شود تا گراف در ابتدا غیر حلقوی باشد.

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Dining philosophers problem». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۲ مارس ۲۰۲۱.