CS3451-INTRODUCTION TO OPERATING SYSTEM

UNIT-1

INTRODUCTION
Computer System - Elements and organization; Operating System Overview -
Objectives and Functions - Evolution of Operating System; Operating System
Structures – Operating System Services - User Operating System Interface - System
Calls – System Programs - Design and Implementation - Structuring methods.

[Link]-System

Computer system consists of one or more CPUs and a number of device controllers
connected through a common bus that provides access to shared memory.
Each device controller is in charge of a specific type of device. The CPU and the device
controllers can execute concurrently, competing for memory cycles. To ensure orderly
access to the shared memory, a memory controller is provided whose function is to
synchronize access to the memory.
Hardware may trigger an interrupt at any time by sending a signal to the CPU, usually by
way of the system bus. Software may trigger an interrupt by executing a special operation
called a system call (also called a monitor call).

When the CPU is interrupted, it stops what it is doing and immediately transfers
execution to a fixed location. The fixed location usually contains the starting address
where the service routine for the interrupt is located. The interrupt service routine
executes; on completion, the CPU resumes the interrupted computation.
A time line of this operation is shown in Figure 1.3.
Interrupts are an important part of computer architecture. Each computer design has its
own interrupt mechanism, but several functions are common. The interrupt must
transfer control to the appropriate interrupt service routine.

The straightforward method for handling this transfer would be to invoke

a generic routine to examine the interrupt information; the routine, in turn, would
call the interrupt-specific handler.
The interrupt routine is called indirectly through the table, with no intermediate
routine needed. Generally, the table of pointers is stored in low memory (the first
100 or so locations).
 These locations hold the addresses of the interrupt service routines for the
various devices. This array, or interrupt vector, of addresses is then indexed by a
unique device number, given with the interrupt request, to provide the address of
the interrupt service routine for the interrupting device. The
interrupt architecture must also save the address of the interrupted instruction.
After the interrupt is serviced, the saved return address is loaded into the program
counter, and the interrupted computation resumes as though the interrupt had not
occurred.

[Link]
Computer programs must be in main memory (also called random- access
memory or RAM) to be executed. Main memory is the only large storage area
(millions to billions of bytes) that the processor can access directly. Dynamic
random-access memory (DRAM) -> is implemented in a semiconductor technology
which forms an array of memory words.
A typical instruction-execution cycle, as executed on a system with a von Neumann
architecture, first fetches an instruction from memory and stores that instruction
in the instruction register.

Two possible reasons if we want the programs and data to reside in main memory
permanently.

1. Main memory is usually too small to store all needed programs and
data permanently.
2. Main memory is a volatile storage device that loses its contents when power is
turned off or otherwise lost.

Secondary storage which most computer systems provide as an extension of main

memory. The main requirement for secondary storage is that it be able to hold large
quantities of data permanently.
Magnetic disk is the most common secondary-storage device which provides storage
for both programs and data. Most programs (web browsers, compilers, word
processors, spreadsheets, and so on) are stored on a disk until they are loaded
into memory.

The wide variety of storage systems in a computer system can be organized in a

hierarchy (Figure 1.4) according to speed and cost. The higher levels are expensive,
but they are fast.

3. I/OStructure
Storage is only one of many types of I/O devices within a computer. A large
portion of operating system code is dedicated to managing I/O, both because of its
importance to the reliability and performance of a system and because of the
varying nature of the devices.
A general-purpose computer system consists of CPUs and multiple
device controllers that are connected through a common bus. Each device
controller is in charge of a specific type of device. Depending on the controller, there
may be more than one attached device.
A device controller maintains some local buffer storage and a set of special-
purpose registers. The device controller is responsible for moving the data between
the peripheral devices that it controls and its local buffer storage.

Typically, operating systems have a device driver for each device controller. This
device driver understands the device controller and presents a uniform interface
to the device to the rest of the operating system. On these systems, multiple
components can talk to other components concurrently, rather than competing
for cycles on a shared bus.
3. EVALUATION OF OPERATING SYSTEM:

Operating System is a type of software that acts as an interface between the user and
the hardware. It is responsible to handle various critical functions of the computer or any
other machine. Various tasks that are handled by OS are file management, task management,
garbage management, memory management, process management, disk management, I/O
management, peripherals management, etc.

Evolution of Operating System:

Operating Systems, has evolved in past years. It went through several changes before getting
its original form. These changes in the operating system are known as the evolution
of operating systems. The evolution of the operating system went through four
generations. Let us see these generations in detail:

First Generation:

• This phase is considered from 1945-1955. Earlier mechanical systems were used which
involved the use of large machines whose parts were manually handled by workers. The
limited capacity to work of a human and the tendency to commit an error by a person
often lead to problems. Thus electronic machines were introduced to do the work.
Though these machines did not use an OS at all still this phase is regarded as the
beginning of the Operating Systems era.
• The electronic machines supplied instructions that were to be executed by the machine
immediately because if an error occurred, the whole process was to be restarted again.
The calculation speed in these machines was limited and still errors could occur if there
was any error in the instruction provided to the machine. These systems were referred
to as serial processing systems.
Second Generation:

• The phase from 1955 to 1965 marked the second generation of Operating Systems. The
systems in this generation were regarded as Batch Systems. These were known as
batch operating systems as the jobs to be done were supplied in a batch to the machine.
A Batch referred to a set of similar tasks or jobs. Job Control Language was used to create
the instructions to execute the job. The instructions were punched on a card which was
then loaded onto a tape that had several such cards and then it was finally sent to the
processor.
• The second generation of OS ensured that the machines remained as busy as possible so
that maximum efficiency could be obtained. The machine took up a job, process the
instructions and then move to the next job that was present on the card loaded onto the
tape. If an error occurred during a particular job, then the job needs to be restarted
again.
• These systems made it possible to execute multiple jobs on a single machine and laid the
foundation for multitasking.
• These systems had a drawback in that when the I/O operations were carried out, the
processor had to remain idle.

Third Generation:

• The phase from 1965-1980 is considered as the third generation of OS. It saw the rise of
multi-programmed batched systems. These systems were very similar to the batched
operating systems. These systems had the ability of multitasking and multiprogramming
where the tasks of multiple users could be run simultaneously.
• Users could connect to the machine and submit their tasks through an online terminal.
The OS held all the tasks in the main memory and managed the tasks to be executed using
various scheduling algorithms such as FCFS, SJF, LJF, etc. This also ensured that the tasks
or jobs do not suffer from starvation.
Fourth Generation:

• 1980 onwards, the generation of OS is known as the fourth generation. With the
development of computer networking and various networking protocols, these
operating systems allowed the users to know the existence of other users on the network.
• The operating systems in this generation saw the use of a Graphical User Interface (GUI)
which made it very easy to interact with the operating system and in turn with the
hardware.
• The fourth generation of operating systems saw the invention of time-shared operating
systems and the Macintosh operating systems. Let us see about the time- shared
operating systems and the Macintosh operating systems in brief.
In other operating systems, many times users felt that their work was not being done as
some tasks took too long to get completed. This lead to starvation of processes or jobs. Time-
shared operating systems solved this problem by ensuring that no user feels that his work
is not being done. These operating systems made use of scheduling algorithms such as Round
Robin in which the work of a user was done for a specific time and then the OS moved to
the next job. Thus, in actuality, these OS shared the time between multiple users and hence
got the name Time Shared Operating Systems.

These types of operating systems paved the way for Mac and Windows OS. The use of
personal computers grew as the OS evolved more and more and the computers became more
user-centric instead of being shared by multiple users. Personal computers became
increasingly cheap as the hardware costs decreased. As the hardware evolved more and
more, the color Macs were developed and Microsoft implemented Windows based on the
Graphical User Interface operating system.
4. OBJECTIVE AND FUNCTIONS OF OPERATING SYSTEM
5. OPERATING SYSTEM STRUCTURE

An operating system is a construct that allows the user application

programs to interact with the system hardware. Since the operating system is
such a complex structure, it should be created with utmost care so it can be
used and modified easily. An easy way to do this is to create the operating
system in parts. Each of these parts should be well defined with clear inputs,
outputs and functions
1. Simple Structure
There are many operating systems that have a rather simple structure.
These started as small systems and rapidly expanded much further than their
scope. A common example of this is MS-DOS. It was designed simply for a niche
amount for people. There was no indication that it would become so popular.
An image to illustrate the structure of MS-DOS is as follows −

It is better that operating systems have a modular structure, unlike MS-DOS.

That would lead to greater control over the computer system and its various
applications. The modular structure would also allow the programmers to hide
information as required and implement internal routines as they see fit
without changing the outer specifications.
2. LAYERED STRUCTURE
One way to achieve modularity in the operating system is the layered
approach. In this, the bottom layer is the hardware and the topmost layer is the
user interface.
An image demonstrating the layered approach is as follows −

3. MONOLITHIC STRUCTURE:

The Monolithic operating System in which the kernel acts as a manager

by managing all things like file management, memory management, device
management, and operational processes of the Operating System.

The kernel is the heart of a computer operating system (OS). Kernel delivers
basic services to all other elements of the System. It serves as the primary
interface between the Operating System and the hardware.

In monolithic systems, kernels can directly access all the resources of the
operating System like physical hardware, exp Keyboard, Mouse etc.
The monolithic kernel is another name for the monolithic operating system.
Batch processing and time-sharing maximize the usability of a processor by
multiprogramming. The monolithic kernel functions as a virtual machine by
working on top of the Operating System and controlling all hardware
components. This is an outdated operating system that was used in banks to
accomplish minor activities such as batch processing and time- sharing, which
enables many people at various terminals to access the Operating System.

A Diagram of the Monolithic structure is shown below

Advantages of Monolithic structure:

• It is simple to design and implement because all operations are

managed by kernel only, and layering is not needed.
 • As services such as memory management, file management, process
scheduling, etc., are implemented in the same address space, the
execution of the monolithic kernel is relatively fast as compared to
normal systems. Using the same address saves time for address
allocation for new processes and makes it faster.

Disadvantages of Monolithic structure:

• If any service in the monolithic kernel fails, the entire System fails
because, in address space, the services are connected to each other and
affect each other.
• It is not flexible, and to introduce a new service

4 .MICRO-KERNEL

Micro-Kernel structure designs the Operating System by removing all

non-essential components of the kernel. These non-essential components
of kernels are implemented as systems and user programs. Hence these
implemented systems are called as Micro-Kernels.

Each Micro-Kernel is made independently and is isolated from other

Micro-Kernels. So this makes the system more secure and reliable. If any Micro-
Kernel fails, then the remaining operating System remains untouched and
works fine.
Advantages of Micro-kernel structure:

• It allows the operating system to be portable between platforms.

• As each Micro-Kernel is isolated, it is safe and trustworthy.
• Because Micro-Kernels are smaller, they can be successfully tested.
• If any component or Micro-Kernel fails, the remaining operating System
is unaffected and continues to function normally.

Disadvantages of Micro-kernel structure:

• Increased inter-module communication reduces system performance.

• System is complex to be constructed.
5. OPERATING SYSTEM SERVICES:

An Operating System provides services to both the users and to the programs.

• It provides programs an environment to execute.

• It provides users the services to execute the programs in a convenient manner.

Following are a few common services provided by an operating system −

• Program execution
• I/O operations
• File System manipulation
• Communication
• Error Detection
• Resource Allocation
• Protection

1. Program execution

Operating systems handle many kinds of activities from user programs to system
programs like printer spooler, name servers, file server, etc. Each of these activities is
encapsulated as a process.

A process includes the complete execution context (code to execute, data to manipulate,
registers, OS resources in use). Following are the major activities of an operating system
with respect to program management −

• Loads a program into memory.

 • Executes the program.
• Handles program's execution.
• Provides a mechanism for process synchronization.
• Provides a mechanism for process communication.
• Provides a mechanism for deadlock handling.

2. I/O Operation

An I/O subsystem comprises of I/O devices and their corresponding driver

software. Drivers hide the peculiarities of specific hardware devices from the users.

An Operating System manages the communication between user and device drivers.

• I/O operation means read or write operation with any file or any specific I/O
device.
• Operating system provides the access to the required I/O device when required.

3. File system manipulation

A file represents a collection of related information. Computers can store files on

the disk (secondary storage), for long-term storage purpose. Examples of storage media
include magnetic tape, magnetic disk and optical disk drives like CD, DVD. Each of these
media has its own properties like speed, capacity, data transfer rate and data access
methods.

A file system is normally organized into directories for easy navigation and usage. These
directories may contain files and other directions. Following are the major activities of
an operating system with respect to file management −
 • Program needs to read a file or write a file.
• The operating system gives the permission to the program for operation on file.
• Permission varies from read-only, read-write, denied and so on.
• Operating System provides an interface to the user to create/delete files.
• Operating System provides an interface to the user to create/delete directories.
• Operating System provides an interface to create the backup of file system.

4. Communication

In case of distributed systems which are a collection of processors that do not share
memory, peripheral devices, or a clock, the operating system manages communications
between all the processes. Multiple processes communicate with one another through
communication lines in the network.

The OS handles routing and connection strategies, and the problems of contention and
security. Following are the major activities of an operating system with respect to
communication −

• Two processes often require data to be transferred between them

• Both the processes can be on one computer or on different computers, but are
connected through a computer network.
• Communication may be implemented by two methods, either by Shared Memory or
by Message Passing.
5. Error handling

Errors can occur anytime and anywhere. An error may occur in CPU, in I/O devices or
in the memory hardware. Following are the major activities of an operating system with
respect to error handling −

• The OS constantly checks for possible errors.

• The OS takes an appropriate action to ensure correct and consistent computing.

6. Resource Management
 In case of multi-user or multi-tasking environment, resources such as main memory,
CPU cycles and files storage are to be allocated to each user or job. Following are the
major activities of an operating system with respect to resource management −

• The OS manages all kinds of resources using schedulers.

• CPU scheduling algorithms are used for better utilization of CPU.

7. Protection

Considering a computer system having multiple users and concurrent execution of

multiple processes, the various processes must be protected from each other's activities.

Protection refers to a mechanism or a way to control the access of programs, processes,

or users to the resources defined by a computer system. Following are the major activities
of an operating system with respect to protection −

• The OS ensures that all access to system resources is controlled.

• The OS ensures that external I/O devices are protected from invalid access
attempts.
• The OS provides authentication features for each user by means of passwords.
10. DESIGN AND IMPLEMENTATION:

An operating system is a construct that allows the user application programs to

interact with the system hardware. Operating system by itself does not provide
any function but it provides an atmosphere in which different applications and
programs can do useful work.

There are many problems that can occur while designing and implementing an
operating system. These are covered in operating system design and
implementation.
1. OPERATING SYSTEM DESIGN GOALS

It is quite complicated to define all the goals and specifications of the

operating system while designing [Link] design changes depending on the type of
the operating system i.e if it is batch system, time shared system, single user
system, multi user system, distributed system etc.

There are basically two types of goals while designing an operating system. These
are −

2. User Goals
The operating system should be convenient, easy to use, reliable, safe and fast
according to the users. However, these specifications are not very useful as there
is no set method to achieve these goals.

3. SYSTEM GOALS
The operating system should be easy to design, implement and maintain. These are
specifications required by those who create, maintain and operate the operating
system. But there is not specific method to achieve these goals as well.
OPERATING SYSTEM MECHANISMS AND POLICIES

There is no specific way to design an operating system as it is a highly

creative task. However, there are general software principles that are applicable
to all operating systems.

A subtle difference between mechanism and policy is that mechanism shows

how to do something and policy shows what to do. Policies may change over time
and this would lead to changes in mechanism. So, it is better to have a general
mechanism that would require few changes even when a policy change occurs.

For example - If the mechanism and policy are independent, then few
changes are required in mechanism if policy changes. If a policy favours I/O
intensive processes over CPU intensive processes, then a policy change to
preference of CPU intensive processes will not change the mechanism.
[Link] SYSTEM IMPLEMENTATION

The operating system needs to be implemented after it is designed. Earlier

they were written in assembly language but now higher level languages are used.
The first system not written in assembly language was the Master Control Program
(MCP) for Burroughs Computers.

Advantages of Higher Level Language

There are multiple advantages to implementing an operating system using
a higher level language such as: the code is written more fast, it is compact and also
easier to debug and understand. Also, the operating system can be easily moved
from one hardware to another if it is written in a high level language.

Disadvantages of Higher Level Language

Using high level language for implementing an operating system leads to a
loss in speed and increase in storage requirements. However in modern systems
only a small amount of code is needed for high performance, such as the CPU
scheduler and memory manager. Also, the bottleneck routines in the system can
be replaced by assembly language equivalents if required.
 UNIT II
PROCESS MANAGEMENT
Processes - Process Concept - Process Scheduling - Operations on Processes - Inter-
process Communication; CPU Scheduling - Scheduling criteria - Scheduling algorithms:
Threads - Multithread Models – Threading issues; Process Synchronization - The Critical-
Section problem - Synchronization hardware – Semaphores – Mutex - Classical problems
of synchronization - Monitors; Deadlock - Methods for handling deadlocks, Deadlock
prevention, Deadlock avoidance, Deadlock detection, Recovery from deadlock.

