Introduction

An Operating System (OS) is an interface between computer user and computer hardware. An operating
system is software which performs all the basic tasks like file management, memory management, process
management, handling input and output, and controlling peripheral devices such as disk drives and printers.
An operating system is a program that acts as an interface between the user and the computer hardware and
controls the execution of all kinds of programs.

Following are some of important functions of an operating System. (Services)

 Memory Management
 Processor Management
 Device Management
 File Management
 Security
o Availability : protecting system against interruption
o Confidentiality: avoiding unauthorized access of data
o Data integrity: protection of data from unauthorized modifications
o Authenticity : identity of users and validity of message or data
 Control over system performance
 Job accounting
 Error detecting aids
 Coordination between other software and users
Memory Management

Memory management refers to management of Primary Memory or Main Memory. Main memory is a large array
of words or bytes where each word or byte has its own address.

Main memory provides a fast storage that can be accessed directly by the CPU. For a program to be executed, it
must in the main memory. An Operating System does the following activities for memory management −

 Keeps tracks of primary memory, i.e., what part of it are in use by whom, what parts are not in use.
 In multiprogramming, the OS decides which process will get memory when and how much.
 Allocates the memory when a process requests it to do so.
 De-allocates the memory when a process no longer needs it or has been terminated.
Processor Management

In multiprogramming environment, the OS decides which process gets the processor when and for how much
time. This function is called process scheduling. An Operating System does the following activities for processor
management −

 Keeps tracks of processor and status of process. The program responsible for this task is known as traffic
controller.
 Allocates the processor (CPU) to a process.
 De-allocates processor when a process is no longer required.

Device Management

An Operating System manages device communication via their respective drivers. It does the following
activities for device management −
 Keeps tracks of all devices. Program responsible for this task is known as the I/O controller.
 Decides which process gets the device when and for how much time.
 Allocates the device in the efficient way.
 De-allocates devices.

File Management
A file system is normally organized into directories for easy navigation and usage. These
directories may contain files and other directions.
An Operating System does the following activities for file management −
 Keeps track of information, location, uses, status etc. The collective facilities are often known as file
system.
 Decides who gets the resources.
 Allocates the resources.
 De-allocates the resources.
Other Important Activities
Following are some of the important activities that an Operating System performs −

 Security − By means of password and similar other techniques, it prevents unauthorized access to
programs and data.
 Control over system performance − Recording delays between request for a service and response from
the system.
 Job accounting − Keeping track of time and resources used by various jobs and users.
 Error detecting aids − Production of dumps, traces, error messages, and other debugging and error
detecting aids.
 Coordination between other softwares and users − Coordination and assignment of compilers,
interpreters, assemblers and other software to the various users of the computer systems.

Types of Operating systems

Batch operating system

The users of a batch operating system do not interact with the computer directly. Each user prepares his job
on an off-line device like punch cards and submits it to the computer operator. To speed up processing, jobs with
similar needs are batched together and run as a group. The programmers leave their programs with the operator and
the operator then sorts the programs with similar requirements into batches.
The problems with Batch Systems are as follows −

 Lack of interaction between the user and the job.

 CPU is often idle, because the speed of the mechanical I/O devices is slower than the CPU.
 Difficult to provide the desired priority.

Time-sharing operating systems

Time-sharing is a technique which enables many people, located at various terminals, to use a particular
computer system at the same time. Time-sharing or multitasking is a logical extension of multiprogramming.
Processor's time which is shared among multiple users simultaneously is termed as time-sharing.
The main difference between Multiprogrammed Batch Systems and Time-Sharing Systems is that in case
of Multiprogrammed batch systems, the objective is to maximize processor use, whereas in Time-Sharing Systems,
the objective is to minimize response time.
Multiple jobs are executed by the CPU by switching between them, but the switches occur so frequently.
Thus, the user can receive an immediate response. For example, in a transaction processing, the processor executes
each user program in a short burst or quantum of computation.

Advantages of Timesharing operating systems are as follows −

 Provides the advantage of quick response.

 Avoids duplication of software.
 Reduces CPU idle time.
Disadvantages of Time-sharing operating systems are as follows −

 Problem of reliability.
 Question of security and integrity of user programs and data.
 Problem of data communication.

Distributed operating System

Distributed systems use multiple central processors to serve multiple real-time applications and multiple
users. Data processing jobs are distributed among the processors accordingly.
The processors communicate with one another through various communication lines (such as high-speed buses or
telephone lines). These are referred as loosely coupled systems or distributed systems. Processors in a distributed
system may vary in size and function. These processors are referred as sites, nodes, computers, and so on.
The advantages of distributed systems are as follows −

 With resource sharing facility, a user at one site may be able to use the resources available at another.
 Speedup the exchange of data with one another via electronic mail.
 If one site fails in a distributed system, the remaining sites can potentially continue operating.
 Better service to the customers.
 Reduction of the load on the host computer.
 Reduction of delays in data processing.

Network operating System

A Network Operating System runs on a server and provides the server the capability to manage data, users,
groups, security, applications, and other networking functions. The primary purpose of the network operating
system is to allow shared file and printer access among multiple computers in a network, typically a local area
network (LAN), a private network or to other networks.
Examples of network operating systems include Microsoft Windows Server 2003, Microsoft Windows Server
2008, UNIX, Linux, Mac OS X, Novell NetWare, and BSD.

The advantages of network operating systems are as follows −

 Centralized servers are highly stable.

 Security is server managed.
 Upgrades to new technologies and hardware can be easily integrated into the system.
 Remote access to servers is possible from different locations and types of systems.
The disadvantages of network operating systems are as follows −

 High cost of buying and running a server.

 Dependency on a central location for most operations.
 Regular maintenance and updates are required.

The characteristics of uniprogramming are as follows:

- Uni programming allows only one program to be present in memory at a time.

- The resources are provided to the single program that is present in the memory at that time.
- Since only one program is loaded the size is small as well.

Characteristics of multiprogramming:

- Multiple programs can be present in the memory at a given time.

- The resources are dynamically allocated.
- The size of the memory is larger comparatively.

In a multiprogramming system there are one or more programs loaded in main memory which are ready to execute.
Only one program at a time is able to get the CPU for executing its instructions (i.e., there is at most one process
running on the system) while all the others are waiting their turn.
The main idea of multiprogramming is to maximize the use of CPU time. Indeed, suppose the currently running
process is performing an I/O task (which, by definition, does not need the CPU to be accomplished). Then, the OS
may interrupt that process and give the control to one of the other in-main-memory programs that are ready to
execute (i.e. process context switching). In this way, no CPU time is wasted by the system waiting for the I/O task to
be completed, and a running process keeps executing until either it voluntarily releases the CPU or when it blocks
for an I/O operation. Therefore, the ultimate goal of multiprogramming is to keep the CPU busy as long as there are
processes ready to execute.

Multiprocessing
Multiprocessing sometimes refers to executing multiple processes (programs) at the same time. This might be
misleading because we have already introduced the term “multiprogramming” to describe that before.
In fact, multiprocessing refers to the hardware (i.e., the CPU units) rather than the software (i.e., running processes).
If the underlying hardware provides more than one processor then that is multiprocessing. Several variations on the
basic scheme exist, e.g., multiple cores on one die or multiple dies in one package or multiple packages in one
system.
Anyway, a system can be both multiprogrammed by having multiple programs running at the same time and
multiprocessing by having more than one physical processor.
Process
A Program in execution. An instance of a program running on a computer

Process Control Block (PCB)

A Process Control Block is a data structure maintained by the Operating System for every process. The
PCB is identified by an integer process ID (PID). A PCB keeps all the information needed to keep track of a
process as listed below

Process State
The current state of the process i.e., whether it is ready, running, waiting, or whatever.
Process privileges
This is required to allow/disallow access to system resources.
Process ID
Unique identification for each of the process in the operating system.
Pointer
A pointer to parent process.
Program Counter
Program Counter is a pointer to the address of the next instruction to be executed for this process.
CPU registers
Various CPU registers where process need to be stored for execution for running state.
CPU Scheduling Information
Process priority and other scheduling information which is required to schedule the process.
Memory management information
This includes the information of page table, memory limits, Segment table depending on memory used by
the operating system.
Accounting information
This includes the amount of CPU used for process execution, time limits, execution ID etc.
IO status information
This includes a list of I/O devices allocated to the process

The architecture of a PCB is completely dependent on Operating System and may contain different
information in different operating systems. Here is a simplified diagram of a PCB

The PCB is maintained for a process throughout its lifetime, and is deleted once the process terminates.
Process Life Cycle
When a process executes, it passes through different states. These stages may differ in different operating
systems. In general, a process can have one of the following five states at a time.
Start
This is the initial state when a process is first started/created.
Ready
The process is waiting to be assigned to a processor. Ready processes are waiting to have the processor
allocated to them by the operating system so that they can run. Process may come into this state after Start state or
while running it by but interrupted by the scheduler to assign CPU to some other process.
Running
Once the process has been assigned to a processor by the OS scheduler, the process state is set to running
and the processor executes its instructions.
Waiting
Process moves into the waiting state if it needs to wait for a resource, such as waiting for user input, or
waiting for a file to become available.
Terminated or Exit
Once the process finishes its execution, or it is terminated by the operating system, it is moved to the terminated
state where it waits to be removed from main memory.

A two state process model

In this model, a process may be in one of two states: Running or Not Running. When the OS creates a new
process, it creates a process control block for the process and enters that process into the system in the Not Running
state. The process exists, is known to the OS, and is waiting for an opportunity to execute. From time to time, the
currently running process will be interrupted and the dispatcher portion of the OS will select some other process to
run. The former process moves from the Running state to the Not Running state, and one of the other processes
moves to the Running state.
A five state process model

In two state process model, if some processes in the Not Running state are ready to execute, while others
are blocked, waiting for an I/O operation to complete. Thus, using a single queue, the dispatcher could not just select
the process at the oldest end of the queue. Rather, the dispatcher would have to scan the list looking for the process
that is not blocked and that has been in the queue the longest. To handle this situation is to split the Not Running
state into two states: Ready and Blocked.

New: A process that has just been created but has not yet been admitted to the pool of executable processes by the
OS. Typically, a new process has not yet been loaded into main memory, although its process control block has been
created.
Ready: A process that is prepared to execute when given the opportunity.
Running: The process that is currently being executed.
Blocked/Waiting: A process that cannot execute until some event occurs, such as the completion of an I/O
operation.
Exit: A process that has been released from the pool of executable processes by the OS, either because it halted or
because it aborted for some reason.

A Seven state process model

New: A process that has just been created but has not yet been admitted to the pool of executable processes by the
OS. Typically, a new process has not yet been loaded into main memory, although its process control block has been
created.
Running: The process that is currently being executed.
Ready: The process is in main memory and available for execution.
Blocked: The process is in main memory and awaiting an event.
Blocked/Suspend: The process is in secondary memory and awaiting an event.
Ready/Suspend: The process is in secondary memory but is available for execution as soon as it is loaded into main
memory.
Exit: A process that has been released from the pool of executable processes by the OS, either because it halted or
because it aborted for some reason.
Blocked to Blocked/Suspend: If there are no ready processes, then at least one blocked process is swapped out to
make room for another process that is not blocked. This transition can be made even if there are ready processes
available, if the OS determines that the currently running process or a ready process that it would like to dispatch
requires more main memory to maintain adequate performance.

Blocked/Suspend to Ready/Suspend: A process in the Blocked/Suspend state is moved to the Ready/Suspend state
when the event for which it has been waiting occurs. Note that this requires that the state information concerning
suspended processes must be accessible to the OS.

Ready/Suspend to Ready: When there are no ready processes in main memory, the OS will need to bring one in to
continue execution. In addition, it might be the case that a process in the Ready/Suspend state has higher priority
than any of the processes in the Ready state. In that case, the OS designer may dictate that it is more important to get
at the higher-priority process than to minimize swapping.

Ready to Ready/Suspend: Normally, the OS would prefer to suspend a blocked process rather than a ready one,
because the ready process can now be executed, whereas the blocked process is taking up main memory space and
cannot be executed. However, it may be necessary to suspend a ready process if that is the only way to free up a
sufficiently large block of main memory. Also, the OS may choose to suspend a lower-priority ready process rather
than a higher priority blocked process if it believes that the blocked process will be ready soon. Several other
transitions that are worth considering are the following:

New to Ready/Suspend and New to Ready: When a new process is created, it can either be added to the Ready
queue or the Ready/Suspend queue. In either case, the OS must create a process control block and allocate an
address space to the process. It might be preferable for the OS to perform these housekeeping duties at an early time,
so that it can maintain a large pool of processes that are not blocked. With this strategy, there would often be
insufficient room in main memory for a new process; hence the use of the (New SReady/Suspend) transition. On the
other hand, we could argue that a just-in-time philosophy of creating processes as late as possible reduces OS
overhead and allows that OS to perform the process-creation duties at a time when the system is clogged with
blocked processes anyway.

Blocked/Suspend to Blocked: Inclusion of this transition may seem to be poor design. After all, if a process is not
ready to execute and is not already in main memory, what is the point of bringing it in? But consider the following
scenario: A process terminates, freeing up some main memory. There is a process in the (Blocked/Suspend) queue
with a higher priority than any of the processes in the (Ready/Suspend) queue and the OS has reason to believe that
the blocking event for that process will occur soon. Under these circumstances, it would seem reasonable to bring a
blocked process into main memory in preference to a ready process.

Running to Ready/Suspend: Normally, a running process is moved to the Ready state when its time allocation
expires. If, however, the OS is preempting the process because a higher-priority process on the Blocked/Suspend
queue has just become unblocked, the OS could move the running process directly to the (Ready/Suspend) queue
and free some main memory.

Any State to Exit: Typically, a process terminates while it is running, either because it has completed or because of
some fatal fault condition. However, in some operating systems, a process may be terminated by the process that
created it or when the parent process is itself terminated. If this is allowed, then a process in any state can be moved
to the exit state.

Reasons for process creation

A process is created in response to the submission of a job.

A process is created when a new user attempts to log on.
An OS may also create a process on behalf of an application.
OS created all processes in a way that was transparent to the user or application program
OS creates a process at the explicit request of another process, the action is referred to as process spawning. When
one process spawns another, the former is referred to as the parent process, and the spawned process is referred to
as the child process.

Reasons for process termination

Reasons for process suspension

Other reasons

1. The process is not immediately available for execution.

2. The process may or may not be waiting on an event. If it is, this blocked condition is independent
of the suspend condition, and occurrence of the blocking event does not enable the process to be
executed immediately.
3. The process was placed in a suspended state by an agent: either itself, a parent process, or the OS,
for the purpose of preventing its execution.
4. The process may not be removed from this state until the agent explicitly orders the removal.

Typical Elements of Process Image

Collection of program, data, stacks, and attributes as the process image. The location of a process image
will depend on the memory management scheme being used. The process image is maintained as a contiguous, or
continuous, block of memory. This block is maintained in secondary memory, usually disk.
To execute the process, the entire process image must be loaded into main memory or at least virtual
memory. when a process is swapped out, part of the process image may remain in main memory. Thus, the OS must
keep track of which portions of the image of each process are still in main memory.

