2022年操作系统知识 .pdf

《2022年操作系统知识 .pdf》由会员分享，可在线阅读，更多相关《2022年操作系统知识 .pdf（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第 3 章 操作系统知识1、进程3-111 进程的三态图（熟练）就绪状态：进程已得到运行所需资源，只等待CPU的调度便可运行。运行状态：进程已得到运行所需资源，并且得到了CPU的调度等待状态：不具备运行条件、等待时机状态。另：等待状态也称阻塞状态。进程的五态图（了解）挂起（资源由内存到外存）恢复或激活（资源由外存到内存）Eg：下列 8 个叙述中，正确的是： （）1） 唤醒：挂起 -就绪2） 封锁：就绪 -挂起/ 激活或恢复3） 调度：就绪 -运行4） 超时：运行 -挂起/ 5） 超时：运行 -就绪/ 时间片到（超时） ，或被更高优先级进程剥夺6） 用户进程可激发调度进程/ 由操作系统系统进程控

2、制7） 用户进程可激发唤醒进程/ 8） 用户进程可激发超时进程/ 由操作系统系统进程控制进程死锁：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 19 页 - - - - - - - - - 进程管理是操作系统的核心，但如果设计不当，就会出现死锁的问题。如果一个进程在等待一个不可能发生的事， 则进程就死锁了。 而如果一个或多个进程产生死锁，就会造成系统死锁。Eg: 系统中有 3 个进程： A、 B、C。这三个进程都需要5 个系统资源。如果系统有 13 个资源，则不可能发生

3、死锁。如果系统有12 个资源，就有可能发生死锁。死锁发生的必要条件：1） 互斥条件：即一个资源每次只能被一个进程使用，在操作系统中这是真实存在的情况。2） 保持和等待条件：有一个进程已获得了一些资源，但因请求其他资源被阻塞时，对已获得的资源保持不变。3） 不剥夺条件： 有些系统资源是不可剥夺的，当某个进程已获得这种资源后，系统不能强行收回，只能有进程使用完时自己释放。4） 环路等待条件：若干个进程形成环形链，每个都占用对方要申请的下一个资源。解决死锁的策略：1） 死锁预防：例如：要求用户申请资源时一起申请所需的全部资源，这就破坏了保持和等待条件；将资源分层，得到上一层资源后，才能申请下一层资源

4、，它破坏了环路等待条件。预防通常会降低系统的效率。2） 死锁避免：避免是指进程在每次申请资源时判断这些操作是否安全，典型算法是“银行家算法” 。但这种算法会增加系统的开销。3） 死锁检测 * ：前两者是事前措施，而死锁的检测则是判断系统是否处于死锁状态，如果是，则执行死锁解除策略。4） 死锁解除 * ：这是与死锁检测结合使用的，它使用的方式就是剥夺。即将资源强行分配给别的进程。Eg：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 19 页 - - - - - - - -

5、- 选 B 首先求剩下的资源数：R1=9-(1+2+2+1+1)=2 R2=8-(2+1+1+2+1)=1 R3=5-(1+1+3)=0 前趋图：前趋图是一个 有向无环图 ， 记为为 DAG，用于描述进程之间执行的前后关系。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 19 页 - - - - - - - - - 图中的每个节点都用于描述一个程序段或进程，乃至一条语句； 节点间的有向边则用于表示两个节点之间存在的偏序或前趋关系“ -” 。如果 Pi 必须在 Pj 之前完

6、成，可写成PiPj，称 Pi 是 Pj 的直接前驱，而称Pi是 Pj 的直接后继。在前驱图中，把没有前驱的节点称为初始节点 ，把没有后继的节点称为 终止节点 。Eg：若有运算式： S=A + B*3/X + X*9 ，要求画出此运算过程的前驱图。S1:Z1= B*3 S2:Z2=X*9 S3:Z3=Z1/X S4:Z4=A+Z3 S5:S=Z4+Z2 Eg: 若每执行一条指令都要分：取值，分析，执行三部分。如下图所示，则如何用前驱图来表示此流水线的执行？流水线的前驱图：进程-PV操作 （同步、互斥） （必考）生产者与消费者（producer-consumer）问题是一个著名的进程同步问题。它描

7、名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 19 页 - - - - - - - - - 述的是：有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有N个缓冲区的缓冲池，生产者进程将它所生产的产品放入一个缓冲区中；消 费 者进程可从一个缓冲区中取走产品去消费。尽管所有的生产者进程必须保持同步， 即不允许消费者进程到一个空缓冲区去取产品； 也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投

