Operating System - 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.

• Logical Address or Virtual Address (represented in bits): An address generated by the CPU
• Logical Address Space or Virtual Address Space( represented in words or bytes): The set of all logical addresses generated by a program
• Physical Address (represented in bits): An address actually available on memory unit
• Physical Address Space (represented in words or bytes): The set of all physical addresses corresponding to the logical addresses

Example:

• If Logical Address = 31 bit, then Logical Address Space = 2³¹ words = 2 G words (1 G = 2³⁰)
• If Logical Address Space = 128 M words = 2⁷ * 2²⁰ words, then Logical Address = log₂ 2²⁷ = 27 bits
• If Physical Address = 22 bit, then Physical Address Space = 2²² words = 4 M words (1 M = 2²⁰)
• If Physical Address Space = 16 M words = 2⁴ * 2²⁰ words, then Physical Address = log₂ 2²⁴ = 24 bits

The mapping from virtual to physical address is done by the memory management unit (MMU) which is a hardware device and this mapping is known as paging technique.

• The Physical Address Space is conceptually divided into a number of fixed-size blocks, called frames.
• The Logical address Space is also splitted into fixed-size blocks, called pages.
• Page Size = Frame Size

Let us consider an example:

• Physical Address = 12 bits, then Physical Address Space = 4 K words
• Logical Address = 13 bits, then Logical Address Space = 8 K words
• Page size = frame size = 1 K words (assumption)

Address generated by CPU is divided into

• Page number(p): Number of bits required to represent the pages in Logical Address Space or Page number
• Page offset(d): Number of bits required to represent particular word in a page or page size of Logical Address Space or word number of a page or page offset.

Physical Address is divided into

• Frame number(f): Number of bits required to represent the frame of Physical Address Space or Frame number.
• Frame offset(d): Number of bits required to represent particular word in a frame or frame size of Physical Address Space or word number of a frame or frame offset.

The hardware implementation of page table can be done by using dedicated registers. But the usage of register for the page table is satisfactory only if page table is small. If page table contain large number of entries then we can use TLB(translation Look-aside buffer), a special, small, fast look up hardware cache.

• The TLB is associative, high speed memory.
• Each entry in TLB consists of two parts: a tag and a value.
• When this memory is used, then an item is compared with all tags simultaneously.If the item is found, then corresponding value is returned.

Main memory access time = m
If page table are kept in main memory,
Effective access time = m(for page table) + m(for particular page in page table)

LIST OF SHELL PROGRAM

/* 1)program to illustrate if  */
#!/bin/bash
echo " enter a value"
read a
echo " enter b value"
read b
if [ $a -ne $b ]
then
    echo "a is not equal to b"
fi

/* 2)program to illustrate if else */
#!/bin/bash
echo "Enter a value"
read a
echo "Enter b value"
read b
if [ $a -eq $b ]
then
 echo "a is equal to b"
else
 echo "a is not equal to b"
fi

/* 3)program to illustrate nested if else */
#!/bin/bash
echo "Enter a value"
read a
echo "Enter b value"
read b
echo "Enter c value"
read c
if [ $a -gt $b  -a $a -gt $c ]
then
     echo "a is big"
elif [ $b -gt $c ]
then
     echo "b is big"
else
     echo "c is big"                       
fi

/* 4)program to find Odd or Even numbers */
#!/bin/bash
echo " enter any no"
read n
x=`expr $n % 2`
if [ $x -eq 0 ]
then
    echo "$n is even"
else
    echo "$n is odd"
fi

/* 5)program to illustrate switch case */
#!/bin/bash
echo "enter 1st value"
read x
echo  "enter 2nd value"
read y
echo "enter 1 adding"
echo "enter 2 sub"
echo "enter 3 mul"
echo "enter 4 quo"
echo "enter 5 rem"
echo "enter 6 exit"
echo "enter * invalid number"
echo "enter u r choice"
read s
case $s in
1)p=`expr $x + $y`
echo "sum =$p"
;;

2)p=`expr $x - $y`
echo "sub=$p"
;;

3)p=`expr $x \* $y`
echo "mul=$p"
;;

4)p=`expr $x / $y`
echo "quo =$p"
;;

5)p=`expr $x % $y`
echo "rem=$p"
;;

6)exit
;;

*)echo "wrong choice"
;;
esac

