Структуры данных «стек» и «очередь» (Pascal/С)

Цель работы: изучить СД «стек» и «очередь», научиться их программно реализовывать и использовать.

З а д а н и е

1. Для СД «стек» и «очередь» определить:

1.1. Абстрактный уровень представления СД:

1.1.1. Характер организованности и изменчивости.

1.1.2. Набор допустимых операций.

1.2. Физический уровень представления СД:

1.2.1. Схему хранения.

1.2.2. Объем памяти, занимаемый экземпляром СД.

1.2.3. Формат внутреннего представления СД и способ его интерпретации.

1.2.4. Характеристику допустимых значений.

1.2.5. Тип доступа к элементам.

1.3. Логический уровень представления СД.

Способ описания СД и экземпляра СД на языке программирования.

2. Реализовать СД «стек» и «очередь» в соответствии с вариантом индивидуального задания в виде модулей на языках Pascal и С.

3. Разработать программы на языках Pascal и С, моделирующие вычислительную систему с постоянным шагом по времени (дискретное время) в соответствии с вариантом индивидуального задания (табл.16) с использованием модулей, полученных в результате выполнения пункта 2. Результат работы программ представить в виде таблицы 15. В первом столбце указывается время моделирования 0, 1, 2, …, N. Во втором — для каждого момента времени указываются имена объектов (очереди — F₁, F₂, …, F_N; стеки — S₁, S₂, …, S_M; процессоры — P₁, P₂, …, P_K), а в третьем — задачи (имя, время), находящиеся в объектах.

Таблица 15

Результаты работы программы

Время	Объекты	Задачи
	F1	(имя,время),(имя,время),...,(имя,время)
:	:::
FN	(имя,время),(имя,время),...,(имя,время)
S1	(имя,время),(имя,время),...,(имя,время)
:	:::
SM	(имя,время),(имя,время),...,(имя,время)
P1	(имя,время)
:	:
PK	(имя,время)
	F1	(имя,время),(имя,время),...,(имя,время)
:	:::
FN	(имя,время),(имя,время),...,(имя,время)
S1	(имя,время),(имя,время),...,(имя,время)
:	:::
SM	(имя,время),(имя,время),..., (имя,время)
P1	(имя,время)
:	:
PK	(имя,время)
:	:	:::

Таблица 16

Варианты индивидуальных заданий

Номер варианта	Номер модуля для стека	Номер модуля для очереди	Номер задачи

Окончание табл.16

Варианты задач

1. Система состоит из процессора P, трех очередей F₀, F₁, F₂ и стека S (рис.9). В систему поступают запросы. Запрос можно представить записью

на языке Pascal:

Type

TInquiry= record

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

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

P: Byte;{приоритет задачи 0 —высший,

1 — средний, 2 — низший}

end;

на языке C:

typedef struct TInquiry

{

char Name[10]; // Имя запроса

unsigned Time; // Время обслуживания

char P; /* Приоритет задачи: 0 — высший,

1 — средний, 2 — низший */

};

Поступающие запросы ставятся в соответствующие приоритетам очереди. Сначала обрабатываются задачи из очереди F₀. Если она пуста, можно обрабатывать задачи из очереди F₁. Если и она пуста, то можно обрабатывать задачи из очереди F₂. Если все очереди пусты, то система находится в ожидании поступающих задач (процессор свободен), либо в режиме обработки предыдущей задачи (процессор занят). Если поступает задача с более высоким приоритетом, чем обрабатываемая в данный момент, то обрабатываемая помещается в стек и может обрабатываться тогда и только тогда, когда все задачи с более высоким приоритетом уже обработаны.

Рис.9. Система задач 1 — 3

2. Система состоит из процессора P, трех очередей F₀, F₁, F₂ и стека S (см. рис.9). В систему поступают запросы. Запрос можно представить записью

на языке Pascal:

Type

TInquiry= record

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

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

P: Byte;{приоритет задачи 0 — высший, 1 — средний, 2 —низший}

end;

на языке C:

typedef struct TInquiry

{

char Name[10]; // имя запроса

unsigned Time; // время обслуживания

char P; /* приоритет задачи: 0 — высший, 1 — средний, 2 — низший */

};

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

3. Система состоит из процессора P, трех очередей F₀, F₁, F₂ и стека S (см. рис.9). В систему поступают запросы. Запрос можно представить записью

на языке Pascal:

Type

TInquiry= record

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

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

P: Byte;{приоритет задачи 0 — высший,

1 — средний, 2 — низший}