8、放产品。临界资源：诸进程间需要互斥方式对其进行共享的资源，如打印机、磁带机等。临界区：每个进程中访问临界资源的那段代码称为临界区。在操作系统中， 进程之间经常存在互斥（都需要共享独占资源时）和同步（完成异步的两个进程的协作）两种关系。信号量： S是一种特殊的变量。表示资源的有无P操作：也称down()、wait() 操作，使 S=S-1 ，若 S0 ，进程暂停执行，放入信号量等待队列。V 操作：也称up()、signal()操作，是 S=S+1 ，若 S=0 ，唤醒等待队列中的一个进程。单缓冲区生产者、消费者问题PV原语描述：S1初值为 1（缓冲池有空间，即有资源），S2初值为 0（缓冲池无货

9、物，即无资源）生产者：消费者：生产一个产品；P（S2） ； / (S2-1)=0 P（S1） ； /（S1-1）=0从缓冲区取走产品；送产品到缓冲区；V（S1） / (S1+1)=1 V（S2） ； / (S2+1)=1 消费产品；多缓冲区生产者、消费者问题PV原语描述：S1初值为 1（缓冲池有空间，即有资源），S2初值为 0（缓冲池无货物，即无资源）Mute 初值为 1（缓冲资源是否被占用）生产者：消费者：生产一个产品；P（S2） ； / (S2-1)=0 P（S1） ； /（S1-1）=0P（mute ）P（mute）/ (mute-1)=0 从缓冲区取走产品；送产品到缓冲区；V（mute

10、 ）; V（mute ）/(mute+1)=1 V（S1） / (S1+1)=1 V（S2） ； / (S2+1)=1 消费产品；Eg: 设公交车上司机的活动是启动车辆，正常行车， 到站停车； 售票员的活动是关车门，售票，开车门，用信号量和P-V操作来实现它们的同步。S1=0 （是否允许司机启动汽车）S2=0 （表示是否允许售票员开车门）(先执行 )司机：售票员 : P（S1） / S1-1=0 关车门启动车辆V（S1） / S1+1=1 允许开车正常行驶售票到站停车P（S2） / S2-1=0 允许开门名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - -

11、- - - - - - 名师精心整理 - - - - - - - 第 5 页，共 19 页 - - - - - - - - - V（S2）开车门上下客读者写者问题：有两组并发进程：读者和写者，共享一组数据区。要求：允许多个读者同时执行读操作；不允许读者、写者同时操作；不允许多个写者同时操作；如果读者来：1） 无读者、写者，新读者可以读2） 有写者等， 但有其他读者正在读，则新读者也可以读 （可能产生问题）3） 有写者写，新读者等如果写者来：1） 无读者，新写者可以写2） 有读者，新写者等待3） 有其他写者，新写者等待PV原语描述：读者：写者：while(true) while(true) P(

12、mute); readcount+; If(readcount=1) P(w); P(w); 写；V(mute); V(w); / 读; P(mute); readcount-; If(readcount=0) V(w); /可写V(mute); 管程：管程是指关于共享资源的数据及在其上操作的一组过程或共享数据结构及其规定的所有操作。采用 P-V同步机制摆编写并发程序，对于共享变量及信号量变量的操作将被分散与各个进程中。缺点：1） 易读性差，2） 不利于修改和维护；3） 正确性难以保证；2、存储程序的装入（重定位）1） 静态重定位： 静态重定位是在虚空间程序执行之前有装配程序完成地址映射工作。

13、名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 19 页 - - - - - - - - - 2） 动态重定位：动态重定位是指程序执行过程中，在CPU 访问内存之前，将要访问的程序或数据地址转换为内存地址。存储实存管理存储管理的任务是存储空间的分配与回收。在现代的操作系统中通常有单一连续分配、固定分区分配、可变分区分配三种分配方法：分配方法单一连续分配固定分区分配可变分区分配分配类型静态分配法静态分配法动态分配法分配特点不分区，所有用户空间给某个进程或作业分 成 大 小

14、不 等 的 区域，区域分完后固定不变分 成 大 小 不 等 的 区域，根据用户要求动态分配在可变分区分配方式中，当有新作业申请分配内存时所采用的存储分配算法有名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 19 页 - - - - - - - - - 以下四种：1） 最佳适应法 ：选择等于或最接近作业需求的内存自由区进行分配。这种方法可以减少碎片，但同时也可能带来更多小得无法再用的碎片。2） 首次适应法 ：从主存地址开始，寻找第一个可用（即大于等于作业需求的内存）的自由区

15、。这种方法可实现快速分配，缩短查找时间。3） 最差适应法 ：选择整个主存中最大的内存自由区。4） 循环首次适应算法：是首次是英法的一个变种，也就是不在是每次都从头开始匹配，而是连续向下匹配。Eg：某计算机系统的内存大小是128K，采用可变分区分配方式进行内存分配，当前系统的内存分块情况如右图所示，现有作业4 申请内存9k，几种不同的存储分配算法在分配中，会产生怎样的结果？首次适应法：最佳适应法：最差适应法：循 环 首次适应算法：Eg：假设某计算机系统的内存大小为256KB，在某一时刻内存的使用情况如表（a）所示。此时，若进程顺序请求20KB，10KB，5KB 的存储空间，系统采用算法为进程一次

