OSDev.org

Hi,

I have some considerations about implementing memory swapping in kernel.

a) is it really needed at all? nowadays with ~1-2GB of memory for each PC?
b) the user process knows better about which data is important or not compared to kernel. A user process can simply write some of its unused data to disk and freeup some memory itself and retry if malloc fails. So swapping can be implemented by the user process itself.

Any ideas?

a) Yesterday I worked on 6GiB of raw image data at once. That's not going to fit into 1-2GiB of RAM.

b) I agree.

Some people think delayed loading boots performance and is useful...

The best thing about paging is that you can write a small app which expects only to work with small files. If your OS does swapping it'll work with a big file also. If not - then you're in trouble.

Implementing swapping in user apps won't give you good performance, because the app doesn't know about the memory requirements of other apps. And it's cumbersome.


I'd implement it but design it in a way that the OS doesn't use it until absolutly neccessary. A user app can implement it's own swapping nonetheless.

Don't put the Swapping into the user process except in special cases.
The process may mark some pages as "non swappable" for realtime purpose.

a) is that also what you will expect/require from all devices you will run your OS on?
b) Swapping is not a thing of the past yet. If you don't do it in-kernel, then you will have to do it in userland.

I think I'll use swapping, but I've two questions:
1) In your opinion is swapping useful also for the kernel? Or only for user apps?
2) Why does swapping improve loading boots performance?

Hi,

Cemre wrote:b) the user process knows better about which data is important or not compared to kernel. A user process can simply write some of its unused data to disk and freeup some memory itself and retry if malloc fails. So swapping can be implemented by the user process itself.

A process might know which of it's pages are least important; but has no idea if these pages are more or less important than pages being used by other processes or pages being used by the rest of OS (e.g. file system cache, buffers, etc). A process doesn't have enough information about everything else to make efficient decisions about whether to send any of it's pages to swap or not.

Secondly, most programmers couldn't be bothered managing their own linear memory usage (they use "malloc()" and "free()" so they don't need to think about which areas they're actually using) and some programmers use garbage collection so they don't need to care about freeing any of it either. The idea that programmers actually care enough about their physical memory usage to implement their own swapping (and care enough to do a better job than an OS's default swapping) is unsubstantiated (or perhaps even unrealistic).

An effective method for determining which pages to send to swap needs to be system-wide. However, if application programmers care enough, it would help if a process could provide suggestions. For example, the OS could give every page a rating and send the page/s with the lowest rating to swap space, and processes could (optionally) modify this rating for any pages they're using (although a process shouldn't be able to increase a page's rating too much, because then you can end up with "RAM hogs").

The rating itself should probably be estimated with something like "rating = (cost_of_sending_page_to_swap + cost_of_retrieving_page) / time_until_page_needed_next". The "cost_of_sending_page_to_swap" could be zero (e.g. unmodified pages that are part of a memory mapped file, where the data is already on disk). The "cost_of_retrieving_page" depends on where the page's data would be reloaded from (e.g. imagine a memory mapped file on a floppy disk). The only part that can't be measured accurately is the "time_until_page_needed_next" - the OS would guess this based on usage history, but a process might be able to provide a more accurate estimate.

Cheers,

Brendan

1) In your opinion is swapping useful also for the kernel? Or only for user apps?

Even if I implemented swapping, I wouldn't swap the kernel itself nor any page tables. I would only swap user code/data pages.

Why does swapping improve loading boots performance?

Some people think delayed loading boots performance and is useful...

it does... but not always, delayed loading would prevent loading unnecessary code/data pieces of the user program. some portions of the program may never be used when program is started with some certain command line parameters. But receiving several page-faults due to delayed loading right after the program is started, would impact performance either...

Main concern about swapping is that: filesystem is ( in my case ) a user process, and I have an interface for dealing with different filesystem types. Kernel would try to use the filesystem to swap some memory.

Wouldn't it be wierd for the OS-Kernel to depend on a user program behind an abstract interface?

Thanks for the opinions btw... Best regards.

Hi,

MarkOS wrote:I think I'll use swapping, but I've two questions:
1) In your opinion is swapping useful also for the kernel? Or only for user apps?

IMHO swapping is useful for any page that won't be needed to retrieve pages from swap again. This includes kernel-space, and paging data structures (e.g. send page tables to swap space).

However, for something like a micro-kernel you wouldn't be able to send most of the kernel's pages to swap space (most would be needed to retrieve pages from swap again) so it probably wouldn't be worth the hassle supporting it.

MarkOS wrote:2) Why does swapping improve loading boots performance?

It doesn't - are you sure you're not thinking of memory mapped files (which is a different part of the whole "virtual memory" thing)?


Cheers,

Brendan

Brendan wrote:

MarkOS wrote:2) Why does swapping improve loading boots performance?

It doesn't - are you sure you're not thinking of memory mapped files (which is a different part of the whole "virtual memory" thing)?

I've read it from the dr_evil post

