Memory Management

In this article we will study the principles of managing the main memory, one of the most precious resources in a multiprogramming operating system. Memory management module of the operating system is primarily concerned with the management of the main (primary) memory of the computer system. We have already studied that main memory is an important resource because it is the only storage media that CPU can access directly. However if your data reside on secondary storage and you want to process this data then this data must first be transferred to main memory by CPU-generated I/O calls. We have already studied that CPU utilization is more in multiprogramming operating system because in this more than one process can run simultaneously at the same time. therefore several programs should be in main memory.

The main memory part of operating system involves following main functions:

1. keeping track of which parts of main memory are currently being reserved and by which program
2. deciding which processes are to be loaded into main memory, when memory space becomes available
3. allocating memory space
4. deallocating memory space

No process may be activated until a finite amount of memory space can be allocated to it. In a multi-user multiprogramming environment, there may be more than one active program in main memory. It is the memory manager that decides which part of which program will be loaded into main memory. It is also the duty of memory manager to ensure the isolation of distinct address space to prevent an active process from erroneously or maliciously accessing and potentially corrupting the contents of the address

In other words, the memory manager has to ensure that there is no unauthorized access by a program of memory space not allocated to it. Therefore before executing any command, it must check that the address being used falls within the area given to that program. Additionally it must provide to allow cooperating processes to access common areas of memory. thus in a multiprogramming environment, the memory manager should simultaneously support both memory protection and sharing of memory. the conclusion is that use main memory optimally and service the program.

There are different schemes of memory management that meet these difficult and something conflicting requirements with various degree of multiprogramming. To provide a common basis for comparing memory management schemes, we consider three main measures – wasted memory, time complexity and memory access overhead.

Wasted memory is the memory that memory manager is unable to allocate the requesting processes. Time complexity refers to the complexity of allocating and deallocating of memory space when a process requests for memory space is accomplished or when a process comes out of memory. Finally memory access overhead refers to the duration of the additional operations performed by a given memory management scheme in accessing memory. Thus an ideal memory manager should minimize wasted memory and have a minimal time complexity and memory access overhead, while providing good protection and flexible sharing.

In a number of schemes to be described in this section, the operating system is illustrated as occupying a part of main memory space in the ‘lower part’ of the memory address space. Remind that it is not mandatory, rather the operating system could be in several sections and/or high memory address. Now let us discuss some standard memory management schemes.

Single Process System

It is one of the simplest ways of managing memory. In this type, the main memory is divided into two parts – one of then is permanently occupied by the operating system and the remaining part is allocated to the user processes, which are loaded and executed one at a time. When one process is completed, the operating system may load another process for execution. In this a part of memory space will be remain unused, as shown in figure-1.

Figure 1

This form of memory management scheme is commonly used by single process microcomputer operating system, such as MS-DOS.

Partitioned Memory Management Schemes

The single process system is used only for uniprocessing systems. But in multiprogramming system, the “user” part is divided into multiple partitions to accommodate multiple processes. Effective memory manager is vital in multiprogramming system. If there are only few processes in memory then they will spend mush of the time in waiting of I/O and CPU will be idle. Thus memory needs to be allocated efficiently to pack as many processes into memory as possible. Partitioned are made either statically or dynamically.

Static Partitioned Memory Management Scheme

In this memory management scheme, the main memory is divided into a number of separate fixed areas, each of which can hold one process at a time. The division of memory is made during the system generation process. The number and sizes of static partitions are usually determined, taking into the consideration the capacity of available main memory, the desired degree of multiprogramming and the typical sizes of processes to be run on a given system.

Figure-2 illustrates the static partitioned memory having four partitioned, one is assumed to be occupied by the operating system and remaining three are occupied by user processes P1, P2 and P3, as indicated, of sizes 150KB, 200KB and 150KB respectively, whereas the size of first partition is assumed to be 100KB, second partition to be 200KB, third partition to be 400KB and forth partition to be 300KB. Normally these three running processes will be independent so that process P1, for example, should not reference addresses out with the bounds of partition 3. And this achieved by memory protection schemes, such as early IBM 360.

