基本结构
冯诺依曼计算机模型
现代计算机模型是基于冯诺依曼计算机模型。
计算机在运行时,先从内存中取出第一条指令,通过控制器的译码,按指令的要求,从存储器中取出数据进行指定的运算和逻辑操作等加工,然后再按地址把结果送到内存中去。
接下来,再取出第二条指令,在控制器的指挥下完成规定操作,依此进行下去。直至遇到停止指令。
计算机组成部分:
控制器(Control):
- 功能是对程序规定的控制信息进行解释,根据其要求进行控制,调度程序、数据、地址,协调计算机各部分工作及内存与外设的访问等。
运算器(Datapath):
- 运算器的功能是对数据进行各种算术运算和逻辑运算,即对数据进行加工处理。
存储器(Memory):
- 存储器的功能是存储程序、数据和各种信号、命令等信息,并在需要时提供这些信息。
输入(Input system):
- 输入设备与输出设备合你为外部设备,简称外设,输入设备的作用是将程序、原始数据、文字、字符、控制命令或现场采集的数据等信息输入到计算机。
- 常见的输入设备有键盘、鼠标器、光电输入机、磁带机、磁盘机、光盘机等。
输出(Output system):
- 它把外算机的中间结果或最后结果、机内的各种数据符号及文字或各种控制信号等信息输出出来。
- 微机常用的输出设备有显示终端CRT、打印机、激光印字机、绘图仪及磁带、光盘机等。
磁盘
磁盘调度算法
读写一个磁盘块的时间的影响因素有:
- 旋转时间(主轴转动盘面,使得磁头移动到适当的扇区上)
- 寻道时间(制动手臂移动,使得磁头移动到适当的磁道上)
- 实际的数据传输时间
其中,寻道时间最长,因此磁盘调度的主要目标是使磁盘的平均寻道时间最短。
先来先服务
FCFS, First Come First Served,按照磁盘请求的顺序进行调度。
优点是公平和简单,缺点是:因为未对寻道做任何优化,使平均寻道时间可能较长。
最短寻道时间优先
SSTF,优先调度与当前磁头所在磁道距离最近的磁道。
虽然平均寻道时间比较低,但是不够公平。
如果新到达的磁道请求总是比一个在等待的磁道请求近,那么在等待的磁道请求会一直等待下去,也就是出现饥饿现象。
具体来说,两端的磁道请求更容易出现饥饿现象。
电梯算法
电梯算法(扫描算法)和电梯的运行过程类似,总是按一个方向来进行磁盘调度,直到该方向上没有未完成的磁盘请求,然后改变方向。
因为考虑了移动方向,因此所有的磁盘请求都会被满足,解决了 SSTF 的饥饿问题。
进程
进程和线程
进程:正在执行的应用程序,线程是轻量级的进程, 进程是分配资源的基础单位。
线程:轻量级进程,是程序执行的基本单位。
线程是进程的一部分,一个线程只能属于一个进程,一个进程可以有多个线程,但至少有一个线程。
每个进程都有独立的代码和数据空间(程序上下文),程序间的切换开销大,每个线程都有自己独立的运行栈和程序计数器(PC),线程间切换开销小。
互斥和同步区别
互斥:是指在不同进程之间的若干程序片断,当某个进程运行其中一个程序片段时,其它进程就不能运行它们之中的任一程序片段,只能等到该进程运行完这个程序片段后才可以运行。
同步:是指在不同进程之间的若干程序片断,它们的运行必须严格按照规定的 某种先后次序来运行,这种先后次序依赖于要完成的特定的任务。
孤儿进程
一个父进程退出,而它的一个或多个子进程还在运行,那么那些子进程将成为孤儿进程。
孤儿进程将被init进程所收养,并由init进程对它们完成状态收集工作。
僵尸进程
一个进程使用fork创建子进程,如果子进程退出,而父进程没有调用wait或waitpid获取子进程的状态信息,那么子进程的进程描述符仍然保存在系统中,这种进程(这个子进程)称之为僵尸进程。
如何清除僵尸进程?
改写父进程,为子进程收尸:具体做法是接收SIGCHLD信号,子进程死后会发送SIGCHLD信号给父进程,父进程收到此信号后,执行waitpid()函数为其(子进程)进行收尸。
就算父进程没有调用wait,内核也会向它发送SIGCHLD消息,默认处理为忽略,我们可以设置一个函数来对其进行处理。
如果把这个子进程(僵尸进程)的父进程杀掉,僵尸进程会变为孤儿进程,由init进程进行管理,init负责进行清理僵尸进程。
守护进程
守护进程就类似于一个后台进程。
进程状态
创建状态:
- 进程由创建而产生。
就绪状态:
- 进程已经准备好运行的状态,即进程已分配到除CPU以外所有的必要资源后,只要再获得CPU,便可立即执行。
运行状态:
- 进程已经获取CPU,其进程处于正在执行的状态。
阻塞状态:
- 正在执行的进程由于发生某事件(如I/O请求、申请缓冲区失败等)暂时无法继续执行的状态,即进程执行受到阻塞。
终止状态
进程通信
管道:
写入的数据都是缓存在内核中,另一个进程读取数据时候自然也是从内核中获取,同时通信数据都遵循先进先出原则。
管道这种通信方式效率低,不适合进程间频繁地交换数据。
消息队列:
消息队列不适合比较大数据的传输,因为在内核中每个消息体都有一个最大长度的限制。
消息队列通信过程中,存在用户态与内核态之间的数据拷贝开销,因为进程写入数据到内核中的消息队列时,会发生从用户态拷贝数据到内核态的过程,同理另一进程读取内核中的消息数据时,会发生从内核态拷贝数据到用户态的过程。
共享内存:
共享内存的机制,就是拿出一块虚拟地址空间来,映射到相同的物理内存中。
这样这个进程写入的东西,另外一个进程马上就能看到了,都不需要拷贝来拷贝去,传来传去,大大提高了进程间通信的速度。
信号量:
用了共享内存通信方式,带来新的问题,那就是如果多个进程同时修改同一个共享内存,很有可能就冲突了。
例如两个进程都同时写一个地址,那先写的那个进程会发现内容被别人覆盖了 。
为了防止多进程竞争共享资源,而造成的数据错乱,所以需要保护机制,使得共享的资源,在任意时刻只能被一个进程访问。
正好,信号量就实现了这一保护机制。
信号量其实是一个整型的计数器,主要用于实现进程间的互斥与同步,而不是用于缓存进程间通信的数据。
信号:
信号是进程间通信机制中唯一的异步通信机制,因为可以在任何时候发送信号给某一进程。
Socket:
要想跨网络与不同主机上的进程之间通信,就需要 Socket 通信了。
操作系统执行一个程序的过程
操作系统检测类型是否是可执行文件。
创建进程,并且将可执行文件映射到该进程。
为该进程设置CPU上下文环境。
将代码和数据从磁盘读入内存。
运行过程中发生缺页异常则重复4。
死锁
多个并发进程中,如果每个进程持有某种资源而又等待其它进程释放其他资源,在未改变这种状态之前都不能向前推进,多个进程无限期相互等待 的一种状态。
四个必要条件
死锁产生的 4 个条件(有一个条件不成立,则不会产生死锁):
互斥:一个资源一次只能被一个进程使用
请求与保持:一个进程因请求资源而阻塞时,对已获得资源保持不放
非抢占:进程获得的资源,在未完全使用完之前,不能强行抢占
循环等待:若干进程之间形成一种头尾相接的环形等待资源关系
死锁处理方法
死锁的四个处理方法:
鸵鸟策略:忽略掉死锁,视而不见
死锁检测与恢复:允许死锁发生,检测它们是否发生,一旦发生死锁,就采取行动解决问题
死锁避免:仔细对资源进行分配,动态地避免死锁,银行家算法是避免死锁的经典算法
死锁预防:破坏引起死锁的 4 个必要条件
银行家算法
银行家算法的主要思想是避免系统进入不安全状态。
在每次进行资源分配时,它首先检查系统是否有足够的资源满足要求,如果有,则先进行分配,并对分配后的新状态进行安全性检查。
如果新状态安全,则正式分配上述资源,否则就拒绝分配上述资源,这样,它保证系统始终处于安全状态,从而避免死锁现象的发生。
安全状态
安全状态与不安全状态的区别是,从安全状态出发,系统能够保证所有的进程都能完成;而从不安全状态出发,没有这样的保证。
活锁
活锁指进程并没有被阻塞,但由于某些条件没有满足,导致一直重复尝试、失败、尝试、失败。
进程仍可以在 CPU 上活动,但 CPU 时间片执行完了之后又下了 CPU,进程没有任何进展但也没有阻塞。
饥饿
进程无限等待的情况。饥饿 ≠ 死锁,但是饥饿至少有一个进程的执行被无限期推迟。
产生饥饿的原因:往往是由于资源分配策略的 不公平性 导致的,比如短作业优先。
此时系统虽然没有发生死锁,某些进程也可能会一直得不到 CPU 的使用权而长时间等待。
当 饥饿 到一定程度,进程任务即使完成也不再具有实际意义时称该进程被饿死。
线程
并发(Concurrent)
并发是一个CPU处理器同时处理多个线程任务。
宏观上是同时处理多个任务,微观上其实是CPU在多个线程之间快速的交替执行CPU把运行时间划分成若干个(微小)时间段,公平的分配给各个线程执行,在一个时间段的线程运行时,其他线程处于挂起状态,这种就称之为并发。
并行(Parallel)
并行是多个CPU处理器同时处理多个线程任务。
当一个CPU执行一个线程时,另一个CPU可以执行另一个线程,两个线程互不抢占CPU资源,可以同时进行,这就被称之为并行。
同步异步/阻塞非阻塞
当一个request发送出去以后,会得到一个response,这整个过程就是一个同步调用的过程。
- 哪怕response为空,或者response的返回特别快,但是针对这一次请求而言就是一个同步的调用。
当一个request发送出去以后,没有得到想要的response,而是通过后面的callback、状态或者通知的方式获得结果。
异步请求分两步:
- 调用方发送request没有返回对应的response(可能是一个空的response)
- 服务提供方将response处理完成以后通过callback的方式通知调用方
阻塞和非阻塞:
- 阻塞和非阻塞就看调用方在发送请求后是否block住了。
协程
协程是一种比线程更加轻量级的存在,协程不是被操作系统内核所管理,而完全是由程序所控制(也就是在用户态执行)。
这样带来的好处就是性能得到了很大的提升,不会像线程切换那样消耗资源。

