Transcript Exam Review - monismith.info

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