Optimized Universal Disk Scheduling Algorithm

Abstract

For efficient and faster working of computer, researchers tries to optimize different scheduling algorithms of operating system. Along with modernization of computer, the speed of hardware (like processor, RAM, and hard disk) gradually increases. But till now processor works in nanoseconds per instruction execution, where as hard disk works in microseconds per memory access. During execution, process needs both CPU bound and I/O bound time. The slowness of hard disk may detain the speed of processor, as due to its sluggishness it is unable to provide the needed data on time. For high-performance computing, the disk scheduling algorithms also need to be optimized along with optimization of CPU scheduling. The proposed scheduling algorithm improves the performance measure of the disk scheduling algorithm by reducing the seek time, the rotational latency, and the platter selection time. Proposed algorithm decreases the space complexity of the kernel as it is able to deal with different situation like difference in partition table, file system, number of hard disk, and RAID technology. The proposed algorithm also able to detect and manage physical bit bad sector of the hard disk.

Introduction

Operating system is a highly advanced integrated programming which provides system management services like process management, device management, file management, etc., by managing all hardware and software resources. Operating system uses different scheduling algorithms [1,2,3] like CPU scheduling, disk scheduling, page replacement for proper management of varieties of tasks and efficient utilization of resources. CPU scheduling is the mechanism of task arrangement and resource utilization for faster execution of processes by fulfilling all requirements. For high-performance computing, researchers endeavor to increase the performance measure of process scheduling. Dash et al. [4] have proposed a concept of dynamic time quantum, generated by mean of all processes burst time. They proposed an optimized CPU scheduling algorithm entitled “DABRR” which optimized the waiting time and turned around time up to 41.23% and 30.70%, respectively. They further progress their research work by integrating and optimizing the concept of priority scheduling in the DABRR algorithm. They proposed an algorithm entitled “CSPDABRR” [5], which integrates 7 specific priority features for each process. CSPDABRR executes the processes based on their priority. In every cycle, it calculates the mean time of all process for finding the value of dynamic time quantum.

The speed of all computer hardware gradually increases, but till now the processor works in nanosecond per execution, whereas hard disk works in microsecond per memory access. So hard disk works million time slower than the processor. Every process need both CPU bound and I/O bound time for completion of its execution. In multiprocessing environment, multiple programs run parallelly at a time, which leads to generation of multiple read or write memory requests. If the hard disk is unable to provide the required data on time, due to its sluggish nature, then the slowness of the hard disk may detain the speed of processor. So for High performance computing disk scheduling algorithm also need to be optimized. Disk scheduling is the process of arrangement of all memory request based on track number for quicker completion.

Literature Review

Hard disk is a secondary storage device made up of platters, actuators, and two motors. The read/write head (present at the end of actuator arm) used to read the data from the magnetic layer, generated during the rotation of the platter. Platters are circular ceramic plates (made up of Fe₂O₃), stacked over the spindle. Tracks are concentric circles present on lower and upper surface of platter. These tracks are further subdivided into multiple partitions called sectors, each holding a fixed amount of data (512 Bytes in MBR and 4096 Bytes in GPT) represented as magnetized bit patterns. A combination of track, sector, and platter number used as an index to access the data from hard disk. Disk scheduling is the process of arrangement of all memory requests based on their memory index (combination of track, sector, and platter number) for quicker completion.

The disk scheduling algorithm’s performance measured in terms of disk response time (which is the combination of seek time, rotational latency, platter selection time, and data transfer time, etc.). Seek time is the amount of time taken by actuator for moving to track of requested information. Rotational latency is the time consumed by the read/write head to reach a particular sector, by rotation of platter. The disk should be efficient enough to serve all memory requests generated from multiple simultaneously executing processes. Achieving this efficiency involves implementing traditional disk scheduling algorithms like FCFS, SSTF, SCAN, CSCAN, LOOK, and C-LOOK, as documented in [1,2,3]. Mallikarjuna and Babu [6] have conducted a performance measure based comparative analysis of traditional disk scheduling algorithms. Similarly, Pokharel [7] and Gaur et al. [8] performed a survey to compare the performance of traditional algorithms, with derived algorithms like ODSA, HDSA, SMCC, NHA, etc. Suranauwarat [9] has created a C# program for simulating disk scheduling algorithms with their statistics.

Among the traditional disk scheduling algorithms, FCFS is the simplest but incurs more seek time than others. Mishra [10] introduced a new algorithm, IFCFS, which prioritizes completing memory requests along the initial head position’s path toward the first memory request before moving in the reverse direction. However, IFCFS struggles to optimize seek time when the first memory request is not located at either end. Seltzer et al. [11] proposed GSTF (grouped shortest time first) and WSTF (weighted shortest time first) mechanisms to enhance disk scheduling algorithm performance. LOOK stands out as the best disk scheduling algorithm in terms of seek time, motivating researchers to optimize it further by reducing seek time. Pandey et al. [12] introduced a zone-based disk algorithm that classifies memory requests into lower and higher zones based on their track’s relationship to the initial head position’s track. Then they implement the LOOK algorithm, beginning with the zone having a higher memory request density.

Rasool and Gakher [13] developed an algorithm that calculates the difference between the highest and lowest request values and compares it with the current head position, subsequently implementing the LOOK algorithm to serve memory requests. Bhoi et al. [14] and Saha et al. [15] devised similar disk scheduling algorithms, arranging requests in ascending order and determining head movement direction based on the left and right distances from the current head position. Kumar and Rajendra [16] introduced the Sort Mid-Current Comparison (SMCC) algorithm to reduce seek time. This algorithm arranges requests in ascending order, calculates the midpoint, and decides head movement based on the comparison between the midpoint and the current head position, then implements LOOK to serve memory requests. Vachhani and Turakhia [17] proposed the median range disk scheduling algorithm, which finds the median range after organizing memory requests in ascending order. Then compares the current head position to the median range and applies SSTF (if the head is positioned within the median range) or LOOK (if the head is positioned outside the median range) accordingly. Mahesh Kumar [18] Proposed a binary search tree-based disk scheduling algorithm. Their proposed algorithm arrange the memory request based on their track (using the binary search tree) before implementing the LOOK disk scheduling algorithm. Mittal [19] developed a simulator incorporating the Box-Muller transformation and concluded that none of the traditional algorithms are better in all situations.

