Мур Фокса

Один працівник для побудови мура витрача Т годин. Питання: Скільки часу треба для 4 робітників . Для кожного ясно що відповідь не дорівнює Т/4. Для 4 людей які будують мур виникає організаційна задача забезпечення того щоб вони працювали разом конструктивно, та не заважали один одному. Розглянемо декілька шляхів організації робіт, кожен метод буде мати безпосередню аналогію з реальними задачами паралельністю програмування.

Метод 1 Конвеєрне розв’язання

Вся робота поділяєть між робочими горизонтально кожен робітник будує тільки один ряд цегли, при цьому всі вони можуть працювати над муром але ефективність буде менша в 100%, тому що неможна починати будувати більш верхні ряди поки побудовані більш нижні.Цей розвязок ілюструє накладні витрати, пов’язані із заповненням і звільненням векторного компа (машини). Цей метод може бути ефективним методом розпаралелення задачі лише якщо мур має достатню довжину так що довший час всі робітники можуть працювати одночасно (конвеєр має бути довшим).

Метод 2 Геометричне розв’язання

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

До того часу поки 2 робітники які працюють поруч не обміняються інформацією про те, що сусідня цегла вже покладена неможна починати ставити наступний ряд цегли. Крім додаткових накладних витрат пов’язаних з таким обміном інформацією та синхронізацією, необхідно забезпечити добрий баланс навантажень для отримання високої продуктивності. Для випадку на рис 3 за нерівномірністю розподілення робіт така організація малоефективна.

Метод 3 Комплексне розв’язання .

При цьому розв’язанні цим методом цегла та цемент не виділяється кожному муляру чи цегляру окремо, а зберігається як централізований ресурс, кожен цегляр забирає цеглу і цемент переносить її до муру та кладе в наступну доступну позицію муру (рис4).

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

Тупік – коли всі звертаються до центрального процесора.

Парадокс дікстра

Умова: для взяття спагеті треба взяти 2 вилки.

Вихід: Один філософне сідає за сті. Тоді одна вилка вілна.

В КС методи обходу тупіків добре розв’язуються але вони можуть дуже просто виникати.

Клсифікація КС:

1) Класифікація Фліна (1996) M.I «труди інституту радіоінженерів», «труди IEEE»

Існують потоки комад і потоки даних . Флінн: «….бувають поодинокі потоки команд і множинні потоки команд, можуть бути поодинокі потоки даних і множинні потоки даних». Отже отримуємо чотири варіанти класифікації:

1) ОКОД

2) МКОД

3) ОКМД

4) МКМД