Quiz 2: Questions

Q2.1.

[10 pts] List all possible outputs for the below program, and explain how each could occur.

public class ThreadExample extends Thread {
    public static void main(String[] args) throws InterruptedException {
        ThreadExample sub = new ThreadExample();
        sub.start();   // kick off 'run'
        sub.doMain();  // simultaneously do 'doMain'
        sub.join();    // 'doMain' is complete; wait for 'run' to complete
        System.out.println(sub.x + " " + sub.y);
    }

    private int x = 0;
    private int y = 3;

    public void run() {
        x = 1;
        y = 4;
    }

    public void doMain() {
        y = 5;
        x = 2;
    }
}
Q2.2.

[12 pts] The below diagram represents an internetwork; each thick solid line represents a single network, with the IP address block as shown (e.g., 10.0.0.0/16). The squares represent routers, each containing two or three Ethernet cards, identified as eth0, eth1, or eth2, configured with the IP address shown.

For the router named chico, in the center, what should the routing table be? Note that each row of the routing table should contain a network specification (or “default”), an Ethernet card identifier, and either the gateway IP address or the word “direct.”

Q2.3.

[10 pts] 74.117.168.0/22 is one CIDR address block owned by University of Arkansas — Fort Smith.

a. What is the network mask for this address block?

b. How many valid IP addresses exist for this block?

Q2.4.

[14 pts] Using shared-memory concurrency, implement a Java class Limit5 whose methods will be called by multiple threads. Each thread will occasionally call waitUntilAvailable, do some work after the method has returned, and then call exit to signal that it is complete. The Limit5 class should ensure that no more than five threads have returned from waitUntilAvailable but not yet called exit. (That is, if five threads are already in this state, and another thread enters waitUntilAvailable, that thread should be stuck in waitUntilAvailable until at least one of the five threads call exit.)

Do not worry about starvation. Of course, your solution should not busy-wait.

public class Limit5 {
    private Object monitor = new Object();


    public void waitUntilAvailable() {


    }

    public void exit() {


    }
}
Q2.5.

[14 pts] Complete the following D function so that when spawned in a separate thread it implements behavior similar to Java's AtomicInteger, whose value starts as indicated in the parameter. The thread should handle any sequence of three types of messages:

  • Given a tid of the requesting thread, it should send the integer's current value to the requesting thread.

  • Given an integer k, it should send increment the current value by k.

  • Given a tid of the requesting thread, an integer expect, and another integer update, it should check whether the current value matches expect. If it does, the current value should change to update and send true to the requesting thread. If it doesn't match, it should do nothing except send false to the requesting thread.

void atomic_integer(int initValue) {

Quiz 2: Solutions

Q2.1.
2 5 x = 1; y = 4; y = 5; x = 2;
1 4 y = 5; x = 2; x = 1; y = 4;
2 4 x = 1; y = 5; y = 4; x = 2;
1 5 y = 4; y = 5; x = 2; x = 1;

The last answer bears some explanation: How could y = 4; happen before x = 1;? In fact, Java allows compilers to reorder code when statements appear to be independent, without considering what might happen with other threads, since considering other threads is intractable and so effectively disables all possible optimizations. These two statements are independent, so the compiler is free to compile them in reverse order — though admittedly there doesn't seem a good reason to do so in this case.

(Another reason that this last answer could come about would be cache coherency: It may be that the value for x written by the run thread makes it into the main/doMain thread's cache, but its value for y does not.)

Q2.2.
networkcardgateway
127.0.0.0/8localdirect
10.0.0.0/16eth1direct
10.1.0.0/16eth0direct
10.2.0.0/16eth010.1.0.2
10.3.0.0/16eth010.1.0.2
10.4.0.0/16eth010.1.0.2
10.5.0.0/16eth110.0.0.3
defaulteth110.0.0.1
(optional)209.65.56.1/21eth110.0.0.1

(The row labeled “optional” is not necessary since it's redundant with the “default” rule, but one could reasonably include it in the answer.)

Q2.3.

a. 255.255.252.0

b. 1,022 (232 − 22 − 2 = 210 − 2 = 1,024 − 2)

Q2.4.
public class Limit5 {
    private Object monitor = new Object();
    private int activeCount = 0;

    public void waitUntilAvailable() {
        synchronized (monitor) {
            while (activeCount < 5) {
                try { monitor.wait(); } catch (InterruptedException e) { }
            }
            activeCount++;
        }
    }

    public void exit() {
        synchronized (monitor) {
            activeCount--;
            monitor.notifyAll();
        }
    }
}
Q2.5.
void atomic_integer(int initValue) {
    int current = initValue;
    while (true) {
        receive(
            (Tid requestor) {
                send(requestor, current);
            },
            (int to_add) {
                current += to_add;
            },
            (Tid requestor, int expect, int update) {
                if (current == expect) {
                    current = update;
                    send(requestor, true);
                } else {
                    send(requestor, false);
                }
            }
        );
    }
}