操作系统

概述

计算机结构

现代计算机模型是基于冯诺依曼结构

基本概念

操作系统
- 操作系统是一个大型的程序系统，负责计算机的全部软、硬资源的分配、调度工作，控制和协调并发活动，实现信息的存取和保护
- 提供用户接口，使用户获得良好的工作环境，操作系统使整个计算机系统实现了高效率、高度自动化、高利用率和高可靠性。
操作系统的组成
- 计算机系统由硬件和软件两部分组成
  - 硬件部分：指其物理装置本身，包括各种处理器（如中央处理器、输入输出处理器和该系统中的其他处理器）、存储器、输入输出设备和通信装置；
  - 软件部分：指由计算机硬件执行以完成一定任务的所有程序及其数据。
并行和并发
- 基本概念
  并发：宏观上在一段时间内能同时运行多个程序
  并行：同一时刻能运行多个指令
  区别两者的关键：是否同时
- 并行需要硬件支持，多l流水线、分布式计算机，在计算机上的体现就是增加cpu的数量可以提高并行
- 操作系统引入进程和线程，使得程序可以并发运行
共享
- 共享是指系统中的资源可以被多个并发进程使用
- 有两种共享方式：互斥共享和同时共享
- 互斥共享的资源为临界资源，例如打印机，在同一时间只允许一个进程访问，需要用同步机制来实现对临界资源的访问
虚拟
- 虚拟技术把一个物理实体转换为多个逻辑实体
- 主要的虚拟技术：
  - 时分复用技术time-multiplexed sharing
  - 空分复用技术space-multiplexed sharing
- 时分复用技术是在“时间”上将资源分割成更小的单位供不同的进程使用，多个进程能在同一个处理器上并发执行使用了时分复用技术，让每个进程轮流占有处理器，每次只执行一小个时间片并快速切换。
- 虚拟内存使用了空分复用技术，它将物理内存抽象为地址空间，每个进程都有各自的地址空间。地址空间的页被映射到物理内存，地址空间的页并不需要全部在物理内存中，当使用到一个没有在物理内存的页时，执行页面置换算法，将该页置换到内存中。
异步
- 异步是彼此独立，在等待某事件的过程中去做另一件事情
- 异步是目的，多线程只是实现异步的一种手段，所以异步和多线程并不相同

基本功能

进程管理
进程控制，进程同步，进程通信，死锁处理，处理调度
内存管理
- 内存分配、地址映射、内存保护和共享、虚拟内存
文件管理
- 文件存储空间的管理、目录管理、文件读写管理和保护
设备管理
- 完成用户的I/O请求，方便用户使用各种设备，并提高设备的利用率
- 主要包括缓冲管理、设备分配、设备处理、虚拟设备等

系统调用

如果一个进程在用户态需要使用内核态的功能，就进行系统调用从而陷入内核，由操作系统代为完成。

用户态和内核态

内核态（Kernel Mode）：CPU可以访问内存所有数据, 包括外围设备, 例如硬盘, 网卡. CPU也可以将自己从一个程序切换到另一个程序
用户态 (User Mode) : 只能受限的访问内存, 且不允许访问外围设备. 占用CPU的能力被剥夺, CPU资源可以被其他程序获取

为什么有内核态和用户态？

由于需要限制不同的程序之间的访问能力, 防止他们获取别的程序的内存数据, 或者获取外围设备的数据, 并发送到网络, CPU划分出两个权限等级 – 用户态和内核态

系统调用-内核切换

内核切换在CPU中的实现称之为陷阱指令(Trap Instruction)
内核调用：操作系统（内核）相当于是在应用程序和硬件之间添加了一个中间层。所以应用程序是不能够直接访问硬件设备的，只能使用内核向外提供的一组接口，这些接口让应用程序受限地访问硬件设备。我们把调用这些接口的过程叫做系统调用
工作流程
1. 用户态程序将一些数据值放在寄存器中, 或者使用参数创建一个堆栈(stack frame), 以此表明需要操作系统提供的服务.
2. 用户态程序执行陷阱指令
3. CPU切换到内核态, 并跳到位于内存指定位置的指令, 这些指令是操作系统的一部分, 他们具有内存保护, 不可被用户态程序访问
4. 这些指令称之为陷阱(trap)或者系统调用处理器(system call handler). 他们会读取程序放入内存的数据参数, 并执行程序请求的服务
5. 系统调用完成后, 操作系统会重置CPU为用户态并返回系统调用的结果

操作系统的两种体系结构

大内核
大内核系统将操作系统的主要内容模块都作为一个紧密联系的整体运行在核心态，从而为应用提供高性能的系统服务。因为各管理模块之间共享信息，能有效利用相互之间的有效特性，所以具有无可比拟的性能优势。
微内核
由于操作系统不断复杂，因此将一部分操作系统功能移出内核，从而降低内核的复杂性。移出的部分根据分层的原则划分成若干服务，相互独立。在微内核结构下，操作系统被划分成小的、定义良好的模块，只有微内核这一个模块运行在内核态，其余模块运行在用户态。因为需要频繁地在用户态和核心态之间进行切换，所以会有一定的性能损失。
两者的优缺点
- 大内核：性能高，内核代码庞大，结构混乱，难以维护
- 微内核：内核功能少，结构清晰，方便维护，但是需要频繁的在核心态和用户态进行切换，性能低

