Teorija
Fiksno particioniranje i unutarnja fragmentacija
Kad nema straničenja, jezgra svakom procesu daje jedan neprekinut komad glavne memorije. Najjednostavnije je fixed partitioning (fiksno particioniranje): memorija je unaprijed podijeljena na partitions (particije), a proces zauzima cijelu particiju bez obzira na to koliko mu treba. Neiskorišteni ostatak particije je internal fragmentation (unutarnja fragmentacija). Kod jednakih particija proces od 2M u particiji od 8M baca 6M; proces veći od particije ne može se učitati bez overlays (preklapanja). Nejednake particije smanjuju otpad. Kod queue per partition (red za svaku particiju) proces uvijek čeka na najmanju particiju u koju stane, pa može čekati i kad su veće particije slobodne; kod jednog zajedničkog reda dobiva najmanju slobodnu particiju u koju stane. Broj particija ograničava broj procesa u memoriji.
Fixed partitioning and internal fragmentation
Without paging, the kernel gives each process one contiguous piece of main memory. The simplest scheme is fixed partitioning: memory is divided into partitions in advance, and a process occupies a whole partition no matter how much it needs. The unused rest of the partition is internal fragmentation. With equal-size partitions, a 2M process in an 8M partition wastes 6M; a process larger than a partition cannot be loaded without overlays. Unequal-size partitions reduce the waste. With a queue per partition, a process always waits for the smallest partition it fits in, so it may wait even when larger partitions are free; with a single queue, it gets the smallest free partition it fits in. The number of partitions limits the number of processes in memory.
Dinamičko particioniranje i sažimanje
Kod dynamic partitioning (dinamičko particioniranje) proces dobiva točno onoliko memorije koliko traži, pa unutarnje fragmentacije nema. Kad procesi izlaze, na primjer kad ih jezgra izbaci na disk (swap-out, izbacivanje; ovdje operacija „-P1”), između zauzetih blokova ostaju holes (rupe). S vremenom memorija postaje niz malih rupa: slobodnog prostora ukupno ima dovoljno, ali ne u jednom komadu. To je external fragmentation (vanjska fragmentacija). Susjedne rupe odmah se spajaju u jednu. Compaction (sažimanje) pomiče procese prema dolje tako da ostane jedna velika rupa, ali troši procesorsko vrijeme i traži relocation (relokacija): proces se mora moći izvoditi s nove adrese, pa se adrese programa prevode tek pri izvođenju, preko baznog registra. Pokazatelj „vanjska fragmentacija” u statistici (1 − najveća rupa / slobodno ukupno) je naš, a ne Stallingsov.
Dynamic partitioning and compaction
With dynamic partitioning, a process gets exactly as much memory as it requires, so there is no internal fragmentation. When processes leave, for example when the kernel swaps them out to disk (here the operation “-P1”), holes are left between the allocated blocks. Over time memory becomes a series of small holes: there is enough free space in total, but not in one piece. This is external fragmentation. Adjacent holes are coalesced into one at once. Compaction shifts the processes down so that one large hole remains, but it wastes processor time and requires relocation: a process must be able to run from its new address, so program addresses are translated only at execution time, through a base register. The “external fragmentation” indicator in the statistics (1 − largest hole / total free) is ours, not Stallings's.
Algoritmi smještanja: first-fit, best-fit, next-fit
Placement algorithms (algoritmi smještanja) odlučuju u koju rupu ide novi proces. First-fit uzima prvu dovoljno veliku rupu od početka memorije, best-fit najmanju rupu u koju proces stane, a next-fit nastavlja traženje od mjesta zadnjeg smještanja (pokazivač ispod trake). Stallings navodi da je first-fit obično najbolji i najbrži. Next-fit češće dijeli veliki slobodni blok na kraju memorije, pa sažimanje treba češće. Best-fit je obično najgori: iza sebe ostavlja sitne rupe u koje više ništa ne stane. Tanenbaum & Bos opisuju i worst-fit (najveća rupa) i quick-fit (zasebni popisi rupa uobičajenih veličina). Isti problem smještanja postoji i na disku, vidi Datotečni sustav.
Placement algorithms: first-fit, best-fit, next-fit
Placement algorithms decide which hole a new process goes into. First-fit takes the first hole that is large enough, scanning from the beginning of memory, best-fit takes the smallest hole the process fits in, and next-fit continues the search from the location of the last placement (the pointer below the bar). Stallings notes that first-fit is usually the best and the fastest. Next-fit more often splits the large free block at the end of memory, so compaction is needed more often. Best-fit is usually the worst: it leaves behind tiny holes that nothing fits in anymore. Tanenbaum & Bos also describe worst-fit (the largest hole) and quick-fit (separate lists of holes of common sizes). The same placement problem exists on disk; see File system.
Buddy sustav
Buddy system (buddy sustav) je kompromis između fiksnih i dinamičkih particija: blokovi su veličine 2k, od najmanjeg bloka do cijele memorije. Zahtjev se zaokružuje na najbližu potenciju broja 2 (ali ne ispod najmanjeg bloka). Ako takvog slobodnog bloka nema, najmanji veći blok dijeli se na dvije jednake polovice, dva buddies (buddyja): to je split (dioba), i ponavlja se dok ne nastane blok prave veličine. Kad se blok oslobodi, a njegov buddy je također slobodan, spajaju se natrag u veći blok: merge (spajanje). Adresa buddyja dobiva se isključivim ILI početne adrese i veličine bloka. Raspored se može nacrtati kao binarno stablo blokova. Unutarnja fragmentacija ostaje (proces od 100K dobiva 128K), ali je vanjska ograničena, a diobe i spajanja su brzi. Inačicu buddy sustava koristi jezgra Linuxa za dodjelu okvira fizičke memorije.
Buddy system
The buddy system is a compromise between fixed and dynamic partitions: blocks are of size 2k, from the smallest block up to the whole memory. A request is rounded up to the nearest power of 2 (but not below the smallest block). If there is no free block of that size, the smallest larger block is split into two equal halves, two buddies: this is a split, and it repeats until a block of the right size appears. When a block is freed and its buddy is also free, the two merge back into a larger block: a merge. The address of a block's buddy is the exclusive OR of the block's start address and its size. The layout can be drawn as a binary tree of blocks. Internal fragmentation remains (a 100K process gets 128K), but external fragmentation is limited, and splits and merges are fast. The Linux kernel uses a variant of the buddy system to allocate frames of physical memory.
Zašto straničenje
I fiksne i dinamičke particije traže da proces bude u memoriji u jednom komadu. Paging (straničenje) dijeli proces na stranice, a memoriju na okvire iste veličine, pa proces može zauzeti bilo koje slobodne okvire: vanjske fragmentacije više nema, a unutarnja ostaje samo u zadnjoj stranici procesa. Segmentation (segmentacija) dijeli program na logičke dijelove različitih veličina, pa opet ima vanjsku fragmentaciju, ali bez unutarnje. Nastavak: Prevođenje adresa (stranice, segmenti, TLB) i Zamjena stranica. Izbacivanje cijelog procesa iz memorije odgovara stanjima Suspend u modelu procesa, vidi Procesi.
Why paging
Both fixed and dynamic partitions require a process to be in memory in one piece. Paging divides a process into pages and memory into frames of the same size, so a process can occupy any free frames: there is no more external fragmentation, and internal fragmentation remains only in the last page of a process. Segmentation divides a program into logical parts of different sizes, so it again has external fragmentation, but no internal fragmentation. Next: Address translation (pages, segments, TLB) and Page replacement. Swapping a whole process out of memory corresponds to the Suspend states of the process model; see Processes.
Literatura: Stallings, Operating Systems: Internals and Design Principles, 9. izd., pogl. 7 Memory Management, odjeljak 7.2 Memory Partitioning (fiksno i dinamičko particioniranje, algoritmi smještanja, buddy sustav, relokacija), uz odjeljak 7.1 kao uvod; alternativno Tanenbaum & Bos, Modern Operating Systems, pogl. 3, odjeljci 3.2.2 (swapping) i 3.2.3 (upravljanje slobodnom memorijom).Reading: Stallings, Operating Systems: Internals and Design Principles, 9th ed., ch. 7 Memory Management, sec. 7.2 Memory Partitioning (fixed and dynamic partitioning, placement algorithms, buddy system, relocation), with sec. 7.1 as an introduction; alternatively Tanenbaum & Bos, Modern Operating Systems, ch. 3, sec. 3.2.2 (swapping) and 3.2.3 (managing free memory).