Matt Chung's Site

Author: mattchung

Advanced Operating Systems: The SPIN Approach

What did I learn? What are the main takeaways?

The concept of border crossing pops up over and over again. This is a new term I never heard of prior to this class. The term is almost synonymous to a context switch but it is subtly different in the sense that a context switch (switch from one process to another or one thread to another) can occur without a border crossing, without changing the underlying hardware address space.

SPIN attempts to enforce protection at the compiler level, by using a restrictive language called Modula-3. Unlike the C language, where you can cast a pointer to whatever data structure you like, Modula-3 enforces type safety, only allowing the developer to cast a pointer to specific types of data structures that they had already specified earlier in the code.

SPIN offers extensibility by allowing different types of OS services to co-exist with one another.

But what are the trade offs with SPIN, when compared with Microkernel and Exokernel?

It appears that SPIN would be more performant than Microkernel due to no border crossings while maintaining flexibilty (multiple types of OS services that cater to application processes) and security (via logical protection domains) with Modula-3, allowing code OS services library code to co-locate with kernel code.

Introduction

Customizing OS with SPIN

Summary

SPIN and Exokernel take two different paths to achieving extensibility. These designs overcome the issue of Microkernel, which compromises in performance due to border crossings, and monolithic, which does not lend itself to extensibility

What we are shooting for in OS Structure

Summary

We want flexibility similar to a microkernel based approach but also want protection and performance of monolithic. We want the best of both worlds: performance protection flexibility

Approaches to Extensibility

Damn, this is a super long video (8 minutes, compared to the other one to two minute videos prior)

Capability based

Hydra OS (1981)

Summary

Hydra did not fully achieve its goal of extensibility

Micro Kernel Based

Summary

Performance took a back seat, since the focus was on extensibility and portability. Bad press for micro kernel based due to the twin goals.

SPIN approach to extensibility

Summary

By co locating the kernel and extension in the same hardware space, the extensions are cheap as procedure call. Doing this by depending on a strongly typed language to provide safety

Logical Protection Domains

Summary

Using a programing language called Modula3, which doesn’t appear to be popular in practice, we can enforce protection at the logical level. This programming language, unlike C, restricts casting pointers to random data structures, only allowing the cast to a particular data type.

Spin mechanisms for protection domains

Summary

The secret sauce of protection and performance are the mechanisms of creating (i.e. expose entry points), resolving (i.e. leverage other entry points), and combining of logical protection domains

Customized OS with Spin

Another example of SPIN os customization

Summary

There can be multiple file systems (written in Modula3), each file system catering to their callers, and each file system using the same underlying hardware address space. And they can share modules with one another, like the networking entry point.

Example Extensions

Summary

Example of Unix Servers implementing their OS on SPIN as well as a video server / display client building on top of spin

Quiz: Border Crossings

Quiz: Least likely for border crossing

Summary

Microkernel and SPIN offer performance since they limit the border crossings. In SPIN, Logical domains do not require border crossings

SPIN Mechanisms for Events

SPIN classifies three types of event handling: one-to-one, one-to-many, many-to-one

Summary

To handle events (like packet arrival) we can have a 1:1 mapping, 1:N mapping or N:1 mapping. For 1:1, an example would be an ICMP packet arriving and the 1 ICMP handler running. In a 1:N mapping, the IP packet arrived event runs and signals three other event handlers like ICMP, UDP, or TCP. Then finally, there is a N:1, and an example of this is an Ethernet and ATM packet event arrives but both funnel into the IP handler

Default Core Services in SPIN

Summary

SPIN offers core services like memory management, CPU scheduling etc. And SPIN will provide a header file that OS programmers need to implement. Remember: these implementations talk to each other through well defined interfaces, offering protection, but are also performant cause there are no border crossings)

Default Core Services in SPIN (Continued)

Summary

Provides primitives, the interface function definition. The semantics are up to the extension itself. SPIN makes sure extensions get time on scheduler

August 31, 2020
Daily Review – Day ending in 2020/08/30
Yesterday