中断

分类
- 按照中断的触发方分成同步中断和异步中断
- 根据中断是否强制触发分成可屏蔽中断和不可屏蔽中断
同步中断
- 主动触发的中断，CPU 指令直接触发
- 触发的集中方式
  - 陷入( trap )：在用户程序中使用系统调用。
  - 错误 : 由 CPU 执行指令的内部事件引起，如非法操作码、地址越界、算术溢出等
  - 程序的异常，这种情况和 Trap 类似，用于实现程序抛出的异常。
异步中断
- 由 CPU 执行指令以外的事件引起，如 I/O 完成中断，表示设备输入/输出处理已经完成，处理器能够发送下一个输入/输出请求

进程管理

进程、线程和协程

1	`进程是操作系统分配资源的最小单元，线程是操作系统调度的最小单元`

进程

进程是资源分配的基本单位
进程控制块(Process Control Block,PCB)描述进程的基本信息和运行状态,所谓的创建进程和撤销进程,都是指对PCB的操作
进程可以并发执行

守护进程

守护进程是脱离于终端并且在后台运行的进程，脱离终端是为了避免在执行的过程中的信息在终端上显示，并且进程也不会被任何终端所产生的终端信息所打断。
守护进程一般的生命周期是系统启动到系统停止运行

僵尸进程和孤儿进程

僵尸进程
- 父进程产生子进程后，会维护子进程的一个PCB结构，子进程退出，由父进程释放，如果父进程没有释放，那么子进程成为一个僵尸进程
孤儿进程
- 子进程结束前，父进程已经退出。
- 孤儿进程会成为iinit进程的孩子，由1号进程维护。

线程

线程是独立调度的基本单位
一个进程可以有多个线程,他们共享线程资源

纤程(协程)Fiber

协程运行在线程之上，当一个协程执行完成后，可以选择主动让出，让另一个协程运行在当前线程之上。协程并没有增加线程数量，只是在线程的基础之上通过分时复用的方式运行多个协程，而且协程的切换在用户态完成，切换的代价比线程从用户态到内核态的代价小很多。
在协程中尽量不要调用阻塞IO的方法，比如打印，读取文件，Socket接口等，除非改为异步调用的方式，并且协程只有在IO密集型的任务中才会发挥作用。协程只有和异步IO结合起来才能发挥出最大的威力
JAVA支持纤程的类库：quasar_core,GO、python支持

进程和线程的区别

资源
进程是资源分配的基本单位,线程不拥有资源,线程访问隶属进程的资源
调度
线程是独立调度的基本单位,在同一个进程中,线程的切换不会引起进程的切换,但一个进程中的线程切换到另一个进程中的线程,会引起线程切换
系统开销
由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。
通信方面
线程间可以通过直接读写同一进程的数据进行通信,但进程间通信需要IPC

进程状态的切换

就绪状态(ready):等待被调度
运行状态(running)
阻塞状态(waiting):等待资源
应该注意以下内容:
- 只有就绪态和运行态可以相互转换,其他都是单向转换.就绪状态的进程通过调度算法从而获得CPU时间,转为运行状态;而运行状态的进程,在分配给他的CPU时间片用完之后就会转为就绪状态,等待下一次调用
- 阻塞状态是缺少需要的资源从而由运行状态转换而来,但是该资源不包括CPU时间,缺少CPU时间会从运行态转换为就绪态

进程调度

不同环境的调度算法不同,因此需要针对不同的环境来讨论调度算法

进程调度策略

先来先服务(FCFS)

先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。

短作业(进程)优先(SJ(P)F)

短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。

高优先权优先（FPF）

为了照顾紧迫型作业，使之在进入系统后便获得优先处理，引入了最高优先权优先(FPF)调度算法。此算法常被用于批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度算法，还可用于实时系统中。当把该算法用于作业调度时，系统将从后备队列中选择若干个优先权最高的作业装入内存。当用于进程调度时，该算法是把处理机分配给就绪队列中优先权最高的进程，这时，又可进一步把该算法分成如下两种。

非抢占式优先权

在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。

抢占式优先权

在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。因此，在采用这种调度算法时，是每当系统中出现一个新的就绪进程i 时，就将其优先权Pi与正在执行的进程j 的优先权Pj进行比较。如果Pi≤Pj，原进程Pj便继续执行；但如果是Pi>Pj，则立即停止Pj的执行，做进程切换，使i 进程投入执行。显然，这种抢占式的优先权调度算法能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。
问题
- 容易出现优先级倒置现象：优先级反转是指一个低优先级的任务持有一个被高优先级任务所需要的共享资源。高优先任务由于因资源缺乏而处于受阻状态，一直等到低优先级任务释放资源为止。而低优先级获得的CPU时间少，如果此时有优先级处于两者之间的任务，并且不需要那个共享资源，则该中优先级的任务反而超过这两个任务而获得CPU时间。如果高优先级等待资源时不是阻塞等待，而是忙循环，则可能永远无法获得资源，因为此时低优先级进程无法与高优先级进程争夺CPU时间，从而无法执行，进而无法释放资源，造成的后果就是高优先级任务无法获得资源而继续推进。
解决方案
- 设置优先级上限，给临界区一个高优先级，进入临界区的进程都将获得这个高优先级，如果其他试图进入临界区的进程的优先级都低于这个高优先级，那么优先级反转就不会发生。
- 优先级继承，当一个高优先级进程等待一个低优先级进程持有的资源时，低优先级进程将暂时获得高优先级进程的优先级别，在释放共享资源后，低优先级进程回到原来的优先级别。嵌入式系统VxWorks就是采用这种策略。
- 临界区禁止中断，通过禁止中断来保护临界区，采用此种策略的系统只有两种优先级：可抢占优先级和中断禁止优先级。前者为一般进程运行时的优先级，后者为运行于临界区的优先级。火星探路者正是由于在临界区中运行的气象任务被中断发生的通信任务所抢占才导致故障，如果有临界区的禁止中断保护，此一问题也不会发生。

