Operating System Simulation Lab ( 5CS10)
INTRODUCTIONCHAPTER 1
1.1 Operating Sytem :
A computer system can be divided roughly into four components: the hardware, the operating system, the applications programs, and the users (Figure 1). The hardware - the central processing unit (CPU), the memory, and the input/output (1/0) devices - provides the basic computing resources. The applications programs - such as compilers, database systems, games, and business programs - define the ways in which these resources are used to solve the computing problems of the users. There may be many differentusers (people, machines, other computers) trying to solve different problems. Accordingly, there may be many different applications programs. The operating system controls and coordinates the use of the hardware among the various applications programs for the various users.
Fig1: Abstract View of the Components of a Computer System.
Operating System manages:
Process Management
Memory Management
File Management
Scheduling of process
Networking
Protection of Data
1.2 Process Scheduling
The objective of multiprogramming is to have some process running at all times,to maximize CPU utilization. The objective of time sharing is to switch the CPUamong processes so frequently that users can interact with each program whileit is running. For a uniprocessor system, there will never be more than onerunning process. If there are more processes, the rest will have to wait until theCPU is free and can be rescheduled.
1.2.1 Preemptive Scheduling
CPU scheduling decisions may take place under the following four circumstances:
1. When a process switches from the running state to the waiting state (for example, I/O request, or invocation of wait for the termination of one of the child processes)
2. When a process switches from the running state to the ready state (for example, when an interrupt occurs)
3. When a process switches from the waiting state to the ready state (for example, completion of I/O)
4. When a process terminates
For circumstances 1 and 4, there is no choice in terms of scheduling. A new process (if one exists in the ready queue) must be selected for execution. There is a choice, however, for circumstances 2 and 3. When scheduling takes place only under circumstances 1 and 4, we say the scheduling scheme is nonpreemptive; otherwise, the scheduling scheme is preemptive. Under nonpreemptive scheduling, once the CPU has been allocated to a process, the process keeps the CPU until it releases the CPU either by terminating or by switching to the waiting state. This scheduling method is used by the Microsoft Windows environment. It is the only method that can be used on certain hardware platforms, because it does not require the special hardware (for example, a timer) needed for preemptive scheduling.
1.2.2 Scheduling Criteria
Different CPU scheduling algorithms have different properties and may favor one class of processes over another. In choosing which algorithm to use in a particular situation, we must consider the properties of the various algorithms. Many criteria have been suggested for comparing CPU scheduling algorithms. Which characteristics are used for comparison can make a substantial difference in the determination of the best algorithm. Criteria that are used include the following:
CPU utilization. We want to keep the CPU as busy as possible. CPU utilization may range from 0 to 100 percent. In a real system, it should range from 40 percent (for a lightly loaded system) to 90 percent (for a heavily used system).
Throughput. If the CPU is busy executing processes, then work is being done. One measure of work is the number of processes that are completed per time unit, called throughput. For long processes, this rate may be one per second.
Turnaround time. From the point of view of a particular process, the important criterion is how long it takes to execute that process. The interval from the time of submission of a process to the time of completion is the turnaround time. Turnaround time is the sum of the periods spent waiting to get into memory, waiting in the ready queue, executing on the CPU, and doing I/O.
Waiting time. The CPU scheduling algorithm does not affect the amount of time during which a process executes or does I/O; it affects only the amount of time that a process spends waiting in the ready queue. Waiting time is the sum of the periods spent waiting in the ready queue.
Response time. In an interactive system, turnaround time may not be the best criterion. Often, a process can produce some output fairly early, and can continue computing new results while previous results are being output to the user. Thus, another measure is the time from the submission of a request until the first response is produced. This measure, called response time, is the amount of time it takes to start responding, but not the time that it takes to output that response. The turnaround time is generally limited by the speed of the output device.
1.3 Scheduling Algorithms
CPUscheduling deals with the problem of deciding which of the processes in the ready queue is to be allocated the CpU. There are many different CPU scheduling algorithms. In this section, we describe several of these algorithms.
1.3.1 First-Come, First-Served Scheduling
By far the simplest CPU scheduling algorithm is the first-come, first-served scheduling (FCFS) algorithm. With this scheme, the process that requests the CPU first is allocated the CPU first. 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. When the CPU is free, it is allocated to the process at the head of the queue. The running process is then removed from the queue.
1.3.2 Shortest-Job-First Scheduling
A different approach to CPU scheduling is the shortest-job-first (SJF) algorithm. This algorithm associates with each process the length of the latter's next CPU burst. When the CPU is available, it is assigned to the process that has the smallest next CPU burst. If two processes have the same length next CPU burst, FCFS scheduling is used to break the tie. Note that a more appropriate term would be the shortest next CPU burst, because the scheduling is done by examining the length of the next CPU-burst of a process, rather than its total length.
1.3.3 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.
Note that we discuss scheduling in terms of high priority and low priority. Priorities are generally 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.
1.3.4 Round-Robin Scheduling
The round-robin (RR) scheduling algorithm is designed especially for timesharing systems. It is similar to FCFS scheduling, but preemption 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. The CPU scheduler goes around the ready queue, allocating the CPU to each process for a time interval of up to 1 time quantum.
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.
Implementation of Scheduling AlgorithmsChapter 2
Object : Write a program to implement FCFS Scheduling Algorithm in C/C++.
Tool Used: C Language Compiler
Windows: Turbo C/ Turbo C++
Linux- GCC/ CC
Program :
#include<stdio.h>
main()
{
int n,bu[20];
float twt,awt,wt[20],tat[20],sum=0;
int i;
printf("Enter the no of processes:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
printf("\nEnter The BurstTime for Process p[%d]",i);
scanf("%d",&bu[i]);
}
wt[1]=0;
for(i=2;i<=n;i++)
{
wt[i]=bu[i-1]+wt[i-1];
}
for(i=1;i<=n;i++)
{
twt=twt+wt[i];
tat[i]=bu[i]+wt[i];
sum+=tat[i];
}
awt=twt/n;
sum=sum/n;
printf("\nTotal Waiting Time=%f",twt);
printf("\nAverage Waiting Time=%f",awt);
printf("\nAverage Turnaround time=%f",sum);
}
Output :
Enter the no of processes:3
Enter The BurstTime for Process p[1]2
Enter The BurstTime for Process p[2]3
Enter The BurstTime for Process p[3]1
Total Waiting Time=7.000000
Average Waiting Time=2.333333
Average Turnaround time=4.333333
Object : Write a program to implement SJF Scheduling Algorithm in C/C++.
Tool Used: C Language Compiler
Windows: Turbo C/ Turbo C++
Linux- GCC/ CC
Program :
#include<stdio.h>
main()
{
int n,bu[20],temp;
float twt,awt,wt[20],tat[20],sum=0;
int i,j;
printf("Enter the no of processes:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
printf("\nEnter The BurstTime for Process p[%d]",i);
scanf("%d",&bu[i]);
}
for(i=n;i>=1;i--)
{
for(j=2;j<=n;j++)
{
if(bu[j-1]>bu[j])
{
temp=bu[j-1];
bu[j-1]=bu[j];
bu[j]=temp;
}
}
}
wt[1]=0;
for(i=2;i<=n;i++)
{
wt[i]=bu[i-1]+wt[i-1];
}
for(i=1;i<=n;i++)
{
twt=twt+wt[i];
tat[i]=bu[i]+wt[i];
sum+=tat[i];
}
awt=twt/n;
sum=sum/n;
printf("\nTotal Waiting Time=%f",twt);
printf("\nAverage Waiting Time=%f",awt);
printf("\nAverage Turnaround time=%f",sum);
}
OUTPUT:
Enter the no of processes:3
Enter The BurstTime for Process p[1]2
Enter The BurstTime for Process p[2]1
Enter The BurstTime for Process p[3]3
Total Waiting Time=4.000000
Average Waiting Time=1.333333
Average Turnaround time=3.333333
Object : Write a program to implement Priority Scheduling Algorithm in C/C++.
Tool Used: C Language Compiler
Windows: Turbo C/ Turbo C++
Linux- GCC/ CC
Program :
#include<stdio.h>
main()
{
int n,b[10],w[10],i,j,h,t,tt;
int stime[10],a[10],p[10];
float avg=0;
printf("\n\tPRIORITY SCHEDULING ALGORITHM");
printf("\n\t*****************************************************\n");
printf("\nEnter howmany jobs:");
scanf("%d",&n);
printf("\nEnter burst time & priority for corresponding job....\n");
for(i=1;i<=n;i++)
{
printf("\nProcess %d:",i);
scanf("%d %d",&b[i],&p[i]); a[i]=i;
}
for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
if(p[i]<p[j])
{
t=b[i]; tt=a[i];
b[i]=b[j]; a[i]=a[j];
b[j]=t; a[j]=tt;
}
w[1]=0;
printf("\nprocess %d waiting time is 0",a[1]);
for(i=2;i<=n;i++)
{
w[i]=b[i-1]+w[i-1];
printf("\nProcess %d waiting time: %d",a[i],w[i]);
avg+=w[i];
}
printf("\ntotal waiting time:%f",avg);
printf("\n\nthe average waiting time is:%f\n",avg/n);
}
OUTPUT:
PRIORITY SCHEDULING ALGORITHM
*****************************************************
Enter howmany jobs:2
Enter burst time & priority for corresponding job....
Process 1:3
2
Process 2:4
1
process 1 waiting time is 0
Process 2 waiting time: 3
total waiting time:3.000000
the average waiting time is:1.500000
Object : Write a program to implement Round Robin Scheduling Algorithm in C/C++.
Tool Used: C Language Compiler
Windows: Turbo C/ Turbo C++
Linux- GCC/ CC
Program :
#include<stdio.h>
main()
{
int n,bu[20],tq,b[20],max=0,Rrobin[20][20],m,j,k,count[10];
float twt,awt,wt[20],tat[20],sum=0;
int i;
printf("Enter the no of processes:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
printf("\nEnter The BurstTime for Process p[%d]",i);
scanf("%d",&bu[i]);
b[i]=bu[i];
if(max<b[i])
max=b[i];
wt[i]=0;
}
printf("Enter the time quantum:");
scanf("%d",&tq);
if(max%tq!=0)
//TO find the dimension of the Round robin array
m=max/tq+1;
else
m=max/tq;
//initializing Round robin array
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
Rrobin[i][j]=0;
}
}
//placing value in the Rrobin array
i=1;
while(i<=n)
{
j=1;
while(b[i]>0)
{
if(b[i]>=tq)
{
b[i]=b[i]-tq;
Rrobin[i][j]=tq;
j++;
}
else
{
Rrobin[i][j]=b[i];
b[i]=0;
j++;
}
}
count[i]=j-1;
i++;
}
for(j=1;j<=n;j++)
{
for(i=1;i<=count[j];i++)
{
if(i==count[j])
{
for(k=1;k<j;k++)
{
if(k!=j)
wt[j]+=Rrobin[k][i];
}
}
else
for(k=1;k<=n;k++)
{
if(k!=j)
wt[j]+=Rrobin[k][i];
}
}
}
for(i=1;i<=n;i++)
printf("\nWaiting Time for process P[%d]=%f",i,wt[i]);
//calculating Average Weighting Time
for(i=1;i<=n;i++)
{
twt=twt+wt[i];
tat[i]=bu[i]+wt[i];
sum+=tat[i];
}
awt=twt/n;
sum=sum/n;
printf("\nTotal Waiting Time=%f",twt);
printf("\nAverage Waiting Time=%f",awt);
printf("\nAverage Turnaround time=%f",sum);
}
OUTPUT:
Enter the no of processes:3
Enter The BurstTime for Process p[1]2
Enter The BurstTime for Process p[2]3
Enter The BurstTime for Process p[3]4
Enter the time quantum:1
Waiting Time for process P[1]=2.000000
Waiting Time for process P[2]=4.000000
Waiting Time for process P[3]=5.000000
Total Waiting Time=11.000000
Average Waiting Time=3.666667
Average Turnaround time=6.666667
MOSS SimulatorChapter 3
3.1 MOSS Scheduling Simulator
Introduction
The scheduling simulator illustrates the behavior of scheduling algorithms against a simulated mix of process loads. The user can specify the number of processes, the mean and standard deviation for compute time and I/O blocking time for each process, and the duration of the simulation. At the end of the simulation a statistical summary is presented. Students may also be asked to write their own scheduling algorithms to be used with process loads defined by the instructor.
Running the Simulator
The program reads a configuration file (scheduling.conf) and writes two output files (Summary-Results and Summary-Processes).
To run the program, enter the following command line.
$ java Scheduling scheduling.conf
The program will display "Working..." while the simulation is working, and "Completed." when the simulation is complete.
Working...
Completed.
The simulator reads parameters from the configuration file ("scheduling.conf"). It creates a specified number of processes, each of which blocks for input or output after a number of milliseconds that can be specified for each process. Each process is allowed to run for a randomly generated amount of time, with the amount of time constrained by a specified average (mean) in milliseconds, and standard deviations from that average. The simulation may also be bounded in the total length of its run.
After reading the configuration file, the scheduling algorithm then "runs" the processes, causing each to block for input or output after the specified interval until all processes have completed their randomly generated amount of runtime, or until the maximum amount of runtime for the simulation is exceeded.
As the simulation proceeds, a log file ("Summary-Processes") is generated which shows the activity of the scheduling algorithm as it considers each process in the process queue.
After the simulation halts, a summary report ("Summary-Results") is generated which shows statistics for each process and for the simulation as a whole.
The Configuration File
The configuration file (scheduling.conf) is used to specify various parameters for the simulation, including:
- the number of processes,
- the mean runtime for a process,
- the standard deviation in runtime for a process,
- for each process, how long the process runs before it blocks for input or output, and
- how long the simulation should run.
Configuration File Options
There are a number of options which can be specified in the configuration file. These are summarized in the table below.
Keyword / Values / Descriptionnumprocess / n / The number of processes to create for the simulation.
meandev / n / The average length of time in milliseconds that a process should execute before terminating.
standdev / n / The number of standard deviations from the average length of time a process should execute before terminating.
process / n / The amount of time in milliseconds that the process should execute before blocking for input or output. There should be a separate process directive for each process specified by the numprocess directive.
runtime / n / The maximum amount of time the simulation should run in milliseconds.
Sample Configuration File
The "scheduling.conf" configuration file looks like this:
// # of Process
numprocess 3
// mean deivation
meandev 1100
// standard deviation
standdev 510
// process # I/O blocking
process 100
process 500
process 30
// duration of the simulation in milliseconds
runtime 5000
The Summary-Results File
The Summary-Results file contains a summary report describing the simulation and includes one line of summary information for each process. The fields and columns in the report are described in the following table.
Field / DescriptionScheduling Type: / The type of the scheduling algorithm used. The value displayed is "hard coded" in the SchedulingAlgorithm.java file.
Scheduling Name: / The name of the scheduling algorithm used. The value displayed is "hard coded" in the SchedulingAlgorithm.java file.
Simulation Run Time: / The number of milliseconds that the simulation ran. This may be less than or equal to the total amount of time specified by the "runtime" configuration parameter.
Mean: / The average amount of runtime for the processes as specified by the "meandev" configuration parameter.
Standard Deviation: / The standard deviation from the average amount of runtime for the processes as specified by the "standdev" configuration parameter.
Process # / The process number assigned to the process by the simulator. The process number is between 0 and n-1, where n is the number specified by the "numprocess" configuration parameter.
CPU Time / The randomly generated total runtime for the process in milliseconds. This is determined by the "meandev" and "standdev" parameters in the configuration file.
IO Blocking / The amount of time the process runs before it blocks for input or output. This is specified for each process by a "process" directive in the configuration file.
CPU Completed / The amount of runtime in milliseconds completed for the process. Note that this may be less than the CPU Time for the process if the simulator runs out of time as specified by the "runtime" configuration parameter.
CPU Blocked / The number of times the process blocked for input or output during the simulation.
Sample Summary-Results File
The output "Summary-Results" file looks something like this:
Scheduling Type: Batch (Nonpreemptive)
Scheduling Name: First-Come First-Served
Simulation Run Time: 2750
Mean: 1100
Standard Deviation: 510
Process #CPU TimeIO BlockingCPU CompletedCPU Blocked
01372 (ms)100 (ms)1372 (ms)13 times
1689 (ms)500 (ms)689 (ms)1 times
2689 (ms)30 (ms)689 (ms)22 times
The Summary-Processes File
The Summary-Processes file contains a log of the actions taken by the scheduling algorithm as it considers each process in the scheduling queue.
Each line in the log file is of the following form:
Process: process-numberprocess-status... (cpu-timeblock-timeaccumulated-timeaccumulated-time)