Class Note for EECS 678 with Professor Kulkarni at KU
Class Note for EECS 678 with Professor Kulkarni at KU
Popular in Course
Popular in Department
This 12 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 18 views.
Reviews for Class Note for EECS 678 with Professor Kulkarni at KU
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
09 Memory Management Outline I Background I Swapping I Contiguous Memory Allocation I Paging I Segmentation I Segmented Paging EECS 678 Introduction to Operating Systems 7 Spring 2009 1 g Background I 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 unit just sees a stream on memory addresses I Accessing memory is slow why 0 register access in one CPU clock or less 0 cache sits between main memory and CPU registers I 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 Spring 2009 2 5 Process Protection in Hardware I Protect OS from user processes and processes from each other operating 0 give each process separate space 5mm 0 determine legal range of addresses 256000 for each process Process I A pair of base and limit 300040 300040 registers de ne the process process base address space 420940 120900 I CPU compares each address quotmquot generated by the process with Proms the base and limit registers 880000 1024000 EECS 678 Introduction to Operating Systems 7 Spring 2009 3 05 Address Binding I 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 Spring 2009 4 Wultistep Processing of User Program source program compiler or assembler compile lime object module linkage editor load module loader load time system library dynamicall loaded system bra39y inmemory dynamic binary linking memory It image we EECS 678 Introduction to Operating Systems Spring 2009 5 3 Logical vs Physical Address Space I 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 I physical address address seen by the hardware memory unit I Logical and physical addresses are the same in compile time and loadtime addressbinding schemes I Logical and physical addresses differ in executiontime addressbinding scheme EECS 678 Introduction to Operating Systems Spring 2009 3 MemoryManagement Unit MMU I Hardware device that maps virtual to physical address I Simple MMU scheme I start each process39s logical address from 0 9 14000 0 base memory address for each logical physrcal process stored in relocation address A address CPU t register memory 346 U 14346 I max process address stored in limit register I relocation register added to every logical address 0440 o logical 0 max correspond to physical R0 Rlimit EECS 678 Introduction to Operating Systems Spring 2009 7 15 Dynamic Loading I Static loading 0 entire program in memory before program starts I program size limited by size of memory I Dynamic loading I routine is not loaded until it is called 0 better memoryspace utilization unused routine is never loaded I useful when large amounts of code are needed to handle infrequently occurring cases I no special support from the operating system is required implemented through program design EECS 678 Introduction to Operating Systems Spring 2009 5 Dynamic Linking l Static linking library modules considered as any other object files linkerloader combines libraries into every binary image in which they may be referenced multiple copies of library code may reside in memory at a time I Dynamic linking linking postponed until execution time small piece of code stub used to locate the appropriate memory resident library routine stub replaces itself with the address ofthe 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 Spring 2009 9 9 I What is swapping 0 moving a process currently resident in memory to a backing store and swapping another process into the freed space Swapping O swap individual pages ofthe same process inout of memory I When is swapping needed 0 if there is no free memory forthe new process dispatched by the scheduler o 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 Spring 2009 1 Schematic View of Swapping ope rating system user space backing store main memory EECS 678 Introduction to Operating Systems 7 Spring 2009 11 g5 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 0 processes must be protected from each other EECS 678 Introduction to Operating Systems 7 Spring 2009 12 a 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 15 Contiguous Memory Allocation 2 I Multiple partition 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 limit relocation register register OS OS OS OS 1 1 process 5 process 5 process 5 process 5 logical physical address yes address Process 9 Process 9 GPU gtlt lt memory process 8 gt gt gt process 10 no process 2 process 2 process 2 process 2 trap addressing error EECS 678 Introduction to Operating Systems 7 Spring 2009 13 EECS 678 Introduction to Operating Systems 7 Spring 2009 14 ynamic StorageAllocation Problem Fragmentation I Given a list of variable sized holes how to allocate memory for a new arrIVIng process of some size n I 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 rst t and best t better than worst t in terms of performance and storage requirement 0 rst t generally the fastest EECS 678 Introduction to Operating Systems 7 Spring 2009 15 I External Fragmentation total memory space exists to satisfy a request but it is not contiguous I 50 percent rule 0 given N allocated blocks 05N blocks will be lost to fragmentation I 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 non contiguous allocation of logical address space I Internal Fragmentation 0 occurs with xed 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 Spring 2009 15 sf Paging l Solution to external fragmentation and compaction o logical address 0 commonly used 0 frequently depe l 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 OS keeps track space of a process can be noncontiguous in most OS nd on hardware support 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 Spring 2009 17 9 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 2 and page size 2 page number page offset 12 mn I7 EECS 678 Introduction to Operating Systems 7 Spring 2009 18 r9 Paging Hardware logical address Pl CPU gtlp IIEI physical address fOOOO 0000 f1111 1111 physical memory page table EECS 678 Introduction to Operating Systems 7 Spring 2009 19 s Paging Model of Logical and Physical Memory frame number page 0 0 page 1 1 page 0 page 2 2 page 3 page table 8 page 2 logical 4 page 1 memory 5 6 7 page 3 physical memory EECS 678 Introduction to Operating Systems 7 Spring 2009 20 a Paging Example o a 1 b 32byte memoryand 4byte pages 0 2 c 3 d 4 e 4 i 2 f o I 9 k 7 h 1 l a i 2 8 m 9 j n 10 k 3 o 11 l pagetable p 12 m 12 13 n 14 o 15 p logical memory 16 b c 1 564144 21 24 f 9 h 28 10 f2 physical memory EECS 678 Introduction to Operating Systems 7 Spring 2009 21 5 Free Frames freeframe list 15 free frame list o 1 2 3 newprocess page table a 13 Before allocation After allocation EECS 678 Introduction to Operating Systems 7 Spring 2009 22 3 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 ef cient 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 Spring 2009 23 g 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 Spring 2009 24 logical address CPU Page frame number number TLB p TLB miss TLB hil llell page table Paging Hardware With TLB physical address physical memory EECS 678 Introduction to Operating Systems 7 Spring 2009 25 5 Memory Protection I 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 Spring 2009 t I Scheme 0 14 bit address space 0 Program uses addresses 0 10468 0 Page size of 2kb o 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 validinvalid bit page table EECS 678 Introduction to Operating Systems 7 Spring 2009 page 0 3 page 1 page 2 27 a I Shared code 0 Paging allows the possibility of easily sharing code Shared Pages 0 one copy of readonly reentrant code shared among processes datai pagegbie 1 Le text editors compilers process or 1 window systems 0 each process has private data 0 signi cant reduction in memory usage possible a I Example 912 O 3 code pages shared as 0 each process has private data dams pagmbye f P process PR or a EECS 678 Introduction to Operating Systems 7 Spring 2009 edi ed2 ed3 data 2 process F 2 page table lor F 2 n l Hierarchical Paging l Hashed Page Tables I Inverted Page Tables Structure of the Page Table EECS 678 Introduction to Operating Systems 7 Spring 2009 if I Sometimes necessary to divide page table into pieces 0 to support a large logical address space 232 to 254 Hierarchical Page Tables 0 example for page size of 4kb page table has 22 entries o 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 1 0 1 0 1 2 EECS 678 Introduction to Operating Systems 7 Spring 2009 30 g9 TwoLevel PageTable Scheme 500 E 708 outer page table o 929 900 page of page table page table 929 memorv EECS 678 Introduction to Operating Systems 7 Spring 2009 sf AddressTranslation Scheme for TwoLevel Paging logical address P1 El pt P2 outer page d table page of page table EECS 678 Introduction to Operating Systems 7 Spring 2009 32 More Levels in Hierarchical Mapping l Two level scheme not appropriate for 64bit machine 0 divide the outer page table further outer page I inner page I offset 2nd outerpagel outerpage linnerpagel offset i m p2 d m i 92 m i 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 7 Spring 2009 33 t l 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 0 use corresponding page frame to form physical address Hashed Page Tables EECS 678 Introduction to Operating Systems 7 Spring 2009 34 t9 Hashed Page Tables 2 physical address El logical address physical memory w gtqisirhpiriiT hash table EECS 678 Introduction to Operating Systems 7 Spring 2009 35 39 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 Spring 2009 36 a Inverted Page Table 2 logical address physical address CPU ipid 0 l dl search i pidl p page table EECS 678 Introduction to Operating Systems 7 Spring 2009 lild y physical memory 37 it Segmentation l Memorymanagement scheme that supports user view of memory 0 a program is a collection of segments subroutine main program user space physical memory space logical address EECS 678 Introduction to Operating Systems 7 Spring 2009 38 g9 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 numbers is legal ifs lt STLR EECS 678 Introduction to Operating Systems 7 Spring 2009 39 5E Segmentation Architecture 2 limit base segment table CPU 5 l39lO v trap addressing error physical memory EECS 678 Introduction to Operating Systems 7 Spring 2009 40 a subroutine stack segment 3 symbol segment 0 table limit base segment 4 c sq 1000 400 400 1100 1000 main program a w M 7 1 400 6300 4300 3200 4700 segment 1 segment 2 logical address space segment table Example of Segmentation 1400 segment 0 2400 3200 segment a 4300 segment 2 4700 segment 4 5700 6300 segment 1 G700 thsical memory EECS 678 Introduction to Operating Systems 7 Spring 2009 41 1 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 address segmentation CPU unit linear address Paging unit physical address physical memory EECS 678 Introduction to Operating Systems 7 Spring 2009 9 l 32bit architecture I Max number of segments 16K 0 8k segments in local descriptor table LDT Intel Pentium Segmentation 0 8k segments in global descriptor table GDT l Max size of segment 4GB l Each segment descriptor is 8 bytes 0 contains segment base and limit I Each logical address is 48 bits 0 16 bit segment selector 32 bit offset l 16 bit segment selector contains 0 13 bit segment number 1 bit table identi er 2 bits of protection I Maps 48 bit logical address to 32 bit linear address EECS 678 Introduction to Operating Systems 7 Spring 2009 43 55 Intel Pentium Segmentation 2 logical address selector descriptor table segment descriptor offset 32bit linear address EECS 678 Introduction to Operating Systems 7 Spring 2009 E I Page size 4kb or 4mb I For 4kb pages two level paging scheme page number Pentium Paging Architecture I page offset P1 P2 d 1 O 1 O 1 2 base of page directory pointed to by CR3 register 1 O high order bits offset into the page directory page directory gives base of inner page table inner page table indexed by middle 10 bits of linear address page table returns base of page low order 12 bits of linear address used to offset page EECS 678 Introduction to Operating Systems 7 Spring 2009 45 E Pentium Paging Architecture 2 logical address I page directory I page table 1 offset 31 22 21 l 12 11 l o Page 4 KB V table page page directory ORB gt 4 MB reglster page page directory offset 1 31 EECS 678 Introduction to Operating Systems 7 Spring 2009 l 22 21 O 46
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'