مسئله تولیدکننده-مصرف‌کننده

در علوم کامپیوتر تولیدکننده-مصرف‌کننده (به انگلیسی: Producer–consumer problem) یا همان مسئله بافر محدود (به انگلیسی: bounded-buffer problem) یک مثال کلاسیک از مشکل همگام سازی چند پروسه‌ای است. اولین نسخه آن توسط دیکسترا در سال ۱۹۶۵ بصورت منتشر نشده و دست‌نویس پیشنهاد شد که در آن بافر نامحدود بود و بعدها در سال ۱۹۷۲ با یک بافر محدود منتشر شد. در اولین نسخه مسئله، دو پروسه سیکلی وجود داشت با نام‌های تولیدکننده و مصرف‌کننده که یک بافر مشترک با اندازه ثابت را به شکل یک صف به اشتراک می‌گذارند. تولیدکننده به‌طور مکرر داده تولید می‌کند و آن را در بافر می‌ریزد. مصرف‌کننده به‌طور مکرراً داده را از بافر می‌خواند و پس از خواندن آن را حذف می‌کند و از این داده به شیوه ای استفاده می‌کند. در اولین نسخه مسئله که دارای یک بافر نامحدود بود، مسئله این بود که چگونه یک کد تولیدکننده و مصرف‌کننده طراحی کنیم به گونه ای که در تبادل داده بین آن‌ها، هیچ داده‌ای از بین نرود یا تکراری نشود و نیز داده توسط مصرف‌کننده به ترتیبی خوانده شود که توسط تولیدکننده نوشته شده‌است، و هر دو پروسه حداکثر پیشرفت ممکن را داشته باشند. در فرمول بندی بعدی مسئله، آقای دیکسترا تولیدکننده‌ها و مصرف‌کننده‌های متعددی را پیشنهاد کرد که مجموعه متناهی از بافرها را به اشتراک می‌گذارند. این کار باعث ایجاد مشکلی دیگر شد و آن این بود که چگونه تولیدکننده‌ها را از نوشتن در بافرهایی که تماماً پر هستند بازداریم و چگونه مصرف‌کننده‌ها را از خواندن بافر، در زمانیکه تمام بافرها خالی هستند بازداریم.
اولین موردی که باید در نظر بگیریم این است که یک تولیدکننده و یک مصرف‌کننده و یک بافر با اندازه متناهی وجود داشته باشد. اگر بافر پر باشد، برای تولیدکننده دو راه حل وجود دارد: یا به حالت خواب برود یا اینکه داده را دور بریزد. در زمان بعدی که مصرف‌کننده یک آیتم را از بافر برمی‌دارد، به تولیدکننده اطلاع می‌دهد تا مجدداً شروع به پرکردن بافر کند. به همین شیوه، اگر مصرف‌کننده بفهمد که بافر خالی است به خواب می‌رود. در زمان بعدی که تولیدکننده داده را در داخل بافر قرار می‌دهد، مصرف‌کننده را از خواب بیدار می‌کند. این راه حل با استفاده از ارتباطات بین پروسه ای که معمولاً از سمافورها استفاده می‌کنند، میسر است. اگر راه حل ناکافی باشد، می‌تواند منجر به بن‌بست شود که در این حالت هر دو پروسه منتظرند تا از خواب بیدار شوند.

پیاده‌سازی ناکافی

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

int itemCount = 0;

procedure producer()
{
 while (true)
 {
 item = produceItem();

 if (itemCount == BUFFER_SIZE)
 {
 sleep();
 }

 putItemIntoBuffer(item);
 itemCount = itemCount + 1;

 if (itemCount == 1)
 {
 wakeup(consumer);
 }
 }
}

procedure consumer()
{
 while (true)
 {

 if (itemCount == 0)
 {
 sleep();
 }

 item = removeItemFromBuffer();
 itemCount = itemCount - 1;

 if (itemCount == BUFFER_SIZE - 1)
 {
 wakeup(producer);
 }

 consumeItem(item);
 }
}

مشکل این راه حل این است که حاوی شرایط رقابتی است که می‌تواند منجر به بن‌بست شود. سناریوی زیر را در نظر بگیرید:

