MODULE 3

OPERATING SYSTEM
Memory management - Different address bindings – compile, link and run time
bindings. - Difference between logical address and physical address - Contiguous
memory allocation – fixed partition and variable partition – Allocation Strategies -
first fit, best fit and worst fit - Define fragmentation – internal and external, and
solutions - Paging and paging hardware - Segmentation, advantages of
segmentation over paging- Concept of virtual memory - Demand paging - Page-
faults and how to handle page faults. - Page replacement algorithms: FIFO,
optimal, LRU -Thrashing.
What is Memory?
Computer memory can be defined as a collection of some data represented in the
binary format.
How Data is being stored in a computer system?
Machine understands only binary language that is 0 or 1. Computer converts every
data into binary language first and then stores it into the memory.
Logical And Physical Addresses
An address generated by the CPU is commonly referred as Logical Address,
whereas the address seen by the memory unit that is one loaded into the memory
address register of the memory is commonly referred as the Physical Address.
The set of all logical addresses generated by a program is known as Logical
Address Space, where as the set of all physical addresses corresponding to these
logical addresses is Physical Address Space. Now, the run time mapping from
virtual address to physical address is done by a hardware device known as Memory
Management Unit.

1
Hardware device that maps virtual to physical address
In MMU scheme,eme, the value in the relocation register is added to every address
generated by a user process at the time it is sent to memory .The user program
deals with logical addresses; it never sees the real physical addresses

Address binding in Operating System

The Memory Management Unit (MMU) translates logical addresses into

physical (RAM) addresses
addresses. Mapping a logical address to a physical address is
called address binding or address mapping.

The Context of Address Binding

In a source code, we have symbolic addresses. They are the identifiers of the
variables, functions, classes, and other constructs.
The assembler maps them to relative numerical addresses. Relative addresses show
the offset to the starting point of the memory that the code will take.
The assembler outputs object files and gives them to the linker.
The linker takes object files and other pieces of code to generate an executable file.
First, it searches for all the libraries nee
needed
ded to execute the object file and appends
them to it one after another. After that, it establishes links correctly so the modules
can reference each other.
Finally, the output is passed to the loader. Specifically, the
loader allocates memory for the executable code and loads it:
2
Types of Address Binding in Operating System

There are mainly three types of an address binding in the OS. These are as follows:
1. Compile Time Address Binding
2. Load Time Address Binding
3. Execution Time or Dynamic Address Binding

compile Time Address Binding

● If the compiler is responsible for performing address binding then it is called

compile-time address binding.
● It will be done before loading the program into memory.
● The compiler requires interacts with an OS memory manager to perform
compile-time address binding.
An example of a system with compile-time address binding is MS-DOS.

3
Load Time Address Binding

● It will be done after loading the program into memory.

● This type of address binding will be done by the OS memory manager i.e
loader.
Therefore, when loading a program, we compute the physical addresses by adding
them to the base address.

In the image above, the relative address 250 becomes the absolute address 142500
because the base is 14000.

Execution-Time Binding

● It will be postponed even after loading the program into memory.

● The program will be kept on changing the locations in memory until the time of
program execution.
● The dynamic type of address binding done by the processor at the time of
program execution.

The majority of general-purpose OSs can use this mechanism. Some popular OSs
like Windows and Linux practically implement dynamic loading, dynamic linking,
and dynamic address binding.

4
The terms "logical address" and "physical address" are used in computer science to
describe different levels of memory addressing within a computer system. Here’s
an explanation of each term and the differences between them:

Key Differences between logical and physical addressing:

● Level of Operation: Logical addresses operate at the program or user level,

while physical addresses operate at the hardware level.
● Visibility: Logical addresses are visible and used by programs, whereas
physical addresses are hidden and used by the hardware.
● Abstraction: Logical addresses provide an abstraction layer that allows
programs to use memory without needing to manage the physical layout,
while physical addresses refer to actual locations in RAM.
● Translation: Logical addresses need to be translated to physical addresses
through a process managed by the MMU and operating system.
● Contiguity: Logical addresses can appear contiguous to a program even if
they are scattered in physical memory, due to mechanisms like paging or
segmentation.

