Assignment 4, Solutions

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.)

Consider the problems you would face in writing a 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.

The Problem: How could you use the select() Unix kernel call in implementing this? How could you use the O_NONBLOCK option for the open() kernel call to implement this. This question asks you to research these and describe their use in this context. Next week, you will have to actually solve the problem with one or the other of these. (See the unix man pages for documentation of these services!)

Here is a nonblocking read from standard input coded with select(); this reads a character into ch only if one is available, and it never blocks, except in the case where another process is competing to read characters from standard input.

                FD_ZERO( &stdinset );
                FD_SET( 0, &stdinset );
                ret = select( 1, &stdinset, NULL, NULL, NULL );
                if (ret == 1) read(0,&ch,1);

Here is a nonblocking read that assumes that the file was opened with the O_NONBLOCK option or that this option was set using the fcntl(0,F_SETFL,...) call.

                ret = read(0,&ch,1);

These two both set ret to 1 when they successfully read a character into ch; although they do it in very different ways. Ignoring the possibility of errors (improperly opened file, end of file, etc), we can therefore embed both of these in a loop that relinquishes to the thread scheduler each time the nonblocking read fails to get a character; the loop should terminate when the read is successful.

It is worth noting that there is no need to call thread_relinquish() if the thread doing the read is the only ready thread! In that case, a normal blocking read is appropriate. Dealing properly with this special case takes a bit of thought.

http://homepage.cs.uiowa.edu/~dwjones/arch/hawk/overview.html#tma
http://homepage.cs.uiowa.edu/~dwjones/arch/hawk/overview.html#mmudata
http://homepage.cs.uiowa.edu/~dwjones/arch/hawk/overview.html#mmu

Part A: What page replacement policies are feasible on this machine. To solve this problem, you will have to figure out what hardware support this MMU offers for page replacement policy and then list the policies (or classes of policies) that remain feasible with this support.

The Hawk MMU does not record anything like the time of last reference to a page, so it cannot support LRU replacement.

It does not record anything like a mark or dirty bit, so it cannot support clock replacement.

The Hawk MMU does allow a page to be marked as inaccessible even when it is actually in main memory. This allows a soft page fault to be used to set the mark bit, allowing support of the modified clock algorithm.

The Hawk MMU does allow a page to be marked as read-only in the MMU even though fields of the page table understood only by software say it ought to be read-write. This allows us to use a soft page-fault to detect dirtying of a clean page, so we can do modified clock replacement augmented with page cleaning as the clock hand sweeps by dirty pages.

In addition to those sophisticated page replacement policies, we can do random replacement.

Part B: Hard page faults on this machine would most likely involve transfer of pages between the CPU and disk. What kind or kinds of soft page faults would the page-fault service routine on this machine need to handle.

As indicated above, unmarked pages in main memory would have the hardware fields of their page table entries set to no-acccess, so a soft page fault could be used to mark pages on their first use after the mark is reset.

In addition, also as indicated above, clean read-write pages in main memory would have the hardware fields of their page table entries set to read-only, so a soft page fault could be used to set the dirty bit on the first write to a page after cleaning.

Finally, the Hawk TLB is designed so the software has complete control of when new virtual-physical associations are loaded in the TLB. There is no indication in the manual of any hardware that automatically loads the TLB from the page table, so this must also be done by soft page faults.

Part C: What is the format of a page-table entry on this machine, where should the page table be stored, and does the MMU dictate any scheme for segmenting the page table?

Each hawk page table entry will have the following format (borrowed verbatim from the MMU description):

         _______________________________________ _______________________
        |_______________________________________|/////////////|_|_|_|_|_|
        |31                                   12|11          5|4       0|
                      physical page                 unused     C R W X V
                         number                 (soft fields?) (rights!)

MMU data register values are computed from page table entries found in main memory during soft page faults caused by TLB misses in the MMU. Nothing in the hardware dictates how the page table is segmented.

Generally, whether the hardware does TLB replacement or whether this is left to software, and whether the page table is a one-level or a two-level paged-segmented structure, the TLB always does a one-level lookup to translate directly from virtual addresses to physical addresses.