IT222 - Øving 3

IT222 - Øving 3

[Rettet med kommentarer]

I - Hva er minne, og hvilke oppgaver har minneadministrasjonen?

Minne er maskinens primærlager - lagringsplassen prosessoren har direkte tilgang til. Prosessoren bruker minnet til å hente instruksjoner og data.

Minneadministrasjonens hovedoppgaver

Oversikt
Å holde oversikt over hvilke minneområder som brukes og hvilke som er ledige.
Tildeling
Bestemme hvem som skal få plass i minne, hvor mye hver prosess skal få, og hvor den skal få plass. I multiprogrammerings-miljøer vil flere prosesser konkurrere om minne samtidig, og man må derfor ha en policy for hvilke prioriteringer som skal benyttes.
Tilordningsteknikk
Når minneområder tilordnes må operativsystemet minneadministrasjonstabeller oppdateres.
Frigjøring
Hvordan skal minne frigjøres - policy for hva som skjer om vi trenger minnet en prosess bruker. Skal vi ta bort minne fra prosesser ved tvang, evt. midlertidig, eller skal vi kun ta minne prosessen frivillig gir fra seg?

II - Administrering av minnet

Den enkleste måten å organisere minnet under multiprogrammering er ved å dele minnet i to, en del som er reservert for operativsystemet (kjerne) og en for brukerprogram, og bare ha en prosess i minnet om gangen. Ved å veksle brukerområdet av minnet på platelager kan man bytte mellom kjørende prosesser. Et register definerer skillet mellom operativsystemet og brukerområdet, og alle minnereferanser blir sjekket mot dette for å unngå systemfeil.

Fordelen med en slik organisering er at man kan ha en veldig enkel minneorganisering uten spesielle maskinvarekrav, og samtidig ha en primitiv form for multiprogrammering. Ulempen er at det er lite effektivt å lagerveksle for hver eneste prosess som skal kjøre.

Ved å innføre flere prosesser i minnet kan man effektivisere multiprogrammeringen. Dersom det ikke er nok plass i primærlageret til å hente inn prosessen som skal kjøre, må andre prosesser veksles ut på platelager inntil det er nok plass. Det kan være forskjellige algoritmer for utskiftingen, det kan f.eks. være den prosessen som tar størst plass i minnet som blir vekslet ut, eller det kan bli den som har lavest prioritet.

For å få til en slik utveksling må minnet partisjoneres, enten med faste inndelinger eller variable inndelinger. En måte å gjøre det på er å ha minnet inndelt i faste partisjonsstørrelser, og prosessen vil bli lagt i kø for den partisjonen som passer best med hensyn på prosessens minnebehov. En annen variant er å ha alle prosessene i samme kø og fordele på partisjonene.

Ved å partisjonere minnet har man flere prosesser i minnet samtidig, og man slipper å veksle like ofte, slik at multiprogrammeringen blir mer effektiv. Hvert brukerprogram har bare en øvre og nedre grense i adresseområdet å forholde seg til. Man må sette opp partisjonene før man starter jobbene, og låser seg derfor til de inndelingene man velger. Dette gjør at man sløser minneplass ved fragmentering, men gir samtidig en enkel administrasjon. Det er fortsatt ueffektivt at hele prosessen blir vekslet om gangen, det kan være at deler av minnet sjelden brukes og kunne vært på ytre lager til det ble nødvendig.

Ved å innføre variable partisjonsstørrelser lar man partisjonsstørrelsen bli tilpasset hver enkelt prosess. (skreddersydd). Dermed kan plassen som ble brukt av 1 stor prosess veksles mot 2 mindre prosesser uten problemer.

Derimot får man problemet at minnet blir fragmentert slik at det kan være litt ledig plass MELLOM hver partisjon, og en prosess kan kanskje ikke lastes inn i minnet selv om det totalt sett er nok ledig plass. Man har altså samme problem som tidligere, men her er det løsbart. Ved å enten jevnlig eller ved behov flytte sammen partisjonene og samle den ledige plassen (kompaktering) unngår man fragmenteringen, og får plass til den nye prosessen.

