Final Exam Solutions

Grade Distributions

Final Exam

Median = 9.0                  X
                X             X
              X X       X     X
  ______X___X_X_X___X_X_X_____X_____X_________
   0 . 2 . 4 . 6 . 8 . 10. 12. 14. 16. 18. 20

Exam Solutions

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.

   __a_b______________

   4 got this, and an equal number gave just a or just b for more than half credit. Assembly language programmers clearly use assemblers to bind constant names to their values, compilers can pass this off to the assembler, but they can also do this entirely, so it makes sense to say, both! Only a few gave other answers!

   b) Binding a variable name with its type.

   __a________________

   6 got this, and 4 more gave a and b for about half credit. The important thing is that type checking is purely a compiler activity. There are no type enforcement rules in all but a few strange assembly or machine languages! Nonetheless, a few asserted that this was a loader or hardware issue!

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

   __a_(b)____________

   Compilers generally take care of the structure of activation records and other data structures, although with a little effort, this can be pushed off onto the assembler. Only 1 got any credit here, and all the rest suggested the linker, loader or run-time system would do this. Apparently, this reflects an extremely bad preparation in 22C:40 -- a reflection on the curriculum, not the students!

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

   __d________________

   4 got this, 1 got partial credit for d,e; the remainder got no credit.

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

   __a_b______________

   4 got this, 7 more got over half credit for a or b (mostly giving just b).

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

   __c________________

   12 got this, making it among the easiest questions on the exam!

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

   __d________________

   6 got this. Binding to virtual addresses is only finalized after relocation. I don't understand why this was easier than the question about binding global variables to specific addresses, because it's really the same question!

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

   __e________________

   7 got this, it should have been easier, because the memory management unit is always the one that finalizes binding to physical addresses.

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?

   ____a_b____________

   1 got this, and 3 more listed just a for more than half credit. It is easiest to work this by exclusion. The interrupt handler is clearly specific to a device (or family of extremely similar devices connected to the computer through identical hardware paths). So, you can't share a driver between a SCSI disk and an IEDE disk. Scheduling policies depend closely on device geometry and physics, so sharing these would be difficult.

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

   ___the_block_or_sector_size__________________________________

   One common bit of code can be shared by all devices for deblocking, with only the block or sector size being used as a parameter to determine how it divides a stream of data into blocks for lower level work. 3 got this, 2 more got half credit for mixing in a measure of oddness.

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

   ___c_______________

   12 got this, making it among the easiest questions on the exam!

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

   ___c_______________

   7 got this. Note that the enqueue routine for a disk queue is typically called from above, in this case, by the file system layer, while the dequeue routine is called by the interrupt handler, the layer below!

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?

   ___one_____________

   4 got this, 1 more said one per device. This is a bit surprising, since few programmers at the undergrad level have written programs that posted I/O requests as a distinct operation from waiting for their completion. You can't do this in Java or C++, and you can't do it using the Unix I/O interface!

   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?

   ___the_number_of_threads_____________________________________

   2 gave this answer, and a few got a tiny bit of credit for suggesting vaguely connected attributes of a process. If you're writing typical Unix or C++ or Java programs, each thread can be blocked waiting for one I/O operation to finish, so the number of threads determines this!

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

   __b_________ ___the_disk_scheduler_can_help_when_the_queue_is_long________

   8 knew it was b, but they didn't understand the potential importance of the disk scheduler, and instead, emphasized overlap of I/O and computation. This is good, but it is a small effect in a truly I/O bound application -- it has a big impact only when the application is balanced between I/O and CPU demand.

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

   __a__________ __this_eliminates_the_context_switching_overhead_____________

   8 got this, and most understood the overhead of context switching.

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.

   ____the_heap_manager_can't_optimize_for_locality_________________________

   3 did well here, 2 more got good partial credit

   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.

   ___knowing_where_the_pointer_is,_it_can_try_to_optimize_allocation_______

   3 did well here, 2 more got good partial credit

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?

   ___the_interrupt_service_routine_can't_change_the_stack_pointer__________

   ___in_order_to_allow_return_to_a_different_context_______________________

   6 did well here, and 3 more gave confusing but fairly good answers. 2 got half credit for the assertion that there is no real-time clock (actually there is, but it doesn't help because of the problems with the stack)!

   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?

   ___returns_would_frequently_end_up_going_to_the_wrong_place______________

   ___typically_in_the_wrong_thread's_past__________________________________

   4 got this, 2 got half credit, and a few had vaguely relevant andwers.