诚毅学院2016年操作系统重修资料

1、1计算机系统是由硬件 系统和 软件 系统两部分组成。2、 分时操作系统的主要特征有多路性、交互性、独占性、及时性 。3、 采用多道程序设计技术能充分发挥CPU与外设的并行工作的能力。4、在主机控制下进行的输入 /输出操作称为联机输入/输出操作。5、 按内存中同时运行程序的数目可以将批处理系统分为两类：单道批处理系统和多道批处理系统。6、 操作系统的主要性能参数有吞吐量和利用率等。其中 吞吐量 指的是单位时间内系统处理的作业量。利用率 指的是在一个给定时间内，系统的一个指定成分被使用的时间比例。7、批处理系统 不允许用户随时干预自己程序的运行。8、 实时操作系统与分时操作系统的主要区别是及时性和

2、高可靠性。9、 操作系统的最重要的特征是并发。10、 操作系统的最基本的特征是并发和共享。11、 操作系统的基本特征有并发、共享、虚拟、异步。12、 在现代操作系统中，资源的分配单位是进程，而处理机的调度单位是线程，一个进程可以有多个线程13、 进程调度完成进程状态从就绪 态到 运行 态的转化。14、 进程的基本状态有就绪,运行,阻塞 。15、系统中存在多个进程时，这些进程对共享资源的使用存在着不同的相互制约关系，制约关系可归结为 两种，一种是 直接制约 关系，另一种是 间接制约 关系。I. I/O控制方式的发展经历了 4个阶段，分别是程序查询方式、I/O中断方式、DMA方式2从资源分配角度出

3、发，I/O设备可以分为 独占设备、共享设备和虚拟设备三种类型。3 按设备所属关系分类，可分为系统设备 和用户设备两类。4通道指专门用于负责输入 /输出工作的处理机，通道所执行的程序称为通道程序。5. 通道是一个独立于 CPU的专管输入/输出的处理机 的处理机，它控制 外设 与内存之间的信息交换。6虚拟设备是通过 虚拟 技术把独占 设备变成能为若干用户 共享 的设备。7打印机是 独占 设备，磁盘是 共享 设备。&根据信息交换方式，通道可分成3种类型，分别是 字节多路通道、数组选择通道 和数组多路通道 。9设备驱动程序是I/O进程和设备控制器 之间的一个 通信 程序。10 设备独立性的含义是 应用

4、程序独立于具体使用的物理设备。II、 为了防止进程对系统资源的无序竞争，所有设备必须由系统 统一分配。12在实现了设备独立性的系统中，I/O进程申请设备是以 逻辑设备名 来申请的。13 设备分配算法有 先来先服务 和优先权高者优先 两种。14 现代计算机I/O系统的结构，由 通道、设备控制器 和 设备 三级组成。15. SPOOLING系统由 输入井输岀井、输入缓冲区输岀缓冲区和输入进程输岀进程三部分组成。1、存储分配解决多道作业（主存空间）的划分问题。为了解决静态和动态存储分配，需采用地址重定位，即把 （逻辑地址） 变换成 （物理地址） ，静态重定位由 （连接装入程序） 实现，动态重定位由

5、（硬 件地址变换机构）实现。2、提高主存利用率主要是通过 （主存分配） 功能实现的。（主存分配） 的基本任务是为每道程序做 （分配内存）：使每道程序能在不受干扰的环境下运行，主要是通过（主存保护）功能实现的。3、由固定分区方式发展为分页存储管理方式的主要推动力是（提高主存的利用率）：由分页系统发展为分段系统，进而以发展为段页式系统的主要动力分别是（既满足用户要求，又提高主存利用率）。4、静态重定位是在作业的（装入过程）中进行的，动态重定位是在作业的（执行过程）中进行的。5、 对外存对换区的管理应以（提高换入换出速度）为主要目标，对外存文件区的管理应以（提高存储空间的利用率）为主要目标。6、从下