Figure-2

From this figure, it is clear that each partition will typically contain unused space, as illustrated by the shaded boxes, called as internal fragmentation. When a process requests for memory space then the memory manager selects the best location in which to place the incoming one. Common algorithms for selection of a suitable of a free partition are first fit and best fit. In first fit, the new process is placed in the first available free partition which can accommodate it. On the other hand in best fit, the new process is placed in the partition in which it fits tightly. Each algorithm has its own merits and demerits.

Initially let all these four partitions are empty. The first partition is allocated to the operating system. Next, let a process P4, of size 250KB, requests for memory space. In this case if we apply first fit algorithm then partition number 3 would be allocated to it, whereas if we apply best fit algorithm then partition number 4 would be allocated to it.

In general requests to allocate partitions may come from one of two primary sources:

1. when a new process is created
2. when a swapped out process is reactivated

This request can be failed due to following reason:

1. no partition is large enough to accommodate incoming one
2. some partitions are free, but none of them is large enough to accommodate the incoming one
3. all partitions are allocated

As far as the first case is concerned, the operating system can not do much other than to report an error. This first problem is overcome by redefining the partitions accordingly. The second and third problems are overcome by vacating the sufficiently large partition. It is the operating system which selects the victim and transfers it to the secondary storage. This process is called swapping. This swapped out process can be later on swapped in, when needed. Swapping has traditionally been used to implement multiprogramming system with limited memory capacity or with little hardware support of memory management.

Static partitioning of memory is generally suitable for static environment where the workload is predictable and its characteristics are known. This scheme was one of the first to be employed in multiprogrammed computers, such as early IBM 360s.

This memory management scheme has following main disadvantages:

1. No single process may exceed the size of the largest partition or you can that it can prevent a process being run due to the unavailability of a partition of sufficient size.
2. It suffers from internal fragmentation of memory, resulting from the difference between the size of the partition and the size of the process loaded in that specific partition. See figure-2, here partition-2 has internal fragmentation of 50KB, partition-3 has of 200KB and finally partition-4 has 150KB. In general, fragmentation refers to the inability of the operating system to allocate portions of unused memory space.

Dynamic Partitioned Memory Management Scheme

In dynamic partitioned memory management scheme, when a process is brought into memory, it is allocated exactly as much memory as it requires and no more. Processes are loaded into consecutive set of memory areas until it is filled, or more likely, the remaining space is too small to accommodate another process. An example is as shown in figure-3. Initially main memory is empty, except the operating system. The first three processes P1, P2 and P3 are loaded in memory as shown in figure-3(b). Now suppose that a process P4 also wants to have memory space. But after loading three process, it leaves a hole at the end of main memory that is too small for a forth process P4. After some time, let process P2 is swapped out of memory, in order to make room for process P4. Since P4 is smaller than process P2 therefore another small hole is created.

Figure 3

No doubt it overcomes the limitations of static partitioned memory management scheme, that is of external fragmentation. But as this example shows, this method starts out well, but eventually it leads to the situation in which there are a lot of small holes (unused) in memory. As time goes on, memory becomes seriously fragmented, and such type of fragmentation is called as internal fragmentation. Remind that internal fragmentation occurs in static (fixed) partition scheme’ ‘internal’ implied ‘within the space allocated to a process’, while ‘external’ refers to space out with any process allocation.

One technique for overcome this problem of external fragmentation is memory compaction, in which some or all partitions are relocated into one end of main memory and thus combining the holes into one large free area. Memory compaction is performed whenever possible or only when needed. There is the decision to be made as to when and how often to perform the memory compaction. The memory compaction is made:

1. as soon as any process terminates
2. when a request to allocate a suitable partition fails
3. at fixed interval of time

No doubt memory compaction is a time consuming procedure, wasteful of processor time. Thus you can say that both unequal static and dynamic partitioned memory management schemes are inefficient in the use of memory.

Simple Paging System

In simple paging scheme, the memory is partitioned into equal fixed sized chunks, called as frames or page frames, that are relatively small, and that each process is also divided into fixed-size chunks of same size, called as pages. Allocation of memory consists of finding a sufficient number of unused page frames for loading of the requesting process’s pages. In other words, the loading process now involves transferring each process page to some memory page frame. In simple paging, at most, the wasted space in memory for that process is a fraction of the last page.

Figure 4

For example, let we want to load a process P1 that has 5 pages. At a given point in time, some of the page frames in memory are in use and some are free. Before loading the process, the operating system finds five free frames and loads the 5 pages of the process P1 into the free five frames. Figure-4 shows this. Now the question arises – is it necessary to find the sufficient unused contiguous page frames to hold the process? The answer is no. We can once again use the concept of logical addresses. A simple base address will no longer suffice. Since each page is mapped separately, different page frames allocated to a single process need not to occupy contiguous areas of physical memory.

In paging system, address translation is performed with the aid of a mapping table, called page map table (PMT). The operating system maintains a PMT for each process. The page map table shows the page frame location for each page of the process. The PMT is created at process-creation time in order to establish the correspondence between the logical (virtual) addresses and physical addresses.

Within the program, each logical address consists of a page number and a relative address (offset) within that page. Since pages and page frames have identical sizes, offsets within each are identical and need not be mapped. With paging the logical to physical address translation is still done by the CPU hardware. The virtual address is split into two – page number and an offset. The page number is sued to index the PMT and to obtain the physical address.

The page size is influenced by several factors. For sake of convenience of mapping, page sizes are usually an integer power of base 2. In most commercial implementation, page sizes vary between 512 bytes and 8kb.

In comparison to other schemes, paging offers high utilization of main memory. in particular this means that when there are not enough free page frames to satisfy the needs of the next process to be loaded, the scheduler may “skip around” the waiting-for-memory queues in order to find a process with small memory requests.

Simple Segmentation

There is another way in which addressable memory can be subdivided, known as segmentation. Unlike paging where a process is divided into a number of fixed-size chunks, segmentation  presents us an alternative method of dividing a process by using variable-length chunks, called segments. Segments are variable, indeed dynamic, in size. Segments are formed at program translation time by grouping together logically related items. Being a result of logical division, individual segments generally have different sizes. Although different segments of a process may be placed in separate, non-contiguous areas of main memory, items belonging to a single segment must be placed in contiguous area of main memory. Thus you can say that this segmentation possesses some properties of both contiguous and non-contiguous memory management schemes. There may be a number of program segments for various types of programs as well as a number of data segments.

When requested to load a segment, the operating system attempts to allocate memory for the supplied segment of a process using dynamic partitioned memory management scheme. The base and size of a loaded segment are recorded in a table, called segment descriptor table (SDT). The conversion of a logical address into a physical address is similar to the simple paging system. In this the logical address consists of two parts – segment number and displacement (offset) within that that segment. The segment number provided in the logical address is used to index the segment descriptor table and to obtain the physical base address of the related segment. After this the base address of the specified segment is added to the offset, only when the offset is not greater than the size of the segment, in order to produce the physical address. However if the offset is greater than the size of the segment then it means that it is an invalid address.

The segmentation has following advantages over non-segmentation schemes:

1. The segmentation is very handy in the situation where the program does not know in advance about the size of a data structure by assigning it a separate segment.
2. It allows programs to be altered and recompiled independently, without requiring that an entire set of programs be relinked and relocated.
3. It provides the facility of sharing by placing the targeted item in a segment that can be addressed by other processes.
4. Additionally it provides the protection by assigning access privileges in a more convenient fashion.

Unfortunately these advantages are not available with paging. But no doubt, paging provides an efficient form of memory management. To combine the advantages of these two schemes, some systems are equipped the hardware and operating system software.

Virtual Memory

