Подпрограмма DECISION здесь не рассматривается (см. упр. 9), как и подпрограмма VALUES, которая применяется для указания запросов лифта. В самом конце программы приводится следующий код:

BEGIN

POOLMAX POOL

ENT4 ENT5 JMP NOP END

CYCLE

POOL

BEGIN

В начале FLOOR = 2

и STATE = NEUTRAL. Начать моделирование.

Вслед за пулом располагаются литералы, временное хранилище.

Приведенная выше программа прекрасно моделирует работу лифта, но выполнять ее бесполезно, поскольку она не выводит никаких выходных данных! На самом деле автор добавил в нее подпрограмму PRINT, которая вызывалась в наиболее

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

Было создано несколько языков программирования, которые позволяли упростить форму указания действий дискретного моделирования с последующей компиляцией этих указаний на машинный язык. В данном разделе язык ассемблера использовался, конечно же, потому, что здесь рассматривались основные методы управления связанными списками и подробности дискретного моделирования на компьютере, который способен вьшолнять последовательные, а не параллельные вычисления. Метод управления последовательностью сопрограмм на основе списка WAIT или перечня действий, который описан в этом разделе, называется квазипараллельной обработкой {quasi-parallel processing).

Анализ времени выполнения такой длинной программы сделать довольно трудно, потому что она пронизана весьма сложными взаимосвязями. Однако большие программы часто тратят большую часть времени на выполнение сравнительно небольших процедур, которые осуществляют простые действия. Поэтому хорошую Оценку общей производительности можно получить с помощью особой процедуры трассировки, или, иначе говоря, с помощью профайлера (profiler), которая выполняет программу и записывает, как часто вьшолняется та или иная команда. Она позволяет обнаружить "уязвимые места" производительности программы, которым следует уделить особое внимание. [См. упр. 1.4.3.2-7. См. также Software Practice &: Experience 1 (1971), 105-133, где приводятся примеры таких исследований для программ на языке FORTRAN, произвольно выбранных из мусорных корзин Станфордского компьютерного центра (Stanford Computer Center).] Автор экспериментировал с программой моделирования работы лифта, запуская ее в течение 10000 единиц по моделируемой шкале вре.мени и при условии, что в модели находится 26 человек. Оказалось, что наиболее часто выполнялся цикл сортировки SORTIN, строки 073-075, а именно -1432 раза, тогда как процедура сортировки SORTIN вызывалась 437 раз. Процедура CYCLE выполнялась 407 раз, поэтому для увеличения скорости ее выполнения не следовало бы вызывать подпрограмму DELETEW в строке 095; лучше полностью включить в программу четыре строки этой подпрограммы (с экономией 4и при каждом использовании CYCLE). С помощью профайлера также было обнаружено, что подпрограмма DECISION вызывалась только 32 раза, а цикл на шаге Е4 (строки 217-219) выполнялся всего 142 раза.

Автор надеется, что при изучении этого примера читатель узнает столько же нового о моделировании, сколько автор узнал о работе лифтов.

УПРАЖНЕНИЯ

1. [21] Предложите описание операций вставки и удаления данных с левого конца дважды связанного списка (1). (С учетом тех же операций на правом конце, которые можно вывести из соображений симметрии, получим описание всех действий для дека общего типа)

► 2. [22] Объясните, почему для односвязного списка нельзя вьшолнять операции так же эффективно, как для дека общего типа Удаление элементов может быть эффективно выполнено только с одного конца односвязного списка

► 3. [22] В модели работы лифта из данного раздела для каждого этажа используются три переменные вызова (CALLUP, CALLCAR и CALLDOWN), которые представляют нажимаемые кнопки. Вполне возможно, что вместо трех лифту необходима только одна или

две двоичные переменные для кнопок вызова на каждом этаже. Объясните, в какой последовательности экспериментатор должен нажимать кнопки в данной модели, чтобы доказать, что для каждого этажа (за исключением самого нижнего и самого верхнего) существуют три независимые двоичные переменные.

4. [24 ] Шаг Е9 в сопрограмме работы лифта обычно отменяется на щаге Е6; даже если он не отменен, он выполняет не очень большой объем работы. Объясните, при каких обстоятельствах лифт будет вести себя иначе, если щаг Е9 удалить из модели. Например, может ли лифт иногда останавливаться на этажах в другом порядке?

5. [20] В табл. 1 человек 10 появляется на этаже О в момент 1048. Покажите, что, если бы человек 10 появился на этаже 2, а не на этаже О, лифт отправился бы вверх, а не вниз после входа всех людей в кабину на этаже 1 несмотря на то, что человек 8 желает спуститься на этаж 0.

6. [23] В период 1183-1233 в табл. 1 пассажиры 7-9 входят в кабину лифта на этаже 1; лифт спускается на этаж О, и из него выходит только пассажир 8. Затем лифт снова останавливается на этаже 1, предположительно для того, чтобы взять пассажиров 7 и 9, которые уже находятся в кабине лифта; таким образом, на этаже 1 лифт уже никто не ожидает. (Эта ситуация возникает в Калтехе довольно редко; если вы вошли в лифт, движущийся в ненужном вам направлении, вам придется снова сделать дополнительную остановку на пути к исходному этажу.) Во многих других типах лифтов пассажиры 7 и 9 не были бы взяты в лифт в момент 1183, так как индикаторы снаружи лифта показали бы, что он движется вниз, а не вверх. Им пришлось бы ожидать возвращения лифта. В описанной модели такие индикаторы не предусмотрены, а потому невозможно сказать, в како.м направлении будет двигаться лифт, до тех пор, пока человек не попадет в кабину. Следовательно, табт 1 отражает реальную ситуацию.

Какие изменения необходимо внести в сопрограммы U и Е, чтобы в описанной выше модели лифта использовались внешние индикаторы, благодаря которым людям не приходилось бы входить в кабину лифта, следующего в противопатожном направлении?

7. [25] Часто программистам очень стыдно признавать свои ошибки в программах, но, если ошибки поучительны, о них не следует забывать; лучше сообщить о приобретенном опыте другим. При создании программы из этого раздела автор совершил (среди прочих) следующую ошибку, строка 154 содержала команду "JANZ CYCLE" вместо "JANZ U4A". Действительно, если лифт прибыл на этаж, нужный конкретному человеку, то больше нет необходимости "отменять" шаг U4. Поэтому можно просто перейти к процедуре CYCLE и продолжить моделирование других действий. В чем же заключается ошибка?

8. [21] Создайте код для выполнения шага Е8, строки 277-292, который опущен в программе из данного раздела.

9. [23] Создайте код для подпрограммы DECISION, который опущен в программе из данного раздела.

10. [40] Вероятно, здесь стоит отметить, что, хотя автор пользовался лифтом в течение многих лет и думал, что довольно хорошо знает принцип его работы, только во время написания этого раздела он обнаружил новые факты об алгоритме выбора направления движения реального лифта. Шесть раз автору приходилось экспериментировать с лифтом, и всякий раз он думал, что уж теперь-то он окончательно понял его modus operandi. (Теперь автор не склонен к продолжению этих экспериментов, так как опасается, что во время нового эксперимента обнажится еще одна новая грань поведения лифта, которая будет противоречить предложенному здесь варианту алгоритма.) Мы часто склонны недооценивать степень непонимания предмета, но лишь до тех пор, пока не попытаемся промоделировать его с помощью компьютера.