For at en partisjon i minnet skal kunne flyttes må den være relokerbar, slik at minnereferanser vil forbli riktige. Hver prosess har relative minnereferanser, og ved utførelse blir minnereferanser lagt til startadressen for partisjonen i det fysiske minnet for å finne den faktiske adressen. Når en partisjon flyttes endrer man ganske enkelt bare startadressen. For at dette skal fungere bør man ha støtte for relative adresserom i maskinvaren.

Med variable partisjonsstørrelser vil operativsystemet kunne bruke en del tid på administrative ting ved å rydde i minnet. På den andre siden får man en mye mer effektiv utnyttelse av minnet, fordi man ikke er bundet av partisjonsstørrelser.

Ved å dele inn prosessens minneområde inn i sider kan man ha programkoden og dataene spredt over flere steder i minnet. Dette skjer ved at man deler programområde og dataområde opp i sider etter en gitt sidestørrelse. Det fysiske minnet er delt opp i siderammer som hver har plass til en enkeltside. For å holde styr på hvor i minnet de enkelte sider er plassert benytter man seg av en såkalt sidetabell.

Man unngår fragmentering mellom partisjonene i minnet, men får fragmentering internt fordi koden og dataene sjelden passer på et helt antall sider. Man kan derimot, i motsetning til ved faste partisjonsstørrelser, ha mindre sider enn programmets fulle størrelse. Man mister ikke tid til å rydde i minnet, men må holde oversikt over sidene i stedet.

Ved å ta ibruk veksling og virtuelt adresserom kan man ha prosesser som totalt bruker mer minne enn tilgjengelig fysisk minne. Ved behov blir sider lest inn i minnet, og kan veksles ut igjen når de ikke er i bruk. Maskinvaren blir mer komplisert for å få til virtuelle adresserom, man må ha en egen minneadministrasjonsenhet (MMU).

En annen måte å administrere minnet på er å dele et program opp i segmenter basert på den logiske strukturen i programmet. F. eks. kan en enkelt prosedyre være i et eget segment. En får samme fordelen som nevnt før med virtuelt minne, fordi en bare behøver å ha de segmentene en har bruk for der og da i minnet. Å dele inn minnet etter oppbygningen av programmet kan bli mer effektivt enn ved sideinndeling, fordi det er enklere å skille ut de delene som sjelden brukes, eller å samle de delene som brukes samtidig. Ren sideinndeling gjør det vanskelig for programmeren å fortelle operativsystemet hva som logisk sett hører sammen i programkoden og dataene, noe han kan med segmentering.

Segmentering gjør at dynamisk lenking blir lett gjennomførbart. Programkode kan samles i et segment som lastes ved behov, og som også kan deles mellom flere prosesser. Man kan også sette forskjellig tilgang på segmentene, slik at fx. programkoden ikke er skrivbar, og dataområdet ikke kjørbart.

Segmentene varierer i størrelse, som gir mindre fragmentering, men øker administrasjonstiden til kompaktering. Ved å skille på dataområder og programkode kan man effektivisere vekslingen. Fordi programkode som er satt som ikke skrivbar ikke endrer seg slipper man å legge den på det ytre lageret på nytt, man har bare latt det ligge der også mens det var i minnet, og frigjører plassen i minnet direkte.

Ved å dele prosessen inn i mange segmenter kan man risikere at operativsystemet bruker det meste av sin tid på å veksle mellom de forskjellige segmentene inn og ut av det ytre lageret (trashing). For å minske dette kan man innføre sideinndeling på segmentene, slik at bare deler av segmentene behøver å være i minnet samtidig. Dette gir veldig mange kostnader administrativt sett, det blir mange store tabeller å holde styr på og slå opp i for hver eneste minnereferanse.