1. PROCESS CONCEPT:
A question that arises in discussing operating systems involves what to call all the
CPU activities. A batch system executes jobs, whereas a time-shared system has
user programs, or tasks. Even on a single-user system such as Microsoft Windows, a
user may be able to run several programs at one time: a word processor, a web
browser, and an e-mail package. Even if the user can execute only one program at a
time, the operating system may need to support its own internal programmed
activities, such as memory management. In many respects, all these activities are
similar, so we call all of them processes. The terms job and process are used almost
interchangeably in this text. Although we personally prefer the term process, much
of operating-system theory and terminology was developed during a time when the
major activity of operating systems was job processing. It would be misleading to
avoid the use of commonly accepted terms that include the word job (such as job
scheduling) simply because process has superseded job.
The Process
Informally, as mentioned earlier, a process is a program in execution. A process is
more than the program code, which is sometimes known as the text section. It also
includes the current activity, as represented by the value of the program counter
and the contents of the processor's registers. A process generally also includes the
process stack, which contains temporary data (such as function parameters, return
addresses, and local variables), and a data section, which contains global variables.
A process may also include a heap, which is memory that is dynamically allocated
during process run time. We emphasize that a program by itself is not a process; a
program is a passive entity, such as a file containing a list of instructions stored on
disk (often called an executable file), whereas a process is an active entity, with a
program counter specifying the next instruction to execute and a set of associated
resources. A program becomes a process when an executable file is loaded into
memory. Two common techniques for loading executable files are double-clicking
an icon representing the executable file and entering the name of the executable file
on the command line (as in prog. exe or a. out.) Although two processes may be
associated with the same program, they are nevertheless considered two separate
execution sequences. For instance, several users may be running different copies of
the mail program, or the same user may invoke many copies of the web browser
program. Each of these is a separate process; and although the text sections are
equivalent, the data, heap, and stack sections vary. It is also common to have a
process that spawns many processes as it runs.

Process State
As a process executes, it changes state. The state of a process is defined in part by
the current activity of that process. Each process may be in one of the following
states:
• New. The process is being created.
• Running. Instructions are being executed.
• Waiting. The process is waiting for some event to occur (such as an I/O
completion or reception of a signal).
• Ready. The process is waiting to be assigned to a processor.
• Terminated.

The process has finished execution. These names are arbitrary, and they vary
across operating systems. The states that they represent are fotind on all systems,
however. Certain operating systems also more finely delineate process states. It is
important to realize that only one process can be running on any processor at any
instant. Many processes may be ready and limiting, however..
Process Control Block
Each process is represented in the operating system by a process control block
(PCB)—also called a task control block. It contains many pieces of information
associated with a specific process, including these: • Process state. The state may be
new, ready, running, waiting, halted, and so on.
Program counter. The counter indicates the address of the next instruction to be
executed for this process.
• CPU registers. The registers vary in number and type, depending on the computer
architecture. They include accumulators, index registers, stack pointers, and
general-purpose registers, plus any condition-code information. Along with the
program counter, this state information must be saved when an interrupt occurs, to
allow the process to be continued correctly afterward
• CPU-scheduling information. This information includes a process priority,
pointers to scheduling queues, and any other scheduling parameters.
• Memory-management information. This information may include such
information as the value of the base and limit registers, the page tables, or the
segment tables, depending on the memory system used by the operating system .
• Accounting information. This information includes the amount of CPU and real
time used, time limits, account mimbers, job or process numbers, and so on.
• I/O status information. This information includes the list of I/O devices allocated
to the process, a list of open files, and so on. In brief, the PCB simply serves as the
repository for any information that may vary from process to process.
[Link] Scheduling
The process scheduling is the activity of the process manager that handles the removal of the running
process from the CPU and the selection of another process on the basis of a particular strategy.
Process scheduling is an essential part of a Multiprogramming operating systems. Such operating systems
allow more than one process to be loaded into the executable memory at a time and the loaded process
shares the CPU using time multiplexing.

Categories of Scheduling
There are two categories of scheduling:

1. Non-preemptive: Here the resource can’t be taken from a process until the process completes
execution. The switching of resources occurs when the running process terminates and moves to a
waiting state.
2. Preemptive: Here the OS allocates the resources to a process for a fixed amount of time. During
resource allocation, the process switches from running state to ready state or from waiting state to ready
state. This switching occurs as the CPU may give priority to other processes and replace the process
with higher priority with the running process.

Process Scheduling Queues

The OS maintains all Process Control Blocks (PCBs) in Process Scheduling Queues. The OS maintains a separate
queue for each of the process states and PCBs of all processes in the same execution state are placed in the same
queue. When the state of a process is changed, its PCB is unlinked from its current queue and moved to its new
state queue.
The Operating System maintains the following important process scheduling queues −
• Job queue − This queue keeps all the processes in the system.
• Ready queue − This queue keeps a set of all processes residing in main memory, ready and waiting to
execute. A new process is always put in this queue.
• Device queues − The processes which are blocked due to unavailability of an I/O device constitute this
queue.
The OS can use different policies to manage each queue (FIFO, Round Robin, Priority, etc.). The OS
scheduler determines how to move processes between the ready and run queues which can only have
one entry per processor core on the system; in the above diagram, it has been merged with the CPU.

wo-State Process Model

Two-state process model refers to running and non-running states which are described below −

S.N. State & Description

1
Running
When a new process is created, it enters into the system as in the running state.

2
Not Running
Processes that are not running are kept in queue, waiting for their turn to execute.
Each entry in the queue is a pointer to a particular process. Queue is
implemented by using linked list. Use of dispatcher is as follows. When a process
is interrupted, that process is transferred in the waiting queue. If the process has
completed or aborted, the process is discarded. In either case, the dispatcher
then selects a process from the queue to execute.

Schedulers
Schedulers are special system software which handle process scheduling in various ways. Their main task
is to select the jobs to be submitted into the system and to decide which process to run. Schedulers are of
three types −
 • Long-Term Scheduler
• Short-Term Scheduler
• Medium-Term Scheduler

Long Term Scheduler

It is also called a job scheduler. A long-term scheduler determines which programs are admitted to the
system for processing. It selects processes from the queue and loads them into memory for execution.
Process loads into the memory for CPU scheduling.
The primary objective of the job scheduler is to provide a balanced mix of jobs, such as I/O bound and
processor bound. It also controls the degree of multiprogramming. If the degree of multiprogramming is
stable, then the average rate of process creation must be equal to the average departure rate of processes
leaving the system.
On some systems, the long-term scheduler may not be available or minimal. Time-sharing operating
systems have no long term scheduler. When a process changes the state from new to ready, then there is
use of long-term scheduler.

Short Term Scheduler

It is also called as CPU scheduler. Its main objective is to increase system performance in accordance
with the chosen set of criteria. It is the change of ready state to running state of the process. CPU
scheduler selects a process among the processes that are ready to execute and allocates CPU to one of
them.
Short-term schedulers, also known as dispatchers, make the decision of which process to execute next.
Short-term schedulers are faster than long-term schedulers.

Medium Term Scheduler

Medium-term scheduling is a part of swapping. It removes the processes from the memory. It reduces the
degree of multiprogramming. The medium-term scheduler is in-charge of handling the swapped out-
processes.
A running process may become suspended if it makes an I/O request. A suspended processes cannot
make any progress towards completion. In this condition, to remove the process from memory and make
space for other processes, the suspended process is moved to the secondary storage. This process is
called swapping, and the process is said to be swapped out or rolled out. Swapping may be necessary to
improve the process mix.

Comparison among Scheduler

S.N. Long-Term Scheduler Short-Term Scheduler Medium-Term Scheduler

1 It is a job scheduler It is a CPU scheduler It is a process swapping

 scheduler.

2 Speed is lesser than short Speed is fastest among Speed is in between both
term scheduler other two short and long term
scheduler.

3 It controls the degree of It provides lesser control It reduces the degree of

multiprogramming over degree of multiprogramming.
multiprogramming

4 It is almost absent or It is also minimal in time It is a part of Time sharing

minimal in time sharing sharing system systems.
system

5 It selects processes from It selects those It can re-introduce the

pool and loads them into processes which are process into memory and
memory for execution ready to execute execution can be continued.

Context Switching
A context switching is the mechanism to store and restore the state or context of a CPU in
Process Control block so that a process execution can be resumed from the same point at a
later time. Using this technique, a context switcher enables multiple processes to share a single
CPU. Context switching is an essential part of a multitasking operating system features.
When the scheduler switches the CPU from executing one process to execute another, the state
from the current running process is stored into the process control block. After this, the state
for the process to run next is loaded from its own PCB and used to set the PC, registers, etc. At that
point, the second process can start executing.
Context switches are computationally intensive since register and memory state must be saved
and restored. To avoid the amount of context switching time, some hardware systems employ
two or more sets of processor registers. When the process is switched, the following
information is stored for later use.

• Program Counter
• Scheduling information
• Base and limit register value
• Currently used register
• Changed State
• I/O State information
• Accounting information
SCHEDULING ALGORITHM
A Process Scheduler schedules different processes to be assigned to the CPU based on
particular scheduling algorithms. There are six popular process scheduling algorithms which we are
going to discuss in this chapter −

• First-Come, First-Served (FCFS) Scheduling

• Shortest-Job-Next (SJN) Scheduling
• Priority Scheduling
• Shortest Remaining Time
• Round Robin(RR) Scheduling
• Multiple-Level Queues Scheduling
These algorithms are either non-preemptive or preemptive. Non-preemptive algorithms are
designed so that once a process enters the running state, it cannot be preempted until it completes
its allotted time, whereas the preemptive scheduling is based on priority where a scheduler may
preempt a low priority running process anytime when a high priority process enters into a ready
state.

First Come First Serve (FCFS)

• Jobs are executed on first come, first serve basis.
• It is a non-preemptive, pre-emptive scheduling algorithm.
• Easy to understand and implement.
• Its implementation is based on FIFO queue.
Poor in performance as average wait time is high.
Wait time of each process is as follows −

Process Wait Time : Service Time - Arrival Time

P0 0-0=0

P1 5-1=4

P2 8-2=6

P3 16 - 3 = 13

Average Wait Time: (0+4+6+13) / 4 = 5.75

Shortest Job Next (SJN)

• This is also known as shortest job first, or SJF
• This is a non-preemptive, pre-emptive scheduling algorithm.
• Best approach to minimize waiting time.
• Easy to implement in Batch systems where required CPU time is known in advance.
• Impossible to implement in interactive systems where required CPU time is not known.
• The processer should know in advance how much time process will take.
Given: Table of processes, and their Arrival time, Execution time
 Process Arrival Time Execution Time Service Time

P0 0 5 0

P1 1 3 5

P2 2 8 14

P3 3 6 8

Waiting time of each process is as follows −

Process Waiting Time

P0 0-0=0

P1 5-1=4

P2 14 - 2 = 12

P3 8-3=5

Average Wait Time: (0 + 4 + 12 + 5)/4 = 21 / 4 = 5.25

Priority Based Scheduling
• Priority scheduling is a non-preemptive algorithm and one of the most common scheduling
algorithms in batch systems.
• Each process is assigned a priority. Process with highest priority is to be executed first and
so on.
• Processes with same priority are executed on first come first served basis.
• Priority can be decided based on memory requirements, time requirements or any other
resource requirement.
Given: Table of processes, and their Arrival time, Execution time, and priority. Here we are
considering 1 is the lowest priority.

Process Arrival Time Execution Time Priority Service Time

P0 0 5 1 0

P1 1 3 2 11

P2 2 8 1 14

P3 3 6 3 5

Waiting time of each process is as follows –

 Process Waiting Time

P0
0-0=0

P1 11 - 1 = 10

P2 14 - 2 = 12

P3 5-3=2

Average Wait Time: (0 + 10 + 12 + 2)/4 = 24 / 4 = 6

Shortest Remaining Time

• Shortest remaining time (SRT) is the preemptive version of the SJN algorithm.
• The processor is allocated to the job closest to completion but it can be preempted by a
newer ready job with shorter time to completion.
• Impossible to implement in interactive systems where required CPU time is not known.
• It is often used in batch environments where short jobs need to give preference.

Round Robin Scheduling

• Round Robin is the preemptive process scheduling algorithm.
• Each process is provided a fix time to execute, it is called a quantum.
• Once a process is executed for a given time period, it is preempted and other process
executes for a given time period.
• Context switching is used to save states of preempted processes.
Wait time of each process is as follows −

Process Wait Time : Service Time - Arrival Time

P0 (0 - 0) + (12 - 3) = 9

P1 (3 - 1) = 2

P2 (6 - 2) + (14 - 9) + (20 - 17) = 12

P3 (9 - 3) + (17 - 12) = 11

Average Wait Time: (9+2+12+11) / 4 = 8.5

Multiple-Level Queues Scheduling

Multiple-level queues are not an independent scheduling algorithm. They make use of other existing
algorithms to group and schedule jobs with common characteristics.

• Multiple queues are maintained for processes with common characteristics.

• Each queue can have its own scheduling algorithms.
• Priorities are assigned to each queue.
For example, CPU-bound jobs can be scheduled in one queue and all I/O-bound jobs in another
queue. The Process Scheduler then alternately selects jobs from each queue and assigns them to
the CPU based on the algorithm assigned to the queue.
 9. Threads

A thread is a flow of execution through the process code, with its own program counter that
keeps track of which instruction to execute next, system registers which hold its current working
variables, and a stack which contains the execution history.

A thread shares with its peer threads few information like code segment, data segment and open
files. When one thread alters a code segment memory item, all other threads see that.

A thread is also called a lightweight process. Threads provide a way to improve

application performance through parallelism. Threads represent a software approach to improving
performance of operating system by reducing the overhead thread is equivalent to a classical
process.

Each thread belongs to exactly one process and no thread can exist outside a process. Each
thread represents a separate flow of control. Threads have been successfully used in
implementing network servers and web server. They also provide a suitable foundation for parallel
execution of applications on shared memory multiprocessors. The following figure shows the
working of a single-threaded and a multithreaded process.
Difference between Process and Thread

S.N. Process Thread

1 Process is heavy weight or resource intensive. Thread is light weight, taking

lesser resources than a process.

2 Process switching needs interaction with operating Thread switching does not need
system. to interact with operating system.

3 In multiple processing environments, each process All threads can share same set of
executes the same code but has its own memory and open files, child processes.
file resources.

4 If one process is blocked, then no other process can While one thread is blocked and
 execute until the first process is unblocked. waiting, a second thread in the
same task can run.

5 Multiple processes without using threads use more Multiple threaded processes use
resources. fewer resources.

6 In multiple processes each process operates One thread can read, write or
independently of the others. change another thread's data.

Advantages of Thread

• Threads minimize the context switching time.

• Use of threads provides concurrency within a process.
• Efficient communication.
• It is more economical to create and context switch threads.
• Threads allow utilization of multiprocessor architectures to a greater scale and efficiency.

Types of Thread

Threads are implemented in following two ways −

• User Level Threads − User managed threads.

• Kernel Level Threads − Operating System managed threads acting on kernel, an
operating system core.
User Level Threads

In this case, the thread management kernel is not aware of the existence of threads. The thread
library contains code for creating and destroying threads, for passing message and data between
threads, for scheduling thread execution and for saving and restoring thread contexts. The
application starts with a single thread.

Advantages
• Thread switching does not require Kernel mode privileges.
• User level thread can run on any operating system.
• Scheduling can be application specific in the user level thread.
• User level threads are fast to create and manage.
Disadvantages
• In a typical operating system, most system calls are blocking.
• Multithreaded application cannot take advantage of multiprocessing.

Kernel Level Threads

In this case, thread management is done by the Kernel. There is no thread management
code in the application area. Kernel threads are supported directly by the operating system. Any
application can be programmed to be multithreaded. All of the threads within an application are
supported within a single process.

The Kernel maintains context information for the process as a whole and for individual’s threads
within the process. Scheduling by the Kernel is done on a thread basis. The Kernel performs
thread creation, scheduling and management in Kernel space. Kernel threads are generally
slower to create and manage than the user threads.

Advantages
• Kernel can simultaneously schedule multiple threads from the same process on multiple
processes.
• If one thread in a process is blocked, the Kernel can schedule another thread of the same
process.
• Kernel routines themselves can be multithreaded.
Disadvantages
• Kernel threads are generally slower to create and manage than the user threads.
• Transfer of control from one thread to another within the same process requires a mode
switch to the Kernel.

Multithreading Models
 Some operating system provides a combined user level thread and Kernel level thread facility.
Solaris is a good example of this combined approach. In a combined system, multiple threads
within the same application can run in parallel on multiple processors and a blocking system call
need not block the entire process. Multithreading models are three types

• Many to many relationship.

• Many to one relationship.
• One to one relationship.

Many to Many Models

The many-to-many model multiplexes any number of user threads onto an equal or smaller
number of kernel threads.

