Operating Systems - Memory Management
Operating Systems –Memory ManagementECE 344ECE 344 Operating Systems1
Memory Management BackgroundSwappingContiguous AllocationPagingSegmentationSegmentation with PagingVirtual MemoryECE 344 Operating Systems2
Binding of Instructions and Data to Memory Compile time:– known memory location– absolute code can be generated– must recompile code if starting location changes. Load time:– generate relocatable code if memory location isnot known at compile time. Execution time:– process can be moved during its execution fromone memory segment to another.– need hardware support for address mappingECE 344 Operating Systems3
Logical vs. Physical Address Space A logical address space that is bound to aseparate physical address space– Logical address – generated by the CPU;also referred to as virtual address.– Physical address – address generated bythe memory management unit. Logical and physical addresses are the samein compile-time and load-time addressbinding schemes. Logical (virtual) and physical addresses differin execution-time address-binding scheme.ECE 344 Operating Systems4
Memory-Management Unit (MMU) Hardware device that maps logical/virtual tophysical address. In MMU the value in the relocation register isadded to every address generated by aprogram at the time the address is sent tomemory. The program deals with logical addresses; itnever sees the real physical addresses.ECE 344 Operating Systems5
Dynamic relocation/binding using arelocation registerECE 344 Operating Systems6
Memory AllocationECE 344 Operating Systems7
Contiguous Memory Allocation Multiple partitions for multiple processes Relocation register and limit registers to protectprocesses from one another (and protect OS code) Both registers are part of process context (i.e., PCB) Relocation register contains value of smallestphysical address Limit register contains range of logical addresses Each logical address must be less than the limitregister.ECE 344 Operating Systems8
Hardware Support for Relocationand Limit RegistersECE 344 Operating Systems9
Multi-partition Allocation Holes are blocks of available memory Holes of various size are scatteredthroughout memory. When a process arrives, it is allocatedmemory from a hole large enough toaccommodate it. Operating system maintains informationabout:– allocated partitions– free partitions (i.e., holes)ECE 344 Operating Systems10
timePQPQPRholeholeSSSSTTTTECE 344 Operating SystemsP11
Dynamic Storage Allocation Problem How to satisfya request for memory of size n.from a list of free holes? First-fit: Allocate the first hole that is bigenough. Best-fit: Allocate the smallest hole that is bigenough; must search entire list, unless orderedby size. Produces the smallest leftover hole. Worst-fit: Allocate the largest hole; must alsosearch entire list. Produces the largestleftover holeECE 344 Operating Systems12
External FragmentationMemoryProcess 5New ProcessholeProcess 6holeECE 344 Operating Systems13
Internal FragmentationMemoryProcess 5required space Memory is allocated in block/partition/junks Giving back a small amount of memory to the memorymanager is not feasible Overhead of managing a few left-over bytes is not worth theeffortECE 344 Operating Systems14
Fragmentation External Fragmentation – total memory spaceexists to satisfy a request, but it is not contiguous. Internal Fragmentation – allocated memory maybe slightly larger than requested memory; this sizedifference is memory internal to a partition, but notbeing used. Reduce external fragmentation by compaction– Shuffle memory contents to place all free memorytogether in one large block.– Compaction is possible only if address binding isdynamic, and is done at execution time.ECE 344 Operating Systems15
Preview The problem so far has been that weallocated memory in contiguous junks What if we could allocate memory in noncontiguous junks? We will be looking at techniques that aim atavoiding– External fragmentation– (Internal fragmentation)ECE 344 Operating Systems16
MemoryProcessFramePage or SegmentMemoryProcessECE 344 Operating Systems17
Paging Physical address space of a process can be noncontiguous; Process is allocated physical memory whenever the latter isavailable. Divide physical memory into fixed-sized blocks calledframes (size is power of 2, between 512 bytes and 8192bytes). Divide logical memory into blocks of same size calledpages. Keep track of all free frames. To run a program of size n pages, need to find n freeframes and load program. Set up a page table to translate logical to physicaladdresses.18 Internal fragmentation: for last page)
Address Translation Scheme Address generated by CPU is divided into:– Page number (p) Used as an index into the page table Page table contains base address of each page inphysical memory.– Page offset (d) combined with base address to define thephysical memory address sent to the memory unit.ECE 344 Operating Systems19
Address Translation Architecturepage numberoffsetbase addressECE 344 Operating Systems20
ProcessPaging ExampleECE 344 Operating Systems21
Paging ExamplePage size is 4Page 0 is in Frame 5, located at address 20i.e., 5 x 4 20Logical address (1,3) ( 7) is mapped to 27(6 x 4 3 27)ECE 344 Operating Systems22
PageNumber,4 bits 16 pagesoffset,12 bits 4096 byte locations(4 k pages)ECE 344 Operating Systems23
freefreefreefreefreeBefore allocationECE 344 Operating SystemsAfter allocation24
Implementation of Page Table Page table is kept in main memory. Page-table base register (PTBR) points to thepage table (part of process context). Page-table length register (PRLR) indicatessize of the page table (part of process context). In this scheme every data/instruction accessrequires two memory accesses. One for thepage table and one for the data/instruction. This is pretty inefficient, if done in softwareECE 344 Operating Systems25
Implementation of Page Table Page table can be extremely large 32 bit virtual address and 4k page size resultsin 1 million pages (232/212 220) 4 byte page table entry, results in a 4MB table Page table requires 1 million entries, eachprocess has its own table Mapping has to be fast A typical instruction has 1, 2, operands,which require memory access (through pagetable)ECE 344 Operating Systems26
Implementation of Page Table Page table as a set of registers– Adds to context switch overhead– Page table usually too large The two memory access problem can besolved by the use of a special fast-lookuphardware cache called associativememory A.k.a. a translation look-aside buffer (TLB)ECE 344 Operating Systems27
Paging Hardwarewith TLBECE 344 Operating Systems28
Page Table Structure Hierarchical Paging Hashed Page Tables Inverted Page TablesECE 344 Operating Systems29
Hierarchical Page Tables Allocating the page table contiguously inmemory is not feasible Break up the logical address space intomultiple page tables Recursively apply the paging scheme to thepage table itself A simple technique is a two-level page tableECE 344 Operating Systems30
Two-Level Paging Example A logical address (on 32-bit machine with 4K pagesize) is divided into:––––A page number consisting of 20 bits.Possible address space of size 220 pages.A page offset consisting of 12 bits.12 bits can address 4096 bytes (i.e., all bytes in the 4kpage). Since the page table is paged, the page number isfurther divided into:– a 10-bit page number.– a 10-bit page offset.ECE 344 Operating Systems31
Two-level Address Thus, a logical address is as follows:page numberp1p210 bits 10 bitspage offsetd12 bits where p1 is an index into the outer pagetable, and p2 is the displacement within thepage of the (inner) page table.ECE 344 Operating Systems32
Address-Translation Scheme Address-translation scheme for a two-level32-bit paging architectureECE 344 Operating Systems33
Two-Level PageTable Schemed{ECE 344 Operating Systems34
Shared MemoryECE 344 Operating Systems35
Shared Pages Shared code– One copy of read-only (reentrant) codeshared among processes (i.e., text editors,compilers, window systems).– Shared code must appear in same location inthe logical address space of all processes. Private code and data– Each process keeps a separate copy of thecode and data.– The pages for the private code and data canappear anywhere in the logical addressspace.ECE 344 Operating Systems36
Shared Pages ExampleECE 344 Operating Systems37
Summary Address bindingContiguous memory managementOverlaysSwappingPagingECE 344 Operating Systems38
Virtual MemoryECE 344 Operating Systems39
Virtual Memory Only part of the program needs to be inmemory for execution. Logical address space can therefore bemuch larger than physical address space. Physical address spaces can be shared byseveral processes. More efficient process creation. Virtual memory can be implemented via– Demand paging– Demand segmentationECE 344 Operating Systems40
Virtual Memory thatis larger thanphysical memoryECE 344 Operating Systems41
Demand Paging Bring a page into memory only when it isneeded.– Less I/O needed– Less memory needed– Faster response– More users Page is needed reference to it– invalid reference abort– not-in-memory bring to memoryECE 344 Operating Systems42
A Pager (vs. swapper)Transfer of a pagedmemory tocontiguous diskspacePredictively bringsin pages of the processECE 344 Operating Systems43
Valid-Invalid Bit With each page table entry a valid–invalid bit is associated(1 in-memory, 0 not-in-memory) Initially valid–invalid bit is set to 0 onall entries During address translation, if valid–invalid bit in page table entry is 0 page fault Demand paging (all bits initially 0)ECE 344 Operating Systems44
ECE 344 Operating Systems45
Steps in Handling a Page FaultECE 344 Operating Systems46
What happens if there is no free frame? Page replacement – find some page inmemory, but not really in use, swap it out.– algorithm– performance algorithm should result in minimum number ofpage faults Same page may be brought into memoryseveral times.ECE 344 Operating Systems47
Page Replacement Prevent over-allocation of memory bymodifying page-fault service routine to includepage replacement Use modify (dirty) bit to reduce overhead ofpage transfers– only modified pages need to be written to disk Page replacement completes separationbetween logical memory and physical memory Thus large virtual memory can be providedon a smaller physical memoryECE 344 Operating Systems48
Need For Page ReplacementECE 344 Operating Systems49
Basic Page Replacement Find the location of the desired page on disk Find a free frame If there is a free frame, use it If there is no free frame, use a pagereplacement algorithm to select a victim frame Read the desired page into the (newly) freedframe Update the page table Restart the processECE 344 Operating Systems50
Page ReplacementECE 344 Operating Systems51
Page Replacement Algorithms Want lowest page-fault rate. Evaluate algorithm by running it on aparticular string of memory references(reference string) Compute the number of page faults on thatstring In all our examples, the reference string is1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.ECE 344 Operating Systems52
Graph of Page Faults Versus The Numberof FramesECE 344 Operating Systems53
First-In-First-Out (FIFO) Algorithm Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 Replace oldest page 3 (4) frames (3 (4) pages can be in memory ata time per process) initialization code frequently used code1145221333249 page faults11542215332443 More frames, more faults )-: ! Implemented withFIFO-queueECE 344 Operating Systems10 page faults54
FIFO Page ReplacementECE 344 Operating Systems55
FIFO Illustrating Belady’s Anamoly (1976)more frames less page faultsECE 344 Operating Systems56
Optimal Algorithm Replace page that will not be used forlongest period of time (cf. SJF) A 4 frames example1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5142345 How do we know this?6 page faults Used for measuring how well an algorithmperforms A baseline, we can’t do betterECE 344 Operating Systems57
Optimal Page ReplacementECE 344 Operating Systems58
Least Recently Used (LRU) AlgorithmReference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 551 use recent past as approximationof near future Counter implementation235434– Every page table entry has a counter; everytime page is referenced through this entry,copy the clock into the counter.– When a page needs to be replaced, look atthe counters to determine least recently usedECE 344 Operating Systems59
LRU Page ReplacementECE 344 Operating Systems60
LRU Algorithm (Cont.) Stack implementation – keep a stack ofpage numbers in a double link form Page referenced move it to the top requires 6 pointers to be changed No search for replacementECE 344 Operating Systems61
Use Of A Stack to Record The Most Recent PageReferencesECE 344 Operating Systems62
LRU Approximation Algorithm 1 Reference bit– With each page associate a bit, initially all 0– When page is referenced bit set to 1– Replace the page which is 0 (if one exists)– We do not know the order, howeverECE 344 Operating Systems63
LRU Approximation Algorithm 2 Keep several reference bits (e.g., 8 bits) per page And keep the reference bit (as before) At periodic intervals (timer interrupt, e.g., 100milliseconds) shift the reference bit of every pageinto the high-order position of the reference bit Right shift the reference bits, dropping low order bit 0000 0000 – not been used in past intervals 1111 1111 – has been used each in interval Interpret as unsigned integers, choose smallest asvictimECE 344 Operating Systems64
LRU Approximation Algorithm 3 Second chance– Need 1 reference bit– Clock replacement– If page to be replaced (in clock order) hasreference bit set to 1. then: set reference bit 0. leave page in memory. replace next page (in clock order), subject to samerules.ECE 344 Operating Systems65
Second-Chance (clock) Page-ReplacementAlgorithmECE 344 Operating Systems66
Counting Algorithms Keep a counter of the number of referencesthat have been made to each page LFU Algorithm: replaces page with smallestcount MFU Algorithm: based on the argument thatthe page with the smallest count wasprobably just brought in and has yet to beusedECE 344 Operating Systems67
Allocation of Frames Each process needs minimum number ofpages Example: IBM 370 – 6 pages to handleMOVE instruction:– instruction is 6 bytes, might span 2 pages– 2 pages to handle from– 2 pages to handle toECE 344 Operating Systems68
Minimum number of framesinstrECE 344 Operating Systems69
Fixed Allocation Two major allocation schemes– fixed allocation– priority allocation Equal allocation – e.g., if 100 frames and 5processes, give each 20 pages. Proportional allocation – Allocate accordingto the size of process.ECE 344 Operating Systems70
Fixed Allocationsi size of process piS sim total number of framessiai allocation for pi mSExample:m 64s i 10s 2 127a1a2ECE 344 Operating Systems10 64 5137127 64 5913771
Priority Allocation Use a proportional allocation scheme usingpriorities rather than size If process Pi generates a page fault,– select for replacement one of its frames– select for replacement a frame from a processwith lower priority numberECE 344 Operating Systems72
Global vs. Local Allocation Global replacement – process selects areplacement frame from the set of allframes; one process can take a frame fromanother Local replacement – each process selectsfrom only its own set of allocated frames.ECE 344 Operating Systems73
Thrashing If a process does not have “enough” pages, thepage-fault rate is very high. This leads to:– low CPU utilization (ready queue is empty)– operating system (may) think that it needs to increasethe degree of multiprogramming– another process added to the system– this process requires pages to be brought in Thrashing a process is busy swapping pages inand out (spends more time paging than executing.)ECE 344 Operating Systems74
Thrashingbring in more processesECE 344 Operating Systems75
Locality Why does paging work? Due to locality (memory accesses are not random) Locality model– Process migrates from one locality to another– Locality corresponds to a procedure call (local variables,some global variables and instructions of procedure)– Localities may overlap Why does thrashing occur?sum over size of all localities total physical memory sizeECE 344 Operating Systems76
Not random Execution moves from onelocality to the nextlocalityinstructionslocal variablessubset of global variablesECE 344 Operating Systems77
Working-Set Model (approximate locality) working-set window a fixed number of pagereferences. Example: 10,000 instruction WSSi (working set size of Process Pi) total number of pages referenced in the mostrecent (varies over time)– if too small will not encompass entire locality.– if too large will encompass several localities.– if will encompass entire process. D Σ WSSi total frames demanded if D m Thrashing (m is total physical memory) Policy if D m, then suspend one of theECE 344 Operating Systems78processes.
Working-set modelECE 344 Operating Systems79
Keeping Track of the Working Set Approximate with interval timer a reference bit Example: 10,000– Timer interrupts after every 5000 time units.– Keep in memory 2 bits for each page.– Whenever a timer interrupts copy reference bit to memorybits and sets the values of all reference bits to 0.– If one of the bits in memory 1 page in working set. Why is this not completely accurate? Improvement 10 bits and interrupt every 1000time units (cost of interrupt!).ECE 344 Operating Systems80
Page-Fault Frequency SchemeECE 344 Operating Systems81
Summary Memory Management Contiguous memory management Paging and segmentation Virtual memory management based ondemand paging Page replacement algorithm Frame allocation strategies Thrashing Locality and working set modelECE 344 Operating Systems82
ECE 344 Operating Systems83
OS Lecture Concepts and OS hackingProcesses and ThreadsOS System Structure and ArchitectureSynchronization– Software based solutions– Hardware based solutions– Semaphores, mutexes/locks, CVs, monitors– Synchronization problems Scheduling algorithm Memory managementECE 344 Operating Systems84
Assignments Tools: CVS, GDB, GCC Adding a delta to a large and complex software system– Not much know methodology about how to do this (but seesoftware engineering course)– Don’t be afraid of the size; work with a localizedunderstanding of system; 20K lines of code is nothingcompared to the size of real OS, DBs, Making design decision which great reach (actually making thedecision is difficult) Implementation of synchronization mechanisms Use of synchronization mechanisms Implementation of system calls (not just a procedure call) Implementation of scheduling algorithms and performancecounters OS and Systems is about hacking; that is building andextending large complex software systemsECE 344 Operating Systems85
The Final Closed book Covers entire lecture and assignments Rough breakdown of final, don’t quote me– 20 – 30 % knowledge questions a la midterm– 10 – 20 % about assignments– 20 – 30 % synchronization– 10 – 20 % memory management– Rest other course topicsECE 344 Operating Systems86
The EndECE 344 Operating Systems87
ECE 344 Operating Systems88
Segmentation Memory-management scheme that supports user’sview of memory. A program is a collection of segments. A segmentis a logical unit such as:main program,procedure,function,method,object,local variables, global variables,common block,stack,symbol table, arraysECE 344 Operating Systems89
User’s View of a ProgramECE 344 Operating Systems90
Logical View of Segmentation11423423user spaceECE 344 Operating Systemsphysical memory space91
Segmentation Architecture Logical address consists of a two tuple: segment-number, offset , Segment table – maps two-dimensionalphysical addresses; each table entry has:– base – contains the starting physical address wherethe segments reside in memory.– limit – specifies the length of the segment. Segment-table base register (STBR) pointsto the segment table’s location in memory. Segment-table length register (STLR)indicates number of segments used by aECE 344 Operating Systems92program;
SegmentationHardwareECE 344 Operating Systems93
Example of SegmentationECE 344 Operating Systems94
Sharing of SegmentsECE 344 Operating Systems95
ECE 344 Operating Systems96
Hashed Page Tables Common in address spaces 32 bits. The virtual page number is hashed into apage table. This page table contains a chain of elementshashing to the same location. Virtual page numbers are compared in thischain searching for a match. If a match isfound, the corresponding physical frame isextracted.ECE 344 Operating Systems97
Hashed Page TableECE 344 Operating Systems98
Inverted Page Table One entry for each real frame of memory. Entry consists of the virtual address of thepage stored in that real memory location, withinformation about the process that owns thatpage. Decreases memory needed to store eachpage table, but increases time needed tosearch the table when a page referenceoccurs. Use hash table to limit the search to one —or at most a few — page-table entries.ECE 344 Operating Systems99
Inverted Page Table ArchitectureECE 344 Operating Systems100
ECE 344 Operating Systems 4 Logical vs. Physical Address Space A logical address space that is bound to a separate physical address space - Logical address - generated by the CPU; also referred to as virtual address. - Physical address - address generated by the memory management unit. Logical and physical addresses are the same
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
In memory of Paul Laliberte In memory of Raymond Proulx In memory of Robert G. Jones In memory of Jim Walsh In memory of Jay Kronan In memory of Beth Ann Findlen In memory of Richard L. Small, Jr. In memory of Amalia Phillips In honor of Volunteers (9) In honor of Andrew Dowgiert In memory of
Memory -- Chapter 6 2 virtual memory, memory segmentation, paging and address translation. Introduction Memory lies at the heart of the stored-program computer (Von Neumann model) . In previous chapters, we studied the ways in which memory is accessed by various ISAs. In this chapter, we focus on memory organization or memory hierarchy systems.
An Introduction to Linux memory management. The basics of paging. Understanding basic hardware memory management and the difference between virtual, physical and swap memory. How do determine hardware installed and how to figure out how processes use that memory. How a process uses physical and virtual memory effectively.
Chapter 2 Memory Hierarchy Design 2 Introduction Goal: unlimited amount of memory with low latency Fast memory technology is more expensive per bit than slower memory –Use principle of locality (spatial and temporal) Solution: organize memory system into a hierarchy –Entire addressable memory space available in largest, slowest memory –Incrementally smaller and faster memories, each .
