全部博文（183）
分类： LINUX
2010-02-05 16:02:38
AS:
The full name of this I/O scheduler is anticipatory scheduling. In a simple word, when it is the time to select which the next request to be dispatched, the I/O scheduler will make a decision whether it is worth to delay to dispatch the next request which has been selected because another next request might arrive soon and this request might be more worth to be dispatched than the next request which has been selected currently. For example, suppose there are two processes creating I/O requests concurrently, at any moment, the disk head can just stay at one position, let's suppose at this time the I/O scheduler is serving process A. It is usual that a process at first reads some data from disk, then waits for a moment, then reads again. The time during the two read operation is called deceptive idleness. Why the author used the word “deceptive”is that this process is not in the real state of idleness, because very soon, the process will create I/O requests at once. Let's go back to our example, suppose the disk head is serving process A. But a moment later, there is no requests from the process A, at the same time, process B is creating requests. The I/O scheduler should make decision now. Should the disk head move to serve process B at once or should the disk head stay for a moment to wait for additional requests from A? It is obvious that if the process A will create requests at once, the disk head will avoid unnecessary movement between A and B. And the shrink of disk movement between A and B will be decreased.
Above is the basic background of anticipatory scheduling. In Linux kernel, AS is based on DEADLINE. In another word, the basic design idea of AS is CSCAN, with the component of anticipatory.
So, there are also two queues like DEADLINE in AS. One is sorted queue, the other is expired queue( I use deadline queue when I describe DEADLINE). The basic principle of AS is the same with DEADLINE, whenever the I/O scheduler selects the requests to be dispatched, it first checks whether the request on the expired queue has expired, if yes, then dispatch this request at once. If no, the request on the sorted queue will be selected, then I/O scheduler will run a routine called as_can_anticipate to decide whether anticipation should do.
Let's discuss it in detail.
First, the I/O scheduler should get the next request to dispatch. But how to get the next request? Which request in the sorted queue should be the next request? The routine as_find_next_rq will do this job. In a simple word, the heuristic to get the next request is below: the next request should be the nearest request to the current disk head. In DEADLINE, nearest means the next request of the sorted queue, in AS, it is a little more complicated, the I/O scheduler will compare the left and right(or back and front) requests of the current one, if the distance between left and the current is smaller than the half distance between the right and current, the left request will be selected. The design idea behind this is very simple, in the original CSCAN, the disk head will move in the same direction, but in AS, the disk head has the chance to move backward.
Once the I/O scheduler has selected the request to be dispatched from the sorted queue, it is still not the time to dispatch. Then, AS will look at the expired queue to check whether the time of the first request has expired. As I have said, if it is, the request of the expired queue will be selected and dispatched at once. Here, let's suppose the time is not expired. Since the request has been selected, AS now will check whether the anticipation should be done. The routine as_can_anticipate will do this job. Thought I do not understand all of these conditions, I just list what I understand about them, maybe the best way is to follow the source code.
/*
there are some other tricks in the routine of as_can_anticipate, such as if the last request is write, anticipation will not be done. Here I just analysis the key part of this routine, actually, as_can_anticipate invokes the routine as_can_break_anticipation, in another word, if as_can_break_anticipation returns 1, which means the anticipation will not be done.
*/
static int as_can_break_anticipation(struct as_data *ad, struct request *rq)
{
struct io_context *ioc;
struct as_io_context *aic;
ioc = ad->io_context;
BUG_ON(!ioc);
spin_lock(&ioc->lock);
/*
this is what I understand of AS, if the current request is from the same process, anticipation will not be done, this request should be dispatched into device driver at once.
*/
if (rq && ioc == RQ_IOC(rq)) {
/* request from same process */
spin_unlock(&ioc->lock);
return 1;
}
/*
each time when a request is dispatched into device driver, ad->ioc_finished will be set to 0, when the request has been finished, and if the latest dispatched request is from the same process with this request, this value will be set to 1. I think we can simply understand it as when ad->ioc_finished equals 1, it means the previous requests from the process has been finished. So, this condition can be understood as if the anticipation time the process has been expired, the anticipation will not be done.
*/
if (ad->ioc_finished && as_antic_expired(ad)) {
/*
* In this situation status should really be FINISHED,
* however the timer hasn't had the chance to run yet.
*/
spin_unlock(&ioc->lock);
return 1;
}
/*
I am not sure what's the meaning of these codes, why is aic NULL? Is it because of the first request from the process?
*/
aic = ioc->aic;
if (!aic) {
spin_unlock(&ioc->lock);
return 0;
}
/*
aic->nr_queued means more than one request have been queued in AS' queue. Here, if the request is synchronize, there is at most one request in the queue for a process. Also, aic->nr_dispatched means more than one request have been dispatched into device driver and they are not finished yet.
What the anticipation wants to do is to wait the next request, since there have been more than one from a process in the queue, it is unnecessary to do anticipation any more.
*/
if (atomic_read(&aic->nr_queued) > 0) {
/* process has more requests queued */
spin_unlock(&ioc->lock);
return 1;
}
if (atomic_read(&aic->nr_dispatched) > 0) {
/* process has more requests dispatched */
spin_unlock(&ioc->lock);
return 1;
}
/*
If the request is sync and it is near the last request, anticipation will not be done.
*/
if (rq && rq_is_sync(rq) && as_close_req(ad, aic, rq)) {
/*
* Found a close request that is not one of ours.
*
* This makes close requests from another process update
* our IO history. Is generally useful when there are
* two or more cooperating processes working in the same
* area.
*/
/*
Here the AS updates ad->exit_prob and ad->exit_no_coop, as its definition, ad->exit_prob means the probability a task will exit while being waited on. ad->exit_no_coop means probability an exited task will not be part of a later cooperating request. Though I am not quiet sure about the deep meaning of this two parameters, I can use a very simple sentence to describe, if the chance that the process has been died is very high, it is worthless to wait.
*/
if (!test_bit(AS_TASK_RUNNING, &aic->state)) {
if (aic->ttime_samples == 0)
ad->exit_prob = (7*ad->exit_prob + 256)/8;
ad->exit_no_coop = (7*ad->exit_no_coop)/8;
}
as_update_iohist(ad, aic, rq);
spin_unlock(&ioc->lock);
return 1;
}
if (!test_bit(AS_TASK_RUNNING, &aic->state)) {
/* process anticipated on has exited */
if (aic->ttime_samples == 0)
ad->exit_prob = (7*ad->exit_prob + 256)/8;
if (ad->exit_no_coop > 128) {
spin_unlock(&ioc->lock);
return 1;
}
}
if (aic->ttime_samples == 0) {
if (ad->new_ttime_mean > ad->antic_expire) {
spin_unlock(&ioc->lock);
return 1;
}
if (ad->exit_prob * ad->exit_no_coop > 128*256) {
spin_unlock(&ioc->lock);
return 1;
}
} else if (aic->ttime_mean > ad->antic_expire) {
/* the process thinks too much between requests */
spin_unlock(&ioc->lock);
return 1;
}
spin_unlock(&ioc->lock);
return 0;
}
Even I list the source code above, I do not answer the question about when to do anticipation exactly. The first condition is thinktime. Thinktime means the time between two requests. If the previous request is being served in device driver while the next request has been decided to dispatch into device driver, thinktime would be 0. Please notice that the next request should not of course be the request from the same process, it might be near the current disk head while it belongs to another process. On the other hand, if the precious request has been served, the time difference between the previous request and the current request to be dispatched is the thinktime. AS use such mathematic formulations to calculate ttime_mean:
aic->ttime_samples = (7*aic->ttime_samples + 256) / 8;
aic->ttime_total = (7*aic->ttime_total + 256*ttime) / 8; // ttime is thinktime
aic->ttime_mean = (aic->ttime_total + 128) / aic->ttime_samples;
It is obvious to notice that if thinktime is large, ttime_mean will be large, if ttime_mean is larger than antic_expire which is the maximum time of anticipation, it means no anticipation should be done. Actually, you can understand it in this way, if the process is I/O insensitive, the interval time between requests from the process is very small, even 0(if the requests are sync, 0 is almost impossible), as a result, think_time will be small, it will always be smaller than antic_expire, which means it is worth to be waited.
The other element to decide whether it is worth to be waited is seek_mean. As we know, locality I/O accession is a default property of process, but this is not always true, especially for random I/O. So, the AS should always consider the distance between the two requests. If the distance of the two requests is small, it might be worth to wait for the next request when the previous request has been served. The mathematic formulation is below:
aic->seek_samples = (7*aic->seek_samples + 256) / 8;
aic->seek_total = (7*aic->seek_total + (u64)256*sdist) / 8;
total = aic->seek_total + (aic->seek_samples/2);
do_div(total, aic->seek_samples);
aic->seek_mean = (sector_t)total;
the mathematic model to calculate seek_mean and ttime_mean is the same. As you may notice I don't explain a routine as_close_req in the source codes above, actually, if the distance between two requests is smaller than seek_mean, it means these two requests are near to each other. Of course, there is a limitation for seek_mean, you can find it yourself in source code.
As considers the thinktime, seek distance the exit probability of this process to evaluate whether it is worth to be waited. I think these 3 elements, especially the first two is the key component of the algorithm AS. Each time when a new request is added to the queue, ttime_mean and seek_mean of the process is updated. At the same time, the AS will check whether the anticipation should be broken if there it is. In a simple word, whenever there is a new request, the AS should check whether this one is the right request being waited.
