Unit 4

MEMORY MANAGEMENT
Main Memory: Background – Swapping - Contiguous Memory Allocation – Segmentation – Paging - Structure
of the Page Table – Virtual Memory: Background - Demand Paging - Copy-on-Write - Page Replacement -
Allocation of Frames – Thrashing - Memory-Mapped Files - Allocating Kernel Memory.
Introduction to Memory
Memory Background
Role of OS in memory management
Role of Memory
• A typical instruction-execution cycle, for example, first fetches an
instruction from memory.
• The instruction is then decoded and may cause operands to be fetched
from memory.
• After the instruction has been executed on the operands, results are stored
back in memory.
• Main memory and the registers built into the processor itself are the only
general-purpose storage that the CPU can access directly.
• Registers that are built into the CPU are generally accessible within one
cycle of the CPU clock.
Process and Address
• Each process has a separate memory space.
• Separate per-process memory space protects the processes from each other
and is fundamental to having multiple processes loaded in memory for
concurrent execution.
• To separate memory spaces, we need the ability to determine the range of
legal addresses that the process may access and to ensure that the process
can access only these legal addresses.
A base and a limit register define a logical
address space.
• 300040 and the limit register is 120900, then the
program can legally access all addresses from 300040
through 420939 (inclusive).
• Any attempt by a program executing in user mode to
access operating-system memory or users’ memory
results in a trap to the operating system, which treats
the attempt as a fatal error.
• This scheme prevents a user program from
(accidentally or deliberately) modifying the code or
data structures of either the operating system or other
users.
Base and limit register
• The base and limit registers can be loaded only by the operating system,
which uses a special privileged instruction.
• Since privileged instructions can be executed only in kernel mode, and
since only the operating system executes in kernel mode, only the
operating system can load the base and limit registers.
• This scheme allows the operating system to change the value of the
registers but prevents user programs from changing the registers’ contents.
Address Binding
• A program resides on a disk as a binary executable file.
• To be executed, the program must be brought into memory and placed
within a process.
• Depending on the memory management in use, the process may be moved
between disk and memory during its execution.
• The processes on the disk that are waiting to be brought into memory for
execution form the input queue.
• The normal single-tasking procedure is to select one of the processes in the
input queue and to load that process into memory.
Address Binding (Cont..)
• Most systems allow a user process to reside in any part of the physical memory.
• Thus, although the address space of the computer may start at 00000, the first
address of the user process need not be 00000.
• Addresses may be represented in different ways during these steps.
• Addresses in the source program are generally symbolic (such as the variable count).
• A compiler typically binds these symbolic addresses to relocatable addresses (such
as “14 bytes from the beginning of this module”).
• The linkage editor or loader in turn binds the relocatable addresses to absolute
addresses (such as 74014).
• Each binding is a mapping from one address space to another.
• The binding of instructions and data to memory addresses can be done at any step
like compile time, load time, execution time.
Dynamic Linking and Shared Libraries
• Some operating systems support only static linking, in which system
libraries are treated like any other object module and are combined by the
loader into the binary program image.
• Dynamic linking, in contrast, is similar to dynamic loading. Here, though,
linking, rather than loading, is postponed until execution time.
• With dynamic linking, a stub is included in the image for each library
routine reference.
• 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.
Types of Loading
 Dynamic Loading
