FINAL YEAR PROJECT
On
DESIGNING A SIMULATOR TO IMPLEMENT A JOB SCHEDULER BASED ON DIFFERENT POPULAR CPU SCHEDULING ALGORITHMS

Submitted as partial fulfillment for the award of
BACHELOR OF TECHNOLOGY
Session 2014-15
In
Computer Science & Engineering
Under the guidance of
Mr.MrinmoySen
By
AnanyaDas(11/CS/15, ananyadas092@gmail.com, +919681851782)
AnshumanMahanty(11/CS/23, anshumanmahanty1@gmail.com, +917501169824)
SayaniBanerjee(11/CS/93, sayanibanerjee.1@gmail.com, +919046422003)

HALDIA INSTITUTE OF TECHNOLOGY, HALDIA

CERTIFICATE

This is to certify that the final year project (CS792) on ‘Designing a Simulator implementing job scheduler based on different popular CPU scheduling algorithms’ has been completed and submitted successfully by the project members Ananya Das (11/CS/15), Anshuman Mahanty (11/CS/23) and Sayani Banerjee (11/CS/93).

------------------------- -------------------------------- ---------------------------
Mr. Tarun Kumar Ghosh Mr. Sourav Mandal, Mr. Mrinmoy Sen
Head of the Department, Convenor, Asst. Prof., Project Mentor, Asst. Prof.,
Computer Science & Engg. Project Evaluation Committee Department of CSE

ACKNOWLEDGEMENTS

We use this opportunity to express our gratitude to everyone who has supported us through the ongoing course of this final year project. The project owes its success not just to the efforts we put in but also to the aspiring guidance, invaluably constructive criticism and the holistic training provided to us by our project mentor, Mr. Mrinmoy Sen. It is our radiant sentiment to place on record our best regards and deepest thankfulness for allowing us the opportunity to work with him and gain from his knowledge.
It would also be of great pleasure to us to thank the other teachers and instructors of our department whose valuable suggestions have benefited us and made our project richer.

Project Members:
Ananya Das
Anshuman Mahanty
Sayani Banerjee

TABLE OF CONTENTS

LITERATURE SURVEY……………………………………….…. .………..………1
REVIEW OF DESIGN……………………………….…………...…………………..10
IMPLEMENTATION OVERVIEW………………………………………………….13
IMPLEMENTATION OF EXISTING ALGORITHMS……………………………..17
OBJECTIVE AND PLANNING FOR NEXT SEMESTER…………………….........26
ANALYSIS OF THE WORK…………………………………………………….......29
REFERENCES/BIBLIOGRAPHY…………………………………………………….32

PROBLEM DISCUSSION

1. Existing System
The understanding of the working of CPU scheduling algorithms is still done largely with the help of manual systems. In the past, most jobs were run as batch jobs, and it didn't matter very much how quickly they ran. Often, how much the CPU cost you depended upon what priority you put on the job -- if your job got better service, you paid more. CPU scheduling is more of an art than a science. It is the process by which an Operating System decides which programs get to use the CPU. With the advent and advancement of time-sharing systems, job scheduling is now of paramount importance. There are various algorithms that govern the scheduling process and the CPU has to choose the most feasible of them in order to enhance it’s throughput and effectiveness. 2. Need for a Simulator
On the analysis of the manual system, the following problems were identified: * Erroneous Input and Output
In the existing system, all tasks are fully dependent on human research and analysis. As a result there is a possibility of error. Input given by the user may not be absolutely foolproof and may be erroneous. A wrong input thereon leads to a corrupt output too. * Reduction in complexity
In the manual system, estimation of performance is evaluated by calculation of scheduling parameters of different algorithms such as waiting time ,turn-around time by making Gantt chart. However simulated representation of CPU scheduling algorithms gives a precise and an accurate result and signifies the best algorithm for a particular task. A simulator thus has a clear advantage over the manual calculations as it involves less complexity in order to know the most feasible scheduling algorithm that the CPU should follow. 3. Reduction in time
Manual system takes a long span of time to understand working of CPU scheduling algorithms. Apart from that manual system does not specifies overall working of algorithms but in a simulator software, the working of different CPU scheduling algorithms can be understood completely and implementation of algorithm can be done in small span of time. PROJECT OBJECTIVE AND SCOPE
Objective:
Our project presents a simulator based on Java to convey the concepts of various scheduling algorithms for a single CPU. The simulator is unique in a number of respects. First, it uses a more realistic process model that can be configured easily by the user. Second, it depicts each process in terms of what the process is currently doing against time. Using this representation, it becomes much easier to understand what is going on inside the system and why a different set of processes is a candidate for the allocation of the CPU at different time. A third unique feature of the simulator is that it allows the user to test and increase his understanding of the concepts studied by making his own scheduling decisions. Thus, our objective is to design the simulator in a manner that makes the understanding, comparison and feasibility study of CPU scheduling algorithms more effective and comprehensible to even the most layman of users.

