Transcript File System - bca study material

File System
• A file system provides efficient and convenient
access to the disk
• The operating system imposes one or more file
systems on a disk
• A file system poses two different design problems
–Defining how the file system should look to the user
• A file and its attributes
• The operations allowed on a file
• The directory structure for organizing files
– Creating algorithms and data structures to map the
logical file system onto the physical secondarystorage devices
File Structure
Four terms are
commonly used when
discussing files:
Field
Record
File
Database
Structure Terms
Field
Record
• collection of related fields that
– basic element of data
can be treated as a unit by some
– contains a single value
application program
– fixed or variable length • One field is the key – a unique
identifier
File
Database
 collection
of related data
 relationships among elements of
data are explicit
 designed for use by a number of
different applications
 consists of one or more types of
files




collection of similar records
treated as a single entity
may be referenced by name
access control restrictions
usually apply at the file level
•
•
•
•
File Attributes
File name
Size information (current, limit)
Physical address
File type
– ASCII vs binary
– Temporary vs Permanent
• Access rights: owner, protection (who can access it)
• Access type: Sequential/Random
• History: Creator, time of last access/modification,
other usage data
• Info for managing links
4
A file system Architecture
User Program
1.Record can be maintained in the form of a
table
2.There should be optimized performance
Basic I/O
Supervisor
Basic File System
Device Drivers
Devices
3.Response time should be minimum
4.Throughput should be maximum
5.File management system should support
verities of devices
6.There should be some standard set of I/O
routines
7.Simultaneous
access
of
file
system/multiuser support
File Organization
The Pile
– Data are collected in the order they arrive
– Purpose is to accumulate a mass of data
and save it
– Records may have different fields
– No structure
– Record access is by exhaustive search
File Organization(Pile)
File Organization
The Sequential File
•Fixed format used for records
•Records are the same length
•All fields have the same (order and length)
•Field names and lengths are attributes of the file
•One field is the key filed (Primary key)
The Sequential File
•Most common form of file structure
•A fixed format is used for records
•Key field uniquely identifies the
record & determines storage order
•Typically used in batch applications
•Only organization that is easily stored
on tape as well as disk
File Organization
•
•
•
•
Indexed Sequential File
New records are added to an overflow file
Record in main file that precedes it is
updated to contain a pointer to the new
record
The overflow is merged with the main file
Multiple indexes for the same key field can
be set up to increase efficiency
Indexed File
• Records are accessed only through
their indexes
• Variable-length records can be
employed
• Exhaustive index contains one entry
for every record in the main file
• Partial index contains entries to
records where the field of interest
exists
• Used mostly in applications where
timeliness of information is critical
• Examples
would
be
airline
reservation systems and inventory
control systems
Explain how disk space is allocated using indexing
Each file has its own index block, which is an array of disk-block
addresses. The ith entry in the index block points to the ith block
of the file. The directory contains the address of the index block.
In order to find and read the ith block , we use the pointer in the
ith index block entry. This scheme is similar to paging scheme.
When the file is created, all pointers in the index block are set to
nil. When the ith block is first written, a block is obtained from
the free space manager and its address is put in the ith indexblock entry. Index allocation support direct access without
suffering from external fragmentation.
Directories
Single-Level Directory Systems
• A single level directory system
– contains 4 files
– owned by 3 different people, A, B, and C
– ownerships are shown, not file names
13
Two-level Directory Systems
Naming conflicts between different users are
eliminated
14
Hierarchical Directory Systems
A hierarchical directory system
15
Path Names
A UNIX directory tree
16
Overview (on-disk structures)
•A directory structure per file system is used to
organize the files
–In unix file systems(UFS), includes the file names and
associated inode numbers(inode is a data structure used
to represent a file system object, which can be one of
various things including a file or a directory
– In windows 2000(NTFS), it is stored in the master file
table
•A File Control Block (FCB) contains many
details about the file
– In UFS, this is called the inode
– In NTFS, this information is stored in the
master file table, with one row per file
File Access Methods
• Sequential Access
read next
write next
reset
no read after last write(rewrite)
Direct Access
read n
write n
position to n
read next
write next
rewrite n
n = relative block number
File Access Methods
• Random access
– bytes/records read in any order
– essential for data base systems
– read can be …
• move file marker (seek), then read or …
• read and then move file marker
19
The Boot Process
Chapter 4: Operating Systems and File Management
20
The Boot Process
• During the boot process, the operating system
kernel is loaded into RAM
– The kernel provides essential operating system
services
• Your computer’s small bootstrap program is
built into special ROM circuitry housed in the
computer’s system unit
Chapter 4: Operating Systems and File Management
21
MBR
The master Boot Record(MBR) is the small bit of code
that the BIOS loads and executes to start the boot
process. This code when fully executed, transfer control
to the boot program stored on the boot partition to load
the operating system.
Allocation Methods
• Allocation methods address the problem of
allocating space to files so that disk space is
utilized effectively and files can be accessed
quickly
• Three methods exist for allocating disk space
– Contiguous allocation
– Linked allocation
– Indexed allocation
File Allocation
Contiguous: A contiguous set of blocks is allocated to a
file at the time of file creation
good for sequential files
 file size must be known at the time of file creation




Suffer from external fragmentation
Chained and linked allocation: Each block
contains a pointer to the next one in the chain
 consolidation to improve locality
Indexed allocation: good both for sequential
and direct access (UNIX)
Contiguous Allocation
• Requires that each file occupy a set of contiguous
blocks on the disk
• Accessing a file is easy – only need the starting
location (block #) and length (number of blocks)
• Problems
– Finding space for a new file (first fit, best fit, etc.)
– External fragmentation (free space is broken into
small unusable chunks)
– Need for compaction, which requires file system
down time
– Determining space for a file, especially if it needs
to grow
Linked Allocation
• Disadvantages
–Can only be used effectively for sequential access of files
• Each access to a file block requires a disk access, and
some may also require a disk seek
• It is inefficient to support direct access capability
– Disk space is required to store the block pointers
•One solution is the clustering of a certain constant
number of blocks
– Relies on the integrity of the links – an error might result
in a pointer value becoming corrupt and then pointing
into the free-space list or to the blocks of another file
•A partial solution is a doubly linked list or storing a
relative block number or the file name in each block
(these schemes all require space and algorithm overhead)
Linked Allocation (continued)
File-Allocation Table (FAT)
Linked Allocation (continued)
• One variation on linked allocation is the file allocation table (FAT)
used by MS-DOS
–A section of the disk on each volume contains the FAT
–The FAT has one entry for each disk block and is indexed by
block number
–The directory entry contains the block number of the first
block of the file
–The table entry indexed by the block number of the next block in the file
–The last block contains a special EOF value as the table entry
–Unused blocks are indicated by a zero table value
–To allocate a new block to a file
•Find the first zero-valued table entry
•Replace the previous end-of-file value with the address of the new block
–Disadvantage – can result in a significant number of disk head seeks
–Advantage – random-access time is improved because the FAT can be
checked
FAT Implementation
It is a simple but efficient method of disk allocation used by MS-Dos,
OS/2. A section of the disk on each volume contains the FAT table. The
table has one entry for each disk block , and is indexed by block number.
The FAT is used as a linked list. The directory entry contains the block
number of the first block of the file. The table entry is indexed by that
block number then contains the block number of the next block in the
file. This chain continues until the last block, which has a special EOF
value as the table entry. Unused blocks are indicated by a 0 table value.
By locating a new block to a file is used to find the first 0 valued table
entry, and replacing the previous end-of-file value with the address of the
new block. The zero is then replaced with the EOF value.
FAT Implementation(Cont.)
FAT allocation scheme can result in a significant number of
head seeks, unless the FAT is cached. The disk head must
move to the start of the partition to read the FAT and find
the location of the block in question, then move to the
location of the block itself. In the worst case , both move
occurs for each block. Here random access is optimized
because the disk head can find the location of any block by
reading the information in the FAT.
Indexed Allocation
Security in Operating System
• Security breaches
• Security goals
• Protected objects of the general purpose
operating system
• Protection of objects
Threats
•
•
•
•
Interruption
Interception
Modification
Fabrication
Protecting Memory and Addressing
•
•
•
•
•
Fence
Relocation
Tagged Architecture
Segmentation
Paging
Fence
A fence is a method to confine users to one side
of a boundary.
Usually, fence is implemented via a hardware
register.
Relocation
Relocation is the process of taking a program
written as if it began at address 0 and changing
all addresses to reflect the actual address at
which the program is located in memory.
Fence register can be used within relocation
process. To each program address, the contents
of the fence register are added. This both
relocates the address and guarantees that no
one can access a location lower than a fence
address.
Paging
An alternative to segmentation is paging. The program
is divided into equal-sized pieces called pages, and
memory is divided into the same sized units, called
page frames. Each address is represented in a form
<page, offset>.
Operating system maintains a table of user page
numbers and their true addresses in memory. The page
portion of every <page, offset> reference is converted
to a page frame address by a table lookup; the offset
portion is added to the page frame address to produce
the real memory address of the object referred to as
<page, offset>.
Directory
This technique works like a file directory. Imagine the
set of objects to be files and the set of subjects to be
users of a computing system. Every file has a unique
owner who possesses “control” access rights, including
the right to declare who has what access and to revoke
access to any person at any time. Each user has a file
directory, which lists all the files to which that user has
access.
OS maintains all directories. Each user has a list
(directory) that contains all the objects that user is
allowed to access.
File Protection Mechanisms
• Basic Forms of Protection
• Single Permissions
AUTHENTICATION
• It is the process of verifying a user’s identity (who
you are) through the use of a shared secret (such as a
password), a physical token or an artifact (such as a
key or a smart card), or a biometric measure (such as
a fingerprint).
• These three types of authentication are commonly
referred to as something you have (physical token),
something you know (shared secret), and something
you are (biometric measure).
• The types and rigor of authentication methods and
technologies vary according to the security
requirements or policies associated with specific
situations and implementations
User Authentication
•
•
•
•
•
•
Use of Passwords
Attacks on Passwords
Password Selection Criteria
The Authentication Process
Flaws in the Authentication Process
Authentication other than Passwords
Passwords &Protection
The
most
common
and
least
stringent
form
of
authentication technology demands that users provide only
a valid account name and a password to obtain access to a
system or network. The password-based authentication is
one-way and normally stores the user-id and password
combination in a file that may be stored on the server in an
encrypted or plaintext file. Most people using the public email systems use this form of authentication.
Data Encryption Standard (DES)
Encryption is based on one-way functions:
functions that are cheap to compute but whose
inverse is very expensive to compute. A still widely
used, though older encryption algorithm is the Data
Encryption Standard (DES), which uses a 56bit
key.
UNIX does not encrypt passwords with a secret
key, instead, it uses the password as the key to
encrypt a standard string. The latter method is not
as vulnerable to attacks based on special properties
of the “secret” key, which must nevertheless be
known to many people.