08Jun/16

Interpreter and Compiler

June 8, 2016Ccompilor, interpreter, translatorDreamMaker

Translator It is a computer program that translates high level programming language code into machine code. Three type of translate programs are available. [1] Interpreter: An Interpreter is a computer program thatRead More…

08Jun/16

Types of programming languages

June 8, 2016Clanguage_type, programming_language_typeDreamMaker

Programming languages can be divided into the following three types. [1] Machine language: Machine language is the only language that can be understood by the computer. It contains two symbols,0 and 1.Read More…

08Jun/16

Flowchart

June 8, 2016Calgorithm, flowcharDreamMaker

A Flowchart is a graphical representation of a process. It uses some predefined symbols to represent a process in simple and understandable manner. Flowchart Symbols: [1] Start/Stop: An oval or rounded rectangleRead More…

08Jun/16

What is Algorithm?

June 8, 2016CalgorithmDreamMaker

“Algorithm” word is derived from the Persian mathematician Abu zafaribne Muhammad musaal-khwarismi, who introduce the concept of algorithm. He introduced a sequential format for the instruction to perform a specific task. ThisRead More…

In this and following posts I am going to explain one of the most important issue of the operating system design called “Deadlock”. It deals with the basic concept of deadlock, how it occurs and finally summing up with its possible solutions.

A system has a finite number of resources to be distributed among multiple processes.
These resources are of different types such as memory space, CPU cycles, files, I/O devices.

A system may have multiple instances of different resources. For example if a system has five printers, then the resource type printer has five instances.
If a process requests an instance of resource type then allocation of any instance of that resource type will satisfy the request.
Each process must request a resource before using it and must release after using it.

A process may request as many resources as it require to complete its task.
The number of resources should not exceed the total number of available resources. For example a process cannot request two disk drives if system has only one.

In normal operation mode, a process may utilize a resource only in the following sequences:

Request: the process requests the resource. If that resource is not free, then the process has to wait until it becomes free.
Use: After getting control of the desired resource, the process can use it. For example if the resource is printer, it can print on the printer.
Release: the process releases the resource.

A system table keeps record about each allocated and free resources.
A system also keeps track of the different processes to which resources are allocated.

If the requested resource is allocated to other process then the process is added to the queue of processes waiting for that resource.
The resources may be either physical resources such as printer, memory, processor or logical resources such as files.

Suppose a system has three CD –RW drives and three processes each having CD-RW drive. Now if each process requests another drive, the process will be in a deadlock state.

This example describes the deadlock of the same resource type.
Deadlock may also occur for different resource type.

For example consider a system having one printer and one tap drive. Suppose tap drive is allocated to process p1 and printer is allocated to process p2. If process p1 requests the printer and process p2 requests the tap drive, then it creates a deadlock.

In simple terms,

A system is said to be in a deadlock state if some processes are waiting for each other to release resources to complete their task.

In a deadlock state, processes will never complete their task and system resources are blocked.
For more on deadlock, refer “Necessary Conditions to occur Deadlock”

In my last post I discussed about “Types of Function”. In this post I will serve one important concept which is related to the function e.i Call by value v/s Call by reference or sometimes also referred to pass by value v/s pass by reference.

We have learnt in my previous post about function with arguments and as we know that while calling such functions we have to supply appropriate arguments.

There are two ways through which we can pass arguments to the function.

Call by Value (Pass by Value)
Call by Reference (Pass by Reference)

In this post I am going to discuss the basic difference between these two methods.
Difference between these two methods can be summarized as below:

Call by Value	Call by Reference
During the function call if we pass values of arguments to the called function instead of memory address than it is referred to as pass by value.	During the function call if we pass memory address of arguments to the called function then it is referred to as pass by reference or pass by address.
In pass by value method, a duplicate copy of the original arguments is created and that copy is passed to the called function.	In pass by reference method, since we are passing memory location of the arguments, no duplicate copy will be prepared
Any changes made to the passed arguments inside the calling function are reflected to that copy only. No changes are made to the original copy of the arguments. That means our original value of the arguments inside the main () will be not affected.	Any changes made to the arguments inside the calling function will be directly reflected to the actual arguments inside the main () also.
It does not require pointer to receive arguments as values are passed and not the memory address.	It requires pointer to receive arguments as memory addresses are passed.

