Minne

Question 1

Hva handler memory managment om?

Answer 1

Håndtere systemets minne ressurser, som inkluderer:

• Allokere plass til prosesser.
• Beskytte minne regioner.
• Gi en virtuelt visning av minnet, slik at det fremstår som om systemet har mer minne en de faktiske tilgjenglige bytene.
• Kontrollere forskjellige nivåer av minnet i et hierarki.

Question 2

Hvordan ser et typisk minne hierarki ut?

Answer 2

tertiary storage (tape)
    |
sekundærminnet (disk)
    |
hovedminnet (ram)
    |
Cache(s)

De lavere nivåene har kopier av data fra høyere nivå.

Question 3

Hva er ‘absolute addressing’?

Answer 3

Lesing av data ved referanse til den ‘absolutte’ byte nummeret i minnet.
- read absolute byte 0x000000ff

Brukes ofte av hardware, og er raskt.

Question 4

Hva er ‘relative addressing’?

Answer 4

Lesing av data ved referanse til relative byte nummer i minnet, som er uavhengi av prosessens lokasjon i minnet, relativ til en base lokasjon som typisk vil bli gitt prosessen.

Trenger en dynamisk address translation, får å finne absolute addresser under kjøretid ved å legge til relative og base addressene.

Question 5

Hvordan ser en prosess sitt minne layout ut?

Answer 5

• System data segment (PCB)
• Text (code) segment
• Data segment
• Stack Segment

Question 6

Hva inneholder en prosess sitt system data segment (PCB)?

Answer 6

Blandt annet segment pekere, pid, program og stack pekere.

Question 7

Hva inneholder en prosess sitt text/code segment?

Answer 7

Code segment er et text segment, som er lest fra program filen (for eksempel av exec).

Er vanligvis read-only, og kan være delt.

Question 8

Hva inneholder en prosess sitt data segment?

Answer 8

Inneholder globale og statiske variabler som har en predefinert verdi og kan bli modifisert.

Initialiserte globale/statiske variabler (data)
Unitialiserte globale/statisk variabler (BSS)

Heap
- Dynamisk minne (vokser mot høyere adresser, mot stacken)

Question 9

Hva inneholder en prosess sitt stack segment?

Answer 9

Lagrer parametere/variabler i funksjoner.
Lagrer register tilstander (f.eks. kall på funksjons EIP)
Vokser mot lavere addresser (mot heapen).

Question 10

Hva er swapping ifht. minne administrering?

Answer 10

Fjerne en prosess fra minnet med all dens tilstand og data - og lagre det på et sekundær medium (disk, flash RAM, tape).

Question 11

Hva er overlays ifht. minne administrering?

Answer 11

Det å manuelt bytte ut deler av kode/data. Blir utført av programmerern, og brukes kun for gamle og memory-scarce systemer.

Question 12

Hva er segmentation/paging ifht. minne administrering?

Answer 12

Fjerne deler av en prosess fra minnet og lagre det på et sekundær medium - størrelsen på delene som blir byttet er gjerne en fast størrelse.

Question 13

Hva er fixed partitioning ifht. minne administrering?

Answer 13

Ved fixed partitioning så deles minne inn i statiske partisjoner ved initialisering av systemet (boot eller tidligere).

Question 14

Hva er fordeler/ulemper med fixed partisjoner med equal-size?

Answer 14

En ulempe er et store programmer ikke kan bli eksekvert (at de ikke får plass i den fast satte partisjon størrelsen).

Små programmer bruker ikke hele partisjonen, og vi får intern fragmentering.

Question 15

Hva er fordeler/ulemper med fixed partisjoner med uequal-size?

Answer 15

Store programmer kan bli lastet med en gang.

Mindre intern fragmentering.

Krever håndtering av hvilken prosess som passer til hvilken partisjon.

Question 16

Hva er dynamisk partitioning ifht. minne administrering?

Answer 16

