OS Notes

Topic#01
Semaphores in Operating System
Semaphores are integer variables that are used to solve the critical section problem by
using two atomic operations, wait and signal that are used for process synchronization.
The definitions of wait and signal are as follows −

 Wait
The wait operation decrements the value of its argument S, if it is positive. If S is
negative or zero, then no operation is performed.

wait(S)

while (S<=0);

S--;

 Signal
The signal operation increments the value of its argument S.

signal(S)

S++;

Types of Semaphores
There are two main types of semaphores i.e. counting semaphores and binary
semaphores. Details about these are given as follows −
  Counting Semaphores
These are integer value semaphores and have an unrestricted value domain.
These semaphores are used to coordinate the resource access, where the
semaphore count is the number of available resources. If the resources are
added, semaphore count automatically incremented and if the resources are
removed, the count is decremented.

 Binary Semaphores
The binary semaphores are like counting semaphores but their value is restricted
to 0 and 1. The wait operation only works when the semaphore is 1 and the
signal operation succeeds when semaphore is 0. It is sometimes easier to
implement binary semaphores than counting semaphores.

Advantages of Semaphores
Some of the advantages of semaphores are as follows −

 Semaphores allow only one process into the critical section. They follow the
mutual exclusion principle strictly and are much more efficient than some other
methods of synchronization.
 There is no resource wastage because of busy waiting in semaphores as
processor time is not wasted unnecessarily to check if a condition is fulfilled to
allow a process to access the critical section.
 Semaphores are implemented in the machine independent code of the
microkernel. So they are machine independent.
Disadvantages of Semaphores
Some of the disadvantages of semaphores are as follows −

 Semaphores are complicated so the wait and signal operations must be

implemented in the correct order to prevent deadlocks.
 Semaphores are impractical for last scale use as their use leads to loss of
modularity. This happens because the wait and signal operations prevent the
creation of a structured layout for the system.
 Semaphores may lead to a priority inversion where low priority processes may
access the critical section first and high priority processes later.
Operating System Operations
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.
The major operations of the operating system are process management, memory
management, device management and file management. These are given in detail as
follows:

Process Management
The operating system is responsible for managing the processes i.e assigning the
processor to a process at a time. This is known as process scheduling. The different
algorithms used for process scheduling are FCFS (first come first served), SJF (shortest
job first), priority scheduling, round robin scheduling etc.
There are many scheduling queues that are used to handle processes in process
management. When the processes enter the system, they are put into the job queue.
The processes that are ready to execute in the main memory are kept in the ready
queue. The processes that are waiting for the I/O device are kept in the device queue.

Memory Management
Memory management plays an important part in operating system. It deals with memory
and the moving of processes from disk to primary memory for execution and back
again.
The activities performed by the operating system for memory management are −

 The operating system assigns memory to the processes as required. This can be
done using best fit, first fit and worst fit algorithms.
 All the memory is tracked by the operating system i.e. it nodes what memory
parts are in use by the processes and which are empty.
 The operating system deallocated memory from processes as required. This may
happen when a process has been terminated or if it no longer needs the
memory.
Device Management
There are many I/O devices handled by the operating system such as mouse,
keyboard, disk drive etc. There are different device drivers that can be connected to the
operating system to handle a specific device. The device controller is an interface
between the device and the device driver. The user applications can access all the I/O
devices using the device drivers, which are device specific codes.

File Management
Files are used to provide a uniform view of data storage by the operating system. All the
files are mapped onto physical devices that are usually non volatile so data is safe in
the case of system failure.
The files can be accessed by the system in two ways i.e. sequential access and direct
access −

 Sequential Access
The information in a file is processed in order using sequential access. The files
records are accessed on after another. Most of the file systems such as editors,
compilers etc. use sequential access.

 Direct Access
 In direct access or relative access, the files can be accessed in random for read
and write operations. The direct access model is based on the disk model of a
file, since it allows random accesses.

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.

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.

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 −

As seen from the image, each upper layer is built on the bottom layer. All the layers hide
some structures, operations etc from their upper layers.
One problem with the layered structure is that each layer needs to be carefully defined.
This is necessary because the upper layers can only use the functionalities of the layers
below them.

What are system calls in Operating

System?
The interface between a process and an operating system is provided by system calls.
In general, system calls are available as assembly language instructions. They are also
included in the manuals used by the assembly level programmers. System calls are
usually made when a process in user mode requires access to a resource. Then it
requests the kernel to provide the resource via a system call.
A figure representing the execution of the system call is given as follows −

As can be seen from this diagram, the processes execute normally in the user mode
until a system call interrupts this. Then the system call is executed on a priority basis in
the kernel mode. After the execution of the system call, the control returns to the user
mode and execution of user processes can be resumed.
In general, system calls are required in the following situations −

 If a file system requires the creation or deletion of files. Reading and writing from
files also require a system call.
 Creation and management of new processes.
 Network connections also require system calls. This includes sending and
receiving packets.
 Access to a hardware devices such as a printer, scanner etc. requires a system
call.
Types of System Calls
There are mainly five types of system calls. These are explained in detail as follows –
Process Control
These system calls deal with processes such as process creation, process termination
etc.
File Management
These system calls are responsible for file manipulation such as creating a file, reading
a file, writing into a file etc.
Device Management
These system calls are responsible for device manipulation such as reading from device
buffers, writing into device buffers etc.
Information Maintenance
These system calls handle information and its transfer between the operating system
and the user program.
Communication
These system calls are useful for interprocess communication. They also deal with
creating and deleting a communication connection.
Some of the examples of all the above types of system calls in Windows and Unix are
given as follows −
Types of System Calls Windows Linux
fork()
CreateProcess()
exit()
Process Control ExitProcess()
wait()
WaitForSingleObject()
CreateFile() open()
ReadFile() read()
File Management
WriteFile() write()
CloseHandle() close()
SetConsoleMode() ioctl()
Device Management ReadConsole() read()
WriteConsole() write()
GetCurrentProcessID() getpid()
Information Maintenance SetTimer() alarm()
Sleep() sleep()
CreatePipe() pipe()
Communication CreateFileMapping() shmget()
MapViewOfFile() mmap()
There are many different system calls as shown above. Details of some of those system
calls are as follows −

open()
The open() system call is used to provide access to a file in a file system. This system
call allocates resources to the file and provides a handle that the process uses to refer
to the file. A file can be opened by multiple processes at the same time or be restricted
to one process. It all depends on the file organisation and file system.

read()
The read() system call is used to access data from a file that is stored in the file system.
The file to read can be identified by its file descriptor and it should be opened using
open() before it can be read. In general, the read() system calls takes three arguments
i.e. the file descriptor, buffer which stores read data and number of bytes to be read
from the file.

write()
The write() system calls writes the data from a user buffer into a device such as a file.
This system call is one of the ways to output data from a program. In general, the write
system calls takes three arguments i.e. file descriptor, pointer to the buffer where data is
stored and number of bytes to write from the buffer.

close()
The close() system call is used to terminate access to a file system. Using this system
call means that the file is no longer required by the program and so the buffers are
flushed, the file metadata is updated and the file resources are de-allocated.

wait()
In some systems, a process may wait for another process to complete its execution.
This happens when a parent process creates a child process and the execution of the
parent process is suspended until the child process executes. The suspending of the
parent process occurs with a wait() system call. When the child process completes
execution, the control is returned back to the parent process.
This system call runs an executable file in the context of an already running process. It
replaces the previous executable file. This is known as an overlay. The original process
identifier remains since a new process is not created but data, heap, stack etc. of the
process are replaced by the new process.
fork()
Processes use the fork() system call to create processes that are a copy of themselves.
This is one of the major methods of process creation in operating systems. When a
parent process creates a child process and the execution of the parent process is
suspended until the child process executes. When the child process completes
execution, the control is returned back to the parent process.
exit()
The exit() system call is used by a program to terminate its execution. In a
multithreaded environment, this means that the thread execution is complete. The
operating system reclaims resources that were used by the process after the exit()
system call.
kill()
The kill() system call is used by the operating system to send a termination signal to a
process that urges the process to exit. However, kill() system call does not necessarily
mean killing the process and can have various meanings.

Operating System - Process Scheduling

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

Process Scheduling Queues

The OS maintains all 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.

Two-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 short
term scheduler other two 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 minimal It is also minimal in time It is a part of Time sharing

in time sharing system sharing system systems.

5 It selects processes from It selects those processes It can re-introduce the process
pool and loads them into which are ready to into memory and execution
memory for execution execute can be continued.
Context Switch
A context switch 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

What is Interprocess Communication?

Interprocess communication is the mechanism provided by the operating system that
allows processes to communicate with each other. This communication could involve a
process letting another process know that some event has occurred or the transferring
of data from one process to another.
A diagram that illustrates interprocess communication is as follows −

Synchronization in Interprocess Communication

Synchronization is a necessary part of interprocess communication. It is either provided
by the interprocess control mechanism or handled by the communicating processes.
Some of the methods to provide synchronization are as follows −

 Semaphore
A semaphore is a variable that controls the access to a common resource by
multiple processes. The two types of semaphores are binary semaphores and
counting semaphores.
  Mutual Exclusion
Mutual exclusion requires that only one process thread can enter the critical
section at a time. This is useful for synchronization and also prevents race
conditions.

 Barrier
A barrier does not allow individual processes to proceed until all the processes
reach it. Many parallel languages and collective routines impose barriers.

 Spinlock
This is a type of lock. The processes trying to acquire this lock wait in a loop
while checking if the lock is available or not. This is known as busy waiting
because the process is not doing any useful operation even though it is active.

Approaches to Interprocess Communication

The different approaches to implement interprocess communication are given as follows
−

 Pipe
A pipe is a data channel that is unidirectional. Two pipes can be used to create a
two-way data channel between two processes. This uses standard input and
output methods. Pipes are used in all POSIX systems as well as Windows
operating systems.

 Socket
The socket is the endpoint for sending or receiving data in a network. This is true
for data sent between processes on the same computer or data sent between
different computers on the same network. Most of the operating systems use
sockets for interprocess communication.

 File
A file is a data record that may be stored on a disk or acquired on demand by a
file server. Multiple processes can access a file as required. All operating
systems use files for data storage.

 Signal
Signals are useful in interprocess communication in a limited way. They are
system messages that are sent from one process to another. Normally, signals
are not used to transfer data but are used for remote commands between
processes.

 Shared Memory
 Shared memory is the memory that can be simultaneously accessed by multiple
processes. This is done so that the processes can communicate with each other.
All POSIX systems, as well as Windows operating systems use shared memory.

 Message Queue
Multiple processes can read and write data to the message queue without being
connected to each other. Messages are stored in the queue until their recipient
retrieves them. Message queues are quite useful for interprocess communication
and are used by most operating systems.
A diagram that demonstrates message queue and shared memory methods of
interprocess communication is as follows −

Different Models of Interprocess

Communication
Interprocess communication is the mechanism provided by the operating system that
allows processes to communicate with each other. This communication could involve a
process letting another process know that some event has occurred or transferring of
data from one process to another.
A diagram that illustrates interprocess communication is as follows −

The models of interprocess communication are as follows −

Shared Memory Model

Shared memory is the memory that can be simultaneously accessed by multiple
processes. This is done so that the processes can communicate with each other. All
POSIX systems, as well as Windows operating systems use shared memory.
Advantage of Shared Memory Model
Memory communication is faster on the shared memory model as compared to the
message passing model on the same machine.
Disadvantages of Shared Memory Model
Some of the disadvantages of shared memory model are as follows −

 All the processes that use the shared memory model need to make sure that they are
not writing to the same memory location.
 Shared memory model may create problems such as synchronization and memory
protection that need to be addressed.
Message Passing Model
Multiple processes can read and write data to the message queue without being
connected to each other. Messages are stored on the queue until their recipient
retrieves them. Message queues are quite useful for interprocess communication and
are used by most operating systems.
Advantage of Messaging Passing Model
The message passing model is much easier to implement than the shared memory
model.
Disadvantage of Messaging Passing Model
The message passing model has slower communication than the shared memory model
because the connection setup takes time.
A diagram that demonstrates the shared memory model and message passing model is
given as follows −

Operating System - Multi-Threading

What is Thread?
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 system. Thread

switching
does not
need to
interact
with
operating
system.

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

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

5 Multiple processes without using threads use more resources. Multiple

threaded
processes
use fewer
resources.

6 In multiple processes each process operates independently of the others. One

thread can
read, write
 or 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 individuals
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 provide 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 Model

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 Kernel-level threads are slower to
manage. create and manage.

2 Implementation is by a thread library at the user Operating system supports creation of

level. 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 Kernel routines themselves can be

advantage of multiprocessing. multithreaded.
Major issues with Multi-threaded
Programs
What are Thread Libraries?
Thread libraries provide programmers with API for creation and management of
threads.
Thread libraries may be implemented either in user space or in kernel space. The user
space involves API functions implemented solely within the user space, with no kernel
support. The kernel space involves system calls, and requires a kernel with thread
library support.

Three types of Thread

1. POSIX Pitheads, may be provided as either a user or kernel library, as an extension to

the POSIX standard.

2. Win32 threads, are provided as a kernel-level library on Windows systems.

3. Java threads: Since Java generally runs on a Java Virtual Machine, the implementation

of threads is based upon whatever OS and hardware the JVM is running on, i.e. either

Pitheads or Win32 threads depending on the system.

Benefits of Multithreading
1. Responsiveness
2. Resource sharing, hence allowing better utilization of resources.

3. Economy. Creating and managing threads becomes easier.

4. Scalability. One thread runs on one CPU. In Multithreaded processes, threads can be

distributed over a series of processors to scale.

 5. Context Switching is smooth. Context switching refers to the procedure followed by CPU

to change from one task to another.

Multithreading Issues
Below we have mentioned a few issues related to multithreading. Well, it's an old
saying, All good things, come at a price.
Thread Cancellation
Thread cancellation means terminating a thread before it has finished working. There
can be two approaches for this, one is Asynchronous cancellation, which terminates
the target thread immediately. The other is Deferred cancellation allows the target
thread to periodically check if it should be cancelled.
Signal Handling
Signals are used in UNIX systems to notify a process that a particular event has
occurred. Now in when a Multithreaded process receives a signal, to which thread it
must be delivered? It can be delivered to all, or a single thread.
fork() System Call
fork() is a system call executed in the kernel through which a process creates a copy of
itself. Now the problem in Multithreaded process is, if one thread forks, will the entire
process be copied or not?
Security Issues
Yes, there can be security issues because of extensive sharing of resources between
multiple threads.
There are many other issues that you might face in a multithreaded process, but there
are appropriate solutions available for them. Pointing out some issues here was just to
study both sides of the coin.
Thread Scheduling

Scheduling of threads involves two boundary scheduling,

 Scheduling of user level threads (ULT) to kernel level threads (KLT)
via leightweight process (LWP) by the application developer.
 Scheduling of kernel level threads by the system scheduler to
