Процеси. Взаимодействие между процеси.

2.Паралелната обработка в основата на мултипрограмните системи.Освен апаратен паралелизъм съществува и логически, реализиран от програмното осигуряване. За да се осигури синхронизирането на апаратната и софтуерната част, трябва да се предоставят механизми за синхронизация и комуникация.

2.1. Процеси основни понятия.

Процес: последователен процес (задача, действие) е изходна точка в теорията на ОС. Последователния процес е работа, извършена от последователен процесор при изпълнение на програмата с нейните данни. Всеки процес има свои процесор и програма. Няколко процеса могат да делят един процесор (виртуален процесор) или една програма (при различни последователност на изпълнение), Програмата е пасивна, процеса активен. Процеса е двойката процесор-програма при изпълнение. Когато пакетно задание постъпи в системата, се създава процес (или няколко). При интерактивните системи с времеделене също се създава процес. Системните задачи (пр.споолинг) също са процеси. В някои системи могат да се създадат подпроцеси , които се изпълняват паралелно. Системните и потребителските процеси се изграждат по еднакви принципи, но системните имат по-големи права (не се състезават за ресурси, тъй като те ги управляват).

Състояния на процеса. По време на съществуването на процеса, той преминава основно през три състояния : 1. Изпълняван процесора е предоставен на процеса; 2. Готов процесът би могъл да се изпълни, ако му се разпредели процесор; 3. Блокиран процеса не може да се изпълни, докато не получи сигнал, съобщение или ресурс. Поддържа се опашка с готовите процеси и опашка с блокираните процеси. Новосъздадения процес се записва в опашката на готовите процеси, откъдето диспечера избира процес за изпълнение. След като определения квант изтече, управление получава диспечера, който избира нов процес, а изпълнявания става готов. В някои ОС има въведени и други състояния на процеса състояние на преустановяване. Процеса преустановява сам себе си, но може да бъде преустановен и от друг процес. Преустановения може да продължи изпълнението си само, ако друг процес го възобнови. Състоянията могат да се разделя и на подсъстояния.

Преустановяването на процесите се използва за да се регулира натоварването на мултипрограмната система. Потребителя също може да преустанови процес, с цел настройка на програмата. Блокиран процес, може да чака настъпване на събитие неопределено дълго. Обикновено преустановяване се прави с цел освобождаване на ресурси. Управление между състоянията се извършва чрез извикване на съответни примитиви.

2.2 Паралелни процеси

Когато два или повече процеса се припокриват във времето, говорим за паралелно изпълнение на процеси. Те могат да бъдат 1.Зависими работят с множества независими променливи и не оказват влияние на други процеси; 2. Взаимодействащи си процеси имат достъп до общи променливи и резултата от един процес влияе върху друг. Общите променливи представят състоянието на ресурсите, разделяни от конкуриращи се процеси. Те също се използват за комуникиране между коопериращи се процеси за общи задачи. Асинхронността на паралелните процеси и различните скорости на изпълнение усложняват взаимодействията между процесите.

2.3. Взаимно изключване на процеси. Въпреки, че физическите и логическите ресурси могат да бъдат разделени, обикновено в момент от времето могат да са достъпни само за един процес. Такива ресурси се наричат критични. Ако няколко процеса трябва да получат достъп до критични ресурси, те съгласуват действията си, така, че само единия да има достъп до ресурса. Това е същността на взаимно изключване на процеси. При това трябва да се спазват следните критерии : 1.Само един процес може да използва ресурса в даден момент; 2.Ако няколко процеса едновременно имат нужда от ресурса, той трябва да е предоставен на един от тях в крайно време; 3.Ако процес получи ресурс, той трябва да го освободи в крайно време. Има варианти на решение на проблема, при които двата процеса използващи общи променливи си сътрудничат, двата процеса се компилират в един общ и ако се изпълняват в непресичащи се интервали от време, ще се получат верни резултати. В този вариант е възможна появата на времезависими грешки. Решението на проблема с взаимното изключване на процеси се решава с определяне на критична секция. За правилното решаване на проблема трябва да са изпълнени: 1.Само един процес може да се намира в критичната си секция в даден момент; 2.Процес може да остане в критичната си секция крайно време; 3.Ако процес иска да влезе в критичната си секция, трябва да му се даде такава възможност в крайно време. (никой процес извън критичната си секция не трябва да пречи на друг да влезе в своята такава)

