Name: Login ID: Code:

Systems Foundational
May 7, 1997

You must answer all questions in the Computer Organization section. You must also answer 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. You are designing the instruction set for a new computer. Parameters that have already been defined include the following:

    Consider these three alternatives for implementing a jump instruction:

    1. The jump instruction consists of a ten-bit opcode and a 22 bit location value. The next instruction to execute after the jump is determined by

      eqnarray38

    2. The jump instruction consists of a ten-bit opcode and a 22 bit location value. The next instruction to execute after the jump is given by

      eqnarray42

      signed two's complement arithmetic is used and tex2html_wrap_inline122 is sign-extended to 32 bits.

    3. The jump instruction consists of a ten bit opcode, a four bit register field, and an 18 bit location value. The next instruction to execute after the jump is given by

      eqnarray47

      tex2html_wrap_inline124 is the general purpose register determined by the register field, signed two's complement arithmetic is used, and tex2html_wrap_inline126 is sign-extended to 32 bits.

    QUESTION: In each case, what portion of the address space is accessible?

  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. Use process creation/termination system calls to write a program that will execute the ``/bin/ls'' program and the ``/bin/ps'' programs simultaneously. When the ls program and the ps program complete, your program should print the message ``LS AND PS ARE DONE''. You may use the process creation/termination system calls from any operating system.
    2. Describe each of the system calls you used in your program. Clearly state what each call does.

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_inline136 
    

    tex2html_wrap_inline138

    tex2html_wrap_inline140

    tex2html_wrap_inline142

Programming Languages

  1. (Dynamically sized objects) There are at least four ways in which arrays can be defined such that they are dynamically sized. (Very few programming languages have more than one or two such ways; some languages have none.)
    1.   Describe two different kinds of dynamically sized arrays.
    2. For both answers in question 1a, describe any complexities involved in passing such arrays as parameters to subroutines.
    3. For both answers to question 1a, describe any complexities involved in placing such an array as a field in a record.

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:

    tabular91

    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.
  2. Show whether or not the following schedule is conflict serializable.

    tabular98

  3. 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.


James Griffioen
Thu May 8 14:16:00 EDT 1997