Xv6: учебная Unix-подобная ОС. Глава 6. Блокировки

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

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

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

Потоки конкурируют за доступ к структуре данных. Ядро кишит структурами, которые потоки используют совместно. Блокировки защищают данные при конкурентном доступе.

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

Глава расскажет, зачем нужны блокировки, как xv6 реализует и использует блокировки.

Состязания

Пример: два процесса вызывают wait, чтобы освободить память дочерних процессов, которые завершились. Ядро одновременно вызовет kfree дважды. Аллокатор памяти ведет список свободных страниц памяти. Вызов kalloc уберет страницу из списка, а kfree - вставит. Фрагмент кода показывает, как выглядит вставка элемента в список:

struct element {
  int data;
  struct element *next;
};

struct element *list = 0;

void push(int data) {
  struct element *l;
  l = malloc(sizeof *l);
  l->data = data;
  l->next = list;
  list = l;
}

Такой push работает в однопоточной системе, но не работает в многопоточной. Оба потока выполнят l->next = list, а затем одно присваивание list = l затрет другое.

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

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

Блокировки упорядочивают работу потоков, которые состязаются за доступ к структуре данных. Блокировка гарантирует, что только один поток выполняет участок кода.

struct element *list = 0;
struct lock listlock; // <--

void push(int data) {
  struct element *l;
  l = malloc(sizeof *l);
  l->data = data;
  acquire(&listlock); // <--
  l->next = list;
  list = l;
  release(&listlock); // <--
}

Инструкции между вызовами acquire и release называют критической секцией. Здесь блокировка защищает список list.

Блокировка помогают соблюдать инварианты данных. Инвариант - свойство данных, которое остается неизменным и гарантирует корректную работу структуры данных. Пример инварианта: list указывает на первый элемент списка, а поле next каждого элемента указывает на следующий. Операция push временно нарушает инвариант, но обязана восстановить. Блокировка не позволит другому потоку работать со списком, пока инвариант нарушен.

Поток выполняет критическую секцию атомарно. Атомарная операция работает как одно целое - другие операции не вмешиваются в работу атомарной. Пример: ассемблерная инструкция add процессора - атомарная.

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

Разработчики делают критические секции как можно короче. Поток держит блокировку дольше, если вызывает acquire в начале операции push, другие потоки ждут дольше - программы работают медленнее. Раздел "Используем блокировки" посоветует, как размещать вызовы acquire и release.

Код: блокировки

Xv6 предлагает два вида блокировок - спин-блокировки и спящие блокировки. Файл kernel/spinlock.h описывает спин-блокировку структурой spinlock. Поле locked = 0, когда блокировка свободна, и locked = 1, когда захвачена. Xv6 могла бы захватить блокировку так:

void 
acquire(struct spinlock * lk) // не работает!
{
  for (;;) {
    if (lk->locked == 0) {
      lk->locked = 1;
      break;
    }
  }
}

Этот код не исключает одновременной работы на разных процессорах. Процессоры одновременно увидят, что lk->locked == 0, и выполнят lk->locked = 1. Каждый процессор считает, что захватил блокировку.

Процессор должен проверять и захватывать блокировку атомарно. Процессор RISC-V предлагает инструкцию amoswap r, a, которая атомарно обменивает содержимое регистра r и ячейки памяти по адресу a. Процессор блокирует шину памяти, когда выполняет инструкцию, поэтому другие процессоры не обращаются к памяти, пока работает amoswap.

Функция acquire вызывает __sync_lock_test_and_set, которая атомарно записывает значение по указанному адресу и возвращает прошлое значение. Код обменивает lk->locked с 1. Поток захватил блокировку, если lk->locked был равен 0, иначе другой поток удерживает блокировку. Обмен 1 на 1 блокировке не повредит.

Функция acquire запоминает процессор в lk->cpu для отладки, как только захватит блокировку. Блокировка защищает и lk->cpu - код обращается к этому полю только когда захватит блокировку.

Spin - от англ. вертеть. Поток вертит цикл, пока захватывает блокировку, поэтому блокировка называется спин-блокировкой.

Функция release - обратная к acquire - очищает lk->cpu и освобождает блокировку. Достаточно присвоить lk->locked = 0, чтобы освободить блокировку. Стандарт языка Си разрешает компиляторам реализовать присваивание с помощью инструкций записи в память, которые не обязаны работать атомарно. Функция release вызывает функцию __sync_lock_release, которая выполняет присваивание атомарно.

Код: используем блокировки

Код xv6 часто работает с блокировками. Функции kalloc и kfree работают с блокировкой, которая защищает список свободных страниц памяти. Выполните упражнения 1 и 2, чтобы узнать, как эти функции работают без блокировок. Увидите, как трудно воспроизвести ошибку и отладить код. Попробуйте обнаружить неизвестные и не защищенные состязания в xv6.

