OS Unit-5

 

Input/Output devices

Input/Output devices are the devices that are responsible for the input/output operations in a computer system.

Basically there are following two types of input/output devices:

• Block devices
• Character devices

Block Devices

A block device stores information in block with fixed-size and own-address.

It is possible to read/write each and every block independently in case of block device.

In case of disk, it is always possible to seek another cylinder and then wait for required block to rotate under head without mattering where the arm currently is. Therefore, disk is a block addressable device.

Character Devices

A character device accepts/delivers a stream of characters without regarding to any block structure.

Character device isn't addressable.

Character device doesn't have any seek operation.

There are too many character devices present in a computer system such as printer, mice, rats, network interfaces etc. These four are the common character devices.

Input/Output Devices Examples

Here are the list of some most popular and common input/output devices:

• Keyboard
• Mouse
• Monitor
• Modem
• Scanner
• Laser Printer
• Ethernet
• Disk

Kernel I/O Subsystem

The kernel provides many services related to I/O. Several services such as scheduling, caching, spooling, device reservation, and error handling – are provided by the kernel, s I/O subsystem built on the hardware and device-driver infrastructure. The I/O subsystem is also responsible for protecting itself from errant processes and malicious users. 

 

1. I/O Scheduling – 
   To schedule a set of I/O requests means to determine a good order in which to execute them. The order in which the application issues the system call is the best choice. Scheduling can improve the overall performance of the system, can share device access permission fairly to all the processes, reduce the average waiting time, response time, turnaround time for I/O to complete. 
   OS developers implement schedules by maintaining a wait queue of the request for each device. When an application issue a blocking I/O system call, The request is placed in the queue for that device. The I/O scheduler rearranges the order to improve the efficiency of the system. 
    

2. Buffering – 
   A buffer is a memory area that stores data being transferred between two devices or between a device and an application. Buffering is done for three reasons. 
   1. The first is to cope with a speed mismatch between producer and consumer of a data stream. 
       
   2. The second use of buffering is to provide adaptation for data that have different data-transfer sizes. 
       
   3. The third use of buffering is to support copy semantics for the application I/O, “copy semantic ” means, suppose that an application wants to write data on a disk that is stored in its buffer. it calls the write() system’s call, providing a pointer to the buffer and the integer specifying the number of bytes to write. 
       
3. Caching – 
   A cache is a region of fast memory that holds a copy of data. Access to the cached copy is much easier than the original file. For instance, the instruction of the currently running process is stored on the disk, cached in physical memory, and copied again in the CPU’s secondary and primary cache. 

   The main difference between a buffer and a cache is that a buffer may hold only the existing copy of a data item, while a cache, by definition, holds a copy on faster storage of an item that resides elsewhere. 

    

4. Spooling and Device Reservation – 
   A spool is a buffer that holds the output of a device, such as a printer that cannot accept interleaved data streams. Although a printer can serve only one job at a time, several applications may wish to print their output concurrently, without having their output mixes together. 

   The OS solves this problem by preventing all output from continuing to the printer. The output of all applications is spooled in a separate disk file. When an application finishes printing then the spooling system queues the corresponding spool file for output to the printer. 

    

5. Error Handling – 
   An Os that uses protected memory can guard against many kinds of hardware and application errors so that a complete system failure is not the usual result of each minor mechanical glitch, Devices, and I/O transfers can fail in many ways, either for transient reasons, as when a network becomes overloaded or for permanent reasons, as when a disk controller becomes defective. 

    

6. I/O Protection – 
   Errors and the issue of protection are closely related. A user process may attempt to issue illegal I/O instructions to disrupt the normal function of a system. We can use the various mechanisms to ensure that such disruption cannot take place in the system. 
   To prevent illegal I/O access, we define all I/O instructions to be privileged instructions. The user cannot issue I/O instruction directly. 

I/O buffering

A buffer is a memory area that stores data being transferred between two devices or between a device and an application.

Uses of I/O Buffering :

• Buffering is done to deal effectively with a speed mismatch between the producer and consumer of the data stream.
• A buffer is produced in main memory to heap up the bytes received from modem.
• After receiving the data in the buffer, the data get transferred to disk from buffer in a single operation.
• This process of data transfer is not instantaneous, therefore the modem needs another buffer in order to store additional incoming data.
• When the first buffer got filled, then it is requested to transfer the data to disk.
• The modem then starts filling the additional incoming data in the second buffer while the data in the first buffer getting transferred to disk.
• When both the buffers completed their tasks, then the modem switches back to the first buffer while the data from the second buffer get transferred to the disk.
• The use of two buffers disintegrates the producer and the consumer of the data, thus minimizes the time requirements between them.
• Buffering also provides variations for devices that have different data transfer sizes.

Types of various I/O buffering techniques :

1. Single buffer :

A buffer is provided by the operating system to the system portion of the main memory.

Block oriented device –

• System buffer takes the input.
• After taking the input, the block gets transferred to the user space by the process and then the process requests for another block.
• Two blocks works simultaneously, when one block of data is processed by the user process, the next block is being read in.
• OS can swap the processes.
• OS can record the data of system buffer to user processes.

Stream oriented device –

• Line- at a time operation is used for scroll made terminals. User inputs one line at a time, with a carriage return signaling at the end of a line.
• Byte-at a time operation is used on forms mode, terminals when each keystroke is significant.

2. Double buffer :

Block oriented –

• There are two buffers in the system.
• One buffer is used by the driver or controller to store data while waiting for it to be taken by higher level of the hierarchy.
• Other buffer is used to store data from the lower level module.
• Double buffering is also known as buffer swapping.
• A major disadvantage of double buffering is that the complexity of the process get increased.
• If the process performs rapid bursts of I/O, then using double buffering may be deficient.

Stream oriented –

• Line- at a time I/O, the user process need not be suspended for input or output, unless process runs ahead of the double buffer.
• Byte- at a time operations, double buffer offers no advantage over a single buffer of twice the length.

3. Circular buffer :

• When more than two buffers are used, the collection of buffers is itself referred to as a circular buffer.
• In this, the data do not directly passed from the producer to the consumer because the data would change due to overwriting of buffers before they had been consumed.
• The producer can only fill up to buffer i-1 while data in buffer i is waiting to be consumed.

