Software Systems Spring 2005 For today, you should have: 1) read Tanenbaum pages 202-219 2) read the Lottery Scheduling paper and answered the reading questions 3) finished Homework 3 4) prepared for a quiz on CPU scheduling Outline: 1) quiz 2) Homework 4 For next time you should: 1) start Homework 4 2) read Chapter 9 from Stochastic Modeling 3) think about projects: proposal due March 4! 4) read notes09.txt and notes10.txt Homework 4 groups: jesus.fernandez william.clayton grant.hutchins jonathan.pollack kathleen.king kevin.tostado christopher.stone douglas.ellwanger steven.shannon anthony.roldan alexander.davis nicholas.zola brendan.doms sharon.talbot aleksander.lorenc sarah.leavitt jonathan.tse kathryn.rivard matthew.colyer Virtual memory -------------- A week or so ago, we saw two processes running at the same time access the same memory location and get two different values. At the time, this was baffling, but that's because we didn't know about... VIRTUAL MEMORY!!! When a process accesses a memory location, it generates a virtual address, or VA. A virtual address is relative to the address space of the process that generates it, but 1) each process has its own address space 2) virtual addresses don't refer to real, physical memory locations. Before the actual memory access, the system has to translate the virtual address into a physical address. This process has to be fast, so it is usually done in hardware, specifically in the MEMORY MANAGEMENT UNIT. The MMU is like a weird lens between the virtual address spaces of the processes and the physical memory. Address translation ------------------- Most address translation is page-based, meaning that the virtual address is split into 1) a page address 2) an offset within the page In general, we can split up the address bits arbitrarily. Small example: 8-bit addresses Option #1: 5 bits of page address, 2 bits of offset How many pages? How many bytes per page? Option #2: 2 bits of page address, 6 bits of offset How many pages? How many bytes per page? Assuming that we choose Option #2, and that we have a 1KB physical memory: How many pages can we fit in physical memory? A space in physical memory where we can put a page is called a frame. In this case there are more frames (total) than there are pages per process. How big is a frame address? So, to translate an address: 1) split the VA into a page address and an offset. 2) look up the page address in the address translation table and get the frame address 3) attach the frame address to the offset and you have the physical address! How big is the address translation table? number of entries * size of entry = number of pages * size of a frame address = Paging ------ The primary benefit of virtual memory is that it creates the illusion that each process runs in an unshared address space. Virtual memory can be expensive to implement, but once you pay the price, there are several addition benefits: 1) you don't have to keep every page for every process in memory. If something hasn't been used for a while, you can move it to disk, or across the network to someone else's memory, or whatever! 2) multiple processes can share physical pages, which provides an efficient form of inter-process communication. 3) you can map files and other kinds of data into a process's address space, so that what seems to be a memory access is actually a file access, or an access to some other device altogether. How does all this work? There are (at least) two kinds of page table entries. A normal entry contains the frame number where the physical memory is located. A "special" entry indicates that the address being translated refers to something other than physical memory. When the process tries to access a special address, the hardware causes a trap, which is similar to an interrupt. What does the OS do next? 1) Figure out where the data really are. 2) Initiate an I/O operation to get the data. 3) Switch to another process, if there is one. Later, when the data arrives: 1) Store the data in physical memory. 2) Update the page table. 3) Resume the interrupted process. Why not wait until the page arrives? What if there aren't any empty frames? Full-sized example ------------------ In a 32-bit address space with 1K pages, how many bits for page address, offset? With 256MB of memory, how many bits for physical address, frame address? How many entries in the page table? How big is each entry? How big is the page table? Hmm. Problem.