Scope:
Scheduling topic discussions and related project area research are very integral design topics, when talking about real-time applications. The CPU scheduling algorithm that is used in the real-time system weighs heavily on the maximization of utilization and throughput, and on the minimization of waiting and turnaround times. The algorithms that are currently being used have been present for quite a long period of time. New algorithms have been recently developed and implemented. For that matter, it is quite an interesting research topic to analyze the progress that these algorithms have permitted the real-time computing world to enjoy.
This research project’s goals are to analyze independent CPU scheduling algorithms, to compare them, to extrapolate the results to include hybrid models, as well as innovative CPU scheduling design techniques, and to conclude by attempting to expose the algorithms better-suited for certain applications.
Feasibility Study:
The aforementioned objective gives a brief and precise description of the properties that this project should possess. This gives rise to the pertinent question of feasibility. The amount of effort spent in terms of man-hour, and the sheer complexity of the implementation of any project , make a feasibility analysis utterly necessary. The feasibility study has to be conducted given due importance to numerous parameters, which are essential in determining the practicality of the project. Our project is supposed to be technically, economically and operationally feasible. Technical feasibility is concerned with specifying equipment and software that will successfully satisfy the user requirement. The technical needs of the system may vary considerably, but might include: * The facility to produce output in a given time. * Response time under certain conditions. * Ability to process a certain volume of transaction at a particular speed.
In examining technical feasibility, configuration of the system is given more importance than the actual make-up of the hardware.
As the simulator is being built using Java as a platform, apart from the accuracy and the reliability that it provides, there is also a lot of scope for further upgradation of versions.
The project should also work under a bare minimum of resources in order for it to be economically feasible and the interface and the actual working of the software should be user-friendly for it to be considered operationally feasible.

LITERATURE SURVEY
The job scheduler manages the allocation of processes from the job queue to the ready queue, and controls unattended background program execution (commonly called batch processing).A process upon creation is present in the job queue from where it expects to be delivered to the ready queue for it to get serviced by the processor. It is said to be in running state if it is currently using the CPU or in the waiting stage if it is present in the ready queue and waiting for another process to finish. A process is said to be in the ready state if it could use the CPU if it were available. When its I/O request completes, an I/O interrupt is generated and then that process will change from waiting state to ready state. All ready processes are kept on a ready queue. All blocked processes are placed on an I/O queue for the requested I/O device. The scheduler uses a scheduling algorithm to decide which process from the ready queue to run when and for how long. There are various scheduling algorithms. The simulator uses the algorithms as follows:

Basic features expected of job scheduler software include: 1. Interfaces which help to define workflows and/or job dependencies. 2. Automatic submission of executions 3. Interfaces to monitor the executions. 4. Priorities and/or queues to control the execution order of unrelated jobs.

Prerequisites:
The CPU scheduler, which is part of the operating system of computer, manages the allocation of the CPU among processes. A process is said to be running in the running state if it is currently using the CPU. A process is said to be ready in the ready state if it could use the CPU if it were available. When its I/O request completes, an I/O interrupt is generated and then that process will change from waiting state to ready state. For a single CPU system, only one process may be running at a time, but several processes may be ready and several may be blocked. All ready processes are kept on a ready queue. All blocked processes are placed on an I/O queue for the requested I/O device. The scheduler uses a scheduling algorithm to decide which process from the ready queue to run when and for how long. There are various scheduling algorithms. The simulator uses the algorithms as follows:

SCHEDULING ALGORITHMS: FIRST COME FIRST SERVE (FCFS) SCHEDULING: * By far the simplest CPU-scheduling algorithm is the first-come, first-served (FCFS) scheduling algorithm. With this algorithm, processes are assigned the CPU in the order they request it. * Basically, there is a single queue of ready processes. Relative importance of jobs measured only by arrival time (poor choice). * The implementation of the FCFS policy is easily managed with a FIFO queue. When a process enters the ready queue, its PCB is linked onto the tail of the queue. * The average waiting time under the FCFS policy, however, is often quite long.

