UNIT-III

Memory-Management Strategies: Introduction, Swapping, Contiguous memory allocation,

Paging, Segmentation, Examples.
Virtual Memory Management: Introduction, Demand paging, Copy on-write, Page replacement,
Frame allocation, Thrashing, Memory-mapped files, Kernel memory allocation, Examples.
Unit Outcomes:
● Examine the various techniques of allocating memory to processes
● Summarize how paging works in contemporary computer systems
● Understanding the benefits of virtual memory systems
MEMORY MANAGEMENT INTRODUCTION:
Memory management is concerned with managing the primary memory. Memory consists
of array of bytes or words each with their own address. The instructions are fetched from the
memory by the CPU based on the value program counter.
Functions of memory management:

 Keeping track of status of each memory location.

 Determining the allocation policy.
 Memory allocation technique.
 De-allocation technique.

Address Binding:
Programs are stored on the secondary storage disks as binary executable files. When the
programs are to be executed they are brought in to the main memory and placed within a process.
The collection of processes on the disk waiting to enter the main memory forms the input queue.
One of the processes which are to be executed is fetched from the queue and placed in the main
memory. During the execution it fetches instruction and data from main memory. After the process
terminates it returns back the memory space. During execution the process will go through different
steps and in each step the address is represented in different ways. In source program the address is
symbolic. The compiler converts the symbolic address to re-locatable address. The loader will
convert this re-locatable address to absolute address.

Binding of instructions and data can be done at any step along the way:
Compile time:-If we know whether the process resides in memory then absolute code can be
generated. If the static address changes then it is necessary to re-compile the code from the
beginning.
Load time:-If the compiler doesn‟t know whether the process resides in memory then it
generates the re-locatable code. In this the binding is delayed until the load time.

Execution time:-If the process is moved during its execution from one memory segment to
another then the binding is delayed until run time. Special hardware is used for this. Most of
the general purpose operating system uses this method.

1
Logical versus physical address:
The address generated by the CPU is called logical address or virtual address. The address
seen by the memory unit i.e., the one loaded in to the memory register is called the physical address.
Compile time and load time address binding methods generate some logical and physical address.
The execution time addressing binding generate different logical and physical address. Set of
logical address space generated by the programs is the logical address space. Set of physical address
corresponding to these logical addresses is the physical address space. The mapping of virtual
address to physical address during run time is done by the hardware device called memory
management unit (MMU). The base register is also called re-location register. Value of the re-
location register is added to every address generated by the user process at the time it is sent to
memory.

Dynamic re-location using a re-location registers

The above figure shows that dynamic re-location which implies mapping from virtual
addresses space to physical address space and is performed by the hardware at run time. Re- location
is performed by the hardware and is invisible to the user dynamic relocation makes it possible to
move a partially executed process from one area of memory to another without affecting.

Dynamic Loading:
For a process to be executed it should be loaded in to the physical memory. The size of the
process is limited to the size of the physical memory. Dynamic loading is used to obtain better
memory utilization. In dynamic loading the routine or procedure will not be loaded until it is called.
Whenever a routine is called, the calling routine first checks whether the called routine is already
loaded or not. If it is not loaded it cause the loader to load the desired program in to the memory
and updates the programs address table to indicate the change and control is passed to newly called
routine.
Advantage: Gives better memory utilization. Unused routine is never loaded. Do not need
special operating system support. This method is useful when large amount of codes are needed to
handle in frequently occurring cases.

2
 Dynamic linking and Shared libraries:
Some operating system supports only the static linking. In dynamic linking only the main
program is loaded in to the memory. If the main program requests a procedure, the procedure is
loaded and the link is established at the time of references. This linking is postponed until the
execution time. With dynamic linking a “stub” is used in the image of each library referenced
routine. A “stub” is a piece of code which is used to indicate how to locate the appropriate
memory resident library routine or how to load library if the routine is not already present. When
“stub” is executed it checks whether the routine is present is memory or not. If not it loads the
routine in to the memory. This feature can be used to update libraries i.e., library is replaced by a
new version and all the programs can make use of this library. More than one version of the library
can be loaded in memory at a time and each program uses its version of the library. Only the
programs that are compiled with the new version are affected by the changes incorporated in it.
Other programs linked before new version is installed will continue using older libraries this type
of system is called “shared library”.

Swapping
Swapping is a technique of temporarily removing inactive programs from the memory of
the system. A process can be swapped temporarily out of the memory to a backing store and then
brought back in to the memory for continuing the execution. This process is called swapping.
Eg:-In a multi-programming environment with a round robin CPU scheduling whenever the time
quantum expires then the process that has just finished is swapped out and a new process swaps in
to the memory for execution.

