Author: mattchung

  • Making sense of the “sense reversing barrier” (synchronization)

    Making sense of the “sense reversing barrier” (synchronization)

    What’s the deal with a sense reversing barrier? Even after watching the lectures on the topic, I was still confused as to how a single flag could toggle between two values (true and false) can communicate whether or not all processes (or threads) are running in the same critical section. This concept completely baffled me.

    Trying to make sense of it all, I did some “research” (aka google search) and landed on a great article titled Implementing Barriers1.  The article contains source code written in C that helped demystify the topic.

    Sense Reversal Barrier. Credit: (Nkindberg 2013)

     

    The article explains how each process must maintain its own local sense variable and compare that variable against a shared flag. That was the key, the fact that each process maintains its own local variable, separate from the shared flag. That means, each time a process enters a barrier, the local sense toggles, switching from 1 to 0 (or from 0 to 1), depending on the variable’s last value. If the local sense variable and the shared flag differ, then the process (or thread) must wait before proceeding beyond the current barrier.

    For example, let’s say process 0 initializes its local sense variable of 0. The process enters the barrier, flipping the local sense from 0 to 1. Once the process reaches the end of the critical section, the process compares the shared flag (also initialized to 0) with its local sense variable and since the two do not equal to one another, then that process waits until all other processes complete.

    References

    1. Nkindberg, Laine. 2013. “Implementing Barriers.” Retrieved September 17, 2020 (http://15418.courses.cs.cmu.edu/spring2013/article/43).
  • Crashing and burning during lunch & Daily Review – Day ending in 2020/09/16

    Crashing and burning during lunch & Daily Review – Day ending in 2020/09/16

    I had mentioned yesterday that I slept horribly, waking up early and starting day off at around 03:45 AM. That wake up time was brutal and as a result, I crashed and burned in the afternoon, leveraging those precious 30 minutes of my lunch to nap in my wife’s / daughter’s bedroom (a room with an actual mattress, unlike my office, where I’m sleeping on the floor on top of a tri-folding piece of foam).

    I slept so well during that afternoon nap that I didn’t hear the ear piercing alarm that I set on my TIMER YS-390 ; luckily I warned my wife before hand and had asked her to wake me up just in case I overslept. Thankfully she did.

    Yesterday, I had suspected that I woke up so early and slept so poorly due to the loud air conditioner shaking on and off throughout the night, but I’m 100% confident of what woke me up this morning at 03:00: my daughter belting out a loud scream (and then immediately fell back asleep).

    Yesterday

    I’m in great company while working from home. Here’s metric sleeping by my foot

    Writing

    • Published my daily review

    Best parts of my day

    • The afternoon 30 minute nap. Seriously. The nap makes me wonder how I would’ve taken that sort of break if I were not working remote and if I were working back in the office?

    Mental and Physical Health

    • Attended my weekly therapy session with good old Roy. As anticipated, we followed up on our tension filled conversation that occurred last week. What was comforting and brought me solace was that he opened up (just a little) and shared that he was similar to me in the sense that he often will take on additional work that just needs to be done, a person who sees a hole and fills it. That conversation made me think of the term transference: “a phenomenon in which an individual redirects emotions and feelings, often unconsciously, from one person to another.”

    Graduate School

    • Watched no lectures yesterday (as mentioned, I was like a zombie) and instead ran my programs (i.e. virtual CPU scheduler and memory coordinator) across the various use cases, collecting all the terminal output that I’ll need to include as part of the submission

    Work

    • Conducted an “on site” interview. I say onsite but because of COVID-19, all interviews are held over (Amazon) Chime.
    • Debugged an unexpected drop in free memory and realized that it pays off to be able to distinguish memory allocations happening on the stack versus memory allocations happening else where (like shared memory in the kernel).

    Family and Friends

    Miscellaneous

    • Got my second hair cut this year (damn you COVID-19) at nearby hair salon. I love the hair salon for a multiple reasons. First, the entire trip — from the moment I leave my house, to the moment I return back — takes 30 minutes, a huge time saver. Second, the stylist actually listens to what I want (you’d be surprised how many other stylists get offended when I tell them what I want and what I don’t want) and gives me a no non-sense hair cut. And third, the hair cut runs cheap: $20.00.  What a steal! I don’t mind paying more for hair cuts (I was previously paying triple that price at Steele Barber).

    Today

    Mainly will just try to survive the day and not collapse from over exhaustion. If I can somehow afford the time, I’d like to nap this afternoon for half an hour. Will gladly trade off 30 minutes of lunch if that means not being zapped of all my energy for the remainder of the day.

    Writing

    • Publish “Synchronization” notes (part 2)
    • Publish daily review (this one that I’m writing right here)

    Mental and Physical Health

    Graduate School

    Work

    • 1:1 meeting with my manager Tim
    • Follow up with fuzzing issue and determine whether or not the issue can be reproduced on other hosts

    Family

    • Respond to my brother-in-law, who I shared my article with and who wants to get into writing and asked me what tools he suggests
  • Synchronization notes (part 2/2) – Linked Based Queuing lock

    Synchronization notes (part 2/2) – Linked Based Queuing lock

    In part 1 of synchronization, I talked about the more naive spin locks and other naive approaches that offer only marginally better performance by adding delays or reading cached caches (i.e. avoiding bus traffic) and so on. Of all the locks discussed thus far, the array based queuing lock offers low latency, low contention and low waiting time. And best of all, the this lock offers fairness. However, there’s no free lunch and what we trade off performance for memory: each lock contains an array with N entries where N is the number of physical CPUs. That high number of CPUs may be wasteful (i.e. when not all processors contend for a lock).

    That’s where linked based queuing locks come in. Instead of upfront allocating a contiguous block of memory reserved for each CPU competing for lock, the linked based queuing lock will dynamically allocate a node on the heap and maintain a linked list. That way, we’ll only allocate the structure as requests trickle in. Of course, we’ll need to be extremely careful with maintaining the linked list structure and ensure that we are atomically updating the list using instructions such as fetch_and_store during the lock operation.

    Most importantly, we (as the OS designer that implement this lock) need to carefully handle the edge cases, especially while removing the “latest” node (i.e. setting it’s next to NULL) while another node gets allocated. To overcome this classic race condition, we need to atomically rely on a new (to me at least) atomic operation: compare_and_swap. This instruction will be called like this: compare_and_swap(latest_node, me, nil). If the latest node’s next pointer matches me, then set the next pointer to NIL. Otherwise, we know that there’s a new node in flight and will have to handle the edge case.

    Anyways, check out the last paragraph on this page if you want a nice matrix that compares all the locks discussed so far.

    Linked Based Queuing Lock

    Summary

    Similar approach to Anderson’s array based queueing lock, but using a linked list (authors are MCS: mellor-crummey J.M. Scott). Basically, each lock has a qnode associated with it, the structure containing a got_it and next. When I obtain the lock, I point the qnode towards me and can proceed into the critical section

    Link Based Queuing Lock (continued)

    Summary

    The lock operation (i.e. Lock(L, me)) requires a double atomic operation, and to achieve this, we’ll use a fetch_and_store operation, an instruction that retrieves the previous address and then stores mine

    Linked Based Queuing Lock

    Summary

    When calling unlock, code will remove current node from list and signal successor, achieving similar behavior as array based queue lock. But still an edge case remains: new request is forming while current thread is setting head to NIL

    Linked Based Queuing Lock (continued)

    Summary

    Learned about a new primitive atomic operation called compare and swap, a useful instruction for handling the edge of updating the dummy node’s next pointer when a new request is forming

    Linked Based Queuing Lock (continued)

    Summary

    Hell yea. Correctly anticipated the answer when professor asked: what will the thread spin on if compare_and_swap fails?

    Linked Based Queuing Lock (continued)

    Summary

    Take a look at the papers to clarify the synchronization algorithm on a multi-processor. Lots of primitive required like fetch and store, compare and swap. If these hardware primitives are not available, we’ll have to implement them

    Linked Based Queuing Lock (continued)

    Summary

    Pros and Cons with linked based approach. Space complexity is bound by the number of dynamic requests but downside is maintenance overhead of linked list. Also another downside potentially is if no underlying primitives for compare_and_swap etc.

    Algorithm grading Quiz

    Comparison between various spin locks

    Summary

    Amount of contention is low, then use spin w delay plus exponential backoff. If it’s highly contended, then use statically assigned.

  • Tired like a zombie & Daily Review – Day ending in 2020/09/15

    Tired like a zombie & Daily Review – Day ending in 2020/09/15

    Today is going to be rough. I slept horribly, waking up multiple times throughout the night. Ultimately, I rolled out of my tri-folding foam mattress (a temporary bed while my daughter and wife sleep on the mattress in a separate room as to not wake me up: that parent life) at 03:45 AM this morning. Perhaps the gods above are giving me what I deserve since I had complained yesterday that I had “slept in” and as a result didn’t get a chance to put in any meaningful work before work. So now they are punishing me. Touché. Touché.

    Yesterday

    Fell into a black hole of intense focus while hunting down a bug that was crashing my program (for project 1 of advanced operating systems).  Sometimes I make the right call and distance myself from a problem before falling into a viscous mental loop and sometimes (like this scenario) I make the right call and keep at a problem and ultimately solve it.

    Writing

    Best parts of my day

    A poop explosion. Elliott’s nugget rolling out of her diaper and landing on the bathroom floor. Making us two parents chuckle
    • Teaching Elliott how to shake her head and signal “no”. For the past few months, I’ve tried to teach her during our daily bathes but when I had tried to previously teach her, her body and head were not cooperating with her. When she had tried say no, she was unable to interdependently control her head movement, her entire body would turn left and right along with her. But yesterday, she got it and now, she loves saying “no” even though she really means yes. She’s so adorable.
    • Jess yelling out for me to rush over to the bathroom to help her … pick up Elliott’s poop that rolled out of her diaper, two nuggets falling out, one landing on the tile floor while the other smashing on the floor mat
    • Catching up over the phone with my friend Brian Frankel. He’s launched a new start up called Cocoon, his company aiming to solve the problem of slimy mushrooms and slimy strawberries in the refrigerator. I had bought one of his new inventions mainly to support his vision (it’s always nice to support friends) but also I’m a huge fan of refrigerator organization and cleanliness.  Unfortunately, the box arrived broken (looks like something heavy in the delivery truck landed on the box, crushing it into pieces)

    Mental and Physical Health

    • At the top of the hour (not every hour, unfortunately) I hit the imaginary pause button, pulling my hands off the keyboard and stepping back from my standing desk to stretch my hamstrings and strengthen my hips with Asians squats

    Graduate School

    • Watched no lectures yesterday, all the time (about 2 hours) dumped into polishing up the virtual CPU scheduler, adding a new “convergence” feature that skips the section of code that (re)pins the virtual CPUs to physical CPUs, skipping when the standard deviation falls 5.0% (an arbitrary number that I chose)
    • Wrestled with my program crashing. The crashes’s backtrace was unhelpful since the location of the code that had nothing to do with the code that I had just added.

    Work

    • Attended a meeting lead by my manager, the meeting reviewing the results of the “Tech Survey”. The survey is released by the company every year, asking engineers to answer candidly to questions such as “Is your work sustainable?” or “Is your laptop’s hardware sufficient for your work?”. Basically, it allows the company to keep a pulse of how the developer experience is and is good starting point for igniting necessary changes.
    • Stepped through code written by a principle engineer, C code that promised to bound a binary search by trading off 2 bytes to serve as an index.

    Family and Friends

    • Fed Elliott during my lunch. Was extremely tiring (but at the same time, enjoyable) chasing her around the kitchen floor, requiring me constantly squat and constantly crawl. She’s mobile now, working her way up to taking one to two steps.
    • Bathed Elliott last night and taught her how to touch her shoulders, a body part she’s been completely unaware of. Since she loves playing with my wedding right, I let her play with during our night time routine and last night I would take the ring, and place the ring on her infant sized shoulder, pointing to it and guiding her opposite hand to reach out to grab the ring.
    • Caught up with one of our friends over Facetime. Always nice to see a familiar face during COVID-19, a very isolating experience that all of society will look back on in a few years, all of us wondering if it just all a bad dream because that’s what it feels like

    Miscellaneous

    • Got my second hair cut this year (damn you COVID-19) at nearby hair salon. I love the hair salon for a multiple reasons. First, the entire trip — from the moment I leave my house, to the moment I return back — takes 30 minutes, a huge time saver. Second, the stylist actually listens to what I want (you’d be surprised how many other stylists get offended when I tell them what I want and what I don’t want) and gives me a no non-sense hair cut. And third, the hair cut runs cheap: $20.00.  What a steal! I don’t mind paying more for hair cuts (I was previously paying triple that price at Steele Barber).

    Today

    Mainly will just try to survive the day and not collapse from over exhaustion. If I can somehow afford the time, I’d like to nap this afternoon for half an hour. Will gladly trade off 30 minutes of lunch if that means not being zapped of all my energy for the remainder of the day.

    Writing

    • Publish “Synchronization” notes (part 2)
    • Publish daily review (this one that I’m writing right here)

    Mental and Physical Health

    Graduate School

    • Write up the README for the two parts of my project
    • Change the directory structure of project 1 so that the submission validator passes
    • Submit the project to Canvas
    • Watch 30 minutes worth of lectures (if my tired brain can handle it today)

    Work

    • Interview a candidate “on-site” later this afternoon
    • Continue troubleshooting unreproducible fuzzing failure (will try to tweak our fuzzer for a potential out of memory issue)

    Family

    • Pack a couple more boxes with Jess. Only a couple more weeks and we move our family unit into a new home in Renton.
  • Synchronization (Notes) – Part 1

    Synchronization (Notes) – Part 1

    I broke down the synchronization topic into two parts and this will cover material up to and including the array based queuing lock. I’ll follow up with part 2 tomorrow, which will include the linked list based queuing lock.

    There a couple different types of synchronization primitives: mutual exclusion and barrier synchronization. Mutual exclusion ensures that only one thread (or process) at a time can write to a shared data structure, whereas barrier synchronization ensures that all threads (or processes) reach a certain point in the code before continuing. The rest of this summary focuses on the different ways we as operating system designers can implement mutual exclusion and offer it as a primitive to system programmers.

    To implement a mutual exclusion lock, three instructions need to be bundled together: reading, checking, writing. These three operations must happen atomically, all together and at once. To this end, we need to leverage the underlying hardware’s instructions such as fetch_and_set, fetch_and_increment, or fetch_and_phi.

    Whatever way we implement the lock, we must evaluate our implementation with three performance characteristics:

    • Latency (how long to acquire the lock)
    • Waiting time (how long must a single thread must wait before acquiring the lock)
    • Contention (how long long to acquire lock when multiple thread compete)

    In this section, I’ll list each of the implementations ordered in most basic to most advanced

    • Naive Spin Lock – a simple while loop that calls test_and_set atomic operation. Downside? Lots of bus traffic for cache invalidation or cache updating. What can we do instead?
    • Caching Spin Lock – Almost identical to the previous  implementation but instead of spinning on a while loop, we spin on a read, followed by a check for test_and_set. This reduces noisy bus traffic of test_and_test (which again, bypasses cache and writes to memory, every time)
    • Spinlock with delay – Adds a delay to each test_and_test. This reduces spurious checks and ensures that not all threads perform test_and_set at the same time
    • Ticket Lock – Each new request that arrives obtains a ticket. This methodology is analogous to a how a deli hands out tickets for their customers; it is fair but still signals all other threads to wake up
    • Array based queuing lock – An array that is N in size (where N is the number of processors). Each entry in the array can be in one of two states: has lock and must-wait. Fair and efficient. But trades off space: each lock gets its own array with N entries where N is number of processors. Can be expensive for machines with thousands of processors and potentially wasteful if not all of them contend for the lock

    Lesson Summary

    Summary

    There are two types of locks: exclusive and shared lock. Exclusive lock guarantees that one and only one thread can access/write data to a location. Shared allows multiple readers, but guaranteeing no other thread is writing at that time.

    Synchronization Primitives

    Summary

    Another type of synchronization primitive (instead of mutual exclusion) is a barrier. A barrier basically ensures that all threads reach a certain execution point and only then can the threads advance. Similar to real life when you get to a restaurant and you cannot be seated until all your party arrives. That’s an example of a barrier.

    Programmer’s Intent Quiz

    Summary

    We can write that enforces barrier with a simple while loop (but its inefficient) using atomic reads and writes

    Programmer’s Intent Explanation

    Summary

    Programmer’s Intent Quiz

    Because of the atomic reads and writers offered by the instruction set, we can easily use a flag to coordinator between processes. But are these instructions sufficient for creating a mutual exclusion lock primitive?

    Atomic Operations

    Summary

    The instruction set ensures that each read and write operation is atomic. But if we need to implement a lock, there are three instructions (read, check, write) that need to be bundled together into a single instruction by the hardware. This grouping can be done in one of three ways: test_and_set or (generically) fetch_and_increment or fetch_and_phi

    Scalability Issues with Synchronization

    Summary

    What are the three types of performance issues with implementing a lock? Which of the two are under the control of the OS designer? The three scalability issues are as follows: latency (time to acquire lock) and waiting time (how long does a thread wait until it acquires the lock) and contention (how long does it take, when all threads are competing to acquire lock, for lock to be given to a single thread). The first and third (i.e. latency and contention) are under the control of the OS designer. The second is not: waiting time is largely driven by the application itself because the critical section might be very long.

    Naive Spinlock (Spin on T+S)

    Summary

    Why is the SPIN lock is considered naive? How does it work? Although the professor did not explicitly call out why the SPIN lock is naive, I can guess why (and my guess will be confirmed in the next slide, during the quiz). Basically, each thread is eating up CPU cycles by performing the test and test. Why not just signal them instead? That would be more efficient. But, as usual, nothing is free so there must be a trade off in terms of complexity or cost. But returning back to how the naive scheduler works, it’s basically a while loop with the test_and_test (semantically guaranteeing on a single thread will receive the lock).

    Problems with Naive Spin Lock

    Problems with naive spinlock

    Summary

    Spin lock is naive for three reasons: too much contention (when lock is released, all threads, maybe thousands, will jump at the opportunity) and does not exploit cache (test and set by nature must bypass cache and go straight to memory) and disrupts useful work (only one process can make forward progress)

    Caching Spinlock

    Caching Spin lock (spin on read)

    Summary

    To take advantage of the cache, processors will first call while(L == locked), taking advantage of the cache. Once test_and_set occurs, all processors will then proceed with test_and_set. Can we do better than this?

    Spinlocks with Delay

    Summary

    Any sort of delay will improve performance of a spin lock when compared to the naive solution

    Ticket Lock

    Summary

    A fair algorithm that uses a deli or restaurant analogy: people who come before will get lock before people who come after. This is great for fairness, but performance still lacking in the sense that when a thread releases its lock, an update will be sent across the entire bus. I wonder: can this even be avoided or its the reality of the situation?

    Spinlock Summary

    Array-based queuing lock

    Summary

    A couple differentiations toptions 1) Read and Test and Test (no fairness) 2) Test and Set with Delay (no fairness) 3) Ticket Lock (fair but noisy). How can we do better? How can we only signal one and only thread to wake up and attempt to gain access to the lock? Apparently, I’ll learn this shortly, with queueing locks. This lesson reminds me of a conversation I had with my friend Martin around avoiding a busy while() loop for lock contention, a conversation we had maybe about a year or so ago (maybe even two years ago)

    Array Based Queuing Lock

    Summary

    Create an array that is N in size (where N is the number of processors). Each entry in the array can be in one of two states: has lock and must-wait. Only one entry can ever be in has-lock state. I’m proud that I can understand the circular queue (just by looking at the array) with my understanding of the mod operator. But even so, I’m having a hard time understanding how we’ll use this data structure in real life.

    Array Based Queuing Lock (continued)

    Summary

    Lock acquisition looks like: fetch and increment (queue last) followed by a while(flags[mypalce mod N] == must wait). Still not sure how this avoids generating cache bus traffic as described earlier…

    Array-based queue lock

    Summary

    Array-basd queuing lock (mod)

    Using mod, we basically update the “next” entry in the array and set them to “has_lock”

  • Honoring my body’s internal alarm clock & Daily Review – Day ending in 2020/09/14

    Honoring my body’s internal alarm clock & Daily Review – Day ending in 2020/09/14

    This morning my body woke me up later than usual. After a few blinks, I squeezed the corner of my Casio G-Shock watch, the green background lighting up and shining the time: 05:55 AM. Ugh. About an hour later than I wanted to wake up.

    On one hand, I’m bummed because I won’t be able to squeeze in as much uninterrupted time before work but on the other hand, my body and brain probably needed the extra sleep. Otherwise, why “sleep in” ?  I try to honor and listen to my body’s signals, another reason why over the past 5 years I’ve stopped setting an alarm clock and instead permitted my body to wake up naturally, whenever my body is ready.

    Oh well. Let’s get cracking.

    Yesterday

    Writing

    Best parts of my day

    • My co-worker unintentionally making me chuckle. During my team’s daily stand up meeting yesterday, I had asked my co-workers how they were coping with all the smoke blanketing the Seattle skies. And my co-worker’s response caught me by surprise. She said that back home in India, there’s always a thick cloud of smoke always resting above their heads and really, the wildfire smoke in Seattle reminds her of home.

    Mental and Physical Health

    • Yesterday I resumed my ritual of switching back and forth between sitting and standing (thank you Jarvis standing desk). At the top of every hour, I try to hit the imaginary pause button and stretch my hamstrings by reaching for the ground with my finger tips. Not much exercise but every little bit counts.

    Graduate School

    • Started watching Barrier synchronization lectures. It’s so amazing how deep I am diving into computer science. I really do enjoy learning how to an OS system designer (maybe me somebody) implements primitive structures such as mutual exclusion and barrier synchronization.
    • Started updating virtual CPU scheduler code to support the notion of “convergence”. The idea is that if the underlying physical CPU utilization ever so slightly deviate (that exact percentage is yet to be determined) then the scheduler should leave them as is and not try to re-balance the work load.

    Work

    • Scheduled an ad-hoc meeting with a principle engineer that took place that day, the two of us troubleshooting a fuzzing failure, the worst kind of failures: failures that cannot be reproduced.
    • Read a design proposal written up by a different principle engineer who evaluated different types of data structures. Realized that the data structure that I had envisioned us using will not meet performance requirements for IPv6 traffic

    Family

    • Took dogs on a very short walk of about 15 minutes at the local park. I skipped walking them over the weekend because of the thick smoke but the two puppies were getting a bit restless so I compromised, sacrificing a (hopefully) very tiny bit of our long term health in order to get them the physical stimulation they needed for the rest of the day

    Today

    Quote of the day

    Have you ever felt out of place in your place?

    I pulled that quote from a rap line from the song Breathing (Part 2) by Hamzaa featuring Wretch 32 & Ghetts.

    Most of my life, I always felt “out of place”. One instance of being out of place was during my teenage years and being one of the only (or perhaps the only) Vietnamese kids attending Calabasas high school, a high school where mostly everyone is white and where everyone thinks they are white.

     

    Writing

    • Publish “Synchronization” notes
    • Publish daily review (this one that I’m writing right here)

    Mental and Physical Health

    • Won’t be running in this smoke so instead, let’s spend 2 minutes (really, that’s all) throughout the day to get the heart pumping. Maybe some jumping jacks or some push ups. And of course, stretching the hamstrings and hip rotators while working behind by standing desk

    Graduate School

    • Fix memory leak with my recent additions to the CPU scheduler
    • Start writing up documentation that will accompany the submission for project 1
    • Watch 15-20 minutes worth of lectures from the barrier synchronization series

    Work

    • Meetings and meetings and meetings (not a really fun day) of sprint planning, Asians@ planning and development meetings, interview debrief

    Miscellaneous

    • Hair cut at 4:00 PM. This will be the second hair cut this year, the last one taking place in June. Obviously I’m trying to minimize unnecessary interactions with other people but damn, I look like a shaggy dog with my heavy and coarse hair weighing me down.
  • Shared Memory Machine Model (notes)

    Shared Memory Machine Model (notes)

    You need to take away the following two themes for shared memory machine model:

    • Difference and relationship between cache coherence (dealt with in hardware) and cache consistency (handled by the operating system)
    • The different memory machine models (e.g. dance hall, symmetric multiprocessing, and distributed shared memory architecture)

    Cache coherence is the promise delivered by the underlying hardware architecture. The hardware guarantees employs one of two techniques: write invalidate or write update. In the latter, when a memory address gets updated by one of the cores, the system will send a message on the bus to invalidate the cache entry stored in all the other private caches. In the former, the system will instead update all the private caches with the correct data. Regardless, the mechanism in which cache is maintained is an implementation detail that’s not privy to the operating system.

    Although the OS has not insight into how the hardware delivers cache coherence, the OS does rely on the cache coherence to build cache consistency, the hardware and software working in harmony.

    Shared Memory Machine Model

    Summary

    Shared memory model - Dance Hall Architecture
    Shared memory model – Dance Hall Architecture
    Symmetric multiprocessing – each processor’s time to access to the memory is the same
    Shared Memory Machine Model – each CPU has its own private cache and its own memory, although they can access each others addresses

    There are three memory architecture: dance hall (each CPU has its own memory), SMP (from perspective of each CPU, access to memory is the same as other CPU), and Distributed shared memory architecture (some cache and some memory is faster to access for a given CPU). Lecture doesn’t go much deeper than this but I’m super curious as to the distributed architecture.

    Shared Memory and Caches

    Summary

    Because each CPU has its own private cache, we may run into a problem known as cache coherence. This situation can occur if the caches tied to each CPU contain different values for the same memory address. To resolve this, we need a memory consistency model.

    Quiz: Processes

    Summary

    Quiz tests us by offering two processes, each using shared memory, each updating different variables. Then the quiz asks us what are the possible values for the variables. Apart from the last one, all are possible, the last one would break the intuition of a memory consistency model (discussed next)

    Memory consistency model

    Summary

    Introduces the sequential consistency memory model, a model that exhibits two characteristics: program order and arbitrary interleaving. This Isi analogous to someone shuffling a deck of cards.

    Sequential Consistency and cache coherence (Quiz)

    Summary

    Cache Coherence Quiz – Sequential Consistency

    Which of the following are possible values for the following instructions

    Hardware Cache Coherence

    Summary

    Hardware Cache Coherence

    There are two strategies for maintaining cache coherence. Write invalidate and write update. In the former, the system bus will broadcast an invalidate message if one of the other cache’s modifies an address in its private cache. In the latter, the system must will send an update message to each of the cache’s, each cache updating it’s private cache with the correct data. Obviously, the lecture oversimplifies the intricacies of maintaining a coherent cache (and if you want to learn more, check out the high performance computing architecture lectures — or maybe future modules in this course will cover this in more detail)

    Scalability

    Summary

    Scalability – expectation with more processors. Pros: Exploit Parallelism. Cons : Increased overhead

    Adding processors increase parallelism and improves performance. However, performance will decrease due to additional overhead of maintaining the bus (another example of making trade offs and how nothing is free).

  • Losing 2 hours searching for a website bookmark & Weekly Review: week ending in 2020/09/06

    Losing 2 hours searching for a website bookmark & Weekly Review: week ending in 2020/09/06

    My weekly review that normally takes place first thing in the morning on Sundays was completely derailed this time around, all because I could find the URL to a website that I had sworn I bookmarked for my wife’s birthday present. I ended up coughing up two hours of searching: searching directly on Reddit’s website (where I was 100% confident I stumbled upon the post), searching through 6 months of my Firefox browser history, and searching through 20 or so pages of Google Results.

    I ultimately found the page after some bizarre combination of keywords using Google, the result popping up on the 6th page of Google (I would share the URL with you but I want to keep it tucked away for the next two week until my wife’s birthday or at least until her present arrives and I gift it to her).

    How about you — when you stumble on something interesting on the internet, what steps do you take to make sure that you can successful retrieve the page again in the future? Do you simply bookmark the page using your browser’s built in bookmark feature? Do you tag that the entry with some unique or common label? Or do you store it away in some third party bookmarking service like pinboard? Or maybe you archive the entire contents of the page offline to your computer using DevonThink? Or something else?

    So many options.

    Ultimately, I don’t think the tool itself really matters: I just need to save the URL in a consistent fashion.

    Writing

    Family and Friends

    [fvplayer id=”3″]

    • Got around to finally calling my Grandma and video chatting with her so that she could see Elliott, who has grown exponentially over the last couple months
    • Signed off on tons of paper work for the new house and pulled the trigger on selling a butt load of my Amazon stocks that will cover the down payment and the escrow costs that we’re going to get hit with on September 30th (my wife’s birthday)
    • Packed about 5 more boxes worth of our belongings (e.g. books, clothing, kitchen goods)

    Music

    • Recorded about 5 different melodies and harmonies using the voice memo app on my iPhone, moving the recordings off my phone and sending them to my MacBook using AirDrop)
    • Attended my (zoom) bi-weekly guitar lesson with Jared, the lessons focusing on three areas: song writing (creative aspect), jamming (connecting with other musicians, mainly my little brother), developing a deeper understanding of the guitar (mastery).

    Mental and Physical Health

    Graduate School

    • I’d estimate I put in roughly 15 hours into graduate school in order to read research papers, write code for project 1 (i.e. writing a virtual CPU scheduler and memory coordinator) and of course watch the Udacity lectures.
    • For the development project, majority of time gets eaten up trying to grok the API documentation to libvrt. In second place would be debugging crashes in my code (which is why I always riddle my code with assert statements, a practice I picked up working at Amazon).
    • I really enjoyed watching and taking notes for this past week’s lectures. I’m taking the class at the perfect time in my career and in my graduate studies, after taking graduate operating systems and after taking high performance computing architecture. Both these courses prepared me well and provided me the foundation necessary to more meaningfully engage with the lectures. What I mean by this is that instead of passively watching and scribbling down notes, I tend to frequently click on the video to pause the stream and try to anticipate what the professor is about to say or try to answer the questions he raises. This active engagement helps the material stick better.

    Organization

    Brother label maker
    • Tossed out the cheap $25.00 label marker from Target and instead invested in a high quality Brother PTD600V label maker. Well worth the investment.
    • Culled my e-mail inbox, dropping the unread count from hundreds down to zero (will need to perform same activity this week)

    Work

    • Wrapped up my design for a new feature long, getting sign off from the technical leadership team at work. Only open action item will be to benchmark the underlying Intel DPDK’s library against IPv6 look ups (which I think I already have data for)
  • Remembering September 11 & Daily Review (day ending on 09/11/2020)

    Remembering September 11 & Daily Review (day ending on 09/11/2020)

    Yesterday was September 11. On this day, every year, Americans grieve and we are all reminded of the unforgettable day back in 2001 when the New York twin towers collapsed to the ground after being struck by the hijacked planes.

    I sure remember the day.

    I was about 12 years old at the time and on that weekday morning — like every other morning —  I was sitting crossed legged in front of our living room television, eating cereal and watching cartoons (“Recess”, the best cartoon ever) before walking to school as a sixth grader. While balancing a spoonful of cereal and milk into my mouth, the channel on the CRT television switched unexpectedly to live news, news that was live streaming the planes nose diving into the New York twin towers, bringing the towers to their knees. As a child, I didn’t understand the implication of it all and I just remember burrowing my eyebrows and shrugging my shoulders, shutting off the television and heading to school.

    The day following September 11 were unforgettable: there was an uptick of both subtle and not so subtle racism against Muslims.

    Back then, my best friend’s name was Osama, and I recall an incident that still makes my blood boil 20 years later. Him and I along with 20 or so other innocent children were packed in the classroom, all of us waiting for our substitute teacher to arrive (not sure why exactly our teacher was absent that day). The teacher for the day, white male aged about 40-50 years old, and was taking roll call, working his way down the list of student’s names on the clipboard resting in his hands.

    As he was running his finger down the list, he paused on Osama’s name, slowly lifting his gaze. He then spat out some flagrant racist comment, asking whether or not my 12 year old friend was a Jihad. Us student were stunned, confusion rippled throughout the room. And poor Osama, his head down in shame.

    Being his best friend, I took it upon myself and I marched out the room, heading full speed towards the principle’s office. After arriving at his office, I explained the situation. What happens afterwords gets a bit fuzzy but I do recall never seeing that substitute teacher again.

    This story reminds me the importance of speaking up for others, something I wrestle with these days. Lately, I bite my tongue because as an adult, realizing that it’s easy these days to offend people and I’m constantly evaluating the unique situation, taking in the context and trying to determine whether or not me speaking up for someone is warranted. Eh, it’s a never ending learning process.

    Yesterday

    Writing

    Best parts of my day

    • Singing and playing guitar during lunch break with the the entire wolf pack. Sang my acoustic rendition of “Punching in a dream”
    • Watching an episode of “The Boys” with Jess while eating dinner.  We both found the episode to be unnecessarily violent (no spoilers).

    Mental and Physical Health

    • Sprinted full speed up and down the hill for about 2 minutes, all while wearing a mask (not only to protect myself again COVID-19, but because to prevent breathing in the wildfire smoke blanketing the entire pacific northwest). Apparently, cotton masks do not block smoke particles so I apparently inhaled some amount of smoke (I deserved my wife reprimanding me for running under these conditions)

    Graduate School

    • Finished the “balancing” aspect of memory optimizer. My initial code was riddled with bugs, the program dropping the memory too fast and too much, causing the underlying guest operating systems to (presumable) swap and crash

    Work

    • Back to back to meetings. Mostly administrative, a few with some value.
    • This was one of the rare (very rare) days where I ate lunch at my desk. I don’t want to make that a habit and cherish lunch time, the one hour of the day where my wife and I and get to (sort of) peacefully eat lunch with our daughter.
    • During sprint planning, our scrum master (a colleague on my team) was driving the conversation and asking during our retrospective how we could “improve” our velocity. I shared with her and everyone else that although I am always up for improving our performance and striving to deliver, I wanted to call out the big elephant in the room: we’re in the midst of a pandemic. Things are not okay. Things are not normal
    • Cherry-picked some of my git commits into other feature branches that our team will be deploying over the next few weeks

    Today

    Writing

    • Publish notes on CPU and device virtualization
    • Publish daily review (this one that I’m writing right here)
    • Publish the terminal output from the memory coordinator test cases and their expected outcomes

    Music

    • Upload all the little melodies and harmonies captured on my iPhone.

    Organization

    • Review OmniFocus’s forecast tab to get a sense of what meetings I have this week and any items that are due soon

    Mental and Physical Health

    Poor air quality due to wildfire smoke
    • Stay inside as much as possible and limit outdoor activity (will only walk the dogs) due to wildfire smoke. In lieu of outside exercise, I’ll throw down some push ups, some pull ups (with the door pull up bar) and some light hamstring stretches

    Graduate School

    • Finish the “optimizer” portion of my memory coordinator
    • Finish the lecture on “Synchronization” (fascinating and challenging topic that reminds me of high performance computing architecture course, the concepts very similar)

    Family

    • Pack up the house into our cardboard moving boxes
    • Bathe Elliott for our night time routine
    • Sing and play guitar during lunch again (what a treat that was yesterday)
    • Sign the final real estate contract for the new house that we are buying in Renton
    • Attempt to sell some of my Amazon stocks since we need the cash for our down payment for the house (not sure if socks can be sold over the weekend but let’s just and find out)
    • Follow up with landlord over text since they did not respond to my e-mail that I had sent around regarding ending our lease since we are moving
  • CPU and Device Virtualization (notes)

    CPU and Device Virtualization (notes)

    This post is a continuation of virtualization. In the previous post, I talked about memory virtualization. This post instead discusses CPU and device virtualization.

    Ultimately, as system designers, one of our chief aims is to provide an illusion to the underlying guest operating systems that they each individually won the underlying hardware, the CPU and IO devices. But how do will the guest OS transfer control back and forth to and from the hypervisor?

    In a fully virtualized environment (i.e. guest OS has no awareness that it is virtualized), the guest operating communicates to the hypervisor via the standard way: sending traps. Unfortunately, this leaves little room for innovation, which is why in a para virtualized environment (i.e. guest OS contains specific code to communicate with the hypervisor) optimizes the communication by sharing a ring buffer (i.e. producer and consumer model)

    Through this shared buffer, the guest VM and hypervisor send messages to one another, the messages containing pointers — not raw data — to buffer allocated by the either the guest operating or allocating by the hypervisor. This efficient method of communication prevents the need to copy buffers between the two entities.

    Introduction

    Summary

    With CPU virtualization, there are two main focuses: giving the illusion to the guest that it owns the CPU and having the hypervisor field events (but what the hell is a discontinuity) ?

    CPU Virtualization

    Summary

    Two techniques for CPU scheduling. Proportional share (commensurate with use) and fair share scheduler: everyone gets the same slice of the pie.

    Device Virtualization Intro

    Summary

    Want to give guest illusion that they own the IO devices

    Device Virtualization

    Device Virtualization: full virtualization vs Para

    Summary

    In a fully virtualized guest OS, there’s little room to innovate for device IO since the mechanism is really just a trap and emulate (by the hypervisor). In contrast, para virtualization offers lots of opportunities for optimization, including utilizing shared buffers. However, we need to figure out how to transfer control back and forth between the guest OS and the hypervisor

    Control Transfer

    Summary

    In a full virtualization environment, control from guest to hypervisor happens through a trap. Whereas in the para virtualization, the guest OS sends hyper calls. However, in both full and para virtualization, the hypervisor communicates to the guest OS via software interrupts.

    Data Transfer

    Summary

    Data Transfer in para virtualization uses a ring buffer for producer/consumer model

    Data transfer in a para virtualization system is fascinating: the guest VM and the hypervisor share a IO circular buffer. The guest VM produces data and the hypervisor consumes it, the guest VM maintaining a pointer to the position of the data. And in the response path, the hypervisor maintains a pointer, on the same IO circular buffer, that tracks the responses (and where the guest VM tracks a private buffer)

    Control and Data Transfer in Action

    Summary

    Control and Data Transfer in Action – ring buffers for transmitting and receiving packets

    Pretty amazing how the hypervisor and guest VM work together to avoid copying data between address spaces. To this end, the guest VM will transmit data by maintaining a circular buffer and copy the pointers into the hypervisor, so no data is copied (just pointers). Same approach in the opposite direction, when hypervisor receives packet and then forwards it to the guest.

    Disk IO Virtualization

    Summary

    Disk Virtualization – ring buffer

    Pretty much identical to data transfer in network IO virtualization. Except that Xen offers a reorder barrier to support higher level semantics like write ahead logging (a topic that seems really interesting to me: I’d be curious how to build a database from the ground up)

    Measuring Time

    Summary

    Fundamental tenet is utility computing so we need a way to accurately bill users

    Xen and guests

    Summary

    Xen and guest – paravirtualization

    Xen offers para virtualization and VMWare offers fully virtualization (i.e. guest VM has no clue). Regardless, virtualization focuses on protection and flexibility, trading off performance