CS162 Fall 2004 Midterm 1 Solutions
===================================
1. (Yitao)
An inverted page table is a hash table for address translation. Besides the
information found in a regular page table entry (physical page number,
protection bit, etc.), each element also contains the ID of the process that
occupies this element (if the table is systemwide) and the virtual page
number. The system can be designed with one inverted page table for all the
processes in the sytstem or one per process, but the former is more efficient.
Given a virtual page number, the system hashes it to obtain an index into the
table. The pid of the current process and the virtual page number are compared
with what are stored in the elements in the linked list. If a match is found,
the physical page number contained in that element is used to construct the
physcal address. (8)
To be efficient, the number of entries in the inverted page table should be
significantly larger than the number of physical page frames in the system 
e.g. 2X. (2) The size of the
virtual address space is independent of the size of the physical address
space. (2) And the number of entries in the inverted page table is also
independent of the size of the virtual address space. But since the inverted
page table needs to store virtual page numbers whose size (number of bits) if
proportional to log(virtual address space size), the size of the inverted page
table in terms of total number of bytes is also proportional to log(virtual
address space). (2)

2. (Yitao)
(1) Relocation (7)
(2) Protection (7)

3. (Karl)
+++
vaddr  segment #  offset \
+++ 
 
 ++ 
 STBR 
 ++ 
  
  
 v 
 ++ 
   
   
   
   
   
 +++++++ 
\> frame #  bounds PVDR 
+++++++++ 
    
    
    
    
    
++++ 
  
 trap(<)+
 
\>(+)</


v
+++
 frame#  offset 
+++
The segment table is a table of where each entry consists of a frame number,
bound, and Permission, Valid, Dirty, Reference bits.
The Segment Table Base Register points to the current process's segment table.
To translate a virtual address, follow the STBR and look up the segment table
entry. (Some people also correctly noted that this involves an adder, but I
did not check for this.) Add the frame number to the offset (from the V.A.)
to get the physical address. Compare the offset to the bound and trap
(segfault) if invalid.
The protection and valid bits also need to be tested, and there needs
to be a trap if the reference is invalid or illegal.
Scoring:
 (2 points) STBR
 (4 points) Segment table, with base and bounds
 (4 points) Permission bits
 (4 points) Adder and comparator
Many people forgot the STBR, and the table entry fields.

4. (Karl)
(a). Complete safe sequence: ACDB, or ADCB.
Scoring: (6 points)
(b). Unsafe.
Either show that ACD or ADC leads to not enough Y left for B, or notice that
there isn't enough Y for B in the first place (it needs 220 but there is only
215 total).
Scoring: (6 points)
Almost everyone got #4 correct.

5. (Yitao)
Method 1

Proof by contradiction: Assume that there is some schedule for N jobs that is
not SJF. Show formula for average flow time. Show that interchanging jobs,
so that a short job moves forward and a long job moves backward, decreases
average flow time. So assumption is contradicted. So there is no such
schedule, and the optimal schedule must be SJF.
Method 2

Let Job_i be the ith job to run, i = 1, 2, ... N. Let T_i be Job_i's
service time. The flow time for Job_i is
f_i = sum_{j = 1}^{i} T_j
Mean flow time is f_0 = sum_{i = 1}^{N} f_i/N. Since N is constant we only
need to minimize the sum.
With SJF, each term f_i in the sum is minimized. This is because using SJF,
f_i is the sum of i shortest service times and this is the shortest flow time
ith job can possibly have.
==> SJF achieves minimal mean flow time*.
* Note: the key in this proof is to number the jobs by the order they are run,
not some labels that move with the jobs. You can think of the scheduling as N
bins numbered 1 through N and you try to find a permutation of the jobs that
fill each bin with each job. You compute the mean flow time by summing the
flow time of each bin.
Scoring: half credit for heuristic/intuition or comparison.
Note that a "proof" is not the same as a heuristic argument.
(What was given in class was the latter.)

6. (Karl)
(a) Shortest Job First.
You know the size of the job after it is submitted, before you start printing.
(You can either assume you can tell the number of pages, or use the file
size.)
Scoring: (8 points)
 partial credit for saying "SJF is optimal except for the fact that we
have no knowledge of the future"
(b) I accepted two answers for full credit:
(1) Supermarket express lane: reserve one printer for short jobs,
e.g. jobs less than 5 pages. Short jobs can still use the longjob
printer. This improves wait time for short jobs, and it is fair for
longer jobs to wait longer.
(2) SJF, FCFS: have a single queue; the two printers take jobs SJF and
FCFS respectively. I.e., one printer takes the shortest job in the
queue, and the other printer takes the earliest submitted job in the
queue. This prevents long jobs from being starved by short jobs, and
is fair to both kinds of jobs.
A common answer that received partial credit:
SJF, LJF: have a single queue; the two printers take jobs SJF and "Longest
Job First". This is not fair for mediumsized jobs. In fact, this is
probably a bad idea.
Note that the goal of a scheduling algorithm is to keep the customers happy.
SJF will not keep customers happy when, late at night, both printers are
running very long jobs, and someone submits a short print job.
Scoring: (8 points)

7. (Karl)
If there are only 2 processes concurrently contending for the critical
section, this code works OK. It starts to fail as the number of processes
increases. If there are many (e.g. 5 or more) then it does not. If there are
7 processes, then the counter "A" will be floating around 67. All 7
processes have to simultaneously decrement A for the next process to increment
sees that it was previously 0 (now it is 1). This is probabilistically
unlikely as the number of processes increases.
This code does not allow multiple processes into the critical section (i.e.,
it does not violate mutual exclusion). It does not suffer from starvation or
deadlock due to processes having different priority. It is a certain kind of
race condition, but when there are many processes, it will almost always fail
(whereas in a typical racecondition bug, the program runs fine normally and
fails once in a blue moon). The problem it has is "indefinite postponement."
One of the biggest problems students had was understanding the code. The
lines::
{increment A in memory, load A}
if A != 1 ...
mean that A is incremented, and the value tested is the value just after
incrementing, EVEN IF ANOTHER PROCESS INCREMENTS "A" IN BETWEEN THE TWO
STATEMENTS.
Perhaps this pseudoC code will clarify::
Init:
int *A = new int; /* shared among all processes */
Mutex code:
while (true) {
int localA; /* local to this process */
atomic { localA = ++ (*A); }
if (localA == 1) break;
atomic {  (*A); }
}
/* critical section */
atomic {  (*A); }
Or this Java code::
class CriticalSection {
private int A; /* shared among all processes */
public void enterCriticalSection() {
while (true) {
int localA; /* local to this process */
atomic { localA = ++A; }
if (localA == 1) break;
atomic { A; }
}
}
public void leaveCriticalSection() {
A;
}
}
Scoring: (13 points)
 partial credit for remembering that there is some kind of infinite loop
or no progress, but wrong explanation.