CS 416 Final Exam info

Get past 417 exams and information about exam taking.

When & where

The final exam will be held on Monday, May 11 from 8:00pm-10:00pm. It will take place in our regular classroom, TIL-257.

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

Remember that the final is optional and will only serve to displace a lower normalized grade on one of the three exams.

Exam rules

Be sure to arrive on time. If you arrive after the exam starts, you will not be allowed to take it.

This will be a closed book, closed notes exam. Calculators, phones, laptops, and tablets are neither needed nor permitted. If you have these devices, you must turn them off, put them out of sight, and not access them for the duration of the exam.

No other electronic devices are permitted except for hearing aids, pacemakers, electronic nerve stimulators, other implanted medical devices, or electronic watches that function only as timekeeping devices or chronographs.

Bring a couple of pens or pencils with you. An extra pencil is affordable fault tolerance. If you want to splurge, the Palomino Blackwing 602 is considered by many to be one of the finest pencils available.

Past exams

Get past exams and information about exam taking here.

What's on the exam?

You are responsible for all the material presented in class except for the last lecture (which covered windowing and power management). The final is cumulative with a concentration toward the latter half of the semester.

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

Topics

You are responsible for the material from since the start of the semester.

Topics that you should know and may be on the exam include:

Introduction & Booting

Text: chapter 1: 1.0-1.2 (p.3-12), 1.4-1.6 (p.18-25)

  • Some basic terms: multiprogramming, system call, batch systems, device drivers, preemption
  • Operating system definition: what does it do?
  • Mechanism versus Policy

Booting

Text: 2.10 (p.92-93)

  • 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 then loads the Volume Boot Record (VBR) from a specific disk partition, which contains the boot loader code that loads the operating system.
  • 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.55-73), 2.6.2 (p. 76), 2.7-2.7.5.3 (p.78-86)

  • 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 software interrupts): INT vs. SYSCALL instructions
  • 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.105-122)

  • 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), zombie; transitions between states
  • 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: keeps track of PCBs.
  • Creating a process under Unix with fork: know that it creates a copy of the parent
  • Know the difference between fork, execve, and wait.
  • What is a zombie process?
  • Know how a process can tell if it is the parent or the child after a fork
  • Loading and executing a program under Unix with execve: know that it overlays the data in the current process
  • You do not need to memorize the internal sequence of operations that fork or other system calls perform
  • The init process

Threads

Text: 4.0-4.6 (p.163-188)

  • 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.
  • Linux clone() operation vs. threads

Synchronization