• The size of a process has thus been limited to the size of physical memory. To
obtain better memory-space utilization, we can use dynamic loading.
• With dynamic loading, a routine is not loaded until it is called. All routines are
kept on disk in a relocatable load format.
• The advantage of dynamic loading is that a routine is loaded only when it is
needed.
• This method is particularly useful when large amounts of code are needed to
handle infrequently occurring cases, such as error routines.
• It is the responsibility of the users to design their programs to take advantage of
such a method. Operating systems may help the programmer, however, by
providing library routines to implement dynamic loading.
Logical Versus Physical Address Space
• An address generated by the CPU is commonly referred to as a logical
address (virtual address), whereas an address seen by the memory unit—
that is, the one loaded into the memory-address register of the memory is
commonly referred to as a physical address.
• The set of all logical addresses generated by a program is a logical address
space.
• The set of all physical addresses corresponding to these logical addresses
is a physical address space.
• The compile-time and load-time address-binding methods generate
identical logical and physical addresses.
• Execution time → Different logical (virtual) and physical address.
Runtime mapping Virtual MMU Physical
Memory Management Unit (MMU)
• The run-time mapping from virtual to physical addresses is done by a
hardware device called the memory-management unit (MMU).
• The base register is now called a relocation register.
• The value in the relocation register is added to every address generated by
a user process at the time the address is sent to memory.
• The user program never sees the real physical addresses.
• We now have two different types of addresses: logical addresses (in the
range 0 to max) and physical addresses (in the range R + 0 to R + max for a
base value R).
Swapping
• A process must be in memory to be executed.
• A process, however, can be swapped temporarily out of memory to a
backing store and then brought back into memory for continued
execution.
• Swapping makes it possible for the total physical address space of all
processes to exceed the real physical memory of the system, thus
increasing the degree of multiprogramming in a system.
• Standard swapping involves moving processes between main memory
and a backing store.
Swapping of two process
What is a backing store ?
• The backing store is commonly a fast disk.
• Large enough to accommodate copies of all memory images for all
users, and it must provide direct access to these memory images.
• The system maintains a ready queue consisting of all processes
whose memory images are on the backing store or in memory and are
ready to run.
• Whenever the CPU scheduler decides to execute a process, it calls the
dispatcher.
• The dispatcher checks to see whether the next process in the queue is
in memory
Standard swapping
• The major part of the swap time is transfer time.
• The total transfer time is directly proportional to the amount of
memory swapped.
• If we want to swap a process, we must be sure that it is
completely idle.
• Never swap a process with pending I/O, or execute I/O operations
only into operating-system buffers.
• It requires too much swapping time and provides too little
execution time to be a reasonable.
Memory Allocation
• The main memory must accommodate both the operating system
and the various user processes.
• We can place the operating system in either low memory or high
memory.
• Since the interrupt vector is often in low memory, programmers
usually place the operating system in low memory as well.
• In contiguous memory allocation, each process is contained in a
single section of memory that is contiguous to the section
containing the next process.
Memory Allocation (Cont..)
• One of the simplest methods for allocating memory is to divide memory
into several fixed-sized partitions.
• In this multiple partition method, when a partition is free, a process is
selected from the input
• queue and is loaded into the free partition.
• When the process terminates, the partition becomes available for another
process.
• In the variable-partition scheme, 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 one
large block of available memory, a hole.
Memory Allocation (Cont..)
• In general, as mentioned, the memory blocks available comprise a set of
holes of various sizes scattered throughout memory.
• When a process arrives and needs memory, the system searches the set for
a hole that is large enough for this process.
• If the hole is too large, it is split into two parts.
• One part is allocated to the arriving process; the other is returned to the set
of holes.
• If the new hole is adjacent to other holes, these adjacent holes are merged
to form one larger hole.
• System may need to check whether there are processes waiting for
memory and whether this newly freed and recombined memory could
satisfy the demands of any of these waiting processes.
How to satisfy a request of size n from a
list of free holes ?
• First fit. Allocate the first hole that is big enough. Searching can start
either at the beginning of the set of holes or at the location where the
previous first-fit search ended. We can stop searching as soon as we find a
free hole that is large enough.
• Best fit. Allocate the smallest hole that is big enough. We must search the
entire list, unless the list is ordered by size. This strategy produces the
smallest leftover hole.
• Worst fit. Allocate the largest hole. Again, we must search the entire list,
unless it is sorted by size. This strategy produces the largest leftover hole,
which may be more useful than the smaller leftover hole from a best-fit
approach.
External Fragmentation
• Both the first-fit and best-fit strategies for memory allocation suffer from
external fragmentation.
• As processes are loaded and removed from memory, the free memory
space is broken into little pieces.
• External fragmentation exists when there is enough total memory space to
satisfy a request but the available spaces are not contiguous: storage is
fragmented into a large number of small holes.
• In the worst case, we could have a block of free (or wasted) memory
between every two processes. If all these small pieces of memory were in
one big free block instead, we might be able to run several more processes.
Internal Fragmentation
• Statistical analysis of first fit, for instance, reveals that, even with some
optimization, given N allocated blocks, another 0.5 N blocks will be lost to
fragmentation. That is, one-third of memory may be unusable! This
property is known as the 50-percent rule.
• Memory fragmentation can be internal as well as external.
• Consider a multiple-partition allocation scheme with a hole of 18,464
bytes.
• Suppose that the next process requests 18,462 bytes.
• If we allocate exactly the requested block, we are left with a hole of 2 bytes.
The overhead to keep track of this hole will be substantially larger than the
hole itself.
Internal Fragmentation
• The general approach to avoiding this problem is to break the physical
memory into fixed-sized blocks and allocate memory in units based on
block size.
• With this approach, the memory allocated to a process may be slightly
larger than the requested memory. The difference between these two
numbers is internal fragmentation—unused memory that is internal to a
partition.
• One solution to the problem of external fragmentation
is compaction
Compaction
• The goal is to shuffle the memory contents to place all free memory
together in one large block.
• Compaction is not always possible, however.
• If relocation is static and is done at assembly or load time, compaction
cannot be done.
• Compaction is possible only if relocation is dynamic and is done at
execution time.
• If addresses are relocated dynamically, relocation requires only moving
the program and data and then changing the base register to reflect the
new base address.
Compaction (Cont..)
• The simplest compaction algorithm is to move all processes toward one
end of memory; all holes move in the other direction, producing one large
hole of available memory. This scheme can be expensive.
• Another possible solution to the external-fragmentation problem is to
permit the logical address space of the processes to be noncontiguous, thus
allowing a process to be allocated physical memory wherever such
memory is available.
Solution to external-Fragmentation
• Another possible solution to the external-fragmentation
problem is to permit the logical address space of the processes
to be noncontiguous, thus allowing a process to be allocated
physical memory wherever such memory is available.
Two complementary techniques achieve this solution are:
1. Segmentation
2. Paging
Segmentation – Programmers view of memory
• User’s view of memory is not the same as the actual physical memory.
• Segmentation is a memory-management scheme that supports this
programmer view of memory.
Segmentation (cont..)
• 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 and an offset.
• For simplicity of implementation, segments are numbered and are referred
to by a segment number, rather than by a segment name.
• Thus, a logical address consists of a two tuple:
<segment-number, offset>.
Segments
A C compiler might create separate segments for the following:
1. The code
2. Global variables
3. The heap, from which memory is allocated
4. The stacks used by each thread
5. The standard C library
Segmentation Hardware
• Although the programmer can now refer to objects in the program by a
two-dimensional address, the actual physical memory is still a one
dimensional sequence of bytes.
• Thus, we must define an implementation to map two-dimensional user-
defined addresses into one-dimensional physical addresses.
• This mapping is effected by a segment table.
• Each entry in the segment table has a segment base and a segment limit.
• 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
Segmentation Example
Paging
• Paging avoids external fragmentation and the need for compaction
whereas segmentation does not.
• The problem arises because, when code fragments or data residing in main
memory need to be swapped out, space must be found on the backing
store.
• Paging is implemented through cooperation between the operating system
and the computer hardware.
Basic Method of Paging Implementation
• The basic method for implementing paging involves breaking physical
memory into fixed-sized blocks called frames and breaking logical
memory into blocks of the same size called pages.
• The backing store is divided into fixed-sized blocks that are the same size
as the memory frames or clusters of multiple frames.
• 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
Paging Model
Paging
• The page size (like the frame size) is defined by the hardware.
• If the size of the logical address space is 2m, and a page size is 2n bytes,
then the high-order m− n bits of a logical address designate the page
number, and the n low-order bits designate the page offset.
• p is an index into the page table and d is the displacement within the page
Multi-level Paging
• Most modern computer systems
support a large logical address
space. In such an environment, the
page table itself becomes excessively
large.
• One way is to use a two-level paging
algorithm, in which the page table
itself is also paged.
Multi-level address translation
Implementation of Paging
• The standard solution is to use a special, small, fast lookup hardware cache
called a translation look-aside buffer (TLB).
• The TLB is associative, high-speed memory.
• 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 returned.
• The search is fast; a TLB lookup in modern hardware is part of the instruction
pipeline, essentially adding no performance penalty.
• To be able to execute the search within a pipeline step, however, the TLB must
be kept small. It is typically between 32 and 1,024 entries in size.
Translation Lookaside Buffer (TLB)
• The TLB contains only a few of the page-table entries.
• When a logical address is generated by the CPU, its page number is presented to the TLB.
EMAT
• The percentage of times that the page number of interest is found in the
TLB is called the hit ratio.
• t – TLB look up time, m – mapping to physical memory, h-hit
EMAT calculation example TLB access time is
20 ns
1. An 80-percent hit ratio, for example, means that we find the desired page number in the
TLB 80 percent of the time. If it takes 100 nanoseconds to access memory, then a
mapped-memory access takes 100 nanoseconds when the page number is in the TLB.