用户态和内核态
Kernel 运行在超级权限模式(Supervisor Mode)下,所以拥有很高的权限。
按照权限管理的原则,多数应用程序应该运行在最小权限下。
因此,很多操作系统,将内存分成了两个区域:
内核空间(Kernal Space),这个空间只有内核程序可以访问。
用户空间(User Space),这部分内存专门给应用程序使用。
用户空间中的代码被限制了只能使用一个局部的内存空间,我们说这些程序在用户态(User Mode) 执行。
内核空间中的代码可以访问所有内存,我们称这些程序在内核态(Kernal Mode) 执行。
什么情况会导致用户态到内核态切换:
系统调用:用户态进程主动切换到内核态的方式,用户态进程通过系统调用向操作系统申请资源完成工作,例如 fork()就是一个创建新进程的系统调用。
异常:当 CPU 在执行用户态的进程时,发生了一些没有预知的异常,这时当前运行进程会切换到处理此异常的内核相关进程中,也就是切换到了内核态,如缺页异常。
中断:当 CPU 在执行用户态的进程时,外围设备完成用户请求的操作后,会向 CPU 发出相应的中断信号,这时 CPU 会暂停执行下一条即将要执行的指令,转到与中断信号对应的处理程序去执行,也就是切换到了内核态。
- 如硬盘读写操作完成,系统会切换到硬盘读写的中断处理程序中执行后边的操作等。
用户态和内核态切换的开销
保留用户态现场(上下文、寄存器、用户栈等)
复制用户态参数,用户栈切到内核栈,进入内核态
额外的检查(因为内核代码对用户不信任)
执行内核态代码
复制内核态代码执行结果,回到用户态
恢复用户态现场(上下文、寄存器、用户栈等)
异常和中断的区别
中断是由硬件设备产生的,而它们从物理上说就是电信号,之后它们通过中断控制器发送给CPU,接着CPU判断收到的中断来自于哪个硬件设备(这定义在内核中),最后,由CPU发送给内核,有内核处理中断。
异常是由CPU产生的,同时,它会发送给内核,要求内核处理这些异常。
系统调用过程:
如果用户态程序需要执行系统调用,就需要切换到内核态执行。
内核程序执行在内核态(Kernal Mode),用户程序执行在用户态(User Mode)。
当发生系统调用时,用户态的程序发起系统调用。
因为系统调用中牵扯特权指令,用户态程序权限不足,因此会中断执行,也就是 Trap(Trap 是一种中断)。
发生中断后,当前 CPU 执行的程序会中断,跳转到中断处理程序。
内核程序开始执行,也就是开始处理系统调用。
内核处理完成后,主动触发 Trap,这样会再次发生中断,切换回用户态工作。
线程调度算法
先到先服务(First Come First Service,FCFS)
就是先到的作业先被计算,后到的作业,排队进行。
最短作业优先
最短作业优先(Shortest Job First, SJF)调度算法通常会同时考虑到来顺序和作业预估时间的长短。
优先级队列(PriorityQueue)
优先级队列可以给队列中每个元素一个优先级,优先级越高的任务就会被先执行。
抢占(Preemption)
抢占就是把执行能力分时,分成时间片段。
让每个任务都执行一个时间片段。
如果在时间片段内,任务完成,那么就调度下一个任务,如果任务没有执行完成,则中断任务,让任务重新排队,调度下一个任务。
多级队列模型:多级队列,就是多个队列执行调度。
紧急任务仍然走高优队列,非抢占执行。
普通任务先放到优先级仅次于高优任务的队列中,并且只分配很小的时间片。
如果没有执行完成,说明任务不是很短,就将任务下调一层。
下面一层,最低优先级的队列中时间片很大,长任务就有更大的时间片可以用。
通过这种方式,短任务会在更高优先级的队列中执行完成,长任务优先级会下调,也就类似实现了最短作业优先的问题。
CPU
冯诺依曼模型中 CPU 负责控制和计算。
为了方便计算较大的数值,CPU 每次可以计算多个字节的数据。
如果 CPU 每次可以计算 4 个 byte,称作 32 位 CPU。
如果 CPU 每次可以计算 8 个 byte,称作 64 位 CPU。
这里的 32 和 64,称作 CPU 的位宽。
并发与并行
并发:
- 由于CPU数量或核心数量不够,多个任务并不一定是同时进行的
- 这些任务交替执行(分配不同的CPU时间片,进程或者线程的上下文切换)
并行:
- 多个任务可以在同一时刻同时执行,通常需要多个或多核处理器,不需要上下文切换,真正的并行
CPU指令集权限
Inter把
CPU指令集
操作的权限由高到低划为4级:
- ring 0
- ring 1
- ring 2
- ring 3
其中 ring 0 权限最高,可以使用所有
CPU 指令集
,ring 3 权限最低,仅能使用常规CPU 指令集
,不能使用操作硬件资源的CPU 指令集
,比如IO
读写、网卡访问、申请内存都不行,Linux系统仅采用ring 0 和 ring 3 这2个权限。ring 0被叫做内核态,完全在操作系统内核中运行
ring 3被叫做用户态,在应用程序中运行
寄存器
CPU 要进行计算,比如最简单的加和两个数字时,因为 CPU 离内存太远,所以需要一种离自己近的存储来存储将要被计算的数字。
这种存储就是寄存器。
寄存器就在 CPU 里,控制单元和逻辑运算单元非常近,因此速度很快。
寄存器中有一部分是可供用户编程用的,比如用来存加和指令的两个参数,是通用寄存器。
还有一部分寄存器有特殊的用途,叫作特殊寄存器。
比如程序指针,就是一个特殊寄存器。
它存储了 CPU 要执行的下一条指令所在的内存地址。
- 注意,程序指针不是存储了下一条要执行的指令,此时指令还在内存中,程序指针只是存储了下一条指令的地址。
下一条要执行的指令,会从内存读入到另一个特殊的寄存器中,这个寄存器叫作指令寄存器。
指令被执行完成之前,指令都存储在这里。
寄存器的数量通常在几十到几百之间,每个寄存器可以用来存储一定字节(byte)的数据。
32 位 CPU 中大多数寄存器可以存储 4 个字节;
64 位 CPU 中大多数寄存器可以存储 8 个字节。
总线
CPU 和内存以及其他设备之间,也需要通信,因此我们用一种特殊的设备进行控制,就是总线。
总线分成 3 种:
地址总线:专门用来指定 CPU 将要操作的内存地址。
数据总线:用来读写内存中的数据。
- 当 CPU 需要读写内存的时候,先要通过地址总线来指定内存地址,再通过数据总线来传输数据。
控制总线:用来发送和接收关键信号,比如中断信号,还有设备复位、就绪等信号,都是通过控制总线传输。
- 同样的,CPU 需要对这些信号进行响应,这也需要控制总线。
存储器分级
当 CPU 需要内存中某个数据的时候,如果寄存器中有这个数据,我们可以直接使用;
如果寄存器中没有这个数据,我们就要先查询 L1 缓存;L1 中没有,再查询 L2 缓存;
L2 中没有再查询 L3 缓存;L3 中没有,再去内存中拿。
L1-Cache:
- 在 CPU 中,相比寄存器,虽然它的位置距离 CPU 核心更远,但造价更低。
- 通常 L1-Cache 大小在几十 Kb 到几百 Kb 不等,读写速度在 2~4 个 CPU 时钟周期。
L2-Cache:
- 在 CPU 中,位置比 L1- 缓存距离 CPU 核心更远。
- 它的大小比 L1-Cache 更大,具体大小要看 CPU 型号,有 2M 的,也有更小或者更大的,速度在 10~20 个 CPU 周期。
L3-Cache:
在 CPU 中,位置比 L2- 缓存距离 CPU 核心更远。
大小通常比 L2-Cache 更大,读写速度在 20~60 个 CPU 周期。
L3 缓存大小也是看型号的,比如 i9 CPU 有 512KB L1 Cache;有 2MB L2 Cache; 有16MB L3 Cache。
程序的执行过程
首先,CPU 读取 PC 指针指向的指令,将它导入指令寄存器。
具体来说,完成读取指令这件事情有 3 个步骤:
CPU 的控制单元操作地址总线指定需要访问的内存地址(简单理解,就是把 PC 指针中的值拷贝到地址总线中)
CPU 通知内存设备准备数据(内存设备准备好了,就通过数据总线将数据传送给 CPU)。
CPU 收到内存传来的数据后,将这个数据存入指令寄存器。
然后,CPU 分析指令寄存器中的指令,确定指令的类型和参数。
如果是计算类型的指令,那么就交给逻辑运算单元计算;如果是存储类型的指令,那么由控制单元执行。
PC 指针自增,并准备获取下一条指令。
比如在 32 位的机器上,指令是 32 位 4 个字节,需要 4 个内存地址存储,因此 PC 指针会自增 4。
CPU100%
top –c
,显示进程运行信息列表,找到最耗CPU
的进程。
按数字1,显示多核CPU信息。
键入P,进程按照CPU使用率排序。
按M按照内存占用进行排序。
top -Hp 【PID】
,显示一个进程的线程运行信息列表,找到最耗CPU的线程。
printf %x\n 【线程pid】
,转换多个线程数字为十六进制。
jstack 【进程PID】| grep 【线程转换后十六进制】-A10
, 使用JStack获取进程PID堆栈。
- 利用
Grep
定位线程ID,打印后续10行信息。
如果
VM Thread os_prio=0 tid=0x00007f871806e000 nid=0xa runnable
,第一个是线程名。
- 如果是
VM Thread
就是虚拟机GC回收线程了。
jstack 【进程PID】> 【文件】
,将JStack
堆栈信息存储到文件。
CPU负载情况
top
15:52:00 up 42:35, 1 user, load average: 0.15, 0.05, 0.01
5:52:00
- 指的是当前时间
up 42:35
- 指的是机器已经运行了多长时间
1 user
- 指的是当前机器有1个用户在使用
load average: 0.15, 0.05, 0.01
- CPU在1分钟、5分钟、15分钟内的负载情况
假设是一个4核的CPU,此时如果你的CPU负载是0.15。
- 这就说明,4核CPU中连一个核都没用满,4核CPU基本都很空闲。
如果CPU负载是1,那说明4核CPU中有一个核已经被使用的比较繁忙了。
- 另外3个核还是比较空闲一些。
要是CPU负载是1.5,说明有一个核被使用繁忙,另外一个核也在使用。
- 但是没那么繁忙,还有2个核可能还是空闲的。
如果你的CPU负载是4,那说明4核CPU都被跑满了,如果你的CPU负载是6。
- 那说明4核CPU被繁忙的使用还不够处理当前的任务,很多进程可能一直在等待CPU去执行自己的任务。
内存
DMA(Direct Memory Access 直接内存访问)
DMA意味着在不涉及CPU的情况下依然可以读取/写入内存,即DMA不需要CPU的支持。
控制直接内存访问的过程。
DMA的优点:
缓解总线上的拥塞。
DMA设备可以直接在内存之间传输数据,而不是使用CPU作为中介。
提升系统并发,CPU可以去处理别的任务了。
页面缓存(Page Cache)
由于读写硬盘的速度比读写内存要慢很多。
为了避免每次读写文件时,都需要对硬盘进行读写操作,Linux 内核会以页大小(4KB) 为单位,将文件划分为多数据块,当用户对文件中的某个数据块进行读写操作时,内核首先会申请一个内存页(称为页缓存)与文件中的数据块进行缓存。
操作系统是如何管理虚拟地址与物理内存地址之间关系?
主要有三种方式,分别是分段、分页、段页。
内存分段
程序包含若干个逻辑分段,如可由代码段、数据段、栈段、堆段组成,每个分段都有不同的属性,所以内存以分段的形式把这些段分离出来进行管理。
分段管理下的虚拟地址由两部分组成,段号和段内偏移量。
- 通过段号映射段表的项
- 从项中获取到段基地址
- 段基地址+段内偏移量=使用的物理内存
不足之处:
- 内存碎片的问题
- 内存交换的效率低的问题

