# Guattery Section Exam 2 Review

The questions for exam 2 will be taken from/similar to/based on the following, and on the homework and lab exercises you’ve been assigned. While the emphasis of the exam will be on the materials since last test (Chapters 6, 7, 8, and 9), many concepts used in these chapters were introduced in earlier chapters. They can’t be disassociated completely.

1. Identify the following:
• resource allocation graph
• shared library
• swapping
• backing store
• contiguous memory allocation
• external fragmentation
• internal fragmentation
• first-fit
• best-fit
• worst-fit
• frame
• page
• page table
• TLB
• valid bit
• modify bit (dirty bit)
• reference bit
• segmentation
• virtual memory
• demand paging
• page replacement algorithms (FIFO, Optimal, LRU and its approximations)
• thrashing
• working set
2. Explain each of the following CPU scheduling algorithms. Which can be preemptive?
• first come, first served
• shortest job first
• round robin
• priority
• multilevel queue
3.  What are the various criteria we use to study the performance of a CPU scheduling algorithm?
4. How do we estimate the length of next CPU burst?
5. What are the four necessary conditions for a deadlock to occur?
6. 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.
7. 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?
8. What are the different ways of dealing with deadlock?
9. How does the Banker’s algorithm work? You should be able to carry out a hand execution of the algorithm.
10. What is a major drawback of using swapping? How does this affect the choice of time quantum?
11. 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. Is there one that works better or worse than the others? Explain your answer.
12. Compare paging and segmentation schemes with respect to internal and external fragmentation.
13. In the context of a paging system, what is a logical address? What is a physical address?
14. Explain how a physical address is determined in a paged system with a TLB. Be specific about what the values are and how they are used.
15. Consider a paged system where addresses are byte addresses, and pages consist of 16 4-byte words. If the desired page is in frame 5, and the offset is byte 4 in the frame, what is the corresponding physical address?
16. In a system with a TLB, assume the following:
• the memory access time is 150 nsec.
• the TLB access time is 25 nsec.
• the TLB hit rate is 80%.

Write a formula for computing the effective access time using these numbers.

17. What does the logical address in a segmented system consist of? How is a physical address computed? Be specific about all calculations and comparisons.
18. Explain a protection scheme that allows pages to be shared by multiple programs.
19. Give two motivations for going to a virtual memory scheme.
20. What is the optimal page replacement algorithm? Why isn’t it used in practice?
21. What do we use in practice to approximate the optimal page replacement algorithm?
22. Given a list of page references (reference string) and a set of frames, figure out page faults for page replace algorithms FIFO, Optimal, LRU.
23. Given a list of page references (reference string) and a window size, figure out the working set within the given window.