perform different unique os functions.
Leightweight Process (LWP) :
Light-weight process are threads in the user space that acts as an
interface for the ULT to access the physical CPU resources. Thread
library schedules which thread of a process to run on which LWP and
how long. The number of LWP created by the thread library depends on
the type of application. In the case of an I/O bound application, the
number of LWP depends on the number of user-level threads. This is
because when an LWP is blocked on an I/O operation, then to invoke
the other ULT the thread library needs to create and schedule another
LWP. Thus, in an I/O bound application, the number of LWP is equal to
the number of the ULT. In the case of a CPU bound application, it
depends only on the application. Each LWP is attached to a separate
kernel-level thread.
Attention reader! Don’t stop learning now
In real-time, the first boundary of thread scheduling is beyond
specifying the scheduling policy and the priority. It requires two
controls to be specified for the User level threads: Contention scope,
and Allocation domain. These are explained as following below.
1. Contention Scope :
The word contention here refers to the competition or fight among the
User level threads to access the kernel resources. Thus, this control
defines the extent to which contention takes place. It is defined by the
application developer using the thread library. Depending upon the
extent of contention it is classified as Process Contention
Scope and System Contention Scope.
1. Process Contention Scope (PCS) –
The contention takes place among threads within a same
process. The thread library schedules the high-prioritized PCS
thread to access the resources via available LWPs (priority as
specified by the application developer during thread creation).
2. System Contention Scope (SCS) –
The contention takes place among all threads in the system. In
this case, every SCS thread is associated to each LWP by the thread
library and are scheduled by the system scheduler to access the
kernel resources.
In LINUX and UNIX operating systems, the POSIX Pthread library
provides a function Pthread_attr_setscope to define the type of
contention scope for a thread during its creation.
int Pthread_attr_setscope(pthread_attr_t *attr, int scope)
The first parameter denotes to which thread within the process the
scope is defined.
The second parameter defines the scope of contention for the
thread pointed. It takes two values.
PTHREAD_SCOPE_SYSTEM
PTHREAD_SCOPE_PROCESS
If the scope value specified is not supported by the system, then the
function returns ENOTSUP.
2. Allocation Domain :
The allocation domain is a set of one or more resources for which a
thread is competing. In a multicore system, there may be one or more
allocation domains where each consists of one or more cores. One ULT
can be a part of one or more allocation domain. Due to this high
complexity in dealing with hardware and software architectural
interfaces, this control is not specified. But by default, the multicore
system will have an interface that affects the allocation domain of a
thread.

Consider a scenario, an operating system with three process P1, P2, P3

and 10 user level threads (T1 to T10) with a single allocation domain.
100% of CPU resources will be distributed among all the three
processes. The amount of CPU resources allocated to each process and
to each thread depends on the contention scope, scheduling policy and
priority of each thread defined by the application developer using
thread library and also depends on the system scheduler. These User
level threads are of a different contention scope.
In this case, the contention for allocation domain takes place as
follows,
1. Process P1:
All PCS threads T1, T2, T3 of Process P1 will compete among
themselves. The PCS threads of the same process can share one or
more LWP. T1 and T2 share an LWP and T3 are allocated to a
separate LWP. Between T1 and T2 allocation of kernel resources via
LWP is based on preemptive priority scheduling by the thread
library. A Thread with a high priority will preempt low priority
threads. Whereas, thread T1 of process p1 cannot preempt thread
T3 of process p3 even if the priority of T1 is greater than the priority
of T3. If the priority is equal, then the allocation of ULT to available
 LWPs is based on the scheduling policy of threads by the system
scheduler(not by thread library, in this case).
2. Process P2:
Both SCS threads T4 and T5 of process P2 will compete with
processes P1 as a whole and with SCS threads T8, T9, T10 of
process P3. The system scheduler will schedule the kernel resources
among P1, T4, T5, T8, T9, T10, and PCS threads (T6, T7) of process
P3 considering each as a separate process. Here, the Thread library
has no control of scheduling the ULT to the kernel resources.
3. Process P3:
Combination of PCS and SCS threads. Consider if the system
scheduler allocates 50% of CPU resources to process P3, then 25%
of resources is for process scoped threads and the remaining 25%
for system scoped threads. The PCS threads T6 and T7 will be
allocated to access the 25% resources based on the priority by the
thread library. The SCS threads T8, T9, T10 will divide the 25%
resources among themselves and access the kernel resources via
separate LWP and KLT. The SCS scheduling is by the system
scheduler.
Note:
For every system call to access the kernel resources, a Kernel Level
thread is created and associated to separate LWP by the system
scheduler.
Number of Kernel Level Threads = Total Number of LWP
Total Number of LWP = Number of LWP for SCS + Number of LWP for
PCS
Number of LWP for SCS = Number of SCS threads
Number of LWP for PCS = Depends on application developer
Here,
Number of SCS threads = 5
Number of LWP for PCS = 3
Number of SCS threads = 5
Number of LWP for SCS = 5
Total Number of LWP = 8 (=5+3)
Number of Kernel Level Threads = 8
Advantages of PCS over SCS :
 If all threads are PCS, then context switching, synchronization,
scheduling everything takes place within the userspace. This
reduces system calls and achieves better performance.
 PCS is cheaper than SCS.
 PCS threads share one or more available LWPs. For every SCS
thread, a separate LWP is [Link] every system call, a
separate KLT is created.
 The number of KLT and LWPs created highly depends on the number
of SCS threads created. This increases the kernel complexity of
handling scheduling and synchronization. Thereby, results in a
limitation over SCS thread creation, stating that, the number of SCS
threads to be smaller than the number of PCS threads.
 If the system has more than one allocation domain, then scheduling
and synchronization of resources becomes more tedious. Issues
arise when an SCS thread is a part of more than one allocation
domain, the system has to handle n number of interfaces.
The second boundary of thread scheduling involves CPU scheduling by
the system scheduler. The scheduler considers each kernel-level
thread as a separate process and provides access to the kernel
resources.

Multiple Processor Scheduling

Multiple processor scheduling or multiprocessor scheduling focuses on

designing the scheduling function for the system which is consist of ‘more
than one processor’. With multiple processors in the system, the load sharing
becomes feasible but it makes scheduling more complex.

As there is no policy or rule which can be declared as the best scheduling

solution to a system with a single processor. Similarly there no best
scheduling solution for a system with multiple processors as well.

In this section, we will be discussing the multiprocessor system along with the
keynotes that must be considered while scheduling the system with multiple
processors.

What is Multiprocessor?
A multiprocessor is a system with several processors. Well with the presence
of multiple processors it becomes complex to design a scheduling algorithm.
The multiprocessor system can be categorized into:

1. Loosely Coupled or Distributed Multiprocessor

Multiple processors in the system are independent of each other. Each

processor in the system has its own memory and I/O channels.

2. Functionally Specialized Processor

In this system, among the collection of multiple processors, there is a master

processor which is a general-purpose processor. This master processor
controls the other specialized processors in the system and provides services
to them.

3. Tightly Coupled Multiprocessors

In this system, the processors are under the integrated control of the
operating system. All the processor in this system shares the common
memory. These processors are sometimes also termed as homogeneous as
they are identical in terms of their functionality.

Keynotes of Multiple Processor Scheduling

Note: The multiprocessing system we are considering have the identical or
homogeneous processors in terms of functionality.
Techniques of multiprocessor Scheduling
Multiprocessor scheduling can be done in two ways asymmetric
multiprocessor scheduling and symmetric multiprocessor scheduling.

In asymmetric multiprocessor scheduling, one processor is assigned as

the master processor which handles all the decisions related to scheduling,
along with I/O processing and other system activities. It the master processor
which runs the operating systems code and the other slave processors only
execute the user code.

In symmetric multiprocessor scheduling, all the processors in the system

are self-scheduling. Each processor in the system either has its own list of
processes to be executed or there may be a common list of processes from
where the processors will extract the process to be executed.