/* 6) program to find factorial using while*/
#!/bin/bash
echo "enter any  number"
read n
fact=1
while [ $n -ne 0 ]
do
fact=`expr $fact \* $n`
n=`expr $n - 1`
done
echo "factorial is : $fact"

/* 6.1)program to find factorial using for*/
#!/bin/bash
fact=1
echo "enter a number"
read n
for (( i=$n; i>=1; i-- ))
do
fact=`expr $fact \* $i`
done
echo "the factorial of $n is $fact"

/* 7)program to illustrate multiplication using while  */
#!/bin/bash
echo "multiplication table"
echo "which table u want"
read n
iter=1
while [ $iter -le 10 ]
do
res=`expr $n \* $iter`
echo $n"*"$iter "=" $res
iter=`expr $iter + 1`
done

/* 7.1)program to illustrate multiplication using for  */
#!/bin/bash
echo "multiplication table"
echo "which table u want"
read n
iter=1
for((  ; $iter < 10 ; ))
do
res=`expr $n \* $iter`
echo $n"*"$iter "=" $res
iter=`expr $iter + 1`
done

/* 8)program to find perfect number using while */
#!/bin/bash
echo enter any number
read n
sum=0
i=1
while [ $i -lt $n ]
do
    x=`expr $n % $i`
    if [ $x -eq 0 ]
    then
    sum=`expr $sum + $i`
    fi
i=`expr $i + 1`
done
if [ $sum -eq $n ]
then
echo number is perfect
else
echo number is not a perfect
fi

/* 8.1)program to find perfect number using for */
#!/bin/bash
echo enter any number
read n
sum=0
i=1
for ((  ;  $i <  $n ; ))
do
    x=`expr $n % $i`
    if [ $x -eq 0 ]
    then
    sum=`expr $sum + $i`
    fi
i=`expr $i + 1`
done
if [ $sum -eq $n ]
then
echo number is perfect
else
echo number is not a perfect
fi

/* 9)program to find prime number using while  */
#!/bin/bash
echo "enter any number"
read n
c=0
i=1
while [ $i -le $n ]
do
 x=`expr $n % $i`
 y=`expr $n % $n`
 if [ $x -eq 0 -a $y -eq 0 ]
 then
 c=`expr $c + 1`
 fi
 i=`expr $i + 1`
done
if [ $c -eq 2 ]
then
echo "$n is a prime number"
else
echo "$n is a not a prime number"
fi

/* 9.1)program to find prime number using for  */
#!/bin/bash
echo "enter any number"
read n
c=0
for (( i=1; i<=$n; i++ ))
do
 x=`expr $n % $i`
 y=`expr $n % $n`
 if [ $x -eq 0 -a $y -eq 0 ]
 then
 c=`expr $c + 1`
 fi
done
if [ $c -eq 2 ]
then
echo "$n is a prime number"
else
echo "$n is a not a prime number"
fi

/* 10)program to reverse the given number using while */
#!/bin/bash
echo "enter any number:"
read n
s=$n
rev=0
while [ $n -gt 0 ]
do
rem=`expr $n % 10`
n=`expr $n / 10`
rev=`expr $rev \* 10 + $rem`
done
echo "$s reverse number  is $rev"

output:

/* 10.1)program to reverse the given number using for */
#!/bin/bash
echo "enter any number:"
read n
s=$n
rev=0
for ((  ;  $n > 0 ; ))
do
rem=`expr $n % 10`
n=`expr $n / 10`
rev=`expr $rev \* 10 + $rem`
done
echo "$s reverse number  is $rev"

output:

/* 11)program to illustrate sequentional for  */
for i in $(seq 1 2 10)
do
echo $i
done

/* 12)program to illustrate sequentional for  */
for i in $(seq 10)
do
echo $i
done

/* 13)program to illustrate hi and bye  */

hi()
{
 echo "welcome to unix"
}
bye()
{
date
ls -l
banner  ram is a boy
cowsay sita is a girl
}

output:

Banker's algorithm

Banker's algorithm

The Banker algorithm is a resource allocation and deadlock avoidance algorithm developed by Edsger Dijkstra, that tests for safety by simulating the allocation for predetermined maximum possible amounts of all resources, then makes an “safe-state” check to test for possible activities, before deciding whether allocation should be allowed to continue.

