Subject: Operating System

Topic: MEMORY MANAGEMENT

Difficulty: Hard

Allocating a single contiguous section of memory to each process is the most primitive method of memory management, usually called partitioning. It has been used in some now-obsolete operating systems. Each single section is called a partition.

Fixed partitioning

The simplest partitioning method is dividing memory into several fixed-sized partitions in advance, called fixed partitioning. Each partition may contain exactly one process.

As Figure __ (a) shows, a 64M memory is divided into 8 equal-size partitions with 8 megabytes each.

Any process whose size is less than or equal to the partition size can be loaded into any partition available. And when no partition is available and a new process is to be loaded, a process already residing in main memory may be selected to be swapped out to free a partition.

So the placement algorithm for this method is very simple. However two disadvantages are present with it:

A program that is too big to be held in a partition needs some special design, called overlay, which brings heavy burden on programmers.

With overlay, a process consists of several portions with each being mapped to the same location of the partition, and at any time, only one portion may reside in the partition.

When another portion is referenced, the current portion will be switched out.

A program may be much smaller than a partition, thus space left in the partition will be wasted, which is referred to as internal fragmentation.

As an improvement shown in Figure __ (b), unequal-size partitions may be configured in main memory so that small programs will occupy small partitions and big programs are also likely to be able to fit into big partitions.

Although this may solve the above problems with fixed equal-size partitioning to some degree, the fundamental weakness still exists

• The number of partitions are the maximum of the number of processes that could reside in main memory at the same time.

• When most processes are small, the system should be able to accommodate more of them but fails to do so due to the limitation.

• More flexibility is needed.

Dynamic partitioning

To overcome difficulties with fixed partitioning, partitioning may be done dynamically, called dynamic partitioning.With it, the main memory portion for user applications is initially a single contiguous block.

When a new process is created, the exact amount of memory space is allocated to the process. Similarly when no enough space is available, a process may be swapped out temporarily to release space for a new process . The way how the dynamic partitioning works is illustrated in Figure ___.

As time goes on, there will appear many small holes in the main memory, which is referred to as external fragmentation.

Thus although much space is still available, it cannot be allocated to new processes. A method for overcoming external fragmentation is compaction.

From time to time, the operating system moves the processes so that they occupy contiguous sections and all of the small holes are brought together to make a big block of space.

The disadvantage of compaction is: The procedure is time-consuming and requires relocation capability.

Address translation

Figure __ shows the address translation procedure with dynamic partitioning, where the processor provides hardware support for address translation, protection, and relocation.

The base register holds the entry point of the program, and may be added to a relative address to generate an absolute address. The bounds register indicates the ending location of the program, which is used to compare with each physical address generated.

If the later is within bounds, then the execution may proceed; otherwise, an interrupt is generated, indicating illegal access to memory. The relocation can be easily supported with this mechanism with the new starting address and ending address assigned respectively to the base register and the bounds register.

Placement algorithm

Different strategies may be taken as to how space is allocated to processes:

First fit:

Allocate the first hole that is big enough. Searching may start either at the beginning of the set of holes or where the previous first-fit search ended.

Best fit:

Allocate the smallest hole that is big enough. The entire list of holes must be searched unless it is sorted by size. This strategy produces the smallest leftover hole.

Worst fit:

Allocate the largest hole. In contrast, this strategy aims to produce the largest leftover hole, which may be big enough to hold another process. Experiments have shown that both first fit and best fit are better than worst fit in terms of decreasing time and storage utilization.