Теоретические основы параллельного программирования: принцип организации критических секций.

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

Рассмотрим программно-аппаратный способ организации критических секций. Этот способ основан на наличии в составе команд процессора специальной команды, выполняющей сразу 2 операции, а именно считывание данных из памяти и занесение данных в память. Впервые такая команда появилась в IBM 360 (команда TS). Команда была двухоперандной: TS <oп1> <oп2> Значение oп2 присваивалось оп1 а в оп2 записывалась «1». Аналогом в системе команд Intel IA-32 является команда XCHG. Эта команда отличается от всех других команд Intel IA-32 тем, что во время ее выполнения на шину управления всегда подается особый сигнал - #lock (блокирует ПДП для всех других периферийных устройств).

      Xchg eax, status      status – статус критической секции.

      Процесс, который хочет занять критическую секцию, должен выполнить следующие инструкции:

      Wait:          move eax,1

            Xchg eax, status

            Cmp eax,1

            Je wait

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

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

      Mov status,0

      Способ универсален и работает в том числе и на многопроцессорных компьютерах (из-за сигнала #LOCK). Все современные ОС построены на критических секциях, а все критические секции для IA-32 построены на команде xchg.

      В ОС windows существует функция LONG InterlockedExchange(LONG * status, LONG * value)

      Благодаря этой функции программа может сама организовать критические секции без обращения к ядру ОС. Значение Value записывается на место старого значения (*Status), а старое значение  (*Status) возвращается функцией InterlockedExchange.

      Использование для организации критической секции:

      LONG         Status = 0;

            …

      While (InterlockedExchange(&Status, 1) == 1);

            …        

            … критическая секция

            …

      Status = 0;

      Такой вариант приводит к полной загрузке ЦП (зависание в нити, ожидающей обслуживания). Для решения проблемы используется вариант:

            …

      While (InterlockedExchange(&Status, 1) == 1){sleep(0) ;}      //Перевод текущей нити в

            …                                                                                // конец списка обслуживания

            … критическая секция

            …

      Однако такой вариант все еще не удовлетворяет условию 3. Чтобы все работало:

      Time(&t)

      While (InterlockedExchange(&Status, 1) == 1)

{

sleep(0);

time(&t1);

if ((t1-t) > 1) return false;

}     Return true;                       //Вход в КС.