Оргазиране на критични секции

P(s);

V(s);

Реализация на семафорите. Toва става чрез командата TS(wait, s) където wait и s са локална и глобална променливи(инициализирани съответно с true и false)

V(s): S:=false;

Проблеми:

Недостатък – семафорите изискват актовно чакане. КОгато процес е в критична секция, другите процеси са принудени да изпадат в цикъл на очакване, докато получат възможност да влязат в критичната си секция.

Друг проблем е инверсия на приоритетите на процесите, която може да доведе до безкрайно отлагане Това се получава при приоритетни дисциплини за планиране на процесора, при които винаги се изпълнява процесът с наи-висок приоритет. ако нископриоритетен се намира в критична секция , а високоприоритетен чака да влезе, то последният отнема процесора и винаги ще цикли. Решение: модификация дефиницията на P(s) и V(s). Когато се изпълнява P(s). Ако s=0, процесът се блокира и отива в опашка на блокираните процеси, а друг процес се избира за изпълнение. Блокираният процес може да се стартира отново чрез изпълнение на V(s) от друг процес.

Реализация на P и V : Обикновено се прилага дисциплината FIFО(FCFS) за управление на опашката, но се използват и други дисциплини.

За да се осигури непрекъсваемост на P и V трябва да се гарантира, че два процеса няма да изпълняват едновременно операциите над семафора- при еднопроцессорна машинма проблемът се решава най-често със забрана на прекъсванията, когато се изпълняват P и V . Може и с командата ТАS

Необходимо е семафорите да се дефинират като запис.

Type semaphore = racord

Stojnost:integer;

Opashka : queue;

End;

Begin

Else begin

Блокиране на извикващия процес в sem.opashka;

Избор на следващ процес за изпълнение;

End;

Еnd;

Begin

Then разблокиране на процес от sem.opashka;

Else sem.stojnost:=1;

End;

status:boolean;

opashka:queue;

end;
procedure wait(var e:event);

begin

if e.status then

else

извикващият процес се блокира е се записва в e.opashka;

избира се нов процес за изпълнение;

end;

procedure signal(var e:event);

begin

e.status:=true;

begin

end;

end;
Управлението се връща на извикващия процес само ако дисциплината за планиране на процесора не е приоритетна и с изместване, например тя е FCSF.

Program производител_потребител;

Var bufer:T;

Запълнен_бyфер, прочетен_буфер :event;

Procedure производител;

Var buf:T;

Begin

Производство на данни в buf;

Bufer:=buf;

Signal(Запълнен_бyфер);

Wait(прочетен_буфер);

Reset(прочетен_буфер);

Until false;

End;
Procedure протребител;

Var buf:T;

Begin

Wait(Запълнен_бyфер);

Buf:=bufer;

Потребление на данни от buf;

Reset(Запълнен_бyфер);

Signal(прочетен_буфер);

Until false;

End;

Initialize(Запълнен_бyфер, false);

Initialize(прочетен_буфер, false);

Parbegin производител; потребител; parend;

End.

Производителят запълва буфера и сиганлизира за събитието запълнен_буфер, което позволява на потребителя, чакащ събитието да започне разпечатване на буфера. Анологично потребителят след прочитане на буфера съобщава за събитието с прочетен_буфер, което позволчва на производителя, очакващ настъпването на това събитие, да запълни отново буфера.

Понякога се използват група от събития.- например в байта, съдържащ състоянието на събитието могат да се запомнят състоянията на група от 8 събития.

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


2.4.2 Използване на семафори-С помощта на семафори може да се реши проблемът производител – потребител. За събитие може да се използва двоичен семафор: P вмсто wait и V вместо signal. Синхронизацията може да се извърши, като в качеството на всяко събитие се използва двоичен семафор, операция P – вместо wait и операция V вместо signal.

Program производител_потребител;

Var bufer:integer;

пълен, празен:semaphore;

Procedure производител;

Var buf:integer;

Begin

Производство на данни в buf;

V(пълен);

P(празен);

End;
Procedure протребител;

Var buf:integre;

Begin

Buf:=bufer;

Потребление на данни от buf;

V(празен);

End;

Begin

Initialize(празен, 0);

Parbegin

While true do производител;

While true do потребител;

parend;

Var buf:…;

Begin

Производство на данни в buf;

Bufer:=buf;

V(пълен);

End;
Procedure протребител;

Var buf:….;

Begin

Buf:=bufer;

V(празен);

Потребление на данни от buf;

End;
От точка 2.3.3 S може да получава цели неотрицателни стойности – тогава S е общ(броячен) семафор. Възможно е да се направи още едно обобщение да се разреши на S да получава и отрицателни стойности. Отрицателната стойност ще показва броя на блокираните пред S процеси:
P(сем ): сем.брой := сем.брой-1;

If сем.брой<0 then

Begin

Блокиране на процеса в сем.опашка;

End;

If сем.брой<=0 then процес от сем.опашка става готов;

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

Procedure производител;