Some researchers focus on reducing rotational latency to optimize disk scheduling algorithms. Jacobson and Wilkes [20] conducted a comparative and simulative analysis of seek time-based and rotational latency-based disk scheduling algorithms for HP hard disk. Hooda and Raheja [21] devised an algorithm to reduce rotational latency through fuzzy logic. Hwang and Shin [22] proposed SRLF and SATF disk scheduling algorithms to decrease rotational latency and access time, respectively. Singh et al. [23] introduced OTHDSA (Optimized Two-Headed Disk Scheduling Algorithm), designed for hard disks with two read/write heads on each side of the platter. It works based on the Left and Right head movements in relation to the memory request positions. Similarly, Shankar et al. [24] developed a disk scheduling algorithm for hard disks with three heads on each side of the platter. Thomasian [25] compares the execution of STF and SPTF with all traditional scheduling algorithms. Dash et al. [26] proposed “Modern Optimized Disk Scheduling Algorithm” capable of optimizing both seek time and rotational latency while handling bad sectors. Jiang and Yu [27] analyzed the integration of RAID concepts with disk scheduling for multi-hard disk systems.

Researchers also assess energy consumption and heat generation in hard disks. Hylick et al. [28] have analyzed different hard disk’s energy consumption based on the type of hardware, type of memory access, and data-chunk’s position and size. Jiang [29] observed that energy consumed per accessing one bit is approximately 100 fj in hard disk and 0.35 fj in solid-state drive.

The remainder of this paper is structured as follows: Sect. 3 illustrates all traditional disk scheduling algorithms along with the drawback in their working style. Section 4 describes the proposal for the optimization. Section 6 explains the working of the proposed algorithm present in Sect. 5. Section 7.1 represents the assumptions made before the execution of proposed algorithm. Section 7.2 illustrates the complexity of the proposed algorithm. Section 7.3 to 7.8 represents a comparative analysis of the proposed algorithm with six traditional and eight derived algorithms in six use case. Section 8 represent all advantage of the proposed algorithm. Finally, Sect. 9 provides the concluding remarks and aspects of more improvement in the future work.

Traditional Algorithm

In the era of high performance computing, a lot of research work going on upon the CPU scheduling, for speeding up the system. During proper execution of a program, three most necessary things are process, processor, and resource. Anything that is needed during the execution of the program (except the processor and process itself) is called as resource. Along with task management, resource scheduling is also an important aspect of the CPU scheduling.

Primary memories like RAM, Cache, and others are hardware resources used for the temporary storage of data under processing. Secondary memories like HDD and SSD are the hardware resources used for the permanent storage of data for longer period. But hard disk is far slower than CPU, As CPU works in nanosecond, and hard disk works in microsecond. So the slowness of the hard disk may detain the speed of processor if it is unable to provide the needed data on time.

In multiprogramming environment, multiple process can execute parallelly at a time. Around 70% of the requested data will be available either in cache or in RAM. But for other data, memory read and write request will be generated for hard disk. Hard disk stores the data on platter in magnetic bit format and the actuator can access one bit data at a time. When a large number of hard disk memory requests generated they are store in the disk queue. The data to be access may be present in different address (combination of Track, sector, and platter). Disk scheduling algorithm tries to reduce the disk access time (DAT) per memory request by rearranging all memory request of the disk queue (based on the address of the memory request) for faster access.

Six traditional algorithms are there to enhance the performance of a hard disk, that we can follow to escalate computers work. FCFS is the least complex algorithm. This algorithm will address all memory request in ascending order of their arrival time. The main drawback of this algorithm is, here the memory requests are not arranged. So actuators have to take large swings if the requests are far from each other which increases the seek time. SSTF (shortest seek time first) algorithm will access the memory request, which will cost the least seek time from the current head position. For better performance, this algorithm calculates the seek time of each request in the disk queue and sort them based on their seek time, before approaching the next nearest request. The main difficulty with this algorithm is an extra expense is there for calculating the seek time for finding out the closest request, and it can also cause starvation for some request which are far from the current position.

SCAN algorithm (elevator algorithm) begins from current position and proceed toward a direction till the last track of the platter (with addressing all the request in between). Then the actuator moves in the reverse direction to access the remaining request. The main issue with this algorithm is the request has to wait until the disk arm comes and the disk arm has to travel to the end even if there is no request from a certain distance to address. C-SCAN (Circular SCAN) begins from current actuator position of the disk and move toward a direction till the last track of the platter (with addressing all the request in between). Then, move in the reverse direction till last track of the platter, without servicing any request. Then, again actuator will move in the reverse direction with accessing the request.

LOOK is almost similar to SCAN but the difference is, in LOOK algorithm the actuator head begins from current position and proceed toward a direction till the last memory request in that direction, with addressing all the request in between. Then the process continues in the reverse direction. C-LOOK (Circular LOOK) algorithm is a combination of both C-SCAN and LOOK algorithms. In this algorithm, the disk head begins from current position and proceed toward a direction till the last memory request in that direction, with addressing all the request in between. Then, the actuator moves in reverse direction till last memory request in that direction, without servicing any request. Then, again reverse the direction of actuator and start servicing the memory request.

Loop Holes

