Примечание. Авторы рекомендуют читать книгу вместе с исходным текстом xv6. Авторы подготовили и лабораторные работы по xv6.

Xv6 работает на RISC-V, поэтому для его сборки нужны RISC-V версии инструментов: QEMU 5.1+, GDB 8.3+, GCC, и Binutils. Инструкция поможет поставить инструменты.

ОС часто выполняет процессов больше, чем доступно процессоров, поэтому ОС планирует работу процессов. Процессы не знают, как ОС распределяет время процессора между ними - каждый процесс владеет виртуальным процессором. ОС мультиплексирует процессы на процессоре - переключает процессы через равные промежутки времени.

Мультиплексирование

Xv6 переключает процессы, когда:

• Процесс добровольно уступает процессор, когда вызывает sleep и ожидает события - завершения ввода-вывода устройства или канала, завершения дочернего процесса.

• Таймер прерывает процесс - xv6 отнимает управление у процесса и передает другому.

Мультиплексирование и виртуальная память разрешают процессу работать так, словно он один на компьютере.

Мультиплексирование ставит перед ОС такие задачи:

• Как переключать процессы? Код написать труднее, чем рассказать о переключении процессов.

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

• Как избежать взаимоблокировок из-за переключения процессов?

• Как освободить ресурсы процесса, когда он завершает работу? Пример: процесс не способен освободить стек ядра, пока выполняется.

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

• Процесс уступает процессор с помощью функций sleep и wakeup. Нельзя терять вызовы wakeup из-за состязаний процессов.

Xv6 решает эти проблемы как можно проще, но код все равно вышел непростым.

Код: переключение контекста

Рисунок показывает шаги переключения процесса:

• Системный вызов или прерывание переключает процесс в режим ядра.

• Поток ядра переключается на поток планировщика текущего процессора.

• Планировщик переключается на поток ядра другого процесса.

• Поток ядра возвращается в режим пользователя.

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

Процессор сохраняет регистры старого потока и загружает регистры нового - переключает контекст выполнения процесса. Процессор переключается на другой код, когда загружает новые значения регистров pc и sp - счетчика команд и указателя стека. Остальные регистры тоже входят в контекст процесса.

Процедура swtch сохраняет и восстанавливает контекст потоков ядра - регистры процессора. Поток ядра процесса вызывает swtch, чтобы сохранить контекст и передать управление потоку планировщика. Файл kernel/proc.h определяет структуру context, структуры proc и cpu, которые включают context. Процедура swtch принимает два аргумента - struct context *old и struct context *new - сохраняет регистры процессора в old и загружает регистры из new.

Процедура swtch сохраняет не 32 регистра RISC-V, а только регистры s0-s11, sp и ra. Компилятор следует соглашениям о вызовах RISC-V и сохраняет остальные регистры на стеке процедуры, которая вызвала swtch.

Структура context содержит адрес возврата ra вместо счетчика инструкций pc - swtch восстанавливает ra из контекста new и выполняет ret, чтобы передать управление по адресу new.ra, чтобы поток продолжил работу с инструкции, которая следует за вызовом swtch. Процедура swtch переключается на стек new.sp нового потока, прежде чем выполнить ret.

Глава 4 рассказывала, что обработчик прерывания таймера вызывает yield. Процедура yield вызывает процедуру sched, которая вызывает swtch, чтобы сохранить контекст в структуре текущего процесса p->context и переключиться на контекст планировщика cpu->context. В прошлом функция scheduler планировщика сохранила этот контекст, когда вызвала swtch и переключилась на процесс, который теперь уступает процессор. Теперь swtch вернется не в sched, а в scheduler и работает на стеке планировщика.

Код: планирование

Каждый процессор выполняет поток планировщика - функцию scheduler. Функция решает, какой процесс выбрать следующим.

Процесс уступает процессор так: освободит блокировки, которые удерживал, захватит блокировку процесса p->lock, обновит состояние процесса p->state и вызовет sched. Функции yield, sleep и exit выполняют эти действия. Процедура sched снова убедится, что прерывания отключены, когда блокировка захвачена. Затем sched вызовет swtch, чтобы сохранить контекст процесса в p->context и переключиться на контекст планировщика cpu->context. Процедура switch возвращается на стек планировщика, словно после вызова из scheduler. Планировщик продолжит цикл for, найдет следующий процесс для запуска, переключится на него и сценарий повторится.

