Click here to Skip to main content
Click here to Skip to main content
Go to top

Generic Version of Priority Queue and Priority Based Process Scheduler Simulation

, 25 Jan 2007
Rate this:
Please Sign up or sign in to vote.
A priority based process scheduler is simulated using a priority queue
Sample image

Introduction

The priority scheduler is a short-term CPU scheduler which schedules processes to the CPU according to their priorities. Here, I've implemented a simulation of a priority scheduler using a priority queue.

The .NET Framework supports many built-in data structures, but it lacks a ready-made priority-queue both under System.Collections and System.Collections.Generic namespaces. Priority Queue has to be implemented using the Heap data structure. While searching The Code Project, I found two articles on priority queue: one written by Leslie Sanford[^] and another written by BenDi[^]. But both of them do not support generics. That's why I have implemented it on my own and tried to make it compatible with industry standards as far as it was possible for me.

Background

There is a short background behind this article. As one of my MTech assignments in college, I had to design a priority scheduler simulator. The scheduler had a peculiar property. After the submission of processes, the scheduler acts on FCFS (First Come First Serve) basis. On the completion of one round, the scheduler acts on Priority basis. The priority and execution time of each process should be proportional to nCi, where n is the total number of processes and i is the PID. The scheduler is a Round Robin scheduler with a customizable time slice and the scheduler has a customizable context-switch time too. The aim of the assignment was to investigate the characteristics of this hypothetical scheduler using different Round Robin time slice and context-switch time. It is very interesting to see that the scheduler finally acts as an FCFS scheduler with several context-switching overheads.

After the completion of the assignment, I decided to submit the generic version of the priority queue under GPL as it might come in handy for others. As the demo of this priority queue class, I've submitted the scheduler too.

Using the Code

The priority queue class is developed in the guidelines of System.Collections.Generic namespaces implementing the interface ICollection and IEnumerable along with their Generic versions. The priority queue places the element with highest priority at the top, i.e. the element with highest priority will be popped first. The priority queue supports the following operations:

  • Enqueue(): It will add an object along with the key in the queue. The object is entered through the tail of the queue.
  • Dequeue(): It will remove an object along with its key from the top of the queue.
  • Peek(): Get the object on the top without removing it.
  • ToArray(): Insert the sorted objects in a new array.

Apart from the above methods, it supports others like...

  • Clear()
  • Contains()
  • CopyTo()
  • Equals()
  • GetEnumerator()
  • GetHashCode()
  • GetType()
  • ToString()
  • TrimExcess()

... and properties like:

  • Count
  • Comparer

The code is well documented so I am not repeating it here.

Here, I give some examples on how to use basic operations like Enqueue() and Dequeue() using the code I used in the scheduler.

// a generic priority queue is initialized
processQueue = new PriorityQueue<int,MyProcess>(maxNumber);
           
// enqueue the process into the queue with the priority
processQueue.Enqueue(myProc, myProc.Priority);
        
// dequeue the top elements  
MyProcess proc = processQueue.Dequeue().Value;

It is worth noting that MyProcess is a structure holding the information of the hypothetical process and it is as follows:

internal struct MyProcess
{
    internal int PID;
    internal int Priority;
    internal int ExecutionTime;   
}

Points of Interest

As I have stated earlier, this Round Robin process scheduler acts on the basis of process priority and ultimately becomes an FCFS process scheduler with several context-switch overheads.

History

  • 26.01.2007: Article submitted

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Anindya Chatterjee
Web Developer Tata Consultancy Services
India India
I am working as a J2EE/Weblogic web developer at Tata Consultancy Services, India.
Follow on   Twitter

You may also be interested in...

Comments and Discussions

 
GeneralMy vote of 5 PinmemberMooseDePaques19-Oct-11 12:37 
GeneralThanks Pinmembersamhainal8-Feb-08 12:16 
GeneralC5 PinprotectorMarc Clifton25-Jan-07 10:30 
GeneralRe: C5 PinmemberNicolae Mogoreanu26-Mar-07 11:25 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web01 | 2.8.140916.1 | Last Updated 25 Jan 2007
Article Copyright 2007 by Anindya Chatterjee
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid