Os-05 Prostor Spremnika

8. KORIŠTENJE I RASPOREĐIVANJE PROSTORA SPREMNIKA 8.1. UVODNA RAZMATRANJA U dosadašnjem opisu pojava u računalnom sustavu pretpostavljalo se da su programi u strojnom obliku smješteni u spremnik čiji je adresni prostor velik 2m bajtova uz m adresnih bitova. U današnjim sustavima je uobičajeno da adresiranje počinje s 0 i završava s adresom 2m-1. Ako su podaci smješteni u uzastopne bajtove adrese moraju biti (ili je prikladno da budu) “poravnate”. 1

podatak (operand)

duljina

adresa završava s bitovima

bajt poluriječ riječ dvostruka riječ četverostruka riječ

8b 16 b 32 b 64 b 128 b

... ... ... ... ...

xxxx xxxo xxoo xooo oooo

Adrese se unutar procesora generiraju u • programskom brojilu • registru kazaljke sloga • adresnim registrima na temelju sadržaja adresnog dijela instrukcija

2

a1

U najjednostavnijem načinu upotrebe spremnika - jednoprogramskom radu - uvijek je samo jedan program u glavnom spremniku. 0

POČETNA ADRESA KORISNIČKOG SUSTAVA

OPERACIJSKI SUSTAV

PROGRAM A

PROGRAM B

PROGRAM C

2m-1 3

Svi programi moraju biti pripremljeni tako da im je • početna adresa jednaka je početnoj adresi korisničkog prostora • veličina manja ili najviše jednaka veličini slobodnog korisničkog prostora Programi B i C moraju se pripremiti za izvođenje i smjestiti u pomoćni (vanjski) spremnik. Kada program A završi u spremnik se može staviti program B ili program C. U načelu bi se ti programi mogli smatrati zadacima jednog sustava zadataka.Višeprocesni (ili višeprogramski) rad mogao bi se ostvariti tako da se pri prebacivanju procesora s procesa na proces u “promjenu konteksta” uključi pražnjenje i punjenje glavnog spremnika. Sličan pristup tzv. preklopnog korištenja spremnika (engl. overlay technique), omogućuje izvođenje programa većih od slobodnog korisnika tog prostora. 4

a2

OPERACIJSKI

SUSTAV STALNI DIO

STALNI DIO PREKLOPNI DIO 1 PREKLOPNI DIO 2 PREKLOPNI DIO 3

Pokazuje se da se već i u najjednostavnijem načinu raspoređivanja spremničkog prostora mora računati s pomoćnim vanjskim spremnikom. Kao pomoćni spremnici danas služe magnetski diskovi. Pretežiti dio diskovnog spremničkog prostora koristi se za smještanje datoteka, no jednako je tako važan i kao pomoćni prostor pri gospodarenju glavnim (radnim) spremnikom. 5

Stoga će prije daljnjih računa raspoređivanja prostora spremnika obraditi svojstva diskova. 8.2. Svojstva magnetskih diskova i njihovo korištenje Jedinka magnetskog diska (engl. magnetic disk drive) sastoji se od: - jedne ili više okruglih ploča presvučenih magnetskim materijalom koje rotiraju konstantnom kutnom brzinom i glava za čitanje i zapisivanje koje se pokreću radijalno; - upravljačkog sklopa sastavljenog od mikroprocesora, spremnika i sučelja prema računalnoj sabirnici.

6

a3

ω ploča cilindar (cylinder) staza (track) sektor

Glava za čitanje i pisanje

sektor

Ruka

reper

7

• glave za čitanje i pisanje mogu se precizno pozicionirati na jednu od koncentričnih staza. • staze su podijeljene na sektore jednake veličine • iako se sve glave pomiču istovremeno na svim diskovima u pravilu se čita samo sektor na jednoj ploči (ili se piše samo jedan sektor). Neka svojstva današnjih diskova • Ploče promjera od 1.3 do 8 inča. Tipični promjeri: 2.5 , 3.5 , 5.25 inča • Gustoća staza 1500 do 5000 staza/inč • Gustoća bitova na stazi 40 000 do 60 000 bitova/inč • Broj ploča u diskovnoj jedinki od 1 do 20 8

a4

• Broj bajtova po sektoru tipično: 256, 512 ili 1024 (vidljivo sa strane računala, inače se znatan broj bitova jednog sektora koristi za korekciju grešaka ) • Mnogi diskovi imaju staze grupirane u zone (3 do 20 zona). Zone s većim promjerom staza imaju više sektora kako bi se iskoristila moguća gustoća bitova. • Svaki sektor ima svoju jedinstvenu adresu, koja se izračunava iz: • rednog broja ploče; • rednog broja staze na ploči; • rednog broja sektora na stazi.