What do you mean by memory management?

Memory is the important part of the computer that is used to store the data. Its
management is critical to the computer system because the amount of main
memory available in a computer system is very limited. At any time, many
processes are competing for it. Moreover, to increase performance, several
processes are executed simultaneously. For this, we must keep several processes in
the main memory, so it is even more important to manage them effectively.

Memory Management Techniques:

The memory management techniques can be classified into following main

categories:

○ Contiguous memory management schemes

○ Non-Contiguous memory management schemes

5
Contiguous memory management schemes:

In a Contiguous memory management scheme, each program occupies a single

contiguous block of storage locations, i.e., a set of memory locations with
consecutive addresses.

Single contiguous memory management schemes:

In this scheme, the main memory is divided into two contiguous areas or partitions.
The operating systems reside permanently in one partition, generally at the lower
memory, and the user process is loaded into the other partition.

Advantages of Single contiguous

iguous memory management schemes:

○ Simple to implement.

○ Easy to manage and design.

○ In a Single contiguous memory management scheme, once a process is

loaded, it is given full processor's time, and no other processor will interrupt
it.

6
Disadvantages of Single contiguous memory management schemes:

○ Wastage of memory space due to unused memory as the process is unlikely

to use all the available memory space.

○ The CPU remains idle, waiting for the disk to load the binary image into the
main memory.

○ It can not be executed if the program is too large to fit the entire available
main memory space.

○ It does not support multiprogramming, i.e., it cannot handle multiple

programs simultaneously.

Multiple Partitioning:

The single Contiguous memory management scheme is inefficient as it limits

computers to execute only one program at a time resulting in wastage in memory
space and CPU time. The problem of inefficient CPU use can be overcome using
multiprogramming that allows more than one program to run concurrently. To
switch between two processes, the operating systems need to load both processes
into the main memory. The operating system needs to divide the available main
memory into multiple parts to load multiple processes into the main memory. Thus
multiple processes can reside in the main memory simultaneously.

The multiple partitioning schemes can be of two types:

○ Fixed Partitioning

○ Dynamic Partitioning

Fixed Partitioning
The earliest and one of the simplest technique which can be used to load more than
one processes into the main memory is Fixed partitioning or Contiguous memory
allocation.

7
In this technique, the main memory is divided into partitions of equal or different
sizes. The operating system always resides in the first partition while the other
partitions can be used to store user processes. The memory is assigned to the
processes in contiguous way. The partitions cannot overlap.A process must be
contiguously present in a partition for the execution.
There are various cons of using this technique.
1. Internal Fragmentation
If the size of the process is lesser then the total size of the partition then some size
of the partition get wasted and remain unused. This is wastage of the memory and
called internal fragmentation.
As shown in the image below, the 4 MB partition is used to load only 3 MB
process and the remaining 1 MB got wasted.

2. External Fragmentation
The total unused space of various partitions cannot be used to load the processes
even though there is space available but not in the contiguous form.
As shown in the image below, the remaining 1 MB space of each partition cannot
be used as a unit to store a 4 MB process. Despite of the fact that the sufficient
space is available to load the process, process will not be loaded.
3. Limitation on the size of the process
If the process size is larger than the size of maximum sized partition then that
process cannot be loaded into the memory. Therefore, a limitation can be imposed
on the process size that is it cannot be larger than the size of the largest partition.
4. Degree of multiprogramming is less
By Degree of multi programming, we simply mean the maximum number of
processes that can be loaded into the memory at the same time. In fixed
partitioning, the degree of multiprogramming is fixed and very less due to the fact
that the size of the partition cannot be varied according to the size of processes.

8
Dynamic Partitioning
Dynamic partitioning tries to overcome the problems caused by fixed partitioning.
In this technique, the partition size is not declared initially. IItt is declared at the time
of process loading.
The first partition is reserved for the operating system. The remaining space is
divided into parts. The size of each partition will be equal to the size of the
process. The partition size varies according to tthe
he need of the process so that the
internal fragmentation can be avoided.