Xv6 удерживает p->lock, когда вызывает switch и передает владение блокировкой коду, на который переключается. До сих пор поток, который захватил блокировку, сам блокировку и освобождал. Здесь же p->lock защищает инвариант полей state и context. Процедура swtch нарушает инвариант, поэтому swtch не отпускает блокировку, пока работает. Новый поток освободит блокировку, когда swtch передаст потоку управление. Если бы swtch не удерживал p->lock, другой процессор мог бы запустить тот же процесс, когда yield установил p->state = RUNNABLE, но прежде чем swtch переключился на стек процесса.

Поток ядра уступает процессор только в sched и переходит в одно и то же место в scheduler. Процедура scheduler почти всегда передает управление другому потоку ядра который вызвал sched в прошлом. Вы заметите закономерность по номерам строк в kernel/proc.c, когда потоки переключаются - 497, 463, 497, 463 и т.д. Процедуры, которые передают управление друг другу через переключение потоков, называют корутинами. Процедуры sched и scheduler - корутины.

Вызов swtch не ведет в sched, когда планировщик переключается на процесс, который xv6 только запустила. Процедура allocproc записывает в регистр ra адрес процедуры forkret - первый вызов swtch передаст управление forkret. Процедура forkret освободит блокировку p->lock и вызовет usertrapret, чтобы процесс вернулся в режим пользователя.

Процедура scheduler выполняет цикл - выбирает процесс, выполняет, пока процесс не уступит процессор, повторяет. Цикл планировщика обходит таблицу процессов в поисках процесса, который готов к выполнению - p->state == RUNNABLE. Каждый процессор запоминает текущий процесс в c->proc. Планировщик меняет состояние процесса на RUNNING и вызывает swtch, чтобы выполнить процесс.

Планировщик следит за инвариантами каждого процесса и удерживает p->lock, пока инварианты нарушены. Примеры инвариантов:

• p->state == RUNNING, регистры процессора принадлежат процессу, а c->proc указывает на этот процесс. Вызов yield по таймеру безопасно переключит этот процесс на другой.

• p->state == RUNNABLE, p->context содержит верные регистры процессора, ни один процессор не выполняет этот процесс и не работает со стеком ядра этого процесса. Поток планировщика на свободном процессоре безопасно запустит этот процесс.

Убедитесь, что код нарушает эти условия, пока держит p->lock.

Xv6 захватывает p->lock в одном потоке и освобождает в другом, чтобы соблюдать инварианты. Пример: yield захватывает p->lock, а scheduler освобождает. Поток удерживает блокировку, пока yield меняет состояние процесса на RUNNABLE. Поток освобождает блокировку, как только scheduler восстановит инвариант - переключится на стек планировщика и очистит c->proc. Аналогично поток удерживает блокировку, пока scheduler меняет состояние процесса с RUNNABLE на RUNNING.

Код: mycpu и myproc

Xv6 часто требует указатель на struct proc текущего процесса. Однопроцессорная система объявит глобальную переменную current_process. Многопроцессорная система выполняет процессы параллельно, поэтому регистр процессора указывает на текущий процесс.

Xv6 ведет структуру cpu для каждого процессора, которая запоминает текущий процесс, контекст планировщика и счетчик захваченных спин-блокировок, чтобы отключать прерывания. Функция mycpu возвращает указатель на структуру cpu текущего процессора. RISC-V нумерует процессоры - назначает каждому hartid. Xv6 хранит hartid процессора в регистре tp, когда работает в режиме ядра. Функция mycpu использует регистр tp как индекс в массиве структур cpu.

Процедура start записывает регистр tp еще при запуске ОС, когда работает в машинном режиме. Процедура usertrapret сохраняет регистр tp на странице trampoline, потому что процесс в режиме пользователя способен изменить регистр tp. Процедура uservec восстановит регистр tp, когда переключится в режим ядра. Компилятор обещает не использовать регистр tp. RISC-V разрешает запрашивать hartid процессора только в машинном режиме, поэтому xv6 работает с регистром tp.

