Final Exam

Name: ________________________________________________

ID Number: ___________________

Please write your answers in the space provided! Make sure your name is in the same form as it appears on your University ID card! Illegible and excessively long answers will be penalized! This exam is open-book, open-notes, closed neighbor! This exam is worth 1/5 of the final grade (20 points; allocate 2 minutes per point).

1. Background: A program is:
   1. compiled and then
   2. assembled and then
   3. linked with some library and then
   4. loaded by a relocating loader and then
   5. run on a machine that has a memory management unit

   The binding of attributes to names in the original program happens at different stages in this process. For each of the following, identify (by number) the stage or stages that are most likely to be involved in determining the binding of the indicated attribute. (0.5 points each)

   a) Binding an integer constant's name with a specific value.

   ___________________

   b) Binding a variable name with its type.

   ___________________

   c) Binding a local variable to a specific offset from the base of the activation record of a function.

   ___________________

   d) Binding a global variable to a specific virtual address.

   ___________________

   e) Binding an internal function name to a specific sequence of instructions.

   ___________________

   f) Binding an external function name to a specific sequence of instructions.

   ___________________

   g) Binding a function name to the virtual address of the first instruction of the receiving sequence of that function.

   ___________________

   h) Binding a global variable to a specific physical address.

   ___________________

    

2. Background: Consider an operating system with the following sequence of layers used between user processes and random access devices such as disks:
   1. Blocking and deblocking
   2. File address to device address translation
   3. Device queues and scheduling
   4. Interrupt handlers

   Answer these questions: (1 point each)

   a) Which of these layers can be device independent, used equally by a large number of different devices?

   ___________________

   b) What device specific information must be available to the first blocking and deblocking layer for it to perform its primary function?

   _____________________________________________________________

   c) Which of these layers is able to perform some cache functions in order to speed access to a device?

   ___________________

   d) Only one of these layers is likely to contain routines that are called both from the layer above and the layer below. Which?

   ___________________

    

    

3. Background: Consider two identical uniprocessor computer systems running identically the same operating system, and each supporting exactly one application program; these applications perform identically the same function, but they do it in different ways. The only difference is that
   • The application on system A is single-threaded.
   • The application on system B is multi-threaded.

   Answer these questions: (1 point each)

   a) What is the maximum length of the disk request queue you are likely to observe on system A?

   ___________________

   b) What attribute of the application would you expect to set the limit on the maximum observed length of the request queue for system B?

   _____________________________________________________________

   c) If the application is input-output bound, which system would you expect to run faster, and why?

   ____________ _____________________________________________________________

   d) If the application is CPU bound, which system would you expect to run faster, and why?

   _____________ _____________________________________________________________

    

    

    

4. Background: Application programs written in Java use a separately allocated block of data on the heap for each object, so when one object contains another another object, the representation of the object will hold a handle, or pointer, to the representation of its component object. Consider the following two heap manager interfaces used when instantiating objects:
   • The classic Unix malloc(s) function, returning a pointer to a newly allocated block of size s.

   • An alternative allocate(p,s) function, which allocates a block of size s and stores it in the pointer pointed to by p.

   Answer the following: (2 points each)

   a) Explain why use of the malloc(s) interface could lead to poor performance on a demand-paged virtual memory system.

   _________________________________________________________________________

   _________________________________________________________________________

   b) Explain how a heap manager using the second interface given above could attempt to overcome this performance problem by using the additional information passed to the heap manager by its caller.

   _________________________________________________________________________

   _________________________________________________________________________

    

5. Background: The widely used PIC family of microcontrollers, made by Microchip Inc, have an instruction set with the following characteristics:
   • The CPU has a small built-in push-down stack (it is not in RAM).
   • The call instruction pushes the program counter on this stack.
   • Interrupts push the program counter on this stack.
   • The return instruction pops the program counter from this stack.
   • No other instructions reference this stack or stack pointer.
   • No other instructions are provided for funciton calling.

   Answer the following questions: (2 points each)

   a) It is impossible to construct a preemptive scheduler on this machine. Why?

   _________________________________________________________________________

   _________________________________________________________________________

   b) Assume you have a cooperative thread package for the PIC; what potential for confusion results when a thread calls a function, and that function uses a thread-scheduler operation such as yield or relinquish?

   _________________________________________________________________________

   _________________________________________________________________________