Midterm 2 Study Guide (Section 01)

Administrivia

  • The exam is designed to be completed in 1 hour.
  • The exam will be open book and “take home” in the sense that you will download if from Moodle, work on it, and upload your solutions. There will be a time limit of 3 hours from the moment of download to the moment you upload and there will be a deadline by which to complete the entire process (the details will be on Moodle). If you run into any issues with the time limit for submission, don’t stress – just get in touch with me as soon as possible.
  • The exam is individual. There will not be anyone looking over your shoulder, but you are expected to be ethical and to abide by the principles of academic honesty.

Study Recommendations

  • Review all assigned readings from the textbook since the last exam (be mindful of the chapter reading guides for SGG 8, 9, and 10).
  • Go through labs, quizzes, and in-class activities. Make sure that you have a solid understanding of the topics they address. The concepts in C systems programming from lab are important to review, but you don’t need to stress about matters of syntax.
  • This document doesn’t mean to give an exhaustive coverage of what might appear in the exam, but it will be useful as a self-check list for your preparation.

Review Guide

  1. Identify the following concepts:
    • multiprogramming
    • process, process control block (PCB)
    • thread
    • context switch
    • scheduling
    • memory protection
    • starvation
    • mutual exclusion
    • atomicity
    • deadlock prevention, deadlock avoidance, deadlock recovery
    • resource allocation graph; wait-for graph
    • Banker’s algorithm for state safety and for resource requests
    • first-fit, best-fit, worst-fit policies for contiguous memory allocation
    • internal fragmentation, external fragmentation
    • segmentation, segment table, segment table base register, segment table length register
    • swapping
    • demand paging
    • page, frame, page table, page table base register, page table length register, valid bit, dirty bit
    • translation lookaside buffer (TLB)
    • physical address, logical address
    • virtual memory
    • page replacement algorithms: FIFO, OPT, LRU, LFU, MFU, second chance
    • Belady’s anomaly, stack algorithms for page replacement
    • working set, thrashing
    • memory mapped file
    • frame allocation policies (global vs. local, fixed vs. priority)
    • effective access time (for RAM, for paging with and without TLB, for virtual memory with and without TLB
  2. What are the necessary conditions for a deadlock to occur?
  3. Given a set of processes, resources, and resource requests, draw the resource allocation graph after each request and state whether or not a deadlock is possible.
  4. In general, a cycle in a resource allocation graph indicates only the possibility of a deadlock. Under what special condition does it indicate the existence of a deadlock?
  5. What are the different ways of dealing with deadlock?
  6. How does the safety version of the Banker’s algorithm work? You should be able to carry out a hand execution of the algorithm.
  7. In contiguous memory allocation schemes, it is possible to use first-fit, best-fit, and worst-fit strategies. State a justification for each of these strategies. When might one of these strategies work better another?
  8. Identify the circumstances in which internal fragmentation and external fragmentation happen. 
  9. What would it take for a system with contiguous memory allocation to minimize external fragmentation? Would the solutions you propose have benefits that outweigh their implementation and operational costs?
  10. What are the advantages and disadvantages of memory management schemes such as swapping and virtual memory? What is the impact that each of these schemes have on the usability of the system (from a programmer’s perspective) and on the implementation of the system?
  11. How can a system guarantee that executable program will be able to run anywhere in RAM memory?
  12. In the context of a paging system, what is a logical address? What is a physical address?
  13. Describe the purpose that aTranslation Lookaside Buffer (TLB) serves, what data it contains, and what it does for a paging system.
  14. Describe the impact that the use of a TLB can have on the effective access time of a virtual memory system.
  15. Explain how a logical address is converted to a physical address in a paging system that includes a TLB.
  16. What happens to the size of page tables as we decrease page sizes? What should be done in a system where a page table does not fit within a single page?
  17. Consider a paging system where logical addresses have 20 bits and pages sizes are 4,096 bytes. How many bits of the logical address are needed to identify a page?
  18. In a paging system with a TLB, consider the metrics below and calculate the memory system effective access time:
    • The memory access time is 150 nsec.
    • The TLB access time is 25 nsec.
    • The TLB hit rate is 80%.
  19. What are the motivations for using virtual memory in a computer system?
  20. Identify the steps the OS takes in handling a page fault in a virtual memory system.
  21. Describe how it is possible that one frame of physical memory can belong to the logical address space of multiple different processes.
  22. Construct a scenario that justifies pre-loading all the pages of a process than to allow pages to be loaded on demand.
  23. Describes the advantages and disadvantages of fixed and priority frame allocation in a virtual memory system.
  24. Describe the advantages and disadvantages of global and local page replacement in a virtual memory system.
  25. Describe how one might identify that the system is in thrashing, what may have caused it, and give  strategies to avoid or to stop it.
  26. Describe the concept of working set and how it relates to thrashing.
  27. Given a sequence of logical address references, identify which references causes page hits and page faults according to the following page replacement algorithms: OPT, FIFO, LRU, second chance.
  28. Compare different strategies to implement and to approximate LRU page replacement.
  29. Describe the purpose and the operation of second hand page replacement, identifying what hardware support it may need.
  30. Describe the concept of working set for processes executed in a virtual memory system.
  31. Explore the advantages and disadvantages of local and global strategies for frame allocation.
Print Friendly, PDF & Email