Встраиваемые системы. Проектирование приложений на микроконтроллерах семейства 68HC12/HCS12 с применением языка С — страница 60 из 70

Вопрос: Что такое ядро?

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

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

8.3. Обзор концепций

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

Мы советуем вам возвратиться к предыдущим разделам и вспомнить о следующих понятиях: об указателях (глава 3), глобальных и локальных переменных (глава 3) и свойствах стеков и в прерываний 68HC12 (глава 4). Повторив эти разделы, вы можете вернуться к рассмотрению динамического распределения памяти.

8.3.1. Требования к динамическому распределению RAM

В главе 4 мы обсуждали систему памяти, встроенную в отладочную плату (EVB) контроллера B32, который предназначен прежде всего для однокристальных применений. Он включает в себя 32 Кб ПЗУ типа FLASH, 1 Кб статической оперативной памяти RAM и 768 байт стираемого по байту ПЗУ типа EEPROM для сохранения данных системы. Карта памяти для B32 EVB показана на рис. 8.1. Обратите внимание, что большая часть объема принадлежит флеш-памяти EEPROM, в то время как оперативная память (RAM) занимает только 1 Кб. Фактически же только 512 байтов, доступны для использования (от $0800 до $9FFF).

$0000 $01FF	Регистры ЦП
$0800 $0BFF	1 Кб RAM «на чипе»; • Код/данные пользователя; • Резервирована для D-Bug12 ($0A00-$0BFF)
$0D00 $0FFF	768 байт EEPROM «на чипе»; • Код/данные пользователя
$8000 $FFFF	FLASH EEPROM 32 Кб «на чипе»; • код D-Bug12 ($8000-$F67F); • Область, доступная пользователю ($F6C0–$F6FF); • Настройка функций D-Bug12 ($F680–$F6BF); • Код запуска D-Bug12 ($F700–$F77F); • Таблица вектора прерывания ($F780–$F7FF); • Расширение загрузчика ($F800-$FBFF); • EEPROM загрузчика ($FC00–$FFBF); • Векторы сброса и прерывания ($FFC0–$FFFF)

Рис. 8.1. Карта памяти микроконтроллера B32

Для чего же эта RAM используется? Прежде всего она используется для локальных переменных каждой функции. Переменные, помещенные в стек, доступны только при вызове функции. При выходе из функции переменные удаляются из стека, освобождая пространство памяти. Ясно, что можно достаточно быстро исчерпать объем стека, если ваш встроенный контроллер использует рекурсивную подпрограмму (вызываемую, например, для получения ряда Фибоначчи или операции вычисления факториала) или функцию с высокой степенью вложения. То есть при обращении к функции, которая снова вызывает функцию, и т.д. В этих ситуациях активны как все функции, так и связанные с ними локальные переменные.

Ключевой инструмент ОСРВ — использование таких абстрактных типов данных, как записи, списки с указателями и очереди. Обсудим их вкратце. Эти типы данных обычно используют динамическое распределение памяти RAM. Где мы можем взять RAM для этих типов данных? Если мы используем 512 байт как для абстрактных типов данных, так и для стека мы можем потенциально сталкиваться с «зависанием» структуры данных при переполнении стека или наоборот. Это может привести к катастрофическому сбою системы. Мы должны предотвратить это любой ценой. В идеале, мы должны выделить дополнительную память RAM в карте памяти B32. Было бы также полезно физически отделить эту память от памяти RAM на плате B32. Это позволило бы нам иметь отдельные пространства RAM для стека и динамической памяти. Но это не всегда возможно. Если же и стек и динамическая память постоянно находятся в одном и том же пространстве памяти, необходимо гарантировать, что не происходит подмены информации в процессе выполнения программы. Контроллер 68HC12 не обеспечивает автоматического контроля этой ситуации и исключение ее при программировании системы входит в вашу задачу.

В разделе 4.7.1 мы уже обсуждали систему памяти, размещенной на плате B32. На рис. 8.2 приведено схемное решение системы, с учетом которого мы можем использовать дополнительное пространство RAM. Настоятельно рекомендуем вам ознакомится с концепций расширения памяти у Pack и Barrett [2002, Ch. 8]. Здесь же мы только приводим схемное решение, не обсуждая проблем подключения памяти, электрической связи с помощью интерфейса и синхронизации. Хотя все они чрезвычайно важны, но при обсуждении динамического распределения памяти, без их рассмотрения можно обойтись.

Рис. 8.2. Подключение внешней памяти к микроконтроллеру при программировании

Прежде чем определить конкретные границы этого дополнительного пространства RAM, обеспечим их удобный расчет. Мы хотим определить область 16 Кб для статической оперативной памяти (SRAM) в карте памяти B32 EVB. Разместим эту память в ячейках от $4000 до $7FFF. Если бы это удалось, то все, к чему мы имели доступ на участке памяти — это 32 Кб×8 SRAM. Если мы заземлим старшую линию адреса этой памяти A[14], то старшие 16 Кб чипа памяти будут недоступны. Как мы уже упоминали в главе 4, PORTA обеспечивает мультиплексную линию данных D[7:0], и старшие разряды адреса A[15:8] в расширенных режимах работы МК. PORTB обеспечивает младшие разряды адреса A[7:0]. Мы используем адресную линию A[15:14] со схемой И-НЕ, чтобы создать активный низкий сигнал для SRAM памяти чипа.

