Os-02 Procesi

4. PROCESI U RAČUNALNIM SUSTAVIMA 4.1. Pojam procesa Programi se mogu podijeliti na programske zadatke. To su odsječci programa koji obavljaju jednu cjelovitu funkciju. Veći programi dobivaju se kombiniranjem više zadataka. Kada se programski zadatak izvodi na računalu (tj.dobiju atribute vremena) on se naziva računalnim procesom ili kraće: procesom. Ovdje se naziv proces koristi u smislu “laki proces”, “osnovni proces”, “slijed instrukcija, nit”. Pojam procesa može se bolje shvatiti, ako se promatraju promjene sadržaja registara procesora i sadržaja spremničkih lokacija. Neka je r - vektor sadržaja registara m- vektor sadržaja spremničkih lokacija

S =

[ mr ]

1

vektor stanja računalnog sustava

Sekvencijski programski zadatak može se promatrati kao niz instrukcija f 1 , f 2 ,..... fN Instrukcije djeluju tako da se mijenja stanje sustava. Uz početno stanje S dobiva se slijed stanja: 0 S , S , S , ........., S , 0 1 2 N pri čemu je S = f (S ). K+1 K K Stanje S ovisi samo o neposredno prethodnom stanju S , što olakšava K+1 K izvođenje prekidnog rada. Početno stanje S 0 sadrži ulazne podatke Završno stanje S N sadrži izlazne podatke. Rastući indeksi ukazuju na rast vremena. Obavljenje svake instrukcije traje izvjesno vrijeme. U trenutku t može se očitati početno stanje 0

2

a1

U jednostavnom modelu jednoprocesorskog sustava stanje SK =

[ mr ]

može se sačuvati ako se; • sačuva sadržaje registara procesora u posebnom dijelu spremnika; • predvidi za svaki od mogućih procesa lokalni radni prostor u spremniku, koji neće biti diran od drugih procesa. U trenutku prekidanja procesa sadržaji registara se spremaju, a neposredno prije nastavljanja sadržaji se moraju obnoviti (to je tzv. promjena konteksta, engl. context switching) 3

Završetkom instrukcije f1 u trenutku t može se očitati stanje S 1. U trenutku t proces okončava i može se očitati završno stanje SN. Kada se promatra programski zadatak T (od engl. task) i njemu pripadni proces P , tada se pretpostavlja da će se niz instrukcija obaviti ispravno i ne zanimaju nas međustanja S i , i/ = 0,N. Važno je samo znati kako će početno stanje S 0biti preslikano u završno stanje, tj.može se zamisliti da zadatak (proces) obavlja neku složenu T funkciju f , te je S N= f T(S 0) Detaljnije: Može se pretpostaviti da je za zadatak T i: Di -domena Dipodskup m R i - kodomena R i podskup m te R i=f T i(D i). 4

a2

U trenutku t 0 proces Pi “čita” ulazne podatke iz D i , a u trenutku t N proces “piše” rezultate u Ri , tj. fT : Dj Ri i

