Internal Fragmentation in Paging

(Ashish Tyagi) #1

I was going through the lecture videos and I had a question about one of the proposed “pros” of paging.

The slides mention that there’s negligible internal fragmentation due to the small allocation sizes. But let’s say a process starts by allocating a billion sized array. Presumably this would result in a request for thousands of pages which, for the sake of simplicity, let’s assume that the Kernel is able to grant. Now if the process just goes to sleep, all these allocated pages would just sit there and be unavailable for other processes that could’ve made better use of them. Would this not be an example of (significant) internal fragmentation?

P.S. - Couldn’t find a good category for this. No one seems to have questions on lecture :sweat_smile:

(Matthew Mc Govern) #2

Well, the trick there is that that huge allocation doesn’t have to really have to happen until the pages are actually used by that process. You can write your virtual memory system in such a way that a process can ask for a bunch of memory, the kernel says ‘sure’, but then doesn’t actually allocate the page until it’s used.

Swapping (aka paging) should allow the kernel to move pages to disk and back into memory as needed. If your sleeping process uses a bunch of pages and goes to sleep, the kernel should be able move that processes memory to disk so you never really run out of memory (until you’re out of swap space).

(Ashish Tyagi) #3

How do you define “used by the process”? The naive definition can just be “oh, the process wants to allocate this billion size array, so it probably has some important data to store. Let me give it the pages it wants” but I don’t think that’s the definition you’re thinking of. I’m just having trouble coming up with a programmatic definition of “used by the process”.

I was aware of the swapping solution, but that would be terribly slow (right?). Geoff mentioned in lecture that when a process wants a virtual address translated, if it needs help from the kernel the machine’s already too slow. So moving stuff back and forth between memory and disk has to be wayyyyyyy too slow. Of course I also realize that swapping’s necessary to give processes the illusion of having more memory available than there actually is.

(Matthew Mc Govern) #4

I meant a process ‘uses’ memory when it reads from it or writes to it. Your VM system doesn’t have to just give a process all of the memory when it asks for it. A process should be able to malloc a huge amount of data without having the kernel immediately allocate any physical pages.

re: swapping
It should end up being sort of slow. In sys161 there are some sys.config hacks to make the time more tolerable when you’re testing.

On the slowness of address translation: It would be slow if the kernel had to translate all the addresses in software. There is a piece of hardware called the Translation Lookaside Buffer (TLB) that will handle those translations if it’s managed correctly. The kernel will have to do some things to manage that TLB, but the TLB will translate things once you set it up right.

This assignment can get super confusing, so don’t feel bad about asking for clarification. If this is still super confusing just keep asking questions and I’m sure another ninja or TA will chime in at some point :slight_smile:

(Ashish Tyagi) #5

That makes sense. Thanks for the answers!

FWIW, my question(s) weren’t in reference to asst3. I just wanted to understand the theory behind paging and why it works. All of that makes a lot sense, so thanks again!

(Geoffrey Challen) #6

We’ll discuss this when we talk about swapping and on-demand paging. But Matt’s answer is correct. For example, this code doesn’t necessarily allocate any memory:

int huge[HUGE_ARRAY];

All it does is either (a) push the stack down (if it’s a local variable) or (b) configure the ELF file to allocate space for this array (if it’s a global variable). The process actually has to touch the array to cause the memory to be instantiated, and even then the kernel can create it (and swap it out) page by page as needed.