操作系统复习篇

若一个时间片尚未用完，正在运行的进程便已经完成，就立即激活调度程序，将它从就绪列表中删除，再调度就绪队列中队首的进程运行，并启动一个新的时间片
时间片设置应考虑在一个时间片用完时，计时器中断处理程序被激活。如果进程尚未运行完毕，调度程序将把它送往就绪队列的末尾

在当前进程A的一个时间片用完时,恰好有新进程B到达,则就绪队列的末尾的排序应该是BA。

确定时间片大小的因素：

系统对响应时间的要求
就绪队列中进程的数目
系统的处理能力

多级队列调度算法

就绪队列从一个分为多个，如：

前台【交互式】
后台【批处理】

每个队列有自己的调度算法，如:

前台——RR
后台——FCFS

调度需在队列间进行：

固定优先级调度，即前台运行完后再运行后台，有可能产生饥饿
给定时间片调度，即每个队列得到一定的CPU时间，进程在给定时间内执行；如80%的时间执行前台的RR调度，20%的时间执行后台的FCFS调度

多级反馈队列调度算法

进程能在不同队列间移动

其他调度算法的局限性：

短进程优先算法，仅照顾短进程而忽略了长进程
如果并未指明进程的长度，则短进程优先和基于进程长度的抢占式调度算法都将无法使用

优点：

不必事先知道各种进程所需的执行时间
可以满足各种类型进程的需要

基于公平原则的调度算法

主要考虑调度的公平性

保证调度算法：

性能保证，而非优先运行
如保证处理及分配的公平性

公平分享调度算法：

调度的公平性主要针对用户而言
使所有用户都获得相同的处理及时间或时间比例

3.3实时调度

实时调度是针对实时任务的调度

实时任务，都联系着一个截止时间：

硬实时HRT任务
软实时SRT任务

实时调度应具备一定的条件：

提供必要的信息：就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、优先级
系统处理能力强（周期性）
采用抢占式调度机制
采用快速切换机制：对终端具有快速响应能力、快速的任务分派能力

非抢占式调度算法

非抢占式轮转调度算法：

响应时间：数秒至数十秒
可用于要求不太严格的实时控制系统

非抢占式优先级调度算法：

响应时间：数秒至数百毫秒
可用于有一定要求的实时控制系统

抢占式调度算法

基于时钟中断的抢占式优先级调度：

响应时间：几十毫秒至几毫秒
可用于大多数实时系统

立即抢占的优先级调度：

响应时间：几毫秒至几百微秒
可用于有严格时间要求的实时系统

最早截止时间优先（EDF）调度算法

EDF根据任务的截止时间确定优先级，截至时间越早，优先级越高
?既可用于抢占式调度，也可用于非抢占式调度
非抢占式调度用于非周期实时任务
抢占式调度用于周期实时任务

最低松弛度优先LLF算法

根据任务的紧急程度（松弛度）确定任务优先级
- 松弛度越低，优先级越高
- 松弛度=必须完成时间-本身的运行时间-当前时间
主要用在抢占式调度方式中

优先级倒置现象

采用优先级调度和抢占方式，可能产生优先级倒置现象：高优先级进程被低优先级进程延迟或阻塞

解决方法：

制定一些规定，如规定低优先级进程执行后，其所占用的处理及不允许被抢占
建立动态优先级继承

?3.4Linux进程调度

?默认调度算法：完全公平调度算法CFS算法

基于调度器类：允许不同的可动态添加的调度算法并存，每个类都有一个特定的优先级

总调度器：根据调度器类的优先顺序，依次对调度器类中的进程进行调度
调度器类：使用所选的调度器类算法（调整策略）进行内部的调度
调度器类的默认优先级顺序为：Stop_Task>Real_Time>Fair>Idle_Tasks

普通进程调度：

采用SCHED_NORMAL调度策略
分配优先级、挑选进程并允许、计算使其运行多久
CPU运行时间与友好值（-20~+19）有关，数值越低优先级越高

实时进程调度：

实时调度的进程比普通进程具有更高的优先级
SCHED_FIFO：金承若处于可执行状态，就会一直执行，直到它自己被阻塞或主动放弃CPU
SCHED_RR:与SCHED_FIFO大致相同，只是进程在耗尽其时间片后，不能再执行，而是需要接受CPU的调度

3.5死锁概述

概念

死锁（Deadlock）：
- 指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态是，若无外力作用，这些进程将永远不能再向前推进
- 一组等待的进程，其中每一个进程都持有资源，并且等待着由这个组中其他进程所持有的资源
可重用性资源：一次只能分配给一个进程，不允许多个进程共享，遵循：请求资源、使用资源、释放资源
可消耗性资源：由进程动态创建和消耗（进程间通信的消息）
可抢占性资源：某进程在获得这类资源后，该资源可以再被其他进程或系统抢占，CPU（处理机）和主存区
不可抢占性资源：当系统把这类资源分配给某进程后，不能强行收回，只能在进程用完后自行释放，打印机、磁带机

产生死锁的必要条件

互斥：一段时间内某资源只能被一个进程占用
请求和保持：一个至少持有一个资源的进程等待获得额外的有其他进程持有的资源
不可抢占：一个资源只有当持有它的进程完成任务后，自由的释放
循环等待：等待资源的进程之间存在环

