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 Operating
System System

Intermediate
Long-term
queue
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 Operating
System 8M System 8M
8M 2M
4M
8M
8M
8M
18M
8M

Fixed Partitions (equal-size or unequal size

 Variable-sized Partitions
Operating Operating OperatingOperating
System System System System

Process 1 Process 1Process 1

Process 2Process 2

Process 3

Process 1 in ProcessProcess
2 in 3 in
 Variable-sized Partitions
Operating Operating Operating Operating
System System System System

Process 1 Process 1 Process 2

Process 4 Process 4 Process 4

Process 3
Process 3 Process 3 Process 3

Process 4 in Process 3 Process 2

Process 2 swapped out swapped in
swapped out
 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
PhysicalPhysical
A Process address address
Logical 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

 Page0
13 13 of A
14 14 Page1
Process A of A
Process A
15 15 Page2
Page 0
Page 0 of A
Page 1
Page 1
Page 2 In In
16 Page 2 16
Page 3 Use Use
Page 3
In In
17 Use 17 Use
18 Process A 18 Page3
Page Table of A
In 13 In
19 Use 19 Use
14
20 15 20
18
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 = <frame number Y, relative address R>

 Frames

Page 1 of A

14
Page 1 of A An instruction

30 An instruction
Process A Page 2 of A
Page Table
15
13
14
15
18

Logical Physical
address 14 30
1 30 address
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
...
A(1) … A(99 ) K RES
RES = SUM(A,K)
...
END

FUNCTION SUM(V,N)
DIMENSION V(N)
SUM = 0
DO 10 I=1,N V (N) I
0 SUM = SUM + V(I)
RETURN
END

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 Stack m
Digits (integer n) : integer; pointer
var m : integer; n
begin
if n < 10 then return n Activation m
record 1 Stack
else begin pointer
m := n div 10; n
return n - m *10 + Digits ( m);
end; Activation in in
record 2
end;
begin The state of the The state of the
read (in); stack after return to
writeln(Digits(in )); stack after the
end. second call of the the main procedure
Digits function 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 compile-
time, 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 stack-
based memory management mechanism is not enough (though, the problem can
be solved by branching the stack at the moment when the process forks).