Homework 3 Solutions

22C:116, Spring 1997

Problem 1 Part A

The page frame table will also contain:
    - the access bits : Accesssibile, Read-only, Read-write
      We need to keep a copy of the real access bits here, because we
      are going to manipulate the access bits from TLB in order to
      get a page fault in the cases we have to update the Mark and
      Dirty bits from the page frame table.
    - the Mark bit ( tells whether a page was accessed or not)
    - The Dirty bit( tells whether a page was written to or not)

Problem 1 Part B

    Page_fault_service_routine:

	if reference is to page not in TLB
	    if referenced page is in main memory
		bring the entry for page in TLB
                set access as Read-only(in TLB)
                set Mark bit to 1(in page table)
	    else
                select a victim page
                if page is dirty issue a write to disk & update TLB and map
                issue a read for desired page
                update TLB and map
                set access as Read-only(in TLB)
                set Mark bit to 1(in page table)
	else
            if Read-only bit in TLB and attempt to write
                if Read-write bit in page table
                    set Dirty bit to 1 (in page table)
                    set Read-write access(in TLB)
                else
                    Real access violation
            else    /* page marked as inaccessable in TLB */
                if accessible according to page table
                    set Mark bit to 1 (in page table)
                    set Read-only access(in TLB)
                else
                    Real access violation



Problem 2 Part A

    page_fault_service_routine:

        if reference is to page not in TLB
            if referenced page is in main memory
                soft page fault for TLB update
            else
                tell scheduler the calling process is blocked
                select page to replace
                update TLB & map for that victim page /or mark page as invalid/
                if page is dirty
                    enqueue a disk I/O request to write the page on disk
                enqueue an disk I/O request to read the desired page
		return to some ready process
        else
            handle access violation


    disk_interrupt_service_routine

	if recently completed I/O request was read after page fault
	    update TLB and map
	    tell scheduler the blocked process is now ready
	else
	    process as a normal I/O completion
	endif
	begin next disk I/O operation
	return from interrupt

Problem 2 Part B

    When a page fault is being serviced and another page fault for
    the same page appears there is no point in servicing it again.
    It is a lost of time, and it leads to having two copies of the
    same page in memory.  That is not only a waste of resources but
    may lead to inconsistancy problems for that page.

    When another fault for a different page interferes care should
    be taken for the global system variables involved ( like faulting
    process ID, page adresses) to remain consistent. Also if the two
    faults are simultaneous may be important in wich order they are
    served.

    These may be solved using a carefully mantained queue of requests,
    which takes into account the type of request(read or write) and
    for what page the request was.


Problem 3

    A scenario in which an infinite recursion can appear would be like
    this:

        A process faults for page A. The page fault routine faults
        itself for the page-table page containing information about
        page A. Then this page-table page is brought in the memory.
        The first call can precede now. Suppose it selects as victim
        page the newly brought page-table page, in order to bring in
        the desired page that originaly faulted. Since now the page
        needed is in the main memory we need to update the
        corresponding page table entry.  But this is not in memory
        anymore, and a fault occurs again.

    Of course if the replacement algorithm doesn't permit this ( to
    swap out a recently bruoght in page) this cannot happen. But in
    order to ensure this we can designate a zone of the main memory
    for page tables only.

    Of course, if a page table is too large and it cannot fit entirely
    in the main memory we are dealing with the pagination of the page
    table itself and we have a number of layers of page-tables. Through
    those the recursion can not be more than the number of layers if
    it is not the case described above.