死锁原因

竞争不可抢占性资源引起死锁
竞争可消耗性资源引起死锁
进程推进顺序不当引起死锁

处理死锁的方法

确保系统永远不会进入死锁状态

死锁预防
死锁避免

允许进入死锁状态，然后恢复系统

死锁检测
死锁恢复

忽略这个问题，假装系统中从未出现过死锁。这个方法被大部分的操作系统采用，包括UNIX

方法：

预防死锁：破坏死锁的四个必要条件中一个或几个
避免死锁：在资源动态分配是，防止系统进入不安全状态
检测死锁：实现不采取任何措施，允许死锁发生，但即使检测死锁发生
解除死锁：检测到死锁发生时，采取相应措施，将进程从死锁状态中解脱出来

3.6预防死锁

破坏死锁的四个必要条件中的一个或几个

互斥：

互斥条件是共享资源必须的，不仅不能改变，还应加以保证

请求和保持：

必须帮正进程申请资源的时候没有占用其他资源

要求进程在执行前一次性申请全部的资源，只有没有占有资源时才可以分配资源
资源利用率低，可能出饥饿
改进：进程只获得运行初期所需的资源后，便开始运行；其后台在运行过程中逐步释放已分配的且用毕的全部资源，然后再请求新资源

非抢占：

如果一个进程的申请没有实现，它要释放所有占有的资源
先占的资源放入进程等待资源列表中
进程在重新得到旧的资源的时候可以重新开始

循环等待：

对所有的资源类型排序进行线性排序，并赋予不同的序号，要求进程按照递增顺序申请资源

如何规定每种资源的序号是十分重要的
限制新类型设备的增加
作业使用资源的顺序与系统规定的顺序不同
限制用户简单、自主的编程

3.7避免死锁

设一个简单而有效的模型，要求每一个进程声明它所需要的资源的最大数

死锁避免算法动态检查资源分配状态以确保不会出现循环等待的情况

资源分配状态定义为可用的与已分配的资源数，和进程所需的最大资源量

安全状态

当进程申请一个有效的资源的时候，系统必须确定分配后是安全的
如果存在一个安全序列，则系统处于安全态
即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕
进程序列<P1,P2,...,Pn>是安全的，如果每一个进程Pi所申请的可以被满足的资源数加上其它进程所持有的该资源数小于系统总数。

不安全状态

可能会到达死锁，但不是死锁

安全状态和不安全状态的区别

安全状态出发，能保证所有进程都能完成
不安全状态出发，无法保证（可能部分完成）

基本事实

如果一个系统在安全状态，就没有死锁
如果一个系统不是处于安全状态，就有可能死锁
死锁避免=>确保系统永远不会进入不安全状态

银行家算法

Dijkstra提出的银行家算法：其这样的名字是由于该算法原本是为银行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。在OS中也可以用它来实现避免死锁

针对资源有多个实例
每一个进程必须事先声明使用的最大量
当一个进程请求资源，它可能要等待
当一个进程得到所有的资源，它必须在有限的时间释放它们

这部分建议去B站找个视频来复习

3.8死锁的检测与解除

当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和解除死锁的手段，为此，系统必须：

保存有关资源的请求和分配信息
提供一种算法，以利用这些信息来检测系统是否已经入死锁状态

基本事实

如果图没有环，那么不会有死锁

如果图有环，那么：

如果每一种资源类型只有一个实例，那么死锁发生
如果一种资源类型有多个实例，那么可能死锁

资源分配图的简化?

在资源分配图中，找出一个既不阻塞又非独立的进程节点Pi。在顺利的情况下，Pi可获得所需资源而继续运行，直至运行完毕，再释放其所占有的全部资源，这相当于消去Pi所有的请求边和分配边，使之成为孤立的结点
P1释放资源后，便可使P2获得资源而继续运行，直到P2完成后又释放出它所占有的全部资源
在进行一系列的简化后，若能消去图中所有的边，使所有进程都成为孤立结点，则称该图是可完全简化的；若不能，则称其不可完全简化

死锁定理

对于较复杂的资源分配图，可能有多个既未阻塞，又非孤立的进程节点，不同的简化顺序，是否会得到不同的简化图？有关文献已经证明，所有的简化顺序，都将得到相同的不简化图
S为死锁状态的充分必要条件是：当且仅当S状态的资源分配图使不可完全简化的。该充分条件称为死锁定理

死锁的解除

常用解除死锁的两种方法：

抢占资源。从一个或多个进程中抢占足够数量的资源给死锁进程，以解除死锁
终止或撤销进程。终止系统中一个或多个死锁进程，直到打破循环回路，使死锁状态消除为止。
- 终止所有死锁进程（最简单方法）
- 逐个终止进程（稍温和方法）

进程终止

中断所有的死锁进程

一次中断一个进程，直到死锁环消失

应该选择怎样的中断程序，使“代价最小”？

进程的优先级
进程需要计算多久，以及需要多久结束
进程使用的资源，进程完成还需要多少资源
进程是交互的还是批处理的

其他问题

通信死锁
活锁
饥饿

通信死锁

竞争性同步：资源死锁
- 多个进程任务无关联，只是共享资源
协同同步：通信死锁
- 多个进程共同完成一个任务，无共享资源
通信死锁的场景：信息丢失
通信死锁的解决：超时重发

