Description
P2 A Simulator for FIFO Queue
Goals
This assignment is designed to help you:
1. get familiar with multi-threaded programming with Pthread.
2. get familiar with critical section with Pthread mutex.
You are required to implement your solution in C++ (other languages are not allowed). Your
work will be tested on the Linux server cs3103-01.cs.cityu.edu.hk.
11 A good tutorial on pthread could be found at https://computing.llnl.gov/tutorials/
12 pthreads/.
2 Requirements
2.1 Background
15 First-In-First-Out (FIFO) queue has been broadly used in computer and network systems. In this
16 assignment, you are required to simulate a simple case of FIFO queue. The model includes a flow,
17 a queue, and a server. The flow is responsible for generating traffic, measured in terms of token,
18 into the queue. The server tries to empty the queue by fetching a certain number of tokens, if
19 any.
20 In the simple FIFO queueing model, the behavior of flow, queue, and server is summarized
21 as follows.
22 • The flow wakes up periodically with an interval time of flowInterval seconds, where
23 flowInterval is an input parameter. Once waking up, the flow generates a random number
24 of tokens, uniformly distributed in [1, 10], and inserts the tokens to the queue. Each token is
25 assigned a unique sequence number in the increasing order.
We assume that the first token
26 has sequence number 0, and the sequence number will be increased by 1 for each consecutive
27 token. We also assume that the flow, after it wakes up, remembers the history of tokens so
28 that the sequence numbers of generated tokens are always increasing.
29 • The queue temporarily stores the token in the FIFO fashion. The maximum size of the queue
30 is set to 50 tokens. If the queue is full, the incoming tokens will be dropped.
31 • The server wakes up periodically with an interval time of 2 seconds. Once waking up, the
32 server fetches a random number of tokens, uniformly distributed in [1, 20]. Note that if the
33 generated random number is larger than the current number of tokens in the queue, all the
34 tokens in the queue will be fetched.
35 The simulation stops after MaxToken number of tokens have been served, where MaxToken is an
36 input parameter. A token is considered to be served if it is fetched from the queue by the
37 server or it is dropped due to buffer overflow.
2.2 Implementation Requirements
39 Your program, named by SFIFO, should consists of three threads: the main thread, the flow thread,
40 and the server thread. The main thread is responsible for creating the flow thread and the server
41 thread, and then waits for these threads to return. The flow thread simulates the behavior of the
42 flow. The server thread simulates the behavior of the server.
43 Your code must print out useful information, and the output must be formatted as the following table:
Flow Queue Server
Token added Latest sequence number Current Length Token fetched Total Token fetched
aaa bbb ccc
zzz xxx yyy
44
45 where the header of the table (i.e., Flow, Queue, Server, Token added, Last sequence number,
46 Current Length, Token served, Total Token served) is printed by the main thread before cre47 ating the other two threads. The numbers aaa, bbb, and ccc are printed by the flow thread when
48 it wakes up.
The numbers xxx, yyy, and zzz are printed by the server thread when it wakes up.
49 In addition, the number aaa is not the accumulative number but the number of tokens at the
50 current round of flow wake-up; the number bbb is the highest sequence number at the current round
51 of flow wake-up; the number ccc is the queue length after the tokens generated at the current round
52 of flow wake-up have been added into the queue.
The number xxx is not the accumulative number
53 but the number of tokens that will be fetched by the server at the current round of its wake-up;
the
54 number yyy is the total number of tokens that have been fetched by the server; the number zzz is
55 the current queue length after the tokens have been fetched by the server at the current round of
56 server wake-up.
57 Note that at the end of the program, the total number of tokens that have been served is equal
58 to the total number of tokens that have been fetched by the server and the total number of tokens
59 that have been dropped by the queue. As such, at the end of the program, you must print out
60 the total number of tokens have been fetched by the server thread, the total number of tokens that
61 have been generated by the flow thread, and the total number of tokens that have been dropped by
62 the queue.
The output should be:
63 The total number of tokens that have been fetched by the server is eee.
64 The total number of tokens that have been generated by the flow is fff.
65 The total number of tokens that have been dropped by the queue is ggg.
66 where eee, fff, and ggg indicate the corresponding numbers.
67
Because the simulation stops after MaxToken number of tokens have been served, the sum of eee
68 and ggg must equal MaxToken. Nevertheless, fff could be larger than MaxToken.
2
69 The queue is implemented as a data structure, rather than a thread. You need to implement
70 your own queue data structure and its related functions, which means that you cannot
71 use the queue data structure provided by the C/C++ library.
72 Since both the flow thread and the server thread need to access the queue data structure, the
73 code segment for accessing the queue is critical section and must be protected with
74 the pthread mutex lock.
2.3 Prompt for user input
76 Your SFIFO needs to accept two integer inputs, MaxToken as the first and flowInterval as the
77 second, e.g.,
78 $ ./SFIFO 500 2
2.4 Code Quality
80 We cannot specify completely the coding style that we would like to see but it includes the following:
81 1. Proper decomposition of a program into subroutines (and multiple source code files when
82 necessary)—A 500 line program as a single routine won’t suffice.
83 2. Comment—judiciously, but not profusely.
Comments also serve to help a marker, in addition
84 to yourself.
To further elaborate:
85 (a) Your favorite quote from Star Wars or Douglas Adams’ Hitch-hiker’s Guide to the Galaxy
86 does not count as comments. In fact, they simply count as anti-comments, and will result
87 in a loss of marks.
88 (b) Comment your code in English. It is the official language of this university.
89 3. Proper variable names—leia is not a good variable name, it never was and never will be.
90 4. Small number of global variables, if any. Most programs need a very small number of global
91 variables, if any. (If you have a global variable named temp, think again.)
92 5. The return values from all function calls should be checked and all values should
93 be dealt with appropriately.
3 Marking
95 Your program will be tested on our CSLab Linux servers (cs3103-01, cs3103-02, cs3103-03).
96 You should tell TA how to compile and run your code in your readme text file.
97 TAs are not supposed to fix the bugs, either in your source code or in your Makefile.
98 If an executable file cannot be generated and running successfully on our Linux servers, it will
99 be considered as unsuccessful.
100 Any program does not print the output as required in the section 2.2 will be considered as
101 unsuccessful.
102 If the program can be run successfully and output is in the correct form, your program will be
103 graded as the following marking scheme.
3
Table 1: Marking scheme.
Components Weight
Create threads 20%
Thread join 10%
Lock and unlock mutex 20%
Exit thread 10%
Queue structure & related functions 20%
Error handling 10%
programming style and in-program comments 10
4 Submission
105 1. This assignment is to be done individually or by a group of two students. You are encouraged
106 to discuss the high-level design of your solution with your classmates but you must implement
107 the program on your own. Academic dishonesty such as copying another student’s work or
108 allowing another student to copy your work, is regarded as a serious academic offence.
109 2. Each submission consists of three files: a source program file (.cpp file), a readme (.txt) file
110 telling us how to compile your code, a text file containing the possible outputs produced by
111 your program (.txt file), and a Makefile if applicable.
112 3. Use your student ID(s) to name your submitted files, such as 5xxxxxxx.cpp, 5xxxxxxx113 readme.txt, 5xxxxxxx.txt for individual submission, or 5xxxxxxx 5yyyyyyy.cpp, 5xxxxxxx 5yyyyyyy114 readme.txt, 5xxxxxxx 5yyyyyyyy.txt for group submission. Only ONE submission is required
115 for each group.
116 4. Submit the files to Canvas.
117 5. The deadline is 10:00 a.m., 14-MAR (Thu). No late submission will be accepted.
118 Question?
119 Contact Miss ZHANG, Yifan at yif.zhang@my.cityu.edu.hk or your course lecturer.
120 The End
4