Writing
- Wrote and published an article on Time Management Tip #1: Pomodoro Technique. How I use the technique and how I’ve adjusted it to fit my needs.
Music
- Had my bi-weekly virtual guitar lesson with Jared. This was the first lesson back, after he took a 1.5 month sabbatical, a vacation he deserves and a vacation that he takes once a year. During the lesson, we didn’t actually focus on any mechanics of guitar this time, which was fine by me because instead, we had a lengthy discussion around where we want to take guitar lessons: what’s the point and what do I want to work towards. More on this in a separate blog post.
Graduate School
- Submitted both homework assignments (apparently a day before it was due: so hooray me) and watched the video lectures while sitting in the back seat of the car, while my wife drove us from Seattle to Renton (see house hunting below, under family section).
Organization
- Miss: I had a scheduled call at 06:00 PM PST with a fellow class mate and I missed the chat. For two reasons: my phone died on the way home and two the event was not scheduled in my calendar, no alerts or notifications. Fortunately, he was still online at the time so we were able to meet over Google Hangouts despite me being 30 minutes late or so.
Family
- House hunted in Renton, viewing three homes and one of which we will submit an offer. We’ll go in at listing price and per our realtor, a friend of my sisters, escalate to about 20k above if there are competing offers. I could really see Jess and I living in the home, the square footage practically doubling the size of our current rental. Funny how having kids changes things. Up until a week or two ago, I opposed the idea of moving to the suburbs, opposed to moving away from Maple Leaf/North Seattle: all favorite local cafes are within walking distance, the amazing off leash dog parks like Magnuson, top notch vegan restaurants. But since COVID hit, my view has changed. Based off of the amount of time we spend at home, which is about 23 out of the 24 hours in the day, I’d love for Elliott to have a little more space, more than the 15 square feet of crawling space that we have now.
Today

Organization
- Plan day and week out by reviewing OmniFocus forecast events
- Process e-mail inbox down to zero
- Migrate sticky notes (written down while walking dogs in the morning) into writing tracker and OmniFocus
Graduate School
- Begin on lecture series for the week, the lecture focusing on virtualization (curious what this means)
- Write up notes taken over the weekend on L3 Microkernel, SPIN, and Mach, three different underlying OS structures, each with their own trade offs
Work
- Finish one pager design document (due tomorrow)
- Review dashboard in preparation for organization wide, weekly operations meeting
Family
- Morning routine of walking dogs at local Northacres park, blending a strawberry and banana smoothie (wait: no much coconut milk so that’s out of the question), eating lunch together, bathing Elliott as part of her night time routine
- Put together loan documents so that we can get a pre-approval for house that we are putting an offer in
Bonus Image

Elliott standing up at the beach

Word of the day

decry – adjective (adj) – publicly denounce

“SPIN and Exokernel used Mach as a basis for decrying Microkernel-based design”

What are you grateful for?

I’m glad I’m writing down what I’m grateful for because its so easy for me to get trapped inside my own brain, my own world, when work (on call specifically) feels like a tornado.
- To be in a financial position to even be looking to buy a home in the midst of COVID-19
Feelings
- Nervous about the move. Just like Jess. Leaving behind North Seattle is scary: we’ve grown to love the city. Will we regret it? Maybe. But the way I see it is that this decision (of moving to Renton) is not a one-way door: we can always move back and rent in North Seattle. Sure, we might not get the same awesome rental that we been living in for 4+ years but that’s a fair trade off. We are doing the right thing by listening to our gut and being heedful to our fears.
August 31, 2020
Weekly Review – Week ending in 2020/08/30
- Writing
  - Developed a manageable cadence of blogging a single blog post every day, most of them daily reviews or notes taken during advanced operating systems
  - Writing the daily reviews (each entry eats up about 15 minutes of my morning) help me not only plant my two feet in the ground and settle for the day, but provide the necessary content for my weekly review / reflections. Will likely continue this new habit (assuming I still wake up between 04:30 and 05:00 AM)