The memory management schemes that we have discussed so far are known as real memory management schemes. In real memory management schemes, it is mandatory to load the complete process image in main memory prior to its execution. But in practice, there are several programs, which can be larger than the available physical memory. This limitation is overcome by virtual memory.

Virtual memory is a memory management scheme where only those portions (pages/segments) of a resident process, which are actually being referenced at any instant, need be present in memory. And the remaining portions of the can be retained on secondary storage. In other words, virtual memory allows execution of partially loaded program. If the flow of execution moves to page/segment, which is not in memory, the operating system has to load the required page/segment from secondary memory to main memory before execution can proceed. Thus where the real memory management schemes strive to approach 100% utilization of main memory, virtual memory systems routinely provide apparent utilization factors in excessing 100%.

Virtual memory makes the task of programmer much easier, because the programmer no longer needs to worry about the amount of main memory. Virtual memory is commonly implemented by demand paging and demand segmentation.

Demand Paging

The demand paging system is similar to simple paging system with a refinement, which simply means that each page of a process is brought into main memory only when it is needed, that is on demand. To keep track the status of each page in main memory, the operating system maintains a presence bit to each entry of the page map table. If the presence bit is set then it means that the corresponding page is in memory. Conversely when the presence bit is not set, the corresponding page is not in main memory. Before loading the process, the operating system clears all presence bits in the related PMT entry. As and when specific pages are transferred from secondary memory to main memory, the corresponding presence bits are set. And when a page is removed from main memory, it s presence bit is reset.

It is true that, at any one time, only a few pages of any given process are needed, if the process tries to reference a page that was not present in main memory, a page fault is triggered. Thus when the running process experiences a page fault, it must be suspended until the missing page is brought in main memory. This tells the operating system to bring the desired page.

In demand paging, the operating system maintains a file map table (FMT) that contains secondary storage addresses of all pages of a process. One FMT is maintained for each active process. When a page fault occurs, the operating system uses the respective FMT to load the desired page into main memory. Since only a few pages of any given process are in memory, therefore more processes can be maintained in main memory. In multiprogramming operating system when resource utilization is low, the degree of multiprogramming can be increased by activating more processes. But it is the duty of the memory manager to keep track of program behavior when doing so.

If a program experiences high page fault rate then more page frames can be allocated to it, if possible, or suspended otherwise. Similarly, if a program experiences low page fault rate then a few page frames can be taken from that program. Thus allocation of a page frames to a process should be appropriate. However if memory manager is overloaded to the extent then most of the active programs are above their upper page fault rate, the system may exhibit a behavior known as thrashing. In this case, the CPU spends most of its time shuttling pages between main memory and secondary memory rather than executing instructions. Thus while allocating page frames to a new process, the operating system must adopt a good allocation strategy because few pages may lead to thrashing and too many pages may unduly restrict the degree of multiprogramming and processor utilization.

Until the concept of virtual memory came into existence, the programmer was actually aware of how much main memory is available. Depending on this fact, the programmer must devise ways to structure the program into pieces that can be loaded one at a time. But with demand paging, the operating system itself loads portions of any process into main memory and relieves the programmer from this responsibility. As far as the programmer is concerned, he or she is dealing with a huge memory. thus virtual memory allows for very effective multiprogramming and relieves the user of the unnecessary tight constraints of main memory.

Demand Segmentation

With demand segmentation, a process does not need to have all its segments in memory to execute. Like demand paging, a segment is loaded only when it is required. If a process references a segment, which is not in main memory then that segment is immediately brought into main memory by the operating system.

Cache Memory Management

Management of Cache memory is also the duty of memory manager. Cache is a very high-speed, expensive memory which is placed between main memory and the CPU. The Cache holds copies of the most frequently used pages in order to increase the speed of execution. When a page is referenced, it is firstly checked in cache. If it is found then the execution of that page continues; otherwise it is fetched from the main memory. when some change is written to cache, the corresponding main memory also has to be updated