Topic 3: File Management, Benefits, , Contiguous allocation requires…
Topic 3: File Management
Describe the various methods of file allocation: Contiguous file allocation, Linked file allocation, Indexed file allocation (CATHERINE)
Linked File Allocation
Indexed File Allocation
Contiguous File Allocation
7.Describe the two free space management techniques:
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.
For example, consider a disk where blocks 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18, 25,26, and 27 are free and the rest of the blocks are allocated.
The free-space bit map would be 001111001111110001100000011100000 ...
simplicity and efficiency in finding the first free block or n consecutive free blocks on the disk.
inefficient unless the entire vector is kept in main memory (and is written to disk occasionally for recovery needs).
Chapter 3 Part 2
Protection can be provided in many ways
When information is stored in a computer system, we want to keep it save.
Reliability is generally provided by duplicate copies of files called ‘backup’.
Small single-user system:
physically removing the floppy disks
locking them in a desk drawer or file cabinet.
In a multiuser system, these approaches cannot be applied. Other mechanisms are needed.
Chapter 3 Part 2 :Describe the Access Control Matrix approach in protection problems:
A) The most common approach to protection problem:
->make access dependent on the identity of the user.
->(Different users may need different types of access to a file or directory.)
->Associate each file and directory to an access-control list (ACL) specifying user names and the types of access allowed for each user.
A) A capability is a token, ticket, or key that gives the possessor permission to access an entity or object in a computer system.
B) A capability can be thought of as a pair (x, r) where x is the name of an object and r is a set of privileges or rights. With each subject we can store that subject's capabilities. And, the subject presents to the guard a capability in order to get access to an object.
C) Note that a capability is completely transferable; it doesn't matter who presents the capability. This framework completely eliminates the need for authentication.
D)However, with ACLs we were assuming that authentication was unforgettable. With capabilities, we now need a way to make capabilities unforgettable. The success of a capability-based mechanism depends on it.
A) The access matrix model is the policy for user authentication, and has several implementations such as “Access Control Lists (ACLs)” and “capabilities”. It is used to describe which users have access to what objects.
B)The access matrix model consists of four major parts:
->A list of objects
->A list of subjects
->A function T which returns an object's type
->The matrix itself, with the objects making the columns and the subjects making the rows
C) In the cells where a subject and object meet lie the rights the subject has on that object. Some example access rights are read, write, execute, list and delete.
Example Access Matrix:
An access matrix has several standard operations associated with it:
->Entry of a right into a specified cell
->Removal of a right from a specified cell
->Creation of a subject
->Creation of an object
->Removal of an subject
->Removal of an object
How Access List are being used?
Giving access to all users can be a problem!
Using “condensed version” of the access list.
In order to condense the length of the access-control list, three classifications of users are introduced.
The most common recent approach is to combine access-control lists with the more general (and easier to implement) owner, group, and universe access control scheme just described.
1) Jim, Dawn, and Jill in a group called “text”.
2) Sara is the “owner”.
3) Other users are called: “universe”.
1.Describe the types of operations that can be controlled:
State the benefits and weaknesses of using each of the file allocation method
Contiguous File Allocation
Linked List Allocation
Indexed File Allocation
Describe the techniques used to prevent data loss:
This is an operating system backup. It saves the database data files onto tape or some other storage media. This type of backup is often used to recover the database to the point of failure.
Types of Physical Backups
For a physical backup (often referred to as an operating system backup) the data files, redo log files and control files are saved on a backup media such as a tape storage system.
The backup is accomplished by using both Windows NT operating system utilities and Oracle database utilities.
There are two different types of physical backups.
One type is called a "COLD" backup and
the other type is called a "HOT" backup.
When choosing the type of backup strategy to use the following should be considered:
Can the database be shutdown so that a database backup can be taken. If the answer is no, then a hot database backup is the backup strategy to use. A hot backup is often used in IS shops that support 24 x 7 access.
A hot backup can be used to recover the database to the point in time of failure. Database recovery from a cold backup will only restore the database to the time when the last backup was taken.
A hot database backup requires more disk space then a cold database backup (the reason for this will be covered later in this chapter).
The logical backup technique uses the IMPORT/EXPORT utilities to create the backup copy of the database. A logical backup will backup the contents of the database.
A logical backup can be used to recover the database to the last backup
Both methods (logical and physical) can be used to restore a database.
But what happens if the disk that holds one of the tablespace data files is damaged.
Restoring the data from an IMPORT/EXPORT does not allow you to correct the damaged data file problem.
To recover the database we must first restore the tablespace's data files. For these types of situations the backup strategy to use is the physical backup.
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).
Contiguous allocation requires that each file occupy a set of contiguous blocks on the disk.
number of disk seeks required is minimal,
meaning seek time is available only when a seek is finally needed.
Accessing a file that has been allocated contiguously is easy.
Contiguous allocation has some problems:
finding space for a new file.
First fit and best fit are the most common strategies used to select a free hole from the set of available holes.
Linked Allocation solves contiguous allocation
Simple – need only starting address
Each block contains a pointer to the next block.
To read a file, we simply read blocks by following the pointers from block to block.
A file can continue to grow as long as free blocks are available.
Linked allocation solves the external-fragmentation and size-declaration problems of contiguous allocation
Brings all pointers together into the index block.
Each file has its own index block, which is an array of disk-block addresses.
Problem: wasted space,
This is extremely fast since the number of seeks are minimal because of contiguous allocation of file blocks.
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.
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.
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 can not 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.
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.
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.