Spring 2018
Your Name:
SID AND 162 Login:
Discussion Section Time:
Copyright By PowCoder代写 加微信 powcoder
162162162, s162 4-5PM, Funday
University of California, Berkeley College of Engineering Computer Science Division – EECS
Anthony D. Joseph and – Exam #1 Solutions February 28, 2018
CS162 Operating Systems
General Information:
This is a closed book and one 2-sided handwritten note examination. You have 110 minutes to answer as many questions as possible. The number in parentheses at the beginning of each question indicates the number of points for that question. You should read all of the questions before starting the exam, as some of the questions are substantially more time consuming.
Write all of your answers directly on this paper. Make your answers as concise as possible. If there is something in a question that you believe is open to interpretation, then please ask us about it!
Good Luck!!
QUESTION POINTS ASSIGNED POINTS OBTAINED 1 18
2 24 3 14 4 21 5 23
CS 162 Spring 2018 Midterm Exam #1 February 28, 2018
NAME: _______________________________________
1. (18 points total) Short Answer.
a. (10 points) True/False and Why? CIRCLE YOUR ANSWER.
i) One can always replace signal() with broadcast() for Hoare-style monitors.
TRUE FALSE
FALSE. Hoare-style monitors can function correctly with if rather than while, so broadcast() for Hoare may incorrectly wake up threads. The correct answer was worth 1 point and the justification was worth an additional 1 point.
ii) One can disable interrupts on any computer system that supports it to guarantee atomicity.
TRUE FALSE
FALSE. Doesn’t work on multiprocessor systems. The correct answer was worth 1 point and the justification was worth an additional 1 point.
iii) In Pintos, the scheduler code runs in the idle thread and facilitates the context switch between any two threads.
TRUE FALSE
FALSE. The idle thread only runs when there are no other threads. The scheduler is run on the two threads’ kernel stacks. The correct answer was worth 1 point and the justification was worth an additional 1 point.
iv) The kernel first validates syscall arguments on the user stack before copying them to its corresponding kernel stack, in order to protect kernel memory.
TRUE FALSE
FALSE. The arguments are checked after copying to prevent malicious user code from evading checks (TOCTOU attack). However, we also accepted TRUE provided the justification mentioned checks both before and after the copy, due to the admittedly ambiguous wording. The important thing was the justification mentioning the check after to protect against TOCTOU attacks. The correct answer was worth 1 point and the justification was worth an additional 1 point.
CS 162 Spring 2018 Midterm Exam #1 February 28, 2018
NAME: _______________________________________
v) A context switch between any two threads requires saving all the old thread’s registers and replacing them all with the new thread’s, including the stack pointer, the segment registers, and the page table base register.
TRUE FALSE
FALSE.Threads within the same process would share the same address space and thus would not need to change the segment/PTBR. The correct answer was worth 1 point and the justification was worth an additional 1 point.
b. (4 points) Briefly, in one to two sentences each, give two reasons why a typical web server creates new threads to service new connections instead of creating new processes to service new connections.
i) Reason #1:
(1) Lots of requests means threads are lower overhead to create.
(2) Many requests will be for the same popular files means threads will share
(3) Lots of requests means switching between threads is less overhead
ii) Reason #2:
c. (2 points) Much of the software code used in the Therac-25 was taken from earlier models, which had functioned without the failures seen in the Therac-25. Why did this reused code suddenly fail in the Therac-25? Briefly, in one to two sentences, explain your answer.
The previous code had the same failings, but was masked by safety interlocks in hardware. Engineers reused the code on faith (“cargo cult programming”) without understanding or retesting it.
d. (2 points) Suppose you are writing a multithreaded test in Pintos for project 1, and one of your test’s threads dereferences a NULL pointer. Briefly, in one sentence, explain what happens to the system and why.
The entire kernel panics because we have not implemented user programs yet, so all threads are using their kernel stacks in shared kernel memory and there is no protection. A Segmentation Fault is user space and only implies a single (user) process crashing (since it is a protection fault), and is NOT equivalent to a kernel panic.
CS 162 Spring 2018 Midterm Exam #1 February 28, 2018
NAME: _______________________________________
2. (24 points total) Scheduling. Consider the following processes with their remaining instructions, arrival times, and priorities (A process with a higher priority number has priority over one with a lower priority number):
Process Remaining instructions Arrival time Priority A324 B411 C133 D212
There is a lock L:
● Process A acquires L in its first unit of time, and releases L in its last unit of time.
● Process D acquires L in its first unit of time, and releases L in its last unit of time.
● Processes busy wait when trying to acquire a lock.
● Priority donation is implementedJ.
Please note:
● The priority scheduler is preemptive.
● All processes arriving at the same time step arrive in alphabetical order.
● The quanta for RR is 1 unit of time and newly arrived processes are scheduled last
for RR. When the RR quantum expires, the currently running thread is added at
the end of to the ready list before any newly arriving threads.
● Break ties via priority in Shortest Remaining Time First (SRTF).
● If a process arrives at time x, they are ready to run at the beginning of time x.
● Ignore context switching overhead and only 1 instruction runs at each time step.
● Total turnaround time is the time a process takes to complete after it arrives.
CS 162 Spring 2018 Midterm Exam #1 February 28, 2018
NAME: _______________________________________
Given the above information, fill in the following table:
Time Round RTF Priority 1BDD 2DDA 3BCD 4AAA 5DAA 6CAA 7BBC 8ABB 9BBB
Total Turnaround Time 28 18 24
Each column was graded separately with the same breakdown of 8 points. The sequence was 6 of the 8 points and the turnaround time was 2 of the 8 points.
CS 162 Spring 2018 Midterm Exam #1 February 28, 2018
NAME: _______________________________________
(14 points total) C Programming.
In the following program, we want to print out, “Process 162 says 42” once. Assume that the process ID of the child process is 162, the fork() is successful, and we want the behavior to be predictable. Do not add extra lines or try to compact your code onto the lines.
No hard-coding/assignment of values is allowed for your blanks inside of main().
1 void helper(void) { 2 exit(42);
4 int main(void) {
12 printf(“Process %d says %d\n”, pid, 13 WEXITSTATUS(kirito));
14 } // or just kirito
a) (8 points) Fill in the above blanks, to output “Process 162 says 42”.
b) (4 points) If the fork() failed, what would be printed out, if anything?
If fork() fails, pid gets set to -1, which is evaluated as a TRUE value, so the first conditional block runs. wait() will return immediately because fork() failed and we will just print out “Process -1 says 0”
c) (2 points) In Linux, is the entire address space copied when fork() executes successfully? If not, what happens instead?
No. It is implemented with copy-on-write, which does not copy the entire address space. Copies are made when modifications are made.
intkirito=0; pid_tpid=fork(); if(pid){
//orwaitpid()
wait( &kirito );
helper ();
CS 162 Spring 2018 Midterm Exam #1 February 28, 2018
NAME: _______________________________________
3. (21 points total) Pintos Priority Donation.
Suppose you have successfully completed project 1 task 2 (priority scheduling), with all tests passing (including recursive and multiple donations). You made the following changes in your thread and lock structs, as indicated in your design doc:
/* thread.h */ struct thread
/* Preexisting members, some omitted for brevity. */ …
int priority;
/* Your new members. */
int base_priority;
struct lock *wanted_lock;
struct list acquired_locks;
/* Priority. */
/* Base priority without donations. */
/* Lock thread is waiting for, if any. */ /* List of acquired locks. */
unsigned magic;
/* synch.h */ struct lock
/* Preexisting members. */
struct thread *holder;
struct semaphore semaphore; /* Binary semaphore controlling access. */ /* Your new members. */
struct list_elem lock_elem; /* For storage in `acquired_locks` list. */
In lock_release(), a thread currently handles multiple donations by looping over acquired_locks and looping over each lock’s waiters to find the maximum priority among all waiters of all locks it holds. It then applies that donation if applicable, otherwise it reverts to the base priority.
One of your project partners thinks this is inefficient and suggests adding an “int lock_priority” member to struct lock, which would represent the highest priority among all of that lock’s waiters so you don’t have to loop over the waiters. Your friend also mentions updating lock_priority as needed upon any thread calling lock_acquire() on that lock, or calling thread_set_priority() on itself. However, your friend forgets that priority donations can change priorities and thus lock_priority is not updated upon each donation.
a. (3 points) Briefly, in two to three sentences, describe a test case that could identify this bug. Hint: think about recursive priority donation
Assuming A
/* mode = 0 for student, 1 for TA, 2 for professor */ enter_room(room_lock* rlock, int mode) {
rlock->lock.acquire();
if (mode == 0) {
while((rlock->activeProfs+rlock->waitingProfs) > 0){ rlock->waitingStudents++; rlock->student_cv.wait(&rlock->lock); rlock->waitingStudents–;
rlock->activeStudents++;
} else if (mode == 1) {
while((rlock->activeProfs+rlock->waitingProfs) > 0 || rlock->activeTas >= TA_LIMIT) {
rlock->waitingTas++; rlock->ta_cv.wait(&rlock->lock); rlock->waitingTas–;
rlock->activeTas++;
while((rlock->activeProfs + rlock->activeTas + rlock->activeStudents) > 0){
rlock->waitingProfs++; rlock->prof_cv.wait(&rlock->lock); rlock->waitingProfs–;
rlock->activeProfs++;
rlock->lock.release();
exit_room(room_lock* rlock, int mode) { rlock->lock.acquire();
if (mode == 0) {
rlock->activeStudents–;
if ((rlock->activeStudents + rlock->activeTas) == 0
Page 12/14
CS 162 Spring 2018 Midterm Exam #1 February 28, 2018
NAME: _______________________________________
&& rlock->waitingProfs) rlock->prof_cv.signal();
} else if(mode == 1) {
rlock->activeTas–;
if ((rlock->activeStudents + rlock->activeTas) == 0
&& rlock->waitingProfs)
rlock->prof_cv.signal();
else if (rlock->activeTas < TA_LIMIT && rlock->waitingTas)
rlock->ta_cv.signal();
rlock->activeProfs–;
if (rlock->waitingProfs)
rlock->prof_cv.signal();
if (rlock->waitingTas) rlock->ta_cv.broadcast(); if (rlock->waitingStudents)
rlock->student_cv.broadcast(); }
rlock->lock.release();
Page 13/14
CS 162 Spring 2018 Midterm Exam #1 February 28, 2018
NAME: _______________________________________
Congratulations on reaching the end of the exam! There is no exam material on this page. Remember that no matter how you do, someone cares for you. We hope you enjoy operating systems so far.
Page 14/14
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com