Ved dynamisk partisjonering så blir minnet oppdelt ved kjøretid.

Partisjonene blir opprettet dynamisk og fjernet etter prosesser er ferdig.

Gir økt ekstern fragmentering under kjøring.

Question 17

Hva er compaction ifht. dynamisk partisjonering?

Answer 17

Campaction er å fjerne ekstern fragmentering ved å flytte på data i minnet.

Question 18

Hvilken algoritmer har vi for compaction?

Answer 18

First fit (enklest, raskest og typisk det beste valget).

Next fit (nesten som first fit).

Best fit (tregest, mye små fragmenter, og derfor ofte værst).

Question 19

Hva er ‘The Buddy System’ ifht. partisjonering?

Answer 19

En miks av fixed og dynamisk partisjonering. Hver partisjon har en størrelse 2^k

Holder en liste av hull i minne layoutet og deres størrelse.

Kalkulerer det minste hull-størrelsen 2^k en prosess vil passe inn i, finner så et hull av den størrelsen.
- Om det ikke er tilgjenglig, del det minste hullet som er større enn 2^k rekursivt i halvdeler.

Question 20

Hva er segmentering ifht. partisjonering?

Answer 20

Samme prinsipp som i dynamisk partisjonering, programmene kan ha forskjellige størrelser.

Deler programmet opp i memory frames av forskjellige størrelser, bestemt av programmeren eller OS’et.

Programmet kan dermed ligge i minnet på forskjellige plasser, istedenfor å måtte ligge som et stort segment.

Gir ingen intern fragmentering, men noe ekstern fragmentering (siden programmet kan ha segmenter av forskjellige størrelser)

Question 21

Hva er paging?

Answer 21

Paging er samme prinsippet som segmentering, men programmet blir delt opp i segmenter av faste/like størrelser definert av maskinen.

Gir ingen ekstern fragmentering, men noe intern fragmentering avhengig av frame size.

Question 22

Hvordan fungerer virtuelt minne?

Answer 22

Minnet er delt opp i frames av like størrelser, kalt page frames.

Programmet blir delt inn i frames av like størrelser, ofte kalt pages.

Noen pages vil ligge i det fysiske minnet, mens andre blir liggende på disk og bli hentet ved behov.

Maskinen vil ha et virtuelt adresserom som er større enn det fysiske minnet.

Virtuelle adresser blir oversatt til fysiske adresser ved å bruke en page table.

Question 23

Hva er oppgaven til MMU ifht. page table?

Answer 23

Sørge for at pagen vi ønsker å aksessere er tilgjenglig i primærminnet, og om den ikke er det, så swapper den pagen fra disk med en page i primærminnet (avgjort av algoritmen brukt) slik at den blir tilgjenglig.

Question 24

Vi har 4KB pages, plass til 8 pages i fysiske minnet, og et 16bit virtuelt adresserom.

Hvordan oversettes det virtuelle til det fysiske?

Answer 24

Pagen er 4KB, så det trengs 12bit for å kunne lagre hele pagen - dette blir offsetet.

Det er da 16-12 = 4 bits til indeksering, som gir oss 4^2 = 16 virtuelle pages.

Indekseringen brukes inn i en page tabell som inneholder de 3 første bitene til den fysiske adressen og en present bit.

Gitt at pagen er present i minnet:
- Spleises de tre bitene fra page tabellen med offsetet til den virtuelle adressen for å gi den nøyaktige adressen til data elementet i den gitte pagen som ble forrespurt.

Question 25

Hvordan håndteres en page fault?

Answer 25

1. Context switch til OS rutine, tilstanden til prosessen som trigget PF blir lagret.
2. OS’et ser det er page fault, prøver å finne adressen til forespurte virtuelle page.
3. OS’et sjekker at rettigheter stemmer for tilgang.
4. OS’et velger en page i fysiske minnet å swappe ut.
5. Hvis valgt page er “dirty”, skriv dens endringer tilbake til disk.
6. OS’et scheduler disk operasjon for å bringe pagen inn i primærminnet når page framen er klar.
7. Disk interrupt når I/O for pagen er ferdig, page tabell blir oppdatert (present bit) og page frame markert som “normal state”.
8. Context switch/swapp tilbake til prosessen som ga page fault, som vil kjøre oppslag av pagen igjen.

