Here is a general outline of the key concepts (arranged by topic) that you should know for the Final.

The exam will have the following format:

1. Definitions: Identify the term described the sentence or phrase.

2. Long Answers:

   • Virtualization

     • Big Picture

     • Memory

   • Concurrency

     • Big Picture

     • Processes vs Threads

     • Synchronization

   • Persistence

     • Big Picture

     • File System

The exam is completely offline. This means there will not be any need for a computer. Furthermore, the test is closed book, closed notes, but open mind.

Furthermore, the exam is also comprehensive. This means there may be questions from the first part of the semester as well. Refer to the Midterm Checklist for possible topics and questions.

Terms

• Virtualization
• Concurrency
• Persistence
• Address Space
• Stack
• Heap
• Address Translation
• Base and Bounds
• Segmentation Fault
• Buffer Overflow
• Uninitialized Read
• Memory Leak
• Dangling Pointer
• Double Free
• Invalid Free
• MMU
• External Fragmentation
• Internal Fragmentation
• Splitting
• Coalescing
• Free List
• First Fit
• Next Fit
• Best Fit
• Worst Fit
• Segregated Lists
• Segmentation
• Code Sharing
• Paging
• Pages
• Page Frame
• Page Table
• TLB
• Valid Bits
• Trap Handler
• Spatial Locality
• Temporal Locality
• Multi-Level Page Table
• Page Directory
• Swapping
• Memory Hierarchy
• Swap Space
• Page Fault
• Eviction
• LRU
• Clock
• Thrashing
• Copy-on-Write
• PIO
• Interrupt
• DMA
• Track
• Disk Head
• Disk Arm
• Rotational Delay
• Seek Time
• Settling Time
• SSD
• Garbage
• Wear Leveling
• RAID
• Striping
• Mirroring
• Parity
• Fail-Stop
• Disk Corruption
• Superblock
• Inode Table
• Inode Bitmap
• Data Bitmap
• Data Block
• Inode
• Dentry
• Extents
• File Allocation Table
• Direct Pointer
• Indirect Pointer
• Buffer Cache
• FFS
• LFS
• Block Groups
• Inode Map
• Checkpoint Region
• Crash Consistency
• Data Integrity
• Checksum
• Atomicity
• Free Blocks
• Bad Blocks
• FSCK
• Data Journaling
• Metadata Journaling

Memory

Address Spaces

1. What is an address space?

2. What is virtual memory?

3. How do we allocate memory?

4. What are some common memory errors?

Free-Space Management

1. Who needs to keep track of memory?

2. What data structures do we use to keep track of memory?

3. What are some strategies for managing memory?

Segmentation

1. What are the problems with base and bounds?

2. How does segmentation address these problems?

3. How do we translate a virtual address to a physical address?

Paging

1. How does paging address the problems in segmentation?

2. What exactly is a page? page frame? page table?

3. How do we translate a virtual address to a physical address?

TLB, Multi-Level Page Tables

1. What problem do TLBs address and how do they solve it?

2. What problem do multi-level page tables address and how do they solve it?

Swapping

1. How does the operating system provide the illusion of infinite virtual memory?

2. How does the operating system handle page faults?

3. What exactly is thrashing?

Filesystems

I/O Devices

1. What is the challenge of persistence?

2. How does the operating system mediate data transfers between the CPU and disk storage?

3. What are the advantages and disadvantages of hard disks versus solid state drives?

RAID

1. What problems does RAID address?

2. What different types of RAID are there and what are the advantages and disadvantages of each?

File Systems

1. How is a typical Unix file system organized?

2. What exactly is an inode?

3. How are blocks allocated?

4. Why does the OS use up all your RAM?

FFS, LFS

1. What problem does FFS solve and how does it solve it?

2. What problem does LFS solve and how does it solve it?

Consistency and Integrity

1. What is the problem of crash consistency and how do file systems deal with it?

2. What is the problem of data integrity and how do file systems deal with it?

Sample Questions

1. What are the three tenets of the Unix Philosophy themes or principles of operating systems?

   • What operating system abstractions demonstrate these themes?

   • What impact does the hardware have on these themes?

2. Given a virtual memory system with the following properties:

   • 14-bit Virtual Address
   • 16-bit Physical Address
   • 64 byte Pages

   • 4 bytes per PTE and PDE

   Sketch all the data structures needed to support a multi-level paged virtual memory system by filling in the table below.  When appropriate, write the solution as a power of 2 and simplify it terms of K, M, G, or T units.

   Pages
   Number of addressable bytes
   Number of pages in address space
   Number of VPN bits in virtual address
   Number of offset bits in virtual address

   Page Table
   Number of PTES
   Number of bytes for just page table
   Number of pages for just page table

   Page Table
   Number of PDEs
   Number of PDI bits in VPN
   Number of PTI bits in VPN
   Number of bytes for just page directory
   Number of pages for just page directory

   Should this multiple level page table have an additional level? Yes No

3. For each of the following assertions regarding concurrency, determine whether or not the statement it is true or false. Provide either evidence of the assertion's correctness or a counter-example to disprove it.

   • Context switches are more expensive than normal function calls.

   • Semaphores can be used in place of mutexes but not condition variables.

   • Deadlock only requires circular dependency and mutual exclusion.

   • Each thread in a process has its own individual stack space.

4. Suppose you worked at a pharmacy and had to gather and dispense requested pills to customers. Rather than gather the pills for each customer yourself, you decide to delegate the work of gathering the pills and dispensing them to customers to other workers (ie. you just dispatch the work to your subordinates).

   • Describe using a diagram, pseudo-code, or prose, how you would simulate the scenario above using processes (each subordinate is a process).

   • Describe using a diagram, pseudo-code, or prose, how you would simulate the scenario above using threads (each subordinate is a thread).

5. The CSE makerspace allows students to do projects with Arduinos and Raspberry Pis... but only has a limited about of capacity:

   • Up to 4 projects can be done in the makerspace at once.

   Model this synchronization problem using POSIX threads, mutexes, condition variables, or semaphores.   Assume each project group is represented by a thread that calls their corresponding enter and leave functions whenever they enter or leave the makerspace.

   Global Variables
   
   void project_enter()                      void project_leave()
   

6. Consider a traditional Unix filesystem.

   • What sort of events would lead to inconsistencies in the filesystem?

   • Which types of inconsistencies would fsck be able to resolve?

7. Consider a multi-indexed filesystem with a 32-bit block address, 4KB block size, and an inode structure with 4 direct pointers and one indirect pointer:

   • What is the largest disk this file system can use?

   • What is the largest file that this file system could store?

   • Assuming a disk of 128GB, how big is the free block bitmap?

   • How many data blocks are required to store 18474 bytes?