20130403–操作系统作业及参考解析.docVIP

《操作系统》作业及参考答案 分别化简如下三个图所示的资源分配图，并判断系统中是否存在死锁。 （图1）（图2）（图3） 参考答案：图1—不可完全简化，有死锁存在；图2和图3可完全简化，没有死锁存在。 可采用哪几种方式将程序装入内存？它们分别适用于何种场合？参考答案：首先由编译程序将用户源代码编译成若干目标模块，再由链接程序将编译后形成的目标模块和所需的库函数链接在一起，组成一个装入模块，再由装入程序将装入模块装入内存；装入模块的方式有：绝对装入方式、可重定位方式和动态运行时装入方式；绝对装入方式适用于单道程序环境下；可重定位方式适用于多道程序环境下；动态运行时装入方式也适用于多道程序环境下。 什么叫静态链接、装入时动态链接和运行时的动态链接？参考答案：静态链接是指事先进行链接形成一个完整的装入模块，以后不再拆开的链接方式；装入时动态链接是指目标模块在装入内存时，边装入边链接的链接方式；运行时的动态链接是将某些目标模块的链接推迟到执行时才进行。 什么叫重定位？有哪几种重定位方式？参考答案：由于一个作业装入到与其地址空间不一致的存储空间所引起的需要对其有关地址部分进行调整的过程就称为重定位（实质是一个地址变换过程/地址映射）。重定位可以分为静态重定位和动态重定位。 为什么要引入动态重定位？如何实现？参考答案：为了在程序执行过程中，每当访问指令或数据时，将要访问的程序或数据的逻辑地址转换成物理地址，引入了动态重定位。动态重定位的实现：可在系统中增加一个重定位寄存器，用它来存放程序在内存中的起始地址，程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的，从而实现动态重定位。 有作业序列：作业A要求18KB，作业B要求25KB，作业C要求30KB。初始内存分配情况如下图所示，问首次适应算法、最佳适应算法和最坏适应算法中哪些能满足该作业序列的分配？并写出判断的过程。 参考答案：（1）对于首次适应算法，作业A分配30KB的空闲分区，作业B分配45KB的空闲分区，此时无法为作业C分配合适的空闲分区了。（2）对于最佳适应算法，作业A分配20KB的空闲分区，作业B分配30KB的空闲分区，作业C分配45KB的空闲分区。（3）对于最坏适应算法，作业A分配45KB的空闲分区，作业B 分配30KB的空闲分区，此后无法为作业C分配合适的空闲分区了。最佳适应算法能满足该作业序列的需求。 采用可变分区方式管理主存空间时，若主存中按地址递增顺序依次有五个空闲区，空闲区的大小分别为15KB，28KB，10KB，226KB，110KB，现有五个作业JA，JB，JC，JD和JE，它们所需的主存依次为10KB、15KB，l02KB，26KB和180KB，如果采用最先适应分配算法能把这五个作业按JA～JE的次序全部装入主存吗?用什么分配算法装入这五个作业可使主存的利用率最高?参考答案：按最先适应分配算法，这五个作业不能全部依次装入主存，因为JE(180K)无法装入主存。用最佳适应分配算法，能使主存的利用率最高，此时，这五个主存块依次装入了五个作业，它们是：JB(15K)，JD(26K)，JA(10K)，JE(180K)，JC(102K)。 请说明动态分区分配方式中内存分区回收时的四种情况。参考答案：（1）回收分区R上面邻接一个空闲分区F1，合并后首地址为空闲分区F1的首地址，大小为F1和R二者大小之和。这种情况下，回收后空闲分区表中表项数不变。（2）回收分区R下面邻接一个空闲分区F2，合并后首地址为回收分区R的首地址，大小为R和F2二者大小之和。这种情况下，回收后空闲分区表中表项数不变。（3）回收分区R上下邻接空闲分区F1和F2，合并后首地址为上空闲分区F1的首地址，大小为F1、R和F2三者大小之和。这种情况下，回收后空闲分区表中表项数不但没有增加，反而减少一项。（4）回收分区R不邻接空闲分区，这时在空闲分区表中新建一表项，并填写分区首地址、大小等信息。这种情况下，回收后空闲分区表中表项数增加一项。 考虑一个伙伴系统，在当前分配下的一个特定块地址为011011110000，（1）如果块大小为4，它的伙伴的二进制地址为多少？（2）如果块大小为16，它的伙伴的二进制地址为多少？参考答案：（1）011011110100 （2）011011100000 令buddyk(x)表示大小为2k、地址为x 的块的伙伴系统地址，试写出buddyk(x)的通用表达式。 假设最初的内存块大小为1MB，有用户进程按下列顺序请求和释放内存空间，画出利用伙伴系统分配和回收内存空间的示意图：A请求100KB，B请求240KB，C请求64KB，D请求