UNIT III

Memory-Management Strategies:
• Introduction
• Swapping
• Contiguous memory allocation
• Paging
• Segmentation
Virtual Memory Management:
• Introduction
• Demand paging
• Copy on-write
• Page replacement
• Frame allocation
• Thrashing
• Memory-mapped files
• Kernel memory allocation.
 Memory-Management Strategies:

Introduction:
• The main purpose of a computer system is to execute programs
• During execution, these programs, together with the data they access, must
be in main memory(at least partially)
Main Memory:
• Memory is central to the operation of a modern computer system. Memory
consists of a large array of bytes, each with its own address.
• The CPU fetches instructions from memory according to the value of the
program counter.
[Link]
[Link]
[Link]
[Link]
CPU Cycles Time for accessing memories:
• Registers – Accessible within one cycle of the CPU clock.
• Main Memory – Access may take many cycles of the CPU clock to complete.
The remedy is to add fast memory between the CPU and main memory. A
memory buffer used to accommodate a speed differential, called a CACHE .
Protection of OS from unauthorized access:
• user processes must be protected from one another
• This protection must be provided by the hardware
• For this we use two registers - BASE and LIMIT
• The base register holds the smallest legal physical
memory address.
• The limit register specifies the size of the range.
Address Binding
• Address binding is the process of mapping from one address space to
another address space.
• Depending on the memory management in use, the process may be moved
between disk and memory during its execution.
• Input queue select a processes ->load into memory ->executes and
accesses instructions and data from memory -> process terminates-> memory
space is declared available.
Addresses may be represented in different ways during these steps.
• Symbolic Addresses :Addresses in the source program
Eg.: variable names(such as variable i)
• Relocatable Addresses :A compiler typically
binds symbolic addresses to relocatable addresses
(in terms of offsets).
Eg:100 bytes from the beginning of this module
• Absolute Addresses :The linkage editor or loader
binds relocatable addresses to absolute addresses
(physical addresses). E.g:74014
Logical Versus Physical Address Space:
• Logical Address Space: The set of all logical addresses generated by a program.
• Physical Address Space: The set of all physical addresses corresponding to these
logical addresses
• In the execution-time address-binding scheme, the logical and physical address
spaces differ.
• The run-time mapping from virtual to
physical addresses is done by a hardware
device called the memory-management
unit (MMU)

Dynamic relocation using a relocation register

Linking and Loading are the utility programs that play a important role in the execution of a
program.
• Loading: Bringing the program from secondary memory to main memory is called Loading.
• Linking: Establishing the linking between all the modules or all the functions of the
program in order to continue the program execution is called linking.
Dynamic Linking and Shared Libraries:
When a program runs, apart from its own modules, it also needs to use certain System
Libraries as well.
• Static Linking: System libraries are treated like any other object module and are combined
by the loader into the binary program image.
• Dynamic Linking:Checks to see whether the needed routine is already in memory. If not,
the routine is loaded into memory.
Dynamically linked libraries:
With linking, a stub is included in the image for each library routine reference.
Stub:The stub is a small piece of code that indicates how to locate the appropriate memory-
resident library routine or how to load the library if the routine is not already present.
 Swapping
• A process must be loaded into memory in order to execute.
• A process, however, can be swapped temporarily out of memory to a
backing store and then brought back into memory continued execution
Example:
• In a multiprogramming environment with a round-robin CPU-scheduling
algorithm.
• When a quantum expires the memory manager will start to swap out the
process that just finished and to swap another process in to the memory
space that has been freed

Swapping of two processes using a disk as a backing store

When Swapping Happens
• A variation of swap is priority based scheduling.
• When a low priority is executing and if a high priority process arrives then a low priority
will be swapped out and high priority is allowed for execution.
• This process is also called as Roll out and Roll in.
• Normally the process which is swapped out will be swapped back to the same memory
space that is occupied previously.
• This depends upon address binding.
• If the binding is done at load time, then the process is moved to same memory location.
• If the binding is done at run time, then the process is moved to different memory location.
• This is because the physical address is computed during run time.
Swapping is constant by other factors:
• To swap a process, it should be completely idle. A process may be waiting for an i/o
operation.
• If the i/o is asynchronously accessing the user memory for i/o buffers, then the process
cannot be swapped.
 Memory Management Techniques
