Assignment 10 Solutions

1. Why is there no such thing as a segment frame?

Since each segment has (potentially) a different size, no standard size frame can be reasonably expected to efficiently hold any segment.

10. Assuming a machine with one accumulator and a memory which is addressed in units of words, where the page size is moderately large, how many different page faults could be caused by an attempt to fetch and execute one instruction, if that instruction is one of the following:

a) LOAD X -- a single word instruction, including the operand address?

Two faults, one for the instruction itself, and one for the page holding the operand.

b) MOVE A,B -- a 3 word instruction (opcode and 2 operand address words)?

Four faults. The instruction itself could cause two faults, one for the page holding the first word of the instruction, and one for the page holding the remainder of the instruction, if the 3 word instruction spans a page boundary. In addition, there could be two more faults, one for the page holding each operand.

c) ADDF A,B,C -- a 4 word instruction (opcode, 3 operand addresses), where each operand is two words long?

Eight faults. The instruction could cause two faults, as above. In addition, because each operand could span a page boundary, each of the three operands could cause two faults.

14. The division of a 32 bit virtual address into 10 bits of segment number, 10 bits of page number, and 12 bits of byte number works out very nicely if each page table and segment table entry is 32 bits. What is the perfect size for a page table or segment table entry if the 32-bit virtual address is broken on a 9/9/14 pattern?

Here, a page is 2¹⁴ or 16K bytes, and the page table and segment table each have 2⁹ or 512 entries. Therefore, we can use a full page (or page frame) to hold the page table for a segment or the segment table for an address space if the entries in that table each take up 2^14-9 or 2⁵ or 32 bytes (4 words of 32 bits each).

3. Recode the deallocate routine shown in Figure 14.4 to eliminate recursion.

void deallocate( pointer block, int size )
{
     int i;
     pointer * p;
     pointer buddy;

     /* compute i as the least integer such that i >= log2(size) */
     for (i = 0; BLOCKSIZE( i ) < size; i++);

     for (;;) { /* loop exit is by return from within body */

          /* see if this block's buddy is free */
          buddy = BUDDYOF( block, i );
          p = &freelists[i];
          while ((*p != NULL) && (*p != buddy)) p = (pointer *)*p;
     
          if (*p != buddy) {
     
               /* buddy not free, put block on its free list */
               *(pointer *)block = freelists[i];
               freelists[i] = block;
               return;
     
          }
     
          /* buddy found, remove it from its free list */
          *p = *(pointer *)buddy;
     
          /* deallocate the block and its buddy as one block */
          i = i + 1;
          if (block > buddy) block = buddy;
     }
}