CS 111 Spring 2022
Lecture 5 Page 1
Operating System Principles: Memory Management CS 111
Spring 2022 Operating System Principles Peter Reiher
Copyright By PowCoder代写 加微信 powcoder
• What is memory management about?
• Memory management strategies: – Fixed partition strategies
– Dynamic partitions
– Buffer pools
– Garbage collection – Memory compaction
CS 111 Spring 2022
Lecture 5 Page 2
Memory Management
• Memory is one of the key assets used in computing
• In particular, memory abstractions that are usable from a running program
– Which, in modern machines, typically means RAM
• We have a limited amount of it
• Lots of processes need to use it
• How do we manage it?
CS 111 Spring 2022
Lecture 5 Page 3
Memory Management Goals
1. Transparency
– Process sees only its own address space
– Process is unaware memory is being shared
2. Efficiency
– High effective memory utilization
– Low run-time cost for allocation/relocation
3. Protection and isolation
– Private data will not be corrupted
– Private data cannot be seen by other processes
CS 111 Spring 2022
Lecture 5 Page 4
Physical Memory Allocation
process 1 data and stack
shared lib X
shared code segment A
process 3 data and stack
process 2 data and stack
shared code segment B
CS 111 Spring 2022
Lecture 5 Page 5
Physical memory is divided between the OS kernel, process private data, and shared code segments.
Physical and Virtual Addresses A RAM cell has a particular physical address
– Essentially a location on a memory chip
Years ago, that address was used by processes
to name memory locations
Now processes use virtual addresses
– Which is not a location on a memory chip
– And usually isn’t the same as the actual physical address
More flexibility in memory management, but
requires virtual to physical translation Spring 2022
Lecture 5 Page 6
Virtual Vs. Physical: A Short Digression
• We use the word ”virtual” a lot in CS • By it, we mean “it ain’t real”
– If we have a virtual widget, we don’t actually have a real widget
– But we want it to behave as if it were real
• How do we do that?
– Software ― lots and lots of software – Usually OS software
• How to make virtual memory act like real? CS 111
Spring 2022
Lecture 5 Page 7
Aspects of the Memory Management Problem
• Mostprocessescan’tperfectlypredicthowmuch memory they will use
• Theprocessesexpecttofindtheirexistingdatawhen they need it where they left it
• Theentireamountofdatarequiredbyallprocesses may exceed amount of available physical memory
• Switchingbetweenprocessesmustbefast – Can’t afford much delay for copying data
• Thecostofmemorymanagementitselfmustnotbe too high
CS 111 Spring 2022
Lecture 5 Page 8
Memory Management Strategies
• Fixed partition allocations • Dynamic partitions
• Relocation
CS 111 Spring 2022
Lecture 5 Page 9
Fixed Partition Allocation
• Pre-allocate partitions for n processes
– One or more per process
– Reserving space for largest possible process
• Partitions come in one or a few set sizes
• Very easy to implement
– Common in old batch processing systems
– Allocation/deallocation very cheap and easy
• Well suited to well-known job mix
CS 111 Spring 2022
Lecture 5 Page 10
Memory Protection and Fixed
Partitions
• Need to enforce partition boundaries
– To prevent one process from accessing another’s memory
• Could use hardware for this purpose
– Special registers that contain the partition
boundaries
– Only accept addresses within the register values
• Basic scheme doesn’t use virtual addresses
CS 111 Spring 2022
Lecture 5 Page 11
The Partition Concept
Partition Registers
Memory Disk
CS 111 Spring 2022
Lecture 5 Page 12
Problems With Fixed Partition
Allocation
• Presumes you know how much memory will
be used ahead of time
• Limits the number of processes supported to the total of their memory requirements
• Not great for sharing memory
• Fragmentation causes inefficient memory use
CS 111 Spring 2022
Lecture 5 Page 13
Fragmentation
• A problem for all memory management systems
– Fixed partitions suffer it especially badly
• Based on inefficiencies in memory allocation
• With too much fragmentation,
• You can’t provide memory for as many processes as you theoretically could
CS 111 Spring 2022
Lecture 5 Page 14
Fragmentation Example
Let’s say there are three processes, A, B, and C
Their memory requirements:
Available partition sizes:
8 Mbytes 4 Mbytes 4 Mbytes
A: 6 MBytes B: 3 MBytes C: 2 MBytes
Total waste = 2MB + 1MB + 2MB =
5/16MB = 31%
If someone asks for a 3MB partition, you can’t provide it
Even though there’s 5 MB unused
Lecture 5 Page 15
CS 111 Spring 2022
Partition 1 8MB
Partition 2 4MB
Partition 3 4MB
Internal Fragmentation
• Fragmentation comes in two kinds:
– Internal and external
• This is an example of internal fragmentation
– We’ll see external fragmentation later
• Wasted space inside fixed sized blocks
– The requestor was given more than he needed
– The unused part is wasted and can’t be used for others
• Internal fragmentation can occur whenever
you force allocation in fixed-sized chunks CS 111
Spring 2022
Lecture 5 Page 16
More on Internal Fragmentation
• Internal fragmentation is caused by a mismatch between
– The chosen size of a fixed-sized block – The actual sizes that programs use
• Average waste: 50% of each block
CS 111 Spring 2022
Lecture 5 Page 17
Summary of Fixed Partition Allocation
• Very simple
• Inflexible
• Subject to a lot of internal fragmentation
• Not used in many modern systems
– But a possible option for special purpose systems,
like embedded systems
– Where we know exactly what our memory needs will be
CS 111 Spring 2022
Lecture 5 Page 18
Dynamic Partition Allocation
• Like fixed partitions, except
– Variable sized, usually almost any size requested
– Each partition has contiguous memory addresses
– Processes have access permissions for the partitions
– Potentially shared between processes
• Each process could have multiple partitions
– With different sizes and characteristics
• In basic scheme, still only physical addresses
CS 111 Spring 2022
Lecture 5 Page 19
Not relocatable
– Once a process has a partition, you can’t easily move its contents elsewhere
Not easily expandable
Impossible to support applications with larger address spaces than physical memory
– Also can’t support several applications whose total needs are greater than physical memory
Problems With Dynamic Partitions
– Of a different kind . . . Spring 2022
Lecture 5 Page 20
Also subject to fragmentation
Relocation and Expansion
• Partitions are tied to particular address ranges
– At least during an execution
• Can’t just move the contents of a partition to another set of addresses
– All the pointers in the contents will be wrong – And generally you don’t know which memory
locations contain pointers
• Hard to expand because there may not be space “nearby”
CS 111 Spring 2022
Lecture 5 Page 21
The Expansion Problem
• Partitions are allocated on request
• Processes may ask for new ones later
• But partitions that have been allocated can’t be moved somewhere else in memory
• Memory management system might have allocated all the space after a given partition
– In which case, it can’t be expanded
CS 111 Spring 2022
Lecture 5 Page 22
Illustrating the Problem
Now Process B wants to expand its partition size
But if we do that, Process B steps on Process C’s memory
We can’t move C’s partition out of the way
And we can’t move B’s partition to a free area
We’re stuck, and must deny an expansion request
CS 111 Spring 2022
that we have enough memory to handle
Lecture 5 Page 23
How To Keep Track of Variable
Sized Partitions? • Startwithonelarge“heap”ofmemory
• Maintainafreelist
– Systems data structure to keep track of pieces of
unallocated memory
• Whenaprocessrequestsmorememory: – Find a large enough chunk of memory
– Carve off a piece of the requested size
– Put the remainder back on the free list
• Whenaprocessfreesmemory
– Put freed memory back on the free list
CS 111 Spring 2022
Lecture 5 Page 24
Managing the Free List • Fixed sized blocks are easy to track
– A bit map indicating which blocks are free
• Variable chunks require more information
– A linked list of descriptors, one per chunk
– Each descriptor lists the size of the chunk and whether it is free
– Each has a pointer to the next chunk on list
– Descriptors often kept at front of each chunk
• Allocated memory may have descriptors too
CS 111 Spring 2022
Lecture 5 Page 25
List might contain all memory fragments
The Free List
CS 111 Spring 2022
Lecture 5 Page 26
…or only
fragments that
are free …
Free Chunk Carving
1. Find a large enough free chunk
2. Reduce its len to requested size
3.Create a new header for residual chunk
4. Insert the new chunk into the list
5. Mark the carved piece as in use
CS 111 Spring 2022
Lecture 5 Page 27
Variable Partitions and Fragmentation
• Variable sized partitions not as subject to internal fragmentation
– Unless requestor asked for more than he will use
– Which is actually pretty common
– But at least memory manager gave him no more than he requested
• Unlike fixed sized partitions, though, subject to another kind of fragmentation
– External fragmentation
CS 111 Spring 2022
Lecture 5 Page 28
External Fragmentation
CS 111 Spring 2022
Lecture 5 Page 29
We gradually build up small, unusable memory chunks scattered through memory
External Fragmentation: Causes
and Effects
• Each allocation creates left-over free chunks
– Over time they become smaller and smaller
• The small left-over fragments are useless – They are too small to satisfy any request
– A second form of fragmentation waste
• Solutions:
– Try not to create tiny fragments
– Try to recombine fragments into big chunks
CS 111 Spring 2022
Lecture 5 Page 30
How To Avoid Creating Small
Fragments?
• Be smart about which free chunk of memory
you use to satisfy a request
• But being smart costs time
• Some choices: – Best fit
– Worst fit – First fit – Next fit
CS 111 Spring 2022
Lecture 5 Page 31
Allocating Partitions in Memory
CS 111 Spring 2022
Lecture 5 Page 32
• Search for the “best fit” chunk
– Smallest size greater than or equal to requested size
• Advantages:
– Might find a perfect fit
• Disadvantages:
– Have to search entire list every time – Quickly creates very small fragments
CS 111 Spring 2022
Lecture 5 Page 33
Not very useful free segments
Here’s the best fit!
CS 111 Spring 2022
Lecture 5 Page 34
Won’t fit! Won’t fit!
• Search for the “worst fit” chunk
– Largest size greater than or equal to requested size
• Advantages:
– Tends to create very large fragments
… for a while, at least • Disadvantages:
– Still have to search entire list every time
CS 111 Spring 2022
Lecture 5 Page 35
Worst Fit in Action
Won’t fit!
CS 111 Spring 2022
Lecture 5 Page 36
Won’t fit! Won’t fit!
Comparing Best and Worst Fit
Worst fit fit
S 111 Spring 2022
Lecture 5 Page 37
• Take first chunk you find that is big enough
• Advantages:
– Very short searches
– Creates random sized fragments
• Disadvantages:
– The first chunks quickly fragment
– Searches become longer
– Ultimately it fragments as badly as best fit
CS 111 Spring 2022
Lecture 5 Page 38
After each search, set guess pointer to chunk after the one we chose.
That is the point at which we will begin our next search.
CS 111 Spring 2022
guess pointer
Lecture 5 Page 39
Next Fit Properties
• Tries to get advantages of both first and worst fit
– Short searches (maybe shorter than first fit) – Spreads out fragmentation (like worst fit)
• Guess pointers are a general technique
– If they are right, they save a lot of time
– If they are wrong, the algorithm still works
– They can be used in a wide range of problems
CS 111 Spring 2022
Lecture 5 Page 40
Coalescing Partitions
• All variable sized partition allocation algorithms have external fragmentation
– Some get it faster, some spread it out
• We need a way to reassemble fragments
– Check neighbors whenever a chunk is freed
– Recombine free neighbors whenever possible
– Free list can be designed to make this easier • E.g., where are the neighbors of this chunk?
• Counters forces of external fragmentation
CS 111 Spring 2022
Lecture 5 Page 41
Free Chunk Coalescing
Previous chunk is free, so coalesce backwards.
UF RS E DE
Next chunk is also free, so coalesce forwards.
Lecture 5 Page 42
CS 111 Spring 2022
Fragmentation and Coalescing
• Opposing processes that operate in parallel
– Which of the two processes will dominate?
• What fraction of space is typically allocated?
– Coalescing works better with more free space
• How fast is allocated memory turned over?
– Chunks held for long time cannot be coalesced
• How variable are requested chunk sizes?
– High variability increases fragmentation rate
• How long will the program execute?
– Fragmentation, like rust, gets worse with time
CS 111 Spring 2022
Lecture 5 Page 43
Variable Sized Partition Summary • Eliminates internal fragmentation
– Each chunk is custom-made for requestor
• Implementation is more expensive – Long searches of complex free lists – Carving and coalescing
• External fragmentation is inevitable
– Coalescing can counteract the fragmentation
• Must we choose the lesser of two evils?
CS 111 Spring 2022
Lecture 5 Page 44
A Special Case for Fixed Allocations
Internal fragmentation results from mismatches between chunk sizes and request sizes (which we have assumed to be randomly distributed)
But if we look at what actually happens, it turns out that memory allocation requests aren’t random at all.
CS 111 Spring 2022
Lecture 5 Page 45
64 256 1K 4K
Why Aren’t Memory Request Sizes Randomly Distributed?
• In real systems, some sizes are requested much more often than others
• Many key services use fixed-size buffers – File systems (for disk I/O)
– Network protocols (for packet assembly)
– Standard request descriptors
• These account for much transient use – They are continuously allocated and freed
• OS might want to handle them specially
CS 111 Spring 2022
Lecture 5 Page 46
Buffer Pools • Iftherearepopularsizes,
– Reserve special pools of fixed size buffers – Satisfy matching requests from those pools
• Benefit:improvedefficiency
– Much simpler than variable partition allocation
• Eliminates searching, carving, coalescing
– Reduces (or eliminates) external fragmentation
• Butwemustknowhowmuchtoreserve
– Too little, and the buffer pool will become a bottleneck – Too much, and we will have a lot of unused buffer space
• Onlysatisfyperfectlymatchingrequests
CS 111 – Otherwise, back to internal fragmentation
Spring 2022
Lecture 5 Page 47
How Are Buffer Pools Used?
• Process requests a piece of memory for a special purpose
– E.g., to send a message
• System supplies one element from buffer pool
• Process uses it, completes, frees memory
– Maybe explicitly
– Maybe implicitly, based on how such buffers are used
CS 111 Spring 2022
• E.g., sending the message will free the buffer “behind the process’ back” once the message is gone
Lecture 5 Page 48
Dynamically Sizing Buffer Pools
• Ifwerunlowonfixedsizedbuffers – Get more memory from the free list
– Carve it up into more fixed sized buffers
• Ifourfreebufferlistgetstoolarge – Return some buffers to the free list
• Ifthefreelistgetsdangerouslylow
– Ask each major service with a buffer pool to return space
• Thiscanbetunedbyafewparameters: – Low space (need more) threshold
– High space (have too much) threshold
– Nominal allocation (what we free down to)
• Resultingsystemishighlyadaptivetochangingloads
CS 111 Spring 2022
Lecture 5 Page 49
Lost Memory
• One problem with buffer pools is memory leaks
– The process is done with the memory – But doesn’t free it
• Also a problem when a process manages its own memory space
– E.g., it allocates a big area and maintains its own free list
• Long running processes with memory leaks can waste huge amounts of memory
CS 111 Spring 2022
Lecture 5 Page 50
Garbage Collection
• One solution to memory leaks
• Don’t count on processes to release memory • Monitor how much free memory we’ve got
• When we run low, start garbage collection
– Search data space finding every object pointer – Note address/size of all accessible objects
– Compute the complement (what is inaccessible) – Add all inaccessible memory to the free list
CS 111 Spring 2022
Lecture 5 Page 51
How Do We Find All
Accessible Memory?
• Object oriented languages often enable this – All object references are tagged
– All object descriptors include size information
• It is often possible for system resources – Where all possible references are known
• E.g., we know who has which files open • How about for the general case?
CS 111 Spring 2022
Lecture 5 Page 52
General Garbage Collection
• Well, what would you need to do?
• Find all the pointers in allocated memory
• Determine “how much” each points to
• Determine what is and is not still pointed to
• Free what isn’t pointed to
• Why might that be difficult?
CS 111 Spring 2022
Lecture 5 Page 53
Problems With General Garbage Collection
• A location in the data or stack segments might seem to contain addresses, but …
– Are they truly pointers, or might they be other data types whose values happen to resemble addresses?
– If pointers, are they themselves still accessible?
– We might be able to infer this (recursively) for
pointers in dynamically allocated structures …
– But what about pointers in statically allocated (potentially global) areas?
• And how much is “pointed to,” one word or a million?
CS 111 Spring 2022
Lecture 5 Page 54
Compaction and Relocation
Garbagecollectionisjustanotherwaytofree memory
– Doesn’t greatly help or hurt fragmentation Ongoingactivitycanstarvecoalescing
– Chunks reallocated before neighbors become free Wecouldstopacceptingnewallocations
– But processes needing more memory would block until some is freed, slowing the system
Weneedawaytorearrangeactivememory
– Re-pack all processes in one end of memory
– Create one big chunk of free space at other end Spring 2022
Lecture 5 Page 55
Memory Compaction
swap device
Now let’s compact!
free block Largest
free block
CS 111 Spring 2022
An obvious improvement!
Lecture 5 Page 56
All This Requires Is Relocation . . .
• The ability to move a process’ data
– From region where it was initially loaded – Into a new and different region of memory
• What’s so hard about that?
• All addresses in the program will be wrong
– References in the code segment
• Calls and branches to other parts of the code • References to variables in the data segment
– Plus new pointers created during execution • That point into data and stack segments
CS 111 Spring 2022
Lecture 5 Page 57
Real physical addresses
Let’s move the partition!
What’s going to happen the next time we access foo?
Why Is Relocation Hard?
CS 111 Spring 2022
Of course, we copy the partition’s contents when we move it
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com