6、列关于虚拟存储器的论述中，选出一条正确的论述。 要求作业运行前，不必全部装入内存，且在运行中不必常驻内存；是正确的7、 在请求分页系统中有着多种置换算法：选择最先进入内存的页面予以淘汰的算法称为（FIFO算法）;选择在以后不再使用的页面予以淘汰的算法称为（OPT算法）: 选择自上次访问以来所经历时间最长的页面予淘汰的算法称为（LRU算法）;8、 静态链接是在 （装入） 到某段程序时进行的，动态链接是在（调用） 到某段程序时进行的。（计算机的地址结构）确定的，其实际容量是由（内存9、一个计算机系统的虚拟存储器的最大容量是由 和硬盘容量之和）确定的。1 0、以动态分区式内存管理中，倾向于优先使用低

7、址部分空闲区的算法是（首次适应法）；能使内存空间中空闲区分布较均匀的算法是（循环适应法）；每次分配时把既能满足要求，又是最小的空闲区分配给进程的算法是 （最佳适应法）。1 1某虚拟存储器的用户编程空间共3 2个页面，每页1KE，主存为16KE。假定某时刻该用户页表中已调入主存的页面的虚页号和物理页号对照表如下：虚页号物理页号 051102437则下面与虚地址相对应的物理地址为（若主存中找不到，即为页失效） 虚地址物理地址0A5C （H ）（ 125C （ H ）1A5C （H ）（页失效）这里，（H）表示十六进制。虚拟存储器的功能由（软硬件结合） 完成。二、填空题1、使每道程序能在内存中各得其

8、所”是通过内存分配功能实现的；保证每道程序在不受干扰的环境下运行，是通过 内存保护 功能实现的；为缓和内存紧张的情况而将内存中暂时不能运行的进程调至外存,这是通过对换 功能实现的；能让较大的用户程序在较小的内存空间中运行, 是通过内存扩充 功能实现的。2、 在连续分配方式中可通过紧凑来减少内存零头，但此时必须将有关程序和数据进行重定位；而动态重定位 是一种允许作业在运行中、在内存中进行移动的技术。3、 分段保护中的越界检查是通过 段表寄存器 中存放的段表长度 和段表中的 段长 实现。4、 在分页系统中若页面较小，虽有利于提高内存利用率 ，但会引起 页表太长；而页面较大，虽有 利于页表长度但会引

9、起页面碎片增大 。5、在分页系统中的地址结构可分为页号 和 页内偏移量 两部分：在分段系统中的地址结构可分为段号禾廿-段内偏移量 两部分。6、在分页系统中，必须设置页表，其主要作用是实现7、在分页系统中进行地址变换时，应将页表寄存器中的 表项位置，从中可得到 物理块号。页号 至U 物理块号 的映射。页表始址和页号进行相加，得到该页的页8、 在两级页表结构中，第一级是页表目录，其中每一项用于存放相应的页表首址。9、 在分页系统中为实现地址变换而设置了页表寄存器，其中存放了页表始址 和 页表长度。10、 在页表中最基本的数据项是物理块号：在段表中最基本的数据项是段的内存始长 和 段长。11、 在作

10、业 装入 时进行的链接称为静态链接：在作业运行中调用 时进行的链接称为动态链接。12、 为实现存储器的虚拟，除了需要有一定容量的内存和相当容量的外存外，还需有地址变换机构 和 缺页中断机构 的硬件支持。请求调页策略，由2、4、6、8、10 分13、在请求分页系统中的调页策略有一预调页策略，它是以预测为基础；另一种是于较易实现，故目前用得较多。【1】有5个批处理作业（A、B、C、D、E）几乎同时到达，估计的运行时间分别为钟，它们的优先数分别为 1、2、3、4、5 （1为最低优先数）。对下面的每种调度算法，分别计算作业的 平均周转时间。（1）最高优先级优先。（2）时间片轮转（时间片为（3） FIF

