diff options
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/umich/img/w24_wrapup/482_submission.png | bin | 0 -> 96194 bytes | |||
| -rw-r--r-- | docs/umich/img/w24_wrapup/482_website.png | bin | 0 -> 118775 bytes | |||
| -rw-r--r-- | docs/umich/index.md | 1 | ||||
| -rw-r--r-- | docs/umich/w24_482.md | 356 | ||||
| -rw-r--r-- | docs/umich/w24_wrapup.md | 16 |
5 files changed, 373 insertions, 0 deletions
diff --git a/docs/umich/img/w24_wrapup/482_submission.png b/docs/umich/img/w24_wrapup/482_submission.png Binary files differnew file mode 100644 index 0000000..969a11a --- /dev/null +++ b/docs/umich/img/w24_wrapup/482_submission.png diff --git a/docs/umich/img/w24_wrapup/482_website.png b/docs/umich/img/w24_wrapup/482_website.png Binary files differnew file mode 100644 index 0000000..dc80170 --- /dev/null +++ b/docs/umich/img/w24_wrapup/482_website.png diff --git a/docs/umich/index.md b/docs/umich/index.md index ecb443b..9174997 100644 --- a/docs/umich/index.md +++ b/docs/umich/index.md @@ -5,3 +5,4 @@ so basically i live in ann arbor now - [Lessons in the US of A](us_lessons.md) - [Fall 2023 Wrapup](f23_wrapup.md) - [Fall 2023 winter break wrapup](f23_winter_break.md) +- [Winter 2024 Wrapup](w24_wrapup.md) diff --git a/docs/umich/w24_482.md b/docs/umich/w24_482.md new file mode 100644 index 0000000..5fb6d2b --- /dev/null +++ b/docs/umich/w24_482.md @@ -0,0 +1,356 @@ +# Winter 2024 Course Review: EECS 482 (4 credit) + +2024-04-30 + +Course Title: Introduction to Operating Systems + +Rating: 4/5 + +## Instructor (Brian Noble) + +Pros: + +- Talks clearly +- Has a schedule +- Lots of interesting stories so you learn something even if you fail 482 + (see [Trivia](#trivia) + +Cons: + +- Practically none? + +## What did I learn? + +Course topics: + +- Threads and concurrency + - Mutexes & condition variables + - Semaphores + - CPU scheduling +- Virtual memory + - Address spaces + - Page tables + - Page replacement (swapping) +- Filesystems + - inodes + - Consistency after crashing +- Network + - Sockets + - Client-server model + - Distributed systems +- Miscellaneous + - RAID + - LFS (log-structured filesystem) + +Brian constantly brought up the five tools of computer science: + +1. Caching +2. Hashing +3. Indirection +4. Replication +5. Encryption + +482 discusses 1 and 3 in great detail, 2 and 4 occasionally. The +philosophical takeaway is: + +- Whenever you have something to protect, add a layer of indirection (e.g. + using virtual addresses for user programs) +- If there's too much data to copy, also use indirection +- It can't be indirection all the way down; there must be something fixed + by convention (e.g. the first sector being the bootloader) +- If indirection gets slow, add caching +- If you want consistency, use replication (e.g. RAID with redundancy) + +The course is all about abstraction: + +- Threads are abstractions for CPUs +- Virtual memory is an abstraction for physical memory +- Filesystems are abstractions for disks +- Sockets are abstractions for network interfaces + +Part of abstraction design is to provide user programs with the illusion +that resource is infinite. A process can spawn thousands of threads on an +8-core machine, and they take turns to execute, thanks to the OS +scheduler. Of course, at some point the context switching overhead +overshadows the benefits of parallelism, but you _could_. + +Another job of the OS is to protect a program from other programs. You +can't trust user programs. Therefore you must build a layer of abstraction +so that the user program can never "control" the machine. The three things +a user program is allowed to do: + +- Touch its own property, e.g. address space, open files +- Touch property that another process explicitly shared with it +- Transfer control back to the OS with a syscall + +The point is that the OS is an absolute tyrant. A user program can never +run for as long as it likes, nor can it touch anything other than what +it's explicitly allowed to. To achieve this, the OS conspires with the +hardware so that it can intervene when certain things happen: + +- Every few milliseconds, the timer interrupt fires, transferring control + over the CPU to the OS +- The program issues a load/store marked unreadable/unwritable, and the + MMU triggers a page fault, also handled by the OS + +Although the timer and the MMU are technically part of hardware, they +always hand over control to the OS. They're part of the abstraction. +Without the timer, it would be up to a user program to give up the CPU, +which makes it really easy to freeze a machine. Without the MMU, user +programs would use direct addressing, enabling anyone to tamper with +anyone's memory. + +However, the OS can bypass either restriction, and it is the only one +allowed to do so. When a timer interrupt fires and hands control over to +the OS, the first thing the OS does is to disable the interrupt, so the OS +itself gets to run for as long as it likes. Once its job is done, it +re-enables the interrupt, and hands control back to a user program (may +not be the same one). We don't give user programs the ability to control +interrupts; not MMU either. + +We just discussed the first half of the course. The second half was less +mind-bending and more optimization trickery with "make the common case +fast" heuristics. However we did make a big deal about consistency. + +The disk only guarantees block writes are atomic. Therefore, if you need +to write two blocks to disk and you lose power halfway, you could have +written zero, one, or two blocks. That basically means you just lost two +blocks of data, because you're unsure either block is the right version. +Worst case is you end up breaking essential metadata, which corrupts the +entire filesystem. + +We can play clever tricks like careful ordering of block writes so the +last block we write "commits" the changes. But when this is not possible, +due to cyclical dependencies, we came up with the notion of journaling, +which doubles the cost of writes because we always keep a copy of the data +we're writing in the journal until we're sure these data made it where +they belong. Where is the journal? On disk. At this point I was convinced +that disks just suck. We're paying 100% overhead just to handle the 0.001% +chance that the machine crashes. But to deliver the "persistent storage" +promise, we have to pay that cost. + +The disk is just a big pool of zeroes and ones — and as such there is no +way to distinguish a block of metadata and a block of data. You have to +allocate a static location as the "boss of metadata"; for example, writing +the root inode to block 0, from which we can discover every descendent, as +we did in project 4. + +### Personal reflections + +The reason why I enrolled in the course is all my friends did it. It was +taught by Manuel, one of the "signature" professors we had at JI, +Shanghai. It's one of the most challenging courses there ever was, so +being the arrogant boy, I took it. Peer pressure except it was me who +pressured myself into taking it. + +The most mind-blowing chapter, also the one I once had the most incorrect +understanding about, is virtual memory. + +Rewind to 2021, when I was taking VG151, intro to CS. I had no idea what +virtual memory was, and was amazed that `malloc` always handed me roughly +the same address every time, beginning with `0x7fff` or something, as if +that part of the RAM was always free. I had mistakenly thought that all +processes share one big heap on the physical memory, and `malloc` had +a global table of free chunks. It does not. Each process has its own +address space, and the user program does not know, nor does it care, where +it lives on physical memory. + +The MMU also explains a gap in my brain. Prior to this course, I thought +the OS would translate memory addresses of a program before it ran (which +is not possible because you can dynamically allocate memory). Now it +became clear that there is a dedicated piece of hardware that does the +translation. + +## Projects + +Project 1 is solo, 2-4 are done in a group of two or three; mine was +three. We were enrolled in the 4-credit version of 482, which means we're +only required to do the core version, which is supposedly less work. + +We met Mondays and/or Wednesday mornings at 10 AM at the Duderstadt. It +was a great excuse to spend money on muffins and coffee at the cafe. +Nearly every time we sat at the same table with a giant screen. There was +an HDMI cable but it doesn't work. I ended up opening a Zoom meeting. + +Of the three autograders I've used at UMich, this is the least visually +interesting one, besides only allowing one submit per day with feedback, +plus three bonus submissions for each project. + + + +It does fit in the brutalist aesthetic of the website. + + + +### Project 1: Multithreaded disk scheduler + +Given mutexes and condition variables, build a disk scheduler. + +Not that hard, took me a few tries to get used to the paradigm of +signaling _after_ work is done. + +### Project 2: Thread library + +We built our own threads, mutexes, and condition variables. We also get to +decide what happens in a timer interrupt. + +The hardest part was taking care of all the `ucontext_t` objects, which +can't be moved because they contain pointers to themselves. We had trouble +keeping track of which stacks and which `ucontext_t`s we could delete, +because the lifetime of the `thread` object is unrelated to that of the +thread's execution flow. We ended up playing pointer tricks, which is +basically shared pointers with extra steps. + +Here is a snippet of code I wrote at 2024-02-20 00:30: + +``` +void thread::delete_context(ucontext_t *context) { + auto it = cpu::self()->stacks.find(context); + assert(it != cpu::self()->stacks.end()); + // delete stack of thread that previously died + // like burying your sibling's bones + // pour one out for the binary spirits + // freed from deallocated homes + delete[] cpu::self()->stack_to_delete; + // we cannot simply delete the stack + // of the thread that is running + // for a ghastly segfault taketh us aback + // with a coredump equally alarming + cpu::self()->stack_to_delete = it->second; + cpu::self()->stacks.erase(it); + delete context; +} +``` + +Another design mistake is how we used the `ucontext_t` pointer in the +mutex as a unique identifier for threads. It turns out the instructors +were so cunning that they managed to make our library allocate +a `ucontext_t` exactly where one was just deleted, tricking our library +into thinking the new thread owned the mutex. I still have a hard time +believing it was possible. They probably overloaded `operator new` on +a modded version of `ucontext_t`. + +I was very involved in project 2; I wrote more than half of the code, and +thus knew it like the back of my hand. + +### Project 3 + +Virtual memory pager. Manages memory address translation, paging, and +swapping. Lots of data structures needed, even a state diagram. + +I grossly underestimated the complexity. The first time I read the specs, +I was like, "pfft! single level page tables?" But it was the hardest +project for me. + +Unlike project 2, project 3 had much less effort from me. All I did was +draw the state diagram and propose the data structures and their names. +Then I got consumed by 373 and the workload shifted to Samuel who +basically did it all on his own. Therefore I don't understand it as +thoroughly as project 2. By the end of project 3 I was completely lost. + +The data structures were a complete mess. Here is a list of structs we +defined: + +- `shadow_table_entry_t` +- `filename_block_t` +- `page_occupant_t` +- `file_occupant_t` +- `swap_occupant_t` +- `page_status_t` + +which are distinct and redundant in a chaotic way. It's a miracle we +passed all the test cases. + +The lack of involvement resulted in a relatively poor understanding of the +pager, so I devoted more energy to project 4. + +### Project 4 + +Network filesystem. Listens on a TCP port and handles concurrent +read/write/create/delete requests from clients. + +I think I did a pretty good job at factoring out just the redundant code +while handling special cases in respective functions. Fortunately we just +have four request types (endpoints) to handle, so a little redundancy is +ok. + +My least favorite part of this project is how strictly we had to enforce +the one request string format. The request string is delimited with _one +space_. No leading or trailing whitespace. All this while claiming that +parsing is "is amenable for processing by `istringstream` (e.g., +`operator>>`)". My sibling in heaven, `istringstream` is not the one you +want if whitespace is significant. I ended up using regexes, because it's +preferable to having to read one character at a time while constantly +checking whether you've exhausted the string stream. I regret nothing. + +Project 4 was the first time I actually used RAII in a productive way. +Because every filesystem access is a traversal down a tree, and we want to +prevent race conditions, every descent requires that we grab a lock and +release a lock. Some are reader locks and some are writer locks. This is +cumbersome to manage manually, so I wrote an RAII wrapper that keeps track +of what locks we are currently holding and what type of locks they are. At +the end of the object lifetime, the destructor simply goes over the list +and unlocks them one by one. If we call a function that needs to +lock/unlock, we simply pass the wrapper by reference. Easy! + +I'm not sure if this is healthy, but I cringe whenever someone optimizes +code to "fit the scenario at hand". In the early stage of the project, +I wrote a function called `alloc_block()`, which takes void and returns +the block number just taken out of a pool. Later we realized that if an +operation needs two allocs, but failed in between, then the first one +would never be freed. We thought it would be better if we could atomically +alloc two blocks, so I suggested my teammate to generalize the function to +take one optional parameter and return potentially more than one block. + +When the function was reimplemented, I found that it was not quite what +I meant. I was thinking something along the lines of + +``` +std::vector<uint32_t> alloc_block(uint32_t count = 1); +``` + +What it ended up being was + +``` +std::pair<uint32_t, uint32_t> alloc_block(uint32_t count = 1); +``` + +which returns the allocated block # in the _second_ element of the pair if +`count == 1` (because it kinda fits our semantics better), and returns two +valid block #s if `count != 1`. + +I feel uncomfortable that `count` did not function as advertised; it +behaved more like a bool. But since we're using our late days (it's the +first time I ever used a late day) and we're tired, I let it slide. + +## Verdict + +Now that I've taken the course, done the projects and sit through the +exams, I do not regret taking this course. I do, however, regret taking it +with two more workload EECS courses, one of which (373) is also +heavy-workload. + +I would recommend Brian Noble to anyone, no questions asked. He is my GOAT +professor of the semester. The slides follow the +motivation-solution-problem-remedy train, which tightly model the actual +evolution of real systems in the e.g. 1980s. It's interesting to know what +came before modern systems and what Linus Torvalds et al. needed to take +care of when they crafted the revolutionary kernel. + +## Trivia + +Brian always has stories to tell. My favorite story is how when he was +young, his advisor talked to him about his unnecessarily complex wording +in his paper. I personally do believe the doctrine, "why many word when +few word do trick". + +Later on a lecture on log-based filesystems, he had a callback to the +story. He goes (paraphrased): + +> What I lament about project 2 is, the right way to identify who owns the +> mutex is to add something to your data structure. But you never do that. +> What you do is you add another map. So what you end up with a lot of +> suprooflo- su- sur- (waves hand) I can't say it. Uhh… extra. My advisor +> would be happy about that. Extra maps. diff --git a/docs/umich/w24_wrapup.md b/docs/umich/w24_wrapup.md new file mode 100644 index 0000000..0f4baf7 --- /dev/null +++ b/docs/umich/w24_wrapup.md @@ -0,0 +1,16 @@ +# Winter 2024 wrapup + +2024-04-30 + +My second semester at UMich is just over, and I will recount major things +that happened. I will continuously update this blogpost. + +## Course reviews + +The biggest mistake that I made is that I elected three EECS courses, two +of which are extra heavy in workload. The rest are not trivial either. It +is impossible to cover all of them in one single blogpost, so I will split +them up into individual articles, listed below. + +- [EECS 482, Intro to OS](w24_482.md) +- Other courses WIP |