9

Dinamička svojstva Prijenos podataka obavlja se po sektorima. Vrijeme potrebno za obavljanje prijenosa dijeli se na: • vrijeme za postavljanje glava (engl. head-positioning time) • vrijeme za prijenos podataka (engl. data transfer rate) Vrijeme za postavljanje glava ima dvije komponente: • vrijeme postavljanja (glave na stazu) (engl. seek time) • rotacijsko kašnjenje (engl. rotational lateney)

10

a5

Rotacijsko kašnjenje određeno je brzinom okretanja ploča. Uobičajena brzina n=3 600 okretaja/min Brzi dijelovi do 7 200 okretaja/min za 3 600 okretaja/min TR=1/60 sekundi = 16.6 ms Prosječno rotacijsko kašnjenje je TR= 1/2 TR = 8.3 ms

11

Upravljački sklopovi podliježu standardima, npr. • SCSI ( Small Computer Standard Interforce ) • IPI - 3 ( Intelligent Peripheral Interface - 3 ) Jedinično se prenose blokovi. Veličina bloka je jednaka veličini sektora ili je višekratnik veličine sektora. U jednom zahtjevu može se prenijeti više blokova. Upravljački sklop: • prihvaća zahtijev za prijenos • obavlja prevođenje logičke adrese sektora u fizičku adresu (broj ploče, broj staze, broj sektora); • određuje redoslijed obavljanja zahtjeva. Pripremni poslovi u upravljačkom sklopu također traju neko vrijeme. Tipično : 0.3 do 1.0 ms 12

a6

Procesor postavlja zahtjev . Obrada zahtjeva

Prijenos u glavni spremnik može početi nakon što je s diska prenesena stanovita količina

Obavijest o ispunjenju zahtjeva

DMA

t

Rotacijsko kašnjenje

Upravljač Disk

t Prijenos s diska

Postavljanje glave Procesor postavlja zahtjev . Obrada zahtjeva DMA

Obavijest o ispunjenju zahtjeva Upravljač

t

Postavljanje glave

Roracijsko kašnjenje Prijenos na disk

Disk

t

13

Podaci za neke komercijalne diskove Tip

Seagate ST434001N Elik-3 SCSI

Promjer 5.25 inč Kapacitet 2.8 GB Broj cilindara 2627 Staza po cilindru 21 Sektora po stazi ~99 Bajta po sektoru 512 Trajanje okreta 11.1 ms 5400 o/min Minimalno 1.7 ms postavljanje ( 1 staza) Prosječno 11.0 ms postavljanje

HPC2200A

HP47560

5.25 inč 5.25 inč 335 MB 1.3 GB 1449 1962 8 19 113 72 256 512 14.99 ms 14.99 ms 40020 o/min 40020 o/min 2.5 ms 1.6 ms x

x 14

a7

“Dugo” postavljanje 10.8+0.012d ms preko d staza “Kratko postavljanje 3.45+0.597 d ms ispod d staza d 616 Postavljanje preko cijelog 22.5 ms xx diska Brzina 4.6 MB/s 1.2 MB/s prijenosa

8.00+0.008d ms 3.24+0.4 d ms 383 xx 10 MB/s

x može se izračunati za d=1/3 1449 odnosno 1/3 1962 xx može se izračunati za d=1449 odnosno 1962 15

Vrijeme (trajanje) postavljanja sastoji se od: - trajanja ubrzavanja ruke, - kretanja konstantnom brzinom (za velike razmake staza), - trajanja usporavanja ruke, - trajanja finog pozicioniranja. Trajanje postavljanja ovisi o razmacima između staza koje glava (ruka) treba savladati : - kod “kratkih pomaka” nema kretanja konstantnom brzinom, već se prvo polovinu vremena ruka ubrzava, a drugu polovinu usporava - kod prelaženja preko svih staza (od najvećeg do najmanjeg promjera) može se koristiti režim “brzog” prijelaza. Prosječno vrijeme postavljanja koje se navodi u podacima odnosi se na prijelaz preko trećine staza (ali nije jednoznačno defini16 rano).

a8

Model diska za ilustrativne primjere Broj ploča (površina) Broj cilindara (staza na ploči) ⋅ Broj sektora na stazi Veličina sektora Brzina vrtnje

P = 10 C = 2000 S = 100 V = 512 B n = 4 800 o/min = 80 o/s TR= 12.5 ms

