CS代考 CS162: Operating Systems and Systems Programming

Spring 2022
University of California, Berkeley College of Engineering Computer Science Division  EECS
Joseph & Kubiatowicz
February 17th, 2022

CS162: Operating Systems and Systems Programming
Your Name:
SID AND Autograder Login (e.g. student042):
Discussion Section Time:
General Information:
This is a closed book exam. You are allowed 1 page of notes (both sides). You may use a calculator. You have 110 minutes to complete as much of the exam as possible. Make sure to read all of the questions first, as some of the questions are substantially more time consuming.
PLEASE WRITE YOUR ANSWERS ON THE ANSWER SHEET, NOT IN-LINE HERE. Make your answers as concise as possible. On programming questions, we will be looking for performance as well as correctness, so think through your answers carefully. If there is something about the questions that you believe is open to interpretation, please ask us about it!
Problem Possible Score
1 18 2 16 3 12 4 23 5 15 6 16

CS 162 Spring 2022 Midterm I SOLUTION
February 17th, 2022
[ This page left for  ] 3.14159265358979323846264338327950288419716939937510582097494459230781640628620899

CS 162 Spring 2022 Midterm I SOLUTION February 17th, 2022
Problem 1: True/False [18 pts]
Please EXPLAIN your answer in TWO SENTENCES OR LESS (Answers longer than this may not
get credit!). Also, answers without an explanation GET NO CREDIT.
Problem 1a[2pts]: If Thread A and B are in the same process, then Thread A can access local
variables stored in Thread B’s stack. True ⬜ False
Explain: Since both threads are in the same process, they share the same address space. Thus, assuming that Thread A can get an address of a local variable on Thread B’s stack, then it can
read it or write it. Note, that this fact doesn’t mean that it is a good idea to program this way! Problem 1b[2pts]: Let n be the size of the virtual address space. On a fork() call, the OS does
O(n) work to duplicate the parent’s address space for the child process. True ⬜ False
Explain:The OS copies all of the parent’s page table entries (to perform copy-of-write), which
mostly scales with the size of the parent’s virtual address space. Note, however, that the question does say “virtual address space.” So, if the virtual address space is very sparsely populated (most of the virtual space is not mapped to actual physical addresses), then multi-level page tables would not have a number of page table entries that scale directly with the size of the virtual address space. If you point this out, we will take “False” as an answer.
Problem 1c[2pts]: Trying to use lseek() on file descriptor #1 will always result in an error. ⬜ True  False
Explain: Descriptor #1 is for stdout. While it is true the lseek() on the default (terminal) output will cause an error, the user can use dup2() to change stdout to refer to a file, which can
accept lseek() operations.
Problem 1d[2pts]: A child process can communicate with its parent by utilizing a data structure on
its heap that was allocated before the parent performed a fork() system call. ⬜ True  False
Explain: Since child and parent have different address spaces, their heaps are distinct. Any
object allocated on the heap before executing fork(), will be copied into the child, but will not be shared between parent and child; or, in other words, a write to the object by the parent will only alter the parents copy of the object and will not affect the child’s copy in any way.
Problem 1e[2pts]: If we have a queue of multiple waiters on a condition variable with Mesa scheduling, and we execute a cond_broadcast(), the waiters would be processed in FIFO order.
⬜ True  False
Explain: The typically implementation of cond_broadcast() makes no guarantees on the
order in which threads are woken up. And, even if they were, there is no guarantee that they will reacquire the lock in the any order related to their original sleeping order.

CS 162 Spring 2022 Midterm I SOLUTION February 17th, 2022
Problem 1f[2pts]: There are situations where disabling interrupts must be used as opposed to other synchronization primitives.
True ⬜ False
Explain: Whenever code is modifying structures that could be altered by an interrupt handler,
then it must disabled interrupts to avoid corrupting the data structures. A good example is the basic scheduling queues which can get altered by the timer interrupt.
Problem 1g[2pts]: Inside the Pintos kernel, we can find the struct thread of the current running thread by rounding down %esp to the nearest page boundary.
True ⬜ False
Explain: The Pintos kernel allocates a page-sized structure in the kernel for each new thread. This 4K page has the TCB at the beginning of the page and uses the rest of the page for a kernel stack. Consequently, taking the stack point ( %esp) and rounding it down to the nearest page boundary will find a pointer to the beginning of the page, which holds the TCB.
Problem 1h[2pts]: The FPU registers must be saved and restored on every entry into the kernel. ⬜ True  False
Explain: Since the kernel doesn’t really use the FPU for anything, we don’t need to
save the FPU registers unless we are context switching. We would do that by pushing them on the kernel stack before we begin the context switch. What this means, is that typical system calls, interrupts, or exceptions that will return to the current user can just leave the FPU registers alone.
Problem 1i[2pts]: Context switching is implemented in Pintos by swapping user stacks. ⬜ True  False
Explain: Context switching is accomplished by swapping kernel stacks, not user
stacks. The reason this works is that the user stack is in (user) memory and the user stack pointer is pushed on the kernel stack automatically on entry to the kernel. Consequently, swapping the kernel stack will implicitly swap out the user stack.

