操作系统笔记

第一章绪论

计算机系统

硬件
- 中央处理器（运算器和控制器）
- 存储器
- 输入设备
- 输出设备
软件
- 系统软件
- 应用软件

计算机系统的几个阶段

手工操作阶段
- 由一道程序独占机器
- 需要人工操作
早期批处理
1. 联机批处理
  - 慢速的输入输出设备和主机直接相连
  - 解决了作业自动转接的问题
  - 设备输入时CPU有大量的空闲等待时间
2. 脱机批处理
  - 使用不和主机直接相连的专用输入输出设备(卫星机)
  - 卫星机将数据转入速度较快的磁带机中, 主机与磁带机交换数据
  - 输入和计算可以并行, 提高了CPU的利用率
多道程序系统
- 计算机的内存中可以同时存在多道程序
- 宏观上这些程序并行
- 微观上这些程序交替执行
- 由各个程序自行决定是否放弃CPU, 从而让其他程序执行
分时操作系统
- 处理机的时间分成时间片
- 按照时间片轮流将处理机分配给各个作业
- 作业在一个时间片内无法完成任务, 则该任务中断, 将处理机让给下一个任务
- 由于时间片很短, 因此每个用户都感觉自己独占计算机
实时操作系统
- 要求计算机对于外来信息在运行的时间内做出快速响应
通用操作系统
- 兼有多道批处理, 分时, 实时处理的功能的操作系统

操作系统的基本类型

批处理操作系统
- 用户脱机使用计算机
- 成批处理
- 多道程序运行
分时系统
- 交互性, 用户可以在执行过程中进行控制
- 多用户同时性, 多个用户可以在一台计算机上共享CPU和其他资源
- 独立性, 每个用户都感觉自己独占计算机

操作系统的功能

处理机管理
存储管理
设备管理
文件系统管理
用户接口

操作系统内核架构

简要结构: 应用程序和操作系统位于同一个地址空间, 不实现内存管理, 特权级隔离等功能, 例如MS-DOS系统.
宏内核:操作系统的所有模块(进程调度,内存管理,文件系统,设备驱动等)都运行在内核态, 例如Linux系统.
微内核:内核仅保持最基础的功能,其他模块作为独立的服务, 例如Mach系统.
外核架构: 由应用程序控制硬件资源, 对硬件的抽象封装到LibOS,与应用程序之间链接.
多内核架构: 解决CPU核数越来越多, 使用异构CPU的场景. 对每个核抽象一个节点.
混合内核架构: 由于发展的需要, 各种架构之间存在一些混合使用的情况.

宏内核由于集成了所有的功能, 因此对于不同架构的扩展性较低; 由于代码量更大, 因此安全性方面无法有效的保证, 且大量功能运行在内核空间, 容易出现单点故障. 微内核功能精简, 更容易保证安全性, 但进程间通信开销更大, 容易造成性能低下.

第二章用户界面

作业

在一次应用业务的处理过程中, 从输入开始到输出结束, 用户要求计算机所做的有关该次业务处理的全部工作称为一次作业
作业的概念一般用于早期批处理系统和现在的大型机, 巨型机

作业说明书

作业说明书一般包括以下内容

作业的基本描述, 通常包括用户名, 作业名, 使用的编程语言, 最大处理时间等
作业的控制描述, 包括控制的描述, 例如是联机还是脱机
资源的要求描述, 包括要求的内存大小, 外设种类或实用程序等

一般用户的输入输出方式

联机输入输出方式, 外围设备直接和主机相联
脱机输入输出方式, 使用单独的输入输出设备, 通过缓冲设备与主机交换数据
直接耦合方式, 把主机和外围机通过一个共用大容量设备直接连接
spooling系统, 多台外围设备通过通道或者DMA方式与主机的外出连接
网络联机方式

操作系统提供的两个接口

为用户提供的各种命令接口
为编程人员提供的系统调用

系统调用

设备管理, 用于请求和释放相关的设备, 以及启动设备操作等
文件管理, 包括对文件的读, 写, 创建和删除等
进程管理, 包括进程的创建, 执行, 撤销, 等待, 执行优先级控制等
进程通信, 用于在进程之间传递消息或信号
存储管理, 包括检查作业占据的内存大小, 获得作业内存地址等
线程管理, 包括线程的创建, 调度, 执行和撤销等

陷阱机构与陷阱指令

在系统中为控制系统调用服务的处理机构称为陷阱处理机构
由于系统调用因此处理机中断的指令称为陷阱指令(或访管指令)
陷阱指令传递参数有三种方法
1. 陷阱指令自带的参数
2. 专用的寄存器
3. 内存中专门开辟的堆栈区

第三章进程管理

程序顺序执行的特点

顺序性
封闭性, 程序执行的结果由给定的初始结果充分决定, 不受外界因素决定
可再现性, 执行结果与运行速度无关, 重复执行结果相同

多道程序执行特点

独立性, 每道程序都是逻辑上独立的
随机性, 各个程序的执行顺序是随机的
资源共享性, 各个程序之间的硬件, 软件资源是共享的

程序的并发执行

一组在逻辑上互相独立的程序或程序段在执行过程中, 其执行时间在客观上相互重叠的执行方式

进程

进程是并发执行的程序在执行过程中分配和管理资源的基本单位, 具有以下特点

