Теория операционных систем



 

Кооперативная многозадачность

По-видимому, самой простой реализацией многозадачной системы была бы библиотека подпрограмм, которая определяет следующие процедуры.

  • struct Thread; В тексте будет обсуждаться, что должна представлять собой эта структура, называемая дескриптором нити.
  • Thread * ThreadCreate(void (*ThreadBody)(void)); Создать нить, исполняющую функцию ThreadBody.
  • void Threadswitch(); Эта функция приостанавливает текущую нить и активизирует очередную, готовую к исполнению.
  • void ThreadExit () ; Прекращает исполнение текущей нити.

Сейчас мы не обсуждаем методов синхронизации нитей и взаимодействия
между ними (для синхронизации были бы полезны также функции void
DeactivateThread(); И void ActivateThread(struct Thread *) ;). Нас интересует только вопрос: что же мы должны сделать, чтобы переключить нити?
функция ThreadSwitch называется диспетчером или планировщиком (scheduler) и ведет себя следующим образом.

  • Она передает управление на следующую активную нить.
  • Текущая нить остается активна, и через некоторое время снова получит управление.
  • При этом она получит управление так, как будто ThreadSwitch представляла собой обычную функцию и возвратила управление в точку, из которой она была вызвана.

Очевидно, что функцию ThreadSwitch нельзя реализовать на языке высокого уровня, вроде С, потому что это должна быть функция, которая не возвращает [немедленно] управления в ту точку, из которой она была вызвана. Она вызывается из одной нити, а передает управление в другую. Это требует прямых манипуляций стеком и записью активизации и обычно достигается использованием ассемблера или ассемблерных вставок. Некоторые ЯВУ (Ada, Java, Occam) предоставляют примитивы создания и переключения нитей в виде специальных синтаксических конструкций.
Самым простым вариантом, казалось бы, будет простая передача управления на новую нить, например, командой безусловной передачи управления по указателю. При этом весь описатель нити (struct Thread) будет состоять только из адреса, на который надо передать управление. Беда только в том, что этот вариант не будет работать.
Действительно, каждая из нитей исполняет программу, состоящую из вложенных вызовов процедур. Для того чтобы нить нормально продолжила исполнение, нам нужно восстановить не только адрес текущей команды, но и стек вызовов (см. разд. Косвенно-регистровый режим со смещением). Поэтому мы приходим к такой архитектуре.

  • Каждая нить имеет свой собственный стек вызовов.
  • При создании нити выделяется область памяти под стек, и указатель на эту область помещается в дескриптор нити.
  • ThreadSwitch сохраняет указатель стека (и, если таковой есть, указатель кадра) текущей нити в ее дескрипторе и восстанавливает SP из дескриптора следующей активной нити (переключение стеков необходимо реализовать ассемблерной вставкой, потому что языки высокого уровня не предоставляют средств для прямого доступа к указателю стека (пример 8.1)).
  • Когда функция ThreadSwitch выполняет оператор return, она автоматически возвращает управление в то место, из которого она была вызвана в этой нити, потому что адрес возврата сохраняется в стеке.

Пример 8.1. Кооперативный переключатель потоков

Thread * thread_queue_head;
Thread * thread_queue_tail;
Thread * current_tread;
Thread * old__thread;
void TaskSwitch () { old_thread=current_thread; add_to_queue_tail(current_thread); current_thread=get_from_queue_head(); asm { .
move bx, old_thread
push bp
move ax, sp
move thread_sp[bx], ax
move bx, current_thread
move ax, rhread_sp[bx]
pop bp
}
return;
}

