Memory Management

Address Binding: Program and data are stored on a secondary disk as a binary
executable files. For executing the program, it is brought into memory and placed within
a process. Collection of processes on the disk that are waiting to be brought into
memory for execution forms the input output queue.

As a process executed, it accesses instructions and data from memory. When process
terminates, its memory space is declared available. Most of the operating systems allow
the user process to reside in any part of the physical memory.

User program consist of various types

of instructions and data. It also
accesses various library files while
executing.

Source program uses symbolic

addresses. A compiler will bind these
addresses to relocatable addresses.
ddresses.
Loader will in turn bind these
relocatable addresses to absolute
addresses. Each binding is a mapping
from one address space to another.

Binding of instructions or data to

memory addresses can be done at any
step along the way.

1. Compile Time: If you know at

compile time, where the process
will reside in the memory, then
absolute code can be generated.
2. Load Time: If it is not known at compile time, where the process will reside in
memory then the compiler must generate relocatable code.
 3. Execution Time: Process may be moved from one memory segment to another
memory segment in execution, and then binding must be delayed until run time.

Logical versus Physical Address Space: Logical address is generated by

CPU. Physical address is the address of main memory and it is loaded into the
memory address register

Compile time and load time address binding method generates same logical and
physical address.

Execution times address binding scheme results in different logical and physical
addresses. In this case the logical address is termed as virtual address.

Set of all logical addresses generated by a program is a logical address space. Set of
all physical addresses corresponding to these logical addresses is a physical address
space.

Mapping of logical to physical address is done by a hardware device called memory

management unit (MMU).

The value of relocation register

(Base register) is added in the
value of logical address to
determine the value of physical
address.

Swapping: Swapping is a technique of temporarily removing inactive programs from

the memory of a system. It removes the processes from the primary memory, when it is
blocked and deallocates the memory. This free memory is allocated to other processes.
Contiguous Memory Allocation: The main memory is divided into two partitions:
one for operating system and other one for the user processes.

Memory Protection: Memory protection means protecting the operating system from
user processes and protecting the user processes from one another. This protection can
be provided using a relocation register and a limit register.

 The relocation register contains the value of smallest physical address.

 The limit register contains the range of logical addresses.

Each logical address must be less than the limit register. The MMU maps the logical
address dynamically by adding the value in the relocation. This mapped address is
sent to the memory.
 If any operating code comes and goes as needed, then such OS code is called
transient code. Using this code changes the size of operating system during program
execution.

Memory Allocation: Two methods can be used for memory allocation:

1. Multiple Fixed Size Partitions: In this method memory is divided into several
fixed size partitions. Each partition may contain exactly one process. Thus the
degree of multiprogramming is bound by the number of partitions.
In this method, when a partition is free, a process is selected from the input queue
and is loaded into the free partition. When a process terminates, the partition
becomes available for other processes.
2. Variable Size Partitions: The operating system keeps a table indicating which
part of memory is available and which parts are occupied. Initially all memory is
available and is considered as one large block of available memory, called a hole.
When a process arrives and need memory, we search for a hole that is large
enough to accommodate this process. If we find one, we allocate only as much
memory as needed. The most common methods to select a hole from the set of
available holes are:
a. First Fit: This method allocates the first hole that is large enough for the
process. We can stop searching as soon as we find a free hole that is large
enough to accommodate the process.
b. Best Fit: This method allocates the smallest hole that is large enough for the
process. For this, we must search the entire list.
c. Worst Fit: This method allocates the largest hole. Again we must search the
entire list.
First fit is faster than the best fit and worst fit. These algorithms can suffer
from external fragmentation.

Fragmentation: Fragmentation can be of two types-

1. Internal fragmentation: In internal fragmentation,
there is wasted space internal to a partition because
the block of data loaded is smaller than the partition.
2. External Fragmentation: In external fragmentation
memory exists to satisfy a request but it is not
contiguous, storage
is fragmented into
large number of small holes.

If we are having a hole of 200K and a hole of

