Структуры данных

В этом разделе мы проведем общий обзор структур данных, используемых в операционных системах, работающих в режиме реального времени. Мы выполним обзор каждой структуры данных отдельно и затем объединим их, чтобы выполнять различные операции внутри ОСРВ.

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

Рис. 8.4. Запись для автомобиля. Запись содержит поля данных, совокупность которых описывает автомобиль

Каждый из типов данных в записи называется полем. Мы объявляем запись или структуру, используя следующий синтаксис:

struct car {

int year; /* год производства* /

char make[10]; /*BWM, Hummer, Saturn */

char model[12]; /*купе, обратимый, SUV, пикап */

char VIN[10]; /* комбинация цифр, букв */

float mileage; /*показания счетчика: от 0 до 500, 000+ */

struct car *next; /*указатель на следующий автомобиль в списке*/

};

/*typedef обеспечивает компилятор an alternate??? */

typedef struct car ELEMENT; /*для типа переменной */

typedef ELEMENT *car_temp_ptr; /*определяет указатель на автомобиль*/

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

Структуры создаются с использованием динамических методов распределения памяти. Как мы уже упоминали, команда malloc() — предоставляет методику динамического распределения памяти, определяя соответствующий объем памяти для структуры данных. Например, чтобы создать новую запись для автомобиля, можно использовать следующий код:

сar_temp_ptr new_car_entry;

new_car_entry = (car_temp_ptr)malloc(sizeof(ELEMENT));

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

/* инициализация новых полей для структуры car */

new_car_entry–> year = 1981; /* год производства */

strcpy(new_car_entry–> make, " Chevy"); /*BWM, Hummer, Saturn */

strcpy(new_car_entry–> model, " Camaro"); /*купе, обратимый, SUV, пикап */

strcpy(new_car_entry–> VIN, " 12Z3 67"); /* комбинация цифр, букв*/

new_car_entry–> mileage = 37456; /*показания спидометра: от 0 до 500, 000+ */

new_car_entry–> next = NULL; /* определяет указатель на автомобиль */

Чтобы распечатать различные поля записи, мы могли бы использовать следующий код:

printf(" \nyear: %4d ", new_car_entry–> year); / *year mfg */

printf(" \nmake: %s ", new_car_entry–> make); /*car делает */

printf(" \nmodel: %s ", new_car_entry–> model); /*model*/

printf(" \nVIN: является ", new_car_entry–> VIN); /*VIN */

printf(" \nMileage: %6.of ", new_car_entry –> mileage); /*odometer reading*/

Поместим все эти части вместе с примером. Мы убедительно просим вас компилировать и выполнить этот код.

#include < stdio.h> /*стандартные входные/выходные функции*/

#include < stdlib.h> /*библиотека и распределение памяти */

void main(void) {

/*определение структуры */

struct car;

int year; /*год выпуска */

char make[10]; /*BWM, Hummer, Saturn*/

char model[12]; /*купе, обратимый, SUV, пикап */

char VIN[10]; /*комбинация цифр и букв*/

float mileage; /*показания одометра: от 0 до 500 000+ */

struct car *next; /*указатель на следующий автомобиль в списке */

typedef struct car ELEMENT;

typedef ELEMENT *car_temp_ptr;

car_temp_ptr new_car_entry; /*ввод записи для автомобиля*/

new_car_entry = (car_temp_ptr)malloc(sizeof(ELEMENT));

/*инициализация новых полей для автомобиля */

new_car_entry-> year = 1981; /*год изготовления*/

strcpy(new_car_entry–> make, " Chevy"); /*BWM, Hummer, Saturn */

strcpy(new_car_entry–> model, " Camaro");

/* купе, обратимый, SUV, пикап */

strcpy(new_car_entry–> VIN, " 12Z3 67");

/* комбинация цифр и букв */

new_car_entry–> mileage - 37456; /*показания одометра: 0 to 500, 000+*/

new_car_entry–> next - NULL; /*указатель на следующий автомобиль в списке*/

printf(" \nyear: %4d", new_car_entry–> year); /*год выпуска */

printf(" \nmake: %s", new_car_entry–> make); /*производитель */

printf(" \nmodel: %s", new_car_entry–> model); /*модель */

printf(" \nVIN: %s ", new_car_entry –> VIN); /*номер */

printf(" \nMileage: %6. Из ", new_car_entry-> mileage); /*показания одометра*/

}