- Music
  - Recorded a short little melody and harmony on my iPhone while playing guitar for Elliott and Jess during lunch. Super simple melody and chorus lyrics go “It’s a sad song, it’s a love song”
- Graduate School
  - Felt proud of myself for being able to connect the dots between theory and practice, catching the relationship between C code I write at work and what I read in the textbook (revolving around virtual private numbers using a bit mask and SHIFT operations)
  - Glad I was able to keep up with all the lectures, although I could’ve finished them much earlier in the week. But I spent an hour on deep diving into virtually indexed physically tagged cache, a topic I could’ve just glossed over but I just couldn’t let go of not understanding the topic
  - Completed writing up the homework assignment, typing it all up took much longer than anticipated due to formatting issues when copying between OmniOutliner and Microsoft Word
- Organization
  - Ripped apart three books and scanned them using my ScanSnap. Again, I’ve nailed down the process since on average, it takes about 8 minutes from running the knife down the spine of the book to the moment the last (200+ page) book scans to my DevonThink system
- Physical and Mental Health
  - Cancelled my weekly psychotherapy session, a session I often look forward to since I’ve been attending just about every week for close to 5 years now
- Family
  - Lots of administrative duties this week, including replacing the punctures front left tire at Discount Tires, chopping up all the freshly bought vegetables and storing them away in reusable Stasher bags, driving from Seattle to Renton to visit my mom who is visiting from California for a few days
Misses
- Not a single day of exercise. This habit fell off the wagon about 2 months ago (or was it 3 or 4) when I injured the sole of my left foot. I was unable to shift any weight to my foot without wincing in pain. But the food healed about 2 months ago and I need to re-establish a habit of exercising: even if it is running for 10 minutes or stretching for 5.
- Being on call really zapped the joy out of my week. For starters, I was unable to break away from the laptop while my mom was in town, not getting to spend much quality time with her. This event, along with waking up at 12:00AM and 3:00 AM throughout the week makes me re-evaluate the team I am on and wonder a team with less operational burden might make sense for my health
Photos of the week

Jess, Matt, Elliott with sun in the background, three of us walking dogs at the park early in the morning

Llttle Elliott at carcreek park, who is starting to not look so little anymore

Reflections

Jess pointed out that when I am on call, I’m a little more edgy, a little less patient. She’s probably right because during the week, I’m constantly getting interrupted with operational issues, requiring me to drop whatever I’m doing — studying, hanging out with my wolf pack — and turn my attention towards work.

Although tiring, the early morning reflections and study sessions are proving to be valuable. I’m able to crank out a ton of work, crossing off graduate school and personal writing before anyone in the house hold wakes up. Being a productive in the morning, even if its just a little, really sets me in a better mood thorughout the day, my mind free to concentrate on the present moment instead of thoughts of “should’ve done this … and this” occupying CPU cycles in my brain.

Graduate school is tough but rewarding and such a privilege. I happened to stumble upon my blog post from 2018, almost 2 years ago to date, when I just got admitted into the graduate program: I was ecstatic to learn about computer science. I still am. And need to continue with my balancing the following: learning deeply (the main point of returning back to graduate school) and just getting things done (I have a family now, so time is very precious).

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

My noise wrinkles every time I see the photo of Elliott crawling in the back seat of the Ford Escape. The picture zooms in on face. I only see pure joy and beauty in her. It really is such an honor to be a father, to be in a position to see her develop and witness her mom basically perform mom magic every day.
August 30, 2020
Selecting research papers to read for Advanced Operating Systems
For advanced operating systems course, us students are required to sign up for (at least) two research papers that we summarize. Although two papers doesn’t sound like much, many former students of the course suggested ignore the other research papers and instead, focus on watching the lectures (which do cover the papers, sort of), banging out the software project, and (sadly) performing rote memorization based off of previous exams (I’ll need to get my Anki set up for this, stat).

Reviews on OMSCentral related to reading papers