进程是一个动态概念, 而程序是一个静态概念
进程具有并发特性, 而程序没有
进程是竞争计算机系统资源的基本单位, 其并发现受到系统约束
不同的进程可以包含同一程序, 只要该程序对应的数据集不同

进程控制块

进程的静态描述由三部分组成, 进程控制块(PCB), 有关程序段, 该程序段操作的数据集, 进程控制块具有如下结构

描述信息
- 包括进程名, 用户名和进程家族关系等
控制信息
- 包括进程的当前状态, 进程优先级, 程序开始地址, 各种计数信息, 通讯信息
资源管理信息
1. 占用内存大小以及管理数据的指针
2. 对换或覆盖的有关信息
3. 共享程序段大小以及起始位置
4. 输入输出设备的设备号
5. 指向文件系统的指针以及有关标识
CPU现场保护结构
- 一个专门的用于保存CPU数据的结构, 可以用于进程中断后的恢复

总之, PCB是系统感知进程的唯一实体, 通过对PCB的操作, 系统为有关进程分配资源从而使的有关进程得以被调度和执行, 执行结束后, 也通过释放PCB来释放进程所占有的各种资源.

进程上下文

进程上下文是进程执行过程中顺序关联的静态描述
已执行过的进程指令和数据在相关寄存器中的内容称为上文
正在执行的指令和数据在寄存器中的内容称为正文
待执行的指令和数据在寄存器中的内容称为下文

进程上下文切换

进程上下文的切换一般分为三个部分

保护被切换进程的正文部分至有关存储区
操作系统进程中, 有关调度和资源分配的程序执行, 并选择新的进程
将被选中的进程的正文部分从有关存储区恢复到有关寄存器和堆栈, 激活被选中进程执行

进程状态和转换

进程至少可以分成五个状态：初始状态, 执行状态, 等待状态, 就绪状态, 终止状态
一个进程被创建后, 处于初始状态
处于就绪状态的进程得到了除CPU以外的所有资源, 只要被调度就可以立即执行, 进入执行状态
处于执行状态的进程有三种转移状态
1. 时间片到达, 回到就绪状态
2. 由于某些事件, 进入等待状态
3. 完成程序, 进入终止状态
处于等待状态的程序在某些事件的唤醒下, 进入就绪状态

原语

在系统态下执行的完成系统特定功能的程序段
是一个不解分割的操作,不允许被中断,不能并发执行

进程控制

1. 进程创建

查询PCB总链,是否有同名进程
如果有,则报错,否则向PCB资源池申请一个空PCB结构
如果不能获得申请,报错,否则填写PCB有关内容
将PCB放入就绪队列和PCB总链

2. 进程撤销

查询进程链表或进程家族
如果没有查到此进程,报错,否则查询该进程是否有子进程
如果有,递归的撤销子进程
释放该进程占用的资源
释放PCB结构本身

3. 进程阻塞

保存当前进程的CPU现场
设置该进程状态
该进程进入等待队列
转进程调度

4. 进程唤醒

从等待队列取出进程
将此进程置为就绪态
将进程送入就绪队列
转进程调度或返回

进程互斥

不允许多个并发程序交叉执行的一段程序称为临界区
由共享公共资源而造成的对并发进程执行速度的间接制约, 简称间接制约
一组并发进程中的一个或多个程序段, 因共享某一共有资源而导致它们必须以一个不允许交叉执行的顺序执行, 称为互斥

信号量和PV原语

信号量sem是一个整数, 当sem大于零时, 表示并发进程可以使用的实体数量, 当sem小于零时, 表示正在等待使用临界资源的进程数
P原语操作主要动作如下
1. --sem
2. 若sem仍大于等于零, 则P原语返回, 该进程继续执行
3. 若sem小于零, 则该进程被阻塞后, 进入该信号量的等待队列, 然后转进程调度
V原语操作的主要动作如下
1. ++sem
2. 若sem仍大于零, 则V原语返回, 该进程继续执行
3. 多sem小于等于零, 则从该信号的等待队列中唤醒一个进程, 然后返回原进程执行或转入进程调度
遇到临界区的时候, 在临界区的两端分别加上P原语和V原语即可完成互斥操作

进程同步

建立两个互补的私有信号量, 通过交叉判断进行同步操作

S1()
{
	...
	P(empty)
	写入数据
	V(full)
	...
}

S2()
{
	...
	P(full)
	取出数据
	V(empty)
	...
}

其中Sa和Sb一个置为0,一个置为1
S1进程执行之前, 会先判断缓冲区是否为空, 确定为空后写入数据, 最后使用V原语唤醒可能等待的S2进程
S2进程执行之前, 会先判断缓冲区是否已满, 确定已满后取出数据, 最后使用V原语唤醒可能等待的S1进程

进程的一般模型

1.生产者-消费者模型

进程之间的资源申请和释放问题可以看作一个生产者-消费者问题, 使用资源的进程可以看为消费者, 而释放资源的进程可以看为生产者, 一般而言这些进程的代码具有如下的结构

deposit(data)
{
	P(avail)
	P(mutex)
	写入数据
	V(full)
	V(mutex)
}

remove(data)
{
	P(full)
	P(mutex)
	取出数据
	V(avail)
	V(mutex)
}

