Blog

This week focused on virtual memory fundamentals and practical memory management in C. The lectures and assignments mostly dealt with understanding how virtual memory works at the OS and hardware level. The main idea was that the OS uses virtual memory to create the illusion that each process has its own private memory, while in reality all processes share the same physical RAM.

Topics covered this week

Some of the topics we covered this week:

• OSTEP 13: Address spaces
  • An address space is the memory view a process thinks it has. The process uses virtual addresses, while the hardware and OS translate those into physical addresses in RAM. This lets many processes run safely at once without each one needing to know where it really sits in physical memory.
  • A typical address space has three main regions
    • Program Code: the compiled instructions of the program. This memory region is static (it doesn’t grow at runtime), so it sits at the top of the address space and stays fixed.
    • Heap: memory for dynamically-allocated data. The heap grows upward (toward higher addresses) as the program requests more memory.
    • Stack: used for function calls, local variables, and return values. The stack grows downward (toward lower addresses) with each function call and shrinks as functions return.
  • Memory management goals
    • Transparency: programs should be able to act as if they have their own memory.
    • Efficiency: translation should be fast and not waste too much memory.
    • Protection: one process should not read/write another process’s memory.
• OSTEP 14: C Memory API
  • Stack vs. heap allocation
    • Stack memory is managed automatically by the compiler, e.g., when declaring a local variable inside a function. Once the function returns, the stack frame is gone, and any pointer to it becomes invalid.
    • Heap memory is for data that needs to outlive a single function call. It is managed manually with malloc and released with free.
  • Common memory bugs
    • Forgetting to allocate memory: if you declare a pointer but never call malloc, then use the pointer, it will point to some random memory address.
    • Allocating too little memory: not allocating enough memory leads to buffer overflow, which results in undefined behavior.
    • Not initializing allocated memory: allocated memory should point to the intended data or NULL.
    • Memory leaks: when allocated memory isn’t explicitly freed, it results in a memory leak, which will degrade performance, especially for long-running processes.
  • Garbage Collection
    • Many programming languages (but not C) perform automatic garbage collection by freeing unreachable memory objects.
• OSTEP 15: Address Translation
  • Base-and-bounds. The memory management unit (MMU) has two special registers: a base register and a bounds register.
    • Base register: where memory for a process starts
    • Bounds register: how much memory is allocated for a process
    • Address translation
      • physical address = virtual address + base
• OSTEP 16: Segmentation
  • To avoid wasting memory by requiring large contiguous memory blocks, the OS will separate and store smaller parts of each process’s virtual memory into physical memory.
  • Segmentation treats the code, heap, and stack as separate parts called segments, each with its own base and bounds, which results in better memory utilization.
  • Segmentation introduces a bin packing problem: how should irregular pieces of virtual memory fit together in an optimal way?
• OSTEP 18: Paging
  • Paging sidesteps the bin packing problem by storing virtual memory into fixed-sized chunks instead of irregularly-sized segments.
  • Virtual memory is divided into pages, physical memory into page frames, and a per-process page table maps virtual page numbers (VPNs) to physical frame numbers (PFNs), allowing flexible placement in physical memory.
  • This avoids fragmentation problems, but introduces extra translation overhead.

Reflection

The biggest challenge this week was just dealing with the sheer volume of information. There’s a lot of things that operating systems and hardware do to handle memory, and it’s a lot of dense technical information to unpack.

I think the most valuable takeaway this week was gaining more exposure to low-level systems programming and design. It’s been interesting to learn about the design challenges and technical solutions that are involved in making virtual memory work, and it looks like we will continue studying this topic in the next module, so we’ll have some more time to process it all.

This week we got into the nitty-gritty details of process management and CPU scheduling. The assignments this week mostly dealt with how the OS decides which process the CPU should run. The lecture material and readings fit together nicely, with each lecture corresponding to a chapter in OSTEP.

Topics covered this week

Some of the topics we covered this week were:

• OSTEP Chapter 4: Processes
  • Processes as the main CPU virtualization abstraction
  • Program versus process
    • A program is just some data on a disk, which contains instructions on how to run the program, while a process is a program that is actually running. A process has an execution state and data in memory, and a single program can have multiple processes running at any given time
  • Machine state, including memory, registers, the program counter, and stack pointer
  • Process creation and process states
    • The OS creates a process by reading the program’s code from disk and loading it into memory, allocating memory for the run-time stack and the heap, then allows the program execute by transferring control to the program’s main entrypoint
  • OS process-management data structures, like the task_struct in Linux, which contains information about the execution state of the process
  • Multiprogramming and context switching, which allow multiple processes to appear to run at the same time, keeping the system responsive for users
  • The difference between a mechanism and a policy
    • A mechanism is how the OS performs some task, like context switching
    • A policy describes which processes the mechanism should be applied to
