Процессы, задачи (потоки) и синхронизация.
Процесс –код программы в процессе выполнения.
Имеет собственную память под код и данные, отображение виртуальной памяти на реальную, а также стек.
Задача (поток, нить) –одна из ветвей выполнения процесса. Разделяет с процессом память под код и данные, отображение виртуальной памяти на реальную. Имеет собственный стек, то есть свои локальные переменные.
Взаимодействие задач легче, поскольку у них есть общая разделяемая память. Для процессов приходится организовывать обмен сообщениями.
Состояние параллельной программы состоит из значений переменных в некоторый момент времени. Программа начинает выполнение в некотором начальном состоянии. Процессы (потоки) выполняются параллельно и каждый изменяет состояние программы. Каждый оператор процесса изменяет состояние неделимым образом. Выполнение пар. программы можно рассматривать как последовательность состояний, которая называется история s0->s1->…->sn. Число возможных историй программы огромно.
Цель синхронизации процессов – исключить нежелательные истории.
Взаимное исключение состоит в выделении в процессах критических секций, которые не прерываются другими процессами, использующими те же переменные. Условная синхронизация состоит в приостановке процесса до выполнения некоторого условия.
<await (B) S;>
Параллельная программа должна обладать некоторыми свойствами:
– безопасность (программа не переходит в нежелательное состояние)
– живучесть (программа обязательно оказывается в желательном состоянии)
Пример.
Поиск образца в файле
{открыть файл}
readln(f,s);
while not (eof(f)) do
begin
if search(p,s) then Writeln(s);
readln(f,s);
end;
Две строки в теле цикла можно попытаться выполнить параллельно. Однако они не являются независимыми. Нужно, чтобы чтение производилось не в ту строку, где происходит поиск.
{открыть файл}
readln(f,s1);
while not (eof(f)) do
begin
if search(p,s1) then Writeln(s1); //*
readln(f,s2); //*
s1:=s2
end;
Программа правильна, но неэффективна, поскольку надо потоки создавать внутри цикла и копировать строки. Нужно сделать два цикла в разных потоках. Используем схему производитель-потребитель. Один поток будет читать из файла в буфер. Другой – искать строку в буфере.
Взаимодействуют потоки через разделяемую переменную buffer.
Var buffer:string;
Const done:Boolean=false;
//процесс 1
var s1:string;
….
While true do
begin
//ожидать заполнения буфера или значения true
if done then break;
s1:=buffer
//сигнализировать, что буфер пуст
if search(p,s1) then Writeln(s1);
end;
//процесс 2
var s2:string;
….
While true do
Begin
Readln(f,s2);
If eof(f) then
Begin
Done:=true;
Break
End;
//ожидать опустошения буфера
buffer:=s2;
//сигнализировать о заполнении буфера
end;
Пример. Поиск максимального элемента в массиве.