Skip to main content Link Menu Expand (external link) Document Search Copy Copied

Meeting Summary for CS 326 Lecture/Lab Spring 2025

Date/Time: March 25, 2025, 02:52 PM Pacific Time (US and Canada)
Meeting ID: 813 3845 7711

Quick Recap

  • Midterm Results & Policy:
    Greg expressed satisfaction with the midterm results—the best seen in several years—and explained a policy for raising midterm scores. The new grading policy will allow an improved final score to replace the midterm score by averaging the two.

  • Key Topics Discussed:

    • Memory allocation in C programming, including the use of power-of-2 strategies.
    • The process of allocating and freeing space.
    • Implementation of programs using pipes and child processes.
    • Complexities in shell programming and the anatomy of a shell implementation.
    • Introduction of the next project: a shell project.

Next Steps

For Students:

  • Install Roo Code before the lab section tomorrow.
  • Explore using Roo Code to support upcoming projects.

For the Professor:

  • Refine the teacher mode for Rue during tomorrow’s lab.
  • Post solutions for the midterm.
  • Release the shell project along with detailed project directions tomorrow.
  • Work through additional shell concepts in the lab.

Detailed Summary

Midterm Results and Future Topics

  • Midterm Performance:
    Greg noted that the midterm results were the best in several years.

  • Score Improvement Policy:
    To raise a midterm score, the final exam score will be averaged with the midterm, and the higher average will be used in the final grade computation.

  • Upcoming Topics:

    • A user-level project and modifications to the shell implementation.
    • Upcoming projects and labs focusing on kernel involvement.
    • The final exam will follow a similar format with a comprehensive review of topics.

Memory Allocation in C Programming

Greg emphasized the importance of proper memory management in C, explaining the three primary areas where memory can be allocated:

  • Stack:
    Used for local variables during function calls.

  • Heap:
    Allocated using functions like malloc and freed with free.

  • Data Section:
    Holds global variables.

Additional points:

  • Pointers must reference allocated memory to be useful.
  • On a 64-bit architecture, pointer size is typically 8 bytes.
  • Void Pointers: Cannot be dereferenced without typecasting.

Mermaid Diagram – Memory Allocation Areas:

flowchart LR
    A[Memory Allocation]
    B[Stack: Local Variables]
    C[Heap: Dynamic Memory (malloc/free)]
    D[Data: Global Variables]
    A --> B
    A --> C
    A --> D

Memory Allocation and Heap Allocator Design

  • Kernel Allocation:
    The kernel allocates memory in 4K chunks, influencing the design of the custom heap allocator.

  • Design Considerations:
    • Reducing the number of system calls.
    • Correct management of allocated memory.
    • Proper use of system calls when working with file descriptors.
  • Argument Manipulation in C:
    Emphasis was placed on the need to understand and correctly implement argument manipulation in C code.

Xv6‑riscv C Code Example – Simulated Heap Allocation (Using sbrk):

Note: xv6 does not include a full-featured malloc, so this example uses sbrk to illustrate dynamic allocation.

#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

int main(void) {
    // Simulate allocating 1000 bytes on the heap.
    char *ptr = sbrk(1000);
    if(ptr == (char*) -1) {
        fprintf(2, "sbrk failed\n");
        exit(1);
    }
    // Use the allocated memory (for example, store a character)
    ptr[0] = 'A';

    // Simulate freeing memory (xv6 does not support sbrk deallocation,
    // but this illustrates the intended process)
    // sbrk(-1000);

    exit(0);
}

File Descriptor Reading and Linked List Iteration

  • File Descriptor (FD) Reading:
    Greg discussed methods to read from an FD and count newline characters:
    • Simple Method: Use a while loop to read one character at a time and increment a counter upon encountering a newline.
    • For more complex problems, using a buffer might be more efficient.
  • Linked List Iteration:
    • Iterating over a linked list to compute average block sizes by summing block sizes and counting blocks.
    • Note that most kernel-level C code avoids floating-point operations.

Memory Allocation and Computation Process

  • Project Overview:
    • Allocation of two memory blocks (1000 bytes and 2000 bytes) was discussed.
    • Computation of values such as the block size and data offset.
    • Keeping track of the running sum of sizes was emphasized.

Allocating and Freeing Space Process

  • Process Description:
    • Initially, a larger block (e.g., 1000 bytes) is allocated.
    • The block is then freed, and a smaller allocation (e.g., 50 bytes) is made.
    • Visual aids were used to help illustrate the calculation of size and offsets for memory allocation.
  • Break:
    The team took a 10-minute break before resuming further discussions.

Implementing Pipes and Child Processes

  • Pipes and Children:
    • For a program requiring three child processes, two pipes are needed.
    • Each pipe connects a pair of processes.
  • Process Operations:
    • Creating the pipes.
    • Forking child processes.
    • Managing file descriptors by closing unused pipe ends in both the parent and child processes.
    • Correct manipulation of the file descriptor table to ensure proper connectivity between standard input and output.

Xv6‑riscv C Code Example – Pipe and Fork Implementation:

#include "kernel/types.h"
#include "user/user.h"

int main(void) {
    int pipefd[2];
    if (pipe(pipefd) < 0) {
        fprintf(2, "Pipe failed\n");
        exit(1);
    }

    int pid = fork();
    if (pid == 0) {
        // Child process: read from pipe
        close(pipefd[1]);  // Close unused write end
        char buffer[128];
        int n = read(pipefd[0], buffer, sizeof(buffer));
        write(1, buffer, n);
        close(pipefd[0]);
        exit(0);
    } else {
        // Parent process: write to pipe
        close(pipefd[0]);  // Close unused read end
        write(pipefd[1], "Hello from parent\n", 19);
        close(pipefd[1]);
        wait(&pid);
        exit(0);
    }
}

Mermaid Diagram – Pipes and Child Processes:

flowchart LR
    A[Parent Process] -->|Creates Pipe| B[Pipe (Write End)]
    A -->|Creates Pipe| C[Pipe (Read End)]
    C -->|Connects to| D[Child Process 1]
    D -->|May communicate with| E[Child Process 2]
    %% Note: For three children, adjust diagram accordingly (e.g., chain children with two pipes)

Shell Programming and Tool Exploration

  • Shell Programming:
    • Complexity in handling multiple data types.
    • Understanding the shell as a tool for user interaction with the operating system.
    • The shell allows the execution of arbitrary commands and the redirection of outputs.
  • Tool Exploration:
    • Tools such as ChatGPT and Root Code were highlighted for their usefulness in problem-solving and project guidance.
    • Students are encouraged to install Root Code before the next lab session.

Unix Shell Design and Command Execution

  • Unix Shell Features:
    • Supports execution of arbitrary commands (e.g., ls, wc).
    • Capable of output redirection to files.
    • Can perform more complex operations, such as sorting and filtering.
    • May be viewed as a mini compiler in terms of processing and redirection.

Shell Implementation and Parsing Process

  • Shell Anatomy:
    • Emphasis was placed on the parsing process.
    • The shell creates a tree data structure to represent the command and its arguments.
  • Parsing Techniques:
    • The concept of recursive descent parsing was explained.
    • Forking is incorporated to create child processes for command execution.
  • Next Project:
    • The upcoming project involves a shell project where students may modify the shell to output the parsed tree.

Mermaid Diagram – Shell Command Parsing Structure:

graph TD
    A[Shell Command]
    B[Command Name]
    C[Argument 1]
    D[Argument 2]
    A --> B
    A --> C
    A --> D