活锁

活锁场景：

多个礼貌的进程
- 获取资源成功
- 请求新资源失败
- 释放已有资源
- 再次尝试
有限的表容量
- 每个进程占有部分
- 试图申请更多资源

饥饿

饥饿场景：

打印机分配
- 优先小文件
- 小文件多
优先级调度
- 高优先级进程多

解决方案：先来先服务

四、进程同步

4.1进程同步的概念

概念

主要任务：使并发执行的进程之间能有小弟共享资源和相互合作，从而使程序的执行具有可再现性

进程间的制约关系：

间接相互制约关系（互斥关系）
- 进程互斥使用临界资源
直接相互制约关系（同步关系）
- 进程间相互合作

临界资源：

系统中某些资源一次只允许一个进程使用，这样的资源称为临界资源或互斥资源或共享变量
诸进程间采取互斥方式，实现了对这种资源的共享

临界区：进程中涉及临界资源的代码段

进入区：用于检查是否可以进入临界区的代码段

退出去：将临界区正被访问的标志恢复为未被访问标志

剩余区：其他代码

?同步机制应遵循的准则

空闲让进：当无进程处于临界区，应允许一个请求进入临界区的进程立即进入自己的临界区
忙则等待：已有进程处于其临界区，其他试图进入临界区的进程必须等待
有限等待：等待进入临界区的进程不能“死等”
让权等待：不能进入临界区的进程，应释放CPU（如转换到阻塞状态）

进程同步机制

软件同步机制：使用编程方法解决临界区问题
- 有难度、具有局限性，现在很少采用
硬件同步机制：使用特殊的硬件指令，可有效实现进程互斥
信号量机制：一种有效的进程同步机制，已被广泛应用
管程机制：新的进程同步机制

4.2软件同步机制

不做介绍

4.3硬件同步机制

关中断：

进入锁测试之前关闭终端，完成锁测试并上锁之后才打开中断
可有效保证互斥，但存在很多缺点

Test-and=Set指令

Swap指令

缺点：

不符合“让权等待”原则，浪费CPU时间
很难解决复杂的同步问题

4.4信号量机制（推荐看B站）

信号量-软件解决方案：

?保证两个或多个代码段不被并发调用
在进入关键代码段前，进程必须获取一个信号量，否则不能运行
执行完该关键代码段，必须释放信号量
信号量有值，为正说明它空闲，为负说明其忙碌

类型：

整型信号量
记录型信号量
AND型信号量
信号量集

整型信号量

信号量S-整型变量
提供两个不可分割的【原子操作】访问信号量（即要么都执行，要么都不执行）

void wait(int s){
 while(s<=0){};
 s--;
}
void signal(int s){
 s++;
}

Wait(s)又称为P(S)
Signal又称为V（S）
缺点：进程忙等

记录型信号量

每个信号量S除一个整数值S.value外，还有一个进程等待队列S.list，存放则色在该信号量的各个进程PCB

typedef struct {
	int value;
	Struct process* L;
}semaphore

void wait(semphore S) {
	S.value--;
	if (S.value < 0) {
		block(S.L);
	}
}

void signal(semphore S) {
	S.value++;
	if (S.value <=0) {
		wakeup(S.L);
	}
}

五、存储器管理

5.1存储器的层次结构

金字塔模型，越高越少，性能越高，价格越贵

概念

可执行寄存器：寄存器和主存储器
主存储器：内存或主存
寄存器：访问速度最快，与CPU协调工作，价格贵
高速缓存：介于寄存器和存储器之间
- 备份主存常用数据，减少对主存储器的访问次数
- 缓和内存与处理机之间的矛盾
磁盘缓存
- 暂时存放频繁使用的一部分磁盘数据和信息
- 缓和主存和I/O设备在速度上的不匹配
- 利用贮存的部分空间，主存可看成辅存的高速缓存

5.2程序的装入和链接

程序的运行步骤：

编译：由编译程序（Compiler）对源程序进行编译，形成若干个目标模块
链接：由链接程序（Linker）将目标模块和它们所需要的库函数链接在一起，形成一个完整的装入模块
由装入程序（Loader）将装入模块装入内存

物理地址和逻辑地址

物理地址（绝对地址）

物理内存的地址，内存以字节为单位编址
物理地址空间：所有物理地址的集合

逻辑地址（虚拟地址、相对地址）

由CPU产生的地址，即程序编译后使用的相对于0字节的地址
逻辑地址空间：由程序所生成的所有逻辑地址的集合

内存保护的实现：硬件

基地址寄存器：保存最小的合法物理内存地址（基地址）
界限寄存器：保存合法的地址范围大小（界限地址）
内存空间保护的实现：判断“基地址<=物理地址<（基地址+界限地址）”是否成立

程序的装入?

绝对装入方式：

编译时产生的地址使用绝对地址
程序或数据被修改时，需要重新编译程序

可重定位装入方式：

编译后的目标模块使用相对地址
在装入时，完成重定位（静态重定位）
需硬件支持

动态运行时装入方式：

编译后的目标模块使用相对地址
在装入时，完成重定位（动态重定位）

程序的链接

静态链接：

在程序运行前，将各目标模块及他们所需的函数链接成一个完成整的装配模块，以后不再拆开
对相对地址进行修改；变换外部调用信号

装入时动态链接：

在装入内存时，采用边装入边链接的链接方式
便于修改和更新
便于实现对目标模块的共享

运行时动态链接：?

将某些目标模块的链接推迟到执行时才执行。即在执行过程中，若发现一个被调用模块尚未装入内存时，立即由OS去找该模块并将它装入内存，并把它连接到调用者模块上
加快装入过程，节省大量的内存空间

5.3对换与覆盖

略

5.4连续分配存储管理方式

连续分配方式：为一个用户程序分配一个连续的内存空间。

分类：

单一连续分配
固定分区分配
动态分区分配
动态可重定位分区分配

单一连续分配

内存：

系统区：供OS使用、低址部分
用户去：供用户使用

分配方式：单道程序环境下，金装有一道用户程序，即整个内存的用户空间由改进成独占

内存分配管理十分简单，内存利用率低
用于单用户、单任务OS

未采取存储器保护措施：节省硬件、方案可行

固定分区分配

最早的，也是最简单的一种可运行多道程序的存储管理方式
与先把可分配的主存储器空间分割成若干个连续区域，称为一个分区
每个分区的大小可以相同也可以不同。但分区大小不变，每个分区装一个且只能装一个作业
内存分配：如果有一个空闲区，则分配给进程

动态分区分配

又称为可变分区分配，根据进程的实际需要，动态地位置分配内存空间
数据结构：表、链
分配算法：顺序式、索引式
分配操作：分配内存、回收内存

分配算法：

基于顺序搜索的动态分区分配算法：首次适应算法、循环首次适应算法、最佳适应算法、最坏适应算法
基于索引搜索的动态分区分配算法：快速适应算法、伙伴系统、哈希算法

快速适应算法：

将空闲分区按其容量大小进行分类，具有相同容量的所有空闲分区设有一个空闲分区链表
系统设有一张管理索引表，每一项对应一个空闲分区类型
分配时，根据进程长度，从索引表中寻找能容纳它的最小空闲分区链表；从链表中取下第一块进行分配
特点：
- 优点：不分割分区，不产生碎片，查找效率高
- 缺点：分区归还主存时算法复杂，系统开销较大，存在浪费

伙伴系统：

分区大小均为2的k次幂
内存按2的幂的大小来分配，如4KB、8KB等
- 满足要求是以2的幂为单位的
- 如果请求不为2的幂，则需要调整到下一个更大的2的幂：先计算一个i值，使2i-1<n<=2i，在2i的空闲区表中找
- 当分配需求小于现在可用内存时，当前段就分为两个更小的2的幂段
  - 继续上述操作直到合适的段大小
主要用于多处理机系统中（Linux早期版本）

哈希算法：

建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项对应于一个空闲分区链表的头指针
进行分配时，根据空闲区大小，通过计算哈希函数，得到在哈希表中的位置，找到对应的空闲分区链表
优点：查找快速

动态可重定位分区分配

连续分配存在的问题
- 碎片：不能被利用的小分区
- 解决方案：紧凑，要求代码和数据可以在内存中移动
- 紧凑：通过移动内存中的作业位置，以把原来多个分散的小分区拼接成一个大分区的方法，也叫“拼接”
动态重定位：在指令运行时，实现地址转换（相对地址转换为绝对地址）
分配算法：类似于动态分区分配算法，增加了紧凑的功能

5.5分页存储管理方式

进程的逻辑空间可能是不连续的，如果有可用的物理内存，它将分给进程
把物理内存分成大小固定的块，称为物理块（frame）。（大小为2的幂，通常为1KB~8KB）
把逻辑内存也分成固定大小的块，称为页（page）
保留所有空闲块的记录
运行一个有N页大小的程序，需要找到N个空的页框来装入程序
存在页内碎片：进程最后一页经常装不满，而形成不可利用的碎片

页表

系统为每个进程建立了一张页表
逻辑地址空间内所有页，一次在页表中有一表项，记录相应页在内存中对应的物理块号
页表的作用：实现从页号到块号的地址映射

页表的实现

页表被保存在主存中
页表寄存器（PTR）指向页表的起始地址和长度
在这个机制中，每一次的数据/指令存取需要两次内存访问，一次是访问页表，一次是访问数据/指令
解决两次访问的问题，是采用小但专用且快速的硬件缓冲，这种缓冲称为转换表缓冲器（TLB）或联想寄存器

页表结构

现代的大多数计算机系统，都支持非常大的逻辑地址空间。在这样的环境下，页表就变得非常大，要占用相当大的空间。

解决方法：

对页表所需要的内存空间，采用离散分配方式
部分页表调入内存

页表结构：两级页表、多级页表、反置页表

5.6分段存储管理方式

略

六、虚拟存储器

6.1虚拟存储器概述

前面所介绍的各种存储器管理方式，有一个共同特点：作业全部装入内存后才能运行

问题：

大作业装不下
少量作业得以运行

解决方法：

扩充内存
逻辑上扩充内存容量（虚拟存储器）

虚拟存储器定义

基于局部性原理，应用程序在运行之前，没有必要全部装入内存，仅需将那些当前要运行的部分页面或段先装入内存便可运行，其余部分暂留在盘上

