OSDev.org

How would I implement swapping from disk to memory if a page fault occurs.
The writing and reading from Disk works with PIO.
Should i create a process that handles all the pages that should be swapped in in a query? If, should the scheduler treat this process specially?
Or can I simply let the page fault handler itself copy the date, so that each process is busy with swapping in it's own pages?

How would this usually be implemented?

thanks in advance
megatron

Hi,

megatron23 wrote:How would I implement swapping from disk to memory if a page fault occurs.
The writing and reading from Disk works with PIO.
Should i create a process that handles all the pages that should be swapped in in a query? If, should the scheduler treat this process specially?
Or can I simply let the page fault handler itself copy the date, so that each process is busy with swapping in it's own pages?

How would this usually be implemented?

How it's usually implemented is different for different OSs (and things like "micro-kernel vs. monolithic" make a huge difference).

Normally, a kernel has a set of different abstractions for different things. For example (for file IO), you might have a "virtual file system" abstraction that you can use without caring which file system you're actually talking to; and below that you might have a standard interface that all file systems provide so that virtual file system doesn't need to care about the differences or implementation details for any specific file system; and below that you might a generic "block device" abstraction so that the file system code doesn't need to care about the differences and implementation details for the device itself.

For swap, I'd do something similar. For example (for swap space), you might have a "swap manager" abstraction that you can use without caring about which "swap provider/s" you're actually talking to; and below that you might have a standard interface that all "swap providers" provide so that the swap manager doesn't need to care about the differences or implementation details for any specific swap provider; and below that you might other abstractions that swap providers use (e.g. the same "block device" abstraction that file systems use) so that the swap provider code doesn't need to care about the differences and implementation details for the device itself.

This might sound complicated; but imagine if the end user wants to use a raw partition on a SATA hard drive for swap space, and use a swap file on a USB flash stick for more swap space, plus use "swap service" on the local network for even more swap space. In this case the swap manager might know how fast each swap provider is and how full each swap provider is, and automatically use the fastest swap provider that has free space (although it could also do some load balancing - e.g. if the fastest swap provider is going flat out trying to keep up, shift some work to the second fastest swap provider). Now imagine that the user wants to make sure that if any of these devices fail there's some redundancy - swap manager could make sure that each page is stored on at least 2 different devices (or, use the fastest 2 devices that aren't full). If the user wants to add a new swap provider, the swap manager could just add it to its list and start using it without the virtual memory manager knowing or caring. If the user wants to remove a swap provider, maybe the swap manager can shift any data from one swap provider to another to allow for safe removal.

