死锁概念，解决方法
死锁：多个进程循环等待它方占有的资源而且无限期的僵持下去。当两个或者两个以上进程同时对多个互斥资源提出使用要求时，有可能导致死锁。
必要条件：
- 互斥条件：某个资源在一段时间内只能由一个进程占有，不能被两个或者两个以上的进程占有。必须在占有该资源的进程主动释放它时，其他进程才能占有该资源。
- 不可抢占条件：进程所获得的资源在未使用完毕之前，资源申请者不能强行的从资源占有者的手中夺取资源，只能由其主动释放。
- 占有且申请条件：进程至少已经占有一个资源，但又申请新的资源。
- 循环等待条件：存在一个进程等待序列，形成一个进程循环等待换。
解决方法；
- 打破互斥条件：允许进程同时访问某些资源；
- 打破不可抢占条件：允许进程强行从占有者那里夺取某些资源；
- 打破占有且申请条件：实行资源预先分配策略。
- 打破循环等待条件：实行资源有序分配策略。
父进程与子进程之间的通信
- Linux下父子进程之间通信可以用
pipe()和fork()函数进行实现； - 管道：连接一个读进程和一个写进程，实现通信的共享文件；
进程间通信方式
- 管道(无名管道)：半双工的，具有固定的读端和写端；只能用于具有亲属关系的进程之间的通信；可以看成是特殊的文件，只能存在于内存中；当一个管道建立时，会创建两个文件描述符。
- FIFO(有名管道)：可也在无关进程之间进行交换数据；有路径名与之相连，是以一种特殊的的文件形式存在于文件系统中。
- 消息队列：消息的链接表，存放在内核中；面向记录的，且独立于发送与接收进程；可实现消息的随即查询。
- 信号量：一个计数器，可以用于进程间的互斥与同步，不用于存储进程间的通信数据。
- 共享内存：指两个或多个进程共享一个给定的存储区，进程可以直接对内存进行存取，需要进行同步，常将信号量+共享内存结合在一起使用。
线程同步的方式怎么使用
线程同步：是指多线程通过特定的设置来控制线程之间的执行顺序，即线程之间通过同步建立起执行顺序的关系。其主要方式有：临界区、互斥对象、信号量、事件对象。其中临界区和互斥对象主要用于互斥控制，信号量和事件对象用于同步控制。
- 临界区：通过对多线程的串行化来访问公共资源或一段代码，其速度快，适合控制数据访问。当有一个线程进入临界区时后，会限制其他进程的抢占。
- 互斥对象：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因此互斥对象只有一个，才能保证公共资源不会被多个线程同时访问。
- 信号量：允许多个先后曾在同一时刻访问同一资源，需要在创建信号量时指出允许的最大资源计数和当前可用资源计数。
- 事件对象：通过通知操作的方式来保持现成的同步，方便实现对多个线程的优先级比较操作。
线程比进程具有哪些优势
- 线程在程序中是独立的，并发的执行流，但是进程中的线程之间的隔离程度要小；
- 由于同一个进程中的线程都有共性，线程比进程具有更高的性能，多个线程将共享同一个进程的虚拟空间；
- 当操作系统创建一个进程时，必须为进程分配独立的内存空间，并分配大量相关资源。
什么时候使用多进程？什么时候使用多线程？
- 需要频繁创建销毁的优先选用线程；
- 需要进行大量计算的优先使用线程；
- 强相关的处理用线程，弱相关的处理用进程；
- 可能要扩展到多机分布的用进程，多核分布的用线程。
虚拟内存及其优缺点
- 虚拟内存：一种内存管理技术，使程序认为自己拥有一块很大且连续的内存。实际上这些内存是不连续的甚至在磁盘上，在需要的时候进行数据交换。
- 优点：弥补物理内存大小的不足；一定程度的提高反应速度；减少对物理内存的读取从而保护内存。
- 缺点：占用一定的物理硬盘空间，加大对硬盘的读写，设置不当会影响整机稳定性与速度。
- 虚拟地址空间是对于一个单一进程的概念，其为每个进程提供了一个假象，好像每个进程都独占的使用内存，每个进程看到的存储器都是一致的，成为虚拟地址空间。
CPU执行程序过程
- CPU读取“程序计数器”的值，这个值是指令的内存地址，然后CPU的“控制单元”操作“地址总线”指定需要访问的内核地址，紧接着通知内存设备准备数据，数据准备好后通过“数据总线”将指令数据传给CPU，CPU收到内存传来的数据后将指令数据存入“指令寄存器”；
- CPU分析“指令寄存器”中的指令，确定指令的类型和参数，计算类型的指令交给“逻辑运算单元”，存储类型的指令交给“控制单元”；
- CPU执行完指令后，“程序计数器”值自增，指向下一条指令，若是32位的CPU，指令时4字节，因此“程序计数器”值自增4。
内核的基本能力
- 管理进程、线程，并且具有进程、线程调度能力；
- 管理内存，决定内存的分配和回收，即内存管理能力；
- 管理硬件设备，为进程与硬件设备之间提供痛惜能力，即硬件通信能力；
- 提供系统调度，是用户程序与操作系统之间的接口。
进程状态
进程状态变迁
- NULL->创建状态：一个新的进程被创建时的第一个状态；
- 创建装填->就绪状态：当进程被创建并完成初始化后，一切就绪准备运行时，变成就绪状态；
- 就绪状态->运行状态：处于就绪状态的进程被操作系统的进程调度器选中后，分配给CPU正式运行该进程；
- 运行状态->结束状态：当进程已经完成或出错时，会被操作系统作结束状态处理；
- 运行状态->就绪状态：处于运行状态的进程在运行过程中，由于分配给它的运行时间片用完，操作系统会把该进程变为就绪态，接着从就绪态选中一个进程运行；
- 运行状态->阻塞状态：当进程请求某个事件必须等待时，进入阻塞状态；
- 阻塞状态->就绪状态：当进程要等待的时间完成时，它从阻塞状态变到就绪状态。
创建进程过程
- 为新进程分配一个唯一的进程标识号，并申请一个空白的PCB，PCB是有限的，若申请失败则创建失败；
- 为进程分配资源，此时如果资源不足，进程进入等待状态，以等待资源；
- 初始化PCB；
- 如果进程的调度队列能够接纳新进程，那就将进程插入到就绪队列，等待被调度运行。
终止进程过程
- 查找需要终止的进程的PCB；
- 如果出于执行状态，则立即终止该进程的执行，然后将CPU资源分配给其他进程；
- 如果还有其子进程，则应将其所有子进程终止；
- 将该进程所拥有的全部资源都归还给父进程或操作系统；
- 将其从PCB所在队列中删除
阻塞进程过程
- 找到要被阻塞进程标识号对应的PCB；
- 如果该进程为运行状态，则保护其现场，将其状态转为阻塞状态，停止运行；
- 将该PCB插入到阻塞队列中去。
唤醒进程过程
- 将该事件的阻塞队列中找到相应进程的PCB；
- 将其从阻塞队列中移出，并设置其状态为就绪状态；
- 把该PCB插入到就绪队列中，等待调度程序调度。
发生进程上下文切换有哪些场景
- 为了保证所有进程可以得到公平调度，CPU时间被划分为一段一段的时间片，这些时间片在被轮流分配给各个进程。这样当某个进程的时间片耗尽时，程序从运行态转化为就绪态，系统从就绪队列中选择另一个进程运行；
- 进程在系统资源不足时，需要等到资源满足后才可以运行，这个时候进程会被挂起，并由系统调度其他程序运行；
- 当进程通过睡眠函数将自己主动挂起时，也会进行重新调度；
- 当有优先级更高的进程运行时，为了保证高优先级进程运行，此时运行的进程会被挂起；
- 当发生硬件中断时，CPU上的进程会被中断挂起，转而执行内核中的中断服务程序。
线程的优缺点
线程的优点
- 一个进程中可以同时存在多个线程；
- 各个线程之间可以并发执行；
- 各个线程之间可以共享地址空间和文件等资源。
线程的缺点
- 当一个进程中的一个线程崩溃时，会导致其所属的所有线程崩溃。
线程与进程的比较
- 进程是资源分配(如内存、文件等)的单位，线程是CPU调度的单位；
- 进程拥有一个完整的资源平台，而线程只独占寄存器和堆栈等必不可少的资源；
- 线程同样具有就绪、阻塞、运行三种基本状态，同样具有状态之间的转换关系；
- 线程能减少并发执行的时间和空间开销：
- 线程的创建时间比进程快，因为在进程的创建过程中，需要资源管理信息，而线程不涉及资源管理信息，只是共享它们；
- 线程的终止时间比进程快，因为线程释放的资源相比较进程较少；
- 同一个进程内的线程切换比进程快，因为线程具有相同的地址空间，切换时不需要切换页表。而进程之间的切换需要切换页表；
- 由于同一个进程的各个线程之间共享内存和文件资源，因此在线程之间传递数据不需要经过内核，其数据交换效率更高。
线程的实现
- 用户线程：在用户控件实现的线程，不是由内核管理的线程，由用户态的线程库来完成线程的管理；
- 内核线程：在内核中实现的线程，由内核管理的线程；
- 轻量级进程：在内核中来支持用户线程。
用户线程的优缺点
优点：
- 每个进程都需要其私有的线程控制块(TCB)列表，用来跟踪记录它各个线程状态信息，TCB 由用户级线程库函数来维护，可用于不支持线程技术的操作系统；
- 用户线程的切换是由线程库函数完成，无需用户态与内核态的切换，所以速度较快；
缺点：
- 由于操作系统不参与现成的调度，如果一个线程发起了系统调用而阻塞，则进程所包含的所有用户线程都无法执行；
- 当一个线程开始运行后，除非它主动交出CPU使用权，否则所在进程内其他线程无法执行。因为用户态的线程无法打断当前运行的线程，它没有这个特权，只有操作系统才有，但是用户线程不是由操作系统管理的；
- 由于时间片分配给进程，因此与其他进程相比，在多线程执行时，每个线程所得到的时间片较少，执行比较慢。
内核线程的优缺点
优点：
- 在一个进程中，如果某个内核线程发起系统调度而被阻塞，并不会影响其他内核线程的运行；
- 分配个线程，多线程的进程获得更多的CPU运行时间；
缺点：
- 在支持内核线程的操作系统中，由内核来维护进程和线程的上下文信息，如PCB和TCP；
- 线程的创建、终止和切换都是通过系统调用的方式来进行，因此对于系统来说，系统开销比较大。
调度算法
分类：
- 非抢占式调度算法：挑选一个进程，然后让该进程运行直到被阻塞，或者直到该进程退出，才会调度另一个进程，即不理会时钟中断这件事；
- 抢占式调度算法：挑选一个进程，然后让进程之运行某段时间，当时间段结束后，若该进程仍在运行，则将其挂起，接着调度程序从就绪队列挑选另一个进程。这种抢占式调度处理需要在时间间隔的末端发生时钟中断，以便把CPU控制返回给调度程序进行调度，即常说的***时间片机制***。
调度原则：
- CPU利用率：调度程序应确保CPU始终是匆忙状态，提高CPU利用率。要提高CPU利用率，在发送I/O时间使得CPU空闲状态下，需要从就绪队列选择一个进城来运行。
- 系统吞吐量：吞吐量是单位时间内CPU完成进程的虎粮，长作业进程会占用较长的CPU资源，因此降低吞吐量，相反短作业进程会提升系统吞吐量。要提高系统的吞吐率，调度程序要权衡长任务和段任务进程的运行完成数量。
- 周转时间：周转时间是进程运行和阻塞时间总和，一个进程的周转时间越小越好。若进程等待时间很长而运行时间很短，则其周转时间就很长，应当避免。
- 等待时间：等待事件是指进程处于就读队列的时间，等待时间越长，用户越不满意。需要考虑就绪队列中的等待时间。
- 响应时间；用户提交请求到系统第一次产生相应所花费的时间，在交互式系统中，响应时间是很衡量调度算法好坏的重要标准。
先来先服务算法（FCFS）
? 每次就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，然后继续选择队列中第一个进程接着运行。该算法对长作业有利，适用于CPU繁忙型作业的系统，不适合I/O繁忙型作业的系统，其不利于短作业。
最短作业优先算法（SJF）
? 会优先选择运行时间最短的进城来运行，有助于提高系统的吞吐量，但显然对长作业不利。
高相应比优先调度算法（HRRN）
? 权衡了短作业和长作业，每次进程调度时，会计算“响应比优先级”，然后将其优先级较高的线程投入运行。优先级=(等待时间+要求服务时间)/要求服务时间。
时间片轮转调度算法（RR）
? 每个进程分配一个时间段，成为时间片，即允许该进程在该时间段中运行。
最高优先级调度算法（HPF）
? 从就绪队列中选择最高优先级的进程运行。其优先级可分为静态优先级和动态优先级，算法可分为抢占式和非抢占式。该算法可能会导致低优先级的进程永远不会运行。
多级反馈队列调度算法（MFQ）
? 多级表示有多个队列，每个队列优先级从高到低，同时优先级越高时间片越短。反馈表是如果有新的进程加入到优先级高的队列时，会立刻停止当前运行的进程，转而去运行优先级高的队列。
进程间通信
管道
- 管道即内核里的一段缓存，创建的子进程会复制父进程的文件描述符，从而两个进程可以通过各自fd写入和读取同一个管道文件实现跨进程通信。
- 管道传输是单向的，若想相互通信，需要创建两个管道；
- 管道通信方式效率低，不适合进程间频繁交换数据；
- 管道较为简单，容易的值管道里的数据已经被另一个进程读取；
- 无格式的流并且大小受限；
- 匿名管道只能用于存在父子关系的进程间通信。
- 命名管道遵循先进先出原则，不支持文件定位操作。
消息队列
- 消息队列是保存在内核中的消息链表，在发送数据时，会分成一个一个独立的数据单元，即消息体。
- 消息队列生命周期随内核，没有释放消息队列或没有关闭操作系统，消息队列会一直存在。
- 消息队列通信不及时，且大小有限制。因此消息队列不适合大数据的传输。
- 消息队列通信过程中，存在用户态与内核态之间的数据拷贝开销。
- 每次数据的写入和读取都需要经过用户态和内核态之间的拷贝过程，因此其通信速度不及时。
共享内存
- 共享内存的机制即拿出一块虚拟地址空间来，映射到相同的物理内存中，不需要拷贝数据，可以有效提高进程间通信的速度。
- 若多个进程同时修改一个共享内存，容易造成冲突。
信号量
- 一个整形计数器，用于实现进程间的互斥与同步，而不是用于缓存进程间通信的数据。
- P操作：将信号量-1，若信号量<0，则进程需要阻塞等待。
- V操作：将信号量+1，若信号量<=0，则表示当前有阻塞的进程，可以将该进程唤醒运行。
信号
- 对于异常情况下的工作模式，需要用到信号的方式来通知进程。
- 信号是进程间通信机制中唯一的异步通信机制，可以在任何时间发送信号给某一进程。
- 主要操作有：执行默认操作、捕捉信号、忽略信号。
Socket
多线程同步
? 同步就是并发进程/线程在一些关键点上可能需要互相等待与互通消息，这种相互支援的等待与互通信息成为进程/线程同步。
? 自旋锁：当获取不到锁的时候，线程就会一直while循环，不做任何事情，所以被称为“忙等待锁”，其一直自旋，利用CPU周期，直到锁可用位置。在单处理器上，需要抢占式调度器，否则自旋锁在单CPU上无法使用。
生产者-消费者问题
- 生产者在生成数据后，放在一个缓冲区中；
- 消费者从缓冲区中取出数据；
- 任何时刻，只能有一个生产者或者消费者访问缓冲区。
- 需要三个信号量：
- 互斥信号量mutex：用于互斥访问缓冲区，其初始化为1；
- 资源信号量fullBuffers：用于消费者寻味缓冲区是否有数据，有数据则可读取数据，初始化为0；
- 资源信号量emptyBuffers：用于生产者询问缓冲区是否有空位，有空位则生成数据，初始化为n(缓冲区大小)；
哲学家就餐问题
-
方案一：引用信号量PV操作，但是会导致死锁问题 -
方案二：仅允许一个哲学家吃饭，即只要有一个哲学家进入临界区，其他哲学家不能动，此时无法有效地利用所有叉子资源。 -
方案三：让偶数编号哲学家“先拿左边的叉子然后拿右边的叉子”，让奇数编号哲学家“先拿右边的叉子然后拿左边的叉子” -
方案四：用state数组记录哲学家进餐情况，一个哲学家在两边邻居都没有进餐时才能进餐。
读者-写者问题
- 读-读 允许：同一时刻，允许多个读者同时读；
- 读-写 互斥：没有写者时，读者才能读；没有读者时，写者才能写；
- 写-写 互斥：没有其他写者是，写者才能写。
死锁
死锁必须同时满足的条件：
- 互斥条件：多个线程不能同时使用一个资源。
- 持有并等待条件：线程A在等待资源2，同时不会释放自己已持有的资源1。
- 不可剥夺条件：当线程已经持有了资源，在自己使用完之前不能被其他线程获取。
- 环路等待条件：两个或两个以上线程获取资源的顺序构成了环形链。
常见的锁
-
互斥锁：互斥锁加锁失败后，线程会释放CPU，给其他线程。互斥锁加锁失败后，会从云哥浒苔陷入到内核态，内核进行线程切换，因此存在性能开销成本。 -
自旋锁：自旋锁加锁失败后，线程会忙等待，直到它拿到锁。如果能确定被锁住的代码执行时间很短，就不应该选用互斥锁，而是选用自旋锁，相反则选择互斥锁。 -
读写锁：分为“读锁”和“写锁”，如果只读取共享资源时用“读锁”，如果要修改共享资源则利用“写锁”。因此读写锁适用于能明确区分读操作和写操作的场景，其在读多写少的场景下，可以发挥出优势。同时可分“读优先锁”和“写有限锁”。 -
悲观锁：认为多线程同时修改共享资源的概率比较高，容易出现冲突，因此在访问共享资源前要先上锁。 -
乐观锁：认为多线程同时修改共享资源的概率比较低。其方式是：先修改完共享资源，再验证这段时间有没有发生冲入，若如果其他线程没有修改资源则操作完成，否则放弃本次操作。
调度算法
进程调度算法
-
非抢占式调度算法：
-
抢占式调度算法
-
先来先服务调度算法：每次从就绪队列中选择最先进入到队列的进程，然后一直运行，知道进程退出或被阻塞才会继续从队列中选择第一个进程进行运行，不适合短作业，因此不适用于I/O繁忙作业系统 -
最短作业优先调度算法：优先选择运行时间段的进城来运行，有助于提高系统的吞吐量，容易造成长作业长期不被运行。 -
高相应比有限调度算法：利用响应比优先级权衡长短作业，相同等待时间选择短作业有限，相同要求服务时间兼顾长作业进程。 -
时间片轮转调度算法：每个进程被分配一个时间片，仅允许该进程在该时间段中的运行。容易降低CPU效率或导致对短作业响应时间边长。 -
最高优先级调度算法：选择该最高优先级的作业进行运行，容易导致低优先级的作业无法运行。 -
多级反馈队列调度算法：设置多个队列，赋予每个队列不同的优先级，每个队列优先级从高到低，同时优先级越高时间片越短。新的进程会被放到第一级队列的末尾，按照先来先服务的原则排队等待被调度，若在第一队列规定的时间片内没有余小宁完成，则将其转入到第二队列的末尾，以此类推。
页面置换算法
缺页中断处理流程：
- 在CPU里访问呢一条Load M指令，然后CPU去找M所对应的页表项；
- 如果页表项状态是有效的，则CPU可直接访问物理内存；若页表项状态是无效的，则CPU发送缺页中断请求；
- 操作系统收到缺页中断，则会执行缺页中断处理函数，先会查找该页面在磁盘中页面的位置；
- 找到磁盘中对应的页面后，需要把该页面换到物理内存中，在换入前，需要在物理内存中找到空闲页，如果找到空闲页，则将页面换入到物理内存中；
- 页面从磁盘换入到物理内存完成后，将其状态改为有效地；
- 最后CPU重新弄执行缺页异常的指令。
??在第四步在物理内存中若找不到空闲页，说明内存已满，此时需要***页面置换算法***选择一个物理页，如果该物理页又被修改过，则将其换出到此爬满，然后把该被置换出去的页表项状态改为无效的，最后把正在访问的页面装入到这个物理页中。
? 所以页面置换算法的功能是，当出现缺页异常，需要重新调入页面而内存已满时，选择被置换的物理页面。即选择一个物理页面换出到磁盘，然后把需要访问的页面换入到物理页。
- 最佳页面置换算法：置换在未来最长时间不访问的页面。
- 先进先出置换算法：选择在内存驻留时间很长的页面进行置换。
- 最近最久未使用的置换算法：选择最长时间没有被访问的页面进行置换。
- 始终页面置换算法：利用唤醒列表，一个表针指向最老的页面。当发生缺页中断时，首先检查表针指向的页面，如果其访问位是0，则淘汰该页面，并将新的页面插入到这个位置，把表针前移一个位置；如果访问位是1，则清楚访问位，并把表针前一个位置，重复这个过程直到找到访问位为0的页面。
- 最不常用置换算法：当发生缺页中断时，选择访问次数最少的页面并将其淘汰。
磁盘调度算法
- 先来先服务算法：先来的请求先被服务。
- 最短寻道时间优先算法：优先选择从当前磁头位置所需寻道时间最短的请求。
- 扫描算法算法：规定磁头在一个方向上移动，访问所有未完成的请求，直到磁头到该方向上的最后磁道，随后调换方向。也叫电梯算法。
- 循环扫描算法：只有磁头超某个特定方向移动时，才处理磁道访问请求，而返回时则快速移动至最靠近边缘的磁道，返回途中不处理任何请求。
- LOOK与C-LOOK算法：将扫描算法和循环扫描算法中的“移动到磁盘最始端或最末端”改为“最远的请求”。
Linux文件系统的两个数据结构
- 索引节点——inode：用来记录文件的辕信息，如inode编号、文件大小、访问权限、创建时间、修改时间、在磁盘中的位置等。索引节点是文件的唯一标识，两者之间一一对应。索引节点同样占用磁盘空间。
- 目录项——dentry：用来记录文件的名字、索引节点指针以及与其他目录项的层级关联关系。目录项是由内核维护的一个数据结构，不存放于磁盘中，而是缓存在内存。
目录和目录项的区别
- 目录是一个文件，持久化存储在磁盘；
- 目录项是内核一个数据结构，缓存在内存；
- 目录项不知表示目录，也可以表示文件。
磁盘存储区域
- 超级块：用于存储文件系统的详细信息，比如块个数、块大小、空闲块等；
- 索引节点区：用来存储索引节点；
- 数据块区：用来存储文件或目录数据。
Linux文件系统分类
- 磁盘文件系统：直接将数据存储在磁盘中；
- 内存文件系统：数据不存储在硬盘中，而是占用内存空间。读写这类文件其实是读写内核中的相关数据；
- 网络文件系统：用来访问其他计算机主机数据的文件系统。
在Linux系统启动时，会将文件系统挂载在根目录。
空闲空间管理
-
空闲表法：为所有的空闲空间建立一张表，表内容包括空闲区的第一个块号和该空闲区的块个数，注意这个方式是连续分配的。此方法仅当有较少的空闲区时效果较好，若存储空间中有大量的小的空闲区，其查询效率较低。同时此方法使用据建立连续文件。 -
空闲链表法：每个空闲块里有一个指针指向下一个空闲块。此方法较为简单，但是无法随机访问，工作效率较低。空闲表法和空闲链表法都不是用于大型文件系统。 -
位图法：利用二进制的一位来表示磁盘中一个盘块的使用情况。空闲时盘块值为0，若已分配则为1。
连接
硬链接
- 硬链接是多个目录项中的索引节点指向一个文件，即同一个inode。
- 硬链接不可以用于跨文件系统。
- 由于多个目录项指向一个inode，那么只有删除文件的所有硬链接及源文件时，系统才会彻底删除该文件。
软连接
- 软链接相当于重新创建一个文件，这个文件有独立的inode，但是其内容是另外一个文件的路径。
- 软连接是可以跨文件系统的。
- 目标文件被删除时，软连接依旧存在，但是其指向的文件无法找到。
文件I/O
缓冲与非缓冲I/O
? 根据是否利用标注库缓冲，可将文件I/O分为缓冲I/O和非缓冲I/O。
- 缓冲I/O：利用标准库的缓存实现文件的快速访问，而标准库在通过系统调用访问文件；
- 非缓冲I/O：直接通过系统调用访问文件，不经过标准库缓存。
直接与非直接I/O
? 由于磁盘I/O速度较慢，因此Linux内核为了减少磁盘I/O次数，在系统用调用后会把用户数据拷贝到内核中缓存起来，这个内核缓存空间及页缓存，只有当缓存满足某些条件时，才会发起磁盘I/O的请求。因此可根据是否利用操作系统的缓存将文件I/O分为直接I/O与非直接I/O。
- 直接I/O：不会发生内核缓存和用户程序之间数据复制，而是直接经过文件系统访问磁盘。
- 非直接I/O：读操作时，数据从内核缓存中拷贝给用户数据。写操作时，数据从用户程序拷贝给内核缓存，再由内核决定什么时候将数据写入到磁盘。
触发内核缓存的数据写入磁盘场景：
- 在调用write的最后，当内核缓存的数据太多，内核会把数据写到磁盘上；
- 用户主动调用sync，内核缓存会刷到磁盘上；
- 当内存十分紧张，无法再分配页面时，也会把内核缓存的数据刷到磁盘上；
- 内核缓存的数据的缓存时间超过某个时间时，也会把数据刷到磁盘上。
阻塞与非阻塞I/O VS 同步与异步I/O
- 阻塞I/O：当用户执行read时，线程会被阻塞，直到内核数据准备好并将数据从内核缓冲区拷贝到应用程序的缓冲区中，当拷贝过程完成，read才算返回。其阻塞等待的是”内核数据准备好“和”数据从内核态拷贝到用户态“两个过程。
- 非阻塞I/O：非阻塞的read请求在数据未准备好的情况下立即返回，可以继续往下执行，此时应用程序不断轮询内核，直到数据准备好，内核将数据拷贝到应用缓冲区中，read调用才可以获取到结果。此时最后一次read调用，获取数据的过程，是一个同步的过程，也需要等待。
- 阻塞I/O、非阻塞I/O、或者非阻塞I/O的多路复用都是同步调用，因为在read调用时，内核将数据从内核空间拷贝到应用程序空间过程都是需要等待的。
- 异步I/O是”内核数据准备好“和”数据从内核态拷贝到用户态“两个过程都可以不用等待。如发起aio_read后，立刻返回，内核自动将数据从内核空间拷贝到应用程序空间，这个拷贝过程同样是异步的，内核自动完成，应用程序不用主动发起拷贝动作。
Linux内存支持的I/O调度算法
- 没有调度算法：不对文件系统和应用程序的I/O做任何处理，常在虚拟机的I/O中，磁盘I/O调度算法交由物理机系统负责。
- 先入先出调度算法：先进入I/O调度队列的I/O请求先发生。
- 完全公平调度算法：大部分将其作为默认的I/O调度器，为每个进程维护了一个I/O调度队列，并按照时间片来均匀分布每个进程的I/O请求。
- 优先级调度：优先级高的I/O请求先发生，适用于大量进程的系统。
- 最终期限调度算法：分别为读、写请求创建了不同的I/O队列，可以提高机械磁盘的吞吐量，确保最终期限的请求被优先处理，适用于在I/O压力比较大的场景。
DMA技术
定义
? 在进行I/O设备和内存的数据传输时候，数据搬运的工作全部交给DMA控制器，而CPU不再参与任何与数据搬运相关的事情，从而可以去处理别的事物。
具体过程
- 用户进程调用read方法，向操作系统发出I/O请i去，请求读取数据到自己的内存缓冲区，进程进入阻塞状态；
- 操作系统收到请求后，进一步将I/O请求发送给DMA，然后让CPU执行其他任务；
- DMA进一步将I/O请求发送给磁盘；
- 磁盘收到DMA的I/O请求，把数据从磁盘读取到磁盘控制器的缓冲区中，当磁盘控制器的缓冲区被读满后，向DMA发起中断信号，告知自己缓冲区已满了；
- DMA收到磁盘的信号，将磁盘控制器缓冲区中的数据拷贝到内核缓冲区中，此时不占用CPU，CPU可以执行其他任务；
- 当DMA读取到足够多的数据后，发送中断信号给CPu；
- CPU收到DMA的信号，知道数据已准备好，于是将数据从内核拷贝到用户空间，系统调用返回。
四次数据拷贝
- 把磁盘的数据拷贝到系统内核的缓冲区中，这个拷贝是通过DMA搬运的；
- 把内核缓冲区的数据拷贝到用户缓冲区里，应用程序可以使用这部分数据，这个搬运过程由CPU完成；
- 把刚才拷贝到用户的缓冲区里的数据，再拷贝到内核的socket缓冲区中，此过程依然由CPU搬运；
- 把内核的socket缓冲区里的数据拷贝到网卡缓冲区里，由DMA搬运。
如何实现零拷贝
- mmap+write：使用mmap()替换read()系统调用函数。mmap()系统调用函数会直接把内核缓冲区里的数据映射到用户空间，这样操作系统内核与用户空间不用再进行任何数据拷贝操作。
- 用户进程调用mmap()后，DMA把磁盘数据拷贝到内核缓冲区里，接着应用进程跟操作系统内核共享这个缓冲区；
- 应用进程调用write()，操作系统直接将内核缓冲区的数据拷贝到socket缓冲区中，这一切都发生在内核态，由CPU来办运输局；
- 把内核的socket缓冲区里的数据拷贝到网卡缓冲区里，这个过程由DMA搬运。
- sendfile：利用sendfile()代替read()和write()两个系统调用，可以减少一次系统调用，同时可以把内核缓冲区里的数据直接拷贝到socket缓冲区里，不用拷贝到用户态。
- 通过DMA将磁盘数据拷贝到内核缓冲区里；
- 缓冲区描述符和数据长度传到socket缓冲区，网卡的SG-DMA控制器可以直接将内核缓存中的用户拷贝到网卡和，不用将数据从操作系统内核缓冲区拷贝到socket缓冲区中。
epoll如何解决poll和select性能损失问题
- epoll在内合理使用红黑树来跟踪进程所有待检测的文件描述字。只需要传入一个待检测的socket，可减少内核和用户空间大量数据拷贝和内存分配。
- epoll是事件驱动的机制，内赫里维护了一个链表来记录就绪事件，当某个socket有事件发生时，通过回调函数内核会将其加入到就绪事件队列中，可通过epoll_wait()函数获取事件发生的文件描述符的个数。
|