9
Advantages of Dynamic Partitioning over fixed partitioning
1. No Internal Fragmentation
Given the fact that the partitions in dynamic partitioning are created according to
the need
ed of the process, It is clear that there will not be any internal fragmentation
because there will not be any unused remaining space in the partition.
2. No Limitation on the size of the process
In Fixed partitioning, the process with the size greater tha
thann the size of the largest
partition could not be executed due to the lack of sufficient contiguous memory.
Here, In Dynamic partitioning, the process size can't be restricted since the
partition size is decided according to the process size.
3. Degree of multiprogramming
ultiprogramming is dynamic
Due to the absence of internal fragmentation, there will not be any unused space in
the partition hence more processes can be loaded in the memory at the same time.
Disadvantages of dynamic partitioning
External Fragmentation
Absence
ence of internal fragmentation doesn't mean that there will not be external
fragmentation.

10
The rule says that the process must be contiguously present in the main memory to
get executed. We need to change this rule to avoid external fragmentation.

Compaction
Dynamic partitioning suffers from external fragmentation. However, this can cause
some serious problems. Use compaction to minimize the probability of external
fragmentation. In compaction, all the free partitions are made contiguous and all
the loaded partitions are brought together.
The free partitions are merged which can now be allocated according to the needs
of new processes. This technique is also called defragmentation.

11
As shown in the image above, the process P5, which could not be loaded into the
memory due to the lack of contiguous space, can be loaded now in the memory
since the free partitions are made contiguous.
Problem with Compaction
The efficiency of the system is decreased in the case of compaction due to the fact
that all the free spaces will be transferred from several places to a single place.

Huge amount of time is invested for this procedure and the CPU will remain idle
for all this time. Despite of the fa fact
ct that the compaction avoids external
fragmentation, it makes system inefficient.

How do we allocate memory for a Process?

Processes enter the main memory and stay till they get completely executed.
Once a process exits, previously occupied memory is fre
freed
ed creating free spaces in
the memory. These spaces of unallocated memory are termed Holes.
12
In a Variable Partition Allocation we use three strategies to allocate memory:

First fit

An incoming process gets allocated into a Hole of size greater than or equal to it.
Searching for Holes can start from the beginning of the memory or from where the
previous first fit search ended.

We traverse through the memory array to find the first Hole able to accomodate the
incoming process. Traversing the memory is stopped once we acquire the First fit
hole.

Best fit

We find the least sized Hole capable of holding the incoming process. This
generates the smallest left over Holes.

13
The entire Memory array has to be traversed to obtain the Best fit Hole.

Worst Fit

We find the largest Hole and allocate the incoming process to it.

14
Similar to the Best fit strategy, the entire Memory array has to be traversed to
obtain the Worst fit Hole.

Memory Protection

Address binding enables memory protection. For example, in a multi-programming

environment, processes are executed simultaneously and concurrently access the
memory and the CPU.
By performing address binding, the OS guarantees the protection of each process’s
memory space. A RAM address can be accessed only by the process whose
address space it belongs to. For instance:

No process can access another one’s memory space because address binding
ensures memory protection.

What is Fragmentation?

Fragmentation is an unwanted problem in the operating system in which the

processes are loaded and unloaded from memory, and free memory space is
fragmented. Processes can't be assigned to memory blocks due to their small size,
and the memory blocks stay unused. It is also necessary to understand that as
programs are loaded and deleted from memory, they generate free space or a hole
in the memory. These small blocks cannot be allotted to new arriving processes,
resulting in inefficient memory use.

15
The conditions of fragmentation depend on the memory allocation system. As the
process is loaded and unloaded from memory, these areas are fragmented into
small pieces of memory that cannot be allocated to incoming processes. It is
called fragmentation.

Types of Fragmentation

There are mainly two types of fragmentation in the operating system. These are as
follows:
1. Internal Fragmentation
2. External Fragmentation

Internal Fragmentation