内存分页
分段的好处是能产生连续的内存空间,但是会出现大量内存碎片与内存交换效率低的问题。
分页是把整个虚拟与物理空间切成一段段固定尺寸的大小,这样一个连续并且尺寸固定的空间叫页,在 Linux 下,每一页的大小为 4KB。
虚拟地址与物理地址是通过页表来映射,虚拟空间内的虚拟地址一定是连续的,物理地址不一定,但可以通过连续的虚拟地址把多个不连续的物理内存组合使用。
页号找到页表中的页项
获取页项的物理页号基地址
偏移量+物理页号基地址计算出物理内存地址
而当进程访问的虚拟地址在页表中查不到时,系统会产生一个缺页异常,进入系统内核空间分配物理内存、更新进程页表,最后再返回用户空间,恢复进程的运行。


内存段页
段式与页式并不是相对的,他们也可以组合在一起使用,在段的基础上进行分页分级。
先将程序划分为多个有逻辑意义的段。
接着再把每个段划分为多个页,也就是对分段划分出来的连续空间,再划分固定大小的页。
虚拟地址结构由段号、段内页号和页内位移三部分组成。
通过段号获取段表的段项
通过段项获取到页表地址
通过页表地址找到段页表
通过段内页号找到段页表的段页项
通过段页项获取物理页基地址
通过物理页基地址+偏移量计算出物理内存地址

