Paging – Memory Management

Paging – Memory Management

Paging is the memory management scheme in which the physical memory allocated to a process is non contiguous.
In this approach, physical memory is divided into fixed size blocks called frames and the logical memory is divided into fixed size blocks called pages.
The size of a page is same as that of a frame.

Page Size = Frame Size

Whenever a process is to be executed, its pages are placed or loaded into any available memory frames. It means a page is mapped into a frame.
Individual pages and frames are recognized by unique numbers as page number and frame number respectively.
Thus, a page number forms a part of logical address and a frame number forms a part of a physical address.

A logical address (i.e. address generated by CPU) consists of two parts : a page number (p) and a page offset (d). A page offset is the displacement within page p at which the referenced item is located.

A physical address (i.e. address of physical memory) also consists two parts: frame number (f) and frame offset (d).

Mapping of pages to frames or address Translations

The mapping of logical address to physical address is provided by using a page table contained by special hardware called memory management unit. The method of converting a logical address into its corresponding physical address is know as address translation.
The page table has one entry for each page of the process and indicates the status of each page.
Each entry of page table is used to specify whether the page has been allocated some space in physical memory or not.

If space is allocated to page then it specifies in which frame it is present.
After the frame number fetched from page table, combined with page offset to define the physical address.
The page size or frame size defined by hardware and always a power of 2.
The page size and frame size is always a power of 2 because this makes the division of a logical address into page number and page offset easy.
If the size of logical address space is 2″^m and a page size is 2^n, then the high-order m-n bits of logical address denote the page number and the n low order bits denote the page offset.

For example, if the logical address space can hold 2^13 address. It means a logical address is 13 bit long. We can say that the logical address space is 2^13 = 8KB.
If there are 8 pages in logical address. It means size of each page is 2^10=1KB
Now, in a logical address of 13 bits, the higher (13-10) = 3 bits denote the page number and rest 10 bits denote the offset.

If the physical address space is 2^12 = 4KB.

It means the physical address is 12 bits long.

Frame size is also 2^10 = 1KB. There will be 4 frames.

In this way in a physical address of 12 bits higher (12-10) = 2 bits specify frame number and remaining 10 bits specify the offset. Thus a logical address 0111010101010 denotes page number is 011 (3 high orders bits) and offset is 1010101010.

The physical address corresponding to this logical address is 011010101010, where 001 is the frame number and 1010101010 is offset. As pages and frames have same size, offsets within each are identical and need not be mapped.

Example for 32-byte memory with 4-byte pages :

32 bytes = 2^5, therefore we have a 5 bit logical address

4 bytes = 2^3, the lower 2 bits are the offset

13 = 01101 in binary
01 in binary, 1 in decimal = offset
011 in binary, 3 in decimal = page no.
physical address equals = page frame * page size + offset
2*4+1 = 9

Implementation of Page Table

The hardware implementation of the page table can be done in several ways:

1. Using Registers

In the simplest case, the page table can implemented as a set of dedicated registers. These registers built with very high-speed logic that effectively translate logical address into physical address. These registers loaded by CPU dispatcher, just as it reloads the other registers. The use of registers for implementing page table done only when page table is small i.e. when the number of entries in hundreds. However when the number of entries required in page table is large (i.e. in millions), the use of registers is not feasible.

2. Using page-table base registers (PTBR)

This method used when page table contains million of entries. In this approach, the page table kept in the main memory and register called page-table base register used to point to page table in memory. Thus, changing the page table requires changing only PTBR and this reduces the context switch time. When this scheme implemented, duration of access time increased i.e. memory access slowed by a factor of 2. This is because, we need two memory access to access the required word, one for the page table and one for the word itself.

3. Using associative memory or translation look-aside buffer