When a process is allocated to a memory block, and if the process is smaller than
the amount of memory requested, a free space is created in the given memory
block. Due to this, the free space of the memory block is unused, which
causes internal fragmentation.
For Example:
Assume that memory allocation in RAM is done using fixed partitioning (i.e.,
memory blocks of fixed sizes). 2MB, 4MB, 4MB, and 8MB are the available
sizes. The Operating System uses a part of this RAM.

16
Let's suppose a process P1 with a size of 3MB arrives and is given a memory
block of 4MB.. As a result, the 1MB of free space in this block is unused and
cannot be used to allocate memory to another process. It is known as internal
fragmentation.
How to avoid internal fragmentation?
The problem of internal fragmentation may arise due to the fixed sizes of the
memoryy blocks. It may be solved by assigning space to the process via dynamic
partitioning. Dynamic partitioning allocates only the amount of space requested by
the process. As a result, there is no internal fragmentation.

External Fragmentation

External fragmentation
ntation happens when a dynamic memory allocation method
allocates some memory but leaves a small amount of memory unusable. There is
enough memory space to complete a request, but it is not contiguous. It's known
as external fragmentation.
For Example:

17
Let's take the example of external fragmentation. In the above diagram, you can
see that there is sufficient space (50 KB) to run a process (05) (need 45KB),
45KB) but
the memory is not contiguous.
How to remove external fragmentation?
This problem occurs when you allocate RAM to processes continuously. It is done
in paging and segmentation, where memory is allocated to processes non- non
contiguously. As a result, if you remove this condition, external fragmentation may
be decreased.
Compaction
ion is another method for removing external [Link]
fragmentation.
is a method by which all free memory that are scattered are placed together in
one large memory block.

Paging in OS (Operating System)

Paging is a storage mechanism used to retrieve processes from the secondary

storage into the main memory in the form of pages.

18
The main idea behind the paging is to divide each process in the form of pages.
The main memory will also be divided in the form of frames.

Pages of the process are brought into the main memory only when they are
required otherwise they reside in the sec
secondary storage.

Example

Let us consider the main memory size 16 Kb and Frame size is 1 KB therefore the
main memory will be divided into the collection of 16 frames of 1 KB each.

19
There are 4 processes in the system that is P1, P2, P3 and P4 of 4 KB each. Each
process is divided into pages of 1 KB each so that one page can be stored in one
frame.

Translating
ranslating a logical address into the physical address:
The logical address generated by CPU always consists of two parts:

1. Page Number(p)
2. Page Offset (d)

where,

Page Number is used to specify the specific page of the process from which the
CPU wants to read the data. and it is also used as an index to the page table.

and Page offset is mainly used to specify the specific word on the page that the
CPU wants to read.

Page Table in OS

20
The Page table mainly contains the base address of each page in the Physical
memory. The base address is then combined with the page offset in order to define
the physical memory address which is then sent to the memory unit.

The physical address consists of two parts:

[Link] offset(d)

[Link] Number(f)

The Frame number is used to indicate the specific frame where the required page
is stored.

and Page Offset indicates the specific word that has to be read from that page.

21
Advantages of Paging in OS

22
 ● It is a memory management technique as we can store the pages of a single
process in a non-contiguous manner as well which saves the memory.
● The problem of external fragmentation is solved with the help of the Paging
technique.
● Allocating the pages within equal and fixed-size frames is easy and simple.
Swapping is also easy between the pages and the page frames.

Segmentation

Segmentation is a memory management technique in which the memory is

divided into the variable size parts. Each part is known as a segment which
can be allocated to a process.
The details about each segment are stored in a table called a segment table.
Segment table is stored in one (or many) of the segments.
Segment table contains mainly two information about segment:
1. Base: It is the base address of the segment
2. Limit: It is the length of the segment.

Why Segmentation is required?

Till now, we were using Paging as our main memory management technique.
Paging is more close to the Operating system rather than the User. It divides all the
processes into the form of pages regardless of the fact that a process can have some
relative parts of functions which need to be loaded in the same page.
Operating system doesn't care about the User's view of the process. It may divide
the same function into different pages and those pages may or may not be loaded at
the same time into the memory. It decreases the efficiency of the system.
It is better to have segmentation which divides the process into the segments. Each
segment contains the same type of functions such as the main function can be
included in one segment and the library functions can be included in the other
segment.

