CS450-SUMMER 2008

Homework Assignment # 3

Due –JULY 13 , 2008

The following directions apply to all assignments:

IMPORTANT: FOLLOW THE FOLLOWING DIRECTIONS OR YOU RISK OF HAVING YOUR SUBMISSION NOT GRADED!!!!!!!!

1. Submit homework/project assignments to BLACKBOARD’s DIGITAL DROP BOX only . Include your source code files, WHEN APPLICABLE, compiled code, WHEN APPLICABLE, executables, WHEN APPLICABLE, README file WHEN APPLICABLE, WORD file with your text type answers etc as required (see 3 below).

2. At the top of each source code file (if code is involved) include the following comments: //Author: Your name //

Student ID: your school ID// Assignment # : ___ // Problem#___//Date:

3. All assignments should include a WORD file named with the same name you use for the zipped name (see

item 4). In the WORD file include : YOUR NAME, YOUR STUDENT ID, YOUR

ASSIGNMENT #, DATE SUBMITTED.

This WORD file also has the text answers to assignments or answers to project questions other than code (i.e. text exercises).

Include any data if the assignment requires it. Any additional comments can be included in the WORD file

(for example special instructions as to how to execute your program IN CASE OF A PROGRAM).

4. Create a folder and include all the assignment files in that folder. Name that folder the same name as the zipped file described next. Zip all files and use the following convention to name the zipped file: yourlastname_assignment#.zip (for projects use yourlastname_project#.zip). Upload the zipped file to the digital drop box of Blackboard.

5. In addition, for any programs that involve executables for (UNIX environment ) or any UNIX shells script programs do the following: The source file and the executable file need to be stored in your UNIX account on the UNIX server. As part of checking your work the TA or I will try to execute your code from there. If your executable file is not there YOU WILL LOOSE THE POINTS. Make sure that the proper permissions have been issued at the file level and at the directory level (if you created a new directory in your account). Use 777 for permissions thus giving permissions to everybody. If your program does not execute, you loose the points.

NOTE: ASSIGNMENTS ARE BASED ON BOTH THE TEXT AND ANY HANDOUTS PRESENT ON THE COURSE”S WEB SITE

PROBLEM 1 (5 points)

This simulator program should be implemented in C using gcc on the UNIX server

This problem consists of a simulation program for the Dispatcher part of the Operating System. The simulator simulates the scheduling algorithms: Short Job First (non-preemptive) and Short Job First (pre-emptive).

The idea behind a simulation is that we can evaluate the algorithms and compare them by providing inputs into the simulation and looking at the output. The output usually consists of the recording of various events that took place during the execution of the simulation program and also various statistics that were collected during the execution.

In the case of pre emptive SJF scheduling, assume that each process listed arrives two ticks apart from the previous process. The user does not have to enter that information. The simulator applies that automatically when pre emptive SJF is chosen.

Note: A tick is one count of the counter. A tick can be assigned any time value that you want to (ms, seconds, minutes etc. –it does not matter)

INPUT FILE

The input file consist of the following data:

1. Number of Processes to be generated. The number can be one to 10 maximum.

2. The burst times in ms for each process listed in line 1, separated by a coma delimiter and ended by the string “end”.

3. Number of ticks to be generated. Choose a large enough number.

4. The scheduling algorithm (1= SJF non pre-emptive, 2=SJF pre-emptive).

Thus a sample input file would look like this:

A. Non pre emptive case

4 #simulate 4 processes.

10, 5, 7, 12, end #( the burst times for the 4 processes).

1000 # run simulator for 1000 ticks.

1 # Use the SJF non pre-emptive

B. Pre emptive case

4 #simulate 4 processes.

10, 5, 7, 12, end #( the burst times for the 4 processes).

0, 3, 7, 10 # Process 1 arrived at 0 time, Process 2 arrived at 3 ticks after P1, Process 3 arrived 7 ticks after P2, Process 4 arrived 10 ticks after P3.

1000 # run simulator for 1000 ticks.

2 # Use the SJF pre-emptive

IMPLEMENTATION

There are two data structures that need to be implemented. One data structure represents the Ready Queue. The second data structure is used to store the various events.

You need to generate ticks at regular intervals. Each tick represents one ms in time (not in real time of course). It is just a counter that ticks. Every so often an event occurs and it is marked by its tick number.

The simulator simulates the dispatcher and the CPU run time. It looks at the ready queue and retrieves a process, runs the process and then it switches according to the scheduling algorithm. Assume that the context switch time is 1 ms. (one count). Therefore that becomes part of the dispatch latency every time a new process is chosen. Running a process means that a process stays in the runnable state (possibly another data structure in your program) for the specified burst time according to the algorithm.

Events and statistics to be recorded in the output file are for each process:

Tick # ___: Process number __ became runnable and run for __ ms. (number of ticks)

Tick #____: Process number ___ was returned to the ready queue.

Tick#_____: Process number __ was terminated.

# repeat for all processes once they reach the termination state.

Total run time for process number __ was ___ ms

Total Wait time for process number __ was ___ms

….

…..

….

Average waiting time for all processes was _________ ms

Total run time for CPU was _________________________

Total idle time for CPU was _________________________

Percent Utilization of CPU __________________________

You should have at least 2 input test files and 2 corresponding output files submitted with your project.

In the case of the pre emptive add another input value in the input file that represents the arrival time of the process.

PROBLEM 2 (2 points)

Do exercise 6.1

Please be precise in your explanations. Prove each property (Mutual Exclusion, Progress and Bounded Waiting) one at a time.

PROBLEM 3 (3 points)

Do exercise 6.3

Do exercise 6.7

PROBLEM 4 (2 points)

Do exercise 6.27

PROBLEM 5 (3 points)

Do exercise 7.11

Do exercise 8.3