CN106775438B - An I/O Scheduling Method Based on the Read and Write Characteristics of Solid State Disk - Google Patents

Abstract

The invention discloses an I/O scheduling method based on different read and write characteristics of solid state disks. Obtain the optimal merge request cluster page size inside the solid-state disk through black-box testing; separate read and write requests, and process read requests and write requests in batches separately to avoid mutual interference in the mixed mode of reading and writing in the solid-state disk; Considering that the performance of read requests in sequential mode is much higher than that in random mode, read requests are not only queued in the linked list according to the arrival time of the request, but also sorted in the red-black tree according to the initial access address of the read request , to construct the sequence of read requests, forward and backward merge the sorted read requests, the maximum size of the merged request does not exceed the cluster page size; considering the performance of write requests in sequential mode and random mode The performance of write requests is basically the same. Write requests only need to be queued in the linked list according to the arrival time of the requests, and there is no need to sort in the red-black tree to construct the order of write requests.

Description

An I/O Scheduling Method Based on the Read and Write Characteristics of Solid State Disk

technical field

The invention belongs to the technical field of solid-state disk storage, and more specifically relates to an I/O scheduling method based on different read-write characteristics of solid-state disks.

Background technique

Solid state disk (SSD for short) is a hard disk that uses NAND flash memory chips as permanent data storage. As the production cost of NAND flash memory chips decreases, the price of SSDs is becoming more and more accepted by people. SSDs are widely used in data centers. , PCs, and various types of mobile devices are increasingly used. However, for a long time, the devices used to build storage systems are hard disk drives (HDD for short), and most of the existing system software is designed and optimized for HDDs. Directly replacing HDDs with SSDs cannot maximize Give full play to the high performance of SSD. Therefore, it is of great significance to optimize the system software for SSD.

HDD is a mechanical rotating hard disk, and its read and write operations mainly have the following steps:

1. Seek: The head actuator moves all the heads to the cylinder to be accessed, and obtains the current head number to be used; 2. Waiting for rotation: After the corresponding disk and track are located, the disk will rotate, and the disk will rotate. During the process, the magnetic head will read the information in the sector header in the sector directly below it, and compare it with the sector number to be read/written. If there is no match, the disk will continue to rotate. If it matches, the disk will continue to rotate. Start reading/writing data from this sector; 3. Complete data reading and writing. A large part of the time for HDD read and write operations is spent on seeking and waiting for rotation, and the optimization of the IO scheduling algorithm in the Linux kernel is mainly to reduce the time consumption of seeking and waiting for rotation.

In the Linux system, the existing IO scheduling algorithms are mainly Noop algorithm, CFQ algorithm Deadline algorithm and Anticipatory algorithm. Among them, the CFQ, Deadline, and Anticipatory algorithms combine continuous read and write requests for HDDs with long seek time, so that continuous read and write can be performed after the seek is completed. The Noop algorithm does not merge read and write requests, but only inserts new requests at the end of the queue.

However, the above-mentioned IO scheduling algorithm has the following problems: 1. In SSDs, the performance of sequential writes and random writes is basically the same, so combining write requests will not improve the speed of SSDs, but will affect the performance of the system; 2. , In SSD, the read efficiency can be improved only when the read requests are merged under the premise of not exceeding the size of the cluster page, and the read efficiency will not be improved when the size of the read request exceeds the size of the cluster page.

Contents of the invention

Aiming at the above defects or improvement needs of the prior art, the present invention provides an I/O scheduling method based on different read and write characteristics of solid-state disks. Large or cannot be coalesced, and write requests have technical problems with unnecessary coalescing.

In order to achieve the above object, according to one aspect of the present invention, a kind of IO scheduling method based on the read and write characteristics of solid state disk is provided, comprising the following steps:

(1) Receive the bio request from the upper layer application and processed by the file system, and judge whether the type of the bio request is a read request or a write request, if it is a read request, then go to step (2), if it is a write request, go to step (3);

(2) Determine whether the read request can be merged with its adjacent read request, if it cannot be merged, then go directly to step (4); if it can be merged and the size of the merged page does not exceed the size of the cluster page, then merge it with Adjacent read requests are merged, and the merged read request can still be merged with its adjacent read requests, and it should be ensured that the merged size does not exceed the size of the cluster page. Put the final merged read request into the read queue and read red-black tree for the system to read data. Then go to step (4).

(3) Judging whether the write request can be merged with the write request in the cache, if possible, merge, and insert the merged write request into the end of the scheduler queue, and go to step (4); otherwise, judge whether it can Merge with the write request in the hash table, if possible, merge, and insert the merged write request into the end of the scheduler queue, and turn to step (4);

(4) Distribute the requests in the scheduler queue to the request queue of the device driver.

Preferably, step (2) includes the following sub-steps:

(2.1) For the read request, judge whether there is a read request merged last time, and if so, jump to step (2.2); otherwise, jump to step (2.3);

(2.2) Determine whether the read request can be merged with the last merged read request. If it cannot be merged, then jump to step (2.3), if it can be merged forward, then jump to step (2.4), if it can be merged backward, then jump to step (2.5);

