Systems Examinations

1. Breadth Exam

1.1 Format

The Breadth examination in Systems is a 3-hour written examination covering a set of core topics in basic operating system concepts and machine architecture/organization, plus a subset of the following:

  • Databases
  • Distributed/Advanced Operating Systems
  • Networks
  • Compilers
  • Programming Languages

Each student taking the exam shall select, prior to taking the exam, two of the above areas to be covered in addition to the core.

To pass the breadth exam, the student must demonstrate understanding of the area-specific concepts, terminology, techniques, algorithms and well-known solutions, and the ability to apply them in their usual context.

Note well: You must pass the Core component to pass the Systems Breadth exam. That is, you cannot pass the Systems Breadth if you score highly on other components while failing the core.


1.2 Syllabi

1.2.1 Core: Machine Organization, Basic Operating Systems

 

Textbooks

Applied Operating System Concepts, Silberschatz, Galvin and Gagne, John Wiley & Sons, 2000. ISBN: 0-471-36508-4
Any undergraduate architecture book, e.g. Computer Architecture, by Hennessey and Patterson.

  • [PH] Computer Organization and Design: The Hardware/Software Interface, Second Edition, David Patterson and John Hennessy, Morgan Kaufmann, August 1997, ISBN: 1-55860-428-6
  • [Tan] Structured Computer Organization, Third Edition, Andrew S. Tanenbaum, Prentice Hall, 1990, ISBN 0-13-854662-2
  • [SGG] Operating System Concepts, 6th Edition Abraham Silberschatz, Peter Baer Galvin, Greg Gagne John Wiley, June 2001, ISBN: 0-471-41743-2

 

Topics

[PH] [Tan] [SGG]
Hardware Basics:
Combinational Logic
Gates
Flip Flops/Latches
Sequential Circuits
Registers
Memory
Clocks
Appendix B Ch 2.1.-2.2
Ch 3.1-3.3
Ch 4.1
Instruction Design
Machine cycles
Instruction Sets
Addressing Modes
Number Representation/Arithmetic
Ch. 2.3
Ch. 3
Ch. 4
Ch. 5.2-5.5
Storage and Peripherals
Interrupts
Memory Hierarchy
Virtual Memory
Buses
Direct Memory Access
Device Characteristics
Device I/O
Ch. 5.6, A.7
Ch. 7
Ch. 8
Ch. 3.4
Ch. 3.6
Ch. 6.1
Ch. 10
Ch. 13
Process Synchronization
Critical Regions
Mutual Exclusion
Locks
Semaphores
Monitors
Ch. 6.3 Ch. 7
Ch. 8
Scheduling
Round Robin
First Come First Served
Shortest Job First
Ch. 6
Storage Hierarchies
Registers/Caches
Virtual Memory
Paging/Segmentation
Page Replacement Algorithms
File Systems
Ch. 7 Ch. 6.2 Ch. 9
Ch. 10 Ch. 11 Ch. 12

 


1.2.2 Databases

 

Textbooks

  • [RAMG] Database Management Systems by Ramakrishnan, Gherke (2nd ed.), 2000, McGraw Hill
  • [SKS] Database System Concepts by Silberschatz, Korth, Sudershan (4th Edition), 2002, McGraw Hill
  • [GMUW] Database Systems: The Complete Book by Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer D. Widom (1st Ed.), 2001, Prentice Hall

 

Topics -- Part 1: CS 405 Material (2 problems)

[RAMG] [SKS] [GMUW]
Entity-Relationship Model
Entities Attributes
Entity Set Relationships
Relationship Sets
Conceptual DB design using ER Model
Ch. 2 Ch. 3 Ch. 2
Relational Model
Keys, integrity constraints,
Translating ER diagrams to
Relational databases,
Views, updates
Ch. 4 Ch. 3 Ch. 3
Relational Algebra/Calculus
Select/Project/Join Set operations
Domain relational calculus
Tuple relational calculus
Ch. 4 Ch. 3 Ch. 5
SQL
Data Definition Language
INSERT statement
SELECT statement
Nested queries, aggregate operators
Ch. 3,5
Ch. 3
Ch. 3
Ch. 5
Ch. 5
Ch. 4




