Part A: Give definitions for the functions needed to break a virtual address into the component fields relevant to this problem and to construct a virtual address from these component fields.
Let's assume that somethinbg like the following masks are available:wordfieldbits = 8 wordfieldmask = ... 0000000011111111 = (1 << wordfieldbits) - 1 pagefieldmask = ... 1111111100000000 = ~ wordfield = (-wordfield) - 1These are given in binary above, and we have assumed, arbitrarily, for the sake of example, that there are 256 words per page.wordfield(va) = va & wordfieldmask pagefield(va) = va >> wordfieldbits makeva( word, page ) = (page << wordfieldbits) | word
Part B: What is the best choice of page replacement policy for this system? LRU would be nice, but the system services you have available do not give sufficient information for that.
We cannot do LRU because we have no accounting method to measure the time of use of a page. We cannot do clock replacement because we have no way to invalidate a page while leaving it in memory. We can, however, use soft page faults to detect attempts to modify a page, and this allows us to schedule pages for cleaning.If a page holds read-only data or pure code, the resulting policy will be effectively random, or at least, no better than random. We can, however, gain the advantage of a software clock policy for pages of read-write data.
In sum, we can't use any really good policy, but we won't be quite as bad as random.
Part C: Give a detailed description of any data structures your code must maintain. These would be initialized by make-virtual, if you bothered to write the code for it (you are not to do so).
We need an array to serve as a software page-table for the range of pages between va1 and va2 inclusive:firstpage = pagefield(va1) lastpage = pagefield(va2) numpages = (lastpage - firstpage) + 1 clockhand = 0 (initially) -- this is really clumsy! we're using the page table -- as a frame table, so there are lots of table entries -- we have to skip before we find one that's relevant. pagetablentry pagetable[numpages]Each page table entry will have the following fieldsrightsIn this table, the rights are read_only, read_write, and unmapped, and they tell the state of the page. Note that all pages in the mapped range are logically read write pages of the open file fd. Therefore, we can conclude the following:rights = unmapped -- the page is in sector pagefield(va) - firstpage of the file rights = read-only -- the page is in main memory and is clean rights = read-write -- the page is in main memory and is dirty
Part D: Give detailed pseudocode for your user-level page fault handler; it should use the data structures you outlined, and it should implement the policy you selected.
faulthandler:
if savarea.cause not one of addr_fault or access_fault,
this is not a page fault,
do other things not related to this assignment
else
page = pagefield(savearea.va)
if page < firstpage or page > lastpage
this is outside the scope of this assignment
else
sector = page - firstpage
if pagetable[sector].rights = read_only
-- soft page fault
note savearea.cause should be access_fault!
pagetable[sector].rights = read_write
map(savearea.va, read-write)
return_trap(savearea)
else
-- real page fault
note pagetable[sector].rights should be unmapped!
note savearea.cause should be addr_fault!
while map(va,read_write) = false
-- really clumsy clocklike replacement
while pagetable[clockhand].rights = unmapped
clockhand = (clockhand + 1) mod numpages
-- because we're using the page table, we have
-- to skip lots of unmapped table entries
if pagetable[clockhand].rights = read_write
-- clean a page
pagetoclean = makeva(clockhand + firstpage), 0)
write pagetoclean to sector clockhand of file fd
map(pagetoclean, read_only)
pagetable[clockhand].rights = read_only
clockhand = (clockhand + 1) mod numpages
else
-- return a clean page to the system
unmap(makeva(clockhand + firstpage),0))
pagetable[clockhand].rights = unmapped
clockhand = (clockhand + 1) mod numpages
endif
endloop
-- we finally mapped the required virtual address
read makeva(page, 0) from sector of file fd
map(savearea.va,read_only)
pagetable[sector].rights = read_only
-- it's now a clean page
return_trap(savearea)
endif
endif
endif
Part E: Given the code you wrote, and given that there are multiple processes running the same code competing for a fixed pool of page frames in main memory, does your code allow processes to share in a controlled manner or does it allow a process to take and keep an unfair fraction of the page frames even though it has a much smaller working set. If the former, how, if the latter, what prevents fair sharing of page frames?
The example code given as an answer to part D returns page frames to the system when it needs a new page frame. As a result, if other processes are waiting for page frames, the returned page frames have a chance of being given to those processes. Because of this, page frames may indeed be assigned to one process at one time and to another process at another time.However, the only time a process gives up page frames is when it needs a frame itself. As a result, if a process gets an unfair number of page frames and then has no more page faults, there is no way for the system to get some of those frames and give them to other processes. Therefore, although this solution does allow some sharing of page frames between processes, it cannot be characterized as fair, merely interesting.