18 Memory Management – Paging I

Mary Anitha Rajam

 

21.1 Introduction

 

Processes that are currently executed should be kept in the main memory. Processes can be placed as a whole, contiguously, in the main memory. The main memory can be divided into fixed partitions or can be dynamically partitioned. The processes are placed into these partitions in the main memory. While placing processes in the holes present in the main memory, first fit, best fit or worst fit can be used. As processes are brought in and removed, in due course of time, it is possible that a number of small-sized holes are formed which are not contiguous. Since a process has to be kept contiguously in the main memory, each of the small holes is not enough to accommodate the incoming process. This problem is called external fragmentation. But, if the holes are moved to one place and made as one large hole, the process can be accommodated. This process of moving all holes to one place is called compaction.

 

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.

 

In this module, we will learn what paging is, what pages and frames are and how mapping of logical address to physical address is done using paging.

 

21.2. Paging 

 

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. We now see an example of how address translation is done using the paging scheme.

 

Consider a process having four pages (Figure 21.1). The physical memory is also divided into similar sized frames. In Figure 21.1, there are eight frames in the physical memory. Now, the pages of the process are placed in the physical memory. Page 0 is put into frame number 1, page 1 is placed in frame number 4, page 2 is placed in frame number 3 and page 3 is placed in frame number7. To remember where each page is placed in the main memory, a page table is used. Since page 0 is placed in frame 1, a 1 (corresponding to the frame number) is entered in the page table as the first entry. Since page 1 is placed in frame number 4, a 4 is entered as the second entry of the page table. Similarly, the other entries are made in the page table.

Fig. 21.1 Example of paging mechanism (Source: [1])

 

When a page is to be placed in the physical memory, it is necessary to know which frames in the physical memory are free. For this, a free frame list is maintained in a frame table by the operating system. This frame table gives details about which frames are allocated, which frames are available and how many total frames are there. The frame table has one entry for each physical page frame. Each entry gives details on whether the frame is free or allocated, if allocated, to which page of which process. Figure 21.2 shows a free-frame list with frames 14, 13, 18, 20 and 15 as free frames. Frames 16, 17, 19 and 21 are already filled with pages of some other processes. A new process with four pages (page 0, 1, 2, 3) arrives. From the free-frame list, the operating system knows that frame 14 is free and places page 0 in frame 14

Fig. 21.2 Maintenance of free frames (Source: [1]) and updates the page table accordingly.

 

Similarly, the other pages of the process are also placed and the page table is updated.

 

21.2.1  Paging – Example 

 

We now see an example of how frames are allocated for processes when many processes are allocated and de-allocated space in the main memory. We also need to note that each process is assigned a different page table. The page table of a particular process has the frame numbers where the pages of that process are stored.

 

We know that, a process has to be kept in main memory while it is using the CPU. When the process is not using the CPU, the frames allocated to that process can be freed and some other process can be assigned the freed frames. Consider the example shown in Figure 21.3. Process A has three pages (pages 0, 1 and 2).

Fig. 21.3 Process A to be assigned space in main memory

 

The pages 0, 1 and 2 of process A are placed in frames 0, 1 and 2 respectively in the physical memory and the page table of process A is updated accordingly (Figure 21.4).

Fig. 21.4 Process A placed in main memory

 

Another process, process B has to be placed in main memory (Figure 21.5). Process B has four pages (page 0,1, 2 and 3).

Fig. 21.5 Process B to be assigned space in main memory

 

The four pages of process B, page 0, 1, 2 and 3 are placed in frames 3, 4, 5 and 6 respectively in the main memory (Figure 21.6). The page table of process B is also updated accordingly.

Fig. 21.6 Process B placed in memory

 

Let another process C arrive and process C has to be placed in main memory (Figure 21.7). Process C has two pages (page 0 and1). These pages are placed in frames 7 and 8 respectively in the main memory and the page table for process C is updated accordingly.

Fig. 21.7 Process C placed in main memory

 

Let process A now be removed from the main memory (Figure 21.8). The frames 0, 1 and 2 allocated to process A are freed. The page table of process A is also freed.

Fig. 21.8 Process A removed from main memory

 

Let another process, process D arrive (Figure 21.9). Process D has four pages, page 0, 1, 2 and 3. These pages are placed in frames 0, 1, 2 and 9 respectively and the page table of process D is updated accordingly.

 

Thus, we see that processes are divided into pages and the pages are placed in free frames in the main memory. The details of the frames where the pages are placed are maintained in the page tables of the respective processes.

Fig. 21.9 Process D placed in main memory

 

21.2.2  Address Translation Scheme

 

We now learn how the logical address generated by the CPU is converted to the corresponding physical address when paging is used as the memory management scheme.

 

The logical address generated by the CPU is divided into two parts, a page number and an offset.

 

–  Page number (p) – used as an index into the page table which contains the frame number. From the frame number, the base address of the page in physical memory can be found.