The following diagram shows the many-to-many threading model where 6 user level threads are
multiplexing with 6 kernel level threads. In this model, developers can create as many user
threads as necessary and the corresponding Kernel threads can run in parallel on a
multiprocessor machine. This model provides the best accuracy on concurrency and when a
thread performs a blocking system call, the kernel can schedule another thread for execution.
Many to One Model

Many-to-one model maps many user level threads to one Kernel-level thread. Thread
management is done in user space by the thread library. When thread makes a blocking system
call, the entire process will be blocked. Only one thread can access the Kernel at a time, so
multiple threads are unable to run in parallel on multiprocessors.

If the user-level thread libraries are implemented in the operating system in such a way that
the system does not support them, then the Kernel threads use the many-to-one relationship
modes.
One to One Model

There is one-to-one relationship of user-level thread to the kernel-level thread. This model
provides more concurrency than the many-to-one model. It also allows another thread to run when
a thread makes a blocking system call. It supports multiple threads to execute in parallel on
microprocessors.

Disadvantage of this model is that creating user thread requires the corresponding Kernel thread.
OS/2, windows NT and windows 2000 use one to one relationship model.
Difference between User-Level & Kernel-Level Thread

S.N. User-Level Threads Kernel-Level Thread

1 User-level threads are faster to create and manage. Kernel-level threads are slower to
create and manage.

2 Implementation is by a thread library at the user level. Operating system supports creation
of Kernel threads.

3 User-level thread is generic and can run on any Kernel-level thread is specific to the
operating system. operating system.

4 Multi-threaded applications cannot take advantage of Kernel routines themselves can be

multiprocessing. multithreaded.
THREADING ISSUES:

We can discuss some of the issues to consider in designing multithreaded programs. These
issued are as follows −

The fork() and exec() system calls

The fork() is used to create a duplicate process. The meaning of the fork() and exec() system
calls change in a multithreaded program.

If one thread in a program which calls fork(), does the new process duplicate all threads, or is the
new process single-threaded? If we take, some UNIX systems have chosen to have two versions
of fork(), one that duplicates all threads and another that duplicates only the thread that invoked
the fork() system call.

If a thread calls the exec() system call, the program specified in the parameter to exec() will
replace the entire process which includes all threads.

Signal Handling
Generally, signal is used in UNIX systems to notify a process that a particular event has occurred.
A signal received either synchronously or asynchronously, based on the source of and the reason
for the event being signalled.

All signals, whether synchronous or asynchronous, follow the same pattern as given below −

• A signal is generated by the occurrence of a particular event.

• The signal is delivered to a process.
• Once delivered, the signal must be handled.
Cancellation
Thread cancellation is the task of terminating a thread before it has completed.

For example − If multiple database threads are concurrently searching through a database and
one thread returns the result the remaining threads might be cancelled.

A target thread is a thread that is to be cancelled, cancellation of target thread may occur in two
different scenarios −
 • Asynchronous cancellation − One thread immediately terminates the target thread.
• Deferred cancellation − The target thread periodically checks whether it should terminate,
allowing it an opportunity to terminate itself in an ordinary fashion.
Thread polls
Multithreading in a web server, whenever the server receives a request it creates a separate
thread to service the request.

Some of the problems that arise in creating a thread are as follows −

• The amount of time required to create the thread prior to serving the request together with
the fact that this thread will be discarded once it has completed its work.
• If all concurrent requests are allowed to be serviced in a new thread, there is no bound on
the number of threads concurrently active in the system.
• Unlimited thread could exhaust system resources like CPU time or memory.
A thread pool is to create a number of threads at process start-up and place them into a pool,
where they sit and wait for work.
10. PROCESS SYNCHRONIZATION

The concept of Process synchronization in an Operating System.

Process Synchronization was introduced to handle problems that arose

while multiple process executions.

Process is categorized into two types on the basis of synchronization and

these are given below:

• Independent Process
• Cooperative Process

1. Independent Processes

Two processes are said to be independent if the execution of one process

does not affect the execution of another process.

2. Cooperative Processes
Two processes are said to be cooperative if the execution of one process
affects the execution of another process. These processes need to be
synchronized so that the order of execution can be guaranteed.
Process Synchronization

It is the task phenomenon of coordinating the execution of processes in

such a way that no two processes can have access to the same shared
data and resources.

• It is a procedure that is involved in order to preserve the

appropriate order of execution of cooperative processes.
• In order to synchronize the processes, there are various
synchronization mechanisms.
• Process Synchronization is mainly needed in a multi-process
system when multiple processes are running together, and more
than one processes try to gain access to the same shared resource
or any data at the same time.

1. Race Condition

At the time when more than one process is either executing the
same code or accessing the same memory or any shared variable; In that
condition, there is a possibility that the output or the value of the shared
variable is wrong so for that purpose all the processes are doing the race
to say that my output is correct. This condition is commonly known as a
race condition. As several processes access and process the
manipulations on the same data in a concurrent manner and due to
which the outcome depends on the particular order in which the access
of data takes place.

Mainly this condition is a situation that may occur inside

the critical section. Race condition in the critical section happens when
the result of multiple thread execution differs according to the order in
which the threads execute. But this condition is critical sections can be
avoided if the critical section is treated as an atomic instruction. Proper
thread synchronization using locks or atomic variables can also prevent
race conditions.

2. Critical Section Problem

A Critical Section is a code segment that accesses shared variables

and has to be executed as an atomic action. It means that in a group of
cooperating processes, at a given point of time, only one process must be
executing its critical section. If any other process also wants to execute
its critical section, it must wait until the first one finishes. The entry to
the critical section is mainly handled by wait() function while the exit
from the critical section is controlled by the signal() function.
3. Entry Section

In this section mainly the process requests for its entry in the
critical section.

4. Exit Section

This section is followed by the critical section.

The solution to the Critical Section Problem

A solution to the critical section problem must satisfy the following

three conditions:
1. Mutual Exclusion

Out of a group of cooperating processes, only one process can be in its

critical section at a given point of time.

2. Progress

If no process is in its critical section, and if one or more threads want to

execute their critical section then any one of these threads must be
allowed to get into its critical section.

3. Bounded Waiting

After a process makes a request for getting into its critical section, there
is a limit for how many other processes can get into their critical section,
before this process's request is granted. So after the limit is reached, the
system must grant the process permission to get into its critical section.

Solutions for the Critical Section

The critical section plays an important role in Process

Synchronization so that the problem must be solved.

Some widely used method to solve the critical section problem is as

follows:
1. Peterson’s Solution

This is widely used and software-based solution to critical section

problems. Peterson's solution was developed by a computer scientist
Peterson that's why it is named so.

With the help of this solution whenever a process is executing in any

critical state, then the other process only executes the rest of the code,
and vice-versa can happen. This method also helps to make sure of the
thing that only a single process can run in the critical section at a specific
time.

This solution preserves all three conditions:

• Mutual Exclusion is comforted as at any time only one process can

access the critical section.
• Progress is also comforted, as a process that is outside the critical
section is unable to block other processes from entering into the
critical section.
• Bounded Waiting is assured as every process gets a fair chance to
enter the Critical section.
• Suppose there are N processes (P1, P2, ... PN) and as at some point
of time every process requires to enter in the Critical Section
• A FLAG[] array of size N is maintained here which is by default
false. Whenever a process requires to enter in the critical section, it
has to set its flag as true. Example: If Pi wants to enter it will
set FLAG[i]=TRUE.
• Another variable is called TURN and is used to indicate the process
number that is currently waiting to enter into the critical section.
• The process that enters into the critical section while exiting would
change the TURN to another number from the list of processes that
are ready.
 • Example: If the turn is 3 then P3 enters the Critical section and
while exiting turn=4 and therefore P4 breaks out of the wait loop.

Synchronization Hardware

Many systems provide hardware support for critical section code.

The critical section problem could be solved easily in a single-processor
environment if we could disallow interrupts to occur while a shared
variable or resource is being modified.

In this manner, we could be sure that the current sequence of

instructions would be allowed to execute in order without pre-emption.
Unfortunately, this solution is not feasible in a multiprocessor
environment.

Disabling interrupt on a multiprocessor environment can be time-

consuming as the message is passed to all the processors.

This message transmission lag delays the entry of threads into the
critical section, and the system efficiency decreases.

Mutex Locks

As the synchronization hardware solution is not easy to implement

for everyone, a strict software approach called Mutex Locks was
introduced. In this approach, in the entry section of code, a LOCK is
acquired over the critical resources modified and used inside the critical
section, and in the exit section that LOCK is released.

As the resource is locked while a process executes its critical

section hence no other process can access it.
UNIT III MEMORY MANAGEMENT
Main Memory - Swapping - Contiguous Memory Allocation – Paging - Structure of the Page Table -
Segmentation, Segmentation with paging; Virtual Memory - Demand Paging – Copy on Write - Page
Replacement - Allocation of Frames –Thrashing.

1. MAIN MEMORY
The main memory is the fundamental storage unit in a computer system. It is associatively large and quick
memory and saves programs and information during computer operations. The technology that makes the main
memory work is based on semiconductor integrated circuits.
RAM is the main memory. Integrated circuit Random Access Memory (RAM) chips are applicable in two
possible operating modes are as follows −

• Static − It consists of internal flip-flops, which store the binary information. The stored data remains solid
considering power is provided to the unit. The static RAM is simple to use and has smaller read and write
cycles.
• Dynamic − It saves the binary data in the structure of electric charges that are used to capacitors. The
capacitors are made available inside the chip by Metal Oxide Semiconductor (MOS) transistors. The stored
value on the capacitors contributes to discharge with time and thus, the capacitors should be regularly
recharged through stimulating the dynamic memory.

Random Access Memory

The term Random Access Memory or RAM is typically used to refer to memory that is easily read from and
written to by the microprocessor. For a memory to be called random access, it should be possible to access any
address at any time. This differentiates RAM from storage devices such as tapes or hard drives where the data is
accessed sequentially.
RAM is the main memory of a computer. Its objective is to store data and applications that are currently in use.
The operating system controls the usage of this memory. It gives instructions like when the items are to be loaded
into RAM, where they are to be located in RAM, and when they need to be removed from RAM.
Read-Only Memory
In each computer system, there should be a segment of memory that is fixed and unaffected by power failure.
This type of memory is known as Read-Only Memory or ROM.

SRAM
RAMs that are made up of circuits and can preserve the information as long as power is supplied are referred to
as Static Random Access Memories (SRAM). Flip-flops form the basic memory elements in an SRAM device.
An SRAM consists of an array of flip-flops, one for each bit. SRAM consists of an array of flip-flops, a large
number of flip-flops are needed to provide higher capacity memory. Because of this, simpler flip-flop circuits,
BJT, and MOS transistors are used for SRAM.

DRAM
SRAMs are faster but their cost is high because their cells require many transistors. RAMs can be obtained at a
lower cost if simpler cells are used. A MOS storage cell based on capacitors can be used to replace the SRAM
cells. Such a storage cell cannot preserve the charge (that is, data) indefinitely and must be recharged
periodically. Therefore, these cells are called dynamic storage cells. RAMs using these cells are referred to as
Dynamic RAMs or simply DRAMs.

2. 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.
 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.

Memory Allocation
Main memory usually has two partitions −
• Low Memory − Operating system resides in this memory.
• High Memory − User processes are held in high memory.
Operating system uses the following memory allocation mechanism.
S.N. Memory Allocation & Description

1
Single-partition allocation
In this type of allocation, relocation-register scheme is used to protect user processes from
each other, and from changing operating-system code and data. Relocation register
contains value of smallest physical address whereas limit register contains range of logical
addresses. Each logical address must be less than the limit register.

2
Multiple-partition allocation
In this type of allocation, main memory is divided into a number of fixed-sized partitions
where each partition should contain only one process. 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.

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.
Fragmentation is of two types −

S.N. Fragmentation & Description

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.

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.
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.
Address Translation
Page address is called logical address and represented by page number and the offset.
Logical Address = Page number + page offset
Frame address is called physical address and represented by a frame number and the offset.
Physical Address = Frame number + page offset
A data structure called page map table is used to keep track of the relation between a page of a process to
a frame in physical memory.
 When the system allocates a frame to any page, it translates this logical address into a physical address
and create entry into the page table to be used throughout execution of the program.
When a process is to be executed, its corresponding pages are loaded into any available memory frames.
Suppose you have a program of 8Kb but your memory can accommodate only 5Kb at a given point in time, then
the paging concept will come into picture. When a computer runs out of RAM, the operating system (OS) will
move idle or unwanted pages of memory to secondary memory to free up RAM for other processes and brings
them back when needed by the program.
This process continues during the whole execution of the program where the OS keeps removing idle
pages from the main memory and write them onto the secondary memory and bring them back when required by
the program.

Advantages and Disadvantages of Paging

Here is a list of advantages and disadvantages of paging −
• 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
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.
 3. Contiguous Memory Allocation

• In this allocation type, the consecutive blocks of memory is allocated to a file/process.

• It executes quickly in comparison to non-contiguous memory.
• It is easy to be controlled by the operating system.
• Minimum overhead since there are not many address translation when a process is being executed.
• There is internal fragmentation in contiguous memory allocation.
• There are different types of partitions: Single partition allocation and multi-partition allocation.
• Memory gets wasted.
• The swapped-in process is arranged in the originally allocated space itself.

Non-contiguous Memory Allocation

• In this type of allocation, separate blocks of memory are allocated to a file/process.

• It executes slowly in comparison to contiguous memory.
• It is difficult to be controlled by the operating system.
• More overhead since it needs to translate multiple addresses.
• It includes paging.
• It includes segmentation.
• No memory is wasted.
• External fragmentation occurs in this type of allocation.
• The swapped-in processes can be arranged in any location in the memory.

Contiguous memory allocation is a memory allocation method that allocates a single contiguous section of
memory to a process or a file. This method takes into account the size of the file or a process and also estimates the
maximum size, up to what the file or process can grow?

Taking into account the future growth of the file and its request for memory, the operating system allocates
sufficient contiguous memory blocks to that file. Considering this future expansion and the file’s request for
memory, the operating system will allocate those many contiguous blocks of memory to that file.

In this section, we will discuss contiguous memory allocation in detail along with its advantages and disadvantages.
So let us star

Contiguous Memory Allocation

1. Memory Allocation
2. Memory Management
3. Fragmentation
4. Advantages and Disadvantages
5. Key Takeaways
Memory Allocation

The main memory has to accommodate both the operating system and userspace. Now, here the userspace has to
accommodate various user processes. We also want these several user processes must reside in the main memory at
the same time.

Now, the question arises how to allocate the available memory space to the user processes that are waiting in a ready
queue?

In Contiguous memory allocation, when the process arrives from the ready queue to the main memory for
execution, the contiguous memory blocks are allocated to the process according to its requirement. Now, to allocate
the contiguous space to user processes, the memory can be divide either in the fixed-sized partition or in the
variable-sized partition.

Fixed-Sized Partition: In the fixed-sized partition, the memory is divided into fixed-sized blocks and each block
contains exactly one process. But, the fixed-sized partition will limit the degree of multiprogramming as the number
of the partition will decide the number of processes.

Variable-Size Partition: In the variable size partition method, the operating system maintains a table that contains
the information about all memory parts that are occupied by the processes and all memory parts that are
still available for the processes.
How holes are created in the memory?

Initially, the whole memory space is available for the user processes as a large block, a hole. Eventually, when the
processes arrive in the memory, executes, terminates and leaves the memory you will see the set of holes of variable
sizes.

In the figure above, you can see that when file A and file C release the memory allocated to them, creates the holes
in the memory of variable size.

In the variable size partition method, the operating system analyses the memory requirement of the process and see
whether it has a memory block of the required size. If it finds the match, then it allocates that memory block to the
process. If not, then it searches the ready queue for the process that has a smaller memory requirement.

The operating system allocates the memory to the process until it cannot satisfy the memory requirement of the next
process in the ready queue. It stops allocating memory to the process if it does not have a memory block (hole) that
is large enough to hold that process.

If the memory block (hole) is too large for the process it gets spilt into two parts. One part of the memory block is
allocated to the arrived process and the other part is returned to the set of holes. When a process terminates and
releases the memory allocated to it, the released memory is then placed back to the set of holes. The two holes that
are adjacent to each other, in the set of holes, are merged to form one large hole.

Now, at this point, the operating system checks whether this newly formed free large hole is able to satisfy the
memory requirement of any process waiting in the ready queue. And the process goes on.

Memory Management

In the above section, we have seen, how the operating system allocates the contiguous memory to the processes.
Here, we will see how the operating system selects a free hole from the set of holes?

The operating system uses either the block allocation list or the bit map to select the hole from the set of holes.

BLOCK ALLOCATION LIST

Block allocation list maintains two tables. One table contains the entries of the blocks that are allocated to the
various files. The other table contains the entries of the holes that are free and can be allocated to the process in the
waiting queue.

Now, as we have entries of free blocks which one must be chosen can be decided using either of these strategies:
first-fit, best-fit, worst-fit strategies.

1. First-fit

Here, the searching starts either at the beginning of the table or from where the previous first-fit search has ended.
While searching, the first hole that is found to be large enough for a process to accommodate is selected.
2. Best-fit