Dva zadatka su nezavisna (međusobno) ako je (nazovimo ih Ti i Tj ) Di ∩ R j= 0 i Dj ∩ R i= 0 i R i ∩ R j= 0 ili (Ri ∩ R j) ∪(D i ∩ Rj ) ∪ (D j ∩ Ri )= 0. Treba uočiti da smije biti D i ∩ D j = 0, tj. zadacima ne smeta dio “samo čitaju” iz nekih zajedničkih lokacija (jer se čitanjem ne mijenja sadržaj). Izvođenje procesa može se prekinuti u svakom trenutku t K (iza obavljanja instrukcije fK. Ako se sačuva stanje S K , on se može nastaviti u budućnosti nakon proizvoljno dugačkog vremena. 5

4.2. Sustav zadataka, zavisni i nezavisni zadaci Svaki složeniji posao može se podijeliti na dijelove - zadatke. Suradnjom zadataka obavlja se cjeloviti složeniji posao. U pojednostavljenom modelu može se definirati sustav zadataka kao:

1

2

N

T = { T , T , ….. T } skup zadataka; × < -relacija parcijalnog uređenja skupa T T. < -”obaviti prije” Primjer: 1 2 3 4 5 6 7 T={T,T,T,T,T,T,T} 1 2 1 3 1 4 T
6

a3

Sustav zadatka prikazan grafom

Relacija < je tranzitivna, tj. (T i < Tj ) i (Tj < TK ) ==> Ti < TK Tako je T1 < T2 < T3 < T4 < T5 < T6 <

Tj Tj Tj Tj Tj Tj

j∈{2,3,4,5,6,7} j∈{5,7} j∈{5,6,7} j∈{6,7} j∈{7} j∈{7}

T1 T2

T3 T5

T4 T6

T7

Zadaci na istom puto od početnog do krajnjeg čvora se međusobno zavisni i moraju se izvoditi propisanim redoslijedom.

7

Zadaci koji nisu na istom putu moraju biti međusobno nezavisni tj. za njih mora biti ispunjen uvjet: (Ri ∩ R j) ∪(D i ∩ Rj) ∪ (D j ∩ Ri )= 0. U primjeru to mora vrijediti za zadatke: (T2, T3), (T2, T4 ), (T2 , T6) (T3 , T4) (T4 , T5) (T5, T6) Međusobno nezavisni zadaci mogu se izvoditi priozvoljnim redoslijedom Pri ostvarenju sustava zadataka (tj. pri njegovoj interpretaciji kao sustav procesa) pojavljuje se problem sinkronizacije procesa - mehanizma za dojavljivanje, kojim jedan zadatak dojavljuje drugom da je završio svoj posao. Drugi problem pri ostvarivanju sustava zadataka je da neki zadaci, koji su inače nezavisni troše (koriste) neka zajednička sredstva koja se smiju koristiti pojedinačno. 8

a4

Korištenje takvih dijeljenih sredstava je samo u dijelu zadatka koji se naziva kritičnim odsječkom (engl. critical section). Ostali dio zadatka je nekritični odsječak. Kritični odsječci zadataka moraju se obavljati međusobno isključeno (ne u isto vrijeme), te se govori o problemu međusobnog isključivanja (engl. mutual exclusion).

9

4.3.

Međusobno isključivanje Promotrimo dva zadatka s kritičnim odsječcima T0 i T1 , koji će postati procesi P0 i P1. Neka oni rade u jednom procesorskom sustavu, ali zbog toga što djeluju prekidi oni mogu biti proizvoljno prekidani na kraju svake instrukcije. Moglo bi se zamisliti naivno rješenje međusobnog isključivanja upotrebom jedne varijable nazovimo je ZASTAVICA: ZASTAVICA = 0 slobodan ulaz ZASTAVICA = l zabranjen ulaz Proces P0 Proces P1 …… …….. pročitaj ZASTAVICA pročitaj ZASTAVICA; dok je ZASTAVICA ≠ 0 činiti dok je ZASTAVICA ≠ 0 činiti pročitaj ZASTAVICA pročitaj ZASTAVICA ZASTAVICA: = 1; ZASTAVICA: = 1 ; kritični odsječak: kritični odsječak: ZASTAVICA: = 0 ; ZASTAVICA: = 0 ; Može se dogoditi da oba procesa ustanove da je zastavica=0 i uđu u10 kritični odsječak.

a5

U svakom ciklusu procesor koji dobije sabirnicu može obaviti samo jedno čitanje ili jedno pisanje Procesi neka budu ciklički, tj. oblika: ponavljati kritični odsječak; nekritični odsječak; do beskonačnosti Dodatne pretpostavke i zahtjevi: 1. Svaki od procesa izvodi se na jednom od N procesora s atomarnim instrukcijama čitanja i pisanja 2. Brzina pojedinih procesa je proizvoljna. 3. Kada se proces obavlja u svom nekritičnom dijelu on ne smije spriječiti drugi proces da uđe u svoj kritični odsječak. 4. Izbor jednog od procesa za ulazak u kritični odsječak mora se obaviti u konačnom vremenu. 11

Sklopovska potpora međusobnom isključivanju U jednoprocesorskom sustavu se međusobno isključivanje može obaviti zabranom prekidanja prije ispitivanja varijable u globalnom spremniku. U više procesorskom sustavu se zabranom prekidanja u pojedinačnom procesoru ne može spriječiti drugi procesor u pristupanju istoj lokaciji spremnika. Rješenje: Dodjeljivač sabirnice treba tako modificirati da omogući dodijeljivanje uzastopnih spremničkih ciklusa istom procesoru. U svakom procesoru predviđenom za višeprocesorski rad mora postojati instrukcija (ili više njih) koja: •dohvaća iz spremnika sadržaj s adresirane lokacije i zapisuje na istu adresu drugi sadržaj, •postavlja na sabirnicu signal koji može prepoznati dodjeljivač sabirnice. 12

a6

Dodjeljivač sabirnice prepoznaje signal i ostavlja procesoru sabirnicu još i u slijedećim ciklusu. Moguće rješenje: Ne bi se smjelo dozvoliti da se za vrijeme ispitivanja ZASTAVICA instrukcija dvaju procesa međusobno isprepliću. U jednom procesorskom sustavu (oba procesa izvode se na jednom procesoru) se to može ostvariti zabranom prekidanja. Proces P0 …….. zabraniti prekidanje; kritični odsječak; dozvoliti prekidanje;

Proces P1 …….. zabraniti prekidanje; kritični odsječak; dozvoliti prekidanje;

Onaj proces koji prvi izvede instrukciju zabrane prekidanja obavit će svoj kritični odsječak, a s obzirom da prekidanje nije dozvoljeno drugi proces ne može nikako biti aktiviran. 13

Međutim, u više procesorskom sustavu se ne može zabrana prekidanja nametnuti svim procesorima. Mora se pretpostaviti da su atomarne (nedjeljive) instrukcije čitanja odnosno pisanja. k-1

k+1

čita j

piši j

}