The memory is usually divided into two partitions:
• for the resident operating system
• for the user processes.
Memory Management Techniques are basic techniques that are used in
managing the memory in operating system.
Memory Management Techniques are basically classified into two categories:
(i) Contiguous:
(ii) Non-contiguous:
Contiguous Memory Allocation :
Contiguous memory allocation is basically a method in which a single
contiguous section/part of memory is allocated to a process or file needing
it.
• There are two popular techniques used for contiguous memory
allocation_x0002_
Fixed Partition Scheme
Fixed Partition Scheme is also called as Static Partitioning or Multiprogramming
With Fixed Size Partition.
• In the fixed partition scheme, memory is divided into fixed number of partitions.
• In the fixed partition, in every partition only one process will be accommodated.
• Degree of multi-programming is restricted by number of partitions in the
memory.
• Maximum size of the process is restricted by maximum size of the partition.
• Every partition is associated with the limit registers.
Limit Registers: It has two limit:
 Lower Limit: Starting address of the partition.
 Upper Limit: Ending address of the partition.
• In this partitioning, number of partitions (non-overlapping) in RAM is fixed but size of
each partition may or may not be same.
Example:
• first process is only consuming 1MB out of 4MB in the main memory.
• Hence, Internal Fragmentation in first block is (4-1) = 3MB.
• Sum of Internal Fragmentation in every block
= (4-1)+(8-7)+(8-7)+(16-14)= 3+1+1+2 = 7MB.
• Suppose process P5 of size 7MB comes.
But this process cannot be accommodated inspite of
available free space because of contiguous allocation.
Hence 7MB becomes part of External Fragmentation.
Advantages of Fixed Partitioning –Easy to implement
Disadvantages of Fixed Partitioning –Internal Fragmentation,
External Fragmentation,Limit process size,
Variable Partition Scheme
Variable Partition Scheme is also called as DynamicPartitioning or Multiprogramming
with variable size partition.
• In the variable partition scheme, initially memory will
be single continuous free block.
• Whenever the request by the process arrives,
accordingly partition will be made in the memory.
• If the smaller processes keep on coming then
the larger partitions will be made into smaller partitions.
• It is used to alleviate the problem faced by Fixed Partitioning.
In contrast with fixed partitioning, partitions are not made
before the execution or during system configure.
Advantages-No Internal Fragmentation,No restriction on Degree of
Multiprogramming,No Limitation on the size of the process and limitation of partitions.
Disadvantages-Difficult Implementation,External Fragmentation.
• To overcome the problem of external fragmentation, compaction technique is
used or non-contiguous memory management techniques are used.
Compaction:
• Moving all the processes toward the top or towards the bottom to make free
available memory in a single continuous place is called as compaction.
Compaction is undesirable to implement because it interrupts all the running
processes in the memory.
Memory Allocation or Dynamic Storage-
Allocation Problem
How to satisfy a request of size n from a list of free holes?
• First-fit:Allocate the first hole that is big enough
• Best-fit:Allocate the smallest hole that is big enough
• Worst-fit:Allocate the largest hole
• Next Fit:Next fit is a modified version of ‘first fit’. It begins as the first fit to
find a free partition but when called next time it starts searching from where
it left off, not from the beginning.

First-fit
 Non-Contiguous Memory Allocation
• Non-contiguous memory allocation is a memory allocation technique.
• Thus, different parts of the same process can be stored at different places in the main memory.

Paging:
• Paging is another memory-management
scheme and paging avoids external fragmentation
• Paging is implemented through cooperation
between the operating system and
the computer hardware.

Paging model of logical and

physical memory
• The basic method for implementing paging involves breaking physical memory
into fixed-sized blocks called frames
• A process is divided into number of partitions called the Pages
• When a process is to be executed, its pages are loaded into any available
memory frames from their source .
• Page size must be same size as the memory frame or clusters of multiple
frames.
• A logical address is generated by CPU while a program is running. Since a
logical address does not physically exists it is also known as a virtual address.
• This address is used as a reference by the CPU to access the actual physical
memory location.
• There is a hardware device called Memory-Management Unit is used for
mapping logical address to its corresponding physical address.
• A physical address identifies the physical location of a specific data element
in memory.
• Every address generated by the CPU is divided into two parts: a page number
(p) and a page offset (d).
• The page number is used as an index into
a page table.
• The page table contains the base address of
each page in physical memory.
• This base address is combined with the
page offset to define the physical memory address
that is sent to the memory unit.
Paging hardware
• Example: Using a page size of 4 bytes and a physical memory of 32 bytes
We have to check which frame the corresponding page available Logical
address 0 is page 0, offset 0.
• Indexing into the page table,
we find that page 0 is in frame 5.
Thus, logical address 0 maps to
 physical address = [(5 × 4) + 0]=20.