Disk Storage

Hard Disk Structure In OS

Hard disk is secondary storage which stores the large amount of data. The Hard disk drive contains a dozens of disks.  These disks are also known as platters. These platters are mount over the spindle which rotates in any direction i.e. clockwise or anti-clockwise. Lets look at hard disk structure in OS.

Platter

• The Platter is made of aluminum or iron oxide.
• Platter diameter range is 1.8 inches to 5.25 inches
• Each platter contains 2 surfaces and 2 Read/Write Head. One Read/Write head requires for one surface of the platter. So, other R/W head use for other surface to store the information’s.
• Every platter holds the same no. of tracks.
• Multiple platters increase the storage capacity.

R/W Head

• R/W Heads moves forth and back over the platter surfaces to Read or Write the data on sectors.
• Read/Write heads does not touch to platters surface. The data written over the platter surface is done through magnetic field. If R/W Head touches over the surface of platter then bad sectors may creates. Had disk may damage due to these bad sectors.

Tracks

• Circular areas of disk are known as tracks.
• There may be more than a 1000 tracks on a 3.5 inch hard disk and sector size. Track Numbering start with zero at outermost track.

Sectors

Tracks are further divided into number of small units; these small units are known as sectors. Sectors are the smallest physical storage units on disk. Size of each sector is almost always 512 Bytes. Sector Numbering start with 1 at outermost tracks.

Cylinder

All Corresponding tracks with same radius of all platters in the Hard disk are known as cylinders.  In simple words we say

“Each tack of all platters with same radius is called a cylinder”

So, Number of tracks in platter is always equal to number of cylinders. For example, a hard disk, where each platter contains 600 tracks then the number of cylinders will also be 600 in the hard disk.

Cylinder Numbering start with zero at outermost cylinder.

Cluster

Cluster is also known as blocks. Group of sectors makes a cluster. There may be 64 or sectors in a cluster. These clusters are used by OS to Read/Write the data.

Disk Capacity

As we know there are number of platters in the hard disk. Each platter contains two R/W heads. There are number of cylinder/tracks in the hard disk. Each track is divided into number of sectors. And each sector has some size but mostly size of sector is 512 Bytes.

Structure of a magnetic disk

A magnetic disk contains several platters. Each platter is divided into circular shaped tracks. The length of the tracks near the centre is less than the length of the tracks farther from the centre. Each track is further divided into sectors, as shown in the figure.

Tracks of the same distance from centre form a cylinder. A read-write head is used to read data from a sector of the magnetic disk.

The disk is divided into tracks. Each track is further divided into sectors. The point to be noted here is that outer tracks are bigger in size than the inner tracks but they contain the same number of sectors and have equal storage capacity. This is because the storage density is high in sectors of the inner tracks where as the bits are sparsely arranged in sectors of the outer tracks. Some space of every sector is used for formatting. So, the actual capacity of a sector is less than the given capacity.

Read-Write(R-W) head moves over the rotating hard disk. It is this Read-Write head that performs all the read and write operations on the disk and hence, position of the R-W head is a major concern. To perform a read or write operation on a memory location, we need to place the R-W head over that position. Some important terms must be noted here:

1. Seek time – The time taken by the R-W head to reach the desired track from it’s current position.
2. Rotational latency – Time taken by the sector to come under the R-W head.
3. Data transfer time – Time taken to transfer the required amount of data. It depends upon the rotational speed.
4. Controller time – The processing time taken by the controller.
5. Average Access time – seek time + Average Rotational latency + data transfer time + controller time.

Note:Average Rotational latency is mostly 1/2*(Rotetional latency).

In questions, if the seek time and controller time is not mentioned, take them to be zero.

If the amount of data to be transferred is not given, assume that no data is being transferred. Otherwise, calculate the time taken to transfer the given amount of data.

The average of rotational latency is taken when the current position of R-W head is not given. Because, the R-W may be already present at the desired position or it might take a whole rotation to get the desired sector under the R-W head. But, if the current position of the R-W head is given then the rotational latency must be calculated.

Question 01: Let suppose there are 8 platters in hard disk drive. As each platters has two surfaces so 16 surfaces will be there in hard drive. Therefore, required R/W head will also be 16. Suppose, there are 1,024 cylinders and 128 sectors in each track. The sector size is 512 bytes.Then

A). Calculate Disk Size?
B). How many number of bits required to represent the disk size?

Part A. Solution

Size of Hard Disk = Cylinder x Heads X Sectors x Sector-Size 
= 1,024 x 16 x 128 x 512 Bytes
=  210 + 24 + 27 + 29 Bytes = 230Bytes = 2GB

Part B. Solution

As 2GB = 230 So, 30 bits are required to represent  2GB hard disk.

Question-02:  Find the size of Single platter if track size 1KB and there are 1024 cylinder? 

Solution: As there is a single platter So, Heads requirement will be 2.

Size of Platter = Cylinder x Heads X track size (because, Track size = Sectors x Sector-Size)
= 210 + 21 + 210 Bytes
=21+220 Bytes = 2MB

Question 03: Why does sector number addressing in CHS (Cylinder Head Sector) start at sector 1 and not 0?

Answer: For all translation modes, Cylinder (C) =0, Head (H) =0 and Sector (S) =1 is equivalent to Logical Block Address (LBA) =0. So the value of Sector is always 1.

Question-03: 

Consider a hard disk with:

4 surfaces

64 tracks/surface

128 sectors/track

256 bytes/sector

1. What is the capacity of the hard disk?
   Disk capacity = surfaces * tracks/surface * sectors/track * bytes/sector
   Disk capacity = 4 * 64 * 128 * 256
   Disk capacity = 8 MB
2. The disk is rotating at 3600 RPM, what is the data transfer rate?
   60 sec -> 3600 rotations
   1 sec -> 60 rotations
   Data transfer rate = number of rotations per second * track capacity * number of surfaces (since 1 R-W head is used for each surface)
   Data transfer rate = 60 * 128 * 256 * 4
   Data transfer rate = 7.5 MB/sec
