Virtual Memory

And we get to the end of our story. We’ve figured out how to share resources, how to schedule students to use resources, and created new technologies along the way.

We have one final problem to tackle, though. Let’s look at it again:

Now that we have multiple cores running, our memory is getting full. Because more people are using the library, there are more books on the shelves. There needs to be more information that we request from the book depot and this is piling up quickly. Students are using their stack and heap spaces at a huge rate. As we allow more students in at one time, they also need their own stack and heap space. Because we want things to be efficient, the librarian continues to give consecutive space on shelves. Some of this space is just sitting there, lonely and empty. “I’m going to reserve this space on the shelves for this student, these two rows, in case he might need them”. While some students do need all two rows, what about those that don’t? How can we efficiently use that memory?

Address Binding

Virtual memory is a way for each process to have its own representation of primary memory. So each student has their own view of what the library looks like. Let’s now pretend that the librarian never wanted the students to actually see the shelves, instead, they must request books through a cool new app called Virtual Library™. The shelves are now hidden behind the wall and the Virtual Library™ app shows a representation of what’s on the shelves. Remember that processes shouldn’t know much about each other, so for each student, we don’t want to not show information about other student’s work. We also want to make sure that empty space is not just going to waste on the shelves. To help with this, the Virtual Library App™ provides a map of the shelves.

Our shelves are labeled 0 – 1000000. We have shelf 1, shelf 2, shelf 3, and so on. For each student, the app shows that their heap/stack space starts at shelf 1 when in reality, the librarian can instruct the busboys to put their contents on any physical shelf. So their Virtual Shelf 1 might actually be tied to Physical Shelf 89570. As far as the student is concerned, they have all of the shelves in the Library to themselves because that’s what the app is showing them! In reality, a complex mechanism happens to connect physical addresses to these virtual addresses. This is called address binding.

How does this help? Well, we can still tell the student that they will have two shelves for their stack. We could tell them they can have 1000 shelves, it doesn’t really matter. As the student writes data, he asks for the notebooks to be stores on shelf 1, spot 1. Then on shelf 1 spot 2. His Virtual Library™ shows notebook 1 on shelf 1, spot 1 but in reality, the book is probably stored on Shelf 89000, spot 17. Another student might call for his own notebook to be stored. For that other student, the app will also say shelf 1 spot 1, but behind the scenes, it will be placed right after the previous student’s data, in Shelf 89000 spot 18. No physical memory is being wasted!

So the difference here is that on the physical shelves, the requests from all students are stored sequentially. There is not space being unused. Previously, when we allowed students physical space directly, some of their two rows might have not been needed. Instead of having Row 1 and 2 for student A and then row 3 and for for student B. Now, any row and spot can belong to anyone!

The Virtual Library™ uses something called a pagetable to transform a virtual address to a physical address and to show a virtual representation of the shelves to the student.

Pages

When we look at our Virtual representation of the library, we could create an address with a lot of information. For example, Shelf 10, Spot 5, Chapter 3, Page 199, Line 17. However, this would be a bit too complex. Instead, we stick to whole Books, since this makes it faster to retrieve. A page, in virtual memory speak, is a contiguous block of virtual memory. So “Spot 5” is considered a page of virtual memory.

Even with virtual memory, our shelves could possibly get full at some point. If this happens we’ll need to move some book back to the depot to make room for the ones that we need. Maybe we can send the books that are least being used. The process of substituting books, or blocks of memory, is called paging.

The end… sort of

We finally have a system that works efficiently. It’s easy to find information, memory is not going to waste and resources are being shared fairly and safely. Our Library is perfect!

Or is it?