KNOW INTUIT, Лекция, Синхронизация на паралелни процеси

Задачи за синхронизация

Известни са типични проблеми със синхронизацията, до които могат да бъдат сведени практически всички известни методи за подреждане на задачи във времето. Тези задачи, като правило, се решават чрез прилагане на втория метод на паралелизиране.

1. Проблем с взаимното изключване. Има няколко процеса, чиито програми съдържат критични интервали, при които процесите имат достъп до един и същ споделен критичен ресурс (например база от знания). Изисква се да се изключи едновременното протичане на повече от един процес в такива критични интервали.

Изисквания за тази задача:

забавянето на всеки процес извън неговия критичен интервал не трябва да влияе върху развитието на други процеси;
решението трябва да бъде симетрично по отношение на процесите;
решението не трябва да позволява безизходни ситуации.

Решение, използващо механизма на семафора:

За сравнение, ето алтернативно решение, използващо механизма за активно изчакване.

Нека разпределим клетка от паметта C, в която ще напишем 0, ако никой от процесите не изисква достъп до критичен ресурс, и номерът i на процеса (или изпълняващия процесор), който е влязъл в своя критичен интервал. Тогава условието за i -тия процес да влезе в критичния интервал е резултат от изпълнението на следния оператор:

Наистина, ако (C) = 0, тогава процесът може да навлезе в критичния интервал. Възможно е обаче след кратко време друг процес (на различен процесор) също да е направил същата проверка и след първия да е изпратил номера си на C. Следователно е необходимо да се провери отново дали C съдържа точно номера на този процес. Ако резултатът от повторния анализ е положителен, процесът може да започнекритичен интервал, т.е. заемат критичен ресурс. След като критичният интервал приключи, 0 се изпраща на C.

Използвайки механизма на семафора, такава синхронизация е много по-лесна, т.к много действия са предвидени вътре в процедурите за тяхната обработка.

2. Задачата "доставчици - потребители". Има ограничен буфер за няколко части от информация. Това е критичен ресурс за два типа процеси:

процеси "доставчици", получаващи достъп до ресурса, поставят няколко или една информация върху свободното място в буфера;
процеси "потребители", получаващи достъп до ресурса, четат части от информацията от него.

Изисква се да се изключи едновременен достъп до ресурса от всеки два процеса. Когато буферът е празен, процесите "потребители" трябва да се забавят, когато буферът е пълен, процесите "доставчици".

Тази задача възниква например при обмен с външни устройства и се състои в софтуерна симулация на пръстен или безкраен буфер.

Възможна схема за решаване на проблема с помощта на семафори:

Имитация на пръстен (безкраен) буфер е показана на фиг. 11.5.

След това усъвършенстваме тази процедура, като вземаме предвид използваните индикатори за четене и попълване.

3. Задачата "читатели - писатели".

Има споделен ресурс - област от паметта, която се нуждае от достъп до два типа процеси:

Процесите от първия тип - "ЧИТАТЕЛИТЕ" - могат да имат достъп до споделен ресурс едновременно. Те четат информация.

Процесите от втория тип - "ПИСАТЕЛИТЕ" - взаимно се изключват един друг и "четящите". Те записват данни в споделена област на паметта.

Проблемът е известен в две версии:

„Читатели“, изявили желание за достъп до ресурса,трябва да го получи възможно най-скоро; това е първата задача на извънредното положение.
2. „Читателите“, които са изявили желание за достъп до ресурса, трябва да го получат възможно най-скоро, ако няма заявки от „писатели“. „Писач“, изискващ достъп до ресурс, трябва да го получи възможно най-скоро, но след като обслужи „читателите“, които са се приближили до ресурса преди първия „писател“. Това е втората задача от извънредното положение.

Представяме възможно решение на проблеми с помощта на комбиниран семафор.

Смятаме, че процедурата OPEN BY READ се изпълнява подобно на процедурата SKIP, като се променя само стойността на семафора на брояча. Процедурата OPEN ON RECORD работи като процедурата OPEN, като „отваря“ семафора и гарантира, че „чакащите“ процеси се стартират от процедурите CLOSE ON RECORD или WAIT ON RECORD, които са били прекъснати.

След това критичните интервали за всяка задача могат да бъдат изпълнени съгласно следните схеми.

