Operating Systems Assignment #3 Solution

Programming platform




As with the previous two assignments, for this one you must ensure your submission works on linux.csc.uvic.ca. You can remotely login to this machine using




ssh anywhere on campus or from home.




You may already have access to your own Unix system (e.g., Linux, macOS) yet we recommend you work linux.csc.uvic.ca rather than try to complete the assignment

on your machine for later submission to conneX. Bugs in systems programming tend




to be platform-specific, and something that works perfectly at home may end up crashing on a different hardware configuration. Your code will be evaluated on linux.csc.uvic.ca, therefore you must ensure any work done on personal laptops or desktops also works correctly on that server.







Individual work




This assignment is to be completed by each individual student (i.e., no group work). Naturally you will want to discuss aspects of the problem with fellow students, and such discussion is encouraged. However, sharing of code is strictly forbidden. If you are still unsure about what is permitted or have other questions regarding academic integrity, please direct them as soon as possible to the instructor. (Code-similarity tools will be run on submitted work.)







Goals of this assignment




Write a C program implementing a simulation of round-robin CPU scheduling.



Write a script (in a language of your own choice) that produces some analysis the simulator output, and present a visual representation from this analysis.

















Task 1: rrsim.c




Unlike the previous assignments involving a significant amount of systems programming, in this one your work is to write a C implementation of round-robin CPU-scheduler simulation.




More specifically your implementation of rrsim.c will accept from stdin a stream of




incoming tasks – each indicating its arrival time and CPU requirement – and display the actions of the CPU at each tick (i.e., was the CPU idle? did a task use a full tick? did a task finish during the tick?). We will work with more abstract ticks rather than

specific units of time such as milliseconds or microseconds.




Below is a sample output from rrsim. Numbered arrows denote points having comments below.






$ ./rrsim --quantum 3 --dispatch 2






1






1
5
3.5






















2
7
4.9






















3
14
1.1






















<ctrl-d






2






























[00000]
IDLE
















[00001]
IDLE
















[00002]
IDLE
















[00003]
IDLE
















[00004]
IDLE




3










[00005]
DISPATCHING


























[00006]
DISPATCHING
















[00007]
id=00001 req=3.50 used=0.00




[00008]
id=00001 req=3.50 used=1.00




[00009]
id=00001 req=3.50 used=2.00
4
[00010]
DISPATCHING
























[00011]
DISPATCHING
















[00012]
id=00002 req=4.90 used=0.00




[00013]
id=00002 req=4.90 used=1.00




[00014]
id=00002 req=4.90 used=2.00




[00015]
DISPATCHING
















[00016]
DISPATCHING
















[00017]
id=00001 req=3.50 used=3.00




[00018]
id=00001 EXIT w=9.50 ta=13.00












[00018]
DISPATCHING
















[00019]
DISPATCHING
















[00020]
id=00003 req=1.10 used=0.00




[00021]
id=00003 req=1.10 used=1.00
6
[00022]
id=00003 EXIT w=6.90 ta=8.00








[00022]
DISPATCHING
















[00023]
DISPATCHING
















[00024]
id=00002 req=4.90 used=3.00




[00025]
id=00002 req=4.90 used=4.00




[00026]
id=00002 EXIT w=14.10 ta=19.00




















































































5




























7






For this run of the simulator, the length of the scheduling quantum is three ticks and the cost of a dispatch (i.e., the work of a context switch & of using the ready queue, etc.) is two ticks.



The input to rrsim up to this point has been typed in by me, and the <ctrl-d is literally the control-key-letter combination (which means “end-of-file” in
Unix). Normally I would pipe the events into rrsim either from a file or from




some event simulator. (Later in this description I briefly show the use of something I call simgen). Each input line consists of (1) a task number




(integer); (2) an arrival time/tick (integer); and (3) the number of ticks required to compute the task (float). You can assume tasks are always provided in order of increasing arrival times.




The simulator has been running for five ticks so far, starting at tick 0. Since the first task does not arrive until tick 5, the CPU is idle for the first five ticks. At tick 5 the first scheduling event occurs. Since the cost of each scheduling / dispatch is two ticks for this simulator, we show these two ticks.



The first task has now executed for three ticks – that is, the length of the quantum – and since it requires 3.5 ticks of computation it is clear that task 1 is not yet finished. Therefore it must be placed at the end of the ready queue, and the next task scheduled. It just so happens that at tick 7 the task with id 2 arrived, and since this is at the head of the queue, task 2 is scheduled. (Note, again, the cost of the dispatch).



Sometime between tick 17 and 18, task 1 was completed. Even though it really only required 0.5 ticks, we count the whole tick towards the task. There are two lines printed by the simulator for tick 18 – one to indicate the completion of task 1 (with its waiting time and turnaround reported), and another to indicate a scheduler dispatch (because at time 18 there are tasks on the queue ready to be scheduled).



Task 3 – which arrived at tick 14 and requires only 1.1 ticks of computation



– starts to run at tick 20. As its required computation fully fits the quantum of 3 for this run of the simulator, it runs to completion (i.e., uses ticks 20 and 21 for computation).




