UNIT III

MEMORY MANAGEMENT AND FILE SYSTEMS

Main Memory – Background, Swapping, Contiguous Memory Allocation, Paging, Segmentation –
Virtual Memory – Demand Paging, Page Replacement, Allocation, Thrashing; Allocating Kernel Memory.
Mass Storage system - HDD Scheduling - File concept, Access methods, Directory Structure, Sharing and
Protection; File System Structure, Directory implementation, Allocation Methods, Free Space Management
Main Memory

● 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

● Memory unit only sees a stream of addresses + read requests, or address + data and write
requests

● Register access in one CPU clock (or less)

● Main memory can take many cycles, causing a stall

 ● 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 address space

● CPU must check every memory access generated in user mode to be sure it is between base
and limit for that user

HARDWARE PROTECTION
ADDRESS BINDING
● Programs on disk, ready to be brought into memory to execute form an input queue

o Without support, must be loaded into address 0000

● Inconvenient to have first user process physical address always at 0000

o How can it not be?

● Further, addresses represented in different ways at different stages of a program’s life

o Source code addresses usually symbolic

o Compiled code addresses bind to relocatable addresses

▪ i.e. ―14 bytes from beginning of this module‖

 o Linker or loader will bind relocatable addresses to absolute addresses

▪ i.e. 74014

o Each binding maps one address space to another

● Address binding of instructions and data to memory addresses can happen at three different
stages

o Compile time: If memory location known a priori, absolute code can be generated; must
recompile code if starting location changes
o Load time: Must generate relocatable code if memory location is not known at compile time

o Execution time: Binding delayed until run time if the process can be moved during its
execution from one memory segment to another

▪ Need hardware support for address maps (e.g., base and limit registers)

MULTISTEP PROCESSING
LOGICAL VS PHYSICAL ADDRESS

● The concept of a logical address space that is bound to a separate physical address space
is central to proper memory management

o Logical address – generated by the CPU; also referred to as virtual address

o Physical address – address seen by the memory unit

● Logical and physical addresses are the same in compile-time and load-time address- binding
schemes; logical (virtual) and physical addresses differ in execution-time address-binding
scheme

● Logical address space is the set of all logical addresses generated by a program
- Physical address space is the set of all physical address generated by a program MMU

● Hardware device that at run time maps virtual to physical address

● Many methods possible, covered in the rest of this chapter

● To start, consider simple scheme where the value in the relocation register is added to every
address generated by a user process at the time it is sent to memory

o Base register now called relocation register

o MS-DOS on Intel 80x86 used 4 relocation registers

● The user program deals with logical addresses; it never sees the real physical addresses

o Execution-time binding occurs when reference is made to location in memory

o Logical address bound to physical addresses

DYNAMIC ALLOCATION

● Routine is not loaded until it is called

● Better memory-space utilization; unused routine is never loaded

● All routines kept on disk in relocatable load format

● Useful when large amounts of code are needed to handle infrequently occurring cases

● No special support from the operating system is required

o Implemented through program design

o OS can help by providing libraries to implement dynamic loading

DYNAMIC LINKING
Static Linking

System Libraries and program code combined by the loader into the binary program image

● Dynamic linking –linking postponed until execution time

● Small piece of code, stub, used to locate the appropriate memory-resident library routine

● Stub replaces itself with the address of the routine, and executes the routine

● Operating system checks if routine is in processes’ memory address

o If not in address space, add to address space

● Dynamic linking is particularly useful for libraries

● System also known as shared libraries

● Consider applicability to patching system libraries

o Versioning may be needed

SWAPPING

● A process can be swapped temporarily out of memory to a backing store, and then brought back
into memory for continued execution
 o Total physical memory space of processes can exceed physical memory

● Backing store – fast disk large enough to accommodate copies of all memory images for all
users; must provide direct access to these memory images

● Roll out, roll in – swapping variant used for priority-based scheduling algorithms; lower-
priority process is swapped out so higher-priority process can be loaded and executed

● Major part of swap time is transfer time; total transfer time is directly proportional to the amount
of memory swapped

● System maintains a ready queue of ready-to-run processes which have memory images on disk

● Does the swapped out process need to swap back in to same physical addresses?

● Depends on address binding method

o Plus consider pending I/O to / from process memory space

● Modified versions of swapping are found on many systems (i.e., UNIX, Linux, and Windows)

o Swapping normally disabled

o Started if more than threshold amount of memory allocated

 CONTIGUOUS ALLOCATION

● Main memory must support both OS and user processes