高响应比优先

在批处理系统中，短作业优先算法是一种比较好的算法，其主要的不足之处是长作业的运行得不到保证。如果我们能为每个作业引入前面所述的动态优先权，并使作业的优先级随着等待时间的增加而以速率a 提高，则长作业在等待一定的时间后，必然有机会分配到处理机。该优先权的变化规律可描述为：
在利用该算法时，每要进行调度之前，都须先做响应比的计算，这会增加系统开销。

时间片轮转法

在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU 分配给队首进程，并令其执行一个时间片。时间片的大小从几ms 到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定的时间内响应所有用户的请求。

多级反馈队列调度算法

前面介绍的各种用作进程调度的算法都有一定的局限性。如短进程优先的调度算法，仅照顾了短进程而忽略了长进程，而且如果并未指明进程的长度，则短进程优先和基于进程长度的抢占式调度算法都将无法使用。而多级反馈队列调度算法则不必事先知道各种进程所需的执行时间，而且还可以满足各种类型进程的需要，因而它是目前被公认的一种较好的进程调度算法。在采用多级反馈队列调度算法的系统中，调度算法的实施过程如下所述。
- 应设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，……，第i+1个队列的时间片要比第i个队列的时间片长一倍。
- 当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，如此下去，当一个长作业(进程)从第一队列依次降到第n队列后，在第n 队列便采取按时间片轮转的方式运行。
- 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1～(i-1)队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1～(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程。

批处理系统、分时系统和实时系统中，各采用哪几种进程（作业）调度算法？

批处理系统常用调度算法：
- 先来先服务
- 最短作业优先
- 最短剩余时间优先
- 响应比最高者优先
分时系统调度算法：
- 轮转调度
- 优先级调度
- 多级队列调度
- 彩票调度
实时系统调度算法：
- 单比率调度
- 限期调度
- 最少裕度法

Linux调度算法CFS

2.6后开始采用该算法，该算法按优先级分配时间片的比例，记录每个线程的执行时间，如果有一个进程执行时间不到它分配的比例，则优先执行该进程
对于实时进程：使用SCHED_FIFO和SCHED_RR(Round Robin)两种，对于普通进程使用CFS,等级最高的为FIIO,这种进程除非自己让出CPU或者被更高级别的FIFO或RR抢占,否则Linux会一直执行它。RR只是这种线程中的同级别FIFO的平均分配。只有实时进程主动让出或执行完毕后，普通进程才有机会执行。

批处理系统

批处理系统没有太多的用户操作,在该系统中,调度算法目标是保证吞吐量和周转时间(从提交到终止的时间)

1.1 先来先服务(first-come first-serverd(FCFS )
按照请求的顺序进行调度。
有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。
1.2 短作业优先(shortest job first(SJF))
按估计运行时间最短的顺序进行调度
1.3 最短剩余时间优先(shortest remaining time next (SRTN))
按估计剩余时间最短的顺序进行排序

交互式系统

交互式系统有大量的用户交互操作,在该系统中调度算法的目标是快速地进行响应

2.1 时间片轮转
将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。
时间轮转算法的效率和时间片的大小有很大的关系
- 因为进程切换都要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间
- 而如果时间片时间太长,那么实时性就得不到保证
2.2 优先级调度
为每个进程分配一个优先级,按优先级进行调度
为了防止优先级低的进程永远得不到调度,可以随着时间的推移增加等待进程的优先级
2.3 多级反馈队列
一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。
多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,..。进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，之前的进程只需要交换 7 次。
每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

进程同步

临界区

每个进程中,对临界资源进行访问的代码称为临界区**(临界资源是一次仅允许一个进程使用的共享资源**)为了互斥访问临界区资源,每个进程在进入临界区之前,需要先进行检查.
临界区同步速度很快，但却只能用来同步本进程内的线程，而不可用来同步多个进程中的线程

互斥量

互斥:多个线程在同一时刻只有一个线程能进入临界区
互斥量跟临界区很相似，比临界区复杂，互斥对象只有一个，只有拥有互斥对象的线程才具有访问资源的权限

信号量

信号量(Semaphore)是一个整形变量,可以对其执行down和up操作,也就是常见的P和V操作
- down:如果信号量大于0,执行-1操作;如果信号量等于0,j进程睡眠,等待信号量大于0.
- up:对信号量执行+1操作,唤醒睡眠的进程让其完成down操作.
- 如果信号量的取值只能为 0 或者 1，那么就成为了 互斥量（Mutex） ，0 表示临界区已经加锁，1 表示临界区解锁。
down 和 up 操作需要被设计成原语,通常的做法是执行这些操作时,屏蔽中断.如果信号量只有1和0,那么就成为了互斥量(Mutex),0表示临界区已经枷锁,1表示临界区已经解锁

原语:若干个机器指令构成的完成某种特定功能的一段程序，具有不可分割性·即原语的执行必须是连续的，在执行过程中不允许被中断。
1
2
3
4
5
6
7
8
9
10
11
12
typedef int semaphore; semaphore mutex = 1; void P1() { down(&mutex); // 临界区 up(&mutex); } void P2() { down(&mutex); // 临界区 up(&mutex); }

使用信号量实现生产者 - 消费者问题

问题描述：使用一个缓冲区来保存物品，只有缓冲区没有满，生产者才可以放入物品；只有缓冲区不为空，消费者才可以拿走物品。

为了同步生产者和消费者的行为，需要记录缓冲区中物品的数量。数量可以使用信号量来进行统计，这里需要使用两个信号量：empty 记录空缓冲区的数量，full 记录满缓冲区的数量。其中，empty 信号量是在生产者进程中使用，当 empty 不为 0 时，生产者才可以放入物品；full 信号量是在消费者进程中使用，当 full 信号量不为 0 时，消费者才可以取走物品。

注意，不能先对缓冲区进行加锁，再测试信号量。也就是说，不能先执行 down(mutex) 再执行 down(empty)。如果这么做了，那么可能会出现这种情况：生产者对缓冲区加锁后，执行 down(empty) 操作，发现 empty = 0，此时生产者睡眠。消费者不能进入临界区，因为生产者对缓冲区加锁了，消费者就无法执行 up(empty) 操作，empty 永远都为 0，导致生产者永远等待下，不会释放锁，消费者因此也会永远等待下去。

#define N 100
typedef int semaphore;
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;
void producer() {
    while(TRUE) {
        int item = produce_item();
        down(&empty);
        down(&mutex);
        insert_item(item);
        up(&mutex);
        up(&full);
    }
}
void consumer() {
    while(TRUE) {
        down(&full);
        down(&mutex);
        int item = remove_item();
        consume_item(item);
        up(&mutex);
        up(&empty);
    }
}

事件

用来通知线程有一些事件已发生，从而启动后继任务的开始
事件对象通过通知操作的方式来保持线程的同步，并且可以实现不同进程中的线程同步操作

管程

管程指的是管理共享变量以及对共享变量的操作过程，让它们支持并发。翻译为 Java 就是管理类的成员变量和成员方法，让这个类是线程安全的。
使用信号量机制实现的生产者消费者问题需要客户端代码做很多控制，而管程把控制的代码独立出来，不仅不容易出错，也使得客户端代码调用更容易。

c 语言不支持管程，下面的示例代码使用了类 Pascal 语言来描述管程。示例代码的管程提供了 insert() 和 remove() 方法，客户端代码通过调用这两个方法来解决生产者-消费者问题。

    monitor ProducerConsumer
    integer i;
    condition c;
    procedure insert();
    begin
        // ...
    end;
    procedure remove();
    begin
        // ...
    end;
end monitor;

经典同步问题

读者-写者问题
允许多个进程同时对数据进行读操作，但是不允许读和写以及写和写操作同时发生。

一个整型变量 count 记录在对数据进行读操作的进程数量，一个互斥量 count_mutex 用于对 count 加锁，一个互斥量 data_mutex 用于对读写的数据加锁。

typedef int semaphore;
//互斥量,对count加锁
semaphore count_mutex = 1;
//互斥量,对读写的数据加锁
semaphore data_mutex = 1;
//进行读操作的进程数量
int count = 0;
void reader() {
    while(TRUE) {
        down(&count_mutex);
        count++;
        if(count == 1) down(&data_mutex); // 第一个读者需要对数据进行加锁，防止写进程访问
        up(&count_mutex);
        read();
        down(&count_mutex);
        count--;
        if(count == 0) up(&data_mutex);
        up(&count_mutex);
    }
}
void writer() {
    while(TRUE) {
        down(&data_mutex);
        write();
        up(&data_mutex);
    }
}

进程通信IPC

进程同步与进程通信很容易混淆，它们的区别在于：
1. 进程同步：控制多个进程按一定顺序执行；
2. 进程通信：进程间传输信息。
进程通信是一种手段，而进程同步是一种目的。也可以说，为了能够达到进程同步的目的，需要让进程进行通信，传输一些进程同步所需要的信息。

1. 管道

管道是通过调用 pipe 函数创建的，fd[0] 用于读，fd[1] 用于写。
- pipe函数:linux中
限制:
- 只支持半双工通信(单向交替传输)
- 只能在父子进程中使用

2.FIFO

也成为命名管道,去除了管道只能在父子线程中使用的限制

1 2	`#include <sys/stat.h>int mkfifo(const char path, mode_t mode); int mkfifoat(int fd, const char path, mode_t mode);`

FIFO常用于客户-服务器应用程序中,FIFO用作汇聚点,在客户进程和服务器进程之间传递数据

3.消息队列

相比于FIFO,消息队列具有以下特点
- 消息队列可以独立于读写进程存在，从而避免了 FIFO 中同步管道的打开和关闭时可能产生的困难；
- 避免了FIFO的同步阻塞问题,不需要进程自己提供同步方法
- 读进程可以根据消息类型有选择地接收消息,而不像FIFO那样只能默认地接收
消息队列的本质就是存放在内存中的消息的链表，而消息本质上是用户自定义的数据结构
由于用户进程写入数据到内存中的消息队列时，会发生从用户态拷贝数据到内核态的过程；同样的，另一个用户进程读取内存中的消息数据时，会发生从内核态拷贝数据到用户态的过程。因此，如果数据量较大，使用消息队列就会造成频繁的系统调用，也就是需要消耗更多的时间以便内核介入。
消息队列通信过程中，存在用户态与内核态之间的数据拷贝开销

4.信号量和PV操作

它是一个计数器,用于为多个进程提供共享数据对象的访问。本质是一个数组，数组的元素（信号量）都是1，使用P操作进行-1，使用V操作+1.
为了获得共享资源，有如下操作
- 创建一个信号量：这要求调用者指定初始值，对于二值信号量来说，它通常是1，也可是0。
- 等待一个信号量：该操作会测试这个信号量的值，如果小于0，就阻塞，也称为P操作。
- 挂出一个信号量：该操作将信号量的值加1，也称为V操作。

5. 信号

信号和信号量是完全不同的两个概念！
信号是进程通信机制中唯一的异步通信机制，它可以在任何时候发送信号给某个进程。通过发送指定信号来通知进程某个异步事件的发送，以迫使进程执行信号处理程序。信号处理完毕后，被中断进程将恢复执行。用户、内核和进程都能生成和发送信号。

6.共享内存

允许多个进程共享一个给定的存储区。因为数据不需要在进程之间复制，所以这是最快的一种 IPC。
两个不同进程的逻辑地址通过页表映射到物理空间的同一区域，它们所共同指向的这块区域就是共享内存。
需要使用信号量用来同步对共享存储的访问。
多个进程可以将同一个文件映射到它们的地址空间从而实现共享内存。另外 XSI 共享内存不是使用文件，而是使用使用内存的匿名段.

7.套接字Socket

与其它通信机制不同的是，它可用于不同机器间的进程通信。
Socket 的本质其实是一个编程接口（API），是应用层与 TCP/IP 协议族通信的中间软件抽象层，它对 TCP/IP 进行了封装。它把复杂的 TCP/IP 协议族隐藏在 Socket 接口后面

死锁

产生原因

系统资源的竞争：系统资源的竞争导致系统资源不足，以及资源分配不当，导致死锁。
进程运行推进顺序不合适：进程在运行过程中，请求和释放资源的顺序不当，会导致死锁。

发生死锁的四个必要条件

互斥条件：一个资源每次只能被一个进程使用，即在一段时间内某资源仅为一个进程所占有，此时若有其他进程请求该资源，则请求进程只能等待
请求与保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求时，该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放（可以通过一次性申请所有资源来避免）
不可剥夺条件:进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放且只能是主动释放 (占用部分资源的线程进一步申请其他资源时，如果申请不到，可以主动释放它占有的资源，可以避免出现这种情况)
循环等待条件: 若干进程间形成首尾相接循环等待资源的关系（靠按序申请资源来预防）
其中，互斥这个条件我们没有办法破坏，因为我们用锁为的就是互斥

存储系统

局部性原理

一个良好的计算机程序常常具有良好的局部性，也就是说，它们倾向于引用邻近于其他最近引用过的数据项的数据项，或者最近引用过的数据项本身
时间局部性
- 时间局部性是指如果程序中的某条指令一旦执行，则不久之后该指令可能再次被执行；如果某数据被访问，则不久之后该数据可能再次被访问。强调数据的重复访问。利用时间局部性，缓存在现代程序系统中扮演着重要角色，数据缓存，磁盘缓存，文件缓存等，极大提高数据的重复访问性能。
空间局部性
- 空间局部性是指一旦程序访问了某个存储单元，则不久之后。其附近的存储单元也将被访问。强调连续空间数据的访问，一般顺序访问每个元素（步长为1）时具有最好的空间局部性，步长越大，空间局部性越差。

磁盘预读

计算机系统是分页读取和存储的，一般一页为4kb,每次读取和存储的最小单元为一页，而磁盘预读时通常会读取页的整倍数

存储层次

寄存器：最快的访问
高速缓存(L1~L3:SRAM):高速缓存钟的访问速度为纳秒级，非常快
- 第一级高速缓存（L1）：通常访问只需要几个周期，通常是几十个kb
- 第二级高速缓存（L2）：比L1约有2到10倍较高延迟性，通常是几百个kb或更多
- 第三级高速缓存（L3）：不一定有，比L2更高的延迟性，通常由数MB之大
- 第四级高速缓存（L4）：不普遍，CPU外部的DRAM，但速度较主存高
主存(DRAM)：访问需要几百个周期，容量非常大，持久化保存数据

内存管理

逻辑地址和物理地址
- 通过MMU使用虚拟寻址，CPU 需要将虚拟地址翻译成物理地址，这样才能访问到真实的物理内存。
需要虚拟地址的优势
- 可以使用一系列相邻的虚拟地址来访问物理内存中不相邻的大内存缓冲区。
- 可以使用一系列虚拟地址来访问大于可用物理内存的内存缓冲区。
- 不同进程使用的虚拟地址彼此隔离，一个进程中的代码无法更改正在由另一进程或操作系统使用的物理内存。

虚拟内存

为了解决互相打扰的问题
- 虚拟空间多大：寻址空间—-64位系统 2^64byte
- 内存映射：偏移量+段的基地址=线性地址（虚拟空间）
- 线性地址通过OS和MMU（Merory Management Unit）来映射到真正的物理地址
特征
- 一个以上的虚拟地址可以指向同一个物理内存地址。
- 虚拟内存空间可大于实际可用的物理地址。
虚拟内存是计算机系统内存管理的一种技术。它使得应用程序认为它拥有连续可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。
虚拟内存被分为用户空间和内核空间两部分，当我们在用户态的时候，只能访问用户空间。只有进入内核态，才能访问内核空间

虚拟页

把内存分成固定大小的页框(4k) ,把硬盘上的程序也分成4k大小的块，用到那一块加载那一块，加载过程中，如果内存已满，会把最不常用的一块放到swap分区。
系统将虚拟内存分割为称为虚拟页(Virtual Page,VP)的大小固定的块，每个虚拟页的大小为P = 2^p字节，类似地，物理内存被分割为物理页(Physical Page,PP)，大小也为P字节（物理页也称为页帧(page frame)）。
任意时刻，虚拟页面都分为互不相交的三种：
- 未分配的：系统还未分配（或者创建）的页。未分配的块没有任何数据和它们相关联，因此也就不占用任何磁盘空间
- 未缓存的：没有缓存在物理存储器中的已分配页
- 缓存的：当前缓存在物理存储器中的已分配页

页表

页表是一种特殊的数据结构，存放着各个虚拟页的状态，是否映射，是否缓存.。
页表的每一个表项分为两部分，
- 第一部分记录此页是否在物理内存上
- 第二部分记录物理内存页的地址(如果在的话)。当进程访问某个虚拟地址，就会先去看页表，如果发现对应的数据不在物理内存中，则发生缺页异常。
图中展示了一个页表的基本组织结构，页表就是一个页表条目(Page Table Entry,PTE)的数组，每个PTE由一个有效位(valid bit)和一个地址组成，有效位表明了该虚拟页当前是否存在于物理内存中，如果有效位是1，该PTE中就会存储物理内存中相应的物理页的起始地址。如果有效位是0，且PTE中的地址为null，这表示这个虚拟页还未被分配，而如果有效位是0且PTE中有地址，那么这个地址指向该虚拟页在磁盘上的起始位置
上图的示例展示了一个有8个虚拟页和4个物理页的系统的页表，四个虚拟页（VP1、VP2、VP4和VP7）当前存储于物理内存中，两个页（VP0和VP5）还未被分配（也就是什么都没存的虚拟内存，在磁盘和物理内存中都不存在这个空间），而剩下的页（VP3和VP6）已经被分配了，但是还未缓存进物理内存（也就是存在于磁盘上）
在上面的过程中，CPU读包含在VP1中的一个数据时，地址翻译硬件将虚拟地址作为一个索引找到页表中的PTE 2，然后再从PTE 2中保存的物理地址从真正的物理内存中读到这个数据，在有效位为1的PTE中成功找到对应的物理页就称之为页命中

缺页异常

如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统将相应的页面或段调入到内存，然后继续执行程序；
页面置换算法
- 当发生缺页中断时，如果当前内存中并没有空闲的页面，操作系统就必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。

CPUCache

CPU Cache 通常分为三级缓存：L1 Cache、L2 Cache、L3 Cache，级别越低的离 CPU 核心越近，访问速度也快，但是存储容量相对就会越小。其中，在多核心的 CPU 里，每个核心都有各自的 L1/L2 Cache，而 L3 Cache 是所有核心共享使用的。

CPU Cache 是由很多个 Cache Line 组成的，CPU Line 是 CPU 从内存读取数据的基本单位，而 CPU Line 是由各种标志（Tag）+ 数据块（Data Block）组成

CacheLine

CPU Line 是 CPU 从内存读取数据的基本单位，而 CPU Line 是由各种标志（Tag）+ 数据块（Data Block）组成

写直达

保持内存与 Cache 一致性最简单的方式是，把数据同时写入内存和 Cache 中，这种方法称为写直达（*Write Through*）。
在这个方法里，写入前会先判断数据是否已经在 CPU Cache 里面了：
- 如果数据已经在 Cache 里面，先将数据更新到 Cache 里面，再写入到内存里面；
- 如果数据没有在 Cache 里面，就直接把数据更新到内存里面。
写直达法很直观，也很简单，但是问题明显，无论数据在不在 Cache 里面，每次写操作都会写回到内存，这样写操作将会花费大量的时间，无疑性能会受到很大的影响。

写回

当发生写操作时，新的数据仅仅被写入 Cache Block 里，只有当修改过的 Cache Block「被替换」时才需要写到内存中
如果当发生写操作时，数据已经在 CPU Cache 里的话，则把数据更新到 CPU Cache 里，同时标记 CPU Cache 里的这个 Cache Block 为脏（Dirty）的，这个脏的标记代表这个时候，我们 CPU Cache 里面的这个 Cache Block 的数据和内存是不一致的，这种情况是不用把数据写到内存里的；
如果当发生写操作时，数据所对应的 Cache Block 里存放的是「别的内存地址的数据」的话，就要检查这个 Cache Block 里的数据有没有被标记为脏的，如果是脏的话，我们就要把这个 Cache Block 里的数据写回到内存，然后再把当前要写入的数据，写入到这个 Cache Block 里，同时也把它标记为脏的；如果 Cache Block 里面的数据没有被标记为脏，则就直接将数据写入到这个 Cache Block 里，然后再把这个 Cache Block 标记为脏的就好了。

写传播

某个 CPU 核心里的 Cache 数据更新时，必须要传播到其他核心的 Cache，这个称为写传播（*Wreite Propagation*）

事务串行化

某个 CPU 核心里对数据的操作顺序，必须在其他核心看起来顺序是一样的，这个称为事务的串形化（*Transaction Serialization*）。
解释
- 假设我们有一个含有 4 个核心的 CPU，这 4 个核心都操作共同的变量 i（初始值为 0 ）。A 号核心先把 i 值变为 100，而此时同一时间，B 号核心先把 i 值变为 200，这里两个修改，都会「传播」到 C 和 D 号核心。
- 那么问题就来了，C 号核心先收到了 A 号核心更新数据的事件，再收到 B 号核心更新数据的事件，因此 C 号核心看到的变量 i 是先变成 100，后变成 200。
- 而如果 D 号核心收到的事件是反过来的，则 D 号核心看到的是变量 i 先变成 200，再变成 100，虽然是做到了写传播，但是各个 Cache 里面的数据还是不一致的。
- 所以，我们要保证 C 号核心和 D 号核心都能看到相同顺序的数据变化，比如变量 i 都是先变成 100，再变成 200，这样的过程就是事务的串形化。
- 要实现事务串形化，要做到 2 点：
  - CPU 核心对于 Cache 中数据的操作，需要同步给其他 CPU 核心；
  - 要引入「锁」的概念，如果两个 CPU 核心里有相同数据的 Cache，那么对于这个 Cache 数据的更新，只有拿到了「锁」，才能进行对应的数据更新。

总线嗅探

写传播的原则就是当某个 CPU 核心更新了 Cache 中的数据，要把该事件广播通知到其他核心。最常见实现的方式是总线嗅探（*Bus Snooping*）。

缓存一致性协议：MESI

概念：**MESI**（Modified Exclusive Shared Or Invalid）(也称为伊利诺斯协议，是因为该协议由伊利诺斯州立大学提出）是一种广泛使用的支持写回策略的缓存一致性协议
MESI的状态
CPU中每个缓存行（caceh line)使用4种状态进行标记（使用额外的两位(bit)表示):
1. M: 被修改（Modified)
  该缓存行只被缓存在该CPU的缓存中，并且是被修改过的（dirty),即与主存中的数据不一致，该缓存行中的内存需要在未来的某个时间点（允许其它CPU读取请主存中相应内存之前）写回（write back）主存。
  当被写回主存之后，该缓存行的状态会变成独享（exclusive)状态
