Operating Systems Exam Review and Course Overview

Exam Review cs550 Operating Systems

Preliminary Information Exam will focus on new content, but old content is still fair game. Exam format will be the same and of similar length to the previous exams. Remember, if you score better on this exam than you did on one of the previous exams, the final exam score will replace the worse of those two scores. We have built upon much of our old content in getting to the new content.

Overview Topics covered in this class included: UNIX/Linux command line tools C programming MPI and POSIX (pthreads) Threads Libraries for C Processes and Threads Synchronization Deadlock Scheduling File Systems Memory Management Cache and Cache Coherency IO Systems Protection and Security (briefly)

Processes and Threads Understand and be able to describe the Ready, Run and Blocked States. Understand the definitions of processes and threads and how they may be represented programmatically (pthreads and MPI). Be able to write programs that make use of threads and processes. Be able to describe and recognize synchronization errors such as race conditions and fix them.

Synchronization Be able to understand, describe, and use synchronization primitives. Semaphores Mutex Locks and Condition Variables Atomic Variables Be able to write and describe pseudocode for the following example of synchronization Readers/Writers Problem Producer-Consumer Problem

Implementations of Processes and Threads Be able to write MPI code using the following primitives Rank (Process Id) Size (Number of processes) Blocking Send and Receive Non-Blocking Send and Receive Barriers Be able to write threaded code and make use of synchronization primitives Know how to create, join, and terminate threads Know how to make use of shared variables

CPU Scheduling Know scheduling policies FCFS First Come First Served SJF Shortest Job First SRTN Shortest Remaining Time Next RR Round Robin Know that others exist too (Dynamic/RT scheduling) Know about CPU Bursts, Time Slices, and how the Scheduler works with the Ready and Run States

Know parts of Scheduler Know parts of scheduler Dispatcher Context Switcher Enqueuer Know preemptive vs. non-preemptive Know Gantt charts and scheduling performance Know about multilevel queues and multiple processor scheduling

Synchronization Concepts Mutual Exclusion Critical sections Race conditions Semaphores Mutex Locks and Condition Variables Interprocess communication Atomic Transaction and Monitors Implementations (Know pseudocode for these!) Producers Consumers with Semaphores Readers Writers with Semaphores

Deadlock Know how to draw a resource allocation graph. Be sure to label multiple requests for the same resource on the exam. Know the conditions for deadlock Circular wait Hold and wait Mutual Exclusion No preemption Know the Dining Philosphers example of deadlock and at least one programmatic way to fix it by preventing deadlock.

Handling Deadlock Prevention ensure Deadlock does not exist by removing one of the four conditions for deadlock. Avoidance Utilize the Banker's algorithm to ensure a safe state exists before allowing processes to proceed. Detect and Recover Allow deadlock to occur, but use a heuristic or algorithm to detect it, then if a deadlock has occurred, then use a graph algorithm to determine which processes are in a circular wait, and rollback to a safe state. Ignore Deadlock Ignore deadlock and require the user or system administrator to either kill off processes or reset the system.

File Systems and Management Know the definition of a file and a directory and understand file permissions Understand file I/O primitives - read, write, open, close Understand file file pointers and the use of standard in/out Fragmentation and free space management Understand the difference between various types of file systems FAT/FAT32 (Non-journaling) NTFS (Journaling, Windows-based) Ext4 (Journaling, Linux-based) Lustre a parallel file system for linux that makes use of metadata storage, object storage servers, and object storage targets Understand file system mounting and unmounting Understand the importance of DMA (Direct Memory Access)

Disk Drives and Management Disk drive parts Platter, arm, spindle, head, tracks, sectors, blocks Disk I/O Scheduling FCFS Shortest Seek Time First (SSTF) Elevator (SCAN) Circular Scan

Cache Understand the importance of cache Understand Cache-Coherent Non-Uniform Memory Access Understand cache coherence methodologies Snooping Snarfing Understand the importance of cache misses with respect to paging and thrashing

Memory Management Partitions Contiguous vs Non-contiguous allocation Frames Pages Segments Fragmentation Process address space Swapping memory Virtual Memory Understand the Translation Lookaside Buffer

Paged Memory Paging policy Fetch Demand Prepaging Replacement Policies LRU FIFO Optimal

I/O Systems I/O Hardware and Buses (e.g. PCI and Daisy Chaining) I/O Ports, Polling, and Algorithm for Data Transfer Interrupts and Interrupt Requests Direct Memory Access Blocking and Non-blocking I/O Asycnhronous System Calls Spooling Kernel Data Structures Know the definition of an iNode (See I/O Systems notes)

Security and Protection (Chpt 14) Know that protection is an internal OS problem and that there are various mechanisms and policies for OS protection Read about the principle of least privilege in Chpt 14 Domains know that these consist of both hardware and software objects Know the definition and parts of the Access Matrix Global table Access Lists Capability Lists Read about access control