11、O （作业的到达顺序为 C、D、B、E、A）答：为了计算方便，假设这批作业的到达时间为0。（1）使用最高优先级优先算法时，作业的调度顺序为2分钟）（4）短作业优先。E、D、C、B、A，各作业的周转时间如下表所示。作业执行时间优先数开始运行时间完成时间周转时间A21283030B42242828C63182424D84101818E10501010平均周转时间为(30+28+24+18+10 ) / 5=22分钟(2) 使用时间片轮转算法时，作业的调度顺序为：0分钟 作业A、B、C、D、E到达，作业A开始运行，作业 B、C、D、E等待2分钟 作业A运行结束，作业 B开始运行，作业 C、D、E等待

12、4分钟 作业C开始运行，作业 D、E、B等待6分钟 作业D开始运行，作业 E、B、C等待8分钟作业E开始运行，作业B、C、D等待10分钟作业B开始运行，作业C、D、E等待12分钟作业B运行结束，作业C开始运行，作业D、E等待14分钟作业D开始运行,作业E、C等待16分钟作业E开始运行，作业C、D等待18分钟作业C开始运行，作业D、E等待20分钟作业C运行结束，作业D开始运行，作业E等待22分钟作业E开始运行，作业D等待24分钟作业D开始运行,作业E等待26分钟作业D运行结束,作业E开始运行30分钟作业E运行结束各作业的周转时间如下表所以。作业执行时间优先数开始运行时间完成时间周转时间A2102

13、2B4221212C6342020D8462626E10583030平均周转时间为(2+12+20+26+30)/ 5=18分钟(3)使用FIFO (作业到达顺序为 C、D、B、E、A)算法时，作业调度顺序为C、D、B、E、A，各作业的周转时间如下表所示。作业执行时间优先数开始运行时间完成时间周转时间A21283030B42141818C63066D8461414E105182828平均周转时间为(30+18+6+14+28)/ 5=19.2分钟(4)使用短作业优先算法时，作业的调度顺序为A、B、C、D、E,各作业的周转时间如下表所示。作业执行时间优先数开始运行时间完成时间周转时间A21022

14、B42266C6361212D84122020E105203030平均周转时间为(2+6+12+20+30)/ 5=14分钟三、问答题1、有一个多道程序设计系统，采用不允许移动的可变分区方式管理主存中的用户空间，设用户空间为100K，主存空间的分配算法为最先适应分配算法，进程调度算法采用先来先服务算法，今有如表所示作 业序列：假定所有作业都是计算型作业且忽略系统调度时间，请分别写出采用先来先服务调度算法”、计算时间短的作业优先算法 ”时作业的装入主存时间、开始执行时间、完成时间、周转时间以及它们的平均周 转时间。表作业名进入输入井”时间需计算时间主存需求量A10： 0642分钟15KB10：

15、1830分钟60KC10： 3024分钟50KD10： 3620分钟10KE10： 4212分钟20K答:作业名进入输入井”时 间装入主存时间开始执行时 间完成时间周转时间A10： 0610： 0610： 0610： 4842分钟B10： 1810： 1810： 4811： 1860分钟C10： 3011 ： 1811： 5012： 1494分钟D10： 3610： 3611： 1811： 3862分钟E10： 4211 ： 1811： 3811： 5068分钟平均周转时间：(42+60+104+62+68)/5=67.2分钟2、在一个批处理单道系统中，采用响应比高者优先的 作业调度算法。当一

16、个作业进入系统后就可以开始调度，假定作业都是仅计算，忽略调度花费的时间。现 有三个作业，进入系统的时间和需要计算的时间如表所示：表作业进入系统时 间需要计算时 间开始时间完成时间周转时间19:0060分钟29:1045分钟39:1525分钟(1) 求出每个作业的开始时间、完成时间及周转时间并填入表中。(2) 计算三个作业的平均周转时间应为多少？解答：先来先服务作业进入系统时 间需要计算时 间开始时间完成时间周转时间19:0060分钟9： 0010 : 0060分钟29:1045分钟10： 0010 : 4595分钟39:1525分钟10： 4511： 10115分钟(2)计算三个作业的平均周转