Processor Affinity
Processor Affinity –
Processor Affinity means a processes has an affinity for the processor on
which it is currently running.
When a process runs on a specific processor there are certain effects on the
cache memory. The data most recently accessed by the process populate the
cache for the processor and as a result successive memory access by the
process are often satisfied in the cache memory. Now if the process migrates to
another processor, the contents of the cache memory must be invalidated for
the first processor and the cache for the second processor must be
repopulated. Because of the high cost of invalidating and repopulating caches,
most of the SMP(symmetric multiprocessing) systems try to avoid migration of
processes from one processor to another and try to keep a process running on
the same processor. This is known as PROCESSOR AFFINITY.
There are two types of processor affinity:
1. Soft Affinity – When an operating system has a policy of attempting to keep
a process running on the same processor but not guaranteeing it will do so,
this situation is called soft affinity.
2. Hard Affinity – Hard Affinity allows a process to specify a subset of
processors on which it may run. Some systems such as Linux implements
soft affinity but also provide some system calls like sched_setaffinity() that
supports hard affinity.
Load Balancing
On symmetric multiple processor system, all the processor must have an
equal workload to get the benefits of multiple processors in the system. If the
workload is not balanced properly among all the processors in the system, it
might happen that some processors may end up sitting idle and some would
have high workload along with the processes in awaiting in CPU.

Load balancing can be implemented on the system with multiple processors,

where every processor in the system has its own list of processes to execute.

If the system has a common list containing the processes to execute then
there is no need for load balancing. This is because whenever a processor will
become idle it will load itself with the process in a common list.

Load balancing can be achieved in two ways i.e. push migration and pull
migration.

Push Migration: Here a task is designed which keeps a periodic check on all
the processor to identify any imbalance of load. If it finds an imbalance of load
then task extracts the load (processes) from an overloaded processor and
assign them to the idle or less busy processor. This pushing of processes
from the overloaded processor to less busy processor is termed as pushing
migration.

Pull Migration: Here the idle processor itself extract a waiting process form
an overloaded or busy processor start executing it to balance the load.

The push and pull migration can be implemented in parallel. For example,
Linux system runs it push migration in every 200 milliseconds and whenever a
processor is found idle it runs it pull migration algorithm to pull processes from
overloaded processors.

If observed carefully the load balancing mechanism crosses the benefits of

processor affinity. As pushing or pulling a process from one processor to
another invalidate content of cache memory as we have seen in processor
affinity.

So there is no perfect strategy or rule to decide the best policy for scheduling
a system with multiple processors to extract maximum benefit.

Symmetric Multithreading
Symmetric multiple processor system has multiple physical processors that
allow several threads to execute concurrently. Now the idea is to create and
provide logical processors instead of physical processors. This concept of
providing logical processors to threads is termed as symmetric multithreading
and hyper-threading technology for Intel processors.

The concept of symmetric multithreading allows you to create several logical

processors over a single physical processor. The view that an operating
system has, have several logical processors where every logical processor
has its own architecture state. Each logical processor has its own general-
purpose and machine state registers. Each logical processor is capable of
handling interrupts and share resources of its physical memory.
The figure above shows you the view of two physical processors where each
of them has created two logical processors. Here from the operating system’s
view, there are four processors to schedule.

The concept of symmetric multithreading is more of hardware rather than

software. It is the hardware which is designed in a way that it could provide
architecture state to each logical processor along with interrupt handling.
Though the operating system must not be designed differently to achieve the
goal of symmetric multithreading. But if OS is designed differently to run on
such system then it can give performance gain.

Consider that that in symmetric multiprocessing we have implemented the

concept of symmetric multithreading and we have two physical processors
and each having two logical processors as in the figure above.

Now both the physical processors are idle. If the operating system is not
designed on the concept of symmetric multithreading then it might happen
that it would schedule separate threads on two separate logical processors of
the same physical processor leaving another physical processor idle.

Instead, it should schedule two separate threads on two different physical

processors.
So, at last, we would conclude that though we can gain performance by
scheduling the multiprocessing system still there is no best solution for
multiprocessing scheduling.

There are various organizations of multiprocessor operating system:

1. Each CPU has its own OS

In this types of the organization then there are much Central processing
units in the system and each CPU has its own private operating system and
memory is shared among all the processors and input-output system are also
shared. All the system is connected by the single bus.

ADVERTISEMENT

2. Master slave multiprocessor

In this type of multiprocessor model, there is a single data structure which
keeps track of the ready processes. In this model, one central processing
unit works as master and other central processing unit work as a slave. In
this, all the processors are handled by the single processor which is called
master server. The master server runs the operating system process and the
slave server run the user processes. The memory and input-output devices
are shared among all the processors and all the processor are connected to a
common bus. This system is simple and reduces the data sharing so this
system is called Asymmetric multiprocessing.
3. Symmetric multiprocessor
Symmetric Multiprocessors (SMP) is the third model. In this model, there is
one copy of the OS in memory, but any central processing unit can run it.
Now, when a system call is made, then the central processing unit on which
the system call was made traps to the kernel and then processes that
system call. This model balances processes and memory dynamical. This
approach uses Symmetric Multiprocessing where each processor is self-
scheduling. The scheduling proceeds further by having the scheduler for
each processor examine the ready queue and select a process to execute. In
this system, this is possible that all the process may be in common ready
queue or each processor may have its own private queue for the ready
process.
What is CPU Scheduling? Or process scheduling
algorithms
CPU Scheduling is a process of determining which process will own CPU for
execution while another process is on hold. The main task of CPU scheduling
is to make sure that whenever the CPU remains idle, the OS at least select
one of the processes available in the ready queue for execution. The selection
process will be carried out by the CPU scheduler. It selects one of the
processes in memory that are ready for execution.

Types of CPU Scheduling

Here are two kinds of Scheduling methods:

Preemptive Scheduling
In Preemptive Scheduling, the tasks are mostly assigned with their priorities.
Sometimes it is important to run a task with a higher priority before another
lower priority task, even if the lower priority task is still running. The lower
priority task holds for some time and resumes when the higher priority task
finishes its execution.

Non-Preemptive Scheduling
In this type of scheduling method, the CPU has been allocated to a specific
process. The process that keeps the CPU busy will release the CPU either by
switching context or terminating. It is the only method that can be used for
various hardware platforms. That's because it doesn't need special hardware
(for example, a timer) like preemptive scheduling.
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.
 Operating System - Memory Management
Memory management is the functionality of an operating system which handles or
manages primary memory and moves processes back and forth between main
memory and disk during execution. Memory management keeps track of each and
every memory location, regardless of either it is allocated to some process or it is free.
It checks how much memory is to be allocated to processes. It decides which process
will get memory at what time. It tracks whenever some memory gets freed or
unallocated and correspondingly it updates the status.
This tutorial will teach you basic concepts related to Memory Management.

Why Use Memory Management?

Here, are reasons for using memory management:

 It allows you to check how much memory needs to be allocated to

processes that decide which processor should get memory at what time.
 Tracks whenever inventory gets freed or unallocated. According to it will
update the status.
 It allocates the space to application routines.
 It also make sure that these applications do not interfere with each
other.
 Helps protect different processes from each other
 It places the programs in memory so that memory is utilized to its full
extent.

Process Address Space

The process address space is the set of logical addresses that a process references in
its code. For example, when 32-bit addressing is in use, addresses can range from 0 to
0x7fffffff; that is, 2^31 possible numbers, for a total theoretical size of 2 gigabytes.
The operating system takes care of mapping the logical addresses to physical
addresses at the time of memory allocation to the program. There are three types of
addresses used in a program before and after memory is allocated −

S.N. Memory Addresses & Description

1 Symbolic addresses
 The addresses used in a source code. The variable names, constants, and
instruction labels are the basic elements of the symbolic address space.

2 Relative addresses
At the time of compilation, a compiler converts symbolic addresses into relative
addresses.

3 Physical addresses
The loader generates these addresses at the time when a program is loaded into
main memory.

Virtual and physical addresses are the same in compile-time and load-time address-
binding schemes. Virtual and physical addresses differ in execution-time address-
binding scheme.
The set of all logical addresses generated by a program is referred to as a logical
address space. The set of all physical addresses corresponding to these logical
addresses is referred to as a physical address space.
The runtime mapping from virtual to physical address is done by the memory
management unit (MMU) which is a hardware device. MMU uses following mechanism
to convert virtual address to physical address.
 The value in the base register is added to every address generated by a user
