UNIT – 3

VIRTUAL MEMORY

Virtual Memory
Virtual memory is a technique that allows the execution of process that may not be completely in
memory. The main visible advantage of this scheme is that programs can be larger than physical
memory.

Virtual memory is the separation of user logical memory from physical memory this separation allows an
extremely large virtual memory to be provided for programmers when only a smaller physical memory
is available ( Fig ).
Following are the situations, when entire program is not required to load fully.
1. User written error handling routines are used only when an error occurs in the data or computation.
2. Certain options and features of a program may be used rarely.
3. 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.
1. Less number of I/O would be needed to load or swap each user program into memory.
2. A program would no longer be constrained by the amount of physical memory that is available.
3. 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.
 Fig. Diagram showing virtual memory that is larger than physical memory.
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 is similar to a paging system with swapping(Fig 5.2). When we want to execute a
process, we swap it into memory. Rather than swapping the entire process into memory.

When a process is to be swapped in, the pager guesses which pages will be used before the process is
swapped out again Instead of swapping in a whole process, the pager brings only those necessary pages into
memory. Thus, it avoids reading into memory pages that will not be used in anyway, decreasing the swap time
and the amount of physical memory needed.

Hardware support is required to distinguish between those pages that are in memory and those pages that
are on the disk using the valid-invalid bit scheme. Where valid and invalid pages can be checked checking the
bit and marking a page will have no effect if the process never attempts to access the pages. While the process
executes and accesses pages that are memory resident, execution proceeds normally.
 Fig. Transfer of a paged memory to continuous disk space

Access to a page marked invalid causes a page-fault trap. This trap is the result of the operating system's
failure to bring the desired page into memory. But page fault can be handled as following (Fig 5.3):

Fig. Steps in handling a page fault

 1. We check an internal table for this process to determine whether the reference was a valid or invalid
memory access.
2. If the reference was invalid, we terminate the process. If .it was valid, but we have not yet brought in
that page, we now page in the latter.
3. We find a free frame.

4. We schedule a disk operation to read the desired page into the newly allocated frame.

5. When the disk read is complete, we modify the internal table kept with the process and the page table to
indicate that the page is now in memory.

6. We restart the instruction that was interrupted by the illegal address trap. The process can now access the
page as though it had always been memory.

Therefore, the operating system reads the desired page into memory and restarts the process as though the
page had always been in memory.

The page replacement is used to make the frame free if they are not in used. If no frame is free then other
process is called in.

Advantages of Demand Paging:

1. Large virtual memory.
2. More efficient use of memory.
3. Unconstrained multiprogramming. There is no limit on degree of multiprogramming.

Disadvantages of Demand Paging:

4. Number of tables and amount of processor over head for handling page interrupts are greater than in the
case of the simple paged management techniques.
5. due to the lack of an explicit constraints on a jobs address space size.

Page Replacement Algorithm

There are many different page replacement algorithms. We evaluate an algorithm by running it on a
particular string of memory reference and computing the number of page faults. The string of memory
references is called reference string. Reference strings are generated artificially or by tracing a given system and
recording the address of each memory reference. The latter choice produces a large number of data.

1. For a given page size we need to consider only the page number, not the entire address.

2. if we have a reference to a page p, then any immediately following references to page p will never cause
a page fault. Page p will be in memory after the
first reference; the immediately following references will not fault.

Eg:- consider the address sequence

0100, 0432, 0101, 0612, 0102, 0103, 0104, 0101, 0611, 0102, 0103, 0104, 0101, 0610, 0102,
 0103, 0104, 0104, 0101, 0609, 0102, 0105
and reduce to 1, 4, 1, 6,1, 6, 1, 6, 1, 6, 1

To determine the number of page faults for a particular reference string and page replacement algorithm,
we also need to know the number of page frames available. As the number of frames available increase, the
number of page faults will decrease.

FIFO Algorithm

The simplest page-replacement algorithm is a FIFO algorithm. A FIFO replacement algorithm associates
with each page the time when that page was brought into memory. When a page must be replaced, the oldest
page is chosen. We can create a FIFO queue to hold all pages in memory.
The first three references (7, 0, 1) cause page faults, and are brought into these empty eg. 7, 0, 1, 2, 0, 3,
0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1 and consider 3 frames. This replacement means that the next reference to 0 will fault.
Page 1 is then replaced by page 0.