Опасно, если таймер прервал поток после вызова функций cpuid или mycpu, а другой процессор запустил этот поток - тогда возвращаемые значения cpuid и mycpu устарели. Xv6 требует отключать прерывания перед вызовом cpuid или mycpu и включать, когда поток закончил работать со значениями, которые вернули эти функции.

Функция myproc возвращает указатель на структуру proc, которая описывает текущий процесс. Функция myproc отключает прерывания, вызывает mycpu, получает указатель c->proc на текущий процесс и снова включает прерывания. Результат myproc останется корректным даже если процесс переедет на другой процессор.

sleep и wakeup

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

• Читатель канала ждет, пока другой процесс в канал запишет.

• Родительский процесс вызывает wait и ждет, пока дочерний процесс завершится.

• Читатель диска ждет, пока диск завершит операцию чтения.

Ядро xv6 усыпляет и будит процессы. Поток ядра засыпает и ждет события. Другой поток вызывает wakeup, чтобы сообщить о событии и разбудить потоки, которые ждут. Функции sleep и wakeup называют механизмами условной синхронизации или последовательной координации. Функции sleep и wakeup предлагают низкоуровневый интерфейс синхронизации. Реализуем семафор на основе sleep и wakeup - высокоуровневый интерфейс, который синхронизирует читателей и писателей.

Xv6 не использует семафоры.

Семафор хранит счетчик и предлагает операции P и V. Операция V - для писателей - увеличивает счетчик на 1. Операция P - для читателей - ждет, пока счетчик станет больше 0, и уменьшает счетчик на 1.

struct semaphore {
	struct spinlock lock;
	int count;
};

void
V(struct semaphore *s) 
{
	acquire(&s->lock);
	s->count += 1;
	release(&s->lock);
}

void
P(struct semaphore *s)
{
	while (0 == s->count) { /* ожидание */ }
	
	acquire(&s->lock);
	s->count -= 1;
	release(&s->lock);
}

Такой семафор работает для одного писателя и одного читателя, которые работают параллельно на двух процессорах, если компилятор не оптимизирует код. Этот код неэффективен - когда писатель работает медленно, читатель тратит время впустую в цикле ожидания. Код работал бы лучше, если бы читатель уступал процессор и возвращался к работе, когда V увеличит счетчик.

Представьте пару функций sleep и wakeup. Вызов sleep(chan) заставляет процесс уступить процессор и уснуть на канале ожидания с номером chan. Вызов wakeup(chan) будит все процессы, которые спят на канале ожидания chan, и заставляет их вызовы sleep выполнить return. Вызов wakeup ничего не делает, если ни один процесс не спит на канале ожидания chan. Научим семафор вызывать sleep и wakeup:

void
V(struct semaphore *s) 
{
	acquire(&s->lock);
	s->count += 1;
    wakeup(s);
	release(&s->lock);
}

void
P(struct semaphore *s)
{
	while (0 == s->count) { sleep(s); }
	
	acquire(&s->lock);
	s->count -= 1;
	release(&s->lock);
}

Теперь P не выполняет цикл ожидания, а уступает процессор. Этот код рискует потерять вызов wakeup. Представьте: P проверяет условие 0 == s->count, решает вызвать sleep, но V на другом процессоре успевает увеличить счетчик и вызвать wakeup, которому нечего делать. Теперь P вызовет sleep, но процесс уже некому разбудить.

V отработала в неподходящее время и нарушила инвариант "P спит только когда 0 == s->count". Наивное и неверное решение - захватить блокировку до проверки s->count, чтобы P проверял счетчик и вызывал sleep атомарно:

void
V(struct semaphore *s) 
{
	acquire(&s->lock);
	s->count += 1;
    wakeup(s);
	release(&s->lock);
}

void
P(struct semaphore *s)
{
	acquire(&s->lock);
	while (0 == s->count) { sleep(s); }
	
	s->count -= 1;
	release(&s->lock);
}

