1. Johngo学长首页
  2. 技术点详细复盘专题
  3. Python

Linux Block模块之deadline调度算法代码解析

• Python • 阅读 23

1 总体说明

Deadline调度器对一个请求的多方面特性进行权衡来进行调度，以期望既能满足块设备扇区的顺序访问又能兼顾到一个请求不会在队列中等待太久导致饿死。Deadline调度器为了兼顾这两个方面，通过红黑树来对请求按起始扇区序号进行排序，称为 sort_list ，通过 fifo 对请求按它们的生成时间进行排序，称为 fifo_list 。

batching – 每当确定了一个传输方向（读/写），那么将会从相应的 sort_list 中将一批连续请求 dispatch 到 request_queue 的请求队列里，具体的数目由 fifo_batch（default-16） 来确定。

总体来讲，deadline算法对request进行了优先权控制调度，主要表现在如下几个方面：

2 数据结构

struct deadline_data {
    /*
     * sort_list红黑树的根，用于对IO请求根据起始扇区进行排序
     * 这里有两棵树，一棵读请求树，一棵写请求树
     */
    struct rb_root sort_list[2];
    /* 按照到期时间排列的先入先出队列FIFO */
    struct list_head fifo_list[2];

    /*
     * 记录批量处理请求的下一个读/写请求
     */
    struct request *next_rq[2];
    /*
     * 当前的发送数，当batching小于fifo_batch时，
     * 请求会连续的发送，大于或等于16时就会启动下一轮dispatch
     */
    unsigned int batching;
    sector_t last_sector;
    /* 写饥饿的次数 */
    unsigned int starved;

    /*
     * 这个数组分别存储了读/写请求的期限
     * 读请求为500ms，写请求为5s
     * 即使写请求超时也不一定立即得到相应，而是等到读请求当前的批次
     * 大于写请求饥饿线的时候才去处理写请求
     */
    int fifo_expire[2];
    /* 批量发送的最大值 */
    int fifo_batch;
    /* 写请求饥饿线，默认为2 */
    int writes_starved;
    /* 表示能否进行前向合并的检查 */
    int front_merges;
};

3 一般流程说明

调用 deadline_add_request() 添加请求，代码执行流程如下：

static void
deadline_add_request(struct request_queue *q, struct request *rq)
{
    struct deadline_data *dd = q->elevator->elevator_data;
    /* 获取请求的方向，读还是写 */
    const int data_dir = rq_data_dir(rq);

    /* 以请求的起始扇区为键值插入到红黑树中 */
    deadline_add_rq_rb(dd, rq);

    /*
     * 设置超时时间，这个请求在超时时间 jiffies + dd->fifo_expire[data_dir]
     * 必须得到响应
     */
    rq->fifo_time = jiffies + dd->fifo_expire[data_dir];
    /* 将rq加入fifo_list */
    list_add_tail(&rq->queuelist, &dd->fifo_list[data_dir]);
}

static void
deadline_add_rq_rb(struct deadline_data *dd, struct request *rq)
{
    /* 获取sort_list中指向根节点的指针root */
    struct rb_root *root = deadline_rb_root(dd, rq);

    /* 将请求插入到红黑树中 */
    elv_rb_add(root, rq);
}

调用 deadline_merge() 对请求进行合并，elevator会自己做后向合并，并且后向合并优先于前向合并

static int
deadline_merge(struct request_queue *q, struct request **req, struct bio *bio)
{
    struct deadline_data *dd = q->elevator->elevator_data;
    struct request *__rq;
    int ret;

    /* 如果可以向前合并 */
    if (dd->front_merges) {
        sector_t sector = bio_end_sector(bio);
        /* 如果能找到一个请求，它的起始扇区号和bio的结束扇区号相同即连续的 */
        __rq = elv_rb_find(&dd->sort_list[bio_data_dir(bio)], sector);
        if (__rq) {
            BUG_ON(sector != blk_rq_pos(__rq));
            /* 如果找到则进行合并 */
            if (elv_bio_merge_ok(__rq, bio)) {
                ret = ELEVATOR_FRONT_MERGE;
                goto out;
            }
        }
    }

    return ELEVATOR_NO_MERGE;
out:
    *req = __rq;
    return ret;
}

