Д. Кнут - Искусство программирования том 1 (1119450), страница 80
Текст из файла (страница 80)
В первых строках табл. 1 показан более драматичный сценарий: человек вызывает лифт на цокольный этаж, но не дожидается его и уходит спустя 15,2 с. Лифт останавливается на цокольном этаже, но, так как там никого нет, направляется на этаж 4, поскольку несколько вызовов поступило со стороны людей, которые направляются вниз. Программирование этой модели работы лифта для некоторого компьютера (в данном случае для компьютера И1Х) заслуживает внимательного изучения. В любой момент в системе может существовать большое количество моделируемых людей (которые могут находиться в разных очередях, причем они могут не дождаться лифта и уйти в любое время). Кроме того, если сразу несколько человек пытается выйти из кабины лифта во время закрытия дверей, может получиться так, что действия, предусмотренные шагами Е4, Е5 н Ей, будут выполняться одновременно.
Течение времени и управление "одновременным' выполнением может быть запрограммировано в результате представления каждого элемента модели некоторым узлом, содержащим поле ИЕХТТ1ИЕ (в нем указывается, когда выполняется следующее действие этого элемента) и поле ИЕХТ1ИБТ (в нем хранится адрес, по которому данный элемент начинает выполнять команды аналогично ссылке для обычной сопрограммы). Каждый элемент ожидает наступления следующего момента в дважды связанном спнске ЫА1Т. Так как этот "список действий" сортируется по полю ЯЕХТТ1ИЕ, все действия будут обработаны в правильной последовательности моделируемых моментов.
В программе также используются дважды связанные списки ЕЬЕОАТОЕ и ЦОЕОЕ. Каждый узел, представляющий некоторое действие (т. е. действие человека нли лифта), имеет следующий вид: ~~$1 3р3$ ю . '~ ~ й ~ 1 й 1 ~ ~,'- 1 5 ~ ' а * ~ ~й ,' ~-$=$~;4="4„'~$4$~ й~ й~~й~,*.фей. -$ $ .„..1 14~1 ~$йй$„:3 ~4.*$ ~ю , ~1~й 13 1 „~ ~ й ~ 1,~ 1 1 ~ ='$ =~:"~,!$ =$.;=",4~, ;"1~:,й,: ~~й:" Дйй~а 44$ ъаа ~~)$ 1 3 ~~ ~~ мйхсймыйсййюыыюы с ю с Р с с й с й й Й 2 с с Й й й Й И й х х х х х х х х х х х х х х х х х х х х х х х х х х х х х х м х х х х х х х х х х х х х х х хххххххххх хх а а а а а а а а а я а а а с с с с с с с с с к к к к = с с к к к а а к к к к йййй"й""ййк йй" й-- ---й ййвйй ййй й к а а а а а а а к к к с с с с с с с к к с а а а а а а а а а а с а а а а а а а а ййй-х й й к в барр й.йй-йй=кйй"ййй=йй=й йаЫййййййй х 1 !ь1 1 1 1 1 е:.
13:, ~ г ° *"Ф ~ 3 ° " ~'Ф1 " х $ * 1 ° 1 3 $ ~к, з~к~ $ ~й~~ ~ а7~ ~ ~~ФУ~ „',.;: ...' „„-' ~ ~ 1! 1 ~ й; -,.:.„-1 ~! й й „'„' 1 ~'й, „.'; 1 ; '~ ~! „. „-', :~ к к:: к =" к = а -. а =' я -. к =, =..-. а к к м.-. к .-. а к а .-,;";". а к к к а.-. к .-, а д й" й й" " -й х х х х х х х х х х х х х х х х х х х х х х х х х х х х х х х х х х х х х хх х ххх ЧВВВЯ [ту кьвчьтоа Рнс. 12.
Некоторые списки из программы моделирования работы лифта (Заголовки списков указаны слева ) Здесь 1.Е1ИИ1 и ЕЫИКА — связи в списке ИА1Т, а ШИК2 и В1.1ИК2 †свя в списках ЦОЕОЕ и ЕЕЕЧАТОЕ Последние два поля, а также поля 1И и ООТ в структуре (6) относятся к узлу, который представляет человека,и не имеют никакого отношения к узлу, представляющему лифт. Третье слово этого узла на гамом деле является командой "1МР" на языке компьютера М11 На рис. 12 показано типичное содержимое списков МА1Т, ЕЕЕЧАТОЕ и одного из списков ЦОЕОЕ Каждый узел в спяске ЦОЕОЕ одновременно находится в списке ИА1Т со значением ИЕХТ1МБТ = П4, но зто не отражено на данном рисунке, поскольку сложность всех взаимосвязей может помешать читателю понять основную идею.
Теперь рассмотрим саму программу. Она довольна большая, но делится на несколько малых частей (как это обычно бывает со всеми большими программами), каждая из которых выглядит достаточно просто Сначала идет некоторое количество строк кода с определением начального содержания таблиц. Рассмотрим наиболее интересные из них, а именно — заголовки списка ИА1Т (строки 010 и 011), списка ЦБЕОЕ (строки 026 и 031) и списка ЕЕЕЧАТОВ (строки 032-033). Каждый из них является узлом со структурой (6), в которой удалены ненужные слова Заголовок списка ИА1Т содержит только два первых слова узла, а заголовкам списков ЦОЕОЕ и ЕЕЕЧАТОК требуется только последнее слово узла. Кроме того, имеются четыре узла, которые всегда присутствуют в данной модели (строки 012-023): узел ОБЕМ1, который всегда представляет шаг П1, подготовку к появлению в системе нового человека; узел ЕЕЕЧ1, который управляет основными действиями лифта на шагах Е1-Е4, Еб — Е8, а также узлы Е1.ЕЧ2 и Е1.ЕЧЗ, которые используются для действий лифта на шагах Еб и Е9, которые выполняются независимо от других действий лифта относительно моделируемой шкалы времена.
Каждый из этих четырех узлов содержит только три слова, так как они никогда не будут входить в состав списков ЦПЕОЕ и Е(.ЕЧАТОВ. Узлы, представляющие деятельность людей, будут находиться в пуле после основной программы. 001 002 008 004 005 006 007 008 «МОДЕЛЬ 1И ШИК1 Н1.1МК1 ИЕХТ1ИЗТ ООТ ШМК2 Ы.1ИК2 РАБОТЫ ЛИФТА ЕЦО 1:1 ЕЦО 2:3 ЕЦП 4:5 ЕЦП 0:2 ЕЦО ЕЦО 2:3 ЕЦО 4:5 Определение палей внутри узлов. ООУ БЛИЦЫ ФИК СОМ СОИ СОИ СОМ 1ИР СОИ СОМ 1ИР СОИ СОИ 1ИР СОИ СОИ СОИ СОИ ЕЦО СОИ СОИ СОИ СОИ СОМ ОВ ЕЦП СОИ СОИ СОИ СОИ СОИ СОИ СОИ СОИ СОИ СОИ СОМ СОИ СОМ СОМ СОИ 010 011 012 018 014 015 016 017 018 НАХТ Пзеа1 ЕЬЕЧ1 ЕБЕЧ2 01У 020 021 022 028 024 025 026 027 028 ОУУ 080 081 082 088 084 085 086 087 088 08У 040 041 042 048 О.Ц 045 046 047 Е).ЕЧ3 АЧАП. ПИК ЦОЕОЕ П.ЕЧАТ САН.
01 СНРОВАННОГО РАЗМЕРА И ЗАГОЛОВКИ СПИСКОВ ««2(ШИК1),««2(В~.ТМК1) Заголовок списка ЫА1Т, 0 где всегда ИЕХТТ1ИЕ = О. «-2(ШИК1) .«-2(Ж.1МК1) Это узел действия Ш, 0 сначала только он 01 находится в списке ЫА11. 0 Этот узел представляет 0 действия лифта, кроме Е1 действий на шагах Е5 и Е9, 0 Этот узел представляет 0 независимые действия ЕБ лифта на шаге Е5. 0 Этот узел представляет 0 независимые действия Е9 лифта на шаге Е9. 0 Связь са свободными узлами, 0 Текущее время моделирования. 3 «-3(ШИК2),«-3(В(.1МК2) Заголовок списка ЦОЕОЕ[0]. «-3(ШИК2),«-3(ВБ1МК2) Заголовок списка ПОБОЕ(1]. »-3(ШМК2),«-З(Ж.1МК2) Сначала все очереди «-З(ШИК2),«-3(Ы.1МК2) пусты. «-3(ШИК2),«-З(В01ИК2) Заголовок списка ЦОЕПЕ[4]. 3 «-3(ШИК2), ° -3(В51ИК2) Заголовок списка ЕБЕЧАТОВ. О О "Дополнение" нулями таблицы САьь 0 (см.
строки 183-186). 0 0 САЫЛР (0], СА(.(.САВ [0], САШ)ОЫИ [О] 0 САШ)Р (1], СШ.САВ (1], СААХПОЫИ И] 0 САШ)Р [2], САББСАВ (2], СА1100 ЫИ [2] 0 САШ1Р(З], САББСАВ[3], САББООЫИ(3] 0 СА110Р(4], САББСАВ[4], СА1100ЫИ[4] 0 0 "Дополнение«нулями таблицы СА11. 0 (см строки 178-181). 0 0 Индикация открытых дверей, активное состояние.
048 02 050 03 Индикация состояния бездействия. Индикация открытых дверей, активное состояние Я СОМ 0 СОМ О Следующая часть программы содержит основные подпрограммы и главные управляющие процедуры процесса моделирования. Подпрограммы 1ИБЕЕТ и ОЕ|ЕТЕ выполняют типичные манипуляции дважды связанными списками. Они помещают текущий узел в список ОПЕПЕ или ЕЕЕЧАТОЕ либо извлекают его из этих списков. (В программе "текущий узел" С всегда представлен индексным регистром 6.) Для работы со списком НА1Т также предусмотрены некоторые подпрограммы. Так, подпрограмма БОЕТ1И помешает текущий узел в список МА1Т, сортируя его по полю МЕХТТ1МЕ. А подпрограмма 1ИМЕП вставляет текущий узел в середину списка МА1Т. Подпрограмма НО10 помещает текущий узел в список МА1Т, причем значение поля ИЕХТТ1НЕ равно текущему времени плюс значение регистра А.
Подпрограмма ОЕ|ЕТЕМ удаляет текущий узел нз списка ИА1Т. Процедура СУСЛЕ является сердцевиной модели управления, поскольку именно она определяет, какое действие будет выполнено дальше (а именно — первый элемент списка МА1Т, который, как нам теперь известно, не пуст), и переходит к его выполнению. Существует два особых входа в процедуру СХС1Е: во-первых, СХС1.Е1 устачавливает значение ИЕХТ1ИЯТ в текущем узле, а во-вторых, НО10С выполняет то же самое с дополнительным вызовом подпрограммы НОЕВ, Таким образом, результат выполнения команды "ЛИР Н01.0С" со значением 1 в регистре А будет заключаться в приостановке действий на 1 единиц по моделируемой шкале времени с переходом в дальнейшем к следующему адресу. 050 ь ПОНПРОГРАИИЫ И ПРОЦЕКУРА 051 1ИЯЕЕТ ЯТ1 9Р Обг 102 3,1(ШМК2) 053 ЯТ2 3,6(ь11ИК2) 054 ЯТб 3,1(ШИК2) 055 ЯТб 3,2(ЕЬ1МК2) 056 ЯТ1 3,6(К11МК2) 057 9Н 1МР 056 ОЕьЕТЕ ЯТ1 9Р 050 101 3,6(ШМК2) 060 ь02 3,6(Еь1ИК2) 061 ЯТ1 3,2(ШИК2) 063 ЯТ2 3,1(Е11ИК2) 065 9М 1МР 061 1ИИЕО ЯТ) 9Р 065 ЬОА ТГИЕ Обб ЯТА 1,6 067 ЕИТ1 МА1Т Обб 1ИР 2Р 060 П010 АОО Т1ИЕ 070 ЯОЕТ1И ЯТ1 9Р 071 ЯТА 1,6 073 ЕМТ1 МА1Т 078 101 О, 1(ШМК1) 071 СИРА 1,1 УПРАВЛЕНИЯ Вставить МОВЕ(С) слева от ИООЕ(г11).
г12 +- ШИК2(г11). ШИК2(С) <- г12. ШМК2(г11) +- С. ЕЬТМК2(г12) +- С, мь1ик2(с) +- г11. Выйти нз подпрограммы. Удалить МОВЕ(С) нз списка. Р+- ШМК2(С) 0 +- М11мк2(с). ШМК2(0) +- Р. еь1ик2(Р) <- 0 Выйти из подпрограммы. Вставить МОВЕ(С) в начале списка МА1Т. Установить ИЕХТТ1ИЕ(С) +- Т1ИЕ. Р < — 1,0С(НА1Т) Вставить МОВЕ(С) справа от ИОВЕ(Р).
гЛ +- ТГИЕ + гЛ. Рассортировать МОВЕ(С) в списке МА1Т. Установить МЕХТТ1ИЕ(С) +- гА, Р +- 10С(МА11) Р +- ШМК1(Р) Сравнить значения в полях МЕХТТ1ИЕ слева направо. 078 Л. ь-2 Установить МЕХТ1М5Т(С) (- г1. тхме +- мехттХНЕ(С). Удалить МООЕ(С) из списка ЧА1Т. Перейти к МЕХТ1МЗТ(С). $ Теперь рассмотрим код сопрограммы П. В начале шага П1 текущим узлом С является узел ОБЕК1 (см. выше строки 012 — 014) и указанные в строках 099 и 100 действия повторно помещают человека ОБЕЕ1 в список ЧА1Т так, что следующий человек появится в системе спустя 1ИТЕЕТ1МЕ единиц времени.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
