The simple solution is shown below in blue. The weakness of this solution is that if a steady stream of traffic continues arriving in one direction, cars waiting to cross in the opposite direction will never get a chance; this effect is known as starvation. See the text solution to the readers-writers problem (pg. 233) for a similar solution that avoids starvation.

a) What does this mean?

Atomic operations can only be executed in their entirety without danger of preemption by an interrupt.

b) In general, what problem could this lead to?

Non-atomicity of the semaphore creation and initialization operations implies that a potential race condition exists in which two processes could create the same semaphore and initialize it to different values. This could lead one of these processes to potentially incorrect behaviour.

c) How did you avoid this problem in your solution to assignment #3?

In this assignment, all semaphores should be created by the main process before the children are forked. Hence, as pointed out in the IPC notes, no race is possible, provided the semaphores are created with a key of IPC_PRIVATE. If a non-private key value is used, another process could potentially create a race condition. However, there was no need to use public keys in this assignment.

d) Briefly describe Stevens' solution and explain how it overcomes this problem.

4. The following code fragment defines the behaviour of a simple I/O controller:

a) What form of I/O management is used by this controller?

Direct I/O with polling.

b) What effect would this controller have on overall system performance if it were used in a multitasking environment?

Because polling is managed by the CPU, many processor cycles are wasted checking the status register of the controller. This has the effect of slowing down other processes executing on the system.

c) The McGill University Health Center uses this controller for starting and stopping the transmission of X-rays in a medical diagnostic device. The controller, which runs in a multitasking environment, queries the device to determine whether it has been activated, and if so, turns it off after 20 ms. As an Operating Systems consultant, you have been hired by the hospital to advise them on the option of switching to an interrupt-driven controller. What is your advice, and are there any questions you should ask about the system? Remember: if any patients are bombarded with a radiation overdose, guess who's going to be sued?

While direct I/O with polling is less efficient that interrupt-driven I/O in terms of overall system performance, the other factor that must be considered in this situation is the process response time to the I/O completion event. Regardless of the I/O strategy, we must ask whether the process managing the X-ray device is guaranteed to respond to the completion event within a specified maximum time period. A real-time system offers such a guaranteed response time to any interrupt event. For our X-ray process, we need to ensure a similar real-time response. Thus, the questions we ask should be as follows:

If we use interrupt-driven I/O, is the X-ray device interrupt uniquely resolved by the system with respect to any other interrupt event that may occur simultaneously? Does the X-ray interrupt have sufficiently high priority to ensure that the appropriate handler will be invoked rapidly, even if many other interrupts occur simultaneously? If we use direct I/O, what effect will interrupts for other devices have on our X-ray process? What about process switching time, or the number of active processes?

5. Chez Guppy, a very exclusive French restaurant, would like to accommodate five dinner parties, P0 through P4, in one evening. The restaurant has a total of 10 plates, 13 bowls, 13 sets of cutlery, and 8 wine glasses. Due to observance of proper etiquette, each group of diners will stop eating and wait for the waiter to bring a requested item (plate, bowl, cutlery, or glass) to the table when it is required. The maximum claim and current allocation tables are as follows:

Assuming that the diners don't mind waiting (after all, the restaurant isn't known for its speedy service) will the restaurant be able to feed all five parties successfully?

We use the Banker's Algorithm to determine whether or not a state is safe with respect to deadlock. From the current state, the vector of allocated resources is Al = [8, 12, 12, 6] and hence, the available resources is Av = [2, 1, 1, 2].

Based on the maximum claims matrix, the only party that can have its maximum claim satisfied at present is P3. If we grant the maximum claim to P3 and assume the party then finishes dining and releases all its resources, the resulting vector of available resources will become Av = [2, 2, 1, 3].

On the following iteration, we find P1 can be satisfied, resulting in Av = [3, 2, 2, 4]. Next, P4 can be satisfied, resulting in Av = [4, 3, 4, 6]. At this point, however, we find that neither P0 nor P2 can have its maximum claim satisfied. P0 may need one additional bowl or P2 may need one additional set of cutlery beyond the resources available. Thus, Chez Guppy may be unable to feed all five parties successfully.

6. A competing restaurant, Mea Culpa, decides that it can't afford the risk of seating patrons and then being unable to serve them. To break the deadlock condition, Mea Culpa imposes a rule that dining parties must be granted their maximum claim on any requested item, if available. For example, when party P2 (above) asks for bowls, they will be given 8 bowls (maximum claim), or else they must wait. When party P4 asks for glasses, they will be given 4 glasses, or else they must wait. Does this solve the deadlock problem? If so, explain why, and if not, explain what is missing to make the rule succeed.

Unfortunately, the possibility of deadlock persists. While the all-or-none rule is a step in the right direction, this does not affect any of the four conditions of deadlock: mutual exclusion, hold-and-wait, cyclic waiting, and no preemption. One suggested improvement to the rule is to require that dining parties always request resources in a specified order, for example, first plates, then bowls, cutlery, and finally, glasses. This imposition of a total order ensures that a cyclic wait is no longer possible, and hence, deadlock is prevented.

7. You are analyzing a virtual memory system containing 4 frames as indicated below. Suppose the sequence of page accesses is as follows: 20 (write), 6 (write), 18 (read), 29 (read) 3 (read). What will the page table then contain if the modified clock replacement algorithm, as described in class, is used? For your solution, assume the clock pointer begins at a position such that the contents of Frame 0 (if unused and not dirty) will be the first page replaced on a page fault.

