Topics for the Final Exam in COP 3402 $Date: 2023/04/12 23:19:54 $ This examination covers topics related to homework assignments 3-4. REMINDERS This test will be for the period scheduled for the final exam (10 AM to 12:50 PM in the usual classroom: PSY 108) and will be closed book. However, you may use one (1) page of notes on one (1) side of a standard 8.5 by 11 inch sheet of paper. These notes can either be hand-written or printed, but if printed, then the font must be a 9-point or larger font. These notes must be turned in with the exam. READINGS See the required textbook (Systems Software by Montagne) chapters 3 and 5-10. See also the course lecture notes, which are available from the course resources webpage (see http://www.cs.ucf.edu/~leavens/COP3402/resources.shtml#course). CONCEPTS/TOPICS Topics marked + below are more important than topics marked - below, which are less important (but were mentioned in the class). Topics marked ++ are very important. Topics marked -- are very unimportant. In general, conceptual questions, and questions that connect topics, techniques, examples, and ideas will be more important than details; the exam may be somewhat of a different flavor than the homework sets. * Basic Terminology It's important to know and understand these terms, so that you understand the questions and can write sensible answers. ** Compilers *** semantic analysis and symbol tables + What is a symbol table? ++ What role does the symbol table play in a compiler? + What kind of information should be remembered for each declaration? Why? + What is an attribute? What kind of information is stored in attributes? + What kind of errors are caught in declaration checking? What is an example of each kind in PL/0? + What is a scope? + What is the scope of a declaration in C? - What is a "forward declaration"? How are they used in C? + Does each scope have its own symbol table? ++ What is a scope? What is a scope in PL/0? In the FLOAT language? In C? + What is a symbol table? What operations would it support? ++ How is a symbol table used to check declarations and uses of identifiers? *** Code generation **** general concepts - What is an IR? What is it used for in a compiler? - What are the advantages of using an IR in code generation? + What information from a name's use is needed to generate code? - How practical would it be for a parser to determine the lexical address of a name that is used in a program with nested procedures? + Which part of the lexical address of a constant or variable can be easily determined by the parser? + What is the general way that the code for a code generator is written? + What does it mean for code to "follow the grammar"? + How are ARs used on the runtime stack? **** expressions + Why are identifier uses important for code generation? + How is the lexical address of a variable (or constant) used to generate code? + What does the generated code for obtaining the value of a variable (or constant) look like in the stack machine? + Where does compiled code put the value of an expression in the stack machine? **** declarations + How are constant declarations translated into machine code in the stack machine? + How are variable declarations translated into machine code? + Where are globally visible constants and variables allocated? **** statements + How are assignment statements compiled? What code do they generate? + How are if-then-else statements compiled? What code do they generate? - How could the addresses used in compiling if-statements be computed? + Would labels (as in HW4) be useful if the machine's jump instructions all required absolute addresses? How would that idea work? + How are while-loops compiled? What code do they generate? **** procedures + How are procedure declarations compiled? + How is the starting address of a procedure obtained by a call instruction? + Why does the runtime stack need to be trimmed before executing a return instruction? How is that done in the stack VM? + With static scoping, what does the BP register point to in an AR for a nested scope? ** Assembly Language + What is an assembly language? + What are the goals of assembly language? ++ How does assembly language differ from a (high-level) programming language? ++ How does an assembler differ from a compiler? + How does an assembler translate forward jumps (to a label)? ** ELF + What is ELF? + What are the sections of an ELF file? What information is in each section? + How does relocation of executable files work? + Are executable files the same in every operating system? + Are executable files the same for every machine (ISA)? ** linkers and loaders *** linkers ++ What is a linker? What does a linker do? + Why is a linker useful for programming? + How does a linker support separate compilation? + How does a linker support program libraries? ++ What is the difference between static linking and dynamic linking? + Which kind of linking is used to link together the compiled files of a user's program? + Which kind of linking is performed to link a user's program to a shared library? *** loaders ++ What is a loader? What does a loader do? + What are the types of loaders? When is each type used? - If we are using a computer with virtual memory, do we still need a relocating loader? ** Operating System (OS) + What are the goals of an operating system? + What are the main techniques that are used to implement an OS? - What are some ways to organize the code in an OS? - What are the advantages and disadvantages of different ways of organizing an OS? + What would happen if an OS was just a bunch of libraries? *** processes ++ What is a process? + Why does an OS have processes? + What are the advantages of the process concept for programming? + How does a process differ from a program? + How does a program become a process? + What states can a process be in? How does it change from one to another? - What is a PCB? What information does it typically store? - Where do a process's permissions come from? - What is a PAS? + What information needs to be saved when suspending a process? *** interrupts + How does an OS enable sharing of resources? + What is needed for an OS to enforce sharing policies? + What is an interrupt? + Why are interrupts needed? + Why is an interrupt handling mechanism a useful idea in an OS? - When does a CPU notice interrupts? + What are the different kinds of interrupts? + What is a trap interrupt? + What does an interrupt handler do? + Why does an interrupt handler need to save the state of the running process? + What is an I/O interrupt? How does it differ from a trap interrupt? - What hardware is needed to handle interrupts? + What is a timer interrupt? Why is it needed? - How could an OS can handle multiple interrupts that occur at the same time? + What is a trap table (aka an interrupt vector)? + What software controls the contents of the interrupt vector? Is that crucial? *** limited direct execution ++ What is limited direct execution? How does it work? + What is needed from the hardware (the ISA) to make limited direct execution work? + What are the differences between user mode and kernel mode? + Describe the kinds of instructions can only be executed successfully in kernel mode. + Why is it useful to have the ISA distinguish between user mode and kernel mode? + What mode (user or kernel) does the system's boot loader run in? + What mode does an OS run in? + What mode does an interrupt handler run in? *** system calls + What is a system call? + How are system calls implemented in an OS? + If a user mode process cannot execute privileged instructions how can it do any I/O? + Is your program's process executed in kernel mode? + If your program is doing I/O, does that mean that the process you are running is executing privileged instructions? - What does a system call function need to do about security? + What is memory protection? Why is it needed? + What does a "segmentation fault" mean for a C program? - What is a PSW? Why is it useful in an OS? *** threads + What is a thread? Why is it a useful concept for an OS? + Does each thread need its own stack? - What is the difference between apparent concurrency and true concurrency? + What is a race condition? Why are race conditions a problem? - Can a system with apparent concurrency have race conditions? + What is a critical section? Why is it important? + What is mutual exclusion? How is it used in concurrent programming? + What is serial execution? Why is it useful? + What is atomic execution? Why is that a useful concept? + What are some mechanisms for safely synchronizing programs? * Skills When a question refers to a programming language, the language will either be described in the question (especially for questions related to grammars and parsing) or it will be C or the PL/0 language. ** Addressing and Subroutines - Determine the lexical address of a local variable in a PL/0 program - Draw before and after pictures showing the effect of call and return instructions on the run-time stack in a VM ** abstract syntax trees (ASTs) + Write C code to create an AST during parsing + Write C code to walk over an AST (e.g., to check for duplicate declarations) ** Static Analysis + Determine if a program has duplicate declarations + Determine if a program has undeclared identifier uses ** Compilers + Be able to write code to traverse an AST and check declarations and identifier uses (given some helping functions) + Be able to write code to traverse an enhanced AST and generate stack machine code (given some helping functions)