CAOS 11

The purpose of Main Memory Management is to maximize the Degree of Multiprogramming without sacrificing stability. We previously dealt with execution of processes that are WHOLLY in memory. However, much of the process loaded in memory is actually not required at that point.
Recall that in the Segmentation example previously, parts of the program (such as Subroutine, Stack, Symbol Table, Functions, Main Program) are divided into segments to be stored in the memory. However, at any given point, would ALL of those segments be used? Unlikely.

There are wastage of memory space, especially in things like overallocation (integer allocated while only byte is required, 1000 index array allocated while only 5 indexes are actually used).

To allow a process that is larger than the available memory to be executed, we use a technique known as Overlay. Overlay only keeps in memory instructions and data that are needed at that given time. The overlaying method is handled by the Overlay driver. Using overlays would cause a program to load faster (because not all memory needs to be loaded at the same time) but would run slower (because I/O would be required to switch parts in and out).

Overlay is a type of Virtual Memory scheme. Virtual Memory allows execution of processes that may not be completely in memory. This means that programs would no longer be constrained by the amount of RAM and the Degree of Multiprogramming can be increased (Increase CPU utilization and throughput).

Virtual memory separates the user logical view from the actual physical memory. Does this sound familiar? Perhaps from the previous article? Well, yes, Paging and Segmentation supports this Virtual Memory scheme (swapping pages/segments into a secondary storage).

We look at a simple Virtual Memory management scheme known as Demand Paging. Recall that in the previous article I mentioned that the secondary storage is divided into fixed-sized frames, but I didn't talk about what is it used for. The secondary storage is actually used for swapping existing Frames in the physical memory into the backing store (backing store and secondary storage is used interchangeably in this article).

When a process needs to do something, it only swaps in the necessary frames, reducing the RAM needed and the time it takes to load up (faster response time).

Recall that the page table also contains a Valid/Invalid flag for each page. This Valid/Invalid flag can now be used to determine if a Page is already loaded in the physical memory.

From the seminar notes, here are the definitions:
Valid - The associated page is both legal AND in memory
Invalid - The associated page is illegal OR legal but not in memory

(Recall that in the previous example, Valid is just for legal, and Invalid is just for illegal. Also recall that Legal means that the page is in the process's address space.)

Here is how the paging table would look like:

(Taken from Recommended Text)

If a process tries to access an Invalid page, a Page Fault Trap occurs. We will be referring to this diagram for the elaboration:


Now let's go through the steps in sequence.

1) Whenever a logical memory is accessed, it is first checked for the Valid/Invalid bit. If it is Valid, operation continues as per normal.

2) However, if the Page being accessed is Invalid, a Page Fault Trap occurs to notify the OS.

3) The operating system schedules a Disk Read to find the missing frame.

4) A list of free Frames is consulted. If there is a free Frame, the Frame is loaded into the Physical Memory. If there is no free Frame, a Page Replacement occurs. This would be described in the next section.

5) The Paging Table is updated to reflect the Valid bit if the Page is successfully loaded.

Now we'll talk about the Page Replacement process. These are the steps outlined in the seminar:
if (Free Frame Exists)
{
}
else
{
Sacrifice a Frame according to Page Replacement Algorithm;
Write Sacrificed Frame to Backing Store;
Update Sacrificed Page Table to Invalid;
}
Load Desired Frame from Backing Store to Free Frame Location;
Update Desired Page Table to Valid;

The Page Replacement Algorithms are used to select a victim frame. The three algorithms we've learned are:
FIFO - Oldest frame is sacrificed
LRU - Least recently used frame is sacrificed
Optimal - Replace the page that will not be used for the longest period of time.

There exists an anomaly known as Belady's Anomaly where, usually in a FIFO environment, the number of page fault actually increases if the number of frames to work with increases. This disproves the assumption that more Frames equate to better performance. We'll discuss this if we have time.

Now we'll go through some examples on how to apply the algorithms. First of all, we'll define the page reference string:
1, 3, 4, 2, 3, 6, 4, 2, 1, 5, 2, 5, 6, 3, 4, 2, 1, 2, 1, 5

Now, suppose that the process has only 3 frames to work with. We'll now go through FIFO:

1 3 4 2 3 6 4 2 1 5 2 5 6 3 4 2 1 2 1 5

1 1 1 2 2 2 2 2 2 5 5 5 5 3 3 3 1 1 1 1
  3 3 3 3 6 6 6 6 6 2 2 2 2 4 4 4 4 4 5
    4 4 4 4 4 4 1 1 1 1 6 6 6 2 2 2 2 2
F F F F   F     F F F   F F F F F     F

In this case, there are 14 faults.

Now let's go through LRU:

1 3 4 2 3 6 4 2 1 5 2 5 6 3 4 2 1 2 1 5

1 1 1 2 2 2 4 4 4 5 5 5 5 5 4 4 4 4 4 5
  3 3 3 3 3 3 2 2 2 2 2 2 3 3 3 1 1 1 1
    4 4 4 6 6 6 1 1 1 1 6 6 6 2 2 2 2 2
F F F F   F F F F F     F F F F F     F

There are 15 faults when using LRU.

Finally, we'll see how Optimal performs:

1 3 4 2 3 6 4 2 1 5 2 5 6 3 4 2 1 2 1 5

1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
  3 3 3 3 6 6 6 6 6 6 6 6 3 4 4 1 1 1 1
    4 4 4 4 4 4 1 5 5 5 5 5 5 5 5 5 5 5
F F F F   F     F F       F F   F

We have a clear winner of 10 faults in Optimal.

However, in real life, the Optimal Page Replacement algorithm is not easy to implement and a practical solution does not exist for this as it requires future knowledge.