2. E:独占的(Exclusive)
  该缓存行只被缓存在该CPU的缓存中，它是未被修改过的（clean)，与主存中数据一致。该状态可以在任何时刻当有其它CPU读取该内存时变成共享状态（shared)。
  同样地，当CPU修改该缓存行中内容时，该状态可以变成Modified状态
3. S:共享的(Shared)
  该状态意味着该缓存行可能被多个CPU缓存，并且各个缓存中的数据与主存数据一致（clean)，当有一个CPU修改该缓存行中，其它CPU中该缓存行可以被作废（变成无效状态（Invalid））
4. 无效的(Invalid)
  该缓存是无效的（可能有其它CPU修改了该缓存行）。
解释
1. 在一个典型系统中，可能会有几个缓存（在多核系统中，每个核心都会有自己的缓存）共享主存总线，每个相应的CPU会发出读写请求，而缓存的目的是为了减少CPU读写共享主存的次数。
2. 一个缓存除在Invalid状态外都可以满足cpu的读请求，一个Invalid的缓存行必须从主存中读取（变成S或者 E状态）来满足该CPU的读请求。
3. 一个写请求只有在该缓存行是M或者E状态时才能被执行，如果缓存行处于S状态，必须先将其它缓存中该缓存行变成Invalid状态（也既是不允许不同CPU同时修改同一缓存行，即使修改该缓存行中不同位置的数据也不允许）。该操作经常作用广播的方式来完成，例如：RequestFor Ownership (RFO)。
4. 缓存可以随时将一个非M状态的缓存行作废，或者变成Invalid状态，而一个M状态的缓存行必须先被写回主存。
5. 一个处于M状态的缓存行必须时刻监听所有试图读该缓存行相对就主存的操作，这种操作必须在缓存将该缓存行写回主存并将状态变成S状态之前被延迟执行。
6. 一个处于S状态的缓存行也必须监听其它缓存使该缓存行无效或者独享该缓存行的请求，并将该缓存行变成无效（Invalid）。
7. 一个处于E状态的缓存行也必须监听其它缓存读主存中该缓存行的操作，一旦有这种操作，该缓存行需要变成S状态。
8. 对于M和E状态而言总是精确的，他们在和该缓存行的真正状态是一致的。而S状态可能是非一致的，如果一个缓存将处于S状态的缓存行作废了，而另一个缓存实际上可能已经独享了该缓存行，但是该缓存却不会将该缓存行升迁为E状态，这是因为其它缓存不会广播他们作废掉该缓存行的通知，同样由于缓存并没有保存该缓存行的copy的数量，因此（即使有这种通知）也没有办法确定自己是否已经独享了该缓存行。
  从上面的意义看来E状态是一种投机性的优化：如果一个CPU想修改一个处于S状态的缓存行，总线事务需要将所有该缓存行的copy变成Invalid状态，而修改E状态的缓存不需要使用总线事务

