This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.
In operating systems certain portion of RAM contains both the static kernel data structures and kernel code. This portion is assigned permanently to the kernel. The other portion of the RAM is called dynamic memory. The dynamic memory is an important resource required by processes as well as kernel. Hence dynamic memory should be assigned only when it's desired and should be set free as soon as its usage is over.
Allocation of physical memory (RAM) among many competing demands is done efficiently with the help of virtual memory system. Such a system aggregates physical memory along with some secondary storage device which provides illusion to the computer that it has more memory than it's actually present in reality.
Virtual memory allows the operating system to perform many advanced functions like caching, swapping and process isolation. The Linux kernel has 4GB of virtual memory address space of which 3GB is allocated to user programs and 1GB for kernel. The following sections will explain how the kernel allocates dynamic memory for its own use.
2. LINUX VIRTUAL MEMORY
2.1 MEMORY MANAGEMENT UNIT
Linux uses a 3-page level structure called page directory, page middle directory and page table.
Page Directory: Any active process is present in main memory and has one page directory. Every entry in the page directory corresponds to one page of page middle directory.
Page Middle Directory: It consists of multiple pages where each entry corresponds to one page in page table.
Page Table: It may also consist of multiple pages where each page represents a virtual page of the process.
The address translation from virtual addresses to physical addresses is done with the help of Memory Management Unit (MMU) of the processor. "The MMU uses a section of memory to translate virtual addresses into physical addresses via a series of table lookups" [Understanding Virtual Memory In Red Hat Linux Enterprise Linux 4 - by Neil Horman]. The page table has a bit which indicates whether each virtual page has a corresponding page available in physical memory. If no such page is present then a page fault exception is generated which is handled by the software that places the required page from hard disk back on physical memory.
Fig 3: Virtual to physical memory translation [Understanding Virtual Memory In Red Hat Linux Enterprise Linux 4 - by Neil Horman]
3. PHYSICAL CONTIGUOUS MEMORY AREAS
3.1 PAGE FRAME MANAGEMENT
3.1.1 NUMA (Non uniform memory access):
Linux supports NUMA model in which the memory is staged in form of banks that requires different cost to access different memory locations depending upon the distance from a given CPU. "For example, a bank of memory might be assigned to each CPU, or a bank of memory very suitable for Direct Memory Access (DMA) near device cards might be assigned"[Understanding the Linux Virtual Memory Manager by Mel Gorman]. This physical memory which is partitioned in form of banks is called node. Within a given node the time taken by given CPU is same, but different CPU's will have differing time values to access the given node. "For every CPU, the kernel tries to minimize the number of accesses to costly nodes by carefully selecting and storing the kernel data structures that are most often referenced by the CPU" [Understanding Linux Kernel by Daniel P. Bovet]. Each node is further subdivided into smaller blocks called zones that correspond to ranges within memory.
3.1.2 MEMORY ZONES:
The storage of Kernel or User data, buffering of disk data and other functionalities are possible with the help of a memory storage unit which consists of fixed size chunks called page frames. The usage of page frames is limited due to some hardware constraints such as
In 32- bit computers with huge RAM capacity; since the linear address space is limited the direct access to physical memory is prohibited.
DMA processors in old ISA buses are able to address only first 16 MB of RAM [Understanding Linux Kernel by Daniel P. Bovet].
To overcome these two limitations Linux splits the physical memory of each node into three different zones.
This zone contains first 16MB of RAM. The old ISA based Legacy devices are allocated space from this zone to perform DMA operations. This zone contains normal page frames which can be directly accessed using linear mapping by the kernel
"Contains page frames of memory from 16MB to 896MB. This space is used by kernel for internal data structures and for user space allocations" [ http://www.redhat.com/magazine/001nov04/features/vm/]. The page frames in this zone can be directly accessed using linear mapping by the kernel
Contains page frames above 896MB. The page frames in this zone cannot be directly accessed by the kernel through linear mapping. This zone is always vacant on 64-bit architectures.
D:\MS_Sem2 docs\Introduction to operating systems\physical memory allocation.jpg
Figure 1: Partition of Physical memory [physical memory management in linux by Hao-ran Liu]
Each zone has page descriptors that have links to the memory node and to the zone within the node having respective page frame. This links are stored as indices rather than pointer in order to minimize the storage space. "When the kernel invokes the memory allocation function it must specify the zones that contain the requested page frames" [Understanding Linux Kernel by Daniel P. Bovet]. Such a request made to function is either satisfied with the available free memory or if no free memory is present then the request gets blocked until there is additional free memory available. Certain requests which are executing inside its critical section or are handling interrupts cannot be blocked and should be assigned memory through atomic memory allocation requests. Such atomic requests are never blocked and are failed if there is no free memory available.
3.1.3 ZONE PAGE FRAME ALLOCATOR:
Zone page frame allocator is the kernel subsystem that manages the memory allocation requests for groups of continuous page frames. The requests for allocating and de-allocating dynamic memory is managed by component called Zone Allocator. This component searches for group of continuous page frames inside a memory zone. Its uses Buddy System to manage page frames within each zone.
3.1.4 BUDDY SYSTEM:
The buddy system is a memory allocation algorithm whose main purpose is to minimize the external fragmentation and improve speed of allocation and de-allocation of pages. To solve the problem of external fragmentation, the free conterminous memory pages are grouped into 11 lists of size 1,2,4,8,16,32,64,128,256,512,1024. This allows grouping all 1 page size block on one list, 2 page size on another and so on. If the request comes for a group of say size 64 conterminous page frames then the algorithm will first verify if such as block is available. If available it is used to satisfy the request or else the algorithm looks for next larger block of 128 page size. If such a block is present then the kernel splits it into two blocks of page size 64. One is allocated to the requestor while other is added to the list of page size 64. "This avoids splitting large contiguous free page blocks when a request can be satisfied by a smaller block thus reducing external fragmentation" [Memory Management in Linux - Abhishek Nayani, Mel Gorman and Rodrigo S. de castro].In reverse operation when block of certain size if freed, the kernel attempts to merge it with another block of same size adjacent to the freed one. This algorithm is iterative till it can merge the blocks to the largest possible size.
3.2 MEMORY AREA MANAGEMENT
3.2.1 SLAB ALLOCATOR:
The main purpose of slab allocator is to prevent the repetitive initialization of objects. It does so by having caches of commonly used objects in memory. This helps the kernel to save its time in allocating, initializing and freeing the same object. "Whenever kernel creates a new process, it allocates memory areas for some fixed size tables like process descriptor, the open file etc. When process terminates these memory areas can be reused" [Understanding the Linux kernel - Daniel P. Bovet].
The slab allocator helps to save such memory areas in cache and use them quickly rather than allocating and de-allocating the same memory areas repeatedly.
Each cache consists of blocks of conterminous pages in memory called slabs. These slabs are split into smaller chunks for the data structures and the objects that the cache manages. "Linux slab allocator uses these ideas to build a memory allocator that is efficient in both space and time" [ http://www.ibm.com/developerworks/linux/library/l-linux-slab-allocator/]
Fig 2: Layout of the Slab Allocator [Understanding the Linux Virtual memory manager - Mel Gorman]
As shown in the above figure the cache consists of three slabs
Consists of fully allocated slabs
Slabs are partially allocated
Consists of empty slabs, the objects are not allocated.
The slab allocator has three main principles:
Minimize or eliminate the internal fragmentation caused by the buddy system by assigning smaller blocks of memory.
Alignment of objects to L1 and L2 caches to optimize the usage of hardware cache.
Caching of commonly used objects
3.2.2 MEMORY POOLS:
Memory pools are the new feature present in Linux version 2.6. Whenever the system faces low-on-memory emergencies the kernel allocates the dynamic memory from the memory pool. Thus memory pool is a reserve of dynamic memory which can be used only by specific kernel component when all the usual memory allocation requests are destined to fail. The memory pool can allocate every form of dynamic memory, the larger page frames as well as smaller memory areas.
NON-CONTIGUOUS MEMORY AREAS
4.1 NON CONTIGUOUS MEMORY AREA MANAGEMENT
If there is frequent access to memory areas then such areas can be mapped to conterminous page frames so as to lower the average memory access time and make significant usage of cache. If however the memory areas are infrequent then noncontiguous page frame allocation scheme is best suited so as to avoid external fragmentation with the disadvantage that the kernel page table would be more often used.
"Linux uses noncontiguous memory areas to allocate data structures for active swap areas, allocate space for a module, or to allocate buffers to some I/O drivers" [ Understanding the Linux kernel - Daniel P. Bovet].
The virtual memory converts the logical addresses to physical addresses at run time allowing the processes to be located anywhere in the main memory. It also allows process to be broken up into smaller chunks which may not necessarily be present contiguously in main memory.
Linux virtual memory management scheme uses page allocation technique for kernel memory allocation. This scheme uses Buddy algorithm which allocates and de-allocates memory to the kernel in units of one or more number of pages.
As the kernel will also require memory in smaller number of units called chunks, this scheme turns out to be inefficient and hence the Linux uses another mechanism called Slab Allocator within the allocated page.