LAIKSAKRĪTĪGIE PROCESI - Procesi un pavedieni

1. Procesi un pavedieni

1.1. Laiksakritība

Laiksakritība ir vairaku procesu (programmu) paralēla izpilde.

1.2. Procesa jēdziens

Programma – instrukciju kopa, kas nosaka operaciju statisko secību, ko izpilda dators datu apstrades procesa.

Process – sistematiska operaciju izpilde kada noteikta rezultata iegūšanai. Tas ir dinamisks objekts, programma izpildes stadija.

1.3. Procesa stavokļu diagramma

Eksistēšanas gaita process var atrasties dažados stavokļos un mainīt tas. Procesa stavokļu diagramma ir paradīta 1.attēla.

1.att. Procesa stavokļu diagramma

Process atrodas izpildīšanas stavokli, ja procesors tiek iedalīts procesam un atrodas procesa rīcība.

Process atrodas gatavības stavokli, ja varētu izpildīties uzreiz pēc procesora nodošanas viņa rīcība.

Process atrodas sabloķēšanas stavokli, ja viņš gaida, kad notiks kaut kads notikums lai būtu iespējams turpinat savu darbu.

Parējas starp šiem stavokļiem var raksturot sekojoši:

1.2.– process tiek parcelts gatavības stavokli, ja ir beidzies procesam iedalītais laika kvants līdz tam momentam, kad process brīvpratīgi atbrīvo procesoru.

1.3. – process tiek parcelts sabloķēšanas stavokli, ja viņš inicializē ievades vai izvades procedūras un gaida to pabeigšanu (vai arī gaida kada cita notikuma beigas).

3.2. – process tiek parcelts gatavības stavokli, kad ir noticis notikums, kura pabeigšanu process gaidīja.

2.1. – process sak izpildīties, kad dispečers izdala viņam procesoru.

Lai varētu efektīvi regulēt datora resursu slodzi, OS var apturēt un atjaunot procesus. Apturēšanu izmanto, lai uz neilgu laiku izslēgtu procesu, kad sistēma ir parslogota. Ja apturēšana ir paredzēta uz ilgaku laiku, procesam jaatbrīvo sistēmas resursi. Atjaunošana ir operacija, kura sagatavo procesu atkartotai palaišanai no ta paša punkta, kura process bija apturēts. Parēja 3.5. ir vajadzīga lai varētu atrak aktivizēt sabloķēto procesu, jo apturēšanas operacijai ir augstaka prioritate.

1.4. Procesa vadības bloks

Procesu vadībai OS izmanto procesa vadības bloku (PCB - Process Control Block), kura tiek saglabata visa informacija par procesu, piem., tekošais stavoklis, prioritate, izdalītie resursi, utt.

OS tiek realizēti mehanismi, kuri ļauj izpildīt dažadas procesa operacijas, tadas ka procesa izvietošana, iznicinašana, prioritates noteikšana un mainīšana, procesa palaišana, utt.

2. Laiksakritīgu procesu izpildīšanas problēmas

2.1.Asinhronais režīms

Laiksakritīgie procesi var izpildīties neatkarīgi viens no otra, bet var arī izpildītie asinhrona režīma, kas nozīme, ka periodiski procesiem vajag sadarboties un sinhronizēties.

Asinhronais režīms – datu apstrades vai parraides veids, kad katras konkrētas operacijas izpilde sakas pēc iepriekšējas operacijas beigu signala saņemšanas.

Sinhronizacija – darbība, kas nodrošina noteiktu notikumu sakrišanu laika divu vai vairaku asinhronu procedūru izpildes gaita.

Procesi vienmēr konkurē lai izmantotu sistēmas ierobežotus resursus, tadus ka atmiņa, centralais procesors, faili.

2.2. Procesu sadarbošanas un konkurences problēmas

Procesu sadarbošanas un konkurences par sistēmas resursiem sfēras izvirza problēmas, kurus obligati jaatrisina:

savstarpēja izslēgšana (Mutual Exclusion);

sinhronizacija (Synchronisation);

strupceļš (Deadlock).

