CS 416 Final Exam info

When & where

The final exam will be held on Monday, May 7 from 4:00pm-7:00pm. It will take place in our regular classroom, SEC-209.

If you plan to take the final, please be sure to bring your ID with you.

Exam rules

This will be a closed book, closed notes exam. Calculators, laptops, netbooks, and tablets are neither needed nor permitted.

No other electronic devices, including phones and music players are permitted except for hearing aids, pacemakers, electronic nerve stimulators, other implanted medical devices, and electronic watches.

Bring a couple of pens or pencils with you. An extra pencil is affordable fault tolerance.

Tentatively, the final exam will consist of 50 multiple choice questions covering topics from the entire semester.

What's on the exam?

You are responsible for all the material presented in class. The final is cumulative with a particular emphasis on the topics of scheduling, memory management, and file systems.

Past exams

Get past 416 exams and information about exam taking here.

Study guides

You might find it helpful to consult the past study guides:

List of topics

Here's a cumulative list of the material we covered in the course (disclaimer: some topics not listed may be on the exam and some listed topics may not, but if you know the list, you can do very well on the exam):

Exam 1 topics

  • Introduction & Booting
    • Text: chapter 1: 1.0-1.2 (p.3-12), 1.4-1.6 (p.18-24)
    • Some basic terms: multiprogramming, system call, batch systems, device drivers, preemption
    • Operating system definition: what does it do?
    • Mechanism versus Policy
  • Booting
    • Text: 2.11 (p.87-88)
    • Boot loader: what does it do?
    • Multi-stage boot loader (chain loading)
    • You do not need to know the PC boot details but have a general idea of what the BIOS does (power-on test, initialize devices, identify boot device, and load MBR)
    • You do not need to know the Mac's EFI-based boot sequence either
    • Master Boot Record (MBR): just know that it contains a boot loader that loads the volume boot loader for a disk partition.
    • You do not need to know how GRUB boots systems beyond the MBR containing the stage 1 loader that then loads the stage 2 loader, which then loads the oprating system (or gives you a choice).
    • For EFI, jut know that it's a successor to the BIOS and has a built-in boot manager that usually loads an OS loader without going through a two-stage`process.
  • OS Concepts
    • Text: 2.1-2.4 (p.47-64), 2.7-2.7.4 (p.68-74)
    • Monolithic vs. modular vs. microkernel structures
    • User mode vs. kernel mode (= privileged mode or supervisor mode)
    • Getting from user to kernel mode and back again
    • Traps (aka softwre interrupts)
    • System calls
    • Programmable interval timer interrupts: why do you need them?
    • Mode switch and context switch
    • What's invoved in saving process state?
    • Device types: character, block, and network
    • Interacting with devices: memory mapped I/O
    • Getting status from devices: interrupts and polling
    • Moving data to/from devices: programmed I/O or DMA
  • Processes
    • Text: 3.0-3.3.2 (p. p.99-114)
    • Program vs. process
    • Memory map: text, data, bss, heap, stack (don't memorize the list but know what each is)
    • Process states: ready, running, blocked (aka waiting)
    • Preemptive multitasking
    • Process control block (PCB): don't memorize the list of what it stores but know that it at least stores the machine state, process state, memory map, and process ID.
    • Process list/table: keeps track of PCBs.
    • Creating a process under Unix with fork: know that it creates a copy of the parent
    • You do not need to memorize the sequence of operations that fork or other system calls perform
    • Execve: what does it do?
  • Threads
    • Text: 4.0-4.6 (p.145-166)
    • What's a thread vs. a process?
    • What do threads in a process share? entire memory map, open files, permissions
    • What's a thread control block (TCB)?
    • Kernel-level versus user-level threads. Advantages & disadvatages of each.
    • Hybrid kernel/user models.
    • thread create and join vs. fork/wait.
  • Synchronization
    • Text: 6.0-6.10 (p.217-259)
    • Definitions: concurrent, asynchronous, independent, synchronous
    • What is a race condition?
    • Definitions: critical section, mutual exclusion, deadlock, starvation
    • What is a spin lock (aka busy waiting)?
    • Problems with disabling interrupts.
    • Problems with test and set locks in software
    • You don't have to know Peterson's algorithm
    • Test and set instruction: how does it work?
    • compare and swap instruction: how does it work?
    • fetch and increment instruction: how does it work?
    • Avoiding spin locks - turn to OS
    • Priority inversion
    • Semaphores
      • What is a semaphore?
      • What are the operations on it?
      • When does a semaphore put threads to sleep and wake them up?
      • Understand the producer-consumer example
    • Event counters
      • What are the operations on it?
      • When does an event counter put a thread to sleep or wake it up?
    • Condition variables (monitors)
      • What are the operations in condition variables?
      • When does a condition variable put a thread to sleep or wake it up?
    • Messages
      • Understand send and receive operations
      • understand the producer-consumer example with a read causing a thread to block if there is nothing to read
      • Understand rendezvous: reads and writes block
      • Understand mailboxes and how indirect addressing helps to support multiple readers and writers
  • Process Scheduling
    • Text: 5.0-5.5.4 (p. 175-197), 5.6-5.6.3 (p.198-205)
    • CPU bursts and I/O bursts
    • What does a scheduler do?
    • When does a scheduler get a chance to dispatch (run) a process?
    • Preemptive versus cooperative schedulers
    • You don't have to memorize the list of 10 scheduling goals.
    • First-come, first served scheduling
      • What's the scheduling algorithm?
      • Disadvantages
    • Round-robin scheduling
      • What's the scheduling algorithm?
      • What is a quantum (aka time slice)?
      • Pros and cons of big and small time slices
      • What are the key advantages and disadvantages?
    • Shortest remaining time first scheduling
      • What's the scheduling algorithm?
      • What is the main purpose/advantage?
      • What is the main drawback?
      • Estimating CPU burst time: don't memorize the function but understand that it's a weighted exponential average that is a function of the last measured CPU burst and past history.
    • Priority scheduling
      • What's the scheduling algorithm?
      • What is the main purpose/advantage?
      • What is the main drawback?
      • Static vs. dynamic priorities
      • What is starvation?
      • What is process aging?
    • Multilevel feedback queues
      • Difference from multilevel queues
      • Priority classes
      • Understand how processes trickle to lower levels based on CPU burst
      • Advantages & disadvantages
    • I will not ask you about guaranteed scheduling, or the completely fair scheduler
    • I will not ask you about the windows or solaris schedulers
    • Multiprocessor scheduling
  • Real-time Scheduling
    • Definitions: release time, deadline, hard vs. soft deadlines
    • Earliest deadline scheduling: how do you pick the next process?
    • Least slack scheduling: how do you pick the next process?
    • Comparison between earliest deadline and least slack scheduling
    • Rate-monotonic analysis: how do you prioritize processes?

Exam 2 topics

  • Memory Management,
    Chapter 7: Main Memory: 7.1 (Background) - 7.8 (Summary); pages 277-312
    Chapter 8: Virtual Memory: 9.1 (Background) - 8.11 (TLB Reach); pages 319-371
    • Static vs. dynamic linking, shared libraries
    • Monoprogramming vs multiprogramming
    • Single partition monoprogramming
    • CPU utilization
    • Dynamically relocatable code
    • Memory management unit: concept of dynamic address translation
    • Logical (virtual) vs Physical (real) addresses
    • Base & limit addressing
    • Multiple fixed partitions (internal vs. external fragmentation)
    • Variable partition multiprogramming
    • Segmentation
    • Allocation algorithms: first fit, best fit, worst fit.
    • Memory compaction (relocation to combine holes)
    • Kernel memory allocation
      • Page allocator (why might you need contiguous pages?)
      • Buddy system
      • Slab allocator (you don't need to know the structures; just have an idea of how it works)
      • Page-based virtual memory:
        • page number and offset (displacement)
        • page table, PTE, page fault
        • direct mapping paging system, page table base register
        • Translation lookaside buffer (TLB)
        • Hit ratio
        • Address space identifier: why do you want it?
        • Multilevel (hierarchical) page tables, partial page table: understand benefit
        • Inverted page table
      • Understand the benefits of page-based virtual memory
      • Key points about the ARM MMU:
        • pages (via a two-level hierarchy) and sections (via direct mapping)
        • two page tables per process (why?)
        • two levels of TLB
        • I will not ask you about the different translation flows.
        • Do not memorize the sizes of different sections and pages.
      • Key points about the Intel MMU:
        • it supports combined paging & segmentation
        • what's a far pointer?
        • Segmentation, offering per-segment protection
        • Depending on the address size and page size, anywhere from direct mapping to four levels of page tables
        • two levels of TLB
        • I will not ask you about descriptor tables or the partitioning of an address to support multi-level page tables.
        • I will not ask you about the different memory models that the architecture supports (IA-32 paging, 64-bit mode, PAE, etc.); just know that you have real mode (physical), paging, segmentation, or combined paging and segmentation.
      • Demand paging
      • Memory-mapped files
      • Have a good idea of what the page fault handler does
      • Page replacement algorithms
        • FIFO replacement
        • LRU replacement (why can't we use this?)
        • Not frequently used replacement
        • Clock (second chance) replacement
        • Nth chance replacement
      • Kernel swap daemon
      • Locality and the working set
      • Working set model
      • Thrashing
      • Resident set
      • Using page fault frequency to manage resident sets
    • Device drivers
      Chapter 12: I/O Systems: 12.1 (Overview) - 12.5 (Transforming I/O Requests to Hardware Operations); pages 493-518
      Chapter 11: Mass-Storage Structure: 11.1.1 (Magnetic Disks), 11.4 (Disk Scheduling) - 11.5.1 (Disk Formatting); 457-459, 462-469
      • Device driver, device controller
      • mechanism vs. policy
      • Device independence
      • Block devices
      • Character devices (you don't have to know about raw and cooked modes)
      • Network devices
      • Kernel modules (you don't need to know the Linux commands; know that a module contains a function that the kernel calls upon loading to allow it to initialize itself and register its services
      • You don't need to know the cdev, gendisk, or net_device structures or their operations but know that each type of device has a set of common functions that drivers need to implement.
      • Buffer cache: understand buffered I/O. Why do you want it?
      • Blocking, non-blocking, asynchronous I/O
      • Major and minor numbers; devices in the filesystem namespace
      • I will not ask you about the Linux udev device manager or the netlink socket interface
      • I will not ask you about any of the functions of file interface or driver interface
      • Kernel, user, and interrupt execution contexts
      • interrupt handler: understand what a hook is
      • top half and bottom half interrupt servicing
      • I/O queues, device status table
      • Goal of driver frameworks
      • The disk
        • Disk scheduling: Elevator algorithms: SCAN, LOOK, C-SCAN, C-LOOK, SSTF
        • I will not ask you about Completely Fair Queueing
        • Linux deadline scheduling
        • NOOP scheduling (FIFO): when would you use it?
        • Anticipatory scheduling: know it's built on top of C-SCAN
        • Read-ahead
        • Logical block addressing vs. cylinder-head-sector addressing.
    • File systems
      Chapter 9: File-System Interface: 9.1 (File Concept) - 9.3.5 (Tree-Structured Directories), 9.4 (File-System Mounting); pages 383-402, 406-408
      Chapter 10: File-System Implementation: 10.1 (File-System Structure) - 10.7.2 (Log-Structured File Systems); pages 423-450
      • Mounting
      • Virtual File System (VFS)
        • Superblock: just know that it keeps key parameters about the file system: size, name, type
        • inode: what kind of info does it store at the VFS layer?
        • directory entry (dentry)
        • file : don't memorize the file operations but a few of them should make sense
      • list of mounted file systems
      • Implementing file systems
        • Terms
          • Disk
          • Block
          • Partition
          • Volume
          • Superblock
          • Metadata
          • inode
          • clusters versus extents
          • internal versus external fragmentation
        • Allocation:
          • contiguous
          • extents
          • linked allocation
          • file allocation table (FAT)
          • indexed (inode); combined indexing with indirect blocks
        • Directories: linear list, hash, B-Tree
        • Low-level vs. high-level formatting
        • Understand the basic operations associated with opening, writing, and deleting files
        • Hard links vs. symbolic links
        • Case studies
          • DOS/Windows FAT
            • Understand that a directory is file containing names, attributes, and the starting block number.
            • Understand how to use a file allocation table.
          • Unix File System (UFS)
            • Understand that a directory is a file containing a list of {name, inode} pairs.
            • Understand what inodes are and how disk blocks are mapped.
            • understand the effects of disk fragmentation.
          • BSD Fast File System
            • How did it improve over UFS?
            • Large blocks, fragments
            • cylinder groups: how did they help?
            • prefetching blocks
            • remember that metadata writes are synchronous
          • Linux ext2
            • Know that it's similar to FFS but cylinder groups are replaced with block groups
            • Know that fragments are gone.
            • Know that it's more aggressive with caching and not forcing metadata writes to be synchronous
          • Linux ext3
            • Understand the concept of a journal, consistent update problem
            • redo logging
            • ordered journaling as an optimization to data journaling
            • writeback journaling vs. ordered journaling
          • Linux ext4
            • Don't study the list of changes; just know that it uses extents instead of block numbers
          • Microsoft NTFS
            • know that it offers journaling + data compression
            • know that it uses extents
            • Know the MFT is similar to an inode (file record) table but is itself structured like a file
            • Everything is a file: easy to grow the file system
            • Behind-the-scenes compression of files
          • YAFFS
            • dynamic vs. static wear leveling
            • basics of a log-structured file system: all data, inode, and metadata changes are written as logs
            • I will not ask you about YAFFS2 vs. YAFFS1
            • Know that for YAFFS the name space is reconstructed by traversing the log.
            • Know that log entries that are no longer needed can get reused.
            • Why is garbage collection needed?
            • Why is this good for wear leveling?
        • Special devices and file systems
          • Special devices: null device, zero device, random device
          • Loop device
          • Special file systems: process file system (procfs), device file system (devfs), FUSE (user-level file system)

    Exam 3 topics (plus virtualization)

    • Client-server networking
      • circuit-switched vs. packet switched networks
      • protocols and layering
      • OSI reference model: understand layers 1-4 (physical, data link, network, transport)
      • terms: node, NIC, baseband vs. broadband
      • ethernet and CSMA/CD vs. CSMA/CA
      • I will not ask about media, hubs, routers, bridges, DOCSIS, ethernet topology, or wireless networks
      • transport address
      • transport-layer protocols: connection-oriented (virtual circuit) vs. connetionless (datagram)
      • Internet Protocol (IP), host and network numbers
      • Don't memorize classes but understand why they were created
      • I will not ask about jumbo packets, MTUs, the structure of ethernet, IP, IPv6, TCP, or UDP packets. Understand, however, ethernet vs. IP addresses and that transport-layer IP protocols (TCP, UDP) have a port number.
      • Don't memorize but understand the list of IP driver responsibilities
      • Packet encapsulation (enveloping)
      • Address resolution protocol (what does it do and why do we need it?)
      • I will not ask about routing
      • TCP vs. UDP, port numbers and their purpose
    • Sockets
      • Text: Section 3.6.1, pages 126-129
      • Purpose of sockets
      • What do the following system calls do? socket, bind, listen, connect
      • I will not ask you about the parameters of the above functions
      • I will not ask about synchronous vs. asynchronous operations
      • System call interface: file descriptor-based and socket-specific
      • What's the purpose of the socket layer and the socket structure?
      • What's the purpose of a socket buffer (sk_buff)?
      • I will not ask you about the socket or proto structures but know what a socket structure is used for vs. a sk_buff (socket buffer).
      • What's the purpose of the abstract device interface layer?
      • I will not ask about specific functions within the device interface (e.g., dev_queue_xmit, netif_rx_schedule)
      • Understand where device drivers sit in the hierarchy.
      • Linux NAPI approach to handling device interrupts
    • Remote procedure calls
      • Text: Section 3.6.2, pages 129-132
      • Remote procedure call: definition/goal
      • I will not ask you about the functional flow of regular procedure calls
      • language-level versus operating-system construct
      • stub functions: purpose of client and server stub functions
      • RPC call flow
      • I will not ask about big vs. little endian or data representation formats
      • I will not ask about implicit vs. explicit typing, where to bind, transport protocols, or security issues
      • Understand the need for an interface definition language (IDL)
    • Network file systems
      • Network attached storage (NAS): definition
      • upload/download model vs. remote access model
      • sequential vs. session semantics
      • I will not ask about immutable files, atomic transactions, or file usage patterns
      • Understand stateful vs. stateless approaches
      • I will not ask about caching but understand what write-through, read-ahead, and delayed writes do
      • NFS
        • I will not ask about design goals
        • Understand that an RPC interface is used
        • Purpose of mounting vs. directory & file access protocols
        • What does the lookup RPC do and why is it not an open of a file ?
        • Do not memorize the NFS RPC functions but have an idea of what they do.
        • Validation as an approach to cache management
        • Read-ahead to improve performance
        • Don't memorize the list of problems with NFS but go through them and understand them
        • Why does locking not work? Why can open with append not be guaranteed to work?
        • I will not ask about NFS version 2 or beyond or about the automounter.
      • AFS
        • Design goals
        • Big ideas: whole file serving and whole file caching
        • I will not ask about cells, volumes, the cell directory server, or the Volume Location Database
        • callback promise
        • session semantics
      • SMB/CIFS
        • Design goals
        • message blocks
        • remote access protocol
        • I will not ask about the structure of the message block
        • Don't memorize the list of commands but they should make sense
        • Understand the things you can do with SMB that you cannot do with NFS (delete on the server won't cause a remotely open file to disappear, lock a file, open with append: all these require state)
        • I will not ask about the protocol but note that it's connection-oriented
    • Protection
      • Text: Sections 13-13.3.2, 13.4-13.5.3, 13.6-13.7 pages 529-534, 536-541, 543-545
      • Principle of least privilege
      • Privilege separation
      • setuid
      • Protection domain, access matrix
      • I will not ask about domain transfers, copy, owner, and control operations
      • Access control list vs. capability list
      • Limited ACLs in POSIX systems vs. full ACLs
      • Discretionary access control (DAC) vs. mandatory access control (MAC)
      • What does the Bell-LaPadula model do?
    • Security
      • Text: Sections 14 to 14.3.3, pages 553-570.
      • I will not ask you to list threats, discuss attack categories or techniques
      • Buffer overflow bug: stack smashing
      • Return Oriented Programming
      • Address Space Layout Randomization
      • Stack canaries
      • I will not ask about network service penetration or SYN flooding
      • What's a virus?
      • What's a rootkit?
      • sandboxing
        • chroot jail
        • kernel-level sandboxing: understand that it provides policy-based access control
        • Java sandbox
    • Cryptographic systems
      • Text: Sections 14.4-14.4.1, pages 570-578.
      • restricted vs. symmetric vs. public key algorithms
      • use of a hash function
      • key length vs. difficulty of brute-force attack
      • understand the difference between public key and symmetric algorithms; what private keys are used for, what public keys are used for.
      • key exchange (using Diffie-Hellman, and public Keys)
        • Diffie-Hellman (know what it does but don't memorize the algorithm)
        • public key cryptography (how do you use it for key exchange?)
      • how do you use public keys for encryption, signatures, and key exchange?
      • do not memorize algorithms: I will not ask you to recite the RSA or Diffie-Hellman algorithms. You should know that Diffie-Hellman is a key exchange algorithm and that RSA is a public-key algorithm.
      • hybrid cryptosystem (understand advantage and how session key exchange works)
      • digital signatures with public key algorithms
      • secure communciation
        • with symmetric cryptography
        • with public key cryptography
        • with a hybrid cryptosystem
    • Authentication
      • Text: 14.5-14.7, pages 581-588.
      • Authentication vs. Identification
      • multi-factor authentication
        • what are the three factors?
      • reusable passwords (PAP, password authentication protocol)
      • dictionary attacks, hash
      • Challenge Handshake Authentication Protocol (CHAP)
      • one-time passwords: s/key, SecurID (just know that the password is f(PIN, seed, time))
      • authentication with symmetric cryptography
      • Kerberos (know the basics how it works - don't worry about memorizing details, know how tickets work and the purpose of the server). See the lecture slides.
      • public key authentication
        • how does it work? What is a nonce and how do you use it?
        • digital certificates (don't memorize fields but understand how a certificate can be used)
      • signed software: page-based vs. whole-code signatures (remember how signatures are created)
    • Virtualization
      • Types of virtualization: memory, CPU, storage, machine
      • Processor (CPU) virtualization vs. machine virtualization
      • Virtual Machine Monitor, hypervisor
      • how do privileged instructions work under a MM? Trap into hypervisor.
      • Hosted VM vs. Native VM
      • Native VM architecture requires the VMM to do scheduling of the virtual machines under it
      • You do not have to know the architectural support in Intel and AMD architectures but you should understand that they can create an exit from a VMM that allows software (the OS under the VM) to feel like an interrupt took place
      • I will not ask you about scheduling VMs
      • What is OS-level virtualization?