19 Memory Management – Paging II

Mary Anitha Rajam

22.1 Introduction

There are memory management schemes, in which, the process need not be put as a whole into the main memory. The process can be divided or split into parts and each part can be put in different free spaces in the main memory. Paging and segmentation are examples of these memory management schemes.

Paging is a memory management scheme that lets physical address space of a process to be noncontiguous. The process is allocated physical memory space, wherever space is available. In this scheme, the physical memory is divided into fixed-sized blocks called frames or page frames (size is power of 2, between 512 bytes and 8192 bytes). The logical memory is also divided into blocks of the same size called pages.

Since the physical memory is divided into frames, to know which frames are free, it is necessary to keep track of all the free frames. When a process of size n pages is to be placed in the main memory, it is necessary to find n free frames and load the pages of the process into these free frames. These frames where the pages are placed need not be contiguous. So, there arises a necessity to remember in which frames the pages are kept. For this, a page table is maintained. The page table helps in translating the logical addresses that are generated to physical addresses.

In this module we learn the implementation of the page table, how a translation look-aside buffer along with the existing paging architecture to improve performance, how memory protection can be incorporated along with paging and the different structures that can be used for the page tables like hashed page tables and inverted page tables.

22.2. Page Tables 

Each process has its own page table. The process control block of a process has a pointer to that process’s page table. There are different ways in which a page table can be implemented. The different ways are discussed in the following subsections.

22.2.1 Registers 

The page table can be implemented as a set of registers. That is, the entries of the page table are kept in registers. For example, the DEC PDP 11 makes use of registers for storing the page table contents. This architecture uses 16 bit logical addresses and the page size is 8 KB (213). Therefore, 13 bits are needed for the offset and the remaining 3 bits are used for the page number. Therefore, the number of entries in the page table = 23 (= 8) entries. These eight entries are therefore kept in 8 fast registers. This method of implementation of the page table is satisfactory if the page table is small. If the page table is large with many entries, availability of that many registers becomes difficult.

22.2.2 Page table kept in main memory 

In this method, the page table is kept in main memory. The starting address of where the page table is kept in main memory is kept in a register called the page-table base register (PTBR). Whenever a process is given the CPU for execution, the dispatcher loads the PTBR with the starting address of that process’s process table. Whenever there is a context switch, it is enough if the value in the PTBR is changed according to the process selected for execution. Another register is maintained called the Page-table length register (PTLR). This register has the value of the size of the page table.

In this scheme, every data/instruction access requires two memory accesses. Once is to access the page table and the second is to access the data/instruction. When the page table is accessed, the frame number is got and the offset is added to the frame number to get the actual physical address. Using this physical address, the main memory is accessed the second time to get the data/instruction. Thus the memory access time is slowed down by a factor of 2.

22.2.2 Associative Memory 

The two memory access problem can be solved by the use of a special fast-lookup hardware cache called associative memory or translation look-aside buffers (TLBs). Each entry of the cache has two parts – a key (tag) and a value. When presented with an item, it is compared with all the keys simultaneously. The page table can be implemented in this manner. The page number and the corresponding frame number correspond to the key and the value (Figure 22.1). Some of the (page number, frame number) pairs are kept in the associative memory. The given page number is searched in parallel in all the entries in the cache. If the page number is present, the corresponding frame number is taken. Else, the page number is searched in the page table kept in main memory.

Fig.22.1 Associative memory – parallel search

22.3  Paging Hardware With TLB

We now look at how the TLB can be used along with the basic paging mechanism(Figure 22.2). A TLB is maintained which has a few (page number, frame number) pairs. As usual, the logical address is divided into a page number and an offset. The page number is first checked in the TLB. If the page number is present in the TLB, the corresponding frame number is taken. If the frame number is got from the TLB itself, it is called a TLB hit. If the frame number is not present in the TLB, it is called a TLB miss. When there is a TLB miss, the page number is now checked in the page table kept in the main memory and the frame number is got from the page table.

If a page is not found in TLB (TLB miss) and is taken from the page table in the main memory, this (page no, frame no) pair is added to the TLB to use in future references. While bringing this (page no, frame no) pair into the TLB, if the TLB is already full, one of the entries already present in the TLB is selected for replacement. The entry selected for replacement can be the least recently used entry or a random entry.

Fig.22.2 Paging hardware with TLB (Source: [1])

22.3.1 Effective Access Time