A variation of swap is priority based scheduling. When a low priority is executing and
if a high priority process arrives then a low priority will be swapped out and high priority is
allowed for execution. This process is also called as Roll out and Roll in.

Normally the process which is swapped out will be swapped back to the same memory
space that is occupied previously. This depends upon address binding.
If the binding is done at load time, then the process is moved to same memory location. If
the binding is done at run time, then the process is moved to different memory location. This is
because the physical address is computed during run time.
Swapping requires backing store and it should be large enough to accommodate the copies
of all memory images. The system maintains a ready queue consisting of all the processes whose
memory images are on the backing store or in memory that are ready to run. Swapping is constant
by other factors: To swap a process, it should be completely idle. A process may be waiting for an
i/o operation. If the i/o is asynchronously accessing the user memory for i/o buffers, then the
process cannot be swapped.

Contiguous memory allocation:

One of the simplest method for memory allocation is to divide memory in to several
fixed partition. Each partition contains exactly one process. The degree of multi- programming
depends on the number of partitions. In multiple partition method, when a partition is free, process
is selected from the input queue and is loaded in to free partition of memory. When process
terminates, the memory partition becomes available for another process. Batch OS uses the fixed
size partition scheme.
The OS keeps a table indicating which part of the memory is free and is occupied.
When the process enters the system it will be loaded in to the input queue. The OS keeps track of
3
 the memory requirement of each process and the amount of memory available and determines
which process to allocate the memory. When a process requests, the OS searches for large hole for
this process, hole is a large block of free memory available. If the hole is too large it is split in to
two. One part is allocated to the requesting process and other is returned to the set of holes. The set
of holes are searched to determine which hole is best to allocate. There are three strategies to select
a free hole:
o First bit:-Allocates first hole that is big enough. This algorithm scans memory from
the beginning and selects the first available block that is large enough to hold the process.
o Best bit:-It chooses the hole i.e., closest in size to the request. It allocates the
smallest hole i.e., big enough to hold the process.
o Worst fit:-It allocates the largest hole to the process request. It searches for the
largest hole in the entire list.

First fit and best fit are the most popular algorithms for dynamic memory allocation. First fit
is generally faster. Best fit searches for the entire list to find the smallest hole i.e., large enough. Worst
fit reduces the rate of production of smallest holes.
All these algorithms suffer from fragmentation.
Memory Protection:
Memory protection means protecting the OS from user process and protecting
process from one another. Memory protection is provided by using a re-location register, with a
limit register. Re-location register contains the values of smallest physical address and limit register
contains range of logical addresses. (Re-location = 100040 and limit = 74600). The logical address
must be less than the limit register; the MMU maps the logical address dynamically by adding the
value in re-location register. When the CPU scheduler selects a process for execution, the dispatcher
loads the re-location and limit register with correct values as a part of context switch. Since every
address generated by the CPU is checked against these register we can protect the OS and other
users programs and data from being modified.

Fragmentation:
Memory fragmentation can be of two types: Internal Fragmentation External Fragmentation
Internal Fragmentation there is wasted space internal to a portion due to the fact that
block of data loaded is smaller than the partition. Eg:-If there is a block of 50kb and if the
process requests 40kb and if the block is allocated to the process then there will be 10kb of
memory left.

External Fragmentation exists when there is enough memory space exists to satisfy the
request, but it not contiguous i.e., storage is fragmented in to large number of small holes.
External Fragmentation may be either minor or a major problem.
One solution for over-coming external fragmentation is compaction. The goal is to move
all the free memory together to form a large block. Compaction is not possible always. If the
relocation is static and is done at load time then compaction is not possible. Compaction is
possible if the re-location is dynamic and done at execution time.
Another possible solution to the external fragmentation problem is to permit the logical
address space of a process to be non-contiguous, thus allowing the process to be allocated physical
memory whenever the latter is available.

Segmentation
Most users do not think memory as a linear array of bytes rather the users thinks memory as a
collection of variable sized segments which are dedicated to a particular use such as code, data,

4
stack, heap etc. A logical address is a collection of segments. Each segment has a name and length.
The address specifies both the segment name and the offset within the segments. The users specify
address by using two quantities: a segment name and an offset. For simplicity the segments are
numbered and referred by a segment number. So the logical address consists of
<segment number, offset>.
Hardware support: We must define an implementation to map 2D user defined address in to 1D
physical address. This mapping is affected by a segment table. Each entry in the segment table has
a segment base and segment limit. The segment base contains the starting physical address where
the segment resides and limit specifies the length of the segment.

