Contents

Textbooks

Electronic options are available for all required sources. At least one physical copy of each text is also available in the physical SCI L037 CS Systems Lab for use within the CS department area. Please use them in the data lab area and return them to the shelf when you are done. If using these shared physical books, please wash your hands before and after. (WWW)

We use one primary textbook extensively:

Other textbooks are used during the first part of the course:

We recommend a good reference on the C programming language. Here are a couple solid options:

Additional materials will be posted directly on the course website.

Preparing for Class Meetings

Before each class meeting, complete the required preparation steps listed in the topics for the day. Preparation varies from day to day, but usually consists of some combination of watching videos, reading, or trying small exercises, and asking or answering questions in the 0xF0rum. Expect the preparation to take more than a few minutes. The preparation is just as important as synchronous class activities themselves, which often build on ideas encountered in assigned preparation material.

How to watch videos for CS 240

Many topics will have videos attached. When asked to watch these videos for preparation, or if you use them for reference at any time:

  • You can view them on YouTube (nocookie version without tracking) or download/watch the MP4 files directly.
  • Take notes like you would in class.
  • You might find it helpful to download a copy of the slides to follow along or take notes.
  • It’s fine to pause and take breaks whenever you want!
  • You do not need to watch all the videos from one topic or even all the videos assigned for one day of preparation in one sitting. The videos are usually broken up into chunks usually between 5 and 15 minutes length, occasionally a little shorter or longer.
  • When the talking head says to “try this,” pause the video to freeze the talking head in a bizarre pose, then actually try the example, just like you would in class when we do an exercise together.

How to read for CS 240

Effective reading for computer science courses demands a staged approach. Aim for two types of reading:

Before class, do an initial reading of the any reading material assigned as preparation for class.

Do not worry about understanding every last detail.

Do aim to acquire:

  • A big-picture view of the pieces we will consider about this topic.
  • Some familiarity with basic mechanics of the ideas introduced.

To help distinguish core points from secondary concerns during initial reading, each reading is listed with one of two style directives:

  • Read means read for enough detail to do indicated reading exercises. If you do get stuck or confused by some details, do not worry. Make a note and move on. If we do not clear up your confusion in class, ask a question or come to office hours.
  • Skim means read for high-level ideas. Perhaps pick out a couple details that look interesting and accessible. Do not spend much time trying to understand all the details before moving on.

Learning how to identify essential vs. inessential details during a first reading is an important skill that takes time to develop. As the semester progresses, we will leave more of this to you.

Readings assignments may indicate specific exercises to try as you read before class. These are typically practice problems from the reading.

  • Try means work through enough of the exercise to see how the basics work. Do not feel obligated to finish every example. Do what is useful to you. (Do not submit anything.)

We typically highlight exercises that practice mechanics. Feel free to try other practice problems as well. They may require more time and critical thinking. We will explore such interesting examples in class.

After class, revisit readings in more depth and try more practice problems to work out details as needed.

More advice for reading

Our main text (CSAPP) sometimes goes into more detail than we will cover, so learning to “read around” extra detail is a useful skill, especially in your pre-class reading.

When reading from CSAPP:

  • “Asides” are optional. If you read them, skim them.
  • “New to C?” blocks can be useful, but usually only if they are short.
  • Some sections (e.g., 2.2 - 2.4 on integer and floating point representations) can be too dense for our purposes. We try steer you around them, but if you find other things getting dense, flip to another reading or just make a note and jump ahead.
  • This book really shines with later material about machine/assembly language, caching, memory management, and other topics. We use it intermittently in the first section of the course, then extensively for the latter two.

Tia Newhall (Swarthmore College) has more good advice on reading computer science textbooks.

Material by Topic

This list of topics includes:

  • Topics covered in class meetings, with preparation directions listings of all lecture materials, associated readings, and activities.
  • Topics covered in lab that are normally covered in lecture in full-semester versions of CS 240. We include all readings and lecture materials for lectures in full-semester versions of CS 240. Labs do not necessarily use all of this material, but we include for reference.
  • +Optional items that offer opportunities to explore further, but are not required.

Data as Bits and Computation as Digital Logic

The Plan

Preparation Before Class

Welcome to CS 240! Your first synchronous CS 240 activities will be a lab meeting on Monday, followed by a class meeting on Tuesday. Many of our meetings will be preceded by some asynchronous preparation, including these first meetings! Usually lab preparation and materials will be provided separately by Jean on the lab page. For the first round, we are gathering everything together here. Please complete the following preparation in advance.

