上篇讲述了程序的编译体系。然而,经过编译体系后,程序离乖乖运行还有很远的路要走,这篇文章继续伴随我们写的程序,来看看what’s beyond the scene。

装载

程序要想乖乖运行,其数据和指令都要在内存中。那么,经过编译体系后,就是装载了。当然,装载不可能只是一口气将可执行文件载入内存这么简单。一般操作系统先要建立一个与程序对应的进程(仅创立虚拟空间,但还未分配,物理空间更没有分配了),然后将控制权交由进程,CPU读取可执行文件的入口地址,才开始运行。接下来聊聊进程。

进程(Process)

在写这部分的时候重温了在大学时代看的现代操作系统时候,看到了自己记下的讲述进程的笔记—进程是具有独立功能的程序关于某个数据集合上的一次运行的活动…这都是什么鬼,我当时在学啥???(艹皿艹 )

实际上啥是进程?就是一段程序。那么进程的主旨是啥?主旨在为这段程序提供一个单一的环境,这个单一的环境让程序好好执行就好,不要管环境外的事。其中,环境包括CPU和内存。CPU指的就是进程在占用CPU运行的时候,造成了没有别的进程存在的假象,即进程是独占CPU的。内存指的是进程的地址空间,进程之间的地址空间相互隔离,进程无法访问到其他进程的空间。怪不得说,要理解进程,能理解到进程是CPU的抽象就到点上了。

接着我们来看一下进程的地址空间,这就是进程“实际”的样子。

Linux进程地址空间

Linux进程地址空间如下图所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 —— —— —— —— —— —— ——       high
|kernel space |
|—— —— —— —— —— —— —— |
|stack |
|—— —— —— —— —— —— —— |
|..... |
|—— —— —— —— —— —— —— |
|dynamic libraries |
|—— —— —— —— —— —— —— |
|..... |
|—— —— —— —— —— —— —— |
|heap |
|—— —— —— —— —— —— —— |
|..... |
|—— —— —— —— —— —— —— |
|R/W .data .bss |
|—— —— —— —— —— —— —— |
|R .text .rodata .init|
|—— —— —— —— —— —— —— |
|reserved |
|—— —— —— —— —— —— —— | low

最高地址先是操作系统内核空间。然后是栈,栈底部放置系统环境变量和命令行参数,比如main函数中的argc和argv,分别代表命令行符号和数量,就放在这里。然后是动态链接库空间。然后是堆。然后是可读写的.data和.bss,已初始化和未初始化的数据段。然后是只可读的代码段、可读数据段、初始化段。最后是保留段,保留段空间被认为是禁止访问的无效空间,比如说空指针指向的0x00,就属于保留段。可以看到,栈是向低地址方向增长,堆是向高地址方向增长。越往高地址,越是操作系统空间,除了保留空间,越往低地址越是用户空间。

虚拟存储器(Virtual-Memory)

虚拟存储器又被译作虚拟内存,CSAPP中被译作虚拟存储器(我更加偏向后者)。它在程序中访问存储器这一过程中扮演了举重若轻的角色。它主要做了两件事:

  • 将物理空间抽象成虚拟空间,这里指的物理空间专指内存上的空间。
  • 管理存储器体系,包括内存和磁盘。

虽然这两件事互相之间藕断丝连,但咱们还是尽量一件事一件事来聊。

第一点,将物理空间抽象成虚拟空间。我们平时写程序包括进程访问的都是虚拟地址,而CPU访问的才是物理地址。那为什么要向用户将物理空间抽象成虚拟空间呢?

  • 解放物理空间的存储管理。这样一来,内存分配的管理方式和其分配的内容可以毫无关联。也就是说,数据被分配的地址与逻辑上程序执行的上下文毫无关系。
  • 提供进程之间的地址空间隔离。如果直接使用物理地址,是不可能用硬件手段阻止进程访问某个区域的存储器的。而使用虚拟地址就可以很简单的侦测出进程访问地址是否合法,是否越界。
  • 多个虚拟空间中的地址可以映射同一物理空间中的地址。这也是可以使动态链接库共享的本质。
  • 简化链接阶段分配地址空间。如果使用物理地址,链接阶段代码都还未载入内存,不可能分配地址空间。而使用虚拟空间将进程之间的地址空间隔离后,直接分配固定地址就可以了。比如,.text段被分配到0x08048000(对于32位)或0x400000(对于64位)。

这里可以看出,链接、装载、进程、虚拟存储器之间环环相扣,一同支撑起计算机体系。

第二点,管理存储器体系。

虚拟存储器管理存储器体系只基于一个思想,内存是磁盘的缓存。实际上,在存储器体系中,高一级的存储器必定是低一级的存储器的缓存。而虚拟存储器划分页来管理内存和磁盘构成的存储器体系。