However I think I'll use memory mapped files. But for now I don't know how to implement them (for example if I have an ELF file on the disk, I can load it little by little instead that all, but how can I resolve its external symbols? So for now I load all the ELF file, relocate it and resolve all its dependencies)

Memory mapped files don't help you to resolve relocations but they can improve an application's performance.
The point of them is that you don't have to use thousands of fread() and fwrite() calls that copy data from kernel to userspace. Less unnecessary copy operations / less function call overhead => better performance.

Korona wrote:Memory mapped files don't help you to resolve relocations but they can improve an application's performance.

Yes, I know. The thing I don't understand is how memory map an ELF file, if it must be modified with (few times) relocations and with external symbols linking.
I think I must resolve symbols after the page fault, while I read the file into memory, but it's not so simple.

Hi,

Korona wrote:Memory mapped files don't help you to resolve relocations but they can improve an application's performance.
The point of them is that you don't have to use thousands of fread() and fwrite() calls that copy data from kernel to userspace. Less unnecessary copy operations / less function call overhead => better performance.

I guess I should point out that the reverse is also true, in that it's usually more efficient to read sequential sectors than to have heads bouncing all over the disk (given that seek times are typically slow compared to the time taken to read sectors). Because of this memory mapping some files can reduce performance (even when less data is actually read), especially for executable files where EIP jumps around everywhere.

The other problem with memory mapped files is there's no graceful way to handle file I/O errors. For example, if you memory map an executable and the executable is in the middle of an instruction when it generates a page fault, and then you get a read error while trying to read the data for that page, what do you do? The only option would be to terminate the process with the equivalent of a "blue screen of death" (I've had very ugly situations on Windows 98 where an executable file from a CD-ROM with read errors was memory mapped). For this reason I'd refuse to memory map any file that isn't on reliable hard drives (e.g. refuse if the file is on CD-ROM, floppy, flash memory, etc). Of course there's no reason you can't just load the entire file to begin with and then pretend it was memory mapped (in cases where you refuse to memory map) so that other software doesn't need to care if memory mapping should/shouldn't be done (and doesn't need to care where the file is actually stored).


Cheers,

Brendan

MarkOS wrote:Yes, I know. The thing I don't understand is how memory map an ELF file, if it must be modified with (few times) relocations and with external symbols linking.
I think I must resolve symbols after the page fault, while I read the file into memory, but it's not so simple.

Ideally, object files would not be relocated at all. If the file specifies a preferred address and that range in the program's virtual address space is available, you can memory map the on-disk file directly with no relocation. If you want to avoid having to load the whole object file into memory when it needs to be relocated, it must be handled in the page fault. It's not simple, because some address values in the program's code could be on the page boundary.

Another design issue is what to do with a relocated page if it gets paged out later. You could store the page in the swap file to avoid relocating it again, or just discard it and relocate it every time it needs to be paged in.

What about when multiple instances of a shared library are relocated at several different addresses? Using the single copy in the original file instead of using separate, nearly identical copies in the swap file might improve disk caching and/or locality of reference. As an optimization, if there's another copy of the page relocated to a different address still in memory, it would likely be much quicker to calculate the difference in virtual addresses, and simply relocate from one address space to another, avoiding a disk read entirely.

b) the user process knows better about which data is important or not compared to kernel. A user process can simply write some of its unused data to disk and freeup some memory itself and retry if malloc fails. So swapping can be implemented by the user process itself.

In Windows there is the WM_COMPACTING message, sent to all top-level windows when memory is running low. It's the OS's way of asking apps to discard what they don't need. I doubt many programs have ever implemented it though. It also says it's only for compatibility with 16-bit Windows (for some reason?).

But the idea is that you could send apps some kind of signal asking them to discard memory if it's not vital, while still being able to do swapping at the kernel level.

Although really I reckon most app programmers are happier letting the OS designers take care of their memory. It's just easier app design that way.

I once tried to create a text editor that could perform its own swapping -- so that it could live inside a specific limited memory allocation, and still edit an arbitrarily large file, efficiently. It was horrifyingly messy, and after working on it for far too long, I gave up. I much prefer virtual memory with the swapping done in the kernel. With a nice small kernel, and nice small apps, and nice small data files -- you will never need it. And if you bog down your system enough to actually need it, then it's perfectly reasonable to expect that you are going to pay a big performance price for that.

I think that it is best (on machines where you can do it) to have the kernel live in physical memory, not virtual memory. So in my case, kernel pages cannot be swapped, because it's impossible.

I think Brendan's concept of swapping is nearly ideal -- except that you need to also encode the priority of the process, along with its own estimation of the probability that it will need the particular page "soon".

Brendan wrote: For this reason I'd refuse to memory map any file that isn't on reliable hard drives.

And that's the reason I say: always read the entire file into a big user memory allocation, give those pages a very low priority, and let the vmem swapper page it all out to standard swapspace on a nice reliable hard drive. Then you can avoid the entire formalized concept of a "memory mapped file" in the first place.