Проблема инверсии приоритетов (производителя и потребителя)

Проблема инверсии приоритета. Оба последних решения имеют один недостаток - активное ожидание, которое, кроме бесцельной траты процессорного времени, могут иметь другие неожиданные последствия. Допустим, есть 2 процесса: процесс H с высокий приоритетом и процесс L - с низким. Допустим, процесс H переходит в состояние выполнения Run как только переходит в состояние готовности Ready. Допустим, процесс L находится в критической области. В это время процесс H переходит в состояние готовности и немедленно запускается. Он пробует войти в критическую область, но, поскольку там находится процесс L, он попадает в состояние вечного активного ожидания. Поскольку процесс L не может получить процессорное время, пока активен процесс H, оба процесса взаимозаблокируются. Такое состояние называется проблемой инверсии приоритета.

Проблема производителя-потребителя. Два процесса совместно используют буфер ограниченного размера. Производитель помещает данные в буфер. Потребитель считывает их оттуда. Допустим, буфер полон и производитель пытается поместить туда порцию данных, либо буфер пуст и потребитель пытается считать данные оттуда.

16. Проблема производителя – потребителя. Решение с помощью примитивов sleep и wake.

Наиболее удачным решением проблемы становится уход проблемного процесса в состояние блокировки, пока второй процесс не активизирует его. Для решения данной проблемы используются примитивы межпроцессного взаимодействия sleep, wake.

Примитивы sleep, wake

Sleep - системный запрос, в результате которого вызывающий процесс блокируется, пока его не разбудит другой процесс. Wake будит процесс, который указывается в качестве параметра.

#define N 100 // объем буфера

int count = 0;

void producer(void)

{

int item;

while(TRUE)

{

item = produce_item();

if (count == N)

sleep();

insert_item(item);

count++;

if (count == 1)

wake(consumer);

}

}

void consumer(void)

{

int item;

while(TRUE)

{

if(count == 0)

sleep();

item = remove_item();

count--;

if (count == N - 1)

wake(producer);

consume_item(item);

}

}

При таком решении возможно возникновение состояние состязания, поскольку не ограничен доступ к переменной count. Допустим, буфер пуст. Потребитель считал значение переменной count, сверил его с нулем. В этот момент произошла передача управления производителю. Производитель заполнил буфер одной порцией данных и послал сигнал wake. Поскольку потребитель не был в состоянии блокировки, сигнал wake пропал. После передачи управления потребитель уйдет в состояние блокировки. Через какое-то время производитель заполнит буфер и так же уйдет в состояние блокировки. Решением этой проблемы может стать использование переменной ожидания активации. Если сигнал wake послан процессу, не находящемуся в режиме блокировки, значение переменной увеличивается. При попытке блокировки данного процесса проверяется состояние переменной активации. Если она не равна нулю, блокировка не происходит, а значение переменной уменьшается.

17. Проблема производителя – потребителя. Мьютексы.

Мьютекс - переменная, которая может находится либо в блокированном, либо в неблокированном состоянии. Похож на семафор, но не умеет считать. Перед входом в критическую область выполняется функция lock. Если мьютекс не заблокирован, то происходит вход в приоритетную область и блокировка мьютекса, иначе происходит блокирование потока (процесса).

mutex_lock:

tsl rg, mutex

cmp rg, 0

jz ok

call thread_yield

jmp mutex_lock

ok:

ret

mutex_unlock:

mov mutex, 0

ret

Процедура обработки мьютекса использует команду tsl и, при невозможности входа в критическую область, вместо активного ожидания передает управление другому потоку либо уходит в состояние блокировки. При повторной передаче управления заново проверяет возможность входа в критическую область.

18. Проблема производителя – потребителя. Семафоры.

Семафоры - тип переменных, используемых для подсчета сигналов запуска, сохраненных на будущее. Может принимать значение 0 либо целое положительное число. Для работы с семафорами предусмотрены 2 функции: down, up.

Функция down сравнивает значение семафора с нулем. Если значение больше 0, то оно уменьшается на единицу и управление возвращается вызывающему процессу. Если значение равно 0, то процесс блокируется по этому семафору.

Операция up увеличивает значение семафора. Если предыдущее значение семафора было равно 0, то посылается сигнал активации по этому семафору и его значение не изменяется. Все операции с семафорами (сравнение, умеличение, уменьшение, блокировка, активация) выполняются атомарно.

#define N 100

semaphore mutex = 1;

semaphore empty = N;

semaphore full = 0;

void producer(void)

{

int item;

while(TRUE)

{

item = pruduce_item();

down(&empty);

down(&mutex);

insert_item(item)

up(&full);

up(&mutex);

}

}

void consumer(void)

{

int item;

while(TRUE)

{

down(&full);

down(&mutex);

item = remove_item();

up(&empty);

up(&mutex);

counsume_item(item);

} }

19. Проблема производителя – потребителя. Мониторы.

Монитор - набор процедур, переменных и других структур данных, объединенных в особый модуль. Процессы могут вызывать процедуры монитора, но при этом доступ к внутренним данным монитора имеют только процедуры, объявленные внутри него.

monitor mon1

{

int i;

int mas[10];

char condition;

void producer(void)

{

...

}

void consumer(void)

{

...

}

}

Доступ к переменным i, mas, condition имеют только функции producer, consumer. Эти функции могут вызываться из внешней программы. Реализации взаимных исключений способствует важное свойство монитора: при обращении к монитору в любой момент времени активным может быть только один процесс. Мониторы являются структурным компонентом языка программирования. Поэтому компилятор обрабатывает вызовы процедур монитора иначе, чем вызовы остальных процедур: первые несколько команд проверяют наличие в мониторе другого процесса. Кроме реализации взаимного исключения необходим способ блокировки тех процессов, которые не могут продолжать свою деятельность. Решение заключается во введении переменных состояния и двух функций: wait, signal. Когда процедура обнаруживает, что не может далее продолжать работу, она выполняет функцию wait на одной из переменных состояний. Это приводит к блокировке процесса, что позволяет другому процессу войти в монитор. С помощью функции signal процесс может активизировать другой процесс, заблокированный на одной из переменных состояния. Процесс, выполняющий функцию signal, должен немедленно покинуть монитор. Переменные состояния, в отличие от семафоров, не являются счетчиками, поэтому операция wait должна выполнятся раньше, чем операция signal, что можно оценить по значению переменных состояния.

В отличие от функций sleep и wake с функциями wait и signal не может произойти ситуация, когда другой один процесс пытается активизировать другой до того как он заблокируется. Даже в случае переключения контекста между проверкой и выполнением функции wait, первый процесс не сможет попасть в монитор, пока из него не выйдет второй.