16、分配后的内存情况如表（b）所示。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 19 页 - - - - - - - - - A最佳适应B .最差适应C.首次适应D.循 环 首 次适应存储-虚存管理1） 页式存储组织设用户程序为16K，共分为8 页，则每页为2K，16K 等于 2 的 14 次方，2K 等于 2 的 11 次方，则页号的位数为3，页面的位数为11, 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - -

17、 - 名师精心整理 - - - - - - - 第 9 页，共 19 页 - - - - - - - - - 逻辑地址到物理地址：根据页号找到块号， 插到物理地址的高位； 页面地址插到物理地址的地位；优点： 利用率高，产生的内存碎片少，内存间分配及管理简单。缺点： 要有相应的硬件支持，增加了系统的开销；请求调页地算法如选择不当，有可能产生抖动现象。Eg：页式存储系统的逻辑地址是由页号和页内地址两部分组成。假定页面的大小为 4K,地址转换过程如下图所示， 图中逻辑地址用十进制表示。图中有效地址经过变换后，十进制物理地址a 应为_ A.33220 B.8644 C.4548 D.2500 已知页面

18、大小为4K，4K 等于 2 的 12 次方，所以页内地址有12 位。把逻辑地址8664 转换为二进制为10 0001 1100 0100，其中的低12 位为页内偏移量，最高两位为页号，所以页号为 2，所得物理块号为 8, 2） 段式存储组织名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 19 页 - - - - - - - - - 优点： 便于多道程序共享内存，便于对存储器的保护，各段程序修改互不影响。缺点： 内存利用率低，内存碎片浪费大。3） 段页式存储组织名师资料总

19、结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 19 页 - - - - - - - - - 优点： 空间浪费小、存储共享容易、存储保护容易、能动态连接。缺点： 由于管理软件的增加，复杂性和开销也随之增加，需要的硬件以及占用的内容也有所增加，使得执行速度大大下降。Eg: 在段页式管理的存储器中，实存等分为（页） 、程序按逻辑模块分成（段） 。在多道程序环境下，每道程序还需要一个（基号）作为用户标志号。每到程序都有对应的（一个段表和一组页表） 。一个逻辑地址包括（基号）x、段号 s

20、、页号 p 和页内地址d 四个部分。假设总长度为 22 位的逻辑地址格式分配如下：2120 位 x； 1914 位 s；1311 位 p； 100 位 d。若 x,s,p,d 均为二进制数表示，其转换为物理地址为（ （ （x）+s）+p）*2的11次方+d 由基号从基号表找到段起始号，4） 页面置换算法最优（ OPT）算法先进先出（ FIFO ）算法最近最少使用（LRU）算法缺页（进入内存时内存中没有与进入页面相同的页面）Eg：在一个虚存系统中，进程的内存空间为3 页，开始内存为空， 有以下访问页序列：1 4 6 5 3 4 5 2 5 4 3 5 1 2 4 1，分别计算缺页次数。1） 使用

21、先进先出算法：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 19 页 - - - - - - - - - 缺页次数为12 2） 使用最佳适应算法缺页次数为9 3） 使用最近最少使用算法缺页次数为11 5） 局部性原理（重要）1、时间局部性（ eg:一个程序在某个时间被使用，可能在不久后再次访问）2、空间局部性（ eg:一个空间被访问，可能不久这个空间周围的空间也被访问）Eg: int i,s=0; for(i=0;i1000;i+) for(j=1;j1000;j+)

22、 s+=j; printf(“结果为： %d ”,s); 3、作业管理作业由三部分构成，即程序、 数据和作业说明书，它是用户在完成一项任务过程中要求计算机系统所做工作的集合。作业的状态有后备状态、运行状态和完成状态3 种。1） 作业状态极其转换名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 19 页 - - - - - - - - - 2） 作业调度算法作业运行时间表：作业所需运行时间（小时）优先级1 2 4 2 5 9 3 8 1 4 3 7 /平均周转时间等于平均运

23、行时间加平均等待时间先来先服务（ FCFS ）/按作业的到来时间顺序作业提交时间开始时间完成时间等待时间周转时间1 0 0 2 0 2 4 0 2 7 2 7 2 0 7 15 7 15 3 0 15 18 15 18 平均等待时间： （0+2+7+15）/4=6 小时平均周转时间： （2+7+15+18）/4=10.5 小时 最短作业优先（SJF ）/ 运行时间短的先运行作业提交时间开始时间完成时间等待时间周转时间1 0 0 2 0 2 4 0 2 5 2 5 2 0 5 10 5 10 3 0 10 18 10 18 平均等待时间：（0+2+5+10） /4=4.25 小时平均周转时间：（

