Final

[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16]

Problem Xf.1.

[10 pts] In Java's implementation of threads, each object has two methods named wait and notifyAll. Explain what each method does.

wait does not return until somebody calls notifyAll (or notify) on the same object.
notifyAll awakes all threads stalled in the wait method on the same object, so that wait will return within those threads, and notifyAll also returns immediately.

Problem Xf.2.

[8 pts] We discussed the relative merits of implementing threads as a kernel-independent user library (user-level threads) and of implementing threads via system calls to the kernel (kernel-level threads). Explain an advantage of one of the approaches over the other. Be sure to mention which approach your point supports.

Advantages of user-level threads:

In switching contexts between threads, avoids switching to kernel mode, which adds quite a bit of time to the context switch.
OS-level support is minimal, so threaded applications can be more portable across operating systems.
Applications have more control over the scheduling policy used for switching between threads.

Advantages of kernel-level threads:

On multicore/multiprocessor systems, threads can be scheduled simultaneously on different cores/processors.
When one thread blocks for a page fault or device access, the OS knows about other live threads in the same process that can still use the CPU.

Problem Xf.3.

[10 pts] Identify two reasons why shared-memory concurrency with locks/semaphores (as implemented by Java, for instance) is problematic, leading some to suggest that message-passing concurrency should be preferred.

