Transcript CS 519: Operating System Theory

Final exam details
December 22, 2009. 12pm-3pm. Venue: SEC 118.
Tips:
Spend time reading the questions before answering them.
Prioritize the questions and answer questions in an order that will
ensure that you maximize your score
Rutgers University
1
CS 416: Operating Systems
I/O
Blocking, non-blocking, and asynchronous I/O. Differences?
Pros and cons?
Buffered and unbuffered I/O. Differences? Pros and cons?
Programmed I/O and DMA. Differences? Pros and cons?
Steps in performing a DMA operation?
Steps in performing an I/O operation?
Rutgers University
2
CS 416: Operating Systems
Disks and Disk Management
Structure. Sectors, tracks, cylinders?
Performance. Seek latency, rotational latency, transfer rate?
Disk scheduling. FCFS, SSTF, SCAN, C-SCAN, LOOK, CLOOK? Pros and cons?
RAID. Different RAID levels? Pros and cons?
Rutgers University
3
CS 416: Operating Systems
File Systems
File allocation. Contiguous, linked, indexed? Pros and cons?
Free space management. Bit map, chained, indexed? Pros and cons?
Buffer cache. How does it work? Consistency? Replacements?
File sharing semantics. Unix, session, immutable files?
Protection. Protection domains? Access control lists, capabilities? Pros and
cons?
Rutgers University
4
CS 416: Operating Systems
Security
Buffer overflow vulnerabilities. Stack smashing attacks. Tricks to
make stack smashing attacks work in practice (see Aleph One
paper and slides).
Techniques to prevent buffer overflow attacks.
Rutgers University
5
CS 416: Operating Systems
Distributed Systems
Fault models. Failstop, crash, Byzantine?
Consensus and coordinated attack results. Why are they impossible?
Communication protocols. Layering? Function of application, transport,
network, and link/physical layers? Examples?
Internet protocols. IP, UDP, TCP? TCP flow control? TCP congestion
control?
RPC. Goal? Stubs? Deviations from regular PC? Semantics?
Transactions. ACID? Two-phase locking and commit?
Distributed algorithms. Happened before? Mutual exclusion algorithms?
Properties?
Material on distributed file systems will NOT be on the final.
Rutgers University
6
CS 416: Operating Systems
Architecture
Caching. Why? Examples? When does it work well?
Invoking the OS. Mechanisms? Differences?
I/O event notification. Mechanisms? Differences?
Send/receive data to I/O devices. Mechanisms? Differences?
Rutgers University
7
CS 416: Operating Systems
Processes and Threads
Stack. Activation records. What is stored there?
Heap. What is stored there?
Address space. What is it?
Process context. Thread context. What do they comprise?
PCB. TCB. Where are they stored? What do they store?
Context switching. How does it happen? Any problems?
Thread states.
User-level and kernel-level threads. Pros and cons?
Rutgers University
8
CS 416: Operating Systems
Synchronization
Critical section. Locks. Semaphores. Monitors.
Atomic operations. Examples?
Spinning vs. blocking. Tradeoff?
Deadlock. Necessary conditions? Techniques for tackling
deadlocks?
Banker’s algorithm.
Rutgers University
9
CS 416: Operating Systems
CPU Scheduling
Metrics: thruput, utilization, turnaround, response time, deadlines
Preemption.
Policies: FCFS, SJF, RR, Priorities, Feedback. Pros and cons.
Rutgers University
10
CS 416: Operating Systems
Memory Management
Paging. Segmentation. How do they work? Pros and cons?
Translation Lookaside Buffer. How does it work? How are misses handled?
Translation from logical (virtual) to physical address. How?
Page tables. Where are they stored? What can we do to reduce their size?
Page replacement policies: FIFO, LRU, Optimal, 2nd chance, Nth chance.
Working set. Thrashing. Swapping.
Rutgers University
11
CS 416: Operating Systems
File systems
File system implementation. Layout and management of disk
pages.
Inodes and directory entries. UNIX-like inodes.
Managing free space. Bitmaps and free lists.
File system consistency semantics.
Log-structured file system implementation. Tradeoffs and design
criteria. Segment cleaning mechanisms and policies. Tradeoffs.
Rutgers University
12
CS 416: Operating Systems