Процессы, задачи (потоки) и синхронизация

Процесс – код программы в процессе выполнения.

Имеет собственную память под код и данные, отображение виртуальной памяти на реальную, а также стек.

Задача (поток, нить) – одна из ветвей выполнения процесса. Разделяет с процессом память под код и данные, отображение виртуальной памяти на реальную. Имеет собственный стек, то есть свои локальные переменные.

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

Состояние параллельной программы состоит из значений переменных в некоторый момент времени. Программа начинает выполнение в некотором начальном состоянии. Процессы (потоки) выполняются параллельно и каждый изменяет состояние программы. Каждый оператор процесса изменяет состояние неделимым образом. Выполнение пар. программы можно рассматривать как последовательность состояний, которая называется история 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;

Пример. Поиск максимального элемента в массиве.