EMAT = 0.8 (20+100)+(1-0.8)*(20+2(100)) = 96+0.2(220)=140 ns

EMAT for 99% hit ratio = 0.99(120)+(1-0.99)*(20+2(100))=118.8+2.2=121 ns

Virtual Memory - Background
• Virtual memory is a technique that allows the execution of
processes that are not completely in memory.
• One major advantage of this scheme is that programs can be
larger than physical memory.
• Virtual memory abstracts main memory into an extremely
large, uniform array of storage, separating logical memory as
viewed by the user from physical memory.
• Virtual memory makes the task of programming much easier,
because the programmer no longer needs to worry about the
amount of physical memory available; she can concentrate
instead on the problem to be programmed.
Virtual Memory larger than physical memory
Virtual Address Space
• The virtual address space of a process refers to
the logical (or virtual) view of how a process is
stored in memory.

• We allow the heap to grow upward in memory

as it is used for dynamic memory allocation.

• Allowing the stack to grow downward in

memory through successive function calls.
• The large blank space (or hole) between the
heap and the stack is part of the virtual address
space but will require actual physical pages only
if the heap or stack grows.
Shared library using virtual memory

• Virtual address spaces that include

holes are known as sparse address
spaces.

• Using a sparse address space is

beneficial because the holes can be
filled as the stack or heap segments
grow or if we wish to dynamically link
libraries (or possibly other shared
objects) during program execution.
Advantages of Shared memory
• System libraries can be shared by several processes through mapping of
the shared object into a virtual address space.
• A library is mapped read-only into the space of each process that is linked
with it.
• Virtual memory allows one process to create a region of memory that it
can share with another process.
• Pages can be shared during process creation with the fork() system call,
thus speeding up process creation.
Demand paging
• Loading the entire program into memory results in loading the executable
code for all options, regardless of whether or not an option is ultimately
selected by the user.
• An alternative strategy is to load pages only as they are needed. This
technique is known as demand paging and is commonly used in virtual
memory systems.
• With demand-paged virtual memory, pages are loaded only when they are
demanded during program execution.
• A lazy swapper never swaps a page into memory unless that page will be
needed.
• A swapper manipulates entire processes, whereas a pager is concerned
with the individual pages of a process
Transfer of a paged memory to contiguous
disk space. • When a process is to be swapped in, the pager
guesses which pages will be used before the
process is swapped out again.