Elements of Process Image

1. User Data
The modifiable part of the user space. May include program data, a user stack area, and programs
that may be modified.
2. User Program
The program to be executed
3. Stack
Each process has one or more last-in-first-out (LIFO) stacks associated with it. A stack is used to
store parameters and calling addresses for procedure and system calls.
4. Process Control Block
Data needed by the OS to control the process

Modes of Execution

Kernel Mode: The kernel is the "core" of any computer system. In Kernel mode, the executing code has complete
and unrestricted access to the underlying hardware. It can execute any CPU instruction and reference any memory
address. Kernel mode is generally reserved for the lowest-level, most trusted functions of the operating system.
Kernel Mode functions:
Memory Management
Process Management
I/O Management

User Mode: In User mode, the executing code has no ability to directly access hardware or reference memory.
Users can run applications.

Process Creation:
When OS decides to create a new process, it follows the following procedure

1. Assign a unique process identifier to the new process

A new entry will be added to primary process table.
2. Allocate space for the process
This includes all elements of process image. OS must know how much space is need for
the user private space and user stack. If any existing address space is to be shared by this
new process then appropriate linkage must be set up.
3. Initialize the process control block
4. Set the appropriate linkage
5. Create or expand other data structure

Process Switching

When a running process is interrupted and the OS assigns another process to the running state and turns
control over to that process. A process switch may occur any time when OS gained control over the currently
running process. When following events occur, OS may get control over the processes.
1. Interrupt
2. Trap
3. Supervisor call

Processor Scheduling

There are three types of scheduling

1. Long term scheduling: Long-term scheduling is performed when a new process is created. This is a
decision whether to add a new process to the set of processes that are currently active. A long-term
scheduler determines which programs are admitted to the system for processing. It is also called a job
scheduler.
2. Short term scheduling: Short-term scheduling is the actual decision of which ready process to execute next.
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. It is also called a CPU scheduler.
3. Medium term scheduling: Medium-term scheduling is a part of swapping. It removes the processes from
the memory. The medium-term scheduler is in-charge of handling the swapped out-processes.

Scheduling Criteria:

CPU utilization – keep the CPU as busy as possible

Throughput – number of processes that complete their execution per time unit .
Turnaround time – amount of time to execute a particular process
Waiting time – amount of time a process has been waiting in the ready queue
Response time – amount of time it takes from when a request was submitted until the first response is produced, not
output (for time-sharing environment)

Scheduling Algorithms

Non preemptive algorithm: In non preemptive algorithms, once the process enters the running state, it can not be
preempted until it completes its allotted time.

Preemptive algorithm: In preemptive algorithms, scheduler may preempt a low priority running process any time
when a high priority process enters into a ready state.

FCFS(First Come First Serve) Algorithm

 Jobs are executed on first come, first serve basis.

 It is a non preemptive scheduling
 Easy to understand and implement.
 Poor in performance as average wait time is high.
Process TAT=WT+BT
P1 0+21
P2 21+3
P3 24+6
P4 30+2
The average TAT is (21+24+30+32)/4= 26.75

SJF(shortest job first) Scheduling

 Jobs with least burst time will execute first

 It is a non preemptive scheduling
 Best approach to minimize waiting time.
 Actual time taken by the process is already known to processor.
Process TAT=WT+BT
P1 11+21
P2 2+3
P3 5+6
P4 0+2

Average TAT is (32+5+11+2)/4=12.5

RR(Round Robin ) Scheduling

 A fixed time is allotted to each process, called quantum, for execution.

 It is a preemptive scheduling
 Once a process is executed for given time period that process is preempted and other process executes for given
time period.

Quantum is 5

Process TAT=WT+BT
P1 0+(15-5)+(21-20)+(21-21)+(26-26)
P2 5
P3 8+(20-13)
P4 13

Average TAT:
Priority Scheduling:

Priority scheduling is a method of scheduling processes based on priority. In this each process is
assigned with some priority. The scheduler chooses the tasks to work as per the priority. Processes with
higher priorities are carried out first. It is often possible that a priority scheduling algorithm can make a
low-priority process wait indefinitely.

Process Burst time Priority

P1 6 3

P2 2 2

P3 14 1

P4 6 4

P3 P2 P1 P4

0 14 16 22 28

Process W.T TAT

P1 16 22

P2 14 16

P3 0 14

P4 22 28

Average W.T : 13

Average T.A.T : 20

SRT (Shortest Remaining Time ) Algorithm

SRT is preemptive version of SJF. The scheduler always chooses the process that has the shortest expected
remaining processing time. When a new process joins the ready queue, it may in fact have a shorter remaining
time than the currently running process. The scheduler may preempt the current process when a new process
becomes ready. It gives more TAT performance compared to SJF. There may be chance of starvation.

Highest Response Ratio Next (HRRN)

In HRRN, we have to calculate a response ratio (R) for each process. Response ratio is ratio of turnaround

time and service time.

R= (W+S)/S

R=response ratio

W= waiting time

S= service time

When current process completes, the scheduler choose the ready process with the highest response ratio

value. The minimum R value is 1, which occurs when a process first enters into the system. HRRN is

suitable for both short job processes and highest waiting time processes.

Process Synchronization

Concurrency:

The execution of two or more processes simultaneously.

Concurrency arises in

Multi programming: Management of multiple processes within a uniprocessor system.

Mutliprocessing: Management of multiple processes with in a multiprocessor.

Distributed processing: Management of multiple processes executing on multiple distributed

computer systems.

Difficulties that arise in concurrent situations

1. Sharing of global resources(variables)
2. Difficult to share or management of resource allocation
3. Difficult to locating programming errors

Shared resources are loaded into a portion of memory global to all applications. The sharing of
main memory among the processes is useful to permit efficient and close interaction among the
processes. Such sharing can lead to problems.
Ex:

Void echo()
{
Chin = getchar();
Chout=chiin;
Putchar(chout);
}

1. Process P1 invokes the echo procedure and is interrupted immediately after

getchar returns its value and stores it in chin. At this point, the most recently
entered character, x, is stored in variable chin.
2. Process P2 is activated and invokes the echo procedure, which runs to conclusion,
inputting and then displaying a single character, y, on the screen.
3. Process P1 is resumed. By this time, the value x has been overwritten in chin
and therefore lost. Instead, chin contains y, which is transferred to chout
and displayed.

Process P1 Process P2

Echo()

Chin =getchar()(Some Input “x”)

- Echo()
- Chin=getchar();(some input “Y”)
- Chout=chin;
- Putchar(chout) (output is “Y”)
Putchar(chout)(output is “Y”)

Both outputs will be same.

This problem can be caused because two processes may be executing simultaneously and both
trying to access the same global variable(resource). The solution for this problem is control
access to the shared resources

Principles of Concurrency Control

Race condition
Operating System Concerns
Process Interaction

Race condition occurs when multiple processes are in race of accessing the shared data items
and the final result depends on the loser of race or order of execution of instructions.

Ex1:

P1 and P2 are two processes share a global variable “a”

At some point p1 updates the variable to the value 1
After some point in its execution, p2 updates the value to 2
Now the two processes are in race prints the value of a
In this case, the loser of the race(the process that updates last) determines the final value.

Ex 2:

P3,P4 sharing the global variables b and c with initial values 1 and 2 respectively

At some point of its execution p3 executes the assignment b=b+c

At some point of its execution p4 executes the assignment c=b+c

Though the two processes updates different values, the final values depends on the order in
which the two processes are execute these tow assignments.

If P3 first, then b=3 and c=5

If P4 first, then b=4 and c=3

Operating System concerns

1. The OS should keep track of various active processes.

2. The OS must allocate and deallocate various resources for processes. The resources
includes
a. Processor time
b. Memory
c. Files
d. I/O Devices
3. The OS must protect the data and resources of each process from unintended
interferences by other processes.

Process Interaction

Process interaction can be classified on basis of degree of awareness.

Mutual Exclusion

It is property of concurrence control that prevents the simultaneous access to a shared resource.
We have to allow only one process to access the resource at any instant of time.

Critical Section

It is a area or a region where critical code is placed. Only one program is allowed into critical
section to access the shared resource.

Critical Resource
Which can not be shared.

Deadlock:
It is a situation or condition when two are more processes are each waiting for another to release
a resource. A deadlock will occur when a process enters into a waiting state because it requested
a resource which is hold by another waiting process.

Starvation:
It is a situation where a process waits for very long time for a resource or event to occur.

Mutual Exclusion: At any instance of time only once process is allowed into the critical section
to access shared resource.
Requirements for Mutual Exclusion
1. Only one process is allowed into the critical section
2. If any process is in its noncritical section, it should not be interfering with other processes
3. When critical section is free, if any process requesting to enter into critical section, it
should be allowed immediately.
4. No process should wait indefinite time to enter into critical section.
5. A process should remains inside the critical section only for the finite time.

.
Mutual Exclusion: Hardware approaches

i. Interrupt disabling
In a uniprocessor system, the fundamental reason of concurrency is that the
processor may dispatch different processes to run from time to time.
And the switching of control happens due to some kind of interrupt, such as
timeout interrupt in a time-sharing environment, I/O operation completion
interrupt, etc. Based on this observation, if we could in some way avoid
concurrency while the execution of critical sections is in progress, the mutual
exclusion problem will then be solved naturally. Hence we obtain a hardware-
based solution as below:
while (true)
{
/* disable interrupts */
/* critical section */
/* enable interrupts */
/* remainder */
}

However this approach also eliminates the concurrency between irrelevant

processes and thus the efficiency could be noticeably degraded. A second problem
is that this approach does not work in a multiprocessor architecture.

ii. Special Machine Instruction

In a multiprocessor environment, the interrupt disabling approach does not

work any more; however it is assumed that the processors share access to a
common main memory and at the hardware level, only one access to a memory
location is permitted at a time. With this as a foundation, some computer
processors designed several machine instructions that carry out two actions, such
as reading and writing, of a single memory location. Since processes interleave at
the instruction level, so such special instructions are atomic and are not subject to
interference from other processes. Two of such kind of instructions are discussed
in the following
A. Compare and swap instruction (Test and Set instruction)

This is also called as compare and exchange instruction.

int compare_and_swap (int *word, int testval, int newval)

{
int oldval;
oldval = *word
if (oldval == testval) *word = newval;
return oldval;
}

This version of the instruction checks a memory location (*word) against a

test value (testval). If the memory location’s current value is testval, it is replaced
with newval; otherwise it is left unchanged. The old memory value is always
returned; thus, the memory location has been updated if the returned value is the
same as the test value.

A shared variable bolt is initialized to 0. The only process that may enter its
critical section is one that finds bolt equal to 0. All other processes at enter their
critical section go into a busy waiting mode. When a process
leaves its critical section, it resets bolt to 0; at this point one and only one of the
waiting processes is granted access to its critical section. The choice of process
depends on which process happens to execute the compare&swap instruction
next.

//Mutal Exclusion by compare and swap

Const int n= some value;
Int bolt;

Int compare_and_swap(int *word,int testval,int newval)

{
Int oldval;
Oldval=*word;
If(oldval==testaval)
*word=newval;
Return oldval;
}

Void P(int i)
{
While(true)
{
While(compare_and_swap(bolt,0,1)==1)
// do nothing

/* Critical section */
Bolt=0;
}
}
Void main()
{
Bolt=0;
Parbegin(p(1),p(2)….p(n));
}

B. Exchange Instruction:

It can be defined as follows.

void exchange (int register, int memory)

{
int temp;
temp = memory;
memory = register;
register = temp;
}

In this, shared variable bolt is initialized to 0. Each process uses a local

variable key that is initialized to 1.The only process that may enter its critical
section is one that finds bolt equal to 0. It excludes all other processes from the
critical section by setting bolt to 1.When a process leaves its critical section, it
resets bolt to 0, allowing another process to gain access to its critical section.
.

// Mutual Exclusion by Exchange instruction

Int const n=number of processes

Int bolt;

void exchange (int register, int memory)

{
int temp;
temp = memory;
memory = register;
register = temp;
}
Void p(int i)
{
Int keyi=1;
While(true)
{
Do
exchange(keyi,bolt)
While(keyi!=0);
//critical section
Bolt=0;
}
}
Void main()
{
Bolt=0;
Parbegin(p(1),p(2)….p(n));
}

Advantage of Machine Instruction approach

• It is applicable to any number of processes on either a single processor or multiple

processors sharing main memory.
• It is simple and therefore easy to verify.
• It can be used to support multiple critical sections; each critical section can be
defined by its own variable.

Disadvantages of Machine Instruction approach

• Busy waiting: If a process is waiting for access to a critical

section, it continues to consume processor time.
• Starvation is possible. When a process leaves a critical section and more than
one process is waiting, the selection of a waiting process is arbitrary. Thus,
some process could indefinitely be denied access.
• Deadlock is possible.
Process P1 executes the special instruction (e.g., compare&swap,
exchange) and enters its critical section. P1 is then interrupted to give the
processor to P2, which has higher priority. If P2 now attempts to use the
same resource as P1, it will be denied access because of the mutual exclusion
mechanism. Thus it will go into a busy waiting loop. However, P1 will never
be dispatched because it is of lower priority than another ready process, P2.

Semaphores
A semaphore, in its most basic form, is a protected integer variable that can facilitate and restrict
access to shared resources in a multi-processing environment.

A semaphore is hardware or a software tag variable whose value indicates the status of a
common resource. Its purpose is to lock the resource being used. A process which needs the
resource will check the semaphore for determining the status of the resource followed by the
decision for proceeding. In multitasking operating systems, the activities are synchronized by
using the semaphore techniques.

The two most common kinds of semaphores are

Binary semaphores

- Binary semaphores can take only 2 values (0/1). They are used to acquire locks. When a resource is
available, the process in charge set the semaphore to 1 else 0.

Counting semaphores(General semaphore)

- Counting Semaphore may have value to be greater than one, typically used to allocate resources
from a pool of identical resources

Two Basic operations of Semaphores

Wait(): If any process wants to access resource (If process enters into a critical section), it calls wait()
Signal(): If any process leaves the critical section , it calls the signal().

Three basic operations that we can perform on a counting semaphore are

1. Init(): a semaphore can be initialized to a nonnegative integer value.

2. semWait(): It is called when a process wants access to a resource. This operation decrements
the semaphore vaule. If the value becomes negative, then the process executing the wait() is
blocked. Otherwise the process continues execution.
3. semSignal(): It is called when a process is done using a resource. This operation increments the
semaphore value.

Struct semaphore
{
Int count;
queueType queue;
};
Void semWait(semaphore s)
{
s.count--;
if(s.count<0)
{
//place this process in s.queue
//block this process
}
}
Void semSignal(semaphore s)
{
s.count++;
if(s.count<=0)
{
//remove a process from s.queue
//place the process on ready list
}
}
Void Init(semaphore s, int v)
{
s.count=v;
}

Basic operation that we can perform on Binary Semaphore

