2020-10-12
85
Программный подход
Программный подход может быть реализован для параллельных процессов, которые выполняются как в однопроцессорной, так и в многопроцессорной системе с разделяемой основной памятью. Обычно такой подход предполагает взаимоисключения на уровне доступа к памяти. Одновременный доступ (чтение и/или запись) к одной и той же ячейке основной памяти упорядочивается при помощи следующего механизма. Рассмотрим для простоты два процесса P0 и P1. Пусть зарезервирована глобальная ячейка памяти turn. Перед выполнением критического участка процесс (P0 или P1) проверяет содержимое turn. Если значение turn равно номеру процесса, то процесс может войти в критический участок. В противном случае он должен ждать, постоянно опрашивая значение turn до тех пор, пока оно не позволит ему войти в критический участок. Пусть также определен логический вектор flag, в котором flag[0] соответствует процессу P0, а flag[1] – процессу P1. Каждый процесс может ознакомиться с флагом другого процесса, но не может его изменить. Когда процессу требуется войти в критический участок, он периодически проверяет состояние флага другого процесса до тех пор, пока тот не примет значение false, указывающее, что другой процесс покинул критический участок. Процесс немедленно устанавливает значение своего собственного флага равным true и входит в критический участок. По выходе из критического участка процесс сбрасывает свой флаг, присваивая ему значение false. Ниже приводится пример алгоритма Петерсона для двух процессов.
|
|
|
boolean flag[2];
int turn;
void P0()
{
while(true)
{
flag[0] = true;
turn = 1;
while (flag[1] && turn = = 1)
/* блокировка входа в критическую секцию для P0 */;
flag[0] = false;
/* остальной код */;
}
}
void P1()
{
while(true)
{
flag[1] = true;
turn = 0;
while (flag[0] && turn = = 0)
/* блокировка входа в критическую секцию для P1 */;
flag[1] = false;
/* остальной код */;
}
}
void main ()
{
flag[0] = false;
flag[1] = false;
/* приостановка выполнения основной программы
и запуск P0,P1 */
parbegin (P0,P1);
}
Условия взаимоисключения выполняются. Рассмотрим процесс P0. Если flag[0] = true, P1 не может войти в критическую секцию. Если P1 уже находится в критической секции, то flag[1] =true и для P0 вход в критическую секцию заблокирован. В данном алгоритме взаимная блокировка предотвращается. Предположим, что P0 заблокирован в своем цикле while. Следовательно, flag[1]= true, а turn = 1. P0 может войти в критическую секцию только в том случае, когда либо flag[1] =false, либо turn = 0. Может быть три случая:
1. P1 не намерен входить в критическую секцию. Однако это невозможно, поскольку при этом выполнялось бы условие flag[1]=false.
|
|
|
2. P1 ожидает входа в критическую секцию. Это также невозможно, так как если turn=1, то P1 способен войти в критическую секцию.
3. P1 циклически использует критическую секцию. Это также невозможно, поскольку P1 перед каждой попыткой входа в критическую секцию устанавливает значение turn = 0, давая возможность доступа в критическую секцию процессу P0.
Алгоритм Петерсона обобщается на случай n процессов.
Аппаратный подход
Процессоры многих компьютеров поддерживают команды, которые за один цикл выборки атомарно выполняют над ячейкой памяти два действия: чтение и запись или чтение и проверка значения. Атомарность означает, что операция неделима, т.е. никакой другой процесс не может обратиться к слову памяти, пока команда не выполнена. В качестве примера рассмотрим команду TSL (Test and Set Lock – проверить и заблокировать), которая действует следующим образом:
TSL RX,LOCK ; содержимое слова памяти lock копируется в регистр rx
; значение lock устанавливается равным 1.
Процессор, выполняющий команду TSL, блокирует шину памяти, чтобы остальные процессоры не могли обратиться к памяти. Таким образом, гарантируется, что операция считывания слова и записи значения неделима. Ниже приводится код программы с использованием TSL на типовом ассемблере для поддержки взаимного исключения.
enter_region;
TSL REGISTER, LOCK
CMP REGISTER,0; предыдущее значение lock сравнивается с нулем
JNE enter_region ; если оно не нулевое – блокировка уже была
; установлена и цикл завершается
RET ; если оно нулевое – установка блокировки, т.е.
; lock:=1 и возврат в вызывающую программу.
; Процесс вошел в критический участок.
leave_region
MOVE LOCK, 0 ; снятие блокировки, т.е. lock:=0. Процесс вышел из
; критической секции.
RET
Совместно используемая переменная lock управляет доступом к общим данным. Если lock=0, любой процесс может изменить значение lock, т.е. lock:=1 и обратиться к общим данным, а затем изменить его обратно, т.е. lock:=0. Прежде чем попасть в критическую секцию, процесс вызывает процедуру enter_region, которая выполняет активное ожидание вплоть до снятия блокировки (когда другой процесс, находившийся в критической секции, вышел из нее), после чего она устанавливает блокировку и возвращает управление процессу, который входит в критическую секцию. По выходе из критической секции процесс вызывает процедуру leave_region, снимающую блокировку. Взаимное исключение для доступа к общим данным может быть реализовано аппаратно путем:
– запрета прерываний в однопроцессорной системе;
– использования аппаратно-поддерживаемой команды.
Запрет прерываний может быть обеспечен использованием примитивов, определенных ядром для запрета и разрешения прерываний. Недостатком аппаратного подхода и алгоритма Петерсона является наличие цикла активного ожидания входа в критическую секцию, расходующего процессорное время.
Использование механизмов операционной системы
Фундаментальный принцип взаимодействия двух или нескольких процессов заключается в использовании обмена сигналами. Для сигнализации используются специальные переменные, называемые семафорами. Для передачи сигнала через семафор s процесс выполняет примитив signal(s), а для получения сигнала – примитив wait(s). В последнем случае процесс приостанавливается до тех пор, пока не осуществится передача соответствующего сигнала.
Будем рассматривать семафор как переменную, принимающую целые значения, над которой определены три операции:
1. Семафор инициализируется неотрицательным значением.
2. Операция wait уменьшает значение семафора. Если это значение становится отрицательным, процесс, выполняющий операцию wait, блокируется.
|
|
|
3. Операция signal увеличивает значение семафора. Если это значение становится отрицательным, то заблокированный операцией wait процесс деблокируется. Ниже приводится алгоритм определения семафорных примитивов.
struct semaphore {
int count;
queueType queue;
}
void wait (semaphore s)
{
s.count--;
if (s.count < 0)
{
Поместить процесс P в s.queue и заблокировать его
}
}
void signal (semaphore s)
{
s.count++;
if (s.count < = 0)
{
Удалить процесс P из s.queue и разблокировать его, т.е. поместить P в список активных процессов.
}
}
Семафор, который может принимать только значения 0 или 1 называется бинарным семафором. Для хранения процессов, ожидающих как обычные, так и бинарные семафоры, используется очередь. При использовании принципа FIFO (first-in-first-out – “первым вошел первым вышел”) первым из очереди освобождается процесс, который был заблокирован дольше других. Ниже приводится алгоритм решения задачи взаимоисключений с использованием семафора.
const int n = N /* количество процессов */
semaphore s = 1;
void P(int i)
{
while(true)
{
wait(s);
/* критическая секция */;
signal(s);
/* остальной код */;
}
}
void main()
{
parbegin (P(1),P(2), …,P(n)); // запуск P1,P2,...,Pn
}
Пусть имеется массив P(i),i=1,...,n процессов. Каждый процесс перед входом в критическую секцию выполняет вызов wait(s).Если s<0, процесс приостанавливается. Если s=1, то s:=0 и процесс входит в критическую секцию. Поскольку s не является больше положительным, любой другой процесс при попытке войти в критическую секцию обнаружит, что она занята. При этом данный процесс блокируется и s:=-1. Пытаться войти в критическую секцию может любое количество процессов, при этом значение семафора каждый раз уменьшается на единицу. После того как процесс, находившийся в критической секции, покидает ее, s:=s+1 и один из заблокированных процессов удаляется из очереди и активизируется, т.е. перемещается из списка приостановленных процессов в список готовых к выполнению процессов. Данный процесс сможет войти в критическую секцию, как только планировщик операционной системы выберет его.
|
|
|
В случае потоков, выполняющихся в пространстве пользователя, используется упрощенная версия семафора, называемая мьютексом (mutex, сокращение от mutual exclusion – взаимное исключение). Мьютекс может управлять взаимным исключением доступа к совместно используемым ресурсам, и его реализация более проста и эффективна. Мьютекс – переменная, которая может находиться в одном из двух состояний: блокированном (<>0) или неблокированном (=0). Значение мьютекса устанавливается двумя процедурами. Для входа в критическую секцию поток или процесс вызывает процедуру mutex_lock. Если мьютекс не заблокирован, поток может войти в критическую секцию. В противном случае вызывающий поток блокируется до тех пор, пока другой поток, находящийся в критической секции, не выйдет из нее, вызвав процедуру mutex_unlock. Если мьютекс блокирует несколько потоков, то из них случайным образом выбирается один. Ниже приводятся коды процедур mutex_lock и mutex_unlock в случае потоков на уровне пользователя с использованием команды TSL.
mutex_lock;
TSL REGISTER,MUTEX ; предыдущее значение mutex копируется в
; регистр и устанавливается новое значение
mutex:=1
CMP REGISTER,0; предыдущее значение mutex сравнивается
; с нулем
JZE ok ; если оно нулевое – mutex не был блокирован
CALL thread_yield; mutex занят, управление передается другому потоку
JMP mutex_lock; повторить попытку позже
ok: RET ; возврат в вызывающую программу
mutex_unlock ; вход в критический участок
MOVE MUTEX,0 ; снятие блокировки, т.е. mutex:=0 и выход из
; критической секции
RET ; возврат
Процедура mutex_lock отличается от вышеприведенной процедуры enter_region следующим образом. Процедура enter_region находится в состоянии активного ожидания, т.е. проверяет в цикле наличие блокировки до тех пор, пока критическая секция не освободится или планировщик не передаст управление другому процессу по истечении кванта времени. Однако в случае потоков ситуация меняется, поскольку нет прерываний по таймеру, останавливающих слишком долго работающие потоки. Поток, пытающийся получить доступ к семафору и находящийся в состоянии активного ожидания, зациклится навсегда, так как он не позволит предоставить процессор другому потоку, желающему снять блокировку. Поэтому, если войти в критическую секцию невозможно, mutex_lock вызывает thread_yield, чтобы предоставить процессор другому потоку. При следующем запуске поток снова проверяет блокировку. Поскольку вызов thread_yield является обращением к планировщику потоков в пространстве пользователя, обращения к ядру не требуется, и он выполняется быстро. Синхронизация потоков на уровне пользователя происходит полностью в пространстве пользователя.