• With this scheme, we need some form of

hardware support to distinguish between the
pages that are in memory and the pages that
are on the disk.

• The valid–invalid bit scheme can be used for

this purpose.

• When this bit is set to “valid,” the associated

page is both legal and in memory.
Execution of Process
• If the bit is set to “invalid,” the page either is not valid (that is, not in the
logical address space of the process) or is valid but is currently on the disk.
• While the process executes and accesses pages that are memory resident,
execution proceeds normally.
Page table when some pages are not in main
memory
Page Faults
Demand Paging (cont..)
• After this page is brought into memory, the process continues to execute,
faulting as necessary until every page that it needs is in memory.
• At that point, it can execute with no more faults. This scheme is pure
demand paging: never bring a page into memory until it is required.
• Some programs could access several new pages of memory with each
instruction execution (one page for the instruction and many for data),
possibly causing multiple page faults per instruction.
Demand Paging (cont..)
• If a page fault occurs while we are fetching an operand, we must fetch
and decode the instruction again and then fetch the operand.
• As a worst-case example, consider a three-address instruction such as
ADD the content of A to B, placing the result in C.
• Paging is added between the CPU and the memory in a computer system.
It should be entirely transparent to the user process.
Why Demand Paging ?
• With no demand paging, user addresses are mapped into physical
addresses, and the two sets of addresses can be different.
• All the pages of a process still must be in physical memory, however.
• With demand paging, the size of the logical address space is no longer
constrained by physical memory.
• If we have a user process of twenty pages, we can execute it in ten frames
simply by using demand paging and using a replacement algorithm to
find a free frame whenever necessary.
• If we have a user process of twenty pages, we can execute it in ten frames
simply by using demand paging and using a replacement algorithm to
find a free frame whenever necessary.
Copy-on Write
• Process creation using the fork() system call may initially bypass the
need for demand paging by using a technique similar to page sharing.
• This technique provides rapid process creation and minimizes the number
of new pages that must be allocated to the newly created process.
• fork() worked by creating a copy of the parent’s address space for the
child, duplicating the pages belonging to the parent.
• Child processes invoke the exec() system call immediately after creation,
the copying of the parent’s address space may be unnecessary.
• Instead, we can use a technique known as copy-on-write, which works by
allowing the parent and child processes initially to share the same pages.
Before process 1 modifies page C
After process 1 modifies page C
Copy-on write
• Obviously, when the copy-on-write technique is used, only the pages that
are modified by either process are copied; all unmodified pages can be
shared by the parent and child processes.
• Only pages that can be modified need be marked as copy-on-write.
• Pages that cannot be modified (pages containing executable code) can be
shared by the parent and child.
• Copy-on-write is a common technique used by several operating systems,
including Windows XP, Linux, and Solaris.
• When it is determined that a page is going to be duplicated using copy on-
write, it is important to note the location from which the free page will be
allocated.
• Many operating systems provide a pool of free pages for such requests.
Page Replacement
• If a process of ten pages actually uses only half of them, then demand paging
saves the I/O necessary to load the five pages that are never used.
• We could also increase our degree of multiprogramming by running twice as
many processes.
• Thus, if we had forty frames, we could run eight processes, rather than the
four that could run if each required ten frames (five of which were never
used).
• If we run six processes, each of which is ten pages in size but actually uses
only five pages, we have higher CPU utilization and throughput, with ten
frames to spare.
• It is possible, however, that each of these processes, for a particular data set,
may suddenly try to use all ten of its pages, resulting in a need for sixty
frames when only forty are available.
Page Faults vs Memory not free
• System memory is not used only for holding program pages. Buffers for I/O also
consume a considerable amount of memory.
• Deciding how much memory to allocate to I/O and how much to program pages is a
significant challenge.
• While a user process is executing, a page fault occurs.
• The operating system determines where, the desired page is residing on the disk but
then finds that there are no free frames on the free-frame list; all memory is in use.
• The operating system has several options at this point. It could terminate the user
process. However, demand paging is the operating system’s attempt to improve the
computer system’s utilization and throughput.
• Users should not be aware that their processes are running on a paged system—
paging should be logically transparent to the user. So, this option is not the best
choice.
Page Replacement
Modify or dirty bit
• If no frames are free, two page transfers (one out and one in) are required.
This situation effectively doubles the page-fault service time and increases
the effective access time accordingly.
• We can reduce this overhead by using a modify bit (or dirty bit).
• When this scheme is used, each page or frame has a modify bit associated
with it in the hardware.
• The modify bit for a page is set by the hardware whenever any byte in the
page is written into, indicating that the page has been modified.
• If the bit is set, we know that the page has been modified since it was read
in from the disk. It has to be written in the disk.
• If bit is not set we need not write the memory page to the disk: it is already
there.
Page Replacement
• We must solve two major problems to implement demand paging: we
must develop a frame-allocation algorithm and a page-replacement
algorithm.
• That is, if we have multiple processes in memory, we must decide how
many frames to allocate to each process; and when page replacement is
required, we must select the frames that are to be replaced.
 First-In-First-Out (FIFO) Algorithm
