UNIVERSITY OF HOUSTON
                 Department of Computer Science

          COSC 4330: Fundamentals of Operating Systems
                        FINAL EXAMINATION
                        December 16, 1993

CLOSED BOOK: You are allowed one 8.5 by 11" sheet of notes.

1.   For each of the statements below, indicate in  one  sentence
     whether  or  not  the statement is true or false, AND WHY (5
     points each):

(a)  One miss every twenty references is an acceptable miss ratio
     for a translation lookaside buffer.

TRUE if the TLB can fetch directly the missing page table entry 
from the main memory:  it would only mean an extra memory 
reference each twenty references.

(b)  One page fault every one thousand references is  an  accept-
     able page fault rate for a virtual memory system.

FALSE since each page fault takes at least 10 ms to be resolved
the paging device would become the bottleneck: a good paging rate
is well below one page every TEN THOUSAND or TWENTY THOUSAND
references.

(c)  The UNIX file access rights are an example of an access con-
     trol list

TRUE, they associate three possible rights (r, w and x) with
three categories of users (the owner of the file, all members
of a group in "/etc/group" and all other users).

(d)  UNIX cannot accommodate very large files.

FALSE, it can accommodate files that have up to  FOUR GIGABYTES
(and they were big files in 1993).

2.   Given the page reference string

             A A A B B C A A C F E B D E

     and a memory size of four page frames, list the  pages  that
     would be expelled from main memory

     (a)  under a LRU policy (5 points):

     (b)  under a FIFO policy (5 points):

(a)  LRU would expel B (to make space for E), A  (to make space
     for B) and C (to make space for D).
      
(b)  FIFO would expel A (to make space for E) and B (to make space
     for D).

3.   What is the major disadvantage of Denning's Working Set pol-
     icy?  (10 points)

Denning's Working Set requires the constant monitoring of all 
process ages that are currently residing in main memory to
be able to detect if they have been used during the last 20,000
to 50,000 memory references.  This task is too complex to
be performed without resulting in an UNREASONABLE OVERHEAD.

4.   Describe the CLOCK page replacement policy  (5  points)  and
     its implementation under Berkeley UNIX (10 points).  What is
     the major disadvantage of this implementation? (5 points)

The Clock policy arranges all page frames into a circular list Each
page frame has a page-referenced bit or use bit that is set to one
whenever frame is accessed.  The page fault handler can reset it to
zero.

There is also a pointer (the hand of the clock) that can move around
the circular list.

Whenever a page must be expelled, the hand moves to the next page in
the circular list and inspects its page-referenced bit.

It this bit is equal to zero, the victim is found. Otherwise the page
fault handler resets the bit to zero and moves the hand to the next
page frame in the circular list.  The process is then repeated until a
page frame with a page-referenced bit equal to zero is found.

Berkeley UNIX implementation of the Clock policy simulates the
page-referenced bit by software.

Instead of resetting the page-referenced bit to zero, Berkeley UNIX
resets the valid bit to zero and saves somewhere the old value of the
valid bit.

When the marked page is accessed again for the first time, the MMU will
encounter a valid bit equal to zero and make a system call to activate
the page fault handler.

The page fault handler will then check the extra bit and restore the
true value of the valid bit so that  the page can continue to be
accessed.  The only disadvantage of the approach is the cost cost o
the two additional context switches.

5.   What is an inverted page table?  (10 points)

An inverted page table has one page table entry per page frame.  The
page table size is then bounded by the size of the physical memory and
not by the size of the process address spaces.

6.   How are block  addresses  stored  in  a  UNIX  i-node?   (10
     points)

In Berkeley UNIX, the 12 first block addresses in the i-node point at
the 12 first blocks of the file.  The  13th block address points to
an indirect block containing the addresses of b/4 additional blocks, 
where b is the block size in bits.  The 14th block address points to
a double indirect block containing the addresses of b/4 indirect
blocks, each containing the addresses of b/4 data blocks.
A 15th block address is not in use.  Hence a total of 12+b/4+b2/16
blocks can be addressed.

7.   Are the following statements true or false  for  the   three
     following disk allocation methods? (20 points)

     This disk allocation method ...    Contiguous   Linked    Indexed

     handles well sequential access        T  F       T  F      T  F

     handles well direct access            T  F       T  F      T  F

     handles well variable-size files      T  F       T  F      T  F

... sequential access    T T T  (all are OK and contiguous is the best)
... direct access        T F T  (worst case for linked allocation)
... variable size files  F T T  (worst case for contiguous allocation)

--IMPORTANT----IMPORTANT----IMPORTANT----IMPORTANT----IMPORTANT--
Please do not try to answer these questions by yourself BEFORE
having a clear idea of what's on the test for which you are
studying.

Materials covered in each test DO VARY from semester to semester
because the pace of the course can change, some materials are be
added and other deleted almost every semester.
----------------------------------------------------------------