======================================================================
CS2200                      Spring 2005                Practice Test 2
======================================================================

Topical Coverage

    Interrupts
    Performance
    Pipelining
    Process Abstraction
    Memory 


Interrupts 

1P  Write out an interrupt handler which will be able to be 
    interrupted and one that will be uninterruptable. Don't worry 
    about the actual "work" of the handler. Just put a comment where 
    that would go.

    Sketch out a datapath with an interrupt request line and an 
    interrupt acknowledge system using daisy chaining.
    
    
2P  What instructions are needed to implement interruptible interrupts?
    Explain the function and purpose of each along with an explanation
    of what would happen if you didn't have them.

Performance
    
3P  A processor has the following frequency of execution of a suite of 
    benchmark programs:
        
        add/nand    35%
        beq         30%
        lw/sw       20%
        Other       15%
        
        A new design for this processor is being proposed which will 
        speed up the execution of the various instructions as show 
        here:
        
                    Old CPI     New CPI        
        add/nand    6           4
        beq         5           4
        lw/sw       7           5
        Other       4           3
        
        What will be the speedup of the new design?
        
Pipelining

4P Examine the following pipelined processor layout:
    
    IF              ID.RR               EX              MEM             WB
    
        INC     R                   R               R               R
                E                   E               E               E
    PC  IMEM    G   RegFile         G   ALU         G   Memory      G   Mux
                I                   I               I               I
                S   SignExtend      S               S               S
                T                   T               T               T
                E                   E               E               E
                R                   R               R               R
                
    Sketch the connections necessary to implement the LW instruction
    which as you will recall has the following semantics:
    
        LW RL, offset(RB)
        
        RL <- MEM[RB + offset]                
        
        
        Note: You also do not have to concern with hazards.
        
        
        
    Assume the machine has instructions with 4 bit opcodes and a 32 bit
    word size and uses word addressing.
    
    Now show the contents of each of the four pipelined registers.
    Note: Only be concered with this instruction! We have started it
    for you...
    
    IF/ID.RR
    +----------------------------------------------------------------+
    |OpCode 4 bits                                                   |
    +----------------------------------------------------------------+
    
    ID.RR/EX
    +----------------------------------------------------------------+
    |OpCode 4 bits                                                   |
    +----------------------------------------------------------------+
    
    EX/MEM
    +----------------------------------------------------------------+
    |OpCode 4 bits                                                   |
    +----------------------------------------------------------------+
    
    MEM/WB
    +----------------------------------------------------------------+
    |OpCode 4 bits                                                   |
    +----------------------------------------------------------------+
        
Pipeline Performance

5P  Assume you have a processor with a CPI of 5 and a clock cycle time 
    of 2 ns. You wish to pipeline this processor with a 5 stage 
    pipeline and each stage will take a maximum of 2 ns. What is the 
    speedup for such a pipelined processor?
    
Process Abstraction

6P  List each processor scheduling algorithm and describe its 
    strengths and weaknesses.
    
    
7P  Examine the information on the 3 processes listed below    
    
        CPU Burst Time      IO Burst Time       Priority
    P1      3                   2               Lowest
    P2      4                   3               Highest
    P3      8                   4               Middle
    
    Show the activity in the processor and the I/O area using the:
    
    A. Priority algorithm
    
    0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16
CPU
I/O

Memory

8P. Describe the advantages and disadvantages of a paged memory 
    system. Include in your answer a discussion of the problems that 
    are solved and the problems that are created.

9P  Given:
      Processor word size 32 bits (word addressing is used)
      Logical address 32 bits
      Page size 1 K
      Physical address 32 bits
      Page table entries are 1 word each.
    
      How big is the page table (in words) for a single process?
      How many frames of physical memory are there assuming all
      possible frames allowed by the physical address are used?     
    
Processes
    
10p  a. Explain why we schedule processes and not programs. 

     b. Explain how we efficiently keep track of processes as they 
        move from ready queue to running to an I/O queue, etc. In 
        other words, what is the abstraction for the process that we 
        use to manage the process? 

     c. What kinds of information are we not required to keep track of 
        with respect to a process.