Вот в чем проблема. Вы купили брюки в универмаге. К сожалению, они слишком тугие, и вам нужно их заменить. Вы звоните в магазин и просите зарезервировать для вас следующий размер. В следующую субботу с чеком на руках вы возвращаетесь в магазин. К сожалению, пять человек уже ждут на кассе. После нескольких минут наблюдения вы подсчитали, что кассир обслуживает одного покупателя каждые четыре минуты. Таким образом, ваше время ожидания должно быть около 20 минут. Но 20 минут ждать долго, учитывая вашу просьбу. Что вы должны сделать? Вернуться позже? Продолжать ждать?
Проблема организации очередей не нова в нашем нынешнем обществе, и такие математики, как Александр Яковлевич Хинчин или Дэвид Джордж Кендалл, поняли ее настолько хорошо, что без колебаний разрабатывали математические теории для оптимизации потоков [1–2]. Их обычно называют теориями массового обслуживания. Их можно применять в различных ситуациях, таких как управление самолетами в аэропорту, ожидание клиентов у стойки или даже при хранении компьютерных программ перед их обработкой. Например, закон Литтла [3] утверждает, что среднее количество ⟨N⟩ заявок в устойчивой системе равно их средней частоте прихода λ, умноженной на их среднее время τ, проведенное в системе, т.е.
⟨N⟩=λ×τ
Однако наша исходная задача имеет интересную особенность. В очереди время ожидания для каждого клиента не обязательно одинаково. На самом деле довольно часто бывает, что у клиентов разное время ожидания, потому что у клиентов разные проблемы. Итак, в нашей исходной задаче сложность заключается в том, что запрос (обменять штаны) требует для кассира гораздо меньше времени на выполнение, чем другие запросы покупателей. И, наконец, вы наказаны.
В области компьютерных наук также существуют проблемы с очередями, и некоторые ученые-компьютерщики разработали очень сложные системы для их решения. Так обстоит дело, например, с сервером NodeJS. NodeJS — это бесплатная программная платформа, написанная на JavaScript и ориентированная на сетевые приложения, которые необходимо масштабировать. Вы можете использовать NodeJs для создания веб-сервера и использовать его для трансляции вашего веб-сайта. Но вы также можете использовать NodeJ для создания приложений с асинхронным вводом-выводом (I/O), таких как сервер обмена мгновенными сообщениями с несколькими пользователями. Особенность NodeJS заключается в том, что он основан на инфраструктуре, управляемой событиями, которая позволяет ему работать асинхронно. Это свойство делает NodeJS неблокирующей системой для программ (см. рис. 1).
Во время выполнения сценария часто бывают фазы «ожидания», когда сценарию приходится ждать ответа от внешней части системы (ввод/вывод), прежде чем он сможет продолжить выполнение. В это время скрипт не может обрабатывать новые задачи и система блокируется. В NodeJS все по-другому, поскольку система не будет ждать завершения скрипта, чтобы выполнить другой скрипт. NodeJS будет запускать несколько скриптов параллельно. Благодаря структуре, управляемой событиями, система будет проинформирована об ожидающих выполнения сценариях и о сценариях, которые необходимо выполнить. Таким образом, все операции внутри системы выполняются асинхронно, а глобальная инфраструктура позволяет избежать очередей.
В примере на рис. 1, у нас загружаются два файла. В системе блокировки две загрузки выполняются одна за другой. Таким образом, общее время ожидания превышает 10 секунд. В неблокирующей системе две загрузки выполняются параллельно, что сокращает общее время ожидания. Обратите внимание, однако, что загрузка файлов 1 и 2 по отдельности обычно занимает больше времени в неблокирующей системе, чем в блокирующей. Однако в целом время загрузки в неблокирующей системе короче, чем в блокирующей.
Но теперь вернемся к нашей первоначальной задаче. Если мы применим логику неблокирующей системы, такой как NodeJS, к нашей очереди магазина, у нас будет следующее решение: мы просто оценим время ожидания каждого запроса клиента в очереди и временно приостановим клиентов, чей запрос слишком длинный, чтобы пропустить клиентов, чей запрос короче. Как только короткий запрос клиента будет выполнен, кассир может забрать клиента, чей запрос длинный. Если запрос клиента все еще слишком длинный, клиент откладывается в сторону, а клиент с более коротким запросом идет к кассиру. И так далее. Затем мы получаем неблокирующую, асинхронную и управляемую событиями очередь.
Однако это решение может работать только с согласия всех клиентов в очереди. Действительно, клиент, не желающий участвовать в неблокирующей системе и поэтому не желающий быть отстраненным, чтобы освободить место для другого клиента, чей запрос быстрее, будет неумолимо блокировать систему, и мы будем прибегать к так называемая блокирующая система. Эта новая проблема похожа на работу Джона Нэша. В этой ситуации точка равновесия Нэша не достигается, потому что хотя бы один человек не играет в игру неблокирующей системы.
Использованная литература:
[1] Дэвид Г. Кендалл. Случайные процессы, возникающие в теории массового обслуживания, и их анализ методом вложенной цепи Маркова. Анналы математической статистики. 1953. Лиен
[2] Дж. Кингман. Дэвид Джордж Кендалл. 15 января 1918 г. - 23 октября 2007 г. Биографические воспоминания членов Королевского общества. 2009. Залог
[3] Джон Д.К. Литтл. Доказательство формулы массового обслуживания L = λW. Исследование операций, том 9, выпуск 3, стр. 383–397. 1961. Лиен
