In Java's implementation of threads, each object has two methods named
wait and notifyAll. Explain what each method
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
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
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.
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.)
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.
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
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.
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
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
GET /filename.txt HTTP/1.1
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.
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
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
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
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.
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.
9, 4, 7
6, 3, 2
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
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
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.
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.
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
5 ⋅ (365.25 ⋅ 10) = 18,262.5 years.
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.
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
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
how long will it take before we are guaranteed to determine the password?
Express your answer in days, and show your work.
104 / 100 / 60 = 1.667 minutes
266 / 100 / 60 / 60 / 24 = 35.754 hours
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
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