CSE 120 Principles of Operating Systems Lecture 7 Memory Management October 16 2003 Prof Joe Pasquale Department of Computer Science and Engineering University of California San Diego 2003 by Joseph Pasquale 1 Before We Begin Read Chapter 9 on Memory Management Midterm is on Tuesday of next week 2 What We Know So Far Goal run multiple programs simultaneously process abstraction of program in execution programmer need not deal with multiplexing CPU P1 P2 P3 P1 P2 P3 Process encapsulates more than CPU time e g memory 3 Sharing the Physical Memory When process is given CPU must also be in memory Problem context switching time CST 10 sec loading from disk 10 MB s to load 1 MB process 100 msec 10 000 x CST Solution keep multiple processes in memory Keep as many processes in memory as possible Context switch select only processes in me 4 Logical vs Physical Views P1 P1 P2 P2 Logical P3 P3 P2 P1 Physical P1 P2 P3 P3 5 Memory Management How to manage space of physical memory Allocate by partitioning into chunks one or more chunks per process Free by deallocating chunks and coalescing if necessary Rearrangement compaction move chunks leaving one free chunk spreading chunks so each has more space to grow 6 Memory Partitioning Fixed static vs variable dynamic equal vs non equal Fragmentation internal vs external Fixed Equal Fixed Non equal Variable Non equal 7 Placement Algorithms First fit Next fit Best fit Worst fit Compaction Internal external fragmentation Fixed Non equal Variable Non equal 8 The Buddy System Dynamically partition in powers of 2 size chunks Allocation given request for size r find smallest chunk while r sizeof chunk 2 divide chunk into 2 buddies each of 1 2 size select one Deallocation free the chunk while buddy is also free Coalesce 9 Example of Buddy System Alloc A 900 KB Alloc B Alloc C Free B Free A 1 2 MB 1 5 MB 2 MB 4 MB 2 MB A A A A 1 MB 1 MB 1 MB 1 MB 1 MB 1 MB 2 MB B B 2 MB 2 MB 2 MB C C C C C 2 MB 2 MB 2 MB 2 MB 2 MB 2 MB 4 MB 8 MB 4 MB 4 MB 4 MB 4 MB 10 Data Structure for Buddy System Alloc A 900 KB 8 MB 4 MB 4 MB 4 MB 2 MB 2 MB 11 Data Structure for Buddy System Alloc A 900 KB Alloc B 1 2 MB 4 MB 4 MB 2 MB A 1 MB B A 1 MB 12 Data Structure for Buddy System Alloc C 1 5 MB B A C 2 MB 1 MB 13 Data Structure for Buddy System Free B 2 MB A C 2 MB 1 MB 14 Data Structure for Buddy System Free A 2 MB 1 MB C 2 MB 1 MB 15 Data Structure for Buddy System Coalesce Coalesce 4 MB 2 MB 2 MB C 2 MB C 2 MB 16 Problems with Sharing Memory The Addressing Problem compiler generates memory refs unknown where process will be in P2 The Protection Problem modifying another process s memory P1 The Space Problem the more processes there are the less memory each have individually P3 17 Address Spaces Address space set of addresses for memory PAS 0 PM kernel Usually linear 0 to N 1 size N Physical Address Space 0 to N 1 N size kernel occupies lowest addresses typically N 1 18 Logical vs Physical Addressing Logical addresses assumes separate memory starting at 0 compiler generated independent of location in physical memory LASs LMs 0 N1 1 P1 PAS PM 0 P2 0 P2 P1 N2 1 Converting logical to physical S W at load time H W at access time 0 N3 1 P3 P3 N 1 19 Hardware for Logical Addressing Base register filled 0 with start address P2 Base To translate logical address add base Achieves relocation To move process change base P1 0 P2 P3 N2 1 N 1 20 Protection Bound register works 0 with base reg P2 Base Bound Check if address less than bound If so add to base If not invalid address trap P1 y n 0 P2 N2 1 P3 N 1 21 Memory Registers Part of Context On Every Context Switch Load base bound registers for selected process Only operating system does loading Kernel must be protected from all processes Benefit Allows each process to be separately located Protects each process from all others 22 Loading To create a process must load it into memory What to load the load module is based on program code data initialized and uninitialized stack keeps track of pending calls starts empty Absolute loading load to a fixed location in memory Relocatable loading load to a variable location dynamic run time loading allow location to change 23 Linking Take object modules create load module Linkage editor resolves inter object references Ex modules A and B A call f x where f x code is in B Dynamic linker defer linkages until load time resolve when load module is loaded run time resolve when referenced Ex wait until f x called to resolve address of f 24
View Full Document
Unlocking...