The emphasis of the exams will be on specifics and details covered in class and in the homework and projects, rather than the general descriptions of the type found mostly in Chapters 1-3 of OSCJ. For example, I might pose a question about how virtual memory provides protection between processes by defining how virtual addresses are interpreted, rather than ask about protection being "any mechanism for controlling access of programs." Many example of "protection" will be cited throughout the semester. Rather than merely knowing a command interpreter or shell is "the interface between the user and the operating system," there might be a question about how UNIX shells use command line scanning, fork() and exec() to get student exercise programs to be compiled and run.
Given this philosophy, study the assigned readings as follows:
OSCJ Ch1-3 (briefly, except for the specifics of examples of Ch. 3
terms given in the lectures, blocking and non-blocking system calls in
general and those covered in Projects 0-1.)
OSCJ Ch 4: Very Important: process or thread scheduling states,
concurrency, synchronization and buffering that occurred in Project 1,
the producer-consumer problem. What is a context switch?
OSCJ Ch5: The difference between a process and a thread (UNIX
terminology). Creating and using threads in Java, sharing of Java
variables by Java threads, scheduling of threads (blocked, ready,
etc.) What has to be saved and restored when one running thread
is replaced by another.
OSCJ Ch7: Emphasis on sections covered in the lectures and
homeworks..including demonstration of the effects of races by showing
the results of different interleavings of primative
operations(p.173-175).
Haviland: System calls used in Project 1, and used in the "smallsh" of
Chapter 5. Terminal behavior and synchronization covered by
Project 1: Raw vs canonical mode, use of MIN and TIME, their effects on
whether certain system calls are blocking or not.
Bovet: Ch 2: Difference between virtual (aka linear address, in i386)
and physical address, their relation to interprocess protection,
Bovet: Ch 3: Process or thread scheduling states, Parenthood, wait
queues, maybe copy-on-write.
OSCJ Ch 7: Race demonstration, the critical section problem, solution
issues for store-synchronous memory operations (Peterson's solution),
effect of preemptive vs non-preemptive scheduling on solutions to the
critical section problem, special hardware instructions, semaphores,
livelock and deadlock (starvation will come later) producer-consumer
and bounded buffer problems, use of Java threads and synchronization as
well as (POSIX) pthreads.
Basic UNIX file programming interfaces, directory structure, the
working directory and pathnames, and the file position indicator
(pointer).
| operating system (kernel) | bus address | Linux kernel wait queue | makefile, dependency, rule |
| operating environment | MMU (memory management unit) | shell (command interpreter) | syscall, trap, or interrupt instruction |
| instruction set architecture | memory access operation | interprocess communication | (execution) stack |
| device registers | virtual address | Unix fork system call | activation record or stack frame |
| CPUs general purpose registers | variable | Unix exec system call | preemptive and non-preemptive scheduling |
| multiprogramming | virtual addess | (Linux kernel) wait queue | |
| PC (program counter) | stack pointer | concurrency | virtual memory |
| CPU mode | interrupt/exception | Unix read and write system calls | physical memory |
| bind, listen, accept, connect (for a socket) | RAM (randomly accessible addressable memory | child process | shared variables |
| system call | base/limit registers | Basic Java thread programming | quantum (not physics) |
| interrupt/exception | Unix CWD, absolute and relative pathname | circular buffer, C/C++/Java's % operator. |
object, class, instance, methods, calling an instance method |
| representation invariant | Unix pipe | resumption point (of a ready thread) | Sequence Diagram (from UML) |
| subroutine or function call | segment (in virtual address space) | race | batch systems |
| executable file | context switch | thread | |
| blocking vs. non-blocking operation | process | thread creation | busy waiting |
| true (hardware) parallelism | process table | time sharing | caches and buffers |
| Producer-Consumer problem | process table entry, control block, or task structure | Unix system call error reporting | readers and writers problem |
| interleaving of execution steps | process scheduling states: running, ready, blocked | critical region (problem) | Java, wait, signal |
| Mutual exclusion/synchronization and threading features in Java | scheduler | directory (of files) | lock or mutex |
| Peterson's solution | return from interrupt/exception | atomic machine instructions, test-and-set | implement one operation using others |
| class, object, method | deadlock | socket, | |
| (final words below) | (final words below) | (final words below) | (final words below) |
| Unix (Posix) pipeline | file system | core image (file) | Gantt chart |
| round robin | aging algorithm, prediction | CPU utilization (%) | |
| message passing for synchronization | response (or turnaround) time | real time systems, periodic, hard, soft | deadlock prevention |
| deadlock avoidance, trajectory, safe state | monitors, condition variables |
Coffman's conditions | Banker's algorithm |
| semaphore | ostrich algorithm | resource allocation graph | shortest job first |
| deadlock detection | lost wakeup | first come first served | two phase locking |
| wait-for graph | priority inversion | scheduling priority | starvation |
| volatile variables in C/C++ | interractive and CPU bound processes | throughput | threaded server |
| Mutual exclusion/synchroniztion and threading features in pthreads | on-line versus off-line algorithm variations | dynamic link libraries, shared libraries | Translation Lookaside Buffer |
| safety and liveness | (Unix) interrupted system call, signals | depth first search | Memory management unit |
| memory hierarchy | locality of reference, | page table entry | translation lookaside buffer |
| multiprogramming, and degree of it | attributes of segments | page fault | segmentation error or signal |
| protection | relocation | swapping | page replacement algorithms |
| embedded processor | segments and pages compared | page replacement | clean and dirty pages |
| reference string | page number | address trace | working set |
| thrashing | direct memory access (re. I/O) | fragmentation, internal and external | log or journal based filesystem |
| physical address | demand paging | memory mapped files | |
| free page frame | MMU (memory management unit) | various page replacement algorithms | Belady's anomaly |
| persistant storage | non-volatile storage | disk drive partitioning | pathname |
| Unix block file abstraction | Unix file related system calls | data storage device characteristics | sequential vs. direct access software interfaces to files |
| File allocation methods | free space management | time-space tradeoffs | hierarchical directory structure |
| Types of files, support alternatives | Windows registry | attributes/values in Windows XP files | hardware vs. software protection architecture |
| Unix superuser | spatial, temporal (for locality of reference) | Hard versus soft link | reference count |
| Unix inode | concurrent file access sematics: Unix and session | function pointer (programming in C/C++) | virtual function |
| Unix file position | Unix file system indirect blocks | Unix buffer cache | I/O device port |
| Various caches related to disks | Disk sectors and addresses | seek time | disk operation scheduling |
| interrupt handler registration | polling to synchronize I/O devices with software | interrupts and I/O synchronization | bus addresses |
| virtual machine | schedule() function in Linux | serial and parallel buses | Unix character vs block special files |
| Encryption | Secret key exchange | authentication | priviliged machine instructions |
| static, automatic, dynamic variables in C/C++ | fair share (process scheduling) | top and bottom half, tasklet | multimedia |
| dummy head | Unix superblock | buddy algorithm | alias |
| PSW (processor status word) | |||
OSCJ Ch 8: Deadlock system model, Coffman's 4 conditions, resource allocation graphs, wait-for graph, depth-first-search (handout of pages from Corman, Leiserson and Rivest's Algorithms book), deadlock avoidance, prevention and recovery. Transaction model, 2-phase locking, log and rollback.
OSCJ Ch 9 and 10: User program processing (compiling vs linking vs loading), address binding, virtual vs physical addresses, dynamic linking, internal versus external fragmentation, memory space allocation strategies (first-fit, best-fit, worst-fit), applications of contiguous allocation, operation of (contemporary) hardware to support virtual memory with paging, page table/offsets, etc,., translation lookaside buffer, average access time formula, hit ratio,. etc., shared pages, demand paging, page replacement problem, various solutions including the optimal solution, reference string, working set, thrashing.
OSCJ Ch 11: Basic UNIX file programming interfaces, directory structure, the working directory and pathnames, the file position indicator (pointer), alternative consistency semantics, acyclic graph.
OSCJ Ch 12: File implementation: "File control block"/inode, reference counter idea and when a file's space can be reclaimed, allocation of space for a file: contiguous versus linked versus indexed, the file-allocation-table (FAT), UNIX "combined" scheme. Free space managment. Unix/Linux virtual file system as an example of subclasses and virtual functions (refer to ULK chapter 12 as needed), function pointers, how file descriptors are used in the Unix kernel, kernel data structures that reflect a disk file system and open files. Example of file system inside a disk partition (first 10 pages of ULK chapter 17).
Disk hardware and OSCJ Ch 13: Basic magnetic disk characteristics, how contemporary disk hardware is manipulated by software (disk sector addressing), buffering and caching within disk drives and within OS kernels, reason for disk operation scheduling, bad blocks.
ULK Chapter 13(p. 427-9, 447-8): Bus-based hardware architecture of contemporary computers, port(on an I/O device or controller), bus or physical address. Busy-waiting (or polling) I/O transfer compared to interrupt-driven and direct memory access, identifying concurrency and parallelism therewith.
It may also be helpful to skim the "Case Study" chapters of OSCJ, chapter 20-24, for reminders about examples that I mentioned informally in the lectures.