虚拟存储器：具有请求调度功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统

其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而成本接近于外存

虚拟存储器的特征

多次性：作业中的程序和数据允许被分成多次调入内存
对换性：作业运行时无需常驻内存
虚拟性：从逻辑上扩充了内存容量，使用户看到的内存容量远大于实际内存容量

虚拟存储器的实现方法

?请求分页系统：

硬件支持：页表、缺页中断、地址变换机构
软件支持：请求调页软件、页面置换软件

请求分段系统：

硬件支持：段表、缺段中断、地址变换机构
软件支持：请求调段软件、段置换软件

段页式虚拟存储器：

增加请求调页和页面置换
Intel 80386及以后

6.2请求分页存储管理方式

?请求分页中的硬件支持

请求页表机制、缺页中断机构、地址变换机构

?请求页表机制：

状态为：指示该页是否在内存
访问字段：记录该页在一段时间内被访问的次数
修改位：标志该页是否被修改过
外村地址：指示该页在外存中的地址（物理块号）

缺页中断机构：

在指令执行期间产生和处理中断信号
一条指令在执行期间，可能产生多次缺页中断

地址变换机构：与分页内存管理方式类似

请求分页中的内存分配

最小物理块数的确定：保证进程正常运行所需的最小物理块数

物理块的分配策略：

?固定分配局部置换
可变分配全局置换
可变分配局部置换

物理块分配算法：

平均分配算法
按比例分配算法
考虑优先权的分配算法

页面调入策略

何时调入页面：

预调页策略：预先调入一些页面到内存
请求调页策略:发现需要访问的页面不在内存是，调入内存

从何处调入页面：

如系统拥有足够的对换区空间，全部从对换区调入所需页面
如系统缺少足够的对换区空间，凡是不会被修改的文件，都直接从文件区调入；当换出这些页面时，由于未被修改而不必将它们重写磁盘，以后再调入时，仍从文件区直接调入
UNIX方式：未运行过的页面，从文件区调入；曾经运行过但又被换出的页面，从对换区调入

页面调入方法

查找所需页在磁盘上的位置
查找一内存空闲块：
- 如果有空闲块，就直接使用
- 如果没有空闲块，使用页面置换算法选择一个“牺牲“内存块
- 将牺牲内存块的内容写到磁盘上，更新页表和物理块表
将所需页读入空闲块，更新页表
重启用户进程

6.3页面置换算法

种类

最佳置换算法（OPT）
先进先出置换算法（FIFO）
最近最久未使用置换算法（LRU）
最少使用算法（LFU）
Clock置换算法
页面缓冲算法PBA

需要一个最小的缺页率

通过运行一个内存访问的特殊序列（访问序列），计算这个序列的缺页次数

最佳置换算法（OPT）

被置换的页将是之后最长时间不被使用的页

由于需要预知未来，因此无法实现，但可以用来作为置换算法的性能评价依据。

先进先出置换算法（FIFO）

思路：总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰

?实现简单，性能较差，因为调出的页可能是经常访问的。很少单独使用

?最近最久未使用置换算法（LRU）

?核心思想：根据历史预测未来

LRU算法的硬件支持：寄存器、栈

寄存器：为内存中的每个页面设置一个移位寄存器

被访问的页面对应寄存器的Rn-1位置为1，定时右移
具有最小数值的寄存器所对应的页面为淘汰页

栈：保存当前使用的各个页面的页面号

被访问的页，移到栈顶
栈底时最近最久未使用页面的页面号

这种方法是最优置换算法的一种近似，但开销比较大

最少使用算法（LFU）

为内存中的每个页面设置一个移位寄存器，用来记录该页面的被访问频率

思路：缺页时，置换访问次数最少的页面

特征：

开销较大
开始时频繁使用，但以后不使用的页面很难置换
- 解决方法：计数定期右移

Clock置换算法

简单的Clock算法

每个页都与一个访问位相关联，初始值为0
当页被访问时访问位为1
置换时选择访问位为0的页；若为1，重新置为0

改进型Clock算法

除需考虑页面的使用情况外，还需增加置换代价
淘汰时，同时检查访问位A与修改位M
- A=0,M=0:最佳淘汰页
- A=0,M=1
- A=1,M=0
- A=1,M=1:最坏淘汰页
置换时，循环一次查找第一类、第二类页面，找到为止

页面缓冲算法PBA

影响效率的因素：页面置换算法、写回磁盘的频率、读入内存的频率

目的：

显著降低页面换进、换出的频率，减少了开销
可采用较简单的置换策略，如不需要硬件支持

具体做法：设置两个链表

空闲页面链表：保存空闲物理块
修改页面链表：保存已修改且需要被换出的页面等被换出的页面数目到达一定值时，再一起换出外存

6.4抖动与工作集

抖动：一个进程的页面经常换入换出

如果一个进程没有足够的页，那么缺页率将很高，将导致：

CPU利用率低下
操作系统任务需要增加多道程序设计的道数
系统中将加入一个新的进程

产生抖动的原因?

根本原因：

同时在系统中运行的进程太多
同时分配给每一个进程的物理块太少，不能满足进程运行的基本要求,致使进程在运行时，频繁换页，必须请求系统将所缺页面调入内存

