《操作系统》读书笔记
2021-07-21 12:17:55 0 举报AI智能生成
考研408操作系统知识框架
作者其他创作
大纲/内容
文件管理
I/O管理
计算机系统概述
进程管理
进程与线程
进程：资源分配的基本单位
一个进程是程序在一个数据集上的一次运行过程
一个进程是程序在一个数据集上的一次运行过程
进程映像(进程实体)
进程控制块PCB(Process Control Block)
PCB是进程存在的唯一标志，PCB常驻内存
进程的创建撤销==PCB的创建和撤销
包含进程标志信息、进程控制信息、进程资源信息、CPU 现场信息四大类
PCB是进程存在的唯一标志，PCB常驻内存
进程的创建撤销==PCB的创建和撤销
包含进程标志信息、进程控制信息、进程资源信息、CPU 现场信息四大类
程序段
被调度到CPU执行的程序代码段
程序段可被多进程共享，包含二进制代码、常量等
被调度到CPU执行的程序代码段
程序段可被多进程共享，包含二进制代码、常量等
数据段
数据堆段：动态分配的存储区
数据栈段：临时变量
数据堆段：动态分配的存储区
数据栈段：临时变量
特性：
动态性：
动态性是进程最基本的特征。
动态性是进程最基本的特征。
并发性：
独立性：
独立获得资源、接受调度的基本单位
独立获得资源、接受调度的基本单位
异步性：
各进程以不可预知的速度向前推进，可能导致运行结果的不确定性
各进程以不可预知的速度向前推进，可能导致运行结果的不确定性
结构性：
进程的状态与转换
子主题
进程控制：(原语实现)
实现进程状态的转换
实现进程状态的转换
进程的创建
创建子进程时为其分配虚拟地址空间(不能共享)
创建子进程时为其分配虚拟地址空间(不能共享)
进程的终止
进程的阻塞和唤醒(成对出现)
进程的切换
进程通信方式：进程之间的信息交换
∵进程的内存地址空间是私有的，相互独立的
∵进程的内存地址空间是私有的，相互独立的
高级通信方式
高效率传输大量数据
高效率传输大量数据
共享存储(共享内存区域)
通信进程自己负责互斥访问
通信进程自己负责互斥访问
基于数据结构的共享(低级方式，效率低)
基于存储区的共享(高级方式，效率高)
消息传递(中间实体)
系统提供发送/接收原语
系统提供发送/接收原语
直接通信方式
直接发给接收进程，并挂载其消息缓冲队列上
直接发给接收进程，并挂载其消息缓冲队列上
间接通信方式(信箱通信方式)
管道通信(字符流)
用于连接两个进程
用于连接两个进程
半双工通信
全双工=>定义两个管道
全双工=>定义两个管道
允许多个写进程，多个读进程
管道实际上是一个固定大小的内存缓冲区(通常为内存上的一页)
是Linux中使用非常频繁的通信机制
是Linux中使用非常频繁的通信机制
低级通信方式(PV操作)
线程：资源调度的基本单位
同一进程的线程共享进程地址空间
同一进程的线程共享进程地址空间
引入目的：
减小程序并发执行时的时空开销，提高OS的并发性能
减小程序并发执行时的时空开销，提高OS的并发性能
实现方式
用户级线程
ULT(User_level Thread)
ULT(User_level Thread)
线程管理由应用程序完成，内核意识不到线程的存在
优缺点：
*线程切换不需要变态，开销小效率高
*并发度不高(单线程)。不可在多核处理机上运行
*线程切换不需要变态，开销小效率高
*并发度不高(单线程)。不可在多核处理机上运行
内核级线程
KLT(Kernel_level Thread)
KLT(Kernel_level Thread)
线程管理(调度、切换)由OS内核完成，故需要变态
优缺点：
*并发能力强(多线程)，可在多核处理机上并行执行
*线程切换由内核完成，需要变态，成本高开销大
*并发能力强(多线程)，可在多核处理机上并行执行
*线程切换由内核完成，需要变态，成本高开销大
多线程模型
多对一模型
一对一模型
多对多模型(n≥m)
结合了上面两种的优点，既能提高并发性，又减小了系统开销
结合了上面两种的优点，既能提高并发性，又减小了系统开销
处理机调度
调度的概念：
调度的层次
高级调度(作业调度)
从辅存中选择作业调入内存，每个作业只调入、调出一次
从辅存中选择作业调入内存，每个作业只调入、调出一次
中级调度(内存调度)
按照某种策略将进程调入调出内存
按照某种策略将进程调入调出内存
低级调度(进程调度)
按照某种策略选取就绪进程分配处理机，最基本的调度(高频)
按照某种策略选取就绪进程分配处理机，最基本的调度(高频)
调度的时机、切换、过程、方式
可以切换的情况
发生引起调度的条件且当前进程无法继续进行
中断处理结束或自陷处理结束
不能切换的情况
处理中断的过程中
进程在OS内核程序临界区(如就绪队列访问)中
普通临界区如打印机资源可以进行调度与切换
普通临界区如打印机资源可以进行调度与切换
原子操作(原语)过程中
切换过程：
1.对原进程运行环境的保存
2.对进程运行环境的恢复
1.对原进程运行环境的保存
2.对进程运行环境的恢复
重要结论：
进程的调度、切换是有代价的，并不是调度越频繁，并发度越高
进程的调度、切换是有代价的，并不是调度越频繁，并发度越高
调度算法的评价指标
CPU利用率
系统吞吐量
周转时间
=作业完成时间-作业提交时间
=作业完成时间-作业提交时间
平均周转时间
带权周转时间(≥1)
平均带权周转时间
等待时间
进程处于等待处理机状态的时间之和
进程处于等待处理机状态的时间之和
响应时间
=首次响应时刻-提交请求时刻
=首次响应时刻-提交请求时刻
典型的调度算法
先来先服务(FCFS)
非抢占式，对长作业有利，对短作业不利
有利于CPU繁忙型作业，不利于I/O繁忙型作业
不会导致饥饿，前面的作业总会处理完
短作业优先(SJF)
非抢占式，对长作业不利，可能导致"饥饿"、"饿死"现象
不能保证紧迫作业即时处理
"平均等待时间、平均周转时间最少"
抢占式SJF：最短剩余时间优先(SRTN)
高响应比优先(HRRN)
响应比
调度时选取响应比最高的就绪进程上处理机运行
非抢占式，不会导致"饥饿"现象
时间片轮转(RR)
轮流让排在就绪队列队头的进程执行一个时间片
抢占式、用于进程调度、不会导致"饥饿"现象
若进程执行完，时间片未用完，进程会主动放弃CPU
优先级调度算法
发生调度时选择最高优先级的作业/进程，
用于作业调度、进程调度，存在"饥饿"现象
用于作业调度、进程调度，存在"饥饿"现象
非抢占式：
当前进程放弃处理机时发生调度，选择就绪队列中优先级最高的进程
抢占式：
当前进程放弃处理机或就绪队列发生变化时检查是否需要调度
当前进程放弃处理机时发生调度，选择就绪队列中优先级最高的进程
抢占式：
当前进程放弃处理机或就绪队列发生变化时检查是否需要调度
静态优先级：创建进程时确定
动态优先级：进程运行过程中动态变化
动态优先级：进程运行过程中动态变化
优先级设置：
系统进程>用户进程、前台进程>后台进程、I/O繁忙型进程>CPU繁忙型进程
系统进程>用户进程、前台进程>后台进程、I/O繁忙型进程>CPU繁忙型进程
多级反馈队列调度算法
抢占式、存在"饥饿"现象
进程同步与互斥
临界资源
定义：一次仅允许一个进程使用的资源
临界资源的访问过程：
进入区：检查可否进入临界区，若是则设置访问标志
临界区(临界段)：进程中访问临界资源的代码段
退出区：清除临界区的访问标志
剩余区：代码中的其余部分
进入区：检查可否进入临界区，若是则设置访问标志
临界区(临界段)：进程中访问临界资源的代码段
退出区：清除临界区的访问标志
剩余区：代码中的其余部分
互斥原则
空闲让进：临界区空闲时允许一个进程访问
忙则等待：临界区正在被访问时，其他要访问的进程需要等待
有限等待：要在有限的时间内进入临界区，保证不会"饥饿"
让权等待：等待进入临界区的进程要释放处理机，防止"忙等"
临界区互斥的基本方法
软件实现方法
单标志法
算法思想：进程在访问完临界区后会把turn值设置为另一个进程的编号
缺点：两个进程需要交替进入临界区，若只有一个进程则无法访问(违背"空闲让进")
双标志法先检查
算法思想：用bool型数组flag[]来标记各进程想进入临界区的意愿(flag[0]=true表示P0进程想要进入临界区)
Pi进程进入临界区之前先检查其他进程的进入意愿，若没有则设置flag[i]=true并开始访问临界区
Pi进程进入临界区之前先检查其他进程的进入意愿，若没有则设置flag[i]=true并开始访问临界区
优缺点：
*不用交替进入，可连续使用
*并发运行时可能出现多个进程同时访问临界区的情况(违背"忙则等待")，因为检查和上锁不能同时进行
*不用交替进入，可连续使用
*并发运行时可能出现多个进程同时访问临界区的情况(违背"忙则等待")，因为检查和上锁不能同时进行
双标志法后检查
算法思想：先"上锁"，后"检查"
优缺点：
*解决了"忙则等待"的问题
*违背了"空闲让进"，"有限等待"原则，存在"饥饿"现象
*解决了"忙则等待"的问题
*违背了"空闲让进"，"有限等待"原则，存在"饥饿"现象
Peterson算法
算法思想：双方都想进入临界区，"孔融让梨"
优缺点：
*综合单标志、双标志的优点，遵循"空闲让进"，"忙则等待"，"有限等待"
*未解决"让权等待"的问题
*综合单标志、双标志的优点，遵循"空闲让进"，"忙则等待"，"有限等待"
*未解决"让权等待"的问题
硬件实现方法
中断屏蔽方法
利用"开/关中断指令"实现，关中断后当前进程不会被中断
优缺点
*简单、高效
*关中断对处理机生效，不适用于多处理机
*只适用于OS内核进程，不适用用户进程(因为开/关中断指令只能运行在内核态)
*简单、高效
*关中断对处理机生效，不适用于多处理机
*只适用于OS内核进程，不适用用户进程(因为开/关中断指令只能运行在内核态)
TestAndSet(TS指令/TSL指令)
TSL指令通过硬件实现，同时执行"检查"和"上锁"操作，执行过程不可被中断
优缺点：
*实现简单，适用于多处理机环境
*不满足"让权等待"原则，存在"忙等"现象
*实现简单，适用于多处理机环境
*不满足"让权等待"原则，存在"忙等"现象
Swap指令(XCHG指令)
信号量机制
整型信号量
用一个整数型变量作为信号量，用来表示系统中某种资源的数量
对信号量的操作只有三种：初始化、P操作、V操作
不满足"让权等待"，存在"忙等"现象
※记录型信号量
P操作：S.value--，之后如果value<0说明资源分完了，
则执行block原语自我阻塞(运行态->阻塞态)，主动放弃处理机并加入S.L中
遵循"让权等待"原则，不会出现"忙等"现象
则执行block原语自我阻塞(运行态->阻塞态)，主动放弃处理机并加入S.L中
遵循"让权等待"原则，不会出现"忙等"现象
V操作：S.value++,之后如果value≤0说明S.L不为空，
则执行wakeup原语唤醒S.L中的队首进程(阻塞态->就绪态)
则执行wakeup原语唤醒S.L中的队首进程(阻塞态->就绪态)
信号量机制实现进程同步
设置同步信号量，初值为0
开始没有S资源，只能由P1产生，P2才能使用
技巧口诀：前V后P
技巧口诀：前V后P
信号量机制实现进程互斥
设置互斥信号量，初值为1
1.临界区前对信号量执行P操作
2.临界区后对信号量执行V操作
2.临界区后对信号量执行V操作
※利用信号量实现前驱关系
(多级同步问题)
(多级同步问题)
画前驱图，把每个前驱关系看成一个同步问题
为每对前驱关系设置同步信号量，初值为0
前V后P
管程(解决信号量机制
编程麻烦、易出错的问题)
编程麻烦、易出错的问题)
定义：管程定义了一个数据结构和能为并发进程所执行的一组操作，这组操作能同步进程和改变管程中的数据
组成：
1.管程的名称
2.局部于管程的共享结构数据说明
3.对该数据结构进行操作的一组过程
4.对管程内的共享数据设置初始值的语句
1.管程的名称
2.局部于管程的共享结构数据说明
3.对该数据结构进行操作的一组过程
4.对管程内的共享数据设置初始值的语句
基本特征：
1.管程内的数据只能被管程内的过程所访问
2.一个进程只有通过调用管程内的过程才能进入管程访问共享数据
3.每次仅允许一个进程在管程内执行某个内部过程
1.管程内的数据只能被管程内的过程所访问
2.一个进程只有通过调用管程内的过程才能进入管程访问共享数据
3.每次仅允许一个进程在管程内执行某个内部过程
经典同步问题
生产者—消费者问题
子主题
子主题
死锁
定义：多个进程因竞争资源而造成的一种循环等待现象，若无外力作用，这些进程都无法向前推进
- 对不可剥夺资源的分配不合理时，可能导致死锁
- 每种资源只有一个并且出现了环路一定会死锁(死锁的充分条件)
- 对不可剥夺资源的分配不合理时，可能导致死锁
- 每种资源只有一个并且出现了环路一定会死锁(死锁的充分条件)
死锁产生的必要条件
互斥条件：对必须互斥使用的资源的争抢才会导致死锁
不可剥夺条件：进程所获得的资源在未使用完之前不可被剥夺，只能主动释放
请求和保持条件：进程已经保持了至少一个资源，但又请求其他进程占有的资源，
此时请求进程被阻塞，但又对保持的资源不释放
此时请求进程被阻塞，但又对保持的资源不释放
循环等待条件：存在一种进程资源的循环等待链，链中每个进程保持的资源被下一个进程所请求
注：循环等待未必死锁，死锁一定有循环等待
注：循环等待未必死锁，死锁一定有循环等待
死锁的处理
不允许死锁发生
静态策略：预防死锁
确保系统不会发生死锁
确保系统不会发生死锁
破坏互斥条件—SPOOLing技术
破坏不可剥夺条件
—申请失败立即释放所有资源
—由OS协助剥夺资源(考虑优先级)
—申请失败立即释放所有资源
—由OS协助剥夺资源(考虑优先级)
破坏请求和保持条件—静态分配法
破坏循环等待条件—顺序资源分配法
动态策略：避免死锁(银行家算法)
银行家算法步骤：
1.检查此次申请是否超过了该进程声明的最大需求
2.检查可用资源能否满足申请资源
3.试探分配资源并修改各数据结构
4.执行安全性算法检查是否导致系统进入不安全状态
注：系统处于不安全状态未必死锁，但死锁一定处于不安全状态，安全状态一定不会死锁
1.检查此次申请是否超过了该进程声明的最大需求
2.检查可用资源能否满足申请资源
3.试探分配资源并修改各数据结构
4.执行安全性算法检查是否导致系统进入不安全状态
注：系统处于不安全状态未必死锁，但死锁一定处于不安全状态，安全状态一定不会死锁
安全性算法步骤：
检查剩余资源是否满足某一进程的最大需求，
若可以，释放该进程保持的所有资源并加入安全序列
不断重复上述过程，直到所有进程加入安全序列或出现死锁
检查剩余资源是否满足某一进程的最大需求，
若可以，释放该进程保持的所有资源并加入安全序列
不断重复上述过程，直到所有进程加入安全序列或出现死锁
允许死锁发生
死锁的检测和解除
死锁的检测
数据结构：资源分配图
两种节点
进程节点(圆圈节点)
资源节点(矩形框表示资源，其中的圆点表示资源的数目)
两种边
进程节点—>资源节点(请求边)
资源节点—>进程节点(分配边)
死锁的检测算法
消除非阻塞进程节点相连的边，直到成为孤立节点
死锁定理：若资源分配图是不可完全简化的，说明发生了死锁
死锁的解除
资源剥夺法：
挂起某些死锁进程，抢占它们的资源并分配给其他死锁进程
挂起某些死锁进程，抢占它们的资源并分配给其他死锁进程
撤销进程法(终止进程法)：
强制撤销部分或全部死锁进程并剥夺资源
强制撤销部分或全部死锁进程并剥夺资源
进程回退法
内存管理
3.1内存管理的概念
从写程序到程序运行
编译：由编译程序把用户源代码编译成
若干个目标模块(把高级语言翻译成机器语言)
若干个目标模块(把高级语言翻译成机器语言)
链接：由链接程序将目标模块及所需
库函数链接，形成一个完整的装入模块
库函数链接，形成一个完整的装入模块
静态链接：
装入前链接成一个完整的装入模块
装入前链接成一个完整的装入模块
装入时动态链接：
运行前边装入边链接
运行前边装入边链接
运行时动态链接：
运行时需要目标模块才装入并链接
运行时需要目标模块才装入并链接
装入(装载)：
由装入程序将装入模块装入内存运行
由装入程序将装入模块装入内存运行
绝对装入
概念：编译程序直接产生绝对地址的目标代码，
装入程序按照装入模块中的地址装入内存
装入程序按照装入模块中的地址装入内存
缺点：只适用于单道程序环境
静态重定位(可重定位装入)
概念：编译、链接后的装入模块的地址都是从0开始的逻辑地址，
装入时对地址进行"重定位"，将逻辑地址转变为物理地址
装入时对地址进行"重定位"，将逻辑地址转变为物理地址
特点：
1.作业装入时一次性分配所需全部内存空间，否则不能装入
2.装入后，运行期间不能移动，也不能申请内存空间
1.作业装入时一次性分配所需全部内存空间，否则不能装入
2.装入后，运行期间不能移动，也不能申请内存空间
动态重定位(动态运行时装入)
概念：编译、链接后的装入模块的地址都是从0开始的逻辑地址，但地址转换是在
程序要执行时才进行，需要一个重定位寄存器(存放程序的起始地址)的支持
程序要执行时才进行，需要一个重定位寄存器(存放程序的起始地址)的支持
特点：
允许程序在运行中发生移动
允许程序在运行中发生移动
内存管理
内存空间的分配与回收
内存的扩充(实现虚拟性)
覆盖技术：解决"程序大小
超过物理内存总和"的问题
超过物理内存总和"的问题
思想：将程序分为多个段(模块)。常用段常驻内存，不常用段需要时调入内存
固定区和覆盖区
固定区(一个)
存放最活跃的程序段
固定区中的程序段在运行过程中不会被调入调出
覆盖区(若干个)
不可能被同时访问的程序段共享一个覆盖区
运行过程中根据需要调入调出程序段
必须由程序员声明覆盖结构，OS完成自动覆盖
缺点：对用户不透明，增加了用户编程负担
交换技术
思想：内存紧张时换出某些进程以腾出内存空间，再换入某些进程
磁盘分为文件区和对换区，换出的进程放在对换区
虚拟存储技术
地址转换：OS负责实现
逻辑地址到物理地址的转换
逻辑地址到物理地址的转换
存储保护：保证各进程在自己的
内存空间内运行，不会越界访问
内存空间内运行，不会越界访问
方法一：在CPU中设置一对上下限寄存器，存放进程的上、下限地址。
进程指令要访问某个地址时检查是否越界
进程指令要访问某个地址时检查是否越界
方法二：利用重定位寄存器(基址寄存器)、界地址寄存器(限长寄存器)进行判断
死锁解除进程选择
0 条评论
下一页