如果做了前向合并，调用 deadline_merged_request() 进行处理，因为前向合并使得请求的起始扇区发生变化，所以相应的处理就是从 sort_list 中先删除再重新加回

static void deadline_merged_request(struct request_queue *q,
                    struct request *req, int type)
{
    struct deadline_data *dd = q->elevator->elevator_data;

    /* 把合并了的请求从sort_list删除再加入 */
    if (type == ELEVATOR_FRONT_MERGE) {
        elv_rb_del(deadline_rb_root(dd, req), req);
        deadline_add_rq_rb(dd, req);
    }
}

合并后，调用 deadline_merged_requests() 做合并后的处理

static void
deadline_merged_requests(struct request_queue *q, struct request *req,
             struct request *next)
{
    if (!list_empty(&req->queuelist) && !list_empty(&next->queuelist)) {
        /* 如果next的期限小于req */
        if (time_before(next->fifo_time, req->fifo_time)) {
            /* 这个queuelist实际上就是真正发给设备驱动程序的队列，处理完了的队列 */
            list_move(&req->queuelist, &next->queuelist);
            /* 因为是next比req要先响应，合并完了肯定要以先响应的为准 */
            req->fifo_time = next->fifo_time;
        }
    }

    /* 从fifo_list和sort_list删除next */
    deadline_remove_request(q, next);
}

最后，调用 deadline_dispatch_requests() 将请求派发到系统的 request_queue 队列中

static int deadline_dispatch_requests(struct request_queue *q, int force)
{
    struct deadline_data *dd = q->elevator->elevator_data;
    const int reads = !list_empty(&dd->fifo_list[READ]);
    const int writes = !list_empty(&dd->fifo_list[WRITE]);
    struct request *rq;
    int data_dir;

    /* 两个方向上的next_rq同时只能有一个为真 */
    if (dd->next_rq[WRITE])
        rq = dd->next_rq[WRITE];
    else
        rq = dd->next_rq[READ];

    /* 如果有rq并且批量disaptch未到上限，则直接进行dispatch */
    if (rq && dd->batching < dd->fifo_batch)
        /* we have a next request are still entitled to batch */
        goto dispatch_request;

    if (reads) {
        BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[READ]));
        /* 触发写请求饥饿线，必须处理写请求了 */
        if (writes && (dd->starved++ >= dd->writes_starved))
            goto dispatch_writes;

        data_dir = READ;

        goto dispatch_find_request;
    }

    if (writes) {
dispatch_writes:
        BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[WRITE]));
        dd->starved = 0;
        data_dir = WRITE;
        goto dispatch_find_request;
    }

    return 0;

dispatch_find_request:
    /*
     * 我们不是处理批量请求，而是选择数据方向上最优的请求
     */

    /*
     * 如果fifo_list有超时或者下一个请求的方向变了，就去
     * fifo_list去request，然后还得执行下面的dispatch_request
     */

    /*
     * 该请求方向存在即将饿死的请求，或不存在批量处理的请求，
     * 则先从FIFO队列头取一个请求
     */
    if (deadline_check_fifo(dd, data_dir) || !dd->next_rq[data_dir]) {
        rq = rq_entry_fifo(dd->fifo_list[data_dir].next);
    } else {
        /*
         * 为什么这里可以直接从fifo_list取而不是sort_list，因为
         * 最终都需要通过rq的rb_node到sort_list找
         */
        /* 按照扇区顺序处理请求 */
        rq = dd->next_rq[data_dir];
    }

    /* 启动新一批请求dispatch */
    dd->batching = 0;

dispatch_request:
    /*
     * rq is the selected appropriate request.
     */
    dd->batching++;
    /*
     * 从fifo_list和sort_list中删除，再加入req->queuelist中，这里就从
     * IO调度层离开了，移动一个请求到请求队列的派发队列
     */
    deadline_move_request(dd, rq);

    return 1;
}