3. The disk is rotating at 3600 RPM, what is the average access time?
   Since, seek time, controller time and the amount of data to be transferred is not given, we consider all the three terms as 0.
   Therefore, Average Access time = Average rotational delay
   Rotational latency => 60 sec -> 3600 rotations
   1 sec -> 60 rotations
   Rotational latency = (1/60) sec = 16.67 msec.
   Average Rotational latency = (16.67)/2
   = 8.33 msec.
   Average Access time = 8.33 msec.

Logical structure

Logical division of hard disk is generally divided into 5 basic terms which are

• MBR (Master Boot Record)
• DBR (DOS Boot Record)
• FAT (File Allocation Tables)
• Root Directory
• Data Area

Disk Scheduling Algorithms

Disk scheduling is done by operating systems to schedule I/O requests arriving for the disk. Disk scheduling is also known as I/O scheduling.

Disk scheduling is important because:

• Multiple I/O requests may arrive by different processes and only one I/O request can be served at a time by the disk controller. Thus other I/O requests need to wait in the waiting queue and need to be scheduled.
• Two or more request may be far from each other so can result in greater disk arm movement.
• Hard drives are one of the slowest parts of the computer system and thus need to be accessed in an efficient manner.

There are many Disk Scheduling Algorithms but before discussing them let’s have a quick look at some of the important terms:

• Seek Time:Seek time is the time taken to locate the disk arm to a specified track where the data is to be read or write. So the disk scheduling algorithm that gives minimum average seek time is better.
• Rotational Latency: Rotational Latency is the time taken by the desired sector of disk to rotate into a position so that it can access the read/write heads. So the disk scheduling algorithm that gives minimum rotational latency is better.
• Transfer Time: Transfer time is the time to transfer the data. It depends on the rotating speed of the disk and number of bytes to be transferred.
• Disk Access Time: Disk Access Time is:

      Disk Access Time = Seek Time + 
                         Rotational Latency + 
                         Transfer Time

• Disk Response Time: Response Time is the average of time spent by a request waiting to perform its I/O operation. Average Response time is the response time of the all requests. Variance Response Time is measure of how individual request are serviced with respect to average response time. So the disk scheduling algorithm that gives minimum variance response time is better.

Disk Scheduling Algorithms

1. FCFS: FCFS is the simplest of all the Disk Scheduling Algorithms. In FCFS, the requests are addressed in the order they arrive in the disk queue.Let us understand this with the help of an example.

   Example:

   Suppose the order of request is- (82,170,43,140,24,16,190)
   And current position of Read/Write head is : 50
   
   So, total seek time:
   =(82-50)+(170-82)+(170-43)+(140-43)+(140-24)+(24-16)+(190-16)
   =642

Advantages:

• Every request gets a fair chance
• No indefinite postponement

Disadvantages:

• Does not try to optimize seek time
• May not provide the best possible service

2. SSTF: In SSTF (Shortest Seek Time First), requests having shortest seek time are executed first. So, the seek time of every request is calculated in advance in the queue and then they are scheduled according to their calculated seek time. As a result, the request near the disk arm will get executed first. SSTF is certainly an improvement over FCFS as it decreases the average response time and increases the throughput of system.Let us understand this with the help of an example.

   Example:

   Suppose the order of request is- (82,170,43,140,24,16,190)
   And current position of Read/Write head is : 50
   

   So, total seek time:

   =(50-43)+(43-24)+(24-16)+(82-16)+(140-82)+(170-40)+(190-170)
   =208

Advantages:

• Average Response Time decreases
• Throughput increases

Disadvantages:

• Overhead to calculate seek time in advance
• Can cause Starvation for a request if it has higher seek time as compared to incoming requests
• High variance of response time as SSTF favours only some requests

3. SCAN: In SCAN algorithm the disk arm moves into a particular direction and services the requests coming in its path and after reaching the end of disk, it reverses its direction and again services the request arriving in its path. So, this algorithm works as an elevator and hence also known as elevator algorithm. As a result, the requests at the midrange are serviced more and those arriving behind the disk arm will have to wait.

   Example:

   Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the Read/Write arm is at 50, and it is also given that the disk arm should move “towards the larger value”.
   

   Therefore, the seek time is calculated as:

   =(199-50)+(199-16)
   =332

Advantages:

• High throughput
• Low variance of response time
• Average response time

Disadvantages:

• Long waiting time for requests for locations just visited by disk arm

4. CSCAN: In SCAN algorithm, the disk arm again scans the path that has been scanned, after reversing its direction. So, it may be possible that too many requests are waiting at the other end or there may be zero or few requests pending at the scanned area.

These situations are avoided in CSCAN algorithm in which the disk arm instead of reversing its direction goes to the other end of the disk and starts servicing the requests from there. So, the disk arm moves in a circular fashion and this algorithm is also similar to SCAN algorithm and hence it is known as C-SCAN (Circular SCAN).

Example:

Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the Read/Write arm is at 50, and it is also given that the disk arm should move “towards the larger value”.

Seek time is calculated as:

=(199-50)+(199-0)+(43-0)

=391

Advantages:

• Provides more uniform wait time compared to SCAN

5. LOOK: It is similar to the SCAN disk scheduling algorithm except for the difference that the disk arm in spite of going to the end of the disk goes only to the last request to be serviced in front of the head and then reverses its direction from there only. Thus it prevents the extra delay which occurred due to unnecessary traversal to the end of the disk.

   Example:

   Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the Read/Write arm is at 50, and it is also given that the disk arm should move “towards the larger value”.
   

   So, the seek time is calculated as:

   =(190-50)+(190-16)
   =314

6. CLOOK: As LOOK is similar to SCAN algorithm, in similar way, CLOOK is similar to CSCAN disk scheduling algorithm. In CLOOK, the disk arm in spite of going to the end goes only to the last request to be serviced in front of the head and then from there goes to the other end’s last request. Thus, it also prevents the extra delay which occurred due to unnecessary traversal to the end of the disk.

   Example:

   Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the Read/Write arm is at 50, and it is also given that the disk arm should move “towards the larger value”
   
   So, the seek time is calculated as:
   =(190-50)+(190-16)+(43-16)
   =341

