CS2200 Exam 4 Solution

ise: avoid verbose answers. Good luck!
Table of Contents:
Question # Topic Total
1 Disk Calculations (7 minutes) 11
2 Deadlocks and Race Conditions (5 minutes) 7
3 Unix Commands and Allocation (8 minutes) 13
4 Threading Library Queue (8 minutes) 12
5 Multithreading (8 minutes) 12
6 Networking (4 minutes) 6
7 Networking (12 minutes) 19
8 Hidden
9 Hidden
Total 100
Question 1:
We reserve the right to modify numbers for this question on the final exam.
a) We have a disk with the following design specifications:
● Total # of cylinders = 250 (numbered 0-249). Assume that 0 = outermost cylinder and 249 = innermost cylinder.
● Current head position = cylinder 47 and the head is currently moving outwards, towards the disk's cylinder 0.
● Suppose that the latency of moving the head position is M per cylinder, and the latency of transferring a track is C.
● Assume there are currently 7 pending requests. Assume that each request transfers an entire track, and that after locating the target track, the disk head can immediately start transferring the track (i.e., there is no rotational latency incurred).
Request id: R1 R2 R3 R4 R5 R6 R7
Cylinder id: 14 17 91 168 56 48 8
Give your answers to questions (i) and (ii) as a function of M and C.
(i) What is the expected response time for R5 (request 5) if the disk scheduling algorithmused is SCAN? Explain your answer. (3 points)
(ii) What is the expected response time for R5 (request 5) if the disk scheduling algorithmused is LOOK? Explain your answer. (3 points)
b) This question is not related to the previous part (a). Assume the following disk drive specifications:
○ Average seek time: 18 ns
○ Rotational speed: 7500 RPM
○ Platters: 3
○ Surfaces: 2
○ Tracks per surface: 8000
○ Sectors per track: 1024
○ Recording density: 256 bytes per sector
This disk has received a request to read 7 random sectors, how much total time (expressed
in ns) will that request take to complete? Explain your answer. (5 points)
Question 2:
The specifications are as follows:
● foo() must set curr to an integer value and call bar(), and ● bar() must increment the value of curr.
a) Student A looks at these specifications and writes the following code:
int curr = 0;
int foo(int val) { int y; curr = val; y = bar(); return y;
} int bar() { int x; x = curr + 1; return x;
}
What can go wrong with this code? What is this error called? (2 points)
b) Using the same specifications, student B implements the following code:
int curr = 0;
pthread_mutex_t curr_mutex;
int foo(int val) { int y;
pthread_mutex_lock(&curr_mutex); curr = val; y = bar();
pthread_mutex_unlock(&curr_mutex); return y;
} int bar() { int x;
pthread_mutex_lock(&curr_mutex); x = curr + 1;
pthread_mutex_unlock(&curr_mutex); return x;
}
What can go wrong with Student B’s code? What is this error called? (2 points)
c) Suggest how to modify Student B’s code to ensure that it produces the desired result? (3 points)
Question 3:
a) Based on Unix commands, determine, for each command, whether a new i-node is created and its reference count. Assume that these commands are executed in the displayed order and that initially none of the files f1, f2, f3, f4 exist in the file system. (6 points)
Command New i-node? (yes/no) Old ref count New ref count
touch f1
touch f2
ln -s f1 f3
cat f3
cp f2 f4
rm f2
b) What is the difference between ln -s f1 f2 and ln f1 f2? Give one reason you would opt to use the latter instead of the former. (2 points)
c) Considera file system that uses the hybrid storage allocation strategy. The file system has the following parameters:
i) Size of index block = 256 bytes
ii) Size of pointer = 16 bytes
iii) Size of data block = 2048 bytes
iv) Each i-node consists of:
1) 1 direct data block pointer
2) 1 single indirect pointer
3) 1 double indirect pointer
What is the size in bytes of the biggest file that can be created with this file system? (5 points)
Question 4:
The internal representation for a lock in the thread library is shown below:

Assume that we have a program with 8 threads, T1 to T8, and the following sequence of events happens:
a) T1 executes thread_mutex_lock(L1);
b) T2 executes thread_mutex_lock(L3);
c) T3 executes thread_mutex_lock(L1);
d) T4 executes thread_mutex_lock(L2);
e) T5 executes thread_mutex_lock(L1);
f) T6 executes thread_mutex_lock(L4);
g) T1 executes thread_mutex_unlock(L1);
h) T7 executes thread_mutex_lock(L2);
i) T2 executes thread_mutex_lock(L4);
j) T8 executes thread_mutex_lock(L3);
Assume that before the start of the sequence, all locks (L1 to L4) were free.
a) Show the thread library’s lock bookkeeping state after the aforementioned 8 steps. For each number in the figure (1 to 12), enter the corresponding thread id (T1 to T8). If a number does not have a corresponding thread id, enter N/A. (8 points)
Note: You should put at most ONE thread-id corresponding to each number.