● Limited resource, must allocate efficiently

● Contiguous allocation is one early method

● Main memory usually into two partitions:

o Resident operating system, usually held in low memory with interrupt vector

o User processes then held in high memory

o Each process contained in single contiguous section of memory

● Relocation registers used to protect user processes from each other, and from changing
operating-system code and data

o Base register contains value of smallest physical address

o Limit register contains range of logical addresses – each logical address must be less than
the limit register

o MMU maps logical address dynamically

o Can then allow actions such as kernel code being transient and kernel changing size
 FRAGMENTATION

● External Fragmentation – total memory space exists to satisfy a request, but it is not
contiguous

● Internal Fragmentation – allocated memory may be slightly larger than requested memory;
this size difference is memory internal to a partition, but not being used

● First fit analysis reveals that given N blocks allocated, 0.5 N blocks lost to fragmentation

o 1/3 may be unusable -> 50-percent rule

● Reduce external fragmentation by compaction

o Shuffle memory contents to place all free memory together in one large block

o Compaction is possible only if relocation is dynamic, and is done at execution time

o I/O problem

▪ Latch job in memory while it is involved in I/O

▪ Do I/O only into OS buffers

● Now consider that backing store has same fragmentation problems

PAGING

● Physical address space of a process can be noncontiguous; process is allocated physical memory
whenever the latter is available
 o Avoids external fragmentation

o Avoids problem of varying sized memory chunks

● Divide physical memory into fixed-sized blocks called frames

o Size is power of 2, between 512 bytes and 16 Mbytes

Divide logical memory into blocks of same size called pages

● Keep track of all free frames

● To run a program of size N pages, need to find N free frames and load program

● Set up a page table to translate logical to physical addresses

● Backing store likewise split into pages

● Still have Internal fragmentation

● Address generated by CPU is divided into:

o Page number (p) – used as an index into a page table which contains base address of
each page in physical memory

o Page offset (d) – combined with base address to define the physical memory address that
is sent to the memory unit

o For given logical address space 2m and page size 2n

page number page offset

p d
 m -n n

PAGING STRUCTURE

● Calculating internal fragmentation

o Page size = 2,048 bytes

o Process size = 72,766 bytes

o 35 pages + 1,086 bytes

o Internal fragmentation of 2,048 - 1,086 = 962 bytes

o Worst case fragmentation = 1 frame – 1 byte

o On average fragmentation = 1 / 2 frame size

 o So small frame sizes desirable?

o But each page table entry takes memory to track

o Page sizes growing over time

▪ Solaris supports two page sizes – 8 KB and 4 MB

● Process view and physical memory now very different

● By implementation process can only access its own memory

● Page table is kept in main memory

● Page-table base register (PTBR) points to the page table

● Page-table length register (PTLR) indicates size of the page table

● In this scheme every data/instruction access requires two memory accesses

o One for the page table and one for the data / instruction

● The two memory access problem can be solved by the use of a special fast-lookup hardware
cache called associative memory or translation look-aside buffers (TLBs)

● Some TLBs store address-space identifiers (ASIDs) in each TLB entry – uniquely identifies
each process to provide address-space protection for that process

o Otherwise need to flush at every context switch

● TLBs typically small (64 to 1,024 entries)

● On a TLB miss, value is loaded into the TLB for faster access next time
o Replacement policies must be considered

o Some entries can be wired down for permanent fast access

 ASSOCIATIVE MEMORY
Address translation (p, d)

o If p is in associative register, get frame # out

o Otherwise get frame # from page table in memory

Page # Frame #

PAGING WITH TLB

MEMORY PROTECTION

● Memory protection implemented by associating protection bit with each frame to indicate if read-only
or read-write access is allowed

o Can also add more bits to indicate page execute-only, and so on

● Valid-invalid bit attached to each entry in the page table:

o ―valid‖ indicates that the associated page is in the process’ logical address space, and is thus a
legal page
 o ―invalid‖ indicates that the page is not in the process’ logical address space

o Or use page-table length register (PTLR)

● Any violations result in a trap to the kernel

VALID OR INVALID BIT IN PAGE TABLE

STRUCTURE OF THE PAGE TABLE

● Memory structures for paging can get huge using straight-forward methods

o Consider a 32-bit logical address space as on modern computers

o Page size of 4 KB (212)

o Page table would have 1 million entries (232 / 212)

o If each entry is 4 bytes -> 4 MB of physical address space / memory for page table alone

▪ That amount of memory used to cost a lot

▪ Don’t want to allocate that contiguously in main memory