(2.3) Judging whether the read request can be merged backwards with the request in the hash list, if so, jump to step (2.5); otherwise, jump to step (2.6);

(2.4) Complete the merge of the read request Rfrq that can be forward merged with the read request, and judge whether the read request Rfrq after the forward merge can continue to be sorted according to the initial access address of the request in the red-black tree in the scheduler The previous read request Rprev of Rfrq continues to merge forward. If yes, jump to step (2.7), otherwise jump to step (2.8);

(2.5) Complete the merging of the request Rbrq that can be merged backwards with the read request, and determine whether the request Rbrq after the backward merging can continue to read the Rbrqs sorted according to the initial access address of the request in the red-black tree in the scheduler The latter requests Rnext to proceed with the backward merge. If so, jump to step (2.9), otherwise jump to step (2.10);

(2.6) Judging whether the read request can be forward merged with the request in the scheduler to read the red-black tree, if so, jump to step (2.4), otherwise jump to step (2.11);

(2.7) Complete the forward merge of the read request Rfrq and the read request Rperv, delete the Rfrq request in the scheduler read queue, read the red-black tree, and the general block layer hash list; at the same time, change the Rprev according to the size of the merged read request The location in the hash list; and the merged latest service time is set to the smaller one of the latest service time of Rfrq and Rprev; finally, the last merged read request is marked as Rfrq.

(2.8) The last merged read request is set to Rfrq, and the starting address of Rfrq is updated in the red-black tree;

(2.9) Complete the backward merge of request Rbrq and request Rnext, delete the Rnext request in the read queue of the scheduler, read the red-black tree, and the hash list of the general block layer, update the position of the Rbrq request in the hash list, and put The earlier service time in Rbrq and Rnext is set as the service time of the merged read request, Rbrq is marked as the last merged read request, and jumps to step (2.14);

(2.10) mark Rbrq as the read request merged last time, and update the position of Rbrq request in the hash list, end conversion;

(2.11) distribute a request Rnrq for this bio request, and request initialization Rnrq with this bio, and judge whether Rnrq has merged property, if have then jump to step (2.12); Otherwise jump to step (2.13);

(2.12) Add the Rnrq request to the hash list, and judge whether there is a read request merged last time. If it exists, then jump directly to step (2.13); otherwise first mark Rnrq as the last merged read request, and jump to step (2.13);

(2.13) Add the Rnrq request to the end of the read queue in the scheduler and read the red-black tree.

Preferably, step (3) includes the following substeps:

(3.1) For the write request, judge whether there is a write request merged last time, and if so, jump to step (3.2); otherwise, jump to step (3.3);

(3.2) Determine whether the bio request can be merged with the last merged write request, if it can be merged forward, go to step (3.4); if it can be merged backwards, go to step (3.5); if not Merge and jump to step (3.3);

(3.3) Determine whether the bio request can be merged backwards with the request in the hash list, and if so, jump to step (3.5); otherwise, jump to step (3.6);

(3.4) Forward merging the bio request with the last merged write request, and judging whether it can continue to be merged with the previous request Wprev in the write list in the scheduler after the merge. If it can be merged with Wprev, then jump to step (3.7), otherwise jump to step (3.8);

(3.5) Complete the backward merging of the bio request and the request Wbrq that can be merged backwards, and judge whether the merged Wbrq can continue to be merged with the next request Wnext of Wbrq in the write list of the scheduler. If yes, jump to step (3.9); otherwise, jump to step (3.10);

(3.6) Allocate a new request Wnrq for the bio request, and initialize Wnrq with the bio request. Then determine whether Wnrq has the merge attribute. If there is, jump to step (3.11); otherwise, jump to step (3.12);

(3.7) Complete the merger of Wfrq and Wprev, and delete Wfrq in the write list and hash list of the scheduler, then adjust the position of Wprev in the hash list, and finally mark Wprev as the last merged write request, which has been Convert the bio request into a write request, and end this conversion;

(3.8) Mark Wfrq as the last merged write request, the bio request has been converted into a write request, and this conversion is ended;

(3.9) Complete the merging of Wbrq and Wnext, and delete Wnext in the write list and hash list of the scheduler, then adjust the position of Wbrq in the hash list, and finally mark Wbrq as the last merged write request. The bio request is converted into a write request, and the conversion ends;

(3.10) Adjust the position of Wbrq in the hash linked list, and mark Wbrq as the write request merged last time, the bio request has been converted into a write request, and this conversion is ended;

(3.11) Add Wnrq to the hash list, and judge whether the write request merged last time exists. If it does not exist, then mark Wnrq as the last merged write request, and jump to step (3.12); otherwise, jump directly to step (3.12);

(3.12) Add Wnrq to the tail of the scheduler write list, thereby converting the bio request into a write request.

Preferably, step (4) includes the following sub-steps:

(4.1) Determine whether the stage of the current distribution request in the scheduler queue is in the read batch processing stage or the write batch processing stage, if it is in the read batch processing stage, then jump to step (4.2); if it is in the write batch processing stage, Then jump to step (4.3),