III - Minne

a) Trashing (tresking) og trimming av arbeidssett

Trashing opppstår når graden av multiprogrammering (antall prosesser, og minnebruken til disse) øker til et slikt nivå at ingen prosesser greier å opprettholde et arbeidssett. Systemet vil i et slikt tilfelle bruke alle cpu-tid på sideveksling, og ingen prosesser vil få gjort noe som helst arbeid.

Tresking kan unngås ved at operativsystemet til en hver tid sørger for at antallet aktive prosesser er stort nok til at multiprogrammeringsgraden er så høy som mulig, samtidig som den er lav nok til at tresking ikke oppstår.

Dette kan gjøres ved å overvåke prosessenes arbeidssett, og sørge for at nye prosesser aktiveres hvis det er ledige siderammer, mens prosesser suspenderes eller arbeidssettene trimmes til så liten størrelse som mulig hvis det er for få ledige siderammer. I tillegg til å unngå tresking må en sørge for å opprettholde en høyest mulig multiprogrammeringsfaktor, slik at CPU-utnyttelsen blir så høy som mulig.

Trimming av arbeidssett kan administreres ved at man setter en øvre og en nedre grense for "rimelige" sidefrekvens-krav (hyppighet for sidekrav i en gitt tidsperiode). Overstiger sidekravene øvre grense tildeles en side, ligger de under nedre grense reduseres antall sider.

b) Hvordan holde styr på bruken av minne

Minne deles opp og avsettes i blokker. En blokk inneholder informasjon om hvorvidt den er ledig, om lengde, og eventuelt pekere til andre blokker (neste/forrige ledige).

Tildelt minneplass registreres i PCBer for hvert program. PCBen innholder pekere til programmets avsatte minne, det kan (er i mange tilfeller) være delt opp i kodeområde, dataområde, og stakk.

Ledig minneplass registreres i en ledig-liste eller et bitkart. Disse registrerer hvilke blokker som er ledige på forskjellige måter.

c) Hensikten med sidetabeller

Sidetabellen brukes for å oversette mellom virtuelle minneadresser (adresser i det virtuelle minneområdet programmene bruker) og de fysiske adressene operativsystemet må adressere i hardware.

d) Viktige momenter ved implementering av minnebehandlingen i et OS

IV - Utskiftingsalgoritmer

Minneadministrasjonen kan velge ut sider til veksling på forskjellige måter.

FIFO

I en First In, First Out-algoritme vil den til enhver tid eldste siden bli lagt på sekundærlageret når det er behov for veksling. Det vil si at sidene står i en kø for utskifting. Algoritmen er veldig enkel og ikke særlig tidkrevende, men lar ikke segmenter "snike i køen" fordi de brukes oftere enn andre. (ingen Braathens Best)

En måte å unngå dette på er å utvide algoritmen ved å gi segmentet en ny mulighet. Dersom siden som vurderes til utskifting nylig har blitt brukt (den har referansebiten slått på), legges den sist i køen for utskifting i stedet, og referansebiten blir slått av. Den eldste siden som ikke har vært brukt blir skiftet ut, hvis ikke vil utskiftingen skje som for en vanlig FIFO-algoritme.

LRU

Ved å bytte ut segmentene basert på hvor ofte de ble brukt istedet for hvor ofte de har blitt vekslet får man en utveksling som prioriterer populære segmenter og gir bedre programflyt. En slik algoritme kalles LRU (Least recently used)

Rekkefølgen for utskrifting blir slik at segmentet det er lengst siden ble brukt skiftes ut sist, mens i andre enden ligger segmentet som nettopp ble brukt.

V - Multiprogrammering

a) Multiprogrammering

Multiprogrammering vil si å ha flere prosesser i minnet samtidig, istf. å ha bare en, for å utnytte minnet, io og andre trege resursser bedre. Dermed slipper man å laste inn en prosess i minnet, kjøre den, legge den tilbake på disk (om nødvendig), laste en ny, kjøre den etc..