ROUND ROBIN (RR) SCHEDULING: * The round-robin (RR) scheduling algorithm is designed especially for time-sharing systems. It is similar to FCFS scheduling, but pre-emption is added to switch between processes. * A small unit of time, called a time quantum or time slice, is defined. A time quantum is generally from 10 to 100 milliseconds. The ready queue is treated as a circular queue. * To implement RR scheduling, * We keep the ready queue as a FIFO queue of processes. * New processes are added to the tail of the ready queue. * The CPU scheduler picks the first process from the ready queue, sets a timer to interrupt after 1 time quantum, and dispatches the process. * The process may have a CPU burst of less than 1 time quantum. * In this case, the process itself will release the CPU voluntarily. * The scheduler will then proceed to the next process in the ready queue. * Otherwise, if the CPU burst of the currently running process is longer than 1 time quantum, * The timer will go off and will cause an interrupt to the OS. * A context switch will be executed, and the process will be put at the tail of the ready queue. * The CPU scheduler will then select the next process in the ready queue. * The average waiting time under the RR policy is often long. | | PRIORITY SCHEDULING: * The SJF algorithm is a special case of the general priority scheduling algorithm. A priority is associated with each process, and the CPU is allocated to the process with the highest priority. Equal-priority processes are scheduled in FCFS order. * An SJF algorithm is simply a priority algorithm where the priority (p) is the inverse of the (predicted) next CPU burst. The larger the CPU burst, the lower the priority, and vice versa. * Priorities are generally indicated by some fixed range of numbers, such as 0 to 7 or 0 to 4095. However, there is no general agreement on whether 0 is the highest or lowest priority. Some systems use low numbers to represent low priority; others use low numbers for high priority. We use as low numbers represent high priority. * Priorities can be defined internally or externally. * Internally defined priorities use some measurable quantity or quantities to compute the priority of a process. For example, time limits, memory requirements, the number of open files, and the ratio of average I/O burst to average CPU burst have been used in computing priorities. * External priorities are set by criteria outside the OS, such as the importance of the process, the type and amount of funds being paid for computer use, the department sponsoring the work, and other, often political, factors. * Priority scheduling can be either pre-emptive or nonpreemptive. When a process arrives at the ready queue, its priority is compared with the priority of the currently running process. * A pre-emptive priority scheduling algorithm will preempt the CPU if the priority of the newly arrived process is higher than the priority of the currently running process. * A nonpreemptive priority scheduling algorithm will simply put the new process at the head of the ready queue.
Evaluation Characteristics: Characteristics | Description | | | Throughput | Number of processes completed per unit time | Waiting time | Amount of time spent ready to run but not running | Response time | Amount of time between submission of request and first response to the request | Scheduler efficiency | Minimize the overhead | | |

Existing Domain:
Prior to this, there already has been a lot of work done towards achieving a foolproof simulation of CPU scheduling algorithms. Computer researchers and scientists are reliant on a good simulator in order to work out the best possible and the most optimal choice for an algorithm in a given situation. Knowledge about job scheduling algorithms, though very abundant overall, is still in a nascent stage and thus this branch of study offers a great deal of scope for further research and enhancement. Simulation softwares for this purpose are generally meant for users who desire to find out what makes a CPU choose one algorithm over the other when a host of processes is to be scheduled by it.

Required Technology: 1. Java (JDK 1.7.0), front-end tool 2. Java Virtual Machine or JVM, back-end tool 3. Operating System, Windows or Unix 4. CPU minimum 1GB RAM

SOFTWARE DEVELOPMENT LIFE CYCLE

A. PLANNING * Conduct preliminary investigation/feasibility study * Determine scope of problem/project * Identify constraints to systems development * Identify resources required * Set timelines, schedules, checkpoints, etc. * Set project deliverable goals * Develop high level specifications

B. ANALYSIS
Key Activities: * Gather business requirements * Build trust and rapport with users * Document the existing system * Develop preliminary data and process models * Verify requirements and current system/procedures with users
Key Outputs: * Systems Requirements Documents * Detailed Project Scope and Deliverables Reports * Data and Process Models C. DESIGN
Key Activities: * Determine technical systems configuration * Determine data structure * Determine make or buy decision * Prototype * Set systems conversion plan
Key Outputs: * Systems architecture report * Systems conversion chart and plan * Psuedocode * Data structure diagrams * Prototypes

