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: 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?