Basically, the first step would be to decide what features you want to support, and then define the abstractions in a way that suits the rest of the OS. We can't predict what features you might want to support; and most of us probably don't know anything about the rest of your OS (and therefore won't know what might suit your OS).


Cheers,

Brendan

To implement swapping, the first decision you need to make is whether to do swapping in per-process level or per-page level.
Then you need to work out a way to mark and manage the swapped portions.
For process swapping, you can add a flag, swap block number, size fields to its proc struct.
For page swapping, you can clear the present bit and change other bits to a block number.

When you understand what i said above. It's straight forward to write a "swap manager":
1. when there's not enough memory, the process call a "swap function" to swap out something(find the swappable process/pages, find some free space in disk's swap area, write these things to disk, update some bits, do bookkeeping), so that you have more free memory to continue,
no context switching happens(in fact none of the "swap manager" thread's business), if still no free memory, it just fails or retry with stronger forcement or sleep for some period and retry, you can choose your strategy here.
2. Periodically wake up the "swap manager" kernel thread. Let it find the swapped out process/pages, if there is enough memory, swap it in, update bits and do bookkeeping.
3. If nothing satisfied, "swap manager" just sleeps.

I suggest you to read unix v6's source code. It's simple and slim(less than 300 lines). And it has been carefully written to avoid many pitfalls(choice of swap in/out,deadlock,etc..) you may encounter in implementing your own swap manager.

The first thing you need to consider is if swapping to disk should be implemented at all. Many years ago, every operating system basically needed this feature because available RAM was smaller than applications and their RAM usage. Today, for a typical hobby-OS, this is normally not true. You have several GB of RAM, the operating system might use a few megabytes, and typical test (and real ones as well) applications are in the same range. The only real issue is disk buffering which could easily fill-up all available linear address space and physical RAM.

What I do is to free non-dirty disk buffers when physical memory is getting low. I don't support swapping. If physical memory gets exhausted, and there are no disk buffers that can be freed, the OS will panic.

I also support a related feature, demand loading pages in an application. I could also implement freeing read-only pages (code and const) in the application image, but I haven't yet as it would have little effect, and freed pages that have been used are likely to be used again.

Hi,

rdos wrote:What I do is to free non-dirty disk buffers when physical memory is getting low. I don't support swapping. If physical memory gets exhausted, and there are no disk buffers that can be freed, the OS will panic.

Fred is the lead graphics designer at a large company. For the last 3 months he's been working on all the graphics for the company's new product, but today he finally finished it all. It's Thursday, and everyone else went home 2 hours ago. Fred stayed late to finish the graphics because his boss told him he can have the day off on Friday if everything is done. All the files are sitting on his computer all in a shared filed or NFS partition or something - it's about 2 GiB of files all ready to go.

Fred sends an email to his boss saying all the graphics are done, and that he will be taking the day off tomorrow. While doing that he sees a request for some changes to a promotional screenshot in his inbox. It's not too important but Fred is curious and opens the screen shot in 4 different windows and makes a few different changes in each one to see what looks the best.

His wife rings his mobile phone. She wants some milk or something. Fred decides to think about the screenshot over the weekend and go home (it's getting late) so he tells his wife he'll be homes soon, turns his monitor off (but leaves his computer running so that everyone can access those 2 GiB of graphics files tomorrow), grabs his keys and leaves work.

Now...

Fred's computer has 4 GiB of RAM, but the OS can only use 3 GiB of it because the motherboard is a bit crappy (doesn't relocate RAM underneath the PCI hole).

The image editor Fred uses is a high quality thing (as you'd expect for a graphics designer) - it converts image files into 4 doubles per pixel (RGBA) while manipulating images to reduce error, and keeps older copies so you can undo changes. The screenshot was 2560 * 1600, so each image costs "2560 * 1600 * 4 * 8 bytes" or about 128 MiB. There's 3 different copies of the image (for the "undo changes" feature) for each window, and 4 windows. This means that about 1.5 GiB of the computers RAM is tied up in dirty/modified graphics data.

The OS, GUI, graphics editor and other things take up another 1 GiB of RAM; and there's 500 MiB left over that's being used for disk caches.

Friday morning, everyone (except Fred, he's gone to the beach with his wife for a well earned 3-day holiday) comes to work. Fred's boss finds out that the graphics were done and lets everyone else who's working on the project know. They're all copying it from Fred's computer (via. the network) and making small adjustments and telling each other they changed a few things and re-downloading, etc.

So...

Does the OS realise that there's 1.5 GiB of dirty/modified graphics data that isn't being used, and send it all to swap space so that it can use that RAM for file caches (and avoid pounding the daylights out of Fred's hard drive all day)?


Cheers,

Brendan

The producer of the graphics software shouldn't have kept all this data in memory, rather should have written it to disk. Keeping it memory mapped with a disk-file image is the best way, that also automatically keeps the changes in case of sudden reboots. If the OS lacked swapping, and simply refused to overcommit memory, the application makers would use sensible ways to ensure the data was safe, not relying on swapping space. Additionally, virtually all languages have memory allocation functions that can fail, and that software need to check for. The difference between an OS that support swapping and one that doesn't, is that the former would allow memory to be overcommitted, while the latter wouldn't.

Besides, I know how badly Windows behaves when it starts resorting to swapping. The whole system virtually becomes unusable.

However, the problem of balancing disk buffers with application memory usage could become complex for a typical desktop system. For an embedded system, not implementing swapping is not a problem. Some such systems don't even have access to swap space at all.

Take our commercial application as an example. The PC has 256MB of RAM, but the uncompressed animations are considerably larger than that, and the files themselves are also larger than the available RAM. What RDOS will do in this case is to let the disk-buffers grow til memory starts to get exhausted, and then would use a second-chance algorithm to free them. This means that image-files will need to be read from disk from time-to-time, but that common sequences are normally cached.

Nice topic!

So I´m mostly with rdos, means I don´t really like swapping.

I´m working on a mikrokernel and wouldn´t really know how to implement swapping there (because the code for writing to disk is in some process). I would need to have the possibility to mark memory as NOT_SWAPPABLE , so that the code for writing data to disk (or somewhere else) could not be swapped out. Next problem would be, which pages should I pick for swapping out? Performance shouldn´t be a problem, because the disk is slow, so some context switches (to read data from disk) cost nearly nothing.

But I´m more interested in how would I tell Processes to lower their caches when I need memory? How will I know that they finished lowering their Caches (to know if I now have enough free memory or that I need to wait a bit longer)? How long should I wait to finish this process?

FlashBurn wrote:But I´m more interested in how would I tell Processes to lower their caches when I need memory? How will I know that they finished lowering their Caches (to know if I now have enough free memory or that I need to wait a bit longer)? How long should I wait to finish this process?

I let device-drivers register hooks for this that gets called as memory gets low. The call also has a parameter for urgency, which the driver should take into account. More urgency would mean a more aggressive approach to freeing memory. The only drivers that really hook this function right now is the disk cache driver, filesystem meta-data cacher and the file data cacher.

The hooks are not called by pagefault handler (that could cause deadlocks), but rather by a dedicated kernel thread that is woken up by the physical memory allocator.

Or iOS memory management for an alternative approach.

While I think that swapping will become obsolete in the near future (due to the amount of ram in computers increasing so quickly), I don't see why you wouldn't support it at all. Even if you dislike how slow it is, etc, once your OS frees non-dirty disk caches and such things that can be freed, swapping out unused memory wouldn't be too bad if you still need more. It not like it particularly difficult to implement - I whipped up an implementation in an afternoon (granted, the algorithm used is extremely simple, but it works) and I barely had to modify other parts of my OS code to get it to fit in. You can always have it as an option that you can turn off.

You need to think about how the data will be stored on disk. You'll need some sort of filesystem to retrieve the data when you want it. And then for when it needs to get swapped in, you could just have the pagefault handler call the method that swaps back the page.

-JL

piranha wrote:While I think that swapping will become obsolete in the near future (due to the amount of ram in computers increasing so quickly), I don't see why you wouldn't support it at all. Even if you dislike how slow it is, etc, once your OS frees non-dirty disk caches and such things that can be freed, swapping out unused memory wouldn't be too bad if you still need more. It not like it particularly difficult to implement - I whipped up an implementation in an afternoon (granted, the algorithm used is extremely simple, but it works) and I barely had to modify other parts of my OS code to get it to fit in. You can always have it as an option that you can turn off.

It depends. If you have for instance PE or ELF for application executables, it's not a big deal to implement swapping on those, and possibly on allocated heap memory as well in application space. But then some applications probably wants to protect themselves from being swapped out (for instance mission critical code), and then you need ways to mark pages as non-swappable.

If you want to extend it to pages in kernel space it is a totally different thing, as then you need page attributes for locking pages in memory, and all code that allocates memory basically needs to deal with that. Many parts in the kernel cannot be swapped-out without catastrohpic results. That's why I have the code for lowering caches in kernel-space. That's about the only thing that is relatively easy to do in kernel-space.