Comp111 - Quiz 2 Review 3

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 ________1________ to a process, as well as whether it might be ________2________ 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 ________3________ rather than for each page.
  2. An inverted page map differs from a regular page map because each page address is ________4________ 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 ________5________ 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 ________6________ that owns the page. Without this extra information, the mapper can't tell the difference between pages intended for use by different ________7________.
  3. The inter-arrival time and service time distributions actually have the same ________8________ distribution function but describe different things. The inter-arrival time distribution describes times ________9________ successive events, while the service time distribution describes time required to ________10________ a particular event. If λ represents the rate of arrival of events, and μ represents the rate of processing, then λ/μ represents the ________11________ that the associated queue of events contains 0 elements, while (λ/μ)n(1-(λ/μ)) represents the ________11________ that the queue contains exactly n elements. This is only true if the queueing system achieves steady-state behavior, i.e., λ/μ < ________12________. If it achieves steady-state behavior, the balance equations say that the input and output ________13________ for each particular queue are the same, while the ________14________ for each queue may differ greatly from that of other queues.
  4. In paging systems, the translation lookaside buffer serves as a ________15________ of the translations between ________16________ and physical page addresses. As it is limited in size, its contents are sometimes treated as ________17________ 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 ________18________ rather than choices made by the processes. Unlike individual processes, the pager has a ________19________ view of resource needs over all processes. This means that it can ________20________ 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 ________21________, 1/μ represents the average time it takes to ________22________ a page into physical memory, and c represents the number of ________22________ operations that can occur concurrently. Increasing the amount of physical memory ________23________ λ; this is strongly recommended if ________24________>1.