• Logical address 3 (page 0, offset 3) maps to
 physical address =[ (5 × 4) +3]=23
Hardware Implementation of Page table
Case1: The page table is implemented as a set of dedicated registers.
Problem: This can be used only when page table is reasonably small.
Case2:Keep the page table in main memory, and a page-table base
register (PTBR) points to the page table.
Problem: the time required to access a user memory
location is increased as there are two memory
access needed to access a byte.
Solution: Making use of Translation Lookaside Buffer(TLB)
• The TLB is associative, high-speed memory.
• Each entry in the TLB consists of two parts:
 a key (or tag)
Paging hardware with TLB.
 a value.
• When the associative memory is presented with an item, the item is compared with all keys
simultaneously. If
the item is found, the corresponding value field is [Link] search is fast;
Structure of the Page Table
• Most modern computer systems support a large logical address space (232 to
264
).
• In such an environment, the page table itself becomes excessively large.
• For example,
• Consider a system with a 32-bit logical address space.
• If the page size = 4 KB (212)then a page table may consist of up to (232/212)
= 1 million entries(approx)
• Consider each entry consists of 4 bytes of data
• So each process may need up to (4*1 million) bytes= 4 MB of physical address
space
• Trying to allocate a Page Table of this size contiguously in main memory is
clearly not a good idea
Hierarchical Paging
• Solution: One simple solution to this problem is to divide the page table into
smaller sizes.
• Multilevel Paging is also called Hierarchal Paging Use a two-level paging
algorithm, in which the page table itself is also paged
• Page Number (p) – used as an index into a page table Page Offset(d)
• P1 – Index into the outer page table
• P2- Displacement within the pages of the outer page table
• Page Offset(d) – The displacement within the pages complete the work
Hashed Page Tables
• A common approach for handling address spaces larger than 32 bits is to use a
hashed page table.
• The hash value being the virtual page number(page number present in logical
address).
• Each entry in the hash table contains a linked list of elements that hash to the
same location.
Each element consists of three fields:
• The virtual page number,
• The value of the mapped page frame, and
• A pointer to the next element in the linked list.
Clustered Page Table
• A variation of this scheme that is useful for 64-bit address spaces.
• It is similar to the hashed page tables except that each entry in the hash table refers to
several pages rather than a single page.
• Therefore, a single page-table entry can store the mappings for multiple physical-page
frames.
• Clustered page tables are particularly useful for sparse address spaces, where memory
references are non_x0002_contiguous and scattered throughout the address space.
Inverted Page Tables
• An inverted page table has one entry for each real page (or frame) of memory.
• Each entry consists of the virtual address of the page stored in that real memory
location, with information about the process that owns the page.
• Thus, only one page table is in the system, and it has
only one entry for each page of physical memory.
• virtual address in the system consists of a triple:
 Segmentation
Segmentation is another non-contiguous memory allocation technique like paging
• Unlike paging ,in segmentation , the processes are not divided into fixed size pages
• Instead ,the processes are divided into several modules called segments which improves the
visualization for the users
• So, here the both secondary memory and main memory are divided into partitions of unequal size
• A logical address space is a collection of segments.
• Each segment has a name and a length.
• The addresses specify both the segment name and the offset within the segment.
• The programmer therefore specifies each address by two quantities:
 a segment name
 an offset.
Thus, a logical address consists of a two tuple:
<Segment-number, offset>.

Programmer’s
view of a program.
Segment Table
• Thus, we must define an implementation to map two_x0002_dimensional
user-defined addresses into one-dimensional physical addresses.
• This mapping is effected by a segment table.
• Each entry in thesegment table has a segment base and a segment
limit(length of the segment).
• The segment base contains the starting physical address where the segment
resides in memory, and the segment limit specifies the length of the segment
Segmentation Hardware
• Although the programmer can now refer to objects in the program by a two-dimensional
address, the actual physical memory is still, of course, a one dimensional sequence of bytes.
• Thus, we must define an implementation to map
two-dimensional user-defined addresses into
one-dimensional physical address.
For example, segment 2 is 400 bytes long and
begins at location 4300.
• Thus, a reference to byte 53 of segment 2 is
mapped onto location 4300 + 53 = 4353.
• A reference to segment 3, byte 852, is mapped to
3200(the base of segment 3) + 852 = 4052.
• A reference to byte 1222 of segment 0 would
result in a trap to the operating system, as this
segment is only 1,000 bytes long.
Why Virtual Memory
• Virtual memory is a storage scheme where secondary memory can be treated as though it is a
part of main memory and large processes can be stored in it.
Only the part of process that is actually needed for execution
will be loaded on the actual memory.
An examination of real programs shows us that:
• Programs often have code to handle unusual error
conditions. Since these errors seldom, if ever, occur in
practice, this code is almost never executed.
• Arrays, lists, and tables are often allocated more memory than they actually need.
An array may be declared 100 by 100 elements, even though it is seldom larger than 10 by 10 elements.
• An assembler symbol table may have room for 3,000 symbols, although the average program has less than
200 symbols.
Diagram showing virtual memory that is larger than physical memory.
Virtual memory involves the separation of logical memory as perceived by users from physical memory.
This separation allows an extremely large virtual memory to be provided for programmers when only a smaller
physical memory is available
Demand Paging
• Consider how an executable program loaded from disk into memory?
• Load pages only as they are needed pages are loaded
only when they are demanded during program
execution. Pages that are never accessed are thus
never loaded into physical memory.
This is called Demand Paging
• A demand-paging system is similar to a paging
system with swapping where processes reside in
secondary memory (usually a disk).
• When we want to execute a process, we swap it into memory rather than swapping the entire
process into memory, though, we use a lazy swapper.
• A lazy swapper never swaps a page into memory unless that page will be needed.
• We thus use “pager,” rather than “swapper,” in connection with demand paging.
• A swapper manipulates entire processes, whereas a pager is concerned with the individual
pages of a process.
Hardware Implementation of Demand Paging
• The pager takes care of swapping pages in and out of the memory.
• How can the hardware implementation to be done to to distinguish between
the pages that are in memory and the pages that are on the disk.
• We can make use of the Present/Absent Bit or Valid/Invalid Bit
• If Bit is set to “VALID,” the associated page is both legal and in memory.
• If the bit is set to “INVALID,” the page either is not in the logical address
space of the process or is valid but is currently on the disk.
Page Table Entries
• The page-table entry for a page that
is brought into memory is set as usual.
• The page-table entry for a page that
is not currently in memory is either
simply marked invalid or contains
the address of the page on disk
( Secondary memory).

Page table when some pages are not in main memory.

