проблема спящего брадобрея

[109]

а вот это, наоборот, явно можно сделать проще, даже когда брадобреев много.

// вначале семафор закрыт
newCustomer = new AutoResetEvent(false); 

// customer reception thread[s]
lock (queue) {
  if (queue.Size == maxSize)
    throw "нет мест";
  queue.Enqueue(сustomer);
  newCustomer.Set(); // open semaphore
}

// each barber's thread
while (true) {
  newCustomer.WaitOne(); // let one barber through and close
  lock (queue) {
    if (queue.IsEmpty) 
      continue;
    customer = queue.Dequeue();
  }
  Shave(customer);
}

собственно, этот же код решает и проблему продюсеров-консъюмеров, вместо того, что там написано (на буфер памяти нет, а спящие треды копить память есть, да?)

Comments

[ivan-gandhi.livejournal.com]

Я, кстати, почитал ту задачу, и тоже не понял, в чём проблема. Достаточно ввести ещё одну entity ("стулья", в твоём варианте queue), и вся синхронизация сводится к двум парам, очередь-клиент и очередь-парикмахер.

[109.livejournal.com]

дык кстати стулья-то там есть (клиент же ищет свободный стул).

перефразируя известную поговорку, all concurrency problems can be solved by adding another queue.

[vsi.livejournal.com]

тоже самое без локов... вернее, с локами надежно спрятанным от посторонних глаз в маленькой но зверски полезной библиотеке имени retlang: http://code.google.com/p/retlang/

код можно копи пейст в студию и запускать, предварительно скачав ретланг, конечно, и добавив его в референсесы


using System;
using Retlang.Fibers;
using Retlang.Channels;
using Retlang.Core;
using System.Threading;

class Program
{
static void Main(string[] args)
{
var workerCount = 10;
var customerCount = 100;
var channel = new QueueChannel();
var register = new Channel();
var reset = new AutoResetEvent(false);

Action shave =
c =>
{
Console.Out.WriteLine("Э, как вы обросли, тов. {0}", c);
Thread.Sleep(1000);
register.Publish(c);
};

using (var dump = new DisposableList())
using (var registerFiber = new PoolFiber())
{
register.Subscribe(registerFiber, c =>
{
customerCount--;
Console.Out.WriteLine("Граджданин, {0}, платим и выметаемя, за вами еще {1} небритых харь", c, customerCount);
if (customerCount == 0)
reset.Set();
});
registerFiber.Start();

for (int i = 0; i < workerCount; i++)
{
var fiber = new PoolFiber();
fiber.Start();
dump.Add(fiber);
channel.Subscribe(fiber, shave);
}

for (int i = 0; i < customerCount; i++)
channel.Publish(i);

reset.WaitOne();
}
}
}

[faceted-jacinth.livejournal.com]

А что случится если кастомер ресепшен тред обработает двух кастомеров пока барберы всё ещё спят? AutoResetEvent.Set вроде не блокируется и вообще не гарантирует ничего? И, типа, через несколько суток работы очередь переполняется, все в ахуе, никто ничего не понимает, етс.

[109.livejournal.com]

а, точно. WaitOne нужно с таймаутом пускать.

[faceted-jacinth.livejournal.com]

С каким именно?

По любому же получится, что в течение какого-то времени чувак тусуется в очереди хотя есть свободные барберы. Происходящего не от загрузки процессора, а от хреновости олгоритма.

Вообще его наверное можно исправить заменив этот эвент на семафор. Типа, на каждого поставленного в очередь кустомера ресепшен тред делает +1, а барберы лочатся в попытках сделать -1.


А так, по-моему, довольно явственно проявилось, что использование хитроумных локов для синхронизации самоподдерживается через Dunning–Kruger effect =)

[109.livejournal.com]

> С каким именно?

с экспоненциальным бэкоффом. хотя ты прав в том смысле, что тогда получится не особо проще того, что в википедии написано.

> По любому же получится, что в течение какого-то времени чувак тусуется в очереди хотя есть свободные барберы.

это ты про когда два сразу пришли?

> Вообще его наверное можно исправить заменив этот эвент на семафор. Типа, на каждого поставленного в очередь кустомера ресепшен тред делает +1, а барберы лочатся в попытках сделать -1.

напиши, если не трудно, в явном виде?

[109.livejournal.com]

я вспомнил, что эту задачу уже раньше решал. ну или очень похожую.

AutoResetEvent signal = new AutoResetEvent(false);
object queueLock = new object();
Queue queue = new Queue();
Queue next = new Queue();

public void Next()
{
	next.Enqueue(queue.Dequeue());
	signal.Set();
}

public void AcceptCustomer(T customer)
{
	lock (queueLock)
	{
		if (queue.Count > 9000)
			throw new Exception("нет мест");
		queue.Enqueue(customer);
		if (next.Count == 0) 
			Next();
	}
}

public void BarbersThread()
{
	while (true)
	{
		signal.WaitOne(); // let one barber through and close
		T customer;
		lock (queueLock)
		{
			customer = next.Dequeue();
			if (queue.Count > 0)
				Next();
		}
		Shave(customer);
	}
}

