Comp111 - Operating Systems

Quiz 2 - Nov 27, 2012 - closed book



Please fill in the blanks. Each blank is worth 5 points. Blanks with the same number have the same answer.

  1. The word ____page____ has several incompatible meanings in Operating Systems. In one sense, it refers to how ____virtual/process____ memory is managed. In another sense, it refers to how disk files are ____read/written____.
  2. A processing unit is in balance if its input rate equals its ____output rate____. In this case, ____Little's____ Law says that L = λW, where L is the ____jobs in system____, λ is the ____arrival rate______, and W is the ____waiting time/time in system____.
  3. A scheduler is fair if every process in the run queue receives the same ____amount of time____. "Completely fair scheduling" tries to insure this by storing the run queue as a red-black tree of processes whose search key is the ____time____ for which the process has executed so far. At each scheduling step, the process with the ____least/leftmost____ key is executed, and then moved to where it then belongs in the tree.
  4. Inside an operating system, most structures are ____arrays____. Dense ones are sometimes ____cached____, while sparse ones are sometimes ____hashed____.
  5. A page of memory in a process maps to a ____frame____ of memory in the operating system.
  6. The function malloc allocates one ____page/frame____ of memory at a time from the operating system, and then packages it for your use. On average, a call to malloc returns ____more____ memory than you requested. The justification for this apparent waste is that as a result, malloc and free can run in ____constant/O(1)____ time.
  7. A disk file is identified via a(n) ____inode____ that describes access privileges and where its contents are, but does not contain its ____name____, which is instead contained in the directory in which the file resides.
  8. (Extra credit) A translation lookaside buffer looks superficially like a hash table, but actually functions as a ____cache____ of recently looked-up addresses.