D. CONSTRUCTION
Key Activities (if create in-house): * Create the physical system * Test the system * Obtain hardware * Create documentation and training materials
Key Outputs: * Tested programs * Databases * Completed system

E. TESTING
UNIT TEST * Testing of individual units or modules
INTEGRATIVE SYSTEMS TESTING * Testing the entire system as one
DEBUGGING
* Correcting systems problems

F. DOCUMENTATION
Two basic types of documentation
Systems Documentation * Information needed for the on-going maintenance and operation of the computer system * Structured for the technical systems professional * Examples: technical diagrams, flowcharts, database management structures, etc.
User documentation * Easy to read (step by step) instructions for using the application system * Structured for non-systems professional

G. IMPLEMENTATION
Key Activities: * Conduct cutover * Train users/customers * Manage change * Obtain user sign off
Key Outputs: * Satisfied users/customers * Modification requests

H. USE/MAINTENANCE
Key Activities: * Conduct on-going systems maintenance Key Outputs: * Change requests * New systems proposals/requests DETAILED SRS (SOFTWARE REQUIREMENT SPECIFICATIONS)
Introduction
* Purpose
The purpose of this project is to build an application engine that simulates various CPU scheduling algorithms and compares them with each other based on different parameters. The application should be modular enough to allow the 'plug-in' of alternative scheduling algorithms.

* Document Conventions
IEEE SRS Template has been used while writing this documentation. * Intended Audience and Reading Suggestions
This document is intended to serve as a reference manual for developers, project managers, users, testers, and documentation writers. It gives a rough impression of how the software should be used and it’s other attributes such as interface and operating environment. * Product Scope
The simulator can be used by students, researchers and operating system developers alike to know about the various nuances of scheduling algorithms through an user-friendly interface.
Overall Description * Product Perspective
The simulator engine should be invoked from a command line with passed parameters or with an input dialog box to receive parameters. The parameters passed to the program will be the number of the processes (a pre-assigned menu of processes - see below), the order to initialize and start them, and the number of total time ticks to run the simulation. As the program runs the user should be able to press certain keys to cause interrupts to occur. Processes will have programmed system requests, such as for an I/O service that will cause the scheduler to put them in the blocked state and in the waiting queue for that service. A random number generator can be used to determine the time that any service takes to complete and generate an interrupt.

* Product Functions
The simulation run will print a string of text messages indicating which process is running, when it generates a service request, when an interrupt occurs, when a context switch occurs, and the state of each process on each context switch. * Operating Environment
The simulator should work in any Operating System with bare minimum hardware requirements. * Design and Implementation Constraints * Programming standard: Object-oriented (Java) * The Operating System used should be a time-sharing one. * Shared memory slots and an autonomous system timer.

User Documentation * This documentation follows the IEEE Standard SRS template format. The manual provides a rough sketch of the software to be built and mentions the features that it should incorporate. * Assumptions and Dependencies * The following assumptions were undertaken during the implementation phase. These assumptions not only simplified the design, but also hid the details that come with a real-time operating system design. 1. There are only two types of processes (in terms of resource usage): CPU-bound and I/O-bound processes. CPU-bound processes perform lots of computation and request a small amount of I/O transfers, while I/O-bound processes request a major amount of I/O transfers, while processing the I/O results in short CPU bursts.

2. It is assumed that there are also only two types of resources: preemptible and non-preemptible resources. Preemptible resources are obtained by the process, which use the resource and return it back to the resource pool (e.g. processor or I/O channel), while non-preemptible resources, once obtained by the process, are not returned until the latter is done with its use (e.g. file space).

3. The simulated processes are aperiodic tasks, i.e. they have deadlines (constraints) by which the task must finish or start, or they may have constraints on both start and finish time. Periodic tasks were considered at the beginning of the project implementation, but after further review, the design was switched to better simulate a real-time environment where tasks are mostly aperiodic ones.

4. The simulated processes are assigned priorities by the designer. These priorities are effectively not used during the FCFS and RR simulations, but are utilized in the STCF simulations. Basically, the priorities are assigned with the inverse remaining time theory in mind.

