Unit III Memory Management

Main Memory – Contiguous Memory Allocation – Paging –

Segmentation – Segmentation with Paging Virtual Memory – Demand

Paging – Copy on Write – Page Replacement (FIFO, LRU, Optimal) –

Allocation of Frames – Thrashing

 Memory Management
Memory is large array of words or bytes, each having its unique address. CPU
fetches instructions from memory according to value of program counter. The
instructions undergo instruction execution cycle. To increase both CPU utilization
and speed of its response to users, computers must keep several processes in
memory. Specifically, the memory management modules are concerned with
following four functions:
1. Keeping track of whether each location is allocated or unallocated, to which
process and how much.
2. Deciding to whom the memory is allocated, how much, when and where. If
memory is to be shared by more than one process concurrently, it must be
determined which process’ request should be satisfied.
3. Once it is decided to allocate memory, the specific locations must be selected
and allocated. Memory status information is updated.
4. Handling the deallocation/reallocation of memory. After the process holding
memory is finished, memory locations held by it are declared free by changing the
status information.
There are varieties of memory management systems. They are:
 Contiguous Memory Management: In this approach, each program
occupies a single contiguous block of storage locations.
 Non-Contiguous Memory Management: In these, a program is divided
into several blocks or segments that may be placed throughout main storage
in pieces or chunks not necessarily adjacent to one another. It is the function
of Operating System to manage these different chunks in such a way that
they appear to be contiguous to the user.
Binding of Instructions and Data to Memory: the binding of data and program
to memory address can be done at any of the following steps:
 Compile Time: Binding at compile time generates absolute addresses where
a prior knowledge is required that where a process resides in the memory.
After sometime if the starting location of a process in memory is changed,
then the entire process must be recompiled to generate the absolute address
again.
 Load Time: at compile time if it is not known that where a process will
reside in memory then the compiler must generate relocatable address. In
this case, final binding is delayed until load time. If the starting address is
 changed then we need only to reload the user code to incorporate this
changed value.
 Execution Time: this method permits moving a process from one memory
segment to another during rum time. In this case, final binding is delayed
until run time.

Most systems allow a user process to reside in any part of the physical memory. In
most cases, a user program will go through several steps- some of which are
optional-before being executed as shown in figure 1. Addresses may be represented
in different ways during these steps. Addresses in the source programs are
generally symbolic. A compiler will bind these addresses to relocatable addresses.
The linkage editor or loader will bind these addresses to absolute addresses. Each
binding is a mapping from one address space to another.

Fig 1: Multistep processing of a user program

 Logical And Physical Addresses: An address generated by the CPU is commonly
refereed as Logical Address, whereas the address seen by the memory unit, that is
one loaded into the memory address register of the memory is commonly refereed
as the Physical Address. The compile time and load time address binding
generates the identical logical and physical addresses. However, the execution
times address binding scheme results in differing logical and physical addresses.
The set of all logical addresses generated by a program is known as Logical
Address Space, whereas the set of all physical addresses corresponding to these
logical addresses is Physical Address Space. Now, the run time mapping from
virtual address to physical address is done by a hardware device known as
Memory Management Unit (MMU).
Here in the case of mapping the base register is known as relocation register. The
value in the relocation register is added to the address generated by a user process
at the time it is sent to memory. Let's understand this situation with the help of
example: If the base register contains the value 1000, then an attempt by the user to
address location 0 is dynamically relocated to location 1000, an access to location
346 is mapped to location 1346 as illustrated in Figure 2

Fig 2: Dynamic relocation using a relocation register

Dynamic Loading
 Routine is not loaded until it is called.
 All routines are kept on disk in a relocatable load format.
 The main program is loaded into memory and is executed. When a routine
 needs to call another routine, the calling routine first checks to see whether
the other the desired

 Routine into memory and to update the program’s address tables to reflect this
change. Then control is passed to the newly loaded routine.
 Better memory-space utilization; unused routine is never loaded.
 Useful when large amounts of code are needed to handle infrequently occurring