This method needs the list of free holes to be sorted according to their size. Then the smallest hole that is large
enough for the process to accommodate is selected from the list of free holes. This strategy reduces the wastage of
memory as it does not allocate a hole of larger size which leaves some amount of memory even after the process
accommodates the space.

3. Worst-fit

This method requires the entire list of free holes to be sorted. Here, again the largest hole among the free holes is
selected. This strategy leaves the largest leftover hole which may be useful for the other process.

Bit Map

The bit map method only keeps track of the free or allocated block. One block is represented by one bit, bit 0
resembles the free block and bit 1 resembles that the block is allocated to a file or a process.

It does not have entries of the files or processes to which the specific blocks are allocated. Normally, implementing
the first fit will search the number of consecutive zeros/free blocks required by a file of process. Having found that
much of consecutive zeros it allocates a file or process to those blocks.

But implementing best-fit or worse-fit will be expensive, as the table of free blocks sorted according to the hole size
has to be maintained. But the bit map method is easy to implement.

FRAGMENTATION:

Fragmentation can either be external fragmentation or internal fragmentation. External fragmentation is when the
free memory blocks available in memory are too small and even non-contiguous. Whereas, the internal
fragmentation occurs when the process does not fully utilize the memory allocated to it.

The solution to the problem of external fragmentation is memory compaction. Here, all the memory contents are
shuffled to the one area of memory thereby creating a large block of memory which can be allocated to one or more
new processes.
Advantages and Disadvantages

The main disadvantage of contiguous memory allocation is memory wastage and inflexibility. As the memory is
allocated to a file or a process keeping in mind that it will grow during the run. But until a process or a file grows
many blocks allocated to it remains unutilized. And they even they cannot be allocated to the other process leading
to wastage of memory.

In case, the process or the file grows beyond the expectation i.e. beyond the allocated memory block, then it will
abort with the message “No disk space” leading to inflexibility.
 The advantage of contiguous memory allocation is it increases the processing speed. As the operating system uses
the buffered I/O and reads the process memory blocks consecutively it reduces the head movements. This speed ups
the processing.

Key Takeaways

• Memory allocation can be done either by a fixed-sized partition scheme or by variable-sized partition scheme.
• Block allocation list has three methods to select a hole from the list of free holes first-fit, best-fit and worse-fit.
• Bit map keeps track of free blocks in memory, it has one bit for one memory block, bit 0 shows that the block is free
and bit 1 shows the block is allocated to some file or a process.
• Contiguous memory allocation leads to fragmentation. Further fragmentation can either be external or internal.
• Contiguous memory allocation leads to memory wastage and inflexibility.
• If the operating system uses buffered I/O during processing, then contiguous memory allocation can enhance
processing speed.

his is all about contiguous memory allocation. We have discussed how the memory is allocated, managed. How does
mentation occur in contiguous
PAGING:
• The address space of a process is broken into fixed sized blocks.
• These fixed size blocks are known as pages.
• The operating system divides the memory blocks into pages.
• The size of the page is determined based on the memory available.
• This technique is quick in terms of memory access.
• It can cause internal fragmentation since some pages would not be utilized as much as the other
pages.
• During the process of paging, a logical address is divided into page number and page offset.
• A page table is used to store the page data.
This is how Paging works −

Segmentation
• In this method, the address space of a process is broken down into varying sized blocks.
• These varying sized blocks are known as sections.
 • A compiler is responsible in determining the size of the segment, the virtual address and the
actual address.
• The size of the section is determined by the user.
• The process of segmentation is slower in comparison to paging.
• It can result in external fragmentation since some memory blocks may not be used at all.
• During this process, a logical address gets divided into a section number and a section offset.
• A segmentation table can be used to store the segmentation data.
This is how Segmentation techniques works with Segment Map Table −

Both paging and swapping are important concepts in operating systems that place a process in the
main memory for its execution, but they are quite different from each other in many aspects. Read
this article to learn more about paging and swapping and their specific characteristics.

What is Paging?
In OS, Paging is a memory management strategy in which the process address space is divided into
blocks of the same size, called pages (where the size of each page is power of 2, and is between 512
bytes and 8192 bytes). The size of the process is then measured in the number of pages.
In the same way, the main memory is divided into small blocks of fixed size called frames. The size of
each frame is kept the same as that of a page to have the optimum utilization of the main memory
and to avoid the external fragmentation. Therefore, paging is basically a memory allocation technique.
It utilizes non-contiguous memory management technique.
What is Swapping?
Swapping is a memory management technique in which an entire process is copied to another
location. In other words, swapping is a technique in which an entire process is to be placed in the main
memory for its execution. Also, swapping removes the inactive processes from the main memory of
the system.
Swapping helps to provide memory space for the operation of other processes. Hence, swapping
impacts the performance of a system, as it helps in executing multiple large operations concurrently.
Swapping can be done without using any memory management technique.
Now, let us discuss the differences between paging and swapping in detail.

Difference between Paging and Swapping in OS

The following are the important differences between paging and swapping in Os −

[Link]. Swapping Paging

It is process where the entire process It is a memory allocation technique.

1.
is copied to another location.

This process occurs when the entire This process occurs when a part of a process is
2. process has been transferred to the transferred to the disk.
disk.

Here, the data is swapped The contiguous block of memory is made non-
3. temporarily from the main memory contiguous but it consists of fixed size called
to a secondary memory. frames known as pages.

It can be done without using any It uses non-contiguous memory management

4.
memory management methods. technique.

It can be done by processes that are Only a process that is currently active can
5.
inactive as well. perform paging operation.

It helps give a direction with respect There is no suggestion about the solution in
6.
to the solution. this technique.
Structure of Page Table in Operating Systems
In this tutorial, we will cover some of the most common techniques used for structuring the Page table.

The data structure that is used by the virtual memory system in the operating system of a computer in
order to store the mapping between physical and logical addresses is commonly known as Page Table.

As we had already told you that the logical address that is generated by the CPU is translated into the
physical address with the help of the page table.

• Thus page table mainly provides the corresponding frame number (base address of the frame)
where that page is stored in the main memory.

The above diagram shows the paging model of Physical and logical memory.

Characteristics of the Page Table

Some of the characteristics of the Page Table are as follows:
 • It is stored in the main memory.
• Generally; the Number of entries in the page table = the Number of Pages in which the process
is divided.
• PTBR means page table base register and it is basically used to hold the base address for the
page table of the current process.
• Each process has its own independent page table.

Techniques used for Structuring the Page Table

Some of the common techniques that are used for structuring the Page table are as follows:

1. Hierarchical Paging
2. Hashed Page Tables
3. Inverted Page Tables

Let us cover these techniques one by one;

Hierarchical Paging
Another name for Hierarchical Paging is multilevel paging.

• There might be a case where the page table is too big to fit in a contiguous space, so we may
have a hierarchy with several levels.
• In this type of Paging the logical address space is broke up into Multiple page tables.
• Hierarchical Paging is one of the simplest techniques and for this purpose, a two-level page
table and three-level page table can be used.

Two Level Page Table

Consider a system having 32-bit logical address space and a page size of 1 KB and it is further divided
into:

• Page Number consisting of 22 bits.

• Page Offset consisting of 10 bits.
As we page the Page table, the page number is further divided into :

• Page Number consisting of 12 bits.

• Page Offset consisting of 10 bits.

Thus the Logical address is as follows:

In the above diagram,

P1 is an index into the Outer Page table.

P2 indicates the displacement within the page of the Inner page Table.

As address translation works from outer page table inward so is known as forward-mapped Page
Table.

Below given figure below shows the Address Translation scheme for a two-level page table

Three Level Page Table

For a system with 64-bit logical address space, a two-level paging scheme is not appropriate. Let us
suppose that the page size, in this case, is [Link] in this case, we will use the two-page level scheme
then the addresses will look like this:
Thus in order to avoid such a large table, there is a solution and that is to divide the outer page table,
and then it will result in a Three-level page table:

Hashed Page Tables

This approach is used to handle address spaces that are larger than 32 bits.

• In this virtual page, the number is hashed into a page table.

• This Page table mainly contains a chain of elements hashing to the same elements.

Each element mainly consists of :

1. The virtual page number

2. The value of the mapped page frame.
3. A pointer to the next element in the linked list.

Given below figure shows the address translation scheme of the Hashed Page Table:
 The above Figure shows Hashed Page Table

The Virtual Page numbers are compared in this chain searching for a match; if the match is found then
the corresponding physical frame is extracted.

In this scheme, a variation for 64-bit address space commonly uses clustered page tables.

Clustered Page Tables

• These are similar to hashed tables but here each entry refers to several pages (that is 16) rather
than 1.
• Mainly used for sparse address spaces where memory references are non-contiguous and
scattered

Inverted Page Tables

The Inverted Page table basically combines A page table and A frame table into a single data structure.

• There is one entry for each virtual page number and a real page of memory
• And the entry mainly consists of the virtual address of the page stored in that real memory
location along with the information about the process that owns the page.
• Though this technique decreases the memory that is needed to store each page table; but it
also increases the time that is needed to search the table whenever a page reference occurs.
Given below figure shows the address translation scheme of the Inverted Page Table:

In this, we need to keep the track of process id of each entry, because many processes may have the
same logical addresses.

Also, many entries can map into the same index in the page table after going through the hash
function. Thus chaining is used in order to handle this.

Segmentation in Operating Systems

In this tutorial, we will be covering segmentation in the Operating System.

Segmentation is another way of dividing the addressable memory. It is another scheme of memory
management and it generally supports the user view of memory. The Logical address space is basically
the collection of segments. Each segment has a name and a length.

Basically, a process is divided into segments. Like paging, segmentation divides or segments the
memory. But there is a difference and that is while the paging divides the memory into a fixed size and
on the other hand, segmentation divides the memory into variable segments these are then loaded
into logical memory space.

A Program is basically a collection of segments. And a segment is a logical unit such as:

• main program
• procedure
• function
• method
• object
• local variable and global variables.
• symbol table
 • common block
• stack
• arrays

Types of Segmentation
Given below are the types of Segmentation:

• Virtual Memory Segmentation With this type of segmentation, each process is segmented into
n divisions and the most important thing is they are not segmented all at once.
• Simple Segmentation With the help of this type, each process is segmented into n divisions and
they are all together segmented at once exactly but at the runtime and can be non-contiguous
(that is they may be scattered in the memory).

Characteristics of Segmentation
Some characteristics of the segmentation technique are as follows:

• The Segmentation partitioning scheme is variable-size.

• Partitions of the secondary memory are commonly known as segments.
• Partition size mainly depends upon the length of modules.
• Thus with the help of this technique, secondary memory and main memory are divided into
unequal-sized partitions.

Need of Segmentation
One of the important drawbacks of memory management in the Operating system is the separation of
the user's view of memory and the actual physical memory. and Paging is a technique that provides the
separation of these two memories.

User'view is basically mapped onto physical storage. And this mapping allows differentiation between
Physical and logical memory.

It is possible that the operating system divides the same function into different pages and those pages
may or may not be loaded into the memory at the same time also Operating system does not care
about the User's view of the process. Due to this technique system's efficiency decreases.

Segmentation is a better technique because it divides the process into segments.

User's View of a Program

Given below figure shows the user's view of segmentation:

logical address

Basic Method
A computer system that is using segmentation has a logical address space that can be viewed as
multiple segments. And the size of the segment is of the variable that is it may grow or shrink. As we
had already told you that during the execution each segment has a name and length. And the address
mainly specifies both thing name of the segment and the displacement within the segment.

Therefore the user specifies each address with the help of two quantities: segment name and offset.

For simplified Implementation segments are numbered; thus referred to as segment number rather
than segment name.

Thus the logical address consists of two tuples:

<segment-number,offset>

where,

Segment Number(s): Segment Number is used to represent the number of bits that are required to
represent the segment.

Offset(d) Segment offset is used to represent the number of bits that are required to represent the size
of the segment.
Segmentation Architecture
Segment Table

A Table that is used to store the information of all segments of the process is commonly known as
Segment Table. Generally, there is no simple relationship between logical addresses and physical
addresses in this scheme.

• The mapping of a two-dimensional Logical address into a one-dimensional Physical address is

done using the segment table.
• This table is mainly stored as a separate segment in the main memory.
• The table that stores the base address of the segment table is commonly known as the
Segment table base register (STBR)

In the segment table each entry has :

1. Segment Base/base address: The segment base mainly contains the starting physical address
where the segments reside in the memory.
2. Segment Limit: The segment limit is mainly used to specify the length of the segment.

Segment Table Base Register(STBR) The STBR register is used to point the segment table's location in
the memory.

Segment Table Length Register(STLR) This register indicates the number of segments used by a
program. The segment number s is legal if s<STLR

Segmentation Hardware
Given below figure shows the segmentation hardware :

The logical address generated by CPU consist of two parts:

Segment Number(s): It is used as an index into the segment table.

Offset(d): It must lie in between '0' and 'segment limit'.In this case, if the Offset exceeds the segment
limit then the trap is generated.

Thus; correct offset+segment base= address in Physical memory

and segment table is basically an array of base-limit register pair.

Advantages of Segmentation
The Advantages of the Segmentation technique are as follows:

• In the Segmentation technique, the segment table is mainly used to keep the record of
segments. Also, the segment table occupies less space as compared to the paging table.
• There is no Internal Fragmentation.
• Segmentation generally allows us to divide the program into modules that provide better
visualization.
 • Segments are of variable size.

Disadvantages of Segmentation
Some disadvantages of this technique are as follows:

• Maintaining a segment table for each process leads to overhead

• This technique is expensive.
• The time is taken in order to fetch the instruction increases since now two memory accesses
are required.
• Segments are of unequal size in segmentation and thus are not suitable for swapping.
• This technique leads to external fragmentation as the free space gets broken down into smaller
pieces along with the processes being loaded and removed from the main memory then this
will result in a lot of memory waste.

Example of Segmentation
Given below is the example of the segmentation, There are five segments numbered from 0 to 4. These
segments will be stored in Physical memory as shown. There is a separate entry for each segment in
the segment table which contains the beginning entry address of the segment in the physical memory(
denoted as the base) and also contains the length of the segment(denoted as limit).
Segment 2 is 400 bytes long and begins at location 4300. Thus in this case a reference to byte 53 of
segment 2 is mapped onto the location 4300 (4300+53=4353). A reference to segment 3, byte 85 is
mapped to 3200(the base of segment 3)+852=4052.

A reference to byte 1222 of segment 0 would result in the trap to the OS, as the length of this segment
is 1000 bytes.

Difference between Paging and Segmentation

In this tutorial we will be covering the difference between Paging and Segmentation these are two
different Memory management techniques in Operating systems.
Paging in OS
Paging is basically a technique of memory management in the operating system. In this technique, the
operating system retrieves the processes from the secondary memory into the main memory and this
memory is in the form of pages. Paging is a logical concept.

With the help of this technique, the main memory is split into the small blocks of physical memory that
are commonly known as frames. In paging size of frames is fixed. In order to prevent external
fragmentation and for the maximum usage of the main memory, the frame size must be the same as
the page size. This technique helps to access the data faster.

Segmentation in OS
Segmentation is another technique of memory management. This technique is similar to Paging except
for the fact that in segmentation the segments of a process are of variable length but in Paging the
pages are of fixed size.

The memory is split into variable-length parts in segmentation. Each part is commonly known as
segments. Information related to each segment is stored in a table and this table is commonly known
as the segment table. The segment table generally occupies less space as compared to the paging
table.
Differences between Paging and Segmentation
Now, we will cover the differences between Paging and Segmentation in the table given below:

Paging Segmentation

Paging is a memory management technique Segmentation is also a memory management technique

where memory is partitioned into fixed-sized where memory is partitioned into variable-sized blocks
blocks that are commonly known as pages. that are commonly known as segments.
 Paging Segmentation

With the help of Paging, the logical address is With the help of Segmentation, the logical address is
divided into a page number and page offset. divided into section number and section offset.

This technique may lead to Internal

Segmentation may lead to External Fragmentation.
Fragmentation.

In Paging, the page size is decided by the While in Segmentation, the size of the segment is
hardware. decided by the user.

In order to maintain the page data, the page table In order to maintain the segment data, the segment table
is created in the Paging is created in the Paging

The page table mainly contains the base address The segment table mainly contains the segment number
of each page. and the offset.

This technique is faster than segmentation. On the other hand, segmentation is slower than paging.

In Paging, a list of free frames is maintained by the In Segmentation, a list of holes is maintained by the
 Paging Segmentation

Operating system. Operating system.

In this technique, in order to calculate the In this technique, in order to calculate the absolute
absolute address page number and the offset both address segment number and the offset both are
are required. required.
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.
Modern microprocessors intended for general-purpose use, a memory management unit, or MMU, is built into
the hardware. The MMU's job is to translate virtual addresses into physical addresses. A basic example is
given below −
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.
Virtual memory is the partition of logical memory from physical memory. This partition supports large virtual
memory for programmers when only limited physical memory is available.
Virtual memory can give programmers the deception that they have a very high memory although the
computer has a small main memory. It creates the function of programming easier because the programmer no
longer requires to worry about the multiple physical memory available.
Virtual memory works similarly, but at one level up in the memory hierarchy. A memory management unit
(MMU) transfers data between physical memory and some gradual storage device, generally a disk. This
storage area can be defined as a swap disk or swap file, based on its execution. Retrieving data from physical
memory is much faster than accessing data from the swap disk.
There are two primary methods for implementing virtual memory are as follows −