500K and a process request for 700 K. We are
having 700 K free memory but we cannot satisfy
the request as this memory is not contiguous. So
there is an external fragmentation of memory.
One technique for overcoming external fragmentation is compaction. In
compaction OS shifts the processes so that they are contiguous and all the free
memory is in one block.
Another possible solution to this problem is allowing non contiguous memory
allocation. For this two techniques are used:

i. Paging
ii. Segmentation

1. Paging: Paging is a memory management scheme that permits the physical

address space of a process to be noncontiguous.
In paging physical memory is broken into fixed size blocks called frames, and
logical memory is also broken into blocks of same size called pages. When a
process is to be executed, its pages are loaded into available memory frames
from the backing storage.
Every address generated by CPU is divided into two parts: a page number (P) and a page
offset (d). The page number is used as an index in page table. The page table contains
the base address of each page in physical memory. This base address is added with the
page offset to define the physical address. The size of a page is a power of 2.

(Paging
Paging Model of Logical and Physical Memory)
Memory
Example: Using a page size of 4 bytes and a physical memory of 32 bytes (8 pages) we
show how the user’s view of memory can be mapped into physical memory.
 Logical address 0
is page 0, offset 0.
By the page table
we can know that
page 0 is in frame
5. Thus logical
address 0 maps to
physical address
20 (= (5 x 4) + 0).
 Logical address 3
(page 0, offset 3)
maps to physical
address 23 (= (5 x
4) + 3).
 Logical address 4
(Page 1, Offset 0).
Page 1 map to
frame 6. Thus
logical address 4 maps to physical address 24 (=(6 x 4) + 0).
In paging, we have no external fragmentation. However, we can have internal
fragmentation.
For example, if pages are of 4 bytes, than a process of 10 bytes will need 2 pages and 2
bytes. So it will be allocated 3 frames, resulting in internal fragmentation of 2 bytes.
Paging hardware with TLB: Translation look a side buffer (TLB) is a small high
speed memory. Each entry in the TLB consists of two parts: A key and a value. The TLB
contains only few page table entries. When a logical address is generated by CPU, its
page number is presented to TLB. If page number is found, its frame number is
immediately available and is used to access memory.
If the page number is not found in TLB (known as TLB miss), a memory reference to the
page table must be made. When the frame number is obtained, we can use this to
access memory.
mory. In addition we add the page number and frame number to TLB, so that
we can find it quickly next time. If the TLB is already full, the operating system must
select one page for replacement.

The percentage of time a particular page is found in the TL

TLBB is called hit ratio.
Protection: To provide protection,
generally an additional bit is
attached to each entry in page
table: a valid-invalid bit.
Example: In a system with 14 bit
address space (0 to 16383), if we
are having a program that uses
only addresses
esses from 0 to 10468,
then addresses in page number 0,
1, 2, 3, 4 and 5 are mapped
normally through the page table.
Any attempt to generate an address in page number 6 and 7 finds that protection bit is
set to invalid.
Structure of Page Table:
1. Hierarchical Page Table: Recent computer system supports large logical addresses.
In such environment, the page table itself becomes very large. So it becomes difficult
to allocate contiguous memory for page table. To solve this problem, two level page
table schemes is used. The page table is divided into number of smaller pieces. In
this, the page table itself is paged.
Example: Consider a system with 32
bits logical address space. The page
size is 4 KB (212). A logical address is
divided into a page number consisting
of 20 bits and a page offset consisting
of 12 bits. As we page the page tables,
so page number is further divided in a
10 bit page number and a 10 bit page
offset. Thus a logical address is as
follows:

Where P1 is index into outer page table,

and P2 is the displacement within the page of the outer page table.
 2. Hashed Page Table: This is used to handle address space larger than 32 bits.
Hash value works as virtual page number. Each entry in the hash table contains a
linked list of elements that hash to the same location. Each element consists of
three fields:
a. The virtual page number.
b. The value of mapped page frame
c. A pointer to the next element in the linked list.

Algorithm works as follows:

i. Virtual page number is taken from virtual address.

