Homework 4 Solutions

22C:116, Fall 1998

Background: A quick examination of the dining philosopher's problem shows that it is never possible for more than two philosophers to eat at one time. Therefore, one solution which is guaranteed to be deadlock free involves adding two tokens to the table, perhaps salt shakers. If each philosopher first collects a salt shaker before attempting to collect forks, then eats, and then puts the salt shaker back, it will be possible for up to two philosophers to eat at once.
Part A: Both the above solution to the dining philosopher's problem and the solution in Figure 2.20 of the text are deadlock free. In addition, both allow two philosophers to eat at once. Tannenbaum's solution always allows two non-adjacent philosophers to eat, while the salt-shaker solution will sometimes allow only one philosopher to eat, because that philosopher's neighbor could take the second saltshaker.
The salt-shaker solution does prevent starvation so long as the semaphore waiting queues are fair (FIFO and random are both fair). Tannenbaum's solution appears not to solve the starvation problem -- two philosophers can take turns eating, preventing the philosopher between them from ever being able to eat.
Part B: Consider the following implementation of the think() operation for use under our example thread package:
```
/****
 * dining philosophers *
 *                  ****/

#include 
#include "threads.h"

void random_wait()
{
    int i;
    do {
        thread_relinquish();
    while (random() & 7);
}

#define eat random_wait
#define think random_wait

semaphore saltshaker;
semaphore forks[5];

void philosopher( int i )
{
    for (;;) {
        think();
	thread_wait( &salt_shaker );
	thread_wait( &forks[i] );
	thread_wait( &forks[(i+1)%5] );
	eat();
	thread_signal( &salt_shaker );
	thread_signal( &forks[i] );
	thread_signal( &forks[(i+1)%5] );
    }
}

int main()
{
    int i;
    srandom( getpid() );  /* makes runs somewhat nondeterministic */
    thread_manager_init();
    thread_semaphore_init( &salt_shaker, 2 );
    for (i=0; i<5; i++) {
        thread_semaphore_init( &forks[i], 1 );
        thread_launch( 4000, philosopher, i );
    }
    thread_manager_start();
}
```

Background: Refer to the discussion of the clock algorithm in the notes and on page 111 in the text. Assume a machine with the following characteristics:

The MMU has t TLB entries, the main memory has space for f page frames, and the address space allows p pages, where t < f < p. Each TLB entry has three fields, a valid bit, a page number, and a frame number.

The MMU will request a page fault if no TLB entry contains a valid entry matching the page requested. If two valid TLB entries match, the MMU will behave nondeterministically.

Part A: What data structures are required to implement clock replacement under this hardware? Give as much detail as possible, given only the above information.

To implement clock replacement on this machine, we need:

A page table with p entries: indexed by the page number from the virtual address.; containing, for each page, a valid bit, a state field, a disk address, a frame number and a TLB entry number.; the states of a page are: on-disk, in-frame, in-TLB.
A frame table with f entries: indexed by the frame number.; containing, for each frame, the page number of the page currently in that frame and a mark bit. We assume that every frame initially holds one page, so we never need to consider frames that hold nothing.
The clock hand,: an integer indexing into the frame table
The TLB with t entries,: defined as given in the background, is all hardware so it need not be mentioned here.
The TLB hand,: an integer indexing into the TLB.

Part B:

page_fault_trap_handler()
    get va, the virtual address that caused the trap
    extract p, the page number, from va
    if not page_table[p].valid then
                abort application program!!!
            else if page_table[p].state = on_disk
        -- we have a real page fault!!!

        -- find a page to replace
        clock_hand = clock_hand + 1
        while frame_table[clock_hand].mark = marked
            frame_table[clock_hand].mark = unmarked
            p' = frame_table[clock_hand].page_number
	    if page_table[p'].state = in_TLB
		TLB[page_table[p'].TLB_entry].valid = false
	        page_table[p'].state = in_frame
	    endif
	    -- note, because of above,
	    -- all unmarked pages are not in the TLB!
        endloop

        -- write that page out
        p' = frame_table[clock_hand].page_number
	write p' from frame selected by clock_hand
          to disk, at address page_table[p'].disk_address
	page_table[p'].state = on_disk

        -- read in the page we need
	read p into frame selected by clock_hand
          from disk, at address page_table[p].disk_address
	page_table[p'].state = in_frame
	page_table[p'].frame_number = clock_hand

            else if page_table[p].state = in_frame
        -- we have a TLB soft page fault!!!
	
	-- really stupid TLB replacement algorithm
	-- we should really hunt up an invalid TLB entry
	TLB_hand = TLB_hand + 1
	if TLB[TLB_hand].valid = true then
	    -- evict TLB entry
            page_table[TLB[TLB_hand].page_number].state = in_frame
            TLB[TLB_hand].valid = false
	endif

	-- make valid TLB entry
        TLB[TLB_hand].page_number = p
        TLB[TLB_hand].frame_number = page_table[p].frame_number
        TLB[TLB_hand].valid = true

	-- set the mark bit!
	frame_table[page_table[p].frame_number].mark = marked
    endif
return