1. A binary semaphore may be initialized to 0 or 1

2. semWaitB(): this operation checks the semaphore value.If the value is 0 then the process
executing the semWaitB() is blocked. If the value is 1 then the value is changed to 0 and
the process continues execution.
3. semSignalB(): this operation checks to see if any processes are blocked on this
semaphore. If so, then a process blocked by a semWaitB operation is unblocked. If no
processes are blocked, then the value of the semaphore is set to 1.

Struct binary_semaphore
{
Enum{zero, one} value;
queueType queue;
};
Void semWaitB(binary_semaphore s)
{
If(s.value==one)
s.value=zero
else
{
//place this process in s.queue
//block this process
}
}
Void semSignalB(binary_semaphore s)
{
If(s.queue is empty())
s.value=1;
else
{
//remove a process from s.queue
//place process on ready list
}

Sample program for mutual exclusion using semaphore

Const n= some value

Semaphore s=1;
Void p(int i)
{
While(true)
{
semWait(s);
//Enters into critical section
semSignal(s);
//remainder
}
}

Void main()
{
Parbegin (p(1),p(2),…..p(n));
}

Tracing of General Semaphore

Tracing of Binary Semaphore
Mutex(Mutual Exclusion):

It is a concept related to binary semaphore. The key difference between binary semaphore and
mutex is; in mutex, the process that locks(sets value to 0) the mutex must be the one to
unlock(sets the value to 1) it. Where as in binary semaphore, it is possible for one process to lock
and another process the unlock the semaphore value.

Strong Semaphore and weak semaphore

A queue is used in every semaphore to hold the waiting processes. When a signal() operation is
performed, a blocked/waiting process which is waiting in the queue removed based FIFO policy.
The semaphore whose definition includes this kind of policy is called as strong semaphore.
Semaphores that does not specify the order in which the processes are removed from the queue is
a weak semaphore.
Producer and Consumer Problem

The problem describes two processes, the producer and the consumer, who share a
common, buffer used as a queue. The producer's job is to generate data, put it into the buffer, and
start again. At the same time, the consumer is consuming the data (i.e., removing it from the
buffer), one piece at a time. The problem is to make sure that the producer won't try to add data
into the buffer if it's full and that the consumer won't try to remove data from an empty buffer.

Producer Consumer
Buffer
1. If there is no space to add items(i.e Buffer is full) then producer will blocked
2. If there is a space to add item, producer is unblocked
3. If there is no item in buffer, consumer blocked
4. If there is a item, consumer unblocked.

There are two types of Buffers

1. Infinite Buffer
In this, the buffer size is not fixed. Following are the definitions of producer and
consumer

Producer:

while(true)
{
//produce item v
buffer[in]=v
in++
}

Consumer:

while(true)
{
while(in<=out)
//do nothing
w=buffer[out];
out++;
//consume item w
}

Solution to infinite buffer producer consumer problem using semaphore

semaphore n=0,s=1;
void producer()
{
while(true)
{
produce();
semwait(s);
append();
semsignal(s);
semsignal(n);
}
}
void consumer()
{
while(ture)
{
semwait(n);
semwait(s);
take();
semsignal(s);
consume();
}
}
void main()
{
parbegin(producer,consumer);
}

Ex: sequence: PCPPCC

N=0 S=1
1 0 producer
1
_________________________________
0 0 consumer
1
__________________________________
1 0 producer
1
__________________________________
2 0 producer
1
___________________________________
1 0 consumer
1
___________________________________
0 0 consumer
1
___________________________________

2. Bounded Buffer:

Here the buffer size is fixed. The buffer treated as circular storage.

Assume, in=0, out=0, e=buffer size

Now following are the producer and consumer functions

Producer:

while(true)
{
//produce an item v
while((in+1)%e==out)
//do nothing
b[in]=v;
in =(in+1)%e;
}

Consumer:

while(true)
{
while(in==out)
//do nothing
w=b[out];
out=(out+1)%e;
//consume item w;
}

Solution to the bounded buffer producer and consumer problem using semaphore
semaphore s=1,n=0,e=buffersize;
void producer()
{
while(true)
{
producer();
semwait(e);
semwait(s);
append();
semsignal(s);
semsignal(n);
}
}

void consumer()
{
while(true)
{
semwait(n);
semwait(s);
take();
semsignal(s);
semsignal(e);
consume();
}
}
void main()
{
parbegin(producer, consumer);
}

Monitors

A monitor is a software module consisting of one or more procedures, an initialization

sequence, and local data.

Characteristics of Monitors
1. The local data variables are accessible only by the monitor’s procedures and
not by any external procedure
2. A process enters the monitor by invoking one of its procedures.
3. Only one process may be executing in the monitor at a time; any other processes
that have invoked the monitor are blocked, waiting for the monitor to become
available.

Monitors supports synchronization with help of conditional variables.

Conditional variables are special data type variables which operated on by two functions

1. cwait(c): Which suspend the execution of a process on the given condition c.

2. csignal(c): Which resumes the execution of blocked process which is blocked by cwait(c) on the
same condition.

Structure of Monitor

Bounded Buffer Producer Consumer problem with Monitor

/*program producer consumer problem*/

Monitor boundedbuffer;
Char buffer[n];
Int nextin=0,nextout=0,count=0;
Cond notFull, notEmpty;
Void append(char x)
{
If(count==n)
Cwait(notFull)
Buffer[nextin]=x;
Count++;
Csignal(nonempty);
}
Void take(char x)
{
If(count==0)
Cwait(notEmpty);
X=buffer[nextout];
Count--;
Csignal(notfull);
}
Void producer()
{
Char x;
While(true)
{
Produce(x);
Append(x);
}
}

Void consumer()
{
Char x;
While(true)
{
Take(x)/remove(x);
Consume(x);
}
}

Void main()
{
Parbegin(producer, consumer);
}

A producer can add characters to the buffer only by using the procedure append inside the monitor; the
producer does not have direct access to buffer. The procedure first checks the condition notfull to
determine if there is space available in the buffer. If not, the process executing the monitor is blocked on
that condition.

Similarly, a consumer can take a character from the buffer using the procedure . Consumer first checks
the condition notempty to determine if there is a character available in the buffer. If not, the process is
blocked on that condition.

Message Passing

Message passing is an approach which provides synchronization and communication. Synchronization

needed to enforce mutual exclusion; communication is needed to exchange the information among the
processes.
The actual functioning of message passing is normally provided in the form of a pair of primitives
Send(destination,message)
Receive(source,message)

Design characteristics of message passing

1. Synchronization
2. Addressing
3. Message format
4. Queuing discipline
Synchronization
The communication of message between two processes implies some kind of synchronization
between the processes. If there is no synchronization among the processes, it may lead to unexpected
things to happen.

Suppose, if a send primitive is executed in a process, there are two possibilities;

i. sending process is blocked until the message is received (till a receiving process
arrives)
ii. it may continue its execution if there is a receiving process.
Similarly, when a process performs receive primitive, there are two possibilities;
i. if a message has previously been sent, the message receive and execution continues
ii. if there is no waiting message, either the process is blocked until a message arrives
or process continues to execute, stopping the attempt to receive.

Both send and receive primitives have blocking and nonblocking states. There three main combinations
are there on these states.
1. Blocking send, blocking receive: Here, both sender and receiver are blocked until the message is
delivered. This combination allows tight synchronization between processes.
2. Nonblocking send, blocking receive: Here, the receiver is blocked until the message is
delivered, the sender may continue its execution after send performing send primitive. It allows a
process to send one or more messages to a variety of destinations.
3. Nonblocking send, nonblocking receive: Here, neither sender or receiver is required to wait.

Addressing

Addressing refers to specifying the destination and sources addresses in the send and receive primitives.
There are two types of addressing, direct and indirect addressing.

Direct Addressing:
In this the processes must know addresses of source and destination ahead. Sender must specify the
destination address in the send primitive, the receiver must specify the source address in the receive
primitive.

Indirect Addressing:
In this, messages are not sent directly from sender to receiver but rather they are sent to a mailbox. A
mailbox is a shared data structure which can hold messages. When two processes communicate, one
process sends a message to the appropriate mailbox and the other process pricks up the message from the
same mail box.

The relationship between the sender and receiver can be one-to-one, many-to-one,one-to-many or many-
to-many.

One-to-one relationship: It allows private communication between two processes.

Many-to-one relationship: it is useful for client server interaction; one process provides service to a
number of other processes. In this case, mailbox is often referred as a port.
One-to-many relationship: it allows for on sender and multiple receivers; it is useful for applications
where a message or some information is to be broadcast to set of processes.

Many-to-many relationship: it allows multiple server processes to provide concurrent service to multiple
clients.

Mailboxes Types:

Mailboxes are two types, static and dynamic

Static mailbox: It is defined only for one send and one receiver.
Dynamic mailbox: Here, there are many senders and many receivers.
Ownership of the mailbox:

Mailboxes can be created by the user or OS

If a process creates a mailbox then process is the owner. When the process is destroyed, the mailbox is
also destroyed.
If OS creates a mailbox then OS is the owner. Mailbox owned by OS can be destroyed by using explicit
commands.

Message Format:
It is divided into two parts: a header and a body. Header contains information about the message like
message type, destination id and source id. It may also contain some control information. Body contains
the actual contents of the message.

Queuing Discipline:
It specifies the order in which the messages have to deliver. It follows FIFO manner, but it may not be
sufficient if some messages are more urgent than others. In this case, we may specify the message
priority. Priority may be given based on message type or destination by the sender.

Mutual Exclusion using Message Passing

In this, there will be one mailbox “box”, which can be used by all processes to send and receive messages.
The mailbox is initialized with null message. If any process wants enter critical section first attempts to
receive a message. If the mail box is empty then the process is blocked. Once a process has acquired the
message, it performs its critical section and then places the message back to the mailbox.

/*Mutual Exclusion Program*/

const int n=//number of processes
void P(int i)
{
Message msg;
While(true)
{
receive(box,msg);
//critical section;
Send(box,msg);
//remainder
}
}
Void main()
{
create mailbox box;
send(box,null);
parbegin(P(1),P(2)….p(n));
}

Solution to the Bounded Buffer Producer/Consumer Problem using Message Passing

Here, there are two mailboxes produce and consume. When a producer generates data, it is sent as
messages to the mailbox consume. As long as there is at least one message in that mail box, the consumer
can consume. consume mailbox serves as a buffer. The size of the buffer is determined by the global
variable capacity. The mailbox produce is filled with number of null messages equal to the capacity of the
buffer. The number of messages in produce decreases with each production and increases with each
consumption.

const int capacity=//buffering capacity

int i;
void producer()
{
message msg;
while(true)
{
receive(produce,pmsg);
pmsg=produce();
send(consume,pmsg);
}
}
void conumer()
{
message cmsg;
while(true)
{
receive(consume,cmsg);
consume(cmsg);
send(produce,null);
}
}
void main()
{
create_mailbox produce,consume;
for(i=1;i<=capacity;i++)
send(produce,null);
parbegin(producer,consumer);
}

Readers/Writers Problem:

The readers/writers problem is defined as follows:

There is a data area shared among a number of processes. The data area could be
a file, a block of main memory, or even a bank of processor registers. There are a number of processes
that only read the data area (readers) and a number that only write to the data area (writers).

The conditions that must be satisfied are as follows:

1. Any number of readers may simultaneously read the file.
2. Only one writer at a time may write to the file.
3. If a writer is writing to the file, no reader may read it.

Readers have priority:

Once readers have gained control, a flow of reader processes could starve the
writer processes. Rather has the case that when a write needs access, then hold up subsequent reading
requests until after the writing is done. Following is solution using semaphore

int readcount = 0;
semaphore wsem = 1; //
semaphore x = 1; //
void main(){
int p = fork();
if(p) reader; // assume multiple instances
else writer; // assume multiple instances
}

void reader(){
while(1){
wait(x);
readcount++;
if (readcount==1)
wait(wsem);
signal(x);
doReading();
wait(x);
readcount--;
if (readcount==0)
signal(wsem);
signal(x);
}
}

void writer(){
while(1){
wait(wsem)
doWriting();
signal(wsem)
}
}

Writers have priority:

In this no new readers are allowed accessto the data area once at least one writer
has declared a desire to write. For writers, the following semaphores and variables are added to the ones
already defined:
• A semaphore rsem that inhibits all readers while there is at least one writer desiring access to the data
area
• A variable writecount that controls the setting of rsem
• A semaphore y that controls the updating of writecount
For readers, one additional semaphore is needed.A long queue must not be
allowed to build up on rsem; otherwise writers will not be able to jump the queue. Therefore, only one
reader is allowed to queue on rsem, with any additional readers queuing on semaphore z, immediately
before waiting on rsem.

int readcount, writecount = 0;

semaphore rsem, wsem = 1; //
semaphore x,y,z = 1; //
void main(){
int p = fork();
if(p) reader; // assume multiple instances
else writer; // assume multiple instances
}

void reader(){
while(1){
wait(z);
wait(rsem);
wait(x);
readcount++;
if (readcount==1)
wait(wsem);
signal(x);
signal(rsem);
signal(z);
doReading();
wait(x);
readcount--;
if (readcount==0)
signal(wsem);
signal(x);
}
}

void writer(){
while(1){
wait(y);
writecount++;
if (writecount==1)
wait(rsem);
signal(y);
wait(wsem);
doWriting();
signal(wsem);
wait(y);
writecount--;
if (writecount==0)
signal(rsem);
signal(y);
}
}

Solution to Readers/writers problem using message passing:

An alternative solution, which gives writers priority and which is implemented using message passing. In
this case, there is a controller process that has access to the shared data area. Other processes wishing to
access the data area send a request message to the controller, are granted access with an “OK” reply
message, and indicate completion of access with a “finished” message. The controller is equipped with
three mailboxes, one for each type of message that it may receive.
The controller process services write request messages before read request messages to give writers
priority. In addition, mutual exclusion must be enforced.

To do this the variable count is used, which is initialized to some number greater than the maximum
possible number of readers. In this example, we use a value of 100.The action of the controller can be
summarized as follows:
• If count _ 0, then no writer is waiting and there may or may not be readers active. Service all “finished”
messages first to clear active readers. Then service write requests and then read requests.
• If count _ 0, then the only request outstanding is a write request. Allow the writer to proceed and wait
for a “finished” message.
• If count _ 0, then a writer has made a request and is being made to wait to clear all active readers.
Therefore, only “finished” messages should be serviced.

void reader(int id){

message rmsg;
while(1){
rmsg = id;
send("ReadReq",rmsg);
receive("Reader"+id,rmsg);
DoReading();
rmsg = id;
send("Fini",rmsg);
}
}
void writer(int id){
message rmsg;
while(1){
rmsg = id;
send("WriteReq",rmsg);
receive("Writer"+id,rmsg);
DoWriting();
rmsg = id;
send("Fini",rmsg);
}
}
void controller(){
while(1){
if(count>0){ //no writer
if (!empty("Fini")){
receive("Fini",msg);
count++;
} else if(!empty("WriteReq")){
receive("WriteReq",msg);
id = msg.id;
count -= MAXREADERS;
} else if(!empty("ReadReq")){
receive("ReadReq",msg)
count--;
send("Reader"+msg.id, "OK");
}
}
if(count==0){//only a writer
send("Writer"+id, "OK");
receive("Fini",msg);
count = MAXREADERS;
}
while(count<0){ // 1 wrtr;n rdrs
receive("Fini",msg);
count++;
}
}
}

DeadLock:

Deadlock is a situation which occurs when a waiting process requests a resource, which is held by another
waiting process. If deadlock occurs, a set of processes may permanently blocked.

Necessary conditions to occur deadlock

1. Mutual Exclusion: At least one resource must be held in a non-sharable mode; that is, only one
process at a time can use the resource. If another process requests that resource, the requesting
process must be delayed until the resource has been released.
2. Hold and Wait: A process must be holding at least one resource and waiting to acquire additional
resources that are currently being held by other processes.
3. No Preemption: Resources cannot be preempted; that is, a resource can be released only voluntarily
by the process holding it, after that process has completed its task.
4. Circular Wait: A set {P0, P1, ..., Pn) of waiting processes must exist such that Po is waiting for a
resource that is held by PI, PI is waiting for a resource that is held by P2, ..., Pn-1 is waiting for a
resource that is held by Pn and Pn is waiting for a resource that is held by P0.

Resources:

There are two types of resources, usable resources and consumable resources.

Usable resources:

Usable resource is one that can be used by one process at a time. These can not be created or destroyed. These
are fixed in size. A resource can be reused when it released by the process.
Ex: memory, secondary memory, files, data structures.

Deadlock with usable resource

Ex: Two processes P and Q are trying to access the resources R1 and R2. Following are the sequence
operation instructions performed by P and Q process.
P0: Request (R1) Q0: Request (R2)
P1: Lock(R1) Q0: Lock(R2)
P2: Request (R2) Q2: Request (R1)
P3: Lock(R2) Q3: Lock(R1)
P4: Perform operatons Q4: Perform operatons
P5: Unlock(R1) Q5: Unlock(R2)
P6: Unlock(R2) Q6: Unlock(R1)

Deadlock will occur if the instructions are executed in the following order
P0,P1,Q0,Q1,P2,Q2

Consumable Resources

Consumable resource is one that can be created and destroyed. There is no limit on the number of consumable
resources. Ex. Interrupts, signals, messages.

Deadlock with consumable resource

A pair of processes P1 and P2, each process attempts to receive a message from another process and then send
message to the other process.

P1 P2
-- --
receive(P2) receive(P1)
-- --
send(P2,M1) send(P1,M2)

Deadlock will occur if the receiving process is blocked until the message is received.

Resource Allocation Graph:

A resource allocation graph is directed graph, which specifies which resource is held by which process and
which process requests what resource.

A directed edge (Request Edge) from a process to resource represents, process is requesting for the resource.
A directed edge (Assignment Edge) from a resource to process represents, resource is allotted to the process.
A dot in the resource represents an instance.

Methods for Handling Deadlocks

Deadlock Preemption
We can preempt occurrence of a deadlock by ensuring that at least one of the deadlock occurrence conditions
can not hold.

Mutual Exclusion: Sharable resources do not require mutual exclusive access and does not involved in
deadlocks. Only non sharable resources require mutual exclusive access. Deadlocks can be preempted by
denying the mutual exclusive condition.
Hold and Wait: To ensure hold and wait condition never occurs in the system, we must guarantee that
whenever a process requests for a resource, it does not hold any resource. All requested resources must allocate
to process before it begins execution. It has two disadvantages; one is low resource utilization and starvation.
No Preemption: If a process that is holding some resources and requesting another resource that can not be
immediately granted until currently allocated resources are preempted. The preempted resources are added to
the list of resources for which the process is waiting. Process will be restarted only when it regain its all
resources (old and new).
Circular Wait: One way to ensure that this condition never holds is to impose a total ordering of all resource
types, and to require that each process requests resources in an increasing order of enumeration.

Deadlock Avoidance:

The deadlock avoidance algorithm dynamically examines the resource allocation state to ensure that
there can never be a circular wait condition. The resource-allocation state is defined by the number of available
and allocated resources, and the maximum demands of the processes.

Safe state algorithm:

A state is safe if the system can allocate resources to each process in some order to avoid a deadlock.
When a process requests an available resource, system must decide if immediate allocation keeps the system in
a safe state. A system is in a safe state only if there exists a safe sequence.
Sequence of processes <PI, P2, ..., Pn,> is a safe sequence , the resources that Pi can still request can
be satisfied by the currently available resources plus the resources held by all the Pj, with j < i.

If process Pi requested resources are not immediately available, then Pi can wait until all Pj have finished.

When Pj is finished, Pi can obtain requested resources, execute, return allocated resources, and terminate.

When Pi terminates, Pi+1 can obtain its needed resources, and so on….

A safe state is not a deadlock state. Conversely, a deadlock state is an unsafe state. Not all unsafe states are
deadlocks. An unsafe state may lead to a deadlock. As long as the state is safe, the operating system can avoid
deadlock.

If a system is in safe state no deadlocks.

If a system is in unsafe state possibility of deadlock.
Avoidance ensure that a system will never enter an unsafe state.

Resource allocation graph algorithm

A claim edge PiRj indicates that process Pi may request resource Rj at some time in the future. This edge
resembles a request edge, but is represented by a dashed line.

When process Pi requests resource Rj, the claim edge PiRj is converted to a request edge. Similarly,
when a resource Rj is released by Pi,th e assignment edge RjPi is reconverted to a claim edge PiRj.

If no cycle exists, then the allocation of the resource will leave the system in a safe state. If a cycle is found,
then the allocation will put the system in an unsafe state.

A resource allocation graph for deadlock avoidance

An unsafe state resource allocation graph for deadlock avoidance

Banker’s Algorithm

The resource-allocation graph algorithm is not applicable to a resource allocation system with multiple
instances of each resource type. In this case banker’s algorithm will be used.

When a new process enters the system, it must declare the maximum number of instances of each resource
type that it may need.

This number may not exceed the total number of resources in the system.

When a user requests a set of resources, the system must determine whether the allocation of these resources
will leave the system in a safe state. If it will, the resources are allocated; otherwise, the process must wait until
some other process releases enough resources.

To implement banker’s algorithm, following data structures are to be maintained.

Available: A vector of length m indicates the number of available resources of each type. If Available[j] = k,
there are k instances of resource type Rj available.

Max: A nXm matrix defines the maximum demand of each process. If Max[i,j] = k, then process Pi may
request at most k instances of resource type Ri.

Allocation: An nXm matrix defines the number of resources of each type currently allocated to each process.
If Allocation[i,j] = k, then process Pi is currently allocated k instances of resource type Rj.

Need: An n x m matrix indicates the remaining resource need of each process. If Need[i,j] = k, then process
Pi may need k more instances of resource type Ri to complete its task.
Note that Need[i,j] = Max[i,j ] - Allocafion[i,j].

Safety Algorithm

1. Let Work and Finish be vectors of length m and n, respectively.

Initialize Work = Available and Finish[i] =false for i = 1,2, ..., n.

2. Find an i such that both

a. Finish[i] =false
b. Needi <=Work.

If no such i exists, go step 4

3. Work = Work + Allocationi

Finish[i] := true
go to step 2.

4. If Finish[i] = true for all i, then the system is in a safe state.

Resource Request Algorithm

Let Requesti be the request vector for process Pi. If Requesti[j] = k, then process Pi wants k instances of
resource type Rj. When a request for resources is made by process Pi, the following actions are taken

1. If Requesti <=Needi, go to step 2. Otherwise, raise an error condition, since the process has exceeded
its maximum claim.
2. If Requesti <=Available, go to step 3. Otherwise, Pi must wait, since the resources are not available.
3. Have the system pretend to have allocated the requested resources to process Pi by modifying the
state as follows

Available= Available - Requesti;

Allocationi= Allocationi+ Requesti
Needi = Needi - Requesti

If the resulting resource-allocation state is safe, the transaction is completed and process Pi is allocated its
resources. However, if the new state is unsafe, then Pi must wait for Requesti and the old resource-allocation
state is restored.

Deadlock Detection

If a system does not include deadlock preemption or deadlock avoidance algorithm, then a deadlock situation
may occur. At the stage, the system must provide two algorithms; one is to examine the state of the system
whether a deadlock has occurred, second is to recover from the deadlock

Single Instance of each Resource Type

If all resources have only a single instance, then we can define a deadlock detection algorithm using wait-for
graph. We obtain wait-for graph from the resource-allocation graph by removing the resource nodes and their
respective edges.

An edge from Pi to Pj in a wait-for graph implies that process Pi is waiting for process Pj to release a resource
that Pi needs. An edge Pi to Pj exists in a wait-for graph if and only if the corresponding resource allocation
graph contains two edges Pi to Rq and Rq to Pj for some resource Rq

If there is a cycle in the wait-for graph then deadlock occurs. To detect deadlock the system needs to maintain
the wait-for graph and periodically invoke an algorithm that searches for a cycle in the graph. This algorithm
needs O(n2) operations, where n is number of vertices in the graph.
Several Instances of a Resource Type

The wait-for graph technique is not applicable to resource allocation system with multiple instances of each
resource type. This deadlock detection algorithm includes three data structures.

Available: A vector of length m indicates the number of available resources of each type.
Allocation: An n x m matrix defines the number of resources of each type currently allocated to each process.
Request: An n x m matrix indicates the current request of each process. If Request[i,j] = k, then process Pi is
requesting k more instances of resource type Ri.

1. Let Work and Finish be vectors of length m and n, respectively

Initialize, Work = Available
For i = 1,2, …, n,
if Allocationi ≠ 0, then Finish [i] = false;
Finish [i] = true.
2. Find an index i such that both:
Finish [i] == false
Requesti ≤ Work
If no such i exists, go to step 4.
3. Work = Work + Allocationi
Finish [i] = true
go to step 2.
4. If Finish [i] == false, for some i, 1 ≤ i ≤ n, then the system is in deadlock state.
Moreover, if Finish [i] == false, then Pi is deadlocked. Algorithm requires an order of O (m x n2) operations
to detect whether the system in deadlocked state.

Recovery from Deadlock

There are two ways to recover from the deadlock state. One is to simply terminate one or more processes to
break the circular wait. Second is to preempt some resources from one or more deadlocked processes.

Process Termination

1. Terminate all deadlocked processes: This method will break the deadlock cycle by terminating all
deadlocked processes. The partial results of these processes must be discarded.
2. Terminate one process at a time until the deadlock cycle is eliminated: In this method, processes
will be terminated one at a time, to eliminate the deadlock. When each process terminated, the
deadlock detection algorithm must be invoked to determine whether any processes are still
deadlocked.

Factors to consider while terminating a process (Cost Factors)

1. What the priority of the process

2. How long the process has computed and how much time needed to finish the remaining task.
3. How many and what type of resources that the process used.
4. How many more resources needs in order to complete

Resource preemption
We can eliminate deadlocks by using resource preemption method. In this we preempt some resources from
process and give these resources to other processes until deadlock cycle is broken.

There are three issues while dealing deadlock with resource preemption method

1. Selecting a victim: Which resources are to be preempted in order to break the cycle. We must
determine the order of preemption to minimize the cost.
2. Rollback: If we preempt a resource from a process, it can not continue with its normal execution
because it is missing some needed resources. We must restart the process in safe state, but it is
difficult to determine a safe state, so the process must rollback.
3. Starvation: while selecting a victim, there is a possibility of same process is always picked as victim.
This results that the process never completes it task, this leads to a starvation.

Dining Philosopher’s problem:

The Dining Philosophers problem is a classic synchronization problem introducing semaphores as a

conceptual synchronization mechanism.
Dining Philosophers: There is a dining room containing a circular table with five chairs. At each chair
is a plate, and between each plate is a single chopstick. In the middle of the table is a bowl of spaghetti. Near
the room are five philosophers who spend most of their time thinking, but who occasionally get hungry and
need to eat so they can think some more.
In order to eat, a philosopher must sit at the table, pick up the two chopsticks to the left and right of a plate,
then serve and eat the spaghetti on the plate.

Memory Management

Memory management is a task of dividing the main memory dynamically to accommodate multiple processes.
This task is performed by operating system. The primary operation of memory management is to bring the
process into the memory for execution.

Following are some basic terminology used in memory management.

Frame: A fixed length block of main memory

Page: A fixed length block of data that resides in secondary memory
Segment: A variable length block of data that resides in secondary memory.
Fragmentation: It refers to the condition of a disk in which files are divided into pieces scattered around the
disk. It occurs when a disk frequently creating, deleting and modifying files. Fragmentation is state where
storage space is used inefficiently, reducing the capacity and performance.
Internal fragmentation: when memory allocated to a process is larger than the requested memory, the extra
space is unused and wasted. This wasted space with the partition is called as internal fragmentation.
External fragmentation: Even though there is sufficient memory is available, but it is not contiguous; storage
is fragmented into a large number of small holes. The wasted space is not allocated to any other partition is
called as external fragmentation.
Overlaying: programs and data are organized into modules. When there is no sufficient main memory, some
modules will be loaded to main memory and some modules will kept in secondary storage. The main program
is responsible for switching these modules to main memory whenever they needed. This switching process is
known as overlaying.

Memory management requirements

1. Relocation
2. Protection
3. Sharing
4. Logical organization
5. Physical organization

Relocation:

In multiprogramming, the main memory is shared among the number of processes. We have to swap some
active processes in and out of main memory to maximize the processor utilization. Once a process is swapped
out to disk, it must be swapped back in to same memory region as before. But sometimes we may need to
relocate the process to a different memory area. OS is responsible for bringing the processes into main
memory.

Protection:

Each process should be protected against the unwanted interference by other processes. Programs in one
process should not be able to access reference memory location of another process for reading or writing
purpose without permission. Relocation requirement increases the difficulty of satisfying protection
requirement. Protection requirement must be satisfied by the processor rather than the operating system.

Sharing:

The memory management system must provide a control access to the shared areas of memory without
compromising essential protection. The protection mechanism must have the flexibility to allow several
processes to access the same portion of main memory. For example, if a number of processes are executing the
same program, it is advantageous to allow each process to access the same copy of the program rather than
having its own separate copy.

Logical Organization:

The main memory is organized as a linear or one-dimensional manner. Secondary memory is also similarly
organized. Most programs are organized into modules, some of them are modifiable and some are
unmodifiable. Following are the advantages of using modules
a. Modules can be written and compiled independently.
b. Different degrees of protection can be given to different modules
c. We can share the some desirable modules among the processes.

Physical organization:

Physical organization refers to how data and programs are stored in memories and how the flow of information
between main and secondary memory happening.
The computer memory is organized into two levels, main memory and secondary memory. Main memory
provides fast access at high cost. It is a volatile and it does not provide permanent storage. It can store
programs and data that currently in use. Secondary memory is slower and cheaper than main memory and it is
non volatile memory. It can store programs and data permanently.

Memory Partitioning

There are two different techniques are used for main memory partitioning.

1. Fixed partitioning
2. Dynamic partitioning

1. Fixed Partitioning

In fixed partitioning, the available main memory is divided into regions with fixed boundaries. It is two types
a. Equal size fixed partitioning
b. Unequal size fixed partitioning

a. Equal size fixed partitioning

In this, the main memory is divided into number of partitions with equal size. Process with size is less
than the partition size can be loaded into any available partition. If all partitions are full, then the
operating system can swap a process out and load another process.
There are two difficulties with the use of equal size fixed partitioning.
i. Process with size greater than partition size cannot be loaded into main memory. In this case,
overlying has to use to execute the process
ii. With equal size fixed partitioning main memory utilization is extremely inefficient. Suppose
there is a process with size 2MB, it must be allocated with a 8MB partition. So there is
wastage of space. This is refereed as internal fragmentation.

b. Unequal size fixed partitioning

In this, the available main memory is divided into partitions with unequal size. By using unequal size
partition, processes with large size can be accommodated without overlaying and process with small
size can be accommodated with less internal fragmentation.

Placement algorithm

It is very easy is to place a process in main memory using equal size partition. As long as there is an available
partition, a process can loaded into that partition. Because all partitions are with equal size, it does not matter
which partition is used. If all partitions are occupied with processes then one those processes must be swapped
out to make a free space for new process.

With the unequal size partitions, there are two possible methods to place a process in memory. One method is
to assign each process to the smallest partition where it will fit. In this case a scheduling queue is needed for
each partition to hold swapped out processes.

Second method is, maintain a single queue for all processes. When it is time to load a process into main
memory, then choose a partition which can accommodate the process. If all partitions are occupied then
swapping must made.
2. Dynamic partitioning

In dynamic partitioning, the partitions are of variable length and number. When a process brought into the
main memory, it is allocated exactly as much memory as it required.

Assume the main memory size is 64MB. Initially it is loaded with OS. Three different processes are
loaded in, and occupy enough space for each process. This leaves a small “hole”( hole is small memory
block that is not sufficient to accommodate a process) at the end of the memory. At some time a new
process process4 with size 8MB has arrived. The OS swaps out the process2, which leaves sufficient space
to load the new process. Because the process4 is smaller than the process2, another small hole is created.
When the process2 swapped back into the main memory, if there is no sufficient memory for process2; the
OS swaps out the process1. This procedure leads to a situation in which there are a lot of small holes in
memory. This is referred as external fragmentation.

One technique that overcomes the external fragmentation is compaction. In this, the free memory (holes) are
combined to form single block of memory that may accommodate a new process. Compaction is a time
consuming procedure and it needs a dynamic relocation capability.
Placement algorithms

When a process loaded into main memory, if there are more than one free block memory of sufficient size are
available, then the OS must decide which free block is to allocate.

There are three placement algorithms that may used to place the processes in memory.
a. Best-fit
b. First-fit
c. Next-fit
Best –fit chooses the block that is closest in size to process request. First-fit begins to scan memory from the
beginning and chooses the first available block that is large enough to accommodate the process. Next-fit
begins scan from the location of the last placement, and choose the next available block that is large enough to
accommodate the process.

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

Paging

Paging is a memory management scheme that permits the physical address of a process/program to be non-
contiguous. In paging, the process/program is divided into blocks; each block is loaded into non contiguous
blocks of the main memory. Paging avoids fragmentation problems. Following diagram illustrates paging
model.

Logical memory addresses Physical memory addresses

Page0 Frame0
P F
A Page1 Frame1
G R
Page2 Frame2
E
A
S Page3 Frame3
Page4 M
Frame4
Frame5 E
Program/Process Page0 F5
Page1 F7
Page2 F0
Page3 F6
Page4 F1

Page table Main Memory

Physical memory is broken into fixed sized blocks called as frames. Logical memory is also broken
into same sized blocks called as pages. When a process is to be executed, its pages are loaded into any
available memory frames. Page table specifies which page is loaded in which frame.
An address generated by the CPU is commonly referred to as a logical address, whereas an address
seen by the memory unit-that is, the one loaded into the memory-address register of the memory-is commonly
referred to as a physical address.

Mapping logical address to physical address (Address Translation)

Every logical address is divided into two parts; a page number (p) and page offset (d). page number is used as
an index in page table to represent the frame number. This frame number and offset defines the physical
address of the page in the main memory.

The size of the page and number of pages are represented in power of 2. Similarly size of frame and number
frames is represented in power of 2. Look at the following example
In the above example,

The size of the page 4 bytes, we can represent 4 as 2 2 . So 2 bits are sufficient to represent 4 in binary format.
Total number of pages is 4, we can represent 4 as 22 . here also 2 bits are sufficient to represent 4 in binary
format.
Total number of bits required to represent a logical address is 4bits
The size of the frame is 4, so it needs 2 bits to represent in binary format
Total number of frames is 8, so it needs 3 bits to represent in binary format
Total number of bits required to represent a physical address is 5bits
Now see how a logical address is mapped into physical address space. Lets consider first byte in 2 nd page (i.e.
1000 logical address). In “1000”, the first two bits represent the page number and next two bits represent offset
(represent which byte).

Translation Look-aside Buffer (TLB)

The TLB is associative, high speed memory. The TLB is used in the page tables. Each entry in TLB consists of
two parts a key and a value. TLB contains only a few of the page table entries. When a logical address is
generated by the CPU, its page number is presented to the TLB. If the page number is found( it is also known
as TLB hit), its frame number is immediately available and is used to access memory.

If the page number is not in the TLB (known as a TLB miss), a memory reference to the page table must be
made. When the frame number is obtained, we can use it to access memory.

The percentage of times that a particular page number is found in the TLB is called the hit ratio.

Structure of page tables

There are three different page table structures.

1. Hierarchical paging
2. Hashed page tables
3. Inverted page tables

Hierarchical paging:

If there is a large logical address space then it is difficult maintain all entries in a single page table. Suppose if
there is a 32bit logical address space and if the page size is 4KB then the page table may consists of one
million entries. In this case, we can use hierarchical paging technique.

In hierarchical paging, page table itself is divided into multiple pages.

Assume it is 32bit system; the logical address consists of 32 bits. A logical address is divided into 20bit page
number and 12 bit offset. As it is hierarchical paging, the page number further divided into 10bit page number
and 10 bit offset

P1 is an index in the outer page table and p2 is an index in the inner page table.

The address translation works from the outer page table to inner page table, so it is known as forward mapped
page table.

Hashed Page Table

Hashed page table is an approach to handle the logical address space larger than 32 bits. Each entry in hashed
page table contains a linked list of elements. Each element consists of three fields; the virtual page number, the
frame number and pointer to the next element in the linked list.

The page number in the logical address is hashed into the hash table. The page number is compared with the
virtual page number of the first element in the linked list. If there is a match the corresponding frame number is
used to form the physical address. If there is no match, match with next entries in the list.

Inverted Page Table

In inverted page table, each entry consists virtual address of the page and information about the process of the
page. The logical contains pid, page number and offset. Inverted page tables uses address space identifier(i).
This ensures the mapping of a logical page for a particular process to the corresponding physical page frame.

Segmentation

In paging, user’s view of logical memory is different from physical memory. There is a separation of user’s
view of logical memory and the actual physical memory. But segmentation supports user’s view of memory.

The logical address space is a collection of segments. Each segment has a number and length. Each segment is
of different sizes. Each logical address consists of two fields, segment number and offset with in the segment.
<segment-number,offset>

Address Translation:

1. Fetch the base address of the segment in the segmentation table by using segment number
2. Compare the offset value with the segment length, where 0<=offset<length
3. Add the offsest to the base address to get the physical address

Example:

Assume the logical address is <1,2>, so segment number is 1 and offset value 2

The base address of the segment 1 is 0x02

Offset value is less than the length of the segment 1(2<6)

Now add offset value to the base address, 0x02+20x04, which is the physical address of the given logical
address.

Demand paging:

Demand paging is a technique in which pages are brought into the main memory on demand
of the process. Demand paging is combination of both paging and swapping. When a process is ready for the
execution, instead of moving all its pages into main memory, only few pages which are necessary for the
execution are brought into the main memory to execute the process. It is difficult to implement demand paging.
Demand paging is used to implement virtual memory. Virtual memory is a space in the disk, which acts as a
main memory temporarily.

In demand paging, we use a pager. When a process swapped in for execution, instead of
swapping in a whole process, the pager brings only those necessary pages into main memory.

When CPU is trying to access a page from main memory, if that page was not found then it is known as page
fault. The missing page will bring from the backing store to continue the process execution.

Handling page faults:

1. Determine whether the reference(page) was a valid or invalid reference.

2. If it is invalid then send a trap(interrupt) to OS to check whether the page is available in the backing
store or not.
3. Find a free frame
4. Move the desired page into the new frame
5. update the page table values to indicate the page is now in the memory.
6. Restart the instruction.

Page Replacement Algorithms

When a page fault occurred, if there is no free frame then we have to replace a old page (if no free frame
available) with new page. Page replacement includes following steps

1. Find the location of the desired page on the disk

2. Find a free frame
a. If there is a free frame, use it
b. If there is no free frame, use a page replacement algorithm to select a page for replacement
c. Swap out the old page to the disk and change the page table and frame accordingly
3. Swap in the new page into the main memory
4. Restart the user process

Page replacement algorithm is a technique, which decides which page has to replace with new page. There
are three different page replacement algorithms

1. First In First Out (FIFO) page replacement algorithm

2. Optimal page replacement algorithm
3. Least Recently Used(LRU) page replacement algorithm

FIFO page replacement algorithm

It is the simplest page replacement algorithm. In FIFO replacement algorithm, each page is associated with a
time value that indicates when that page was brought into the main memory. In FIFO algorithm, the oldest
page is replaced with a new page.

Example:

Reference string: 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1

Number of frames: 3

Number of page faults is 15

If we increase the number of frames then number of page fault will decrease.
Reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 7 7 7 7 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2
frames 0 0 0 0 0 0 4 4 4 4 4 4 4 4 4 4 7 7 7
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1
y y y y n y n y n n y n n y y n n y n n
Page fault
Number of page faults is 10

Belady’s Anomaly : In some replacement algorithms, the page fault rate may increase as the number of
frames increases.

Sample Reference string to prove belady’s anomaly is 1,2,3,4,1,2,5,1,2,3,4,5

Number of frames 3

Reference String 1 2 3 4 1 2 5 1 2 3 4 5
1 1 1 4 4 4 5 5 5 5 5 5
Frames 2 2 2 1 1 1 1 1 3 3 3
3 3 3 2 2 2 2 2 4 4
Page fault y y y y y y y n n y y n

Number of page faults is 9

Now take 4 as number of frames

Reference string
1 2 3 4 1 2 5 1 2 3 4 5
Frames 1 1 1 1 1 1 5 5 5 5 4 4
2 2 2 2 2 2 1 1 1 1 5
3 3 3 3 3 3 2 2 2 2
4 4 4 4 4 4 3 3 3
Page fault y y y y n n y y y y y y

Number of page faults is 10

Hence, FIFO page replacement algorithm suffers from belady’s anomaly.

Optimal page replacement algorithm

Optimal page replacement algorithm has the lowest page fault rate of all algorithms and it is never suffers from
belady's anomaly. In optimal page replacement, page that will not be used for the longest period of time is
replaced with new page. It guarantees the lowest page fault rate for the fixed number of frames. It is difficult to
implement optimal page replacement algorithm because user has to know future data in advance.

Example:

Reference string: 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1

Number of frames: 3

Page fault rate is 9

Example 2:
Reference string: 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1

Number of frames: 4
Reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 7 7 7 7 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1
frames 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 4 4 4 4 4 4 4 4 4 4 7 7 7
Page fault 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
y y y y n y n y n n n n n y n n n y n n
Page fault rate is 8

Least Recently Used(LRU) page replacement algorithm

In LRU algorithm, each page is associated with a time value that represents page’s last use. In LRU, the page
that has not been used for the longest period of time is replaced with a new page. In LRU, the strategy is
looking backward to find a victim page.

Example 1

Reference string is 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1

Number of frames 3
Page fault rate is 12

Example 2

Reference string is 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1

Number of frames 4

Reference string
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
Frames 7 7 7 7 7 3 3 3 3 3 3 3 3 3 3 3 3 7 7 7
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 4 4 4 4 4 4 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
Page fault y y y y n y n y n n n n n y n n n y n n

Page fault rate is 8

I/O Management:

Users/programmers can interact with computer by providing information through IO devices. Management of
these devices may affect the throughput o the system. Devices communicate with computer through bit or byte
streams using a data bus or device controller. Following are some situations where IO devices are required.

a. User may give input to computer and get output from the computer
b. Device may give input to computer and get output from the computer
c. Computers to communicate over networks

The major functions of an IO module are categorized as follows.

 Control and timings

 Processor and Device Communication
 Data buffering
 Error Detection

Control and Timings

The I/O function includes a control and timing requirement to co-ordinate the flow of traffic between internal
resources and external devices. For example, the control of the transfer of data from an external device to the
processor might involve the following sequence of steps

a. The processor interacts with the I/O module to check the status of the attached device.
b. The I/O module returns the device status.
c. If the device is operational and ready to transmit, the processor requests the transfer of data, by means of a
command to the I/O module.
d. The I/O module obtains a unit of data from external device.
e. The data are transferred from the I/O module to the processor.

Processor and Device Communication

During IO operation, the IO module must communicate with the processor and with the external device.
Processor communication involves the following

Command decoding:
The I/O module accepts command from the processor, typically sent as signals on control bus.
Data:
Data are exchanged between the processor and the I/O module over the data bus.
Status Reporting:
Because peripherals are so slow, it is important to know the status of the I/O module. For example, if
an I/O module is asked to send data to the processor(read), it may not be ready to do so because it is still
working on the previous I/O command. This fact can be reported with a status signal. Common status signals
are BUSY and READY.
Address Recognition:
Just as each word of memory has an address, so thus each of the I/O devices. Thus an I/O module
must recognize one unique address for each peripheral it controls.

Device communication involves command status information and data

Data Buffering:
An essential task of an I/O module is data buffering. The data buffering is required due to the
mismatch of the speed of CPU, memory and other peripheral devices. In general, the speed of CPU is higher
than the speed of the other peripheral devices. So, the I/O modules store the data in a data buffer and regulate
the transfer of data as per the speed of the devices. The I/O module must be able to operate at both device and
memory speed.

Error Detection:
Another task of I/O module is error detection and for subsequently reporting error to the processor.
Block diagram of IO Module

There are three basic techniques or modes of IO operation. They are

 Programmed I/O
 Interrupt Driven I/O
 Direct Memory Access(DMA)

Programmed I/O

In programmed I/O, the data transfer between CPU and I/O device is carried out with the help of a
software routine. When a processor is executing a program and encounters an instruction relating to I/O, it
executes that I/O instruction by issuing a command to the appropriate I/O module.
The I/O module will perform the requested action and then set the appropriate bits in the I/O status
register. The I/O module takes no further action to alert the processor. It is the responsibility of the processor to
check periodically the status of the I/O module until it finds that the operation is complete. In programmed I/O,
when the processor issues a command to a I/O module, it must wait until the I/O operation is complete.
Generally, the I/O devices are slower than the processor, so in this scheme CPU time is wasted. CPU
is checking the status of the I/O module periodically without doing any other work.
To execute an I/O-related instruction, the processor issues an address, specifying the particular I/O
module and external device, and an I/O command. There are four types of I/O commands that an I/O module
will receive when it is addressed by a processor

Control: Used to activate a peripheral device and instruct it what to do. For example, a magnetic tape unit may
be instructed to rewind or to move forward one record. These commands are specific to a particular type of
peripheral device.
Test: Used to test various status conditions associated with an I/O module and its peripherals. The processor
will want to know if the most recent I/O operation is completed or any error has occurred.
Read: Causes the I/O module to obtain an item of data from the peripheral and place it in the internal buffer.
Write: Causes the I/O module to take an item of data ( byte or word ) from the data bus and subsequently
transmit the data item to the peripheral.
Interrupt Driven IO

The problem with programmed I/O is that the processor has to wait a long time for the I/O module of
concern to be ready for either reception or transmission of data. The processor, while waiting, must repeatedly
interrogate the status of the I/O module.
The solution to this problem is to provide an interrupt mechanism. In this approach the processor
issues an I/O command to a module and then go on to do some other useful work. The I/O module then
interrupts the processor to request service when it is ready to exchange data with the processor. The processor
then executes the data transfer. Once the data transfer is over, the processor then resumes its former
processing.

The occurrence of an interrupt triggers a number of events, both in the processor hardware and in software.
When an I/O device completes an I/O operation, the following sequences of hardware events occurs:

1. The device issues an interrupt signal to the processor.

2. The processor finishes execution of the current instruction before responding to the interrupt.
3. The processor tests for the interrupt; if there is one interrupt pending, then the processor sends an
acknowledgement signal to the device which issued the interrupt. After getting acknowledgement, the device
removes its interrupt signals.
4. The processor now needs to prepare to transfer control to the interrupt routine. It needs to save the
information needed to resume the current program at the point of interrupt. The minimum information required
to save is the processor status word (PSW) and the location of the next instruction to be executed which is
nothing but the contents of program counter. These can be pushed into the system control stack.
5. The processor now loads the program counter with the entry location of the interrupt handling program that
will respond to the interrupt.
Two design issues arise in implementing interrupt I/O.
1. There will almost invariably be multiple I/O modules, how does the processor determine which device
issued the interrupt?
2. If multiple interrupts have occurred how the processor does decide which one to process?

Direct Memory Access (DMA)

Programmed I/O and Interrupt Driven I/O methods require the active intervention of the processor to
transfer data between memory and the I/O module, and any data transfer must transverse a path through the
processor. Thus both these forms of I/O suffer from two inherent drawbacks.
1. The I/O transfer rate is limited by the speed with which the processor can test and service a device.
2. The processor is tied up in managing an I/O transfer; a number of instructions must be executed for
each I/O transfer.
DMA: It is an approach that transfers large block of data at high speed between external devices and memory
directly with out continuous intervention by the processor.
DMA transfers are performed by a control circuit associated with the I/O device and this circuit is referred as
DMA controller. The DMA controller allows direct data transfer between the device and the main memory
without involving the processor. To transfer data between memory and I/O devices, DMA controller takes over
the control of the system from the processor and transfer of data take place over the system bus. For this
purpose, the DMA controller must use the bus only when the processor does not need it, or it must force the
processor to suspend operation temporarily.
Cycle Stealing: it is a method used by the DMA control over the system bus to transfer data between external
devices and memory. After data transfer completion it returns control back to CPU.

DMA Block Diagram

When the processor wishes to read or write a block of data, it issues a command to the DMA module, by
sending to the DMA module the following information.
1. Whether a read or write is requested, using the read or write control line between the processor and the
DMA module.
2. The address of the I/O devise involved, communicated on the data lines.
3. The starting location in the memory to read from or write to, communicated on data lines and stored
by the DMA module in its address register.
4. The number of words to be read or written again communicated via the data lines and stored in the
data count register.

The processor then continues with other works. It has delegated this I/O operation to the DMA module.
The DMA module checks the status of the I/O devise whose address is communicated to DMA controller by
the processor. If the specified I/O devise is ready for data transfer, then DMA module generates the DMA
request to the processor. Then the processor indicates the release of the system bus through DMA
acknowledge. When the transfer is completed, the DMA module sends an interrupt signal to the processor.
After receiving the interrupt signal, processor takes over the system bus. Thus the processor is involved only at
the beginning and end of the transfer.
The DMA mechanism can be configured in following three ways

1. Single bus, detached DMA - I/O configuration.

2. Single bus, Integrated DMA - I/O configuration.
3. Using separate I/O bus.

Single bus, detached DMA - I/O configuration:

In this, all modules share the same system bus. The DMA module here acts as an alternative
processor. This method uses programmed I/O to exchange data between memory and an I/O module through
the DMA module. For each transfer it uses the bus twice. The first one is when transferring the data between
I/O and DMA and the second one is when transferring the data between DMA and memory. Since the bus is
used twice while transferring data, so the bus will be suspended twice. The transfer consumes two bus cycles.

Single bus, integrated DMA I/O configuration:

Number of required bus cycles can be reduced in this method. DMA module and one or more I/O modules are
integrated together in such a way that the system bus is not involved. The DMA module, processor and the
memory module are connected through the system bus. In this configuration each transfer will use the system
bus only once and so the processor is suspended only once. The system bus is not involved when transferring
data between DMA and I/O device, so processor is not suspended.Processor is suspended when data is
transferred between DMA and memory.
Using separate I/O Bus:

In this configuration the I/O modules are connected to the DMA through another I/O bus. In this case
the DMA module is reduced to one. Transfer of data between I/O module and DMA module is carried out
through this I/O bus. In this transfer, system bus is not in use and so it is not needed to suspend the processor.
There is another transfer phase between DMA module and memory. In this time system bus is needed for
transfer and processor will be suspended for one bus cycle.

Disk Organization

A disk is a circular platter constructed of metal or of plastic coated with a magnetizable material.
Data is recorded on and later retrieved from the disk via a conducting coil named the head. During a read or
write operation, the head is stationary while the platter rotates beneath it.
The write mechanism is based on the fact that electricity flowing through a coil produces a magnetic
field. Pulses are sent to the head, and magnetic patterns are recorded on the surface below.
The read mechanism is based on the fact that a magnetic field moving relative to a coil produces on
electric current in the coil. When the surface of the disk passes under the head, it generates a current of the
same polarity as the one already recorded.
The data on the disk are organized in a concentric set of rings, called track. Each track has the same
width as the head. Adjacent tracks are separated by gaps. This prevents error due to misalignment of the head
or interference of magnetic fields.
Same number of bits is stored in each track, so inner most track has more density than the outermost
track. Data are transferred to and from the disk in blocks. Usually, the block is smaller than the capacity of the
track. Accordingly, data are stored in block-size regions known as sector.
Physical characteristics of Disk

1. The head may be either fixed or movable with respect to the radial direction of the platter.
2. In a fixed-head disk, there is one read-write head per track. All of the heads are mounted on a rigid
arm that extends across all tracks.
3. In a movable-head disk, there is only one read-write head. Again the head is mounted on an arm.
Because the head must be able to be positioned above any track, the arm can be extended for this
purpose.
4. The disk itself is mounted in a disk drive, which consists of the arm.
5. A disk can be a removable or non removable. A non removable disk is permanently mounted on the
disk drive. A removable disk can be removed and replaced with another disk.
6. For most disks, the magnetizable coating is applied to both sides of the platters, which is then referred
to as double sided disk. If the magnetizable coating is applied to one side only, then it is termed as
single sided disk.

Some disk drives accommodate multiple platters stacked vertically above one another. Multiple arms are
provided for read write head.

Organization and accessing of data on a disk

Each surface is divided into tracks and each track is divided into sectors. Data on disks are addressed
by specifying the surface number, the track number, and the sector number. Read and write operations always
start at sector boundaries. If the number of words to be written is smaller than that required to fill a sector, the
disk controller repeats the last bit of data for the remaining of the sector.
During read and write operation, it is required to specify the starting address of the sector from where
the operation will start, that is the read/write head must positioned to the correct track, sector and surface.
Therefore the address of the disk contains track no., sector no., and surface no. If more than one drive is
present, then drive number must also be specified.

Suppose that the disk system has 8 data recording surfaces with 4096 track per surface. Tracks are
divided into 256 sectors. Then the format of disk address word is:

Suppose each sector of a track contains 512 bytes of disk recorded serially, then the total capacity of
the disk is:

Disk Performance parameters

When a disk drive is operating, the disk is rotating at constant speed. To read or write, the head must be
positioned at the desired tack and at the beginning of the desired sector on the track. Track selection involves
moving the head.

Seek Time:
Seek time is the time required to move the read/write head to the proper track.

Rotational Delay (Latency Time):

Once the track is selected, the time it takes to reach the beginning of the desired sector is known as
rotational delay or rotational latency.

Transfer Time:
The transfer time to or from the disk depends on the rotational speed of the disk and it is estimated as

So, the average access time can be expressed as

The disk access time is sum of seek time and rotational delay. The disk access time is relatively higher
than the time required to access data from main memory and performs CPU operation. Also the disk drive
contains some mechanical parts and it involves mechanical movement, so the failure rate is also high.
A disk array is an arrangement of several disk, organized to increase performance and improve
reliability of the resulting storage system. Performance is increased through data striping. Reliability is
improved through redundancy.
Disk arrays that implement a combination of data striping and redundancy are called Redundant
Arrays of Independent Disks (RAID).

Data stripping:
In data striping, the data is segmented in equal-size partitions distributed over multiple disks. The size of the
partition is called the striping unit. The partitions are usually distributed using a round-robin algorithm. If the
disk array consists of D disks, then partition i is written in to disk ( i mod D ).

Redundancy:
Having more disks increases storage system performance, it also lowers overall storage system reliability,
because the probability of failure of a disk in disk array is increasing. Reliability of a disk array can be
increased by storing redundant information. If a disk fails, the redundant information is used to reconstruct the
data on the failed disk.

Disk Scheduling Algorithms

Disk scheduling is is done by operating systems to schedule I/O requests arriving for 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 disk controller. Thus other I/O requests need to wait in 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 computer system and thus need to be accessed in an
efficient manner.
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 queue. In this approach, every request gets a fair chance and no indefinite
postponement. All incoming requests are placed at the end of the queue. Whatever number that is
next in the queue will be the next number served. Using this algorithm doesn't provide the best results.
To determine the number of head movements you would simply find the number of tracks it took to
move from one request to the next. It does not try to give optimize seek time and performance may be
poor.

Ex 1: Given the following queue -- 95, 180, 34, 119, 11, 123, 62, 64 with the Read-write head initially
at the track 50 and the tail track being at 199

Ex 2:
Queue with I/O requests 23, 89, 132, 42, 187, head initial position is 100

2. Shortest Seek Time First (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 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. Starvation may occur because of a
request if it has higher seek time as compared to incoming requests.
Ex 1:

Ex 2:

3. Scan (Elevator Algorithm):

In this approach, 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 like an elevator and hence also known as elevator algorithm.
Ex 1:
Ex 2:

4. C-Scan (Circular Scan):

Circular scanning works just like the elevator to some extent. It begins its scan toward the nearest
end and works its way all the way to the end of disk. Once it hits the bottom or top it jumps to the
other end and moves in the same direction.
Ex: 1
Ex: 2

5. Look:
It is similar to the SCAN disk scheduling algorithm except 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.

6. C-Look:
As LOOK is similar to SCAN algorithm, in similar way, CLOOK is similar to CSCAN disk scheduling
algorithm. In CLOOK, the disk arm inspite 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.
RAID Levels

RAID stands for redundant array of independent disks. Today the term has been updated to
redundant array of independent disks. RAID is a way of grouping individual physical drives together
to form one bigger drive called a RAID set. RAID can make many smaller disks appear as one large
disk to a server. The RAID set represents all the smaller physical drives as one logical disk to your
server. The logical disk is called a LUN or logical unit number. Using RAID has two main advantages.
Better performance and higher availability, which means it goes faster and breaks down less often.

Performance is increased because the server has more spindles to read from or write to
when data is accessed from a drive. Availability is increased because the RAID controller can re-
create lost data from parity information. Parity is basically a checksum of the data that was written
to the disks, which gets written along with the original data. The controller re-creates the data that
was lost when the drive went bad by using the parity information stored on the surviving disks in the
RAID set.
There are a number of different ways drives can be grouped together to form RAID sets.
The different methods used to group drives are called RAID types. RAID types are numbered from 0
to 5. The numbers represent the level of RAID being used. RAID levels 0, 1 and 5 are the most
common. Combinations of RAID types may be used together. For example, you can create RAID 10
sets, by combine the RAID 0 sets into a RAID 1 set. This will essentially give you the performance
benefits of RAID 0, with the availability benefits of RAID 1.
The RAID type you should use depends on the type of application you are running on your
server. RAID 0 is the fastest. RAID 1 is the most reliable and RAID 5 is a good combination of both.

RAID 0:
RAID 0 is called disk striping. All the data is spread out in chunks across all the disks in the RAID set.
RAID 0 has great performance because you spread the load of storing data onto more physical drives. There
is no parity generated for RAID 0. Therefore there is no overhead to write data to RAID 0 disks. RAID 0 is only
good for better performance, and not for high availability, since parity is not generated for RAID 0 disks.
RAID 0 requires at least two physical disks.

RAID 1:
RAID 1 is called disk mirroring. All the data is written to at least two separate physical disks. The
disks are essentially mirror images of each other. If one of the disks fails, the other can be used to retrieve
data. Disk mirroring is good for very fast read operations. It's slower when writing to the disks, since the data
needs to be written twice. RAID 1 requires at least two physical disks

RAID 1+0:
RAID 1+0, which is also called RAID 10, uses a combination of disk mirroring and disk striping. The
data is normally mirrored first and then striped. Mirroring striped sets accomplishes the same task, but is less
fault tolerant than striping mirror sets. If you lose a drive in a stripe set, all access to data must be from the
other stripe set, because stripe sets have no parity. RAID 1+0 requires a minimum of four physical disks.

RAID 2:
RAID 2 is a technique that stripes data at the bit level using a Hamming code to detect errors. You need
two groups of disks. One group of disks is used to write the data, another group is used to write the error
correction codes. This uses Hamming error correction code (ECC), and stores this information in the
redundancy disks. When data is written to the disks, it calculates the ECC code for the data on the fly, and
stripes the data bits to the data-disks, and writes the ECC code to the redundancy disks. When data is read
from the disks, it also reads the corresponding ECC code from the redundancy disks, and checks whether the
data is consistent. If required, it makes appropriate corrections on the fly. This uses lot of disks and can be
configured in different disk configuration.
This is not used anymore. This is expensive and implementing it in a RAID controller is complex, and ECC
is redundant now-a-days, as the hard disk themselves can do this.
RAID 3:
RAID 3 uses something called a parity disk to store the parity information generated by the RAID
controller on a separate disk from the actual data disks, instead of striping. This RAID type is not currently
used very often because it performs poorly when there are a lot of little requests for data, as in a database.
This type performs well under applications that just want one long sequential data transfer. Applications like
video servers work well with this RAID type. RAID 3 requires a minimum of three physical disks.

RAID 4:
This uses block level striping. It uses multiple data disks, and a dedicated disk to store parity. It needs
minimum of 3 disks (2 disks for data and 1 for parity). It provides good random reads, as the data blocks are
striped. This is just like RAID 3 in having the dedicated parity disk, but this stripes blocks. This is just like RAID
5 in striping the blocks across the data disks, but this has only one parity disk. This is not commonly used.
RAID 5:
RAID 5 uses disk striping with parity. The data is striped across all the disks in the RAID set, along
with the parity information needed to reconstruct the data in case of disk failure. RAID 5 is the most common
method used, since it achieves a good balance between performance and availability. RAID 5 requires at least
three physical disks.

RAID 6:
RAID 6 increases reliability by utilizing two parity stripes, which allows for two disk failures within
the RAID set before data is lost. RAID 6 is seen in SATA environments, and solutions that require long data
retention periods, such as data archiving or disk-based backup.

File System Management

File Concepts
The file system consists of two distinct parts: a collection of files, each storing related data, and a
directory structure, which organizes and provides information about all the files in the system.
Computers can store information on several different storage media, such as magnetic disks,
magnetic tapes, and optical disks in the form of files. Files are mapped, by the operating system, onto
physical devices. These storage devices are usually nonvolatile, so the contents are persistent through power
failures and system reboots. A file is a named collection of related information that is recorded on secondary
storage. Data cannot be written to secondary storage unless they are within a file. The file structure depends
on the type of the file. A text file is a sequence of characters organized into lines. A source file is a sequence
of subroutines and functions. An object file is a sequence of bytes organized into blocks.
File Attributes:

Name: The symbolic file name is the only information kept in human readable form.
Identifier: This unique tag, usually a number, identifies the file within the file system; it is the non-human-
readable name for the file.
Type: This information is needed for those systems that support different types.
Location: This information is a pointer to a device and to the location of the file on that device.
Size: The current size of the file (in bytes, words, or blocks), and possibly the maximum allowed size are
included in this attribute.
Protection: Access-control information determines who can do reading, writing, executing, and so on.
Time, date, and user identification: This information may be kept for creation, last modification, and last use.
These data can be useful for protection, security, and usage monitoring.

The information about all files is kept in the directory structure that also resides on secondary storage.

File Operations
1. Creating a file
2. Writing a file
3. Reading a file
4. Repositioning within a file
5. Deleting a file
6. Truncating a file.
Most OSes require that files be opened before access and closed after all access is complete. Normally the
programmer must open and close files explicitly, but some rare systems open the file automatically at first
access. Information about currently open files is stored in an open file table, contains

>File pointer - records the current position in the file, for the next read or write access.
>File-open count - How many times has the current file been opened and not yet closed? When this counter
reaches zero the file can be removed from the table.
>Disk location of the file.
>Access rights

Access Methods
The information in the file can be accessed in several ways. Some systems provide only one access
method for files and other systems provide many methods.

Sequential Access:
The simplest access method is sequential access. Information in the file is processed in order, one
record after the other. This mode of access is by far the most common; for example, editors and compilers
usually access files in this fashion.
Direct Access:
Random access file organization provides, accessing the records directly. Each record has its own
address on the file with by the help of which it can be directly accessed for reading or writing. The records
need not be in any sequence within the file and they need not be in adjacent locations on the storage
medium.

Indexed sequential access:

This mechanism is built up on base of sequential access. An index is created for each file which
contains pointers to various blocks. Index is searched sequentially and its pointer is used to access the file
directly.

Directory Structure

Systems can store millions of files on the disk. To manage all these data, we need to organize them.
This organization is usually done in two parts. First, disks are split into partitions, also known as mini disks.
Sometimes, partitions are used to provide several separate areas within one disk, each treated as a separate
storage device. Partitions can also store multiple operating systems, allowing a system to boot and run more
than one. Second, each partition contains information about files within it. This information is kept in entries
in a device directory or volume table of contents. The device directory (more commonly known simply as a
directory) records information-such as name, location, size, and type-for all files on that partition.
Operations that are performed on Directory:

 Search for a file

 Create a file - add to the directory
 Delete a file - erase from the directory
 List a directory - possibly ordered in different ways.
 Rename a file - may change sorting order
 Traverse the file system.

Directory Structures:
1. Single Level Directory:
The simplest directory structure is the single-level directory. All files are contained in the same
directory, which is easy to support and understand. A single-level directory has significant limitations,
however, when the number of files increases or when the system has more than one user. Since all files are in
the same directory, they must have unique names. If two users call their data file test, then the unique-name
rule is violated.
Even a single user on a single-level directory may find it difficult to remember the names of all the
files as the number of files increases.

2. Two Level Directory:

A single-level directory often leads to confusion of file names among different users. The standard
solution is to create a separate directory for each user.
In the two-level directory structure, each user has his own The UFDs have similar structures, but each
lists only the files of a single user. W11en a user job starts or a user logs in, the system's is searched. The MFD
is indexed by user name or account number, and each entry points to the UFD for that user.
When a user refers to a particular file, only his own UFD is searched. Thus, different users may have
files with the same name, as long as all the file names within each UFD are unique. To create a file for a user,
the operating system searches only that user's UFD to ascertain whether another file of that name exists. To
delete a file, the operating system confines its search to the local UFD; thus, it cannot accidentally delete
another user's file that has the same name.
Although the two-level directory structure solves the name-collision problem, it still has
disadvantages. This structure effectively isolates one user from another. Isolation is an advantage when the
users are completely independent but is a disadvantage when the users want to cooperate on some task and to
access one another's files. Some systems simply do not allow local user files to be accessed by other users.
A two-level directory can be thought of as a tree, or an inverted tree, of height 2. The root of the tree is
the MFD. Its direct descendants are the UFDs.
3. Tree Structured Directories:

It is an extension to the two-tiered directory structure. A tree is the most common directory structure.
The tree has a root directory, and every file in the system has a unique path name.

A directory (or subdirectory) contains a set of files or subdirectories. A directory is simply

another file. Files may be accessed using either absolute pathnames ( relative to the root of the tree )
or relative pathnames ( relative to the current directory. ) Directories are stored the same as any other
file in the system, except there is a bit that identifies them as directories.
Path names can be of two types: absolute and relative. An absolute path name begins at the
root and follows a path down to the specified file, giving the directory names on the path. A relative
path name defines a path from the current directory.
If the current path is root/spell/mail then the relative path nan<e prt/first refers to the same
file as does the absolute path name root/spell/mail/prt/first.
With a tree-structured directory system, users can be allowed to access, in addition to their
files, the files of other users. For example, user B can access a file of user A by specifying its path
names. User B can specify either an absolute or a relative path name. Alternatively, user B can change
her current directory to be user A's directory and access the file by its file names.

4. Acyclic Graph Directories

When the same files need to be accessed in more than one place in the directory structure
( e.g. because they are being shared by more than one user / process ), it can be useful to provide an
acyclic-graph structure. These shared files or sub directories can be implemented by using a new
directory entry called a link. A link a pointer to another file or a subdirectory.
A hard link ( usually just called a link ) involves multiple directory entries that both refer to
the same file. Hard links are only valid for ordinary files in the same file system.
A symbolic link, that involves a special file, containing information about where to find the
linked file. Symbolic links may be used to link directories and/or files in other file systems, as well as
ordinary files in the current file system.
Hard links require a reference count, or link count for each file, keeping track of how many
directory entries are currently referring to this file. Whenever one of the references is removed the link
count is reduced, and when it reaches zero, the disk space can be reclaimed.
For symbolic links there are some issues , what to do with the symbolic links when the
original file is moved or deleted:
 One option is to find all the symbolic links and adjust them also.
 Another is to leave the symbolic links dangling, and discover that they are no longer valid the
next time they are used.
 What if the original file is removed, and replaced with another file having the same name before
the symbolic link is next used?

5. General Graph Directories

If cycles are allowed in the graphs, then several problems can arise:
i. Search algorithms can go into infinite loops. One solution is to not follow links in search
algorithms.
ii. Sub trees can become disconnected from the rest of the tree and still not have their reference
counts reduced to zero. Periodic garbage collection is required to detect and resolve this problem.

File System Structure

File systems provide efficient and convenient access to the disk by allowing data to be stored, located, and
retrieved easily. The file system itself is generally composed of many different levels. Each level in the design
uses the features of lower levels to create new features for use by higher levels. File systems organize storage
on disk drives, and can be viewed as a layered design
At the lowest layer are the physical devices, consisting of the magnetic media, motors & controls, and
the electronics connected to them and controlling them. Modern disk put more and more of the electronic
controls directly on the disk drive itself, leaving relatively little work for the disk controller card to perform.

I/O Control consists of device drivers, special software programs ( often written in assembly ) which
communicate with the devices by reading and writing special codes directly to and from memory addresses
corresponding to the controller card's registers. Each controller card ( device ) on a system has a different set of
addresses that it listens to, and a unique set of command codes and results codes
that it understands.

The basic file system level works directly with the device drivers in terms of retrieving and storing raw
blocks of data, without any consideration for what is in each block. Depending on the system, blocks may be
referred to with a single block number, ( e.g. block # 234234 ), or with head sector cylinder combinations.

The file organization module knows about files and their logical blocks, and how they map to physical
blocks on the disk. In addition to translating from logical to physical blocks, the file organization module also
maintains the list of free blocks, and allocates free blocks to files as needed.

The logical file system deals with all of the meta data associated with a file ( UID, GID, mode, dates,
etc ), i.e. everything about the file except the data itself. This level manages the directory structure and the
mapping of file names to file control blocks, FCBs, which contain all of the meta data as well as block number
information for finding the data on the disk.

Common file systems in use include the UNIX file system, UFS, the Berkeley Fast File System, FFS,
Windows systems FAT, FAT32, NTFS, CDROM systems ISO 9660, and for Linux the extended file systems
ext2 and ext3

Directory Implementation

The selection of directory-allocation and directory-management algorithms significantly affects the efficiency,
performance, and reliability of the file system. Directories need to be fast to search, insert, and delete, with a
minimum of wasted disk space. Directories can be implemented by using two different data structures, Linear
list and hashed tables.

Linear List:

The simplest method of implementing a directory is to use a linear list of file names with pointers to
the data blocks. This method is simple to program but time-consuming to execute. To create a new file, we
must first search the directory to be sure that no existing file has the same name. Then, we add a new entry at
the end of the directory. To delete a file, we search the directory for the named file and then release the space
allocated to it.
To reuse the space after deleting a file, we can do it by using one of the following ways,
i. Mark the entry as unused by assigning special name or indicator or a flag value
ii. Attach this free space to list of free directory entries.
iii. Copy the last entry in the directory into the freed location

The real disadvantage of a linear list of directory entries is that finding a file requires a linear search.

Hash Table

Another data structure used for a file directory is a hash table. With this method, a linear list stores the
directory entries, but a hash data structure is also used. The hash table takes a value computed from the file
name and returns a pointer to the file name in the linear list. Therefore, it can greatly decrease the directory
search time. Insertion and deletion are also fairly straightforward, although some provision must be made for
collisions-situations in which two file names hash to the same location. The problem with hash tales is size,
here size is fixed and the hash function works based on size of the hash table.

Allocation methods:

Allocation methods specify how space is allocated for the files in the disk. There are three major allocation
methods, contiguous, linked and indexed.

Contiguous Allocation:

Contiguous Allocation requires that all blocks of a file be kept together contiguously. Performance is
very fast, because reading successive blocks of the same file generally requires no movement of the disk
heads. Contiguous allocation of a file is defined by the disk address and length of the first block. If the file is n
blocks long and starts at location b, then it occupies blocks b, b + 1, b + 2, ... , b + n - 1.
Accessing a file that has been allocated contiguously is easy. For sequential access, the file system
remembers the disk address of the last block referenced and, when necessary, reads the next block. For direct
access to block i of a file that starts at block b, we can immediately access block b + i. Thus, both sequential
and direct access can be supported by contiguous allocation.

The problem with contiguous allocation is determining how much space is needed for a file. When the
file is created, the total amount of space it will need must be found and allocated. Problems can arise when
files grow, or if the exact size of a file is unknown at creation time: Overestimation of the file's final size
increases external fragmentation and wastes disk space. Underestimation may require that a file be moved or a
process aborted if the file grows beyond its originally allocated space. If a file grows slowly over a long time
period and the total final space must be allocated initially, then a lot of space becomes unusable before the file
fills the space.
To minimize these drawbacks, some operating systems use a modified contiguous-allocation scheme.
Here, a contiguous chunk of space is allocated initially; then, if that amount proves not to be large enough,
another chunk of contiguous space, known as an is added. The location of a file's blocks is then recorded as a
location and a block count, plus a link to the first block of the next extent.

Linked Allocation:

Linked allocation solves all problems of contiguous allocation. With linked allocation, each file is a
linked list of disk blocks; the disk blocks may be scattered anywhere on the disk. The directory contains a
pointer to the first and last blocks of the file. Each block contains a pointer to the next block. These pointers
are not made available to the user.
To create a new file, we simply create a new entry ile the directory. With linked allocation, each
directory entry has a pointer to the first disk block of the file. This pointer is initialized to nil, to signify an
empty file. Linked allocation involves no external fragmentation, does not require pre known file sizes, and
allows files to grow dynamically at any time.
The major problem is that it can be used effectively only for sequential-access files. To filed the
ith block of a file, we must start at the beginning of that file and follow the pointers until we get to the ith
block. Each access to a pointer requires a disk read, and some require a disk seek. Consequently, it is
inefficient to support a direct-access capability for linked-allocation files. Another big problem with linked
allocation is reliability if a pointer is lost or damaged. Doubly linked lists provide some protection, at the cost
of additional overhead and wasted space.

An important variation on linked allocation is the use of a file allocation table (FAT). This simple but
efficient method of disk-space allocation is used by the MS-DOS and OS/2 operating systems.

A section of disk at the beginning of each volume is set aside to contain the table. The table has one
entry for each disk block and is indexed by block number. The FAT is used in much the same way as a linked
list. The directory entry contains the block number of the first block of the file. The table entry indexed by that
block number contains the block number of the next block in the file. This chain continues until it reaches the
last block, which has a special end-of-file value as the table entry. An unused block is indicated by a table
value of 0. Allocating a new block to a file is a simple matter of finding the first 0-valued table entry and
replacing the previous end-of-file value with the address of the new block. The 0 is then replaced with the end-
of-file value.

Indexed Allocation:

Linked allocation solves the external-fragmentation and size-declaration problems of contiguous

allocation. However, in the absence of a FAT, linked allocation cannot support efficient direct access, since the
pointers to the blocks are scattered with the blocks themselves all over the disk and must be retrieved in order.
The index allocation solves this problem by bringil1.g all the pointers together into one location: the index
block.
Each file has its own index block, which is an array of disk-block addresses. The i th entry in the
index block points to the ith block of the file. The directory contains the address of the index block. To find
and read the ith block, we use the pointer in the ith index-block entry.
When the file is created, all pointers in the index block are set to nil. When the ith block is first
written, a block is obtained from the free-space manager and its address is put in the ith index-block entry.
Indexed allocation supports direct access, without suffering from external fragmentation, because any free
block on the disk can satisfy a request for more space.

Indexed allocation supports direct access, without suffering from external fragmentation, because any
free block on the disk can satisfy a request for more space. Indexed allocation does suffer from wasted space,
however. The pointer overhead of the index block is generally greater than the pointer overhead of linked
allocation. Consider a common case in which we have a file of only one or two blocks. With linked allocation,
we lose the space of only one pointer per block. With indexed allocation, an entire index block must be
allocated, even if only one or two pointers will be non-nil.
Some disk space is wasted ( relative to linked lists or FAT tables ) because an entire index block must
be allocated for each file, regardless of how many data blocks the file contains. This leads to questions of how
big the index block should be, and how it should be implemented. There are several approaches:

Linked Scheme An index block is one disk block, which can be read and written in a single disk operation.
The first index block contains some header information, the first N block addresses, and if necessary a pointer
to additional linked index blocks.
MultiLevel Index The first index block contains a set of pointers to secondary index blocks, which in turn
contain pointers to the actual data blocks.
Combined Scheme This is the scheme used in UNIX inodes, in which the first 12 or so data block pointers are
stored directly in the inode, and then singly, doubly, and triply indirect pointers provide access to more data
blocks as needed. ( See below. ) The advantage of this scheme is that for small files ( which many are ), the
data blocks are readily accessible ( up to 48K with 4K block sizes ); files up to about 4144K ( using 4K blocks
) are accessible with only a single indirect block ( which can be cached ), and huge files are still accessible
using a relatively small number of disk accesses ( larger in theory than can be addressed by a 32bit address,
which is why some systems have moved to 64bit file pointers. )

Free Space Management:

Since disk space is limited, we need to reuse the space from deleted files for new files, if possible.
(Write-once optical disks only allow one write to any given sector, and thus such reuse is not physically
possible.) To keep track of free disk space, the system maintains a free space list. The free-space list records all
free disk blocks-those not allocated to some file or directory. To create a file, we search the free-space list for
the required amount of space and allocate that space to the new file. This space is then removed from the free-
space list. When a file is deleted, its disk space is added to the free-space list.

Bit Vector:

The free-space list is implemented as a bitmap or bit vector. Each block is represented by 1 bit. If the block is
free, the bit is 1; if the block is allocated, the bit is 0. For example, consider a disk where blocks 2, 3, 4, 5, 8, 9,
10, 11, 12, 13, 17, 18, 25, 26, and 27 are free and the rest of the blocks are allocated. The free-space bit map
would be
001111001111110001100000011100000
The main advantage of this approach is its relative simplicity and its efficiency in finding the first free block or
n consecutive free blocks on the disk.

Linked List:

Another approach to free-space management is to link together all the free disk blocks, keeping a
pointer to the first free block in a special location on the disk and caching it in memory. This first block
contains a pointer to the next free disk block, and so on.
In the above example, 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18, 25, 26, and 27 were free and the rest of the blocks
were allocated. In this situation, we would keep a pointer to block 2 as the first free block. Block 2 would
contain a pointer to block 3, which would point to block 4, which would point to block 5, which would point to
block 8, and so on. This scheme is not efficient; to traverse the list, we must read each block, which requires
substantial I/0 time.

Counting:

Another approach takes advantage of the fact that, generally, several contiguous blocks may be
allocated or freed simultaneously, particularly when space is allocated with the contiguous-allocation
algorithm or through clustering. Thus, rather than keeping a list of n free disk addresses, we can keep the
address of the first free block and the number (n) of free contiguous blocks that follow the first block. Each
entry in the free-space list then consists of a disk address and a count.

Protection and Security

Protection refers to a mechanism for controlling the access of programs, processes, or users to the
resources defined by a computer system. The processes in an operating system must be protected from one
another's activities. To provide such protection, we can use various mechanisms to ensure that only processes
that have gained proper authorization from the operating system can operate on the files, memory segments,
CPU, and other resources of a system.

Goals of Protection:

1. To prevent malicious misuse of the system by users or programs.

2. To ensure that each shared resource is used only in accordance with system policies, which may
be set either by system designers or by system administrators.
3. To ensure that errant programs cause the minimal amount of damage possible.

Principles of Protection:

The principle of least privilege dictates that programs, users, and systems be given just enough privileges
to perform their tasks. This ensures that failures do the least amount of harm. Typically each user is given
their own account, and has only enough privilege to modify their own files. The root account should not
be used for normal day to day activities. The System Administrator should also have an ordinary account,
and reserve use of the root account for only those tasks which need the root privileges

Domain of Protection:

A computer system is a collection of processes and objects. By objects, we mean both (such as
the CPU, memory segments, printers, disks, and tape drives) and (such as files, programs, and
semaphores). Each object has a unique name that differentiates it from all other objects in the system, and
each can be accessed only through well-defined and meaningful operations. The operations that are
possible may depend on the object. For example, on a CPU, we can only execute. Memory segments can be
read and written, Data files can be created, opened, read, written, closed, and deleted; program files can be
read, written, executed, and deleted. A process should be allowed to access only those resources for which it
has authorization. Furthermore, at any time, a process should be able to access only those reso1Jrces that it
currently requires to complete its task.

Domain structure:
A domain is a set of objects and respective operations. A process operates within a protection domain, which
specifies the resources that the process may access. The ability to execute an operation on an object is an
access right. So domain is a collection of access rights, each of which is an ordered pair < object name,
access right set>

Ex: if domain D is defined as <File F, {read,write}> then a process executing in domain D can both read and
write file F but it can not perform any other operation.

A domain may be static or dynamic. In static domain, the set of resources available to the process are fixed;

Domain Switching: It enables process to switch from one domain to another domain.

Access Matrix:

The domain of protection can be view as a matrix called access matrix. The rows of the access matrix represent
domains, and the columns represent objects. Each entry in the matrix consists of a set of access rights.

There are four domains and four objects-three files (F1, F2, F3) and one laser printer. A process executing in
domain 0 1 can read files F1 and F3 . A process executing in domain 0 4 has the same privileges as one
executing in domain 0 1; but in addition, it can also write onto files F1 and F3 . Note that the laser printer can
be accessed only by a process executing in domain D2.
The access-matrix scheme provides us with the mechanism for specifying a variety of policies.
we must ensure that a process executing in domain Di can access only those objects specified in row ( and then
only as allowed by the access-matrix entries.

The access matrix provides an appropriate mechanism for defining and implementing strict control for both the
static and dynamic association between processes and domains. They are,
 Switching
 Copy
 Owner
 Control

Switching:
When we switch a process from one domain to another, we are executing an operation (switch) on an
object. Processes should be able to switch from one domain to another. Switching from domain Di to domain
Dj is allowed if and only if the access right “switch” is placed at access(i,j) index. In the following table, a
process executing in domain D2 can switch to domain D3 or to domain D4 . A process in domain D4 can
switch to D1, and one in domain D1 can switch to D2.
Copy:
The ability to copy an access right from one domain (or row) of the access matrix to another is
denoted by an asterisk (*) appended to the access right. The copy right allows the access right to be copied
only within the column. (that is, for the object) for which the right is defined.
In the following figure (a), a process executing in domain D 2 can copy the read operation into any
entry associated with file F2 . Hence, the access matrix of Figure (a) can be modified to the access matrix
shown in Figure (b ).

The copy mechanism has two variants:

Transfer: (Transfer Copy)

An access right is copied from access(i, j) to access(k, j); it is then removed from access(i, j). This
action is a transfer of a right, rather than a copy.

Limited: (Limited Copy)

When an access right R* is copied from access(i,j) to access(k,j), only the right R (not R*) is created. A
process executing in domain Dk cannot further copy the right R.

A system may select only one of these three copy rights, or it may provide all three by identifying
them as separate rights: copy, transfer, and limited copy.

Owner:
We also need a mechanism to allow addition of new rights and removal of some rights. The owner
right controls these operations. If access(i, j) includes the owner right, then a process executing in domain Di
can add and remove any right in any entry in column j.
In the following figure, domain D1 is the owner of F1 and thus can add and delete any valid right in column F1.
Similarly, domain D2 is the owner of F2 and F3 and thus can add and remove any valid right within these two
columns. Thus, the access matrix of Figure (a) can be modified to the access matrix shown in Figure (b).

Control:

The copy and owner rights allow a process to change the entries in a column. A mechanism is also
needed to change the entries in a row. The control right is applicable only to domain objects. If access(i, j)
includes the control right, then a process executing in domain Di can remove any access right from row j.
For example, suppose that, in Figure (a), we include the control right in access(D2, D4). Then, a
process executil1.g in domain D2 could modify domain D4, as shown in Figure (b).

Figure (a)

Figure (b)
Implementation of Access Matrix

An access matrix can be implemented by using following methods.

Global Table:
The simplest approach is one big global table with < domain, object, rights > entries.
Unfortunately this table is very large and so cannot be kept in memory ( without invoking virtual memory
techniques). There is also no good way to specify groupings If everyone has access to some resource, then
it still needs a separate entry for every domain.

Access Lists for Objects:

Each column of the table can be kept as a list of the access rights for that particular object,
discarding blank entries. For efficiency a separate list of default access rights can also be kept, and
checked first.

Capability Lists for Objects:

In a similar fashion, each row of the table can be kept as a list of the capabilities of that domain.
Capability lists are associated with each domain, but not directly accessible by the domain or any user
process.
Capability lists are themselves protected resources, distinguished from other data in one of two
ways:
 A tag, possibly hardware implemented, distinguishing this special type of data. ( other types may
be floats, pointers, booleans, etc. )
 The address space for a program may be split into multiple segments, at least one of which is
inaccessible by the program itself, and used by the operating system for maintaining the process's
access right capability list.
A Lock Key Mechanism:

Each resource has a list of unique bit patterns, termed locks. Each domain has its own list of
unique bit patterns, termed keys. Access is granted if one of the domain's keys fits one of the resource's
locks. Again, a process is not allowed to modify its own keys.

Comparison:
Each of the methods here has certain advantages or disadvantages, depending on the particular
situation and task at hand. Many systems employ some combination of the listed methods.

Real Time Operating Systems (RTOS)

Real Time Operating Systems are very fast and quick respondent systems. Real time applications
used this RTOS. A real time application is an application program that functions within a time frame.
Real time processing requires quick transaction and characterized by supplying immediate response. For
example, a measurement from a petroleum refinery indicating that temperature is getting too high and
might demand for immediate attention to avoid an explosion. RTOS is a real time OS working with real
time constraints as power, time and efficient usage of memory. Most of the embedded systems are bound
to real time constraints and it is achieved using real time system. The main concern of RTOS is it
produces an accurate output within the deadline or time.
Examples of real time applications include:
 Videoconference applications
 VoIP (voice over Internet Protocol)
 Online gaming
 Community storage solutions
 Some e-commerce transactions
 Chatting
 IM (instant messaging)
Examples of RTOS
 VxWorks
 QNX
 eCos
 RTLinux
An example is form your PC if you copy some data from one device to another device it may take several
minutes or more, we cannot predict responsiveness of the system of course, due to the tasks running
parallel at that time.
But, a real time embedded system can give an accurate output at right time that means, it is time critical
no delay is encouraged for real time systems and if any delay occurs it may lead to catastrophic effects.
For example Airbag control system in a car. If you drive a car at a high speed accidents may happen, in
such case airbag opens and saves your life.

Types of RTOS
Soft RTOS:
Soft real time OS is a type of OS where certain deadlines may be missed, they will respond at a time
t=0+. Soft real time systems are not constrained to extreme rules. The critical time of the soft real time
may be delayed to some extent. The expected latency between the tasks and time constraints may be
deviated. The preemption period for a soft real time task is about few milliseconds.
Ex: Digital camera, mobile phones, online data base etc.
Hard RTOS
Hard real time OS is a type of OS we can predict the deadline, they will respond at a time t=0. Hard real
time systems are constrained to predicted time constraints, deadlines and latency.
Ex: Air bag control in cars, anti-lock brake, engine control system etc.

Differences between RTOS and GPOS

 General purpose operating systems cannot perform real time tasks whereas RTOS is suitable for
real time applications.
 There is deadline associated with real time kernel but GPOS does not follow timely mechanism.
 The real time kernel follows preemptive scheduling policy whereas GPOS follow non preemptive
scheduling technique.
 Synchronization is a problem with GPOS whereas synchronization is achieved in real time kernel.
 Inter task communication is done using real time OS where GPOS does not.
 Latency is a problem with GPOS but it is overcome using real time OS.
 Priority inversion cannot be done in GPOS, it is done with real time kernel.
 Jitter i.e. timing error in task is not present in real time OS, present in GPOS.

Micro Kernels:

A core feature of any operating system, the kernel manages communication between hardware and
software. The kernel is responsible for managing memory, and I/O to memory, cache, the hard drive, and
other devices. It also handles device signals, task scheduling, and other essential duties. The kernel is one
of the first components loaded into memory during the boot process, and remains active as long as the
computer is operational. Kernels vary widely in function and scope, but always greatly affect their
operating system's capabilities. For this reason, particularly in Unix, administrators tweak the kernels to
best suit their requirements.
Compared to a typical kernel, a microkernel is compact, performing only the basic functions universal to
all computers. Designed to be integrated into different operating systems, a microkernel works with OS-
specific servers that provide higher level functions. This component-based structure improves a system's
portability, but potentially at the expense of performance. Mac OS and WinNT are two examples on
microkernel OS architecture.
Here some advantages to the microkernel OS architecture…
1. Service separation has the advantage that if one service (called a server) fails others can still work
so reliability is the primary feature. For example if a device driver crashes does not cause the
entire system to crash. Only that driver need to be restarted rather than having the entire system
die. This means more persistence as one server can be substituted with another. It also means
maintenance is easier.
2. Different services are built into special modules which can be loaded or unloaded when needed.
Patches can be tested separately then swapped to take over on a production instance.
3. Message passing allows independent communication and allows extensibility
4. The fact that there is no need to reboot the kernel implies rapid test and development.
5. Easy and faster integration with 3d party modules.
Here are some disadvantages to the microkernel approach…
1. Memory foot print is large
2. Potential performance loss (more software interfaces due to message passing)
3. Message passing bugs are not easy to fix
4. Process management is complex