The use of segment table is shown in the above figure: Logical address consists of two parts:
segment number„s‟ and an offset„d‟ to that segment. The segment number is used as an index to
segment table. The offset‟d‟ must bi in between 0 and limit, if not an error is reported to OS. If legal
the offset is added to the base to generate the actual physical address. The segment table is an array
of base limit register pairs.
Protection and Sharing: A particular advantage of segmentation is the association of protection
with the segments. The memory mapping hardware will check the protection bits associated with
each segment table entry to prevent illegal access to memory like attempts to write in to read-only
segment. Another advantage of segmentation involves the sharing of code or data. Each process
has a segment table associated with it. Segments are shared when the entries in the segment tables
of two different processes points to same physical location. Sharing occurs at the segment table.
Any information can be shared at the segment level. Several segments can be shared so a program
consisting of several segments can be shared. We can also share parts of a program.
Advantages: Eliminates fragmentation. x Provides virtual growth. Allows dynamic
segment growth. Assist dynamic linking. Segmentation is visible.
Differences between segmentation and paging:-

Segmentation:

 Program is divided in to variable sized segments. x User is responsible for dividing the
program in to segments.
 Segmentation is slower than paging.
 Visible to user.
 Eliminates internal fragmentation.
 Suffers from external fragmentation.
 Process or user segment number, offset to calculate absolute address.
Paging:

 Programs are divided in to fixed size pages.

5
  Division is performed by the OS.
 Paging is faster than segmentation.
 Invisible to user.
 Suffers from internal fragmentation.
 No external fragmentation.
 Process or user page number, offset to calculate absolute address.

Paging
Paging is a memory management scheme that permits the physical address space of a
process to be non-contiguous. Support for paging is handled by hardware. It is used to avoid
external fragmentation. Paging avoids the considerable problem of fitting the varying sized memory
chunks on to the backing store. When some code or date residing in main memory need to be
swapped out, space must be found on backing store.

Basic Method:
Physical memory is broken in to fixed sized blocks called frames (f). Logical memory is
broken in to blocks of same size called pages (p). When a process is to be executed its pages are
loaded in to available frames from backing store. The blocking store is also divided in to fixed-
sized blocks of same size as memory frames. The following figure shows paging hardware:

Logical address generated by the CPU is divided in to two parts: page number (p) and page
offset (d). The page number (p) is used as index to the page table. The page table contains base
address of each page in physical memory. This base address is combined with the page offset to
define the physical memory i.e., sent to the memory unit. The page size is defined by the hardware.
The size of a power of 2, varying between 512 bytes and 10Mb per page. If the size of logical
address space is 2^m address unit and page size is 2^n, then high order m-n designates the page
number and n low order bits represents page offset.

6
 Eg:-To show how to map logical memory in to physical memory consider a page size of 4
bytes and physical memory of 32 bytes (8 pages). Logical address 0 is page 0 and offset 0. Page 0
is in frame 5. The logical address 0 maps to physical address 20. [(5*4) + 0]. ogical address 3 is
page 0 and offset 3 maps to physical address 23 [(5*4) + 3]. Logical address 4 is page 1 and offset
0 and page 1 is mapped to frame 6. So logical address 4 maps to physical address 24 [(6*4) + 0].
Logical address 13 is page 3 and offset 1 and page 3 is mapped to frame 2. So logical address 13
maps to physical address 9 [(2*4) + 1].
Hardware Support for Paging:

The hardware implementation of the page table can be done in several ways:
The simplest method is that the page table is implemented as a set of dedicated registers. These
registers must be built with very high speed logic for making paging address translation. Every
accessed memory must go through paging map. The use of registers for page table is satisfactory if
the page table is small.
If the page table is large then the use of registers is not visible. So the page table is kept in the
main memory and a page table base register [PTBR] points to the page table. Changing the page
table requires only one register which reduces the context switching type. The problem with this
approach is the time required to access memory location. To access a location [i] first we have to
index the page table using PTBR offset. It gives the frame number which is combined with the page
offset to produce the actual address. Thus we need two memory accesses for a byte.

The only solution is to use special, fast, lookup hardware cache called translation look aside
buffer [TLB] or associative register. LB is built with associative register with high speed memory.
Each register contains two paths a key and a value.

When an associative register is presented with an item, it is compared with all the key
values, if found the corresponding value field is return and searching is fast. TLB is used with the
page table as follows: TLB contains only few page table entries. When a logical address is generated
by the CPU, its page number along with the frame number is added to TLB. If the page number is
found its frame memory is used to access the actual memory. If the page number is not in the TLB
(TLB miss) the memory reference to the page table is made. When the frame number is obtained
use can use it to access the memory. If the TLB is full of entries the OS must select anyone for
replacement. Each time a new page table is selected the TLB must be flushed [erased] to ensure
that next executing process do not use wrong information. The percentage of time that a page
number is found in the TLB is called HIT ratio.

Protection:
Memory protection in paged environment is done by protection bits that are associated with each
frame these bits are kept in page table. x One bit can define a page to be read-write or read-only.
To find the correct frame number every reference to the memory should go through page table. At
7
 the same time physical address is computed. The protection bits can be checked to verify that no
