Механизмы синхронизации

2002 v.0.2
10. Механизмы синхронизации
Реализация семафоров
- Семафор

это динамическая структура, создаваемая в ядре, с помощью специального примитива (сервиса) ядра;
- P и V операции – примитивы ядра;
Примитив – процедура, реализованная в ядре, выполняющая неделимое действие; может вызываться из задач приложения
Вызов примитива – событие, обрабатываемое ядром (осществляется через механизм программных прерываний)

2002 v.0.2

type Семафор;
Создать_Семафор(S: Семафор; НачЗначение: Integer);
P(S:

Семафор);
V(S: Семафор);

ЯДРО

Реализация механизма семафоров

Создать_Семафор(Доступ,1);

P(Доступ);
. . .
V(Доступ);

ПРИЛОЖЕНИЕ

2002 v.0.2

type Семафор = ^рСемафор

рСемафор = record
Очередь: УказательНаОчередь;
НЗначение: 0..1;
ТЗначение: 0..1;
endtype

Реализация механизма семафоров (2)

Создать_Семафор(S: Семафор;
НачЗначение: Integer);
1. S:= new(Семафор);
2. S.Очередь:= СоздатьОчередь;
3. S.НЗначение:= НачЗначение;
4. S.ТЗначение:= НачЗначение;

2002 v.0.2
P(S: Семафор):

1. Запретить_прерывания();
2.

if (S.ТЗначение=0) then
2.1. Поставить_В_Очередь(ТекПроц,S.Очередь)
2.2. R:= Взять_Из_Очереди(ОчередьГотовых);
2.3. Переключение_Контекста(ТекПроц,R);
3. S.ТЗначение:= 0;
3. Разрешить_прерывания();

Примечание. Подразумевается, что
Переключение_Контекста()
разрешает прерывания

Реализация механизма семафоров (3)

2002 v.0.2
V(S: Семафор):

1. Запретить_Прерывания();

2. R:= Взять_Из_Очереди(S.Очередь);
3. Поставить_В_Очередь(R,ОчередьГотовых);
4. if(Очередь_Пуста(S.Очередь))
then S.ТЗначение:= 1;
5. Разрешить_Прерывания();

Реализация механизма семафоров (4)

2002 v.0.2
Пример сервисов, поддерживающих семафоры в

RTEK

KC_CloseSema – end the use of dynamic semaphore
KC_DefSemaCount – define a semaphore count
KC_DefSemaName – define the name of a previously
opened dynamic semaphore
KC_DefSemaName – define the properties of a semaphore
KC_GetSemaCount – get the current semaphore count
KC_GetSemaName – get the name of a semaphore
KC_GetSemaProp - get the properties of a semaphore
KC_GetSemaWaiters – get the number and list of tasks
waiting on semaphore
KC_InitSemaClassProp – initialize the semaphore object
class properties

2002 v.0.2
KC_LookupSema – look up

a semaphore’s name to get its
handle
KC_OpenSema – allocate and name a dynamic semaphore
KC_SignalSema – signal a semaphore
KC_SignalSemaM – signal multiply semaphores
KC_TestSema – test a semaphore
KC_TestSemaT – test a semaphore and wait for a specified
time if the semaphore is not DONE
KC_TestSemaW - test a semaphore and wait if the
semaphore is not DONE

Пример сервисов, поддерживающих семафоры в RTEK

2002 v.0.2
Разделяемый ресурс – данные, процедуры,

устройства, одновременно требуемые для выполнения нескольких задач

Использование семафоров

Задача 1 (P1 = а)

t

Задача 2 (P2 = b>a)

t

Задача работает не используя ресурс

Задача запрашивает (освобождает) ресурс, вызов P-операции (V- операции)

Задача работает с использованием ресурса

(!) Задача с более высоким приоритетом ждет пока менее приоритетная задача закончит работу с ресурсом

2002 v.0.2
Высокоприоритетная Задача 3 удерживается низкоприоритетной

