Multi-threading - Token Bucket Emulation in C

[ This content is protected and may not be shared, uploaded, or distributed. ]

This spec is private (i.e., only for students who took or are taking CSCI 402 at USC).0You do not have permissions to display this spec at a public place (such as a public bitbucket/github).0You also do not have permissions to display the code you write to implementation this spec at a public place0since your code was written to implement a private spec. (If a prospective employer asks you to post your0code, please tell them that you do not have permissions to do so; but you can send them a private copy.)

To download the spec below in one command (so you can make a backup of the spec in case the class web server is not available0due to network or server problem), do the following inside a terminal in Ubuntu 16.04 (preferable in an empty directory)0to make a quick and dirty (may be incomplete) backup of our spec:

wget -r -l 1 --user=USERID --password=PASSWORD http://merlot.usc.edu/cs402-f22/projects/warmup2/index.html

where USERID and PASSWORD are the user ID and password used to access protected content from our class web site.

Then type the following in the terminal:

firefox merlot.usc.edu/cs402-f22/projects/warmup2/index.html

Please remember that I do update the spec occasionally. You should ONLY look at your backup copy when0the class web site is unavailable.

Assignment Description

(Please check out the Warmup 2 FAQ before0sending your questions to the TAs, the course producers, or the instructor.)

In this assignment, you will emulate/simulate a traffic shaper0that transmits/services packets controlled by a token bucket filter depicted below0using multi-threading within a single process.0If you are not familiar with pthreads, you should read Chapter 2 of our0required textbook.

IMPORTANT:0Please note that this assignment is posted before all the0background materials (e.g., Unix signals) have been covered in lectures.0If you do not want to learn about these components on your own0(by learning from the textbook), please delay starting this project until0they are covered in class. There will be plenty of time to implement this project after the relevant topics are covered in class. If you don't want to0wait and don't want to learn about Unix signals and stuff on your own, I would strongly0recommend that you do this assignment in two steps. First, you write your0code to do the emulation without any <Ctrl+C>-handling code. By the time you0get this part to work perfectly, we would have covered everything you need0to finish the assignment. Then you follow the recommendations in the lecture to0add <Ctrl+C>-handling code.



















