Let’s Build an Own Operating System (PrimitiveOS)

Part 8- Page Frame Allocation

Welcome Back!

This is my journey through making a new Operating System named PrimitiveOS.This is the 8th article of the article series and after reading this you can get a proper idea about page frame allocation in an OS.

Before entering this Please read previous parts if you haven’t already done so. In the last article, I had written about paging in an OS.

Let’s Build an Own Operating System (PrimitiveOS)

About the topic

Demand paging is used to implement virtual memory, which is an important element of operating systems. The creation of a page-replacement method and a frame allocation mechanism is required for demand paging. If you have several processes, frame allocation methods are utilized to determine how many frames to assign to each process.

There are various constraints to the strategies for the allocation of frames:

• You cannot allocate more than the total number of available frames.
• Each process should be given at least a certain amount of frames. There are two reasons for this restriction. The first reason is that when the number of frames allocated decreases, the page fault ratio rises, lowering the process’ execution speed. Second, there should be enough frames to contain all of the numerous pages that might be referenced by any single instruction.

Frame allocation algorithms –
The two algorithms commonly used to allocate frames to a process are:

1. Equal allocation: Each process in a system with x frames and y processes gets the same amount of frames, i.e. x/y. Each process will receive 5 frames if the system contains 48 frames and 9 processes. The three frames that aren’t assigned to any process might be utilized as a buffer pool for free frames.

• Disadvantage: In frameworks with forms of shifting sizes, it does not make much sense to deliver each handle rise to outlines. Assignment of an expansive number of outlines to a little handle will inevitably lead to the wastage of an expansive number of designated unused outlines.

1. Proportional allocation: Frames are allocated to each process according to the process size.
   For a process pi of size si, the number of allocated frames is ai = (si/S)*m, where S is the sum of the sizes of all the processes and m is the number of frames in the system. For instance, in a system with 62 frames, if there is a process of 10KB and another process of 127KB, then the first process will be allocated (10/137)*62 = 4 frames and the other process will get (127/137)*62 = 57 frames.

• Advantage: All the processes share the available frames according to their needs, rather than equally.

Global vs Local Allocation –
The number of frames allocated to a process can also dynamically change depending on whether you have used global replacement or local replacement for replacing pages in case of a page fault.

1. Local replacement: When a process needs a page that is not in the memory, it can bring in the new page and allocate it a frame from its own set of allocated frames only.

• Advantage: The pages in memory for a particular process and the page fault ratio is affected by the paging behavior of only that process.
• Disadvantage: A low priority process may hinder a high priority process by not making its frames available to the high priority process.

1. Global replacement: When a process needs a page that is not in the memory, it can bring in the new page and allocate it a frame from the set of all frames, even if that frame is currently allocated to some other process; that is, one process can take a frame from another.

• Advantage: This does not hinder the performance of processes and hence results in greater system throughput.
• Disadvantage: The page fault ratio of a process can not be solely controlled by the process itself. The pages in memory for a process depend on the paging behavior of other processes as well.

ENTRY(loader)  /* the name of the entry symbol */

    . = 0xC0100000 /* the code should be relocated to 3 GB + 1 MB */

    /* these labels get exported to the code files */
    kernel_virtual_start = .;
    kernel_physical_start = . - 0xC0000000;

    /* align at 4 KB and load at 1 MB */
    .text ALIGN (0x1000) : AT(ADDR(.text)-0xC0000000)
    {
        *(.text)    /* all text sections from all files */
    }

    /* align at 4 KB and load at 1 MB + . */
    .rodata ALIGN (0x1000) : AT(ADDR(.rodata)-0xC0000000)
    {
        *(.rodata*) /* all read-only data sections from all files */
    }

    /* align at 4 KB and load at 1 MB + . */
    .data ALIGN (0x1000) : AT(ADDR(.data)-0xC0000000)
    {
        *(.data)            /* all data sections from all files */
    }

    /* align at 4 KB and load at 1 MB + . */
    .bss ALIGN (0x1000) : AT(ADDR(.bss)-0xC0000000)
    {
        *(COMMON)           /* all COMMON sections from all files */
        *(.bss)             /* all bss sections from all files */
    }

    kernel_virtual_end = .;
    kernel_physical_end = . - 0xC0000000;

These labels (kernel_virtual_end , kernel_physical_end) can directly be read from assembly code and pushed on the stack to make them available to C code. (We have done something very similar to this when we were creating functions with arguments.) You can do this as follows.

extern kernel_virtual_start
    extern kernel_virtual_end
    extern kernel_physical_start
    extern kernel_physical_end

    ; ...

    push kernel_physical_end
    push kernel_physical_start
    push kernel_virtual_end
    push kernel_virtual_start

    call kmain

As I mentioned before in this way we can get the labels as arguments to kmain. If you want to use C instead of assembly code, we can do that by declare the labels as functions and take the addresses of these functions:

void kernel_virtual_start(void); /*the function*/

    /* ... */

    unsigned int vaddr = (unsigned int) &kernel_virtual_start;
    /*Taking the address to a variable*/

Since we are using GRUB modules we need to make sure the memory they use is marked as reserved as well. ( Hope you remember that in a earlier stage we created a simple program to push a number to EAX register using modules.)

Remember that the available memory does not need to be contiguous. But it’s convenient to divide the memory sections into complete page frames, because we can’t map part of pages into memory.

How Can We Access a Page Frame?

How do we know which page frames are in use? The most important functions you’ll have to write is the page frame allocator. The page frame allocator will keep track of which are free and which aren’t. There are several ways to do this: bitmaps, linked lists, trees, the Buddy System (used by Linux) etc.

Bitmaps are quite easy to implement. One bit is used for each page frame and one (or more) page frames are dedicated to store the bitmap.

Bitmap

A large array of N/8 bytes is used as a large bit map of the memory usage (that is, bit #i in byte #n define the status of page #n*8+i). Setting the state of a given page is fast (O(1)), allocating a page may take time (O(N)).

• an uint32_t comparison can test up to 32 bits at once and thus speed up allocations
• keeping a pointer to the last allocated bit may improve the performance of the next search (keeping information about the fact all the previous bytes were searched unsuccessfully)

After the execution the page frame allocator returns the physical start address of a free page frame. That means this page frame is not mapped in or no page table points to this page frame.

So, how can we read and write data to the frame?

At first, we need to map this page frame into virtual memory, by updating the Page Directory Table and/or Page Table used by the kernel.

When all accessible page tables are full, however, there will be a conflict. We can’t map the page frame into memory in this case because we’d need a new page table that takes up a whole page frame, and we’d have to map the page frame to write to it. This circular reliance must be broken in some way.

One option is to set aside a portion of the kernel’s first page table (or another higher-half page table) for temporarily mapping page frames so that they are accessible. The kernel contains at least one page table if it is mapped at 0xC0000000 (page directory entry with index 768) and 4 KB page frames are used. We can allocate the last entry (entry 1023) of this page table to temporary mappings if we assume — or limit ourselves to — a kernel with a maximum size of 4 MB minus 4 KB. The virtual address of pages mapped in with the kernel’s PT’s last entry will be:

(768 << 22) | (1023 << 12) | 0x000 = 0xC03FF000

We may add the page frame we wish to use as a page table to the paging directory and remove the temporary mapping after we’ve temporarily mapped it and set it up to map in our initial page frame.

A Kernel Heap

we’ve as it were been able to work with fixed-size information, or straightforwardly with crude memory. Presently that we have a page outline allocator ready to actualize malloc and free to utilize within the bit. A redress execution ought to too return page outlines to the page outline allocator on call to free, at whatever point adequately expansive pieces of memory are liberated.

Thank you for reading. We will meet soon.

#staysafe #stayconnected

Reference: https://littleosbook.github.io/ https:/
http://os.phil-opp.com/

For any issue with making files, you can follow my repository

https://github.com/Sachin-Tharaka/PrimitiveOS