Optimal Algorithm

An optimal page-replacement algorithm has the lowest page-fault rate of all algorithms. An optimal
page-replacement algorithm exists, and has been called OPT or MIN. It is simply
Replace the page that will not be used for the longest
period of time.

Now consider the same string with 3 empty frames.

The reference to page 2 replaces page 7, because 7 will not be used until reference 15, whereas page 0
will be used at 5, and page 1 at 14. The reference to page 3 replaces page 1, as page 1 will be the last of the
three pages in memory to be referenced again. Optimal replacement is much better than a FIFO.

The optimal page-replacement algorithm is difficult to implement, because it requires future knowledge
of the reference string.

LRU Algorithm

The FIFO algorithm uses the time when a page was brought into memory; the OPT algorithm uses the
time when a page is to be used. In LRU replace the page that has not been used for the longest period of time.

LRU replacement associates with each page the time of that page's last use. When a page must be
replaced, LRU chooses that page that has not been used for the longest period of time.

Let SR be the reverse of a reference string S, then the page-fault rate for the OPT algorithm on S is the
same as the page-fault rate for the OPT algorithm on SR.
LRU Approximation Algorithms

Some systems provide no hardware support, and other page-replacement algorithm. Many systems
provide some help, however, in the form of a reference bit. The reference bit for a page is set, by the hardware,
whenever that page is referenced. Reference bits are associated with each entry in the page table Initially, all
bits are cleared (to 0) by the operating system. As a user process executes, the bit associated with each page
referenced is set (to 1) by the hardware.

Additional-Reference-Bits Algorithm

The operating system shifts the reference bit for each page into the high-order or of its 5-bit byte,
shifting the other bits right 1 bit, discarding the low-order bit.
These 5-bit shift registers contain the history of page use for the last eight time periods. If the shift
register contains 00000000, then the page has not been

used for eight time periods; a page that is used at least once each period would have a shift register value of
11111111.

Second-Chance Algorithm

The basic algorithm of second-chance replacement is a FIFO replacement algorithm. When a page gets a
second chance, its reference bit is cleared and its arrival e is reset to the current time.

Enhanced Second-Chance Algorithm

The second-chance algorithm described above can be enhanced by considering troth the reference bit
and the modify bit as an ordered pair.

1. (0,0) neither recently used nor modified best page to replace.

2. (0,1) not recently used but modified not quite as good, because the page will need to be written out
before replacement.
3. (1,0) recently used but clean probably will be used again soon.
4. (1,1) recently used and modified probably will be used again, and write out will be needed before
replacing it

Counting Algorithms

There are many other algorithms that can be used for page replacement.

• LFU Algorithm: The least frequently used (LFU) page-replacement algorithm requires that the page with the
smallest count be replaced. This algorithm suffers from the situation in which a page is used heavily during the
initial phase of a process, but then is never used again.
• MFU Algorithm: The most frequently used (MFU) page-replacement algorithm is
based on the argumentthat the page with the smallest count was probably just brought
in and has yet to be used.

Page Buffering Algorithm