其中avail和full信号量是私有信号量, 用于两个不同进程的同步
mutex信号量是共有信号量, 用于各个进程之间的互斥
V原语因为是释放操作, 因此通常没有顺序要求
注意:要先执行同步P操作, 再进程互斥P操作, 从而确保互斥锁定之前, 获得执行机会的进程一定可以执行完毕, 避免进程死锁

2.读者-写者模型

有两组并发的进程：读者和写者, 其中要求任何时刻, 写者之间互斥, 读者与写者互斥, 读者之间可以同时读取

writer(data)
{
	P(w);
	写入数据
	V(w);
}


reader(data)
{
	P(R);
	++Rcount;
	if (Rcount == 1){
		P(w);
	}
	V(R);
	...
	读取数据
	...
	P(R);
	--Rcount;
	if(Rcount == 0){
		V(w);
	}
	V(R);
}

对于写者, 只要开始访问数据, 就可以直接锁定
对于读者, 只有第一个需要互斥写者, 只有最后一个需要释放锁定, 因此需要使用一个计数器
因为多个进程访问计数器, 因此计数器的读写需要锁定

3.哲学家吃饭模型

一共有5个哲学家, 每个哲学家之间有一个筷子
哲学家拿到两个筷子时才能开始进餐
当一个哲学家拿到一个筷子以后, 除非拿到另外一个筷子并完成进餐, 否在绝对不会放下手中的筷子
实际上, 进一步分析可知, 如果限制最大吃饭人数, 即限制最多4人同时吃饭, 则可以保证4人中, 至少有一人可以获得两个筷子, 从而完成吃饭

main()
{
	int chopstick[5] = {1};
	int count = 4;
	cobegin
		eat[0]();
		eat[1]();
		...
		eat[4]();
	coend
}


eat[i]()
{
	think;
	P(count);
	P(chopstick[i]);
	P(chopstick[(i+1) mod 5]);
	eat;
	V(chopstick[i]);
	V(chopstick[(i+1) mod 5]);
	V(count);
	think;
}

4.理发问题

有一个理发师, 一把理发椅和n把供等待客户坐的椅子
如果没有顾客, 理发师在理发椅上休息
当有一个顾客到来时, 唤醒理发师进行理发
当理发师在理发的时候, 如果有新顾客到来, 则判断等待区是否有空闲, 如果有则等待, 否在离开

main()
{
	int customers = 0;
	int barbers = 1;
	int wait = 0;

	cobegin
		Barber();
		Customer();
	coend
}

Barber()
{
	while()
	{
		P(customers);
		wait = wait - 1;
		理发;
		V(barbers);
	}
}

Customer()
{
	if(wait<n)
	{
		wait = wait + 1;
		V(customers);
		P(barbers);
		理发;
	}
	else
	{
		离开理发店;
	}
}

进程通信

直接通信
- 在发送和接受时, 都需要制定双方的标识
间接通信
- 借助共享的数据结构进行通信

进程间的通信方式

主从式
- 主进程可以自由的使用从进程的资源或数据
- 从进程的受到主进程的控制
- 实际上是一种控制关系
会话式
- 使用进程在使用服务进程提供的服务以前, 必须获得服务进程的同意
- 服务进程根据使用进程的要求提供服务, 但所提供的服务的控制由服务进程完成
- 实际上是一种调用关系
消息或邮箱机制
- 只要存在空缓冲区或邮箱, 发送进程就可以发送消息
- 发送进程和接受进程之间没有直接的联系
- 实际上是一种平等的关系
共享存储区方式
- 共享存储区不需要移动数据
- 两个进程通过对同一共享存储区进行操作实现互相通信
- 这个共享区是每个互相通信的进程的一个组成部分
文件共享方式
- 借助文件系统原有机制进行通信

消息的结构

发送进程名
接受进程名
数据
数据的相关操作

消息缓冲机制

在发送进程把消息写入缓冲区和把换从区挂入消息队列时, 应禁止其他进程对该缓冲区消息队列的访问
缓冲区中无消息存在时, 接受进程不能收到任何消息

Send(B,m)
{
	向系统申请一个缓冲区;
	P(mutex);
	将发送区消息m送入新申请的消息缓冲区;
	把消息缓冲区挂入接收进程的消息队列;
	V(mutex);
	V(SM);
}

Receive(A,n)
{
	P(SM);
	P(mutex);
	摘下消息队列中的消息n;
	将消息n冲缓冲区复制到接收区;
	释放缓冲区;
	V(mutex);
}

邮箱通信

邮箱由邮箱头和邮箱体组成, 邮箱头总包含相关的身份信息, 邮箱体中是需要传输的数据
两个进程之间是简单的同步问题, 按照同步问题加锁即可

线程

进程是资源的拥有者, 也是调度单位, 但是线程不拥有资源, 只是一个调度单位, 从而能更加方便的进行调度

死锁的必要条件

互斥条件：进程要求对所分配的资源进行排他性控制, 即在一段时间之内某资源仅为一一个进程占有
部分分配, 进程每次申请它所需要的一部分资源, 在等待新资源的时候, 不释放已经占有的资源
不剥夺条件：进程已经获得的资源, 在没有使用完毕之前, 不能被剥夺
环路条件, 存在进程链循环, 循环中每个进程已经获得的资源被下一个进程请求

死锁的排除方法

预防死锁：采取某种措施, 限制并发进程对资源的请求, 从而破坏产生死锁的必要条件中的一个或几个来防止死锁
- 互斥条件是设备的固有特性, 不仅不能改变, 而且还应该加以保护
- 摒弃”请求和保持”条件：资源预分配策略：运行前一次性分配给进程所有需要的资源
  - 优点：简单易行且安全
  - 缺点：资源浪费, 进程延时运行
- 摒弃”不可剥夺”条件
  - 缺点：实现复杂, 系统代价很高
- 摒弃”环路等待”条件：把系统资源按照类型排序, 进程要按照资源的序号递增的次序提出资源申请
  - 优点：比上述两种方法的综合性能要好
  - 缺点：限制了进程对资源的请求, 同时给系统中所有资源编号增加来系统开销
避免死锁：系统在分配资源时, 根据资源的使用情况预测是否会产生死锁
- 银行家算法
  1. 判断分配条件, 并尝试分配
  2. 分配后进行安全性检测, 如果安全则接受分配, 否则撤销分配
  3. 安全性检测即在当前分配完成后,是否存在方案可以使后续进程都能分配需要的资源并完成
- 银行家算法数据结构
  - Available m元素的数组,表示资源可用总数
  - Max[i,j] 进程i对资源j的最大使用量
  - Allocation[i,j] 进程i当前已经获得的资源j的数量
  - Need[i,j] 进程i还需要的资源j的数量
  - Request 当前请求分配的资源数组
- 安全性检测数据结构
  - Work m元素向量,表示当前可以分配的资源,初始值Word = Available
  - Finish n元素向量,表示任务是否可完成
死锁的检测和恢复
- 通过死锁检测算法检测系统中是否有死锁
- 通过中止进程, 强制剥夺资源等方法解除死锁

第四章处理机调度

调度层次

作业调度：宏观调度, 高级调度
- 按一定原则选择外存后备队列中的作业, 为其分配内存等资源, 并建立进程
- 在作业执行完毕后, 回收系统资源
交换调度：内外存交换, 中级调度
- 按给定的策略, 将外存中处于就绪状态或等待状态的进程调入内存, 或将内存中暂时不使用的进程调至外存
- 提高内存利用率和系统吞吐量
进程调度：微观调度, 低级调度
- 决定就绪队列中那个进程获得处理机
线程调度
- 可有OS内核完成, 也可由用户程序进行

作业的状态

提交状态
- 一个作业处于从输入设备进入外存的过程时处于的状态
后备状态
- 作业的全部内容都通过输入设备输入到外存输入井中, 等待进入内存
执行状态
- 作业一旦被作业调度程序选中, 则为其分配所需的资源, 并创建进程, 送入内存中投入运行
完成状态
- 作业运行完毕, 准备退出系统时的状态（所占用的资源尚未全部被系统回收）

面向用户的性能指标

周转时期
- 作业从提交到完成所用的时间
- 包括平均周转时间和平均带权周转时间
- 平均带权周转时间的权值为 1/运行时间
响应时间
- 用户发出命令(例如键盘按键)到系统给出响应的时间(例如屏幕输出字符)

面向系统的性能指标

吞吐量
设备利用率
设备均衡利用
公平性
优先级

调度算法的衡量

易于实现
运行开销小

进程调度功能

记录所有进程的执行情况（静态和动态）
按一定策略, 选择一个就绪进程
完成进程上下文切换

进程上下文切换步骤

检查是否可以进行进程切换
保存被切换进程现场
选择一个新进程
恢复被选中进程现场

引起进程调度的原因

正在执行的进程执行完毕, 或由于某种错误而中止
执行中的进程自己调用阻塞原语, 将自己阻塞进入等待
执行P原语
执行V原语, 激活
提出I/O请求后被阻塞
执行完系统调用后
分时系统中时间片到
一个高优先级的进程就绪（可抢占式系统）

进程调度方式

非抢占式
- 某一进程被调度后, 将一直执行到完成或者被阻塞
- 即是由于自身的原因而让出CPU
抢占式
- 由于优先权, 短作业优先或时间片到等原因, 系统强制剥夺正在执行的进程的CPU

进程调度性能衡量

定性衡量
1. 公平性
2. 可靠性
3. 简洁性
定量评价
1. CPU利用率
2. 响应时间
3. 吞吐量

调度算法

先来先服务
短作业优先
- 每次一个任务执行完毕后,从当前等待的队列中选择耗时最短的作业
最高响应比法
- 响应比 = 响应时间 / 运行时间
- 响应时间 = 作业等待时间+预计执行时间
- 响应比 = 1 + 作业等待时间 / 运行时间
- 每次一个任务执行完毕后,从当前等待队列中选择响应比最高的作业
时间片轮转法
- 所有作业排成一个FIFO队列
- 依次选择队首进程执行一个时间片,时间片到后回到队尾
- 在执行过程中,如果任务结束,可以提前结束时间片,开始下一个作业的调度
多级队列法
- 可以设置多个队列,每个队列可采取不同的调度算法
优先级算法
1. 静态优先级
  - 所有进程根据各种因素确定一个优先级,在执行过程中始终不变
