in Operating System
1,177 views
0 votes
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
22 44 79
1.2k views

5 Comments

edited by

I will like to deny..

https://www.geeksforgeeks.org/fixed-or-static-partitioning-in-operating-system/

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?

0
0
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.
0
0

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.

meaning??

0
0
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
0
0

Subscribe to GO Classes for GATE CSE 2022

3 Answers

2 votes
2 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.

by
1 5 10
1 vote
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
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

by
99 129 310
1 vote
1 vote

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.

by
1 5 16

Related questions

0 votes
0 votes
1 answer
1
1 vote
1 vote
1 answer
3