> -- Trurl писал(а):
> Дело в том, что случайный (в любом смысле) выбор ничем не лучше любого другого. Ситуация в некотором смысле обратная той, что в недетерминированной машине Тьюринга. Тел демон выбирает наилучший вариант, а здесь мы должны быть готовы к тому, что он будет пакостить.
Да, есть такая вероятность, что при случайном выборе какой-то вариант никогда не будет выбираться.
Есть такое понятие fairness (не знаю, как лучше перевести, как честность?). В книге Verification of sequential and concurrent programs говорится:
> -- Цитата:
> Fisher and Paterson [1983] have shown that any fair scheduler that is applicable for arbitrary runs of n components needs at least n! = 1*2*...*n scheduler states.One way of organizing such a scheduler is by keeping the components in a queue. In each check the scheduler activates that enabled component which is earliest in the queue. This component is then placed at the end of the queue.
То есть, по-хорошему, все условия в цикле Дейкстры нужно организовать сначала в очередь, затем выбирать первый, который выполняется, и помещать его в конец очереди.