Код больше не теряет вызов wakeup, но ведет к взаимоблокировке - P удерживает блокировку, пока спит, поэтому V зависнет на захвате блокировки.

Изменим интерфейс sleep - пусть код передает функции условную блокировку, чтобы sleep освобождала блокировку, когда процесс засыпает. Блокировка заставит V дождаться, когда P уснет, прежде чем V вызовет wakeup. Функция sleep снова захватит блокировку, когда P проснется, прежде чем выполнить return.

void
V(struct semaphore *s) 
{
	acquire(&s->lock);
	s->count += 1;
    wakeup(s);
	release(&s->lock);
}

void
P(struct semaphore *s)
{
	acquire(&s->lock);
	while (0 == s->count) { sleep(s, &s->lock); }
	
	s->count -= 1;
	release(&s->lock);
}

Функция sleep освобождает блокировку и засыпает атомарно.

Код: sleep и wakeup

Xv6 реализует функции sleep и wakeup как в последнем примере кода. Такой код sleep и wakeup и правила работы с ними гарантируют, что ни один вызов wakeup не потеряется. Вызов sleep помечает процесс как SLEEPING и вызывает sched, чтобы уступить процессор. Функция wakeup ищет процессы, которые спят на указанном канале, и помечает RUNNABLE. Пользователи sleep и wakeup выбирают номер канала ожидания произвольно. Xv6 часто использует адрес структуры данных как номер канала ожидания.

Вызов sleep(chan, lk) захватывает p->lock. Теперь процесс, который готовится ко сну, удерживает две блокировки - p->lock и lk. Функция, которая вызвала sleep, захватила блокировку lk, чтобы другой процесс не вызвал wakeup. Теперь sleep освободит lk - даже если другой процесс вызовет wakeup, вызов wakeup ожидает освобождения p->lock.

Теперь процесс удерживает только p->lock и засыпает - sleep запомнит канал ожидания, установит p->state = SLEEPING и вызовет sched.

Теперь другой процесс способен захватить условную блокировку lk, удовлетворить условие, которого ждет спящий, и вызвать wakeup(chan). Важно, что процесс удерживает lk, когда вызывает wakeup. Вызов wakeup обходит таблицу процессов и захватывает блокировку p->lock, потому что меняет p->state процесса и потому что p->lock гарантирует, что sleep и wakeup не упустят друг друга. Вызов wakeup ищет процесс, что спит на канале chan и будит. Планировщик увидит этот процесс, как только получит управление.

Как правила блокирования для sleep и wakeup гарантируют, что спящий процесс не упустит wakeup? Процесс, который вызывает sleep - читатель - удерживает lk или p->lock или обе блокировки с момента до проверки условия и до тех пор, когда установит p->state = SLEEPING. Процесс, который вызывает wakeup - писатель - удерживает обе блокировки в цикле wakeup. Таким образом писатель удовлетворит условие, прежде чем читатель проверит условие, либо писатель вызовет wakeup после того как читатель уснет.

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

Не страшно, если sleep и wakeup случайно выберут канал, который используют другие, если читатель вызывает sleep в цикле проверки условия.

Здорово, что sleep и wakeup не требуют специальной структуры данных для канала ожидания и не требуют от читателя и писателя знать друг о друге.

Код: каналы

Xv6 реализует каналы - pipes - с помощью sleep и wakeup. Глава 1 рассказывала о каналах - один процесс пишет байты в один конец канала, ядро копирует байты в буфер памяти, затем процесс читает байты с другого конца канала. Следующие главы расскажут, как файловые дескрипторы связаны с каналами, а пока изучим функции piperead и pipewrite.

Структура pipe описывает канал и содержит блокировку lock и циклический буфер data. Поля nread и nwrite считают байты, которые процесс читает из буфера и записывает в буфер. За байтом data[PIPESIZE - 1] логически следует байт data[0]. Буфер полон, когда nwrite == nread + PIPESIZE, и пуст, когда nwrite == nread. Следующий байт для чтения - data[nread % PIPESIZE]. Следующий байт для записи - data[nwrite % PIPESIZE].