Also, the following constraints were placed on the system:
• Only 10 processes can enter the system at the STS level;
• A process can block at most 10 times;
• A queue can hold at most 10 PCB’s;
• The highest priority level is 10;
• The maximum amount of time a process can be in the system for is 255 time ticks.

Requirements

The simulation should include the following objects: * 3.1 Process
Create a process class that can be extended to simulate different kinds of processes. You should have a user interface process (e.g. one waiting for keyboard input), a calculating process (possible background job), and two processes that require inter-process communications, such as a producer-consumer pair. Each process should be an endless loop that doesn't really do anything (except the producer and consumer) but generates a service request, either for I/O or for communication (e.g. semaphore). The I/O requests don't really need to do any I/O, they just activate an I/O module that then generates a random time to assert an interrupt.

Each process should have an associated process control block with a minimum amount of information for the scheduler to manage with. Process instances should be generated dynamically at start up.

3.2 CPU

The CPU object is the main loop that "runs" the running process. This is basically a loop that counts a number of steps (machine instructions) modulo some number between 1,000 and 10,000. That is the counter loops back to zero at some point. Each process should have a different (perhaps randomly generated at startup) number within the range that it passes to the CPU to indicate the count at which a system call is made. Different processes should have different points in their count where the calls are made. The count represents the execution address so that if an interrupt occurs, that value is stored in the PCB while the interrupt is serviced.

The CPU doesn't actually do much during an interrupt service. Generate a small random time interval to expire before restoring the interrupted process. You could even do this with a busy-waiting loop on a random number between 100 and 500 or something like that.

3.3 I/O Devices

Create two I/O devices that will get activated by a system call from one of the processes and then, at some random interval later, generate an interrupt when the service is complete. It doesn't matter what they do but they need to generate an explanation string when they are activated and when they generate the interrupt. You can also have a keyboard I/O that generates an interrupt whenever the user types a key.

3.4 System Timer

The system timer is an autonomous device that has a standard time delay set after which it generates an interrupt. Since the timer has the highest priority of any interrupt you will have to make provisions for dealing with multi-level interrupts (just in case). For purposes of this simulation we can set all process quanta to the same value and use a simple sleep for the timer.

3.5 Shared Memory

Make provisions for at least several shared memory slots, especially for the semaphores used in the producer-consumer problem. These semaphores can be global variables already initialized at start up and known to the processes in advance.

3.6 Scheduler

The scheduler will be called each time the CPU receives an interrupt or a process makes a system call. It will need to determine what happened to activate it and then do whatever context switching is needed to enforce the round-robin policy. In the simple version, all processes have the same priority. The scheduler must also manage the various queues (ready and blocked for semaphores/I/O).

RESEARCH METHODOLOGY
The theoretical aspects that need to be known beforehand while proceeding with this project have been thoroughly researched with the help of various textbooks and research manuals. The rest of the research has been carried out through online resources. The focus has been on understanding clearly the different features that each scheduling algorithm entails.
Once finished, the application will, in all likelihood, be a source of great help to people interested in the domain of operating systems and job scheduling. To carry out the required functionalities of the simulator, an object-oriented approach has been followed since Java is our platform.

In a nutshell, our research work has till now gone through the following steps:
1. Gathering and interpretation of information through textual and online resources.
2. Deciding upon the parameters and evaluation criteria that are to be incorporated in the simulator, and also building consensus over the desired output and the presentation format.
3. Determining the feasibility of various technical and non-technical aspects.
4. A rough layout of the application and associated programming concepts that need to be followed in order to achieve the desired layout.

MINIMUM SYSTEM REQUIREMENTS
1. HARDWARE REQUIREMENTS: MAIN PROCESSOR PENTIUM 4 HARD DISK CAPACITY 80 GB RAM 1 GB PROCESSOR SPEED 466 MHZ MONITOR VGA MOUSE NORMAL
2. SOFTWARE REQUIREMENTS: OPERATING SYSTEM WINDOWS XP TOOL USED C TECHNICALITY OF DESIGN
We have designed the simulator that implements the job scheduler based on different CPU scheduling algorithms. The application allows the user to choose the number of processes that he/she wants to deal with. The choice to be made next is of the scheduling algorithm that is to be followed while deciding the series of execution of the processes.
The user is then asked to feed arrival time and burst time for each process. The CPU scheduler or the short-term scheduler follows the chosen algorithm to transfer the processes from the ready queue to the CPU. Each algorithm vacates the ready queue with different frequencies and probability. This, in turn, alters the frequency of the job scheduler.
It has been assumed that the job scheduler follows an FCFS scheme of handling the jobs inside it.
Thus, our system design incorporates the chronology of how the job queue is vacated as per the chosen scheduling algorithm. Depending on the algorithm chosen, jobs are transferred from the ready queue to the CPU, thus emptying the ready queue at distinct rates. This impacts the frequency of the job scheduler. Thus the following design has been implemented and the simulator has been built based on this.
Input:-
* Number of processes * Choice of scheduling algorithm * Arrival time of each process * Burst time of each process