end;

на языке C:

typedef struct TInquiry

{

char Name[10]; // Имя запроса

unsigned Time; // Время обслуживания

char P; /* Приоритет задачи: 0 — высший,

1 — средний, 2 — низший */

};

Поступающие запросы ставятся в соответствующие приоритетам очереди. Сначала обрабатываются задачи из очереди F₀. Если она пуста, можно обрабатывать задачи из очереди F₁. Если и она пуста, то можно обрабатывать задачи из очереди F₂. Если все очереди пусты, то система находится в ожидании поступающих задач (процессор свободен), либо в режиме обработки предыдущей задачи (процессор занят). Если поступает задача с более высоким приоритетом, чем обрабатываемая в данный момент, то обрабатываемая помещается в стек, если она выполнена менее чем на половину по времени, и может обрабатываться тогда и только тогда, когда все задачи с более высоким приоритетом уже обработаны.

4. Система состоит из двух процессоров P₁ и P₂, трех очередей F₀, F₁, F₂ и двух стеков S₁ и S₂ (рис.10).

Рис.10. Система задчи 4

В систему поступают запросы. Запрос можно представить записью

на языке Pascal:

Type

TInquiry= record

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

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

P: Byte;{приоритет задачи 0 — высший,

1 — средний, 2 — низший}

end;

на языке C:

typedef struct TInquiry

{

char Name[10]; // имя запроса

unsigned Time; // время обслуживания

char P; /* приоритет задачи: 0 — высший,

1 — средний, 2 — низший */

};

Поступающие запросы ставятся в соответствующие приоритетам очереди. Сначала обрабатываются задачи из очереди F₀. Задача из очереди F₀ поступает в свободный процессор P₁ или P₂, если оба свободны, то в P₁. Если очередь F₀ пуста, то обрабатываются задачи из очереди F₁. Задача из очереди F₁ поступает в свободный процессор P₁ или P₂, если оба свободны, то в P₁. Если очереди F₀ и F₁ пусты, то обрабатываются задачи из очереди F₂. Задача из очереди F₂ поступает в свободный процессор P₁ или P₂, если оба свободны, то в P₁. Если процессоры заняты и поступает задача с более высоким приоритетом, чем обрабатываемая в одном из процессоров, то задача из процессора помещается в соответствующий стек, а поступающая — в процессор. Задача из стека помещается в соответствующий процессор, если он свободен, и очереди с задачами более высокого приоритета пусты.

5. Система состоит из трех процессоров P₁, P₂, P₃, очереди F, стека S и распределителя R (рис.11).

Рис.11. Система задач 5 и 6

В систему поступают запросы на выполнение задач трех типов — Т₁, Т₂ и Т₃, каждая для своего процессора. Запрос можно представить записью

на языке Pascal:

Type

TInquiry= record

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

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

T: Byte;{тип задачи 1 — Т₁, 2 — Т₂, 3 — Т₃}

end;

на языке C:

typedef struct TInquiry

{

char Name[10]; // Имя запроса

unsigned Time; // Время обслуживания

char T; // Тип задачи: 1 — Т₁, 2 — Т₂, 3 — Т₃

};

Поступающие запросы ставятся в очередь. Если в «голове» очереди находится задача Ti и процессор Ti свободен, то распределитель ставит задачу на выполнение в процессор Pi, а если процессор Pi занят, то распределитель отправляет задачу в стек и из очереди извлекается следующая задача. Если в вершине стека находится задача, процессор которой в данный момент свободен, то эта задача извлекается и отправляется на выполнение.

6. Система состоит из трех процессоров P₁, P₂, P₃, очереди F, стека S и распределителя R (рис.11). В систему поступают запросы на выполнение задач трех типов — Т₁, Т₂ и Т₃, каждая для своего процессора. Запрос можно представить записью

на языке Pascal:

Type

TInquiry= record

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

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

T: Byte;{тип задачи 1 — Т₁, 2 — Т₂, 3 — Т₃}

end;

на языке C:

typedef struct TInquiry

{

char Name[10]; // Имя запроса

unsigned Time; // Время обслуживания

char T; // Тип задачи: 1 — Т₁, 2 — Т₂, 3 — Т₃

};

Поступающие запросы ставятся в очередь. Если в «голове» очереди находится задача T_i и процессор Р_i свободен, то распределитель ставит задачу на выполнение в процессор P_i, а если процессор P_i занят, то распределитель отправляет задачу в стек и из очереди извлекается следующая задача. Задача из стека поступает в соответствующий ей свободный процессор только тогда, когда очередь пуста.

