Software Systems Spring 2008 For today, you should have: 1) Worked on Homework 3 (Thursday) 2) Read Chapter 10 of the Cow Book 3) Done the next semaphore problem (exclusive queue) 4) Read Tanenbaum page 202-210 (no reading questions) 5) prepared for a quiz Outline: 1) fork.c (a popular choice for "most confusing") 2) performance evaluation / early project thinking 3) virtual memory / address translation / paging 4) exclusive queue solution -- handoff pattern For next time you should: 1) finish Homework 3 (read "What to turn in") 2) flip through Chapter 11 of the Cow Book just to see what's there, and then read Chapter 12 and do Exercise 12-2. 3) do the next semaphore problem (producer-consumer) 4) read from Tanenbaum and answer the questions below fork.c ------ Read "man fork" and the handout at wb/ss/handouts/stevens93fork.pdf What's this "copy on write thing"? What do you think of the buffering behavior!?! Issues about timing this kind of operation. Results: Process creation time = Thread creation time = Virtual memory -------------- When a process accesses a memory location, it generates a virtual address, or VA. 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 (at least) = 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 additional 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 1KB 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? Page replacement algorithms --------------------------- Read Tanenbaum page 214-242 and answer the following questions. This is a longish reading assignment, so budget your time. 1) Why is this topic worth studying even if you don't care about page replacement? 2) What is the (impossible) optimal algorithm? 3) Why would we expect NRU to be a good heuristic? 4) Why do unmodified pages make good victims? Note: it is potentially confusing to say that a modified page is written "back" to disk, because in many cases the page has never been on the disk. 5) Does FIFO sound like a good idea to you? 6) What is the "second chance" idea? 7) What is the biggest drawback of LRU? 8) What is the motivation behind NFU and aging? 9) What is the motivation for Working Set? (don't get hung up in the details) 10) What factors does WSClock take into account in choosing a victim? Skip Section 4.5 In Section 4.6 1) What is the difference between global and local page replacement? 2) What is PFF? 3) What is thrashing and how would load control help (if it existed)? 4) What are the pros and cons of large pages? 5) What is the point of having a separate address space for instructions and data? Does this idea have a future? 6) Why might a programmer want an API to control the page table? Why not just let programs write their own page tables?