Comp111 - Quiz 2 Review 3 answers

Dec 8, 2009 - closed book



Please fill in the blanks. Each blank is worth 5 points. There are several reasonable answers for some of the blanks; choose one. Blanks with the same number have the same answer. Extra credit answers count only if errors are made in the regular quiz; in no case will one's score be greater than 100.

  1. Each page in a memory page table has attributes known to the operating system but not necessarily known to the processes that utilize the page. These attributes include whether the page is ____read-only/readable/writeable/etc (I think I should also accept available; if you put this there, then have me regrade it)____ to a process, as well as whether it might be ____shared/associated____ with other processes. These attributes take up a significant amount of space in memory, so that some operating systems define them by specifying them for each ____segment (alas, process is incorrect)____ rather than for each page.
  2. An inverted page map differs from a regular page map because each page address is ____hashed____ into an offset into the page table rather than being interpreted as an offset into the page table. This means that one can often hop directly to the appropriate page map entry, but sometimes one must ____search/scan/skip____ within the page table for an appropriate entry. Each entry of an inverted page map must thus contain the real offset of the page, as well as an identifier of the ____process____ that owns the page. Without this extra information, the mapper can't tell the difference between pages intended for use by different ____processes____.
  3. The inter-arrival time and service time distributions actually have the same ____cumulative/probability (I think I should also accept "exponential")____ distribution function but describe different things. The inter-arrival time distribution describes times ____between____ successive events, while the service time distribution describes time required to ____service/process____ a particular event. If λ represents the rate of arrival of events, and μ represents the rate of processing, then λ/μ represents the ____probability____ that the associated queue of events contains 0 elements, while (λ/μ)n(1-(λ/μ)) represents the ____probability____ that the queue contains exactly n elements. This is only true if the queueing system achieves steady-state behavior, i.e., λ/μ < ____1.0____. If it achieves steady-state behavior, the balance equations say that the input and output ____rates____ for each particular queue are the same, while the ____service times/mean time in system____ for each queue may differ greatly from that of other queues.
  4. In paging systems, the translation lookaside buffer serves as a ____cache/in-memory representation____ of the translations between ____logical____ and physical page addresses. As it is limited in size, its contents are sometimes treated as ____virtual____ memory, and paged in and out just like process pages.
  5. In assignment three, the deadlock detection algorithm often detects deadlock conditions that do not persist. This is because the deadlock is caused by choices made by the ____operating system/pager____ rather than choices made by the processes. Unlike individual processes, the pager has a ____global/overall/comprehensive____ view of resource needs over all processes. This means that it can ____break/undo/avoid____ potential deadlock conditions when they occur, simply by making more informed choices.
  6. (EXTRA CREDIT: can increase score to 100, but not above 100) A virtual memory paging system may be modelled as an M/M/c queueing system, where 1/λ is the average time between page ____faults/misses____, 1/μ represents the average time it takes to ____swap/load____ a page into physical memory, and c represents the number of ____swap/load____ operations that can occur concurrently. Increasing the amount of physical memory ____decreases____ λ; this is strongly recommended if ____λ/μc____>1.