Assignment 9, due Nov 1

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

  1. Background: Problem 2 on the midterm, part B, can be restated in the following terms: Consider a system using demand paged virtual memory. When a page is in main memory, the page table entry is marked as valid and it contains the physical address of the page. When a page has been swapped out to disk, the page table entry is marked as invalid and it contains the disk sector number holding the page.

    A Problem: If each process has its own virtual address map, does this make it difficult to implement shared pages? Why, and why does your answer change when you segment the address map and share entire segments?

    Note: One problem is identical with shared pages or shared segments: with either scheme, a block of shared memory may be assigned different virtual addresses in the two different page tables, and this leads to trouble with linked lists or other data structures containing shared pointers. Clearly, this is not the issue!

  2. Background: The notes for Lecture 22 includes an example of protocol bloat where transmitting an 8-bit character through the session layer requires transmission of 286 bits over the physical communications medium.

    Note that the packet sizes imposed by the formats for the session, transport and network layers are limited to 256 bytes because of the use of 1-byte message-size fields. The link layer uses reserved STX, ETX and EOT characters (presumably, it also uses some kind of escape codes when these special characters are present in the data from upper layers, but you can ignore that detail here).

    For this problem, we define the utilization of the physical layer to the the ratio of actual user data sent (from above the session layer) to total bits transmitted over the physical layer.

    Problem: What is the maximum utilization possible, given the limits on packet size set by each of the layers. Assume that there are only two users of the network, and that these users exchange packets alternately and as fast as possible. Ignore the time taken by all computations.

  3. Background: Consider the problem of implementing the Demos model of interprocess communication under our example thread manager. Assume that messages are passed by copying from the sender's buffer to the receiver's buffer and that the sender blocks until the message has been copied to the recipient (this is called synchronous message passing).

    Part A: Synchronous message passing involves the sender and receiver both blocking until the message has been conveyed. Given that our thread package has semaphores, these must be the tools we use to block. Give a protocol allowing the sender and receiver of a message to block at the right times; in giving this, you must specify what semaphores are used, what components they are associated with, and where the wait and signal operations go relative to the code for copying the buffers.

    Part B: Present an appropriate data structure (or appropriate data structures) for representing a request by a sender to send a message to a receiver. This may contain some combination of data, pointers to data, links, pointers to links, and semaphores or pointers to semaphores.

    Notice: This is all in preparation for an upcoming programming problem.

  4. Problems from the Text:
    Problem 22 on page 580.
    Problem 32 on page 581.