操作系统之考研高频考点
概念：
1负责管理协调硬件，软件等计算机资源的工作
2为上级用户，应用程序提供简易的服务
3是一种系统软件
功能：1资源管理，包括进程管理，存储管理，文件管理，设备管理
2为上级提供服务，包括命令接口（联机命令，脱机命令），程序接口，GUI 用户图形图像界面
3对硬件机器扩展
并行：两个或者多个事件同一时刻同时发生
并发：两个事件或者多个事件同一时间内间隔发生，宏观上同时发生，微观上交替发生
资源共享（互斥共享方式和同时共享方式）
虚拟：空分复用技术（虚拟存储技术）？时分复用技术（虚拟处理器技术）？
操作系统的特征：并发，共享，虚拟，异步
操作系统的发展历程：
手工操作阶段，
批处理阶段（单道批处理系统，多道批处理系统），
分时操作系统，
实时操作系统，。
网络操作系统 ，分布式操作系统，个人计算机操作系统
运行机制：
两种指令（特权指令，非特权指令），
两种处理器状态（核心态，用户态），
两种程序（内核程序，应用程序）
内核
操作系统的内核概念：是操作系统底层软件，是最基本，最核心部分
内核包括：
1时钟管理，实现计时功能
2中断处理，负责中断机制
3原语是一种特殊的程序，执行具有原子性（设备驱动，CPU 切换），一气呵成，从始至终不能中断
4对系统资源进行管理，包括：进程管理，存储器管理，设备管理等功能，
体系结构：大内核和微内核
大内核：将操作系统的主要功能模块都作为系统内核，运行在核心态，优点是高性能，缺点是内核代码庞大，结构混乱，难维护
微内核：只保留最基本的功能，优点是内核功能少，结构清晰，方便维护，缺点是性能低，需要频繁的在核心态和用户态之间切换
中断机制
诞生：为了实现多道程序并发执行而引入的一种技术
本质：发生了中断就意味着需要操作系统介入，CPU 会立即进去核心态
用户态->核心态的切换是通过中断实现的，并且中断是唯一途径
中断分类：
内中断（也称为故障fault ，终止abort ，陷入trap）：
自愿中断——指令中断
强迫中断——硬件故障和软件中断
外中断：外设请求和人工干预
外中断处理过程：
每条指令结束后，CPU检查是否有外部中断信号，
若有外部中断信号，则需要保护被中断进程的CPU环境，
根据中断信号类型转入相应的中断处理程序，
恢复原来进程的CPU环境并退出中断，返回原进程继续往下执行
系统调用
用户接口包括：
命令接口（联机，脱机）——允许用户直接使用
程序接口——允许用户通过程序间接使用，由一组系统调用组成，比如.dll文件
概念作用：
应用程序通过系统调用请求操作系统的服务。系统中的各种共享资源都由操作系统统一掌管，因此，在用户程序中，凡是与资源有关的操作（如存储分配，IO操作，文件管理），都必须通过系统调用的方式向操作系统提出服务请求，由操作系统代为完成。
保证了系统的稳定性和安全性，防止用户进行非法操作。
按功能分类：
设备管理——完成设备的请求/释放/启动等功能
文件管理——完成文件的读/写/创建/删除等
进程控制——完成进程的创建/撤销/阻塞/唤醒等功能
进程通信——完成进程之间的消息传递/信号传递等功能
内存管理——完成内存的分配/回收等功能
1陷入指令（访管指令或trap 指令）是在用户态执行的，执行陷入指令之后立即引发一个内中断，从而CPU进入核心态
2发出系统调用请求是在用户态，而对系统调用的相应处理是在核心态下进行
3陷入指令是唯一一个只能在用户态执行，而不可在核心态执行的指令
进程
进程（进程实体）由程序段，数据段，PCB三部分组成。一般情况下，我们把进程实体就简称为进程，例如，所谓创建进程实质上就是创建进程实体中的PCB，而撤销进程，实质上是撤销进程实体中的PCB
区别：进程实体是静态的，进程是动态的
传统的典型定义：
1进程是程序的一次执行过程
2进程是一个程序及数据在处理机上顺序执行时所发生的活动
3进程是具有独立功能的程序在数据集合上运行的过程，是系统进行资源分配和调度的一个独立单位
PCB（Process Control Block ）：
进程描述信息——进程标识符PID和用户标识符UID
进程控制和管理信息——进程当前状态，优先级
资源分配清单——程序段指针，数据段指针，键盘，鼠标
处理机相关信息——各种寄存器的值
进程的组织方式：
链接方式——按照进程状态将PCB分为多个队列，操作系统持有指向各个队列的指针
索引方式——根据进程状态的不同，建立几张索引表，操作系统持有指向各个索引表的指针
进程的特征：
动态性——进程是程序的一次执行过程，是动态地产生，变化和消亡
并发行——内存中有多个进程实体，各进程可并发执行
独立性——进程是能独立运行，独立获得资源，独立接受调度的基本单位
异步性——各进程按各自独立的，不可预知的速度向前推进，操作系统提供“进程同步机制”来解决异步问题
结构性——每个进程都会配置一个PCB，结构上看，进程由程序段，数据段，PCB组成
进程的三种基本状态
运行态（Running ）——占有CPU，并在CPU上运行
就绪态（Ready）——已经具备运行条件，但由于没有空闲CPU，而暂时不能运行
阻塞态（Waiting /Blocked ）——因等待某一事件而暂时不能运行
创建态（New）——进程正在被创建，操作系统为进程分配资源，初始化PCB
终止态（Terminated ）——进程正在从系统中撤销，操作系统会回收进程拥有的资源，撤销PCB
进程状态的转换：
就绪态—>运行态：进程被调度
运行态—>就绪态：时间片到，或CPU被其他高优先级的进程抢占
运行态—>阻塞态：等待系统资源分配，或等待某事件发生（主动行为）
阻塞态—>就绪态：资源分配到位，等待的事件发生（被动行为）
进程控制——实现进程状态的转换
用原语实现进程控制。原语的特点是执行期间不允许中断，只能一气呵成。这种不可被中断的操作即原子操作。采用“关中断”和“开中断指令”实现，只允许在核心态下执行特权指令。
进程控制原语
1更新PCB中的信息（如修改进程状态的标志，将运行环境保存到PCB，从PCB恢复运行环境）
a所有的进程控制原语一定都会修改进程状态标志
b剥夺当前运行进程的CPU使用权必然需要保存其运行环境
c某进程开始运行前必然要恢复其运行环境
2将PCB 插入合适的队列
3分配或回收资源
进程通信
是指进程之间的信息交换
进程是分配系统资源的单位（包括内存地址空间），因此各进程拥有的内存地址空间相互独立
一般的，为了保证安全，一个进程不能直接访问另一个进程的地址空间
共享存储——两个进程对共享空间的访问必须是互斥的，操作系统只负责提供共享空间和同步互斥工具（如P ，V操作）
包括基于数据结构的共享，基于存储区的共享
管道通信——“管道”是指用于连接读写进程的一个共享文件，又名pipe 文件。其实就是在内存中开辟一个大小固定的缓冲区
1管道只能采用半双工通信，若要实现全双工通信，就需要设置两个管道
2各个进程要互斥地访问管道
3数据以字符流的形式写入管道，当管道写满时，写进程的write （）系统性调用将被阻塞，等待读进程将数据取走。当读进程将数据全部取走后，管道变空，此时读进程的read（）系统调用将被阻塞。
4如果没写满，就不允许读。如果没读空，就不允许写。
5数据一旦被读出，就从管道中被抛弃，这就意味着读进程最多只能有一个，否则就可能读错数据
消息传递：
直接通信方式——消息直接挂到接受进程的消息缓冲队列上
间接通信方式——也叫信箱通信方式
线程
传统的进程是程序执行流的最小单位
引入线程后，线程成为了程序执行流的最小单位
可以把线程理解为“轻量级的进程”
线程是一个基本的CPU执行单元，也是程序执行流的最小单位。引入线程后，不仅进程之间可以并发，进程内的各线程之间之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务
引入线程后，进程只作为除CPU之外的系统资源的分配单元
引入线程带来的变化：
1资源分配、调度——传统进程机制中，进程是资源分配，调度的单位
引入线程后，进程是资源分配的基本单位，线程是调度的基本单位
2并发性——传统进程机制中，只能进程间并发
引入线程后，各线程间也能并发，提升了并发度
3系统开销——传统的进程间并发，需要切换进程的运行环境，系统开销大
线程间并发，如果是同一进程内的线程切换，则不需要切换进程环境，系统开销小
引入线程后，并发所带来的系统开销小
线程属性：
1线程是处理机调度的单位
2多核CPU计算机中，各个线程可占用不同的CPU
3每个线程都有一个线程ID、线程控制块（TCB）
4线程也有就绪、阻塞、运行三种基本状态
5线程几乎不拥有系统资源
6同一进程的不同线程间共享进程的资源
7由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预
8同一进程中的线程切换，不会引起进程切换
9切换同进程内的线程，系统开销小
10切换进程，系统开销大
线程实现方式
用户级线程（User-Level Thread, ULT）——由应用程序通过线程库实现。所有的线程管理工作都有，应用程序负责（包括线程切换）
用户级线程中，线程切换可以在用户态下完成，无需操作系统干预
可以这样理解，“用户级线程”就是“从用户的视角能看到线程”
内核级线程（Kernel-Level Thread, KLT）—
由操作系统内核完成。线程调度、切换等工作都由内核负责，必须在内核态下完成
操作系统只“看得见”内核级线程，因此只有内核级线程才是处理机分配的单位
多线程模型
映射—>
多对一，多个用户级线程映射到一个内核级线程。每个用户进程只对应一个内核级线程
优点，用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高，多个线程不可以在多核处理机上并行运行
一对一，一个用户级线程映射到一个内核级线程。每个用户进程拥有与用户进程同数量的内核级线程
优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强，多线程可以在多核处理机上并发执行
缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理成本高，开销太
多对多：是集大成者
处理机调度
当有一堆任务要处理，由于资源有限，这些事情没法同时处理，这就需要确定某种规则来决定处理这些任务的顺序，这就是调度
在多道程序系统中，进程的数量往往多于处理机的个数，不可能同时并行处理各个进程。处理机调度，就是从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程的并发执行
调度的三个层次：
高级调度（作业调度）
中级调度（内存调度），就是决定将哪个处于挂起状态的进程重新载入内存
在引入了虚拟存储技术后，可将暂时不能运行的进程调至外存等待。等它重新具备了运行条件且内存又稍有空闲时，再重新载入内存。目的是为了提高内存利用率和系统吞吐量
暂时调到外存等待的进程状态称为挂起状态。PCB并不会一起调到外存，而是常驻内存。PCB中会记录进程数据在外存中的存放位置，进程状态等信息，操作系统通过内存中的PCB来保持对各个进程的监控，管理。挂起的进程PCB会被放到挂起队列中。
就绪态—>就绪挂起
阻塞态—>阻塞挂起
区别“挂起”和“阻塞”
这两种状态都是暂时不能获得CPU服务，但挂起状态是将进程映像调到外存，而阻塞态下的进程映像还在内存中。
低级调度（进程调度）——是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。进程调度的频率很高，一般几十毫秒一次。内存—>CPU
进程调度的时机和方式
进程调度就是按照某种算法从就绪队列中选择一个进程为其分配处理机
需要进行进程调度的情况：
1当前运行的进程主动放弃处理机
a进程正常终止
b运行过程中发生异常而终止
c进程主动请求阻塞（如等待IO）
2当前运行的进程被动放弃处理机
a分给进程的时机片用完
b有更紧急的事需要处理（如IO中断）
c有更高优先级的进程进入就绪队列
不能进行进程调度与切换的情况
1在处理中断的过程中。中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。
2进程在操作系统内核程序临界区中
3在原语中。原子操作不可中断，要一气呵成（如之前讲过的修改PCB中进程状态的标志，并把PCB放到相应队列）
进程在操作系统内核程序临界区中不能进行调度与切换✅
进程处于临界区时不能进行处理机调度❌
辨析：
临界资源：一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源
临界区：访问临界资源的那段代码。
内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列
进程调度的方式
非剥夺调度方式（非抢占式）——只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态
剥夺调度方式（抢占式）当一个进程正在处理机上执行时，如果有一个更重要的或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要更紧迫的那个进程
进程调度与进程切换
狭义的进程调度指的是从就绪队列中选一个要运行的进程（这个进程可以是刚被暂停执行的进程，也可以另一个进程，需要进行进程切换）
进程切换是指一个进程让出处理机，另一个进程占用处理机的过程
广义的进程调度包含了选择一个进程和进程切换两个步骤
进程切换的过程主要完成了：
1对原来运行进程各种数据的保存
2对新的进程各种数据的恢复（如：程序计数器、程序状态字、数据寄存器）
进程切换是有代价的，过于频繁的进行进程调度，切换，会使得整个系统的效率降低。因为系统的大部分时间都花在进程切换上，执行进程的时间减少。
调度算法的评价指标
CPU利用率
系统吞吐量
周转时间=完成时间−运行时间
a平均周转时间
b带权周转时间=周转时间/运行时间
c平均带权周转时间
等待时间=周转时间−运行时间
平均等待时间
响应时间
调度算法
先来先服务（FCFS，First Come First Serve ）
算法思想：主要从“公平”的角度考虑
算法规则：按照作业/进程到达的先后顺序进行服务
用于作业/进程调度：用于作业调度时，考虑的是哪个作业先到达后备队列；用于进程调度时，考虑的是哪个进程先到达就绪队列
是否可抢占：非抢占式算法
优点：公平，算法实现简单
缺点：排在长进程后的短进程需要等待很长的时间，带权周转时间很大，对短进程用户体验不好
是否导致饥饿：不会
短作业优先（SJF，Shortest Process First ）
算法思想：追求最少的平均等待时间，最少的平均周转时间，最少的平均带权周转时间
算法规则：最短的进程优先得到服务
用于作业/进程调度
是否可抢占：非抢占式算法，但是也有抢占式算法——最短剩余时间优先算法（SRTN Shortest Remaining Time Nest ）
优点：能得到最短的平均等待时间，平均周转时间
缺点：不公平，对短作业有利，对长作业不利，可能产生饥饿现象
高响应比优先（HRRN Highest Response Ratio Next ）
算法思想：综合考虑作业/进程的等待时间和要求服务的时间
算法规则：在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务
既可以用于作业调度，也可以用于进程调度
非抢占式算法，只有当前运行的作业/进程主动放弃处理机才需要调度
优点：等待时间相同的，要求服务时间短的优先（SJF的算法优点）
要求服务时间相同的，等待时间长的优先（FCFS的算法优点）
不会导致饥饿的问题
时间片轮转（RR Round Robin ）
算法思想：公平的，轮流的为各个进程服务，让每个进程在一定时间间隔内都可以得到响应
算法规则：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。
用于进程调度
抢占式算法。由时钟管理发出时钟中断来通知CPU
优点：公平，响应快，适用于分时操作系统
缺点：由于高频的进程切换，因此有一定开销，不区分任务的紧急程度
不会导致饥饿
如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大
优先级调度算法
算法思想：根据任务的紧急程度来决定处理顺序
算法规则：每个作业/进程都有各自的优先级，调度时选择优先级最高的
既可用于作业调度，也可用于进程调度，甚至还会用于IO调度中
抢占式和非抢占式都有。非抢占式只需要在进程主动放弃处理机时进行调度即可，而抢占式还需要在就绪队列变化时，检查是否会发生抢占。
优点：用优先级区分紧急程度，重要程度。适用于实时操作系统
缺点：如果源源不断地有高优先级进程到来，则可能导致饥饿
多级反馈队列调度算法
算法思想：折中权衡
算法规则：
1设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
2新进程到达时先进去，第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还没结束，则进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾
3只有第k级队列为空，才会为k+1级队头的进程分配时间片
用于进程调度
抢占式算法。在k级队列的进程运行过程中，若上级的队列中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列的队尾
优点：对各类型进程相对公平（FCFS的优点），每个新到达的进程都可以很快得到响应（RR的优点），短进程只用较少的时间就可以完成（SPF的优点），不必实现估计进程的运行时间（避免用户作假），可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、IO密集型进程
会导致饥饿
临界区是进程中访问临界资源的代码段
进入区和退出区是负责实现互斥的代码段
进程互斥遵循的原则：
1空闲让进。临界区空闲时，可以允许一个请求进入临界区的立即进入临界区
2忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待
3有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不饥饿）
4让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。
进程互斥的软件实现方法
单标志法
算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。
违背了空闲让进原则。
双标志先检查法
先检查后上锁🔒，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题
违反了忙则等待原则
双标志后检查法
先上锁后检查
虽然解决了忙则等待，但是又违背了空闲让进和有限等待原则，会因长期无法访问临界资源而产生饥饿现象
Peterson 算法
思想：在双标志后检查法中，两个进程都争着进入临界区，尝试主动让对方先使用临界区
进程互斥的硬件实现方法
中断屏蔽法
利用开/关中断指令实现
优点：简单，高效
缺点：不适用于多处理机，只适用于操作系统内核进程，不适用于用户进程（因为关中断指令只能运行在内核态）
TestAndSetLock 指令
是用硬件实现的，执行过程不允许被中断，只能一气呵成
优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞，适用于多处理机环境
缺点：不满足让权等待⌛️原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致忙等
Swap 指令（Exchange 指令，XCHG指令）
逻辑上同TSL
信号量机制
用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作从而很方便的实现进程互斥，进程同步
信号量其实是一个变量，可以用一个信号量表示系统中某种资源的数量
原语是一种特殊的程序段，其执行只能一气呵成，不可被中断，原语是由关中断开中断指令实现
一对原语：wait（S）和signal （S）常简称为P 、V操作（来自荷兰语🇳🇱proberen 测试、检测，verhogen 增加）申请操作，释放操作
信号量机制实现进程同步
设置同步信号量S，初始为0
在前操作之后执行V（S）
在后操作之前执行P（S）
信号量机制实现前驱关系
互斥mute
实现互斥操作要在实现同步操作之后，不然会发生死锁🔒
管程
管程是一种特殊的软件模块，有这些部分组成：
1局部于管程的共享数据结构说明
2对该数据结构进行操作的一组过程
3对局部于管程的共享数据设置初始值的语句
4管程有一个名字
管程的基本特征：
1局部于管程的数据只能被局部于管程的过程所访问
2一个进程只有通过调用管程内的过程才能进入管程访问共享数据
3每次仅允许一个进程在管程内执行某个内部过程
引入管程的目的无非就是要更方便地实现进程互斥和同步
1需要在管程中定义共享数据
2需要在管程中定义用于访问这些共享数据的入口
3只有通过这些特定的入口才能访问共享数据
4管程中有很多入口，但是每次只能开放其中一个入口，并且只能让一个进程或线程进入（比如说，在生产者消费者问题中，各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证一个时间段内最多只会有一个进程在访问缓冲区。这种互斥性是由编译器负责实现）
5可以在管程中设置条件变量以及等待⌛️/唤醒操作来解决同步问题，可以让一个进程或者线程在条件变量上等待，可以通过唤醒操作将等待在条件变量上的进程或线程唤醒
Java中类似于管程的机制
用关键字synchronized 来描述一个函数，那么这个函数同一时间段内只能被一个线程调用
死锁
死锁：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象
饥饿：由于长期得不到想要的资源，某进程无法向前推进
死循环：某进程执行过程中一直跳不出某个循环的现象。
区别：
死锁一定是循环等待对方手里的资源导致的，因此如果有死锁现象，那至少有两个或者两个以前的进程同时发生死锁。发生死锁的进程一定处于阻塞态
饥饿可能只有一个进程发生饥饿。发生饥饿的进程既可能是阻塞态（长期得不到IO设备），也可能是就绪态（长期得不到处理机）
死循环可以上处理机运行，只不过无法顺利推进。死锁和饥饿是由于操作系统分配资源的策略不合理导致的，而死循环是由代码逻辑的错误导致的
死锁产生的必要条件
1互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁
2不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动放弃。
3请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己的资源保持不放。
4循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。
注意⚠️发生死锁时一定有循环等待，但是发生循环等待时未必死锁
死锁的处理策略
预防死锁：破坏死锁产生的四个必要条件
避免死锁：避免系统进入不安全状态（银行家算法）
死锁的检测和解除：允许死锁发生，系统负责检测出死锁并解除
