Memory Management

Memory Management

❖ Memory management is the act of managing computer memory.

❖ The essential requirement of memory management is to provide

ways to dynamically allocate portions of memory to programs at
their request, and freeing it for reuse when no longer needed.
Memory Management
Memory Management
 Memory Management Requirements

These requirements include the following:

• Relocation
• Protection
• Sharing
• Logical organization
• Physical organization
 Memory Management Requirements

Relocation
• In a multiprogramming system, the available main
memory is generally shared among a number of processes.
• Programmerdoesn’tknow apriori which other programs are
in main memory.
• To maximize processor utilization we need to swap
active processes in and out.
• Hence we need to relocate the processto a different
area of memory.
Logical vs. Physical Address Space
 Hardware Support for Relocation and Limit Registers
• Relocation registers used to protect user processes from each other, and from changing
operating-system code and data
• Relocation register contains value of smallest physical address
• Limit register contains range of logical addresses – each logical address must be
less than the limit register
• Context switch
• MMU maps logical address dynamically
 Memory Management Requirements

• Protection
* Each process should be protected against unwanted interference
by other processes
* Programs in other processes should not be able to reference
memory locations in a process for reading or writing purposes
without permission.
* Hence all memory references generated by a process must be
checked at run time to ensure that they refer only to the memory
space allocated to that process.(Limit Register)
 Memory Management Requirements

• Sharing
* Protection mechanism must allow several processes to access the
same portion of main memory. For example, if a number of
processes are executing the same program, it is advantageous to
allow each process to access the same copy of the program rather
than have its own separate copy.
* Processes that are cooperating on some task may need to share
access to the same data structure.
* The memory management system must allow controlled access to
shared areas of memory without compromising essential
protection.
 Memory Management Requirements

• Logical Organization

* Main memory in a computer system is organized as a linear, or

one-dimensional, address space, consisting of a sequence of bytes
or words.
* Physically Secondary memory is organization is same as main
memory.
* Programs may be organized into modules, some of which are
unmodifiable (read only, execute only) and some of which contain
data that may be modified.
 Memory Management Requirements

* If the OS and H/W effectively is able to handle user programs and

data in the form of modules, then a number of advantages can be
realized:
1. Modules can be written and compiled independently, with all
references from one module to another resolved by the system at
run time.
2. Different degrees of protection (read only, execute only) can be
given to different modules.
3. The modules need to be shared among processes, hence it is easy
for the user to specify the sharing that is desired.
 Memory Management Requirements
• Physical Organization
Computer memory is organized into two levels: main memory and
secondary memory.
* Main memory provides fast access at relatively high cost. Main
memory is volatile: does not provide permanent storage.
* Secondary memory is slower and cheaper than main memory and
is usually not volatile.
Thus secondary memory of large capacity can be provided for
long-term storage of programs and data, while a smaller main
memory holds programs and data currently in use.
The flow of information between main and secondary memory is a
major system concern. The principal operation of memory
management is to bring processes into main memory for execution
by the processor.
Memory Management Techniques
1.Memory Partitioning
 Memory Partitioning

There are two difficulties with the use of partitions: equal-size fixed
•A program may be too big to fit into a partition. In this case, the
programmer must design the program with the use of overlays so
that only a portion of the program need be in main memory at
any one time. When a module is needed that is not present, the
user’s program must load that module into the program’s
partition, overlaying whatever programs or data are there.
•Main memory utilization is extremely inefficient. Any program,
no matter how small, occupies an entire partition.
 Memory Partitioning
Example: There may be a program whose length is less than 2
Mbytes; yet it occupies an 8-Mbyte partition whenever it is swapped
in.
The phenomenon, in which there is wasted space internal to a
partition due to the fact that the block of data loaded is smaller
than the partition, is referred to as internal fragmentation .
Both of these problems can be lessened by using unequal-size
partitions ( Figure b ).
Programs as large as 16 Mbytes can be accommodated without
overlays.
Partitions smaller than 8 Mbytes allow smaller programs to be
accommodated with less internal fragmentation.
Memory Partitioning
Memory Partitioning
 Memory Partitioning

