The Gateway to Computer Science Excellence
0 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?
in Operating System by Active (3.6k points) | 192 views
When page table is not fit into the one frame then we apply paging on the page table. After applying paging  there in no external fragmentation.
U are not getting my point. I am talking about the multilevel page table itself, in the multilevel page table, the last page table is lesser than the total frame size in most of the cases, which results in internal fragmentation. If many such cases happen, then will there not be a chance of external fragmentation?
No it is still internal fragmentation. external fragmentation happens when space is available but we can't allot it to a process.

I am presenting that case only, see the case below

 Here frames are of 4KB, now say a page of size 4KB comes... will it not suffer from external fragmentation fragmentation?

So you are trying to say that if there are many internal fragmentation in a system then it creates external fragmentation ?
is it not?

Internal Fragmentation occurs when a fixed size memory allocation technique is used. External fragmentation occurs when a dynamic memory allocation technique is used.


I will like to deny..

Moreover, just look at your own definition of external fragmentation-->

external fragmentation happens when space is available but we can't allot it to a process.

Haven't I presented the same case above?

yes you are correct.

But external fragmentation also depends on size of process.

external fragmentation happens when we can't allocate a new process some space but the space is still available.

In the case which you are telling  we will have external fragmentation if  you fill the whole space provided to store the page tables and then a new page table comes. Then we will no frame left to allocate it. But that case is rare.

In the case which you are telling  we will have external fragmentation if  you fill the whole space provided to store the page tables and then a new page table comes. Then we will no frame left to allocate it.


2kb and 2kb space allocated a 4kb process in non contiguous manner

So there is no external fragementation because all space utilized properly

We had 4kb space and process size also 4kb

2 Answers

+1 vote

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

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.


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.


by Boss (24.1k points)
0 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 - All your doubts will be cleared and it is going to give a clear picture of multi-level paging as well.

by Active (1.3k points)

Related questions

0 votes
1 answer
0 votes
1 answer
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,333 answers
105,197 users