Пусть два процессора параллельно вызвали piperead и pipewrite. Вызов pipewrite захватит блокировку, которая защищает инварианты счетчиков и буфера. Вызов piperead ожидает захвата блокировки в acquire. Вызов pipewrite выполнит цикл записи байтов и вызовет wakeup, если буфер окажется полон, чтобы читатели канала проснулись, а писатель уснет. Вызов sleep освободит блокировку pi->lock.

Теперь piperead захватит pi->lock, проверит, что pi->read != pi->nwrite - буфер не пуст - скопирует байты из канала и увеличит nread на число прочитанных байтов. Теперь буфер освободит место для записи, поэтому читатель вызывает wakeup и будит писателей.

Код канала использует отдельные каналы ожидания &pi->nread и &pi->nwrite для читателя и писателя - так ОС работает эффективнее, когда много писателей и читателей работают с одним каналом. Код канала вызывает sleep в цикле проверки условия - все, кроме первого процесса, уснут снова.

Код: wait, exit и kill

Глава 1 рассказывала, как родительский процесс вызывает wait и ждет, пока дочерний процесс вызовет exit - это пример работы sleep и wakeup. Родитель уже спит или выполняет другую работу, когда дочерний процесс завершается - вызов wait не должен потерять вызов exit. Xv6 помечает процесс как ZOMBIE, когда процесс вызывает exit, чтобы wait опознал завершенный процесс. Вызов wait помечает дочерний процесс как UNUSED, копирует код завершения и возвращает PID дочернего процесса. Процесс init усыновит осиротевшие процессы, если родительский процесс завершится раньше дочерних - init периодически вызывает wait. Каждому процессу назначен родитель, который освобождает ресурсы дочернего. Важно избегать взаимоблокировок между конкурентными вызовами wait и exit, exit и exit.

Вызов wait(addr) сперва захватывает блокировку wait_lock, которая гарантирует, что родитель не упустит вызов exit дочернего процесса. Вызов wait ищет в таблице процессов дочерний процесс в состоянии ZOMBIE, освобождает ресурсы процесса и структуру proc, копирует код завершения процесса по адресу addr и возвращает PID дочернего процесса. Функция wait вызовет sleep, если ни один дочерний процесс еще не завершился, и ждет, когда дочерний процесс вызовет exit. Функция wait часто удерживает две блокировки - wait_lock и pp->lock дочернего процесса. Функция wait захватывает блокировки только в порядке wait_lock, pp->lock, чтобы избежать взаимоблокировок.

Вызов exit выполняет такие шаги:

• Запоминает код завершения процесса.

• Освобождает часть ресурсов.

• Вызывает reparent, чтобы init усыновил дочерние процессы.

• Будит родительский процесс, который спит в wait.

• Помечает вызывающий процесс как ZOMBIE.

• Освобождает процессор.

Функция exit удерживает обе блокировки - wait_lock и p->lock. Блокировка wait_lock гарантирует, что родительский процесс не пропустит wakeup. Блокировка p->lock гарантирует, что родительский процесс, который вызвал wait, не тронет дочерний процесс, пока exit не освободит процессор вызовом swtch. Функция exit захватывает блокировки в том же порядке, что и wait, чтобы не допустить взаимоблокировки.

Кажется, что exit не должен будить родительский процесс, пока не пометил дочерний как ZOMBIE, но родительский процесс не захватит p->lock, пока scheduler не освободит p->lock.

Один процесс завершает другой вызовом kill. Функция kill не уничтожает процесс, так как процесс может все еще работать на другом процессоре. Функция kill устанавливает флаг p->killed процесса и будит, если процесс спал. Скоро процесс войдет или выйдет из режима ядра, а usertrap вызовет exit, когда увидит флаг p->killed.

Опасно, если kill разбудит процесс, но условие, которое процесс ждал, не выполнено. Xv6 вызывает sleep в цикле проверки условия, чтобы процесс еще раз проверил условие после возврата из sleep. Xv6 помещает и проверку флага p->killed в те циклы, где процесс способен безопасно завершить работу.

