Saturday, April 19, 2014

FIFO page replacement technique

Here's a simulation of FIFO page replacement technique . . .

FifoPageReplacement.java


import java.util.Scanner;
public class FifoPageReplacement
{
public static void main(String[] args)
{
/*System.out.println("Enter the number of pages : ");
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
System.out.println("Enter the size Physical memory : ");
int P = sc.nextInt();
while(true)
{
System.out.println("Enter page referenced : ");
int p = sc.nextInt();
}*/
int pages[] = new int[100];
int inMem[] = {0,0,0};
int i=0,x,memPt=-1;
Scanner sc=new Scanner(System.in);
System.out.println("Enter Page String (0 for END)");
while(true)
{
x=sc.nextInt();
if(x==0) break;
pages[i++]=x;
}
for(x=0;x<i;x++)
{
if(pages[x]==inMem[0] || pages[x]==inMem[1] || pages[x] == inMem[2])
System.out.println("No Page Fault");
else
{
System.out.println("Page Fault for "+pages[x]+" Main Mem is ["+inMem[0]+inMem[1]+inMem[2]+"]");
memPt =(memPt+1)%3;
inMem[memPt]=pages[x];
}
}
}
}


Here's a simulation of Least Recently Used algorithm for page replacement . . .Tell me if any Changes required . ..

LRU.java

import java.util.Scanner;
public class LRU
{
public static void main(String[] args)
{
System.out.println("Enter the Number of Frames : ");
Scanner sc = new Scanner(System.in);
int F = sc.nextInt();
Page page[] = new Page[F];
int pages[] = new int[100]; // Array of String References
for(int i =0;i<F;i++)
{
page[i] = new Page(F);
}
int min=0,i=0;
System.out.println("Enter the Page no (0 for exit)");
//Entering the String References...
while(true)
{
int x = sc.nextInt();
if(x==0) break;
else
pages[i++] = x;
}
// Now Applying the LRU Strategy
boolean pageFaultOccured = true;
for(int j=0; j<i; j++)
{
for(int k=0;k<F;k++)
{
if(page[k].pno == pages[j]) // do we have requested page in memory?
{
pageFaultOccured = false;
page[k].set();
break;
}
}
if(pageFaultOccured == false)
{
pageFaultOccured = true;
System.out.println("NO PAGE FAULT");
for(int k=0;k<F && page[k].count!=F;k++)
{
page[k].dec();
}
}
else
{
System.out.println("PAGE FAULT");
// now find which page need to be replaced
// Find a page with minimum count value (least used)
for(int l=0; l<3; l++)
{
if(page[min].count>page[l].count)
min=l;

page[l].dec();
}
page[min].pno = pages[j];
System.out.println("Page entered at Frame : "+min);
page[min].set();
}
}
}
}
class Page
{
int pno;
int count;
int Frames;
Page(int Frames)
{
this.pno = 0;
this.count = 0;
this.Frames = Frames;
}
void dec()
{
if(this.count == 0)
this.count = 0;
else
this.count--;
}
void set()
{
this.count = this.Frames;
}

}


Thursday, April 17, 2014

Refined Readers Writers solution

Here's an improved version of Readers writers where i have used Semaphore class provide in java.util.concurrent package . . . Tell me if any changes required

ReadersWriters.java

