程序代写 Networks & Operating Systems Essentials

Networks & Operating Systems Essentials
School of Computing Science, Room: S122

Memory Management (Recap)

• Idea #1àLet’s use special registers to store the first and last address in a process’s address space (Base Register & Limit Register)
• Idea #2àPartition RAM into fixed size partitions, allocate one to each running process
– Would work, but is inflexible and clunky
– Creates internal fragmentation: space within partitions goes unused
• Idea #3àVariable-sized partitions:
– The OS keeps track of lists of allocated ranges and “holes” in RAM
– When a new process arrives, it blocks until a hole large enough to fit it is
– If hole is too large, it’s split in two parts: one allocated to the new process, one
added to the list of holes
• Two or more adjacent holes may be merged
• The OS may then check whether the newly created hole is large enough for any waiting
– Can create external fragmentation: space in between partitions too small to
– Idea #4:à Segments : Maintain several “specialised” segments and a table with info for each segment (extension of BR/LR to “mini” address spaces)
• … but how to map segments to “holes” in RAM?
Networks & Operating Systems Essentials 3

Idea #5: Paging
Networks & Operating Systems Essentials 4

– Partition address space in equally sized, fixed-size partitions (page)
• Size always a power of 2 — i.e., 2d
• Typical page sizes: 1KB – 4KB (could get even bigger in modern OS)
• Each page is kept on disk, so there can be a lot of them
– A location in the address space can be given as either an address, or a page number plus an offset within set page
– Given an address with n bits:
• The least significant d bits are the offset
• The most significant p = n – d bits define the page number
– Partition a large portion of RAM into page frames, each of size equal to a page
– Maintain a page table for each address space; each entry contains:
• A boolean (resident/valid bit): True if page is loaded into a page frame
• A frame address: if resident bit is True, contains the physical address of the first location in the frame
• Can be per process or contain additional data (e.g., process ID) for protection
– Paging means moving a page/frame of data from disk to memory or vice-versa
Networks & Operating Systems Essentials 5

Paging Example
• Assume we have a 32-byte memory — i.e., n = 5
• Assume 4-byte frames — i.e., d = 2
• Assume our process’s address space (i.e. logical memory) is 16 bytes large