2.3.2.Решение с машинна команда TS. В много процесори съществува команда TS (Test & Set провери и установи). Формата е TS(a,b) с параметри от логически тип. Командата чете стойността на променливата b, записва я в a (a:=b) и установява b:=true. Всеки процес има локална променлива, а обща е глобална променлива за всички процеси и е инициализирана с false. Процес (пр. P_1) влиза в критичната си секция в зависимост от локалната си променлива, ако няма друг процес използващ общия ресурс, то глобалната променлива е false, тогава P_1 влиза в критичната си секция, а другите са в процес на изчакване.При излизане P_1 указва на глобалната променлива false. Решението осигурява взаимно изключване, но е възможно попадане в безкрайно отлагане. Решение : program взаимно_изключване; var обща:boolean; procedure P_1; var локална:boolean; begin repeat локална:=true; while локална do TS(локална,обща); критична секция; обща:=false; ; until false; end; procedure P_2; var локална:boolean; begin repeat локална:=true; while lokalna do TS(локална, обща); критична секция; обща:=false; .; until false; end; begin обща:=false; parbegin P_1; P_2; parend; end. TS в някои машини се реализа и по друг начин използва се машинен признак като локална променлива, командата е TS(b).

2.3.3. Семафори. С въвеждането на семафори се избягва сложното и неефективно действие на командата TS. Различаваме двоични семафори (0,1) и общи семафори (0,1,2,). Общата дефиниция е: 1.P(s); while s=0 do skip; s=s-1; Извиквайки P(s), процеса чака стойност на семафора s=0, докато друг процес не го освободи с V(s); 2.V(s):s:=s+1; Тъй като s е обща променлива, операциите P и V трябва да са неделими (те са критични спрямо s). Когато процес модифицира s, никой друг процес не може да променя семафора. Единствено по време на празната операция (skip) може да се променя семафора. За решаване проблема с критичните секции, във всеки процес се организира : P(s); критична секция; V(s); Когато някой от процесите е в критична секция, s=0; Взаимното изключване е гарантирано, тъй като при s=1, само един процес може да приложи P(s), останалите чакат при s=0, докато процеса не направи операция V(s). За реализация на критичните секции са достатъчни двоичните семафори. Семафорните се реализират обикновено с TS(wait,s), където wait и s са локална и глобална (инициализирани с true и false). Основния недостатък на взаимното изключване е, че P и V изискват активно очакване, т.е. когато процес е в критична секция, другите принудително изпадат в цикъл на очакване. При това те напразно изразходват процесорно време. Друг проблем е т.нар. инверсия на приоритетите на процесите, която може да доведе до безкрайно отлагане ако нископриоритетен процес се намира в критична секция, и в опашката на готовите постъпи високоприоритетен, последния отнема процесора от нископриоритетния и той започва да изпълнява активно очакване. За да се отстрани недостатъка, трябва да се промени дефиницията на P и V вместо чакане изчаквания процес преминава в състояние на блокиран така той чака на опашката на блокираните, а вместо него се изпълняват дуги процеси.

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

2.4.1. Събития.Основно изискване при синхронизацията на процесите е: на единия процес се дава възможност да чака, докато друг не му съобщи за настъпване на събитие. Събитията се представят с блок за състояние (дескриптор), който в най-простия си вид включва флаг за състоянието на събитието и указател към заглавие на опашка от процеси, очакващи настъпването на събитието. Използването на събитията може да се разшири до група от събития. Както и при другите обекти, когато броя на събитията в ОС е фиксиран и те се разпределят глобално, възможно е да се случи два независими процеса да използват едно и също събитие. Очевидно трябва да се вземат мерки за разпределение на ресурса. Проблема може да се реши когато са предвидени операции за създаване (унищожаване) на събития от процесите.

2.4.2 Използване на семафори за синхронизация и за броячи на ресурси. Синхронизацията може да се извърши, като в качеството на всяко събитие се използва двоичен семафор, операция P вместо wait и операция V вместо signal. Ако s получава цели неотрицателни числа тогава s е общ (броячен) семафор. Възможно е s да получава и отрицателни стойности. Отрицателната стойност ще показа броя на блокираните пред s процеси: P(semaphor):sem.broi:=sem.broi-1; if sem.broi <0 then begin блокиране на процеса в sem.опашка; избор на готов процес за изпълнение; end; V(semapohor):sem.broi+1; if sem.broi <= 0 then процес от sem.опашка става готов; .. При изпълнение на V(s) извикващия процес продължава. Това е валидно, ако дисциплината за планиране на процесора е от вида FIFO, RR и т.н. При приоритетните дисциплини с изместване трябва да се извика планиращата програма за избор на пренос за изпълнение. Обобщения семафор може да се използва за оргнизация и отчитане на ресурси. Всеки процес би могъл да се охарактеризира с броя и типа на ресурсите, които произвежда (освобождава) или консумира (заема). Това могат да са устройства, процесори, буфери, и т.н. Процес произвежда единица ресурс и изпълнява V над свързания с ресурса семафор, а консумира ресурс с P. При инициализацията семафора получава стойност, равна на броя на достъпните ресурси. Съществуват и разширени семафорни примитиви, позволяващи операциите P,V над няколко семафора едновременно. Това разрешава заемане и освобождаване на няколко ресурса в една операция.

