Final Exam Topics

Fall 2005

Exam Date: Wednesday, 14 December, 4:30-7:00PM, Williams 309.

References: Silberschatz chapters 8-11 and sections 13.1, 13.2, and 15.1-15.3. Note that chapters 7, 12, and 14 will not be covered.

Note: This is a closed book exam. You may use the Beginning Linux Programming book if there are no marks in it.

Chapter 8: Memory Management

• Understand the memory heirarchy and especially how cache is used to overcome slow memory and buses.
• Address binding: compile time vs load time vs execution time.
• Code segments, data segments, and stack segments and how they're used for C programs.
• Understand how the relocatable object module, the absolute program, and the final loaded program are created and how addersses are adjusted in each.
• Know how dynamic memory is handled.
• Logical vs Physical address space.
• Swapping.
• Fixed-partition allocation strategies, variable-partition allocation strategies and dynamic allocation strategies. Best fit, worst fit, first fit.
• Know how dynamic address binding is done (relocation registers, hardware dynamic relocation, runtime bounds checking, etc.) for paging and segmentation.
• Holes and External and internal fragmentation.

• Paging. How addresses are broken into page numbers and offsets.
• Paging. Be able to translate logical addresses into physcial addresses using page tables.
• Paging. Be able to explain how pageing is implemented using TLBs, PTBR, etc.
• Paging. Know what associative memory is and how it can be used to speed up paging.
• Paging. Be able to do Effective Access Time calculations.
• Paging. Be able to create/use multi-level paging examples.
• Page tables. Hardware support of paging.
• Protection. Valid bits.
• Paging. Be able to evaluate page performance.
• Paging. Know what inverted page tables are and how they're used.
• Shared pages.
• Know how Linux implements virtual memory (including the number of bits used for different tables in an i386 system).
• Segmentation. Know how segmentation works and how it is implemented.
• Segmentation. Method. Hardware support. Protection and sharing. Fragmentation. Know how the user can use segments.
• Segmentation. Be able to translate logical addresses to physical addresses in segmentation systems.
• Multics. Be able to explain how the MULTICS paging/segmentation system works.

Chapter 9: Virtual Memory

• Virtual memory. What it is, how it works, locality.
• Address translation; how to go from a virtual address to a physical address. Be able to figure out the number of bits allocated to various parts of an address given a page size.
• Demand paging. Method. Hardware support.
• Performance. Effective access time. Steps in swapping and how they affect performance.
• Page replacement. General method. Valid/invalid and dirty bits, page faults.
• Be able to calculate EAT with paging.
• Page replacement algorithms.
• FIFO.
• Belady's anonaly and why it works (stack algorithms).
• Optimal.
• LRU.
• LRU approximation algorithms (additional-reference bits, second-chance, enhanced second-chance, counters, etc.).
• The various clock algorithms.
• Least Frequently Used/Most Frequently Used algms.

• Page size considerations.
• Effect of program structure on page fault rate. Thrashing.
• Frame allocation algorithms (fixed, priority, etc.).
• Working set algorithm. Be able to describe this algorithm, talk about implementations of the algorithm, describe its strengths and weaknesses, etc.
• Know the various implementations of the Working set algorithm.
• Allocating kernel memory (buddy system, slab allocation).
• Other issues: pre-paging, page size, TLB reach, program structure, I/O interlock.

Chapter 10: File Systems

• Understand the file manager's job: translating stream-block into byte streams, record-streams, or structured record files.
• Directory structures (heirarchtical, acyclic-graph, general graph).
• File system mounting.
• Know how file-sharing is done both locally and remotely.
• Know about failure modes and consistency semantics.

Chapter 11: File System implementation

• Know what file control blocks are and how they're used.
• Know block allocation methods: contiguous, linked (and FAT), indexed. Be able to explain the DOS FAT file system and the Linux file structure.
• Free-space management. Bit vectors, linked lists, grouping.
• Directory implementation.
• Be able to talk about efficiency and performance of disks, page caches, unified caches, etc.
• Know what log structured (journaled) file systems are in general. You do not have to know how NFS works.

Chapter 13: I/O Systems

• Know what device controllers and bus controllers are and how they interact.
• Know what polling and interrupts are and how they each work and how they are different.
• Know how a IO manager communicates with devices via the bus controller.
• Know what race conditions are and how they occur.
• Be able to describe DMA.

Chapter 14: Protection and Security

• Know the categories and methods of security violations.
• Know the 4 levels of security.
• Know the different types of security threats described in class including Trojan Horse (and its variations), trap doors, logic bombs and stack overflows.
• Be able to describe in detail how stack overflows can be used to gain access to a computer.
• Be able to describe in detail how the Morris worm worked and why it was so effective.
• Be able to describe the different types of virii and how they work, especially macro viruses. Know the different categories of virii described in class.
• Be able to describe network and system threats such as worms, port scanning, and DOS.

Last updated on 08 Dec 2005 by John Barr