零拷贝

四次拷贝的情况

用户应用进程调用read函数，向操作系统发起IO调用，上下文从用户态转为内核态（切换1）
DMA控制器把数据从磁盘中，读取到内核缓冲区。
CPU把内核缓冲区数据，拷贝到用户应用缓冲区，上下文从内核态转为用户态（切换2），read函数返回
用户应用进程通过write函数，发起IO调用，上下文从用户态转为内核态（切换3）
CPU将用户缓冲区中的数据，拷贝到socket缓冲区
DMA控制器把数据从socket缓冲区，拷贝到网卡设备，上下文从内核态切换回用户态（切换4），write函数返回
传统IO的读写流程，包括了4次上下文切换（4次用户态和内核态的切换），4次数据拷贝（两次CPU拷贝以及两次的DMA拷贝)

零拷贝的两种实现方式

mmap+write

mmap
- 在LINUX中我们可以使用mmap用来在进程虚拟内存地址空间中分配地址空间，创建和物理内存的映射关系
- 使用mmap后的文件拷贝流程
- 应用进程调用了 mmap() 后，DMA 会把磁盘的数据拷贝到内核的缓冲区里。接着，应用进程跟操作系统内核「共享」这个缓冲区；
- 应用进程再调用 write()，操作系统直接将内核缓冲区的数据拷贝到 socket 缓冲区中，这一切都发生在内核态，由 CPU 来搬运数据；
- 最后，把内核的 socket 缓冲区里的数据，拷贝到网卡的缓冲区里，这个过程是由 DMA 搬运的。

sendfile

在 Linux 内核版本 2.1 中，提供了一个专门发送文件的系统调用函数 sendfile(),
- 它可以替代前面的 read() 和 write() 这两个系统调用
- 该系统调用，可以直接把内核缓冲区里的数据拷贝到 socket 缓冲区里，不再拷贝到用户态，这样就只有 2 次上下文切换，和 3 次数据拷贝

SG-DMA

但是这还不是真正的零拷贝技术，如果网卡支持 SG-DMA（The Scatter-Gather Direct Memory Access）技术（和普通的 DMA 有所不同），我们可以进一步减少通过 CPU 把内核缓冲区里的数据拷贝到 socket 缓冲区的过程。
ethtool -k eth0 | grep scatter-gather :查明是否支持scatter-gather
从 Linux 内核 2.4 版本开始起，对于支持网卡支持 SG-DMA 技术的情况下， sendfile() 系统调用的过程发生了点变化，具体过程如下:
- 第一步，通过 DMA 将磁盘上的数据拷贝到内核缓冲区里；
- 第二步，缓冲区描述符和数据长度传到 socket 缓冲区，这样网卡的 SG-DMA 控制器就可以直接将内核缓存中的数据拷贝到网卡的缓冲区里，此过程不需要将数据从操作系统内核缓冲区拷贝到 socket 缓冲区中，这样就减少了一次数据拷贝；
零拷贝（Zero-copy）技术，因为我们没有在内存层面去拷贝数据，也就是说全程没有通过 CPU 来搬运数据，所有的数据都是通过 DMA 来进行传输的。
零拷贝技术的文件传输方式相比传统文件传输的方式，减少了 2 次上下文切换和数据拷贝次数，只需要 2 次上下文切换和数据拷贝次数，就可以完成文件的传输，而且 2 次的数据拷贝过程，都不需要通过 CPU，2 次都是由 DMA 来搬运。
所以，总体来看，零拷贝技术可以把文件传输的性能提高至少一倍以上。

大文件传输

针对大文件的传输，不应该使用 PageCache，也就是说不应该使用零拷贝技术，因为可能由于 PageCache 被大文件占据，而导致「热点」小文件无法利用到 PageCache，这样在高并发的环境下，会带来严重的性能问题
在高并发的场景下，针对大文件的传输的方式，应该使用「异步 I/O + 直接 I/O」来替代零拷贝技术。

01操作系统

操作系统

https://x-leonidas.github.io/2022/02/01/01操作系统/操作系统/

作者

听风

发布于

2022年2月1日

更新于

2025年6月26日

许可协议

二叉树上一篇