OPERATING SYSTEMS MEMORY MANAGEMENT - WPI
OPERATING SYSTEMSMEMORY MANAGEMENTJerry Breecher8: Memory Management1
OPERATING SYSTEMMemory ManagementWhat Is In This Chapter?Just as processes share the CPU, they also sharephysical memory. This chapter is aboutmechanisms for doing that sharing.8: Memory Management2
MEMORY MANAGEMENTJust as processes share the CPU, they also share physical memory. This section is aboutmechanisms for doing that sharing.EXAMPLE OF MEMORY USAGE:Calculation of an effective addressFetch from instructionUse index offsetExample: ( Here index is a pointer to an address )loop:loadaddstoreincskip equalbranch loop. continue .register, index42, registerregister, indexindexindex, final address8: Memory Management3
MEMORYMANAGEMENTDefinitions The concept of a logical address space that is bound to a separatephysical address space is central to proper memory management. Logical address – generated by the CPU; also referred to as virtualaddress Physical address – address seen by the memory unit Logical and physical addresses are the same in compile-time and loadtime address-binding schemes; logical (virtual) and physical addressesdiffer in execution-time address-binding scheme8: Memory Management4
MEMORYMANAGEMENTDefinitionsRelocatableMeans that the program image can reside anywhere in physical memory.BindingPrograms need real memory in which to reside. When is the location of thatreal memory determined? This is called mapping logical to physical addresses. This binding can be done at compile/link time. Converts symbolic torelocatable. Data used within compiled source is offset within objectmodule.Compiler:If it’s known where the program will reside, then absolute code is generated.Otherwise compiler produces relocatable code.Load:Binds relocatable to physical. Can find best physical location.Execution:The code can be moved around during execution. Means flexible virtualmapping.8: Memory Management5
MEMORYMANAGEMENTBinding Logical To PhysicalSourceThis binding can be done at compile/linktime. Converts symbolic to relocatable.Data used within compiled source is offsetwithin object module.Can be done at load time.Binds relocatable to physical.Can be done at run time.Implies that the code can bemovedaroundduringexecution.The next example shows how a compilerand linker actually determine the locationsof these effective addresses.CompilerObjectOther ObjectsLinkerExecutableLoaderLibrariesIn-memory Image8: Memory Management6
MEMORYMANAGEMENTBinding Logical To Physical4 voidmain()5 {6 printf( "Hello, from main\n" );7 b();8}91011 voidb()12 {13 printf( "Hello, from 'b'\n" );14 }8: Memory Management7
MEMORYMANAGEMENTBinding Logical To PhysicalASSEMBLY LANGUAGE p),%r2%r0(%r2)-64(%sp),%sp000000E0: E8200000000000E4 28200000000000E8: 1FADB43A00104BC23F59E840C00037DE3F81; main(); get current addr BC;;;;;get code start areacall printfcalc. String loc.call bstore return addr; return from mainSTUB(S) FROM LINE 6voidb(); get current addr F8; get code start area; call printf; return from b8: Memory Management8
000020E4000020E8000020ECBinding Logical To PhysicalEXECUTABLE IS DISASSEMBLED HERE0009000F; . . .08000240; . . .48656C6C; H e l6F2C2066; o ,726F6D20; r o m620A0001; b . .48656C6C; H e l6F2C2066; o ,726F6D20; r o m6D61696E; m a i6BC23FD9 stw%r2,-20(%sp); main37DE0080 ldo64(%sp),%spE8200000 bl0x000020C0,%r1D4201C1E depi0,31,2,%r134213E81 ldo-192(%r1),%r1E84017AC bl0x00003CA0,%r2B43A0040 addi32,%r1,%r26E8400040 bl0x000020F4,%r26BC23FD9 stw%r2,-20(%sp)4BC23F59 ldw-84(%sp),%r2E840C000 bv%r0(%r2)37DE3F81 ldo-64(%sp),%spE8200000 bl0x000020E8,%r1; stub28203000 addilL%6144,%r1E020E772 be,n0x000003B8(%sr7,%r1)08000240 nop8: Memory Management.@lf.lfn9
MEMORYMANAGEMENTBinding Logical To 002104000021080000210C0000211000002114EXECUTABLE IS DISASSEMBLED HERE6BC23FD9 stw%r2,-20(%sp)37DE0080 ldo64(%sp),%spE8200000 bl0x00002100,%r1D4201C1E depi0,31,2,%r134213E01 ldo-256(%r1),%r1E840172C bl0x00003CA0,%r2B43A0010 addi8,%r1,%r264BC23F59 ldw-84(%sp),%r2E840C000 bv%r0(%r2)37DE3F81 4(%sp),%sp0x00003CE8,%r10x00000428(%sr7,%r1)8: Memory Management; b; printf10
MEMORYMANAGEMENTMore DefinitionsDynamic loading Routine is not loaded until it is calledBetter memory-space utilization; unused routine is never loaded.Useful when large amounts of code are needed to handle infrequently occurring cases.No special support from the OS is required - implemented through program design.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 of the routine, and executes the routine.Operating system needed to check if routine is in processes’ memory address.Dynamic linking is particularly useful for libraries.Memory ManagementPerforms the above operations. Usually requires hardwaresupport.8: Memory Management11
MEMORYMANAGEMENTSINGLE PARTITIONALLOCATIONBARE MACHINE:No protection, no utilities, no overhead.This is the simplest form of memory management.Used by hardware diagnostics, by system boot code, real time/dedicated systems.logical physicalUser can have complete control. Commensurably, the operating system has none.DEFINITION OF PARTITIONS:Division of physical memory into fixed sized regions. (Allows addresses spaces to bedistinct one user can't muck with another user, or the system.)The number of partitions determines the level of multiprogramming. Partition is givento a process when it's scheduled.Protection around each partition determined bybounds ( upper, lower )base / limit.These limits are done in hardware.8: Memory Management12
MEMORYMANAGEMENTSINGLE PARTITIONALLOCATIONRESIDENT MONITOR:Primitive Operating System.Usually in low memory where interrupt vectors are placed.Must check each memory reference against fence ( fixed or variable ) in hardware orregister. If user generated address fence, then illegal.User program starts at fence - fixed for duration of execution. Then user code hasfence address built in. But only works for static-sized monitor.If monitor can change in size, start user at high end and move back, OR use fence asbase register that requires address binding at execution time. Add base register toevery generated user address.Isolate user from physical address space using logical address space.Concept of "mapping addresses” shown on next slide.8: Memory Management13
CPULogicalAddressSINGLE PARTITIONALLOCATION No PhysicalAddress8: Memory ManagementMEMORY14
MEMORYMANAGEMENTJOB SCHEDULINGCONTIGUOUSALLOCATIONAll pages for a process areallocated together in onechunk.Must take into account who wants to run, the memory needs, and partitionavailability. (This is a combination of short/medium term scheduling.)Sequence of events:In an empty memory slot, load a programTHEN it can compete for CPU time.Upon job completion, the partition becomes available.Can determine memory size required ( either user specified or"automatically" ).8: Memory Management15
CONTIGUOUSALLOCATIONMEMORYMANAGEMENTDYNAMIC STORAGE(Variable sized holes in memory allocated on need.)Operating System keeps table of this memory - space allocated based ontable.Adjacent freed space merged to get largest holes - buddy system.ALLOCATION PRODUCES HOLESOSOSOSprocess 1process 1process 1process 2process 3Process 2TerminatesProcess 4Startsprocess 38: Memory Managementprocess 4process 316
MEMORYMANAGEMENTCONTIGUOUSALLOCATIONHOW DO YOU ALLOCATE MEMORY TO NEW PROCESSES?First fit - allocate the first hole that's big enough.Best fit - allocate smallest hole that's big enough.Worst fit - allocate largest hole.(First fit is fastest, worst fit has lowest memory utilization.)Avoid small holes (external fragmentation). This occurs when there aremany small pieces of free memory.What should be the minimum size allocated, allocated in what chunk size?Want to also avoid internal fragmentation. This is when memory ishanded out in some fixed way (power of 2 for instance) and requestingprogram doesn't use it all.8: Memory Management17
MEMORYMANAGEMENTLONG TERMSCHEDULINGIf a job doesn't fit in memory, the scheduler canwait for memoryskip to next job and see if it fits.What are the pros and cons of each of these?There's little or no internal fragmentation (the process uses the memory given to it the size given to it will be a page.)But there can be a great deal of external fragmentation. This is because thememory is constantly being handed cycled between the process and free.8: Memory Management18
MEMORY MANAGEMENTCOMPACTIONTrying to move free memory to one large block.Only possible if programs linked with dynamic relocation (base and limit.)There are many ways to move programs in memory.Swapping: if using static relocation, code/data must return to same place.But if dynamic, can reenter at more advantageous memory.OSP1OSOSP1P1P2P3P3P2P2P38: Memory Management19
MEMORY MANAGEMENT PAGINGNew Concept!!Logical address space of a process can be noncontiguous; process isallocated physical memory whenever that memory is available and theprogram needs it.Divide physical memory into fixed-sized blocks called frames (size ispower of 2, between 512 bytes and 8192 bytes).Divide logical memory into blocks of same size called pages.Keep track of all free frames.To run a program of size n pages, need to find n free frames and loadprogram.Set up a page table to translate logical to physical addresses.Internal fragmentation.8: Memory Management20
PAGINGMEMORY MANAGEMENTAddress Translation SchemeAddress generated by the CPU is divided into: Page number (p) – used as an index into a page table whichcontains base address of each page in physical memory. Page offset (d) – combined with base address to define thephysical memory address that is sent to the memory unit.4096 bytes 2 12 – it requires 12 bits to contain the Page offsetpd8: Memory Management21
MEMORY MANAGEMENTPAGINGPermits a program's memory to be physically noncontiguous so it can be allocatedfrom wherever available. This avoids fragmentation and compaction.Frames physical blocksPages logical blocksSize of frames/pages isdefined by hardware (powerof 2 to ease calculations)HARDWAREAn address is determined by:page number ( index into table ) offset--- mapping into --- base address ( from table ) offset.8: Memory Management22
MEMORY MANAGEMENTPaging Example - 32-byte memory with 4-byte pages0a1b2c3d4e5f6g7h8I9j10 k11 l12 m13 n14 o15 pLogical MemoryPAGING04801235612Ijklmnop12Page Table1620abcd24efghPhysical Memory288: Memory Management23
MEMORY MANAGEMENT A 32 bit machine canaddress 4 gigabytes whichis 4 million pages (at 1024bytes/page).WHO sayshow big a page is, anyway? Couldusededicatedregisters (OK only withsmall tables.) Could use a registerpointing to table in memory(slow access.) Cacheorassociativememory (TLB TranslationLookaside Buffer): simultaneous search is fastand uses only a fewregisters.PAGINGIMPLEMENTATION OF THE PAGE TABLETLB Translation Lookaside Buffer8: Memory Management24
MEMORY MANAGEMENTPAGINGIMPLEMENTATION OF THE PAGE TABLEIssues include:key and valuehit rate 90 - 98% with 100 registersadd entry if not foundEffective access time %fast*time fast %slow*time slowRelevant times:2 nanoseconds to search associative memory – the TLB.20 nanoseconds to access processor cache and bring it into TLB for next time.Calculate time of access:hit 1 search 1 memory referencemiss 1 search 1 mem reference(of page table) 1 mem reference.8: Memory Management25
MEMORY MANAGEMENTPAGINGSHARED PAGESDataoccupyingonephysicalpage,butpointed to by multiplelogical pages.Useful for common code must be write protected.(NOwrite-abledatamixed with code.)Extremelyusefulforread/write communicationbetween processes.8: Memory Management26
MEMORY MANAGEMENTPAGINGINVERTED PAGE TABLE:One entry for each real page ofmemory.Entry consists of the virtualaddress of the page stored in thatrealmemorylocation,withinformation about the process thatowns that page.Essential when you need to dowork on the page and must findout what process owns it.Use hash table to limit the searchto one - or at most a few - pagetable entries.8: Memory Management27
MEMORY MANAGEMENTPAGINGPROTECTION: Bits associated with page tables. Can have read, write, execute, valid bits. Valid bit says page isn’t in address space. Write to a write-protected page causes a fault. Touching an invalid page causes a fault.ADDRESS MAPPING: Allows physical memory larger than logical memory. Useful on 32 bit machines with more than 32-bit addressable words of memory. The operating system keeps a frame containing descriptions of physical pages; if allocated, thento which logical page in which process.8: Memory Management28
MEMORY MANAGEMENTPAGINGMULTILEVEL PAGE TABLEA means of using page tablesfor large address spaces.8: Memory Management29
MEMORY MANAGEMENTSegmentationUSER'S VIEW OF MEMORYA programmer views a process consisting of unordered segments with variouspurposes. This view is more useful than thinking of a linear array of words. Wereally don't care at what address a segment is located.Typical segments includeglobal variablesprocedure call stackcode for each functionlocal variables for eachlarge data structuresLogical address segment name ( number ) offsetMemory is addressed by both segment and offset.8: Memory Management30
MEMORY MANAGEMENTSegmentationHARDWARE -- Must map a dyad (segment / offset) into one-dimensional address.Segment TableLimitCPUSBaseDLogicalAddressYes No8: Memory ManagementPhysicalAddressMEMORY31
MEMORY MANAGEMENTSegmentationHARDWAREbase / limit pairs in a segment 00320047001403423Logical Address Space8: Memory ManagementPhysical Memory32
MEMORY MANAGEMENTPROTECTION AND SHARINGSegmentationAddresses are associated with a logicalunit (like data, code, etc.) so protection iseasy.Can do bounds checking on arraysSharing specified at a logical level, asegment has an attribute called"shareable".Can share some code but not all - forinstance a common library of ent lengths vary.sinceAgain have issue of fragmentation;Smaller segments means lessfragmentation. Can use compactionsince segments are relocatable.8: Memory Management33
MEMORY MANAGEMENTSegmentationPAGED ress frame at ( page table base for segment offset into page table ) offset into memoryLook at example of Intel architecture.8: Memory Management34
MEMORY MANAGEMENTWRAPUPWe’ve looked at how to do paging - associating logical withphysical memory.This subject is at the very heart of what every operatingsystem must do today.8: Memory Management35
8: Memory Management 4 MEMORY MANAGEMENT The concept of a logical address space that is bound to a separate physical address space is central to proper memory management. Logical address – generated by the CPU; also referred to as virtual address Physical address – address seen by the memory unit Logical and
Using the WPI Robotics Library The WPI Robotics library (WPILib) is a set of software classes that interfaces with the hardware in your FRC robots control system. There are classes to handle sensors, motors, the driver station, and a number of other utility functions such as timing and field management. What is the WPI Robotics Library?
Iron Angel Force back the invading enemy using a customizable mech-suit. by Brainstorm Productions: Eric Benson erbenson@wpi.edu Keenan Gray krgray@wpi.edu Connor Porell cgporell@wpi.edu . 2!! Game Summary Iron Angel is an exciting action-based shooter. The player is put in control of a powerful mech-
7 Terminology WPI: Worcester Polytechnic Institute, a four-year private university in Worcester, Massachusetts, USA MQP: Major Qualifying Project, a project done at WPI, usually completed in a student's senior year. It is in the student's major field, and must be completed prior to graduating. [WPI, 2014] CS: Computer Science HTML: Hypertext Markup Language, a markup language that is used .
Memory Management Ideally programmers want memory that is o large o fast o non volatile o and cheap Memory hierarchy o small amount of fast, expensive memory -cache o some medium-speed, medium price main memory o gigabytes of slow, cheap disk storage Memory management tasks o Allocate and de-allocate memory for processes o Keep track of used memory and by whom
Virtual Memory Cache Memory summary Operating Systems PAGED MEMORY ALLOCATION Analysis Advantages: Pages do not need to store in the main memory contiguously (the free page frame can spread all places in main memory) More e cient use of main memory (comparing to the approaches of early memory management) - no external/internal fragmentation
Operating Systems. Memory Management 26 / 91. Swapping Introduction Swapping Relocation Protection Simple schemes Segmentation Paging Mixed systems Operating Systems. Memory Management 27 / 91. Swapping Swapping (The Swap) area is a part of the disk used as auxiliar memory A running process needs to be in memory. Swapping can increase the
Memory Management To execute a program all (or part) of the instructions must be in memory All (or part) of the data that is needed by the program must be in memory. Memory management determines what is in memory and when Memory management activities Keeping track of which parts of memory are currently
Quality level according to API 6A - PSL 1, 2 or 3. 1. In the trunnion mounted design configuration, the ball is supported by bearing, held in position by the valve closures. This configuration allows to discharge any side loads on the valve body, enabling a smoother operation of the ball, minimizing the operating torque and reducing seat seal wear. 2. Anti-Blow Out stem design. 3. Standard .
