Page 49 - 6571

во тільки у випадку, якщо вони зчитують і записують спільні
змінні. Отже, дві частини програми незалежні, якщо вони не ви-
конують зчитування і запис одних і тих же змінних.
Дамо більш точне визначення незалежності паралельних

процесів. Нехай множина читання частини програми – це змінні,
які вона зчитує, але не змінює. Нехай множина запису частини
програми – це змінні, в які вона записує (і, можливо, зчитує). Дві

частини програми називаються незалежними, якщо результатом
перетину їх множин запису є порожня множина.
Зчитування або запис будь-якої змінної є неподільною опе-
рацією. Це відноситься як до простих змінним (таких як цілі чис-

ла), які зберігаються в окремих словах пам’яті, так і до окремих
елементів масивів або структур (записів).

З попереднього визначення випливає, що дві частини про-
грами незалежні, якщо вони тільки зчитують спільні змінні, або
кожна частина програми зчитує змінні, відмінні від тих, які інша
частина програми записує. Іноді дві частини програми можуть

безпечно виконуватися паралельно, навіть роблячи запис в одні і
ті ж змінні. Однак це можливо, якщо не важливий порядок, в
якому відбувається запис. Наприклад, якщо декілька процесів пе-

ріодично оновлюють графічний екран, і будь-який порядок вико-
нання оновлень не впливає (не псує) на вид екрану.
Повернемося до задачі пошуку шаблону в файлі. Які частини
програми незалежні і, отже, можуть бути виконані паралельно?

Програма починається із зчитування першого рядка вводу, що
повинно бути виконано перед усіма іншими діями. Після цього
програма входить в цикл пошуку шаблону, виводить рядок, якщо

шаблон був знайдений, а потім зчитує новий рядок. Вивести ря-
док до того, як у ньому був виконаний пошук шаблону, не можна,
тому перші два рядки циклу виконати паралельно неможливо.
Однак можна прочитати наступний рядок вводу під час пошуку

шаблону в попередньому рядку і можливо його друк. Отже, розг-
лянемо іншу, паралельну версію попередньої програми.

string line;
прочитати вхідний рядок з stdin в line;
while (!EOF) {
co
// шукати pattern в line;
if (pattern є в line) вивести line;

48