(4.2) Determine whether the total number of requests distributed in the read batch processing stage has exceeded the threshold. If the threshold has been exceeded, then jump to step (4.4), otherwise jump to step (4.5);

(4.3) Determine whether the total number of requests distributed in the batch writing stage has reached the upper limit, if it has reached the upper limit, jump to step (4.4), otherwise jump to step (4.6);

(4.4) Create a batch processing stage, and determine whether there is a corresponding read request in the scheduler queue, if there is, jump to step (4.9); otherwise jump to step (4.10);

(4.5) set the request Drq to be distributed in the scheduler to next_rq[read], and jump to step (4.7);

(4.6) Set the request Drq to be distributed in the scheduler to next_rq[write], and jump to step (4.8);

(4.7) Distribute Drq to the request queue of the device driver layer, delete the Drq from the read linked list and read red-black tree of the scheduler, and set next_rq[read] to the value of Drq in the read red-black tree of the scheduler For the next request, count the operation at last, and end the request distribution process;

(4.8) Distribute Drq to the request queue of the device driver layer, delete Drq from the write list of the scheduler, set next_rq[write] to be the next request of Drq in the write list of the scheduler, and finally count the operation, End the request distribution process;

(4.9) Judging whether there is a request in the write list of the scheduler, if not, then jump to step (4.11); if it exists, continue to judge whether there is a timed-out write request or the number of times the write request is starved has reached the upper limit, If the judgment result is true, then jump to step (4.12); otherwise, jump to step (4.11);

(4.10) Judging whether there is a request in the write list of the scheduler, if there is, then jump to step (4.12); otherwise, there is no request to be distributed in the scheduler, and this request distribution process is ended;

(4.11) Determine whether next_rq[read] exists. If it exists, jump to step (4.13); otherwise, jump to step (4.14);

(4.12) Set the number of times the write request is starved to 0. Then judge whether there is a timeout write request or whether next_rq[write] is empty. If the determination result is true, jump to step (4.15); otherwise jump to step (4.16);

(4.13) The request Drq to be distributed is set to next_rq[read], batching=0 is set, a read batch processing stage is started to be created, and the step (4.7) is jumped to;

(4.14) the request Drq to be distributed is set to the first request in the scheduler read linked list, batching=0 is set, a read batch processing stage is started to be created, and the step (4.7) is jumped to;

(4.15) the request Drq to be distributed is set to the first request in the scheduler write linked list, batching=0 is set, a write batch stage is started to be created, and the step (4.8) is jumped to;

(4.16) Set the request Drq to be distributed to next_rq[write], set batching=0, start to create a write batch processing stage, and jump to step (4.8).

Generally speaking, compared with the prior art, the above technical solutions conceived by the present invention can achieve the following beneficial effects:

(1) The present invention can solve the problem that the continuous read requests that exist in the existing method are too large or not merged: due to the adoption of step (2.2) step (2.4) step (2.5) and step (2.7), it can Solve the problem that the read requests in the existing Noop algorithm are not merged, and the read requests in the CFQ, Deadline, and Anticipatory algorithms are merged too much.

(2) The present invention can solve the problem of unnecessary merging of continuous write requests existing in the existing method: due to the adoption of step (3.4) step (3.5) step (3.7) and step (3.9), the existing method can be solved There is a problem of merging consecutive write requests in the IO scheduling algorithm.

(3) The present invention makes full use of the read and write performance of solid state disks under different access modes: considering that the performance of read requests in SSDs in sequential mode is much higher than that of read requests in random modes, the read requests are not only based on the time when the request arrives Queue in the linked list, and also sort in the red-black tree according to the initial access address of the read request to construct the order of the read request, and perform forward and backward merges on the sorted read requests; considering the write in sequential mode The performance of the request is basically the same as that of the write request in the random mode. The write request only needs to be queued in the linked list according to the arrival time of the request. It does not need to be sorted in the red-black tree to construct the order of the write request, and the write request is only processed later. to merge.

(4) The present invention makes full use of the rich parallelism of solid state disks: when merging read and write requests, it is considered that the smallest read and write operation unit in the SSD is a page, and in order to utilize the parallelism inside the SSD, the read and write operations may be aggregated The cluster page is the smallest operation unit. The size of the cluster page is obtained through black-box testing, and when merging requests, ensure that the merged request does not exceed the size of the cluster page. When the request size reaches the size of the cluster page, continuing to merge requests will not bring performance improvement, but will cause the SSD device to wait idle and reduce performance.

Description of drawings

Figure 1 is the I/O path accessed by the Linux operating system SSD.

Fig. 2 is a flow chart of the I/O scheduling method based on different read and write characteristics of the solid state disk according to the present invention.

Fig. 3 is the transition from read bio request to request in the scheduling method.

Fig. 4 is the transition from writing bio request to request in the scheduling method.

Fig. 5 is the dispatching request to the device driver layer in the dispatching method.

Detailed ways