I gave up on trying to read all the papers, electing to focus on projects and memorize the lectures instead. It worked out ok for me, and I averaged 18 hours a week on this course anyway. YMMV.

The downside to me is the number of readings was, well, high. Somewhere around 45 papers are to be read during the semester, and most of them are foundational but also from an earlier time in computing. I enjoy newer research papers with tech I can relate to, so for me in general these were less enjoyable and more difficult to digest. Still worthwhile, I think, but more of a slog.

The sheer number of papers assigned could easily push the time commitment past 30 hours a week if a student were to read them all, but as most have noted, you can largely skip reading them. Even skipping papers, the lectures are long and are difficult to get through. The content is broad and I think it tries to cover too much ground.

Papers I’m going to read

So although I’ll probably skim most of the research papers, I’ll dig into the below papers in depth. Why did I choose these papers? Well, some of the other papers (on networking) played into my strengths, categories that I’m somewhat well versed on. As a result, I chose papers grouped under categories that I not only find interesting (distributed systems and failures + recovery mechanism) but categories I’m unfamiliar with.
- Liu, Kreitz, van Renesse, Hickey, Hayden, Birman, Constable, “Building Reliable High Performance Communication Systems from Components “, 17th ACM Symposium on Operating System Principles, OS Review, Volume 33, Number 5, Dec. 1999.
- D. Porter, O. Hofmann, C. Rossbach, A. Benn, E. Witchel, “Operating System Transactions“, SOSP’09.
Stretch goal
- Lamport, L., “Time, Clocks, and the Ordering of Events in a Distributed System”, Communications of the ACM, 21, 7, pgs. 558-565, July 1978.
References
1. Student Review – https://omscentral.com/review/-M7Z0y3X-ORUdktU4bqT
2. Student Review – https://omscentral.com/review/-M74QupA7ND5_xq-cY2Z
3. Student Review – https://omscentral.com/review/-M69xss3dGXWiXXft9Ha
4. Sign up link
August 29, 2020
My time management tip #1 – Pomodoro Technique
Since the pandemic hit the states back in February this year, I’ve been working remotely from home (such a blessing and a serious privilege). Working from home underscores the importance of time management, especially for someone like me who can either deeply fall into work mode for hours and hours (never breaking eyes away from screen) or scroll mindlessly on websites like Hacker News or Reddit. The former melts my mental health and the latter kills my productivity.

So to avoid either scenario — working too long or not working at all — I employ a Pomodoro technique¹. The pomorodoro technique, which I picked up years ago when taking Learning How to Learn Course on Coursera, was invented in the early 1990s by Franscesco Cirillo. The basic premise is this: you set a timer for 25 minutes and work deeply for those 25 minutes. Once the alarm sounds, you break. The idea is that the technique improves your focus and promotes giving your brain some time off to relax.

So how do I use the Pomorodo technique in practice? What does it look like?

I use a kitchen timer, the TIMER YS-390 to be specific. This model hits all of my own personal requirements. The device has a dual count timer. I set the top timer to 50 minutes (my personal period of deep focus) and the bottom for 10 minutes; the 10 minutes is my grace period, allowing me to ease into my work (basically I cut myself some slack here). In addition to the dual timers, the alarm’s volume can be adjusted: no sound, low, high. I typically set the volume knob on low as to not frighten my daughter awake when she’s sleeping (my dentist’s rule: never wake a sleeping baby). And finally, the third feature I love is the physical cue. When either of the timers hit zero, the little button begins flashing red like a cop car. This makes it difficult to ignore and I find it really forces my eyes to break away from the screen.

So what happens when the timer sounds the alarm? I start by silencing it, hitting the silicone start/stop button, stepping away from the computer and if I’m lucky enough, take a 5-10 minute break with either my baby daughter (who is growing up way too fast) or wife or dogs (or if I’m really lucky, all four of them). This break, is also no exception, but instead of using my TIMER YS-390, I set a countdown alarm on my G-Shock watch.

Do I always break at the very moment the alarm sounds?

