Assignment 5 Solutions

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

  1. Background: There is a user-level thread package written in C and callable from C or C++ programs on-line at:
    http://homepage.cs.uiowa.edu/~dwjones/opsys/threads/

    The usual way for a C program to read a character from standard input is to call ch=getchar(); for many purposes, this is equivalent to the Unix kernel call read(0,&ch,1). (Under Unix, file descriptor zero is standard input.)

    The Problem: Write, thread_getchar(), a routine to read a character from standard input under the thread manager. This would have to allow other threads to run until a character was available on standard input.

    Suggestion: You could use the select() Unix kernel call to implement this, or you could you use the O_NONBLOCK option for the open() kernel call (opening /dev/tty, the current interactive terminal) to implement this, or you could use fcntl to set the O_NONBLOCK attribute of file descriptor zero, which is already open. (See the unix man pages for documentation of these services!)

    	char thread_getchar()
    	{
    		char ch; /* a one-character read buffer */
    		if (readylist.head == thread_null) {
    			/* there is only one thread, do blocking read */
    			read( 0, &ch, 1 );
    		} else {
    			/* there are many threads, do nonblocking read */
    			int flags = fcntl( 0, F_GETFL, 0 );
    			int count;
    			fcntl( 0, F_SETFL, flags | O_NONBLOCK );
    			for (;;) {
    				/* polling loop letting other threads run */
    				count = read( 0, &ch, 1 );
    				if (count == 1) break;
    				thread_relinquish();
    			}
    			fcntl( 0, F_SETFL, flags );
    			/* restore flags here to avoid needing global state */
    		}
    		return ch;
    	}
    
  2. Background: Your code for thread_getchar() probably makes one or two kernel calls each time you call it. Kernel calls are typically more expensive than procedure or function calls because of the cost of crossing the user/kernel protection boundary.

    A Problem: Under certain circumstances, some of the kernel calls suggested above allow thread-getchar() to make fewer than 1 kernel call per character being read. What implementation would allow this, and under what circumstances will this be true?

    A Hint: Consider the difference between getchar() as defined in <stdio.h> and the Unix kernel call read(0,&ch,1). You can read the source for the former in /usr/include/stdio.h.

    When the user has typed several characters of input into the typeahead buffer while the application has not consumed these, a single call to read can consume these from the I/O driver's queue, after which, successive calls to thread_getchar() should be able to return characters from some internal buffer without going to the expense of contacting the operating system.

    If we set O_NONBLOCK, as in the solution distributed above, but instead of reading one character, we read all the available characters into a static buffer, then when this buffer is nonempty, thread_getchar() can simply consume from it, while it uses the logic given in the solution above only when the buffer is found to be empty.

  3. Background: You know that the page-fault handler in a virtual memory system must do disk I/O in order to handle a fault. Suppose we have a hard drive with one partition reserved as the "swap space" used for the virtual memory of the entire system, with many different processes running on the system.

    Further, suppose our disk I/O driver uses the elevator algorithm for disk I/O scheduling, and that it uses the trick suggested in the course notes to use the pending requests in the disk queue as a cache.

    A Question: Explain the relationship between the process manager, the disk interrupt service routine and the page-fault handler. Focus on the time when the disk I/O transfer required to service a page fault is completed.

    If we assume that the page fault handler enqueues requests for disk I/O in the disk request queue, when a disk I/O request is completed, the disk interrupt service routine must do one of two things.

    One option is to inform the disk I/O interrupt handler that the disk I/O that was just completed was part of the service for a page fault. In this case, that the disk I/O interrupt service routine can continue with any necessary processing of the page fault. From the perspective of the scheduler, the page fault service routine in this case is very similar to an interrupt service routine, operating outside the scheduler's authority.

    Alternatively, the disk I/O interrupt service routine does not know that the I/O just completed was part of the service for a page fault, so it must treat I/O completion for a page fault just like I/O completion of any user read or write. In that case, the scheduler must view the page fault handler must operate as operating as part of the user process.

  4. A Problem: Do problem 11 on page 374 of the text. The numbers requested in the text give the peak data rate to or from the device. Also compute the average data rate you'd expect for a sequence of input or output requests to randomly selected sectors on disk.

    The peak transfer rate is approximately the number of bytes per track times the number of revolutions per second. This is an approximation because it ignores the intersector gap, and it ignores any prolog and epilog that may be recorded with each sector.

    Formula: sect/track * bytes/sect * revs/sec = bytes/sec
    Floppy: 9 * 512 * 1/0.200 = 23,040
    Hard: 281 * 512 * 1/0.00833 = 17,270,000

    The average transfer rate is approximated by assuming an average seek plus an average rotational latency between each pair of successive one-sector reads, and then computing sectors per second and multiplying by bytes per sector.

    Formula: bytes/sector / (sec/seek + sec/rotate / 2 + sec/sector) = bytes/sec
    Floppy: 512/(0.077 + 0.200/2 + 0.022) = 2,573
    Hard: 512/(0.0069 + 0.00833/2 + 0.000017) = 46,180