Лекции по "Системному программированию"

Состояние состязания

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

Критические области

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

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

- два процесса  не должны одновременно находится в критической области;

- в программе  не должно быть предположений  о скорости или количестве  процессов;

- процесс,  находящийся вне критической  области, не может блокировать  другие процессы;

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

 

 

 

 

11. Решение проблемы взаимного  исключения. Запрет прерываний. Переменная  блокировки.

1. Запрет  прерываний. Самое простое решение  состоит в запрещении всех  прерываний при входе процесса  в критическую область. Таким  образом становится невозможным прерывание по таймеру, что исключает передачу процессора другому процессу. Недостатки:

- если прерывания  отключены пользовательским процессом  и, в результате какого-либо  сбоя, не включены обратно - это  приведет к краху системы;

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

2. Переменные  блокировки. Допустим, существует одна  совместно используемая переменная, изначально равная нулю. Если  процесс хочет попасть в критическую  область, он считывает значение  этой переменной, сравнивает ее  с нулем, и, в случае равенства,  изменяет значение на единицу  и входит в критическую область.  Если переменная равна 1, то  процесс ожидает (не уходит  в состояние блокировки или  готовности). Недостаток: один процесс  считывает переменную, успешно сравнивает  ее с нулем, но до того, как  успевает сменить ее значение  на единицу, управление получает  другой процесс. Он изменяет  значение на единицу и входит  в критическую область. При  передаче управления первому  процессу, он повторно устанавливает  значение переменной блокировки  в единицу и входит в критическую  область. Соответственно, в критической  области находится 2 процесса, что  противоречит условию №1. Повторной  проверкой значения переменной  такая ситуация не решается.

 

12. Решение проблемы взаимного  исключения. Строгое чередование. 

3. Строгое чередование.

while(TRUE)

{

while(turn);

critical_region();

turn = 1;

noncritical_region();

}

while(TRUE)

{

while(!turn);   //активное ожидание

critical_region();

turn = 0;

noncritical_region();

}

Переменная  turn, изначально равная 0, отслеживает, чья очередь входить в критическую область. Постоянная проверка значения переменной, в ожидании некоторого значения, называется активным ожиданием и является бесцельной тратой процессорного времени. Используется только в случае небольшого времени ожидания. Блокировка, использующая активное ожидание, называется спин-блокировкой. Недостаток: допустим, процесс 1 вышел из критической области и выполняет работу вне ее. Процесс 0 попадает в критическую область, быстро выполняет ее, передает очередь процессу 1, быстро выполняет свою некритическую секцию и возвращается к активному ожиданию. В этот момент оба процесса находятся в некритической области и процесс 1 блокирует процесс 0, что нарушает условие №3.

 

13. Решение проблемы взаимного исключения. Алгоритм Петерсона.

int turn;

int interested[2];

void enter_region(int process)

{

int other;

other = 1 - process;

interested[process] = TRUE;

turn = process;

while (turn == process && interested[other] == TRUE); // активное ожидание

}

void leave_region(process)

{

interested[process] = FALSE;

}

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

 

14. Решение проблемы взаимного  исключения. Команда TSL.

Команда TSL (Test and Set lock) - это решение требуют части аппаратного обеспечения. Некоторые компьютеры могут иметь команду tsl rg, lock. Команда считывает в регистр содержимое переменной lock, а в переменную lock сохраняет некоторое ненулевое значение. При этом гарантируется, что операция считывания и сохранения слова неделима (атомарная операция). Это означает, что во время выполнения команды не может произойти переключение контекста и другой процесс не сможет обратиться к слову lock, пока команда не выполнена до конца.

enter_ko:

tsl rg, lock

cmp rg, 0

jne enter_region

ret

leave_ko:

mov lock, 0

ret

Прежде чем  попасть в критическую область, процесс вызывает процедуру enter_region, которая выполняет активное ожидание до снятия блокировки, устанавливает новую блокировку и возвращает управление. Алгоритм надежен, однако использует активное ожидание.

 

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

Проблема  инверсии приоритета. Оба последних решения имеют один недостаток - активное ожидание, которое, кроме бесцельной траты процессорного времени, могут иметь другие неожиданные последствия. Допустим, есть 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, первый процесс не сможет попасть в монитор, пока из него не выйдет второй. 

20. Планирование и диспетчеризация.  Общие положения.

Со времен систем пакетной обработки данных планировщик  играет важную роль в функционировании ОС. При правильном выборе алгоритма  планирования можно значительно  повысить эффективность системы. С  появлением многозадачных интерактивных  ОС роль планировщика возросла. Теперь, кроме повышения эффективности, нужно обращать внимание на время  отклика отдельных задач. Тем  не менее планировщик должен эффективно использовать процессор, поскольку переключение между процессами требует значительных затрат:

- переключение  в режим ядра;

- сохранение  контекста;

- сохранение  карты памяти;

- запуск  блока управления памятью с  картой памяти нового процесса;

- восстановление  контекста нового процесса из  таблицы процессов;

- запуск  нового процесса и переключение  в режим пользователя.

В связи с  этим, количество переключений между  процессами следует минимизировать. С точки зрения планирования процессы бывают двух типов:

- процессы, ограниченные возможностями процессора. Характеризуются длинными периодами  использования процессора и редким  ожиданием ввода/вывода;

- процессы, ограниченные возможностями устройств ввода/вывода. Короткие периоды вычислений и частое ожидание устройств ввода/вывода.

Ключевым  вопросом планирования является выбор  момента для принятия решений. Самые  распространенные ситуации:

- создание  нового процесса - планировщику необходимо  выбрать: запустить дочерний процесс  либо продолжить выполнять родительский;

- когда процесс  завершает работу, планировщик должен  выбрать один процесс из списка  готовых;

- процесс  блокируется на операции ввода/вывода  либо семафоре;

- при возникновении  прерывания от устройства ввода/вывода  планировщик может восстановить  прерванный процесс либо запустить  процесс, ожидаюий это прерывание, либо какой-то другой процесс;

- при каждом  k-ом прерывании по таймеру алгоритмы планирования можно разделить на 2 больших типа:

‡ без  переключений - выбранный процесс  может работать до завершения блокировки либо пока сам не отдаст процессор;

‡ с переключениями (приоритетное плаинрование) - выбранному процессу позволяют работать некоторое максимально возможное фиксированное время. Если к концу этого времени процесс не заблокируется или не завершится, управление передается другому процессу. Такие алгоритмы требуют прерывание по таймеру.