Trajanje 1 okretaja Trajanje postavljanja glava preko d staza d ≤4 TS= 1.5 d ms TS=4.0+0.5 d 4 ≤ d ≤ 400 TS=10.0+0.01d d ≥ 400 Kapacitet C •S •P •V = 1024 •106 B Brzina prijenosa VP= 4.096 •106 B/s VP= (V• S)/TR = V •S •n

17

Primjer: Koliko je trajanje prijenosa programa veličine 1 MB = 1024 KB s diska u radni spremnik? Zanemariti sva vremena zadržavanja upravljačkog sklopa. Koristiti podatke za model diska. Razmotriti dva slučaja: a) program je smješten na disku kompaktno b) program se prenosi u blokovima veličine 1 KB smještenim u dva uzastopna sektora, s tim da ti parovi mogu biti raspršeni po cijelom disku. a) Za 1024 KB potrebna su 2048 sektora Kompaktni smještaj : 3 uzastopna cilindra 2 cilindra puna 2 000 sektora u 3. cilindru 1 staza (48 sektora)

18

a9

Trajanje: • postavljanje na 1. cilindar 10.0+c/3 •0.01 16.66 ms • • rotacijsko kašnjenje 1/2TR=1/2 12.5 6.25 ms • prijenos 10 staza 10TR= 125 125.00 ms • premještanje na susjedni cilindar 1.50 ms • prijenos 10 staza 10TR=125 125.00 ms • premještanje na susjedni cilindar 1.50 ms • 6.25 ms • rotacijsko kašnjenje 1/2TR=1/2 12.5 • • priojenos 48 sektora 48/100TR=0.48 12.5 6.00 ms Ta= 294.41 ms b) Za svaki par sektora treba 1024 puta uzeti u obzir • postavljanje na cilindar 10.0+c/3 0.001 =16.66 ms • rotacijsko kašnjenje 1/2TR=6.25 ms • trajanje prijenosa 2 sektora 2/100TR=0.25 ms Tb= 1024 (16.66 + 6.25 + 0.25) = 23 715.84 ms = 23.72 s 19

Vrijeme (trajanje) prijenosa podataka ovisi o brzini prijenosa (engl. data transfer rate) Brzina prijenosa određena je brzinom okretanja i gustoćom bitova na stazi. Tipične brzine : 1 do 5 MB/s Upravljački sklop jedinke diska Glavni spremnik Blok DMA Procesor

Pristup

Buff. Mikroprocesor

Lokalni spremnik

20

a10

Upravljački sklop može zahtjeve za prijenos s cilindara posluživati na razne načine. Recimo da su redom prispjeli zahtjevi za pristup do cilindara : 1700, 200, 1900, 700, 800, 100, 1500, 1100 Glava za čitanje/pisanje nalazi se početno na cilindru 900

21

0 100 200

700 800 900

1100

1500

Početni položaj glave 1700 1900 FCFS: Glave su prešle preko 7800 staza

SSTF: Glave su prešlepreko 3200 staza

22

a11

FCFS first come first served SSTF shortest seek time first SCAN scan (LOOK) C-SCAN circular scan (C-LOOK) ODREĐIVANJE VREMENA POSTAVLJANJA I ROTACIJSKOG KAŠNJENJA FCFS d1 = 800 d2 = 1500 d3 = 1700 d4 = 1200 d5 = 100 d6 = 700 d7 = 1400 d8 = 400 TK=206 ms 23

STSF

d1= 100 d2= 100 d3= 400 d4= 400 d5= 200 d6= 200 d7=1700 d8= 100

Tk= . . . = 154 ms

24

a12

8.3. Statičko dodjeljivanje spremnika • Povijesno značenje • Adrese koje se generiraju u programu su fizičke adrese glavnog (radnog) spremnika • Programi moraju biti pripremljeni tako da započinju na početnoj adresi korisničkog adresnog prostora. • Pri pripremi programa stvara se tzv. premjestivi modul (relokatibilni) kod kojeg je početna adresa jednaka nuli, a sve ostale adrese referiraju se na tu početnu adresu. • Pretpostavimo da je strojni oblik zapisan u polje (riječi) R[1..k] i da su neke od njih adrese. U takovom pojednostavljenom modelu može se poljem bitova odrediti u kojoj riječi treba promijeniti adresu C[1..k]. C[i]=0 ne treba mijenjati C[i]=1 treba promijeniti 25

