Memory Allocation Schemes in Operating Systems | OS Tutorials

We first consider how to manage and allocate main (“core”) memory (also called random-access memory (RAM)). In general, a memory manager provides two operations:

Address allocate(int size);

voiddeallocate(Address block);

Memory Allocation Steps in Operating System

• The procedure allocate receives a request for a contiguous block of memory of size bytes and returns a pointer to such a block.
• The procedure deallocate releases the indicated block, returning it to the free pool for reuse. Sometimes a third procedure is also provided, Address reallocate(Address block, intnew_size); which takes an allocated block and changes its size, either returning part of it to the free pool or extending it to a larger block. It may not always be possible to grow the block without copying it to a new location, so reallocate returns the block’s new address.
• Memory allocators are used in a variety of situations. In Unix, each process has a data segment. There is a system call to make the data segment bigger, but no system call to make it smaller.
• Also, the system call is quite expensive. Therefore, there are library procedures (called malloc, free, and realloc) to manage this space. Only when malloc or realloc runs out of space is it necessary to make the system call.

Algorithms for Memory Management

• The memory manager needs to keep track of the “holes” between them. The most common data structure is a doubly linked list of holes.
• This data structure is called the free list. This free list doesn’t actually consume any space (other than the head and tail pointers), since the links between holes can be stored in the holes themselves provided each hole is at least as large as two pointers.
• To satisfy an allocate(n) request, the memory manager finds a hole of size at least n and removes it from the list.
• If the hole is bigger than n bytes, it can split off the tail of the hole, making a smaller hole, which it returns to the list.
• To satisfy a deallocate request, the memory manager turns the returned block into a “hole” data structure and inserts it into the free list. If the new hole is immediately preceded or followed by a hole, the holes can be merged into a bigger hole.

How does the Memory Manager Know How Big the Returned Block is?

• The usual trick is to put a small header in the allocated block, containing the size of the block and perhaps some other information.
• The allocate routine returns a pointer to the body of the block, not the header, so the client doesn’t need to know about it.
• The deallocate routine subtracts the header size from its argument to get the address of the header. To make it easier to coalesce adjacent holes, the memory manager also adds a flag (called a “boundary tag”) to the beginning and end of each hole or allocated block, and it records the size of a hole at both ends of the hole.
• When the block is deallocated, the memory manager adds the size of the block (which is stored in its header) to the address of the beginning of the block to find the address of the first word following the block.
• It looks at the tag there to see if the following space is a hole or another allocated block. If it is a hole, it is removed from the free list and merged with the block being freed, to make a bigger hole.
• Similarly, if the boundary tag preceding the block being freed indicates that the preceding space is a hole, we can find the start of that hole by subtracting its size from the address of the block being freed, remove it from the free list, and merge it with the block being freed.
• Finally, we add the new hole back to the free list. Holes are kept in a doubly-linked list to make it easy to remove holes from the list when they are being coalesced with blocks being freed.

How does the Memory Manager Choose a Hole to Respond to an Allocate Request?

There are different techniques/algorithms by which an empty hole is allocated to any request. These are discussed in detail in the next session.

Memory Allocation Schemes

The main memory must accommodate both the operating system and the various user processes. The memory is usually divided into two partitions as shown in Figure 2.

1. One for the resident operating system.
2. The other for user processes.

• We can place the operating system in either low or high memory. The major factor affecting this decision is the location of the interrupt vector; it is more common to place the operating system in low memory.
• Memory can be partitioned in two ways:
  1. Single Partition Allocation
  2. Multiple Partition Allocation

Single Partition Allocation

If the operating system is residing in low memory and the user processes are executing in high memory, we need to protect the operating system code and data from changes by the user processes. We also need to protect the user processes from one another. We can provide this protection by using a relocation register.

• Figure 3 shows that the MMU maps the logical address dynamically by adding the value in the relocation register, and the finally mapped address is sent to memory.
• The relocation-register scheme provides an effective way to allow the operating system size to change dynamically.

Transient Operating System Code:

• The operating system contains code and buffer space for device drivers. If a device driver is not commonly used, it is undesirable to keep the code and data in memory, since we can use that space for other purposes.
• Such code is sometimes called transient operating-system code.
• Thus, using this code changes the size of the operating system during program execution.

Multiple Partition Allocation

• In multiple partitions, the memory is divided into different partitions. The operating system keeps a table indicating which parts of memory are available and which are occupied.
• Initially, all memory is available for user processes and is considered as one large block of available memory, a hole.
• When a process arrives and needs memory, it searches for a hole large enough for this process.
• If it find, allocates only as much memory as needed, keeping the rest available to satisfy future requests.