Research Of Adaptive Splitting-based I/O Scheduling Algorithm In Disk Storage

In the I/O architecture of operating system,the block I/O layer is a module running independently between the file system and disk storage devices.This module can reduce the I/O processing time on disks,by performing merging and sorting operations with respect to the received I/O requests.However,in the case of a large number of concurrent I/O requests to access disk blocks,the traditional I/O scheduling algorithms,especially the merging operations in the algorithms,will result in a certain time overhead,which will affect system performance in turn.Therefore,how to use the I/O scheduling algorithm to make more reasonable and efficient reorganization of I/O requests in the block I/O layer has become one of the research hotspots of disk optimization.In view of the characteristics and the exsiting problem above,this thesis carries out the research of I/O scheduling algorithm based on block I/O layer.The research work mainly includes the following aspects.Firstly,the distribution of I/O requests in the block I/O layer is studied.Considering that I/O requests with similar starting block numbers are more likely to be consecutive in physical address and are more likely to be associated with the same application,this thesis proposes an adaptive splitting-based block I/O scheduling mechanism.The mechanism attempts to partition the I/O requests in the queue according to the starting block numbers,so that the I/O requests with similar block numbers will be split into the same group as much as possible.After that,merging and reordering operations will be carried out in each group.Different from the traditional I/O scheduling algorithm,the divide-and-conquer idea adopted by the proposed mechanism can significantly reduce the time overhead caused by merging consecutive I/O requests.Secondly,a merge judgment strategy is proposed based on adaptive splitting-based block I/O scheduling mechanism.Considering that,the existing full-merge operation may generate many I/O requests with excessive data volume,which can affect the average response time of I/O requests,this thesis introduces a new merge judgment strategy.The proposed strategy will evaluate whether the current I/O request should be merged with other consecutive I/O requests.The merging operation will be carried out if the constraints are met,and if not,the merging operation will not be conduct.Compared with the common merge mechanism in traditional I/O scheduling algorithm,this strategy can effectively avoid the appearance of I/O requests with excessive data volume and ensure the fairness of response between I/O requests.Thirdly,in order to organize I/O requests more reasonably,a priority-based I/O requests sorting mechanism is proposed.The algorithm sets the corresponding priority value for each I/O request by considering the influence of both the size of the I/O request and the moving distance of the disk head on the I/O response time.In this mechanism,all I/O requests need to be sorted and scheduled according to the priority value.Finally,in order to verify the effectiveness of the proposed optimization scheme,this thesis carries out a series of simulation experiments on the Disksim simulator.The experimental results show that the proposed optimization methods can not only reduce the I/O completion time,but also provide an effective trade-off between the average I/O response time and the overall I/O completion time,which can improve the system performance to a certain degree.