Uvod v paralelne procese

Problemi paralelnih procesov

So�asno izvajanje ve� programskih procesov odpira dodatne probleme, ki jih pri navadnih programih ne zasledimo, �etudi so ti programi lahko zelo kompleksni. Ve�ina teh problemov terja pravilno sinhronizacijo paralelnih procesov. Stvar postane �e toliko te�ja, �e ti programski procesi ne potekajo na istem ra�unalniku. Oglejmo si najprej tipi�ne probleme, zatem pa �e mehanizme, ki jih moramo zato uporabiti.

Problem kriti�nih sekcij

Problem nastopi, ko ve� so�asnih procesov ob�asno terja dostop do skupnih ra�unalni�kih virov ali skupnih podatkovnih struktur, ki jih �eli spreminjati. Ko dobi proces dostop do takih skupnih podatkovnih struktur, je v takoimenovani kriti�ni sekciji .

Zagotoviti moramo,da je v �asu, ko je nek proces v kriti�ni sekciji, drugim procesom dostop v to sekcijo prepovedan.

Ostali procesi lahko medtem paralelno potekajo, v primeru zahteve po vstopu v zasedeno kriti�no sekcijo pa �akajo. Ob sprostitvi kriti�ne sekcije lahko vanjo vstopi lepo en proces.

Medsebojno izob�enje so�asnih programskih procesov lahko zagotovimo s posebnimi konstrukti.

Primer:

Vzemimo sistem z ve� terminali. Sistem naj "�teje �tevilo vrstic, vtipkanih v enem dnevu". V ta namen imamo skupno sistemsko spremenljivko lineCount. Delo posameznih uporabnikov za terminali nadzorujejo lo�eni procesi. Kadarkoli nek uporabnik na svojem terminalu vtipka , se izvedejo v sklopu njegovega programskega procesa stavki naslednje vsebine:

load lineCount 
add 1 
store lineCount

Vzemimo primer, da lineCount �e vsebuje vrednost 1234 in da proces A pravkar izvaja ukaz add, ki vrednost v akumulatorskem registru pove�a na 1235. Naj v tem trenutku proces B (zaradi enakega �tetja) prav tedaj izvede operacijo load. Podatke 1235 v akumulatorju se zato spet pokvari na 1234 in, �e bi v tem hipu proces A izvedel �e zadnjo operacijo (store), bi o�itno shranil v spremenljivko lineCount zgre�eno vrednost.

Problem lahko re�imo, �e je dostop posameznih programskih procesov do takih skupnih spremenljivk, kot je v na�em primeru lineCount, ekskluziven.

Podobne probleme zasledimo tudi na primer pri ve�uporabni�kem dostopu do podatkov v podatkovnih bazah, pri (sistemskem) dostopu do skupnih podatkovnih struktur (operacijskega sistema) v ve�procesnih operacijskih sistemih itd.

Problem omejenega pomnilnika (Proizvajalec - porabnik)

To je v bistvu problem dveh so�asnih procesov, pri katerem en proces (proizvajalec) generira podatke, ki jih mora uporabljati drug proces (uporabnik). Da bi bilo izvajanje obeh procesov med seboj �imbolj neodvisno, shranjuje proces - proizvajalec podatke v skladi��e (medpomnilnik, buffer), drug proces pa jih iz tega skladi��a jemlje v istem zaporedju.

Tako so�itje dveh procesov zasledimo zelo pogosto v okviru modulov operacijskih sistemov, predvsem v v modulih, ki so odgovorni za vhodno- izhodne operacije ra�unalnika.

Seveda je "skladi��e" omejeno (�e drugega ne �e z velikostjo pomnilnika). Proizvajalec lahko medpomnilnik napolni le do neke meje. Pred nadaljnjim polnjenjem mora po�akati, da ga "porabnik" vsaj malo izprazni. Prav tako ne sme proces - porabnik ni� "vzeti iz medpomnilnika", �e ni �e vanj kaj vlo�il proces - proizvajalec. Potrebna je koordinacija delovanja obeh procesov.

