操作系统知识点-(2).pdf

1综合类题目：（综合类题目：（30 分）分）进程同步互斥方面的程序题1 请求（虚拟）分页管理的逻辑地址到物理地址的变换，能看懂页表。地址变换：在执行指令在执行指令 MOV r1，2500时，地址转换步骤如下：时，地址转换步骤如下：取出程序地址字取出程序地址字 2500 送虚地址寄存器送虚地址寄存器 VR，然后由硬件分离出页号，然后由硬件分离出页号 P 和页内地址和页内地址 W，实际上分离出页号和页，实际上分离出页号和页内地址是一件很简单的事，因为页长为内地址是一件很简单的事，因为页长为 1K，所以页内地址占，所以页内地址占 10 位（位（0-9 位）位），页号占，页号占 6 位（位（10-15 位）位），所以，所以硬件只要简单地取出硬件只要简单地取出 VR 寄存器中的高寄存器中的高 6 位即为页号，低位即为页号，低 10 位即为页内地址。当然我们通过计算可以得到位即为页内地址。当然我们通过计算可以得到P=2，W=452根据页号根据页号 P=2，硬件自动查该进程的页表，找到第，硬件自动查该进程的页表，找到第 2 页对应的块号为页对应的块号为 7，将块号送到内存地址寄存器，将块号送到内存地址寄存器 MR 的高的高10 位中。位中。将将 VR 中的中的 W 的值的值 452 复制到复制到 MR 的低的低 10 位中，从而形成内存地址。系统就以位中，从而形成内存地址。系统就以 MR 中的地址访问内存中的地址访问内存2 给定页面访问序列，分别用各种置换算法计算缺页次数给定页面访问序列，分别用各种置换算法计算缺页次数某程序在内存中分配三个块，访问页的顺序为某程序在内存中分配三个块，访问页的顺序为 4，3，2，1，4，3，5，4，3，2，1，5，按，按 FIFO、LRU、OPT 算算法分别计算缺页次数法分别计算缺页次数FIFO 4 3 2 1 4 3 5 4 3 2 1 5页页 1 4 3 2 1 4 3 5 5 5 2 1 1页页 2 4 3 2 1 4 3 3 3 5 2 2页页 3 4 3 2 1 4 4 4 3 5 5 x x x x x x x x x 共缺页中断共缺页中断 9 次次LRU 4 3 2 1 4 3 5 4 3 2 1 5页页 1 4 3 2 1 4 3 5 4 3 2 1 5页页 2 4 3 2 1 4 3 5 4 3 2 1页页 3 4 3 2 1 4 3 5 4 3 2 x x x x x x x x x x共缺页中断共缺页中断 10 次次OPT 4 3 2 1 4 3 5 4 3 2 1 5页页 1 4 3 2 1 1 1 5 5 5 2 1 1页页 2 4 3 3 3 3 3 3 3 5 5 52页页 3 4 4 4 4 4 4 4 4 4 4 x x x x x x x 共缺页中断共缺页中断 7 次次3 银行家算法银行家算法1、银行家算法中的数据结构、银行家算法中的数据结构可利用资源向量可利用资源向量 Available。它是一个含有。它是一个含有 m 个元素的数组，其中每个元素代表一类可利用资源的数目。个元素的数组，其中每个元素代表一类可利用资源的数目。如：如：ABC523345674 磁盘调度算法-求应用各种算法产生的访问序列、每步移动的磁道数、移动的总磁道数等。先来先服务：假设磁盘访问序列：先来先服务：假设磁盘访问序列：98，183，37，122，14，124，65，67读写头起始位置：读写头起始位置：5398，183，37，122，14，124，65，67磁头走过的总道数：磁头走过的总道数：640最短寻道时间优先最短寻道时间优先(SSF)：98，183，37，122，14，124，65，67865，67，37，14，98，122，124，183磁头走过的总道数：磁头走过的总道数：236扫描算法（电梯算法）：扫描算法（电梯算法）：98，183，37，122，14，124，65，6737，14，65，67，98，122，124，183磁头走过的总道数：磁头走过的总道数：208循环扫描调度算法：循环扫描调度算法：5 混合索引中求某虚拟地址对应的索引级数、在索引块内的指针项数、和最终数据块中的偏移。每个文件都有一个每个文件都有一个 I 结点结点(I-node)，其中可以有，其中可以有 13 个指针用于空间分配。个指针用于空间分配。前前 10 个指针指向可以直接访问的磁盘块。个指针指向可以直接访问的磁盘块。剩下剩下 3 个指针指向间接块，即不包含数据的块。个指针指向间接块，即不包含数据的块。第一个指针指向一级间接块。第一个指针指向一级间接块。第二个指针指向二级间接块。第二个指针指向二级间接块。6 成组链接法的分配与回收实例。分配分配该过程首先检查空闲盘块号栈是否上锁。该过程首先检查空闲盘块号栈是否上锁。如未上锁，从栈顶取出一空闲盘块号，如未上锁，从栈顶取出一空闲盘块号，9将栈顶指针下移一格，将栈顶指针下移一格，空闲盘块号数的减空闲盘块号数的减 1 操作；操作；若该盘块号已是栈底，由于在该盘块号所对应的盘块中记有下一组可用的盘块号，调用磁盘读过程，若该盘块号已是栈底，由于在该盘块号所对应的盘块中记有下一组可用的盘块号，调用磁盘读过程，将内容读入栈中，作为新的盘块号栈的内容；将内容读入栈中，作为新的盘块号栈的内容；并把栈底对应的盘块分配出去。并把栈底对应的盘块分配出去。（数据已读入栈中）（数据已读入栈中）。再分配一相应的缓冲区，作为该盘块的缓冲区，再分配一相应的缓冲区，作为该盘块的缓冲区，最后，把栈中的空闲盘块数减最后，把栈中的空闲盘块数减 1 并返回。并返回。回收回收将回收盘块的盘块号，记入空闲盘块号栈的顶部，并执行空闲盘块数加将回收盘块的盘块号，记入空闲盘块号栈的顶部，并执行空闲盘块数加 1 操作。操作。当栈中空闲盘块号数目已达加当栈中空闲盘块号数目已达加 100 时，将现有栈中的时，将现有栈中的 100 个盘块号记入新回收的盘块中，个盘块号记入新回收的盘块中，再将其盘块号作为新的栈底。再将其盘块号作为新的栈底。7 针对多个进程的建立与结束，分别应用动态分区的三种算法（首次适应、循环首次适应、最佳适应）进行内存的申请与释放，求最后的内存占用情况。叙述简答、填空及选择：（叙述简答、填空及选择：（30 分、分、20 分、分、20 分）分）8 三种操作系统（从各种特性上比较）他们的比较/异同等。多道批：分时系统；实时系统多道批：资源利用率公高；系统吞吐量大；平均周转时间长；无交互能力分时和实时地区别：多路性：分时：时多时少 实时：周期性对多路现场信息采集独立性：实时：每个终端向实时系统提出服务和对对象的控制是彼此独立，互不干扰分时：每个用户独占一个终端互不干扰及时性:10分时：很短时间获得相应，一般 13 秒实时：响应时间更短交互性：分时：可以和系统进行人机对话实时：交互性较弱可靠性：实时系统要求较高9 进程与程序（从顺序和并发执行的特点上）他们的比较进程与程序（从顺序和并发执行的特点上）他们的比较/异同等。异同等。顺序性：顺序性：程序：一个操作必须在上一个操作结束后程序：一个操作必须在上一个操作结束后进程：多个操作可以同时执行进程：多个操作可以同时执行并发性：并发性：程序：产生间断性，失去封闭性，不可再现程序：产生间断性，失去封闭性，不可再现进程：多个进程同一时间可以同时进行进程：多个进程同一时间可以同时进行10 进程与线程（从并发、调度、占有资源、各自特点等方面比较）他们的比较进程与线程（从并发、调度、占有资源、各自特点等方面比较）他们的比较/异同等。异同等。并发：引入线程后，进程之间可并发，统一进程中各个线程可并发并发：引入线程后，进程之间可并发，统一进程中各个线程可并发调度：传统调度：传统 os,拥有资源，独立调度和分配的基本单位是进程；引入线程后线程是调度和分配的基本单位，进拥有资源，独立调度和分配的基本单位是进程；引入线程后线程是调度和分配的基本单位，进程是拥有资源的基本单位。统一进程中线程切换不引起进程切换，不同进程中线程切换引起进程切换。程是拥有资源的基本单位。统一进程中线程切换不引起进程切换，不同进程中线程切换引起进程切换。拥有资源：进程是拥有资源的独立单位拥有资源：进程是拥有资源的独立单位11 两种不同线程，他们的比较/异同等。用户线程：不用系统调用实现，用线程库管理，切换速度快内核线程：用系统调用实现，提供 api，线程切换需要核心支持切换比较：核心线程需要核心支持，时间慢；用户线程切换速度快资源分配：核心线程通过系统调用获得资源；用户线程通过进程获得资源12 系统调用与普通的函数调用，他们的比较/异同等。缺页中断和普通中断，他们的比较/异同等。相同点：保护现场；中断处理；恢复现场不同点：一般中断为一条指令完成后中断，缺页中断为一条指令执行时中断；一条指令执行时可能产生多个缺页中断13 网络操作系统和分布式操作系统，他们的比较/异同等。14 页表、快表、P/V 操作、死锁、Spooling、原语、目录文件及目录线形检索过程、虚拟存储器、微内核、置换算法、设备独立性及如何实现页表：为了将页号和页内地址转换成内存地址，用一个数据结构来登记页号和对应块号的关系。快表：把页表放在快速存储器中来加快访问内存的速度的快速存储器P/V 操作：死锁：两个已经占用资源的线程同时请求对方的资源不得，而相互等待对方。Spooling：外围操作与 CPU 对数据的处理同时进行，这种在联机情况下实现的同时外围操作交 Spooling。原语：一种特殊的系统调用，特点是不可被中断原语：一种特殊的系统调用，特点是不可被中断目录文件：为了实现对文件目录的管理，将文件目录一文件的形式保存在外存的文件虚拟存储器：为了使编程人员不受内存结构容量的限制，系统为用户构建一种存储器，其容量远大于内存，虚拟存储器：为了使编程人员不受内存结构容量的限制，系统为用户构建一种存储器，其容量远大于内存，这种面向编程的存储器这种面向编程的存储器11微内核：设备独立性：应用程序独立于具体使用的物理设备设备独立性：应用程序独立于具体使用的物理设备实现：系统具有将逻辑设备名转换成物理设备名的功能；引用程序使用逻辑名，系统执行时使实现：系统具有将逻辑设备名转换成物理设备名的功能；引用程序使用逻辑名，系统执行时使用物理名用物理名。15 文件的逻辑结构（流式、结构文件的逻辑结构（流式、结构/记录文件（顺序、索引、索引顺序、直接）记录文件（顺序、索引、索引顺序、直接）及物理结构（连须、链接（隐式、）及物理结构（连须、链接（隐式、显式）显式）、索引）、索引）16 内部/外部碎片、段式、段页式、请求分页存储管理的原理，以及这几种管理方式的逻辑地址到物理地址的转换过程外部碎片：由于大量信息由于先后写入、置换、删除而形成的不连续的空间碎片内部碎片：申请内存的大小和空闲区大小而使空闲区被切割，使得空闲区变小而无法使用。段式：原理：用户程序划分（分成若干段）；逻辑地址分割（段号+段内地址）；内存划分（分为若干长度不同的区）；内存分配（已段为单位分配，段内连续，段之间不连续）地址转换：用段号找到该段首地址再和段内地址相加段页式：原理：用户程序划分（按段划分程序，按页划分段）；逻辑地址（段号+（页号+页内地址）；内存划分（按页式管理）；内存分配（一夜为单位分配）地址转换：段表记录每一段的页表始址和页表长度，页表记录页号和块号的对应关系分页：原理：程序划分（分成页）；逻辑地址（页号+页内地址）；内存空间（按页的大小分成块）；内存分配（已夜分配）地址转换：用页号找出块号再和页内地址相加17 进程的七种状态及引起状态间转换的原因和相关原语进程的七种状态及引起状态间转换的原因和相关原语18 四种设备 IO 方式程序 I/O 方式I/O 中断方式DMA 方式通道方式1219I/O 系统的层次及每层的功能与任务20 设备分配的数据结构及其英文缩写21 从资源角度设备可分为哪几种？独占性设备共享性设备虚拟设备22 逻辑设备表的主要功能设备控制表 DCT：记录本设备情况控制器控制表 COCT：记录本控制器情况系统设备表 SDT：记录系统中全部设备的情况23 缓冲区的种类单缓冲双缓冲循环缓冲缓冲池24spooling 的结构及原理；结构：输入井和输出井；输入缓冲区和输出缓冲区；输入进程和输出进程原理：利用一道程序模拟脱机输入，将 IO 设备数据传送到磁盘；利用另一程序模拟脱机输出，将磁盘数据输出到输出设备25 文件控制块及索引节点的内容文件控制块：文件名，文件号，用户名，文件地址，文件长度，文件类型，文件属性，共享计数，文件的建立日文件名，文件号，用户名，文件地址，文件长度，文件类型，文件属性，共享计数，文件的建立日期，保存期限，最后修改日期，最后访问日期，口令，文件逻辑结构，文件物理结构等期，保存期限，最后修改日期，最后访问日期，口令，文件逻辑结构，文件物理结构等索引节点：磁盘索引节点：磁盘索引节点：文件主标识符，文件类型，存取权限，物理地址，长度，连接计数，存取时间文件主标识符，文件类型，存取权限，物理地址，长度，连接计数，存取时间内存索引节点：内存索引节点：文件打开时，磁盘索引节点进内存以便于使用，增加了几项：文件打开时，磁盘索引节点进内存以便于使用，增加了几项：索引节点标号，状态（是否上锁或修改）索引节点标号，状态（是否上锁或修改），访问计数，所属文件系统的逻辑设备号，链接指，访问计数，所属文件系统的逻辑设备号，链接指针。针。26 文件目录的改进及好处；将 FCB 文成 2 部分：符号目录项（文件名，文件号），基本目录项（除文件名其他部分）好处：主要信息在检索目录时用不到，不进内存，加快速度27 装入与链接的类型13装入：绝对装入方式；可重定位装入方式；动态运行时装入连接：静态链接；装入时动态链接；运行时动态链接28 动态重定位及物理地址形成定义：由于经过紧凑后的用户程序在内存中的位置发生了变化，必须对程序和数据的地址进行修改由于经过紧凑后的用户程序在内存中的位置发生了变化，必须对程序和数据的地址进行修改(变换变换)重重定位。定位。地址变换过程是在程序执行期间，随着对指令和数据的访问而自动进行的，故称为动态重定位。地址变换过程是在程序执行期间，随着对指令和数据的访问而自动进行的，故称为动态重定位。物理地址形成：在系统中增加一个重定位寄存器，存放程序在内存中的起始地址。所以在系统中增加一个重定位寄存器，存放程序在内存中的起始地址。所以“紧凑紧凑”后只要用新起始地址后只要用新起始地址置换重定位寄存器中内容。置换重定位寄存器中内容。程序执行时访问的：程序执行时访问的：内存地址内存地址=相对地址相对地址+重定位寄存器中的起始地址重定位寄存器中的起始地址29 内存的值换算法都有哪几种？先进先出 FIFO第二次机会淘汰 SCR最佳页面算法 OPT最近最久未使用 LRU30 页式、段式方式的逻辑地址是几维的？分别访问几次内存？页式 1 维 段式 2 维；都访问 2 次31 动态分区的三种算法（首次适应、循环首次适应、最佳适应）的工作原理首次适应：当进程申请大小为当进程申请大小为 SIZE 的内存时，系统从空闲区表的第一个表目开始查询，直到首次找到等于或大于的内存时，系统从空闲区表的第一个表目开始查询，直到首次找到等于或大于SIZE 的空闲区。从该区中划出大小为的空闲区。从该区中划出大小为 SIZE 的分区分配给进程，余下的部分仍作为一个空闲区留在空闲的分区分配给进程，余下的部分仍作为一个空闲区留在空闲区表中，但要修改其首址和大小。区表中，但要修改其首址和大小。循环首次适应：分配时，从上次找到的空闲分区的下一个空闲分区开始查找，直至找到第一个能满足要求的空闲分区，分配时，从上次找到的空闲分区的下一个空闲分区开始查找，直至找到第一个能满足要求的空闲分区，从中划出一块与请求的大小相等的内存空间分配给作业。从中划出一块与请求的大小相等的内存空间分配给作业。最佳适应：按空闲区大小从小到大的次序组成空闲区表按空闲区大小从小到大的次序组成空闲区表当进程申请一个存储区时，系统从表头开始查找，当找到第一个满足要求的空闲区时，停止查找，并且当进程申请一个存储区时，系统从表头开始查找，当找到第一个满足要求的空闲区时，停止查找，并且这个空闲区是最佳的空闲区这个空闲区是最佳的空闲区32 死锁的四个必要条件互斥条件：涉及的资源是非共享的。互斥条件：涉及的资源是非共享的。不剥夺条件：不能强行剥夺进程拥有的资源。不剥夺条件：不能强行剥夺进程拥有的资源。请求和保持（部分分配）条件：进程在等待一新资源时继续占有已分配的资源。请求和保持（部分分配）条件：进程在等待一新资源时继续占有已分配的资源。环路条件：存在一种进程的循环链，链中的每一个进程已获得的资源同时被链中的下一个进程所请求。环路条件：存在一种进程的循环链，链中的每一个进程已获得的资源同时被链中的下一个进程所请求。33 处理死锁的几种方法14预防；破坏死锁四个必要条件中的一个或多个，来防止死锁破坏死锁四个必要条件中的一个或多个，来防止死锁避免；资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。检测；通过检测机构及时检测出死锁的发生通过检测机构及时检测出死锁的发生解除;撤消或挂起一些进程。以回收一些资源，再将它们分配给处于阻塞状态的进程，使之转为就绪状态撤消或挂起一些进程。以回收一些资源，再将它们分配给处于阻塞状态的进程，使之转为就绪状态34 叙述预防死锁可以使用的方法破坏请求和保持（部分分配）条件破坏请求和保持（部分分配）条件;破坏不可剥夺条件破坏不可剥夺条件;破坏环路条件破坏环路条件35 进程调度的几种算法的原理及特点（有利于什么样的作业等等）先来先服务算法先来先服务算法 FCFS：有利于长作业，不利于短作业：有利于长作业，不利于短作业最短作业优先算法最短作业优先算法 SJF：对长作业不利：对长作业不利高优先权调度算法高优先权调度算法:照顾紧迫作业，常用于批处理照顾紧迫作业，常用于批处理;最高响应比优先算法最高响应比优先算法 HRN：有利于短作业有利于短作业等待时间越长，优先级越高等待时间越长，优先级越高对于长作业也不会无限等待对于长作业也不会无限等待时间片轮转程序调度算法时间片轮转程序调度算法:多队列反馈调度算法多队列反馈调度算法:36 进程通讯有几种形式37 消息缓冲区通讯的原理38 什么是 PCB？为什么是进程的唯一标志？定义：为了描述一个进程和其它进程以及系统资源的关系，为了刻画一个进程在各个不同时期所处的状态，人们采为了描述一个进程和其它进程以及系统资源的关系，为了刻画一个进程在各个不同时期所处的状态，人们采用了一个与进程相联系的数据块，称为进程控制块（用了一个与进程相联系的数据块，称为进程控制块（PCB）。系统利用系统利用 PCB 来控制和管理进程，所以来控制和管理进程，所以 PCB 是系统感知进程存在的唯一标志是系统感知进程存在的唯一标志39 进程既是调度的基本单位也是分配资源的基本单位40 操作系统的几种类型（批处理、实时、分时、网络、分布式），操作系统的四大特征（虚拟异步并发共享）的含义、虚拟：一个物理实体映射为若干个对应的逻辑实体分时或分空间一个物理实体映射为若干个对应的逻辑实体分时或分空间异步：操作系统必须随时对以不可预测的次序发生的事件进行响应操作系统必须随时对以不可预测的次序发生的事件进行响应并发：内存中放多道作业，内存中放多道作业，在一个时间段上来看，每一道作业都能不同程度地向前推进在一个时间段上来看，每一道作业都能不同程度地向前推进共享：系统中的资源可供多个并发的进程共同使用系统中的资源可供多个并发的进程共同使用批处理：用户将作业交到机房，操作员将一批作业输入到辅存（如磁盘）上，形成一个作业队列。当需要调入作业时，用户将作业交到机房，操作员将一批作业输入到辅存（如磁盘）上，形成一个作业队列。当需要调入作业时，管理程序从这一批中选几道作业调入内存，让它们进入内存运行。当一些作业完成时，管理程序调入另一些管理程序从这一批中选几道作业调入内存，让它们进入内存运行。当一些作业完成时，管理程序调入另一些程序，直到这一批作业全部完成。程序，直到这一批作业全部完成。实时：实时控制；实时信息处理；高响应性；高可靠性、高安全性实时控制；实时信息处理；高响应性；高可靠性、高安全性分时：15多个用户分时使用主机，每一用户分得一个时间片，用完这个时间片后操作系统将处理机分给另一用户，如多个用户分时使用主机，每一用户分得一个时间片，用完这个时间片后操作系统将处理机分给另一用户，如此循环，每一用户可以周期性地获得此循环，每一用户可以周期性地获得 CPU 使用权，这样每一用户都有一种独占使用权，这样每一用户都有一种独占 CPU 的感觉的感觉网络：客户客户/服务器模式（服务器模式（Client/Server）网络中的各个站点可以分为两大类：网络中的各个站点可以分为两大类：服务器：为客户提供服务如文件服务、打印服务、数据库服务等服务器：为客户提供服务如文件服务、打印服务、数据库服务等客户机：用户通过客户机访问服务器客户机：用户通过客户机访问服务器对等模式（对等模式（Peer-to-Peer）各个站点是对等的，它既可作为客户也可作为服务各个站点是对等的，它既可作为客户也可作为服务分布式：由多个分散的处理单元经网络的连接而形成的系统。由多个分散的处理单元经网络的连接而形成的系统。在分布式处理系统中，系统的处理和控制功能都分散在在分布式处理系统中，系统的处理和控制功能都分散在系统的各个处理单元上。系统中的所有任务可以动态地分配到各个处理单元中去系统的各个处理单元上。系统中的所有任务可以动态地分配到各个处理单元中去