|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitry Kalinin 2:5009/5.43 02 Aug 2001 21:25:22
To : Alexander Orlov
Subject : Re: мутексы, семафоры и т.п.
--------------------------------------------------------------------------------
31 Июл 01 14:42, Alexander Orlov -> All:
AO> Hello All!
AO> Как реализованы семафоры, мутексы и т.п. средства синхронизации
AO> потоков-процессов? Сам API в windows и POSIX для этих зверей я знаю,
AO> но как они устроены внутри? Возможна ли реализация семафоров без
AO> явного запрещения переключения потоков-процессов на время доступа к
AO> семафору? С запрещением переключения контекста на время доступа к
AO> объекту синхронизации задача вырождается почти в тривиальную, так что
AO> этот вариант мне не интересен. Когда-то давно я что-то слышал про
AO> соотвествующие алгоритмы, т.е. по крайней мере есть люди, занимающиеся
AO> этой проблемой.
AO> Поделитесь ифнормацией, ссылочками, библиографией и т.п.
Два года назад у нас преподавал предмет один очень умный мужик, эту тему
(семафоры, мутексы, мониторы ...) теоретически изучили от и до. Вот маленькая
выдержка из лекций:
Семафор это защищенная переменная, значение которой можно опрашивать и изменять
только при помощи операции инициализация-семафора и двух специальных операций P
и V.
Операция P над семафором S записывается как P (S) и выполняется по правилам :
если S > 0
то S: = S1
иначе ( ожидать на S).
Операция V над семафором S записывается как V(S) и выполняется по правилам:
если (один или более процессов ожидают на S)
то (разрешить одному из процессов продолжить работу)
иначе S:= S+1.
Различают два вида семафоров: двоичные семафоры, у которых S может принимать
значения 0 и 1, и считающие семафоры, где S может принимать неотрицательные
целые значения.
Подобно операции проверить_и_установить, операции инициализация_семафора, P(S) и
V(S) являются неделимыми. Участки взаимоисклю-ения по семафору S обрамляются
операциями P(S) и V(S). Если одновременно несколько процессов попытаются
выполнить операцию P(S), то только одному из них будет позволено это сделать, а
остальным придется ждать.
Семафоры и операции над ними могут быть реализованы как программно, так и
аппаратно. При программной реализации они размещаются в той части ядра
операционной системы, где осуществляется управление сменой состояний процессов.
Hа рис.3.14 приведен пример обеспечения взаимоисключения двух процессов с
использованием семафорной техники. Здесь примитив Р (активный) эквивалент для
рассматриваемого ранее примитива вход_взаимоисключения, а примитив V(S) для
выход_взаимоисключения.
Бинарные семафоры применяются для обеспечения доступа к разделяемым ресурсам в
режиме взаимоисключения и для синхронизации процессов.
Обеспечение взаимоисключения с помощью семафора
program Пример_семафора;
var активный: семафор;
procedure П1;
begin
while истина do begin Предшествующие операторы процесса П1;
Р(активный); Критический участок процесса П1;
V(активный);
Прочие операторы процесса П1;
end;
end;
procedure П2;
begin
while истина do begin
Предшествующие операторы процесса П2; Р(активный);
Критический участок процесса П2; V(активный);
Прочие операторы процесса П2;
end;
end;
{Основной процесс }
begin
инициализация_семафора(активный, 1);
П1; П2;
end;
Рис.3.14.
Считывающие семафоры особенно полезны в случаях, когда некоторый ресурс
выделяется из пула идентичных ресурсов. При инициализации такого семафора в его
счетчике указывается количественный показатель объема ресурса пула. Каждая
операция Р вызывает уменьшение счетчика на 1, показывая, что некоторому процессу
для использования выделен еще один ресурс из пула. Каждая операция V вызывает
увеличение значения счетчика на 1, показывая, что процесс возвратил ресурс в пул
и этот ресурс может быть выделен другому процессу. Если делается попытка
выполнить операцию Р, когда в счетчике семафора уже нуль, то соответствующему
процессу придется ждать момента, пока в пул не будет возвращен освобо-дившийся
ресурс, т.е. пока каким-либо процессом не будет выполнена операция V(S) над
нужным семафором.
Dmitry
--- 0f 0f 0e 0e 0e 0e 0c 0c 0a 09 09 06 03 00 00 00 ДВБВДБДДВДДДДДБДДДДД
* Origin: bESt reGUARdS (2:5009/5.43)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
