مسئله شام فلاسفه

در دو نوشتار قبل تا حدی با مفاهیم پروسه و ریسه (thread) آشنا شدیم. همچنین با دو مفهوم parallelism و concurrency آشنا شدیم و فهمیدیم که سیستم‌عامل‌های امروزی برای استفاده بهینه‌تر از منابع کامپیوتر تلاش می‌کنند پروسه‌ها و ریسه‌ها را تا حد امکان همزمان پیش ببرند. این هم‌زمانی در نهایت منجر به بروز مشکلاتی می‌شود. این مشکلات ناشی از منابع مشترک بین پروسه‌ها هستند. برای مثال دو پروسه سعی می‌کنند به‌طور همز‌مان از منبع A، استفاده کنند. بدیهی است که طراحان سیستم‌عامل باید برای جلوگیری از مشکل چنین موقعیت‌هایی را در نظر داشته باشد. یکی از مسائل سنتی و کلاسیکی که در این زمینه مطرح می‌شود مسئله شام فلاسفه است که در این مطلب به آن می‌پردازیم.

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

آیا می‌توانی برنامه‌ای برای هر فیلسوف بنویسی، به طوری که هرگز هیچ‌کدام از فلاسفه در یک موقعیت گیر نکنند؟

این مسئله اولین بار توسط ادگار دیکسترا در سال ۱۹۶۵ مطرح شد. البته صورت اولیه مسئله با چیزی که در بالا عنوان شد تفاوت‌هایی دارد اما کلیت مسئله همین است.

حل مسئله

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

#define N 5                                           / * number of philosophers * /
void philosopher(int i)
      {
      while (TRUE) {
            think( );
            takeـــfork(i);
            takeـــfork((i+1) % N);
            eat( );
            putـــfork(i);
            putـــfork((i+1) % N);
            }
      }

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

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

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