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