In order to overcome the problem of longer duration of access time, we can use high- speed associative memory.
This small, fast look-up or high-speed hardware also known as translation look-aside buffer.
This TLB contains a few entries of the page-table. Each entry consists of a pair; page number, frame number.
When a logical address generated by the CPU, its page number used to address that location of TLB that contains the corresponding frame number.
If the page number found in TLB, its frame number immediately available, and used to access memory.
When the page number not present in the TLB, known as TLB miss. In such a case, the page table accessed in order to obtain the frame number of that page number. In addition, the page number and its corresponding frame number added as a new entry in TLB, so that it can found quickly on next reference. If the TLB is already full of entries, the operating system replaces some entry in TLB.
If the page number present in the TLB, known as TLB hit. In such a case, the frame number picked up from the TLB to generate physical address.
The percentage of times that a particular page number found in the TLB, called the hit ratio.

An 80 percent of hit ratio means that we find the desired page number in the TLB 80 percent of the time. If it takes 20 nanosecond to search the TLB, and 100 nanoseconds to access the memory, then a mapped-memory access takes 120 nanoseconds when the page number is in the TLB.
If the page in number is not in TLB (i.e. TLB miss), it consumes 20 nanoseconds. In this case, we must access memory for page table and find the frame number, it takes 100 nanoseconds. Now to access the desired byte in memory, another 100 nanoseconds consumed. Thus total of 220 nanoseconds, if there is TLB miss.
Thus, we can find effective memory access time by weighing each case by its probability.

Hit ratio is 80%

In case of TLB hit, time consumed = 120 nanoseconds

In case of TLB miss, time consumed = 220 nanoseconds

Effective access time = 0.80 x 120 + 0.20 x 220

= 140 nanoseconds

This example suffers a 40% slowdown in memory access time (from 100 to 140 nanoseconds).

If hit ratio is 98%

Then, effective access time = 0.98×120 + 0.02 x 220

= 122 nanoseconds

Now, there is only a 22% slowdown in memory access time. Thus, with the increase in hit ratio, slowdown in access time decreases.

Memory Protection in paging

In order to provide memory protection in paging, we can use various protection bits for each frame in the memory.
These bits kept in the page table for each entry of page and its corresponding frame.
In order to indicate whether the page read only or read-write, we can use a bit in page table to specify it. Whenever page table accessed to find a frame (during computation of physical address). This protection bit checked to ensure that no writes made to read only page. If an attempt made to write to a read-only page, hardware trap sent to the operating system.

There can also one more bit in page table called valid/invalid bit to determine an invalid program generated address.
When this bit set to “valid“, it indicates that the associated page present in the process’ logical-address space and thus a legal or valid page.
If the bit set to “invalid“, it indicates that the page not present in the process logical- address space.
For example, consider a system with 14-bit address space i.e. these addresses may vary from 0 to 16,383. We may have a program that should use only addresses from 0 to 10468.
If the page size is 2KB, we get a situation as shown in fig. 7.28 Address in page 0, 1, 2, 3. 4 and 5 mapped through page table.
If an attempt made to generate an address in pages 6 or 7, a trap sent to operating system as valid/invalid bit for these entries set to invalid.

Sharing in paging

When paging is implemented; we can share the common program code i.e. the pages containing common code can shared by number of processes. For a code to be shared, it is important that it should be reentrant. A reentrant code also known as pure code. Such a code is non-self modifying.

Thus, a reentrant code does not change during the execution of a program. As a result it can be shared. Two or more processes can execute the same code at the same time. In such a case, each process has its own copy of registers and data storage to hold the data for the process’ execution. Examples of the programs that can be shared are compilers, editors, database system, run-time libraries etc.

Advantages of Paging

It does not suffer from external fragmentation.
Paging achieves a higher degree of multiprogramming as compared to contiguous storage allocation methods.
It also allows the sharing of common code among the processes.

Disadvantages of Paging

The page address mapping hardware usually increases the cost of the computer and at the same time slows down the processor.
Page map table needs to stored in the memory. Moreover processor time must spent to maintain and update these tables. This incurs overhead.
Although there is no external fragmentation but paging suffers from internal fragmentation.
Some memory will still unused if the number of available blocks not sufficient for the address spaces of the jobs to run. For example, if two blocks totaling 8K bytes are available, they cannot use if the minimum job size to be run is over 8K bytes.
A jobs’s address space limited to the size of physical memory.