For the Banker's algorithm to work, we need to know three things:
    • How much of each resource each process could possibly request[MAX]
    • How much of each resource each process is currently holding[ALLOCATED]
    • How much of each resource the system currently has available[AVAILABLE]
Implementation :Let ‘n’ be the number of processes in the system and ‘m’ be the number of resources types.
Available : 

• It is a 1-d array of size ‘m’ indicating the number of available resources of each type.
• Available[ j ] = k means there are ‘k’ instances of resource type R_j
  

Max :

• It is a 2-d array of size ‘n*m’ that defines the maximum demand of each process in a system.
• Max[ i, j ] = k means process P_i may request at most ‘k’ instances of resource type R_j.
  

Allocation :

• It is a 2-d array of size ‘n*m’ that defines the number of resources of each type currently allocated to each process.
• Allocation[ i, j ] = k means process P_i is currently allocated ‘k’ instances of resource type R_j
  

Need :

•  It is a 2-d array of size ‘n*m’ that indicates the remaining resource need of each process.
• Need [ i,  j ] = k means process P_i currently need ‘k’ instances of resource type R_j
  for its execution.
  
• Need [ i,  j ] = Max [ i,  j ] – Allocation [ i,  j ]
  

Note:

Allocation_i specifies the resources currently allocated to process P_i a
Need_i specifies the additional resources that process P_i may still request to complete its task.
Banker’s algorithm consist of Safety algorithm and Resource request algorithm


Safety Algorithm
The algorithm for finding out whether or not a system is in a safe state can be described as follows:

1) Let Work and Finish be vectors of length ‘m’ and ‘n’ respectively.
Initialize: Work = Available
Finish[i] = false; for i=1, 2, 3, 4….n

2) Find an i such that both
a) Finish[i] = false
b) Need_i <= Work
if no such i exists goto step (4)

3) Work = Work + Allocation[i]
Finish[i] = true
goto step (2)

4) if Finish [i] = true for all i
then the system is in a safe state

Resource-Request Algorithm
Let Request_i be the request array for process P_i. Request_i [j] = k means process P_i wants k instances of resource type R_j. When a request for resources is made by process P_i, the following actions are taken

1) If Request_i <= Need_i
Goto step (2) ; otherwise, raise an error condition, since the process has exceeded its maximum claim.

2) If Request_i <= Available
Goto step (3); otherwise, P_i must wait, since the resources are not available.

3) Have the system pretend to have allocated the requested resources to process Pi by modifying the state as
follows:
Available = Available – Requesti
Allocation_i = Allocation_i + Request_i
Need_i = Need_i– Request_i

Program on Bankers algorithm
#include <stdio.h>
#include <stdlib.h>
void main()
{
    int Max[10][10], need[10][10], alloc[10][10];
    int avail[10], completed[10], safeSequence[10];
    int p, r, i, j, process, count=0;
    printf("\nEnter the no of processes : ");
    scanf("%d", &p);
    for(i = 0; i< p; i++)
    completed[i] = 0;
    printf("\nEnter the no of resources : ");
    scanf("%d", &r);
    printf("\nEnter the Max Matrix for each process : ");
    for(i = 0; i < p; i++)
    {
    printf("\nFor process %d : ", i + 1);
    for(j = 0; j < r; j++)
        scanf("%d", &Max[i][j]);
    }
    printf("\nEnter the allocation for each process : ");
    for(i = 0; i < p; i++)
    {
    printf("\nFor process %d : ",i + 1);
    for(j = 0; j < r; j++)
        scanf("%d", &alloc[i][j]);
    }
    printf("\nEnter the Available Resources : ");
    for(i = 0; i < r; i++)
    scanf("%d", &avail[i]);
    for(i = 0; i < p; i++)
    {
      for(j = 0; j < r; j++)
       {
        need[i][j] = Max[i][j] - alloc[i][j];
       }
    }
    do
    {
        printf("\n Max matrix:\tAllocation matrix:\n");
        for(i = 0; i < p; i++)
        {
        for( j = 0; j < r; j++)
            printf("%d ", Max[i][j]);
        printf("\t\t");
        for( j = 0; j < r; j++)
            printf("%d ", alloc[i][j]);
        printf("\n");
        }
        process = -1;
        for(i = 0; i < p; i++)
        {
        if(completed[i] == 0)//if not completed
        {
            process = i ;
            for(j = 0; j < r; j++)
            {
            if(avail[j] < need[i][j])
            {
                process = -1;
                break;
            }
            }
        }
        if(process != -1)
            break;
        }

       if(process != -1)
         {
              printf("\nProcess %d runs to completion!", process + 1);
        safeSequence[count] = process + 1;
        count++;
        for(j = 0; j < r; j++)
        {
            avail[j] += alloc[process][j];
            alloc[process][j] = 0;
            Max[process][j] = 0;
            completed[process] = 1;
        }
        }
    }while(count != p && process != -1);

    if(count == p)
    {
        printf("\nThe system is in a safe state!!\n");
        printf("Safe Sequence : < ");
        for( i = 0; i < p; i++)
        printf("%d ", safeSequence[i]);
        printf(">\n");
    }
    else
        printf("\nThe system is in an unsafe state!!");
}