Before your first lab meeting on Monday:

  1. Watch video 1 for this topic in the “Materials” section just below.
  2. Complete the first lab assignment by watching this playlist of three “Computer Science Crash Course” videos about computing history and basic electronic building blocks for digital computation. (You will work with these in the first lab.)
  3. Bookmark and tour the main CS 240 course website, your central source for all course info and materials.
  4. Sign up for the CS 240 “0xF0rum” (powered by Zulip), our primary means of online communication, using the invitation link sent in the initial course email message. Asynchronous course communication will happen there (not email).
  5. Post a brief message in the intros topic of the #community stream on the CS 240 0xF0rum to introduce yourself with:
    • your name;
    • your pronouns; and
    • something that brought you joy since the end of last term/semester.
  6. Review the SCI L037 access map to plan your arrival for lab!

Before your first class meeting on Tuesday:

  1. Watch videos 2-3 for this topic (listed just below, in “Materials”) to wrap up course motivation.
  2. Skim reading 3 (listed just below, in “Materials”) for general background on the working of modern computers.
  3. Review the CS 240 course website and logistics/policies page.
    • Video 4 tours the website.
    • Video 5 covers other logistics and policies if you prefer a guided tour to complement reading the full text. (Maybe play this at double speed or use it as a sleep aid.)
  4. Complete the appropriate preparation steps listed in all other topics that appear in Tuesday’s course calendar entry. Like this topic, all other lecture topics linked from the calendar include a listing of the required preparation steps to complete ahead of each class meeting.

Questions? Post them in the 0xF0rum. (If you are unable to sign up, email the instructor ASAP.)

Materials

Slides: ➊ plan.pdf ➍ plan-4up.pdf

Videos: YouTube☰ yt playlist The Plan

  1. ▸ mp4 YouTube yt What is CS 240?
  2. ▸ mp4 YouTube yt Basic Computer Model
  3. ▸ mp4 YouTube yt Why take CS 240?
  4. ▸ mp4 YouTube yt How does CS 240 work? Website Tour
  5. ▸ mp4 YouTube yt How does CS 240 work? Logistics and Policies

Readings:

  1. Read: About CS 240 (syllabus and policies)
  2. Read: Lab policies
  3. Skim: CSAPP 1.0 - 1.7, 1.9.2 - 1.10

Digital Logic (lab-only)

Lab-only: The Digital Logic topic is covered only in lab. These materials are provided for optional reference in addition to the lab materials.

Materials

Exercises:

Slides: ➊ gates.pdf ➍ gates-4up.pdf

Readings:

Data as Bits

Preparation Before Class

For Tuesday:

  1. Reading 1 (below)
  2. Watch videos or read (or both):
    • Videos 1-5 (below)
    • Readings 2-3 (below)

Note that the YouTube viewing option may be useful if you wish to watch faster or slower.

For Wednesday:

  1. Optional review of material covered live in preceding class meeting: videos 6-9
  2. New preparation: videos 10-11 and 13
  3. Also see prep for the next topic, which also begins on Wednesday.

Follow up after class by reviewing Readings 3-4.

Materials

Exercises:

Slides: ➊ bits.pdf ➍ bits-4up.pdf

Videos: YouTube☰ yt playlist Data as Bits

  1. ▸ mp4 YouTube yt Positional Number Representation and Binary
  2. ▸ mp4 YouTube yt Conversion Between Binary and Decimal
  3. ▸ mp4 YouTube yt Binary Arithmetic
  4. ▸ mp4 YouTube yt Bytes and Hexadecimal
  5. ▸ mp4 YouTube yt Fixed-size Data Types
  6. ▸ mp4 YouTube yt Bitwise Operators
  7. ▸ mp4 YouTube yt Bitwise Operator Practice
  8. ▸ mp4 YouTube yt Bit Sets
    Errors:
    • The ~a set complement example should be ~b. The slides have been updated.
  9. ▸ mp4 YouTube yt Boolean Logical Operators
  10. ▸ mp4 YouTube yt Card Encoding Ideas
  11. ▸ mp4 YouTube yt Compact Encodings with Bit Fields and Masks
  12. Mask Practice (see exercise above)
  13. ▸ mp4 YouTube yt Bit Shifting
  14. ▸ mp4 YouTube yt Shift-and-Mask Puzzle
  15. ▸ mp4 YouTube yt Shift-and-Mask Review

