Примечание. Авторы рекомендуют читать книгу вместе с исходным текстом xv6. Авторы подготовили и лабораторные работы по xv6.
Xv6 работает на RISC-V, поэтому для его сборки нужны RISC-V версии инструментов: QEMU 5.1+, GDB 8.3+, GCC, и Binutils. Инструкция поможет поставить инструменты.
ОС часто выполняет процессов больше, чем доступно процессоров, поэтому ОС планирует работу процессов. Процессы не знают, как ОС распределяет время процессора между ними - каждый процесс владеет виртуальным процессором. ОС мультиплексирует процессы на процессоре - переключает процессы через равные промежутки времени.
Мультиплексирование
Xv6 переключает процессы, когда:
Процесс добровольно уступает процессор, когда вызывает
sleep
и ожидает события - завершения ввода-вывода устройства или канала, завершения дочернего процесса.Таймер прерывает процесс - xv6 отнимает управление у процесса и передает другому.
Мультиплексирование и виртуальная память разрешают процессу работать так, словно он один на компьютере.
Мультиплексирование ставит перед ОС такие задачи:
Как переключать процессы? Код написать труднее, чем рассказать о переключении процессов.
Как вынудить процесс уступить процессор, чтобы процесс об этом не знал? Xv6 полагается на прерывания таймера, чтобы переключать процессы.
Как избежать взаимоблокировок из-за переключения процессов?
Как освободить ресурсы процесса, когда он завершает работу? Пример: процесс не способен освободить стек ядра, пока выполняется.
Как выполнять системные вызовы, которые управляют состоянием процесса? Каждый процессор запоминает, какой процесс выполняет, чтобы такие системные вызовы работали.
Процесс уступает процессор с помощью функций
sleep
иwakeup
. Нельзя терять вызовыwakeup
из-за состязаний процессов.
Xv6 решает эти проблемы как можно проще, но код все равно вышел непростым.
![Так xv6 переключается с одного процесса на другой](https://webcf.waybackmachine.org/web/20240320074636/https://habrastorage.org/webt/hi/jh/-i/hijh-icyzjw-0beud8ygobdmkoq.png)
Код: переключение контекста
Рисунок показывает шаги переключения процесса:
Системный вызов или прерывание переключает процесс в режим ядра.
Поток ядра переключается на поток планировщика текущего процессора.
Планировщик переключается на поток ядра другого процесса.
Поток ядра возвращается в режим пользователя.
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
, когда хотя бы один процесс готов к работе.