Ch. 6
Data Storage
Disks, RAID
Buffers and buffer management
Files and file systems
Ch. 7,8
Ch. 7
Ch. 7
Ch. 8
Ch. 11



Ch. 11
Indexing
Heaps, hash tables, hashing
B+ trees
Ch. 8,9,10
Ch. 8,10
Ch. 9
Ch. 12


Ch. 13
Query Evaluation/Optimization
Access paths for selection, projection
Join, set operations
Query equivalence, Query evaluation plans
Cost models, cost estimation
Ch. 12, 13
Ch. 12
Ch. 12
Ch. 13
Ch. 13
Ch. 13, 14
Ch. 13
Ch. 13
Ch. 14
Ch. 14
Ch. 15
Normal Forms
Schema refinement
Functional dependencies
Boyce-Codd Normal Form
Third normal form
Lossless join decomposition
Ch. 15 Ch. 7 Ch. 3

Topics -- Part 2: CS 505 Material (1 problem)

[RAMG] [SKS] [GMUW]
Transaction Management
Transactions, transaction schedules
concurrent execution, serializability
Ch. 18 Ch. 15 Ch. 19
Concurrency control
Lock-based control, strict 2-phase locking
Ch. 19 Ch. 16 Ch. 18
Crash Recovery
ARIES, logs, checkpointing
Recovering from a systems crash
Ch. 20 Ch. 17 Ch. 17
Security in Databases
Access control
Ch. 17 Ch. 6
Object-Database Systems
Structured types
Inheritance
Object-relational databases
Object-oriented databases
Ch. 25




Ch. 8,9


Ch. 9
Ch. 8
Ch. 4

 


1.2.3 Distributed/Advanced Operating Systems

 

Textbooks

  • [S&S] Singhal and Shivaratri, Advanced Concepts in Operating Systems, McGraw Hill, 1994;
  • [SIN] Sinha, Distributed Operating Systems Concepts and Design, IEEE Computer Society Press, 1997, ISBN - 0-7803-1119-1;
  • [T&S] Tanenbaum and Steen, Distributed Systems Principles and Paradigms, Prentice Hall, 2002.

 

Topics

[S&S] [SIN] [T&S]
Synchronization
Language mechanisms: monitors, serializers,
communicating sequential processes, Ada rendezvous
Distributed mutual exclusion
Distributed deadlock detection
Clock synchronization
2.1--2.6, 6.1--6.14, 7.7, 7.8 6.2 5.1
Distributed shared memory
Design and implementation of DSM systems
Consistency models
5.1 -- 5.11
Distributed file systems
File accessing models
File-sharing semantics
Caching schemes
Replication
Fault tolerance
9.1 -- 9.8 10.1, 10.2
Distributed scheduling
Algorithms for distributed scheduling
11.1 -- 11.12
Theoretical foundation
Lamport's clocks, Vector clocks
Global snapshots, recovery
Causal ordering
5.1 -- 5.8
Database Operating systems
Concurrency control algorithms
Lock-based algorithms
Timestamp-based algorithms
20.1 -- 20.4
Communication-kernel based operating systems
Message-passing semantics
Server processes
Distributed V kernel, Mach.
12.3, 12.4

 


1.2.4 Networks

 

Textbooks

 

  • [P&D] Larry L. Peterson and Bruce S. Davie, Computer Networks: A Systems Approach, second edition, Morgan Kaufman Publishers, 2000.

 

Topics

 

