Teorija
Politika zamjene
Kad page fault (promašaj stranice) zatekne sve frame (okvir) zauzete, operacijski sustav mora izabrati stranicu koju će izbaciti. To je replacement policy (politika zamjene), jedna od Stallingsovih politika virtualne memorije, uz politike dohvata, smještanja, upravljanja rezidentnim skupom, čišćenja i upravljanja opterećenjem. Algoritmi se uspoređuju na reference string (niz referenci), nizu brojeva stranica koje proces redom koristi. U načinu zamjene stranica simulator koristi fixed allocation (fiksna dodjela) i local scope (lokalni opseg): proces ima stalan broj okvira i izbacuje samo svoje stranice. Stallings broji promašaje tek nakon što se okviri prvi put napune (oznaka F na slici), a simulator uz njih prikazuje i ukupan broj, zajedno s promašajima pri punjenju (P).
Replacement policy
When a page fault finds every frame occupied, the operating system must choose a page to remove. This is the replacement policy, one of Stallings's virtual memory policies, alongside the fetch, placement, resident set management, cleaning and load control policies. The algorithms are compared on a reference string, the sequence of page numbers that a process uses in turn. In page replacement mode the simulator uses fixed allocation and local scope: the process has a constant number of frames and replaces only its own pages. Stallings counts page faults only after the frames have first been filled (marked F in his figure); the simulator also shows the total, including the faults while filling (L).
OPT, LRU i FIFO
OPT izbacuje stranicu čija je sljedeća uporaba najdalje u budućnosti; ako se više stranica više nikad ne koristi, simulator bira onu u najnižem okviru. OPT daje najmanje promašaja, ali traži poznavanje budućih referenci, pa služi samo kao mjerilo za druge algoritme. LRU izbacuje stranicu koja se najdulje nije koristila i oslanja se na locality (lokalnost): nedavno korištene stranice vjerojatno će se uskoro opet koristiti. LRU je blizu OPT-a, ali sklopovlje bi uz svaku referencu moralo pamtiti vrijeme uporabe, što je preskupo. FIFO izbacuje stranicu koja je najdulje u memoriji; jednostavan je, ali ne gleda uporabu, pa izbacuje i stalno korištene stranice. Na Stallingsovom nizu nakon punjenja OPT ima 3 promašaja, LRU 4, Clock 5, a FIFO 6.
OPT, LRU and FIFO
OPT replaces the page whose next use is farthest in the future; if several pages are never used again, the simulator picks the one in the lowest frame. OPT gives the fewest page faults, but it needs to know future references, so it serves only as a benchmark for other algorithms. LRU replaces the page that has gone unused for the longest time and relies on locality: recently used pages are likely to be used again soon. LRU comes close to OPT, but the hardware would have to record the time of use with every reference, which is too expensive. FIFO replaces the page that has been in memory the longest; it is simple, but it ignores use, so it also removes pages that are used all the time. On Stallings's string, after the frames fill, OPT has 3 page faults, LRU 4, Clock 5 and FIFO 6.
Clock i bit korištenja
Clock približno ostvaruje LRU uz malo sklopovlja. Svaki okvir ima use bit (bit korištenja) u koji sklopovlje upisuje 1 pri svakoj referenci. Okviri čine kružni međuspremnik, a clock hand (kazaljka) pokazuje na sljedećeg kandidata. Pri zamjeni kazaljka prelazi okvire: bit 1 briše u 0 i ide dalje, a prvu stranicu s bitom 0 izbacuje; nova stranica dobiva bit 1, a kazaljka se pomiče na sljedeći okvir. Stranica koja je korištena tako dobiva još jednu priliku; Tanenbaum Clock opisuje kao kružnu izvedbu algoritma second chance (druga prilika), koji istu provjeru radi na FIFO listi. Inačica s modify bit (bit izmjene) radije izbacuje nepromijenjene stranice, jer izmijenjenu stranicu prije izbacivanja treba zapisati na disk, kao u scenariju Promašaj stranice na stranici Prevođenje adresa.
Clock and the use bit
Clock approximates LRU with little hardware. Every frame has a use bit, which the hardware sets to 1 on every reference. The frames form a circular buffer, and the clock hand points to the next candidate. On a replacement the hand moves over the frames: it clears a use bit of 1 to 0 and moves on, and it replaces the first page whose bit is 0; the new page gets a use bit of 1, and the hand moves to the next frame. A page that has been used thus gets one more chance; Tanenbaum describes Clock as a circular implementation of the second-chance algorithm, which does the same check on a FIFO list. A variant with a modify bit prefers to replace unmodified pages, because a modified page must be written to disk before it is replaced, as in the scenario Page fault on the Address translation page.
Beladyjeva anomalija
Očekujemo da više okvira znači manje promašaja, ali kod FIFO to ne vrijedi uvijek. Na nizu 1 2 3 4 1 2 5 1 2 3 4 5 FIFO s 3 okvira ima 9 promašaja, a s 4 okvira 10. To je Belady's anomaly (Beladyjeva anomalija); uz konvenciju ovog simulatora pokazuje je i Clock. LRU i OPT su stack algorithms (algoritmi stoga): skup stranica u memoriji s F okvira uvijek je podskup skupa s F + 1 okvira, pa dodatni okvir nikad ne povećava broj promašaja. Krivulja promašaja u simulatoru označava svaku takvu točku natpisom „anomalija”.
Belady's anomaly
We expect more frames to mean fewer page faults, but with FIFO this does not always hold. On the string 1 2 3 4 1 2 5 1 2 3 4 5, FIFO with 3 frames has 9 page faults, and with 4 frames 10. This is Belady's anomaly; under this simulator's conventions Clock shows it too. LRU and OPT are stack algorithms: the set of pages in memory with F frames is always a subset of the set with F + 1 frames, so an extra frame never increases the number of page faults. The fault curve in the simulator marks every such point with the label “anomaly”.
Rezidentni i radni skup
Resident set (rezidentni skup) su stranice procesa koje su trenutno u memoriji. Working set (radni skup) W(t, Δ) su različite stranice korištene u zadnjih Δ referenci do trenutka t; Δ (delta) je working-set window (prozor radnog skupa). Strategija radnog skupa drži u memoriji upravo W: promašaj nastaje kad referenca nije među zadnjih Δ referenci. Uz variable allocation (promjenjiva dodjela) broj okvira procesa raste i pada s veličinom radnog skupa, a global scope (globalni opseg) dopušta izbacivanje stranica drugih procesa. Page fault frequency (PFF, učestalost promašaja stranica) je praktična zamjena: procesu se dodaje okvir kad promašuje prečesto, a oduzima kad promašuje rijetko.
Resident set and working set
The resident set is the set of pages of a process that are currently in memory. The working set W(t, Δ) is the set of distinct pages used in the last Δ references up to time t; Δ (delta) is the working-set window. The working-set strategy keeps exactly W in memory: a page fault occurs when the referenced page has not been referenced in the last Δ references. With variable allocation the number of frames of a process grows and shrinks with the size of its working set, and global scope allows pages of other processes to be replaced. Page fault frequency (PFF) is a practical substitute: a process gets an extra frame when it faults too often and loses one when it faults rarely.
Thrashing i upravljanje opterećenjem
Kad je ukupna veličina radnih skupova veća od memorije, procesi stalno izbacuju stranice koje će im uskoro trebati: to je thrashing. Procesor tada većinom čeka uređaj za straničenje, pa iskorištenost pada iako je procesa više. Load control (upravljanje opterećenjem) zato ograničava multiprogramming level (razina multiprogramiranja) i po potrebi suspendira procese, vidi Procesi; o tome koji spremni proces dobiva procesor odlučuje Raspoređivanje. Model thrashinga u simulatoru je pojednostavljen i naš: 24 okvira, procesi koji ciklički koriste po 6 stranica, globalni LRU i jedan uređaj za straničenje. S 4 procesa (24 stranice) iskorištenost je 100 %, a s 5 procesa (30 stranica) pada na oko 10 %. Kako promašaj stranice nastaje u sklopovlju i prelazi u jezgru, prikazuju Prekidi i Put jednog poziva; dodjelu okvira bez virtualne memorije prikazuje Dodjela memorije.
Thrashing and load control
When the total size of the working sets exceeds memory, processes keep removing pages they will soon need: this is thrashing. The processor then spends most of its time waiting for the paging device, so utilization drops even though there are more processes. Load control therefore limits the multiprogramming level and suspends processes when needed, see Processes; which ready process gets the processor is shown on the Scheduling page. The thrashing model in the simulator is simplified and our own: 24 frames, processes that cycle through 6 pages each, global LRU and one paging device. With 4 processes (24 pages) utilization is 100%, and with 5 processes (30 pages) it drops to about 10%. How a page fault arises in the hardware and passes into the kernel is shown on the Interrupts and Journey of a call pages; allocating frames without virtual memory is shown on the Memory allocation page.
Literatura: Stallings, Operating Systems: Internals and Design Principles, 9. izd., pogl. 8 (8.2 Operating System Software: Replacement Policy, Resident Set Management, Load Control); alternativno Tanenbaum & Bos, Modern Operating Systems, pogl. 3 (3.4 Page Replacement Algorithms, 3.5.1 Local versus Global Allocation Policies, 3.5.2 Load Control).Reading: Stallings, Operating Systems: Internals and Design Principles, 9th ed., ch. 8 (8.2 Operating System Software: Replacement Policy, Resident Set Management, Load Control); alternatively Tanenbaum & Bos, Modern Operating Systems, ch. 3 (3.4 Page Replacement Algorithms, 3.5.1 Local versus Global Allocation Policies, 3.5.2 Load Control).