left_adjoint
/
miscellaneous-docs
1
0
Fork 0
Code Issues Pull Requests Packages Projects Releases Wiki Activity
miscellaneous-docs/revising201.org

27 KiB
Raw Permalink Blame History

revising cs201

resources

https://thefengs.com/wuchang/courses/cs201/ https://docs.google.com/document/d/1GuMczYrPDQ8X0SfKO3VuuTSJf6yAwlFCYZNsXZqSTMc/edit#heading=h.rc090q9jbwe5 https://online.pcc.edu/d2l/home/387733

https://www.pcc.edu/ccog/cs/201/

For the optimization section of cs201: https://lore.kernel.org/netdev/20231129072756.3684495-1-lixiaoyan@google.com/ A really cool example of a patch that massively sped-up TCP because it played with the layout of structs to change the cache-line behavior and reduce misses

Random notes about development

  • It lists figure 8.26 that shows all possible signals but doesn't include them, which I think is kinda bad for these purposes. Should include figure in the site if its referenced.
  • Module 8 needs a section about user defined signals since they're needed for the homework
  • There should be a section explaining what sig_atomic_t is, what atomic is, and what volatile is
  • This class has zero collaborative learning by default. We should add more explicit pair-programming, debugging, and discussion exercises to it
  • Practice problem weirdness okay I literally don't know where a number of the practice problems come from. They're listed as coming from the book with numbers but I've checked both the 2nd and 3rd editions of the text and they don't match up with either.

Discussion prompts

These should all be some kind of small pair programming prompts with the requirement that to get full 4/4 credit you need to

Module 1

Concept: Exercise with bit flags

Consider the program for turning on and off bit flags in Lesson 7 of this module. With your partner write your own program in this style that defines several flags and, from the console, allows you to turn the flags on or off. Get creative with it! Maybe include a flag that prints the menu backwards or in capslock!

Module 2

Concept: Two's complement tutorial

Using what you've learned from writing a program that reads and sets bit flags, write a program that lets someone type in an int and then uses a for-loop to print out the two's complement representation of the number and to print out what number that bit sequence corresponds to as an unsigned int.

Module 3

Concept: Exploring the limits of floating points

Write a program with your partner that will demonstrate some of the limitations of floating point. An easy idea would be to demonstrate the fact that two float-s together doesn't always follow the laws of arithmetic (0.1 + 0.1 might not be 0.2!)

Module 4

Concept: Playing with gcc -S

With your partner write a C program that lets you read in two numbers and then add them together. Compile this code and check to make sure it works. Then generate assembly code from this using the -S option, find the instructions where the numbers are added together, and instead change it to a multiplication in the assembly. Check this program compiles and then turn it in! Try also changing your prompt in assembly as well.

Module 5

Concept:

Module 6

Concept: Structs in C and assembly

With your partner write a program that uses both a union and a struct. Generate the corresponding assembly and look at it. Upload the files and explain what you observe about the layout of the data in the corresponding assembly.

Module 7

With your partner, write a program that

  • reads in an integer, n, from the user
  • and runs a function that recursively forks "left" and "right" processes to a depth of n
  • printing out a message every time a process ends

Module 8

With your partner write a program that writes a signal handler for SIGALARM and the alarm function to make an alarm clock program that reads from the user and, when the alarm goes off, gives the option to cancel the alarm or "snooze" it. Until the alarm goes off it should print something to signify "sleeping" once a second

Module 9

Module 10

Write a program that is intentionally slow and badly written, upload it, and comment on another team's code to figure out how to fix it.

Quiz writing