Когда эта программа будет откомпилирована и выполнена, на экране вашего ПК появится следующее сообщение:

year: 1981

make: Chevy

model: Camaro

VIN: 12Z367

Mileage: 37456

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

Список с указателями. Список с указателями является мощной структурой данных, которая может быть создана, вставлена в программу или удалена из нее динамически в процессе выполнения программы. Список связей состоит из узлов, содержащих две части: часть данных и часть поля связи. Часть данных хранится информация об узле (или пункте) списка. Например, если мы должны были создать список автомобилей, готовых к продаже, частью данных для узла будет структура (или запись) car, которую мы разработали в предыдущем разделе. Полем связи был бы указатель (адрес памяти) следующую запись в списке. Начало списка названо головой (head). Конец списка называется хвостом (tail) и обозначается символом нуля (?) в поле связи. Это построение списка иллюстрируется на рис. 8.5. Здесь приведено объявление различных списков, позволяющих автомобильным дилерам проследить за состоянием парка автомобилей.

car_temp_ptr head_ptr; /*начало списка состояния автомобилей */

car_temp_ptr in_stock_list; / *автомобили в наличии */

car_temp_ptr repair_list; /*автомобили в ремонтных мастерских - не предназначены для продажи */

car_temp_ptr paint_shop_list; /*автомобили в мастерских покраски - не предназначены для продажи */

car_temp_ptr sold_list; /*проданные автомобили - не предназначены для продажи */

Мир автомобильных продаж очень динамичен. Автомобильные дилеры постоянно продают автомобили, занимаются их обменом, размещают автомобили в мастерских для ремонта, или даже производят перекрашивание автомобилей. Если нам необходимо создать список для каждого из этих действий, мы будем постоянно добавлять и удалять элементы в каждом из списков. Эти действия иллюстрируются на рис. 8.5в и 8.5г.

Рис. 8.5. Операции со списком a) список состоит из узла с данными и указателя, мента в список, г) удаление элемента

Чтобы вставить новый автомобиль в список, мы были бы должны найти соответствующее место для автомобиля в существующем списке. Например, если мы размещаем автомобили в алфавитном порядок, мы должны просматривать список, пока мы не найдем, соответствующее место чтобы вставить автомобиль в список, как показано на рис. 8.6. Как только соответствующая точка ввода найдена, указатель предшествующего узла должен быть изменен, чтобы указать на новый автомобиль, и указатель нового автомобиля должен быть изменен, чтобы указать на следующий автомобиль в списке.

Рис. 8.6. Список с указателями для текущего учета автомобилей

Когда автомобиль продан, он больше не доступен для продажи. Он должно быть затем быть удален из списка «для продажи». Для этого связь предшествующего автомобиля должна теперь указывать на последующий автомобиль. Автомобиль, который был продан, будет теперь действительно исключен из списка «для продажи» и может быть добавлен в список «проданные». Если бы у нас не было списка «проданные», мы могли бы освободить динамическую память, выделенную для этого автомобиля. Это осуществляется с помощью команды free(argument).

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

Рис. 8.7. Общие функции, связанные со списками с указателями

На рис. 8.7 показаны общие функции, связанные со списком с указателями. Код для каждой из этих функций приведен ниже:

/*********************************************************************

/*имя файла: linklist.с */

/*********************************************************************

/*включенные файлы*/

*include < stdio.h> /*стандартная библиотека ввода - вывода */

*include < stdlib.h> /*стандартная библиотека динамического */

/*распределения*/

/*global variables - глобальные переменные. Объявление этих переменных */

/*помещают в файл заголовка (header file). Они приведены здесь, */

/* чтобы иллюстрировать последовательность построения программы. */

/*определение структуры " автомобиль" */

struct car {

int year; /* год производства */

char make[10]; /*BWM, Hummer, Saturn */

char model[12]; /*купе, обратимый, SUV, пикап */

char VTN[10]; /*комбинация цифр, букв */

float mileage; /*показания спидометра: от 0 до 500, 000+*/

struct car *next; /*указатель на следующий автомобиль в списке */

};

/*определение указателя на автомобиль */

typedef struct car ELEMENT;

typedef ELEMENT *car_temp_ptr;

/*функции прототипов*/

void initialize_link_list(void);