2. 动态优先级
  - 在执行过程中动态改变优先级,从而获得更好的调度效果
  - 例如,等待时间越长,优先级越高
  - 例如,每执行一个时间片,降低一个优先级
多级反馈轮转法
- 设置多个队列,赋予不同优先级
- 优先级越低,时间片越长
- 新进入的进程首先进入优先级最高的等待队列
- 如果一个时间片内进程未能执行完毕,则降级到下一个优先级队列(直到最低一级)
- 高优先级队列为空是,才调度低优先级的进程

第五章存储管理

程序逻辑结构

程序地址:用户编程时使用的地址
程序地址空间:用户的程序地址集合,总是从0开始编制,但既可以是一维空间也可以是多维空间

逻辑地址,物理地址与地址映射

逻辑地址(相对地址,虚地址): 用户的程序编译后使用的地址,通常是相对地址,且假设首地址是0,并且相对此地址进行编址
物理地址(绝对地址,实地址): 内存中存储单元的地址
地址映射:将逻辑地址转化为物理地址

存储管理功能

存储分配与回收
地址变换
- 程序加载时的重定位技术
- 程序运行时的地址变换机构和技术
存储共享与保护
- 代码和数据的共享,提高内存利用率
- 限制在各自的内存区域内操作,互不干扰
存储器扩充方式
- 覆盖
- 交换
- 请求调入 / 预调入

重定位

在可执行文件装入时需要解决可执行文件中地址(包含指令和数据的地址)和内存地址的对应. 有三种重定位方式

绝对装入:编程或编译时确定绝对地址
静态地址重定位: 程序执行前,由装入程序完成地址映射,程序执行过程中,映射关系始终不变
动态地址重定位: 处理机执行程序时,由地址映射机构动态的完成地址映射

存储保护方法

界限保护(上界/下界寄存器或基址/限长寄存器)
- 所有访问都限定在指定的范围中,否在产生越界错误
- 由硬件判断是否允许访问,如果不允许则产生越界中断,有操作系统进行处理
访问方式保护(保护键)
- 对于允许多个进程共享的存储区域,每个进程都有自己的访问权限
- 如果一个进程对共享区域的访问违反了权限规定,则发生操作越权 (即读写保护)
- 为每一个被保护内存区域指定保护键和若干禁止的访问方式,同时进程指定保护键开关
- 如果访问时键值不匹配而且是被禁止的访问方式,则产生访问出错中断

虚拟存储器

为用户提供一种不受物理存储器结构和容量的限制的存储技术
使得用户编程时不需要考虑物理存储器的结构和容量
每个进程都有自己的虚存,且虚存大小不受物理存储器容量的限制

虚拟存储器物质基础

两级存储结构: 内存与外存储器
地址变化机构: 实现逻辑地址与物理地址的转化

虚拟存储器原理

程序运行时,不将全部的数据调入内存,只调入当前需要的部分
在程序执行过程中,如果需要访问的部分不再内存中,处理器通知操作系统将相应的程序或数据调入内存,然后继续执行
将内存中暂时不使用的数据移出内存,保存到外层,从而腾出内存空间

内外存数据传输控制

由应用程序控制
- 覆盖
由OS控制
- 交换(整个进程空间)
- 虚拟存储(部分进程空间)
  - 请求调入
  - 预调入

覆盖

一个程序的几个代码段或数据段按照时间先后占用公共的内存空间
用户负担大
程序段最大长度仍然受内存容量限制
不能实现虚拟存储器

交换

将暂时不能执行的程序送到外存,从而获得空闲内存空间装入新程序

虚拟存储

请求调入: 程序需要访问时,系统自动的从外存调入相关的内存段
预调入: 系统预测后续可能被访问的内存段,并提前调入

分区存储管理

把内存分为一些大小相等或不等的分区, 除了操作系统占用一个分区以外, 其余分区用来存放进程和程序和数据
适用于多道程序和简单的分时程序
难以进行内存分区共享
存在碎片
- 内碎片: 占用分区内难以利用的部分
- 外碎片: 占用分区之间难以利用的部分

分区分类

固定分区法: 系统初始化时固定的分区
- 分区大小不等
- 分区个数,大小不变
- 每个分区有一对界地址寄存器
- 采用静态重定位方式载入
- 实现简单,要求的硬件支持少,但内存利用率低
动态分区法: 在作业的处理过程中,按照需要分割
- 从可用表 /自由链中找到一个足够容纳该作业的可用空白块
- 如果空白块比需要的大,则将空白块一分为二,一部分是分配区,另一部分还是空白

空闲分区查找算法

最先适应法:按照内存地址由低向高依次查找
最佳适应法:从空白区间最小的开始查找
最坏适应法:从空白区间最大的开始查找

紧缩技术

将内存中占用的分区向一段移动,从而使空间分区聚集在另外一段
在分区释放或内存分配失败时执行此操作

页式存储管理

目标是解决分区管理内存利用率不高的问题
将逻辑空间分页和内存空间分块,页和块大小相等
当用户程序装入内存时,以页为单位装入
逻辑上连续的页可以装入物理上不连续的块中

地址映射方式

以2进制来看,低位部分是页类位移,高位即为页号

联想存储器