cases.
 No special support from the operating system is required.
 Implemented through program design.

Dynamic Linking
 Linking is postponed until execution time.
 Small piece of code, stub, is used to locate the appropriate memory-
resident library routine, or to load the library if the routine is not already
present.
 When this stub is executed, it checks to see whether the needed routine
is already in memory. If not, the program loads the routine into memory.
 Stub replaces itself with the address of the routine, and executes the routine.
 Thus the next time that code segment is reached, the library routine is
executed directly, incurring no cost for dynamic linking.
 Operating system is needed to check if routine is in processes’ memory address.
 Dynamic linking is particularly useful for libraries.

Swapping: Swapping is a memory management scheme in which any process can

be temporarily swapped from main memory to secondary memory so that the main
memory can be made available for other processes. It is used to improve main
memory utilization. In secondary memory, the place where the swapped-out
process is stored is called swap space.
Fig 3: Swapping of two processes using a disk as a backing store
A variant of this swapping policy is used for priority-based scheduling algorithms.
If a higher- priority process arrives and wants service, the memory manager can
swap out the lower-priority process so that it can load and execute higher-priority
process. When the higher-priority process.

Finishes, the lower-priority process can be swapped back in and continued. This variant
of swapping is sometimes called roll out, roll in.
Contiguous Allocation: In contiguous memory allocation, all the available
memory space remain together in one place. It means freely available memory
partitions are not scattered here and there across the whole memory space. The
main memory must accommodate both the operating system and the various user
processes. The memory is usually divided into two partitions, one for the resident
operating system, and one for the user processes.
In the contiguous memory allocation when any user process request for the memory
a single section of the contiguous memory block is given to that process according
to its need. We can achieve contiguous memory allocation by dividing memory
into the fixed-sized partition.
A single process is allocated in that fixed sized single partition. But this will
increase the degree of multiprogramming means more than one process in the main
memory that bounds the number of fixed partition done in memory. Internal
fragmentation increases because of the contiguous memory allocation.
Fig 4: Contiguous Memory Allocation

Fixed sized partition: In the fixed sized partition the system divides memory into
fixed size partition (may or may not be of the same size) here entire partition is
allowed to a process and if there is some wastage inside the partition is allocated to a
process and if there is some wastage inside the partition then it is called internal
fragmentation.

Variable size partition: In the variable size partition, the memory is treated as one
unit and space allocated to a process is exactly the same as required and the
leftover space can be reused again.

This procedure is a particular instance of the general dynamic storage-allocation

problem, which is how to satisfy a request of size n from a list of free holes. There
are many solutions to this problem. The set of holes is searched to determine which
hole is best to allocate, first-fit, best-fit, and worst-fit are the most common
strategies used to select a free hole from the set of available holes.

 First-fit: Allocate the first hole that is big enough. Searching can start either
at the beginning of the set of holes or where the previous first-fit search
ended. We can stop searching as soon as we find a free hole that is large
enough.
 Best-fit: Allocate the smallest hole that is big enough. We must search the
entire list, unless the list is kept ordered by size. This strategy-produces the
smallest leftover hole.
  Worst-fit: Allocate the largest hole. Again, we must search the entire list
unless it is sorted by size. This strategy produces the largest leftover hole
which may be more useful than the smaller leftover hole from a best
approach.

The disadvantage of contiguous memory allocation is fragmentation. There are

two types of fragmentation, namely, internal fragmentation and External
fragmentation.

Internal fragmentation: When memory is free internally, that is inside a process

but it cannot be used, we call that fragment as internal fragment. For example say a
hole of size 1252 bytes is available. Let the size of the process be 1258. If the hole
is allocated to this process, then six bytes are left which is not used. These six bytes
which cannot be used forms the internal fragmentation.

External fragmentation: All the three dynamic storage allocation methods

discussed above suffer external fragmentation. When the total memory space that
is got by adding the scattered holes is sufficient to satisfy a request but it is not
available contiguously, then this type of fragmentation is called external
fragmentation.