Output:- * Gantt chart
The Gantt chart depicts the order of the execution of the processes and the amount of time for which it gets executed before being succeeded by another process. It is a horizontal bar chart with time as the horizontal axis and processes or jobs as the vertical axis. Individual operations, which in our case are processes, are displayed as horizontal bars in the chart, indicating the time at which the operation begins and ends.
In our Gantt chart, each horizontal bar bears the name/number of the process it corresponds to. Inside the parentheses next to the process name/number, the remaining burst is indicated so as to make the user aware about how much of burst is left in that process. * Average Waiting Time

The amount of time for which a process has been waiting in the ready queue gives the waiting time for that process. The waiting time of each process is added to each other to obtain the total waiting time (WTtot).

On dividing WTtot by the number of processes, we get the average waiting time WTavg, which is one of the most important evaluation criteria we have employed in our system.

An optimal scheduling algorithm is the one which yields a low value of the average waiting time.

* Turn-around Time

This evaluation parameter measures the interval from the time of submission of the process to the time of completion of the process. Lower the turn-around time, higher is the efficiency of the scheduler.
The system has been designed. The important aspects such as average waiting time and turn-around time have been dealt with. The design allows the user to get a hands-on experience of how a scheduler works.
The pictorial representation of the Gantt chart allows the user to visually comprehend the coming-in and going-out of processes with respect to time.

IMPLEMENTATION OF THE DESIGN
Given below is the initial screen that has four choices for the user to choose from. After feeding his choice, the user then has to enter the number of processes and the arrival and burst times of each process.
In the screenshot given below (Fig 1), the user has opted for the FCFS algorithm.

Fig. 1
Here processes P1 and P3 have the same arrival time. Thus the FCFS algorithm sorts them on the basis of burst times. P1 on account of having a shorter burst time is executed first. Since processes run for their full burst, there are no parentheses alongside the process name.
Fig 2 shows the output screen for the set of values input by the user in Fig 1.

Figure 3 illustrates a user opting for priority scheduling. And figure 4 shows the output for the same.

Fig 3
Here P1 and P3 have the same priority and hence the sorting has been done based on their arrival times.

Fig 4
The next pair of illustrations (Fig 5 and Fig 6) show how the round-robin algorithm works.

Fig 5
Here the user has to also feed in the CPU quantum time, which is amount of time for which a process runs before being succeeded by another process.

Fig 6
The processes can be seen to follow a round-robin order (P1, P2, P3, P1, P2, P3.. and so on).
The numbers within the parentheses indicate the remaining burst time corresponding to a process.

TECHNICAL DISCUSSION AND ANALYSIS OF THE ALGORITHM
The job scheduling simulator has been designed based on the cpu scheduling algorithms like FCFS (first come first serve), round robin and priority scheduling algorithm. On a first note lets discuss about the algorithm i.e the technicality behind the simulator.We are taking the no of processes, arrival time and burst time as the input to the simulator. The output of the simulator will be gnatt chart,turnaround time and average waiting time.So the algorithm goes as follows.First we make a structure for the process and gnatt chart and print the empty gnat chart.Following it we create a node according to each of the processes arrival time ,burst time and remaining time.Likewise we create node for every process.Now we simulate the process according to any of the algorithm which we choose. We check for if there is a vacant slot in the ready queue, if there is no vacant slot then we wait for the ready queue to become empty by aplying any of the scheduling algorithms.From the job queue the processes are moved in the ready queue according to FCFS algorithm always.Alternatively we check for if there is any priority given to the processes as there we have to apply priority scheduling.After checking which scheduling algorithm to apply the simulator then sorts the processes according to the process arrival time and if there are more than one process then they are sorted according to their burst time. The simulator then checks if the job queue is empty and all the processes are scheduled according to the respective algorithms or not. If scheduling is completed for all of the processes then the parameters lke average waiting time,total turnaround time,response time ,throughput and efficiency is calculated and displayed.
Thus from the simulator we are able to get a knowledge about which scheduling algorithm gives the best output that is,a lower avg waiting time ,lower turnaround time and as a result higher efficiency and find out which algorithm is the most optimal one.
So,in this way we design the job scheduling simulator to simulate the processes based on different cpu scheduling algorithms.
IMPLEMENTATION OF EXISTING ALGORITHMS
The supporting algorithm behind the simulator has been given below. The simulator allows the user to feed in number of processes, arrival and burst times, and the choice for a scheduling algorithm.
The simulator returns the Gantt chart, and turn-around and average waiting time values.