1. مصرف‌کننده همین الان متغیر itemcount را خوانده‌است و متوجه شده‌است که مقدار آن صفر است و می‌خواهد به داخل بلوک if وارد شود.
2. درست قبل از فراخوانی sleep، مصرف‌کننده دچار وقفه می‌شود و تولیدکننده از سر گرفته می‌شود.
3. تولیدکننده یک آیتم ایجاد می‌کند و آن را داخل بافر قرار می‌دهد و مقدار itemcount را افزایش می‌دهد.
4. از آنجایی که قبل از آخرین وضعیت بافر خالی بود، تولیدکننده سعی می‌کند تا مصرف‌کننده را از خواب بیدار کند.
5. متأسفانه مصرف‌کننده هنوز نخوابیده‌است، در نتیجه، فراخوانی wakeup از دست می‌رود. زمانیکه مصرف‌کننده از سر گرفته می‌شود مجدداً به خواب می‌رود و دیگر هیچ وقت بیدار نخواهد شد. علت این است که مصرف‌کننده فقط زمانی توسط تولیدکننده بیدار می‌شود که itemcount برابر یک باشد.
6. تولیدکننده تا زمانی که بافر پر شود وارد حلقه می‌شود و بعد از آن وی نیز به خواب می‌رود از آنجایی که هردو پروسه برای همیشه به خواب می‌روند، به‌ناچار، وارد یک بن‌بست می‌شویم؛ بنابراین این راه حل نامطلوب است.

یک آنالیز دیگر این است که اگر زبان برنامه‌نویسی پروتکل های(semantic) دستیابی‌های همزمان به متغیرهای مشترک (در این مورد itemcount) با استفاده از همگام سازی را تعریف نکرده باشد، آنگاه راه حل مورد استفاده به همین دلیل نامطلوب خواهد بود و نیازی به اثبات آشکار یک شرایط رقابتی نیست.

استفاده از پرچم‌ها (سمافر)

سمافرها مشکل از دست رفتن فراخوانی بیدار کردن را حل می‌کنند. در راه حل زیر، ما از دو سمافور با نام‌های fillcount و emptycount برای حل مسئله استفاده می‌کنیم. fillcount تعداد آیتم‌هایی است که هم‌اکنون در بافر وجود دارد و قابل خواندن است، در حالیکه emptycount تعداد فضاهای خالی موجود در بافر است که می‌توان آیتم‌ها را در آن نوشت. زمانیکه یک آیتم جدید در داخل بافر قرار داده می‌شود، fillcount افزایش پیدا می‌کند و emptycount کاهش پیدا می‌کند. زمانیکه تولیدکننده سعی می‌کند تا emptycount را، که مقدار صفر دارد، کاهش دهد به خواب می‌شود. بعداً، وقتی که یک آیتم مصرف می‌شود، emptycount افزایش پیدا می‌کند و تولیدکننده بیدار می‌شود. طرز کار مصرف‌کننده نیز به همین شکل است.

semaphore fillCount = 0; // items produced
semaphore emptyCount = BUFFER_SIZE; // remaining space

procedure producer()
{
 while (true)
 {
 item = produceItem();
 down(emptyCount);
 putItemIntoBuffer(item);
 up(fillCount);
 }
}

procedure consumer()
{
 while (true)
 {
 down(fillCount);
 item = removeItemFromBuffer();
 up(emptyCount);
 consumeItem(item);
 }
}

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

1. دو تولیدکننده emptycount را کاهش می‌دهند.
2. یکی از تولیدکننده‌ها درگاه خالی بعدی را در بافر مشخص می‌کند.
3. دومین تولیدکننده درگاه خالی بعدی را مشخص می‌کند و نتایج مشابهی با تولیدکننده اول به دست می‌آورد.
4. هر دو تولیدکننده به داخل درگاه یکسانی می‌نویسند.

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

mutex buffer_mutex; // similar to "semaphore buffer_mutex = 1", but different (see notes below)
semaphore fillCount = 0;
semaphore emptyCount = BUFFER_SIZE;

procedure producer()
{
 while (true)
 {
 item = produceItem();
 down(emptyCount);
 down(buffer_mutex);
 putItemIntoBuffer(item);
 up(buffer_mutex);
 up(fillCount);
 }
}

procedure consumer()
{
 while (true)
 {
 down(fillCount);
 down(buffer_mutex);
 item = removeItemFromBuffer();
 up(buffer_mutex);
 up(emptyCount);
 consumeItem(item);
 }
}

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

استفاده از مانیتورها

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

monitor ProducerConsumer
{
 int itemCount = 0;
 condition full;
 condition empty;

 procedure add(item)
 {
 if (itemCount == BUFFER_SIZE)
 {
 wait(full);
 }

 putItemIntoBuffer(item);
 itemCount = itemCount + 1;

 if (itemCount == 1)
 {
 notify(empty);
 }
 }

 procedure remove()
 {
 if (itemCount == 0)
 {
 wait(empty);
 }

 item = removeItemFromBuffer();
 itemCount = itemCount - 1;

 if (itemCount == BUFFER_SIZE - 1)
 {
 notify(full);
 }

 return item;
 }
}

procedure producer()
{
 while (true)
 {
 item = produceItem();
 ProducerConsumer.add(item);
 }
}

procedure consumer()
{
 while (true)
 {
 item = ProducerConsumer.remove();
 consumeItem(item);
 }
}

منابع

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