Based on Notes made by Sharon Francis, Steffi Devasia, Remi Rajan,Yashaswi Alva
Modified by : Jibrael Jos
The pfdata table describes each page of physical memory. Fields of an entry are
The swap use table contains an entry for every page on swap device
Fork in paging system
Page faults A page fault occurs when a process accesses a virtual page for which there is no page table entry(PTE) in the page table or whose PTE in some way prohibits the access, e.g., because the page is not present or because the access is in conflict with the access rights of the page.
Two types
Modified by : Jibrael Jos
- Primary memory is a precious resource that frequently cannot contain all active processes in the system.
- The memory management system decides which processes should reside (at least partially) in main memory.
- It monitors the amount of available primary memory and may periodically write processes to a secondary device called the swap device to provide more space in primary memory.
- At a later time, the kernel reads the data from swap device back to main memory.
UNIX systems transfers’ entire processes between Primary memory and the swap device, but does not transfer parts of a process independently, except for shared text. Such a memory management policy is called swapping.
Swapping The swap device is a block device in a configurable section of a disk.
Space allocated for files is used statically, since it’ll exist for long time. Allocation of space on swap device is transitory, depending on the pattern of process scheduling.
Kernel allocates contiguous space on the swap device without fragmentation.
The kernel maintains free space for file system in a linked list of free blocks, accessible from the file system super block.
It maintains free space of the swap device in an in-core table, called map.
The kernel treats each unit of the swap map as group of disk blocks.
As kernel allocates and frees resources, it updates the map accordingly.
Space allocated for files is used statically, since it’ll exist for long time. Allocation of space on swap device is transitory, depending on the pattern of process scheduling.
Kernel allocates contiguous space on the swap device without fragmentation.
The kernel maintains free space for file system in a linked list of free blocks, accessible from the file system super block.
It maintains free space of the swap device in an in-core table, called map.
The kernel treats each unit of the swap map as group of disk blocks.
As kernel allocates and frees resources, it updates the map accordingly.
A map is an array where each entry consists of an address of an allocable resource and the number of resource units available there.
A map initially consists of one entry that indicates the address and the total number of resources.
A map initially consists of one entry that indicates the address and the total number of resources.
Algorithm malloc(refer page 273)
Input:address_of_map,number_of_unit
Output: address if successful. 0,
Swapping Process Out
Kernel swaps a process out when it needs space in memory, which might result from any of the following:
Input:address_of_map,number_of_unit
Output: address if successful. 0,
Swapping Process Out
Kernel swaps a process out when it needs space in memory, which might result from any of the following:
- The fork system call must allocate space for a child process.
- The brk system call increases the size of process, when a process becomes larger by the natural growth of its stack.
- The kernel wants to free space in memory for processes it had previously swapped out and should now swap in.
- The kernel must 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 on the swap device.
- The mapping between physical memory and swap device is kept in page table entry.
Fork Swap fork() is a system call to create a child process. When the parent process calls fork() system call, the child process is created and if there is short of memory then the child process is sent to the read-to-run state in the swap device, and return to the user state without swapping the parent process. When the memory will be available the child process will be swapped into the main memory.
Expansion Swap
If a process requires more memory it reserves enough space on the swap device to contain the memory space of the process, including the newly requested space
Then it adjust the address translation mapping of the process
Finally, it swaps the process out on newly allocated space in swapping device
When the process swaps the process into memory, it will allocate physical memory according to new address translation map
Expansion Swap
If a process requires more memory it reserves enough space on the swap device to contain the memory space of the process, including the newly requested space
Then it adjust the address translation mapping of the process
Finally, it swaps the process out on newly allocated space in swapping device
When the process swaps the process into memory, it will allocate physical memory according to new address translation map
Swapping Process In
Swapper: - The only process that swaps processes in from swap device and swaps processes out if it needs space in main memory.
Sleep if there is no work for it to do or if it is unable to do any work.
Executes only in kernel mode.
Uses internal kernel functions to do swapping.
Algorithm swapper
Input and output : none
{
Loop
For(checks all ready to run but swapped out processes)
Select the swapped out longest process;
If (no such process)
{
Sleep until a process on swap device wakes up;
Goto loop;
}
If(enough room in main memory for process)
{
Swap process in and goto loop;
}
For( all process loaded in main memory, not zombie and not locked in memory)
{
If(Sleeping process)
Choose process with highest value for priority + residence time;
Else
Choose process with highest value for residence time + nice;
}
If (chosen process is not sleeping or requirements not satisfied)
Sleep till a process is swapped in;
Else
Swap out process;
Goto loop;
Note:
Sleep if there is no work for it to do or if it is unable to do any work.
Executes only in kernel mode.
Uses internal kernel functions to do swapping.
Algorithm swapper
Input and output : none
{
Loop
For(checks all ready to run but swapped out processes)
Select the swapped out longest process;
If (no such process)
{
Sleep until a process on swap device wakes up;
Goto loop;
}
If(enough room in main memory for process)
{
Swap process in and goto loop;
}
For( all process loaded in main memory, not zombie and not locked in memory)
{
If(Sleeping process)
Choose process with highest value for priority + residence time;
Else
Choose process with highest value for residence time + nice;
}
If (chosen process is not sleeping or requirements not satisfied)
Sleep till a process is swapped in;
Else
Swap out process;
Goto loop;
Note:
Clock handler - Measures the time that each process has been in core or swapped out.
Zombie processes and process that are locked in memory do not get swapped out.
Kernel swaps out sleeping process rather than those “ready to run because of greater chance of “ready to run” processes for getting scheduled.
Flaws of the Algo to choose a process to Swap out
Demand paging
Locality- Process tends to execute in small portions of their text space.
Working set – Set of pages that the process has referenced in last n memory references, where n is the window.
Page default – When a process accesses a page that is not part of working set.
Data structures for demand paging (refer diagram in page 288)
Zombie processes and process that are locked in memory do not get swapped out.
Kernel swaps out sleeping process rather than those “ready to run because of greater chance of “ready to run” processes for getting scheduled.
Flaws of the Algo to choose a process to Swap out
- It may swap out a process that does not provide enough memory for incoming process.
- If swapper sleeps as it could not find enough memory, it searches again for a process to swap in although it had chosen one.
- If the Swapper chooses a “ready to run” process to swap out, it is possible that the process had not executed since it was previously swapped in.
- If swapper attempts to swap out a process but cannot find space on swap device, a system deadlock may arise if several conditions are met.
Demand paging
Locality- Process tends to execute in small portions of their text space.
Working set – Set of pages that the process has referenced in last n memory references, where n is the window.
Page default – When a process accesses a page that is not part of working set.
Data structures for demand paging (refer diagram in page 288)
- Page table entry
- Disk block descriptors
- Page frame data table
- Swap use table
Page Table Entry contains the physical address of page and the following bits:-
- Valid: whether the page content legal
- Reference: whether the page is referenced recently
- Modify: whether the page content is modified
- copy on write: kernel must create a new copy when a process modifies its content
- Age: Age of the page
- Protection: Read/ write permission
The pfdata table describes each page of physical memory. Fields of an entry are
- Page state.
- No. of processes that reference the page.
- Logical device and block number.
- Pointers to other pfdata table entries.
The swap use table contains an entry for every page on swap device
Fork in paging system
- The kernel of a swapping system makes a physical copy of the parent’s address space.
- On the paging system, the kernel avoids copying the page by manipulating the region tables, page table entries and increments the region reference count of shared regions.
- The kernel allocates a new region table entry and page table for data and stack regions and examines each parent page table entry.
- If page is valid, increments the reference countindicating the number of processes that share the page. If page exists on a swap device, it increments the swap use table reference count.
- The page can be referenced through both regions, which share a page until a process writes to it. The kernel copies it so that each region has a private version.
- If either process writes the page, it incurs a protection fault and in handling the fault, the kernel makes a new copy of the page for the faulting process. The physical copy is deferred until a process needs it.
- In BSD system
- The fork system call makes a physical copy of the pages of the parent process.
- It also contains the vfork system call, which assumes that a child process will immediately invoke exec on return from the vfork call.
- Vfork does not copy page tables, hence faster than System V implementation.
- Child process executes in the same physical address space as the parent process and can thus overwrite the parent’s date and stack.
Exec in paging systemOn a demand paged system, however the executable file may be too large to fit in main memory. The kernel does not preassign memory to the executable file but ‘faults’ it in, assigning memory as needed.
First assigns the page tables and disk block descriptors for the executable file, marking the page table entries “demand fill” or “demand zero’.
The fault handler notes whether the page is “demand fill”, meaning its contents will immediately be overwritten with the contents of the executable file so it need not be cleared, or that it is “demand zero,” meaning that its contents should be cleared.
If the process cannot fit into memory, the page stealer process periodically swaps pages from memory, making for the incoming file.
A process may incur a page fault while reading each page, even though it may never access the page. The page stealer may swap pages from memory before the exec is done. To make exec more efficient, the kernel can demand page directly from the executable file.
If a process incurs a page fault during a read system call it would overwrite the fields to read the page from the file system.
To page directly from the executable file, the kernel finds all the disk block numbers of the executable file when it does the exec and attaches the list to the file inode.
The page stealer process
First assigns the page tables and disk block descriptors for the executable file, marking the page table entries “demand fill” or “demand zero’.
The fault handler notes whether the page is “demand fill”, meaning its contents will immediately be overwritten with the contents of the executable file so it need not be cleared, or that it is “demand zero,” meaning that its contents should be cleared.
If the process cannot fit into memory, the page stealer process periodically swaps pages from memory, making for the incoming file.
A process may incur a page fault while reading each page, even though it may never access the page. The page stealer may swap pages from memory before the exec is done. To make exec more efficient, the kernel can demand page directly from the executable file.
If a process incurs a page fault during a read system call it would overwrite the fields to read the page from the file system.
To page directly from the executable file, the kernel finds all the disk block numbers of the executable file when it does the exec and attaches the list to the file inode.
The page stealer process
- The page stealer is a kernel process that swaps out memory pages that are no longer part of the working set of a process.
- The kernel creates the page stealer during system initialization and invokes it throughout the lifetime of the system when low on free pages. It locks a region when a process faults on a page in the region.
- There are two paging states for a page in memory: the page is aging and is not yet eligible for swapping or the page is eligible for swapping and is available for reassignment to other virtual pages.
- The first state indicates that a process recently accessed the page, and the page is in its working set and assigns a reference bit whenever a page is referenced.
- When the reference number exceeds a threshold value, the kernel puts the page into the second state ready to be swapped.
- If two or more processes share a region, they update the reference bits of the same set of page table entries. If a page is part of the working set of any process, it remains in memory; if it is not part of the working set of any process, it is eligible for swapping.
- When the page stealer decides to swap out a page, it considers whether a copy of the page is on a swap device. There are three possibilities:
- If no copy of the page is on the swap device, the kernel schedules the page for swapping: the page stealer places the page on a list of pages to be swapped out and continues. When the list of pages to be swapped reaches a limit, the kernel writes the pages to the swap device.
- If a copy of the page is already on the swap device and no process has modified its in core contents. The kernel clears the in core page table entry, decrements the reference count and puts the entry on free list for future allocation.
- If a copy of the page is on a swap device but a process has modified its contents in memory, the kernel schedules the page for swapping and frees the space it currently occupies on the swap device.
Page faults A page fault occurs when a process accesses a virtual page for which there is no page table entry(PTE) in the page table or whose PTE in some way prohibits the access, e.g., because the page is not present or because the access is in conflict with the access rights of the page.
Two types
- Validity faults
- Protection faults
When the fault handlers execute there is an I/O execution happening i.e., reading a page from disk to memory and hence fault handlers go to sleep which is an exception from other interrupt handlers.
Validity fault handler
Demand paging has a data structure called page table entry which has a valid bit.
If a process referring a page in the main memory whose valid bit is not set i.e., 0, it results in validity fault.
The valid bit is not set for those pages:
that are outside the virtual address space of a process
that are the part of the virtual address space of the process but no physical address is assigned to it.
Algorithm vfault(refer page 299)
Input: address where process faulted
Output: none
STEPS :-
Finds PTE and Disk block descriptor(DBD)
Locks the region
Finds if record is in disk block
If no exit by sending Segmentation violation signal
If yes allocate a page and initiate read process
Checks if page in cache
If yes update PTE
If contents not valid sleep till it becomes valid
If no assign new page and update PTE
Set the valid bit ,unlock the region
The page that caused faults can be in one of the 5 states:-
Validity fault handler
Demand paging has a data structure called page table entry which has a valid bit.
If a process referring a page in the main memory whose valid bit is not set i.e., 0, it results in validity fault.
The valid bit is not set for those pages:
that are outside the virtual address space of a process
that are the part of the virtual address space of the process but no physical address is assigned to it.
Algorithm vfault(refer page 299)
Input: address where process faulted
Output: none
STEPS :-
Finds PTE and Disk block descriptor(DBD)
Locks the region
Finds if record is in disk block
If no exit by sending Segmentation violation signal
If yes allocate a page and initiate read process
Checks if page in cache
If yes update PTE
If contents not valid sleep till it becomes valid
If no assign new page and update PTE
Set the valid bit ,unlock the region
The page that caused faults can be in one of the 5 states:-
On a swap device and not in memory It’s been swapped out of memory
Disk block descriptor contains the block info where the page is stored
Updates page table entry if not in cache to point it to the page about to be read
Initiates read operation
Faulting process sleeps until the completion of I/O
On the free page list in memory Page is swapped out but not been reassigned
Block number found in the disk block descriptor
Reassigns page table entry to point to the page just found
Remove from free list
In an executable fileExists on the executable file and not on swapping device
examines disk block descriptor, finds logical block number in the file that contains page, finds the inode
using disk block number it reads the page into memory
Marked “demand zero”kernel allocates free page in memory
updates the appropriate page table entry
it clears the page to zero and also “demand zero” flags marked “demand zero”
Marked “demand fill”kernel allocates free page in memory
updates the appropriate page table entry
it clears the “demand fill” flags
Validity fault handler concludes by setting validity bit of the page and clearing the modify bit
At the end checks for the process priority since it was put to sleep and also for the signals and returns to user mode
Protection fault handler
Protection fault refers to the process accessing the pages, which do not have the access permission. A process also incur the protection fault when it attempts to write a page whose copy on write bit was set during the fork() system call.
Algorithm pfault(refer page 304)Input: address where process faulted
Output: none
Steps:-Finds appropriate region, page table entry, disk block descriptor
Lock the region
If invalid page
Unlock the region and quit
If copy on write bit not set
Unlock the region and quit
If copy on write bit is set and if page is shared by another process i.e. page frame reference count is >1
Allocate a new page and copy the contents of the old page to it
Update page table entry with new page number
Decrement the reference count of old page frame data entry
If copy on write bit is set and if it’s not shared by any other process/* when no process is using it*/
If copy of page exists on swap device
Free space on swap disk wen count drops to 0
If page is on page hash queue
Remove from the queue
Set modify bit, Clear copy on write bit in page table entry
unlock the region
If the page is invalid the fault handler returns immediately and the process will incur a validity fault.
Validity fault is handled but the process will incur the protection fault again
At the end checks for the process priority since it was put to sleep and also for the signals and returns to user mode
Disk block descriptor contains the block info where the page is stored
Updates page table entry if not in cache to point it to the page about to be read
Initiates read operation
Faulting process sleeps until the completion of I/O
On the free page list in memory Page is swapped out but not been reassigned
Block number found in the disk block descriptor
Reassigns page table entry to point to the page just found
Remove from free list
In an executable fileExists on the executable file and not on swapping device
examines disk block descriptor, finds logical block number in the file that contains page, finds the inode
using disk block number it reads the page into memory
Marked “demand zero”kernel allocates free page in memory
updates the appropriate page table entry
it clears the page to zero and also “demand zero” flags marked “demand zero”
Marked “demand fill”kernel allocates free page in memory
updates the appropriate page table entry
it clears the “demand fill” flags
Validity fault handler concludes by setting validity bit of the page and clearing the modify bit
At the end checks for the process priority since it was put to sleep and also for the signals and returns to user mode
Protection fault handler
Protection fault refers to the process accessing the pages, which do not have the access permission. A process also incur the protection fault when it attempts to write a page whose copy on write bit was set during the fork() system call.
Algorithm pfault(refer page 304)Input: address where process faulted
Output: none
Steps:-Finds appropriate region, page table entry, disk block descriptor
Lock the region
If invalid page
Unlock the region and quit
If copy on write bit not set
Unlock the region and quit
If copy on write bit is set and if page is shared by another process i.e. page frame reference count is >1
Allocate a new page and copy the contents of the old page to it
Update page table entry with new page number
Decrement the reference count of old page frame data entry
If copy on write bit is set and if it’s not shared by any other process/* when no process is using it*/
If copy of page exists on swap device
Free space on swap disk wen count drops to 0
If page is on page hash queue
Remove from the queue
Set modify bit, Clear copy on write bit in page table entry
unlock the region
If the page is invalid the fault handler returns immediately and the process will incur a validity fault.
Validity fault is handled but the process will incur the protection fault again
At the end checks for the process priority since it was put to sleep and also for the signals and returns to user mode
