裸机（硬件只听得懂二进制指令）——>操作系统（属于软件，提供良好交互界面）——>应用软件——>用户使用
操作系统是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织和调度计算机工作和资源的分配；以提供给用户和其他软件方便的借口和环境；它是计算机系统中最基本的系统软件。
直观eg:
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WW8XyZtb-1686645858091)(file:///C:\Users\25864\AppData\Local\Temp\ksohtml15544\wps1.jpg)]
作为系统资源管理者：
功能 处理机（CPU)管理，存储器管理，文件管理，设备管理
目的 安全 高效
目标 为上层（用户）提供方便易用的服务
封装思想：
操作系统将硬件功能封装成简单易用的服务，使用户能更方便使用计算机，而无需关注底层硬件的原理，只需对操作系统发出指令即可。
（1）图形化用户接口（GUI)
用户可以使用形象的图形界面进行操作，而不再需要记忆复杂的指令参数。
（2）命令接口是用户利用操作系统命令组织和控制作业的执行或管理计算机系统。
联机命令接口=交互式命令接口 用户说一句，系统跟着做一句
eg: 命令解释行
脱机命令接口=批处理命令接口 用户说一堆，系统跟着做一堆
eg: bat文件
（3）程序接口：（系统调用，用户通过程序间接使用）
可以在程序中进行系统调用来使用程序接口。
普通用户不能直接使用程序接口，只能通过程序代码间接使用
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TIwzxBSz-1686645858092)(file:///C:\Users\25864\AppData\Local\Temp\ksohtml15544\wps2.jpg)]
操作系统四大特征：并发、共享、虚拟、异步。
1.并发：指两个或多个事件再同一时间间隔内发生，宏观上同时发生，微观上交替发生
（并行：两个多个事件同一时刻同时发生）
操作系统的并发性指计算机系统中同时存在多个运行着的程序。
一个单核处理机同一时刻只能执行一个程序。
即使现在多核但大部分时刻我们可能同时操作很多很多程序，即使4核，也依然要并发。
2.共享共享指资源共享，指系统中的资源可供内存中多个并发执行的进程共同使用
两种资源共享方式：
互斥共享：一个时间段内只允许一个进程访问该资源
同时共享：一个时间段内多个进程“同时”（宏观上同时，微观上交替）对它进行访问
互斥eg：摄像头
同时eg：
网盘 QQ 微信可以同时从硬盘往外面传输数据（微观上是交替访问硬盘）
打游戏同时听歌 微观上也是同时使用
QQ发送文件A 微信发送文件B
两个进程正在并发执行（并发性）
需要共享地访问硬盘资源（共享性）
如果失去并发性，则系统中只有一个程序正在进行，则共享性失去存在的意义
如果失去共享性，则QQ和微信不能同时访问硬盘资源，也就不能同时发送文件，
也就失去了并发性。
4.虚拟虚拟是指把一个物理上的实体变为若干逻辑上的对应物，
物理实体是实际存在的，而逻辑对应物是用户感受到的。
“空分复用技术”
eg1:
一个程序需要放入内存，并给它分配CPU才能执行
如果程序同时运行的内存>电脑内存总量
运用虚拟存储器技术，就可以同时运行
“时分复用技术”（微观上处理机在各个微小的时间段内交替执行）
eg2:
假设一个单核CPU同时运行六个程序
运用虚拟处理器技术，实际上只有一个单核CPU，在用户看来却有6个CPU同时为自己服务。
如果没有并发性，实际虚拟性也失去了意义
异步
异步是指，在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。
只有系统有并发性，才有可能导致异步性。
手工操作阶段
程序员用纸带手工输入二进制，让计算机进行运算，计算机再进行二进制输出。
缺点：效率太低，计算机大部分时间都在等待用户输入。
批处理阶段
优点：缓解人机速度矛盾
缺点：资源利用率较低
优点：多道程序并发执行，资源利用率高
缺点：不提供人机交互功能
优点：提供人机交互功能
缺点：不能有限处理紧急任务
实时操作系统
硬实时系统
必须在绝对严格的规定时间内完成处理
软实时系统
能接受偶尔违反时间规定
优点：能优先处理紧急任务
网络操作系统
网络操作系统是在网络环境下实现对网络资源的管理和控制的操作系统，是用户与网络资源之间的接口。
网络操作系统是建立在独立的操作系统之上，为网络用户提供使用网络系统资源的桥梁。实现网络中各种资源的共享和各台计算机之间的通信。
分布式操作系统
分布式系统是多个处理机通过通信线路互连而构成的松散耦合的系统
个人计算机操作系统
个人计算机操作系统：即是个人使用的计算机操作系统，如常见的有有Windows，MacOs等，方便个人使用。
程序是如何运行的
指令：就是处理器（CPU）能识别、执行的最基本命令
注：很多人习惯把 Linux、Windows、MacOS 的“小黑框”中使用的命令也称为“指令”，其实这是“交互式命令接口”，注意与本节的“指令”区别开。本节中的“指令”指二进制机器指令
内核程序vs应用程序
我们普通程序员写的程序就是"应用程序"
而对于那些操作系统的开发者，他们写的是"内核程序"，由很多内核程序又能组成操作系统内核简称内核。内核是操作系统的核心部分，也是最接近硬件的部分。
特权指令vs非特权指令
程序运行的过程就是CPU执行一条一条机械指令的过程，在CPU设计和生成的时候就划分了特权指令和非特权指令，因此CPU执行一条指令前就能判断出其类型。
应用程序只能使用非特权指令如：加法指令、减法指令
内核程序有时会让CPU执行一些特权指令，如：内存清零指令。这些指令影响重大只能运行操作系统内核来使用
内核态 vs 用户态
CPU 能判断出指令类型，但是他怎么区分正在运行的是内核程序，还是应用程序呢？
由此引出内核态和用户态。
CPU有两种状态，内核态和用户态
处于内核态时，说明此时正在运行的是内核程序，此时特权指令和非特权指令都可执行
处于用户态时，说明此时正在运行的是应用程序，此时只能执行非特权指令
内核态、用户态 的切换
一个故事：
① 刚开机时，CPU 为“内核态”，操作系统内核程序先上CPU运行
② 开机完成后，用户可以启动某个应用程序
③ 操作系统内核程序在合适的时候主动让出 CPU，让该应用程序上CPU运行（操作系统内核让出CPU之前，会用一条特权指令将PSW的标志设置为“用户态”）
④ 应用程序运行在“用户态”
⑤ 此时，一位猥琐黑客在应用程序中植入了一条特权指令，企图破坏系统…
⑥ CPU发现接下来要执行的这条指令是特权指令，但是自己又处于“用户态”
⑦ 这个非法事件会引发一个中断信号(CPU检测到中断信号后，会立即变为“核心态”，并停止运行当前的应用程序，转而运行处理中断信号的内核程序)
⑧ “中断”使操作系统再次夺回CPU的控制权
⑨ 操作系统会对引发中断的事件进行处理，处理完了再把CPU使用权交给别的应用程序
内核态->用户态：执行一条特权指令——修改PSW的标志位用户态，这个动作意味着操作系统将主动让出CPU的使用权
用户态->内核态：由中断引起,硬件自动完成变态过程,触发中断信号意味着操作系统将强行夺回CPU的使用权
注：除了非法使用特权指令以外，还有很多事件会触发中断指令。记住只要需要操作系统接入，就会触发中断指令。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-n5lU6Rdq-1686645858093)(file:///C:\Users\25864\AppData\Local\Temp\ksohtml15544\wps3.jpg)]
中断的作用:中断会使cpu由用户态转化为内核态，使得操作系统重新夺回cpu的使用权。中断也是让操作系统夺回cpu使用权的唯一路径。
如果没有中断机制会导致cpu一直执行某一个应用程序，从而导致无法进行并发，所以一定要实现中断。
中断的类型
**内中断：**与当前执行的指令有关，中断信息来源于cpu内部。
**外中断：**与当前执行的代码无关，中断信息来源于cpu外部。
内中断例子：
用户态下，发现特权指令就会引发中断，从而转化为内核态，处理中断信号的内核程序。
执行除法指令时发现除数为0.
int main（void){ int i=i/0; }//除0错误，异常[Warning] division by zero [-Wdiv-by-zero]
所以如果执行指令非法或者参数非法或者主动想要切换内核态，就会引发内中断。
“系统调用”是操作系统提供给应用程序（程序员/编程人员）使用的接口，可以理解为一种可供应用程序调用的特殊函数， 应用程序可以通过系统调用来请求获得操作系统内核的服务。
**系统调用和库函数区别：**库函数可能也会使用系统调用。
其他：
特性，思想
所有的系统功能都放在内核里(大内核结构的OS通常也采用了"模块化"的设计思想)
优点
缺点
特性，思想
只把中断、原语、进程通信等最核心的功能放入内核。进程管理、文件管理、设备管理等功能以用户进程的形式运行在用户态
优点
缺点
特性，思想
内核分多层，每层可单向调用更低一层提供的接口
优点
缺点
特性，思想
将内核划分为多个模块，各模块之间相互协作。
内核=主模块+可加载内核模块
主模块:只负责核心功能，如进程调度、内存管理
可加载内核模块:可以动态加载新模块到内核,而无需重新编译整个内核
优点
缺点
特性，思想
内核负责进程调度、进程通信等功能，外核负责为用户进程分配未经抽象的硬件资源，且由外核负责保证资源使用安全
优点
缺点
操作系统（如Windows、Linux等）是一种程序，程序以数据的形式存放在硬盘中，而硬盘通常分为多个分区，一台计算机中又有多个或多种外部存储设备。操作系统引导是指计算机利用CPU运行特定程序，通过程序识别硬盘，识别硬盘分区，识别硬盘分区上的操作系统，最后通过程序启动操作系统，一环扣一环地完成上述过程。
常见操作系统的引导过程如下：
1）激活CPU
激活的CPU读取ROM(只读存储器)中的boot程序，将指令寄存器置为BIOS（基本输入/输出系统）的第一条指令，即开始执行BIOS的指令。
2）硬件自检
启动BIOS程序后，先进行硬件自检，检查硬件是否出现故障。如有故障，主板会发生不同含义的蜂鸣，启动中止；如无故障，屏幕会显示CPU、内存、硬盘等信息。
3）加载带有操作系统的硬盘
硬件自检后，BIOS开始读取Boot Sequence(通过CMOS （Complementary Metal Oxide Semiconductor互补金属氧化物半导体））里保存的启动顺序，或者通过与用户交互的方式)，把控制权交给启动顺序排在第一位的存储设备，然后CPU将该存储设备引导扇区的内容加载到内存中。
4）加载主引导记录MBR
硬盘以特定的标识符区分引导盘和非引导盘。如果发现一个存储设备不是可引导盘，就检查下一个存储设备。如果无其他启动设备，就会死机。主引导记录MBR的作用是告诉CPU去硬盘的哪个主分区去找操作系统。
5）扫描硬盘分区表，并加载硬盘活动分区
MBR包含硬盘分区表，硬盘分区表以特定的标识符区分活动分区和非活动分区。主引导记录扫描硬盘分区表，进而识别含有操作系统的硬盘分区（活动分区）。找到硬盘活动分区后，将控制权交给活动分区。
6）加载分区引导记录PBR
读取活动分区的第一个扇区，这个扇区被称为分区引导记录(PBR)，其作用是寻找并激活分区根目录下用于引导操作系统的程序（启动管理器）。
一、什么是虚拟机(Virtual Machine,VM）？
虚拟机是一类能够通过软件模拟其他系统行为，做到虚拟化、跨平台等目的的一类的软件。Java虚拟机，它们都有很好的虚拟化能力，每一个虚拟机都可以运行一个操作系统。
同义术语：虚拟机管理程序/虚拟机监控程序/Virtual Machine Monitor/Hypervisor
二、虚拟机管理 程序
直接运行在硬件上（第一类VMM）：相比上两种，原生架构就很强大了，它也是可以运行多个操作系统的
①虚拟机软件直接安装在计算机硬件上。
②虚拟机本身就是一个操作系统。
运行在宿主操作系统（第二类VMM）：此架构可以在应用软件内安装多个操作系统进行操作（可以说是只要电脑配置够，可以安装无数个虚拟机）
①虚拟机作为应用软件安装在操作系统上。
②直接安装在硬件上的系统为宿主系统。
第二类VMM商业化应用更广泛
二者在运行模式上：
第一类VMM运行在最高特权级（Ring 0），考研执行最高特权的指令
第二类部分运行在用户态，部分运行在内核态。GuestOS发出的系统调用会被VMM截获，并转化为VMM对HostOS的系统调用
要想理解进程，首先要了解程序的概念。
**程序：**静态的，存放在磁盘里的可执行文件，是一系列指令的集合。如QQ.exe等
**进程（progress）：**动态的，是程序的一次执行过程，一个程序可以产生多个进程。
既然一个程序可以产生多个进程，那么操作系统是如何区分这些看似相同的进程的呢？原来，当进程被创建的时候，操作系统会为每个进程创建一个PID（progress ID）根据这些唯一的ID就可以实现区分进程的功能。
操作系统将PID以及管理程序所需要的其他信息均存放在一个特殊的数据结构PCB（progress control black，进程控制块）中。
进程主要由以下三个部分组成，其中PCB是给操作系统用的，程序段、数据段是供进程自己使用的，如下图所示：
PCB：PCB是进程存在的唯一标志，当进程被创建时，操作系统为其创建PCB，当进程结束时，会回收其PCB。
PCB存储的主要信息：
我们上面所说的”进程“实际上应该叫做”进程实体“，进程是一个动态过程，进程实体是静态的。进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。不过一般不做区分。
进程主要有以下特征： 结构性、动态性、并发性、独立性、异步性
**结构性：**每个进程都会有一个PCB，进程（实体）由PCB、程序段、数据段构成。
**并发性：**指多个进程实体同存于内存中，且能在一段时间内同时运行。这里应注意，引入进程的目的也正是为了使其进程实体能和其它进程实体并发执行；而程序(没有建立 PCB)是不能并发执行的。
动态性： 进程是程序的一次执行过程，动态地产生以及消亡，这是进程最基本的特性。
**独立性：**进程（实体）是一个能独立运行、独立分配资源和独立接受调度的基本单位。凡未建立 PCB 的程序都不能作为一个独立的单位参与运行。
异步性： 进程按各自独立的、 不可预知的速度向前推进。操作系统会采用进程同步机制来解决异步问题。
因为进程的执行在时间上是不连贯的，所以进程就会有多种状态，其中就绪态、执行态、阻塞态是三种最基本的状态。除此之外进程还可能会有创建态以及终止态。
**（1）创建态：**在进程被创建时他的状态是创建态，这个时候操作系统为进程分配了一些资源，初始化了PCB。但是因为资源不完整所以还不能运行。
**（2）就绪态（Ready）：**创建态结束后，进程便进入“就绪态”，处于就绪态的进程已经具备运行条件，但由于没有空闲CPU，就暂时不能运行。
**（3）执行态：**当CPU空闲时，他会在就绪队列中选择一个就绪态的进程让他上处理机运行，这时程序就进入了执行态。
**（4）阻塞态：**正在执行的进程可能会遇到一些事件（请求IO，申请缓存空间等）而无法继续执行下去，此时进程进入了阻塞态，这个时候CPU会让这个进程下处理机并运行另一个处于就绪态的进程。
**（5）终止态：**一个进程可以执行 exit 系统调用，请求操作系统终止该进程。此时该进程会进入“终止态”，操作系统会让该进程下CPU，并回收内存空间等资源，最后还要回收该进程的PCB。当终止进程的工作完成之后，这个进程就彻底消失了。
下面用一张图说明这几种状态之间的转化情况：
这里我们需要注意一下：就绪态没有办法变为阻塞态，阻塞态也没有办法变为执行态，因为阻塞态是主动请求发生的，必须要进程在运行中才能发出这种请求。
进程PCB中，会有一个变量 state 来表示进程的当前状态。如：1表示创建态、2表示就绪态、3表示运行态…为了对同一个状态下的各个进程进行统一的管理，操作系统会将各个进程的PCB组织起来。主要的进程组织方式有链接方式以及索引方式两种。
**链接方式：**这是把具有同一状态的 PCB，用其中的链接字链接成一个队列。这样，可以形成绪队列、若干个阻塞队列和空白队列等。**对其中的就绪队列常按进程优先级的高低排列，把优先级高的进程的 PCB 排在队列前面。**此外，也可根据阻塞原因的不同而把处于阻塞状态的进程的 PCB 排成等待 I/O 操作完成的队列和等待分配内存的队列等。
**索引方式：**系统根据所有进程的状态建立几张索引表。例如，就绪索引表、阻塞索引表等，并把各索引表在内存的首地址记录在内存的一些专用单元中。在每个索引表的表目中，记录具有相应状态的某个 PCB 在 PCB 表中的地址。
知识总览图
什么是进程控制？
进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、进程状态状态转换等功能。
简化理解:反正进程控制就是要实现进程状态转换，如下图:
如何实现进程控制？
用原语实现进程控制。原语的特点是执行期间不允许中断，只能一起呵成。这种不可被中断的操作即原子操作。原语采用“关中断指令”和“开中断指令”实现，当关中断指令执行之后，原语代码是不能被外部中断信号干扰的，所有的原语代码执行的时候一气呵成，中间不会中断，当开中断指令执行之后，代码执行时会被外部的中断信号干扰，如下图:
显然，关/开中断指令的权限非常大，必然是只允许在核心态下执行的特权指令。
原语学习技巧:进程控制会导致进程状态的转换。无论哪个原语，要做的无非三类事情:
1.更新PCB中的信息(如修改进程状态标志、将运行环境保存到PCB、从PCB恢复运行环境)
a.所有的进程控制原语一定都会修改进程状态标志
b.剥夺当前运行进程的CPU使用权必然需要保存其运行环境
c.某进程开始运行前必然要恢复其运行环境
2.将PCB插入合适的队列
3.分配/回收资源
进程创建的原语,如下图:
进程撤销的原语，如下图:
进程阻塞和唤醒的原语，如下图:
进程切换的原语，如下图:
知识总览
一、什么是进程通信？
进程通信就是指进程之间的信息交换。
进程是分配系统资源的单位（包括内存地址空间)，因此各进程拥有的内存地址空间相互独立。
二、进程通信
1、共享存储
基于数据结构的共享：比如共享空间里只能放一个长度为10的数组。这种共享方式速度慢、限制多，是一种低级通信方式。
基于存储区的共享：在内存中画出一块共享存储区，数据的形式、存放位置都由进程控制，而不是操作系统。相比之下，这种共享方式速度更快，是一种高级通信方式。
两个进程对共享空间的访问必须是互斥的（互斥访问通过操作系统提供的工具实现）。
操作系统只负责提供共享空间和同步互斥工具（如P、v操作)
2、管道通信
管道只能采用半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道。
各进程要互斥地访问管道。（当进程1往管道写数据时，进程2是不允许访问管道的，只有进程1把管道给释放了，进程2 才能读）
数据以字符流的形式写入管道，当管道写满时，写进程的write()系统调用将被阻塞。等待读进程将数据取走，此时读进程的read()系统调用将被阻塞。
数据一旦被读出，就从管道中被抛弃，这就意味着读进程最多只能有一个，否则可能会有读错数据况。
在一个管道中允许多个写进程，一个读进程
问：管道里边数据传输的怎么实现的？
答：首先进程1会往管道里边写数据，当管道里边数据写满了之后，进程2才能从里边读取数据，而只有数据被全部读取之后，进程1才能继续往里边写数据。
3、消息传递
进程间的数据交换以格式化的消息(Message）为单位。进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换。
一个格式化消息会分为消息头和消息体
直接通信方式就是将消息直接挂到接收进程的消息缓冲队列上，每个进程会有一个消息缓冲队列，然后如果有另外一个进程想给它发送消息的时候，这个进程会首先创建好这个消息体，格式化的消息体，然后这个消息会通过发送原语发送给目标进程，这个消息就会被挂到目标进程的消息缓冲队列的队尾，然后这个进程又会通过接收原语来依次把这些队列当中的这些消息一个一个取走，然后进行处理，这就是直接通信方式。
间接通信方式其实也比较类似，只不过这些消息是需要先发送到一个中间实体，这个中间实体可以称之为信箱，所以间接通信方式也可以称之为信箱通信方式，比如说像计算机网络之后会学到的电子邮件系统就是一种间接通信方式，一种信箱通信方式，系统会为各个通信的进程管理一个信箱，而这个信箱当中可能会有各种各样的消息，并且这些消息可能是不同的进程之间通信的一些消息，那具体是由哪个进程发，由哪个进程接收，这些都是在消息头里会包含的一些数据，所以并不用不需要担心这些消息会被举错，那么如果一个进程想要给另外一个进程发送消息的话，这个消息会用发送原语先发送到这个中间实体信箱当中，之后读进程会用接收原语再从信箱当中取走属于自己的消息。
知识回顾与重要考点
线程概念
1、什么是线程？如何理解线程？
我们先说一下进程，什么是进程呢？
对于进程而言：
站在我们用户这边来谈进程，它就是系统中运行起来的程序；
站在操作系统这个角度来谈进程，每一个进程它都有很多信息来描述它 – PCB ，在 Linux 下这个描述进程信息的结构体就是 task_struct 。通过命令 ps -[参数选项] 来查看进程
再谈线程
**官方定义：**线程是一个进程内部的控制序列；
我自己的理解：Linux 下 CPU 调度是以 PCB 来进行调度的，
Linux 下线程是以进程控制块 PCB 进行模拟的，所以说 PCB 就是对线程的描述， Linux 下进程、线程不作区分
因此线程是一个轻量级进程，一个进程中至少有一个线程，线程是进程内的一条执行流；通过命令 ps -efL 查看；其中[tgid] 轻量级进程 ID 、[pid] 是线程组（主线程 ID)
这时候，原来的进程就变成了具有一个或者多个线程的线程组
从而可能一个进程会有多个线程，它们都使用了相同的虚拟地址空间
线程的安全性
因此：线程调度切换、线程的创建与销毁的成本将大大减少
但是共享了同一个虚拟地址空间，就出现了数据访问的不唯一性，资源争抢问题突出、一些系统调用和异常都针对于整个进程，进程崩溃的情况下所有线程都会退出、稳定性差 ---- 线程的安全性
线程、进程优缺点
2、线程的优缺点？
线程的优点：
一个进程可能会有多个线程，而这些线程共享了同一个虚拟地址空间，因此有时候也说线程是运行在进程当中的
它们共享了虚拟地址空间因此线程间通信就变得极为方便
创建或者销毁一个线程的成本相对于进程来说成本低（不需要额外创建地址空间）
线程的调度切换相对于进程成本较低
线程的缺点：
线程、进程各自的区别
3、多线程与多进程的区别？
线程、进程的使用场景
4、在什么情况下使用线程什么情况下使用进程？
1）需要频繁创建销毁的优先用线程
原因请看上面的对比。
这种原则最常见的应用就是Web服务器了，来一个连接建立一个线程，断了就销毁线程，要是用进程，创建和销毁的代价是很难承受的
2）需要进行大量计算的优先使用线程
所谓大量计算，当然就是要耗费很多CPU，切换频繁了，这种情况下线程是最合适的。
这种原则最常见的是图像处理、算法处理。
3）强相关的处理用线程，弱相关的处理用进程
什么叫强相关、弱相关？理论上很难定义，给个简单的例子就明白了。
一般的Server需要完成如下任务：消息收发、消息处理。“消息收发”和“消息处理”就是弱相关的任务，而“消息处理”里面可能又分为“消息解码”、“业务处理”，这两个任务相对来说相关性就要强多了。因此“消息收发”和“消息处理”可以分进程设计，“消息解码”、“业务处理”可以分线程设计。
当然这种划分方式不是一成不变的，也可以根据实际情况进行调整。
4）可能要扩展到多机分布的用进程，多核分布的用线程
原因请看上面对比。
5）都满足需求的情况下，用你最熟悉、最拿手的方式
至于“数据共享、同步”、“编程、调试”、“可靠性”这几个维度的所谓的“复杂、简单”应该怎么取舍，我只能说：没有明确的选择方法。但我可以告诉你一个选择原则：如果多进程和多线程都 能够满足要求，那么选择你最熟悉、最拿手的那个。
一.用户级线程
在用户级线程中，有关线程管理（线程的创建、撤销和切换等）的所有工作都由应用程序完成，内核意识不到线程的存在。应用程序可以通过使用线程库设计成多线程程序。通常，应用程序从单线程开始，在该线程中开始运行，在其运行的任何时刻，可以通过调用线程库中的派生例程创建一个在相同进程中运行的新线程。
二、内核级线程
在内核级线程中，线程管理的所有工作由内核完成，应用程序没有进行线程管理的代码，只有一个到内核级线程的编程接口。内核为进程及其内部的每个线程维护上下文信息，调度也在内核基于线程架构的基础上完成。
三、组合实现
有些系统中使用组合方式的多线程实现。线程创建完全在用户空间中完成，线程的调度和同步也在应用程序中进行。一个应用程序中的多个用户级线程被映射到一些（小于等于用户级线程的数目）内核级线程上。
四、多线程模型
有些系统同时支持用户线程和内核线程，由此产生了不同的多线程模型，即实现用户级线程和内核级线程的连接方式。
1、多对一模型
将多个用户级线程映射到一个内核级线程，线程管理在用户空间完成。此模式中，用户级线程对操作系统不可见（即透明）。
**优点：**线程管理是在用户空间进行的，因而效率比较高。
**缺点：**一个线程在使用内核服务时被阻塞，整个进程都会被阻塞；多个线程不能并行运行在多处理机上。
2、一对一模型
将每个用户级线程映射到一个内核级线程。
**优点：**当一个线程被阻塞后，允许另一个线程继续执行，所以并发能力较强。
**缺点：**每创建一个用户级线程都需要创建一个内核级线程与其对应，这样创建线程的开销比较大，会影响到应用程序的性能。
3、多对多模型
将n个用户级线程映射到m个内核级线程上，要求m≤n。
**特点：**多对多模型是多对一模型和一对一模型的折中，既克服了多对一模型并发度不高的缺点，又克服了一对一模型的一个用户进程占用太多内核级线程而开销太大的缺点。此外，还拥有多对一模型和一对一模型各自的优点，可谓集两者之所长。
一、线程状态概述
当线程被创建并启动以后，它既不是一启动就进入了执行状态，也不是一直处于执行状态。在线程的生命周期中， 有几种状态呢？在API中 java.lang.Thread.State 这个枚举中给出了六种线程状态：
这里先列出各个线程状态发生的条件，下面将会对每种状态进行详细解析 。
二、线程的状态图
三、状态详细说明
3.1 初始状态(NEW)
New 表示线程被创建但尚未启动的状态：当我们用 new Thread() 新建一个线程时，如果线程没有开始运行 start() 方法，所以也没有开始执行 run() 方法里面的代码，那么此时它的状态就是 New。而一旦线程调用了 start()，它的状态就会从 New 变成 Runnable
3.2 可运行状态(RUNNABLE)
Java 中的 Runable 状态对应操作系统线程状态中的两种状态，分别是 Ready 和Running ，也就是说，Java 中处于 Runnable 状态的线程有可能正在执行，也有可能没有正在执行，正在等待被分配 CPU 资源。
注意：
如果一个正在运行的线程是 Runnable 状态，当它运行到任务的一半时，执行该线程的 CPU 被调度去做其他事情，导致该线程暂时不运行，它的状态依然不变，还是 Runnable，因为它有可能随时被调度回来继续执行任务。
3.2.1 就绪状态(RUNNABLE之READY)
3.2.2 运行中状态(RUNNABLE之RUNNING)
线程调度程序从可运行池中选择一个线程作为当前线程时线程所处的状态。这也是线程进入运行状态的唯一的一种方式。
3.3 阻塞状态
在 Java 中阻塞状态通常不仅仅是 Blocked，实际上它包括三种状态，分别是 Blocked(被阻塞）、Waiting(等待）、Timed Waiting(计时等待），这三种状态统称为阻塞状态。
3.3.1 Blocked(被阻塞)
从 Runnable 状态进入 Blocked 状态只有一种可能，就是进入 synchronized 保护的代码时没有抢到 monitor 锁，无论是进入 synchronized 代码块，还是 synchronized 方法，都是一样。
3.3.2 Waiting(等待)
处于这种状态的线程不会被分配CPU执行时间，它们要等待被显式地唤醒，否则会处于无限期等待的状态。
线程进入 Waiting 状态有三种可能性：
没有设置 Timeout 参数的 Object.wait() 方法。
没有设置 Timeout 参数的 Thread.join() 方法。
LockSupport.park() 方法。
刚才强调过，Blocked 仅仅针对 synchronized monitor 锁，可是在 Java 中还有很多其他的锁，比如 ReentrantLock，如果线程在获取这种锁时没有抢到该锁就会进入 Waiting 状态，因为本质上它执行了 LockSupport.park() 方法，所以会进入 Waiting 状态。同样，Object.wait() 和 Thread.join() 也会让线程进入 Waiting 状态。
Blocked 与 Waiting 的区别是 Blocked 在等待其他线程释放 monitor 锁，而 Waiting 则是在等待某个条件，比如 join 的线程执行完毕，或者是 notify()/notifyAll()
3.3.3 Timed_Waiting(限期等待)
处于这种状态的线程不会被分配CPU执行时间，不过无须无限期等待被其他线程显示地唤醒，在达到一定时间后它们会自动唤醒。
以下情况会让线程进入 Timed_Waiting 状态。
设置了时间参数的 Thread.sleep(long millis) 方法；
设置了时间参数的 Object.wait(long timeout) 方法；
设置了时间参数的 Thread.join(long millis) 方法；
设置了时间参数的 LockSupport.parkNanos(long nanos) 方法和 LockSupport.parkUntil(long deadline) 方法。
3.3.4 阻塞状态流转到下一个状态说明
想要从 Blocked 状态进入 Runnable 状态，要求线程获取 monitor 锁即可。
而从 Waiting 状态流转到其他状态则比较特殊，因为首先 Waiting 是不限时的，也就是说无论过了多长时间它都不会主动恢复。只有当执行了 LockSupport.unpark()，或者 join 的线程运行结束，或者被中断时才可以进入 Runnable 状态。如果其他线程调用 notify() 或 notifyAll()来唤醒它，它会直接进入 Blocked 状态，这是因为唤醒 Waiting 线程的线程，如果调用 notify() 或 notifyAll()，要求必须首先持有该 monitor 锁，所以如果处于 Waiting 状态的线程被唤醒时拿不到该锁，就会进入 Blocked 状态，直到执行了 notify()/notifyAll() 的唤醒它的线程执行完毕并释放 monitor 锁，才可能轮到它去抢夺这把锁，如果它能抢到，就会从 Blocked 状态回到 Runnable 状态。
同样在 Timed_Waiting 状态 中执行 notify() 和 notifyAll() 也是一样的道理，它们会先进入 Blocked 状态，然后抢夺锁成功后，再回到 Runnable 状态。当然对于 Timed_Waiting 而言，如果它的超时时间到了且能直接获取到锁/join的线程运行结束/被中断/调用了LockSupport.unpark()，会直接恢复到 Runnable 状态，而无需经历 Blocked 状态。
3.4 终止状态(TERMINATED)
要想进入这个状态有两种可能：
run() 方法执行完毕，线程正常退出。
出现一个没有捕获的异常，终止了 run() 方法，最终导致意外终止。
注意：
当线程的run()方法完成时，或者主线程的main()方法完成时，我们就认为它终止了。这个线程对象也许是活的，但是它已经不是一个单独执行的线程。线程一旦终止了，就不能复生。
在一个终止的线程上调用start()方法，会抛出java.lang.IllegalThreadStateException异常。
3.5 线程转换注意事项
**高级调度（作业调度）：按一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。**每个作业只调入一次，调出一次。作业调入时会建立PCB，调出时才撤销PCB。
低级调度（进程调度/处理机调度）：按照某种策略从就绪队列中选取一个进程，将处理机分配给它。
进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。
进程调度效率很高，一般几十毫秒一次
中级调度（内存调度）：按照某种策略决定将哪个处于挂起状态的进程重新调入内存
内存不够时，可将某些进程的数据调出外存。等内存空闲或者进程需要运行时再重新调入内存。
暂时调到外存等待的进程状态为挂起状态。被挂起的进程PCB会被组织成挂起队列
一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要比高级调度更高
补充知识
暂时调到外存等待的进程状态为挂起状态（挂起态，suspend）
挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态
七状态模型
注意“挂起”与“阻塞”的区别：
两种状态都是暂时不能获得CPU服务，但挂起态是将进程映像调到外存去了，而阻塞态下进程映像还在内存中。
有的操作系统会把就绪挂起、阻塞挂起分为两个挂起队列，甚至会根据阻塞原因不同再把阻塞挂起进程进一步细分为多个队列
知识总览图
进程调度的时机
进程调度(低级调度)，就是按照某种算法从就绪队列中选择一个进程为其分配处理机。
例题
**临界资源:**一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源。
临界区:访问临界资源的那段代码。
内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列(由各就绪进程的PCB组成)
如果还没退出内核程序临界区(还没解锁)就进行进程调度，但是进程调度相关的程序肯定要访问就绪队列这个临界资源，因为它需要从就绪队列中挑选一个线程，为它分配处理机，但此时就绪队列被锁住了，因此又无法顺利进行进程调度。
内核程序临界区访问的临界资源如果不尽快释放的话，极有可能影响到操作系统内核的其他管理工作。因此在访问内核程序临界区期间不能进行调度与切换。
在打印机打印完成之前，进程一直处于临界区内，临界资源不会解锁。但打印机又是慢速设备，此时如果一直不允许进程调度的话就会导致CPU一直空闲。
普通临界区访问的临界资源不会直接影响操作系统内核的管理工作。因此在访问普通临界区时可以进行调度与切换。
进程的调度方式
进程的切换与过程
“狭义的进程调度”与“进程切换”的区别：
狭义的进程调度指的是从就绪队列中选中一个要运行的进程。（这个进程可以是刚刚被暂停执行的进程，也可能是另一个进程，后一种情况就需要进程切换）
进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。
广义的进程调度包含了选择一个进程和进程切换两个步骤。
进程切换的过程主要完成了:
对原来运行进程各种数据的保存
对新的进程各种数据的恢复
(如：程序计数器，程序状态字，各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块中)
注意：进程切换是有代价的，因此如果过于频繁的进行进程调度、切换，必然会使整个系统的效率降低，使系统大部分时间都花在了进程切换上，而真正用于执行进程的时间减少。
CPU运行哪个进程由调度算法决定。
一个进程在CPU上运行的时间由时间片决定。
执行调度器/调度程序的时机：
需要注意：
闲逛进程的特点：
CPU利用率： （CPU处于忙碌时间）÷（CPU总时间）（通常会考察多道程序并发执行的情况下CPU利用率）
系统吞吐量： 单位时间内完成的作业数目
系统吞吐量=（一段时间内完成的作业数目÷一段时间）
周转时间： 作业被提交到系统到作业完成的这段时间
平均周转时间：各个作业周转时间和÷作业数目
带权周转时间：作业周转时间÷作业实际运行时间（带权周转时间越小，用户效果越好）
平均带权周转时间：带权周转时间和÷作业数
等待时间： 进程/作业处于等待处理机状态的时间
相应时间： 用户提交请求到首次产生响应所用的时间
算法规则：按照作业/进程先后顺序进行服务。顾名思义，就是先来的先为你服务，类似于生活中的银行叫号排队，和排队买奶茶。
算法思想：从公平的角度考虑
举个栗子:
10个人去买奶茶，第一个排队的人买100杯奶茶，后边的9个人都买1杯奶茶，但是因为第一个人是先到的，所以要先为第一个人打奶茶，这样的话，对后边的9个人很不友好，后边的9个人等待时间会很长。
优点：公平
缺点：不利于短作业进程
于是就引出了短作业优先算法
算法规则：要求服务时间短的进程优先得到服务。
算法思想：追求最少的平均等待时间，平均周转时间和平均带权周转时间。
**1.非抢占式的短作业优先算法：**有服务时间更短的进程到达就绪队列时，要等待运行中的进程执行完，才调度这个服务时间更短的进程。
**2.抢占式的短作业优先算法:**又叫做，最短剩余时间优先算法，即就绪队列中，哪个进程剩余运行时间更短，哪个进程先被调度。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Rd4qC8vr-1686645858094)(C:\Users\25864\Desktop\111303716843053782.png)]
优点：平均等待时间，平均周转时间更短。
缺点：对短作业有利，对长作业不利，如果有与源源不断的短进程加入到就绪队列时，长进程会长时间得不到服务，会产生饥饿现象，如果一直得不到服务则服务被“饿死”。
先来先服务算法没有考虑作业的运行时间，如果先到的是一个服务时间很长的进程的话，对短进程很不利。
短作业优先算法没有考虑等待时间，如果有很多的短进程到达就绪队列时，长作业会等好久，对长作业很不利。
于是出现了一个同时考虑运行时间和等待时间的算法。
算法规则：在每次准备调度时，计算各个进程的响应比(响应比：等待时间+服务时间 /服务时间)
算法思想：总和考虑进程的等待时间和服务时间。
优缺点：总和考虑了等待时间和服务时间的问题。
等待时间相同时，服务时间短的优先（短作业优先的优点），
服务时间相同时，等待时间长的优先（先来先服务的优点），对于长作业来说随着等待时间越来长，响应比也回越来越大，避免了长作业饥饿的问题。
总结：这三种算法只根据公平，平均等待时间，平均周转时间等来评价系统的整体性能指标，不关心响应时间和任务的紧急程度，对于用户来说，交互性很差，所以这三种算法只适用于早期的批处理系统。
算法规则：按照各进程到达就绪队列的顺序，轮流让每个进程执行一个时间片，如果进程在一个时间片内没有执行完，则剥夺处理器，将进程重新放到就绪队列的尾部。
算法思想：公平地，轮流地为某个进程服务，让每一个进程在一定时间内都能得到响应。
算法规则：调度时选择优先级最高的进程或者作业。
算法思想：要根据任务的紧急程度来决定处理顺序。
算法规则：
1.设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。
2.新进程到达时，放入第一级队列，按照先来先服务原则排队等待被分配时间片，若时间片用完进程还未执行完，则放到下一级就绪队列尾部，如果已经实在最低级队列，则重新放到队列尾。
3.只有第k级队列为空时，才会为k+1对头的进程分配时间片。
算法思想：对其他算法的这种权衡。
系统中按进程类型设置多个队列
当有一个作业被调度进内存并创建进程后
将其插入某个队列
如上图
系统进程
交互式进程
需要得到即时反馈, 以提高用户体验
批处理进程
放低一些优先级体验影响不大, 大多是计算
以上是一个例子, 实际可能划分更多
队列之间可以采用固定优先级:
高优先级内没有进程时才能调度低优先级队列中的进程
缺点:
低优先级的可能无法及时响应
例如上述的打字软件, 当系统进程不断有进程时, 可能打字无法及时得到响应
给用户带来不好的体验
根据上面固定优先级的缺点, 队列之间可以采用时间片划分
例如给各个队列分配时间的50%, 40%, 10%
王道考研中讲的意思大概是高优先级给的为50%, 也就是高优先级更多
但应该和多级反馈队列算法中类似, 高优先级的在前, 且给的时间由少到多
因为如上述例子, 系统进程可能并不多, 如果分配过多的时间比例, 可能大多数时间都被浪费了
而需要大量时间进行处理的进程如视频渲染这些, 处理机工作的时间过少
队列之间采用一种调度方式
而各个队列再根据进程种类的不同, 采取不同的调度方式
例如
系统进程队列采用优先级调度
可以区分不同任务的优先级, 便于操作系统管理
交互式队列采用RR(时间片轮转)
确保各类交互式进程都可以在某个周期内得到服务
保证进程不会等太久, 避免用户糟糕的体验
批处理队列采用FCFS
**进程同步：**在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约关系。
**进程同步的概念：**把异步环境下的一组并发进程因直接制约而互相发送消息、进行互相合作、互相等待，使得各进程按一定的速度执行的过程称为进程间的同步。具有同步关系的一组并发进程称为合作进程，合作进程间互相发送的信号称为消息或事件。
进程间制约关系：
（1）资源共享关系：
互斥共享方式
同时共享方式
（2）相互合作关系
进程互斥：
1.进程互斥概念：
两个或两个以上的进程，不能同时进入关于同一组共享变量的临界区域，否则可能发生与时间有关的错误，这种现象被称作进程互斥· 也就是说，一个进程正在访问临界资源，另一个要访问该资源的进程必须等待。
临界资源：一个时间段内只允许一个进程使用的资源称为临界资源
2.临界资源的互斥访问的四个部分：
进入区
临界区
退出区
剩余区
3.为实现进程互斥，所有的同步机制应该遵循四大准则：
1.单标志法：
该算法可以实现“在同一时刻最多只允许一个进程访问临界区”
**缺点：**该算法先让P0进入访问区，再有P1进入，然后轮流访问。若P0一开始不进行访问，P1只能卡在就绪中，只能等P0访问结束后才能进行访问，若P0一直不访问，则P1只能一直等待（这时候CPU处于空闲阶段）。违背了“空闲让进”的原则。
2.双标志先检查法：
该算法先检查各进程的的选择意愿，再进行选择性进入。
**缺点：**可能两进程同时想进入临界区，违反了“忙则等待”的原则。
3.双标志后检查法：
**缺点：**违背了“空闲让进”和“有限等待”的原则。
4.Peterson算法：
**缺点：**未遵循“让权等待”的原则。但相比与前几种算法，是很好的。但依然不够完美。
小结：
中断屏蔽方法
利用 开/关中断 指令 实现。与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换。
**TestAndSet（TS指令 ）**TestAndSetLock指令（ TSL指令）
Swap指令（也叫 Exchange指令 / XCHG指令）
Swap指令 是用硬件实现的，执行的过程不允许被中断，只能一气呵成。
总结：
自旋锁是最比较简单的一种锁，一直自旋，利用 CPU 周期，直到锁可用。需要注意，在单核 CPU 上，需要抢占式的调度器（即通过时钟中断一个线程，运行其他线程）。否则，自旋锁在单 CPU 上无法使用，因为一个自旋的线程永远不会放弃 CPU。
自旋锁开销少，在多核系统下一般不会主动产生线程切换，适合异步、协程等在用户态切换请求的编程方式，但如果被锁住的代码执行时间过长，自旋的线程会长时间占用 CPU 资源，所以自旋的时间和被锁住的代码执行的时间是成「正比」的关系，我们需要清楚的知道这一点。
自旋锁与互斥锁使用层面比较相似，但实现层面上完全不同：当加锁失败时，互斥锁用「线程切换」来应对，自旋锁则用「忙等待」来应对。这里的忙等待，可以用「while」循环实现，但最好不要这么干！！CPU提供了「PAUSE」指令来实现忙等待。
自旋锁原理
自旋锁不就是不停的while循环去获取锁，还需要讲原理？等等，去获取锁状态的时候怎么保证数据原子性？难道又用互斥锁？如果真套一层互斥锁，那我就给自旋锁洗不了地了。显然在这里不能这么套娃！
反复尝试加锁的时候，包含两个步骤：
这个过程叫做「Compare And Swap」，简称「CAS」，它把上述两个步骤合并成一条硬件级指令，在「用户态」完成加锁和解锁操作，不会主动产生线程上下文切换，所以相比互斥锁来说，会快一些，开销也小一些。
上面说，不推荐while循环获取锁，Intel CPU提供的「PAUSE」指令，「PAUSE」指令是什么？那它如何解决无脑while循环占用CPU且低效率的问题呢？
其实自旋锁不会主动释放CPU，所以不可能解决占用CPU的问题，但能让这个过程更省电，抢占锁效率更高。
用户进程可以通过使用操作系统提供的一对原语【wait(S)和signal(S)】来对信号量进行操作，从而很方便实现了进程互斥、进程同步。
信号量其实就是一个变量（可以是一个整数，也可以是更复杂的记录型变量），可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为1的信号量
wait、signal原语简称P、V操作。
一、整型信号量
**存在问题：**不满足“让权等待”，会发生“忙等”。
二、记录型信号量
当资源分配完之后进程需要进入等待队列
进入等待队列的进程使用资源
P,V操作
用信号量机制实现进程互斥
由之前的学习我们知道**进程互斥就是在同一时间访问临界资源的进程只能有一个。并且P操作是申请资源并上锁的原语，V操作时释放资源并解锁的原语，**我们引用一个互斥信号量mutex表示进入临界区的名额，并设置初值为1来实现进程互斥。
1. 分析并发进程的关键活动，划定临界区（如：对临界资源打印机的访问就应放在临界区） 2. 设置互斥信号量 mutex，初值为 1 3. **在进入区 P(mutex)——申请资源** 4. **在退出区 V(mutex)——释放资源** 这里需要注意：P(mutex)与V(mutex)必须成对存在，如果缺少P那么互斥性就不可以保证，如果缺少V就导致资源不能解锁，并且等待进程永远不会被唤醒。
用信号量机制实现进程同步
进程同步就是将并发进程按照一定要求有序推进，以解决并发性带来的问题。
分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码）
设置同步信号量 S, 初始为 0
在**“前操作”之后**执行 V(S)
在**“后操作”之前**执行 P(S)
以下面的操作为例，解释一下这四个步骤的原因：
semaphore S = 0; //初始化同步信号量，初值为0
P1(){
操作1;
操作2;
V(S);//p1先执行导致s++
操作3;
}
P2(){
P(S);//p1先执行发现s=1发现有资源，开始执行
操作4;
操作5;
操作6;
}
以上的代码可以保证操作2发生在操作4之前。因为异步性导致的问题我理解就是**资源不足，因为第二步需要第一步所带的资源。**所以同步信号量设为了0而非1（1的话意思就是资源十分充足，谁想用访问就行）。因为操作2要发生在操作4之前就是说操作2要为操作4带来所需资源，所以解锁就是释放资源，一定要在前操作之后使用。
技巧口诀：前v后p
信号量机制实现前驱关系
**前驱关系就是一个同步问题，即某一操作必须在一个操作之后。**下图所示的前驱关系：S2必须在S1之后产生，S6必须在S4 S5 S3都完成之后进行。
实现步骤如下：
1. 要为每一对前驱关系各设置一个**同步信号量**
2. 在**“前操作”之后**对相应的同步信号量执行 V 操作
3. 在**“后操作”之前**对相应的同步信号量执行 P 操作
生产者-消费者问题-运行机制
系统中有一组生产者进程和一组消费者进程
生产者进程每次生产一个产品放入缓冲区
消费进程每次从缓冲区中取出一个产品并使用。（这里的“产品”理解为某种数据）
生产者、消费者共享一个初始为空、大小为n的缓冲区。 //刚开始空闲缓冲区的数量为n， 非空闲缓冲区（产品）的数量为0
只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。就是缓冲区没满->生产者生产 //同步关系。这是因为缓冲区满时，生产者要等待消费者取走产品
只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。 就是缓冲区没空->消费者消费 //同步关系。这是因为缓冲区空时，消费者需要等待生产者放入产品
缓冲区是临界资源，各进程必须互斥地访问 //互斥关系
生产者-消费者问题-P、V操作实现
PV操作题目分析步骤
关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
整理思路。根据各进程的操作流程确定P、V操作的大致顺序。
生产者每次要消耗（P）一个空闲缓冲区，并生产（V）一个产品。
消费者每次要消耗（P）一个产品， 并释放一个空闲缓冲区（V）。
//往缓冲区放入/取走产品需要互斥
设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。（互斥信号量初值一般为 1 ；同步信号量的初始值要看对应资源的初始值是多少）
实现关键
信号量机制可实现互斥、同步、对一类系统资源的申请和释放。
互斥 设置初值为1的互斥信号量
同步 设置初值为0的同步信号量（实现 “一前一后”）
为一类系统资源的申请和释放设置一个信号量，初始值即为资源的数量（本质上也属于“同步问题”，若无空闲资源，则申请资源的进程需要等待别的进程释放资源后才能继续往下执行）
伪代码实现
semaphore mutex = 1; //互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n; //同步信号量，表示空闲缓冲区的数量
semaphore full = 0; //同步信号量，表示产品的数量，也即非空缓冲区的数量
生产者-消费者问题-能否改变相邻P、V操作的顺序?
若此时缓冲区内已经放满产品
则 empty=0，full=n。
则生产者进程执行① 使mutex变为0，
再执行②，由于已没有空闲缓冲区，因此生产者被阻塞。
由于生产者阻塞，因此切换回消费者进程。
消费者进程执行③，由于mutex为0，即生产者还没释放对临界资源的“锁”，因此消费者也被阻塞。
=>这就造成了生产者等待消费者释放空闲缓冲区，而消费者又等待生产者释放临界区的情况，生产者和消费者循环等待被对方唤醒，出现“死锁”。
同样的，若缓冲区中没有产品
即full=0，empty=n。按③④① 的顺序执行就会发生死锁。
因此实现互斥的P操作一定要在实现同步的P操作之后。 V操作不会导致进程阻塞，因此两个V操作顺序可以交换。
多生产者-多消费者问题-描述
桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。如图。
如何用PV操作实现上述过程？
多生产者-多消费者问题-分析
就是画出结构图
分析步骤
关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
整理思路。根据各进程的操作流程确定P、V操作的大致顺序。
设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。（互斥信号量初值一般为 1，同步信号量的初始值要看对应资源的初始值是多少）
分析结果如下
互斥关系： 实现方式 在临界区前后分别PV
对缓冲区（盘子）的访问要互斥地进行
同步关系（一前一后）：实现方式 前V后P
父亲将苹果放入盘子后，女儿才能取苹果
母亲将橘子放入盘子后，儿子才能取橘子
只有盘子为空时，父亲或母亲才能放入水果 //“盘子为空”这个事件可以由儿子或女儿触发，事件发生后才允许父亲或母亲放水果
多生产者-多消费者问题-伪代码实现
初始化整型变量
semaphore mutex = 1; //实现互斥访问盘子（缓冲区）
semaphore apple = 0; //盘子中有几个苹果
semaphore orange = 0; //盘子中有几个橘子
semaphore plate = 1; //盘子中还可以放多少个水果
各进程执行逻辑
引出问题-可不可以不用互斥信号量？
代码模拟过程
刚开始，儿子、女儿进程即使上处理机运行也会被阻塞。如果刚开始是父亲进程先上处理机运行，则：
父亲 P(plate)，可以访问盘子->母亲 P(plate)，阻塞等待盘子->父亲放入苹果 V(apple)，女儿进程被唤醒，其他进程即使运行也都会阻塞，暂时不可能访问临界资源（盘子）->女儿 P(apple)，访问盘子，V(plate)，等待盘子的母亲进程被唤醒->母亲进程访问盘子（其他进程暂时都无法进入临界区）->……
结论：即使不设置专门的互斥变量mutex，也不会出现多个进程同时访问盘子的现象
这是因为本题中的缓冲区大小为1，在任何时刻，apple、orange、plate 三个同步信号量中最多只有一个是1。因此在任何时刻，最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区…
引出问题-当盘子容量为2能否继续实现？
代码模拟过程
父亲 P(plate)，可以访问盘子->母亲 P(plate)，可以访问盘子->父亲在往盘子里放苹果，同时母亲也可以往盘子里放橘子。于是就出现了两个进程同时访问缓冲区的情况，有可能导致两个进程写入缓冲区的数据相互覆盖的情况。
结论：如果缓冲区大小大于1，就必须专门设置一个互斥信号量 mutex 来保证互斥访问缓冲区。
需要注意的是，在生产者-消费者问题中，实现互斥的P操作一定要在实现同步的P操作之后，否则可能引起“死锁”。
知识回顾与重要考点
解决“多生产者-多消费者问题”的关键在于理清复杂的同步关系。
在分析同步问题（一前一后问题）的时候不能从单个进程行为的角度来分析，要把“一前一后”发生的事看做是两种“事件”的前后关系。
比如，如果从单个进程行为的角度来考虑的话，我们会有以下结论：
如果盘子里装有苹果，那么一定要女儿取走苹果后父亲或母亲才能再放入水果
如果盘子里装有橘子，那么一定要儿子取走橘子后父亲或母亲才能再放入水果
这么看是否就意味着要设置四个同步信号量分别实现这四个“一前一后”的关系了？
正确的分析方法应该 从“事件”的角度来考虑，我们可以把上述四对“进程行为的前后关系”抽象为一对“事件的前后关系”
盘子变空事件->放入水果事件
“盘子变空事件”既可由儿子引发，也可由女儿引发；
“放水果事件”既可能是父亲执行，也可能是母亲执行。这样的话，就可以用一个同步信号量解决问题了
上述两种分析方法结果如图
问题描述
假设一个系统有三个抽烟者和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料:烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。 供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料在桌上。轮流让三个抽烟者抽烟
semaphore offer1 = 0; // 桌上组合一的数量 纸+胶水
semaphore offer2 = 0; // 桌上组合二的数量 烟草+胶水
semaphore offer3 = 0; // 桌上组合三的数量 烟草+纸
semaphore finish = 0; // 抽烟是否完成
int i = 0; // 用于实现“轮流抽烟”
供应者代码：
provider(){
while(1){
if(i == 0){
将组合一放桌上;
V(offer1);
}else if(i == 1){
将组合二放桌上;
V(offer2);
}else if(i == 2){
将组合三放桌上;
V(offer3);
}
i = (i + 1) % 3;
P(finish);
}
}
吸烟者代码：
smoker1(){
while(1){
P(offer1);
从桌上拿走组合一;
V(finish);
}
}
smoker2(){
while(1){
P(offer2);
从桌上拿走组合二;
V(finish);
}
}
smoker3(){
while(1){
P(offer3);
从桌上拿走组合三;
V(finish);
}
}
写进程和读进程（或写进程）同时运行会产生错误。
因此要求：可以同时读、只能一个写、写完前不能有其他进程访问。
处理问题的方法在最后一段：
writer的P(rw)和V(rw)相当于写文件前后的上锁和解锁。
reader中的mutex是因为要互斥地访问count。
reader中的P(rw)和V(rw)相当于读文件的上锁和解锁：只有还有文件要读就不解锁。
因此写进程可能饥饿。
这种算法也被称为==读写公平法。==不会让写进程饥饿。
看这里知道为什么不会让写进程饥饿
此图来自上面的链接：
增加的P(w)和V(w)有交替唤醒的感觉。
总结
当所有哲学家都拿起左边的筷子，那么无法都拿起右边的筷子，会死锁。
三种解决方法：
3.仅当一个哲学家左右两只筷子都可用时才允许他抓起筷子。
互斥地拿筷子：
这种方法对应上面链接中的解决方法2.
总结
为什么要引入管程
信号量机制存在问题：编写程序困难、易出错。
管程的定义和基本特征
管程是一种特殊的软件模块，有：
基本特征：
static class Monitor{
private Item [] buffer = new Item[N];
private int count = 0;
public synchronized void insert(Item item){
if(count == N) this.wait();
buffer[count ++] = item;
if(count == 1) this.notify();//唤醒操作
}
public synchronized remove(){
if(count == 0) this.wait();
count --;
if(count == N - 1) this.notify();
return buffer[count];
}
}
ProducerConsumer pc = new ProducerConsumer();
//生产者进程
producer(){
while(1){
item = 生产一个产品;
pc.insert(item);
}
}
//消费者进程
consumer(){
while(1){
item = pc.remove();
消费产品item;
}
}
引入管程的目的无非就是要更方便地实现己丑年互斥和同步。
1、什么是死锁？
在并发的环境下，各进程在竞争资源的情况下造成的一种互相等待对方占有的资源，导致各个进程发生阻塞，无法向前推进的现象，就是死锁
2、死锁、饥饿、死循环的区别和共同点？
**共同点：**进程无法顺利的向前推进（除了故意设计死循环）
**区别：**死锁是竞争资源，导致进程阻塞，进程无法向前推进的现象。
饥饿：长期得不到想要的资源，导致进程无法向前推进的现象。例如短进程优先算法中，长进程可能一直得不到资源，所以会发生长进程“饥饿”。
**死循环：**进程一直跳不出某一个循环，导致进程处于死循环状态，不过这个死循环的设计也许是程序员故意的，嘿嘿。
3、死锁产生的四个必要条件？
关键：只要四个必要条件中有一个不成立，死锁就不会发生！
必要条件一：互斥条件：必须对互斥的资源进行竞争抢夺才会可能导致死锁现象的发生。
必要条件二：不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
必要条件三：请求和保持条件：对已经占有的资源不释放，又提出了新的资源请求，此时发生了进程阻塞，但是还不释放自己已经占有的资源。
必要条件四：循环等待条件：存在一条进程资源的循环等待链，链中的每一个进程已经获得的资源同时被下一个进程所请求。
4、什么时候会发生死锁？
总而言之一句话：对不可剥夺的资源的不合理分配，可能导致死锁。
具体可以有以下几种情况：
各个进程对不可剥夺的资源的竞争可能引起死锁；
请求和释放资源的顺序不当，也同样可能会导致死锁；
信号量的使用不当也可能造成死锁，例如在pv操作中，实现互斥的p操作在实现同步的p操作之前，可能会导致死锁。
5、死锁的处理策略？
**预防死锁：**破坏必要条件
**避免死锁：**防止系统进入不安全状态
**死锁的检测和解除：**对已发生的死锁进行检测并且采取措施进行解除。
预防死锁：
破坏互斥条件：例如采用SPOOLing技术将互斥的资源变为可以共享的资源。缺点：不是所有的互斥资源都允许改为共享使用，为了系统的安全，有些资源必须是互斥的。
**破坏不可剥夺条件：**方案一：当某个进程需要的资源被其他进程占有的时候，可以由操作系统吸住，将想要的资源强行剥夺；方案二：当某个进程请求某个资源得不到满足时，必须释放已经保持的所有资源，待以后需要时再进行申请。 缺点：实现复杂，频繁的申请和释放资源会增大系统的开销。
**破坏请求和保持条件：**使用静态分配方法，在进程在运行前将所需要的资源全部申请，在所需要的资源没有得到满足的情况下，不让其投入运行。 缺点：可能会导致某些进程饥饿。
**破坏循环等待条件：**采用顺序资源分配法，首先给资源编号，规定每个进程必须按编号递增的顺序请求资源。 缺点：资源的实际使用顺序可能和编号顺序不一样，会导致资源的浪费。
避免死锁： 采用银行家算法，使得系统处于安全状态，则一定不会发生死锁。银行加算法的核心思想：在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态，如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。
死锁的检测与解除：
**死锁的检测：**如果某时刻系统的资源分配图是不可完全简化的，则此时系统是存在死锁的。
**死锁的解除：**资源剥夺法：挂起某些死锁进程，并且抢占它们的资源，将这些资源分配给其他的死锁进程，但是要注意防止被挂起的进程因为长时间得不到资源而引起饥饿。
**撤销进程法：**强制撤销部分或者全部死锁进程。可能会使得即将结束的进程被撤销，而功亏一篑。
**进程回退法：**让一个或者多个死锁进程回退到可以避免死锁的地步，往往是通过系统记录进程的历史信息，设置还原点实现的。
内存管理章节知识框架
说明：
内存管理和进程管理是操作系统的核心内容，需要重点复习。本章围绕分页机制展开：通过分页管理方式在物理内存大小的基础上提高内存的利用率，再进一步引入请求分页管理方式，实现虚拟内存，使内存脱离物理大小的限制，从而提高处理器的利用率。
什么是内存？有什么作用？
字长（即机器字长）：
机器字长是指计算机进行一次整数运算（即定点整数运算）所能处理的二进制数据的位数，通常与CPU的寄存器位数、加法器有关。因此，机器字长一般等于内部寄存器的大小，字长越长，数的表示范围越大，计算精度越高。计算机字长通常选定为字节(8位）的整数倍。
补充知识：几个常用的数量单位
进程的运行指令-指令
逻辑地址 vs 物理地址
1.5 从写程序到程序运行
1.6 装入模块、装入内存
装入模块：组装成一个可执行文件。
装入内存：将可执行文件装入内存（这样就可以执行可执行文件了）。
1.7 装入的三种方式
1.7.1 绝对装入
绝对装入。在编译时，若知道程序将驻留在内存的某个位置，则编译程序将产生绝对地址的目标代码。绝对装入程序按照装入模块中的地址，将程序和数据装入内存。由于程序中的逻辑地址与实际内存地址完全相同，因此不需对程序和数据的地址进行修改。
适用环境：
绝对装入方式只适用于单道程序环境。另外，程序中所用的绝对地址，可在编译或汇编时给出，也可由程序员直接赋予。而通常情况下在程序中采用的是符号地址编译或汇编时再转换为绝对地址。
1.7.2 可重定位装入（静态重定位的）
可重定位装入。在多道程序环境下，多个目标模块的起始地址（简称始址）通常都从0开始，程序中的其他地址都是相对于始址的，此时应采用可重定位装入方式。根据内存的当前情况，将装入模块装入内存的适当位置。装入时对目标程序中指令和数据的修改过程称为重定位,地址变换通常是在装入时一次完成的,所以又称静态重定位,如图3.2(a)所示。
静态重定位的特点:
静态重定位的特点是，一个作业装入内存时，必须给它分配要求的全部内存空间，若没有足够的内存，则不能装入该作业。此外，作业一旦进入内存，整个运行期间就不能在内存中移动，也不能再申请内存空间。
1.7.3 动态运行时装入（动态重定位）：现在绝大部分计算机采用的方式
动态运行时装入，也称动态重定位。程序在内存中若发生移动，则需要采用动态的装入方式。装入程序把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址均为相对地址。这种方式需要一个重定位寄存器的支持，如图3.2(b)所示。
动态重定位的特点如下:
可以将程序分配到不连续的存储区中;在程序运行之前可以只装入它的部分代码即可投入运行，然后在程序运行期间，根据需要动态申请分配内存;便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间。
1.8 程序链接的三种方式
1.9 小结
覆盖技术：
**定义：**所谓覆盖，是指同一内存区可以被不同的程序段重复使用。
可以相互覆盖的程序段叫做覆盖。
可共享的内存区叫做覆盖区。
把程序执行时并不要求同时装入内存的覆盖组成一组，叫覆盖段，并分配同一个内存区
2.交换技术：
3.虚拟储存技术：
所谓虚拟存储，就是把内存与外存有机的结合起来使用，从而得到一个容量很大的“内存”，这就称之为虚拟存储。
虚拟储存技术的分类：
虚拟存储的发展尚无统一标准，从虚拟化存储的拓扑结构来讲主要有两种方式：即对称式与非对称式。对称式虚拟存储技术是指虚拟存储控制设备与存储软件系统、交换设备集成为一个整体，内嵌在网络数据传输路径中；非对称式虚拟存储技术是指虚拟存储控制设备独立于数据传输路径之外。从虚拟化存储的实现原理来讲也有两种方式；即数据块虚拟与虚拟文件系统。
拓扑结构：通过借用几何学中的点与线这两种最基本的图形元素描述，抽象地来讨论网络系统中各个端点相互连接的方法、形式与几何形状，可表示出网络服务器、工作站、网络设备的网络配置和相互之间的连接。它的结构主要有总线型结构、星型结构、环型结构、树型结构、网状结构。
（1）对称式虚拟存储
该方案具有以下主要特点：
（1）采用大容量高速缓存，显著提高数据传输速度。
（2）多端口并行技术，消除了I/O瓶颈。
（3）逻辑存储单元提供了高速的磁盘访问速度。
（4）成对的HSTD系统的容错性能。
（5）在SAN Appliance之上可方便的连接交换设备，实现超大规模Fabric结构的SAN。
（2）非对称式虚拟存储系统
这种方案具有如下特点：
（1）将不同物理硬盘阵列中的容量进行逻辑组合，实现虚拟的带区集，将多个阵列控制器端口绑定，在一定程度上提高了系统的可用带宽。
（2）在交换机端口数量足够的情况下，可在一个网络内安装两台虚拟存储设备，实现Strip信息和访问权限的冗余。
虚拟存储技术的实现方式：
（1）在服务器端的虚拟存储
（2）在存储子系统端的虚拟存储
（3）网络设备端实施虚拟存储
总结：
一、什么是连续分配管理
连续分配管理方式是内存空间分配与回收的一种管理方式，相较于非连续分配管理方式而言，连续分配要求为用户进程分配的必须是一个连续的内存空间。
连续分类管理方式有三种方式，包括：
单一连续分配
固定分区分配
动态分区分配
二、单一连续分配
在单一连续分配方式中，内存被分为两个部分：系统区和用户区。（如下图）
系统区通常位于内存的低地址部分，用户存放操作系统的相关数据。
用户区存放用户进程相关数据，用户区内只能有一道用户程序，用户程序独占用户区。
优点：
1.实现简单、无外部碎片；
2.可以采用覆盖技术扩充内存。
什么是覆盖技术？
覆盖技术是一种用于解决程序大小超过物理内存总和的问题。
即出现如下图的情况，如何让程序运行的一种方法
覆盖技术的思想：
将程序分成多个段，常用的段常驻内存，不常用的段只有在需要的时候调入内存，运行完毕之后既调出内存。
内存又被分为一个固定区和多个覆盖区。常用的段放在固定区中（只有当程序运行完后，才会调出内存）。不常用的段放在覆盖区中，只有在需要的时候调入覆盖区，用不到的时候既调出覆盖区。
举栗：该程序具有层次结构，B运行的时候，C不能运行。D运行的时候，E、F不能运行。E运行的时候，F、D不能运行。
当不采用覆盖技术存储时，总共需要8+8+10+12+4+10 = 52K内存。
当采用覆盖技术存储时，则可根据层次结构，划分出一个固定区和两个覆盖区（A、B）。固定区的内存大小为8K。覆盖区A的内存大小为10K（因为在同一时间段内，B和C只能有一个运行，所以取其大者）。同理覆盖区B的内存大小为12K。由此可见，当采用覆盖技术时，只需要30K的内存，便可以运行这个程序。
但是覆盖技术增加了程序员的编程难度，现在已经很少使用了
3.不一定需要内存保护。
什么是内存保护？
所谓内存保护即内存中的进程即不能修改操作系统的数据，也不能修改其他进程的数据。即各个进程只能访问自己的内存空间。
内存保护的两种方式：
<1. 上下限寄存器，访问地址之前需要与两个寄存器中的数据进行对比，处于二者之间方可访问。
<2.界地址寄存器+重定位寄存器。其中重定位寄存器中存储的是物理地址的起始位置，界地址寄存器存放的是逻辑地址的最大位置。
三、固定分区分配
为了在内存中装入多道程序，而且这些程序之间又不会相互干扰。于是将整个用户空间划分为若干个固定大小的分区。（这里的固定大小，指划分完后分区的大小不再改变。而不是内存大小都一样的分区）。每个分区中只能装入一道作业。
作业与进程的区别
1.作业是用户向计算机提交任务的任务实体。在用户向计算机提交作业作业后，系统将它放入外存中的作业等待队列中等待执行。而进程则是完成用户任务的执行实体，是向系统申请分配资源的基本单位。任一进程，只要它被创建，总有相应的部分存在于内存中。
2.一个作业可由多个进程组成，且必须至少由一个进程组成，反过来不成立。
3.作业的概念主要用在批处理系统中，像UNIX这样的分时系统中就没有作业的概念。而进程的概念则用在几乎所有的多道程序系统中。
固定分区分配有两种方式：1、分区大小相等 2、分区大小不等
**分区大小相等：**如下图，即将用户区分成内存大小一致的多个分区。每个分区只能放一道作业。
分区大小相等：缺乏灵活性，但适合于一台计算机控制多个相同对象的场合。
分区大小不等： 先统计大作业小作业一共有多少，然后根据比例进行划分。如下图
操作系统如何对各个分区进行管理？
建立分区说明表（分区大小、起始地址、状态），如图
优点：
实现简单、无外部碎片。
缺点：
1、当用户程序太大时，所有的分区都无法满足，这时候需要采用覆盖技术进行处理，但降低了性能
2、会产生内部碎片
四、动态分区分配
动态分区分配又被称为可变分区分配，这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区。并使分区的大小正好适合进程的需要。因此分区的大小和数目都是可变的。
动态分区分配的三个问题：
1、采用什么样的数据结构记录内存使用情况
2、当有多个分区满足进程的需求时，选择哪一个分区分配
3、分配与回收的处理。
下面我们一一探讨。
采用什么样的数据结构记录内存使用情况
两种常用的数据结构：空闲分区表、空闲分区链（如下图）
当有多个分区满足进程的需求时，选择哪一个分区分配
此处设计到了动态分区分配算法，常见的有四种：首次适应算法、最佳适应算法、最坏适应算法、邻近适应算法。这里仅简单的提一下。
首次适应算法：空闲分区链（或表），按照起始地址从小到大排序，分配内存时按照从前往后的顺序依次查找，找到合适的即分配。
最佳适应算法：空闲分区链（或表），按照容量从小到大排序，分配内存时按照从前往后的顺序依次查找，找到合适的即分配。
最坏适应算法：空闲分区链（或表），按照容量从大到小排序，分配的时候，只看第一个分区即可（因为最大）。
邻近适应算法：是在首次适应算法的基础上，进行的一些优化。即空闲分区链（或表），按照起始地址从小到大排序，每次分配内存时从上次查找结束的位置开始查找空闲分区链（或表），找到第一个合适的分区即分配。
分配与回收的处理
分配的时候，出现的两种情况
第一种，分区大小大于进程大小
对于这一种，只需要修改空闲分区表（或链）的起始地址和大小即可
第二种，分区大小等于进程大小
对于这一种，则需要在空闲分区链（或表）中删除该空闲分区。
回收的时候出现的四种情况（其实我觉得就两种）
一种是回收区的前面、后面、或者前面后面都有一个空闲分区，这时候需要进行空闲分区的合并
如图，收回4MB的分区，但是其后面有一个空闲分区，则需要进行合并
第二种就是和上面的相反，前后都没有空闲分区，那么直接在空闲分区表（或链）增加一个即可。
五、内部碎片和外部碎片
内部碎片：分配给某进程的内存区域中，有部分没被用上。
外部碎片：某些内存中的某些空闲分区由于太小而难以利用。
内部碎片是针对固定分区而言的，如果有一个分区是10MB，一个进程使用了8MB，那么剩下的2MB无法被使用，即产生了内部碎片。动态分区分配不会产生这个问题的原因是，分区的大小和数目都不是固定的，这个2MB也可以作为一个小分区继续使用。
外部碎片：则是针对动态分区而言的，即空闲分区内存的总和大于进程所需要的内存，但每一个空闲分区的内存都小于进程所需要的内存。
动态分区分配可以通过"紧凑"技术，处理外部碎片。
紧凑技术即把所有已分配进程全部往前提，放在一起。如图（针对上图的紧凑处理）
知识总览
**动态分区分配算法：**在动态分区分配方式中，当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配?
1、首次适应算法
**算法思想：**每次都从低地址开始查找，找到第一个能满足大小的空闲分区。
如何实现：空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
考点！！！
首次适应算法 是最有可能使得 高地址空间成为大的空闲区 的分配算法
2、最佳适应算法
算法思想：由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即，优先使用更尔的空闲区。
如何实现：
空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
**缺点：**每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块。因此这种方法会产生很多的外部碎片。
3、最坏适应算法
又称最大适应算法（Largest Fit)
算法思想：为了解决最佳适应算法的问题――即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。
如何实现：空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
**缺点：**每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达，就没有内存分区可用了。
4、邻近适应算法
算法思想：首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。
如何实现：空闲分区以地址递增的顺序排列（可排成一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链（或空闲分区表)，找到大小能满足要求的第一个空闲分区
首次适应算法，会导致低地址部分留下一些比较小的碎片，但是我们每一次开始检索，都需要从低地址部分的这些小碎片开始往后检索，所以这就会导致首次适应算法在查找的时候，可能会多花一些时间。不过这并不意味着邻近适应算法就比首次适应算法优秀很多。
知识回顾与重要考点
基本分页存储管理的思想——把内存分为一个个相等的小分区,再按照分区大小把进程拆分成一个个小部分
基本概念
将内存空间分为一个个大小相等的分区(比如:每个分区4KB),每个分区就是一个“页框” ,或称 “页帧”、“内存块”、“物理块”。每个页框有一个编号,即 “页框号” (或者“内存块号”、“页帧号”、“物理块号”)页框号从 0 开始。
将用户进程的地址空间也分为与页框大小相等的一个个区域,称为“页”或“页面”。每个页面也有一个编号,即页号。页号也是从0开始(注:进程的最后一个页面可能没有一个页框那么大。因此,页框不能太大,否则可能产生过大的内部碎片)
操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说,进程的页面与内存的页框有一一对应的关系。
各个页面不必连续存放,也不必按先后顺序来,可以放到不相邻的各个页框中。
如何实现地址转换
将进程地址空间分页之后,操作系统该如何实现逻辑地址到物理地址的转换?
如何计算：
**页号=**逻辑地址/页面长度(取除法的整数部分)
**页内偏移量=**逻辑地址%页面长度(取除法的余数部分)
页面在内存中的起始位置: 操作系统需要用某种数据结构记录进程各个页面的起始位置。
比如上面的例子中：
如果每个页面大小为2的K次方(B),用二进制数表示逻辑地址,则末尾K位即为页内偏移量,其余部分就是页号。
因此,如果让每个页面的大小为2的整数幂,计算机就可以很方便地得出一个逻辑地址对应的页号和页内偏移量。
**总结：**分页存储管理中,如何实现地址换?
1.要算出逻辑地址对应的页号
2.要知道该页对应页面在内存中的起始地址
3.要算逻辑地址在页面内的“偏移量”
4.物理地址=页面始址+页内偏移量
逻辑地址结构
分页存储管理的逻辑地址结构如下所示:
地址结构包含两个部分:前一部分为页号,后一部分为页内偏移量W。在上图所示的例子中,地址长度为32位,其中0-11位为“页内偏移量”,或称“页内址”;12~31位为“页号”。
页表
为了能知道进程的每个页面在内存中存放的位置,操作系统要为每个进程建立一张页表
为什么每个页表项的长度是相同的,页号是“隐含”的?
各页表项会按顺序连续地存放在内存中，如果该页表在内存中存放的起始地址为X,则M号页对应的页表项一定是存放在内存地址为X+3M
因此,页表中的“页号”可以是“隐含”的。
只需要知道页表存放的起始地址和页表项长度,即可找到各个页号对应
的页表项存放的位置
在本例中,一个页表项占3B,如果进程由n个页面,则该进程的页表总
共会占3n个字节
总结
概述
什么是基本地址变换机构？
基本地址变换机构，可以理解为将逻辑地址转变为物理地址的一组硬件机构，这些硬件需要做些什么事情，才能将逻辑地址转换为物理地址。
页表寄存器
基本地址变换机构，可以借助进程的页表将逻辑地址转换为物理地址。
通常情况下，会在系统中设置一个页表寄存器（PTR），存放页表在内存的起始地址F和页表长度M。
当进程还是未执行的时候，页表的起始地址和页表长度，放在进程控制块当中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。
ps：页面的大小是2的整数幂。
设页面大小为L，逻辑地址A到物理地址E的变换过程是怎么样的呢？
首先根据页号P和页内偏移量W（如果用十进制来计算，那么P=A/L，W=A%L，在实际计算机运行的过程当中，逻辑地址是固定不变的，那么就会让其计算的速度更快）。
比较页号P和页表长度M，若P>=M，则产生越界中断，否则继续执行。（页号是从0开始的，页表长度至少是1，因此P=M时也会发生越界）
页表中页号P对应的页表项地址=页表起始地址F+页号P*页表项长度，取出该页表项内容b，即为内存块号
计算物理地址E=b*L+W（可以看见，页面大小L是已知的，偏移量W是比较好计算的，只有页表项内容b是不好计算的，也是最容易出错的）
一、局部性原理
int i=0;
int a[100];
while(i<100)
{
a[i]=i;
i++;
}
对于上述程序，1号内存块存放程序对应的指令，10号内存块存放程序中定义的变量
因为有一个while循环，程序执行的时候，会频繁的访问1号，10号内存块
1.时间局部性
如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行;
如果某个数据被访问过，不久之后该数据很可能再次被访问。(因为程序中存在大量的循环)
2.空间局部性
一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。(因为很多数据在内存中都是连续存放的)
上小节介绍的基本地址变换机构中，每次要访问一个逻辑地址，都需要查询内存中的页表。由于局部性原理，可能连续很多次查到的都是同一个页表项。既然如此，能否利用这个特性减少访问页表的次数呢?
二、快表
TLB——Translation Lookaside Buffer
根据功能可以译为快表，直译可以翻译为旁路转换缓冲，也可以把它理解成页表缓冲。
快表，又称联想寄存器(TLB），是一种访问速度比内存快很多的高速缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程。与此对应，内存中的页表常称为慢表。
三、地址变换过程
因此，若快表未命中，则访问某个逻辑地址需要两次访存（注意:在找到页表项后，应同时将其存入快表,以便后面可能的再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换)
由于查询快表的速度比查询页表的速度快很多，因此只要快表命中，就可以节省很多时间因为局部性原理，一般来说快表的命中率可以达到90%以上。
命中快表——只需要一次访问内存（访问物理地址对应的内存）
没有命中快表——需要访问两次内存
第一次：访问存放在内存中的页表，找到页表项地址，取出对应的内存块号
第二次：由内存块号和页内偏移量，得出物理地址，然后访问物理地址对应的内存
例:某系统使用基本分页存储管理，并采用了具有快表的地址变换机构。访问一次快表耗时1us，访问一次内存耗时100us。若快表的命中率为90%，那么访问一个逻辑地址的平均耗时是多少?
(1+100)×0.9+(1+100+100)×0.1 = 111 us
有的系统支持快表和慢表同时查找，如果是这样，平均耗时应该是(1+100)×0.9+(100+100)×0.1=110.9 us
若未采用快表机制，则访问一个逻辑地址需要100+100 = 200us显然，引入快表机制后，访问一个逻辑地址的速度快多了。
四、总结
知识总览
单级页表存在的问题
**问题1：**页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框。
**问题2：**由程序的局部性原理，进程在一段时间内只需要访问某几个页面就可以正常运行了。因此没必要让整个页表都常驻内存。
如何解决单级页表的问题
两级页表的原理、地址结构
页面大小4KB=4x1024=212，即页内地址12位。
剩余的32-12=20位就是页号。
12位就是页内偏移的数量，20位就是有多少页。
进程最多有220个页面，如果都连续存放的话太大了。由于每个页面大小4KB，每个页表项4B，则每页可以放下1K=1024项，最左边的图就是把每页都分开放，就不需要连续的很大的内存了。
页目录表用来存每个二级页表的序号和它对应的块号：
二级页表像一个中间商
两级页表结构的逻辑地址结构：一级页号有10位，共1024个，对应0-1023（最左边的图），二级页号同理。
如何实现地址变化
到此，第一个问题：连续存放会占太多空间的问题已经解决了：
第二个问题的解决方法之后再说。
需要注意的细节
各级页表的大小不能超过一个页面：
但是，两级页表要3次访存，空间利用率高了，时间就慢了。
总结
知识总览
分段
按照程序自身的逻辑划分段，每段从0开始编址。
分配：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间不能相邻。
段号位数决定了每个进程最多可以分为几个段，段内地址位数决定了每个段的最大长度是多少。
举个例子，最大的段号是1023，说明最后一个段是1023——那么在它前面还有0-1022这1023个，所以一共有1024个段，也就是说，最大段号为1023说明共有1024个段，也就是进程最多被分为1024个段。
段内地址同理。
段表
通过段表可以找到某个逻辑段的存放位置。
每个段表项包括：段长，基址。各个段表项长度相同。
段号可以隐含，因为段表项长度相同，而且是按顺序存放的。
地址变换
一张没啥用的图：
逻辑地址转换为物理地址的流程：
分段、分页管理的对比
或许可以理解为（我猜的）：
页是信息的物理单位——因为实际上计算机内部就是这样存放信息的。
段是信息的逻辑单位——因为这样用户能更好理解信息并分配、运用信息，所以把它整成段。
分页——地址空间一维。
分段——地址空间二维。
分段更容易实现信息的共享和保护。
不能被修改的代码可以被共享。只需让各进程的段表项指向同一个段就相当于实现了共享。
关于分页不容易共享：页面不是按逻辑模块划分的，就很难共享。
更完整的对比：
总结
分页、分段的优缺点分析
段式管理产生外部碎片分析：
分段 + 分页 = 段页式管理
段表，页表
如何实现地址转换
小结
知识总览
以下是虚拟内存的基本概念
引入：传统存储管理方式的特征、缺点
局部性原理
简而言之，时间局部性原理——一个数据被访问，它很可能还被访问；
空间局部性原理——一个存储单元被访问，附近的存储单元也很可能被访问。
虚拟内存的定义和特征
简而言之，虚拟内存，让CPU以为所有程序都装入了，实际上只装入了快要用到的，剩下的等快要用到再装入。
CPU寻址范围大可以理解为：如果要用到某个程序但它还没装入，CPU寻址范围大就可以很快的找到他并把它装入——很快地弥补了。
所以虚拟内存的最大容量由计算机的CPU寻址范围确定。
虚拟内存有以下三个主要特征：
多次性：程序可以分多此进入内存。
对换性：程序可以换入换出。
虚拟性：内存容量大于实际容量（内存容量虚拟了一部分）。
如何实现虚拟内存技术
知识总览：
页表机制—请求页表与基本页表的区别：
页表中断机构：
地址变换机构
1.最佳置换算法—OPT
往后依次寻找发现7是短时间内使用不到的所以淘汰。
**缺点：**无法实现。因为程序无法提前预知之后的访问页面。
2.先进先出置换算法—FIFO
3.最近最久未使用置换算法—LRU
4.时钟置换算法—CLOCK
5.改进型时钟置换算法
驻留集
页面分配、置换策略
页面分配
置换策略
固定分配局部置换、可变分配局部置换、可变分配全局置换
何时调入页面
从何处调页
我们的外存分为两个区域：对换区和文件区
Unix的方式
抖动（颠簸）现象
工作集
访问方式：
open系统调用–打开文件
mmap系统调用–将文件映射到进程的虚拟地址空间
多个进程可以映射同一个文件，实现共享
在物理内存中，一个文件对应同一份数据，当一个进程修改文件数据时，另一个进程可以立马“看到”