In recent times, most of the hard disks are made up of multi platter. Traditional algorithms focus on the seek time only. Some derived algorithm tries to optimize the rotational latency. But they did not focus on minimizing all subsections of disk access time (DAT). Traditionally, different drivers are used for different type of hard disk and RAID technologies. So gradually the size of kernel increase, as the operating system needs to contain disk drivers and scheduling algorithm for different type of hard disk. Traditional disk scheduling algorithms also not capable of solving the problems of bad sector in hard disk.

Our Proposal

Figure 1 represents the top and side view of the platter and actuator arms arrangement in hard disk. Hard disk is a magnetic disk which contains two motors. Actuator motor used for the movement of actuator. Read/write head, placed at the end of the actuator, used for accessing the data from the virtual magnetic layer of the platter. Spindle motor used for circular movement of multiple platters of same radius. Platters are circular ceramic plates (made up of Fe₂O₃), coated with a shallow layer of diamagnetic material typically 10–20 nm in depth over the both surface of the platter. Platter’s surface also contains an outer layer of carbon for protection of magnetic material. Platters physically divided into multiple concentric circles, named as track. Cylinder is a virtual index imagined by considering the track of same number present in different platters. Further each track virtually subdivided into sectors. Sectors are smallest block of fixed size. Size of sector in hard disk is 512 and 4096 Byte for MBR and GPT based hard disk, respectively. The disk scheduling algorithm use the combination of platter, track, sector index to uniquely identify each smallest block of data storage in hard disk.

The effectiveness of disk scheduling algorithm depends upon its disk response time (DRT) per memory request. Equations 1 2 3 4 indicates the calculation method for disk response time. The time taken for processing (memory conversion) of memory request is called as command processing time (CPT). The time taken for physical movement of actuator from current track to the track of next memory request is called as seek time (SkT). Time required for the settling of actuator is called as setle time (StlT). After reaching a particular track, the time taken for reaching a particular sector is called as Rotational Delay/Rotational Latency (RL). Time taken for selecting a particular actuator based on the platter and surface of the memory request is called as platter selection time (PST). The time required to read or write a single bit on platter is called as data read time (DRT). The access time (AT) is the combination of Command processing time (CPT), seek time (SkT), setle time (StlT), rotational latency (RL), platter selection time (PST), data read time (DRT). Internal data transfer time (IDTrT) is the time required for transfer of data from platter to HDD mother board, whereas external data transfer time (EDTrT) is the time required for transfer of data from HDD mother board to the system. The data transfer time (DTrT) is the combination of internal data transfer time (IDTrT) and external data transfer time (EDTrT). Similarly the disk access time (DAT) is the union of access time (AT) and data transfer time (DTrT). The disk response time (DRT) is the combination of disk access time (DAT) and disk queueing time (DQT).

Fig. 1

Top and side view of hard disk

Fig. 2

Structure of disk queue and bad sector List

Minimizing the disk response time (DRT) per each memory request is the aim of the disk scheduling algorithm. As traditional algorithms arrange the memory request based on track, for decreasing the seek time. Similarly, the memory request can further arrange based on the sector and platter for minimizing the rotational latency and platter selection time, respectively. The descending order of per unit time consumption in hard disk is seek time, rotational latency, and platter selection time. So we proposed to first arrange all memory request based on track number. Then sub-arrange the memory request (with same track) based on sector. Further sub-arrange the memory request (with same track and sector combination) based on platter. This way of memory request arrangement is far better than the previous disk queuing techniques, as it leads to better disk response time.

$$\begin{aligned} \text {DRT}= &\, {} \text {DAT} + \text {DQT} \end{aligned}$$

(1)

$$\begin{aligned} \text {DAT}= &\, {} \text {AT} + \text {DTrT} \end{aligned}$$

(2)

$$\begin{aligned} \text {AT}= &\, {} \text {CPT} + \text {SkT} + \text {StlT} + \text {RL} + \text {PST}+ \text {DRT} \end{aligned}$$

(3)

$$\begin{aligned} \text {DTrT}= &\, {} \text {IDTrT} + \text {EDTrT} \end{aligned}$$

(4)

Figure 2 shows the proposed structure of disk queue and bad sector List. Disk queue is the queue made up of double-circular-linked-list. Each node of disk queue contains the details of a memory request like type of memory request and address of memory request (with platter, track, sector number). This algorithm also proposed a mechanism to detect and manage the bit bad sector of the hard disk with the help of “Bad Sector List.” Bad sector list is the queue made up of double-circular-linked-list, which stores additional details required for the management of the Bad sector.

Processor generates the hard disk memory request with logical address. First address conversion has been done by file system from logical address to block address. The second address conversion have been done by partition table from block address to physical address. So the address conversion depends on the type of file system and partition table used by hard disk. The disk scheduling algorithm of single hard disk system is different from disk scheduling algorithm of multi hard disk system. Because the disk scheduling algorithm of multi hard disk system, also should be capable of dealing with different type of RAID (Redundant Array of Independent Disks) used in the system. Previously, different drivers are used for different type of hard disk and RAID technologies. So multiple disk drivers need to be integrated in the kernel of operating system, which unnecessarily increases the kernel size of the operating system. if one algorithm is capable of dealing with all possible situation, then it can decrease the kernel size. The proposed algorithm is capable of dealing with different type of file system, partition table, and RAID technology.

Proposed Algorithm

MPTD

Algorithm 1

MPTD(): modern partition table detector

FSH

Algorithm 2

FSH(): file system handler

MDH

Algorithm 3

MDH(MemReq, Dn): multidisk handler

Fig. 3

Flowchart of MDH

MODSBSM2.0

Fig. 4

Flowchart of MODSBSM2.0

Algorithm 4

MODSBSM2(Dn, MemReq, v): modern optimized disk scheduling with bad sector management

BSM

Algorithm 5

BSM(Index): bad sector management

Illustration

