Paging in OS

Paging is a method of gaining access to data more quickly. When a program requires a page, it is available in the main memory because the OS copies a set number of pages from the storage device into the main memory. Paging permits a process’s physical address space to be noncontiguous. Paging refers to a memory management strategy that does away with the need for the allocation of contiguous physical memory.

In this article, we will look more into the Paging in OS according to the GATE Syllabus for (Computer Science Engineering) CSE. Let us read ahead to find out more about it.

Table of Contents

• What is Paging in the OS?
• Memory Management Unit
• Practice Problems on Paging in OS
• Frequently Asked Questions on Paging in OS

What is Paging in the OS?

Paging is a storage mechanism used in OS to retrieve processes from secondary storage to the main memory as pages. The primary concept behind paging is to break each process into individual pages. Thus the primary memory would also be separated into frames.

One page of the process must be saved in one of the given memory frames. These pages can be stored in various memory locations, but finding contiguous frames/holes is always the main goal. Process pages are usually only brought into the main memory when they are needed; else, they are stored in the secondary storage.

The frame sizes may vary depending on the OS. Each frame must be of the same size. Since the pages present in paging are mapped on to the frames, the page size should be similar to the frame size.

Example

Assuming that the main memory is 16 KB and the frame size is 1 KB, the main memory will be partitioned into a collection of 16 1 KB frames. P1, P2, P3, and P4 are the four processes in the system, each of which is 4 KB in size. Each process is separated into 1 KB pages, allowing one page to be saved in a single frame.

Because all of the frames are initially empty, the pages of the processes will be stored in a continuous manner. The graphic below depicts frames, pages, and the mapping between them.

Consider the case when P2 and P4 are shifted to the waiting state after a period of time. Eight frames are now empty, allowing other pages to be loaded in their stead. Inside the ready queue is the process P5, which is 8 KB (8 pages) in size.

Given that we have 8 noncontiguous frames accessible in memory, paging allows us to store the process in many locations. As a result, we can load the process P5 page instead of P2 and P4.

Memory Management Unit

The Memory Management Unit (MMU) is responsible for converting logical addresses to physical addresses. The physical address refers to the actual address of a frame in which each page will be stored, whereas the logical address refers to the address that is generated by the CPU for each page.

When the CPU accesses a page using its logical address, the OS must first collect the physical address in order to access that page physically. There are two elements to the logical address:

• Page number
• Offset

The OS’s memory management unit must convert the page numbers to the frame numbers.

Examples

Let’s say the CPU requests the 10th word of the 4th page of process P3 in the image above. Because page number 4 of process P1 is stored at frame number 9, the physical address will be returned as the 10th word of the 9th frame.

Let’s consider another example:

• If the physical address is 12 bits, then the physical address space would be 4 K words
• If the logical address is 13 bits, then the logical address space would be 8 K words
• If the page size is equal to the frame size, which is equal to 1 K words (assumption),

Then:

The address generated by the CPU is divided into the following:

• Page offset(d): It refers to the number of bits necessary to represent a certain word on a page, page size in Logical Address Space, or page word number or page offset.
• Page number(p): It is the number of bits needed to represent the pages in the Logical Address Space or the page number.

The Physical Address is divided into the following:

• Frame offset(d): It refers to the number of bits necessary to represent a certain word in a frame, or the Physical Address Space frame size, the word number of a frame, or the frame offset.
• Frame number(f): It’s the number of bits needed to indicate a frame of the Physical Address Space or a frame number.

Dedicated registers can be used to implement the page table in hardware. However, using a register for the page table is only useful if the page table is tiny. We can employ TLB (translation look-aside buffer), a particular, tiny, fast look-up hardware cache if the page table has a significant number of entries.

• The TLB is a high-speed, associative memory.
• LB entries are made up of two parts: a value and a tag.
• When this memory is accessed, an item is compared to all tags at the same time.
• If the object is located, the value associated with it is returned.

m = main memory access time

In case the page table is kept in the main memory,

then the effective access time would be = m(page table) + m(page in page table)

Practice Problems on Paging in OS

1. The logical memory gets broken into various blocks of similar sizes known as _______.

a) pages

b) backing store

c) frames

d) none of the above

Answer- (a) pages

2. The physical memory gets broken into various fixed-sized blocks known as _________.

a) pages

b) backing store

c) frames

d) none of the above

Answer- (c) frames

3. Which of these is used in the form of an index in a given page table?

a) page offset

b) frame offset

c) frame bit

d) page number

Answer- (d) page number

4. The smaller page tables can be implemented in the form of a set of which of these?

a) registers

b) counters

c) stacks

d) queues

Answer- (a) registers

5. Paging helps in increasing the ______ time.

a) execution

b) context – switch

c) waiting

d) all of the above

Answer- (b) context – switch

Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus, GATE Previous Year Question Paper, and more.

Also Explore,

• Batch Operating System
• Binary Semaphores in Operating System
• Contiguous Memory Allocation in Operating System
• Counting Semaphores in Operating System
• Deadlock Detection and Recovery in Operating System
• Deadlock Prevention in Operating System
• Distributed Operating System
• Dynamic Partitioning in Operating System
• Fixed Partitioning in Operating System
• Functions of Operating System
• Methods for Handling Deadlock in Operating System
• Multiprocessing Operating System
• Multiprogramming Operating System
• Multitasking Operating System
• Network Operating System
• Non-Contiguous Memory Allocation in Operating System
• Operating System Services
• Process in Operating System
• Process Scheduler in Operating System
• Process Scheduling in Operating System
• Process State in Operating System
• Real-Time Operating System
• Resource Allocation Graph in Operating System
• Semaphores in Operating System
• Time-Sharing Operating System
• Types of Operating System