ii. Virtual page number is hashed into page table.
iii. Virtual page number is compared with field (a) in the first element of linked list. If
there is a match, the corresponding page frame value (Field b) is used to form the
desired physical address.
iv. If there
here is no matching, entire linked list is searched for a matching.
3. Inverted Page Table: An inverted page table has one entry for each real page (Frame)
of memory. There is only one page table in the system.
Each
ch virtual address in the system consists of ttriplets -
<Process ID, Page Number, Offset>

Each inverted page table entry is a pair (Process ID, Page Number). When a memory
reference
ference occurs, the inverted page table is searched for a match. If a match is found-
found
say at entry i, and then physical address (i, Offset) is generated. If no match is found,
then an illegal address access has been attempted.

Segmentation: Segmentation iiss a memory management scheme, in which logical

address space is a collection of segments. Each segment has a name and a length. For
implementation purpose, segments are numbered and are referred by a segment
number. Thus logical address consists of two tup
tuples:

<Segment_number, Offset>

Segmentation Hardware: In this memory management technique, we use a table called

segment table for mapping the addresses.
Each entry of segment table has a segment base and a segment limit. The segment base
contains the starting
arting physical address and segment limit specifies the length of segment.

A logical address consists of two parts: a segment number S and an offset into that
segment d. The offset value d of the logical address must be between 0 and segment
limit.. If this offset is legal, it is added to base of segment to produce the address in
physical memory.

Example: Consider the situation as

per diagram.

We have five segments numbered

from 0 to 4. The segment table has
separate entry for each segment.

Segmentation
ation may cause external
fragmentation, when all blocks of
free memory are too small to
accommodate a segment.
Segmentation with Paging: In this method, both memory management methods
are combined to give best results. In this method, logical address space is divided into
two parts:

Local Descriptor Table: Consists of segments that are private to that process.

Global Descriptor Table: Consists of segments that are shared among all processes.

The logical address is a pair (Selector, Offset), where the selector is a 16 bit number.

In which S represents the segment number, g indicates, whether the segment is in GDT
or LDT, and P deals with protection.

Offset is a 32 bit number, specifying the location of word within the segment.

Physical address is formed as follows:

 The segment registers points to the appropriate entry in LDT or GDT.

 The base and limit information about the segment is used to generate a linear
address of 32 bits.
 Linear address is divided into a page number of 20 bits and a page offset of 12
bits.
 The page number is further divided into a 10 bit page directory, and a 10 bit page
table pointer as:
We use 2 level paging schemes for address translation to avoid many entries in the page
table.

(Address Translation in Segmentation with Paging)

Virtual Memory: It is a virtual resource of a computer. It is an illusion that a computer

system has more memory than it is actually having.

Virtual memory allows execution of partially loaded processes. Virtual memory also
allows sharing of files and memory by several different processes through page sharing.

Virtual memory is commonly implemented by demand paging. It can also be

implemented by demand segmentation.
Demand Paging: A demand paging system is similar to a paging system with swapping.
We have a lazy swapper for this purpose. A lazy swapper never swaps a page into
memory unless that page will be needed.

When a process is to be swapped in, the pages used before the process is swapped out.
In demand paging, instead of swapping in the whole process, the swapper brings only
necessary pages into memory.

In demand paging, we also need some form of hardware support to differentiate between
the pages that are in memory and that are in disk. Generally valid-Invalid bit scheme is
used for this purpose.

A valid bit indicates that the page is both legal and in memory. An invalid bit indicates
that the page is either not valid or page is valid but is currently on the disk. Access to a
page marked invalid causes a page fault. The procedure to handle the page fault is as
follows:

1. We check the page table to determine whether the reference was a valid or invalid
memory access.
 2. If reference was invalid, we terminate the process. If it is valid and we have not yet
brought the page into memory, we must page it in.
3. We search for a free frame (from free frame list).
4. We read the desired page into allocated frame.
5. When disk read is complete, page table is modified to indicate that page is now in
memory.
6. We restart the instruction
struction that was interrupted by illegal address trap.

In extreme case, we can use pure demand paging i.e. never bring a page into memory
until it is required.

Performance of demand paging: We calculate effective access time to find out the
performance of demand paging. Suppose memory access time is ma. As long as we have
no page faults, effective access time is equal to memory access time.

Let P be the probability of a page fault (0 ≤ P ≤ 1). Than effective access time

