Rashtreeya Sikshana Samithi Trust

RV Institute of Technology and Management®

(Affiliated to VTU, Belagavi)

JP Nagar, Bengaluru – 560076

Department of Computer Science and Engineering

Course Name: Operating Systems

Course Code: BCS303
III
Semester
2022 Scheme
Usm

CPU
 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

Module IV
4.1Memory Management
Memory management is concerned with managing the primary memory. Memory consists of
array of bytes or words each with their own address. The instructions are fetched from the
memory by the CPU based on the value program counter.

Functions of memory management

 Keeping track of status of each memory location.
 Determining the allocation policy.
 Memory allocation technique.
 De-allocation technique.

4.1.1 Basic Hardware

Program must be
→ brought (from disk) into memory and
→ placed within a process for it to be run.
Main-memory and registers are only storage CPU can access directly.
Register access in one CPU clock.
Main-memory can take many cycles.
Cache sits between main-memory and CPU registers.
Protection of memory required to ensure correct operation.
A pair of base- and limit-registers define the logical (virtual) address space
(Fig. 3.9 & 3.1

III SEMESTER OPERATING SYSTEM (BCS303) 3

 RV Institute of Technology & Management®

Fig. 4.1 A base and a limit-register define a logical-address space

4.1.2 Address Binding

Programs are stored on the secondary storage disks as binary executable files. When the
programs are to be executed, they are brought in to the main memory and placed within a
process. The collection of processes on the disk waiting to enter the main memory forms the
input queue. One of the processes which are to be executed is fetched from the queue and placed
in the main memory. During the execution it fetches instruction and data from main memory.
After the

III SEMESTER OPERATING SYSTEM (BCS303) 4

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

Fig. 4.2 Hardware address protection with base and limit-registers

process terminates it returns back the memory space. During execution the process will
go through different steps and in each step the addresses represented in different ways. In source
program the address is symbolic. The compiler converts the symbolic address to re-locatable
address. The loader will convert this re-locatable address to absolute address (Fig. 3.11).

Binding of instructions and data can be done at any step along the way:
Compile time: -If we know whether the process resides in memory then absolute code
can be generated. If the static address changes, then it is necessary to re-compile the code from
the beginning.

Load time: -If the compiler doesn‘t know whether the process resides in memory then it
generates the re-locatable code. In this the binding is delayed until the load time.

Execution time: -If the process is moved during its execution from one memory segment
to another then the binding is delayed until run time. Special hardware is used for this. Most of
the general-purpose operating system uses this method.

4.1.3 Logical versus physical address

The address generated by the CPU is called logical address or virtual address. The
address seen by the memory unit i.e., the one loaded in to the memory register is called the
physical address. Compile time and load time address binding methods generate some logical
and physical address. The execution time addressing binding generate different logical and
physical address. Set of logical address space generated by the programs is the logical address
space.

III SEMESTER OPERATING SYSTEM (BCS303) 5

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

Fig. 4.3 Multistep processing of a user-program

The base register is also called re-location register. Value of the re-location register is
added to every address generated by the user process at the time it is sent to memory.

Fig. 4.4 Dynamic re-location using a re-location register

III SEMESTER OPERATING SYSTEM (BCS303) 6

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

The above Fig. 3.12 shows that dynamic re-location which implies mapping from virtual
addresses space to physical address space and is performed by the hardware at run time. Re-
location is performed by the hardware and is invisible to the user dynamic relocation makes it
possible to move a partially executed process from one area of memory to another without
affecting.

4.1.4 Dynamic Loading

For a process to be executed it should be loaded in to the physical memory. The size of
the process is limited to the size of the physical memory. Dynamic loading is used to obtain
better memory utilization. In dynamic loading the routine or procedure will not be loaded until it
is called. Whenever a routine is called, the calling routine first checks whether the called routine
is already loaded or not. If it is not loaded it cause the loader to load the desired program in to
thememory and updates the programs address table to indicate the change and control is passed
to newly called routine.

Advantage: Gives better memory utilization. Unused routine is never loaded. Do not need
special operating system support. This method is useful when large amount of codes are needed
to handle infrequently occurring cases.

4.1.5 Dynamic linking and Shared libraries

Some operating system supports only the static linking. In dynamic linking only, the
main program is loaded in to the memory. If the main program requests a procedure, the
procedure is loaded and the link is established at the time of references. This linking is postponed
until the execution time. With dynamic linking a ―stub‖ is used in the image of each library
referenced routine.

A ―stub‖ is a piece of code which is used to indicate how to locate the appropriate
memory resident library routine or how to load library if the routine is not already present.
When―stub‖ is executed, it checks whether the routine is present is memory or not. If not, it
loads the routine in to the memory. This feature can be used to update libraries i.e., library is
replaced by anew version and all the programs can make use of this library.

More than one version of the library can be loaded in memory at a time and each program
uses its version of the library. Only the programs that are compiled with the newversion are
affected by the changes incorporated in it. Other programs linked before new versionis installed
will continue using older libraries this type of system is called ―shared library‖.

4.2Swapping

III SEMESTER OPERATING SYSTEM (BCS303) 7

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

Swapping is a technique of temporarily removing inactive programs from the memory

of the system. A process can be swapped temporarily out of the memory to a backing store
and then brought back in to the memory for continuing the execution. This process is called
swapping.

Eg:- In a multi-programming environment with a round robin CPU scheduling whenever the time
quantum expires then the process that has just finished is swapped out and a new process swaps
in to the memory for execution.

A variation of swap is priority-based scheduling. When a low priority is executing and if

a high priority process arrives then a low priority will be swapped out and high priority is
allowed for execution. This process is also called as Roll out and Roll in.

Normally the process which is swapped out will be swapped back to the same memory
space that is occupied previously. This depends upon address binding.
If the binding is done at load time, then the process is moved to same memory location. If
the binding is done at run time, then the process is moved to different memory location. This is
because the physical address is computed during run time.

Fig. 4.5 Swapping of two processes using a disk as a backing-store

Swapping requires backing store and it should be large enough to accommodate the
copies of all memory images (Fig. 3.13). The system maintains a ready queue consisting of all
the processes whose memory images are on the backing store or in memory that are ready to run.
Swapping is constant by other factors: To swap a process, it should be completely idle. A
process may be waiting for an i/o operation. If the i/o is asynchronously accessing the user
memory for i/o buffers, then the process cannot be swapped.

4.2.1 Contiguous memory allocation

III SEMESTER OPERATING SYSTEM (BCS303) 8

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

One of the simplest methods for memory allocation is to divide memory in to several
fixed partition. Each partition contains exactly one process. The degree of multi-programming
depends on the number of partitions. In multiple partition method, when a partition is free,
process is selected from the input queue and is loaded in to free partition of memory. When
process terminates, the memory partition becomes available for another process. Batch OS uses
the fixed size partition scheme.

The OS keeps a table indicating which part of the memory is free and is occupied. When
the process enters the system, it will be loaded in to the input queue. The OS keeps track of the
memory requirement of each process and the amount of memory available and determines which
process to allocate the memory.

When a process requests, the OS searches for large hole for this process, hole is a large
block of free memory available. If the hole is too large it is split in to two. One part is allocated
to the requesting process and other is returned to the set of holes. The set of holes are searched to
determine which hole is best to allocate. There are three strategies to select a free hole:

Fig. 4.6 Hardware support for relocation and limit-registers

First bit:-Allocates first hole that is big enough. This algorithm scans memory from the
beginning and selects the first available block that is large enough to hold the process.
Best bit:-It chooses the hole i.e., closest in size to the request. It allocates the smallest
hole i.e., big enough to hold the process.
Worst fit:-It allocates the largest hole to the process request. It searches for the largest
hole in the entire list.

First fit and best fit are the most popular algorithms for dynamic memory allocation. First
fit is generally faster. Best fit searches for the entire list to find the smallest hole i.e., large
enough. Worst fit reduces the rate of production of smallest holes. All these algorithms
suffer

III SEMESTER OPERATING SYSTEM (BCS303) 9

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

from fragmentation.

4.2.2 Memory Protection

Memory protection means protecting the OS from user process and protecting
process from one another. Memory protection is provided by using a re-location register, with
a limit register. Re-location register contains the values of smallest physical address and limit
register contains range of logical addresses (Fig. 3.14).

(Re-location = 100040 and limit = 74600). The logical address must be less than the
limit register; the MMU maps the logical address dynamically by adding the value in re-
location register. When the CPU scheduler selects a process for execution, the dispatcher
loads the re-location and limit register with correct values as a part of context switch. Since
every address generated by the CPU is checked against these register we can protect the OS
and other users‘ programs and data from being modified.

4.2.3 Fragmentation

Memory fragmentation can be of two types: Internal Fragmentation External

Fragmentation Internal Fragmentation there is wasted space internal to a portion due to the
fact that block of data loaded is smaller than the partition. Eg: - If there is a block of 50kb and
if the process requests 40kb and if the block is allocated to the process then there will be 10kb
of memory left.

External Fragmentation exists when there is enough memory space exists to satisfy
the request, but it not contiguous i.e., storage is fragmented in to large number of small holes.

External Fragmentation may be either minor or a major problem.

One solution for over-coming external fragmentation is compaction. The goal is to

move all the free memory together to form a large block. Compaction is not possible always.
If the relocation is static and is done at load time then compaction is not possible. Compaction
is possible if the re-location is dynamic and done at execution time.

Another possible solution to the external fragmentation problem is to permit the

logical address space of a process to be non-contiguous, thus allowing the process to be
allocated physical memory whenever the latter is available.

4.3 Paging
Paging is a memory management scheme that permits the physical address space of a
process to be non-contiguous. Support for paging is handled by hardware. It is used to avoid
external fragmentation. Paging avoids the considerable problem of fitting the varying sized
memory chunks on to the backing store. When some code or date residing in main memory

III SEMESTER OPERATING SYSTEM (BCS303) 10

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

need to be swapped out, space must be found on backing store.

4.3.1 Basic Method

Physical memory is broken in to fixed sized blocks called frames (f). Logical
memory is broken in to blocks of same size called pages (p).

When a process is to be executed its pages are loaded in to available frames from
backing store. The blocking store is also divided in to fixed-sized blocks of same size as
memory frames. The following Fig. 3.16 shows paging hardware:

Fig. 4.7 Paging hardware

Logical address generated by the CPU is divided in to two parts: page number (p) and
page offset(d). The page number (p) is used as index to the page table. The page table contains
base address of each page in physical memory.

This base address is combined with the page offset to define the physical memory i.e.,
sent to the memory unit. The page size is defined by the hardware.

The size of a power of 2, varying between 512 bytes and 10Mb per page. If the size of
logical address space is 2^m address unit and page size is 2^n, then high order m-n designates the
page number and n low order bits represents page offset.

III SEMESTER OPERATING SYSTEM (BCS303) 11

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

Fig. 4.8 Paging model of logical and physical-memory

• The page-table contains the base-address of each page in physical-memory (Fig. 3.17):
• Address generated by CPU is divided into 2 parts:
1) Page-number(p) is used as an index to the page-table and
2) Offset(d) is combined with the base-address to define the physical-
address. This physical-address is sent to the memory-unit.