17、时间应为多少？解答:先来先服务：(60+95+115)/3=90(分钟)2. 进程之间存在哪几种相互制约关系？各是什么原因引起的？下列活动分别属于哪种制约关系？(1)若干同学去图书馆借书；(2)两队举行篮球比赛；(3) 流水线生产的各道工序；(4)商品生产和社会消费。解：进程间存在着 2种相互制约的关系：直接制约关系(即同步问题)和间接制约关系(即互斥问题)。 同步问题是存在逻辑关系的进程之间相互等待所产生的制约关系，互斥问题是相互无逻辑关系的进程间竞 争使用相同资源所发生的制约关系。(1) 属于互斥关系，因为书的个数是有限的，一本书只能借给一个同学；(2) 属于互斥关系，篮球只有一个，两队都

18、要争夺；(3) 属于同步关系，各道工序的开始都依赖前道工序的完成；(4) 属于同步关系，商品没生产出来，消费无法进行，商品未消费完，生产也无须进行。3. 设有两个优先级相同的进程P1和P2如下。信号量 S1和S2的初值均为0，试问P1、P2并发执行结束后， x=?， y=?， z=?进程 P1进程 P2y:=1;x:=1;y:=y+2;x:=x+1;V(S1);P(S1);z:=y+1;x:=x+y;P(S2)；V(S2) ；y:=z+y;z:=x+z;解：因为 P1 和 P2 是两个并发进程，所以进程调度程序调度 P1 和 P2 的顺序是不确定的。这里不妨假设 P1先执行。进程 P1执行到语

19、句P(S2)时，S2= -1,进程P1阻塞。此时，y=3 , z=4。当 进程调度程序调度到进程P2时，由于进程P1已执行了 V(S1)，进程P2在执行P(S1)时并未阻塞而继续执行，当执行到 V(S2)时，将P1唤醒，然后执行最后一个语句z:=x+z，此时x=5 , z=9。当进程P1再次被调度时，继续执行 P1 的最后一个语句，此时y=1 2,最终结果是： x=5，y=12，z=9。如果当P2进程执行到V(S2)时，将P1唤醒，然后P2进程被中断，此时 x=5 , y=3, z=4。P1进程开始 执行然后执行最后一个语句 y：=z+y，此时x=5, y=3,z=7。然后P2进程被调度，执行

20、 z:= x+z，此时x=5 , y=3, z=12。如果 P2 先执行,则执行结果与上面4. 桌上有一空盘,只允许存放一个水果。爸爸可向盘中放苹果,也可向盘中放桔子。儿子专等吃盘 中的桔子,女儿专等吃盘中的苹果。规定当盘中空时一次只能放一只水果供吃者取用,请用P、 V 原语实现爸爸、儿子、女儿三个并发进程的同步。分析 在本题中,爸爸、儿子、女儿共用一个盘子,且盘中一次只能放一个水果。当盘子为空时,爸 爸可将一个水果放入果盘中。若放入果盘中的是苹果,则允许女儿吃,儿子必须等待；若放入果盘中的是 桔子,则允许儿子吃,女儿必须等待。本题实际上是生产者-消费者问题的一种变形。这里,生产者放入缓冲区的

21、产品有两类,消费者也有两类,每类消费者只消费其中固定的一类产品。解在本题中，应设置三个信号量S、So、Sa,信号量S表示盘子是否为空，其初值为1;信号量So表示盘中是否有桔子,其初值为0;信号量 Sa 表示盘中是否有苹果,其初值为0。同步描述如下：int S=1;father()son( )daughter( )int Sa=0;int So=0;while(1)while(1)while(1)main( )P(S );P(So);P(Sa);Cobegin将水果放入盘中;从盘中取出桔子 ;从盘中取出苹果father();if (放入的是桔子) V(So);V(S);V(S);son();el

