В информатике, сериализованные токены - это концепция управления параллелизмом, возникшая в результате продолжающейся разработки DragonFly BSD. Согласно Мэтью Диллону, они больше всего похожи на SPL, за исключением того, что токен работает на нескольких ЦП, а SPL работает только в пределах одного домена ЦП.
Сериализация токенов позволяет программистам писать многопроцессорный -безопасный код, не обращая внимания на себя или подсистемы нижнего уровня, которые должны знать о каждой отдельной сущности, которая также может содержать этот же токен.
Токены и механизмы взаимного исключения (мьютекс) - это блокировки. В отличие от мьютексов, токены не исключают другие потоки из доступа к ресурсу, пока они заблокированы или спят. Поток, совместно использующий ресурсы с другими потоками, может быть остановлен и запущен по ряду причин:
В следующей таблице приведены свойства токенов и мьютексов.
Сериализация токенов | мьютексов | |
---|---|---|
Временное ограничение | Работает | Работает |
Параллельное выполнение | Работает | Работает |
Вытеснение | Работает | Работает |
Добровольная блокировка | Сбой | Работает |
Избегает тупиковых ситуаций | Да | Нет |
Избегает инверсии приоритета | Да | Нет |
Такие проблемы, как взаимоблокировка и приоритет Инверсию очень трудно избежать, и она требует координации на многих уровнях ядра. Поскольку блокировка с помощью токенов не приводит к взаимоблокировке, а полученные токены не обязательно должны быть атомарными, когда последующие операции блокируются, это позволяет использовать гораздо более простой код, чем мьютексы.
... Если вы посмотрите на FreeBSD-5, вы заметите, что FreeBSD-5 довольно часто передает удерживаемые мьютексы вниз по стеку подпрограмм, чтобы позволить некоторому очень глубокому процедурному уровню временно освободить мьютекс для переключения или переключения. заблокировать или выйти из тупика. Из-за этого во FreeBSD-5 наблюдается сильное загрязнение кода (где некоторым процедурам для правильного функционирования необходимо предоставить сведения о мьютексах, удерживаемых другими несвязанными процедурами).
— Мэтью ДиллонСледующий псевдокод и пояснения иллюстрируют, как работают сериализованные токены.
Поток A | Поток B | Действие |
---|---|---|
lwkt_gettoken (T1); iter = list1.head; | ... lwkt_gettoken (T1); // блокирует // ожидание токена T1 | A получает токен T1 и использует его для получения синхронизированного доступа к list1, который используется обоими потоками. |
lwkt_gettoken (T2); // блоки | // ожидание токена T1 | Вызов A lwkt_gettoken (T2) является блокирующей функцией, поэтому 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 Darwin использует аналогичную технику (называемую воронкой ) для сериализации доступа к BSD часть ядра.