Page 41 - 4868

39 Ошибка! Стиль не определен.

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

6.2. Розпаралелювання (задача пошуку зразка у файлі)

Розглянемо задачу пошуку всіх екземплярів шаблону pattern у файлі
filename.Змінна pattern – це заданий рядок, азмінна filename – ім’я
файлу.Ця задача без значних зусиль вирішується в ОС Unix на командному
рівні за допомогою однієї із команд сімейства grep, наприклад:
grep pattern filename

У результаті створюється один процес.Він виконує приблизно наступну
послідовну програму.

string line;
прочитати рядок вводу з stdin в line;
while (!EOF) { # EOF – це кінець файлу
шукати pattern в line;
if (pattern є в line) вивести line;
прочитати наступний рядок вводу;
}

Тепер бажано з’ясувати два основних питання: чи можна розпаралелити
цю програму?Якщо так, то яким чином?
Основна вимога для можливості розпаралелювання будь-якої програми
полягає в тому, що вона повинна містити незалежні частини.Дві частини
програми взаємно залежні, якщо кожна з них породжує результати,
необхідні для виконання іншої.Це можливо тільки у випадку, якщо вони
зчитують і записують спільні змінні.Отже, дві частини програми незалежні,
якщо вони не виконують зчитування і запис одних і тих же змінних.
Дамо більш точне визначення незалежності паралельних процесів.Нехай
множина читання частини програми – це змінні, які вона зчитує, але не
змінює.Нехай множина запису частини програми – це змінні, в які вона
записує (і, можливо, зчитує).Дві частини програми
називаютьсянезалежними, якщо результатом перетину їх множин запису є
порожня множина.
Зчитування або запис будь-якої змінної є неподільною операцією.Це
відноситься як до простих змінним (таких як цілі числа), які зберігаються в
окремих словах пам’яті, так і до окремих елементів масивів або структур
(записів).
З попереднього визначення випливає, що дві частини програми
незалежні, якщо вони тільки зчитують спільні змінні, або кожна частина
програми зчитує змінні, відмінні від тих, які інша частина програми
записує.Іноді дві частини програми можуть безпечно виконуватися
паралельно, навіть роблячи запис в одні і ті ж змінні.Однак це можливо,
якщо не важливий порядок, в якому відбувається запис.Наприклад, якщо
декілька процесів періодично оновлюють графічний екран, і будь-який