3.1. RAM Memory
In this document you will learn how the RAM in a computer system is used to store all the data and coded required to execute a program. You will also learn about a technique called indirection used to manipulate memory addresses as if they were data.
Unless otherwise stated, for all the examples in this document we will assume that the memory cell contains 8 bits (1 byte).
igital circuits can only process information represented as zeros and ones, but in order to do that, data must be stored and remembered in another circuit. In a computer system, this storage location is called the RAM (random access memory), or memory in general. This memory is simply a large table of cells, each of them capable of storing a pre-defined unit of information such as, for example one byte.
As in the case of any other table, you need to know two numbers: the size of each of its elements, and the number of elements it has. Nowadays, memories used in computer systems store information in multiples of bytes, and the most common memory cell size is 1 byte. A memory can be seen then as a table containing a large number of bytes. The cells in this table are numbered started with the number zero for the first cell, one for the second, two for the third, and so on. The number of a cell is called its memory address and when written, it is usually prefixed by the symbol “@”. All the address values of a memory
is usually called its address space. The following figure shows the structure, content and addresses of a RAM chip storing S bytes.
Structure of RAM memory
The way data is accessed in memory is determined by the size of its cells. For example, if the cells store one byte each, the data is accessed one byte at a time. Some computer systems are capable of accessing a set of contiguous cells in one single operation, but this is simply to optimize the access time. Still, each cell is referred by its unique address. So, if you want to change the value of a single bit in a byte of a memory storing one byte per cell, you still need to read the entire byte, modify the single bit, and write the byte back again to memory.
Internally, each memory cell is implemented using a set of transistors and gates that are capable of remembering a previously defined set of bits. A memory chip is then simply a collection of cells, each of them capable of storing a unit of information, and each of them with a unique address. RAM memory also has the property of being volatile, that is, when the power is turned off, the data is lost. Non-volatile memories are those that maintain the information even after the system has been powered down. A USB memory stick, or a hard drive are examples of non-volatile memory. There are two types of volatile memory: static and dynamic.
Static RAM (also known as SRAM) is the memory that works intuitively as described. Data is stored in a cell until it is overwritten or the power is stopped. The number of transistors required to implement one cell is around one hundred, and the time it takes for the chip to perform a read operations is around ten nanoseconds (one nanosecond is 10-9 second).
Dynamic RAM (also known as DRAM) supports the same operations (read and write) and is also organised in cells, each of which has an address. The main difference is that the physical structure of the cell is much simpler and the value is stored using capacitors. If one of these capacitors is charged it is storing a one, and if discharged it is storing a zero. The problem is that capacitors leak current, and therefore, those that are charged (and therefore storing a one) start to discharge over certain time interval. If no operation is done, even if the chip has power, the charge in the capacitors disappears and the cell loses its value. However, if a read operation is done over a cell, it refreshes the charges of those capacitors storing ones. Cells take a few milliseconds to lose their charge.
This type of cell may seem to be useless because it forgets its data, however it is actually used in most computers. The reason is that the cells are much simpler than those in static memory and therefore chips with higher capacity (number of bytes) are more easily produced. The counterpart is that each memory cell must be read after certain time interval, thus slowing down the overall read/write operations. This problem is alleviated by including (in the chip itself) a mechanism to refresh the cells by simply reading all of them continuously before the capacitors lose their charge. This is the reason why this memory is called dynamic - because it is constantly being read or refreshed. Most computer systems use dynamic memory as their main memory due to its low cost and high capacity. The size of a cell in a dynamic memory is approximately one fourth of a static cell, and it is much simpler to design and produce.
Static RAM has a clear advantage over dynamic RAM - it is faster. Computer systems tend to use both types of memory. For components that need to be extremely fast, SRAM is used. For those components where a large amount of memory is needed, DRAM is the solution.
3.2. Memory operations
The two operations allowed in memory are reading a value and writing a value. In a read operation, the memory receives an address and returns the content of the cell with that address. In the write operation, the memory receives an address and a value (of the size of a cell), writes the value in the cell with the given address, and no result is produced. Another way to specify the behaviour of these operations is by using the notation typically used in programming languages when defining a function. For example, for a memory with 1 byte cells:
Byte Read(Address a): Given an address, returns the byte stored in that cell.
void Write(Address a, Byte b): Store byte b in the cell with address a.
The data stored initially in memory before any read or write operation is executed is undefined. If the first operation executed in RAM memory after starting a computer system is a read operation, the result is undefined or garbage. Thus, every read operation must be performed on a cell in which content has been previously written. The next figure shows the effect of executing a sequence of six operations over in a given memory.
Memory operations
As memories are digital circuits, all the data must be encoded in base 2, and this also includes the data needed for the read and write operations. The data that is read or written is a byte (if the memory cell has 1 byte size) and is encoded in base 2. The addresses are unsigned integers that may have values from zero to the number of cells minus one. These addresses need to be encoded also in base 2.
Therefore, reading one address from memory consists of sending the memory chip a set of bits encoding a memory address, and the memory chip sends the set of bits stored in the referred cell. Analogously, a write operation consists of sending two sets of bits, one encoding the information to be stored in the cell, and the other set encoding the address of the cell to be written.
The encoding of memory address has a direct relation with the size of the memory. Every cell in memory has an address, and therefore, the number of cells corresponds to the maximum value allowed for an address plus one (given that addresses begin at 0). Since the addresses are encoded in base 2, a memory chip with addresses represented by n bits, cannot have more than cells numbered from 0 to
. Another way to state this relation is that the size
of a memory chip and the number of bits
used to encode the addresses must satisfy the following equation:
As a consequence of this relationship between the number of bits used to encode an address and the number of elements, it is often the case that the number of cells in a memory chip is a power of two. Once a number of bits are used to encode the address, chips tend to include as many cells as possible.
The size of a memory chip is measured in units that do not follow the conventional rules of multiples of 10. Instead, the units are related by multiples of powers of 2. A kilobyte is 1024 bytes. The different units and their relation is shown in the following table:
| Prefix | Symbol | Size (Power) |
|---|---|---|
| kilo | K | |
| mega | M | |
| giga | G | |
| tera | T | |
| peta | P | |
| exa | E | |
| zetta | Z | |
| yotta | Y |
3.3. Connection between memory and processor
The connection between memory and a processor in a computer system must allow the execution of the operations as previously described. This is implemented using a technique in digital circuits called the bus. A bus is a set of wires in which several circuits can read and write binary values. In many computer systems, there are two buses. The first bus is used to send the address of the operation to the memory chip, and therefore is called the address bus. The second is used to send the data from the processor to the memory chip when performing a write operation, or from the memory chip to the processor when performing a read operation. This bus is called the data bus. Aside from these two set of wires, an additional one bit wire is needed so that the processor notifies the memory chip the type of operation that is requested. This signal is typically represented in digital circuits as denoting that the value 1 is used to encode the read operation, and zero to encode the write operation. The following figure shows how these signals are typically connected in a computer system.
Signals connecting processor and memory
The slanted line across the bus lines is the notation used to denote the number of bits or wires that are part of that signal. In the previous figure, the data bus has 8 bits, whereas the address bus has a generic n bits. From the relation between the number of bits used to encode the address we can deduce that the maximum memory size for this computer system is
bytes.
Buses are implemented as metallic tracks on a chip surface. The wires are connected to the input and output ports of the processor and memory chips. Thus, adding an extra bit to the address bus to allow the system to have double the memory, is usually not possible. Today’s computer systems include a large enough number of address bits so that memory can grow up to a reasonable size. Computer systems may operate with a memory smaller than what is allowed by the number of bits used to encode the address. The following figure shows the situation in which a processor has 32 bits to encode the address, and yet, the memory physically available is only 256 Megabytes.
Example of possible memory and available memory in a computer system
Processors typically include a mechanism by which the upper limit of the address space is known. Before any operation is executed in memory, the address is checked against this limit. If the address is beyond this value, the operation is stopped and an exception is raised.
3.4. Data Storage
The only structure offered by the memory in a computer system is the storage of values in cells. When using computer systems, however, we often need to make use of data that is structured a more complex way than a single memory cell alone. Therefore, there must be a policy to store other types of data structures manipulated by a processor. There must be a description of how the data structures used in a program are mapped to the structure provided by a RAM memory chip.
High level programming languages such as Java define a set of data structures called basic data types, plus a mechanism to combine them and create more complex data structures. In those languages that are compiled, the compiler is in charge of mapping the complex data structures to the memory of the computer system. Processors are typically designed to execute certain operations very fast over data of certain sizes. For example, in some processors addition and subtraction of 32 bit integers can be executed faster than for 64 bit integers. If the processor is not capable of performing certain operations (for example, multiplication of numbers of 128 bits), it typically resorts to some library that can execute the operation at a much higher cost in time. The following table shows the basic data types in Java, their corresponding sizes in bytes, and the range of values that they can encode.
| Type | Values | Size | Range |
|---|---|---|---|
| Boolean | true, false | 1 bit | |
| byte | Integer | 8 bits | [-128, 127] |
| char | Character (unicode) | 16 bits | [0, 65535] |
| short | Integer | 16 bits | [-32768, 32767] |
| int | Integer | 32 bits | [-2147483648, 2147483647] |
| long | Integer | 64 bits | [-9223372036854775808, 9223372036854775807] |
| float | IEEE-754 Floating point | 32 bits | [±1.4012985E-45, ±3.4028235E+38] |
| double | IEEE-754 Floating point | 64 bits | [±4.94065645841246544E-324, ±1.7976931348623157E+308] |
The simple rule to store data in memory is to use as many consecutive cells as needed to store a complex data structure. The address of the first cell from which the data structure is stored will be referred to as the data address. Analogously, when a data structure is stored at a certain memory address, what it really means is that it is stored with as many memory cells as required starting at the given address.
3.4.1. Storage for Booleans
Booleans, despite being the most simple data structure (only two possible values), are not the easiest ones to store. Memories allow access the values stored in an entire cell (typically 1 byte minimum), so storing a single bit often means accessing information that is not directly available and requires additional processing to extract or insert the appropriate value from or into the whole memory cell. With this technique, eight Boolean values can be stored in a 1 byte memory cell. However, the disadvantage of this technique is that to access the Boolean, we need to know the memory address and the position of the bit inside the byte, which is a number between 0 and 7. As an alternative, Booleans can be stored in an entire memory cell leaving the rest of bits untouched. In this case, all bits but one are wasted, but the access to the value is much faster. The following figure shows these two possibilities in a memory with 1 byte cells.
Two strategies to store Booleans
Review questions for 3.4.1 Storage for Booleans
3.4.2. Storage for characters
The storage required to store a character depends on the encoding scheme that is used. For example, in the case of ASCII, 8 bits are required to encode each character. In this case, if the size of the memory cells is one byte, one single cell is needed per character. A sequence of characters will then occupy consecutive cells in memory. The following figure shows how the sequence of characters “My first string.” encoded in ASCII is stored in memory in address 0x120.
String stored in memory
As you can see, every symbol, including the white space, has its own encoding. If the chosen encoding scheme was Unicode UTF-16, then each symbol would occupy two consecutive memory cells instead of one.
Review questions for 3.4.2 Storage for characters
3.4.3. Storage for integers and natural numbers
In order to store an arbitrary integer or natural value it is essential to know in advance the size of the representation. The most common sizes for these numbers are 2, 4, 8 or even 16 bytes. As in the case of the previous data structures, once these numbers are encoded using zeros and ones, they are stored using as many consecutive memory cells are needed. The operations with these numbers are so common that the size of these numbers is decided based on the circuits needed for their operations. For example, if an integer size of 32 bits (4 bytes) is chosen, it is likely that the processor has a circuit to perform addition and subtraction of numbers of this size.
But to store these numbers in memory we also need to know the order in which the bytes are arranged. They can be stored from least significant to most significant, or vice versa. These two possibilities are equally used by computer system designers and as a consequence today’s processors are divided along this feature. Let us consider the example of a system that manipulates integers represented by 32 bits (4 bytes). The binary representation of the number 70960543 using 2’s complement is 0x043AC59F. Assume that the number is stored at the memory address 0x00001000. The following figure shows the two options to store this number in a memory with 1 byte cells:
Two options to store an integer in memory
These two possibilities to store integers and naturals bigger than one byte are known as little endian (when the first byte stored is the least significant) and big endian (when the first byte stored is the most significant). Each computer system uses one of the two methods to store and manipulate all the integers and natural numbers. The problem with this duality appears when there are two processors in a system with different policies for this storage. In this situation, manipulating integers and naturals may require additional operations to swap the order in which the bytes are manipulated. The following figure shows how the same sequence of bytes may be interpreted as two different numbers when using little or big endian.
Interpretations of an integer in memory with little and big endian
There are numerous reasons in favour and against each policy, but none of them are enough to rule one better than the other. In the case of little endian, if the size of the representation needs to be extended, we only need to use extra memory cells at the end. If the number is stored using big endian, the bytes also need to be re-arranged.
Important
The little/big endian policy only applies when the data is stored in memory. In other words, if we are manipulating numbers in regular written notation, we use the convention that the byte at the right is the least significant. It is when this number is read or written to memory where the policy is needed.
Review questions for 3.4.3 Storage for integers and natural numbers
3.4.4. Storage for machine instructions
Storing instructions is simply done by using as many consecutive memory cells are required by the size of the instruction. Thus, a sequence of instructions requires as many bytes as the sum of the size of each of the instructions to be stored in memory. Depending on the length of the binary encoding of the instructions there are two types of processors, those with a fixed length for all the instructions, and those with variable instruction length. Accessing the instructions in a sequence for the case of a system using fixed instruction length is very easy as the next instruction is a fixed number of bytes away from the previous one.
If the system uses variable instruction length, the address of the next instruction in a sequence needs to be deducted from the address of the current instruction and its size. This is precisely what is done by the processor while executing a program. It first obtains one instruction from memory at a specific address. Interprets its content, deduces its size, and this size is then added to the address of the instruction to obtain the address of the following instruction in the sequence. The following figure shows an example of how to store these two instruction formats.
Storage for fixed and variable length format
When storing instructions there is no need to make the distinction between little and big endian because in this encoding there is no such thing as a most significant byte in the instruction encoding. The policy used when writing the binary encoding of one instruction is to write the bytes in the order in which they are stored in memory.
Review questions for 3.4.4. Storage for machine instructions
3.4.5. Size of the read and write operations in memory
Let us consider the case of a memory chip with cells storing 1 byte each. Even though each memory address refers to a single cell, when a memory chip is used as part of a computer system, the time it takes to read or write a value is much larger than the speed of the processor. In other words, every time an operation is required from memory, the overall system is delayed waiting for the memory chip to finish it, thereby becoming a bottleneck for the overall system performance.
Designers have come up with a huge number of design decisions and techniques included in the architecture of a processor that reduce this delay. One of the most effective techniques is to perform read and write operations for several cells at the same time. The memory still maintains its structure and the possibility of addressing each cell individually, however, some systems allow the read and write operations to be done in blocks of consecutive memory cells. This technique based on the observation that when reading data from memory, most of the time several consecutive bytes are needed (think, for example, when reading an integer encoded with 4 bytes). The drawback of this technique is that there might be some operations that manipulate more cells than what is really required.
Most systems allow the memory operations to be performed in one single step for more than one byte. The objective is to be able to execute this operation in the same time that it takes to write a single byte. This can be done by combining multiple memory chips or modules to behave as a regular memory. For example, let us consider the case in which we want a memory with 1 byte cells, 4 Gigabyte size (therefore with addresses encoded with 32 bits), and that allows operations over four bytes simultaneously. The example can be generalised with any cell group containing any power of two cells. The solution consists on using four memory chips connected in parallel, so each takes care of the operation for one of the four bytes. The resulting memory has the cell with address 0 stored in the first chip, the address 1 in the second chip, third address in the third chip, fourth address in the fourth chip, fifth address again in the first chip and so on.
With this scheme, and if we number the modules from 0 to 3, the cell with memory address in position p is stored in the module number
p % 4 where
% represents the remainder of the integer division. With this distribution in which four consecutive cells are stored in different modules, a read or write operation over four consecutive cells can be carried out in the time it takes one module to perform that operation. This is because all of the modules are working in parallel. For example, if each memory module takes 10 milliseconds to perform an operation, the time to read or write four consecutive cells (one on each module) will also take 10 milliseconds. If, on the other hand, all cells are in the same module, the operation would take 40 milliseconds (10 milliseconds for each of the four operations). The only requirement for this scheme to work is that the blocks of four cells have to be aligned with memory addresses that are multiple of 4. In other words, the cells in address 0, 1, 2 and 3 can be returned in the time it takes one module to perform the operation. This does not apply if we require the addresses 2, 3, 4 and 5, because, although they are in consecutive addresses, they are not part of the same block of four cells.
Access to memory in blocks of four bytes
Each memory module receives the most significant 30 bits of the 32 address bits. This is because the operation is performed over a block of four consecutive cells. The address is obtained then by dropping the two least significant bits of the address. (As we are looking at groups of four cells, we can divide the address by four which, in binary, means dropping the two least significant bits.) Each module then provides one of the bytes in the group. With this configuration, four bytes are read or written in the time it takes one module to execute the operation, as all four of them work in parallel. With this technique, even though internally there are four memory blocks, the complete circuit behaves as a 4 Gigabyte, 1 byte per cell, regular memory.
What happens if the processor wants to access to four consecutive bytes with an address that is not a multiple of four? In this case, the scheme previously describe does not work anymore, because the bytes will not be included in the same block of four bytes. These type of memory requests are called unaligned memory operations, and require the memory to perform more than one operation to manipulate the requested information. For example, if the processor wants to read the four bytes in addresses 43, 44, 45 and 46, by dividing the address by four we can determine that byte 43 is in one four byte block, while bytes 44, 45 and 46 are in the next four-byte block. The memory would then access the first block (with address 40), take only the last byte, and then access the block in address 44 and discard the last byte (with address 47).
Two memory accesses to obtain 4 consecutive bytes in two blocks
3.5. Storing an Array
Programs executed in computer system use complex data structures made out of combinations of basic data types. An example of these structures are arrays or tables. A table is a set of data elements, each of them can be used by a natural number which is called the index. In Java, all arrays have their first element at index zero, second element at index 1, etc. The last element of the table is at the index equal to the number of elements minus one. In most of the high level programming languages, the syntax to access elements in a table using an index is the name of the table followed by the index in square brackets, i.e. table[index]. How is this data structured stored in RAM?
As in the case of basic data, the strategy is similar, use consecutive memory positions to store all the elements. If a table contains elements, and each of them requires
bytes, the table requires at least
bytes. If the elements in the table are stored starting from the generic address
and each element occupies
bytes, the address of the element in the position
of the table is computed with the formula
The following figure shows how this equation provides the address of each element.
Address of any element in an array or table
Let us consider a table of four integers (encoded each with 4 bytes) stored in memory starting in position 0x100 with the following values (in the order in which they are in the table): 0x34AF89C4, 0x583B7AF1, 0x97FA7C7E, 0x14C8B9A0. The next figure shows how these numbers are stored in memory in a system using the little endian policy.
Example of how an array of four integers (encoded with 32 bits) is stored
But in order to manipulate data arrays, it is not enough to store the elements in consecutive positions. Suppose you have a table of integers stored in memory and you have to obtain the sum of all its elements. You would write code containing a loop to traverse all the elements in the table and accumulate its sum in an auxiliary variable. But, how do you know that you have reached the last element? Most operations over tables require to know its number of elements.
There are two techniques to know the number of elements in a table when stored in memory. The first one consists on placing a special value which is not used for any other purpose but to mark the end of the table. This is the technique used when storing a table of characters (or a string). Each element in the array contains a character, and the last element of the table is followed by an extra special value which does not correspond with any other valid value. In the case of the characters, that value is zero. In other words, when encoding characters, there is one extra symbol that is included in the encoding scheme, and is used to mark the end of a sequence. With this technique, if a sequence of characters needs to be traversed, we need to check that the element that we are currently processing is not the end of sequence character.
But this technique only works when there is a special code for the end of sequence. It does not work for the case of integers or naturals if they are encoded using base 2 or 2’s complement. In both encoding schemes all values are valid numbers, and therefore there is no spare encoding for the end of sequence. How do we know the size of a table in this case? The second technique is to store the size of the array in another memory location as an additional natural number. With this solution, if the table needs to be traversed, the number of elements must be first obtained from this memory location, and then used it to stop the traversal at the right location. Both techniques, the mark at the end of the table, and storing the size in an additional variable are used internally by the compilers to translate high level code to machine code.
Review questions for 3.5. Storing an Array
3.5.1. How tables are stored in Java
The high level programming language Java guarantees that any access to an element in a table is always done with an index within the bounds of the table. If a table with nnnelements is defined in Java, every access with an index with value iii is verified that satisfies the following equation
But the actual check that the index satisfies this equation can only be done while the program is executing. Imagine an access to a table in Java with the expression table[expression] where expression is a variable that captures some sophisticated calculation returning an integer. When can be guaranteed that the access to the element is correct? The solution consists on making this check while the program is running and right before the access is performed. In other words, before accessing the element, the program executes some additional instructions to verify that the previous equation is satisfied for the value of expression. If the equation is not satisfied, an exception is raise of the type ArrayIndexOutOfBounds.
The technique used by the Java language to implement this mechanism is to store the size of the table in the first memory positions of the table. After this number, all the elements of the table are then stored in consecutive positions. The following figure shows how a table of six integers (encoded with 32 bits) are stored with the little endian policy starting at the memory address 0x100.
A Java array of six integers stored in memory
As you can see, when computing the address of any element in the table, the four bytes that are used to store the size must be taken into account. Thus, in a Java program, before accessing an element in position in a table with elements each of size
bytes stored starting at position
, the program performs the following operations:
- Obtain the integer
stored in position
- Check that
. If not satisfied, raise exception.
- Check that
. If not satisfied, raise exception.
- Calculate the address of the element as
.
.6. Storing memory addresses
Assume that we have a computer system with 4 Gigabytes of memory and therefore the addresses are encoded with 32 bits (2 32 = 4 ∗ 2 30 = 4 G i g a b y t e s). As we said before, memory addresses are in fact natural numbers (positive numbers starting at zero). In this system, the addresses are the numbers in the range
[ 0 , 2 32 − 1 ]. But this number itself can also be stored in memory. In other words, we can store in memory the binary representation of a memory address in four consecutive cells of 1 byte.
From this point of view, a memory address can be considered either as the unique identifier of a memory cell, but also as a natural number that can be manipulated normally. Let us now assume that in the memory address with number 0x00000100 we stored the 32 bit integer with value 0x0153F2AB. Now, in the address 0x00000200 we must store the address of this value. This can be easily done by storing the value 0x00000100 in the address 0x00000200 using four consecutive bytes, or specifically, the cells with addresses from 0x200 to 0x203. We will use the little endian policy to store that number. The following figure shows the data stored in memory for these two addresses.
Memory address 0x00000100 stored as a regular natural number (Little Endian)
After storing the address of a number in position 0x00000200, is it possible to obtain with that information the value 0x0153F2AB? The answer is yes, but not in an straightforward way. We first have to obtain the number stored in the address 0x00000200, use that data now as the address of another number and access that new value. This type of access is called an indirection, that is, rather than accessing directly the number 0x0153F2AB, we first obtained another number from a different address, that happened to be the address of the number. Another way of looking at it is to consider the value stored in position 0x00000200 as indirectly pointing to the value 0x0153F2AB. The following figure shows this situation.
Indirection: memory address contains the memory address of another value
The indirection technique can be chained an arbitrary number of times. The address of the position that contains the address of the data can itself be stored in memory. In this case, to access the final value, two indirections are required instead of one. It is then possible to store a chain of addresses each of them pointing to the next until eventually reaching a specific value. The following figure shows an example of a triple indirection. Position 0x00000100 contains the memory address of the memory address of the memory address of the value.
Triple indirection to access a value
This technique shows how the memory in a computer system is nothing more than a table with cells storing bytes. The interpretation of that information is not contained in memory but is contained in the programs that manipulate this data. The previous figure shows how 16 bytes are stored in memory with different values. However, the information that position 0x00000400 contains the address of the address of the address of an integer is part of the context in which this data is being used.
Review questions for 3.6. Storing memory addresses
3.6.1. Examples of indirection
Although storing a memory address as a natural number in memory may not appear to be something useful, this technique is used very frequently by computer systems when executing the code written in high level languages.
Example
Storing a table of strings
Suppose that a program has a set of strings stored in several locations spread over memory. Although each string has its characters stored in consecutive memory locations, the strings are not next to each other. You would like to keep these strings sorted in alphabetical order, and for that purpose, you want to create an additional data structure that contains this information.
One possible solution would be to create a new table with duplicates of all the strings stored in consecutive memory locations but sorted in alphabetical order as required. However, the essential information is the order of the strings, and to store that, we are using duplicates, which is a waste of memory space.
An alternative solution is to use indirection. Instead of creating a table of strings we can create a table of the addresses of strings. In other words, this table, rather than having the strings stored in consecutive memory locations, it contains the addresses of these strings. Sorting the strings can be done by knowing that the elements in the table are the addresses of the strings. The following figure shows this technique in a system in which characters occupy one byte and memory addresses are encoded with 4 bytes.
Table of string addresses
Sorting the strings can be done without moving any of the characters in memory. The resulting table contains in each of its elements the address of a string, that is, the address of the first character of the string. The code to, for example, print the strings in order would traverse the table and print the content pointed to by each of the table elements.
Example
References in Java
The Java programming language uses indirection to access any element of an object. Suppose that you have defined a class with name Data itself containing an public integer field with name value. Suppose you execute the following portion of code in the main method:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public class Data {
int value;
public static void main(String[] args) {
Data obj1, obj2;
obj1 = new Data();
obj1.value = 1;
obj2 = obj1;
obj2.value = 2;
System.out.println(obj1.value);
return;
}
}
|
Which value does this program print in the screen? The code assigns the one number to the value field of the first object (i.e. assigns 1 to the value field of obj1), and a second number to the value field of the second object (2 to the value field of obj2). Then, the value of in the first object is printed, and the screen shows the second value (2!). The explanation for this behaviour is in the line obj2 = obj1. In Java, objects are manipulated using references. The variables with names obj1 and obj2 are not objects, but references that point to an object. In fact, in the previous code only one object is created by invoking the new function. obj1 is actually a reference pointing to the new object, and the assignment obj2 = obj1 assigns to obj2 the same reference contained in obj1 which points to the newly created object. After this statement, both references point to the same object, and this is the reason why the program prints the value assigned through obj2.
Internally, Java programs represent references as memory locations that contain another memory address, that of the object they refer to. Thus, whenever a reference is used in Java, there is an indirection being executed. The line obj2.value = 2 first accesses the information in obj2 which, as it is a reference, it is the address of the object, in which the assignment is taking place. The following figure shows how the information is managed in memory for this program.
Two Java references pointing to the same object
The object is created at an arbitrary position in memory (in the figure in 0x0256A1FB). In two additional memory locations the references obj1 and obj2 are stored. The first one receives its value after executing the call to the method new. The second reference gets the same value that is stored in obj1. From that point on, any changes to the object done through obj2 is visible through obj1.
Example
Double indirection with references in Java
References in Java are implemented in memory using indirection. But a class in Java may contain as one of its fields references to other objects. For example, if a second class Data2 is defined with a field with name c1 of class Data, the field is a reference to an object. Let us consider now the following program.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
public class Data2 {
Data c1;
public static void main(String[] args) {
Data2 obj2;
obj2 = new Data2();
obj2.c1 = new Data();
obj2.c1.value = 4;
return;
}
}
|
In this case, the reference obj2 points to an object of class Data2 which itself contains a reference to an object of class Data. The execution of the last line of code in the main method requires a double indirection. The value of the variable obj2 is the address of the object of class Data2, and once it is accessed, we need to extract its field c1. The value of this field is another reference and therefore contains the address of the object of class Data. A second indirection is then executed to access the field in that object and assign the value. The following figure shows the access to this field through the double indirection.
Accessing a field in a Java object through double indirection
3.7. Additional Exercises
- Design a memory for a computer system that offers the processor the possibility of accessing eight consecutive bytes in the time it takes to read a single byte. Use as many basic memory chips as you need. The design should specify the size of the buses and their internal structure.
- The memory of a computer system allows access to four consecutive bytes with a single operation as long as they are stored in an address that is a multiple of four. Two programs are executed in this processor with identical instructions that access an array of one million integers of 4 bytes each. The first program executes one million memory accesses to the memory area where there array is stored. The second program execute exactly double of those operations to access the same area. How is this possible?
- Suppose that a computer system allows operations in memory in groups of 32 bits (4 bytes). The following operations are executed over memory:
Write(0x100, 0x01234567) Write(0x101, 0x89ABCDEF) Write(0x102, 0xFFFFFFFF) Read(0x100)What is the result (4 bytes) of the last operation?