OS开学考前临时抱佛jio（2）

背景
复习inging。。。

操作系统概述：

程序并发性：多个程序在宏观上同时向前推进
资源共享性：os和多个用户程序公用系统中的各种资源
异步性：在os之上，宏观上同时运行的多个程序交替执行
虚拟性：利用某种技术将一个物理实体变为若干个逻辑实体

定时装置：
绝对时钟：记载实际时间，不中断
间隔时钟：定时发生中断，是实现多道程序的基础——保证os获得控制权

系统栈：
作用：1.保存中断现场 2.保存os子程序转移返回点、参数、局部变量、返回值
位置：内存中os空间的一个固定区域

特权指令和非特权指令：
特权指令：只有在管态才能执行的指令（os运行时所处的状态）
非特权指令：在管态和目态都可以执行的指令，只与程序本身有关，不影响系统状态（目态：一般用户程序运行的状态）

cpu状态和切换：
cpu状态：系统态（管态、核心态）、用户态（目态，常态）
状态转换：管->目（置程序状态字PSW），目->管（中断，trap）

地址映射机构：
逻辑地址（虚）：程序中产生的地址
物理地址（实）：存储器地址

存储保护设施：
防止应用程序：1.侵犯os空间 2.侵犯其他用户空间
地址检查： 1.越界检查 2.越权检查（对共享区域）

中断装备：
发现并响应中断的硬件机构

操作系统的运行原理：
程序1，中断，进入os，保存程序1现场，去到程序2，恢复程序2现场，置psw，进入程序2

2.进程五状态：创建、就绪、运行、终止、等待

进程控制块（PCB)：
定义：标志进程存在的数据结构，包括系统对进程进行管理所需要的全部信息
内容：进程标识（pid），状态，现场信息，调度参数，所属用户（uid）等

进程队列：
就绪队列：系统一个或若干个（调度算法确定）
等待队列：每一个等待事件一个
运行队列：每一个处理机一个

进程的类型和特性：
系统进程：运行os程序，完成系统管理（服务）功能
用户进程：运行用户程序，为用户服务
并发性：可以与其他进程一道向前推进
动态性：动态产生、消亡、生存期内状态动态变化
独立性：一个进程是可以调度的基本单位
交互性：同时运行的进程可能相互作用
异步性：进程以各自独立，不可预知的速度向前推进
结构性：每一个进程都有一个PCB

线程：进程内一个相对独立的执行流
TCB：标志线程存在的数据结构，其中包含对Thread管理需要的全部信息
内容：线程标识、状态、调度参数、现场
存放位置：
用户级线程：目态
核心级线程：管态

线程的实现：
用户级别线程：
实现方法：1.基于library函数，系统不可见
2.线程的create，delete，yield在目态完成
3.TCB在目态，每个线程一个系统栈
优点：1.不依赖os，灵活
2.切换速度块
缺点：同一个进程中多个线程不能真正并行，一个线程进入os受阻，同一个进程的其他线程不能执行
核心级别线程：
实现方法：1.基于系统调用
2.用户栈+系统栈完成，系统栈记录用户栈位置，pc+ip
3.os完成线程操作
优点：1.同一个进程内多线程可并行
2.一个线程进入核心等待，其他线程仍可以执行
缺点：1.系统开销大，同一进程内多线程切换速度慢
2.调度算法不能灵活控制
混合级别线程

中断与处理器调度

处理器调度算法衡量指标：平均周转事件

常用算法：

1.先到先服务算法（FCFS）：按进入就绪态的次序来调度

优点：公平，不会出现饿死
缺点：短进程（线程）等待事件长，从而平均等待时间长

2.最短作业优先（SJF)：按照CPU阵发事件递增的次序调度，易于证明其平均周转事件最短

优点：最大限度降低了平均等待时间
缺点：不公平，容易产生饥饿和饿死

3.最短剩余时间优先算法（SRTN)：剥夺式算法

当CPU空闲时，选择剩余时间最短的进程或线程。当一个新进程或线程到达时，比较新进程所需时间与当前运行进程估计剩余时间，若新进程更短，则切换。

4.最高响应比优先算法（HRN）：

1.FCFS，很好理解，先来后到的顺序，一个做完下一个，周转时间=等待+运行时间
2.RR，每个p轮2秒，直至运行完，周转时间很长哦，不过公平
3.优先级调度，剥夺式算法，来了优先级更高的马上剥夺，直至运行完

互斥、同步与通信

与时间有关的错误：进程执行交叉、涉及公共变量

公共变量：多个进程都需要访问的变量

临界区：访问共享变量的程序段

临界资源：一次只允许一个进程使用的资源

进程互斥：多个进程不能同时进入关于同一组共享变量的临界区域，否则可能发生与时间有关的错误