When a page fault occurs, a victim frame is chosen as before. However, the
desired page is read into afree frame from the pool before the victim is written out.
This procedure allows the process to restart as soon as possible, without waiting for the
victim page to be written out. When the victim is later written out, its frame is added to
the free-frame pool.
When the FIFO replacement algorithm mistakenly replaces a page mistakenly
replaces a page that is still in active use, that page is quickly retrieved from the free-
frame buffer, and no I/O is necessary. The free-frame buffer provides protection against
the relatively poor, but simple, FIFO replacement algorithm.
Allocation of frames
An important aspect of operating systems, virtual memory is implemented using demand
paging. Demand paging necessitates the development of a page-replacement
algorithm and a frame allocation algorithm. Frame allocation algorithms are used if you
have multiple processes; it helps decide how many frames to allocate to each process.
There are various constraints to the strategies for the allocation of frames:
• You cannot allocate more than the total number of available frames.
• At least a minimum number of frames should be allocated to each process. This
constraint is supported by two reasons. The first reason is, as less number of frames
are allocated, there is an increase in the page fault ratio, decreasing the performance
of the execution of the process. Secondly, there should be enough frames to hold all
the different pages that any single instruction can reference.
Frame allocation algorithms –
The two algorithms commonly used to allocate frames to a process are:
1. Equal allocation: In a system with x frames and y processes, each process gets
equal number of frames, i.e. x/y. For instance, if the system has 48 frames and 9
processes, each process will get 5 frames. The three frames which are not allocated to
any process can be used as a free-frame buffer pool.
• Disadvantage: In systems with processes of varying sizes, it does not make
much sense to give each process equal frames. Allocation of a large number of
frames to a small process will eventually lead to the wastage of a large number of
allocated unused frames.
2. Proportional allocation: Frames are allocated to each process according to the
process size.
For a process pi of size si, the number of allocated frames is ai = (si/S)*m, where S is
the sum of the sizes of all the processes and m is the number of frames in the system.
For instance, in a system with 62 frames, if there is a process of 10KB and another
process of 127KB, then the first process will be allocated (10/137)*62 = 4 frames and
the other process will get (127/137)*62 = 57 frames.
• Advantage: All the processes share the available frames according to their
needs, rather than equally.
Global vs Local Allocation –
The number of frames allocated to a process can also dynamically change depending on
whether you have used global replacement or local replacement for replacing pages in
case of a page fault.
1. Local replacement: When a process needs a page which is not in the memory, it
can bring in the new page and allocate it a frame from its own set of allocated frames
only.
• Advantage: The pages in memory for a particular process and the page
fault ratio is affected by the paging behavior of only that process.
• Disadvantage: A low priority process may hinder a high priority process
 by not making its frames available to the high priority process.
2. Global replacement: When a process needs a page which is not in the memory, it
can bring in the new page and allocate it a frame from the set of all frames, even if
that frame is currently allocated to some other process; that is, one process can take a
frame from another.
• Advantage: Does not hinder the performance of processes and hence
results in greater system throughput.
• Disadvantage: The page fault ratio of a process can not be solely
controlled by the process itself. The pages in memory for a process depends on the
paging behavior of other processes as well.
 Process Creation & Termination
Process creation is achieved through the fork() system call. The newly created process is called the child
process and the process that initiated it (or the process when execution is started) is called the parent
process. After the fork() system call, now we have two processes - parent and child processes.

After creation of the child process, let us see the fork() system call details.
#include <sys/types.h>
#include <unistd.h>

pid_t fork(void);
Creates the child process, after this call, there are two processes, the existing one is called the
parent process and the newly created one is called the child process.
The fork() system call returns either of the three values −
• Negative value to indicate an error, i.e., unsuccessful in creating the child process.
• Returns a zero for child process.
• Returns a positive value for the parent process. This value is the process ID of the newly
created child process.

Process Creation and Process termination are used to create and terminate processes
respectively. Details about these are given as follows −

Process Creation

A process may be created in the system for different operations. Some of the events that lead to
process creation are as follows −

• User request for process creation

• System Initialization
 • Batch job initialization
• Execution of a process creation system call by a running process

A process may be created by another process using fork(). The creating process is called the
parent process and the created process is the child process. A child process can have only one
parent but a parent process may have many children. Both the parent and child processes have
the same memory image, open files and environment strings. However, they have distinct
address spaces.

A diagram that demonstrates process creation using fork() is as follows −

Process Termination

Process termination occurs when the process is terminated The exit() system call is used by
most operating systems for process termination.

Some of the causes of process termination are as follows −

• A process may be terminated after its execution is naturally completed. This process
leaves the processor and releases all its resources.
• A child process may be terminated if its parent process requests for its termination.
• A process can be terminated if it tries to use a resource that it is not allowed to. For
example - A process can be terminated for trying to write into a read only file.
• If an I/O failure occurs for a process, it can be terminated. For example - If a process
requires the printer and it is not working, then the process will be terminated.

A process can terminate in either of the two ways −

• Abnormally, occurs on delivery of certain signals, say terminate signal.
 • Normally, using _exit() system call (or _Exit() system call) or exit() library function.