Siden prosessoren er mye raskere enn alt annet, prøver man å begrense tiden den venter på ting så mye som mulig. For eksempel ved å putte så mye som mulig i minnet siden diskaksess går så treigt, og justere i hvilken rekkefølge ting kjører slik at alt er i mer jevnt bruk.

b) Fragmentering

Fragmentering reduserer ledig minne og er enten intern eller ekstern Ekstern fragmentering oppstår når prosesser og data fjernes fra minnet; minneområdet hvor det fjernede lå blir frigjort, men de nå tomme bitene kan være vanskelig å ta i bruk til nye ting, da et sammenhengende område kan være for lite til at noe nytt kan lastes inn. Intern fragmentering oppstår når det er plass til overs i ei minneblokk etter at den har blitt fylt, når denne er av fast størrelse og det var mindre innlasta enn det var plass.

Man kan redusere fragmentering ved å pakke (kompaktere) minnet, dvs. sortere innholdet og flytte sammen sammenhørende ting til sammenhengende minneområder slik at det blir større sammenhengende tomme områder også. Hvis man ligner minnet til et cd-stativ, vil prosesser og data i minnet være cdene i stativet. Hvis de ti nederste plassene for øyeblikket er reservert "svensktoppar", etterfulgt av fem plasser muzak og tre plasser juleviser, med to ledige plasser øverst, og man vil gi bort all muzaken til den bråkete naboen ved siden av og i stedet sette inn seks cder med D.D.E, så ligger "juleviseblokka" i veien da det bare blir fem ledige plasser mellom denne og svenskemusikken. Dermed må f.eks juleviseblokka (den minste) flyttes så det blir minst seks sammenhengende ledige plasser. En annen måte å defragmentere på er ved 'lagerveksling' (swapping). Ved swapping flyttes avbrutte prosesser ut av minnet, og inn igjen når det er dens tur igjen, da kan man sette prosessen inn på et bedre egnet sted.

c) Sider vs. segment

Begge er måter å dele opp minnet i mer håndterlige biter på, men: sideinndelt minne har kun ett adresserom, segmentert har mange, ett per segment. Hvis sideinndelt minne ikke er behovsstyrt kan det ikke være større enn fysisk minne, med segmenter er det enkelt å skille prosedyrer og data og beskytte det separat, prosedyrer kan enklere deles og tabeller lettere tilpasses, men: programmereren/kompilatoren må være klar over at programmet skal kjøre i et segmentert miljø. En side har en fast størrelse, segmenter kan variere i størrelse. Ved reint segmentert minne er fragmentering et problem slik at man må pakke eller swappe, ved sideinndelt minne kan intern fragmentering være et problem.

d) Rein kode

Rein kode (pure code/commands) er kode som ikke endrer seg, dvs. den tar ikke vare på tilstandsdata og kan brukes av mer enn en prosess samtidig. Konstanter, sia de ikke endrer seg, kan brukes i rein kode.

Rein kode er kjekt å ha på systemer med lite minne; ofte brukte kodesnutter som er reine behøver bare lagres en gang, og man kan gjerne anse rein kode som en form for caching.

VI - Relokering

Oversettelse av virtuell (logisk) adresse til fysisk (faktisk) adresse.

a) Fordel ved to relokeringsregistre

Man kan sjekke om en adresse peker på et lovlig område i minnet på en enkel måte før man gjør noe med adressen, som å hente det den peker på. Dermed beskytter man områdene som ikke er i bruk fra å endres/leses av den aktive prosessen.

b) To relokeringsregister og adresseberegning

I det ene, base, legges adressen til starten på minneområdet, i det andre, limit legges lengden. Når man skal hente fra/skrive til minnet, sjekker man først om adressen er mindre enn limit, hvis så er den innenfor grensene og innholdet av baseregisteret legges til slik at man får fysisk adresse, og man kan sende avgårde kallet.