In order to make the object, technical solution and advantages of the present invention clearer, the present invention will be further described in detail below in conjunction with the accompanying drawings and embodiments. It should be understood that the specific embodiments described here are only used to explain the present invention, not to limit the present invention. In addition, the technical features involved in the various embodiments of the present invention described below can be combined with each other as long as they do not constitute a conflict with each other.

As shown in Figure 1, the IO request initiated by the upper-layer application through the system call read-write module will first pass through the virtual file system layer (Virtual file system, referred to as VFS), and reach the file system layer that actually needs to be accessed, and then pass through the general block layer and IO scheduling layer, and finally reach the SCSI device driver layer to request data from the underlying disk. The I/O scheduling method based on the different read-write characteristics of the solid state disk in the present invention works on the I/O scheduling layer. Specifically complete the following two functions:

1. Cooperate with the general block layer to encapsulate the bio request issued by the file system layer into a request according to a certain strategy, and add it to the request queue of the scheduling layer;

2. Distribute the requests in the request queue of the IO scheduling layer to the request queue of the lower SCSI device driver layer according to a certain strategy. The read requests arriving at the solid-state disk show a stronger sequence, which can reasonably and moderately utilize the internal parallelism of the solid-state disk and avoid mutual interference between read and write requests, thereby improving the I/O performance of the entire solid-state disk system.

The overall idea of the present invention is that it fully considers the mutual interference of read and write requests in the solid state disk, separates the read and write requests, and processes read requests and write requests in batches; considering that the performance of read requests in sequential mode is much higher than that in random mode For the performance of read requests, the read requests are not only queued in the linked list according to the arrival time of the requests, but also sorted in the red-black tree according to the initial access address of the read requests to construct the order of the read requests, and the read requests after sorting Perform forward merging and backward merging; considering that the performance of write requests in sequential mode is basically the same as that in random mode, write requests only need to be queued in the linked list according to the arrival time of the request, and do not need to be in the red-black tree. Sorting constructs the sequence of write requests, and only merges backwards for write requests; considering that there is an optimal parallelism available in solid-state disks, when the merge request reaches the size of the cluster page, the merge will not continue, and the request will reach When the cluster page size is small, the rich parallelism in the solid state disk can be fully utilized, and continuing to merge requests will not bring about performance improvement, but will cause the SSD device to wait idle and reduce performance.

The present invention is implemented in the I/O scheduling layer of the Linux kernel, and specifically completes the following two functions: 1. Cooperate with the general block layer to encapsulate the bio request issued by the file system layer into a request according to a certain strategy, and add it to the request queue of the scheduling layer ; 2. Distribute the requests in the request queue of the IO scheduling layer to the request queue of the lower SCSI device driver layer according to a certain strategy. The read requests arriving at the solid-state disk show a stronger sequence, which can reasonably and moderately utilize the internal parallelism of the solid-state disk and avoid mutual interference between read and write requests, thereby improving the I/O performance of the entire solid-state disk system.

As shown in Figure 2, the IO scheduling method based on the read and write characteristics of the solid state disk in the present invention includes the following steps:

(1) Receive the bio request from the upper-layer application and process through the file system (in this embodiment, the file system is an ext4 file system), and judge whether the type of the bio request is a read request or a write request, if it is a read request Then go to step (2), if it is a write request, go to step (3);

(2) Determine whether the read request can be merged with its adjacent read request, if it cannot be merged, then go directly to step (4); if it can be merged and the size of the merged page does not exceed the size of the cluster page, then merge it with Adjacent read requests are merged, and the merged read request can still be merged with its adjacent read requests, and it should be ensured that the merged size does not exceed the size of the cluster page. Put the final merged read request into the read queue and read red-black tree for the system to read data. Then go to step (4).

(3) Judging whether the write request can be merged with the write request in the cache, if possible, merge, and insert the merged write request into the end of the scheduler queue, and go to step (4); otherwise, judge whether it can Merge with the write request in the hash table, if possible, merge, and insert the merged write request into the end of the scheduler queue, and turn to step (4);

(4) Distribute the requests in the scheduler queue to the request queue of the device driver, and the process ends.

As shown in Figure 3, step (2) in the inventive method comprises the following substeps:

(2.1) For the read request, judge whether there is a read request merged last time, and if so, jump to step (2.2); otherwise, jump to step (2.3);

(2.2) Determine whether the read request can be merged with the last merged read request. If it cannot be merged, then jump to step (2.3), if it can be merged forward, then jump to step (2.4), if it can be merged backwards, then jump to step (2.5); specifically, if the read If the address of the request is continuous with the previous read request, and the size of the merged request does not exceed the size of the cluster page, it means that it can be merged forward. If the address of the read request is continuous with the address of the next read request , and the merged read request size does not exceed the cluster page size, it means that it can be merged backwards;

The advantage of this step is that by caching the last merged request, the delay in searching for a request that can be merged with the current read request can be greatly shortened with little overhead, improving the efficiency of the merged request and increasing performance; in addition, after the merge The size of the request does not exceed the size of the cluster page, which can make full use of the rich parallelism inside the SSD, and will not cause the SSD device to wait idle due to excessive consolidation, which can further improve performance;