Neka je PA početna adresa apsolutnog modula, koji se zapisuje u A[1..k] Priprema apsolutnog modula je za i = 1 do k činiti ako je C[i] = 1 onda A[i] := R[i] + PA inače A[i] := R[i] Premještanje programa na drugu početnu adresu zahtijeva novo preračunavanje. U načelu program pripremljen u apsolutnom obliku nema smisla modificirati za novu PA, te se dodjeljivanje može nazvati statičnim. U višeprogramskom radu prikladno je da više programa (programskih zadataka, procesa) bude smješteno u radni spremnik. U ranijim sustavima se cijeli spremnik dijelio na particije. 26

a13

• Svaki od programa pripreman je za jednu od particija. • Particije su u načeli bile različitih veličina. REDOVI PROGRAMA ZA POJEDINE PARTICIJE

O.S. PA1

PA2

PA3

1 MB

1 MB

512 KB 256 KB PA5 256 KB PA4

27

Dio spremnika ostaje neiskorišten Dva razloga neiskorištenosti: • programi su u načelu manji od veličine particije (to je tzv. unutarnja neiskorištenost) • događa se da u nekim razdobljima nema programa (ili su blokirani) za pojedine particije, tako da cijela particija ostaje neiskorištena (premještanje programa iz particije u particiju je skupo!

28

a14

8.4 Dinamičko dodjeljivanje spremnika s jednim segmetom Priprema apsolutnog modula zahtijeva pribrajanje početne adrese na neke adresne sadržaje premjestivig modula.Taj se posao može obaviti sklopovski i to tijekom izvođenja programa u trenutku kada se adresira radni spremnik * Program stalno ostaje u premjestivom obliku tj. S početnom adresom jednakom nuli - to tzv. Logički adresni prostor programa. * Kada se program smjesti u spremnik, on je smješten u fizički adresni prostor. * Unutar procesora generiraju se adrese logičkog adresnog prostora, a kada se pristupa u spremnik one se prevode u fizičke adrese pribrajanjem početne adrese fizičkog adresnog prostora,

29

Al

Af +

Procesor Spremnik PA Bazni registar

Spremnički međusklop U višeprocesnom radu treba osigurati da procesi jedan drugom ne diraju adresni prostor. Nikako se ne može pouzdati u disciplinu (“bezgrešnost”) proizvođača programa. 30

a15

Prekid Da Af>Ogr

OGRADA

Spremnik Al

Procesor

Af +

PA Bazni registar

Af
Prekid

31

O.S PA1 Ograda1 PA2 Ograda2 PA2 Ograda3 PA3

P1

VELIČINA 1

P2

VELIČINA 2

OGRADAi=PAi+VELIČINAi

P3 P4

VELIČINA 3 VELIČINA 4

Ograda3

U opisnik procesa treba uvrstiti PAi i OGRADAi Prilikom promjene konteksta treba u BAZNI registari REGISTAR OGRADE napuniti sadržaje Pai i OGRADAi onog procesa koji se aktivira 32

a16

Kako voditi evidenciju o raspodjeli prostora spremnika ? Tokom rada neki procesi završavaju a drugi traže spremnik Stoga mogu nastati nepopunjeni dijelovi ili “rupe” S vremenom rupe mogu postati male tako da se ne može pronaći program koji bi je mogao pšopuniti. To je tzv. fragmentacija sprenmika

Puni blok Rupa

Faktor fragmentacije

Puni blok Rupa Puni blok

Zbroj veličina rupa f=

Rupa

Veličina korisničkog prostora Eviencija stanja spremnika može se voditi u dvije liste: * Lista punih blokjova * Lista praznih blokova - rupa

33

PUNI_B PA

PA

VELIČINA

VELIČINA

PA VELIČINA

PRAZNI_B

PA VELIČINA

PA VELIČINA

PA VELIČINA

Za smanjenje fragmentacije bilo bi korisno spajati susjedne rupe u veće cjeline. Za olakšanje spajanja može se alternativno voditi evidencija o 34 susjednosti blokova

a17

Npr. Uz svaki puni i prazni blok se na njegovu početku i kraju žrtvuje određeni broj bajtova

0 Veličina

1 Veličina

Veličina

0 Veličina

1 Veličina

Rupa s dodatnim kazaljkama

Puni blok

35

1 Veličina A’

1 Veličina A Veličina A Rupa 1 Veličina A 1 Veličina B Veličina B

OSLOBAĐANJE B

Veličina A’

Puni blok 1 Veličina B 1 Veličina C Rupa 1 Veličina C

Veličina C 1 Veličina A’ Veličina A’=VeličinaA+VeličinaB+VeličinaC

Spremnik je podijeljen na dva skupa blokova H={Hi | i=1,..n} skup rupa veličine hi F= {Fi | i=1,..m} skup punih blokova veličine fi

36

a18

Kada dođe novi zahtjev za dodjelu prostora veličine k, može se u načelu postupiti na dva načina: * dodjela prve odgovarajuće rupe, tj dodjeli se prva Hi za koju je hi>= k (first fit) * dodjeljuje se Hi za koju je ispunjeno hi>=k hi-k minimalno Pri tome se može postupiti na dva načina: Ako je hi-k <ε onda dodjeljuje se cijela rupa inače ostaje rupa veličine hi-k Čitavo vrijeme prati se fragmentacija. Ako fragmentacija postane značajna, onda se može zastati s radom i obaviti preslikavanje programa: * Programi se moraju fizički preseliti * U opisnike treba zapisati nove početne adrese 37

Kako ocijeniti fenomen fragmentacije? Knuthovo 50%-tno pravilo Pretpostavke: * Razmatra se stohostičko ravnotežno stanje: Vjerojatnost oslobađanja jednaka je vjerojatnosti zahtjeva. * Prosječna vrijednost broja punih blokova je m Prosječna vrijednost broja rupa ne n * Vjerojatnost q da će se pronaći rupa jednaka je veličini zahtjeva je vrlo mala. Suprotna vjerojatnost p=1-q je bliska jedinici. * Koristi se najbolje slaganje dodjele * Veličina spremnika je vrlo velika tako da se rubni uvjeti mogu zanemariti. * Pri oslobađanju punog bloka novonastala rupa spaja se sa susjednim rupama.

38

a19

Postoje četiri tipa punih blokova B

A

C

B

A

C

B

A

C

B

A

C

Oslobađanjem A dobiva se B

A

Tip i broj a blokova tipa:

C

B

C’

B’

b

m=a+b+c+d n=(2d+b+c)/2 S obzirom da je b=c, n=(2d+2b)/2=b+d

C

c

B’

c

Broj punih blokova Broj rupa 39

Vjerojatnost da broj rupa poraste za 1: (1) Vjerojatnost oslobađanja * a/m Vjerojatnost da broj rupa opadne za 1 (2) vjerojatnost oslobađanja *d/m+ vjerojatnost zahtjeva*q Iz uvjeta ravnoteže (1)=(2) vjerojatnost zahtjeva = vjerojatnost oslobađanja: a/m=d/m+q ili a/m=d/m+(1-p) tj a=d+(1-p)m pa je m=a+b+c+d=d+(1-p)m+2b+d = (1-p)m+2b+2d pm=2(b+d)=2n a kako je p->1 n=m/2 U stacionarnom stanju uz m punih blokova ima m/2 rupa u spremniku.

40

a20

Ocjena fragmentacije: Pretpostavke: b prosječna veličina punog bloka h prosječna veličina rupe h=k*b (naći koeficijent k) M Veličina memorije Slijedi: h=(M-mb)/n=(M-mb)/(m/2) M=mb(k/2+1) f=(n*k*b)/M=m/2*k*b/(m*b*(k/2+1)) f=k/(k+2) Simulacijom se može dobiti primjerice za : b=M/10 f=>0.1 h=>0.22b za b=M/3

f=>0.5

h=>2b

41

8.5 Dodjeljivanje spremnika straničenjem, ostvarenje virtualnog spremnika 8.5.1 Osnovne napomene. Za ostvarenje virtuelnog spremnika bitna je zamisao da se program može podijeliti u dijelove, koji ne moraju biti istovremeno u radnom spremniku . Začetak takvog korištenja spremnika je njegovo preklopno (Overlay) korištenje: -jedan osnovni dio programa . Stalni dio (root) mora se cijelo vrijeme nalaziti u spremniku - drugi dijelovi mogu se naizmjence premještati s vanjskog spremnika u radni i obrnuto. Programer mora voditi računa o svin detaljima ostvarenja takvog načina rada -podijeliti program na odgovarajuće dijelove -u stalni dio programa ugraditi mehanizme za donošenje odluke o prebacivanju preklopnih dijelova (overlaya) 42 -voditi evidenciju o načinu korištenja pojedinih dijelova

a21

Posao se usložnjava u višeprocesorskom radu i ne može se izbjeći fragmentacija spremnika. 8.5.2 Sklopovska podloga straničenja Program djeluje u svom tzv. logičkom adresnom prostoru. Procesor pri izvođenju programa djeluje u logičkom adresnom prostoru izračunava logičke adrese (tzv. efektivne adrese) Svaka lokacija u spremniku označena je svojom fizičkom adresom i govori se o fizičkom adresnom prostoru 0 1 2

p

}2