The solution to this kind of external fragmentation is compaction. Compaction is a

method by which all free memory that are scattered are placed together in one large
memory block. It is to be noted that compaction cannot be done if relocation is
done at compile time or assembly time. It is possible only if dynamic relocation is
done, that is relocation at execution time.

One more solution to external fragmentation is to have the logical address space
and physical address space to be noncontiguous. Paging and Segmentation are
popular noncontiguous allocation methods.
Non-contiguous memory allocation: In the non-contiguous memory allocation the
available free memory space are scattered here and there and all the free memory
space is not at one place. So this is time-consuming. In the non-contiguous memory
allocation, a process will acquire the memory space but it is not at one place it is at
the different locations according to the
 Process requirement. This technique of non-contiguous memory allocation reduces
the wastage of memory which leads to internal and external fragmentation. This
utilizes all the free memory space which is created by a different process.

Fig 5: Non-contiguous Memory Allocation

Non-contiguous memory allocation is of different types,

 Paging
 Segmentation

Paging: Paging is a memory management scheme that eliminates the need for
contiguous allocation of physical memory. This scheme permits the physical
address space of a process to be non- contiguous.
The physical memory is divided into a number of fixed size blocks, called frames
and the logical address space is also divided into fixed size blocks called pages.
When a process is to be executed, its pages are loaded into any available memory
frames from the backing store. The backing store is also divided into fixed size
blocks that are of the same size of the frames i.e. the size of a frame is same as the
size of a page for a particular hardware.

Every address generated by the CPU is divided into two parts: a page number (p)
and a page offset (d). The page number is used as an index into a page table. The
page table contains the base address of each page in physical memory. This base
address is combined with the page offset to define the physical memory address
that is sent to the memory unit. The paging model of memory is shown in figure 6.
The page size like the frame size is defined by the hardware. The size of a page is
typically a power of 2, varying between 512 bytes and 16 MB per page depending
on the computer architecture. The selection of a power of 2 as a page size makes
the translation of a logical address into a page number and page offset particularly
easy. If the size of logical address is 2m , and a page size is 2n addressing units,
then the high order m-n bits of a logical address designate the page number, and
the n low order bits designate the page offset.

Fig 6: Paging System

Paging Example: consider the memory in figure 7. 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. Indexing into the page table, we find that the page 0 is in frame 5. Thus logical
address 0 maps to physical address 20(=(5x4)+0). Logical address 3 (page 0, offset
3) maps to physical address 23(=(5x4)+3). Logical address 4 is page 1, offset 0,
according to the page table, page 1 is mapped to frame 6. Thus, logical address 4
maps to physical address 24(=(6x4)+0). Logical address 13 maps to physical
address 9.
When we use a paging scheme, we have no external fragmentation. Any free frame
can be allocated to a process that needs it. However, we may have some internal
fragmentation.
 0 a 0
1 b
2 c
3 d
4 e 0 5
5 f 4 i
1 6
6 g j
2 1 k
7 h 3 2
8 i l
Page Table
9 j 8 m
10 k n
11 l o
12 m p
13 n
12
14 o
15 p
Logical memory
16

20 a
b
c
d
24 e
f
g
h
28

Physical memory

Fig 7: Paging example for a 32-byte memory with 4 byte pages

 Segmentation: In Operating Systems, Segmentation is a memory management
technique in which, the memory is divided into the variable size parts. Each part is
known as segment which can be allocated to a process. The details about each
segment are stored in a table called as segment table. Segment table is stored in
one (or many) of the segments.

Segment table contains mainly two information about

segment:

 Base: It is the base address of the segment

 Limit: It is the length of the segment.

Segment base contains the starting physical address where the segment resides in

memory, whereas segment limit specifies the size of segment. The use of segment
table is illustrated in the figure 8.
Fig 8: Segmentation Hardware
Logical address consists of two parts ‘s’ and ‘d’. The value of offset ‘d’ must be
between 0 and the segment limit. If it is not so, then we trap to the operating system
with an error message in addressing which indicates that the logical address attempt
beyond the size of segment. If the offset value is legal then it is added to the
segment base to produce the address in the physical memory of the desired byte.
Example: consider the following segment table:

