Last weeks lecture examined the role of
the Process Manager within the general model of an operating system.
We have considered a range of policies used by the Process Manager
to undertake its responsibilities. We defined differences between
a multi-user and a single user system. We examined the roles of
the Process Scheduler and the Job Schedulers and how they support
the Process Manager to provide 'controlled' access to the CPU
resource. We established that access to the CPU will be based
on a policy that will for example aim to provide fair, equal,
or prioritised access to the CPU. Finally we examined the problems
that can be experienced when attempting to shaft resources, in
particular we examined the four stages of deadlock.
The purpose of the Memory Manager
The memory manager (MM) has the job of allocating memory for each
job to be executed, and then reclaiming memory when a job is completed.
Basically programs and data are stored in this part of the computer
system. The MM will allocate memory to program jobs, whilst ensuring
that the programs in memory remain separate from one and other.
Memory management is critical to a system's performance. Performance
will depend on:-
o how much memory is available
o how memory allocation is optimised.
Modern memory management must allow for
multiple jobs and multiple users.
Functions of the Memory Manager
Ultimately, the memory manager must:
- allocate memory to jobs
- ensure available memory is used well
- track allocation of memory
- maximise memory allocation
- ensure efficient re-use of memory
- de-allocate memory when job is finished
- Amalgamate free memory
- allow for variations in re-use
- should be able to cope with overflow
- ensure a fair and efficient management process
In previous sections we have already met
four types of memory, each with particular properties:-
- Cache - very fast, small in size
- RAM - fast, large but limited
- Disk - slow but unlimited in size
This technique allows peripherals to gain direct access to the
main memory of the computer. When the device initiates Direct
Memory Access (DMA) the processor is compelled to stop all bus
activity - so allowing for higher data rates. It is an I/O technique
that allows a control unit to access the main memory directly
and so transfer the data without intervention from the CPU.
This technique is used for relocating the contents of the main
memory onto the disk or a backing store. It is not 'real memory'.
The technique is used when the sum of the total memory required
by all the programs exceeds the physical availability.
Single block systems
Here a single job is placed into the main memory at one time.
The entire job is loaded and all memory is allocated to the 'one'
job. If a job is too large, then it cannot be loaded. The memory
manager will keep track of the job from start to the end address.
Advantages include the following factors:-
- A simple memory management system.
- The system is easier to understand and implement.
- It is more suited to PCs; no partition intrusions problems are
The disadvantages include:
- Larger amounts of CPU can be wasted through swapping jobs in
and out of memory.
- The CPU is idle during any I/O steps.
- In the same way, peripheral devices are idle when program is
At system initialization the memory is divided
into fixed partitions of various sizes according to typical programming
needs of users. Partition sizes are static once system powered
up. They can be changed on complete shut-down of system, power-up
and reconfiguration of system.
Fixed partitioning will:-
- allow for multiple jobs in memory
- split memory into fixed sized partitions - remaining in contiguous
- place one job (only) in each partition
- protect jobs from jobs running in other partitions - partition
intrusion is prevented
- allocate jobs according to available memory as assigned by the
MM using a special table which is known as the memory allocation
The Memory Allocation Table provides details
- partition size (for example in kilobits)
- memory address (location)
- access to (job number)
- partition status (free/busy)
Here the MM will track which partition is
in use, which job has the partition and the start and end address
of a memory allocation.
The main advantage of fixed partitioning
schemes is that they permit:-
- memory protection.
The disadvantages include:
- inappropriate partition sizing prevents some jobs from running
- internal fragmentation.
The effect of fragmentation is discussed
From the available jobs in the Job queue, the jobs are allocated
memory space according to the first available partition that can
accommodates the job size. Even though Job 3 requires only 30k
(and there is 70k available in partition 1) it cannot run.
Careful consideration must be given to setting
partitioning sizes; there is a need to reach some 'balance'. If
for example, most partitions are too small, then the larger jobs
will have a longer turnaround whilst waiting for the only partition
'big enough'. If however, the partitions are too big , then memory
is wasted and any unused memory cannot be allocated to another
job. Reaching this happy balance will depend on the types of jobs
processed and of course the agreed expected processing times.
Figure 1: Internal fragmentation
Dynamic partitioning is similar to fixed partitions, however the
partition sizes are dynamic (they change). A partition table of
use is also maintained and memory is still kept in contiguous
blocks. Here, jobs are given as much memory as they require for
processing. The jobs are placed into memory according to a predetermined
policy, for example 'First Come First Served' (FCFS). Dynamic
partitioning is more efficient, but external fragmentation and
reallocation issues have to be addressed.
Reallocatable dynamic partition
Under reallocatable dynamic partitioning, the memory allocation
scheme is responsible for 'bringing together' the available memory
from the empty partitions and external fragmentation. Blocks are
compacted together to make one block of memory large enough to
accommodate some or all of the jobs waiting for memory.
Fragmentation occurs when processes are continually swapped in
and out of memory. The processes are released into a fixed number
of randomly sized partitions. As a result swapping out will leave
a number of different sized partitions. In other words, the dynamic
allocation of memory creates unusable fragments of memory between
allocated blocks of memory. When swapping in the process needs
to search through all the different sized partitions to find a
fit. The partition is rarely filled by a process. The space between
the used partition and the start position of the next partition
is called external fragmentation. There has to be a plan in place
to collect all the external fragmentation allowing for future
reallocation. Amalgamation can be considered here.
Where the total free memory space is greater
than the program size, and no suitably sized contiguous space
is available to accommodate program, then amalgamation of free
space is required. Amalgamation aims to anticipate and provide
for the biggest area possible. It will collect all free area,
including areas adjacent to another free area, and areas that
are isolated from all other areas.
The MM will attempt to relocate the free areas using some form
of allocation scheme. Schemes are based on algorithms which assume
that the memory manager keeps the following two lists:-
1. Free memory blocks.
2. Busy memory blocks.
Some allocation schemes are described as follows:-
Fastest (or First Fit) memory allocation
This scheme searches from the beginning of the free block list.
It selects the first block of memory large enough to meet requirements
Most Efficient (or Best Fit) memory allocation
This scheme considers all the free memory blocks. It allocates
the block that results in the least amount of wasted space. One
problem with 'Best Fit' is the need to completely search the table
to find the best fit.
Comparing first-fit and best-fit
The first fit will run through table of free space and allocate
to the first space that fits. The best fit will run through table
and allocate to space that results in least amount of wastage.
Which method is best? There is no straightforward answer - it
must depend on the job mix. Recent technological advancements
have resulted in faster access times'. As a result the scheme
that best saves valuable resources, such as memory space, might
be considered better.
Virtual memory derived from days when computers had very small
memories. It was necessary to deal with programs larger than memory.
Most of the program would be stored on secondary memory devices
and program chunks swapped in and out of memory. Chunks were originally
called 'overlays'. Swapping was originally the responsibility
of the programmer. Now swapping is automated using overlay swapping
that is invisible to the programmer. Memory swapping became known
as virtual memory. The virtual memory exists on the disk rather
than in main memory. The processor will address a 'piece' of its
physical address space (on disk). The located 'piece' (or page)
is then transferred to a page frame in main memory. Virtual memory
is then implemented through the use of a page table.
There are three approaches to the use of
3. Combined segmentation and paging.
Paging allows for the use of continuous,
one-dimensional address space, that is one memory cell after another.
Here, jobs are divided into fixed sized blocks called pages. The
scheme then attempts to match the job size according to the available
memory. It will allocate as many pages as required for a job.
The page allocation does not have to be contiguous. Example page
sizes (which are fixed by the computer) might be in the range
of 128 to 4096 memory locations. In other words the virtual memory
exists on the disk. The processor will address a 'piece' of the
disk's physical address space. The located pieces are transferred
to a page in the memory. The virtual memory is made possible through
the use of a paging table. Paging allows a job to load even if
there is not enough memory. We have removed the restriction on
the maximum program size. Program writers can now consider the
memory space as infinite. This infinite RAM does not exist - it
The main advantages can be summarized as
- Improved efficiency.
- The need for compacting is eliminated.
- Internal fragmentation is reduced.
The main disadvantages include:
- Increased HIW and 5/W overheads.
- Internal fragmentation may occur on the last page.
Page allocation tracking
Many allocation methods are used. Two are
1. Bit maps
Here a bit array is kept for all pages in each job. If a page
is currently being used the bit is set 'on'. A single bit indicates
if the virtual page is currently in main memory.
2. Linked lists
Here a marker is placed at the end of each page, from where the
address of next page is given.
Up to now we have loaded the whole job into memory. In practice
this is not required. Not all parts of a job run at the same time.
Demand paging loads only part of a job into RAM. The rest is loaded
into pages on the disk. There is a Page File on the disk. As the
job runs pages are swapped in and out of RAM.
Page removal policy
A policy needs to exist to remove faulty pages or to bring in
a new page. Several methods have been developed for removing pages,
two methods include:-
1. First In First Out (FIFO)
This policy removes the page that has been in RAM the longest.
2. Least Recently Used (LRU)
This removes the page that has the least amount of recent activity
Many processors split job memory into segments,
for example program code, data and stack. These segments can have
a set of independent address spaces. Segments are swapped in and
out of main memory in the same fashion as pages. One essential
difference is that pages are all the of the same size and segments
are not. A segment can actually change size during execution of
a program. Also, different segments can be protected in different
ways, for example when dealing with data or program code.
This section has examined the typical role of the Memory Manager
within the computer system. We have reviewed a range of memory
components and techniques used by the memory manager, ranging
from DMA to virtual memory and fixed partitioning through to dynamic
partitioning. Finally we have explored some of the problems associated
with partitioning and have examined some techniques used to overcome