Logički adresni prostor dijeli se na stranice p. (page) veličine 2 m -> broj bitova efektivne adrese. p -> broj bitova za adresiranje unutar stranice r=m-p -> broj bitova za kodiranje rednog broja stranice

2r-1

43

U 32 bitnoj arhitekturi uz stranice veličine 4KB (p=log2(4096)) m=32, p=12, r=m-p=20 Veličina efektivne memorije 2m=220* 212=4GB Broj stranica 2r=220=1M stranica U 64 bitnoj arhitekturi uz stranice veličine 4KB (p=log2(4096)) m=64, p=12, r=m-p=52 m 32 32 9 Veličina efektivne memorije 2 =2 * 2 = 16* 10 GB Broj stranica 2r=252=4*106GB

0 1 2

2r-1

}2

p

Stvarni (fizički) spremnik podijeljen je na okvire jednake veličini stranice tj 2p

44

a22

m=r+p

p

r

Procesor

Prekid kod promašaja

q+p

Tablica q

2r*q

Spremnik

45

Broj stranice 0

A

1

B

2

Bit prisutnosti 0

4

1

Broj okvira 0

1

0

C

2

0

3

D

3

0

1

4

E

1

2

5

4

1

5

0

F

6

0

6

G

7

7

H

Logički adresni prostor

