COS212
Assignment 5

Department of Computer Science
Deadline: 28/05/2018 at 23:00
General instructions:
• This assignment should be completed individually, no group e ort is allowed.
• Be ready to upload your assignment well before the deadline as no extension will be granted.
• You may not import any of Java’s built-in data structures. Doing so will result in a mark of 0. You may only make use native of arrays where applicable. If you require additional data structures, you will have to implement them yourself.
• If your code does not compile you will be awarded a mark of 0. Only the output of your program will be considered for marks but your code may be inspected for plagiarism.
• Read the entire assignment before you start coding.
• You will be a orded three upload opportunities.
After Completing This Assignment:
Upon successful completion of this assignment you will have implemented your own scheduling model for concurrent applications using a precedence graph.
Background
Precedence graphs are graph structures used in concurrent applications. They have a variety of uses including, but not limited to, scheduling, proving serializability, con ict resolution, etc. This assignment will focus on a particular type of application involving scheduling.
Consider a scenario where multiple entities (people, processors, threads, etc.) may concurrently request service but they can only be sequentially serviced. One way to resolve this would be to issue the entities with numbered tokens which dictate the order in which they will be serviced. There are a number

T1

T2
Figure 1: Precedence graphs T1 and T2
of issues to consider: Firstly, we generally have an upper bound on token numbers and cannot issue tokens up to in nity. Secondly, how do we deal with reaching the upper bound? We cannot simply wrap-around and re-use token numbers indiscriminantly because we risk upsetting the order in which entities would get serviced. Finally, what if entities get tired of waiting and abandon their tokens? The goal here is to set up a system that can issue a limited number of tokens in such a way that one can re-use returned tokens without upsetting the order of service. One can make use of a special type of precedence graph TN to achieve this goal.
The Precedence Graph TN
TN is a directed cyclic graph which can issue at most N tokens at a time. Therefore, the graph T1 can issue a single token, T2, two tokens, T3, three tokens, etc. The graph uses cycles to maintain the order of the tokens among one another and to allow it to recycle returned tokens. Figure 1 shows the precedence graphs T1 and T2 where vertices represent tokens. T1 is trivial and consists of a single vertex. T2 is a cycle with three vertices numbered 0, 1 and 2. T2 is interpreted as follows: The token 0 comes before 1, 1 comes before 2 and 2 comes before 0. Therefore, if two entities have tokens 0 and 1, then 0 needs to be serviced before 1. The wrap-around occurs in the relationship between 0 and 2, where if two entities have those tokens, 2 needs to be serviced before 0. The reason T2 can only issue two tokens at a time is because of the cycle. It needs at least one open vertex. If it issues all three of its available tokens all at once, what would happen?
Graph Dominance
In precedence graphs, a special kind of relationship known as dominance needs to be maintained. Domination ensures order. Consider a graph G with two subgraphs G1 and G2. Subgraph G1 is said to dominate subgraph G2 in G if there is a directed edge from every single vertex in G1 to every single vertex in G2. This relationship between subgraphs becomes important when constructing TN, for N 2. In T2, vertex 0 dominates vertex 2, vertex 2 dominates vertex 1 and vertex 1 in turn dominates vertex 0.

Figure 2: Precedence graphs T2 and T3.
Precedence Graph Construction
Special care needs to be taken when constructing TN, for N 2. It is not simply a case of adding more vertices into the cycle. Doing so opens up the door for a whole host of potential problems, especially once you consider that tokens may be abandoned in any order without being serviced and they need to be reclaimed. The precedence graph TN is recursively constructed through a process called composition. The composition of the graph G from two graphs A and B is denoted as G = A ? B. Composition creates G by replacing every single vertex v ? A with a copy of B and that particular subgraph becomes Bv in G. Furthermore, if in A, v dominated another vertex w, then subgraph Bv should also dominate subgraph Bw in G. TN is recursively constructed through composition using prior graphs and is de ned with the following recursive de nition:
1. T1 is a single vertex representing the token 0.
2. T2 is a simple cycle with three vertices representing the tokens 0, 1 and 2.
3. TN = T2?TN-1, for N 2.
The graphs T1 and T2 are prede ned and subsequent TN’s are obtained by composing T2 and TN-1. Figure 2 shows T2 and T3 side-by-side. T3 was obtained through the composition of two instances of T2. T4 would be obtained with T4 = T2?T3.
The representation in gure 2 is cumbersome both in terms of the number of edges added for each subsequent N and with the labeling of the vertices (there are multiple 0 vertices, for example). To that end, the representation for precedence graphs should be simpli ed and the graph TN should be considered as a collection of subgraphs. Figure 3 uses a new notation to simplify the graph T3. With this notation, rectangles are used to denote subgraphs in T3 (there are 3). Each subgraph is then also labled as the vertices in T2. For example, the rectangle labelled 0 represents subgraph 0, the rectangle labelled 1, the subgraph 1 and so on. Furthermore, the depiction of the number of edges is simpli ed in that if there is an edge from one subgraph (in the rectangles) i to another subgraph j, then it means that subgraph i dominates subgraph j. This also resolves the labelling issue of the vertices. Each vertex is labelled by appending its own label to that of the subgraph (and sub-sub-graph, etc) it appears in. For example, in gure 3, the red vertex now represents the token 00, the blue vertex the token 01, the green vertex the token 12 and the yellow vertex the token 21. Figure 4 uses this simpli ed notation to depict T4 and vertices in this graph are labeled concatenating subgraph labels starting at the highest level (the outer-most rectangles) and moving down to subgraphs until individual vertices are reached.