The attempted access to page 20 results in a page fault, so we have to replace a page. We first scan the table looking for u = 0, d = 0 and find such a page immediately in frame 0. We replace this page and advance the clock pointer.

Next, for the write to page 6, we find that the page is already in the table, so the write sets the corresponding dirty bit.

The attempted access to page 18 results in a page fault, so we have to replace a page. We first scan the table looking for u = 0, d = 0 and fail. Next, we scan the table looking for u = 0, d = 1, resetting the used bit to zero as we do so. At frame 3, we find a table entry of u = 0, d = 1, so replace this page and adjust the clock pointer.

Page 29 is already in the page table, so the read sets the used bit.

The attempted access to page 3 results in a page fault, so we have to replace a page. We first scan the table looking for u = 0, d = 0 and fail. Next, we scan the table looking for u = 0, d = 1, resetting the used bit to zero as we do so. At frame 1, we find a table entry of u = 0, d = 1, so replace this page and adjust the clock pointer. The final state of the page table is shown below.

8. Experiments with varying page size for a virtual memory design yield the following results. Explain what is happening to cause these results, using simple diagrams as necessary.

Referring to the fault rate column, with page sizes larger than the minimum (512 bytes), spatial locality helps decrease the fault rate. However, as the page size increases, the number of pages that can be maintained in primary memory must decrease. Hence, once the page size exceeds an optimum value (4096 bytes), temporal locality begins to suffer and the fault rate increases. Referring to the instruction rate column, we see that performance peaks at a page size of 2048 bytes. Even though the fault rate drops, the instruction rate actually decreases slightly with the larger page size. Keeping in mind that the miss penalty is equal to the sum of page access and page transfer times, this anomaly can be explained by the increased cost of transferring larger pages from disk to main memory on each page fault.

9. In the context of network communications:

a) What does it mean for a connection-oriented server process to bind a socket?

Before a socket can be used to receive messages, it must be bound to a port number, which serves as the third component of the transport layer address tuple <network, host, port>. For any given transport layer protocol, the port establishes the communication endpoint associated with the socket on the specified host.

b) Why doesn't the client need to do the same?

Since the client does not expect to receive messages unless it requests information from a server, the task of specifying the communication endpoint is unnecessary. When the client connects to a server, the system will dynamically establish a port number on the client if needed for returned data.

c) Should a connectionless server bind a socket? Explain.

Yes, the socket must be bound to a port regardless of which transport protocol is used. Otherwise, clients will be unable to communicate with the server since the communication endpoint is undefined.

d) Can the same TCP socket be used to accept a connection from a client and then read a message from that client? Explain.

10. A number of cable providers have registered with the CRTC as a Competitive Local Exchange Carrier to offer IP-based phone service to Ontario and Quebec customers. One of these companies has hired you to design its software for conference calls.

a) Why might you want to use TCP as the transport layer protocol for this software?

TCP is reliable. Data is guaranteed to arrive in the correct order without error or loss. Thus, there is no need to worry about packets of voice information being dropped or corrupted.

b) Why might you want to use UDP as the transport layer protocol for this software?

While the reliability of TCP is a bonus, it comes with the price of lower performance than UDP. For voice communications, overall throughput, and, as pointed out in the bonus question, delay, are more significant factors than the occasional loss of a packet. Furthermore, UDP allows multicasting, which provides a significant performance improvement over repeated one-to-one data transmission as the number of receivers increases.

Bonus: Assume that voice data is encoded in 200 byte packets, each containing approximately 200 ms of sound information. A packet drop rate (i.e. packets not received by one or more listeners) of 5% or less is tolerable. However, humans are very sensitive to timing in voice communications. Therefore, voice data must be received by the listeners as soon as possible after it has been generated by the speaker. Assuming you have decided to build the previously discussed conference call software using UDP, describe how you would ensure reasonably low rates of dropped packets while maintaining minimum delay.

Since UDP is inherently unreliable, we need to establish some form of acknowledgement scheme between sender and receivers that causes the sender to decrease its transmission rate when packet loss becomes unacceptable. However, given the parameters above, decreasing the transmission rate to less than 1KBps will result in a steadily increasing delay! We can resolve this conundrum by noting that voice can be subsampled with a corresponding decrease of quality in the reproduced signal. Furthermore, various compression schemes exist that trade off data size with computational complexity and accuracy. These variables allow the sender to decrease transmission rate while maintaining a relatively constant delay.

We have seen the sliding window protocol as a means of allowing the sender to continue transmitting a certain number of packets without receiving an acknowledgement of receipt. However, as the number of receivers grows, scalability becomes a serious concern. One possibility is to use a tree-like hierarchical acknowledgement scheme, in which n middle-layer receivers each forward transmitted data to a maximum of m bottom-layer receivers. Each middle-layer receiver expects occasional acknowledgement information from the bottom-layer receivers, and forwards a summary to the sender. This method can be extended to multiple levels as necessary.

Another possibility is to use a negative acknowledgement (NAK) protocol in which receivers only inform the sender if data appears to have been dropped. Provided the sender decreases its transmission rate appropriately when a number of such NAKs have been received, and increases its transmission rate when no NAKs have arrived for a suitably long period, a balance can be achieved between our requirements for low packet loss and minimum delay.

Naturally, reliability of acknowledgement transmission is a concern for either protocol. For this reason, it may be advisable to use TCP in the backward direction from voice receiver to sender to ensure that ACK or NAK data is received in a timely manner.