Если система программирования предполагает, что при вызове функции должны сохраняться определенные регистры (как, например, С-компиляторы для х86 сохраняют при вызовах регистры SI и DI (ESI/EDI в 1386)), то они также сохраняются в стеке. Поэтому предложенный нами вариант также будет автоматически сохранять и восстанавливать все необходимые регистры.
Понятно, что кроме указателей стека и стекового кадра, struct Thread должна содержать еще некоторые поля. Как минимум, она должна содержать указатель на следующую активную нить. Система должна хранить указатели на описатель текущей нити и на конец списка. При этом ThreadSwitch переставляет текущую нить в конец списка, а текущей делает следующую за ней в списке. Все вновь активизируемые нити также ставятся в конец списка. При этом список не обязан быть двунаправленным, ведь мы извлекаем элементы только из начала, а добавляем только в конец.
Часто в литературе такой список называют очередью нитей (thread queue) или очередью процессов. Такая очередь присутствует во всех известных автору реализациях многозадачных систем. Кроме того, очереди нитей используются и при организации очередей ожидания различных событий, например, при реализации семафоров Дейкстры.
Планировщик, основанный на Threadswitch, т. е. на принципе переключения по инициативе активной нити, используется в ряде экспериментальных и учебных систем. Этот же принцип, называемый кооперативной многозадачностью, реализован в библиотеках языков Simula 67 и Modula-2. MS Windows 3.x также имеют средство для организации кооперативного переключения задач — системный вызов GetNextEvent.
Часто кооперативные нити называют не нитями, а сопрограммами — ведь они вызывают друг друга, подобно подпрограммам. Единственное отличие такого вызова от вызова процедуры состоит в том, что такой вызов не ие-рархичен — вызванная программа может вновь передать управление исходной и остаться при этом активной.
Основным преимуществом кооперативной многозадачности является простота отладки планировщика. Кроме того, снимаются все коллизии, связанные с критическими секциями и тому подобными трудностями — ведь нить может просто не отдавать никому управления, пока не будет готова к этому.
С другой стороны, кооперативная многозадачность имеет и серьезные недостатки.
Во-первых, необходимость включать в программу вызовы Threadswitch усложняет программирование вообще и перенос программ из однозадачных или иначе организованных многозадачных систем в частности.
Особенно неприятно требование регулярно вызывать Threadswitch для вычислительных программ. Чаще всего такие программы исполняют относительно короткий внутренний цикл, скорость работы которого определяет скорость всей программы. Для "плавной" многозадачности необходимо вызывать Threadswitch из тела этого цикла. Делать вызов на каждом шаге Цикла нецелесообразно, поэтому необходимо будет написать код, похожий на приведенный в примере 8.2.

Пример 8.2. Внутрений цикл программы в кооперативно многозадачной среде

int counter; // Переменная-счетчик,
while(condition) {
// Вызывать ThreadSwitch каждые rate циклов.
counter++;
if (counter % rate == 0) ThreadSwitch();
.... // Собственно вычисления j
}

Условный оператор и вызов функции во внутреннем цикле сильно усложняют работу оптимизирующим компиляторам и приводят к разрывам конвейера команд, что может очень заметно снизить производительность. Вызов функции на каждом шаге цикла приводит к еще большим накладным расходам и, соответственно, к еще большему замедлению.
Во-вторых, злонамеренная нить может захватить управление и никому не отдавать его. Просто не вызывать ThreadSwitch, и все. Это может произойти не только из-за злых намерений, но и просто по ошибке.
Поэтому такая схема оказывается непригодна для многопользовательских систем и часто не очень удобна для интерактивных однопользовательских.
Почему-то большинство коммерческих программ для Win16, в том числе и поставлявшиеся самой фирмой Microsoft, недостаточно активно использовали вызов GetNextEvent. Вместо этого такие программы монопольно захватывали процессор и рисовали известные всем пользователям этой системы "песочные часы". В это время система никак не реагирует на запросы и другие действия пользователя кроме нажатия кнопки RESET или клавиш <CTRL>+<ALT>+<DEL>.
В-третьих, кооперативная ОС не может исполняться на симметричной многопроцессорной машине, а приложения, написанные в расчете на такую ОС, не могут воспользоваться преимуществами многопроцессорности.
Простой анализ показывает, что кооперативные многозадачные системы пригодны только для учебных проектов или тех ситуаций, когда программисту на скорую руку необходимо сотворить многозадачное ядро. Вторая ситуация кажется несколько странной — зачем для серьезной работы может потребоваться быстро сделанное ядро, если существует много готовых систем реального времени, а также общедоступных (freeware или public domain) в виде исходных текстов реализаций таких ядер?

 
Назад Начало Вперед