📚 Topics
Contents
- Textbooks
- Preparing for Class Meetings
- Material by Topic
- Computational Building Blocks
- Hardware-Software Interface
- Abstractions for Practical Systems
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.
We use one primary textbook extensively:
- CSAPP 3e (Wellesley online access):
Computer Systems: A Programmer’s Perspective, 3/E. (3rd edition, significant changes since 2nd)
Bryant and O’Hallaron, Pearson, 2016. ISBN-13: 9780134092669.- We need the 3rd edition. See the errata.
- Unfortunately, the library is not able to acquire an electronic
version, but there are several options to access the book,
including, but not limited to:
- If you prefer physical books, paperback copies are available for much less than the hardcover version. “Global” 3rd editions mostly work, but have some additional errors (not listed on the errata page).
- 6 months of access to an electronic version is available for $35.
- During difficult pandemic circumstances, we have scans of the relevant excerpts available for CS 240 students (Wellesley ONLY). Being scans, these excerpts are not quite as good quality as some other electronic or paper options.
- Please contact the instructors if none of the available options work for you.
Other textbooks are used during the first part of the course:
- DDCA (Wellesley online access):
Digital Design and Computer Architecture.
Harris and Harris, Morgan Kaufmann, 2007.
We recommend a good reference on the C programming language. Here are a couple solid options:
- Essential C (PDF)
Nick Parlante, 2003. Stanford University. - K&R:
The C Programming Language, 2nd edition.
Kernighan and Ritchie, Prentice Hall, 1988. ISBN-13: 978-0131103627, ISBN-10: 0131103628.
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. Expect the preparation to take more than a few minutes. Synchronous class activities will build on ideas in 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:
- Do an initial reading in preparation for the class when the topic is scheduled.
- Revisit the reading later for deeper details or reference.
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 and listings of all lecture materials, associated readings, and activities.
- +Optional items that offer opportunities to explore further, but are not required.
The Plan
Preparation
Welcome to CS 240! Labs and lectures–including the first lab and lecture this week–are generally preceded by some asynchronous preparation to allow us to use meeting time productively. Please complete these steps in advance.
Before your first CS 240 lecture:
- Watch videos 1-3 for this topic (listed just below, in “Materials”) to understand the motivation for this course.
- Prepare for topics listed on the first day of lecture on the course calendar. Each lecture topic on the calendar links to a section on this page with preparation steps to complete ahead of lecture and materials for the topic.
By the end of the day of your first CS 240 lecture:
- Complete the intros assignment,
in which you will introduce yourself to your instructors,
learn about the course, and remind yourself how to connect
to
cs.wellesley.edu=tempest.wellesly.edu.
Before your first CS 240 lab:
- 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. For following labs, lab preparation and materials will be provided separately by Peter on the lab page.
- Bookmark and tour the main CS 240 course website, your central source for all course info and materials, and review course logistics and policies.
Before the end of this week:
- Skim reading 3 (listed just below, in “Materials”) for general background on the working of modern computers.
Materials
Slides: ➊ plan.pdf ➍ plan-4up.pdf
Videos:
☰ yt playlist
The Plan
Readings:
- Read: About CS 240 (syllabus and policies)
- Read: Lab policies
- Skim: CSAPP 1.0 - 1.7, 1.9.2 - 1.10
Computational Building Blocks
Digital Logic
Preparation
For Friday, Jan 27:
- Review basic digital logic gates and Boolean algebra notation from lab and lecture.
- Reading 1 (below)
For Tue, Jan 31:
- Carefully review slides 14-15 and do all the exercises along the way.
- In Tue’s lecture, we’ll go over any questions you have about these slides/exercises and complete these slides.
Materials
Exercises:
Slides: ➊ gates.pdf ➍ gates-4up.pdf
Readings:
Data as Bits
Tuesday 31 January (Lecture)Wednesday 1 February (Lab)Friday 3 February (Lecture)Tuesday 7 February (Lecture)
Preparation
For Tue Jan 31:
- Reading 1 (below)
- Watch videos 1–7
The YouTube viewing option may be useful if you wish to watch faster or slower.
During Class on Fri Feb 03:
We will work on this worksheet on Binary & Hex + Bitwise, Logical & Shift Operators in C
After Class:
- Follow up with videos on any remaining topics we did not cover in class.
- Flesh out the parts of the Binary & Hex + Bitwise, Logical & Shift Operators in C we did not finish in class, and compare your solutions with the SOLUTIONS doc.
- Review extra detail in Readings 2-4 as needed.
During Class on Tue Feb 07:
Class will begin by answering any lingering questions on this topic, especially questions on the Binary & Hex + Bitwise, Logical & Shift Operators in C worksheet and the accompanying SOLUTIONS.
Materials
Exercises:
- Basic Bit Exercises
- Basic Bit Exercises SOLUTION
- Mask and Shift Exercises
- Mask and Shift Exercises SOLUTION
- +Supplemental Bits Practice
- +Supplemental Bits Practice SOLUTION
Slides: ➊ bits.pdf ➍ bits-4up.pdf
Videos:
☰ yt playlist
Data as Bits
- ▸ mp4 yt Positional Number Representation and Binary
- ▸ mp4 yt Conversion Between Binary and Decimal
- ▸ mp4 yt Binary Arithmetic
- ▸ mp4 yt Bytes and Hexadecimal
- ▸ mp4 yt Fixed-size Data Types
- ▸ mp4 yt Bitwise Operators
- ▸ mp4 yt Bitwise Operator Practice
- ▸ mp4 yt Bit Sets
Errors:- The
~aset complement example should be~b. The slides have been updated.
- The
- ▸ mp4 yt Boolean Logical Operators
- ▸ mp4 yt Card Encoding Ideas
- ▸ mp4 yt Compact Encodings with Bit Fields and Masks
- Mask Practice (see exercise above)
- ▸ mp4 yt Bit Shifting
- ▸ mp4 yt Shift-and-Mask Puzzle
- ▸ mp4 yt Shift-and-Mask Review
Readings:
- Preparing for Class Meetings in CS 240, including tips for effective watching and reading.
- Binary and hexadecimal number systems
- Information as bits + context
- Bitwise Boolean algebra and bit manipulation
Integer Representation
Preparation
Before lecture on Tue Feb 7:
- Videos 1-9
During lecture on Tue Feb 7:
Refer to these Notes on Representing Information as Bits
After lecture on Tue Feb 7:
- Follow up with videos on any remaining topics we did not cover in
class, most likely including:
- Shifts as arithmetic (video 11) and how to compose them to accomplish general multiplication (videos 12-14).
- Converting between types (video 15).
- Complete the Fixed-Sized Integer Exercises and review their solutions. These are excellent practice to prepare for the two’s-complement puzzles in the Bits assignment.
- Review any other videos or readings as needed.
During lecture on Wed Feb 10: We continued to flesh out more exericises in these Notes on Representing Information as Bits
Materials
Exercises:
- Fixed-Size Integer Exercises
- Fixed-Size Integer Exercises SOLUTION
- +Supplemental Integers Practice
- +Supplemental Integers Practice SOLUTION
Slides: ➊ integers.pdf ➍ integers-4up.pdf
Videos:
☰ yt playlist
Integer Representation
- ▸ mp4 yt Unsigned Representation, Modular Arithmetic, Overflow
- ▸ mp4 yt Sign-Magnitude Representation
- ▸ mp4 yt Two's Complement Representation
- ▸ mp4 yt Two's Complement Examples
- ▸ mp4 yt Two's Complement Addition
- ▸ mp4 yt Two's Complement Overflow
- ▸ mp4 yt Overflow and Reliability
- ▸ mp4 yt Two's Complement is Awesome, Complement Rules
- ▸ mp4 yt Deriving Two's Complement
- ▸ mp4 yt Sign Extension
- ▸ mp4 yt Shift Arithmetic
- ▸ mp4 yt Shift and Add
- ▸ mp4 yt Shift and Add Puzzle Review
- ▸ mp4 yt Muliplication
- ▸ mp4 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.
-
For the basics, read one of:
- “Twos Complement” section of these notes. Stop at “Floating Point.”
- Fundamentals of Data Representation: Two’s Complement
- CSAPP’s treatment of number representation is more thorough, but
some students find it too dense and prefer to skip some parts.
- Read: CSAPP 2.2 - 2.2.3.
-
Then, for reference on integer multiplication and division, their relation to bitwise operations, and sign extension:
Combinational Logic
Preparation
Before lab on Wed Feb 08:
- Do Reading 2 on muxes and decoders.
Before lecture on Fri Feb 10:
- Do Reading 1 on Karnaugh maps.
After class on Fri Feb 10:
- Follow up with additional detail in Readings 1-2.
Materials
Slides: ➊ mux.pdf ➍ mux-4up.pdf
Readings:
- Karnaugh Maps: DDCA 2.7 (pages 71-79)
- Multiplexers and decoders: DDCA 2.8 (pages 79-84)
Arithmetic Logic
Preparation
Before lab on Wed Feb 08:
- Skim Reading 1
Before lecture on Tue Feb 14:
- Redo Reading 1 for details
Before lab on Wed Feb 15:
- Skim Reading 2
Before lecture on Fri Feb 17:
- Redo Reading 2 for details
Materials
Slides: ➊ alu.pdf ➍ alu-4up.pdf
Readings:
- Adders, one of:
- DDCA 5.1 - 5.2.1 (pages 233-240) up through Ripple Carry Adders (feel free to skim beyond if you are curious, ignore Verilog and VHDL)
- Digital Circuits: Adders up until Carry Lookahead Adder (feel free to skim beyond if you are curious)
- Arithmetic Logic Unit (high-level organization), one of:
- DDCA 5.2.2 - 5.2.4 (pages 240-244) up through Ripple Carry Adders (feel free to skim beyond if you are curious)
- Arithmetic Logic Unit sections “Signals” and “Circuit Operation”
We will look at details of a specific ALU design in class.
Sequential Logic
Tuesday 14 February (Lecture)Wednesday 15 February (Lab)Friday 17 February (Lecture)Friday 24 February (Lecture)
Preparation
Before lecture on Tue Feb 14:
- Skim Reading 1.
During lecture on Tue Feb 14: - Note: we didn’t have time to cover any material on Sequential Logic (latches, flip-flops, etc) on Tue Feb 14 and instead spent most of the lecture understanding the ALU architecture for Lab 04 on Wed Feb 15.
Before lab on Wed Feb 15:
- Redo Reading 1 for details
- Skim Reading 2 for a bit more on RAM.
Before lecture on Fri Feb 17:
- Redo Reading 2 for details
During lecture on Fri Feb 17: - Note: we didn’t have time to cover any material on Sequential Logic (latches, flip-flops, etc) on Wed Feb 17 and instead spent all of the lecture understanding assembly code for the HW Instruction Set Architecture (ISA) in preparation for for Lab 05 on on Wed Feb 22. - We’ll cover the Sequential Logic material in class on Fri Feb 24
During lecture on Fri Feb 24: Today we finally covered the Sequential Logic material in class.
Materials
Slides: ➊ registers.pdf ➍ registers-4up.pdf
Readings:
- Latches, Flip-Flops, Registers:
- DDCA 3.0 - 3.2.4 (pages 103-109)
- Note for context: In class, we use the terms leader and follower to describe the component latches of a D flip-flop. This textbook uses a different terminology that has been widely used in the past to describe flip-flops (and a handful of other computer systems concepts that CS 240 does not consider) by analogy to enslavement. We do not use that terminology in class. We ask that you also use the leader/follower terms.
- DDCA 3.0 - 3.2.4 (pages 103-109)
- Random Access memory (basics):
- Read DDCA 5.5 - 5.5.5 (pages 257-262) (ignore Verilog and VHDL). We will cover RAM only briefly.
A Simple Processor
Preparation
Before lecture on Friday Feb 17:
- Skim one option for Reading 1.
During lecture on Friday Feb 17:
We covered slides 1-11 of A Simple Processor and did the exercises on pp 8&9 and 10&11. The solutions to these exercises can be found in pp 8-11 of the solution slides.
Before lab on Wed Feb 22:
- Carefully study slides 5-11 and understand every detail.
- Skim slides 12-22
Before lecture on Fri Feb 24:
- Review slides 12-22. We will study them more in lecture
After lecture on Fri Feb 24:
- Carefully study slides 12-22 and understand every detail. Ask questions about what you don’t understand!
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 one of:
- Central Processing Unit (Operation section)
- CSAPP 1.4.1, 2.1.0
- DDCA 7.3-7.3.3 (pages 368-379) – describes a similar microarchitecture for a similar 32-bit ISA, but relies on some detail from an extensive discussion of instruction set architecture in Chapter 6. Our coverage will be more cursory.
+Floating Point Number Representation (optional)
+Optional: This topic is an optional opportunity for further depth or exploration.
Preparation
For Thursday
- No preparation
Materials
Slides: ➊ floats.pdf ➍ floats-4up.pdf
Readings:
- In Fall 2022, this topic is completely optional and will not be covered in lecture.
To learn more about this topic, skim one of:
- DDCA 5.3 (pages 249-253)
- SCO Appendix B
- If you want more detail (e.g., on denormalization as discussed in class, or many in-depth examples), read CSAPP 2.4.
Hardware-Software Interface
Programming with Memory
Tuesday 28 February (Lecture)Wednesday 1 March (Lab)Friday 3 March (Lecture)Tuesday 7 March (Lecture)Wednesday 8 March (Lab)Friday 10 March (Lecture)
Preparation
Tue Feb 28 During Class
We’ll cover the slides corresponding to much of the material from videos 1–15. You’ll get lots of practice with these concepts in Lab 6.
Fri Mar 03 During Class
We covered Programming with Memory slides 16-32 and the Memory/Pointer Notes and Examples.
Tue Mar 07 During Class
The plan is to cover (1) Programming with Memory slides 33-49 and (2) Notes on Strings + malloc & free
Fri Mar 10 During Class
Before starting x86 material, we’ll wrap up Programming with Memory material by covering this Pointers Assignement Exercise.
Materials
Slides: ➊ memory.pdf ➍ memory-4up.pdf
Videos:
☰ yt playlist
Programming with Memory
- ▸ mp4 yt Byte-Addressable Memory
- ▸ mp4 yt Multi-Byte Values in Memory
- ▸ mp4 yt Data, Addresses, Pointers
- ▸ mp4 yt C Variables as Memory Locations
- ▸ mp4 yt C Pointer Primitives
- ▸ mp4 yt C Pointer Example
- ▸ mp4 yt C Arrays
- ▸ mp4 yt C Arrays and Pointers
- ▸ mp4 yt C Pointer Arithmetic
- ▸ mp4 yt C Array Sizing
- ▸ mp4 yt C Array Expression Examples
- ▸ mp4 yt Pointer Exercises Intro
- ▸ mp4 yt C Strings
- ▸ mp4 yt C Strings as
char*and Cursor Pointer Style - ▸ mp4 yt C
0,'\0', andNULL - ▸ mp4 yt Memory Address Space Layout
- ▸ mp4 yt C Memory Allocation with
malloc/free - ▸ mp4 yt C Arrays of Pointers to Arrays
- ▸ mp4 yt
zipCountReview - ▸ mp4 yt C
scanfand Memory Errors Teaser - ▸ mp4 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:
- Read: CSAPP 3.10.1
- Read Pointer Basics and watch the silly video too.
- K&R 5 - 5.5
- The Descent to C
- The 5-minute Guide to C Pointers
+Reasoning about Programs (optional)
+Optional: This topic is an optional opportunity for further depth or exploration.
Preparation
No preparation.
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.
- How to use assertions in C, John Reekie.
- The benefits of programming with assertions (a.k.a. assert statements), Philip Guo.
For later:
- C Programming Tips, Philip Guo.
x86 Basics
Preparation
Materials
Exercises:
Slides: ➊ x86-basics.pdf ➍ x86-basics-4up.pdf
Videos:
☰ yt playlist
x86 Basics
- ▸ mp4 yt Intro and History
- ▸ mp4 yt Registers, Data Movement Instructions, and Memory Addressing Modes
- ▸ mp4 yt Memory Examples
- ▸ mp4 yt Memory Addressing Review
- ▸ mp4 yt Load Effective Address (lea)
- ▸ mp4 yt Procedure Call Stack Basics
- ▸ mp4 yt Arithmetic and Logic Instructions,
arithExercise Setup - ▸ mp4 yt
arithExercise Review,logicalExercise Setup - ▸ mp4 yt
logicalExercise Review
Readings:
x86 Control Flow
Tuesday 14 March (Lecture)Wednesday 15 March (Lab)Friday 17 March (Lecture)Tuesday 21 March (Lecture)
Preparation
Materials
Exercises:
- x86 Control Flow If-Else Exercise
- x86 Control Flow Loop Exercise
- x86 Control Flow Loop Exercise SOLUTION
Slides: ➊ x86-control.pdf ➍ x86-control-4up.pdf
Videos:
☰ yt playlist
x86 Control Flow
- ▸ mp4 yt Condition Codes, Comparisons, and Tests
Errors:- The example for the
gtfunction should uselong, notint, as the type of its arguments.
- The example for the
- ▸ mp4 yt Jumps, Translating If-Else, and
absdiffExercise Setup - ▸ mp4 yt
absdiffExercise Review, goto, and If Compilation Exercise Setup - ▸ mp4 yt If Compilation Exercise Review and PC-Relative Addressing
- ▸ mp4 yt Translating Loops
- ▸ mp4 yt Conditional Moves
- ▸ mp4 yt Translating Switch Statements with Jump Tables
- ▸ mp4 yt Translating Switch Statement Cases, Reverse Engineering Switches
Readings:
-
Comparisons, Tests, and Jumps
-
Translating
ifconditionals -
Translating loops
-
Translating
switchstatements- Skim: CSAPP 3.6.8, 3.6.6
x86 Procedures, Call Stack
Tuesday 21 March (Lecture)Wednesday 22 March (Lab)Friday 24 March (Lecture)Tuesday 4 April (Lecture)Friday 7 April (Lecture)Wednesday 12 April (Lab)
Preparation
For Fri Mar 24 during class:
- We will cover these Function Compilation Examples
Materials
Exercises:
Slides: ➊ x86-procedures.pdf ➍ x86-procedures-4up.pdf
Videos:
☰ yt playlist
x86 Procedures, Call Stack
- ▸ mp4 yt The Call Stack Stores Procedure Context
- ▸ mp4 yt Procedure Control Flow Instructions (
call/ret), Data Flow Conventions, Puzzle Setup - ▸ mp4 yt Procedure Puzzle Review
- ▸ mp4 yt Procedure and Stack Frame Example
- ▸ mp4 yt Register Saving Conventions, Callee-Save Example
- ▸ mp4 yt Recursion Example
- ▸ mp4 yt Stack Storage Example, Procedure Summary
Readings:
- Read: CSAPP 3.7 - 3.7.4
- Read: CSAPP 3.7.5 - 3.7.6
- x86 Machine Diagram
Representing Data Structures
Preparation
For Thursday:
- Video 1 or reading 1
Materials
Exercises:
Slides: ➊ data-structures.pdf ➍ data-structures-4up.pdf
Videos:
☰ yt playlist
Representing Data Structures
- ▸ mp4 yt Simple Arrays
- ▸ mp4 yt Multi-Level Arrays (Arrays of Pointers to Arrays of...)
Errors:- In the copyleft example, the second and third movq should be movl and should be moved to and from %ecx instead of %rcx.
- ▸ mp4 yt Row-Major Multidimensional Arrays
- ▸ mp4 yt Row-Major Array Review
- ▸ mp4 yt Structs
- ▸ mp4 yt Struct Alignment
- ▸ mp4 yt Linked List Representation
Readings:
- Read: CSAPP 3.8.1 - 3.8.2 (review simple arrays)
- Read: CSAPP 3.8.3 - 3.8.4 (nested arrays)
- Read: CSAPP 3.9 (heterogeneous data structures)
- Read: CSAPP 3.10.1 (pointer review)
- x86 Machine Diagram
Buffer Overflows
Preparation
For Tuesday:
- No preparation.
Materials
Exercises:
Slides: ➊ buffer.pdf ➍ buffer-4up.pdf
Videos:
☰ yt playlist
Buffer Overflows
- ▸ mp4 yt Overview
- ▸ mp4 yt Stack Layout and No Bounds Checking in C
- ▸ mp4 yt Example Overview
- ▸ mp4 yt Example 1 - Overwrite Padding (Lucky)
- ▸ mp4 yt Example 2 - Corruption and Segfault
- ▸ mp4 yt Example 3 - Silent Corruption and Arbitrary Code Execution
- ▸ mp4 yt Remote Code Execution and Avoiding Vulnerabilities
Readings:
- Read: CSAPP 3.10.3-3.10.4
- x86 Machine Diagram
Abstractions for Practical Systems
Memory Allocation
Tuesday 18 April (Lecture)Wednesday 19 April (Lab)Friday 21 April (Lecture)Tuesday 25 April (Lecture)
Preparation
For Lab on Wed Apr 19:
This week’s lab will launch the malloc assignment, in which you
(and a strongly recommended partner) will flesh out an
implementation of malloc and free from the
Memory Allocation lecture).
To prepare for lab (and as part of the malloc assignment), it is recommended that you review the malloc slides/videos. Optionally, you can do readings 1–3.
Materials
Slides: ➊ malloc.pdf ➍ malloc-4up.pdf
Videos:
☰ yt playlist
Memory Allocation
- ▸ mp4 yt Allocator Basics
- ▸ mp4 yt Determining Block Size
- ▸ mp4 yt Block Format and Heap Layout
- ▸ mp4 yt Implicit Free List Search
- ▸ mp4 yt Implicit Free List Allocation and Splitting
- ▸ mp4 yt Implicit Free List Freeing and Coalescing
- ▸ mp4 yt Explicit Free Lists
- ▸ mp4 yt Explicit Free List Search, Allocation, and Splitting
- ▸ mp4 yt Explicit Free List Freeing and Coalescing
- ▸ mp4 yt Seglists and Allocation Summary
- ▸ mp4 yt Malloc Assignment - Block Format
Errors:- Note that this video was recorded in Spring 2020 before the "Remembrallocator" title for the Malloc assignment was retired along with the past course assignment theme.
Readings:
Memory Hierarchy, Cache
Preparation
In class on Tuesday, Apr 24, 2023
We covered only slides 1-5 of the Memory Hierarchy/Cache slides today.
In class on Friday, Apr 28, 2023
We’ll cover only the key high-level aspects of memory hierachcy & caches today.
After the Friday, Apr 28, 2023 class
- Learn about the memory hiearchy/cache material in more detail by watching the videos and doing the reading.
Materials
Exercises:
Slides: ➊ cache.pdf ➍ cache-4up.pdf
Videos:
☰ yt playlist
Memory Hierarchy, Cache
- ▸ mp4 yt Motivating Example
- ▸ mp4 yt Cache Overview
- ▸ mp4 yt Cache Mechanics
- ▸ mp4 yt Locality
- ▸ mp4 yt More Locality Examples
- ▸ mp4 yt Cache Performance and the Hierarchical Memory Design
- ▸ mp4 yt Cache Organization
- ▸ mp4 yt Cache Blocks
- ▸ mp4 yt Direct-Mapped Cache Placement Policy and Cache Tags
- ▸ mp4 yt Address Fields
- ▸ mp4 yt Why Not Another Direct Mapping (Aside)
- ▸ mp4 yt Cache Puzzle 1
- ▸ mp4 yt Cache Conflicts and Associative Cache Placement Policies
- ▸ mp4 yt Cache Puzzle 2
- ▸ mp4 yt General Cache Dimensions and Organization
- ▸ mp4 yt General Cache Read Mechanics
- Cache Analysis Example 1: Spatial Locality in Direct-Mapped Caches
- Cache Analysis Example 2: Cache Conflicts in Direct-Mapped Caches
- Cache Analysis Example 3: Cache Conflicts Resolved by Associativity
- Types of Cache Misses
- Cache Write Policies
- Cache-Friendly Code and Summary
Readings:
Exceptional Control Flow
Process Model
Preparation
Tue May 02 During Class
We’ll study some examples from this Process Examples document.
Materials
Slides: ➊ process.pdf ➍ process-4up.pdf
Readings:
- Read: CSAPP 1.7, 8.2 - 8.4
Beyond 240
+Shells, Signals (optional)
+Optional: This topic is an optional opportunity for further depth or exploration.
Preparation
No preparation.
Materials
Slides: ➊ shell.pdf ➍ shell-4up.pdf
+Threads (optional)
+Optional: This topic is an optional opportunity for further depth or exploration.
Preparation
No preparation.
Materials
Slides: ➊ threads.pdf ➍ threads-4up.pdf
Readings:
Code Examples: examples
+Virtual Memory (optional)
+Optional: This topic is an optional opportunity for further depth or exploration.
Preparation
No preparation.
Materials
Slides: ➊ virtual-memory.pdf ➍ virtual-memory-4up.pdf
Readings:
- Read: CSAPP 9.0 - 9.7