Šo problēmu risinašanai OS izmanto semaforus un citus līdzekļus (slēdzeni, nosacījuma mainīgie, barjeras, notikumi, monitori).

2.2.1. Savstarpēja izslēgšana

Savstarpējas izslēgšanas problēma – nodrošinat pieeju koplietojamiem resursiem tikai vienam procesam katra momenta.

Koplietojamie resursi (Shareable resources) ir tadas, kas vienlaicīgi var izmantot vairaki procesi.

Kad process griežas pie koplietojamiem resursiem, uzskata, ka process atrodas sava kritiska apgabala (Critical section). Ja procesi sadarbojas, izmantojot kopīgus mainīgus un viens no procesiem atrodas sava kritiska apgabala, tad parējiem procesiem tiek aizliegta iespēja ieiet savos kritiskos apgabalos.

2.2.3. Sinhronizacija

Sinhronizacija – procesu sadarbība atsevišķos punktos (process nevar turpinat savas darbības, kamēr cits process nesasniegs kadu noteiktu punktu vai nepabeigs savu darbu). OS ir atbildīgas par tada veida sinhronizaciju.

2.2.3. Strupceļš

Strupceļš – situacija, kad vairaki procesi pieprasa vienus un tos pašus resursus, neatbrīvo paturētus resursus un rezultata bloķē viņš otru (2.att.). Novērst šadas situacijas vai samazinat to negatīvu ietekmi ir viena no OS funkcijam.

2.att. Strupceļa situacija

2.3. Semafori

2.3.1. Semafora jēdziens

Semafors ir īpašs datu tips, ko izmanto, lai sinhronizētu vairakus procesus, kas izpildas vienlaicīgi. Semafors ir aizsargats mainīgs, kura vērtību var nolasīt un nomainīt, izmantojot specialas operacijas wait un signal un semafora inicializēšanas komandas.

wait(S) IF val(S)>0 THEN val(S):=val(S)-1 ELSE (gaid t uz S)

signal(S) IF (process gaida uz S) THEN (atļaut procesam turpinat darbu) ELSE val(S):=val(S)+1

Kur:

S – semafora vards,

Val(S) – semafora vērtība (vesela tipa skaitlis)

Var redzēt, ka katra operacija signal palielina semafora vērtību uz “1”, bet katra veiksmīga operacija wait pazemina semafora vērtību uz “1”. Tatad, semafora vērtība tiek noteikta ar sekojošo izteiksmi:

Val(S) = C(S) + ns(S) - nw(S), kur

Val(S) – semafora S vērtība

C(S) – semafora S inicializēta vērtība

ns(S) – operaciju signal skaits

ws(S) - operaciju wait skaits

2.3.2. Semafors un savstarpējas izslēgšanas problēma

Izmantojot semafora koncepciju var atrisinat savstarpējas izslēgšanas problēmu ar vienkaršo paņēmienu – katru procesa kritisku apgabalu ielenkt ar operacijam wait un signal uz vienīga semafora ar sakuma vērtību “1”.

Wait(mutex);

critical section;

Signal(mutex);

kur mutex – semafora vards.

2.3.3. Semafors un asimetriska sinhronizēšana

Semafora koncepciju var izmantot sinhronizacijas mehanisma realizēšanai: viens process bloķē pats sevi, izpildot operaciju WAIT uz semafora P ar sakuma stavokli 0 lai sagaidītu kada notikuma pienakšanu; cits process konstatē, ka gaidīts notikums ir noticis un atbrīvo sabloķētu procesu ar operacijas SIGNAL palīdzību.

Process A Process B

L1: wait(P);…

…L2: signal(P);

Šaja piemēra sinhronizacija ir asimetriska, jo procesa A izpildīšanu regulē process B.

2.3.4. Semafors un simetriska sinhronizēšana

Piemērs, kur katrs no procesiem regulē cita procesa izpildi, ir klasiska problēma “ražotajs – patērētajs” (“producer-consumer”). (“Ražotajs” sadarbojas ar “patērētaju” izmantojot buferu, kura “ražotajs” ievieto kadu elementu un no kura “patērētajs” izņem šo elementu. Bufera ietilpība – N elementi.)