● Hierarchical Paging

● Hashed Page Tables

● Inverted Page Tables TWO LEVEL PAGE SCHEME

● A logical address (on 32-bit machine with 1K page size) is divided into:

o a page number consisting of 22 bits

o a page offset consisting of 10 bits

o Since the page table is paged, the page number is further divided into:

o a 12-bit page number

o a 10-bit page offset

o Thus, a logical address is as follows:

● where p1 is an index into the outer page table, and p2 is the displacement within the page of the inner
page table

● Known as forward-mapped page table Address Translation Scheme

 SEGMENTATION

Memory-management scheme that supports user view of memory A program is a collection of segments

● Logical address consists of a two tuple:

▪ <segment-number, offset>,

● Segment table – maps two-dimensional physical addresses; each table entry has:

o base – contains the starting physical address where the segments reside in memory

o limit – specifies the length of the segment

o Segment-table base register (STBR) points to the segment table’s location in memory

▪ Segment-table length register (STLR) indicates number of segments used by a program;gment number s is legal
if s < STLR
VIRTUAL MEMORY

VIRTUAL ADDRESS SPACE

● Usually design logical address space for stack to start at Max logical address and grow
―down‖ while heap grows ―up‖

o Maximizes address space use

o Unused address space between the two is hole

▪ No physical memory needed until heap or stack grows to a given new page

● Enables sparse address spaces with holes left for growth, dynamically linked libraries, etc

● System libraries shared via mapping into virtual address space

● Shared memory by mapping pages read-write into virtual address space

● Pages can be shared during fork(), speeding process creation

SHARED LIBRARY USING VIRTUAL MEMORY

DEMAND PAGING
Could bring entire process into memory at load time

● Or bring a page into memory only when it is needed

o Less I/O needed, no unnecessary I/O

o Less memory needed

o Faster response

o More users

● Similar to paging system with swapping (diagram on right)

 Lazy swapper – never swaps a page into memory unless page will be needed

o Swapper that deals with pages is a pager

● With swapping, pager guesses which pages will be used before swapping out again

● Instead, pager brings in only those pages into memory

● How to determine that set of pages?

Need new MMU functionality to implement demand paging If pages needed are already memory resident
No difference from non demand-paging

● If page needed and not memory resident

o Need to detect and load the page into memory from storage

▪ Without changing program behavior

o Initially valid–invalid bit is set to i on all entries

o With each page table entry a valid–invalid bit is associated (v in-memory –

memory resident, i not-in-memory)

▪ Without programmer needing to change code

 ● Example of a page table snapshot:

● During MMU address translation, if valid–invalid bit in page table entry is i.

● page fault If there is a reference to a page, first reference to that page will trap to operating
system:
PAGE FAULT
● Operating system looks at another table to decide: Invalid reference abort and Just not in memory
1. Find free frame
2. Swap page into frame via scheduled disk operation
3. Reset tables to indicate page now in memory Set validation bit = v
4. Restart the instruction that caused the page fault
5. Extreme case start process with no pages in memory
6. Actually, a given instruction could access multiple pages -> multiple page faults
7. Page table with valid / invalid bit
PERFORMANCE

n Stages in Demand Paging (worse case)

1. Trap to the operating system

2. Save the user registers and process state

3. Determine that the interrupt was a page fault

4. Check that the page reference was legal and determine the location of the page on the disk

5. Issue a read from the disk to a free frame:

1. Wait in a queue for this device until the read request is serviced
 2. Wait for the device seek and/or latency time

3. Begin the transfer of the page to a free frame

6. While waiting, allocate the CPU to some other user

7. Receive an interrupt from the disk I/O subsystem (I/O completed)

8. Save the registers and process state for the other user

9. Determine that the interrupt was from the disk

10. Correct the page table and other tables to show page is now in memory

11. Wait for the CPU to be allocated to this process again

12. Restore the user registers, process state, and new page table, and then resume the interrupted instruction

PAGE REPLACEMENT

● Prevent over-allocation of memory by modifying page-fault service routine to include page

replacement

● Use modify (dirty) bit to reduce overhead of page transfers – only modified pages are written to
disk

● Page replacement completes separation between logical memory and physical memory – large
virtual memory can be provided on a smaller physical memory
 NEED
BASIC PAGE REPLACEMENT

1. Find the location of the desired page on disk

2. Find a free frame:

- If there is a free frame, use it
- If there is no free frame, use a page replacement algorithm to select a victim frame
- Write victim frame to disk if dirty