3

1

Tablica prevođenja

E

3

H

4

A

Fizički adresni prostor

Pomoćni spremnik (disk) 46

a23

r

p

Logička adresa

RAM 2r*q Fizička adresa q

p

Pri adresiranju fizičkog spremnika bi trebalo: - pristupiti do spremnika i dohvati lokaciju u tablici prevođenja (tablicu stranice) - oblikovati fizičku adresu i pristupiti do adresirane lokacije u fizičkom spremniku 47

Stoga se uz procesor (memorijski međusklop postaje dio procesora) dograđuje priručni međuspremnik za prevođenje adresa u kojem se zapisuju adrese adrese okvira (engl. Translation lookaside buffer TLB) (to je obično asocijativni međuspremnik). U međuspremniku se osim adrese (rednog broja) okvira zapisuje bit prisutnosti a i neki drugi bitovi koji pomažu pri adresiranju.

48

a24

Primjer: Intel 486 p=12 r=q=20 m=32 Tablica prevođenja je dvorazinska: * bitovi 22 - 31 određuju indeks u tablici tablica (directory) * bitovi 12 - 21 određuju indeks u tablici stranica (table) 31

22 21

r

10

CR3 registar

12 18

p

10

Tablica tablica (page dir.)

Tablice stranica

0

12

20

49

Tablica stranica je također stranica veličine 4096 bajta te sadrži adrese 1K okvira. Tablica tablica je također stranica veličine 4K i može adresirati 1K tablica stranica. To znači da: *Jedna tablica tablica može adresirati 1K*1K=1M stranica tj čitav linearni adresni prostor od 4GB. * Tablice zauzimaju 4MB + 4KB prostora za 4GB veliki program. Operacijski sustav se može odabrati da se * jedna tablica tablica koristi za sve zadatke ili * jedna tablica tablica koristi za svaki zadatak posebno ili * postupa proizvoljno Pri izvođenju nekog programa tablica tablica mora biti u radnom spremniku Pojedine tablice stranica moraju se dobaviti u radni spremnik kada se 50 koriste.

a25

Stranice koje se dohvaćaju imaju adrese svojih okvira u TBL međuspremniku. Taj međuspremnik se automatski puni iz tablice stranica i u njemu se zadržavaju do istisnuća novim adresama. Sadržaj tablice satranica: *Za stranicu koja je u okviru 31

Redni broj okvira = =bazna adresa okvira

12

11

65

0

1 Bit prisutnosti Bit pristupa

Bit pisanja Za stranicu koja nije prisutna u glavnom spremniku 31

0

0 bit prisutnosti 51

Očigledno je da straničenje usporava odvijanje programa. Procjena usporenja: Pretpostavimo da je: ts - vrijeme pristupa do radnog spremnika td - vrijeme dobavljanja stranice iz pomoćnog spremnika p - vjerojatnost promašaja Efektivno vrijeme pristupa je te=(1-p)*ts+p*td Primjer: Neka je ts=100ns=0,1 us td=10ms= 10000 us te=0,1+9999,9*p us -3 uz p=10 (jedan promašaj na tisuću dohvata) te=10.099us uz p=10-4 (jedan promašaj na deset tisuća dohvata) te=1.099us uz p=10-5 (jedan promašaj na sto tisuća dohvata) te=0.199us uz p=10-6 (jedan promašaj na miliondohvata) te=0.1099us 52