void print_link_list(car_temp_ptr);

void insert_link_list(car_temp_ptr);

void delete_link_list(car_temp_ptr);

void search_link_list(car_temp_ptr);

/*переменные*/

/ " Создают списки, чтобы следить за состоянием автомобильного сервиса*/

car_temp_ptr in_stock_list; /* автомобили в продаже */

car_temp_ptr repair_list; /* автомобили в ремонт - не подлежат продаже*/

car_temp_ptr paint_shop_list; /*автомобили в покраске - не подлежат продаже*/

car_temp_ptr sold_list; /*проданные автомобили -- не подлежат продаже*/

car_temp_ptr new_car_entry; /*новый автомобиль для введения в список*/

int TRUE=1, FALSE=0; /*логические флаги */

void main(void) {

/*заполняет пустой список переменными NULL */

in_stock_list = NULL; /* автомобили в продаже */

repair_list = NULL; /* автомобили в ремонте - не подлежат продаже */

paint_shop_list = NULL; /* автомобили в покраске - не подлежат продаже*/

sold_list = NULL; /*проданные автомобили -- не подлежат продаже * /

new_car_entry = NULL;

initialize_link_list(); /*составление списка для продажи */

print_link_list(in_stock_list); /*print the list */

insert_link_list(in_stock_list); /*вставить новый автомобиль в список*/

print_link_list(in_stock_list); /*распечатать список */

delete_link_list(in_stock_list); /*удалить автомобиль из списка */

print_link_list(in_stock_list); /*распечатать список */

search_link_list(in_stock_list); /*поиск определенного пункта в списке */

}

/********************************************************************/

/*void initialize_link_list (car_temp_ptr): инициализирует автомобиль */

/* для списка продаж используя список.Отметим, что этот список */

/* с указателями был объявлен как глобальная переменная. */

/*********************************************************************

void initialize_link_list(void) {

car_temp_ptr new_car_entry1, new_car_entry2;

/*создает вход в список автомобилей */

new_car_entry = (car_temp_ptr)malloc(sizeof(ELEMENT));

/*инициализирует новые поля для ввода автомобиля в список*/

new_car_entry-> year = 1981; /*год выпуска */

strcpy(new_car_entry-> make, " Chevy"); /*BWM, Hummer, Saturn */

strcpy(new_car_entry-> model, " Camaro"); /*купе, обратимый, SUV, пикап*/

strcpy(new_car_entry-> VIN, " 12Z3 67"); /*комбинация цифр и букв */

new_car_entry-> mileage = 37456; /*показания одометра: от 0 до 500 000+*/

new_car_entry-> next = NULL; /*указатель на следующий автомобиль в списке*/

in_stock_list = new_car_entry;

new_car_entry1 = (car_temp_ptr) malloc(sizeof(ELEMENT));

/*инициализирует новые поля для ввода автомобиля в список*/

new_car_entry1-> year = 1974; /*год выпуска*/

strcpy(new_car_entry1-> make, " Ford"); /*BWM, Hummer, Saturn */

strcpy(new_car_entry1-> model, " Mustang11")/*купе, обратимый, SUV, пикап*/

strcpy(new_car_entry1-> VIN, " 3L265ST"); /*комбинация цифр и букв */

new_car_entry1-> mileage = 122456; /*показания одометра: от 0 до 500 000+ */

new_car_entry1-> next = NULL; /*указатель на следующий автомобиль в списке */

new_car_entry2 = (car_temp_ptr)malloc(sizeof(ELEMENT));

/*инициализирует новые поля для ввода автомобиля в список*/

new_car_entry2-> year = 1997; /*год выпуска*/

strcpy(new_car_entry2-> make, " Saturn"); /*BWM, Hummer, Saturn */

strcpy(new_car_entry2-> model, " SL1"); /*купе, обратимый, SUV, пикап */

strcpy(new_car_entry2-> VIN, " 234TH67"); /*комбинация цифр и букв */

new_car_entry2-> mileage = 140512; /*показания одометра: от 0 до 500 000+ */

new_car_entry2-> next = NULL; /*указатель на следующий автомобиль в списке*/

new_car_entry1-> next = new_car_entry2;

}

/********************************************************************/

/*print_link_list: печатает поля выделенного списка с указателями */

/********************************************************************/