7. RSS– It stands for random scheduling and just like its name it is nature. It is used in situations where scheduling involves random attributes such as random processing time, random due dates, random weights, and stochastic machine breakdowns this algorithm sits perfect. Which is why it is usually used for and analysis and simulation.
8. LIFO– In LIFO (Last In, First Out) algorithm, newest jobs are serviced before the existing ones i.e. in order of requests that get serviced the job that is newest or last entered is serviced first and then the rest in the same order.

   Advantages

   • Maximizes locality and resource utilization

   Disadvantages

   • Can seem a little unfair to other requests and if new requests keep coming in, it cause starvation to the old and existing ones.
   Example
   Suppose the order of request is- (82,170,43,142,24,16,190)
   And current position of Read/Write head is : 50

   

9. N-STEP SCAN – It is also known as N-STEP LOOK algorithm. In this a buffer is created for N requests. All requests belonging to a buffer will be serviced in one go. Also once the buffer is full no new requests are kept in this buffer and are sent to another one. Now, when these N requests are serviced, the time comes for another top N requests and this way all get requests get a guaranteed service

   Advantages

   • It eliminates starvation of requests completely
10. FSCAN– This algorithm uses two sub-queues. During the scan all requests in the first queue are serviced and the new incoming requests are added to the second queue. All new requests are kept on halt until the existing requests in the first queue are serviced.
    Advantages
    • FSCAN along with N-Step-SCAN prevents “arm stickiness” (phenomena in I/O scheduling where the scheduling algorithm continues to service requests at or near the current sector and thus prevents any seeking)

Each algorithm is unique in its own way. Overall Performance depends on the number and type of requests.

Note:Average Rotational latency is generally taken as 1/2(Rotational latency).

RAID

RAID or redundant array of independent disks is a data storage virtualization technology that combines multiple physical disk drive components into one or more logical units for data redundancy, performance improvement, or both.

It is a way of storing the same data in different places on multiple hard disks or solid-state drives to protect data in the case of a drive failure. A RAID system consists of two or more drives working in parallel. These can be hard discs, but there is a trend to use SSD technology (Solid State Drives).

RAID combines several independent and relatively small disks into single storage of a large size. The disks included in the array are called array members. The disks can combine into the array in different ways, which are known as RAID levels. Each of RAID levels has its own characteristics of:

• Fault-tolerance is the ability to survive one or several disk failures.
• Performance shows the change in the read and writes speed of the entire array compared to a single disk.
• The array's capacity is determined by the amount of user data written to the array. The array capacity depends on the RAID level and does not always match the sum of the RAID member disks' sizes. To calculate the particular RAID type's capacity and a set of member disks, you can use a free online RAID calculator.

RAID systems can use with several interfaces, including SATA, SCSI, IDE, or FC (fiber channel.) Some systems use SATA disks internally but that have a FireWire or SCSI interface for the host system.

Sometimes disks in a storage system are defined as JBOD, which stands for Just a Bunch of Disks. This means that those disks do not use a specific RAID level and acts as stand-alone disks. This is often done for drives that contain swap files or spooling data.

How RAID Works

RAID works by placing data on multiple disks and allowing input/output operations to overlap in a balanced way, improving performance. Because various disks increase the mean time between failures (MTBF), storing data redundantly also increases fault tolerance.

RAID arrays appear to the operating system as a single logical drive. RAID employs the techniques of disk mirroring or disk striping.

• Disk Mirroring will copy identical data onto more than one drive.
• Disk Striping partitions help spread data over multiple disk drives. Each drive's storage space is divided into units ranging from 512 bytes up to several megabytes. The stripes of all the disks are interleaved and addressed in order.
• Disk mirroring and disk striping can also be combined in a RAID array.

In a single-user system where significant records are stored, the stripes are typically set up to be small (512 bytes) so that a single record spans all the disks and can be accessed quickly by reading all the disks at the same time.

In a multi-user system, better performance requires a stripe wide enough to hold the typical or maximum size record, allowing overlapped disk I/O across drives.

Levels of RAID

Many different ways of distributing data have been standardized into various RAID levels. Each RAID level is offering a trade-off of data protection, system performance, and storage space. The number of levels has been broken into three categories, standard, nested, and non-standard RAID levels.

Standards RAID Levels

Below are the following most popular and standard RAID levels.

1. RAID 0 (striped disks)

RAID 0 is taking any number of disks and merging them into one large volume. It will increase speeds as you're reading and writing from multiple disks at a time. But all data on all disks is lost if any one disk fails. An individual file can then use the speed and capacity of all the drives of the array. The downside to RAID 0, though, is that it is NOT redundant. The loss of any individual disk will cause complete data loss. This RAID type is very much less reliable than having a single disk.

There is rarely a situation where you should use RAID 0 in a server environment. You can use it for cache or other purposes where speed is essential, and reliability or data loss does not matter at all.

2. RAID 1 (mirrored disks)

It duplicates data across two disks in the array, providing full redundancy. Both disks are store exactly the same data, at the same time, and at all times. Data is not lost as long as one disk survives. The total capacity of the array equals the capacity of the smallest disk in the array. At any given instant, the contents of both disks in the array are identical.

RAID 1 is capable of a much more complicated configuration. The point of RAID 1 is primarily for redundancy. If you completely lose a drive, you can still stay up and running off the other drive.

If either drive fails, you can then replace the broken drive with little to no downtime. RAID 1 also gives you the additional benefit of increased read performance, as data can read off any of the drives in the array. The downsides are that you will have slightly higher write latency. Since the data needs to be written to both drives in the array, you'll only have a single drive's available capacity while needing two drives.

3. RAID 5(striped disks with single parity)

RAID 5 requires the use of at least three drives. It combines these disks to protect data against loss of any one disk; the array's storage capacity is reduced by one disk. It strips data across multiple drives to increase performance. But, it also adds the aspect of redundancy by distributing parity information across the disks.

4. RAID 6 (Striped disks with double parity)

RAID 6 is similar to RAID 5, but the parity data are written to two drives. The use of additional parity enables the array to continue to function even if two disks fail simultaneously. However, this extra protection comes at a cost. RAID 6 has a slower write performance than RAID 5.

