Вытесняющая многозадачность

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

• Каждой нити выделяется квант времени.
• Если нить не освободила процессор в течение своего кванта, ее снимают и переставляют в конец очереди. При этом все готовые к исполнению нити более или менее равномерно получают управление.

Этот механизм, называемый time slicing или разделение времени, реализован в микрокоде транспьютера и практически во всех современных ОС. Общим названием для всех методов переключения нитей по инициативе системы является термин вытесняющая (preemptive) многозадачность. Таким образом, вытесняющая многозадачность противопоставляется кооперативной, в которой переключение происходит только по инициативе самой задачи. Разделение времени является частным случаем вытесняющей многозадачности. В системах с приоритетами, вытеснение текущей задачи происходит не только по сигналам таймера, но и в случае, когда по каким-то причинам (чаше всего из-за внешнего события) активизируется процесс, с приоритетом выше, чем у текущего.
При этом вопрос выбора кванта времени является нетривиальной проблемой. С одной стороны, чрезмерно короткий квант приведет к тому, что большую часть времени система будет заниматься переключением потоков. С другой стороны, в интерактивных системах или системах реального времени слишком большой квант приведет к недопустимо большому времени реакции.
В системе реального времени мы можем объявить нити, которым надо быстро реагировать, высокоприоритетными и на этом успокоиться. Однако нельзя так поступить с интерактивными программами в многопользовательской или потенциально многопользовательской ОС, как UNIX на настольной машине х86 или Sun.
Из психологии восприятия известно, что человек начинает ощущать задержку ответа при величине этой задержки около 100 мс. Поэтому в системах разделенного времени, рассчитанных на интерактивную работу, квант обычно выбирают равным десяткам миллисекунд. В старых системах, ориентированных на пакетную обработку вычислительных задач, таких как ОС ДИСПАК на БЭСМ-6, квант мог достигать десятых долей секунды или даже секунд. Это повышает эффективность системы, но делает невозможной или, по крайней мере, неудобной — интерактивную работу. Многие современные системы подбирают квант времени динамически для разных классов планирования и приоритетов процесса.
Системы реального времени обычно имеют два класса планирования — реального и разделенного времени. Класс планирования, как правило, дается не отдельным нитям, а целиком процессам. Процессы реального времени не прерываются по сигналам таймера и могут быть вытеснены только активизацией более приоритетной нити реального времени. Нити реального времени высочайшего приоритета фактически работают в режиме кооперативной многозадачности. Зато нити процессов разделенного времени вытесняются и друг другом по сигналам таймера, и процессами реального времени по мере их активизации.
Вытесняющая многозадачность имеет много преимуществ, но если мы про сто будем вызывать описанный в предыдущем разделе ThreadSwitchпо прерываниям от таймера или другого внешнего устройства, то такое переключение будет непоправимо нарушать работу прерываемых нитей.
Действительно, пользовательская программа может использовать какой-тл из регистров, который не сохраняется при обычных вызовах. Поэтому, например, обработчики аппаратных прерываний сохраняют в стеке все используемые ими регистры. Кстати, если наша функция ThreadSwitch будет сохранять в стеке все регистры, то произойдет именно то, чего мы хотим. ThreadSwitch вызывается по прерыванию, сохраняет регистры текущей нити в текущем стеке, переключается на стек новой нити, восстанавливает из ее стека ее регистры, и новая нить получает управление так, будто и не теряла его.
Полный набор регистров, которые нужно сохранить, чтобы нить не заметила переключения, называется контекстом нити или, в зависимости от принятой в конкретной ОС терминологии, контекстом процесса. К таким регистрам, как минимум, относятся все регистры общего назначения, указатель стека, счетчик команд и слово состояния процессора. Если система использует виртуальную память, то в контекст входят также регистры диспетчера памяти, управляющие трансляцией виртуального адреса (пример 8.3).

Пример 8.3. Функция переключения контекста в ядре Linux/x86