CS 162 Spring 2022 Midterm I SOLUTION February 17th, 2022
Problem 2: Multiple Choice [16pts]
Problem 2a[2pts]: Which of the following are true about syscalls in Pintos? (choose all that
apply): A:⬜
B:  C:⬜ D:
User programs directly call the syscall functions in the file src/userprog/syscall.c.
Arguments passed into system calls must be validated before they are used.
Syscalls in Pintos are run in user mode.
The wait syscall returns the exit code of the child process specified in the argument to the function.
None of the above.
Problem 2b[2pts]: What are some reasons that overuse of threads is bad (i.e. using too many threads at the same time in a single process)? (choose all that apply):
The thread name-space becomes too large and fragmented, making it very difficult to efficiently track the current executing thread.
The overhead of switching between too many threads can waste processor cycles such that the overhead outweighs actual computation (i.e. thrashing)
Excessive threading can waste memory for stacks and TCBs
The number of page tables becomes too large, thus overloading the virtual memory mechanisms.
Problem 2c[2pts]: What are the disadvantages of disabling interrupts to serialize access to a critical
section? A: 
B: ⬜ C:  D:  E:
(choose all that apply):
User code cannot utilize this technique for serializing access to critical sections.
Interrupt controllers have a limited number of physical interrupt lines, thereby making it problematic to allocate them exclusively to critical sections.
This technique would lock out other hardware interrupts, potentially causing critical events to be missed.
This technique is a very coarse-grained method of serializing, yielding only one such lock for each core.
This technique could not be used to enforce a critical section on a multiprocessor.
All of the above.

CS 162 Spring 2022 Midterm I SOLUTION February 17th, 2022
Problem 2d[2pts]: In Pintos, every user thread is matched with a corresponding kernel thread (complete with a kernel stack). What is true about this arrangement (choose all that apply):
C:  D:⬜ E: 
When the user-thread makes a system call that must block (e.g. a read to a file that must go to disk), the thread can be blocked at any time by putting the kernel thread (with its stack) to sleep and waking another kernel thread (with its stack) from the ready queue.
The presence of the matched kernel thread makes the user thread run twice as fast as it would otherwise.
The kernel thread helps to make sure that the page table is constructed properly so that the user thread’s address space is protected from threads in other processes.
While user code is running, the kernel thread manages cached data from the file system to make sure the most recent items are stored in the cache and ready when the user needs them.
The kernel gains safety because it does not have to rely on the correctness of the user’s stack pointer register for correct behavior.
Problem 2e[2pts]: What are some disadvantages of Base&Bound style address translation? (choose all that apply):
Base&Bound cannot protect kernel memory from being read by user programs. Sharing memory between processes is difficult.
Context switches incur a much higher overhead compared to use of a page table. Base&Bound will lead to external fragmentation.
With Base&Bound, each process can have its own version of address “0”.
Problem 2f[2pts]: Which of the following are true about condition variables? (choose all that apply):
A:⬜ B:  C:⬜ D:  E:⬜
B:⬜ C:⬜ D: ⬜
cond_wait(), and cond_signal() can only be used when holding the lock associated with the condition variable.
In practice, Hoare semantics are used more often than Mesa semantics. Mesa semantics will lead to busy waiting in cond_wait().
cond_signal() can only be called after setting the boolean condition associated with the condition variable to true.
All of the above.

