Computer Science 360 – Introduction to Operating Systems

Assignment #3

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

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

2. 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.

Page 2 of 6 — Monday, June 26, 2017

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.

1. 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.

2. 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

$ ./rrsim –quantum 3 –dispatch 2

1 5 3.5

2 7 4.9

3 14 1.1

<ctrl-d>

[00000] IDLE

[00001] IDLE

[00002] IDLE

[00003] IDLE

[00004] IDLE

[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

[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

[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

1

2

3

4

5

6

7

Page 3 of 6 — Monday, June 26, 2017

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.

3. 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.

4. 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).

5. 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).

6. 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).

7. 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.

Page 4 of 6 — Monday, June 26, 2017

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

Page 5 of 6 — Monday, June 26, 2017

• 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

(3) 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.

������

������

������

������

������

������

� � �� �� �� ��

������� ������� ����

�������� ��������

����� ����� ��������� �� � ������ ����� ���� ������ ����

����

�����

�����

�����

������

������

������

������

������

������

� � �� �� �� ��

������� ���������� ����

�������� ��������

����� ����� ��������� �� � ������ ����� ���� ������ ����

����

�����

�����

�����

Page 6 of 6 — Monday, June 26, 2017

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.