import java.util.Scanner;
import java.util.concurrent.Semaphore;
public class ReadersWriters
{
public static void main(String[] args)
{
System.out.println("Enter the number of Readers : ");
Scanner sc = new Scanner(System.in);
int totalReaders = sc.nextInt();
Reader reader[] = new Reader[totalReaders];
System.out.println("Enter the number of Writers : ");
int totalWriters = sc.nextInt();
Writer writer[] = new Writer[totalWriters];
Database db = new Database(0);
Semaphore semDB = new Semaphore(1);
Semaphore semRC = new Semaphore(1);
for(int i=0;i<totalReaders;i++)
{
reader[i] = new Reader(i,db,semRC,semDB);
new Thread(reader[i]).start();
}
for(int i=0;i<totalWriters;i++)
{
writer[i] = new Writer(i,db,semDB);
new Thread(writer[i]).start();
}
}
}
class Reader implements Runnable
{
int rno;
Database db;
Semaphore semDB;
Semaphore semRC;
Reader(int rno, Database db, Semaphore semDB, Semaphore semRC)
{
this.rno = rno;
this.db = db;
this.semDB = semDB;
this.semRC = semRC;
}
public void run()
{
try{
semRC.acquire(); //acquire lock on reader Count
db.rc++; //Increment Reader Count
semRC.release(); // release the lock on reader count
if(db.rc == 1) // Check if only one reader
{
db.rc--;
semDB.acquire(); // Acquire lock on value of database or Enter the Critical section
System.out.println("Value read by the reader "+this.rno+" is :"+db.read());
Thread.sleep(2000);
semDB.release(); // Exit from the critical section
}
}
catch(InterruptedException ie)
{
ie.printStackTrace();
}
}
}
class Writer implements Runnable
{
int wno;
Database db;
Semaphore semDB;
Writer(int wno, Database db,Semaphore semDB)
{
this.wno = wno;
this.db = db;
this.semDB = semDB;
}
public void run()
{
try{
semDB.acquire(); // Entering the Critical Section
System.out.println("Writer "+this.wno+" is writing value "+(this.wno+10)+" to the Database...");
db.write(this.wno+10); // Writing the value to the Database
Thread.sleep(2000);
semDB.release(); // leaving the Critical Section
}
catch(InterruptedException ie)
{
ie.printStackTrace();
}
}
}
class Database
{
int value;
int rc;
Database(int value)
{
this.value = value;
this.rc = 0;
}
int read()
{
return this.value;
}
void write(int value)
{
this.value = value;
}

}
Here is a simulation of Optimal Page replacement algorithm in operating system . . .Suggestions to improve the simulation are welcome :-)

Optimal.java

import java.util.Scanner;
public class Optimal
{
public static void main(String[] args)
{
System.out.println("Enter the number of Frames");
Scanner sc = new Scanner(System.in);
int F = sc.nextInt();
Page page[] = new Page[F];
for(int i=0;i<F;i++)
{
page[i] = new Page();
}
int pages[] = new int[100];
System.out.println("Enter the String References : (0 for Exit)");
int size =0;
while(true)
{
int x = sc.nextInt();
if(x==0) 
break;
pages[size++] = x;
}
// Now we check for page Fault
for(int j=0;j<size;j++)
{
boolean pageFaultOccured=true;
for(int k=0;k<F;k++)
{
if(page[k].pno == pages[j])
{
// No Page Fault
pageFaultOccured=false;
break;
}
}
if(pageFaultOccured == false)
{
System.out.println("NO PAGE FAULT :-)");
}
else
{
System.out.println("PAGE FAULT :-(");
// Check for Empty Frames and insert if any
boolean pageInserted=false;
for(int k=0;k<F;k++)
{
pageInserted=false;
if(page[k].pno == 0)
{
page[k].pno=pages[j];
System.out.println("Page Entered at Frame : "+k);
pageInserted=true;
break;
}
}
if(pageInserted==false)
{
int lf=0;
for(int k=0;k<F;k++)
{
if(page[lf].nextReferred(pages,j,size) < page[k].nextReferred(pages,j,size))
lf = k;
}
page[lf].pno = pages[j];
System.out.println("Page Entered at Frame : "+lf);
}
}
}
}
}
class Page
{
int pno;
Page()
{
this.pno = 0;
}
int nextReferred(int arr[], int curr, int size)
{
int next=0;
for(int i=curr; i<size; i++)
{
if(this.pno == arr[i])
{
next = i;
break;
}
}
if(next==0)
next=size+1;
return next;
}
}

Monday, April 14, 2014

FCFS Scheduling Algorithm

Here is a very simple Simulation of First Come First Serve (FCFS) Scheduling algorithm in java . . . .Tell me if any changes are required... :-)


FCFS.java


import java.util.Scanner;
public class Fcfs
{
public static void main(String[] args)
{
int N;
Timer timer = new  Timer(0);
System.out.println("Enter the number of processes :");
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
Process process[] = new Process[N];
// Initialize all the processes
for(int i=0;i<N;i++)
{
System.out.println("Enter the Process no :");
int x = sc.nextInt();
System.out.println("Enter the Burst for process : "+x+" :");
int newburst = sc.nextInt();
process[i] = new Process(x,timer,newburst);
}
// Schedule the processes
for(int i=0; i<N; i++)
{
process[i].execute();
}
// Now displaying the Statistics
System.out.println("\n*************************************************\n");
System.out.println("--Process--Waiting Time--Turnaround Time--");
for(int i=0;i<N;i++)
{
System.out.println("  "+process[i].pno+"              "+process[i].waitingTime+"            "+process[i].turnaroundTime+"  ");
}
System.out.println("\n*************************************************\n");
}
}
class Process
{
int pno;
int burst;
int submissionTime;
int completionTime;
int waitingTime;
int turnaroundTime;
Timer timer;
Process(int pno, Timer timer,int burst)
{
this.pno = pno;
this.timer = timer;
this.burst = burst;
}
void execute()
{
this.submissionTime = timer.time;
for(int i=0;i<this.burst;i++)
{
timer.tick();
}
this.completionTime = timer.time;
System.out.println("Process "+this.pno+" is executing and finishing at : "+timer.time);
this.turnaroundTime = this.completionTime;
this.waitingTime = this.turnaroundTime - this.burst;
}
}
class Timer
{
int time;
Timer(int time)
{
this.time = time;
}
void tick()
{
this.time =this.time + 1;
}
}