process, which is treated as offset at the time it is sent to memory. For example,
if the base register value is 10000, then an attempt by the user to use address
location 100 will be dynamically reallocated to location 10100.
 The user program deals with virtual addresses; it never sees the real physical
addresses.

Static vs Dynamic Loading

The choice between Static or Dynamic Loading is to be made at the time of computer
program being developed. If you have to load your program statically, then at the time
of compilation, the complete programs will be compiled and linked without leaving any
external program or module dependency. The linker combines the object program with
other necessary object modules into an absolute program, which also includes logical
addresses.
If you are writing a Dynamically loaded program, then your compiler will compile the
program and for all the modules which you want to include dynamically, only
references will be provided and rest of the work will be done at the time of execution.
At the time of loading, with static loading, the absolute program (and data) is loaded
into memory in order for execution to start.
If you are using dynamic loading, dynamic routines of the library are stored on a disk
in relocatable form and are loaded into memory only when they are needed by the
program.

Static vs Dynamic Linking

As explained above, when static linking is used, the linker combines all other modules
needed by a program into a single executable program to avoid any runtime
dependency.
When dynamic linking is used, it is not required to link the actual module or library with
the program, rather a reference to the dynamic module is provided at the time of
compilation and linking. Dynamic Link Libraries (DLL) in Windows and Shared Objects
in Unix are good examples of dynamic libraries.

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.
 Operating System - Virtual Memory

A computer can address more memory than the amount physically installed on the
system. This extra memory is actually called virtual memory and it is a section of a
hard disk that's set up to emulate the computer's RAM.
The main visible advantage of this scheme is that programs can be larger than physical
memory. Virtual memory serves two purposes. First, it allows us to extend the use of
physical memory by using disk. Second, it allows us to have memory protection,
because each virtual address is translated to a physical address.
Following are the situations, when entire program is not required to be loaded fully in
main memory.
 User written error handling routines are used only when an error occurred in the
data or computation.
 Certain options and features of a program may be used rarely.
 Many tables are assigned a fixed amount of address space even though only a
small amount of the table is actually used.
  The ability to execute a program that is only partially in memory would counter
many benefits.
 Less number of I/O would be needed to load or swap each user program into
memory.
 A program would no longer be constrained by the amount of physical memory
that is available.
 Each user program could take less physical memory, more programs could be
run the same time, with a corresponding increase in CPU utilization and
throughput.
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.
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.
File Systems in Operating System:
Structure, Attributes, Type
What is File System?
A file is a collection of correlated information which is recorded on secondary
or non-volatile storage like magnetic disks, optical disks, and tapes. It is a
method of data collection that is used as a medium for giving input and
receiving output from that program.

In general, a file is a sequence of bits, bytes, or records whose meaning is

defined by the file creator and user. Every File has a logical location where
they are located for storage and retrieval.

Objective of File management System

Here are the main objectives of the file management system:

 It provides I/O support for a variety of storage device types.

 Minimizes the chances of lost or destroyed data
 Helps OS to standardized I/O interface routines for user processes.
 It provides I/O support for multiple users in a multiuser systems
environment.

Properties of a File System

Here, are important properties of a file system:

 Files are stored on disk or other storage and do not disappear when a
user logs off.
 Files have names and are associated with access permission that
permits controlled sharing.
 Files could be arranged or more complex structures to reflect the
relationship between them.
File structure
A File Structure needs to be predefined format in such a way that an operating
system understands . It has an exclusively defined structure, which is based
on its type.

Three types of files structure in OS:

 A text file: It is a series of characters that is organized in lines.

 An object file: It is a series of bytes that is organized into blocks.
 A source file: It is a series of functions and processes.

File Attributes
A file has a name and data. Moreover, it also stores meta information like file
creation date and time, current size, last modified date, etc. All this information
is called the attributes of a file system.

Here, are some important File attributes used in OS:

 Name: It is the only information stored in a human-readable form.

 Identifier: Every file is identified by a unique tag number within a file
system known as an identifier.
 Location: Points to file location on device.
 Type: This attribute is required for systems that support various types of
files.
 Size. Attribute used to display the current file size.
 Protection. This attribute assigns and controls the access rights of
reading, writing, and executing the file.
 Time, date and security: It is used for protection, security, and also
used for monitoring

File Type
It refers to the ability of the operating system to differentiate various types of
files like text files, binary, and source files. However, Operating systems like
MS_DOS and UNIX has the following type of files:
Character Special File
It is a hardware file that reads or writes data character by character, like
mouse, printer, and more.

Ordinary files
 These types of files stores user information.
 It may be text, executable programs, and databases.
 It allows the user to perform operations like add, delete, and modify.

Directory Files
 Directory contains files and other related information about those files.
Its basically a folder to hold and organize multiple files.

Special Files
 These files are also called device files. It represents physical devices
like printers, disks, networks, flash drive, etc.

Functions of File
 Create file, find space on disk, and make an entry in the directory.
 Write to file, requires positioning within the file
 Read from file involves positioning within the file
 Delete directory entry, regain disk space.
 Reposition: move read/write position.

Commonly used terms in File systems

Field:
This element stores a single value, which can be static or variable length.

DATABASE:
Collection of related data is called a database. Relationships among elements
of data are explicit.
FILES:
Files is the collection of similar record which is treated as a single entity.

RECORD:
A Record type is a complex data type that allows the programmer to create a
new data type with the desired column structure. Its groups one or more
columns to form a new data type. These columns will have their own names
and data type.

File Access Methods

File access is a process that determines the way that files are accessed and
read into memory. Generally, a single access method is always supported by
operating systems. Though there are some operating system which also
supports multiple access methods.

Three file access methods are:

 Sequential access
 Direct random access
 Index sequential access

Sequential Access
In this type of file access method, records are accessed in a certain pre-
defined sequence. In the sequential access method, information stored in the
file is also processed one by one. Most compilers access files using this
access method.

Random Access
The random access method is also called direct random access. This method
allow accessing the record directly. Each record has its own address on which
can be directly accessed for reading and writing.

Sequential Access
This type of accessing method is based on simple sequential access. In this
access method, an index is built for every file, with a direct pointer to different
memory blocks. In this method, the Index is searched sequentially, and its
pointer can access the file directly. Multiple levels of indexing can be used to
offer greater efficiency in access. It also reduces the time needed to access a
single record.

Space Allocation
In the Operating system, files are always allocated disk spaces.

Three types of space allocation methods are:

 Linked Allocation
 Indexed Allocation
 Contiguous Allocation

Contiguous Allocation
In this method,

 Every file users a contiguous address space on memory.

 Here, the OS assigns disk address is in linear order.
 In the contiguous allocation method, external fragmentation is the
biggest issue.

Linked Allocation
In this method,

 Every file includes a list of links.

 The directory contains a link or pointer in the first block of a file.
 With this method, there is no external fragmentation
 This File allocation method is used for sequential access files.
 This method is not ideal for a direct access file.

Indexed Allocation
In this method,

 Directory comprises the addresses of index blocks of the specific files.

 An index block is created, having all the pointers for specific files.
  All files should have individual index blocks to store the addresses for
disk space.

File Directories
A single directory may or may not contain multiple files. It can also have sub-
directories inside the main directory. Information about files is maintained by
Directories. In Windows OS, it is called folders.

Single Level
Directory

Following is the information which is maintained in a directory:

 Name The name which is displayed to the user.

 Type: Type of the directory.
 Position: Current next-read/write pointers.
 Location: Location on the device where the file header is stored.
 Size : Number of bytes, block, and words in the file.
 Protection: Access control on read/write/execute/delete.
 Usage: Time of creation, access, modification

File types- name, extension

File Type Usual extension Function
Executable exe, com, bin or ready-to-run machine- language program
none

Object obj, o complied, machine language, not linked

Source code c. p, pas, 177, asm, source code in various languages

a

Batch bat, sh Series of commands to be executed