3. Bring the desired page into the (newly) free frame; update the page and frame tables

4. Continue the process by restarting the instruction that caused the trap

ALGORITHMS

● Frame-allocation algorithm determines

o How many frames to give each process

o Which frames to replace

● Page-replacement algorithm

o Want lowest page-fault rate on both first access and re-access

 ● Evaluate algorithm by running it on a particular string of memory references (reference string) and
computing the number of page faults on that string

o String is just page numbers, not full addresses

o Repeated access to the same page does not cause a page fault

o Results depend on number of frames available

● In all our examples, the reference string of referenced page numbers is

▪ 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1

FIFO

OPTIMAL ALGORITHM

LRU
Keep a pool of free frames, always

o Then frame available when needed, not found at fault time

o Read page into free frame and select victim to evict and add to free pool

o When convenient, evict victim

● Possibly, keep list of modified pages

o When backing store otherwise idle, write pages there and set to non-dirty

● Possibly, keep free frame contents intact and note what is in them

o If referenced again before reused, no need to load contents again from disk

o Generally useful to reduce penalty if wrong victim frame selected

Each process needs minimum number of frames

● Example: IBM 370 – 6 pages to handle SS MOVE instruction:

o instruction is 6 bytes, might span 2 pages

o 2 pages to handle from

o 2 pages to handle to

● Maximum of course is total frames in the system

● Two major allocation schemes

o fixed allocation

o priority allocation
● Many variations

THRASHING

● If a process does not have ―enough‖ pages, the page-fault rate is very high

o Page fault to get page

o Replace existing frame

o But quickly need replaced frame back

o This leads to:

▪ Low CPU utilization

▪ Operating system thinking that it needs to increase the degree of multiprogramming

▪ Another process added to the system

● Thrashing a process is busy swapping pages in and out

● Why does demand paging work?

Locality model

● Process migrates from one locality to another

● Localities may overlap

● Why does thrashing occur?

size of locality > total memory size

● Limit effects by using local or priority page replacement

MASS STORAGE SYSTEM

● One of the responsibilities of the operating system is to use the hardware efficiently.

● A fast access time and

● High disk bandwidth.

● The access time has two major components;

● The seek time is the time for the disk arm to move the heads to the cylinder containing the desired sector.

● The rotational latency is the additional time waiting for the disk to rotate the desired sector to the disk head.

● The disk bandwidth is the total number of bytes transferred, divided by the total time between the first request
for service and the completion of the last transfer.
HDD SCHEDULING
The operating system is responsible for using hardware efficiently - for the disk drives, this means having a fast
access time and disk bandwidth.
Access time has two major components
Seek time
It is the time for the disk arm to move the heads to the cylinder containing the desired sector.
Rotational latency
It is the additional time waiting for disk to rotate the desired sector to the disk head.
Disk bandwidth is the total number of bytes transferred, divided by the total time between the first request for service
and the completion of the last transfer.
Improve seek time and disk bandwidth by scheduling the servicing of disk I/O request in a good order.
Type of Disk Scheduling
FCFS –The I/O requests are serviced strictly in the same order as they are received.
It generally does not provide the fastest service.
the order of request is- (82,170,43,140,24,16,190)
And current position of Read/Write head is: 50

So, total overhead movement (total distance covered by the disk arm) =
(82-50)+(170-82)+(170-43)+(140-43)+(140-24)+(24-16)+(190-16) =642
Total head movement of 640 cylinders
SSTF -Shortest Seek Time First
Selects the request with the minimum seek time from the current head position.
Seek time increases with no. of cylinders traversed by the head.
Sometimes it may cause starvation of some request.
It is a form of SJF scheduling; may cause starvation of some requests.
It is the substantial improvement over FCFS, it is not optimal

So, total overhead movement (total distance covered by the disk arm) =
(50-43)+(43-24)+(24-16)+(82-16)+(140-82)+(170-140)+(190-170) =208
Total head movement of 208 cylinders
CAN -The disk arm starts at one end of the disk, and moves toward the other end, servicing requests until it gets to the
her end of the disk, where the head movement is reversed and servicing continues.
is also called as Elevator algorithm.

o, total overhead movement (total distance covered by the disk arm) = (199-50) + (199-16) =332
request arrives in the queue just in front of the head, it will be serviced almost immediately request arrives just behind
e head will have to wait until the arm moves to the end of disk, reverses direction & comes back.
-SCAN
ircular SCAN
Provides a more uniform wait time than SCAN.