Циклы с вызовом sleep не проверяют флаг p->killed, если код выполняет атомарную операцию. Пример: драйвер virtio не проверяет p->killed, потому что дисковые операции входят в транзакцию. Драйвер повредит файловую систему, если прервет выполнение транзакции.

Вызов kill не завершит процесс, который ожидает завершения операции ввода-вывода диска, пока процесс не завершит системный вызов - тогда usertrap увидит p->killed и вызовет exit.

Блокирование процессов

Блокировка p->lock защищает не только поля структуры proc - state, chan, killed, xstate и pid - но и другие алгоритмы и структуры данных, которые связаны с процессом. Вот полный список:

• Блокировка p->lock защищает новые записи таблицы процессов.

• Блокировка p->lock скрывает процесс из виду, пока xv6 создает или уничтожает процесс.

• Блокировка p->lock не позволит вызову wait работать с процессом, пока процесс-зомби не освободил процессор.

• Блокировка p->lock не позволит планировщику другого процессора запустить процесс, когда процесс получил p->state = RUNNABLE, но еще не выполнил swtch.

• Блокировка p->lock гарантирует, что только один поток планировщика запустит RUNNABLE процесс.

• Блокировка p->lock не позволит прерыванию таймера приостановить процесс, пока процесс выполняет swtch.

• Блокировка p->lock и условная блокировка помогают вызову sleep не упустить вызов wakeup.

• Вызов kill захватит блокировку p->lock, чтобы процесс не завершился вызовом exit, а ядро не поместило в таблицу процессов другой процесс вместо него, пока kill проверяет p->pid и устанавливает p->killed.

• Вызов kill читает и пишет p->state атомарно с помощью p->lock.

Вызов wait работает с дочерними процессами текущего процесса, поэтому другой процесс не должен изменять указатели p->parent дочерних процессов, пока wait работает. Блокировка p->lock родителя не защищает дочерние процессы, потому что дочерний процесс указывает на родительский, а не наоборот. Приходится защищать дерево процессов глобальной блокировкой wait_lock.

Глобальная блокировка wait_lock защищает поле p->parent каждого процесса. Только родитель процесса изменяет p->parent, остальные процессы только читают. Блокировка wait_lock - условная блокировка - аргумент вызова sleep - которой пользуется функция wait, пока ждет завершения дочерних процессов. Дочерний процесс вызывает exit и удерживает wait_lock или p->lock, пока не присвоит p->state = ZOMBIE, разбудит родительский процесс и освободит процессор. Также wait_lock упорядочивает параллельные вызовы exit родительского и дочернего процессов, поэтому init гарантированно проснется.

Реальность

Планировщик xv6 следует политике планирования Round Robin - переключает процессы по кругу. Другие ОС реализуют политики планирования с приоритетами - процесс с высоким приоритетом работает чаще процесса с низким приоритетом. ОС часто ставят противоречивые цели и усложняют политики планирования. Пример: ОС хочет честно распределить время между процессами, но и поддерживать скорость обработки задач. Сложные политики иногда ведут к нежелательным последствиям - инверсиям приоритетов и конвоям процессов.

Инверсия приоритетов случается, когда процесс с низким приоритетом удерживает блокировку, которая нужна процессу с высоким приоритетом. Процесс с высоким приоритетом ожидает, пока освободится блокировка, но процесс с низким приоритетом выполняется реже, поэтому удерживает блокировку дольше. Процесс с низким приоритетом выполняет работу, хоть и медленно, а процесс с высоким приоритетом простаивает.

Конвой из нескольких процессов с высоким приоритетом сопровождает один процесс с низким приоритетом, если процесс с низким приоритетом удерживает блокировку, которая нужна процессам с высоким приоритетом. Конвой движется - выполняет работу - со скоростью процесса с низким приоритетом.

Планировщики используют дополнительные механизмы, чтобы устранить проблемы инверсии приоритетов и конвоев. Функции sleep и wakeup - простой и эффективный метод, но разработчики придумали и другие. Общая проблема таких методов - не потерять wakeup.