Fig. 4.9 Free frames (a) before allocation and (b) after allocation
Eg:- To show how to map logical memory in to physical memory (Fig. 3.18) consider a

III SEMESTER OPERATING SYSTEM (BCS303) 12

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

page size of 4 bytes and physical memory of 32 bytes (8 pages). Logical address 0 is page 0 and
offset 0. Page 0 is in frame 5. The logical address 0 maps to physical address 20. [(5*4) +
0].logical address 3 is page 0 and offset 3 maps to physical address 23 [(5*4) + 3]. Logical
address4 is page 1 and offset 0 and page 1 is mapped to frame 6. So logical address 4 maps to
physical address 24 [(6*4) + 0]. Logical address 13 is page 3 and offset 1 and page 3 is mapped
to frame
2. So logical address 13 maps to physical address 9 [(2*4) + 1].

4.3.2 Hardware Support for Paging

The hardware implementation of the page table can be done in several ways:

The simplest method is that the page table is implemented as a set of dedicated registers.
These registers must be built with very high-speed logic for making paging address translation.
Every accessed memory must go through paging map. The use of registers for page table is
satisfactory if the page table is small.

If the page table is large then the use of registers is not visible. So, the page table is kept
in the main memory and a page table base register [PTBR] points to the page table. Changing the
page table requires only one register which reduces the context switching type. The problem with
this approach is the time required to access memory location. To access a location [i] first we
have to index the page table using PTBR offset. It gives the frame number which is combined
with the page offset to produce the actual address. Thus, we need two memory accesses for a
byte.

The only solution is to use special, fast, lookup hardware cache called translation look
aside buffer [TLB] or associative register. LB is built with associative register with high speed
memory. Each register contains two paths a key and a value.

Fig. 4.10 Paging hardware with TLB

When an associative register is presented with an item, it is compared with all the key

III SEMESTER OPERATING SYSTEM (BCS303) 13

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

values, if found the corresponding value field is return and searching is fast. TLB is used with
the page table as follows: TLB contains only few page table entries. When a logical address is
generated by the CPU, its page number along with the frame number is added to TLB.

If the page number is found its frame memory is used to access the actual memory. If
the page number is not in the TLB (TLB miss) the memory reference to the page table is made.
When the frame number is obtained use can use it to access the memory. If the TLB is full of
entries the OS must select anyone for replacement.

Each time a new page table is selected the TLB must be flushed [erased] to ensure that
next executing process do not use wrong information. The percentage of time that a page
number is found in the TLB is called HIT ratio.

4.3.3 Protection

Memory protection in paged environment is done by protection bits that are associated
with eachframe these bits are kept in page table. x One bit can define a page to be read-write or
read-only. To find the correct frame number every reference to the memory should go through
page table. At the same timephysical address is computed. The protection bits can be checked to
verify that no writers are made to read-only page. Any attempt to write in to read-only page
causes a hardware trap to the OS. This approach can be used to provide protection to read-only,
read- write or execute-only pages. One more bit is generally added to each entry in the page
table: a valid-invalid bit (Fig. 3.20).

Fig. 4.11 Valid (v) or invalid (i) bit in a page-table

III SEMESTER OPERATING SYSTEM (BCS303) 14

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

A valid bit indicates that associated page is in the processes logical address space and thus it is a
legal or valid page. If the bit is invalid, it indicates the page is not in the processes logical
addressed space and illegal. Illegal addresses are trapped by using the valid-invalid bit. The OS
sets this bit for each page to allow or disallow accesses to that page.

4.3.4 Shared Pages

Advantage of

paging:

Possible to share common code.

Re-entrant code (Fig. 3.21) is non-self-modifying code, it never changes during
execution.
Two or more processes can execute the same code at the same time.
Each process has its own copy of registers and data-storage to hold the data for the
process's execution.
The data for 2 different processes will be different.
Only one copy of the editor need be kept in physical-memory (Fig. 3.21).
Each user's page-table maps onto the same physical copy of the editor, but data pages are
mapped onto different frames.

Disadvantage:
Systems that use inverted page-tables have difficulty implementing shared-memory.

Fig. 4.12 Sharing of code in a paging environment

III SEMESTER OPERATING SYSTEM (BCS303) 15

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

4.4 Structure of Page Table

a. Hierarchical paging:

Recent computer system supports a large logical address apace from 2^32 to 2^64. In
thissystem the page table becomes large.

So, it is very difficult to allocate contiguous main memory for page table. One
simplesolution to this problem is to divide page table in to smaller pieces.

There are several ways to accomplish this division.

One way is to use two-level paging algorithm in which the page table itself is also paged.
Eg:-In a 32 bit machine with page size of 4kb.

A logical address is divided in to a page number consisting of 20 bits anda page offset
of 12 bit.

The page table is further divided since the page table is paged, the page number
isfurther divided in to 10-bit page number and a 10-bit offset.

The page-table itself is also paged (Fig. 3.22).

This is also known as a forward-mapped page-table because address translation works

from the outer page-table inwards.

For example (Fig. 3.23):

Consider the system with a 32-bit logical-address space and a page-size of 4 KB.
A logical-address is divided into

→ 20-bit page-number and

→ 12-bit page-offset.

Since the page-table is paged, the page-number is further divided into

→ 10-bit page-number and

→ 10-bit page-offset.

Thus, a logical-address is as follows:

III SEMESTER OPERATING SYSTEM (BCS303) 16

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

Fig. 4.13 A two-level page-table scheme

Fig. 4.14 Address translation for a two-level 32-bit paging architecture

b. Hashed page table:

Hashed page table handles the address space larger than 32 bit. The virtual page number
is used as hashed value. Linked list is used in the hash table which contains a list of elements
that hash to the same location.

Each element in the hash table contains the following three fields: Virtual page number x
Mapped page frame value x Pointer to the next element in the linked list.

III SEMESTER OPERATING SYSTEM (BCS303) 17

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

Fig. 4.15 Hashed page-table

Working:

Virtual page number is taken from virtual address. Virtual page number is hashed in to
hash table (Fig. 3.24).

Virtual page number is compared with the first element of linked list. Both the values are
matched, that value is (page frame) used for calculating the physical address. If not match then
entire linked list is searched for matching virtual page number. Clustered pages are similar to
hash table but one difference is that each entity in the hash table refer to several pages.

c. Inverted Page Tables:

Since the address spaces have grown to 64 bits, the traditional page tables become a
problem. Even with two level page tables. The table can be too large to handle. An inverted page
table has only entry for each page in memory. Each entry consisted of virtual address of the page
stored in that read-only location with information about the process that owns that page.

Each virtual address in the Inverted page table consists of triple <process-id , page number
, offset >. The inverted page table entry is a pair <process-id , page number>. When a memory
reference is made, the part of virtual address i.e., <process-id , page number> is presented in to
memory sub-system.

The inverted page table is searched for a match. If a match is found at entry I then the
physical address <i, offset> is generated. If no match is found then an illegal address access has
been attempted. This scheme is as shown in Fig. 3.25.

III SEMESTER OPERATING SYSTEM (BCS303) 18

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

Fig. 4.16 Inverted page-table

4.5 Segmentation

4.5.1 Basic Method

[Link] This is a memory-management scheme that supports user-view
of memory (Fig. 3.26).
[Link] A logical-address space is a collection of segments.
[Link] Each segment has a name and a length.
[Link] The addresses specify both
→ segment-name and
→ offset within the segment.

Fig. 4.16 Programmer‘s view of a program

III SEMESTER OPERATING SYSTEM (BCS303) 19
 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

[Link] Normally, the user-program is compiled, and the compiler automatically constructs segments
[Link] reflecting the input program. For ex:

→ The code → Global variables

→ The heap, from which memory is allocated → The stacks used by each thread
→ The standard C library

Hardware Support
Segment-table maps 2-dimensional user-defined addresses into one-dimensional physical-addresses.
In the segment-table, each entry has following 2 fields:

Segment-base contains starting physical-address where the segment resides in

memory. Segment-limit specifies the length of the segment (Fig. 3.27).

A logical-address consists of 2 parts:

Segment-number(s) is used as an index to the segment-table.

Offset(d) must be between 0 and the segment-limit.
If offset is not between 0 & segment-limit, then we trap to the OS (logical-addressing attempt
beyond end of segment).
If offset is legal, then it is added to the segment-base to produce the physical-memory address.

