Memory Management

Problems of memory management : The greatest problem of memory management is that memory is finite, and that is why one should take into account the possibility of its exhaustion. Of course, this problem gradually loses importance due to constant reduction of hardware prices, but it will never completely disappear. Another problem appears if programming language provides explicit mechanism of memory management (like malloc/free in C or new/delete in C++). In this case, a compiler cannot guarantee correctness of compiled programs, and the programmer becomes responsible for correct memory operations. Unfortunately, people are far less reliable, prone to make errors, tend to repeat the same errors, and even ignore available safe mechanisms. Therefore, explicit memory management causes many errors, and that, in turn, leads to obligatory laborious debugging and causes great inconvenience for a programmer. Errors related to incorrect memory management are particularly difficult because they are abrupt. They may show themselves up only in very rare cases, may depend on the order of execution of previous statements, and so, they are harder to debug than errors in program algorithms. For example, a typical error is the allocation of a resource only in one branch of a conditional statement while the resource is used or freed even if this branch is not executed. However, in some cases it is difficult to do without programmer’s intervention. For instance, releasing a resource associated with some external object (e.g., files on disk, records from database, network connections etc) usually requires explicit actions. In that case, freeing the memory allocated for the corresponding variable in program accomplishes the release task only partially, because a file or a record from a database would be still unavailable for other applications. From the programmer’s viewpoint, memory is freed immediately after execution of explicit freeing statement (free/delete) or when the “lifetime” of the last variable referencing this memory comes to an end. These operations, making the variable programmatically unavailable, are called the freeing of memory. However, from the compilers developer viewpoint, all work only begins at that moment. In case of explicit memory freeing, things seem to be more or less clear, though this mechanism still presents some troubles for a programmer as it was described above. Mostly, variables are freed automatically anyway (at the end of a block, a procedure etc). Hence, it is necessary to track the moment when the memory is no longer used, i.e., make sure that nobody else uses the given memory block. Sometimes it is a non-trivial task due to the