= (1 - P) x ma + P x page fau
fault time.
Page Replacement: If any page fault occurs then following steps are followed-

1. Find the location of desired page on the disk.

2. Find a free frame:
a. If there is a free frame, use it.
b. If there is no free frame, use a page replacement algorithm to select a victim
frame.
c. Write the page to the disk and modify the page and frame table accordingly.
3. Read the desired page into free frame and modify the page and frame table.
4. Restart the user process.

Page replacement is basis to demand paging. With this method, virtual memory can
be provided for programmers on a smaller physical memory.

To implement demand paging, we must develop some frame allocation algorithm and
some page replacement algorithms.

Page Replacement Algorithm:

 1. FIFO Page Replacement: In this algorithm, a time was associated with each
page, when the page was brought into main memory. To replace the page, we
chose the oldest page for replacement.
Example 1: Consider the reference string:
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 with three frames.

7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 7 7 2 2 2 4 4 4 0 0 0 7 7 7

0 0 0 3 3 3 2 2 2 1 1 1 0 0

1 1 1 0 0 0 3 3 3 2 2 2 1

Total Page Faults = 15

Example 2: Consider a reference string:

1 2 3 4 1 2 5 1 2 3 4 5 with three frames.

1 2 3 4 1 2 5 1 2 3 4 5
1 1 1 4 4 4 5 5 5
2 2 2 1 1 1 3 3
3 3 3 2 2 2 4

Total Page Fault = 9

If we use 4 frames in place of 3 frames

1 2 3 4 1 2 5 1 2 3 4 5

1 1 1 1 5 5 5 5 4 4

2 2 2 2 1 1 1 1 5

3 3 3 3 2 2 2 2

4 4 4 4 3 3 3

Total page Fault = 10

For some page replacement algorithms, the page fault rate may increase, as the number
of allocated frames increases. This most unexpected result is called Belady’s Anomaly.

2. Optimal Page Replacement Algorithm: According to this algorithm ‘Replace the

page that will not be used for the longest period of time.’
This page replacement algorithm guarantees the lowest page fault rate for a fixed
number of frames.
Example: Consider the reference string:
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 with three frames.
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

7 7 7 2 2 2 2 2 7

0 0 0 0 4 0 0 0

1 1 3 3 3 1 1

Number of page faults = 9

Unfortunately, optimal page replacement algorithm is difficult to implement,

because it requires future knowledge of the reference string.

3. LRU Page Replacement Algorithm: In this method, we replace the page that has
not been used for the longest period of time.
Example: Consider the reference string:
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 with three frames.

7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

7 7 7 2 2 4 4 4 0 1 1 1

0 0 0 0 0 0 3 3 3 0 0

1 1 3 3 2 2 2 2 2 7

Number of page faults = 12.

Frame Allocation: Frame allocation can be done in two ways:

 1. Equal Allocation: This is easiest method to split m frames among n processes
and to give everyone an equal share of m/n frames. Sometimes this scheme
wastes a lot of memory.
Example: Consider a system with 1 KB frame size. Suppose, there are only two
processes in the system, one of 10 KB and another of 127 KB. System contains
memory of 62 frames. Both processes are allocated equal (i.e. 31 frames). The
small process does not need more than 10 frames, thus 21 frames are wasted.
2. Proportional Allocation: We allocate the available memory to each process
according to its size.
Let the size of memory for process P i is Si and define
S = ∑ Si
Then if total number of available frames is m, we allocate a i frames to process
Pi, Where ai is approximately
ai ≈ (Si/S) x m
Example: In proportional allocation, we would split 62 frames between two
processes, one of 10 pages and one of 127 pages by allocating 5 frames and 57
frames respectively. Since -
(10/132) x 62 ≈ 5

(127 / 132) x 62 ≈ 57

Thrashing: Thrashing is when the page fault and swapping happens very frequently
at a higher rate, and then the operating system has to spend more time swapping
these pages. This state in the operating system is known as thrashing. Because of
thrashing, the CPU utilization is going to be reduced or negligible.