Fig. 4.17 Segmentation hardware

Consider we have five segments numbered from 0 through 4. The segments are stored in physical
memory as shown in Fig.. The segment table has a separate entry for each segment, giving start address

III SEMESTER OPERATING SYSTEM (BCS303) 20

 RV Institute of Technology and Management

in physical memory (or base) and the length of that segment (or limit). For example, segment 2 is
400 bytes long and begins at location 4300. Thus, a reference to byte 53 of segment 2 is mapped
onto location 4300 + 53 = 4353.

Fig. 4.18 Example of segmentation.

IV SEMESTER OPERATING SYSTEM (18CS43) 1

 RV Institute of Technology & Management®

Virtual-Memory Management

4.9 Background

Virtual memory is a technique that allows the execution of processes that are not completely in
memory. One major advantage of this scheme is that programs can be larger than physical
memory.

 In practice, most real processes do not need all their pages, or at least not all at once, for
several reasons:
1. Error handling code is not needed unless that specific error occurs, some of
which are quite rare.
2. Certain features of certain programs are rarely used.
 The ability to load only the portions of processes that are actually needed has several
benefits:
o Programs could be written for a much larger address space (virtual memory space
) than physically exists on the computer.
o Because each process is only using a fraction of their total address space, there is
more memory left for other programs, improving CPU utilization and system
throughput.
o Less I/O is needed for swapping processes in and out of RAM, speeding things
up.
The Fig. 4.21 below shows the general layout of virtual memory, which can be much larger
than physical memory

Fig. 4.21 Diagram showing virtual memory that is larger than physical
memory.

 The Fig. below shows virtual address space, which is the programmer‘s logical view
of process memory storage. The actual physical layout is controlled by the process's

IV SEMESTER OPERATING SYSTEM (18CS43) 2

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

page table.
 Note that the address space shown in Fig. 4.2 is sparse - A great hole inthe middle
of the address space is never used, unless the stack and/or the heap grow to fill the
hole.

Fig. 4.22 Virtual address space.

 Virtual memory also allows the sharing of files and memory by multiple processes,
with several benefits:
 System libraries can be shared by mapping them into the virtual address space of
more than one process.
 Processes can also share virtual memory by mapping the same block of memory to
more than one process as shown in Fig. 4.3.
 Process pages can be shared during a fork( ) system call, eliminating the need to copy
all of the pages of the original ( parent ) process.

Fig. 4.23 Shared library using virtual memory

4.2 Demand
Paging
The basic idea behind demand paging is that when a process is swapped in, its pages

are not swapped in all at once. Rather they are swapped in only when the process needs
IV SEMESTER OPERATING SYSTEM (18CS43) 2
 RV Institute of Technology & Management®

them. ( on demand. ) This is termed as lazy swapper, although a pager is a more

accurate

IV SEMESTER OPERATING SYSTEM (18CS43) 2

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

term as shown in Fig. 4.4.

Fig. 4.24 Transfer of a paged memory to contiguous disk space.

 The basic idea behind demand paging is that when a process is swapped in, the
pager only loads into memory those pages that is needed presently.
 Pages that are not loaded into memory are marked as invalid in the page table,using
the invalid bit. Pages loaded in memory are marked as valid.
 If the process only ever accesses pages that are loaded in memory ( memory resident
pages ), then the process runs exactly as if all the pages were loaded in to memory as
shown in Fig. 4.5.

Fig. 4.25 Page table when some pages are not in main memory.
 On the other hand, if a page is needed that was not originally loaded up, then a
page fault trap is generated, which must be handled in a series of steps:
1. The memory address requested is first checked, to make sure it was a
valid memory request.
2. If the reference is to an invalid page, the process is terminated. Otherwise,
if the page is not present in memory, it must be paged in.
3. A free frame is located, possibly from a free-frame list.

IV SEMESTER OPERATING SYSTEM (18CS43) 3

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

4. A disk operation is scheduled to bring in the necessary page from disk.

5. After the page is loaded to memory, the process's page table is updated
with the new frame number, and the invalid bit is changed to indicate that
this is now a valid page reference as shown in Fig. 4.6.
6. The instruction that caused the page fault must now be restarted from
the beginning.

Fig. 4.26 Steps in handling a page fault.

 In an extreme case, the program starts execution with zero pages in memory. Here
NO pages are swapped in for a process until they are requested by page faults. This
is known as pure demand paging.
 The hardware necessary to support demand paging is the same as for paging and
swapping: A page table and secondary memory.

4.2.1 Performance of Demand Paging

 There is some slowdown and performance hit whenever a page fault occurs (as the
required page is not available in memory) and the system has to go get it from
memory.
 There are many steps that occur when servicing a page fault and some of the steps are
optional or variable. But just for the sake of discussion, suppose that a normal memory
access requires 200 nanoseconds, and that servicing a page fault takes 8 milliseconds.
(8,000,000 nanoseconds, or 40,000 times a normal memory access. ) With a page fault
rate of p, (on a scale from 0 to 1), the effective access time is now:
Effective access time = p * time taken to access memory in page fault+ (1-p)* time taken to
access memory
= p * 8000000 + ( 1 - p ) * ( 200 )
= 200 + 7,999,800 * p

IV SEMESTER OPERATING SYSTEM (18CS43) 4

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

Even if only one access in 1000 causes a page fault, the effective access time drops from 200
nanoseconds to 8.2 microseconds, a slowdown of a factor of 40 times. In order to keep the
slowdown less than 10%, the page fault rate must be less than 0.0000025, or one in 399,990
accesses.

4.3 Copy-on-Write
The idea behind a copy-on-write is that the pages of a parent process is shared by the child
process, until one or the other of the processes changes the page. Only when a process
changes any page content, that page is copied for the child as shown in Fig. 4.7 and 4.8.

Only pages that can be modified need to be labeled as copy-on-write. Code segments can
simply be shared.

Some systems provide an alternative to the fork() system call called a virtual memory fork,
vfork( ). In this case the parent is suspended, and the child uses the parent's memory pages.
This is very fast for process creation, but requires that the child not modifying the address
space of parent.

Fig. 4.27 Before process 1 modifies page C. Fig. 4.28 After process 1 modifies page C.

4.4 Page Replacement

In order to make the most use of virtual memory, we load several processes into
memory at the same time. Since we only load the pages that are actually needed by each
process at any given time, there are frames to load many more processes in memory.
If some process suddenly decides to use more pages and there aren't anyfree
framesavailable. Then there are several possible solutions to consider:
1. Adjust the memory used by I/O buffering, etc., to free up some frames for
user processes.
2. Put the process requesting more pages into a wait queue until some free
frames become available.
3. Swap some process out of memory completely, freeing up its page frames.
4. Find some page in memory that isn't being used right now, and swap that
page only out to disk, freeing up a frame that can be allocated to the process

IV SEMESTER OPERATING SYSTEM (18CS43) 5

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

requesting it. This is known as page replacement, and is the most common
solution as shown in Fig. 4.9. There are many different algorithms for page
replacement.

Fig. 4.29 Need for page replacement.

The previously discussed page-fault processing assumed that there would be free frames
available on the free-frame list. Now the page-fault handling must be modified to free up a
frame if necessary, as follows:

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

2. Find a free frame:
a. If there is a free frame, use it.
b. If there is no free frame, use a page-replacement algorithm to select
an existing frame to be replaced, known as the victim frame.
c. Write the victim frame to disk. Change all related page tables to
indicate that this page is no longer in memory.
3. Read in the desired page and store it in the frame. Change the entries in
page table.
4. Restart the process that was waiting for this page.

Note that step 2c adds an extra disk write to the page-fault handling, thus doubling the time
required to process a page fault. This can be reduced by assigning a modify bit, or dirty bit to
each page in memory, indicating whether or not it has been changed since it was last loaded in
from disk. If the page is not modified the bit is not set.

If the dirty bit has not been set, then the page is unchanged, and does not need to be written out
to disk. Many page replacement strategies specifically look for pages that do not have their
dirty bit set.

IV SEMESTER OPERATING SYSTEM (18CS43) 6

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

Fig. 4.30 Page replacement.

There are two major requirements to implement a successful demand paging system.

A frame-allocation algorithm and a page-replacement algorithm. The former centers

around how many frames are allocated to each process, and the latter deals with how to
select a page for replacement when there are no free frames available.

The overall goal in selecting and tuning these algorithms is to generate the
fewest number of overall page faults. Because disk access is so slow relative to memory
access, even slight improvements to these algorithms can yield large improvements in
overall system performance.
Algorithms are evaluated using a given string of page accesses known as a
reference string.

Fig. 4.31 Graph of page faults versus number of frames.

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. Obviously, as the
number of frames available increases, the number of page faults decreases as shown in Fig.
4.11.

IV SEMESTER OPERATING SYSTEM (18CS43) 7

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

Few Page Replacement algorithms –

a) FIFO Page Replacement

 A simple and obvious page replacement strategy is FIFO, i.e. first-in-first-out.

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

 Or a FIFO queue can be created to hold all pages in memory. As new pages are
brought in, they are added to the tail of a queue, and the page at the head of the
queue is the next victim as shown in Fig. 4.12.
 In the following example, a reference string is given and there are 3 free frames.
There are 20-page requests, which results in 15-page faults.

Fig. 4.32 FIFO page-replacement algorithm.

 Although FIFO is simple and easy to understand, it is not always optimal, or

even efficient.
 Belady's anomaly tells that for some page-replacement algorithms, the page-
fault rate may increase as the number of allocated frames increases as shown
in Fig. 4.13.

Fig. 4.33 Page-fault curve for FIFO replacement on a reference string.

b) Optimal Page Replacement

 The discovery of Belady's anomaly lead to the search for an optimal page-