抖动的发生与系统为进程分配物理块的多少有关

工作集

所谓工作集，时指在某段时间间隔t里进程是既要访问页面的集合，用 $w\left ( t,\Delta \right )$ 表示， $w\left ( t,\Delta \right )$ 属于 $w\left ( t,\Delta+1 \right )$ .

工作集的变化：

进程开始执行后，随着访问新页面逐步建立比较稳定的工作集
当内存访问的局部性区域位置大致稳定时，工作及大小也大致稳定
局部性区域的位置变化时，工作集快速扩张和收缩过度到下一个稳定值

抖动的预防方法

采取局部置换策略：只能在分配给自己的空间内进行置换

把工作集算法融入到处理机调度中

利用L=S准则调节缺页率：

L是缺页之间的平均时间
S是平均却页服务时间
L>S说明很少发生缺页
L<S说明频繁缺页
L=S磁盘和处理机都可达到最大利用率

?选择暂停进程

6.5请求分段存储管理方式

略

七、输入/输出系统

?7.1I/O系统的功能、模型和接口

I/O系统管理的主要对象：I/O设备和对应的设备控制器

I/O系统的主要任务：完成用户提出的I/O请求，提高I/O速率和设备利用率

I/O系统的基本功能

能够隐藏物理设备的细节
能够保证OS与设备无关
能够提高处理机和I/O设备的利用率
能够对I/O设备进行控制
能够确保对设备的正确共享
能够处理错误

各种I/O模块之间的关系

I/O系统的上下接口：

上接口：I/O系统接口
下接口：软件/硬件接口
在上、下接口之间是I/O系统

I/O系统的分层：

中断处理程序
设备驱动程序
与设备无关的I/O软件

I/O系统接口

块设备接口：

块设备：数据的存取和传输都是以数据块为单位的设备，如磁盘，光盘，通常采用DMA I/O方式
隐藏了磁盘的二维结构
将抽象命令映射为底层操作

流设备（字符设备）接口：

字符设备：数据的存取和传输都是以字符为单位的设备，如键盘，打印机。不可寻址
通常采用中断驱动I/O方式
get和put操作：字符设备采用顺序存取方式
in-control指令：包含许多参数，每个参数均表示一个与具体设备相关的特定功能

网络通信接口：

OS提供相应的网络软件和网络通信接口，以使计算机能通过网络同网络上的其他计算机进行通信

7.2I/O设备和设备控制器

I/O设备的类型

按使用特性分类：存储设备、I/O设备
按传输速率分类：
- 低速：键盘、鼠标等
- 中速：行式打印机等
- 高速：磁带机、磁盘机
按信息交换单位分类：块设备、字符设备
按设备的共享属性分类：独占设备、共享设备

设备与控制器之间的接口

通常，设备并不是直接与CPU进行通信，而是与设备控制器通信，因此，在设备与设备控制器之间应有一接口，在该接口中有三类信号个对应一条信号线，分别是：数据、状态、控制信号线。

设备控制器

主要功能：控制一个或多个I/O设备，以实现I/O设备和计算机之间的数据交换
是CPU与I/O设备之间的接口，接受CPU的命令，控制I/O设备工作
是一个可编制的设备：
- 当仅控制一个设备时，只有唯一地址
- 当控制多个设备时，有多个地址，并每一个地址对应一个设备

基本功能：

接受和识别命令
数据交换
标识和报告设备的状态
地址识别
数据缓冲区
差错控制

设备控制器的组成：

设备控制器与处理机的接口：实现CPU与设备控制器之间的通信，包括数据、地址和控制线
与设备的接口：连接设备
I/O逻辑：实现对设备的控制

内存映像I/O

驱动程序将抽象I/O命令转换成具体的命令和参数等装入设备控制器的相应寄存器，由控制器执行这些命令，具体实施对I/O设备的控制。具体方法：

采用特定I/O指令：访问内存和设备需要两种不同的指令
采用内存映像I/O形式：在编址上不再区分内存单元地址和设备控制器中的寄存器地址，统一编址k。k在0~n-1范围时，为内存地址；若k>=n时，为某控制器的寄存器地址。统一了访问方法，简化了I/O编程

I/O通道

I/O通道的引入：

目的：使一些原来由CPU处理的I/O任务转由通道来承担，从而把CPU从繁杂的I/O任务中解脱出来。

通道是特殊处理机，与普通处理机的区别：指令类型单一、没有自己的内存（与CPU共享内存）

通道类型：

字节多路通道：按字节交叉方式工作的通道
数组选择通道：可以连接多台高速设备，但在一段时间内只允许一台设备传输数据，传输率高
数组多路通道：结合前两者优点，含有多个非分配型子通道

“瓶颈”问题：通道价格昂贵，造成通道不足。

解决方法：增加设备到CPU间的通路而不增加通道

多路方式不仅解决了“瓶颈”问题，而且提高了系统的可靠性

I/O设备的控制方式?

