Chapter Ten

Storage Management (Memory)

In Chapter 2, we mentioned the physical memory, namely. DRAM, Video RAM and also cache memory. We also touched the virtual memory system and its operation. In this chapter, we will look at detailed memory strategies including Fetch (when to obtain page from disk), Place (where to place) and Replace (which page to disk). We also discussed virtual and non-virtual memory system. Upon completion of this module, you should understand

Memory storage
Different memory strategy
Different placement scheme

memory storage

Storage (Memory) management determines how a storage organization should perform under different policies. The following questions are usually raised to determine the memory strategy.

When do we get a new program to place in memory?
Where in the main memory do we place the next program to be run?
If the main memory is full, which program do we displace?

If we can answer the above questions properly, we have already come up a well-defined memory management scheme.

Storage Hierarchy

The types of storage in a computer system include:

Cache memory
Main memory, e.g. RAM, ROM
Secondary memory, e.g. Disk, Tape, Drum and CD-ROM

The characteristics are:

Programs to be executed must reside in the main memory (real or physical memory)
Secondary storage is less costly than main storage and have much greater capacity and is used to store the programme (Laser disk has capacity up to 600M)
Main memory may be accessed much faster than secondary storage.
Cache memory is a high-speed storage which is much faster than the main memory and is relatively expensive than main memory.
frequently used programs is recommended reside in cache memory to speed up operation as this will increase performance.

In order to satisfy the above criteria, a manager of the storage (in Windows 95/98, it is called virtual memory manager) under the operating system must:

Keep track of the status of all parts of allocable main store - either be free or allocated
Allocate portions of free store to a requesting process according to some store management policy
Ensure that the addresses generated by the process are routed to its own areas of store, and cannot be routed to another process’s areas of store
Reclaim store areas from processes - either by preemptions, or when the process indicates that it has no further use for a store area, or when the process terminates

It is concluded that the memory management strategies are defined to obtain the best possible use of the main memory for the following three operations:

FETCH
WHEN to obtain the next program

a) Demand - Referenced by a running program

b) Anticipatory - as Anticipated

PLACEMENT
WHERE in the main memory to place the program
REPLACEMENT
WHICH program is to be displaced to make room for incoming programs

Figure shows the three operations. Here, the main memory is partitioned into two blocks for operating system and user. A process is making a request from the disk to decide the placement.

Memory Management Schemes

This section discusses many allocation schemes that are broadly classified as virtual and non-virtual.

A set of schemes going from simple to complex will be presented. Each successive scheme attempts to achieve increase in throughput performance. The memory management schemes include:

Single contiguous allocation
Fixed partitioning allocation
Variable partitioning allocation
Paged allocation
Segmented allocation
Segmented-paged allocation

These schemes can be further divided into two main groups, namely, Nonvirtual Strategy and Virtual Strategy.

Non-virtual (Nonvirtual)

 It is termed “what you see is what you get”. For instance, DOS 6.2 is a non-virtual operating system. If your programme is greater than the conventional memory size, the operating system cannot execute it. @LIST =  The computer organization restricts number of accessible memory locations e.g. 16-bit program counter = 216 = 65536
If the actual memory capacity installed is less than the maximum, then the program is limited by this capacity
Based on the above classification, it is a typical example of
Single contiguous allocation;
Fixed partitioning allocation; or
Variable partitioning allocation.

Virtual

It is termed “what you want is what you get”. For instance, Windows 3.1/Windows 95/98, Windows NT, Unix, VAX/VMS are non-virtual operating systems. If your programme is greater than the conventional memory size, the operating system still can execute it.

This strategy emulates the maximum main storage capacity on computer systems where the actual capacity is much less.
Based on the above classification, it is a typical example of
Paged allocation;
Segmented allocation; or
Segmented-paged allocation.

Nonvirtual Strategies

Single Contiguous Allocation

As shown in Figure , there is a memory block consisting of operating system and a single block (continuous) for user. The allocation for this is most advantageous in two ways:

Program execution is simple the CPU does not have to modify the programmer’s memory references in order to find the correct memory location.
Protection of the OS is simple Any memory references beyond a certain threshold value imply possible destruction of OS

The characteristics  for single contiguous allocation are:

one process (and its children) are given access to the whole of main store
main store contains the OS and the application codes
any part of the storage area not required by the process is unused (wasted)

Advantages and Disadvantages

The advantages are:

its simplicity
often found in small computer

The disadvantage is under utilization of store and processor.

Overlay

When an application is too large to be fitted in the memory, it must be overlayed. That is to say, it must load the programme piece by piece on internal programme call basis. The characteristics are:

The application program must be structured into resident and non-resident sections.
Non-resident sections displace each other during program execution.
This method is time-consuming, complex, and makes program maintenance difficult.
It is not needed in Virtual Storage operating system.

Example

For a 10K main procedure A with following sub-procedures from B to G with programme size. Procedure A will call Procedure B, C and D. Procedure B will call E and F while Procedure C will call F and G.

procedure

B

7K

 

C

3K

D

3K

E

11K

F

2K

G

5K

What is the overlay structure? What is the minimum amount of memory required to run the program? Draw a block diagram for Overlay structure.

The overlay structure is shown in Figure . Based on this diagram, the minimum amount of storage is summation of Procedure A, B and E, which is equal to 28K.

Fixed Partitioning Allocation