PLACEMENT ALGORITHM
* With equal-size partitions, the placement of processes in memory
is trivial.
* As long as there is any available partition, a process can be loaded
into that partition.
* Because all partitions are of equal size, it does not matter which
partition is used.
* If all partitions are occupied with processes that are not ready to
run, then one of these processes must be swapped out to make
room for a new process.
 Memory Partitioning

PLACEMENT ALGORITHM
With unequal-size partitions, there are two possible ways to assign
processes to partitions.

1. Assign each process to the smallest partition within which it will

fit.
A scheduling queue is maintained for each partition, to hold
swapped-out processes destined for that partition ( Figure a ).
Advantage: Processes are always assigned in such a way as to
minimize wasted memory within a partition (internal
fragmentation).
 Memory Partitioning
Disadvantage:
* Consider a case in which there are no processes
with a size between 12 and 16M at a certain point in time.
* In that case, the 16M partition will remain unused, even though
some smaller process could have been assigned to it.
* A preferable approach would be to employ a single queue
for all processes ( Figure b ).
* When it is time to load a processinto main
memory,the smallest available partition that will hold the
process is selected.
* If all partitions are occupied, then a swapping decision must be
made.
Memory Assignment for Fixed
Partitioning
 Memory Partitioning

Disadvantages of unequal-size partitions

* The number of partitions specified at system generation time

limits the number of active (not suspended) processes in the
system.
* Because partition sizes are preset at system generation time,
small jobs will not utilize partition space efficiently.
 2.Dynamic Partitioning

• The partitions are of variable length and number.

• When a processis brought into main memory, it
is allocated exactly as much memory as it requires and no
more.
e.g. Consider 64 Mbytes of main memory in figure.
* Initially, main memory is empty, except for the OS (a).
* The first three processes are loaded in, starting where the
operating system ends and occupying just enough space for
each process (b, c, d).
* This leaves a “hole” at the end of memory that is too small for a
fourth process. At some point, none of the processes in memory
is ready.
2. Dynamic Partitioning
 2.Dynamic Partitioning

* The operating system swaps out process 2 (e), which leaves

sufficient room to load a new process, process 4 (f).
* Because process 4 is smaller than process 2, another small hole
is created.
* Later, a point is reached at which none of the processes in main
memory is ready, but process 2, in the Ready-Suspend state, is
available.
* Because there is insufficient room in memory for process 2, the
operating system swaps process 1 out (g) and swaps process 2
back in (h).
 2.Dynamic Partitioning

Drawback: External Fragmentation

A situation arrives in which there are a lot of small holes in

memory. As time goes on, memory becomes more and more
fragmented, and memory utilization declines. This
phenomenon is referred to as external fragmentation.
 Compaction

External fragmentation is overcome by compaction :

From time to time, the OS shifts the processes so that they are
contiguous and so that all of the free memory is together in
one block.
In Figure h , compaction will result in a block of free memory of
length 16M. This may well be sufficient to load in an additional
process.
Memory compaction is time consuming.
 Coalescing

* No data movement is required.

* We ambulate adjacent holes.
 Memory Allocation Strategies

* The OS must decide how to assign processes to memory (how

to plug the holes).

* When it is time to load or swap a process into main memory,

and if there is more than one free block of memory of sufficient
size, then the operating system must decide which free block to
allocate.

Three strategies are used: Best-fit, first-fit, and next-fit.

 Memory Allocation Strategies

4. Next-fit: Begins to scan memory from the location of the last placement, and
chooses the next available block that is large enough.
 Memory Allocation Strategies
Example:
* Figure a shows Memory
configuration after a
number of placement and
swapping-out operations.

* Figure shows the

b difference between the
best-, andnext-fit
first-,
placement algorithms in
satisfying a 16-Mbyte
allocation request.
 Memory Allocation Strategies