possibility of existence of several program objects referencing the memory block. In this case, one can say that aliasing takes place. The simplest sample of aliasing is the situation when there are two pointers referencing the same address. Another example is passing an array to a procedure. Generally, tracking aliasing is resource-consuming and very difficult to implement. There is a need to return the freed memory to the system, in other words, to utilize it. Note that it is difficult to predict when freeing and utilization will be performed. Moreover, in most programming languages a programmer cannot force utilization of a specified object if it was allocated automatically (though there is such possibility for large objects in C#). Obviously, memory utilization is complicated by the problems of detection of aliases for the block of memory being freed. On the next slide we consider some problems that can be caused by different errors in this analysis.

Static and dynamic memory allocation : A compiler’s designer should make a distinction between two important classes of information about a program: • Static information, i.e. information available at compile-time • Dynamic information, i.e. information that is unavailable at compile-time but becomes available at run-time For instance, the values of constants in languages with strict type system are known at compile-time while the values of variables are generally known at run-time only. At compile time, we know a number of branches in a switch statement, but the branch, which is actually executed, can be determined only at run-time. The division of information into static and dynamic enables us to choose a memory allocation method for the given variable, structure or procedure. For example, the size of memory for scalar variables can be calculated and memory can be allocated at compile-time, but the memory of variable size requested by the user should be allocated at run-time. Obviously, static memory allocation is preferable and “cheaper”. “Boundary” cases like memory allocation for arrays are of special interest. The fact is that the amount of memory for fixed-size arrays can be statically computed for the most of modern programming languages. Nevertheless, the allocation for arrays is often deferred

until the run-time. The allocation deferment could be reasonable for languages that allow the declaration of dynamic arrays, i.e. arrays which boundaries are unknown at compile-time. C# all are languages of such kind. Memory allocation deferment enables using the same algorithm for all types of arrays. On the contrary, in Pascal and С/С++ languages, arrays that are allocated automatically can be always allocated at compile-time. Note that when you write int[] n = new int[3]; in C++ you have to manage the array memory “manually”, e.g., free it and so on. The stages of memory management As we already mentioned above, all actions performed by memory management mechanisms can be divided into standard stages. We shall emphasize three major stages: • Initial memory allocation • Memory utilization • Compaction and reuse During initial memory allocation, it is necessary to mark all memory either as free or as used. Besides, there is a need to keep track of free memory. Furthermore, the system should locate blocks of memory that are no longer used and utilize these blocks for subsequent reuse. There are different methods of utilization: simple (when freed blocks are adjacent and continuous) or complex (when freed blocks are located in random order or in the different memory areas). Finally, the memory should be reused. In order to achieve this, memory compacting mechanisms, which create large memory blocks from a number of little ones, can be applied. The following three basic methods of memory management (written in increasing order of implementation complexity) should be mentioned: • Static memory allocation • Stack-based memory allocation • Heap-based memory allocation Earlier, many programming languages were designed with an assumption that only one certain memory management mechanism out of these three is used. Today most of programming languages require a compiler to use all memory management mechanisms. Usually, it is assumed that the “cheapest” suitable method is used in every particular case.

 Static memory allocation It is the simplest method of memory management. It was employed widely enough at the earliest stage of programming languages evolution. If a language could be implemented using only static memory allocation, the maximum efficiency can be achieved since it is unnecessary to perform run-time memory allocations, deallocations, different checks, and other frequent and time-consuming operations. It is interesting that the efficiency of static allocation was probably the reason for survival of one of the earliest programming languages, Fortran. In Fortran's problem domain (mathematical and other scientific computations) the execution speed was the most important parameter and, on average, programs produced by Fortran compilers were more efficient than programs in a language with more complicated memory management mechanisms. As time went by, the efficiency of programs became less important that the convenience of programming, but huge amount of working code has already been developed to that time. That is why Fortran even today is more alive than dead. As mentioned above, a desire to reduce the memory allocation issue to static memory allocation enforces developers to abandon many convenient language constructions, for example: recursive procedures (since it is unknown how many times the procedure is called, and it is impossible to distinguish recursive activations), arrays with dynamic bounds, and nested functions/procedures. Summarizing, we can say that only simple variables, structures and fixed-size arrays are at the disposal of a programmer. This poor set is exactly the set of data types provided by Fortran and Cobol. Today it may seem astonishing, but people contrived to create large industrial systems having that limited set of constructions. However, there are cases when this set is not convenient, for example, it is difficult to imagine writing a compiler in Cobol. Stack-based memory management Since static memory allocation overly restricts a programmer, designers of programming languages have to employ more complicated means of memory management that work at run-time. The simplest among them is the stack-based memory management. The idea is that memory for variables declared in a block or a procedure is allocated on the top of a special stack at the time of entering the given block or procedure. On leaving the block, the memory is freed not “discordantly”, but from the stack top only. Obviously, with this approach the tasks of utilization and reuse become trivial, while the problem of compaction does not exist at all.

Under such conditions all values from the block or procedure combine in one part of the stack called a frame. For memory management purposes we need two pointers, the stack pointer referencing the first free cell, and the frame pointer keeping the address of the beginning of the frame (frame pointer is used when control flow leaves a block or a procedure). Stack-based memory management is especially advantageous for languages with strict nesting of procedure entries and exits. In addition, all structures are required to have fixed size, to be created only on entering a procedure or a block, and to be destroyed on leaving the procedure or the block. All information necessary to functioning of the given procedure or function can be combined in the so-called activation record, which completely identifies the given instance (or activation) of the procedure. In that case, stack-based memory management is enough for all data elements used in a program. In such a way, we have succeeded in the dismissal of restrictions on nested procedures and recursive calls, as compared to the static memory allocation. However, as before, we require all variables to be of fixed size. Instead, on leaving a procedure, a compiler exactly knows the size of the memory block to free (hence, it knows how many memory cells must be popped from the stack top). Heap management Finally, the last memory management mechanism is heap management. Heap management is used for all data structures, which are not suitable for static or stack memory allocation. The heap is needed in those cases when allocation and deallocation of memory can happen at arbitrary moments. Moreover, most modern object-oriented languages cannot do without dynamic construction and destruction of objects. So for good or for the bad the heap management became one of the basic memory management mechanisms in modern systems. In the presence of heap management the tasks of utilization and compaction of memory become very difficult: the facts of releasing memory are not always irrefutable, the order of releasing is unpredictable, and memory intended for allocating new objects usually resembles a sieve. The garbage collection mechanism is usually responsible for solution of these problems. During garbage collection the allocated memory is scanned to locate unused blocks, and freed memory is passed for reuse. For the first time garbage collection was used in LISP translators, in which it is almost the only mechanism of memory management. Perhaps, the most critical problem of heap management is tracking active elements in memory: as soon as a need for freeing extra memory arises, the garbage collection process should utilize all memory blocks that are no longer used. There are several methods to

determine whether the given block is currently used in the program. The most widespread methods are reference counting and different algorithms of memory marking.

Memory Management Functions: Monitor Basic form of Operating System, designed to deal with special task like I/O and other control routines Input/Output Control System (IOCS) Contains programs to control devices, handle interrupts, block and unblock data, transfer data between I/O device and primary storage. The major portion of monitor is IOCS Bootstrap Loader Enable a computer to load the operating system into memory when the system is power up. Booting The process of enabling the bootstrap loader, then followed by the operating system. Rebooting refer to reset of the computer system by restarting the booting process to overcome certain unexpected situations. Swapping A process needs to be in memory to be executed, but can be swapped temporarily out of memory to a backing store (disk), then brought back into memory for continued execution. Single User Monitor (OS) Systems The operating system normally is loaded into the low end of memory. When user process request I/O service, a call is made to the IOCS service routines within the monitor, on completion, control is return back to user.

Memory management cases : 1. Swapping 2. Partitioning 3. Paging 4. Virtual memory 1. Swapping • • • •

Short-term queue: processes in ready state I/O queues: processes not ready to use the processor All these processes are in main memory Because the processor is much faster than I/O devices, it is common for all the processes in main memory to be waiting on I/O. • The processor will be idle, because no processors are ready. • Swapping can make the processor more occupied Swap a non-ready process out of the main memory and swap a ready process in. •

The out process goes to disk, and joins in an intermediate queue.

• The in process may come from:  The long-term queue (a new process, in ready state)  The intermediate queue (a process which has just finished an I/O operation)

Operating System Long-term queue

Operating System Intermediate

queue

Long-term queue

No swapping

With swapping

Points to notice: • Swapping is an I/O operation, so could be slow. • Fortunately, disk I/O is the fastest among all I/O devices. • The total memory required by all active processors may exceed the size of the main memory. E.g. the processes in the main memory have almost used up the memory, and now a big process in the intermediate queue is ready. But this process cannot be swapped in. 2. Partitions How should memory be allocated to the processes? Partitions: each process is given a portion of the memory • Fixed partitions • Variable-size partitions

Operating System 8M 8M 8M

Operating System 8M 2M 4M 8M

8M 8M

18M

Fixed Partitions (equal-size or unequal size

Variable-sized Partitions Operating System

Operating System

Process 1

OperatingOperating System System

Process 1Process 1

Process 2Process 2

Process 3

Process 1 in

ProcessProcess 2 in 3 in

Variable-sized Partitions Operating System

Process 1

Operating System

Operating Operating System System

Process 1

Process 2

Process 4

Process 4 Process 4

Process 3

Process 3

Process 3

Process 2 swapped out

Process 4 in

Process 3

Process 3 Process 2 swapped out swapped in

Fixed Partitions: • A process may not use all the partition • So, waste of main memory Variable-sized partitions: • Allocate the right amount of memory for each process • Seems to be more efficient • But there are 'holes' in the main memory • So, needs compaction to put all the processes in main memory together, to remove 'holes'. • But compaction is time-consuming Logical address Vs. Physical address • When a process is swapped out and later on swapped in, it may not be placed in the same place as before, e.g. process 2 in the above figure. • So the instructions and data in a process (program) may have different addresses each time the process is swapped in. How does the processor keep track of the changing addresses of the relevant instructions and data? Each instruction or data has a logical address within a process.

Logical address

An instruction A process

Each process has a base address (starting address) in the main memory, when it is loaded into memory:

Base address

A Process

Main Memory

Physical address (of instruction/data = Logical address (of instruction/data) + Base address (of the process)

Base address Logical address

A Process

PhysicalPhysical address address

An instruction

Main Memory Main Memory CPU needs to know the physical addresses of instructions and data in the memory in order to fetch the instructions/data. Physical addresses are calculated as above.

3. Paging - more efficient use of memory •

Divide a program into many small fixed-sized chunks (pages).

•

Divide the main memory into many small fixed-sized chunks (frames)

• A frame can store a page • A program is stored in many frames

Process A Page 0 Page 1 Page 2 Page 3

13

13

Page0 of A

14

14

Page1 of A

15

Page2 of A

16

In Use

17

In Use

18

Page3 of A

19

In Use

Process A

15 16

In Use

17

In Use Process A Page Table

18 19 20

Page 0 Page 1 Page 2 Page 3

In Use

13 14 15 18

20

Points to Note: • When loading a program, all the pages will be stored in some free frames • Those frames may not be continuous • There is a page table for each process (program)  showing the frame numbers for each page • Logical vs. physical address Logical address vs. Physical address Logical address of an instruction = <page number X, relative address (in that page) R> Page X stored in Frame Y Physical address of an instruction =

Frames Page 1 of A 14 An instruction

Page 1 of A 30

An instruction Process A Page Table

Page 2 of A

13 14 15 18 Logical address

1

30

Physical address

15

14

30

4. Demand Paging & Virtual Memory Simple Paging: • load all the pages of a program into memory • more efficient use of memory than partitioning  only the last page may not occupy a whole frame Demand Paging: • load a page only when it is required • need not to swap in or out unused pages • more efficient use of memory Virtual Memory • It is possible for a process to be larger than all of main memory. • This is because not all pages of the process need to be in main memory. • The programmer needs not to know how much main memory is available. • The memory size he is concerned is the size of the disk storage, where his programs are stored. • This much larger memory is called Virtual Memory.

The examples of memory management allocation: 1- The example of static memory allocation

DIMENSION INTEGER A (99) 10 READ (1,5) K 5 FORMAT (I2) IF (K .EQ . 0) GO TO 30 ... RES = SUM(A,K) ... END FUNCTION SUM(V,N) DIMENSION V(N) SUM = 0 DO 10 I=1,N 0 SUM = SUM + V(I) RETURN END

A(1)

…

A(99 )

V (N)

K

RES

I

Let us consider a small example written in Fortran. In Fortran all memory is allocated statically, and at run-time only values of variables and array elements are changed. In order to achieve this, each function (subprogram) is compiled in a statically allocated memory area, which contains the machine code itself and related data. The interaction among subprograms is implemented through blocks of data, which are common for several subprograms (COMMON), or through argument passing and transferring control in non-recursive calls. All data have one of the five predefined types; memory used by variables is never released.

All these restrictions permit compiler to use the simplest way of data representation in memory, a single-dimensional array of variables. The main function is compiled independently from SUM function; thereby, two different address spaces are created for these functions. Compiled subprograms are linked only at run-time. It is interesting that Fortran has a specific predefined memory mapping for representation of multi-dimensional arrays in memory. The order of elements corresponds to the following layout: the first column of a multidimensional array occupies a continuous block of memory, the second column occupies a block, which lies just after the memory occupied by the first column, and so on. The layout differs from common layouts when the first row goes first, then the second row and so on. Another Fortran feature is more troublesome: since no run-time checks are performed, serious errors cannot be traced (say, violation of array bounds or extraction of a real value in an integer variable imposed on the same memory with the EQUIVALENCE statement). Memory management for nearly all languages includes static constituent, since static allocation does not require any run-time overheads. Constants, variables and fixed-size arrays can be allocated statically. But in more complicated programming languages, we will need values that will become known only at run-time for the memory allocation needs.

2-The example of stack-based memory management

var in : integer; function Digits (integer n) : integer; var m : integer; begin if n < 10 then return n else begin m := n div 10; return n - m *10 + Digits end; end; begin read (in); writeln(Digits(in end.

));

( m);

Stack pointer

m

Activation record 1

m

Activation record 2

in

n

n

The state of the stack after the second call of the Digits function

Stack pointer

in

The state of the stack after return to the main procedure of the program

A simple example in Pascal on the slide illustrates the stack-based memory management. This program uses the recursive function Digits to count the sum of digits of a number. We should be able to distinguish different instances of Digits function, which can be achieved by creating independent activation record for each instance. The first picture shows the moment after the first recursive call. After return to the main program, all variables that are no longer used are removed from the stack and the stack pointer shifts downwards (this moment is shown on the second picture). Note that each frame allocates all statically known variables in the beginning of each frame, while other variables are consequently allocated above the statically known part of frame. Thus, though addresses of frames are unknown at compiletime, we can at least calculate offsets from the beginning of frames statically. Another approach to the solution of the problem of allocation of dynamic information is concerned with allocating in the stack frame data with the size known at compile-time and allocating in the stack frame pointers to the dynamic part of the stack frame, or the heap. Another notable issue concerns parallelism: under conditions of parallelism, order of returns from procedures cannot be guaranteed, and so, the purely stackbased memory management mechanism is not enough (though, the problem can be solved by branching the stack at the moment when the process forks).