From 0c5419ce28e18dc45c85653d4f7ab7a3a6c3260b Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Fri, 21 Jul 2006 00:56:03 +0000 Subject: [PATCH] Add an identifier to each question in the design document templates, so that they are easier to refer to individually. --- doc/filesys.tmpl | 105 ++++++++++++++++++++++---------------------- doc/userprog.tmpl | 109 ++++++++++++++++++++++++---------------------- doc/vm.tmpl | 101 +++++++++++++++++++++--------------------- 3 files changed, 162 insertions(+), 153 deletions(-) diff --git a/doc/filesys.tmpl b/doc/filesys.tmpl index 63329ab..e3d6f56 100644 --- a/doc/filesys.tmpl +++ b/doc/filesys.tmpl @@ -26,102 +26,105 @@ FirstName LastName ---- DATA STRUCTURES ---- ->> Copy here the declaration of each new or changed `struct' or `struct' ->> member, global or static variable, `typedef', or enumeration. ->> Identify the purpose of each in 25 words or less. +>> A1: Copy here the declaration of each new or changed `struct' or +>> `struct' member, global or static variable, `typedef', or +>> enumeration. Identify the purpose of each in 25 words or less. ->> What is the maximum size of a file supported by your inode structure? +>> A2: What is the maximum size of a file supported by your inode +structure? ---- SYNCHRONIZATION ---- ->> Explain how your code avoids a race if two processes attempt to extend ->> a file at the same time. +>> A3: Explain how your code avoids a race if two processes attempt to +>> extend a file at the same time. ->> Suppose processes A and B both have file F open, both positioned at ->> end-of-file. If A reads and B writes F at the same time, A may read ->> all, part, or none of what B writes. However, A may not read data ->> other than what B writes, e.g. if B writes nonzero data, A is not ->> allowed to see all zeros. Explain how your code avoids this race. +>> A4: Suppose processes A and B both have file F open, both +>> positioned at end-of-file. If A reads and B writes F at the same +>> time, A may read all, part, or none of what B writes. However, A +>> may not read data other than what B writes, e.g. if B writes +>> nonzero data, A is not allowed to see all zeros. Explain how your +>> code avoids this race. ->> Explain how your synchronization design provides "fairness". File ->> access is "fair" if readers cannot indefinitely block writers or vice ->> versa. That is, many processes reading from a file cannot prevent ->> forever another process from writing the file, and many processes ->> writing to a file cannot prevent another process forever from reading ->> the file. +>> A5: Explain how your synchronization design provides "fairness". +>> File access is "fair" if readers cannot indefinitely block writers +>> or vice versa. That is, many processes reading from a file cannot +>> prevent forever another process from writing the file, and many +>> processes writing to a file cannot prevent another process forever +>> from reading the file. ---- RATIONALE ---- ->> Is your inode structure a multilevel index? If so, why did you choose ->> this particular combination of direct, indirect, and doubly indirect ->> blocks? If not, why did you choose an alternative inode structure, ->> and what advantages and disadvantages does your structure have, ->> compared to a multilevel index? +>> A6: Is your inode structure a multilevel index? If so, why did you +>> choose this particular combination of direct, indirect, and doubly +>> indirect blocks? If not, why did you choose an alternative inode +>> structure, and what advantages and disadvantages does your +>> structure have, compared to a multilevel index? SUBDIRECTORIES ============== ---- DATA STRUCTURES ---- ->> Copy here the declaration of each new or changed `struct' or `struct' ->> member, global or static variable, `typedef', or enumeration. ->> Identify the purpose of each in 25 words or less. +>> B1: Copy here the declaration of each new or changed `struct' or +>> `struct' member, global or static variable, `typedef', or +>> enumeration. Identify the purpose of each in 25 words or less. ---- ALGORITHMS ---- ->> Describe your code for traversing a user-specified path. How do ->> traversals of absolute and relative paths differ? +>> B2: Describe your code for traversing a user-specified path. How +>> do traversals of absolute and relative paths differ? ->> Look over "pwd.c" in src/examples. Briefly explain how it +>> B3: Look over "pwd.c" in src/examples. Briefly explain how it >> determines the present working directory. ---- SYNCHRONIZATION ---- ->> How do you prevent races on directory entries? For example, only one ->> of two simultaneous attempts to remove a single file should succeed, ->> as should only one of two simultaneous attempts to create a file with ->> the same name, and so on. +>> B4: How do you prevent races on directory entries? For example, +>> only one of two simultaneous attempts to remove a single file +>> should succeed, as should only one of two simultaneous attempts to +>> create a file with the same name, and so on. ->> Does your implementation allow a directory to be removed if it is in ->> use as a process's current directory? If so, what happens to that ->> process's future file system operations? If not, how do you prevent ->> it? +>> B5: Does your implementation allow a directory to be removed if it +>> is in use as a process's current directory? If so, what happens to +>> that process's future file system operations? If not, how do you +>> prevent it? ---- RATIONALE ---- ->> Explain why you chose to represent the current directory of a process ->> the way you did. +>> B6: Explain why you chose to represent the current directory of a +>> process the way you did. BUFFER CACHE ============ ---- DATA STRUCTURES ---- ->> Copy here the declaration of each new or changed `struct' or `struct' ->> member, global or static variable, `typedef', or enumeration. ->> Identify the purpose of each in 25 words or less. +>> C1: Copy here the declaration of each new or changed `struct' or +>> `struct' member, global or static variable, `typedef', or +>> enumeration. Identify the purpose of each in 25 words or less. ---- ALGORITHMS ---- ->> Describe how your cache replacement algorithm chooses a cache block to ->> evict. +>> C2: Describe how your cache replacement algorithm chooses a cache +>> block to evict. ->> Describe your implementation of write-behind. +>> C3: Describe your implementation of write-behind. ->> Describe your implementation of read-ahead. +>> C4: Describe your implementation of read-ahead. ---- SYNCHRONIZATION ---- ->> When one process is actively reading or writing data in a buffer cache ->> block, how are other processes prevented from evicting that block? +>> C5: When one process is actively reading or writing data in a +>> buffer cache block, how are other processes prevented from evicting +>> that block? ->> During the eviction of a block from the cache, how are other processes ->> prevented from attempting to access the block? +>> C6: During the eviction of a block from the cache, how are other +>> processes prevented from attempting to access the block? ---- RATIONALE ---- ->> Describe a file workload likely to benefit from buffer caching, and ->> workloads likely to benefit from read-ahead and write-behind. +>> C7: Describe a file workload likely to benefit from buffer caching, +>> and workloads likely to benefit from read-ahead and write-behind. SURVEY QUESTIONS ================ diff --git a/doc/userprog.tmpl b/doc/userprog.tmpl index a8b4269..1cf7ed7 100644 --- a/doc/userprog.tmpl +++ b/doc/userprog.tmpl @@ -26,87 +26,90 @@ FirstName LastName ---- DATA STRUCTURES ---- ->> Copy here the declaration of each new or changed `struct' or `struct' ->> member, global or static variable, `typedef', or enumeration. ->> Identify the purpose of each in 25 words or less. +>> A1: Copy here the declaration of each new or changed `struct' or +>> `struct' member, global or static variable, `typedef', or +>> enumeration. Identify the purpose of each in 25 words or less. ---- ALGORITHMS ---- ->> Briefly describe how you implemented argument parsing. How do you ->> arrange for the elements of argv[] to be in the right order? How do ->> you avoid overflowing the stack page? +>> A2: Briefly describe how you implemented argument parsing. How do +>> you arrange for the elements of argv[] to be in the right order? +>> How do you avoid overflowing the stack page? ---- RATIONALE ---- ->> Why does Pintos implement strtok_r() but not strtok()? +>> A3: Why does Pintos implement strtok_r() but not strtok()? ->> In Pintos, the kernel separates commands into a executable name and ->> arguments. In Unix-like systems, the shell does this separation. ->> Identify at least two advantages of the Unix approach. +>> A4: In Pintos, the kernel separates commands into a executable name +>> and arguments. In Unix-like systems, the shell does this +>> separation. Identify at least two advantages of the Unix approach. SYSTEM CALLS ============ ---- DATA STRUCTURES ---- ->> Copy here the declaration of each new or changed `struct' or `struct' ->> member, global or static variable, `typedef', or enumeration. ->> Identify the purpose of each in 25 words or less. +>> B1: Copy here the declaration of each new or changed `struct' or +>> `struct' member, global or static variable, `typedef', or +>> enumeration. Identify the purpose of each in 25 words or less. ->> Describe how file descriptors are associated with open files. Are ->> file descriptors unique within the entire OS or just within a single ->> process? +>> B2: Describe how file descriptors are associated with open files. +>> Are file descriptors unique within the entire OS or just within a +>> single process? ---- ALGORITHMS ---- ->> Describe your code for reading and writing user data from the kernel. - ->> Suppose a system call causes a full page (4,096 bytes) of data to be ->> copied from user space into the kernel. What is the least and the ->> greatest possible number of inspections of the page table (e.g. calls ->> to pagedir_get_page()) that might result? What about for a system ->> call that only copies 2 bytes of data? Is there room for improvement ->> in these numbers, and how much? - ->> Briefly describe your implementation of the "wait" system call and how ->> it interacts with process termination. - ->> Any access to user program memory at a user-specified address can fail ->> due to a bad pointer value. Such accesses must cause the process to ->> be terminated. System calls are fraught with such accesses, e.g. a ->> "write" system call requires reading the system call number from the ->> user stack, then each of the call's three arguments, then an arbitrary ->> amount of user memory, and any of these can fail at any point. This ->> poses a design and error-handling problem: how do you best avoid ->> obscuring the primary function of code in a morass of error-handling? ->> Furthermore, when an error is detected, how do you ensure that all ->> temporarily allocated resources (locks, buffers, etc.) are freed? In ->> a few paragraphs, describe the strategy or strategies you adopted for +>> B3: Describe your code for reading and writing user data from the +>> kernel. + +>> B4: Suppose a system call causes a full page (4,096 bytes) of data +>> to be copied from user space into the kernel. What is the least +>> and the greatest possible number of inspections of the page table +>> (e.g. calls to pagedir_get_page()) that might result? What about +>> for a system call that only copies 2 bytes of data? Is there room +>> for improvement in these numbers, and how much? + +>> B5: Briefly describe your implementation of the "wait" system call +>> and how it interacts with process termination. + +>> B6: Any access to user program memory at a user-specified address +>> can fail due to a bad pointer value. Such accesses must cause the +>> process to be terminated. System calls are fraught with such +>> accesses, e.g. a "write" system call requires reading the system +>> call number from the user stack, then each of the call's three +>> arguments, then an arbitrary amount of user memory, and any of +>> these can fail at any point. This poses a design and +>> error-handling problem: how do you best avoid obscuring the primary +>> function of code in a morass of error-handling? Furthermore, when +>> an error is detected, how do you ensure that all temporarily +>> allocated resources (locks, buffers, etc.) are freed? In a few +>> paragraphs, describe the strategy or strategies you adopted for >> managing these issues. Give an example. ---- SYNCHRONIZATION ---- ->> The "exec" system call returns -1 if loading the new executable fails, ->> so it cannot return before the new executable has completed loading. ->> How does your code ensure this? How is the load success/failure ->> status passed back to the thread that calls "exec"? +>> B7: The "exec" system call returns -1 if loading the new executable +>> fails, so it cannot return before the new executable has completed +>> loading. How does your code ensure this? How is the load +>> success/failure status passed back to the thread that calls "exec"? ->> Consider parent process P with child process C. How do you ensure ->> proper synchronization and avoid race conditions when P calls wait(C) ->> before C exits? After C exits? How do you ensure that all resources ->> are freed in each case? How about when P terminates without waiting, ->> before C exits? After C exits? Are there any special cases? +>> B8: Consider parent process P with child process C. How do you +>> ensure proper synchronization and avoid race conditions when P +>> calls wait(C) before C exits? After C exits? How do you ensure +>> that all resources are freed in each case? How about when P +>> terminates without waiting, before C exits? After C exits? Are +>> there any special cases? ---- RATIONALE ---- ->> Why did you choose to implement access to user memory from the +>> B9: Why did you choose to implement access to user memory from the >> kernel in the way that you did? ->> What advantages or disadvantages can you see to your design for file ->> descriptors? +>> B10: What advantages or disadvantages can you see to your design +>> for file descriptors? ->> The default tid_t to pid_t mapping is the identity mapping. If you ->> changed it, what advantages are there to your approach? +>> B11: The default tid_t to pid_t mapping is the identity mapping. +>> If you changed it, what advantages are there to your approach? SURVEY QUESTIONS ================ diff --git a/doc/vm.tmpl b/doc/vm.tmpl index aef4fb8..987e057 100644 --- a/doc/vm.tmpl +++ b/doc/vm.tmpl @@ -26,106 +26,109 @@ FirstName LastName ---- DATA STRUCTURES ---- ->> Copy here the declaration of each new or changed `struct' or `struct' ->> member, global or static variable, `typedef', or enumeration. ->> Identify the purpose of each in 25 words or less. +>> A1: Copy here the declaration of each new or changed `struct' or +>> `struct' member, global or static variable, `typedef', or +>> enumeration. Identify the purpose of each in 25 words or less. ---- ALGORITHMS ---- ->> Describe your code for locating the frame, if any, that contains ->> the data of a given page. +>> A2: Describe your code for locating the frame, if any, that +>> contains the data of a given page. ->> How does your code coordinate accessed and dirty bits between +>> A3: How does your code coordinate accessed and dirty bits between >> kernel and user virtual addresses that alias a single frame, or >> alternatively how do you avoid the issue? ---- SYNCHRONIZATION ---- ->> When two user processes both need a new frame at the same time, how ->> are races avoided? +>> A4: When two user processes both need a new frame at the same time, +>> how are races avoided? ---- RATIONALE ---- ->> Why did you choose the data structure(s) that you did for representing ->> virtual-to-physical mappings? +>> A5: Why did you choose the data structure(s) that you did for +>> representing virtual-to-physical mappings? PAGING TO AND FROM DISK ======================= ---- DATA STRUCTURES ---- ->> Copy here the declaration of each new or changed `struct' or `struct' ->> member, global or static variable, `typedef', or enumeration. ->> Identify the purpose of each in 25 words or less. +>> B1: Copy here the declaration of each new or changed `struct' or +>> `struct' member, global or static variable, `typedef', or +>> enumeration. Identify the purpose of each in 25 words or less. ---- ALGORITHMS ---- ->> When a frame is required but none is free, some frame must be +>> B2: When a frame is required but none is free, some frame must be >> evicted. Describe your code for choosing a frame to evict. ->> When a process P obtains a frame that was previously used by a +>> B3: When a process P obtains a frame that was previously used by a >> process Q, how do you adjust the page table (and any other data >> structures) to reflect the frame Q no longer has? ->> Explain your heuristic for deciding whether a page fault for an ->> invalid virtual address should cause the stack to be extended into the ->> page that faulted. +>> B4: Explain your heuristic for deciding whether a page fault for an +>> invalid virtual address should cause the stack to be extended into +>> the page that faulted. ---- SYNCHRONIZATION ---- ->> Explain the basics of your VM synchronization design. In particular, ->> explain how it prevents deadlock. (Refer to the textbook for an ->> explanation of the necessary conditions for deadlock.) +>> B5: Explain the basics of your VM synchronization design. In +>> particular, explain how it prevents deadlock. (Refer to the +>> textbook for an explanation of the necessary conditions for +>> deadlock.) ->> A page fault in process P can cause another process Q's frame to be ->> evicted. How do you ensure that Q cannot access or modify the page ->> during the eviction process? How do you avoid a race between P ->> evicting Q's frame and Q faulting the page back in? +>> B6: A page fault in process P can cause another process Q's frame +>> to be evicted. How do you ensure that Q cannot access or modify +>> the page during the eviction process? How do you avoid a race +>> between P evicting Q's frame and Q faulting the page back in? ->> Suppose a page fault in process P causes a page to be read from the ->> file system or swap. How do you ensure that a second process Q +>> B7: Suppose a page fault in process P causes a page to be read from +>> the file system or swap. How do you ensure that a second process Q >> cannot interfere by e.g. attempting to evict the frame while it is >> still being read in? ->> Explain how you handle access to paged-out pages that occur during ->> system calls. Do you use page faults to bring in pages (as in user ->> programs), or do you have a mechanism for "locking" frames into ->> physical memory, or do you use some other design? How do you +>> B8: Explain how you handle access to paged-out pages that occur +>> during system calls. Do you use page faults to bring in pages (as +>> in user programs), or do you have a mechanism for "locking" frames +>> into physical memory, or do you use some other design? How do you >> gracefully handle attempted accesses to invalid virtual addresses? ---- RATIONALE ---- ->> A single lock for the whole VM system would make synchronization easy, ->> but limit parallelism. On the other hand, using many locks ->> complicates synchronization and raises the possibility for deadlock ->> but allows for high parallelism. Explain where your design falls ->> along this continuum and why you chose to design it this way. +>> B9: A single lock for the whole VM system would make +>> synchronization easy, but limit parallelism. On the other hand, +>> using many locks complicates synchronization and raises the +>> possibility for deadlock but allows for high parallelism. Explain +>> where your design falls along this continuum and why you chose to +>> design it this way. MEMORY MAPPED FILES =================== ---- DATA STRUCTURES ---- ->> Copy here the declaration of each new or changed `struct' or `struct' ->> member, global or static variable, `typedef', or enumeration. ->> Identify the purpose of each in 25 words or less. +>> C1: Copy here the declaration of each new or changed `struct' or +>> `struct' member, global or static variable, `typedef', or +>> enumeration. Identify the purpose of each in 25 words or less. ---- ALGORITHMS ---- ->> Describe how memory mapped files integrate into your virtual memory ->> subsystem. Explain how the page fault and eviction processes differ ->> between swap pages and other pages. +>> C2: Describe how memory mapped files integrate into your virtual +>> memory subsystem. Explain how the page fault and eviction +>> processes differ between swap pages and other pages. ->> Explain how you determine whether a new file mapping overlaps any ->> existing segment. +>> C3: Explain how you determine whether a new file mapping overlaps +>> any existing segment. ---- RATIONALE ---- ->> Mappings created with "mmap" have similar semantics to those of data ->> demand-paged from executables, except that "mmap" mappings are written ->> back to their original files, not to swap. This implies that much of ->> their implementation can be shared. Explain why your implementation ->> either does or does not share much of the code for the two situations. +>> C4: Mappings created with "mmap" have similar semantics to those of +>> data demand-paged from executables, except that "mmap" mappings are +>> written back to their original files, not to swap. This implies +>> that much of their implementation can be shared. Explain why your +>> implementation either does or does not share much of the code for +>> the two situations. SURVEY QUESTIONS ================ -- 2.30.2