Olabisi Onabanjo University, Ago Iwoye.

Ogun State. Nigeria.

Faculty of Science
Department of Mathematical Sciences

BSc- Lecture Note: OPERATING SYSTEM

Objectives: To learn the fundamental of Operating System (OS), the mechanism of OS to handle
process and threads and their communication. The mechanisms involve in memory manage ment,
filing system and device in OS concepts. The components and management aspects of
concurrency management and knowledge on distributed operating system concepts.

Course Outlines:
 Introduction: Overview of OS. Basic OS functions and the historical development
 Processes Management: Process, Process Control Block. Process State, Scheduling (CPU
Utilisation and task scheduling), Concurrency (mutual exclusion, synchro nisation,
deadlock, starvation, race condition)
 Memory Management: Physical and Virtual memory,
 Scheduling Input/Output: Disk request scheduling
 File Management: Overview, file Organization and access, file directories, File sharing,
Record blocking, secondary storage management, File system protection and security

FUNDAMENTALS OF OPERATING SYSTEM

Computing machines have been increasing in complexity for many centuries, but only recently
have they become complex enough to require something recognisable as an operating system.

What is Operating System?

An operating system is system software that act as an intermediary and enables the computer
hardware to communicate and operate with the computer software which hide the complexities of
hardware from the user and manage between the hardware‟s resources.

An operating system can also be defined as one program running at all times on the computer
(usually called the kernel), with all its applications programs and provide an environment in
which a user can execute program.
 An operating system is an important part of almost every computer system. A computer system
can be divided into four components: the hardware, the operating system, the applications
programs, and the users.
The hardware includes the Central Processing Unit (CPU), the memory, and the input/output (I/O)
devices - provides the basic computing resources while the applications programs such as
compilers, database systems, games, and business programs define the ways in which these
resources are used to solve the computing problems of the users. An operating system is a control
program that executes user programs to prevent errors and improper use of the computer. It is
especially concerned with the operation and control of I/O devices.

Functions of Operating System

Operating System has following functions:
 It manages the computer‟s resources such as CPU, memory, file and devices.
 Behaves as a Virtual Machine
 Establish a user‟s interface
 Execute and provide services for application software

Historical Development of Operating System

For those who grew up having an entire computer sitting at their finger tips waiting at their beck
and call to carry out every command, it is hard to imagine punching a program into punch cards,
submitting it over a Dutch door and then waiting at least 24 hours to get a printout of the run. Or,
even worse, driving 30 miles and waiting one week between program submission and receipt of
the printout. But, to understand how today‟s operating systems came to be what they are, we need
to go back “to those days of yesteryear,” as the saying goes.

The chief function of an operating system is to manage the resources of a complex computer
system. It has been said that necessity is the mother of invention. The development of operating
systems to their present day form is a good illustration of that. At each stage in this development,
bottlenecks were found which prevented using the computer resources to their fullest
capacity. The need to eliminate those bottlenecks gave impetus to inventiveness leading to the
next step in the history of operating systems. The development describes along with the particular
type of operating system.

Stages of Development
 The Earliest Computer:
The earliest computers did not have software. Their functionality was hardwired. To reprogram
the machine required rewiring. These machines, of course, did not have an operating system.

 User Setup and Breakdown:

With the advent of the stored program machine the day of the von Neumann architecture
machines began. But the early machines were very costly, available only to clients with deep
pockets. When it was not uncommon to pay thousands of dollar for a computer, those who used
these machines for business or research were willing to go to great lengths just to get their
“moment in the sun”. Computers were scheduled around the clock and users had to come in at
their scheduled time. In addition to load their programs, the users had to load (and link, if
necessary) any system software, such as compilers and device drivers, needed for their run. And
additional work was required to make the machine available for the next user.

 Operator Controlled Machines:

Very soon it became clear that during the rather lengthy setup and breakdown time the very
expensive computer was not doing useful work. This waste of resources had to be remedied. A
computer operator was put in charge of the machine. Users submitted their programs on punch
cards. The operator scheduled job execution, loaded the programs, collected the output and
performed any required setup operations. By running jobs with similar system requirements in
the same time frame, the setup and breakdown process was streamlined. Jobs could also be
arranged by priority, run time and other criteria.

 Simple Batch Systems

To further reduce slack time, the amount of time during which the computer did no useful work,
the scheduling and loading functions were turned over to a program called the monitor (called
a resident monitor, if it stayed in memory at all times). Users submitted short instructions in a
cryptic language called Job Control Language (JCL) to aid the monitor in its task. Jobs were
grouped together and run in batches. Often a separate computer was used to handle the I/O
operations. Debugging for this and other early systems was accomplished by interpreting a core
dump, a hexadecimal snaps hot of the contents of memory and all registers at the time of program
error. Hardware features such as memory protection, timers, privileged instructions and interrupts
were added to machines during this stage of development. On, the computer components were
separated

SPOOLING
When a job is executed, the operating system satisfies its requests for card reader input by reading
from the disk and when the job requests the printer to output a line that line is copied into a
system buffer and is written to the disk. When the job is completed, the output is actually printed.
This form of processing is called s pooling i.e. Simultaneous Peripheral Operation On-Line.
Spooling uses the disk as a huge buffer, for reading as far ahead as possible on input devices and
for storing output files until the output devices are able to accept them.

Spooling is also used for processing data at remote sites. The CPU sends the data via
communications paths to a remote printer. The remote processing is done at its own speed, with
no CPU intervention. The CPU just needs to be notified when the processing is completed, so that
it can spool the next batch of data.
Spooling overlaps the I/O of one job with the computation of other jobs. Spooling has a direct
beneficial effect on the performance of the system. Spooling can keep both the CPU and the I/O
devices working at much higher rates

 Multiprogrammed Batch Systems

Spooling provides an important data structure (A job pool). Spooling will generally result in
several jobs that have already been read waiting on disk, ready to run. A pool of jobs on disk
allows the operating system to select which job to run next, to increase CPU utilization. An I/O
operation is orders of magnitude slower than instruction execution. For this reason the processor
would sit idle a large proportion of the time, despite the efficiency improvements brought about
by batch systems. Instead of doing useful work, the processor would wait for an I/O operation to
complete. The observation was made that more than one job could be read into memory, allowing
the processor to switch back and forth between jobs (or processes). While one process was
involved in I/O, another could be running that is making use of the processor. Jobs must be run
sequentially, on a first-come, first-served basis. However, when several jobs are on a direct-access
device, such as a disk, job scheduling becomes possible. The most important aspect of job
scheduling is the ability to multiprogrammmg. Thus, schedulers and memory
management modules were added to the software repertoire of an operating system.

 Interactive Multiprogramming (Time Sharing Systems)

The importance of good response time and short turnaround time were factored into the OS design
process. The major step taken was the advent of time shared systems. An interactive, or hands-
on, computer system provides on-line communication between the user and the system. The user
gives instructions to the operating system or to a program directly, and receives an immediate
response.

Time sharing, or multitasking, is a logical extension of multiprogramming. Multiple jobs are

executed by the CPU switching between them, but the switches occur so frequently that the users
may interact with each program while it is running. Since the processor speed was many orders
of magnitude faster than the actions taken by the user, under ideal conditions the user could work
as if she had sole access to the machine. Time-sharing systems were developed to provide
interactive use of a computer system at a reasonable cost. A time-shared operating system uses
CPU scheduling and multiprogramming to provide each user with a small portion of a time -shared
computer.

 Single User Multiprogramming

With the introduction of personal computer with multiprogramming resulted in extremely useful
computer systems. The user could run several processes at one time, doing useful work with one
program while waiting for another program to complete its task. In addition, this could perform
operations which require two programs to run simultaneously, e.g., copy text from a web page and
paste it into a word processing document.
Figure 1: Components of Operating System

PROCESS AND THREAD MANAGEMENT

Process Management
The design of an operating system must be done in such a way that all requirements should be
fulfilled.
 The operating system must interleave the execution of multiple processes, to maximize
