Сериализация токенов
 | В этой статье есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения )
|
В информатике DragonFly сериализация токенов представляет собой концепцию управления параллелизмом, возникшую в результате продолжающейся разработки BSD . По словам Мэтью Диллона , они больше всего похожи на SPL , за исключением того, что токен работает на нескольких процессорах , тогда как SPL работают только в домене одного процессора.
Сериализация токенов позволяет программистам писать многопроцессорно -безопасный код, при этом ни себе, ни подсистемам нижнего уровня не нужно знать о каждом отдельном объекте, который также может содержать один и тот же токен.
Сравнение с взаимным исключением (мьютексом)
[ редактировать ]Токены и механизмы взаимного исключения (мьютекс) являются блокировками . В отличие от мьютексов, токены не исключают доступ других потоков к ресурсу, пока они заблокированы или находятся в режиме ожидания. Поток, совместно использующий ресурсы с другими потоками, может быть остановлен и запущен по ряду причин:
- Временное разделение: планировщик пользовательского пространства (США) пытается гарантировать, что все потоки имеют равные шансы на выполнение, поэтому он запускает каждый поток в течение короткого периода времени (временной интервал), а затем переключается на другой поток.
- Параллельное выполнение: на многопроцессорных компьютерах поток может выполняться одновременно с другим потоком на другом процессоре.
- Вытеснение: поток может вытеснять поток с более низким приоритетом, например аппаратное прерывание или потоки облегченного ядра .
- Добровольная блокировка: поток может заснуть, если ему нужно чего-то ждать, ему нечего делать или он вызывает функцию, которая блокируется. Даже вызов для получения блокировки может быть заблокирован.
В следующей таблице приведены свойства токенов и мьютексов.
| Сериализация токенов | Мьютексы | |
|---|---|---|
| Временное разделение | Работает | Работает |
| Параллельное выполнение | Работает | Работает |
| Упреждение | Работает | Работает |
| Добровольная блокировка | Не удалось | Работает |
| Избегает тупиковой ситуации | Да | Нет |
| Избегает инверсии приоритетов | Да | Нет |
Таких проблем, как взаимоблокировка и инверсия приоритетов, очень трудно избежать, и они требуют координации на многих уровнях ядра. Поскольку блокировка с помощью токенов не приводит к взаимоблокировке, а полученные токены не обязательно должны быть атомарными при блокировке последующих операций, это позволяет использовать гораздо более простой код, чем мьютексы.
... Если вы посмотрите на FreeBSD-5, вы заметите, что FreeBSD-5 довольно часто передает удерживаемые мьютексы в стек подпрограмм, чтобы позволить какому-то очень глубокому процедурному уровню временно освободить мьютекс для переключения, блокировки или обработки. с тупиком. Из-за этого во FreeBSD-5 происходит сильное загрязнение кода (когда некоторым процедурам для правильной работы необходимо знать мьютексы, удерживаемые другими несвязанными процедурами).
— Мэтью Диллон
Пример
[ редактировать ]Следующий псевдокод и пояснения иллюстрируют работу сериализации токенов.
| Нить А | Нить Б | Действие |
|---|---|---|
lwkt_gettoken(T1); iter = list1.head; |
... lwkt_gettoken(T1); // blocks // waiting for token T1 |
A получает токен T1 и использует его для получения синхронизированного доступа к списку list1, который используется обоими потоками. |
lwkt_gettoken(T2); // blocks |
// waiting for token T1 |
Вызов lwkt_gettoken(T2) со стороны A является блокирующей функцией, поэтому A переходит в режим сна и временно теряет свои токены. Он будет разбужен, когда планировщик увидит, что доступны и T1, и T2. |
// waiting for T1 and T2 |
list1.head = list1.head.next; lwkt_releasetoken(T1); |
B получает T1 и модифицирует список1. Обратите внимание, что «iter» в A по-прежнему указывает на старую главу списка. |
// get the new version of the head:
iter = list1.head;
// make new list:
while (iter != null) {
list2.tail = iter;
iter = iter.next;
}
lwkt_releasetoken(T1);
lwkt_releasetoken(T2);
|
Планировщик видит, что доступны и T1, и T2, поэтому он пробуждает поток A. Поскольку A был закодирован правильно, он обновляет свой итератор, добавляя в него новый заголовок списка1 и выполняет над ним некоторые неблокирующие операции. Обратите внимание, что для А было бы лучше просто попросить оба жетона в начале. |
Уровень техники в ядре Дарвина
[ редактировать ]Mac OS X использует Ядро Darwin аналогичную технику (называемую воронкой ) для сериализации доступа к BSD- части ядра.