a26

Stranica u okviru

8.5.3 Straničenje na zahtjev (engl. demand paging) Stranice se dobavljaju u radni spremnik kada je to potrebno

Instrukcija

Adresiranje

1

TLB

6

0

pokretanje procesa ponavljanja instrukcije

tablica stranica

Prazni okvir

5

nadopuna tablica

2

prekid zbog promašaja

4 operacijski sustav

3

dohvat stranice

Prebacivanje stranice u prazni okvir Adresirana 53 stranica

Prilikom promašaja događa se slijedeće: Prekid zbog promašaja Spremiti kontekst procesa Blokirati proces Zatražiti punjenje tražene stranice Prebacivanje završeno Nadopuniti tablive Deblokirati proces Proglasiti proces pripravnim Pri ponovnom pokretanju procesa ponoviti istrukciju koja je izazvala prekid. U kontekstu treba sačuvati programsko brojilo vraćeno na adrese instrukcije kao i obnovljene sadržaje registara koji su se do pojave prekida već promijenili. 54

a27

8.5.4. Strategija zamjene stranica Ako pri zahtjevu za punjenje stranica nema praznog okvira treba odabrati stranicu koja će biti izbačena iz radnog spremnika. Kako? Mjera vrednovanja strategije može biti broj promašaja tijekom izvođenja programa FIFO strategija: Izbaciti stranicu koja je najdulje u radnom spremniku. FIFO strategiju je teško ostvariti a osim toga pati od Beladyjeve anomalije. S povećanjem broja raspoloživih okvira može porasti broj promašaja Neka se redom pristupa do stranica: 123412512345

55

Broj okvira 1 123412512345 2 3

4

5

113311552244 -22442211335

Broj promašaja 12 12

1114445--55-222111--33--33322--24-

9

1111--1----1222--2------33--332222 ---4--444333

10

1 1 1 1- - 1 - - - - -222--2 ------33--3-------4--4----------5-----

5 56

a28

Optimalna strategija (OPT) Izbaciti strranicu koja se najdalje u budućnosti ne će upotrebljavati. Nije prikladna za praktičnu upotrebu. Služi samo za usporedbu! Primjer: 3 okvira; koriste se redom sreanice 50120304230321201501 5552 -2- 2-- 2-- 2 - --5-- 000 0 4 0 0 0 - - 11 3 3 3 1 1

9 promašaja

Za usporedbu: FIFO: 5552 22444 0 -000 333222 -- 11 100033

00 11 22

555 100 221

15 promašaja

57

LRU strategija (Last recently used) Izbaciti onu stranicu koja u prošlosti nije najdulje upotrebljavana. (Zamisao: Možda stranica više nije ni potrebna!) Primjer: 50120304230321201501 5552 - 000 - - 11

2 4440 0 0033 3 3222

1 1 1 3 0 0 2 2 5

12 promašaja

Ostvarenje LRU strategije također nije jednostavno Jedna od mogućih aproksimacija:

Tablica stranjca Bitovi pristupa

Posmačni registri povijesti

58

a29

Uz tablicu stranica postoji: * bit pristupa *posmačni registri povijesti * Početno su svi bitovi pristupa i posmačni registri jednaki nuli. * Svaki puta kada se pristupa stranici postavlja se njezin bit pristupa * Prekid od sataperiodički (npr. Svakih 100 ms) pomiče bit pristupa u posmačne registre i briše ga. * Sadržaji posmačnih registara tretiraju se kao binarni brojevi i izbacuje se stranica (ili jedna od stranica) s najmanjim brojem. To rješenje degenerira tako da nema registatara povijesti. Stranice se dijele u dvije grupe * stranice u koje se u zadnjoj periodi vremena pristupalo * stranice u koje se nije pristupalo Korisno je ako se stranica koja se izbacuje nije promijenila. Nju ne treba prenositi u pomoćni spremnik, jer tamo postoji važeća kopija. Time se štedi jedan pristup na disk. 59 Za ostvarenje te zamisli uz bit pristupa uvodi se i bit pisanja (vidi I486).

Kada se u stranicu piše, bit pisanja se postavlja. Redoslijed odabira stranica za izbacivanje Redoslijed

Stranica

1

bit bit pristupa pisanja 0 0

2

0

1

nije * pisana upotrebljavana (“nečista”)

3