• OSTEP Chapter 5: The C process API
  • The process tree represents processes as parent and child nodes, so that a single parent process can have many child processes.
  • OS process creation with the C Process API
    • The C Process API provides functions to manage processes
      • fork() clones the calling process, creating a new process that continues execution from the same point as the calling process
      • wait() lets a parent pause until a child process finishes
      • exec() replaces the calling process with a new process
• OSTEP Chapter 6: Limited direct execution
  • How does the OS control processes if the process controls the CPU while it is running?
    • Limited Direct Execution allows processes to run directly on hardware, while allowing the OS to maintain control
  • Kernel mode vs. user mode
    • Kernel mode allows all instructions to run, allowing direct access to hardware and memory
    • User mode only allows non-privileged instructions to run, which is how programs normally run
  • Hardware interrupts allow devices to run instructions on the CPU through an interrupt handler
    • If a program needs to run a privileged instruction, it uses a system call, which triggers a trap into the kernel. The kernel handles the request and then returns control back to user mode
• OSTEP Chapter 7: Process Scheduling
  • Scheduling metrics
    • Turnaround time (TAT) measures how long it takes a job to finish after arriving
    • Response time measures how long it takes the system to start running the job after it arrives.
  • Scheduling policies
    • First-In First-Out (FIFO) or First-Come First-Served (FCFS)
      • Processes are run sequentially, in the order that they arrive
    • Shortest Job First (SJF)
      • The processes that will take the least time to complete will run first
    • Shortest Time to Completion First (STCF)
      • Processes that will complete quickly can preempt longer-running processes
    • Round Robin scheduling
      • Each process runs for a short time slice, so that processes appear to be running simultaneously
• OSTEP Chapter 8: Multi-Level Feedback Queue (MLFQ)
  • The OS does not know when jobs will arrive or how long they will take, so it uses a multi-level feedback queue (MLFQ) to dynamically balance the priority of processes, optimizing responsiveness and turnaround time
    • New jobs start at high priority, and the scheduler adjusts their priority based on how they behave
    • Jobs that use a lot of CPU gradually move down, while jobs that frequently give up the CPU, such as interactive programs, can stay higher
  • Problems
    • Starvation: lower-priority jobs will never run if there are always higher-priority jobs
    • Gaming the system: processes may be able to maintain high priority through certain tricks, like requesting I/O before the end of its time slice
  • Solutions
    • Boosting: intermittently move every job to highest-priority, so that it is guaranteed to run eventually
    • CPU allotment: give a process a certain amount of CPU time before moving it to a lower priority

Reflection

The most challenging concept this week was calculating scheduling metrics, like turnaround time. This is especially tricky to calculate when dealing with time-sliced scheduling and different job arrival times, since the jobs will all consume part of the CPU’s time, and there are a lot of different factors to keep track of.

For the lab this week, I made Gantt charts with matplotlib to visualize scheduling metrics, which involved creating a scheduling simulation algorithm in Python. This helped a lot with understanding the decisions that the OS makes when running processes.

It’s been interesting to learn about how a program actually runs, and I now have a better understanding of things I’ve used before but hadn’t thought about much. For example, I hadn’t really thought about what happens when entering a command into a command prompt, but now I have a better idea of how a shell can handle user input with the C Process API.

This week we got started with the course and covered a lot of ground: computer architecture, C programming, the history of Unix and Linux, and the core abstractions that operating systems provide. The reading from OSTEP Chapter 2 paired well with the lectures, and it looks like it should be a helpful resource for the rest of the course.

Topics covered this week

Some of the topics we covered were:

• Computer architecture
  • Basic components of a computer (Von Neumann model)
    • The CPU fetches instructions from memory and then executes them.
    • The system’s memory (RAM or volatile storage) stores instructions and the data that the instructions will operate on, while non-volatile storage, like a hard drive, stores persistent data.
    • I/O devices act as an interface between the system and users, or other systems over the network.
  • Buses connect the different components of the system. Faster buses are closer to the CPU.
  • The storage hierarchy refers to different types of storage used by a computer. The fastest storage, like CPU registers, store the least amount of data, while slower storage, like hard drives, can store more data.
  • The operating system as a resource manager
    • The OS allocates CPU time, memory, and disk space fairly and efficiently across all running processes.
  • Physical vs. virtual memory
    • Physical memory is the actual RAM in the computer, while virtual memory is an operating system abstraction that gives each program its own address space and maps those addresses to physical memory.
  • The memory layout of a running program describes how the system stores different kinds of data needed to run a program. For example, the program code and heap are stored at the beginning of the memory block, while the call stack is stored at the end.