• Reference string: 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1
• 3 frames (3 pages can be in memory at a time per process)

15 page faults

• Can vary by reference string: consider 1,2,3,4,1,2,5,1,2,3,4,5

• Adding more frames can cause more page faults!
• Belady’s Anomaly
FIFO Illustrating Belady’s Anomaly
 Least Recently Used (LRU) Algorithm

• Use past knowledge rather than future

• Replace page that has not been used in the most amount of time
• Associate time of last use with each page

• 12 faults – better than FIFO but worse than OPT

• Generally good algorithm and frequently used
• But how to implement?
 Optimal Page Replacement Algorithm
• Replace page that will not be used for longest period of time
• 9 is optimal for the example
• How do you know this?
• Can’t read the future
• Used for measuring how well your algorithm performs
Home work
Consider the following page reference string:
7, 2, 3, 1, 2, 5, 3, 4, 6, 7, 7, 1, 0, 5, 4, 6, 2, 3, 0 , 1.
• Assuming demand paging with three frames, how many page faults
would occur for the following replacement algorithms?
• LRU replacement
• FIFO replacement
• Optimal replacement
Allocation of Frames
• The simplest case is the single-user system. Consider a single-user system with 128 KB of
memory composed of pages 1 KB in size. This system has 128 frames. The operating
system may take 35 KB, leaving 93 frames for the user process. Under pure demand
paging, all 93 frames would initially be put on the free-frame list.