在页式存储技术中,每次都需要访问内存两次,严重影响系统效率(一次访问页表,一次访问内存)
因此使用联想存储器来加速查询速度
类似与Cache,但联想存储器和页表是并行查询

请求页式存储管理

纯页式管理提高了内存利用率,但还是不能为用户提供虚存
当用户程序页面数大于当前空闲内存块数时,系统还是不能装入此程序
用户程序依然受到物理内存大小限制
请求时页式存储管理技术的目标即解决上述问题

请求页式管理的区别

当用户程序要调入内存时,不是全部装入,而是只装入部分页
在程序运行过程中,如果发现需要访问的数据不在内存,则向系统发出缺页中断
系统将相应的页调入内存,程序继续运行

请求页式管理的数据结构变化

从调入角度,需要添加标志位,用于判断是否已经调入
从调出角度,需要添加标志位,用于判断最近是否访问,是否修改等
此外还需要记录有关数据在外存中的地址,以便以后续的调入

调度策略

预调入
请求调入

淘汰(置换)算法

随机淘汰法
- 随机选择一个页换出
轮转法和先进先出法
- 轮转法循环的换出内存中的某些块,这些块可能已经驻留很长时间,也可能刚刚调入
- 先进先出法每次淘汰内存中驻留时间最长的页
最近最久未使用算法
- 当淘汰一个页时,选择里当前时间最近的一段时间内,最长时间没有被使用的页
- 在表格中,向左寻找当前的项中最近一次出现的距离,选择距离最远的项淘汰
- 有两个近似算法
  1. 最不经常使用页面淘汰算法
    - 淘汰到淘汰时间为止,访问次数最少的那一页
    - 淘汰后,所有计数器清零,开始下一轮统计
  2. 最近没有使用页面淘汰算法
    - 淘汰当淘汰时间为止,没有被访问的也
    - 只用设置标志位,不用设置计数器
理想淘汰算法
- 淘汰以后不再使用或最长时间不再使用的页
- 在表格中,向右寻找当前项中最近一次出现的距离,选择距离最远的项淘汰
  注意: 第一次调入时也是缺页

Belady现象

使用FIFO算法时,在给进程分配内存块时,有时会出现分配的块越多,缺页次数反而增加的现象

页式管理优缺点

有效的解决了碎片问题
支持虚存
但是需要响应的硬件支持
增加了系统开销
如果调入算法不当,可能产生抖动
内碎片问题无法解决
不利于程序和数据共享

段式管理

一个程序按照其逻辑,分成若干段
每一段都从0开始编址
段长不固定,可根据需要动态增长
各段之间不需要连续

分页与分段的异同点

在内存中都不是整体连续,都使用地址映射机构进行转换
页时信息的物理单位,用户不需要处理. 段是信息的逻辑单位,分段可以更好的满足用户需求
页的大小是固定的,段的大小是可以变化的
分页的作业地址空间是一维的,分段的作业地址空间是二维的

段页式存储管理

结合分段的逻辑优势和分页的空间管理优势
将程序在逻辑上分段,在每段上分页
每段的页都从0开始依次变址
由此分段大小不再受内存可用区域的限制

第六章文件管理

文件

一段程序或数据的集合
一组赋名的相关联字符流的集合或相关联记录的集合

文件系统

负责为用户建立,撤销,读写,修改和复制文件
完成对文件的按名存取和存取控制

文件类型

按性质和用途分类
- 系统文件(可执行)
- 用户文件(可读可写可执行)
- 库文件(可读可执行)
按文件保护方式
- 只读文件
- 读写文件
- 可执行文件
- 不保护文件
按文件注释和处理方式
- 普通文件:一般的文本文件和二进制文件
- 目录文件:包含文件目录信息的文件,用于检索普通文件
- 特殊文件:输入输出设备可以看做特殊文件
按信息流
- 输入文件: 如读卡机或键盘,只能读入
- 输出文件: 如打印机,只能写出
- 输入/输出文件:如磁盘,既可读又可写
按文件的数据形式
- 源文件
- 目标文件
- 可执行文件

文件的组织结构

逻辑结构
- 字符流式无结构文件
- 记录式有结构文件

记录式结构文件种类

连续结构:把记录按照先后顺序排列
- 适用性强
- 排列顺序与内容无关(便于记录的追加)
- 搜索性能较差
多重结构:一个包含n个记录吗,m个键的文件构成一个mn的矩阵
- 如果矩阵i行j列值为1,则说明记录键k[i]在记录R[j]中
- 同一键可以同时属于不同的记录
- 以键k[i]为队首,以包含k[i]的记录为队列元素构成队列
- 此结构搜索效率高于连续结构,但必须先找到对应的键,并在其队列中顺序查找
转置结构:把含有相同键的记录指针全部指向该键
-把所有与同一键对应的记录的指针连续地置于目录中该键的位置下
顺序结构:把文件的键按照规定的顺序,如字母顺序排列
- 适合与按某种顺序来搜索,追加,删除记录

文件物理结构

顺序结构
- 把逻辑上连续的文件依次存放在连续的物理块上
- 结构简单,存取速度快
- 不能动态增长, 部分删除会有零头
链接结构
- 类似链表结构,每个块的末尾有指向下一块的指针
  -文件可以动态增长