Text: 5.0-5.9 (p.203-238), 5.11 (Deadlocks, p. 242-249)

  • Definitions: concurrent, asynchronous, independent, synchronous
  • What is a race condition?
  • Definitions: critical section, mutual exclusion, deadlock, starvation
  • What is a spinlock (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? Understand initialization, up, and down
    • 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 null messages and 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
  • Deadlock
    • Conditions for deadlock
    • Wait-for graph
    • Ways of handling: prevention, avoidance, detection, ignore

Process Scheduling

Text: 6.0-6.5.4 (p. 259-291), 6.7-6.7.3 (p.298-307)

  • 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
  • Turnaround time, response time,
  • 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
    • Role of process aging
    • Gaming the scheduler by performing I/O
    • Advantages & disadvantages
  • Lottery scheduler
    • Goal and general principle
  • I will not ask you about guaranteed scheduling, or the completely fair scheduler
  • I will not ask you about Linux, Windows, or Solaris schedulers
  • Multiprocessor scheduling issues: CPU affinity, hard vs. soft affinity
  • What is hyperthreading?
  • Purpose of Linux scheduling domains

Real-time Scheduling

Text: 6.6-6.6.4 (p. 291-297)

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

Memory Management

Text: chapter 7: Main Memory: 7.1 (Background) - 7.9 (Summary); pages 325-365
Text: chapter 8: Virtual Memory: 8.1 (Background) - 8.9.3 (TLB Reach), pages 371-416

  • 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)
  • 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 (ASID): why do you want it?
    • Multilevel (hierarchical) page tables, partial page table: understand benefit
    • I will not ask you about inverted page tables
  • 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)
    • I will not ask you about ARM's two page tables per process
    • Two levels of TLB
    • I will not ask you about the different translation flows.
    • Do not memorize the sizes of different sections and pages. Just understand the value of sections in having an efficient way to map large chunks of memory, such as an operating system, to a process' address space.
  • Key points about the Intel MMU:
    • 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: understand know the concept
  • Memory-mapped files
  • Have a good idea of what the page fault handler does, not any specific steps
  • 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
  • Kernel memory allocation
    • Page allocator (why might you need contiguous pages?)
    • Buddy system
    • I will not ask you about the zone allocator
    • Slab allocator (you don't need to know the structures or operations; just have an idea of how it works)
    • SLOB allocator
    • I will not ask you about SLUB; it's just a variation of Slab

Device drivers


Text: chapter 12: I/O Systems: 7.1 (Overview) - 7.9 (Transforming I/O Requests to Hardware Operations); pages 561-589
Text: Chapter 9: Mass-Storage Structure: 9.1.1 (Magnetic Disks), 9.1.2 (Solid State Disks), 9.4 (Disk Scheduling) - 9.5.1 (Disk Formatting); pages 441-443, 446-454 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 vs. bottom half interrupt servicing
  • I/O queues, device status table
  • Goal of driver frameworks (super high level - just that they identify classes of devices and define required functions)
  • The disk
    • Disk scheduling algorithms: SCAN, LOOK, C-SCAN, C-LOOK, SSTF, FCFS
    • 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


Text: Chapter 10: File-System Interface: 10.1 (File Concept) - 10.3.5 (Tree-Structured Directories), 10.4 (File-System Mounting); pages 477-496, 500-502
Text: Chapter 11: File-System Implementation: 11.1 (File-System Structure) - 11.7.2 (Log-Structured File Systems); pages 517-544

  • Terms
    • Disk
    • Block
    • Partition
    • Volume
    • Track
    • Cylinder
    • Seek
    • File
    • File name
    • File data
    • Metadata
    • Attribute
    • Directory
    • Superblock
    • inode
    • Clusters vs. Extents
    • Internal vs. external fragmentation
  • 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
  • mount points: kernel needs to keep a track of mounted file systems
  • Implementing file systems
    • Allocation:
      • contiguous
      • extents
      • linked allocation
      • file allocation table (FAT)
      • indexed (inode); combined indexing with indirect blocks
    • Directories - possible structures: linear list, hash, B-Tree
    • Hard links vs. symbolic links
    • Functions: understand the basic operations; don't memorize steps
      • mounting
      • union mounts
      • file system checking (don't memorize steps but understand the point of it)
      • steps in creating files (don't memorize but understand)
      • creating directories: what's different from creating a file?
      • opening a file
      • writing to a file (don't memorize steps but understand what needs to be done if the file has to grow; also, realize that sometimes you need to read to modify just parts of a block)
      • reading from a file
      • deleting a file (understand that it's about reference counting)
  • 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 (FFS)
      • How did it improve over UFS?
      • Large blocks, fragments (don't worry about the mechanics of how fragments are managed)
      • Cylinder groups: how did they help?
      • Prefetching blocks
      • Remember that metadata writes are synchronous for robustness
    • 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

File systems: Log-Structured File Systems

Warning: the description of log-structured file systems in the text (pages 543-544) is incorrect. It discusses journaling rather than log-structured file systems.

  • dynamic vs. static wear leveling
  • Block Lookup Table: logical-to-physical block translation on the flash controller
  • Flash Translation Layer (FTL):
  • just the 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 or versus any other log-structured types
  • 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?
  • Purpose of checkpointing.
  • Why is a log-structured file system good for wear leveling?

Pseudo devices and special file systems


Text: Section 15.7.4: The Linux Process File System, pages 720-721

  • Pseudo devices: null device, zero device, random device
  • Loop device: what is it?
  • Special file systems
    • Process file system (procfs): what does it do?
    • Device file system (devfs): purpose
    • FUSE (user-level file system)

Client-Server networking

  • Recognize channel partitioning, TDM, FDM, and token passing if you see them but you do not have to know about them except that they differ from the random access used by packet switching.
  • circuit-switched vs. packet switched networks
  • protocols and layering
  • OSI reference model: understand layers 1-4 (physical, data link, network, transport)
  • I will not ask about media, hubs, routers, bridges, ethernet topology, or wireless networks
  • What is protocol (packet) encapsulation?
  • transport-layer protocols: connection-oriented (virtual circuit) vs. connetionless (datagram)
  • Internet Protocol (IP)
    • Ethernet MAC address vs. IP address
    • What is the Address Resolution Protocol (ARP) used for?
    • What is the Domain Name System (DNS) used for?
    • TCP vs. UDP
    • Purpose of port numbers
  • 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.
  • I will not ask about routing

Sockets


Text: 3.6 (Communication in Client-Server Systems): 3.6.1 (Sockets); pages 136-138

  • 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 interfaces: file descriptor-based and socket-specific
    • WHat does it mean for a socket to be compatible with files?
  • What's the purpose of the the socket structure?
  • What's the purpose of a socket buffer (sk_buff)? How does it make moving data through the network stack efficient?
  • 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).
  • Top half vs. bottom half work for receiving incoming messages
  • What's the purpose of the abstract device interface layer?
  • I will not ask about routing. You don't need to know about the FIB (Forwarding Information Base).
  • 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: 3.6 (Communication in Client-Server Systems): 3.6.2 (Remote Procedure Calls); pages 138-142

  • 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: understand the diagram and what is meant by marshaling/unmarshaling
  • 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 purpose of an interface definition language (IDL)

Network attached storage


Text: 11.8 (NFS) pages 545-551

  • 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
  • understand what write-through caches, 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?
  • 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
    • Understand the things you can do with SMB that you cannot do with NFS because SMB is stateful (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: 13 (Protection) - 13.3.2 (An Example: UNIX) pages 601-606.
Text: 13.4 (Access Matrix) - 13.5.3 (Capability Lists) pages 608-613.
Text: 13.6 (Access Control) - 13.7 (Revocation) pages 615-616.

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

Cryptographic systems


Text: 14.4 (Cryptography as a Security Tool) - 14.4.1 (Encryption) pages 650-657.

  • 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 public key cryptography
  • how do you use public keys for encryption, signatures, and key exchange?
  • do not memorize algorithms: I will not ask you about the inner working of algorithms. You should understand, however, how to use public keys, private keys, and symmetric keys.
  • hybrid cryptosystem (understand advantage and how session key exchange works)
  • digital signatures with public key algorithms
  • purpose of a cryptographic hash function
  • secure communciation
    • with symmetric cryptography
    • with public key cryptography
    • with a hybrid cryptosystem

Authentication


Text: 14.5 (User Authentication) - 14.7 (Firewalling) pages 661-674.

  • reusable passwords: PAP, password authentication protocol
    • How do you ensure passwords cannot be not accessed?
    • dictionary attacks, hash, salt
  • Challenge Handshake Authentication Protocol (CHAP)
  • one-time passwords: SecurID (just know that the password is f(PIN, seed, time))
  • Wgat us a man-in-the-middle attack?
  • 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)
      • What's the purpose of a certificate?
      • What's makes it unforgeable?

Security


Text: 14 (Security) - 13.3.3 (Denial of Service) pages 633-650.

  • I will not ask you to list threats, discuss attack categories or techniques
  • Buffer overflow bug: stack smashing
    • benefits of no execute permission
    • Return Oriented Programming
    • Address Space Layout Randomization (ASLR)
    • Stack canaries
  • I will not ask about network service penetration or SYN flooding
  • I will not ask about key logging
  • What's a virus?
  • What's a rootkit?
  • sandboxing
    • chroot jail
    • Kernel-level sandboxing: understand that it provides policy-based access control
    • What is the Java sandbox?
  • signed software
    • page-based signatures - why?
    • vs. whole-code signatures (remember how signatures are created)
    • I will not ask you any details about Microsoft Authenticode

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?