CFQ调度算法

Question

CFQ算法根据发出请求的进程的I/O优先级使用一组有序队列。这意味着优先级进程有一个队列，比如说，1，优先级2的另一个队列，等等。

据我所知，该算法接收每个队列的第一个请求，对它们进行排序(以避免不必要的头部移动)，并将它们放入调度队列中以供处理。但是，由于单个请求可以读取许多块(不一定是连续的)，这类请求怎么可能呢？我是说，如果我有：

Request1 = [1,2,345,6,423] 

和

Request2 = [3,4,2344,664]

作为a，b，c是块a、b和c的列表，请求1和2是如何放置到调度队列中的？如您所见，它们有一个非空的交集(例如，块6位于块3和4之后)

另一件我不明白的事情是，由于一个请求可以有多个块可读，其中会有什么样的调度？FCFS？或者是点菜？

例如，假设我们有一个请求，其中包含以下要读取的块列表：

[1,23,5,76,3]

算法将如何处理这一问题？

FCFS：

[1,23,5,76,3]

或者通过对块进行排序：

[1,3,4,23,76]

也许我不懂算法，找不到足够的文档。如果有人有更详细解释的链接，请给我参考。

Answer 1

我知道，CFQ没有安排单轨请求，而是为一些请求安排时间。来自IA64wiki的报价

CFQ调度程序的目标是在争夺磁盘访问权限的进程之间公平分配磁盘时间。此外，它还使用预期和截止日期来提高性能，并尝试绑定延迟。 发出I/O的每个进程都有一个时间段，在此期间，它对同步请求具有独占访问权限。时间切片由两个参数限定:由进程的I/O优先级调整的slice_sync给出每个片的长度(毫秒)；quantum给出可以发出的请求数。 所有进程共享一组异步I/O的17个队列，每个有效I/O优先级共享一个队列。每个队列根据slice_async (按优先级调整)获得一个时间片，并且队列被处理为循环。 在每个切片中，合并请求(前请求和后请求)，并根据扫描发出请求，允许向后查找back_seek_max，但与前向查找相比，back_seek_penalty有偏见。CFQ将在片内等待一个进程发出更多的I/O，这允许预期，并在流程发出突发I/O时提高公平性；但通常情况下，它会降低性能。