Shared-memory solutions lead to race conditions and deadlock, which are difficult to find.
With many processors/cores, giving each core efficient access to memory is quite challenging, including complex issues such as cache concurrency; it becomes impractical beyond, say, 16 cores. (One even gets into memory models where one thread's code may say to modify one memory location after another but another thread may see the second memory location updated before the first.)

Problem Xf.4.

[8 pts] In a system where some processes are I/O-bound while others are compute-bound, how can the OS improve on a simple Round Robin approach for process scheduling to improve overall system performance?

We should prioritize those processes that are I/O-bound, so that whenever they are ready for the CPU we can spend the small amount of time it takes so that the I/O-bound process is again waiting on I/O. This will use the I/O devices more heavily while having a negligible effect on CPU usage.

Problem Xf.5.

[10 pts] Explain what NAT (network address translation) accomplishes, and outline how it works.

NAT translates computers assigned IP addresses in an internal network to IP addresses within the overall Internet; it is particularly useful when there is are fewer IP addresses allocated to an organization than the organization has computers.

Whenever a computer in the internal network with internal IP address A wants to communicate with the external network, it goes through a gateway implementing NAT. If the gateway has not seen A before, it temporarily allocates an external IP address B and remembers the correspondence between A and B. The gateway replaces the source address in the packet with B before sending it on toward its destination. Any subsequent packets from A sent through the gateway also have their source address replaced with B. And when an IP packet comes to the gateway labeled to be sent to B, the gateway replaces the destination A before sending it back to its address.

Problem Xf.6.

[10 pts] What is the purpose of the time-to-live field in an IPv4 packet header, and how does it work?

The time-to-live field ensures that each IP packet eventually disappears from the network, even in the case that it happens to enter an endless cycle of routers, each believing that the way to get the packet to the destination is to send it to the next router in the cycle. As each router forwards a packet to its next destination, it decrements the value in the time-to-live field; but if the time-to-live field already contains 0, it drops the packet rather than forward it to the next destination.

Problem Xf.7.

[10 pts] When a user requests a URL like http://ozark.hendrix.edu/filename.txt, what does the browser do to retrieve the file via HTTP?

The browser opens a TCP connection to port 80 on the server ozark.hendrix.edu, sending it a message like the following.

GET /filename.txt HTTP/1.1
Host: ozark.hendrix.edu
   a blank line terminates its request

It then awaits a response from the server, which will include a header describing the requested file, followed by a blank line, followed by the file contents.

Problem Xf.8.

[10 pts] Suppose a computer A asks a DNS server B for the IP address of www.meteo.an, and B's cache does not have anything related. What happens to resolve the IP address?

After A sends its request to B, B will first go to the root DNS servers to give the IP address for an authoritative DNS server (call it C) for the .an domain. It will then ask C for the IP address of an authoritative DNS server (call it D for .meteo.an. Finally, it asks D for the IP address of www.meteo.an. All of these results (the IP addresses for C, D, and www.meteo.an) are stored into B's cache should anybody else ask in the near future, and the final IP address is sent to A in response to its request.

Problem Xf.9.

[10 pts] Traditionally one reads a file by repeatedly reading a sequence of bytes into a buffer, with each read returning the next group of bytes from the file. More recently, operating systems have also supported memory-mapped I/O, where a portion of the virtual address space can be dedicated to refer to the contents of a file. Explain two reasons why a programmer might opt to use memory-mapped I/O rather than the traditional technique.

The traditional technique involves a system call each time we want to read more bytes, and system calls are themselves relatively slow. Memory-mapped I/O does not require system calls.
The traditional technique copies data from the operating system's memory into the user process's buffer, and the copying takes time. By contrast, memory-mapped I/O can be implemented so that the program is directly accessing the OS memory for representing the file.
Memory-mapped I/O is quite a bit simpler when the program jumps around the file; in the traditional technique, each jump has a system call of its own, called a seek.
Two processes can open up the same memory-mapped file, and any changes by one process would be seen immediately by the other. This provides a way that processes can have shared-memory concurrency, even though the processes themselves actually have distinct addresses spaces.

Problem Xf.10.

[8 pts] Suppose we have a disk of 8 sectors, numbered 2 through 9, with the following three files occupying sectors as listed. Tabulate the FAT contents, using 0 to indicate end of file and 1 to indicate an unused sector.

`a.txt`:	9, 4, 7
`b.txt`:	6, 3, 2
`c.txt`:	5

`i`	FAT[`i`]
2	0
3	2
4	7
5	0
6	3
7	0
8	1
9	4

Problem Xf.11.

[10 pts] Identify two differences between designing a filesystem for flash memory versus designing for a hard disk.

In designing for a hard disk, data placement is a major consideration: Files are much more efficient when they are at adjacent locations to avoid having to move the disk head as the file is read.
Flash memory hardware needs to be notified when a block becomes available, so that it does not waste time copying the block elsewhere as part of its wear-leveling.
A flash-based filesystem can perform better if writes are batched together.
Because flash supports a limited number of writes to each block, the filesystem should avoid frequently changing data. For example, the filesystem may not want to include in a file's metadata the time when a file was most recently read.

Problem Xf.12.

[8 pts] Suppose we have a group of closely related changes to the disk to effect one conceptual change, such as moving a file from one directory to another. Describe how a journaling filesystem ensures that all these changes take place together, regardless of the possibility that the computer might crash in the midst of performing them.

Journaling filesystems include a separate log of actions that are being performed. For any set of changes, it first writes a description of the upcoming changes into the log, concluding with a log record saying that the set of changes is “committed.” The filesystem ensures that this log data is actually on disk before actually changing anything on disk. On bootup, the filesystem goes through the log to find the “committed” changes, ensuring that those changes are reflected on disk.

Problem Xf.13.

[10 pts] Suppose we have a two-disk RAID 1 array, where each disk has an expected lifetime of 10 years, and replacing a disk takes one full day. What is the expected time before the RAID fails (i.e., one fails while the other disk is being replaced)? Show your work.

The expected time before one of the disk fails is five years. Whenever one disk fails, the probability that the other fails before the first is repaired is 1 / (365.25 ⋅ 10), so we expect 365.25 ⋅ 10 failures of one disk before the other one fails during repair. Overall, then, the expected number of years to both failing simultaneously is 5 ⋅ (365.25 ⋅ 10) = 18,262.5 years.

Problem Xf.14.

[10 pts] Describe how the one-time pad algorithm for symmetric encryption works, and explain why it is usually impractical even for situations where one can guarantee secure exchange of the symmetric key.

With the one-time pad, we have an n-bit string K as our symmetric key. Given an n-bit message M, we encrypt it to our cryptotext C using a bitwise exclusive-or: M ^ K. Receiving C, we can decrypt back to M by doing another bitwise exclusive-or C ^ K.

The one-time pad is usually impractical because the key must be so long: as long as the maximum possible number of bits to be sent over the conversation's lifetime.

Problem Xf.15.

[10 pts] Suppose we have a hashed version of a password that we would like to crack, and suppose that our computer can hash 100 passwords in a second.

If we know that the target password is a four-digit number, how long will it take before we are guaranteed to determine the password? Express your answer in minutes, and show your work.
If we know that the target password has six lower-case English letters. how long will it take before we are guaranteed to determine the password? Express your answer in days, and show your work.

10⁴ / 100 / 60 = 1.667 minutes
26⁶ / 100 / 60 / 60 / 24 = 35.754 hours

Problem Xf.16.

[8 pts] Suppose Alice and Bob wants to use signatures so that Bob can verify that a message is indeed sent from Alice. You may assume that Bob can be sure that Alice's public key is genuine. How would they go about it (without reference to a particular algorithm for signatures)?

Alice generates a matching pair of keys K (the public key) and S (the private key).
Alice announces K to Bob.
Bob sends his message M followed by the “certificate,” which is the result of encrypting H(M) using K. (By H(M), I mean a cryptographic hash of M.)
Alice can verify that the version of M she received is correct by decrypting the certificate using S and verifying that this matches what she herself computes as H(M).