Text txt, doc textual data documents

Word doc,docs, tex, rrf, various word-processor formats

processor etc.

Library lib, h libraries of routines

Archive arc, zip, tar related files grouped into one file, sometimes
compressed.

Operating System - Security

Security refers to providing a protection system to computer system resources such as
CPU, memory, disk, software programs and most importantly data/information stored in
the computer system. If a computer program is run by an unauthorized user, then
he/she may cause severe damage to computer or data stored in it. So a computer
system must be protected against unauthorized access, malicious access to system
memory, viruses, worms etc. We're going to discuss following topics in this chapter.
  Authentication
 One Time passwords
 Program Threats
 System Threats
 Computer Security Classifications

Authentication
Authentication refers to identifying each user of the system and associating the
executing programs with those users. It is the responsibility of the Operating System to
create a protection system which ensures that a user who is running a particular
program is authentic. Operating Systems generally identifies/authenticates users using
following three ways −
 Username / Password − User need to enter a registered username and
password with Operating system to login into the system.
 User card/key − User need to punch card in card slot, or enter key generated by
key generator in option provided by operating system to login into the system.
 User attribute - fingerprint/ eye retina pattern/ signature − User need to pass
his/her attribute via designated input device used by operating system to login
into the system.

One Time passwords

One-time passwords provide additional security along with normal authentication. In
One-Time Password system, a unique password is required every time user tries to
login into the system. Once a one-time password is used, then it cannot be used again.
One-time password are implemented in various ways.
 Random numbers − Users are provided cards having numbers printed along
with corresponding alphabets. System asks for numbers corresponding to few
alphabets randomly chosen.
 Secret key − User are provided a hardware device which can create a secret id
mapped with user id. System asks for such secret id which is to be generated
every time prior to login.
 Network password − Some commercial applications send one-time passwords
to user on registered mobile/ email which is required to be entered prior to login.

Program Threats
Operating system's processes and kernel do the designated task as instructed. If a
user program made these process do malicious tasks, then it is known as Program
Threats. One of the common example of program threat is a program installed in a
computer which can store and send user credentials via network to some hacker.
Following is the list of some well-known program threats.
  Trojan Horse − Such program traps user login credentials and stores them to
send to malicious user who can later on login to computer and can access
system resources.
 Trap Door − If a program which is designed to work as required, have a security
hole in its code and perform illegal action without knowledge of user then it is
called to have a trap door.
 Logic Bomb − Logic bomb is a situation when a program misbehaves only
when certain conditions met otherwise it works as a genuine program. It is
harder to detect.
 Virus − Virus as name suggest can replicate themselves on computer system.
They are highly dangerous and can modify/delete user files, crash systems. A
virus is generatlly a small code embedded in a program. As user accesses the
program, the virus starts getting embedded in other files/ programs and can
make system unusable for user

System Threats
System threats refers to misuse of system services and network connections to put
user in trouble. System threats can be used to launch program threats on a complete
network called as program attack. System threats creates such an environment that
operating system resources/ user files are misused. Following is the list of some well-
known system threats.
 Worm − Worm is a process which can choked down a system performance by
using system resources to extreme levels. A Worm process generates its
multiple copies where each copy uses system resources, prevents all other
processes to get required resources. Worms processes can even shut down an
entire network.
 Port Scanning − Port scanning is a mechanism or means by which a hacker
can detects system vulnerabilities to make an attack on the system.
 Denial of Service − Denial of service attacks normally prevents user to make
legitimate use of the system. For example, a user may not be able to use
internet if denial of service attacks browser's content settings.

Computer Security Classifications

As per the U.S. Department of Defense Trusted Computer System's Evaluation Criteria
there are four security classifications in computer systems: A, B, C, and D. This is
widely used specifications to determine and model the security of systems and of
security solutions. Following is the brief description of each classification.

S.N. Classification Type & Description

1
Type A
 Highest Level. Uses formal design specifications and verification techniques. Grants
a high degree of assurance of process security.

2
Type B
Provides mandatory protection system. Have all the properties of a class C2
system. Attaches a sensitivity label to each object. It is of three types.
 B1 − Maintains the security label of each object in the system. Label is used
for making decisions to access control.
 B2 − Extends the sensitivity labels to each system resource, such as storage
objects, supports covert channels and auditing of events.
 B3 − Allows creating lists or user groups for access-control to grant access or
revoke access to a given named object.

3
Type C
Provides protection and user accountability using audit capabilities. It is of two
types.
 C1 − Incorporates controls so that users can protect their private information
and keep other users from accidentally reading / deleting their data. UNIX
versions are mostly Cl class.
 C2 − Adds an individual-level access control to the capabilities of a Cl level
system.

4
Type D
Lowest level. Minimum protection. MS-DOS, Window 3.1 fall in this category.

Disk Scheduling Algorithms

Disk scheduling is done by operating systems to schedule I/O requests
arriving for the disk. Disk scheduling is also known as I/O scheduling.
Disk scheduling is important because:
 Multiple I/O requests may arrive by different processes and only one
I/O request can be served at a time by the disk controller. Thus
other I/O requests need to wait in the waiting queue and need to be
scheduled.
 Two or more request may be far from each other so can result in
greater disk arm movement.
 Hard drives are one of the slowest parts of the computer system
and thus need to be accessed in an efficient manner.
There are many Disk Scheduling Algorithms but before discussing
them let’s have a quick look at some of the important terms:
 Seek Time:Seek time is the time taken to locate the disk arm to a
specified track where the data is to be read or write. So the disk
scheduling algorithm that gives minimum average seek time is
better.
 Rotational Latency: Rotational Latency is the time taken by the
desired sector of disk to rotate into a position so that it can access
the read/write heads. So the disk scheduling algorithm that gives
minimum rotational latency is better.
 Transfer Time: Transfer time is the time to transfer the data. It
depends on the rotating speed of the disk and number of bytes to
be transferred.
 Disk Access Time: Disk Access Time is:

Disk Access Time = Seek Time +

Rotational Latency +
Transfer Time
 Disk Response Time: Response Time is the average of time spent by
a request waiting to perform its I/O operation. Average Response
time is the response time of the all requests. Variance Response
Time is measure of how individual request are serviced with respect
to average response time. So the disk scheduling algorithm that
gives minimum variance response time is better.
Disk Scheduling Algorithms
1. FCFS: FCFS is the simplest of all the Disk Scheduling Algorithms. In
FCFS, the requests are addressed in the order they arrive in the disk
[Link] us understand this with the help of an example.

Example:
Suppose the order of request is- (82,170,43,140,24,16,190)
And current position of Read/Write head is : 50

So, total seek time:

=(82-50)+(170-82)+(170-43)+(140-43)+(140-24)+(24-16)+(190-
16)
=642
Advantages:
 Every request gets a fair chance
 No indefinite postponement
Disadvantages:
 Does not try to optimize seek time
 May not provide the best possible service
2. SSTF: In SSTF (Shortest Seek Time First), requests having shortest
seek time are executed first. So, the seek time of every request is
calculated in advance in the queue and then they are scheduled
according to their calculated seek time. As a result, the request near
the disk arm will get executed first. SSTF is certainly an
improvement over FCFS as it decreases the average response time
and increases the throughput of [Link] us understand this with
the help of an example.
 Example:
Suppose the order of request is- (82,170,43,140,24,16,190)
And current position of Read/Write head is : 50

So, total seek time:

=(50-43)+(43-24)+(24-16)+(82-16)+(140-82)+(170-40)+(190-170)
=208
Advantages:
 Average Response Time decreases
 Throughput increases
Disadvantages:
 Overhead to calculate seek time in advance
 Can cause Starvation for a request if it has higher seek time as
compared to incoming requests
 High variance of response time as SSTF favours only some requests
