multi-threading computer science assignment

CSc 360: Operating Systems (Fall 2020)1

Assignment 2: Airline Check-in System2

Code Due: 11:55 pm, Nov. 6, 20203

1 Introduction4

In this assignment, you need to face the second programming challenge: implementing a task scheduler. You will5 learn how to use the three programming constructs provided by the posix pthread library:6

1. thread7

2. mutex8

3. condition variable (convar)9

to do so. Your goal is to simulate an airline check-in system, called ACS.10 The check-in system includes 2 queues and 4 clerks. One queue (Queue 0) for economy class and the other11

(Queue 1) for business class. We assume that the customers in each queue are served FIFO, and the customers in12 the business class have a higher priority than the customers in the economy class. In other words, when a clerk13 is available, the clerk picks a customer in the business class, if any, to serve, and picks a customer in the economy14 class to serve only if the business class queue is empty. When a clerk is available and there is no customer in any15 queue, the clerk remains idle. We assume that the service time for a customer is known when the customer enters16 the system.17

You will use threads to simulate the customers arriving and waiting for service, and your program will schedule18 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 hand20 and their description is stored in a file (refer to Section 2.2).21

2 Customers22

2.1 Properties of Customers23

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 is27 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 represent29 customers, to call usleep() for the required amount of time.30

2.2 The Format of Input File31

Your program (ACS) will accept one parameter on the command line:32

ACS customers.txt33

where customers.txt is the name of the input file.34

1

2.2.1 File Format35