• Paging
Paging is a technique of memory management where small fixed-length pages are allocated instead of a single
large variable-length contiguous block in the case of the dynamic allocation technique. In a paged system,
each process is divided into several fixed-size ‘chunks’ called pages, typically 4k bytes in length. The memory
space is also divided into blocks of the equal size known as frames.

Advantages of Paging

There are the following advantages of Paging are −

• In Paging, there is no requirement for external fragmentation.
• In Paging, the swapping among equal-size pages and page frames is clear.
• Paging is a simple approach that it can use for memory management.

Disadvantage of Paging

There are the following disadvantages of Paging are −

• In Paging, there can be a chance of Internal Fragmentation.
 • In Paging, the page table employs more memory.
• Because of Multi-level Paging, there can be a chance of memory reference overhead.
• Segmentation
The partition of memory into logical units called segments, according to the user’s perspective is called
segmentation. Segmentation allows each segment to grow independently, and share. In other words,
segmentation is a technique that partition memory into logically related units called a segment. It means that
the program is a collection of the segment.
Unlike pages, segments can vary in size. This requires the MMU to manage segmented memory somewhat
differently than it would manage paged memory. A segmented MMU contains a segment table to maintain
track of the segments resident in memory.
A segment can initiate at one of several addresses and can be of any size, each segment table entry should
contain the start address and segment size. Some system allows a segment to start at any address, while other
limits the start address. One such limit is found in the Intel X86 architecture, which requires a segment to start
at an address that has 6000 as its four low-order bits.

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.
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 −

• Large virtual memory.

• More efficient use of memory.
• There is no limit on degree of multiprogramming.
Disadvantages
• Number of tables and the amount of processor overhead for handling page interrupts are greater than in
the case of the simple paged management techniques.

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

First In First Out (FIFO) algorithm

• Oldest page in main memory is the one which will be selected for replacement.
• Easy to implement, keep a list, replace pages from the tail and add new pages at the head.
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.

Least Recently Used (LRU) algorithm

• Page which has not been used for the longest time in main memory is the one which will be selected for
replacement.
• Easy to implement, keep a list, replace pages by looking back into time.
Page Buffering algorithm

• To get a process start quickly, keep a pool of free frames.

• On page fault, select a page to be replaced.
• Write the new page in the frame of free pool, mark the page table and restart the process.
• Now write the dirty page out of disk and place the frame holding replaced page in free pool.

Least frequently Used(LFU) algorithm

• The page with the smallest count is the one which will be selected for replacement.
• This algorithm suffers from the situation in which a page is used heavily during the initial phase of a
process, but then is never used again.

Most frequently Used(MFU) algorithm

• This algorithm is based on the argument that the page with the smallest count was probably just brought
in and has yet to be used.
 COPY-ON-WRITE IN OPERATING SYSTEM:

In this tutorial, we will be covering the Copy on Write which is one of the resource management
techniques.

Copy-on-Write(CoW) is mainly a resource management technique that allows the parent and child process
to share the same pages of the memory initially. If any process either parent or child modifies the shared page,
only then the page is copied.

The CoW is basically a technique of efficiently copying the data resources in the computer system. In this
case, if aunit of data is copied but is not modified then "copy" can mainly exist as a reference to the original
data.

But when the copied data is modified, then at that time its copy is created(where new bytes are actually
written )assuggested from the name of the technique.

The main use of this technique is in the implementation of the fork system call in which it shares the virtual
memory/pages of the Operating system.

Recall in the UNIX(OS), the fork() system call is used to create a duplicate process of the parent process which
isknown as the child process.

• The CoW technique is used by several Operating systems like Linux, Solaris, and Windows XP.
• The CoW technique is an efficient process creation technique as only the pages that are
modified arecopied.

Free pages in this technique are allocated from a pool of zeroed-out pages.

The Copy on Write(CoW) Technique

The main intention behind the CoW technique is that whenever a parent process creates a child process both
parent andchild process initially will share the same pages in the memory.

• These shared pages between parent and child process will be marked as copy-on-write which means
that if the parent or child process will attempt to modify the shared pages then a copy of these pages will be
created and the modifications will be done only on the copy of pages by that process and it will not affect other
processes.

Now its time to take a look at the basic example of this technique:

Let us take an example where Process A creates a new process that is Process B, initially both these processes will
sharethe same pages of the memory.
Figure: Above figure indicates parent and child process sharing the same pages

Now, let us assume that process A wants to modify a page in the memory. When the Copy-on-write(CoW) technique is
used, only those pages that are modified by either process are copied; all the unmodified pages can be easily shared by
the parent and child process.

Figure: After Page Z is modified by Process A

Whenever it is determined that a page is going to be duplicated using the copy-on-write technique, then it is important to
note the location from where the free pages will be allocated. There is a pool of free pages for such requests; provided
by many operating systems.

And these free pages are allocated typically when the stack/heap for a process must expand or when there are copy-on-
write pages to manage.

These pages are typically allocated using the technique that is known as Zero-fill-on-demand. And the Zero-fill-on-
demand pages are zeroed-out before being allocated and thus erasing the previous content.

Page Fault in Operating System

In this tutorial, we will be covering the concept of page fault and how to handle page fault in the Operating System.
PAGE FAULT IN OPERATING SYSTEM:

Page fault dominates more like an error. It mainly occurs when any program tries to access the data or
the code that is in the address space of the program, but that data is not currently located in the RAM
of the system.

• So basically when the page referenced by the CPU is not found in the main memory then the
situation is termed as Page Fault.
• Whenever any page fault occurs, then the required page has to be fetched from the secondary
memory into the main memory.

In case if the required page is not loaded into the memory, then a page fault trap arises

The page fault mainly generates an exception, which is used to notify the operating system that it must
have to retrieve the "pages" from the virtual memory in order to continue the execution. Once all the
data is moved into the physical memory the program continues its execution normally. The Page fault
process takes place in the background and thus goes unnoticed by the user.

• The hardware of the computer tracks to the kernel and the program counter (PC) is generally
saved on the [Link] registers store the information of the current state of instruction.
• An assembly program is started that usually saves the general registers and also saves the other
volatile information to prevent the OS from destroying it.

Handling the Page Fault

Given below is the simple procedure to handle the page fault:

Figure: Steps to Handle the Page fault

If you will access a page that is marked as invalid then it also causes a Page Fault. Then the Paging
hardware during translating the address through the page table will notice that the invalid bit is set
that will cause a trap to the Operating system.

This trap is mainly the result of the failure of the Operating system in order to bring the desired page
into memory.

Let us understand the procedure to handle the page fault as shown with the help of the above
diagram:

1. First of all, internal table(that is usually the process control block) for this process in order to
determine whether the reference was valid or invalid memory access.
2. If the reference is invalid, then we will terminate the process. If the reference is valid, but we
have not bought in that page so now we just page it in.
3. Then we locate the free frame list in order to find the free frame.
4. Now a disk operation is scheduled in order to read the desired page into the newly allocated
frame.
5. When the disk is completely read, then the internal table is modified that is kept with the
process, and the page table that mainly indicates the page is now in memory.
6. Now we will restart the instruction that was interrupted due to the trap. Now the process can
access the page as though it had always been in memory.
Page Replacement Algorithms in Operating System
In this tutorial, we will be covering the concept of Page replacement and its algorithms in the
Operating system.

As studied in Demand Paging, only certain pages of a process are loaded initially into the memory.
This allows us to get more processes into 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 :

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 and is most commonly used.

In this case, if a process requests a new page and supposes there are no free frames, then the
Operating system needs to decide which page to replace. The operating system must use any page
replacement algorithm in order to select the victim frame. The Operating system must then write the
victim frame to the disk then read the desired page into the frame and then update the page tables.
And all these require double the disk access time.

• Page replacement prevents the over-allocation of the memory by modifying the page-fault
service routine.
• To reduce the overhead of page replacement a modify bit (dirty bit) is used in order to
indicate whether each page is modified.
• This technique provides complete separation between logical memory and physical memory.

Page Replacement in OS

In Virtual Memory Management, Page Replacement Algorithms play an important role. The main
objective of all the Page replacement policies is to decrease the maximum number of page faults.

Page Fault – It is basically a memory error, and it occurs when the current programs attempt to access
the memory page for mapping into virtual address space, but it is unable to load into the physical
memory then this is referred to as Page fault.

Basic Page Replacement Algorithm in OS

Page Replacement technique uses the following approach. If there is no free frame, then we will find
the one that is not currently being used and then free it. A-frame can be freed by writing its content to
swap space and then change the page table in order to indicate that the page is no longer in the
memory.

1. First of all, find the location of the desired page on the disk.
2. Find a free Frame: a) If there is a free frame, then use it. b) If there is no free frame then make
use of the page-replacement algorithm in order to select the victim frame. c) Then after that
write the victim frame to the disk and then make the changes in the page table and frame table
accordingly.
3. After that read the desired page into the newly freed frame and then change the page and
frame tables.
4. Restart the process.

Figure: Page Replacement

Page Replacement Algorithms in OS

This algorithm helps to decide which pages must be swapped out from the main memory in order to
create a room for the incoming page. This Algorithm wants the lowest page-fault rate.
Various Page Replacement algorithms used in the Operating system are as follows;

Let us discuss all algorithms one by one in the upcoming sections:

1. FIFO Page Replacement Algorithm

It is a very simple way of Page replacement and is referred to as First in First Out. This algorithm mainly
replaces the oldest page that has been present in the main memory for the longest time.

• This algorithm is implemented by keeping the track of all the pages in the queue.

• As new pages are requested and are swapped in, they are added to the tail of a queue and the
page which is at the head becomes the victim.
• This is not an effective way of page replacement but it can be used for small systems.

Advantages

• This algorithm is simple and easy to use.

• FIFO does not cause more overhead.

Disadvantages

• This algorithm does not make the use of the frequency of last used time rather it just replaces
the Oldest Page.
 • There is an increase in page faults as page frames increases.
• The performance of this algorithm is the worst.

2. LIFO Page Replacement Algorithm

This Page Replacement algorithm stands for "Last In First Out".This algorithm works in a similar way to
the LIFO principle.

• In this, the newest page is replaced which is arrived at last in the primary memory
• This algorithm makes use of the stack for monitoring all the pages.

3. LRU Page Replacement Algorithm in OS

This algorithm stands for "Least recent used" and this algorithm helps the Operating system to search
those pages that are used over a short duration of time frame.

• The page that has not been used for the longest time in the main memory will be selected for
replacement.
• This algorithm is easy to implement.
• This algorithm makes use of the counter along with the even-page.

Advantages of LRU

• It is an efficient technique.
• With this algorithm, it becomes easy to identify the faulty pages that are not needed for a long
time.
• It helps in Full analysis.

Disadvantages of LRU

• It is expensive and has more complexity.

• There is a need for an additional data structure.

4. Optimal Page Replacement Algorithm

This algorithm mainly replaces the page that will not be used for the longest time in the future. The
practical implementation of this algorithm is not possible.
 • Practical implementation is not possible because we cannot predict in advance those pages that
will not be used for the longest time in the future.
• This algorithm leads to less number of page faults and thus is the best-known algorithm

Also, this algorithm can be used to measure the performance of other algorithms.

Advantages of OPR

• This algorithm is easy to use.

• This algorithm provides excellent efficiency and is less complex.
• For the best result, the implementation of data structures is very easy

Disadvantages of OPR

• In this algorithm future awareness of the program is needed.

• Practical Implementation is not possible because the operating system is unable to track the
future request

5. Random Page Replacement Algorithm

As indicated from the name this algorithm replaces the page randomly. This Algorithm can work like
any other page replacement algorithm that is LIFO, FIFO, Optimal, and LRU.
THRASHING IN OPERATING SYSTEM

In this tutorial, we will be covering the concept of thrashing in the Operating system.

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.

Let's understand by an example, if any process does not have the number of frames that it needs to
support pages in active use then it will quickly page fault. And at this point, the process must
replace some pages. As all the pages of the process are actively in use, it must replace a page that
will be needed again right away. Consequently, the process will quickly fault again, and again, and
again, replacing pages that it must bring back in immediately. This high paging activity by a
process is called thrashing.

During thrashing, the CPU spends less time on some actual productive work spend more time
swapping.
 Figure: Thrashing

Causes of Thrashing

Thrashing affects the performance of execution in the Operating system. Also, thrashing results in
severe performance problems in the Operating system.

When the utilization of CPU is low, then the process scheduling mechanism tries to load many
processes into the memory at the same time due to which degree of Multiprogramming can be
increased. Now in this situation, there are more processes in the memory as compared to the
available number of frames in the memory. Allocation of the limited amount of frames to each
process.
Whenever any process with high priority arrives in the memory and if the frame is not freely
available at that time then the other process that has occupied the frame is residing in the frame
will move to secondary storage and after that this free frame will be allocated to higher priority
process.

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.

Effect of Thrashing

At the time, when thrashing starts then the operating system tries to apply either the Global page
replacement Algorithm or the Local page replacement algorithm.

Global Page Replacement

The Global Page replacement has access to bring any page, whenever thrashing found it tries to
bring more pages. Actually, due to this, no process can get enough frames and as a result, the
thrashing will increase more and more. Thus the global page replacement algorithm is not suitable
whenever thrashing happens.

Local Page Replacement

Unlike the Global Page replacement, the local page replacement will select pages which only
belongs to that process. Due to this, there is a chance of a reduction in the thrashing. As it is also
proved that there are many disadvantages of Local Page replacement. Thus local page replacement
is simply an alternative to Global Page replacement.

Techniques used to handle the thrashing

As we have already told you the Local Page replacement is better than the Global Page
replacement but local page replacement has many disadvantages too, so it is not suggestible. Thus
given below are some other techniques that are used:
Working-Set Model

This model is based on the assumption of the locality. It makes the use of the parameter ? in order
to define the working-set window. The main idea is to examine the most recent? page reference.
What locality is saying, the recently used page can be used again, and also the pages that are
nearby this page will also be used?

1. Working Set

The set of the pages in the most recent? page reference is known as the working set. If a page is in
active use, then it will be in the working set. In case if the page is no longer being used then it will
drop from the working set ? times after its last reference.

The working set mainly gives the approximation of the locality of the program.

The accuracy of the working set mainly depends on? what is chosen?

This working set model avoids thrashing while keeping the degree of multiprogramming as high as
possible.
2. Page Fault Frequency

The working-set model is successful and its knowledge can be useful in preparing but it is a very
clumpy approach in order to avoid thrashing. There is another technique that is used to avoid
thrashing and it is Page Fault Frequency(PFF) and it is a more direct approach.

The main problem is how to prevent thrashing. As thrashing has a high page fault rate and also we
want to control the page fault rate.

When the Page fault is too high, then we know that the process needs more frames. Conversely, if
the page fault-rate is too low then the process may have too many frames.

We can establish upper and lower bounds on the desired page faults. If the actual page-fault rate
exceeds the upper limit then we will allocate the process to another frame. And if the page fault
rate falls below the lower limit then we can remove the frame from the process.

Thus with this, we can directly measure and control the page fault rate in order to prevent
thrashing.
 UNIT IV STORAGE MANAGEMENT
Mass Storage system – Disk Structure - Disk Scheduling and Management; File-System Interface - File
concept - Access methods - Directory Structure - Directory organization - File system mounting - File
Sharing and Protection; File System Implementation - File System Structure - Directory implementation -
Allocation Methods - Free Space Management; I/O Systems – I/O Hardware, Application I/O interface,
Kernel I/O subsystem.

1. Mass storage system :

Storage Management is defined as it refers to the management of the data storage equipment’s that are
used to store the user/computer generated data. Hence it is a tool or set of processes used by an administrator to
keep your data and storage equipment’s safe. Storage management is a process for users to optimize the use of
storage devices and to protect the integrity of data for any media on which it resides and the category of storage
management generally contain the different type of subcategories covering aspects such as security, virtualization
and more, as well as different types of provisioning or automation, which is generally made up the entire storage
management software market.
Storage management key attributes: Storage management has some key attribute which is generally used to
manage the storage capacity of the system. These are given below:
1. Performance
2. Reliability
3. Recoverability
4. Capacity
Feature of Storage management: There is some feature of storage management which is provided for storage
capacity. These are given below:
1. Storage management is a process that is used to optimize the use of storage devices.
2. Storage management must be allocated and managed as a resource in order to truly benefit a corporation.
3. Storage management is generally a basic system component of information systems.
4. It is used to improve the performance of their data storage resources.
Advantage of storage management: There are some advantage of storage management which are given below:
● It becomes very simple to manage a storage capacity.
● It generally reduces the time consumption.
 ● It improves the performance of system.
