Generic Version of Priority Queue and Priority Based Process Scheduler Simulation

• Download source files - 25.75 KB
• Download demo project - 47.79 KB

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