- 不适合随机访问,一般只用于逻辑上连续且顺序访问的情景
索引结构
- 为每个文件建立一个索引表,从表中可以直接查询到指定块的物理块号(类似页表)
- 即可满足动态增长又可实现随机存取
- 使用索引表增加了存储空间开销,且需要至少访问两次存储器

索引表组织

连接模式:索引表占满一块就用指针链接下一块
多级索引:存放的不是索引,而是存索引块的地址
综合模式:索引表的头几项设置为直接寻址,后的设置为多重索引

磁盘调度算法

先到先服务
- 简单公平
- 效率不高,可能导致磁头反复移动
最短寻道时间优先
- 优先选择距离当前磁头最近的访问请求进行服务
- 改善了磁盘的平均服务时间
- 可能造成某些访问长时间得不到服务
扫描算法(电梯算法)
- 无访问时,磁头位置不动
- 有访问时,磁头按一个方向移动,依次处理经过的请求
- 如果到达边缘就转换方向

文件存储空间管理

空闲文件目录法: 所有空闲块记录在一个表中
- 适合仅有少量空白区域的情况
- 适合连续文件
空闲块链法: 所有块链接成一个链表
- 只需要一个头结点保存空闲区信息
- 效率低
成组链接法: 把文件存储设备的所有空闲块按组保存
- 例如见空闲块每50块分成一组
- 每组第一块存放前一组的总块数和各块块号,后面的块为空,作为空闲块等待分配
- 第一组只有49块,最后一组可能不足50块
- 将最后一组调入内存,并维持成栈结构
- 分配空间时,进行出栈操作,如果只剩下一块,就从此块中取出前一组地址,载入新的组,并将此块分配给请求进程
- 释放空间时,进行入栈操作,如果到达50块,就将所有块号存入,并清空栈,将栈的第一块链接到此组
位示图法: 使用一串二进制位反应空间分配情况

文件目录管理

文件组成
- 文件体: 文件本身的信息
- 文件说明(文件控制块FCB)
  - 存放为了管理文件所需要的信息
  - 包括文件名,起始物理位置,存取控制信息等
文件目录
- 单级目录
  - 系统为所有存入系统的文件建立一张表
  - 每个文件有一个表目
  - 各个文件处于平等地位
  - 简单且能够按名存取
  - 不允许重名,且文件多时,查找速度慢
- 二级目录
  - 主目录文件(MFD Main File Directory)
    - 存放不同组名的有关存取控制信息
    - 包括用户名,用户子目录所在文件物理地址等
  - 用户文件目录(UFD User File Directory)
    - 存放用户文件的文件说明
    - 即该用户的FCB
  - 文件名 <==> 用户名/文件名
  - 解决了文件重名和文件共享的问题
    - 由于有用户名,所以可以同名
    - 由于UFD可以指定地址,所以可以在物理层面是上共享文件
  - 不适合大量用户和大量文件的系统
- 多级目录结构
  - 产生于Unix系统,已被现代操作系统广泛采用
  - 多级目录中,处理最低一级的物理块总有文件信息,其他没记目录中都是存放下一级目录或文件说明信息
  - 通过路径名解决了重名问题
  - 查找速度快

文件共享

绕道法
- 要求用户处于当前目录下工作
- 所有的文件访问都是相对当前目录进行
- 当前目录一般存放在内存中
- 依次向上回溯到需要访问的节点与当前目录的公共节点,再从公共节点依次向下找到目标节点
- 效率低
链接法
- 将一个链接指针直接指向共享文件所在的目录
基本文件目录表
- 基本文件目录BFD(Basic File Directory)
  - 包括文件的结构信息,物理块号,存取控制等信息
  - 有系统赋予唯一的内部标识符来标识
  - 此目录以连续文件的形式存于卷头部,此长度决定了卷内最大文件数
- 符号文件目录SFD(Symbol File Directory)
  - 有用户给出文件名和文件内部标识符组成
  - 用于建立文件名和文件内部标识符对应关系

第七章设备管理

设备管理的任务

选择和分配IO设备以进行数据传输操作
控制IO设备和内存数据之间交换数据
为用户提供友好的透明接口
提高并行操作度

设备管理的功能

提供和进程管理系统的接口
进行设备分配
实现设备和设备,设备和CPU之间的并行操作
进行缓冲区的分配,释放以及相关的管理

数据传送控制方式

程序直接控制
- 由用户进程直接控制
- 控制简单,不需要硬件支持
- CPU和外围设备只能串行工作
- 无法发现和处理由于硬件产生的错误
中断方式
- CPU利用率大大提高
- 支持多道程序与设备并行操作
- 一次数据传输可能需要多次中断,会消耗大量CPU时间
- 可能造成CPU无法响应中断和出现数据丢失的问题
DMA方式
- 在外围设备和内存之间开辟直接的数据交换通路
- DMA通过挪用CPU的一个工作周期把数据送入内存
- 除了数据开始传送时需要CPU的启动指令,以及传送结束后CPU进行中断处理以外,不再需要CPU频繁干预
- CPU中断处理次数大大减少
- 排除了数据丢失的问题
- 由于MDA方式对外围设备的某些操作还是需要CPU控制,且配备多个DMA是不经济的,因此DMA方式也存在一定的局限性
通道方式
- 一个独立于CPU的专门负责I/O控制的处理机
- 有自己的指令系统,通道指令受CPU启动,并在操作结束后向CPU发出中断信号
- 与DMA方式的区别
  - DMA方式中,数据的传输有CPU控制,通道中有专门的硬件控制
  - DMA方式中,每台设备至少一个DMA控制器,通道中一个通道可以控制多态设备与内存进行数据交换