Section 5 contains the proposed algorithm. This section will analyze the execution of the proposed algorithm. The algorithm is made up of five functions. The first two functions MPTD (modern partition table detector) and FSH (file system handler) always executed once during booting of the system. Three types of partition tables are there, which used for addressing of individual sectors of hard disk, viz., MBR, GPT, and Hybrid. MPTD() function is used to detect whether the system is booted by BIOS or UEFI. Then, it tries to detect whether the partition table and addressing present on single side (on first track of 1st platter’s upper surface) or on both side (on first track of 1st platter’s upper surface and on last track of last platter’s lower surface). Based on that the function will conclude which kind of partition table have been used by the hard disk. Then, based on that it will fix the sectors size and number of bit use for the addressing of each sector. Basically five type of physical file system used for hard disk, viz., FAT, NTFS, ExFAT, btrfs, and ext4. FSH() function is used for detecting type of physical file system used for each drive. Then, set the attributes of each drive w.r.t to their File System.

Whenever processor is unable to find the required data from the cache and RAM. It will generate a memory request for the hard disk. The third function MDH (multidisk handler) is executed at host controller for every memory request. After receiving a memory request it first check for number of hard disk present in the system. If the system contains a single hard disk then the host controller will directly send the memory request to the hard disk. But if the system contains multiple hard disk, then the algorithm has to check the type of RAID that have been selected for the system. Different type of RAID technologies available for multi hard disk system are RAID 0, RAID 1, RAID 2, RAID 3, RAID 4, RAID 5, RAID 6, RAID 10, RAID 30, RAID 50, RAID60, and still improving. But all RAID technologies basically focus on three aspects, viz., mirroring, stripping, and parity bit. So in case of multi hard disk environment the MDH() detect the type of stripping (bit stripping, or block stripping, or no stripping), mirroring (mirroring or no mirroring), and parity bit (dedicated parity, or distributed parity, or no parity) selected for the system. Then the function will send the memory request to mentioned hard disk with additional required information. This function behaves as a universal algorithm as it capable of dealing with any number of hard disk and with any RAID technology.

Once a hard disk receives a memory request, it will store them in its disk queue. Disk queue is a queue made up of double circular linked list. Each hard disk have their own disk queue. The structure of disk queue’s node represented in Fig. 2. All nodes of disk queue contain nine sections. The first section stores the address of previous node. Similarly, last section stores the address of next node. Seven middle section holds attribute of memory request like Platter, Track, Sector Number, Index, type of request, and BSI. The time required for movement of head from one track to another is called as seek time. Seek time for a memory request can be calculated by multiplication of number of track to move and time required for single track movement (90,00,000 ns). The time required to reach a particular sector by rotation of platter is called as rotational latency. Rotational latency for memory request can be calculated by multiplication of number of sector to cover and time for single sector movement (65,104 ns). The time required for selection of a particular actuator arm based on platter and surface number is called as platter selection time. It cost around 1 ns per actuator selection. So the descending order of per unit time consumption in hard disk is seek time (90,00,000 ns), rotational latency (65,104 ns), and platter selection time (1 ns).

Seek time (SkT) for single track movement $= 9$ millisecond = 90,00,000 ns

Revolution per minute $= 7200$

Revolution per second $= 120$

Number of cycle per second $= 120$

Number of sectors per second $= 120{*}128 = 15{,}360$

Rotational latency (RL) for single sector $= 1/15{,}360 = 65.104 \,\text {micro second} = 65,104 \,\text {ns}$

Once disk queue receives a set of memory request, first it organizes all memory request based on ascending order of their track number. Then, calculate the distance from the track of initial head position to track of first node as LD (left distance). Similarly calculate the distance from initial head position track to track of last node as RD (right distance). If LD is less than RD, then rearrange the sectors (with similar track) in ascending order. Then, arrange the platters (of same track-sector combinations) in ascending order. Finally, serve all memory request from starting to ending index of disk queue. If RD is less than LD, then re-arrange the sectors (with similar track) in descending order. Then arrange the platters (of same track-sector combination) in descending order. Finally serve all memory request from ending to starting index of disk queue. This way of memory request arrangement is far better than the previous disk queuing techniques, as it leads to better disk response time.

Fig. 5

Internal structure of hard disk

Side view of platter and actuator arrangement is represented in Fig. 5. Cylindrical plates (platters) of same size are stacked upon a single spindle motor. All read/write head are attached to a single actuator arm. All heads move together simultaneously and remain at same cylinder. Once actuator reach a particular cylinder, first access all memory request present in different platters of same sector. After that it performs all memory request present in different platters of next sector. Same process continues till end of all request present in same cylinder, then move to next cylinder.

At the time of accessing a memory request normal memory operation will occur, if the concerned bit is accessible. But if it is not accessible, then increase the BSI of that index by 1. If one index has BSI 2 (means it have been inaccessible for more than twice), then that index is transferred to bad sector table. Hard disk stores all data in binary bit format. The last function BSM (bad sector management) deals with bad sector list. Indexes, which came to bad Sector List has both prescribed bit and finalized section as 0. When an index of bad Sector List accessed for the first time, BSM check if the concerned memory request gets the correct output by considering the preferred bit as zero. Then, the finalized section become 1. Thereafter, memory access operation will be conducted by considering the bit as zero. But during first time if the memory request does not get the correct output by considering the preferred bit as zero. Then, the both preferred bit section and finalized section become 1. Thereafter, memory access operation will be conducted by considering the bit as one.

Comparative Analysis

