Outline for EECS 678 with Professor Kulkarni at KU 4
Outline for EECS 678 with Professor Kulkarni at KU 4
Popular in Course
Popular in Department
This 46 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Kansas taught by a professor in Fall. Since its upload, it has received 20 views.
Reviews for Outline for EECS 678 with Professor Kulkarni at KU 4
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
5 Memory Management Outline I Background l Swapping l Contiguous Memory Allocation l Paging l Segmentation l Segmented Paging EECS 678 Introduction to Operating Systems 7 Spn39ng 2009 5 Background l Memory is a large array of bytes 0 memory and registers are only storage CPU can access directly 0 both instructions and data are fetched from memory 0 memory unitjust sees a stream on memory addresses l Accessing memory is slow why 0 register access in one CPU clock or less 0 cache sits between main memory and CPU registers l Protection of memory required to ensure correct operation 0 isolate processes from one another and from the OS EECS 678 Introduction to Operating Systems 7 Sp ng 2009 3 Process Protection in Hardware l Protect OS from user processes and processes from each other operating 0 give each process separate space System 0 determine legal range of addresses 256000 for each process Process l A pair of base and limit 300040 300040 registers define the process process base address space 420940 120900 l CPU compares each address generated by the process with process the base and limit registers limit 880000 1024000 EECS 678 Introduction to Operating Systems 7 Spring 2009 3 5 Address Binding l Address binding of instructions and data to memory addresses can happen at three different stages 0 compile time If memory location known a priori absolute code can be generated gt must recompile code if starting location changes 0 load time Must generate relocatable code if memory location is not known at compile time gt code can be placed anywhere in memory 0 execution time Binding delayed until run time if the process can be moved during its execution from one memory segment to another gt need hardware support for address maps eg base and limit registers EECS 678 Introduction to Operating Systems 7 Sp ng 2009 4 Mllultistep Processing of User Program SOU FEE program compller or sumpile assembler tlme object module other object modules Ilnkage edlmr load load module lime system library loader dynamrcall loaded 1 system library ln rnemory V dynam lo binary 53 linking memory mm lmage EECS 678 Irmoduaion to Operating Systems 7 Spring 2009 5 Logical vs Physical Address Space l The concept of a logical address space that is bound to a separate physical address space is central to proper memory management 0 logical address generated by the CPU also referred to as virtual address 0 physical address address seen by the hardware memory unit I Logical and physical addresses are the same in compile time and loadtime addressbinding schemes l Logical and physical addresses differ in executiontime addressbinding scheme EECS 678 Introduction to Operating Systems 7 Sp ng 2009 6 39 MemoryManagement Unit MMU I Hardware device that maps virtual to physical address I Simple MMU scheme start each process39s logical address from 0 base memory address for each process stored in relocation register max process address stored in limit register relocation register added to every logical address logical O max correspond to physical RO Rlimit CPU logical address relocation register 14000 physical address 346 G MMU EECS 678 Introduction to Operating Systems 7 Spring 2009 1 4346 memory Dynamic Loading I Static loading 0 entire program in memory before program starts program size limited by size of memory I Dynamic loading routine is not loaded until it is called better memoryspace utilization unused routine is never loaded useful when large amounts of code are needed to handle infrequently occurring cases no special support from the operating system is required implemented through program design EECS 678 Introduction to Operating Systems 7 Sp ng 2009 5 Dynamic Linking l Static linking 0 library modules considered as any other object files 0 linkerloader combines libraries into every binary image in which they may be referenced 0 multiple copies of library code may reside in memory at a time I Dynamic linking O linking postponed until execution time 0 small piece of code stub used to locate the appropriate memory resident library routine stub replaces itself with the address of the routine OS checks if routine is in processes memory address only one copy of libraries resident in memory at a time such a library is called a shared library EECS 678 Introduction to Operating Systems 7 Sp ng 2009 9 5 Swapping I What is swapping 0 moving a process currently resident in memory to a backing store and swapping another process into the freed space 0 swap individual pages of the same process inout of memory I When is swapping needed 0 if there is no free memory for the new process dispatched by the scheduler 0 if some process needs more physical memory than is available I Backing store is generally maintained on disk 0 swapping is costly 0 if swapped out memory needs to be brought back in immediately all the time then it will lead to memory thrashing I See 39top39 and 39swapon s39 under Linux EECS 678 Introduction to Operating Systems 7 Sp ng 2009 10 Schematic View of Swapping ope rating system process P1 process P2 user space backing store main memory EECS 678 Introduction to Opemling Systems 7 Spring 2009 Contiguous Memory Allocation l Efficient allocation of main memory is important 0 memory is limited in size 0 contains the OS and multiple concurrently active user processes I Main memory usually divided into two partitions o resident operating system usually held in low memory with interrupt vector 0 user processes then held in high memory I Contiguous memory allocation 0 each process in a single contiguous region of memory 0 allows multiple processes to reside in memory at the same time o processes must be protected from each other EECS 678 Introduction to Operating Systems 7 Sp ng 2009 12 g Hardware Support for Protection I Relocation and limit registers used to protection 0 of user processes from each other and 0 operating system from the user processes I Hardware checks 0 base register contains value of smallest physical address 0 each logical address must be less than the limit register 0 MMU maps logical address dynamically limit relocation register register logical l physical address yes address CPU lt memory no trap addressing error EECS 678 Introduction to Operating Systems 7 Spring 2009 13 g Contiguous Memory Allocation 2 l Multiplepartition method 0 hole block of available memory gt holes of various size are scattered throughout memory 0 when a process arrives it is allocated memory from a hole large enough to accommodate it 0 operating system maintains information about a allocated partitions b free partitions hole OS OS OS OS process 5 process 5 process 5 process 5 process 9 process 9 process 8 gt gt gt process 10 process 2 process 2 process 2 process 2 EECS 678 Introduction to Operating Systems 7 Sp ng 2009 14 Dynamic StorageAllocation Problem I Given a list of variablesized holes how to allocate memory for a new arrivmg process of some snze n l Memory allocation schemes 0 Firstfit Allocate the rst hole that is big enough 0 Bestfit Allocate the smallest hole that is big enough must search entire list unless ordered by size gt produces the smallest leftover hole 0 Worstfit Allocate the largest hole must also search entire list gt produces the largest leftover hole I Performance 0 firstfit and bestfit better than worstfit in terms of performance and storage requirement 0 firstfit generally the fastest EECS 678 Introduction to Operating Systems 7 Sp ng 2009 15 5 Fragmentation l External Fragmentation total memory space exists to satisfy a request but it is not contiguous l 50percent rule 0 given N allocated blocks 05N blocks will be lost to fragmentation l Solutions to external fragmentation o compaction gt move allocated blocks to place all holes together gt compaction is possible only if relocation is dynamic 0 permit noncontiguous allocation of logical address space I Internal Fragmentation 0 occurs with fixed sized blocks used to reduce cost of managing extremely small holes 0 size of last block may be slightly larger than requested memory 0 what is the greatest memory loss due to internal fragmentation EECS 678 Introduction to Operating Systems 7 Sp ng 2009 16 5 Paging l Solution to external fragmentation and compaction O logical address space of a process can be noncontiguous O commonly used in most 08 O frequently depend on hardware support I Scheme 0 divide physical memory into fixedsized blocks called frames gt size is generally power of 2 between 512 bytes and 8192 bytes 0 divide logical memory into blocks of same size called pages 0 08 keeps track of all free frames 0 a program of size n pages needs n free frames before loading 0 needs a page table to translate logical to physical addresses l Problem of internal fragmentation still exists EECS 678 Introduction to Operating Systems 7 Sp ng 2009 17 Address Translation Scheme l Hardware defines the page size and frame size I Page size d determines the number of bits required to specify the page offset n o How 0 d 2n l The remaining bits in the logical address specify the page number p I For logical address space 2m and page size 2 page number page offset p d mn I7 EECS 678 Introduction to Operating Systems 7 Sp ng 2009 18 Paging Hardware logical physical address address fOOOO 0000 CPU gt p d f d gt f1111 1111 p i physical page table memory EECS 678 Introduction to Operating Systems 7 Spring 2009 Paging Model of Logical and Physical Memory frame number pageO 0 0 1 page1 1 4 1 pageo 2 3 pagez 2 3 7 page3 page table 3 pagez logical 4 page1 memory 5 6 7 pages physical memory EECS 678 Introduction to Opemling Systems 7 111ng 2009 20 Paging Example 0 a 1 b 32byte memory and 4byte pages 0 2 c 3 d 4 e 4 i 5 f j 6 g D 5 k 7 h 1 6 I 8 i 2 1 s m 9 j n 10 k 3 2 o 11 pagetable p 12 m 12 13 n 14 a 15 p 1ogical memory 16 20 a b C 1 54 1 21 24 g h 3919 28 EECS 678 11111001121101 to Operaung Systems 7 Spnng 2009 freeframe list 14 13 18 a Before allocation Free Frames 13 14 15 16 17 18 19 2O 21 freeframe list 15 new process page table 10 13 14 15 16 17 18 19 2O 21 After allocation EECS 678 Introduction to Operating Systems 7 Spring 2009 page 1 page 0 page 2 page 3 5 Page Table Issues l Small or large page size 0 small page size reduces internal fragmentation loss how 0 large page size reduces size of page table how 0 larger transfers produces more efficient disk transfers l Each memory loadstore goes through page table 0 page table access must be fast 0 store page tables in hardware registers 0 only possible for small tables up to 256 entries I Each process has its own page table 0 page table switching on each context switch must be fast I Most computers allow large page tables 0 page table is kept in main memory 0 single register points to page table address in memory EECS 678 Introduction to Operating Systems 7 Sp ng 2009 23 E Page Table Implementation l Pagetable base register PTBR points to page table 0 only this register affected on each context switch I Every loadstore requires two memory accesses 0 one for the page table and one for the datainstruction l Translation lookaside buffer TLB 0 cache to hold popular page table entries 0 access to TLB should be very fast use associative cache l However each process has its own page table 0 on a context switch 08 changes PTBR pointer o and may need to purge the TLB 0 use addressspace identifiers ASle in each TLB entry gt uniquely identifies each process to provide addressspace protection for that process EECS 678 Introduction to Operating Systems 7 Sp ng 2009 24 a Paging Hardware With TLB CPU logical address p d page frame number number TLB hit physical address V f d TLB p TLB miss f physical memory page table EECS 678 Introduction to Operating Systems 7 111ng 2009 25 Memory Protection l Memory protection implemented by associating protection bit with each frame I Validinvalid bit attached to each entry in the page table 0 valid indicates that the associated page is in the process logical address space and is thus a legal page 0 invalid indicates that the page is not in the process logical address space EECS 678 Introduction to Operating Systems 7 Sp ng 2009 26 as l Scheme 0 14 bit address space 0 Program uses addresses 0 10468 Page size of 2kb Accessing addresses on pages 6 and 7 is invalid gt segmentation fault I Problems 0 addresses 10469 12287 are still valid 0 page table still contains all rows 0 use page table length register 00000 10468 12287 page 0 page 1 page 2 page 3 page 4 page 5 Memory Protection 2 frame number valid invalid bit OOmV WN 39 ltltltltltlt 39 IOVU39lgtml LO 0 page table EECS 678 Introduction to Operating Systems 7 Spring 2009 page 0 page 1 page 2 page 3 page 4 page 5 page n 27 a l Shared code 0 Paging allows the possibility of easily sharing code 0 one copy of read only reentrant code shared among processes ie text editors compilers window systems 0 each process has private data 0 significant reduction in memory usage possible I Example 0 3 code pages shared 0 each process has private data EECS 678 Introduction to Operating Systems 7 Spring 2009 ed1 Shared Pages 3 ed 2 4 ed 3 6 1 data 1 page table for P1 process F 1 ed 1 3 ed 2 4 ed 3 6 2 data 3 page table for P3 process F A ed1 data 1 data 3 ed1 ed2 ed2 lmbm ed3 data 2 page table for P2 process P2 10 11 eds data 2 28 39 Structure of the Page Table l Hierarchical Paging l Hashed Page Tables I Inverted Page Tables EECS 678 Introduction to Operating Systems 7 Sp ng 2009 29 Hierarchical Page Tables I Sometimes necessary to divide page table into pieces 0 to support a large logical address space 232 to 264 0 example for page size of 4kb page table has 220 entries 0 contiguous allocation of big page tables not feasible l Twolevel page table paged pagetable 0 further divide the page number field 0 p1 index into outer page table 0 p2 displacement within outer page table page number page offset pi p2 d 10 10 12 EECS 678 Introduction to Operating Systems 7 Sp ng 2009 30 J TwoLevel PageTable Scheme O M 100 500 500 708 39 708 outerpage 929 2 table 900 900 gtlt 5 pageof 929 page table page table memory EECS 678 Introduction to Operating Systems 7 Spring 2009 AddressTranslation Scheme for TwoLevel Paging logical address P1 Pad pi M outer page table d page of page table EECS 678 Introduction to Operating Systems 7 Spring 2009 31 More Levels in Hierarchical Mapping l Two level scheme not appropriate for 64bit machine 0 divide the outer page table further outer page inner page offset 2nd outer page outer page inner page offset P1 P2 d P1 P2 P3 d 42 10 12 32 10 10 12 l Even threelevel scheme is daunting O outer page table still 234 bytes in size I We can go on increasing the number of paging levels 0 but each level requires a memory access 0 twolevel page table requires three memory accesses for each loadstore o nlevel requires n1 memory accesses 0 need another page table implementation EECS 678 Introduction to Operating Systems Spring 2009 33 Hashed Page Tables I Common in address spaces gt 32 bits 0 virtual page number is the hash l Each hash table entry contains a linked list of elements I Each element contains 0 virtual page number 0 value of mapped page frame 0 next pointer l Algorithm 0 hash virtual page number into hash table 0 compare with each element in linked list until match is found I use corresponding page frame to form physical address EECS 678 Introduction to Operating Systems 7 Sp ng 2009 34 g9 Hashed Page Tables 2 physical logical address address p d r d gt gt 3383 hash table EECS 678 Introduction to Operating Systems 7 Spring 2009 5 Inverted Page Table l Attempt to overcome drawbacks of traditional page tables 0 machines with large virtual address spaces have huge tables 0 consume lot of memory I Inverted page table approach 0 table contains one entry for each real page of memory 0 entry consists of the virtual address of the 0 also contains information on process that owns that page 0 see figure on next page I Decreases memory needed to store each page table but 0 linear search of table needed to find physical mapping 0 substantial increase in search time for every memory access 0 Use hash table to limit the search to one or few pagetable entries EECS 678 Introduction to Operating Systems 7 Sp ng 2009 36 Inverted Page Table 2 physical memory logical address physlcal address CPU pid p d i d gt searchl i J Pid P pagetable EECS 678 Introduction to Operating Systems 7 Spring 2009 Segmentation l Memorymanagement scheme that supports user view of memory 0 a program is a collection of segments subroutine 4 main 3 program user space physical memory space logical address EECS 678 Introduction to Operating Systems 7 Spring 2009 38 Segmentation Architecture l Logical address consists of a two tuple ltsegment number offsetgt l Segment table maps twodimensional physical addresses each table entry has 0 base contains the starting physical address where the segments reside in memory 0 limit specifies the length of the segment I Segmenttable base register STBR points to the segment table s location in memory I Segmenttable length register STLR indicates number of segments used by a program segment number sis legal ifs lt STLR EECS 678 Introduction to Operating Systems 7 Sp ng 2009 39 g5 Segmentation Architecture 2 limit base segment table CPU gt s V trap addressing error physical memory EECS 678 Introduction to Operating Systems 7 Spring 2009 Example of Segmentation subroutine stack 1400 segment 3 Segmen1 0 2400 symbol segment 0 table limit base sq segment 0 1000 1400 1 400 5300 3200 main 2 400 4300 program 3 1100 3200 segmenta 4 1000 4700 segment table 4300 segment 1 segment 2 segment 2 4700 logical address space segment 4 5700 6300 segment 1 6700 thsical memorv EECS 678 Introduction to Operating Systems 7 Spring 2009 5 Example The Intel Pentium l Supports both segmentation and segmentation with Paging l CPU generates logical address 0 given to segmentation unit gt which produces linear addresses 0 linear address given to paging unit gt which generates physical address in main memory gt paging units form equivalent of MMU logical CPU address gt segmentation unit linear address Paging physical address physical unit EECS 678 Introduction to Operating Systems 7 Spring 2009 memory 42 Intel Pentium Segmentation 32bit architecture Max number of segments 16K 0 8k segments in local descriptor table LDT 0 8k segments in global descriptor table GDT Max size of segment 4GB Each segment descriptor is 8 bytes 0 contains segment base and limit Each logical address is 48 bits 0 16 bit segment selector 32 bit offset 16 bit segment selector contains 0 13 bit segment number 1 bit table identifier 2 bits of protection Maps 48 bit logical address to 32 bit linear address EECS 678 Introduction to Operating Systems 7 Sp ng 2009 43 5 Intel Pentium Segmentation 2 logical address selector offset descriptor table segment descriptor 82bit linear address EECS 678 Introduction to Operating Systems 7 SpIing 2009 6 Pentium Paging Architecture I Page size 4kb or 4mb I For 4kb pages two level paging scheme page number page offset P1 P2 d 10 10 12 0 base of page directory pointed to by CR3 register 0 10 highorder bits offset into the page directory 0 page directory gives base of inner page table 0 inner page table indexed by middle 10 bits of linear address 0 page table returns base of page 0 loworder 12 bits of linear address used to offset page EECS 678 Introduction to Operating Systems Spring 2009 45 5 Pentium Paging Architecture 2 logical address page directory I page table offset 31 22 21 l 12 11 0 page 4 KB table gt page page directory CR gt 4 MB register page page directory I offset 31 22 21 O EECS 678 Introduction to Operating Systems 7 Spring 2009
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'