writers are made to read-only page. Any attempt to write in to read-only page causes a hardware
trap to the OS. This approach can be used to provide protection to read-only, read-write or execute-
only pages. One more bit is generally added to each entry in the page table: a valid- invalid bit.

A valid bit indicates that associated page is in the processes logical address space and thus it is a
legal or valid page.
If the bit is invalid, it indicates the page is not in the processes logical addressed space and illegal.
Illegal addresses are trapped by using the valid-invalid bit.
The OS sets this bit for each page to allow or disallow accesses to that page.

Structure Of Page Table

a. Hierarchical paging:
Recent computer system support a large logical address apace from 2^32 to 2^64. In this
system the page table becomes large. So it is very difficult to allocate contiguous main memory for
page table. One simple solution to this problem is to divide page table in to smaller pieces. There
are several ways to accomplish this division.
One way is to use two-level paging algorithm in which the page table itself is also paged.
Eg:-In a 32 bit machine with page size of 4kb. A logical address is divided in to a page number
consisting of 20 bits and a page offset of 12 bit. The page table is further divided since the page
table is paged, the page number is further divided in to 10 bit page number and a 10 bit offset.

b. Hashed page table:

Hashed page table handles the address space larger than 32 bit. The virtual page number is used as
hashed value. Linked list is used in the hash table which contains a list of elements that hash to the
same location.
c. Inverted Page Tables:
Since the address spaces have grown to 64 bits, the traditional page tables become a
problem. Even with two level page tables. The table can be too large to handle. An inverted page
table has only entry for each page in memory. Each entry consisted of virtual address of the page
stored in that read-only location with information about the process that owns that page. Each
element in the hash table contains the following three fields: Virtual page number x Mapped page
8
frame value x Pointer to the next element in the linked list
Working:
Virtual page number is taken from virtual address. Virtual page number is hashed in to hash table.
Virtual page number is compared with the first element of linked list. Both the values are
matched, that value is (page frame) used for calculating the physical address. If not match then
entire linked list is searched for matching virtual page number. Clustered pages are similar to hash
table but one difference is that each entity in the hash table refer to several pages.

Each virtual address in the Inverted page table consists of triple <process-id , page number , offset
>. The inverted page table entry is a pair <process-id , page number>. When a memory reference is
made, the part of virtual address i.e., <process-id , page number> is presented in to memory sub-
system. The inverted page table is searched for a match. If a match is found at entry I then the
physical address <i , offset> is generated. If no match is found then an illegal address access has
been attempted. This scheme decreases the amount of memory needed to store each page table, it
increases the amount of time needed to search the table when a page reference occurs. If the whole
table is to be searched it takes too long.

Advantage:

 Eliminates fragmentation.
 Support high degree of multiprogramming.
 Increases memory and processor utilization.
 Compaction overhead required for the re-locatable partition scheme is also eliminated.
Disadvantage:

 Page address mapping hardware increases the cost of the computer.

 Memory must be used to store the various tables like page tables, memory map tableetc.
 Some memory will still be unused if the number of available block is notsufficient
for the address space of the jobs to be run.
c. Shared Pages:
Another advantage of paging is the possibility of sharing common code. This is useful in
timesharing environment. Eg:-Consider a system with 40 users, each executing a text editor. If the
text editor is of 150k and data space is 50k, we need 8000k for 40 users. If the code is reentrant it
can be shared. Consider the following figure
9
 If the code is reentrant then it never changes during execution. Thus two or more processes
can execute same code at the same time. Each process has its own copy of registers and the data of
two processes will vary. Only one copy of the editor is kept in physical memory. Each users page
table maps to same physical copy of editor but date pages are mapped to different frames. So to
support 40 users we need only one copy of editor (150k) plus 40 copies of 50k of data space i.e.,
only 2150k instead of 8000k.

Virtual Memory Management

Virtual memory is a technique that allows for the execution of partially loaded process.
There are many advantages of this: A program will not be limited by the amount of physical
memory that is available user can able to write in to large virtual space. Since each program takes
less amount of physical memory, more than one program could be run at the same time which can
increase the throughput and CPU utilization. Less i/o operation is needed to swap or load user
program in to memory. So each user program could run faster.
Virtual memory is the separation of users logical memory from physical memory. This
separation allows an extremely large virtual memory to be provided when these is less physical
memory. Separating logical memory from physical memory also allows files and memory to be
shared by several different processes through page sharing.
Virtual memory is implemented using Demand Paging.
Demand Paging
A demand paging is similar to paging system with swapping when we want to execute a
process we swap the process the in to memory otherwise it will not be loaded in to memory. A
swapper manipulates the entire processes, where as a pager manipulates individual pages of the
process.
Basic concept: Instead of swapping the whole process the pager swaps only the necessary pages in
to memory. Thus it avoids reading unused pages and decreases the swap time and amount of
physical memory needed.