23
24
With the help of segment map tables and hardware assistance, the operating system
can easily translate a logical address into physical address on execution of a
program.
The Segment number is mapped to the segment ta table.
ble. The limit of the respective
segment is compared with the offset. If the offset is less than the limit then the
address is valid otherwise it throws an error as the address is invalid.
In the case of valid addresses, the base address of the segment is added to the
offset to get the physical address of the actual word in the main memory.

25
26
Advantages of Segmentation

1. No internal fragmentation
2. Less overhead
3. It is easier to relocate segments than entire address space.
4. The segment table is of lesser size as compared to the page table in paging.

Disadvantages

1. It can have external fragmentation.

2. it is difficult to allocate contiguous memory to variable sized partition.
3. Costly memory management algorithms.

Virtual Memory

A computer system has a limited amount of memory. Adding more memory

physically is very costly. Therefore most modern computers use a combination of
both hardware and software to allow the computer to address more memory than
the amount physically present on the system. This extra memory is actually
called Virtual Memory.

Virtual Memory is a space where large programs can store themselves in form of
pages. This technique is useful as large virtual memory is provided for user
programs when a very small physical memory is there.

27
Fig. Diagram showing virtual memory that is larger than physical memory. Virtual
memory is commonly implemented by demand paging.

Demand Paging

A demand paging is similar to a paging system with swapping. When we want to

execute a process, we swap it into memory. Rather than swapping the entire
process into memory.

When a process is to be swapped in, the pager guesses which pages will be used
before the process is swapped out again Instead of swapping in a whole process,
the pager brings only those necessary pages into memory.

28
Page Fault: A page fault happens when a running program accesses a
memory page that is mapped into the virtual address space but not loaded in
physical memory. Since actual physical memory is much smaller than virtual
memory, page faults happen. In case of a page fault, Operating System might
have to replace one of the existing pages with the newly needed page. Different
page replacement algorithms suggest different ways to decide which page to
replace.
Steps in handling a page fault

When the process requires any of the page that is not loaded into the memory, a
page fault trap is triggered and following steps are followed,

1. The memory address which is requested by the process is first checked, to verify
the request made by the process.

2. If its found to be invalid, the process is terminated.

3. In case the request by the process is valid, a free frame is located, possibly from
a free-frame list, where the required page will be moved.

29
4. A new operation is scheduled to move the necessary page from disk to the
specified memory location. ( This will usually block the process on an I/O wait,
allowing some other process to use the CPU in the meantime. )

5. When the I/O operation is complete, the process's page table is updated with the
new frame number, and the invalid bit is changed to valid.

6. The instruction that caused the page fault must now be restarted from the
beginning. There are cases when no pages are loaded into the memory initially,
pages are only loaded when demanded by the process by generating page faults.
This is called Pure Demand Paging.

Page Replacement

In Demand Paging, only certain pages of a process are loaded initially into the
memory. This allows us to get more number of processes into the memory at the
same time. but what happens when a process requests for more pages and no free
memory is available to bring them in.

Following steps can be taken to deal with this problem:

30
1. Put the process in the wait queue, until any other process finishes its execution
thereby freeing frames.

2. Or, remove some other process completely from the memory to free frames.

3. Or, find some pages that are not being used right now, move them to the disk to
get free

frames. This technique is called Page replacement.

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.

FIFO (First-In-First-Out)

● FIFO follows the simple principle of replacing the page that entered memory
first.
● When a page fault occurs, the oldest page, which arrived earliest, is replaced.
● It does not require any additional data structures to maintain the order of page
usage.
For Example:

Consider the page reference string of size 12: 1, 2, 3, 4, 5, 1, 3, 1, 6, 3, 2, 3 with

frame size 4(i.e. maximum 4 pages in a frame).

31
Total Page Fault = 9

Initially, all 4 slots are empty, so when 1, 2, 3, 4 came they are allocated to the
empty slots in order of their arrival. This is page fault as 1, 2, 3, 4 are not available
in memory.

