This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.
Primary memory is a very precious resource which frequently cannot contain every active processes in the system
The memory management system has the ability to decide which processes should reside (at least partially) in main memory
It also monitors the amount of available primary memory and may also periodically write processes to a secondary device which is called the swap device to provide more space in primary memory
At a later time, the kernel also reads the data from swap device back to the main memory
UNIX Memory Management Policies
Has two main areas:
It's Easy to implement
It utilizes Less system overhead
Has Greater flexibility
The swap device is like a block device in a configurable section of a disk
Kernel allocates contiguous space on the swap device without any fragmentation
It also maintains free space of the swap device in an in-core table, called map
The kernel treats each unit of the swap map as a group of disk blocks
As kernel allocates and frees resources, it also updates the map accordingly
Swapping Process Out
Memory à Swap device
Kernel swap out whenever it needs memory
When fork() called for allocate child process
When called for increase the size of process
When the process become larger by growth of its stack
Previously swapped out processes want to swap in but there is not enough memory
The kernel should gather the page addresses of data at primary memory to be swapped out
Kernel copies the physical memory assigned to a process to the allocated space which is on the swap device
The mapping between physical memory and swap device is kept in page table entry
There may not be enough free memory when fork() called
Child process swap out and "ready-to-run"
Swap in when kernel schedules it
It reserves enough space on the swap device to contain the memory space of the process, including newly requested space
Then it adjusts the address translation mapping of the process
Finally, it swaps the process out on newly allocated space in the swapping device
When the process swaps the process into memory, it will allocate physical memory according to the new address translation map
Not all pages of process resides in memory
When a process accesses a page which is not part of its working set, it incurs a page fault.
The kernel suspends the execution of a process until it reads the page into memory and makes it accessible to the process
Data Structure for Demand Paging
Page table entry
Disk block descriptors
Page frame data table
Swap use table
Page Table Entry
It contains the physical address of page and the following bits:
Valid: whether the page content is legal
Reference: whether the page is referenced recently or not
Modify: If the page content is modified
copy on write: kernel must create a new copy when a process modifies its content
Age: Age of page
Protection: Read/ write permission
Disk Block Descriptor
Swap Device number as there can be several swap devices
Block number that contains the page
Memory Management in Linux
It contains two Parts
Architecture Independent Memory
It should be flexible and portable enough across platforms
Implementations for a specific architecture
Architecture Independent Memory Model
Process virtual address space which is divided into pages
Page size given in PAGE_SIZE macro in asm/page.h
(4K for x86 and 8K for Alpha)
The pages are mostly divided between 4 segments
User Code, User Data, Kernel Code, Kernel Data
In User mode, access is only User Code and User Data
But in Kernel mode, access is also needed for User Data
put_user(), get_user(), memcpy_tofs(), memcpy_fromfs() allow kernel to access user data
Registers cs and ds point to the code and the data segments of the current mode
fs points to data segment of the calling process in kernel mode.
Get_ds(), get_fs(), and set_fs() are also defined in asm/segment.h
Segment + Offset = 4 GB Linear address (32 bits)
Of this, user space = 3 GB and kernel space = 1GB
Linear Address are converted to physical address using 3 levels
Page Table Entry (pte_t)
Presence (is the page present in VAS?)
Read, Write and Execute
Macros of Pgprot_type
PAGE_COPY/READ_ONLY (read only, used by copy-on-write)
PAGE_KERNEL (accessibe only by kernel)
Page Table Functions
mk_pte(), Pte_clear(), set_pte()
pte_mkclean(), pte_mkdirty(), pt_mkread(), â€¦.
pte_none() (checks whether entry is set)
pte_page() (returns the address of page)
pte_dirty(), pte_present(), pte_young(), pte_read(), pte_write()
int do_mmap(struct file *, unsigned long addr, unsigned long len, unsigned long prot, unsigned long flags, unsigned long off);
It creates a new memory region
Also creates the required PTEs
Sets the PTEs to fault later
The handler (nopage) will either copy-on-write if anonymous mapping, or will bring in the required page of the file.
How is brk() implemented?
Checks whether to allocate (deny if not enough physical memory, exceeds its VA limits, or crosses stack).
Then call do_mmap() for anonymous mapping between the old and the new values of brk (in process table).
Returns the new brk value.
On a sys call, CS points to the kernel segment. DS and ES are set to the kernel segment as well.
Next, FS is set to the user data segment.
Put_user() and get_user() can then access the user space if needed.
The address parameters to these functions cannot exceed 0xc0000000.
Violation of this results in a trap, together with any writes to a read-only page (creates a problem on 386, while the problem does not exist in 486/Pentium)
Hence, verify_area() is typically called before performing any such operations.
Physical and Virtual addresses are the same except for those allocated using vmalloc().
Kernel segment is shared across processes (not switched !)
Memory Allocation for Kernel Segment
Memory_start = console_init(memory_start, memory_end);
Typically done for drivers to reserve areas, and for some of the other kernel components.
Void *kmalloc(size, priority), Void kfree (void *) // in mm/kmalloc.c
Void *vmalloc(size), void *vmfree(void *) // in mm/vmalloc.c
Kmalloc is mainly used for physically contiguous pages while vmalloc does not allocate physically contiguous pages
Memory allocated is not initialized (and is not paged out).
Allocates virtually contiguous pages, but they do not need to be physically contiguous.
Uses get_free_page() to allocate the physical frames.
Once all the required physical frames are found, the virtual addresses are then created at an unused part.
The virtual address searches for unused parts on x86 begins at the next address after physical memory on an 8 MB boundary.
One (virtual) page is also left free after each allocation for cushioning.
vmalloc vs kmalloc
Contiguous vs non-contiguous physical memory
kmalloc is faster and less flexible
vmalloc involves get_free_page() and sometimes needs to block to find a free physical page
DMA requires contiguous physical memory
All kernel segment pages are locked in the memory (no swapping)
The user pages can be paged out:
Complete block device
By fixed length files in a file system
First 4096 bytes are like a bitmap indicating that space for that page is available for its paging.
At byte 4086, string "SWAP_SPACE" is stored.
Hence, max swap of 4086*8-1 = 32687 pages = 130784KB per device or file
MAX_SWAPFILES specifies the number of swap files or devices
Swap devices are more efficient than swap file.