Round Robin Scheduling

Here's a simulation of round robin process scheduling algorithm . . . . Tell me if it requires any changes . . . :-)

RoundRobin.java

import java.util.Scanner;
public class RoundRobin
{
public static void main(String[] args)
{
int N;
int newburst;
int totalburst = 0;
Timer timer = new Timer(0);;
final int timeSlice = 2;
System.out.println("Enter the Number of Processes :");
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
Process process[] = new Process[N];
// First Step : Intializing all the processes
for(int i=0;i<N;i++)
{
System.out.println("Enter the burst for Process : "+i+" :");
newburst = sc.nextInt();
totalburst = totalburst + newburst;
process[i] = new Process(i,timeSlice,newburst,timer);
}
//Second step : Scheduling the processes
int j=0;
while(timer.currentTime != totalburst) // Under construction
{
System.out.println("Time now : "+timer.currentTime);
process[j].execute();
j = (j+1)%N;
}
// Now Displaying all the Turnaround time values neatly:
System.out.println("\n*************************************************\n");
System.out.println("--Process--Waiting Time--Turnaround Time--");
for(int i=0;i<N;i++)
{
System.out.println("  "+process[i].pno+"              "+process[i].waiting+"            "+process[i].turnaround+"  ");
}
System.out.println("\n*************************************************\n");
}
}
class Process
{
int pno;
int burst;
int remburst;
int timeSlice;
int turnaround=0;
int waiting=0;
int submissionTime;
int completionTime;
Timer timer;
Process(int pno, int timeSlice, int burst, Timer timer)
{
this.pno = pno;
this.timeSlice = timeSlice;
this.burst = burst;
this.remburst = this.burst;
this.timer = timer;
}
void execute()
{
// set the Arrival time /Submission time
if(this.remburst == this.burst)
this.submissionTime = timer.currentTime;
if(this.remburst > 0)
{
int tempburst = this.remburst;
this.remburst = this.remburst - timeSlice;

if(this.remburst <= 0 )
{
for(int i=0;i<tempburst;i++)
{
timer.tick();
}
this.remburst = 0;
System.out.println("Process "+this.pno+" has Finished executing");
this.completionTime = timer.currentTime;
this.turnaround = this.completionTime - this.submissionTime;
this.waiting = this.turnaround - this.burst;
}
else
{
System.out.println("Process "+this.pno+" is executing");
System.out.println("Remaining Time for process "+this.pno+" is :"+this.remburst);
for(int i=0;i<timeSlice;i++)
{
timer.tick();
}
}
}
}
}
class Timer
{
int currentTime;
Timer(int time)
{
this.currentTime = time;
}
void tick()
{
this.currentTime = this.currentTime + 1;
}
}

Readers Writers

Here is an implementation of Readers Writers solution although it has a major bug . . . .Can you find it??? 

ReaderWriter.java

public class ReaderWriter
{
public static void main(String[] args)
{
DB database = new DB(1);
Mutex mut = new Mutex(1);
Reader reader[] = new Reader[5];
Writer writer[] = new Writer[5];
for(int i=0;i<5;i++)
{
writer[i] = new Writer(i,mut,database);
new Thread(writer[i]).start();
}
for(int i=0;i<5;i++)
{
reader[i] = new Reader(i,mut,database);
new Thread(reader[i]).start();
}
}
}
class Reader implements Runnable
{
int rno;
DB database;
Mutex mut;
Reader(int rno, Mutex mut, DB database)
{
this.rno = rno;
this.mut = mut;
this.database = database;
}
public void run()
{
try
{
mut.downMutex(); // Enter Critical Section
database.incRC();
if(database.rc == 1) // i.e if its the First Reader
{
database.downDB(); // Put a lock on DB
}
mut.upMutex();     // Leave Critical Section
//Thread.sleep(2000);
System.out.println("Value read by Reader "+this.rno+" is :"+database.db); // Access the DB value
mut.downMutex(); // Again Enter Critical Section
database.decRC();
if(database.rc == 0) //If the Reader is done 
{
database.upDB(); // release the Lock on DB
}
mut.upMutex(); // Leave Critical Section
}
catch(Exception e){e.printStackTrace();}
}
}
class Writer implements Runnable
{
int wno;
int value;
DB database;
Mutex mut;
Writer(int wno, Mutex mut, DB database)
{
this.wno = wno;
this.mut = mut;
this.database = database;
}
public void run()
{
try
{
this.value = this.wno + 10 ;  // Creating some data
database.downDB();    // Trying to put lock in Database
database.db = this.value;     // Writing to the Database
System.out.println("Writer "+this.wno+" is writing "+this.value+" to Database");
database.upDB();  // Releasing the lock
}
catch(Exception e){e.printStackTrace();}
}
}