Need to write 10 questions on the signal handling section:

  1. The kill function is only used for sending the SIGKILL signal to end a process (T/F) [F]

  2. What does hitting "ctrl-c" at the terminal due?

    1. Immediately stop the foreground process
    2. Send an interrupt signal to all processes in the foreground's process group
  3. To install a signal handler you need to call the function inside main (T/F) [F]

  4. In the following code, what is the final value of ourNum if you hit ctrl-c three times while the program is running

      #include <stdio.h>
  #include <signal.h>
  #include <unistd.h>

  volatile sig_atomic_t ourNum = 0;

  void signal_handler(int sig){
    ourNum = ourNum + sig;
  }

  int main(){
    signal(SIGINT, signal_handler);
    while(ourNum < 5){
      sleep(1);
      printf("The current number is: %d \n", ourNum);
    }
    return 0;
  }
  5. The only type that is allowed to be shared between a signal handler and your main code is sig_atomic_t (T/F) [T]
  6. A variable declared with the volatile keyword can be cached (T/F) [F]

  7. If you run the following code, what happens if—from another terminal—you type kill followed by the process ID printed out at the beginning of the program?

    1. The program prints "Caught the signal!"
    2. The program sleeps until it prints "Yawn! I'm awake now"
    3. The program terminates [x]
    4. This program is invalid and has undefined behavior
      #include <stdio.h>
  #include <signal.h>
  #include <unistd.h>

  sigset_t mask;

  void handler(int sig){
    printf("Caught the signal!\n");
  }

  int main() {
    printf("Hi I'm process %d !\n", getpid());
    signal(SIGINT, handler);
    sigemptyset(&mask);
    sigaddset(&mask, SIGINT);
    sigprocmask(SIG_BLOCK, &mask, 0);

    sleep(10);
    printf("Yawn! I'm awake now\n");

    return 0;
  }

  8. What are good uses of writing a handler for SIGUSR1

    1. Letting two processes communicate with each other asynchronously
    2. When you w

Week 10.

  1. The "time" command reports the total clock time a process takes (T/F) [F]
  2. The smaller the stride, the less likely you are to have a cache miss (T/F) [T]
  3. GCC is capable of eliminating some kinds of recursive call and turning them into loops (T/F) [T]
  4. Can program optimization increase the side of the executable? (T/F) [T]

  5. Loop unrolling is

    1. When you avoid loops in favor of function calls
    2. When you restructure the loop to do multiple iterations per round
    3. When the compiler eliminates all loops in the program
    4. When you inline all function calls that happen in a loop

Practice problem matching

Module 1

  1. Problem 2.1 (L3)
  2. Problem 2.6 (L3)
  3. Problem 2.7 (L4)
  4. Problem 2.8 (L5)

Module 2

  1. Problem 2.2 (L3)
  2. Problem 2.3 (L3)
  3. Problem 2.4 (L3)
  4. Problem 2.5 (Module 1 L6)
  5. Problem 2.9 (L5)
  6. Problem 2.10 (L4)
  7. Problem 2.11 (L5)

Module 3

  1. Problem 2.12 (L5)
  2. Problem 2.13 (L2)
  3. Problem 2.14 (L1)
  4. Problem 2.15 (L2)

