/* following only needed for getpid() call used for srandom() */ #include/* following only needed for random() and srandom() */ #include /* following needed for most of program */ #include #include "threads.h" /*******************************/ /* Simulated Random Preemption */ /*******************************/ void may_relinquish() /* call this to randomly do context switching */ { if (random() & 3) thread_relinquish(); } /**********************/ /* FIFO Queue package */ /**********************/ #define size 5 struct thread_semaphore data, space; int head, tail; char qdata[size]; void initqueue() { thread_semaphore_init( &data, 0 ); thread_semaphore_init( &space, size ); head = 0; tail = 0; } void enqueue( int c ) { thread_wait( &space ); may_relinquish(); qdata[tail] = c; tail++; if (tail >= size) tail = 0; may_relinquish(); thread_signal( &data ); } int dequeue() { int c; thread_wait( &data ); may_relinquish(); c = qdata[head]; head++; if (head >= size) head = 0; may_relinquish(); thread_signal( &space ); return c; } /*******************/ /* The Application */ /*******************/ void producer( int n ) { int i; for (i = 1; i <= 10; i++) { enqueue(n); } } int dequeue_count; void consumer( int n ) { int i,j; do { (void) dequeue(); dequeue_count++; } while (dequeue_count != 30); puts( "done!" ); } int main() { srandom( (unsigned) getpid() ); /* randomize the random numbers */ thread_manager_init(); thread_startup_report(); initqueue(); dequeue_count = 0; thread_launch( 4000, producer, 'a' ); thread_launch( 4000, producer, 'b' ); thread_launch( 4000, producer, 'c' ); thread_launch( 4000, consumer, '1' ); thread_launch( 4000, consumer, '2' ); thread_manager_start(); }
Part B: After this program outputs the message `done' to say that the 30th item has been dequeued, the tread manager terminates the entire program; it does so with a normal termination message, but it leaves one of the producers hanging awaiting an item from the queue that will never arrive. It would take an extraordinary effort to make both consumers terminate cleanly when the final item went through the queue.
Page Table Structure
_______________________________________________________________
|_______________________________________|/////////////|_|_|_|_|_| 0
|_______________________________________|/////////////|_|_|_|_|_| 1
|_______________________________________|/////////////|_|_|_|_|_| 2
...
_______________________________________________________________
|_______________________________________|/////|_|_|_|0|_|_|_|_|_| n
|31 12|11 | |5|4 0|
physical page unused R'W'X' C R W X V
(frame) number
In the above, the C, R, W, X and V fields are defined identically to
the corresponding fields in the MMU data register. The G field is not
used, and the corresponding bit in the page-table entry is always zero!
The R' and W' bits are used to support soft page faults.
In a page table entry, if the V bit is zero, the page is invalid or on disk. It is invalid if the R'W'X' field is zero, indicating that the page can never be used. The R'W'X' bits have exactly the same meaning as the RWX bits, but are interpreted only by software. These bits differ in the event that soft page faults are being used to mark or dirty pages.
The frame table, indexed by frame number, can have entries that mirror the trap-memory-address register:
Frame Table Structure
_______________________________________________________________
|_______________________________________|/////////////////////|_| 0
|_______________________________________|/////////////////////|_| 1
|_______________________________________|/////////////////////|_| 2
...
_______________________________________________________________
|_______________________________________|/////////////////////|_| n
|31 12|11 | |
| page V|
page
If the V bit in a frame-table entry is 0, the page field is nonsense.
Part B Here is high level pseudocode for a page-fault trap service routine on the Hawk machine:
page fault service routine:
temp = trap memory address register
cause = temp & 3
page = temp >> 12
entry = page_table[page]
select cause in
case 0: -- invalid TLB entry
if entry.V then -- page table entry is valid, soft fault
mmu_data_register = entry
else -- page is actually invalid
if entry.R'W'X' = 000 then -- page should never be used
user's saved PC = user's bus-trap handler address
-- above code forces bus trap for user!
else -- it is a normal page fault
.
. -- code for normal page fault handling
.
endif
endif
case 1: -- fetch from non-code page
if entry.X' = 0 then -- genuinely not executable
user's saved PC = user's bus-trap handler address
-- above code forces bus trap for user!
else -- soft page fault to mark page
entry.X = 1
mmu_data_register = entry
endif
case 2: -- store on non-writable page
if entry.W' = 0 then -- genuinely not writable
user's saved PC = user's bus-trap handler address
-- above code forces bus trap for user!
else -- soft page fault to mark page
entry.W = 1
mmu_data_register = entry
endif
case 3: -- read from non-readable page
if entry.R' = 0 then -- genuinely not readable
user's saved PC = user's bus-trap handler address
-- above code forces bus trap for user!
else -- soft page fault to mark page
entry.R = 1
mmu_data_register = entry
endif
endselect
return
In the page-fault handling code omitted above, we assume some kind of clock
algorithm will be used. In the code for clock replacement, the following
functions (or macros) can be used:
is_marked( frame )
if frame_table[frame].V then -- this frame holds some page
entry = page_table[frame_table[frame].page]
if entry.RWX = 000 then
return false
else
return true
endif
else
return false
endif
unmark( frame )
if frame_table[frame].V then -- this frame holds some page
entry = page_table[frame_table[frame].page]
entry.RWX = 000
trap_memory_address_register = frame_table[frame]
MMU_data_register = 0 -- invalidate TLB entry
-- if page is needed, a soft page fault will update the TLB
endif
is_dirty( frame )
if frame_table[frame].V then -- this frame holds some page
entry = page_table[frame_table[frame].page]
if entry.W = 0 then
return false
else
return true
endif
else
return false
endif
mark_clean( frame )
if frame_table[frame].V then -- this frame holds some page
entry = page_table[frame_table[frame].page]
entry.W = 0
trap_memory_address_register = frame_table[frame]
MMU_data_register = 0 -- invalidate TLB entry
-- if page is needed, a soft page fault will update the TLB
endif
Load word 6144 into register 0 Fetch from 1020 Push Register 0 onto stack (this is the actual parameter) Fetch from 1024 Store to 8192 Call procedure at 5120 Fetch from 1028 Store to 8188 Subtract 16 from SP (this is in the called procedure) Fetch from 5120 Compare actual parameter Fetch from 5124 Load from 8192 Jump if equal to 5152 Fetch from 5128In the above, I have assumed, rather arbitrarily, that instructions and operands are 32 bits each, and that immediate operands are embedded in the instruction word and not stored in successive addresses after the instruction.