7. Система состоит из двух процессоров P₁ и P₂, трех очередей F₁, F₂, F₃ и стека (рис.12).

Рис.12. Система задач 7 и 10

В систему могут поступать запросы на выполнение задач трех типов — Т₁, Т₂, Т₃. Задача типа Т₁ может выполняться только процессором P₁. Задача типа Т₂ может выполняться только процессором P₂. Задача типа Т₃ может выполняться любым процессором. Запрос можно представить записью

на языке Pascal:

Type

TInquiry= record

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

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

T: Byte;{тип задачи 1 — Т₁, 2 — Т₂, 3 — Т₃}

end;

на языке C:

typedef struct TInquiry

{

char Name[10]; // имя запроса

unsigned Time; // время обслуживания

char T; // тип задачи: 1 — Т₁, 2 — Т₂, 3 — Т₃

};

Поступающие запросы ставятся в соответствующие типам задач очереди. Если очередь F₁ не пуста и процессор P₁ свободен, то задача из очереди F₁ поступает на обработку в процессор P₁. Если процессор Р₁ обрабатывает задачу типа Т₃, а процессор Р₂ свободен и очередь F₂ пуста, то задача из процессора Р₁ поступает в процессор Р₂, а задача из очереди F₁ в процессор Р₁, если же процессор Р₂ занят или очередь F₂ не пуста, то задача из процессора Р₁ помещается в стек.

Если очередь F₂ не пуста и процессор P₂ свободен, то задача из очереди F₂ поступает на обработку в процессор P₂. Если процессор Р₂ обрабатывает задачу типа Т₃, а процессор Р₁ свободен и очередь F₁ пуста, то задача из процессора Р₂ поступает в процессор Р₁, а задача из очереди F₂ — в процессор Р₂, если же процессор Р₁ занят или очередь F₁ не пуста, то задача из процессора Р₁ помещается в стек.

Если очередь F₃ не пуста и процессор P₁ свободен, и очередь F₁ пуста или свободен процессор Р₂ и очередь F₂ пуста, то задача из очереди F₃ поступает на обработку в свободный процессор. Задача из стека поступает на обработку в свободный процессор Р₁, если очередь F₁ пуста, или в свободный процессора Р₂, если очередь F₂ пуста.

8. Система состоит из двух процессоров P₁ и P₂ и двух очередей F₁, F₂ и стека S (рис.13). В систему могут поступать запросы на выполнение задач двух типов — Т₁ и Т₂. Задача типа Т₁ может выполняться только процессором P₁. Задача типа Т₂ может выполняться любым процессором.

Запрос можно представить записью

на языке Pascal:

Type

TInquiry= record

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

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

T: Byte; {тип задачи 1 — Т₁, 2 — Т₂}

end;

на языке C:

typedef struct TInquiry

{

char Name[10]; // имя запроса

unsigned Time; // время обслуживания

char T; // тип задачи 1 — Т₁, 2 — Т₂

};

Рис.13. Система задачи 8

Поступающие запросы ставятся в соответствующие типам задач очереди. Если очередь F₁ не пуста и процессор P₁ свободен, то задача из очереди F₁ поступает на обработку в процессор P₁. Если процессор Р₁ обрабатывает задачу типа Т₂, а процессор Р₂ свободен, то задача из процессора Р₁ поступает в процессор Р₂, а задача из очереди F₁ в процессор Р₁, если же процессор Р₂ занят, то задача из процессора Р₁ помещается в стек.

Если очередь F₂ не пуста и процессор P₂ свободен, то задача из очереди F₂ поступает на обработку в процессор P₂. Если процессор Р₂ занят, а процессор Р₁ свободен и очередь F₁ пуста, то задача из очереди F₂ поступает в процессор Р₁, а задача из стека поступает на обработку в свободный процессор Р₂, если F₂ пуста, или в свободный процессор Р₁, если очередь F₁ пуста и задачу нельзя поместить в процессор Р₂.

9. Система состоит из двух процессоров P₁ и P₂ и трех очередей F₁, F₂, F₃ и стека (рис.14).

Рис.14. Система задачи 9