processor utilization while providing reasonable response time.
 The operating system must allocate resources to processes in conformance with a specific
policy
 The operating system may be required to support Interprocess communication and user
creation of processes

Program and Process

A process is a program in execution. For example, when we write a program for instance in C and
compile it, the compiler creates a binary code. The original code and Binary code, both are
programs. When we actually run the binary code, it becomes a process.

A process is an instance of program execution. A process is an „active‟ entity as opposed to a

program which is considered to be a „passive‟ entity. A single program can create many processes
when run multiple times, for example when we open a .exe or binary file multiple times, many
instances begin (many processes are created).
Attributes or Characteristics of a Process

Process has the following Attributes.

1. Process Id: A unique identifier assigned by operating system
2. Process State: Can be ready, running, waiting, finish etc.
3. CPU registers: Like Program Counter (CPU registers must be saved and restored when a
process is swapped out and in of CPU)
5. Accounts information:
6. I/O status information: For example devices allocated to process, open files, etc
7. CPU scheduling information: For example Priority
All the above attributes of a process are also known as Context of the Process.

Every Process has its known Program Control Block (PCB) that is each process will have a
unique PCB. All the Above Attributes are the part of the PCB.

Process Control Block

An operating system maintains a structure called a Process Control Block (PCB) for each of its
active processes. The PCB for a process contains or refers to the following kinds of information.
 Resource Management Information
 Administrative Information
 An Execution Snapshot

Resource management information includes all information about resources other than the
processor that a process is using. This includes page tables and open files and I/O streams. In
addition, most operating systems support command-line arguments and environment variables for
programs. The resource information for such operating systems contains references to structures
containing the command-line arguments and environment variables

Administrative information includes a process identifier, resource usage information (such as

execution time), process ownership, and any kind of administrative data needed by system
administrators for running their system securely.
The execution snapshot captures any information about a process that is required to resume its
operation from the time when the snapshot was taken. The contents are somewhat dependent on
the processor, but always include register and PC contents.

Process States
The operating system is responsibility is controlling the execution of processes; this includes
determining the interleaving pattern for execution and allocating resources to processes.

Process Creation: When a new process is to be added to those currently being managed, the
operating system builds the data structures that are used to manage the process and allocates
address space in main memory to the process. This is the creation of a new process.
Process Termination: Any computer system must provide a means for a process to indicate its
completion. A batch job should include a Halt instruction or an explicit operating system service
call for termination.
A process may be in one of two states: Running or Not Running. When the operating system
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 operating syste m,
and is waiting to execute. Processes that are not running must be kept in some sort of queue,
waiting their turn to execute. There is a single queue in which each entry is a pointer to the
process control block of a particular process.

A Process is in one of the following five (5) states

1. New: Newly Created Process (or) being created process. The creation transition is caused by a
system call instruction for loading a program. A process control block is created for the
program. It is initialized so that the process starts with cleared registers and PC set to the
program's start (main) address. Usually the operating system sets up three open files:
standard input, standard output, and standard error.
2. Ready: After creation Process moves to Ready state, that is process is ready for execution. A
process in the ready state has all of the resources that it needs for further execution except
for a processor. It is normally held in a ready queue until a processor becomes available.
Suspended Ready: When ready queue becomes full, some processes are moved to suspend
ready state
3. Run: Currently running process in CPU (only one process at a time can be under execution in a
single processor).
4. Wait (or Block): When process request for I/O request.
5. Complete (or terminated): Process Completed its execution.
Suspended Block: When waiting queue becomes full.

Figure 2: A Process State

Modes of Execution
Processors support at least two modes of execution. Certain instructions can only be executed in
the more-privileged mode. These would include reading or altering a control register, such as the
program status word; primitive I/O instructions; and instructions that relate to memory
management. The less privileged mode is often referred to as the user mode, because user
programs typically would execute in this mode. The more-privileged mode is referred to as the
system mode, control mode, or kernel mode.

Mode Switch
A mode switch occurs when CPU privilege level is changed, for example when a system call is
made or a fault occurs. The kernel works in more privileged mode than a standard user task. If a
user process wants to access things which are only accessible to the kernel, a mode switch must
occur. The currently executing process need not be changed during a mode switch. A mode witch
typically occurs for a process context switch to occur. Only the Kernel can cause a context switch.

It is necessary to protect the operating system and key operating system tables, such a s process
control blocks from interference by user programs. In the kernel mode, the software has complete
control of the processor and all its instructions, registers, and memory. This level of control is not
necessary and for safety is not desirable for user programs.

Process Switching
Sometimes, a running process is interrupted and the operating system assigns another process to
the running state and turns control over to that process, which is defined as process switching. A
process switch may occur any time that the operating system has gained control from the currently
running process.

When does Process switching happen?

1. When a high priority process comes to ready state, compared to priority of running process
2. Interrupt occurs
3. User and Kernel mode switch: (It is not necessary)
4. Preemptive CPU scheduling is used.

A process switch may occur any time that the operating system has gained control from the
currently running process. The main cause is system interrupt i.e. two kinds of system interrupts:
 Trap
 Interrupt

Trap is event that is external to and independent of the currently running process, such as the
completion of an I/O operation. Interrupt relates to an error or exception condition generated
within the currently running process, such as an illegal file access attempt.

Interrupt, control is first transferred to an interrupt handler, then to an operating system.

There are different kinds of Interrupt :
 Clock interrupt: The operating system determines whether the currently running process has
been executing for the maximum allowable unit of time, that is time slice.
 I/O interrupt: The operating system determines what I/O action has occurred. If the I/O action
constitutes an event for which one or more processes are waiting, then the operating system
moves all of the corresponding blocked processes to the Ready state.
 Memory fault: The processor encounters a virtual memory address reference for a word that is
not in main memory. The operating system must bring in the block (page or segment) of memory
containing the reference from secondary memory to main memory. After the I/O request is issued
to bring in the block of memory, the process with the memory fault is placed in a blocked state.
With a trap the operating system determines if the error or exception condition is fatal, then the
currently running process is moved to the Exit state and a process switch occurs.

Threads Management

What is a Thread?
A thread is a path of execution within a process. However, a process can contain multiple
threads. A thread of execution is the smallest sequence of programmed instructions that can be
managed independently by a scheduler which is typical a part of OS. Threads in a process can
execute different parts of the program code at the same time. They can also execute the same
parts of the code at the same time, but with different execution state

Modern operating systems allow a process to be divided into multiple threads of execution. T he
threads within a process share all process management information except for information
directly related to execution. This information is moved out of the PCB into Thread Control
Block (TCBs).

They have independent current instructions; that is, they have (or appear to have) independent
program counters. They are working with different data; that is, they are (or appear to be)
working with independent registers. This is accomplished by moving execution state out of the
PCB into thread control blocks (TCBs). Each thread has its own TCB.

Thread Control Block

A thread control block (TCB) contains a thread identifier, a reference to the PCB for the process
to which it belongs, a reference to the TCB for the thread that created it, and an execution
snapshot. A thread has indirect access to non-execution related resources through the PCB of the
process to which it belongs. Thus threads within a process share memory, open files, and I/O
streams.
Why Multithreading?
Thread is also known as lightweight process. The idea is achieve parallelism by dividing a
process into multiple threads. For example, in a browser, multiple tabs can be different threads.
MS word uses multiple threads, one thread to format the text, other thread to process inputs etc.
Difference between Process and Thread
The typical difference is that threads within the same process run in a shared memory space,
while processes run in separate memory spaces. Threads are not independent of one other like
processes as a result threads shares with ot her threads their code section, data section and OS
resources like open files and signals. But, like process, a thread has its own program counter
(PC), a register set, and a stack space

Thread and Process are two closely related terms in multi-threading. The main difference
between the two terms is that the threads are a part of a process, i.e. a process may contain one or
more threads, but a thread cannot contain a process.
In programming, there are two basic units of execution: processes and threads. They both execute
a series of instructions. Both are initiated by a program or the operating system.
 Faster process switch: Context switch time between threads is less compared to process