It is also known as Fixed Partition Multiprogramming, or Multiprogramming with Fixed Number of Tasks. The characteristics are as follows:

Main storage is divided into a number of fixed-size blocks, each of which may be of different size, in order to permit multiprogramming as shown in Figure . Here, it consists of three fixed memory blocks, namely, block 1, block 2 and block 3.
Each partition holds a single job, and the CPU switches rapidly between users to create the illusion of simultaneity.
Jobs are translated with absolute assemblers and compilers to run in specific partition.
If a partition is occupied, the job has to wait even if other partitions are free.
Two boundary registers for every partition permit operating system and interprocess protection.

Advantages and disadvantages

The advantages are as follows:

It avoids wastage of CPU idle time
Operating system is easy to implement

The disadvantages are as follows:

degree of multiprogramming is fixed
only 1 job per partition
waste of main storage
some partitions not used

It causes internal fragmentation, which means that processes do not consume all the allocated storage has unused holes and fragments. Figure shows the internal fragmentation. Here, operating system allocates more storage block to P2, which is more than P2 needs. This leaves holes between P2 and P3.

Variable Partitioning Allocation

It is also known as Multiprogramming with Variable Number of Tasks, or Variable Partition Multiprogramming.

Since Fixed Partitioning is too limited, the concept of Variable Size Partition is implemented.
Processes are allocated with memory as much as they required, provided that there is enough free memory available as shown in Figure . Here, the allocation of storage block is not fixed.
A “relativity” mechanism is used to make the program independent from its physical core memory location using ‘Base-and-Limit Registers’.
When a process is loaded, the physical address at which the process’s store area begins is stored in the BASE Register.
a Limit Register stores the Base Register value + the length of the process’s store area
There is no Internal fragmentation. However, it now has external fragmentation as shown in Figure . Here, the summation of holes is sufficient for a new process.
Fragmentation in Variable Partitioning is severe since completed processes leave holes
Garbage collection (Compaction) or Coalescing of free space necessary
To reduce external fragmentation is to perform Compaction as shown in Figure . Here, the hole after compaction is sufficient for a new process P4. It is achieved by
moving all occupied area to one end or the other of main storage leaving free storage as a single, large hole. However, there is a problem, which,
it will consume large amount of system resources.
Coalescing Holes:
maintain a free storage list
merge adjacent holes together to form a single large hole

Storage Placement Strategies

It is about where to put programs and data in the main memory and consists of three strategies, namely, best-fit, first-fit and worst-fit.

Best-Fit

Place job in the smallest possible hole in which it will fit
Leave larger holes for larger segments
Use a linked list arranged in increasing order of size

Disadvantages:

it needs to search through the linked list of memory blocks
it is time consuming as it needs to go through the checking
will be left with many tiny holes as each size is not perfectly matched.

First-Fit

Place job in the first storage hole on free storage list in which it will fit
Observed to be as good as Best-fit
Linked list in increasing order of initial address of each hole
Advantages:
The placement decision can be made quickly
It can easily detect if two holes are adjacent to each other by using the following:

if address+size = address stored in next node = adjacent holes

Worst-Fit

Place jobs in the largest hole in which it will find
After placing the program in the largest hole, the remaining hole may still be large enough to hold another program.
Partitioning is undesirable in many respects

Why let the physical capacity of the main memory limits the process?

The process will execute out of the predefined boundaries, which might corrupt the other processes.

The organization, or architecture, of the CPU determines the upper limit of the addressable memory.
Memory allocation is contiguous

Why not allocate memory for a process in pieces (Non-contiguous)?

Firstly, there is an overhead to keep track the free storage. Secondly, to arrange the memory like this is equivalent to a virtual system.

Summary

This chapter covered the memory storage strategies, namely, virtual and non-virtual. Non-virtual storage including single contiguous allocation, fixed partitioning allocation and variable partitioning allocation was discussed with example. External fragmentation and internal fragmentation leading to low utilisation of storage were also discussed. The commonly used three placement strategies, namely, best-fit, worst-fit and first-fit were included for comparison. There is no conclusion which placement strategy is the best as there are advantages and disadvantages for each of them. Virtual storage strategy will be covered in later chapter.

Self-test Question

A program is made up of a main program A with size 30K bytes and the following procedures:
 

Procedure

Size (K Bytes)

Procedure

Size (K Bytes)

B

9

F

5

C

7

G

9

D

8

H

6

E

4

I

7

The program is written such that Main Program A will call procedures B, C, and D. Procedure B in turn calls E, F, H, and G, procedure C may call H,and E, and procedure D may call H, F, I and G. Draw a tree type structure and determine the minimum amount of memory required to run the program using Overlay Structure. If the whole program is loaded into the memory, what will be the minimum memory required? (Past examination question)

Select the CORRECT statement(s) about storage strategy.

Non-virtual storage refers to what you want is what you get.

Fixed partitioning allocation refers to virtual storage.

Page allocation is classified as a virtual system.

Select the CORRECT statement(s) about storage placement strategies.

The Best-Fit strategy places a job in the largest possible hole in which it will fit.

The advantage of First-Fit is that the placement decision can be made quickly.

The characteristic of Worst-Fit is that memory allocation is contiguous.

There are three memory blocks, namely, B1, B2 and B3, each of which in size is 200K, 100K and 150K. Two processes each of which requires 50K and 70K respectively. After executing these processes, list the remaining memory size for each block using first-fit, best-bit and worst-fit respectively.