Virtual Memory
November 30,
2023
From taking an Intro to Systems course and now being almost done with
an Operating Systems course, I’ve noticed that understanding,
really understanding virtual memory is easier said than done.
I’d like to run through introduce a small (still sort of
work-in-progress) program I’ve written that students will hopefully find
helpful.
This post got a bit longer than I thought it would, so you can just
read “The small program in question” section. But feel free to peruse
“Why it might be difficult to understand VM” for some of my thoughts on
teaching and understanding VM as a systems concept.
Don’t get me wrong, I don’t yet have a perfect mental model of it
either – because it really is more difficult than it seems! I think the
creed “almost everything in CS can be solved with indirection” is
generally true, and VM is one of the quintessential triumphs of systems
abstraction.
The small program in
question
Link to txt
file of program. I of course welcome feedback. I'm thinking about
writing another, similar program that takes similar input but
instead of text output, it graphically displays the layout of the
page table hierarchy (with ncurses or some such library).
For reference, it basically takes some basic VM system parameters
as input (size of the virtual address space, physical address space,
size of virtual page number, physical page number, etc) and then
you can pick what you want the output to be, ranging from the amount
of levels needed to support such a system in a multi-level page table
set up, to the maximum possible virtual address (which would just be
2^n - 1, where n is the size of the virtual address in bits).
Why might it be
difficult to understand VM
TL;DR:
- Systems concepts, at a high level, aren’t super difficult
to wrap your head around. So you as a student could forever have a
cursory, incomplete understanding of VM and be perfectly fine.
- At a lower level, there are many, many considerations you have to
take into account for implementing VM.
- Implementing important memory-related mechanisms by extending your
knowledge of VM is really hard, even for grad students.
I will say this: like many other systems concepts (see scheduling,
the process abstraction, etc) VM is relatively easy to “get” at a high
level. Like okay, the computer abstracts a huge address space for each
process, and it maps the few parts that the process actually uses to
physical memory. Great.
But dig into the implementation even just a little bit, and you’ll
find a heap (no pun intended) of implications and details to consider.
For example, how would you maintain these mappings of virtual addresses
to their physical counterparts?
If you decided to use a page table (as real-world systems do), which
map virtual pages (which are a fixed-size unit of memory, usually 4KB)
to physical frames in what are called page table entries, you should be
wary of the fact that these page tables would grow linearly with respect
to the size of the VAS. And VASes tend to be very big! Your computer may
have a 64-bit address space, so there are 2^64 possible addresses. This
is an incomprehensibly huge number: more than the grains of sand on
Earth, more than the number of stars in the universe.
Then consider the fact that you have to maintain one of these tables
for each running process. It’s common for computers nowadays to
have more than one thousand running processes at any given time, so you
can see why the size would pose a problem.
Page tables in modern systems circumvent this issue by using yet more
indirection, in what are called multi-level page tables. The top-level
page table has page table entries that don’t hold mappings of
virtual-to-physical addresses, but rather hold mappings to other page
tables. That means one entry in the top-level page table can access
PGSIZE^n addresses, where n is the number of levels.
Very cool.
Another significant pro of multi-level page tables is that if there
are pages that aren’t currently being used in RAM (and there are usually
many of these unmapped pages, since most processes don’t use that much
memory), we don’t have to traverse the n levels for those
pages’ mappings, nor do we even have to store the entries for those
pages in the lower levels. In fact, the only page table we really need
in RAM at all times is the top-level page table. This saves us a lot of
space.
Anyways, that’s only one of the optimizations that are commonly used
in real-world VM systems. This sort of paradigm with multiple layers of
indirection shows up all the time in systems because of its
ability to bestow a single pointer with access to magnitudes more data
than it might’ve originally had. There are many more details that go
into a complete VM implementation…
One last thing I want to mention: my OS professor once told us about
how when he gave the qualifying exam for the graduate-level OS course,
he included a question related to VM. Specifically, it asked something
along the lines of: given that this minimal OS implements a static
(non-growing) stack, how would you implement a dynamic stack?
Apparently, the question was hard enough that he ended up having to
remove it from the grading at the end. All of this to say that even
graduate students with a significant amount of systems experience
struggle with a complete understanding of VM.
On "RPG sites" and their slow death
Sunday, 16 Jul 2023
From the age of about 10, I want to say, I was obsessed with RPG
sites, forums, whatever you'd call them. They go by several
unofficial names. My first and most significant experience of the
word "RPG" wasn't D&D or Monster Hunter, or rocket powered
grenades in Call of Duty. It was a website like this one.
And this one.
And this.
You get the idea.
It's honestly one of the most convoluted things to explain to
someone, which is partly why communities like these tend to be so
insular and closed-off. Not because they necessarily want to be,
but because they're exist to play an incredibly niche role. It's
very lore-heavy, so it appeals to the detail-oriented. At the same
time, it requires a consistent flow of creativity, productivity,
and interacting with strangers, so it's hardly a monastic or
anti-social activity.
The premise of the majority of RP sites goes along these lines:
you roleplay as an animal, most commonly a wolf (notably, there
have been lions and horses. Some websites focus on human
roleplaying, but in general it's a free for all, with werewolves,
actual anime characters, and yes, real people). The setting is some
arbitrary land with a few (or a lot of) intrinsic rules. There may
be magic, or it may be centred around realism. Often, there are
some kind of cohort, like packs, prides, or species. In-character
interactions are centred around inter-cohort conflict and politics,
ranging from coups, to powerful family dynasties, entire religions,
and more. The fact that you're an animal is probably the least
important factor in all of this.
I know a few people who did roleplay formerly, but they got
their start in ones that were chatroom-based, which I never got
accustomed to. One of, if not the first roleplay
forums I registered on was moonisland.rpg, which has long
since been defunct. It must've been back in about 2014 or earlier,
when Discord didn't exist and everyone had to use
Chatango, or Skype. When I logged back onto Chantango
after at least 5 years of forgetting its existence, I could see my
friends' accounts and their bios, which often had short
descriptions of their characters. None had been online for several
years. When the link to Moon Island RPG finally broke, it was like
a chunk of my adolescence had split off as a calving iceberg
plunging into the ocean.
Gaining "sentience"
I was never really self-conscious about it. Part of me knew it
was weird, or at least out of the ordinary. But this was even
before I knew about the in-joke of furries, otherkin, off-color
remarks about bestiality, etc. To me at the time, it was very much
in the same vein as real works of fiction such as the
Warriors series and it didn't strike me as being a little
perverse until much, much later. And certainly it wasn't anything
to be embarrassed about— in fact, the only thing that kept me from
talking about it with others was the fact that there would be so
much exposition and backstory involved. Perhaps fortunately, these
sites tended to have in-depth rulesets and mechanics that would be
difficult to explain in one sitting to someone totally unfamiliar
with the medium. On the other hand, once one got accustomed to the
framework, virtually every other roleplay site would follow the
same basic rules, which included restrictions on chronology (there
was something called "liquid-time"), on "power-play", and more
granular things like word count limit or style guidelines.
I vaguely remember the moment in which I realized that this
whole thing was aberrant, and it was when someone around my age, a
member of a site, said that she would never have opened this site
on her laptop, that she only ever posted and browsed on her phone,
and that she would die if a classmate found out what exactly she
was doing. And it made me think, huh, maybe this whole charade is
weird and perhaps even insane. A whole world built around the
premise of you pretending to be an animal, where these animals have
the mind and intelligence and personality of humans, and therefore
live lives as intense as any one of us.
So why am I confessing all of this to you now?
I'm not exactly embarrassed. Well, maybe a little bit. But I'm
glad that, for the majority of the time I've spent on these sites,
I did so without the shadow of shame hanging over my head. I
enjoyed it sincerely. And I'm certainly not placing any blame on
that one girl, whose intention was by no means to shame me, or
anybody else in that chat. I'm a little surprised that no one
responded with righteous indignance, though. It was a real naked
emperor moment, at least to me.
Shadowing the decline of the 'old internet'
Anyways, to get back to the reason why I wrote this: these sites
are going through a long, protracted death.
It was particularly damning when I was trying to find example
websites to put at the beginning of this post, and half of them
were completely dead, a quarter were inactive, and the rest were
simply just hanging in there. None of the websites I was on when I
began roleplaying exist anymore, at least not in their current
iteration.
Maybe it's me being pessimistic, but by now I can say that I've
had enough experience with them to see the overlying trend— that
is, their undeniable decline. And I think that's a shame, and I
think that it is a symptom of what people on Neocities love to talk
about: the increasing inactivity on forums as more and more people
flock around centralized social media, the general lack of
incentive for creativity, whatever. Just saying the words "Bulletin
Board Forum" feels like it dates me! It's what everyone has on
their manifestos. A part of me understands that these RPG forums
and communities pose somewhat of an anomaly. They should've died
out a long time ago, or at least be much less robust than they are
right now (although today they are still a shadow of their former
selves, in my opinion, which saddens me to no end. There is simply
no way to turn back the clock, other than to look at them through
what pages the Wayback Machine has managed to crawl through and
save).
What forums remain are often maintained faithfully by the
memberbase that was once a part of the newer generation. The
original members, way back in the early 2000s, are mostly all
living their adult lives now, probably well into their 30s and
perhaps even in their 40s. When I joined at the age of 10 (which
broke basically every site's rule that a member had to be over the
age of 13, 16, and in some cases 18) there were many people who
were teenagers or in their twenties. I expected a steady stream of
tweens and/or younger teens to continue to nourish the memberbase,
but from where I'm standing now, that has mostly dried up. Many
more people seem to be leaving rather than joining. I don't mean
for this to come across as narcissistic, but it feels as if I was
part of the youngest group to join, the final wave of newcomers now
left to commandeer and inhabit these unmoored ships. Now, the
average demographic of these sites seems to be composed of people
no younger than college students. In fact, it's more likely that
you'll see a mother with kids than a 13 year old posting about her
sparkledog character.
I don't want to use the word stagnate, because of its
unequivocably negative connotation. But make no mistake, I'm glad
that these communities have a core that looks to the long-term. I
see the same people who have written on these sites (sometimes on
the one particular site in question!) for close to a decade, in
some cases for over a decade (very few sites can claim to have
lasted that long without fading off into oblivion, inactivity, and
expired domain names, but they do exist).
For a time, posting on these forums made up a vast majority of
my time spent online. I was 13 when I got to be a moderator,
because I'd lied and said I was 16. Maybe this says something about
my own age, because this was still around the time where it was
normal and even encouraged to lie about your personal information
online (and I think getting my start on online socialization in
these websites ingrained into me this old-school habit). It was
fun, and stressful, and I had to step down prematurely before
leaving RP sites altogether and going on a long hiatus, and I often
wonder what these people are doing now. Many of them were either
adults, college students, or about-to-be-college-students. They
were all on the cusp of something significant in their lives. On
the personal OOC (out-of-character) boards, there were posts about
marriages, graduations, and the mundane everyday. There was also a
lot of venting and tragedy, as expected.
I think COVID quarantines injected new life into the ailing
scene, but now it's winding down again. Every year has its ups and
downs, with holiday seasons, with school breaks, etc. But again, I
tell you, it used to be so much more. And there's really no way to
bring what used to be back. Believe me, I've tried. Maybe it was
the rose-colored glasses that 13 year old me had on, that made me
feel as if the possibilities were limitless and that this virtual
world was bursting at the seams with activity and ideas. Filled
with HTML and CSS that broke just about every W3C guideline. Filled
with photomanipulations and art both egregiously bad and
breathtakingly beautiful. Filled with disgusting purple prose,
laconic phone-posts riddled through with disastrous typos,
sometimes with genuinely fantastic, touching writing that I still
think about to this day.
This was really how I learned to code (badly) w/r/t web design,
how I taught myself digital art and photomanipulations, and how I
learned to write. I wrote a lot. If I wasn't involved in
RP sites, there's no telling when or even if I'd get
around to learning web design and Photoshop, even starting with
digital art, skills that serve me well to this day. Like it or not,
these sites made me who I am today, which is why I can't help but
be a little upset that they're so... diminished.
What I have taken away
Here's a list of things (not exhaustive) that I learned through
posting on RP forums and interacting with members:
- HTML/CSS
- Swans, the band
- Gillian Welch, the musician
- Ozymandias by Percy Bysshe Shelley
- T. S. Eliot
- The Raven Cycle by Maggie Stiefvater
- Cormac McCarthy
- The Imitation Game (and therefore Alan Turing lol)
- A bunch of zoos in Germany that have wolves
- The Creative Commons license
I understand that people move on with their lives. You can't
really roleplay as glittery horses on the internet forever. But
where are the kids? Is the death of forum roleplay really
inevitable? I find that part hard to accept. A lot of the webpages
aren't even archived, so hours and hours, weeks and months of
man-effort are, what? Lost to time, just like that? I click on a
website and the last post was made two years ago. Actually, the
most recent post is spam left behind by a bot advertising a
suspicious brand of Russian viagra, the title in tangled Cyrillic
and the username an obfuscated sequence of meaningless letters and
numbers. Or, the admin of the website has shut it down and rendered
thousands of words and histories inaccessible to the public. What a
total ghost town. Where did all these people go? When exactly is it
decided, when the very last post is made?
And the writers— are they okay, now, living out real life? I
remember being 14 or so, and trying to console a 30 year old woman
who was having a depressive episode, insisting to me that she was
ugly, fat, and unlovable. I remember reading the posts of someone
who had gone through a horrific accident, had been burned severely
on her arms and upper body. She had, for some reason, posted photos
of her (healed) wounds in explaining why she had been absent for so
long.
A few months ago I got the news that one of the members I knew,
that I roleplayed with, who was rather well-known and had been with
the site for a long time, had died of cancer.
I didn't know her that well, but all the same I grieved. I had
written with her before. But she was gone forever, and I'd never
see her writing ever again.
When I said "long, protracted death", maybe it was too
pessimistic. Maybe the decrease in memberbase is asymptotic— maybe
there will always be a nucleus of people, no matter how small, who
are willing to put in the work to keep a forum alive. Maybe
extinction was never a possibility. But the "golden era" has
definitely passed, and I don't see much reason for a resurgence.
Hell, call me a hypocrite; I haven't posted regularly on these for
years.
This post is my little elegy for these communities. May they
continue to be unacceptably socially weird. May they continue to
house the work of young artists and writers all over the world, and
act as a hub for their inspiration. Most of all, may they continue
to thrive, create, teach, and welcome, proving that real connection
is still possible in an internet swamped by the detritus of the
powers-that-be.