Readings:

  1. Preparing for Class Meetings in CS 240, including tips for effective watching and reading.
  2. Binary and hexadecimal number systems
  3. Information as bits + context
    • Read: CSAPP 2 - 2.1.2
    • Skim: CSAPP 2.1.4 - 2.1.5.
  4. Bitwise Boolean algebra and bit manipulation
    • Read: CSAPP 2.1.6 - 2.1.9 (including the Asides.)
    • Optional: K&R 2.7, 2.9 for C reference

Integer Representation

Preparation Before Class

This topic is critical for the Bits assignment!

For Wednesday:

  1. Videos 1-3

For Friday:

  1. Review addition and overflow if needed: videos 5-6
  2. New material: videos 7-10

For Tuesday:

  1. Review shifts as arithmetic (video 11) and see how this can accomplish general multiplication (videos 12-14).
  2. See notes on converting between types (video 15).
  3. Complete the fixed-sized integer exercises and review the solutions. Post any questions on the 0xF0rum so we can resolve integer questions there. Tuesday’s class meeting will start with the next topic.

For later reference, consult remaining videos and readings.

Materials

Exercises:

Slides: ➊ integers.pdf ➍ integers-4up.pdf

Videos: YouTube☰ yt playlist Integer Representation

  1. ▸ mp4 YouTube yt Unsigned Representation, Modular Arithmetic, Overflow
  2. ▸ mp4 YouTube yt Sign-Magnitude Representation
  3. ▸ mp4 YouTube yt Two's Complement Representation
  4. ▸ mp4 YouTube yt Two's Complement Examples
  5. ▸ mp4 YouTube yt Two's Complement Addition
  6. ▸ mp4 YouTube yt Two's Complement Overflow
  7. ▸ mp4 YouTube yt Overflow and Reliability
  8. ▸ mp4 YouTube yt Two's Complement is Awesome, Complement Rules
  9. ▸ mp4 YouTube yt Deriving Two's Complement
  10. ▸ mp4 YouTube yt Sign Extension
  11. ▸ mp4 YouTube yt Shift Arithmetic
  12. ▸ mp4 YouTube yt Shift and Add
  13. ▸ mp4 YouTube yt Shift and Add Puzzle Review
  14. ▸ mp4 YouTube yt Muliplication
  15. ▸ mp4 YouTube yt Converting Between Unsigned and Signed Types

Readings:

Refer to this material only after videos/class. We’d like to introduce signed integer representations before you read about them.

As you read, focus on the positional representation of signed integers more than the mechanics of how to convert from integer representation to the representation you know well.

  1. For the basics, read one of:

  2. Then, for reference on integer multiplication and division, their relation to bitwise operations, and sign extension:

    • Skim: CSAPP 2.2.4 - 2.2.8.
    • Read: CSAPP 2.3.4-2.3.8

Combinational Logic (lab-only)

Lab-only: The Combinational Logic topic is covered only in lab. These materials are provided for optional reference in addition to the lab materials.

Materials

Slides: ➊ mux.pdf ➍ mux-4up.pdf

Readings:

Karnaugh Maps

Multiplexers and decoders

+Floating Point Number Representation (optional)

+Optional: This topic is an optional opportunity for further depth or exploration.

Materials

Slides: ➊ floats.pdf ➍ floats-4up.pdf

Readings:

  • Skim one of:
  • If you want more detail (e.g., on denormalization as discussed in class, or many in-depth examples), read CSAPP 2.4.

Processor Building Blocks and the Memory Model

Arithmetic Logic (lab-only)

Lab-only: The Arithmetic Logic topic is covered only in lab. These materials are provided for optional reference in addition to the lab materials.

Materials

Slides: ➊ alu.pdf ➍ alu-4up.pdf

Readings:

Adders

  • Read one of:
    • DDCA 5.1 - 5.2.1 (pages 233-234) up through Ripple Carry Adders (feel free to skim beyond if you are curious, ignore Verilog and VHDL)
    • SCO 3.2.3 (Arithmetic Circuits)
    • Digital Circuits: Adders up until Carry Lookahead Adder (feel free to skim beyond if you are curious)

Arithmetic Logic Unit

  • Read one of these to understand the high-level organization of an ALU. We will look at details of a specific ALU design in class.

Programming with Memory