Step 1: Make a structure for process and Gantt chart.
Step 2: Print the empty Gantt chart. Step 3:Create a node according to the process’s arrival time, burst time, remaining time.

Step 4:Create another node in same format and connect it with the previous node.

Step 5: Repeat steps 3 and 4 until all the processes have their individual nodes.

Step 6: Choose one algorithm among FCFS, Round robin, priority scheduling.

Step 7: If ready queue is full then go to step 8 otherwise go to step 10.

Step 8: Wait for an empty slot in ready queue.

Step 9: Employ any of the CPU scheduling algorithms to create a vacant slot in the ready queue.

Step 10: The process in the job queue is to be moved in the empty slot of the ready queue according to FCFS.

Step 11: if (priority_scheduling=true) then sort the processes according to their priority. Otherwise go to step 12. Step 12: sort the processes according to arrival time. If there is more than one process arriving at the same time then sort them according to their burst time.

Step 13: if job queue is empty and no other process left then go to step 14.

Step 14: to calculate throughput 14a: count the no of processes executed. 14b: calculate the total time required to execute them. 14c: divide 14a/14b.

Step 15: to calculate waiting time.

15a: amount of time a process has been waiting in the ready queue. 15b: add up the waiting time of each process to get the total waiting time. 15c: divide by the total no of processes to get the average waiting time.

Step 16: to calculate turnaround time. 16a: calculate the interval from time of submission of the process to the time of completion of the process. 16b: add up all the processes turnaround time to get the total turnaround time.

Step 17: to calculate response time. 17a: calculate the time of submission to the time the first response is produced. 17b: add up all the response time of processes to get the total response time.

Step 18: to calculate efficiency.
Scheduler should keep the system busy cent percent of the time when possible. If the CPU and all the Input/Output devices can be kept running all the time, more work gets done per second than if some components are idle.

Step19: Display waiting time, response time, turnaround time, throughput and efficiency.

Step 20:- STOP.

Given above is the flowchart representation for our existing simulator algorithm.

Our simulator focuses on the three most popular CPU scheduling algorithms:

* First-Come First-Serve (FCFS) * Priority Scheduling * Round-Robin

These algorithms are described on the next few pages:

FCFS Algorithm

1. Input: number of processes n, arrival and burst times Output: Waiting time, turn-around time of each processes initializing apw1,p,n1.
2.for i = 1 to n Input burst time for each process=(i+1) End for
3.n1=n
int turn[]=new int[n] apw1=new int[n+1]
4. Initialize apw1[0]=0,float t=0, float tu=0 p=new int[n] for i = 1 to n apw1[i]=bt[i-1]+apw1[i-1] End for
5. for i = 1 to n print individual waiting time for process p for i = 0 to n p[i]=i+1 print(p[i]) End for End for
6. for i = 0 to n t+=apw1[i] float avg=t/n print average waiting time End for
7.for i = 0 to n turn[i]=bt[i]+apw1[i] print turnaround time for process(i+1) End for
8.for i = 0 to n tu+=turn[i]; float avg1=tu/n; print average turn-around time End for
9.Exit

ROUND-ROBIN SCHEDULING
1.Input: Number of process n, arrival, burst times Output: Average waiting time ,Average turn-around time
2.Input burst time for i=0 to n Enter burst Time for (i+1) End for

3.Input Time quantum for i= 0 to n a[i]=bt[i] End for for i=0 to n wt[i]=0 End for

4.for i=0 to n if(bt[i]>q) bt[i]-=q End for 5.for j= 0 to n if((j!=i)&&(bt[j]!=0)) wt[j]+=q; else for j=0 to n if((j!=i)&&(bt[j]!=0)) wt[j]+=bt[i] bt[i]=0 End if
End for