(2.3) Judging whether the read request can be merged backwards with the request in the hash list, if so, jump to step (2.5); otherwise, jump to step (2.6);

(2.4) Complete the merge of the read request Rfrq that can be forward merged with the read request, and judge whether the read request Rfrq after the forward merge can continue to be sorted according to the initial access address of the request in the red-black tree in the scheduler The previous read request Rprev of Rfrq continues to merge forward. If yes, jump to step (2.7); otherwise, jump to step (2.8);

(2.5) Complete the merging of the request Rbrq that can be merged backwards with the read request, and determine whether the request Rbrq after the backward merging can continue to read the Rbrqs sorted according to the initial access address of the request in the red-black tree in the scheduler The latter requests Rnext to proceed with the backward merge. If so, jump to step (2.9), otherwise jump to step (2.10);

(2.6) Judging whether the read request can be forward merged with the request in the scheduler to read the red-black tree, if so, jump to step (2.4), otherwise jump to step (2.11);

(2.7) Complete the forward merge of the read request Rfrq and the read request Rperv, delete the Rfrq request in the scheduler read queue, read the red-black tree, and the general block layer hash list; at the same time, change the Rprev according to the size of the merged read request The position in the hash list; and the latest service time after merging is set to the smaller one of the latest service time of Rfrq and Rprev; finally, the last merged read request is marked as Rfrq, and this conversion ends. Specifically, the above steps are to delete the copy of the merged read request, adjust the service time and position in the hash list of the merged read request, and record the address of the last merged read request;

The advantage of this step is: through forward merging, small requests can be aggregated into large requests, which can greatly improve the throughput of the system;

(2.8) The last merged read request is set to Rfrq, and the starting address of Rfrq is updated in the red-black tree;

(2.9) Complete the backward merge of request Rbrq and request Rnext, delete the Rnext request in the read queue of the scheduler, read the red-black tree, and the hash list of the general block layer, update the position of the Rbrq request in the hash list, and put The earlier service time in Rbrq and Rnext is set as the service time of the merged read request, Rbrq is marked as the last merged read request, and jumps to step (2.14);

The advantage of this step is: through backward merging, small requests can be aggregated into large requests, which can greatly improve the throughput of the system;

(2.10) mark Rbrq as the read request merged last time, and update the position of Rbrq request in the hash list; end conversion;

(2.11) distribute a request Rnrq for this bio request, and request initialization Rnrq with this bio, and judge whether Rnrq has merged property, if have then jump to step (2.12); Otherwise jump to step (2.13);

(2.12) Add the Rnrq request to the hash list, and judge whether there is a read request merged last time. If it exists, then jump directly to step (2.13); otherwise first mark Rnrq as the last merged read request, and jump to step (2.13);

(2.13) Add the Rnrq request to the end of the read queue in the scheduler and read the red-black tree;

The advantage of this step is: set the latest time for the read request to be serviced, give priority to the overtime read request, and avoid a certain read request from being unserviced for a long time; in addition, the read request is not only queued in the linked list according to the arrival time of the request, It is also sorted in the red-black tree according to the initial access address of the read request to construct the sequentiality of the read request, so as to make full use of the read performance in the sequential mode which is far superior to that in the random mode;

As shown in Figure 4, step (3) in the inventive method comprises the following substeps:

(3.1) For the write request, judge whether there is a write request merged last time, and if so, jump to step (3.2); otherwise, jump to step (3.3);

(3.2) Determine whether the bio request can be merged with the last merged write request, if it can be merged forward, go to step (3.4); if it can be merged backwards, go to step (3.5); if not Merge and jump to step (3.3);

The advantage of this step is that by caching the last merged request, the delay in searching for a request that can be merged with the current bio request can be greatly shortened, improving the efficiency of the merged request, and increasing performance; in addition, after the merge The size of the request does not exceed the size of the cluster page, which can make full use of the rich parallelism inside the SSD, and will not cause the SSD device to wait idle due to excessive consolidation, which can further improve performance;

(3.3) Determine whether the bio request can be merged backwards with the request in the hash list, and if so, jump to step (3.5); otherwise, jump to step (3.6);

(3.4) Forward merging the bio request with the last merged write request, and judging whether it can continue to be merged with the previous request Wprev in the write list in the scheduler after the merge. If it can be merged with Wprev, then jump to step (3.7), otherwise jump to step (3.8);

(3.5) Complete the backward merging of the bio request and the request Wbrq that can be merged backwards, and judge whether the merged Wbrq can continue to be merged with the next request Wnext of Wbrq in the write list of the scheduler. If yes, jump to step (3.9); otherwise, jump to step (3.10);

The advantage of this step is: through backward merging, small requests can be aggregated into large requests, which can greatly improve the throughput of the system;

(3.6) Allocate a new request Wnrq for the bio request, and initialize Wnrq with the bio request. Then determine whether Wnrq has the merge attribute. If there is, jump to step (3.11); otherwise, jump to step (3.12);

