Understanding how internal fragmentation occurs in systems using only paging with huge page size

Question

The excerpt below is from the OS text by Galvin et. al.

When we use a paging scheme, we have no external fragmentation: any free frame can be allocated to a process that needs it. However, we may have some internal fragmentation. Notice that frames are allocated as units. If the memory requirements of a process do not happen to coincide with page boundaries, the last frame allocated may not be completely full. For example, if page size is $2,048$ bytes, a process of $72,766$ bytes will need $35$ pages plus $1,086$ bytes. It will be allocated $36$ frames, resulting in internal fragmentation of $2,048 − 1,086 = 962$ bytes. In the worst case, a process would need n pages plus $1$ byte. It would be allocated $n + 1$ frames, resulting in internal fragmentation of almost an entire frame.

The above screenshot is from "High-Performance Computer Architecture" by Georgia Tech... Here the instructor says, that the size of the process is till that much as shown by the grey brace in the right. And our system is such that we are allocating say 2 pages to the process, then the dashed portion is the internal fragmentation.

The problem which I am having is something as follows. I drew the situation as shown above. The virtual address space of the process is shown in green. On the left, I show the virtual address bits. Now, in computers, page sizes are usually in powers of 2. So the page offset I guess, however long, if the page size is less than the virtual address space size, then it shall equally divide the virtual address space of the process. Now if it is equally divided, the last portion of the virtual address space shall have the stack section, then how shall there be a [internal] fragmentation [in the last part of the last page as shown in the above pictures]?

Suppose if we use a page size of $4 MB$ then :

The picture might be something like this I guess. Note that the portions shown in blue I guess are internal fragmentation. While the huge gap between heap and stack is not allocated frames in the main memory, so we need not bother about them... But I guess it depends on the size of the stack and the code, data, and heap portion. Whether they are aligned properly as per the page or not, to have internal fragmentation and I feel we can't just simply say that only the last part of the last frame shall not be occupied and it is the only internal fragmentation. Moreover, how is the Galvin text calculating the size of the process?

Answer 1

Internal fragmentation occurs because the OS cannot allocate less than one page to a certain process. This implies that the last chunk of code/data for a process will take one page no matter its size. The worst case scenario is when the code/data use several pages + 1 byte. You thus end up with a whole page lost to internal fragmentation.

Now you are right that the code/data doesn't necessarily fit into one page. This creates some internal fragmentation in the other pages. This internal fragmentation though is minimal considering that it can be as long as an instruction can be.

To determine the size of a process, the OS simply looks in the executable. Most compilers/linkers will split the code/data of a compiled program in pages already. This means that the loading of processes is quite simple (unless you have some dynamic linking which makes it more complex). The OS simply allocates the pages that the process needs according to what is laid out in the executable.

In dynamic memory allocation, the libc implementation keeps track of the data you have available and attempts to avoid internal fragmentation as much as possible.

Answer 2

Forget the stack, forget all the details of the memory layout. Internal fragmentation always happens, because the OS hands out memory in multiples of the page size, and consumers might not need the full page. Whatever portions of pages are unused are "internal fragmentation".

Under reasonable assumptions about allocation sizes, the bigger the page size, the bigger the average amount wasted by rounding up each allocation (or process, or arena, or however you slice it) to a whole number of pages. Therefore larger page sizes go hand-in-hand with larger losses to internal fragmentation.

Imagine throwing a pizza party where you tell the guests that if they want to attend, they have to order one or more entire pizzas for themselves, and not share with anyone else. How much pizza will get thrown out at the end of the day compared to a party where each guest takes one or more slices, instead?