k

nedjeljivo

k+2

neprekidivo

Za dva nedjeljiva ciklusa se govori kao o jednom nedjeljivom ciklusu čitanja i pisanja (engl. read_modify_write) Najjednostavnija rješenja: •Instrukcija ispitaj_i_postavi (engl. test and set - TAS) TAS ZASTAVICA ACC: = ZASTAVICA ZASTAVICA=1 nedjeljivo

}

14

a7

Instrukcija LOCK iza koje slijedi instrukcija zamjeni (engl. exchange - XCHG) LOCK XCHG ZASTAVICA ACC : ZASTAVICA ZASTAVICA : = ACC

} nedjeljivo

Međusobno isključivanje se obavlja jednostavno Proces Pi ponavljati TAS ZASTAVICA; dok je ACC ≠ 0 činiti TAS ZASTAVICA; kritični odsječak; ZASTAVICA: = 0; nekritični odsječak; do beskonačnosti

15

ili Proces Pi ponavljati ACC: = 1 LOCK ; XCHG ZASTAVICA; dok je ACC = 1 činiti LOCK ; XCHG ZASTAVICA ; kritični odsječak; ZASTAVICA : = 0; nekritični odsječak; do beskonačnosti 16

a8

Svaki od procesora ima specifična rješenja: Npr. **Intel 486: Prefiks LOCK se može upotrijebiti ispred instrukcija: * za ispitivanje i promjenu bitova BTS, BTR BTC * za jednooperandne instrukcije INC, DEC, NOT, NEG *za dvooperandne instrukcije ADD,ADC,SUB,SBB;AND,OR *za zamjene XCHG XADD CMPXCHG kada te instrukcije adresiraju (modificiraju) sadržaje u spremniku. (Ispred XCHG čak i nije potreba LOCK!). Ako se LOCK upotrijebi ispred drugih instrukcija (ili spomenute ne adresiraju spremnik) generira se iznimka kao i ta nepostojeći operacijski kod. 17

** Digital Alpha: Ima par instrukcija LDQ_L i STO_C LDQ_L R1,ZASTAVICA Modificiraj R1; STQ_C R1 ZASTAVICA; (Spremi R1 u ZASTAVICA) U ovom odsječku mogu se koristiti samo instrukcije koje adresiraju registre i instrukcije grananja. Ovakva sklopovski podržana rješenja mogu se koristiti samo u čvrsto povezanim sustavima (u kojima se sabirnica ili mreža za prospajanje može jednoznačno koristiti i upravljati. U raspodijeljenim sustavima se za međusobno isključivanje moraju koristiti mehanizmi koji su slični Lamportovom 18 rješenju

a9