he head moves from one end of the disk to the other. Servicing requests as it goes. When it reaches the other end,
owever, it immediately returns to the beginning of the disk, without servicing any requests on the return trip.
t treats the cylinders as a circular list that wraps around from the last cylinder to the first one.
Look-The disk arm moves once from cylinder 0 side to cylinder n side and then back to cylinder 0 side and keeps
ervicing requests on the way.
Arm goes only as far as the final request in each direction. Then, it reverses direction immediately, without going all the
way to the end of the disk
o, total overhead movement (total distance covered by the disk arm) = (190-50) + (190-16) = 314
C-Look-Arm only goes as far as the last request in each direction, then reverses direction immediately, without first
oing all the way to the end of the disk.

.
FILE CONCEPT

File System
A file is a named collection of related information that is recorded on secondary storage.
From a user’s perspective, a file is the smallest allotment of logical secondary storage;
that is, data cannot be written to secondary storage unless they are within a file.
Examples of files:
A text file is a sequence of characters organized into lines (and possibly pages).
A source file is a sequence of subroutines and functions, each of which is further organized
as declarations followed by executable statements.
An object file is a sequence of bytes organized into blocks understandable by the
system’s linker.
An executable file is a series of code sections that the loader can bring into memory and
execute.
File Attributes
Name: The symbolic file name is the only information kept in human readable form.

Identifier: This unique tag, usually a number identifies the file within the file system. It is the non-human readable
name for the file.

Type: This information is needed for those systems that support different types.

Location: This information is a pointer to a device and to the location of the file on that device.

Size: The current size of the file (in bytes, words or blocks) and possibly the maximum allowed size are included in
this attribute.
Protection: Access-control information determines who can do reading, writing, executing
and so on.

Time, date and user identification: This information may be kept for creation, last modification and last use. These
data can be useful for protection, security and usage monitoring.
File Operations

● Creating a file

● Writing a file

● Reading a file

● Repositioning within a file

● Deleting a file

● Truncating a file

The two primitive operations are appending and renaming the file. The operating system use a small table called open
file table which containing the information about all opened files.

It uses the open() system call before opening the file. The open file table also has an open count associated with each
file to indicate how many process have the file open.
Each close() decreases this open count and when open count reaches zero, the file is no longer in use, and file’s entry is
removed from the open file table.

Common File Types

ACCESS METHODS
Sequential access
In sequential access, the OS read the file word by word. A pointer is maintained which initially points to the base
address of the file. If the user wants to read first word of the file then the pointer provides that word to the user and
increases its value by 1 word. This process continues till the end of the file.

Direct Access

The Direct Access is mostly required in the case of database systems. In most of the cases, we need filtered information
from the database. The sequential access can be very slow and inefficient in such cases.

Indexed Access
If a file can be sorted on any of the filed then an index can be assigned to a group of certain records. However, A
particular record can be accessed by its index. The index is nothing but the address of a record in the file.

DIRECTORY STRUCTURE
The file system of computers can be [Link] we need to organize them. This organization is done in two parts:
First disk is split into one or more partition, also known as minidisks.
Second partition contains information about files within it. this information is kept in entries in a device directory.
Device Directory records information about Name, location, size and type for all files on that partition.
A Typical File System Organization

Search for a file

We need to be able to search a directory structure to find the entry for a particular file.
Create a file
New a file is no longer need; we want to remove it from the directory.
Delete a file
When a file is no longer needed, we want to remove it from the directory.
List a directory
We need to be able to list the files in a directory and the contents of the directory entry for each file in the list.
Rename a file
The content of the file must be changeable.
Traverse the file system
Copying all files to magnetic tape, this technique provides a backup in case of system failure.
There are five directory structures.
They are as follows:
[Link]-level directory
[Link]-level directory
[Link]-Structured directory
[Link] Graph directory
[Link] Graph directory
Single-level directory
The simplest directory structure is the single- level directory.
All files are contained in the same directory.
Disadvantage

When the number of files increases or when the system has more than one user, since all files are in the same directory,
they must have unique names.

Advantages
Since it is a single directory, so its implementation is very easy.
If the files are smaller in size, searching will become faster.
The operations like file creation, searching, deletion, updating are very easy in such a directory structure.
Disadvantages
There may chance of name collision because two files can have the same name.
Searching will become time taking if the directory is large.
This cannot group the same type of files together.
Two Level Directory
Each has own user file directory(UFD).
File names only need to be unique within a given user's directory.

A master file directory is used to keep track of each user’s directory, and must be maintained when users are added to
or removed from the system.

A separate directory is generally needed for system (executable) files.

