WikiDer > Сериализация токенов

Serializing tokens

В Информатика, сериализация токенов представляют собой концепцию контроля параллелизма, возникающую в результате постоянного развития DragonFly BSD. Согласно с Мэтью Диллон, они больше всего похожи на SPL, за исключением того, что токен работает с несколькими Процессоры в то время как SPL работают только в пределах одного домена ЦП.

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

Сравнение с взаимным исключением (мьютекс)

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

  1. Распределение времени: планировщик пространства пользователя (США) пытается гарантировать, что у всех потоков есть шанс на выполнение, поэтому он запускает каждый поток в течение короткого периода времени (интервал времени), а затем переключается на другой поток.
  2. Параллельное выполнение: в многопроцессорных компьютерах поток может выполняться точно в то же время, что и другой поток на другом процессоре.
  3. Вытеснение: поток может вытеснить поток с более низким приоритетом, например, аппаратное прерывание или легкие потоки ядра.
  4. Добровольная блокировка: поток может спать, если ему нужно чего-то ждать, у него нет работы или вызывается функция, которая блокирует. Может заблокироваться даже вызов для получения блокировки.

В следующей таблице приведены свойства токенов и мьютексов.

Сериализация токенов против мьютексов
 Сериализация токеновМьютексы
Временное нарезаниеРаботаетРаботает
Параллельное исполнениеРаботаетРаботает
УпреждениеРаботаетРаботает
Добровольная блокировкаТерпит неудачуРаботает
Избегает тупикадаНет
Избегает инверсии приоритетадаНет

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

... Если вы посмотрите на FreeBSD-5, вы заметите, что FreeBSD-5 довольно часто передает удерживаемые мьютексы вниз по стеку подпрограмм, чтобы позволить некоторому очень глубокому процедурному уровню временно освободить мьютекс, чтобы переключить, заблокировать или разрешить с тупиком. Из-за этого во FreeBSD-5 наблюдается большое загрязнение кода (где некоторым процедурам для правильного функционирования необходимо предоставить сведения о мьютексах, удерживаемых другими несвязанными процедурами).

— Мэтью Диллон

пример

Следующее псевдокод и пояснения иллюстрируют, как работают сериализованные токены.

Пример PseudoCode с использованием сериализованных токенов
Поток АРезьба BДействие
lwkt_gettoken (T1); iter = list1.head;
... lwkt_gettoken (T1); // блоки // ждем токена T1
A получает токен T1 и использует его для получения синхронизированного доступа к list1, который используется обоими потоками.
lwkt_gettoken (T2); // блоки
// ждем токена T1
Вызов lwkt_gettoken (T2) A является функцией блокировки, поэтому A переходит в спящий режим и временно теряет свои токены. Он будет активирован, когда планировщик увидит, что доступны и T1, и T2.
// ждем T1 и T2
list1.head = list1.head.next; lwkt_releasetoken (T1);
B получает T1 и изменяет list1. Обратите внимание, что «iter» A по-прежнему указывает на старую главу списка.
// получаем новую версию головы: iter = list1.head; // создаем новый список: while (iter! = null) {list2.tail = iter; iter = iter.next;} lwkt_releasetoken (T1); lwkt_releasetoken (T2);
 Планировщик видит, что доступны и T1, и T2, поэтому он пробуждает поток A. Поскольку A был закодирован правильно, он обновляет свой итератор с новым заголовком list1 и выполняет с ним некоторые неблокирующие операции. Обратите внимание, что для A было бы лучше просто попросить оба жетона в начале.

Предшествующий уровень техники в ядре Дарвина

Mac OS Xс Дарвин ядро использует похожую технику (называемую воронка) для сериализации доступа к BSD часть ядра.

Смотрите также

использованная литература