Computer science (opereatring system)
lmoueomx
new_microsoft_word_document.docxPROGRAMMING ASSIGNMENT NUMBER 2
CSC 40600 O/S SIMULATION PROCESS MANAGEMENT Spring 2016
Your team programming assignment is to write a program to simulate the operations of an Operating System as it processes a stream of incoming processes. Students will normally work in teams of two or three. Students may work by themselves but are highly discouraged from doing so. The purpose of the simulation is to compare the results of at least two different scheduling algorithms and their effect on system performance. The completed assignment is due on May 11, 2015.
PROGRAM SPECIFICATIONS: This simulation will employ only one processor (CPU), one I/O device, and one each Long Term Queue, Short Term Queue and I/O Queue. Each queue is to be limited in size as follows:
A. Long Term Queue 60 jobs
B. Short Term Queue 30 jobs
C. I/O Queue 30 jobs
Each job is to have a Process Control Block in which data about the job is kept. The actual format of the data structure to maintain this information will be determined by each team. Other data structures, such as temporary storage locations, flags, queues, etc., will be used as needed for the simulation and the format will again be determined by each team.
Time in the simulation will be measured in a unit called a "clock tick". A clock tick is one pass through the main loop of the program (see PSEUDOCODE). All statistical calculations are to be made using a clock tick as the unit of measure for the simulation.
All processes will be non-preemptive. The simulation will encounter only one type of interrupt, I/O. When a process is interrupted, suspend the process without returning it to the SHORT TERM QUEUE. When a process is suspended for I/O, use a suspend time of 3 clock ticks before returning the process to the CPU. (This simulates the context switch time)
Use FCFS scheduling for both the Long Term Queue and I/O Queue. The initial scheduling algorithm for the Short Term Queue is also to be FCFS.
For extra credit, your team may run the simulation a second time employing one (or more) of the following changes:
1. Employ one other scheduling algorithm for the Short Term Queue selected from the following: (10 points)
a. RoundRobin -- quantum between 10 and 50 (your choice)
b. Shortest Remaining Time Next
c. Shortest Job First
d. Highest-Response-Ratio Next
2. Simulate the system using preemptive processes for the scheduling
algorithm(s) employed. (5 points)
3. Simulate the system using two CPUs but one STQ (10 points)
4. Simulate the system using two I/O Devices (either with one
I/O queue for each or one I/O queue for both I/O Devices. (Five
points per additional device up to a maximum of 3 devices (15 pts).
Queues may be implemented as linkedlists, arrays or any other data structure you think is appropriate. You are to use separate wait counters for each queue and the CPU (for jobs that are suspended.) You may use GLOBAL VARIABLES if you desire but all GLOBAL VARIABLES MUST de declared in one central location (i.e. "variable.h" file)
TEAM PROGRAMMING ASSIGNMENT
CSC 40600 O/S SIMULATION PROCESS MANAGEMENT Spring 2016
Page 2
Each team will process the same data stream so a meaningful comparison of STQ algorithms can be made. The system in the simulation will process an unknown number of jobs. You may however figure on a MAXIMUM of 150 jobs for the simulation. DO NOT WRITE YOUR SIMULATION TO PROCESS ONLY 150 JOBS. IN PRACTICE, JOBS ENTER AND LEAVE THE SYSTEM ON A CONTINUING BASIS. YOU DO NOT KNOW HOW MANY JOBS YOU WILL BE PROCESSING. YOU MAY HOWEVER USE THIS FIGURE TO SET A MAXIMUM SIZE ON ANY DATA STRUCTURES USED IN YOUR SIMULATION. Other specification may be added later as the need develops.
DOCUMENTATION: Your program must be well documented. Internal documentation is to include a short heading in each routine/procedure/function to include the following:
1. File name (if external files are used) or module name.
2. The identity of the PRIMARY author of the module
3. The identity of the CONTRIBUTING author(s) of the module
4. The date the module was last revised (or created)
5. A short narrative description of what the module does (how it
contributes to the simulation).
INPUT: Input data for the program will be in the form of a series of integer numbers that represent information about a job (process) after it has been compiled. The numbers will represent, in order,
1. A job number to identify it.
2. A job length (the total of all the CPU bursts and I/O bursts)
3. The inter arrival time (the time between consecutive jobs
arriving into the system)
4 The I/O Burst length. (The length of time a process requires
an I/O device.)
5. A series of CPU Bursts. (One CPU burst is the time a process
requires the CPU to complete a task.)
The I/O Burst length will be constant within one job but may change between jobs. The number and length of CPU Bursts will vary within each job. Each job begins with a CPU burst and ends with an I/O burst. Each job will have a maximum of 25 CPU Bursts. A burst is simply a length of time that the job is engaged in some type of productive activity. We are NOT interested in the particulars of the activity but simply the amount of time each activity consumes.
PROCESSING: Processing will consist of gathering information about each job as it passes through the system. The actual amount and type of data necessary to produce the desired output results will be determined by each team. The CPU and I/O Bursts act as counters for determining how long a job stays in the system. For example, a job in the CPU will have its current CPU burst length decremented by one for each pass through the main loop of
the program. Similarly, the I/O burst length will be decremented if the job is in the state of processing I/O. Also, all waiting counters must be incremented if a job is not processing either an I/O or CPU burst. This must be done for each job in the system for each pass through the loop in the main program. After the last job is processed, statistical data for the simulation will be computed.
TEAM PROGRAMMING ASSIGNMENT
CSC 40600 O/S SIMULATION PROCESS MANAGEMENT Spring 2016
Page 3
Individual job information that you may need to monitor are described below. 1. A label to indicate to which job the statistic belongs
2. Total time spend in the CPU
3. Total wait time in the Long Term Queue
4. Total wait Time in the Short Term Queue
5. Total wait Time in the I/O Queue
6. Turnaround Time
7. Response Time
8. Total time spent in context switching
OUTPUT: Output for the simulation is to contain enough meaningful data so that a valid comparison of different algorithms may be made. The output will consist of a statistical summary of the results of the simulation. As a minimum the summary report is to consist of the following:
1. The identity of the team members
2. The algorithm used
3. The total time to complete the simulation
3. The total system time spent in context switching
4. CPU utilization rate
5. The Average Response Time for all jobs.
6. Average Turnaround Time for all jobs
7. The system Throughput per 1000 clock ticks.
8. The Average LTQ wait time for all jobs.
9. The Average STQ wait time for all jobs.
10. The Average IOQ wait time for all jobs.
All output information must have an appropriate label and all numeric information is to be accurate to two decimal places. The actual format is left to the determination of each team but it should be a COMPROMISE BETWEEN READABILITY AND CONSERVATION OF PAPER RESOURCES.
EXTRA CREDIT ONE: Include in your program output the calculated average,
(10 points) variance, and standard deviation of the Inter Arrival
Times, the Job Lengths, the I/O Burst Lengths and the CPU
Burst Lengths of all jobs.
EXTRA CREDIT TWO: Submit a type written report that includes the following:
(10 points) 1. The title of the report
2. The identity (names) of the team members.
3. The simulation specifications to include:
A. Number of jobs processed
B. Number of major devises (CPU, STQ, etc.) used
C. Type of scheduling algorithm(s) used and on
which devices( CPU, I/O, and queues)
D. Any other information the team may deem
appropriate.
4. If the program employs a second algorithm, an outline
of the algorithm (or PSEUDOCODE) used in the
simulation to manage the Short Term Queue
5. A minimum of three (3) ways in which the simulation
can be enhanced (made more realistic)
THIS ASSIGNMENT MAY BE WORTH A TOTAL OF 120 POINTS OUT OF A POSSIBLE 100.
OPERATING SYSTEM SIMULATION PSEUDOCODE
This handout is meant as a guide in developing your OS simulation program. You may use it as such or you may completely ignore it as you develop your program. This guide employs the FCFS algorithm.
MAIN Module (** Indicates a separate procedure.)
1. Initialize variables
** 2. Read in all processes from the input file.
** 3. Enter the first process into the system.
4. Increment the clock
5. While (jobs are being processed)
** 4.1 Manage the LTQ
** 4.2 Manage the STQ
** 4.3 Manage the CPU
** 4.4 Manage the I/O Queue
** 4.5 Manage the I/O Device
** 4.6 Remove finished jobs
4.7 Increment the clock
** 4.8 Check for incoming processes
** 6. Process the accumulated data.
1. The variables to initialize and their meanings are (15):
clock = 0 {The simulator clock to keep track of the
total time of the simulation run }
io_timer = 0 {Indicates the current I/O burst }
job_timer = 0 {Keeps track of the time between job arrivals}
more_jobs = 0 {Keeps track of the # of jobs in system }
process_timer = 0 {Keeps track of the current CPU burst }
suspend_timer = 0 {Keeps track of current interrupt time }
cpu_ready_flag = true {Signals that the CPU is available }
cpu_complete_flag = false {Signals the completion of a CPU burst }
finished_flag = false {Signals that a JOB is finished }
interrupt_flag = false {Signals that an interrupt is in progress }
io_complete_flag = false {Signals the completion of an I/O burst }
io_device_flag = true {Signals that the I/O device is available }
job_flag = false {Signals the a job has arrived }
stop_flag = false {Signals to stop CPU job processing }
suspend_flag = false {Signals context switch to handle interrupt }
Other variables used are:
cpu = 0 {integer to indicate which job has the CPU. }
count = 0 {keeps track of the number of processes ran }
devise = 0 {integer to signal which process is in the I/O device }
process = 1 {integer to indicate the process entering the CPU }
ioprocess =1 {integer to indicate the process entering the I/O device}
temp = 0 {integer to indicate which process is suspended }
ioq_full = false {Signals that the I/O Queue is full }
ioq_empty = true {Signals that the I/O Queue is empty }
ltq_empty = true {Signals that the Long Term Queue is empty }
ltq_full = false {Signals that the Long Term Queue is full }
stq_empty = true {Signals that the Short Term Queue is empty}
stq_full = false {Signals that the Short term Queue is full }
Operating System Simulation Page 2
2. Read in all processes contained in the input file. Each line is one
process (record) which can be read into some structure created by you.
3. Get a job into the system. This routine checks to see if a job has
arrived. If one has arrived, then a FLAG is set for the LTQ to
pick up the JOB and the number of jobs in the system is increased by
one.
3.1 Increment job_timer.
3.2 IF (process interarrival time = job_timer )
3.2.1 Set job_flag to TRUE { Signal LTQ of job arrival }
3.2.2 Record time of arrival
3.2.3 Reset job_timer to zero
3.2.4 Increment count { Total number of jobs ran }
3.2.5 Increment more_jobs { Number of Jobs in the system }
4. WHILE (there are jobs to process)
4.1 Managing the LTQ This routine increments the LTQ Wait counters
for all the processes in the Long Term Queue and places any
incoming jobs in the back of the queue.
4.1.1 IF (ltq_empty is FALSE) THEN { the LTQ queue is not empty}
Increment the WAIT counters for all processes in the queue.
4.1.2 IF (job_flag is TRUE) AND (ltq_full is FALSE) THEN
4.1.2.1 Put the incoming job(s) in the queue.
4.1.2.2 Set job_flag to FALSE
4.1.2.3 Set ltq_empty to FALSE
4.1.3 IF (the LTQ queue is full) THEN
Set ltq_full to TRUE
Operating System Simulation Page 3
4.2 Managing the STQ This routine increments the STQ Wait counters
for all processes in the Short Term Queue. It then moves a job,
that is finished with the I/O device, from the I/O device to the
Short Term Queue.
{ the STQ is not empty }
4.2.1 IF (stq_empty is FALSE) THEN
Increment the WAIT counter for all processes in the Queue
{A process has finished with
the I/O device and the STQ
is not full }
4.2.2 IF (io_complete_flag is TRUE) THEN
4.2.2.1 Set the io_complete_flag to FALSE
4.2.2.2 Set the io_device_flag to TRUE
4.2.2.3 IF (finished_flag is TRUE) THEN
4.2.2.3.1 Decrement more_jobs {Remove job from the system}
4.2.2.3.2 Set finished_flag to FALSE
4.2.2.3.3 Collect the data
ELSE
IF (stq_full is FALSE) THEN
4.2.2.3.4 Place the process in the STQ
4.2.2.3.5 Set device = 0
4.2.2.3.6 IF (STQ is full) THEN
Set stq_full to TRUE
{The STQ is not full and the
LTQ is not empty}
4.3.3 IF (stq_full is FALSE) AND (ltq_empty is FALSE) THEN
4.3.3.1 Move a process from the LTQ to the STQ
4.3.3.2 Set stq_empty to FALSE
4.3.3.3 IF (LTQ is now empty) THEN
4.3.3.3.1 Set ltq_empty to TRUE
4.3.3.3.2 Set ltq_full to FALSE
4.3.3.4 IF (STQ is full) THEN
Set stq_full to TRUE
Operating System Simulation Page 4
4.3 Managing the CPU
4.3.1 IF (suspend_flag = TRUE) THEN {the process is suspended }
Decrement the suspend_timer
{Check for completion of interrupt}
IF ( suspend_timer = 0 ) THEN
Set interrupt_flag to FALSE
Set suspend_flag to FALSE
ELSE {a process is in the CPU when
interrupt occurred}
IF (temp = process) THEN
Increment cpu WAIT counter
Set stop_flag to TRUE
{check for interrupt if processing
4.3.2 IF (stop_flag = FALSE) THEN has not been halted}
IF (interrupt_flag = TRUE) THEN
IF (suspend_timer = 0) THEN
IF (cpu > 0) THEN {Suspend the process}
Set temp = cpu
Set cpu = 0
Set suspend_timer = 3
Set suspend_flag to TRUE
{ if there is no interrupt and a job is
in the cpu, process the cpu burst and
check to see if it is finished }
ELSE
IF (cpu = process) THEN
Increment process_timer
IF ( process_timer = cpu burst length ) THEN
Set cpu_complete_flag to TRUE
Set process_timer to 0
{ IF the interrupt flag is not set and
if a process has been suspended }
ELSE
IF (temp = process) THEN
Set cpu = process
Increment cpu wait counter
Set temp = 0
{ If the interrupt flag is not set and if a
process has not been suspended and if the
STQ is not empty, get the next job for the
cpu, reset the cpu ready flag, and reset
the process timer. }
ELSE
IF(stq_empty = FALSE)AND
(cpu_ready_flag is TRUE ) THEN
Set process=the head of the STQ
Set cpu = process
Delete job from the queue
Set stq_full to FALSE
IF (STQ is now empty) THEN
Set stq_empty to TRUE
Set cpu_ready_flag to FALSE
Set process_timer to 0
4.3.3 Set the stop_flag to FALSE
Operating System Simulation Page 5
4.4 Manage the I/O Queue - This routine increments the I/O Wait
counters for all the processes in the I/O Queue and places
any job finished with the CPU in the back of the queue.
4.4.1 IF ( ioq_empty is FALSE ) THEN { I/O Queue is not empty }
Increment the I/O Queue Wait counter for all processes
in the Queue.
4.4.2 IF (cpu_complete_flag is TRUE) THEN
IF (ioq_full is FALSE ) THEN
Add the process to the tail of the queue.
Set cpu = 0
Set ioq_empty to FALSE
Set cpu_ready_flag to TRUE
IF (the queue is full) THEN
Set ioq_full to TRUE
Set the cpu_complete_flag to FALSE
4.5 Manage the I/O Device
4.5.1 IF ( interrupt_flag is FALSE ) THEN
IF ( device = ioprocess) THEN { process is in the
I/O device }
Increment the I/O Timer
{ if the I/O burst is finished and
there are more cpu burst to process,
set the interrupt flag. }
IF ( io_timer = I/O burst length ) THEN
Set io_complete_flag to TRUE
Set device = 0
IF ( next CPU burst length <> 0 ) THEN
Set the interrupt flag to TRUE
ELSE
Set the finished_flag to TRUE
ELSE
IF ( ioq_empty is FALSE ) AND
( io_device_flag is TRUE ) THEN
{ the I/O Queue is not empty
so place a process in the
I/O device from the queue }
Set ioprocess = head of the IOQ
Set device = ioprocess
Delete the job from I/O queue
IF the IO Queue is now empty,
Set ioq_empty to TRUE
Set the io_timer = 0
Set io_device_flag to FALSE
Other routines that you may need include:
1. a routine to add a job to a queue.
2. a routine to delete a job from a queue.
3. a routine to take a job out of the system
4. a routine to compute the statistical data
5. a routine to process the data.
NOTE: This list is not meant to be complete.
Schematic Diagram for the OPERATING SYSTEM Simulation
Incoming Job Flag Program Clock Job Timer
Files
Suspension
Long Term Queue Timer
Temp
.
Suspend Flag
CPU
STQ Ready
Flag
Process
Short Timer
Term
Queue
CPU Ready Flag
I/O Queue
Ready Flag
I/O I/O I/O Queue
Completion Interrupt
Flag Flag
Finished
Flag
I/O Device
I/O Device
Flag
I/O Timer
NOTE: Other Flags may be necessary
to monitor the full or empty
status of queue.
Results to the User
GENERAL OUTLINE FOR THE OPERATING SYSTEM PROJECT
1. Main Program
A. CREATE the desired information about the JOBS using
some random number function. (This will be done by
the instructor)
B. READ in all processes from the file created in "A"
C. DO WHILE Last_Job NOT Done
1) Start Clock
2) Read Job Record
3) Manage the Long Term Queue
4) Manage the Short Term Queue(s)
5) Manage the CPU(s)
6) Manage the I/O Queue(s)
7) Manage the I/O Device(s)
8) Check for finished jobs
9) Check for incoming processes
D. Compile the statistical data.
E. Process the data.
F. Produce the desired output.