• When the free-frame list was exhausted, a page-replacement algorithm

would be used to select one of the 93 in-memory pages to be replaced with
the 94th, and so on.
• We can require that the operating system allocate all its buffer and table
space from the free-frame list.
• When this space is not in use by the operating system, it can be used to
support user paging.
• The basic strategy is clear: the user process is allocated any free frame
Minimum Number of Frames
• Obviously, as the number of frames allocated to each process decreases,
the page-fault rate increases, slowing process execution.
• In addition, remember that, when a page fault occurs before an executing
instruction is complete, the instruction must be restarted.
• Consequently, we must have enough frames to hold all the different pages
that any single instruction can reference.
• Whereas the minimum number of frames per process is defined by the
architecture, the maximum number is defined by the amount of available
physical memory.
Allocation Algorithms
• The easiest way to split m frames among n processes is to give everyone an
equal share, m/n frames. This scheme is called equal allocation.
• Allocate available memory to each process according to its size. This is
called proportional allocation.
• Notice that, with either equal or proportional allocation, a high-priority
process is treated the same as a low-priority process.
• One solution is to use a proportional allocation scheme wherein the ratio
of frames depends not on the relative sizes of processes but rather on the
priorities of processes or on a combination of size and priority.
Global Allocation
• Global replacement allows a process to select a replacement frame from the
set of all frames, even if that frame is currently allocated to some other
process; that is, one process can take a frame from another.
• One problem with a global replacement algorithm is that a process cannot
control its own page-fault rate.
• The set of pages in memory for a process depends not only on the paging
behavior of that process but also on the paging behaviour of other
processes.
Local Allocation
• Local replacement requires that each process select from only its own set
of allocated frames.
• Under local replacement, the set of pages in memory for a process is
affected by the paging behavior of only that process.
• Local replacement might hinder a process, however, by not making
available to it other, less used pages of memory. Thus, global replacement
generally results in greater system throughput and is therefore the more
commonly used method.
Thrashing
• If the number of frames allocated to a low-priority process falls below the
minimum number required by the computer architecture, we must
suspend that process’s execution.
• The process does not have the number of frames it needs to support pages
in active use, it will quickly page-fault.
• This high paging activity is called thrashing. A process is thrashing if it is
spending more time paging than executing.
 Causes of Thrashing
