Лекции (984123), страница 7
Текст из файла (страница 7)
В процессе компьк>терного моделирования исследуется поведение сетей, например, для вычисления максимального или среднего времени ожидания, моделируется реа,кция сети на случайно приходящие сообщения. Та,ким же образом можно имитировать появление посетителей в банке и определить число окон, открываемых в различные часы рабочего дня. Очереди захода самолетов на посадку и ожидания разрешения взлета, очереди автомобилей на проезд в узких местах дорожной сети, и т.
п. тоже нуждаются в моделировании на ЭВМ; ° решение собственных задач информатнки, в частности в области операционных систем ЭВМ. Система имеет дело с целой серией запросов к программным и аппаратным ресурсам: запуск и завершение процессов, .доступ к какому-нибудь регистру, устройству или файлу (принтеру, консоли оператора и т. д.).
Некоторые типы запросов приоритетны по отношению к другим, но одпотипные запросы должны удовлетворяться, вообще говоря, в порядке их поступления. Необходимо подчеркнуть, что математическая статистика, теория случайных процессов, теория массового обслуживания, теория надежности и базирующаяся па их основе теория очередей, способны дать некоторые теоретические результаты, касающиеся очередей, но зачастую требуют слишком упрощающих гипотез о способах, которыми реализук>тся входы и выходы.
Пра,ктически же для получения более реалистических результатов приходится прибегать к моделированию. Более редким вариантом очереди является дек (Во>>Ыс Е>><1сг! >.>пепе) двухконцовая очередь, где чтение и доступ возможны с обоих концов. Ограничив удаление одним концом получают модель очереди с приоритетными льготными элементами. В литературе немного примеров, где применяются деки. Это различные железнодорожные разъезды и трамвайные депо и один из методов внешней сортировки.
Хорошие иллюстрации на тему линейных динамических структур данных (трамвайно-троллейбусного типа> см. в (63). 214 5.4.1 Функциональная спецификация. СОЗДАТЬ: ПУСТО: В ОЧЕРЕДЬ; ИЗ ОЧЕРЕДИ: ПЕРВЫЙ: ДЛИНА: УНИЧТОЖИТЬ: Π— ~От От » Ьоо1еап От х 7' — От О с> От » 1' От — » 1>1 От — «О Если очередь находится в обеих частях спецификации, то исходная очередь подвергается модификации и создается скорректированная очередь того же типа От подобно индуктивному (ллумулятивному) присваиванию тина х +== 1. За,мечание. Операции ИЗ ОЧЕРЕДИ и ПЕРВЫЙ можно рассматривать как единую операцию вида л,>т — » Щ х Т, результатом которой является извлеченная компонента и новая, укороченная очередь. Перечисленные операции имеют следующие свойства И Е 7' и >уд Е От: 1.
ПУСТО(СОЗДАТЬ) — -- багие СОЗДЛТ1э всегда порождает пустую очередь; 2. ПУСТО(В ОЧЕРЕДЬ (дД> -- Га1ве Если добавляется компонента к очереди, то результирующая очередь заведомо непуста; 3. ПЕРВЫЙ(В Ос1ЕРЕДЬ(СОЗДЛТЫ)) -- 1. Внесенный в пусту.ю очередь элемент всегда становится ее первым элементом. 4. Последовательность действий: 215 Итак, очередь - упорядоченный, одномерный, динамически изменяемый набор компонент, в котором включение новых компонент (пополнение очереди) производится на одном конце набора,, а всякий доступ к компонентам и их исключение (удаление обработашн>й компоненты) на другом конце ~43~. Количество комлн>нент очереди называется ее длилюй.
Однако длина очереди в оглределении не фиксируется и может быть вычислена «вручпуло» последовательным перебором всех ее кокплопент. То есть это неэлементарпая составная оглерация. Более того, лля вычисления длины эти элементы придется извлечь из очереди и, если очередь требуется сохранить, поместить их в том же порядке в другую очередь. Ввиду строго последовательного доступа к классической очереди операция вычисления ее длины является довольно дорогой с врсменнбй сложностью 0(>У) и с такой жс пространственной сложностью. Очередь может быть пустой, тогда ес длина равна нулн>. Компонента очереди может иметь любой тип, простой или составной, за, исключением файлового типа Паскаля, для которого присваивание не определено.
Обозначим тип элемента очереди идентификатором 1'. Тип От (очередь объектов типа Т) характеризуется следун>щими операциями: с»: - СОЗДА'!'Ь с»: - В О'!ЕРКДЬ(с», 1,) с»: "В ОЧЕР!йДЬ(с», 12) 1' В олп,личие от, срай,лое перемотка пе требуепъсл!,» »л ПЕ1'ВЫЙ1Ч) ~1=-1, ! 1: ИЗ О 1Е Еди(ц) 1:-=-ПЕРВЫИ(с») 1'1 — 12 1 с»:-- ИЗ ОЧЕРЕДИ® заносящая во вновь созданную пустую очередь сначала элемент 1ь а затем элемент 12, а затем извлекающая из нее два элемента, сохраняет их порядок. Это свойство по индукции может быть распространено на случай любой последовательности элементов (1м 12,..., 1„), даже если эти элементы вставляются в непустую очередь или «разбавлены» ка,кими-то другими элементами, их порядок на выходе из очереди нарушс;н не будет. Функциональная спецификация «очереди вообще» имеет не только теоретическое значение. В частности, указанные правила и свойства функциональной спецификации в точности соответствуют тестам для любой конкретной структуры, претендующей на право называться очередью.
5.4.2 Логическое описание и физическое представление Для работы с очередями в какой-нибудь программной среде надо реализовать перечисленные выше операции с их свойствами. В универсальных языках программирования встроенный тип данных очередь, как правило, отсутствует. Для специализированных языков моделирования, таких как ОРВИ, этот тип данных, наоборот, характерен. Если же надо реализовать очереди на каком-то конкретном универсальном языке программирования, напримср, на Паскале, го это, скорее всего. придется делать вручную. Для этого нужно отобразить абстрактную структуру очереди па именующиеся в Паскале линейные структуры: файл или массив, либо создать цепочку компонент на, динамических структурах 143~. 5.4.2.1 Реализация на файле Назовем тип очереди на файле именем с»пепе: Фуре с»пепе — 61е оГ 'Т; Для каждой очереди опишем переменную Паскаля типа очередь: айаг с»: с»пслпе; причем для долговременных очередей соответствующий файл должен быть внешним, а имя соответствующей файловой переменной должно быть помещено в заголовок Паскаль- программы: ргоигагп с»попса(!прШ,, опгрШ, с»): Процедура СОЗДАТЬ.
216 ргосес1пге Сгеа1е(айаг»1: с1пепе): Ьеиш геът1Се(»1):, епс1; В результате мы получим пустой внешний файл, подготовленный для записи компонент очереди. Спецификатор айаг необходим, поскольку файл-параметр без ~аг передавался бы по значению, что сводится к копированию файлов, нереализованному в Паскале. Функция ПУСТО.
ГппсС1оп Еп1рСу(чаг й: с1пепе): Ьоо1еап; Ьеиш гевеС(»1); ЕтрСу: — ео»(с~); епс1; Поскольку мы реализуем очередь на файле, пустой очереди должен соответствовать пустой файл. Предиката пу»:тоты файла, в Паскале нет, но мс>жно воспол~зо~ат~ся предикатом еоГ(»1), который совпадает с ЕтрС»1Ц) после перемотки файла, к началу. Функцию В ОЧЕРЕДЬ можно реализовать процедурой Риа6, выполняющей неразрус»»аю»»»рю запись (добавление) компоненты в очередь. Церемония производится с соблюдением всех правил работы с файлами Паскаля. Для дозаписи добавляемой компоненты в конец файла надо сначала добраться до его конца.
Это можно сделать только последовательным чтением всех его компонент, но даже после этого в пего нельзя дописать добавляемую компоненту, поскольку в соответствии со стандартом Паскаля операция гевеС устанавливает режим доступа «только чтение Поэтому дозапись компоненты надо делать в едином сеансе записи, копируя исходный файл-очередь в локальный времеш»ый файл»11 с последующей перезаписью в исходный файл и добавлением компоненты. Локальный файл для копирования создается только на время ра,боты этой процедуры.
ргосес1пге Рпа1»(ьаг й: йпепе; С: Т); маг »11: »1пепе: Ьенш гевеС(»1); ген»»г1Се (»11); Мп1е поС ео1(с1) с1о Ьеиш 1' »11:--- »1»~ с11-:-; с1-; неС(»1); рпС(»11); епс1; гевеС(с11); геи г1Се(»1); жЫ1е поС еоЯ»11) с1о Ьен1п 1' »1»= Ч1 (( С С с1-: — с11-; деС(с11); рпС®; епс1; »1":-- С; 217 рп$®; епс1; Функция ПЕРВЫИ. В соответствии с выбранным отображением очереди на, файл первый элемент очереди всегда находится в начале файла. Заметим, что несмотря на наличие спецификатора айаг, обязательного для файлов в Паскале, очередь не модифицируется, к соответствующему файлу даже не применяется операция чтения, а элемент берется из буфера в памяти д ) .
Гппс$1оп Тор(тхаг с1: с!пепе): Т: Ьеп!п гевеС®; Тор: — с1:, епс1; Функция ИЗ ОЧЕ!»ЕДИ должна обеспечивать фактическое исключение выбранной (прочитанной) компоненты из файла, в котором хранится очередь. Альтернативное решение сделать просто гевеС(у) и затем пропустить компоненту де1(д) не годится, так как повторное обращение к этой процедуре снова даст эту же компоненту.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
