Author: mattchung

  • Operating Systems – Memory Virtualization – Paging

    Operating Systems – Memory Virtualization – Paging

    In my other blog post on memory segmentation, I talked about diving the process’s virtual address space into segments: code, heap, stack. Memory segmentation is just one approach to memory virtualization and another approach is paging. Whereas segmentation divides the address space into segments, paging chops up the space into fixed-sized pieces.

    Each piece is divided into a virtual private number (VPN) and the offset; the number of bits that make up the offset is determined by the size of the page itself and the number of pages dictate the number of bits of the virtual private number.

    To support the translation between virtual address to physical address, we need a page table, a per process data structure that maps the virtual address to the physical frame number (PFN).

    (more…)

  • Word of the day “Notwithstanding”

    Today’s word of the day is “Notwithstanding”.

    Definition – preposition – in spite of

    Example Sentences

    notwithstanding the evidence, the consensus is that the jury will not reach a verdict1

     

    Notwithstanding his nervousness, the young man looked his interviewer directly in the eyes as he answered the questions2

     

    His nervousness notwithstanding , the young man looked his interviewer directly in the eyes as he answered the questions.

     

    Synonyms

    • Nevertheless
    • Nonetheless
    • However

    References

    1. https://www.merriam-webster.com/dictionary/notwithstanding
    2. https://www.grammarly.com/blog/notwithstanding/

     

  • Fear is a Guide

    Fear is a Guide

    While driving to my tennis lesson, I listened to Jared’s (my guitar instructor) video on “Fear is a Guide” and I must say that I love the new direction he is taking on his YouTube channel. He was previously focusing on delivering guitar lessons. Now, he’s honing on what is important to him including song writing and teaching people how to express themselves creatively through music.

    In the video (below), Jared takes the position that if, in the context of music, you are scared of doing something (practicing scales, writing a song, performing in front of people), then that’s the very thing you should be focusing on. Not only do I agree with him 100%, but I think this philosophy or mindset applies to all areas of life.

    In fact, one of my mentors living in Los Angeles had pretty much gave me the same advice:

    If you are not doing something everything that you are afraid of, then you are NOT growing – Phil

    And that advice, I think, is sound. Obviously take that with a grain of salt. Some things you should just straight up be afraid of and avoid, like running into a hungry pack of raccoons in the middle of the night.

  • Memory segmentation

    Memory segmentation

    This blog post contains notes I took on memory segmentation, from “OS in Three Easy Pieces Chapter 16”, one strategy for implementing virtual memory systems. In the next blog post, I’ll cover a different approach: paging.

    16.1 Segmentation: Generalized Base / Bounds

    Summary

    We use segmentation to divide the virtual address space into three distinct segments: code, stack and heap. This technique allows us to accommodate processes with large address spaces.

    16.2 Which segment are we referring to ?

    Summary

    How do hardware know which segment that the request is referring to? Are we requesting memory for stack, heap, or code? Well, there are two approaches: an explicit and implicit approach. For the explicit, we reserve 2 bits at the top of the address. So 00 might refer to code, and 01 might refer to heap, and 10 might refer to the stack. But there’s an implicit approach, too. If the address is based off of the stack base pointer, then we check the stack segment.

    16.3 What about the stack?

    Summary

    Why do we need special consideration for the stack? Because the stack grows backwards, from a higher memory address to lower. Because of this, we need an additional flag to tell the hardware whether the segment grows up or down.

    16.4 Support for sharing

    Summary

    Systems designers realized that with segmenting, processes can share memory with each other. In particular, they could share code segments and in order to support this feature, hardware must add an additional bit to the memory metadata. In particular, the “Protection” field tells us whether or not the segment can be read and executed or can be read and written to. Obviously, for code sharing, we need the segment to be read-execute only.

    16.5 Fine-grained vs Coarse-grained Segmentation Fault

    Summary

    Breaking the address space into (3) segments is considered coarse-grained and some designers preferred a more flexible address space, with a large number of smaller segments, known as fine-grained. The idea behind this was that the designers thought they could learn about which segments were in use and could utilize memory more effectively. Not sure if they were right, though.

    16.6 OS Support

    Summary

    There are two issues with segmentation: a pre-existing problem is how to handle context switches and the second is how to handle external fragmentation? With segmentation, we no longer have a contiguous block of addresses for the process. Instead, we chop them up. So what happens if the stack or heap requires 20KB and although we have 24KB, there’s no continuous space? Well, there are several approaches, the first being extremely inefficient: a background process runs and re-arranges the blocks into contiguous blocks: this approach is extremely inefficient. Another approach is to maintain some sort of free-list and there is a long list of algorithms (e.g. first-fit, worst-fit). Regardless of algorithm, we cannot avoid this issue called external fragmentation.

    16.7 Summary

    Summary

    Segmentation helps accomplish a more effective virtualization of memory but it does not come without cost or complexities. The primary issue is external fragmentation and the second issue is that the if the segments do not line up exactly, then we waste lots of memory.

  • Weekly Review – 2020/08/17 – 2020/08/23

    Weekly Review – 2020/08/17 – 2020/08/23

    • Writing
      • Wrote and published close to a dozen blog posts over the past week, creating a new cadence of bite-sized posts instead of large pieces that sit in draft mode
      • Feeling more confident about my digital organization system, storing all my books and articles and journals consistently, naming them author_year and storing them into DevonThink
    • Graduate School
      • Finished Advanced OS refresher course (threads and file systems and memory systems — skipped over networking module) and posted notes on blog
      • Finished taking notes and watching video lectures from Lesson 1 from Advanced OS course
      • Finished pre-lab assignment on fixing up multi-threaded code (producer/consumer) written with pthread library
    • Health
      • Took 1 hour tennis lesson with Olivia (shoulders and chest sore, that’s a good thing) and most important — produced some sweat
      • Attended my weekly therapy session (mental health: check)
    • Family
      • Bathed Elliott 5 nights this week (1:1 Father and Daughter time)
      • Sang Elliott “Punching in a Dream” while she balanced herself on top guitar neck
      • Visited sister and niece and brother in-law in Renton
      • Shopped with Aunt at Viet Wah, picking up all the ingredients for cooking clay pot fished (vegetarian version)
      • Called dad for his 62nd birthday, despite us not talking for the past two months

    Photos of the week

    Metric the human dog sprawled out across the couch
    Metric the human dog sprawled out across the couch

     

    Little Elliott looking super cute, Mushroom in the background
    Little Elliott looking super cute, Mushroom in the background

    Reflections

    I’d like to find a way to more shave off a few minutes when copying my outline notes from OmniOutliner to WordPress. To this end, perhaps I’ll code up a little python script because right now, copying and pasting and formatting takes an unnecessary 10 minutes, time that I could’ve spent on writing or studying or something else.

     

  • My classmates syllabus in excel form

    My classmates syllabus in excel form

    One of my virtual class mates took the poorly formatted syllabus living on Canvas and converted the document into a beautifully organized excel sheet (above).

    I appreciate him sharing this screenshot since it saves me at least 15 minutes from copying and pasting and wrestling with inevitable formatting issues.  On top of that, I now have a better sense of what to expect over the next 14 weeks of the Fall 2020 term.

    Thanks Luis Batista!

    References

    1 – Piazza Post: https://piazza.com/class/kduvuv6oqv16v0?cid=6_f7

     

  • Snapshotting my understanding before tackling homework assignment #1

    Snapshotting my understanding before tackling homework assignment #1

    Before tackling the homework assignment, I’m going to rate myself on the questions (below), from a scale of 1 (no freaking clue) to 5 (truly understand). The point of this exercise that I just made up myself is that I want to capture my understanding (or lack thereof) at a moment and time. Why do this? Because I know I’ve learned a ton in graduate school (and at work) over the past couple years and it’s easy to lose sight of those little victories and I want to look back (in a few days or in a few weeks) and say “Hey! Look at all your learned!”

    questions from #1 homework assignment (Advanced Operating Systems)
    questions from #1 homework assignment (Advanced Operating Systems)

     

    1. Consider a processor that supports virtual memory. It has a virtually indexed physically tagged cache, TLB, and page table in memory. Explain what happens in such a processor from the time the CPU generates a virtual address to the point where the referenced memory contents are available to the processor.

    (more…)

  • Done with advanced operating systems refresher course

    I’ve finished watching the lectures and taking notes for the operating systems refresher course1 that covers operating system fundamentals, the course covering topics including virtual memory system (e.g. paging, virtually indexed physically tagged) and file systems (e.g. FAT, EXT, inodes) and multi-threaded program (e.g. mutexes, conditional variables, synchronization) and networking2. The notes can be found in the following blog posts:

    Some of the videos really saved my bacon. Without watching the multi-threaded series, I think I would’ve struggled more than necessary on completing the pre-lab homework assignment, which has us students troubleshoot a misbehaving producer/consumer multi-threaded program.

    Reference

    1 – Operating Systems Refresher Course – https://classroom.udacity.com/courses/ud098

    2 – Oh yea, in the title, I included “sort of” because I’m skipping over the networking module. Not because I don’t find the topics interesting (I do), but mainly for two reasons: the interest of time and I think I’m fairly comfortable with those topics (I mean, I did work at Cisco at an network engineer, previously worked in Amazon’s Route53 DNS team and I currently build networking/packet process devices)

  • Little Elliott has found her voice

    Little Elliott has found her voice

    [fvplayer id=”1″]

    Just a short little video milestone of Elliott finding her voice, which sounds raspier than usual since I think she may have overdone it yesterday, making this “ah ah ah” noise for 14 hours.

  • Advanced Operating System Notes (File Systems)

    Advanced Operating System Notes (File Systems)

    Although I’ve covered file systems in previous courses, including graduate introduction of operating systems, I really enjoy learning more about this concept in a little depth.  The file system’s module is packed with great material, the material introducing a high level introduction of file system and then jumps into the deep end unveils what an operating system does behind the scenes.

    Main Take Aways

    • The high level purpose of a file system provides three key abstractions: file, filename and directory tree.
    • A developer can interface with the file system in two ways: a position based (i.e. cursor) and a memory based (i.e. block)
    • C function strol converts a string to a long
    • Mmap system calls maps a file on the file system to a contiguous block of memory (the second method a developer can interface with a file systeme)
    • FAT (file allocation table) glues and chains disk blocks together. It is essentially a linked list (persisted as a busy bit vector table) that is great for sequential reads (i.e. traversing the linked list) but awful for random access (i.e. to get to the middle, need to traverse from head)
    • EXT linux file system is based on inodes and improves random access using 12 direct pointers (13th pointer provides first level of indirection, 14th pointer second level of indirection, 15th pointer third level of direction)
    • Learned about the buffer cache (i.e. write-through) and how we a journal can help stabilize the system while maintaining decent performance
    Linked list and busy bit table
    Linked list and busy bit table

    (more…)