虚拟内存
实际上运行的进程并不是直接使用物理内存地址,而是把进程使用的内存地址与实际的物理内存地址做隔离,即操作系统会为每个进程分配独立的一套虚拟地址。
每个进程玩自己的地址,互不干涉,至于虚拟地址怎么映射到物理地址,对进程来说是透明的,操作系统已经把这些安排的明明白白了。
操作系统会提供一种机制,将不同进程的虚拟地址和不同内存的物理地址映射起来。

MMU内存管理单元:
在 CPU 中一个小型的设备,内存管理单元(Memory Management Unit, MMU)。
当 CPU 需要执行一条指令时,如果指令中涉及内存读写操作,CPU 会把虚拟地址给 MMU,MMU 自动完成虚拟地址到真实地址的计算;
然后,MMU 连接了地址总线,帮助 CPU 操作真实地址。
页面置换算法
在地址映射过程中,若在页面中发现所要访问的页面不在内存中,则产生缺页中断。
当发生缺页中断时,如果操作系统内存中没有空闲页面,则操作系统必须在内存选择一个页面将其移出内存,以便为即将调入的页面让出空间。
而用来选择淘汰哪一页的规则叫做页面置换算法。
最佳置换算法(OPT )
这是一种理想情况下的页面置换算法,但实际上是不可能实现的。
该算法的基本思想是:
发生缺页时,有些页面在内存中,其中有一页将很快被访问(也包含紧接着的下一条指令的那页),而其他页面则可能要到 10、100 或者 1000 条指令后才会被访问,每个页面都可以用在该页面首次被访问前所要执行的指令数进行标记。
最佳页面置换算法只是简单地规定:标记最大的页应该被置换,这个算法唯一的一个问题就是它无法实现。
当缺页发生时,操作系统无法知道各个页面下一次是在什么时候被访问。
虽然这个算法不可能实现,但是最佳页面置换算法可以用于对可实现算法的性能进行衡量比较。
先进先出置换算法(FIFO )
总是选择在主存中停留时间最长(即最老)的一页置换,即先进入内存的页,先退出内存。
- 理由是:最早调入内存的页,其不再被使用的可能性比刚调入内存的可能性大。
最近最久未使用(LRU )算法
LRU 算法是与每个页面最后使用的时间有关的。
当必须置换一个页面时,LRU 算法选择过去一段时间里最久未被使用的页面。
零拷贝
传统I/O有性能问题。
数据拷贝
在传统 I/O 中,数据的传输通常涉及多次数据拷贝。
数据需要从应用程序的用户缓冲区复制到内核缓冲区,然后再从内核缓冲区复制到设备或网络缓冲区。
这些数据拷贝过程导致了多次内存访问和数据复制,消耗了大量的 CPU 时间和内存带宽。
用户态和内核态的切换
- 由于数据要经过内核缓冲区,导致数据在用户态和内核态之间来回切换,切换过程中会有上下文的切换。
零拷贝技术用来解决以上问题。

