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