The following example to swap two values using call by value and call by reference demonstrates the difference between these two methods.

Example using Call by Value

The following program uses swapByValue() function to exchange values of X and Y using call by value method.


#include "stdio.h"

void swapByValue(int, int); /* Function Prototype */

void main() /* Main function */
{
    int x = 10, y = 20;
    
    printf("\n Before swapping X: %d, Y: %d\n", x, y);
    /* actual arguments will be as it is */
    swapByValue(x, y);     /* calling function for swapping */
    printf("\n After swapping X: %d, Y: %d\n", x, y);
}

void swapByValue(int a, int b)  /* Function definition */
{
   int t;
   t = a; a = b; b = t;    /* swapping */
}

OUTPUT
======
X: 10, Y: 20

Since any changes made to the passed arguments inside the calling function are reflected to that copy only and no changes are made to the original copy of the arguments, values of X and Y are not affected as it operates on local copies of a and b only.

Example using Call by Reference

The following program uses swapByReference() function to exchange values of X and Y using call by reference method. Note that we are passing addresses of X and Y inside the function.

#include "stdio.h"

void swapByReference(int *, int *); /* Function Prototype with pointer */

void main() /* Main function */
{
    int x = 10, y = 20;
    
    printf("\n Before swapping X: %d, Y: %d\n", x, y);
    /* actual arguments will be as it is */
    swapByReference(&x, &y);     /* Passing addresses for swapping */
    printf("\n After swapping X: %d, Y: %d\n", x, y);
}

void swapByReference(int *a, int *b)  /* Function definition with pointer */
{
   int t;
   t = *a; *a = *b; *b = t;    /* swapping */
}

OUTPUT
======
X: 20, Y: 10

Since any changes made to the passed arguments inside the calling function are reflected to the original copy of the arguments, values of X and Y are affected directly.

I hope after reading this post, it would be clear to you how these two methods behave differently.

If you remember, we were talking about functions since last two posts. My previous post was on “Elements of Function”.
In this post we will discuss about “Types or Categories of Function”.

We can categorize functions into the following types based on function arguments and return value.

Function with no arguments and no return value
Function with no arguments and return value
Function with arguments but no return value
Function with arguments and return value.
Function that returns multiple values.

Function with no arguments and no return value

This type of function neither receives any arguments nor returns any value.

We need not to pass arguments while calling that function and we also don’t need any receiving parameter to receive return value as it does not return any value.

The below example to find prime number implements function with no arguments and no return value.

/*C program to check whether a number entered by user is prime or not using function with no arguments and no return value*/
#include "stdio.h"

void main()
{
    void prime();        // function declaration
    prime();            // No argument is passed to prime().
}
/* There is no return value to calling function main(). So, return type of prime() is void */

void prime()
{ 
   int num,i,flag=0;
   printf("Enter positive integer enter to check:\n");
   scanf("%d",&num);
   for(i=2;i<=num/2;++i)
   {
      if(num % i == 0)
      {
         flag = 1;
      }
   }
   if (flag == 1)
      printf("%d is not prime",num);
   else 
      printf("%d is prime",num); 
}

Function with no arguments and return value

A function that does not take any argument but has return value falls under this category.

Since it does not take any arguments, we need not to pass arguments during the function call but we need receiving variable to receive the value returned by the function.

The following program to calculate sum implements function with no arguments and return value.

/*C program to calculate sum using function with no arguments and return value*/
#include "stdio.h"

void main()
{
   float result ;          // variable to receive sum
   float sum();            // function declaration
   result = sum();        // No argument is passed to sum().
   printf(“\n Sum is %.2f “ , result) ;
}
/* return type of sum() is float */

float sum()
{ 
    float x, y, ans;
    printf("Enter X & Y:\n");
    scanf("%f %f",&x, &y);

    ans = x + y; 
    return ans;    // returns result to calling function i.e. main() 
}

Function with arguments but no return value

A function that takes arguments but does not return any value falls under this category.

Since it takes arguments, we need to pass them during the function call but we don’t need receiving variable to receive the value as it does not return any value.

The following program to calculate sum implements function with arguments and no return value.