Page Fault
• But what happens if the process tries to access a page that was not brought into memory? Access to a page
marked invalid causes a page fault.
• The paging hardware, in translating the address through the page table, will notice that the invalid bit is set,
causing a trap to the operating system.
A page fault may occur at any memory reference:
• If the page fault occurs on the instruction fetch, we can restart by fetching the instruction again.
• If the a page fault occurs while we are fetching an operand, we must fetch and decode the instruction again
and then fetch the operand.
Consider a three-address instruction such as ADD the content of A to B, placing the result in C. These are the
steps to
execute this instruction:
• 1. Fetch and decode the instruction (ADD).
• 2. Fetch A.
• 3. Fetch B.
• 4. Add A and B.
• 5. Store the sum in C
The procedure for handling this page fault:
1. We check an internal table (usually kept with the
process control block) for this process to determine
whether the reference was a valid or an invalid memory
access.
2. If the reference was invalid, we terminate the process.
[Link] it was valid but we have not yet brought in that page,
we now page it in.
4. We find a free frame
5. We schedule a disk operation to read the desired page
into the newly allocated frame.
6. When the disk read is complete, we modify the
internal table kept with the process and the page table to
indicate that the page is now in memory.
7. We restart the instruction that was interrupted by the trap.
Performance of Demand Paging
• A computer system’s can be significantly affected by Demand paging .
• Let us see how ,by taking a look at the Effective Access Time.
• the memory-access time( ma) ranges from 10 to 200 nanoseconds.
• If there no page faults, the effective access time is equal to the memory
access time.
• But what if a page fault occurs?
• Let p be the probability of a page fault (0 ≤ p ≤ 1).
Effective Access Time =(1 − p) × ma + p × page fault time.
Where (1 − p) × ma: Time spent for normal memory access
p × page fault time: Time Spent for handling page fault
Copy-on-Write
Copy on Write(CoW) is a technique that is used for sharing virtual memory or
pages.
• It is mostly used in conjunction with the fork()
system call that is used for creating child processes.
• Fork() will create a copy of the parent’s address
When pages are shared between P1 and P2 and
space for the child, duplicating the pages belongingno modificationto the pages are done yet
to the parent.
• Instead of doing this we can optimize this method by
making the parent and child processes to share the
common pages and only create a copy when one of the
processed(either child or parent) wants to write(modify)
After process 1 modifies page C.
a [Link] technique is called Copy and Write
Problems of Demand paging
• With the help of demand paging, we are increasing our degree of multiprogramming by
loading the required
pages into memory hence facilitating the possibility of having more processes loaded into
memory.
This could lead to over-allocation of memory.
• Example:Suppose we have 40 frames in memory.
• We have 6 processes each of which has 10 pages but uses only 5 at the moment.
• We can load these(6*5)=30 pages into the memory
• So all the processes are executing simultaneously.
• Still we have 10 frames free.
• Now at some point let’s say all the 6 processes wants to use all their 10 pages.
So we need to load the remaining
(6*5)=30pages into memory, while we have
only 10 free frames.
Need for page replacement
• [Link] could terminate the user process.
– Not the best choice as it destroys the purpose of Demand paging
• [Link] operating system could instead swap out a process, freeing all its frames and reducing the level of
multiprogramming.
– A good option in certain circumstances.
• [Link] can make use of PAGE REPLACEMENT technique.
– The most common solution
Page Replacement
• Page Replacement is the technique of swapping out pages from physical memory when there are more free
frames available in order to make room for other pages which has to be loaded to the physical memory
• If a process wants to use/access a page which is not present in physical memory ,it will cause [Link],that page
has to be now loaded into memory.
• But if there are no free frames available to load that page, what should we do then?
• We look for an occupied frame that is not being used currently.
• We free that by writing its contents to the swap space.
• We update the pages tables(and other tables) to indicate that the pages is now no more in memory
• We load the page of the process that caused the pages fault to occur into the freed frame
Page-fault service time when no frames are free
• If no frames are free, two page transfers
(one out and one in) are required.
• This doubles the page-fault service time
and increases the effective access time accordingly
How can we reduce this?
• We can make use of the modify (Dirty )Bit.
• The modify bit is set when a page has been modified .
• So, when pages replacement has to be done
on a page which is present in memory.
• If the bit is set That the page has been modified
and we need to write to the disk.
• If the modify bit is not set That means the page has not
been modified and it is the same as the copy which is already present in the disk. In this case, we
don’t have to overwrite this pages on the disk ,thus reducing the overhead and the effective access
time accordingly
FIFO Page Replacement
• The simplest page-replacement algorithm is a first-in, first-out (FIFO) algorithm.
• When a page must be replaced, the oldest page is chosen to be swapped out.
How to maintain a record of the time that were brought into memory in order to figure out which
is the oldest page?
– We not strictly necessary to record the time.
– Instead we can use a FIFO queue that can hold all the pages that are in memory
– When replacement has to be done, we choose the page at the head of the queue to be
swapped.
– When a new page is loaded into memory, we add it at the tail of th queue
Example
• Consider reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 where each
value represents a page.
Lets say we have 3 frames in memoryAlso, let's consider a queue that can hold
all the pages that are loaded in memory
Hit ratio = Total number of page hits / Total number of references
Miss ratio= Total number of page misses / Total number of
references
Belady’s anomaly:
General Expectation about the relation between number of frames in memory
and number of page faults.
Increasing the number of page frames results in an increase in the number of
page faults for certain memory access patterns.

Graph of page faults versus number of frames