Memory Address Translation
Wait… What if p and f were a different size?
Should then p be larger or smaller than f? p<=f Networks & Operating Systems Essentials Source: A. Silberschatz, “Operating System Concepts”, 9th Ed., 2012. Allocation of Frames • Each process needs minimum number of frames – Maximumistotalframesinthesystem,minusframesallocatedtothe • Three major allocation schemes: – Fixedallocation • Divide available frames equally among processes – Proportionalallocation • Give each process a percentage of frames equal to its size divided by the sum of sizes of all processes – Priorityallocation • Like proportional allocation, but taking into account the priority of a process (possibly in combination with its size) • Speed of access to memory may vary across CPUs -- e.g., NUMA (non-uniform memory access) systems – Betterallocatememory“closeto”theCPUwheretheprocessthat caused the page fault is running Implementation considerations • Page table is an OS construct but with hardware assistance... • Page table is kept in main memory – Page-tablebaseregister(PTBR)pointstobeginningofpagetable location – Page-tablelengthregister(PTLR)indicatessizeofthepagetable • But wait! In this scheme every data/instruction access requires two memory accesses!!! – Oneforthepagetableandoneforthedata/instruction • How is this acceptable? • Caching to the rescue... – Use an on-CPU cache of the Page Tableè Translation Lookaside Buffer (TLB) Translation Lookaside Buffer (TLB) @Operating System Concepts 9th edition Aside: TLB Effective Access Time • Consider a system where each memory access takes m = 100ns and each TLB lookup requires t = 10ns • Now consider a X% TLB hit ratio (ρ) – ForX%ofmemoryaccesseswe’llhavethephysicaladdressfromthe TLB in 10ns – For(100-X)%ofmemoryaccesses,we’llneedtogotoRAMtofetch the mapping to the physical address, taking 10ns + 100ns – ...plus100nsfortheactualmemoryaccess • Effective Access Time (EAT): – EAT=ρ ́(t+m) + (1–ρ) ́(t+m+m) – ρ=80%èEAT=0.8 ́(10+100)+0.2 ́(10+100+100)=130ns – ρ=99%èEAT=0.99 ́(10+100)+0.01 ́(10+100+100)=111ns • Not that bad after all... Shared Pages • Pages may be shared across processes – Often done for pages containing code Ø One copy of read-only (reentrant) code shared among processes (i.e., text editors, compilers) • Remember fork? – Expensive as should create fully copy of parent process’s address space • Can we make it any faster? • Yes, with Copy-on-Write (COW) – Both processes share the same pages – If a process tries to modify a page, a private copy is created Implementation considerations (cont.) • Time for some quick math... – 4 kB page frames in a 64-bit address space – 4kB = 212 bytesè12-bit offsetè52-bit page no Ø 252 pages in the page table – Assume 2 ́ 64 bits (=16 bytes) per entry of the page table Ø 16 ́ 252 = 256 = 32 petabytes! • Now the page table cannot fit in the RAM!!! • Solution: partition the page table... Networks & Operating Systems Essentials 19 Implementation considerations (cont.) • Idea #1: Hierarchical page tables – 2-level PTs quite common • Idea #2: Hashed page tables – Hash table of linked lists of mappings – Can contain multiple mappings per entry (clustered PTs) • Idea #3: Inverted page table – Maintain mappings of each physical frame to virtual addresses – Mapping must also contain owner process id Networks & Operating Systems Essentials 21 Paging revisited • Remember: – Each page is kept on disk, so there can be a lot of them – Paging means moving a page/frame of data from disk to memory or vice-versa – Originally, all pages are on disk (e.g., before executing a program) • When should a page be moved from disk to memory? – All pages on process startup – Every page only as needed (accessed) Ø Demand paging -- i.e., using a “lazy” pager Networks & Operating Systems Essentials 22 Demand Paging • Remember the “resident/valid bit”? • What if a process tries to access a page that isn’t loaded in RAM? – Pagefault! • The pager (a.k.a. page fault handler) kicks in... 1. Trap to OS (process is blockedàcontext switch) 2. Kernelcomputespagelocationondisk 3. Kernelissuesadiskreadtoloadcontentsofthepagetoafreeframe 4. Jumptotheprocessscheduler(otherprocessesexecute) 5. Interruptfromthedisk(I/Ocompleted) 6. Contextswitch&controlpassedtopager 7. Pagerupdatesthepagetable(frameaddress,residentbit) 8. ProcessmovedtotheREADYqueue 9. Pagerreturnstoprocessscheduler Networks & Operating Systems Essentials 23 Demand Paging • Virtual memory can run almost as fast as real memory, if the proportion of instructions that cause a page fault is low enough • In the real world, programs perform almost all their memory accesses at addresses close to where they recently accessed data – Nearlyallaccessesaretoaworkingsetwhichiskeptinpageframes • Page faults occur when a program changes its working set (e.g. when a method has finished, and calls another) • Occasionally, a program will perform too many page faults – Theresultisthatitstartstoexecutethousandsoftimesslowerthanit should – Thisiscalledthrashing Networks & Operating Systems Essentials 24 Demand Paging • Time for some more quick math... • Suppose you execute 100 instructions; 1 causes a page fault and 99 don’t • How much slower will this run than if there were no page fault? – Typical time to execute an instruction: 1ns (if cache hit) – Typical disk access time: 50ms • We’ll estimate this, not calculate it exactly – Time for 100 instructions (no page fault) = 1ns / instruction ́ 100 instructions = 100 ns – Time for 99 instructions = 99 ns ~= 102 ns – Timefor1pagefaultassumingfreeframeexists~=50ms=50 ́106 ns=5 ́107 ns – Slowdown = (5 ́ 107)/102 = 500,000 • Conclusion: if you have as many as 1% page faults, your program will run half a million times slower! • Generally, if page fault rate: p Î [0, 1], then Effective Access Time (EAT) = (1 – p) ́ memory access + p ́ (page fault overhead + swap page out + swap page in + restart overhead) Networks & Operating Systems Essentials 25 Page Replacement • Normally, most or all of the page frames are in use • In this case, when a page fault occurs, it isn’t possible simply to read the page into an empty frame • The system must: 1. Select a full frame (page replacement strategy/algorithm) 2. Write its contents to disk (page-out) 3. Then read the required page into this frame (page-in) • In practice, it’s better to keep several empty frames • On a page fault, the read (to load the data) can start immediately • A separate write (to clear another frame) can be done right after that (or lazily even later) • Can further optimise page-outs by introducing “dirty/modified” bit • Set to 1 if page has been updatedàonly write page to disk if true Page Replacement • Note: With page replacement, larger virtual memory can be provided on a smaller physical memory • Page replacement requires hardware... – Circuitry in the CPU must: 1. Find the page number 2. Look up the page table entry 3. Check for residency 4. If resident, find the real memory address 5. If not resident, generate an interrupt – Has to be done in hardware, for efficiency • ... and software – In the event of a page fault, the pager must: • Perform the disk I/O • Maintain the page table • Implement the page replacement policy – Has to be done in software, because of complexity and flexibility Networks & Operating Systems Essentials 27 Page Replacement • If a page is written from a frame back to disk, and data on this page is needed soon, it will have to be read back in – ThisresultsintoomuchdiskI/O(slow) • Therefore, the pager doesn’t randomly choose a frame to clear – Ithasasophisticatedpagereplacementpolicy – Goal:Trytochooseaframecontainingapagethatprobablywon’tbe needed again soon • Enter page replacement algorithms... • Alternatives: – Globalreplacement:considerall(non-OS)frames – Localreplacement:onlyconsiderframesallocatedtotheprocessthat caused the page fault Networks & Operating Systems Essentials 28 Page Replacement Algorithms • Optimal (OPT or MIN): – Page-outthepagethatwon’tbeusedforthelongestperiodoftime-- unrealistic • First-In-First-Out (FIFO): – Storethepage-intimeofeverypage;chooseoldestpagetopage-out – Addloadedpagesatthetailofaqueue;choosetheheadofthequeue to page out • Least Recently Used (LRU): – Storethetimeofuseofeverypage;choosethepagethathasn’tbeen used for the longest – Moveaccessedpagesatthetailofaqueue;choosetheheadofthe queue to page-out – Pickapageatrandom – GenerallybetterthanFIFObutworsethanLRUinpractice Networks & Operating Systems Essentials 29 Page Replacement Algorithms (cont.) • Simple reference-bit-based: – Maintainan“accessedbit”perpage(initially0);choosefirstpagewith • Least Frequently Used (LFU) / Non Frequently Used (NFU) – Maintaincounterofaccessestoeachpage;choosethepagewiththe lowest count to page-out • Aging / additional reference bits: – Maintainamulti-bitwordperpage;setMSBto1onaccess;shiftright regularly; choose page with lowest value to page-out • Second-chance (clock): – Maintainan“accessedbit”perpage;runFIFOtoselectapage;if accessed bit is 0, page-out; otherwise (if 1), set to 0, move the page at the tail of the queue and re-run FIFO Networks & Operating Systems Essentials 30 Page Replacement Algorithms (cont.) • Not Recently Used (NRU): – Maintain“accessed”and“modified”bitsperpage;usethetwobits (accessed, modified) as a 2-bit score; choose the first page with the lowest score • (0,0) = 0: not accessed, not modified (best candidate)èif found, page- out • (0,1) = 1: not recently used but modified (will need write out to disk)è write-out, clear modified bit, continue the search • (1,0) = 2: recently used but not modified (better keep it as might be used again soon)èclear accessed bit, continue the search • (1,1) = 3: accessed and modified (worst candidate) è clear accessed bit, continue the search • Multiple passes may be required; by the 3rd pass, all pages will be at (0,0) Networks & Operating Systems Essentials 31 Page Replacement Algorithm Evaluation • Evaluation methodology: – Usefixedsequenceofpageaccesses – Evaluatedbycomputingthenumberofpagefaults(denotedby*) • Running example: – Consideracachewith3slotsandthefollowingstreamofrequests: A, B, C, A, B, B, D, A, C, D, B • A, B, C, D: page numbers/addresses Networks & Operating Systems Essentials 32 OPT example • Accessstring:B,C,A,B,B,D,A,C,D,B • ‘*’ = page fault Networks & Operating Systems Essentials 33 RANDOM example • Accessstring:B,C,A,B,B,D,A,C,D,B • ‘*’ page fault Networks & Operating Systems Essentials 34 FIFO example • Accessstring:B,C,A,B,B,D,A,C,D,B • Maintaining page-in time for every page • ‘*’ = page fault Networks & Operating Systems Essentials 35 LRU example • Accessstring:B,C,A,B,B,D,A,C,D,B • Maintaining last access time for every page • ‘*’ = page fault Networks & Operating Systems Essentials 36 LFU example • Accessstring:B,C,A,B,B,D,A,C,D,B • Maintaining access counts for every page • ‘*’ = page fault Networks & Operating Systems Essentials 37 Reference Bit example • Accessstring:B,C,A,B,B,D,A,C,D,B • Maintaining reference bit for every page, resetting after two accesses • ‘*’ = page fault Networks & Operating Systems Essentials 38 Aging example • Accessstring:B,C,A,B,B,D,A,C,D,B • Maintaining 3 bits for every page, shifting on every access • ‘*’ = page fault Networks & Operating Systems Essentials 39 Second-chance (clock) example • Accessstring:B,C,A,B,B,D,A,C,D,B • Maintaining page-in time and access bit for every pageà(page_in, access) • ‘*’ = page fault Networks & Operating Systems Essentials 40 NRU example • Access string: B, C, A, B, B, D, A, C, D, B • Maintaining page-in time, and access and modify bit for every pageà(page_in, access, modify) • Assume underlined accesses are modifications • ‘*’ = page fault Networks & Operating Systems Essentials 41 Recommended Reading • Silberschatz, Galvn and Gagne, Operating Systems Essentials, Chapter 7, sections 7.3,7.4, 7.5 Networks & Operating Systems Essentials 42 程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts