• CPU 虚拟化被分为两篇,此篇是第一篇,Mechanism
  • 今天阅读到项目代码时候,涉及到了 Python 协程的概念,由于才疏学浅一时半会儿未能参透协程的实际意义。查阅了很多资料,都是和线程、进程对照着一起阐述,理解起来实在有难度,有了比较浅薄的了解之后决定还是先继续了解进程这一块的知识。
  • 威斯康辛州大学操作系统书籍《Operating Systems: Three Easy Pieces》读书笔记系列之 Virtulization(虚拟化)。本篇为虚拟化技术的基础篇系列第二篇(Mechanism and Policy),机制和策略。(结合第一篇给出的虚拟化两层实现)
  • CPU 虚拟化被分为两篇,此篇是第一篇,Mechanism

Chapter Index

  • TODO

Mechanism: Limited Direct Execution

  • 实现 CPU 虚拟化的主要思想为运行一个进程一段时间,然后运行另一个进程,轮流执行。即时分共享的方式来利用 CPU。这样的方式也就存在着一列问题:
    • Performance: 如何在不引入特别多的开销的情况实现虚拟化?
    • Control: 当持有 CPU 的执行(控制)权时,如何高效运行当前进程?
  • CRUX:如何高效、可控地虚拟化 CPU?

Basic Technique: Limited Direct Execution

  • Direct Execution:是指在 CPU 上直接运行程序。即当操作系统希望启动程序运行时,会在进程列表中为其创建一个进程条目,为其分配一些内存,将程序代码(从磁盘)加载到内存中,找到入口点(main()函数或类似的),跳转到那里,并开始运行用户的代码。协议如下:
    20200817223139
  • 这种直接的方式衍生了一些问题:
    • 操作系统如何保证这个程序只做规定范围内的事情(即我们在代码里描述的事情),还要很高效地去执行?
    • 在程序运行过程中,操作系统如何暂停这个程序切换到另一个进程上去执行,从而实现时分复用 CPU?
  • 因此需要为这种直接执行的机制引入一定的限制

Problem #1: Restricted Operations

  • 上述机制的优点在于执行很快,因为直接在 CPU 上运行。但是如果进程希望执行一些其他受限的操作,比如发起磁盘 I/O 或者申请更多的内存和 CPU 等,则需要进行一定的限制和处理。
  • 针对 I/O 类型的操作,如果放任进程做任何事情,就无法构建许多我们想要构建的系统。比如构建一个带权限控制和访问的文件系统。针对进程的 I/O 操作需要进行权限的校验,放任进程的话就可能导致进程读写整个磁盘,就完全失去了权限的保护。
  • 实际上采用的方法是引入一个新的处理器模式,即 User Mode。该模式下的代码运行中会受到限制。比如,在该模式下,进程不能发起 I/O 请求,如果发起将引发异常然后操作系统可能终止进程。与用户模式对应的模式叫做 Kernel Mode,操作系统(或内核)就以这种模式运行,该模式下,运行的代码可以做任何事情,即该模式下无限制。
  • 如果进程确实需要执行某些限制的指令,譬如发起 I/O,那么此时就引入了新的概念 System call。系统调用其实是内核向用户暴露的某些关键功能,譬如文件系统的相关操作,进程的创建销毁通信等,内存的分配回收等。程序为了执行系统调用,需要首先执行 trap 指令,该指令将进入到内核中并将权限级别提升到内核模式,一旦在内核中,程序就可以执行想要执行的受限制的操作,当执行结束后,操作系统会调用 return-from-trap 指令,回到发起调用的用户程序并将权限级别调整回用户模式。
  • 在执行 trap 指令时有一些硬件上的细节需要注意,即为了保证之后操作系统发起 return-from-trap 指令后能够正确地回到原来的程序,需要保存原有的用户程序的寄存器数据,即原有进程的上下文。在 x86 上,处理器将会把 PC,flags 以及其他寄存器压栈到每个进程对应的内核栈上,return from trap 的时候才出栈恢复用户态下的程序执行。其他平台可能使用了不同的实现,但基本原理大体如此。
  • trap 指令如何知道运行操作系统中哪部分的代码?借助系统启动时构建的 trap table,由于启动时处于内核态,很容易配置机器硬件的行为,操作系统需要在 trap table 中维护当发生某些异常事件时对应的硬件需要执行什么样的操作,从而告诉硬件这些 trap handlers 的位置,然后硬件会记住对应的处理程序的位置直到下次系统启动。为了指定准确的系统调用,通常为每个系统调用分配一个系统调用号。因此,用户代码负责将所需的系统调用号放入寄存器或堆栈上的指定位置;当操作系统在trap handler 中处理系统调用时,检查这个数字,确保它是有效的,如果是,就执行相应的代码。这种间接性可以作为一种保护形式;用户代码不能指定要跳转到的确切地址,但必须通过号码请求特定的服务。
  • 如下就是 Limited Direct Execution 的协议,被分成了两个阶段。
    • 第一阶段即启动阶段,初始化 trap table,每个硬件对应的记住系统调用处理程序的位置。
    • 第二阶段即进程运行阶段,首先需要设置一些内容,分配内存等操作,返回用户态执行程序,当程序需要进行系统调用的时候再次进入内核态,执行对应的系统调用处理程序,执行完后返回主程序,直到程序执行完再次进入内核态释放内存。
      20200818101241