10
The valid-invalid bit scheme can be used to distinguish between the pages that are on the disk and
that are in memory.

o If the bit is valid then the page is both legal and is in memory.
o If the bit is invalid then either page is not valid or is valid but is currently on the disk.
Marking a page as invalid will have no effect if the processes never access to that page.
Suppose if it access the page which is marked invalid, causes a page fault trap. This may result in
failure of OS to bring the desired page in to memory.
The step for handling page fault is straight forward and is given below:

 We check the internal table of the process to determine whether the reference made is valid or
invalid.
 If invalid terminate the process,. If valid, then the page is not yet loaded and we now page it
in.
 We find a free frame.
 We schedule disk operation to read the desired page in to newly allocated frame.
 When disk reed is complete, we modify the internal table kept with the process to indicate that
the page is now in memory.
We restart the instruction which was interrupted by illegal address trap. The process can
now access the page. In extreme cases, we start the process without pages in memory. When the
OS points to the instruction of process it generates a page fault. After this page is brought in to
memory the process continues to execute, faulting as necessary until every demand paging i.e., it
never brings the page in to memory until it is required.

Hardware support:

For demand paging the same hardware is required as paging and swapping.
Page table:-Has the ability to mark an entry invalid through valid-invalid bit.
Secondary memory:-This holds the pages that are not present in main memory.
Performance of demand paging: Demand paging can have significant effect on the
performance of the computer system.
Let P be the probability of the page fault (0<=P<=1)
Effective access time = (1-P) * ma + P * page fault. Where P = page fault and ma = memory
11
 access time. Effective access time is directly proportional to page fault rate. It is important
to keep page fault rate low in demand paging.

A page fault causes the following sequence to occur:

Trap to the OS.

Save the user registers and process state. Determine that the interrupt was a page fault. Checks
the page references were legal and determine the location of page on disk. Issue a read from disk
to a free frame.
If waiting, allocate the CPU to some other user. Interrupt from the disk. Save the registers
and process states of other users. Determine that the interrupt was from the disk. Correct the page
table and other table to show that the desired page is now in memory.

Comparison of demand paging with segmentation:-

Segmentation:
o Segment may of different size.
o Segment can be shared.
o Allows for dynamic growth of segments.
o Segment map table indicate the address of each segment in memory.
o Segments are allocated to the program while compilation.
Demand Paging:
o Pages are of same size.
o Pages can‟t be shared.
o Page size is fixed.
. o Page table keeps track of pages in memory.
o Pages are allocated in memory on demand.

Copy-On-Write:
Demand paging is used when reading a file from disk in to memory. Fork () is used to create
a process and it initially bypass the demand paging using a technique called page sharing. Page
sharing provides rapid speed for process creation and reduces the number of pages allocated to the
newly created process. Copy-on-write technique initially allows the parent and the child to share
the same pages. These pages are marked as copy-on-write pages i.e., if either process writes to a
shared page, a copy of shared page is created.
Eg:-If a child process try to modify a page containing portions of the stack; the OS
recognizes them as a copy-on-write page and create a copy of this page and maps it on to the address
space of the child process. So the child process will modify its copied page and not the page
belonging to parent. The new pages are obtained from the pool of free pages.

Memory Mapping: Standard system calls i.e., open (), read () and write () is used for sequential
read of a file. Virtual memory is used for this. In memory mapping a file allows a part of the virtual
address space to be logically associated with a file. Memory mapping a file is possible by mapping
a disk block to page in memory.

12
Page Replacement
Demand paging shares the I/O by not loading the pages that are never used.
Demand paging also improves the degree of multiprogramming by allowing more process to
run at the sometime. Page replacement policy deals with the solution of pages in memory to be
replaced by a new page that must be brought in. When a user process is executing a page fault
occurs. The hardware traps to the operating system, which checks the internal table to see that this
is a page fault and not an illegal memory access. The operating system determines where the derived
page is residing on the disk, and this finds that are no free frames on the list of free frames.
When all the frames are in main memory, it is necessary to bring a new page to satisfy the
page fault, replacement policy is concerned with selecting a page currently in memory to be
replaced. The page i,e to be removed should be the page i,e least likely to be referenced in future.

Working of Page Replacement Algorithm

1. Find the location of derived page on the disk.
2. Find a free frame x If there is a free frame, use it. x Otherwise, use a replacement algorithmto
select a victim. x Write the victim page to the disk; change the page and frame tables
accordingly.