Var redzēt, ka šeit eksistē divas sinhronizacijas problēmas un viena savstarpējas izslēgšanas problēma:

“ražotajs” nevar ievietot elementu buferī, ja tas ir aizpildīts (var izmantot semaforu SPACE ar sakuma stavokli N);

“patērētajs” nevar izņemt elementu, ja buferis ir tukšs (var izmantot semaforu ITEM ar sakuma stavokli 0);

kamēr “ražotajs” izmanto buferi, “patērētajs” gaida un otradi (var izmantot semaforu BUFFER ar sakuma stavokli 1).

Producer program                          Consumer program

repeat indefinitely                          repeat indefinitely

begin produce item;begin wait(ITEM);

wait(SPACE); wait(BUFFER);

wait(BUFFER);extract item from buffer;

deposit item in buffer; signal(BUFFER);

signal(BUFFER); signal(SPACE);

signal(ITEM) consume item

end end

2.3.5. Monitori

Monitors ir programma, kura sistēma kontrole, vada un parbauda operaciju izpildi. Monitors ir procedūru un informatīvo struktūru kopa, kuru procesi izmanto laika dalības režīma un kuru katra momenta var izmantot tikai viens process.

Salīdzinoši ar semaforiem, monitoriem ir sekojošas priekšrocības:

• Monitors ir loti elastīgs līdzeklis, ar kura palīdzību var realizēt gan semaforus, gan citus sinhronizacijas līdzekļus.

• Visu sadalamo mainīgo lokalizēšanu monitora ļauj atbrīvoties no sarežģītam konstrukcijam sinhronizējošos procesos.

• Monitori ļauj procesiem kopīgi izmantot programmu, kura pēc būtības ir kritisks apgabals.

Monitora piemērs ir programma-planotajs, kas sadala kaut kadus resursus. Katru reizi, kad process grib saņemt sava rīcība resursa daļu tas griežas pie planotaja. Šo planotaju izmanto visi procesi un katram no procesiem jebkura momenta var rasties nepieciešamība griezties pie planotaja, bet planotajs nevar apkalpot vienlaicīgi vairak ka vienu procesu. Ir situacijas, kad monitoram vajag apturēt procesu, kurš griežas pie ta, piem., ja process pieprasa resursu, kuru jau izmanto cits process. Šaja gadījuma monitors var sabloķēt šo procesu, kamēr resurss nebūs atbrīvots. Procesu sabloķēšanai izmanto operacijas wait un signal. Kad sabloķē procesu, jauzrada arī nosacījums, kad process varēs turpinat darbu, piem., resurss brīvs. Kad nosacījums tiek izpildīts, monitors izstrada signalu signal un pasludina, ka

nosacījums ir izpildīts. Ja kaut kadi procesi gaida ša nosacījuma izpildi, tad viens no tiem pamostas un saņem atļauju turpinaties.

Monitors ir viena vai vairakas procedūras ar statiskam, globalam, informatīvam struktūram. Kad pie monitora griežas pirmo reizi visi mainīgie saņem savas sakuma vērtības; kad vēlak - tiek izmantotas mainīgo vērtības, kas palika no iepriekšējas griešanas. Mainīgie ar tipu „condition” nav līdzīgi parastajiem mainīgajiem. Kad tiek definēts tads mainīgais, tas nozīme, ka tiek organizēta rinda. Process, kas izpilda wait komandu tiek ievietots šaja rinaa. Wait process, kas izpildīja operaciju signal ļauj citam procesam, kas gaidīja, iziet no rindas un ieiet monitora.

Monitora piemērs ir paradīts zemak:

monitor resursu_planotajs

var resurss_aiznemts:boolean;

resurss_brivs:boolean;

procedure pakert_resursu

begin

if resurss_aiznemts then

wait(resurss_brivs);

resurss_aiznemts:=true;

end;

procedure atdot_resursu

begin

resurss_ainemts:=false;

signal(resurs_brivs);

end;

begin

resurs_aiznemts:=false;

end;

2.4. Strupceļi

2.4.1. Strupceļu izcelšanas nosacījumi

