Teorija
Logička i fizička adresa
Program radi s logical address (logička adresa), a memorija s physical address (fizička adresa). Kod paging (straničenje) logički adresni prostor dijeli se na page (stranica) jednake veličine, a fizička memorija na frame (okvir) iste veličine. Memory management unit (MMU, jedinica za upravljanje memorijom) dijeli adresu na broj stranice (viši bitovi) i offset (pomak, niži bitovi). Broj stranice je indeks u page table (tablica stranica) procesa, čiju adresu drži registar PTBR (page table base register), a unos daje broj okvira. Fizička adresa je okvir · veličina stranice + pomak: offset se prepisuje nepromijenjen. Stallingsov primjer: uz 16-bitnu adresu i stranice od 1 KB (6 + 10 bitova) adresa 1502 je stranica 1 s pomakom 478, stranica 1 je u okviru 6, pa je fizička adresa 6 · 1024 + 478 = 6622. Paging nastavlja fiksno particioniranje iz modula Dodjela memorije, ali bez vanjske fragmentacije.
Logical and physical address
A program works with logical addresses, and memory with physical addresses. With paging, the logical address space is divided into pages of equal size, and physical memory into frames of the same size. The memory management unit (MMU) splits an address into a page number (the high bits) and an offset (the low bits). The page number is an index into the page table of the process, whose address is held in the PTBR (page table base register), and the entry gives the frame number. The physical address is frame · page size + offset: the offset is copied unchanged. Stallings's example: with a 16-bit address and 1 KB pages (6 + 10 bits), address 1502 is page 1 with offset 478, page 1 is in frame 6, so the physical address is 6 · 1024 + 478 = 6622. Paging resembles fixed partitioning (see Memory allocation), but the partitions are small, and a process may occupy several that need not be contiguous.
Segmentacija
Kod segmentation (segmentacija) program se dijeli na segmente različite duljine, npr. kod, podatke i stog. Adresa je broj segmenta i pomak, a tablica segmenata za svaki segment čuva base (baza) i length (duljina). MMU prvo provjerava je li pomak manji od duljine, a zatim bazu zbraja s pomakom; bitovi se ovdje ne prepisuju, nego zbrajaju. Uz 4 bita segmenta i 12 bitova pomaka adresa 4848 je segment 1 s pomakom 752, pa uz bazu 8224 daje 8976. Pomak 752 u segmentu 0 duljine 750 izaziva protection fault (zaštitna greška). Kombinacija segmentacije i straničenja opisana je u udžbeniku, ali se ovdje ne simulira.
Segmentation
With segmentation, a program is divided into segments of different lengths, for example code, data and stack. An address is a segment number and an offset, and the segment table keeps a base and a length for each segment. The MMU first checks whether the offset is less than the length, and then adds the base to the offset; here the bits are not copied but added. With 4 bits of segment number and 12 bits of offset, address 4848 is segment 1 with offset 752, so with base 8224 it gives 8976. Offset 752 in segment 0 of length 750 causes a protection fault. The combination of segmentation and paging is described in the textbook, but it is not simulated here.
Bitovi P i M i dvorazinska tablica
Page table entry (PTE, unos tablice stranica) uz broj okvira ima present bit (bit prisutnosti, P) i modify bit (bit izmjene, M). P = 0 znači da je stranica valjana, ali je na disku; M = 1 znači da je stranica mijenjana i da se prije izbacivanja mora zapisati na disk. Za 32-bitni adresni prostor sa stranicama od 4 KB tablica bi imala 220 unosa po procesu, pa se koristi two-level page table (dvorazinska tablica stranica): outer table (vanjska tablica) s 210 unosa pokazuje na inner table (unutarnja tablica), što je Stallingsova podjela 10/10/12. Unutarnje tablice postoje samo za korišteni dio prostora, a svaka razina znači jedan pristup memoriji više.
The P and M bits and the two-level table
Besides the frame number, a page table entry (PTE) has a present bit (P) and a modify bit (M). P = 0 means that the page is valid but on disk; M = 1 means that the page has been modified and must be written to disk before it is replaced. For a 32-bit address space with 4 KB pages the table would have 220 entries per process, so a two-level page table is used: an outer table with 210 entries points to inner tables, which is Stallings's 10/10/12 split. Inner tables exist only for the used part of the space, and every level means one more memory access.
Invertirana tablica stranica
Inverted page table (invertirana tablica stranica) ima jedan unos po okviru, a ne po stranici, pa joj veličina ovisi o fizičkoj memoriji, a ne o broju procesa. Unos kaže koji proces (pid) i koja njegova stranica je u tom okviru. Za traženje se koristi hashing (raspršivanje) broja stranice i pid-a, a kolizije rješava chaining (ulančavanje). U simulatoru je h = (stranica + pid) mod broj okvira, a lanci počinju u hash anchor table (tablica ulaza raspršivanja). Ta zasebna tablica je naša pretpostavka, kao kod IBM-ova PowerPC-a i u Tanenbaumu; Stallingsova slika raspršuje izravno u IPT. Svaka proba u lancu je jedan pristup memoriji.
Inverted page table
An inverted page table has one entry per frame, not per page, so its size depends on physical memory and not on the number of processes. An entry says which process (pid) and which of its pages is in that frame. The lookup uses hashing of the page number and the pid, and collisions are resolved by chaining. In the simulator h = (page + pid) mod number of frames, and the chains start in a hash anchor table. This separate table is our assumption, as in IBM's PowerPC and in Tanenbaum; Stallings's figure hashes directly into the IPT. Every probe in a chain is one memory access.
TLB i lokalnost
Bez pomoći bi svaka referenca trebala dva pristupa memoriji: jedan za tablicu i jedan za podatak. Translation lookaside buffer (TLB) je mala asocijativna memorija u MMU-u s nedavnim prijevodima: hit (pogodak) daje okvir bez čitanja tablice. To radi zbog locality (lokalnost): program uzastopno pristupa istim stranicama. Stallingsov dijagram toka redom provjerava TLB, na promašaj čita tablicu stranica, ako je P = 1 upisuje prijevod u TLB i tek tada tvori fizičku adresu. Effective access time (EAT, efektivno vrijeme pristupa) je prosječno vrijeme po referenci; naš model ga računa kao (pretraživanja TLB-a · vrijeme TLB-a + pristupi memoriji · vrijeme memorije + promašaji stranice · vrijeme promašaja) / broj referenci. Uz 100 ns za memoriju i 8 ms za promašaj stranice jedan promašaj stoji koliko 80 000 pristupa memoriji.
TLB and locality
Without help, every reference would need two memory accesses: one for the table and one for the data. The translation lookaside buffer (TLB) is a small associative memory in the MMU that holds recent translations: a hit gives the frame without reading the table. This works because of locality: a program accesses the same pages again and again. Stallings's flowchart checks the TLB first; on a miss it reads the page table, and if P = 1 it loads the translation into the TLB and only then forms the physical address. The effective access time (EAT) is the average time per reference; our model computes it as (TLB lookups · TLB time + memory accesses · memory time + page faults · page fault time) / number of references. With 100 ns for memory and 8 ms for a page fault, one page fault costs as much as 80,000 memory accesses.
Promašaj stranice kao iznimka
Kad je P = 0, MMU izaziva page fault (promašaj stranice), exception (iznimka) koja usred instrukcije prenosi upravljanje jezgri kao trap (zamka), vidi Prekidi. Jezgra blokira proces i radi process switch (promjena konteksta), vidi Procesi. Zatim uzima slobodni okvir ili bira victim page (stranica-žrtva), vidi Zamjena stranica; poništava njezin unos u TLB-u, izmijenjenu žrtvu zapisuje na disk (write-back, pisanje natrag), čita traženu stranicu i ažurira tablicu. Proces je cijelo to vrijeme blokiran. Nakon toga slijedi instruction restart (ponovno pokretanje instrukcije): ista instrukcija ponovno promaši TLB, pročita tablicu i tek tada puni TLB. Za razliku od toga, adresa izvan mapiranog prostora ili pomak izvan segmenta je protection fault: proces se prekida i instrukcija se ne ponavlja. Cijeli tijek jednog promašaja stranice kroz sve slojeve, od MMU-a do diska i natrag, prikazuje Put jednog poziva.
The page fault as an exception
When P = 0, the MMU raises a page fault, an exception that transfers control to the kernel in the middle of an instruction as a trap, see Interrupts. The kernel blocks the process and performs a process switch, see Processes. It then takes a free frame or chooses a victim page, see Page replacement; it invalidates the victim's TLB entry, writes a modified victim to disk (write-back), reads the requested page and updates the table. The process is blocked the whole time. Then comes the instruction restart: the same instruction misses the TLB again, reads the table and only then fills the TLB. In contrast, an address outside the mapped space or an offset outside the segment is a protection fault: the process is terminated and the instruction is not repeated. The whole flow of one page fault through all layers, from the MMU to the disk and back, is shown on the Journey of a call page.
Literatura: Stallings, Operating Systems: Internals and Design Principles, 9. izd., pogl. 7 (7.3 Paging, 7.4 Segmentation) i pogl. 8 (8.1 Hardware and Control Structures: tablice stranica, TLB, invertirana tablica), uz pogl. 1 (1.4 Interrupts, razred „program”); alternativno Tanenbaum & Bos, Modern Operating Systems, pogl. 3 (3.3 Virtual Memory, 3.6.2 Page Fault Handling, 3.6.3 Instruction Backup, 3.7 Segmentation).Reading: Stallings, Operating Systems: Internals and Design Principles, 9th ed., ch. 7 (7.3 Paging, 7.4 Segmentation) and ch. 8 (8.1 Hardware and Control Structures: page tables, TLB, inverted page table), with ch. 1 (1.4 Interrupts, the “program” class); alternatively Tanenbaum & Bos, Modern Operating Systems, ch. 3 (3.3 Virtual Memory, 3.6.2 Page Fault Handling, 3.6.3 Instruction Backup, 3.7 Segmentation).