3. Read the desired page into the free frame; change the page and frametables.
Restart the user process.
Victim Page
The page that is supported out of physical memory is called victim page. x If no frames are
free, the two page transforms come (out and one in) are read. This will see the effective access time.

 Each page or frame may have a dirty (modify) bit associated with the hardware. The modify
bit for a page is set by the hardware whenever any word or byte in the page is written into, indicating
that the page has been modified.
 When we select the page for replacement, we check its modify bit. If the bit is set, then the
page is modified since it was read from the disk.
 If the bit was not set, the page has not been modified since it was read into memory.
Therefore, if the copy of the page has not been modified we can avoid writing the memory page to
the disk, if it is already there. Sum pages cannot be modified.
We must solve two major problems to implement demand paging: we must develop a frame
allocation algorithm and a page replacement algorithm. If we have multiple processors in memory,
we must decide how many frames to allocate and page replacement is needed.

13
PAGE REPLACEMENT ALGORITHMS:
FIFO Algorithm:

 This is the simplest page replacement algorithm. A FIFO replacement algorithm associates
each page the time when that page was brought into memory.
 When a Page is to be replaced the oldest one is selected.
 We replace the queue at the head of the queue. When a page is brought into memory, we
insert it at the tail of the queue.
Example: Consider the following references string with frames initially empty.

The first three references (7,0,1) cases page faults and are brought into the empty frames. The next
references 2 replaces page 7 because the page 7 was brought in first. Since 0 is the next references
and 0 is already in memory e has no page faults. The next references 3 results in page 0 being
replaced so that the next references to 0 causer page fault. This will continue till the end of string.
There are 15 faults all together.

Belady’s Anamoly
For some page replacement algorithm, the page fault may increase as the number of
allocated frames increases. FIFO replacement algorithm may face this problem.

Optimal Algorithm
Optimal page replacement algorithm is mainly to solve the problem of Belady‟s Anamoly.
Optimal page replacement algorithm has the lowest page fault rate of all algorithms. An optimal
page replacement algorithm exists and has been called OPT. The working is simple “Replace the
page that will not be used for the longest period of time” Example: consider the following reference
strin

14
The first three references cause faults that fill the three empty frames. The references to page 2
replaces page 7, because 7 will not be used until reference 18. The page 0 will be used at 5 and page
1 at 14. With only 9 page faults, optimal replacement is much better than a FIFO, which had 15
faults. This algorithm is difficult t implement because it requires future knowledge of reference
strings.

Least Recently Used (LRU) Algorithm

If the optimal algorithm is not feasible, an approximation to the optimal algorithm is
possible. The main difference b/w OPTS and FIFO is that; FIFO algorithm uses the time when the
pages was built in and OPT uses the time when a page is to be used.
The LRU algorithm replaces the pages that have not been used for longest period of time.
The LRU associated its pages with the time of that pages last use. x This strategy is the optimal
page replacement algorithm looking backward in time rather than forward. Ex: consider the
following reference string

The first 5 faults are similar to optimal replacement.

When reference to page 4 occurs, LRU sees that of the three frames, page 2 as used least
recently. The most recently used page is page 0 and just before page 3 was used. The LRU policy
is often used as a page replacement algorithm and considered to be good. The main problem to how
to implement LRU is the LRU requires additional h/w assistance. Two implementation are possible:

Counters: In this we associate each page table entry a time -of -use field, and add to the cpu a
logical clock or counter. The clock is incremented for each memory reference. When a reference
to a page is made, the contents of the clock register are copied to the time-of-use field in the page
table entry for that page. In this way we have the time of last reference to each page we replace the
page with smallest time value. The time must also be maintained when page tables are changed.
Stack: Another approach to implement LRU replacement is to keep a stack of page numbers when
a page is referenced it is removed from the stack and put on to the top of stack. In this way the top
of stack is always the most recently used page and the bottom in least recently used page. Since the
entries are removed from the stack it is best implement by a doubly linked list. With a head and tail
pointer. Neither optimal replacement nor LRU replacement suffers from Belady‟s Anamoly. These
are called stack algorithms.

15
 LRU Approximation
An LRU page replacement algorithm should update the page removal status information
after every page reference updating is done by software, cost increases.
But hardware LRU mechanism tend to degrade execution performance at the same time,
then substantially increases the cost. For this reason, simple and efficient algorithm that
approximation the LRU have been developed. With h/w support the reference bit was used. A
reference bit associate with each memory block and this bit automatically set to 1 by the h/w
whenever the page is referenced. The single reference bit per clock can be used to approximate
LRU removal. The page removal s/w periodically resets the reference bit to 0, write the execution
of the users job causes some reference bit to be set to 1. If the reference bit is 0 then the page has
not been referenced since the last time the reference bit was set to 0.

Count Based Page Replacement

There is many other algorithms that can be used for page replacement, we can keep a counter of
the number of references that has made to a page.