(3.7) Complete the merger of Wfrq and Wprev, and delete Wfrq in the write list and hash list of the scheduler, then adjust the position of Wprev in the hash list, and finally mark Wprev as the last merged write request, which has been Convert the bio request into a write request, and end this conversion;

(3.8) Mark Wfrq as the last merged write request, the bio request has been converted into a write request, and this conversion is ended;

(3.9) Complete the merging of Wbrq and Wnext, and delete Wnext in the write list and hash list of the scheduler, then adjust the position of Wbrq in the hash list, and finally mark Wbrq as the last merged write request. The bio request is converted into a write request, and the conversion ends;

(3.10) Adjust the position of Wbrq in the hash linked list, and mark Wbrq as the write request merged last time, the bio request has been converted into a write request, and this conversion is ended;

(3.11) Add Wnrq to the hash list, and judge whether the write request merged last time exists. If it does not exist, then mark Wnrq as the last merged write request, and jump to step (3.12); otherwise, jump directly to step (3.12);

(3.12) Add Wnrq to the tail of the scheduler write linked list, thereby converting the bio request into a write request;

The advantage of this step is: fully considering that the performance of sequential write requests in SSD is basically the same as that of random write requests, the write requests are only queued in the linked list according to the arrival time, and there is no need to follow the initial access address of the write request in red and black. Sorting in the tree, constructing the order of write requests, eliminating the performance overhead of sorting and improving performance;

As shown in Figure 5, step (4) in the inventive method comprises the following substeps:

(4.1) Determine whether the current distribution request in the scheduler queue is in the read batch processing phase or the write batch processing phase. If it is in the batch reading phase, then jump to step (4.2); if it is in the batch writing phase, then jump to step (4.3); specifically, by obtaining the value of the next_rq[dir] variable when the program is running Determine whether the distribution request is in the batch read phase or the batch write phase. The advantage of this step is: distribute read requests or write requests in batches, avoid performance degradation caused by mutual interference between read and write requests in SSD;

(4.2) Determine whether the total number of requests distributed in the read batch processing stage has exceeded the threshold. If the threshold has been exceeded, then jump to step (4.4), otherwise jump to step (4.5); in the present invention, the value range of the threshold is (0,16].

(4.3) Determine whether the total number of requests distributed in the batch writing stage has reached the upper limit, if it has reached the upper limit, jump to step (4.4); otherwise, jump to step (4.6);

(4.4) Create a batch processing stage, and determine whether there is a corresponding read request in the scheduler queue, if there is, jump to step (4.9); otherwise jump to step (4.10);

(4.5) set the request Drq to be distributed in the scheduler to next_rq[read], and jump to step (4.7);

(4.6) Set the request Drq to be distributed in the scheduler to next_rq[write], and jump to step (4.8);

(4.7) Distribute Drq to the request queue of the device driver layer, delete the Drq from the read linked list and read red-black tree of the scheduler, and set next_rq[read] to the value of Drq in the read red-black tree of the scheduler For the next request, count the operation at last, and end the request distribution process;

The advantage of this step is: in the stage of batch distribution of read requests, the next read request is obtained from the red-black tree species, so as to use the sorting function of the red-black tree to construct the sequence of read requests, and make full use of the performance of sequential read in SSD, which is much higher than Random read performance;

(4.8) Distribute Drq to the request queue of the device driver layer, delete Drq from the write list of the scheduler, set next_rq[write] to be the next request of Drq in the write list of the scheduler, and finally count the operation, End the request distribution process;

The advantage of this step is that in the phase of distributing write requests in batches, the next write request is obtained from the linked list without constructing the sequence of write requests, thereby saving the overhead of sorting and making full use of the performance of random write in SSD and sequential write. have the same performance;

(4.9) Judging whether there is a request in the write list of the scheduler, if not, then jump to step (4.11); if it exists, continue to judge whether there is a time-out write request or the number of times the write request is starved has reached the upper limit. If the judgment result is true, then jump to step (4.12); otherwise, jump to step (4.11);

The advantage of this step is: the batch distribution process of read requests is created first, and read requests are given a higher priority, which has met the user's strict requirements on the response time of read requests. In addition, in order to prevent write requests from being starved to death, the The latest time when a write request needs to be serviced. When a write request times out, the timed-out write request is given priority;

(4.10) Determine whether there is a request in the write list of the scheduler. If it exists, jump to step (4.12); otherwise, there is no request to be distributed in the scheduler, and the request distribution process ends;

(4.11) Determine whether next_rq[read] exists. If it exists, jump to step (4.13); otherwise, jump to step (4.14);

(4.12) Prepare for the batch processing phase of the write request, and set the number of times the write request is starved to 0. Then judge whether there is a timeout write request or whether next_rq[write] is empty. If the determination result is true, jump to step (4.15); otherwise jump to step (4.16);

(4.13) The request Drq to be distributed is set to next_rq[read], batching=0 is set, a read batch processing stage is started to be created, and the step (4.7) is jumped to;

(4.14) the request Drq to be distributed is set to the first request in the scheduler read linked list, batching=0 is set, a read batch processing stage is started to be created, and the step (4.7) is jumped to;