Разработчики много трудятся, чтобы определить инварианты данных и защитить их блокировками. Эти правила помогут:

• Поток записывает ячейку памяти, а в это время другой поток читает или записывает эту же ячейку памяти. Блокировка защищает такую ячейку памяти.

• Блокировка защищает инварианты. Одна блокировка защищает группу ячеек памяти, из которых состоит инвариант.

Правила говорят, когда использовать блокировки, но не говорят, когда блокировки не нужны. Важно использовать как можно меньше блокировок, так как блокировки мешают программам работать параллельно. Блокировки не нужны системе с единственным потоком.

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

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

Пример: xv6 назначает блокировку каждому файлу. Каждый процесс работает с файлом независимо от того, с какими файлами работают другие процессы. Процессы могли бы одновременно работать с одним и тем же файлом, если блокировки бы защищали части файла.

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

Взаимные блокировки и порядок захвата блокировок

Ядро захватывает блокировки в одном порядке, иначе зависнет из-за взаимной блокировки.

Пример: один поток захватывает блокировки в порядке A, B, а другой поток - в порядке B, A. Первый поток удерживает A и захватывает B, но другой поток удерживает B и захватывает A. Оба потока ожидают вечно - ни один поток не освободит первую блокировку, пока не захватит вторую.

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

Код xv6 часто содержит сценарии с двумя блокировками из-за особенностей работы sleep. Глава 7 расскажет о функции sleep.

Пример: процедура consoleintr обрабатывает прерывания клавиатуры - ввод символов. Процедура захватывает блокировку cons.lock буфера клавиатуры. Процедура вызывает wakeup и будит процесс, который ожидает ввод. Функция wakeup захватывает блокировку p->lock этого процесса. Код ядра захватывает блокировки только в порядке cons.lock, p->lock.

Код файловой системы содержит последовательности блокировок длиннее двух. Процесс удерживает блокировки директории, структуры inode, области на диске, vdisk_lock драйвера и p->lock процесса, когда создает файл. Код ядра захватывает эти блокировки только в таком порядке.

Трудно следовать порядку захвата блокировок, если порядок захвата конфликтует с логической структурой программы. Представьте, что модуль M1 вызывает M2, но правило требует захватить блокировку M2 раньше M1.

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

Разработчик проектирует схему блокировок. Ошибка в схеме ведет к взаимной блокировке потоков. Каждая новая блокировка усложняет схему.

Блокировки в xv6

Повторные блокировки

Повторные или рекурсивные блокировки решают отдельные проблемы взаимных блокировок и порядка захвата блокировок. Повторные блокировки разрешают потоку захватить блокировку еще раз, если поток удерживает эту блокировку. Xv6 не разрешает захватывать блокировки повторно - ядро вызывает panic и останавливает работу.

Повторные блокировки усложняют работу программиста - поток войдет в критическую секцию дважды и нарушит атомарную операцию. Представьте такие функции f и g:

struct spinlock lock;
int data = 0; // защищена блокировкой lock

void f() {
  acquire(&lock);
  if (data == 0) {
    call_once();
    h();
    data = 1;
  }
  release(&lock);
}

void g() {
  aсquire(&lock);
  if (data == 0) {
    call_once();
    data = 1;
  }
  release(&lock);
}

Интуиция подсказывает, что код вызовет call_once единственный раз. Проблема возникнет, если h вызывает функцию g.

Код с нерекурсивными блокировками обрушит ядро при повторном захвате блокировки lock. Программист выяснит причину остановки ядра и исправит код.

Код с повторными блокировками захватит lock еще раз и снова войдет в критическую секцию - вызовет call_once дважды. Ядро не остановит работу, поэтому обнаружить и исправить такую ошибку сложнее.

Xv6 не использует повторные блокировки, чтобы упростить код. Оба вида блокировок работают, если разработчики соблюдают правила обращения с ними. Попробуйте превратить блокировки xv6 в повторные. Научите acquire запоминать, что текущий поток захватил блокировку и добавьте счетчик повторных захватов к структуре spinlock.

Блокировки и обработчики прерываний

Отдельные спин-блокировки защищают данные, которые потоки и обработчики прерываний используют совместно. Обработчик прерываний таймера clockintr увеличивает счетчик ticks, а функция sys_sleep ядра читает ticks. Блокировка tickslock упорядочивает доступ к счетчику ticks.

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

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

Xv6 включает прерывания, когда процессор не удерживает блокировок. Функция acquire вызывает push_off, а release - pop_off, чтобы считать захваченные блокировки. Процедура pop_off вернет флаг sstatus.SIE, который включает прерывания, в состояние до первого вызова push_off. Процедуры intr_on и intr_off включают и выключают прерывания соответственно.

