操作系统笔记
最近马上要期末考试了，操作系统这门课很重要，我个人学的不认真，不太好，
但总归学了一点点，记录一下，防止老年痴呆。。。
所有截图全部来自B站王道考研
操作系统概述
操作系统的定义
管理系统资源，控制程序执行，改善人机界面，提供各种服务，并合理组织计算机工作流程
和为用户方便有效地使用计算机提供良好运行环境的一种系统软件操作系统的特征
并发性，共享性，异步性
并发性是指两个或两个以上的活动或事件在同一时间间隔内发生。
并行性是指两个或两个以上的活动或事件在同一时刻发生。
并行活动一定是并发的，并发活动不一定是并行的，
并行性是并发性的特例，而并发性是并行性的扩展操作系统的资源管理技术
复用，虚拟，抽象
复用又可分为：空分复用，时分复用
空分复用，指的是空间上，各进程共享存储空间，例如内存和外存
时分复用，指的是时间上，各进程按时间片使用资源，例如CPU复用和虚拟的主要目标是解决物理资源不足的问题，抽象则用于处理系统复杂性
重点解决资源易用性，资源抽象软件对内封装实现细节，对外提供应用接口
多道程序设计的CPU利用率计算公式
CPU利用率=1-p^n
p是程序平均等待IO操作的时间占其运行时间的比例为p(若80%的时间用于等待IO操作，则p=0.8)
n是多道程序设计的道数（CPU利用率与道数及程序等待IO时间之间的关系）CPU利用率=CPU有效时间/CPU总的运行时间
CPU总的运行时间=CPU有效时间+CPU空闲等待时间
多道程序设计的优缺点
优点：提高CPU，内存和设备的利用率，提高系统的吞吐率，
使单位时间内完成的作业数量增加，充分发挥系统的并行性，使设备与设备之间
CPU与设备之间均可并行工作缺点：延长了作业的周转时间
系统调用的定义及作用
- 系统调用是操作系统提供给用户的特殊接口，应用程序只有通过系统调用才能
请求系统服务并使用系统资源 - 系统调用的作用
- 内核可以基于权限和规则对资源访问进行裁决，保证系统的安全性
- 系统调用对资源进行抽象，提供一致性接口，避免用户在使用资源时发生错误
且使编程效率大大提高
- 系统调用由访管指令实现，当CPU执行程序中编写的由访管指令实现的系统调用时会
产生异常信号，通过陷阱机制，处理器状态由用户态变为内核态，进入操作系统并
执行相应的服务例程，以获得操作系统服务，当系统调用执行完毕时，处理器再次
切换状态，控制返回至发出系统调用的程序，系统调用是应用程序获得操作系统服务的
唯一途径
- 系统调用是操作系统提供给用户的特殊接口，应用程序只有通过系统调用才能
处理器管理
特权指令和非特权指令
特权指令是指仅在内核态下才能使用的指令
非特权指令在目态和管态下都能工作，操作系统程序能够执行全部机器指令，
应用程序只能使用非特权指令。处理器状态及其转换
- 处理器的状态指的是，根据执行程序对资源和机器指令的使用权限将处理器
设置成不同状态，至少需划分为两种状态，内核态(管态)和用户态(目态) - 处理器由用户态向内核态转换
- 程序请求操作系统服务，执行系统调用
- 程序运行时产生中断事件(如IO操作完成)，运行程序被中断，转向中断处理程序处理
- 程序在运行时产生异常事件(如发生程序性中断或目态执行特权指令)，运行程序被打断
转向异常处理程序工作
- 处理器由内核态到用户态
计算机通常提供一条称作加载程序状态字的特权指令（Intel x86为iret指令）
用来实现从内核态返回用户态，操作系统将控制权转交给应用程序
- 处理器的状态指的是，根据执行程序对资源和机器指令的使用权限将处理器
程序状态字的定义和作用
- 定义：程序运行时，其状态不断动态地变化，如当前处于目态还是管态，下一条要执行的
指令位置是什么等等。操作系统将程序运行时的一组动态信息汇聚在一起，称为程序状态字
并存放在处理器的一组特殊寄存器里，以方便系统的控制和管理 - 作用：主要作用是实现程序状态的保护和恢复。
- 定义：程序运行时，其状态不断动态地变化，如当前处于目态还是管态，下一条要执行的
进程状态和转换
- 进程状态有不同的模型
- 三态模型
就绪态：进程具备运行条件，等待系统分配处理器以便运行的状态
等待态：又称阻塞态，睡眠态，指进程不具备运行条件，正在等待某个事件完成的状态
运行态：进程占有处理器正在运行的状态 - 五态模型
新建态：新建态对应于进程被创建时的状态，尚未进入就绪队列
终止态：指进程完成任务到达正常结束点，或出现无法克服的错误而异常终止
或被操作系统及有终止权的进程所终止时所处的状态 - 七态模型
挂起指的是内存资源已经不能满足进程运行的要求时，必须把某些进程挂起，
对换到磁盘对换区中，释放它所占有的某些资源，暂时不参与低级调度。
挂起分为：挂起等待态，挂起就绪态
- 三态模型
- 进程状态有不同的模型
进程控制块PCB的定义
每个进程有且仅有一个进程控制块，或称进程描述符，它是进程存在的唯一表示，
是操作系统用来记录和刻画进程状态及环境信息的数据结构，是进程动态特征的汇集
也是操作系统掌握进程的唯一资料结构和管理进程的主要依据。进程控制块包括进程执行时的情况，以及进程让出处理器之后所处的状态，断点等信息。
处理器调用层次
- 处理器调度按照层次可分为三级，高级调度(作业调度)，中级调度和低级调度(进程调度)
用户作业从进入系统成为后备作业开始，直到运行结束退出系统为止，均需经历不同
级别的调度 - 高级调度，按照预定的调度策略挑选若干作业进入内存，即高级调度控制多道程序设计
的道数。 - 中级调度，根据内存资源情况决定内存中所能容纳的进程数目，并完成外存和内存中
的进程对换工作 - 低级调度，根据某种原则决定就绪队列中哪个进程/线程获得处理器，并将处理器出让给
它使用，低级调度是操作系统最为核心的部分，执行十分频繁，其调度策略的优劣将
直接影响系统性能，因为这部分代码要求精心设计并常驻内存。
- 处理器调度按照层次可分为三级，高级调度(作业调度)，中级调度和低级调度(进程调度)
选择调度算法原则
- 资源利用率
CPU利用率=CPU有效时间/CPU总的运行时间
CPU总的运行时间=CPU有效时间+CPU空闲等待时间 - 吞吐率
单位时间内CPU处理作业的个数 - 周转时间
用户从向系统提交作业开始到作业完成为止的时间间隔
周转时间=作业完成时间-作业到达时间 - 带权周转时间
带权周转时间=周转时间/进程所需CPU时间
- 资源利用率
作业调度和低级调度算法
- 先来先服务算法，FCFS，非剥夺式调度算法
不利于短作业而优待了长作业，不利于IO繁忙型作业而有利于CPU繁忙型作业
作业调度和进程调度都适合 - 最短作业优先算法，SJF，非剥夺式调度算法
会导致饥饿现象，长作业长时间得不到服务
作业调度和进程调度都适合 - 最短剩余时间优先算法，SRTF，剥夺式调度算法
只适用于进程调度 - 最高响应比优先算法，HRRF，非剥夺式调度算法
响应比=1+作业等待时间/作业处理时间
作业调度和进程调度都适合 - 优先级调度算法
进程/线程优先级的确定可采用静态和动态两种方式
静态优先级指的是进程在运行过程中优先级不改变，会出现饥饿现象
动态优先级指的是进程在运行过程中随占有CPU时间增加，逐渐降低其优先级
随进程等待时间增加，逐渐提高其优先级。不会出现饥饿现象 - 轮转调度算法(时间片调度)，RR，剥夺式调度算法
- 多级反馈队列调度算法，MLFQ
- 先来先服务算法，FCFS，非剥夺式调度算法
同步，通信与死锁
Bernstein条件，并发进程的无关性
无关的并发进程：一个进程不会改变另一个与其并发执行的进程的变量
交互的并发进程：一个进程的执行可能会影响其他进程的执行结果Bernstein条件就是判断两个并发进程的无关性的，若满足条件，结果为空集，则
两个并发进程无关
（R(P1)∩W(P2)）∪（R(P2)∩W(P1)）∪（W(P1)∩W(P2)）=∅与时间有关的错误
如果对两个交互的并发进程不加以控制，则会产生与时间相关的错误：
结果不唯一，永远等待进程的交互：竞争与协作
在多道程序设计系统中，并发进程存在两种基本关系：竞争和协作
竞争关系
竞争关系又称互斥关系，资源竞争会引发两个控制问题，死锁和饥饿
进程互斥是指若干进程因相互争夺独占型资源而产生的竞争制约关系协作关系
进程同步是指为完成共同任务的并发进程基于某个条件来协调其活动
因为需要在某些位置上排定执行的先后次序而等待，传递信号或消息
所产生的协作制约关系
临界区管理
并发进程中与共享变量有关的程序段称为临界区
共享变量所代表的资源称为临界资源，即一次仅能供一个进程使用的资源临界区的调度原则：互斥使用，有空让进，忙则等待，有限等待
信号量与PV操作
在操作系统中用信号量表示物理资源的实体
PV操作则是一组原语操作，此操作不可分割，若完成则都完成，若失败则都失败
PV操作的不可分割性确保执行时的原子性及信号量值的完整性信号量按其取值可分为两种：
- 二值信号量，仅允许取值为0或1，主要解决进程互斥问题
- 一般信号量，又称计数信号量，允许取大于1的整型值，主要解决进程同步问题
死锁
死锁的定义
如果一个进程集合中的每个进程都在等待只能由此集合中的其他进程才能引发的
事件，而无期限陷入僵持的局面称为死锁死锁的解决方法
死锁的防止
死锁产生的条件 1. 互斥条件：临界资源是独占资源，进程应互斥且排他地使用这些资源 2. 占有和等待条件：进程在请求资源得不到满足而等待时，不释放 已占有的其他资源 3. 不剥夺条件：又称不可抢占，已获资源只能由进程自愿释放， 不允许被其他进程剥夺 4. 循环等待条件：又称环路条件，存在循环等待链，其中，每个进程 都在等待链中等待下一个进程所持有的资源，造成这组进程处于 永远等待状态。 死锁防止的策略： 1. 破坏互斥条件，使得资源可同时访问而非互斥使用，但很多资源由于其 特殊性质决定只能互斥地占有，所以这种做法不可行。 2. 破坏占有和等待条件：静态分配是指进程必须在执行之前就申请需要的 全部资源，且直到所要的资源都得到满足后才开始执行，采用这种策略 会严重地降低资源的利用率 3. 破坏不剥夺条件：剥夺调度能够防止死锁，但只适用于内存和处理器资源 4. 破坏循环等待条件：采用层次分配策略，将系统中所有的资源排列到不同 层次中。 一个进程得到某层的一个资源后，只能再申请较高层的资源， 当进程释放某层的一个资源时，必须先释放所占有的较高层资源， 当进程获得某层的一个资源后，如果想申请同层的另一个资源，必须先 释放此层中的已占有资源。
死锁的避免
<img src="{%imgPrefix%}/blog/os/system.jpg"/>- 死锁的检测与恢复
死锁的检测和恢复往往配套使用，当死锁被检测到后，采用各种方法解除系统
死锁以恢复到可运行状态的常用方法有资源剥夺法，进程回退法，进程撤销法
和系统重启法。
- 死锁的检测与恢复
存储管理
地址转换
程序员编写的代码称为源程序，源程序要被执行需要经过，编译，链接，装入三个过程
- 编译，指的是把将源程序编译为计算机可执行的目标程序
- 链接，指的是将由多个目标程序转换成一个整体的可重定位代码，此时该程序处在
逻辑地址空间。 - 装入，指的是把逻辑地址空间中的进程调用到内存中执行，在装入的时候，涉及到
- 地址转换的问题，也就是将抽象地址，转换成进程在内存中的实际地址，物理地址。
地址转换又称地址重定位，分为三种方式，静态重定位，动态重定位，运行时链接地址重定位
连续存储管理
固定分区存储管理
固定分区存储管理又称静态分区模式，就是将内存分为固定数目的小内存块，每个内存块
只装入一个作业，固定分区会出现内部碎片。可变分区存储管理
可变分区存储管理又称动态分区模式，按照作业的大小分配内存，可变分区会产生外部碎片
通过对内存空闲区的管理及分配，则有几种常见的可变分区分配算法：
内存不足的存储管理技术(内存空间的扩充)
- 覆盖技术：程序执行过程中程序的不同模块在内存中相互替代，以达到
小内存执行大程序的目的。 - 移动技术：将内存中空闲区进行合并为一个大的空闲区
- 交换技术：将内存中阻塞态的进程对换到外存中的对换区中，以解决内存容量不足的问题
- 覆盖技术：程序执行过程中程序的不同模块在内存中相互替代，以达到
非连续存储管理
基本分页存储管理
分页的基本概念
页面：进程逻辑地址空间分成大小相等的区，每个区称为页面或页，页号从0开始编号 页框：把内存物理地址空间分成大小相等的区，其大小与页面大小相等， 每一个区是一个页框，块号从0开始编号 逻辑地址：分页存储器的逻辑地址由页号和页内偏移量组成，前者表示地址所在 页面的编号，后者表示页内位移，页号的位数决定页面的个数，页内偏移量决定页面的大小。 如果有K位表示页内偏移量，则说明该系统中一个页面的大小是2^k个内存单元 如果有M位表示页号，则说明在该系统中，一个进程最多允许有2^m个页面 页表：为了能知道进程的每一个页面在内存中存放的位置，操作系统要为每一个 进程建立一张页表，进程的每一页对应一个页表项，每个页表项由页号和块号组成 页表记录进程页面和实际存放的内存块之间的对应关系。页表存储在内存中。 页表项：页表项由页号和块号组成，每个页表项的大小是相等的，所以页表项的 页号是不占存储空间的，只要知道要访问的页号，则该页表项的地址为： 页表首地址+页号*页表项长度(大小)，而页表项的块号是占存储空间的，块号所占空间 大小等于页表项长度，不知道怎么描述，举个例子：如果某个系统内存为4GB，页面大小 为4KB，则一个页表项长度：2^32/2^12=2^20个内存块，2^20个内存块可用20位二进制 数表示，一个字节可表示8位二进制数，则需要3字节可表示2^20个内存块，所以该系统 中一个页表项占3个字节。分页存储管理中逻辑地址转物理地址
局部性原理引出的快表机制
- 局部性原理分为空间局部性，时间局部性，
时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很可能再次
执行，如果某个数据被访问过，不久之后该数据很可能再次被访问，其原理是
(程序中存在大量的循环)
空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元
也很可能被访问(因为很多数据在内存中都是连续存放的) - 通过设置一个比内存更快的寄存器，将被访问过的页表项集合也就是快表，存放
在寄存器中，就能提高访问物理地址速度，如果快表命中，则只需要一次访存。
- 局部性原理分为空间局部性，时间局部性，
二级页表
- 单级页表的缺点是，页表是存放在内存中的，如果页表过长，则需要分配
很多个连续的页框给该页表存放，所以二级页表产生了。 - 二级页表就是将原来的单个页表分成两个页表，页目录表和二级页表
页目录表的块号指向二级页表首地址，二级页表的块号指向实际物理块号首地址
- 单级页表的缺点是，页表是存放在内存中的，如果页表过长，则需要分配
基本分段存储管理
- 分段式存储管理与分页式存储管理的区别不止在于页面大小，段长，
分段式按照程序的模块分段，从而实现信息之间的共享。 - 段号的位数决定了每个进程最多可以分为几个段
段内地址位数决定了每个段的最大长度是多少 - 分段式的地址转换
- 分段式存储管理与分页式存储管理的区别不止在于页面大小，段长，
基本段页式存储管理
段式存储和页式存储的优缺点
段页式管理的逻辑地址结构
段页式的地址转换
虚拟内存的实现
- 虚拟内存的定义和特征
- 如何实现虚拟内存技术
请求分页存储管理
- 请求分页存储管理的页表机制
- 缺页中断机构
- 请求分页和基本分页存储的主要区别
- 请求分页的地址转换
- 页面置换算法
概念：在程序执行的过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序，若内存空间不够，由操作系统负责将内存
中暂时用不到的信息换出到外存，页面置换算法就是决定应该换出哪个页面。算法优劣标准
使用缺页率来衡量页面置换算法的优劣，缺页率等于缺页中断次数/页面访问的总次数
注意：缺页会发生中断，但未必发生页面置换，若还有可用的空闲内存块， 就不用进行页面置换。
磁盘管理
