Paging in Operating System
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.
Prerequisite
Before this its important to know a few terminologies –
This will also be useful –
- 1 byte = 2^3 bits
- 1KB = 2^10 bytes
- 1MB = 2^20 bytes
- 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
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
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.
- For 14 bits of Physical address the physical address space would be 16K.
- Thus number of frame = physical address space/frame size = 16/2 = 8
- f value would be 3 as 2 power 3 is 8 (need help? – Check frame number definition above)
- For 16 bits Logical address the logical address space would be 64 bits.
- Thus number of page = physical address space/page size = 64/2 = 32
- 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
Additional Facts about Page Table
- Page table is kept in main memory
- Page-table base register (PTBR) points to the page table
- Page-table length register (PTLR) indicates size of the page table
- In this scheme every data/instruction access requires two memory accesses
- One for the page table
- one for the data / instruction
- 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.
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 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
Login/Signup to comment