Swap space management during pure demand paging

Question

The following is a doubt that I came across while doing a OS home assignment - however, it seems more concept-based than a straightforward coding question, so IMHO I don't think the homework tag is appropriate for this.

In a pure demand paging scheme for multiple processes running at the same time, given a fixed amount of RAM and Swap memory, what happens in the following 2 cases w.r.t the swap space, when

1. A process encounters a page-fault, and there are no free frames available in the RAM, hence requiring one of the pages from the process' chunk of Kernel Frames to be written out to swap (for simplicity, I'm not considering the copy-on-write case). Explicitly, where in the Swap space would this frame be written, and what data structures need to be updated for that?

2. When a process needs to page-in a particular page, where does it look in the Swap memory, and how would it know if that particular page be present in Swap at all ?

As you can well imagine, I'm having difficulty understanding in what way to manage the Swap space during pure demand management scheme, and what data structures would be essential. It would be great if you could refer to any links in your answer (I searched in "Operating System Concepts - 8th edition by Silberschatz, I couldn't find an explicit answer for my question).

Answer 1

To answer this question I will visit some prerequisite understanding. Pure demand paging cannot be accomplished without hardware support. All modern computer architectures support paging, however many have different implementation details.

x86 processors use what is called a page table to keep track of virtual address spaces and page mappings, as well as bits about access privilages and, more relevant, whether or not that page is even present in physical memory. Violations trigger page faults which are trapped by the OS.

For more information on that, see this article.

In order to answer the question of page swapping, we must first visit the question of how the operating system keeps track of what pages are used by what process and how they are allocated. There are many different data structures that can be used for such. A flat bit array marking whether a frame is allocated or not is one way. Linked lists or stacks is another. With pure demand paging, allocated pages are not actually marked as present when they are allocated. This has the effect that no physical ram is set aside for a process until it actually writes to it. Once it does, the hardware throws a fault which the OS traps, and then the OS uses a swapping algorithm if there are no available physical pages to assign to the already allocated virtual page.

For more information on page frame allocation, see here. There you will see a general overview of some suitable datastructures.

Once a suitable algorithm for page allocation is implemented, another for allocating disk space for swapping must be chosen. Windows, as an example, has historically used a flat file in the filesystem for page swapping. I would imagine that for each node in the datastructure keeping track of allocated pages there is an assocated pointer to an offset in the file, indicating the position of the page in the disk. Unix-like operating systems have traditionally used separate partitions for page swapping which is arguably faster since there is no filesystem layer.

It is also possible to divorce the swapping algorithm datastructures from those of the allocation algorithm, however the two are related so this is probably not often done.

I hope that answers your question despite the relative brevity with which I have treated it. I found that the best way to learn about operating systems is to dive into the sometimes nasty architectural specific details that can be found in sites like wiki.osdev.org and www.osdever.net which specifically deal with hobby OS making and provide excellent tutorials on such details.