Single Resource Output:

Multiple Resource Output:

Page Replacement Algorithms - Optimal Page Replacement

Page Replacement Algorithms - Optimal Page Replacement

//program on page replacement alogarthim -optimal 
#include<stdio.h>
main()
{
 int frames[10],n,seq[30],c=0,i,j,nl,x=0,m,k,flag=0,l,mf[10];
 int c1,c2,c3,m1,m2;
 printf("enter number of pages:");
 scanf("%d",&nl);
 printf("\n enter pages:");
 for(i=0;i<nl;i++)
  scanf("%d",&seq[i]);
 printf("\n enter no of frames:");
 scanf("%d",&n);
 for(i=0;i<n;i++)
  frames[i]=-1;
 for(x=0,i=0;x<n;i++)
 {
  for(j=0;j<n;j++)
  {
   flag=0;
   if(seq[i]==frames[j])
   {
     flag=1;
     break;
   }
  }
  if(flag==0)
   {
   frames[x]=seq[i];
   m=i;
   x++;
   c=c+1;
   printf("\n \n");
   for(k=0;k<x;k++)
    printf("\t %d",frames[k]);
   }
 }
  for(i=m+1;i<nl;i++)
  {
   for(j=0;j<n;j++)
   {
    flag=0;
    if(seq[i]==frames[j])
    {
     flag=1;
     break;
    }
   }
   if(flag==0)
   {
    for(k=0;k<n;k++)
    mf[k]=0;
    c1=0;c2=0;c3=0;
    for(j=i+1;j<nl;j++)
    {
     for(k=0;k<n;k++)
     {
      if(frames[k]==seq[j])
      {
       mf[k]=mf[k]+1;
       if(k==0)
         c1=1;
       else if(k==1)
         c2=1;
      else if(k==2)
         c3=1;
      break;
      }
     }
     if(((c1==1)&&(c2==1))||((c2==1)&&(c3==1))||((c3==1)&&(c1==1)))
            break;
    }
    m1=0;
    m2=mf[0];
    for(k=0;k<n;k++)
    {
     if(mf[k]<m2)
     {
      m1=k;
      m2=mf[k];
     }
    }
    frames[m1]=seq[i];
    c=c+1;
    printf("\n \n");
    for(l=0;l<n;l++)
     printf("\t %d",frames[l]);
   }
  }
  printf("\n\n\n the n of pages faults=%d",c);
}

output:

Page Replacement Algorithms - LRU

Page Replacement Algorithms - LRU

