2017/FinalTopics

From CS61
Jump to: navigation, search

Final Topics

Data Representation and Storage

  • Describe some ways that the abstraction provided by the C language is similar to and different from the abstraction provided by the underlying machine.
  • Explain the difference between a program and a process.
  • Visualize how memory is arranged in a process.
  • Write simple programs to help you answer questions about how memory is arranged in a process.
  • Identify what program behavior is governed by C and what is governed by lower layers of abstraction.
  • Explain how and why optimized and unoptimized code can behave differently.
  • Explain the representations underlying different data types in a C program.
  • Recognize common hex numbers.
  • Look at a hex number and have a sense of where it is in the address space.
  • Add/subtract hexadecimal numbers.
  • Define the following terms (with respect to C):
    • Object
    • Declaration
    • Definition
    • Use size_t, ssize_t appropriately
  • Use pointer arithmetic correctly.
  • Explain how C data types arranged in memory:
    • Sizes
    • Alignment
    • Endianness
    • Convert between binary, decimal, and hexadecimal
  • Explain how both fundamental and derived data types are laid out in memory
  • Write code that places things in memory how you want them
  • Explain how to encode both positive and negative numbers in binary
  • Add and subtract binary numbers
  • Explain why 2’s complement is a good representation
  • Explain the purpose of dynamic memory
  • Define the terms arena, heap
  • Identify common errors involving dynamic memory
  • Explain how dynamic memory allocations are aligned
  • Comfortably manipulate hidden meta-data structures.
  • Comfortably build simple functions to a specification.
  • Explain the relationship between a language with explicit malloc/free and one that uses garbage collection.
  • Build a simple garbage collector for C.
  • Demonstrate the impact that the quality of a dynamic memory allocation library can have on application performance.
  • Implement a simple fixed-size allocator
  • Explain how your allocator could be a piece of a more comprehensive allocator
  • Explain what undefined behavior is and know when it can occur
  • Understand how to avoid undefined behavior.
  • Use sanitizers to debug undefined behavior.

Assembly and Machine Programming

  • Explain what assembly language is
  • Define:
    • Registers
    • Instruction
    • Operands
  • Produce C program from assembly
  • Read x86-64 assembly containing arithmetic and logical operators.
  • Be comfortable reading assembly that manipulates data of different sizes.
  • Use gdb and objdump to examine the assembly underlying a C function/program
  • Read simple assembly
  • Know what registers are available in x86-64 assembly and their general use cases.
  • Become comfortable with the typeless nature of assembly
  • Interpret different modes of addressing in x86-64 assembly.
  • Interpret test and cmp instructions.
  • Explain the different flags in the x86-64 architecture, how they get set and how they get used.
  • Follow an assembly program’s control flow
  • Read and understand assembly programs using a wide range of addressing modes
  • Read and understand assembly programs with a variety of control flow instructions
  • Tackle (parts of) Assignment 2!
  • Define stack frame and the calling convention.
  • Understand which registers are callee saved and which are caller saved.
  • Explain how the assembler sets up the stack for execution of a function.
  • Locate parameters and local variables on the stack.
  • Explain how understanding how programs use memory and being able to read assembly creates opportunities to wreak havoc.
  • Explain how compilers (and possibly other tools) help protect you/programs from nefarious behavior.

Standard I/O and Caches

  • Define memory hierarchy.
  • Evaluate the performance differences found at the different layers of the hardware memory hierarchy.
  • Explain the different kinds of caching that processors and hardware systems perform to mitigate the performance differences between the levels of the memory hierarchy.
  • Develop intuition about how caching of various types affects program performance
  • Explain how caching is used at different layers of the I/O path to improve performance
  • Identify location of common caches in the IO path.
  • Discuss issues particular to write caches
  • Understand what streams and random-access files are and how to use them.
  • Define:
    • Block size
    • Cache block
    • Cache slot
    • Cache hit/miss rate
    • Replacement policy
    • Write-back
    • Write-through
    • Cache consistency
  • Explain how read performance changes in the presence of a cache
  • Observe the effects of the different caches available in libraries and the operating system

