OSDev.org

I'm implementing swapping in my virtual memory manager.
I've yet implemented memory-mapped files, shared memory, and other memory related things.
I have also a function (it's not complete) that choose pages to swap.
The only thing I don't know how to handle is the swap file. I don't know which would be a good format for the swap file.

Have you any idea or document to read about swap file format?

I think I will mark the page to swap to not present, change the physical address to an offset in the swap file. So when the page will be accessed the next time, I will load the page data from the swap file at the offset saved into the PTE.
In the swap file, I will save the pages one after another without any structure.

However I need a good algorithm to choose which pages are the best candidates to be swapped out... Do you know any good method?
(For now I swap out pages randomly from a task in the lowest priority list)

Jeko wrote:In the swap file, I will save the pages one after another without any structure.

Heh, and how will you plan to save information about the free pages in swap file?

egos wrote:

Jeko wrote:In the swap file, I will save the pages one after another without any structure.

Heh, and how will you plan to save information about the free pages in swap file?

mmmmh I don't know
The swapping is a really difficult thing...

Why don't you use one file per page?
you only have to load a single file and map it.

for example:
you have to swap the virtual page 0x00001000.
so you write the data of these page to a file: /swap/2/00001000 - the 2 is the PID of the process.
So if the process with the PID 2 want's to access the page at 0x00001000 you just have to load the file, and map into the process' virtual mem. space.

RedEagle wrote:Why don't you use one file per page?
you only have to load a single file and map it.

for example:
you have to swap the virtual page 0x00001000.
so you write the data of these page to a file: /swap/2/00001000 - the 2 is the PID of the process.
So if the process with the PID 2 want's to access the page at 0x00001000 you just have to load the file, and map into the process' virtual mem. space.

Yes, I think I will do as you say. It's a good method. I must only choose how to handle directories and files into the swap file.

But the most important problem is how to choose pages that are best candidates to swap

Swapping algorithms are one of the most researched topic's of OS-Development.
It is a very complex piece of software. I'd say you start with something simpler, like 'random-swapping', which should suffice for the start. Also search for 'LRU-, clock-algorithm, etc..'

cyr1x wrote:Swapping algorithms are one of the most researched topic's of OS-Development.
It is a very complex piece of software. I'd say you start with something simpler, like 'random-swapping', which should suffice for the start. Also search for 'LRU-, clock-algorithm, etc..'

Yes, for now I'm swapping out pages randomly from the address space of a task in the low priority list... But I want a better algorithm...

Jeko wrote:

RedEagle wrote:Why don't you use one file per page?
you only have to load a single file and map it.

for example:
you have to swap the virtual page 0x00001000.
so you write the data of these page to a file: /swap/2/00001000 - the 2 is the PID of the process.
So if the process with the PID 2 want's to access the page at 0x00001000 you just have to load the file, and map into the process' virtual mem. space.

Yes, I think I will do as you say. It's a good method. I must only choose how to handle directories and files into the swap file.

But the most important problem is how to choose pages that are best candidates to swap

No way... Using each page as a file on a disk will surely be a huge amount of overhead. Most importantly, this involves the huge overhead of the namespace lookup.. So if the process has 4000 pages, the filesystem driver has to do a lot of work to access the address that is required...

Swapping is a very fast process. Start a task manager in windows, and enable the PF delta (Page fault delta) or the page faults column in the process list. Now simply open notepad or any other application. Even if you select to open a file or even just minimize the application, there are almost a 1000 swaps from the disk (each of 4 kB). This number may not follow in the subsequent work... But this clearly indicates that your swapping system needs to have great performance. If you use a single file for the swap file, then a lot of overhead is eliminated.

For a swap file, you could have a table at the starting that specifies the address in RAM and the flags (information about the page)... You could also have a hashing technique that would speed up the access to the swap file for a particular page.

First of all, the concept of marking a page as not present and changing its address in the PTE to the offset in the pagefile is a good idea. Very similar to what Windows 2000 does (and I imagine later versions). They add some more complications in there, but that's the premise. As for knowing where to place it in the swap file. Well what I would do is use the first page of the swapfile (since nothing is ever mapped to address 0) as meta-data. Basically I would put structures there to track swap file freelists. A simple system could be making part of that first page a bitmap of free parts of the swapfile. This would allow a total of up to 32768 (4096* pages to be in the swap file, if you add a level of indirection this number could be vastly increased.

Another concept (which might be faster) is to have the 4096 32-bit values in the first page of the swap file be offsets to free lists. Each of these could have 4096 32-bit values which are offsets to unused swapfile entries. you replace the value of second level entries with 0 with a page is being used int the swapfile and you replace the first level entries with 0 if all second level entries below it are used.

There are lots of ways to go about it, but I would definitely make that first page part of the accounting since it won't be used for anything anyway.

salil_bhagurkar wrote:Start a task manager in windows, and enable the PF delta (Page fault delta) or the page faults column in the process list. Now simply open notepad or any other application. Even if you select to open a file or even just minimize the application, there are almost a 1000 swaps from the disk (each of 4 kB).

Windows task manager shows soft and hard page faults in this column. But only hard page faults result in disk access. If windows had to read/write that often from the swap file it would be a lot slower.


Storing metadata about the swap file on the disk is not a good idea. Try to reduce disk access as much as possible. Use RAM for the metadata as the disk has already enough to do if it's paging-time. Your algorithms and data structures don't have to be time-efficient (but space-efficient) because the computer is usually no longer CPU-bound when paging is happening.