Question 26

Hvilken algoritmer har vi for page replacement?

Answer 26

First In First Out (FIFO)
Second Chance
Clock (Second Chance)
Least Recently Used (LRU)
Least/Most Relevant for Presentation (L/MRP)
Interval Caching (IC)

Question 27

Hva er ulempen med FIFO for page replacement?

Answer 27

Det gir en ikke-optimal replacment, selvom en gitt page blir brukt oftere, så kan den bli kastet ut ved enden av køen og må swappes inn igjen ved neste bruk.

Question 28

Hva er ideen til Second Chance algoritmen for page replacement?

Answer 28

En modifisert FIFO, tilfører en referanse bit.

Når en page blir referert igjen så blir R bitten sat, og pagen vil bli behandlet som en nylig lastet page.
- Så om en page med R bit ligger sist i kø for å bli kastet ut, så vil den pagen flyttes til starten av køen (og R biten blir resat).

Question 29

Hvordan kan Second Chance algoritmen for page replacement optimiseres?

Answer 29

Ved å bruke en sirkulær liste istedenfor en vanlig liste.

Vi har altså en liste i en sirkulær form, og vi flytter bare pekeren rundt (istedenfor å flytte siste element til starten om R bit er satt)

Question 30

Hva er prinsippet til LRU algoritmen for page replacement?

Answer 30

Prinsippet er at det alltid er den pagen som er lengst tid siden ble referert som blir replaced.

Sparer (vanligvis) mye disk aksess.
Er kostbar algoritme ifht. å vedlikeholde en ordnet liste, men disk aksess spart er en fordel.

Question 31

Hva er ideen til L/MRP page replacment algoritmen?

Answer 31

L/MRP er en buffer mekanisme for en enkelt interaktiv, continuouse data strøm.

Ideen er at den prelaster units som er mest relevant for presentasjon fra disken.
Og replacer units som er minst relevant for presentasjon.

Question 32

Hva er ideen til Interval Caching (IC) page replacment algoritmen?

Answer 32

IC er en caching strategi for streaming servere.

Ideen er at den cacher data mellom requests for samme video strøm basert på avstanden mellom strømmen av data mellom de to requestene.

Question 33

Hvor mange entries har en page tabell for en 32-bit maskin med 4kB pages?
Hvorfor er det relevant?

Answer 33

1M entries, 32bit - 12bit for page offset = 20bits, 2^20 = 1M.

Hvert page tabel vil da være ca 4 bytes, og 4MB totalt.

Hvert program trenger dens egen page tabel, og om vi har 100 programmer så trenger vi 400MB til bare page tables - og disse kan ikke swappes ut til disk.

Oppslag i en page tabell med 1M entries vil også begynne å ta betydelig tid.

Question 34

Hva er ideen til multi-level paging?

Answer 34

Ideen er å ha en 1-nivå page tabel som alltid ligger i minnet, og denne har pekere til andre page tabels - og disse kan swappes inn og ut fra disk (og dermed spare dyrbart primæminne).

Eksempel:
Vi har en 32bit virtuell addresse, og 4kB pages.
31—–22-21—–12-11—–0
- Da er 4kB = 12bit offset
- Da er bit 31-22 indeksen inn i 1-nivå page tabellen.
- På indeksen i første page tabellen, så er det en peker til 2-nivå page tabellen.

• Og bit 21-12 er indeksen inn i 2-nivå page tabellen.
• På indeksen i andre page tabellen er de første bitene til den fysiske adressen til pagen, som spleises med offsettet for å gi den eksakte adressen til elementet i pagen vi ønsker å hente.