class Mutex
{
int mutex;
Mutex(int mutex)
{
this.mutex = mutex;
}
void upMutex()
{
this.mutex = 1;
}
void downMutex()
{
while(this.mutex==0);
this.mutex = 0;
}
}
class DB
{
int dbLock;
int db;
int rc = 0; // Reader Count
DB(int dbLock)
{
this.dbLock = dbLock;
}
void upDB()
{
this.dbLock = 1;
}
void downDB()
{
while(this.dbLock == 0);
this.dbLock = 0;
}
void incRC()
{
this.rc = this.rc + 1;
}
void decRC()
{
this.rc = this.rc - 1;
}
}

Sunday, April 13, 2014

Dining Philosopher Solution

From now i'll be posting solutions to some of the programming assignments in my blog :-)

Implementation of Dining Philosopher problem's solution in java :

import java.util.*;
public class DiningPhilosopher
{
public static void main(String[] args)
{
Mutex mut = new Mutex(1);
Chopstick ch[] = new Chopstick[5];
for(int i=0;i<5;i++)
{
ch[i] = new Chopstick();
ch[i].cno = i;
ch[i].in_use = false;
}
// Creating The Philosophers
Philosopher ph[] = new Philosopher[5];

for(int i=0;i<5;i++)
{
ph[i] = new Philosopher(i,ch[i],ch[(i+1)%5],mut);
new Thread(ph[i]).start();
}
}
}
class Philosopher implements Runnable // The "processes" among which the resources are shared
{
Philosopher(int pno, Chopstick left, Chopstick right, Mutex mut)
{
this.pno = pno;
this.left = left;
this.right = right;
this.mut = mut;
}
Mutex mut;
Chopstick left;
Chopstick right;
int state=2; // THINKING by default 1: HUNGRY 2:THINKING 3:EATING
int sem=1;
int pno;
void think()
{
System.out.println("Philosopher "+this.pno+" is Thinking");
}
void takeChopsticks()
{
// turn mutex down ; cannot enter cs if mutex already down ; gets blocked :-P
//down(mutex); // Enter Critical section
mut.downMutex(); // Entering CS
this.state=1;  // State is Hungry
System.out.println("Philosopher "+this.pno+" is HUNGRY");
this.test();   // Trying to acquire two Chopsticks
mut.upMutex();     // Exit Critical Section
semDown(); // Block Philosopher if he did'nt get Chopsticks
}
void eat()
{
System.out.println("Philosopher "+this.pno+" is Eating");
}
void putChopsticks()
{
mut.downMutex(); // Enter Critical section
this.state=2;  // State is thinking
left.in_use = false; // Pick up left chopstick
right.in_use = false; // pick up right chopstick
mut.upMutex(); //up(mutex);   // Exit Critical Section
}
void test()
{
if(left.in_use==false && right.in_use==false && this.state==1) // If Both left and right chopsticks are free //and i am hungry
{
this.state=3; // 3: means Eating
left.in_use = true;
right.in_use = true;
semUp();
}
}
public void run()
{
try{
this.think();
// Thread.sleep(1000);
this.takeChopsticks();
// Thread.sleep(1000);
this.eat();
// Thread.sleep(1000);
this.putChopsticks();
}
catch(Exception e)
{
e.printStackTrace();
}
}
void semUp()
{
this.sem = 1;
}
void semDown()
{
while(this.sem == 0); // blocking condition
this.sem=0;
}
}
class Chopstick // The resources needed to be shared
{
int cno;
boolean in_use; // true for in_use & false for free
void setuse(boolean in_use)
{
this.in_use = in_use;
}
}
class Mutex
{
int mutex;
Mutex(int mutex)
{
this.mutex = mutex;
}
void upMutex()
{
this.mutex = 1;
}
void downMutex()
{
while(this.mutex==0);
this.mutex = 0;

}
}