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