No. Sometimes I find that I’m really in the flow (for work or for graduate school or for writing on this blog) so what I do instead is quickly press the bottom right button, resetting the 10 minute timer. This allows me another grace period of deep work. It’s okay to not be so rigid and cut yourself some slack.

References
August 29, 2020
Daily Review – Day ending in 2020/08/27
What’s your chief aim for today

Learning that while I’m on call for my team, I very rarely hit my targets for the day (see section on “How did yesterday go”). Not only that, but I’m drained by the end of the day, little to no CPU cycles left for studying (although this window of time is ripe, since Elliott is asleep). Nonetheless, I’ll still call out what I want to accomplish today since these little tasks, when added together, help me fulfill my long term goals (a separate page for this will be pinned up on my blog soon).
- Writing
  - Write and publish one piece on this blog
- Graduate School
  - Complete typing up answers for assignment #1
  - Edit answers for pre-lab assignment
  - Watch and take notes on second module in advanced operating systems (Lesson 2)
- Organization
  - Review Inbox items sitting in OmniFocus
  - Scan projects sitting in my OmniFocus
- 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?

Basically, when I’m call, the entire day is blurry, the day flashing by right before my eyes. During the day, I’m in a completely different state, a reactive mode, dealing with whatever gets thrown at me from auto cut tickets to Chime messages or Slack messages or e-mails. Chaotic days like this put me in a despondent state.
- Another emotionally draining day, thanks to the on call operations for the week. I got paged at 12:00 AM and after troubleshooting for about half an hour, I was unable to fall back asleep for at least another 45 minutes. When getting woken up in the middle of the night, I find that there’s a very small window — about 15 minutes — in which I can fall back asleep. After that amount of time has elapsed, falling back asleep requires serious deep breathing
- Because of the interrupted sleep, I was unable to wake up early and use that morning slot to squeeze in studying before work. I’ll borrow back some time during the day to make up for it though. Oh yea, I also am a bit flustered that I was unable to comfortably hang out out with my daughter and wife and dogs because I did end up getting paged this morning (at around 07:00 am). Fortunately, we had already walked at the park so I was nearby my laptop: so no breach in service level agreement (SLA).
- Did not get to put any study time in (as mentioned above) so I’ll need to carve out time today to catch up with watching videos lectures and typing up my homework assignment for advanced operating systems.
Word of the day

remiss – adjective (adj) – lacking care or attention to duty; negligent.

“it would be very remiss of me not to pass on that information”

What are you grateful for?

I’m glad I’m writing down what I’m grateful for because its so easy for me to get trapped inside my own brain, my own world, when work (on call specifically) feels like a tornado.
- My German Shepherd dog (Metric) is in good health (she eats raw, gets daily exercise) and behaves wonderfully with my daughter. I do feel a pang in my heart when I notice small signs that she’s aging, signs like an additional grey whisker sprouting out.
- Jess ordering two delicious vegan sandwiches for lunch, sandwiches glazed with moist hummus and filled with soft chick peas. Yummy.
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.
References
1. https://www.theatlantic.com/culture/archive/2020/08/lovecraft-country/615259/
August 28, 2020
Thinking out loud – Not fully understanding virtually indexed physically tagged (VIPT) details
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.

Reference
1. https://cs.stackexchange.com/questions/68492/does-the-aliasing-problem-show-up-in-a-virtually-indexed-physically-tagged-cache
2. https://cseweb.ucsd.edu/classes/fa10/cse240a/pdf/08/CSE240A-MBT-L18-VirtualMemory.ppt.pdf
August 28, 2020
Daily Review – Day ending in 2020/08/26
What’s your chief aim for today
- Writing
  - Write and publish one piece on this blog
- Graduate School
  - Complete typing up answers for assignment #1
  - Edit answers for pre-lab assignment
  - 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 moment¹.

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 ²

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.
References
1. https://www.theatlantic.com/culture/archive/2020/08/lovecraft-country/615259/
August 27, 2020
OS Structure Overview

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

August 27, 2020
How to go beyond physical memory ?

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.

August 26, 2020