Transcript Memory Management

Memory Management
Chapter 5
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Memory binding
•
•
•
Each entity has a set of attributes, e.g. a variable has
type, size, dimensionality.
Binding is the action of specifying values of attributes of
an entity.
Two types of binding are used in practice:
– Early binding: Restrictive, but leads to efficient execution
– Late binding: Flexible, but may lead to less efficient execution
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Memory binding
•
•
Memory allocation is a binding of the `memory address’
attribute of a data entity
Static and dynamic binding are examples of early and
late binding, respectively
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Features of static and dynamic memory allocation
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Memory allocation preliminaries
•
Stack
– LIFO allocation
– A `contiguous’ data structure
– Used for data allocated `automatically’ on entering a block
•
Heap
– Non-contiguous data structure
– Pointer-based access to allocated data
– Used for `program controlled data’ (PCD data) that is explicitly
allocated and de-allocated in a program, e.g. malloc/calloc
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
A heap before and after freeing an allocation area
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Memory allocation model for a process
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Linking, loading and execution of programs
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Memory binding in programs
•
•
•
The origin of a program is the address of its first
instruction or data byte
A compiler is given an origin specification
It binds instructions and data of a program in accordance
with its origin specification
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Assembly program P and its generated code
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Linking and relocation of programs
•
Linking
– A program may wish to use library functions and other programs
– These library functions and other programs should become a part of the
program
– Linking is the function that performs this action
•
Relocation
– Many program may have the same origin specification, so the address
binding of some of them has to be changed
– A program may have to be executed from a memory area that is
different from the area for which it is compiled
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Linking and relocation of programs
•
Linking and relocation could be performed
– Statically
– Dynamically
•
•
What are the advantages of dynamic linking or
relocation?
How is dynamic linking or relocation performed?
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Program relocation using the relocation register:
(a) program, (b) its view during execution
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Memory protection using bound registers
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Memory protection using memory protection leys
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Kernel actions for memory protection
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Free area management in a heap:
(a) singly linked free list, (b) doubly linked free list
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Heap management: (a) free list,
(b)-(d) allocation using first, best and next fit
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Memory fragmentation
•
•
Fragmentation is the development of un-usably small
areas in memory
It has several consequences
– Memory is wasted
– The OS may run out of space to be allocated
•
Two forms of memory fragmentation
– Internal fragmentation
– External fragmentation
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Forms of memory fragmentation
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
How to counter external fragmentation?
•
Do not allow free memory areas to become too small
– Best fit leads to successively smaller memory areas!
•
•
Combine adjoining free areas into a single larger
memory area
Perform compaction
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Boundary tags
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Merging using boundary tags (a) Free list,
(b) -(d) freeing of areas X, Y or Z
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Memory compaction
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Buddy system
•
When memory is to be allocated
– Allocate the entire free area to satisfy a request, or
– Split a free area into two free areas of equal size
* These areas are called buddies
* One of the buddies is considered for satisfying a memory request
(either completely, or through successive splitting)
•
When memory is to be freed
– It is merged with its buddy, if the buddy is also free
•
Status of blocks is saved in a status map
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
A buddy system
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Buddy system operation when a block is released
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Powers of two allocators
•
•
•
•
•
Allocation is in terms of blocks whose sizes are different
powers of 2
Blocks are not split or merged
Free lists are maintained for different block sizes
The header element contains information about block
status and size. It is stored in the block itself
Header element occupies memory, hence memory
efficiency is low for requests that are powers of two in
size
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Header element in the powers-of-two allocator
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Approaches to memory allocation
•
•
Contiguous memory allocation
– Allocates a single contiguous memory area to a request
– Suffers from fragmentation
– Requires provision to counter fragmentation
Noncontiguous memory allocation
– Allocates a set of disjoint memory areas to a request
– Overcomes certain forms of fragmentation (internal ? External?)
– Requires address translation during execution of programs
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Contiguous memory allocation
•
Fixed partitioned memory allocation
– Partitions are fixed once and for all
– A process is allocated a memory partition that is larger in size
than its maximum requirement
•
Variable partitioned memory allocation
– A process is allocated only as much memory as it needs
– Memory is reused through first-fit, best-fit, etc.
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Internal fragmentation in fixed partitioned allocation
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Memory compaction in variable partitioned
allocation
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Noncontiguous memory allocation
•
•
Several disjoint memory areas may be allocated in
response to a request. However, hardware aids in the
execution of programs.
– User or a process is not aware of noncontiguity
– Hence two views of a process exist
* Logical view: View by the user or process itself.
* Physical view: Actual situation regarding allocation
– The organization of components in the logical view is called logical
organization, and addresses used in it are called logical addresses
– Addresses used in the physical view are called physical addresses
Avoids external fragmentation as no memory area is too
small to be allocated
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Noncontiguous memory allocation
•
How is noncontiguous memory allocation performed?
– A process is considered to consist of a set of components
– Each component is allocated a contiguous area of memory that can
accommodate it
– Each logical address in an instruction is considered to consist of a pair
(component #, byte #)
•
During operation of the process, a hardware unit called
the memory management unit (MMU) converts a
(component #, byte #) pair into an absolute memory
address
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Noncontiguous memory allocation
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Logical and physical views of a process in a
noncontiguous memory allocation
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Schematic of address translation in non-contiguous
memory allocation
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Approaches to Noncontiguous memory allocation
•
Paging
– A process consists of components of a fixed size, called pages
– The page size is a power of 2 and is fixed in the architecture
– Memory is divided into parts called page frames, whose size
matches the size of a page
– The kernel allocates memory to all pages of a process
– The kernel builds a page table that stores information about
addresses of page frames allocated to processes
– The MMU uses information in the page table to perform address
translation
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Paging
•
•
A logical address is split into a pair (page #, word #)
This splitting is performed using bit-splitting since the
page size is a power of 2
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Processes in paging
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Approaches to noncontiguous memory allocation
•
Segmentation
– Each component in a process is a logical unit called a segment,
e.g., a function, a module or an object
– Components have different sizes
– The kernel allocates memory to all components and builds a
segment table
– Each logical address in a segment is a pair of the form (segment
#, byte #)
– The MMU uses the segment table to perform address translation
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
A process Q in segmentation
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Comparison of continuous and noncontinuous
memory allocation
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Kernel memory allocation
•
•
•
•
The kernel creates and destroys data structures used to
store information about user processes and resources at
a very high rate, e.g. PCBs, ECBs.
Hence efficiency of kernel memory allocation directly
influences its overhead
Kernel uses special techniques to perform memory
allocation for its data structures
These techniques exploit the fact that the sizes of many
of these data structures are known in advance, e.g.
PCBs, ECBs.
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Slab allocator
•
•
•
•
•
•
A slab is a fixed sized area of memory
A slab contains data structures of the same kind
A slab is preformatted to contain standard sized slots for
these data structures
A free list indicates which slots are free
If all slabs containing data structures of a specific kind
are full, new slabs are allocated by the kernel
Allocation and de-allocation of memory is very fast
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Format of a slab
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Program forms employed in operating systems
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
(a) a program, and (b) its equivalent overlay
structured program in execution
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Sharing of a program
(a) static sharing, (b) dynamic sharing
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005
Reentrant program (a) structure of program C,
(b)-(c) invocation by A and B.
Chapter 5:
Memory Management
Dhamdhere: Operating Systems—
A Concept-Based Approach
Slide No: ‹#›
Copyright ©2005