I’m really struggling to intimately understanding virtually index privately tagged concept. From a high level, I get that VIPT is an optimization technique, parallelizing both the translation of virtual addresses to physical and the cache look up of the physical address. This seems impossible at first since the cache depends on the physical frame number (PFN).
So in order to accomplish this, we’ll use the some bits of the VPN to search in the TLB and then the least significant bits when searching the cache. This makes sense. But what I don’t quite fully don’t understand is why we have to limit the size of the cache in order to avoid aliasing (i.e. different virtual addresses that end up mapping to the same physical frame).
Thinking out loud here … I suppose that if the index of the physical bits bleed into the virtual address, then we actually do not avoid the aliasing problem, the issue of having more than one virtual address map to the same physical frame.
Ok, I think I got it.
But what’s the catch?
You only can have a very small cache, the size equal to the page size multiplied by the set associativity. This means that the only way to increase the size of the cache is by increasing the associativity which ultimately increases the look up time as well since the cache has to look the tag up across multiple cache lines.
Watch and take notes on second module in advanced operating systems (Lesson 2)
Organization
Review Inbox items sitting in OmniFocus
Quickly glance over project
Work
Continue to chip away at writing one-pager design for a prototype for new feature at work
Survive today’s on call and flurry of operational issues that may arise
How did yesterday go?
Realized that checking my work laptop first thing in the morning for just that one little thing doesn’t work: I get sucked in and begin tackling other items, including checking my e-mail inbox, or slack messages, or whatever. So my rule of thumb is to not flip open the lid of my work laptop until I am ready to fully work
Work drained me. All the back to back operational issues not only enervated me but derailed my entire day, something I should just expect since on call is so variable
Being on call yesterday, I was unable to break away from the laptop while my mom was visiting Seattle, not getting to spend much quality time with her. Bummer. These feelings make me reevaluate work (see Feelings section)
Word of the day
underscore – verb (n) – to underline or to emphasize
Even Atlanta, Donald Glover’s Twin Peaks–esque FX series, toys with the supernatural and the surreal to underscore points about race made in its quieter moment1.
In an internal memo, Stan Deal, chief executive of Boeing Commercial Airplanes and Greg Hyslop, Boeing’s chief engineer, sought to underscore the message that safety is the company’s top priority 2
What are you grateful for?
My sister delivering a healthy little girl, her birthing free from any major complications (unless you consider an epidural a complication)
Feelings
As mentioned above, on call operations for my team (and many other teams in Amazon) can drain every ounce of energy. Every time my phone sounds an alarm, my body releases cortisol and stress washes over me. Granted, there are some weeks where very little issues crop up: but that’s the not the norm as of late. But is this how I want to live my life 24×7, once every 5-6 weeks? Sure, the work is rewarding and challenging and intellectually stimulating but one entire week of pure exhaustion may not be worth the cost
Seeing my wife watch over both my daughter and niece (Maiya) sends butterflies to my stomach. She’s patient and gentle with them, two important qualities for anyone.
In the context of an operating system, what does structure even mean and why is it important? Structure determines how the operating system serves application in regards to the underlying hardware and how it balances the following qualities: protection, performance, flexibility, scalability, agility, and responsiveness.
To obtain the above qualities, several designs exist including monolithic and microkernel. In a monolithic OS, there’s a division between applications running in user space vs the operating system’s core services (e.g. file systems, memory, scheduling). Taking this division a step further is microkernel design, separating the core services from the kernel, the core services all running in user space. There are trade offs between each approach. Monolithic operating systems improve performance, reducing the number of system calls between user and privileged mode, a trade off that microkernel operating systems sacrifice. However, microkernel operating systems offer greater extensibilty, allowoing applications to select which OS core services cater to their needs.
Introduction
Summary
Will study structure of OS, whatever that means. To this end, we’ll learn about SPIN and Exokernel approaches, two terms I’m unfamiliar with, and then a micro kernel)
Quiz: OS System Services
Summary
I got most of the services, apart from inter process communication (IPC) and thread scheduling, I named the others including access to I/O devices, access to network, memory management (protection, sharing, demand paging)
OS Structure
Summary
Structure determines how OS serves applications and the underlying hardware
Goals of OS Structure
Summary
There are six goals of an OS: protection (users themselves and between users, and of course the OS), performance (the time taken for OS to carry out its service), Flexibility (not one size fits all and should be able to adapt to different applications), Scalability (essentially if hardware improves, so should the speed of the operating system), Agility (how quickly can the OS respond to changing environment), responsiveness (does OS react to events, liken I/O, quickly)
Commercial OS
Summary
Apparently I’ll learn that somehow, system designers can have their cake and eat it too. That is, they do can achieve both performance without really sacrificing protection and flexibility. How? Who knows, though I should find out soon
Monolithic Structure
Summary
Monolithic OS – division between applications and OS core services (e.g. file system, memory addressing, scheduling)
Why do we call it a monolithic structure? Because the big blob (see photo) contains all the services (e.g. file system, network access, memory management, scheduling) offered by the operating system
DOSlike Structure
Summary
At a glance, the DOS like structure seems indistinguishable from monolithic. But how is it different?
Quiz DOSlike Structure Pros and Cons
Summary
Seems like DOS allows applications to run in the same space as the OS, so no trapping is necessary: just a procedure call. Trade off here is lack of protection; the OS can get corrupted by a running application.
DOSlike Structure (continued)
Summary
DOSlike structure and its lack of protection is unacceptable for general purpose OS. On the other hand, monolitic structure reduces performance, while offering protection. But we need to also consider how we can customize and tailor needs of different applications — via customization
Opportunities for customization
Summary
Learned a little more about why customization might be important. I thought that page fault handling should be the same for every process but there’s a missed opportunity here. Since the OS sort of bets on processes not requiring the entire address space, this bet might be expensive if the page fault handler (along with the eviction algorithm) runs unnecessarily. SO perhaps OS can learn more about the process and inform the cache replacement policy
Microkernel based OS Structure
Summary
Microkernel OS – OS services run in user mode too, indistinguishable from user space apps.
Why the hell do we want to overcomplicate the OS design by introducing a microkernel based OS structure? What’s the gain here? Extensibility! Previously, application 1 and application 2 would access the file system or the memory manager or the scheduler. There’s lack of extensibility here. Also, each of those servers (e.g. file system, memory management, cpu scheduler) also run in user space and will still require some sort of IPC to talk to one another, requiring the servers to talk to the micro kernel via system calls. I’ll soon find out but I think this is expensive; that is, we are sacrificing performance, I think. Will find out shortly in next lesson
Downside to the Mikrokernel
Summary
Biggest down side with microkernel approach is potential performance hit. For application to talk to file system (or other servers), a lot of IPC is needed. Data flowing between services require IPC calls in order to Marshall data in and out between applications and servers, and between servers as well
Why performance loss
Summary
Memory locality changes since we need to context switch, dramatically impeding performance. Same goes with copying data between user space and system space. This strategy is unlike monolithic, which the servers can share data easily with one another, although a little more inflexible.
What do we want?
Summary
Trade off between performance, extensibility and protection
Is it possible to get the OS to exhibit all three desirable characteristics: performance, extensibility, and protection — at the same time? Apparently, there is, but I’ll have to wait until the next module
How can the OS make use of a larger, slower device to transparently provide the illusion of a large virtual address space?
Overview
Why try and create a large virtual address space, a virtual address space that is larger than the physical amount of address memory installed on the system? Well, the illusion of a larger virtual address space serves as a useful abstraction for application developers: they just request more memory and simply get it — thanks to the operating system.
Arpaci-Dusseau and Arpaci-Dusseau 2018) – Swap Space
To this end, the OS creates a memory hierarchy. At the top sits the fastest cache (L1 or L2 or L3) and at the bottom sits hard disks (as much as 10,000 slower). And the speed of the cache is inversely proportional to the cost. That is, fast cache is expensive and slow cache is cheap.
Essentially, the OS reserves portions of the disk as swap, the location in which memory is paged in (i.e. from disk to memory) and out of (from memory to disk). How does the OS determine which pages currently live in memory and which pages live on disk? By looking at the page table entry metadata. More specifically, if the present bit is set then the physical frame lives in memory. Otherwise, it lives on disk.
In the scenario when the page lives on disk, the page handler must get invoked. With the present bit set as 0, the page handler will find the memory living in swap (the address is also stored in the metadata of the page table entry), page the memory into either a physical frame (that was available or freed up by the page replacement policy), set the present bit equal to 1, and finally re-run the instruction that generated the page fault (i.e. memory access when present bit set to 0).
21.1 Swap Space
Summary
The swap space is orders of magnitude larger than physical memory, allowing OS to prevent a large amount of memory to the process and program developers
21.2 The Present Bit
Summary
The present bit is a flag that lets the translate lookaside buffer (TLB), hardware or OS software based, whether the physical frame number itself lives in memory or whether it has been swapped out to disk. If the bit/flag is set to 0, then we must invoke the pagefault handler. Also, the TLB locates the page table based off of the page table register but this rises another question for me: who’s responsibility it is to set the page table register. Probably the OS since the OS is responsible for this per process page table. The OS is a beast!
21.3 The Page Fault
Summary
The TLB checks the PTE and if the PTE’s present bit is set to 0, the page fault handler runs. The page fault handler will check the PTE’s metadata for the location / index of where the page table entry exists on disk (or whatever underlying swap mechanism). Then, the page fault handler will rerun the process and the TLB (hardware or software) will then update its cache. During this page fault workflow, the process is put into a blocked state so other processes can run: concurrency for the win!
21.4 What if Memory is Full
Summary
Need to invoke the page replacement policy (like an LRU)
21.5 Page Fault Control Flow
Summary
When a page fault occurs, the hardware (TLB) and software (OS) must carry out a sequence of actions, depending on the scenario. Focusing on the OS, if a page fault occurs, then the OS must fetch a new physical address, populate the page frame with the right contents, update the PTE, setting the valid bit equal to 1, update the PTE’s page frame number, then finally retry the instruction.
21.6 When replacements really occur
Summary
To optimize the address space and ensure there are always pages available, the swap (or page) daemon runs in the background, freeing up memory for running processes and for the OS.
Review Inbox and Important projects sitting in OmniFocus (this was a miss yesterday)
Put in 1 hour study session before and after work for advanced operating systems (seems unlikely since I woke up at 05:00 instead of 04:30 and made the fatal mistake of checking my work laptop first)
Continue to chip away at writing one-pager design for a prototype for new feature at work
Drive from Seattle to Renton in the early morning (while express lanes are flowing in our direction) to visit my sister and my new niece (Charly) who was born just a few hours ago. Looking forward to seeing my mom, who lives in OC but who is visiting us up in sunny Seattle for a few days now that Charly has arrived
How did yesterday go?
Pretty good (although Jess says that I’m always a bit more on the edge, a little less patient, when I’m on call and getting paged throughout the week
Felt good about squeezing in early morning and after work study sessions. I admit that I find myself taking the longer path on some homework and reading assignments, but then I remind myself that my purpose of graduate school is not to just get a master of computer science degree but to learn, to grow, to change the way my mind thinks. So I find solace in my decisions to reading a little more than necessary, generating and answering my own questions while reading the textbook
I did not review my inbox (or personal e-mail, really) in neither OmniFocus nor my excel backed project list. Need to remind myself that to trust the system of getting things done (GTD), I need to establish a routine of extracting to-do items out of my brain and into the same location — every time. And of course, reviewing that list (which as I mentioned as part of this post, I did not do)
But I am consistently writing, editing and most importantly, publishing on my blog, a strong cadence unfolding. In some ways, I am carrying out Jerry Seinfield’s “Don’t break the chain” strategy1, a self motivation tool
Word of the day
The men set off in fear and trepidation
A few days ago, five-star basketball recruit Keion Brooks was asked about his level of interest in the Louisville Cardinals and expressed some trepidation2.
trepidation – noun (n) – a feeling of fear or agitation about something that may happen
What are you grateful for?
Jess dropping off snacks at my desk, fresh slices of peaches and toast covered with peanut butter helping me relax while tackling on call
Feelings
After not speaking to my dad for 2 months and then very briefly video chatting with him on his birthday (August 23rd), he now is suddenly active on WhatsApp, sending Jess and I random links to Facebook, his way of communicating with us. I’m unsure how to engage with him: I’m never sure actually, how we — as a family — should move forward when we’re this entangled since dealing with addiction in the family is a complicated matter. Oh well. I’m not in this alone: I have Jess. And we’ll sort it out. And also, I need to remind myself that I need not figure this out all alone.
Recover from waking up from 03:00 AM from being woken up from operational issue
Write and publish one piece on this blog
Review Inbox and Important projects sitting in OmniFocus
Put in 1 hour study session before and after work for advanced operating systems
Chip away at writing one-pager design for a prototype for new feature at work
Word of the day
You cannot geld the human race
Geld – verb (v) – to deprive of vitality or vigor
What are you grateful for?
Having a steady income and job that I enjoy despite being in the midst of COVID-19
Feelings
Tired as I type this out since I got paged out of bed for 03:00 AM for a NOP (no operation) issue at work
Yesterday
Woke up naturally (i.e. without alarm) at around 04:15
Felt good about being able to connect the dots between theory and practice (when reviewing out to generate virtual private numbers using a BITMASK and SHIFT operations)
Followed my morning Routine (e.g. walk dogs at local park, blended fruit and vegetable smoothie, warm up chai, write)
Pulled into Discount Tires for scheduled appointment to replace punctured front left tire
Finished reading chapter on paging systems while waiting for tired to be replaced
Recorded a short little melody and harmony on my iPhone while playing guitar for Elliott and Jess during lunch
Ad-hoc shopping at Target to pick up size 4 diapers, bottle scrubber for the kitchen, plastic hooks to hang the broom, stasher reusable zip lock bags
Ordered and picked up sushi for dinner (avocado rolls, cucumber rolls, croquette and vegetable mini tempera udon soup)
Chopped up fresh vegetables and stored them away in the (just purchased) stasher bags
Cut up Jess’s recently purchased book, scanning the book using my Fujitsu IX1500 ScanSnap and then converting the document in mobi format using calibre (new open source software I discovered while searching stack overflow)
In my other blog post on memory segmentation, I talked about diving the process’s virtual address space into segments: code, heap, stack. Memory segmentation is just one approach to memory virtualization and another approach is paging. Whereas segmentation divides the address space into segments, paging chops up the space into fixed-sized pieces.
Each piece is divided into a virtual private number (VPN) and the offset; the number of bits that make up the offset is determined by the size of the page itself and the number of pages dictate the number of bits of the virtual private number.
To support the translation between virtual address to physical address, we need a page table, a per process data structure that maps the virtual address to the physical frame number (PFN).
While driving to my tennis lesson, I listened to Jared’s (my guitar instructor) video on “Fear is a Guide” and I must say that I love the new direction he is taking on his YouTube channel. He was previously focusing on delivering guitar lessons. Now, he’s honing on what is important to him including song writing and teaching people how to express themselves creatively through music.
In the video (below), Jared takes the position that if, in the context of music, you are scared of doing something (practicing scales, writing a song, performing in front of people), then that’s the very thing you should be focusing on. Not only do I agree with him 100%, but I think this philosophy or mindset applies to all areas of life.
In fact, one of my mentors living in Los Angeles had pretty much gave me the same advice:
If you are not doing something everything that you are afraid of, then you are NOT growing – Phil
And that advice, I think, is sound. Obviously take that with a grain of salt. Some things you should just straight up be afraid of and avoid, like running into a hungry pack of raccoons in the middle of the night.
This blog post contains notes I took on memory segmentation, from “OS in Three Easy Pieces Chapter 16”, one strategy for implementing virtual memory systems. In the next blog post, I’ll cover a different approach: paging.
16.1 Segmentation: Generalized Base / Bounds
Summary
We use segmentation to divide the virtual address space into three distinct segments: code, stack and heap. This technique allows us to accommodate processes with large address spaces.
16.2 Which segment are we referring to ?
Summary
How do hardware know which segment that the request is referring to? Are we requesting memory for stack, heap, or code? Well, there are two approaches: an explicit and implicit approach. For the explicit, we reserve 2 bits at the top of the address. So 00 might refer to code, and 01 might refer to heap, and 10 might refer to the stack. But there’s an implicit approach, too. If the address is based off of the stack base pointer, then we check the stack segment.
16.3 What about the stack?
Summary
Why do we need special consideration for the stack? Because the stack grows backwards, from a higher memory address to lower. Because of this, we need an additional flag to tell the hardware whether the segment grows up or down.
16.4 Support for sharing
Summary
Systems designers realized that with segmenting, processes can share memory with each other. In particular, they could share code segments and in order to support this feature, hardware must add an additional bit to the memory metadata. In particular, the “Protection” field tells us whether or not the segment can be read and executed or can be read and written to. Obviously, for code sharing, we need the segment to be read-execute only.
16.5 Fine-grained vs Coarse-grained Segmentation Fault
Summary
Breaking the address space into (3) segments is considered coarse-grained and some designers preferred a more flexible address space, with a large number of smaller segments, known as fine-grained. The idea behind this was that the designers thought they could learn about which segments were in use and could utilize memory more effectively. Not sure if they were right, though.
16.6 OS Support
Summary
There are two issues with segmentation: a pre-existing problem is how to handle context switches and the second is how to handle external fragmentation? With segmentation, we no longer have a contiguous block of addresses for the process. Instead, we chop them up. So what happens if the stack or heap requires 20KB and although we have 24KB, there’s no continuous space? Well, there are several approaches, the first being extremely inefficient: a background process runs and re-arranges the blocks into contiguous blocks: this approach is extremely inefficient. Another approach is to maintain some sort of free-list and there is a long list of algorithms (e.g. first-fit, worst-fit). Regardless of algorithm, we cannot avoid this issue called external fragmentation.
16.7 Summary
Summary
Segmentation helps accomplish a more effective virtualization of memory but it does not come without cost or complexities. The primary issue is external fragmentation and the second issue is that the if the segments do not line up exactly, then we waste lots of memory.
