CS2200 Summer 2005 Practice Test 2

Interrupts

1P. Write an interrupt handler in LC-2200 assembly language that
    will allow itelf to be interrupted. Assume that the handler
    takes the contents of address 0xFFF0 and stores it in the
    location pointed to by the contents of location 0x4000
    after which it increments 0x4000. You may assume that
    0x4000 has been initialized already.
    
Performance

2P. Assume a processor has the following mix of instructions:
    
    Instruction     CPI     Percent of Dynamic 
                            Instruction Count
    ADD/ADDI/NAND   5       33%
    BEQ             6       24%
    LW/SW           7       29%
    JALR            4       14%   
    
    What is the CPI of this processor?
    
Pipelining

3P. Starting with a basic pipeline design show what changes you 
    would need to make to implement a pop instruction. This 
    instruction (pop R) will load the value of the memory location 
    pointed to by the stack pointer ($sp) into the register R and 
    then $sp will be decremented. Your design must do this as 
    efficiently as possible. You should include in your answer the 
    contents of the pipeline registers. Can this instruction be 
    completed in 5 cycles?

Process

4P. Given the following processes:

         Process ID      Priority        Typical Burst Time
                        (1 is highest)
        P1              2               6 ms
        P2              1               3
        P3              2               4
        P4              4               5
        P5              5               7
        P6              3               6
        
        
    Show the processor activity for the above processes given the 
    following scheduling algorithms:
    
    Priority
      1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22  
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
            
    Shortest Job First
      1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22  
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    
    Round Robin
      1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22  
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    
    First Come First Served
      1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22  
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    
    You only have to go as far as the chart will allow.
    
Memory

5P. A certain processors memory system has the following characteristics:

    Virtual address is 32 bits long
    
    Physical address is 48 bits long (and sufficient memory exists to
    use the full address space)
    
    Page size is 1 kByte
    
    Assume 1 32-bit word (4 bytes) for each page table entry
    
    How many entries are in the page table?
    
    How many bits are in the offset part of the virtual address
    
    How many frames are there in memory?
    
    How may bits in the Virtual Page Number?
    
    How many bits in the Physical Frame Number?   
    
6P. Given the following Page references show the activity for an optimal
    replacement policy. IMPORTANT: ASSUME THAT THE REFERENCES REPEAT IN
    THIS PATTERN INFINITELY.
   
   
     Page References:                      
Frame     1  2  3  1  3  4  2  5  4  2  1  3  1  2  5  1  2  1  3  4  5  2   
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    1   |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    2   |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    3   |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+