Note that since function sum () does not have return type, we cannot use value calculated by sum () into main () so if we require further processing on calculated result inside main () then we have to provide return value and if no further processing is required inside the main () then its ok to use function with no return value.

Function with arguments and return value

A function that takes arguments as well as return value falls under this category.

Since it takes arguments, we need to pass them during the function call.
We also need receiving variable to receive the value as it returns value.

The following program to calculate sum implements function with arguments and return value.

Function that returns multiple value

Normally a function returns only single value but a function can also returns multiple values.

We can make a function to return multiple values using pointer.
The following program to swap values implements function that returns multiple value.

/*C program to swap values using function with multiple return value by pointer*/

#include "stdio.h"

void main()
{
   float x, y ;          // variable to declaration

   void swap(float *, float *); //function declaration with pointer

   printf(“\n Enter X & Y : “);   // read data from user 
   scanf(“%f %f”, &x, &y);        

   swap(&x, &y);       // arguments are passed by reference.

   printf(“\n X & Y after swapping is %.2f %.2f “ , x, y);
}

/* return type of sum() is float */

float sum(float *a, float *b)
{ 
   float temp ;     

   temp = *a ;       // swap value using pointer
   *a = *b ; 
   *b = temp ;
}

Note: We will look into more detail about functions with pointer when we deal with pointers.

Hello everyone!. You might remember about my last post on “Introduction to Function” in which I had discussed about the what function is and what advantages it can bring. If you haven’t read my previous post yet, I strongly suggest you to read it first as this post is a supplementary for the same.

In this post as promised I will try to explain basic elements of functions in as easy way as possible.

Elements of Functions

Every function has the following elements:

Function Declaration (Function Prototype)
Function Definition
Function Call

Function Declaration (Function prototype)

Similar to variables, in C, every function needs to be declared before it can be used.

Functions can be declared either globally (inside the main() ) or locally (outside the main() ) as per the program requirement. (You can read more on this at Structure of C Program)

Syntax:

return_type function_name( argument list ) ;

Function prototype has the following three parts:

Return type :

It specifies return type of the function that means type of the data that a function will return such as int, float, char etc.
Function that does not return any value will have return type as void.

Function Name:

It is the name of the function and it should be any meaningful name.
It should follow all naming convention rules.
Some examples of function names are display, show, calculate etc.

Argument List:

Argument list specifies list of all arguments required for the function to perform the desired task.
Arguments are separated by comma. It may include both data type and argument name but normally only data type is provided.
The following is an example of function prototype for doing sum of two float values:

Function Declaration Example

float sum ( float, float ) ;  OR  float sum (float x, float y) ;

Where, int is a return type, sum is the name of the function and int x, int y are the argument list.

Function Definition

Function definition contains executable block of statements.
It can be written either before or after the main() but normally it is written after the main().

Syntax:

return_type function_name( argument list )
{
    // local variable declaration ;

    // executable statements ;

      :
      :

    // return statement ;
}

The function definition contains the following two parts:

Function Header
Function Body

Function Header:

The first line of function definition is known as function header.
It consists of three parts: return type, function name and argument list.

Function Body:

It consists of three parts: local variable declaration part, executable part and return statement.
All the required variables are declared at the local variable declaration part.
Executable part contains all the executable statements that performs actual task.
return statement should be the last statement inside the function body. It is optional.
If return type of function is void then it can be omitted but function having return type other than void must include return statement.

Example of function definition is given below for above function declaration.

Function Definition Example

float sum ( float x, float y)
{
    float result ;          // local variable
    result = x + y ;       // executable statement

    return result ;       // return statement
}

Example of function without return type is as follow:

void sum ( float x, float y)
{
    float result ;         // local variable
    result = x + y ;      // executable statement

    printf(“\n Sum is %.2f” , result);

    return ;        // return statement. its optional
}

Note : We can omit return statement if function return type is void.

Function Call

A function can be called simply by using name of the function followed by a list of Actual parameters (Arguments) if any.
The following example calls sum() function that we defined above.

void main ( )
{
    float result ;                   // receiver local variable

    result = sum (10.0, 20.0 );     // function call

    printf(“\n Sum is %.2f” , result);

}