To reflect the effectiveness of proposed algorithm (MODSBSM2), it is compared with 6 traditional (FCFS, SSTF, SCAN, C-SCAN, LOOK, CLOOK), and 8 derived (ODSA, HDSA, RP-13, SMCC, MRSA, SRLF, SATF, FDS) algorithms. Saman Rasool has not entitled his algorithm. So that algorithm represented as RP-13 (as per number of that paper in reference list). First the possible situations divided into two types based on number of platter in hard disk (single-platter hard disk and multi-platter hard disk). Then, each situation further divided into 3 types based on track number of memory requests (ascending, or descending, or random order). So the execution of all fifteen algorithms are compared and tested in six cases, viz., Case-1 (Single Platter Ascending Order Track), Case-2 (Single Platter Descending Order Track), Case-3 (Single Platter Random Order Track), Case-4 (Multi Platter Ascending Order Track), Case-5 (Multi Platter Descending Order Track), Case-6 (Multi Platter Random Order Track). In each cases, all fifteen algorithms executed with twenty memory requests with their particular memory request index (Platter, Track, Sector-based Index).

Assumption

Table 1 and Eqs. 1 2 3 4 indicates the calculation method of disk response time. The IDTrT, EDTrT, CPT, StlT, DRT is considered as 1 ns each. As per assumption Eqs. 4 3 2 1 has been modified and represented as Eqs. 7 8 9 10

$$\begin{aligned} \text {Seek} \, \text {Time}= &\, {} \text {number} \, \text {of} \, \text {tracks} \, \text {to} \, \text {move} * 90,00,000 \, \text {ns.} \end{aligned}$$

(5)

$$\begin{aligned} \text {Rotational} \, \text {latency}= &\, {} \text {number} \, \text {of} \, \text {sectors} \, \text {to} \, \text {cover} * 65104 \, \text {ns.} \end{aligned}$$

(6)

$$\begin{aligned} \text {DTrT}= &\, {} \text {IDTrT} (1 \, \text {ns}) + \text {EDTrT} (1 \, \text {ns}) \nonumber \\= &\, {} 2 \, \text {ns} \end{aligned}$$

(7)

$$\begin{aligned} \text {AT}= &\, {} \text {CPT} (1 \, \text {ns)} + \text {SkT} + \text {StlT} (1 \, \text {ns})\nonumber \\{} & {} + \text {RL} + \text {PST} + \text {DRT} (1 \, \text {ns}) \nonumber \\= &\, {} \text {SkT} + \text {RL} + \text {PST} + 3 \, \text {ns} \end{aligned}$$

(8)

$$\begin{aligned} \text {DAT}= &\, {} \text {AT} + \text {DTrT} (2 \, \text {ns}) \end{aligned}$$

(9)

$$\begin{aligned} \text {DRT}= &\, {} \text {DAT} + \text {DQT} (1 \, \text {ns}) \end{aligned}$$

(10)

Table 1 Disk response time

Complexity Analysis

The amount of resource utilized during execution of an algorithm is called as complexity. Based on type of resource two type of complexity are there, viz., time complexity and space complexity. Whenever an algorithm got optimized by optimizing the performance measure, it always led to additional complexity. The derived disk scheduling algorithms also consume some additional time. Table 2 indicate the additional complexity of all fifteen algorithms. The proposed algorithm consists of five functions. The MPTD () & FSH () will execute during booting of the system with additional complexity of 2 and 5 ns each. They will execute once so will not considered for each memory request. The MDH () will lead to additional complexity of 3 ns. The MODSBSM2.0() will execute for each memory request with additional time complexity of $O (t (\log t) + s (\log s) + p (\log p))$. Where t indicates number of tracks, s indicates max number of different sectors for memory requests at same track, p indicate max number of different platters for Memory request of same track and sector combination. Finally, BSM () will lead to additional time complexity of O(b), where no of bad sector incurred during scheduling. Equation 11 represents the overall complexity of proposed algorithm. So complexity of proposed algorithm:

$$\begin{aligned} \text {Worst} \, \text {case} \, \text {complexity}&= O (2) + O (5) + O (3) \\ & \quad + O (t (\log t) + s (\log s) + p (\log p)) + O (b) \\&= O (t (\log t) + s (\log s) + p (\log p)) \end{aligned} $$

(11)

$\because O (2), O (5), O (3), O (b)$ are negligible parameters.

During algorithm optimization normally, a trade-off between complexity and performance measure have been checked. An optimized algorithm is considered to be better if it have far more better performance measure with respect to additional complexity. Following use-case will justify how the proposed algorithm have better disk response time even after considering the added time complexity.

Table 2 Complexity of all fifteen algorithm

Case-1

This use-case illustrate a situation with 20 memory requests of ascending order track to be executed in a single platter hard disk. Table 3 depicts the memory requests of Case-1. As per this use case the read/write head initially positioned at p1sf1t65sc4.

Table 3 Memory requests of Case-1

Figure 6 represents the total disk response time of all fifteen algorithms with respect to twenty memory request of Case-1. In Case-1, total disk response time of FCFS, SSTF, SCAN, CSCAN, LOOK, and CLOOK are 2,290,302,021, 2,290,302,019, 2,416,302,025, 3,601,536,367, 2,290,302,019, and 3,403,536,355 ns, respectively. In Case-1, SSTF and LOOK are the best traditional disk scheduling algorithm with total disk response time of 2,290,302,019 ns. But after including the overhead time the best traditional algorithm is FCFS with total disk response time (along with overheads) of 2,290,302,021 ns.

Fig. 6

Total disk response time of fifteen algorithms with respect to Case-1

In Case-1, total disk response time of ODSA, HDSA, RP-13, SMCC, MRSA, SRLF, SATF, FDS and MODSBSM2 are 2,290,302,021, 2,290,302,019, 2,944,812,421, 2,290,302,021, 2,290,302,021, 12,319,145,926, 3,063,812,485, 5,492,414,005, and 2,273,635,397 ns, respectively. In Case-1, MODSBSM2 is the best derived disk Scheduling algorithm with total disk response time of 2,273,635,397 ns. After including the overhead time the best derived algorithm is MODSBSM2 with total disk response time (along with overheads) of 2,273,635,397 ns. Based on total disk response time (along with overheads), MODSBSM2 is the best disk scheduling algorithm of Case-1. Table 12 represents the execution of Case-1 with 6 traditional disk scheduling algorithms. Tables 13 and 14 represents the execution of Case-1 with 8 derived, and proposed disk scheduling algorithm.