context switch. Process context switch is more overhead for CPU.
 Responsiveness: If the process is divided into multiple threads, if one thread completed its
execution, then its output can be immediately responded.
 Effective Utilization of Multiprocessor system: If we have multiple threads in a single
process, then we can schedule multiple threads on multiple processor. This will make
process execution faster.
 Resource sharing: Resources like code, data and file can be shared among all threads
within a process.
Note: stack and registers cannot be shared among the threads. Each thread have its own
stack and registers.
 Communication: Communication between multiple thread is easier as thread shares
common address space. while in process we have to follow some specific communication
technique for communication between two process.
 Enhanced Throughput of the system: If process is divided into multiple threads and each
thread function is considered as one job, then the number of jobs completed per unit time
is increased. Thus, increasing the throughput of the system.

Comparison between Process and Thread:

Process Thread
Definition An executing instance of a A thread is a subset of the process.
program is called a process.
Process It has its own copy of the data It has direct access to the data
segment of the parent process. segment of its process.
Communication Processes must use inter- Threads can directly communicate
process communication to with other threads of its process.
communicate with sibling
 processes.
Overheads Processes have considerable Threads have almost no overhead.
overhead.
Creation New processes require New threads are easily created.
duplication of the parent
process.
Control Processes can only exercise Threads can exercise considerable
control over child processes. control over threads of the same
process.
Changes Any change in the parent Any change in the main thread
process does not affect child may affect the behavior of the
processes. other threads of the process.
Memory Run in separate memory spaces. Run in shared memory spaces.
File descriptors Most file descriptors are not It shares file descriptors.
shared.
File system There is no sharing of file It shares file system context.
system context.
Signal It does not share signal It shares signal handling.
handling.
Controlled by Process is controlled by the Threads are controlled by
operating system. programmer in a program.
Dependence Processes are independent. Threads are dependent.

Process Synchronisation
On the basis of synchronisation, processes are categorized as one of the following two types:
 Independent Process: Execution of one process does not affect the execution of other
processes.
 Cooperative Process: Execution of one process affects the execution of other processes.
Therefore, Process synchronization problem arises in the case of Cooperative process also
because resources are shared in Cooperative processes. These leads to Critical Section
Problem.

Critical section is a code segment that can be accessed by only one process at a time. Critical
section contains shared variables which need to be synchronized to maintain consistency of data
variables.

Semaphores
A Semaphore is an integer variable, which can be accessed only through two
operations wait() and signal(). In the entry section, the process requests for entry in the Critical
Section.
There are two types of Semaphores: Binary Semaphores and Counting Semaphores
 Binary Semaphores: They can only be either 0 or 1. They are also known as mutex locks,
as the locks can provide mutual exclusion. All the processes can share the same mutex
semaphore that is initialized to 1. Then, a process has to wait until the lock becomes 0.
Then, the process can make the mutex semaphore 1 and start its critical section. When it
completes its critical section, it can reset the value of mutex semaphore to 0 and some other
process can enter its critical section.
 Counting Semaphores: They can have any value and are not restricted over a certain
domain. They can be used to control access a resource that has a limitation on the number
of simultaneous accesses. The semaphore can be initialized to the number of instances of
the resource. Whenever a process wants to use that resource, it checks if the number of
remaining instances is more than zero, i.e., the process has an instance available. Then, the
process can enter its critical section thereby decreasing the value of the counting semaphore
by 1. After the process is over with the use of the instance of the resource, it can leave the
critical section thereby adding 1 to the number of available instances of the resource.

Any solution to the critical section problem must satisfy three requirements:
 Mutual Exclusion: If a process is executing in its critical section, then no other process is
allowed to execute in the critical section.
 Progress: If no process is in the critical section, then no other process from outside can
block it from entering the critical section.
 Bounded Waiting: A bound must exist on the number of times that other processes are
allowed to enter their critical sections after a process has made a request to enter its
critical section and before that request is granted.

Peterson’s Solution
Peterson‟s Solution is a classical software based solution to the critical section problem. In
Peterson‟s solution, we have two shared variables:
boolean flag[i] :Initialized to FALSE, initially no one is interested in entering the critical section
int turn : The process whose turn is to enter the critical section.
Peterson‟s Solution preserves all three conditions:
 Mutual Exclusion is assured as only one process can access the critical section at any
time.
 Progress is also assured, as a process outside the critical section does not blocks other
processes from entering the critical section.
 Bounded Waiting is preserved as every process gets a fair chance.

Disadvantages of Peterson‟s Solution

 It involves Busy waiting
 It is limited to 2 processes.

TestAndSet
TestAndSet is a hardware solution to the synchronization problem. In TestAndSet, there are
shared lock variable which can take either of the two values 0 or 1. That is 0 for Unlock and 1 for
Lock.
Before entering into the critical section, a process inquires about the lock. If it is locked, it keeps
on waiting till it become free and if it is not locked, it takes the lock and executes the critical
section.
In TestAndSet, Mutual exclusion and progress are preserved but bounded waiting cannot be
preserved.

Usage of Semaphores: Semaphores can be used to deal with n process critical section problem.
The n processes shares the semaphores, mutex (standing for mutual exclusion), initialized to 1.)
Implementation
When-a-process-executes the wait operation and finds that the semaphore value is not positive, it
must wait However, rather than busy waiting, the process can block itself. The block operation
places a process into a waiting queue associated with the semaphore, and the state of the process
is switched to the waiting state. Then, control is transferred to the CPU scheduler, which selects
another process to execute
A process that is blocked, waiting on a semaphore should be resorted when some other process
executes a signal operation. The process is restarted by a wake up operation, which changes the
process from the waiting state to the ready state.

Priority Scheduling
Priority scheduling is a non-preemptive algorithm and one of the most common scheduling
algorithms in batch systems. Each process is assigned a priority. Process with the highest priority
is to be executed first and so on. Processes with the same priority are executed on first come first
served basis. Priority can be decided based on memory requirements, time requirements or any
other resource requirement.

Implementation:
 First input the processes with their burst time and priority.
 Sort the processes, burst time and priority according to the priority.
 Now simply apply FCFS algorithm.

Note: A major problem with priority scheduling is indefinite blocking or starvation. A solution to
the problem of indefinite blockage of the low-priority process is aging.
Aging is a technique of gradually increasing the priority of processes that wait in the system for a
long period of time.

Starvation or indefinite blocking is phenomenon associated with the Priority scheduling

algorithms, in which a process ready to run for CPU can wait indefinitely because of low priority.
In heavily loaded computer system, a steady stream of higher-priority processes can prevent a
low-priority process from ever getting the CPU.

Deadlocks and Starvation

The implementation of a semaphore with a waiting queue may result in situation where two or
more processes are waiting indefinitely for an event that can be caused by only one of the waiting
processes. The event in execution of a signal operation. When suc h a state is reached, these
processes are said to be deadlocked.
Another problem related to deadlocks is indefinite blocking or starvation, a situation where
processes wait indefinitely within the semaphore. Indefinite blocking may occur if we add and
remove processes from the list associated with a semaphore in LIFO order. Other name of
deadlock is Circular Waiting. Other name of starvation is Lived lock.

When deadlock occurs no process can make progress, while in starvation apart from the victim
process other processes can progress or proceed.

Solution to Starvation: Aging

Aging is a technique of gradually increasing the priority of processes that wait in the system for a
long time. For example, if priority ranges from 127 (low) to 0(high), this could increase the
priority of a waiting process by 1 Every 15 minutes. Eventually even a process with an initial
priority of 127 would take no more than 32 hours for priority 127 process to age to a priority-0
process.

Figure 3: Effect of Time changes on Priority

Deadlock
Deadlock is a situation where a set of processes are blocked because each process is holding a
resource and waiting for another resource acquired by some other process.
Consider an example when two trains are coming toward each other on same track and there is
only one track, none of the trains can move once they are in front of each other. Similar situation
occurs in operating systems when there are two or more processes hold some resources and wait
for resources held by other(s).