Figure 1: A system with a token bucket filter.
Figure 1 above depicts the system you are required to emulate.0The token bucket has a capacity (bucket depth) of B tokens.0Tokens arrive into the token bucket according to an unusual arrival process0where the inter-token-arrival time between two consecutive tokens is 1/r.0We will call r the token arrival rate0(although technically speaking, it's not exactly the token arrival rate;0please understand that this is quite different from saying that the tokens0arrive at a constant rate of r).0Extra tokens (overflow) would simply disappear if the token bucket is full.0A token bucket, together with its control mechanism, is referred to as a token bucket filter.

Packets arrive at the token bucket filter according to an unusual arrival process0where the inter-arrival time between two consecutive packets is 1/lambda.0We will call lambda the packet arrival rate0(although technically speaking, it's not exactly the packet arrival rate;0please understand that this is quite different from saying that the packets0arrive at a constant rate of lambda).0Each packet requires P tokens in order for it to be eligiable for transmission.0(Packets that are eligiable for transmission are queued at the Q2 facility.)0When a packet arrives, if Q1 is not empty,0it will just get queued onto the Q1 facility.0(Please note that, in this case, you do not have to check if there is0enough tokens in the bucket so you can move the packet at the head of0Q1 into Q2 and you need to understand why you do not0need to perform such a check.)0Otherwise, it will check if the token bucket has P or more tokens in it.0If the token bucket has P or more tokens in it,0P tokens will be removed from the token bucket and0the packet will join the Q2 facility0(technically speaking, you are required to first add the0packet to Q1 and timestamp the packet, remove the0P tokents from the token bucket and the packet from0Q1 and timestamp the packet, before0moving the packet into Q2),0and wake up the servers in case they are sleeping.0If the token bucket does not have enough tokens, the packet gets queued into the0Q1 facility.0Finally, if the number of tokens required by a packet is larger than the bucket depth,0the packet must be dropped (otherwise, it will block all other packets that follow it).

The transmission facility (denoted as S1 and S20in the above figure and they are referred to as the "servers")0serves packets in Q2 in the first-come-first-served order and0at a transmission/service rate of mu per second. When a server becomes0available, it will dequeue the first packet from Q2 and start0transmitting/servicing the packet. When a packet has received 1/mu seconds of service,0it leaves the system. You are required to keep the servers as busy as possible.

When a token arrives at the token bucket, it will add a token0into the token bucket. If the bucket is already full, the token0will be lost. It will then check to see if Q1 is empty.0If Q1 is not empty, it will see if there is enough tokens0to make the packet at the head of Q1 be eligiable for transmission0(packets in Q1 in also served in the first-come-first-served order).0If it does, it will remove the corresponding number of0tokens from the token bucket, remove that packet from Q1 and move it into Q2, and wake up the servers in case they0are sleeping. It will then check the packet that is now at the head of Q10to see if it's also eligiable for transmission, and so on.

Technically speaking, the "servers" are not part of the "token bucket filter".0Nevertheless, it's part of this assignment to emulation/simulation the severs0because the servers are considered part of the "system" to be emulated.0(For the purpose of this spec, we will use the term "emulation" and "simulation" interchangeably.)

Our system can run in only one of two modes.

Deterministic : In this mode, all inter-arrival times are equal to01/lambda seconds and all service times are equal to01/mu seconds (both these values must be rounded to the nearest millisecond), and all packets require exactly0P tokens.0If 1/lambda is greater than 10 seconds, please use an inter-arrival time of 10 seconds.0If 1/mu is greater than 10 seconds, please use an service time of 10 seconds.

Trace-driven : In this mode, we will drive the emulation0using a trace specification file (will be referred to as a "tsfile"). Each line in the0trace file specifies the inter-arrival time of a packet,0the number of tokens it need in order for it to be eligiable0for transmission, and its service time.0(Please note that in this mode, it's perfectly fine if an inter-arrival time or0a service time is greater than 10 seconds.)0If you are running in the trace-drive mode, you must not validate or read the entire tsfile before0you start your simulation.

In either mode, if 1/r is greater than 10 seconds, please use an0inter-token-arrival time of 10 seconds.0Otherwise, please round the inter-token-arrival time to the nearest millisecond.

Your job is to emulate the packet and token arrivals,0the operation of the token bucket filter, the first-come-first-served queues Q1 and Q2,0and servers S1 and S2.0You also must produce a trace of your0emulation for every important event occurred in your0emulation. Please see more details0below for the requirements.

You must use:

one thread for packet arrival

one thread for token arrival

one thread for each server


You must not use one thread for each packet.

In addition, you must use at least0one mutex to protect Q1, Q2, and the token bucket.0(It is recommended that you use exactly one mutex to protect Q1,0Q2, and the token bucket.)

Finally, Q1 and Q2 must have infinite0capacity (i.e., you should use My402List0from warmup assignment #1 to implement them and0not use arrays).
We will not go over the slides for this0assignment in class. Although it's important that you are familiar0with it. Please read it over. If you have questions, please e-mail the instructor.

Compiling

Please use a Makefile so that when the grader simply enters:

make warmup2

an executable named warmup2 is created (minor variation is permitted0if you document it).0Please make sure that your submission conforms to0other0general compilation requirements0and README requirements.

Commandline

The command line syntax (also known as "usage information") for warmup2 is as follows:

warmup2 [-lambda lambda] [-mu mu] [-r r] [-B B] [-P P] [-n num] [-t tsfile]

Square bracketed items are optional.0You must follow the UNIX convention that commandline options0can come in any order. (Note: a commandline option is a0commandline argument that begins with a - character in a0commandline syntax specification.)0Unless otherwise specified,0output of your program must go to stdout and0error messages must go to

stderr.

The lambda, mu, r, B, and0P parameters all have obvious meanings (according to0the description above).0The -n0option specifies the total number of packets to arrive. If the -t option is specified, tsfile0is a trace specification file that you should use0to drive your emulation. In this case, you should ignore0the -lambda, -mu, -P,0and -n commandline options and run your emulation in the0trace-driven mode.0You may assume that tsfile conforms to the tracefile format specification. (This means that0if you detect an error in this file, you may simply print an error0message and call exit(). There is no need to perform error recovery.)0If the -t option is not used, you should run your emulation0in the deterministic mode.

The default value (i.e., if it's not specified in a commandline0option) for lambda is 1 (packets per second),0the default value for mu is 0.35 (packets per second),0the default value for r is 1.5 (tokens per second),0the default value for B is 10 (tokens),0the default value for P is 3 (tokens), and0the default value for num is 20 (packets).0B, P, and num must be positive integers0with a maximum value of 2147483647 (0x7fffffff).0lambda, mu, and r must be positive real numbers.

Running Your Code and Program Output

The emulation should go as follows. At emulation time 0,0all 4 threads (arrival thread, token depositing thread,0and servers S1 and S2 threads)0got started. The arrival thread would sleep so that it can0wake up at a time such that the inter-arrival time of the first0packet would match the specification (either according to0lambda or the first record in a tracefile). At the same time,0the token depositing thread would sleep so that0it can wake up at a time such that the inter-token-arrival time between0consecutive tokens is 1/r seconds and would try to0deposit one token into the token bucket each time it wakes up.0The actual arrival time of the first packet p1 is denoted as time T1,0the actual arrival time of the 2nd packet p2 is denoted as time T2, and so on.

As a packet or a token arrives, or as a server becomes free,0you need to follow the operational rules of the token bucket filter.0Since we have four threads accessing shared data structures,0you must use the tricks you learned from Chapter 2 related lectures.0Please also check out the slides for this0assignment for the skeleton code for these threads.


You are required to produce a detailed trace for every important0event occurred during the emulation and every such event must be timestamped.0Each line in the trace must correspond to one of the following situations:

If a packet is served by a server (server S1 is assumed below for illustration),0there must be exactly 7 output lines that correspond to this packet.0They are:


p1 arrives, needs 3 tokens, inter-arrival time = 503.112ms0

p1 enters Q1

p1 leaves Q1, time in Q1 = 247.810ms, token bucket now has 0 token0

p1 enters Q2

p1 leaves Q2, time in Q2 = 0.216ms0

p1 begins service at S1, requesting 2850ms of service0

p1 departs from S1, service time = 2859.911ms, time in system = 3109.731ms

Please note the following:

The value printed for "inter-arrival time" must equal to the timestamp of the "p1 arrives" event minus the timestamp of the "arrives" event for the previous packet.

The value printed for "time in Q1" must equal to0the timestamp of the "p1 leaves Q1" event minus the timestamp of the "p1 enters Q1" event.

The value printed for "time in Q2" must equal to0the timestamp of the "p1 leaves Q2" event minus the timestamp of the "p1 enters Q2" event.

The value printed for "requesting ???ms of service" must be the requested service time (which must be an integer) of the corresponding packet.

The value printed for "service time" must equal to0the timestamp of the "p1 departs from S1" event minus the timestamp of the "p1 begins service at S1" event0(and it should be larger than the requested service time printed for the "begin service" event).

The value printed for "time in system" must equal to0the timestamp of the "p1 departs from S1" event minus the timestamp of the "p1 arrives" event.

If a packet is dropped, you must print:


p1 arrives, needs 3 tokens, inter-arrival time = 503.112ms, dropped

Please note that the value printed for "inter-arrival time" must equal to0the timestamp of the "p1 arrives" event minus the timestamp of the "arrives" event for the previous packet.

If <Ctrl+C> is pressed by the user, you must print the following (and print a '\n' before it to make sure that it lines up with all the0other trace printouts):


SIGINT caught, no new packets or tokens will be allowed

Please understand that in order for the above to get printed correctly in a trace printout,0using a signal handler to catch signals may not work. You are strongly advised to use0a separate SIGINT-catching thread and uses

sigwait().

If a packet is removed when it's in Q# (Q1 or Q2) because <Ctrl+C> is pressed by the user, you must print:


p1 removed from Q#

If a token is accepted, you must print:


token t1 arrives, token bucket now has 1 token

If a token is dropped, you must print:


token t1 arrives, dropped

When you are ready to start your emulation, you must print:


emulation begins

When you are ready to end your emulation, you must print:


emulation ends

All the numeric values above are made up. You must replace them with the actual0packet number, actual number of tokens required, actual server number, measured inter-arrival time,0measured time spent in Q1, actual number of tokens left behind when a packet is moved into Q2,0measured time spent in Q2, measured service time, and measured time in the system.

The output format of your program must satisfy the following0requirements.

You must first print all the emulation paramters.0Please see the sample printout for what the output must look like.


Whenever a token arrives, you must assign a number to it, and add it to the token bucket.0You must then print its arrival time,0the fact that it has arrived, and the number of tokens in the the token bucket.0Please see the sample printout for what the output must look like.


Whenever a packet arrives, you must assign a number to it.0You must then print its arrival time,0the fact that it has arrived, the number of tokens it needs for transmission,0and the time between its arrival time and the arrival time of the previous packet.0Please see the sample printout for what the output must look like.


You then must append this packet onto Q1. Afterwards, you must then print0the time this packet entered Q1 and the fact that it has entered Q1.0Please see the sample printout for what the output must look like.

Later on, when this packet leaves Q1, it removes the correct number of tokens0from the token bucket. You must then print the time this packet leaves Q1,0the fact that it has left Q1, the amount of time it spent in Q1, and0the number of tokens in the the token bucket.0Please see the sample printout for what the output must look like.

You must then append this packet onto Q2. Afterwards, you must then print0the time this packet entered Q2 and the fact that it has entered Q2.0Please see the sample printout for what the output must look like.

Later on, when this packet leaves Q2 and enters the server,0you must then print which server the packet entered, the time the packet begin service,0the fact that it has begun service, and the amount of time it spent in Q2.0Please see the sample printout for what the output must look like.

When emulation ends, you must print all the necessary statistics.0Please see the sample printout for what the output must look like.0If a particular statistics is not applicable (e.g., will cause divide-by-zero error),0instead of printing a numeric value, please print "N/A" followed by an explanation0(such as, for example, "no packet was served"). Please note that your program output must never contain any "NaN" (which means "not-a-number").


Below is an example what your program output must look like0(please note that the values used here are just a bunch of unrelated0random numbers for illustration purposes):

Emulation Parameters:0

number to arrive = 200

lambda = 2

mu = 0.35

r = 40


(print this line only if -t is not specified)0 (print this line only if -t is not specified)0
B=100






P = 3
(print this line only if
-t is not specified)0

tsfile = FILENAME
(print this line
only if -t is specified)0

0






00000000.000ms: emulation begins0





00000250.726ms: token t1 arrives,
token bucket
now
has 1
token0

00000501.031ms: token t2 arrives,
token bucket
now
has 2
tokens0

00000503.112ms: p1 arrives, needs
3 tokens, inter-arrival time = 503.112ms

00000503.376ms: p1 enters Q10





00000751.148ms: token t3 arrives,
token bucket
now
has 3
tokens0


00000751.186ms: p1 leaves
Q1, time in Q1 = 247.810ms, token bucket now has 0 token0

00000752.716ms: p1 enters
Q20



00000752.932ms: p1 leaves
Q2, time in Q2 = 0.216ms0


00000752.982ms: p1 begins
service
at S1, requesting 2850ms of service0

00001004.271ms: p2 arrives, needs
3 tokens, inter-arrival time = 501.159ms

00001004.526ms: p2
enters
Q10



00001005.615ms: token t4
arrives,
token bucket now has 1
token0

00001256.259ms: token t5
arrives,
token bucket now has 2
tokens0

00001505.986ms: p3
arrives, needs
3 tokens, inter-arrival time = 501.715ms

00001506.713ms: p3
enters
Q10



00001507.552ms: token t6
arrives,
token bucket now has 3
tokens0

00001508.281ms: p2
leaves
Q1, time in Q1 = 503.755ms, token bucket now has 0 token0
00001508.761ms: p2 enters Q20

00001508.874ms: p2 leaves Q2, time in Q2 = 0.113ms0

00001508.895ms: p2 begins service at S2, requesting 1900ms of service0

...0

00003427.557ms: p2 departs from S2, service time = 1918.662ms, time in system = 2423.286ms0

00003612.843ms: p1 departs from S1, service time = 2859.861ms, time in system = 3109.731ms0

...0

????????.???ms: p20 departs from S?, service time = ???.???ms, time in system = ???.???ms0

????????.???ms: emulation ends0

0

Statistics:0

0

average packet inter-arrival time = <real-value>0

average packet service time = <real-value>0

0

average number of packets in Q1 = <real-value>0

average number of packets in Q2 = <real-value>0

average number of packets at S1 = <real-value>0

average number of packets at S2 = <real-value>0

0

average time a packet spent in system = <real-value>0 standard deviation for time spent in system = <real-value>0

0

token drop probability = <real-value>0

packet drop probability = <real-value>0

In the Emulation Parameters section, please print the emulation0parameters specified by the user or the default values mentioned0above. Please do not print the "adjusted" values because0certain parameters are too small. (For example, if lambda is 0.01,0you must print 0.01 and not 0.1.)

After Emulation Parameters section comes the Event Trace section.0The first column there contains timestamps and they correspond to0event times, measured relative to the start of the emulation.0Every emulation event must be timestampted. You need to figure out how to make sure that the timestamp values0look reasonable (e.g., never decrease in value).0Please use 8 digits (with leading zeroes) to the left of the decimal point and 3 digits0after the decimal point for all the timestamps in this column.0All time intervals must be printed in milliseconds with 3 digits0after the decimal point. In the printout, after emulation parameters,0all values reported must be measured values.

In the Statistics section,0the average number of packets at a facility can0be obtained by adding up all the time spent at that facility0(for all relevant packets) divided by the total emulation time.0The time spent in system for a packet is the difference between the time the packet departed0from the server and the time that packet arrived.0The token drop probability is the total number of tokens0dropped because the token bucket was full divided by the total number0of tokens that was produced by the token depositing thread.0The packet drop probability is the total number of packets dropped because the number of tokens required is larger than0the bucket depth divided by the total number0of packets that was produced by the arrival thread.

All real values in the0Emulation Parameters and Statistics sections must be printed with at0least 6 significant digits.0(If you are using printf(), you can use "%.6g".)0A timestamp in the beginning of a line of trace output must be in milliseconds with 8 digits (zero-padded) before the0decimal point and 3 digits (zero-padded) after the0decimal point. Please note that the timestamps must have microsecond resolution.

Please use sample means when you calculated the averages.0If n is the number of sample, this mean that you should divide0things by n (and not n-1).

The unit for time related statistics must be in seconds (and0not milliseconds).

Let X be something you measure.0The standard deviation of X is the square root of the variance of X.0The variance of X is the average of the square of X minus the square0of the average of X.0Please note that we must use the "population variance"0(and not a "sample variance") in our calculation since we have all the data points.0Let E(X) denote the average of X, you can write:

Var(X) = E(X2) - [E(X)]2

When you are keep statistics, you should keep a running average.

Please note that it's very important that the event time in the printout0is monotonically increasing (as shown in the sample printout below).0This can be difficult to achieve when we have multiple threads running in parallel.0But since we are using only one mutex, you can use the following simple (although not super-efficient) trick.0When you are getting the time for an event, you must have the mutex locked, and you must not release the mutex0until you have printed the line of printout that corresponds to that event, i.e., reading the clock and0printing out the event is done in one atomic operation.


If the user presses <Ctrl+C> on the keyboard, you must0stop the arrival thread and the token depositing thread,0remove all packets in Q1 and Q2,0let your server finish transmitting/servicing the current packet, and output statistics.0(Please note that it may not be possible to remove all packets0in Q1 at the instance of signal delivery.0The idea here is that once0signal delivery has occurred, the only packet you should serve0are the ones currently being transmitted/serviced. All other packets should be removed from the system.)

You can divide the packets into 3 categories.

    1. Completed packets: these are the packets that made it all the way to the server and completed service at the server.

    2. Dropped packets: these are the packets arrived into the system but never made it even to Q1 because it needs too many tokens.
    3. Removed packets: these are the packets that got into Q1 to begin with but never made it to the server.

All packets should participate in the calculation of the average packet inter-arrival time and packet drop probability statistics.0Only completed packets should participate in the calculation of the average packet service time statistics.0Only completed packets should participate in the calculation of the average number of packets in Q1/Q2/S1/S2 and0time spent in system statistics.

Finally, when no more packet can arrive into the system, you0must stop the arrival thread as soon as possible. Also, when Q1 is empty and no future packet can arrive into Q1,0you must stop the token depositing thread as soon as possible.

Trace Specification File Format

The trace specification file is an ASCII file containing0n+1 lines (each line is terminated with a "\n")0where n is the total number of packets to arrive.0Line 1 of the file contains a positive integer which corresponds0to the value of n.0Line k of the file contains the inter-arrival time0in milliseconds (a positive integer),0the number of tokens required (a positive integer), and service time in milliseconds (a positive integer)0for packet k-1.0The 3 fields are separated by space or tab characters0(or any combination of any number of these characters).0There must be no leading or trailing space or tab characters in a line.0If a line is longer than 1,024 characters (including the '\n' at the end of a line), it is considered an error.0A sample tsfile for n=30packets is provided. It's content is listed below:

30

2716    2    92530

7721    1    151490

972    3    2614

In the above example,0packet 1 is to arrive 2716ms after emulation starts, it needs 2 tokens0to be eligible for transmission, and its service time should be 9253ms;0the inter-arrival time between packet 2 and 1 is to be 7721ms, it needs 10token to be eligible for transmission, and its service time should be 15149ms;0the inter-arrival time between packet 3 and 2 is to be 972ms, it needs 30token to be eligible for transmission, and its service time should be 2614ms.

In the above example, you should treat these numeric values as "targets"0or your emulation. In your trace output, you need to print what you measured0(i.e., by reading the clock). It should be very unlikely that a0measured inter-arrival time or a measured service time0has exactaly the same value as its corresponding target value.0For example, the inter-arrival time of packet 3 is suppose to be 972 milliseconds.0If the reported actual inter-arrival time between packets 2 and 3 is exactly 972.000 milliseconds,0you should look for bugs in your code! Actually, you should probably get a0different value every time your rerun your emulation.

This file is expected to be error-free. (This means that0if you detect a real error in a tsfile, you must simply print an error0message and call exit() immediately.0You MUST NOT print statistics or attempt to recover from error in this case.)

You are expected to create your own tsfile to test your program.0Make sure you know how to create test cases where you know for sure that packets will be wait in Q1, in Q2, or both.0You should be able to look at your tsfile and predict what will happen0in the trace and verify that your program printout is consistent with your prediction.

Minimum Emulation Time

If you have the fastest machine in the universe that there is no overhead anywhere (i.e., bookkeeping time is zero everywhere, takes zero time to execute any code, etc.)0and it's running a real-time OS that always sleeps exactly the amount of time you ask it to sleep,0what would be the minimum simulation time when you run warmup2? Of course, this depends on the parameters of your simulation. Let's take the0sample tsfile shown above and think about when each packet will leave the simulation if we simply run:
./warmup2 -t tsfile.txt

    1. If there is no overhead anywhere, packet p1 would arrive at exactly 2716ms into the simulation.0At that time, the token bucket should have more than enough tokens for p1 and p1 would start transmitting immediately. Since the transmission time0of p1 is 9253ms, p1 should finish transmission at time 11969ms.

    2. Packet p2 would arrive at exactly 7721ms after the arrival time of packet p1. This means that packet p2 would arrive at time 10437ms.0At that time, the token bucket should have more than enough tokens for p2 and p2 would start transmitting immediately. Since the transmission time0of p2 is 15149ms, p2 should finish transmission at time 25586ms.

    3. Packet p3 would arrive at exactly 972ms after the arrival time of packet p2. This means that packet p3 would arrive at time 11409ms.0At that time, the token bucket should have more than enough tokens for p3. But,0both servers are busy. Therefore, p3 must wait in Q2. The server that transmitted p1 would finish first at time 11969ms0and it would start transmitting p3 as soon as it becomes available. Since the transmission time0of p3 is 2614ms, p3 should finish transmission at time 14583ms.

From the above analysis, simulation will end when p2 is transmitted at time 25586ms. By doing analysis like this,0you can figure out the minimum simulation time of your program. If your program runs faster than that, you would know for sure0that you have a bug in your code! (Of course, if the number of packets is large in an input file, it may not be feasible to do this type of analysis by hand.)

Grading Guidelines

The grading guidelines and grading data (in w2data.tar.gz)0have been made available.0Please run the scripts in the guidelines on a standard 32-bit Ubuntu 16.04 system.0It is possible that there are bugs in the guidelines. If you find0bugs, please let the instructor know as soon as possible.0(Note: the grading guidelines is subject0to change without notice.)

The grading guidelines is the only grading procedure we will use to grade your program. No other grading procedure will be used.0Please note that the grader may use a different set of trace files and commandline arguments when grading your submission.0(We may make minor changes if we discover bugs in the script or things that we forgot to test.)0It is strongly recommended that you run your code through the scripts in the grading guidelines.

For your convenience, a copy of the grading scripts are made available here:

section-A.csh0

section-B.sh0

section-A-all.sh0

section-B-all.sh

(Technically speaking, the scripts above are not "grading scripts" since they are just scripts provided for0your convenience to save you some typing. The grader will not run these scripts when grading.)

After you have download the above shell scripts, please put them in the same directory0as warmup2 and run the following command:

chmod 755 section-*.sh section-*.csh

Please also follow the beginning part of the grading guidelines to unpack0the grading data file (i.e., w2data.tar.gz)0so that the script can work properly.0By the way, please do not run these grading scripts in a shared folder.0For unknown reasons, running the grading scripts from within a shared folder may not work correctly!

A Perl script, "analyze-trace.txt", is made available to help you to debug0your program printout. (I have to name it as if it's a text file. Otherwise, my web server would try0to execute the Perl script.) Please read the comment at the top of the code to see how to use it.0This code only works if your printout is in the right format and each regular packet has 7 lines of printout0(with their timestamps in chronological order) and each dropped packet has 1 line of printout.0If your printout has missing lines in the printout or if the lines are in the wrong order,0you should fix your code and rerun this script!

For this assignments, please always use pthread_cond_broadcast() to wake up server threads.0Please do not use pthread_cond_signal() anywhere in your code. (Yes, this is not the most0efficient way. But since the grader must follow the grading guidelines when grading, this would most likely0get you the most number of points.)

In section (A) of the grading guidelines, each test has a minimum emulation time.0The numbers were obtained using the Minimum Emulation Time analysis mentioned above.0If the running time of your code is too fast or too slow, it means that you have pretty serious bugs in your code and0you need to get them fixed or you will end up losing a lot of points.

Miscellaneous Requirements & Hints

Please read the general programming FAQ if you0need a refresher on file I/O and bit/byte manipulications in C.


You must NOT use any external code segments0to implement this assignment.0You must implement all these functionalities from scratch.


You must NOT use semaphores to implement this assignment.0You must implement thread synchronization using pthread mutex and condition variable.0If you use something like a semaphore, you will lose a lot of points!

Please do not use an array to store all the packets. If you do that, you may end up0losing a lot of points because there will be cases your program will not be able to handle.0Please design your program so that it can handle billions of packets. If you don't know0how to do this, you should start a discussion in the class Google Group.


It's probably not a good idea to keep0timestamps in double because you need to worry about round-off errors when you0add or subtract timestamps. I would strongly recommend that you keep timestamps in struct timeval,0which is the data structure used by gettimeofday() to represent time. This data structure0contain two integers (tv_sec is the number of seconds since 1/1/1970 and tv_usec is the0number of microseconds in the current second) so you don't have to worry about round-off errors.0But you need to worry about carry when you add timestamps and borrow when you subtract timestamps.0To add timestamps, you can use timeradd(), and to subtract timestamps, you can use timersub().0Please do "man timeradd" to see how to use these functions.0You may have to write additional utility functions to do things like displaying timestamps0(for the first column of your trace printout), displaying intervals (for other types of trace printout), etc.


You are required to use0separate compilation0to compile your source code. You must divide your source code into separate source files in a logical way.0You also must not put the bulk of your code in header files!


Please use gettimeofday() to get time information with0a microsecond resolution.0You can use select() or usleep()0(or equivalent) to sleep for a specified number of microseconds.


I do not recommend using a signal handler to catch SIGINT.0You are strongly advised to use a separate SIGINT-catching thread and uses sigwait().


Removing packets are part of the emulation. Therefore, removing of each packet must be timestamped0and you must not terminate your emulation before you have removed all the packets.


If <Ctrl+C> is pressed and you print the "SIGINT caught" message in the printout, you must print0a timestamp for this event.


Your code must not "busy-wait"! "Busy-waiting" means that you have code that's0staying in a tight loop to wait for some condition to become true. Such code0is very unfriendly to the environment you are running your program in. Therefore,0you must not do busy-waiting. If you find a piece of busying waiting code, just0insert "usleep(100000)" inside the loop to sleep for 0.1 second before0checking the condition again. Since it's so easy to not do busy-waiting, if the0grader sees that your code is doing busy-waiting, a lot of points will be deducted.0(Please understand that this is just a quick and dirty fix! The correct way to0wait for some condition to become true is to sleep in a CV queue as discussed in lectures.)


If your code is not doing anything useful (i.e., just waiting for something) and0you run "top" from the commandline on your 32-bit Ubuntu 16.04 system and you0see that your program is taking up one of the top spots in CPU percentages and showing something like more than 0.5%,0there is a good chance that you have busy-waiting code. In this is the case,0run your code under gdb and run "top" in another terminal.0When your code is not doing anything useful and your process starts to show up0in "top", press <Ctrl+C> in gdb. Hopefully, your0program will break inside your busy-waiting loop (use the where command0to see where you are inside gdb)!

Please understand the meaning of inter-arrival time. It means time between0consecutive packets. Let's say the inter-arrival time is 1 second and we are0running in the deterministic mode. Does it mean that0packet 1 will arrive at 1 second after the start of emulation,0packet 2 will arrive at 2 second after the start of emulation,0packet 3 will arrive at 3 second after the start of emulation, etc.?0No. You need to schedule packet 1 to arrive at 1 second after the start of emulation.0But packet 1 will most likely not arrive until a little bit later than 1 second after the start of emulation.0You record the actual time of arrival of packet 1 and you add 1 second to it and that would give you the0expected arrival time of packet 2. Then you can schedule packet 2 to arrive at its expected arrival time.


Here are some additional hints:

For this assignment, you are implementing a time-driven emulation0(and not an event-driven simluation such as the ns-2 in networking).0For an event-driven emulation, you can easily implement this project0using a single thread and an event queue. In a time-driven emulation,0a thread must sleep for the amount of time that it supposes to take to0do the a job. For example, if a server would take 317 milliseconds0to serve a job, it would actually sleep (using select/usleep())0for some period of time so that the packet seem to stay in the0server for 317 milliseconds. Similarly, if the arrival thread needs to wait0634 milliseconds between the arrivals of packets p1 and0p2, it should sleep for some period of time so that it0looks like packet p2 arrives 634 milliseconds after0packet p1 has arrived.


You need to calculate time correctly for the select/usleep()0call mentioned above.0For example, if the arrival thread needs0to wait 634 milliseconds between the arrivals of packets p10and p2. Assuming that it took 45 milliseconds to do0bookkeeping and to enqueue the packet to the queueing system,0you should sleep for 589 milliseconds (and not sleep for 634 milliseconds).0(Please note such calculation does not apply to sleeping for the server thread0but only applies to the packet arrival and token depositing threads.)


Continue with the above example, if it took more than 634 milliseconds to do0bookkeeping and to enqueue the packet to the queueing system, what should you do?0Since you cannot sleep for a negative number of microseconds, you should skip sleeping.0This is "best-effort" emulation. You are not required to hit the target time,0you just need to try your best to match inter-arrival times. When you cannot, you should0still try your best (i.e., 0 is the closest number to a negative number).

Submission

All assignments are to be submitted electronically (including0the required "README" file). To submit your work, you must first0tar all the files you want to submit into a "tarball" and0gzip it to create a gzipped tarfile named warmup2.tar.gz. Then you upload0warmup2.tar.gz to the0Bistro system.0The command you can use to create a gzipped tarfile is:

tar cvzf warmup2.tar.gz MYLISTOFFILES0

ls -l warmup2.tar.gz

Where MYLISTOFFILES is a list of file names that you are submitting0(you can also use wildcard characters if you are sure that it will pick up only the right files).0DO NOT submit your compiled code, just your source code and0README file. Two point will be deducted for each0binary file included in your submission (e.g., warmup2, .o, .gch, core, etc.).0The last command shows you how big the created "warmup2.tar.gz" file is.0If "warmup2.tar.gz" is larger than 1MB in size, the submission server will not accept it.

Please note that the 2nd commandline argument of the tar command above0is the output filename of the tar command. So, if you omit0warmup2.tar.gz above, you may accidentally replace one of your files with0the output of the tar command and there is no way to recover the lost file (unless you have made a backup copy).0So, please make sure that the first commandline argument is cvzf and the 2nd commandline argument0is warmup2.tar.gz.

A w2-README.txt template file is provided here.0You must save it as your w2-README.txt file and0follow the instructions in it to fill it out with appropriate information and include it in your submission.0You must not delete a single line from w2-README.txt.0Please make sure that you satisfy all the README requirements.

Here is an example commands for creating your warmup2.tar.gz file:

tar cvzf warmup2.tar.gz Makefile *.c *.h w2-README.txt

If you use an IDE, you need to modify the commands above so that you include ALL0the necessary source files and subdirectories and make sure you have not forgotten to0include a necessary file in order for the grader to compile your code on a "clean" system.

You should read the output of the above commands carefully to make sure0that warmup2.tar.gz is created properly.0If you don't understand the output of the above commands, you need to learn0how to read it! It's your responsibility to ensure that0warmup2.tar.gz is created properly.

To check the content of warmup2.tar.gz, you can use the following command:

tar tvzf warmup2.tar.gz

Please read the output of the above command carefully to see what files were included in warmup2.tar.gz0and what are their file sizes and make sure that they make sense.

Please enter your USC e-mail address and your submission PIN below. Then click on the Browse button0and locate and select your submission file (i.e., warmup2.tar.gz).0Then click on the Upload button to submit your warmup2.tar.gz.0(Be careful what you click! Do NOT submit the wrong file!)0If you see an error message, please read the dialogbox carefully and fix what needs to be fixed and repeat the procedure.0If you don't know your submission PIN, please visit this web site to have your PIN e-mailed to your USC e-mail address.


When this web page was last loaded, the time at the submission server (merlot.usc.edu) was030Aug2022-16:05:17.

Reload this web page to see the current time on merlot.usc.edu.

USC E-mail:   @usc.edu

Submission PIN:


Event ID (read-only):    merlot.usc.edu_80_1557931083_237


Submission File Full Path:    Choose File    No file chosen


Upload

If the command is executed successfully and if everything checks out,0a ticket will be issued to you to let you know "what" and "when"0your submission made it to the Bistro server. The next web page you0see would display such a ticket and the ticket should look like the sample shown in the submission web page0(of course, the actual text would be different, but the format should be similar).0Make sure you follow the Verify Your Ticket instructions0to verify the SHA1 hash of your submission to make sure what you did not accidentally submit the wrong file.0Also, an e-mail (showing the ticket) will be sent to your USC e-mail address.0Please read the ticket carefully to know exactly "what" and "when"0your submission made it to the Bistro server.0If there are problems, please contact the instructor.

It is extreme important that you also verify your submission0after you have submitted warmup2.tar.gz electronically to make0sure that every you have submitted is everything you wanted us to grade.0If you don't verify your submission and you ended up submit the wrong files, please understand that due to our fairness policy,0there's absolutely nothing we can do.

Finally, please be familiar with the Electronic Submission Guidelines0and information on the bsubmit web page.0
[Last updated Fri Aug 19 2022] 0[Please see copyright regarding copying.]

[0Home0|0Description0|0Lectures0|0Videos0|0Discussions0| Projects0|0Forum0]