3. SCAN: In SCAN algorithm the disk arm moves into a particular
direction and services the requests coming in its path and after
reaching the end of disk, it reverses its direction and again services
the request arriving in its path. So, this algorithm works as an
elevator and hence also known as elevator algorithm. As a result, the
requests at the midrange are serviced more and those arriving
behind the disk arm will have to wait.

Example:
Suppose the requests to be addressed are-
82,170,43,140,24,16,190. And the Read/Write arm is at 50, and it is
also given that the disk arm should move “towards the larger
value”.
 Therefore, the seek time is calculated as:
=(199-50)+(199-16)
=332
Advantages:
 High throughput
 Low variance of response time
 Average response time
Disadvantages:
 Long waiting time for requests for locations just visited by disk arm
4. CSCAN: In SCAN algorithm, the disk arm again scans the path that
has been scanned, after reversing its direction. So, it may be
possible that too many requests are waiting at the other end or
there may be zero or few requests pending at the scanned area.
These situations are avoided in CSCAN algorithm in which the disk arm
instead of reversing its direction goes to the other end of the disk and
starts servicing the requests from there. So, the disk arm moves in a
circular fashion and this algorithm is also similar to SCAN algorithm
and hence it is known as C-SCAN (Circular SCAN).
Example:
Suppose the requests to be addressed are-82,170,43,140,24,16,190.
And the Read/Write arm is at 50, and it is also given that the disk arm
should move “towards the larger value”.

Seek time is calculated as:

=(199-50)+(199-0)+(43-0)
=391
Advantages:
 Provides more uniform wait time compared to SCAN
5. LOOK: It is similar to the SCAN disk scheduling algorithm except for
the difference that the disk arm in spite of going to the end of the
disk goes only to the last request to be serviced in front of the head
and then reverses its direction from there only. Thus it prevents the
extra delay which occurred due to unnecessary traversal to the end
of the disk.

Example:
Suppose the requests to be addressed are-
82,170,43,140,24,16,190. And the Read/Write arm is at 50, and it is
 also given that the disk arm should move “towards the larger
value”.

So, the seek time is calculated as:

=(190-50)+(190-16)
=314
6. CLOOK: As LOOK is similar to SCAN algorithm, in similar way, CLOOK
is similar to CSCAN disk scheduling algorithm. In CLOOK, the disk
arm in spite of going to the end goes only to the last request to be
serviced in front of the head and then from there goes to the other
end’s last request. Thus, it also prevents the extra delay which
occurred due to unnecessary traversal to the end of the disk.
 Example:
Suppose the requests to be addressed are-
82,170,43,140,24,16,190. And the Read/Write arm is at 50, and it is
also given that the disk arm should move “towards the larger
value”

So, the seek time is calculated as:

=(190-50)+(190-16)+(43-16)
=341
7. RSS– It stands for random scheduling and just like its name it is
nature. It is used in situations where scheduling involves random
attributes such as random processing time, random due dates,
random weights, and stochastic machine breakdowns this algorithm
sits perfect. Which is why it is usually used for and analysis and
simulation.
8. LIFO– In LIFO (Last In, First Out) algorithm, newest jobs are serviced
before the existing ones i.e. in order of requests that get serviced
 the job that is newest or last entered is serviced first and then the
rest in the same order.
Advantages
 Maximizes locality and resource utilization
Disadvantages
 Can seem a little unfair to other requests and if new requests
keep coming in, it cause starvation to the old and existing ones.

Demand Paging :
The process of loading the page into memory on demand (whenever
page fault occurs) is known as demand paging.
The process includes the following steps :

1. If the CPU tries to refer to a page that is currently not available in

the main memory, it generates an interrupt indicating a memory
access fault.
2. The OS puts the interrupted process in a blocking state. For the
execution to proceed the OS must bring the required page into the
memory.
3. The OS will search for the required page in the logical address
space.
4. The required page will be brought from logical address space to
physical address space. The page replacement algorithms are used
for the decision-making of replacing the page in physical address
space.
5. The page table will be updated accordingly.
6. The signal will be sent to the CPU to continue the program execution
and it will place the process back into the ready state.
Hence whenever a page fault occurs these steps are followed by the
operating system and the required page is brought into memory.
Advantages :
 More processes may be maintained in the main memory: Because
we are going to load only some of the pages of any particular
process, there is room for more processes. This leads to more
efficient utilization of the processor because it is more likely that at
least one of the more numerous processes will be in the ready state
at any particular time.
 A process may be larger than all of the main memory: One of the
most fundamental restrictions in programming is lifted. A process
larger than the main memory can be executed because of demand
paging. The OS itself loads pages of a process in the main memory
as required.
 It allows greater multiprogramming levels by using less of the
available (primary) memory for each process.
Swapping:
Swapping a process out means removing all of its pages from memory,
or marking them so that they will be removed by the normal page
replacement process. Suspending a process ensures that it is not
runnable while it is swapped out. At some later time, the system swaps
back the process from the secondary storage to the main memory.
When a process is busy swapping pages in and out then this situation
is called thrashing.
Thrashing :
At any given time, only a few pages of any process are in the main
memory and therefore more processes can be maintained in memory.
Furthermore, time is saved because unused pages are not swapped in
and out of memory. However, the OS must be clever about how it
manages this scheme. In the steady-state practically, all of the main
memory will be occupied with process pages, so that the processor and
OS have direct access to as many processes as possible. Thus when
the OS brings one page in, it must throw another out. If it throws out a
page just before it is used, then it will just have to get that page again
almost immediately. Too much of this leads to a condition called
Thrashing. The system spends most of its time swapping pages rather
than executing instructions. So a good page replacement algorithm is
required.
In the given diagram, the initial degree of multiprogramming up to
some extent of point(lambda), the CPU utilization is very high and the
system resources are utilized 100%. But if we further increase the
degree of multiprogramming the CPU utilization will drastically fall
down and the system will spend more time only on the page
replacement and the time is taken to complete the execution of the
process will increase. This situation in the system is called thrashing.
Causes of Thrashing :
1. High degree of multiprogramming : If the number of processes keeps
on increasing in the memory then the number of frames allocated to
 each process will be decreased. So, fewer frames will be available
for each process. Due to this, a page fault will occur more frequently
and more CPU time will be wasted in just swapping in and out of
pages and the utilization will keep on decreasing.
For example:
Let free frames = 400
Case 1: Number of process = 100
Then, each process will get 4 frames.
Case 2: Number of processes = 400
Each process will get 1 frame.
Case 2 is a condition of thrashing, as the number of processes is
increased, frames per process are decreased. Hence CPU time will
be consumed in just swapping pages.

2. Lacks of Frames: If a process has fewer frames then fewer pages of

that process will be able to reside in memory and hence more
frequent swapping in and out will be required. This may lead to
thrashing. Hence sufficient amount of frames must be allocated to
each process in order to prevent thrashing.
Recovery of Thrashing :
 Do not allow the system to go into thrashing by instructing the long-
term scheduler not to bring the processes into memory after the
threshold.
 If the system is already thrashing then instruct the mid-term
schedular to suspend some of the processes so that we can recover
the system from thrashing.

Virtual Memory in OS: What is, Demand

Paging, Advantages
What is Virtual Memory?
Virtual Memory is a storage mechanism which offers user an illusion of
having a very big main memory. It is done by treating a part of secondary
memory as the main memory. In Virtual memory, the user can store
processes with a bigger size than the available main memory.
Therefore, instead of loading one long process in the main memory, the OS
loads the various parts of more than one process in the main memory. Virtual
memory is mostly implemented with demand paging and demand
segmentation.

Why Need Virtual Memory?

Here, are reasons for using virtual memory:

 Whenever your computer doesn’t have space in the physical memory it

writes what it needs to remember to the hard disk in a swap file as
virtual memory.
 If a computer running Windows needs more memory/RAM, then
installed in the system, it uses a small portion of the hard drive for this
purpose.

How Virtual Memory Works?

In the modern world, virtual memory has become quite common these days. It
is used whenever some pages require to be loaded in the main memory for
the execution, and the memory is not available for those many pages.