–  Page offset (d) – combined with the base address got from the page table to define the physical memory address that is sent to the memory unit.

 

Figure 21.10 shows the address translation architecture. The logical address generated by the CPU is divided into a page number p and an offset d. The page number is used as an index into the page table to get the frame number f. This frame number is combined with the offset d to get the physical address.

Fig. 21.10 Address Translation Architecture

 

Let us now see an example of how address translation is done (Figure 21.11). The process has four pages as shown in the figure. The size of each of the pages is 4 bytes. The size of each of the frames is the same as the size of each page (4 bytes). The four pages are placed in different frames in the main memory. The page table entries are also shown. There are four entries in the page table, corresponding to the number of pages in the process. The first page of the process (logical addresses from 0 to 3) is placed in the frame starting from address 20.  This is the sixth frame. Since the frame numbers start from 0, the frame number corresponding to the sixth frame is 5 and 5 is entered in the page table, corresponding to the first page of the process.

 

The size of the page in this example is 4 bytes. 4 = 22. 2 bits are needed to address one of the 4 bytes within a page. Therefore, 2 bits are used for the offset. If the logical address is a 4 bit address, 2 bits are used for the offset and the remaining 2 bits are used for the page number.

Fig. 21.11 Address translation – example

 

Consider the logical address 1 (corresponding to ‘b’).

1 can be written in binary as 0001.

p        off

00     01

 

Here, 01 is the offset and 00 is the page number. Now, let us see how the address translation is done. The page number is used as an index into the page table. When the page number 00 is used as an index into the page table, it corresponds to the first entry in the page table. The frame number is taken from the first entry. The frame number is 5. Since the size of each frame is 4 bytes, we multiply the frame number with the size of the frame to get the starting address of the frame (5 x 4 = 20). This address is now added with the offset to get the physical address (20 + 01 = 21). We see that ‘b’ is kept in physical address 21.

 

Let us take another example. Consider logical address 10. This corresponds to ‘k’. When written in binary, the logical address is 1010. Since 2 bits are used for the page number and 2 bits for the offset, 10 is used as the page number and 10 as the offset. The page number 10 (2 in decimal) is used as an index into the page table to get the frame number 1. The starting address of the frame is got as 1 x 4 = 4. This starting address is added to the offset 10 (decimal number 2) to get 4 + 2 = 6. The character in the physical address 6 is ‘k’. Thus the address translation is done.

 

Numeric problem:Consider a logical-address space of eight pages of 1,024 words each mapped onto a physical memory of 32 frames.

 

a. How many bits are in the logical address?

b. How many bits are in the physical address?

 

The size of the page = 1,024 words = 210.

 

Therefore, the number of bits in the logical address = 3 (for page number) + 10 (for offset) = 13 bits Therefore, the number bits needed for the offset = 10 To address one of the 8 (23) pages, 3 bits are needed.

 

To address one of the 32 (25) frames, 5 bits are needed

Therefore, the number of bits in the physical address = 5 + 10 = 15 bits

 

21.2.3 Fragmentation 

 

There is no external fragmentation in paging. But, internal fragmentation is possible, if the size of a process is not a multiple of the page size. That is, the last page of the process will not occupy the entire frame in the physical memory. There will be some space in the last frame that will not be utilized and this results in internal fragmentation. For example, if the page size is 2048 bytes and the size of process is 72,766 bytes, the process needs 36 frames – 35 full frames + 1086 bytes. Hence, there is an internal fragmentation of 2048 – 1086 = 962 bytes. The last frame is occupied by only 1086 bytes and the remaining 962 bytes are not utilized.

 

Suppose that the size of a frame is n bytes. In the worst case, due to internal fragmentation, only one byte in the frame may be occupied. The remaining n-1 bytes’ space gets wasted. It is found that, on the average, one-half page gets wasted per process. How to avoid internal fragmentation? Small page sizes are desirable. When smaller page sizes are used, less space gets wasted due to internal fragmentation. Bu the disadvantage is that the number of pages gets increased and hence, the number of entries in the page-table also gets increased. When the pages are smaller in size, the amount of data transferred between the disk and the main memory is less, but, disk I/O is more efficient when the amount of data being transferred is larger. Large page sizes are used these days. Even, on-the-fly page-size support has also been proposed.

 

21.3  Summary 

 

In this module, we learnt that processes are divided into equal-sized pages and the main memory is divided into similar sized frames. Information about free frames are maintained in a free frame list. The information about the frames where the pages are placed is maintained in a page table. The translation from the logical address to the physical address is done using the page table. Paging suffers from internal fragmentation.

 

References

 

1. Abraham Silberschatz, Peter B. Galvin, Greg Gagne, “Operating System Concepts”, Ninth Edition, John Wiley & Sons Inc., 2012.

  1. Charles Crowley, “Operating Systems: A Design-Oriented Approach”, Irwin Professional Publishing, 1996.