Case-2

This use-case illustrate a situation with 20 memory requests of descending order track to be executed in a single platter hard disk. Table 4 depicts the memory requests of Case-2. As per this use case the read/write head initially positioned at p1sf2t75sc7.

Table 4 Memory requests of Case-2

Fig. 7

Total disk response time of fifteen algorithms with respect to Case-2

Figure 7 represents the total disk response time of all fifteen algorithms with respect to twenty memory request of Case-2. In Case-2, total disk response time of FCFS, SSTF, SCAN, CSCAN, LOOK, and CLOOK are 2,925,755,107, 2,917,421,795, 2,953,421,801, 3,537,786,416, 2,917,421,795, and 3,429,786,404 ns, respectively. In Case-2, SSTF and LOOK are the best traditional disk scheduling algorithms with total disk response time of 2,917,421,795 ns. But after including the overhead time the best traditional algorithm is LOOK with total disk response time (along with overheads) of 2,917,421,821 ns.

In Case-2, total disk response time of ODSA, HDSA, RP-13, SMCC, MRSA, SRLF, SATF, FDS and MODSBSM2 are 2,451,325,460, 2,459,658,770, 2,917,421,795, 2,451,325,460, 2,451,325,460, 13,255,080,820, 2,900,755,173, 8,165,088,485, 2,442,992,150 ns, respectively. In Case-2, MODSBSM2 is the best derived disk Scheduling algorithm with total disk response time of 2,442,992,150 ns. After including the overhead time the best derived algorithm is MODSBSM2 with total disk response time (along with overheads) of 2,442,992,178 ns. Based on total disk response time (along with overheads), MODSBSM2 is the best disk scheduling algorithm of Case-2. Table 15 represents the execution of Case-2 with 6 traditional disk scheduling algorithms. Tables 16 and 17 represents the execution of Case-2 with 8 derived, and proposed disk scheduling algorithm.

Case-3

This use-case illustrate a situation with 20 memory requests of random order track to be executed in a single platter hard disk. Table 5 depicts the memory requests of Case-3. As per this use case the read/write head initially positioned at p1sf1t165sc7.

Table 5 Memory requests of Case-3

Figure 8 represents the total disk response time of all fifteen algorithms with respect to twenty memory request of Case-3. In Case-3, total disk response time of FCFS, SSTF, SCAN, CSCAN, LOOK, and CLOOK are 8,624,203,045, 3,092,067,619, 3,344,067,625, 3,374,338,480, 3,092,067,619, and 3,086,338,468 ns, respectively. In Case-3, CLOOK is the best traditional disk scheduling algorithm with total disk response time of 3,086,338,468 ns. After including the overhead time the best traditional algorithm is CLOOK with total disk response time (along with overheads) of 3,086,338,494 ns.

In Case-3, total disk response time of ODSA, HDSA, RP-13, SMCC, MRSA, SRLF, SATF, FDS and MODSBSM2 are 2,018,203,044, 2,018,203,044, 2,018,203,044, 2,018,203,044, 2,018,203,044, 11,022,479,233, 3,069,671,844, 4,998,421,859, and 2,009,869,734 ns, respectively. In Case-3, MODSBSM2 is the best derived disk Scheduling algorithm with total disk response time of 2,009,869,734 ns. After including the overhead time the best derived algorithm is MODSBSM2 with total disk response time (along with overheads) of 2,009,869,762 ns. Based on total disk response time (along with overheads), MODSBSM2 is the best disk scheduling algorithm of Case-3. Table 18 represents the execution of Case-3 with 6 traditional disk scheduling algorithms. Tables 19 and 20 represents the execution of Case-3 with 8 derived, and proposed disk scheduling algorithm.

Fig. 8

Total disk response time of fifteen algorithms with respect to Case-3

Case-4

This use-case illustrate a situation with 20 memory requests of ascending order track to be executed in a multi platter hard disk. Table 6 depicts the memory requests of Case-4. As per this use case the read/write head initially positioned at p1sf2t140sc0.

Table 6 Memory requests of Case-4

Figure 9 represents the total disk response time of all fifteen algorithms with respect to twenty memory request of Case-4. In Case-4, total disk response time of FCFS, SSTF, SCAN, CSCAN, LOOK, and CLOOK are 3,018,927,107, 2,245,122,415, 3,054,927,103, 3,564,606,812, 3,018,927,097, and 3,402,606,799 ns, respectively. In Case-4, SSTF is the best traditional disk scheduling algorithm with total disk response time of 2,245,122,415 ns. After including the overhead time the best traditional algorithm is SSTF with total disk response time (along with overheads) of 2,245,122,605 ns.

Fig. 9

Total disk response time of fifteen algorithms with respect to Case-4

In Case-4, total disk response time of ODSA, HDSA, RP-13, SMCC, MRSA, SRLF, SATF, FDS and MODSBSM2 are 2,236,789,103, 2,245,122,415, 2,245,122,415, 2,236,789,103, 2,236,789,103, 11,077,812,663, 2,228,455,789, 5,342,455,777, and 2,228,455,785 ns, respectively. In Case-4, MODSBSM2 is the best derived disk scheduling algorithm with total disk response time of 2,228,455,785 ns. After including the overhead time the best derived algorithm is MODSBSM2 with total disk response time (along with overheads) of 2,228,455,815 ns. Based on total disk response time (along with overheads), MODSBSM2 is the best disk scheduling algorithm of Case-4. Table 21 represents the execution of Case-4 with 6 traditional disk scheduling algorithms. Tables 22 and 23 represents the execution of Case-4 with 8 derived, and proposed disk scheduling algorithm.

