1,632 views
1 votes
1 votes
I have read that paging does not suffer from external fragmentation as the frames and the pages are all of the equal sizes, but when we store a last level page table in a frame at that time it may not fully occupy the frame. Similarly, if n such page tables are stored, that does not occupy the frames entirely, then there can be a case where all the gaps exceed a page size. Then there should be external fragmentation, right? So why is it said that paging does not have external fragmentation?

3 Answers

3 votes
3 votes

The collection of internal fragmentation do not contribute to external fragmentation. External fragmentation is contributed by the empty space which is EXTERNAL to partition(or page). So if suppose there are only two frames in main memory ,say of size 16B, each occupied by only 1B data. The internal fragmentation in each frame is 15B. The total unused space is 30B. Now if you want to load one new page of some process, you will see that you do not have any frame available. You are unable to load a new page eventhough you have 30B unused space. Will you call this as external fragmentation? Answer is no. Because these 15B unused space are INTERNAL to the pages. So in paging, internal fragmentation is possible but not external fragmentation.

1 votes
1 votes

We do paging because we want a process to be stored in non contiguous manner in the main memory.

So we divide main memory in equal size partition called frames and secondary memory space also in equal size partition where each partition is called page such that

Size of page = size of frame.

here size of each frame is fixed so we have fixed size partitioning scheme thus leading to internal fragmentation in the main memory.

Since size of secondary memory > size of main memory(let)

so we will have more pages as compared to frames.

let there be 4 frames in main memory and 7 pages in secondary memory.

Suppose there is a process which occupies $3$ pages in secondary memory i.e. $P_1,P_2,P_3$ pages are occupied in secondary memory and the remaining pages are still free.

So we will now pick each of the page and find a frame for it to store it in main memory.

page frame allocated
1 2
2 1
3 4
4  
5  

Suppose the allocation goes like shown above.

now only frame 3 is empty.

Now we store the above table(page table) also in a frame and we only have frame 3 left to allocate it as all other frames are occupied.

SO NOW MAIN MEMORY IS FULL SINCE ALL THE FRAME OF MAIN MEMORY IS OCCUPIED.

now suppose a new process is created in Secondary memory and it occupies $P_4,P_5,P_6$ so now we want to execute it so we again need frames but frames are full.

So we will deallocate the frames and delete the page table to process 1 and give it to pages and page table of process 2 now process 2 will execute.

If process 2 would have been of size 6 pages then concept of virtual memory would have been used.

So NO EXTERNAL FRAGMENTATION

1 votes
1 votes

Let's first understand what is External fragmentation. External fragmentation is caused due to "Contiguous behavior" of memory location and not just by Internal fragmentation i.e. we were not able to span a process over non-contiguous memory locations. Now, when some processes (who got preempted or get executed) leaves the Main Memory, they create Holes (in dynamic memory partitions). These Holes may or maybe Contiguous. If a upcoming process cannot accommodate in one of these Holes, it has to wait for bigger Hole, which may or may not be created and therefore, it will increase it's execution time (Overall, decreasing the CPU Utilization). Therefore, we came across a concept called Paging. What we do here is, we divide the Physical memory (Main memory or RAM) into frames and a process into pages such that Page Size = Frame Size. Now, we can span a process over non-contiguous manner in these frames. 

Coming to your Query, there can be External fragmentation in Paging. Generally, the last level page table is either smaller or equal to a Page Size. Same thing goes for Last page table (if you know this 😬 or you can say last Page) of second level, third level, and so on. On an average, there is an overhead (wastage) of about p/2, where p is Page Size. Therefore, we should need to find an Optimal Page Size to overcome this overhead, which is equal to p = $\sqrt{2se}$ (is Size of Virtual Address space and is Page table entry).

Please go through this example too - https://gateoverflow.in/490/gate2008-67?show=94002#c94002. All your doubts will be cleared and it is going to give a clear picture of multi-level paging as well.

Related questions

0 votes
0 votes
1 answer
1
Markzuck asked Dec 22, 2018
1,327 views
for memory overhead in Multi level paging, for innermost table only 1 page size shall be counted na? and NOT the complete page table size?please explain the concept, than...
0 votes
0 votes
1 answer
2
1 votes
1 votes
1 answer
4