实现零拷贝的技术主要有两种:mmap+write,sendfile
。
mmap+write
利用mmap替换read系统调用函数。
mmap系统调用函数会直接将内核缓冲区的数据映射到用户空间,这样操作系统内核与用户空间之间就不需要任何的拷贝操作。

具体流程:
应用进程调用了mmap系统调用函数之后,DMA会把磁盘缓冲区的数据拷贝到内核缓冲区中。
接着,应用进程和操作系统内核共享这个缓冲区。
应用进程再调用write函数,操作系统直接将内核缓冲区的数据拷贝到socket缓冲区。
再由DMA控制器copy到网卡。
这还不是最理想的零拷贝因为还是需要两次系统调用,四次上下文切换,3次拷贝。
sendfile
在linux内核版本2.1中,提供了一个新的系统调用函数sendfile。
- 这个系统调用函数可以代替read和write两个系统调用函数。
通过 sendfile,应用程序可以直接将文件数据从文件系统传输到网络套接字或者目标文件,而无需经过用户缓冲区和内核缓冲区。

这样系统调用的次数就变成了一次,上下文切换的次数减小到了两次,数据拷贝次数为3次。
如果网卡支持SG—DMA,就可以将数据拷贝次数减小为两次。
DMA(直接内存访问) 是一种硬件特性,允许外设(如网络适配器、磁盘控制器等)直接访问系统内存,而无需通过 CPU 的介入。
在数据传输时,DMA 可以直接将数据从内存传输到外设,或者从外设传输数据到内存,避免了数据在用户态和内核态之间的多次拷贝。

