Matt Chung's Site

Author: mattchung

  • Weekly Review: week ending in 2020/09/06

    Weekly Review: week ending in 2020/09/06

    Another installment of my weekly reviews. I think the practice of carving out around 30 minutes on Sunday to look back at the previous week and look forward for the next week helps me in several ways. First, the posts help me recognize my tiny little victories that I often neglect and they also help me appreciate everything in my life that are easy to take for granted (like a stable marriage and healthy children and a roof over our heads and not having to worry about my next pay check).  Second, these weekly rituals tend to reduce my anxiety, giving me some sense of control over the upcoming week that will of course not go according to plan.

    Looking back at last week

    Writing

    Things I learned

    • How static asserts are great way to perform sanity checks during compilation and are a great way to ensure that your data structures fit within the processor’s cache lines
    • Learned a new type of data structure called a n-ary tree (used for the MCS tree barrier)
    • Learned about the different ways to implement mutual exclusion and ways to implement barrier synchronization (thanks advanced operating systems course)
    • Read C code at work that helped sharpen my data structure skills since I saw first hand how in production code we trade off space for performance by creating a index that bounds the range for a binary search

    Family and Friends

    • Taught Elliott had to shake her head (i.e. say “No”). Probably the biggest mistake this week since she’s constantly shaking her head (even though she’s trying to say “yes”). Does teaching her how to touch her shoulders balance out teaching her how to say no?
    • Finally was able to book Mushroom an appointment to get her groomed (with COVID-19, Petsmart grooming was closed for time). I felt pretty bad and even tried cutting parts of her fur myself because patches of her hair were getting tangled and she was itching at them and giving herself heat rashes
    • Chased Elliott around the kitchen while trying to feed her spoonfuls of broccoli and potato that Jess cooked up for her. I believe the struggle of Elliott not sitting still during lunch is karma, payback for all the times when I was her age and made my parents chase me around
    • Watched several episodes of Fresh off the boat while eating dinner with Jess throughout the week. We are really enjoying this show and I find the humor relatable as a Vietnamese American man that grew up around the same time frame of the show.
    • Video chatted with some old familiar faces and these social interactions were actually the best parts of my day. I need to do this more: reach out to people and just play catch up
    • Packed packed packed and sorted out administrative stuff like printing out statements proving the transaction from Morgan Stanley to Wells Fargo and obtaining home insurance and reading through contracts for the new house that we’ll be moving into in less than 2 weeks

    Mental and Physical Health

    • Attended my weekly therapy session and was comforted when my therapist shared that he was like me in the sense that we often take on work that just needs to get done, and this similarity between the two of us may explain why tensions built up between the two of us the previous week
    • Did not exercise at all really because of the wildfire smoke blanketing the pacific north west. Luckily, yesterday the weather cleared up so I will take advantage of the fresh air
    • Got a hair cut. Originally, I categorized getting a hair cut underneath the miscellaneous section but upon reflection, I find grooming oneself and taking care of our physical appearance (not in vein) actually positively impacts our mental health (or negatively if we don’t treat ourselves). It really is easy to let oneself go, especially during the pandemic.

    Graduate School

    • Submitted Project 1 on virtual CPU scheduler and memory coordinator
    • Learned a ton from watching lectures on mutual exclusion and barrier synchronization (see section above on What I Learned)
    • Finished watching most of the lecture series on parallel systems but still need to finish Scheduling and Shared Memory Multiprocessor OS

    Music

    • Guitar lesson with Jared last Sunday. Focused on introducing inversions as a way to spice things up with my song writing.
  • Barrier Synchronization (Part 2/2)

    Barrier Synchronization (Part 2/2)

    Part 1 of barrier synchronization covers my notes on the first couple types of synchronization barriers including the naive centralized barrier and the slightly more advanced tree barrier. This post is a continuation and covers the three other barriers: MCS barrier, tournament barrier , dissemination barrier.

    Summary

    In the MCS tree barrier, there are two separate data structures that must be maintained. The first data structure (a 4-ary tree, each node containing a maximum of four children) handling the arrival of the processes and the second data structure handling the signaling and waking up of all other processes. In a nutshell, each parent node holds pointers to their children’s structure, allowing the parent process to wake up the children once all other children have arrived.

    The tournament barrier constructs a tree too and at each level are two processes competing against one another. These competitions, however, are fixed: the algorithm predetermines which process will advanced to the next round.  The winners percolate up the tree and at the top most level, the final winner signals and wakes up the loser. This waking up of the loser happens at each lower level until all nodes are woken up.

    The dissemination protocol reminds me of a gossip protocol. With this algorithm, all nodes detect convergence (i.e. all processes arrived) once every process receives a message from all other processes (this is the key take away); a process receives one (and only one) message per round. The runtime complexity of this algorithm is nlogn (coefficient of n because during each round n messages, one message sent from one node to its ordained neighbor).

    The algorithms described thus far share a common requirement: they all require sense reversal.

    MCS Tree Barrier (Binary Wakeup)

    MCS Tree barrier with its “has child” vector

    Summary

    Okay, I think I understand what’s going on. There are two separate data structures that need to be maintained for the MCS tree barrier. The first data structure handles the arrival (this is the 4-ary tree) and the second (binary tree) handles the signaling and waking up of all the other processes. The reason why the latter works so well is that by design, we know the position of each of the nodes and each parent contains a pointer to their children, allowing them to easily signal the wake up.

    Tournament Barrier

    Tournament Barrier – fixed competitions. Winner holds the responsibility to wake up the losers

    Summary

    Construct a tree and at the lowest level are all the nodes (i.e. processors) and each processor competes with one another, although the round is fixed, fixed in the sense that the winner is predetermined. Spin location is statically determined at every level

    Tournament Barrier (Continued)

    Summary

    Two important aspects: arrival moves up the tree with match fixing. Then each winner is responsible for waking up the “losers”, traversing back down. Curious, what sort of data structure? I can see an array or a tree …

    Tournament Barrier (Continued)

    Summary

    Lots of similarity with sense reversing tree algorithm

    Dissemination Barrier

    Dissemination Barrier – gossip like protocol

    Summary

    Ordered communication: like a well orchestrated gossip like protocol. Each process will send a message to ordained peer during that “round”. But I’m curious, do we need multiple rounds?

    Dissemination Barrier (continued)

    Summary

    Gossip in each round differs in the sense the ordained neighbor changes based off of Pi -> P(I + 2^k) mod n. Will probably need to read up on the paper to get a better understanding of the point of the rounds ..

    Quiz: Barrier Completion

    Summary

    Key point here that I just figured out is this: every processor needs to hear from every other processor. So, it’s log2N with a ceiling since N rounds must not be a power of 2 (still not sure what that means exactly)

    Dissemination Barrier (continued)

    Summary

    All barriers need sense reversal. Dissemination barrier is no exception. This barrier technique works for NCC and clusters.Every round has N messages. Communication complexity is nlogn (where N is number of messages) and log(n). Total communication nlogn because N messages must be sent every round, no exception

    Performance Evaluation

    Summary

    Most important question to ask when choosing and evaluating performance is: what is the trend? Not exact numbers, but trends.

  • How to convert .heic images to .jpeg using command line on MacBook

    How to convert .heic images to .jpeg using command line on MacBook

    My wife’s apple iPhone X saves images she captured with her camera as .heic format1 , a relatively new file format that compresses high quality images and I needed a way to convert these type of files to .jpeg (which apparently dates back to 1992) so that they can be uploaded to my blog and eventually rendered by your browser.

    After some googling, I discovered that my MacBook ships with the sips command line (scriptable image processing system) and the tool provides all the functionality I need. Each image that sips process takes about a second so that’s not too bad when bulk converting photos.

    SIPs Command

    $ sips -s format jpeg --resampleWidth <resolution> <source> --out <destination>

    Example

    Below is an example of the command that I ran to convert images for my blog, converting the image to a minimum of 1200 pixels (in width).

    % sips -s format jpeg --resampleWidth 1200 IMG_1043.HEIC --out 2020-09-15-elliotts-nuggets.jpeg
    /Users/matthewchung/Downloads/IMG_1043.HEIC
    /Users/matthewchung/Downloads/2020-09-15-elliotts-nuggets.jpeg

    References

    1. https://www.howtogeek.com/345314/what-is-the-heif-or-heic-image-format/
  • Finally clean air & Daily Review – Day ending in 2020/09/18

    Finally clean air & Daily Review – Day ending in 2020/09/18

    Hooray! Today is the first day in a couple weeks that air quality is considered good, at least according to the EPA. I’m so pleased and so grateful for clean air because my wife and daughter have not left the house since the wild fires started a week ago (or was it two weeks — I’ve lost concept of time since COVID hit) and today marks the first day we can as an entire family can go for a walk at a local park (it’s the little things in life) and breathe in that fresh, crisp pacific northwest air. Of course, we’ll still be wearing masks but hey, better than staying cooped up inside.

    Yesterday

    What I learned yesterday

    • Static assertion on C structures.  This type of assertion fires off not at at run-time but at compile time.  By asserting on the size of a structure, we can ensure that they are sized correctly. This sanity check can be useful in situations such as ensuring that your data structure will fit within your cache lines.

    Writing

    • Published my daily review that I had to recover in WordPress since I had accidentally deleted the revision

    Best parts of my day

    • Video chatting at the end of the work day with my colleague who I used to work with in Route 53, the organization I had left almost two years ago.  It’s nice to speak to a familiar face and just shoot the shit.

    Graduate School

    • Finished lectures on barrier synchronization (super long and but intellectually stimulating material)
    • Started watching lectures on lightweight RPC (remote procedure calls)
    • Submitted my project assignment
    • Met with a classmate of mine from advanced operating systems, the two of us video chatting over Zoom and describing our approaches to project 1 assignment

    Work

    • Finished adding a simple performance optimization feature that takes advantage of the 64 byte cache lines, packing some cached structs with additional metadata squeezed into the third cache line.

    Miscellaneous

    • Got my teeth cleaned at the dentist. What an unusual experience. Being in the midst of the pandemic for almost 8 months now I’ve forgotten what it feels like to talk to someone up close while not wearing a mask (of course the dentist and dental hygienist were wearing masks) so at first I felt a bit anxious. These days, any sort of appointments (medical or not) are calculated risks that we must all decide for ourselves.

    Today

    Writing

    • Publish Part 1 of Barrier Synchronization notes
    • Publish this post (my daily review)
    • Review my writing pipeline

    Mental and Physical Health

    • Slip on my Freebird shoes and jog around the neighborhood for 10 minutes. Need to take advantage of the non polluted air that cleared up (thank you rain)
    • Swing by the local Cloud City coffee house and pick up a bottle of their in house Chai so that I can blend it in with oat milk at home.

    Graduate School

    Organization

    • Review my tasks and project and breakdown the house move into little milestones

    Family

    • Take Mushroom to her grooming appointment. Although I put a stop gap measure in place so that she stops itching and wounding herself, the underlying  issue is that she needs a haircut since her hair tends to develop knots.
    • Walk the dogs at either Magnuson or Marymoore Park. Because of the wild fires, everyone (dogs included) have been pretty much stuck inside the house.
    • Pack pack pack. 2 weeks until we move into our new home in Renton. At first, we were very anxious and uncertain about the move. Now, my wife and I are completely ready and completely committed to the idea.

     

     

  • Barrier Synchronization (Part 1/2)

    Barrier Synchronization (Part 1/2)

    As mentioned previously, there are different types of synchronization primitives that us operating system designers offer.  If as an application designer you nee to ensure only one thread can access a piece of shared memory at a time, use a mutual exclusion synchronization primitive. But what about a different scenario in which you need all threads to reach a certain point in the code and only once all threads reach that point do they continue? That’s where a barrier synchronization comes into play.

    This post covers two types of barrier synchronizations. The first is the naive, centralized barrier and the second is the a tree barrier.

    In a centralized barrier, we basically have a global count variable and as each thread enters the barrier, they decrement the shared count variable.  After decrementing the count, threads will hit a predicate and branch: if the count is not zero, then the thread enters a busy spin loop, spinning while the count is greater than zero. However, if after decrementing the counter equals zero, then that means all threads have arrived at the end of the barrier synchronization.

    Simple enough, right? Yes it is, but the devil is in the details because there’s a subtle bug, a subtle edge case. It is entirely possible (based off of the code snippet below) that when the last thread enters the barrier and decrements the count, all the other threads suddenly move beyond the barrier (since the count is not greater than zero). In other words, the last thread never gets to reset the count back to N number of threads.

    How to avoid this problem? Simple: add another while loop that guarantees that the threads do not leave the barrier until the counter gets reset. Very elegant. Very simple.

    One way to optimize the centralized barrier is to introduce a sense reversing barrier (as I described in “making sense of the sense reversing barrier”).

    The next type of barrier is a tree barrier. The tree barrier groups multiple process together at multiple levels (number of levels is logn where n is the number of processors), each group maintaining its own count and local sense variables. The benefit? Each group spins on its own locksense. Downside? The spin location is dynamic, not static and can impede performance on NUMA architectures.

    Centralized Barrier

    Centralized Barrier

    Summary

    Centralized barrier synchronization is pretty simple: keep a counter that decrements as each thread reaches the barrier. Every thread/process will spin until the last thread arrives, at which point the last thread will reset the barrier counter so that it can be used later on

    Problems with Algorithm

    Summary

    Race condition: last thread, while updating the counter, all other threads move forward

    Counting Barrier

    Summary

    Such a simple and elegant solution by adding a second spin loop (still inefficient, but neat nonetheless). Sense reverse barrier algorithm

    Sense Reversing Barrier

    Sense Reversing Barrier

    Summary

    One way to optimize the centralized barrier is to introduce a sense reversing barrier. Essentially, each process maintains its own unique local “sense” that flips from 0 to 1 (or 1 to 0) each time synchronization barrier is needed. This local variable is compared against a shared flag and only when the two are equal can all the threads/processes proceed past the current barrier and move on to the next

    Tree Barrier

    Tree Barrier

    Summary

    Group processes (or threads) and each group has its own shared variables (count and lock sense). Before flipping the lock sense, the final process needs to move “up to the next level” and check if all other processors have arrived at the next level. Things are getting a little more spicy and complicated with this type of barrier

    Tree Barrier (Continued)

    Summary

    With a tree barrier, a process arrives at its group (of count and lock sense), and will decrement the count variable and will then check the lock sense variable. If lock sense is not equal, then spin. If last

    Tree Barrier (continued)

    Summary

    Once the last process reaches the root, it’s their responsibility to begin waking up the lower levels, traversing back down the tree. At each level, they will be flipping the lock sense flag

    Tree Barrier (Continued)

    Summary

    As always, there’s a trade off or hidden downside with this implementation. First, the spin location is not statically determined. This dynamic allocation may be problematic, especially on NUMA (non uniformed memory access architecture) architecture, because a process may be spinning on a remote memory location. But my question is, are there any systems that do not offer coherence?

  • On letting go & Daily Review – Day ending in 2020/09/17

    With working remote and establishing a (somewhat) daily routine (that has become pretty monotonous), it’s sometimes easy to forget that we’re in the midst of a global pandemic. But that reality is amplified because of the recent wild fires, forcing those of us living in the pacific north west (PNW) — and those living in Northern California — to remain indoors.  This additional layer of lock down definitely impacts the mental health for both my wife and I. I’m almost certain that not breathing in fresh air from outside negatively affects my 11 month year old daughter, who has not stepped (or carried) outside this past week — not even for a few minutes.  I really want her to join me for the daily walks with the dogs, even if it is for a few minutes, but my wife and I agreed that’s its best for the long term if she doesn’t inhale any of the ashes trickling down from the sky.

    Source: https://www.kingcounty.gov/depts/health/covid-19/data/key-indicators.aspx

     

    On Letting Go

    Unrelated to the above comment about the pandemic, I was reading Write it down make it happen on my Kindle while sitting on the can (you’d be surprised how much reading you can get done during your trips to the bathroom) and there’s a section in the book that suggests sometimes the way to make things happen is to simply let go of the reins and relegate all control.

    On some level, I agree that sometimes you’ll find the very thing you’ve been looking for when you stop searching. This concept rings true to me because during my mid twenties, I stopped searching for “the one” and instead, began looking inward and healing myself (my life was spiraling out of control due to my compulsive and addictive behavior) and on the path to recovery, I ended up meeting the one, my now wife, the two of us bumping into each other while volunteering at a children’s orphanage (she often jokes and tells people that I adopted her …  not everyone gets the joke).

    Yesterday

    What I learned yesterday

    • Learned a new data structure called n-ary tree (i.e. each node can have up to N children). Picked up this new graph theory inspired data structure from watching the video lectures for advanced operating systems

    Funny moments

    • Professor made me laugh while I was watching his recorded lecture videos, the professor describing the tournament barrier and how the algorithm “rigs” the competition and how the algorithm seems applicable to real life given professional sports rig competitions all the time (e.g. baseball and world series) Okay, reading this out to myself now doesn’t sound that funny but I guess its something you have to hear first hand.

    Writing

    Best parts of my day

    • Eating dinner with Jess while grubbing on some delicious Vietnamese take out food from our favorite (for now) local restaurant called Moonlight. They sell the best Vegan Vietnamese food, dishes including Ca Co (clay pot fish) and Canh Chua (Vietnamese Sweet and Sour Soup) and Pho. All this wonderful food while the two of us planted in front of the cinema sized television playing “Fresh Off The Boat”.
    • Bridging the gap between theory (computer science) and practice (life as a software engineer at Amazon). While walking through code with a principle engineer, he described the data structure he came up with that (classically) traded space for lookup performance, describing an index that bounds the binary search. To clarify the data structure, he “whiteboarded” with me, using (an internally hosted) draw.io, and the figures made me realize that the data structure resembles how page tables in operating systems are designed.

    Mental and Physical Health

    • Remembered to stretch my hamstrings a couple days throughout the day. Not really enough exercise but the best I could do given that the weather outside still is labeled “very unhealthy” due to the wildfire smokes.

    Graduate School

    • Watched a few more lectures from the “Barrier Synchronization” series, learning more about the tree barrier and the tournament barriers, two slightly more advanced data structures than the simplistic centralized barrier
    • Finished putting together my submission, a .zip file containing: source code, Makefile, log files (from running my program against the test cases).

    Work

    • Met with a Vietnamese senior principle engineer yesterday who I reached out to for two reasons: asking him to participate in a future event that I’ll host on behalf of Asians@ and asking him for some tips given he’s excelled (at least on paper) in his career while bringing his full self to work (i.e. being a father).
    • Walked through some C data structures with a principle engineer and successfully imported the code (with a few minor tweaks) into my team’s package
    • During my 1:1 with my manager, he straight up asked me if I was leaving the team. I realized that I may have given him that impression because during a team meeting, I spoke up about how if the operations on the team continues to disturb me and wake me up consistently in the middle of the night then I would reconsider switching teams, which is true. Although I love my position and love what I’m doing at work, I do value other things such as a good nights sleep because poor sleep means poor mental health which leads me down a very dark path.

    Family and Friends

    • Watched after my daughter yesterday morning from 06:00 to 06:45, allowing my wife to catch up on some sleep due to a difficult night with Elliott, who we think is teething, given that she’s been waking up in the middle of the night, waking up more than usual.
    • Left a couple voice notes in WhatsApp for my brother-in-law, who is getting into writing and who asked me for some suggestions on writing platforms to host his blogging content. In short, I say it doesn’t really matter all that much but what does matter is that he owns his content and syndicates it out

    Miscellaneous

    • Downloaded 30 days of Wells Fargo and Morgan Stanley transaction history, proving that my wife and I have the funds needed to complete the transaction on September 30th, the day we close on our house located in Renton

    Today

    Writing

    • Publish Part 1 of Barrier Synchronization notes
    • Publish this post (my daily review)

    Mental and Physical Health

    • Stretch stretch stretch! Add a 5 minute event that notifies you on your phone so that step back from your desk and reach for your toes. Squat a couple times. Drop to the ground for a couple push ups. Get that heart pumping!

    Graduate School

    Work

    • Attend weekly operational meetings
    • Submit code review for small feature the optimizations look up time on the packet path

    Administrative

    • Attend my dentist appointment at 02:30 in the afternoon. How the hell is that going to work with the pandemic? Obviously I won’t be able to wear a mask with the pandemic … I should probably give them a ring this afternoon, before stepping into the appointment

    Family

    • Pack pack pack! There’s only a couple weeks left until we are out of this house. It’s difficult to pack at the end of the day because both Jess and I are both exhausting, her from watching Elliott and me from working. But maybe we can pack while eating dinner instead of sprawling out on the couch and watching “Fresh off the boat” (one of my favorite TV series, I think)

     

     

  • 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.