//Program on Page Replacement Algorithms - LRU
#include<stdio.h>
void main()
{
 int frames[10],n,seq[30],c=0,i,j,n1,x=0,m,k=0,flag=0,l,fc[10],r;
 printf("\n enter number of pages : ");
 scanf("%d",&n1);
 printf("\n enter the pages : ");
 for(i=0;i<n1;i++)
  scanf("%d",&seq[i]);
 printf("enter the number of frames:");
   scanf("%d",&n);
 for(i=0;i<n;i++)
 {
   frames[i]=-1;
   fc[i]=0;
 }
 for(x=0,i=0;x<n;i++)
 {
  for(j=0;j<n;j++)
  {
   flag=0;
   if(seq[i]==frames[j])
   {
    flag=1;
    k++;
    fc[j]=k;
    break;
   }
  }
  if(flag==0)
  {
   frames[x]=seq[i];
   m=i;
   c=c+1;
   k++;
   fc[x]=k;
   x++;
   printf("\n \n");
   for(l=0;l<x;l++)
    printf("\t %d",frames[l]);
  }
 }
 for(i=m+1;i<n1;i++)
 {
   for(j=0;j<n;j++)
   {
    flag=0;
    if(seq[i]==frames[j])
    {
     flag=1;
     k++;
     fc[j]=k;
     break;
    }
   }
   if(flag==0)
   {
    r=fc[0];
    j=0;
    for(l=1;l<n;l++)
    {
     if(r>fc[l])
     {
      r=fc[l];
      j=l;
     }
    }
    frames[j]=seq[i];
    k++;
    fc[j]=k;
    c=c+1;
    printf("\n \n");
    for(l=0;l<n;l++)
      printf("\t %d",frames[l]);
  }
 }
 printf("\n \n the no of pages faults:%d",c);
}


output:

Page Replacement Algorithms - FIFO

Page Replacement Algorithms - FIFO

When a page fault occurs, the operating system has to choose a page to remove from memory to make room for the page that has to be brought in. The page replacement is done by swapping the required pages from backup storage to main memory and vice-versa. 

The page replacement algorithm is evaluated by running the particular algorithm on a string of memory references and compute the page faults.Referenced string is a sequence of pages being referenced.

Page faults are not errors and are common and necessary to increase the amount of memory available to programs in any operating system that utilizes virtual memory, including Microsoft Windows, Mac OS X, Linux and Unix.

Each operating system uses different page replacement algorithms. To select the particular algorithm, the algorithm with lowest page fault rate is considered.

1.First-In, First-Out page replacement

2.Least recently used page replacement

3.Optimal page replacement algorithm

 Program on FIFO( First-In, First-Out ) page replacement

//Program to illustrate First In First Come Page Replacement Alogarthim
#include<stdio.h>
void main()
{
 int frames[10],n,seq[30],c=0,i,j,n1,x=0,m,k,flag=0,l;
 printf("\n enter the number of pages : ");
 scanf("%d",&n1);
 printf("\n enter the pages : ");
 for(i=0;i<n1;i++)
   scanf("%d",&seq[i]);
 printf("enter the number of frames : ");
   scanf("%d",&n);
 for(i=0;i<n;i++)
   frames[i]=-1;
 for(x=0,i=0;x<n;i++)
 {
   for(j=0;j<n;j++)
   {
     flag=0;
     if(seq[i]==frames[j])
     {
          flag=1;
          break;
     }
   }
 
    if(flag==0)
   {
     frames[x]=seq[i];
     m=i;
     x++;
     c=c+1;
     printf("\n\n");
    for(k=0;k<x;k++)
      printf("\t %d",frames[k]);
   }
  }
  k=0;
  for(i=m+1;i<n1;i++)
  {
   if(k==n)
     k=0;
   for(j=0;j<n;j++)
   {
    flag=0;
    if(seq[i]==frames[j])
    {
      flag=1;break;
    }
   }
   if(flag==0)
   {
    frames[k]=seq[i];
    k++;
    c=c+1;
    printf("\n \n");
    for(l=0;l<n;l++)
     printf("\t %d",frames[l]);
   }
  }
  printf("\n \n the no of page faults = %d",c);
 }

output:

 

How to Install VirtualBox Guest Additions on Ubuntu 18.04 Guest / virtual machine

Install VirtualBox Guest Additions on Ubuntu 18.04 Guest / virtual machine

Step 1. Install required packages. Before installing VirtualBox Guest Additions on Ubuntu 18.04 we need to install some required packages. So open the terminal and run the following command.

sudo apt install linux-headers-$(uname -r) build-essential dkms

Step 2. Install Guest Additions using virtual box. In order To install VirtualBox Guest Additions on Ubuntu virtual machine, Got to VirtualBox - select the Devices from VirtualBox host application menu - click Insert Guest Additions CD image.

Step 3. This will open a pop up window and it will ask you to run it. Press Run button (see the picture below) After pressing Run button it will install VirtualBox Guest Additions on Ubuntu 18.04. Press enter to close the window.

Step 4. Shut down your Ubuntu 18.04 Guest.

Step 5. Start Ubuntu 18.04 virtual machine and check if copy and paste works. Finish