Тема 7. Межпроцессное взаимодействие (Inter-Process Communication, ipc)
Задачи IPC
Передача данных между процессами
Обеспечение детерминированной работы процессов (взаимоисключение)
С
A=0x10
инхронизация взаимодействующих процессов
Состояние состязания (гонок)
Race Condition
Недетерминированное исполнение
P: a, b, c;
Q: d, e, f;
P: x=2; y=x+1;
Q: y=3; x=y-2;
Условие Бернстайна
R(a), W(a)
W(P)
∩ W(Q)
== ∅
P, Q: W(P) ∩ R(Q) == ∅
R(P) ∩ W(Q) == ∅
следовательно, выполнение детерминировано
Взаимоисключение
Требование запрета одновременной записи и чтения разделённых данных более, чем одним процессом
Критическая секция (область) — часть программы, в которой происходит доступ к разделяемым данным
Условия корректной совместной работы
Два процесса не должны одновременно находиться в критической области
Программа не должна делать предположений о скорости работы или количестве процессоров
Процесс, находящийся вне критической области, не должен блокировать другие процессы
Процесс не должен бесконечно ожидать попадания в критическую секцию
Способы организации взаимоисключения
1) Запрет прерываний
2) Переменная блокировки
3) Строгое чередование
4) Алгоритм Петерсона
5) Алгоритм Лэмпорта
6) Аппаратная поддержка
6.1) TSL
6.2) XCHG
1) Запрет прерываний
sti
cli
label: sti
jmp label
2) Переменная блокировки
while (1) {
while (lock == 1);
lock = 1;
do_crit_work();
lock = 0;
do_noncrit_work();
}
3) Строгое чередование
while (1) {
while (turn);
do_crit_work();
turn = 1;
do_noncrit_work();
}
или
while (1) {
while (!turn);
do_crit_work();
turn = 0;
do_noncrit_work();
}
4) Алгоритм Петерсона
int turn;
int flag[2];
void lock(int process); {
int other = 1 - process;
flag[process] = 1;
turn = process;
while (turn == process && flag[other]);
}
void unlock(int process);
{
flag[process] = 0;
}
5) Алгоритм Лэмпорта («кондитерской»)
#define N 5
int choosing[N]; int ticket[N];
void lock(int process) {
choosing[process] = 1;
ticket[process] = 1 + max(ticket);
choosing[process] = 0;
for (i = 0 ; i < N ; i++) {
while (choosing[i]);
while (ticket[i] != 0 && (ticket[process] > ticket[i] || (ticket[process] == ticket[i] && process > i)))
}
}
void unlock(int process) {
ticket[process] = 0;
}
6.1) Аппаратная поддержка (TSL, Test and Set Lock)
lock:
TSL RX, LOCK
CMP RX, #0
JNE lock
RET
unlock:
MOV LOCK, #0
RET
6.2) Аппаратная поддержка (xchg)
lock:
MOV RX, #1
XCHG RX, LOCK
CMP RX, #0
JNE lock
RET
unlock:
MOV LOCK, #0
RET
Недостатки активного ожидания
Трата ресурсов впустую
Проблема инверсии приоритета
Тема 8. Примитивы межпроцессного взаимодействия
Проблема производитель-потребитель
Два процесса одновременно используют буфер ограниченного размера
Проблемы:
Запись в полный буфер
Чтение из пустого буфера
#define N 10
int count = 0;
void producer(void)
{
int item;
while (TRUE) {
item = produce_item();
if (count == N)
sleep();
insert_item();
count = count + 1;
if (count == 1)
wakeup(consumer);
}
void consumer(void)
{
int item;
while (TRUE) {
if (count == 0)
sleep();
item = remove_item();
count = count – 1;
if (count == N-1)
wakeup(producer);
consume_item(item);
}
Примитивы межпроцессного взаимодействия
1) Семафоры
2) Мьютексы
3) Мониторы
4) Очереди сообщений
5) Барьеры