Задача постачальника-споживача

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Задача постачальника-споживача (англ. producer-consumer problem), також відома як задача обмеженого буфера (англ. bounded-buffer problem) - це класичний приклад задачі синхронізації кількох процесів. Задача описує два процеси, постачальник і споживач, які спільно використовують буфер встановленого розміру. Завданням постачальника є створення шматку даних, запис його до буфера і повторення цих дій раз за разом. Одночасно з цим споживач споживає дані (тобто, видаляє їх з буфера) по одному шматку за раз. Задача полягає в тому, щоб не дати постачальнику записати дані, коли буфер повний, а споживачу не дати видалити дані з порожнього буфера.

Розв'язком може бути перехід у стан очікування або скасування даних у буфері, коли той заповниться. Коли споживач видалить наступні дані з буфера, він сповіщає про це постачальника, який починає заповнювати буфер знов. В цьому разі споживач може заснути, якщо буфер виявиться порожнім. Коли постачальник запише наступні дані він будить споживача. Розв'язання задачі можна досягнути за допомогою взаємодії між процесами, зазвичай використовуються семафори. Невідповідний підхід може спричинити взаємне блокування, коли обидва процеси опиняться в стані очікування. Задача може бути узагальнена на випадок багатьох постачальників і споживачів.

Здійснення[ред.ред. код]

Непідхоже здійснення[ред.ред. код]

Такий розв'язок дозволяє системі потрапити в стан перегонів. Для розв'язання цієї проблеми уважний розробник може використати рішення подане нижче. Використовуються дві бібліотечні функції, sleep і wakeup. Коли викликається sleep, викликач блокується допоки інший процес не розбудить його через використання wakeup. itemCount - кількість записів у буфері.

int itemCount;
 
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 дорівнює 1.
  6. Постачальник буде працювати до заповнення буфера, після чого також засне.

Тож обидва процеси будуть спати довіку, ми втрапили в взаємне блокування.

Додатковий розбір показує, що якщо мова програмування не надає можливість конкурентного доступу до спільних змінних (наразі itemCount) без використання механізмів синхронізації, тоді рішення незадовільні, навіть без необхідності показування стану перегонів.

Використання семафорів[ред.ред. код]

Семафори розв'язують питання неспрацювання виклику wakeup. В рішенні нижче ми використовуємо два семафори, fillCount і emptyCount, для розв'язання проблеми. fillCount - це кількість доступних записів у буфері, і emptyCount - це кількість вільних місць в буфері. fillCount збільшується, а emptyCount зменшується коли новий запис записується. Якщо постачальник намагається зменшити emptyCount коли його значення нуль, тоді він засинає. Коли споживається наступний запис, emptyCount збільшується і постачальник прокидається. Споживач працює подібним чином.

semaphore fillCount = 0; // записів записано
semaphore emptyCount = BUFFER_SIZE; // залишилось місця
 
procedure producer() {
    while (true) {
        item = produceItem();
        down(emptyCount);
            putItemIntoBuffer(item);
        up(fillCount);
    }
}
 
procedure consumer() {
    while (true) {
        down(fillCount);
            item = removeItemFromBuffer();
        up(emptyCount);
        consumeItem(item);
    }
}

Наведений розв'язок спрацьовує добре, коли присутні один постачальник та один споживач. Однак, у випадку з багатьма постачальниками та споживачами цей розв'язок схильний до серйозних станів перегону, що можуть призвести до читання з однієї або писання в одну комірку кількома процесами одночасно. Для розуміння як це можливо уявімо як може бути здійснена підпрограма putItemIntoBuffer(). Вона може містити дві дії, перша це визначення доступного слоту і друга це запис в нього. ця процедура може виконуватись одночасно декількома процесами, що уможливлює такий перебіг подій:

  1. Два постачальники зменшують emptyCount
  2. Один з них визначає наступну порожню комірку в буфері
  3. Другий постачальник визначає наступну порожню комірку і отримує однаковий з першим результат
  4. Обидва пишуть в одну комірку

Для подалання цієї проблеми, ми маємо переконатись, що лиш один постачальник виконує putItemIntoBuffer() в цей час. Інакше кажучи, ми потребуємо спосіб для виконання критичної секції із взаємним виключенням. Для успішного виконання цієї задачі ми використаємо двійковий семафор, відомий як м'ютекс. Через те, що значення м'ютекса може бути або нуль, або одиниця, тільки один процес може виконуватись між down(mutex) і up(mutex). Розв'язок для багатьох постачальників і споживачів наведений вище.

semaphore mutex = 1;
semaphore fillCount = 0;
semaphore emptyCount = BUFFER_SIZE;
 
procedure producer() {
    while (true) {
        item = produceItem();
        down(emptyCount);
            down(mutex);
                putItemIntoBuffer(item);
            up(mutex);
        up(fillCount);
    }
}
 
procedure consumer() {
    while (true) {
        down(fillCount);
            down(mutex);
                item = removeItemFromBuffer();
            up(mutex);
        up(emptyCount);
        consumeItem(item);
    }
}

Зауважте, що черговість збільшення та зменшення різних семафорів важлива: зміна черговості може спричинити взаємне блокування.

Використання моніторів[ред.ред. код]

Наступний псевдокод наводить розв'язок задачі постачальника-споживача із використанням моніторів. Через прихованість взаємного виключення в випадку використання моніторів, додаткові зусилля для захисту критичної секції не потрібні. Інакше кажучи, розв'язок наведений нижче працює з будь-якою кількістю постачальників і споживачів без змін. Варто також зазначити, що використання моніторів робить можливість перегонів значно меншою порівняно з використанням семафорів.

monitor ProducerConsumer {
    int itemCount
    condition full;
    condition empty;
 
    procedure add(item) {
        while (itemCount == BUFFER_SIZE) {
            wait(full);
        }
 
        putItemIntoBuffer(item);
        itemCount = itemCount + 1;
 
        if (itemCount == 1) {
            notify(empty);
        }
    }
    procedure remove() {
        while (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()
    }
}

Зауважте використання while в коді згори у випадку перевірки на порожність або заповнення буфера. Якщо while замінити на if, забагато записів може бути записано в буфер або може відбутися спроба видалення з порожнього буфера.

Без семафорів або моніторів[ред.ред. код]

Задача постачальника-споживача, особливо у випадку одного постачальника та одного споживача, має значну подібність до FIFO або каналу зв'язку. Шаблон постачальник споживач може забезпечити високо дієву передачу даних без покладання на семафори, м'ютекси або монітори для передачі даних. Використання цих примітивів може вплинути на швидкодію через високу вартість здійснення. Базовий код на C подано нижче. Зауважте, що:

  • Атомарний читати-змінювати-записувати доступ до спільних змінних не використовується: кожна з двох змінних лічильників оновлюється лише одним потоком.
  • Цей приклад не присипляє потоки, хоча це може бути вдалим рішенням в деяких системах.
volatile unsigned int produceCount, consumeCount;
TokenType buffer[BUFFER_SIZE];
 
void producer(void) {
    while (1) {
        while (produceCount - consumeCount == BUFFER_SIZE)
            sched_yield(); // буфер повний
 
        buffer[produceCount % BUFFER_SIZE] = produceToken();
        produceCount += 1;
    }
}
 
void consumer(void) {
    while (1) {
        while (produceCount - consumeCount == 0)
           sched_yield(); // буфер порожній
 
        consumeToken( buffer[consumeCount % BUFFER_SIZE]);
        consumeCount += 1;
    }
}