В систему могут поступать запросы на выполнение задач двух типов — Т₁ и Т₂. Задача типа Т₂ обрабатывается процессором P₂. Задача типа Т₁ сначала обрабатывается процессором P₁, затем результат обработки (Т₁`) обрабатывается процессором Р₂.

Запрос можно представить записью

на языке Pascal:

Type

TInquiry= record

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

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

Time1: Word; {время обработки

процессором Р₁. Для задач

типа Т₂ Time1=0}

Time2: Word; {время обработки

процессором Р₂}

end;

на языке C:

typedef struct TInquiry

{

char Name[10]; // имя запроса

char T; // тип запроса

unsigned Time1; /* время обработки

процессором Р₁. Для задач

типа Т₂ Time1=0 */

unsigned Time2; /* время обработки

процессором Р₂ */

};

Поступающие запросы на выполнение задач типа Т₁ и Т₂ ставятся в соответствующие типам задач очереди. Результат обработки Т₁` задачи Т₁ процессором Р₁ ставится в очередь F₃. Если очередь F₁ не пуста и процессор P₁ свободен, то задача из очереди F₁ поступает на обработку в процессор P₁.

Если очередь F₃ не пуста и процессор P₂ свободен, то задача из очереди F₃ поступает на обработку в процессор P₂. Если процессор Р₂ занят выполнением задачи типа Т₂, то она помещается в стек, а задача из очереди F₃ — в процессор Р₂. Задача из стека возвращается в процессор Р₂, если очередь F₃ пуста. Задача из очереди F₂ поступает на обработку в процессор P₂, если он свободен и очередь F₃ и стек пусты.

10. Система состоит из двух процессоров P₁ и P₂, трех очередей F₁, F₂, F₃ и стека (см. рис.12). В систему поступают запросы. Запрос можно представить записью

на языке Pascal:

Type

TInquiry= record

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

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

P: Byte;{приоритет задачи 0 — высший,

1 — средний, 2 — низший}

end;

на языке C:

typedef struct TInquiry

{

char Name[10]; // имя запроса

unsigned Time; // время обслуживания

char P; /* приоритет задачи: 0 — высший,

1 — средний, 2 — низший */

};

Поступающие запросы ставятся в соответствующие приоритетам очереди. Сначала обрабатываются задачи из очереди F₁. Задача из очереди F₁ поступает в свободный процессор P₁ или P₂, если оба свободны, то в P₁. Если очередь F₁ пуста, то обрабатываются задачи из очереди F₂. Задача из очереди F₂ поступает в свободный процессор P₁ или P₂, если оба свободны, то в P₁. Если очереди F₁ и F₂ пусты, то обрабатываются задачи из очереди F₃. Задача из очереди F₃ поступает в свободный процессор P₁ или P₂, если оба свободны, то в P₂. Если процессоры заняты и поступает задача с более высоким приоритетом, чем обрабатываемая в одном из процессоров, то задача из процессора помещается в стек, а поступающая — в процессор. Задача из стека поступает в один из освободившихся процессоров, если все задачи с более высоким приоритетом уже обработаны.

11. Система состоит из двух процессоров Р₁ и Р₂, двух стеков S₁ и S₂ и четырех очередей F₁, F₂, F₃, F₄ (рис.15).

Рис.15. Система задачи 11

В систему могут поступать запросы на выполнение задач двух приоритетов — высший (1) и низший (2). Задачи сначала обрабатываются процессором P₁, затем P₂. Запрос можно представить записью

на языке Pascal:

Type

TInquiry= record

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

Р: Byte; {приоритет}

Time1: Word; {время выполнения задачи процессором P₁}

Time2: Word; {время выполнения задачи процессором P₂}

end;

на языке C:

typedef struct TInquiry

{

char Name[10]; // Имя запроса

char Р; // Приоритет

unsigned Time1; /* Время выполнения

задачи процессором P1 */

unsigned Time2; /* Время выполнения

задачи процессором P2 */

};

Запросы на выполнение задач высшего приоритета ставятся в очередь F₁, а поступающие с процессора Р₁ — в очередь F₃. Запросы на выполнение задач низшего приоритета, поступающие с генератора задач, ставятся в очередь F₂, а поступающие с процессора Р₁ — в очередь F₄.

Процессор Р₁ обрабатывает запросы из очередей F₁ и F₂, а процессор Р₂ — из очередей F₃ и F₄. Процессор сначала обрабатывает задачи из очереди задач с высшим приоритетом, затем из очереди задач с низшим приоритетом. Если процессор выполняет задачу с низшим приоритетом и приходит запрос на выполнение задачи с высшим приоритетом, то выполняемая задача помещается в соответствующий процессору стек, а пришедшая задача — в процессор. Задача из стека возвращается в процессор, если все задачи большего приоритета обработаны.