Chapter 12: File Management

List the desirable properties of files

1. Long term existence

   1. kept on secondary storage

2. Sharable between processes

3. Structure

   1. internal structure of file so it can be organized to be suitable for certain applications

File structure: What is a field?

• Basic element of data

• contains a single value

• characterized by its length and data type

• can be fixed length or variable length

File structure: What is a record?

• collection of related fields

• treated as a unit

• can be variable length if some fields are variable length or if number of fields vary

File structure: What is a file?

• a collection of similar records

• treated as a single entity

• have unique file names

• may restrict access

File structure: What is a database?

• collection of related data (one or more files)

• relationships exist among elements

• managed by separate DBMS

Do UNIX bytes have internal structure?

No, they’re just streams of bytes

What is a file management system?

• set of system software providing file services to users and applications

• programmer does not need to develop file management software for each application

Objectives for a file management system

1. Meet the data management needs and requirements of the user

2. Guarantee that the data in the file are valid

3. Optimize performance

4. Provide I/O support for a variety of storage device types

5. minimize or eliminate the potential for lost of destroyed data

6. provide a standardized set of I/O interface routines

7. Provide I/O support for multiple users

User requirements for file management system

1. Should be able to create, delete, read and change files

2. May have controlled access to other users’ files.

3. May control what type of accesses are allowed to the user’s files.

4. Should be able to restructure the user’s files in a form appropriate to the problem.

5. Should be able to move data between files.

6. Should be able to back up and recover the user’s files in case of damage.

7. Should be able to access the user’s files by using symbolic names.

What does file system architecture consist of?

1. Device driver

   1. communicates directly with hardware device

2. Basic file system

   1. Handles physical I/O

3. Basic I/O supervisor

   1. Responsible for file I/O initiation and termination, device selection, I/O scheduling, buffer allocation

4. Logical I/O

   1. enables users and applications to access records

   2. provides record-oriented I/O capability

5. Access method

   1. access files based on their structure and method of access

File management functions

1. Identify and locate a selected file.

   1. Use a directory to describe the location of all files plus their attributes.

2. Enforce user access control (shared system).

3. Employ access method on the records.

4. Provide blocking for file I/O.

   1. Block for output and unblock for input.

5. Manage secondary storage

   1. Allocate files to available blocks.

   2. Manage free storage of available blocks.

   3. Scheduling of I/O requests

Criteria for choosing a file organization

1. Rapid access

2. ease of update

3. economy of storage

4. simple maintenance

5. reliability

There are a large number of file organizations. Most file organizations are related to one of the five fundamental file organizations

1. Pile

2. Sequential File

3. Indexed Sequential File

4. Indexed file

5. Direct or hashed file

How does the pile file organization work?

1. Data are collected in the order they arrive

2. Purpose is to accumulate a mass of data and save it

3. Records may have different structures or no structure

4. Data access is by exhaustive search

5. may be useful to store data prior to processing

How does the sequential file organization work?

1. Fixed format used for records

2. records are the same length

3. all fields the same (order and length)

4. field names and lengths are attributes of the file

5. one field is the key field

   1. uniquely identifies the record

   2. records are stored in key sequence

6. New records are placed in a log file or transaction file

7. log file is periodically merged with the master file

8. useful in batch processing

Drawback of sequential file

• must shift everything if you want to insert data (will make things slow for file)

  • so put new records in separate file before we merge it

• Bad for lookup b/c we can’t just jump into the middle

Indexed Sequential File Organization

• File is like a sequential file with key and data.

• Index provides a lookup capability to quickly reach the vicinity of the desired record.

• Greatly reduces the time required to access a single record, while still providing sequential processing.

• Additions can be handled by an overflow file, which can be periodically merged with the main file.

Indexed File

1. Use multiple indexes for different key fields

2. Abandons sequential format with single key

3. records are accessed only by their index

4. Records can be variable length.

5. Exhaustive index has pointers to every record.

6. Partial index only has pointers to records having the field of interest.

7. Useful in applications such as an airline reservation system that need to access particular records quickly, but rarely need to process them sequentially.

What does a direct or hash file do?

When is it useful?

• Turn key value into an address to support direct access of records in the file

• Gives very rapid access to data

• Useful if records are only accessed one at a time

How are indexes often implemented?

As B trees for low height

What information does the directory contain?

1. info about files

   1. attributes

   2. location

   3. ownership

2. Itself, directory is a file owned by the OS

What structure is used for storing the file directory?

tree structure (at top is master, beneath are users)

In a multiuser system, files should be able to be shared between users, giving us two issues….

1. Access rights

2. Simultaneous access

What rights does the owner have to a file?

all access rights and may grant rights to others

Access rights may be given to different classes of users.

Typical classes are….

1. Specific user

2. a group of users

3. All

How do file sharing access rights work?

these rights constitute a hierarchy with higher level rights including the lower level ones

When does the OS or file management system must enforce discipline?

When access is granted to append or update a file to more than one user

How may the OS or file management system enforce discipline?

1. Lock the entire file when it is to be updated

2. Another approach is to lock individual records during update

Users work with a logical view of a file as a set of records.

How does the I/O view the file?

physical view; as a set of blocks

When we write to data, what happens?

What about if we read it?

blocking of records occur

unlocking is performed

Blocking considerations

1. The larger the block, the more records that are passed in a single I/O

2. For sequential access this reduces I/O’s, but may result in unnecessary data transfer for random access.

3. Typically blocks are of fixed length to simplify the I/O transfer.

List the blocking methods

1. Fixed

2. Variable-length spanned

3. Variable-length unspanned

Explain fixed blocking method

• fixed length records

• may cause internal fragmentation

Explain variable length spanned blocking method

• variable length records which may span blocks

• permits unlimited record size

• may require multiple I/Os

Explain variable-length unspanned blocking method

• variable-length records which do not span blocks

• may cause internal fragmentation

A file consists of a collection of blocks on what device?

secondary storage device

What manages the blocks?

OS/file management system

What are two management issues when it comes to managing blocks on the secondary storage device?

1. Allocating blocks to files

2. Maintaining a list of free blocks

File allocation issues

1. Whether to allocate the maximum space required all at once, or to allocate space in portions.

2. If portions are used, how big should a portion be?

3. If portions are used, how to keep track of the portions.

What does preallocation require?

max file size be declared and allocated when the file is created (leads to overrequesting)

What does dynamic allocation allow?

ports of space to be given to the file so it can grow dynamically (but keeping track of seaprate pieces is hard)

Allocation Portion size methods

1. Large, variable-length contiguous portion

   1. good performance

   2. may cause fragmenetation

   3. simple allocation table with pointer to beginning and length

2. Small fixed-sized blocks

   1. good flexbility

   2. requires more complicated allocation table to keep track of non-contiguous blocks

Three methods of file allocation

1. Contiguous allocation

   1. a single contiguous set of blocks is allocated to a file at the time of file creation.  Thus, this is a preallocation method of a variable-size portion.  May require periodic compaction due to fragmentation.  Good for sequential file access.

2. Chained allocation

   1. allocate individual blocks.  Each block contains a pointer to the next block.

3. Indexed allocation

   1. an index specifies the location of each block.

What does the disk allocation table do?

What are its techniques?

keeps track of available space (need to know to perform allocations)

• bit tables

  • each bit represents a block

• chained free portions

  • free portions are chained together

• indexing

  • index keeps track of every free portion as if it was a file

• Free block list

  • blocks are numbered and list of free block numbers is maintained