Два подхода к планированию.

1. ОС о потоках ничего не знает.

ОС планирует 2 процесса: А и В. А получает кванты и процесс А сам планирует, кому его надо отдать.

Схема хороша тем, что каждый процесс может планировать так, как ему необходимо. Такой подход называется волоконный(Fiber).

2. OC знает все о потоках и планирует их напрямую.

Сам процесс, кроме общих ресурсов, ничего не несет. У любого потока имеется свой приоритет.

Этот подход называется поточным(Thread).

Синхронизация.

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

1. Критическая секция(часто используемый элемент синхронизации)

Пример: В банке есть счет 100 $. Программист пишет процедуру добавления денег на ваш счет.

void Add$(float delta)

{

float v = Get$();

v = v + delta;

Set$(v);

}

Вдруг процесс А хочет добавить 50$ и одновременно процесс В – 60$:

Потеряны 60$, потому что к Add$() получили доступ процесс А и процесс В параллельно.

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

Чтобы исправить положение добавим в функцию Add$()следующее:

Enter($) – войти в критическую секцию

Leawe($) – выйти из критической секции.

void Add$(float delta)

{

Enter($);

float v = Get$();

v = v + delta;

Set$(v);

Leawe($);

}

2. События.

Фактически логическая переменная, которая отвечает за то, произошел процесс или нет.

Говорят, что событие установлено, если true и сброшено, если false.

Функциональная спецификация:

- установить

- сбросить

- дождаться

Используется, когда надо синхронизировать процессы.

3. Барьер(б)

Используется, когда надо быть уверенным в том, что несколько процессов завершили свое действие.

Функциональная спецификация:

- зарегистрироваться на б

- разрегистрироваться на б

- достигли б

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

Лекция №8

4. Семафор – контролирует доступность нескольких однотипных ресурсов.

Семафор открыт, если счетчик > 0 и закрыт, если 0.

Функциональная спецификация:

- захватить семафор(если счетчик > 0, то он уменьшится на единицу, если счетчик = 0 – процесс находится в состоянии ожидания до тех пор, пока счетчик не стане равен 1 и, отнимая ее, продолжит работу)

- освободить семафор

Тупики.

Тупик(взаимная блокировка) – это ситуация, когда два или более процессов не могут продолжить свое выполнение без внешнего вмешательства.

Пример:

Для того, что бы в системе мог быть тупик, в обязательном порядке должны быть выполнены следующие условия:

1. в системе должен быть уникальные ресурсы

2. операционная система не может забрать у процесса ресурс, которым он владеет

3. владея уникальными ресурсами, процесс продолжает запрашивать другие ресурсы

4. в системе должен существовать цикл(на графе) из процессов, требующих ресурсов друг у друга

Что можно делать с тупиками:

1. избавиться от тупиков вообще(нарушить условия)

   0. убрать циклы

   1. заставить процесс запрашивать все и сразу

   2. можно нарушить со стороны процесса

   3. нарушение первого условия: избавиться от уникальных ресурсов. Любой процесс, который захочет работать с уникальным ресурсом заставлять работать не с уникальным ресурсом напрямую, а через специальный мониторинг, который управляет уникальными ресурсами.

Во многих случаях можно заменить уникальный ресурс драйвером.

2. Пытаться обойти тупик(потенциально возможно)

3. Тупик может быть, осталось только из него выйти.

   0. если тупик есть, то пусть будет

   1. если тупик есть в системе, то существует цикл. Находим линейный набор процессов, которые можно «убить» и все хорошо

   2. использовать механизм контрольных точек.