Preparation Before Class

For Tuesday:

  1. Videos 1-6. Expect to have some questions. This usually takes some repetition.

Tuesday class will spend time on Pointer Exercises Part 1.

For Wednesday:

  1. As needed, review arrays and pointer arithmetic with videos 7-11 or readings.
  2. Wrap up Part 1 of the Pointer Exercises exercises from class and review solutions. Work with your partner(s) from the previous class if possible. Video 12 can help if you are a little stuck.

Wednesday class will spend time on Pointer Exercises Part 2.

For Friday:

  1. Wrap up at least the contains_char functions from Part 2 of the Pointer Exercises exercises from class. (Skip substring.) Work with your partner(s) from the previous class if possible. You do not need to submit this.
  2. Videos 16-19: allocating memory in the heap

Follow-up:

  1. Videos 20-21: memory bugs and perspective on C
  2. Readings and other reference below for alternative perspectives on the same ideas.

Materials

Exercises:

Slides: ➊ memory.pdf ➍ memory-4up.pdf

Videos: YouTube☰ yt playlist Programming with Memory

  1. ▸ mp4 YouTube yt Byte-Addressable Memory
  2. ▸ mp4 YouTube yt Multi-Byte Values in Memory
  3. ▸ mp4 YouTube yt Data, Addresses, Pointers
  4. ▸ mp4 YouTube yt C Variables as Memory Locations
  5. ▸ mp4 YouTube yt C Pointer Primitives
  6. ▸ mp4 YouTube yt C Pointer Example
  7. ▸ mp4 YouTube yt C Arrays
  8. ▸ mp4 YouTube yt C Arrays and Pointers
  9. ▸ mp4 YouTube yt C Pointer Arithmetic
  10. ▸ mp4 YouTube yt C Array Sizing
  11. ▸ mp4 YouTube yt C Array Expression Examples
  12. ▸ mp4 YouTube yt Pointer Exercises Intro
  13. ▸ mp4 YouTube yt C Strings
  14. ▸ mp4 YouTube yt C Strings as char* and Cursor Pointer Style
  15. ▸ mp4 YouTube yt C 0, '\0', and NULL
  16. ▸ mp4 YouTube yt Memory Address Space Layout
  17. ▸ mp4 YouTube yt C Memory Allocation with malloc/free
  18. ▸ mp4 YouTube yt C Arrays of Pointers to Arrays
  19. ▸ mp4 YouTube yt zipCount Review
  20. ▸ mp4 YouTube yt C scanf and Memory Errors Teaser
  21. ▸ mp4 YouTube yt Why C?

Readings:

General memory model:

  • +Optionally, read: SCO 2.2.2 - 2.2.3, 5.1.2 (stop at “Note that having separate address spaces for instructions and data”)
  • Read: CSAPP 2.1.0, 2.1.3 - 2.1.4

Mix and match to start learning about addresses and pointers in C:

+Reasoning about Programs (optional)

+Optional: This topic is an optional opportunity for further depth or exploration.

Materials

Slides: ➊ assertions.pdf ➍ assertions-4up.pdf

Readings:

In most semesters, we do not have time to cover this topic in lecture, but we ask you to skim these resources.

For later:

Sequential Logic (lab-only)

Lab-only: The Sequential Logic topic is covered only in lab. These materials are provided for optional reference in addition to the lab materials.

Materials

Slides: ➊ registers.pdf ➍ registers-4up.pdf

Readings:

The Instruction Set Architecture Model

x86 Basics

Preparation Before Class

For Friday:

  • Video 1

For Tuesday:

Mix and match videos or readings (whichever you prefer) to understand basics of x86, registers, data movement instructions, the lea (load effective address) intruction, and basic stack instructions.

  • Videos 2-6.
  • Readings 1-3.

Follow-up for Wednesday:

Please review #1 and #2 from the exercises (see videos 8-9) and try out exercises #3. (Feel free to try #4 as well, not required.) Still uncertain about details? Try some practice problems from CSAPP (suggestions below with Readings).

Materials

Exercises:

Slides: ➊ x86-basics.pdf ➍ x86-basics-4up.pdf

