Многопроцессорный вычислительный комплекс на основе коммутационной матрицы

Страница: 12/18

struct semaphore

{

int lock;

};

Init(semaphore)

struct semaphore semaphore;

{

semaphore.lock = 1;

}

Pprim(semaphore)

struct semaphore semaphore;

{

while (read_and_clear(semaphore.lock));

}

Vprim(semaphore)

struct semaphore semaphore;

{

semaphore.lock = 1;

}

Процесс повторяет инструкцию read and clear в цикле до тех пор, пока не будет считано значение, отличное от нуля. Начальное значение компоненты семафора, связанной с блокировкой, должно быть равно 1. Как таковую, данную семафорную конструкцию нельзя реализовать в составе ядра операционной системы, поскольку работающий с ней процесс не выходит из цикла, пока не достигнет своей цели. Если семафор используется для блокирования структуры данных, процесс, обнаружив семафор заблокированным, приостанавливает свое выполнение, чтобы ядро имело возможность переключиться на контекст другого процесса и выполнить другую полезную работу. С помощью функций Pprim и Vprim можно реализовать более сложный набор семафорных операций, соответствующий тому составу, который определен в разделе “Определение семафоров”. Для начала дадим определение семафора как структуры, состоящей из поля блокировки (управляющего доступом к семафору), значения семафора и очереди процессов, приостановленных по семафору. Поле блокировки содержит информацию, открывающую во время выполнения операций типа P и V доступ к другим полям структуры только одному процессу. По завершении операции значение поля сбрасывается. Это значение определяет, разрешен ли процессу доступ к критическому участку, защищаемому семафором.

Алгоритм операции P:

/*

Операция над семафором типа P

входная информация:

(1) семафор;

(2) приоритет;

выходная информация:

0 - в случае нормального завершения;

1 - в случае аварийного выхода из состояния приостанова по cигналу, принятому в режиме ядра;

*/

{

Pprim(semaphore.lock);

уменьшить (semaphore.value);

если (semaphore.value >= 0)

{

Vprim(semaphore.lock); вернуть (0);

}

/* следует перейти в состояние приостанова */

если (проверяются сигналы)

{

если (имеется сигнал, прерывающий нахождение в состоянии приостанова)

увеличить (semaphore.value);

если (сигнал принят в режиме ядра)

{

Vprim(semaphore.lock);

вернуть (-1);

}

в противном случае

{

Vprim(semaphore.lock);

longjmp;

}

}

}

поставить процесс в конец списка приостановленных по семафору;

Vprim(semaphore.lock);

выполнить переключение контекста;

проверить сигналы (см. выше);

вернуть (0);

}

В начале выполнения алгоритма операции P ядро с помощью функции Pprim предоставляет процессу право исключительного доступа к семафору и уменьшает значение семафора. Если семафор имеет неотрицательное значение, текущий процесс получает доступ к критическому участку. По завершении работы процесс сбрасывает блокировку семафора (с помощью функции Vprim), открывая доступ к семафору для других процессов, и возвращает признак успешного завершения. Если же в результате уменьшения значение семафора становится отрицательным, ядро приостанавливает выполнение процесса, используя алгоритм, подобный алгоритму sleep: основываясь на значении приоритета, ядро проверяет поступившие сигналы, включает текущий процесс в список приостановленных процессов, в котором последние представлены в порядке поступления, и выполняет переключение контекста.

Алгоритм V

/*

Операция над семафором типа V

входная информация: адрес семафора

выходная информация: отсутствует

*/

{

Pprim(semaphore.lock);

увеличить (semaphore.value);

если (semaphore.value <= 0)

{

удалить из списка процессов, приостановленных по семафору, первый по счету процесс;

перевести его в состояние готовности к запуску;

}

Vprim(semaphore.lock);

}

Операция V получает исключительный доступ к семафору через функцию Pprim и увеличивает значение семафора. Если очередь приостановленных по семафору процессов непустая, ядро выбирает из нее первый процесс и переводит его в состояние "готовности к запуску". Операции P и V по своему действию похожи на функции sleep и wakeup. Главное различие между ними состоит в том, что семафор является структурой данных, тогда как используемый функциями sleep и wakeup адрес представляет собой всего лишь число. Если начальное значение семафора - нулевое, при выполнении операции P над семафором процесс всегда приостанавливается, поэтому операция P может заменять функцию sleep. Операция V, тем не менее, выводит из состояния приостанова только один процесс, тогда как однопроцессорная функция wakeup возобновляет все процессы, приостановленные по адресу, связанному с событием. С точки зрения семантики использование функции wakeup означает: данное системное условие более не удовлетворяется, следовательно, все приостановленные по условию процессы должны выйти из состояния приостанова. Так, например, процессы, приостановленные в связи с занятостью буфера, не должны дальше пребывать в этом состоянии, если буфер больше не используется, поэтому они возобновляются ядром. Еще один пример: если несколько процессов выводят данные на терминал с помощью функции write, терминальный драйвер может перевести их в состояние приостанова в связи с невозможностью обработки больших объемов информации. Позже, когда драйвер будет готов к приему следующей порции данных, он возобновит все приостановленные им процессы. Использование операций P и V в тех случаях, когда устанавливающие блокировку процессы получают доступ к ресурсу поочередно, а все остальные процессы - в порядке поступления запросов, является более предпочтительным. В сравнении с однопроцессорной процедурой блокирования (sleep-lock) данная схема обычно выигрывает, так как если при наступлении события все процессы возобновляются, большинство из них может вновь наткнуться на блокировку и снова перейти в состояние приостанова. С другой стороны, в тех случаях, когда требуется вывести из состояния приостанова все процессы одновременно, использование операций P и V представляет известную сложность. Если операция возвращает значение семафора, является ли она эквивалентной функции wakeup?

Реферат опубликован: 6/09/2006