0

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.

enter image description here 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.

Picture

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 :

Picture

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?

1
1

The answer is that you set yourself up exactly in the situation that does not create internal fragmentation, as defined by the text, which says,

If the memory requirements of a process do not happen to coincide with page boundaries

But above, you set things up so that they did coincide. So... no fragmentation. Except that, as you noticed, the unused heap and stack do occupy space, and those spaces ought to be considered "fragmented" (however harmlessly). This is why you don't want to have huge pages.

However, I believe that memory is not allocated that way. Pages are not just memory chunks, they have properties that can be set. So, for example, you might put the code in a bunch of pages, and then inform the OS that those pages are read only (and/or can be shared with other processes). You can't do that with the heap. On the contrary you might request for heap pages not to be executable, so that several security exploits will not work.

To enjoy these goodies, you need to allocate separate pages to the various types of process memory.

So, it would be extremely unlikely for the code, static data and heap sections to be exactly aligned to whatever the page size is; and there, internal fragmentation would occur.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.