MEMORY MANAGEMENT the computer starts at 00000,

the first address of the user

Introduction process does not need to be
00000. This arrangement
The CPU can be shared by a set of affects the addresses that the
processes. As a result of CPU user program can use. In most
scheduling, we can improve both the cases, a user program will go
utilization of the CPU and the speed through several steps-some of
of the computer's response to its which may be optional-before
users. To realize this increase in being executed. Addresses may
performance, however, we must keep be represented in different
several processes in memory; that is, ways during these steps.
we must share memory. Therefore Addresses in the source program
main memory has to be properly are generally symbolic (such as
managed by Operating systems. count). A compiler will
Various memory management typically bind these symbolic
algorithms are used by OS from addresses to relocatable
simple methods to complex paging addresses (such as "14 bytes
and segmentation strategies. Each from the beginning of this
approach has its own advantages module"). The linkage editor or
and disadvantages. loader will in turn bind these
relocatable addresses to absolute
addresses (such as 74014).
Background Each binding is a mapping
from one address space to
Memory is central to the operation of a another.
modern computer system. Memory
consists of a large array of words or
bytes, each with its own address.
The CPU fetches instructions from
memory according to the value of the
program counter. The execution of
instructions may cause additional
loading from and storing to specific
memory addresses.

Address Binding

Usually, 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 collection of
processes on the disk that is Classically, the binding of instructions
waiting to be brought into and data to memory addresses can be
memory for execution forms the done at any step along the way:
input queue.
Compile time: If you know at compile
Most systems allow a user time where the process will reside in
process to reside in any part of memory, then absolute code can be
the physical memory. Thus, generated. For example, if you know a
although the address space of priori that a user process resides
starting at location R, then the physical addresses is done by a
generated compiler code will start at hardware device called the memory-
that location and extend up from there. management unit (MMU). A simple
If, at some later time, the starting MMU scheme is shown here.
location changes, then it will be
necessary to recompile this code. The
This method requires hardware
MS-DOS .COM-format programs are
support slightly different from the
absolute code bound at compile time.
hardware configuration. The base
register is called a relocation register.
Load time: If it is not known at compile The value in the relocation register is
time where the process will reside in added to every address generated by a
memory, then the compiler must user process at the time it is sent to
generate relocatable code. In this case, memory. For example, if the base is at
final binding is delayed until load time. 14000, then an attempt by the user
If the starting address changes, we to address location 0 is dynamically
need only to reload the user code to relocated to location 14000; an access
incorporate this changed value. to location 346 is mapped to location
14346. Thus the user program deals
Execution time: If the process can be with logical addresses. The memory-
moved during its execution from one mapping hardware converts logical
memory segment to another, then addresses into physical addresses.
binding must be delayed until run time. This form of execution-time binding is
Special hardware must be available for shown in the figure above. The final
this scheme to work. Most general- location of a referenced memory
purpose operating systems use this address is not determined until the
method. reference is made.

Logical Versus Physical Address Space We have two different types of

addresses: logical addresses (in the
An address generated by the CPU is range 0 to max) and physical
commonly referred to as a logical addresses (in the range R + 0 to R +
address, whereas an address seen by max for a base value R). The user
the memory unit-that is, the one loaded generates only logical addresses and
into the memory-address register of thinks that the process runs in
the memory-is commonly referred to as locations 0 to max. The user program
a physical address. supplies logical addresses; these
logical addresses must be mapped to
physical addresses before they are
The compile-time and load-time used. The concept of a logical-
address-binding methods generate address space that is bound to a
identical logical and physical separate physical address space is
addresses. However, the execution-time central to proper memory management.
address binding scheme results in
differing logical and physical addresses.
Overlays
To enable a process to be larger than
We use logical address and virtual
the amount of memory allocated to it,
address interchangeably. The set of all
we can use overlays. The idea of
logical addresses generated by a
overlays is to keep in memory only
program is a logical-address space;
those instructions and data that are
the set of all physical addresses
needed at any given time. When other
corresponding to these logical
instructions are needed, they are
addresses is a physical-address space.
loaded into space occupied previously
Thus, in the execution- time address-
by instructions that are no longer
binding scheme, the logical- and
needed.
physical-address spaces differ.

Swapping
The run-time mapping from virtual to
 Allocation
A process needs to be in memory to
be executed. A process, however, can I. Contiguous Memory Allocation
be swapped temporarily out of
memory to a backing store, and then In contiguous memory allocation, each
brought back into memory for process is contained in a single
continued execution. For example, in a contiguous section of memory by the
multiprogramming environment with a OS.
round-robin CPU-scheduling algorithm,
when a quantum expires, the memory
TWO TYPES:
manager will start to swap out the
process that just finished, and to swap • Fixed Partitioning
in another process to the memory space • Dynamic Partitioning
that has been freed. In the meantime,
the CPU scheduler will allocate a time
Fixed Partitioning
slice to some other process in memory.
When each process finishes its
quantum, it will be swapped with In this scheme for memory
another process. Ideally, the memory management, we can assume that
manager can swap processes fast the OS occupies some fixed portion
enough that some processes will be in of main memory and that the rest of
memory, ready to execute, when the main memory is available for use by
CPU scheduler wants to reschedule the multiple processes. The simplest
CPU. The quantum must also be scheme for managing this available
sufficiently large that reasonable memory is to partition it into
amounts of computing are done regions with fixed boundaries.
between swaps.
PARTITION SIZES: Figure below shows
examples oftwo alternatives for fixed
partitioning.

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- One possibility is to make use of equal-
priority process so that it can load and size partitions. In this case, any
execute the higher-priority process. process whose size is less than or
When the higher-priority process equal to the partition size can be
finishes, the lower-priority process loaded into any available partition. If
can be swapped back in and all partitions are full and no process is
continued. This variant of swapping is in the Ready or Running state, the
sometimes called roll out, roll in. operating system can swap a process
out of any of the partitions and load in
Memory Management Schemes another process, so that there is some
work for the processor.
There are various memory
management schemes that are There are two difficulties with the use of
employed by modern operating equal-size fixed partitions:
systems to place processes in the main
memory for getting executed by the CPU • A program may be too big to fit into a
partition. In this case, the programmer
TWO TYPES: must design the program with the use
I. Contiguous Memory of overlays so that only a portion of the
Allocation program need be in main memory at
any one time. When a module is
II. Non-Contiguous Memory needed that is not present, the user’s
program must load that module into the point is reached at which none of the
program’s partition, overlaying whatever processes in main memory is ready, but
programs or data are there. process 2, in the Ready-Suspend state,
is available. Because there is
• Main memory utilization is insufficient room in memory for
extremely inefficient. Any program, no process 2, the operating system
matter how small, occupies an entire swaps process 1 out (g) and swaps
partition. In our example, there maybe a process 2 back in (h).
program whose length is less than 2
Mbytes; yet it occupies an 8-Mbyte As this example shows, this method
partition whenever it is swapped in. This starts out well, but eventually it leads
phenomenon, in which there is wasted to a situation in which there are a lot of
space internal to a partition due to the small holes in memory. As time goes on,
fact that the block of data loaded is memory becomes more and more
smaller than the partition, is referred to fragmented, and memory utilization
as internal fragmentation. declines. This phenomenon is
referred to as external fragmentation,
Both of these problems can be lessened, indicating that the memory that is
though not solved, by using unequal external to all partitions becomes
size partitions. In this example, increasingly fragmented.
programs as large as 16 Mbytes can
be accommodated without overlays. One technique for overcoming external
Partitions smaller than 8 Mbytes allow fragmentation is compaction: From
smaller programs to be time to time, the OS shifts the
accommodated with less internal processes so that they are contiguous
fragmentation and so that all of the free memory is
together in one block. For example, in
Dynamic Partitioning (Variable Figure 7.4h , compaction will result in a
Partitioning) block of free memory of length 16M.
This may well be sufficient to load in
To overcome some of the difficulties an additional process. The difficulty
with fixed partitioning, an approach with compaction is that it is a time
known as dynamic partitioning was consuming procedure and wasteful of
developed. This approach has been processor time. Compaction demands
supplanted by more sophisticated the need for a dynamic relocation
memory management techniques. With capability.
dynamic partitioning, the partitions are
of variable length and number. When a
process is brought into main memory, PLACEMENT ALGORITHM:
it is allocated exactly as much memory Because memory compaction is time
as it requires and no more. consuming, the OS designer must be
For e.g, using 64 Mbytes of main clever in deciding how to assign
memory, is shown in Figure 7.4 . Initially, processes to memory (how to plug the
main memory is empty, except for the holes). When it is time to load or swap a
OS (a). The first three processes are process into main memory, and if there
loaded in, starting where the operating is more than one free block of memory
system ends and occupying just enough of sufficient size, then the operating
space for each process (b, c, d). This system must decide which free block to
leaves a “hole” at the end of memory allocate.
that is too small for a fourth process.
At some point, none of the processes Three placement algorithms that might
in memory is ready. The operating be considered are best-fit, first-fit, and
system swaps out process 2 (e), next-fit. All are limited to choosing
which leaves sufficient room to load a among free blocks of main memory that
new process, process 4 (f). Because are equal to or larger than the process
process 4 is smaller than process 2, to be brought in. Best-fit chooses the
another small hole is created. Later, a
block that is closest in size to the processor time.
request. First- fit begins to scan
memory from the beginning and 2. Non Contiguous Allocation
chooses the first available block that
is large enough. Next-fit begins to Another possible solution to the
scan memory from the location of the external-fragmentation problem is to
last placement, and chooses the next permit the physical - address space of
available block that is large enough. a process to be non contiguous. Thus
allowing a process to be allocated
physical memory wherever the latter is
EXAMPLE: Figure 7.5a shows an available. Two complementary
example memory configuration after techniques achieve this solution:
a number of placement and swapping- paging and segmentation.
out operations. The last block that was
used was a 22-Mbyte block from which Non Contiguous Allocation
a 14-Mbyte partition was created.
Figure 7.5b shows the difference 1. PAGING
between the best-, first-, and next-fit
placement algorithms in satisfying a Introduction
16-Mbyte allocation request. Best-fit will
search the entire list of available Both unequal fixed-size and variable-
blocks and make use of the 18-Mbyte size partitions are inefficient in the
block, leaving a 2-Mbyte fragment. First- use of memory. The former results in
fit results in a 6-Mbyte fragment, and internal fragmentation, the latter in
next-fit results in a 20-Mbyte fragment. external fragmentation. Suppose, if,
Disadvantage of Dynamic Allocation- that main memory is partitioned into
External fragmentation. equal fixed-size chunks that are
relatively small, and that each
Though dynamic allocation starts out process is also divided into small
well, but eventually it leads to a fixed-size chunks of the same size.
situation in which there are a lot of Then the chunks of a process, known
small holes (free memory blocks) in as pages, could be assigned to
memory. As time goes on, memory available chunks of memory, known as
becomes more and more fragmented, frames, or page frames. Therefore the
and memory utilization declines. This wasted space in memory for each
phenomenon is referred to as process is due to internal
external fragmentation, indicating fragmentation consisting of only a
that the memory that is external to all fraction of the last page of a
partitions becomes increasingly process. There is no external
fragmented. fragmentation.

TWO REMEDIES Method

1. Compaction Paging is a memory-management

scheme that permits the physical-
One technique for overcoming address space of a process to be
external fragmentation is compaction. non- contiguous. Physical memory is
That is from time to time, the OS broken into fixed-sized blocks called
shifts the processes so that they are frames. (size is power of 2, between
contiguous and so that all of the free 512 bytes and 8192 bytes). Logical
memory is together in one block. It will memory is also broken into blocks of
result in a block of free memory of the same size called pages. When a
length 16M. This may well be process is to be executed, its pages
sufficient to load in an additional are loaded into any available memory
process. The difficulty with frames from the backing store. The
compaction is that it is a time backing store is divided into fixed-
consuming procedure and wasteful of sized blocks that are of the same size
as the memory frames. arrays.

OS keep track of all free frames. In segmentation, the logical-address

To run a program of size n pages, space is considered as a collection of
need to find n free frames and segments. Each segment has a name
load program. A page table is set
and a length. The addresses specify
up to translate logical to physical
both the segment name and the offset
addresses. It contains the frame
number corresponding to each within the segment.
page.
The user therefore specifies each
OS use hardware support for paging. address by two quantities:
ow: a segment name and an offset.

The selection of a power of 2 as a

For simplicity of implementation,
page size makes the translation of
segments are numbered and are
a logical address into a page
number and page offset particularly referred to by a segment number, rather
easy. If the size of logical-address than by a segment [Link], Logical
address consists of a two tuple:
space is 2m, and a page size is 2n
addressing units (bytes or words), <segment-number, offset>,
then the high-order m - n bits of a
logical address designate the page • Segment table - maps two-
number, and the n low-order bits dimensional physical addresses;
designate the page offset. each table entry has:
o base - contains the
Thus, the logical address is as follows: starting physical address
where p is an index into the page where the segments
table and d is the displacement
reside in memory.
within the page. Every address
generated by CPU is divided into: o limit - specifies the length
of the segment.

The use of a segment table is

This base address is combined with illustrated in Figure above. A logical
the page offset to define the physical address consists of two parts: a
memory address that is sent to the
segment number, s, and an offset into
memory unit. The paging model of
that segment, d. The segment number
memory is shown in below
is used as an index into the segment
When we use apaging scheme, we
table. The offset d of the logical
have no external fragmentation: Any
address must be between 0 and the
free frame can be allocated to a
process that needs it. However, we segment limit. If it is not, we trap to
may have some internal fragmentation. the operating system (logical
addressing attempt beyond end of
segment). If this offset is legal, it is
added to the segment base to produce
2. SEGMENTATION
the address in physical memory of the
desired byte. The segment table is thus
Segmentation is a memory-
essentially an array of base-limit register
management scheme that supports
user view of memory. A program is a pairs.
collection of segments. A segment is
a logical unit such as: main program, We have five segments numbered from
procedure, function, method, object, 0 through 4. The segments are stored
local variables, global variables, in physical memory as shown. The
common block, stack, symbol table, segment table has a separate entry for
each segment, giving the beginning needed for CPU. Thus a lazy swapper
address of the segment in physical never swaps a page into memory
memory (or base) and the length of unless that page will be needed.
that segment (or limit).
The process of loading the
page into memory on demand
For example, segment 2 is 400 bytes
(whenever page fault occurs) is known
long and begins at location 4300. Thus, as demand paging.
a reference to byte 53 of segment 2 is
mapped onto location 4300 + 53 = 4353. Demand Paging Example
A reference to segment 3, byte 852, is
mapped to 3200 (the base of segment 3) Consider a process visualized
+ 852 = 4052. A reference to byte 1222 in logical memory shown in figure
of segment 0 would result in a trap to below. Presently only the pages 0,2
the operating system, as this segment and 5 are loaded in the main memory.
is only 1,000 bytes long. There is a page table associated with
Virtual Memory each process. With each page table
entry a valid-invalid bit is associated.
What is Virtual Memory? This bit has the following values : (1 →
in-memory, 0 → not-in-memory).
Virtual Memory is a storage scheme
that provides user an illusion of having For all pages in main memory,
a very big main memory. This is done there will be frame number
by Operating Systems by treating a part associated with it and valid- invalid
of secondary memory as the main bit is set to 1. All other will
memory. If a process is bigger than behaving its value as 0
available main memory it can be
executed.

The Operating System can load the

different parts of more than one
process in the main memory. By doing
this, the degree of multiprogramming
will be increased and therefore, the CPU
utilization will also be increased.

Virtual memory is implemented using

Demand Paging.

Demand Paging:

A demand-paging system is a • If there is ever a

non contiguous memory allocation reference to a page,
method. It is similar to a paging first reference will trap
system with swapping. Processes to page table.
reside on secondary memory (which is
usually a disk). Processes are • If the page table has no frame
considered to be a collection of PAGES. number and valid-invalid bit =0 a
Physical memory is considered to be page fault occurs.
composed of a collection of FRAMES. • When a page fault occurs, the
OS will try to find (get) an
Only the important pages of a empty frame in the physical
process that is needed for execution
memory.
by CPU will be loaded into memory
frames. A lazy swapper (pager) is • The required page will be located
assigned to bring the pages into the in disk(virtual memory)
memory from the disk whenever it is • It is then swapped into the empty
 frame.
• Page table is updated with
necessary updating of frame
number for the page and also
the validation bit is made equal
to 1.

. Page Replacement Algorithms

In Demand paging, when a page

fault occurs, the OS tries to solve it by
bringing the desired page from disk
into an empty frame available in the
main memory. But it may happen that
there will not be any empty frame
available.

In this circumstance, the OS

has to swap a page in memory frame
Advantages : (called victim frame) into the disk and
create an empty frame. This
More processes maybe maintained identification of victim frame is done by
in the main memory: OS using a Page Replacement algorithm.
A process maybe larger than the
main memory can be executed. Different page replacement
algorithms suggest different ways to
The degree of multiprogramming is
decide which page to replace. The
increased.
target for all algorithms is to reduce the
number of page faults.
Page Fault Service Time : The time
taken to service the page fault is
1. First In First Out (FIFO) Page
called page fault service time.
Replacement Algorithm:
Thrashing : It is often found that when
the page fault and swapping happens This is the simplest page replacement
very frequently at a higher rate, the algorithm. In this algorithm, the
operating system has to spend more operating system keeps track of all
time swapping these pages. This state pages in the memory in a queue; the
in the operating system is known as oldest page is in the front of the
thrashing. Because of thrashing, the queue. When a page needs to be
CPU utilization is going to be reduced or replaced page in the front of the
negligible. queue is selected for removal.
Example 1: Consider page reference
string 1, 3, 0, 3, 5, 6, 3 with 3 page
frames. Find the number of page faults.
 references 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0,
3, 2, 3 with 4 page frame. Find
number of page fault.

Explanation:
• Initially, all slots are empty, so
Explanation: when 7 0 1 2 are allocated to the
• Initially, all slots are empty, so empty slots → 4 Page faults
when 1, 3, 0 came they are • Next for 0 , as it is already there so
allocated to the empty slots → → 0 Page fault.
3 Page Faults.
• When 3 came it will take the place
• When 3 comes, it is already in of 7 because it is not used for the
memory so → 0 Page Faults. longest duration of time in the
• Then 5 comes, it is not available future.—>1 Page fault.
in memory so it replaces the • Next, 0 is already there so —> 0
oldest page slot i.e 1. → 1 Page Page fault.
Fault.
• Next, 4 will takes place of 1 —> 1
• When 6 comes, it is also not Page Fault.
available in memory so it
• Now for the further page
replaces the oldest page slot i.e
reference string —> 0 Page
3 → 1 Page Fault.
fault because they are already
• Finally, when 3 come it is not available in the memory.
available so it replaces 0 → 1
page fault. Optimal page replacement is perfect,
but not possible in practice as the
Belady’s anomaly operating system cannot know future
requests. The use of Optimal Page
It is a problem with FIFO method. It is replacement is to setup a benchmark
proved that it is possible to have more so that other replacement algorithms
page faults when increasing the can be analyzed against it.
number of page frames while using the
First in First Out (FIFO) page 3. Least Recently
replacement algorithm. For example, if Used Page
we consider reference strings 3, 2, 1, 0, Replacement
3, 2, 4, 3, 2, 1, 0, 4, and 3 slots, we get Algorithm:
9 total page faults, but if we increase In this algorithm, page will be replaced
slots to 4, we get 10- page faults. which is least recently used.

Example-3: Consider the page

2. Optimal Page Replacement Page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2,
Replacement Algorithm: 3, 0, 3, 2, 3 with 4 page frames. Find
In this algorithm, pages are number of page faults.
replaced which would not be
used for the longest duration of
time in the future.
Example-2: Consider the page
 • Address •
• Current length •
• Maximum length
Operation performed on directory are:
• Search for a file •
• Create a file •
• Initially, all slots are empty,
so when 7 0 1 2 are • Delete a file •
allocated to the empty slots
→ 4 Page faults A directory is a container that
• As 0 is already there so →0 is used to contain folders
Page fault. and files. It organizes files
and folders in a hierarchical
• When 3 came it will take the manner.
place of 7 because it is
least recently used →1
Page fault
• As 0 is already in memory so →
0 Page fault.
• Next, 4 will takes place of 1 →
1 Page Fault. There are several logical structures of a
• Now for the further page directory
reference string → 0 Page • Single-level directory
fault because they are
already available in the • Two-level directory
memory. Tree-structured directory
What is a File? SINGLE LEVEL DIRECTORY
A file is a collection of Single-level directory -
related information that is • The single-level directory is
recorded on secondary the simplest directory structure.
storage. Or
In it, all files are contained in the
A file is a collection of logically same directory. In this,a single
related entities directory is maintained for all the
The name of the file is divided into users.
two parts as shown below:
• Naming problem: Users
• name cannot have same name for two
extension, separated by a period. files in a directory.
Example: palindrome.c • Grouping problem: Users
FILE DIRECTORIES: cannot group files according to
their need.
Collection of files is a file
directory. The directory contains
information about the files,
including attributes, location
and ownership. Much of this
directory information is
managed by the operating system.
Information contained in a device TWO-LEVEL DIRECTORY
directory are: In this separate directory for each
user is maintained.
• Name Path name: Due to two levels there
• Type is a path name for every file to locate
 that file. time of file creation.
Now, we can have same filename for
different [Link] is efficient in
this method.

TREE-STRUCTURED DIRECTORY:
• Directory is maintained in
the form of a tree.

The File allocation table contains

the entries:
• Address of starting block
• Length of the allocated portion.
Advantages:
• Both the Sequential and Direct
Searching is efficient and also
Accesses are supported by this.
there is grouping capability.
• This is extremely fast since the
We have absolute or relative path
number of seeks are minimal
name for a file.
because of contiguous allocation
of file blocks.
FILE ALLOCATION METHODS Disadvantages:
The allocation methods define how the • This method suffers from both
files are stored in the disk blocks. internal and external fragmentation.
There are three main disk space or file
• This makes it inefficient in terms
allocation methods.
of memory utilization.
• Contiguous • With it is difficult to
Allocation accommodate big files when
• Linked Allocation continuous blocks are not
• Indexed Allocation available.
The main idea behind these methods is
to provide: 2. Linked List Allocation
• Efficient disk In this scheme, each file is a linked list
space utilization. of disk blocks which need not be
• Fast access to the contiguous.
file blocks.
The disk blocks can be scattered
1. Continuous Allocation anywhere on the disk. The directory
A single continuous set of blocks in entry contains a pointer to the starting
the disk is allocated to a file at the and the ending file block. Each block
contains a pointer to the next block the blocks occupied by the file
occupied by the file. and therefore provides fast
Advantages: access to the file blocks.
• It overcomes the problem of
• This is very flexible in terms of file
external fragmentation.
size.
Disadvantages:
• File size can be increased easily
since the system does not have • The pointer overhead for indexed
to look for a contiguous chunk of allocation is greater than linked
memory. allocation.
• This method does not suffer from • More blocks has to be
external fragmentation. assigned for index block
thereby memory utilization
• This makes it relatively better in
decreases.
terms of memory utilization.
Disadvantages:
File Access Methods
• Because the file blocks are
distributed randomly on the disk, a
To read/write information
large number of seeks are needed to
from/to a file there are
access every block individually.
several ways to access the
• This makes linked allocationslower. file. They are known as file
• It does not support random or direct access methods.
access.
Three important methods are:
• We cannot directly access the blocks
of a file. Sequential-Access
Method
• A block k of a file can be
accessed by traversing k blocks Direct Access
sequentially (sequential access) Method
from the starting block of the file via Index sequential
block pointers. Method.
• Pointers required in the linked Sequential-Access Method
allocation incur some extra overhead. • Data is accessed one record
right after another record in an
3. Indexed order. When we use read
Allocation command, it move ahead pointer
A special block known as the Index by one.
block contains the pointers to all the
blocks occupied by a file. Each file has
its own index block. The ith entry in the
index block contains the disk address of
the ith file block.

• When we use write command, it

will allocate memory and move
the pointer to the end of the file
.Such a method is reasonable for
tape.
Advantages :
Advantages: • It is simple to implement
• This supports direct access to • It quickly accesses the next
 entry. File operations must be
Disadvantages: controlled:
• Time consuming to locate an Read - Reading from a file.
item. Write - Writing or rewriting the
• Moving a sizable chunk of the file.
file may be necessary to insert a Execute - Loading the file and
new record. executing it.
Direct Access Method Append - Writing the new
information to the already
existing file, editing must be end
Also known as relative access
at the end of the existing file.
method. It allows reading / writing a
block/record on any order. The Delete - Deleting the file which
direct access to the specific block is of no use and using its
is allowed.i.e. read block 17, then space for the another data.
read block 56,then write block 13 etc List - List the name and
… attributes of the file.
Operations like renaming, editing
the existing file, copying; these can
also be controlled.
There are many protection mechanism
OS uses.

[Link] Control Mechanism :

A list named as Access-Control

List (ACL) is maintained. It specify
3 . Index sequential method the names of the users and the
It is built on the top of the types of access associate with
sequential access method. each of the [Link] such
These methods construct an a variable lengthy list is tedious and
index for the file. To find a consumes much space in systems.
record in the file, we first search
the index, and then by the help Improvement
of pointer we access the file Condense the length of the
directly. access-control [Link] systems
recognize three classification of
users in connection with each file:
Owner - Owner is the user who has
created the file.
Group - A group is a set of members
who has similar needs and they are
sharing the same file.
Universe - In the system, all other
users are under the category called
universe.
File protection
The most common recent
Files have to be kept safe from approach is to combine access-
improper access by unauthorized control lists with the normal
users. In multiuser environment, not general owner, group, and universe
all users must be given access for access control scheme.
different types of operations in a file.
Other Protection Approaches: Disk Access Time = Seek Time +
The access to any system is also Rotational Latency + Transfer Time
controlled by the password. If the use
of password is random and it is Disk Scheduling
changed often, this may be result in Disk scheduling is done by operating
limit the effective access to a file. systems to schedule I/O requests
arriving for I/O in the disk. Disk
The use of passwords has a few scheduling is also known as I/O
disadvantages: scheduling. Multiple I/O requests may
The number of passwords are very arrive by different processes and only
large so it is difficult to remember one I/O request can be served at a
the large passwords. If one password time by the disk controller. Thus other
is used for all the files, then once it is I/O requests need to wait in the waiting
discovered, all files are accessible; queue and need to be scheduled.
protection is on all-or-none basis. Disk Scheduling Algorithms
File Recovery To improve efficiency of servicing I/O
What is file recovery in operating request, when two or more request
system? comes, the OS schedules disk arm
movement based on a disk scheduling
File recovery is the process of
algorithm.
restoring data that has been lost,
accidentally deleted, corrupted or
made inaccessible. In enterprise IT, 1. FCFS Scheduling
data recovery typically refers to the FCFS is the simplest of all the
restoration of data to a desktop, Disk Scheduling Algorithms. In
laptop, server or external storage FCFS, the requests are addressed
system from a backup. in the order they arrive in the disk
queue.
Suppose the order of request is-
Secondary Storage management (82,170,43,140,24,16,190) And
Secondary memory is the permanent current position of Read/Write
storage of data and in bulk quantity. head is : 50
Usually a Hard Disk Drive (HDD) The
acts as the fixed secondary storage movement
drive in a computer. An OS manages of RW
the hard disk efficiently. head is as
follows
The disk is divided into tracks. Each
track is further divided into sectors. The
intersection creates a block called track
-sector as shown below. Read-Write(R-
W) head moves over the rotating hard
disk.
Terms :
Seek time - The time taken by the R-W
head to reach the desired track from
its current position.
Rotational latency - Time is taken by the
sector to come under the R-W head.
Data transfer time - Time is taken to So, total seek time:
transfer the required amount of data. =(82-50)+(170-82)+(170-43)+(140-
It depends upon the rotational speed. 43)+(140-24)+(24-16)+(190-16)
=642 In SCAN algorithm the disk arm moves
Advantages: into a particular direction and services
the
Every request gets a fair chance No
indefinite postponement requests coming in its path and
after reaching the end of disk, it
Disadvantages: reverses its direction and again
Does not try to optimize seek time services the request arriving in its
May not provide the best possible path. So, this algorithm also known
service as elevator algorithm. As a result, the
requests at the midrange are serviced
2. SSTF (Shortest Seek Time First) more and those arriving behind the
scheduling disk arm will have to wait.
Here requests having shortest seek
time are executed first. So, the seek Suppose the requests to be addressed
time of every request is calculated in are 82,170,43,140,24,16,190.
advance in the queue. They are And the Read/Write arm is at 50, It is
scheduled according to their also given that the disk arm should
calculated seek time. As a result, the move“towards the larger value”.
request near the disk arm will get
executed first. SSTF is certainly an
improvement over FCFS as it
decreases the average response time
and increases the throughput of
system.

Example:
Suppose the order of request is-
(82,170,43,140,24,16,190) And current Therefore, the seek time is calculated
position of Read/Write head is : 50 as: =(199-50)+(199-16)
=332

Advantages:
High throughput Low variance of
response time Average response time

Disadvantages:
Long waiting time for requests for
So, total seek time: locations just visited by disk arm
=(50-43)+(43-24)+(24-16)+(82-16)+(140- 4. CSCAN
82)+(170-140)+(190-170) =208 CSCAN algorithm is similar to SCAN
Advantages: with a minor [Link] reaching
Average Response Time decreases the end in
Throughput increases Disadvantages: one direction instead of reversing its
Overhead to calculate seek time in direction of scanning , it goes to the
advance other end of
Can cause Starvation for a request if the disk and starts servicing the
it has higher seek time as compared requests from there. So, the disk arm
to incoming requests. moves in a circular fashion .Hence it is
3. SCAN Scheduling known as C-SCAN (Circular SCAN).
Example:
Suppose the
requests to be
addressed are-
82,170,43,140,24,16,
190. And the
Read/Write arm is
at 50, So, the seek time is calculated as: =(190-
and it is also given that the disk arm 50)+(190-16)
should move “towards the larger value”. =314

RAID
(Redundant Arrays of Independent
Disks)
A technique which makes use of a
combination of multiple disks instead
of using a single disk for:
1. Increased performance
Fast storing and
retrieval of data
from storage to
CPU
Seek time is calculated as: =(199- 2. Data redundancy
50)+(199-0)+(43-0) =391 Same data is
5. LOOK backed up for
data reliability
It is similar to the SCAN disk onto another disk.
scheduling algorithm except for the Thus data loss
difference .Here the disk armin spite can be prevented
of going to the end of the disk goes on failure of any
only to the last request to be main disk.
serviced in front of the head and then
reverses its direction from there only.
Different RAID levels
Thus it
prevents the extra delay which 1. RAID-0 (Stripping)
occurred due to unnecessary
traversalto the end of the disk.
Example:
Suppose the
requests to be
addressed are-
82,170,43,140,24,16,
190. And the
Read/Write arm is
at 50. RAID 0 (disk striping) is the process of
dividing(stripping) a body of data into
It is also given that the disk arm should
blocks and spreading the data blocks
move “towards the larger value”.
across multiple disk. RAID 0 offers the
best performance and capacity but no
fault tolerance.
2. RAID 1 (mirrored disks)

Disk management
Disk management of the operating
It duplicates(mirrors) the data across system includes:
two disks in the array, providing full Disk Formatting
redundancy. Both disks store exactly
the same data, at the sametime, and Divides
at all times. RAID 1 is the disk into
tracks and
primarily for redundancy. If you
sectors during
completely lose a drive, you can
installation
still stay up and running off the
Booting from
other drive.
disk
When the computer is
3. RAID 5 turned on or restarted,
(striped disks with single parity) the program stored in
RAID 5 is disk striping with parity. With the initial bootstrap
this level of RAID, data is striped ROM finds the location
across three or more disks, with parity of the OS kernel from
information stored across multiple the disk, loads the
disks. Parity information is a kernel into memory, and
calculated value that's used to restore runs the OS.
data from the other drives if one of the Bad block recovery
drives in Errors in bad sectors are
the set fails. recovered frequently by
OS

I/O MANAGEMT
I/O Requests are managed by
Operating [Link] manages
the I/0 hardware in a computer
system to perform it efficiently.
I/O Hardware
4. RAID 10 (Or RAID 1+0) Stripping with I/O Hardware is a set of
Mirroring specialized hardware devices
that help the OS access disk
This level Combines RAID 1 and drives, printers, and other
RAID 0 in a single system, which peripherals. These devices are
offers higher performance than RAID 1, located inside the
but at a much higher cost. This is a motherboard and connected to the
nested or hybrid RAID configuration. It processor using a bus. They often
provides security by mirroring all data have specialized controllers that allow
on secondary drives while using striping them to quickly respond to requests
across each set of drives to speedup from software.
data transfers.
 management.
• To control task management.

What is Kernel I/O Subsystem?

The kernel of an OS provides
many services related to I/O. The
kernel has an I/O subsystem built
on the hardware and device-driver
infrastructure that provides several
functions, including I/O scheduling,
A computer system contains CPUs
buffereing, caching, spooling,
and more than one device controllers
device reservation, error handling
connected to a common bus channel.
and I/O protection. The I/O
The device driversof OS control the
subsystem is also responsible for
device controllers . These device drivers
protecting itself from errant
provide an interface to I/O devices for
processes and malicious users.
communicating with the system
hardware promoting ease of
communication providing access to
shared memory. They are present in the
kernel of OS.
I/O Interface:
There is need of surface whenever
any CPU wants to communicate with
I/O devices. The interface is used to
interpret address which is generated
by CPU. Thus, surface is used to
communicate to I/O devices i.e. to
share information between CPU and
I/O devices
interface is used which is called asI/O
Interface.

KERNEL OF OS

Kernel is central component

of an OS that manages
operations of computer and
hardware. It basically
manages operations of
memory and CPU time. It is
core
component of an operating system.
Objectives of Kernel:
• To establish communication
between user level application
and hardware.
• To decide state of incoming
processes.
• To control disk management.
• To control memory