Os MM - 021727
Os MM - 021727
Os MM - 021727
The operating system takes care of mapping the logical addresses to physical addresses at the time
of memory allocation to the program. There are three types of addresses used in a program before
and after memory is allocated −
1|Page
1
Symbolic addresses
The addresses used in a source code. The variable names, constants, and instruction labels
are the basic elements of the symbolic address space.
2
Relative addresses
At the time of compilation, a compiler converts symbolic addresses into relative addresses.
3
Physical addresses
The loader generates these addresses at the time when a program is loaded into main
memory.
Virtual and physical addresses are the same in compile-time and load-time address-binding
schemes. Virtual and physical addresses differ in execution-time address-binding scheme.
The set of all logical addresses generated by a program is referred to as a logical address space.
The set of all physical addresses corresponding to these logical addresses is referred to as a
physical address space.
The OS manages the memory by carrying out the followings operation
Allocation and Relocation: Each process must have enough memory to
execute.
Protection and Sharing: A process should not run into the memory space of
another process.
It checks how much memory is to be allocated to processes.
It decides which process will get memory at what time.
It tracks whenever some memory gets freed or unallocated and
correspondingly it updates the status.
Relocation
2|Page
When a process is to be executed, it has to be loaded
from the secondary storage (like hard disk) to the main
memory (RAM). This is called process loading. Since,
main memory is limited and other processes also need it
for their execution, an operating system swaps the two
processes, which is called swapping. Once the process
is 'swapped out', it is uncertain to predict when it will
be
'swapped in' because of the number of processes
running concurrently
4|Page
In the contiguous memory allocation when any user process request for the
memory a single section of the contiguous memory block is given to that process
according to its need. We can achieve contiguous memory allocation by dividing
memory into the fixed-sized partition.
A single process is allocated in that fixed sized single partition. But this will
increase the degree of multiprogramming means more than one process in the main
memory that bounds the number of fixed partition done in memory. Internal
fragmentation increases because of the contiguous memory allocation.
Memory Allocation
When the multiple memory holes (partitions) are large enough to
contain a process, the operating system must use an algorithm to
select in which hole the process will be loaded. The partition
selection algorithm are as follows:
⇒ First-fit: The OS looks at all sections of free memory. The
process is allocated to the first hole found that is big enough
size than the size of process.
⇒ Next Fit: The next fit search starts at the last hole allocated
and The process is allocated to the next hole found that is big
enough size than the size of process.
⇒ Best-fit: The Best Fit searches the entire list of holes to find
the smallest hole that is big enough size than the size of
process.
⇒ Worst-fit: The Worst Fit searches the entire list of holes to
find the largest hole that is big enough size than the size of
process.
5|Page
Fragmentation: As processes are loaded and removed from
memory, the free memory space is broken into little pieces. It
happens after sometimes that processes cannot be allocated to
memory blocks considering their small size and memory blocks
remains unused. This problem is known as Fragmentation. The
wasting of memory space is called fragmentation. There are two
types of fragmentation as follows:
1. External Fragmentation: The total memory space exists to
satisfy a request, but it is not contiguous. This wasted space
not allocated to any partition is called external fragmentation.
The external fragmentation can be reduce by compaction (or
defragmentation).
2. Internal Fragmentation: The allocated memory may be
slightly larger than requested memory. The wasted space within
a partition is called internal fragmentation. One method to reduce
internal fragmentation is to use partitions of different size
Advantage: Management or block keeping is easy.
Disadvantage: Internal fragmentation
6|Page
logical addresses generated by a program’s perspective.
The hardware device called Memory-Management Unit is used for mapping
logical address to its corresponding physical address.
Physical Address identifies a physical location of required data in a memory. The
user never directly deals with the physical address but can access by its
corresponding logical address.
1. The basic difference between Logical and physical address is that Logical
address is address generated by CPU during execution whereas Physical
Address refers to location in memory unit. Note that user deals with only
logical address(Virtual address). The logical address undergoes translation
by the MMU or address translation unit in particular.
2. Logical address is generated by CPU in perspective of a program whereas
the physical address is a location that exists in the memory unit.
Address Mapping
Address Mapping or Address binding is the process of mapping (Translating)
from one address space to another address space eg from logical address to
physical address, form physical to virtual address etc.
Memory mapping is the translation between the logical address space
and the physical memory address space.
b) Non-contiguous memory allocation
In the non-contiguous memory allocation, the available free memory space are
scattered here and there and all the free memory space is not at one place. So this is
time-consuming. In the non-contiguous memory allocation, a process will
acquire the memory space but it is not at one place it is at the different locations
according to the process requirement. This technique of non-contiguous memory
allocation reduces the wastage of memory which leads to internal and external
fragmentation. This utilizes all the free memory space which is created by a
different process.
7|Page
Non-Contiguous Memory
S.NO. Contiguous Memory Allocation
Allocation
Non-Contiguous memory
Contiguous memory allocation
allocation allocates separate
1. allocates consecutive blocks of
blocks of memory to a
memory to a file/process.
file/process.
2. Faster in Execution. Slower in Execution.
It is difficult for the OS to
3. It is easier for the OS to control.
control.
Both Internal fragmentation and
External fragmentation occurs
external fragmentation occurs in
5. in Non-Contiguous memory
Contiguous memory allocation
allocation method.
method.
7. Wastage of memory is there. No memory wastage is there.
Swapping
Swapping is a mechanism in which a process can be swapped temporarily out of main memory
(or move) to secondary storage (disk) and make that memory available to other processes. At
some later time, the system swaps back the process from the secondary storage to main memory.
Though performance is usually affected by swapping process but it helps in running multiple and
big processes in parallel and that's the reason Swapping is also known as a technique for
memory compaction.
9|Page
The total time taken by swapping process includes the time it takes to move the entire process to
a secondary disk and then to copy the process back to memory, as well as the time the process
takes to regain main memory.
Let us assume that the user process is of size 2048KB and on a standard hard disk where
swapping will take place has a data transfer rate around 1 MB per second. The actual transfer of
the 1000K process to or from memory will take
2048KB / 1024KB per second
= 2 seconds
= 2000 milliseconds
Now considering in and out time, it will take complete 4000 milliseconds plus other overhead
where the process competes to regain main memory.
Fragmentation
As processes are loaded and removed from memory, the free memory space is broken into little
pieces. It happens after sometimes that processes cannot be allocated to memory blocks
considering their small size and memory blocks remains unused. This problem is known as
Fragmentation.
1
External fragmentation
Total memory space is enough to satisfy a request or to reside a process in it, but it is not
contiguous, so it cannot be used.
2
Internal fragmentation
Memory block assigned to process is bigger. Some portion of memory is left unused, as it
cannot be used by another process.
10 | P a g e
The following diagram shows how fragmentation can cause waste of memory and a compaction
technique can be used to create more free memory out of fragmented memory −
External fragmentation can be reduced by compaction or shuffle memory contents to place all
free memory together in one large block. To make compaction feasible, relocation should be
dynamic.
The internal fragmentation can be reduced by effectively assigning the smallest partition but
large enough for the process.
Paging
A computer can address more memory than the amount physically installed on the system. This
extra memory is actually called virtual memory and it is a section of a hard that's set up to
emulate the computer's RAM. Paging technique plays an important role in implementing virtual
memory.
Paging is a memory management technique in which process address space is broken into blocks
of the same size called pages (size is power of 2, between 512 bytes and 8192 bytes). The size of
the process is measured in the number of pages.
11 | P a g e
Similarly, main memory is divided into small fixed-sized blocks of (physical) memory called
frames and the size of a frame is kept the same as that of a page to have optimum utilization of
the main memory and to avoid external fragmentation.
Paging reduces external fragmentation, but still suffer from internal fragmentation.
Paging is simple to implement and assumed as an efficient memory management technique.
Due to equal size of the pages and frames, swapping becomes very easy.
Page table requires extra memory space, so may not be good for a system having small RAM.
Segmentation
12 | P a g e
Segmentation is a memory management technique in which each job is divided into several
segments of different sizes, one for each module that contains pieces that perform related
functions. Each segment is actually a different logical address space of the program.
When a process is to be executed, its corresponding segmentation are loaded into non-contiguous
memory though every segment is loaded into a contiguous block of available memory.
Segmentation memory management works very similar to paging but here segments are of
variable-length where as in paging pages are of fixed size.
A program segment contains the program's main function, utility functions, data structures, and
so on. The operating system maintains a segment map table for every process and a list of free
memory blocks along with segment numbers, their size and corresponding memory locations in
main memory. For each segment, the table stores the starting address of the segment and the
length of the segment. A reference to a memory location includes a value that identifies a
segment and an offset.
13 | P a g e
Operating System - Virtual Memory
A computer can address more memory than the amount physically installed on the system. This
extra memory is actually called virtual memory and it is a section of a hard disk that's set up to
emulate the computer's RAM.
The main visible advantage of this scheme is that programs can be larger than physical memory.
Virtual memory serves two purposes. First, it allows us to extend the use of physical memory by
using disk. Second, it allows us to have memory protection, because each virtual address is
translated to a physical address.
Following are the situations, when entire program is not required to be loaded fully in main
memory.
User written error handling routines are used only when an error occurred in the data or
computation.
Certain options and features of a program may be used rarely.
Many tables are assigned a fixed amount of address space even though only a small amount of
the table is actually used.
The ability to execute a program that is only partially in memory would counter many benefits.
Less number of I/O would be needed to load or swap each user program into memory.
A program would no longer be constrained by the amount of physical memory that is
available.
Each user program could take less physical memory, more programs could be run the same
time, with a corresponding increase in CPU utilization and throughput.
14 | P a g e
Virtual memory is commonly implemented by demand paging. It can also be implemented in a
segmentation system. Demand segmentation can also be used to provide virtual memory.
Demand Paging
A demand paging system is quite similar to a paging system with swapping where processes
reside in secondary memory and pages are loaded only on demand, not in advance. When a
context switch occurs, the operating system does not copy any of the old program’s pages out to
the disk or any of the new program’s pages into the main memory Instead, it just begins
executing the new program after loading the first page and fetches that program’s pages as they
are referenced.
15 | P a g e
While executing a program, if the program references a page which is not available in the main
memory because it was swapped out a little ago, the processor treats this invalid memory
reference as a page fault and transfers control from the program to the operating system to
demand the page back into the memory.
Advantages
Following are the advantages of Demand Paging −
16 | P a g e
Page Replacement Algorithm
Page replacement algorithms are the techniques using which an Operating System decides which
memory pages to swap out, write to disk when a page of memory needs to be allocated. Paging
happens whenever a page fault occurs and a free page cannot be used for allocation purpose
accounting to reason that pages are not available or the number of free pages is lower than
required pages.
When the page that was selected for replacement and was paged out, is referenced again, it has to
read in from disk, and this requires for I/O completion. This process determines the quality of the
page replacement algorithm: the lesser the time waiting for page-ins, the better is the algorithm.
A page replacement algorithm looks at the limited information about accessing the pages
provided by hardware, and tries to select which pages should be replaced to minimize the total
number of page misses, while balancing it with the costs of primary storage and processor time
of the algorithm itself. There are many different page replacement algorithms. We evaluate an
algorithm by running it on a particular string of memory reference and computing the number of
page faults,
Reference String
The string of memory references is called reference string. Reference strings are generated
artificially or by tracing a given system and recording the address of each memory reference. The
latter choice produces a large number of data, where we note two things.
For a given page size, we need to consider only the page number, not the entire address.
If we have a reference to a page p, then any immediately following references to page p will
never cause a page fault. Page p will be in memory after the first reference; the immediately
following references will not fault.
For example, consider the following sequence of addresses − 123,215,600,1234,76,96
If page size is 100, then the reference string is 1,2,6,12,0,0
17 | P a g e
Optimal Page algorithm
An optimal page-replacement algorithm has the lowest page-fault rate of all algorithms. An
optimal page-replacement algorithm exists, and has been called OPT or MIN.
Replace the page that will not be used for the longest period of time. Use the time when a page
is to be used.
18 | P a g e
Easy to implement, keep a list, replace pages by looking back into time.
19 | P a g e