CSCI 315 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 8, 9, and 10), many concepts used in these chapters were introduced in earlier chapters. They can't be disassociated completely.
 

1. Identify the following:
   1. object code
   2. linking
   3. loading
   4. dynamic linking
   5. shared library
   6. swapping
   7. backing store
   8. physical address
   9. logical address
   10. contiguous memory allocation
   11. external fragmentation
   12. internal fragmentation
   13. first-fit
   14. best-fit
   15. worst-fit
   16. frame
   17. page
   18. page table
   19. TLB
   20. valid bit
   21. modify bit (dirty bit)
   22. reference bit
   23. virtual memory
   24. demand paging
   25. page replacement algorithms (FIFO, Optimal, LRU and its approximations)
   26. Belady's anomaly
   27. thrashing
   28. working set
   29. file
   30. directory
   31. attributes of a file
   
   
   
   
2. 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.
   
   
3. In the context of a paging system, what is a logical address? What is a physical address?
   
   
4. 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.
   
   
5. 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?
   
   
6. 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.
   
   
7. Give two motivations for going to a virtual memory scheme.
   
   
8. What is the optimal page replacement algorithm? Why isn't it used in practice?
   
   
9. What do we use in practice to approximate the optimal page replacement algorithm?
   
   
10. Given a list of page references (reference string) and a set of frames, figure out page faults for page replace algorithms FIFO, Optimal, LRU.
    
    
11. Given a list of page references (reference string) and a window size, figure out the working set within the given window. NOTE: this is easy, but I will not ask you to do this on the exam. You should know what a working set is and how an OS can use the working set sizes to try to prevent thrashing, but you don't need to know about windows and ways of approximating the working sets.
    
    
12. What are some possible ways of organizing a directory system?
    
    
13. What are the two main types of file access covered in the course text?