用轮询的可编程I/O方式（基本不用）：
- 实现容易但效率偏低，CPU会长期处于忙等??
使用中断的可编程I/O方式（广泛采用）：
- 当某进程要启动某个I/O设备工作时，便由CPU向相应的设备控制器发出一条I/O命令，然后立即返回继续执行原来的任务。设备控制器域是按照命令的要求去控制指令的I/O设备。此时，CPU与I/O设备并行操作
直接存储器访问方式（DMA）：进一步减少CPU对I/O设备的干预
- 数据传输的基本单位是数据块
- 所传送的数据是从I/O设备直接送入内存的，或者相反
- 仅在传送一个或多个数据块的开始和结束时，才需CPU干预
I/O通道方式：是DMA方式的发展，可进一步减少CPU的干预
- 是对一组数据快以读/写及有关的控制和管理作为单位干预
- 可实现CPU、通道和I/O设备三者的并行操作
- 通道程序：由一系列通道指令构成，通道指令不同于CPU指令

7.3中断和中断处理程序

介绍

中断和陷入：

中断：CPU对I/O设备发来的中断信号的一种响应
陷入：CPU内部事件引起的中断

中断向量表：存放每个设备的中断处理程序的入口地址，并为每个设备的中断请求作为一个中断号，对应于中断向量表中的一个表项

中断优先级：系统为每个中断源规定不同的优先级

对多中断的处理方式

当处理及正在处理一个中断时，又来了一个新的中断请求，有两种处理方式：

屏蔽（禁止）中断
嵌套中断

Linux中的中断处理

采用了上半部和下半部机制：

上半部：中断处理程序。（简单快速，执行时禁止一些或全部中断）
下半部：一些虽然与中断有关但是可以延后执行的任务（稍后执行，执行时可以响应所有的中断）

中断处理程序的设计：

注册中断
处理中断
注销中断

7.4设备驱动程序

略

7.5与设备无关的I/O软件

略

7.6用户层的I/O软件

?略

7.7缓冲区管理

缓冲区是一个存储区域，可以由专门的硬件组成；更多的是利用内存。

引入缓冲区的原因：

缓和CPU与I/O设备间速度不匹配的矛盾
减少对CPU的中断频率，放宽对CPU中断响应时间的限制
解决数据粒度不匹配的问题
提高CPU与I/O设备之间的并行性

单缓冲

每当用户进程发出一I/O请求时，操作系统便在主存中位置分配一缓冲区

在设备输入时

T:从磁盘把一块数据输入到缓冲区的时间
M:操作系统将该缓冲区中的数据送到工作区的时间
C:CPU对这块数据处理的时间
当T>C，系统对每一块数据的处理时间为M+T（C忽略）
反之，则为M+C
系统对每一块数据的处理时间为：Max(C,T)+M

双缓冲

在设备输入时，先将数据送入第一缓冲区，装满后便转向第二缓冲区
此时操作系统可以从第一缓冲区移出数据，并送入用户进程，接着由CPU对数据进行计算
在双缓冲时，系统处理一块数据的时间可以粗略地认为是Max(C,T),如果C>T，则可使CPU不必等待设备输入

环形缓冲区

当输入和输出两者的速度相差悬殊，双缓冲的效果则不够理想，不过可以随着缓冲区数量的增加，使情况有所改善。

多个缓冲区：

在循环缓冲中包含多个缓冲区，其每个缓冲区的大小相同
作为输入的多缓冲区可分为三类：
- 用于装输入数据得空缓冲区R
- 已装满数据的缓冲区G
- 计算进程正在使用的现行工作缓冲区C
多个指针：
- 作为输入的缓冲区可设置3个指针：
  - 用于指示及算您成下一个而用缓冲区G的指针Nextg
  - 指示输入进程下次可用的空缓冲区R的指针Nexti
  - 用于指示计算进程正在使用的缓冲区C的指针Current

缓冲池

当系统较大时，将会有许多循环缓冲，这不仅要消耗大量的内存，且利用率不高。

为了提高缓冲区利用率，引入公共缓冲池，在池中设置了多个可供若干个进程共享的缓冲区

缓冲池的组成：

空闲缓冲队列：空闲缓冲区所链城的队列
输入队列：装满输入数据的缓冲区所链成的队列
输出队列：装满输出数据的缓冲区所链成的队列
4中工作缓冲区：收容输入、提取输出、收容输出、提取输入缓冲区

缓存和缓冲

缓冲可以保存数据项的唯一的现有版本
缓存指示提供一个位于其他地方的数据项的更快存储副本
有时，同一个内存区，既可以是缓冲，也可以是缓存

7.8磁盘性能概述和磁盘调度

磁盘结构

盘面（磁头）：磁盘设备可能包含一个或多个盘片，每个盘片分为一个或两个盘面，每个面上有一个读写磁头
磁道（柱面）：每个盘面可分为若干磁道
扇区：每条磁道逻辑上分成若干大小相同的扇区。每个扇区的大小相当于一个盘块（数据块）
每条磁道上可存储相同数目的二进制位
磁盘密度即每英寸中所存储的位数，显然是内层磁道叫外层磁道的密度高

容量=柱面*磁头*扇区

磁盘的类型

分类一：硬盘、软盘

分类二：单片盘、多片盘

分类三：

固定头：每个磁道上都有一个读写磁头
- 并行方式读/写，有效提高I/O速度
- 主要用于大容量磁盘
移动头：每个盘面仅有一个磁头，能移动寻道
- 串行方式读/写，I/O速度较慢
- 广泛应用于中、小磁盘设备中

磁盘访问时间