(4.15) the request Drq to be distributed is set to the first request in the scheduler write linked list, batching=0 is set, a write batch stage is started to be created, and the step (4.8) is jumped to;

(4.16) Set the request Drq to be distributed to next_rq[write], set batching=0, start to create a write batch processing stage, and jump to step (4.8).

Those skilled in the art can easily understand that the above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. Any modifications, equivalent replacements and improvements made within the spirit and principles of the present invention, All should be included within the protection scope of the present invention.

Claims (4)

1. an IO scheduling method based on solid state disk read and write characteristics, is characterized in that, comprises the following steps: (1) Receive the bio request from the upper layer application and processed by the file system, and judge whether the type of the bio request is a read request or a write request, if it is a read request, then go to step (2), if it is a write request, then Go to step (3); (2) Determine whether the read request can be merged with its adjacent read request, if it cannot be merged, then go directly to step (4); if it can be merged and the size of the merged page does not exceed the size of the cluster page, then merge it with Adjacent read requests are merged, and the merged read request can still be merged with its adjacent read requests, and it should be ensured that the merged size does not exceed the size of the cluster page, and the final merged read request is put into the read queue and read In the red-black tree, read data for the system, then turn to step (4); (3) Judging whether the write request can be merged with the write request in the cache, if possible, merge, and insert the merged write request into the end of the scheduler queue, and go to step (4); otherwise, judge whether it can Merge with the write request in the hash table, if possible, merge, and insert the merged write request into the end of the scheduler queue, and turn to step (4); (4) Distribute the requests in the scheduler queue to the request queue of the device driver. 2. IO scheduling method according to claim 1, is characterized in that, step (2) comprises the following substeps: (2.1) For the bio request, judge whether there is a read request merged last time, if there is, then jump to step (2.2); otherwise jump to step (2.3); (2.2) Determine whether the bio request can be merged with the last merged read request. If it cannot be merged, then jump to step (2.3). If it can be merged forward, then jump to step (2.4). If it can be merged To merge, jump to step (2.5); (2.3) Determine whether the bio request can be merged backwards with the request in the hash list, and if so, jump to step (2.5); otherwise, jump to step (2.6); (2.4) Forward merge the bio request with the last merged read request, and determine whether the read request Rfrq after the forward merge can continue to be read in the red-black tree in the scheduler and sorted according to the initial access address of the request The previous read request Rprev of the read request Rfrq continues to merge forward, if it can, then jump to step (2.7), otherwise jump to step (2.8); (2.5) Merge the bio request with the last merged read request backwards, and judge whether the read request Rbrq after the backward merged can continue to be sorted according to the initial access address of the request in the red-black tree in the scheduler The last request Rnext of the read request Rbrq continues to merge backwards; if possible, jump to step (2.9), otherwise jump to step (2.10); (2.6) Judging whether the read request can be forward merged with the request in the scheduler to read the red-black tree, if so, jump to step (2.4), otherwise jump to step (2.11); (2.7) Complete the forward merge of read request Rfrq and read request Rperv, delete the read request Rfrq in the scheduler read queue, read red-black tree, and general block layer hash list; change the read request according to the size of the merged read request Request the position of Rprev in the hash list; and set the merged latest service time to the smaller one of the latest service time of read request Rfrq and read request Rprev; finally set the last merged read request as read Request Rfrq to end the conversion; (2.8) the last merged read request is set to read request Rfrq, and reads the starting address of read request Rfrq updated in the red-black tree, ends conversion; (2.9) Complete the backward merge of the read request Rbrq and the request Rnext, delete the request Rnext in the read queue of the scheduler, read the red-black tree, and the hash list of the general block layer, and update the position of the read request Rbrq in the hash list , setting the earlier service time of the read request Rbrq and the request Rnext as the service time of the merged read request, marking the read request Rbrq as the last merged read request, and ending the conversion; (2.10) mark read request Rbrq as the read request merged last time, and update the position of read request Rbrq in the hash list, end conversion; (2.11) allocate a new read request Rnrq for the bio request, and use the bio request to initialize the read request Rnrq, and judge whether the read request Rnrq has a merge attribute, if so, jump to step (2.12); otherwise jump to step ( 2.13); (2.12) Add the read request Rnrq to the hash linked list, and judge whether there is a read request merged last time, and if so, jump directly to step (2.13); otherwise, first mark the read request Rnrq as the read request merged last time , and jump to step (2.13); (2.13) Add the read request Rnrq to the end of the read queue in the scheduler and read the red-black tree. 3. IO scheduling method according to claim 2, is characterized in that, step (3) comprises the following substeps: (3.1) For the bio request, judge whether there is a write request merged last time, and if so, jump to step (3.2); otherwise, jump to step (3.3); (3.2) Determine whether the bio request can be merged with the last merged write request, if it can be merged forward, go to step (3.4); if it can be merged backwards, go to step (3.5); if not Merge and jump to step (3.3); (3.3) Determine whether the bio request can be merged backwards with the request in the hash list, and if so, jump to step (3.5); otherwise, jump to step (3.6); (3.4) Forward merge the bio request with the last merged write request, and determine whether the write request Wfrq after the forward merge can continue to be merged with its previous write request Wprev in the write list in the scheduler, If it can be merged with the write request Wprev, then jump to step (3.7), otherwise jump to step (3.8); (3.5) Merge the bio request with the last merged write request backwards, and judge whether the write request Wbrq after the backward merge can continue to be merged with the next request Wnext in the write list of the scheduler, and jump if it can Go to step (3.9); otherwise jump to step (3.10); (3.6) Allocate a new write request Wnrq for the bio request, and use the bio request to initialize the write request Wnrq, then judge whether the write request Wnrq has a merge attribute, if so, jump to step (3.11); otherwise jump to step (3.12 ); (3.7) Complete the merging of the write request Wfrq and the write request Wprev, and delete the write request Wfrq in the write list and the hash list of the scheduler, and then need to adjust the position of the write request Wprev in the hash list, and finally write the write request Wprev The write request marked as the last merge has converted the bio request into a write request, ending this conversion; (3.8) Mark the write request Wfrq as the last merged write request, the bio request has been converted into a write request, and this conversion is ended; (3.9) Complete the merging of the write request Wbrq and the request Wnext, and delete the request Wnext in the write list and the hash list of the scheduler, then need to adjust the position of the write request Wbrq in the hash list, and finally mark the write request Wbrq as up The merged write request has converted the bio request into a write request, ending this conversion; (3.10) Adjust the position of the write request Wbrq in the hash linked list, and mark the write request Wbrq as the last merged write request, which has converted the bio request into a write request, and ends this conversion; (3.11) Add the write request Wnrq to the hash list, and judge whether the last merged write request exists, if not, then mark the write request Wnrq as the last merged write request, and jump to step (3.12) ; Otherwise, skip directly to step (3.12); (3.12) Add the write request Wnrq to the tail of the scheduler write list, thereby converting the bio request into a write request. 4. IO scheduling method according to claim 3, is characterized in that, step (4) comprises the following substeps: (4.1) Determine whether the stage of the current distribution request in the scheduler queue is in the read batch processing stage or the write batch processing stage, if it is in the read batch processing stage, then jump to step (4.2); if it is in the write batch processing stage, Then jump to step (4.3), (4.2) Determine whether the total number of batching requests distributed in the read batch processing stage has exceeded the threshold, if it has exceeded the threshold, then jump to step (4.4), otherwise jump to step (4.5); (4.3) Determine whether the total number of batching requests distributed in the batch writing stage has reached the upper limit, if it has reached the upper limit, jump to step (4.4), otherwise jump to step (4.6); (4.4) Create a batch processing stage, and determine whether there is a corresponding read request in the dispatcher queue, if there is, jump to step (4.9); otherwise jump to step (4.10); (4.5) set the request Drq to be distributed in the scheduler to next_rq[read], and jump to step (4.7); (4.6) set the request Drq to be distributed in the scheduler to next_rq[write], and jump to step (4.8); (4.7) Distribute the request Drq to be distributed to the request queue of the device driver layer, delete the request Drq to be distributed from the read list and read the red-black tree of the scheduler, and set next_rq[read] to the request Drq to be distributed in The scheduler reads the next request in the red-black tree, and finally adds 1 to batching to end the request distribution process; (4.8) Distribute the request Drq to be distributed to the request queue of the device driver layer, delete the request Drq to be distributed from the write list of the scheduler, and set next_rq[write] to be the next one of the request Drq to be distributed in the write list of the scheduler Request, and finally add 1 to batching to end the request distribution process; (4.9) Judging whether there is a request in the write list of the scheduler, if not, then jump to step (4.11); if it exists, continue to judge whether there is a timed-out write request or the number of times the write request is starved has reached the upper limit, If the judgment result is true, then jump to step (4.12); otherwise, jump to step (4.11); (4.10) Judging whether there is a request in the write list of the scheduler, if there is, then jump to step (4.12); otherwise, there is no request to be distributed in the scheduler, and this request distribution process is ended; (4.11) Determine whether next_rq[read] exists, if it exists, jump to step (4.13); otherwise jump to step (4.14); (4.12) Set the number of times that the write request is starved to 0, and then judge whether there is a time-out write request or whether next_rq[write] is empty, if the judgment result is true, go to step (4.15); otherwise, go to step (4.16); (4.13) The request Drq to be distributed is set to next_rq[read], batching=0 is set, a read batch processing stage is started to be created, and the step (4.7) is jumped to; (4.14) the request Drq to be distributed is set to the first request in the scheduler read linked list, batching=0 is set, a read batch processing stage is started to be created, and the step (4.7) is jumped to; (4.15) the request Drq to be distributed is set to the first request in the scheduler write linked list, batching=0 is set, a write batch stage is started to be created, and the step (4.8) is jumped to; (4.16) Set the request Drq to be distributed to next_rq[write], set batching=0, start to create a write batch processing stage, and jump to step (4.8).