Решение задачи взаимного исключения с помощью специальных команд ЦП (активное ожидание)

Постановка задачи взаимного исключения.

Необходимо согласовать работу n>1 параллельных потоков при использовании некоторого критического ресурса таким образом, чтобы удовлетворить следующим требованиям:

1. Одновременно внутри критической секции должно находиться не более одного потока.
2. Критические секции не должны иметь приоритета по отношению друг к другу.
3. Остановка какого-либо потока вне его критической секции недолжна влиять на дальнейшую работу потоков при использовании критических ресурсов.
4. Любой поток может переходить в любое состояние вне пределов своей критической секции.
5. Решение о вхождении потоков в их критические секции при одинаковом времени поступления запросов не откладывается на неопределенный срок, а является конечным во времени.
6. Освобождение критического ресурса и выход из критической секции должны быть произведены потоком, использующим критический ресурс, за конечное время.
7. Относительные скорости выполнения потоков неизвестны и произвольны.

Необходимость синхронизации.

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

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

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

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

Решение задачи взаимного исключения с помощью запрещения прерываний.

while (true){

DisableInterrupts();

CS();

EnableInterrupts();

NCS();

}

Недостатки:

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

Алгоритм Петерсона.

int ready[2]={0,0}; // Номера потоков.

int turn=0; // Номер потока, имеющего приоритет при входе в критическую секцию.

while (true) {

ready[i]=1;

turn=1-i;

while ((ready[1-i]) && (turn=1-i));

CS();

ready[i]=0;

NCS();

}

Является приоритетным для многопроцессорных систем.

Алгоритм булочной.

Решение задачи взаимного исключения с помощью специальных команд ЦП (активное ожидание).

I. Test&Set.

int Test&Set (int *a) {

int tmp;

tmp =*a;

*a=1;

return tmp;

} // По указанному адресу записываем 1, а возвращаем то, что было раньше.

int lock=0; // 0 — свободен, 1 — занят.

while (true) {

while (Test&Set(&lock)) // Как только ресурс освободится, войдем в КС.

(*);

CS();

lock=0;

NCS();

}