Systems may or may not allow users to access other directories besides their own

If access to other directories is allowed, then provision must be made to specify the directory being accessed.

If access is denied, then special consideration must be made for users to run programs located in system directories.
A search path is the list of directories in which to search for executable programs, and can be set uniquely for each
user.
Advantages

● The main advantage is there can be more than two files with same name, and would be very helpful if there are
multiple users.

● A security would be there which would prevent user to access other user’s files.

● Searching of the files becomes very easy in this directory structure.

Disadvantages

● As there is advantage of security, there is also disadvantage that the user cannot share the file with the other users.

● Unlike the advantage users can create their own files, users don’t have the ability to create subdirectories.

● Scalability is not possible because one user can’t group the same types of files together.

[Link]-Structured directory
A tree is the most common directory structure.

The tree has a root directory. Every file in the system has a unique path name.

A path name is the path from the root, through all the subdirectories to a specified file.
A directory (or sub directory) contains a set of files or sub directories.

● A directory is simply another file. But it is treated in a special way.

● All directories have the same internal format.

● 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 path names or relative path names.

● An absolute path name begins at the root and follows a path down to the specified file, giving the directory names

on the path.

● A relative path name defines a path from the current directory.

Advantages

● This directory structure allows subdirectories inside a directory.

● The searching is easier.

Disadvantages

● As the user isn’t allowed to access other user’s directory, this prevents the file sharing among users.

● As the user has the capability to make subdirectories, if the number of subdirectories increase the searching

may become complicated.

 4. Acyclic Graph Directory

● An acyclic graph is a graph with no cycles. To implement shared files and subdirectories this directory structure is

used.

● An acyclic – graph directory structure is more flexible than is a simple tree structure, but it is also more complex.

In a system where sharing is implemented by symbolic link, this situation is somewhat easier to handle. The
deletion of a link does not need to affect the original file; only the link is removed. 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.

Advantages
Sharing of files and directories is allowed between multiple users.
Searching becomes too easy.
Flexibility is increased as file sharing and editing access is there for multiple users.
Disadvantages
Because of the complex structure it has, it is difficult to implement this directory structure.
The user must be very cautious to edit or even deletion of file as the file is accessed by multiple users.
If we need to delete the file, then we need to delete all the references of the file inorder to delete it permanently.

General Graph Directory

The general-graph directory can have cycles, meaning a directory can contain paths that loop back to the starting point.
This can make navigating and managing files more complex.
Advantages
More flexible than other directory structures.
Allows cycles, meaning directories can loop back to each other.
Disadvantages
More expensive to implement

SHARING AND PROTECTION

When information is stored in a computer system, we want to keep it safe from physical damage (the issue of
reliability) and improper access (the issue of protection). Reliability is generally provided by duplicate copies of files.
Many computers have systems programs that automatically (or through computer-operator intervention) copy disk files
to tape at regular intervals (once per day or week or month) to maintain a copy should a file system be accidentally
destroyed. File systems can be damaged by hardware problems (such as errors in reading or writing), power surges or
failures, head crashes, dirt, temperature extremes, and vandalism. Files may be deleted accidentally. Bugs in the file-
system software can also cause file contents to be lost.
File System structure
Hard disks have two important properties that make them suitable for secondary storage of files in file systems:
(1) Blocks of data can be rewritten in place
(2) they are direct access, allowing any block of data to be accessed with only (relatively) minor movements of the disk
heads and rotational latency.
File systems organize storage on disk drives, and can be viewed as a layered design.
Layers of file system

There are six layers. Each layers give support to neighbor layers. It also
provides function to above layer and below layer. Each layer uses the features
of neighbor layer while creating new features for use by the higher levels.
File system creates two main design problems:
1. Creation of algorithm and data structure for of mapping of logical file system to physical secondary storage devices.
2. File system view for user.
A basic file system only to issue generic commands to the appropriate device driver to read and write physical blocks
on the disk. It also manages the memory buffer and caches that hold various file system, directory and data blocks.
When buffer is full, the buffer manager must find more buffer memory or free up buffer space to allow a requested I/O
complete.
Caches are used to hold frequently used file system meta data to improve performance.
Application program layer: User/programmer creates an application programs.
Logical file system layer: It manages metadata information. Operating system maintains file control block for each
file.
File organization modules layer: This layer maintains information about files and be their logical blocks and physical
blocks. It translates the logical block address to physical block address by considering physical location of files and file
allocation method.
Basic file system layer: It generates the command for device drivers. Particular device driver read data and writes
physical blocks on the disk.
Input-output control interface: It consists of device driver and interrupt handler. Both are used for data transfer
between main memory and disk system.
Devices: It contains actual hardware device link disk, memory.
File organization module
It knows about files and their logical blocks as well as physical blocks.
It translates logical block addresses to the physical block for the basic file system to transfer.
Logical file system
It manages meta data information which includes all of the file system structure except the actual data.
It maintains the file system via file – control block(FCB).
It also responsible for file system protection and security.
FCB
It contains information about file, including ownership, permissions and location of the file contents.
When a layered structure is used for file system implementation, duplication of code is minimized.