The chances that two drives break down at the same moment are minimal. However, if a drive in a RAID 5 system died and was replaced by a new drive, it takes a lot of time to rebuild the swapped drive. If another drive dies during that time, you still lose all of your data. With RAID 6, the RAID array will even survive that second failure also.

Nested RAID levels

Some RAID levels are referred to as nested RAID because they are based on a combination of RAID levels, such as:

1. RAID 10 (1+0)

This level Combines RAID 1 and RAID 0 in a single system, which offers higher performance than RAID 1, but at a much higher cost.

This is a nested or hybrid RAID configuration. It provides security by mirroring all data on secondary drives while using striping across each set of drives to speed up data transfers.

2. RAID 01 (0+1)

RAID 0+1 is similar to RAID 1+0, except the data organization method is slightly different. Rather than creating a mirror and then striping the mirror, RAID 0+1 creates a stripe set and then mirrors the stripe set.

3. RAID 03 (0+3, also known as RAID 53 or RAID 5+3)

This level uses striping similar to RAID 0 for RAID 3's virtual disk blocks. This offers higher performance than RAID 3 but at a higher cost.

4. RAID 50 (5+0)

This configuration combines RAID 5 distributed parity with RAID 0 striping to improve RAID 5 performance without reducing data protection.

Non-standard RAID levels

Non-standard RAID levels vary from standard RAID levels, and they are usually developed by companies or organizations for mainly proprietary use, such as:

1. RAID 7

A non-standard RAID level is based on RAID 3 and RAID 4 that adds caching. It includes a real-time embedded OS as a controller, caching via a high-speed bus, and other stand-alone computer characteristics.

2. Adaptive RAID

This level enables the RAID controller to decide how to store the parity on disks. It will choose between RAID 3 and RAID 5, depending on which RAID set type will perform better with the kind of data being written to the disks.

3. Linux MD RAID 10

The Linux kernel provides this level. It supports the creation of nested and non-standard RAID arrays. Linux software RAID can also support standard RAID 0, RAID 1, RAID 4, RAID 5, and RAID 6 configurations.

Implementation of RAID

The distribution of data across multiple drives can manage either by computer hardware or by software.

1. Hardware-based

Hardware-based RAID requires a dedicated controller installed in the server. Hardware RAID controllers can be configured through card BIOS or Option ROM before an operating system is booted. And after the operating system is booted, proprietary configuration utilities are available from each controller's manufacturer.

Hardware RAID is created using separate hardware. There are two options:

• AN inexpensive RAID chippossibly built into the motherboard.
• More expensive option with a complex stand-alone RAID controller. These controllers can be equipped with their CPU, battery-backed up cache memory, and typically hot-swapping.

A hardware-based RAID card does all the RAID array(s) management, providing logical disks to the system with no overhead on the part of the system itself. Additionally, hardware RAID can offer many different types of RAID configurations simultaneously to the system. This includes providing a RAID 1 array for the boot and application drive and a RAID-5 array for the large storage array.

Some other operating systems have implemented their own generic frameworks for interfacing with any RAID controller and provide tools for monitoring RAID volume status. A hardware RAID has some advantages over a software RAID, such as:

• It doesn't use the CPU of the host computer.
• It allows users to create boot partitions.
• It handles errors better since it communicates with the devices directly.
• It supports hot-swapping.

2. Software RAID

Software RAID is an included option in all of Steadfast's dedicated servers. This means there is NO cost for software RAID 1 and is highly recommended if you're using local storage on a system. It is highly recommended that drives in a RAID array be of the same type and size. Software RAID is one of the cheapest RAID solutions.

Software-based RAID will control some of the system's computing power to manage the RAID configuration. If you're looking to maximize a system's performance, such with a RAID 5 or 6 configurations, it's best to use a hardware-based RAID card when you're using standard HDDs.

Many modern operating systems provide software RAID implementations. Software RAID can be implemented as:

• A layer that abstracts multiple devices, thereby providing a single virtual machine.
• A layer that sits above any file system and provides parity protection to user data.

If a boot drive fails, the system must be sophisticated enough to boot from the remaining drive or drives.

There are certain limitations on the use of the software RAID to boot the system. Only RAID 1 can contain boot partition, while system boot is impossible with software RAID 5 and RAID 0.

In most cases, software RAID doesn't implement the hot-swapping, and so it cannot be used where continuous availability is required.

Benefits of RAID

Benefits of RAID include the following.

• An improvement in cost-effectiveness because lower-priced disks are used in large numbers.
• The use of multiple hard drives enables RAID to improve the performance of a single hard drive.
• Increased computer speed and reliability after a crash depending on the configuration.
• There is increased availability and resiliency with RAID 5. With mirroring, RAID arrays can have two drives containing the same data. It ensures one will continue to work if the other fails.

Drawbacks of RAID

RAID has the following drawbacks or disadvantages:

• Nested RAID levels are more expensive to implement than traditional RAID levels because they require many disks.
• The cost per gigabyte of storage devices is higher for nested RAID because many of the drives are used for redundancy.
• When a drive fails, the probability that another drive in the array will also soon fail rises, which would likely result in data loss. This is because all the drives in a RAID array are installed simultaneously. So all the drives are subject to the same amount of wear.
• Some RAID levels, such as RAID 1 and 5, can only sustain a single drive failure.
• RAID arrays are in a vulnerable state until a failed drive is replaced and the new disk is populated with data.
• When RAID was implemented, it takes a lot longer to rebuild failed drives because drives have much greater capacity.

However, nested RAID levels address these problems by providing a greater degree of redundancy, significantly decreasing the chances of an array-level failure due to simultaneous disk failures.

File Concepts

File Concept

Computer store information in storage media such as disk, tape drives, and optical disks. The operating system provides a logical view of the information stored in the disk. This logical storage unit is a file.

The information stored in files are non-volatile, means they are not lost during power failures. A file is named collection of related information that is stored on physical storage.

Data cannot be written to a computer unless it is written to a file. A file, in general, is a sequence of bits, bytes, lines, or records defined by its owner or creator. The file has a structure defined by its owner or creator and depends on the file type.