Omejenemu pomnilniku pravijo v�asih tudi kro�ni medpomnilnik (ring- buffer), saj ga za�ne proizvajalec, potem, ko je pri�el do konca, spet pomniti "na za�etku". Analogno se dogaja s porabnikom: Ko vzame z medpomnilnika zadnji element, gre naslednjega iskati spet na "za�etek". V ra�unalni�kem smislu uporabljata oba procesa kazalca na teko�i element v tem medpomnilniku. Pomembno je, da kazalec procesa- porabnika ne prehiti kazalca proizvajalca (in obratno).

Problem pisalcev in bralcev

Imejmo ve� so�asnih procesov, ki lahko berejo ali popravljajo isto podatkovno strukturo. Struktura naj bo dovolj kompleksna, da je posamezen proces ne more prebrati ali zapisati v "enem koraku". To pomeni, da bi lahko nek proces za�el zapisovati novo verzijo, med samim zapisovanjem pa bi lahko nek drug proces strukturo "prebral". Podatki, ki bi jih tako dobil, bi bili lahko delno �e "novi", delno pa �e "ta stari", skratka nekonsistentni. Da ne pride no nekonsistence podatkov, moramo zagotoviti, da v obdobju, ko nek proces zapisuje nove podatke, noben drug proces ne more ne brati ne pisati v to strukturo. Seveda pa lahko ve� "bralcev" so�asno bere. Potrebna je torej pravilna koordinacija pisalcev in bralcev.

Problem smrtnega objema

Obravnavali bomo razli�ne tehnike medsebojne sinhronizacije paralelnih programskih procesov. Ta se dose�e tako, da proces, ki naj bo sinhroniziran z nekim drugim, v danem trenutku po�aka na nek dogodek (event). Prav mo�no je, da do tega dogodka iz razli�nih razlogov ne more priti. Pravimo, da se je en ali ve� paralelnih procesov zna�lo v smrtnem objemu (deadlock). Oglejmo si nekaj mo�nih vzrokov za tak pojav ter ugotovimo, kako ga lahko prepre�ujemo.

Do smrtnega objema lahko pride, ko na primer dva procesa �akata drug na (dogodek) drugega. Ker pa sta oba s tem blokirana, do odre�ilnega dogodka ne v enem ne v drugem procesu ne pride. Preprost zgled je lahko naslednji. Imamo dva programska procesa, ki za svoje delo potrebujeta dve periferiji. Vsak si �e lasti eno in �aka na drugo. Problem ponazoruje slika.

Kateri pogoji so potrebni za nastop smrtnega objema?
Kako prepre�ujemo nastop smrtnega objema?

Primer v Javi

Problem stradanja

Sorodni problem smrtnemu objemu je problem stradanja ali nedolo�enega zapostavljanja. V�asih mu tudi re�emo problem �ivega objema (livelock). Nek proces �aka na neko sredstvo, vendar je (morda zaradi ni�je prednosti) stalno zapostavljen in nikdar ne pride na vrsto. Tipi�en primer �ivega objema lahko zasledimo pri slabo zasnovanem algoritmu razvr��anja procesov (scheduling). Nek proces z nizko prioriteto morda nikdar ne pride na vrsto, ker imajo prednost procesi z vi�jo prednostjo. Ta problem lahko re�ujemo na primer tako, da s staranjem prednost takemu procesu zvi�ujemo.

Navedene probleme blokiranja nekega procesa (nedolo�eno zapostavljanje, smrtni objem) zasledimo na primer pri operacijskih sistemih ra�unalnikov. Operacijski sistem je predvsem "upravnik sredstev" (resource manager) ra�unalni�kega sistema. Za ta sredstva pa isto�asno lahko konkurira ve�paralelnih programskih procesov.

Filozofi na ve�erji 1, 2,