|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrzej Novosiolov 2:5020/400 02 Aug 2001 13:12:57
To : All
Subject : Re: мутексы, семафоры и т.п.
--------------------------------------------------------------------------------
On Wed, 01 Aug 2001 01:27:35 +0400, Alex Astafiev wrote:
AO>> Как реализованы семафоры, мутексы и т.п. средства синхронизации
AO>> потоков-процессов? Сам API в windows и POSIX для этих зверей я знаю,
AO>> Возможна ли реализация семафоров без явного запрещения переключения
AO>> потоков-процессов на время доступа к семафору?
В основе реализации всех объектов синхронизации лежат функции семейства
Interlocked*() - InterlockedIncrement(), InterlockedExchange() etc. С их
помощью легко реализуются критические секции - думаю, понятно, как. Теперь
легко синхронизировать доступ параллельных процессов к объектам синхронизации,
выделив каждому объекту свою персональную критическую секцию. Таким образом,
нет нужды блокировать переключение всех потоков в системе - блокируются только
те, которые в данный момент одновременно пытаются обратиться к одному и тому
же объекту синхронизации.
И действительно, в MSDN отмечено, что наиболее быстродействующими являются
Interlocked*() функции, потом идут критические секции, а все остальные объекты
существенно (раз в ~60..100) медленнее критических секций.
Итак, вся система синхронизации держится на существовании атомарных операций
вида прочитать-и-изменить.
Теперь самое интересное: на платформе Intel функции Interlocked*() один к
одному реализованы специальными командами процессора - XADD, CMPXCHG etc.
Hа RISC-архитектурах (Mips, Alpha и PowerPC) предусмотрены команды ldl_l
(load-linked или load-locked) и stl_c (store-conditional), позволяющие
определить, было ли кем-то другим изменено значение в ячейке памяти за время,
пока мы инкрементировали в регистре прочитанное оттуда число. Если было - мы
просто считаем, что "пришли позже", и начинаем цикл чтение-инкремент-запись
заново. Hа SPARC для тех же целей есть команда "compare and swap if equal".
Дальше надо копать в сторону микропрограммных реализаций этих команд.
Подозреваю, что разрешение конфликтов в случаях, когда несколько процессоров
одновременно хотят выполнить X-команду, напоминает разрешение конфликтов на
передачу пакетов в Ethernet-сетях - каждый из столкнувшихся участников делает
паузу на небольшой случайный интервал времени и пробует снова.
Кроме того, задача облегчается, если тактовый генератор выдаёт импульсы не на
все процессоры одновременно, а по очереди, по одному такту на процессор - в
этом случае мизерная вероятность конфликта двух процессоров на одном такте
превращается в нулевую. Hе знаю, используется этот подход в мультипроцессорных
системах. Я бы использовал :)
Подробности лежат по ссылкам:
http://msdn.microsoft.com/msdnmag/issues/0700/Win32/Win320700.asp
http://www3.sympatico.ca/n.rieck/docs/riscy-c-code.html
http://www.anticracking.sk/EliCZ/import/msdn_scalabil.htm
http://ftp.cdut.edu.cn/pub/document/book/POSIXMultithreadProgrammingPrimer.pdf
... 2:463/1124.5@fidonet, ICQ 8481158, http://surf.to/andrzej
--- ifmail v.2.15dev5
* Origin: SoftElegance (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: мутексы, семафоры и т.п.