Segment Base Length

0 219 600
1 2300 14
2 90 100
3 1327 580
4 1952 96
What are the physical addresses for the following logical addresses?
(a) 0430
(b) 110
(c) 2500
(d) 3400
(e) 4112

Sol. For the given logical address the first digit refers to the segment number (s)
while remaining digits refers to the offset value (d).
(a) 0430 the first digit 0 refers to segment 0 and 430 refers to offset value
for the logical address (0430). Also the size of segment 0 is 600 as shown in
given table

So Physical address for logical address 0430 would be

=base + offset (430) = 219+430= 649
(b) Physical address for 110 = 2300 + 10 = 2310
(c) Physical address for 2500 = 90 + 500 = 590

But it is impossible since the segment size is 100 so it is illegal address.

(d) Physical address for 3400 = 1327 + 400 = 1727
(e) Physical address for 4112 = illegal address as the size of segment 4 (96<offset
value 112)
Virtual Memory

 A computer can address more memory than the amount physically installed
on the system. This extra memory is actually called virtual memory and it
is a section of a hard disk that's set up to emulate the computer's RAM.
 The main visible advantage of this scheme is that programs can be larger than
physical memory. Virtual memory serves two purposes.
 First, it allows us to extend the use of physical memory by using disk.
 Second, it allows us to have memory protection, because each virtual
address is translated to a physical address.

Following are the situations, when entire program is not required to

be loaded fully in main memory.

User written error handling routines are used only when an error occurred in the data or
computation.
Certain options and features of a program may be used rarely. Many tables are assigned a
fixed amount of address space even though only a small amount of the table is actually
used.
The ability to execute a program that is only partially in memory

would counter many benefits.

Less number of I/O would be needed to load or swap each user

program into memory.

A program would no longer be constrained by the amount of physical memory that is
available.
Each user program could take less physical memory, more programs could be run the same time,
with a corresponding increase in CPU utilization and throughput.

• Modern microprocessors intended for general- purpose use, a memory

management unit, or MMU, is built into the hardware. The MMU's job is to
translate virtual addresses into physical addresses. A basic example is given
below −

•
Virtual memory is commonly implemented by demand paging. It can also be
implemented in a segmentation system. Demand segmentation can also be used
to provide virtual memory.
Demand Paging

• A demand paging system is quite similar to a paging system with swapping

where processes reside in secondary memory and pages are loaded only on
demand, not in advance.
• When a context switch occurs, the operating system does not copy any of
the old program’s pages out to the disk or any of the new program’s pages
into the main memory
• Instead, it just begins executing the new program after loading the first
page and fetches that program’s pages as they are referenced.
• While executing a program, if the program references a page which is not
available in the main memory because it was swapped out a little ago, the
processor treats this invalid memory reference as
a page fault and transfers control from the program to the
operating system to demand the page back into the memory.
• Advantages
• Following are the advantages of Demand Paging −
• Large virtual memory.
• More efficient use of memory.
• There is no limit on degree of multiprogramming.
• Disadvantages
• Number of tables and the amount of processor overhead for handling page
interrupts are greater than in the case of the simple paged management
techniques.
The various partition allocation

schemes

• :
• 1. First Fit: In the first fit, partition is allocated which is first sufficient from
the top of Main Memory.
• 2. Best Fit Allocate the process to the partition which is first smallest
sufficient partition among the free available partition.
• 3. Worst Fit Allocate the process to the partition which is largest sufficient
among the freely available partitions available in the main memory.
• 4. Next Fit Next fit is similar to the first fit but it will search for the
first sufficient partition from the last allocation point.

Page Replacement Algorithms

The page replacement algorithm decides which memory page is to be replaced. The
process of replacement is sometimes called swap out or write to disk. Page replacement
is done when the requested page is not found in the main memory (page fault).
Types of Page Replacement Algorithms
There are various page replacement algorithms. Each algorithm has a different method
by which the pages can be replaced.