Deadlock can arise if following four conditions hold simultaneously (Necessary Conditions)
 Mutual Exclusion: One or more than one resource are non-sharable (Only one process can
use at a time).
 Hold and Wait: A process is holding at least one resource and waiting for resources.
 No Preemption: A resource cannot be taken from a process unless the process releases the
resource.
 Circular Wait: A set of processes are waiting for each other in circular form.
Methods for handling deadlock
There are three ways to handle deadlock
  Deadlock prevention or avoidance: The idea is to not let the system into deadlock state.
 Deadlock detection and recovery:
 Let deadlock occur, then do Preemption to handle it once occurred.
Ignore the problem all together: If deadlock is very rare, then let it happen and reboot the system.
This is the approach that both Windows and UNIX take.

Deadlock Detection and Recovery

Deadlock Detection
1. If resources have single instance: In this case for Deadlock detection we can run an algorithm
to check for cycle in the Resource Allocation Graph. Presence of cycle in the graph is the
sufficient condition for deadlock.

Figure 4: Process Cycle in Deadlock

In the above diagram, resource 1 and resource 2 have single instances. There is a cycle R1–
>P1–>R2–>P2. So Deadlock is confirmed.
2. If there are multiple instances of resources: Detection of cycle is necessary but not sufficient
condition for deadlock detection, in this case system may or may not be in deadlock varies
according to different situations.

Deadlock Recovery: Traditional operating system such as Windows doesn‟t deal with deadlock
recovery as it is time and space consuming process. Real time operating systems use Deadlock
recovery.
Recovery method
1. Killing the Process: Killing all the process involved in deadlock.

2. Resource Preemption: Resources are preempted from the processes involved in deadlock,
preempted resources are allocated to other processes, so that there is a possibility of recovering
the system from deadlock. In this case systems go into starvation.
Deadlock Prevention
Deadlock can be prevented by eliminating any of the above four condition discussed.
 Eliminate Mutual Exclusion: It is not possible to dis-satisfy the mutual exclusion because
some resources, such as the tap drive and printer, are inherently non-shareable.
 Eliminate Hold and wait
1. Allocate all required resources to the process before start of its execution, this way hold
and wait condition is eliminated but it will lead to low device utilization. for example, if a
process requires printer at a later time and it has to be allocated printer before the start of
its execution printer will remained blocked till it has completed its execution.
2. Process will make new request for resources after releasing the current set of resources.
This solution may lead to starvation.

 Eliminate No Preemption : Preempt resources from process when resources required by

other high priority process.
 Eliminate Circular Wait: Each resource will be assigned with a numerical number. A
process can request for the resources only in increasing order of numberin g.
For Example, if P1 process is allocated R5 resources, now next time if P1 ask for R4, R3
lesser than R5 such request will not be granted, only request for resources more than R5
will be granted.

Deadlock Avoidance
Deadlock avoidance can be done with Banker‟s Algorithm.
Banker‟s Algorithm is resource allocation and deadlock avoidance algorithm which test all the
request made by processes for resources, it check for safe state, if after granting request system
remains in the safe state it allows the request and if their is no safe state it don‟t allow the request
made by the process.

Inputs to Banker’s Algorithm

1. Max need of resources by each process.
2. Currently allocated resources by each process.
3. Max free available resources in the system.
Request will only be granted under below condition.
1. If request made by process is less than equal to max need to that process.
2. If request made by process is less than equal to freely available resource in the system.
MEMORY MANAGEMENT
Memory is central to the operation of a modern computer system. Memory is a large array of
words or bytes, each with its own address. “Memory is the primary and fundamental power, without which
there could be no other intellectual operation.”
A program resides on a disk as a binary executable file. The program must be brought into
memory and placed within a process for it to be executed Depending on the memory management
in use the process may be moved between disk and memory during its execution. The co llection
of processes on the disk that are waiting to be brought into memory for e xecution forms the input
queue that is selected one of the process in the input queue and to load that process into memory.

The binding of instructions and data to memory addresses can be done at any step along the way:
 Compile time: If it is known at compile time where the process will reside in memory,
then absolute code can be generated.
 Load time: If it is not known at compile time where the process will reside in memory,
then the compiler must generate re-locatable code.
 Execution time: If the process can be moved during its execution from one memory
segment to another, then binding must be delayed until run time.

Dynamic Loading
Better memory-space utilization can be done by dynamic loading. With dynamic loading, a
routine is not loaded until it is called. All routines are kept on disk in a re-locatable load format.
The main program is loaded into memory and is executed. The advantage of dynamic loading is
that an unused routine is never loaded.

Dynamic Linking
Most operating systems support only static linking, in which system language libraries are treated
like any other object module and are combined by the loader into the binary program image. The
concept of dynamic linking is similar to that of dynamic loading. Rather than loading being
postponed until execution time, linking is postponed. This feature is usually used with system
libraries, such as language subroutine libraries. With dynamic linking, a stub is included in the
image for each library-routine reference. This stub is a small piece of code that indicates how to
locate the appropriate memory-resident library routing.

Overlays
The entire program and data of a process must be in physical memory for the process to execute.
The size of a process is limited to the size of physical memory. So that a process can be larger
than the amount of memory allocated to it, a technique called overlays is sometimes used. The
idea of overlays is to keep in memory only those instructions and data that are needed at any given
time. When other instructions are needed, they are loaded into space that was occupied previously
by instructions that are no longer needed.
Example, consider a two-pass assembler. During pass 1, it constructs a symbol table; then, during
pass 2, it generates machine-language code. One may be able to partition such an assembler into
pass 1 code, pass 2 code, the symbol table 1 , and common support routines used by both pass 1 and
pass 2.

Let us consider
Pass1 70K
Pass 2 80K
Symbol table 20K
Common routines 30K

To load everything at once, we would require 200K of memory. If only 150K is available, we
cannot run our process. But pass 1 and pass 2 do not need to be in memory at the same time. We
thus define two overlays: Overlay A is the symbol table, common routines, and pass 1, and
overlay B is the symbol table, common routines, and pass 2. We add an overlay driver (10K) and
start with overlay A in memory. When we finish pass 1, we jump to the overlay driver, which
reads overlay B into memory, overwriting overlay A, and then transfers control to pass 2. Overlay
A needs only 120K, whereas overlay B needs 130K
As in dynamic loading, overlays do not require any special support from the operating system.

Logical versus Physical Address Space

An address generated by the CPU is commonly referred to as a logical address, whereas an
address seen by the memory unit is commonly referred to as a physical address.
The compile-time and load-time address-binding schemes result in an environment where the
logical and physical addresses are the same. The execution-time address-binding scheme results in
an environment where the logical and physical addresses differ. In this case, we usually refer to
the logical address as a virtual address. The set of all logical addresses generated by a program is
referred to as a logical address space; the set of all physical addresses corresponding to these
logical addresses is referred to as a physical address space.

The run-time mapping from virtual to physica l addresses is done by the Memory Management
Unit (MMU), which is a hardware device. The base register is called a relocation register. The
value in the relocation register is added to every address generated by a user process at the time it
is sent to memory.

The user program deals with logical addresses, therefore, the memory-mapping hardware converts
logical addresses into physical addressed.
Logical addresses (in the range 0 to max) and
Physical addresses (in the range R + 0 to R + max for a base value R).
The user generates only logical addresses. The concept of a logical address space that is bound to
a separate physical address space is central to proper memory management
Swapping
A process can be swapped temporarily out of memory to a backing store, and then brought back
into memory for continued execution. Assume a multiprogrammmg environment with a round
robin CPU-scheduling algorithm. When a quantum expires, the memory manager will start to
swap out the process that just finished, and to swap in another process to the memory space that
has been freed. When each process finishes its quantum, it will be swapped with another process.

A variant of this swapping policy is used for priority-based scheduling algorithms. If a higher-
priority process arrives and wants service, the memory manager can swap out the lower-priority
process so that it can load and execute the higherpriority process. When the higher priority
process finishes, the lower-priority process can be swapped back in and continued. This variant of
swapping is sometimes called rollout, roll in.