Operating system File system formats

Windows XP,NT and 2000 FAT,FAT32,NTFS
UNIX UNIX file system(UFS)
Standard LINUX Extended file system
DIRECTORY IMPLEMENTATION
Directory Implementation The selection of directory-allocation and directory-management algorithms significantly
affects the efficiency, performance, and reliability of the file system.
LINEAR LIST
The simplest method of implementing a directory is to use a linear list of file names with pointers to the data blocks.
This method is simple to program but time-consuming to execute. To create a new file, we must first search the
directory to be sure that no existing file has the same name. Then, we add a new entry at the end of the directory. To
delete a file, we search the directory for the named file and then release the space allocated to it. To reuse the directory
entry, we can do one of several things. A linked list can also be used to decrease the time required to delete a file. The
real disadvantage of a linear list of directory entries is that finding a file requires a linear search. Directory information
is used frequently, and users will notice if access to it is slow.
HASH TABLE
Another data structure used for a file directory is a hash table. Here, a linear list stores the directory entries, but a hash
data structure is also used. The hash table takes a value computed from the file name and returns a pointer to the file
name in the linear list. Therefore, it can greatly decrease the directory search time. Insertion and deletion are also fairly
straightforward, although some provision must be made for collisions—situations in which two file names hash to the
same location. The major difficulties with a hash table are its generally fixed size and the dependence of the hash
function on that size.
ALLOCATION METHODS
The allocation methods define how the files are stored in the disk blocks.
There are three main disk space or file allocation methods.
1. Contiguous Allocation
2. Linked Allocation
3. Indexed Allocation
The main idea behind these methods is to provide:
Efficient disk space utilization.
Fast access to the file blocks.
All the three methods have their own advantages and disadvantages as discussed below:
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.
Storage allocation involves the same issues discussed earlier for the allocation of contiguous blocks of memory (first
fit, best fit, fragmentation problems, etc.) The distinction is that the high time penalty required for moving the disk
heads from spot to spot may now justify the benefits of keeping files contiguously when possible. In this scheme, each
file occupies a contiguous set of blocks on the disk.

For example, if a file requires n blocks and is given a block b as the starting location, then the blocks assigned to the
file will be: b, b+1, b+2, ......b+n-1. This means that given the starting block address and the length of the file (in terms
of blocks required), we can determine the blocks occupied by the file.
The directory entry for a file with contiguous allocation contains
Address of starting block
Length of the allocated portion.
Advantages:
Both the Sequential and Direct Accesses are supported by this. For direct access, the address of the kth block of the file
which starts at block b can easily be obtained as (b+k).
This is extremely fast since the number of seeks are minimal because of contiguous allocation of file blocks.
Disadvantages:
This method suffers from both internal and external fragmentation. This makes it inefficient in terms of memory
utilization.
Increasing file size is difficult because it depends on the availability of contiguous memory at a particular instance.
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.
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.
In this scheme, each file is a linked list of disk blocks which need not be contiguous. The disk blocks can be scattered
anywhere on the disk.
The directory entry contains a pointer to the starting and the ending file block. Each block contains a pointer to the next
block occupied by the file.
The file ‘jeep’ in following image shows how the blocks are randomly distributed. The last block (25) contains -1
indicating a null pointer and does not point to any other block.
Advantages
This is very flexible in terms of file size. File size can be increased easily since the system does not have to look for a
contiguous chunk of memory.
This method does not suffer from external fragmentation. This makes it relatively better in terms of memory
utilization.
Disadvantages:
Because the file blocks are distributed randomly on the disk, a large number of seeks are needed to access every block
individually. This makes linked allocation slower.
It does not support random or direct access. We cannot directly access the blocks of a file. A block k of a file can be
accessed by traversing k blocks sequentially (sequential access) from the starting block of the file via block pointers.
Pointers required in the linked allocation incur some extra overhead.