Optimal Page Replacement algorithm → this algorithms replaces the page which
will not be referred for so long in future. Although it can not be practically
implementable but it can be used as a benchmark. Other algorithms are compared to
this in terms of optimality.
Least recent used (LRU) page replacement algorithm → this algorithm replaces the
page which has not been referred for a long time. This algorithm is just opposite to the
optimal page replacement algorithm. In this, we look at the past instead of staring at
future.
FIFO → in this algorithm, a queue is maintained. The page which is assigned the
frame first will be replaced first. In other words, the page which resides at the rare end
of the queue will be replaced on the every page fault.
First In First Out (FIFO)
This is the simplest page replacement algorithm. In this algorithm, the OS
maintains a queue that keeps track of all the pages in memory, with the oldest page
at the front and the most recent page at the back.
When there is a need for page replacement, the FIFO algorithm, swaps out the
page at the front of the queue, that is the page which has been in the memory for
the longest time.
 Advantages
 Simple and easy to implement.
Low overhead.

Disadvantages

 Poor performance.

 Doesn’t consider the frequency of use or last used

 time, simply replaces the oldest page.

Least Recently Used (LRU)

Least Recently Used page replacement algorithm keeps track of page usage over a
short period of time. It works on the idea that the pages that have been most heavily
used in the past are most likely to be used heavily in the future too.

In LRU, whenever page replacement happens, the page which has not been used for the
longest amount of time is replaced.
 Page Fault ratio = 8/12

Advantages

 Efficient.

Disadvantages
 Complex
Implementation.
 Expensive.
 Requires hardware
support.
 Optimal Page Replacement
Optimal Page Replacement algorithm is the best page replacement algorithm as it
gives the least number of page faults. It is also known as OPT, clairvoyant
replacement algorithm, or Belady’s optimal page replacement policy.

In this algorithm, pages are replaced which would not be used for the longest duration
of time in the future, i.e., the pages in the memory which are going to be referred
farthest in the future are replaced.

Page Fault ratio = 6/1

Advantages

 Easy to Implement.
 Simple data structures are used. Highly
efficient.

Disadvantages
 Requires future knowledge of the program. Time-
consuming
Allocation of frames

When many processes are kept in the physical memory, the way in which the physical frames
are allocated to the different processes is called allocation of frames. For example, if there are
50 free frames and five processes, how many frames does each process get?

In pure demand paging, all the 50 physical frames are in the list of free frames. During
execution, page faults occur and the necessary pages are brought in to the free frames. If there is
no free frame, a page replacement algorithm is used. After termination of a process, the frames
that the process used are added back to the free frame list.

There is another variant where free frames are always kept available. When there is a page
fault, a victim page is selected. But before moving out the victim page, the required page is
moved into one of the free frames. The victim page is later moved out and the corresponding
frame where the victim page was kept is moved to the list of free frames.

There are few constraints while allocating frames. It is not possible to allocate frames more
than the total number of available frames. It is also needed that each process must be allocated
at least a minimum number of frames. This is because, when the number of frames allocated to
a process decreases, page-fault rate increases.

29.2.1 Minimum Number of Frames

Each process should be allocated a minimum number of frames. But the minimum number
depends on the instruction-set. It depends on the number of pages that a single instruction can
reference. If there is a machine in which all the memory-reference instructions refer to only one
memory address, then it is enough to allocate a minimum of two frames for the process. That
is, one frame for instruction and one frame for the memory reference. Suppose the instruction
set supports one level of indirect level addressing, then a minimum of three frames must be
allocated per process. If there are multiple levels of indirection, then there are more problems.
Hence it is necessary to place a limit on the levels of indirection (usually, 16).

29.2.2 Allocation Algorithms Equal allocation:

The simplest way to split the frames among the processes is to share the frames equally. For
example, if 100 frames are to be shared among 5 processes, each process is given 20 (100/5)
pages. If there are 103 frames and 5 processes, then each process may be given 20 pages and the
remaining 3 frames may be added to the pool of free frames.