The difference between _exit() and exit() is mainly the cleanup activity. The exit() does some
cleanup before returning the control back to the kernel, while the _exit() (or _Exit()) would
return the control back to the kernel immediately.
•
• In most cases, if a parent process is terminated then its child processes are also
terminated. This is done because the child process cannot exist without the parent
process.
• If a process requires more memory than is currently available in the system, then it is
terminated because of memory scarcity.
 Copy on Write
Copy on Write or simply COW is a resource management technique. One of its main use
is in the implementation of the fork system call in which it shares the virtual
memory(pages) of the OS.
In UNIX like OS, fork() system call creates a duplicate process of the parent process
which is called as the child process.
The idea behind a copy-on-write is that when a parent process creates a child process
then both of these processes initially will share the same pages in memory and these
shared pages will be marked as copy-on-write which means that if any of these processes
will try to modify the shared pages then only a copy of these pages will be created and
the modifications will be done on the copy of pages by that process and thus not affecting
the other process.
Suppose, there is a process P that creates a new process Q and then process P modifies
page 3.
The below figures shows what happens before and after process P modifies page 3.
Thrashing

In case, if the page fault and swapping happens very frequently at a higher rate, then the
operating system has to spend more time swapping these pages. This state in the operating
system is termed thrashing. Because of thrashing the CPU utilization is going to be reduced.

Let's understand by an example, if any process does not have the number of frames that it needs
to support pages in active use then it will quickly page fault. And at this point, the process must
replace some pages. As all the pages of the process are actively in use, it must replace a page that
will be needed again right away. Consequently, the process will quickly fault again, and again,
and again, replacing pages that it must bring back in immediately. This high paging activity by a
process is called thrashing.

During thrashing, the CPU spends less time on some actual productive work spend more time
swapping.

Figure: Thrashing

Causes of Thrashing

Thrashing affects the performance of execution in the Operating system. Also, thrashing results
in severe performance problems in the Operating system.

When the utilization of CPU is low, then the process scheduling mechanism tries to load many
processes into the memory at the same time due to which degree of Multiprogramming can be
increased. Now in this situation, there are more processes in the memory as compared to the
available number of frames in the memory. Allocation of the limited amount of frames to each
process.

Whenever any process with high priority arrives in the memory and if the frame is not freely
available at that time then the other process that has occupied the frame is residing in the frame
will move to secondary storage and after that this free frame will be allocated to higher priority
process.

We can also say that as soon as the memory fills up, the process starts spending a lot of time for
the required pages to be swapped in. Again the utilization of the CPU becomes low because most
of the processes are waiting for pages.

Thus a high degree of multiprogramming and lack of frames are two main causes of thrashing in
the Operating system.

Effect of Thrashing

At the time, when thrashing starts then the operating system tries to apply either the Global page
replacement Algorithm or the Local page replacement algorithm.

Global Page Replacement

The Global Page replacement has access to bring any page, whenever thrashing found it tries to
bring more pages. Actually, due to this, no process can get enough frames and as a result, the
thrashing will increase more and more. Thus the global page replacement algorithm is not
suitable whenever thrashing happens.

Local Page Replacement

Unlike the Global Page replacement, the local page replacement will select pages which only
belongs to that process. Due to this, there is a chance of a reduction in the thrashing. As it is also
proved that there are many disadvantages of Local Page replacement. Thus local page
replacement is simply an alternative to Global Page replacement.

Techniques used to handle the thrashing

As we have already told you the Local Page replacement is better than the Global Page
replacement but local page replacement has many disadvantages too, so it is not suggestible.
Thus given below are some other techniques that are used:
Working-Set Model

This model is based on the assumption of the locality. It makes the use of the parameter ? in
order to define the working-set window. The main idea is to examine the most recent? page
reference. What locality is saying, the recently used page can be used again, and also the pages
that are nearby this page will also be used?

1. Working Set

The set of the pages in the most recent? page reference is known as the working set. If a page is
in active use, then it will be in the working set. In case if the page is no longer being used then it
will drop from the working set ? times after its last reference.

The working set mainly gives the approximation of the locality of the program.

