COSC 4330
                        FINAL EXAMINATION
                           MAY 1, 2000

Closed Book. You can have one sheet of notes.

1.   Answer in one or two sentences to the following questions
     (6×5 points).

     a.   What is the main disadvantage of the VMS page replacement
          policy?

          The policy assumes that we can predict ahead of time
          the sizes of the resident set of pages for each
          process. In fact, this is not possible.

     b.   What is the main advantage of having TLB misses handled by
          the hardware?

          A TLB miss will cost only one main memory access
          instead of requiring two context switches.

     c.   What is the purpose of the dirty bit? (5 points)

          To tell whether the page has been modified since it was
          brought into main memory.

     d.   What is the main advantage of mapping files into the address
          space of the processes that access them?

          The portions of the file that are brought into main
          memory can be accessed without any kernel intervention.

     e.   What is the major difference between the contents of a page
          table entry and those of a TLB entry?

          The TLB entry must include the page number.

     f.   What is the major disadvantage of inverted page tables?

          Each page frame can only belong to one process.

2.   Complete the following sentences: (4×5 points)

     a.   To implement the Clock policy on the VAX, the designers of
          Berkeley UNIX had to simulate_ the page-referenced bit __.
          in software.

     b.   On demand fetch means that pages are loaded into main
          memory when _ they are accessed for the first time ______.

     c.   Memory compaction is used to fight
          _ external fragmentation_________________________________.

     d.   The simplest way to reduce the size of page tables is to
          increase the _ page size of the system __________________.

3.   A virtual memory system has a virtual address space of 4
     Gigabytes and a page size of 512 bytes. Each page table entry
     occupies 4 bytes.

     a.   How many bits of the virtual address will remain unchanged
          by the address translation process? ( 5 points)

                     _ 9 _bits (because lb 512 = 9)

     b.   What is the maximum number of page table entries in a page
          table?

            _223_ entries (because lb 4G = 32 and 32 - 9 = 23)

4.   What was the motivation for adding a second hand to the
     Clock page replacement policy? (5 points) In a system having a
     very large physical memory, why would you like to have the two
     hands separated by a small angle? (5 points)

     When main memory sizes started to grow in the mid-eighties,
     it was found that the hand of the clock was taking too much
     time to scan the whole main memory.  Hence, more recent UNIX
     implementations have added a second hand that expels the
     pages that have not been accessed by the process after their
     valid bit had been cleared by the first hand.  The angle
     should be kept small so that pages are expelled fast enough.

5.   Given the page reference string

              1 0 4 0 2 1 2 4 3 3 3 0 5 4 3 1 7 2 0

     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):
          _____________________________________________

6.   It is often said that the UNIX file system favors small
     files. Do you think it is true? (5 points) Why? (5 points)

     UNIX favors small files because its i-node structure
     provides faster access to files that do not use indirect
     blocks.  This was done because most UNIX files are small
     files.

 7.   Explain how the UNIX file system implements access control
     lists (5 points) What would be the main advantage of a fuller
     implementation of the concept?(5 points)

     UNIX uses a fixed size access control list where one can
     specify three classes of users (owner, all members of one of
     the groups specified in /etc/groups, all users) and three
     access rights (read, write and execute).

     A more complete implementation of the concept would allow
     the file owner to specify exactly who can access the file
     and exactly what each individual can do.