When the compiler encounters a function call, the control is transferred to the function definition and executes the function line by line and a computed value is returned with the help of return statement.
The returned value is assigned to the receiver variable. This is illustrated as below:

Arguments that passed in function call and arguments receiving in function definition should have the same data type.

For example in above function call sum (10.0, 20.0) we have passed arguments of float type and inside function definition those float type arguments are received by float type variable x and y respectively. In short, type of arguments in function call and function definition should be same.

The argument names used in function definition is known as formal parameters.

With this post we are moving on to the advance topics of C language.
In this post, I am going to discuss one of the most important concept of modern programming languages i.e Function. So let’s dive in.

A function is a block of code that performs a specific task.

When a set of related executable statements are places within a group then it is referred to as function.
We can use functions for the operations which are need to be repeated.

C functions can be classified into two categories:

Library Functions
User-defined Functions (UDF)

Library Functions

Library functions are provided by the C programming language.
They are also knows as in-built or ready-made functions.
User need not to define them. User can directly use them in the program.
Some examples of library functions are : printf(), scanf(), strlen(), gets(), clrscr(), etc.

User-defined Functions (UDF)

User-defined functions are those functions which are written by the user (programmer).
Similar to variables, they need to be defined before using them because compiler dos not have knowledge about them.
main() is an example of user-defined functions.

Advantages of Functions ( Need for UDF)

Re-usability

One of the major advantages of functions is re-usability.
There are situations in which we need to perform some operations or calculations multiple times. If we do not use functions, we have to rewrite that code again and again.
In such cases, function helps a lot. We can reuse the code which is already written. There is no need to rewrite that code again and again.
Function works on the principle “write once, use multiple times”
So this way, we have to write the functions once and it can be used for multiple times.

Modularity

Function provides modularity into program by dividing large programs into smaller parts called modules.
These modules can easily be coded, tested and debugged separately.
Development will be fast since modules can be assigned to multiple programmers.
Each programmer is responsible to code, test and debug modules assigned to him or her only.
Programmers can work on the different modules of the same projects simultaneously.

Easy debugging

Programs divided into functions can be easily debugged.
Since programs are sub-divided into modules, individual modules are coded, tested and debugged separately.
If any error is found or modules do not work properly, we only need to check the modules responsible for that task.
We need not to check the whole program starting from the scratch.
Since each module is small and implements limited functionality, they are easy to code, debug and modify.
It saves both time and labor.

Easy management

Project management becomes easy as different modules are assigned to different team of programmers.
Programmers can work on separate modules simultaneously on the same projects.
Since task is divided into smaller modules, it becomes easy to handle and manage.

Provides Readability

Programs are divided into different smaller modules and these modules further can be sub-divided for better understanding.
Programs written through functions allow better readability.
They are easy to read and understand.
It helps to understand program flow and logic.

That’s it for this post. Elements of Function will be discussed in the next post so please stay tuned!

Hello there. In my last post I you learnt about searching techniques in which I explained two most common searching techniques i.e. linear search and binary search.

In this post again I am going to discuss another most common operation that we often require to perform on the data that is sorting.

We often require to analyse the data to take some decision. Analysis requires that data should be in sorted order. So we can say that similar to searching,sorting is the another most common operation we need to perform frequently.

Sorting is a process of arranging a set of data in some order.

There are two different methods to sort data either in ascending or in descending order.

There are so many techniques available for sorting such as bubble sort, quick sort, merge sort, selection sort, insertion sort, quick sort etc.

In this post I will try to explain two most common sorting techniques: Bubble sort and selection sort.

Bubble Sort

Bubble sort is the simplest method for sorting. In this method, to arrange elements in ascending order 0^th element is compared with the 1^st If it is greater than the 1^st element then they are interchanged.

In the same way all elements (excluding last) are compared with their next element and interchanged if required. On completing 1st iteration the largest element is placed at the last position.

Similarly, in the second iteration the comparisons are made till the last but one element. This time the second largest element is placed at the second last position.

After all iteration the list becomes a sorted list.

Bubble Sort Implementation

/* C Program to implement Bubble sort. */

#include "stdio.h"
#include "conio.h"

