Сериализация токенов - Serializing tokens
 | Эта статья поднимает множество проблем. Пожалуйста помоги Улучши это или обсудите эти вопросы на страница обсуждения. (Узнайте, как и когда удалить эти сообщения-шаблоны) (Узнайте, как и когда удалить этот шаблон сообщения)
|
В Информатика, сериализация токенов представляют собой концепцию контроля параллелизма, возникающую в результате постоянного развития DragonFly BSD. Согласно с Мэтью Диллон, они больше всего похожи на SPL, за исключением того, что токен работает с несколькими Процессоры в то время как SPL работают только в пределах одного домена ЦП.
Сериализация токенов позволяет программистам писать мультипроцессор -безопасный код, при котором они или подсистемы нижнего уровня не должны знать о каждом отдельном объекте, который также может содержать тот же токен.
Сравнение с взаимным исключением (мьютекс)
Токены и взаимное исключение (мьютекс) механизмы замки. В отличие от мьютексов, токены не исключают другие потоки из доступа к ресурсу, пока они заблокированы или спят. Поток, разделяющий ресурсы с другими потоками, может быть остановлен и запущен по разным причинам:
- Распределение времени: планировщик пространства пользователя (США) пытается гарантировать, что у всех потоков есть шанс на выполнение, поэтому он запускает каждый поток в течение короткого периода времени (интервал времени), а затем переключается на другой поток.
- Параллельное выполнение: в многопроцессорных компьютерах поток может выполняться точно в то же время, что и другой поток на другом процессоре.
- Вытеснение: поток может вытеснить поток с более низким приоритетом, например, аппаратное прерывание или легкие потоки ядра.
- Добровольная блокировка: поток может спать, если ему нужно чего-то ждать, у него нет работы или вызывается функция, которая блокирует. Может заблокироваться даже вызов для получения блокировки.
В следующей таблице приведены свойства токенов и мьютексов.
| Сериализация токенов | Мьютексы | |
|---|---|---|
| Временное нарезание | Работает | Работает |
| Параллельное исполнение | Работает | Работает |
| Упреждение | Работает | Работает |
| Добровольная блокировка | Терпит неудачу | Работает |
| Избегает тупика | да | Нет |
| Избегает инверсии приоритета | да | Нет |
Такие вопросы, как тупик и инверсия приоритета может быть очень трудно избежать и требует координации на многих уровнях ядра. Поскольку блокировка с помощью токенов не приводит к взаимоблокировке, а полученные токены не обязательно должны быть атомарными, когда последующие операции блокируются, это позволяет использовать гораздо более простой код, чем мьютексы.
... Если вы посмотрите на FreeBSD-5, вы заметите, что FreeBSD-5 довольно часто передает удерживаемые мьютексы вниз по стеку подпрограмм, чтобы позволить некоторому очень глубокому процедурному уровню временно освободить мьютекс, чтобы переключить, заблокировать или разрешить с тупиком. Из-за этого во FreeBSD-5 наблюдается большое загрязнение кода (где некоторым процедурам для правильного функционирования необходимо предоставить сведения о мьютексах, удерживаемых другими несвязанными процедурами).
— Мэтью Диллон
пример
Следующее псевдокод и пояснения иллюстрируют, как работают сериализованные токены.
| Поток А | Резьба 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 часть ядра.