操作系统复习:虚拟化部分

The Abstraction: The Process

如果说在操作系统哪个抽象是最重要的,我肯定会回答:进程。进程就是对运行着的程序的抽象。程序本身就是在磁盘中躺着,有了操作系统,才让这些在磁盘中的字节变得鲜活了起来。

通过时间片分享(time sharing)技术,可以让多个进程轮流执行,每个进程就好像拥有一个独立的虚拟CPU一样。

为了能够实现CPU虚拟化,OS需要同时使用低级别的机制(mechanisms)和一些高级别的策略(policies)。

The Abstraction: A Process

要彻底理解进程是什么,我们就需要理解当程序运行的时候,它可以更新或者读取什么东西?

第一个显然是内存,指令在内存里,程序需要的数据也在内存里,所以进程包含了一个叫地址空间(address space)的东西。

第二个是寄存器,因为很多指令都需要显式修改寄存器的值。寄存器包含程序计数器(program counter,有时候也叫做指令指针instruction pointer),栈指针以及栈帧指针。

第三个是程序需要写东西回磁盘,所以需要进行IO,自然包括当前进程打开的文件列表。

进程API

本章不具体讨论这些api,只是概括性了解一下。

  • create:操作系统必须要有api能够创建出新进程。当你在shell中敲命令或者是在桌面程序中双击的时候,其实就是对应的进程的创建。
  • destory:进程执行完成后一般会自己关闭,当然用户也可以强行关闭。
  • wait:进程有时候需要等待别的进程。
  • Miscellaneous Control:杂项控制,比如操作系统有的时候需要暂停某个进程
  • status:还需要有一些接口能够得着进程的状态。

进程创建

那么,是如何把磁盘中的程序弄到内存中变成进程的呢?首先需要把磁盘中的程序,load它的代码段和程度段到内存,即指定的地址空间中。在早期操作系统中,是把程序整个放到内存中的,而现在的操作系统是懒加载,即只有在需要的时候才放入内存。

放入内存之后,就需要为栈分配空间,为堆分配空间(malloc分配的是堆空间),并且堆空间会随着程序运行而增长(当然也可以减小)。

然后每个进程默认是有三个文件描述符的,对应标准输入,标准输出和标准错误。

在做完这些之后,进程的舞台就已经准备好了,接下来操作系统就去执行main(),这样就把CPU转移到了新的进程上了。

进程状态

  • Running:此时进程正在使用处理器。
  • Ready:可以运行,但是操作系统没有让它运行。
  • Blocked:在一些事情发生之前,进程一直需要等待。最简单的例子就是如果一个进程需要IO等待,那么就进入这个状态,别的进程就可以获得CPU了。当IO完成的时候,是直接让这个阻塞的进程马上运行,还是等一下才运行,这取决于操作系统是如何调度的。

数据结构

操作系统是一个程序,那么和别的程序一样,它当然也有自己的数据结构。

首先是对于context:

1
2
3
4
5
6
7
8
9
10
struct context{
int eip;
int esp;
int ebx;
int ecx;
int edx;
int esi;
int edi;
int ebp;
}

然后是对于进程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct proc{
char *mem; // 该进程内存的开始的地方
uint sz; // 进程占用了多少内存空间
char *kstack; // 进程栈的最底层
enum proc_state state; // 进程状态
int pid; // 进程id
struct proc *parent; // 父进程
void *chan; // 如果不是0则睡眠
int killed; // 如果不是0则死亡
struct file *ofile[NOFILE]; // 打开的文件
struct inode *cwd; // 当前目录
struct context context; // 上下文
struct trapframe *tf; // 对于中断所对应的帧
}

操作系统通常会使用进程链表来控制所有的进程。但是有的时候人们的关注点不在于多个进程,而在于单个进程,PCB,process control block里面就包含了进程的所有信息。即可以理解为PCB就是进程链表中的一个节点。

总结

上面就是对一个进程的抽象,接下来就是对高级的策略和低级的机制的讲解,看看它们是如何虚拟化CPU的。

家庭作业部分

首先如果只有两个进程,当一个进程完成的时候,那如果另外一个进程在等待IO,那CPU也会等它,因为此时系统没有别的进程需要CPU了。

##Interlude: Process API

Unix中最有趣的是,创建进程可以使用一对系统调用——fork()exec(),还有一个是进程等待的,叫wait()

系统调用——fork()

本科的时候学习这个函数的时候就觉得非常奇怪,一个函数返回两个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int main(int argc, char *argv[]) {
printf("hello world, pid = %d \n", (int) getpid());
int rc = fork();
if (rc < 0) {
fprintf(stderr, "fork");
} else if (rc == 0) {
printf("child process pid = %d\n", (int) getpid());
} else {
printf("father process pid = %d\n", (int) getpid());
}
return 0;
}

请用sudo运行这个程序。这个程序会先输出hello world,之后就可能先输出child,可能先输出father,纯凭运气。

不知道你发现没有,这个fork系统调用,为什么跟我们平时写的函数一模一样呢?这里的fork,首先确实是一个procedure call,但是在这个里面,隐藏了一条trap指令,通过设置系统调用的相关变量,并且执行trap,就可以执行系统调用了。也就是别人已经帮你封装好了。

系统调用——wait()

上面说了哪个进程先输出纯看运气,但是在实际中,一般都是父进程fork一个子进程,派它去完成任务,然后父进程返回,所以我们一般会让父进程等待在其完成,使用这个系统调用。

当然事无绝对,是存在一些情况,当子进程还没完成但是wait()就已经返回了,即僵尸进程的由来。

系统调用——exec()

如果你想调用别的进程,那么就可以使用这个系统调用,它有好几个变种。具体就是通过这个系统调用,传入你要执行的命令(进程名字),并且把参数传过去,就可以执行了。

具体的过程是,给定一个可执行的程序的名字和一些参数,然后加载这个程序的代码和数据,覆盖掉自己原来的代码段和数据段,当然堆栈部分也要重新初始化,相当于把自己变成了那个程序。所以如果使用exec系统调用,并没有创建新的进程。

分析API

为什么要这么设计呢?这样设计可以让shell在fork之后执行代码,在exec之前执行代码。具体来说,当我们打开shell,输入一个命令,此时shell就可以知道上哪里去找到这个命令的可执行文件,并且使用fork来创建子进程,并且在子进程使用exec或者它的变体来执行任务,同时父进程进行wait。一旦父进程的wait返回,说明已经执行完毕,此时又再次显示提示符。

如果执行的命令进行了重定向,那么在创建完子进程之后,进行exec之前,shell关闭掉它的标准输出,并且打开指定的文件,这样就会重定向到指定的文件了。

如果关闭了标准输出,那么当使用open系统调用的时候,就会把打开的文件的文件描述符置成STDOUT_FILENO,这样就会输出到文件中去了。

系统调用pipe和上面的原理很相似,在上面的例子中,进程的输出被连接到内核的pipe中,另外一个进程的标准输入也连接到同一根管道,这样就可以将一个进程的输出作为另一个程序的输入,连成一条链。

进程控制和用户

除了上面三个系统调用,还有一些用来和进程进行沟通的方法。比如kill系统调用会发送信号给进程。

在很多shell中,可以通过一些键盘的组合键来发送信号给当前正在运行的进程

进程通过使用signal系统调用来捕捉这些信号,当信号到来的时候,进程会暂停自己正常的运行,转而执行一段特殊的代码来响应这个信号。当然不是任何用户都能够发送信号给进程的,这个也是操作系统进行控制的。

有用的工具

通过ps命令可以查看正在运行的进程(大概率就是ps和你的shell),top展示了系统中的进程并且消耗的资源。

家庭作业

  1. 如果有一个变量,在父进程创建子进程之前就已经存在,那么父进程和子进程分别分别修改了这个变量之后,结果是什么呢?

    因为子进程会获得父进程所有的一切的复制,所以这个变量在子进程里面也会有,而且这个变量和父进程的那个变量已经完完全全没有任何关系了。

  2. 如果父进程使用open系统调用打开了一个文件,然后创建了子进程,那么它们两个可以同时拥有这个文件描述符吗,它们可以同时对这个文件进行写入操作吗?

    经过实际编写代码验证,一个文件的文件描述符在两个进程中是一致的,都为3,但是文件的最后内容,取决于两个进程中最后执行的那个进程,也就是说会覆盖掉。

  3. 如何在不是用wait的情况下,保证子进程先结束呢?

    emmm 说实话不会。查阅资料,可以首先暂停父进程,然后到子进程完成自己的任务之后,通过kill发送一个SIGCONT信号给父进程,父进程就会继续进行了。

  4. 为什么exec会有这么多的变种呢?

    emmm 不清楚哎。

  5. wait函数返回的是什么?

    在子进程中返回的是-1,父进程中的wait返回的是子进程的pid。

  6. waitpid和wait有什么区别呢?

    waitpid可以指定等待的进程pid。

  7. 如果父进程创建了一个子进程,然后在子进程里面关闭了标准输出,然后使用了printf,会发生什么呢?

    屏幕中啥都不显示

  8. 编写一个程序,它能够创建两个子进程,并且子进程之间利用管道进行通信。

Mechanism: Limited Direct Execution

操作系统通过时间片分享机制来实现虚拟化,但是要解决几个问题:效率怎么维持?控制权怎么解决呢?

操作系统必须保证自己掌握着系统的控制权。

最简单的实现:有限直接执行

不难想到一种叫limited direct execution的方法:当操作系统开始一个程序的时候,做好准备工作,然后调用该进程的main,接着程序就执行,直到返回。接下来操作系统进行一些清理工作。

但是这么做明显也有问题:进程执行的时候,操作系统如何发送信号给进程呢?怎么保证这个进程不瞎搞事呢?

问题1:限制操作

直接执行程序的话,显然会非常快,因为程序直接运行在CPU上。但是问题是如果这个进程需要操作一些高权限的操作,例如IO或者是其他资源呢?

通过设置用户态和内核态,就可以解决这个问题。运行在用户态的代码,就不可以处理IO请求,如果强行这么做,处理器会触发一个异常并且跳转到操作系统中,接着操作系统就会干掉这个进程。而操作系统就运行于内核态,不受限制。

那如果用户态的代码真的需要去从文件中获取信息呢?现代的硬件提供了一种能力,能够让用户程序使用一个系统调用,内核会暴露一些关键的函数给用户程序,以便使用。

为了能够执行一个系统调用,程序必须使用一条特殊的指令——trap。这条指令可以同时跳转到内核并且提高内核的优先级。结束的使用使用 return-from-trap指令,跳转到用户程序的同时并且降低优先级。

内核同时还有一个trap table,这东西在操作系统启动的时候(操作系统启动的时候当然是内核态)进行初始化。

也就是通过内核态和用户态之间的切换,保证了进程不能想做什么就做什么。

问题2:在进程中切换

听上去进程切换不难,但是有一个问题:在进程A使用CPU的时候,操作系统并没有在运行啊,如果操作系统没有运行,它怎么进行操作呢?(实际上它也确实无能为力),那它要如何去夺权呢?

在早期的mac os中,使用的是合作模型:操作系统信任进程在执行一段时间的CPU之后会放弃CPU时间,这样OS就能够执行别的任务,使用的是yield系统调用。也即是OS只需要等待系统调用,当进程执行系统调用,那么CPU时间就会回到自己这里。显然,模型建立在信任之上的话,一旦有恶意程序不调用系统调用,而且也不放弃,那么整个系统就完蛋了。

所以需要一种方式强行拿回CPU时间,怎么办呢?使用timer interrupt。本质上是使用一个硬件,这个硬件能够每隔一段时间,自动触发一个中断,只要中断触发,那么当前运行的进程就停止,中断处理程序会执行(需要保存进程的状态),这样OS就得到了CPU控制权。所以在系统启动的时候,不仅要设置trap table,也同样需要设置这个定时器。

不管是进程自愿放弃CPU时间,还是通过定时OS强制获取了控制权,OS都需要考虑接下来让哪个进程来运行,这一部分就是通过scheduler来完成的。

如果OS决定切换进程执行,那么OS就需要执行context switch,做法也很简单,就是把之前的进程的寄存器保存起来(保存到kernal stack中),然后把将要执行的进程的寄存器恢复(从kernal stack中恢复),这样当return-from-trap指令运行的时候,就可执行接下来的进程了。

更为具体的,当定时器中断发生的时候,user register由硬件来隐式保存,保存到kernal stack中。当操作系统决定切换进程的时候,kernel register被操作系统显式进行保存,保存到内存的进程结构中去。下面这张图就说明了这个过程:

image-20200712212642769

并发下的问题

比如系统调用的时候,发生了时间中断,这怎么办呢?

当你正在处理一个中断,另外一个中断发生了,怎么办呢?

这些问题会在第二部分完成,但是这里先简单来回答一下。通过在处理中断的时候,disable interrupts屏蔽中断。这样就不会导致CPU被抢走。还有一些锁机制来解决这些问题,在多进程中非常有用。

总结

在这部分我们学到了一些low-level的机制来实现CPU虚拟化,通过在系统启动的时候设置好trap table和interrupt timer,可以有效解决这些问题。

我们还留下一个问题,接下来,应该让哪一个进程来执行呢?

家庭作业

手动测试一下一个system call和一个context switch的时间。

测试system call非常简单,难的是测试context switch的时间。思路:在单CPU上运行两个进程,并且使用两根管道连接它们。第一个进程,在管道A中写,并且等待从管道B中读。因为第一个进程需要等待管道B来读取,所以操作系统就把阻塞了,然后转到第二个进程,第二个进程是往管道B里面写,同时等待管道A中读,当第二个进程需要读的时候,它也阻塞了,此时又切换回第一个进程,这样循环就建立了。通过多次重复,就可以得出结果了。

linux下有一个sched setaffinity系统调用可以保证两个进程运行在同一个CPU中。

实测在阿里云学生机上面,系统调用是0.287微秒,进程上下文切换是1.343微秒。

Scheduling: Introduction

低级别的机制,例如进程间的上下文切换我们已经了解了。现在我们需要理解高级别的策略了。

工作量假设

workload,即工作量,对于我们之后做出决策是至关重要的,但是目前我们的假设是有一点不切实际的,但是最终会成为一个可行的方案。再次强调,接下来的内容有点荒唐,但是请先接受。

  1. 所有的进程运行的总时间一致。
  2. 进程同时抵达。
  3. 一旦开始,进程就必须执行完成(不可被中断)
  4. 所有进程只使用CPU
  5. 每个进程需要的时间是确定的

调度的指标

我们需要有指标来评估每种调度的好坏。目前只使用一个叫turnaround time的指标。计算也很简单,就是一个job完成的时间点减去这个job开始的时间点。

FIFO

先到先得,也叫First Come, First Served (FCFS)。如果假设每个job运行的时间是10ms,那么非常容易计算出turnaround time的平均是20ms。

现在,我们把假设1去掉。那么每个job的时间就不再是相同了,如果按照先来先得,那么如果第一个进程使用了超级久的时间,这样turnaround time的平均值就会非常大。

SJF

Shortest Job First (SJF),最短优先。看上去非常完美,也可以证明确实是最优解。但是一旦我们把条件2放松,即进程并不是同时抵达的,这个算法就崩掉了:一个超级费时的job先到了,因为整个系统中只有它,那么当然是让它运行,接下来到了几个用时短的进程,但是由于条件3的存在,它们只能等待。

STCF

Shortest Time-to-Completion First。接下来我们把条件三也去掉,这样我们可以通过之前讲述的定时中断来打断进程的运行从而完成。这样就可以通过preempt(抢占)来缩短。

任何时候,只要当一个新的job加进来,定时器就会决定哪个job会最快完成,那么就让它执行。

新的指标:响应时间

之前我们通过放宽123三个条件,完成了这三个算法的构思。但是现在的应用,很多都是用户在屏幕前操作,所以这里需要新增一个指标——response time响应时间。

响应时间的定义也简单: 响应时间 = 第一次运行的时间 - 到达的时间

显然在这个指标下,STCF表现异常差劲,它会让最先完成的进程完成,而最后完成的那个进程,需要等待超级久的时间。

Round Robin

RR算法,让进程执行一个time slice,或者也叫scheduling quantum,然后切换到下一个job。不停重复,直到job完成。注意,时间片的大小,必须是时间中断的倍数。显然如果时间片越小,那么响应时间越短。当然太小的,context switch就会比较多,这部分开销就会变大。所以时间片大小的决策,也是一个trade-off的过程。

有得必有失,RR的turnaroud time是所有算法中,最糟糕的,没有之一。

合并IO

这里,我们将放宽条件4。当一个进程需要IO操作的时候,系统会让其阻塞,所以对于调度器来说,阻塞之后选哪个进程继续运行是一个问题。同理当IO完成的时候,如何抉择也是同样的。

No More Oracle

最后一个条件,操作系统其实压根不知道这个进程需要多久,也就是,还需要继续改进。

总结

本章中我们提出了两种度量方法,也提出了4种调度算法,明白了在turnaround time和response time之间的不可调和的矛盾。

Scheduling: The Multi-Level Feedback Queue

Multi-level Feed- back Queue (MLFQ),最为有名的进程调度算法,中文翻译成多级反馈队列。

提出这个算法的人,获得了图灵奖,在现代操作系统中有着极其重要的作用。该算法同时着眼于之前我们提到的两个度量:turnaround time 和 response time。

MLFQ:基础规则

首先有很多个列队,每一个队列都分配了一个不同的优先级,一个job只能属于一个队列,在优先级更高的队列中的job会优先执行。如果一堆jobs在同一个队列中,那么使用RR算法调度。总结起来就是两条:

  • 规则1:优先级队列高的job先执行,只要有优先级高的队列,那么优先级低的队列中的job是无法执行的。
  • 规则2:同一优先级的job之间使用RR。

显然现在的问题就是,我们如何把job放到队列中去,MLFQ算法会根据它对job的观察,来进行调整。通俗讲就是通过过去推测未来。

如何改变优先级?

接下来我们先做出一些假设:

  • 规则3:当一个job到来的时候,它的优先级是当前系统中最高的。
  • 规则4a:如果一个job使用了全部的时间片,那么优先级就需要降低。
  • 规则4b:如果一个job还没有用完时间片就放弃了CPU时间,那么优先级不变。

这里显然会导致一个问题,如果一个进程不使用完时间片,那么它的优先级永远是最高的,而之前规则1规定了,在有高优先级的情况下,低优先级是不能执行的,这就会导致饥饿问题。

第二个问题就是,job只要没用完时间片,比如在即将用完之前,去读取一个文件,那么就会放弃CPU,这样就能一直保证在最高的优先级队列中。

最后一个问题是,如果一个进程一开始用CPU比较多,然后掉到了低优先级队列,之后进程改变了状态,但是它永远都在优先级低的队列中了,这不公平。

优先级提升

为了防止饥饿问题的产生,最简单的方法就是定期提升所有job的优先级,所以规则5诞生了:

  • 规则5:经过一定的时间,把所有的job放到最高优先级的队列中去。

Better Accounting

接下来需要解决的问题是,怎么解决之前提到的第二个问题,即如果有恶意的进程,故意在时间片用完之前放弃CPU来保持高优先级,所以我们只需要修改下规则4a和4b即可,修改过后的规则如下:

  • 规则4:只要一个进程用完了它所给的时间,就会被降级。

调整和一些其他的问题

如何具体参数化这个调度器呢?

越高级的队列的时间片越小等等,但是这个问题终究还是多种多样的,因为不同的实现是不同的。

Scheduling: Proportional Share

这一部分介绍另外一种调度器——比例分享调度器,有时候也叫做公平调度器。

它基于这么一个需求:希望每个job所占的CPU百分比是固定的。

基本想法:用中彩票的思想

就最简单的想法就是用ticket,假设两个进程A和B,A有75张tickets,B有25张,那么A就有75%的CPU,B有75%的CPU。那么只需要生成一个随机数,如果落到了0-74之间执行A,否则执行B即可。

ticket机制

ticket currency,即每个进程还可以接着对自己获得tickets再次进行分配。ticket transfer,一个进程还可以把自己的ticket交给别的进程。ticket inflation,没想到吧,这东西还能通货膨胀,当然这必须在一个进程互相信任的系统中,一个进程如果确实需要更多的CPU,那它就可以增加自己手中的ticket。

实现

实现真的超级简单:一个链表其中每个节点是进程,一个良好的随机数生成器,一个数字记录系统中ticket的总数。只需要生成一个随机数,遍历链表,找到那个进程,然后它就可以执行了。

如何分配ticket?

这是一个棘手的问题,其中的一种解决方法是:用户有一些选票,他可以把这些选票分配给任何job。然而这并不是一个实际的方法,因为它根本没告诉你到底怎么做。

为什么不是确定性而是使用随机呢?

随机在对于比较长的时间中,效果不错,但是如果是时间很短的进程,可能就没那么理想,于是就有了stride scheduling,一种确定的公平的调度器。也是很简单:每个job都有一个stride,可以理解为就是ticket的倒数。具体算法就是:每次选择最小的stride的进程(一开始大家都是0,那么随机选择即可),执行它,然后加大它的stride(加大方法就是它目前的值加上一个stride)。不停循环即可。

因为stride是票数的倒数,所以票数越大,stride就越小;stride越小,每次需要加的stride也小,就越可能执行到。

这个算法的最大缺点是需要维护一个global的状态,不然当有新的进程到来的时候,因为肯定是0,那么新进程会一直霸占CPU,而显然在随机算法那里不会有这个问题。

Linux的CFS

Completely Fair Scheduler (CFS),完全公平的调度方法。大多数的调度算法,都基于固定时间片,CFS则不然,它的目标就是在所有的进程之间公平分配。

基本想法

通过一个叫virtual runtime (vruntime)的东西。只要进程运行,那么这个vruntime就会增长。每个进程的vruntime都会以相同的速度增长,当需要调度的时候,就让最低的vruntime的进程执行。

显然如果调度频繁,那么context switch开销大;不频繁则保证不了公平性。所以使用了一些控制参数来进行调控。

第一个参数是sched_latency,该参数用来调控在切换之前,一个进程应该运行多久。典型的值是48ms,所以如果有4个任务那么就是每个进程运行12ms。

第二个参数 min_granularity,因为如果进程太多,那么会导致每个进程分到的时间太少了,这个值就是用来保证每个进程分到的时间不会低于这个值。

注意,CFS本身也需要用到定时中断,所以也必须是倍数。

加权

当然CFS允许给某些进程更高的优先级。但是它使用的不是ticket机制,而是用的nice等级,一个从-20到+19的值。数字越小优先级越高(-20优先级最高)

image-20200713020131479

根据这张表格,可以把nice值映射到一个权重,然后可以计算出每个进程应该占据的时间片大小,公式如下:

image-20200713020301525

同时,vruntime的计算公式也要变更一下:

image-20200713020447550

emmmm里面的数学原理暂不深究了。

用红黑树

对于一个调度器来说,它必须马上让一个进程执行,但是之前是一个链表,通过链表寻找会比较耗时。CFS就通过一颗红黑树来代替链表。

红黑树只记录可以运行的进程,如果进程睡眠或者阻塞了,就会被从红黑树中移除。

处理IO进程和睡眠进程

之前说了如果进程睡眠或者阻塞,会被从红黑树中移除。那当醒来的时候,它的vruntime会很小,那岂不是就一直霸占CPU了吗?不会的,CFS会将这些进程的vruntime设置成红黑树中最小的vruntime。

总结

在这一部分我们讨论了什么是按比例分配的调度算法,分别有彩票型、stride型和CFS这三种。前两种都是理论型的,只有CFS是真正实现了的。而CFS本身也特别像RR,只不过是带了权重的RR。

从上面的分析中我们也发现,如果一些进程因为IO或者睡眠等问题放弃CPU,那么之后会得到更多的CPU。

但是对于一些云平台,按照比例分配的调度算法可以发挥它们的优点,比如我固定分配30%给我的虚拟机。

Multiprocessor Scheduling (Advanced)

之前讲述的都是在单核CPU中,这一章我们将来学习在多核CPU中如何进行调度。

多处理器架构

多处理架构通过cache来共享数据。在单CPU架构中,cache的存在是为了加速;在多CPU中,每个CPU都有自己的缓存,这就导致了cache coherence(缓存一致性)问题的发生。

cache是基于局部性原理的,即时间局部性和空间局部性。

如果要解决缓存一致性问题,有一个解决办法:CPU可以通过总线去监视别的CPU(bus snooping),每个cache都通过观察总线来得知内存的变化,如果CPU知道自己的cache中的数据变了,要么更新这个数据,要么抛弃这个数据。

Synchronization

在共享数据的时候,mutual exclusion primitives(互斥原语,最典型的就是锁)能够保证正确性。

还举了一个删除链表头节点的例子,在多线程环境中会出现问题。

Cache Affinity

Cache Affinity,缓存关联性。一个进程获得CPU时间的时候,会在CPU缓存和TLB中建立一堆状态。如果下一次这个进程还是在同一个CPU上跑,那么就能够运行得很快。如果每次都换一个CPU跑(由于缓存一致性协议的存在,能够保证进程是可以正确运行的),那么速度就会比较慢。所以调度算法应该尽可能让某个进程一直运行在相同的CPU上。

单队列调度

最简单的就是把所有的jobs放到一个队列中,我们管这个叫single-queue multiprocessor scheduling,简称为SQMS。就是根据现在有多少个CPU,来选择多少个最佳作业。比如有三个jobABC,然后只有两个CPU,那么这个算法就把CPU分给AB,下一轮分给CA……

它的缺点是缺乏可扩展性,编程人员需要为其加入一些锁,来保证它运行的正确性。从上面的描述中也可以看到,它缺乏关联性。如果要能够具有缓存关联性,那么算法会比较复杂,书中没有介绍。

多队列调度

multi-queue multiprocessor scheduling,MQMS,用来进行优化。拥有多个队列,每个队列都是一个调度算法。当一个job进入系统的时候,会被分配一个队列(通过随机或者别的什么方法),接下来就是独立调度了,避免了共享和同步的问题。

但是又有新的问题了:负载均衡。如果某一个CPU队列中的任务完成了,那么CPU就会空闲。可以通过migration来解决这个问题,而在队列之间移动继承,需要一个叫work stealing的技术,简单来说就是每个队列每隔一定时间去看看别的队列的情况,如果发现别的队列比自己忙,就偷一些job过来放到自己这里。

Linux Multiprocessor Schedulers

很遗憾,在linux中并没有一种公共的解决方案来解决这多处理器调度的问题,目前有三种方案:O(1)、CFS和BFS,这里只简单介绍一下。BFS使用了单队列,而另外两个使用的是多队列。所以从这个角度来说,单队列和多队列其实都是成功的算法。

总结

单队列非常的简单,在负载均衡这部分表现优异,但是在缓存关联性这块表现不佳。对队列恰好相反。

对CPU虚拟化的阶段性总结

我们学习了OS如何虚拟化CPU,有很多机制:trap和trap handler,timer interrupt,在进程切换的时候OS和硬件是如何保存它们的状态的。同时可以看到OS是一个偏执狂,它既希望自己能够控制机器,又希望程序能够跑得足够快。同时我们学到在turnaround time 和 response time不可调和的矛盾,就算在现在,linux也在为三个多处理器调度而争论的喋喋不休。

The Abstraction: Address Spaces

早期的系统

早期的系统,压根就没有对内存的抽象,操作系统放在内存的低地址中,然后用户程序使用其余的部分。

多程序和时间分享

然后就有了多程序系统,操作系统通过context switch进行切换来使用CPU,但是内存中的程序呢?难道每一次context switch就需要把整个程序从内存中移入和移除吗?所以我们必须在内存中保留进程,那么就需要对内存地址进行保护。

Address Space

所以我们需要抽象出一个物理内存的概念,这样可以方便使用——于是address space地址空间就诞生了。在系统中执行的程序的眼里,地址空间就是物理内存。

为了简便起见,地址空间里面有三个部分:代码,堆,栈。

代码位于地址空间的低地址,接下来是堆,而栈则位于最高地址。堆和栈通过不停增长来填补空白区域。

image-20200713123813649

也就是当程序运行的时候,堆栈部分会进行扩大或者缩小。

目标

接下来开始虚拟内存,我们需要首先指定好目标:

  1. 虚拟内存必须是透明的
  2. 虚拟内存必须高效,通过使用TLB,能够调和时间和空间。
  3. 虚拟内存必须具备安全性,意味着只有进程自己可以修改自己的内存内容。

总结

我们对虚拟内存有了最基本的认识,也提出了目标,接下来就来实现这些目标。

特别提醒:你在程序中打印的地址全部是虚拟地址,无一例外。

1
2
3
4
5
6
7
int main(int argc, char *argv[]) {
printf("location of code : %p\n", main);
printf("location of heap : %p\n", malloc(100e6));
int x = 3;
printf("location of stack: %p\n", &x);
return x;
}

这段程序的输出看上去像是真的物理地址,然而其实还是虚拟地址。

Interlude: Memory API

内存种类

程序只能控制两部分内存,一部分是栈,但是这部分的分配和回收是隐式的,所以这部分的内存可以理解为是自动的,由编译器自动帮我们完成的。第二部分是堆内存,这部分的分配和回收就是显式的了,所以要慎重!

系统调用——malloc

通过传入一个具体的空间的值(字节为单位),这个系统调用会替你去堆空间开辟空间,如果成功返回指向新开辟空间的指针,否则返回NULL。

在使用malloc的时候,我们一般搭配sizeof使用,需要注意sizeof是一个编译期间才知道结果的函数,所以要谨慎使用。

1
2
3
4
5
6
7
//64位机器中
int main(int argc, char *argv[]) {
void *x = malloc(10 * sizeof(int));
printf("%d\n", sizeof(x)); // x=8
int y[10];
printf("%d\n", sizeof(y)); // y=40
}

为什么malloc返回的是一个void*,这是为了让程序员自己决定应该强制转型成什么。

系统调用——free

free只有一个参数,那就是malloc返回的那个参数。从这里你可以看到,申请的内存的长度,并没有被当成参数传入,所以这部分由库自己来解决的。

常见错误

在java中,内存的分配和回收都是交给垃圾回收器的,所以很爽。但是在c语言中,就需要自己管理,于是就有下面这些错误。

忘记分配内存了

1
2
3
char *src = "hello";
char *dst; // oops! unallocated
strcpy(dst, src); // segfault and die

这个会引发一个段错误。

没有分配足够的空间

就算没有分配足够的空间,程序也能运行,但是其实上发生了一个buffer overflow的问题。至于不同的操作系统如何对待这个问题,见仁见智了。

忘记初始化内存空间

问题不是很严重,但是需要尽量避免。

忘记释放内存空间

典型的memory leak,在长时间运行的程序中(操作系统本身就是这么一个程序),这是一个非常严重的问题。就算是像java这种语言,一样会遭遇这个问题。

短时间的程序可能不是那么严重,因为一旦进程运行完毕,操作系统就会回收进程的所有内存,这这部分内存自然包含了你malloc的内存,所以影响不是很大,但是!!请一定记住malloc了就free。

过早释放空间

你的程序还需要一块空间但是你却过早的使用free释放了它,导致一个叫dangling pointer的问题(野指针,悬空指针)

重复释放一块空间

double free问题,至于会发生什么问题,it depends

参数错误

free的参数,必须要是malloc返回的指针,所以别瞎释放。

底层OS支持

其实malloc和free准确讲应该是一个库函数,它们底层依靠别的系统调用来实现。

其中一个底层系统调用就是brk,该指令用来改变程序中堆的末尾地址,通过传入一个地址来进行修改。所以增大或者减小heap的实际就是通过这个系统调用来实现的。另外一个sbrk作用一样,只不过传入一个增加的地址大小。

虽然底层是通过brk和sbrk来实现的,但是实际中请千万不要去使用。

除了上面提到的,你还可以通过mmap系统调用来获得一片匿名的内存地址空间,称为swap space。和heap非常像,但是不是heap。

其它调用

calloc,就是malloc加上初始化内存为0。 realloc用来改变分配的内存的大小。

总结

这部分我们介绍了内存分配的API以及其可能存在的问题。

Mechanism: Address Translation

之前的CPU的部分,我们用到了limited direct execution,主要思想就是普通的东西进程自己解决,但是需要特殊的东西的时候需要操作系统来帮忙。这种方法既保证了高效性,同时也保证了对硬件的控制。同样的,在内存虚拟部分,我们也需要这两个目标——高效且保持控制。

hardware-based address translation,通过硬件来完成虚拟内存到真实物理内存的映射。而操作系统则必须能够管理内存,并知道哪些内存正在使用。

假设

我们首先假设地址空间必须被连续的放在物理内存中,所以我们也同时假设地址空间的地址必须比真实内存的小,最后我们假设所有的地址空间都是一样大的。

一个例子

1
2
int x = 3000;
x = x + 3;

这段代码,假设编译完成之后的汇编代码是这样子的:

1
2
3
movl 0x0(%ebx), %eax   ;把ebx的内容移动到eax中   		128
addl $0x03, %eax ;把3加到eax中 132
movl %eax, 0x0(%ebx) ;把eax放回到ebx 135

毫无疑问这三条汇编是在程序的代码段中,那么程序就是这么执行的:

  1. 从地址128中取来第一条指令
  2. 执行这条指令,即把ebx指向的内容(其实就是x,位于栈中)放到eax中
  3. 从地址132中取来第二条指令
  4. 执行,这一条不需要和内存交互
  5. 从地址135中取来第三条指令
  6. 执行,并且把eax的值放回到ebx中。

动态迁移(基于硬件)

dynamic relocation,使用两个寄存器,一个是base register,另外一个是bounds register(AKA limit register)。通过使用它们可以保证我们的进程只会在自己的空间中运行。

程序自己以为自己的内存空间从零开始,但是通过基址寄存器,可以轻松的找到它在内存中的真正地址。由于这是在程序运行的时候完成的,所以才叫dynamic。

至于界限寄存器么,就是一开始用来判断有没有越界的。可以有两种实现,第一种是存放虚拟地址的上界,第二种是存放真实物理地址的上界,两种在逻辑上是完全相等的,为了简便,我们采用的是第一种。

注意!这两个寄存器的真实位置是在CPU上,人们称那些在处理器中,帮助进行address translation的那部分为memory management unit (MMU)

硬件支持的总结

之前我们说CPU提供两种模式,分别是用户态和内核态,CPU需要一个处理器状态字,以此来表明目前自己运行在哪个模式下,通过一些特殊场景(系统调用或者中断),CPU可以切换自己的模式。

然后CPU还集成了电路能够完成base register和limit register。此外,硬件还需要提供特殊的指令能够更改这两个寄存器的值,当然这些指令必须是特权的,只有在内核态才可以执行。

下面是一张表格的总结:

image-20200713144412299

操作系统的问题

硬件提供了那么多的功能,操作系统就有了新问题需要解决:

  • 在进程创建的时候,需要为其开辟内存空间,在之前的假设中(每块大小固定),这非常容易。操作系统本身维护了一个叫free list的列表来追踪哪个内存空间是空闲的。你可能会说要是大小不固定该怎么办呢?这不是本章讨论的问题。
  • 进程结束之后需要回收空间,只需要简单将那块内存加入到free list中即可。
  • 当context switch的时候,由于CPU的base register和limit register只有一对,所以需要保存并且加载它们的值,那么应该把它们放那里呢?process control block (PCB)中。
  • 第四点,操作系统需要提供异常处理器(在系统启动的时候就创建好),这样如果有进程想要访问别的进程的内存,CPU会触发一个异常,然后异常处理器就可以处理——直接干掉那个进程。

image-20200713145557837

上图展示了在启动的时候OS命令硬件都做了什么。

总结

在这一部分我们扩展了LDE,有了地址转化,操作系统可以轻松掌控各个进程的内存,而且由于是硬件支持的,所以非常高效。

当然也有缺点,比如如果一个程序的堆和栈都比较小,那么中间一大片内存就被浪费了,被称为internal fragmentation,这主要是由于我们采用的每个进程固定的大小锁造成的,所以我们需要一个更好的机制来充分利用内存空间,显然对于base和bounds来说,太粗粒度了,我们接下来进行讨论。

Segmentation

之前也提到了,因为使用base + bound寄存器会浪费空间,为了解决这个问题而生。

广义的base和bounds

Segmentation就是为了解决这个问题的。我们为什么不再分的细一点,使用逻辑的段来代替地址空间呢?

一个段是一个连续的地址空间,那么我们可以有三个段,分别是代码段、堆段和栈段。这样这三个部分就可以分别定为,而不是要在一块空间中了,这样也就不会有空间的浪费了。为了实现这个,只需要三对寄存器保存即可。

所以段错误其实就是访问非法地址的错误,但是其实就算计算机不支持分段,该术语仍然正确。

然后又提出了offset的概念,表示相对于自己当前的段偏移的字节数,只有把offset加上base才是真正的物理地址。

我们应该使用哪个段呢?

硬件上使用的是段寄存器,那么问题来了,需要知道偏移量才可以计算出真正的地址,如何知道偏移量呢?

一种简单的方法就是根据地址划分,前几位是段,后几位是offset。因为我们说了我们有三个段,所以只需要前两位作为段号,剩下的作为偏移量。

栈怎么办呢

因为栈是向低地址方向增长的,所以其实我们还需要一位来记录数据结构增长的方向。

共享支持

那既然有了一位代表增长的方向,为什么不多来几位来丰富功能呢?为了支持共享,拿出一个protection bits,如果设置成read-only,那么就可以进行共享——而且进程本身还并不知情。

但是与此对应的是,除了要验证bound寄存器的值,还需要验证protection bits的值。

段的粒度

目前只有三种段,所以是粗粒度的coarse-grained,因为它把地址空间分成比较大的块。但是在早期的系统中,反而是细粒度的,更加灵活。

如果需要的段比较多,那么就需要一个segment table来保存信息。

操作系统支持

看上去用段来进行内存分配非常不错,但是还是有一些问题的存在:

  1. 操作系统在context switch的时候应该干些什么?当然是需要保存相关的寄存器的值啦。
  2. 在内存大小变动的时候(比如创建对象需要扩大heap的时候),操作系统需要更新寄存器的值。
  3. 为段找到物理内存是一件麻烦的事情。

随着使用,内存马上会千疮百孔,就很难找出一片合适的空间来使用了,这个问题称为external fragmentation。一个解决方法就是对内存进行压缩,但是压缩的成本比较大,因为需要停止进程,而且所需时间也不少。另外一种解决方法是使用一个free-list管理算法,尽最大努力让大块内存能够分配,具体的实现有best-fitworst-fit, first-fit以及更为复杂的buddy algorithm,但是不论怎么努力,内存碎片,永远存在。

总结

内存分段让内存分配更加灵活,避免了大段内存空间的浪费。同时也很效率,同时还支持共享。

接下来我们要解决两个问题:第一个是碎片问题,第二个是段的分法还是不够细,期望找到一种更好的方法。

Free-Space Management

这部分我们将要探索一下free-space management,空闲空间管理。对于固定大小的比较简单,而对于随机大小的则比较难。

假设

之前我们也留下了一个问题,为什么在释放内存的时候不需要指明大小呢?

内存的分配,可以是操作系统分配空间给进程,也可以是进程本身使用malloc来分配heap空间。这两个分配内存空间都可以使用free list来完成。

在内存中管理堆空间中空闲的块的数据结构叫做free-list(这段话应该有点问题),包含了对所有空间的引用。虽然叫list,但是实际上不一定是list。

internal fragmentation:每当请求内存的时候,都会分给固定大小的内存块,这样就造成了内部的浪费。

external fragmentation:频繁回收和分配,会导致小的内存块夹杂在已经分配的内存块之间,所以叫外部碎片。

我们接下来主要关注external fragmentation——堆中的空间碎片。

我们假设,一旦一个程序使用了malloc分配了内存,那么就会返回堆中的一个指针,可以说这块内存被这个程序所拥有了,所以没办法做压缩。

最后我们假设分配连续的内存空间,并且在某些条件下,内存区域是可以增长的。

低级别的机制

我们首先介绍大多数分配中使用的机制。

  • 讨论基础的分割和合并
  • 如何快速且轻松的追踪内存区域的大小。
  • 如何构造上面所说的free-list

分割和合并

free-list可以是一个链表,每个节点记录了当前可以使用的空闲内存的起始点和长度。对于大于长度的,遍历链表可以得到NULL,而对于等于长度的,可以找到一个完美的点来契合,那么对于小于指定长度的呢?它会找到一个节点能够分配出空间,然后对这个节点进行分割,并对链表进行了修改。

同理进行空间释放的时候,就会把几个空闲的节点进行合并,制造出一块大的连续的空间。

追踪分配空间的大小

只需要在分配空间的时候,在head block里面保存信息就行了。由于这部分需要占据一定的空间,我们假设是N,所以当用户要求分配10个字节的空间的时候,真正需要去找N+10字节的空间来满足需求。

实现Free List

当我们分配一个新节点的时候,你需要使用malloc来为节点分配内存,而是需要在空闲的空间中创建出一个list,即一开始heap创建的时候就有一个list,然后这个list只有一个头部信息。

调整Heap大小

一开始程序分配到的heap会比较下,然后通过sbrk系统调用来增大heap。具体就是通过OS找到一些空闲的物理页,然后会把这些空闲的物理页给需求的进程。

基本策略

Best fit

通过扫描整个链表,找到所有能够满足要求的最小值。

Worst Fit

扫描整个链表找到最大的那块内存,分配。研究表明这个策略效果很差。

First Fit

从链表开始,只要找到第一个能够放得下,就使用。

####Next Fit

和First fit相同的思路,只不过是它还有一个指针指向了链表尾部,这样可以有效均衡整个链表。

其它的方法

Segregated Lists

如果某个应用经常申请固定大小的,那么使用一个单独的list来分配。我个人是没感觉出来有什么好处,不过书中说的是碎片问题就不再需要那么关注了?

当系统启动的时候,会为内存对象分配一些object caches,这些object caches就是segregated free list。

Buddy Allocation

因为合并是一个非常重要的过程,所以有一些对合并进行改进的操作,其中一个就是binary buddy allocator

一开始空闲空间指定为2N,如果有请求空闲的内存,那么就把空闲空间一分为二,直到找到足够大的空间。

假设有一块64K的空间,需要分配7KB。那就不停分下去,直到8KB。因为分的时候是一分为二,所以合并的时候会非常简单。

其它办法

上面也提到了一些算法的缺点就是需要遍历整个链表,这就导致了速度慢,那么可以用别的数据结构来代替链表提升性能。

总结

我们介绍了一些初级的内存分配算法。

Paging: Introduction

有这么一种说法,操作系统使用了两种方法来解决空间的管理问题:第一种是把东西(这里指的是内存)切分成大小可变的块,比如在虚拟内存中的segmentation,这个方法的问题是存在碎片;第二种是把东西(这里指的是内存)分成大小相等的块,我们称之为paging。与此同时,我们把物理内存看成是一个数组,其中的每一个元素都是page frames

一个简单的例子

图就省略了,脑补即可。paging技术相比之前的段技术,最大的优点就是灵活性,其次的优点是简单。

为了记录每个进程所使用的虚拟页和物理页之间的关系,我们需要一个叫page table的数据结构来记录一下,该数据结构是每一个进程都有的。

假设有一条指令被从内存中已经读到了CPU中,并且即将要开始执行,这条指令是movl <virtual address>, %eax,为了能够执行这条指令,我们首先要把这个虚拟地址分成两部分: virtual page number (VPN)offset。接下来通过查表,可以把这个VPN转换成真实物理的页的号码,即physical frame number (PFN),这样就能找到真实的物理地址了,如下图所示:

image-20200714200923561

上面的这部分是非常好理解的,那么问题是:这个page table在哪里呢?有多大,里面典型的内容是什么?分页会让系统变慢吗?

page table在哪里

在32位的寻址空间中,一页的大小普遍是4KB,即12位,那么剩下的20位就是VPN,那就需要220条记录,假设一条记录(page table entry (PTE))只有4字节,那也要4MB,而且这是每个进程的!显然这也太大了,如果一个系统有100个进程,那内存就要分400MB空间在这上面。这个page table太大的问题,这里先暂时放一放,并不打算解决。

page table被放到内存中,由操作系统管理。

page table究竟是什么

是一个map,key是VPN,value是PFN。最简单的实现是一个数组,叫做linear page table,数组的下标是VPN,里面的内容是PTE(PET本身就包含了PFN,见下图)

image-20200714202658441

这个PTE里面除了存PFN,还存放了valid bit用来指示这个页有没有启用;protection bits(如果一个页只允许读但是你强行要写的话,就会进入trap然后把控制权转移给OS);present bit(0)用来指示这个页是在物理内存中还是在磁盘中;dirty bit用来指明该页是不是已经在内存中被修改过了;reference bit (a.k.a. accessed bit)表明这个页被使用了多少次,在之后的页置换中有作用;还有2的U/S位用来指示在用户态的进程能否访问这个页。

分页慢

除了页表太大意外,还有一点就是慢。显然操作系统需要首先获取到页表,执行转换工作,然后再去对应的物理页中把数据取回来。也就是我们额外进行了一次内存的操作,势必会让程序跑得慢。

获取页表,我们可以假设有一个page-table base register寄存器里面存放了当前进程的页表的位置。

现在的问题有俩:页表所占空间太大以及查询页表需要额外的时间导致程序变慢,我们需要解决这两个关键的问题。

内存追踪

这部分用一个简单的例子来完成。假设有一个长度为1000的数组,我们现在要将其每个元素都赋值成0。然后将其反编译,可得如下结果:

1
2
3
4
1024 movl $0x0,(%edi,%eax,4)
1028 incl %eax
1032 cmpl $0x03e8,%eax
1036 jne 0x1024

第一条指令:首先计算出虚拟地址(edi放的是数组基址,eas放的是index,4是int的字节数),然后把0扔进去。

第二条指令:index 加一的操作

第三条指令:比较一下当前的index和1000。

第四条指令:如果index比1000小,则跳到1024,即第一条。

为了讨论的方便,我们假设虚拟地址的寻址空间是64K,页的大小是1K。并且我们假设我们知道页表位于物理内存的1K处。

接下来,我们需要知道指令的位置,从上面看到是从1024开始的,也就是说从第二页(VPN=1,因为是从0开始计数的)开始的,我们假设VPN1被映射到了PFN4。

然后是数组本身,一共是4000字节,那么我们假设虚拟地址是40000~440000,并且对应关系是(VPN39对应PFN7,40对应8)。

那么程序真正运行的时候会这么做:

  1. 需要取得对应的指令,那么就首先需要去页表里面查出,这条指令对应的虚拟地址的真正物理地址在哪里。
  2. 然后指令需要被放到CPU里面去执行
  3. 可以看到还有一个mov指令,也需要把虚拟地址转换成真实地址。

所以一次循环里,我们一共访问内存10次,4次是把指令放到内存中,一次更新index,还有五次是进行地址转化。

总结

我们介绍了paging技术,同时也发现了它的两个问题,接下来的两章就用来解决它们。

更快速——TLB

我们如何来加速地址转换的这个过程呢,并且尽可能少的使用内存。有没有什么硬件能帮助我们实现,操作系统需要怎么配合呢?

物理层次上,有一个硬件translation-lookaside buffer(TLB)来帮助我们,它本身是MMU的一部分(也就是在CPU上的),本质上就是一块cache用来记录虚拟地址到真实物理地址的记录,所以还有一个名字叫address-translation cache

所以在实际中,我们会首先去TLB里面看看有没有映射,如果有那就直接用(意味着不需要去内存的页表中查找了)

基本算法

硬件层面的算法:首先需要从虚拟地址中获取VPN,检查一下TLB里面有没有对应的记录,如果找到了,就说明是TLB hit,直接就可以进行转换。之后进行保护检查,如果通过就说明是可以访问的内存,那么就访问。如果没找到,那么就是TLB miss,我们就需要做一些额外的工作。硬件需要首先找到page table,并找到对应记录,把记录放入到TLB中,然后重新找一次

这里是不是很好奇为什么不是直接返回而是需要再找一次??明明已经知道物理地址了,却还要“大费周章”?

这是因为用户态只能使用虚拟地址,也就是你找到的物理地址不能直接给用户程序,而是只能放到TLB里面,然后让用户再次执行这段指令。

举例说明

一段非常简单的代码:

1
2
3
4
int sum = 0;
for (i = 0; i < 10; i++) {
sum += a[i];
}

我们在这里忽略sum和i,同时忽略从内存中取指令。当需要a[0]的时候,首先抽取出它的VPN,然后首先去TLB里面找,自然没找到。然后就会去页表里面找,并放一份到TLB中。接下来a[1]的时候就可以直接在TLB里找了(a[0]和a[1]有极大可能性在同一页中,这里别杠),速度大大提高。

所以在这次数组更新中,TLB的命中情况是这样的:miss,hit,hit,hit,hit….miss,hit,hit,hit…很显然,是空间连续性导致了这一结果。接下来,由于时间连续性,这段代码很有可能再被使用,所以命中率也非常非常高。

谁处理TLB Miss?

是操作系统还是硬件来处理呢?

早些时候用的复杂指令集,硬件可以完全处理这个错误。通过page-table base register,硬件是可以知道page table放在哪里的。在IntelX86架构中,使用的是multi-level page table,而寄存器使用的CR3。

现在用的是精简指令集,这些指令集有software-managed TLB,如果TLB miss产生了,硬件会发生一个异常,暂停当前的进程并进入到内核态,使用trap handler,那么就可以更新TLB了。这里注意,回去之后需要执行的指令和一般的系统调用不太一样,别的都是哪条指令触发了系统调用,回去的时候调用的是下一条,而TLB这里回去的仍然是同一条(这个特性也决定了一定要特别小心,否则就是死循环),这也就以为程序计数器的值是不同的。用软件实现的好处是简单,灵活性高。

TLB内容是什么?

一个典型的TLB里面可能有32/64/128个条目,其中的一条条目可能是这样的:

image-20200714231251293

这里的other bits 和之前的PTE非常的想。

TLB的问题:Context Switch

当进程进行切换的时候,显然TLB的内容也要切换(可以由硬件实现,也可以由操作系统实现,还可以两者一起)。

最简单的实现就是清空掉TLB,有一条指令可以做到。当然代价就是下一次同一个进程再来的时候,又要重新进行缓存,这样子效率很低。

然后有一些系统支持多个进程共享TLB,通过一个address space identifier (ASID)的域,也就是用来分辨不同的进程的。

问题:代替策略

对于所有的cache来说,一个避不开的问题就是cache replacement,当TLB满的时候,我们需要替换出一个,那么把哪一条记录踢出去呢?显然一切以最高命中率为前提来设计。接下来我们将会学习,在这里我们仅仅是介绍一下least-recently-used(LRU)。这个算法充分利用了空间连续性;当然也可以用随机剔除的方法。

真实TLB条目

image-20200714235743871

选取了一台32位机器,其中页的大小是4KB,所以VPN是20位,offset是12位。但是奇怪的是,VPN在上图中居然只有19位,其实其中的半由内核使用。而PFN是24位的,所以可以支持物理内存为64G的机器。

上面还有一个G,如果该标志置位,说明这个页是所有进程共享的,那么自然就忽略掉ASID了。

然后是3bit长的一个Coherence位,D位的意思是dirty位,V位是valid位。灰色部分的是未使用。

总结

通过TLB我们可以有更快的速度来找到虚拟内存对应的真实物理空间。

当然有一个问题,要是一个程序需要的页数超过了TLB的数量,程序运行就会很慢,在下一章里我们讨论如何解决这个问题。而且这个技术也被数据库管理系统大量使用。

更小的表

TLB的存在帮助我们快速的进行地址转换,但是还遗留了一个页表占据超多内存空间的问题。

简单的解决方法:更大的页

只要我的页更大,那么相应的VPN就会变小,这样页表的数目就会变少。当然更大的页带来的问题就是空间的浪费,也就是内部碎片的问题。所以大部分操作系统使用的还是4KB的页大小(当然其实大部分系统都支持各种页大小)。在数据库中,可以让页大小高达4MB并且在里面存放最常用的数据,这TLB只需要一条记录,

###混合:paging和segment

hybrid,我个人倾向于将其翻译为中庸,即采用了两种方法的长处。

这里我们使用paging和segmentation结合在一起。我们可以将程序分成三段,分别是代码段、堆段和栈段,然后将这三个段分别对应三张页表。

回忆一下我们在segmentation中的做法,有一个base寄存器和一个limit寄存器。在这一部分,在MMU中仍然保留有这个结构。但是我们用base来指向page table的物理地址,而limit寄存器则用来指向page table的结尾。

现在来假设一下,32位地址空间,前两个比特用来判断是哪个段的。那么当TLB miss的时候,通过查看前两个比特就可以知道是应该使用哪一对寄存器,然后到对应的地方去找。

缺点是什么?缺点是不够灵活,而且会有外部碎片的产生。于是人们接着寻找更好的方法

多级页表

舍弃掉分段的话,可以使用multi-level page table,相当于把一个数组变成了一棵树,这也是很多操作系统采用的。

简单来说就是通过page directory,利用多级目录的思想来“压缩”页表。

page directory中的条目被称为page directory entries,它包含了一个valid bit和一个page frame number (PFN)。如果PDE是valid,那么就说明这条页目录条目所指向的页中,至少有一条是有效的。说起来拗口,其实就是如果在页目录表中的一条数据不是valid的,就说明它压根不指向任何一个页表。

这种方式最明显的优点就是节省空间(代价就是你要在内存中多查一次或者多次)

详细例子

有16KB内存,页的大小是64字节,所以虚拟内存的空间是14比特的,8比特用来给VPN,6比特用来给offset,页表拥有28=256个条目。如果一个条目的大小是4字节,那么如果用传统的数组的方法,需要消耗1KB的空间。

256个条目,而一个页的大小是64字节,一个条目的大小是4字节,也就说一个页可以存放下16个条目,那么256个条目只需要16页就可以放下了,对应到page directory中就是16条记录,分别对应了16个页。

所以我们将地址的前4比特作为页的查找项。有了这四个比特,我们就可以找到页目录中对应的那一条记录,通过这条记录我们能够找到对应的页表,然后再根据在PTE中的索引,我们就可以找到最终的记录了。

多余两层结构

在我们的例子中,只有一层是页目录,接下来就是页表了,但是实际中可能会有多余两层的结构出现

Inverted Page Tables

为了更省空间,还可以让所有进程共享一个page table,于是就有了这个方法。

把页表放到磁盘中

尽管我们已经竭尽所能的缩小了页表,但是仍然有可能页表太大了以致于内存放不下,操作系统通过吧课表放到kernel virtual memory里,并且允许系统把一部分页表swap到磁盘中来缓解压力,这也是下一部分学习的内容。

总结

我们知道了页表不是简简单单通过一个数组实现的,而是通过更为复杂的数据结构。通过时间来交换空间。

Beyond Physical Memory: Mechanisms

之前我们有一个假设是所有的page table都能放到内存中的,当内存放不下的时候,就需要磁盘来进行帮忙了。

Swap Space

第一件要做的事情就是我们要确保物理磁盘中是有这个空间的,我们把这块空间叫做swap space,因为我们把页从内存中交换到磁盘上,或者从磁盘中换回来。

Present Bit

当从虚拟页面转化到物理页面的时候,有一个标志位——present bit用来指示这个页到底在不在物理内存中。如果在的话那么一切照旧,如果不在的话那么就会有一个page fault(其实应该叫page miss更为贴切)产生。

page错误产生之后,page-fault handler就会执行,OS会处理。

Page fault

之前提到过TLB可以由硬件实现,也可以软件实现。而page fault则一律交给操作系统来完成。当缺页中断产生的时候,操作系统需要知道缺失的页在磁盘的哪里,这个地址一般被存放在页表中,即代替了原来应该存放真实物理内存地址。

那么为什么这里需要操作系统来做,而硬件不再插手了呢?第一是因为磁盘慢,第二是操作磁盘更加复杂。

一旦缺失的页被找到并且被放入物理内存,操作系统就可以更新页表,把之前放在磁盘中的位置更新成真实物理内存的地址了。

这里需要注意的是,当缺页的时候是去磁盘中找的,也就是在进行IO,所以进程会进入阻塞状态,此时操作系统安排别的进程执行。

内存满了怎么办?

内存满了的话,那就只能踢掉已经在内存里的页了。当然这需要用到page-replacement policy,而这个策略的好坏直接影响了操作系统的执行速度,所以非常重要,我们将在下一章中深入理解。

什么时候发生页替换

之前我们假设的是当内存满了的时候,但是实际中这显然不合适,内存中始终会有一块区域是空着的,操作系统通过high watermark (HW)和low watermark (LW)来帮助执行。如果发现当前内存中可用的页数量低于LW了,那么操作系统就执行一个后台线程,把内存清理清理,直到可用的页数量到HW。这个线程的名字就叫做swap daemon

总结

本章我们了解了一个存在位present bit,如果是0那么就会引发page fault,并且交给page-fault handler来处理。值得注意的是,这些过程对于进程来说都是透明的。

Beyond Physical Memory: Policies

在这一章我们研究在内存中,是通过什么策略来把页换出内存的。

缓存管理

我们将主内存视为虚拟内存的缓存,那么我们要做的就是就是尽量降低cache misses

average memory access time,平均内存访问时间,计算公式如下:

image-20200715141908872

TM的意思是直接在内存中访问的时间,TD表示直接访问磁盘的时间。显然这个磁盘访问的时间是远远大于内存访问时间的。

最佳策略

这个策略中心思想很简单:在所有页中,假设每个页都会在未来的某段时间后被用到,那么选择最远的未来被用到的那个页,踢出去。

然而未来是无法知晓的,所以这种方法并不能实现,但是可以作为衡量的标准(即完美的标准)。

FIFO

早期的系统都是为了避免复杂性,所以使用了简单的方法来实现,这其中就包括了FIFO。有一个队列来实现,当需要替换的时候就把最先进来的页给踢出去。

这里还有一个有趣的现象,就是当扩大cache的时候,命中率反而下降的问题。

随机

实现很简单,然后实际效果嘛,全看运气。

LRU

我们再一次使用过去来推测未来。如果某个页过去被用到了多次,那么将来它很有可能再被用到。

一个程序会经常用到一些特别的代码(比如在循环中),我们应该把这些东西留存在内存之中。

Least-Frequently-Used (LFU)是最少被使用的页面换出,Least-Recently- Used (LRU)是最近最少使用的页。

一个例子

如果抛开时间和空间的局部性原则,那么通过测试,FIFO、随机和LRU这三种的命中率是一致的。

接下来我们使用二八原则,即80%使用的都是20%的页。结果是LRU明显好于FIFO和随机。

最后再来一个对FIFO和LRU最极端的例子:循环取页,且页的总数总是大于容量,所以一开始LRU和FIFO的命中率是0,但是随机算法却还有着不错的表现。

实现

我们必须要有一个数据结构来保存相关的信息。

针对FIFO,我们可以有一个list,而且只需要在两个时候更新:当页被剔出内存和当页加入进来的时候。

随机的话只需要一个良好的随机数发生器即可。

对于LRU,我们还需要知道哪个是最近最少使用的,一种思路就是在page上新增一个代表时间的东西,当页被使用的时候更新这个时间,当页需要被踢出内存的时候操作系统遍历扫描这个时间,找到最小的那个。显然遍历来说,时间成本有点太高了,那退一步说,我们可不可以不用找到最小的那个,而是使用比较小的那个呢?

近似LRU

完美的LRU对于性能影响较大,所以我们这里是用近似LRU——同时也是很多现代操作系统的选择。这个需要硬件的支持,每一页都有use bit,只要一个页被使用了,那么这个bit就是1。硬件不会将这个位置0,只有操作系统会置0。

clock algorithm是一个简单的算法,假设有一个环形的list,时针从某一个页开始(随便哪个都行),当页需要被踢出内存的时候,时针开始看它指向的那个页的use bit是不是1,如果是的话就把它置成0,并且移动到下一个页。

脏页

如果一个页在内存中被修改了,那么必须将它写回到磁盘里。如果页并没有脏,那么直接丢掉就好了。所以硬件支持一个dirty bit,用来显示这个页是不是被修改过。这样上面的那个时钟算法除了考虑use bit之外,还可以考虑这个标志,尽量找那些干净的替换。

其它策略

除了上面的这些,操作系统还需要考虑其它的内容,比如什么时候把页换进来呢?最简单的就是当需要的时候呗,当然也可以未卜先知提前拿进来:比如第P个页拿进来了,那么就顺手把P+1也带进来。

另外一个策略就是操作系统如何把脏页写回到磁盘,最简单的当然是每次写一次,但是其实很多系统会把这些脏页聚合在一起,然后一次性写。

Thrashing抖动

在结束这章之前,我们还有一个问题,如果超额分配了怎么办,即目前所有程序需要的内存超过了物理内存,发生了抖动

早期的操作系统有一套复杂的机制来检测和解决,最简单的就是随机干掉几个进程,还取了个admission control的名字…这和我们生活中有时候挺像的:与其执行很多任务,不如专心做少点的任务。

总结

我们在这部分介绍了一些页面置换策略,操作系统最后使用近似的LRU——时钟算法,当然其实还有一种更简单的策略——买更多的内存(笑)

Complete Virtual Memory Systems

终于到了虚拟内存的最后了,这部分我们将总体回顾一下,并且聊一聊虚拟内存的细节部分。

我们具体以两个系统为例,一个是VAX/VMS操作系统,尽管现在已经50岁了,但是一些idea还是那么有用;另外一个就是大名鼎鼎的linux了。

VAX/VMS

这个系统的主架构师是之后Windows系统的领导者,为了简便,下面就用VMS来代替了。

内存管理硬件

VMS操作系统的进程寻址空间是32位的,一个页是512字节,所以offset是9位,VPN是23位。其中VPN的前两位用来标记是哪个段的,所以它的管理方法用的是段页式。

整个内存的低部分是进程空间,进程空间里的一般放的是用户代码和堆(朝下生长),另一部分是栈,朝上生长,而整个内存的高部分的一半则是操作系统空间。

该系统由于页比较小,所以如果用简单的数组来作为页表的,那么每个进程的页表会非常大,系统的设计者想了两个办法,第一个是把堆栈分开,这样堆栈之间的内存就不需要记录进页表。第二个是操作系统会分配内核的空间,但是这也导致了复杂性的加剧。

真实的地址空间

我们之前只是简单的假设了三个:代码段和堆栈,但是实际上在VMS中这个复杂的多。

image-20200715165944173

在进行context switch的时候,需要切换P0和P1的寄存器,但是不需要切换S的寄存器。

上面的图还可以解释为什么下面这段代码是错误的:

1
2
3
4
5
int main(int argc, char *argv[]) {
int *p = NULL;
*p = 10;
return 0;
}

在C语言中,NULL是0,而第0页可以看到是不可用的。

至于为什么操作系统在物理内存中的地址是不变的,有一些优点:首先是如果执行系统调用write,那么会操作系统会首先把数据从进程中复制到自己的结构中。

页替换

这个操作系统的PTE里面没有reference bit,意味着硬件无法支持LRU,必须操作系统自己来。它使用了一种叫segmented FIFO的策略:每个进程都有一个最大的页数能够放在内存中resident set size (RSS),当一个进程的页数超过这个RSS了,就把最先进来的页踢出去。当然这么做效率不好,所以有一些改进:新增两条second- chance lists,分别对应了干净的页和修改过的页。如果另外一个进程需要页,那么首先从干净的列表中查找,这样可以大大改进FIFO的效率。同样的页进行了页的聚集,把要修改的页一次性写入。

其它的tricks

VMS还有两大法宝,分别是demand zeroing和copy-on-write,这两个其实都是偷懒的办法。

demand zeroing就是当一个进程需要页的时候,操作系统会找到一个页,然后把页清零,但是清零这个过程比较耗时间,所以操作系统知识简单把这个页标记一下,当真的要读取这个页或者往这个页里面写东西的时候,触发一个trap,然后OS才真正把这个页清零。

copy-on-write也差不多,当操作系统需要把一个页从一个地方复制到另外一个地方的时候,它可以不复制,而是指向需要被复制的页并将其标记为read only,如果只是读取一下,那么不会有任何问题。如果真的需要写了,那么就trap到OS,OS就需要真正的去复制一份。

copy-on-write最大的用处应该就是在fork系统调用的时候了,因为需要复制父进程的所有空间,所以如果真正去复制了,会很慢;而且这其中大部分的空间都会被exec给覆盖掉,所以用这个技术特别有用。

linux

地址空间

image-20200715190118231

可以看到这是Linux的内存结构图,和上面的VMX其实是挺像的。在32位的机器上,用户空间和内核空间的分界点是内存的四分之三处。

稍微有点奇怪的是kernel部分,分了两层,一块叫kernel logical addresses,如果需要在这块空间里分配空间,那么就使用kmalloc。很多之前的结构其实都放在这里,比如page table,每个进程都有的kernel stack。而且这部分的内容,是不能被交换到磁盘中去的,而且这部分的内容是直接映射到物理内存中的最开始的位置的。因为这部分是操作系统中最重要的地方,而且是连续的,都是被分配到了物理内存的开始处。

还有一部分是kernel virtual address,在这部分分配内存的话,需要使用vmalloc,而且这部分的内存大概率它不是连续的,这部分内存经常被用来作为buffer,而且这部分还可以用来做为内存的扩展,不过由于目前都是64位机器了,所以这功能也就算了吧。

页表结构

和之前的VMX不同,Linux采用的是多级页表的组织结构,一个寄存器里面存放了页目录的位置,剩下的交给硬件来处理。

然后就是从32位到64位的转变了,64位的机器使用了四级的结构,一个虚拟地址示意图如下所示:

image-20200715195353473

最左边16位并没有被使用。最右边的offset还是12位,说明页的大小还是4K。随着内存的扩大,以后可能还会有五级和六级,想想看,我只是为了把虚拟内存转化为真实物理内存,就需要六次内存访问,这是多么大的开销。

更大的页

更大的页,能够有效减少映射条目,这样可以提高TLB的命中率。在最开始的时候,Linux开发者知道数据库需要这方面的支持,所以希望能够让这些应用使用更大的页,这样只有小部分软件收到影响(而且还是值得的)。随着时间的推移,Linux新增了huge page的支持,可以让操作系统自己来选择这个软件应该使用多大的页,而这个过程对于软件来说是完全透明的。

page cache

为了有效缓解从磁盘中读取和写入的缓慢,大多数操作系统使用了caching缓存系统,Linux自然也不例外。

从三个地方获取了数据并保存在内存中:memory-mapped files,file data以及metadata从设备中获取的(通过read和write系统调用),每个进程都有的堆栈的页。这些内存被放在了page cache hash table,这样能够加快查找速度。

这个page cache会知道里面的条目是不是脏了,脏掉的数据会被一个叫pdflush的后台线程写回到磁盘中。、,可能是每隔一段时间,也可能是因为脏页太多了。

有时候Linux运行比较慢,就会使用2Q的变种:LRU有效但是可以有替代品,比如有一个进程重复访问一个大文件,那么LRU就会把其它文件踢出内存。Linux有两个lists来完成,第一个是inactive list,当你第二次访问的时候,就会放到active list里。所以如果要把页换出去,优先考虑的是inactive list

安全性和缓冲溢出

可能古老的操作系统VMX和现代操作系统Linux之间的区别就是安全性了。

其中一个安全问题就是buffer overflow攻击,可能会影响到用户程序甚至是操作系统,精心构造的攻击确实可以造成privilege escalation特权提升。最简单的防御手段就是让某一部分区域的代码无法执行,通过设置NX位。

另外一个问题是return-oriented programming (ROP),攻击者可以利用在内存中的一些别的程序的代码(称为gadgets)来构造自己的攻击代码。为了解决这个问题,Linux使用了address space layout randomization (ASLR),地址随机化。

其它安全问题:Meltdown And Spectre

问题的根源来自,CPU进行了疯狂的优化,这其中有一项是推测要执行的指令并且提前执行,如果猜中了可以提高效率,猜错会有补偿。

emmm 接下来的内容现在不想看了。

总结

这部分我们浏览了两大操作系统,观察了它们是如何进行内存虚拟化的。同时还额外学习了一些安全知识。


到这里,对于这本书的第一部分算是看完了,稍微来进行梳理一下。

首先这部分主要讲了两个部分的虚拟化,一个是CPU,另外一个就是内存。

  • CPU这块首先了解了进程,并且了解了进程相关的系统调用,明白了在shell中是如何进行命令执行的。然后引出了LDE,来解决操作系统中部分操作的限制问题和进程的切换问题。接下来介绍了进程的一些调度算法,包括FIFO,SJF和最终的MLFQ,其中穿插了RR,还额外介绍了一种百分比的调度算法。

  • 内存这块呢,首先介绍了地址空间,然后是照理是一些系统调用。接下来讲到了如何进行地址的映射,并且通过分段来解决碎片的问题。之后再进一步了解了分页,以及TLB和多级页表。同时也了解了页的交换算法,最后还用了两个具体的系统做了例子。