26: Ruslasöfnun og minnisvillur

Question 1

Hvað er ruslasöfnun:

Answer 1

sjálfvirk skil á minni sem úthlutað hefur
verið í kösinni - notendaforrit þurfa ekki sjálf að skila því

Question 2

Hvar er ruslasöfnun algeng?

Answer 2

Algengt í mörgum kvikum (dynamic) forritunarmálum:
– Python, Ruby, Java, Perl, ML, Lisp, Mathematica

Question 3

Útgáfur (“íhaldsamir” ruslasafnarar) til fyrir C og C++, afhverju?

Answer 3

Til að henda ekki óvart einhverju mikilvægu

Question 4

Hvernig veit minnisstýringin hvenær hægt er að skila minni?

Answer 4

Almennt getum við ekki vitað hvað mun verða notað í
framtíðinni

En við getum sagt að sumar blokkir munu ekki verða notaðar,
ef það eru engir bendar á þær lengur

Question 5

Gefum okkur ákveðnar forsendur um benda

Answer 5

– Minnisstjóri getur greint á milli benda og ekki-benda
– Allir bendar benda á upphaf blokkar
– Ekki hægt að fela benda
(t.d., með því að kasta þeim í int, og síðan aftur til baka)

Question 6

Helstu ruslasöfnunarreikniritin

Answer 6

Mark-and-sweep
Tilvísanatalning
Afritunarsöfnun
Kynslóðasafnarar

Question 7

Mark-and-sweep söfnun (McCarthy, 1960)

Answer 7

Færir ekki blokkir (nema ef þjappað um leið)

Question 8

Tilvísanatalning (Collins, 1960)

Answer 8

Færir ekki blokkir (tölum ekki um hér)

Question 9

Afritunarsöfnun (Minsky, 1963)

Answer 9

Færir blokkir (tölum ekki um hér)

Question 10

Kynslóðasafnarar (Lieberman og Hewitt, 1983)

Answer 10

Söfnun byggð á líftíma
- Flestar úthlutanir verða rusl mjög fljótlega
- Einbeitir sér því að minnissvæðum sem nýlega búið að úthlut

Question 11

Við lítum á minnið eins og stefnunet (directed graph)

Answer 11

Hver blokk er hnútur í netinu

Hver bendir er leggur í netinu

Hólf utan kasarinnar sem innihalda benda inn í kösina kallast
rótarhnútar (t.d. gistu, hólf á hlaða, víðværar breytur)

Question 12

Hnútur (blokk) er aðgengilegur ef

Answer 12

það er vegur til hans frá einhverri rót

Question 13

Óaðgengilegir hnútar eru ?

Answer 13

rusl (notendaforrit getur ekki þurft á þeim að halda)

Question 14

Mark-and-Sweep söfnun

Answer 14

Hægt að byggja ofan á malloc/free pakka
– Úthlutum með malloc þangað til “minnið klárast”
* Þegar minnið hefur klárast:
– Notar auka mark-bita í haus hverrar blokkar
– Mark: Byrja í rótunum og setja mark-bitann í aðgengilegum blokkum
– Sweep: Fara í gegnum allar blokkir og skila ómerktum blokkum

Question 15

Mark notar ______ til að fara í gegnum minnisnetið

Answer 15

djúpleit

Question 16

Sweep notar ______ til að finna næstu blokk

Answer 16

lengdirnar