CSE380 - Operating SystemsNotes for Lecture 11 - 10/20/2005© Matt Blaze(some examples by Insup Lee)Where are we?• Memory Management– monoprogramming– base/segment registers– swapping• representation– bitmaps vs. linked lists• allocation strategies– first fit, best fit, worst fitAn aside:Measuring Systems• Simple ideas– easy to explain• Elegant ideas– easy to evaluate and analyze• Good ideas– work well• Not many ideas all all three…Recall from last week:Optimum number of processes• Say each process spends 75% time waiting, how manyprocesses would keep CPU doing useful work all the time?• If each process spends .75 time waiting and assumingindependence, probability that N processes will all wait at thesame time is .75N (this equals .05 for N = 10). So effective CPUutilization is 1 - .75N• If waiting fraction is p then CPU utilization is 1 – pN– this is only a rough estimate, but a useful guide• Number of processes is constrained by memory– so adding more memory can let CPU do more workCPU Utilization:waiting vs. # of processesWhy is this useful to know?• Three parameters– number of processes– CPU utilization– CPU bound vs. I/O bound• Graph tells us– expected utilization given a number of processesof a given type– when it makes sense to buy another CPU– (does not take into account OS overhead)A question:How can we figure out whether agiven program is CPU-bound orI/O bound?Also from last week:Memory Allocation• Suppose a new processrequests 15K, which holeshould it use?– First-fit: 30K hole– Best-fit: 20K hole– Worst-fit: 60K holeFree: 30KO S: 20K Free: 20KB: 50KFree: 60KD: 20KSwapping allocation strategies• Let {Hi | i = 1,…,n} be unused blocks and k be thesize of a requested block.• First-Fit– Select the first Hi such that size (Hi) > k.– In other words, select the first block that is big enough• Best-Fit– Select Hi such that size (Hi) >= k and if size (Hj) > k then size (Hj) > size (Hi) for all i != j.– In other words,, select the smallest block that is big enough.• Worst-Fit– select the largest block (leave the biggest new hole)So which one?• All could leave many small and useless holes.• Assuming 1K blocks:• Best-Fit sometimes performs better: Assume holesof 20K and 15K, requests for 12K followed by 16Kcan be satisfied only by best-fit• But First-Fit can also perform better: Assume holes of20K and 15K, requests for 12K, followed by 14K, and7K, can be satisfied only by first-fit• In practice:– First-Fit is usually better than Best-Fit– First-Fit and Best-Fit are better than Worst FitA question:How do we know which will bebest “in practice”?Approaches to predictingsystem performance• On one end of spectrum: Analytical Approach– fundamental performance properties of thealgorithms and architecture• On other end: Empirical Measurement– instrument and measure the system under“typical” workloads, benchmarks• In the middle: Simulation– measure a model implementation of the system• based on traces or workload generatorsAnalytical Approach• Examine the algorithms against someperformance model, discover theoreticalproperties• Great if you can do it– but need the right model• must capture real performance– can’t always produce meaningful analysis• in fact, we usually can’t• for many systems have we can’t say much more than“somewhere between ‘zero’ and ‘infinite’”Empirical Measurement• Take a real implementation and instrument itto take measurements of performance• Input may be real or synthetic– benchmarks• Great if you can do it - gives real numbers– but may really only measure implementationquality– requires building a whole implementation– requires input workload to be repeatableSimulation• Build a model of the system that recordsperformance measurements– doesn’t have to actually work as a real system,just run the parts of the system being measured(e.g., cache algorithms)• Input may be synthetic (output of a statisticalmodel) or from record of real system input(trace-driven simulation)• Nice compromise, often used• Pitfalls: may not model the system correctlyOK, back to memoryVirtual Memory next…Virtual Memory• Memory is mapped between virtual and physicaladdress spaces on per-process basis– processes use virtual addresses, which are translated byhardware into physical addresses– takes care of relocation and protection problem– requires hardware - a Memory Management Unit (MMU)• The mapping can change at the operating system’spleasure– many addresses might not have a mapping– swapping/paging can store infrequently used memory ondisk– can therefore have more virtual memory than physicalmemoryVirtual MemoryPlusses and Minuses• Advantages– Relocation is basically free– Processes can have huge address spaces• a single process can even use more memorythan is available on the machine• Disadvantages– requires special hardware (MMU)– requires extensive OS supportIssues in Virtual Memory• How are virtual addresses structured?– paging vs. segmentation• What is the interface to the MMU?– loading page table– dealing with references to unmapped addresses• What data structures maintain the mapping tophysical addresses• How to decide what virtual addresses get toreside in physical memory– page replacement rulesVirtual Addresses• Virtual memory gives a complete separation oflogical and physical address-spaces• Today, typically a virtual address is 32 bits– This allows a process to have 4GB of virtual memory– Physical memory is usually smaller than this, and variesfrom machine to machine– Virtual address spaces of different processes aredistinct• Structuring of virtual memory– Paging: Divide the address space into fixed-size pages– Segmentation: Divide the address space into variable-size segments (corresponding to logical units)Paging ArchitectureThe position and function of the MMUPaging• Physical memory is divided into chunks called page-frames (on Pentium, each page-frame is 4KB)• Virtual memory is divided into chunks called pages;size of a page is equal to size of a page frame– So typically, 220 pages (a little over a million) in virtualmemory• OS keeps track of mapping of pages to page-frames• Some calculations:– 10-bit address : 1KB of memory; 1024 addresses– 20-bit address : 1MB of memory; about a million addresses– 30-bit address