void main( )
{
    int arr[50], n, i, temp ;
    clrscr() ;
    printf("Enter No.of elements (Maximum 50):");
    scanf("%d",&n);
 
    printf("Enter %d integers values...\n", n);
    for (i = 0; i < n; i++)
        scanf("%d",&arr[i]);
    printf ( "Array before sorting:\n") ;
	for ( i = 0 ; i < n ; i++ )
		printf ( "%d\t", arr[i] ) ;

		// bubble sort
	for ( i = 0 ; i < n ; i++ )
	{
	    for ( j = 0 ; j < n - i ; j++ )
            {
                 if ( arr[j] > arr[j + 1] )
	         {
		     temp = arr[j] ;
		     arr[j] = arr[j + 1] ;
		     arr[j + 1] = temp ;
	         }
	    }
        }
	printf ( "\n Array after bubble sort:\n") ;

	for ( i = 0 ; i < n ; i++ )
		printf ( "%d\t", arr[i] ) ;

	getch();
}

Selection Sort

In this method, to arrange elements in ascending order 0^th element is compared with all other element. If 0^th element is greater than the compared element then they are interchanged.

This way, after the first iteration the smallest element is placed at the 0^th
In the same way 1^st element is compared with all other elements and after completion of second iteration, second smallest element is placed at 1^st

The same process is repeated for all other remaining elements.
After all iteration the list becomes a sorted list.
The above figure illustrates the process of selection sort.

/* C Program to implement Selection sort. */

#include "stdio.h"
#include "conio.h"

void main( )
{
    int arr[50], n, i, temp ;

    clrscr() ;

    printf("Enter No.of elements (Maximum 50):");
    scanf("%d",&n);
 
    printf("Enter %d integers values...\n", n);
 
    for (i = 0; i < n; i++)
        scanf("%d",&arr[i]);
   
    printf ( "Array before sorting:\n") ;

	for ( i = 0 ; i < n ; i++ )
	     printf ( "%d\t", arr[i] ) ;
		// selection sort logic
	for ( i = 0 ; i < n-1 ; i++ )
	{
		for ( j = i+1 ; j < n - i ; j++ )
                {
                        if ( arr[i] > arr[j] )
			{
				temp = arr[i] ;
				arr[i] = arr[j] ;
				arr[j] = temp ;
			}
		}
	}
	printf ( "\n Array after selection sort:\n") ;

	for ( i = 0 ; i < n ; i++ )
		printf ( "%d\t", arr[i] ) ;

	getch();
}

My previous post described some useful string handling functions to deal with string data for different operations. In this post I am about to explain one of the most common and frequently required operation called Searching.

Searching is most common operation that is required to perform on the set of data. We often need to look for a particular peach of data of our interest in the available set of data. If data is large enough then manual searching might be time consuming and in some cases it might not be feasible at all.

Today’s majority of the software and devices whether it is our smartphone where we search for particular contact or messages, email or social media sites supports searching operation as it is the primary requirement to deal with the data for better understanding and analysis. Search engines like google, yahoo are the best examples of how searching helps us to make our life more comfortable. Although they uses more complex algorithms, they works on the same principle.

In this post, I will show you how the searching can be implemented using C programming language.

Searching is a process to find out some element from the given set of data.

The search operation may be successful if search value is found and unsuccessful if not found.
There are two standard search methods:

Linear search
Binary search.

Linear search

Linear Search is the simplest searching method.
In this method the search element is sequentially searched in the list.
It can be applied to a sorted or unsorted list of data.
In case of sorted list, searching starts from 0^th element and continues until the element is found or a greater value is found [assume list is sorted in ascending order].
In case of unsorted list, searching starts from 0^th element and continues until the element is found or up to the end of the list.

Example:

Now consider the following example of unsorted array of 10 elements.

Suppose searching element is 50. So 50 is compared with all the elements starting from 0th element.
The searching process is over either 50 is found or the list is over.

Linear Search Implementation

// C Program to implement linear Search.
#include "stdio.h"
 
