[Перевод] Xv6: учебная Unix-подобная ОС. Глава 9. Еще раз о конкуренции09.04.2024 15:15

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

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

Трудно добиться быстродействия ядра, организовать параллельную работу потоков и при этом писать ясный код. Блокировки помогают параллельным потокам работать корректно, но иногда блокировки использовать трудно. Глава расскажет о хитрых сценариях с блокировками в xv6 и о сценариях без блокировок.

Сценарии с блокировками

Блокирование элементов кеша

Кеш блоков диска хранит по одной копии блока диска, иначе процессы внесут противоречивые изменения в разные копии одного и того же блока. Буфер кеша struct buf содержит копию блока диска и блокировку lock, чтобы процессы работали с буфером по очереди. Блокировки буфера недостаточно — представьте, что два потока одновременно обращаются к блоку диска, которого нет в кеше. Xv6 дополнительно объявляет блокировку bcache.lock, которая защищает набор блоков диска в кеше. Поток удерживает bcache.lock, когда проверяет, содержит ли кеш блок, и когда изменяет набор блоков кеша — читает блок с диска или вытесняет из кеша. Поток захватывает bcache.lock, находит блок в кеше, освобождает bcache.lock и захватывает блокировку lock буфера. Такой сценарий часто встречается — одна блокировка на набор элементов и по одной блокировке на каждый элемент.

Атомарные операции

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

Примеры:

Процедура yield захватит блокировку вызовом acquire в одном потоке, а освободит блокировку поток планировщика.
Код вызывает acquiresleep и ждет ввода-вывода, затем просыпается на другом процессоре.

Блокировки помогают изменять набор переменных атомарно и упорядочивают работу потоков с одной переменной. Язык Си говорит — состязание потоков ведет к неопределенному поведению программы. Блокировки защищают код от состязаний и неопределенного поведения.

Уничтожение объекта, который содержит блокировку

Уничтожить объект, который содержит блокировку, непросто — владение блокировкой не страхует от ошибок. Уничтожение объекта нарушит работу другого потока, который ожидает захвата блокировки в acquire. Проблему решит счетчик ссылок на объект — код уничтожит объект, когда уничтожит последнюю ссылку. Пример: код pipeclose следит за счетчиками pi->readopen и pi->writeopen файловых дескрипторов, которые ссылаются на канал.

Нежелательное кеширование

Компилятор способен выдать машинный код, который читает и пишет память не в том порядке, как исходный текст на языке Си. Пример: машинный код потока, который вызывает функцию killed, способен кешировать значение p->killed в регистре процессора и работать только с регистром — поток не узнает, что значение p->killed изменилось в памяти. Блокировки запрещают такое кеширование.

Сценарии, похожие на блокировки

Счетчики ссылок

Часто xv6 пользуется счетчиком ссылок или флагом, чтобы запретить уничтожать или повторно использовать объект — состояние процесса p->state, счетчики ссылок в структурах file, inode и buf служат этим целям. Блокировка защищает флаг или счетчик, а он защищает объект.

Файловая система пользуется счетчиками ссылок как разделяемой блокировкой, которую одновременно удерживают несколько процессов. Блокировку с единственным владельцем здесь использовать нельзя. Пример: цикл в namex разблокирует директорию, прежде чем спуститься на уровень ниже, иначе зависнет, когда встретит . или .. . Глава 8 рассказывала, как namex запрещает уничтожать директорию с помощью счетчика ссылок и не блокирует директорию.

Защита объекта различными способами

Иногда xv6 защищает один и тот же объект различными способами в течение жизни объекта. Примеры:

Блокировка kmem.lock защищает страницу физической памяти, когда страница свободна.
Блокировка канала pi->lock защищает страницу физической памяти, которую канал занимает.
Блокировка не защищает страницу физической памяти, когда страница содержит память программы. Код аллокатора гарантирует, что не отдаст страницу другому процессу.

Память нового процесса живет так: родительский процесс запрашивает память у kalloc, владеет памятью, передает память дочернему процессу, а когда дочерний процесс завершается, освобождает память вызовом kfree.

Отключение прерываний

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

Не используем блокировки

Иногда xv6 не защищает блокировками объекты, которые потоки используют совместно. Код спин-блокировок полагается на атомарные инструкции RISC-V. Ключевое слово volatile запрещает компилятору кешировать переменную started в main.c, которую процессоры опрашивают, пока ожидают разрешения к работе.

Xv6 содержит сценарии, когда один поток пишет данные, другой — читает, но блокировка не защищает данные. Пример: родительский процесс не защищает страницы памяти блокировкой, когда вызывает fork и пишет память дочернего процесса, потому что дочерний процесс еще не выполняется.

Пример показывает не проблему блокирования, а проблему порядка работы с памятью — см. главу 6. Один процессор не увидит операции записи другого процессора без барьера памяти. Родительский процесс освобождает блокировки, а дочерний захватывает — барьеры памяти в acquire и release гарантируют, что дочерний процесс увидит операции записи родительского.

Параллелизм

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

Каналы xv6 — хороший пример параллелизма. Каждый канал владеет блокировкой, поэтому процессы способны читать и писать разные каналы независимо друг от друга — одновременно на нескольких процессорах. Читатель и писатель одного канала работают по очереди, потому что по очереди захватывают блокировку.

Пример сложнее: переключение процессов. Два потока ядра работают параллельно и способны одновременно вызвать yield, sched или swtch. Каждый поток удерживает блокировку, но это разные блокировки, поэтому потоки не ждут друг друга. Потоки работают по очереди в коде scheduler, потому что по очереди ищут RUNNABLE-процесс в таблице процессов, поэтому увеличение числа процессоров не ускорит код переключения процессов.

Пример: параллельные потоки вызывают fork. Потоки поочередно захватывают pid_lock, kmem.lock и блокировки процессов, когда ищут UNUSED-процесс. В то же время параллельные вызовы fork копируют память процессов параллельно.

В каждом из примеров блокировки мешают потокам работать параллельно. Разработчик ядра способен придумать другие схемы работы потоков, чтобы улучшить производительность. Разработчик измеряет производительность, прежде чем оптимизировать — выбирает тот код, который выполняется чаще, блокировки, которые дольше остальных захвачены, где больше процессоров простаивают и где оптимизация даст наибольшую выгоду.

Упражнения

Измените каналы xv6 так, чтобы параллельные потоки на разных процессорах одновременно писали и читали в один и тот же канал.
Измените процедуру scheduler так, чтобы сократить время ожидания захвата блокировки, когда параллельные потоки ищут RUNNABLE-процесс в таблице процессов.
Избавьтесь от лишнего упорядочивания потоков в fork.