The input file is a text file and has a simple format. The first line contains the total number of customers that will36 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 040 (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. We47 will not test your code with an input file that does not comply with the above format.48

2.2.2 An Example49

The following file specifies 7 customers50

751

1:0,2,6052

2:0,4,7053

3:0,5,5054

4:1,7,3055

5:1,7,4056

6:1,8,5057

7:0,10,3058

Note that all times are measured in 10ths of a second, and in the above example, the first customer arrives at 0.2s59 and her service time is 6s.60

2.3 Output61

Your simulation is required to output all events and state changes showing the internal behavior of62 ACS. The messages must include, but are not limited to:63

1. A customer arrives: customer ID64

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"72

2

Note that the output of times (including arrival time, the time when a clerk starts serving a customer, the time73 when a clerk finishes a service) is relative machine time, calculated by the machine time when the output event74 occurs minus the machine time when the simulation starts. Therefore, the output of the times may not exactly75 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 in77 the system, (2) the average waiting time of all business-class customers, and (3) the average waiting78 time of all economy-class customers. The waiting time of a customer is defined as from the time when the79 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 Design Document85

You will write a design document which answers the following questions. It is recommended that you think through86 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 very88 important to have a clear design before you start coding. So think about the following carefully and then write down89 the 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 the100 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 are required to type in your document and submit it in pdf file format together with your code. Other104 file format or handwriting will not be accepted.105

4 Submission106

The code and the design document are submitted through connex-->Assignments in one zip file. The tutorial107 instructor will give the detailed instruction in the tutorial.108

3

4.1 Submission Requirements109

1. The name of the submission file must be p2.tar.gz110

2. p2.tar.gz must contain all your files in a directory named p2111

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 we115 will test you code using our own input file.116

7. The design document specified in Section 3.117

5 Plagiarism118

This assignment is to be done individually. You are encouraged to discuss the design of the solution with your119 classmates, but each student must implement their own assignment. The markers may submit your code to an120 automated plagiarism detection service.121

6 Miscellaneous122

6.1 Manual Pages123

Be sure to study the man pages for the various functions to be used in the assignment. For example, the man page124 for pthread create can be found by typing the command:125

$ man pthread create126

At the end of this assignment you should be at least familiar with the following functions:127

1. File access functions:128

(a) atoi129

(b) fopen130

(c) feof131

(d) fgetc and fgets132

(e) fclose133

2. Thread creation functions:134

(a) pthread create135

(b) pthread exit136

(c) pthread join137

3. Mutex manipulation functions:138

(a) pthread mutex init139

(b) pthread mutex lock140

(c) pthread mutex unlock141

4. Condition variable manipulation functions:142

(a) pthread cond init143

4

(b) pthread cond wait144

(c) pthread cond broadcast145

(d) pthread cond signal146

It is absolutely critical that you read the man pages, and attend the tutorials.147 Your best source of information, as always, is the man pages.148 For help with posix threads:149

http://www.opengroup.org/onlinepubs/007908799/xsh/pthread.h.html150

A good overview of pthread can be found at: http://www.llnl.gov/computing/tutorials/pthreads/151

6.2 Important Notes152

We want to (re-)emphasize the following points:153

1. You are required to type in your design document. Hand writing will not be accepted.154

2. We will give a time quota of 3 minutes for your program to run on a given input. This time quota is given155 so that non-terminating programs can be killed. So make sure your input file does not include too many long156 customers (e.g., arrive too late or service time too long). Since your program simulates in 10ths of a second,157 this should not be an issue, at all.158

3. It is required that you use relative machine time. This is to avoid cheating with an implementation that159 does not really simulate the customers but instead performs an offline analysis to obtain results. The markers160 will read your C code to ensure that the pthread library is used as required. Offline analysis means that161 your program does not simulate mutual exclusion and thread synchronization but obtains the output based on162 algorithm analysis. You will get 0 marks if you are caught using offline analysis.163

4. As you progress through your degree the projects and assignments will continue to become more complicated164 and difficult. It is impossible to describe in detail every possible case/feature in the assignment specification.165 Instead you are expected to apply the techniques you have learned so far in your degree, use common sense, and166 ask questions to lecture instructor or TAs when something is unclear. We will announce further clarification,167 if necessary, on Connex. Complaining the specification is unclear at the last minute is not acceptable.168

5. You are required to use C. Any other language is not acceptable.169

6. You are required to strictly follow the input file format. Failing to do so will result in the deduction of scores.170

7. Your work will be tested on linux.csc.uvic.ca. Make sure your code can work on linux.csc.uvic.ca171

8. Programming with semaphore is permitted but not recommended. You have been warned that debugging with172 semaphore is much harder.173

7 Marking174

We will mark your design document and your code submission.175

7.1 Design Document (10% of this assignment)176

You are required to answer all questions listed in Section 3. Your design will be marked based on the clear and177 correct logic and the correctness of your algorithm.178

5

7.2 Code (90% of this assignment)179

7.2.1 Functionality180

1. Your ACS must correctly schedule the customer services, with our own test files. We will not disclose all test181 files before the final submission. This is very common in software engineering.182

2. You are required to catch return errors of important function calls, especially when a return error may result183 in the logic error or malfunctioning of your program.184

3. Your program must output at least the information described in Section 2.3.185

7.2.2 Code Quality186

We cannot specify completely the coding style that we would like to see but it includes the following:187

1. Proper decomposition of a program into subroutines (and multiple source code files when necessary)—A 1000188 line C program as a single routine would fail this criterion.189

2. Comment—judiciously, but not profusely. Comments also serve to help a marker, in addition to yourself. To190 further elaborate:191

(a) Your favorite quote from Star Wars or Douglas Adams’ Hitch-hiker’s Guide to the Galaxy does not count192 as comments. In fact, they simply count as anti-comments, and will result in a loss of marks.193

(b) Comment your code in English. It is the official language of this university.194

3. Proper variable names—leia is not a good variable name, it never was and never will be.195

4. Small number of global variables, if any. Most programs need a very small number of global variables, if any.196 (If you have a global variable named temp, think again.)197

5. The return values from all system calls and function calls listed in the assignment specification198 should be checked and all values should be dealt with appropriately.199

7.3 Detailed Test Plan200

The detailed test plan for the code submission is as follows.201

Components Weight Make file 5 Input file 5

Normal cases 25 Special cases (illegal values) 5

Output format 5 Catch system call return values 5

Correct statistics 15 Comments (functional decomposition) 5

Code style 5 Critical sections 10

Readme 5

Total Weight 90

202

Last but not the least, please read this document carefully. TAs and the lecture instructor will not respond for203 questions or appeals that have been clearly explained in this document. If you are not sure, confirm with the course204 instructor.205

6