Számítógépes dokumentáció 1
A hősnek szokása volt, hogy cigarettacsikkeket bőrtáskába helyezett, és új cigarettákat készített. Így az átlagéletek elkerülhetetlen törvényének diktátumai szerint évek óta füstölte a dohány egy részét.
T. Pratchett
A memória dinamikus elosztásával a feladat végrehajtása során memóriaelosztásra vonatkozó kérelmek keletkeznek. A dinamikus elosztás ezért ellentétes a statikus értékkel. amikor a kérések a program összeállításakor keletkeznek. Végül mindkét és más kérést gyakran az ugyanazon memóriaelosztási algoritmus dolgozza fel az operációs rendszermagban. Ám sok esetben a statikus felosztás sokkal egyszerűbben megvalósítható, mint a dinamikus kiosztás. A fő nehézség itt az, hogy ha a statikus kiosztás természetellenesnek és ezért ritkán szükségesnek tűnik, az a képesség, hogy lemondjon a korábban kiosztott memóriáról. Dinamikus elosztással gyakran meg kell adni a kért blokkok eldobásának képességét, hogy a szabad memóriát felhasználhassa a későbbi kérelmek kielégítésére. Így egy dinamikus lekötő helyett egy egyszerű határvonal a foglalt és a szabad memória között (amely egyszerű esetben statikus eloszlás esetén elegendő) kénytelen tárolni egy esetleg leválasztott szabad memória területek listáját, amelyet medence vagy gyűjteménynek neveznek.
A memória kéréseinek és hibáinak számos szekvenciája az összes rendelkezésre álló memóriát kis blokkokká alakíthatja, és a nagy blokk lefoglalására irányuló kísérlet sikertelen lesz akkor is, ha a rendelkezésre álló kisblokkok hossza összege sokkal nagyobb, mint a szükséges. Ezt a jelenséget memória fragmentációnak nevezik (4.3. Ábra). Néha pontosabb kifejezést alkalmaznak - a külső fragmentáció (a belső fragmentáció később kerül megvitatásra). Emellett sok blokk hosszú keresést igényel. Különböző kis kis nehézségek is vannak. Szerencsére az emberiség sokáig foglalkozott a memóriaelosztás problémájával, és számos jó vagy elfogadható megoldást találtak.
A megoldandó probléma függvényében különböző stratégiákat alkalmaznak a szabad memóriablokkok megtalálásához. Például egy program azonos méretű vagy több rögzített méretű blokkokat oszthat meg. Ez nagymértékben megkönnyíti a töredezettségmentesítési feladatok megoldását és a szabad RAM elemek keresését.
Vannak olyan helyzetek, amikor a blokkok felszabadulnak az azzal ellentétes sorrendben, amelyikben kiosztottak. Ez lehetővé teszi, hogy csökkentse a memória felosztását a veremszerkezetre, vagyis ténylegesen vissza kell térnie a foglalt és a szabad memória közötti határ egyszerű megjegyzéséhez.
Vannak olyan helyzetek is, amikor a foglalt blokkok egy része elmozdítható a memóriából - lehetőség van a memória töredezettségmentesítésére. Elfoglalt memóriakártyák mozgatása a szabad területek egyesítéséhez. Például a UNAL rendszer korábbi implementációiban realloc () függvény használható erre a célra.
Ábra. 4.3. Külső fragmentáció
A magas szintű nyelvek standard könyvtári funkcióiban, például
.. Malloc / szabad / realloc C, új / dobja a Pascal, stb algoritmusok célja a leggyakoribb eset általában akkor használjuk: a program kéri blokkok véletlenszerű méretű véletlenszerűen, és feleslegessé őket véletlenszerűen.
A véletlenszerű kérelmek azonban messze nem a legrosszabb lehetőség. A halomkezelési stratégia részleteinek ismerete nélkül meglehetősen könnyű olyan programot készíteni, amely sok közös algoritmust "elrontaná" (4.2. Példa).
4.2. Példa. Példa a memória kérések sorrendjére
míg (TRUE) void * bl = malloc (véletlenszerű (10)); / * Véletlen méret 0-10 bájt * / void * b2 = malloc (random (10) +10); L. 10-20 byte * /
ha (N == NULL B2 == NULL) / * Ha nincs memória * /
break; / * kilép a hurokból * /
szabad (b1);
void * L3 = malloc (150);
/ * Valószínűleg a memóriát nem osztják ki * /
Az ilyen program végrehajtása eredményeképpen az összes rendelkezésre álló memória "vágásra készül": bármelyik két szabad blokk között egy kisebb méretű forgalmas blokkot helyezünk el (4.4. Ábra)
Ábra. 4.4. A program kimenete a 4.2. Példában
Szerencsére a 4.2. Példa mesterséges. A valós programok esetében ez a helyzet ritka, és gyakran jobbnak tűnik a program javítása, mint az egyetemes halomkezelő algoritmus módosítása.
A fenti példa azon a feltételezésen alapul, hogy a rendszer hozzárendel memóriablokkat, amelyek mérete a kérthez egy bájt pontosságával megegyezik. Ha a minimális hozzárendelési egység 32 bájt, a külső példánk nem okoz semmiféle külső töredezettséget: minden blokkhoz egy blokkot osztunk ki. De szembesülnek az ellenkező probléma, amely az úgynevezett belső töredezettség: ha a rendszer képes rydelyat csak blokkokat, hogy a 32 többszörösei bájt, és valóban szükség van 15 vagy 47 bájt, 17 bájtot blokk elvész (lásd 4.5 ábra)..
Ábra. 4.5. Belső széttagoltság
Ábra. 4.6. Antisortirovka
Ábra. 4.7. Párosított címkék
Ábra. 4.8. Párosított címkék kombinálásával
megjegyzés
Ez egy nagyon nagy előny, mivel nagyban megkönnyíti a mutatók hibáinak felismerését, amit a Zortech C / C ++ kézikönyv azt mondja, hogy "a tapasztalt programozók, amikor ezt a szót hallják [ping hiba, jegyzetíró] a táblázat alatt "([Zortech v3.xj].
Ábra. 4.9. Töredékek a malloc implementálásában a GNU LibC-től
4.3. Példa. A malloc / free telepítése a GNU LibC-ben. A __default_morecore függvény a 4.1. Példában látható.
/ * Ha ennek a blokknak egyes töredékei szabadok, akkor ezt a töredéket a fragmensek listájába soroljuk be a blokk első szabad töredéke után. * /
következő = (struct list *) ptr;
next-> next = prev-> next;
következő-> prev = prev;
prev-> next = next;
ha (next-> next! = NULL) next-> next-> prev = next;
++_heapinf® [blokk] .busy.info.frag.nfree;
más
/ * Ebben a blokkban nincsenek szabad töredékek, ezért szerepeljen ez a töredék a töredékek listáján, és bejelenti, hogy ez az első szabad töredék ebben a blokkban. * /
prev = (struct list *) ptr;
_heapinfo [blokk] .busy. info. frag. nfree = 1;
_heapinfo [blokk] .busy. info. frag. első = (jel nélküli hosszú int)
((unsigned long int) ((char *) ptr - (char *) NULL)% BLOCKSIZE »típus); prev-> next = _fraghead [type] .next; prev-> prev = _fraghead [típus]; prev-> prev-> next = prev; ha (prev-> next! = NULL)
prev-> next-> prev = prev;
break;
/ * Hajtsa vissza a memóriát a halomba. * / void
_ libc_free (ptr) _ ptr_t ptr; regisztráljon a struct alignlist * 1;
ha (ptr == NULL) visszatér;
az (1 = _aligned_blocks; 1! = NULL; 1 = l-> következő) ha (l-> aligned == ptr)
l-> aligned = NULL;
/ * Jelölje meg a listaelemet ingyenesnek. * /
ptr = l-> pontos;
break;
ha (_ free_hook! = NULL) (* _ free_hook) (ptr);
más
_free_internal (ptr);
#include
#ifdef elf_alias
elf_alias (ingyenes, cfree);
#endif
Ennek az algoritmusnak a legfőbb hátrányai közé tartozik a megfelelő blokk keresési idejének becslésének képtelensége, ami a valós idejű feladatok számára elfogadhatatlan. Ezekhez a feladatokhoz algoritmust kell előírni, amely egy alkalmas memóriablokkot talál egy rögzített (lehetőleg kis) időre, vagy ésszerű választ ad arra, hogy nincs megfelelő blokk.
A probléma megoldásának legegyszerűbb módja, ha több fix méretű tömbre van szükségünk (lásd a 4.10. Ábrát). Az egyes méretű blokkokat egyesítjük a listánkban. Ha nincs semmi a szükséges méretű blokkok listáján, akkor a nagyobb blokkok listáját vesszük szemügyre. Ha van valami ott, akkor ezt a blokkot részekre vágjuk, egyet adunk a kérő programnak, a második pedig. Igaz, ha a szükséges blokkok mérete egymásnak nem sokszorosodik, mit fogunk csinálni a fennmaradó részekkel?
Ennek a problémának a megoldásához be kell vezetnünk bizonyos korlátozásokat az elosztott blokkok méretére. Például akkor szükséges, hogy ezek a dimenziók egyenlő a Fibonacci-számok (sorozata egész számok, ahol Fi + 1 = Fi + Fi-1. Ebben az esetben, ha meg kell Fi byte, és csak Fi méretű egység + 1 Mi mi könnyen kap két blokk - az egyik a kívánt méretet, és a többi - Fi-1, ami szintén nem vész Igen, bármilyen korlátozás a méret a vezetést a belső töredezettség, de nagy a díjat Secure keresési időt blokk ..?
Ábra. 4.10. Fix méretű blokkok elosztása
Ábra. 4.11. Az ikrek algoritmusa
A fent leírt megközelítés bonyolultabb alkalmazásai is vannak. Például, Novell Netware szabad memória medence áll 4 robban lépésekben 16 bájt (egy blokk mérete 16, 32, 48, 64 bájt), 3 sorok lépéssel 64 bájt (méret 128 egység, 192, 256 bájt) és tizenöt sorok lépés 256 bájt (512 bájtról 4 KB-ra). Nagyobb lekérdezések esetén az egész oldal kiemelt. Érdekes, hogy a kifinomult stratégiában rejlő valós idejű képességeket gyakorlatilag nem használják a Netware-ben.
Például ha a hálózati csatoló illesztőprogramja úgy találja, hogy nincs szabad puffer, hogy megkapja a következő adatcsomagot, akkor nem próbál meg új puffert hozzárendelni a standard algoritmussal. Ehelyett az illesztő egyszerűen figyelmen kívül hagyja a bejövő adatokat, csak az elveszett csomagok számlálójának növelésével. Egy különálló rendszerfolyamat figyelemmel kíséri ennek a számlálónak az állapotát, és csak akkor, ha bizonyos időintervallumon belül meghalad egy bizonyos küszöbértéket, új puffert ad le a vezetőnek.
A felhasználói adatok ilyen megközelítése cinikusnak tűnhet, de nem szabad megfeledkezni arról, hogy amikor az adatok átkerülnek a hálózaton, a csomagvesztés más okai is előfordulhatnak, például az elektromágneses interferencia miatti adatok romlása. Ezért minden magas szintű hálózati protokoll lehetővé teszi a csomagok továbbítását abban az esetben, ha veszteségük van, akármi is okozhatja ezt a veszteséget. Másrészt viszont a valós idejű rendszerekben az olyan adatok figyelmen kívül hagyása, amelyeket még mindig nem tudunk elfogadni és feldolgozni, meglehetősen gyakori, bár nem mindig elfogadható stratégia.