Problemi darka e filozofeve
- 1. 1 Problemi darka e filozofeve -Lexioni 5 Ne shkencen kompjuterike, problemi i darkes se filozofeve eshte nje shembull ilustrues i dizenjimit te algoritmeve konkurente dhe qe perdoret per te ilustruar ceshtjet e sinkronizimit dhe teknikave per zgjidhjen e tyre. Eshte formuluar ne vitin 1965 nga Edsger Dijkstra, si ushtrim provimi, qe ne terma kompjuterike do te thote konkurenca per akses ne periferike si psh aksesi ne disk. Ilustrimi i problemit darka e filozofeve Pese filozofe gjenden ne nje tryeze dhe duan te darkojne ne nje pjate me spageti. Ndodhet nje pirun midis 2 filozofeve. Cdo filozof duhet te mendoje dhe te haje. Nje filozof mund te haje vetem nese i ka te dy pirunat njerin ne te majte dhe tjetrin ne djathte ne te njejten kohe. Cdo pirun duhet te mbahet vetem nga nje filozof dhe nje filozof mund te haje vetem nese piruni nuk eshte i zene nga nje filozof tjeter.Pasi filozofi mbaron se ngreni, duhet te vendose pirunin me qellim qe tu jape te tjereve mundesine qe te hane. Nje filozof mund te marre nje pirun ne te djathten ose ne te majten e tij nese vihen ne dispozicion te tij, por nuk mund te filloje te haje nese nuk i ka te dy pirunjte ne dispozicion. E ngrena nuk eshte e limituar, qe do te thote qe mund ta supozojme pjaten me spageti si burim I palimituar. Problemi eshte si te mund te dizenjojme nje disipline per te ngrene (algorime konkurent) qe filozofet te mos mbeten pa ngrene ? Nese alternojme te ngrenin dhe mendimin, duhet te kemi parasysh qe filozofet nuk mund ta dijne se kur filozofet e tjere kane deshire te hane apo te mendojne. Ky problem eshte dizenjuar per te ilustruar shmangien e deadlock, gjendja e sistemit ne cilen nuk mund te kemi progress te metejshem.Per te pare nese dizenjimi I zgjidhjes eshte i duhuri, konsideroni propozimin e meposhtem: Instruktoni cdo filozof te sillet si me poshte: Mendo derisa piruni i majte te vihet ne dispozicion; nese vihet merre ne dore; Mendo derisa piruni i djathte te vihet ne dispozicion; nese vihet merre ne dore; Kur te dy pirunat jane ne dore, fillo se ngreni deri ne nje kohe te caktuar; Vendos , pirunin e djathte ne tryeze; Vendos , pirunin e majte ne tryeze; Fillo nga e para Kjo zgjidhje deshton: lejon qe sistemi te kaloje ne gjendje deadlock, dhe nuk ka mundesi per progres te metejshem.
- 2. Ky eshte rasti kur cdo filozof, ka marre pirunin e majte dhe pret per pirunin e djathte. Me instruksionet e dhena kjo gjendje mund arrihet, dhe kur arrihet filozofit i duhet te prese pafundesisht per pirunin tjeter. Resource starvation- Vdekja nga burimi-mund te ndodhe gjithashtu ne menyre te pavarur nga deadlock, nese nje filozof i caktuar nuk mund te marre te dy pirunjte per efekt te kohes. Psh mund te kete nje rregull qe filozofi te vendose pirunin nese pret per nje periudhe deri 10 minuta per pirunin tjeter dhe te prese edhe 10 minuta te tjera per tentativen tjeter.Kjo skeme eliminon mundesine per deadlock (sistemi mund te avancoje ne nje gjendje tjeter) por perseri mund te kete probleme me livelock. Kjo ka te beje me gjendjen qe ndodh kur dy ose me shume procese ne menyre te vazhdueshme ndryshojne gjendjen e tyre ne pergjigje te ndryshimeve te procesit tjeter. Rezultati ne kete gjendje eshte qe askush nga proceset nuk arrin te perfundoje. Livelock ne shembullin tone pasqyrohet kur te gjithe filozofet shfaqen ne te njejten kohe ne dhomen e ngrenies dhe cdo njeri prej tyre merr pirunin e majte ne te njejten kohe dhe pret 10 minuta derisa te marre pirunin tjeter , nuk e merr pirunin , perseritet cikli filozofi pret 10 minuta te tjera perpara se te marre pirunin tjeter. Mutual exclusion eshte berthama e problemit; filozofet qe darkojne krijojne nje skenar te pergjithshem dhe abstrakt, I nevojshem per shpjegimin e ceshtjeve te tilla. Deshtimet qe mund te hasin keta filozofe jane analoge me veshtiresite qe ndeshen ne programime kompjuterike kur shume programe duhet te ekzekutohen dhe kerkojne akses ne burimet e ndara. Te gjitha keto ceshtje studiohen ne lenden e programimit konkurent. Problemi ne origjine Dijkstra,i referohej paisjeve te jashtme si psh disqeve te jashtme.Sidoqofte, veshtiresite qe morem ne konsiderate ne darken e filozofeve, ndeshen shume me shpesh kur disa procese aksesojne nje grup te dhenash qe jane azhornuar. Sisteme te tilla si psh berthamat e sistemit operativ, perdorin mijera lock (bllokime) dhe sinkronizime qe kerkojne zbatim strikt te metodave dhe protokolleve nese duhet te shmangen probleme te tilla si deadlock, starvation ose korruptime te dhenash. 2 Zgjidhje Zgjidhja e hierarkise se burimeve - Resource hierarchy solution Kjo zgjidhje e problemit eshte propozuar nga Dijkstra. Ajo i cakton nje renditje te pjesshme te burimeve (piruneve ne kete rast) dhe krijon nje marreveshje qe te gjitha burimet do kerkohen te renditura, dhe asnje nga dy burimet (pirunet) qe nuk kane lidhje renditje me njera-tjetren nuk do te perdoren nga nje njesi pune ne te njejten kohe. Ne kete rast burimet (pirunat) do te etiketohen me numrin 1 deri ne 5 dhe cdo njesi pune (filozof) do te marr ne fillim pirunin qe ka numrin me te vogel dhe pastaj pirunin qe ka numrin me te madh midis dy pirunjve qe ai ndermend te perdore. Rendi qe duhet te ndjeke cdo filozof per te leshuar pirunin nuk ka rendesi. Ne kete rast nese 4 filozofe nga 5, kapin ne te njejten kohe pirunat me numrin me te vogel, vetem numri me i madh do te mbetet ne tavoline, dhe filozofi i peste ne kete menyre nuk do te mund te kape asnje pirun. Per me teper, vetem nje filozof do te kete akses tek piruni me numrin me te madh qe te mund te filloje te haje me dy piruna. Zgjidhja me hierarkine e burimit shmang deadlock, por nuk eshte gjithnje praktike, sidomos nese lista e burimeve te kerkuara nuk njihet paraprakisht.Psh.Nese nje filozof mban burimin 3 dhe 5 dhe me pas percakton se do te kerkoje edhe burimin 2, ai duhet te leshoje burimin 5, pastaj 3 para se te marre burimin 2, pastaj te rikerkoje burimin 3 dhe 5 ne kete renditje.Programet kompjuteriket qe aksesojne numer te madh rekordesh ne databaze nuk do te ekzekutohen ne menyre te efektshme nese do tu kerkohet te leshojne te gjitha rekordet me vlerat me te larta perpara aksesimit te nje rekordi te ri, duke e bere kete lloj zgjidhje jo praktike per kete qellim.
- 3. Zgjidhja me udheheqes - Conductor solution Nje zgjidhje tjeter alternative mund te arrihet duke prezantuar nje kamarier ne tavoline. Filozofi do te kerkoje lejen e tij para se te kape nje pirun. Duke qene se kamarieri ka informacion sesa pirunj jane ne perdorim, ai eshte ne gjendje te gjykoje dhe parandaloje deadlock. Kur 4 piruna jane ne perdorim, filozofi tjeter qe te kerkoje nje pirun duhet te prese miratimin e kamarierit, dhe ky miratim nuk jepet deri sa nje pirun tjeter te leshohet. Logjika eshte e thjeshte duke specifikuar qe filozofi duhet te kerkoje marre pirunin ne doren e majte, para pirunit ne doren e djathte ( ose anasjelltas).Kamarieri vepron si semafor. Per te ilustruar sesi punon konkretisht kjo zgjidhje, konsiderojme qe filozofet te etiketohen sipas drejtimit te akrepave te ores nga A ne E. Nese A dhe C jane ne proces te ngreni, ath 4 pirunj jane ne perdorim. B ulet midis A dhe C dhe nuk ka asnje pirun ne dispozicion, nderkohe qe D dhe E kane nje pirun te paperdorur midis tyre. Nese supozojme se D do te haje, kur ai deshiron te kape pirunin e peste, mund te ndodhe deadlock.Nese ai i kerkon kamarierit dhe ai i thote te prese, mund te jemi te sigurte qe heren tjeter 2 piruna do te leshohen dhe do te kemi te pakten nje filozof qe mund te rezultoje I suksesshem qe te kerkoje 2 piruna, duke eliminuar ne kete menyre deadlock. Chandy / Misra solution-Zgjidhja Kandi/Misra Kandi dhe Aggarwal ne 1984 propozuan nje zgjidhje te ndryshme per darken e filozofeve, duke lejuar agjentet diktues ( P1,.Pn) te luftojne per nje numer burimesh arbitrare, ndryshe nga zgjidhja Dijkstra. Eshte komplet e shperdare dhe nuk ka nevoje per nje autoritet qendror pas inicializimit. Sidoqofte, thyen kerkesen filozofet nuk i flasin njeri-tjetrit (per shkak te mesazheve kerkues). 1. Per cdo cift filozofesh qe pretendon nje burim, kapet nje pirun dhe I jepet filozofit qe ka ID me te vogel. Cdo pirun mund te jete i paster ose i papaster.Fillimisht te gjithe pirunjte jane te papaster 2. Kur nje filozof kerkon te perdore disa burime (psh te haje), ai duhet ta marre pirunin nga fqinji i tij. Per te gjithe pirunjte qe ai nuk I disponon, dergon nje mesazh kerkues. 3. Kur nje filozof qe ka nje pirun merr nje mesazh kerkues, ai e mban pirunin e tij nese eshte I paster, por leshon pirunin qe mund te jete i papaster. Nese e leshon pirunin ai fillimisht e pastron ate. 4. Kur filozofi mbaron se ngreni, pirunjte e tij jane te papaster. Nese nje filozof tjeter ka bere kerkese per pirun ai e pastron ate dhe e leshon. Kjo zgjidhje lejon nje shkalle te madhe konkurence dhe zgjidh disa probleme te medha arbitrare. Zgjidh gjithashtu problemin starvation.Etiketat e paster/e papaster, veprojne si menyre per tu dhene perparesi proceseve qe kane me shume uri, dhe perbejne disavantazh per proceset qe sapo kane ngrene. Ne rastin e darkes se filozofeve, mund te themi qe filozofet nuk lejohen te hane dy here, ne nje radhe pa u dhene mundesine te tjereve te perdorin pirunjte ndermjet tyre. Ne analizen e tyre, ata derivojne ne nje sistem me nivele preferencash qe nis nga shperndarja e burimeve (pirunjve) dhe gjendja e paster/papaster. Ata tregojne qe ne kete sistem, mund te pershkruhet nje grafik aciklik, i cili nuk mund te shnderrohet ne ciklik. Kjo garanton shmangien e deadlock. Sidoqofte, nqs sistemi inicializohet ne nje gjendje perfekte simetrike, psh sic eshte rasti qe te gjithe filozofet mbajne pirunin e majte, ath grafiku eshte ciklik qe ne fillim, dhe zgjidhja mund te coje ne deadlock. Inicializimi i sistemit ku filozofet me id te ulet kane pirunj te papaster siguron qe ne fillim qe grafiku te jete aciklik. 3