The effective memory access time is reduced by using a TLB. We now see how the memory access time is reduced. Let the associative memory lookup time be e time units. Let the time to access the physical memory be 1 microsecond. The hit ratio is defined as the percentage of times that a page number is found in the associative registers. Let the hit ratio = a.

The effective access time (EAT) is calculated as

EAT = (1 + e) a + (2 + e)(1 – a)

= 2 + e – a

That is, when there is a hit, the access time includes the time to look into the associative memory (e) and the time to access the actual data in the main memory (1). When there is a miss, the access time includes the time to look into the associative memory (e) (but not found), the time to look into the page table kept in the main memory (1) and the time to access the actual data in the main memory (1).

Let us now see an example of how effective memory access time is calculated:

Assume it takes 20 nsecs to search TLB and 100 nsecs to access memory, what is the effective memory access time, if the hit ration is 80%?

If the page number is present in the TLB, memory access time = 120 nsecs (20+100)

If  page  number  is  not  present  in  the  TLB,  memory  access  time  =  220  nsecs (20+100+100)

If 80 percent hit ratio, effective memory-access time = 0.80 x 120 + 0.20 x 220 = 140 nsecs.

22.4 Memory Protection 

In this section, we learn how memory protection is implemented by associating protection bits with each frame. Protection bits are kept in the page table for each page. These bits specify whether that page is read-only, read-write or execute-only. Whenever a page is to be accessed, the appropriate access permissions are checked. For example, if the user is trying to write to page that is read-only, a trap is sent to the operating system, indicating that there is a violation in the access.

Another protection mechanism that is added to the page table is the valid-invalid bit. If the valid bit is set for a page, it means that the page is in the logical address space of the process. If the invalid bit is set, then it specifies that the page is not in the logical address space of the process. This can be understood with an example (Figure 22.3). Consider a 14-bit address space. Since it is a 14-bit address space, the logical addresses range from 0 to 214 – 1 (that is 0 to 16383). Let the page size be 2K (211) bytes. The number of pages possible with this 14-bit address space is 214 / 211  = 23 = 8 pages. Suppose a process has addresses from 0 to 10,468. This will occupy five full pages and a part of the sixth page. Therefore, in the page table, out of the 8 entries possible, only the first 6 entries are marked as valid. The last two pages are marked as invalid. So, if an address is generated in the range 12,288 – 16,383, a trap is given to the operating system, indicating that the address generated is an invalid one.

Fig.22.3 Valid(v) or Invalid (i) Bit In A Page Table (Source:[1])

22.4 Page Table Structure

Hashed page tables, inverted page tables and hierarchical paging are some of the techniques for structuring the page table. In this section we learn how inverted page tables and hashed page tables are used.

22.4.1 Hashed Page Tables 

This type of page tables is common in logical address spaces greater than 32 bits. When the logical address space is very large, the sizes of page tables become very large. In this technique, the virtual page number (hash value) is hashed into a page table (Figure 22.4). This page table contains a chain of elements hashing to the same location. Each element has three fields: virtual page number, value of the matched page frame, pointer to the next element in the linked list. The virtual page numbers are compared in this chain searching for a match. If a match is found, the corresponding physical frame is extracted.

Fig. 22.4 Hashed page tables (Source: [1])

22.4.2  Inverted Page Table

Usually, each process has a page table associated with it and the page table has an entry for each page of the process. But, the drawback is that each page table may have a number of entries and may consume large amounts of physical memory. A solution to this is to use an inverted page table. In an inverted page table, there is only one page table common to all processes. There is one entry for each real physical page (frame) of memory. Each entry in this page table consists of the virtual address of the page stored in that real memory frame with information about the process that owns that page. Figure 22.5 shows how an inverted page table is used. The page number in the logical address is used along with the process id of the process to search in the inverted page table. When a match is found, the corresponding frame number is taken. This decreases the memory needed to store each process’s page table, but increases time needed to search the table when a page reference occurs. It may be needed to search the entire table. A table may be used to limit the search to one — or at most a few — page-table entries.

Fig. 22.5 Inverted page table (Source: [1])

22.5. Summary

This module discussed where page tables can be kept. Page tables can be kept in registers, memory or in TLB. There are different structures for the implementation of page tables. This module discussed the implementation of hashed page tables and inverted page tables.

References

1. Abraham Silberschatz, Peter B. Galvin, Greg Gagne, “Operating System Concepts”, Ninth Edition, John Wiley & Sons Inc., 2012.
2. Charles Crowley, “Operating Systems: A Design-Oriented Approach”, Irwin Professional Publishing, 1996.