Test 2: Questions
[12 pts] List all possible outputs for the below program, and explain how each could occur.
public class ThreadExample extends Thread {
private int x = 0;
private int y = 2;
public void run() {
x = 1;
y = 4;
}
public void doMain() {
x += y;
}
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);
}
}
[10 pts] UCA's CIDR address block is 69.196.224.0/19.
a. What is the network mask for this address block?
b. How many valid IP addresses exist for this block?
[14 pts]
Using shared-memory concurrency, implement a Java class that
supports a reading/writing lock, with
three methods: getRead, getWrite, and release.
At any time, this lock will either be in a reading or a writing state;
when in reading state, multiple threads can have a read lock,
but when in writing state, only one thread at a time can have a write lock.
It is eligible to switch between reading and writing states once
nobody holds the lock.
A thread will call getRead, and the method will return once
the lock is in reading state (and the thread calling the method
is allocated a reading lock).
A thread will call getWrite, and the method will return
once the calling thread has reserved the lock while it is in writing state.
Any thread calling release will lead to one less
reservation on the lock.
Do not worry about starvation. Of course, your solution should not busy-wait.
public class ReadWriteLock {
// suggested instance variables - feel free to ignore or add more
private Object monitor = new Object();
private int numReading = 0; // number of read locks acquired
private int numWriting = 0; // number of write locks (0 or 1)
public void getRead() {
}
public void getWrite() {
}
public void release() {
}
}
[12 pts] Suppose we want a D program using message passing for concurrency, where the user can type “begin” to tell a different thread to start displaying the integers starting from 1, with a one-second delay between each number. When the user types “end,” though, the thread should immediately halt its counting.
Without actually writing any code, describe what threads should exist in the D program, when they should be spawned, and what messages should be passed between them to implement the desired behavior.
[14 pts]
Complete the following D function so that when spawned in a
separate thread it implements semaphore-like behavior.
When another thread wants to execute a DOWN request, it
will send a message containing its tid (thread ID) to semaphore,
and it should send a message containing true once the
DOWN request is satisfied.
When another thread wants to execute a UP request,
it will send an integer (assumed 1, but semaphore
can ignore the value).
You will likely want to maintain a queue of waiting threads.
The starter code already creates an empty queue.
To insert, use queue.insertFront(value);
to remove from the back of the queue, use
queue.removeAny(), which returns the value removed;
and to test whether the queue is empty, use queue.empty(),
which returns true or false.
void semaphore(int initValue) {
DList!Tid queue = DList!int(cast(Tid[]) []);
[8 pts] Layer 4 of the OSI model is the “transport layer,” sandwiched between layer 3 (network) and layer 5 (session). What is the purpose of the transport layer?
[10 pts] Modern Ethernet networks typically use two different kinds of cabling. Name each, and identify an advantage of each.
[8 pts] Describe what an ARP proxy does.
[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 gummo, in the upper right corner, 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.”
Test 2: Solutions
The run and
doMain methods would be compiled into the following
instructions.
| A1. | Store 1 into x |
B1. | Load x into a register. | |
| A2. | Store 4 into y |
B2. | Load y into a register. | |
| B3. | Store sum of registers at x. |
We can get five possible results.
- 1: B1, B2, B3, A1, A2
- 2: B1, B2, A1, A2, B3
- 3: A1, B1, B2, A2, B3
- 4: B1, A1, A2, B2, B3
- 5: A1, A2, B1, B2, B3
a. 255.255.240.0
b. 8,094 (232 − 19 − 2 = 213 − 2 = 8,096 − 2 = 8,094)
public class ReadWriteLock {
private Object monitor = new Object();
private int numReading = 0; // number of read locks acquired
private int numWriting = 0; // number of write locks (0 or 1)
public void getRead() {
synchronized (monitor) {
while (numWriting > 0) {
try { monitor.wait(); } catch (InterruptedException e) { }
}
numReading++;
}
}
public void getWrite() {
synchronized (monitor) {
while (numReading > 0 || numWriting > 0) {
try { monitor.wait(); } catch (InterruptedException e) { }
}
numWriting++;
}
}
public void release() {
synchronized (monitor) {
if (numReading > 0) {
numReading--;
} else {
numWriting--;
}
monitor.notifyAll();
}
}
}
We can do this using three threads.
- The first thread simply receives input from the user. This
thread is often blocked on the
readlnfunction. - The second thread is the “manager,” which keeps track of whether the counting should be active and always responds promptly to any query.
- The final thread actually does the counting. It spends much
of its time blocked in the
sleepfunction.
All three threads would be spawned at the beginning. Messages sent include the following.
- When the user-input thread reads a message from the keyboard, it sends a true/false message to the manager informing it of the request (true says that the user requests to begin, false says that the user requests to stop). If this is indeed a change in status, the manager sends the true/false message to the counting thread so that it will restart.
- When the counting thread is ready to step to a new number,
it sends its tid to the manager, who responds with
trueif it should keep going. If it should not keep going, then the manager does not respond (and so the counter thread remains halted) until it is informed of a change in status.
[While explicitly not requested in the question, below is a working program.]
import std.stdio;
import std.concurrency;
import std.string : strip;
import core.thread : Thread;
import core.time : dur;
void main() {
Tid manager = spawn(&manageCount);
while (true) {
string line = strip(readln());
send(manager, line == "begin");
}
}
void manageCount() {
Tid count = spawn(&count, thisTid);
bool isGoing = false;
while (true) {
receive(
(bool input) { // user asks to begin (true) or end (false)
if (input != isGoing) { // ignore duplicate requests
send(count, input);
isGoing = input;
}
},
(Tid counter) { // counter asks whether to keep going
if (isGoing) {
send(count, true); // only respond if we've already started
}
}
);
}
}
void count(Tid manager) {
int cur = 0;
while (true) {
send(manager, thisTid); // should we keep going?
if (receiveOnly!bool()) {
cur++;
writeln(cur);
Thread.sleep(dur!"seconds"(1));
} else {
cur = 0; // reset if we're to stop
}
}
}
void semaphore(int initValue) {
DList!Tid queue = DList!int(cast(Tid[]) []);
int current = initValue;
while (true) {
receive(
(Tid new_tid) { // DOWN request
if (current > 0) { // we can decrement immediately
current--;
send(new_tid, true);
} else {
queue.insertFront(new_tid); // must wait, so into queue
}
},
(int to_add) { // UP request
if (queue.empty()) { // if queue is empty, we increment
current++;
} else { // otherwise we complete a queued DOWN request
Tid old_tid = queue.removeAny();
send(old_tid, true);
}
});
}
}
The network layer specifies how to route between two hosts that are not physically connected. This includes how hosts are identified — i.e., their addresses.
Twisted-pair cables (made of copper, like telephone wires) and fiber optic cables. Twisted-pair cabling is cheaper and easier to work with; fiber optic cables can transport a signal much farther (e.g., for 10Mbit Ethernet, twisted-pair's maximum length is 100m while fiber's maximum is 2000m), is harder to tap, and the signal is not affected by electromagnetic noise.
An ARP proxy is typically a router with multiple Ethernet controllers, which is configured to serve as an ARP proxy on one (or more) of the controllers. Let us suppose that its two controllers are eth0 and eth1, and it is serving as an ARP proxy on eth0. Whenever the router notices an ARP request on eth0's network concerning an IP address that belongs on eth1's network, the router responds on eth0 with eth0's MAC address even though the router is not the actual owner of that IP address. Of course, this means that whoever wants to send a packet to that IP address will now send it to the router, whereupon the router will route the packet out of eth1 (perhaps needing to first issue an ARP request of its own on eth1 to determine which MAC address should actually receive the packet).
| network | card | gateway | |
| 127.0.0.0/8 | local | direct | |
| 10.1.0.0/16 | eth1 | direct | |
| 10.2.0.0/16 | eth0 | direct | |
| 10.3.0.0/16 | eth2 | direct | |
| 10.4.0.0/16 | eth2 | 10.3.0.2 | |
| default | eth1 | 10.1.0.1 | |
| (optional) | 10.0.0.0/16 | eth1 | 10.1.0.1 |
| (optional) | 10.5.0.0/16 | eth1 | 10.1.0.1 |
| (optional) | 209.65.56.1/21 | eth1 | 10.1.0.1 |
(The three rows labeled “optional” are not necessary since they're redundant with the “default” rule, but one could reasonably include them in the answer.)