Original: https://www.cnblogs.com/yuzqprog/p/16795361.html
Author: 将信_且信
Title: Linux Block模块之deadline调度算法代码解析

相关阅读

Title: Pandas笔记

传送门

简介

  • Pandas 名字衍生自术语 “panel data”（面板数据）和 “Python data analysis”（Python 数据分析）。
  • Pandas 一个强大的分析结构化数据的工具集，基础是 Numpy（提供高性能的矩阵运算）。
  • Pandas 可以从各种文件格式比如 CSV、JSON、SQL、Microsoft Excel 导入数据。
  • Pandas 可以对各种数据进行运算操作，比如归并、再成形、选择，还有数据清洗和数据加工特征。
  • Pandas 广泛应用在学术、金融、统计学等各个数据分析领域。

Pandas 应用

  • Pandas 的主要数据结构是 Series （一维数据）与 DataFrame（二维数据）

Series

Pandas Series 类似表格中等一个列（column），类似于一维数组，可以保存任何数据类型 Series 由索引（index）和列组成，函数如下：

pandas.Series( data, index, dtype, name, copy)
参数说明：

  • data：一组数据(ndarray 类型)。
  • index：数据索引标签，如果不指定，默认从 0 开始。
  • dtype：数据类型，默认会自己判断。
  • name：设置名称。
  • copy：拷贝数据，默认为 False。
    Linux Block模块之deadline调度算法代码解析

Linux Block模块之deadline调度算法代码解析Linux Block模块之deadline调度算法代码解析
Linux Block模块之deadline调度算法代码解析

; DataFrame

DataFrame的创建，读写，插入和删除
loc & iloc

apply()

  • pandas的apply函数是自动根据function遍历每一个数据，然后返回一个数据结构为Series的结果
  • 传送门

DataFrame 是一个表格型的数据结构，它含有一组有序的列，每列可以是不同的值类型（数值、字符串、布尔型值）。DataFrame 既有行索引也有列索引，它可以被看做由 Series 组成的字典（共同用一个索引）。

Linux Block模块之deadline调度算法代码解析Linux Block模块之deadline调度算法代码解析Linux Block模块之deadline调度算法代码解析

Linux Block模块之deadline调度算法代码解析
Linux Block模块之deadline调度算法代码解析Linux Block模块之deadline调度算法代码解析

loc

Linux Block模块之deadline调度算法代码解析
Linux Block模块之deadline调度算法代码解析
Linux Block模块之deadline调度算法代码解析

; CSV

它的文件以纯文本形式存储表格数据(数字和文本)。

[En]

Its files store tabular data (numbers and text) in plain text.

Linux Block模块之deadline调度算法代码解析
Linux Block模块之deadline调度算法代码解析
数据处理
head()
  • head( n ) 方法用于读取前面的 n 行，如果不填参数 n ，默认返回 5 行。

tail()

  • tail( n ) 方法用于读取尾部的 n 行，如果不填参数 n ，默认返回 5 行，空行各个字段的值返回 NaN。

info()

  • info() 方法返回表格的一些基本信息
    Linux Block模块之deadline调度算法代码解析

JSON

JSON Object Notation，JavaScript 对象表示法），是存储和交换文本信息的语法，类似 XML。

JSON 比 XML 更小、更快，更易解析

Original: https://blog.csdn.net/weixin_41413511/article/details/117620875
Author: 王蒟蒻
Title: Pandas笔记

原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/363431/

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
0

【自取】最近整理的，有需要可以领取学习：



Linux核心资料大放送~

全栈面试题汇总（持续更新&可下载）

一个提高学习100%效率的工具！

【超详细】深度学习面试题目！

LeetCode Python刷题答案下载！

LeetCode Java版刷题答案下载！

LeetCode C++ 版本，抓紧保存！

LeetCode GO语言 刷题答案下载！

大家都在看

最近整理资源【免费获取】：   👉 程序员最新必读书单  | 👏 互联网各方向面试题下载 | ✌️计算机核心资源汇总