الگوریتم غذا خوردن

مسئله شام خوردن فیلسوف‌ها (به انگلیسی: Dining philosophers problem) یک مسئله کلاسیک در مباحث ارتباط بین فرایندی است که اغلب در طراحی الگوریتم‌های همروند، برای نشان دادن مشکلات و مسائل همگام‌سازی و تکنیک‌های حل آن‌ها مطرح می‌شود.

شرح مسئله[ویرایش]

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

مشکلات و راه حل‌ها[ویرایش]

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

• تا وقتی که چنگال سمت چپ در دسترس قرار نگرفته‌است، فکر کند. وقتی که چنگال سمت چپ در دسترس قرار گرفت، آن را بردارد.
• تا وقتی که چنگال سمت راست در دسترس قرار نگرفته‌است، فکر کند. وقتی که چنگال سمت راست در دسترس قرار گرفت، آن را بردارد.
• وقتی که هر دو چنگال برداشته شد، برای یک مدت زمان ثابتی غذا بخورد.
• سپس چنگال سمت راست را بر روی میز قرار دهد.
• سپس چنگال سمت چپ را بر روی میز قرار دهد.
• این مراحل را از ابتدا تکرار کند.

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

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

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

برای نشان دادن این راه حل، فرض کنید که فیلسوف‌ها به شکل ساعت‌گرد از A تا E نام‌گذاری شده‌اند. اگر A و C در حال غذا خوردن باشند، چهار چنگال در حال استفاده است. فیلسوف B که در میان A و C قرار دارد، چنگالی برای غذا خوردن ندارد. D و E هم هر دو یک چنگال دارند که نمی‌توانند با آن غذا بخورند. فرض کنید که D بخواهد غذا بخورد. وقتی که او می‌خواهد پنجمین چنگال را بردارد، احتمالاً بن‌بست رخ خواهد داد. اما اگر ابتدا از پیشخدمت سؤال کند و پیشخدمت هم به او بگوید که صبر کند، می‌توانیم مطمئن باشیم که دفعه بعد که یک فیلسوف دو چنگالش را روی میز گذاشت، حداقل یکی دیگر از فیلسوف‌ها می‌تواند دو تا از سه چنگال را برداشته و شروع به غذا خوردن کند.

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

منابع[ویرایش]

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

منبع: fa.wikipedia.org