課程名稱︰高等作業系統
課程性質︰選修
課程教師：蘇雅韻
開課學院：電資學院
開課系所︰資工所、網媒所
考試日期（年月日）︰2011.06.01
考試時限（分鐘）：150分鐘
試題 :
Advanced Operating Systems
National Taiwan University
Spring 2011
Exam
Notes:
1. This exam lasts for 150 minutes and consists of 85 points. Budget your time
accordingly.
2. This exam has 5 questions and 8 pages (including this one); check that you
have all pages before starting.
3. Many questions have more than one correct answer! However, some answers are
more correct than others. You should therefore use good judgment and follow
solid systems principles in answering each question.
4. State your assumptions and show your intermediate work, where appropriate.
1. Short answers (16%, 4% each)
(1) Given the following observation found in "Availability in the "Globally
Distributed Storage Systems" paper: larger failure bursts have higher
rack affinity. How would you design a replication policy for Haystack
directory to determine which Haystack stores to store a newly uploaded
photo to ensure your replication is effective?
(2) You noticed that after you change the content of your own website, the
content shows up in Google search results after just a few hours. Use
the material in the Percolator paper, assume that your webpage is
stored in a BigTable, and briefly describe how Google's indexing system
utilizes Percolator to quickly incorporate your new content into their
index?
(3) In the Scheduler Activation paper, how does a user-level thread
scheduler communicate to kernel to express its desired level of
parallelism?
(4) Provide two benefits of structuring a kernel for multicores that
uses explicit message passing over shared memory for inter-core
communication.
2. File system: local and distributed (24%)
(1) (6%) Consider two caching strategies for distributed file systems:
whole-file caching as used in AFS, and block-level caching as used in
NFS (or known as remote-open in the AFS paper). Briefly explain what
whole-file caching scheme is, and what block caching is.
(2) (6%) In Section 5 of the AFS paper, Howard et al. argued several
advantages of the whole-file caching against remote-open scheme,
provide two scenarios where remote-open is a better fit.
(3) (6%) In the GFS system architecture, a single master serves metadata
while a large number of chunk servers handle chunk read/write
operations. Describe two techniques that the GFS designers deploy to
ensure the single master does not become a performance bottleneck.
(4) (6%) For a workload consisting of many writes, such as compilation or
downloading many small files, which local file system would perform
better? fast file system or log-structured file? Why?
3. Virtual machines and kernels (20%)
(1) (4%) Based on the implementation described in the Disco and Xen papers,
please answer whether it is the (a) virtual machine monitor or (b) the
guest operating system that is responsible in creating the illusion of
a contiguous physical memory?
(2) (8%) You want to apply the resource container concept on Xen to track
the resource usage for each VM. Based on the implementation described
in Section 3 of the paper, describe how Xen could account CPU, disk,
and network usage for each virtual machine. (Assume the resource usage
of each virtual machine is accounted to one resource container, and you
can modify both Xen and Domain 0). Please specify where you would add
the accounting mechanism.
(3) (8%) You need to choose an "operating system" to host machines from
multiple tenants on your multicore machines for a cloud environment,
which exposes hardware interface. Would you choose an Exokernel
approach or a virtual machine approach (such as Xen or Disco)? Justify
your answer by providing the benefits of your chosen approach and what
your design goals are.
4. Data race (20%)
(1) (5%) Based on the papers covered in this semester, define what data
race is.
(2) (10%, 5% each) If two threads both execute the code snippet below.
Based on the (a) Eraser and (b) "Bugs as Deviant Behavior" papers,
answer the following questions:
(1) if their system can detect data race?
(2) If it can, how? If it cannot, why not?
Please be specific on your answer and state your additional assumption
if there is any.
┌──────────────────────────────────┐
│int u, v; │
│lock mutex; │
│ │
│thread_func(void* data) │
│{ │
│ int thread_id = (int*)data; // obtain my thread id │
│ if (thread % 2 == 0) { │
│ lock(mutex); │
│ u = v++; │
│ unlock(mutex); │
│ } else { │
│ v++; │
│ } │
│} │
└──────────────────────────────────┘
(3) (5%) Using the same code snippet as question (2), describe how
Determinator prevents data race from happening?
5. Feedback (5%)
Please write down your favorite and least favorite papers for the class.
There is no right or wrong answer here: you will get full credits if you
write any paper we covered in this class. =)