Assignment 2: Multi-Flow Scheduler (MFS)

Assignment 2: Multi-Flow Scheduler (MFS)

1 Introduction
In this assignment, you need to implement a task scheduler. You will learn how to use the three programming5 constructs provided by the posix pthread library:6
1. threads7
2. mutexes8
3. condition variables (convars)9
to do so. Your goal is to construct a simulator of a router (in a broad sense, a router is a computer anyway) to10 schedule the transmission of multiple traffic flows. The scheduler is called Multi-Flow Scheduler (MFS).11 As shown in Figure 1, n flows to the router should be transmitted via its output interface. Each flow is allocated12 to a dedicated queue. Assume that the router has only one output interface, which must be shared by the flows. To13 simplify your job, we assume flows are given before hand and their description is stored in a file (refer to Section 2.2).14 You will use threads to simulate the flows arriving and waiting for transmission, and your program will schedule15 these flows to meet the requirements in Section 2.3.16
2 Flows17
2.1 Properties of Flows18
Each flow, which will be simulated by a thread, has the following attributes:19
1. Arrival Time: It indicates when the flow will arrive.20
2. Transmission Time: It indicates the time required to transmit the flow (i.e., from the time when the flow21 is scheduled to transmit to the time when its transmission is over). We assume non-preemptive scheduling,22 meaning that when a flow is transmitting, other flows with a higher priority cannot interrupt its transmission.23
3. Priority: It is an integer number between 1 (inclusive) and 10 (inclusive), indicating the priority of the flow.24 A larger number means a lower priority.25
All times are measured in 10ths of a second. The times will be simulated by having your threads, which represent26 flows, to call usleep() for the required amount of time.27
Figure 1: The multi-flow scheduling system
1
2.2 The Format of Input File28
Your program (MFS) will accept one parameter on the command line:29
MFS flow.txt30
where flow.txt is the name of the input file.31
2.2.1 File Format32
The input file is a text file and has a simple format. The first line contains the number of flows that will be simulated.33 After that, each line contains the information about a single flow, such that:34
1. The first character specifies the unique number of the flow.35
2. A colon(:) immediately follows the unique number of the flow.36
3. Immediately following is an integer that indicates the arrival time of the flow.37
4. A comma(,) immediately follows the previous number.38
5. Immediately following is an integer that indicates the transmission time of the flow.39
6. A comma(,) immediately follows the previous number.40
7. Immediately following is an integer that indicates the priority of the flow.41 8. A newline (\n) ends a line.42 To not kill yourself by checking the false input file, you should build a correct input file for your own test. We43 will not test your code with an input file that does not comply with the above format.44
2.2.2 An Example45
The following file specifies three flows.46
347 1:3,60,348 2:6,70,149 3:3,50,350
The flow specifications are listed in the following table:51
Flow No. Arrival time Transmission time Priority 1 0.3s 6s 3 2 0.6s 7s 1 3 0.3s 5s 3
52
2.3 Simulation Rules53
The rules enforced by the MFS are:54
1. Only one flow is on transmission at any given time.55
2. When a flow arrives, the arriving flow starts transmission if no other flow is on transmission; otherwise, the56 arriving flow must wait.57
3. When multiple flows arrive at the same time and no other flow is on transmission, the arriving flow with58 the highest priority starts its transmission. If they have the same priority, the one that has the smallest59 transmission time starts its transmission. If there is still a tie, the one that appears first in the input file starts60 its transmission first.61
2
4. When a flow finishes its transmission, all waiting flows compete for next transmission according to the following62 rules:63
(a) The one with the highest priority start its transmission first.64 (b) If there is a tie at the highest priority, the one whose arrival time is the earliest start its transmission first.65 (c) If there is still a tie, the one that has the smallest transmission time starts its transmission first.66 (d) If there is still a tie, the one that appears first in the input file starts its transmission first.67
2.4 Output68
Your simulation is required to output all events and state changes showing the internal behavior of MFS. The69 messages must include, but are not limited to:70
1. A flow arrives71
2. A flow waits for the completion of another transmitting flow.72
3. A flow starts transmission73
4. A flow finishes its transmission74
You must:75
1. print the arrival of each flow using the following format string to show the flow attributes:76
"Flow %2d arrives: arrival time (%.2f), transmission time (%.1f), priority (%2d). \n"77
2. print the ID of the waiting flow and the ID of the waited flow using the format string:78
"Flow %2d waits for the finish of flow %2d. \n"79
3. print the ID of the flow that starts its transmission and the time when it starts transmission using the format80 string:81
"Flow %2d starts its transmission at time %.2f. \n"82
4. print the ID of the flow that finishes its transmission and the time when it finishes transmission using the83 format string:84
"Flow %2d finishes its transmission at time %d. \n"85
Note that the output of times (including arrival time, the time when a flow starts transmission, the time when86 a flow finishes its transmission) is relative machine time, calculated by the machine time when the output event87 occurs minus the machine time when the simulation starts. Therefore, the output of the times may not exactly88 matches (but should be close to) the results with manual calculation.89
3 Design before Coding90
You should write a design document which answers the following questions. It is recommended that you think91 through the following questions very carefully before coding. Debugging will be harder after the basic design has92 been coded. Therefore, it is very important to ensure that the basic design is correct. So think about the following93 carefully and then write down the answers.94
1. How many threads are you going to use? Specify the task that you intend each thread to perform.95
2. Do the threads work independently? Or, is there an overall “controller” thread?96
3. How many mutexes are you going to use? Specify the operation that each mutex will guard.97
3
4. Will the main thread be idle? If not, what will it be doing?98
5. How are you going to represent flows? what type of data structure will you use?99
6. How are you going to ensure that data structures in your program will not be modified concurrently?100
7. How many convars are you going to use? For each convar:101
(a) Describe the condition that the convar will represent.102 (b) Which mutex is associated with the convar? Why?103 (c) What operation should be performed once pthread cond wait() has been unblocked and re-acquired the104 mutex?105
8. In 25 lines or less, briefly sketch the overall algorithm you will use. You may use sentences such as:106
If a flow finishes transmission, release trans mutex.107
4 Submission Requirements (Due: 23.55 pm, Nov. 4, 2016108
1. The name of the submission file must be p2.tar.gz, which contains all your files, including Makefile, source109 code, your input file, readme, design document.110
2. Your document must be in pdf file format. Other file format or handwriting will not be accepted.111
Note: We may test your code with our own input file following the format described in Section 2.2,

6 Miscellaneous117
6.1 Manual Pages118
Be sure to study the man pages for the various functions to be used in the assignment. For example, the man page119 for pthread create can be found by typing the command:120
$ man pthread create121
At the end of this assignment you should be at least familiar with the following functions:122
1. File access functions:123
(a) atoi124 (b) fopen125 (c) feof126 (d) fgetc and fgets127 (e) fclose128
2. Thread creation functions:129
(a) pthread create130 (b) pthread exit131
4
(c) pthread join132
3. Mutex manipulation functions:133
(a) pthread mutex init134 (b) pthread mutex lock135 (c) pthread mutex unlock136
4. Condition variable manipulation functions:137
(a) pthread cond init138 (b) pthread cond wait139 (c) pthread cond broadcast140 (d) pthread cond signal141
It is absolutely critical that you read the man pages, and attend the tutorials.142 Your best source of information, as always, is the man pages.143 For help with posix threads:144
http://www.opengroup.org/onlinepubs/007908799/xsh/pthread.h.html145
A good overview of pthread can be found at: https://computing.llnl.gov/tutorials/pthreads/146
6.2 Important Notes147
We want to (re-)emphasize the following points:148
1. You are required to type in your design document. Hand writing will not be accepted.149
2. We will give a time quota of 2 minutes for your program to run on a given input. This time quota is given150 so that non-terminating programs can be killed. So make sure your input file does not include too many long151 flows (e.g., arrive too late or transmit too long). Since your program simulates flows in 10ths of a second, this152 should not be an issue, at all.153
3. It is required that you use relative machine time. This is to avoid cheating with an implementation that154 does not really simulate the flows but instead performs an offline analysis to obtain scheduling results. The155 markers will read your C code to ensure that the pthread library is used as required. Offline analysis means156 that your program does not simulate mutual exclusion and thread synchronization but obtains the output157 based on algorithm analysis. You will get 0 marks if you are caught using offline analysis.158
4. As you progress through your degree, the projects and assignments will continue to become more complicated159 and difficult. It is impossible to describe in detail every possible case/feature in the assignment specification.160 Instead you are expected to apply the techniques you have learned so far in your degree, use common sense,161 and ask questions to lecture instructor or TAs when you “feel” something is unclear. We will announce162 further clarification, if necessary, on Connex. Complaining the specification is unclear at the last minute is not163 acceptable.164
5. You are required to use C. Any other language is not acceptable.165
6. You are required to strictly follow the input file format. Failing to do so will result in the deduction of scores.166
7. Your work will be tested on linux.csc.uvic.ca.167
8. Programming with semaphore is permitted but not recommended. You have been warned that debugging with168 semaphore is much harder.