The accuracy of the working set mainly depends on? what is chosen?

This working set model avoids thrashing while keeping the degree of multiprogramming as high
as possible.

2. Page Fault Frequency

Figure: Page fault frequency

The working-set model is successful and its knowledge can be useful in preparing but it is a very
clumpy approach in order to avoid thrashing. There is another technique that is used to avoid
thrashing and it is Page Fault Frequency(PFF) and it is a more direct approach.

The main problem is how to prevent thrashing. As thrashing has a high page fault rate and also
we want to control the page fault rate.

When the Page fault is too high, then we know that the process needs more frames. Conversely,
if the page fault-rate is too low then the process may have too many frames.

We can establish upper and lower bounds on the desired page faults. If the actual page-fault rate
exceeds the upper limit then we will allocate the process to another frame. And if the page fault
rate falls below the lower limit then we can remove the frame from the process.

Thus with this, we can directly measure and control the page fault rate in order to prevent
thrashing.
Memory-mapped files
A memory-mapped file contains the contents of a file in virtual memory. This mapping
between a file and memory space enables an application, including multiple processes,
to modify the file by reading and writing directly to the memory. You can use managed
code to access memory-mapped files in the same way that native Windows functions
access memory-mapped files, as described in Managing Memory-Mapped Files.

There are two types of memory-mapped files:

• Persisted memory-mapped files

Persisted files are memory-mapped files that are associated with a source file on a
disk. When the last process has finished working with the file, the data is saved to
the source file on the disk. These memory-mapped files are suitable for working
with extremely large source files.

• Non-persisted memory-mapped files

Non-persisted files are memory-mapped files that are not associated with a file on
a disk. When the last process has finished working with the file, the data is lost and
the file is reclaimed by garbage collection. These files are suitable for creating
shared memory for inter-process communications (IPC).

Processes, Views, and Managing Memory

Memory-mapped files can be shared across multiple processes. Processes can map to
the same memory-mapped file by using a common name that is assigned by the
process that created the file.

To work with a memory-mapped file, you must create a view of the entire memory-
mapped file or a part of it. You can also create multiple views to the same part of the
memory-mapped file, thereby creating concurrent memory. For two views to remain
concurrent, they have to be created from the same memory-mapped file.

Multiple views may also be necessary if the file is greater than the size of the
application's logical memory space available for memory mapping (2 GB on a 32-bit
computer).

There are two types of views: stream access view and random access view. Use stream
access views for sequential access to a file; this is recommended for non-persisted files
and IPC. Random access views are preferred for working with persisted files.

Memory-mapped files are accessed through the operating system's memory manager,
so the file is automatically partitioned into a number of pages and accessed as needed.
You do not have to handle the memory management yourself.

The following illustration shows how multiple processes can have multiple and
overlapping views to the same memory-mapped file at the same time.

The following image shows multiple and overlapped views to a memory-mapped file:
Allocating kernel memory
Two strategies for managing free memory that is assigned to kernel processes:

1. Buddy system –

Buddy allocation system is an algorithm in which a larger memory block is divided into small parts to satisfy
the request. This algorithm is used to give best fit. The two smaller parts of block are of equal size and called
as buddies. In the same manner one of the two buddies will further divide into smaller parts until the request is
fulfilled. Benefit of this technique is that the two buddies can combine to form the block of larger size
according to the memory request.
Example – If the request of 25Kb is made then block of size 32Kb is allocated.

Four Types of Buddy System –