LRU Page Replacement
• LRU replacement associates with each page the time of that page’s last use.
• When a page must be replaced, LRU chooses the page that has not been used
for the longest period of time.
• It is almost the optimal page-replacement algorithm looking backward in
time, rather than forward.
Example:
• Consider the reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0
1Where each value represents a [Link]’s say we have 3 frames in
memory
Optimal Page Replacement:
Replace the page that will not be used for longest period of time in the
future
• An optimal page-replacement algorithm—the algorithm that has the
lowest page-fault.
• It will never suffer from Belady’s anomaly.
• This page-replacement algorithm guarantees the lowest possible page fault
rate for a fixed number of frames.
Example:
• Consider the reference string: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 Where
each value represents a page.
Let’s say we have 3 frames in memory
Least Frequently Used(LFU) Page-Replacement Algorithm
• COUNTER-Keeps a count of the number of references made to each page.
• Pages which are least used- will have lesser counts.
• Pages which are frequently- will have greater counts.
• Replace the page with the least count.
• Problem: Pages that were heavily used during the initial phase of phase of
processes would have higher counts and would remain in memory though they
may not be needed further.
• Solution: Shift the counts right by 1 bit at regular intervals, forming an
exponentially decaying average usage count
Most Frequently Used(MFU) Page Replacement Algorithm
• COUNTER-Keeps a count of the number of references made to each page.
• Pages which are least used- will have lesser counts.
• Pages which are frequently used - will have a greater counts.
• Based on the argument that the page with the smallest count was probably
just brought in and is yet to be used.
• DO not replace the page with the least count Both LFU and MFU algorithms
are
o Expensive to implement and
o They also Do not approximate Optimum page Replacement well.
• Hence they are not usually used
Frame allocation
• An important aspect of operating systems, virtual memory is implemented
using demand paging. Demand paging necessitates the development of a
page-replacement algorithm and a frame allocation algorithm. Frame
allocation algorithms are used if you have multiple processes; it helps
decide how many frames to allocate to each process.
• There are various constraints to the strategies for the allocation of frames:
• You cannot allocate more than the total number of available frames.
• At least a minimum number of frames should be allocated to each process.
This constraint is supported by two reasons. The first reason is, as less
number of frames are allocated, there is an increase in the page fault ratio,
decreasing the performance of the execution of the process. Secondly, there
should be enough frames to hold all the different pages that any single
instruction can reference.
Frame allocation algorithms
• The two algorithms commonly used to allocate frames to a process are:
Equal Allocation
• The frames are equally distributed among the processes
• If we have m number of frames.
• If we have n number of Processes.
Example:
– Number of frames:98
– Number of Process:5
– Each process gets = 98/5=19 frames
• The remaining 3 frames are kept as free-frames buffer pool.
Proportional Allocation
• The frames are distributed among the processes according to their sizes
Let
– m be the number of frames.
– si be the process pi
– Number of frames allocated to pi=ai
Where
Example
• In a system with 64 free frames where frame size =1KB,say we have just
• 2 process- P1-10kb AND P2-127KB.
Here m=64, Si=10kb, S2=127kb
S=si+s2=(10+127)kb=137 kb
Frame allocation to P1= a1=s1/S*m=10/137*64=5(appro)
• Frame allocation to P2= a2=s2/S*m=127/137*64=59(appro)
Priority Allocation
• The frames are distributed among the processes according to their priorities.
• Here we implement a proportional allocation scheme using priorities or a combination of
size and priorities rather than just size of the processes.
• So, we allocate more frames to processes with higher priorities so as to speed up their
execution
Global vs Local Allocation –
The number of frames allocated to a process can also dynamically change depending on
whether you have used global replacement or local replacement for replacing pages in case
of a page fault.
• Local replacement and global replacement differ in that local replacement restricts a
process to only allocate pages within its own allocated frames, while global replacement
allows a process to allocate pages from any available frames in the system, regardless of
the process to which they were previously assigned.
Thrashing:
It occurs when the system spends more time swapping pages than actually
performing useful tasks.
Sever Performance Problem due to Thrashing
The operating system monitors CPU utilization. If CPU utilization is too low,
we increase the degree of multiprogramming by introducing a new process
to the system.
Locality Model
• A locality is a set of pages that are actively used together. The locality model
states that as a process executes, it moves from one locality to another. A
program is generally composed of several different localities which may
overlap.

Techniques to handle:
1. Working Set Model
• This model is based on the above-stated concept of the Locality Model.
• The basic principle states that if we allocate enough frames to a process to
accommodate its current locality, it will only fault whenever it moves to
some new locality. But if the allocated frames are lesser than the size of the
current locality, the process is bound to thrash.
• The accuracy of the working set depends on the selection of_.
• If is too small, it will not encompass the entire locality;
• If is too large, it may overlap several localities.
• if is infinite, the working set is the set of pages touched during the process
execution.
• The most important property of the working set, then, is its size. If we
compute the working-set size, WSSi , for each process in the system, we can
then consider that

