Assignment 11, due Nov 15

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

  1. Background: There was one error in the spec for the Demos-like model given in the previous assignment. This is corrected here; changes are in italics:
    s = send( dst, buf, len );
    send to dst (of type link) the contents of the buffer buf (of type void*) with a length in bytes of len (of type int). Variables of type link may be directly included in the buffer. This blocks until the message has been delivered. The number of bytes delivered to the receiver will be the minimum of the sender's and receiver's buffer sizes; this is returned to the sender after successful message delivery. If dst is an invalid link, the return value is -1, the thread does not block, and no message is delivered.

    s = receive( queuetab, number, buf, len );
    receive a message from the indicated queue number (an integer) in the queue table queuetab (of type queuetable*) into the buffer buf (of type void*) with a length in bytes of len (of type int). This blocks until the message has been delivered. The number of bytes delivered to the receiver will be the minimum of the sender's and receiver's buffer sizes; the sender's buffer size is returned to the receiver after successful message delivery so that the receiver may determine if data has been lost. If an invalid queue number is used, the return value is -1, the thread does not block, and no message is delivered.

    number = queueselect( queuetab, numbers, len );
    given numbers (of type int*), an array of len (of type int) integers, each interpreted as a queue number, and given queuetab (of type queuetable*), block until one of the queues indexed in numbers contains a message, and return the queue number. If more than one of the queues mentioned in numbers contains a message, the number returned may refer to any one of them.

    queuetab = newqueuetable( slots );
    allocate a queue table with a capacity of slots queues (an integer), returning a pointer to that table in queuetab (of type queuetable*). All the queues in the table are initially empty.

    link = newlink( queuetab, number );
    return a link allowing sending of messages to the indicated queue number (an integer) in the indicated queue table.

    Note that this set of primitives doesn't require the use of a link table because we allow links to be stored intermixed with normal variables. Note also that the queue table is not necessarily implemented as an array of queues! It is an abstraction which may have additional complexity.

    Problem: Finish the implementation of these primitives.

  2. Background: The Intel Hypercube family of supercomputers, sold during the 1980's, had computer modules that contained an 80x86 CPU, RAM and 10 ethernet interfaces each. The ethernet interfaces were intended for point-to-point links along the edge of the hypercube, so these systems could be configured with up to to 210 computer modules. One of the ethernet interfaces in each hypercube was typically used to communicate with the outside world.

    I/O to and from such a hypercube is a major bottleneck, so Intel sold an alternate configuration in which the number of computer modules was halved and each computer module was configured with a local hard drive. This was seen as an intriguing candidate for use as a database engine, and it still an interesting alternative to pairing a supercomputer with a large RAID for many applications.

    Part A: Which RAID levels are feasible on the Intel Hypercube family? Refer to Figure 5-19 in the text.

    Part B: Assume we wish to use RAID level 1 on an Intel Hypercube. As a result, a process reading or writing a file must perform a distributed computation. Identify the atomic transactions that must be built into the primitive read and write operations, if we assume the use of a conventional Unix-like file system.

  3. A Problem from the text:
    Do problem 26 on page 376.