void main()
{
   int array[50], n, i, search, found = 0;
 
   printf("Enter No.of elements (Maximum 50):");
   scanf("%d",&n);
   printf("Enter %d integers values...\n", n);
 
   for (i = 0; i < n; i++)
      scanf("%d",&array[i]);
 
   printf("Enter value to Serch :");
   scanf("%d", &search);
   for (i = 0; i < n; i++)
   {
      if ( search == array[i] )
      {
        	 found = 1;
	 printf("%d found at location %d.\n", search, i+1);
        	 break;
      }
      
   }
   if ( found == 0 )
      printf("Not found! %d is not present in the list.\n", search);
 
  getch();  
}

Notice that we have used flag variable called “found” just to keep track about the failure of search operation by setting it with initial value 0.
We are setting value 1 if the search value is found and let the user notify by showing the message. If the search value is not present in the list, flag variable found will be unchanged so outside the for loop we are checking against its initial value so that we can notify about the failure of the search operation.

Binary Search

Another most common searching technique is the binary search.
It uses divide and conquer technique for searching.
Binary search can only be applied on sorted data. That means data should be in sorted order before applying binary search.
According to this technique an array or list of data is divided into two parts from some mid point by using the following formula:

mid = (low+high) / 2;

where, mid = mid point , low = starting array index and high= last index of an array.
After splitting an array or list into two parts, there are three possibilities:

Search value > array[mid]: In this case search value is greater than the array [mid] value so searching will be done in the right direction.
Search value < array[mid]: In this case search value is less than the mid point value so searching will be carried on the left side.
Search = array[mid] : In this case our searching is finished as we found the desired value.

Example:

Consider the following example to find out element 82 in the given set of elements:

An array contains 10 elements so initially low will set to index 1 and high will be set to index 10 (note: array index always tarts from 0 but for simplicity we have assume 1).
Since our array has more than two elements, first it will be divided into two sub parts from the mid point using the formula:

mid = (low+ high) / 2

mid = (1+10) / 2

mid = 5 ;

In the first iteration array will be divided from the 5th index as shown in the second figure.
Since our search value 82 is greater than the value present at mid point which is 9, search will be done in the right direction with modified low value (low =mid +1: e.i. 5+1 = 6).
Again the right sub array will be divided into the two sub parts using the same concept.

mid = ( 6+10) /2

mid = 8

We have new mid value as 8 in the net iteration and this time the third case will be executed and so we will get our search value 82 as our mid is equal to our search value.
Binary search offers major improvement in the performance than the linear search.

Binary Search Implementation

// C Program to implement Binary Search
#include "stdio.h"
 
void main()
{
   int array[50], i, low, high, mid, n, search;
 
   printf("Enter No.of elements (Maximum 50):");
   scanf("%d",&n);
   printf("Enter %d integers values...\n", n);
 
   for (i = 0; i < n; i++)
       scanf("%d",&array[i]);
 
   printf("Enter value to Serch :");
   scanf("%d", &search);
 
   low = 0;
   high = n - 1;
   mid = (low+high)/2;
 
   while (low <= high)
   {
      if (array[mid] < search) // search in right direction
         low = mid + 1;
      else if (array[mid] == search) // if mid is the search value
      { 
          printf("%d Found at location %d.\n", search, mid+1);
          break;
      }
      else    // search in left direction
         high = mid - 1;

         mid = (low + high)/2; // split into two parts
   } 

   if (low > high)
      printf("Not found! %d is not present in the list.\n", search);
 
   getch();  
}

We already talked about “Storage Hierarchy” in the previous article in which we explained about the different types of memories and their characteristics. This article deals with the similar topic in which I am going to explain you about Cache Memory and Associative Memory.

A cache is a smaller and faster memory that is used by the CPU to reduce the average memory access time.
It stores the copies of the data which are most frequently used.
It is a temporary storage area that provides easy and fast access of the data compare to main memory.

When the CPU needs a particular piece of information, it first checks whether it is available in the cache or not. If so then the CPU reads from or writes to the cache.

It is much faster than reading from or writing to main memory. Putting a copy of information under the assumption that we will need again soon.

Most CPUs have at least three independent caches: one is instruction to speed up executable instruction fetch, second a data cache to speed up data fetch and store. Last is translation look-aside buffer which translates virtual address to physical address.

Generally caching have the limited size so cached management is an important design problem. Careful selection of its size and a replacement policy can result in 80 to 99 % of all accesses from the case. It will increase the performance.