24、2+5+10+18）/4=10.25 小时 最高响应比优先算法（难）Eg：一个有 两个作业管理进程的批处理程序，作业调度采用最高相应比优先的算法 ，进程调度采用基于优先数（优先数大者优先）的算法，则有作业序列如表所示。作业序列表：作业名到达时间估计运行时间（分）优先数A 10:00 50 5 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 19 页 - - - - - - - - - B 10:20 60 7 C 10:50 40 3 D 11:20 80 8 E 11

25、:40 30 6 F 12:00 70 9 响应比公式：响应比=1+等待运行时间/估计运行时间响应比=周期运行时间/估计欲行时间两个作业管理进程（最多有两个进程进入内存进行等待）作业调度 （那个作业先进入内存，多种方法， 此处为最高优先比算法）进程调度（那个进入进入内存的作业先被CPU调度，多种方法，此处为最大优先数法）10:00 A作业到达，无竞争运行；10:20 B作业到达，作业进入内存，优先数大于A，所以B开始运行，此时，A作业等待；10:50 C作业到达，此时内存中已有两个作业，所以C无法进入内存，内存中有A作业等待；11:20 B作业完成，D作业到达，此时计算响应比，以确定C和D中哪

26、一个作业能进入内存，C的响应比为1+30/40=7/4,D的响应比为1+0/80=1。显然C的响应比高，所以C进入内存。这是内存中有A和C两个作业，A比C的优先数大，所以A开始运行。此时，内存中有C作业在等待；11:40 E作业到达，此时内存中已有两个进程，所以E不能进入内存；11:50 A作业完 成，D响应比=1+30/80=11/8，E的响应 比=1+10/30=4/3.D比E响应比高，所以D进入内存。同时D的优先数比C大，所以D运行。此时，内存中C作业在等待。12:00 F作业大大，此时内存中已有两个进程，所以F不能进入内存；13:10 D作业完成，此时的E响应比=1+90/30=4,F

27、的响应比=1+70/70=2。E比F的响应比高，所以E进入内存。又因为E的优先数比C大，所以E运行。内存中C作业仍在等待。13:40 E作业完成，F作业进入内存，由于F的优先级比C大，所以F开始运行；14:50 F作业完成，C开始运行；15:30 C作业完成；-作业的完成时间为：11:20 B作业完成；11:50 C作业完成；13:10 D作业完成；13:40 E作业完成；14:40 F作业完成；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 19 页 - - - -

28、- - - - - 15:30 C作业完成； 定时轮转/ 给定一个时间片，每个作业依次循环运行一个时间片，直至运行结束。 优先数/ 优先级越高先运行作业提交时间开始时间完成时间等待时间周转时间2 0 0 5 0 5 4 0 5 8 5 8 1 0 8 10 8 10 3 0 10 18 10 18 平均等待时间：（0+5+8+10） /4=5.75 小时平均周转时间：（5+8+10+18）/4=8.75 小时3） 作业周转时间单个作业周转时间：Ti=Tei Tsi 或Ti=Twi+Tri Tei 为作业的完成时间，Tsi 为作业的提交时间Twi 为作业的等待时间，Tri 为作业的执行时间作业平

29、均周转时间：T=（T1+T2+ +Tn）/n 4、目录和 spooling 1）文件目录一级目录结构（单用户）二级目录结构名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 19 页 - - - - - - - - - 树形目录结构2）spooling 技术例如：打印机虚拟排队操作系统例子：1、名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 19 页

30、 - - - - - - - - - 2、 若系统中有同类资源16 个，有 4 个进程 p1,p2,p3,p4 共享资源。已知 p1,p2,p3,p4所需资源总数分别为8,5,9,6.各进程请求资源的次序如下表所示，若系统采用银行家算法为他们分配资源，那么第几次申请分配会使系统进入不安全状态？3若有一个仓库，可以存放p1,p2 两种产品，但是每次只能存放一种产品。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 19 页 - - - - - - - - - 要求：1） w

31、=P1 的数量 P2的数量2） -iwk (I,k 为正整数 ) k i 若用P-V 操作实现P1 和 P2 产品的入库过程，至少需要_个同步信号量和_个互斥信号量，其中，同步信号量地初值分别为_,互斥信号量的初值分别为 _。（1）A、 0 B、1 C、2D、3 （2）A、 0 B、1C、2 D、3 （3）A、 1 B、I,k,0 C、I,k D、i-1,k-1 （4）A、 1 B、1,1 C、1,1,1 D、I,k 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 19 页 - - - - - - - - -