Question

java  Operating System Scheduler

Two scheduling strategies for an operating system scheduler are first come first serve (FCFS) and fixed priority pre-emptive scheduling (FPPS). Since queues operate on a first come first serve basis, FCFS is implemented using a queue. Similarly, FPPS is implemented using a priority queue.

The operating system scheduler simulation is already provided for you. To use it you simply need to modify the main method to run the simulator using either the LinkedListQueue or the PriorityQueue.

Run the simulator a few times with each type of queue. Answer the following four questions about your experiments in a plain text file called scheduler.txt.

1. What are differences in how the jobs are managed between FCFS and FPPS?

2. What is are the advantages of FCFS over FPPS and vice versa?

3. What potential problems do you see happening if you were using an operating system with an FCFS scheduler?

4. What potential problems do you see happening if you were using an operating system with an FPPS scheduler?

public class Simulation
{
private Queue scheduler;
  
private static final int DEFAULT_TIME = 100;
private static final int NUMBER_OF_JOBS = 10;
private static final int PRIORITY_LEVELS = 3;
private static final int MAX_DURATION = 1000;
  
/**
* Creates an Operating System Simulator to test a given scheduler.
*
* @param scheduler The scheduler to test. The scheduler should use the Queue
* interface.
*/
public Simulation(Queue scheduler)
{
this.scheduler = scheduler;
}
  
/**
* Runs the simulator by creating a certain number of Jobs and then running
* until all the Jobs are completed. It outputs a progress report at each time
* it retrieves a new Job from the scheduler and runs it. By default it runs
* each Job for 100 milliseconds at a time, however, if a Job finishes before
* that time has elapsed the remaining time is given to the next Job.
*/
public void run()
{
if (scheduler == null)
{
return;
}
  
Random generator = new Random();
System.out.println("Creating jobs...");
for (int i = 0; i < NUMBER_OF_JOBS; i ++)
{
Job temp = new Job(generator.nextInt(PRIORITY_LEVELS),
generator.nextInt(MAX_DURATION));
scheduler.enqueue(temp);
System.out.println(temp);
}
  
System.out.println();
System.out.println("Running jobs...");
int time = DEFAULT_TIME;
while (!scheduler.isEmpty())
{
Job active = scheduler.dequeue();
  
System.out.println("Running Job " + active.getId() + " for " + time + " milliseconds..");
if (active.getDuration() >= time)
{
active.run(time);
time = DEFAULT_TIME;
}
else
{
time = DEFAULT_TIME + time - active.getDuration();
active.run(active.getDuration());
}
System.out.print("..." + active);   
  
if (active.getDuration() > 0)
{
scheduler.enqueue(active);
System.out.println();
}
else
{
System.out.println(" COMPLETE!");
}
}
}
  
/**
* The main method creates the scheduler and the operating system simulator
* on which to test it. It also runs the simulator. Modify the main method
* in order to change the scheduler and compare the results.
*/
public static void main(String[] args)
{
Queue jobs = null; // Replace null with the queue you want to test
Simulation simulator = new Simulation(jobs);
simulator.run();
}
}

class Job

public class Job
{
/**
* This constant indicates that an application is the owner of the job.
*/
public static final int APPLICATION = 0;
  
/**
* This constant indicates that the user is the owner of the job.
*/
public static final int USER = 1;
  
/**
* This constant indicates that the operating system is the owner of the job.
*/
public static final int SYSTEM = 2;
  
private int owner;
private int duration;
private int id;
  
private static int currentId = 0;
  
/**
* The constructor for Job initializes its three instance variables. It gets
* the owner and the duration (in milliseconds) from the user and assigns
* a unique id to the Job.
*
* @param owner Either 0, 1 or 2 inidicating who created the Job.
* @param duration The number of milliseconds the Job must run until completion.
*/
public Job(int owner, int duration)
{
this.owner = owner;
this.duration = duration;
this.id = currentId ++;
}
  
/**
* Gets the unique id of the Job.
*
* @return An integer id unique to this Job.
*/
public int getId()
{
return this.id;
}
  
/**
* Gets the owner of the Job.
*
* @return 0, 1 or 2 indicating the owner, an application, the user or
* the system respectively, of the Job.
*/
public int getOwner()
{
return this.owner;
}
  
/**
* Gets the remaining duration, in milliseconds, of the Job.
*
* @return An integer containing the remaining duration of the Job.
*/
public int getDuration()
{
return this.duration;
}
  
/**
* Runs the job for a certain number of milliseconds.
*
* @param time An integer containing the number of milliseconds that the
* job should be run.
*/
public void run(int time)
{
this.duration -= time;
  
if (this.duration < 0)
{
this.duration = 0;
}
  
try
{
if (time > duration)
{
Thread.sleep(time);
}
else
{
Thread.sleep(duration);
}
}
catch (Exception e)
{
// Do nothing
}
}
  
/**
* Determines if two Jobs are equal by comparing their unique ids.
*
* @param other The Job to compare with this Job.
* @return True if the two Jobs have the same id, false otherwise.
*/
public boolean equals(Job other)
{
return this.getId() == other.getId();
}
  
/**
* Produces a String representation of the Job.
*
* @return A String representation of the job.
*/
public String toString()
{
StringBuffer result = new StringBuffer();
  
result.append("Job ");
result.append(getId());
  
result.append(" owned by ");
switch(getOwner())
{
case SYSTEM: result.append("the system "); break;
case USER: result.append("the user "); break;
case APPLICATION: result.append("an application "); break;
default: result.append(" ERROR "); break;
}
  
result.append("has ");
result.append(duration);
result.append(" microseconds remaining;");
  
return result.toString();
}
}

Answer 1

1. In FCFS jobs are put into normal QUEUE data structure which itself follows FCFS policy. Irespective of the jobs' priority in the queue, job that is oldest in the queue will be executed.
But in FPPS jobs are put into a PRIORITY QUEUE data structure which dequeues an item based on some predefined priority. In this case job that have highest priority in the queue will be executed first irespective of its age in the queue.

2. Advantages of FCFS:
   a. No starvation
   b. Simple data structure

Advantages of FPPS:
   a. Can reduce avg waiting time
   b. Known for improving throughput
   c. System task and other urgent jobs can be easily handled

3. FCFS have certain problem:
   a. Shorter job or Urgent job have to wait quite long in the queue
   b. Can increase the avg waiting time if there are more shorter job than longer jobs

4. FPPS have certain problem:
   a. Complex data structure
   b. Can cause starvation of lower priority jobs
   c. Job dispatcher may consume little more time since dequeue operation of Priority queue is not always of complexity O(1)