void print_link_list(car_temp_ptr print_list) {

car_temp_ptr temp_ptr; /*объявляет текущий указатель */

printf(" \nCars available in stock for sale: ");

/*продвижение по списку */

for (temp_ptr=print_list; temp_ptr! = NULL; temp_ptr-temp_ptr-> next) {

printf(" \n\nyear: %4d, temp_ptr-> year); /*год выпуска*/

printf(" \nmake: %s", temp_ptr-> make); /*изготовитель*/

printf(" \nmodel: %s", temp_ptr-> model); /*модель*/

printf(" \nVIN: %S", temp_ptr-> VIN); /*номер*/

printf(" \nMileage: %6.0f", temp_ptr-> mileage); /*показания одометра*/

}

}

/********************************************************************/

/*insert_link_list (in_stock_list) - вставляют новый автомобиль в */

/* отмеченный список в алфавитном порядке */

/********************************************************************/

void insert_link_list(car_temp_ptr in_stock_list) {

car_temp_ptr new_car_entry, list, ptr;

int place_found;

list = in_stock_list;

/*создает ввод автомобиля */

new_car_entry = (car_temp_ptr) malloc(sizeof(ELEMENT));

/*инициализирует новые поля для ввода автомобиля в список */

new_car_entry-> year = 2002; /*год выпуска */

strcpy(new_car_entry-> make, " Hummer"); /*BWM, Hummer, Saturn*/

strcpy(new_car_entry-> model, " H2"); /*купе, обратимый, SUV, пикап */

strcpy(new_car_entry-> VTIM, " 73H2L7"); /*комбинация цифр и букв*/

new_car_entry-> mileage = 13; /*показания одометра: от 0 до 500 000+ */

new_car_entry-> next = NULL; /*указатель на следующий автомобиль в списке */

if (list==NULL) { /*вставка в пустой список */

list=new_car_entry;

} else {

/* вставка в первый элемент списка */

if (strcmp(new_car_entry-> make, list-> make) < 1) {

new_car_entry-> next=list;

list = new_car_entry;

} else /*вставка в непустой список */

{

ptr = list; /*определение позиции вставки */

place_found = FALSE;

while((ptr-> next! = NULL) & & (! place_found)) {

if (strcmp (new_car_entry-> make, ptr-> next-> make) > = 1) /*сравнение */

{

ptr=ptr-> next; /*продвижение по списку */

} else /*вставка после указателя */

{

place_found = TRUE;

}

}/*конец цикла while*/

/*переадресует указатель, чтобы */

/*закончить ввод в список */

new_car_entry-> next = ptr-> next;

ptr-> next - new_car_entry;

}/*конец else*/

}/*конец else*/

}/*конец insert_link_list*/

/********************************************************************/

/*delete_link_list (car_temp_ptr): */удаление отмеченных элементов */

/*из списка */

/********************************************************************/

void delete_link_list(car_temp_ptr in_stock_list) {

car_temp_ptr current, backup, temp; /*текущий указатель списка */

char delete_make[10];

/*определить поле make для удаления */

printf(" \n\nDelete car from for sale list.");

printf(" \nEnter make of car for deletion from list.");

scanf(" %s", delete_make);

/*инициировать указатели для поиска */

current = in_stock_list;

backup=NULL;

/*поиск записи, содержащих заданное значение make */

while (strcmp(current-> make, delete_make)! =0) {

backup = current;

current = current-> next;

}

/*Был удален автомобиль из первого элемента? */

if (backup == NULL){ /*удалить автомобиль из первого элемента */

in_stock_list = in_stock_list-> next;

} else { /*удалить элемент из списка */

backup-> next = current -> next;

}

free(current); /*перераспределить динамическую память*/

}

/********************************************************************/

/********************************************************************/

/*void search_link_list (car_temp_ptr) - найти запись с определенным */

/* значением поля make. Распечатать автомобили этого изготовителя. */

/********************************************************************/

void search_link_list(car_temp_ptr search_list) {

char search_make[10];

car_temp_ptr temp_ptr; /*объявить текущий указатель */

/*определить изготовителя для поиска */

printf(" \n\nSearch for car in stock.");

printf(" \nEnter make of car to search for in list. ");

scanf(" %s", search_make);

/*движение по списку */

for(temp_ptr-search_list; temp_ptr! =NULL; temp_ptr=temp_ptr-> next) {

if (strcmp(temp_ptr-> make, search_make) == 0) {

printf(" \n\nyear: %4d", temp_ptr-> year); /*год изготовления */

printf(" \nmake: %s", temp_ptr-> make); /*изготовитель */

printf(" \nmodel: %s", temp_ptr-> model); /*модель */

printf(" \nVIN: %s", temp_ptr-> VIN); /*номер */

printf(" \nMileage: %6.0f ", temp_ptr-> mileage);

/*считать показания одометра*/

}

}

}

/********************************************************************/

/********************************************************************/

После выполнения программы на дисплее появится следующее сообщение.

year: 1981

make: Chevy

model: Camaro

VIN: 12Z367

mileage: 37456

year: 1974

make: Ford

model: Mustang11

VIN: 3L265ST

mileage: 122456

year: 1997

make: Saturn

model: SL1

VIN: 234TH67

mileage: 140512

year: 1981

make: Chevy

model: Camaro

VIN: 12Z367

mileage: 37456

year: 1974

make: Ford

model: Mustang11

VIN: 3L265ST

mileage: 122456

year: 2002

make: Hummer

model: H2

VIN: 73H2L7

mileage: 13

year: 1997

make: Saturn

model: SL1

VIN: 234TH67

mileage: 140512

Удалены следующие автомобили из списка для продаж.

Введено поле make для удаления из списка – Hummer

year: 1981

make: Chevy

model: Camaro

VIN: 12Z367

mileage: 37456

year: 1974

make: Ford

model: Mustang11

VIN: 3L265ST

mileage: 122456

year: 1997

make: Saturn

model: SL1

VIN: 234TH67

mileage: 140512

Найден автомобиль в списке продаж.

Введенное поле make для поиска – Saturn

year: 1997

make: Saturn

model: SL1

VIN: 234TH67

mileage: 140512

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

Очередь. Очередь представляет собой особым образом сконфигурированный список с указателями. Она называется также буфером первым-вошел-первым-вышел (first-in first out — FIFO). Элементы добавляются в хвост очереди и извлекаются с головы, как показано на рис. 8.8. Вернемся к нашей автомобильной коммерческой аналогии. Как только вы приобретаете автомобиль, вы должны зарегистрировать его в департаменте транспортных средств. Я был там недавно с моим сыном, которому нужны было заменить водительские права. После нашего прихода мы встали в хвост очереди и стали ждать, пока нас обслужат. После короткого ожидания, мы достигли головы очереди и смогли получить требуемые права. Нас обслуживали в порядке прохождения очереди. Во время пика занятости, например, в утренние часы, в конце месяца — очередь в департаменте может быть очень длинной. В более свободное время она может быть совсем короткой. В обоих случаях мы видим, что очередь не имеет фиксированного числа элементов. Длина очереди или число элементов в ней, является переменной величиной и изменяется, в зависимости от действия программы.

Рис. 8.8. Структура данных очередь — «первым вошел–первым вышел»

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

Рис. 8.9. Круговая очередь

Стек. Стек — это структура данных последним вошел — первым вышел (last-in-first-out — LIFO), показанная на рис. 8.10. Она также может быть создана с помощью методов списка с указателями. Во встроенных контроллерных системах на базе 68HC12, стек — определенная пользователем часть RAM, в которой в течение нормального выполнения программы временно хранятся переменные, например содержимое какого-либо регистра. Верхняя часть стека в 68HC12 обычно определяется последней позицией RAM плюс один. Указатель вершины стека для 68HC12 содержит адрес последнего используемого расположения стека. Когда элемент помещают в стек, указатель вершины стека уменьшается на 1 (проводится операция декремента). Когда элемент извлекается из стека, указатель вершины стека увеличивается на 1 (операция инкремента). Когда программирование проводится на языке C, положение вершины стека является опцией компилятора. Если встроенная контроллерная система содержит только один стек, лучше всего просто использовать свойства, встроенные в процессор. Однако, как мы скоро увидим, в ОСРВ можем потребоваться несколько стеков, по одному для каждой задачи. В этом случае разработчику системы необходимо, чтобы обеспечить работу нескольких стеков. Если используются динамические методы распределения памяти, то несколько стеков создаются и используются в динамической памяти. Мы оставим разработку структуры данных стека, использующей динамические методы распределения памяти в качестве вашей домашней работы (задача 1 для самостоятельного исследования). Вместо этого, мы разработаем структуру стека с фиксированный размером массива. Стек с фиксированным массивом используется, когда размер стека известен и неизменен. Как мы скоро увидим, стеки с успехом могут используются в блоках управления задачами.

Рис. 8.10. Стек

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

• initialize_stack: инициализация стека;

• push: поместить элемент в стек;

• pull: извлечь элемент из стека;

• stack_empty: выяснить, не пуст ли стек. Это необходимо сделать до использования функции pull;

• stack_full: выяснить, не полон ли стек. Это необходимо сделать до использования функции push;

• print_stack: распечатать содержимое стека.

Основные операции стека показаны на рис. 8.11.

Рис. 8.11. Операции со стеком

Следующий программный код реализует стек с фиксированным массивом.

/********************************************************************/

/* имя файла: stack.с */

/********************************************************************/

/*включенные файлы*/

#include < stdio.h> /*стандартная библиотека I/O */

#include < stdlib.h> /*стандартная библиотека динамического распределения*/

/*global variables - объявляет глобальные переменные в header file. */

/* Они приведены здесь, чтобы иллюстрировать общее построение программы.*/

/*определение структуры*/

struct stack_struct {

int stack_top; /*следующая используемая позиция в стеке*/

int stack_item[10]; /*элемент, сохраненный в стеке с фиксированным размером */

}

typedef struct stack_struct stack; /*массив для распознавания имен различных переменных*/

typedef stack *stack_ptr; /*определение указателей на стек */

/*функции-прототипы*/

void initialize_stack(stack);

void push(stack*, int); /*Используется метод передачи параметра по ссылке*/

int pull(stack *); /* когда содержимое стека должно измениться */

int stack_empty(stack);

int stack_full(stack);

void print_stack(stack);

/*переменные*/

int YES=1, NO=0; /*логические флаги */

stack stack1; /*объявление стека */

char *filename;

FILE *outputfile;

void main(void) {

int response;

int stack_item;

/*печать результата в файл/

printf(" \n\nEnter a filename for output.");

scanf(" %s", filename);

outputfile = fopen(filename, " a");

initialize_stack(stack1);

response = stack_empty(stack1); /*вызов по значению */

response = stack_full(stack1);

print_stack(stack1);

push(& stack1, 11); /*вызов по ссылке */

push(& stack1, 12);

push(& stack1, 13);

push{& stack1, 14);

print_stack(stack1);

pull(& stack1);

pull(& stack1);

pull(& stack1);

pull(& stack1);

pull(& stack1);

fclose(outputfile); /*закрыть выходной файл */

}

/********************************************************************/

/*initialize_stack: установить указатель вершины стека в 0 */

/********************************************************************/

void initialize_stack(stack a_stack) {

a_stack.stack_top=0; /*установить указатель стека в 0*/

}

/********************************************************************/

/*stack_empty: возвращает ДА если стек пуст, и НЕТ в противном случае */

/********************************************************************/

int stack_empty(stack a_stack) {

fprintf(outputfile, " \n\nStack top: %d", a_stack.stack_top);

if (a_stack.stack_top == 0) /*проверить не пуст ли стек*/

{

fprintf(outputfile, " \nStack Empty! ");

return YES;

} else {

fprintf(outputfile, " \nStack is not empty.");

return NO;

}

}

/********************************************************************/

/*stack_full: возвращает ДА если стек полон, и НЕТ в противном случае */

/********************************************************************/

int stack_full(stack a_stack) {

if (a_stack.stack_top == 10) /*проверить не заполнен ли стек */

{ /*произвольный выбор предела стека */

fprintf(outputfile, " \n\nStack Full! ");

return YES;

} else {

fprintf(outputfile, " \n\nStack is not full.");

return NO;

}

}

/********************************************************************/

/*print_stack: печать текущего элемента (на вершине стека) */

/********************************************************************/

void print_stack(stack a_stack) {

int i;

if (! (stack_empty(a_stack)))/*проверить не пуст ли стек перед печатью*/

{ /*перейти к основанию стека перед печатью */

for(i = a_stack.stack_top; i> =0; i=i-1)

fprintf(outputfile, " \nStack item: %d", a_stack.stack_item[i]);

} else fprintf(outputfile, " \nCannot print - stack is empty! ");

}

/********************************************************************/

/*push(stack *, int): запись элемента в стек */

/********************************************************************/

void push(stack *a_stack, int item) {

fprintf(outputfile, " \n\nBefore push - stack pointer: %d",

a_stack-> stack_top);

if (! (stack_full(*a_stack))) /*проверка заполнения стека*/

/* перед записью элемента*/

{

a_stack-> stack_item[a_stack-> stack_top] = item;

fprintf(outputfile, " \nstack item after push: %d",

a_stack-> stack_item[a_stack-> stack_top]);

a_stack-> stack_top = a_stack-> stack_top + 1;

fprintf(outputfile, " \nstacktop after push: %d",

a_stack-> stack_top);

} else fprintf(outputfile, " \nCannot push - stack is full! ");

}

/********************************************************************/

/*pull(stack *): извлечение элемента из стека */

/********************************************************************/

int pull(stack *a_stack) {

int item;

fprintf(outputfile, " \n\nBefore pull - stack pointer: %d",

a_stack-> stack_top);

if (! (stack_empty(*a_stack))) /*проверка не пуст ли стек */

/*перед извлечением элемента*/

{

item = a_stack-> stack_item[a_stack-> stack_top-1];

fprintf(outputfile, " \nstack item pulled: %d", item);

a_stack-> stack_top = a_stack-> stack_top - 1;

fprintf(outputfile, " \nstacktop after pull: %d",

a_stack-> stack_top); return item;

} else fprintf(outputfile, " \nCannot pull - stack is empty! ");

}

/********************************************************************/

Мы показали работу этого примера на рис. 8.12. После выполнения этой программы будет выдан следующий код:

Рис. 8.12. Запись в стек и извлечение из стека

Stack top: 0

Stack Empty!

Stack is not full.

Stack top: 0

Stack Empty!

Cannot print - stack is empty!

Before push - stack pointer: 0

Stack is not full.

stack item after push: 11

stacktop after push: 1

Before push - stack pointer: 1

Stack is not full.

stack item after push: 12

stacktop after push: 2

Before push - stack pointer: 2

Stack is not full.

stack item after push: 13

stacktop after push: 3

Before push - stack pointer: 3

Stack is not full.

stack item after push: 14

stacktop after push: 4

Stack top: 4

Stack is not empty.

Stack item: 0

Stack item: 14

Stack item: 13

Stack item: 12

Stack item: 11

Before pull - stack pointer: 4

Stack top: 4

Stack is not empty

stack item pulled: 14

stacktop after pull: 3

Before pull - stack pointer: 3

Stack top: 3

Stack is not empty.

stack item pulled: 13

stacktop after pull: 2

Before pull - stack pointer: 2

Stack top: 2

Stack is not empty,

stack item pulled: 12

stacktop after pull: 1

Before pull - stack pointer: 1

Stack top: 1

Stack is not empty.

stack item pulled: 11

stacktop after pull: 0

Before pull - stack pointer: 0

Stack top: 0

Stack Empty!

Cannot pull - stack is empty!

Несколько стеков. Обычно система микропроцессора содержит один стек. Этот стек объявляется внутри RAM, и процессор имеет несколько функций для объявления положения стека (LDS), записи данных (PUSH), извлечение данных из стека (PULL) и т.д. Кроме того, как мы уже рассказывали в главе 4, в процессор встроен целый ряд аппаратных функций, связанных стеком, таких, как сохранение данных программного счетчика и ключевых регистров. В операционной системе реального времени нам нужен будет стек для каждой задачи, в котором мы будем сохранять контекст. Следовательно, мы должны иметь несколько стеков для работы с системами ОСРВ. В этих случаях, мы используем понятия о стеке, рассмотренные в этом разделе. Мы могли бы легко объявлять дополнительные стеки, использовав приведенный выше код. Кроме того, таким же образом может работать любой из стеков, которые мы объявим.

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

Основные понятия

Ранее в этой главе мы сказали, что ОСРВ — компьютерная операционная система, которая должна своевременно обрабатывать несколько событий при ограниченных ресурсах процессора. Наше исследование ОСРВ начинается с определения понятия задачи. Это потребует радикального изменения нашего понимания программ (сдвига парадигмы). При наличии в системе только одного последовательного процессора, мы можем рассматривать программу как последовательность шагов, которые процессор выполняет один за другим по определенному алгоритму. В ОСРВ, наша программа состоит из независимых, асинхронных (могущих появиться в любое время) взаимодействующих задач. И все они будут конкурировать за драгоценное (и ограниченное) время обработки. Наша программа состоит из механизмов, позволяющих следить за состоянием каждой задачи, планировать задачи для выполнения, и удостовериться, что каждая задача получает необходимую долю процессорного времени.

Мы начнем этот раздел, с получения хорошего описания того, что мы понимаем под задачей и как мы представляем ее в программе. Затем мы исследуем, как следить за состоянием каждой задачи и модифицировать его, используя блок управления задачами (task control block — TCB). Мы исследуем также, как отслеживается состояние другой системой информации, с помощью управляющих блоков устройства. Мы увидим, как диспетчер следит за состоянием всех задач и определяет, какая из задач является очередной. В заключение, мы также исследуем различные алгоритмы планирования, которые могут использоваться в ОСРВ.

8.4.1. Что такое задача?

Задача — это независимое, асинхронное действие, которое выполняется системой ОСРВ. Поскольку задачи асинхронны, мы не можем точно предугадать момент, когда они будут выполняться программой. Каждая задача может рассматриваться как маленькая, независимая программа, которая выполняет специфическое действие. Так как мы имеем несколько задач, конкурирующих за использование одного и того же процессора, задача должна иметь возможность сохранить контекст (ключевые значения регистров, счетчик программы, и т.д.). Эта информация резервируется на интервале выполнения другой задачи. Следовательно, каждая задача должна иметь свой стек для сохранения контекста. Даже если выполнение задачи прервано другой задачей, в конечном счете, его планируется завершить позднее.

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

Пример: В главе 7 был рассмотрен проект автономного робота, проходящего через неизвестный лабиринт. Этот робот, обнаруживая границы лабиринта с помощью инфракрасных локаторов, принимал решения, двигаться ли вперед или повернуть в необходимом направлении, чтобы пройти через лабиринт. При проходе через лабиринт робот должен был избежать земляных мин (магнитов в полу лабиринта). Как мы говорили, робот должен находить мины с помощью датчика Холла. Если робот обнаруживал магнит, он должен был остановиться, отъехать назад, и объехать мину. Робот был также оборудован ЖК дисплея (ЖКД), показывающим его текущее состояние в процессе выполнения программы.

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

• Функции инициализации ЖКД, ATD-преобразователя и системы широтно-импульсной модуляции (ШИМ);

• ATD-преобразование выходных сигналов ИК датчиков;

• Сравнение выходных сигналов ИК датчика с пороговыми уровнями обнаружения стенки;

• Алгоритм поворотов робота, позволяющий правильно изменить движение робота в ответ на выходные сигналы ИК датчиков;

• Функции, позволяющие осуществить поворот робота направо, налево и продолжить движение вперед;

• Метод обработки выходного сигнала датчика Холла;

• Функции, необходимые для выполнения объезда мины — остановка, задний ход, и объезд;

• Функции, обеспечивающие работу ЖКД.

Эти функции показаны в структуре программы (рис.8.13).

Рис. 8.13. Структура программы, управляющей роботом, проходящим лабиринт

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

Сценарий. Робот помещается в начальную точку неизвестного лабиринта, содержащего магнитные мины. Операционная система инициализирует ЖКД, ATD-конвертер и систему ШИМ. В главе 4, мы обсуждали требования инициализации для каждой из этих систем робота.

Как только инициализация закончена, робот начинает проход через неизвестный лабиринт, обрабатывая сигналы ИК датчиков и датчика Холла. Что получается, если робот получит сигналы о приближении к стенке одновременно с сигналом об обнаружении мины? Робот не сможет обрабатывать оба эти два события одновременно, поскольку располагает только одним процессором. Оба события являются критическими, хотя и не в равной степени. Если мы обрабатываем сначала информацию о стенках, робот избегает столкновения, но рискует подорваться на мине, если обработка информации о стенках не закончится достаточно быстро. С другой стороны, если мы сначала обрабатываем информацию о минах, считая эту задачу более приоритетной, мы подвергаемся риску возможного столкновения со стенками. К тому же оба события взаимосвязаны. Мы не хотим подорваться на мине, обрабатывая информацию о стенках, но и не хотим наткнуться на стенки объезжая мины.

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