• Функция sleep в Unix отключала прерывания - для компьютера с одним процессором этого достаточно.

• Xv6 работает на нескольких процессорах, поэтому захватывает блокировку в sleep.

• Функция msleep во FreeBSD тоже захватывает блокировку.

• Функция sleep в Plan 9 принимает указатель на функцию - sleep захватывает блокировку и вызывает эту функцию, чтобы проверить условие, прежде чем освободит блокировку и уснет.

• Функция sleep в Linux работает с очередью процессов - очередь владеет отдельной блокировкой. Раздел 6.2. Blocking I/O в Linux Device Drivers рассказывает о работе с очередью ожидания в Linux.

Вызов wakeup работает медленно, когда обходит таблицу процессов - лучше, когда sleep и wakeup работают со структурой данных, которая хранит спящие процессы. Так sleep и wakeup работают с очередью процессов в Linux. Plan 9 зовет такую структуру местом встречи. Библиотеки потоков зовут такую структуру условной переменной, а sleep и wakeup называют wait и signal соответственно. Эти механизмы реализуют ту же идею - блокировка защищает условие ожидания, а процесс освобождает блокировку и засыпает атомарно.

Вызов wakeup в xv6 будит все процессы, которые спят на канале ожидания. Грохочущее стадо процессов конкурирует за проверку условия и нагружает процессор. Условные переменные предлагают две операции, чтобы будить процессы - signal будит один процесс, а broadcast будит все.

Процессы часто пользуются семафорами для синхронизации. Пример: счетчик семафора означает число свободных байтов в буфере канала или число дочерних процессов-зомби. Счетчик показывает число вызовов wakeup и не теряет ни одного. Также счетчик помогает справиться с ложными wakeup и грохочущим стадом процессов.

Трудно освобождать ресурсы, когда ОС завершает процесс вызовом kill. Процесс спит глубоко в ядре, если выполнил цепочку вызовов функций ядра перед вызовом sleep - придется раскрутить стек так, чтобы каждая функция освободила ресурсы. C++, Java и другие языки предлагают механизм исключений, который помогает освобождать ресурсы при аварийном завершении функции, но язык Си не поддерживает исключения. В Unix один процесс отправляет другому сигнал вызовом kill(pid, sig) - тогда процесс, который получил сигнал завершения SIGKILL, вернет -1 из системного вызова и сообщит об ошибке EINTR. Xv6 не поддерживает сигналы.

В xv6 случается, что kill устанавливает флаг p->killed после того, как процесс проверил условие, но прежде чем уснул. Процесс упустит вызов kill, уснет и не завершится, пока снова не наступит условие пробуждения.

В xv6 не каждый цикл вызова sleep проверяет флаг p->killed. Проверьте, какие циклы могли бы проверять p->killed и завершать работу.

ОС запускает процессы быстрее - за константное время вместо линейного - если ведет список свободных записей таблицы процессов, а не обходит всю таблицу. Xv6 использует линейный поиск по таблице процессов в allocproc.

Упражнения

• Функция sleep должна проверять lk != &p->lock, чтобы избежать взаимоблокировки. Представьте, что код

if(lk != &p->lock) {
  acquire(&p->lock);
  release(lk);
}

заменили на

release(lk);
acquire(&p->lock);

Как это нарушит работу sleep?

• Реализуйте семафоры в xv6, но не используйте sleep и wakeup. Используйте спин-блокировки. Замените вызовы sleep и wakeup в коде xv6 семафорами и оцените результат.

• Устраните состязание между kill и sleep так, чтобы процесс-жертва прерывал системный вызов, если получил kill после того, как проверил p->killed, но до вызова sleep.

• Разработайте план, в котором каждый цикл вызова sleep в xv6 проверяет флаг p->killed. Пример: пусть драйвер virtio немедленно завершает цикл while, когда убит другим процессом.

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

• Измените код scheduler в xv6 так, чтобы планировщик использовал RISC-V инструкцию WFI - Wait For Interrupt - когда нет ни одного процесса, готового к работе. Гарантируйте, что ни один процессор не выполняет WFI, когда хотя бы один процесс готов к работе.