• The CPU scheduler sees the decreasing CPU
utilization and increases the degree of
multiprogramming as a result.
• The new process tries to get started by taking
frames from running processes, causing more
page faults and a longer queue for the paging
device.
• As a result, CPU utilization drops even
further, and the CPU scheduler tries to
increase the degree of multiprogramming
even more.
• If the degree of multiprogramming is
increased even further, thrashing sets in, and
CPU utilization drops sharply.
Memory Mapped Files
• Consider a sequential read of a file on disk using the standard system calls
open(), read(), and write(). Each file access requires a system call and
disk access.
• We can use the virtual memory techniques discussed so far to treat file I/O
as routine memory accesses. This approach, known as memory mapping a
file, allows a part of the virtual address space to be logically associated
with the file.
• Memory mapping a file is accomplished by mapping a disk block to a
page (or pages) in memory.
Memory Mapped Files
Allocating Kernel Memory
• When a process running in user mode requests additional memory, pages
are allocated from the list of free page frames maintained by the kernel.
• Kernel memory is often allocated from a free-memory pool different from
the list used to satisfy ordinary user-mode processes.
• The kernel requests memory for data structures of varying sizes, some of
which are less than a page in size.
• The kernel must use memory conservatively and attempt to minimize
waste due to fragmentation.
Buddy System
• The buddy system allocates memory from a fixed-size segment consisting
of physically contiguous pages.
• Memory is allocated from this segment using a power-of-2 allocator,
which satisfies requests in units sized as a power of 2(4 KB, 8 KB, 16 KB,
and so forth).
• A request in units not appropriately sized is rounded up to the next
highest power of 2. For example, a request for 11 KB is satisfied with a 16-
KB segment
Slab Allocation
• A slab is made up of one or more physically contiguous pages.
• A cache consists of one or more slabs.
• There is a single cache for each unique kernel data structure
1. a separate cache for the data structure representing process descriptors
2. a separate cache for file objects,
3. a separate cache for semaphores and so on.
• The slab-allocation algorithm uses caches to store kernel objects.
• Each cache is populated with objects that are instantiations of the kernel
data structure the cache represents.
Slab Allocation (Cont..)
1. No memory is wasted due to fragmentation.
• Fragmentation is not an issue because each unique kernel data structure
has an associated cache, and each cache is made up of one or more slabs
that are divided into chunks the size of the objects being represented.

• Thus, when the kernel requests memory for an object, the slab allocator
returns the exact amount of memory required to represent the object.
Allocating Kernel Memory through slab
Slab Allocation (Cont..)
2. Memory requests can be satisfied quickly.
• The slab allocation scheme is thus particularly effective for managing
memory when objects are frequently allocated and deallocated, as is often
the case with requests from the kernel.
• Objects are created in advance and thus can be quickly allocated from the
cache.
• When the kernel has finished with an object and releases it, it is marked as
free and returned to its cache, thus making it immediately available for
subsequent requests from the kernel.