replacement algorithm, which is simply that which yields the lowest of all
possible page-faults, and which does not suffer from Belady's anomaly.
 Such an algorithm does exist, and is called OPT or MIN. This algorithm is
"Replace the page that will not be used for the longest time in the future."

IV SEMESTER OPERATING SYSTEM (18CS43) 8

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

 The same reference string used for the FIFO example is used in the example
below, here the minimum number of possible page faults is 9 as shown in Fig.
4.14.
 Unfortunately OPT cannot be implemented in practice, because it requires the
knowledge of future string, but it makes a nice benchmark for the comparison
and evaluation of real proposed new algorithms.

Fig. 4.34 Optimal page-replacement algorithm.

c) LRU Page Replacement

 The LRU (Least Recently Used) algorithm, predicts that the page that has not
been used in the longest time is the one that will not be used again in the near
future.
 Some view LRU as analogous to OPT, but here we look backwards in
time instead of forwards.
 Fig. 4.15 illustrates LRU for our sample string, yielding 12 page faults, ( as
compared to 15 for FIFO and 9 for OPT. )

Fig. 4.35 LRU page-replacement algorithm

LRU is considered a good replacement policy, and is often used. There are two
simple approaches commonly used to implement this:
1. Counters. With each page-table entry a time-of-use field is associated. Whenever a
reference to a page is made, the contents of the clock register are copied to the time-of-
use field in the page-table entry for that page. In this way, we always have the "time" of
the last reference to each page. This scheme requires a search of the page table to find
the LRU page and a write to memory for each memory access.

IV SEMESTER OPERATING SYSTEM (18CS43) 9

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

2. Stack. Another approach is to use a stack, and whenever a page is accessed, pull
that page from the middle of the stack and place it on the top. The LRU page will
always be at the bottom of the stack as shown in Fig. 4.16. Because this requires
removing objects from the middle of the stack, a doubly linked list is the
recommended data structure.
Neither LRU or OPT exhibit Belady's anomaly. Both belong to a class of page-
replacement algorithms called stack algorithms, which can never exhibit Belady's
anomaly.

Fig. 4.36 Use of a stack to record the most recent page references.

d) LRU-Approximation Page Replacement

Many systems offer some degree of hardware support, enough to approximate LRU.
In particular, many systems provide a reference bit for every entry in a page table,
which is set anytime that page is accessed. Initially all bits are set to zero, and they
can also all be cleared at any time. One bit distinguishes pages that have been
accessed since the last clear from those that have not been accessed.

d.1 Additional-Reference-Bits Algorithm

 An 8-bit byte (reference bit) is stored for each page in a table in memory.
 At regular intervals (say, every 100 milliseconds), a timer interrupt transfers control to
the operating system. The operating system shifts the reference bit for each page into the
high-order bit of its 8-bit byte, shifting the other bits right by 1 bit and discarding the
low- order bit.
 These 8-bit shift registers contain the history of page use for the last eight time periods.
 If the shift register contains 00000000, then the page has not been used for eight
time periods.
 A page with a history registers value of 11000100 has been used more recently than
one with a value of 01110111.

d.2 Second-Chance Algorithm

 The second chance algorithm is a FIFO replacement algorithm, except the reference
bit is used to give pages a second chance at staying in the page table.
 When a page must be replaced, the page table is scanned in a FIFO (circular
queue) manner.

 If a page is found with its reference bit as ‗0‘, then that page is selected as
thenext victim.
 If the reference bit value is ‗1‘, then the page is given a second chance and its reference

IV SEMESTER OPERATING SYSTEM (18CS43) 10

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

bit value is cleared (assigned as ‗0‘) as shown in Fig. 4.17.

Fig. 4.37 Second-chance (clock) page-replacement algorithm.

 Thus, a page that is given a second chance will not be replaced until all other pages
have been replaced (or given second chances). In addition, if a page is used often, then
it sets its reference bit again.
 This algorithm is also known as the clock algorithm. One way to implement the second-

chance algorithm is as a circular queue. A pointer indicates which page is to be replaced next.
When a frame is needed, the pointer advances until it finds a page with a 0-reference bit. As it
advances, it clears the reference bits. Once a victim page is found, the page is replaced, and the
new page is inserted in the circular queue in that position.

d.3 Enhanced Second-Chance Algorithm

 The enhanced second chance algorithm looks at the reference bit and the modify
bit (dirty bit) as an ordered page, and classifies pages into one of four classes:
1. (0, 0) - Neither recently used nor modified.
2. (0, 1) - Not recently used, but modified.
3. (1, 0) - Recently used, but clean.
4. (1, 1) - Recently used and modified.

 This algorithm searches the page table in a circular fashion, looking for the first page it
can find in the lowest numbered category. i.e. it first makes a pass looking for a (0, 0),
and then if it can't find one, it makes another pass looking for a ( 0, 1 ), etc.
 The main difference between this algorithm and the previous one is the preference for
replacing clean pages if possible.
e) Counting-Based Page Replacement
 There are several algorithms based on counting the number of references that have
been made to a given page, such as:
o Least Frequently Used, LFU: Replace the page with the lowest reference count.
A problem can occur if a page is used frequently initially and then not used any

IV SEMESTER OPERATING SYSTEM (18CS43) 11

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

more, as the reference count remains high. A solution to this problem is to right-
shift the counters periodically, yielding a time-decaying average reference count.
o Most Frequently Used, MFU: Replace the page with the highest reference
count. The logic behind this idea is that pages that have already been referenced
a lot have been in the system a long time, and we are probably done with them,
whereas pages referenced only a few times have only recently been loaded, and
we still need them.

f) Page-Buffering Algorithms
 Maintain a certain minimum number of free frames at all times. When a page-
fault occurs, go ahead and allocate one of the free frames from the free list first,
so that the requesting process is in memory as early as possible, and then select a
victim page to write to disk and free up a frame.
 Keep a list of modified pages, and when the I/O system is idle, these pages are
written to disk, and then clear the modify bits, thereby increasing the chance of
finding a "clean" page for the next potential victim and page replacement can be
done much faster.

4.5 Allocation of Frames

 The absolute minimum number of frames that a process must be allocated is

dependent on system architecture.
 The maximum number is defined by the amount of available physical memory.

4.5.1 Allocation Algorithms

After loading of OS, there are two ways in which the allocation of frames can be done to
the processes.
 Equal Allocation - If there are m frames available and n processes to share
them,each process gets m / n frames, and the leftovers are kept in a free-frame buffer
pool.
 Proportional Allocation - Allocate the frames proportionally depending on the
sizeof the process. If the size of process i is Si, and S is the sum of size of all
processes in the system, then the allocation for process Pi is ai = m * Si / S. where m is
the free frames available in the system.
Consider a system with a 1KB frame size. If a small student process of 10 KB and an
interactive database of 127 KB are the only two processes running in a system with 62 free
frames.

With proportional allocation, we would split 62 frames between two processes,

as follows-
m=62, S = (10+127)=137
Allocation for process 1 = 62 X 10/137 ~ 4
Allocation for process 2 = 62 X 127/137 ~57

Thus allocates 4 frames and 57 frames to student process and database respectively.

 Variations on proportional allocation could consider priority of processrather

IV SEMESTER OPERATING SYSTEM (18CS43) 12

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

than just their size.

4.5.2 Global versus Local Allocation

 Page replacement can occur both at local or global level.
 With local replacement, the number of pages allocated to a process is fixed, and
page replacement occurs only amongst the pages allocated to this process.
 With global replacement, any page may be a potential victim, whether it
currently belongs to the process seeking a free frame or not.
 Local page replacement allows processes to better control their own page fault rates,
and leads to more consistent performance of a given process over different system load
levels.
 Global page replacement is overall more efficient, and is the more commonly
used approach.

4.5.3 Non-Uniform Memory Access (New)

 Usually the time required to access all memory in a system is equivalent.

 This may not be the case in multiple-processor systems, especially where each
CPUis physically located on a separate circuit board which also holds some portion
of the overall system memory.
 In such systems, CPUs can access memory that is physically located on the
sameboard much faster than the memory on the other boards.
 The basic solution is akin to processor affinity - At the same time that we try to
schedule processes on the same CPU to minimize cache misses, we also try to allocate
memory for those processes on the same boards, to minimize access times.

4.6 Thrashing

Thrashing is the state of a process where there is high paging activity. A process that is
spending more time paging than executing is said to be thrashing.

4.6.1 Cause of Thrashing

When memory is filled up and processes starts spending lots of time waiting for their pages to
page in, then CPU utilization decreases (Processes are not executed as they are waiting for
some pages), causing the scheduler to add in even more processes and increase the degree of
multiprogramming even more. Thrashing has occurred, and system throughput plunges. No
work is getting done, because the processes are spending all their time paging.

In the graph given below, CPU utilization is plotted against the degree of multiprogramming.
As the degree of multiprogramming increases, CPU utilization also increases, although more
slowly, until a maximum is reached.

If the degree of multiprogramming is increased even further, thrashing sets in, and CPU
utilization drops sharply as shown in Fig. 4.18. At this point, to increase CPU utilization and
stop thrashing, we must decrease the degree of multiprogramming.

IV SEMESTER OPERATING SYSTEM (18CS43) 13

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

Fig. 4.38 Thrashing.

Local page replacement policies can prevent thrashing process from taking pages away from
other processes, but it still tends to clog up the I/O queue.

The locality model states that, as a process executes, it moves from locality to locality. A locality is a
set of pages that are actively used together (Fig. 4.19). A program is generally composed of several
different localities, which may overlap. For example, when a function is called, it defines a new
locality.
In this locality, memory references are made to the instructions of the function call, its local variables,
and a subset of the global variables. When we exit the function, the process leaves this locality, since
the local variables and instructions of the function are no longer in active use.