Problem #2: Switching Between Processes

  • 假设只有一个 CPU,如果一个进程在运行,那就意味着操作系统此时不在运行,那这时候操作系统就不能做很多事情,也就引出了关键问题 CRUX: 操作系统如何重新获得控制权以便在进程间切换?

A Cooperative Approach: Wait For System Calls

  • 早期的一些操作系统采用的方式是协作式,等待系统调用。即相信进程会合理运行,并且假设进程运行太长时间的话会定时地放弃 CPU 的使用并由操作系统决定运行别的进程。
  • 友好的进程如何放弃 CPU 的执行权?大多数进程通常都是通过系统调用将 CPU 的执行权转给操作系统,比如打开文件后读取文件,或者向另一台机器发送数据,又或者创建新进程,这样的系统通常显式地包含了一个 yield 系统调用,它什么都不干,只是将控制权交给操作系统,以便系统可以运行其他进程。
  • 如果应用程序进行了一些非法的操作也会把 CPU 的控制权转移给操作系统,比如除以 0 或者访问不能被访问的内存空间,都会导致 trap 的执行,然后操作系统就获取到了 CPU 的执行权,并可能终止这样的违规进程。
  • 因此,在协作调度系统中,操作系统通过等待系统调用或某种非法操作的发生来重新获得对 CPU 的控制。但是这样太过理想,即对进程太过自信,假设一个进程有很多问题,且是个死循环,但是从不进行系统调用,这个时候操作系统就永远都拿不到 CPU 了。

A Non-Cooperative Approach: The OS Takes Control

  • 如上所述,如果没有硬件的额外帮助,进程不进行系统调用,也不出错的话,CPU 控制权根本无法交给操作系统,要是程序死循环执行,就只能重启了。所以这时候的 CRUX:即使进程不协作,操作系统如何获得 CPU 的控制权?操作系统可以做什么来确保流氓进程不会占用机器?
  • timer interrupt 时钟中断是指每隔几毫秒发生一次中断,产生中断时当前正在运行的进程停止,执行操作系统中预先定义的中断处理程序,此时操作系统重新获得了 CPU 的执行权,这时候就可按照逻辑执行,譬如停止当前进程,运行另一个进程。
  • 时钟中断程序和前面讨论的系统调用一样,需要在系统启动时就通知硬件哪些代码在发生中断时执行。除此以外系统还需要启动时钟,从而保证操作系统最终能够获取到 CPU 的执行权。时钟当然也可以关闭。时钟的启动和关闭都是一些权限极高的操作。
  • 中断操作发生时对硬件也会有一定的要求,跟系统调用时对硬件的要求类似,即需要保存原有的用户程序所对应的寄存器数据,也就是所谓的进程上下文。