Strupceļš – situacija, kad divi procesi, kas pieprasa vienus un tos pašus resursus, bloķē viens otru.

Ir formulēti strupceļu izcelšanas četri nepieciešamie nosacījumi

1.    Savstarpējas izslēgšanas nosacījums (procesi prasa piešķirt tiesības uz resursu monopolu vadību);

2.    Resursu gaidīšanas nosacījums (procesi patur jau izdalītus viņu rīcība resursus un gaida papildus resursus);

3.    Resursu pardalīšanas no jauna neiespējamības nosacījums (nevar atņemt resursus no procesa, kamēr tie nebūs izmantoti lai process pabeigtu savu izpildi);

4.    Riņķveida gaidīšanas nosacījums (eksistē procesu virkne, kura procesi patur resursus, kas ir nepieciešami nakamam virknes procesam).

2.4.2. Strupceļu likvidēšanas politikas

Novērst strupceļu situacijas vai samazinat to negatīvo ietekmi ir OS funkcija, kuras realizēšanai izmanto dažadas politikas:

novērst strupceļus,

automatiski atklat strupceļus,

likvidēt strupceļus ar operatora palīdzību.

1. Novērst strupceļus – ideja balstas uz ta, ka sistēma nedrīkst nonakt

strupceļa stavoklī. Tapēc, kad kaut kads process izstrada pieprasījumu,

kas var novest sistēmu pie strupceļa, sistēma veic pasakumus, lai izvairītos no bīstama stavokļa – vai nu neapmierina pieprasījumu, vai atņem resursu no cita procesa. Metodes priekšrocība – strupceļš vienmēr tiek novērsts. Trūkumi – neefektīvi tiek izmantoti sistēmas resursi un dargi var izmaksat algoritms, kas realizē šo pieeju.

2. Automatiski atrast – pieļauj, lai sistēma nokļūtu strupceļa situacija. Kad

tas reali notiek, sistēma ar specialas programmas palīdzību atrod strupceļu un pēc tam var atņem resursus no dažadiem procesiem, lai citi varētu izkustēties no vietas. Šī metode ļauj izmantot resursus efektīvak un ja reali strupceļa situacijas paradas diezgan reti, tad resursu noslogojuma palielinašana sedz izdevumus strupceļa atklašanai un izejai no tas.

3. Likvidēt ar operatora palīdzību – paredz, ka strupceļa situacija rodas ļoti reti, lai par to uztrauktos. Ja tomēr strupceļš rodas, tad sistēmu vienkarši palaiž no jauna. Bet var gadīties, ka sistēmas palaišana no jauna var izmaksat loti dargi.

2.4.3. Baņķiera algoritms

“Baņķiera algoritms” – pamats strupceļu novēršanas algoritmiem:

n – procesu skaits sistēma;

t –konkrēta resursa skaits sistēma;

m(i) – procesa (i) maksimala vajadzība pēc resursa (m(i) ≤ t );

l(i) – procesam izdalītais resursu skaits ( l(i) ≤ m(i) );

c(i)=m(i)-l(i) – procesa tekoša vajadzība pēc resursa;

a = t-Σl(i) – resursu skaits, kas vel ir pieejams sadalīšanai (i=1,2,…,n).

“Baņķiera” algoritma nosacījumi:

Ja sistēma var nodrošinat procesam resursa maksimali vajadzīgo skaitu, process izmanto visus resursus, atgriež tas sistēmai un beidz savu darbu;

Sistēmas stavoklis ir drošs, ja OS var nodrošinat visu procesu pabeigšanu;

Izdalīt resursu procesam var tikai tad, ja pēc izdalīšanas sistēmas stavoklis paliek drošs;

Nedrošs sistēmas stavoklis nozīme, ka nelabvēlīgas darbību secības gadījuma strupceļš ir iespējams.

“Baņķiera” algoritma piemērs:

“Baņķiera” algoritma ierobežojumi:

Sadalamo resursu fiksēts skaits;

Izpildamo procesu fiksēts un pastavīgs skaits;

Maksimala vajadzība pēc resursiem ir zinama katram procesam;