a) LFU (Least frequently used):

This causes the page with the smallest count to be replaced. The reason for this selection
is that actively used page should have a large reference count. This algorithm suffers from the
situation in which a page is used heavily during the initial phase of a process but never used again.
Since it was used heavily, it has a large count and remains in memory even though it is no longer
needed.

b) Most Frequently Used (MFU):

This is based on the principle that the page with the smallest count was probably just brought in
and has yet to be used.

Allocation of Frames
The allocation policy in a virtual memory controls the operating system decision
regarding the amount of real memory to be allocated to each active process. In a paging system if
more real pages are allocated, it reduces the page fault frequency and improved turnaround
throughput. If too few pages are allocated to a process its page fault frequency and turnaround times
may deteriorate to unacceptable levels.
The minimum number of frames per process is defined by the architecture, and the
maximum number of frames. This scheme is called equal allocation. With multiple processes
competing for frames, we can classify page replacement into two broad categories
a) Local Replacement: requires that each process selects frames from only its own sets of allocated
frame.
b). Global Replacement: allows a process to select frame from the set of all frames. Even if the
frame is currently allocated to some other process, one process can take a frame fromanother.
In local replacement the number of frames allocated to a process do not change but with
global replacement number of frames allocated to a process do not change global replacement
results in greater system throughput.

16
 Other consideration
There is much other consideration for the selection of a replacement algorithm and allocation
policy.
1) Preparing: This is an attempt to present high level of initial paging. This strategy is to bring
into memory all the pages at one time. 2) TLB Reach: The TLB reach refers to the amount of
memory accessible from the TLB and is simply the no of entries multiplied by page size.
Page Size: following parameters are considered a) page size us always power of 2 (from 512 to
16k) b) Internal fragmentation is reduced by a small page size. c) A large page size reduces the
number of pages needed.
Invented Page table: This will reduces the amount of primary memory i,e. needed to track virtual
to physical address translations. 5) Program Structure: Careful selection of data structure can
increases the locality and hence lowers the page fault rate and the number of pages in working
state.

Real time Processing: Real time system almost never has virtual memory. Virtual
memory is the antithesis of real time computing, because it can introduce unexpected long term
delay in the execution of a process.

Thrashing
If the number of frames allocated to a low-priority process falls below the minimum
number required by the computer architecture then we suspend the process execution. A process is
thrashing if it is spending more time in paging than executing.

If the processes do not have enough number of frames, it will quickly page fault. During
this it must replace some page that is not currently in use. Consequently it quickly faults again and
again. The process continues to fault, replacing pages for which it then faults and brings back. This
high paging activity is called thrashing. The phenomenon of excessively moving pages back and
forth b/w memory and secondary has been called thrashing.
Cause of Thrashing: Thrashing results in severe performance problem. The operating system
monitors the cpu utilization is low. We increase the degree of multi programming by introducing
new process to the system. A global page replacement algorithm replaces pages with no regards to
the process to which they belong. The figure shows the thrashing
As the degree of multi programming increases, more slowly until a maximum is reached. If the
degree of multi programming is increased further thrashing sets in and the cpu utilization drops
sharply.

17
 At this point, to increases CPU utilization and stop thrashing, we must increase degree of multi
programming. We can limit the effect of thrashing by using a local replacement algorithm. To
prevent thrashing, we must provide a process as many frames as it needs.
Locality of Reference: As the process executes it moves from locality to locality. A locality is a set
of pages that are actively used. A program may consist of several different localities, which may
overlap. Locality is caused by loops in code that find to reference arrays and other data structures
by indices. The ordered list of page number accessed by a program is called reference string.
Locality is of two types

1) spatial locality 2) temporal locality

Working set model

Working set model algorithm uses the current memory requirements to determine the number of
page frames to allocate to the process, an informal definition is “the collection of pages that a
process is working with and which must be resident if the process to avoid thrashing”. The idea is
to use the recent needs of a process to predict its future reader. The working set is an approximation
of programs locality. Ex: given a sequence of memory reference, if the working set window size to
memory references, then working set at time t1 is {1,2,5,6,7} and at t2 is changed to {3,4} At any
given time, all pages referenced by a process in its last 4 seconds of execution are considered to
compromise its working set. A process will never execute until its working set is resident in main
memory. Pages outside the working set can be discarded at any movement. Working sets are not
enough and we must also introduce balance set. If the sum of the working sets of all the run able
process is greater than the size of memory the refuse some process for a while. Divide the run able
process into two groups, active and inactive. The collection of active set is called the balance set.
When a process is made active its working set is loaded.

18
SOLVED PROBLEMS:
1. Least recently used (LRU) algorithm
2. First-In, First-out (FIFO) algorithm

PART- A QUESTIONS(2Marks):