any feedback will be greatly appreciated.

[faceted-jacinth.livejournal.com]

Нифига не понял, что и зачем делает эта версия и почему в ней не возникнет этой же проблемы: "AutoResetEvent.Set: Sets the state of the event to signaled, which allows at most one waiting thread to proceed", соответственно если вызвать его даже не два, а много раз подряд, скажем, в три раза больше раз, чем у нас есть брадобреев, то часть сигналов проебётся -- не разбудит ни одного брадобрея. Поскольку брадобреи бреют не более чем одного кастомера на сигнал, будут накапливаться необслуженные кастомеры.

С этим можно бороться, например брадобреи могут делать так: while (true): lock, get customer, and signal.WaitOne() only if no customers. Не забыв отпустить лок конечно же =) Поскольку тред на ресепшене делает Set после того, как записывает очередного кастомера, всё сработает правильно (и этот Сет вообще говоря тоже нехило бы вынести из-под лока). Из недостатков -- ну, каждый брадобрей, ухвативший более одного кастомера с одного WaitOne, скорее всего стырил его у какого-то другого брадобрея, который по сигналу проснётся, залочит очередь и ничего там не обнаружит, это неэффективно.

Я предлагал другой способ: вместо AutoResetEvent используется Semaphore, ресепшен вызывает Release, барберы -- WaitOne. В отличие от мьютекса семафор не требует, чтобы релизил тот же тред, что лочил. В отличие от AutoResetEvent семафор не проёбывает число релизов. И вроде как довольно очевидно, что если у семафора установить тот же лимит, что и у очереди, то он не переполнится (а если и переполнится, то это не пройдёт бесследно, что ДИКО хорошо). Потому что ресепшен вначале пушит в очередь, потом в семафор, а барберы достают в обратном порядке.


Разумеется, ни в чём вышесказанном я не уверен и только массивные полевые испытания под жуткой нагрузкой могут немного этой уверенности прибавить.

PS: кстати, что за фигня с Reference Source (http://referencesource.microsoft.com/), не в курсе? Что-то оно похоже превратилось в зомби сразу после открытия (в смысле что за блогом, форумом и документацией никто не следит ваще), но вроде что-то иногда выкладывают (вот, под семёрку что-то выложили). И заставить его работать мне не удалось.

[109.livejournal.com]

Нифига не понял, что и зачем делает эта версия и почему в ней не возникнет этой же проблемы: "AutoResetEvent.Set: Sets the state of the event to signaled, which allows at most one waiting thread to proceed", соответственно если вызвать его даже не два, а много раз подряд, скажем, в три раза больше раз, чем у нас есть брадобреев, то часть сигналов проебётся -- не разбудит ни одного брадобрея. Поскольку брадобреи бреют не более чем одного кастомера на сигнал, будут накапливаться необслуженные кастомеры.

мля-а, ну кода же три строчки, что тут непонятного? я не верю, что ты посмотрел и не понял; я о тебе очень высокого мнения. давай ты посмотришь ещё раз, прежде чем я начну объяснять.

[faceted-jacinth.livejournal.com]

А!

Меня вот что запутало: я же правильно понимаю, что в очереди next никогда не должно быть больше одного кастомера, то есть её можно смело превратить в `Customer next;` и вместо `if (next.count > 0)` писать `if (next != null)`, ну а вместо `next.Dequeue` -- `customer = next; next = null`?

Тогда да, кажется тоже работает.

[faceted-jacinth.livejournal.com]

или даже вообще, volatile bool barberPending. Чтобы как бы совсем понятно было.

[109.livejournal.com]

можно и так, но с двумя очередями очевиднее, что происходит (в явном виде употребляются слова enqueue и dequeue), и more generic - мало ли, в следующий раз по два кастомера брать надо будет.

[109.livejournal.com]

а это будет уже совсем непонятно. pending-то кастомер, а не барбер.

и куда его совать-то, этот volatile? вместо локов не получится, локи всё равно нужны. а тогда лишний point of synchronization. но всё равно не понимаю, куда.

[faceted-jacinth.livejournal.com]

Эм, он volatile для того, чтобы компилятор не соптимизил доступ к нему.

В принципе может быть это и не нужно в данном конкретном случае -- lock сам по себе вроде бы является read-write barrier (но вот насчёт read не уверен, кстати!), однако над такими вещами лучше не задумываться излишне, по-моему.

Не, это barberAwakeningPending имелось в виду!

[109.livejournal.com]

я знаю, зачем нужен volatile, я не понимаю, куда его тут совать. ну обнаружили мы, что нету барберов pending, дальше что? спинлочить? не думаю, что ты это имел в виду. код можешь написать?

и да, lock - это всегда both read and write barrier, (иначе бы не работало ничего).

[syarzhuk.livejournal.com]

Кстати, вспомнилось. Мы в институте писали модели всяческих очередей на GPSS
А что есть теперь для подобного?