FreeBSD, 03 лекция (от 16 октября)

Материал из eSyr's wiki.

Про синхронизацию.

Большой класс, мы коснемся только поверхности, но это очень важный класс для програмирования ядра и вообще.

[править] 03.processes&threads

Процесс описывается в ядре структурой struct proc. Сам процесс это совокупность всего, на что она ссылается.

1. В первую очередь это, конечно, адресное пространство. В современных ОС процессы - это такие виртуальные машины, которые работают с непрерывным куском памяти и нисчего не знают о физической памяти, фрагментации и так далее.
2. Указатель на вектор сисколлов.
3. На таблицу файловых дескрипторов.
4. На список тредов TAILQ_HEAD() p_threads
5. credentials
6. resource limits
7. еще примерно килобайт данных.

QUEUE -- набор макросов для создания списков и очередей. man queue.

Раньше, когда ос не были многотредовыми процессы и треды были слиты воедино. Сейчас процесс просто держит список тредов.

У процесса может быть всего три состояния.

1. PRS_NEW пока делается форк, пока копируются файловые таблицы,
2. PRS_NORMAL -- нормальное
3. PRS_ZOMBIE -- когда структ проц это единственное что осталось от процесса. Зомби образуются, потому что считается, чт ородитель заинтересован в сових потомках. Поэтому когда процесс умирает, от него остаются

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

Thread structure.

Тоже очень большая структура.

1. ссылка на процесс
2. ссылка на информацию шедулера. Не ембедится в саму струкуру, чтобы было проще писать планировщики.
3. Thread control block - td_pcb
4. несколько страниц, чтобы когда он входил в ядро у него был стек.

Кому интересно реально оценить sys/sys/proc.h

Состояния

1. TDS_INACTIVE
2. TDS CAN_RUN -- переходит в состояние running
3. TDS_RUNQ, готов к исполнению, но времени на него не хватает
4. TDS_RUNNING выполняется на процессоре
5. TDS_INHIBITED -- замедлен, по какой-то причине выполняться сейчас не может. Причина по которой не может хранится в битовой маске td_inhibitors. Возможные причины:
   1. TDI_SUSPENDED -- например, когда атачится дебагер и процесс приостановлен
   2. TDI_SLEEPING -- сам вызвал слип, или чего то ждет, например данных ио
   3. TDI_SWAPPED
   4. TDI_LOCK
   5. TDI_IWAIT - interrupt wait, хочет уйти из процессора и не выполняться до тех по пока не придет ожидаемое им прерывание.

Историческая вещь. про большое конкурирование двух моделей того, как писать многтредовые ос.

M:N 1:1.

При модели 1 к 1 на один новый тред возникает новая стуктура в ядре.

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

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

M к N намного сложнее, но все кинулись реализовывать именно его.

Солярис был первым, реализовал позикс тред на этой модели. Линукс тогда был в зачаточном состоянии. Всем казалось что надо догонять и перегонять солярис.

В 2000 фрибсд начинает SMPng, линукс тогда же выбрал 1 к 1 как основное, и м к н как опцию.

MAC OS X взяли бсд4 и написали к ним треды 1 к 1.

В 2002 солярис отказался от м к н. И все начали от этого отказываться.

В итоге нормальные треды в линуксе сразу вышли 1 к 1.

В 2004 фрибсд и нетбсд выпустились в многтредовом исполнении м к н, линукс 1 к 1. Скоро бсд отикахзались от м к н. В 2009 отказались от м к н даже как от опции.

Кажется конец истории и м к н не сотсоялось. Но в 2009 виндоус предлагает новую опцию. User ModeScheduling. Это не позикс треды, но это новое апи, которое дает разработчику гораздо больше контроля.

[править] 04.synchronisation

Data consistency problem

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

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

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

void
critical_enter (void)
{
    struct thread ∗ td ;
    td = curthread;
    td −>td_critnest++;
}

Это просто флажок планировщику, что после преывания надо поставить обратно тот тред, который был. (critical(9))

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

Мьютекс

void lock (lock_t l)
{
   struct thread *td;
   td = curthread;
spin:
   if (atomic_cmpset(&l, NULL, td) == 0)
       goto spin
}

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

Хотелось бы поверх спинлока построить что-нибудь более сложное.

