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

什么是 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进行尝试验证的代码如下

/* Calibrates loops_per_tick, used to implement brief delays. */
void
timer_calibrate (void)
{
  unsigned high_bit, test_bit;

  ASSERT (intr_get_level () == INTR_ON);
  printf ("Calibrating timer...  ");

  /* Approximate loops_per_tick as the largest power-of-two
     still less than one timer tick. */
  loops_per_tick = 1u << 10;
  while (!too_many_loops (loops_per_tick << 1))
    {
      loops_per_tick <<= 1;
      ASSERT (loops_per_tick != 0);
    }

  /* Refine the next 8 bits of loops_per_tick. */
  high_bit = loops_per_tick;
  for (test_bit = high_bit >> 1; test_bit != high_bit >> 10; test_bit >>= 1)
    if (!too_many_loops (high_bit | test_bit))
      loops_per_tick |= test_bit;

  printf ("%'"PRIu64" loops/s.\n", (uint64_t) loops_per_tick * TIMER_FREQ);
}

 

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

/* Returns true if LOOPS iterations waits for more than one timer
   tick, otherwise false. */
static bool
too_many_loops (unsigned loops)
{
  /* Wait for a timer tick. */
  int64_t start = ticks;
  while (ticks == start)
    barrier ();

  /* Run LOOPS loops. */
  start = ticks;
  busy_wait (loops);

  /* If the tick count changed, we iterated too long. */
  barrier ();
  return start != ticks;
}

 

优化壁垒

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

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

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

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

/* Optimization barrier.

   The compiler will not reorder operations across an
   optimization barrier.  See "Optimization Barriers" in the
   reference guide for more information.*/
#define barrier() asm volatile ("" : : : "memory")

 

本文链接

回复