* Best-fit will search the entire list of available blocks and make
use of the 18-Mbyte block, leaving a 2-Mbyte fragment.
* First-fit results in a 6-Mbyte fragment, and next-fit results in a
20-Mbyte fragment.
Numerical:
1. Consider six memory partitions of size 200 KB, 400 KB, 600
KB, 500 KB, 300 KB and 250 KB. These partitions need to be
allocated to four processes of sizes 357 KB, 210 KB, 468 KB and
491 KB in that order. Perform the allocation of processes using-
First Fit Algorithm, Best Fit Algorithm, Worst Fit Algorithm
 First Fit Algorithm-
Given processes are-
Process P1 = 357 KB
Process P2 = 210 KB
Process P3 = 468 KB
Process P4 = 491 KB

First Fit Algorithm-

 First Fit Algorithm-
Step-02:

Step-03:

Step-04:

•Process P4 can not be allocated the memory.

•This is because no partition of size greater than or equal to the size of
process P4 is available.
Best Fit Algorithm-
Worst Fit
Algorithm-
 Numerical

Let us say the given partitions are: Process P1 = 150 KB, Process P2
= 500 KB, Process P3 = 200 KB, Process P4 = 300 KB and Process
P5 = 550 KB.
How would each of the first-fit, Best-fit, andworst-fit
algorithm place the processes of 220k, 430k, 110k,425k(in order).
Which algorithm is most efficient?
 Paging

* Paging is memory management technique which allows

physical address space of the process to be noncontiguous.

* While reading book only current page that we are reading is

visible, others are not.

* Both unequal fixed-size and variable-size partitions are

inefficient in the use of memory; the former results in internal
fragmentation, the latter in external fragmentation.
 Paging

* Physical address space of a process can be noncontiguous;

* process allocates physical memory whenever the latter is available
* Divide physical memory into fixed-sized blocks called frames
* Size is power of 2, between 512 bytes and 16 Mbytes
* Divide logical memory into blocks of same size called pages
* To run a program of size N pages, need to find N
free frames and load program
* Backing store likewise split into pages
* Set up a page table to translate logical to physical addresses
* System keeps track of all free frames
 Paging
* Some of the frames in memory are in use and some are free.
* A list of free frames is maintained by the OS.
* Process A, stored on disk, consists of four pages. When it is
time to load this process, the OS finds four free frames and
loads the four pages of process A into the four frames
( Figure b ).
* Process B, consisting of three pages, and process C, consisting
of four pages, are subsequently loaded.
* Process B is suspended and is swapped out of main memory.
* All of the processes in main memory are blocked, and the OS
needs to bring in a new process, process D, which consists of
five pages.
Paging
 Paging
* If there are not sufficient unused contiguous frames to hold the
process, operating system still load D using the concept of
logical address.
* The operating system maintains a page table for each process.
The page table shows the frame location for each page of the
process.
* Within the program, each logical address consists of a page
number and an offset/displacement within the page.
* The logical-to-physical address translation is done by processor
hardware.
* The processor must know how to access the page table of the
current process.
 Paging Model of Logical and Physical
Memory

page table to translate logical to physical

addresses
 Paging
* Presented with a logical address (page number, offset), the
processor uses the page table to produce a physical address
(frame number, offset).
* The five pages of process D are loaded into frames 4, 5, 6, 11,
and 12.
* Figure shows the various page tables at this time.
* In addition, the OS maintains a single free-frame list of all the
frames in main memory that are currently unoccupied and
available for pages.
 Address Translation Scheme

* Address generated by CPU is divided into:

* Page number (p) – used as an index into a page table
* which contains base address of each page in physical memory
* Page offset (d) – offset within a page
* combined with base address to define the physical memory address that
is
sent to the memory unit page
offset
page number page offset
p d
m-n
n

* For given logical address space 2m and page size

2n
Paging Hardware
Paging
 Implementation of Page Table

* For each process, Page table is kept in main memory

* Page-table base register (PTBR) points to the page table
* Page-table length register (PTLR) indicates size of the page
table
* In this scheme every data/instruction access requires two memory
accesses
*One for the page table and one for the data / instruction

* The two memory access problem can be solved by the use of a

