Midterm Study Questions

22C:116, Spring 2002

Douglas W. Jones

These questions are not intended to occupy all of your time prior to the midterm exam! Expect that at least 1/2 of the exam questions will not focus on the material discussed by these study questions, do not expect that the answers to any of these study questions will be the same as the answers to any of the exam questions.

These are study questions! They should motivate you to explore the material we have covered and focus on certain issues that will be central to some of the exam questions.

  1. Background: The UNIX kernel call sbrk(i), given an integer i, enlarges the program's static data segment by i bytes (rounded up to the page size if memory addressing is paged) and returns a pointer (traditionally of type char*, but void* on newer systems) to the first byte of the space that was newly added to the data segment.

    When a UNIX process is launched, there is no heap. The initial static segment is sized to just hold the static variables of the program, and no more. When the heap manager is first called, it uses sbrk() to create the initial heap, and whenever the heap is full -- that is, whenever an allocation request cannot be satisfied within the current heap, sbrk() is called again to enlarge the heap.

    An issue: What is a sensible value to use for i in the call sbrk(i) when the heap is found to be full as a result of a call to malloc(k)?

    An issue: If a storage allocator uses lazy merger of free blocks, when should sbrk() be called in relation to the merge operation?

    An issue: What is the relationship between fragmentation in the heap and the locality of reference of the program.

    An idea: Consider the following two interfaces to the heap manager in the context of a virtual memory environment:

    p = malloc( size )
    malloc() is a function returning a pointer to the allocated block.

    palloc( &p, size )
    malloc() is a procedure that stores a pointer to the allocated block in the variable p, given that the address of p is passed as a parameter.

    Explain how the heap manager can use the extra information passed to it in the second version to improve the locality property of applications in a way that would be generally infeasible if the first version was used. (Unfortunately, in C, the first version is standard!)

  2. Background: IBM's VM operating system was originally developed for the IBM System 360/67 and was the preferred operating system on the System 370. Today, its descendants are still in widespread use on IBM's line of enterprise servers (the name they prefer for what used to be called mainframes).

    VM (which stands for Virtual Machine) as originally developed had the interesting property that it would run applications that were intended to run stand-alone on a bare machine, a machine with no resident operating system. If you had, for example, an interactive text editor that ran on a bare machine, you could run it from an interactive terminal under VM with no need to make any changes changes. Because VM had control of the machine, the editor's attempts to read from the console keyboard would become reads from your interactive terminal. The editor's attempts to write to the console display would become writes to your interactive terminal, and the editors operations on the system disk would become operations on the virtual disk allocated to your process.

    In effect, each process under VM is provided by the operating system with an entire virtual computer system, complete with virtual resources corresponding to each of the physical resources of the real machine. This is the source of the name VM! Each of these virtual resources are mapped, through an appropriate resource manager to a physical resource. Thus, the virtual line printer attached to your process is actually implemented by the print spooler plus a physical printer.

    VM allows you to run your own favorite operating system under VM. Today, VM is usually run on an enterprise server, and it allocates one virtual machine to run some legacy IBM operating system such as OS/MVT while allocating other virtual machines to run LINUX or CMS, two decent interactive systems. It is even possible to run VM under VM, although obviously, stacking too many layers of operating systems degrades the system performance! Once VM began to work reasonably well, new versions of VM were debugged as if they were applications running under the production version of VM (applicatons debugging tools are far easier to use than debugging tools designed for use on a bare system).

    An issue: What operations performed by an applicaton running under VM are treated as system calls?

    An issue: Suppose a program running under Linux under VM makes a Linux kernel call. What kind of things must happen?

    An issue: Does VM require any special hardware? Does this hardware requirement differ in any essential way from the hardware required to run UNIX, Linux, or Windows/NT? For the purpose of this question, ignore questions of the specific instruction set (after all, Linux and VM both run on the IBM enterprise server family of machines).

    An issue: Think about the problem of memory management under VM. Suppose a program running under Linux running under VM causes a page fault. What kind of things must happen?