CPS110 Exam2 with answers April 1, 2004

Do one question from each category, plus an additional question. Each worth 25 points.

Synchronization:

1. Highway 110 is a two-lane road that passes through a one-lane bridge. A car
can safely enter the bridge if and only if there are no oncoming cars in the
bridge. You may assume that each car is represented by a thread that calls
Enter (int direction) and Leave() functions, passing an argument indicating the
direction of travel. The traffic light policy is that cars are allowed through
in sequence. If there is a car waiting to go in the opposite direction, then
that car should get the right of way, and be allowed to pass. Implement Enter
and Leave functions that avoids deadlocks and starvations using any of the
following synchronization primitives : locks, condition variables, mutexes,
semaphores.

Lock L; Condition W[2];
int cars[2]={0,0}, wait[2]={0,0}, cdir=0;

void Enter(int dir) {
L->Acquire();
int od = 1-dir;
wait[dir]++;
while ((cars[od]>0)||((wait[od]>0)&&(cdir==dir))) {
W[dir]->Wait(L);
}
cars[dir]++;
wait[dir]--;
cdir=dir;
L->Release();
}

void Leave(int dir) {
L->Acquire();
cars[dir]--;
if (cars[dir]==0) W[1-dir]->Broadcast(L);
L->Release();
}

Explanation: If there are cars on the bridge going the other way, OR if
the last car to enter the bridge was going MY way, and there are cars
going the other way waiting to cross, I wait.

This is somewhat inefficient, since when there are cars waiting to cross
in BOTH directions, it allows only one car at a time to enter the
bridge, in alternate directions. However, this makes inefficient use of
th bridge, since it takes time for a car to cross. More cars could
cross if several were allowed onto the bridge in a given direction,
before stopping that flow, and allowing cars from the other direction to
cross. This would clear both lines faster.

Also, the Broadcast wakes up all waiting cars. If there are still cars
waiting going in my direction, then only one of the awakened cars will
actually make it onto the bridge -- the first car to enter the bridge
will change cdir, stopping the line of cars. Thus the Broadcast causes
more processes to awaken than can actually run -- all must execute the
tests and issue new Wait() operations. This uses extra processor
cycles.

2. In an electronic funds transfer system, there are hundreds of identical
processes that work as follows: each process reads in input line specifying an
amount of money, the account number to be credited, and the account number to
be debited (i.e., both account numbers known). The process must lock both
accounts, then transfer the money, and finally release the locks when finished.
The primitive you have available for your use locks a single account at a time
(e.g,. lock(acctnum) ). Locks must be held on both accounts while transferring
money otherwise errors could result. Even with thousands of accounts, if there
are many processes running in parallel, there is a real danger of encountering
already locked accounts when requesting locks and, thus, the danger of
deadlock. Describe a scheme to do this that avoids deadlocks and starvation.
The key to avoiding deadlock is to acquire the locks in some fixed
order, say in increasing numeric order. In this way, there can be no
cycle of lock holds:
Transfer(int A1, int A2, int Amount) {
if (A1==A2) return;
if (A1<A2) { lock(A1); lock(A2); }
else {lock(A2); lock(A1); }
/* Do the funds transfer here. */
unlock(A1); unlock(A2);
}

Starvation: A tranaction could be prevented from eve running if other
transactions were constantly granted the lock for one of the accounts
needed. To prevent this, the system lock monitor must grant requests
for a given lock in some fair order, ensuring that no request waits
forever. For example, it might use the First Come First Served order.

Scheduling:

3. Consider a system with two processes, H, a high priority process, and L, a
low priority process. The scheduler chooses the highest priority ready process
to be the one to run at each scheduling opportunity. Suppose that L has just
run and entered a critical section protected by a spin-lock (a busy-waiting
implementation). Now H becomes ready to run, having completed some I/O
that previously had it blocked, and is scheduled immediately. Then H tries to
enter its critical section by trying to acquire the spin-lock. Assuming you
can modify the code of processes H and L, without changing the priorities, what
could you change so that this is avoided ? What can you change at the OS level
to prevent this ? Explain your answer.
You can change the code so that a Lock, rather than a spin-lock, is used
to protect the critical section. (Any scheme which blocks when access
to the CS is denied will work.) With this change, when H tries to enter
the CS, H blocks, and is no longer running. This allows the
lower-priority process L to run, and hopefully exit the CS.

Note: Other processes of priority between H and L might still run,
preventing L from actually getting any CPU time.)