Fig. 4.39 Locality in a memory-reference pattern.

IV SEMESTER OPERATING SYSTEM (18CS43) 14

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

4.6.2 Working-Set Model

Fig. 4.40 Working-set model.

The working set model is based on the concept of locality, and defines a working set window,
of length delta. Whatever pages are included in the most recent delta page references are said
to be in the processes working set window, and comprise its current working set, as illustrated
in Fig. 4.20:

The selection of delta is critical to the success of the working set model - If it is too small then
it does not encompass all of the pages of the current locality, and if it is too large, then it
encompasses pages that are no longer being frequently accessed.
The total demand of frames, D, is the sum of the sizes of the working sets for all processes
(D=WSSi). If D exceeds the total number of available frames, then at least one process is
thrashing, because there are not enough frames available to satisfy its minimum working set. If
D is significantly less than the currently available frames, then additional processes can be
launched.
The hard part of the working-set model is keeping track of what pages are in the current
working set, since every reference adds one to the set and removes one older page.

4.6.3 Page-Fault Frequency

When page- fault rate is too high, the process needs more frames and when it is too low, the
process may have too many frames.
The upper and lower bounds can be established on the page-fault rate. If the actual page- fault
rate exceeds the upper limit, allocate the process another frame or s spend the process. If the
page-fault rate falls below the lower limit, remove a frame from t e process. Thus, we
directly measure and control the page-fault rate to prevent [Link]

Fig. 4.41 Page-fault frequency.

IV SEMESTER OPERATING SYSTEM (18CS43) 15

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

4.7 File System

The file system consists of two distinct parts: a collection of files, each storing related data, and a
directory structure, which organizes and provides information about all the files in the system.

4.7.1 File Concept

A file is a collection of related information that is recorded on secondary storage. A file is
a sequence of bits, bytes, lines, or records, the meaning of which is defined by the file's creator
and user.
a) File Attributes
A file is named, for the convenience of its human users, and is referred to by its name. A file's
attributes vary from one operating system to another. The attributes of a file are p-
o Name - The symbolic file name is the only information kept in human readable form.
Some special significance is given to names, and particularly extensions (.exe, .txt, etc.).
o Identifier – It is a unique number, that identifies the file within the file system.
o Type – Type of the file like text, executable, another binary, etc.
o Location -. location of the file on that device.
o Size - The current size of the file (in bytes, words, or blocks)
o Protection - Access-control information (reading, writing, executing).
o Time, date, and user identification –These data can be useful for protection,
security, and usage monitoring.

b) File Operations
The operating system provides system calls to create, write, read, reposition, delete,
and truncate files.
o Creating a file - Two steps are necessary to create a file
 Find space in the file system for the file.
 Make an entry for the new file in the directory.
o Writing a file - To write a file, the system call consists of both the name of the file
and the information to be written to the file. Given the name of the file, the
system searches the directory to find the file's location. The system must
keep a write pointer to the location in the file where the next write is to
take place. The write pointer must be updated whenever a write occurs.
o Reading a file - To read from a file, the system call that specifies the name of the
file and where the next block of the file should be put. The directory is
searched for the file, and the system needs to keep a read pointer to the
location in the file where the next read is to take place. Once the read has
taken place, the read pointer is updated.
o Repositioning within a file - The directory is searched for the file, and the file
pointer is repositioned to a given value. This file operation is also known
as a file seek.
o Deleting a file – To delete a file, search the directory for the file. Release all file
space, so that it can be reused by other files, and erase the directory entry.

 Truncating a file - The user may want to erase the contents of a file but keep its attributes.
Rather than forcing the user to delete the file and then recreate it, this function allows
all attributes to remain unchanged –except for file length. The file size is reset to zero.

IV SEMESTER OPERATING SYSTEM (18CS43) 16

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

 Information about currently open files is stored in an open file table. It contains
information‘s like:
o File pointer - records the current position in the file, for the next read or write
access.
o File-open count - How many times has the current file been opened by different
processes, at the same time and not yet closed? When this counter reaches zero
the file can be removed from the table.
o Disk location of the file – The information needed to locate the file on disk is
kept in memory so that the system does not have to read it from disk for each
operation.
o Access rights – The file access permissions are stored on the per-process table so
that the operating system can allow or deny subsequent I/O requests.
 Some systems provide support for file locking.
o A shared lock is for reading only.
o An exclusive lock is for writing as well as reading.
o An advisory lock, it is up to the software developers to ensure that locks are acquired
or released.
o A mandatory lock, prevents any other process from accessing the locked file. (A
truly locked door.)

Fig. 4.42 Common file types.

4.7.2 File Types

 File name consists of two parts: name and extension

 The user and the operating system can identify the type of a file using the name.
 Most operating systems allow users to specify a file name as a sequence of
characters followed by a period and terminated by an extension. Example:
[Link], threads‘ etc. as shown in Fig. 4.22.
 The system uses the extension to indicate the type of the file and the type of
operations that can be done on that file.

IV SEMESTER OPERATING SYSTEM (18CS43) 17

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

 For instance, only a file with a ―. corn", ".exe", or ".bat‖, can be executed.

c) File Structure
 The study of different ways of storing files in secondary memory such that they can be
easily accessed.
 File types can be used to indicate the internal structure of the file. Certain files must be in
a particular structure that is understood by the operating system.
 For example, the operating system requires that an executable file have a specific
structure so that it can determine where in memory to load the file and the location of the
first instruction.
 UNIX treats all files as sequences of bytes, with no further consideration of the internal
structure.
 Macintosh files have two forks - a resource fork, and a data fork. The resource fork
contains information relating to the UI, such as icons and button images. The data fork
contains the traditional file contents-program code or data.

d) Internal File Structure

 Disk systems typically have a well-defined block size determined by the size of
a sector. A group of sectors form a group
 All disk I/0 is performed in units of one block, and all blocks are the same size.
 Logical records may even vary in length. Padding a number of logical records
into physical blocks is a common solution to this problem.
 The packing can be done either by the user's application program or by the
operating system. In either case, the file may be considered a sequence of
blocks.
 All the basic I/O functions operate in terms of blocks.
 Disk space is always allocated in terms of blocks. Some portion of last
block (while storing a file) is always wasted. This is called internal
fragmentation.

4.8 Access Methods

The file information is accessed and read into computer memory. The information in the file
can be accessed in several ways.

a) Sequential Access
 Here information in the file is processed in order, one record after the other.
 This mode of access is a common method; for example, editors and compilers
usually access files in this fashion.
 A sequential access file emulates magnetic tape operation, and generally supports a
few operations:
o read next - read a record and advance the file pointer to the next position.
o write next - write a record to the end of file and advance the file pointer to
the next position as shown in Fig. 4.23.
o skip n records - May or may not be supported. ‗n‘ may be limited to
positive numbers, or may be limited to +/- 1.

IV SEMESTER OPERATING SYSTEM (18CS43) 18

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

Fig. 4.43 Sequential-access file.

b) Direct Access
A file is made up of fixed-length logical records that allow programs to read and write
records randomly. The records can be rapidly accessed in any order.

Direct access is of great use for immediate access to large amount of information.
Eg: Database file. When a query occurs, the query is computed and only the selected rows are
access directly to provide the desired information.
Operations supported include:
 read n - read record number n. (position the cursor to n and then read the record)
 write n - write record number n. (position the cursor to n and then write the record)
 jump to record n – move to nth record (n- could be 0 or the end of file)
 If the record length is L, there is a request for record ‗N‘. Then the direct access
to the starting byte of record ‗N‘ is at L*(N-1)

Eg: if 3rd record is required and length of each record(L) is 50, then the starting
position of 3rd record is L*(N-1)
Address = 50*(3-1) = 100.

c) Other Access Methods (Indexed method)

 These methods generally involve the construction of an index for the file called index file.
 The index file is like an index page of a book, which contains key and address. To find a
record in the file, we first search the index and then use the pointer to access the record
directly and find the desired record.
 An indexed access scheme can be easily built on top of a direct access system.
 For very large files, the index file itself is very large. The solution to this is to create an
index for index file. i.e. multi-level indexing as shown in Fig.
4.24.

Fig. 4.44 Example of index and relative files.

IV SEMESTER OPERATING SYSTEM (18CS43) 19

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

4.9 Directory Structure

Directory is a structure which contains filenames and information about the files like
location, size, type etc. The files are put in different directories. Partitioning is useful for limiting
the sizes of individual file systems, putting multiple file-system types on the same device, or
leaving part of the device available for other uses.
Partitions are also known as slices or minidisks as shown in Fig. 4.24. A file system can
be created on each of these parts of the disk. Any entity containing a file system is generally
known as a volume.

Fig. 4.45 A typical file-system organization.

4.9.1 Directory Overview

The directory can be viewed as a symbol table that translates file names into their directory
entries.
Directory operations to be supported include:
o Search for a file - search a directory structure to find the entry for
a particular file.
o Create a file – create new files and add to the directory
o Delete a file - When a file is no longer needed, erase it from the directory
o List a directory - list the files in a directory and the contents of
the directory entry.
o Rename a file – Change the name of the file. Renaming a file may
also allow its position within the directory structure to be changed.
o Traverse the file system - Access every directory and every file within
a directory structure.

4.9.2 Directory Structures

a) Single-Level Directory
 It is the simplest directory structure.
 All files are contained in the same directory, which is easy to support and understand.

The limitations of this structure are that -

 All files are in the same directory must have unique names.
 Even a single user on a single-level directory may find it difficult to remember the
names of all the files as the number of files increases as shown in Fig. 4.26.

IV SEMESTER OPERATING SYSTEM (18CS43) 20

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

Fig. 4.46 Single-level directory

