代码代写｜CSCI 402 Warmup Assignment 2 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). You do not  have permissions to display this spec at a public place (such as a public bitbucket/github). You also do not have permissions to display the code you write to implementation this spec at a public place since your code was written to implement a private spec. (If a prospective employer asks you to post your code, 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 available due to network or server problem), do the following inside a terminal in Ubuntu 16.04 (preferable in an empty directory) to 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 when the class web site is unavailable.

Assignment Description

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

In this assignment, you will emulate/simulate a traffic shaper that transmits/services packets controlled by a token bucket filter depicted below using multi-threading within a single process. If you are not familiar with pthreads, you should read Chapter 2 of our required textbook.

IMPORTANT: Please note that this assignment is posted before all the background materials (e.g.,Unix signals) have been covered in lectures. If you do not want to learn about these components on your own (by learning from the textbook), please delay starting this project until they 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 to wait and don’t want to learn about Unix signals and stuff on your own, I would strongly recommend that you do this assignment in two steps. First, you write your code to do the emulation without any <Ctrl+C>-handling code. By the time you get this part to work perfectly, we would have covered everything you need to finish the assignment. Then you follow the recommendations in the lecture to add <Ctrl+C>-handling code.

Figure 1 above depicts the system you are required to emulate. The token bucket has a capacity (bucket depth) of B tokens. Tokens arrive into the token bucket according to an unusual arrival process where the inter-token-arrival time between two consecutive tokens is 1/r. We will call r the token arrival rate (although technically speaking, it’s not exactly the token arrival rate; please understand that this is quite different from saying that the tokens arrive at a constant rate of r).

Extra tokens (overflow) would simply disappear if the token bucket is full. A 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 process where the inter-arrival time between two consecutive packets is 1/lambda. We will call lambda the packet arrival rate (although technically speaking, it’s not exactly the packet arrival rate; please understand that this is quite different from saying that the packets arrive at a constant rate of lambda). Each packet requires P tokens in order for it to be eligiable for transmission. (Packets that are eligiable for transmission are queued at the Q2 facility.) When a packet arrives, if Q1 is not empty, it will just get queued onto the Q1 facility. (Please note that, in this case, you do not have to check if there is enough tokens in the bucket so you can move the packet at the head of Q1 into Q2 and you need to understand why you do not need to perform such a check.) Otherwise, it will check if the token bucket has P or more tokens in it. If the token bucket has P or more tokens in it, P tokens will be removed from the token bucket and the packet will join the Q2 facility (technically speaking, you are required to first add the packet to Q1 and timestamp the packet, remove the P tokents from the token bucket and the packet from Q1 and timestamp the packet, before moving the packet into Q2),and wake up the servers in case they are sleeping. If the token bucket does not have enough tokens, the packet gets queued into the Q1 facility. Finally, if the number of tokens required by a packet is larger than the bucket depth, the packet must be dropped (otherwise, it will block all other packets that follow it).

The transmission facility (denoted as S1 and S2 in the above figure and they are referred to as the “servers“) serves packets in Q2 in the first-come-first-served order and at a transmission/service rate of mu per second. When a server becomes available, it will dequeue the first packet from Q2 and start transmitting/servicing the packet. When a packet has received 1/mu seconds of service, it 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 token into the token bucket. If the bucket is already full, the token will be lost. It will then check to see if Q1 is empty. If Q1 is not empty, it will see if there is enough tokens to make the packet at the head of Q1 be eligiable for transmission (packets in Q1 in also served in the first-come-first-served order). If it does, it will remove the corresponding number of tokens from the token bucket, remove that packet from Q1 and move it into Q2, and wake up the servers in case they are sleeping. It will then check the packet that is now at the head of Q1 to see if it’s also eligiable for transmission, and so on.

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

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

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

simulation.

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

Your job is to emulate the packet and token arrivals, the operation of the token bucket filter, the first-come-first-served queues Q1 and Q2, and servers S1 and S2. You also must produce a trace of your emulation for every important event occurred in your emulation. Please see more details below 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 least one mutex to protect Q1, Q2, and the token bucket. (It is recommended that you use exactly one mutex to protect Q1, Q2, and the token bucket.)

Finally, Q1 and Q2 must have infinite capacity (i.e., you should use My402List from warmup assignment #1 to implement them and not use arrays).

We will not go over the slides for this assignment in class. Although it’s important that you are familiar with 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 permitted if you document it). Please make sure that your submission conforms to other general compilation requirements and 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. You must follow the UNIX convention that commandline options can come in any order. (Note: a commandline option is a commandline argument that begins with a – character in a commandline syntax specification.) Unless otherwise specified,output of your program must go to stdout and error messages must go to stderr.

The lambda, mu, r, B, and P parameters all have obvious meanings (according to the description above). The -n option specifies the total number of packets to arrive. If the -t option is specified,tsfile is a trace specification file that you should use to drive your emulation. In this case, you should ignore the -lambda, -mu, -P, and -n commandline options and run your emulation in the trace-driven mode. You may assume that tsfile conforms to the tracefile format specification. (This means that if you detect an error in this file, you may simply print an error message and call exit().

There is no need to perform error recovery.) If the -t option is not used, you should run your emulation in the deterministic mode.

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

Running Your Code and Program Output

The emulation should go as follows. At emulation time 0, all 4 threads (arrival thread, token depositing thread, and servers S1 and S2 threads) got started. The arrival thread would sleep so that it can wake up at a time such that the inter-arrival time of the first packet would match the specification (either according to lambda or the first record in a tracefile). At the same time, the token depositing thread would sleep so that it can wake up at a time such that the inter-token-arrival time between consecutive tokens is 1/r seconds and would try to deposit one token into the token bucket each time it wakes up. The actual arrival time of the first packet p1 is denoted as time T1, the 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, you need to follow the operational rules of the token bucket filter. Since we have four threads accessing shared data structures, you must use the tricks you learned from Chapter 2 related lectures. Please also check out the slides for this assignment for the skeleton code for these threads.

You are required to produce a detailed trace for every important event occurred during the emulation and every such event must be timestamped. Each 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), there must be exactly 7 output lines that correspond to this packet. They are:

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

p1 enters Q1

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

p1 enters Q2

p1 leaves Q2, time in Q2 = 0.216ms

p1 begins service at S1, requesting 2850ms of service

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 to the 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 to the 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 to the timestamp of the “p1 departs from

S1” event minus the timestamp of the “p1 begins service at S1” event (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 to the 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 to the 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 the other trace printouts):

Please understand that in order for the above to get printed correctly in a trace printout,using a signal handler to catch signals may not work. You are strongly advised to use a 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 actual packet number,actual number of tokens required, actual server number, measured inter-arrival time, measured time spent in Q1, actual number of tokens left behind when a packet is moved into Q2, measured time spent in Q2, measured service time, and measured time in the system.