CS 162 Spring 2022 Midterm I SOLUTION February 17th, 2022
Problem 2g[2pts]: Consider the following pseudocode implementation of a lock_acquire(). lock_acquire() {
interrupt_disable();
if (value == BUSY) {
put thread on wait queue;
Go to sleep();
value = BUSY;
interrupt_enable();
Which of the following are TRUE? Assume we are running on a uniprocessor/single-core machine. (choose all that apply):
For this implementation to be correct, we should call interrupt_enable() before sleeping.
For this implementation to be correct, we should call interrupt_enable() before putting the thread on the wait queue.
For this implementation to be correct, sleep() should trigger the scheduler and the next scheduled thread should enable interrupts.
It is possible for this code to be run in user mode. None of the above.
Problem 2h[2pts]: Which of the following statements about files are true? (choose all that apply):
The same file descriptor number can correspond to different files for different processes.
The same file descriptor number can correspond to different files for different threads in the same process
Reserved 0, 1, and 2 (stdin, stdout, stderr) file descriptors cannot be overwritten by a user program.
File descriptions keep track of the file offset.
An lseek() within one process may be able to affect the writing position for another process.

CS 162 Spring 2022 Midterm I SOLUTION February 17th, 2022 Problem 3: Readers-Writers Access to Database [12 pts]
Reader() {
//First check self into system
lock.acquire();
while ((AW + WW) > 0) {
okToRead.wait(&lock);
lock.release();
// Perform read access
AccessDatabase(ReadOnly);
// Now, check out of system
lock.acquire();
if (AR == 0 && WW > 0)
okToWrite.signal();
lock.release();
Writer() {
// First check self into system
lock.acquire();
while ((AW + AR) > 0) {
okToWrite.wait(&lock);
lock.release();
// Perform read/write access
AccessDatabase(ReadWrite);
// Now, check out of system
lock.acquire();
if (WW > 0){
okToWrite.signal();
} else if (WR > 0) {
okToRead.broadcast();
lock.release();
Problem 3a[2pts]: Above, we show the Readers-Writers example given in class. What are the correctness constraints described by the Reader/Writer model above? (Hint: When can writers/readers access the database)?
Readers can only access the database when there are no writers. Furthermore, writers can only access the database when there are no active readers or writers. In addition, we will accept that this code priorities writes over reads.
Problem 3b[2pts]: The above code uses two condition variables, one for waiting readers and one for waiting writers. Suppose that all of the following requests arrive in very short order (while R1 and R2 are still executing):
Incomingstream:R1 R2 W1R3 W2 W3R4 R5 R6 W4 R7W5 W6 R8 R9W7 R10
In what order would the above code process the above requests? If you have a group of requests that are equivalent (unordered), indicate this clearly by surrounding them with braces ‘{}’. You can assume that the wait queues for condition variables are FIFO in nature (i.e. signal() wakes up the oldest thread on the queue). Explain how you got your answer.
Since writes have priority over reads and writes must execute one at a time, we get: {R1, R2 }W1W2 W3W4W5 W6 W7 {R3 R4 R5 R6 R7R8 R9R10 }

CS 162 Spring 2022 Midterm I SOLUTION February 17th, 2022
NOTE: Each of the following subparts are independent. Describe in 2-3 sentences the conceptual changes needed to support the new feature, including the positions where the described logic should be added or changed.
Problem 3c[4pts]: Suppose we have now upgraded our storage system to Google Sheets, which can now handle multiple writers accessing the database at the same time. How do we modify the existing logic to have multiple writers access the database concurrently? Assume all other correctness constraints are the same.
Change the condition for writers to only check for active readers: (while AR > 0) in line 3 line of the Writer() code.
Also change all okToWrite.signal() to okToWrite.broadcast() in closing/checkout code at end of both Reader() and Writer() code.
Problem 3d[4pts]: Suppose funds have run low, and our database can only handle a certain number of readers at a time. How do we modify the logic so that at most 10 readers may access the database at any time?
Check the number of active readers in the condition check in line 3 of the Reader(): while ((AW + WW) > 0 || (AR >= 10))
Furthermore, in the Reader() closing/checkout, we need to see if there is a reader waiting for access if there aren’t any writers:
// Existing code here
if (AR == 0 && WW > 0)
okToWrite.signal();
// New code here
if (AR > 0)
okToRead.broadcast();
This modification may not be before the writer signal, as we still want to prioritize writers if there are any waiting writers.

CS 162 Spring 2022 Midterm I SOLUTION February 17th, 2022
Problem 4: Atomic Synchronization Primitives [23pts]
In class, we discussed a number of atomic hardware primitives that are available on modern
architectures. In particular, we discussed “test and set” (TSET), SWAP, and “compare and swap” (CAS). They can be defined as follows (let “expr” be an expression, “&addr” be an address of a memory location, and “M[addr]” be the actual memory location at address addr):
Test and Set (TSET) Atomic Swap (SWAP) Compare and Swap (CAS)
Both TSET and SWAP return values (from memory), whereas CAS returns either true or false. Note that our &addr notation is similar to a reference in c, and means that the &addr argument must be something that can be stored into. For instance, TSET could be used to implement a spin-lock acquire as follows:
int lock = 0; // lock is free
// Later: acquire lock
while (TSET(&lock));
CAS is general enough as an atomic operation that it can be used to implement both TSET and SWAP. For instance, consider the following implementation of TSET with CAS:
TSET(&addr) {
temp = M[addr];
} while (!CAS(addr,temp,1));
return temp;
Problem 4a[2pts]:
Show how to implement a spinlock acquire with a single while loop using CAS instead of TSET. You must only fill in the arguments to CAS below:
// Initialization
int lock = 0; // Lock is free
TSET(&addr) {
int result = M[addr];
M[addr] = 1;
return (result);
SWAP(&addr, expr) {
int result = M[addr];
M[addr] = expr;
return (result);
CAS(&addr, expr1, expr2) {
if (M[addr] == expr1) {
M[addr] = expr2;
return true;
return false;
// acquire lock
while ( !CAS( ________________________________ ) );
lock , 0, 1
Page 10/20

CS 162 Spring 2022 Midterm I SOLUTION
February 17th, 2022
Problem 4b[2pts]:
Show how SWAP can be implemented using CAS. Don’t forget the return value.
SWAP(&addr, reg1) {
Object result;
result = M[addr];
Problem 4c[2pts]:
With spinlocks, threads spin in a loop (busy waiting) until the lock is freed. In class we argued that spinlocks were a bad idea because they can waste a lot of processor cycles. The alternative is to put a waiting process to sleep while it is waiting for the lock (using a blocking lock). Contrary to what we implied in class, there are cases in which spinlocks would be more efficient than blocking locks. Give a circumstance in which this is true and explain why a spinlock is more efficient.
If the expected wait time of the lock is very short (such as because the lock is rarely contended or the critical sections are very short), and it is possible for the holder of the lock to make progress while the waiter is spinning (really for a multi-core or multiprocessor system),
then it is possible that a spin lock will waste many fewer cycles than putting threads to sleep/waking them up.
The important issue is that (1) the expected wait time must be less than the time to put a thread to sleep and wake it up and (2) the spinning thread is not impeding the progress of the releasing thread. A single-core machine does not meet this requirement.
_____________________________;
!CAS(addr, result, reg1)
} while ( ________________________________ );
return result;
Page 11/20

CS 162 Spring 2022 Midterm I SOLUTION February 17th, 2022
Using Atomic Primitives to Implement a LOCK-Free Queue:
A queue is considered “lock-free” if multiple threads can operate on this object simultaneously without the use of locks, busy-waiting, or sleeping. In this problem, we construct a lock-free FIFO queue using atomic CAS operation. We need both an Enqueue() and Dequeue() method.
We are going to do this in a slightly different way than normally. Rather than Head and Tail pointers, we are going to have “PrevHead” and Tail pointers. PrevHead will point at the last object returned from the queue. Thus, we can find the head of the queue (for dequeuing). If we don’t worry about simultaneous Enqueue() or Dequeue() operations, the code is straightforward:
/*** Queue Entries and Structure ***/
typedef struct QueueEntry {
struct QueueEntry *next;
void *stored;
} QueueEntry;
typedef struct Queue {
QueueEntry *prevHead;
QueueEntry *tail;
/*** Queue initialization ****/
void initQueue(Queue *newqueue)
newqueue‐>prevHead = allocQueueEntry(NULL);
newqueue‐>tail = newqueue‐>prevHead;
/*** Allocate a QueueEntry to hold pointer to item ***/
QueueEntry *allocQueueEntry(void *myItem)
QueueEntry *newqueue = (QueueEntry *)malloc(sizeof(QueueEntry));
newqueue‐>stored = myItem;
newqueue‐>next = NULL;
return newqueue;
/*** Enqueue operation ****/
void Enqueue(Queue *myqueue, void *newo

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts