Disjoint Memory Schemes

Recall the 2 assumptions we have made - each process occupies a contiguous memory region and the physical memory is large enough to contain one or more processes with complete memory space. Now, we will look at what happens when we remove the first assumption. What can we do if the process do not have to be contiguous?

Pagning Scheme

The basic idea is that physical memory is split into regions of fixed size (decided by hardware) known as physical frame. The logcal memory of a process is similarly split into regions of same size known as logical page. At execution time, the pages of a process are loaded into any availalble memory frame. Logical memory space remains contiguous while the occupied physical memory region can be disjoined.

Lookup Mechanism

In contiguous memory allocation, it is very simple to keep track of the usage of a process. Minimally, we only need the starting address and size of process. Under the paging scheme, we need some mapping between the logical and physical address. The logical page and physical frame mapping is no longer straightforward. To help with this, we need a lookup table to provide the translation, known as the page table.

Note that pages refer to logical and frame is physical.

Illustration

Here, we have out physical memory divided into the same size frames. We have our logical process that turns up and has 4 pages. They can go anywhere in memory in any order. Each page is the same size as the frame. The page table will contain the frame number where the page is located.

If a logical address comes out of page 2, how do we know the physical address? The address is broken up logically into 2 parts. 1 is the offset within the page and the other is the number of the page. This is mapped to the offset and physical frame number.

Since both page and frame are same sized, the offset would be the same. So we only worry about translating the page number to frame number to get the memory address. So, the physical address is just the frame number * size of physical frame + offset.

Logical Address Translation

There are some design decisions we have to make. - Keep frame size (and page size) as a power of 2. - Physical frame size == Logical page size

We are taking a logical address and interpreting it as 2 parts - 1 for offset and 1 for page number. The offset is the same as that of the physical address, so we look at what is the translation mechanism (using the page table) to get the number of the frame.

So, given a page/frame of size \(2^n\) with m bits of logical address (LA),

• p = Most significant m - n bits of LA
• d = Remaining n bits of LA (for the offset)
• Use p (page number) to find frame number f with mapping mechanism like page table
• Calculate physical address (PA) with \(PA = f*2^n + d\)

Example

Here, we have 4 logical prages and 8 physical frames. The size of each page is 4 bytes (so frame also 4 bytes). We need 2-bit addresses for the logical page and offset, so the size of logical address is 4 bits. This corresponds to 16 bytes address. Here we are interpreting logical address as page number and offset.

Here, there isn't external fragmentation. Since they are all about the same size, there isn't much gaps being formed. Internal fragmentation can happen, but only for the last frame. All other frames would be full. The clear separation of logical and physical address space also allows for greater flexibility and simple address translation.

Implementation

A common pure-software solution is to have the OS store the page table information in the PCB (not necessarily entire table, but a pointer to it). We need to store this so we can do the lookup, which we need to do for every logical address. So this is part of the memory context of a process. Each process needs their own page table to convert their own logical address (which can both start at 0).

Since it is part of the memory context, we require 2 memory access for every memory reference - 1 for the page table and the other for the actual byte we want. This can be inefficient so we can make use of caching.

Hardware Support

Modern processors provide Translation Look-Aside Buffer (TBL) which acts as a cache of a few page table entries, essentially a fast hardware lookup. Recall that whenever we have a lookup in a cache, we can have a hit or miss. Similarly when we use the page number to search TLB associatively, we can have entry found/not found.

• TLB-Hit: Frame number is retrieved to generate phyiscal address
• TLB-Miss: Memory access to full page table where the retrieved frame number is used to generate physical address and update TLB.

From the diagram, we take the page number p, do a lookup on the page table to get frame number f and at the same time, store it in the TLB.

Since this page number refers to the currently running process, when we do a context switch, we have to empty the cache (TLB entries are flushed) and bring in the next process' TLB, so that new processes will not get incorrect translation. Hence, when a process resumes running, we will encounter many TLB misses to fill the TLB (it is till possible to place some entries initially).

If the TLB keeps getting cleaned out, it can cause problems. Adding the PID can help identify processes (like OS) to state that for such processes, don't clean the TLB for e.g. the kernel. This lets up keep more elements for faster lookup.

