Description
1 Introduction
5 You have survived the first programming challenge: building a functional Shell interpreter. Good job! However, you
6 did not handle task scheduling but instead depended on the host operating system to do the job.
7 In this assignment, you need to face the second programming challenge: implementing a task scheduler. You will
8 learn how to use the three programming constructs provided by the posix pthread library:
9 1. threads
10 2. mutexes
11 3. condition variables (convars)
12 to do so. Your goal is to construct a simulator of a router (in a broad sense, a router is a computer anyway) to
13 schedule the transmission of multiple traffic flows. The scheduler is called Multi-Flow Scheduler (MFS).
14 As shown in Figure 1, n flows to the router should be transmitted via its output interface. Each flow is allocated
15 to a dedicated queue. Assume that the router has only one output interface, which must be shared by the flows. To
16 simplify your job, we assume flows are given before hand and their description is stored in a file (refer to Section 2.2).
17 You will use threads to simulate the flows arriving and waiting for transmission, and your program will schedule
18 these flows to meet the requirements in Section 2.3.
19 2 Flows
20 2.1 Properties of Flows
21 Each flow, which will be simulated by a thread, has the following attributes:
22 1. Arrival Time: It indicates when the flow will arrive.
23 2. Transmission Time: It indicates the time required to transmit the flow (i.e., from the time when the flow
24 is scheduled to transmit to the time when its transmission is over). We assume non-preemptive scheduling,
25 meaning that when a flow is transmitting, other flows with a higher priority cannot interrupt its transmission.
MFS
Q1
Q2
Qn
Figure 1: The multi-flow scheduling system
1
26 3. Priority: It is an integer number between 1 (inclusive) and 10 (inclusive), indicating the priority of the flow.
27 A larger number means a lower priority.
28 All times are measured in 10ths of a second. The times will be simulated by having your threads, which represent
29 flows, to call usleep() for the required amount of time.
30 2.2 The Format of Input File
31 Your program (MFS) will accept one parameter on the command line:
32 MFS flow.txt
33 where flow.txt is the name of the input file.
34 2.2.1 File Format
35 The input file is a text file and has a simple format. The first line contains the number of flows that will be simulated.
36 After that, each line contains the information about a single flow, such that:
37 1. The first character specifies the unique number of the flow.
38 2. A colon(:) immediately follows the unique number of the flow.
39 3. Immediately following is an integer that indicates the arrival time of the flow.
40 4. A comma(,) immediately follows the previous number.
41 5. Immediately following is an integer that indicates the transmission time of the flow.
42 6. A comma(,) immediately follows the previous number.
43 7. Immediately following is an integer that indicates the priority of the flow.
44 8. A newline (\n) ends a line.
45 To not kill yourself by checking the false input file, you should build a correct input file for your own test. We
46 will not test your code with an input file that does not comply with the above format.
47 2.2.2 An Example
48 The following file specifies three flows.
49 3
50 1:3,60,3
51 2:6,70,1
52 3:3,50,3
53 The flow specifications are listed in the following table:
Flow No. Arrival time Transmission time Priority
1 0.3s 6s 3
2 0.6s 7s 1
3 0.3s 5s 3
54
2
55 2.3 Simulation Rules
56 The rules enforced by the MFS are:
57 1. Only one flow is on transmission at any given time.
58 2. When a flow arrives, the arriving flow starts transmission if no other flow is on transmission; otherwise, the
59 arriving flow must wait.
60 3. When multiple flows arrive at the same time and no other flow is on transmission, the arriving flow with
61 the highest priority starts its transmission. If they have the same priority, the one that has the smallest
62 transmission time starts its transmission. If there is still a tie, the one that appears first in the input file starts
63 its transmission first.
64 4. When a flow finishes its transmission, all waiting flows compete for next transmission according to the following
65 rules:
66 (a) The one with the highest priority start its transmission first.
67 (b) If there is a tie at the highest priority, the one whose arrival time is the earliest start its transmission first.
68 (c) If there is still a tie, the one that has the smallest transmission time starts its transmission first.
69 (d) If there is still a tie, the one that appears first in the input file starts its transmission first.
70 2.4 Output
71 Your simulation is required to output all events and state changes showing the internal behavior of MFS. The
72 messages must include, but are not limited to:
73 1. A flow arrives
74 2. A flow waits for the completion of another transmitting flow.
75 3. A flow starts transmission
76 4. A flow finishes its transmission
77 You must:
78 1. print the arrival of each flow using the following format string to show the flow attributes:
79 “Flow %2d arrives: arrival time (%.2f), transmission time (%.1f), priority (%2d). \n”
80 2. print the ID of the waiting flow and the ID of the waited flow using the format string:
81 “Flow %2d waits for the finish of flow %2d. \n”
82 3. print the ID of the flow that starts its transmission and the time when it starts transmission using the format
83 string:
84 “Flow %2d starts its transmission at time %.2f. \n”
85 4. print the ID of the flow that finishes its transmission and the time when it finishes transmission using the
86 format string:
87 “Flow %2d finishes its transmission at time %d. \n”
88 Note that the output of times (including arrival time, the time when a flow starts transmission, the time when
89 a flow finishes its transmission) is relative machine time, calculated by the machine time when the output event
90 occurs minus the machine time when the simulation starts. Therefore, the output of the times may not exactly
91 matches (but should be close to) the results with manual calculation.
3
92 3 Submission: Deliverable 1 (Design Due: 23:59 pm, June 11, 2012)
93 You will write a design document which answers the following questions. It is recommended that you think through
94 the following questions very carefully before answering them.
95 Unlike Assignment 1, debugging will be harder after the basic design has been coded. Therefore, it is very
96 important to ensure that the basic design is correct. So think about the following carefully and then write down the
97 answers.
98 1. How many threads are you going to use? Specify the task that you intend each thread to perform.
99 2. Do the threads work independently? Or, is there an overall “controller” thread?
100 3. How many mutexes are you going to use? Specify the operation that each mutex will guard.
101 4. Will the main thread be idle? If not, what will it be doing?
102 5. How are you going to represent flows? what type of data structure will you use?
103 6. How are you going to ensure that data structures in your program will not be modified concurrently?
104 7. How many convars are you going to use? For each convar:
105 (a) Describe the condition that the convar will represent.
106 (b) Which mutex is associated with the convar? Why?
107 (c) What operation should be performed once pthread cond wait() has been unblocked and re-acquired the
108 mutex?
109 8. In 25 lines or less, briefly sketch the overall algorithm you will use. You may use sentences such as:
110 If a flow finishes transmission, release trans mutex.
111 The marker will not read beyond 25 lines.
112 Note: You will submit the design with connex, and you are required to type in your document and submit it in
113 pdf file format. Other file format or handwriting will not be accepted.
114 4 Submission: Deliverable 2 (Code Due: 3:30 pm, June 29, 2012)
115 The code is submitted through connex. The tutorial instructor will give the detailed instruction in the tutorial.
116 4.1 Submission Requirements
117 1. The name of the submission file must be p2.tar.gz
118 2. p2.tar.gz must contain all your files in a directory named p2
119 3. Inside the directory p2, there must be a Makefile.
120 4. Invoking make on it must result in an executable named MFS being built, without user intervention.
121 5. You may not submit the assignment with a compiled executable and/or object (.o) files.
122 6. Inside the directory p2, there must be an input file following the format described in Section 2.2, although we
123 will test you code using our own input file.
124 5 Plagiarism
125 This assignment is to be done individually. You are encouraged to discuss the design of the solution with your
126 classmates, but each student must implement their own assignment. The markers may submit your code to an
127 automated plagiarism detection service.
4
128 6 Miscellaneous
129 6.1 Manual Pages
130 Be sure to study the man pages for the various functions to be used in the assignment. For example, the man page
131 for pthread create can be found by typing the command:
132 $ man pthread create
133 At the end of this assignment you should be at least familiar with the following functions:
134 1. File access functions:
135 (a) atoi
136 (b) fopen
137 (c) feof
138 (d) fgetc and fgets
139 (e) fclose
140 2. Thread creation functions:
141 (a) pthread create
142 (b) pthread exit
143 (c) pthread join
144 3. Mutex manipulation functions:
145 (a) pthread mutex init
146 (b) pthread mutex lock
147 (c) pthread mutex unlock
148 4. Condition variable manipulation functions:
149 (a) pthread cond init
150 (b) pthread cond wait
151 (c) pthread cond broadcast
152 (d) pthread cond signal
153 It is absolutely critical that you read the man pages, and attend the tutorials.
154 Your best source of information, as always, is the man pages.
155 For help with posix threads:
156 http://www.opengroup.org/onlinepubs/007908799/xsh/pthread.h.html
157 A good overview of pthread can be found at: http://www.llnl.gov/computing/tutorials/pthreads/
158 6.2 Important Notes
159 We want to (re-)emphasize the following points:
160 1. You are required to type in your design document. Hand writing will not be accepted.
161 2. We will give a time quota of 2 minutes for your program to run on a given input. This time quota is given
162 so that non-terminating programs can be killed. So make sure your input file does not include too many long
163 flows (e.g., arrive too late or transmit too long). Since your program simulates flows in 10ths of a second, this
164 should not be an issue, at all.
5
165 3. It is required that you use relative machine time. This is to avoid cheating with an implementation that
166 does not really simulate the flows but instead performs an offline analysis to obtain scheduling results. The
167 markers will read your C code to ensure that the pthread library is used as required. Offline analysis means
168 that your program does not simulate mutual exclusion and thread synchronization but obtains the output
169 based on algorithm analysis. You will get 0 marks if you are caught using offline analysis.
170 4. As you progress through your degree the projects and assignments will continue to become more complicated
171 and difficult. It is impossible to describe in detail every possible case/feature in the assignment specification.
172 Instead you are expected to apply the techniques you have learned so far in your degree, use common sense, and
173 ask questions to lecture instructor or TAs when something is unclear. We will announce further clarification,
174 if necessary, on Connex. Complaining the specification is unclear at the last minute is not acceptable.
175 5. You are required to use C. Any other language is not acceptable.
176 6. You are required to strictly follow the input file format. Failing to do so will result in the deduction of scores.
177 7. You should use the Linux machines in ECS242 to test your work.
178 8. Programming with semaphore is permitted but not recommended. You have been warned that debugging with
179 semaphore is much harder.
180 7 Marking
181 We will mark your design document and your code submission.
182 7.1 Design Document (10% of this assignment)
183 You are required to answer all questions listed in Section 3. Your design will be marked based on the clear and
184 correct logic and the correctness of your algorithm.
185 7.2 Code Submission(90% of this assignment)
186 7.2.1 Functionality
187 1. Your MFS must correctly schedule the flow transmissions, with our own test files. We will not disclose all test
188 files before the final submission. This is very common in software engineering.
189 2. You are required to catch return errors of important function calls, especially when a return error may result
190 in the logic error or malfunctioning of your program.
191 3. Your program must output at least the information described in Section 2.4.
192 7.2.2 Code Quality
193 We cannot specify completely the coding style that we would like to see but it includes the following:
194 1. Proper decomposition of a program into subroutines (and multiple source code files when necessary)—A 1000
195 line C program as a single routine would fail this criterion.
196 2. Comment—judiciously, but not profusely. Comments also serve to help a marker, in addition to yourself. To
197 further elaborate:
198 (a) Your favorite quote from Star Wars or Douglas Adams’ Hitch-hiker’s Guide to the Galaxy does not count
199 as comments. In fact, they simply count as anti-comments, and will result in a loss of marks.
200 (b) Comment your code in English. It is the official language of this university.
201 3. Proper variable names—leia is not a good variable name, it never was and never will be.
6
202 4. Small number of global variables, if any. Most programs need a very small number of global variables, if any.
203 (If you have a global variable named temp, think again.)
204 5. The return values from all system calls and function calls listed in the assignment specification
205 should be checked and all values should be dealt with appropriately.
206 If you are in doubt about how to write good C code, you can easily find
207 http://www.chris-lott.org/resources/cstyle/.
208 The http://www.chris-lott.org/resources/cstyle/indhill-annot.html is an excellent short style guide.
209 7.3 Detailed Test Plan
210 The detailed test plan for the code submission is as follows.
Components Weight
Make file 1
Input file 1
Normal cases 4
Priority tie 2
Arrival time tie 2
Transmission time tie 2
All tie 2
Special cases (illegal values) 1
Output format 1
Catch system call return values 1
Comments (functional decomposition) 2
Code style 1
Critical sections 2
Readme 1
Total Weight 23
211
212 Note that a score of 23/23 means that you obtain 90% (Section 7.2) of this assignment. If that is the case,
213 congratulations!
214 Last but not the least, please read this document carefully. TAs and the lecture instructor will not respond for
215 questions or appeals that have been clearly explained in this document. If you are not sure, confirm with the course
216 instructor.
7
