What happens in UNIX/Linux when a program is bigger then size of memory

If you can modify the source code, then use rusage data to measure the RSS and record how many TCP connections are in play at the time of the measurement.

If source code cannot be changed, then use the RSS of the network app as reported by top or ps and get the number of network connections at the time of measurement from lsof -i.

Collect this data every minute while your application moves through peak load, and from that data you can come up with a formula that relates number of connections to RAM usage.

Of course there are a lot more things that you could measure, in particular you might want to measure kernel RAM usage, although tcp data structures should be predictable and calculable in advance. In any case, have a look at this question https://serverfault.com/questions/10852/what-limits-the-maximum-number-of-connections-on-a-linux-server for more information on TCP tuning and how to get a clear view of what is happening in the network stack.

Kudos on your research so far, this is indeed an interesting set of questions.

There’s an important aspect to consider here generally: memory allocation is partly the operating system’s responsibility, and partly each running process’s responsibility (ignoring old systems without memory protection and virtual address spaces). The operating system takes care of providing each process with its own address space, and allocating physical memory to processes when necessary. Each process takes care of carving up its address space (to some extent) and ensuring it’s used appropriately. Note that a process’s responsibility will be largely invisible to programmers, since the runtime environment takes care of most things.

Now, to answer your questions...

1. In my mind garbage collection is one step removed from what you’re doing here. I imagine you’re writing in C, using malloc() and free(). Garbage collection, where supported by the programming language and runtime environment, takes care of the latter part: it identifies blocks of memory which were previously allocated but are no longer in use (and, importantly, can never again be used), and returns them to the allocator. The question linked in JdeBP’s comment provides some background, but I find it mostly interesting because it demonstrates that different people have very different opinions on garbage collection, and even what constitutes garbage collection.

   In the context we’re interested in, I would use “memory compaction” to talk about the process under discussion.

2. From a userspace programming perspective, what your professor is asking for isn’t possible, in C, under Linux, for one simple reason: what we care about here isn’t physical memory fragmentation, it’s address space fragmentation. When you allocate your many 800,000-byte blocks, you’ll end up with just as many pointers to each block. On Linux, at this point, the operating system itself hasn’t done much, and you don’t necessarily have physical memory backing each allocation (as an aside, with smaller allocations the operating system wouldn’t be involved at all, just your C library’s allocator; but the allocations here are large enough that the C library will use mmap, which is handled by the kernel). When you free the odd-numbered blocks, you get back those blocks of address space, but you can’t change the pointers you have to the other blocks. If you print the pointers out as you go, you’ll see the difference between them is not much more than the allocation request (802,816 bytes on my system); there’s no room between two pointers for a 900,000 byte block. Because your program has actual pointers to each block, rather than some more abstract value (in other contexts, a handle), the runtime environment can’t do anything about that, and so it can’t compact its memory to coalesce free blocks.

   If you use a programming language where pointers aren’t a programmer-visible concept, then memory compaction is possible, under Linux. Another possibility would be to use a memory allocation API where the returned values aren’t pointers; see for example the handle-based heap allocation functions under Windows (where pointers are only valid when a handle is locked).

3. Your professor’s exercise is effectively measuring the performance of mmap, which includes its free-block-walking algorithm. You first allocate 3 × m blocks, then free half of them, and then start allocating m blocks again; freeing all those blocks dumps a huge load of free blocks on the kernel’s allocator, which it needs to keep track of (and the time taken by the free calls shows that there’s no optimisation being done at this point). If you track the allocation times of each individual block, you’ll then see that the first 900k allocation takes much, much longer than the others (three orders of magnitude on my system), the second is much faster but still takes a lot longer (two orders of magnitude), and the third allocation is back to typical performance levels. So there’s something going on, but the returned pointers show that it wasn’t memory compaction, at least not allocated block compaction (which, as explained above, is impossible) — presumably the time corresponds to time processing the data structures the kernel uses to keep track of the available address space in the process (I’m checking this and will update later). These lengthy allocations can grow to dwarf the overall allocation sequences you’re measuring, which is when the 900k allocations end up taking longer overall than the 800k allocations.

   The reason overcommit changes the behaviour you see is that it changes the exercise from purely manipulating address space, to actually allocating memory, and thus reduces the size of your playground. When you can overcommit, the kernel is only limited by your process’s address space, so you can allocate far more blocks and put much more pressure on the allocator. When you disable overcommit, the kernel is limited by the available memory, which reduces the value you can have for m down to levels where the allocator isn’t stressed enough for the allocation times to blow up.