● In virtualization and automation technologies, it can help an organization improve its agility.
Limitations of storage management:
● Limited physical storage capacity: Operating systems can only manage the physical storage space that is
available, and as such, there is a limit to how much data can be stored.
● Performance degradation with increased storage utilization: As more data is stored, the system’s
performance can decrease due to increased disk access time, fragmentation, and other factors.
● Complexity of storage management: Storage management can be complex, especially as the size of the
storage environment grows.
● Cost: Storing large amounts of data can be expensive, and the cost of additional storage capacity can add
up quickly.
● Security issues: Storing sensitive data can also present security risks, and the operating system must have
robust security features in place to prevent unauthorized access to this data.
● Backup and Recovery: Backup and recovery of data can also be challenging, especially if the data is
stored on multiple systems or devices.

4.1. MASS STORAGE SYSTEM IN OPERATING SYSTEMS

Now, we are going to learn about each and every mass storage device in detail. But before learning about them let
us know about what is a primary and secondary memory.

Primary Memory
A processor or computer initially or directly accesses primary memory while using a computer. It enables a
processor to access programs and services that are now in use and temporarily stored in a particular area of
memory.

Primary storage and main memory are the other terms which can be used as a substitute to the term primary
memory.
The volatile storage component of a computer system is primary memory. Although there may be data buses,
cache memory, or Random Access Memory (RAM), RAM is the most common example for primary memory.
An operating system (OS), user interface, and any user-installed and running software utilities are all loaded into
main memory as soon as a computer turns on. When a program or application is launched from main memory, it
communicates with the system processor to carry out all of its unique functions.
Secondary memory is said to be slower than primary memory.
Secondary Memory
Secondary memory is non-volatile, permanent computer memory that is not directly accessible by a computer or
processor. Data that can be quickly and easily retrieved, transmitted, and utilized by apps and services can be
stored by the user and then used in this manner.
Secondary storage is another name which can be used as a substitute to the word secondary memory.
Read-only memory (ROM), flash drives, hard disk drives (HDD), magnetic tapes, and other forms of internal and
external storage media are all considered secondary memory. Only the major or main memory may access
secondary memory during computations, and only then is it sent to the processor.
Even if the computer is not powered on, data can be stored and retained in secondary memory, which is slower
than primary memory. Additionally, it has large storage capacity, with each memory being capable of holding
anywhere from a few megabytes (MB) to many terabytes (TB).
Secondary memory is said to be slower than primary memory.
All the mass storage media belongs to the secondary memory.

Difference between Primary Memory and Secondary Memory

S. Primary Memory Secondary Memory

No

1.) Primary Memory is also primarily known as main Secondary Memory is also primarily
memory or primary storage memory known as secondary memory storage

2.) They are also known as Internal Memory They are also known as Auxiliary Memory
or Backup Memory or Additional Memory.

3.) Primary Memory is more costlier than Secondary Memory Secondary Memory is less costlier than
Secondary Memory

4.) Primary memory is said to be faster than Secondary Secondary memory is said to be slower
memory. than primary memory.
5.) It stores information or data that the processing unit is It has a substantial amount of information
currently using. Usually, capacity ranges from sixteen and data storage. Typically, capacity
Giga Bytes (16 GB) to Thirty Two Giga Bytes (32 GB). ranges from 200 GB to terabytes.

6.) The Primary Memory can be divided as Volatile and Non The Secondary Memory can only be
Volatile Memories classified as Non Volatile Memory only.

7.) Data cannot be preserved in the event of a power outage Because it has a non-volatile memory, the
since it is a volatile memory. information may be kept even in the event
of a power outage.

Now, let us learn about the types of the Mass Storage Media which are present in the market.
Mass Storage Structure
Systems designed to store enormous volumes of data are referred to as mass storage devices. Massive storage
devices are sometimes used interchangeably with peripheral storage, which is the management of bigger volumes
of data that are larger than the native storage capability of a computer or device.
The basic idea of Mass Storage is to create a Data Backup or Data Recovery System.
Along with computer systems, definitions of mass storage technologies and tactics have changed. The earliest and
most basic mass storage techniques date back to the era of main frame supercomputers, according to experts.
Punch cards, Hollerith cards, and other relatively similar manual storage medium are examples of this Mass
Storage Media these days. Today, mass storage may include several kinds of hard disks or solid-state storage
devices, as well as tape drives and other physical data storage devices.
The concepts of data backup and data recovery are frequently linked to mass storage media. The biggest Business
Companies will make plans for recording, storing, and backing up all accessible data, which calls for a lot more
mass storage media than what factory-direct gear can provide. This suggests a method for handling continuous
mass storage that uses tape or other media. Other kinds of mass storage could function well as a data storage plan
for a big network or a bunch of mobile distant devices. To backup data on a portable tablet that doesn't have a lot
of internal capacity, for instance, mass storage for a tablet might require the usage of flash or Universal Serial Bus
media (USB Media).
The Mass Storage Structure Devices are:
1. Magnetic Disks
2. Solid State Disks
3. Magnetic Tapes
Magnetic Disks
Now, we are going to know about all whereabouts of the Magnetic Disk Mass Storage Structure Devices.
The process of magnetization is used to write, rewrite, and access data on a magnetic disk, a storage device. This
process is known as Magnetic Disk. It is coated magnetically and has tracks, spots, and sectors for storing data.
In 1956, IBM created the first magnetic hard drive, a substantial device with 50 21-inch (53-cm) platters. Despite
being large, it could only hold 5 megabytes of information. Since then, magnetic disks' storage capabilities have
multiplied dramatically while simultaneously shrinking in size.
Basic Common Examples of Magnetic Disks are:
1. Floppy Disks
2. Hard Disks
3. Zip Disks

The Magnetic Disk basically looks like:

Structure and Working of Magnetic Disks:

The basic structure of Magnetic Disks is:
A mechanical arm that travels across a revolving magnetic surface, known as the platter, makes up the majority of
a magnetic disk. They come together to make a "comb." Both reading from and writing to the disk are done using
the mechanical arm. A magnetization process is used to read and write data on magnetic disks.
One or more disk-shaped platters with magnetic material covering them. Unlike "floppy" disks, which are
composed of more flexible plastic, hard disk platters are built of stiff metal.
There are two work areas on each plate. The very top and bottom surfaces of a stack of platters were occasionally
avoided by older hard disk drives because they are more prone to damage or even breaking in some cases.
The arm's head slides across the platter's surface while it continues to spin rapidly. The head floats on a small
layer of air since the entire apparatus is hermetically sealed. Tiny patches on the disk surface are magnetized and
data is saved when a small current is delivered to the head. When the head needs to read the data, a little current
could be delivered to such tiny locations on the platter.
On the disk, data is arranged in sectors and tracks, with tracks serving as the disk's spherical divisions. Blocks of
data are separated into sectors, which are a subset of tracks. The sectors are where the magnetic disk's read and
write operations are carried out. Because the tracks are so close together, the floating heads need to be controlled
extremely precisely while reading or writing data.
The tracks are a series of concentric circles that separate each working surface. A cylinder is a group of tracks that
are all at the same distance from the platter's edge, or in the accompanying figure, all the tracks that are directly
above one another.
A piece track is further split into sectors, generally storing 512 bytes of data each, however some newer drives
occasionally employ greater sector sizes.
(Sectors also include a header and a trailer, which among other things contain checksum data. Although internal
fragmentation and the quantity of disk that has to be designated bad in the event of mistakes are increased by
larger sector sizes, the percentage of the disk used by headers and trailers is reduced.)
Read-write heads are used to read data from hard drives. In the typical setup (shown below), one head is used for
each surface, mounted on a separate arm, and moved concurrently from one cylinder to the next by a shared arm
assembly. (Other designs, such as separate read-write heads, might accelerate disk access but present significant
technical challenges.)
The number of heads (or working surfaces) times the number of tracks per surface times the number of sectors per
track times the number of bytes per sector equals the storage capacity of a conventional disk drive. The head-
sector-cylinder number of a specific physical block of data can be used to identify it.
The time needed to move the heads from one cylinder to another and for the heads to settle down after the transfer
is known as the positioning time, also known as the seek time or random access time. This is usually the stage
that moves slowly and is the main obstacle to high transfer rates.
The time it takes for the requested sector to spin and enter the read-write head is known as the rotational latency.
This can be anything from 0 and 1 complete revolutions, with an average of 12 revolutions. This is a physical
action that often follows seek time as the second-slowest step. (If a disk rotates at 7200 revolutions per minute,
the average rotational delay is 1/2 revolution / 120 revolutions per second, or just over 4 milliseconds, a long time
by computer standards.
The amount of time needed to electronically transmit data from a disk to a computer is called the transfer rate.
(Some writers could also use the phrase "transfer rate" to refer to the entire transfer rate, which includes search
time, rotational delay, and the transfer rate of electronic data.)
Over the surface, disk heads "fly" on a paper-thin air cushion. In the event that they should unintentionally make
contact with the disk, a head crash takes place, which may or may not permanently harm or even entirely destroy
the disk. Due of this, it is customary to park the disk heads while shutting off a computer, which entails moving
the heads off the disk or to an empty space on the disk.
Typically, floppy disks are removeable. Hard drives may also be taken out and replaced with fresh ones, and
some of them can even be swapped out while the computer is still functioning.
The I/O Bus, a connection used to connect disk drives to computers, is used for this purpose. Enhanced Integrated
Drive Electronics (EIDE), Advanced Technology Attachment (ATA), Serial ATA (SATA), Universal Serial Bus
(USB), Fiber Channel (FC), and Small Computer Systems Interface (SCSI) are a few of the popular interface
types.
The disk controller is included within the disk itself, whereas the host controller is located at the I/O bus's
computer end. Via Input Output ports, the CPU sends orders to the host controller. The disk controller moves
information from the onboard cache to the host controller and motherboard memory at electronic speeds after
moving information between the magnetic surface and onboard cache.
Solid State Disks
Old technologies are frequently employed in new ways as economic conditions and technology evolve. The
growing usage of solid state drives, or SSDs, is one illustration of this.
SSDs function as a tiny, quick hard disk using memory technology. To maintain the information over power
cycles, certain implementations may employ either flash memory or DRAM chips protected by a battery.
Due to the lack of moving components, SSDs operate far more quickly than conventional hard drives, and some
issues, such the scheduling of disk accesses, simply do not exist.
SSDs do have certain drawbacks, too, including the fact that they cost more than hard drives, are often smaller,
and may have shorter life spans.
As a high-speed cache for information on hard disks that has to be retrieved fast, SSDs are particularly helpful.
One use is to store frequently requested file system meta-data, such as directory and I node information. A boot
drive is another version that has the OS and certain application executables but no essential user data. In order to
make laptops thinner, lighter, and quicker, SSDs are also employed in them.
The throughput of the bus may become a limiting problem due to how much quicker SSDs are than conventional
hard drives, which leads to certain SSDs being linked directly to the system PCI bus.
Magnetic Tapes
Prior to the advent of hard disk drives, magnetic tapes were frequently utilized for secondary storage; today, they
are mostly used for backups.
It might take a while to get to a specific location on a magnetic tape, but once reading or writing starts, access
rates are on par with disk drives.
Tape drive capacities may be anywhere from 20 and 200 GB, and compression can increase that capacity by
double.
4.2. DISK STRUCTURE
What is Hard Disk ?
Hard Disk is a secondary storage device. It is a type of electro mechanical device. A hard disk stores
and retrieves digital data using magnetic storage. Disk is rigid rapidly rotating platters coated with
magnetic material.
Hard Disk Pack consist of more than one disk.
How Data is Stored in a Hard Disk ?
● Data is stored in Disk in form of tracks and sectors.
● Disk surface is divided in to tracks.
● Track is further dived in to sectors.
● Sector is the addressable unit in disk.
Basic picture for disk storage concept is given below

Disk Structure in OS
Disk structure is as shown in following figure
Step wise description of Disk Structure is given below
● Disk surfacе dividеd into tracks
● A rеad/writе hеad positionеd just abovе thе disk surfacе
● Information storеd by magnеtic rеcording on thе track undеr rеad/writе hеad
● Fixеd hеad disk
● Moving hеad disk
● Dеsignеd for largе amount of storagе
● Primary dеsign considеration cost, sizе, and spееd
Hardwarе for disk systеm
● Disk drivе, Dеvicе motor, Rеad/writе hеad, Associatеd logic
Disk controllеr
● Dеtеrminеs thе logical intеraction with thе computеr
 ● Can sеrvicе morе than onе drivе (ovеrlappеd sееks)
Cylindеr
● Thе samе numbеrеd tracks on all thе disk surfacеs
● Еach track contains bеtwееn 8 to 32 sеctors
Sеctor
● Smallеst unit of information that can bе rеad from/writtеn into disk
● Rangе from 32 bytеs to 4096 bytеs
Disk Performance Parameters
Some important parameters used to measure the performance of hard disk are as follow
Sееk timе
● Seek Timе is time rеquirеd by rеad/writе hеad to movе to rеquеstеd track
● Includеs thе initial startup timе and thе timе rеquirеd to travеrsе thе tracks to bе crossеd oncе thе
accеss arm is up to spееd.
Latеncy or rotational dеlay
● Timе rеquirеd for thе rеquеstеd sеctor to comе undеr thе rеad/writе hеad.
● Rotational delay is generally the half of the time taken in one rotation.
Data Transfer Rate
Data transfer rate is define as the amount of data transfer in per unit time for example 30 MB/Sec.
Data Transfer Time
Data Transfer time is the total time taken to transfer a specific amount of data from the disk. Data
Transfer time depends on the data transfer rate of the disk.
Average Access Time
Average access time is calculated as
Average Access Time = Seek Time + Rotational Latecny + Data Transfer Time

4.3. DISK SCHEDULING AND MANAGEMENT

Disk scheduling and management are essential components of a computer's operating system that handle
the organization and access of data on a disk. Disk scheduling algorithms determine the order in which
the read/write head of the disk moves to access data, which impacts the efficiency and speed of accessing
data. Some commonly used disk scheduling algorithms include First-Come-First-Serve, Shortest Seek
Time First, and SCAN. Disk management, on the other hand, involves tasks such as disk partitioning,
formatting, and file system creation. It ensures that the disk is properly utilized, optimized for
performance, and maintained to prevent data loss or corruption. Efficient disk scheduling and
management are crucial for ensuring the smooth and effective operation of a computer system.
Types of Disk Scheduling Algorithms
● First-Come, First-Served (FCFS) − The FCFS algorithm is the simplest disk scheduling
algorithm, in which the requests are processed in the order they arrive. It is a nonpreemptive
algorithm that does not take into account the distance between the current request and the next
request.
● Shortest Seek Time First (SSTF) − The SSTF algorithm processes the request with the shortest
seek time, i.e., the request that requires the least amount of movement by the disk's head. This
algorithm can minimize the head movement, but it may result in starvation of some requests.
● SCAN − The SCAN algorithm processes the requests in a specific direction, either from the
innermost track to the outermost track or vice versa. After reaching the end of the disk, the head
reverses direction and processes the requests in the opposite direction. This algorithm provides a
balance between the number of requests processed and the time each request waits.
● C-SCAN − The C-SCAN algorithm is similar to the SCAN algorithm, but the head moves only in
one direction and processes requests only in that direction. When it reaches the end of the disk, it
immediately returns to the beginning of the disk and starts processing requests again. This
algorithm can eliminate the possibility of starvation.
● LOOK − The LOOK algorithm is similar to the SCAN algorithm, but the head reverses direction
when it reaches the last request in the current direction. This algorithm can reduce the waiting
time for requests that are close to the head's current position.
● C-LOOK − The C-LOOK algorithm is similar to the C-SCAN algorithm, but the head reverses
direction when it reaches the last request in the current direction. This algorithm can reduce the
waiting time for requests that are close to the head's current position and eliminate the possibility
of starvation.
Evaluation Criteria for Disk Scheduling Algorithms
● Throughput − Throughput is the number of input/output operations that can be processed per
unit time. A disk scheduling algorithm with high throughput can process more requests in a
shorter time, resulting in higher system performance.
● Turnaround time − Turnaround time is the time taken to process a request from the time it is
submitted to the time it is completed. A disk scheduling algorithm with a low turnaround time can
provide faster service to the users.
 ● Waiting time − Waiting time is the time that a request spends waiting in the queue before it is
processed. A disk scheduling algorithm with a low waiting time can provide faster service to the
users.
● Response time − Response time is the time taken to provide the first response to a user's request.
A disk scheduling algorithm with a low response time can provide faster service to the users.
● Fairness − Fairness refers to the equal treatment of all requests in the queue. A disk scheduling
algorithm that provides fair treatment to all requests can ensure that no request is starved of
resources.
Selection of Disk Scheduling Algorithm
● Deterministic − In deterministic disk scheduling, the algorithm is selected based on the
characteristics of the workload. For example, if the workload consists of short requests, the SSTF
algorithm may be the best choice.
● Dynamic − In dynamic disk scheduling, the algorithm is selected based on the current state of the
system. For example, if the disk is heavily loaded, the operating system may switch to a more
efficient algorithm to handle the increased workload. Dynamic disk scheduling can adapt to
changes in the workload and improve system performance.
The selection of the disk scheduling algorithm depends on several factors, including the characteristics of
the workload, system performance requirements, and the available resources. The operating system must
evaluate the different disk scheduling algorithms based on the evaluation criteria and select the algorithm
that best meets the system's requirements.
Advantages
● Improved performance − Disk scheduling algorithms ensure that data is accessed in the most
efficient manner possible, which improves the performance of the system.
● Fairness − Disk scheduling algorithms ensure that all requests for data access are treated fairly
and given a chance to be processed.
● Reduced disk fragmentation − Disk scheduling algorithms can help to reduce disk
fragmentation by accessing data in a more organized manner.
Disadvantages
● Overhead − Disk scheduling algorithms can create overhead and delay in processing data access
requests, which can reduce overall system performance.
● Complexity − Some disk scheduling algorithms can be complex and difficult to understand,
which may make it difficult to optimize system performance.
● Risk of starvation − Disk scheduling algorithms can result in starvation of certain requests,
which can lead to inefficiencies and reduced system performance.
Disk Management
Disk management is the process of organizing, optimizing, and maintaining data on a disk within a
computer system. It involves tasks such as disk partitioning, formatting, and file system creation to
ensure efficient use of disk space, prevent data loss, and improve system performance. Proper disk
management is crucial for preventing issues such as disk failure, fragmentation, and data corruption. By
allocating space to files and creating a file system, disk management helps to organize data and improve
the efficiency and speed of accessing it.
Techniques for Disk Management
● File Allocation Table (FAT) − FAT is a file system used by many operating systems, including
Windows and some versions of Linux. It uses a table to keep track of the location of files on the
disk, and it supports long file names and basic file security features.
● New Technology File System (NTFS) − NTFS is a file system used by Windows operating
systems that offers advanced features, including file compression, encryption, and disk quotas. It
also provides better performance and reliability compared to FAT.
● Unix File System (UFS) − UFS is a file system used by Unix and Unix-like operating systems,
including Linux and macOS. It supports features such as file permissions, symbolic links, and
journaling, which provides faster recovery from disk errors.
● ZFS − ZFS is a file system used by some operating systems, including FreeBSD and OpenSolaris.
It provides advanced features such as data compression, snapshotting, and automatic repair of
data errors.
● Disk Quotas − Disk quotas are used to limit the amount of disk space that a user or group can
use. This helps to prevent one user from monopolizing disk space and can improve system
performance and reliability.
Disk Optimization Techniques
● Defragmentation − Defragmentation is the process of rearranging files on the disk to reduce
fragmentation, which can slow down disk access times. Defragmentation can improve disk
performance and extend the life of the disk.
● Compression − Compression is the process of reducing the size of files to save disk space. It can
be used to compress files that are not frequently accessed, such as archives or backups.
Compression can improve disk utilization and reduce storage costs.
● Encryption − Encryption is the process of encoding data to prevent unauthorized access. It can
be used to protect sensitive data, such as financial or personal information. Encryption can
improve data security and prevent data breaches.
Advantages
● Data organization − Disk management helps to organize data on a disk by allocating space to
files and creating a file system. This improves the efficiency and speed of accessing data.
 ● Prevent data loss − Disk management includes features such as disk partitioning, formatting, and
backup. This helps to prevent data loss and recover lost data in the event of disk failure or other
issues.
● Optimized performance − Proper disk management ensures that the disk is optimized for
performance, which improves the speed and efficiency of data access.
Disadvantages
● Complexity − Disk management can be complex and difficult to understand, especially for
novice users. This can result in errors or improper disk configurations that may cause data loss or
corruption.
● Time-consuming − Disk management tasks such as disk partitioning and formatting can be time-
consuming, especially for large disks or complex configurations.
● Risk of data loss − Improper disk management can result in data loss or corruption, which can be
difficult or impossible to recover.
[Link]-SYSTEM INTERFACE
For the majority of users, the file system is the most obvious aspect of any operating system.
This provides users the method for storage and access to data as well as programs of the
operating system where all the users of the computer system can use it.
The file system consists of 2 distinct parts:
● a collection of files, that store related data, and
● a directory structure, which organizes and provides information about all the files in the
system.
In this chapter, you will learn about the different file tribute, concepts of file and its storage
along with operations on files.
File Attributes
A file is named, for the ease of its users and is referred by its name. A name is usually a string of
characters like [Link], along with an extension which designates the file format. Some
systems (like Linux) distinguish between uppercase and lowercase characters in names, whereas
other systems don't. When a file is given a name, it becomes independent of the process, the user
and also the system which created it. Let's suppose, one user might make the file [Link],
and another user might be editing that file by deducing its name. The file's owner may write the
file to a compact disk (CD) or send it via an e-mail or copy it across a network, and it could still
be called [Link] on the destination system.
Fundamental Components of A File
A file's attributes vary from one operating system to another but typically consist of these:
● Name: Name is the symbolic file name and is the only information kept in human
readable form.
● Identifier: This unique tag is a number that identifies the file within the file system; it is
in non-human-readable form of the file.
● Type: This information is needed for systems which support different types of files or its
format.
● Location: This information is a pointer to a device which points to the location of the file
on the device where it is stored.
● Size: The current size of the file (which is in bytes, words, etc.) which possibly the
maximum allowed size gets included in this attribute.
● Protection: Access-control information establishes who can do the reading, writing,
executing, etc.
 ● Date, Time & user identification: This information might be kept for the creation of the
file, its last modification and last used. These data might be useful for in the field of
protection, security, and monitoring its usage.
File operations
A file is an abstract data type. For defining a file properly, we need to consider the operations
that can be performed on files. The operating system can provide system calls to create, write,
read, reposition, delete, and truncate files. There are six basic file operations within an Operating
system. These are:
● Creating a file: There are two steps necessary for creating a file. First, space in the file
system must be found for the file. We discuss how to allocate space for the file. Second,
an entry for the new file must be made in the directory.
● Writing a file: To write to a file, you make a system call specify about both the name of
the file along with the information to be written to the file.
● Reading a file: To read from a file, you use a system call which specifies the name of the
file and where within memory the next block of the file should be placed.
● Repositioning inside a file: The directory is then searched for the suitable entry, and the
'current-file-position' pointer is relocating to a given value. Relocating within a file need
not require any actual I/O. This file operation is also termed as 'file seek.'
● Deleting a file: For deleting a file, you have to search the directory for the specific file.
Deleting that file or directory release all file space so that other files can re-use that
space.
● Truncating a file: The user may wish for erasing the contents of a file but keep the
attributes same. Rather than deleting the file and then recreate it, this utility allows all
attributes to remain unchanged — except the file length — and let the user add or edit the
file content.
4.8. FILE SYSTEM MOUNTING
Just as a file must be opened before it is used, a file system must be mounted before it can be
available to processes on the system. More specifically, the directory structure can be built out of
multiple volumes, which must be mounted to make them available within the file-system name
space. The mount procedure is straightforward. The operating system is given the name of the
device and the mount point—the location within the file structure where the file system is to be
attached. Typically, a mount point is an empty directory.
For instance, on a UNIX system, a file system containing a user's home directories might be
mounted as /home; then, to access the directory structure within that file system, we could
precede the directory names with ftiome, as in /homc/janc. Mounting that file system under
/users would result in the path name /users/jane, which we could use to reach the same directory.
Next, the operating system verifies that the device contains a valid file system. It does so by
asking the device driver to read the device directory and verifying that the directory has the
expected format. Finally, the operating system notes in its directory structure that a file system is
mounted at the specified mount point. This scheme enables the operating system to traverse its
directory structure, switching among file systems as appropriate. To illustrate file mounting,
consider the file system depicted in Figure 10.12, where the triangles represent subtrees of
directories that are of interest. Figure 10.12(a) shows an existing file system, while Figure
10.12(b) shows an unmounted volume residing on /device'/dsk.

At this point, only the files on the existing file system can be accessed. Figure 10.13 shows the
effects of mounting the volume residing on /device/dsk over /users. If the volume is unmounted,
the file system is restored to the situation depicted in Figure 10.12.
Systems impose semantics to clarify functionality. For example, a system may disallow a mount
over a directory that contains files; or it may make the mounted file system available at that
directory and obscure the directory's existing files until the file system is unmounted, terminating
the use of the file system and allowing access to the original files in that directory.
As another example, a system may allow the same file system to be mounted repeatedly, at
different mount points; or it may only allow one mount per file system. Consider the actions of
the Macintosh operating system. Whenever the system encounters a disk for the first time (hard
disks are found at boot time, and floppy disks are seen when they are inserted into the drive), the
Macintosh operating system searches for a file system on the device. If it finds one, it
automatically mounts the file system at the root level, adding a folder icon on the screen labeled
with the name of the file system (as stored in the device directory). The user is then able to click
on the icon and thus display the newly motinted file system. The Microsoft Windows family of
operating systems (95, 98, NT, small 2000, XP) maintains an extended two-level directory
structure, with devices and volumes assigned drive letters.
Volumes have a general graph directory structure associated with the drive letter. The path to a
specific file takes the form of drive-letter;\path\to\file. The more recent versions of Windows
allow a file system to he mounted anywhere in the directory tree, just as UNIX does. Windows
operating systems automatically discover all devices and mount all located file systems at boot
time. In some systems, like UNIX, the mount commands are explicit. A system configuration file
contains a list of devices and mount points for automatic mounting at boot time, but other
mounts may be executed manually.

[Link] SHARING AND PROTECTION

File sharing is the practice of distributing or providing access to digital files between two or
more users or devices. While it is a convenient way to share information and collaborate on
projects, it also comes with risks such as malware and viruses, data breaches, legal
consequences, and identity theft. Protecting files during sharing is essential to ensure
confidentiality, integrity, and availability. Encryption, password protection, secure file transfer
protocols, and regularly updating antivirus and anti-malware software are all important measures
that can be taken to safeguard files. This article will explore the different types of file sharing,
risks associated with file sharing, protection measures, and best practices for secure file sharing.

Definition of file sharing

File sharing refers to the process of sharing or distributing electronic files such as documents,
music, videos, images, and software between two or more users or computers.
Importance of file sharing
File sharing plays a vital role in facilitating collaboration and communication among individuals
and organizations. It allows people to share files quickly and easily across different locations,
reducing the need for physical meetings and enabling remote work. File sharing also helps
individuals and organizations save time and money, as it eliminates the need for physical
transportation of files.
Risks and challenges of file sharing
File sharing can pose several risks and challenges, including the spread of malware and viruses,
data breaches and leaks, legal consequences, and identity theft. Unauthorized access to sensitive
files can also result in loss of intellectual property, financial losses, and reputational damage.
The need for file protection
With the increase in cyber threats and the sensitive nature of the files being shared, it is essential
to implement adequate file protection measures to secure the files from unauthorized access,
theft, and cyberattacks. Effective file protection measures can help prevent data breaches and
other cyber incidents, safeguard intellectual property, and maintain business continuity.
Types of File Sharing
File sharing refers to the practice of distributing or providing access to digital files, such as
documents, images, audio, and video files, between two or more users or devices. There are
several types of file sharing methods available, and each method has its own unique advantages
and disadvantages.
● Peer-to-Peer (P2P) File Sharing − Peer-to-peer file sharing allows users to share files
with each other without the need for a centralized server. Instead, users connect to each
other directly and exchange files through a network of peers. P2P file sharing is
commonly used for sharing large files such as movies, music, and software.
● Cloud-Based File Sharing − Cloud-based file sharing involves the storage of files in a
remote server, which can be accessed from any device with an internet connection. Users
can upload and download files from cloud-based file sharing services such as Google
 Drive, Dropbox, and OneDrive. Cloud-based file sharing allows users to easily share files
with others, collaborate on documents, and access files from anywhere.
● Direct File Transfer − Direct file transfer involves the transfer of files between two
devices through a direct connection such as Bluetooth or Wi-Fi Direct. Direct file transfer
is commonly used for sharing files between mobile devices or laptops.
● Removable Media File Sharing − Removable media file sharing involves the use of
physical storage devices such as USB drives or external hard drives. Users can copy files
onto the device and share them with others by physically passing the device to them.
Each type of file sharing method comes with its own set of risks and challenges. Peer-to-peer file
sharing can expose users to malware and viruses, while cloud-based file sharing can lead to data
breaches if security measures are not implemented properly. Direct file transfer and removable
media file sharing can also lead to data breaches if devices are lost or stolen.
To protect against these risks, users should take precautions such as using encryption, password
protection, secure file transfer protocols, and regularly updating antivirus and antimalware
software. It is also essential to educate users on safe file sharing practices and limit access to files
only to authorized individuals or groups. By taking these steps, users can ensure that their files
remain secure and protected during file sharing.
Risks of File Sharing
File sharing is a convenient and efficient way to share information and collaborate on projects.
However, it comes with several risks and challenges that can compromise the confidentiality,
integrity, and availability of files. In this section, we will explore some of the most significant
risks of file sharing.
● Malware and Viruses − One of the most significant risks of file sharing is the spread of
malware and viruses. Files obtained from untrusted sources, such as peer-to-peer (P2P)
networks, can contain malware that can infect the user's device and compromise the
security of their files. Malware and viruses can cause damage to the user's device, steal
personal information, or even use their device for illegal activities without their
knowledge.
● Data Breaches and Leaks − Another significant risk of file sharing is the possibility of
data breaches and leaks. Cloud-based file sharing services and P2P networks are
particularly vulnerable to data breaches if security measures are not implemented
properly. Data breaches can result in the loss of sensitive information, such as personal
data or intellectual property, which can have severe consequences for both individuals
and organizations.
● Legal Consequences − File sharing copyrighted material without permission can lead to
legal consequences. Sharing copyrighted music, movies, or software can result in
copyright infringement lawsuits and hefty fines.
 ● Identity Theft − File sharing can also expose users to identity theft. Personal
information, such as login credentials or social security numbers, can be inadvertently
shared through file sharing if security measures are not implemented properly.
Cybercriminals can use this information to commit identity theft, which can have severe
consequences for the victim.
To protect against these risks, users should take precautions such as using trusted sources for file
sharing, limiting access to files, educating users on safe file sharing practices, and regularly
updating antivirus and anti-malware software. By taking these steps, users can reduce the risk of
malware and viruses, data breaches and leaks, legal consequences, and identity theft during file
sharing.
File Sharing Protection Measures
● Encryption − Encryption is the process of converting data into a coded language that can
only be accessed by authorized users with a decryption key. This can help protect files
from unauthorized access and ensure that data remains confidential even if it is
intercepted during file sharing.
● Password protection − Password protection involves securing files with a password that
must be entered before the file can be accessed. This can help prevent unauthorized
access to files and ensure that only authorized users can view or modify the files.
● Secure file transfer protocols − Secure file transfer protocols, such as SFTP (Secure
File Transfer Protocol) and HTTPS (Hypertext Transfer Protocol Secure), provide a
secure way to transfer files over the internet. These protocols use encryption and other
security measures to protect files from interception and unauthorized access during
transfer.
● Firewall protection − Firewall protection involves using a firewall to monitor and
control network traffic to prevent unauthorized access to the user's device or network.
Firewalls can also be configured to block specific file sharing protocols or limit access to
certain users or devices, providing an additional layer of protection for shared files.
Best Practices for Secure File Sharing
● Use trusted sources for file sharing − To reduce the risk of downloading malware or
viruses, it is essential to use trusted sources for file sharing. Users should only download
files from reputable sources and avoid downloading files from unknown or suspicious
websites.
● Limit access to files − To minimize the risk of data breaches or leaks, users should limit
access to files only to authorized individuals or groups. This can be done by using
password protection, encryption, and other access control measures.
● Educate users on safe file sharing practices − Educating users on safe file sharing
practices can help reduce the risk of security incidents. Users should be trained on how to
 identify and avoid phishing scams, how to recognize suspicious files or emails, and how
to securely share files.
● Regularly update antivirus and anti-malware software − To ensure maximum
protection against malware and viruses, it is essential to regularly update antivirus and
anti-malware software. This will help to identify and remove any potential threats to the
user's device or network.
4.12. DIRECTORY IMPLEMENTATION
Directory implementation in the operating system can be done using Singly Linked List and
Hash table. The efficiency, reliability, and performance of a file system are greatly affected by
the selection of directory-allocation and directory-management algorithms. There are numerous
ways in which the directories can be implemented. But we need to choose an appropriate
directory implementation algorithm that enhances the performance of the system.
Directory Implementation using Singly Linked List
The implementation of directories using a singly linked list is easy to program but is time-
consuming to execute. Here we implement a directory by using a linear list of filenames with
pointers to the data blocks.

Directory Implementation Using Singly Linked List

● To create a new file the entire list has to be checked such that the new directory does not
exist previously.
● The new directory then can be added to the end of the list or at the beginning of the list.
● In order to delete a file, we first search the directory with the name of the file to be
deleted. After searching we can delete that file by releasing the space allocated to it.
● To reuse the directory entry we can mark that entry as unused or we can append it to the
list of free directories.
● To delete a file linked list is the best choice as it takes less time.
Disadvantage
The main disadvantage of using a linked list is that when the user needs to find a file the user has
to do a linear search. In today’s world directory information is used quite frequently and linked
list implementation results in slow access to a file. So the operating system maintains a cache to
store the most recently used directory information.
Directory Implementation using Hash Table
An alternative data structure that can be used for directory implementation is a hash table. It
overcomes the major drawbacks of directory implementation using a linked list. In this method,
we use a hash table along with the linked list. Here the linked list stores the directory entries, but
a hash data structure is used in combination with the linked list.
In the hash table for each pair in the directory key-value pair is generated. The hash function on
the file name determines the key and this key points to the corresponding file stored in the
directory. This method efficiently decreases the directory search time as the entire list will not be
searched on every operation. Using the keys the hash table entries are checked and when the file
is found it is fetched.

Directory Implementation Using Hash Table

Disadvantage:
The major drawback of using the hash table is that generally, it has a fixed size and its
dependency on size. But this method is usually faster than linear search through an entire
directory using a linked list.

[Link] ALLOCATION METHODS

The allocation methods define how the files are stored in the disk blocks. There are three main
disk space or file allocation methods.
● Contiguous Allocation
● Linked Allocation
● Indexed Allocation
The main idea behind these methods is to provide:
● Efficient disk space utilization.
● Fast access to the file blocks.
All the three methods have their own advantages and disadvantages as discussed below:
1. Contiguous Allocation
In this scheme, each file occupies a contiguous set of blocks on the disk. For example, if a file
requires n blocks and is given a block b as the starting location, then the blocks assigned to the
file will be: b, b+1, b+2,……b+n-1. This means that given the starting block address and the
length of the file (in terms of blocks required), we can determine the blocks occupied by the file.
The directory entry for a file with contiguous allocation contains
● Address of starting block
● Length of the allocated portion.
The file ‘mail’ in the following figure starts from the block 19 with length = 6 blocks. Therefore,
it occupies 19, 20, 21, 22, 23, 24 blocks.
Advantages:
● Both the Sequential and Direct Accesses are supported by this. For direct access, the
address of the kth block of the file which starts at block b can easily be obtained as (b+k).
● This is extremely fast since the number of seeks are minimal because of contiguous
allocation of file blocks.
Disadvantages:
● This method suffers from both internal and external fragmentation. This makes it
inefficient in terms of memory utilization.
● Increasing file size is difficult because it depends on the availability of contiguous
memory at a particular instance.
2. Linked List Allocation
In this scheme, each file is a linked list of disk blocks which need not be contiguous. The disk
blocks can be scattered anywhere on the disk.
The directory entry contains a pointer to the starting and the ending file block. Each block
contains a pointer to the next block occupied by the file.
The file ‘jeep’ in following image shows how the blocks are randomly distributed. The last block
(25) contains -1 indicating a null pointer and does not point to any other block.

Advantages:
● This is very flexible in terms of file size. File size can be increased easily since the
system does not have to look for a contiguous chunk of memory.
● This method does not suffer from external fragmentation. This makes it relatively better
in terms of memory utilization.
Disadvantages:
● Because the file blocks are distributed randomly on the disk, a large number of seeks are
needed to access every block individually. This makes linked allocation slower.
● It does not support random or direct access. We can not directly access the blocks of a
file. A block k of a file can be accessed by traversing k blocks sequentially (sequential
access ) from the starting block of the file via block pointers.
● Pointers required in the linked allocation incur some extra overhead.
3. Indexed Allocation
In this scheme, a special block known as the Index block contains the pointers to all the blocks
occupied by a file. Each file has its own index block. The ith entry in the index block contains
the disk address of the ith file block. The directory entry contains the address of the index block
as shown in the image:
Advantages:
● This supports direct access to the blocks occupied by the file and therefore provides fast
access to the file blocks.
● It overcomes the problem of external fragmentation.
Disadvantages:
● The pointer overhead for indexed allocation is greater than linked allocation.
● For very small files, say files that expand only 2-3 blocks, the indexed allocation would
keep one entire block (index block) for the pointers which is inefficient in terms of
memory utilization. However, in linked allocation we lose the space of only 1 pointer per
block.
For files that are very large, single index block may not be able to hold all the pointers.
Following mechanisms can be used to resolve this:
1. Linked scheme: This scheme links two or more index blocks together for holding the
pointers. Every index block would then contain a pointer or the address to the next index
block.
2. Multilevel index: In this policy, a first level index block is used to point to the second
level index blocks which inturn points to the disk blocks occupied by the file. This can be
extended to 3 or more levels depending on the maximum file size.
3. Combined Scheme: In this scheme, a special block called the Inode (information
Node) contains all the information about the file such as the name, size, authority, etc and
the remaining space of Inode is used to store the Disk Block addresses which contain the
actual file as shown in the image below. The first few of these pointers in Inode point to
the direct blocks i.e the pointers contain the addresses of the disk blocks that contain
data of the file. The next few pointers point to indirect blocks. Indirect blocks may be
single indirect, double indirect or triple indirect. Single Indirect block is the disk block
that does not contain the file data but the disk address of the blocks that contain the file
data. Similarly, double indirect blocks do not contain the file data but the disk address
of the blocks that contain the address of the blocks containing the file data.
 UNIT V

VIRTUAL MACHINES AND MOBILE OS

Virtual Machines – History, Benefits and Features, Building Blocks, Types of Virtual
Machines and their Implementations, Virtualization and Operating-System Components;
Mobile OS – iOS and Android.

1. Virtual Machines

Virtual Machine abstracts the hardware of our personal computer such as CPU, disk
drives, memory, NIC (Network Interface Card) etc, into many different execution
environments as per our requirements, hence giving us a feel that each execution environment
is a single computer. For example, Virtual Box.

When we run different processes on an operating system, it creates an illusion that each
process is running on a different processor having its own virtual memory, with the help of
CPU scheduling and virtual-memory techniques. There are additional features of a process that
cannot be provided by the hardware alone like system calls and a file system. The virtual
machine approach does not provide these additional functionalities but it only provides an
interface that is same as basic hardware. Each process is provided with a virtual copy of the
underlying computer system.

virtual machine for several reasons, all of which are fundamentally related to the ability
to share the same basic hardware yet can also support different execution environments, i.e.,
different operating systems simultaneously.
The main drawback with the virtual-machine approach involves disk systems. Let us
suppose that the physical machine has only three disk drives but wants to support seven virtual
machines. Obviously, it cannot allocate a disk drive to each virtual machine, because virtual-
machine software itself will need substantial disk space to provide virtual memory and
spooling. The solution is to provide virtual disks.
Users are thus given their own virtual machines. After which they can run any of the
operating systems or software packages that are available on the underlying machine. The
virtual-machine software is concerned with multi-programming multiple virtual machines onto
a physical machine, but it does not need to consider any user-support software. This
arrangement can provide a useful way to divide the problem of designing a multi-user
interactive system, into two smaller pieces.

Advantages:
1. There are no protection problems because each virtual machine is completely isolated from
all other virtual machines.
2. Virtual machine can provide an instruction set architecture that differs from real computers.
3. Easy maintenance, availability and convenient recovery.
Disadvantages:
1. When multiple virtual machines are simultaneously running on a host computer, one virtual
machine can be affected by other running virtual machines, depending on the workload.
2. Virtual machines are not as efficient as a real one when accessing the hardware.

TYPES OF VIRTUAL MACHINES:

You can classify virtual machines into two types:

1. System Virtual Machine: These types of virtual machines gives us complete system
platform and gives the execution of the complete virtual operating system. Just like virtual
box, system virtual machine is providing an environment for an OS to be installed
completely. We can see in below image that our hardware of Real Machine is being
distributed between two simulated operating systems by Virtual machine monitor. And then
some programs, processes are going on in that distributed hardware of simulated
machines separately
.

3. Process Virtual Machine: While process virtual machines, unlike system virtual machine,
does not provide us with the facility to install the virtual operating system completely.
Rather it creates virtual environment of that OS while using some app or program and this
environment will be destroyed as soon as we exit from that app. Like in below image, there
are some apps running on main OS as well some virtual machines are created to run other
apps. This shows that as those programs required different OS, process virtual machine
provided them with that for the time being those programs are running. Example – Wine
software in Linux helps to run Windows applications.
4.
2. HISTORY OF VIRTUAL MACHINES
The concept of virtual machines (VMs) can be traced back to the 1960s when IBM
introduced the concept of time-sharing on its mainframe computers. Time-sharing allowed multiple
users to simultaneously access a single computer, but it required each user tohave their own virtual
machine, which would run its own operating system and applications.

The first true virtual machine, however, was developed in the early 1970s by a team of
researchers at IBM led by Gerald Popek and Robert Goldberg. Their system, called CP-67/CMS,
allowed multiple instances of the IBM System/360 operating system to run simultaneously on a
single mainframe computer.

In the 1980s and 1990s, virtualization technology continued to evolve, with companies
such as DEC and Sun Microsystems developing their own virtual machine software. However, it
wasn't until the early 2000s that virtualization became mainstream, thanks in large part to the
development of the x86 architecture and the introduction of hardware-assisted virtualization
technologies such as Intel VT and AMD-V.

Today, virtual machines are used in a wide variety of applications,from server consolidation
and cloud computing to software development and testing. In recent years, containerization has
emerged as a popular alternative to traditional virtualization, butvirtual machines remain a critical
component of the modern computing landscape.

3. BENEFITS OF USING A VIRTUAL MACHINE

A virtual machine is essentially a computer within a computer. VMs have several advantages:

• Lower hardware costs. Many organizations don’t fully utilize their hardware
resources. Instead of investing in another server, organizations can spin up virtual
servers instead.
• Quicker Desktop Provisioning and Deployment. Deploying a new physical server
often takes numerous time-consuming steps. However, with virtualized systems,
organizations can deploy new virtual servers quickly using secure pre-configured server
templates.
• Smaller Footprint. Utilizing virtualization reduces the office space needed to maintain
and extend IT capabilities while also freeing up desk space to support more employees.
• Enhanced Data Security. Virtualization streamlines disaster recovery by replicating
your servers in the cloud. Since VMs are independent of the underlying hardware,
organizations don’t need the same physical servers offsite to facilitate a secondary
recovery site. In the event of a disaster, employees can be back online quickly with a
cost-effective backup and disaster recovery solution.
• Portability. It’s possible to seamlessly move VMs across virtual environments and
even from one physical server to another, with minimal input on the part of IT teams.
VMs are isolated from one another and have their own virtual hardware, making them
 hardware-independent. Moving physical servers to another location is a more resource-
intensive task.
• Improved IT Efficiency. Many IT departments spend at least half of their time
managing routine administrative tasks, however with virtualization it’s possible to
partition one physical server into several virtual machines—administrators can deploy
and manage multiple operating systems at once from a single physical server.

4. CHALLENGES IN USING A VIRTUAL MACHINE

VMs have a huge number of advantages, especially when people need to run more than one
operating system in a single physical device. However, there are several challenges associated with using
VMs:

• When simultaneous VMs run on a host computer, each can introduce an unstable performance
depending on the workload of the system.

• The efficiency of VMs falls short compared to physical machines.

• Licensing models of virtualization solutions can be tricky. They can result in huge upfront
investment costs due to additional hardware requirements.

• Due to the increasingly high number of breaches on VM and cloud deployments, security is an
added concern.

• For every virtualization solution, the infrastructure setup is complex. Small businesses have to
hire experts to deploy these solutions successfully.

• VMs pose data security threats when multiple users try to access the same or different VMs on
the same physical host.

FEATURES OF VIRTUAL MACHINES

A virtual machine (VM) is an emulation of a computer system that enables multiple

operating systems to run simultaneously on a single physical machine. The following are
some of the features of virtual machines:

• Isolation: Each VM is completely isolated from other VMs and the host operating
system, providing a secure environment for running applications.

• Hardware independence: Virtual machines can run on any hardware platform, as long as
the host system provides the necessary resources.

• Software compatibility: Virtual machines can run different operating systems and
software, making them useful for testing and developmentpurposes.

• Snapshots: Virtual machines can take snapshots of the current state of thesystem,
allowing for easy rollback in case of software or configuration issues.
• Resource allocation: Resources such as CPU, memory, and storage canbe allocated
to each VM individually, allowing for efficient use of the underlying hardware.

• Mobility: Virtual machines can be easily moved between physical hosts, making them
useful for disaster recovery and workload balancing.

• Cost savings: By running multiple virtual machines on a single physical host,

organizations can save on hardware and maintenance costs.

• Scalability: Virtual machines can be easily created and removed, allowing for flexible
scaling of IT resources.

Overall, virtual machines provide a highly flexible and efficient way to run multiple
operating systems and applications on a single physical machine.
BUILDING BLOCKS OF VIRTUAL MACHINES

Virtual machines (VMs) are essentially software that emulates a computer system within
another computer system. The building blocks of virtual machines include:

• Hypervisor: The hypervisor is the software layer that creates and manages
virtual machines. It is also known as a virtual machine monitor (VMM). The
hypervisor manages the physical resources of the host computer, such as CPU,
memory, and disk space, and allocates them to virtual machines.

• Virtual CPU: A virtual CPU is a software emulation of a physical CPU that is

assigned to a virtual machine. The virtual CPU is responsible for executing
theinstructions of the guest operating system running within the virtual machine.

• Virtual Memory: The virtual memory is a software abstraction of the physical

memory of the host computer that is assigned to a virtual machine. The guest
operating system running within the virtual machine thinks that it has access to a
certain amount of physical memory, but in reality, it is accessing virtual memory

• Virtual Disk: A virtual disk is a file that is used to store the virtual machine's operating
system, applications, and data. The virtual disk is mapped to physical storage on the
host computer.

• Virtual Network Adapter: A virtual network adapter is a software component that

allows a virtual machine to communicate with othercomputers and devices on a
network. The virtual network adapter isconnected to a virtual switch that is managed
by the hypervisor.
Guest Operating System: The guest operating system is the operatingsystem that is installed
within the virtual machine. The guest operating system thinks that it is running on a physical
computer, but in reality, it is running within a virtual machine
3. VIRTUALIZATION AND OPERATING-SYSTEM COMPONENTS:

• Virtualization is the process of creating a virtual version of a resource, such as an

operating system, a server, a storage device, or a network. This virtualversion can be used to
run multiple applications or operating systems simultaneously on a single physical
machine, or to partition a single physical machine into multiple virtual machines, each with
its own operating system and applications.

• Virtualization technology allows for greater flexibility, scalability, and efficiency in

managing computing resources. It enables organizations to consolidate multiple physical
servers into a single machine, reducing hardware costs and power consumption. It also
allows for better utilizationof computing resources, as virtual machines can be dynamically
allocated and de-allocated based on demand.
 There are several types of virtualization, including:

• Server virtualization: This involves partitioning a physical server into multiple

virtual servers, each with its own operating system and applications.

• Desktop virtualization: This involves running multiple desktop environments on a

single physical machine, allowing multiple users to access the same hardware
resources.

• Application virtualization: This involves running applications in a virtual

environment, isolated from the underlying operating system and otherapplications.

• Storage virtualization: This involves abstracting physical storage devices into

virtual storage pools, allowing for more efficient allocation and management of
storage resources.

Overall, virtualization technology has revolutionized the way computing resources are
managed and utilized, providing organizations with greaterflexibility, scalability, and
efficiency.

COMPONENTS OF OS

An operating system is a large and complex system that can only be created by
partitioning into small parts. These pieces should be a well-defined part of the system,
carefully defining inputs, outputs, and functions.

Although Windows, Mac, UNIX, Linux, and other OS do not have the same
structure, most operating systems share similar OS system components, such as
file, memory, process, I/O device management.
The components of an operating system play a key role to make a variety of computer
system parts work together. There are the following components of an operating system,
such as:

• Process Management

• File Management
• Network Management

• Main Memory Management

• Secondary Storage Management

• I/O Device Management

• Security Management

• Command Interpreter System

Operating system components help you get the correct computing bydetecting CPU
and memory hardware errors.
PROCESSMANAGEMENT

• The process management component is a procedure for managingmany processes running

simultaneously on the operating system. Every running software application program has
one or more processes associated with them.

• For example, when you use a search engine like Chrome, there is aprocess running for that
browser program.

• Process management keeps processes running efficiently. It also usesmemory allocated to

them and shutting them down when needed.

• The execution of a process must be sequential so, at least oneinstruction should be

executed on behalf of the process.

•
FUNCTIONS OF PROCESS MANAGEMENT
• Here are the following functions of process management in theoperating system, such
as:

• Process creation and deletion.

• Suspension and resumption.

• Synchronization process

• Communication process

NOTE: OS facilitates an exchange of information between processesexecuting on the same

or different systems.

FILEMANAGEMENT

• A file is a set of related information defined by its creator. It commonly represents

programs (both source and object forms) anddata. Data files can be alphabetic, numeric, or

alphanumeric.