Topics- Variable declarations and definitionsPrinceton University COS 217: Introduction to Programming Systems Spring 2009 Final Exam Preparation Topics You are responsible for all material covered in lectures, precepts, assignments, and required readings. This is a non-exhaustive list of topics that were covered. Topics that were covered after the midterm exam are in boldface. 1. Number Systems • The binary, octal, and hexadecimal number systems • Finite representation of integers • Representation of negative integers • Binary arithmetic • Bitwise operators 2. C Programming • The program preparation process: preprocess, compile, assemble, link • Program structure: multi-file programs using header files • Process memory layout: text, stack, heap, rodata, data, bss sections • Data types • Variable declarations and definitions • Variable scope, linkage, and duration/extent • Constants: #define, constant variables, enumerations • Operators and statements • Function declarations and definitions • Pointers; call-by-reference • Arrays: arrays and pointers, arrays as parameters, strings • Command-line arguments • Input/output functions • Text files • Structures • Dynamic memory mgmt.: malloc(), calloc(), realloc(), free() • Dynamic memory mgmt. errors: dangling pointer, memory leak, double free • Abstract data types; opaque pointers • Void pointers • Function pointers and function callbacks • Parameterized macros and their dangers (see King Section 14.3) 3. Programming-in-the-Large • Testing o External testing taxonomy: boundary condition, statement, path, stress o Internal testing techniques: testing invariants, verifying conservation properties, checking function return values, changing code temporarily, leaving testing code intact o General testing strategies: testing incrementally, comparing implementations, automation, bug-driven testing, fault injection • Debugging heuristics Page 1 of 4o Understand error messages, think before writing, look for familiar bugs, divide and conquer, add more internal tests, display output, use a debugger, focus on recent changes • Program and programming style o Top-down design • Data structures and algorithms o Linked lists, hash tables, memory ownership • Module qualities: o Separates interface and implementation, encapsulates data, manages resources consistently, is consistent, has a minimal interface, reports errors to clients, establishes contracts, has strong cohesion, has weak coupling • Generics o Generic data structures via void pointers, generic algorithms via function pointers, wrappers • Building o Automated builds, dependencies, partial builds • Portable programming o General heuristics o Heuristics related to differences in hardware, operating systems, compilers, libraries, and cultures • Performance improvement techniques o Optimize only when and where necessary o Improve asymptotic behavior Use better data structures or algorithms o Improve execution time/space constants Coax the compiler to perform optimizations Exploit capabilities of the hardware Capitalize on knowledge of program execution 4. Under the Hood: Toward the Hardware • Computer architectures and the IA-32 computer architecture o The Von Neumann architecture o Control unit vs. ALU o Little-endian vs. big-endian byte order o Language levels: high-level vs. assembly vs. machine • Assembly languages and the IA-32 assembly language o Directives (.section, .asciz, .long, etc.) o Mnemonics (movl, addl, call, etc.) o Jump instructions and condition codes o Instruction operands: immediate, register, memory o Memory addressing modes: direct, indirect, indexed, base pointer o The stack and local variables o The stack and function calls: the C function call convention • Machine language o Opcodes o The ModR/M byte o The SIB byte o Immediate, register, memory, displacement operands • Assemblers o The forward reference problem o Pass 1: Create symbol table o Pass 2: Use symbol table to generate data section, rodata section, bss section, text section, relocation records • Linkers o Resolution: Fetch library code o Relocation: Use relocation records and symbol table to patch code Page 2 of 45. Under the Hood: Toward the Operating System • Virtual Memory o The memory hierarchy: registers vs. cache vs. memory vs. local secondary storage vs. remote secondary storage o Locality of reference o Page faults • Dynamic memory management o Memory allocation strategies o Free block management o Optimizing malloc() and free() • Unix system calls o For process control The process abstraction The process lifecycle Context switches The getpid(), execvp(), fork(), and wait() system calls The exit() and system() functions o For interacting with the file system The stream abstraction The open(), creat(), close(), read(), write(), and lseek() system calls o For inter-process communication The dup(), dup2(), and pipe() system calls • Unix signals o Sending signals via keystrokes, the kill command, and the raise() and kill() functions o Installing signal handler functions: the signal() function o Ignoring signals o Race conditions o Blocking signals: the sigaction() and sigprocmask() functions • Unix alarms and timers o The alarm() function o The setitimer() function 6. Applications • De-commenting • Lexical analysis via finite state automata • String manipulation • Symbol tables, linked lists, hash tables • Dynamically expanding arrays • Buffer overrun attacks • Unix shells 7. Tools: The Unix/GNU programming environment • Unix, Bash, Emacs, GCC, GDB for C, GDB for assembly language, Gprof, Make Page 3 of 4Readings As specified by the course "Schedule" Web page. Readings that were assigned after the midterm exam are in boldface. Required: • C Programming (King): 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 22 • Computer Systems (Bryant & O'Hallaron): 1, 3 (OK to skip 3.14 and 3.15), 8, 10 • Communications of the ACM "Detection and Prevention of Stack Buffer Overflow Attacks" • The C Programming Language (Kernighan & Ritchie) 8.7 Recommended: • Computer Systems (Bryant & O'Hallaron): 2, 5, 7, 11 • The Practice of Programming (Kernighan &
View Full Document
Unlocking...