A process is swapped out will be swapped back into the same memory space that it occupies
previously. If binding is done at assembly or load time, then the process cannot be moved to
different location. If execution-time binding is being used, then it is possible to swap a process
into a different memory space. Swapping requires a backing store. The backing store is commonly
a fast disk. It is large enough to accommodate copies of all memory images for all users. The
system maintains a ready queue consisting of all processes whose memory images are on the
backing store or in memory and are ready to run.

Contiguous Allocation
The main memory must accommodate both the operating system and the various user processes.
The memory is usually divided into two partitions, one for the resident operating system, and
other for the user processes.
 Single Contiguous Allocation: Simplest allocation method used by MS-DOS. All memory
(except some reserved for OS) is available to a process.
 Partitioned Allocation: Memory is divided in different blocks. In Partition Allocation, when
there is more than one partition freely available to accommodate a process‟s request, a
partition must be selected. To choose a particular partition, a partition allocation method is
needed. A partition allocation method is considered better if it avoids internal fragmentation.
The various partition allocation schemes:
1. First Fit: First partition fitting the requirements, allocate the first hole that is big enough.
Searching can start either at the beginning of the set of holes or where the previous first-fit
search ended. We can stop searching as soon as we find a free hole that is large enough.
Leads to fast allocation of memory space
Advantage: Faster in making allocation
Disadvantage: Leads to memory waste
2. Best-fit: Allocate the smallest hole that is big enough. We must search the entire list,
unless the list is kept ordered by size. This strategy-produces smallest partition fitting
the requirements and results in least wasted space. Internal fragmentation reduced but not
eliminate.
 Advantage: Makes the best use of memory space
Disadvantage: Slower in making allocation

3. Worst-fit: Allocate the largest hole. Again, we must search the entire list unless it is
sorted by size. This strategy produces the largest leftover hole which may be more useful
than the smaller leftover hole from a best-t approach.

4. Next Fit: This is similar to the first fit but it will search for the first sufficient partition
from the last allocation point.
 Paged memory management: Memory is divided in fixed sized units called page frames,
used in virtual memory environment.
 Segmented memory management: Memory is divided in different segments (a segment is
logical grouping of process' data or code). In this management, allocated memory does not
have to be contiguous. Most of the operating systems (for example Windows and Linux) use
Segmentation with Paging. A process is divided in segments and individual segments have
pages

Is Best-Fit really best?

Although, best fit minimizes the wastage space, it consumes a lot of processor time for searching
the block which is close to required size. Also, Best-fit may perform poorer than other algorithms
in some cases. For example, see below exercise.

Exercise: Consider the requests from processes in given order 300K, 25K, 125K and 50K. Let
there be two blocks of memory available of size 150K followed by a block size 350K.
Which of the following partition allocation schemes can satisfy above requests?
A) Best fit but not first fit.
B) First fit but not best fit.
C) Both First fit & Best fit.
D) neither first fit nor best fit.
Solution: Let us try all options.
Best Fit: 300K is allocated from block of size 350K. 50 is left in the block. 25K is allocate d from
the remaining 50K block. 25K is left in the block. 125K is allocated from 150 K block. 25K is
left in this block also. 50K can‟t be allocated even if there is 25K + 25K space available.

First Fit: 300K request is allocated from 350K block, 50K is left out. 25K is be allocated from
150K block, 125K is left out. Then 125K and 50K are allocated to remaining left out partitions.
So, first fit can handle requests.
So option B is the correct choice.
Early Memory Allocation System
Types of Early Memory Allocation Schemes:
1. Single-user systems
2. Fixed partitions
3. Dynamic partitions
4. Relocatable dynamic partitions

1. Single-User Contiguous Scheme:

 Program is loaded in its entirety into memory and allocated as much contiguous space in memory
as it needs.
 Jobs processed sequentially in single-user systems
 Requires minimal work by the Memory Manager
 Register to store the base address
 Accumulator to keep track of the program size

Disadvantages of Single-UserContiguous Scheme:

• Doesn‟t support multiprogramming
• Not cost effective

2. Fixed Partitions:
 Main memory is partitioned; one partition/job.
 Allows multiprogramming
 P artit ion sizes rema in stat ic unless and unt il computer syste m id shut down,
reconfigured, and restarted
 Requires protection of the job‟s memory space
 Requires matching job size with partition size To allocate memory spaces to jobs, the
operating system‟s Memory Manager must keep a table as shown below:

Disadvantages:
• Requires entire program to be stored contiguously
• Jobs are allocated space on the basis of first available partition of required size
• Works well only if all of the jobs are of the same size or if the sizes are known aheadof
time
• Arbitrary partition sizes lead to undesired results
• Too small a partition size results in large jobs having longer turnaround time
• Too large a partition size results in memory waste or internal fragmentation

External and Internal Fragmentation

As processes are loaded and removed from memory, the free memory space is broken into little
pieces.
External fragmentation exists when enough to the memory space exists to satisfy a request, but it
is not contiguous; storage is fragmented into a large number of small holes. Depending on the
total amount of memory storage and the average process size, external fragmentation ma y be
either a minor or a major problem.
Given N allocated blocks, another 0.5N blocks will be lost due to fragmentation. That is, one -third
of memory may be unusable. This property is known as the 50 percent rule.
Internal fragmentation -memory that is internal to partition, but is not being used.

N O T E : J ob 3 m us t w a it e ve n t h ou g h 70K of f r e e s p a c e i s a v a i l a b l e i n
P a r t i t i o n 1 w h e r e J o b 1 o c c u p i e s only 30K of the 100K available,

T ab l e 1 an d Figure 5: A S i m p l i fi e d F i x e d P art i t i o n M e m o ry

3. Dynamic Partitions:
 Jobs are given only as much memory as they request when they are loaded
 Available memory is kept in contiguous blocks
 Memory waste is comparatively small

Disadvantages:
• Fully utilizes memory only when the first jobs are loaded
• Subsequent allocation leads to memory waste or external fragmentation
Figure 6 : A S i m p l i fi e d D yn am i c P art i t i o n M e m o ry
Table 2 and Figure 7: A S i m p l i fi e d I n t e rn al F rag m e n t at i o n
Paging
External fragmentation is avoided by using paging. In this, physical memory is broken into blocks
of the same size called pages. When a process is to be executed, its pages are loaded into any
available memory frames. Every address generated by the CPU is divided into any two parts: a
page number(p) and a page offset(d). The page number is used as an index into a page table. The
page table contains the base address of each page in physical memory. This base address is
combined with the gage offset to define the physical memory address t hat is sent to the memory
unit. Paging is a form of dynamic relocation. Every logical address is bound by the paging
hardware to some physical address.
When we use a paging scheme, we have no external fragmentation: Any free frame can be
allocated to a process that needs it. If process size is independent of page size, we can have
internal fragmentation to average one-half page per process.

Segmentation:
A user program can be subdivided using segmentation, in which the program and its associated
data are divided into a number of segments. It is not required that all segments of all programs be
of the same length, although there is a maximum segment length. As with paging, a logical
address using segmentation consists of two parts, in this case a segment number and an offse t.
Because of the use of unequal-size segments, segmentation is similar to dynamic partitioning.
In segmentation, a program may occupy more than one partition, and these partitions need not be
contiguous. Segmentation eliminates internal fragmentation but , like dynamic partitioning, it
suffers from external fragmentation. However, because a process is broken up into a number of
smaller pieces, the external fragmentation should be less. Whereas paging is invisible to the
programmer, segmentation usually vis ible and is provided as a convenience for organizing
programs and data.

Another consequence of unequal-size segments is that there is no simple relationship between

logical addresses and physical addresses. Segmentation scheme would make use of a segment
table for each process and a list of free blocks of main memory. Each segment table entry would
have to as in paging give the starting address in main memory of the corresponding segment. The
entry should also provide the length of the segment, to assure that invalid addresses are not used.
When a process enters the Running state, the address of its segment table is loaded into a special
register used by the memory management hardware.
NOTE: Segmentation and paging can be combined to have a good result.