So now, this belongs to the hardware context of the process.

Impact on memory access time

Suppose TLB access takes 1ns and main memory access takes 50ns, what is th eaverage memroy access time if TLB contains 40% of the whole page table (i.e. TLB hit 40%)

Memory access time = TLB hit + TLB miss = 40% x (1ns + 50ns) + 60% x (1ns + 50ns + 50ns) = 81ns

We have two 50ns due to access to the page table as well.

Protection

To provide memory protection, we have access-right bits and valid bit. In the contiguous memory allocation, we had protection in terms of size (base and limit). For paging, we can use access right bits - each page table entry has { w ritable, r eadable, e x ecutable} bits to check what are the access rights of the pages we are accessing in memory.

Recall that logical memory range is usually the same for all processes, but not all process utilize the whole range. Some pages are out-of-range for a particular process. Using the valid bit, if the address is more than size of process, even if it is a valid logical address, it is not valid for the particular process since it is not using that address.

So valid bit indicates whether a page is valid to access and OS will set the valid bits when a process is running. Mmeory access is checked against this bit and out-of-range access will be caught by the OS.

Page Sharing

Page table can allow several processes to share the same physical memory frame by using the same physical frame number in the page table entries (could have same lookup).

Some possible usage include having shared code page - some code (e.g. C standard library, system calls) are used by many processes, rather than having a copy each, just use a shared one. This is also how we can implement copy-on-write. Parent and child process can share a page until one tries to change a value in it, allowing us to keep the code the same until needed.

Illustration

All pageWith sharingCopy Necessary

Witout page sharing/copying all pages, we can fit the pages into 1 frame each

With sharing, we can map the page table differently differently

If we only copy the necessary pages, we can end up with 1 page in a different location and other pages map to an existing page

Segmentation Scheme

The memory space of a process is treated as a single entity so far. But internally, we know that the processes have slightly differrent type of space. Internally, memory regions have different usage in a process. The text, data heap and stack can be thought of as different parts of the process (different segments) The nice thing is independently, these segments can grow and shrink and be managed differently.

So we separate the regions into multiple memory segments (where logical memory space of a process is now a collection of segments). Each segment has a name and a limit (since it grows and shrinks and segments are not the same size). All memory reference is now specified as Segment name + offset

Logical Address Translation

But since the name is conceptual, how do we actually get the starting address?

To lookup a table and get information about a segment, we need to know what is the base and limit. We then lookup the thing with base + offset.

Each segment is mapped to a contiguous physical memory region (with a base address and limit), and the segmentation name is usually represented as a single number, aka segment id. This id acts as an index to the segment table.

The logical address is <SegID, Offsest> where SegID is used to look up <Base, Limit>of the segment in a segment table. The physical address PA is base + offset where offset < limit for all valid access.

Illustration

2 matches with index 2 which has a bse of 2400. The actual address is 2400 + 500 = 2900.

Hardware Support

So the CPU generates the segment ID and address, look up on the segment table, check if address is within the limit and if it is, add the offset and get the actual address. Else, get an addressing error (segmentation fault)

Summary

So each segment is an independent contiguous memory space where each can grow/shrink and be protected/shared independently. However, due to requiring a variable-size contiguous memory region, this can cause external fragmentation.

Also, it is important to note that segmentation and paging are not the same - they are trying to solve slightly different problems.

Segmentation with Paging

When you think of a segment, it is different parts of a process. With paging, it is because it is difficult to manage processes with multiple pages so we take a process and split it into pages. So, why not take a segment and break it into multiple pages?

The idea is we take a segment and page them (somewhat think of them as individual processes). So each segment has its own page table and the lookup now is in 2 steps - first for segment ID and second for segment page table.

Now, the CPU generates an address that is calculated slightly differently. We have the segment id and offset, but within the segment now there is also the page number. The lookup on the segment table now gives us the page table address (instead of offset) to get the frame number. After checking if the page is valid, we do a lookup on the page table for the physical frame (frame number, where we can then retrieve the address), else addressing error.

So, now the process is divided into segments which are further divided into pages. The lookup is using segment Id, from which we get the frame number and finally the actual physical address.