3. Порядок выполнения работы

1. Получить вариант задания у преподавателя.

2. Разработать программу.

3. Продемонстрировать выполнение программы преподавателю, сравнить полученный результат с ожидаемым.

4. Оформить и защитить отчет.

4. Требования к оформлению отчета

Отчет по лабораторной работе должен содержать следующие разделы:

• задание по лабораторной работе;

• листинг программы;

• выводы по проделанной работе.

5. Варианты заданий

1. Синтаксический контроль расстановки скобок в арифметическом выражении.

2. Вычисление арифметического выражения, представленного в постфиксной форме записи.

3. Перевод арифметического выражения из инфиксной формы записи в постфиксную.

4. "Ханойская башня". В общем виде постановка задачи состоит в следующем.

Башня состоит из N дисков, положенных один на другой так, что чем выше находится диск, тем меньше его диаметр.

Требуется переместить эту башню, соблюдая следующие правила:

- за один раз можно перекладывать только один диск;

- нельзя класть диск на диск меньшего размера;

- можно пользоваться только одной резервной площадкой.

При выполнении работы программу решения поставленной задачи следует дополнить средствами визуализации на экране дисплея процесса перемещения дисков.

6. Контрольные вопросы.

1. Что такое стек?

2. Какие еще структуры данных Вам известны?

3. Какие функции используются для реализации стека?

4. Для чего может быть использован стек?

Лабораторная работа №2 Использование очереди при решении задач обслуживания вс поступающих заявок

1. Цель работы

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

2. Теоретические сведения

Процедуры и функции, необходимые для реализации очереди, следует оформить в виде макромодуля Unit. Рекомендуемый состав интерфейсной секции модуля Unit состоит в следующем.

InitQueue - процедура для инициализации структуры; вызов процедуры должен быть выполнен до начала любых действий с очередью;

PutQueue - процедура для добавления нового элемента в конец очереди;

GetQueue - функция для получения первого элемента очереди (элемент из очереди удаляется);

IsEmptyQueue - функция для проверки наличия элементов в очереди; для пустой очереди функция возвращает значение TRUE (истина);

IsFullQueue - функция для проверки возможности вставки в очередь новых элементов; при отсутствии доступной памяти функция возвращает TRUE;

QueueError - функция для получения кодов завершения выполняемых процедур и функций, работающих с очередью.

Обработку ошибочных ситуаций, возникающих при работе с очередью, рекомендуется провести в соответствии с методикой, описанной в предыдущей лабораторной работе.

Приведенную форму интерфейсной секции следует сохранить и для последующих реализаций очереди при использовании других структур хранения.

Поддержка кольцевого буфера

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

Проблема заключается в "движении" очереди за счет удаления головных элементов и добавления хвостовых. Решением проблемы является организация на одномерном массиве "кольцевого буфера", т.е. введения дополнительного отношения следования между первым и последним элементами массива.

Структура хранения очереди в виде кольцевого буфера может быть определена при помощи следующего набора переменных:

- QueueBuff - одномерный одноиндексный массив для организации кольцевого буфера;

- QueueSize - константа для задания размера массива (количество элементов);

- Head - индекс элемента массива QueueBuff с первым элементом очереди;

- Tail - индекс элемента массива QueueBuff, следующим за последним элементом очереди (такое указание конца очереди может упростить реализацию программ поддержки).

Структура хранения очереди в кольцевом буфере.

Дополнительное отношение следования (связь между первым и последним элементами) целесообразно реализовать программно при помощи функции NextQueuePos.

Процедура SetQueErr используется для записи кода завершения в переменную QueueErr.

Рекомендуемая последовательность реализации процедур и функций такова:

InitQueue

SetQueErr

QueueError

IsEmptyQueue

IsFullQueue

PutQueue

GetQueue

При реализации лабораторной работы для контроля правильности работы программ рекомендуется разработка средств визуализации содержимого очереди задач. Возможный вариант демонстрации очереди состоит в показе на экране кольцевого буфера в виде затемненного прямоугольника, на котором цветом выделяется положение элементов очереди. Демонстрацию очереди желательно выполнить в динамике, при которой визуальный образ очереди должен перемещаться на экране в соответствии с изменением положения очереди.

Здесь кратко рассмотрены рекомендации для решения задачи имитации процесса поступления и обслуживания заданий в вычислительной системе.

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

- количество поступивших в ВС заданий;

- количество отказов в обслуживании заданий из-за переполнения очереди;

- среднее количество тактов ожидания обслуживания;

- количество тактов простоя процессора из-за отсутствия в очереди заданий для обслуживания и др.

Каждое задание в системе представляется некоторым однозначным идентификатором (например, порядковым номером задания).

Для проведения расчетов фиксируется (или указывается в диалоге) число тактов работы системы. Выполнение каждого такта состоит в последовательной имитации момента появления нового задания и момента освобождения процессора.

Для моделирования момента появления нового задания можно использовать значение датчика случайных чисел. Если значение датчика меньше некоторого порогового значения q1 (0<=q1<=1), то считается, что на данном такте имитации в вычислительную систему поступает новое задание (тем самым параметр q1 можно интерпретировать как величину, регулирующую интенсивность потока заданий).

Регистрация нового задания в ВС может быть сведена к передаче идентификатора задания в очередь ожидания процессора. Ситуацию переполнения очереди заданий следует понимать как нехватку ресурсов ВС для ввода нового задания (отказ от обслуживания).

Для моделирования процесса обработки заданий следует учитывать, что процессор может быть занят обслуживанием очередного задания либо же может находиться в состоянии простоя.

Простой процессора возникает в случае, когда при завершении обработки очередного задания очередь ожидающих заданий оказывается пустой.

Моделирование момента завершения обработки очередного задания также может быть выполнено по описанной выше схеме. При помощи датчика случайных чисел формируется еще одно случайное значение, и если это значение меньше порогового значения q2 (0<=q2<=1), то принимается, что на данном такте имитации процессор завершил обслуживание очередного задания и готов приступить к обработке задания из очереди ожидания (тем самым параметр q2 можно интерпретировать как величину, характеризующую производительность процессора ВС).

Если процессор завершил обработку очередного задания или находится в состоянии простоя, предпринимается попытка загрузки процессора, извлекая для обработки задание из очереди ожидания. В случае, когда очередь заданий оказывается пустой, процессор остается незагруженным (простой процессора).

Если процессор завершил обработку очередного задания или оказался свободным после выполнения предшествующего, то предпринимается попытка его загрузки. Для этого извлекается задание из очереди ожидания. Следует учитывать, что очередь заданий может оказаться пустой, и процессор в этом случае останется незагруженным (простой процессора).

При реализации описанной выше схемы имитации процесса обслуживания заданий в вычислительной системе разработку программного комплекса рекомендуется выполнить в виде двух макромодулей. В первом модуле комплекса целесообразно выполнить реализацию простейшей модели вычислительной системы. Во вторую же часть программы (Unit) рекомендуется поместить все подпрограммы поддержки, отвечающие за работу с очередью.