Class Note for CMPSCI 377 at UMass(47)
Class Note for CMPSCI 377 at UMass(47)
Popular in Course
Popular in Department
This 3 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 22 views.
Reviews for Class Note for CMPSCI 377 at UMass(47)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
CMPSCI 377 Operating Systems Paging and Virtual Memory ln modern operating systems applications do not access physical memory directly instead they use virtual memory Each application has the illusion of having the whole address space to itself starting from address 0 to 2GB or more Notice that while programs manage memory at the level of bytes the OS manages the memory in groups of bytes called pages typically of 4kB or SkB in size Handling memory in uniformly sized chunks makes it easier to manage the whole memory think of playing Tetris with all squaresi Both the virtual and the physical memory are treated this way ie by being divided into pages To keep the discussion unambiguous we generally refer to virtual pages as pages and physical pages as page frames or simply as framesi Every virtual page has a virtual address which is mapped to a page frame in the physical RAMi When some application needs to access a virtual page the system translates its virtual address into a real physical address and then the actual data might be read andor written Notice that some virtual pages do not map to any actual physical memory address because not all virtual pages are necessarily being used at any given time these unused virtual pages are called invalidi If a program ever tries to access an invalid page the CPU traps to the operating system causing a Segmentation Fault or Access Violationi 1 So far we only know that virtual memory is somehow mapped into physical memory But why do we need virtual memory Some of the reasons for using it are the following 0 Each individual program to have the illusion of having the whole address space for itself 0 The address space used by each process is isolated from other applications iiei applications cannot damage other applications Notice that since each program thinks it has the whole memory to itself programs can use a lot of virtual memory in fact a computer might use huge amounts of virtual memory much more than the amount of actual physical memory available Of course this is no magic trick Using much more virtual memory than actual physical RAM works because in practice processes use only a small portion of their virtual address space lf however all processes suddenly decide to use more virtual memory than can be mapped into physical memory then we need to use some other mechanism such as paging discussed later Typical operating systems use a virtual address space layout which includes a stack a mmap region a heap and the programs coder Because the stack grows towards the heap if the program calls a recursive function too deeply the stack could over ow into the heap region which will generally cause the program to crash 201 The Memory Management Unit MMU When a program issues a memory load or store operation the virtual addresses VAs used in those operations have to be translated into real physical memory addresses PAS The MMU Memory Management Unit a portion of the CPU performs these translations The MMU uses a page table eigi big hash table that maps VAs into PAsi Since memory accesses happen all the time the MMU must be really fast and is thus 1Notice that although arrays are contiguous in virtual memory parts of it can be mapped into nonecontiguous physical memory addresses 21 22 Chapter 2 Paging and Virtual Memory implemented in hardware Notice however that mapping every single byte of virtual memory to a physical address would require a huge page table one entry per byte of virtual address space lnstead the MMU maps virtual pages to physical pages Also since we want to isolate each program s address space from other applications address spaces the MMU must keep a separate page table for each process Thus multiple different processes use the same virtual address to refer to their own data which is not a problem since these addresses would be mapped into different physical addresses The page table also marks all virtual pages that are allocated and therefore are being used so that it is possible to know which ones pages have valid mappings into PAs Virtual pages that are not being mapped into a physical address are marked as invalid a CPU exception occurs when a program tries to reference or access a virtual address that is not valid Besides valid bits entries in the page table also store lots of other information such as read and write bits to indicate which pages can be readwritten 202 Virtual addresses Virtual addresses are made up of two parts the rst one contains a page number and the second one contains an offset inside that page Suppose our pages are 4kB 4096 bytes long and that our machine uses 32 bit addresses Then we can have at most 232 addressable bytes of memory therefore we could t at most 232212 220 pages This means that we need 20 bits to address any single page Thus the rst part of the virtual address is formed by its 20 most signi cant bits These bits are used to index into the page table The 32 7 20 12 least signi cant bits of the VA are used as an offset inside the page Of course with 12 bits of offset we can address 212 4096 bytes which is exactly what we expect in order to address every byte inside our 4kB pages 203 Page Table Structure Each process has its own separate page table A page table with 220 entries each entry consuming 4 bytes requires 4MB of memory While this seems like very little on modern machines with gigabytes of RAM a system with 80 processes would need more than 300 megabytes just for storing page tables Modern systems solve this problem by using multi level page tables This approach hierarchically divides the virtual address space so that the rstlevel table points to secondlevel tables and so on Previously we described a llevel system which split the virtual address into two parts Consider a 2level system which divides the VA into three parts an offset into the page 12 bits a levell page table index 10 bits and a level0 page table entry 10 bits Then if we use the 10 most signi cant bits of a virtual address we obtain an index in the level0 page table if we follow the pointer given by that entry we get a pointer to a levell page table The entry to be accessed in this page table is given by the middle 10 bits of the virtual address We can again follow the pointer speci ed on that levell page table entry and nally arrive at a physical page The last 10 bits of the VA gives us the offset within that frame Using this structure the system consumes much less physical memory to store page tables for processes which consume small amounts of virtual address space For example a process which maps only a single virtual page needs 210 1024 bytes of memory for its level0 page table and another 1024 bytes for a single levell page table in this case only one entry in the Olevel table is used the rest of the entires are invalid and do not point to levell tables What about 64bit systems If the system used at tables it would require 252 entries in the page table Even if a twolevel scheme were used the level0 index would require 64 7 10 7 l2 42 bits thus requiring a 242 entry tablel Thus 64 bit systems use page tables with higher depth eg 4 level tables A drawback of using this hierarchical approach is that for every load or store instruction we have to perform Chapter 2 Paging and Virtual Memory 23 several indirections which of course makes everything slowerl Modern systems reduce this overhead by several orders of magnitude using something called the Translation Lookaside Buffer TLB The TLB is a fast fully associative memory that caches mappings from virtual page numbers to physical frame numbersl Typically TLBs can cache from 8 to 2048 page table entries Some systems such as IBM s Power4 have 2level TLBs similar to having L1 and L2 caches in the CPU for memory Finally notice that if the total virtual memory in use ie the sum of the virtual memory used by all processes is larger than the physical memory the OS must put some of the excess somewhere In this case the disk is used to store memory pages that must be removed to make room for other active pages We call this page eviction When these pages are accessed again the OS restores them to physical RAM from the disk possibly evicting other pages If processes continually access pages swapped to disk then the system will spend most of its time moving data around from RAM to disk This situation is called thrashing as the system does lots of work but makes no useful progressl
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'