4. Проблем "философи за хранене". На кръглата маса седят k философи, които прекарват времето си, редувайки философски размисли с хранене. Преди всяка - чиния спагети, между чиниите - по една вилица. Всеки философ се нуждае от две вилици, за да яде. Можете да използвате само вилиците, разположени до чиниите. Тъй като преходите от мислене към хранене се извършват в непредвидими моменти, възможни са конфликти и е необходима синхронизация на процесите.

Нека си представим следния модел, който изисква решението на този проблем - моделът на оперативен обмен между процесори на векторна CS или редове (колони) на матрична CS (фиг. 11.6).

Например, след преброяване на следващия елемент във възел на мрежата, резултатите трябва да бъдат предадени на съседни процесорни елементи за използване в следващата итерация. Възможността е очевиднаконфликти при опит за едновременно обратно предаване.

Нека "левият" семафор Ci е свързан с i -тия процесор за прехвърляне вляво, а "десният" семафор Ci+1 за прехвърляне вдясно (или обратно). Нека всеки процесор, който трябва да премине към двама съседи, първо се опита да затвори своя "десен" (по същия начин, "ляв") семафор. След това, ако левият съсед не е имал време да направи това, той ще се опита да затвори „левия“ семафор и да направи трансфер. Тогава е възможно общо блокиране, ако всички процесори затворят всички семафори едновременно. (При преизчисляване на стойностите на функцията в възлите на мрежата вероятността от такава ситуация е висока.)

Нека позволим на четните процесори да затварят първо "левите" ("десните") семафори, а на нечетните - "десните" ("левите") семафори. Тогава програмните схеми за тях ще изглеждат така:

Нека трябва да се размени процесор с нечетен номер i - ляв и десен. Опитва се да изпълни процедурата CLOSE (Ci+1) . Да приемем, че този семафор (за него - "десен") е затворен от i+1 -ти процесор. Но за този процесор с четен номер този семафор също е първи в реда на затваряне („ляво“). Следователно той или чака възможността да затвори своя "десен" семафор, или извършва обмен. Ако чака своя "правилен" семафор, значи ще го чака, т.к той е вторият за процесора i+2, който извършва обмена. Това означава, че този процесор ще завърши обмена и ще отвори своя "лев" семафор. Тогава процесорът i+1 ще обмени и ще отвори семафор Ci+1. Тогава процесорът i най-накрая ще може да извърши необходимата процедура. След това ще се опита да изпълни процедурата CLOSE (Ci). Този семафор е "десен", т.е. вторият за четния процесор i-1. Следователно този процесор е затворил и двата свързани с него семафора и комуникира. В края на обмена той ще отвори семафори и процесорът ще изчаканеобходим "ляв" семафор и ще може да го затвори за себе си. По този начин не може да възникне безизходица.

Обикновено n е степен на две. Ако n е нечетно, тогава на границата си взаимодействат два "нечетни" процеса на обмен. Тук е възможно блокиране, когато процесор 1 затвори C2 и процесор n затвори семафор C1 (1 = (n+1)mod n) . Процесорът n обаче определено ще изчака семафор Cn да се отвори и да извърши обмена. Това означава, че процесор 1 ще изчака отварянето на семафор C1, ще извърши обмена и ще отвори C2. Така че задънените блокировки също са изключени в този случай.

Разглеждането на този проблем със синхронизацията ни отвежда извън обхвата на традиционното използване на многопроцесорна система от типа MIMD, която включва например самолетите от семейството Elbrus. Въпреки това, многофункционалността на такава архитектура позволява по принцип възможността за възпроизвеждане върху нея на по-"твърди" архитектури - матрични и векторни, т.е. Тип SIMD. Реализирането на метода "решетка" върху матрични КС или върху структури от типа "хиперкуб" изисква такова прехвърляне не само към два съседни процесора в ред, но и към съседните в колона, диагонално и т.н. Това означава, че е възможно да се обобщи този проблем и алгоритъмът за синхронизация. Горната техника за разделяне на процесори на четни и нечетни може да се приложи във всички посоки на обмен - в редове, колони, диагонали и т.н.

5. Задачата за актуализиране на данни. Предполага забрана за използване на актуализирани данни. Например, процесорът актуализира запис в база данни. В най-простия случай може да се използва функция, която забранява достъпа до този запис, докато не бъде актуализиран. (Разбира се, ние не считаме това примитивно решение, когато базата данни е превърната в ресурс с последователен достъп. Ние се стремим към многоканален, паралелен достъп.)

Вместо знакможе да се използва семафор. Чакането може да се организира чрез процедурите WAIT или HIM.