So, in that case, instead of preventing pages from entering in the main
memory, the OS searches for the RAM space that are minimum used in the
recent times or that are not referenced into the secondary memory to make
the space for the new pages in the main memory.

Let’s understand virtual memory management with the help of one example.

For example:
Let’s assume that an OS requires 300 MB of memory to store all the running
programs. However, there’s currently only 50 MB of available physical
memory stored on the RAM.

 The OS will then set up 250 MB of virtual memory and use a program
called the Virtual Memory Manager(VMM) to manage that 250 MB.
 So, in this case, the VMM will create a file on the hard disk that is 250
MB in size to store extra memory that is required.
 The OS will now proceed to address memory as it considers 300 MB of
real memory stored in the RAM, even if only 50 MB space is available.
  It is the job of the VMM to manage 300 MB memory even if just 50 MB
of real memory space is available.

What is Demand Paging?

A demand paging mechanism is very much similar to a paging system with

swapping where processes stored in the secondary memory and pages are
loaded only on demand, not in advance.

So, when a context switch occurs, the OS never copy any of the old program’s
pages from the disk or any of the new program’s pages into the main memory.
Instead, it will start executing the new program after loading the first page and
fetches the program’s pages, which are referenced.

During the program execution, if the program references a page that may not
be available in the main memory because it was swapped, then the processor
considers it as an invalid memory reference. That’s because the page fault
and transfers send control back from the program to the OS, which demands
to store page back into the memory.
Types of Page Replacement Methods
Here, are some important Page replacement methods

 FIFO
 Optimal Algorithm
 LRU Page Replacement

FIFO Page Replacement

FIFO (First-in-first-out) is a simple implementation method. In this method,
memory selects the page for a replacement that has been in the virtual
address of the memory for the longest time.

Features:
 Whenever a new page loaded, the page recently comes in the memory
is removed. So, it is easy to decide which page requires to be removed
as its identification number is always at the FIFO stack.
 The oldest page in the main memory is one that should be selected for
replacement first.

Optimal Algorithm
The optimal page replacement method selects that page for a replacement for
which the time to the next reference is the longest.

Features:
 Optimal algorithm results in the fewest number of page faults. This
algorithm is difficult to implement.
 An optimal page-replacement algorithm method has the lowest page-
fault rate of all algorithms. This algorithm exists and which should be
called MIN or OPT.
 Replace the page which unlike to use for a longer period of time. It only
uses the time when a page needs to be used.
LRU Page Replacement
The full form of LRU is the Least Recently Used page. This method helps OS
to find page usage over a short period of time. This algorithm should be
implemented by associating a counter with an even- page.

How does it work?

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

Features:
 The LRU replacement method has the highest count. This counter is
also called aging registers, which specify their age and how much their
associated pages should also be referenced.
 The page which hasn’t been used for the longest time in the main
memory is the one that should be selected for replacement.
 It also keeps a list and replaces pages by looking back into time.

Fault rate
Fault rate is a frequency with which a designed system or component fails. It
is expressed in failures per unit of time. It is denoted by the Greek letter ?
(lambda).

Advantages of Virtual Memory

Here, are pros/benefits of using Virtual Memory:

 Virtual memory helps to gain speed when only a particular segment of

the program is required for the execution of the program.
 It is very helpful in implementing a multiprogramming environment.
 It allows you to run more applications at once.
 It helps you to fit many large programs into smaller programs.
 Common data or code may be shared between memory.
 Process may become even larger than all of the physical memory.
 Data / code should be read from disk whenever required.
 The code can be placed anywhere in physical memory without requiring
relocation.
  More processes should be maintained in the main memory, which
increases the effective use of CPU.
 Each page is stored on a disk until it is required after that, it will be
removed.
 It allows more applications to be run at the same time.
 There is no specific limit on the degree of multiprogramming.
 Large programs should be written, as virtual address space available is
more compared to physical memory.

Disadvantages of Virtual Memory

Here, are drawbacks/cons of using virtual memory:

 Applications may run slower if the system is using virtual memory.

 Likely takes more time to switch between applications.
 Offers lesser hard drive space for your use.
 It reduces system stability.
 It allows larger applications to run in systems that don’t offer enough
physical RAM alone to run them.
 It doesn’t offer the same performance as RAM.
 It negatively affects the overall performance of a system.
 Occupy the storage space, which may be used otherwise for long term
data storage.

Swap-Space Management in Operating

system
Swapping is a memory management technique used in multi-
programming to increase the number of processes sharing the CPU. It
is a technique of removing a process from the main memory and
storing it into secondary memory, and then bringing it back into the
main memory for continued execution. This action of moving a process
out from main memory to secondary memory is called Swap Out and
the action of moving a process out from secondary memory to main
memory is called Swap In.
Swap-Space :
The area on the disk where the swapped-out processes are stored is
called swap space.
Swap-Space Management :
Swap-Swap management is another low-level task of the operating
system. Disk space is used as an extension of main memory by the
virtual memory. As we know the fact that disk access is much slower
than memory access, In the swap-space management we are using
disk space, so it will significantly decreases system performance.
Basically, in all our systems we require the best throughput, so the
goal of this swap-space implementation is to provide the virtual
memory the best throughput. In these article, we are going to discuss
how swap space is used, where swap space is located on disk, and how
swap space is managed.
Swap-Space Use :
Swap-space is used by the different operating-system in various ways.
The systems which are implementing swapping may use swap space to
hold the entire process which may include image, code and data
segments. Paging systems may simply store pages that have been
pushed out of the main memory. The need of swap space on a system
can vary from a megabytes to gigabytes but it also depends on the
amount of physical memory, the virtual memory it is backing and the
way in which it is using the virtual memory.

It is safer to overestimate than to underestimate the amount of swap

space required, because if a system runs out of swap space it may be
forced to abort the processes or may crash entirely. Overestimation
wastes disk space that could otherwise be used for files, but it does not
harm other.
Following table shows different system using amount of swap space:
Figure – Different systems using amount of swap-space
Explanation of above table :
Solaris, setting swap space equal to the amount by which virtual
memory exceeds page-able physical memory. In the past Linux has
suggested setting swap space to double the amount of physical
memory. Today, this limitation is gone, and most Linux systems use
considerably less swap space.
Including Linux, some operating systems; allow the use of multiple
swap spaces, including both files and dedicated swap partitions. The
swap spaces are placed on the disk so the load which is on the I/O by
the paging and swapping will spread over the system’s bandwidth.
Swap-Space Location :
Figure – Location of swap-space
A swap space can reside in one of the two places –
1. Normal file system
2. Separate disk partition
Let, if the swap-space is simply a large file within the file system. To
create it, name it and allocate its space normal file-system routines
can be used. This approach, through easy to implement, is inefficient.
Navigating the directory structures and the disk-allocation data
structures takes time and extra disk access. During reading or writing
of a process image, external fragmentation can greatly increase
swapping times by forcing multiple seeks.
There is also an alternate to create the swap space which is in a
separate raw partition. There is no presence of any file system in this
place. Rather, a swap space storage manager is used to allocate and
de-allocate the blocks. from the raw partition. It uses the algorithms for
speed rather than storage efficiency, because we know the access time
of swap space is shorter than the file system. By this Internal
fragmentation increases, but it is acceptable, because the life span
of the swap space is shorter than the files in the file system. Raw
partition approach creates fixed amount of swap space in case of
the disk partitioning.
Some operating systems are flexible and can swap both in raw
partitions and in the file system space, example: Linux.
Swap-Space Management: An Example –
The traditional UNIX kernel started with an implementation of
swapping that copied entire process between contiguous disk regions
and memory. UNIX later evolve to a combination of swapping and
paging as paging hardware became available. In Solaris, the designers
changed standard UNIX methods to improve efficiency. More changes
were made in later versions of Solaris, to improve the efficiency.