Task 2 completes at tick 26. As no more tasks will “arrive” in the simulator, and all simulator tasks are now completed, the line reporting the wait/turnaround statistics for task 2 is also the last line of the simulation.



To simplify your implementation, you must assume a quantum always starts from the beginning of each scheduling event even if the previous task did not use up its whole quantum. Also: The cost of a dispatch occurs for each scheduling event whether or not the same task that used up its quantum is selected immediately for rescheduling (i.e., even if there is only one task in the system). There is no cost for adding a newly-arrived task to the ready queue.




Your output from rrsim is to match the formatting shown in my example run.


You are provided with the following files:




rrsim.c: Your solution to Task 1 must appear in this file. The code provided to you in rrsim.c reads tasks from stdin and stores them in a linked list (see linkedlist.[ch] below). The simulator-loop code itself is to appear in the function named run_simulation().



linkedlist.[ch]: Provided code for operations on a singly-linked list. Each node in the linked list is of type taskval_t storing information about a task. The list



of events will be in such a linked list, and your ready queue for the simulator must also use a linked list with nodes of taskval_t (i.e., you are not permitted




to use an array for the ready queue). Note that moving a task from the incoming event list to the ready queue does not require creating a brand new node.




testlist.c: Completed code demonstrating usage of the linked-list functions.



Please read and study this to learn how the linked-list functions are to be used. Note routines modifying the list always return the head of the resulting list (i.e., add_front(), add_end(), remove()). Operations to be applied on all nodes of a linked list are performed using apply(). Please look at the examples in testlist using print_task() and increment_count() – defined in testlist – as function-pointer arguments to apply() implemented in linkedlist.




simgen.c: (see below)



makefile: builds rrsim, linkedlist, simgen and testlist.



Because you will want to generate random tasks for your simulator I have provided such a program named simgen. It takes two command-line arguments: the number




of tasks for the run and the seed for the random number generator. Below is an example of how simgen and rrsim work together in the bash shell (e.g., 1000 tasks




with a random-seed value 3141, for which the simulator is executed using a quantum of 50 and a dispatch cost of 0):







$ ./simgen 1000 3141 | ./rrsim --quantum 50 --dispatch 0







Task 2: Analyzing output from the simulator




The waiting time and turnaround time of tasks scheduled in a round-robin manner will vary with both the quantum length and the cost of a context switch (i.e., dispatch time). In order to explore this you are to analyze the output of the simulator’s run by computing the average waiting time and average turnaround time for all tasks. To make the analysis more interesting you must compute these for different quantum lengths and dispatch costs:




quantum lengths: 50, 100, 250, and 500 ticks
dispatch costs: 0, 5, 10, 15, 20 and 25 ticks



That is, for a particular number of tasks (at least 1000) and a particular seed (e.g., perhaps some permutation of your student number) you must perform 20 different runs of the simulator, and for each run compute the average wait and average turnaround. You are then to plot the result in two separate graphs:




Plot the average waiting times where the horizontal axis is the dispatch cost and the vertical axis is the average waiting time (both axes in ticks); each plotted line corresponds to a different quantum length.
Same as above, but instead plot the average turnaround times.



Below are graphs I have generated using data from my own implementation of rrsim. (Note your graphs will probably vary somewhat depending upon the number of tasks you choose.)



You must write your own scripts to (1) generate the data, (2) compute statistics, and




arrange them for plotting. For the two graphs above I used a combination of a bash script, a Python3 script, and gnuplot to generate, aggregate and plot the data. However, you should use whatever tools you have at your disposal, but you must at least clearly describe such usage in your submission.








What you must submit:




C source-code file named rrsim.c containing your solution to Task 1.



Two PDFs specifically named graph_waiting.pdf and graph_turnaround.pdf showing the graphs for Task 2.



A markdown file named task2.md with a description of the steps you took to complete Task 2.






What you may submit:




Any scripts or programs (or both) used to complete Task 2.






Evaluation




Given that there are a variety of possible solutions to this assignment, the teaching team will not evaluate submissions by just using a marking script. Students will instead demonstrate their work to our course marker. Sign-up sheets for demos will be provided a few days before the due-date; each demo will require 15 minutes.




Our grading scheme is relatively simple.




“A” grade: An exceptional submission demonstrating creativity and initiative. The rrsim program runs without any problems, the presented graphs meet the description set out for task 2, and task2.md clearly describes steps used to complete task 2.



“B” grade: A submission completing the requirements of the assignment. The rrsim program runs without any problems, the presented graphs meet the description set out for task 2, and task2.md clearly describes steps used to complete task 2.



“C” grade: A submission completing most of the requirements of the assignment. The rrsim program runs with some problems, or the presented graphs do not meet the description set out for task 2, or task2.md does not describes the steps used to complete task 2, or files are not correctly named.



“D” grade: A serious attempt at completing requirements for the assignment. The rrsim program runs with serious problems, and task 2 cannot be evaluated.



“F” grade: Either no submission is given, or the submission represents very little work.