1Lecture 7Memory ManagementOctober 16, 2003Prof. Joe PasqualeDepartment of Computer Science and EngineeringUniversity of California, San Diego© 2003 by Joseph PasqualeCSE 120: Principles of Operating Systems2Before We Begin …Read Chapter 9 (on Memory Management)Midterm is on Tuesday of next week3What We Know So FarGoal: run multiple programs “simultaneously”• process: abstraction of program in execution• programmer need not deal with multiplexing CPUProcess encapsulates more than CPU time, e.g., memoryP1P2P3P1P2P34Sharing the Physical MemoryWhen process is given CPU, must also be in memoryProblem• 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 me5Logical vs. Physical ViewsP1P2P3P2P1P3P1P1P2P2P3P3LogicalPhysical6Memory ManagementHow to manage space of (physical) memoryAllocate by partitioning into chunks• one or more chunks per processFree by deallocating chunks and coalescing if necessaryRearrangement• compaction: move chunks, leaving one free chunk• spreading chunks, so each has more space to grow7Memory PartitioningFixed/static vs. variable/dynamic, equal vs. non-equalFragmentation: internal vs. externalFixedEqualFixedNon-equalVariableNon-equal8Placement AlgorithmsFirst-fitNext-fitBest-fitWorst-fitCompactionInternal / externalfragmentationVariableNon-equalFixedNon-equal9The Buddy SystemDynamically partition in powers-of-2 size chunksAllocation• given request for size r, find smallest chunk• while (r < sizeof(chunk)/2)– divide chunk into 2 buddies (each of 1/2 size), select oneDeallocation• free the chunk• while (buddy is also free)– Coalesce10Example of Buddy System8 MBAlloc A900 KB4 MB4 MB2 MB2 MBA2 MB4 MB 4 MB1 MBAlloc B1.2 MBAB1 MB4 MBAlloc C1.5 MBAB1 MB2 MBCFree BA1 MB2 MBC2 MBFree A1 MB2 MBC2 MB1 MB2 MBC2 MB2 MB2 MBC4 MB11Data Structure for Buddy System8 MB4 MB 4 MB2 MB 2 MB4 MBAlloc A: 900 KB12Data Structure for Buddy System2 MB4 MBA 1 MBB4 MBA 1 MBAlloc A: 900 KB Alloc B: 1.2 MB13Data Structure for Buddy SystemBA 1 MBAlloc C: 1.5 MB2 MBC14Data Structure for Buddy System2 MBA 1 MBFree B2 MBC15Data Structure for Buddy System2 MB1 MB 1 MBFree A2 MBC16Data Structure for Buddy System2 MB 2 MBCoalesce2 MBC4 MBCoalesce2 MBC17Problems with Sharing MemoryThe Addressing Problem• compiler generates memory refs• unknown where process will be inThe Protection Problem• modifying another process’s memoryThe Space Problem• the more processes there are, theless memory each have individuallyP2P1P318Address SpacesAddress space• set of addresses for memoryUsually linear: 0 to N-1 (size N)Physical Address Space• 0 to N-1, N = size• kernel occupies lowest addresses(typically)0N-1PASkernelPM19Logical vs. Physical AddressingLogical addresses• assumes separatememory starting at 0• compiler generated• independent of locationin physical memoryConverting logical to physical• S/W: at load time• H/W: at access timeP10N1-1P20N2-1P30N3-1LMsLASsP2P1P30N -1PMPAS20Hardware for Logical AddressingBase register filledwith start addressTo translate logicaladdress, add baseAchieves relocationTo move process:change baseP20N2-1P2P1P30N -1Base +21ProtectionBound register workswith base regCheck if address lessthan boundIf so, add to baseIf not, invalidaddress, trapP20N2-1P2P1P30N -1Base +<Boundy/n?22Memory Registers Part of ContextOn Every Context Switch• Load base/bound registers for selected process• Only operating system does loading• Kernel must be protected from all processesBenefit• Allows each process to be separately located• Protects each process from all others23LoadingTo create a process, must load it into memoryWhat 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 memoryRelocatable loading: load to a variable location• dynamic run-time loading: allow location to change24LinkingTake object modules, create load moduleLinkage editor: resolves inter-object references• Ex., modules A and B• A: call f(x), where f(x) code is in BDynamic 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
View Full Document
Unlocking...