2022年操作系统-计算题 .pdf
四、计算题1有以下三个作业，分别采用先来先服务和短作业优先作业调度算法。试问它们的平均周转时间各是什么？是否还可以给出一种更好的调度算法，使其平均周转时间优于这两种调度算法？作业到达时间所需 CPU 时间1 0.0 8 2 0.4 4 3 1.0 1 解： 1采用先来先服务作业调度算法时的实施过程如下。作业到达时间所需 CPU 时间开始时间完成时间周转时间1 0.0 8 0.0 8.0 8.0 2 0.4 4 8.0 12.0 11.6 3 1.0 1 12.0 13.0 12.0 这时，作业的调度顺序是123。其平均周转时间为：8 + 11.6 + 12/ 3 = 10.53 2采用短作业优先作业调度算法时的实施过程如下。作业到达时间所需 CPU 时间开始时间完成时间周转时间1 0.0 8 0.0 8.0 8.0 3 1.0 1 8.0 9.0 8.0 2 0.4 4 9.0 13.0 12.6 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 16 页这里要注意， 在作业 1 运行完毕进行作业调度时，作业 2 和 3 都已经到达。 由于是实行短作业优先作业调度算法，因此先调度作业3 运行，最后调度作业2 运行。 所以，这时的作业调度顺序是132。其平均周转时间为：8 + 8 + 12.6/ 3 = 9.53 3还可以有更好的作业调度算法，使其平均周转时间优于这两种调度算法。例如，如果知道在作业1 后面会来两个短作业，那么作业 1 到达后， 先不投入运行。 而是等所有作业到齐后，再按照短作业优先作业调度算法进行调度，具体实施过程如下。作业到达时间所需 CPU 时间开始时间完成时间周转时间3 1.0 1 1.0 2.0 1.0 2 0.4 4 2.0 6.0 5.6 1 0.0 8 6.0 14.0 14.0 这时的作业调度顺序是32 1。其平均周转时间为：1 + 5.6 + 14/ 3 = 6.87 2有一组作业，它们的到达时间和所需CPU时间如下所示，分别采用先来先服务和短作业优先作业调度算法，给出它们的调度顺序、作业周转时间以及平均周转时间。作业号到达时间所需 CPU 时间1 9:00 70 分钟2 9:40 30 分钟3 9:50 10 分钟4 10:10 5 分钟解： 1采用先来先服务作业调度算法时的实施过程如下：作业号到达时间所需 CPU 时间开始时间完成时间周转时间1 9:00 70 分钟9:00 10:10 70 分钟精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 16 页2 9:40 30 分钟10:10 10:40 60 分钟3 9:50 10 分钟10:40 10:50 60 分钟4 10:10 5 分钟10:50 10:55 45 分钟这时，作业的调度顺序是1234，其平均周转时间为：70 + 60 + 60 + 45 / 4 = 58.75 2采用短作业优先作业调度算法时的实施过程如下：作业号到达时间所需 CPU 时间开始时间完成时间周转时间1 9:00 70 分钟9:00 10:10 70 分钟4 10:10 5 分钟10:10 10:15 5 分钟3 9:50 10 分钟10:15 10:25 35 分钟2 9:40 30 分钟10:25 10:55 75 分钟这时，作业的调度顺序是1432，其平均周转时间为：70 + 5 + 35 + 75/ 4 = 46.25 三、简答题1. 对临界区的管理应遵循哪些基本准则？答：为了合理利用临界资源，保证进程互斥地进入临界区，对临界区的管理应遵循以下准则：1空闲让进。 当无进程处于临界区时，说明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源。2忙则等待。 当已有进程进入临界区时，说明临界资源正在被访问，因而其他试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。3 有限等待。对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入“死等”状态。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 16 页4 让权等待。 当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入 “忙等”状态。2. 什么是死锁？死锁的预防措施有哪些？答： 死锁是指多个并发执行的进程因竞争系统资源而造成的一种僵局，假设无外力作用，这些进程都将无法向前推进。由于产生死锁的4 个必要条件必须同时存在，系统才会产生死锁，所以，只要使4 个必要条件中至少有一个不能成立，就可以到达预防死锁的目的。1破坏“请求和保持” 条件，优点是简单、 易于实现且很安全；2破坏“不剥夺” 条件， 在采用这种方法预防死锁时，进程是在需要资源时才提出请求。这样， 一个已经保持了某些资源的进程，当它再提出新的资源要求而不能立即得到满足时，必须释放它已经保持的所有资源，待以后需要时再重新申请。这种预防死锁方法，实现起来比较复杂，且要付出很大代价。3破坏“循环等待”条件， 在这种方法中规定，系统将所有的资源按类型进行线形排队，并赋予不同的序号。这种预防死锁的策略与前两种策略比较，其资源利用率和系统吞吐量，都有较明显的改善。由于互斥性是某些资源的固有特性，所以一般不破坏互斥条件。3. 进程之间有哪些基本的通信方式？分别有什么特点？答：进程通信根据交换信息量的多少分为高级通信和低级通信。低级通信一般只传送一个或几个字节的信息，以到达控制进程执行速度的作用如P、V 操作；高级通信则要传送大量数据，目的不是为了控制进程的执行速度，而是为了交换信息。高级进程通信方式有很多种，大致可归为三类： 共享存储器、 管道通信和消息传递。 1共享存储器： 在内存种分配一片空间作为共享存储区。需要进行通信的进程把它附加到自己的地址空间中， 不需要时则把它取消。2管道通信： 它是连接两个命令的一个打开文件。一个命令向该文件中写入数据，为写者；另一个命令从该文件中读出数据，为读者。3消息传递：它以消息为单位在进程间进行数据交换。三、简答题1. 将一个程序装入内存通常有哪几种方式？答： 1绝对装入方式。绝对装入方式是由装入程序根据装入模块中的地址将程序和数据装入内存。 程序中所使用的绝对地址，既可在编译或汇编时给出，也可由程序员直接赋予。采用绝对装入方式的前提是地址空间的容量要足够且可用。这种方式对于单道程序是可行的。 但对于多道程序来讲，程序员需要准确地了解内存分区及使用的情况，正确定位程序或数据的内存地址，防止冲突的发生，而且一旦程序或数据被修改后，可能需要改变程序中的所有地址。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 16 页2可重定位装入方式。可重定位装入又称静态重定位装入，装入程序根据内存当前的实际使用情况， 将装入模块装入到内存适当的地方，地址变换在装入时一次完成。这种方式采用相对地址来存放程序和数据。一般设定程序的地址空间从0 开始，当需要装入该程序时，通过转换来确定它们在内存中的实际位置。3动态运行时装入方式。动态运行时装入又称动态重定位装入，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此， 装入内存后的所有地址都仍是相对地址。为使地址转换不影响指令的执行速度，这种方式需要特殊硬件的支持。2. 简述基本分页存储管理的主要优缺点。答：基本分页存储管理的主要优点有：不要求作业或进程的程序和数据在内存中连续存放，从而有效地解决了碎片问题；提高了内存的利用率，又有利于组织多道程序运行。主要缺点有： 采用动态地址转换机构降低了CPU的速度； 由于作业的地址空间不一定是存储块的整数倍， 因而最后一个存储块往往是装不满的，即出现了块内碎片问题；要求运行的作业必须全部装入内存才能运行，如果现有的空闲块不足以满足该作业的要求，作业只能等待， 浪费了内存空闲空间。3. 什么是虚拟存储器？虚拟存储器具有哪些特征？答： 所谓虚拟存储器， 是指具有请求调入功能和置换功能，把内存和外存结合起来使用，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量和内存大小无直接关系，主要由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而成本却又接近于外存。虚拟存储器的特征可以概括为以下4 点：1离散性：装入虚拟存储器的进程都是离散存放的，这是虚拟存储器的基础。2 多次性：一个作业被分成多次调入内存运行，即在作业运行时没必要将其全部装入，只需将当前要运行的那部分程序和数据装入内存，以后每当运行到尚未调入的那部分程序时，再将它调入。3对换性：允许在作业的运行过程中进行换进、换出。在进程运行期间，允许将那些暂不使用的程序和数据，从内存调至外存的对换区换出，待以后需要时再将它们从外存调至内存换进。4虚拟性：指能够从逻辑上扩充内存容量，虚拟出一个较大的逻辑空间，使用户所看到的内存容量远大于实际内存容量。4. 简述分页与分段的区别。答：分段和分页的区别：段式管理和页式管理都采用离散分配方式，且地址转换都需要硬件的支持。但它们也存在以下几个方面的不同：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 16 页1页是信息的物理单位，分页是为了提高内存的利用率，与源程序的逻辑结构无关，由系统自动完成，对用户是不可见的；段是信息的逻辑单位，分段是为了满足用户的需要，段对用户是可见的。2页的大小固定不变，由系统决定，页只能以页大小的整数倍地址开始；段的大小不固定，由用户编写的程序决定，段可以从内存的任何地址开始。3分页的逻辑地址空间是一维的，用一个记忆符就可以表示一个地址；分段的地址空间是二维的，为了标志一个地址，用户必须给出段号和段内地址。4页是信息的物理单位，页的共享和保护受到限制；段是信息的逻辑单位，段可以充分实现共享和保护。5段式管理与分区管理一样可能产生内存碎片，而页式管理则能很好地消除碎片。5. 常用的页面置换算法有哪几种？试比较它们的优缺点。答：常用的页面置换算法有最正确置换算法、先进先出置换算法、最近最久未使用置换算法和 Clock 置换算法。最正确置换算法性能最好，是一种理想情况下的页面置换算法，但无法实现； 先进先出置换算法简单， 易实现， 性能最差， 可能出现 Belady 现象， 淘汰驻留内存时间最长的页面，不实用； 最近最久未使用置换算法性能较好，是对最正确置换算法最好的逼近，根据历史信息选择淘汰页面，常被采用，但对硬件要求较高；Clock置换算法易发生缺页中断。6试述缺页中断与一般中断的区别。答：在电脑系统中，由于某些事件的出现，打断了当前程序的运行，而使CPU 去处理出现的事件，这称为“中断”。通常，电脑的硬件结构都是在执行完一条指令后，去检查有无中断事件发生的。如果有，那么就暂停当前程序的运行，而让CPU 去执行操作系统的中断处理程序， 这叫“中断响应”。 CPU在处理完中断后，如果不需要对CPU重新进行分配，那么就返回被中断进程的程序继续运行；如果需要进行CPU 的重新分配，那么操作系统就会去调度新进程。由上面的讲述可以看出，缺页中断与一般中断的区别如下。1两种中断产生的时刻不同：缺页中断是在执行一条指令中间时产生的中断，并立即转去处理； 而一般中断则是在一条指令执行完毕后，当硬件中断装置发现有中断请求时才去响应和处理。2处理完毕后的归属不同：缺页中断处理完后，仍返回到原指令去重新执行，因为那条指令并未执行； 而一般中断则是或返回到被中断进程的下一条指令去执行，因为上一条指令已经执行完了，或重新调度，去执行别的进程程序。三、简答题精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 16 页1. 在操作系统的设备管理中，为什么要引入缓冲？答：引入缓冲的主要原因有如下几点：1引入缓冲可以进一步改善CPU和 I/O 设备之间速度不匹配的情况。2可以协调逻辑记录大小和物理记录大小不一致的问题。3缓冲技术的引入还可以减少对CPU的中断次数，放宽CPU对中断响应时间的限制。2. 简述 SPOOLing 系统的主要特点。答： 1提高了I/O 的速度。从对低速I/O 设备进行的I/O 操作变为对输入井或输出井的操作，如同脱机操作一样，提高了I/O 速度，缓和了CPU 与低速 I/O 设备速度不匹配的矛盾。2将独占设备改造为共享设备。因为在SPOOLing 系统中，实际上并没为任何进程分配设备，而只是在输入井或输出井中为进程分配一个存储区和建立一张I/O 请求表。这样，便把独占设备改造为共享设备。3实现了虚拟设备功能。多个进程同时使用一个独享设备，而对每一进程而言，都认为自己独占这一设备，不过，该设备是逻辑上的设备。3. 磁盘调度算法有哪几种？各自的特点是什么？1先来先服务(FCFS) 。这是一种最简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次地得到处理，不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长。2最短寻道时间优先(SSTF) 。该算法选择这样的进程：其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。但这种算法不能保证平均寻道时间最短。3扫描 (SCAN) 算法。既能获得较好的寻道性能，又能防止“ 饥饿 ” 现象，故被广泛用于大、中、小型机器和网络中的磁盘调度。但SCAN也存在这样的问题：当磁头刚从里向外移动而越过了某一磁道时，恰好又有一进程请求访问此磁道，这时，该进程必须等待，待磁头继续从里向外， 然后再从外向里扫描完所有要访问的磁道后，才处理该进程的请求，致使该进程的请求被大大地推迟。4循环扫描 (CSCAN) 算法。为了减少SCAN 算法的延迟问题，CSCAN算法规定磁头单向移动，例如， 只是自里向外移动，当磁头移到最外的磁道并访问后，磁头立即返回到最里的欲访问的磁道，亦即将最小磁道号紧接着最大磁道号构成循环，进行循环扫描。三、简答题精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 16 页1简述文件的概念及分类。答：文件是在逻辑上具有完整意义的信息集合，是信息的一种组织形式，是存储在外存上的具有标志名的一组相关信息的集合。也可以说文件是一组相似记录的集合，它被用户和应用程序看作是一个实体，并可以通过名字访问。常见的文件分类有以下几种：按文件用途分类：1系统文件；2库文件；3用户文件。按存取控制权限分类：1只读文件；2读 /写文件； 3可执行文件；4不保护文件。按存放时限分类：1临时文件；2永久文件；3档案文件。按文件的信息流向分类：1输入文件；2输出文件；3输入 /输出文件。按文件的组织形式分类：1普通文件；2目录文件；3特殊文件。2. 简述文件、记录和数据项三者间的关系。答：数据项是电脑中操作系统处理的最小信息单位，是基本数据单元；记录是相关数据项的集合； 文件是一组相似记录的集合，它被用户和应用程序看作是一个实体，并可以通过名字访问。即：文件是相关“记录”的集合，而记录是相关“数据项”的集合，数据项是文件中不可再分解的最小“数据单位”。3. 文件控制块包含哪些内容？答： FCB一般应该包括以下内容：(1) 有关文件存取控制的信息。如文件名、 用户名、 文件主存取权限、授权者存取权限、文件类型和文件属性，即读写文件、执行文件、只读文件等。(2) 有关文件结构的信息。文件的逻辑结构，如记录类型、记录个数、记录长度、成组因子数等。 文件的物理结构，如文件所在设备名，文件物理结构类型，记录存放在外存的相对位置或文件第一块的物理块号，也可指出文件索引的所在位置等。(3) 有关文件使用信息。它包括已打开该文件的进程数、文件被修改的情况、文件当前大小等。(4) 有关文件管理信息。如文件建立日期、文件最近修改日期、文件访问日期、文件保留日期、记账信息等。4. 简述文件目录的作用。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 16 页答：文件目录一般包含文件控制块和索引结点。文件目录是文件系统的关键数据结构，它是文件系统实现“按名存取”的重要手段。为实现“按名存取”，必须建立文件名与外存空间中的物理地址的对应关系，表达这种对应关系的数据结构称为文件目录。5. 什么是文件的逻辑结构？答：文件的逻辑结构就是从用户观点出发所见到的文件结构，通常分为两种形式记录式文件和流式文件。记录式文件在逻辑上总是被看成一组顺序的记录集合，是一种有结构的文件组织。 它又分成定长记录文件和变长记录文件。流式文件又称无结构文件，是指文件内部不再划分记录。它是由一组相关信息组合成的有序字符流。6. 简述文件的检索过程。答：每当建立一个新文件时，系统就要为它设立一个FCB ，其中记录了这个文件的所有属性信息。 多个文件的FCB便组成了文件目录，文件目录也用文件形式保存起来，这个文件就是目录文件。 当用户要求存取某个文件时，系统查找目录文件， 先找到相对应的文件目录，然后，比较文件名就可以找到所寻文件的文件控制块FCB 文件目录项，再通过FCB指出的文件的文件信息相对位置或文件信息首块物理位置等，就能依次存取文件信息。7. 简述文件存储空间管理的几种常用的方法的优缺点。答：文件存储空间管理的几种常用的方法：空闲表法、空闲链表法、位示图法、成组链接法。空闲表法在内存分配上，虽然很少采用连续分配方式，然而在外在的管理中，由于它具有较高的分配速度，可以减少访问磁盘的I/O 频率， 因而在诸多分析方式中仍然占有一席之地。空闲链表法是将所有空闲盘区拉成一条空闲链表。根据构成链所用基本元素的不同，可以把链表分成两种形式。空闲盘块链： 这种方法的优点是分配和回收一个盘块的过程非常简单，但在为一个文件分配盘块时，可能要多次重复操作。空闲盘区链： 这是将磁盘上的所有空闲盘区每个盘区可包含假设干个盘块拉成一条链。在每个盘区上，除含有用于指示下一个空闲盘区的指针外，还应有能指明本盘区大小盘块数 的信息。分配盘区的方法与内存的动态分区分配类似，通常采用首次适应算法。在回收盘区时， 同样也要将回收区与相邻的空闲盘区合并。在采用首次适应算法时，为了提高对空闲盘区的检索速度，可以采用显式链接方法，即在内存中为空闲盘区建立一张链表。由于空闲表和空闲链表法在分配和回收空闲块时，都需在外存上查找空闲块号或链接块号，这需经过设备管理程序启动外设才能完成。为提高空闲表的分配、回收速度， 可以采用位示图进行管理。 空闲表和空闲链表法不适用于大型文件系统，因为这会使空闲块表或空闲块链太长。成组链接法是一种结合上述两种方法而形成的空闲块管理方法。通常在UNIX/Linux 系统中采用。它的实现方法是：将假设干个空闲块归为一组，将每组中的所有空精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 16 页闲块号放入其前一组的第一个空闲块号指示的磁盘块中，而将第一组中的所有空闲块号放入文件系统的超级块中的空闲块号表中。8为什么在使用文件之前，总是先将其打开后再用？答：有关文件的信息都存放在该文件的FCB里，只有找到文件的FCB ，才能获得它的一切信息。但FCB是在磁盘里。因此，只要对文件进行操作，就要到磁盘里去找它的FCB 。这种做法， 无疑影响了文件操作的执行速度。正因为如此， 操作系统才考虑在对文件进行操作前，先将其打开，把文件的FCB内容复制到内存中来。这样，查找文件的FCB ，就不必每次都要去访问磁盘。9. 简述常见的文件保护方法。答：通常，可以采用存取控制矩阵、存取控制表、权限表和口令等方法，来到达保护文件不受侵犯的目的。参见教材6.5.3 。二、简答题1. 简述数据加密模型的含义。答：数据加密过程就是通过加密系统把原始的数字信息明文，通过数据加密系统的加密方法将其变换成与明文完全不同的数字信息密文 的过程。 密文经过网络传输到达目的地后，再用数据加密系统的解密方法将密文复原成为明文。一个数据加密模型如下列图所示。它由 4 部分组成：1明文 plain text：被加密的文本称为明文。2密文 cipher text：加密后的文本称为密文。3加密解密算法：用于实现从明文密文到密文明文转换的公式、规则或程序。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 16 页4密钥：是一个具有特定长度的数字串，密钥的值是从大量的随机数中选取的。密钥是加密和解密算法中的关键参数。2. 简述系统安全性的内容与性质。答：系统安全性包括个方面的内容，即逻辑安全、物理安全和安全管理。其中，逻辑安全是指系统中信息资源的安全；物理安全是指系统设备及相关设施受到物理保护，使之免遭破坏或丧失；安全管理包括各种安全管理的政策和机制。逻辑安全包括以下几方面: 1保密性； 2完整性； 3可用性：要保证电脑网络系统的安全、可靠，必须保证系统实体有安全的物理环境条件。这个安全的物理环境条件是指机房及其设施的安全，主要包括以下内容： 1电脑系统的环境条件。2机房场地环境的选择。3机房的安全防护。系统安全性的性质：系统安全问题涉及的面较广，不仅与系统中所使用的硬件、软件设备的安全性能有关，而且与构造系统时所采用的方法有关，从而导致系统安全问题的性质更为复杂，主要表现为多面性、动态性、层次性和适度性。3. 简要说明DES加密处理的过程。答：第一阶段： 先将明文分出64 位的明文段，然后对64 位明文段做初始易位处理，得到，将其左移32 位，记为L0，右移 32 位，记为R0。第二阶段：对初始易位结果X0进行 16 次迭代处理，每一次使用56 位加密密钥Ki。输出的左 32 位 Li是输入的右32 位 Ri-1的复制；而输出的右32 位 Ri， 则是在密钥Ki的控制下，对输入的右32 位 Ri-1 做函数 f 的变换后的结果， 再与输入的左32 位 Li-1 进行异或运算而形成的，即：Li=Ri 1Ri=f(Ri1,Ki)Li1第三阶段：把经过16 次迭代处理的结果(64 位)的左 32 位与右 32 位互易位置。第四阶段：进行初始易位的逆变换。4. 使用哪些方法可以提高用户认证的安全性？答：用以提高用户认证的安全性的方法有：使用加密技术和身份验证、数字签名、 生物标志的认证技术、智能卡识别技术等。5. 列举几种采用生物识别技术的认证。答：指纹或声音、智能卡。6. 简述如何进行职业道德教育与法制建设。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 16 页答： 1为了保证电脑系统的安全，对从事电脑工作人员的职业道德教育也是十分重要的。国家必须制定出有关的准则，从管理制度及社会宣传教育等各方面综合考虑加以解决。所有电脑用户，特别是管理者，除了要加强业务学习外，更需要加强道德修养。2由于电脑犯罪已经是造成对国家安全、社会稳定、财产金融、经济建设、私人保密权利等的巨大威胁，因此，国家必须从法律和政策上采取有效对策。而且，由于电脑犯罪的最大特点是高技术智能犯罪，对于熟悉电脑的人，掌握作案技术很容易，而且盗窃大量钱财和信息不易被发现，甚至不留痕迹， 这给侦破工作带来了极大困难。这一犯罪特点也给传统法律提出了新的问题，因为， 原有法规中的内容，用于裁定电脑犯罪时已很不适应，甚至有点牵强附会。因此，有必要制定新的法规。总之，要想保证系统的安全，除了需要发展安全技术外，更需要培养用户的安全意识，加强电脑专业人员的职业道德教育，以及完善防范电脑犯罪的法制建设。四、计算题1有两个用户进程A 和 B，在执行过程中都要使用系统中同一台打印机输出各自的计算结果。1试说明A、 B 两进程之间存在什么样的制约关系？2为保证这两个进程能正确地打印出各自的结果，试写出利用记录型信号量机制实现进程的同步算法。答： 1 A、B 两进程之间存在互斥的制约关系。因为打印机属于临界资源，必须一个进程使用完之后另一个进程才能使用。2设 mutex 用于互斥的信号量，初值为1。进程 A 进程 B. . . . P(mutex) P(mutex) 申请打印机申请打印机使用打印机使用打印机精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 16 页V(mutex)V(mutex) . .2有一个阅览室，共有100 个座位，用一张表来管理它，每个表目记录座号和读者。读者进入时要先在表上登记，退出时要注销登记。试用信号量及其P、V 操作来描述各个读者“进入”和“注销”工作之间的同步关系。解： 在管理读者“进入”和“注销”阅览室的工作中，存在这样一些制约关系：1100 个座位是读者共同使用的资源，因此要用一个资源分配信号量来管理它；2读者“进入”阅览室时，要申请座位。只有申请到座位才能进入，否则应该等待到座位的释放；3没有读者时，不能做“注销”工作，必须等到有了读者才能做。因此，可以设置两个信号量：S1：初值为100，管理座位的分配；S2：初值为0，控制“注销”与“进入”间取得同步。“进入”与“注销”两个进程的流程如下列图所示。在读者进入时，调用“进入”进程，通过P(S1)来申请座位。如果申请到，就可以办理阅览手续。如果 100 个座位都申请完毕， 那么第 101 个读者就只有在关于S1的队列上等待，等到有人调用“注销”进程执行V(S1)。在有读者离去时，就调用“注销”进程。四、计算题1.假设在一基本分页存储管理系统中，某作业的页表如下所示：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 16 页页号块号0 1 2 3 2 3 1 6 已知页面大小为1024 字节，试将逻辑地址1011、2148、4000、5012 转化为相应的物理地址。解：物理地址由页号P 和页内地址W 两部分组成，P 等于逻辑地址除以页面大小的除数， W 等于逻辑地址除以页面大小的余数，物理块号和页面大小相同。则逻辑地址为1011 的物理地址算法如下：P=1011/1024=0,W=1011, 据页表可知页号为0 的页对应的是物理块号为2 的块，所以物理地址=2*1024+1011=3059 ；同理，逻辑地址为2148 的物理地址： P=2148/1024=2,W=100 。页号为 2 对应物理块号1，物理地址 =1*1024+100=1124 ；逻辑地址为4000 的物理地址：P=4000/1024=3,W=904 。页号为3 对应物理块号6，物理地址 =6*1024+904=7048 ；逻辑地址为5012 的物理地址： P=5012/1024=4 。页号为4 的页面在页表中没有，所以要产生页面中断，请求将外存中的页面调入内存。2在可变分区存储管理中，按地址法组织当前的空闲分区，其大小分别为10KB，4KB，20KB，18KB，7KB，9KB，12KB和 15KB，现在依次有3 个存储请求为12KB，10KB，9KB，问使用最先适应算法时的分配情形如何？那么最正确适应算法、最坏适应算法呢？解： 用表来说明实行各种分配算法时的情形。1最先适应算法：请求队列最先适应算法初始10K 4K 20K 18K 7K 9K 12K 15K 12K 10K 4K 8K 18K 7K 9K 12K 15K 10K 0 4K 8K 18K 7K 9K 12K 15K 9K 0 4K 8K 9K 7K 9K 12K 15K 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 16 页2最正确适应算法：请求队列最正确适应算法初始10K 4K 20K 18K 7K 9K 12K 15K 12K 10K 4K 20K 18K 7K 9K 0 15K 10K 0 4K 20K 18K 7K 9K 0 15K 9K 0 4K 20K 18K 7K 0 0 15K 3最坏适应算法：请求队列最坏适应算法初始10K 4K 20K 18K 7K 9K 12K 15K 12K 10K 4K 8K 18K 7K 9K 12K 15K 10K 10K 4K 8K 8K 7K 9K 12K 15K 9K 10K 4K 8K 8K 7K 9K 12K 6K 可见，分配算法不同，选择的分配对象也不一样。3 某请求分页式存储管理系统，接收一个共7 页的作业。 作业运行时的页面走向如下：1，2，3， 4，2，1，5， 6，2，1，2， 3，7，6，3， 2，1，2，3， 6。假设采用最近最久未用页面淘汰算法， 作业在得到2 块和 4 块内存空间时， 各会产生出多少次缺页中断？如果采用先进先出页面淘汰算法时，结果又如何？解： 1采用最近最久未用LRU页面淘汰算法，作业在得到2 块内存空间时所产生的缺页中断次数为18 次，如下列图 a所示；在得到4块内存空间时所产生的缺页中断次数为 10 次，如下列图b所示。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 16 页2采用先进先出FIFO 页面淘汰算法，作业在得到2 块内存空间时所产生的缺页中断次数为18 次，如下列图a所示；在得到4 块内存空间时所产生的缺页中断次数为14次，如下列图b所示。四、计算题磁盘请求以10、22、20、 2、40、 6、38 柱面的次序到达磁盘驱动器。移动臂移动一个柱面需要6ms，分别实行先来先服务算法、最短寻道时间优先算法和扫描算法时，各需要多少总的查找时间？假定磁臂起始时定位于柱面20。解：1先来先服务算法：调度的顺序是2010 2220240638，总共划过的柱面数是10+12+2+18+38+34+32=146，因此总的查找时间为：1466=876ms。2最短寻道时间优先：调度的顺序是202210 623840由于磁臂起始时定位于柱面20，所以可以把后面第20 柱面的访问立即进行，总共划过的柱面数是2+12+4+4+36+2=60，因此总的查找时间为：606=360ms。3扫描算法初始由外向里移动：调度的顺序是202238 401062由于磁臂起始时定位于柱面20，所以可以把后面第20 柱面的访问立即进行，总共划过的柱面数是 2+16+2+30+4+4=58，因此总的查找时间为：586=348ms。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 16 页
