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

برای حل مسئله این وسوسه وجود دارد که از راه حل زیر استفاده کنیم. در این راه حل از دو روتین کتابخانه تحت عنوان 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». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۱ مارس ۲۰۲۱.