When 5 comes, it is not available in memory so page fault occurs and it replaces
the oldest page in memory, i.e., 1.

When 1 comes, it is not available in memory so page fault occurs and it replaces
the oldest page in memory, i.e., 2.

When 3,1 comes, it is available in the memory, i.e., Page Hit, so no replacement
occurs.

When 6 comes, it is not available in memory so page fault occurs and it replaces
the oldest page in memory, i.e., 3.

When 3 comes, it is not available in memory so page fault occurs and it replaces
the oldest page in memory, i.e., 4.

32
When 2 comes, it is not available in memory so page fault occurs and it replaces
the oldest page in memory, i.e., 5.

When 3 comes, it is available in the memory, i.e., Page Hit, so no replacement

occurs.

Page Fault ratio = 9/12 i.e. total miss/total possible cases

Belady’s anomaly proves that it is possible to have more page faults when
increasing the number of page frames while using the First in First Out (FIFO)
page replacement algorithm.

Advantages

● Simple to understand and implement

● Does not cause more overhead

Disadvantages

● Poor performance
● Doesn’t use the frequency of the last used time and just simply replaces the
oldest page.

[Link] Page Replacement in OS

Optimal page replacement is the best page replacement algorithm as this algorithm
results in the least number of page faults. In this algorithm, the pages are replaced
with the ones that will not be used for the longest duration of time in the future.
This algorithm was introduced long back and is difficult to implement because it
requires future knowledge of the program behaviour.

33
Total Page Fault = 6

Initially, all 4 slots are empty, so when 1, 2, 3, 4 came they are allocated to the
empty slots in order of their arrival. This is page fault as 1, 2, 3, 4 are not available
in memory.

When 5 comes, it is not available in memory so page fault occurs and it replaces 4
which is going to be used farthest in the future among 1, 2, 3, 4.

When 1,3,1 comes, they are available in the memory, i.e., Page Hit, so no
replacement occurs.

When 6 comes, it is not available in memory so page fault occurs and it replaces 1.

When 3, 2, 3 comes, it is available in the memory, i.e., Page Hit, so no replacement

occurs.

Page Fault ratio = 6/12

[Link] Recently Used (LRU)

34
Least Recently Used page replacement algorithm keeps track of page usage over a
short period of time. It works on the idea that the pages that have been most
heavily used in the past are most likely to be used heavily in the future too.

In LRU, whenever page replacement happens, the page which has not been used
for the longest amount of time is replaced.

Total Page Fault = 8

Initially, all 4 slots are empty, so when 1, 2, 3, 4 came they are allocated to the
empty slots in order of their arrival. This is page fault as 1, 2, 3, 4 are not available
in memory.

When 5 comes, it is not available in memory so page fault occurs and it replaces 1
which is the least recently used page.

When 1 comes, it is not available in memory so page fault occurs and it replaces 2.

When 3,1 comes, it is available in the memory, i.e., Page Hit, so no replacement
occurs.

35
When 6 comes, it is not available in memory so page fault occurs and it replaces 4.

When 3 comes, it is available in the memory, i.e., Page Hit, so no replacement

occurs.

When 2 comes, it is not available in memory so page fault occurs and it replaces 5.

When 3 comes, it is available in the memory, i.e., Page Hit, so no replacement

occurs.

Page Fault ratio = 8/12

Advantages

● Efficient.
● Doesn't suffer from Belady’s Anomaly.
Disadvantages

● Complex Implementation.
● Expensive.
● Requires hardware support.

Thrashing

In case, if the page fault and swapping happens very frequently at a higher rate,
then the operating system has to spend more time swapping these pages. This state
in the operating system is termed thrashing. Because of thrashing the CPU
utilization is going to be reduced.

36
Causes of Thrashing

● Thrashing affects the performance of execution in the Operating system

● We can also say that as soon as the memory fills up, the process starts
spending a lot of time for the required pages to be swapped in. Again the
utilization of the CPU becomes low because most of the processes are
waiting for pages.

● Thus a high degree of multiprogramming and lack of frames are two main
causes of thrashing in the Operating system.

37