1. What are the functions of memory management?

2. When is a system in safe state?
3 What is the Translation Lookaside Buffer (TLB)?
4. What is the basic function of paging?
5. List the reasons for process suspension.
6. What are the differences between Logical and Physical address?
7. Write short note on swapping?
8. Write about Internal and External Fragmentation?
9. What is meant by Paging? Give its advantages.
10. What is meant by Global Replacement and Local Replacement?

UNIT-3
PART- A QUESTIONS(2Marks):

1. What are the functions of memory management?

Keeping track of status of each memory location.
Determining the allocation policy.
Memory allocation technique.
De-allocation technique.
2. When is a system in safe state?
A state is a safe state in which there exists at least one order in which all the process willrun
completely without resulting in a deadlock. A system is in safe state if there exists a safe
sequence. A sequence of processes <P1,P2, ............. PN>t; is a safe sequence for the current
allocation state if for each Pi the resources that Pi can request can be satisfied by the currently
available resources. If the resources that Pi requests are not currently available then Pi can obtain
all of its needed resource to complete its designated task. A safe state is not a deadlock state.
3 What is the Translation Lookaside Buffer (TLB)?
To overcome this problem a high-speed cache is set up for page table entries called a Translation
Lookaside Buffer (TLB). Translation Lookaside Buffer (TLB) is nothing but a special cache used
to keep track of recently used transactions. TLB contains page table entries that have been most
recently used. Given a virtual address, the processor examines the TLB if a page table entry is
present (TLB hit), the frame number is retrieved and the real address is formed.

19
4. What is the basic function of paging?

Paging is a Memory-management scheme that permits the physical –address space of a process to
be Non-contiguous.

5. List the reasons for process suspension.

- Normal completion
- Time limit exceeded
- Memory unavailable
- Protection error
- Arithmetic error
- I/O failure
- Invalid instruction
6. What are the differences between Logical and Physical address?
The address generated by the CPU is called logical address or virtual address. The address seen
by the memory unit i.e., the one loaded in to the memory register is called the physical address.
Compile time and load time address binding methods generate some logical and physical address.
The execution time addressing binding generate different logical and physical address.
Set of logical address space generated by the programs is the logical address space. Set of
physical address corresponding to these logical addresses is the physical address space.
7. Write short note on swapping?

Swapping is a technique of temporarily removing inactive programs from the memory of the
system. A process can be swapped temporarily out of the memory to a backing store and then
brought back in to the memory for continuing the execution. This process is called swapping.
For example, in a multi-programming environment with a round robin CPU scheduling whenever
the time quantum expires then the process that has just finished is swapped out and a new process
swaps in to the memory for execution.

8. Write about Internal and External Fragmentation?

Memory fragmentation can be of two types: Internal Fragmentation External Fragmentation.

Internal Fragmentation there is wasted space internal to a portion due to the fact that block of data
loaded is smaller than the partition. Eg:-If there is a block of 50kb and if the process requests
40kb and if the block is allocated to the process then there will be 10kb of memory left.

External Fragmentation exists when there is enough memory space exists to satisfy the request,
but it not contiguous i.e., storage is fragmented in to large number of small holes. External
Fragmentation may be either minor or a major problem. One solution for over-coming external
fragmentation is compaction.

20
9. What is meant by Paging? Give its advantages.

Paging is a Memory-management scheme that permits the physical –address space of a process to
be Non-contiguous.
Advantages:
Avoids the considerable problem of fitting the varying -sized memory chunks onto the baking
store Fragmentation problems are also prevalent baking store, except that access is much slower,
so compaction is impossible.

10. What is meant by Global Replacement and Local Replacement?

Global Page Replacement allows a process to select a replacement frame from the set of all
frames, even if that frame is currently allocated to some other process.
Local Replacement requires that each process select from only its own set of allocated frames.
Here the number of frames allocated to a process doesn‟t change.

PART- B QUESTIONS(10 Marks):

1. Compare and contrast the physical and virtual memory?

2. Briefly explain demand paging. List out advantages and disadvantages of demand paging.
3. Discuss about optimal page replacement algorithm.
4. If the contents of reference string is: 0, 2, 1, 6, 4, 0, 1, 0, 3, 1, 2, 1 and there are four frames
available in the memory then find page fault and page fault rate using optimal page algorithm.
5. Explain about deadlocks in detail?
6. Give short notes on any two page replacement algorithms?
7. Given memory partition of 100 KB, 500 KB, 200 KB and 600 KB (in order). Show with neat
sketch how would each of the first-fit, best-fit and worst-fit algorithms place processes of 412 KB,
317 KB, 112 KB and 326 KB (in order). Which algorithm is most efficient in memory allocation?
8. Define paging? Explain paging concept in detail?f

21