Var buf:…;

Begin

Производство на запис в buf;

P(вз_изкл);

Buf се прехвърля в bufer;

V(вз_изкл);

V(брой);

Var buf:….;

Begin

……………………….

P(брой);

Чете се от bufer в buf;

V( вз_изкл);

Потребление на buf;

…………………………

End;

Procedure производител;

Var buf:…;

Begin

Производство на запис в buf;

P(празен);

P(вз_изкл);

Buf се прехвърля в bufer;

V(вз_изкл);

V(пълен);

Until false;

End;
Procedure протребител;

Var buf:….;

Begin

repeat

P(вз_изкл);

Чете се от bufer в buf;

V( вз_изкл);

V (празен);

Потребление на buf;

Until false;

End;
3.Читатели и писатели: реализира се при много процеси като тези, които се изпълняват, се записват във файл или буфер, след което се четат. Данни (файл или запис) могат да се използват от няколко процеса. Няма проблем, ако двама читатели искат да четат общите данни едновременно. Проблем има ако читател и писател, или 2ма писатели искат достъп до базата данни. Решение: дава се предимство на читателите- никакъв читател да не се държи чакащ, освен, ако писател вече не е получил достъп до общия обект; ако писател чака за достъп, никой читател не може да стартира. Имаме една променлива за броя на читателите. Ако няма читатели- предимството се дава на писателите.

Семафорът запис е общ за читатели и писатели. Той осигурява взаимното изключване на писателите, а също така служи на първия/последния читател да влезе/напуссне критичната сесия

Procedure читател;

begin

repeat

читатели= читатели +1;

If читатели=1 then Р(запис);

V(вз.изкл); Четене на данни;

P(вз.изкл);

читатели= читатели –1;

If читатели=0 then V(запис);

V(вз.изкл);

Until false;

End;

Begin

P(запис);

Запис на данни;

V(запис);

Until false;

End;

Безкрайното отлагане на писател се решава с подреждането на опашката пред семафор запис. Когато писател направи V(запис) процесорът може да се предостаяи или на читател или на писател.

общите данни са:

var vilica:array[0..4] of semaphore; initialize (всеки семафор,1);

За всеки философ:

repeat мисли;

P(вилица[I]);

P(вилица[I+1] mod 5];

яде;

V(вилица[I+1]mod 5);

until false;

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

Възможни изходи са: 1. Да се позволи най-много на четири философа да седят на масата; 2. Да се позволи на философ да вземе вилица, само ако и двете са свободни (в критична секция); 3. Да се използва асиметрично решение: Четен философ вдига първо лявата си вилица и след това дясната, докато нечетен обратно. Класическо решение: проверява дали и двете вилици са свободни- взима ги и двете. Правилно решение в глава 3.2
5.Спящият бръснар- В бръснарница има 1 бръснар, 1 бръснарски стол и N стола за чакащи клиенти. Ако няма клиенти- бръснарят сяда на стола и спи. Ако влезе клиент- той събужда бръснаря. Ако влезе друг клиент- той сяда на стол, или ако няма свободен стол-си излиза.

Използват се: един броячен (общ) семафор- за чакащите клиенти(без подстригвания); един двоичен семафор- проверява заетостта на бръснаря, един взаимно изключващ ; допълнителната променлива- брои чакащите.

procedure бръснар;

begin

P(клиенти);

P(вз.изкл);

чакащи=чакащи-1;

V(бръснар) ;

V(вз.изкл);

обслужване

untill false;

end;

procedure клиент;

P(вз.изкл);

if (чакаши<столове)

begin

V(клиенти);

V(вз.изкл) ;

P(бръснар);

получава услуга;

end

end;

-в бръснарницата има >1 бръснар

-в бръснарницата има 1 касиер

-в бръснарницата няма касиер, а свободен бръснар играе неговата роля(но само от един клиент може да се приемат парите в даден момент и има само една каса)

- Променена чакалня. Освен столове има и места за правостоящи, т.е. капацитеът е столове и места. Клиентът сяда ако има стол. Ако няма свободен стол чака прав. Ако няма и места за правосточши напуска. При свободен бръснар(нека са >1) сяда клиент от седналите(най-дълго чакалия) Ако има правостаящи, първият сяда на свободния стол.

- справедливо решение. Ако в горното решение 3-а клиенти са седнали, би трябвало да станат по реда на сядане. Ако обаче бръснарят е бърз или клиентът е плешив, те няма да стават от столовете си в този ред. За решеване на проблема се добавя масив от семафори и номера за клиентите(брояч в критична секция). При сядане клиент изпълнява P над семафора си, при ставане – V. Номерата на клиетнте се записват в опашка.

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.

program Ograni4en bufer

var bufer array[0..n] of integer;

zapisani, pro4eteni: integer;

procedure proizwoditel; procedure potrebitel;

var var

begin begin

proizwedeni := 0; konsumir := 0;

while true do while true do

begin begin

proizwejda i zapiswa Inc(konsumir);