Build a simple read cache.

  • Simulate different cache replacement policies
  • Given a workload, a cache size, and a replacement policy, calculate hit/miss rates
  • Given hit/miss rates and the performance of different levels of the memory hierarchy, compute average access times.
  • Use mmap (and its associated calls).
  • Explain the relationship between mmap and caching.
  • Discuss the pros and cons of using mmap.
  • Demonstrate how access patterns affect performance
  • Determine how C arrays are allocated in memory
  • Modify programs to produce more cache friendly code
  • Use strace.

Kernel Programming and Virtual Memory

  • Explain what virtual memory is and, conceptually, how it works.
  • Explain what process isolation is, why it is important, and how virtual memory helps us achieve it
  • Identify the different mechanisms that processor hardware uses to help provide process isolation
  • Define “dangerous” instructions and tell whether an instruction is dangerous
  • Identify the different mechanisms that the operating system kernel uses to provide process isolation
  • Describe how the operating system kernel and processor hardware work together
  • Define protected control transfer
  • Define exception
  • Distinguish the three kinds of exception: traps, faults, and interrupts
  • Explain what support hardware must provide to enable virtual memory.
  • Describe what an MMU does and how hardware helps with the MMU function
  • Given mapping tables, translate between virtual and physical addresses manually
  • Manipulate addresses to extract various fields
  • Reason about various trade-offs in virtual memory systems
  • Be able to talk about page faults and why they might occur
  • Explain how control transfers between user-level processes and the kernel
  • Be able to write code that handles virtual memory for fork
  • Explain the impact of recursion on memory consumption
  • Design ways to limit a process’s stack consumption.
  • Explain what the fork system call does from both an application programming perspective and an operating system perspective
  • Explain the copy-on-write concept
  • Be comfortable with debugging on WeensyOS

Shells and Process Management

  • Explain how processes are created
  • Create new processes, synchronize with them, and communicate exit codes back to the forking process.
  • Know how exec works and be able to write code using it
  • Start building a simple shell
  • Manually set up pipelines
  • Understand how conditionals are used in a shell
  • Use pipes comfortably to:
    • Communicate between parents and children
    • Communicate between sibling processes
    • Be prepared to convert from manually constructing pipelines to doing so in your shell.
  • Redirect standard in and standard out
  • Implement proper pipe and file descriptor hygiene.
  • Use errno and system call return values to catch and distinguish error conditions.
  • Develop/identify test programs that will help you debug your shell
  • Write signal handlers
  • Write code that uses signal handlers
  • Explain the difference between blocking and polling.
  • Discuss the tradeoffs between blocking and polling.
  • Discuss how to use blocking system calls to coordinate processes.
  • Be able to use utilization as a metric to measure system efficiency.
  • Use the system calls related to sending signals.
  • Explain the select system call.
  • Read man pages and use them to determine how a system call or library function should be used.

Synchronization and Concurrency

  • Define thread and understand how it differs from a process
  • Identify possible race conditions in code
  • Develop solutions that avoid race conditions
  • Define:
    • Mutual exclusion
    • Critical section
    • Race condition
    • Deadlock
    • Starvation
  • Use mutexes and CVs to solve simple synchronization problems, bathroom-themed or not
  • Be comfortable using the pthreads APIs to:
    • create threads
    • wait for threads
    • synchronize threads
  • Explain what mutexes and CVs are and know when you might want to use them
  • Explain the relationship between mutexes and CVs
  • Explain how hardware helps us implement synchronization
  • Atomic instructions
  • Explain how synchronization problems arise and what bad things can go wrong.
  • Use pipes to synchronize between two processes
  • Identify race conditions when we need to both wait and test a condition.

Networking

  • Know how to use sockets, including how to use a socket to set up connection both clientside and serverside
  • Define:
    • Client
    • Server
    • Protocol
    • RPC (Remote Procedure Call)
  • Be able to send HTTP requests and receive the server’s response
  • Know how to make your client robust to delays or lost connections
  • Modify an existing server to efficiently handle multiple connections
  • Apply what we learned about synchronization to manage our server
  • Define denial of service attacks.
  • Apply defensive coding practices to make your server immune to a DOS attack like the one launched by wdbblaster