用flag为1表示该进程想要去临界区，当另一个进程flag也为1且turn也标注为1时，跳过
只有在另一个进程昨晚以后，flag为0，本进程才能进入临界区，然后再将flag设置为0
这里可以体现一种礼让的精神

信号量（semaphore）：
value记录的是，当value为-记录的是排队的个数，当value为+记录的是还能接受处理的个数

P原语：
来了一个进程，排队数+1，如果正在排队，让queue睡眠

V原语：
一个进程处理完，如果正在排队，让queue wakeup

先看S2，只有生产者生产完物品后执行V（s2），消费者才可以通过P（s2），保证消费者“有物可取”
再看S1，只有消费者取出物品后执行V（S1），生产者才可以通过P（S1），保证生产者”不会生产过剩“
最后看mutex，互斥量表示临界区中只有一个人

比向量大小，比较需求值，可用值，以及分配后是否安全决定是否分配

通过比较可用资源和request资源进行分配，若分配完后可以释放之前分配的，那么系统可用就会增加。

反之，若像（2）一样，request完但不释放，且几个所需资源都变成了0，那这样其他任意进程都无法执行完，就凉凉了

就是比较可用和need，最后将allocation加到available中，继续下一个

存储管理

静态等长分配：

位示图用二进制表示空页
空闲页面用基数+个数表示
空闲链用指针表示

动态异长分配
界地址，段式存储管理

最先适应：取第一个可满足区域
优点：尽量使用低地址空间，高区保持大空闲区域
缺点：可能分割大空闲区

最佳适应：取最小可满足区域
优点：尽量使用小空闲区，保持大空闲区
缺点：可能形成碎片

最坏适应：取最大可满足区域
优点：防止形成碎片
缺点：分割大空闲区

单一连续内存存储管理

内存空间划分：动态异长，整个内存被动态划分成多个长度各异的区域

进程空间划分：由连续的区域构成

所需表目
内存分配表：用于记录内存中已分配的区域
空闲区域表：用于记录内存尚未分配的区域

所需寄存器：
首地址寄存器：整个系统有一个，用于保存正在运行进程的起始地址(b)
限长寄存器：整个系统有一个，用于保存正在运行进程的长度(l)

地址映射：a -> a + b（a为逻辑地址，b为进程起始地址）

步骤：
1.由程序确定逻辑地址a
2.a与l比较是否越界
3.a与b相加得到物理地址

页式：

内存空间划分：内存空间静态地划分为若干个等长区域，每个区域称为一个物理页 架，每个页架通常由2i个单元，从0开始一次编址，称为页内地址。

进程空间划分：内存空间静态地划分为若干个等长区域，每个区域称为一个逻辑页 面，每个页架通常由2i个单元，从0开始一次编址，称为页内地址。

所需表目：

页表：用于记录进程的逻辑页面和内存页框之间的对应关系

总页表：用于记录页框的使用情况

所需寄存器：

页表首址寄存器：用于保存正在运行进程的页表的首址

页表长度寄存器：用于保存正在运行进程的页表长度

快表

地址映射：物理地址=页架首址+页内地址=页架号*2i + 页内地址

由于是等长，页内地址d是不变的。
通过页架首址p查快表得到f页架号或者通过p和进程起始地址b查表得到f，并记录进f
最后（f，d）即为物理地址

段式存储

内存空间划分：内存空间静态地划分为若干个长度各异区域，每个区域称为一个物 理段，每个物理段在内存中有一个起始地址，称为段首址。将物 理段中的所有单元由0开始依次编址，称为段内地址。

逻辑地址(s,d) -> 物理地址(b’+d)，这里是二维变一维的操作
若有快表，通过段号可知段首址b‘和段长l’，随后若d在l‘内，b’+d即为物理地址
若无，根据s（若在l内），结合进程地址b可以查到b‘和l’，比较后再放入快表即可

段页式存储

内存按页式等长，进程按段式不等长

段表：一个进程一个，用于记录各段的页表长度l‘和页表首址b’

页表：每段一个，用于记录一段中各个逻辑页号与页框号对应关系

段s对应进程，页对应内存，逻辑页号为p
(s, p, d) -> (f, d)
若有快表(s, p) -> f皆大欢喜
若无，比较sl是否越界，然后由s和b（进程首址）查段表得到页表(b’,l’)，然后通过比较p和l‘是否越界，再由b’和p查表得到f，最后（f，d）合并即可

也就是s和原生的进程首址b查段表得到页表（b’,l’)，再利用偏移量p得到f

页存储基础上加入内外存，若不在内存，则缺页中断（保存现场）：
1.读入空闲页
2.无空闲，淘汰其一并写回外存，进入1操作
3.更新页表和快表
4.恢复现场

这些都是软件完成

总结：
下次还要看文件和磁盘

来源：白速龙王的回眸