选书
选这本书的初衷有两点吧,一个是大学学习计算机科学的几门课程,并没有一个整体的认识,故梳理和细化下计算机的知识体系,二是深入理解下系统背后的设计原理及折中的考虑,知其然而知其所以然。
《计算机科学导论》可以作为计算机相关从业者的初级知识体系梳理,这本《深入理解计算机系统》可以更加深入和细化计算机这个学科的核心组件和概念的相关知识。
这本书作为CMU的计算机院教材,在豆瓣的口碑和评价也很高。
读书摘要
计算机系统概览
计算机系统:由硬件和软件组成的,共同工作来运行应用程序(用组成和目的来定义)。
信息=位+上下文(0和1表示了所有信息,香农之后信息有了单位,就是是和否)。
磁盘、内存、网络上都是二进制流,区分不同数据对象的唯一方法就是读数据时的上下文。
同样的一个字节序列可能表示整数、浮点数、字符串或者机器指令。
C语言
C语言:是Dennis Ritchie于1969-1973年创建,是由一个人而非协会掌控。
目的:实现Unix操作系统,是系统级编程的首选。
程序处理流程
处理器读取并解释储存在内存中的指令
硬件组成
总线:贯穿整个系统的一组电子管道,成为总线(感觉设计思想来源于生产线,计算机是一个循环使用的生产线)
I/O设备:是系统与外部世界的联系通道。
主存:是一个临时存储设备,在处理器执行程序时,用来存放程序和程序处理的数据。
处理器:是解释主存中指令的引擎,核心是一个字的存储设备。
高速缓存
系统花了大量的时间把信息从一个地方挪到另一个地方(就像人运送货物一样)
磁盘比主存大1000倍,但读取时间是主存的1000万倍,读寄存器比主存快100倍。
解决方案是用cpu cache高速缓存,L2的访问比主存快5-10倍。
存储设备形成层次结构
L0:寄存器
L1:高速缓存(SRAM)
L2:高速缓存(SRAM)
L3:高速缓存(SRAM)
L4:主存(DRAM)
L5:本地二级存储(磁盘)
L6:远程二级缓存(分布式文件系统)
系统管理硬件
硬件管理实现的两个目标:
- 如何防止硬件被滥用
- 向应用程序提供简单一致的机制来控制复杂而又通常大不相同的低级硬件系统
方法是抽象,将计算资源cpu抽象成进程,将主存抽象为虚拟内存,将I/O设备抽象成文件。
进程:是操作系统对一个正在运行的程序的一种抽象;是计算机科学中最重要和最成功的概念之一。
线程:同一个进程内不同的执行单元,共享进程上下文。
虚拟内存:
- 程序代码和数据,对所有程序进程来说,代码是从同一固定地址开始,之后是数据位置。
- 程序和数据后是运行时堆,在进程开始运行时就被指定了大小。
- 共享库是存放想C标准库和数学库的代码和数据区域。
- 栈是用来实现用户函数调用,运行时可动态的扩展和收缩。
- 内核虚拟内存是为内核保留,用户不可见,也不允许应用程序读写这个区域。
文件:
- 文件就是字节序列,仅此而已?
Amdahl定律
- Gene Amdahl是计算机领域的早期先锋之一,对提升系统某一部分性能所能带来的效果做出了重要的总结。
- 整体优化效果S=1/(1-a),a为减少的耗时占比,S为最终提升性能,例如2X则为2倍性能提升。
并发和并行
- 线程级并发:早期单核为交替并行执行,多核后则为多核并发执行。
- 超线程:cpu某个部分有多个硬件备份,可以并行执行多个线程。
- 指令集并行:cpu同时执行多条指令的属性为指令级并行。
- 单指令、多数据并行:SIMD技术。
抽象的使用是计算机科学中最为重要的概念之一。
指令集架构提供了对实际处理器硬件的抽象,底层的硬件远比抽象描述的要复杂精细,它并行执行,又和有序模型保持一致。
信息是如何表示和处理的
信息存储
大多数计算机使用8位的块(byte字节),作为最小的可寻址的内存单位,而不是单独的位。
十六进制:二进制表示太长,十进制转化麻烦,故使用了十六进制来表示位模式。
字长:每台计算机有一个字长,指明指针数据的大小,决定了虚拟地址空间的最大值。
大小端:表示顺序和逆序的字节,源自一个故事(想不起来自己剥鸡蛋从大头还是小头开始了,应该是从裂口最大的那块儿,外国人的习惯好奇怪)
信息表示
位运算规则:布尔代数
整数表示:为什么分为两种一种有符号,一种无符号,从单字节到多字节不同的整数?
原码、反码、补码:为了降低电路复杂度的抽象表示。
信息运算
数据运算结果:正溢出、正常、负溢出。
乘以常数:如何优化为移位操作,将复杂度降为常数。
浮点数:符号、尾数、阶码表示法。
机器是如何理解程序的
计算机执行机器代码:用字节序列编码低级的操作,包括处理数据、管理内存、读写存储设备上的数据及网络通信。
编译器:基于语言的规则、目标机器的指令集和操作系统,生成机器代码。
Intel处理器系列成为X86。
8086:第一代单芯片,16位微处理器之一。
80286:134K个晶体管。
i386:32位体系结构。
i486:1.2M个晶体管,指令集进行小扩展。
Pentium:3.1M个晶体管,性能提升。
PentiumPro:5.5M个晶体管,新处理器设计。
Pentium/MMX:4.5M个晶体管,增加整数向量指令。
Pentium II:7M个晶体管,P6体系延伸。
Pentium III:8.2M个晶体管,引入SSE,浮点向量指令。
Pentium 4:2000年,42M个晶体管,SSE升级到SSE2,增加双精度浮点数。
Pentium 4E:125M个晶体管,增加超线程。
Core 2:291M个晶体管,第一个多核处理器。
Core i7:781M个晶体管,支持超线程的多核。
介绍了计数器、寄存器、取指(取指令)、译码(翻译指令)、执行(算数)、存储、逻辑跳转、数据跳转的整体流程。
边界检查:读时越界访问,写时缓冲区溢出。
电脑的大脑处理器是如何工作的-处理器体系结构
现在微处理器可以说是人类创造出的最复杂的系统之一。
寄存器:存储数据或指令。
条件码:保存状态并控制输出条件。
指令编码设计:代码和操作码(代码类似分区码的设计,区分一类指令,这样可以简化电路设计)。
CISC:文档1200多页,后续终将无人维护或变的不容易维护,指令丰富开发方便。
RISC:指令少于100个,不支持乘法等复杂指令,开发成本高。
HCL:逻辑设计和硬件控制语言,从门电路开始的逻辑电路设计。
CPU的整体升级思想:将处理组织成阶段。
取指:从内存读取指令字节,分为icode和ifunc,类似分区码(区分一类操作)和操作。
译码:从寄存器读入最多两个操作数(这段写的不是很明白)。
执行:算数逻辑单元ALU要么执行操作,要么增加或减少栈指针。
访存:将数据写入内存,或者从内存读出数据。
写回:最多可写两个结果到寄存器文件。
更新PC:将PC(程序计数器)设置成下一条指令地址。
这章设计了一个Y86-64简化版处理器,说明了设计中遇到的问题及方案。
SEQ架构:所有的硬件单元处理都在一个时钟周期内完成。
通过Y86-64+SEQ架构,一个流水线型的CPU基本完成。
SEQ的原则:从不回读,从来不需要为了完成一条指令的执行而去读由该指令更新了的状态。
流水线布局的局限性:
- 不一致的划分:时钟速率是由最慢的阶段的延迟限制的。
- 流水线过深,收益反而下降:将最慢的阶段划分为更小的阶段来提升效率,单阶段之间的寄存器增加了指令整体延时。
流水线冒险(指令间相关)
- 数据相关:下一条依赖这条计算的结果。
- 控制相关:这一条需要确定下一条指令的位状态。
两种相关导致的流水线计算错误称为冒险。
解决冒险的方案:
- 插入暂停来避免数据冒险,这样性能不好。
- 用转发来避免数据冒险,将结果传给较早阶段的技术称为数据转发或旁路。
- 加载/使用数据冒险:将暂停和转发结合,避免加载/使用数据冒险。
- 避免控制冒险:使用插入气泡指令的方式取消控制预测错误指令,浪费一些计算时钟。
异常处理:各个阶段错误处理机制。
形式化验证:
- 背景:即使一个设计通过了广泛的测试,我们也不能保证对于所有可能的程序,它都能正确运行。
- 方案:形式化验证新方法能够保证有工具能够严格的考虑一个系统所有可能的行为,并确定是否有设计错误。
- (认知和现实:无论数学还是其他所有学科,都是基于认识和抽象的总结,而所有的认识和抽象都有信息折损,故无法适配所有场景,故个人认为形式化验证所有可能的行为也是伪命题,应该是尽可能多,而不是所有可能的行为)
程序如何优化性能
高效程序的原则:
- 必须选择一组适当的算法和数据结构。
- 必须编写出编译器能够有效优化转化为高效可执行代码的源代码。
- 仔细研究内循环代码是分析低性能一个很好的开端。
- 了解编译器优化和局限性是性能优化的基础。
- 过程调用会带来较大开销,而且妨碍大多数形式的程序优化。
- 消除不必要的内存引用:例如减少全局数据访问,可以优化空间局部性,进而减少内存引用。
- 寄存器溢出:例如循环变量的数量超过寄存器数量称为寄存器溢出,现代x86-64处理器有16个寄存器,超过了会在内存栈中分配,增加内存访问次数,降低性能。
- 分支预测和预测错误处罚:cpu执行时进行分支预测加载下一条指令进行处理,若预测错误则下一条或几条的处理浪费为预测错误处罚。
- 书写适合用条件传送实现的代码:大部分依赖数据的判断是很难做分支预测的。
- 内存性能:考虑空间局部性,尽量在寄存器、L1、L2、L3最近的存储中命中指令和依赖的数据。
存储器的层次结构
存储器系统是一个具有不同容量、成本和访问时间的存储设备的层次结构。
访问速度:
- 寄存器:0个时钟。
- 高速缓存:4-75个时钟。
- 主存:上百个时钟。
- 磁盘:千万个时钟。
随机访问存储器:
- SRAM:双稳态存储器单元。
- DRAM:电容充放电。
- 传统的DRAM:每个芯片中单元分为d个超单元,每个超单元由w个DRAM单元组成。
- 内存模块:封装DRAM芯片,插到主板扩展槽,240个双列直插内存模块-DIMM。
- 增强型DRAM:又称FPM DRAM(内存里增加了缓存?提升速度)(大学聚完餐带电插DDRII的条,插反后瞬间冒烟短路了)。。
非易失性存储器:
- ROM:一次编程。
- ERPROM:可擦写可编程。
- 闪存:基于EEPROM(手机、相机、笔记本等场景使用)。
磁盘存储:
- 磁盘读取为毫秒级,比DRAM慢了10万倍,比SRAM慢100万倍。
- 磁盘组成:盘片、主轴(5400-15000转每秒)、磁盘驱动器。
- 磁盘容量:记录密度、磁道密度、面密度。
- 寻道时间:移动传动臂所需时间称为寻道时间。
固态硬盘:(SSD)
- 基于闪存技术,是磁盘的有效替代品。
存储技术趋势:
- 越来越快:
- 1985年,SRAM150ns,2015年,1.3ns,提升115倍。
- 1985年,DRAM200ns,2015年,20ns,提升10倍。
- 1985年,磁盘75ms,2015年,3ms,提升25倍。
- 1985年,cpu时钟周期166ns,2015年,0.33ns,提升500倍。
- 越来越便宜:(美元每G)
- 1985年,SRAM2900美元,2015年,25美元,便宜116倍。
- 1985年,DRAM880美元,2015年,0.02美元,便宜4 4000倍。
- 1985年,磁盘10 0000,2015年0.03,便宜333 3333。
局部性:引用临近于其他最近引用过的数据项的数据项。
- 时间局部性:被引用过一次的内存位置很可能在不远的将来多次被引用。
- 空间局部性:被引用过一次的内存位置,将来引用附近的一个内存位置。
缓存:
- 命中:在当前使用层缓存中存在,
- 不命中:冷缓存,通过放置策略进行填充。
- 放置填充碰撞:LRU等替换。
缓存对性能影响参数:
- 不命中率:不命中数/引用总数
- 命中率:1-不命中率
- 命中时间:读取传输所需时间
- 不命中处罚:不命中的额外时间,L1处罚为10个周期,L3处罚为50个周期,主存处罚为200个周期。
- 缓存大小:较大的可以提高命中率,成本上升。
- 块大小:较大块不命中处罚增加。
- 相联度影响:是命中时间和不命中处罚的折中。
- 写策略影响:越往下越倾向于写回,而不是直写。
程序是如何组织运行的
链接器把程序各个部分联合成一个文件,处理器加载文件到内存,执行它,好像这个程序是在独占使用处理器和主存,实际上,在任何时刻,系统上都有多个程序在运行。
编译器驱动程序:常含语言预处理、编译器、汇编器和链接器。
静态链接:完成符号解析和重定位两个任务。
目标文件分类:可重定位目标文件、可执行目标文件、共享目标文件。
加载:将可执行目标文件的代码和数据从磁盘复制到内存中。
动态链接共享库:解决依赖的共用库更新后重复编译和操作的问题。
库打桩:linux链接器技术,允许截获共享库的调用,而执行自己的代码。
系统是如何控制异常的
控制流:假设从加电到断电,程序计数器假设一个值序列,a0,a1,…,an-1,从ak到ak+1的过渡成为控制转移,这样的转移序列称为处理器的控制流。
异常控制流(ECF exception control flow):对系统控制流发生突变做出反应的处理机制。
异常:一部分又硬件实现,一部分由操作系统实现,是控制流中的突变。
异常表:处理器处理事件的跳转表。
异常类别:中断、陷阱、故障、终止。
中断:处理器外部的IO信号。
陷阱和系统调用:陷阱是有意的异常,最重要的用途是在用户和内核之间提供一个像过程一样的接口,叫做系统调用。
故障:由错误情况引起。
终止:由不可恢复的致命错误造成的结果。
上下文切换:内核中一种较高层次的异常控制流来实现多任务。
信号:软件形式的异常,允许进程和内核中断其他进程。
如何编写读写相同存储位置的并发流程序的问题,困扰着数代计算机科学家。
这章介绍了异常及分类,异常在硬件及软件中的使用,进程处理,信号处理等应用场景。
内存的管理方式:虚拟内存
虚拟内存:为了更加有效的管理内存并且少出错,现代系统提供了一种对主存的抽象概念,叫做虚拟内存。
物理地址、虚拟地址、地址翻译。
内存管理单元:CPU芯片上的专用硬件,利用存放在主存中的查询表来动态翻译虚拟地址,该表的内容由操作系统管理。
物理页:也称为页帧,是物理内存分割的基本单位。
页命中、缺页。
多级页表:增加检索效率,和mysql B+树,redis的跳表异曲同工。
内存映射:将一个虚拟内存的区域与一个磁盘上的对象关联起来,以初始化这个虚拟内存区域的内容。
写时复制(copy on write):私有对象使用的一种被映射到虚拟内存中的技术。
内存申请和释放:malloc、free。
碎片:当有未使用的内存,但不能用来满足分配请求时。
内存分配问题和内存回收问题演进封装为内存分配器和垃圾收集器及各种算法。
系统如何读写文件
输入/输出:是在主存和外部设备之间复制数据的过程。
linux文件分类:普通文件、目录文件和套接字文件。
路径类型:绝对路径和相对路径。
打开文件的表示:描述符表、文件表、v-node表。
系统如何连接网络
所有的网络应用都是基于相同的基本编程模型,有着相似的整体逻辑结构,并且依赖相同的编程接口。
一个套接字就是通信的一个端点,从linux的角度来看,套接字就是一个有相应描述符的打开文件。
connect bind listen accept
CGI使用了大量的环境变量。
处理规模提升之并发编程
现代操作系统提供的三种基本结构构造并发的程序:进程、I/O多路复用、线程。
进程:fork exec waitpid
I/O多路复用:select poll epoll,优点是没有进程上下文切换比较快,缺点是编码复杂,代码比基于进程的服务器多三倍(?)。
线程:是运行在进程上下文中的逻辑流。
线程ID:TID
每个线程有独立的线程上下文:线程ID、栈、栈指针、程序计数器、条件码、目的寄存器等。
寄存器是从不共享的,而虚拟内存总是共享的。
临界区 互斥 不安全区
信号量与互斥锁。
同步开销巨大,要尽可能避免,如果无可避免,必须要用尽可能多的有用计算弥补这个开销。
线程安全:当且仅当多个并发线程反复调用时,一直产生正确的结果。
可重入性:多个线程调用时,不会引用任何共享数据。
死锁:一组线程被阻塞了,等待一个永远不会为真的条件。
用书
- 对计算机更加深入的理解。
- 性能优化的方向和原理。
- 计算机发展趋势及技术选型。