Homework 5 Solutions

22C:116, Spring 2002

Douglas W. Jones
  1. Part A: Rewrite your application code that said write(1,"string\n",7) to operate correctly under the preemptive thread manager (some relevant material is in the notes for lecture 14, but you'll also find help in the UNIX man page for write).

    
    	{
    		int remaining = 7;
    		char* bp = "string\n";
    		for (;;) {
    			int n = write( d, bp, nb );
    			if (errno != EINTR) break;
    			if (n == remaining) break;
    			remaining = remaining - n;
    			bp = bp + n;
    		}
    	}
    
    

    Part B: Package your solution to part A in a function, thread_write, that can be substituted for all calls to write in your program.

    If the delivery of a signal interrupt a write operation, causing it to write fewer bytes than required, we will need to add a thread-safe write routine such as the following:
    
    	int thread_write( int d, char* buf, int nbytes)
    	{
    		int remaining = nbytes;
    		int done = 0;
    		char* bp = buf;
    		for (;;) {
    			int n = write( d, bp, nb );
    			done = done + n;
    			if (errno != EINTR) break;
    			if (n == remaining) break;
    			remaining = remaining - n;
    			bp = bp + n;
    		}
    		return done;
    	}
    
    

  2. For each of the following suggested mechanisms for anticipatory paging, suggest the likelyhood that adding it to the virtual memory system would lead to a significant performance improvement:

    a) We could add a system call "anticipate(x)" that the user can use to predict that a use of page x will come soon, and then urge users to include it in their code whenever they can guess future reference patterns of their program.

    Most users are unlikely to bother inserting calls to anticipate() in their code, and when they try to do so, many users will make poor guesses about which pages they should anticipate using.

    For a few very important applications, however, where the developer can afford the time to instrument the applicaton and find out what pages it references that can be anticipated, use of this system call may lead to significant performance improvements.

    All of this is, however, predicated on the size of the available memory. The set of pages that should be anticaped if there are N available page frames may be significantly different from the set that should be anticipated if there are 2*N page frames. Therefore, while this may allow expensive optimization of a program for a particular system configuration, the entire optimization process may need to be repeated if the configuration is changed.

    b) We could ask the system to attempt to anticipate user reference patterns. For example, when a page fault occurs for page x, the system could check to see if page x+1 is in memory, and if it is not, schedule a read for that page too, since most memory references tend to be sequential.

    Bringing in not only the page that caused a fault but the next successive page in the address space will pay off quite well for programs that have blocks of sequential memory accesses that are larger than a page. Thus, if the page size is smaller than many of the program's arrays, or if the page size is smaller than many of the functions in the program, this will be likely to pay off, while if the program has choppy code (large numbers of very small functions) and choppy data (lots of small objects, with large objects represented by linked data structures of small pieces), this will not have much advantage.

  3. Problems from the Text:
    Do problem 32 on page 266 in the text.
    If pages can be shared between processes (for example, if read-only code segments are shared, as in most UNIX systems), then such pages can be in multiple working sets.

    Do problem 36 on page 267 in the text.
    If the instruction is load memory-to-register and the instruction contains the absolute 32-bit address of the operand, the instruction itself must be larger than 32 bits.

    Assuming that the machine has word addressable memory, the instruction itself may span a page boundary, but the operand may not (because it is a word), so we could have a total of 3 faults, 2 page faults caused by attempts to fetch the instruction itself and one more fault caused by the operand reference. Here, we assumed that none of the pages involved was in memory to begin with, and we assumed that the first word of the instruction was in the last word of one page.

    If the machine has byte addressable memory and if it supports non-aligned operands, it is possible for this instruction to cause 4 faults because the operand itself may span a page boundary.