[P&D]
Channels and signals
Channel types
signal encoding
bandwidth and latency
Ch. 1, 2
1.1
2.1
1.1.4,2.2
Link layer
Framing
Multiplexing
Error detection
Reliable transmission
Medium access control methods
Ch. 1, 2
2.3
1.1.2
2.4
2.5
2.6, 2.7, 2.8
Network layer
Virtual circuits/datagrams
Internet Protocol
routing (static/adaptive)
congestion control
Ch. 3, 4, 6
3.1
4.1
4.2,4.3
6.1
Transport layer
UDP, TCP
Connection management, flow control
Van Jacobson congestion control
Ch. 5, 6
5.1, 5.2
6.3
Miscellaneous
Protocol design and implementation
Presentation coding
Security

1.2.1, 1.3
7.1, 1.2
8.1, 8.2, 8.3, 8.4

 

 


 

1.2.5 Compilers

 

Textbook

  • [ASU] A. V. Aho, R. Sethi, J. D. Ullman, Compilers: Principles, Techniques, and Tools, Addison-Wesley, 1986.

 

Topics

 

[ASU]
Lexical analysis
Regular expressions, finite automata
Specification of tokens
Ch. 3
Syntax analysis
Context-free grammars and their properties
BNF and EBNF notations
Parse trees and derivation process
First and Follow sets
Top-down parsing by recursive descent
LL(1) parse tables
bottom-up parsing including SLR(1) parse tables
Ch. 4
Syntax-directed translation
Inherited and synthesized attributes
Attribute grammars
Ch. 5
Semantic analysis
Scoped symbol tables
Type checking
Ch. 6, Section 7.6
Storage organization and runtime environments
Activation records (frames)
Stack of activation records
Chains of static and dynamic links
Access to local and non-local variables
Heaps and dynamically allocated objects
Ch. 7, Section 9.3
Intermediate code generation
Syntax trees
Forms of intermediate codes
Code generation for expressions
Control-of-flow and function statements
Basic optimization methods
Ch. 8, 9, Section 10.1, 10.2
Miscellaneous
Compiler-compiler tools
Interpreters
Register allocation
Garbage collection
Bootstrapping
Ch. 1, 11, Section 7.7, Section 9.7

 

 


 

1.2.6 Programming Languages

 

Textbook

[FIN] R. Finkel, Advanced Programming Language Design, Addison-Wesley, 1995.

 

Topics

 

[FIN]
Classical Algol-like languages
Expressions
Control constructs
Procedures and parameter passing
Block structure
Runtime store organization
Ch. 1
1.3
Coroutines and CLU iterators Ch. 2
2.2
Types
Static vs. dynamic typing
Name and structural type equivalence
Abstract data types
First-class procedures
Generic packages, polymorphic types.
Ch. 1, 3
1.3.1
3.1, 3.2, t.3., 3.5, 3.6, 3.7.6
Functional programming
Static vs. dynamic scope
Deep vs shallow binding
Metacircular interpretation
Lazy evaluation
Lisp
Ch. 4
4.1, 4.4
Object-oriented programming
Classes and objects, variables and methods
Inheritance
Interfaces
Java, C++, Smalltalk.
Ch. 5
Concurrent programming
Multiple threads
Conditional critical regions
Monitors
Remote procedure invocation
Ada rendezvous
Cooperation by messages
Communicating Sequential Processes
Ch. 7
Logic programming
Terms, predicates, and queries
Backtracking inference engine
Negation
Prolog
Ch. 8
8.1

 


2. Depth Exam

The depth exam in Systems tests depth of knowledge and understanding in a particular sub-area of systems. The exam consists of two parts: a written test over papers in the literature of the student's chosen area, and a presentation covering the student's chosen research topic. The student wishing to sit for the depth examination shall, with the assistance of his/her advisor and other faculty in the chosen sub-area, agree upon a set of papers for the student to read and be tested over in the written part, and a time for the examination. The written exam will last not more than three hours.

To pass the depth exam, the student must demonstrate, in addition to familiarity with basic concepts and solutions, the ability to transfer knowledge between problems and extend solutions to new areas.

The presentation part of the exam is intended to show that the student can express technical ideas clearly and precisely. The student shall prepare a one-hour talk on the student's chosen research topic. This talk will be presented to the student's depth committee and the general public.