Videos: YouTube☰ yt playlist x86 Basics

  1. ▸ mp4 YouTube yt Intro and History
  2. ▸ mp4 YouTube yt Registers, Data Movement Instructions, and Memory Addressing Modes
  3. ▸ mp4 YouTube yt Memory Examples
  4. ▸ mp4 YouTube yt Memory Addressing Review
  5. ▸ mp4 YouTube yt Load Effective Address (lea)
  6. ▸ mp4 YouTube yt Procedure Call Stack Basics
  7. ▸ mp4 YouTube yt Arithmetic and Logic Instructions, arith Exercise Setup
  8. ▸ mp4 YouTube yt arith Exercise Review, logical Exercise Setup
  9. ▸ mp4 YouTube yt logical Exercise Review

Readings:

  1. Background

  2. Data Movement

    • Read: CSAPP 3.3 - 3.4 (including “New to C?” to help remember those pointers…)
    • Suggested Exercises: try CSAPP practice problems 3.1, 3.2. Take a look at practice problem 3.5, but don’t spend too long on it. We’ll try more like this in class.
  3. Load Effective Address:

  4. Arithmetic

    • Read: CSAPP 3.5 - 3.5.4
    • Suggested Exercises: try CSAPP practice problems 3.8, 3.9. (Note x <<= 4; is the same as x = x << 4;.)
    • Skim: CSAPP 3.5.5
  5. x86 Machine Diagram

A Simple Processor (lab-only)

Lab-only: The A Simple Processor topic is covered only in lab. These materials are provided for optional reference in addition to the lab materials.

Materials

Slides: ➊ arch.pdf ➍ arch-4up.pdf

Readings:

Read for general organization and design points about instruction set architecture and microarchitecture. We will build our own toy architecture in class and lab.

  • Read: Central Processing Unit (Operation section)
  • +Optionally, read: SCO 2.1 - 2.1.2, 2.2.2, 5.1 - 5.1.2 (stop at “Note that having separate address spaces for instructions and data”), skim 5.1.3 - 5.1.4
  • Alternatives:
    • Read: CSAPP 1.4.1, 2.1.0
    • DDCA 7.3-7.3.3 (alt. ebook) describes a similar microarchitecture for a similar 32-bit ISA, but relies on some detail from an extensive discussion of instruction set architecture in Chappter 6. Our coverage will be more cursory.

x86 Control Flow

Preparation Before Class

For Wednesday:

Please also see the follow-up in the x86 basics prep.

  • Videos 1-2.
  • Readings 1-2.

For Friday:

  • Review if-else (up through video 4).
  • Learn about loops (video 5 or reading 3).
  • Check out videos 6-8 or reading 4. These will be relevant for a part of the x86 project, but the prep to start the procedures topic is more important for making this class meeting useful.

Materials

Exercises:

Slides: ➊ x86-control.pdf ➍ x86-control-4up.pdf

Videos: YouTube☰ yt playlist x86 Control Flow

  1. ▸ mp4 YouTube yt Condition Codes, Comparisons, and Tests
  2. ▸ mp4 YouTube yt Jumps, Translating If-Else, and absdiff Exercise Setup
  3. ▸ mp4 YouTube yt absdiff Exercise Review, goto, and If Compilation Exercise Setup
  4. ▸ mp4 YouTube yt If Compilation Exercise Review and PC-Relative Addressing
  5. ▸ mp4 YouTube yt Translating Loops
  6. ▸ mp4 YouTube yt Conditional Moves
  7. ▸ mp4 YouTube yt Translating Switch Statements with Jump Tables
  8. ▸ mp4 YouTube yt Translating Switch Statement Cases, Reverse Engineering Switches