The basic concept involved is that if a process is allocated less number of frames, then
there will be frequently page faults. As a result, no valuable work would be done by the
CPU, and the CPU utilization would fall drastically.

The long-term scheduler would then try to improve the CPU utilization by loading some
more processes into the memory, thereby increasing the degree of multiprogramming.
Unfortunately, this would result in a further decrease in the CPU utilization, triggering
 a chained reaction of higher page faults followed by an increase in the degree of
multiprogramming, called thrashing.

Global Vs Local Replacement: Global replacement allows a process to select a

replacement frame from the set of all frames, even if that frame is allocated to some
other process.
Local replacement requires that each process select frames only from its own set of
allocated frames.
Example: Consider an allocation scheme, where we allow a high priority process to
select frames from the low priority processes for replacement. This approach allows a
high priority process to increase its frame allocation at the cost of low priority process.
With a local replacement strategy, the number of frames allocated to each process
proc does
not change.

Cache Memory Organization: The data or contents of the main memory that are
used frequently by CPU are stored in the cache memory so that the processor can easily
access that data in a shorter time. Whenever the CPU needs to access memory,
me it first
checks the cache memory. If the data is not found in cache memory, then the CPU
checks data into the main memory.
Cache memory is placed between the CPU and the main memory.
Characteristics of Cache Memory
a. Cache memory is an extremely fast memory type that acts as a buffer between
RAM and the CPU.
b. Cache Memory holds frequently requested data and instructions so that they are
immediately available to the CPU when needed.
c. Cache memory is costlier than main memory or disk memory but more economical
econom
than CPU registers.
d. Cache Memory is used to speed up and synchronize with a high
high--speed CPU.
Levels of Memory
a. Level 1 or Register: It is a type of memory in which data is stored and accepted
that are immediately stored in the CPU. The most commonly used
use register is
Accumulator, Program counter, Address Register, etc.
b. Level 2 or Cache memory: It is the fastest memory that has faster access time
where data is temporarily stored for faster access.
c. Level 3 or Main Memory: It is the memory on which the computer
compu works
currently. It is small in size and once power is off data no longer stays in this
memory.
d. Level 4 or Secondary Memory: It is external memory that is not as fast as the
main memory but data stays permanently in this memory.
 Important Questions
1. Define address binding. What is the difference between dynamic loading and
dynamic linking?
2. Define logical address and physical address.
3. What is logical address space and physical address space?
4. What are the methods of contiguous memory allocation?
5. Define first fit, best fit and worst fit methods of memory allocation.
6. Differentiate demand paging with pure demand paging. What is lazy swapper?
7. Explain Paging with example. Differentiate Paging and Segmentation.
8. Explain the difference between External fragmentation and Internal fragmentation.
How to solve the fragmentation problem using paging.
9. Illustrate the page-replacement algorithms
i. FIFO
ii. Optimal Page Replacement
use the reference string 7, 0,1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2,1, 2, 0, 1, 7, 0,1 for a
memory with three frames.
10. Consider the following page-reference string:
1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6
How many page faults would occur for the following replacement algorithms,
assuming frame size is 4? Remember that frames are initially empty?
(i) LRU replacement
(ii) FIFO replacement
(iii) Optimal replacement
11. Define virtual memory.
12. What do you mean by Belady's anomaly? Which algorithm suffers from Belady’s
anomaly and how can it be rectified?
13. What is Thrashing? What is the cause of Thrashing? How does the system detect
Thrashing? What can the system do to eliminate this problem?
14. Consider the following page reference string:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 1, 5, 6
 How many page faults would occurs for the following replacement algorithms,
assuming three frames.
i. LRU Page Replacement
ii. FIFO Page Replacement
iii. Optimal Page Replacement
15. When do page fault occurs? Describe in details the actions taken by operating
system when a page fault occurs.
16. What is paging? Describe how logical address is translated to physical address in
a paged system. Further give reasons as to why page size is always a power of 2?
17. Given memory partition of 100 K, 500 K, 200 K, 300 K, and 600 K (in order) how
would each of the first-fit, best-fit and worst-fit algorithms place processes of 212
K, 417 K, 112 K, and 426 K (in order)? Which algorithm makes the most efficient
use of memory?