VIRTUAL MEMORY
Virtual memory is a technique that allows the execution of process that may not be completely in
memory. The main visible advantage of this scheme is that programs can be larger than physical
memory. Virtual memory is the separation of user logical memory from physical memory this
separation allows an extremely large virtual memory to be provided for programmers when only a
smaller physical memory is available.
Virtual memory is commonly implemented by demand paging. It can also be implemented in a
segmentation system. Demand segmentation can also be used to provide virtual memory.

Demand Paging
A demand paging is similar to a paging system with swapping. When we want to execute a
process, we swap it into memory. Rather than swapping the entire process into memory. When a
process is to be swapped in, the pager guesses which pages will be used before the process is
swapped out again Instead of swapping in a whole process, the pager brings only those necessary
pages into memory. Thus, it avoids reading into memory pages that will not be used in anyway,
decreasing the swap time and the amount of physical memory needed.

Hardware support is required to distinguish between those pages that are in memory and those
pages that are on the disk using the valid-invalid bit scheme.

Where valid and invalid pages can be checked, checking the bit and marking a page will have no
effect if the process never attempts to access the pages. While the process executes and accesses
pages that are memory resident, execution proceeds normally. Access to a page marked invalid
causes a page-fault trap. This trap is the result of the operating system's failure to bring the desired
page into memory.

But page fault can be handled as following :

 An internal table for this process to determine whether the reference was a valid or invalid
memory access.
 If the reference was invalid, the process is terminated. If .it was valid, but we have not yet
brought in that page, we now page in the latter
 Find a free frame
 Schedule a disk operation to read the desired page into the newly allocated frame.
 When the disk read is complete, we modify the internal table kept with the process and the
page table to indicate that the page is now in memory.
 Restart the instruction that was interrupted by the illegal address trap. The process can
now access the page as though it had always been memory.

Therefore, the operating system reads the desired page into memory and restarts the process as
though the page had always been in memory.

The page replacement is used to make the frame free if they are not in used. If no frame is free
then other process is called in.

Page Replacement Algorithm

There are many different page replacement algorithms. We evaluate an algorithm by running it on
a particular string of memory reference and computing the number of page faults. The string of
 memory references is called reference string. Reference strings are generated artificially or by
tracing a given system and recording the address of each memory reference. The latter choice
produces a large number of data.

1. For a given page size we need to consider only the page number, not the entire address.
2. if we have a reference to a page p, then any immediately following references to page p will never
cause a page fault. Page p will be in memory after the first reference; the immediately following
references will not fault.

Eg:- consider the address sequence

0100, 0432, 0101, 0612, 0102, 0103, 0104, 0101, 0611, 0102, 0103, 0104, 0101, 0610, 0102,
0103, 0104, 0104, 0101, 0609, 0102, 0105 and reduce to 1, 4, 1, 6,1, 6, 1, 6, 1, 6, 1
To determine the number of page faults for a particular reference string and page replacement
algorithm, we also need to know the number of page frames available. As the number of frames
available increase, the number of page faulks will decrease.

The following are the algorithm for page replacement:

FIFO Algorithm
The simplest page-replacement algorithm is a FIFO algorithm. A FIFO replacement algorithm
associates with each page the time when that page was brought into memory. When a page must
be replaced, the oldest page is chosen. We can create a FIFO queue to hold all pages in memory.

The first three references (7, 0, 1) cause page faults, and are brought into these empty eg. 7, 0, 1,
2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1 and consider 3 frames. This replacement means that the next
reference to 0 will fault. Page 1 is then replaced by page 0.

Optimal Algorithm
An optimal page-replacement algorithm has the lowest page-fault rate of all algorithms. An
optimal page-replacement algorithm exists, and has been called OPT or MIN. It is simply.
Replace the page that will not be used for the longest period of time. The optimal page-
replacement algorithm is difficult to implement, because it requires future knowledge of the
reference string.
Now consider the same string with 3 empty frames.
The reference to page 2 replaces page 7, because 7 will not be used until reference 18, whereas
page 0 will be used at 5, and page 1 at 14. The reference to page 3 replaces page 1, as page 1 will
be the last of the three pages in memory to be referenced again. Optimal replacement is much
better than a FIFO.
 Least Recently Unit (LRU) Algorithm
The FIFO algorithm uses the time when a page was brought into memory; the OPT algorithm uses
the time when a page is to be used. In LRU replace the page that has not been used for the longest
period of time. LRU replacement associates with each page the time of that page's last use. When
a page must be replaced, LRU chooses that page that has not been used for the longest period of
time.

Let SR be the reverse of a reference string S, then the page-fault rate for the OPT algorithm on S is
the same as the page-fault rate for the OPT algorithm on SR

INPUT/OUTPUT (I/O) SYSTEMS

I/O with computer systems can be roughly grouped into three categories:

• Human readable: Suitable for communicating with the computer user. Examples include printers
and video display terminals, the latter consisting of display, keyboard, and perhaps other devices
such as a mouse.
• Machine readable: Suitable for communicating with electronic equipment. Examples are disk
and tape drives, sensors, controllers, and actuators.
• Communication: Suitable for communicating with remote devices. Examples are digital line
drivers and modems. But they differ in the form of application.
I/O Organization

Three techniques for performing I/O:

 Programmed I/O: The processor issues an I/O command, on behalf of a progress, to an
I/O module; that process then busy wait for the operation to be completed before
proceeding.

 Interrupt-driven I/O: The processor issues an I/O command on behalf of a process,

continues to execute subsequent instructions, and is interrupted by the I/O module.

 Direct Memory Access (DMA): A DMA module controls the exchange of data between
main memory and an I/O module. The DMA unit is capable of mimicking the processor
and, indeed, of taking over control of the system bus just like a processor. It needs to do
this to transfer data to and from memory over the system bus.

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:

 Whether a read or write is requested, using read or write control line between the processor
and the DMA module.
 The address of the I/O device involved, communicated on the data line.
 The starting location in memory to read from or write to, communicated on the data lines and
stored by the DMA module in its address register.
 The number of the word to be read or written, again communicated via the data lines and
stored in the data count register.

The DMA module transfers the entire block of data, one word at a time, directly to or from
memory, without going through the processor. When the transfer is complete , the DMA module
sends an interrupt signal to the processor. Thus, the processor is involved only at the beginning
and end of the transfer. The DMA module, uses programmed I/O to exchange data between
memory and an I/.O module through the DMA module.

The Evolution of the I/O Function

The processor directly controls a peripheral device. This is seen in simple microprocessor-
controlled devices. A controller or I/O module is added. The processor uses programmed I/O
without interrupts. The processor need not spend time waiting for an I/O operation to be
perforated, thus increasing efficiency. The I/O module is given direct control of memory via
DMA. It can now move a block of data to or from memory without involving the processor. The
I/O module is enhanced to become a separate processor. The I/O module has a local of its own.
With this architecture, a large set of I/O device can be controlled, with minimal processor
involvement.

Design Objectives
Two objectives are considered designing the I/O facility: efficiency and generality. Efficiency is
important because I/O operations often form a bottleneck in a computing system. I/O devices are
extremely slow compared with main memory and the processor. One way to tackle this problem is
multiprogramming, which, as we have seen, allows some processes to be waiting on I/O
operations while another process is executing. The other major objective is generality.

