課程名稱︰高等作業系統 課程性質︰選修 課程教師：蘇雅韻 開課學院：電資學院 開課系所︰資工所、網媒所 考試日期（年月日）︰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. =) --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.51.155 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1436074623.A.A2F.html