At the OS level, I'd have to change the scheduling rule (assuming the
code is still using spin-locks). The new rule would be to run H only
until it uses T[H] time units, then pre-empt H, and run L for T[L] time
units. The idea is to ensure that L gets SOME execution time, while
still ensuring that H gets more. To do this, set T[H]>T[L].
The difficulty with this scheme is that H may not get enough execution
time to meet it deadline, if there is such a deadline.

4. A computer system runs a stream S of jobs in First Come First Served order.
The stream of jobs arrival times is normally distributed with mean arrival rate
of 1 job every 40 seconds. The CPU requirement of the jobs is normally
distributed, with a mean of 10 seconds per job. In addition, two high-priority
real-time jobs must also run on the same computer. Job A requires 5 seconds
every 30 seconds, and job B requires 2 seconds every 6 seconds. Design a
scheduling policy for this system that ensures the deadlines for the real-time
jobs are met. Specify whether your scheduler uses preemption or not. Specify
the rules which the scheduler uses to choose the next job to run, and the
rule(s) used for choosing the scheduler decision times (e.g., when the next job
from S completes, or after X seconds.)
Policy: Give the real-time jobs higher priority than any job in S.
Schedule the real-time jobs using Earlist Deadline First.
The schedule uses pre-emption.
Whenever a real-time deadline passes, the running job is
interrupted, and the scheduler determines which real-time job's
deadline comes next, and runs that job.
When ANY job finishes, the scheduler again makes a decision. If
both RT jobs have completed their current work, the scheduler
resumes the current job from S (if it had been interrrupted), or
picks the next job from S in FCFS order, and starts running it.
Decisions are made: At any RT job deadline, and when any job finishes.
Rule: If any RT job has work to do in this period, run that RT job
whose next deadline comes earliest. Otherwise, resume or start the
first job in the FCFS queue of stream S.

Memory management :

5.
(a) A computer with 32-bit virtual addresses uses a two-level page table.
Virtual addresses are split into a 9-bit top-level page table field, an 11-bit
second-level page table field, and an offset. How large are the pages and how
many are there in the address space ?
Virtual Page Number occupies 9+11 bits, while the page offset occupies
the rest. VPN is 20 bits, Offset is 32-20=12 bits. So there are
2**12=4096 bytes per page, and there are 2**20 pages in the address
space.

(b) A machine has 48-bit virtual addresses and 32-bit physical addresses. Pages
are 8K. How many entries are needed for a conventional page table? For an
inverted page table ?
8K byte page requires an Offset field of 13 bits, since 8K=2**13
The size of the VPN field is then 48-13 = 35 bits.
This means that a conventional page table, with one entry per virtual
page, needs 2**35 entries. (This is some 32 billion entries.)
An inverted page table needs one entry per Physical page. There are
32-13 = 19 bits in the physical page frame number, and hence 2**19
entries in an invertd page table. (2**19 is about 1/2 million -- a
feasible page table size.)


6. Consider an application accessing the pages in the folowing order:
1 2 3 4 1 2 ... with { 1 2 3 4} repeated M times. Assume a memory contains
just 3 page frames which is initially empty. Show the first reference on which
LRU and OPT make DIFFERENT decisions. What are those decisions? Finally,
estimate how many page faults LRU will make, and how many OPT will make
on this reference string and explain why.
1 2 3 <4> 1 2 3 4
At the first reference to page 4, memory will hold pages 1 2 3. LRU
will choose to replace the page refernced longest ago, which is page 1.
OPT will look ahead, and find the page which will be first referenced
farthest into the future, so OPT will pick page 3.

I'll show the reference string on line 1, and below each reference, show
the contents of memory AFTER that reference in a column, giving the page
in frame i in row i. The *'s mark page faults:

LRU:
* * * * * *
1 2 3 4 1 2 3 4 1 2 3 4
1 1 1 4 4
- 2 2 2 1
_ _ 3 3 3
So LRU appears to fault at every reference. LRU: 4M faults.

OPT
* * * * * *
1 2 3 4 1 2 3 4 1 2 3 4
1 1 1 1 1 2
- 2 2 2 3 3
_ _ 3 4 4 4
So OPT appears to fault once every 3 references. OPT: 4M/3+2
(The +2 accounts for the first iteration, when nothing was in memory,
and 2 extra faults occur.)

Why: LRU looks into the past, and in this case by accident makes the
worst poccilbe decision at every fault. OPT, seeing the future, avoids
some faults, by keeping in memory those pages that WILL be referenced in
the immediate future (next).