b) Two-Level Directory
 Each user gets their own directory space - user file directory (UFD)
 File names only need to be unique within a given user's directory.
 A master file directory (MFD) is used to keep track of each user‘s directory,
and must be maintained when users are added to or removed from the system.
 When a user refers to a particular file, only his own UFD is searched.
 All the files within each UFD are unique.
 To create a file for a user, the operating system searches only that user's UFD to
ascertain whether another file of that name exists.
 To delete a file, the operating system confines its search to the local UFD; thus, it
cannot accidentally delete another user's file that has the same name. The user
directories themselves must be created and deleted as necessary.
 This structure isolates one user from another. Isolation is an advantage when the
users are completely independent but is a disadvantage when the users want to
cooperate on some task and to access one another's files as shown in Fig. 4.27.

Fig. 4.47 Two-level directory structure

c) Tree-Structured Directories
 A tree structure is the most common directory structure.
 The tree has a root directory, and every file in the system has a unique path name.
 A directory (or subdirectory) contains a set of files or subdirectories.
 One bit in each directory entry defines the entry as a file (0) or as a subdirectory (1).
Special system calls are used to create and delete directories.
 Path names can be of two types: absolute and relative. An absolute path begins at the
root and follows a down to the specified file, giving the directory names on the path.
A relative path defines a path from the current directory (Fig. 4.28).
 For example, in the tree-structured file system of Fig. below if the current directory is
root/spell/mail, then the relative path name is prt/first and the files absolute path name
root/spell/mail/prt/jirst.

IV SEMESTER OPERATING SYSTEM (18CS43) 21

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

Fig. 4.48 Tree-structured directory structure.

 Directories are stored the same as any other file in the system, except there is a bit
that identifies them as directories, and they have some special structure that the OS
understands.

 One question for consideration is whether or not to allow the removal of directories
that are not empty - Windows requires that directories be emptied first, and UNIX
provides an option for deleting entire sub-trees.

d) Acyclic-Graph Directories
 When the same files need to be accessed in more than one place in the directory
structure (e.g. because they are being shared by more than one user), it can be useful
to provide an acyclic-graph structure. (Note the directed arcs from parent to child. )

o UNIX provides two types of links (pointer to another file) for implementing the
acyclic-graph structure.

o A hard link (usually just called a link) involves multiple directory entries that
both refer to the same file. Hard links are only valid for ordinary files in the same
filesystem.

o A symbolic link, that involves a special file, containing information about where
to find the linked file. Symbolic links may be used to link directories and/or files
in other filesystems, as well as ordinary files in the current filesystem as shown in
Fig. 4.29.

 Windows only supports symbolic links, termed shortcuts.

 Hard links require a reference count, or link count for each file, keeping track of
how many directory entries are currently referring to this file. Whenever one of the
references is removed the link count is reduced, and when it reaches zero, the disk
space can be reclaimed.

IV SEMESTER OPERATING SYSTEM (18CS43) 22

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

Fig. 4.49 Acyclic-graph directory structure.

 For symbolic links there is some question as to what to do with the symbolic
links when the original file is moved or deleted:

o One option is to find all the symbolic links and adjust them also.

o Another is to leave the symbolic links dangling, and discover that they are no
longer valid the next time they are used.

o What if the original file is removed, and replaced with another file having the
same name before the symbolic link is next used?

Another approach to deletion is to preserve the file until all references to it are deleted. To
implement this approach, we must have some mechanism for determining that the last
reference to the file has been deleted.

When a link or a copy of the directory entry is established, a new entry is added to the file-
reference list. When a link or directory entry is deleted, we remove its entry on the list. The
file is deleted when its file-reference list is empty.

e) General Graph Directory

 If cycles are allowed in the graphs, then several problems can arise:

o Search algorithms can go into infinite loops. One solution is to not follow links in
search algorithms. (Or not to follow symbolic links, and to only allow symbolic links
to refer to directories)

o Sub-trees can become disconnected from the rest of the tree and still not havetheir
reference counts reduced to zero. Periodic garbage collection is required to detect and
resolve this problem. (chkdsk in DOS and fsck in UNIX search for these problems,
among others, even though cycles are not supposed to be allowed in either system.
Disconnected disk blocks that are not marked as free are added back to the file
systems

IV SEMESTER OPERATING SYSTEM (18CS43) 23

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

with made-up file names, and can usually be safely deleted.)

o when we add links to an existing tree-structured directory, the tree structure is

destroyed, resulting in a simple graph structure (Fig. 4.30).

Fig. 4.50 General graph directory.

4.10 File-System Mounting

The basic idea behind mounting file systems is to combine multiple file systems into one large
tree structure.
The mount command is given a filesystem to mount and a mount point (directory) on which to
attach it.
Once a file system is mounted onto a mount point, any further references to that directory
actually refer to the root of the mounted file system.

Any files (or sub-directories) that had been stored in the mount point directory prior to
mounting the new filesystem are now hidden by the mounted filesystem, and are no longer
available. For this reason, some systems only allow mounting onto empty directories (Fig.
4.31 a).

Filesystems can only be mounted by root, unless root has previously conFig.d certain
filesystems to be mountable onto certain pre-determined mount points. (E.g. root may allow
users to mount floppy filesystems to /mnt or something like it) Anyone can run the mount
command to see what filesystems are currently mounted (Fig. 4.31 b).

Filesystems may be mounted read-only, or have other restrictions imposed.

The traditional Windows OS runs an extended two-tier directory structure, where the first tier
of the structure separates volumes by drive letters, and a tree structure is implemented below
that level.

IV SEMESTER OPERATING SYSTEM (18CS43) 24

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

Macintosh runs a similar system, where each new volume that is found is automatically mounted
and added to the desktop when it is found. More recent Windows systems allow filesystems to be
mounted to any directory in the filesystem, much like UNIX.

Fig. 4.32 shows the effects of mounting the volume residing on /device/dsk over /users. If the volume is
unmounted, the file system is restored to the situation depicted in Fig. 4.31.

Fig. 4.51 File system, (a) Existing system, (b) Unmounted volume. Fig. 4.52 Mount point

4.10 File Sharing

4.10.1 Multiple Users
On a multi-user system, more information needs to be stored for each file:
The owner (user) who owns the file, and who can control its access.
The group of other user IDs that may have some special access to the file.
What access rights are afforded to the owner (User), the Group, and to the rest of the world
(the universe, a.k.a. Others.)
Some systems have more complicated access control, allowing or denying specific
accesses to specifically named users or groups.

4.10.2 Remote File Systems

The advent of the Internet introduces issues for accessing files stored on remote
computers The original method was ftp, allowing individual files to be transported across
systems as needed. Ftp can be either account and password controlled, or anonymous,
not requiring any user name or password.
Various forms of distributed file systems allow remote file systems to be mounted onto
a local directory structure, and accessed using normal file access commands. (The actual
files are still transported across the network as needed, possibly using ftp as the
underlying transport mechanism.)
The WWW has made it easy once again to access files on remote systems without
mounting their filesystems, generally using (anonymous) ftp as the underlying file
transport

IV SEMESTER OPERATING SYSTEM (18CS43) 25

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

mechanism.

a) The Client-Server Model

 When one computer system remotely mounts a filesystem that is physically located
on another system, the system which physically owns the files acts as a server, and
the system which mounts them is the client.
 User IDs and group IDs must be consistent across both systems for the system to
work properly. (I.e. this is most applicable across multiple computers managed by
the same organization, shared by a common group of users. )
 The same computer can be both a client and a server. (E.g. cross-linked file systems.
)
 There are a number of security concerns involved in this model:
o Servers commonly restrict mount permission to certain trusted systems only.
Spoofing (a computer pretending to be a different computer) is a potential
security risk.
o Servers may restrict remote access to read-only.
o Servers restrict which filesystems may be remotely mounted. Generally, the
information within those subsystems is limited, relatively public, and
protected by frequent backups.

o The NFS (Network File System) is a classic example of such a system.

b) Distributed Information Systems

 The Domain Name System, DNS, provides for a unique naming system across
all of the Internet.
 Domain names are maintained by the Network Information System, NIS, which
unfortunately has several security issues. NIS+ is a more secure version, but has
not yet gained the same widespread acceptance as NIS.
 Microsoft's Common Internet File System, CIFS, establishes a network login
for each user on a networked system with shared file access. Older
Windowssystems used domains, and newer systems (XP, 2000), use active
directories. User names must match across the network for this system to be
valid.
 A newer approach is the Lightweight Directory-Access Protocol, LDAP, which
provides a secure single sign-on for all users to access all resources on a
network. This is a secure system which is gaining in popularity, and which has
the maintenance advantage of combining authorization information in one central
location.

c) Failure Modes

 When a local disk file is unavailable, the result is generally known immediately,
and is generally non-recoverable. The only reasonable response is for the response
to fail.
 However, when a remote file is unavailable, there are many possible reasons, and
whether or not it is unrecoverable is not readily apparent. Hence most remote
access
IV SEMESTER OPERATING SYSTEM (18CS43) 26
 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

systems allow for blocking or delayed response, in the hopes that the remote
system (or the network) will come back up eventually.

4.10.3 Consistency Semantics

Consistency Semantics deals with the consistency between the views of shared files
on a networked system. When one user changes the file, when do other users see the
changes?
The series of accesses between the open () and close () operations of a file is called the
file session.

Examples of consistency semantics -

a) UNIX Semantics

 The UNIX file system uses the following semantics:

o Writes to an open file are immediately visible to any other user who has the
file open.

o One implementation uses a shared location pointer, which is adjusted for

all sharing users.
 There is a single copy of the file, which may delay some accesses.

b) Session Semantics

 The Andrew File System, AFS uses the following semantics:

o Writes to an open file are not immediately visible to other users.
o When a file is closed, any changes made become available only to users who open
the file at a later time.
 According to these semantics, a file can be associated with multiple (possibly different)