Readings:

  1. Comparisons, Tests, and Jumps

    • Read: CSAPP 3.6 - 3.6.4
    • Suggested Exercises: Try CSAPP practice problems 3.13 - 3.14. Just consider what operator you’d put in place of COMP or TEST to match the assembly code. (Don’t worry about #define etc. if you don’t remember how macros work.)
  2. Translating if conditionals

    • Read: CSAPP 3.6.5
    • Suggested Exercises: CSAPP practice problem 3.16
  3. Translating loops

    • Read: CSAPP 3.6.7
    • Suggested Exercises: CSAPP practice problems 3.23, 3.24
  4. Translating switch statements

    • Skim: CSAPP 3.6.8, 3.6.6
  5. x86 Machine Diagram

The Procedure Call Stack Model and Data Layout

x86 Procedures, Call Stack

Preparation Before Class

For Friday:

No prep required before class. We will hit the highlights of these things; the videos/readings cover additional details that may be helpful.

  • Videos 1, 2.
  • Reading 1

For Monday Lab and Tuesday Class:

Watch or read:

  • Videos 3-4 for review. Videos 5-6 to get a taste before Monday. (Also useful for lab and definitely useful for later phases in the x86 assignment.)
  • Reading 2

Materials

Exercises:

Slides: ➊ x86-procedures.pdf ➍ x86-procedures-4up.pdf

Videos: YouTube☰ yt playlist x86 Procedures, Call Stack

  1. ▸ mp4 YouTube yt The Call Stack Stores Procedure Context
  2. ▸ mp4 YouTube yt Procedure Control Flow Instructions (call/ret), Data Flow Conventions, Puzzle Setup
  3. ▸ mp4 YouTube yt Procedure Puzzle Review
  4. ▸ mp4 YouTube yt Procedure and Stack Frame Example
  5. ▸ mp4 YouTube yt Register Saving Conventions, Callee-Save Example
  6. ▸ mp4 YouTube yt Recursion Example
  7. ▸ mp4 YouTube yt Stack Storage Example, Procedure Summary

Readings:

  1. Read: CSAPP 3.7 - 3.7.4
  2. Read: CSAPP 3.7.5 - 3.7.6
  3. x86 Machine Diagram

Representing Data Structures

Preparation Before Class

For Wednesday:

Watch or read:

  • Videos:
    • Video 1 (review arrays at the x86 level)
    • Videos 5-6 (basics of C structs)
    • Video 7 (linked list example)
  • Readings 1, 3, 4.

For Friday:

Watch or read:

  • Videos 2-4 (multi-level and nested arrays)
  • Reading 2

Materials

Exercises:

Slides: ➊ data-structures.pdf ➍ data-structures-4up.pdf

Videos: YouTube☰ yt playlist Representing Data Structures

  1. ▸ mp4 YouTube yt Simple Arrays
  2. ▸ mp4 YouTube yt Multi-Level Arrays (Arrays of Pointers to Arrays of...)
    Errors:
    • In the copyleft example, all occurrences of 4 in the x86 code should be replaced by 8.
  3. ▸ mp4 YouTube yt Row-Major Multidimensional Arrays
  4. ▸ mp4 YouTube yt Row-Major Array Review
  5. ▸ mp4 YouTube yt Structs
  6. ▸ mp4 YouTube yt Struct Alignment
  7. ▸ mp4 YouTube yt Linked List Representation

Readings:

  1. Read: CSAPP 3.8.1 - 3.8.2 (review simple arrays)
  2. Read: CSAPP 3.8.3 - 3.8.4 (nested arrays)
  3. Read: CSAPP 3.9 (heterogeneous data structures)
  4. Read: CSAPP 3.10.1 (pointer review)
  5. x86 Machine Diagram

Buffer Overflows

Preparation Before Class

For Thursday Lab

Mix and match videos and readings to understand buffer overflows:

  • Videos 1-6
  • Reading 1

For Friday:

  • Video 7

Materials

Exercises:

Slides: ➊ buffer.pdf ➍ buffer-4up.pdf

Videos: YouTube☰ yt playlist Buffer Overflows

  1. ▸ mp4 YouTube yt Overview
  2. ▸ mp4 YouTube yt Stack Layout and No Bounds Checking in C
  3. ▸ mp4 YouTube yt Example Overview
  4. ▸ mp4 YouTube yt Example 1 - Overwrite Padding (Lucky)
  5. ▸ mp4 YouTube yt Example 2 - Corruption and Segfault
  6. ▸ mp4 YouTube yt Example 3 - Silent Corruption and Arbitrary Code Execution
  7. ▸ mp4 YouTube yt Remote Code Execution and Avoiding Vulnerabilities

Readings:

  1. Read: CSAPP 3.10.3-3.10.4
  2. x86 Machine Diagram

The Memory Hierarchy, Cache, and Memory Allocation

Memory Allocation

Preparation Before Class

For Tuesday:

Videos or readings:

  • Videos 1-3
  • Reading 1

For Wednesday:

Videos or readings:

  • Review videos 2-6, readings 1-2 for details of implicit free lists
  • Video 11 (block format for the Malloc assignment)

For the Malloc assignment:

  • Videos 10-11
  • If exploring explicit free lists: videos 7-9, reading 3

Materials

Slides: ➊ malloc.pdf ➍ malloc-4up.pdf

Videos: YouTube☰ yt playlist Memory Allocation

  1. ▸ mp4 YouTube yt Allocator Basics
  2. ▸ mp4 YouTube yt Determining Block Size
  3. ▸ mp4 YouTube yt Block Format and Heap Layout
  4. ▸ mp4 YouTube yt Implicit Free List Search
  5. ▸ mp4 YouTube yt Implicit Free List Allocation and Splitting
  6. ▸ mp4 YouTube yt Implicit Free List Freeing and Coalescing
  7. ▸ mp4 YouTube yt Explicit Free Lists
  8. ▸ mp4 YouTube yt Explicit Free List Search, Allocation, and Splitting
  9. ▸ mp4 YouTube yt Explicit Free List Freeing and Coalescing
  10. ▸ mp4 YouTube yt Seglists and Allocation Summary
  11. ▸ mp4 YouTube yt Malloc Assignment - Block Format
    Errors:

Readings:

  1. Read: CSAPP 9.9 - 9.9.5 (basics)
  2. Read: CSAPP 9.9 - 9.9.12 (implicit free lists)
  3. Read: CSAPP 9.9.13 - 9.9.14 (explicit free lists and beyond)
  4. Skim: CSAPP 9.10 - 9.11 (garbage collection, C memory errors)

Memory Hierarchy, Cache

Preparation Before Class

For Friday:

Mix and match videos or readings as you prefer, to learn about the memory hierarchy, locality, cache mechanics and organization, and direct-mapped caches:

  • Videos 1-4
  • Reading 1.

If you missed discussion of 2D nested arrays earlier, you may want to review Video 3 or Reading 2 from the data structures topic.

For Tuesday:

  • Videos 5-8 (partly covered in class Friday)
  • Videos 9-10, 13

Materials

Exercises:

Slides: ➊ cache.pdf ➍ cache-4up.pdf

Videos: YouTube☰ yt playlist Memory Hierarchy, Cache

  1. ▸ mp4 YouTube yt Motivating Example
  2. ▸ mp4 YouTube yt Cache Overview
  3. ▸ mp4 YouTube yt Cache Mechanics
  4. ▸ mp4 YouTube yt Locality
  5. ▸ mp4 YouTube yt More Locality Examples
  6. ▸ mp4 YouTube yt Cache Performance and the Hierarchical Memory Design
  7. ▸ mp4 YouTube yt Cache Organization
  8. ▸ mp4 YouTube yt Cache Blocks
  9. ▸ mp4 YouTube yt Direct-Mapped Cache Placement Policy and Cache Tags
  10. ▸ mp4 YouTube yt Address Fields
  11. ▸ mp4 YouTube yt Why Not Another Direct Mapping (Aside)
  12. ▸ mp4 YouTube yt Cache Puzzle 1
  13. ▸ mp4 YouTube yt Cache Conflicts and Associative Cache Placement Policies
  14. ▸ mp4 YouTube yt Cache Puzzle 2
  15. ▸ mp4 YouTube yt General Cache Dimensions and Organization
  16. ▸ mp4 YouTube yt General Cache Read Mechanics
  17. Cache Analysis Example 1: Spatial Locality in Direct-Mapped Caches
  18. Cache Analysis Example 2: Cache Conflicts in Direct-Mapped Caches
  19. Cache Analysis Example 3: Cache Conflicts Resolved by Associativity
  20. Types of Cache Misses
  21. Cache Write Policies
  22. Cache-Friendly Code and Summary

Readings:

  1. Memory Hierarchy, Locality, General Cache Mechanics, Direct-Mapped Caches
  2. Associative Caches, Cache Policies, and Performance
  3. Cache-Friendly Code

The Process Model and Virtual Memory

Exceptional Control Flow

Preparation Before Class

No preparation.

Materials

Slides: ➊ ecf.pdf ➍ ecf-4up.pdf

Readings:

Process Model

Preparation Before Class

No preparation.

Materials

Slides: ➊ process.pdf ➍ process-4up.pdf

Readings:

  • Read: CSAPP 1.7, 8.2 - 8.4

+Shells, Signals (optional)

+Optional: This topic is an optional opportunity for further depth or exploration.

Materials

Slides: ➊ shell.pdf ➍ shell-4up.pdf

Virtual Memory

Materials

Slides: ➊ virtual-memory.pdf ➍ virtual-memory-4up.pdf

Readings:

Beyond 240