• Text file – It has a sequence of characters.
• Image file – It has visual information such as photographs, vectors art and so on.
• Source file – It has subroutines and function that are compiled later.
• Object file – It has a sequence of bytes, organized into bytes and used by the linker.
• Executable file – The binary code that the loader brings to memory for execution is stored in an exe file.

File Attributes

A file has a single e editable name given by its creator. The name never changes unless a user has necessary permission to change the file name. The names are given because it is humanly understandable.

The properties of a file can be different on many systems, however, some of them are common:

1. Name – unique name for a human to recognize the file.
2. Identifier – A unique number tag that identifies the file in the file system, and non-human readable.
3. Type – Information about the file to get support from the system.
4. Size – The current size of the file in bytes, kilobytes, or words.
5. Access Control – Defines who could read, write, execute, change, or delete the file in the system.
6. Time, Date, and User identification – This information kept for date created, last modified, or accessed and so on.

The information about the file is kept in a directory structure which also resides on the secondary storage.

File Organization

It is used to determine an efficient file organization for each base relation. For example, if we want to retrieve student records in alphabetical order of name, sorting the file by student name is a good file organization. However, if we want to retrieve all students whose marks is in a certain range, a file ordered by student name would not be a good file organization. Some file organizations are efficient for bulk loading data into the database but inefficient for retrieve and other activities.

The objective of this selection is to choose an optimal file organization for each relation.

Types of File Organization

In order to make effective selection of file organizations and indexes, here we present the details different types of file Organization. These are:

Heap (unordered) File Organization

An unordered file, sometimes called a heap file, is the simplest type of file organization.

Records are placed in file in the same order as they are inserted. A new record is inserted in the last page of the file; if there is insufficient space in the last page, a new page is added to the file. This makes insertion very efficient. However, as a heap file has no particular ordering with respect to field values, a linear search must be performed to access a record. A linear search involves reading pages from the file until the required is found. This makes retrievals from heap files that have more than a few pages relatively slow, unless the retrieval involves a large proportion of the records in the file.

To delete a record, the required page first has to be retrieved, the record marked as deleted, and the page written back to disk. The space with deleted records is not reused. Consequently, performance progressively deteriorates as deletion occurs. This means that heap files have to be periodically reorganized by the Database Administrator (DBA) to reclaim the unused space of deleted records.

Heap files are one of the best organizations for bulk loading data into a table, as records are inserted at the end of the sequence; there is no overhead of calculating what page the record should go on.

Pros of Heap storage

Heap is a good storage structure in the following situations:

When data is being bulk-loaded into the relation.

The relation is only a few pages long. In this case, the time to locate any tuple is Short, even if the entire relation has been searched serially.

When every tuple in the relation has to be retrieved (in any order) every time the relation is accessed. For example, retrieve the name of all the students.

Cons of Heap storage

Heap files are inappropriate when only selected tuples of a relation are to be accessed.

Hash File Organization

In a hash file, records are not stored sequentially in a file instead a hash function is used to calculate the address of the page in which the record is to be stored.

The field on which hash function is calculated is called as Hash field and if that field acts as the key of the relation then it is called as Hash key. Records are randomly distributed in the file so it is also called as Random or Direct files. Commonly some arithmetic function is applied to the hash field so that records will be evenly distributed throughout the file.

Pros of Hash file organization

Hash is a good storage structure in the following situations:

When tuples are retrieve based on an exact match on the hash field value, particularly if the access order is random. For example, if the STUDENT relation is hashed on Name then retrieval of the tuple with Name equal to “Rahat Bhatia” is efficient.

Cons of Hash file organization

Hash is not a good storage structure in the following situations:

When tuples are retrieved based on a range of values for the hash field. For example, retrieve all students whose name begins with the “R”.

When tuples are retrieved based on a range of values for the hash field. For example, if STUDENT relation has hash filed Roll Number and the query is to retrieve all students with roll numbers in the range of 3000-5000.

When tuples re retrieved based on a field other than the hash field. For example, if the STUDENT relation is hashed on Roll Number, then hashing cannot be used to search for a tuple based on the Class attribute.

When tuples are retrieved based on only part of the hash field. For example, if the STUDENT relation is hashed on Roll Number and Class, then hashing cannot be used to search for a tuple based on the class attribute alone.

When the hash field frequently updated. When a hash field updated, the DBMS must deleted the entire tuple and possible relocate it to a new address (if the has function results in a new address). Thus, frequent updating of the hash field impacts performance.

File Access Mechanism

The allocation methods define how the files are stored in the disk blocks. There are three main disk space or file allocation methods.

• Contiguous Allocation
• Linked Allocation
• 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:

1. Contiguous Allocation

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.

The file ‘mail’ in the following figure starts from the block 19 with length = 6 blocks. Therefore, it occupies 19, 20, 21, 22, 23, 24 blocks.

Figure - Contiguous allocation of disk space.

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.

2. Linked List Allocation

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.

Figure - Linked allocation of disk space.

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

3. Indexed Allocation

In this scheme, a special block known as the Index block contains the pointers to all the blocks occupied by a file. Each file has its own index block. The ith entry in the index block contains the disk address of the ith file block. The directory entry contains the address of the index block as shown in the image:

Figure - Indexed allocation of disk space.

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.

For files that are very large, single index block may not be able to hold all the pointers.

Following mechanisms can be used to resolve this:

1. Linked scheme: This scheme links two or more index blocks together for holding the pointers. Every index block would then contain a pointer or the address to the next index block.
2. Multilevel index: In this policy, a first level index block is used to point to the second level index blocks which inturn points to the disk blocks occupied by the file. This can be extended to 3 or more levels depending on the maximum file size.
3. Combined Scheme: In this scheme, a special block called the Inode (information Node) contains all the information about the file such as the name, size, authority, etc and the remaining space of Inode is used to store the Disk Block addresses which contain the actual file as shown in the image below. The first few of these pointers in Inode point to the direct blocks i.e the pointers contain the addresses of the disk blocks that contain data of the file. The next few pointers point to indirect blocks. Indirect blocks may be single indirect, double indirect or triple indirect. Single Indirect block is the disk block that does not contain the file data but the disk address of the blocks that contain the file data. Similarly, double indirect blocks do not contain the file data but the disk address of the blocks that contain the address of the blocks containing the file data.

