As you prepare for the final, read the assigned readings from the textbook and study your lecture notes. In addition, make sure you learned the following:

Processes/threads:

• Know how to solve a synchronization problem (e.g., classical or like the Bridges assignment) using some synchronization primitives (e.g., semaphores, monitors).
• Know how to implement high-level synchronization primitives on top of low-level ones (e.g., monitors on top of semaphores).
• Know the different variations of monitors (e.g., wait/signal or wait/notify on condition variables, Java wait/notify/notifyAll) and how they work and are implemented.
• Know different CPU scheduling algorithms (e.g., FIFO, SJF, SRT, RR, MLF, Priority). You should be able to trace the execution for a given sequence of jobs and compute performance measures (e.g., response time, waiting time).

Memory:

• Know different virtual memory architectures (e.g., paging, segmentation, segmentation with paging) and differences (e.g., pages versus segments, internal versus external fragmentation).
• Under a virtual memory architecture, know how address translation works and how to draw the address translation diagram showing the different registers/tables and their size and width in bits. Also, numerically carry out translations from a given virtual address to a physical address.
• Know different algorithms for allocating and freeing memory (e.g., first-fit, best-fit, worst-fit, coalescing free blocks, memory compaction). Know how to trace the execution given a sequence of memory requests and how to express an algorithm in pseudo-code.
• Know about demand paging and different page replacement algorithms (e.g., FIFO, LRU, Second Chance, Enhanced Second Chance, Working Set, Page Fault Frequency). Know how to trace the execution given a sequence of page references and how to express an algorithm in pseudo-code.
• Know how to briefly define or contrast different terms (e.g., thrashing, load control, paging, prefetching, swapping, dynamic relocation, temporal and spatial locality, local versus global page replacement).
• Know how to speed up algorithms using appropriate hardware support and/or approximations (e.g. TLB for address translation).

Files:

• Know about different file types (e.g., structured versus unstructured) and different access methods (e.g., sequential versus random).
• Know what happens when you "open" a file, and how many I/O operations are needed.
• Know different ways to allocate a file on a disk (e.g., contiguous, linked, indexed sequential, indexed with indirection), and how many I/O opeartions are needed to retrieve a block given a certain file.

Disks and I/O:

• Know the role of a device driver (e.g., disk driver).
• Know different algorithms for disk scheduling (e.g., FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK). You should be able to trace the execution for a given sequence of jobs and compute performance measures (e.g., response time, waiting time).
• Understand the life cycle of a process (of CPU and I/O bursts).
• Understand the life cycle of an I/O request (e.g., read characters from a file) going between file system, disk driver, DMA controller.

Networks and Distributed Systems:

• What is a network and what are potential benefits of networking.
• Know about different levels of connectivity (point-to-point, LAN, WAN, internet).
• Why do we need and how do we implement MAC (Medium Access Control) in shared LANs (e.g., Ethernet CSMA/CD, Token Ring) and understand differences between different MACs (e.g., in terms of determinism and fairness).
• Know the architecture of a network subsystem (e.g., TCP/IP) in an operating system. Understand the functionality of different layers (application, transport, internet, network interface) and the life cycle of an application message as it travels from a source application to a destination application on a remote host.
• Know about naming (e.g., Internet names and DNS) and addressing (e.g., IP addresses and ARP). Understand the importance of uniqueness of names and addresses and how it is achieved in a manageable way using hierarchical structures.
• Know about routing of packets and routing tables. Distinguish between connectionless and connection-oriented network (routing) service.
• Know the various functions of a transport protocol (e.g., TCP); error detection, error correction, sequencing, demultiplexing, etc.
• How error correction is achieved using a window-based retransmission protocol, such as TCP.
• You should be able to carry out a simple evaluation of the performance of a network or protocol (e.g., in terms of its utilization, throughput, response time).
• Know about network programming interfaces (e.g., sockets, RPC, Java RMI), client-server communication paradigm. You should be able to contrast different implementations (e.g., sequential versus concurrent servers).
• Know how to implement coordination/synchronization given a distributed set of processes (e.g., using Lamport's logical clocks, centralized coordinator, token passing). You should understand the concepts of partial and total ordering of events, and election of a coordinator/monitor (e.g., bully and ring algorithms).

Distributed File Systems:

• Understand the architecture of a distributed file system, such as Sun's NFS.
• Know the different naming schemes (server+path, mounting of remote files/directories, global) and their limitations.
• Understand caching, different cache update policies (write-through, delayed writes) and their advantages and disadvantages.
• Understand consistency. Know about different approaches (client- versus server-initiated), and what is meant by UNIX semantics and session semantics.
• Define and contrast stateful and stateless file servers.
• Define file replication and know about update protocols (e.g., primary copy and voting).

Case Studies:

• You should be able to define terms such as memory mapping a file, SMP (Symmetric Multiprocessing), POSIX, user versus kernel threads, microkernel, atomic transactions.
• You should be able to realize the goal and assess the advantages and disadvantages of a given policy. For example, realize that a given CPU scheduling policy automatically gives priority to interactive jobs or that a given page replacement policy implements an approximation of LRU!

Queueing Theory:

• You should be able to analyze Markovian systems (e.g., M/M/1 and M/M/1/K systems). Know how to draw a state transition diagram of a given system (e.g., a multiprogramming system or a system of interactive terminals), and compute state probability distribution and performance measures (resource utilization, throughput, response time, etc.). Know Little's law and how to apply it.

/