Module 4

  1. 3.1 (L6)
  2. 3.2 (L6)
  3. 3.3 (L8-ish) [these two don't entirely correspond]
  4. 3.4 (L8-ish)
  5. 3.5 (L8)
  6. 3.13 (L8)

Module 5

  1. 13.12 (L4)

Module 6

  1. 3.8 (L2)
  2. 3.9 (L2)
  3. 3.10 (L2)
  4. 3.11 ??

Module 7

  1. 8.1 (L3)
  2. 8.2 (L3)
  3. 8.3 (L3)
  4. 8.4 (L6)
  5. 8.5 (L6)
  6. 8.6 (L6)
  7. 8.7 (L7)
  8. 8.8 (L7)

Module 8

There are no practice problems

  1. (proposed) 8.5
  2. (proposed) 8.7 – these are going to require massaging to put into the format for the online h5p system

Module 9

  1. 6.2 (L6)
  2. 6.3 (L6)
  3. 6.4 (L6)
  4. 6.5 (L6)
  5. (proposed) 6.17

Module 10

  1. 5.1 (L4)
  2. 5.2 (L4)
  3. 5.3 (L4)

Section by section summary

Module 1: C language and numeric representation

Lesson 1 - C++ to C Language

  • Content: complete

    • This maybe should be paginated into multiple lessons rather than just one

  • Program examples: Need more whole programs and worked examples showing how to convert one to the other

    • TODO Find an example from CS 162 that would be good for the worked example, something they would have already seen before

Lesson 2 - Information Storage

  • Content: complete

  • This section is extremely tiny

    • Get folded into something else?

Lesson 3 - Hexadecimal Numbers

  • Content: mostly complete

    • Need an aside connecting hexadecimal to common applications like encoding colors, one of the most common ways you'll see hex

      • Text:

        So a lot of people's first introduction to writing numbers in hex isn't decompiling code or low-level system programming, but dealing with color in art programs! Color, for computers, is generally represented as "24-bit color depth" which means that we're using 24 bits to represent the full RGB color. We do this by splitting the 24-bits into 8-bits for red, 8-bits for green, and 8-bits for blue. Now, what numbers can you represent with 8-bits? 0 – 255! And if you use two digits of hex, what numbers can you represent? Well that's 0x00, which is 0, through 0xFF which is 15*16 + 15 or 255. So in order to represent a 24bit color we can just write a hex number with six digits! Pure black is then 0x000000, pure white is 0xFFFFFF, and something like teal is 0x39a78e. If you've never played with hex representations of colors check out https://www.color-hex.com/.

  • Practice problems

    • Problem 2.1
    • Problem 2.6

  • Program examples:

    • Show some small programs that actually use hex syntax for arithmetic

        #include <stdio.h> // this is how we are able to call printf

  int main(){

    int hex1 = 0x1A; // 16 + 10 = 26
    int hex2 = 0xFF; // 15*16 + 15 = 255

    printf("hex1 in decimal is: %d\n", hex1); // the %d directive prints signed integers in decimal
    printf("hex2 in decimal is: %d\n", hex2);
    printf("The sum in hex is: 0x%x\n", hex1 + hex2); // the hex directive is %x (or %X if you want UPPERCASE LETTERS)

    return 0;
  }

Lesson 4 - Word and Data Sizes

  • Problem 2.7
  • Content: complete

Lesson 5 - Byte Ordering

  • Problem 2.8
  • Content: complete
  • TODO Remove reference to tutorial point (replace with wikipedia entry for stability: https://en.wikipedia.org/wiki/Endianness#Networking)
  • TODO Inline the showbytes.c file, google doc links in the course content are permissions disaster waiting to happen

Lesson 6 - Boolean Algebra

  • Problem 2.5
  • Content: complete
  • TODO Rename it because this isn't actually boolean algebra this is pointwise bit operations :-P

  • Program examples:

    • Cellular automata, because they're fun and creative
    • Okay this is an example that works but it's definitely too complex for a first example and I'd need to write an entire thing about cellular automata 
  #include <stdio.h>

  // Define constants
  #define RULE 30         // The rule number for the cellular automata
  #define GENERATIONS 16  // The number of generations to simulate
  #define WIDTH 64        // The width of the cellular automata

  int main() {
      // Declare a long long variable to store the current state of the automata
      long long current_state = 1LL << (WIDTH / 2);  // Set the initial state with a single cell in the center
   
      // Iterate for the specified number of generations
      for (int gen = 0; gen < GENERATIONS; gen++) {
          // Print the current state of the automata
          for (int i = 0; i < WIDTH; i++) {
              // Check each bit of the current state using bitwise AND
              // If the bit is set (1), print an asterisk; otherwise, print a space
              putchar((current_state & (1LL << i)) ? '*' : ' ');
          }
          // Move to the next line after printing each generation
          putchar('\n');
       
          // Calculate the next state of the automata
          long long next_state = 0;
          for (int i = 0; i < WIDTH; i++) {
              // Get the state of the left neighbor
              // If it's the leftmost cell, consider the left neighbor as 0
              int left = (i == 0) ? 0 : (current_state & (1LL << (i - 1))) != 0;
           
              // Get the state of the current cell
              int center = (current_state & (1LL << i)) != 0;
           
              // Get the state of the right neighbor
              // If it's the rightmost cell, consider the right neighbor as 0
              int right = (i == WIDTH - 1) ? 0 : (current_state & (1LL << (i + 1))) != 0;
           
              // Apply the rule to determine the new state of the current cell
              // The rule is defined by the RULE constant, which represents the outcome
              // for each possible combination of the left, center, and right cells
              int new_bit = (RULE >> (left * 4 + center * 2 + right)) & 1;
           
              // Set the corresponding bit in the next state using bitwise OR and left shift
              next_state |= (long long)new_bit << i;
          }
       
          // Update the current state with the next state for the next generation
          current_state = next_state;
      }
   
      return 0;
  }

Lesson 7 - Bit Flags and Masking

  • Content: complete

  • Program examples:

    • Need an actual complete example of turning on and off bits in a bit flag

    • Extend the partial code into a full thing with a TUI so that students can see how it works and play with it

        #include <stdio.h>

  #define MOTOR_ON     1   // mask for 1st bit - 2^0
  #define SPEED_LOW    2   // mask for 2nd bit - 2^1
  #define SPEED_MEDIUM 4   // mask for 3rd bit - 2^2
  #define SPEED_HIGH   8   // mask for 4th bit - 2^3
  #define REVERSE      16  // mask for 5th bit - 2^4

  void print_menu() {
      printf("\nBit Flag Menu:\n");
      printf("1. Toggle MOTOR_ON\n");
      printf("2. Toggle SPEED_LOW\n");
      printf("3. Toggle SPEED_MEDIUM\n");
      printf("4. Toggle SPEED_HIGH\n");
      printf("5. Toggle REVERSE\n");
      printf("0. Exit\n");
  }

  void print_bit_flag(int bit_flag) {
      printf("\nCurrent Bit Flag: %d\n", bit_flag);
      printf("MOTOR_ON: %s\n", (bit_flag & MOTOR_ON) ? "ON" : "OFF");
      printf("SPEED_LOW: %s\n", (bit_flag & SPEED_LOW) ? "ON" : "OFF");
      printf("SPEED_MEDIUM: %s\n", (bit_flag & SPEED_MEDIUM) ? "ON" : "OFF");
      printf("SPEED_HIGH: %s\n", (bit_flag & SPEED_HIGH) ? "ON" : "OFF");
      printf("REVERSE: %s\n", (bit_flag & REVERSE) ? "ON" : "OFF");
  }

  int main() {
      int bit_flag = 0;
      int choice;

      do {
          print_bit_flag(bit_flag);
          print_menu();
          printf("Enter your choice: ");
          scanf("%d", &choice);

          switch (choice) {
              case 1:
                  bit_flag ^= MOTOR_ON;
                  break;
              case 2:
                  bit_flag ^= SPEED_LOW;
                  break;
              case 3:
                  bit_flag ^= SPEED_MEDIUM;
                  break;
              case 4:
                  bit_flag ^= SPEED_HIGH;
                  break;
              case 5:
                  bit_flag ^= REVERSE;
                  break;
              case 0:
                  printf("Exiting...\n");
                  break;
              default:
                  printf("Invalid choice. Please try again.\n");
          }
      } while (choice != 0);

      return 0;
  }

Module 2: Integer representation

Lesson 1: Integer Data Types

  • Content: complete

  • Very short, again, just a single table

    • is this something that should get folded into another section?

Lesson 2: Unsigned Integer Encoding

  • Content: complete
  • Very very short

Lesson 3: Signed Integer Encoding

  • Practice problems

    • Problem 2.2
    • Problem 2.3
    • Problem 2.4
  • Content: complete

  • Programming examples:

    • Access numbers bit by bit to demonstrate 2s complement

Lesson 4: Type Casting

  • Problem 2.10
  • Content: complete

  • Programming examples:

    • Need some exampes of good and bad practices with typecasting, base them off the examples that are in the section but as full code you can run and see what happens rather than just reading

Lesson 5: Integer Arithmetic

  • Problem 2.9
  • Problem 2.11
  • Content: complete

  • Programming examples:

    • Need to build out actual running examples of the problem with detecting overflow
    • Base them off of the examples but fleshed out into something that can run

module 3: Floating point

Lesson 1: Fractional Binary Numbers

  • Problem 2.14
  • Content: complete

Lesson 2: IEEE 754 Floating Point Encoding

  • Problem 2.13
  • Problem 2.15

  • Content: mostly complete

    • There need to be a lot more examples in the text itself, worked out in detail
    • This is a notoriously finicky topic

  • Programming examples:

    • Write an actual example of numerical analysis that demonstrates the utility of having a positive and negative zero
    • Show don't tell

Lesson 3: Floating Point Examples

  • Content ???

    • This section lists them as "fractional binary numbers" but they're not they're IEE floating point which is, in fact, different
    • Needs more examples worked out

Lesson 4: Floating Point Rounding

  • Content: mostly complete

    • Need to explain why you can't properly represent the real numbers on a computer (issues of computability)
    • How do you change the rounding mode of the floating point unit?

Lesson 5: Floating Point Operations

  • Problem 2.12
  • Content: complete

  • Programming examples:

    • Needs a few examples of what can go wrong in typecasting

Module 4: Introduction to object code

Lesson 1: Build Process

  • Content: complete

Lesson 2: Object Code in gcc

  • Content: complete

  • Activity needed: reading hex dumps of object code

    • Need to show how to compile a hello world file to a .o and then read it in a hex editor, spotting the text "hello world" in the compiled file

Lesson 3: Getting Assembly and Machine Code

  • Content: complete

Lesson 4: Assembly Code

  • Content: needs expansion

    • This section only gives a few sentences of light description of what assembly code is
    • Would be better with more context before jumping into the mess of register names in the next section

Lesson 5: Accessing Data

  • Content: complete

Lesson 6: Move Instructions

  • Practice problems

    • 3.1
    • 3.2
  • Content: complete

Lesson 7: Push and Pop Instructions

  • Content: complete

Lesson 8: Arithmetic Operations

  • Practice problems:

    • 3.3 (sorta, this and 3.4 are about mapping C to generated code)
    • 3.4
    • 3.5
    • 3.13
    • 3.11 (from Module 6 practice problems, similar to 3.3 and 3.4)
    • Content: complete

(New) Lesson 9: Worked examples of assembly

This section needs worked, explained, examples of assembly code. There are no complete examples in the course site as it exists.

Module 5: Object code: control

Lesson 1: Logical and Shift Operators

  • Content: complete

    • Should we really be talking about IA-64 though? The architecture is deprecated and yet it's not even made clear that this is an architecture that no longer is in use (even wikipedia lists it as a discontinued processor architecture https://en.wikipedia.org/wiki/IA-64)

lesson 2: Accessing the Condition Codes

  • Content: complete

  • Programming examples:

    • Need full examples of condition setting and jumping

  • Activity needed:

    • give a full example that uses labels and jumps
    • give instructions for how to read the objdump

Lesson 3: If Statements

  • Content: mostly complete

    • Show how to reconstruct the if-statement from the assembly

  • Practice problem needed:

    • Need a problem like 13.12 for lesson 4

Lesson 4: Loop Statements

  • Content: mostly complete

    • Show how to reconstruct the loop from the assembly

  • Practice problem:

    • 13.12

Lesson 5: Switch Statements

  • Content: complete (but with an edit suggestion)

    • Personally I don't like the aside about gcc optimization avoiding division
    • It's a good lesson!
    • But don't do the "leave this to students to figure out"
    • We should work out the unoptimized version and show the differences between them

  • Programming example

    • Need comparison between generated assembly of if-else statements vs. the same logic expressed as a switch/case

Module 6: Object code: Procedures and Floating Point

Lesson 1: Procedures

  • Content: editing fixes

    • This bit about "procedures are what C language calls functions" isn't right. C calls functions "functions". I think the author meant to say something more like "In most assembly languages, functions are labeled sequences of code called 'procedures'" or something like that

    • In comparison to a lot of lessons this one is dense and introduces

      • Procedure definitions in assembly
      • Calling conventions and "the stack"
      • Inlining code
      • How to handle large numbers of arguments to functions
    • Maybe should break it up into pieces

  • Practice problem:

    • Need a problem here related to looking at assembly and reconstructing a possible function definition that could result in it

Lesson 2: Heterogenous Data Structures

  • Content: Complete

  • Practice problems

    • 3.8
    • 3.9
    • 3.10

  • Programming example:

    • Need full examples for each category showing how arrays, unions, and structs compile down

Lesson 3: Buffer Overflows and Security Issues

  • Content: Needs expanding

    • Need real-world examples and resources to explore about buffer overruns

  • Programming examples:

    • Hands-on demo of how a buffer overflow would work

Lesson 4: Floating Point

  • Content: complete

  • Programming example:

    • It needs to be inlined rather than be a separate file

Module 7: Processes

Lesson 1: Flow Control

  • Content: Complete

    • But very very tiny

Lesson 2: Exceptions

  • Content: complete

Lesson 3: Classes of Exceptions

  • Content: complete

  • Practice problems:

    • 8.1
    • 8.2
    • 8.3

Lesson 4: Exceptions in Linux/x86-64

  • Content: complete

  • Programming examples:

    • Need some complete examples showing code that demonstrates the exceptions/faults, at least of a divide error and a general protection fault

Lesson 5: Processes

  • Content: Complete but denser than the rest of the section

    • Might not need to be broken up but definitely needs self-assessment because these are heavier concepts

  • Practice problems:

    • Need something here!

Lesson 6: Process Control

  • Content: Complete

  • Practice problems

    • 8.4
    • 8.5
    • 8.6

Lesson 7: Examples of Fork

  • Content: needs expanding (or potentially redistribution)

    • Basically all the programming examples from this module are right here, right now
    • This might need to be re-organized into the rest of the sections so that there's things to test out in each lesson rather than it all being at the end

  • Practice problems

    • 8.7
    • 8.8

Module 8: Signal handling

All lessons here need practice problems

Lesson 1: Signals in Linux Systems

  • Content: complete

Lesson 2: Signal Management

  • Content: complete

  • Programming examples:

    • Need complete examples of signal handling instead of just a line or two, shouldn't be redundant with L5

  • Practice problems:

    • Needed

Lesson 3: Blocking and Unblocking Signals

  • Content: complete

  • Programming example:

    • Just need to expand the partial examples into entire, compilable examples

  • Practice problems:

    • Needed

Lesson 4: Writing Signal Handlers

  • Content: refactor

    • I think this section needs to be redistributed into lessons 2 and 3

    • Explain what volatile and sig_atomic_flag mean

      • Recall this later when dealing with caching in Module 9
  • (NEW) Proposed practice problem 8.7 (section 8.5) from textbook

Lesson 5: Signal Handler Examples

  • Content: needs expansion

    • These are not full examples
    • Need more examples that actually match to the kinds of parent/child relations like in the shoot-out assignment
  • (NEW) Proposed practice problem 8.8 (section 8.5)

Module 9: Memory systems

Okay I'll be honest I think this entire module is basically just one lesson stretched out. It's a very superficial look at what memory is, the kind of thing that you can explain in 10-15 minutes at a time. We can collapse lessons 1/2/4 into one, 3/5 into one, and then lesson 6 should perhaps get expanded significantly with some actual diagrams and examples.

This would be a great place to include the TCP speed up linked above as a case-study in a more fleshed out final lesson

Lesson 1: RAM

  • Content: complete

Lesson 2: Other types of Memory

  • Content: complete (but extremely short)

Lesson 3: Accessing Main Memory

  • Content: complete

Lesson 4: Disk Storage

  • Content: complete

Lesson 5: Locality

Lesson 6: Memory Hierarchies and Caches

  • Practice problems

    • 6.2
    • 6.3
    • 6.4
    • 6.5

Module 10: Optimzation

Lesson 1: Optimization

  • Content: needs expansion

    • Needs to explain more clearly that optimization is primarily done during execution by the architecture, secondarily by the compiler, and finally if it can't be done by the compiler it falls to you

Lesson 2: gcc Optimization levels

  • Content: complete…ish

    • It's actually not just O3 that can cause problems, I've seen it happen at even lower compilation
    • Also need to check if there is an alias that makes gcc on replit default to something other than -O0 because I've seen optimization bugs happen without specifying an optimization level

    • Need to provide some concrete examples of what optimization caused bugs can look like

      • iterating through an array with a while loop where the order of conditions matters
      • show generated assembly and how it differs

Lesson 3: How to measure performance?

  • Content: complete but very short

    • Needs a couple of examples to show and test out measurement

Lesson 4: How to Optimize Code

  • Content:

    • Needs to be split into multiple segments, too much in one thing
    • Need to show the actual assembly for these different manual optimizations in order to show how the optimizations are implemented
    • There's some slightly out of date stuff in here about recursion, function calls, and things like that

  • Practice problems

    • 5.1
    • 5.2
    • 5.3