磁盘在工作时是以恒定速率旋转

为了读写：

磁头必须移动到要求的磁道上
等待所制定的山区开始位置旋转到磁头下
开始读写数据?

磁盘的访问时间=寻道时间+旋转延迟时间+传输时间

早期的磁盘调度算法

磁盘调度的目标，使使磁盘的平均寻道时间最小

先来先服务FCFS
最短寻道时间优先SSTF
SCAN算法
循环扫描算法C-SCAN
CLOCK
NStepSCAN算法
FSCAN算法

先来先服务FCFS调度算法

最简单的磁盘调度算法，但平均寻道时间可能较长

最短寻道时间优先SSTF

选择这样的进程，其要求访问的磁道，与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但不保证平均寻道时间最短（贪心算法）

SSTF明显优于FCFS,但可能会出现饥饿

SCAN算法

也称：电梯调度算法。不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头当前的移动方向

磁臂从磁盘的一段向另一端移动，沿途响应服务请求，当到达另一端是，磁头改变移动方向，继续处理。磁头在磁盘上来回扫描

循环扫描算法C-SCAN

提供比SCAN算法更均匀的等待时间

磁头从磁盘一端移动到另一端，随着移动不断处理请求。不过，当磁头移动到另一端时，马上返回到磁盘开始，返回时并不处理请求。

CLOCK

?C-SCAN的一种形式。磁头之移动到一个方向上最远的请求位置。戒指，马上回头，而不是继续道磁盘的尽头

NStepSCAN算法

“磁臂粘着”现象：进程反复请求对某一磁道的I/O操作

将磁盘请求队列分为若干个长度为N的子队列；按FCFS算法依次处理子队列；每个子队列使用SCAN算法

FSCAN算法

是?NStepSCAN算法的简化：

请求队列分为两个子队列：

当前所有请求队列，按SCAN算法调度
扫描期间，新出现的请求队列，推迟到下一次扫描时处理

八、文件管理

8.1文件和文件系统

数据项、记录和文件

数据项：

基本数据项：描述一个对象的某种属性，又称字段
组合数据项：由若干个基本数据项组成?

记录：

?记录时一组相关数据项的集合，用于描述一个对象在某方面的属性
关键字：唯一能表示一个记录的数据项
如；学号、学号+课程号

文件：具有文件名的一组相关元素的集合

有结构文件（记录）、无结构文件（字符流）
在文件系统中温嘉三年hi最大的单位，描述了一个对象集

文件类型

按用途分类：

系统文件
用户文件
库文件

按文件中数据的形式分类：

源文件
目标文件
可执行文件

按存取控制属性分类：

只执行文件
只读文件
读写文件

按组织形式和处理方式分类：

普通文件
目录文件
特殊文件

文件系统的层次结构

对象及其属性

对对象操纵和管理的软件集合

文件管理系统的核心部分

文件系统的接口

命令接口
程序接口

文件系统的功能

对文件存储空间的管理
对文件目录的管理
用于将文件的逻辑地址转换为物理地址的机制
对文件读和写的管理
对文件的共享和保护

与文件系统有关的软件

I/O控制层：文件系统最底层，设备驱动程序层
基本文件系统层：处理内存与磁盘之间数据块的交换
基本I/O管理程序：完成与磁盘I/O有关的事物
逻辑文件系统：处理与记录和文件相关的操作

文件操作

最基本的文件操作：

创建文件、删除文件、读文件、写文件
设置文件的读/写位置

文件的打开和关闭操作：

打开：系统将文件从外存拷贝到内存打开文件表的一个表目中
关闭：把文件从打开文件表的表目中删除

其他文件操作：

重命名、改文件拥有者、查询文件状态等
创建/删除目录?

8.2文件的逻辑结构

?文件结构

文件的逻辑结构：从用户观点所观察的文件组织形式
文件的物理结构：文件的存储结构，指系统将文件存储在外村上所形成的一种存储组织形式
- 不仅与存储介质的存储性能有关
- 也与所采用的外村分配方式有关

文件的逻辑结构和物理结构，都影响文件的检索速度

文件名和文件类型

按文件是否有结构分类：

有结构文件（记录式文件）
- 定长记录
- 变长记录
无结构文件（流式文件）
- 源程序、可执行文件、库函数

有结构文件按文件的记录方式分类：

顺序文件
索引文件
索引顺序文件

顺序文件

串结构：按存入时间的先后顺序，记录间的顺序与关键字无关，但检索比较费时

顺序结构：指定一个字段为关键字，所有记录按关键字排序。检索时可用有效的查找算法。

优点：有利于大批记录读写、存取效率最高、可存储在顺序存储设备上

缺点：增删改查效果差

索引文件

按关键字建立索引：

为边长记录文件建立一张索引表
索引表按关键字排序
实现直接存取?

?具有多个索引表的索引文件：

为顺序文件建立多个索引表
为每一个可能会成为索引条件的域配置一张索引表

顺序索引文件

有效克服了变长记录文件不便于直接存取的缺点
保留了顺序文件的关键特征：记录按关键字的顺序组织
新增了2个新特征：
- 引入文件索引表:实现随机访问
- 增加溢出文件：记录新增、删除和修改的记录

文章来源:https://blog.csdn.net/m0_63024355/article/details/135464866
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！