● 1:
● 2: ● 3: ● 4: ● 5: ● 6: ● 7:
● 8: ● 9:
● 10: ● 11:
● 12:
b) Shown in the figure below are possible points of execution for each of the eight threads (T1 to T8).For each thread, select the number that best corresponds to its current point of execution based on your answer to part (a). (4 points)

Note: the execution point numbered “1” corresponds to a thread being before or after the critical section in its execution.
a. T1:
b. T2:
c. T3:
d. T4:
e. T5:
f. T6:
g. T7:
h. T8:
Question 5:
The following timelines show the execution history of two threads, each running on a different core of a multicore processor that is endowed with hardware cache coherence for shared memory. x and y are shared memory locations the two threads are operating on, while R1 and R2 are general-purpose registers in each core. For each sequence, determine the final value of x and y.
● Threads:
Thread 1 (T1)
Time 0: R1 <- 0
Time 2: R1 <- R1 + 2
Time 4: x <- R2 + R2 Thread 2 (T2)
Time 1: R2 <- 0
Time 3: R2 <- R1 + R2
Time 5: y <- x + R1
a. What is the value of x? (2 points)
i. 2
ii. 4
iii. 6
iv. None of the above
b. What is the value of y? (2 points)
i. 2 ii. 4 iii. 6
iv. None of the above
● Threads:
Thread 1 (T1)
Time 0: R1 <- 0
Time 1: R1 <- R1 + 2
Time 4: x <- R2 + R2 Thread 2 (T2)
Time 1: R2 <- 0
Time 2: R2 <- R1 + R2
Time 3: y <- x + R1
a. What is the value of x? (2 points)
i. 2 ii. 4 iii. 6
iv. None of the above
b. What is the value of y? (2 points)
i. 2 ii. 4 iii. 6
iv. None of the above
● Threads:
Thread 1 (T1)
Time 0: R1 <- 0
Time 2: R1 <- R1 + 2
Time 3: x <- R2 + R2 Thread 2 (T2)
Time 1: R2 <- 0
Time 2: R2 <- R1 + R2
Time 3: y <- x + R1
a. What is the value of x? (2 points)
i. 2 ii. 4 iii. 6
iv. None of the above
b. What is the value of y? (2 points)
i. 2 ii. 4 iii. 6
iv. None of the above
Question 6:
(a) (3 points) The Ethernet protocol is ubiquitously used for the Media Access and Control (MAC) layer that detects collisions and retransmits a packet if there is a collision. Given this mechanism, why do we also need the transport layer to deal with packet retransmissions?
(b) (3 points) In the ethernet network shown in the following figure, assume that nodes N1, N3, N4,and N5 all simultaneously attempt to send packets to N6. Which nodes will experience collision of their packets? Why?

Question 7:
a) (8 points) In the network below, each link is bi-directional and symmetric. With the indicated link costs, use the Distance Vector algorithm to compute the shortest path from network node y to all other network nodes. Show the contents of the DV table for ‘Node x’. One row of the table is pre-populated for you.
Cost through immediate neighbors
Destination v w y
t
u 6 (xvu) 9 (xwu) 15 (xytu)
v
w
y

b) (4 points) A transport protocol adds a packet header consisting of the following fields to eachpacket.
Assume that each of the header fields in the transport layer occupies 4 bytes.
● destination_port
● source_port
● protocol_type
● num_packets
● sequence_number
● packet_size
● check_sum
A network layer protocol adds a datagram header consisting of the following two fields to each packet:
● ipv6 destination_IPaddress
● ipv6 source_IPaddress
A link-layer protocol adds a frame header consisting of the following two fields to each datagram:
● destination_MAC_address
● source_MAC_address
Each IPv6 address is 16 bytes and each MAC address is 6 bytes.
The link-layer operates on a Malav’s link layer implementation that can transmit a total of 1590 bytes per frame.
i) Compute the maximum payload that can be sent in each packet on the wire. (2 points)
ii) Yesha wants to send a 94.875KB Word document to Andrej via the internet.
Assume that the protocol stack mentioned above minimizes the total number of packets that need to be sent. Assume the network is error free (no collision, no loss of packets, no packet corruption). Compute the number of packets required to send the Word document to Andrej. Show your work for credit. (2 points)
c) (5 points) Assume Prit wants to send a message consisting of 1000 packets to John using Malav’s ‘Sliding Window’ reliable transport layer protocol implementation with a window size of 10 packets.
Assume that the network connecting Prit’s and John’s computers has the following characteristics:
● Transmission speed on the physical link = 2.5 * 108 meters/sec
● Packet loss = 20% (only for data packets; zero loss for ACKs)
● Sender overhead = 1 millisecond
● Receiver overhead = 2 milliseconds
● Assume each router hop adds a fixed cumulative routing plus queuing latency of 0.1 milliseconds.

Assume that the time to place the data packet and ACK on the wire are negligible compared to the propagation time on the medium.
What’s the total elapsed time (in milliseconds) for Prit to be certain that the file has been successfully transmitted to John?
Question 8: (Hidden)
Question 9: (Hidden)