views. Almost no constraints are imposed on scheduling accesses. No user is delayed
in reading or writing their personal copy of the file.
 AFS file systems may be accessible by systems around the world. Access control is
maintained through (somewhat) complicated access control lists, which may grant
access to the entire world (literally) or to specifically named users accessing the files
from specifically named remote environments.

c) Immutable-Shared-Files Semantics
 Under this system, when a file is declared as shared by its creator, then the name
 cannot be re-used by any other process and it cannot be modified.

4.11 Protection

The information in a computer system must be stored safely without any physical damage (the
issue of reliability) and improper access (the issue of protection).
Reliabilityis generally provided by duplicate copies of files. Many computers have systems
programs that automatically copy disk files to tape at regular intervals (once per day or week or

IV SEMESTER OPERATING SYSTEM (18CS43) 27

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

month). The damage could be due to hardware problems (such as errors in reading or writing),
power surges or failures, head crashes, dirt, temperature extremes, and vandalism.

4.11.1 Types of Access

Systems that do not permit access to the files of other users do not need protection. Thus, we
could provide complete protection by prohibiting access. Alternatively, we could provide free
access with no protection. Several different types of operations may be controlled:
Read- Read from the file.
Write- Write or rewrite the file.
Execute - Load the file into memory and execute it.
Append- Write new information at the end of the file.
Delete - Delete the file and free its space for possible
reuse. List - List the name and attributes of the file.

4.11.2 Access Control

To make access to files depending on the identity of the user. Different users may need different
types of access to a file or directory. The most general scheme to implement dependent access is
to associate with each file and directory an access-control list (ACL) specifying user names and
the types of access allowed for each user. When a user requests access to a particular file, the
operating system checks the access list associated with that file. If that user is listed for the
requested access, the access is allowed. Otherwise, a protection violation occurs, and the user job
is denied access to the file.

If we want to allow everyone to read a file, we must list all users with read access. This
technique has two undesirable consequences:
Constructing such a list may be a tedious, if we do not know in advance the list of users in the
system.
The directory entry, must be of variable size, as the list grows, resulting in more complicated
space management.

These problems can be resolved by use of a condensed version of the access list. To condense the
length of the access-control list, many systems recognize three classifications of users in
connection with each file:
Owner- The user who created the file is the owner.
Group - A set of users who are sharing the file and need similar access is a group, or
work group.
Universe- All other users in the system constitute the universe.
The most common recent approach is to combine access-control lists with owner, group, and
universe access control scheme.

4.11.3 Other Protection Approaches

Associate a password with each file.
Using of password is effective, but has a few disadvantages:
The number of passwords that a user needs to remember maybe large
If one password is used, then once the password is discovered, all the files can be accessed.

IV SEMESTER OPERATING SYSTEM (18CS43) 28

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

Some system allows users to associate a password to a subdirectory, rather than only to file.

4.12 File-System Structure

Disks provide the bulk of secondary storage on which a file system is maintained. The two
characteristics that make them a convenient medium for storing multiple files:
1. A disk can be rewritten in place; it is possible to read a block from the disk, modify the
block, and write it back into the same place.
2. A disk can access directly any given block of information it contains. Thus, it is simple to
access any file either sequentially or randomly, and switching from one file to another
requires only moving the read-write heads and waiting for the disk to rotate.

To improve I/O efficiency, I/O transfers between memory and disk are performed in units
of blocks. Block sizes may range from 512 bytes to 4K or larger. (Rather than transferring
a byte at a time,)
A file system poses two quite different design problems.
 The first problem is defining how the file system should look to the user. This
task involves defining a file and its attributes, the operations allowed on a file, and
the directory structure for organizing files.
 The second problem is creating algorithms and data structures to map the logical
file system onto the physical secondary-storage devices.

File systems organize storage on disk drives, and can be viewed as a layered design:

At the lowest layer are the physical devices, consisting of the magnetic media, motors &
controls, and the electronics connected to them and controlling them. Modern disk put more
and more of the electronic controls directly on the disk drive itself, leaving relatively little
work for the disk controller card to perform.

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

The basic file system level works directly with the device drivers in terms of retrieving and
storing raw blocks of data, without any consideration for what is in each block.

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

The logical file system deals with all of the meta data associated with a file (UID, GID, mode,
dates, etc), i.e. everything about the file except the data itself. This level manages the
directory

IV SEMESTER OPERATING SYSTEM (18CS43) 29

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

structure and the mapping of file names to file control blocks, FCBs, which contain all of the
meta data as well as block number information for finding the data on the disk.

The layered approach to file systems means that much of the code can be used
uniformly for a wide variety of different file systems, and only certain layers need to be
filesystem specific.

 When a layered structure is used for file-system implementation, duplication of

code is minimized. The I/O control and sometimes the basic file-system code can
be used by multiple file systems.
 Common file systems in use include the UNIX file system, UFS, the
Berkeley Fast File System, FFS, Windows systems FAT, FAT32, NTFS, CD-
ROM systems ISO 9660, and for Linux the extended file systems ext2 and
ext3.

4.13 File-System Implementation

On disk, the file system may contain information about how to boot an operating system stored
there, the total number of blocks, the number and location of free blocks, the directory structure,
and individual files.

File systems store several important data structures on the disk:

A boot-control block, (per volume) can contain information needed by the system to boot an
operating system from that volume. If the disk does not contain an operating system, thisblock
can be empty. It is typically the first block of a volume In UFS, it is called the boot block; in
NTFS, it is the partition boot sector.
A volume control block, (per volume) contains volume (or partition) details, such as the
number of blocks in the partition, size of the blocks, free block count and free-block pointers,
and free FCB count and FCB pointers. In UFS, this is called a superblock; in NTFS, it is
stored in. the master file table.
A directory structure (per file system), containing file names and pointers to
corresponding FCBs. UNIX uses inode numbers, and NTFS uses a master file table.

The File Control Block, FCB, (per file) containing details about ownership, size,
permissions, dates, etc. UNIX stores this information in inodes, and NTFS in the
master file table as a relational database structure.

There are also several key data structures stored in memory:

An in-memory mount table contains information about each mounted volume.

An in-memory directory cache of recently accessed directoryinformation.
A system-wide open file table, containing a copy of the FCB for every currently open
file in the system, as well as some other related information as shown in Fig. 4.32.
per-process open file table, containing a pointer to the system open file table as

IV SEMESTER OPERATING SYSTEM (18CS43) 30

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

Fig. 4.53 A typical file-control block.

Fig. 4.33 illustrates some of the interactions of file system components when files are
created and/or used:

When a new file is created, a new FCB is allocated and filled out with important
information regarding the new file.

When a file is accessed during a program, the open( ) system call reads in the FCB
information from disk, and stores it in the system-wide open file table. An entry is added
to the per-process open file table referencing the system-wide table, and an index into
theper- process table is returned by the open( ) system call. UNIX refers to this index as a
file descriptor, and Windows refers to it as a file handle.

If another process already has a file open when a new request comes in for the same file,
and it is sharable, then a counter in the system-wide table is incremented and the per-
process table is adjusted to point to the existing entry in the system-wide table.

When a file is closed, the per-process table entry is freed, and the counter in the system-
wide table is decremented. If that counter reaches zero, then the system wide table is also
freed. Any data currently stored in memory cache for this file is written out to disk if
necessary.

Fig. 4.54 In-memory file-system structures, (a) File open, (b) File read.
4.13.1 Partitions and Mounting

 Physical disks are commonly divided into smaller units called partitions. They can
also be combined into larger units, but that is most commonly done for RAID
installations and is left for later chapters.

IV SEMESTER OPERATING SYSTEM (18CS43) 31

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

 Partitions can either be used as raw devices ( with no structure imposed upon them
), or "cooked;' containing a file system. they can be formatted to hold a filesystem
( i.e. populated with FCBs and initial directory structures as appropriate. ) Raw
partitions are generally used for swap space, and may also be used for certain
programs such as databases that choose to manage their own disk storage system.
Partitions containing filesystems can generally only be accessed using the file
system structure by ordinary users, but can often be accessed as a raw device also
by root.
 Boot information can be stored in a separate partition. Again, it has its ownformat,
because at boot time the system does not have file-system device drivers loaded
and therefore cannot interpret the file-system format.
 The boot block is accessed as part of a raw partition, by the boot program prior to
any operating system being loaded. Modern boot programs understand multiple
OSes and filesystem formats, and can give the user a choice of which of several
available systems to boot.
 The root partition contains the OS kernel and at least the key portions of the OS
needed to complete the boot process. At boot time the root partition is mounted,
and control is transferred from the boot program to the kernel found there. ( Older
systems required that the root partition lie completely within the first 1024
cylinders of the disk, because that was as far as the boot program could
reach.

Once the kernel had control, then it could access partitions beyond the 1024
cylinder boundary. )
 Continuing with the boot process, additional filesystems get mounted, adding their
information into the appropriate mount table structure. As a part of the mounting
process the file systems may be checked for errors or inconsistencies, either
because they are flagged as not having been closed properly the last time they
were used, or just for general principals. Filesystems may be mounted either
automatically or manually. In UNIX a mount point is indicated by setting a flag in
the in-memory copy of the inode, so all future references to that inode get re-
directed to the root directory of the mounted filesystem.

4.13.2 Virtual File Systems

Virtual File Systems, VFS, provide a common interface to multiple different

filesystem types. In addition, it provides for a unique identifier ( vnode ) for files
across the entire space, including across all filesystems of different types. (UNIX
inodes are unique only across a single filesystem, and certainly do not carry across
networked file systems.)
The VFS in Linux is based upon four key object types:
The inode object, representing an individual
file
The file object, representing an open file.
The superblock object, representing a filesystem.
The dentry object, representing an individual directory entry.
Linux VFS provides a set of common functionalities for each filesystem, using
function pointers accessed through a table. The same functionality is accessed
through the same table position for all filesystem types, though the actual functions
IV SEMESTER OPERATING SYSTEM (18CS43) 32
 RV Institute of Technology & Management®