1

0

upotrebljavana “čista”

4

1

1

upotrebljavana

nije * nije pisana upotrebljavana (čista)

“nečista”

* nakon zadnjeg brisanja od sata 60

a30

8.5.5. Dodjela stranica u višezadaćnom sustavu. Pretpostavimo da korisnički prostor ima m okvira. U jednozadaćnom sustavu svi okviri dodjeljuju se jednom procesu. U višezadaćnom radu moguća su dva pristupa: Globalna podjela: Svi procesi dobivaju stranice iz zajedničkog prostora Lokalna podjela raspoloživi okviri dijele se unaprijed na procese. Globalna podjela je nezgodna jer se tešk može izbjeći (i nadzirati) međudjelovanje procesa. Pri lokalnoj podjeli može se: * podijeliti na n procesa jednoliko sve okvire tj o=int(m/n) okvira po procesu * podijeliti okvire srazmjerno veličini programa Pi - broj stranica procesa i P=Σpi Oi=int(Pi/P*m)

61

Eventualna dinamička preraspodjela okvira obavlja se kao posljedica promatranja ponašanja procesa Broj promašaja

Dodati jedan okvir

Suviše promašaja Područje “normalnog” promašaja

Oduzeti jedan okvir

“Premalo” promašaja Broj okvira

Ako svi procesi suviše promašuju, treba smanjiti stupanj višezadaćnosti te raspodjeliti okvire procesima koji ostaju. 62

a31

8.5.6. Model radnog skupa stranica Ako zbog nekog razloga neki proces treba zaustaviti I oduzeti mu okvire koje koristi, kod ponovnog pokretanja tog procesa stranice će se puniti promašivanjem Bilo bi razumno zapamtiti koje stranice su bile u radnom spremniku i napuniti ih sve u jednom zahvatu. Ne vraćaju se sve stranice već samo one koje su u jednom razdoblju tzv. Vremenskom prozoru, koristile. To je radni skup stranica. D - vremenski prozor W(tj,D) - radni skup stranica u trenutku tj s prozorom širine D (engl. Working set) Vrijeme t i širina prozora mjere se u nekom virtualnom mjerilu (diskretiziranom) 63

Primjer: Neka se u uzastopnim vremenskim intervalima pristupa u slijedeće stranice: 2 6 1 5 7 7 7 7 5 1 6 2 3 4 2 3 4 4 4 3 1 4 3 t1

D=2

D=2 W(t1,2)={1,5}

W(t2,2)={3,4}

D=4

D=4

W(t1,4)={1,5,7}

W(t2,4)={3,4}

D=10

D=10

W(t1,10)={1,2,5,6,7}

t2

W(t2,10)={2,3,4,6,} 64

a32

Veličina radnog skupa mijenja se tijekom odvijanja programa Uz dovoljno širok prozor, sve stranice Pi nekog procesa mogu se nalaziti u radnom skupu 1<=|w(t,D)|<=Pi Praćenjem rada nekog programa može se ustanoviti da u tipičnom slučaju postoje vremenska razdoblja kada je radni skup slabo promjenjiv, te razdoblja (tranzijetna) kada je veličina skupa jako promjenjiva. |W(t,D)|

t Stabilno

65

8.5.7. Utjecaj straničenja na odvijanje programa U načelu korisnik računala ne mora ništa znati o načinu dodjele prostora u spremniku Međutim nekada se mogu uočiti znatne promjene u trajanju programa pri neznatnim zahvatima u njegovu strukturu. Uobičajeni primjer je odsječak programa za inicijalizaciju matrice. Primjer: Pretpostavimo da treba inicijalizirati matricu A[1..512,1..512]s nulama. Za i:=1 do 512 činiti za j:=1 do 512 činiti A[i,j]:=0; Neka jedna stranica bude veličine 512 riječi. Ako se matrica smješta po recima, tada je u jednoj stranici smješten jedan stupac |A[i,1] | |A[i,2] |A[i,3] |A[i,4] …. |A[i,512] | jedna stranica 66

a33

Ako na raspolaganju imamo samo jedan okvir, izvođenje inicijalizacije će izazvati 512 promašaja. Mala modifikacija programa Za j:=1 do 512 činiti za i:=1 do 512 činiti A[i,j]:=0; izaziva 512 * 512 = 261 144 promašaja. Ako se za svaku zamjenu stranica utroši 20 ms, programi traju: a) 512 * 20 = 10240 ms = 10,24 s b) 261114* 20 = 5222880 ms = 5222.88 s=1 sat 27 min 2.88 s

67

a34