element s danni w buf; Await(zapisani,

Inc(proizwedeni); konsumir);

Await(pro4eteni, 4ete danni ot

proizwedeni-n); bufer w buf;

Zapis na dannite Advance(pro4eteni);

ot buf w bufer; konsumirane

Advance(zapisani); na elementa;

End End

zapisani:=0; pro4eteni:=0;

Parbegin proizwoditel; potrebitel; parend;

End.

- Адресиране на процесите.

- Буфериране и блокиране. Всяка комуникационна линия може да има възможност да буферира определен брой съобщения, т.е. с нея да бъде свързана опашка от съобщения. От тук и реализацията е с или без блокиране на процесите. 1.Блокиращи примитиви. Изпращаме съобщение и докато то не се прочете, процесът се блокира и обратно: процесът се блокира, докато съобщението не се получи. Няма буфериране. Нарича се “рандеву”. Ползва се за синхронизиран обмен на данни. Недостатък: блокират се процесите. 2.Неблокиращи примитиви.- чрез използване на буфер – изпращача записва съобщението в буфера. Ако е пулен, се блокира и чака да се освободи място. Получателя чете от буфера. Ако е празен, се блокира. При неограничен буфер подателят не се блокира. – чрез условни примитиви – send изпраща съобщение ако получателят е блокиран. Receive приема ако податлят е блокиран. Недостатък: необходима е допълнителна синсхронизация. – чрез винаги неблокиращ – изпращача не се блокира. Ако изпрати съобщение преди да е прочетено предходното, първото се губи. Необходима е синхронизация.

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

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

- Реализация със семафори. Индиректна комуникация може да се осъществи със семафори, като за всеки процес се свърже семафор, пред който процесът се блокира, когато send и receive трябва да чакат. Обща буферна област се използва за пазене на пощенските кутии. Буферната област също е защитена със семафор. При изпълнение на receive над празна пощ. кутия процесът се записва в опашаката на чакащи, освобождава буферната област чрез семафор, и се самоблокира пред своя семафор. При събуждане отново заема буф.-та област. При извършване на send над непълна пощ. кутия съобщението се записва и се проверява дали има чакащ процес. Ако да, 1-ят се изважда от опашката, прави се V над семафора му и буф. Бласт се освобождава. Когато send не може да завърши поради пълна пощ. кутия името на подателя се записва в опашката на пощ. кутия, освобождава се чрез семафора буферната област и се прави P над семафора на подателя. Когато получател извади съобщение и има процес за изпращане в тази кутия, подателят ще бъде събуден чрез V.

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

При използване на глоб. данни от 2 и > потока, програмиста прави синхроизацията. Всеки поток протича последователно. Потоците са статични (бр. им не се променя по време на  на процеса) или динамични (променя се). За управление на потоците се използват примитиви. Има 2-а начина за реализ.-я на прим-те: в потребителското пространство(с библитотеки, тези потоци са бързи, работят под <> ОС, блокирането на поток блокира процеса, има 1 квант за всички потоци в 1 процес) или в ядрото(по-бавни, процесът може да получава >= 1 квант, блокирането на поток води до избор на друг). 2-та вида са показани на фиг-та.

 и комбиниран метод- намалява недостатъците на първите 2 .
8.Управление на процесите в UNIX- Всеки процес принадлежи към процесна група. 1 или > такива образуват сесия. Няма асинхронност в 1 процес. Има 2 уникални процеса: Процес 0(наречен scheduler) се създава при стартиране. Той поражда процес 1 – прародител на всички процеси. Когато потребител влезне в системата пр-ес 1 създава пр-ес за потребителя. Всеки процес се състои от 3 сегмента: текстов(това са командите), данни и стек (той се намира на най-старши адрес и се разширява към по-младшите). Процесите имат потребителска и ситемна(когато след прекъсване се изпълнява проц-а на ядрото) фаза, които се редуват. Процесите се изпълняват в опр. ред: 1)създаден; 2)готов за изпълнение- намира се в паметта; 3)готов за изпълнение-във вторична памет; 4)с-е на изпълнение; 5)спящ- блокиран в паметта, чакащ събитие; 6)изместен от друг; 7)зомби- завършил. Системните данни за управление на процес съставят структурата на процеса, която е елемент на таблицата на процесите. Таблицата е в ядрото. В структурата на всеки процес има: целочислен-и идентиф-ри на процеса, състояние на процеса, информация за планиране, данни за сигналите и образ на процеса. Всеки процес има таблица на сегментите на процеса. Всеки елемент на таблицата съдържа начален виртуален адрес на сегмент резрешен начин на достъп до сегмента и указател към елемент на обща таблица на сегментите. В системите с виртуална памет сегментите се раздеят на страници. В обща таблица на сегмента се пазят указатели към страниците. Системните данни използвани от ядрото само когато процесът е в оперативната памет образуват потребителската структура. В нея например се пазят състоянието на регистрите, таблица на отворените фаилове и др.

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