Assignment 1, Solutions

Part of the homework for 22C:116, fall 2002
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

  1. What is your E-mail address? (If you have more than one, give the address you'd prefer used for class purposes.)

    No solution given

  2. What operating system or systems were used for programming assignments in your previous operating system courses. For this purpose, count as an operating system course any course where you worked directly with the facilities of an operating system kernel, without the protecting cloak of middleware such as the standard Java, C or C++ libraries -- these are, after all, tools designed to protect you from having to learn about operating systems.

    No solution given

  3. What computer architecture or architectures were the focus of your previous computer hardware courses. For this purpose, count as hardware courses any courses where you had to either program in assembly language, write software to generate code in machine language, or study the construction of hardware or software to execute a machine language. Please indicate which of the above you have done with each such machine architecture you have used.

    No solution given

  4. Background: Consider an object O of class C, where M is a method of O and P is a parameter to the method M. The class C has several subclasses, each with its own implementation of M. A call to method M of object O passing parameter P would be written as follows in a typical object-oriented programming language: 
          O.M(P)
    There are several well-known approaches to implementing polymorphic objects; The fastest stores, in each object, pointers to the code of the polymorphic methods of that object's class. Objects with many polymorphic methods are therefore large. To minimize the object size, we can store, in each object, a pointer to the descriptor for the object's class, and store pointers to all of the polymorphic methods in the class descriptor.

    Problem: Give code or pseudocode at the machine language level for the example call given above. Use the machine architecture you know best, or alternatively, give code in C (not C++) instead of machine code or machine-level pseudocode.

    Pseudocode, by the way, gives details about some computation with an informal disregard for syntactic formality.

    The following answers ignore multiple inheritance; this simplifies things considerably. If we assume each object contains pointers to its methods, the C code will be:

    (*(O->M))(O,P)

    Here, field M of structure O is a pointer to the function that implements the method, and this function takes 2 parameters. The first parameter is the structure itself, so the function has access to the object itself! If each object contains only a pointer to its class descriptor, where the descriptor has pointers to the relevant methods, the C code would be:

    (*(O->Class->M))(O,P)

    In assembly language, the former solution might be coded as follows on a typical RISC machine:

    LOAD X1,O ;index register 1 gets a pointer to object O
    LOAD X3,M(X1) ;index register 3 gets the contents of field M
    LOAD X2,P ;index register 2 gets the parameter P
    CALL (X3) ;call the function pointed to by X3
    ; we assume the called function expects its parameters in X1 and X2

  5. Background Function calls are typically implemented by an instruction or an instruction sequence (the calling sequence) that pushes certain information on the stack. Calls to interrupt handlers typically begin with the hardware's interrupt transfer mechanism followed by some instructions to push certain information on the stack.

    The Question What is the difference between the information pushed on the stack by a typical function call and by response to a typical interrupt.

    A function call need only push the return address and the contents of the few general purpose registers it will use during its execution. If it pushes registers it does not use, this is because either there is a very low-cost mechanism for saving all registers or because the compiler was unable to determine, at the time the calling sequence was finalized, what registers the function would need.

    In contrast, an interrupt service routine must typically save not only the general purpose registers that it will be using, but also significant parts of the processor state that are hidden from user programmers. These hidden parts of the state might include such things as the memory management unit control registers and the state of the hardware protection mechanism. The interrupt entry and exit sequences are almost always hand-coded in assembly or machine language, so the amount of information saved is not a function of the intelligence of the compiler.