缓冲技术

引入缓冲的目的
- 缓和CPU和I/O设备间速度不匹配的矛盾
- 减少CPU中断次数
- 解决DMA或或通道方式时的瓶颈问题
缓冲区种类
- 按照缓冲器个数
  - 单缓冲
    - CPU与外设之间只设立一个缓冲区
    - 共用资源需要互斥使用
  - 双缓冲
    - 设置两个缓冲区
    - 实际很少使用此方案
  - 多缓冲/缓冲池
    - 把主存的多个缓冲区分为两个部分
    - 输入缓冲区和输出缓冲区
    - 每个缓冲区依然是临界资源,必须互斥使用
- 按照I/O控制
  - 专用硬件
  - 软件缓冲
缓冲区管理
1. 用于收容输入数据的工作缓冲区(hin): 输入设备-> 缓冲区
2. 用于提取输入数据的工作缓冲区(sin): 缓冲区->CPU
3. 用于收容输出数据的工作缓冲区(hout): CPU->缓冲区
4. 用于提取输出数据的工作缓冲区(sout): 缓冲区->输出设备

设备分配技术

数据结构
1. 系统设备表SDT(System Device Table)
  - 记录所有I/O设备信息
  - 包括设备类型,设备标识符,进程标识符,DCT指针等
2. 设备控制表DCT(Device Control Table)
  - 系统中的每台设备都有一张设备控制表
  - 记录设备各方面特征,以及与设备相联的设备控制器入口位置
3. 设备控制器表COCT(COntroller Control Table)
  - 每个控制器有一张控制器控制表
  - 包含控制器号,控制器状态,通道指针等
4. 通道控制表CHCT(CHannel Control Table)
  - 每个通道都有一张通道控制表
  - 包括通道号,通道状态,等待队列指针等
设备分配方式
1. 静态分配
  - 在作业执行前,由系统一次性分配给该作业所需的全部设备,控制器和通道
  - 在作业进行过程中,不再改变
  - 不会死锁
  - 设备利用率低
  - 适用于独占型的设备
2. 动态分配
  - 在进行需要设备时,通过系统调用项系统提出请求,一旦使用个完毕,立即释放
  - 提高了设备利用率
  - 分配不当会引起死锁
  - 适用于共享型的设备
设备独立性
- 指应用程序独立于具体使用的物理设备
- 用户编制程序使用的设备与实际使用的设备无关
设备分配策略
- 先请求先分配
- 优先级高者先分配
设备分配顺序
1. 分配设备
2. 分配控制器
3. 分配通道
虚拟设备和假脱机技术
1. 虚拟设备
  - 虚拟设备是指代替独享设备的那部分存储空间以及有关的控制结构
2. SPOOLING系统(Simultaneous Peripheral
  Operation On Line)
  - 同时联机的外围操作或假脱机操作
  - 利用一台高速共享设备,将一台独享设备模拟成多台可并行操作的虚拟设备
  - 提高了I/O速度
  - 设备并没有分配给任何进程
  - 实现了虚拟设备功能

I/O进程控制

从用户进程的I/O请求开始,给用户进程分配设备,启动有关设备进行I/O操作,以及在I/O在I/O操作之后响应中断,进行善后处理为止的整个系统控制过程
模块功能说明
- I/O请求处理模块
  - 将用户进程的I/O请求变换为设备管理程序所能接受的信息,并将I/O请求命令插入指向的相应DCT的I/O请求队列
- 设备分配程序
  - 为I/O请求分配相应的设备,控制器和通道
- 缓冲区管理模块
  为I/O传送申请必要的缓冲区,以及保证I/O传送的顺利完成
- 中断处理
  - 数据传输结束后,外设发出中断请求,I/O控制过程根据中断原因调用中断处理程序,并作出中断响应
I/O控制的实现方式
- 作为请求I/O操作的进程的一部分实现
- 作为当前进程的一部分实现
  - 当前进程处理中断
  - 剩余部分有I/O进程控制
- 作为专门的系统进程
  - 由系统进行I/O调度
I/O进程的实现方式
- 每个设备设置一个专门的I/O进程
  - 该进程只能在系统态下执行
- 整个系统设置一个I/O进程
- 每类设备设置一个I/O进程
  - 该进程既可在系统态也可在用户态执行

设备驱动程序

是驱动物理设备和DMA控制器或I/O控制器等直接进行I/O操作的子程序的集合
设备驱动程序负责设置相应设备有关寄存器的值,启动设备进行I/O操作,指定操作的类型和数据流向等
设备开关表(Device Switch Table, DST)对驱动程序进行管理
- 给出相应设备的各种操作子程序的入口地址
- 一般是二维的,行和列分别是设备类型和驱动程序类型
- 设备开关表也是I/O进程的一个数据结构

最后更新： 2024年04月18日 13:26

原始链接： https://lizec.top/2017/09/23/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%E7%AC%94%E8%AE%B0/

第一章 绪论