Consider the C program provided at the end of this document. It is an implementation of a weighted-round-robin (WRR) resource allocation algorithm. The program takes the number of clients (n) and their individual weights, {wi | 1 ≤ i ≤ n} as input and determines a weighted-round-robin schedule for allocating some shared resource to the clients.

The output is a sequence of (repeated) client numbers (from the range 1….n) to be allocated in order, one unit of the shared resource.

1. Show the control-flow graphs for the three procedures in the program.

2. Show the call graph for the program. Include the library functions in your call graph.

3. Provide a test suite that achieves statement coverage, but not branch coverage.

4. Provide a test suite that achieves branch coverage, but not condition coverage. (Treat compound conditions as a single branch point for this purpose.)

5. Provide a test suite that achieves condition and branch coverage. What additional test cases, if any, do you need for MC/DC coverage?

6. Do the above test suites (taken together) achieve loop boundary coverage for all the loops in the program? If yes, identify the test cases that achieve this for each of the loops. If not, provide additional test cases to achieve loop boundary coverage (zero, one, and many times through the loop).

If any of these tests suites are not feasible, justify why it is the case. Feel free to try executing the code (no guarantees here), with any additions that you may need, to check whether your tests achieved the desired level of structural coverage.

In a directed graph with a designated exit node, we say that a node m post-dominates another node n, if m appears on every path from n to the exit node.

Let us write m pdom n to mean that m post-dominates n, and pdom(n) to mean the set of all post-dominators of n, i.e., {m | m pdom n}.

Answer the following, providing justification for each: 1. Does b pdom b hold true for all b?

2. Can both a pdom b and b pdom a hold true for two different nodes a and b?

3. If both c pdom b and b pdom a hold true, what can you say about the relationship between c and a?

4. If both c pdom a and b pdom a hold true, what can you say about the relationship between c and b?

5. How would you use the answer to your previous question to characterize the immediate post-dominator of a node other than the exit node?

(Hint: immediate post-dominator is, in some sense, the "nearest post-dominator" of a node)

6. Suppose the set of post-dominators pdom(n) is known for every successor n of a node m, can we then derive pdom(m)?

7. Cast the computation of pdom(m) in terms of flow equations. What are the gen and kill sets for m? How would you classify the flow analysis: forward or backward, any-path or all-path?

8. Provide an iterative work-list algorithm (see Chapter 6 for examples) for computing the post-dominance relation based on the flow equations.