|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Victor Petrov 2:5030/744.113 03 Aug 2001 14:16:21
To : Alexander Orlov
Subject : мутексы, семафоры и т.п.
--------------------------------------------------------------------------------
В письме от Alexander Orlov к All от Вторник Июль 31 2001 14:42 писалось:
AO> Как реализованы семафоры, мутексы и т.п. средства синхронизации
AO> потоков-процессов? Сам API в windows и POSIX для этих зверей я знаю, но
AO> как они устроены внутри? Возможна ли реализация семафоров без явного
AO> запрещения переключения потоков-процессов на время доступа к семафору?
Все имеющиеся алгоритмы (например, P-V семафоры Дейкстры) основаны на том, что
аппаратура предоставляет возможность "атомарного" выполнения некоторой
инструкции, которая одновременно имзменяет значение переменной и возвращает
старое значение (кстати, специально для этого фирма Intel ввела в i486 команды
cmpxchg и xadd, хотя можно пользоваться и старой доброй xchg). "Атомарность"
означает, что во время выполнения этой инструкции не может произойти
переключение потоков, а также (в многопроцессорной системе) другие процессоры не
смогут обратиться к той же области памяти.
Предположим, что у нас есть (реализованная на ассемблере) атомарная операция
swap (a, b), которая меняет местами значения переменных a и b. Тогда
синхронизацию можно организовать следующим образом. Заводим переменную
semaphore. Сначала она равна нулю (семафор свободен), но иногда становится
равной 1 (семафор занят). Определяем следующие операции:
volatile int semaphore = 0;
void lock_semaphore (void);
{
int a = 1;
do swap (a, semaphore) while (a == 1);
return;
}
void release_semaphore (void);
{
semaphore = 0;
}
Таким образом, lock_semaphore ждет, пока семафор станет свободным, и занимает
его, а release_semaphore освобождает семафор.
Теперь критичные участки программы оформляются так:
lock_semaphore ();
сделать что-то полезное;
release_semaphore ();
Гарантируется "атомарность" выполнения критичных участков в том смысле, что во
время выполнения одного такого участка не может начаться выполнение другого
такого участка другим потоком (или процессором в многопроцессорной системе).
(Такие участки иногда называются "мониторами").
С помощью мониторов можно организовать другие, более сложные и эффективные
процедуры синхронизации.
В заключение замечу, что эти средства по-настоящему необходимы только в
многопроцессорной системе; при наличии одного процессора намного проще и
эффетивнее временно запрещать переключение потоков.
Да, если будешь это реализовывать на языке высокого уровня, "объясни"
компилятору, что переменная semaphore может изменяться "извне", а то он может
попытаться "соптимизировать" эти процедуры. В языке C для этого существует
спецификатор volatile.
Victor
--- EOS v0.70
* Origin: Свобода - это познанная необходимость. (2:5030/744.113)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