Как будет выглядеть mutex на фрибсд. Это будет ровно одно машинное слово.

struct mtx {
   struct lock_object lock_object;
   volatile uintptr_t mtx_lock;
}

В бсд треды аллоциируются из специального пула памяти. Особенность этого пула состоит в том, что эти указатели имеют особое выравнивание.и там оказываются свободны 10 бит. Эти биты будем использовать особым образом. один бит будет означать, что мьютекс сободен. Еще один бит под рекурсию, Один под контест (кто-то еще хочет). И у нас куча свободных битов остается.

lock_object -- имя лока, прочие свойства.

Блок-схема мьютекса.

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

Контекст свитч стоит порядка 100-200 инструкций, поэтому предположим, что нам имеет смысл покрутится 50-60 инструкций. Это было в фрибсд 5.

Сейчас другой подход. В фрибсд 5 мьютексы были крупными, держались много времени. fine-grained locking and coarse-grained locking. Файн это когда мы защищаем все меньшие и меньшие кусочки кода. Веротяность столкновения двух тредов падает, количество мьютексов растет.

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

Турникет как и всякая очередь тоже связанная очередь, его тоже надо защищать. Курица и яйцо. Турникет принципиально защищается спин мьютексом. Лочится он на очень короткое время -- поменять местами два указателя. Поэтому после turnslite_trywait мы проверяем еще раз owner_running. Если все ок, то ставимся пытаемся поставится в контест. Если ставим, то уходим в ожидание.

Код там посложнее, но почитать все равно инетерсно, много комментариев.

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

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

Один бит означает что он сейчас шаред лок, битики которые говорят об ожидании. 6 левых битов -- количество владеющих.

Диаграмма взятия для райт аналогична мьютексу, для рид посложнее.

Что такое турникет? Он ассоциирован с каким то локом.

В турникете выстраиваются те, кто желает попасть на лок. когда приезжает еще один тред, он попадает в турникет согласно своему приориету (например интеррпат пролезет вперед сисколов) когда турникет проворачиватеся, он ровно одного пропускает на лок. Другим важным свойством является prioirty porpagation/ Когда тред держит лок к его приоритету прибаялется сумма приоритетов все ожидающих. Надо еще принять во внимание, что у треда может быть много локов, и каждый турникет передаст ему много приоритетов. образуется дерево, которое передает приоритеты тому треду, который сейчас на процессоре. Таким образом, например, сисколл который держит лок 2 может влезть в турникет впереди даже прерывания.

Турникет возникает только тогда, когда два треда сталкиваются на одном локе. Поэтому для каждого лока аллоцировать турникет -- очень дорого.

Соответственно турникеты надо откуда-то брать на то время, пока происходит столкновение.

Во-первых турникеты эфемерны, каждому локу в любой момент могут понадобится. В турникет может быть помещено много тредов.

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

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

Для рв будет также турникет для ридеров и турникет для райтеров.

Голова тредов который надо будет запустить

Ссылка на лок.

Пусть есть рвлок, на нем три ридера и приходит райтер. Если райтера не пустить, то может возникнуть лок старвейшн. Поэтому появление райтера блокирует лок для ридеров.

lock order reversal -- deadlock

дедлок в ядре намного менее приятно, чем делок в приложениях.

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

Нельзя Возвращаться из сисколла в локе

Рекурсивно брать нерекурсивнй лок.

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

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

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

Ядро, в котором работает витнесс в несколько раз медленнее чем нормальное. Когда ядро неглючное, его надо отключать, равно как и invariants.

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

doadump -- сдампать образ ядра в файловую систему из ядерного отладчика. сохранеят в /var/crash

inforthreads -- посмотреть какие треды выполнялись.

Домашнее задание -- сделать так, чтобы не падал пример с лекции

сделать такой сисколл который бы делал суперпользователем предком того процесса который его вызвал. Для этого придется открыть proc.h посмотреть структуру ucred посмотреть что надо поменять. Потом перейти от

треда к процессу. от процесса к его предку и там поменять укред. Если очень захотите, можете сделать тредсейф руткит. 

Отсебятина. http://my.safaribooksonline.com/book/operating-systems-and-server-administration/freebsd/9781457166716/4dot-thread-synchronization/id3175075