22、se V(Sa);吃桔子 ;吃苹果 ;daughter();Coend 【1】假设现在有p个进程，每个进程最多需要m个资源，并且有r个资源可用，什么样的条件可以保证死锁不会发生。【解答】如果一个进程有 m 个资源它就能够结束，不会使自己陷入死锁中。因此，最差的情况是每个进程有 m-1 个资源并且需要另外一个资源。如果留下有一个资源可用，那么其中某一个进程就能够结束并释放 它所有的资源，使其他进程也能结束。所以避免死锁的条件是：r=p(m-1)+1【 2】一台计算机有 6 台磁带机，由 n 个进程竞争使用，每个进程可能需要两台磁带机，那么 n 是多少时， 系统才没有死锁的危险？【解答】对于三个进

23、程，每个进程能够有两个驱动器。对于4 个进程，驱动器可以按照( 2， 2， 1， 1)的方法进行分配，使前面两个进程先结束。对于 5 个进程，可以按照( 2， 1， 1， 1， 1)的方法进行分发， 使一个进程先结束。对于六个进程，每个进程都拥有一个磁带驱动器同时需要另外一个驱动器，产生了死 锁。因此，对于 n6 的系统来说是无锁的。【 3】假设某系统中有4 种资源 (R1,R2,R3,R4) ，在某时刻系统中共有 5 个进程，进程 P1， P2， P3， P4，P5 的最大资源需求数量和此刻已分配到资源数向量分别如下系统中当前可用资源向量为 (2,1,0,0),问1 当前系统是否是安全的？2

24、 如果进程 P3 发出资源请求向量 (0,1,0,0) ，系统能否将资源分配给它？【答案】1 当前系统是安全的 2 系统不能将资源分配给它 【分析】进程的最大资源需求数减去当前进程已获得的资源数就是进程仍需要的资源数，此刻各个进行的 仍需要资源数向量为： P1(0,0,0,0);P2(0,7,5,0);P3(6,6,2,2);P4(2,0,0,2);P5(0,3,2,0) 而系统的可用资源向量为 (2,1,0,0), 这时存在如下执行序列，使进程顺序执行完毕，状态安全 进程可用资源数P1 完成后(2,1,1,2)P4 完成后(4,4,6,6)P5 完成后(4,7,9,8)P2 完成后(6,7,

25、9,8)P3 完成后(6,7,1,12)在P3发出资源请求(0,1,0,0)后，假设系统把资源分配给P3,则个进程已分配资源数为： P1(0,0,1,2);P2(2,0,0,0);P3(0,1,3,4);P4(2,3,5,4);P5(0,3,3,2)此 时 系 统 可 用 资 源 为 (2,0,0,0)， 各 进 程 仍 需 要 资 源 向 量 为 ：P1(0,0,0,0);P2(0,7,5,0);P3(6,5,2,2);P4(2,0,0,2);P5(0,3,2,0) 满足资源需求的进程执行序列为：进程名可用资源数P1 完成后(2,0,1,2)P4 完成后(4,3,6.6)P5 完成后(4,6

26、,9,8)此时可用资源不能满足P2,P3的需求，即此时系统状态是不安全的，将拒绝资源请求1 、 对于如下的页面访问序列：1 ， 2 ， 3 ， 4 ， 1 ， 2 ， 5 ， 1 ， 2 ， 3 ， 4 ， 5当内存块数量分别为 3 和 4 时，试问：使用 FIFO 、OPT 、LRU 置换算法产生的缺页中断是 多少？(所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断) 解： FIFO 淘汰算法：内存块为 3 时，缺页中断(或称缺页次数、页面故障)为 9 ；内存块为 4 时，缺页中断为 10 。LRU 淘汰算法：内存块为 3 时，缺页中断为 10 ；内存块为 4 时，缺页中断为 8