页(Page)

为什么要分页。假设,现在计算机要执行一个在磁盘上的程序,而内存中已经被其他程序占据,空间不够了,这时候怎么办?只能将其中的一个程序置换到磁盘上,然后将要执行的程序从磁盘置换到内存,来执行程序。若是这个程序占的空间很大,比如说1/2内存大小,那么现在CPU又要在这两个程序之间切换执行。内存就要一直置换1/2大小的空间,可想而知程序就不要执行了,一直置换玩吧,这实际上是就是内存使用效率低下。

这时我们再重新思考一下,根本不需要整个程序都在内存中,只要执行的那部分在就可以了。所以,很自然的将程序减小粒度,划分固定地大小来置换空间就可以了,这样就提升了内存的使用效率。更别说,基于局部性原理这个页的划分方式还很高效呢。

页的属性、页表(Page-Table)

从页开始,虚拟存储器做的这两件事相连的地方就会慢慢呈现出来。在物理空间中划分好了页,虚拟空间中也要划分好页与之对应。被划分好的页可以未被分配、已分配、已缓存,这可以看做成页的一个属性。页面未被分配,就是页面还未关联任何数据,页面还未被用到。页面已被分配就是已被关联数据,但是数据还在磁盘上,未被缓存到内存中,虚拟页(Virtual Page)特指的就是这样的页。而页已被缓存,就是数据已经被缓存到内存中,物理页(Physcial Page)特指的就是这样的页。

页表就是一个记录页的属性和页虚拟空间与物理空间映射关系的数据结构。页表用一个有效位(valid bit)就记录了页的属性,有效位为1代表页已被缓存,有效位为0且页表项不为空代表页已被缓存,有效位为0且页表项为空代表页未被分配。对于已被缓存的页,页的虚拟空间直接映射到物理空间。

缺页中断(Page-Fault)

就像上面内存中满了后执行磁盘上的程序猜测的一样,当去页表中查找到所需页面未被缓存到内存中,操作系统会发起硬件中断,将所需页缓存到内存中,然后重新发起页表查找动作,这一过程就是缺页中断。如果内存不足,这时还要淘汰页面以释放空间。淘汰页面有多种算法,这里就不细聊了。缺页中断很好理解,很有趣的一点是,管理存储器系统时,页面从不会主动缓存到内存中,就有被用到时,才会通过缺页中断缓存到内存

而malloc和calloc就是从侧面证明了这一点,malloc和calloc只是提供一块线性的虚拟空间,而物理空间上没做任何分配。等到真正使用虚拟空间的时候,才会缺页中断,实际分配物理空间。

Copy-On-Write

除了malloc和calloc,进程的Copy-On-Write也与虚拟存储器息息相关。fork产生子进程后,子、父进程拥有不同的虚拟空间,但是映射同一物理空间。并且子、父进程都对物理空间只有只读权限,等到子进程或者父进程要修改物理空间,会触发无权限的缺页中断。这时,操作系统才将真正拷贝物理空间,使子、父进程拥有自己的物理空间。 这就是Copy-On-Write,write lead to copy。

再看装载

文章开头聊装载的时候,实际上忽略了如何真正的“载入”可执行文件。在聊过缺页中断后,再来看看装载。因为缺页中断,极大的简化了装载。装载不需进行任何的显式数据IO,全部交给缺页中断来真正的“载入”。装载不用将可执行文件缓存到内存,而是等到指令跑到内存中无缓存的虚拟地址触发缺页中断。装载只需要提供出可执行文件与虚拟空间的映射就好。装载会将映射记录在进程的vma(Virtual Memory Area)数据抽象中。

从虚拟空间来看,进程创建后,虚拟空间也被创建。此时,虚拟空间是未分配的,装载将映射记录在进程的vma中,就是将虚拟空间从未分配转换为已分配。等到缺页中断,再将虚拟空间从已分配转换到已缓存。

虚拟地址翻译(Translation)成物理地址

将虚拟地址翻译成物理地址,是由操作系统软件、CPU中的硬件MMU(memory management unit)、页表一起协同做到的。

如何翻译呢?最简单的方法就是记录每一个虚拟地址到物理地址的映射,缺陷很明显,要维护一个与地址空间同样大的表,时间复杂度、空间复杂度都不理想。

这里,我们来回想一下,页表已经以页为单位映射了虚拟空间到物理空间。那么,地址可分为页号+页内offset两部分,只要保持虚拟空间和物理空间划分大小一样的页,就可如下计算:

1
2
3
4
5
virtual address = page in virtual space number + page offset(后12位)
|
↓ page table map ||

pysical address = page in phsical space number + page offset(后12位)