2.4.3. Решения на класически проблеми. 1.Безкраен буфер. Предполага се, че процесите производител и потребител са свързани чрез буфер, които се състои от безкраен брой елементи с еднакъв размер. Буфера може да е от тип опашка. Производителя може да добавя в края на опашката, като винаги има празен елемент, а потребителя чете от началото. Синхронизация е необходима, за да не чете потребителя от празна опашка. Въвеждаме семафор брой, семафор вз_изкл., за изключване при работа с буфера (критична секция); 2.Ограничен буфер: предполага се, че буферна памет се състои от n клетки. Възниква необходимост да се избегне четене от празен буфер и запис в пълен.Работата на производителя и потребителя се синхронизира с 3 семафора празен, пълен, вз.изкл. Не е задължително взаимното изключване на буферните операции, освен в случаите, когато буферите са свързани в списък или програмата е за m производителя и n>=1 потребителя тогава е необходима защита за буферните операции; 3.Читатели и писатели:Данни (файл или запис), могат да се използват от няколко процеса. Някои от процесите могат да искат да прочетат новите данни. Ако двама читатели искат да четат общите данни едновременно, няма проблем. Такъв възниква при опит за достъп на писател и друг процес (писател или читател). Затова писателите трябва да имат монополен достъп до ресурса. Проблема се решава с налагане на приоритети. Първи проблем: никакъв читател да не се държи чакащ, освен, ако писател вече не е получил достъп до общия обект. Втори проблем: готов писател да извърши запис веднага след като е възможно, т.е. ако писател е чакащ за достъп, никои читател не може да стартира. Решението на всеки от проблемите може да води до безкрайно отлагане на писатели, или читатели. Семафора запис е общ за читатели и писатели, а служи и на първия/последния читател да влезе/напусне критичната секция. Той не се използва от читателите които влизат или излизат, докато другите читатели са в критична секция. Семафора взимно_изкл се използва за осигуряване на работата с променливата брой_читатели, която дава броя на четящите процеси. Безкрайното отлагане на писател се решава с подреждането на опашката пред семафор запис. Когато писател направи V(запис), процесора може да се направи или на читател или на писател. 4.Обядващи философи: Пет философа прекарват времето си в мислене и ядене около кръгла маса с пет вилици и пет чинии. Когато философ огладнее се опитва да вземе двете вилици около него (лява и дясна), но не може да вземе вилица от ръката на съсед. Когато философ успее да вземе две вилици, той яде, без да ги освобождава, когато свърши с яденето ги оставя от двете си страни. Това е класически проблем в синхронизацията. Едно решение е да се представи всяка вилица със семафор. Философ се опитва да вземе вилица с P-операция и да я освободи с V операция. Program filosof; var vilica:array[0..4] of semaphore; initialize (всеки семафор,1); За всеки философ: repeat мисли; P(вилица[I]); P(вилица[I+1] mod 5]; яде; V(вилица[I]); V(вилица[I+1]mod 5); until false; Решението гарантира, че двама съседи няма да ядат едновременно, но трябва да се отхвърли, защото може да възникне мъртва хватка. Програмта може да се модифицира така, че философа, след вдигане на лявата вилица, проверява дали дясната е свободна, ако не е пробва пак след време, тук също може да възникне мъртва хватка, в случаи че петте вземат лявата си вилица. Възможни изходи са: 1. Да се позволи най-много на четири философа да седят на масата; 2. Да се позволи на философ да вземе вилица, само ако и двете са свободни (в критична секция); 3. Да се използва асиметрично решение: Четен философ вдига първо лявата си вилица и след това дясната, докато нечетен обратно.

2.4.4. Проблеми с използване на семафори. При реализация със семафори може да се достигне до ситуация, когато два или повече процеса чакат да настъпи събитие, което може да се предизвика само от един от тях. Процесите са в мъртва хватка. Друг проблем е неопределеното блокиране. Може да се създаде ситуация, при която процеси неопределено дълго чакат семафор. Най-често при LIFO. Тъй като процесите използват по случаен път общи променливи, възможни са времезависими грешки. За да се избегнат трябва да се спазва последователността: преди влизане в критична секция се изпълнява P(s), а след излизането й V(s).