special fast-lookup hardware cache called associative memory or
translation look-aside buffers (TLBs)
Translation Look-aside Buffers
(TLB)
Translation Look-aside Buffers
(TLB)
Translation Look-aside Buffers
(TLB)
 Segmentation

* A user program can be subdivided using segmentation, in which

the program and its associated data are divided into a number of
segments .
* A logical address using segmentation consists of two parts, in
this case a segment number and an offset.
* Segmentation eliminates internal fragmentation but, like
dynamic partitioning, it suffers from external fragmentation.
Segmentation
 Segmentation
* Each entry in the segment table has a segment base and a
segment limit. The segment base contains the starting physical
address where the segment resides in memory, and the segment
limit specifies the length of the segment.
* A logical address consists of two parts: a segment number, s, and
an offset into that segment, d.
* The segment number is used as an index to the segment table. The
offset d of the logical address must be between 0 and the segment
limit. If it is not, we trap to the operating system (logical
addressing attempt beyond end of segment).
* When an offset is legal, it is added to the segment base to produce
the address in physical memory of the desired byte. The segment
table is thus essentially an array of base-limit register pairs.
Segmentation
 Segmentation
* We have five segments numbered from 0 through 4.
* The segments are stored in physical memory as shown.
* The segment table has a separate entry for each segment, giving
the beginning address of the segment in physical memory (or
base) and the length of that segment (or limit).
* For example, segment 2 is 400 bytes long and begins at
location 4300. Thus, a reference to byte 53 of segment 2 is
mapped onto location 4300 +53= 4353.
* A reference to segment 3, byte 852, is mapped to 3200 (the
base of segment 3) + 852 = 4052.
* A reference to byte 1222 of segment 0 would result in a trap to
the operating system, as this segment is only 1000 bytes long.
 Virtual Memory
* Virtual memory is a technique that allows the execution of
processes that are not completely in memory. Entire program
code not needed at same time
* Virtual memory abstracts main memory into an extremely large,
uniform array of storage, separating logical memory as viewed
by the user from physical memory.
▪ Frees programmers from the concerns of
memory-storage limitations.
▪ Allows processes to share files easily and to
implement shared memory.
▪ More processes can be accommodated i.e. Degree of
Multiprogramming can be increased, increasing CPU utilization.
▪ programs could be larger than physical memory
Virtual Memory
Virtual Memory
 Demand Paging

Virtual memory can be implemented via:

* Demand paging
* Demand segmentation
Demand paging:
Demand Paging
Demand Paging
Demand Paging
 Demand Paging

What happens if the process tries to access a page that was not
brought into memory? Access to a page marked invalid causes a
PAGE FAULT.
Demand Paging
Demand Paging
 Page Replacement Strategies

* If a process of ten pages actually uses only half of them, then demand
paging saves the I/0 necessary to load the five pages that are never
used.
* We could also increase our degree of multiprogramming by running
twice as many processes.
* If we had forty frames, we could run eight processes, rather than the
four that could run if each required ten frames (five of which were
never used).
* If we run six processes, each of which is ten pages in size but uses only
five pages, we have higher CPU utilization and throughput, ten frames
to spare. It is possible, however, that each of these processes, for a
particular data set, may suddenly try to use all ten of its pages,
resulting in a need for sixty frames when only forty are available.
 Page Replacement Strategies
* If we increase our degree of multiprogramming, we are over allocating
memory. While a user process is executing, a page fault occurs.
* The operating system determines where the desired page is residing on
the disk but then finds that there are no free frames on the free-frame list;
all memory is in use.
* The operating system has several options at this point.
• It could terminate the user process. However, demand paging is the operating
system's attempt to improve the computer system's utilization and throughput.
• Users should not be aware that their processes are running on a paged
system-paging should be logically transparent to the user. So this option is not
the best choice.
• The operating system could instead swap out a process, freeing all its frames
and reducing the level of multiprogramming.
The most common solution: Page Replacement
Page Replacement Strategies
Page Replacement Strategies
1. FIFO
1. FIFO
1. FIFO
2. Optimal Algorithm
2. Optimal Algorithm
3. Least-Recently Used (LRU)
Thrashing
Thrashing
Thrashing