CS414 Operating Systems - Homework 2

Due Due: Feb 12, 10am. No late assignments will be accepted.

Submit your solution using CMS. Prepare your solution using Word (.doc) or some ascii editor (.txt), as follows:

• Use 10 point or larger font.
• Start each problem's solution on a new page.
• Use at most 1 page per problem.

1. Consider the following 2-process concurrent program, which manipulates the value of a shared integer variable s that initially equals 0.

   VAR s : INTEGER INITIAL(0)
   
   p1: PROCESS;
         VAR i : INTEGER;
         FOR i:= 1 TO 5 BY 1
               s := s + 1
             END
       END PROCESS p1
   
   p2: PROCESS;
         VAR j : INTEGER;
         FOR j:= 1 TO 5 BY 1
               s := s - 1
             END
       END PROCESS p2
   

   1. What is the largest value that s could have when these 2 processes terminate?
   2. What is the smallest value that s could have when these 2 processes terminate?
   3. What other integer values are possible when execution of these 2 processes terminate.

   ---

2. A new instruction set is being contemplated for a next generation of processor. This instruction set contains the usual instructions to store, load, and manipulate data, as well as a novel "interlock" instruction for implementing critical sections: evenize(s,t).
   • Instructions that access a single word of memory (e.g., load and store) are assumed to execute atomically.
   • evenize(s,t) is assumed to execute atomically.
   • Execution of evenize(s,t) is assumed to have the following effect:

     evenize(s,t):  t := s
                    s := shift_left_by_1(s)
     

   Use evenize(s,t) in conjunction with the usual (non-interlock) instructions found on a processor and implement entry and exit protocols for solving the critical section problem. Or explain why no such protocol can be constructed. Feel free to present your solution using a high-level language notation instead of assembly language.

   ---

3. Suppose instead of evenize(s,t), the following instruction were added.

   incr(s,t):  s := s + 1
               t := s
   

   Assume a word size of 32 bits.

   Use incr(s,t) in conjunction with the usual (non-interlock) instructions found on a processor and implement entry and exit protocols for solving the critical section problem. Or explain why no such protocol can be constructed. Feel free to present your solution using a high-level language notation instead of assembly language.

   ---

4. We outlined in class a way to multiplex a processor by using timer interrupts. The essential elements include the following.
   • The kernel maintains an array

     process_states[1 .. n] of processorState

     where each element of the array stores a process state (i.e., the registers, program counter (pc), status word defining which interrupts are disabled, etc). Note, the interval timer is not considered part of a process state.

   • The kernel maintains an integer variable running to indicate which element of process_states most recently was loaded by the kernel into the processor registers.
   • Instruction LDST addr causes the process state starting at address addr to be loaded into the processor registers.
   • Instruction LDIT val causes the interval timer to be loaded with value val.
   • Associated with each interrupt type int (where the interrupt types include timer and inp-out) is:
     • old_int, a corresponding interrupt "old" area where the process state is stored by hardware when the interrupt occurs,
     • new_int, a corresponding interrupt "new" area that is initialized by the operating system kernel and from which a process state is loaded by hardware when an interrupt occurs (so that control transfers to the appropriate interrupt handler), and
     • two instructions: IntEn_int and IntDis_int. Instruction IntEn_int causes interrupts of type int to become enabled and any pending interrupts of type int are delivered; IntDis_int causes interrupts of type int to become disabled (so they remain pending when they occur).
   • Function SelectNextReady implements a short-term scheduler and thus returns an integer between 1 and n that corresponds to a process that can next be loaded into the processor registers and executed.

   Below is proposed code for an I/O interrupt handler. Thus, you can assume the value corresponding to pc in new_inp-out contains the address of io_intrpt_handler.

   io_intrpt_handler:  
        IntDis inp-out
        process_states[ running ] := old_inp-out
        ... i/o device specific actions ...
        running := SelectNextReady
        LDIT 100000
        LDST process_states[ running ]
   

   1. At the code review for io_intrpt_handler, one of the engineers complained that it seemed as though inp-out interrupts are being disabled but never re-enabled and argued that an IntEn_inp-out instruction should be added to this code segment. Argue that adding such an instruction is not necessary (and therefore the reviewer is wrong) by explaining how the desired effect of re-enabling inp-out interrupts is (presumably) being achieved by other means.

   2. There are, nevertheless, reports of odd behavior in the system. Processes seem to terminate prematurely and without a trace. The problem is especially prevalent when I/O loads are heavy. Hypothesize the cause and suggest a repair.

   ---

5. What are the similarities and differences between multiprogramming and multiprocessing?