Name: Login ID: Code:

Systems Breadth Exam
May 7, 1997

You must answer all questions in the Computer Organization section. You must also answer all the questions in two of the remaining four areas. Do not write any answers on this paper. Only mark your name and code on this paper. Write all your answers on the blank paper provided to you. Only use one side of each sheet of paper. Write your code at the top of each sheet of paper. Do not write your name on your answer sheets.

Computer Organization

  1. OnesCount-3 is a function that receives a three-bit binary value as input and outputs the count of the number of input bits that are one.

    1. Give boolean functions to describe the output bits of OnesCount-3 in terms of its inputs. Your functions should be expressed as minimal sum-of-products expressions.
    2. Draw a circuit diagram for your minimal OnesCount-3 functions using AND gates, OR gates and inverters.
    3. Could your OnesCount-3 circuit be constructed using a PLA? If yes, describe the parameters of the PLA and the steps involved in constructing the PLA-based implementation. If no, why not?
    4. Could your OnesCount-3 circuit be constructed using a ROM? If yes, describe the parameters of the ROM and the steps involved in constructing the ROM-based implementation. If no, why not?
  2. Suppose we are constructing a small, dedicated computer system with a read-only disk. Software accesses the disk drive through the following hardware registers:

    Assume typical values for the seek delay, throughput rate, and instruction cycle time.

    1. Write a pseudo-code algorithm that uses programmed I/O techniques to read the block at disk address Daddr into memory at Maddr.
    2. What would happen if your algorithm were implemented and run with interrupts enabled?
    3. Describe how a DMA controller could be used to replace programmed disk I/O in this system. What advantages would it offer? Why?

Operating Systems

  1. Rewrite the following program using semaphores to synchronize the processes so that every character read from the keyboard is printed on the screen exactly once.

                         #define SIZE 10
                         char buff[SIZE];
    
                         main () {
                           create(process1);
                           create(process2);
                         }
    
    process1() {                           process2() {
      int i=0;                                int i=0;
    
      while (1) {                             while (1) {
          buff[i] = getchar();                    printf("%c", buff[i]);
          i = (i+1) % SIZE;                       i = (i+1) % SIZE;
      }                                       }
    }                                      }
  2. Process Creation:
    1. Write a C program that will execute the ``/bin/ls'' program and pipe its output through ``/bin/more''. You may use the system calls from any operating system you like, but you must use the basic process creation/termination and IPC calls (not calls like the Unix system() library routine). Your program should wait for ls and more to complete and then should print the message ``LS AND PS ARE DONE''.
    2. Describe each of the system calls you used in your program. Clearly state what each call does.
  3. Describe how a hierarchical file system might be laid out on the disk.

Compilers

  1. Describe, in terms of FIRST and FOLLOW sets, requirements for a context-free grammar to be parsable by a recursive descent parser (without backtracking).
  2. Compute FOLLOW and FIRST sets for the nonterminals of a grammar given below. Based on your answer to question 1 check if one can design a recursive descent parser (with no backtracking) for this grammar.
     
     		   tex2html_wrap_inline128 
    

    tex2html_wrap_inline130

    tex2html_wrap_inline132

    tex2html_wrap_inline134

  3. Show the LL(1) parse table for the grammar given above.

Programming Languages

  1. Give a Prolog declaration that defines append/3.
  2.   What is the result of the following Prolog query?
            ?- append([1,2], X, [1,2,3,4])
  3. Trace the execution of the query in part 2.

Databases

  1. Consider the following database schema used by a store: (Salesperson, Office, Buyer, Product, Amount, Cost)
    R = SOBPAC

    There are the following functional dependencies:

    tabular79

    1. Find all keys for R.
    2. Find a 3NF decomposition that has a lossless join and preserves dependencies.
    3. Find a lossless join decomposition into Boyce-Codd normal form.
    1. Show whether or not the following schedule is conflict serializable.

      tabular87

    2. If it is not conflict serializable, is it view serializable? Justify your answer.
  2. Consider the following database schema used by a simple company:
              Customers (Id, Name, State, Phone)
              Orders (Order-#, Id, Item, Quantity)
              Stock (Item, Desc, Price, On-Hand)
              Vendor (Vendor_Id, Item, Cost, State)
    Transform the following into any commercial query language such as SQL, QBE, or Quel:
    1. Find all customers (Name) ordering any Item that Costs more than 100.00.
    2. Find all Items where the sum of the ordered Quantity exceeds the amount On-hand.
    3. Find the average Cost of all Items ordered by customers in the State of Kentucky.
    4. Find the Name of all customers who have ordered items from all of the vendors.


James Griffioen
Thu May 8 14:13:58 EDT 1997