CS 140 Fall 2004 Midterm Solutions

Statistics

For this exam, the mean was 32.3 and the standard deviation 7.3.

Retrieving Exams

If you have not picked up your exam, it is available from Judy Polenta in Gates 351.

SCPD Students

If you're a SCPD student, then we'll send it back to you through the SCPD if you marked on the exam that you're an SCPD student. Otherwise we'll assume that you want to pick it up in person. You can email the staff list if you change your mind.

Grading Errors

If you believe that part of your exam was graded in error, please request a regrade. You should preferably attend the office hours of the person who graded the question (shown below), or as a second choice email the staff list. Arithmetic errors should go to the staff list or the office hours of any of the staff.

ProblemGrader
1, 2, 3, 4Ben
5, 6, 7Mendel
8, 9, 10Sameer

Problem 1

Question

You are implementing an OS with a partner. You ask your partner to write some synchronization functions:
lock(L) - Locks L.
unlock(L) - Unlocks L.
sleep() - Makes the current thread sleep until woken with wake().
wake(T) - Wakes thread T.
Your partner decides include several combination functions:
lock_sleep(L) - Atomically lock(L) then sleep().
unlock_sleep(L) - Atomically unlock(L) then sleep().
lock_wake(L,T) - Atomically lock(L) then wake(T).
unlock_wake(L,T) - Atomically unlock(L) then wake(T).
You may assume that all of these functions, but no others, execute atomically. Use them to implement the semaphore operations.

Solution

Here's a solution that would receive full credit:

Integer V, initially set to the starting semaphore value.
Lock L, initially unlocked.
Queue of threads Q, initially empty.

P():
    lock(L)
    if V == 0 then
        put(Q, cur_thread())
        unlock_sleep(L)
    else
        V = V - 1
        unlock(L)

V():
    lock(L)
    if is_empty(Q) then
        V = V + 1
    else
        wake(get(Q))
    unlock(L)

Many essentially correct solutions failed to wake up waiters in first-come first-served order (FCFS). For example, although the following solution provides proper mutual exclusion, there is a window between wake() and the awakened thread reacquiring the lock, in which another thread calling P() can sneak in. This is unfair to the waiting thread, so solutions that didn't enforce FCFS acquisition lost 1 point.

P():
    lock(L)
    while V == 0 do
        put(Q, cur_thread())
        unlock_sleep(L)
        lock(L)
    V = V - 1
    unlock(L)

V():
    lock(L)
    V = V + 1
    if not is_empty(Q) then
        wake(get(Q))
    unlock(L)

In another variant of the previous case, some students who didn't see the race at all wrote the "while" loop as an "if". This turns an unfair situation into an incorrect one and cost an additional 2 points.

A few students switched P() and V(). This cost 1 point.

Other common problems included failure to release an acquired lock, failure to relock a lock that was released and then needed again later, trying to re-acquire a lock that was already locked, and trying to re-release a lock that had already been released. These cost 2 points each.

General race conditions cost from 3 to 5 points depending on severity.

Some solutions didn't maintain a list of waiting threads. This cost 3 points if the solution was otherwise reasonable.

A few students thought that only the combination functions were atomic, and thus used only those functions in the solution. This didn't cost any points, but it was unnecessary.

Problem 2

Question

A common trick used in computer systems is to interpose or "wrap" an interface. To wrap an interface A, every call to that interface is redirected to another interface B which does some processing and passes the call on to interface A. For example, the interface A has two functions:

int foo1(int x);
int foo2(double y);

then interface B would have functions that look like:

int foo1(int x) { /* do processing */ return A->foo1(x); }
int foo2(double y) { /* do processing */ return A->foo2(y); }

One example usage of wrapping would be an interface that counted all the calls to methods of A. Interface B would be given to all places that interface A was referenced and hence would get invoked before A was called each time.

Assume your project partner adds some general support for wrapping interfaces to your OS. The question comes up what happens if the interface being wrapped (e.g. A in our example) is actually a monitor. Your partner claims that if the interface is a monitor, the wrapping interface (e.g. B in our example) should also be a monitor. You claim the wrapping interface should never be a monitor. Are you, your partner or neither of you right in this? Justify your answer.

Solution

Suppose A implements a queue with a bounded buffer, as in Mendel's example of a monitor in class, and that thread 1 is waiting in A's "get" method for a byte to be written to the buffer. Thread 1 doesn't have A's monitor lock, because it's waiting, but—if B is a monitor—it does have B's monitor lock, because the wait operation only releases the running monitor's lock. If thread 2 then attempts to execute a "put," it will first try to acquire B's monitor lock. The result is a deadlock, because thread 1 will not release B's monitor lock until it returns from the "get," but thread 2 will not allow the "get" to complete because it needs B's monitor lock. Therefore, B must not be a monitor.

Other answers received between 0 and 4 points partial credit, depending on the number and quality of the interesting observations they made about the situation.