FAT (File Allocation Table)

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.
Indexed Allocation
Indexed Allocation combines all of the indexes for accessing each file into a common block (for that file), as opposed
to spreading them all over the disk or storing them in a FAT table.

Advantages:
This supports direct access to the blocks occupied by the file and therefore provides fast access to the
file blocks.
It overcomes the problem of external fragmentation.
Disadvantages:
The pointer overhead for indexed allocation is greater than linked allocation.
For very small files, say files that expand only 2-3 blocks, the indexed allocation would keep one entire
block (index block) for the pointers which is inefficient in terms of memory utilization. However, in linked allocation
we lose the space of only 1 pointer per block.
Some disk space is wasted (relative to linked lists or FAT tables) because an entire index block must be allocated for
each file, regardless of how many data blocks the file contains. This leads to questions of how big the index block
should be, and how it should be implemented.
There are several approaches:
Linked Scheme - An index block is one disk block, which can be read and written in a single disk operation. The first
index block contains some header information, the first N block addresses, and if necessary a pointer to additional
linked index blocks
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 or so data block pointers are stored
directly in the inode, and then singly, doubly, and triply indirect pointers provide access to more data blocks as needed.
The advantage of this scheme is that for small files (which many are ), the data blocks are readily accessible ( up to
48K with 4K block sizes ); files up to about 4144K ( using 4K blocks ) are accessible with only a single indirect block (
which can be cached ),and huge files are still accessible using a relatively small number of disk accesses ( larger in
theory than can be addressed by a 32-bit address, which is why some systems have moved to 64-bit file pointers.)
FREE SPACE MANAGEMENT
Since disk space is limited, we need to reuse the space from deleted files for new files, if possible.
To keep track of free disk space, the system maintains a free-space [Link] free-space list records all free disk blocks –
those not allocated to some file or [Link] create a file, we search the free-space list for the required amount of
space, and allocate that space to the new [Link] space is then removed from the free-space [Link] a file is deleted,
its disk space is added to the free-space list.

1. Bit Vector
The free-space list is implemented as a bit map or bit vector.
Each block is represented by 1 bit. If the block is free, the bit is 1; if the block is allocated, the bit is 0.
2,3,4,5,8,9,10,11,12,13,17,18,25,26 and 27 are free, and the rest of the block are allocated. The free space bit map
would be
001111001111110001100000011100000 …
The main advantage of this approach is its relatively simplicity and efficiency in finding the first free block, or n
consecutive free blocks on the disk.
2. Linked List
Another approach to free-space management is to link together all the free disk blocks, keeping a pointer to the first
free block in a special location on the disk and caching it in memory.
This first block contains a pointer to the next free disk block, and so on. In our example, we would keep a pointer to
block 2, as the first free block. Block 2 would contain a pointer to block 3, which would point to block 4, which would
point to block 5, which would point to block 8, and so on.
However, this scheme is not efficient; to traverse the list, we must read each block, which requires substantial I/O time.
The FAT method incorporates free-block accounting data structure. No separate method is needed.
3. Grouping
A modification of the free-list approach is to store the addresses of n free blocks in the first free block.
The first n-1 of these blocks are actually free.
The last block contains the addresses of another n free blocks, and so on.
The importance of this implementation is that the addresses of a large number of free blocks can be found
quickly.
4. Counting
We can keep the address of the first free block and the number n of free contiguous blocks that follow the first
[Link] entry in the free-space list then consists of a disk address and a count. Although each entry requires more
space than would a simple disk address, the overall list will be shorter, as long as the count is generally greater than1.
Recovery
Files and directories are kept both in main memory and on disk, and care must be taken to ensure that system failure
does not result in loss of data or in data inconsistency.
1. Consistency Checking
The directory information in main memory is generally more up to date than is the corresponding information on the
disk, because cached directory information is not necessarily written to disk as soon as the update takes
[Link], a special program is run at reboot time to check for and correct disk inconsistencies.
The consistency checker—a systems program such as chkdsk in MS-DOS—compares the data in the directory
structure with the data blocks on disk and tries to fix any inconsistencies it finds. The allocation and free-space-
management algorithms dictate what types of problems the checker can find and how successful it will be in fixing
them.
2. Backup and Restore
Magnetic disks sometimes fail, and care must be taken to ensure that the data lost in such a failure are not lost forever.
To this end, system programs can be used to back up data from disk to another storage device, such as a floppy disk,
magnetic tape, optical disk, or other hard [Link] from the loss of an individual file, or of an entire disk, may
then be a matter of restoring the data from backup.