Some parts of the operating system must interact directly with the computer hardware. Generally
they follow following layer of involvement
• Logical I/O: The logical I/O module deals with the device as a logical resource and is not
concerned with the details of actually controlling the device. The logical I/O module is
concerned with managing general I/O functions on behalf of user processes, allowing them to
deal with the device in terms of a device identifier and simple commands such as open, close,
read, write.
• Device I/O: The requested operations and data (buffered characters, records, etc.) toe converted
into appropriate sequences of I/O instructions, channel commands, and controller orders.
Buffering techniques may be used to improve utilizations.
• Scheduling and Control: The actual queuing and scheduling of I/O operations occurs at this
layer, as well as the control of the operations. Thus, interrupts are handled at this layer and I/O
status is collected and reported. This is the layer of software that actually interacts with the I/O
module and hence the device hardware.
• Directory management: At this layer, symbolic file names are converted to identifiers that either
reference the file directly or indirectly through a file descriptor or index table.
• File system: This layer deals with the logical structure of files and with the operations that can
be specified by users, such as open, close, read, write. Access rights are also managed at this
layer.
• Physical Organization: Virtual memory addresses must be converted into physical main
memory addresses, taking into account the segmentation and paging structure, logical references
to files and records must be converted to physical secondary storage addresses, taking into
account the physical track and sector structure of the secondary storage device. Allocation of
secondary storage space and main storage buffers is generally treated at this layer as well.

Single Buffer
The simplest type of support that the operating system can provide is single buffer. When a user
process issues an I/O request, the operating system signs a buffer in file system portion of main
memory to the operation. For block-oriented devices, the single buffering scheme can be used.
The two main jobs of a computer are I/O and processing. In many cases, the main job is I/O and
the processing is merely incidental. For instance, when we browse a web page or edit a file, our
immediate interest is to read or type in some information.
The role of operating system in computer I/O is to manage and control I/O operations and I/O
devices. Although related topics appear in other chapters, here we bring together the pieces to
paint a complete picture. We discuss the I/O services that the operating system provides, and the
embodiment of these services in the application I/O interface. .

DISKS MANAGEMENT

The disk increase in the speed of processors and main memory has far outstripped that for disk
access, with processor and main memory speeds increasing by about two orders of magnitude
compared to one order of magnitude for disk.

Disk Performance Parameters:

When the disk drive is operating, the disk is rotating at constant speed. To read or write, the head
must be positioned at the desired track and at the beginning of the desired sector on that track.
Track selection involves moving the head in a movable-head system or electronically selecting
one head on a fixed-head system. On a movable-head system, the time it takes to position the head
at the track is known as seek time. When once the track is selected, the disk controller waits until
the appropriate sector rotates to line up with the head. The time it takes for the beginning of the
sector to reach the head is known as rotational delay, or rotational latency. The sum of the seek
time, if any, and the rotational delay equals the access time, which is the time it takes to get into
position to read or write. Once the head is in position, the read or write operation is then
performed as the sector moves under the head; this is the data transfer portion of the operation; the
time required for the transfer is the transfer time.

Seek Time Seek time is the time required to move the disk arm to the required track. It turns out
that this is a difficult quantity to pin down. The seek time consists of two key components: the
initial start-up time and the time taken to traverse the tracks that have to be crossed once the
access arm is up to speed.
Rotational Delay Disks, other than floppy disks, rotate at speeds ranging from 3600 rpm up to, as
of this writing, 15,000 rpm; at this latter speed, there is one revolution per 4ms. Thus, on the
average, the rotational delay will be 2ms. Floppy disks typically rotate at between 300 and 600
rpm. Thus the average delay will be between 100 and 50ms.
Transfer Time The transfer time to or from the disk depends on the rotation speed of the disk in
the following fashion:
First-In-First-Out The simplest form of scheduling is first-in-first-out (FIFO) scheduling, which
processes items from the queue in sequential order .This strategy has the advantage of being fair,
because every request is honoured and the requests are honoured in the order received. With
FIFO, if there are only a few processes that require access and if many of the requests are to
clustered file sectors, then we can hope for good performance.
Priority With a system based on priority (PRI), the control of the scheduling is outside the control
of disk management software.

Last In First Out ln transaction processing systems, giving the device to the most recent user
should result. In little or no arm movement for moving through a sequential file. Taking
advantage of this locality improves throughput and reduces queue length.
Shortest Service Time First The SSTF policy is to select the disk I/O request the requires the
least movement of the disk arm from its current position.

Performance
Once the basic disk methods are selected, there are still several ways to improve performance.
Most disk controllers include local memory to form an on-board cache that is sufficiently large to
store entire track a time. Once a seek is performed, the track is read into the disk cache starting at
the sector under the disk head. The disk controller then transfers any sector requests to the
operating system. Once blocks makes it from the disk controller into main memory, the operating
system may cache the bloc ks there. Some systems maintain a separate section of main for a disk
cache, where blocks are kept under the assumption that they will be used again shortly. Other
systems treat all physical memory as a buffer pool that is shared by the paging system and the
disk-block caching system. A system performing many I/O operations will use most of its
memory as a block cache, whereas a system executing i programs will use more memory as
paging space. Some systems optimize their disk cache by using different replace algorithms.
Another method of using main memory to improve performance is common on personal
computers. A. section of memory is set aside and treated as a virtual disk, or RAM disk. In this
case, a RAM disk device driver accepts all the standard disk operations, but performs those
operations on the memory section, instead of on a disk. All disk operations can then be executed
on this RAM disk and, except for the lightning-fast speed, users will not notice a difference. RAM
disks are useful only for temporary storage, since a power failure or a reboot of the system will
usually erase them. Commonly, temporary files such as intermediate compiler files are stored
there.

The difference between a RAM disk and a disk cache is that the contents of the RAM disk are
totally user controlled, whereas those of the disk cache are under the control of the operating
system. A RAM disk will stay empty until the user creates files there.

Disk Scheduling
One of the responsibilities of the operating system is t o use the hardware efficiently^For/the disk
drives, this means having a fast access time and disk bandwidth. The access time has two major
components. The seek time is the time for the disk arm to move the heads to the cylinder
containing the desired sector. The rotational latency is the additional time waiting for the disk to
rotate the desired sector to the disk head. The disk bandwidth is the total number of bytes
transferred, divided by the total time between the first request for service and the comple tion of
the last transfer.

The request specifies several pieces of information:

 Whether this operation is input or output
 What the disk address for the transfer is
 What the memory address for the transfer is
 What the number of bytes to be transferred is

If the desired disk drive and controller are available, the request can be serviced immediately. If
the drive or controller is busy, any new requests for service will need to be placed on the queue of
pending requests for that drive.

FCFS Scheduling
The simplest form of disk scheduling is, of course, first-come, first-served (FCFS). Consider, a
example, a disk queue with requests for I/O to blocks on cylinders 98,183, 37,122, 14,124, 65,
67. In that order. If the disk head is initially at cylinder 53, it will first move from 53 to 98, then to
183, 37,422, 14, 124, 65, and finally to 67, for a total head movement of 640 cylinders.
 SSTF Scheduling
It seems reasonable to service all the requests close to the current head position, before moving
the head far away to service other requests. This assumption is the basis for the shortest-seek-
time-first (SSTF) algorithm. The SSTF algorithm selects the request with the minimum seek time
from the current hea d position. Since seek time increases with the number of cylinders traversed
by the head, SSTF chooses the pending request closest to the current head position. SSTF
scheduling is essentially a form of shortest-job-first (SJF) scheduling, it may cause starvation of
some requests.

SCAN Scheduling
In the SCAN algorithm, the disk arm starts at one end of the disk, and moves toward the other
end, servicing requests as it reaches each cylinder, until it gets to the other end of the disk. At the
other end, the direction of head movement is reversed, and servicing continues. The head
continuously scans back and forth across the disk.
The SCAN algorithm is sometimes called the elevator algorithm.

C-SCAN Scheduling
Circular SCAN (C-SCAN) is a variant of SCAN that is designed to provide a more uniform wait
time. Like SCAN, C-SCAN moves the head from one end of the disk to the other servicing
requests along the way. When the head reaches the other end, it immediately returns to the
beginning of the disk, without; servicing any requests on the return trip

LOOK Scheduling
Both SCAN and C-SCAN move the disk arm across the full width of the disk. In practice, neither
algorithm is implemented this way. More commonly, the arm goes only as far as the final request
in each direction. Then, it reverses direction immediately, without first going all the way to the
end of the disk. These versions of SCAN and C-SCAN are called LOOK and C-LOOK