6.sum=0 for k=0 to n sum=sum+bt[k] while(sum!=0) for i=0 to n tat[i]=wt[i]+a[i] End for End while End for
7.for i=0 to n print process, average time, waiting time, total average time End for
8.floatavg_wt=0
float avg_tat=0 for j=0 to n avg_wt+=wt[j] End for for j=0 to n avg_tat+=tat[j] End for print average waiting time ,Average turn-around time

9.Exit

PRIORITY SCHEDULING
Preemptive:

1.Input: number of processes, Process time Output: Turnaround time, total average waiting time

2. for i=0 to n Enter process name= p[i] Enter process time= pt[i] Enter priority =pr[i] End for 3. for i=0 to (n-1) for j=(i+1) to n if(pr[i]>pr[j]) temp1=pr[i]; pr[i]=pr[j]; pr[j]=temp1; temp1=pt[i]; pt[i]=pt[j]; pt[j]=temp1; End if End for End for 4.temp = p[i] p[i] = p[j] p[j] = temp 5. for i=1 to n wt[i]=wt[i-1]+et[i-1] totwt=totwt+wt[i] avgwt=totwt/n End for 6. for i=0 to n Print name, time ,priority, waiting time Print total average time, average waiting time End for 7.Exit Nonpreemptive:

1.Input:Number of process Output: average turn-around time, waiting time for i =0 to n Input burst time for each process(i+1) end for
2. n1=n apw1[0]=0 float tu=0
3.for i=0 to n Enter the priority for p (i+1) end for
4.for i=0 to n pr1[i]=pr[i] end for 5.for i=0 to n for int j=i+1to n if(pr1[i]>pr1[j]) temp=pr1[i] pr1[i]=pr1[j] pr1[j]=temp end if end for
6.for i=0 to n for int j=0 to n if(pr1[i]==pr[j]) p[i]=j+1 end if end for 7.for i=0 to n int k=p[i] apw1[i+1]=bt[k-1]+apw1[i] end for for i=0 to n print individual waiting time for process p end for
8.for i=0 to n t+=apw1[i] float avg=t/n print average waiting time is=avg end for 9.for i=0 to n turn[i]=bt[k-1]+apw1[i] print turnaround time for process p end for for i=0 to n tu+=turn[i] float avg1=tu/n print average turn-around time end for

10.Exit.

ANALYSIS OF THE OUTPUT:
Here we present a brief analysis of the output.The output of the simulator is * Average waiting time * Total turnaround time * Efficiency
We check which algorithm is able to give a low average waiting time,lower turnaround time and so a higher efficiency of the given processes.
Hence the simulator gives an output of which algorithm is the optimal one i.e. the objective.

TESTING METHODOLOGY:

Black-box testing:
This is a method of software testing that examines the functionality of an application without peering into its internal structures or workings. This method of test can be applied to virtually every level of software testing: unit, integration, system and acceptance.

The job scheduling simulator application successfully passes this black box testing as we are giving the input and we are getting the desired output.In Black box testing the tester is aware of what the application does but is not aware of how it is done.

White-Box testing:
White-box testing (also known as clear box testing, glass box testing, transparent box testing, and structural testing) is a method of testing software that tests internal structures or workings of an application, as opposed to its functionality (i.e. black-box testing). In white-box testing an internal perspective of the system, as well as programming skills, are used to design test cases. The tester chooses inputs to exercise paths through the code and determine the appropriate outputs.
Here we see that the application also passes this testing method by implementing the code separately as well as along with the GUI.We get the same answer in both cases.In this testing we are more concerned about how the system works .

BIBLIOGRAPHY

* http://www.cs.allegheny.edu/sites/cs250S2008/25

* Silbersatchz, Galvin and Gagne: Operating Systems

* Operating Systems, Tannenbaum

* Introduction to Algorithms: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein

APPENDIX STUDENT INFORMATION PAGE
1. Name: Sayani Banerjee
Permanent Address: Bharat Sevashram Sangha, Kenduadihi, Bankura-722102
Email ID: sayani.banerjee1@gmail.com

2. Name: Anshuman Mahanty
Permanent Address: Alkapuri, Road No. 10, Gardanibagh, Patna- 800002
Email ID: anshumanmahanty1@gmail.com

3. Name: Ananya Das
Permanent Address: Township, Haldia-721655
Email ID: ananyadas092@gmail.com