Student ID
Login (studentXXX)
Computer Science 162 . of California, Berkeley Final Exam
December 17, 2019
Copyright By PowCoder代写 加微信 powcoder
TA Name and Section Time
Name of Students to your Left and Right
Name of Students in Front of You and Behind You
This is a closed-book exam with two 2-sided handwritten pages of notes permitted. It is intended to be a 110 minute exam. You have 170 minutes to complete it. The number at the beginning of each question indicates the points for that question. Write all of your answers directly on this exam. Make your answers as concise as possible. If there is something in a question that you believe is open to interpretation, please raise your hand to request clarification. When told to open the exam, put your Student ID on every page and check that you have them all. The final pages are for reference.
By my signature below, I swear that this exam is my own work. I have not obtained answers or partial answers from anyone, and I have not discussed it with anyone who took the early alternate exam.
X _______________________________________
Grade Table (for instructor use only)
Question: 1 2 3 4 5 6 7 8 9 Total Points: 1 24 20 10 9 12 14 18 0 108 Score:
Final Exam – Page 2 of 24 Student ID:
1. (1 point) Miscellaneous Questions
(a) (1 point) Write your Student ID on every page of the exam.
(b) (1 bonus point) You will receive one point for completing the CS 162 Exit Survey.
(c) (1 bonus point) The winners of the Pintos Music Contest will each receive one point.
Final Exam – Page 3 of 24 Student ID:
2. (24 points) Operating System Concepts: True/False
Choose True or False for the questions below. You do not need to justify your answers.
(a) (1 point) If a process attempts to open and read a file it does not have permission to access, then the read system call will fail with the error EACCES (“Permission denied”).
⃝ True √ False
(b) (1 point) If a fair scheduler, like Linux CFS, strives to meet a responsiveness target T by giving each task a quantum of T divided by the number of tasks, then the minimum granularity may cause it to exceed the target latency with a large number of tasks.
√ True ⃝ False
(c) (1 point) Increasing the size of a cache will increase its hit rate under any workload and
eviction policy.
⃝ True √ False
(d) (1 point) A single memory access may result in a TLB hit and a cache miss. √ True ⃝ False
(e) (1 point) As a system’s workload is increased past the half-power point, causing it to approach 100% utilization, response time typically increases due to queuing delays.
√ True ⃝ False
(f) (1 point) LRU is an appropriate policy to evict page frames for demand paging.
⃝ True √ False
(g) (1 point) In the x86 architecture, a TLB miss results in a trap to the operating system,
which walks the page table in software to retrieve the page table entry. ⃝ True √ False
(h) (1 point) A user program may interact with I/O devices by reading and writing to memory addresses reserved for memory-mapped I/O.
⃝ True √ False
(i) (1 point) In a typical file system, large files account for most in-use disk space.
√ True ⃝ False
(j) (1 point) The compiled kernel code exists as a file in the file system at a known inumber.
⃝ True √ False
(k) (1 point) The FAT file system supports hard links.
⃝ True √ False
(l) (1 point) In a Unix FFS-style inode-based file system, there is no limit on how large a file can be, except for the size of the underlying storage device. (Ignore any limits due to a fixed-size “file length” field.)
⃝ True √ False
(m) (1 point) In the Windows NTFS file system, a small file’s data may be stored directly in
the master file record, without any direct or indirect block pointers. √ True ⃝ False
(n) (1 point) The low-level file API (read, write) is accelerated by the kernel’s buffer cache. √ True ⃝ False
Final Exam – Page 4 of 24 Student ID:
(o) (1 point) The Transmission Control Protocol (TCP) allows each endpoint of a connection to have at most one outstanding unACKed packet at a time.
⃝ True √ False
(p) (1 point) In NFS and the System (AFS), a user’s modifications to a file must
become visible to other users in the system as soon as the write operation completes. ⃝ True √ False
(q) (1 point) A group of machines can use the Two-Phase Commit (2PC) protocol to guarantee that they will perform a task atomically, i.e., either all or none.
√ True ⃝ False
(r) (1 point) The Domain Name System (DNS) uses consistent hashing to partition the global
set of DNS records across all machines in the system. ⃝ True √ False
(s) (1 point) The virtual machine monitor uses the host OS managed page table to ensure that writes to the guest page table trap and the VMM is able to update both the guest and shadow page tables.
⃝ True √ False
(t) Containers handle package dependences for collections of processes, whereas Kubernetes introduces Pods as a mechanism for co-locating a related set of containers on a set of (virtualized) resources.
√ True ⃝ False
(u) (1 point) Containers and virtual machines both isolate a collection of processes from all
the rest of the processes. √ True ⃝ False
(v) (1 point) The socket abstraction is dictated by the transport layer of the network stack to allow a client and a server to communicate over HTTP.
⃝ True √ False
(w) (1 point) The total number of virtual pages is never greater than the total number of
physical page frames. ⃝ True √ False
(x) (1 point) A distributed key/value store can use a master directory server to direct client put/get requests to multiple replicas.
√ True ⃝ False
Final Exam – Page 5 of 24 Student ID:
3. (20 points) Operating System Concepts: Short Answer
There are 24 points of questions below. You must answer 20 points worth of questions. Clearly
cross out or leave blank the ones that should not be graded.
Fill in the blanks correctly for the questions below. You do not need to provide justifications.
(a) (1 point) A process may request the operating system to perform a privileged action on
its behalf by issuing a/an system call .
(b) (1 point) Stride Scheduling (or CFS) is a scheduling algorithm that is based on a similar
principle as Lottery Scheduling, but is not based on randomness.
(c) (1 point) The subset of its virtual address space that a process is actively using over a
given time interval is called a/an working set .
(d) (1 point) To evict a page to disk, the operating system finds which page table entries map
to pages that are not recently used .
(e) (1 point) A transaction is a/an atomic sequence of reads/writes.
(f) (1 point) A group of n machines can maintain safety and liveness in the face of fail-stop failures as long as at least a majority of (or ⌈n+1⌉) node(s) is/are not faulty.
Write an answer in the box provided for each of the questions below.
(g) (2 points) Components of a file system
i. (1 point) What are the four components of a file system?
Solution: Directory Structure, Index, Storage Blocks, and Free Blocks
ii. (1 point) Which component(s) of a file system might the kernel access to handle an open system call? Assume the file path corresponds to a regular file that already exists (not an I/O device, directory, or soft link).
Solution: Directory Structure and Index
(h) (2 points) In the scheme discussed in class, explain why it is not necessary
to undo any operations in the log when recovering after a crash.
Solution: All operations written to the log are idempotent, so it is safe to redo them even if they were executed before the crash or in a previous recovery attempt.
(i) (2 points) The concept of dispatch—passing a request to the appropriate request handler for processing—arises in a variety of systems. Give two examples of dispatch in software systems that we studied in class.
Solution: Any two of the following would receive full credit: interrupt vector table, system call handler, RPC/HTTP server, and Linux VFS. Other examples are vtables (polymorphism), opcode dispatch in interpreters, and protocol dispatch in networks.
Final Exam – Page 6 of 24 Student ID:
(j) (3 points) Before you build a buffer cache, you run measurements and find that on average it takes 10 ms to perform each file operation. With the buffer cache, you can perform an operation in 1 ms when it does not have to go to disk. What fraction of the operations must be serviced by the buffer cache for the average operation time to be below 2 ms?
Solution: 10(1−x)+x < 2 =⇒ x > 8. We also accepted 9 , as the problem can 9 10
also be read as including the 1 ms on cache misses. We stated a clarification for this at the exam, but ultimately we decided to accept both answers.
(k) (1 point) How will your buffer cache influence the I/O queuing delays experienced by applications?
Solution: It will decrease I/O queueing delays because the bandwidth is higher and the latency lower for the buffer cache.
(l) (2 points) In distributed file systems, like AFS and NFS, which component is responsible for providing consistency?
Solution: The server is responsible for notifying clients when data they may have cached has been overwritten by another client.
(m) (2 points) When either the client or server closes a connection socket, how is the other party notified? How do they reach agreement to close?
Solution: One notifies the other with a FIN message. They agree by each sending a FIN-ACK.
(n) (2 points) In order for complex data objects to be passed as arguments or results in an RPC over a socket to a possibly remote machine, what needs to be done to the data?
Solution: It needs to be serialized into a canonical form that can be reconstructed by the other participant.
(o) (2 points) What should a client do after establishing a TCP connection with a server, but before sending user identity and password over that connection?
Solution: It should (1) verify the identity of the server it is connecting to, and (2) establish a secure channel over the TCP connection.
Final Exam – Page 7 of 24 Student ID:
4. (10 points) Pintos
Choose True or False for the questions below according to Pintos, the operating
system you used in the projects for this class. You do not need to justify your answers.
(a) (1 point) Accesses to kernel memory (PHYS_BASE and above) in the system call handler and interrupt handlers operate directly on physical addresses, bypassing all page tables.
⃝ True √ False
(b) (1 point) It is inherently unsafe to call sema_down on a zero-value semaphore in a thread
while interrupts are disabled. ⃝ True √ False
(c) (1 point) Interrupts are disabled while Pintos switches threads (i.e., while executing the switch_threads function).
√ True ⃝ False
(d) (1 point) On a successful call to pagedir_clear_page, Pintos flushes the TLB.
√ True ⃝ False
(e) (1 point) The physical address corresponding to a kernel virtual address can be computed
by subtracting PHYS_BASE. √ True ⃝ False
(f) (1 point) If two processes simultaneously hold open file descriptors corresponding to the same file, then two instances of an in-memory inode exist for that file.
⃝ True √ False
Answer the questions below according to Pintos, the operating system you used in the
projects for this class. You do not need to justify your answers.
(g) (1 point) If Pintos is implemented with a global lock around the file system, as in Project 1, what is the maximum number of outstanding disk requests at any one time?
(h) (1 point) If Pintos is implemented with a 64-sector buffer cache without a global lock, as
in Project 3, what is the maximum number of outstanding disk requests at any one time? (h) 64
(i) (1 point) When scheduling timer expires, causing the timer_interrupt function to be invoked, in which stack does the timer_interrupt function execute?
Solution: It executes in the kernel stack of the currently running thread.
(j) (1 point) While a process executes in userspace, what is stored on its kernel stack?
Solution: While a process executes in userspace, its kernel stack is empty. (Mentioning setup stack frames left on the process’ kernel stack when switching to userspace for the first time for that process is OK.)
Final Exam – Page 8 of 24 Student ID:
5. (9 points) Multi-Threaded Processes
In the CS 162 projects, each Pintos process consists of a single thread of execution. Suppose now that we want to make processes in Pintos multi-threaded. We will represent a process control blockusingstruct processandwewillrepresentathreadcontrolblockusingstruct thread.
(a) (1 point) How must the exit system call change to handle multi-threaded processes? Solution: If a thread issues an exit system call, then that thread, and all other threads
in its process, should exit.
(b) (5 points) Fill in struct thread and struct process below. Here are some guidelines:
• Account for each field in the current struct thread (see detachable reference material for this definition).
• Your design should support the full lifecycle of a thread/process: creation, system call/page fault handling, and exit.
struct thread {
tid_t tid;
enum thread_status status;
uint8_t* stack;
int priority;
struct list_elem allelem;
struct list_elem elem;
struct list_elem processelem;
struct process* process;
unsigned magic;
⃝ struct thread only √ struct process only ⃝ both structs
(d) (1 point) Suppose we would like to implement non-busy-waiting sleep in this system, as
you did in Project 2. Which structure(s) must you modify to implement this? √ struct thread only ⃝ struct process only ⃝ both structs
struct process {
pid_t pid;
char name[16];
uint32_t* pagedir;
struct list threads;
struct lock process_lock;
(c) (1 point) Suppose we would like to implement file descriptors in this system, as you did in Project 1. Which structure(s) must you modify to implement this?
(e) (1 point) Suppose we would like to implement a current working directory in this system, as you did in Project 3. Which structure(s) must you modify to implement this?
⃝ struct thread only √ struct process only ⃝ both structs
Final Exam – Page 9 of 24 Student ID:
Commentary:
The int priority; and char name[16]; field can go in either struct or be omitted en- tirely (the name isn’t strictly needed, and the priority is not used by the default scheduler).
Our purpose in asking about the exit system call at the beginning is to help you realize that you need a way to read the struct process given the struct thread, and also a way to read the struct threads for a given struct process. This motivates our example solution where each struct holds a reference to the other. If struct list_elem allelem; is placed in struct thread, then you need a struct process* process; field in struct thread. If struct list_elem allelem; is placed in struct process, then you need a
struct list_elem processelem; in struct thread and a struct list threads; in struct process. Having both a process pointer in struct thread (or a PID field) and a list of threads in struct process is the most efficient solution, but not strictly necessary since you could iterate over all the all thread list. unsigned magic; must be the last field in struct thread. Finally, a lock is needed in struct process to synchronize process state when accessed by the threads in that process.
Final Exam – Page 10 of 24 Student ID:
6. (12 points) Inode Design
Alice, Benjamin, Catherine, and David would like to design a file system for Pintos as follows. The on-disk inode has 10 direct pointers. The inode does not have any indirect pointers, but instead may point to another on-disk inode, which provides links to the remaining bytes of the file. The inode that it points to may point to yet another inode, and so on. Note that an inode may point to another inode even if it is not completely full. This does not mean that the file is sparse, only that the remaining bytes in the inode are unused.
(a) (1 point) What is the size, in bytes, of the largest file that can be represented by a single inode, without using a pointer to another inode?
(a) 5120 (or 10 * BLOCK_SECTOR_SIZE)
(b) (1 point) List an access pattern that this inode structure supports efficiently.
Solution: Sequential reads and writes through a file.
(c) (1 point) List one similarity between this inode structure and Windows NTFS.
Solution: For fragmented files in NTFS, Master File Table Records are linked to- gether, like inodes in this structure.
(d) (1 point) List one difference between this inode structure and Windows NTFS.
Solution: Whereas each inode in this structure has direct pointers, Master File Table Records in NTFS can store data in extents.
(e) (2 points) Complete struct inode_disk for this design. Do not assume any useful file data is stored in the magic or unused fields. You may not need all of the blank lines. Ensure that sizeof(struct inode_disk) == BLOCK_SECTOR_SIZE. Note that off_t is defined as follows: typedef int32_t off_t;.
struct inode_disk {
off_t length; // length of data in THIS inode, not including linked inodes
uint32_t isdir;
block_sector_t direct[10];
block_sector_t linked; // inumber of linked inode
unsigned magic;
uint8_t unused[ BLOCK_SECTOR_SIZE – (4 + 4 + 40 + 4 + 4) ]; };
Final Exam – Page 11 of 24 Student ID:
(f) (6 points) The group is using the following in-memory inode structure. Note that there is no bounce buffer within the in-memory inode (this is different from the Pintos starter code, which has the struct inode_disk data; element in struct inode). struct inode {
struct list_elem elem;
block_sector_t sector;
int open_cnt;
bool removed;
int deny_write_cnt;
/* Element in inode list. */
/* Sector number of disk location. */
/* Number of openers. */
/* True if deleted, false otherwise. */
/* 0: writes ok, >0: deny writes. */
Based on this information, implement byte_to_sector for this group’s inode design.
• Assume the syscall handler acquires a global file system lock, as in Project 1.
• You may call read/write from disk directly; do not use a buffer cache.
• Assume there is enough stack space to store a buffer of BLOCK_SECTOR_SIZE bytes. • Assume that files are not sparse.
/* Returns the block device sector that contains byte offset POS
within a file. Returns INVALID_SECTOR if the file does not contain
data for a byte at offset POS (e.g., POS is past the end of file). */
block_sector_t byte_to_sector(const struct inode *inode, off_t pos) {
ASSERT(inode != NULL);
block_sector_t rv = INVALID_SECTOR;
struct inode_disk bounce;
block_read(fs_device, inode->sector, &bounce);
while ( pos >= bounce.length ) { if (bounce.linked == INVALID_SECTOR) {
return rv; // end of file
pos -= bounce.length;
block_read(fs_device, bounce.linked, &bounce);
rv = bounce.direct[pos / BLOCK_SECTOR_SIZE];
return rv; }
Final Exam – Page 12 of 24 Student ID:
7. (14 points) Condition Variables
Condition variables in the Pintos starter code are implemented using semaphores, and semaphores are implemented directly. In this problem, you will implement condition variables directly, without using semaphores.
Your condition variable should work in the same way as the existing implementation in Pintos (i.e., Mesa semantics). Your implementation does not have to work with priority scheduling (Project 2).
(a) (2 points) First, define struct condition and cond_init appropriately. struct condition {
struct list waiters;
void cond_init(struct condition* cond) {
ASSERT(cond != NULL);
list_init(&cond->waiters);
(b) (5 points) Implement cond_wait. Do not use semaphores.
void cond_wait(struct condition* cond, struct lock* lock) {
ASSERT(cond != NULL);
ASSERT(lock != NULL);
ASSERT(!intr_context());
ASSERT(lock_held_by_current_thread(lock));
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com