25: Minnisúthlutun

Question 1

Kvik minnisúthlutun

Answer 1

malloc og free

Question 2

Forritarar nota minnisúthlutara
(eins og malloc) til að ?

Answer 2

fá sýndarminni á keyrslutíma

Question 3

Minnisúthlutarar (dynamic
memory allocators) sjá um?

Answer 3

svæði í sýndarminni sem kallast kös (heap).

Question 4

Hvernig virkar Kvik minnisúthlutun?

Answer 4

Úthlutari skipuleggur kösina sem safn af misstórum
blokkum, sem eru annaðhvort úthlutaðar (allocated)
eða lausar (free)

Þegar kemur beiðni um nýja blogg þá finnur hann lausa blokk og lætur hana af hendi

Question 5

Tvær gerðir úthlutara:

Answer 5

Bein úthlutun og óbein úthlutun

Question 6

Hvað er Bein úthlutun: ?

Answer 6

notendaforrit úthlutar og losar minni
* Til dæmis: malloc og free í C

Question 7

Hvað er Óbein úthlutun?

Answer 7

notendaforrit úthlutar, en losar ekki
minni
* Til dæmis new og ruslasöfnun í Java

Question 8

malloc pakkinn

Answer 8

include <stdlib.h></stdlib.h>

void *malloc(size_t size)

skilar bendi á void, forritarinn skilar sjálfur bendi á þá tegund sem hann vill fá

Question 9

Þegar malloc heppnast

Answer 9

Þá fáum við bendi á minnisblokk með stærð a.m.k. size bæti uppröðuð
(aligned) að 16 bætum (á x86-64)

Question 10

Þegar malloc heppnast ekki

Answer 10

Skilar NULL (0) og setur errno sem ENOMEM

Question 11

void free(void *p)

Answer 11

Skilar blokkinni sem p bendir á, í safn lausra minnisblokka

lykilatriði : p verður að koma frá fyrra kalli á malloc eða realloc

Question 12

calloc:

Answer 12

útgáfa af malloc sem upphafsstillir blokkina sem 0

Question 13

realloc:

Answer 13

breytir stærð á áður-úthlutaðri minnisblokk

Question 14

sbrk:

Answer 14

innra fall í úthlutara, til að breyta stærðinni á kösinni

Question 15

Takmarkanir

Answer 15

Geta gert alls konar runur af malloc og free köllum, vitum ekki í hvaða röð þau koma

Getum ekki ráðið fjölda eða stærð úthlutaðra blokka

Verðum að svara malloc köllum strax og getum ekki umraðað beiðnum

Verður að úthluta blokkum úr lausa minninu

Úthlutaðar blokkir verða að uppfylla uppröðunarskilyrði

Getur aðeins unnið með og breytt lausa minninu

Getur ekki fært blokkir eftir að þeim hefur verið úthlutað

Question 16

Mælikvarði: Afköst (throughput)

Answer 16

Markmið: hámarka afköst og hámarka minnisnýtingu

Afköst: Fjöldi afgreiddra minnisbeiðna á tímaeiningu

Question 17

Mælikvarði: Minnisnýting

Answer 17

Gera greinar mun á farm (payload) og overhead

Question 18

Hvað er Sundrun (fragmentation)?

Answer 18

Sundrun veldur lélegri minnisnýtingu

– Innri sundrun (internal fragmentation)
– Ytri sundrun (external fragmentation)

Question 19

Innri sundrun (internal fragmentation)

Answer 19

á sér stað ef farmurinn er minni en stærð blokkarinnar

Question 20

Ytri sundrun (external fragmentation)

Answer 20

Eitthvað sem var ekki nýtt á milli blokka

Question 21

Að vita hverju er verið að skila, Venjulega aðferð:

Answer 21

Geyma lengd blokkarinnar í orðinu á undan blokkinni
* Þetta orð oft kallað haussvið eða haus (header)
– Krefst eins aukaorðs fyrir hverja úthlutaða blokk

Question 22

Hvaða aðferðir eru til þess að halda utanum lausar blokkir?

Answer 22

Aðferð 1: Óbeinn listi notar lengdirnar til þess að hoppa— tengir allar blokkir

Aðferð 2: Tengdur listi af lausu blokkunum með bendum

Aðferð 3: Aðskildir listar

Aðferð 4: Blokkir raðaðar eftir stærð

Question 23

Óbeinn (implicit) listi

Answer 23

Fyrir hverja blokk þarf bæði stærð og úthlutunarstöðu

Question 24

Óbeinn listi, hvernig er hægt að finna lausa blokk

Answer 24

First-fit:
Next-fit:
Best fit:
Worst-fit:

Question 25

First-fit:

Answer 25

– Byrja fremst í listanum, velja fyrstu lausu blokkina sem passar:
– Tekur línulegan tíma í fjölda blokka (úthlutaðra og lausra)
– Í reynd verður fremsti hluti listans dálítið brotakenndur (splintered)

Question 26

Next-fit:

Answer 26

– Eins og First-fit, nema við byrjum þar sem síðasta leit endaði
– Ætti að vera hraðvirkari en First-fit: skoðum ekki aftur sömu blokkirnar
– Virðist þó valda verra uppbroti á blokkunum

Question 27

Best fit:

Answer 27

– Byrja fremst, velja bestu lausu blokkina: með fæstu aukabætunum
– Afgangsbrotin verða lítil — fáum oftast betri minnisnýtingu
– Oftast hægvirkari en First-fit

Question 28

Úthlutun á lausri blokk: Hvað er skipting (splitting)?

Answer 28

Ef úthlutað pláss er minna en lausa blokkin þá getum við
skipt henni upp

Question 29

Óbeinn listi: Losun blokkar

Answer 29

Þurfum bara að hreinsa “úthlutað” bitann

En getur valdið “gervi sundrun” (false fragmentation)

Það er til nóg af samfelldu
lausu plássi, en úthlutarinn
mun ekki finna það

Þurfum að Sameina (coalesce) við næstu blokkir ef þær lausar

Question 30

Óbeinn listi: Tvíátta sameining

Answer 30

Jaðarmerki (boundary tags) [Knuth73]

– Endurtaka stærðina í hinum enda blokkanna
– Leyfir okkur að ferðast um listann í hina áttina líka, en þarf aukapláss
– Mikilvæg og almenn aðferð!

Question 31

Gallar við jaðarmerki

Answer 31

Innri sundrun
– Notar meira aukaminni
– Ekki hagkvæmt er mikið af litlum blokkum

Question 32

Hvaða blokkir þurfa að hafa jaðarmerki?

Answer 32

Þurfum aðeins jaðarmerki fyrir lausar blokkir

Question 33

Yfirlit yfir helstu úthlutunaraðferðir

Answer 33

Staðsetningaraðferð (placement)
Skiptingaraðferð (splitting)
Sameiningaraðferð (coalescing)

Question 34

Staðsetningaraðferð (placement):

Answer 34

– First-fit, Next-fit, Best-fit, o.fl.

– Skiptum á lægri afköstum fyrir minni sundrun (fragmentation)

Question 35

• Skiptingaraðferð (splitting):

Answer 35

– Hvernig skiptum við upp lausum blokkum?

– Hve mikla innri sundrun sættum við okkur við?

Question 36

Sameiningaraðferð (coalescing):

Answer 36

– Tafarlaus sameining: sameina um leið og kallað er á free

– Tafin sameining: reyna að auka hraða á free með því að
bíða með sameiningu þar til hennar er þörf. Dæmi:
–Sameina um leið og listinn skannaður fyrir malloc
– Sameina þegar magn ytri sundrunar nær einhverju lágmarki (threshold)