COMP 530 Operating Systems Memory Management Basics Don Porter Portions courtesy Emmett Witchel and Kevin Jeffay 1 COMP 530 Operating Systems Background Detour Splitting Numbers In elementary school one typically learns about the ones tens hundreds etc E g 13 24 can be modeled as 10 1 2 3 4 One can apply the same reasoning to space Room numbers in SN FB hundreds digit indicates the floor remaining digits indicate position within floor Street address lower 2 digits indicate house number upper digits indicate block Or an array of 10 byte sub arrays 0 1 2 3 4 5 6 7 8 9 0 10 20 30 40 2 Background Detour Splitting Numbers 2 0 1 2 3 4 5 6 7 8 9 COMP 530 Operating Systems 10 0 One could rename tens to index 20 30 40 E g byte 34 is in sub array index 3 One could rename ones to offset E g byte 34 is offset 4 in sub array 3 In this example address 34 becomes a tuple 3 4 In base 10 this is an intuitive concept We will use this in base 2 3 COMP 530 Operating Systems Splitting Numbers in Base 2 0 1 2 3 4 5 6 7 8 9 10 0 Same idea applies just need to split on powers of 40 20 30 two instead of ten Say we go to sub arrays of size 8 0 1 2 3 4 5 6 7 0 0x8 0x10 0x18 0x20 4 COMP 530 Operating Systems Why do we care We will see lots of variations on using modular arithmetic to calculate an index and offset in the next few lectures And why base 2 How data is carried on wires in chip Easier to implement modular arithmetic in base 2 Use cheap logical operators instead of expensive division When dividing if n is a power of two x n x log2 n x n x n 1 5 COMP 530 Operating Systems Review Address Spaces Physical address space The address space supported by the hardware Starting at address 0 going to address MAXsys Virtual address space A process s view of its own memory Starting at address 0 going to address MAXprog But where do addresses come from MOV r0 0xfffa620e Program P MAXsys MAXprog 0 0 COMP 530 Operating Systems Which is bigger physical or virtual address space A Physical address space B Virtual address space C It depends on the system COMP 530 Operating Systems Program Relocation Program issues virtual addresses Machine has physical addresses If virtual physical then how can we have multiple programs resident concurrently Instead relocate virtual addresses to physical at run time While we are relocating also bounds check addresses for safety I can relocate that program safely in two registers COMP 530 Operating Systems 2 register translation MAXsys MEMORY EXCEPTION Virtual Addresses CPUCPU no yes Physical Addresses 1500 1000 1000 Base 500500 Limit Register Register Program P s physical address space 1000 0 Instructions MAXprog Program Program P s P s virtual virtual address address space space 0 COMP 530 Operating Systems With base and bounds registers the OS needs a hole in physical memory at least as big as the process A True B False COMP 530 Operating Systems The Fragmentation Problem MAX External fragmentation Unused memory between units of allocation E g two fixed tables for 2 but a party of 4 Internal fragmentation Unused memory within a unit of allocation E g a party of 3 at a table for 4 Program Code Program Code text text Execution Stack Execution Stack DataData Execution Stack Execution Stack Program Q s PAS Program R s PAS 0 COMP 530 Operating Systems Dynamic Allocation of Partitions MAX Simple approach Allocate a partition when a process is admitted Allocate a contiguous memory partition to the into the system process OS keeps track of Full blocks Empty blocks holes Allocation strategies First fit Best fit Worst fit Program Program Program Program P1 P2 P3 P4 P5 0 COMP 530 Operating Systems First Fit Allocation To allocate n bytes use the first available free block such that the block size is larger than n 1K bytes 2K bytes 2K bytes To allocate 400 bytes we use the 1st free block available 500 bytes 500 bytes First Fit Rationale and Implementation COMP 530 Operating Systems Simplicity Requires Free block list sorted by address Allocation requires a search for a suitable partition De allocation requires a check to see if the freed partition could be merged with adjacent free partitions if any Advantages Simple Tends to produce larger free blocks toward the end of the address space Disadvantages Slow allocation External fragmentation COMP 530 Operating Systems Best Fit Allocation 1K bytes 1K bytes To allocate n bytes use the smallest available free block such that the block size is larger than or equal to n 2K bytes 2K bytes To allocate 400 bytes we use the 3rd free block available smallest 500 bytes COMP 530 Operating Systems Best Fit Rationale and Implementation Avoid fragmenting big free blocks To minimize the size of external fragments produced Requires Free block list sorted by size Allocation requires search for a suitable partition De allocation requires search merge with adjacent free partitions if any Advantages Works well when most allocations are of small size Relatively simple Disadvantages External fragmentation Slow de allocation Tends to produce many useless tiny fragments not really great COMP 530 Operating Systems Worst Fit Allocation 1K bytes 1K bytes To allocate n bytes use the largest available free block such that the block size is larger than n 2K bytes To allocate 400 bytes we use the 2nd free block available largest 500 bytes COMP 530 Operating Systems Worst Fit Rationale and Implementation Avoid having too many tiny fragments Requires Free block list sorted by size Allocation is fast get the largest partition De allocation requires merge with adjacent free partitions if any and then adjusting the free block list Works best if allocations Advantages are of medium sizes Disadvantages Slow de allocation External fragmentation Tends to break large free blocks such that large partitions cannot be allocated COMP 530 Operating Systems Allocation strategies First fit best fit and worst fit all suffer from external fragmentation A True B False COMP 530 Operating Systems Eliminating Fragmentation Compaction Relocate programs to coalesce holes MAX Program P1 Swapping Preempt processes reclaim their memory Ready Ready Running Running ready queue Waiting Waiting semaphore condition queues Suspended Suspended suspended queue Program P2 Program P3 P4 Program 0 COMP 530 Operating Systems Sharing Between Processes 2n 1 Schemes so far have considered only a single address space per process A single name space per process No sharing How can one share code and data between programs
View Full Document