• If the total demand for frames D exceeds the available frames m (i.e., 𝐷>𝑚),
thrashing will occur.
• In response, the OS will select a process to suspend, swap out its pages, and
reallocate its frames to other processes. The suspended process can be
restarted later.
2. Page Fault Frequency
• A more direct approach to handling thrashing is through the Page-Fault
Frequency (PFF) concept, which aims to control the page fault rate.
• A high page fault rate suggests that a process has too few frames allocated,
while a low page fault rate indicates that it has too many frames.
• Upper and lower limits can be established on the desired page fault rate as
shown in the diagram.
• If the page fault rate falls below the lower limit, frames can be removed from
the process. Similarly, if the page fault rate exceeds the upper limit, more frames
can be allocated to the process.
Memory-mapped files:
• We can use standard system calls like read(), seek(), open(), and so on to
perform a sequential read of a file present on the disk.
• Thus, to access a file from the disk we need system calls and disk access.
Memory mapping is a technique that allows a part of the virtual address
space to be associated with a file logically.
• This technique of memory mapping leads to a significant increase in
performance.
Basic Mechanism of Memory Mapping
•The Operating System uses virtual memory for memory mapping a file by mapping
a disk block to a page in physical memory. Initially accessed through demand paging,
if a process references an address not in physical memory, a page fault occurs, and
the OS loads the missing page into memory.
•A page-sized portion of the file is loaded from the file system into physical memory.
• Accessing files via memory, instead of using read() and write() system calls,
simplifies and speeds up file operations.
• Multiple processes can map the same file simultaneously, enabling data sharing.
• If one process writes data in virtual memory, the changes are visible to all
processes mapping the same file section.
• The memory mapping system calls support copy-on-write functionality which
allows processes to share a file in read-only mode but the processes can have their
own copies of data that they have modified.
• The sharing of memory is depicted with the help of a diagram shown
below.
Types of Memory Mapped Files
• Basically, there are two types of memory mapped files:

• Persisted: Persisted files are connected with a source file on a disk. After
completing the final process, the data is saved to the source file on disc.
Working with very big source files is appropriate with these type of
memory-mapped files.
• Non-persisted: Non-persisted files are not connected to any disk-based
files. The data is lost when the last process with the file completes its
required task. The shared memory that these files enable for inter-process
communications or IPC.
Kernel memory allocation
• Allocating kernel memory is a critical task in operating system design, as the
kernel needs to manage memory efficiently and effectively to ensure optimal
system performance. Two common methods for allocating kernel memory are
the buddy system and the slab system.
1. Buddy system –
• Buddy allocation system is an algorithm in which a larger memory block is
divided into small parts to satisfy the request.
• This algorithm is used to give best fit.
• The two smaller parts of block are of equal size and called as buddies.
• In the same manner one of the two buddies will further divide into smaller
parts until the request is fulfilled.
• Benefit of this technique is that the two buddies can combine to form the
block of larger size according to the memory request.
Example – If the request of 25Kb is made then block of size 32Kb is allocated.
Four Types of Buddy System
• Binary buddy system-It is a memory allocation scheme that divides memory into
partitions to minimize fragmentation by splitting blocks into halves.
• Fibonacci buddy system- It is a memory allocation method where memory
blocks are split based on Fibonacci sequence sizes to reduce fragmentation
compared to the Binary Buddy System
• Weighted buddy system-It is a memory allocation technique that improves
the standard buddy system by using different weight factors to allow more
flexible block sizes, thereby reducing internal fragmentation.
• Tertiary buddy system- It is a variation of the buddy system that divides
memory blocks into thirds rather than halves, aiming to provide more
flexibility and reduce fragmentation in memory allocation.
2. Slab Allocation –
• A second strategy for allocating kernel memory is known as slab allocation.
• It eliminates fragmentation caused by allocations and deallocations. This
method is used to retain allocated memory that contains a data object of a
certain type for reuse upon subsequent allocations of objects of the same
type.
• In slab allocation memory chunks suitable to fit data objects of certain type
or size are preallocated.
• Cache does not free the space immediately after use although it keeps track
of data which are required frequently so that whenever request is made the
data will reach very fast.
Two terms required are:
• Slab – A slab is made up of one or more physically contiguous pages. The slab
is the actual container of data associated with objects of the specific kind of
the containing cache.
• Cache – Cache represents a small amount of very fast memory. A cache
consists of one or more slabs. There is a single cache for each unique kernel
data structure.