80

Because it's undecidable whether the program will use the memory again. This means that no algorithm can correctly determine when to call free() in all cases, which means that any compiler that tried to do this would necessarily produce some programs with memory leaks and/or some programs that continued to use memory that had been freed. Even if you ensured ...


53

As David Richerby rightly noted, the problem is undecidable in general. Object liveness is a global property of the program, and may in general depend on the inputs to the program. Even precise dynamic garbage collection is an undecidable problem! All real-world garbage collectors use reachability as a conservative approximation to whether or not an ...


37

Short version: "page" means "virtual page" (i.e. a chunk of virtual address space) and "page frame" means "physical page" (i.e. a chunk of physical memory). That's it, pretty much. It's important to keep the two concepts distinct because at any given time, a page may not be backed by a page frame (it could be a zero-fill page which hasn't been accessed, or ...


29

It's an incompleteness problem, not an undecidability problem While it's true that the optimal placement of deallocation statements is undecidable, that's simply not the issue here. Since it's undecidable for both humans and compilers, it's impossible to always knowingly select the optimal deallocation placement, regardless of whether it's a manual or ...


26

The trick to making this work is "paging." When bringing data from a hard disk into physical memory, you don't just bring a few bytes. You bring an entire page. 4k bytes is a very common page size. If you only need to keep track of pages, not each individual byte, the mapping becomes much cheaper. If you have a 48 bit address space and 4096 byte pages, ...


24

Sure. In principle, given appropriate hardware, you could have just a disk, with everything stored on disk. Any time the CPU did a load or store instruction, there could be some hardware that turns that into a disk read or write. It'd be extremely slow: on a magnetic disk, each seek takes about 10ms, so you could do about 100 random-access reads and ...


23

Currently, none of the posted answers are fully correct. Why don't compilers automatically insert deallocations? Some do. (I'll explain later.) Trivially, you can call free() just before the program exits. But there's an implied need in your question to call free() as soon as possible. The problem of when to call free() in any C program as soon as the ...


16

In terms of computability, it is known that every modern day computer can be simulated by a Turing Machine whose only storage is a single, linear tape cells that can be written. Assuming you can keep adding unlimited amounts of disk storage, a computer having only hard drives is just as powerful. So certainly you could make a computer without memory. Of ...


14

It's actually not that hard to design an operating system that doesn't require an MMU. There are a few conveniences you'll have to do without, but nothing insurmountable. Since different tasks will have to be loaded at different addresses, all your code (except for the kernel, the standard library, and any other code that's part of your base runtime ...


14

Actually, what you've described confuses ballooning and 'same-page-merging'. I'll try to elaborate on the two to make the distinction apparent. Memory ballooning This is a trick to make sure that some of the memory allocated to the guest virtual machine remains usable by another guest or the host itself (caches, etc). It's done in the following way: The ...


14

Note that I am not a garbage collection expert. This answer only gives examples of techniques. I do not claim that it is a representative overview of garbage collection techniques. An unscanned queue is a common choice. The queue can get large — potentially as large as the deepest data structure. The queue is typically stored explicitly, not on the stack of ...


14

The question is not purely academic. It is a matter of historical record that one of the earliest commercially-produced computers [sorry, I don't recall which offhand] did not have any RAM - all programs were executed by fetching instructions directly off of a magnetic drum [a rotating cylinder with outer surface magnetizable (disks came later)]. It was ...


14

So, there are two distinct uses of the word "map", that I'll unpack here. The first is very generic, where map means "to associate," particularly by way of a function. If we say "$f$ maps each $x$ to $2x$", then we're saying $\forall x \ldotp f(x) = 2x$. This usage includes "memory mapped IO:" there is a (conceptual) function associating each piece of ...


12

Because it isn't moved: it's copied.


11

Some work has been done that matches your description. For instance: Compiler-directed array interleaving for reducing energy in multi-bank memories. by Delaluz, V. Design Automation Conference, 2002. Proceedings of ASP-DAC 2002. 7th Asia and South Pacific and the 15th International Conference on VLSI Design. Proceedings. describes a such an optimization.


11

In a nutshell: Garbage collectors do not use recursion. They just control tracing by keeping track of essentially two sets (that may combine). The order of tracing and cell processing is irrelevant, which gives considerable implementation freedom to represent the sets. Hence there are many solutions that are actually very cheap in memory usage. This is ...


10

The operating system performs a lot of work before executing the first instruction. The OS must set up at least two data structures, the page table and the region map. The region map is called different things in different operating systems. Inside the Linux kernel, for example, it is a linked list of memory-region objects and some kind of index (e.g. a ...


10

The pattern you're talking about, where objects know how to clean their resources up, falls into three relevant categories. Let's not conflate destructors with finalizers - only one is related to garbage collection: The finalizer pattern: cleanup method declared automatically, defined by programmer, called automatically. Finalizers are called ...


10

"Humans do it, so it's not impossible" is a well-known fallacy. We do not necessarily understand (let alone control) the things that we create - money is a common example. We tend to overestimate (sometimes dramatically) our chances of success in technological matters, especially when human factors seem to be absent. Human performance in computer ...


10

The issue is mostly a historic artifact, not an impossibility of implementation. The way most C compilers build code is so that the compiler only sees each source file at a time; it never sees the whole program at once. When one source file calls a function from another source file or a library, all the compiler sees is the header file with the return type ...


9

From a computer architecture point of view, and with the caveat that nomenclature sometimes varies, especially when there is a family of related architectures which has evolved for a long time, or when the marketing department decides to that the usual terms have to used in another way (either to put the product in better light by using a bigger number, or ...


9

The lack of automatic memory management is a feature of the language. C is not supposed to be a tool for writing software easily. It is a tool for making the computer do whatever you tell it to do. That includes allocating and deallocating memory at the moment of your choosing. C is a low-level language you use when you want to control the computer ...


8

"Coalescing" can also refer to coalescing memory access patterns. In this usage, coalescing is used to mean making sure that threads run simultaneously, try to access memory that is nearby. This is usually because: Memory is usually retrieved in large blocks from RAM. Some processing units will try to predict future memory accesses and cache ahead, while ...


8

Since the number of frames is equal to the size of the memory divided by the page size, increasing the page size will proportionately decrease the number of frames. Having fewer frames will tend to increase the number of page faults because of the lower freedom in replacement choice. Imagine a system with four frames with the reference history of 0, 4, 3, ...


8

As I recall, copy collectors are supposed to be paging friendly, as the tracing by copying tends to improve the locality of pointer references. This has a positive effect on the program (mutator) that will cause less page faults when following links, and will also improve the next collection cycle as tracing will also cause less page faults. The tracing ...


8

I am not sure if this is actually on-topic here, but anyway. The main memory in x86 architectures is addressed byte-wise. If you want to retrieve 16 bits from address 2000h (note that AX is a 16 register), then you will need to read 8 bits from 2000h and 8 bits from 2001h. This is why the operation needs to read "2 cells". Note that the term "cell" is not ...


8

A page is a region of virtual address space, and a page frame is a region of physical memory. A page which maps a region of physical memory must have the same size as that piece of physical memory, otherwise there's no point. They also typically must be aligned correctly. If you try to map, say, a 2Mb page frame into virtual memory, both the virtual address ...


8

In the following I am going to be less than accurate in a number of ways, sacrificing technical accuracy to provide a basic understanding. It is obvious that you have read a number of technical sources and the very technicalness of the material is making it difficult for you to understand what is a fairly basic and simple concept. In simple terms the most ...


7

To answer this question I will visit some prerequisite understanding. Pure demand paging cannot be accomplished without hardware support. All modern computer architectures support paging, however many have different implementation details. x86 processors use what is called a page table to keep track of virtual address spaces and page mappings, as well as ...


7

Usermode to kernelmode: Wrong! ;-) Yes, interrupts are processed in kernel mode, and originally the way to enter kernel mode was by an interrupt forced somehow by software. On the DEC 2020 there was a set of UIOs (Unimplemented Instruction Opcodes), calling any of those caused a trap to the operating system. They included floating point instructions (if not ...


Only top voted, non community-wiki answers of a minimum length are eligible