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

Очередь. Очередь представляет собой особым образом сконфигурированный список с указателями. Она называется также буфером первым-вошел-первым-вышел (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 */
/********************************************************************/