Case-5

This use-case illustrate a situation with 20 memory requests of descending order track to be executed in a multi platter hard disk. Table 7 depicts the memory requests of Case-5. As per this use case the read/write head initially positioned at p1sf1t65sc4.

Table 7 Memory requests of Case-5

Fig. 10

Total disk response time of fifteen algorithms with respect to Case-5

Figure 10 represents the total disk response time of all fifteen algorithms with respect to twenty memory request of Case-5. In Case-5, total disk response time of FCFS, SSTF, SCAN, CSCAN, LOOK, and CLOOK are 2,808,999,918, 2,792,333,298, 3,062,333,304, 3,351,731,793, 2,792,333,298, and 3,045,731,781 ns respectively. In Case-5, SSTF is the best traditional disk scheduling algorithm with total disk response time of 2,792,333,298 ns. After including the overhead time the best traditional algorithm is SSTF with total disk response time (along with overheads) of 2,792,333,488 ns.

In Case-5, total disk response time of ODSA, HDSA, RP-13, SMCC, MRSA, SRLF, SATF, FDS and MODSBSM2 are 2,263,463,572, 2,280,130,190, 2,792,333,298, 2,263,463,572, 2,263,463,572, 8,529,445,475, 2,742,333,434, 5,103,445,283, and 2,246,796,950 ns, respectively. In Case-5, MODSBSM2 is the best derived disk scheduling algorithm with total disk response time of 2,246,796,950 ns. After including the overhead time the best derived algorithm is MODSBSM2 with total disk response time (along with overheads) of 2,246,796,980 ns. Based on total disk response time (along with overheads), MODSBSM2 is the best disk scheduling algorithm of Case-5. Table 24 represents the execution of Case-5 with 6 traditional disk scheduling algorithms. Tables 25 and 26 represents the execution of Case-5 with 8 derived, and proposed disk scheduling algorithm.

Case-6

This use-case illustrate a situation with 20 memory requests of random order track to be executed in a multi platter hard disk. Table 8 depicts the memory requests of Case-6. As per this use case the read/write head initially positioned at p1sf2t89sc6.

Table 8 Memory requests of Case-6

Figure 11 represents the total disk response time of all fifteen algorithms with respect to twenty memory request of Case-6. In Case-6, total disk response time of FCFS, SSTF, SCAN, CSCAN, LOOK, and CLOOK are 8,613,348,883, 1,959,565,051, 2,463,565,057, 3,599,158,856, 1,959,565,051, and 2,663,158,844 ns, respectively. In Case-6, SSTF and LOOK are the best traditional disk scheduling algorithms with total disk response time of 1,959,565,051 ns. But after including the overhead time the best traditional algorithm is LOOK with total disk response time (along with overheads) of 1,959,565,077 ns.

Fig. 11

Total disk response time of fifteen algorithms with respect to Case-6

In Case-6, total disk response time of ODSA, HDSA, RP-13, SMCC, MRSA, SRLF, SATF, FDS and MODSBSM2 are 1,976,231,675, 1,959,565,051, 2,178,640,586, 1,976,231,675, 2,161,973,962, 8,053,682,445, 2,233,973,974, 8,115,565,049, and 1,942,898,431 ns, respectively. In Case-6, MODSBSM2 is the best derived disk scheduling algorithm with total disk response time of 1,942,898,431 ns. After including the overhead time the best derived algorithm is MODSBSM2 with total disk response time (along with overheads) of 1,942,898,461 ns. Based on total disk response time (along with overheads), MODSBSM2 is the best disk scheduling algorithm of Case-6. Table 27 represents the execution of Case-6 with 6 traditional disk scheduling algorithms. Tables 28 and 29 represents the execution of Case-6 with 8 derived, and proposed disk scheduling algorithm.

Result Analysis

The traditional and derived algorithms basically focus on optimization of seek time and rotational latency only. Generally, operating system contain different drivers for different type of situation like difference in partition table, file system, number of hard disk and RAID technology. Previous algorithms neither try to develop a universal algorithm (compatible to all type of hard disk), nor consider to minimize the other time parameters.

Table 9 explains the specific benefits of all five function of the proposed algorithm. Modern partition table detector (MPTD) run during booting time to detect the booting section (BIOS or UEFI) and number of addressing table the hard disk contains. Based on that it will set the environment variable like sector size and number of bit for sectors addressing. So this function is applicable for MBR, GPT, and hybrid partition table.

Table 9 Function-based analysis of MODSBSM2

Fig. 12

Hard disk for which proposed algorithm is applicable

Similarly, file system handler (FSH) run during booting time to detect the type of physical file system present in each drive. Based on that it will set the environment variables for that drive. So this function is applicable for FAT, NTFS, ExFAT, btrfs, ext4 file systems. Fist two function executed during the booting process. But the remaining three functions are executed for all memory requests generated for hard disk. When a memory request generated multi disk handler (MDH) checks the number of hard disk present in the system. If system contain only one hard disk, then directly send the memory request to that hard disk. Otherwise checks the type of RAID technology used, then send the memory request to mentioned hard disk with preferable environment variable based on RAID technology. With the combination of MPTD, FSH, MDH the proposed algorithm is applicable to 225 situations as shown in Fig. 12.

Once the disk queue receives a set of memory request, first MODSBSM2() function organizes all memory request based on ascending order of their track number. Then calculate the distance from initial head position track to track of first node as LD (left distance). Similarly calculate the distance from initial head positions track to track of last node as RD (right distance). If LD is less than RD, then rearrange the sectors (with similar track) in ascending order. Then, arrange the platters (of same track-sector combinations) in ascending order. Finally, serve all memory request from starting to ending index of the disk queue. If RD is less than LD, then re-arrange the sectors (with similar track) in descending order. Then arrange the platters (of same track-sector combination) in descending order. Finally serve all memory request from ending to starting index of the disk queue. This way of memory request arrangement is far better than the previous disk queuing techniques, as it leads to better disk response time.