2.4.5. Събитийни броячи. Възможно е да се реши проблема ограничен буфер и без използването на взаимно изключване - с събитийни броячи. Три операци са дефинирани над брояча EC: 1.Read(EC) : връща текущата стойност на EC; 2. Advance(EC) :увеличава стойността на EC с 1; 3.Await(EC,v): Чака, докато EC не стане >= на v. Когато производителя създаде нов елемент, той проверява за свободно място в буфера чрез await. В началото са прочетени=0, и производителя не се блокира. Ако се произведат n+1 елемента, преди потребителя да тръгне, чрез await производителя ще чака, докато прочетени стане 1. От своя страна, потребителя, преди да прочете I-я елемент ще чака докато записани стан е i.

2.5. Комуникация между процесите. Съществуват основно две схеми за комуникация използване на обща памет и системи със съобщения. При единия вариант приложния програмист отговаря за правилното комуникиране между процесите. При другия ОС е отговорна за комуникацията. За изпращане и получаване на съобщения се използват две операции от вида: send(приемник, съобщение) и receive(източник, съобщение). Нужно е наличие на комумикационни линии, еднопосочни или двупосочни, буфериране на съобщенията и др.

2.5.1. Адресиране на процесите. 1.Директна комуникация. Всеки процес изпращащ или получаващ съобщение, трябва явно да посочи името на получателя/подателя. Операциите са: send(получател, съобщените); receive(подател, съобщение); Установения канал е двупосочен, с два процеса. Процесите трябва да знаят имената помежду си. Схемата е симетрична. Възможен е и асиметричен вариант send(съобщение) и receive(съобщение). Възможно е и радио разпращане един предава всички приемат. 2. Индиректна комуникация. Използва се буферна памет, наречена пощенска кутия, за съхраненение на получените съобщения (send(Postbox,message); receive(postbox,message);) Връзка се установява само ако има обща пощенска кутия.Проблем е кои да получи съобшението, ако няколко процеса изпълняват receive. Решението е чрез ограничаване по двойки, или системата да извършва арбитраж. Пощенската кутия е или прикрепена към процес, или е процес, или е множество управлявано от ОС. Обикновено ОС разрешва създаване и унищожаване на кутии. В най-простия случаи комуникацията е еднопосочна, но в много случаи е необходима и двупосочна комуникация (изпращане на съобщение и получаване на отговор)

2.5.2. Буфериране и блокоране. Всяка комуникационна линия може да има възможност да буферира определен брой съобщения, т.е. с нея да бъде свързана опашка от съобщения. От тук и реализацията с или без блокиране. 1.Блокиращи примитиви. Не се използва буфериране (опашката е с 0 капацитет). Подателя се блокира до получаване на съобщението, а получателя се блокора до изпращане на съобщението. Недостатък е че се пречи на паралелизма блокораните процеси не вършат полезна работа. 2.Неблокиращи примитиви. Чрез използване на буфер при реализацията може да се използва ограничен или неограничен буфер, условни примитиви (send изпраща само ако подателя е блокиран в очакване), винаги неблокиращ( ако се изпрати съобщение преди да е получено старото, то то се губи).

2.5.3. Формат на съобщенията с фиксирана дължина, с променлива дължина, от определен тип. При тези с фиксирана дължина, физически се реализира просто, но е труден програмния код. При определения тип може да се запише mb:mailbox[n] of T.

2.5.4. Обработка на грешки. Вероятността за грешка в разпределение среди е по-голяма от тази в едномашинните среди. Някои от възможните грешки: подател или получател могат да завършат преди съобщението да е обработено. Получателя чака съобщение от вече несъществуващ подател или изпращане на съобщение към завършил процес. Загуба на съобщението в мрежата, неполучаване на съобщението навреме и др. Най-често проблемите се решават със задаване на време на изпращане/получаване.

2.6. Еквивалентност на средствата за взаимодействие.

2.6.1. Реализация със семафори. Индиректна комуникация може да се осъществи със семафори, като за всеки процес се свърже семафор, пред който процесът се блокира, когато send и receive трябва да чакат. Обща буферна област се използва за пазене на пощенските кутии. Буферната област също е защитена със семафор.

2.6.2. Реализация на семафори чрез съобщения. Ако е на разположение система със съобщения, възможна е реализация чрез въвеждане на нов процес синхронизиращ. Той включва брояч и свързан списък от чакащи процеси свързани със семафор. За да направи P и V, желаещия процес извиква процедура, която изпраща съобщение към синхронизиращия процес, указвайки желаната операция и семафор. Когато пристигне съобщението, синхронизиращия процес проверява брояча, за да види дали операцията може да бъде завършена. Времезависими грешки се избягват, тъй като синхронизиращия процес обработва само една заявка в даден момент.