/* Фрагмент файла \arch\i386\kernel\process.c.
* Сохранение и восстановление регистров общего назначения
* и сегментных регистров CS, DS и S3 осуществляется при входе в ядре *и при выходе из него соответственно. */
/*
* switch_to(х,у) должна переключать задачи с х на у *
* Мы используем fsave/fwait, поэтому исключения [сопроцессора]
* сбрасываются в нужный момент времени (пока вызов со стороны
* fsave или fwait обрабатывается), и не могут быть посланы
* другому процессу. Отложенное сохранение FP более не имеет
* смысла на современных ЦПУ и это многое упрощает (SMP и UP
* [uniprocessor, однопроцессорная конфигурация] теперь
* обрабатываются одинаково).
Раньше мы использовали аппаратное переключение
* контекста. Причина, по которой мы больше так не делаем
* становится очевидна, когда мы пытаемся аккуратно восстановиться
* из сохраненного состояния, которое стало недопустимым
* (в частности, висящие ссылки в сегментных регистрах).
* При использовании аппаратного переключения контекста нет способа
* разумным образом выйти из плохого состояния [контекста]. *
* То, что Intel документирует аппаратное переключение контекста как
* медленное — откровенная ерунда, этот код не дает заметного ускорения.
* Однако здесь есть некоторое пространство для улучшения, поэтому
* вопросы производительности могут рано или поздно оказаться актуальны.
* [В данном случае], однако, нам важнее, что наша реализация * обеспечивает большую гибкость.
*/ void __switch_to(struct task_struct *prev_p, struct task_struct *next_p)
(
struct thread_struct *prev = &prev_p->thread, Д *next = &next_p->thread;
struct tss_struct *tss = init_tss + smp_processor_id();
unlazy_fpu (prev__p) ;
/*
* Перезагрузить espO, LOT и указатель на таблицу страниц: */
tss->espO = next->espO;
/*
* Сохранить %fs и %gs. He нужно сохранять %ез и %ds,
* потому что при исполнении в контексте ядра это
* всегда сегменты ядра. */
asm volatile("movl %%fs,%0":"=m" (* (int *)&prev->fs)); asm volatile("movl %%gs,%0":"=m" (*(int *)&prev->gs));
* Восстановить Its и Ч
loadsegment(fs, next->fs); loadsegment(gs, next->gs);
/*
* Если это необходимо, перезагрузить отладочные регистры */ if (next->debugreg[7]){
loaddebug(next, 0};
loaddebug(next, 1);
loaddebug(next, 2);
loaddebug(next, 3);
/* не 4 и 5 */
loaddebug(next, 6);
loaddebug(next, 7);
if (prev->ioperm || next->iopenn) { if (next->ioperm) {
*
/*
* Копирование четырех линий кэша .... не хорошо, но
* и не так уж плохо. У кого-нибудь есть идея лучше?
* Оно воздействует только на процессы, использующие iopermO.
* [Размещение этих TSS в области 4K-tlb и игры с виртуальной
* памятью для переключения битовой маски ввода/вывода на
* самом деле неприемлемы.] */
memcpy(tss->io_bitmap, next->io_bitmap,
IO_BITMAP_SIZE*sizeof(unsigned long)); tss~>bitmap = IO_BITMAP_OFFSET; } else /*
* Смещение битовой маски, указывающее за пределы ограничителя "- - >
* порождает контролируемое SIGSEGV, если процесс пытается
* использовать команды обращения к портам. Первый вызов
* sys_ioperm() устанавливает битовую маску корректно. */
tss->bitmap = INVALID 10 BITMAP OFFSET;

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

Как правило, оказывается неудобным сохранять контекст именно в стеке. Тогда его сохраняют в какой-то другой области памяти, чаще всего в дескрипторе процесса. Многие процессоры имеют специальные команды сохранения и загрузки контекста. Для реализации вытеснения достаточно сохранить контекст текущей нити и загрузить контекст следующей активной нити из очереди. Необходимо предоставить также и функцию переключения нитей по их собственной инициативе, аналогичную ThreadSwitch или, точнее, DeactivateThread.
Обычно вместо DeactivateThread система предоставляет высокоуровневые примитивы синхронизации, например семафоры или примитивы гармонического взаимодействия. Вызов DeactivateThread оказывается скрытым внутри таких высокоуровневых функций.
Вытесняющий планировщик с разделением времени ненамного сложнее кооперативного планировщика — и тот, и другой реализуются несколькими десятками строк на ассемблере. В работе (Прохоров 1990| приводится полный ассемблерный текст приоритетного планировщика системы VAX/VMS, занимающий одну страницу (автору неизвестно, не нарушает ли авторские права фирмы DEC публикация этого текста). Впрочем, планировщики, рассчитанные на многопроцессорные машины, часто бывают несколько сложнее (пример 8.4).

Пример 8.4. Планировщик Linux 2.5

/*
* 'schedule!)' — функция планировщика. Это очень простой и
* приятный планировщик: он не совершенен, но несомненно работает
* в большинстве случаев.
* The goto is "interesting".
*
* ЗАМЕЧАНИЕ!! Задача 0 является 'пустой' задачей, которая вызывается
* когда ни одна другая задача не может выполняться. Она не может быть
* "убита" и не может "спать". Информация о состоянии в task[0] никогда
* не используется.
*/
asmlinkage void schedule(void)
{
struct schedule_data * sched_data;
struct task_struct *prev, *next, *p;
struct list_head *tmp;
int this__cpu, c;
if (!current->active_mm) BUG(); need_resched_back: prev = current; this_cpu = prev~>processor;
if (in_interrupt())
goto scheduling_in_interrupt;
release_kernel_lock(prev, this_cpu);
/* Выполнить административную работу здесь, пока мы не держим
* ни одной блокировки.
*/
if (softirq_active(this_cpu) & softirq_mask(this_cpu))
goto handle_softirq; handle_softirq_back:
/*
* 'shed data" защищена неявно, тем фактом, что мы можем исполнять
* только один процесс на одном ЦПУ. */
sched__data = & aligned_data[this_cpu].schedule_data;
spin_lock_irq (&runqueue__lock) ;
/* Переместить исчерпанный процесс RR в конец [очереди] */ if (prev->policy == SCHED_RR)
goto move_rr_last; pove_rr_back:
switch (prev->state) { case TASKJLNTERRUPTIBLE:
if (signal_pending (prev) ) { prev->state = TASK_RUNNING; break; } default:
dei_f rom_runqueue (prev) ; case TASK_RUNNING: ;
}
prev->need_resched = 0;
/*
* это собственно планировщик: */
repeat_schedule : /*
* Выбрать процесс по умолчанию. . . */
next = idle_task(this_cpu) ; с = -1000;
if (prev->state == TASK_RUNNING) goto still_running;
still_running_back :
list_for_each (tmp, srunqueue_head) {
p = list_entry (tmp, struct task_struct, run_list) ; if (can_schedule (p, this_cpu) ) {
int weight = goodness (p, this_cpu, prev->active_mm) ; if (weight > c)
с = weight, next = p;
/* Следует ли перевычислить счетчики? */
if (!c)
goto recalculate; /*
* с этого момента ничто ке может помешать нам
* переключиться на следующую задачу, отметить этот
* факт в sched_data. */
sched_data->curr = next; tifdef CONFIG_SMP
riext->has_cpu = I;
next->processor = this_cpu; lendif
spin_unlock__irq (&runqueue_lock) ;
if (prev == next) goto same_process;
ttifdef CONFIG_SMP /*
* Поддерживать значение 'last schedule' для каждого процесса
* (его необходимо пересчитать лаже если мы планируем тот же
* процесс). Сейчас это значение используется только в SMP, и оно
* приблизительно, поэтому мы не обязаны поддерживать его,
* пока захвачена блокировка runqueue. */
sched_data->last_schedule = get_cycles();
/*
* Мы снимаем блокировку планировщика рано (это глобальная
* блокировка), поэтому мы должны защитить предыдущий процесс
* от повторного планирования во время switch_to(). */
ttendif /* CONFIG_SMP */
kstat.context_swtch++; /*
* Переключение контекста воздействует на три процесса:
prev
.. ==> (last => next)
* Это 'prev' , 'далеко предшествующий' размещенному в стеке 'next1,
* но функция switch_to() устанавливает prev на (только что
* работавший) процесс 'last'.
* Описание несколько запутанно, но не лишено глубокого смысла,
*/
prepare_to_switch ( ) ;
{
struct mm struct *mm = next->mm;
struct mm_struct *oldmm = prev->active_mm;
if ( !mmi (
if (next->active_mm) BUG ( ) ;
next->active_mm = oldmm;
atomic_inc (&oldmm->mra_count) ;
enter_lazy_tlb (oldmm, next, this_cpu) ; } else {
if (next->active_mm != mm) BUG ( ) ;
switch_mm(ol<±nm, mm, next, this__cpu) ;
if ( !prev->irin) (
prev->active_mm = NULL; mmdrop (oldmm) ;
/*
* Этот оператор только переключает состояние регистров
* и стека. */
switch_to(prev, next, prev); __schedule_tail(prev);
same_process:
teacquire_kernel__lock (current) ; if (current->need_resched) goto need reached back;
recalculate: {
struct task_struct *p;
spin_unlock_irq (&runqueue_lock) ;
read_lock (&tasklist_lock) ;
for_each_task (p)
p->counter = (p->counter » 1) + NICE_TO_TICKS (p->nice)
read_unlock (&tasklist__lock) ;
spin_lock_irq (&runqueue_lock) ; } goto repeat_schedule;
still_running:
с = goodness (prev, this_cpu, prev->active_mm) ; next = prev;
goto still_running_back;

handle_sof tirq: do_softirq ( ) ; goto handle_softirq_back;
move_rr_last :
if ( !prev->counter) (
prev->counter = NICE_TO_TICKS (prev->nice) ; move_last_runqueue (prev) ; } goto move_rr_back;
scheduling_in_interrupt :
printk ("Scheduling in interrupt\n") ;
BUG ( ) ;
return;

Контексты современных процессоров
У современных процессоров, имеющих десятки регистров общего назначения и виртуальную память, размер контекста процесса измеряется сотнями байтов. Например, у процессора VAX контекст процессора состоит из 64 32-разрядных слов, т. е. 256 байт. При этом VAX имеет только 16 регистров общего назначения, а большая часть остальных регистров так или иначе относится к системе управления виртуальной памятью.
У микропроцессоров SPARC, имеющих регистровый файл объемом до нескольких килобайтов, контекст, на первый взгляд, должен быть чудовищного размера. Однако программе одновременно доступны лишь 32 регистра общего назначения, 24 из которых образуют скользящее по регистровому файлу окно. Благодаря этому факту, контекст процессора SPARC состоит только из первых восьми регистров общего назначения и служебных регистров. Регистровое окно новой нити выделяется в свободной области регистрового файла, а его передвижение обрабатывается при помощи исключений заполнения и очистки окна.
Если в системе всего несколько активных процессов, может оказаться так, что их регистровые окна постоянно "живут" в регистровом файле, поэтому объем данных, реально копируемых при переключении нитей, у SPARC не больше, чем у CISC-процессоров с небольшим количеством регистров общего назначения. Впрочем, и у SPARC, и у CISC-процессоров основную по объему часть контекста процесса составляют регистры диспетчера памяти.
На этом основано преимущество транспьютера перед процессорами традиционных и RISC-архитектур. Дело в том, что транспьютер не имеет диспетчера памяти, и у него вообще очень мало регистров. В худшем случае, при переключении процессов (в транспьютере, как и в старых ОС, нити называются процессами) должно сохраняться 7 32-разрядных регистров. В лучшем случае сохраняются только два регистра — счетчик команд и статусный регистр. Кроме того, перенастраивается регистр wptr, который выполняет по совместительству функции указателя стека, базового регистра сегмента статических данных процесса и указателя на дескриптор процесса.
Транспьютер имеет три арифметических регистра, образующих регистровый стек. При этом обычное переключение процессов может происходить только, когда этот стек пуст. Такая ситуация возникает довольно часто; например, этот стек обязан быть пустым при вызовах процедур и даже при условных и безусловных переходах, поэтому циклическая программа не может не иметь точек, в которых она может быть прервана. Упомянутые в предыдущем разделе команды обращения к линкам также исполняются при пустом регистровом стеке. Поэтому, оказывается достаточно перезагрузить три управляющих регистра, и мы передадим управление следующему активному процессу.
Операция переключения процессов, а также установка процессов в очередь при их активизации полностью реализованы на микропрограммном уровне.
Деактивизация процесса происходит только по его инициативе, когда он начинает ожидать сигнала от таймера или готовности линка. При этом процесс исполняет специальную команду, которая устанавливает его в очередь ожидающих соответствующего события, и загружает контекст очередного активного процесса. Когда приходит сигнал таймера или данные по линку, то также вызывается микропрограмма, которая устанавливает активизированный процесс в конец очереди активных.
У транспьютера также существует микропрограммно реализованный режим разделения времени, когда по сигналам внутреннего таймера активные про цессы циклически переставляются внутри очереди. Такие переключения ка уже говорилось, могут происходить только, когда регистровый стек текущег процесса пуст, но подобные ситуации возникают довольно часто.
Кроме обычных процессов в системе существуют так называемые высокопри оритетные процессы. Если такой процесс получает управление в результате внешнего события, то текущий низкоприоритетный процесс будет прерван независимо от того, пуст его регистровый стек или нет. Для того чтобы при этом не разрушить прерванный процесс, его стек и весь остальной контекст записываются в быструю память, расположенную на кристалле процессора. Это и есть тот самый худший случай, о котором говорилось ранее. Весь цикл переключения занимает 640нс по сравнению с десятками и, порой, сотнями микросекунд у традиционных процессоров [INMOS 72 TRN 203 02, Харп 1993].
Благодаря такой организации транспьютер не имеет равных себе по времени реакции на внешнее событие. На первый взгляд, микропрограммная реализация такой довольно сложной конструкции, как планировщик, снижает гибкость системы. В действительности, в современных системах планировщики имеют довольно стандартную структуру, и реализация, выполненная в транспьютере, очень близка к этому стандарту, известному как микроядро (microkernel) (см. разд. Монолитные системы или системы с микроядром).