Category: Advanced Operating Systems
-
Daily Review – Day ending in 2020/09/27
Writing Published a post on the anki settings I used to cram for the midterm exam Family and Friends Walked the dogs at Magnuson Park. Elliott and Jess joined too since Elliott has been waking up so early these days (around 05:45 AM). Trying to get the dogs to capitalize on these amazing off…
-
My Anki settings for cramming for an exam
I spent a few minutes fiddling with my Anki settings yesterday, modifying the options for the advanced operating systems deck that I had created to help me prepare for the midterm. Although Anki’s default settings are great for committing knowledge and facts over a long period of time (thanks to its internal algorithm exploiting the…
-
Shared memory multiprocessing (notes for advanced operating systems)
OS for parallel machines Summary There are many challenges that the OS faces when building for parallel machines: size bloat (features OS just has to run), memory latency (1000:1 ratio) and numa effects (one process accessing another process’s memory across the network), false sharing (although I’m not entirely sure whether false sharing is a net…
-
Midterm preparation (part 3/3) – Virtualization to Test-And-Set
Question 3d The algorithm is implemented on a cache coherent architecture with an invalidation-based shared-memory bus. The circular queue is implemented as an array of consecutive bytes in memory such that each waiting thread has a distinct memory location to spin on. Let’s assume there are N threads (each running on distinct processors) waiting…
-
Midterm preparation (part 2/3) – Virtualization to Test-And-Set
This is a continuation of me attempting to answer the midterm questions without peeking at the answers. Part 1 covered questions from OS Structures and this post (part 2) covers virtualization and includes questions revolving around memory management in hypervisors and how to test-and-set atomic operations work. A few useful links I found while trying…
-
Midterm preparation – Questions and my guesses for OS Structures section
As mentioned in my recent post on taking a multi pass approach for midterm preparation, I’m taking a stab at answering the midterm questions myself and below are my unfiltered attempts followed by the correct answer that I pulled from the answer key. OS Structures Question 1a Protection domains allow providing independence, integrity, and isolation…
-
Multi pass approach for studying to advanced operating systems midterm (fall 2020)
According to the omscentral reviews for the advanced operating systems course, the midterm exams are nearly identical to the previous semester’s exams and former students strongly suggest rote memorization as a the primary study method. In my opinion, these types of tests do not really serve as a great litmus test for evaluating a student’s…
-
Advanced Operating Systems (AOS) notes
If you are an online masters of computer science student (OMSCS) at Georgia Tech and enrolled in advanced operating systems (AOS) course, you might want to check out the notes I’ve taken for the lectures by clicking on the advanced operating systems category on my blog. For each video lecture, I’ve written down a summary…
-
Parallel Systems – Scheduling (notes)
The key take away for scheduling is that as OS designers you want to follow this mantra: “keep the caches warm“. Following this principle will ensure that the scheduler performs well. There are many different scheduling algorithms including first come first serve (FCFS), fixed processor (focus on fairness), fixed processor (thread runs on the same…
-
Remote Procedure Call (RPC) notes
Remote procedure call (RPC) is a framework offered within operating systems (OS) to develop client/server systems and they promote good software engineering practices and promote logical protection domains . But without careful consideration, RPC calls (unlike simple procedure calls) can be cost prohibitive in terms over overhead incurred when marshaling data from client to server…
-
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…
-
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…
-
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.…
-
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…
-
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…
-
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…
-
Memory coordinator test cases (and expected outcome)
I’m getting ready to begin developing a memory coordinator for project 1 but before I write a single line of (C) code, I want to run the provided test cases and read the output of the tests so that a get a better grip of the memory coordinator’s actual objective. I’ll refer back to these…
-
Memory Virtualization (notes)
The operating system maintains a per process data structure called a page table, creating a protection domain and hardware address space: another virtualization technique. This page table maps the virtual address space to physical frame number (PFN). The same virtualization technique is adopted by hypervisors (e.g. VMWare). They too have the responsibility of mapping the…
-
Papers to read for designing and writing up the C memory coordinator
Below are some memory management research papers that my classmate shared with the rest of us on Piazza1. Quickly scanning over the papers, I think the material will point me in the right direction and will paint a clearer picture of how I might want to approach writing my memory coordinator. I do wonder if…
-
How to obtain the length of the memory statistics array when calling virDomainMemoryStats
Up to ‘nr_stats’ elements of ‘stats’ will be populated with memory statistics from the domain. Only statistics supported by the domain, the driver, and this version of libvirt will be returned. What does the above API description even mean by nr_stats? How do you determine the number of elements that need to be populated? For…
-
A snapshot of my understanding before tackling the memory coordinator
Now that I finished writing the vCPU scheduler for project 1, I’m moving on to the second part of the project called the “memory coordinator” and here I’m posting a similar blog post to a snapshot of my understanding of project 1 , the motivation being that I take for granted what I learned throughout…
-
Introduction to virtualization (notes)
As system designers, our goal is to design a “black box” system that create an illusion that our users have full and independent access to the underlying hardware of the system. This is merely an abstraction since we are building multi-tenant systems with many applications and many virtual guest machines running on a single piece…
-
A naive round robin CPU scheduler
A couple days ago, I spent maybe an hour whipping together a vary naive CPU scheduler for project 1 in advanced operating systems. This naive scheduler pins each of the virtual CPUs in a round robin fashion, not taking utilization (or any other factor) into consideration. For example, say we have four virtual CPUs and…
-
Advanced Operating Systems (Project 1) – monitoring CPU affinity before launching my own scheduler
Project 1 requires that we write a CPU scheduler and memory coordinator. Right now, I’m focusing my attention on the former and the objective for this part of the project is write some C code that pins virtual CPUs to physical CPUs based off of the utilization statistics gathered with the libvrt library (I was…