pointed to

IV SEMESTER OPERATING SYSTEM (18CS43) 33

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

by the pointers may be filesystem-specific. Common operations provided include

open (), read( ), write(), and mmap( ).

Fig. 4.55 Schismatic view of a virtual file system.

Thus, the file-system implementation consists of three major layers, as depicted schematically in
Fig. 4.34. The first layer is the file-system interface, based on the open (), read (), write (), and
close () calls and on file descriptors. The second layer is called the virtual file system (VFS)
layer; it serves two important functions:

1. It separates file-system-generic operations from their implementation by defining a clean

VFS interface. Several implementations for the VFS interface may coexist on the same
machine, allowing transparent access to different types of file systems mounted locally.

2. The VFS provides a mechanism for uniquely representing a file throughout a network.
The VFS is based on a file-representation structure, called a vnode, that contains a
numerical designator for a network-wide unique file. (UNIX inodes are unique within
only a single file system.) This network-wide uniqueness is required for support of
network file systems. The kernel maintains one vnode structure for each active node (file
or directory).

3. The layer implementing the file system type or the remote-file-system protocol is the third
layer of the architecture.

4.14 Directory Implementation

The selection of directory-allocation and directory-management algorithms significantly affects

the efficiency, performance, and reliability of the file system. Directories need to be fast to
search, insert, and delete, with a minimum of wasted disk space.
a) Linear List
 A linear list is the simplest and easiest directory structure to set up, but it doeshave

IV SEMESTER OPERATING SYSTEM (18CS43) 34

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

some drawbacks.
 The disadvantage of a linear list of directory entries is that finding a file requires
a linear search.
 To overcome this, a software cache is implemented to store the recently
accessed directory structure.
 Deletions can be done by moving all entries, flagging an entry as deleted, or
by moving the last entry into the newly vacant position.
 A sorted list allows a binary search and decreases the average search time.
However, the requirement that the list be kept sorted may complicate creating and
deletingfiles,
 A linked list makes insertions and deletions into a sorted list easier, with overhead
for the links.
 An advantage of the sorted list is that a sorted directory listing can
beproduced without a separate sort step.

b) Hash Table

 With this method, a linear list stores the directory entries, but a hash data structure is
also used.
 The hash table takes a value computed from the file name and returns a pointer to the
file name in the linear list. Therefore, it can greatly decrease the directory search time.
 Here collisions may occur. Collision is the situation where two file names hash to the
same location.
 Alternatively, a chained-overflow hash table can be used. Each hash entry can be a linked
list instead of an individual value, and we can resolve collisions by adding the new entry
to the linked list.
 The major disadvantage with a hash table are its generally fixed size and the dependence
of the hash function on that size. For example, assume that we make a linear-probing hash
table that holds 64 entries. The hash function converts file names into integers from 0 to
63, for instance, by using the remainder of a division by 64. If we later try to create a 65th
file, we must enlarge the directory hash table—say, to 128 entries. As a result, we need a
new hash function that must map file names to the range 0 to 127, and we must
reorganize the existing directory entries to reflect their new hash-function values.

4.15 Allocation Methods

The main problem is how to allocate space to these files so that disk space is utilized effectively
and files can be accessed quickly. Three major methods of allocating disk space are in wide use:
contiguous, linked, and indexed.

a) Contiguous Allocation

 Contiguous Allocation requires that all blocks of a file be kept together

contiguously.
 Performance is very fast, because reading successive blocks of the same file
generally requires no movement of the disk heads, or at most one small step to the
next adjacent cylinder.

IV SEMESTER OPERATING SYSTEM (18CS43) 35

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

 Storage allocation is done by using one of the algorithms (first fit, best fit, worst
fit).
 The allocation of blocks contiguous leads to external fragmentation.
 Problems can arise when files grow, or if the exact size of a file is unknown at
creation time:
o Over-estimation of the file's final size increases external fragmentation and
wastes disk space.
o Under-estimation may require that a file be moved or a process aborted if
the file grows beyond its originally allocated space.
o If a file grows slowly over a long time period and the total final space
must be allocated initially, then a lot of space becomes unusable before the
file fills the space.
 A variation is to allocate file space in large contiguous chunks (Fig. 4.35),
called extents. When a file outgrows its original extent, then an additional
one block is allocated. A pointer points from last block of contiguous
memory allocation to the extended chunk.

Fig. 4.56 Contiguous allocation of disk space

b) Linked Allocation

 Disk files can be stored as linked lists, with the expense of the storage space
consumed by each link. (E.g. a block may be 508 bytes instead of 512.)
 Linked allocation involves no external fragmentation, does not require pre-known
file sizes, and allows files to grow dynamically at any time as shown in Fig. 4.36.
 Unfortunately, linked allocation is only efficient for sequential access files, as
random access requires starting at the beginning of the list for each new location
access.
 Allocating clusters of blocks reduces the space wasted by pointers, at the cost of
internal fragmentation.
 Another big problem with linked allocation is reliability if a pointer is lost or
damaged. Doubly linked lists provide some protection, at the cost of additional
overhead and wasted space.

III SEMESTER OPERATING SYSTEM (BCS303) 36

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

Fig. 4.36 Linked allocation of disk space

 The File Allocation Table, FAT, used by DOS is a variation of linked allocation,
where all the links are stored in a separate table at the beginning of the disk. The
benefit of this approach is that the FAT table can be cached in memory, greatly
improving random access speeds (Fig. 4.37).

Fig. 4.57 File-allocation table

c) Indexed Allocation

 Indexed Allocation combines all of the indexes (block numbers) for accessing
each file into a common block (for that file).
 Each file will have a common block called the index block as shown in Fig. 4.38.
 Some disk space is wasted (relative to linked lists or FAT tables) because an
entire index block must be allocated for each file, regardless of how many data
blocks the file contains. This leads to questions of how big the index block should
be, and how it should be implemented. There are several approaches:

III SEMESTER OPERATING SYSTEM (BCS303) 37

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

Fig. 4.58 Indexed allocation of disk space.

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

4.16 Performance

Optimal allocation method is different for sequential access files than for random access
files, and is also different for small files than for large files.
Some systems support more than one allocation method, which may require specifying how
the file is to be used (sequential or random access) at the time it is allocated. Such systems
also provide conversion utilities.
Some systems have been known to use contiguous access for small files, and automatically
switch to an indexed scheme when file sizes surpass a certain threshold.

III SEMESTER OPERATING SYSTEM (BCS303) 38

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

Fig. 4.59 The UNIX inode.

And of course some systems adjust their allocation schemes (e.g. block sizes ) to best match the
characteristics of the hardware for optimum performance.

4.17 Free-Space Management

The space created after deleting the files can be reused. Another important aspect of disk
management is keeping track of free space in memory. The list which keeps track of free space in
memory is called the free-space list. To create a file, search the free-space list for the required
amount of space and allocate that space to the new file. This space is then removed from the free-
space list. When a file is deleted, its disk space is added to the free-space list. The free-space list,
is implemented in different ways as explained below.

a) Bit Vector

 Fast algorithms exist for quickly finding contiguous blocks of a given size
 One simple approach is to use a bit vector, in which each bit represents a disk
block, set to 1 if free or 0 if allocated.

For example, consider a disk where blocks 2,3,4,5,8,9, 10,11, 12, 13, 17and 18 are free, and
the rest of the blocks are allocated. The free-space bit map would be
0011110011111100011

 Easy to implement and also very efficient in finding the first free block or
‗n‘ consecutive free blocks on the disk.
 The down side is that a 40GB disk requires over 5MB just to store the bitmap.

b) Linked List
 A linked list can also be used to keep track of all free blocks.

III SEMESTER OPERATING SYSTEM (BCS303) 39

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

 Traversing the list and/or finding a contiguous block of a given size are not easy,
but fortunately are not frequently needed operations (Fig. 4.40). Generally, the
system just adds and removes single blocks from the beginning of the list.
 The FAT table keeps track of the free list as just one more linked list on the table.

Fig. 4.60 Linked free-space list on disk.

c) Grouping

 A variation on linked list free lists. It stores the addresses of n free blocks in the
first free block. The first n-1 blocks are actually free. The last block contains the
addresses of another n free blocks, and so on.
 The address of a large number of free blocks can be found quickly.
d) Counting

 When there are multiple contiguous blocks of free space then the system can
keep track of the starting address of the group and the number of contiguous free
blocks.
 Rather than keeping al list of n free disk addresses, we can keep the address of
first free block and the number of free contiguous blocks that follow the first
block.
 Thus, the overall space is shortened. It is similar to the extent method of
allocating blocks.
e) Space Maps (New)
 Sun's ZFS file system was designed for huge numbers and sizes of files,
directories, and even file systems.
 The resulting data structures could be inefficient if not implemented carefully. For
example, freeing up a 1 GB file on a 1 TB file system could involve updating
thousands of blocks of free list bit maps if the file was spread across the disk.
 ZFS uses a combination of techniques, starting with dividing the disk up into
(hundreds of) metaslabs of a manageable size, each having their own space map.
 Free blocks are managed using the counting technique, but rather than write the
information to a table, it is recorded in a log-structured transaction record.
Adjacent free blocks are also coalesced into a larger single free block.
 An in-memory space map is constructed using a balanced tree data structure,
constructed from the log data.
 The combination of the in-memory tree and the on-disk log provide for very fast
and efficient management of these very large files and free blocks.
III SEMESTER OPERATING SYSTEM (BCS303) 40