Posts

2025 2025-12-28 building simcity 2025-12-26 https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-mechanisms.pdf kernel stack is stack used by the kernel. lol. in some sense it’s a fake distinction - the only difference between user stack vs. kernel stack is privilege https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf FIFO = simple, but long-running first task causes long average turnaround shortest job first = also simple, but a long task that comes first also causes long average turnaround shortest time to completion first = scheduler determines which of the jobs on the docket has the least amount of time left; adds complexity of preemption https://www.fabiensanglard.net/quakeSource/ fish that ate the whale 2025-12-25 fish that ate the whale 2025-12-24 https://podcasts.apple.com/us/podcast/how-hudson-river-trading-actually-uses-ai/id1056200096?i=1000734391225 2025-12-23 https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-api.pdf https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-mechanisms.pdf 2025-12-21 https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-intro.pdf

Last time, I was asking myself what the point of using RDTSCP was. Why shouldn’t I just call RDTSC and call it a day? How to Benchmark Code Execution Times (Intel Guide) explains the problem: When we call the RDTSC instruction, we pretend that the instruction will be executed exactly at the beginning and at the end of code being measured. The solution is to call a serializing instruction before calling the RDTSC one. A serializing instruction is an instruction that forces the CPU to complete every preceding instruction… before continuing the program execution. ...

TSC is a register that increments on every CPU tick. RDTSC is the assembly instruction that reads TSC into EDX:EAX. RDTSCP is the assembly instruction that reads TSC into EDX:EAX and also reads the processor ID (IA32_TSC_AUX) into ECX. Equivalent to doing RDTSC + RDPID in a single instruction. Benchmarking a critical session of code is probably as simple as start = rdtsc() // get current counter value .... beep boop, executing code .... cycles = rdtsc() - start // theoretically the number of cycles But things are, of course, a little more complicated. ...

An optimization of free() using boundary tags Last week, I was concerned about the performance of the coalescing algorithm. In particular - could I be smarter about coalescing by trading off memory for time? Memory is “cheap”, so I’m happy to store some extra bytes that facilitate the coalescing process. As a reminder, the two embedded data structures in the heap: struct FreeBlockHeader { size_t size; // size of free space FreeBlockHeader* next; // location of next free block }; struct AllocBlockHeader { size_t size; // size of allocated space }; The coalescing algorithm works by continuously comparing the head of the free list with every other node in the free list - until no more coalescing is possible. ...

In v0, we made the simplifying assumption that all the data we work with are fixed-size blocks. Now, we’re going to relax the assumption: data can now be requested in any size. Our simplifying assumptions meant that we didn’t have to track how much free space is available; we could just iterate over the blocks until we found one that was marked as empty. The problem with variable sizes is that now, we need to do some bookkeeping. When we request memory, our memory allocator needs to know: ...

For the next couple weeks, we’re going to write a memory allocator. I’m dumb, so I need to start from dead-simple problem constraints and work my way up to increasingly complex constraints. As such, we’ll write this allocator in stages. What is the memory allocation problem? Every process gets allocated memory - but some memory demands are more dynamic than others. This means that the programmer must bear responsibility over memory allocation. ...