Важно, что acquire вызывает push_off до записи lk->locked, иначе прерывание таймера повесит процессор. Функция release вызывает pop_off после освобождения блокировки по той же причине.

Интуиция подсказывает - процессор выполняет инструкции в том порядке, в каком программист инструкции записал. Такой взгляд подходит однопоточным программам, но не многопоточным. Компиляторы оптимизируют код: переупорядочивают инструкции чтения и записи памяти, кешируют переменные в регистрах и не обращаются к памяти. Процессор выполняет инструкции в другом порядке, когда инструкции не зависят друг от друга, потому что так быстрее. Пример: процессор встречает последовательность инструкций A, B и выполняет инструкцию B первой, потому что данные для A еще не готовы.

The RISC-V instruction set manual Volume I: unprivileged ISA

Hans-J Boehm. Threads cannot be implemented as a library. ACM PLDI Conference, 2005.

Представьте, что процессор упорядочит инструкции записи памяти так, что код push выполнит l->next = list после release. Другой процессор захватит блокировку и увидит элемент list с неверным указателем next.

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

Процедуры acquire и release создают барьер памяти вызовом __sync_synchronize, чтобы запретить процессору и компилятору переупорядочивать инструкции. Часто этого достаточно для защиты ядра xv6. Глава 9 расскажет о некоторых исключениях.

Спящие блокировки

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

Пример: поток удерживает блокировку, когда работает с файлом. Чтение и запись секторов диска занимает десятки миллисекунд.

Поток не уступает процессор другому потоку, когда удерживает спин-блокировку. Другой поток повесит процессор, если захватит ту же блокировку - вызов acquire не вызывает yield, поэтому не уступит процессор первому потоку. Вспомните: процессор отключает прерывания, когда захватывает спин-блокировку, поэтому таймер не переключит потоки.

Хотим блокировку, которая:

• разрешает прерывания

• разрешает уступать процессор, когда захвачена

• уступает процессор сразу, если acquire не захватил блокировку

Файл kernel/sleeplock.h предлагает спящие блокировки. Функция acquiresleep уступает процессор, когда ждет освобождения блокировки с помощью техник, о которых расскажет глава 7. Спящая блокировка содержит поле locked, которое защищает спин-блокировка lk. Функция acquiresleep вызывает sleep, которая атомарно освобождает lk и уступает процессор. Этот процессор выполняет другие потоки, пока acquiresleep ждет.

Спящие блокировки не отключают прерывания, поэтому спящие блокировки нельзя использовать в обработчиках прерываний. Функция acquiresleep уступает процессор, поэтому спящие блокировки нельзя использовать внутри критических секций, которые защищены спин-блокировкой - нельзя уступать процессор после захвата спин-блокировки. Спин-блокировки же можно использовать внутри критических секций, которые защищены спящими блокировками.

Спин-блокировки подходят для коротких критических секций лучше, чем спящие. Спящие блокировки лучше спин-блокировок в длинных критических секциях.

Реальность

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

Unix-подобные ОС поддерживают потоки POSIX - библиотеку pthreads. Процесс владеет несколькими pthread-потоками и выполнять потоки параллельно на нескольких процессорах. Библиотека pthreads предлагает потоки и блокировки в режиме пользователя, барьеры, одиночные и рекурсивные блокировки и т.д.

Библиотека pthreads требует поддержки со стороны ОС, чтобы работать в режиме пользователя. Примеры:

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

• Один pthread-поток запрашивает или освобождает память процесса, а ядро обновляет кеш таблиц страниц других процессоров.

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

L Lamport. A new solution of dijkstra’s concurrent programming problem. Communications of the ACM, 1974

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

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

Maurice Herlihy and Nir Shavit. The Art of Multiprocessor Programming, Revised Reprint. 2012.

Paul E. McKenney, Joel Fernandes, Silas Boyd-Wickizer and Jonathan Walpole. RCU Usage In the Linux Kernel: Eighteen Years Later

Упражнения

• Уберите вызовы acquire и release из kalloc и проверьте, нарушит ли это работу ядра. Что замечаете, пока работает xv6? Запустите usertests. Как объясните происходящее? Можете ли нарушить работу ядра, если вставите пустые циклы в критическую секцию kalloc?

• Уберите вызовы acquire и release из kfree и верните в kalloc. Нарушит ли это работу ядра? Что опаснее - убрать блокировки из kalloc или kfree?

• Два процессора одновременно вызывают kalloc - одному придется ждать. Измените kalloc.c так, чтобы процессоры работали параллельно, не ожидая друг друга.

• Напишите параллельную программу, которая использует потоки POSIX. Пример: напишите параллельную хеш-таблицу и оцените, как меняется число операций вставки и поиска в секунду, когда число процессоров увеличивается.

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