22

Storing local variables on a stack is an implementation detail – basically an optimization. You can think of it this way. When entering a function, space for all local variables is allocated somewhere. You can then access all variables, since you know their location somehow (this is part of the process of allocation). When leaving a function, the space is ...


21

Having y on the stack doesn't physically prevent x from being accessed, which, as you pointed out, makes computer stacks different from other stacks. When a program is compiled, the positions of variables in the stack are also predetermined (within the context of a function). In your example, if the stack contains an x with a y "on top of" it, then the ...


14

I can see why you're confused. The diagram is a bit confusing, and may actually be incorrect. First off, let's think about why a kernel needs a memory allocator below the level of pages. This is probably already stuff that you mostly know, but I'll go through it for completeness. Pages are the typical "unit" of memory operations. When a user-space ...


13

The entries of a hash table are stored in an array. However, you have misunderstood the application of the modulo operator to the hash values. If the hash table is stored in an array of size $n$, then the hash function is computed modulo $n$, regardless of how many items are currently stored in the table. So, in your example, if you were storing ...


11

With fixed-size blocks, what you have described is a free list. This is a very common technique, with the following twist: the list of free blocks is stored in the free blocks themselves. In C code, it would look like this: static void *alloc_ptr = START_OF_BIG_SEGMENT; static void *free_list_head = NULL; static void * allocate(void) { void *x; if ...


11

To provide a concrete example of how a compiler manages the stack and how values on the stack are accessed, we can look at visual depictions, plus code generated by GCC in a Linux environment with i386 as the target architecture. 1. Stack frames As you know, the stack is a location in the address space of a running process that is used by functions, or ...


9

There are two special registers: ESP (stack pointer) and EBP (base pointer). When a procedure is invoked the first two operations are usually push ebp mov ebp,esp The first operation saves the value of the EBP on the stack, and the second operation loads the value of the stack pointer into the base pointer (to access the local variables). ...


8

You are confused because the local variables stored in stack are not accessed with the access rule of stack: First In Last Out, or just FILO. The thing is that the FILO rule applies to function call sequences and stack frames, rather than to local variables. What is a stack frame? When you enter a function, it is given some amount of memory on the stack, ...


7

Network latency is orders of magnitude too high for a remote server to usefully share its RAM directly, even if you could cobble together a virtualization layer to make it work. However, today's network speeds are high enough that remote RAM based key/value stores like memcached can compete favorably with hammering a local database due to insufficient local ...


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

Hash-table usually do waste space. Many algorithms do, since time-space trade-offs are common, but they usually hide it better :). Like other algorithms, hash-tables do it to get better time performance. The first point is that you try to avoid collisions in your hash-table, because that keeps the access time cost constant (but collisions are usually ...


6

The idea underneath the slab allocator is that the operating system needs specific but somewhat standard data structures (for example the process PCB, semaphores, file metadata etc) that suggest the memory usage that is necessary for them. The slab allocator algorithm provides stocks of memory areas whose dimensions and initialization are optimized for ...


5

Heap allocators typically call a system call to reserve a region of pages and then dole out chunks of that to new, malloc, and other higher-level calls. The system call on Unix used to be brk and sbrk, but implementations sometimes use mmap as well. I think windows uses VirtualAlloc, but it's not totally clear to me. A good resource for this is Wikipedia's ...


5

Heap memory and the heap data structure are two different and unrelated things. This really bothered me when I was learning about memory, especially since stack memory was actually a stack. The original use of the word heap in computer science referred to the data structure. However, in the 1970s some authors began to use the word heap to refer to the pool ...


5

This is really a question about memory allocators and doesn't have much to do with operating systems. "Memory control block" does seem to be a DOS specific term for a node in a free list. I'm not aware of any broadly used term for those nodes. They are usually just called "free blocks" or "unallocated blocks" or some such. An operating system kernel ...


5

RAM is cleared after each power cycle. The power-up value of cells depends on the technology. Static RAM content is usually random (there is no preference between 0 and 1, but the same chip may present similar patterns after each power-up). Dynamic RAM has the value corresponding to empty capacitors in the RAM array, which usually corresponds to ones, but ...


4

This answer is about generic memory management techniques. I missed that the question asks about the case where all blocks have the same size (and are aligned). The basic strategies you should know are first-fit, next-fit, best-fit, and the buddy system. I wrote a short summary once for a course I taught, I hope it's readable. I point there to a fairly ...


4

Short answer, summarizing the other answers: It is done by the operating system. Simple (early) operating systems assigned fixed size areas for code, data, stack + heap (with the idea that the stack and heap grew towards each other). Early Unix systems had a space for the stack and an area for data, used also by the heap (which could be extended with the ...


4

First there is the answer already given by André Souza Lemos. The data need not be destroyed. It is usually sufficient to mark the corresponding space as unused in some table, so that the system will no longer try to read it: it considers that there is nothing stored there. But the data is often still there, often fairly easy to find, even when some key ...


4

Deleting is not necessarily destroying data. It can be done (much faster, indeed) by making it inaccessible. You can do it by erasing critical information from the data structures that are used to index the data you want to delete. How exactly this is done depends on how the storage device is organized (formatted).


4

There are many ways to implement local variables by a language runtime system. Using a stack is a common efficient solution, used in many practical cases. Intuitively, a stack pointer sp is kept around at runtime (in a fixed address, or in a register -- it does really matter). Assume that every "push" increments the stack pointer. At compile time, the ...


4

Yes, it is certainly possible. It really depends if you want it enough to pay the price in terms of complication. First of all, I would strongly recommend that your array should have negative indices: a[-1], a[-2], and so on. This will be good because the stack grows downwards, and if you adopt this convention then you will not need to move all your ...


3

"Local variable" is a concept in the source language. Some target languages have the concept (e.g. virtual machines with dictionary-based scopes), but many do not. Since you're using Java, let's look at the JVM. A local variable cannot be accessed by other methods (e.g. you can't pass a variable by reference like you can in C++ or Fortran), and cannot be ...


3

There is no single standard implementation of JavaScript, so if you want to know what happens in a particular implementation, you should use your web search skills, focusing your efforts on that particular implementation. That said, a cursory web search reveals two main points: Arrays can be implemented simply as associative arrays (also known as hash ...


3

A good way to look at hash tables is like a lookup table with infinite index range (well, not really infinite, you're still constrained by the value limit of the key you're using). Lets say you're trying to store some specific values of sqrt(x) in a lookup table where X is an integer, it would go something like this: [1] = 1 [3] = 1.732 [10000] = 100 This ...


3

Dynamic linking is performed at the time of program loading only and uses compile-time established names. Dynamic loading can be done at any point in program execution. From wikipedia: Unlike static linking and loadtime linking, this mechanism allows a computer program to startup in the absence of these libraries, to discover available libraries, and to ...


3

Quick note, sizeof(char) is defined to be 1. So you can just simplify to malloc(1). The real answer however is quite boring. Your program has what's so called undefined behavior. In C (and C++), if you make an error like this the result is undefined. This could mean that your program will crash right as you trigger the bug. But it doesn't necessarily crash. ...


3

The easiest idea is to think of variables as fix names for addresses in memory. Indeed, some assemblers display machine code that way ("store value 5 in address i", where i is a variable name). Some of these addresses are "absolute", like global variables, some are "relative", like local variables. Variables (i.e. addresses) in functions are relative to ...


3

Row-major order stores the rows of the array one after another in memory. That is, the array a d g j b e h k c f i l is stored as a d g j b e h k c f i l To determine the address of an element in this list, we need to know how many elements come before it. For element $[I,J]$, this is the number of complete rows above row $I$ times the length of a ...


2

What would happen if the overlay driver experienced an error and the error handling routines weren't loaded? You should think of the error handling routines as being a necessary part of the overlay driver.


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