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: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.load lineCount add 1 store lineCount
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?
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.