Main memory can be viewed as a fast catch for secondary storage.
Data transfer from cache to CPU and registers is usually a hardware function, with no o/s intervention.

Associative Memory

Associative memory is a special type of computer memory which is used in very high speed searching applications.
It is also known as content-addressable memory (CAM).

In the standard memory RAM user provides a memory address and it returns the data stored to that location.
While in a CAM user supplies a data word and it searches its entire memory to see whether that data word is stored anywhere in it.

On success it returns a list of one or more storage memory addresses where the data was found. It reduces the searching time of item since data item is identified by its content rather than its address.
CAMs are an outgrowth of RAM which is an integrated circuit that stores data temporarily.

One of the important component in the computer system is the computer storage. In this post we will focus on the storage hierarchy.

The wide variety of storage system can be organized in hierarchy according to speed and cost. The hierarchy levels are expensive but they are fast.

As we move down in a hierarchy the cost for bit generally decrease, where as the access time and storage capacity generally increases.

Semiconductor memory is a faster and chipper type of memory. The top 3 levels of memory in hierarchy is constructed using semiconductor memory.
In addition to having differing speed and cost the various storage system are either volatile or non-volatile.

Volatile storage lost its contents when the power supply for the device is off.
In the absence of expensive battery and generator backup system data must be return to non-volatile storage for permanent storage.

In the hierarchy shown in figure the storage system above the electronic disk is volatile where as those below are non-volatile.

During normal operation the electronic disk stores data in large D-RAM array, which is volatile. Many electronic disk devices contain a hidden magnetic hard disk and a battery for backup power.

If external power is interrupted the electronic disk controller copies the data from RAM to magnetic disk. When external power is restore, the controller copies the data back in to the RAM.

The design of computer memory system must balance all this factors.
It uses only as much expensive memory as necessary, which providing as much inexpensive, non-volatile memory as possible.

Cache can be installing to improve performance where a large access time is needed between two components.

After discussing Optimal algorithm for the page replacement policy, now its time to move on the next page replacement algorithm which is “LRU Algorithm”.
LRU stands for Least Recently Used Algorithm and it is the variation of optimal page replacement algorithm.

The FIFO page replacement algorithm uses arrival time for page replacement decision while optimal algorithm uses a time when a page is to be used that means future reference.

In least recently used algorithm when a page fault generates, we choose the page that was used very less in the past. In other words, optimal algorithm checks forward reference while LRU checks backward reference in the page reference string.

The page table entry records the time when the page was last referenced and it is modified every time when the page is referenced. It is basically works on the assumption that if a page is not used frequently in the past then chances are there that it might not be required in the future also.

Let’s see this algorithm at work.

Example:

Consider the same page reference string and find out total number of page faults using least recently used algorithm. Assume total number of free frames are 3.

Page Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

Initially all three frames are free so the first three page references for pages 7, 0 and 1 will result in page fault so first, second and third free frames will be allocated to page 7, 0, and page 1 respectively. At this point all the three frames are occupied and we have no more free frames available.

Reference for page 2 will generate page fault as page 2 is not available in the memory and since we don’t have any free frame available, swapping is required according to least recently used algorithm by finding the page that has used least in the recent past.

To look back in the past we have to check in the backward direction of in the page reference string starting from the current page reference i.e. page 2. We can figure out that page 1 and page 0 is recently used so page 7 will be selected as it is the least recently used page. Page 7 will be replaced by page 2.

Reference for the page 0 will generate no page fault as it is already available in the memory. Then after reference for page 3 will result in the page fault and by looking in the backward direction, we found the page as least recently used and replaced with page 3.

Similarly all the reference will be checked against the available pages in the memory and in the page reference string to find out least recently used page. You can see complete calculation in the above figure.

The LRU is quite good compare to FIFO but the major problem is how to implement LRU algorithm. The problem is to determine an order for the frames defined by the time of last use. It can be implemented by two ways.

Counters:

In this case, we add extra time field in the page table that will record time of the page access. It will modify the timer each time when a page is referenced.

Stack:

Another possible way to implement LRU is the stack. Whenever a page is referenced it is removed from the stack and put on the top. So the stack will always have most recently used page at the top and the least recently used (LRU) page at the bottom of the stack.