Assignment 7 Solutions

Part of the homework for 22C:50, Summer 2004
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

  1. The standard C library routine fputc( char c, FILE * f) puts one character out to the given file. This is implemented using the standard Unix output routine write( int fd, char * buf, int size ). In effect, fputc does blocking (defined in Chapter 9), and its complement, fgetc does deblocking. For further details about either of these, refer to the documentaton available from the Unix/Linux man command. Note, because there are multiple write commands in different sections of the manual, you will need to say man 2 write in order to get the relevant document (section 1 of the manual documents shell commands, section 2 documents the operating system interface, section 3 documents the C standard library).

    a) Propose a representation of objects of type FILE as used in the C standard library to represent output data streams, inasmuch as you can infer this from the manual information about the putc and write calls.

    	typedef struct file {
    		int fd;    /* file descriptor of Unix file */
    		char * buf; /* pointer to the buffer */
    		int bufsize; /* size of the buffer */
    		char * pos; /* pointer to the position in the buffer */
    	} FILE;

    b) Propose an implementation of the fputc function in terms of your representation proposed in part a. Ignore any strangeness involved with interactive files.

    	int fputc( int ch, FILE * stream )
    		stream->pos = ch;
    		if (stream->pos > (stream->buf + stream->bufsize)) {
    			write( stream->fd, stream->buf, stream->bufsize );
    			stream->pos = stream->buf;
    		return ch;

    Note that the above solution ignores the possibility that write might fail. That would obscure the essential behavior of this code.

    c) Explain why it is useful to have a macro, putc as well as a callable function, fputc to perform the same operation.

    The overhead of a function call can be significant, involving several instructions to call the function and return from it. Since the amount of work done in a normal call to fputc is very small, elimination of the overhead of function calls can lead to a significant speedup.

  2. Suppose you are responsible for implementing a character sequential driver such as the one discussed in Figure 10.8. Assume you are intent on using an object oriented implementation. It could be in a language like Java or C++, or you could fake it in C, this does not matter.

    a) What are the methods applicable to the objects of class queue that are required by this driver?

    	queueinstance.enqueue( ch )
    	ch = queueinstance.dequeue()

    b) What variables or data structures must be encapsulated into each queue object (that is, used for the representaton of each queue object)? To answer this question, you will have to select an appropriate queue implementation.

    Each queue object would contain a buffer, a head pointer and a tail pointer if we use a bounded buffer implementation.

    c) When would you input/output driver allocate (instantiate) new queue objects and what would be the lifetime of these objects?

    A pair of queue objects are associated with each input/output device, one queue each for input and output. So, if devices may not be changed while the system is running, these queues can be statically allocated. If devices may be dynamically connected to the system, as with USB devices, then whenever the system detects connection of a new device that uses this driver, a new pair of queue objects would be allocated, and whenever the system detects disconnection, the corresponding queues would be deallocated.