FILES AND FILE MANAGEMENT SYSTEMS

The most important parts of an operating system is the file system. The file system provides the
resource abstractions typically associated with secondary storage. The file system permits users to
create data collections, called files, with desirable properties, such as the following:
• Long-term existence: Files are stored on disk or other secondary storage and do not disappear
when a user logs off.
• Sharable between processes: Files have names and can have associated access permissions that
permit controlled sharing.
• Structure: Depending on the file system, a file can have an internal structure that is convenient
for particular applications. In addition, files can be organized into hierarchical or more complex
structure to reflect the relationships among files.
 Any file system provides not only a means to store data organized as files, but a collection of
functions that can be performed on files. Typical operations include the following:
• Create: A new file is defined and positioned within the structure of files.
• Delete: A file is removed from the file structure and destroyed.
• Open: An existing file is declared to be "opened" by a process, allowing the process to perform
functions on the file.
• Close: The file is closed with respect to a process, so that the process no longer may perform
functions on the file, until the process opens the file again.
• Read: A process reads all or a portion of the data in a file.
• Write: A process updates a file, either by adding new data that expands the size of the file or by
changing the values of existing data items in the file.

Typically, a file system maintains a set of attributes associated with the file

File Structure
Four terms are use for files
• Field
• Record
• Database

A field is the basic element of data. An individual field contains a single value. A record is a
collection of related fields that can be treated as a unit by some application program.
A file is a collection of similar records. The file is treated as a singly entity by users and
applications and may be referenced by name. Files have file names and maybe created and
deleted. Access control restrictions usually apply at the file level.
A database is a collection of related data. Database is designed for use by a number of different
applications. A database may contain all of the information related to an organization or project,
such as a business or a scientific study. The database itself consists of one or more types of files.
Usually, there is a separate database management system that is independent of the operating
system.

File Management Systems:

A file management system is that set of system software that provides services to users and
applications in the use of files. Following objectives for a file management system:
• To meet the data management needs and requirements of the user which include storage of data
and the ability to perform the aforementioned operations.
• To guarantee, to the extent possible, that the data in the file are valid.
• To optimize performance, both from the system point of view in terms of overall throughput.
• To provide I/O support for a variety of storage device types.
• To minimize or elimina te the potential for lost or destroyed data.
• To provide a standardized set of I/O interface routines to use processes.
TO provide I/O support for multiple users, in the case of multiple-user systems

Allocation Methods
The direct-access nature of disks allows us flexibility in the implementation of files. Three major
methods of allocating disk space are in wide use: contiguous, linked and indexed. Each method
has its advantages and disadvantages.

 Contiguous Allocation
The contiguous allocation method requires each file to occupy a set of contiguous blocks on the
disk. Disk addresses define a linear ordering on the disk. Contiguous allocation of a file is defined
by the disk address and length (in block units) of the first block.

The contiguous disk-space-allocation problem can be seen to be a particular application of the

general dynamic storage-allocation First Fit and Best Fit are the most common strategies used to
select a free hole from the set of available holes. Simulations have shown that both first-fit and
best-fit are more efficient than worst-fit in terms of both time and storage utilization. Neither first-
fit nor best-fit is clearly best in terms of storage utilization, but first-fit is generally faster. These
algorithms suffer from the problem of external fragmentation.

 Linked Allocation
Linked allocation solves all problems of contiguous allocation. With link allocation, each file is a
linked list disk blocks; the disk blocks may be scattered anywhere on the disk. There is no
external fragmentation with linked allocation, and any free! block on the free-space list can be
used to satisfy a request. Notice also that there is no need to declare the size of a file when that file
is created. A file can continue to grow as long as there are free blocks. Consequently, it is never
necessary to compact disk space. The major problem is that it can be used effectively for only
sequential access files.

 Indexed Allocation
Linked allocation solves the external-fragmentation and size-declaration problems of contiguous
allocation. 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 a nd need to be
retrieved in order Indexed allocation solves this problem by bringing all the pointers together into
one location.

Allocation supports direct access, without suffering from external fragmentation because any free
block on he disk may satisfy a request for more space. Indexed allocation does suffer from wasted
 space. The pointer overhead of the index block is generally greater than the pointer overhead of
linked allocation.

SECURITY
Projection can improve reliability by detecting latent errors at the interfaces between component
subsystems. Early detection of interface errors can often prevent contamination of a healthy
subsystem by a subsystem that is malfunctioning

A computer system is a collection of processes and objects. By objects, we mean both hardware
objects (such as the CPU, memory segments, printers, disks, tape drives), and software objects
(such as files, programs, and semaphore)

The Security Problem

The operating system can allow users to protect their resources. We say that a system is secure if
its resources art used and accessed as intended under all circumstances. Unfortunately, it is not
generally possible to achieve total security.

Security violations of the system can be categorized as being either intentional (malicious) or
accidental. Among the forms of malicious access are the following:
• Unauthorized reading of data (theft of information)
• Unauthorized modification of data
• Unauthorized destruction of data j
To protect the system, we must take security measures at two levels:
 Physical: The site or sites containing the computer systems must be physically secured
against armed or surreptitious entry by intruders.
 Human: Users must be screened carefully so that the chance of authorizing a user who
then gives access to an intruder (in exchange for a bribe, for example) is reduced.
Security at both levels must be maintained if operating-system security is to be ensured.

Authentication
A major security problem for operating systems is the authentication problem. The protection
system depends on an ability to identify the programs and processes that are executing.
Authentication is based on one or more of three items: user possession (a key or card), user
knowledge (a user identifier and password), and a user attribute (fingerprint) retina pattern, or
signature).

Passwords
The most common approach to authenticating a user identity is the use of user passwords. When
the user identifies herself by user ID or account name, she is asked for a password. If the user-
supplied password matches the password stored in the system.
Password Vulnerabilities
Although there are problems associated with their use, passwords are nevertheless extremely
common, because they are easy to understand and use. The problems with passwords are related
to the difficulty of keeping a password secret.
There are two common ways to guess a password. One is for the intruder (either human or
program) to know the user or to have information about the user. The other way is to use brute
force; trying all possible combinations of letters, numbers, and punctuation until the password is
found.
Passwords can be either generated by the system or selected by a user. System generated
passwords may be difficult to remember, and thus users may commonly write them down

Encrypted Passwords
One problem with all these approaches is the difficulty of keeping the password secret. The
UNIX system uses encryption to avoid the necessity of keeping its password list secret. Each user
has a password. The system contains a function that is extremely difficult (the designers hope
impossible) to invert, but is simple to compute.

One-Time Passwords
To avoid the problems of password sniffing and shoulder surfing, a system could use a set of
paired passwords. When a session begins, the system randomly selects and presents one part of a
password pair; the user must supply the other part. In this system, the user is challenged and must
respond with the correct answer to that challenge

This approach can be generalized to the use of an algorithm as a password. The algorithm might
be an integer function. In this one-time password system, the password is different in each
instance. Anyone capturing the password from one session and trying to reuse it in another session
will fail.

The user uses the keypad to enter the shared secret, also known as a personal identification
number (PIN). Another variation on one-time passwords is the use of a code book, or one time
pad.

Encryption
Encryption is one common method of protecting information transmitted over unreliable links.
The basic mechanism works as follows.

1. The information (text) is encrypted (encoded) from its initial readable form (called clear text),
to an internal form (called cipher text). This internal text form, although readable, does not
make any sense.
2. The cipher text can be stored in a readable file, or transmitted over unprotected channels.
3. To make sense of the cipher text, the receiver must decrypt (decode) it back into clear text.

Even if the encrypted information is accessed by an unauthorized person or program, it will be

useless unless it can be decoded.
CASE STUDY: UNIX AND WINDOW OPERATING SYSTEM

References:
[Link]
[Link]
[Link]
[Link]
[Link]/~jdmooney/classes/cs550/notes/tech/mutex/[Link]
[Link]