• Function calls and the stack
  • The system stores function calls in a LIFO memory structure called the call stack. In an x86 architecture, the esp register points to the top of the stack, and the ebp register points to the stack frame, which contains data related to the function call, e.g., arguments, local variables, and the return address.
• The C programming language is a simple, low-level language created by Dennis Ritchie at Bell Labs in 1973. Many operating systems, like Linux, are implemented in C, and many programming languages, like JavaScript and Go, use the familiar C syntax.
  • Data types
    • C has primitive data types, like char, int, long, float, and double, which are the basis for derived types like pointers, arrays, and structs.
  • Pointers point to locations in memory, and are useful for passing a reference to some data that a function should modify.
  • Structs are structured data types, similar to objects, but without object-oriented behavior, like inheritance and methods. Structs can be used for creating custom data types, like a String.
  • Memory allocation in C is handled manually by functions like malloc, calloc, and free.
• Linux and the shell
  • Unix and Linux history
    • Unix was created by Ken Thompson and Dennis Ritchie at Bell Labs in 1969.
    • Linux was created by Linus Torvalds in 1991 as a clone of Unix. Many programs from the GNU software project were integrated with the Linux kernel to create the Linux operating system.
  • Shell scripting with bash
    • The shell describes the command-line interface between the user and the OS.
    • The shell reads commands entered by the user, interprets them, and then asks the operating system (usually through system calls) to execute the requested actions.
    • The Bourne Again Shell (bash) is a commonly used shell.

Reflection

After reviewing these topics, the area that I’m least familiar with is low-level memory management. I tend to use higher-level programming languages, like Python and JavaScript, where memory management is handled automatically. We explored memory management a bit in this week’s programming assignment, so I’m getting some more experience with it.

Structs and pointers are a bit easier for me to understand, since these concepts are often used in higher-level programming languages. I’m familiar with the difference between passing by value vs. passing by reference and object-oriented programming, so I’ve been able to translate that knowledge to C programming.

I’m also pretty familiar with Linux, and recently earned my Linux+ certification. It looks like next week’s lesson will cover process management. I’m already familiar with Linux concepts like systemd, process kill signals, and controlling background tasks, so it will be interesting to see how that is handled at the hardware level.

Looking back on the HW1 assignment, I would probably approach this assignment in a similar way. Now that I have a better understanding of the game’s mechanics, however, I would implement some things differently. Although it wasn’t part of the assignment, creating a game with a Java Swing UI would be a fun challenge. Hangman is a visual game with simple graphical components, so it shouldn’t be too difficult to make a UI for it.

The thing I enjoyed most about this course was learning Kotlin. It’s a modern, expressive, multi-paradigm programming language, which allows for more flexibility than Java. Kotlin supports most Java language features, with a few exceptions, making it possible to follow both object-oriented and functional programming paradigms when designing an application.

I also learned a lot about Android development. Learning how to use Jetpack Compose has been pretty intuitive for me, since I’m already familiar with React. Before this course, I hadn’t done much native programming for mobile devices, having mostly focused on web development, so it was great to learn more about this area of software development. Maybe I’ll learn Swift next, since I have an iPhone, or spend some more time learning React Native to target Android and iOS.

Overall, this course has been helpful for learning more about software development and design patterns. There are a ton of resources for learning more, like Node.js Design Patterns and Patterns.dev. I’ll make sure to spend some more time continuing to learn about this topic.

I reviewed Glenn’s code for the Markov assignment. Glenn’s strategy was to first implement methods that didn’t call any other methods, then implement the methods that called those methods, which makes sense, since you can make sure the methods without any dependencies work before implementing the methods that call other methods.

My strategy was to first scaffold out the code according to the documentation, so that everything was syntactically correct. From there, I implemented the logic as it was described in the documentation, focusing on getting the tests to pass. After that, I reviewed the documentation again and checked the output to make sure it made sense.

I think both of our strategies are reasonable for this assignment. Glenn’s code follows the Google Java Style Guide, and so does my code.

I also worked on developing an Android app this week using Kotlin, which is Google’s recommended language for Android development, and I’ve been liking it so far. I’m finding Kotlin to be more expressive than Java, similar to TypeScript, which is my go-to programming language. Kotlin also works with Java, so both languages can work together in the same project.