Proportional allocation:

But the issue here is that each process has a different size. When each process has a different
size, it is not fair to allocate the same number of frames to all the processes.
 Therefore, it is advantageous to go for proportional allocation. In proportional allocation, the
number of frames allocated to a process is based on the size of the process.

Let si be the size of process pi. Let m be the total number of frames present in the physical
memory.

Therefore the sum of the sizes of all the processes S = Σ si. The allocation for process pi is ai
= si / S x m.
Consider an example where m = 64. Suppose there are two processes p1, p2. Let the size of
process p1 be s1 = 10. Let the size of process p2 be s2 = 127.
The number of frames allocated to process p1 is a1 = 10/137×64 = 5. The number of frames
allocated to process p2 is a2 = 127/137×64 = 159.
Thus, we see that process p1 gets less number of frames because it has a smaller size.
Process p2 gets more number of frames because it is larger.

Priority Allocation:

In this method, frames are proportionally allocated using priorities rather than the size. It is
also possible to allocate frames based on a combination of size and priority.

Global vs. Local Allocation

Another issue that occurs when multiple processes compete for frames is explained in this
section. Suppose process Pi generates a page fault. Hence, the required page of process Pi has
to be brought into the physical memory. Suppose there is no free frame and a victim frame has
to be selected for page replacement. Now, there are two possibilities in selecting the victim
frame. One possibility is that the victim frame selected can be one of the frames allocated to
process Pi. This is called local replacement. The other possibility is that the page selected for
replacement can be a frame from a process (which may or may not be Pi) with a lower priority
number. This is called global replacement.

Global replacement:In global replacement, since a process selects a replacement frame from
the set of all frames, one process can take a frame from another. This allows a high priority
process to select frames from a low priority process. This may increase the number of frames
allocated to a high priority process. However, the low priority processes will still suffer from
page faults, since the high priority process takes frames from the low priority process.
Therefore, the set of pages in memory for a process may depend on the paging behaviour of
other processes.

Local replacement:In local replacement, each process selects from only its own set of
allocated frames. Therefore, the number of frames allocated to a process does not change. The
set of pages in memory for a process is affected by the paging behaviour of only that process.
But a process may not be able to use other less used pages of other processes.

Global replacement gives better throughput and hence, global replacement is commonly used.
 Thrashing

If a process does not have enough frames, the page-fault rate is very high. If all allocated
pages are active page replacement will lead to more page faults. Suppose a process is allocated
5 frames and all pages are active. If there is a page fault now for that process, one of the 5 active
frames is moved out and the required page is brought in. Since the page that is moved out is an
active page, the moved out page may be needed immediately. There is a page fault again and
another active page is moved out to bring in the required page. This leads to page faults again
and again.

When the number of page faults becomes more, the system spends most of the time in paging
activity (moving in and moving out pages). This results in low CPU utilization. Since the CPU
utilization is low, the operating system thinks that there are not enough processes to use the
CPU. Therefore, the operating system increases the degree of multiprogramming. That is, it
adds another process to the system. This increases the paging activity even further. This results
in thrashing, where a process spends more time on paging than executing.

Suppose global page replacement is used. If the currently executing process needs more
frames, it takes frames currently allocated to other processes. This makes the other processes
also to fault, taking frames from other processes. This activity continues and leads to a high
paging activity. This decreases the CPU utilization further. The degree of multiprogramming is
further increased and the CPU utilization is further reduced.

Fig. 29.1 Thrashing ()

Figure 29.1 shows that the CPU utilization increases with the increase in the degree of
multiprogramming to a certain extent. If the degree of multiprogramming is increased
still further, it results in the decrease of CPU utilization. This worsens the thrashing.

The effects of thrashing can be minimized by using a local replacement strategy. It is also
necessary that the process is provided with as many frames as it needs at a particular time. That
is, the process must be given some minimum number of frames so that page faults seldom occur
and a local replacement strategy must be used.
 Locality model of process execution:

The minimum number of frames to be allocated for a process may be decided based on the
number of pages in the locality of the process at a particular time. The locality of a process
refers to the set of pages that are used together by a process at a particular time. Any program is
composed of several localities. During execution, a process migrates from one locality to
another. For example, suppose a process is executing a subroutine. During that time, the process
executes only the pages in that subroutine. The pages of that subroutine form the locality of the
process during that time. It is possible for localities to overlap. If the number of frames
allocated to a process becomes equal to the number of pages in the locality at that time, no page
fault occurs. Only after the process moves to another locality, page faults may occur. Thus, if
the minimum number of frames allocated to each process is equal to the number of pages in its
locality, there is no page fault.

When the sum of the localities of all the processes becomes more than the total memory size,
then thrashing occurs. We now see two methods used to avoid thrashing – the working set
model and the page-fault frequency scheme.

29.3.1 Working-Set Model

The working-set model is based on the locality of the process. A working set is defined which
is an approximation of the program’s locality. Let D º working-set window be a fixed number of
page references. The working set refers to the set of pages in the most recent D page references.
If a page of a process is active, then that page is present in the working set of that process. If a
page is not used for some time, then that page will be dropped from the working set.

Fig. 29.2 Example of working-set model

The working set size of a process is the total number of pages referenced in the process in the
most recent D references. Consider the example shown in Figure 29.2. Let D = 10 memory
references. At time t1, the working set comprises of the (unique) pages 1,2,5,6 and 7. The
working set size at t1 is 5. At time t2, the working set has changed and it comprises of the pages
3 and 4. The working set size at t2 is 2.
 The accuracy of the working set depends on the selection of D. If D is too small, the working
set will not encompass the entire locality. If D is too large, the working set will
encompass several localities. If D = ¥, the working set will encompass the entire program.

Let WSSi denote the working set size of process Pi. Let D = S WSSi be the total demand of all
the processes. If D > m, that is, if the sum of the working set sizes of all the processes becomes
greater than the total number of frames, thrashing occurs. Therefore, if D > m, then one of the
processes must be suspended. If D < m, that is, if the total demand of all the processes becomes
less than the total number of frames available, then another process is initiated. Thus thrashing
can be avoided. This method also helps in keeping the degree of multiprogramming as high as
possible.

Keeping track of the working set is difficult in this method.

Keeping Track of the Working Set:The working set can be approximated using a fixed
interval timer and a reference bit. For each page, additional 2 bits are kept in memory. For
example, let the working set size D = 10,000 references. Let the timer interrupt after every 5000
time units. Whenever the timer interrupts, the reference bit is copied to the additional bit
maintained in memory and the values of all the reference bits are set to 0. When there is a page
fault, we can examine the current reference bit and the two in-memory bits to determine
whether a page was used within the last 10,000 to 15,000 references. If it was used, at least 1 of
these bits will be on. If it has not been used, these bits will be off. Those pages with at least 1
bit on will be considered to be in the working set. But, this may not be entirely accurate,
because, we really don’t know how many times a page is referenced within the 5000 time units.
To improve the accuracy, we may increase the number of in-memory bits and increase the
frequency of checking the reference bit (say, 10 in-memory bits and interrupt every 1000 time
units).

Page-Fault Frequency Scheme:

The second method to avoid thrashing is the page-fault frequency scheme. Thrashing has a
high a page-fault rate. Therefore, if thrashing can be controlled, page-fault rate can be
controlled.

If the page-fault rate is too low, then it means that the process has more frames than needed
and hence, it must lose frames. If the page-fault rate too high, it means that the process has
fewer frames than needed and the process must gain frames.

Figure 29.3 shows how the page-fault rate varies with the increase in the number of frames.
An upper bound and a lower bound are maintained. If the page-fault rate goes beyond the upper
bound, the number of frames allocated to each process is increased. If the page-fault rate goes
below the lower bound, the number of frames allocated to each process is decreased.