硬件
冯诺依曼结构
- 运算器
- 控制器
- 存储器
- 输入
- 输出
现代计算机结构
- CPU
- 位宽 32位 4B/64位 8B
- 32位CPU 最大只能操作2^32=4GB内存
- 寄存器
- 指令寄存器(存当前指令) 通用寄存器(存数据) 程序寄存器(存下一条指令的内存地址)
- 控制器
- 逻辑运算单元
CPU 执行程序的过程
- 第一步,CPU 读取「程序计数器」的值,这个值是指令的内存地址,然后 CPU 的「控制单元」操作「地址总线」指定需要访问的内存地址,接着通知内存设备准备数据,数据准备好后通过「数据总线」将指令数据传给 CPU,CPU 收到内存传来的数据后,将这个指令数据存入到「指令寄存器」。
- 第二步,「程序计数器」的值自增,表示指向下一条指令。这个自增的大小,由 CPU 的位宽决定,比如 32 位的 CPU,指令是 4 个字节,需要 4 个内存地址存放,因此「程序计数器」的值会自增 4;
- 第三步,CPU 分析「指令寄存器」中的指令,确定指令的类型和参数,如果是计算类型的指令,就把指令交给「逻辑运算单元」运算;如果是存储类型的指令,则交由「控制单元」执行;
磁盘
存储器结构
- 寄存器
- CPU Cache
- L1 Cache
- 数据缓存
- 指令缓存
- L2 Cache
- L3 Cache
- 内存
- DRAM
- SSD/HDD
Cache
Cache数据由内存读取,一块一块地读的。 一块数据称为Cache Line
CPU在读数据时,无论数据是否在Cache中,都会先访问Cache。只有当Cache中找不到数据时才访问内存,并且把内存的数据读入Cache。
CPU如何访问Cache?以直接映射Cache为例
Cache与内存的映射关系
通过取模得到。
举个例子,内存共被划分为 32 个内存块,CPU Cache 共有 8 个 CPU Cache Line,假设 CPU 想要访问第 15 号内存块,如果 15 号内存块中的数据已经缓存在 CPU Cache Line 中的话,则是一定映射在 7 号 CPU Cache Line 中,因为 15 % 8 的值是 7
Cache Line中的Tag会标记该CacheLine 对应的内存块位置。
内存访问地址
- 组标记(TAG)
- cache line索引 Index
- 偏移量 Offset
如果内存中的数据已经在 CPU Cache 中了,那 CPU 访问一个内存地址的时候,会经历这 4 个步骤:
- 根据内存地址中索引信息,计算在 CPU Cache 中的索引,也就是找出对应的 CPU Cache Line 的地址;
- 找到对应 CPU Cache Line 后,判断 CPU Cache Line 中的有效位,确认 CPU Cache Line 中数据是否是有效的,如果是无效的,CPU 就会直接访问内存,并重新加载数据,如果数据有效,则往下执行;
- 对比内存地址中组标记和 CPU Cache Line 中的组标记,确认 CPU Cache Line 中的数据是我们要访问的内存数据,如果不是的话,CPU 就会直接访问内存,并重新加载数据,如果是的话,则往下执行;
- 根据内存地址中偏移量信息,从 CPU Cache Line 的数据块中,读取对应的字。
Cache提升命中率
数据缓存:按照内存布局顺序访问,将可以有效的利用 CPU Cache 带来的好处
指令缓存:让分支预测器能有效工作。
多核CPU缓存命中率:线程在不同核心来回切换,各个核心的缓存命中率就会受到影响。可以把线程绑定在某一个 CPU 核心上,这样性能可以得到非常可观的提升。
数据一致性
数据写入内存时,如何保证内存数据和Cache一致。
写直达
数据同时写入内存和Cache(如果数据在Cache中的话)中。
简单但是性能不好,浪费写入时间
写回
发生写操作时,新数据如果在Cache中,先写到Cache Block里并标记为脏。数据如果不在Cache中,则定位对应的Cache Block,如果该Block标为脏,则将其中的数据写回内存,然后从内存读取需要写入的内存块到Cache Block中,将数据写到Cache Block中,并标记为脏。
内存
虚拟内存
- 我们程序所使用的内存地址叫做虚拟内存地址(Virtual Memory Address)
- 实际存在硬件里面的空间地址叫物理内存地址(Physical Memory Address)。
- 进程持有的虚拟地址会通过 CPU 芯片中的内存管理单元(MMU)的映射关系,来转换变成物理地址,然后再通过物理地址访问内存。
操作系统通过内存分段(早期)或内存分页来管理虚拟地址映射。
内存分段
程序是由若干个逻辑分段组成的,如可由代码分段、数据分段、栈段、堆段组成。不同的段是有不同的属性的,所以就用分段(Segmentation)的形式把这些段分离出来。
分段=段选择因子(段号+标志位) + 段内偏移量
- 段选择因子:保存在段寄存器内
- 段号:段表的索引
- 段表:段的基地址、段界限、特权级
- 段偏移量:0到段界限之间
- 程序被分为四个段
- 分段的不足之处
- 内存碎片
- 虽然分段可以做到内存按需分配,程序内部不会出现内部的内存碎片。但是由于每个段长度不一,当旧程序关闭后,会产生不连续的内存空间,产生外部内存碎片,导致新程序可能无法装载。
- 频繁内存交换,效率低
- 将已使用的段交换到硬盘中。然后再将这部分的数据存入连续的段中,拼凑内存碎片空间。
- 硬盘读写速度慢,因此内存交换费时。
- 好处
- 能产生连续的内存空间,
内存分页
解决分段的内存碎片多,内存交换的效率低的问题。
将内存分为一段段的固定大小,即是页。Linux中一页大小为4KB。
通过页表映射虚拟地址和物理地址。
页表是存储在内存里的,内存管理单元 (MMU)将虚拟内存地址转换成物理地址。
而当进程访问的虚拟地址在页表中查不到时,系统会产生一个缺页异常,进入系统内核空间分配物理内存、更新进程页表,最后再返回用户空间,恢复进程的运行。
分页如何解决分段的缺陷
分页机制使得内存可以按固定大小划分,因此页之间是紧密排列的,不会出现外部缺陷。但是如果程序不足一页的大小,也得分配一个页给它。会存在页内的内部内存碎片。
内存空间不够时,操作系统可以把最近没被使用的内存页面换出(写入硬盘中),一次性写入磁盘的也只有少数的页,时间开销少。
甚至可以只有在程序运行中,需要用到对应虚拟内存页里面的指令和数据时,再加载到物理内存里面去。
分页机制如何将虚拟地址映射到物理地址
- 虚拟地址=页号+偏移量
- 页表:维护虚拟页号对应的物理页所在内存的基址
考虑32位环境下,虚拟地址空间有4GB,即是2^32个B。一个页大小为4KB(2^12B),则需要用2^20的页表项。一个页表项有4B,则需要一个2^22 = 4MB的空间用于维护页表。
100个进程就需要400MB。开销很大。
多级页表
上述情况下,将4MB的单级页表再次分页,一级页表分为1024个二级页表(10b),二级页表包含1024个页表项(10b)。一页有4KB,需要4K地址,需要12b维护。
一共32bit。
一级页表可以覆盖所有的虚拟地址空间,需要4B*1024 = 4KB大小,二级页表则可以在需要时再创建。
级数越多,页表占用空间越少。
TLB:Translation Lookaside Buffer 页表缓存
段页式内存管理
- 先将程序划分为多个有逻辑意义的段,也就是前面提到的分段机制;
- 接着再把每个段划分为多个页,也就是对分段划分出来的连续空间,再划分固定大小的页;
- 段号、段内页号和页内位移
- 段表(段号->页表) 页表(页号->物理页号)
Linux内存管理
- 进程在用户态时,只能访问用户空间内存;
- 只有进入内核态后,才可以访问内核空间的内存;
用户空间内存
- 代码段,包括二进制可执行代码;
- 数据段,包括已初始化的静态常量和全局变量;
- BSS 段,包括未初始化的静态变量和全局变量;
- 堆段,包括动态分配的内存,从低地址开始向上增长;
- 文件映射段,包括动态库、共享内存等,从低地址开始向上增长(跟硬件和内核版本有关(opens new window));
- 栈段,包括局部变量和函数调用的上下文等。栈的大小是固定的,一般是 8 MB。当然系统也提供了参数,以便我们自定义大小;
- 保留区:不可访问的内存保留区,防止程序因为出现 bug,导致读或写了一些小内存地址的数据,而使得程序跑飞。
进程管理
线程与进程的比较
- 进程是资源(包括内存、打开的文件等)分配的单位,线程是 CPU 调度的单位;
- 进程拥有一个完整的资源平台,而线程只独享必不可少的资源,如寄存器和栈;
- 线程同样具有就绪、阻塞、执行三种基本状态,同样具有状态之间的转换关系;
- 线程能减少并发执行的时间和空间开销;
对于线程相比进程能减少开销,体现在:
- 线程的创建时间比进程快,因为进程在创建的过程中,还需要资源管理信息,比如内存管理信息、文件管理信息,而线程在创建的过程中,不会涉及这些资源管理信息,而是共享它们;
- 线程的终止时间比进程快,因为线程释放的资源相比进程少很多;
- 同一个进程内的线程切换比进程切换快,因为线程具有相同的地址空间(虚拟内存共享),这意味着同一个进程的线程都具有同一个页表,那么在切换的时候不需要切换页表。而对于进程之间的切换,切换的时候要把页表给切换掉,而页表的切换过程开销是比较大的;
- 由于同一进程的各线程间共享内存和文件资源,那么在线程之间数据传递的时候,就不需要经过内核了,这就使得线程之间的数据交互效率更高了;
进程通信
1. 管道
- 匿名管道
- 管道是单向的,因此父子之间的进程双向通信需要建立两个管道
- 命名管道
- 可以在不相关的进程之间通信
2. 消息队列
- 数据单元为消息体,是用户自定义的数据类型 大小固定
- 缺点
- 通信不及时
- 大小有限制,不适合大数据的传输
- 通信过程中存在用户态和内核态之间的数据拷贝开销
3. 共享内存
- 共享内存的机制,就是拿出一块虚拟地址空间来,映射到相同的物理内存中。
4. 信号量
- 信号量其实是一个整型的计数器,主要用于实现进程间的互斥与同步,而不是用于缓存进程间通信的数据。
- 信号初始化为 1,就代表着是互斥信号量
- 信号初始化为 0,就代表着是同步信号量,它可以保证进程 A 应在进程 B 之前执行。
5. 信号
- 信号是进程间通信机制中唯一的异步通信机制,因为可以在任何时候发送信号给某一进程,一旦有信号产生,我们就有下面这几种,用户进程对信号的处理方式。
- 1.执行默认操作。Linux 对每种信号都规定了默认操作,例如,上面列表中的 SIGTERM 信号,就是终止进程的意思。
- 2.捕捉信号。我们可以为信号定义一个信号处理函数。当信号发生时,我们就执行相应的信号处理函数。
- 3.忽略信号。当我们不希望处理某些信号的时候,就可以忽略该信号,不做任何处理。有两个信号是应用进程无法捕捉和忽略的,即 SIGKILL 和 SEGSTOP,它们用于在任何时候中断或结束某一进程。
线程同步
线程互斥
使用互斥来让线程避免对临界资源的竞争
线程同步
并发进程/线程在一些关键点上可能需要互相等待与互通消息,这种相互制约的等待与互通信息称为进程/线程同步。
使用锁或者信号量实现线程互斥和线程同步
锁
自旋锁,即是忙等待锁
当获取不到锁时,线程就会一直 while 循环,不做任何事情。会忙等待
自旋锁是最比较简单的一种锁,一直自旋,利用 CPU 周期,直到锁可用。
开销少,在多核系统下一般不会主动产生线程切换,适合异步、协程等在用户态切换请求的编程方式,但如果被锁住的代码执行时间过长,自旋的线程会长时间占用 CPU 资源,所以自旋的时间和被锁住的代码执行的时间是成「正比」的关系,我们需要清楚的知道这一点。
互斥锁
- 互斥锁加锁失败后,线程会释放 CPU ,给其他线程;
- 会有两次线程上下文切换(切换线程的私有数据、寄存器等不共享的数据)的成本:
- 当线程加锁失败时,内核会把线程的状态从「运行」状态设置为「睡眠」状态,然后把 CPU 切换给其他线程运行;
- 接着,当锁被释放时,之前「睡眠」状态的线程会变为「就绪」状态,然后内核会在合适的时间,把 CPU 切换给该线程运行。
- 使用场景:能确定被锁住的代码执行时间很短,就不应该用互斥锁,而应该选用自旋锁,否则使用互斥锁。
读写锁
读写锁适用于能明确区分读操作和写操作的场景。
- 当「写锁」没有被线程持有时,多个线程能够并发地持有读锁,这大大提高了共享资源的访问效率,因为「读锁」是用于读取共享资源的场景,所以多个线程同时持有读锁也不会破坏共享资源的数据。
- 但是,一旦「写锁」被线程持有后,读线程的获取读锁的操作会被阻塞,而且其他写线程的获取写锁的操作也会被阻塞。
「读优先锁」
「写优先锁」
「公平读写锁」
乐观锁
乐观锁做事比较乐观,它假定冲突的概率很低
工作方式是:
- 先修改完共享资源,再验证这段时间内有没有发生冲突
- 如果没有其他线程在修改资源,那么操作完成
- 如果发现有其他线程已经修改过这个资源,就放弃本次操作。
只有在冲突概率非常低,且加锁成本非常高的场景时,才考虑使用乐观锁。
悲观锁
前面提到的互斥锁、自旋锁、读写锁,都是属于悲观锁。
悲观锁做事比较悲观,它认为多线程同时修改共享资源的概率比较高,于是很容易出现冲突,所以访问共享资源前,先要上锁。
信号量
- P 操作:将 sem 减 1,相减后,如果 sem < 0,则进程/线程进入阻塞等待,否则继续,表明 P 操作可能会阻塞;
- V 操作:将 sem 加 1,相加后,如果 sem <= 0,唤醒一个等待中的进程/线程,表明 V 操作不会阻塞;
死锁避免
死锁只有同时满足以下四个条件才会发生:
- 互斥条件;
- 多个线程不能同时使用同一个资源。
- 持有并等待条件;
- 持有并等待条件是指,当线程 A 已经持有了资源 1,又想申请资源 2,而资源 2 已经被线程 C 持有了,所以线程 A 就会处于等待状态,但是线程 A 在等待资源 2 的同时并不会释放自己已经持有的资源 1。
- 不可剥夺条件;
- 线程已经持有了资源 ,在自己使用完之前不能被其他线程获取
- 环路等待条件;
- 两个线程获取资源的顺序构成了环形链。
利用工具排查死锁
Java jstack
C pstack+gdb
避免方式
最常见的并且可行的就是使用资源有序分配法,来破环环路等待条件。
调度算法
进程调度
FIFO
FCFS 对长作业有利,适用于 CPU 繁忙型作业的系统,而不适用于 I/O 繁忙型作业的系统。
短作业优先
显然对长作业不利
高响应比优先
时间片轮转
- 如果时间片用完,进程还在运行,那么将会把此进程从 CPU 释放出来,并把 CPU 分配另外一个进程;
- 如果该进程在时间片结束前阻塞或结束,则 CPU 立即进行切换;
时间片长度设置:
- 如果时间片设得太短会导致过多的进程上下文切换,降低了 CPU 效率;
- 如果设得太长又可能引起对短作业进程的响应时间变长。
最高优先级调度
多用户计算机系统希望调度有优先级。
进程的优先级可以分为,静态优先级或动态优先级:
- 静态优先级:创建进程时候,就已经确定了优先级了,然后整个运行时间优先级都不会变化;
- 动态优先级:根据进程的动态变化调整优先级,比如如果进程运行时间增加,则降低其优先级,如果进程等待时间(就绪队列的等待时间)增加,则升高其优先级,也就是随着时间的推移增加等待进程的优先级。
非抢占式和抢占式:
- 非抢占式:当就绪队列中出现优先级高的进程,运行完当前进程,再选择优先级高的进程。
- 抢占式:当就绪队列中出现优先级高的进程,当前进程挂起,调度优先级高的进程运行。
缺点:导致低优先级的进程永远不会运行。
多级反馈队列
「时间片轮转算法」和「最高优先级算法」的综合和发展。
- 设置了多个队列,赋予每个队列不同的优先级,每个队列优先级从高到低,同时优先级越高时间片越短;
内存页面置换算法
缺页中断
与一般中断的主要区别在于:
- 缺页中断在指令执行「期间」产生和处理中断信号,而一般中断在一条指令执行「完成」后检查和处理中断信号。
- 缺页中断返回到该指令的开始重新执行「该指令」,而一般中断返回回到该指令的「下一个指令」执行。
- 状态位:用于表示该页是否有效,也就是说是否在物理内存中,供程序访问时参考。
- 访问字段:用于记录该页在一段时间被访问的次数,供页面置换算法选择出页面时参考。
- 修改位:表示该页在调入内存后是否有被修改过,由于内存中的每一页都在磁盘上保留一份副本,因此,如果没有修改,在置换该页时就不需要将该页写回到磁盘上,以减少系统的开销;如果已经被修改,则将该页重写到磁盘上,以保证磁盘中所保留的始终是最新的副本。
- 硬盘地址:用于指出该页在硬盘上的地址,通常是物理块号,供调入该页时使用。
最佳页面置换
置换在「未来」最长时间不访问的页面。最理想的情况。
先进先出
驻留时间最长的页将被换掉。
最近最久未使用LRU
选择最长时间没有被访问的页面进行置换
优点:性能好
缺点:实现代价高,需要维护一个所有页面的链表,最近最多使用的页面在表头,最近最少使用的页面在表尾。每次访问内存时都必须要更新「整个链表」。
时钟页面置换
把所有的页面都保存在一个类似钟面的「环形链表」中,一个表针指向最老的页面。
当发生缺页中断时,算法首先检查表针指向的页面:
- 如果它的访问位位是 0 就淘汰该页面,并把新的页面插入这个位置,然后把表针前移一个位置;
- 如果访问位是 1 就清除访问位,并把表针前移一个位置,重复这个过程直到找到了一个访问位为 0 的页面为止;
最不常用算法
不是指这个算法不常用,而是当发生缺页中断时,选择「访问次数」最少的那个页面,并将其淘汰。
对每个页面设置一个「访问计数器」,每当一个页面被访问时,该页面的访问计数器就累加 1。在发生缺页中断时,淘汰计数器值最小的那个页面。
缺点:
- 需要考虑效率和硬件成本的。
- 只考虑了频率问题,没考虑时间的问题。
磁盘调度
先来先服务
最短寻道时间优先
缺陷:存在某些请求的饥饿
扫描算法
电梯算法
中间部分的磁道会比较占便宜,中间部分相比其他部分响应的频率会比较多
循环扫描
只有磁头朝某个特定方向移动时,才处理磁道访问请求,而返回时直接快速移动至最靠边缘的磁道
Comments NOTHING