Saving and Restoring Context

  • 既然操作系统已经重新获得了控制权,无论是通过系统调用协作,还是通过时钟中断更强制执行,都必须决定:是继续运行当前正在运行的进程,还是切换到另一个进程。这个决定是由调度程序(scheduler)做出的,它是操作系统的一部分,即调度策略。
  • 进程的切换其实就是我们常常说的上下文切换 context switch,就是指操作系统要做的就是为当前正在执行的进程保存一些寄存器的值(例如,到它的内核栈),并为即将执行的进程恢复一些寄存器的值(从它的内核栈)。这样一来,操作系统就可以确保最后执行从陷阱返回指令时,不是返回到之前运行的进程,而是继续执行另一个进程。
  • 为了保存当前正在运行的进程的上下文,操作系统会执行一些底层汇编代码,来保存通用寄存器、程序计数器,以及当前正在运行的进程的内核栈指针,然后恢复寄存器、程序计数器,并切换内核栈,供即将运行的进程使用。通过切换栈,内核在进入切换代码调用时,是一个进程(被中断的进程)的上下文,在返回时,是另一进程(即将执行的进程)的上下文。当操作系统最终执行从return-from-trap 指令时,即将执行的进程变成了当前运行的进程。至此上下文切换完成。
  • 如下所示,进程 A 运行时被中断时钟中断,硬件保存寄存器数据到内核栈中,进入内核模式,时钟中断处理程序中,操作系统决定从正在运行的进程 A 切换到进程 B。此时,它调用 switch()例程,该例程仔细保存当前寄存器的值(保存到 A 的进程结构),恢复寄存器进程 B(从它的进程结构),然后切换上下文(switch context),具体来说是通过改变栈指针来使用 B 的内核栈(而不是 A 的)。最后,操作系统从 trap 返回,恢复 B 的寄存器并开始运行它。
  • 图中涉及到了两种类型的寄存器的保存和恢复。
    • 第一种是时钟中断时,硬件隐式地保存了 user registers 到进程的内核栈中
    • 第二种是内核中上下文切换的时候,操作系统显式地保存了 kernel registers 到进程的内存数据结构中
      20200818111835
  • 如下给出了 xv6 的上下文切换代码
1 # void swtch(struct context **old, struct context *new);
2 #
3 # Save current register context in old
4 # and then load register context from new.
5 .globl swtch
6 swtch:
7   # Save old registers
8   movl 4(%esp), %eax # put old ptr into eax
9   popl 0(%eax) # save the old IP
10  movl %esp, 4(%eax) # and stack
11  movl %ebx, 8(%eax) # and other registers
12  movl %ecx, 12(%eax)
13  movl %edx, 16(%eax)
14  movl %esi, 20(%eax)
15  movl %edi, 24(%eax)
16  movl %ebp, 28(%eax)
17
18  # Load new registers
19  movl 4(%esp), %eax # put new ptr into eax
20  movl 28(%eax), %ebp # restore other registers
21  movl 24(%eax), %edi
22  movl 20(%eax), %esi
23  movl 16(%eax), %edx
24  movl 12(%eax), %ecx
25  movl 8(%eax), %ebx
26  movl 4(%eax), %esp # stack is switched here
27  pushl 0(%eax) # return addr put in place
28  ret # finally return into new ctxt

Worried About Concurrency?

  • CRUX:在系统调用期间发生了时钟中断的话会怎么样?以及在处理一个中断的时候发生了另一个中断又会怎么样?
  • 具体的细节会在并发部分进行详细阐释,简单地讲 操作系统会在中断期间禁止中断,即保证在一个中断处理过程中不会交出 CPU,但是需要保证其他中断不会因为等待时间过长而丢失。除此以外还有一些加锁的方案,以保护共享的数据结构的并发访问。

Summary

  • limited direct execution:让你想运行的程序在 CPU 上运行,但首先确保设置好硬件,以便在没有操作系统帮助的情况下限制进程可以执行的操作。
  • 操作系统会在启动时加载 trap 处理程序并启动时钟中断,仅在受限模式下运行进程,从而保证进程高效执行,只有在需要执行高级别的操作如系统调用或者占用 CPU 时间过长的时候,才会由操作系统接管 CPU 进行干预。