Альтернативой расширению памяти является использование варианта HCS12 с большей дополнительной областью RAM. Обратитесь к различным доступным вариантам, описанным в разделах 1.3, 1.4 и 4.8. Эти варианты включают в себя RAM объемом от 4 до 12 Кб.

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

Вопросы для самопроверки

Вопрос: Какова цель применения схемы И-НЕ?

Ответ: Логический элемент И-НЕ переходит на низкий уровень и генерирует сигнал разрешения (CE) для SRAM памяти, когда A15 находится на низком , а A14 — на высоком уровне.

Вопрос: Какова цель применения микросхемы 74HC573?

Ответ: Эта микросхема действует как защелка при демультиплексировании линий адреса/данных от порта РA.

Вопрос: Каков промежуток адресов памяти RAM?

Ответ: От $4000 до $7FFF или 16 Кб RAM.

Вопрос: Каков размер SRAM памяти?

Ответ: Этот размер составляет 215 или 32К адресов с размещением одного байта в каждом адресе. Нам удается использовать только нижние 16 Кб памяти.

Вопрос: Какой вид будет иметь карта памяти после введения этих новых компонентов памяти.

Ответ: Карта памяти приведена на рис. 8.3.

$0000 $01FF	Регистры ЦП
$0800 $0BFF	1 Кб RAM «на чипе»; • Код/данные пользователя ($0800-$09FF); • Резервирована для D-Bug12 ($0A00-$0BFF)
$0D00 $0FFF	768 байт EEPROM «на чипе»; • Код/данные пользователя
$8000 $FFFF	FLASH EEPROM 32 Кб «на чипе»; • код D-Bug12 ($8000–$F67F); • Область, доступная пользователю ($F6C0–$F6FF); • Настройка функций D–Bug12 ($F680-$F6BF); • Код запуска D-Bug12 ($F700–$F77F); • Таблица вектора прерывания ($F780–$F7FF); • Расширение загрузчика ($F800–$FBFF); • EEPROM загрузчика ($FC00–$FFBF); • Векторы сброса и прерывания ($FFC0–$FFFF)

Рис. 8.3. Карта памяти B32, расширенная внешней флеш-памятью и RAM

8.3.2. Динамическое распределение памяти

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

Динамическое распределение памяти осуществляется с помощью команды распределения памяти malloc(). Эта команда содержится в файле заголовка stdlib.h, который является частью любого С компилятора. Команда malloc() обычно используется вместе с функцией sizeof(). Эта комбинация функций чрезвычайно полезна при динамическом распределении памяти. Общая форма этой комбинации функций:

Ptr = (variable_type)*malloc(sizeof(variable_type));

Большинство структур данных объявляется и распределяется с помощью этой методики. Когда переменная больше не нужна, пространство памяти используемое для нее, возвращается системе с помощью функции free(). Это наилучший способ динамического распределения памяти. Мы создаем переменные на ходу (в процессе выполнения программы), когда мы нуждаемся в них, и избавляемся от переменных, когда они больше не нужны.

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

Теперь, когда мы имеем два отдельных пространства RAM в нашей карте памяти, мы можем легко выделить одну из них для стека, а другую — для динамической памяти. Мы рекомендуем использование меньшего пространства для стека и большего для динамической памяти. В данном компиляторе имеются параметры настройки, конфигурируемые пользователем и позволяющие установить адрес начала для стека и области динамической памяти.

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

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

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

Структура. Мы будем использовать взаимозаменяемые термины запись и структура. Структуры позволяют программистам при разработке совокупности данных для спецификации, использовать другие основные типы данных. Это позволяет им следить за сложной информацией, которая может содержать различные типы данных. Например, если вы разрабатываете систему описи для автомобильного торгового агента, вы могли бы разработать следующую структуру основных данных для конкретного автомобиля, таких, как год выпуска, изготовитель, модель, номер идентификации транспортного средства (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  /*стандартные входные/выходные функции*/
#include  /*библиотека и распределение памяти */
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  /*стандартная библиотека ввода - вывода */
*include  /*стандартная библиотека динамического */
                    /*распределения*/
/*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  /*стандартная библиотека I/O */ 
#include  /*стандартная библиотека динамического распределения*/

/*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, в процессор встроен целый ряд аппаратных функций, связанных стеком, таких, как сохранение данных программного счетчика и ключевых регистров. В операционной системе реального времени нам нужен будет стек для каждой задачи, в котором мы будем сохранять контекст. Следовательно, мы должны иметь несколько стеков для работы с системами ОСРВ. В этих случаях, мы используем понятия о стеке, рассмотренные в этом разделе. Мы могли бы легко объявлять дополнительные стеки, использовав приведенный выше код. Кроме того, таким же образом может работать любой из стеков, которые мы объявим.

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

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