有了这个基本思想,再需要一个MMU硬件就可以实现地址翻译了。CPU会将虚拟地址交给MMU,MMU负责进行虚拟地址到虚拟空间中页号的计算,还有物理空间中页号到物理地址的计算。页表存放在内存,MMU用虚拟地址查询物理地址需要进行内存访问。MMU最后计算出物理地址,就去内存中物理空间中取数据,最后返回给CPU。如果页是已分配,MMU就会发起缺页中断。

以上就实现出了整个地址翻译过程,但是,这还不够。在翻译过程中,MMU访问内存在硬件计算级别上,慢得不可忍。这就需要TLB(Transfer lookinside buffer),TLB就是在MMU中的缓存寄存器。TLB用虚拟地址作为索引缓存物理地址和页属性。如果TLB缓存命中(cache hit),就可以大大减少内存访问的开销。

多级页表

即使按页作为粒度划分,页表还是太大了。页表可以做成多级结构。映射的本质本来是,用更小的空间索引更大的空间用索引的空间换搜索的时间。有趣的一点是,多级映射结构正好相反,用多级结构搜索时间换顶级结构的空间。多级结构只有顶级需要常驻在存储器中,次级可以缓存,增加了搜索的时间,减少了存储器中的空间。

mmap

类似于装载交给虚拟存储器做真正的“载入”。将虚拟存储器的能力开放出来,文件也可以交给虚拟存储器做管理。这样,修改进程虚拟空间中的数据,就等同于修改磁盘上的文件。这就是mmap,进程空间映射文件。更加详细的内容,推荐这篇文章

总结

虚拟存储器这个翻译是有深意的,上面所说的这些都可以看做是一个整体的抽象,用户(包括进程)不care数据是在内存还是磁盘上,也不care是用虚拟地址还是物理地址访问,用户只认为是用地址访问一个存储器。而这个存储是“虚拟”的、不是实际存在的。也就是说虚拟存储器隐藏了,虚拟地址、物理地址、内存、磁盘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

—— —— —— —— —— —— —— —— —— —— —— —— —— —— —— |CPU/OS's view | | -->| | -->| | -->| |
| MMU | | PageTable | | | | |
| | <--| | <--| Memory | | |
—— —— —— —— —— —— —— | | | Disk |
| | <--| |
—— —— —— —— | |
| |
—— —— —— ——


|User/Process's view —— —— —— —— —— ——
| |
|"virtual" memory |
| |
—— —— —— —— —— ——

终于,在结合链接、装载、进程、虚拟存储器之后,程序可以乖乖“开始”运行了,对,只是“开始”运行而已。你看看,我们写下任何一行的code,都是站在巨人的肩膀上仰望星空。

在这里我就多贫几句,为什么要学习这些计算机体系?明明在平常工作中都不会用到。有没有觉得,平时在写业务的时候,我们就是进程。而架构师提供给我们一个与进程类似的一个单一的环境,单线程、完备的抽象。换句话说,架构师就充当了虚拟存储器的职能。那么,想当一个架构师去架构软件,万里长征的第一步难道不是学习已有的计算机体系如何做抽象?

接下来,补充一点平时容易迷糊的并发编程相关概念,就权当是彩蛋了O(∩_∩)O!

并发(Concurrency)与并行(Parallelism)

个人认为浅显区别开就好,不是搞高并发的就不长篇大论了。实际上,这两个概念不是在一个层级上,并发指的是程序的设计结构,编出来的程序可能会并发。并行是指计算机处理器同时执行多个任务,并行执行。一个指的是逻辑上编程的方式,一个指的是物理上处理器处理的方式。

线程安全(Thread-Safe)

线程安全指的是,多次以多线程执行程序和这段程序以单线程执行最后结果一致。而线程不安全,就需要加锁考虑线程同步。而不可变数据是线程安全的,可变数据才会出现线程不安全的情况。

锁实质上都是用信号(signal)去提示操作,其实并没有实质上的物理手段去阻止操作,比如说阻止存储器的读写,锁就像红绿灯一样,没有实际的墙阻止汽车启动,而是用信号去提示汽车。

比较常见的锁机制就是互斥锁(mutex)和信号量(semaphore)。而互斥锁就是个特殊的二元信号量这点就不多说了。但是互斥锁与二元信号量有什么区别?区别在于,互斥锁只能在同一个线程上获取和释放,而二元信号量没有这种限制。

还有很不常见的锁机制为条件(condition),condition有些特殊,它已经不是上锁、解锁这样一对一的模型了。它更像是事件分发。condition可以等待新的条件的触发,不触发就堵塞。而condition触发一次,可以即没有等待的或者多个等待的。这就像是事件派发,有观察者堵塞着等待事件源发生。事件源发生后,被派发给单个或者所有观察者,然后观察者继续执行。说白了也是一种信号提示。

引用

深入理解计算机系统(CSAPP)

程序员的自我修养—链接、装载与库