Paging in Operating System

January 21, 2023

Paging in OS

Paging in OS

Paging is a memory-management scheme that permits the physical address space of a process to be noncontiguous or in other words eliminates the need for contiguous allocation of physical memory.

Paging in OS

First you need to understand the meaning of contiguous memory. It means that the memory blocks must be side by side to one another without any breakage.

What is Paging?

Paging is a memory-management scheme that permits the physical address space of a process to be noncontiguous or in other words eliminates the need for contiguous allocation of physical memory.

That is we can have logically use memory spaces that physically lie at different locations in the memory

This allows viewing memory spaces that physically lie at different locations in the hardware to be logically viewed as contiguous.

This is possible via mapping of physical and virtual memory that is done by hardware component called memory management unit (MMU). The mapping process that is done by MMU is basically paging process.

Let’s see how paging process is implemented.

Paging OS 1
Prerequisite 

Before this its important to know a few terminologies –

This will also be useful –

  1. 1 byte = 2^3 bits
  2. 1KB = 2^10 bytes
  3. 1MB = 2^20 bytes
  4. 1GB = 2^30 bytes
Logical View
  • Logical Space Available – The total space available in logical system
  • Logical Address – This is also known as Virtual Address and is directly generated by the CPU of the system.
  • Conversion Examples –
    • If Logical address is 21 bit then -> Logical Address space = 221 which is 2 * 220. Thus 2M words
    • If Logical address is 23 bit then -> Logical Address space = 223 which is 23 * 220. Thus 8M words
Physical View
  • Physical Space Available – All possible set of physical store locations
  • Physical Address – This is true address as seen where information is stored in the hardware.
  • Conversion Examples –
    • If Logical address is 34 bit then -> Logical Address space = 234 which is 24 * 230. Thus 16 G words

Frames vs pages

Frames are basically the sliced up physical memory blocks of equal size. Example : 512kb of memory can be divided into 4 parts for 128kb each

While, pages are sliced up logical memory blocks of equal size. While solving any problem always the page size should be equal to frame size.

Some Formulas – 

  • No. of Frames = Physical address space/ Frame size
  • No. of pages = Logical address space/ Page size

Logical Address

Page address is called logical address and is a combination of  by page number (denoted as ‘p’) and offset (denoted as ‘d’).

Page number sometimes is also called as VPN(Virtual Page Number).

Logical Address = Page number + page offset

Logical Address – p + d

● For given logical address space 2m and page size 2n

Page Number(p)- Number of bits required to represent the pages in Logical Address Space

Page offset(d) – Number of bits required to represent particular word in a page or page size of Logical Address Space

Page Number Page Offset

Physical Address

Frame address is called physical address and is a combination of a frame number (denoted as ‘f’) and the offset (denoted as ‘d’).

Frame number is also sometimes referred as PFN (Physical Frame Number.

Physical Address = Frame number + page offset

Physical Address – f + d

Frame Number(f) – Number of bits required to represent the pages in Physical Address Space

Frame offset(d) – Number of bits required to represent particular word in a page or page size of Physical Address Space

Note – We have seen students getting confused in if frame belongs to physical or logical and page belonging to physical or logical.

  • Frame is Physical
  • Page is Logical
Paging OS 2
OS dekstop gif
OS mobile gif

Priority Scheduling

CPU Scheduling

FCFS Scheduling

Preemptive Scheduling

How Paging Happens in System?

There are two ways paging can happen in the system

  • Using Page Table
  • Using translation look-aside buffers or TLB’s
Using Page Table

Lets take an example to understand, where physical address is 14 bits and Logical address is 16 bits and let’s assume a frame size(page size as both are equal) of 2 bit.

  1. For 14 bits of Physical address the physical address space would be 16K.
    1. Thus number of frame = physical address space/frame size = 16/2 = 8
    2. f value would be 3 as 2 power 3 is 8 (need help? – Check frame number definition above)
  2. For 16 bits Logical address the logical address space would be 64 bits.
    1. Thus number of page = physical address space/page size = 64/2 = 32
    2.  p value would be 5 as 2 power 5 is 32 (need help? – Check page number definition above)

Help – Check conversion example given above on this post to understand how the above happened.

Additional Formula for Page table – 

Size of page table = (total number of page table entries) *(size of a page table entry)

Assume a offset value of 10

Paging OS 3a
Paging OS 3b
Additional Facts about Page Table
  1. Page table is kept in main memory
  2. Page-table base register (PTBR) points to the page table
  3. Page-table length register (PTLR) indicates size of the page table
  4. In this scheme every data/instruction access requires two memory accesses
    1. One for the page table
    2. one for the data / instruction
  5. 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)
Using Translational Look-Aside Buffers or TLB’s

We all know registers are faster than normal storage options in system, which is why in page tables registers are used. But, registers can cause poor performance if the the page table is very large. To solve this problem we use a special faster hardware called TLB i.e. translational look aside buffers.

These are fast, and they have a tag and value.

Paging OS 4

Practice Question for you – (Very hard, if you’re able to solve this, you will be able to solve any question of this section)

Consider a machine with 64 MB physical memory and a 32-bit virtual address space. If the page size is 4KB, what is the approximate size of the page table?
(a) 16 MB
(b) 8 MB
(c) 2 MB
(d) 24 MB

Answer –

We suggest you don’t look at the answer, try it yourself.

Now, this question is very easy but, to confuse you. Somethings are given in bits and some are given in MB words.

Given –

  • Physical Memory – 64MB
  • Virtual Address Space – 32 bit i.e. 232
  • Page Size = 4KB = 22 *(210) = 212

So Number of pages i.e. number of entries in page table = 232/212

Thus number of entries – 220

Repeat the same process for Physical memory. Final out come will be

page frames = 226/212

Thus 214

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime
OS dekstop banner

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Get Prime
Course List
Course List

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout
Checkout