Problem 3

Question

Is it possible to implement a critical section with wait-free/non-blocking synchronization? Justify your answer. (Hint: Think about the critical section definition.)

Solution

No, because a critical section requires that two threads not be allowed to execute a given section of code simultaneously, but wait-free synchronization does not provide any mutual exclusion.

Also accepted for full credit: wait-free synchronization can be used to construct a lock, which can be in turn used to implement a critical section.

Other answers received between 0 and 2 points partial credit, depending on the number and quality of the interesting observations they made about the situation.

Problem 4

Question

(a) Under what conditions (if any) does a non-preemptive CPU scheduler move a process from the ready state to the running state?

(b) How about a preemptive CPU scheduler?

Solution

(a) When the previously running process gives up the CPU as the result of yielding, blocking, sleeping, making a system call, traps and exceptions, etc.

(b) Anything in part (a), plus involuntary context switches due to timer interrupts, I/O interrupts, etc.

Full credit required at least 2 examples for each part, at one point each. Writing down "anything from (a)" in (b) counted as one example.

Problem 5

Question

Can a system with all jobs having the same priority ever suffer from the priority inversion problem? Justify your answer.

Solution

The priority inversion problem refers to a problem where synchronization overrides the priority system so lower priority jobs end up blocking higher priority jobs from running. If all jobs have the same priority this clearly cannot happen since we can't have lower or higher priority jobs.

Problem 6

Question

Explain why a multiprocessor CPU scheduler might assign jobs to run on particular processors rather than having a global run queue serving all the processors.

Solution

A couple of reasons:

  1. Under what we called cache affinity or processor affinity scheduling we try to get cache/TLB reuse by running a process on the same processor that ran it recently.
  2. Having local run queues can reduce the synchronization demands as compared to a global run queue that needs to be accessed by all processors.

Problem 7

Question

Describe how or where the operating system gets the following information about a process.

(a) Where in a process to start executing when a program started running?

(b) The first available heap memory address?

(c) The initial value for the stack pointer for the process?

Solution

(a) Typically the linker stores the initial program counter in the header of the program object file. When the OS first starts executing a program this value is used as the starting PC.

(b) The start of the heap is initialized from values store in the object file by the linker. The OS then tracks the current available position.

(c) When a process is created the initial stack pointer is determined by the operating system. Typically it is set to some space allocated for the program's stack.

Problem 8

Question

(a) Does the placement of a process's page in physical memory by the virtual memory subsystem affect the amount of external fragmentation?

(b) How about the amount of internal fragmentation?

Justify your answer.

Solution

(Thanks to Michael Turitzin)

(a) Paging of physical memory was set up to deal with (i.e., remove) external fragmentation. Since paging essentially breaks memory up into an array of fixed sized pages, a given page can be placed anywhere without leading to external fragmentation.

(b) The placement of a process' page in physical memory is independent of the issue of internal fragmentation, which is generally caused by a process not fully using a page it was allocated. Since the virtual address a process uses is separate from the actual layout of allocated pages, the layout has nothing to do with internal fragmentation.

This question asked about the placement of pages in physical memory. Some students just explained external and internal fragmentation without explaining how they would relate to placement / location. In this case, they got zero or very little credit.

Problem 9

Question

(a) Can adding prepaging to a demand page virtual memory system decrease the number of page faults?

(b) How about can it increase the number of page faults?

Justify the answer.

Solution

(Thanks to Michael Turitzin)

(a) Yes, prepaging essentially pages in data from disk into memory before it is explicitly requested by the process. If the right pages are brought in, pages faults can be reduced.

(b) If prepaging in pages for one process causes pages for another process to be paged out, then the second process may pagefault where it would not have without the prepaging.

Problem 10

Question

Which of the following conditions would necessarily be present in a system that is thrashing.

(a) Paging disk nearly 100% active.

(b) Paging disk near 100% of capacity

(c) Some processes on the machine are blocked much of the time.

(d) CPU is 100% busy

(e) CPU is 100% idle.

Justify your answer for each.

Solution

(Thanks to Michael Turitzin)

(a) Present. Pagefaults cause disk accesses, and in a thrashing situation, pagefaults are almost constantly occurring.

(b) Not necessarily present. This depends on the size of the paging disk in comparison to the memory requirements of the running processes.

(c) Present. When a process page-faults, it must wait for the corresponding disk-access to complete. Since disk accesses are very slow, thrashing processes will be blocked most of the time.

(d) Not present. The process running will most likely be waiting for disk accesses to complete, which is not at all CPU intensive.

(e) Not present. The CPU still has to context switch between thrashing processes and deal with I/O operations (and possibly other non-thrashing processes), so the CPU won't be 100% idle.

In this question, the justification counted more than the "yes" or "no" answer. If the justification did not make sense (even if the right answer was given), there was no credit given for that part.


cs140-win0405-staff@lists.stanford.edu