Kotlin appears to be gaining more traction in recent years, so it could be a good language to learn.

Project 1 Code Review

I reviewed code from Glenn and Jack for Project 1. One of the first things I noticed from reviewing my teammates’ code was that I overlooked implementing a method in my own code. All of the tests passed on my code, and it seemed like everything was working correctly, but I guess that one slipped by me. It’s helpful to work with a team for this reason, since one person will often see what another person might miss. Other than that, we all completed the assignment and wrote code in a clear and understandable way.

Another thing I did differently was to handle the resistance between between ElementalTypes with a matrix, since the values were given as a table, so a matrix made sense. I also simplified the constructor and setPhrase function a bit to avoid leaking this out of the constructor.

My general strategy for approaching this assignment was to first read the documentation, then scaffold out out the classes and resolve any syntax errors so that the code would compile. From there, I worked on implementing the logic as it was described in the documentation, focusing on getting the tests to pass. After all the tests were passing, I reviewed the output from the tests to make sure it made sense, then cleaned up the code a bit and added some javadocs.

My teammates described their strategies as follows:

I just did what make sense to me at the moment and skip that I don’t get quickly. If I ran into a method that uses another method, I stop and try to do the other method first. Basically I’m solving methods that doesn’t need other method because it makes more sense to me workflow wise. I also try to debug and step into code anytime I can. That all I can think of.

– Glenn

When solving this assignment, I tried my best to follow the documentation and understand why certain tests didn’t pass. I would try different approaches until I figured out what worked and didn’t work.

– Jack

I think my strategy worked for the most part, but in the future, I’ll make sure to review the documentation again, even after the tests are passing, to catch anything that may have been overlooked. I used an automated Google Java Style Guide formatter, and my teammates’ code also appears to follow the Google Java Style Guide.

The most challenging part of this project was probably understanding and implementing the Monster battle mechanics, but it was also the most interesting. It might help to create a state diagram to explain how everything should work together.

Overall, I’m proud of completing this project by implementing code that is clear and concise, while learning more about object-oriented software design in the process. I didn’t do anything to celebrate for this project, but I will be sure to celebrate after the next project, especially since it’s the final project before the holiday break. Maybe I’ll buy a new bike for Christmas, or use the time to work on some personal projects.

Code Review

I reviewed code from Khanh, Glenn, and Jack for the Hangman assignment. There weren’t many major improvements to be made. The assignment was fairly straightforward, so we all followed the instructions and produced similar code. Here are the reviews I shared with my classmates:

Here are some positive trends I noticed about the code I reviewed:

1. All of the tests passed, and the game worked correctly with each student’s code.
2. Adding a conditional to check if a variable is null or a List is empty. It’s important to do this to prevent runtime errors.
3. Using a do-while loop in the chooseWord method. This makes sense because the loop may or may not need to repeat, depending on if the randomly selected word has been guessed already.

There is always room for some improvement though. Here are a couple things I noticed that could be improved:

1. Throwing an error with more specific messages, to help debugging.
2. Making sure to remove TODO comments once they are resolved.
3. Using imports instead of fully-qualified class names (FQCNs).

The reviews I received from my classmates were generally positive. One reviewer mentioned that I could improve my code’s comments by including them throughout the code instead of just using javadoc comments. I agree that it can often be helpful to have comments in code to explain specific parts.

Takeaways

I think the hardest part of this assignment was just wrapping my head around the documentation and how the code is supposed to function. The biggest victory from the assignment for me was developing the practical skill of onboarding to a new codebase. Onboarding to an unfamiliar codebase can often be a challenge, but once you get the hang of it, you can develop strategies to make it easier.

For example, one thing I’ll do is to make sure the code is syntactically correct before implementing any logic. Fixing the syntax errors will usually allow the code to compile, which is always a step in the right direction. From there, it’s a lot easier to focus on getting the tests to pass and following the assignment’s instructions on how to implement the code.

One thing that could help make the code more testable is to have the Hangman class handle its own input, instead of having a separate GameLoader class handle input. Being able to test the entire game end-to-end within a single class would make it easier to verify the complete functionality of the game, so that any issues would be isolated to a single class.

This week, we worked on a few Java projects to better understand OOP concepts. The four pillars of object-oriented programming (OOP) are abstraction, encapsulation, inheritance, and polymorphism, which help to keep code modular, reusable, secure, and maintainable, among other benefits.

