System): As we know, a process needs two type of time, CPU time and IO time. For I/O, it requests the Operating system to access the disk.
However, the operating system must be fare enough to satisfy each request and at the same time, operating system must maintain the efficiency and speed of process execution.
The technique that operating system uses to determine the request which is to be satisfied next is called disk scheduling.
Let's discuss some important terms related to disk scheduling.
Seek Time
Seek time is the time taken in locating the disk arm to a specified track where the read/write request will be satisfied.
Rotational Latency
It is the time taken by the desired sector to rotate itself to the position from where it can access the R/W heads.
Transfer Time
It is the time taken to transfer the data.
Disk Access Time
Disk access time is given as,
Disk Access Time = Rotational Latency + Seek Time + Transfer Time
Disk Response Time
It is the average of time spent by each request waiting for the IO operation. Purpose of Disk Scheduling
The main purpose of disk scheduling algorithm is to select a disk request from the queue of IO requests and decide the schedule when this request will be processed.
Disk Scheduling Algorithms
The list of various disks scheduling algorithm is given below. Each algorithm is carrying some advantages and disadvantages. The limitation of each algorithm leads to the evolution of a new algorithm.
o FCFS scheduling algorithm
o SSTF (shortest seek time first) algorithm o SCAN scheduling o C-SCAN scheduling o LOOK Scheduling o C-LOOK scheduling
FCFS Scheduling Algorithm
It is the simplest Disk Scheduling algorithm. It services the IO requests in the order in which they arrive. There is no starvation in this algorithm, every request is serviced.
Disadvantages o The scheme does not optimize the seek time. o The request may come from different processes therefore there is the possibility of inappropriate movement of the head.
Example
Consider the following disk request sequence for a disk with 100 tracks 45, 21, 67, 90, 4, 50, 89, 52, 61, 87, 25
Head pointer starting at 50 and moving in left direction. Find the number of head movements in cylinders using FCFS scheduling. Solution
Shortest seek time first (SSTF) algorithm selects the disk I/O request which requires the least disk arm movement from its current position regardless of the direction. It reduces the total seek time as compared to FCFS.
It allows the head to move to the closest track in the service queue.
Disadvantages o It may cause starvation for some requests. o Switching direction on the frequent basis slows the working of algorithm. o It is not the most optimal algorithm.
Example
Consider the following disk request sequence for a disk with 100 tracks
45, 21, 67, 90, 4, 89, 52, 61, 87, 25
Head pointer starting at 50. Find the number of head movements in cylinders using SSTF scheduling. Solution:
It is also called as Elevator Algorithm. In this algorithm, the disk arm moves into a particular direction till the end, satisfying all the requests coming in its path,and then it turns backand moves in the reverse direction satisfying requests coming in its path.
It works in the way an elevator works, elevator moves in a direction completely till the last floor of that direction and then turns back.
Example
Consider the following disk request sequence for a disk with 100 tracks
98, 137, 122, 183, 14, 133, 65, 78
Head pointer starting at 54 and moving in left direction. Find the number of head movements in cylinders using SCAN scheduling.
In C-SCAN algorithm, the arm of the disk moves in a particular direction servicing requests until it reaches the last cylinder, then it jumps to the last cylinder of the opposite direction without servicing any request then it turns back and start moving in that direction servicing the remaining requests.
Example
Consider the following disk request sequence for a disk with 100 tracks
98, 137, 122, 183, 14, 133, 65, 78
Head pointer starting at 54 and moving in left direction. Find the number of head movements in cylinders using C-SCAN scheduling. No. of cylinders crossed = 40 + 14 + 199 + 16 + 46 + 4 + 11 + 24 + 20 + 13 = 387
Look Scheduling
It is like SCAN scheduling Algorithm to some extant except the difference that, in this scheduling algorithm, the arm of the disk stops moving inwards (or outwards) when no more request in that direction exists. This algorithm tries to overcome the overhead of SCAN algorithm which forces disk arm to move in one direction till the end regardless of knowing if any request exists in the direction or not.
Example
Consider the following disk request sequence for a disk with 100 tracks
98, 137, 122, 183, 14, 133, 65, 78
Head pointer starting at 54 and moving in left direction. Find the number of head movements in cylinders using LOOK scheduling. Number of cylinders crossed = 40 + 51 + 13 + +20 + 24 + 11 + 4 + 46 = 209
C Look Scheduling
C Look Algorithm is similar to C-SCAN algorithm to some extent. In this algorithm, the arm of the disk moves outwards servicing requests until it reaches the highest request cylinder, then it jumps to the lowest request cylinder without servicing any request then it again start moving outwards servicing the remaining requests.
It is different from C SCAN algorithm in the sense that, C SCAN force the disk arm to move till the last cylinder regardless of knowing whether any request is to be serviced on that cylinder or not.
Example
Consider the following disk request sequence for a disk with 100 tracks
98, 137, 122, 183, 14, 133, 65, 78
Head pointer starting at 54 and moving in left direction. Find the number of head movements in cylinders using C LOOK scheduling. Number of cylinders crossed = 11 + 13 + 20 + 24 + 11 + 4 + 46 + 169 = 298
2. File system implementation:
File system implementation in an operating system involves several key components and processes that manage how data is stored, organized, accessed, and secured on storage devices such as hard drives, SSDs, and other storage media. Here’s a structured explanation of the key aspects involved:
1. File System Structure:
o Files: Basic units for storing data. Files can range from simple text documents to complex multimedia files. o Directories (Folders): Containers for organizing files hierarchically. Directories can contain both files and other directories. 2. File Allocation Methods: o Contiguous Allocation: Allocates contiguous blocks of disk space to each file. Simple to implement but leads to fragmentation over time. o Linked Allocation: Each file is a linked list of disk blocks. No external fragmentation, but traversal can be slow. o Indexed Allocation: Uses an index block that contains pointers to all blocks of a file. Faster access than linked allocation but requires additional space for the index. 3. Directory Implementation: o Directories are managed through special files known as directory files. o A directory file contains records that map file names to their corresponding inode (Index Node) numbers or file control blocks (FCBs). 4. File Operations: o File Creation: Involves allocating space and setting up metadata like file attributes and permissions. o File Reading and Writing: Involves accessing and modifying file content, often mediated by the file system's buffer cache for efficiency. o File Deletion: Involves reclaiming allocated space and updating directory structures. 5. File System Metadata: o Inodes (Index Nodes): Metadata structures that store information about each file, including file type, permissions, owner, size, timestamps, and pointers to data blocks. o Superblock: Contains metadata about the file system itself, such as total number of blocks, free blocks, and block size. 6. File System Consistency and Reliability: o Journaling: Technique to ensure file system consistency by logging changes before they are committed to the file system structures. o Checkpoints: Periodic snapshots of file system state to aid recovery in case of system crashes or power failures. o Data Integrity: Mechanisms to detect and correct errors in stored data, such as checksums and redundancy. 7. Access Control and Security: o File systems enforce access control policies to restrict which users or processes can read, write, or execute files. o Security features like encryption can be implemented at the file system level to protect data confidentiality. 8. File System Mounting and Unmounting: o Mounting: Attaching a file system to a directory in the OS's namespace, making its contents accessible. o Unmounting: Detaching a file system safely from the directory, ensuring all pending operations are completed and resources are released. 9. File System Types: o Various file system types exist, each optimized for different purposes (e.g., NTFS, FAT32, ext4, APFS). Each type has its own data structures and algorithms for storage management. 3. File Allocation Methods:
There are various methods which can be used to allocate disk space to the files. Selection of an appropriate allocation method will significantly affect the performance and efficiency of the system. Allocation method provides a way in which the disk will be utilized and the files will be accessed.
There are following methods which can be used for allocation.
We will discuss three of the most used methods in detail.
Contiguous Allocation:
If the blocks are allocated to the file in such a way that all the logical blocks of the file get the contiguous physical block in the hard disk then such allocation scheme is known as contiguous allocation.
In the image shown below, there are three files in the directory. The starting block and the length of each file are mentioned in the table. We can check in the table that the contiguous blocks are assigned to each file as per its need. Linked List Allocation:
Linked List allocation solves all problems of contiguous allocation. In linked list allocation, each file is considered as the linked list of disk blocks. However, the disks blocks allocated to a particular file need not to be contiguous on the disk. Each disk block allocated to a file contains a pointer which points to the next disk block allocated to the same file.
File Allocation Table:
The main disadvantage of linked list allocation is that the Random access to a particular block is not provided. In order to access a block, we need to access all its previous blocks.
File Allocation Table overcomes this drawback of linked list allocation. In this scheme, a file allocation table is maintained, which gathers all the disk block links. The table has one entry for each disk block and is indexed by block number. File allocation table needs to be cached in order to reduce the number of head seeks. Now the head doesn't need to traverse all the disk blocks in order to access one successive block.
It simply accesses the file allocation table, read the desired block entry from there and access that block. This is the way by which the random access is accomplished by using FAT. It is used by MS-DOS and pre-NT Windows versions.
Indexed Allocation:
Instead of maintaining a file allocation table of all the disk pointers, Indexed allocation scheme stores all the disk pointers in one of the blocks called as indexed block. Indexed block doesn't hold the file data, but it holds the pointers to all the disk blocks allocated to that particular file. Directory entry will only contain the index block address. Linked Index Allocation:
Single level linked Index Allocation:
In index allocation, the file size depends on the size of a disk block. To allow large files, we have to link several index blocks together. In linked index allocation,
o Small header giving the name of the file
o Set of the first 100 block addresses o Pointer to another index block
For the larger files, the last entry of the index block is a pointer which points to another index block. This is also called as linked schema. Multilevel Index Allocation:
In Multilevel index allocation, we have various levels of indices. There are outer level index blocks which contain the pointers to the inner level index blocks and the inner level index blocks contain the pointers to the file data.
o The outer level index is used to find the inner level index. o The inner level index is used to find the desired data block.
Inode:
In UNIX based operating systems, each file is indexed by an Inode. Inode are the special disk block which is created with the creation of the file system. The number of files or directories in a file system depends on the number of Inodes in the file system. 4. Swap-Space Management: Swap-space management is another low-level task of the operating system. Virtual memory uses disk space as an extension of main memory. Since disk access is much slower than memory access, using swap space significantly decreases system performance. The main goal for the design and implementation of swap space is to provide the best throughput for the virtual memory system.
Swap space is used in various ways by different operating systems, depending on the memory-management algorithms in use. For example, systems that implement swapping may use swap space to hold an entire process image, including the code and data segments. Paging systems may simply store pages that have been pushed out of the main memory. The amount of swap space needed on a system can vary depending on the amount of physical memory, the amount of virtual memory it is backing, and how it is used. It can range from a few megabytes of disk space to gigabytes.
Uses of Swap Space
The different operating system uses Swap-space in various ways. The systems that are implementing swapping may use swap space to hold the entire process, including image, code, and data segments.
o Swapping is a memory management technique used in multi-programming to
increase the number of processes sharing the CPU. It is a technique of removing a process from the main memory, storing it into secondary memory, and then bringing it back into the main memory for continued execution. This action of moving a process out from main memory to secondary memory is called Swap Out. The action of moving a process out from secondary memory to main memory is called Swap In. o Paging systems may simply store pages that have been pushed out of the main memory. The need for swap space on a system can vary from megabytes to gigabytes. Still, it also depends on the amount of physical memory, the virtual memory it is backing, and how it uses the virtual memory.
Where does the Swap Space Reside?
Swap space can reside in one of these two places: The normal file system or Separate disk partition.
o External fragmentation can greatly increase swapping times by forcing multiple
seeks during the reading or writing of a process image. We can improve performance by caching the block location information in physical memory and by using special tools to allocate physically contiguous blocks for the swap file. However, the cost of traversing the file-system data structures still remains. o Alternatively, swap space can be created in a separate raw partition, as no file system or directory structure is placed in this space. Rather, a separate swap-space storage manager is used to allocate and deallocate the blocks from the raw partition. This manager uses algorithms optimized for speed rather than storage efficiency because swap space is accessed more frequently than file systems. o Internal fragmentation may increase, but this trade-off is acceptable because the life of data in the swap space generally is much shorter than that of files in the file system. Swap space is reinitialized at boot time, so any fragmentation is short-lived. This approach creates a fixed amount of swap space during disk partitioning. Adding more swap space requires repartitioning the disk or adding another swap space elsewhere.