Figure 3: Simpli ed depiction of precedence graph T3.

Figure 4: Simpli ed depiction of precedence graph T4.
Examples
With graph construction completed, the graph can now be used to issue tokens.
Example 1
Consider the graph T2. The starting vertex ( rst token to be issued) is vertex 0. Entity P1 requests a token and receives the token 0. Next, entity P2 requests a token. The next token issued is obtained by considering both the neighbor of the current vertex and that neighbor’s neighbor. If both are available, then issue the neighbor’s neighbor as the next token. In this case, the current vertex 0’s neighbor 2 and 2’s neighbor 1 are both available. So issue the token 1 to P2. At this point the graph is now full and no more tokens can be issued. If 2 was also issued, then we would end up with deadlock.
The rst token to be considered for service is 0. If 0 is either serviced or abandoned by P1, then 0 becomes available again and the current vertex for service becomes vertex 1. Because the graph now has an additional token available again, a request for a token is accepted and entity P3 requests a token. 1, the current vertex, has its neighbor 0 checked for availability and 0’s neighbor 2 is also checked. Both 0 and 2 are available so issue the neighbor’s neighbor in this case 2 as the next token and the graph is full again. The process keeps on cycling through the graph.
Example 2
Consider the graph T3. The starting subgraph S0 is labeled 0 and the starting vertex is the vertex 00. If a request for a token is made, 00 is issued and this vertex becomes the current vertex. Another request for a token is directed to the same subgraph S0. 00’s neighbor 02 and its neighbor 01 are both available so the next token issued is 01. At this point the S0 is now full (it is an instance of T2). If at most only two tokens are ever requested and serviced, then the process will keep on cycling in S0 (identical to example 1). However, if a third request is made for a token and the previous two have not been serviced or abandoned yet, then you move on to the next subgraph which in this case would be S1 with its starting vertex 10. The process for choosing the next subgraph is similar to choosing the next vertex, i.e. a neighbor-of-a-neighbor approach. Issue 10 as the next token. At this point T3 is now full and no new token can be issued until any of the current tokens are either serviced or abandoned. From this point the example can continue in a number of ways.
Scenario 1
00 is abandoned or serviced and becomes available again and the next token up for service becomes 01. T3 can now issue another token. A request for a token comes in and the current subgraph is S1 so the token needs to be issued from this subgraph. Remember that at this point 01 is still active and should enjoy service before any of the tokens in S1. 10’s neighbor 12 and its neighbor 11 are checked. Both are available so token 11 is issued and T3 becomes full again until 01 is serviced or any of the tokens are abandoned.
Scenario 2
01 is abandoned (it cannot be serviced because 00 is still occupied). A new request for a token is entertained from the current subgraph S1. The next available token is 11. Remember, because 00 is still occupied, it should enjoy service before anything else in S1.
Scenario 3
00 and 01 are abandoned or serviced and become available again but 10 is still occupied. Another request for a token comes in. This scenario plays out the same as the previous two. You remain within S1 because it was not full yet and issuing a token now from S0 would be an error because S0 enjoys precedence over subgraph 1.
Scenario 4
00 is serviced and becomes available again. Next, a request for a token comes in and 11 is issued and S1 is now full. Next, 01 serviced and becomes available again. T3 can now issue another token. A request for a token comes in. S1 is full (both tokens 10 and 11 are claimed). Move on to S2 and issue token 20 as the next token and S2 becomes your current subgraph.
Example 3
Consider the graph T4. The rst subgraph is labelled 0, rst sub-sub graph is labelled 00 and the rst vertex is 000. Therefore we start in subsubgraph S00, which is an instance of T2. A request for a token issues vertex 000. A subsequent request will issue 001 at which point S00 becomes full. A subsequent request for a token moves on to subsubgraph S01 and the token 010 is issued. At this point, the subgraph S0, which is an instance of T3, becomes full. Another request for a token is issued. Because S0 is full, move on to the next subgraph S1 and its rst available subsubgraph S10 and issue the token 100. Now T4 is full and no new tokens can be issued until any of the occupied tokens are abandoned or serviced. If any of the tokens 000, 001 or 010 become available again, then T4 would be able to issue new tokens but the search continues in S10, with 101 being the next available token. If from this point on only a maximum of two tokens are ever issued, the process will cycle in subsubgraph S10.
Your Task
Download the archive assignment5.tar.gz from the course website. This archive contains partial code which you must complete in order to create a precedence graph for a given N. Each method is described in the comments within the partial code given to you. You have to write code to test your implementation in the Main.java le. Your Main.java le will be overwritten for marking purposes.
After your graph has been constructed, it should allow for the issuing and servicing of tickets, account for abandoned tickets and return string representations for traversals of the graph.
You must create your own make le and include it in your submission.
Submission Instructions:
Your Main.java le will be replaced for marking purposes. Once you are satis ed that your program is working, compress all of your code, including a working makefile, into a single archive (either .tar.gz, .tar.bz2 or .zip) and submit it for marking to the appropriate upload link (Assignment 5) before the deadline. Include any additional les containing classes that you’ve written in your archive as well.
References
1. Herlihy, M. and Shavit, N. (2008). The Art of Multiprocessor Programming. Amsterdam: Elsevier/Morgan Kaufmann