© Copyright 2006, 2007 Грибов Игорь, e-mail: gribov@depni.sinp.msu.ru
Изменения в версиях. О процессах с любовью. Другим путем. Программное решение.
Полная версия раздела задается в виде: версия.подверсия.выпуск.
Номер версии увеличивается при появлении глав, затрагивающих не рассмотренные ранее вопросы. Названия этих глав выносятся в оглавление раздела. Подверсия увеличивается, когда в существующие главы добавляются новые абзацы, рисунки, либо значительно перерабатывается имеющийся материал, существенно изменяя содержание главы. А при внесении лишь незначительных правок в существующие главы увеличивается номер выпуска.
Версия 1.1.1. В главе «Программное решение» уточнено описание работы функции send_data() при условии ее периодического асинхронного вызова.
Версия 1.2.0. Приведена новая версия функции write_data(dt, priority)в главе «программное решение».
Задача централизованного управления доступом программ к главному разделяемому ресурсу ЭВМ – процессору была успешно решена в 70-х годах XX века. Для этого был придуман механизм процессов. Его основная идея заключается в том, что в системе имеется некоторое ядро, называемое диспетчером или планировщиком, которое обладает возможностью переключения контекстов выполняемых заданий. Причем диспетчер не просто распределяет их очередность в соответствии с установленными приоритетами, но может принудительно прерывать выполнение одних задач и запускать либо продолжать выполнение других. В современных операционных системах общего назначения период работы диспетчера и, соответственно, темп переключения контекста процессов составляет от одной до десяти миллисекунд.
Помимо функций управления очередностью выполнения, в многозадачных системах поддерживается механизм разграничения доступа к общим ресурсам ЭВМ: областям памяти, портам ввода-вывода и др. Такая изоляция процессов от системных ресурсов и друг от друга позволяет существенно повысить общую надежность системы. Если процесс пытается получить доступ к запрещенным для него ресурсам, его выполнение может быть прекращено. А когда некоторый общий ресурс оказывается занят, то с помощью механизма взаимных исключений (mutexes) выполнение процесса приостанавливается до освобождения этого ресурса. Практически все великие операционные системы прошлого: MVC от IBM, DECовская VAX/VMS и другие обеспечивали «мультипрограммирование с произвольным числом процессов».
В схеме работы диспетчера, приведенной на рисунке, изначально выполняется наиболее ранний процесс 1, которому необходим доступ к некоторому разделяемому ресурсу. До его получения процесс устанавливает mutex, блокирующий доступ к ресурсу со стороны других процессов. В момент времени А возникает процесс 2 с более высоким приоритетом, которому нужен доступ к тому же самому ресурсу. Планировщик начинает его выполнение, но процесс 2 не может продвинуться далее момента Б, поскольку требует доступа к занятому разделяемому ресурсу. Поэтому он ставится в состояние ожидания (блокируется на mutex-e) и продолжается выполнение процесса 1. В момент времени В порождается высокоприоритетный процесс 3, которому не нужен доступ к занятому ресурсу. Поэтому диспетчер вновь приостанавливает выполнение процесса 1 и переключается на процесс 3. Отработав его до конца, он возвращается к процессу 1, который выполняется до момента освобождения разделяемого ресурса Г. Далее с точки Б возобновляется выполнение процесса 2, который может теперь захватить разделяемый ресурс. После его завершения окончательно выполняется процесс 1. Наконец, очередь доходит до процесса 4. Такая схема работы планировщика является упрощенной, но вполне отражает основные свойства алгоритмов диспетчеризации. В практических реализациях планировщик может выполнять сразу несколько заданий одного приоритета, выделяя каждому из них некоторый квант времени. Кроме того, с целью избежать неопределенно длительного ожидания, диспетчер может уделять некоторое внимание низкоприоритетным процессам, даже когда в системе имеются задания более высокого приоритета.
В мультипрограммной системе процессом становится обычный законченный исполняемый модуль или файл программы. Алгоритм активации процесса не значительно отличается от обычного запуска программы, например, из командой строки операционной системы. Для этого сначала создается копия текущего - родительского процесса (вызов fork()), затем она подменяется на код нового - дочернего процесса, который запускается на выполнение (вызов exec(...)). Такой механизм позволяет дочернему процессу унаследовать большинство ресурсов родительского, не нарушая общую политику прав и обязанностей всей системы. Иногда оба эти действия объединяются в одном вызове “метания икры” spawn(...).
Помимо чисто технологических заслуг, изобретение процессов оказало решающее влияние на саму возможность проектирования больших операционных систем и приложений. Каждая задача-процесс теперь может быть разработана и отлажена автономно, отдельным творческим коллективом. А механизм разграничений, поддерживаемый ядром операционной системы, позволяет достаточно безопасно запускать эти процессы, не опасаясь краха всей системы при ошибках в отдельных задачах. Таким образом, появилась возможность существенно наращивать возможности систем, исправлять ошибки, вносить изменения не прибегая к новой сборке всей системы в целом, а заменяя лишь модули тех или иных задач-процессов.
Технология процессов оказалась столь привлекательной, что вскоре – к середине 80-х - была масштабирована. Стало возможным многопоточное исполнение отдельных модулей внутри процессов. Такие потоки изначально получили название «легковесных процессов», но вскоре - и уже надолго - стали именоваться нитями (threads). Многопоточность проникла и во встраиваемые приложения, где используются сравнительно компактные операционные системы реального времени. С помощью нитей, в частности, можно переложить решение практически всех проблем доступа к разделяемым ресурсам на плечи операционной системы. Например, для каждого запроса передачи данных в некоторое устройство может быть создана отдельная нить. Правда, эффективность такого решения для систем реального времени довольно невысока. А учитывая, что само применение операционных систем в микроконтроллерах оправдано далеко не во всех случаях, целесообразно поискать другие пути решения проблемы. Далее в этой главе приведен алгоритм, обеспечивающий организацию доступа к единому разделяемому ресурсу разно-приоритетных асинхронно возникающих объектов (сообщений).
На рисунке показана схема организации асинхронного доступа разно-приоритетных объектов (сообщений, данных) к некоторому разделяемому ресурсу. В практических приложениях таким ресурсом может оказаться например, порт вывода данных или канал доступа к сети.
Для реализации алгоритма создается линейный набор (кэш) буферов, обеспечивающих оперативное хранение данных. Доступ к каждому буферу защищен отдельным семафором. Приоритет буфера определяется его размещением относительно начала кэша. Соответственно, при записи объекта более высокого приоритета поиск свободного буфера начинается левее (по рисунку). В нашем случае занятый буфер 4 оказался соответствующим приоритету сообщения. Поэтому объект заносится в следующий свободный буфер 5. Непосредственно после записи предпринимается попытка передачи всех накопленных данных в порт вывода I/O. При этом буферы проверяются на предмет наличия сообщений начиная с максимального приоритета (по рисунку слева направо). Поскольку операция вывода объектов инициируется асинхронно, она также защищена семафором. А в связи с тем, что любая отправка данных в порт I/O может оказаться безуспешной, осуществляется периодическое (по таймеру) сканирование кэша и до-вывод оставшихся в нем данных. В противном случае сообщения могли бы застрять в буфере как минимум до записи очередного объекта, то есть на неопределенное время.
Алгоритм асинхронного сигналобезопасного доступа сообщений различного приоритета к разделяемому ресурсу приведем на примере программы вывода данных. Упрощенный вариант этой программы можно найти главе "Критические разделяемые ресурсы".
#define CACHE_SIZE 8 // Число буферов в кэше (не менее 5)
#define PRIORITY_2 2 // Пороговый приоритет сообщения (минимальный)
#define PRIORITY_4 4
#define PRIORITY_7 7 // Пороговый приоритет сообщения (максимальный)
#define WRITE_ATTEMPTS 50 // Максимальное число попыток записи данных
#define WRITE_DELAY 20000 // Временной интервал между попытками записи данных (мкс)
#define ERROR -1 // Код ошибки
#define OK 1 // Код нормального завершения
typedef char int8;
typedef unsigned char unsigned8;
typedef short int16;
typedef unsigned short unsigned16;
typedef int int32;
typedef unsigned int unsigned32;
typedef struct {
unsigned8 data_1;
unsigned16 data_2;
int32 data_3;
} data; // Структура данных сообщения
typedef struct {
int16 busy;
data dt;
} cachedata; // Структура данных буфера – дополнена семафором busy
cachedata cache[CACHE_SIZE]; // Кэш-буфер. Номер буфера = его индекс + 1
int16 sem_send, flag_send; // Семафор и флаг отправки данных
int32 sleep_cnt; // Счетчик времени задержки
void micro_sleep(unsigned32 microseconds) // ms_0
{
sleep_cnt = (microseconds / 10000) + 1; // ms_2
while (sleep_cnt > 0);
}Функция micro_sleep(...) обеспечивает временную задержку с точностью до периода вызова нижеприведенной функции periodic(). Время задержки задается в микросекундах. В строке [ms_2] при вычислении начального значения счетчика времени задержки предполагается, что период равен 10 миллисекундам. Такая реализация функции задержки уместна в приложениях без использования операционной системы. Если же ОС поддерживает функции “засыпания”: sleep(...), nanosleep(...) и т.п., целесообразно пользоваться именно этими функциями.
int16 data_out(data *dt)
{
return OK;
return ERROR;
}Функция отправки data_out(dt)осуществляет непосредственный вывод данных в гнездо, регистр, порт и т.п. Эта функция должна поддерживать лишь транзакционную сигналобезопасность и возвращать код успешного завершения OK либо ошибки ERROR.
void send_data(void) // sd_0
{
unsigned16 cnt;
do { // sd_4
flag_send = 0; // sd_5
sem_send++; // sd_6
if (sem_send == 0) { // sd_7
for (cnt = 0; cnt < CACHE_SIZE; cnt++) { // sd_8
if (flag_send != 0) break; // sd_9
if (cache[cnt].busy >= 0) { // sd_10
if (data_out(&cache[cnt].dt) == OK) { // sd_11
cache[cnt].busy = -1; // sd_12
} else break; // sd_13
}
}
}
sem_send--; // sd_17
} while (flag_send != 0); // sd_18
flag_send = 1; // sd_19
}Функция send_data()осуществляет приоритетный вывод данных из буферов кэша. Поскольку она работает с разделяемыми ресурсами (вывод данных [sd_11] и освобождение буфера [sd_12]), повторно-входимое обращение к циклу вывода [sd_8] не допустимо. Безусловная сигналобезопасность функции поддерживается блокирующим семафором sem_send [sd_6, sd_17], который также используется для закрытия доступа к кэшу на время выполнения критической секции записи данных в write_data(dt, priority). При выводе сообщений производится линейный просмотр кэша (цикл [sd_8]) и при обнаружении заполненного буфера [sd_10] предпринимается попытка отправки данных [sd_11]. Если она завершается успешно, соответствующий буфер освобождается [sd_12]. При неудачной отправке данных вывод остальных буферов не производится [sd_13]. В качестве флага заполненности используется семафор сигналобезопасного доступа к соответствующему буферу. При освобождении буфера этот семафор устанавливается в открытое состояние явно – операцией присваивания [sd_12].
Для обеспечения приоритетного вывода данных, поступающих во время выполнения критической секции функции (от [sd_6] до [sd_17]) служит внешний цикл на основе флага flag_send. Этот флаг устанавливается [sd_19] после любого обращения к send_data(), обеспечивая внешнее зацикливание [sd_4, sd_18] критической секции вывода данных. Причем состояние этого флага контролируется не только по окончании полного цикла просмотра буфера [sd_18], но и внутри этого цикла [sd_9]. Таким образом, при записи в начало кэша нового сообщения цикл [sd_8] прерывается и будет возобновлен с первого буфера, то есть с сообщений высокого приоритета.
Отправка данных с помощью функции data_out(dt) [sd_11, sd_13] может завершиться безуспешно. Поэтому следует периодически возобновлять попытки вывода – даже при отсутствии новых данных. В противном случае уже записанные данные могут “зависнуть” в кэше на неопределенное время – до очередного обращения к функции write_data(dt, priority). Периодический асинхронный вызов функции send_data(), не обусловленый поступлением в кэш новых данных, приводит к дополнительным особенностям ее поведения. Если вызов оказывается повторно-входимым, после его завершения устанавливается флаг flag_send и внутренний цикл [sd_8] прерывается оператором [sd_9]. Соответственно, внешний цикл [sd_4, sd_18] возобновляет просмотр кэша с начала даже при отсутствии новых данных. А в некоторых случаях, например, при обращении к send_data() после открытия семафора [sd_17], но до проверки флага [sd_18] произойдет дополнительное “холостое” выполнение внешнего цикла. Следует также отметить, что при штатной работе функции отправки данных data_out(dt) практически все периодические обращения к send_data() оказываются “холостыми”. Это, однако, не является основанием для отмены алгоритма, по сути обеспечивающего вывод данных в режиме жесткого реального времени с максимальной задержкой, определяемой периодом обращения к функции send_data().
int16 write_data(data *dt, unsigned16 priority) // wd_0
{
unsigned16 cnt, wrac, cabg;
cabg = 0; // wd_4
if (priority <= PRIORITY_2) cabg += 4; // wd_5
else if (priority <= PRIORITY_4) cabg += 2; // wd_6
else if (priority <= PRIORITY_7) cabg += 1; // wd_7
wrac = WRITE_ATTEMPTS; // wd_8
do { // wd_9
sem_send++; // wd_10
for (cnt = cabg; cnt < CACHE_SIZE; cnt++) { // wd_11
cache[cnt].busy++; // wd_12
if (cache[cnt].busy == 0) { // wd_13
cache[cnt].dt = *dt; // wd_14
sem_send--; // wd_15
send_data(); // wd_16
return OK; // wd_17
}
cache[cnt].busy--; // wd_19
}
sem_send--; // wd_21
if (sem_send != -1) break; // wd_22
send_data(); // wd_23
micro_sleep(WRITE_DELAY); // wd_24
wrac--;
} while (wrac > 0); // wd_26
return ERROR; // wd_27
}Повторно-входимая функция записи данных write_data(dt, priority) производит заполнение кэша разно-приоритетными сообщениями. Именно эта функция выполняет роль прикладного интерфейса (API) для асинхронного доступа к системе вывода данных.
Начальный номер буфера для занесения сообщения определяется его приоритетом [wd_4...wd7]. Сообщения, имеющие приоритет от нуля до PRIORITY_2 включительно, записываются в пятый и последующие буферы кэша [wd_5]. Для данных с приоритетами свыше PRIORITY_2 и до PRIORITY_4 доступны буферы, начиная с третьего [wd_6]. Сообщения, имеющие приоритет свыше PRIORITY_4, но не более PRIORITY_7, размещаются начиная со второго буфера [wd_7]. Наконец, для записи данных с приоритетом, превышающим PRIORITY_7, подключается первый буфер кэша [wd_4]. Используемые в [wd_5...wd7] величины смещения номера начального буфера подразумевают, что полное число буферов в кэше - CACHE_SIZE - должно быть не менее пяти.
Параметр WRITE_ATTEMPTS [wd_8] определяет максимальное число попыток записи в случае, если в кэше не осталось свободного места. В такой ситуации производится вывод данных [wd_23] и по истечении промежутка времени WRITE_DELAY микросекунд [wd_24] вновь осуществляется поиск свободного буфера (цикл [wd_9..wd_26]). Таким образом, полное время, в течение которого предпринимаются попытки записи данных, составляет не менее WRITE_DELAY*WRITE_ATTEMPTS микросекунд. Если за это время ни один подходящий буфер так и не освободился, функция завершается с кодом ошибки ERROR [wd_27]. Оператор [wd_22] облегчает решение проблемы, возникающей при повторном обращении к функции записи данных, когда заняты все доступные буферы. В этом случае семафор sem_send окажется в закрытом состоянии, поскольку его инкремент осуществляется два или более раз [wd_10]. В результате, все попытки вывести накопленные в кэше данные [wd_23] окажутся безуспешными. Цикл [wd_9..wd_26] будет выполняться без какого-либо положительного эффекта, не позволяя отправить даже высоко приоритетные сообщения.
Доступ к каждому буферу осуществляется сигналобезопасно с использованием семафора [wd_12, wd_13, wd_19]. Функция просматривает кэш, начиная с буфера, номер которого зависит от приоритета сообщения (цикл [wd_11]). При обнаружении свободного буфера [wd_13] он заполняется данными [wd_14], а его семафор остается в закрытом состоянии. После этого осуществляется попытка немедленного вывода данных [wd_16] и возвращается код нормального завершения OK. Обратим внимание на использование в функции write_data(dt, priority) семафора блокирования вывода данных sem_send [wd_10, wd_15, wd_21]. Поскольку вызов функции вывода send_data() может осуществляться асинхронно по отношению к функции записи, нужно предотвратить некорректное использование разделяемых ресурсов. Так, после выполнения попытки захвата буфера [wd_12] и до фактической записи данных [wd_14] этот буфер не может считаться готовым для вывода, несмотря на значение флага busy, соответствующее заполненному буферу. Кроме того, если вызов send_data() произойдет непосредственно до семафорной операции [wd_19], значение семафора станет меньше минус 1 и данный буфер будет постоянно блокирован.
void periodic(void) // pr_0
{
if (sleep_cnt > 0) sleep_cnt--; // pr_2
send_data(); // pr_3
} Функция periodic() активируется периодическим таймером и занимается решением двух задач. В [pr_2] обслуживается счетчик времени задержки, а в [pr_3] производится до-вывод данных (см. рисунок в Другим путем и описание функции send_data()). Поскольку send_data() является безусловно сигналобезопасной, ее вызовы могут производиться асинхронно, в том числе по сигналу или прерыванию таймера.
void init_io(void) // in_0
{
unsigned16 cnt;
sleep_cnt = 0;
sem_send = 0; // in_5
for (cnt = 0; cnt < CACHE_SIZE; cnt++) cache[cnt].busy = -1; // in_6
sem_send = -1; // in_7
}Функция (пере)инициализации init_io() открывает семафоры буферов данных [in_6] и вывода данных [in_7]. На время переинициализации вывод данных блокируется семафором sem_send [in_5]. Вызов init_io() должен выполняться только извне по отношению к функциям записи и вывода данных, например, из монитора прикладной программы. Данные, записанные во время прохождения переинициализации могут быть утеряны.