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: Explain any difference in performance you would expect between the above solution to the dining philosopher's problem and the solution in Figure 2.20 of the text. Would one solution sometimes allow two philosophers to dine in parallel when the other forces one or the other to wait?
Part B: Consider the following implementation of the think() operation for use under our example thread package:
void think()
{
int i;
do {
thread_relinquish();
while (random() & 7);
}
Using this version of relinquish (with appropriate initialization of the
random number generator), and using thread_semaphore objects to implement
the synchronization required for forks and salt shakers, implement the above
solution to the dining philosopher's problem under our thread manager.
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.
Part B: Give pseudocode, in terms of the above, for the page fault trap handler. This should use all of the detail about data structures from part A, and it should implement clock replacement.