Задачей 2 в течение временного интервала td , значение которого трудно просчитать заранее

Проблема инверсии приоритетов

Задача 1 (P1 = а)

t

Задача 3 (P3 = c>b)

t

Задача 2 (P2 = b>a)

t

td

2002 v.0.2
Протокол наследования приоритетов
Задача 1 (Р1

= а)

t

Задача 3 (Р3 = c>b)

t

Задача 2 (Р2 = b>a)

t

p1 = с

p1 = a

Приоритет Задачи 1, удерживающей ресурс, поднимается до значения приоритета Задачи 3 в момент, когда Задача 3 выставляет требование на этот ресурс

2002 v.0.2
Priority Ceiling протокол
Задача 1 (Р1

= а)

t

Задача 3 (Р3 = c>b)

t

Задача 2 (Р2 = b>a)

t

Р1 = с

Р1 = a

С Ресурсом связывается понятие приоритета;
В процессе проектирования приложения Ресурсу присваивается приоритет той использующей его задачи, который является наивысшим;
При запросе Задачей Ресурса ей присваивается приоритет этого Ресурса

2002 v.0.2
Недостатки механизма семафоров
Низкий уровень, слабая

защищенность от ошибок при программировании
Возможность использования P(S) и V(S) над одним семафором из разных задач (семафор S может быть установлен в 0 в одной задаче, а в 1 – в другой)
Возможность вызова V-операции над семафором без предварительного вызова P-операции
Не позволяет реализовать протокол наследования приоритетов, т. к. не определен процесс-«владелец» семафора

2002 v.0.2
Mutual Exclusion



Type mutex = (занят,

свободен);

Множество значений:

Множество действий:

Var S: mutex;
lock(S):
if(S=занят) then ждать(S=свободен);
Владелец:= ТекущийПроцесс;
S:= занят;
unlock(S):
if(Владелец=Текущий процесс) then
S:= свободен
else
Исклюение;

2002 v.0.2


Mutual Exclusion (2)

Создать_Mutex(S);


Приложение

Задача 1 -

владелец

t

Задача 3 – Ошибка!

t

Задача 2 – становиться владельцем

t

Бросается
Исключение !

2002 v.0.2

type mutex = ^рMutex

рMutex = record
Очередь: УказательНаОчередь;
Состояние: занят, свободен;
Владелец: процесс;
endtype

Реализация mutex

Создать_mutex(S: mutex);
1. S:= new(mutex);
2. S.Очередь:= СоздатьОчередь;
3. S.Владелец:= nill;
4. S.Состояние:= свободен;

2002 v.0.2
Реализация mutex (2)
Реализация протокола наследования

приоритетов требует модификации дескриптора задачи –TCB:

type TCB = ^рTCB
рTCB = record
Адрес: АдресПроцедуры;
Состояние: (Готов,Активен,Блокирован);
Приоритет: 1..128;
(!) ТПриоритет: 1..128;
Контекст: АдресСтека
endtype

2002 v.0.2

lock(S: mutex):
1. Запретить_Прерывания;

2. if(S.Состояние=занят) then
2.1. S.Владелец.ТПриоритет:=
ТекПроц.Приоритет;
2.2. ждать(S.Состояние=свободен);
3. S.Владелец:= ТекПроц;
4. S.Состояние:= занят;
5. Разрешить_Прерывания;

Примечание. Реализация ждать() показана на слайде 4

Реализация mutex (3)

2002 v.0.2
unlock(S: mutex);
1. Запретить_Прерывания;

2. if(S.Владелец=ТекПроц) then
2.1. R:= Взять_Из_Очереди(S.Очередь);
2.2. Поставить_В_Очередь(R,ОчердьГотовых)
2.3. S.Состояние:= свободен;
else Исключение;
3. S.Владелец.ТПриоритет:=
S.Владелец.Приоритет;
4. S.Владелец:= nill;
5. Разрешить_Прерывания();

Реализация mutex (4)