Научно-исследовательский университет

Томский политехнический университет

Институт Кибернетики

Кафедра ОСУ

Пояснительная записка к курсовой работе

по дисциплине «Структуры и алгоритмы обработки данных»
Вариант №15

Исполнитель

студент, 8В83 ____________ Б.А. Сафронов

(подпись)

____________

(дата)
Руководитель

доцент ____________ О.Б. Фофанов

(подпись)

____________

(дата)

Томск 2010

Содержание

1. Моделирование абстрактных типов данных (АТД) для различных реализаций

1.1 Постановка задачи

Номер задачи: 7;

Система состоит из двух процессоров P1 и P2, трёх очередей F1, F2, F3 и стека (рис.1.7). В систему могут поступать запросы на выполнение задач трёх типов – Т1, Т2, Т3. Задача типа Т1 может выполняться только процессором P1. Задача типа Т2 может выполняться только процессором P2. Задача типа Т3 может выполняться любым процессором. Запрос можно представить записью.

Type

TInquiry= record

Name: String[10]; {имя запроса}

Time: Word; {время обслуживания}

T: Byte; {тип запроса}


Генератор задач
end;

О

Ч

Е

Р

Е

Д

Ь

F1

О

Ч

Е

Р

Е

Д

Ь

F3

О

Ч

Е

Р

Е

Д

Ь

F2

P1

P2


Стек

Рис.1

Поступающие запросы ставятся в соответствующие типам задач очереди. Если очередь F1 не пуста и процессор P1 свободен, то задача из очереди F1 поступает на обработку в процессор P1. Если процессор Р1 обрабатывает задачу типа Т3, а процессор Р2 свободен и очередь F2 пуста, то задача из процессора Р1 поступает в процессор Р2, а задача из очереди F1 в процессор Р1, если же процессор Р2 занят или очередь F2 не пуста, то задача из процессора Р1 помещается в стек.

Если очередь F2 не пуста и процессор P2 свободен, то задача из очереди F2 поступает на обработку в процессор P2. Если процессор Р2 обрабатывает задачу типа Т3, а процессор Р1 свободен и очередь F1 пуста, то задача из процессора Р2 поступает в процессор Р1, а задача из очереди F2 - в процессор Р2, если же процессор Р1 занят или очередь F1 не пуста, то задача из процессора Р1 помещается в стек.

Если очередь F3 не пуста и процессор P1 свободен, и очередь F1 пуста или свободен процессор Р2 и очередь F2 пуста, то задача из очереди F3 поступает на обработку в свободный процессор. Задача из стека поступает на обработку в свободный процессор Р1, если очередь F1 пуста, или в свободный процессора Р2, если очередь F2 пуста.
Стек: 4;

Стек в динамической памяти (связанная схема).

Очередь: 5;

Очередь на ОЛС. “Хвост” очереди – последний, а “голова” - первый элемент ОЛС

1.2 Краткое теоретическое описание реализуемых объектов

Стек – это специальный тип списка, в котором все вставки и удаления выполняются в начале(FIFO-first in first out), называемом вершиной (top). То есть всегда есть доступ только к верхнему элементу, к дальнейшим можно обращаться только после удаления первого. В нашем случае стек представлен динамической структурой: элемент стека – запись, содержащая указатель на следующий элемент.

Очередь – специальный тип списка - (queue), в котором вставка элементов осуществляется с одного конца (rear), а удаление с другого (front). В динамической реализации в записи присутствуют 3 указателя: на следующий элемент, на текущий и на предыдущий.

следующая страница>