27、 。2、某段表内容如下：段号 段首地址 段长度0 120K 40K1 760K 30K2 480K 20K3 370K 20K一逻辑地址为(2, 154)的实际物理地址为多少？解:逻辑地址(2i54)表示段号为2,即段首地址为 480K, i54为单兀号，则实际物理地址为480K+i54【4】假定系统中有五个进程P。、Pi、P2、P3、P4和三种类型资源A、B、C，每一种资源的数量分别为10、5、7。各进程的最大需求、T0时刻资源分配情况如下所示。MaxAllocati onNeedAvailableABCABCABCABCPo753oio743332Pi3222ooi22P29o23o26o

28、oP32222iioiiP4433oo243i试问：To时刻是否安全？ To之后的Ti时刻Pi请求资源Requesti(l,0,2)是否允许？ Ti之后的T2时刻P4请求资源Request4(3,3,0)是否允许？ T2之后的T3时刻Po请求资源Requesb(o,2,O)是否允许？ 解：To时刻是否安全？工作向量Work.它表示系统可提供给进程继续运行所需要的各类资源的数目贵源情况work ABcABCAlloration ABcWo ik+Allot JrtcmfinishABCPO7457430 1075(thePl3321222 00sA32trueP27F56003021057tru

29、eP35320112 I1743trueP47434311 0274 Atrue从表中可找出一个序列Pi、P3、P4、Po、P2使各进程顺序地一个个地执行完成。安全序列为P1、P3、P4、P。、P2，T0时刻系统是安全的。 To之后的Ti时刻Pi请求资源Requesti(i,o,2)可否允许？Requesti (i,0,2) Nf(i(2,2), Pi请求在最大需求范围内。Requesti(i,0,2) Available(3,3,2可用资源可满足Pi 请求需要。试探把要求的资源分配给进程Pi并修改有关数据结构的数值：Available(2,3,0) = Available(3,3,2)-Re

30、quest i(i,0,2);Needi(0,2,0) = Need i(i,2,2)-Requesti (i,0,2);Allocation i(3,0,2) =Allocation i(2,0,0)+Requesti(i,0,2);利用安全性算法检查试探将资源分配后状态的安全性如下：源情况进程、workANeed BCAllocndon 1 1 + kllOi JfLfinhutKhABCABCABCPo7457430107气wtruePl230020302532trueF:75561)03021057true岭532011211743tnifP474343102745true因为先分配资

31、源给 Pl进程符合按安全序列Pl、P3、P4、Po、P2分配资源，所以试探将资源分配给进程P1后的状态是安全的，可将资源分配给进程Pl。 Ti之后的T2时刻P4请求资源Request4(3,3,0)是否允许？Request4(3,3,0) Ne4dB,1), P4请求在最大需求范围内。Request4(3,3,0) Available(2,3不成立，即可用资源暂不能满足P4请求资源需要，P4阻塞等待。P4请求资源Request4(3,3,0)不允许 T2之后的T3时刻P0请求资源Requestg(0,2,0)是否允许？Requesto(0, 2, 0) Nee7, 4, 3);Request。

32、, 2, 0) ( m+ 1) /2 + 1 即 mv n 27】系统中磁头停留在磁道号为 70的磁道上，这时先后有 4个进程提出了磁盘访问请求，要访问的磁盘 的磁道号按申请到达的先后顺序依次为：45,68,28,90。移动臂的运动方向：沿磁道号递减的方向移动。若分别采用FCFS磁盘调度算法、SSTF算法，SCAN算法算法时，所需寻道长度分别为多少(走过多少柱 面)？答：FCFS 磁盘调度算法：(70-45) + (68-45) + (68-28) + (90-28) =150;SSTF 算法：(70-68) + ( 90-68) + (90-45) + (45-28) =86SCAN 算法：(70-68) + (68-45) + (45-28) + (90-28) =104【引