Linux下实现电梯算法（linux电梯算法）
电梯算法（Elevator Algorithm）是一种计算机中磁盘调度时的非常重要的算法，应用范围广泛，现在普遍用于Linux系统的虚拟存储器管理。电梯算法可以有效地改善磁盘I/O性能，减少磁盘I/O中的空转，提高磁盘的I/O效率。
电梯算法的基本思想是使当前的磁头按照设定的方向（通常是上升或下降）前进，当它移动到下一个I/O定位点时，请求此I/O定位点，直至完成所有I/O操作后，再令磁头返回到磁盘上初始位置，重新开始一轮循环。
电梯算法可以简单地通过在磁头IDLE时增加时间增加磁头运作效率，提高磁头切换事件个数。在Linux内核上，磁盘I/O实现了电梯算法，可以通过检查和修改如下代码实现：
/* 电梯算法 – 当前请求的I/O定位点越近，其优先级越大 */
int elevator_direction = 1;
struct request *elevator_previous_request = NULL; //定义一个elevator_previous_request指向一个struct request类型的指针变量，用于存储上次I/O请求
struct request *cmp_request(struct request *a, struct request *b)
{
if(a->sector == b->sector)
return a;
else if ( elevator_direction == 1 && a->sector sector )
return a;
else if ( elevator_direction == -1 && a->sector > b->sector )
return a;
else
return b;
}
/* 电梯算法 – 当前请求的I/O定位点越近，其优先级越大 */
bool elevator_pose(struct request *req)
{
if ( elevator_previous_request == NULL ) {
elevator_previous_request = req;
elevator_direction = 1;
return true;
}
struct request *prev_head = cmp_request( elevator_previous_request, req );
if ( elevator_previous_request == prev_head) {
if (req->sector > elevator_previous_request->sector )
elevator_direction = 1;
else
elevator_direction = -1;
}
elevator_previous_request = req;
return true;
}
在Linux内核中，电梯算法被实现为一个磁盘调度程序，其目的是根据磁盘I/O定位点优先级来调度磁盘请求，及时完成I/O操作，同时提高磁盘I/O性能。用电梯算法来管理虚拟存储器，可以尽可能有效地使用磁盘访问，从而提高系统性能。
