Topics on final
CS 273 (OS), Fall 2020
Note: An asterisk [*] indicates lists of concepts you may be asked to produce without prompting (e.g., "List the four necessary and sufficient conditions for deadlock"). For other concept lists, you may be asked to comment but will not be asked to recite the list.
Note: An asterisk [*] indicates deeply conceptual topics that are especially important to review.
Overview
- Linux and system calls
- IPC
- Scheduling
- Memory management
- File systems
- I/O and devices
- Deadlock
- Security and protection
- Project-related questions
Linux and system calls
Familiarity with behavior of most emphasized system calls:
fork,execve,wait,waitpid,open,read,write,lseek,close,dup,dup2,pipe,kill.Process diagrams indicating process history and system calls performed
Threads - focus on differences/similarities between threads and processes, and reading/modifying pthreads code (example codes and project stage concepts)
IPC
[*] Four conditions for correct IPC
General (often incorrect) IPC strategies; pros and cons of busy loops
Primitive systems for correct IPC without busy loops: semaphores, monitors, message passing
Scheduling
Concepts: compute-bound vs I/O bound; batch, interactive, real-time; policy vs mechanism
Algorithms: Be able to apply them and generally discuss advantages/disadvantages
Batch: FCFS, SJF
Interactive: Round robin, priority, shortest process next with aging
Memory management
Swapping
Conceptual understanding; differences and similarities with paging.
Data structures for managing swapping: bitmaps, linked lists, buddy system
-
Terms: page, page frame, virtual memory, page table, page fault, MMU, TLB, etc.
Structure of addresses as page frame numbers + offsets
Tradeoffs in page table size
Page replacement policies: NRU (with R, M), FIFO, LRU, NFU (remember R, e.g., aging)
Segmented memory concepts.
I/O and devices
Six layers of I/O: User level; device independent OS software; device drivers; interrupt handler; device controller; device.
Know what each layer does.
Understand how the layers relate to other aspects of a computer system
I/O software design models: programmed I/O (with polls and busy waits), interrupt-driven I/O (blocking for input); DMA
Generic structure of a device driver.
Disks:
Disk arm scheduling algorithms: first-come first-served (FCFS); shortest seek first (SSF); elevator algorithm
Deadlock
[*] Definition of deadlock
[*] Four necessary and sufficient conditions for deadlock
Pros and cons of deadlock strategies discussed in class.
Deadlock strategies related to the four conditions; e.g., deadlock avoidance (safe states).
File systems
Features apparent to a user: logical internal organization; device independence; file naming; file types; random access; memory mapped files
File storage strategies, including the examples of UNIX i-nodes and DOS FAT (File Allocation Table)
General understanding of Linux i-nodes and directories
Issues in the block cache: e.g., retaining essential blocks, discarding unnecessary blocks early, write-through cache
File system-related system calls
Security and protection
Categories of security issues: availability, secrecy, authenticity, integrity
'88 Internet worm as an example of security flaws.
Types of security attack: Trojan horse, login spoofing, logic bomb, trap door, buffer overflow, etc. Generally know what these attacks are.
Strategies for passwords (e.g., two-factor, passwordless authentication)
Protection mechanisms: protection domains; access control lists vs. capabilities; how Linux uid/gid strategy relates.
Seven principles of security: be able to recognize them and discuss them in context of examples.
Seven principles of security: be able to recognize them and discuss them in context of examples.
Project-related questions
Programming with standard system calls (no need to memorize #include files)
Programming with pthreads, sockets, FILEs, including synchronization (given example code)
Concepts in the kernel project -- virtual machines and virtual OS installations; elements of adding a system call