Sistēma garantē, ka resursu pieprasījumi būs nodrošinati parskatama laika intervala (kada?);

Procesi atgriež resursus sistēmai arī parskatama laika intervala (kada?).

Algoritmam ir teorētiska nozīme un to var uzskatīt par pamatu pieejamo algoritmu izstradei.

3. Pavedieni

Procesa koncepciju raksturo divi parametri:

1.    Resursu parvaldīšana (resource ownership)

2.    Planošana/izpilde (scheduling/execution)

Visas OS abi šie raksturojumi kopa nosaka procesa būtību. Bet OS var uzskatīt šos raksturojumus atsevišķi vienu no otra un šaja gadījuma dispečerizacijas vienību (2.) sauc par pavedienu (thread) un resursu vadības vienību (1.) sauc par procesu (process) vai uzdevumu (task).

Daudz pavedienu režīms (daudz plūsmu) ir OS spēja uzturēt vairaku pavedienu izpildīšanu viena procesa ietvaros (3.att.).

Daudz pavedienu vidē ar procesu ir saistīti šadi elementi:

1.    Virtuala adrešu platība, kura ir izvietots process.

2.    Aizsargata pieeja pie procesoriem, failiem, ievades un izvades resursiem, citiem procesiem.

Daudz pavedienu vidē ar pavedienu ir saistīti šadi elementi:

1.    Pavediena stavoklis (izpildas, gatavs, bloķēts …).

2.    Neizpildama pavediena konteksta saglabašana.

3.    Izpildīšanas steks.

4.    Statiska atmiņa, kas tiek iedalīta pavediena lokaliem mainīgiem.

5.    Pieeja pie procesa atmiņas un resursiem. Šo pieeju sadala visi procesa pavedieni.

3.Att. Pavedienu konstrukcija

Visi procesa pavedieni sadala sev starpa procesa resursus, atrodas viena adrešu platība un var izmantot pieeju vieniem un tiem pašiem datiem. Ja viens pavediens maina kadus datus atmiņa, tad citi pavedieni savas pieejas laika jau var vērot izmaiņas. Ja viens pavediens atver failu lasīšanai, šo failu var lasīt arī citi procesa pavedieni.No ražīguma viedokļa pavedienu izmantošanai ir šadas priekšrocības:

1.    Jauna pavediena izveidošana esoša procesa ietvaros prasa mazaku laiku neka jauna procesa izveidošana.

2.    Pavedienu var pabeigt atrak, neka procesu.

3.    Parslēgšana starp pavedieniem notiek atrak neka starp procesiem.

4.    Tiek paaugstinata informacijas apmaiņas efektivitate.

4. Kontroles jautajumi pašparbaudei

1. Process – ir …

2. Laiksakritība – ir …

3. Procesa „izpildīšanas” stavoklis – ir …

4. Procesa „gatavības” stavoklis – ir …

5. Procesa „sabloķēšanas” stavoklis – ir …

6. Procesa vadības bloks – ir …

7. Datu apstrades asinhronais režīms – ir …

8. Sinhronizacija datu apstradē – ir …

9. Procesu sadarbošanas un konkurences problēmas - ir …

10.Savstarpēja izslēgšana – ir …

11.Koplietojamie resursi – ir …

12.Kritiskais apgabals – ir …

13.Procesu sinhronizacija – ir …

14.Strupceļš – ir …

15.Semafors – ir …

16.Operacija SIGNAL(S) – ir …

17.Operacija WAIT(S) – ir …

18.Savstarpējas problēmas atrisinašana ar semafora izmantošanu

19.Asimetriska procesu sinhronizēšana ar semafora izmantošanu

20.Simetriska procesu sinhronizēšana ar semafora izmantošanu

21.Monitors – ir …

22.Strupceļu izcelšanas nepieciešamie nosacījumi

23.Strupceļu novēršanas politikas

24.”Baņkiera algoritma” galvena ideja un realizēšanas ierobežojumi

25.Pavediens (thread) ir …

27.Daudzpavedienu (daudzu plūsmu) režīms – ir …

28.Daudzpavedienu režīma priekšrocības