1. Abstraction describes the process of hiding complex implementation details and exposing only the necessary features of an object. For example, we designed a Shape interface that exposes an abstract getArea function to be implemented by concrete classes.
2. Encapsulation allows an object to control and restrict access to its own internal state. For example, we developed a simple Hangman game, which used private fields to keep track of the state of the game, like the secretWord that the user tries to guess.
3. Inheritance is the process whereby a subclass can acquire properties and methods from a superclass. For example, we worked on a Pokémon-style game, where different types of subclasses inherit properties from a Monster superclass.
4. Polymorphism means “many forms” and describes how a common interface can behave differently depending on the object to which it is being applied. For example, the different Monster subclasses have common methods that behave differently, depending on which kind of Monster is being used.

We also practiced some software development techniques this week, like test-driven development (TDD) and version control with Git. We used TDD to implement our Java projects according to tests and specifications included with the assignment, in addition to writing our own tests with JUnit. To keep track of changes we made to our repositories, we used the GitHub flow, which involves working on a new feature branch created from the main branch, opening a pull request to merge changes, and then merging the new changes back into the main branch.

This week for our Software Design class, we got our Java development environments set up and worked on some coding exercises using CodingBat.

We started with some straightforward code challenges and then moved on to more difficult ones. I’ve taken a Java course before and have used Java to solve LeetCode problems, so some of these problems were familiar. The hardest part was probably remembering Java syntax and methods, since it’s been awhile since I’ve used the language.

To solve the problems, the first thing I would do is get the code to compile by returning the correct type. For example, if the function is supposed to return a String, I would just have it return an empty String. On CodingBat, this displays all the test cases, which helps with getting an idea of how to solve the problem and figuring out which edge cases to consider.

For simpler problems, I would just start coding out the solution, but for more complex problems, it’s helpful to follow a structured approach. George Pólya’s How to Solve It presents a helpful problem solving framework that can be remembered as UPER:

1. Understand the problem
2. Plan a solution
3. Execute the solution
4. Review and revise

I was able to solve many of the easier problems on the first try, while harder problems took a bit more effort. I set up a Java development environment on my local machine to debug and step through harder problems, which made it easier to see what the issue was.

Reviewing Final Video Projects

This week, we reviewed other teams’ final video projects. Each team made two videos: a short video for a general audience, and a longer video designed for technical professionals.

SB53 – California AI Safety Bill

short video / long video

This team did a great job of introducing this legislation to people who might not be familiar with it. Both presentations were pretty clear and covered the main points of the presentation well. The research and video production were also done well, and they did a great job of making the topic interesting and understandable. One small change I might suggest is to make sure that the speaker’s video doesn’t block the text on slides.

It seems like they coordinated their work pretty well, in terms of who would cover which parts of the presentation. Each speaker had their own presentation style for the longer presentation, which was reasonable, like a conference, while the shorter presentation had a more consistent style. Both videos were appropriate for their intended audience.

It was interesting to learn more about this legislation, and I look forward to hearing more about how it is implemented, especially the CalCompute data centers.

Trend of DeepFake/AI Content Generation

short video / long video

This team delivered a timely introduction to a topic that is becoming more concerning, as AI-content generation tools become more sophisticated. The topic was presented appropriately for its intended audience, although the short video and long video felt pretty similar, with the same background music and template. I would recommend not including background music for the longer presentation, since it was a little distracting.

The video production could use a little work. The material was interesting, and it seems like they did their research on the topic, but some production issues made it difficult to follow.

Drone Delivery Systems

short video / long video

This team understood the assignment. The short video was fun and engaging, while the longer video was more comprehensive and technical.

The first video seemed to use a lot of AI-generated content. It felt like watching a commercial, which worked pretty well. The second video was more like a work presentation/product demo, and it seems like they did a good amount of research. Both videos were appropriate for their intended audiences.

This team seemed to work pretty well together. Both videos felt cohesive and consistent.

Weekly Summary

Our team’s videos are available here: short video / long video

We definitely learned a lot about LLMs in the short time we had to research and produce these videos. I’m grateful for this opportunity to learn more about LLMs, as they are becoming more and more integrated into our daily lives. It’s definitely helpful to know more about how these tools work, so that we can use them more effectively.

I think our team learned a lot about communication and collaboration. We probably could have used more time to work on this, since everyone’s schedule is different. It might have helped to start the project earlier in the term, with a deadline for a rough cut before the final cut.

As much as I appreciate asynchronous work, it probably would have helped to have more meetings. Asynchronous work is great for deep, focused work, but getting in alignment is often easier with meetings. We’ll work on staying in communication and meeting more aggressive deadlines on future projects.