Figure - The UNIX inode.

File Directories

A directory is a container that is used to contain folders and files. It organizes files and folders in a hierarchical manner. 

There are several logical structures of a directory, these are given below.  

• Single-level directory – 
  The single-level directory is the simplest directory structure. In it, all files are contained in the same directory which makes it easy to support and understand. 

  A single level directory has a significant limitation, however, when the number of files increases or when the system has more than one user. Since all the files are in the same directory, they must have a unique name. if two users call their dataset test, then the unique name rule violated. 

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 not have the same name. 
• Searching will become time taking if the directory is large. 
• This can not group the same type of files together. 

• Two-level directory – 
  As we have seen, a single level directory often leads to confusion of files names among different users. the solution to this problem is to create a separate directory for each user. 

  In the two-level directory structure, each user has their own user files directory (UFD). The UFDs have similar structures, but each lists only the files of a single user. system’s master file directory (MFD) is searches whenever a new user id=s logged in. The MFD is indexed by username or account number, and each entry points to the UFD for that user. 

Advantages: 

• We can give full path like /User-name/directory-name/. 
• Different users can have the same directory as well as the file name. 
• Searching of files becomes easier due to pathname and user-grouping. 

Disadvantages:

• A user is not allowed to share files with other users. 
• Still, it not very scalable, two files of the same type cannot be grouped together in the same user. 
   
• Tree-structured directory – 
  Once we have seen a two-level directory as a tree of height 2, the natural generalization is to extend the directory structure to a tree of arbitrary height. 
  This generalization allows the user to create their own subdirectories and to organize their files accordingly. 

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. 

Advantages: 

• Very general, since full pathname can be given. 
• Very scalable, the probability of name collision is less. 
• Searching becomes very easy, we can use both absolute paths as well as relative.

Disadvantages: 

• Every file does not fit into the hierarchical model, files may be saved into multiple directories. 
• We can not share files. 
• It is inefficient, because accessing a file may go under multiple directories. 
   
• Acyclic graph directory – 
  An acyclic graph is a graph with no cycle and allows us to share subdirectories and files. The same file or subdirectories may be in two different directories. It is a natural generalization of the tree-structured directory. 

  It is used in the situation like when two programmers are working on a joint project and they need to access files. The associated files are stored in a subdirectory, separating them from other projects and files of other programmers since they are working on a joint project so they want the subdirectories to be into their own directories. The common subdirectories should be shared. So here we use Acyclic directories. 

  It is the point to note that the shared file is not the same as the copy file. If any programmer makes some changes in the subdirectory it will reflect in both subdirectories. 

Advantages: 

• We can share files. 
• Searching is easy due to different-different paths. 

Disadvantages:

• We share the files via linking, in case deleting it may create the problem, 
• If the link is a soft link then after deleting the file we left with a dangling pointer. 
• In the case of a hard link, to delete a file we have to delete all the references associated with it. 
   
• General graph directory structure – 
  In general graph directory structure, cycles are allowed within a directory structure where multiple directories can be derived from more than one parent directory. 
  The main problem with this kind of directory structure is to calculate the total size or space that has been taken by the files and directories. 
   

Advantages: 

• It allows cycles. 
• It is more flexible than other directories structure. 

Disadvantages:

• It is more costly than others. 
• It needs garbage collection. 

File sharing

File sharing is the practice of sharing or offering access to digital information or resources, including documents, multimedia (audio/video), graphics, computer programs, images and e-books. It is the private or public distribution of data or resources in a network with different levels of sharing privileges.

File sharing can be done using several methods. The most common techniques for file storage, distribution and transmission include the following:

• Removable storage devices
• Centralized file hosting server installations on networks
• World Wide Web-oriented hyperlinked documents
• Distributed peer-to-peer networks

File sharing is a multipurpose computer service feature that evolved from removable media via network protocols, such as File Transfer Protocol (FTP). Beginning in the 1990s, many remote file-sharing mechanisms were introduced, including FTP, hotline and Internet relay chat (IRC).

Operating systems also provide file-sharing methods, such as network file sharing (NFS). Most file-sharing tasks use two basic sets of network criteria, as follows:

• Peer-to-Peer (P2P) File Sharing: This is the most popular, but controversial, method of file sharing because of the use of peer-to-peer software. Network computer users locate shared data with third-party software. P2P file sharing allows users to directly access, download and edit files. Some third-party software facilitates P2P sharing by collecting and segmenting large files into smaller pieces.
• File Hosting Services: This P2P file-sharing alternative provides a broad selection of popular online material. These services are quite often used with Internet collaboration methods, including email, blogs, forums, or other mediums, where direct download links from the file hosting services can be included. These service websites usually host files to enable users to download them.

Once users download or make use of a file using a file-sharing network, their computer also becomes a part of that network, allowing other users to download files from the user's computer. File sharing is generally illegal, with the exception of sharing material that is not copyrighted or proprietary. Another issue with file-sharing applications is the problem of spyware or adware, as some file-sharing websites have placed spyware programs in their websites. These spyware programs are often installed on users' computers without their consent and awareness.

File System Implementation

A file is a collection of related information. The file system resides on secondary storage and provides efficient and convenient access to the disk by allowing data to be stored, located, and retrieved.

File system organized in many layers :

• I/O Control level –
  Device drivers acts as interface between devices and Os, they help to transfer data between disk and main memory. It takes block number a input and as output it gives low level hardware specific instruction.
  /li>
• Basic file system –
  It Issues general commands to device driver to read and write physical blocks on disk.It manages the memory buffers and caches. A block in buffer can hold the contents of the disk block and cache stores frequently used file system metadata.
• File organization Module –
  It has information about files, location of files and their logical and physical blocks.Physical blocks do not match with logical numbers of logical block numbered from 0 to N. It also has a free space which tracks unallocated blocks.
• Logical file system –
  It manages metadata information about a file i.e includes all details about a file except the actual contents of file. It also maintains via file control blocks. File control block (FCB) has information about a file – owner, size, permissions, location of file contents.