1. Binary buddy system
2. Fibonacci buddy system
3. Weighted buddy system
4. Tertiary buddy system
Why buddy system?
If the partition size and process size are different then poor match occurs and may use space inefficiently.
It is easy to implement and efficient then dynamic allocation.
Binary buddy system –
The buddy system maintains a list of the free blocks of each size (called a free list), so that it is easy to find a
block of the desired size, if one is available. If no block of the requested size is available, Allocate searches for
the first non-empty list for blocks of atleast the size requested. In either case, a block is removed from the free
list.
Example – Assume the size of memory segment is initially 256kb and the kernel requests 25kb of memory.
The segment is initially divided into two buddies. Let we call A1 and A2 each 128kb in size. One of these
buddies is further divided into two 64kb buddies let say B1 and B2. But the next highest power of 25kb is 32kb
so, either B1 or B2 is further divided into two 32kb buddies(C1 and C2) and finally one of these buddies is
used to satisfy the 25kb request. A split block can only be merged with its unique buddy block, which then
reforms the larger block they were split from.
Fibonacci buddy system –
This is the system in which blocks are divided into sizes which are Fibonacci numbers. It satisfies the
following relation:
Zi = Z(i-1)+Z(i-2)
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 144, 233, 377, 610. The address calculation for the binary and weighted buddy
systems is straight forward, but the original procedure for the Fibonacci buddy system was either limited to a
small, fixed number of block sizes or a time consuming computation.
Advantages –
• In comparison to other simpler techniques such as dynamic allocation, the buddy memory system has
little external fragmentation.
• The buddy memory allocation system is implemented with the use of a binary tree to represent used or
unused split memory blocks.
• The buddy system is very fast to allocate or deallocate memory.
• In buddy systems, the cost to allocate and free a block of memory is low compared to that of best-fit
or first-fit algorithms.
• Other advantage is coalescing.
• Address calculation is easy.
What is coalescing?
It is defined as how quickly adjacent buddies can be combined to form larger segments this is known as
coalescing.
For example, when the kernel releases the C1 unit it was allocated, the system can coalesce C1 and C2 into a
64kb segment. This segment B1 can in turn be coalesced with its buddy B2 to form a 128kb segment.
Ultimately we can end up with the original 256kb segment.
Drawback –
The main drawback in buddy system is internal fragmentation as larger block of memory is acquired then
required. For example if a 36 kb request is made then it can only be satisfied by 64 kb segment and remaining
memory is wasted.

2. Slab Allocation –

A second strategy for allocating kernel memory is known as slab allocation. It eliminates fragmentation caused
by allocations and deallocations. This method is used to retain allocated memory that contains a data object of
a certain type for reuse upon subsequent allocations of objects of the same type. In slab allocation memory
chunks suitable to fit data objects of certain type or size are preallocated. Cache does not free the space
immediately after use although it keeps track of data which are required frequently so that whenever request is
made the data will reach very fast. Two terms required are:
• Slab – A slab is made up of one or more physically contiguous pages. The slab is the actual container
of data associated with objects of the specific kind of the containing cache.
• Cache – Cache represents a small amount of very fast memory. A cache consists of one or more slabs.
There is a single cache for each unique kernel data structure.
Example –
• A separate cache for a data structure representing processes descriptors
• Separate cache for file objects
• Separate cache for semaphores etc.
Each cache is populated with objects that are instantiations of the kernel data structure the cache represents.
For example the cache representing semaphores stores instances of semaphore objects, the cache representing
process descriptors stores instances of process descriptor objects.
Implementation –
The slab allocation algorithm uses caches to store kernel objects. When a cache is created a number of objects
which are initially marked as free are allocated to the cache. The number of objects in the cache depends on
size of the associated slab.
Example – A 12 kb slab (made up of three contiguous 4 kb pages) could store six 2 kb objects. Initially all
objects in the cache are marked as free. When a new object for a kernel data structure is needed, the allocator
can assign any free object from the cache to satisfy the request. The object assigned from the cache is marked
as used.
In linux, a slab may in one of three possible states:
1. Full – All objects in the slab are marked as used
2. Empty – All objects in the slab are marked as free
3. Partial – The slab consists of both
The slab allocator first attempts to satisfy the request with a free object in a partial slab. If none exists, a free
object is assigned from an empty slab. If no empty slabs are available, a new slab is allocated from contiguous
physical pages and assigned to a cache.
Benefits of slab allocator –
• No memory is wasted due to fragmentation because each unique kernel data structure has an
associated cache.
• Memory request can be satisfied quickly.
• The slab allocating scheme is particularly effective for managing when objects are frequently
allocated or deallocated. The act of allocating and releasing memory can be a time consuming process.
However, objects are created in advance and thus can be quickly allocated from the cache. When the kernel
has finished with an object and releases it, it is marked as free and return to its cache, thus making it
immediately available for subsequent request from the kernel.