Tables 10 and 11 represents time parameter based performance measure of fifteen algorithms, based on their execution in six cases. The proposed disk scheduling algorithm is able to improve the performance measure by minimizing three output time parameters, viz., seek time, rotational latency and platter selection time. Figure 13 analyzes and compares total disk response time (along with overheads) of fifteen algorithms with respect to six cases. All six traditional algorithms focus on optimization of only seek time. SCAN and LOOK algorithms have the problem of uncertainty in detecting the direction of the initial head movement. Five derived algorithms (ODSA, HDSA, RP-13, SMCC, MRSA) also try to optimize the seek time only. SRLF tries to optimize the rotational latency. SATF tries to optimize both seek time and rotational latency. Both SRLF and SATF are greedy algorithms. So they have two basic problems. First, they go for local optimum instead of global optimum. Second they may lead to starvation of some memory requests. FDS uses fuzzy logic for optimizing both seek time and rotational latency. FDS classify all memory request into 9 groups. First all memory requests divided into three group based on seek time. Then each group further divided into three sub-group based on rotational latency. But here also an uncertainty problem is there for deciding the sequence of memory requests (those are present in same group).

Table 10 Comparative analysis of all fifteen algorithms for Case 1 to Case-4

Table 11 Comparative analysis of all fifteen algorithms for Case 5, 6 and total

MODSBSM2 arrange all memory requests based on track, then rearrange all memory requests (with same track number) based on sector, then further rearrange all memory requests (with same track-sector combination) based on Platter. So it can reduce seek time, rotational latency and platter selection time. The initial head movement decided by comparing the distance of Initial Head Position from lowest track with memory request and from highest track with memory request. So uncertainty problem will not arise in MODSBSM2. Figure 14 represents the Percentage of Total Disk Response time optimized by all fifteen disk response time with respect to FCFS. MODSBSM2 is the most optimized disk scheduling algorithm, which optimize the total disk response time (along with overheads) up to 53.52%.

Fig. 13

Comparative analysis of total disk response time (along with overheads) of fifteen algorithms

Fig. 14

Optimization ratio of fifteen algorithms, based on total disk response time, with respect to FCFS

If any address of the hard disk become inaccessible, then that is called as a bad sector. Hard disk may have two type of bad sector, viz., physical bad sector and logical bad sector. The proposed algorithm is able to detect and manage physical bit bad sector. If a particular index remains inaccessible for two consecutive times, then that index details will be stored in the Bad sector list. Then the BSM function manages the situation by finding a proper prescribed bit for the particular index. The proposed algorithm reduces number of time a memory request executed by n-2 times, where the n indicates the number times the particular bad sector accessed. Heat generation and energy consumption decreases due to the reduction in number of times a memory request got executed.

Energy Conserved = $e*n-2$. ($e \sim 100$ fj, e indicates Energy Consumed per one-bit memory access).

Heat reduced = $h*n-2$ (heat generated per bit access).

Finally summarizing the benefits of MODSBSM2:

• 1. Single Algorithm applicable for 225 different type of hard disk environment (able to deal with all RAID technology, File System, and partition table).

• 2. Optimize the total disk response time (along with overheads) up to 53.52%.

• 3. NO Uncertainty Problem.

• 4. Avoid the starvation.

• 5. MODSBSM2 able to solve the problem of Physical Bit Bad-Sector.

Conclusion

This paper recommends a new algorithm entitled MODSBSM2, for optimization of disk scheduling. The proposed algorithm compared vastly with six traditional and eight derived algorithms in six diverse adequate use cases. The proposed algorithm is able to optimize the output time based performance measure (total disk response time along with overheads) up to 53.52% with respect to FCFS disk algorithm. The proposed algorithm is able to reduce the space complexity of OS kernel, as it is universally applicable to deal with different situation like difference in partition table, file system, number of hard disk and RAID technology. This Algorithm also able to detect and manage physical bit bad sector of the hard disk. In future work, we want to optimize the SSD scheduling algorithm.

Appendix A: Working of Algorithms in Use-Cases

See Tables 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29

Table 12 Case-1 solutions by Traditional Algorithms

Table 13 Case-1 solutions by ODSA, HDSA, RP-13, SMCC, MRSA, SRLF

Table 14 Case-1 solutions by SATF, FDS, MODSBSM2

Table 15 Case-2 solutions by Traditional Algorithms

Table 16 Case-2 solutions by ODSA, HDSA, RP-13, SMCC, MRSA, SRLF

Table 17 Case-2 solutions by SATF, FDS, MODSBSM2

Table 18 Case-3 solutions by Traditional Algorithms

Table 19 Case-3 solutions by ODSA, HDSA, RP-13, SMCC, MRSA, SRLF

Table 20 Case-3 solutions by SATF, FDS, MODSBSM2

Table 21 Case-4 solutions by Traditional Algorithms

Table 22 Case-4 solutions by ODSA, HDSA, RP-13, SMCC, MRSA, SRLF

Table 23 Case-4 solutions by SATF, FDS, MODSBSM2

Table 24 Case-5 solutions by Traditional Algorithms

Table 25 Case-5 solutions by ODSA, HDSA, RP-13, SMCC, MRSA, SRLF

Table 26 Case-5 solutions by SATF, FDS, MODSBSM2

Table 27 Case-6 solutions by Traditional Algorithms

Table 28 Case-6 solutions by ODSA, HDSA, RP-13, SMCC, MRSA, SRLF

Table 29 Case-6 solutions by SATF, FDS, MODSBSM2