没有在内存层面区拷贝数据,全过程都没有使用CPU搬运数据,所有数据都是通过DMA进行传输的。
整个过程只需要两次上下文的切换和两次数据拷贝。
IO多路复用
I/O多路复用通过一种机制,可以监视多个描述符,一旦某个描述符就绪(一般是读就绪或者写就绪),能够通知程序进行相应的读写操作。
select,poll,epoll都是IO多路复用的机制。
但select,poll,epoll本质上都是同步I/O,因为他们都需要在读写事件就绪后自己负责进行读写,也就是说这个读写过程是阻塞的,而异步I/O则无需自己负责进行读写,异步I/O的实现会负责把数据从内核拷贝到用户空间。
select:
它仅仅知道了,有 I/O 事件发生了,却并不知道是哪那几个流(可能有一个,多个,甚至全部),只能无差别轮询所有流,找出能读出数据,或者写入数据的流,对他们进行操作。
所以select 具有 O(n)的无差别轮询复杂度,同时处理的流越多,无差别轮询时间就越长。
它是基于数组来存储的,它有最大连接数的限制。
poll:
poll 本质上和 select 没有区别,它将用户传入的数组拷贝到内核空间,然后查询每个 fd 对应的设备状态,但是它没有最大连接数的限制,原因是它是基于链表来存储的。
epoll:
epoll 在内核里使用红黑树来跟踪进程所有待检测的文件描述符,把需要监控的 socket 通过
epoll_ct()
函数加入到内核中的红黑树里。
- 红黑树是个高效的数据结构,增删查一般时间复杂度都是
O(logn)
。通过对这颗红黑树进行操作,这样就不需要像 select/poll 每次操作时都传入整个 socket 集合,只需要传入一个待检测的socket,减少了内核和用户空间大量的数据拷贝和内存分配。
epoll 使用事件驱动的机制,内核里面维护了一个链表来记录就绪事件。
当某个 socket 有事件发生时,通过回调函数内核会将其将入到这个就绪事件列表中。
当用户调用
epoll_wait()
时,只会返回有事件发生的文件描述符的个数。
- 不需要像 select/poll 那样轮询扫描整个 socket 集合,大大提高了检测的效率。
epoll 相关接口的作用如下:
- epoll_create(),epoll_ctl()和 epoll_wait()系统调用。
epoll 的方式监听的 Socket 数量越多的时候,效率不会大幅度降低,能够同时监听的 Socket 的数目也非常多,上限就为系统定义的进程打开的最大文件描述符个数。
epoll 支持两种事件触发模式,分别是边缘触发和水平触发:
- 使用边缘触发时,当被监控的 Socket 描述符有可读事件发生时,服务器端只会从
epoll_wait
中苏醒一次,即时进程没有调用 read 函数从内核读取数据,也依然只苏醒一次,因此程序要保证一次性将内核缓冲区的数据读取完。- 使用水平触发模式时,当被监控的 Socket 上有可读事件发生时,服务端不断地从
epoll_wait
中苏醒,知道内核缓冲区数据被 read 函数读完才结束,目的是告诉有数据需要读取。select/poll 只有水平触发模式,epoll 默认的触发模式是水平触发,但是可以根据应用场景设置为边缘触发模式。