Advantages :

1. Duplication of code is minimized.
2. Each file system can have its own logical file system.

Disadvantages :

If we access many files at same time then it results in low performance.

We can implement file system by using two types data structures :

1. On-disk Structures –
Generally they contain information about total number of disk blocks, free disk blocks, location of them and etc. Below given are different on-disk structures :
1. Boot Control Block –
   It is usually the first block of volume and it contains information needed to boot an operating system.In UNIX it is called boot block and in NTFS it is called as partition boot sector.
2. Volume Control Block –
   It has information about a particular partition ex:- free block count, block size and block pointers etc.In UNIX it is called super block and in NTFS it is stored in master file table.
3. Directory Structure –
   They store file names and associated inode numbers.In UNIX, includes file names and associated file names and in NTFS, it is stored in master file table.
4. Per-File FCB –
   It contains details about files and it has a unique identifier number to allow association with directory entry. In NTFS it is stored in master file table.



2. In-Memory Structure :
They are maintained in main-memory and these are helpful for file system management for caching. Several in-memory structures given below :
1. Mount Table –
   It contains information about each mounted volume.
2. Directory-Structure cache –
   This cache holds the directory information of recently accessed directories.
3. System wide open-file table –
   It contains the copy of FCB of each open file.
4. Per-process open-file table –
   It contains information opened by that particular process and it maps with appropriate system wide open-file.

Directory Implementation :

1. Linear List –
   It maintains a linear list of filenames with pointers to the data blocks.It is time-consuming also.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 file at end of the directory.To delete a file, we search the directory for the named file and release the space.To reuse the directory entry either we can mark the entry as unused or we can attach it to a list of free directories.
2. Hash Table –
   The hash table takes a value computed from the file name and returns a pointer to the file. It decreases the directory search time. The insertion and deletion process of files is easy. The major difficulty is hash tables are its generally fixed size and hash tables are dependent on hash function on that size.

File 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.

• Contiguous Allocation
• Linked Allocation
• 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:

1. Contiguous Allocation

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.

The file ‘mail’ in the following figure starts from the block 19 with length = 6 blocks. Therefore, it occupies 19, 20, 21, 22, 23, 24 blocks.

Figure - Contiguous allocation of disk space.

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.

2. Linked List Allocation

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.

Figure - Linked allocation of disk space.

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

3. Indexed Allocation

In this scheme, a special block known as the Index block contains the pointers to all the blocks occupied by a file. Each file has its own index block. The ith entry in the index block contains the disk address of the ith file block. The directory entry contains the address of the index block as shown in the image:

Figure - Indexed allocation of disk space.

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.

For files that are very large, single index block may not be able to hold all the pointers.

Following mechanisms can be used to resolve this:

1. Linked scheme: This scheme links two or more index blocks together for holding the pointers. Every index block would then contain a pointer or the address to the next index block.
2. Multilevel index: In this policy, a first level index block is used to point to the second level index blocks which inturn points to the disk blocks occupied by the file. This can be extended to 3 or more levels depending on the maximum file size.
3. Combined Scheme: In this scheme, a special block called the Inode (information Node) contains all the information about the file such as the name, size, authority, etc and the remaining space of Inode is used to store the Disk Block addresses which contain the actual file as shown in the image below. The first few of these pointers in Inode point to the direct blocks i.e the pointers contain the addresses of the disk blocks that contain data of the file. The next few pointers point to indirect blocks. Indirect blocks may be single indirect, double indirect or triple indirect. Single Indirect block is the disk block that does not contain the file data but the disk address of the blocks that contain the file data. Similarly, double indirect blocks do not contain the file data but the disk address of the blocks that contain the address of the blocks containing the file data.

Figure - The UNIX inode.

Protection in File System

In computer systems, alot of user’s information is stored, the objective of the operating system is to keep safe the data of the user from the improper access to the system. Protection can be provided in number of ways. For a single laptop system, we might provide protection by locking the computer in a desk drawer or file cabinet. For multi-user systems, different mechanisms are used for the protection.

Types of Access :

The files which have direct access of the any user have the need of protection. The files which are not accessible to other users doesn’t require any kind of protection. The mechanism of the protection provide the facility of the controlled access by just limiting the types of access to the file. Access can be given or not given to any user depends on several factors, one of which is the type of access required. Several different types of operations can be controlled:

• Read –
  Reading from a file.
• Write –
  Writing or rewriting the file.
• Execute –
  Loading the file and after loading the execution process starts.
• Append –
  Writing the new information to the already existing file, editing must be end at the end of the existing file.
• Delete –
  Deleting the file which is of no use and using its space for the another data.
• List –
  List the name and attributes of the file.

Operations like renaming, editing the existing file, copying; these can also be controlled. There are many protection mechanism. each of them mechanism have different advantages and disadvantages and must be appropriate for the intended application.

Access Control :

There are different methods used by different users to access any file. The general way of protection is to associate identity-dependent access with all the files and directories an list called access-control list (ACL) which specify the names of the users and the types of access associate with each of the user. The main problem with the access list is their length. If we want to allow everyone to read a file, we must list all the users with the read access. This technique has two undesirable consequences:

Constructing such a list may be tedious and unrewarding task, especially if we do not know in advance the list of the users in the system.

Previously, the entry of the any directory is of the fixed size but now it changes to the variable size which results in the complicates 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 classification of users in connection with each file:

• Owner –
  Owner is the user who has created the file.
• Group –
  A group is a set of members who has similar needs and they are sharing the same file.
• Universe –
  In the system, all other users are under the category called universe.

The most common recent approach is to combine access-control lists with the normal general owner, group, and universe access control scheme. For example: Solaris uses the three categories of access by default but allows access-control lists to be added to specific files and directories when more fine-grained access control is desired.

Other Protection Approaches:

The access to any system is also controlled by the password. If the use of password are is random and it is changed often, this may be result in limit the effective access to a file.

The use of passwords has a few disadvantages:

• The number of passwords are very large so it is difficult to remember the large passwords.
• If one password is used for all the files, then once it is discovered, all files are accessible; protection is on all-or-none basis.