读 Pintos 内核源码(一): 内核级跑分

June 7, 2015 | 02:42

什么是 Pintos

我是在搜索操作系统的公开课的时候接触 Pintos 的, 这是斯坦福 CS140 这门课上的实验作业用到的一个操作系统框架. 这个操作系统框架并不是一个完整实现的操作系统, 需要我们去填充他的功能, 比如我们要为他编写线程优先级算法用来更合理的抢占CPU时间片, 或者为他编写用户应用程序接口, 或者为他编写虚拟内存管理模块, 以及文件系统.

跑分

说跑分其实是夸张了. 这里写的只是稍微类似跑分的一种东西: 想知道在 cpu 最小的一个周期里面, 执行了多少个语句.

在 Pintos 中, time.c 文件提供了一个全局变量 tick (signed long long 类型), 这个变量存储是开机到现在总共流逝了多少个 cpu 最小时钟周期的一个统计.

现在我们需要通过 tick 以及 C 语言编程, 来获取在一个 tick 内本机的 cpu 可以执行轮空循环. 在跑分的过程中, 操作系统仅仅开启了单线程, 没有别的任何任务在运行. 这样的跑分在系统已经完成加载之后是无法进行的.

 

跑分流程

跑分分为三个部分:

  1. 等待当前 tick 结束, 以保证跑分从一个 tick 的开头开始;
  2. 进行空循环阶段;
  3. 空循环结束, 得出跑分结果.

以上思路存在一个问题, 就是如何得出跑分结果. 如果使用一个 count++ 来统计循环了多少轮, 那么这就不是一个空循环, 得出来的结果有一个常量系数的误差.

在经典的二分算法中, 总是不停的尝试可能的值, 然后对值进行验证, 如果验证通过, 那么二分结束. Pintos 借鉴了其中的先尝试后验证的思路, 并且所尝试的值呈指数级增长, 与二分算法有异曲同工之妙.

  1. 等待当前 tick 结束, 以保证跑分从一个 tick 的开头开始;
  2. 记录新的 tick 的值;
  3. 进行 x 遍空循环;
  4. 查看当前 tick 值是否发生改变;
  5. 如果没有发生改变, 则将 x 乘以 2, 调到第 3 步;
  6. 得出的结果是, 一个 tick 可以执行的空循环次数的范围是 [x/2, x).

 

源代码

反复乘2进行尝试验证的代码如下

 

保证每次尝试处于完整的一个 tick 下的代码如下:

 

优化壁垒

现在的编译器是越来越聪明了, 如果你写了一个空循环, 他能知道这是在做无用功, 然后帮你把空循环删掉; 如果你按顺序写的几行语句之间没有关系, 不需要遵循一个先后顺序, 那么他将会乱序执行来达到更快的速度.

为什么不按原本的顺序来执行语句能够更快呢? 因为 CPU 内部结构复杂, 有时候 CPU 的某些部分正忙, 某些部分正闲. 而乱序执行技术根据各单元电路的空闲状态和各指令能否提前执行的具体情况分析后, 将可以提前执行的指令立即发送给相应电路执行, 就能达到提高程序执行速度的作用.

但是对空循环的优化以及乱序执行技术并非什么时候都很棒, 有时候会给我们带来麻烦, 比如我们用空循环来跑分的时候, 以及用标记变量来为多线程服务的时候.

在 Pintos 中, 可以通过 barrier() 来设置一个优化壁垒, 使得编译器不进行上述优化. 这就是上面的代码里面的空循环为什么有一个 barrier() 的原因.

 

( 转载请注明: Jecvay Notes )

多达 7 条吐槽

  • hai
    2015/06/10

    久不久来大神的网站逛一逛

  • zhang
    2015/06/13

    支持学长啊,我现在是西工大大二学生,假期申请了谢磊教授的语音识别实验室学习,考试月闲就一直在看博主的爬虫教程,收获良多,十分感谢

    • 2015/06/13

      好厉害! 你是哪院的?

      • zhang
        2015/06/14

        计算机学院,学长应该是ACM的吧,膜拜啊,没进ACM,学分绩也不高,只能多学学专业知识了

        • 2015/07/24

          小哥下学期大三吗?有没有兴趣搞点小新闻了?

  • 2015/09/22

    你们这个多说批量评论系统不错呀, 我关了网站的时候都能绕过博客直接添加评论.

  • any
    2016/09/06

    a=1

说几句