《操作系统精髓与设计原理·第六版》中文版答案.doc 71页

'复习题答案第1章计算机系统概述1.1列出并简要地定义计算机的四个主要组成部分。主存储器，存储数据和程序；算术逻辑单元，能处理二进制数据；控制单元，解读存储器中的指令并且使他们得到执行；输入/输出设备，由控制单元管理。1.2定义处理器寄存器的两种主要类别。用户可见寄存器：优先使用这些寄存器，可以使机器语言或者汇编语言的程序员减少对主存储器的访问次数。对高级语言而言，由优化编译器负责决定把哪些变量应该分配给主存储器。一些高级语言，如C语言，允许程序言建议编译器把哪些变量保存在寄存器中。控制和状态寄存器：用以控制处理器的操作，且主要被具有特权的操作系统例程使用，以控制程序的执行。1.3一般而言，一条机器指令能指定的四种不同操作是什么？处理器－寄存器：数据可以从处理器传送到存储器，或者从存储器传送到处理器。处理器－I/O：通过处理器和I/O模块间的数据传送，数据可以输出到外部设备，或者从外部设备输入数据。数据处理：处理器可以执行很多关于数据的算术操作或逻辑操作。控制：某些指令可以改变执行顺序。1.4什么是中断？中断：其他模块（I/O，存储器）中断处理器正常处理过程的机制。1.5多中断的处理方式是什么？处理多中断有两种方法。第一种方法是当正在处理一个中断时，禁止再发生中断。第二种方法是定义中断优先级，允许高优先级的中断打断低优先级的中断处理器的运行。1.6内存层次的各个元素间的特征是什么？存储器的三个重要特性是：价格，容量和访问时间。1.7什么是高速缓冲存储器？高速缓冲存储器是比主存小而快的存储器，用以协调主存跟处理器，作为最近储存地址的缓冲区。1.8列出并简要地定义I/O操作的三种技术。可编程I/O：当处理器正在执行程序并遇到与I/O相关的指令时，它给相应的I/O模块发布命令（用以执行这个指令）；在进一步的动作之前，处理器处于繁忙的等待中，直到该操作已经完成。中断驱动I/O：当处理器正在执行程序并遇到与I/O相关的指令时，它给相应的I/O模块发布命令，并继续执行后续指令，直到后者完成，它将被I/O模块中断。如果它对于进程等待I/O的完成来说是不必要的，可能是由于后续指令处于相同的进程中。否则，此进程在中断之前将被挂起，其他工作将被执行。直接存储访问：DMA模块控制主存与I/O模块间的数据交换。处理器向DMA模块发送一个传送数据块的请求，（处理器）只有当整个数据块传送完毕后才会被中断。1.9空间局部性和临时局部性间的区别是什么？空间局部性是指最近被访问的元素的周围的元素在不久的将来可能会被访问。临时局部性（即时间局部性）是指最近被访问的元素在不久的将来可能会被再次访问。1.10开发空间局部性和时间局部性的策略是什么？空间局部性的开发是利用更大的缓冲块并且在存储器控制逻辑中加入预处理机制。时间局部性的开发是利用在高速缓冲存储器中保留最近使用的指令及数据，并且定义缓冲存储的优先级。第2章操作系统概述71 2.1操作系统设计的三个目标是什么？方便：操作系统使计算机更易于使用。有效：操作系统允许以更有效的方式使用计算机系统资源。扩展的能力：在构造操作系统时，应该允许在不妨碍服务的前提下有效地开发、测试和引进新的系统功能。2.2什么是操作系统的内核？内核是操作系统最常使用的部分，它存在于主存中并在特权模式下运行，响应进程调度和设备中断。2.3什么是多道程序设计？多道程序设计是一种处理操作，它在两个或多个程序间交错处理每个进程。2.4什么是进程？进程是一个正在执行的程序，它被操作系统控制和选择。2.5操作系统是怎么使用进程上下文的？执行上下文又称为进程状态，是操作系统用来管理和控制所需的内部数据。这种内部信息和进程是分开的，因为操作系统信息不允许被进程直接访问。上下文包括操作系统管理进程以及处理器正确执行进程所需要的所有信息，包括各种处理器寄存器的内容，如程序计数器和数据寄存器。它还包括操作系统使用的信息，如进程优先级以及进程是否在等待特定I/O事件的完成。2.6列出并简要介绍操作系统的五种典型存储管理职责。进程隔离：操作系统必须保护独立的进程，防止互相干涉数据和存储空间。自动分配和管理：程序应该根据需要在存储层次间动态的分配，分配对程序员是透明的。因此，程序员无需关心与存储限制有关的问题，操作系统有效的实现分配问题，可以仅在需要时才给作业分配存储空间。2.7解释实地址和虚地址的区别。虚地址指的是存在于虚拟内存中的地址，它有时候在磁盘中有时候在主存中。实地址指的是主存中的地址。2.8描述轮循调度技术。轮循调度是一种调度算法，所有的进程存放在一个环形队列中并按固定循序依次激活。因为等待一些事件（例如：等待一个子进程或一个I/O操作）的发生而不能被处理的进程将控制权交给调度器。2.9解释单体内核和微内核的区别。单体内核是一个提供操作系统应该提供的功能的大内核，包括调度、文件系统、网络、设备驱动程序、存储管理等。内核的所有功能成分都能够访问它的内部数据结构和程序。典型情况下，这个大内核是作为一个进程实现的，所有元素都共享相同的地址空间。微内核是一个小的有特权的操作系统内核，只提供包括进程调度、内存管理、和进程间通信等基本功能，要依靠其他进程担当起和操作系统内核联系作用。2.10什么是多线程？多线程技术是指把执行一个应用程序的进程划分成可以同时运行的多个线程。第3章进程描述和控制3.1什么是指令跟踪？指令跟踪是指为该进程而执行的指令序列。3.2通常那些事件会导致创建一个进程？新的批处理作业；交互登录；操作系统因为提供一项服务而创建；由现有的进程派生。（表3.1）3.3对于图3.6中的进程模型，请简单定义每个状态。运行态：该进程正在执行。就绪态：进程做好了准备，只要有机会就开始执行。阻塞态：进程在某些事件发生前不能执行，如I/O操作完成。新建态：刚刚创建的进程，操作系统还没有把它加入到可执行进程组中。71 退出态：操作系统从可执行进程组中释放出的进程，或者是因为它自身停止了，或者是因为某种原因被取消。3.4抢占一个进程是什么意思？处理器为了执行另外的进程而终止当前正在执行的进程，这就叫进程抢占。3.5什么是交换，其目的是什么？交换是指把主存中某个进程的一部分或者全部内容转移到磁盘。当主存中没有处于就绪态的进程时，操作系统就把一个阻塞的进程换出到磁盘中的挂起队列，从而使另一个进程可以进入主存执行。3.6为什么图3.9（b）中有两个阻塞态？有两个独立的概念：进程是否在等待一个事件（阻塞与否）以及进程是否已经被换出主存（挂起与否）。为适应这种2*2的组合，需要两个阻塞态和两个挂起态。3.7列出挂起态进程的4个特点。1.进程不能立即执行。2.进程可能是或不是正在等待一个事件。如果是，阻塞条件不依赖于挂起条件，阻塞事件的发生不会使进程立即被执行。3.为了阻止进程执行，可以通过代理把这个进程置于挂起态，代理可以是进程自己，也可以是父进程或操作系统。4.除非代理显式地命令系统进行状态转换，否则进程无法从这个状态中转移。3.8对于哪类实体，操作系统为了管理它而维护其信息表？内存、I/O、文件和进程。3.9列出进程控制块中的三类信息。进程标识，处理器状态信息，进程控制信息。3.10为什么需要两种模式（用户模式和内核模式）？用户模式下可以执行的指令和访问的内存区域都受到限制。这是为了防止操作系统受到破坏或者修改。而在内核模式下则没有这些限制，从而使它能够完成其功能。3.11操作系统创建一个新进程所执行的步骤是什么？1.给新进程分配一个唯一的进程标识号。2.给进程分配空间。3.初始化进程控制块。4.设置正确的连接。5.创建或扩充其他的数据结构。3.12中断和陷阱有什么区别？中断与当前正在运行的进程无关的某些类型的外部事件相关，如完成一次I/O操作。陷阱与当前正在运行的进程所产生的错误或异常条件相关，如非法的文件访问。3.13举出中断的三个例子。时钟终端，I/O终端，内存失效。3.14模式切换和进程切换有什么区别？发生模式切换可以不改变当前正处于运行态的进程的状态。发生进程切换时，一个正在执行的进程被中断，操作系统指定另一个进程为运行态。进程切换需要保存更多的状态信息。第4章线程、对称多处理和微内核4.1表3.5列出了在一个没有线程的操作系统中进程控制块的基本元素。对于多线程系统，这些元素中那些可能属于线程控制块，那些可能属于进程控制块？这对于不同的系统来说通常是不同的，但一般来说，进程是资源的所有者，而每个线程都有它自己的执行状态。关于表3.5中的每一项的一些结论如下：进程标识：进程必须被标识，而进程中的每一个线程也必须有自己的ID。处理器状态信息：这些信息通常只与进程有关。进程控制信息：调度和状态信息主要处于线程级；数据结构在两级都可出现；进程间通信和线程间通信都可以得到支持；特权在两级都可以存在；存储管理通常在进程级；资源信息通常也在进程级。4.2请列出线程间的模式切换比进程间的模式切换开销更低的原因。71 包含的状态信息更少。4.3在进程概念中体现出的两个独立且无关的特点是什么？资源所有权和调度/执行。4.4给出在单用户多处理系统中使用线程的四个例子。前台和后台操作，异步处理，加速执行和模块化程序结构。4.5哪些资源通常被一个进程中的所有线程共享？例如地址空间，文件资源，执行特权等。4.6列出用户级线程优于内核级线程的三个优点。1.由于所有线程管理数据结构都在一个进程的用户地址空间中，线程切换不需要内核模式的特权，因此，进程不需要为了线程管理而切换到内核模式，这节省了在两种模式间进行切换（从用户模式到内核模式；从内核模式返回用户模式）的开销。2.调用可以是应用程序专用的。一个应用程序可能倾向于简单的轮询调度算法，而另一个应用程序可能倾向于基于优先级的调度算法。调度算法可以去适应应用程序，而不会扰乱底层的操作系统调度器。3.用户级线程可以在任何操作系统中运行，不需要对底层内核进行修改以支持用户级线程。线程库是一组供所有应用程序共享的应用级软件包。4.7列出用户级线程相对于内核级线程的两个缺点。1.在典型的操作系统中，许多系统调用都会引起阻塞。因此，当用户级线程执行一个系统调用时，不仅这个线程会被阻塞，进程中的所有线程都会被阻塞。2.在纯粹的用户级进程策略中，一个多线程应用程序不能利用多处理技术。内核一次只把一个进程分配给一个处理器，因此一次进程中只能有一个线程可以执行。4.8定义jacketing。Jacketing通过调用一个应用级的I/O例程来检查I/O设备的状态，从而将一个产生阻塞的系统调用转化为一个不产生阻塞的系统调用。4.9简单定义图4.8中列出的各种结构。SIMD：一个机器指令控制许多处理部件步伐一致地同时执行。每个处理部件都有一个相关的数据存储空间，因此，每条指令由不同的处理器在不同的数据集合上执行。MIMD：一组处理器同时在不同的数据集上执行不同的指令序列。主/从：操作系统内核总是在某个特定的处理器上运行，其他处理器只用于执行用户程序，还可能执行一些操作系统实用程序。SMP：内核可以在任何处理器上执行，并且通常是每个处理器从可用的进程或线程池中进行各自的调度工作。集群：每个处理器都有一个专用存储器，而且每个处理部件都是一个独立的计算机。4.10列出SMP操作系统的主要设计问题。同时的并发进程或线程，调度，同步，存储器管理，可靠性和容错。4.11给出在典型的单体结构操作系统中可以找到且可能是微内核操作系统外部子系统中的服务和功能。设备驱动程序，文件系统，虚存管理程序，窗口系统和安全服务。4.12列出并简单解释微内核设计相对于整体式设计的七个优点。一致接口：进程不需要区分是内核级服务还是用户级服务，因为所有服务都是通过消息传递提供的。可扩展性：允许增加新的服务以及在同一个功能区域中提供多个服务。灵活性：不仅可以在操作系统中增加新功能，还可以删减现有的功能，以产生一个更小、更有效的实现。可移植性：所有或者至少大部分处理器专用代码都在微内核中。因此，当把系统移植到一个处理器上时只需要很少的变化，而且易于进行逻辑上的归类。可靠性：小的微内核可以被严格地测试，它使用少量的应用程序编程接口（API），这就为内核外部的操作系统服务产生高质量的代码提供了机会。分布式系统支持：微内核通信中消息的方向性决定了它对分布式系统的支持。面向对象操作系统环境：在微内核设计和操作系统模块化扩展的开发中都可以借助面向对象方法的原理。71 4.13解释微内核操作系统可能存在的性能缺点。通过微内核构造和发送信息、接受应答并解码所花费的时间比一次系统调用的时间要多。4.14列出即使在最小的微内核操作系统中也可以找到的三个功能。低级存储器管理，进程间通信（IPC）以及I/O和中断管理。4.15在微内核操作系统中，进程或线程间通信的基本形式是什么？消息。第5章并发性：互斥和同步5.1列出与并发相关的四种设计问题进程间的交互，共享资源之间的竞争，多个进程的同步问题，对进程的处理器时间分配问题5.2列出并发的三种上下文多个应用程序，结构化应用程序，操作系统结构5.3执行并发进程的最基本要求是什么？加强互斥的能力5.4列出进程间的三种互相知道的程度，并简单地给出各自的定义。进程间互相不知道对方：这是一些独立的进程，他们不会一起工作。进程间间接知道对方：这些进程并不需要知道对方的进程ID号，但他们共享访问某些对象，如一个I/O缓冲区。进程间直接知道对方：这些进程可以通过进程ID号互相通信，用于合作完成某些活动。5.5竞争进程和合作进程进程间有什么区别。竞争进程需要同时访问相同的资源，像磁盘，文件或打印机。合作进程要么共享访问一个共有的资源，像一个内存访问区，要么就与其他进程相互通信，在一些应用程序或活动上进行合作。5.6列出与竞争进程相关的三种控制问题，并简单地给出各自的定义。互斥：竞争进程仅可以访问一个临界资源（一次仅有一个进程可以访问临界资源），并发机制必须满足一次只有一个进程可以访问临界资源这个规则。死锁：如果竞争进程需要唯一的访问多于一个资源，并且当一个进程控制着一个进程，且在等待另一个进程，死锁可能发生。饥饿：一组进程的一个可能会无限期地拒绝进入到一个需要资源，因为其他成员组成垄断这个资源。5.7列出对互斥的要求。1.必须强制实施互斥：在具有关于相同资源或共享对象的临界区的所有进程中，一次只允许一个进程进入临界区。2.一个在临界区停止的进程必须不干涉其他进程。3.绝不允许出现一个需要访问临界区的进程被无限延迟的情况，即不会饿死或饥饿。4.当没有进程在临界区中时，任何需要进入临界区的进程必须能够立即进入。5.对相关进程的速度和处理器的数目没有任何要求和限制。6.一个进程驻留在临界区中的时间是有限的。5.8在信号量上可以执行什么操作。1.一个信号量可以初始化成非负数。2.wait操作使信号量减1，如果值为负数，那么进程执行wait就会受阻。3signal操作使信号量增加1，如果小于或等于0，则被wait操作阻塞的进程被解除阻塞。5.9二元信号量与一般信号量有什么区别。二元信号量只能取0或1，而一般信号量可以取任何整数。5.10强信号量与弱信号量有什么区别。强信号量要求在信号量上等待的进程按照先进先出的规则从队列中移出。弱信号量没有此规则。71 5.11.什么是管程。管程是由一个或多个过程，一个初始化序列和局部数据组成的软件模块。5.12对于消息，有阻塞和无阻塞有什么区别？发送者和接收者任一方阻塞则消息传递需要等待，都无阻塞则不需等待。5.13通常与读者-写者问题相关联的有哪些条件？1.任意多的读进程可以同时读这个文件2.一次只有一个写进程可以往文件中写3.如果一个写进程正在往文件中写时，则禁止任何读进程读文件。第6章并发性：死锁和饥饿6.1给出可重用资源和可消费资源的例子。可重用资源：处理器，Ｉ/Ｏ通道，主存和辅存，设备以及诸如文件，数据库和信号量之类的数据结构。可消费资源：中断，信号，消息和Ｉ/Ｏ缓冲区中的信息。6.2可能发生死锁所必须的三个条件是什么？互斥，占有且等待，非抢占。6.3产生死锁的第４个条件是什么？循环等待。6.4如何防止占有且等待的条件？可以要求进程一次性地请求所有需要的资源，并且阻塞这个资源直到所有请求都同时满足。6.5给出防止无抢占条件的两种方法。第一种，如果占有某些资源的一个进程进行进一步资源请求被拒绝，则该进程必须释放它最初占用的资源，如果有必要，可再次请求这些资源和另外的资源。第二种，如果一个进程请求当前被另一个进程占有的一个资源，则操作系统可以抢占另一个进程，要求它释放资源。6.6如何防止循环等待条件？可以通过定义资源类型的线性顺序来预防。如果一个进程已经分配到了Ｒ类型的资源，那么它接下来请求的资源只能是那些排在Ｒ类型之后的资源类型。6.7死锁避免，检测和预防之间的区别是什么？死锁预防是通过间接地限制三种死锁必要条件的至少一个或是直接地限制循环等待的发生来避免死锁的出现。死锁避免允许可能出现的必要条件发生，但是采取措施确保不会出现死锁的情况。而死锁检测允许资源的自由分配，采取周期性的措施来发现并处理可能存在的死锁情况。第7章内存管理7.1内存管理需要满足哪些需求？重定位、保护、共享、逻辑组织和物理组织。7.2为什么需要重定位进程的能力？通常情况下，并不能事先知道在某个程序执行期间会有哪个程序驻留在主存中。此外还希望通过提供一个巨大的就绪进程池，能够把活动进程换入和换出主存，以便使处理器的利用率最大化。在这两种情况下，进程在主存中的确切位置是不可预知的。7.3为什么不可能在编译时实施内存保护？71 由于程序在主存中的位置是不可预测的，因而在编译时不可能检查绝对地址来确保保护。并且，大多数程序设计语言允许在运行时进行地址的动态计算（例如，通过计算数组下标或数据结构中的指针）。因此，必须在运行时检查进程产生的所有存储器访问，以便确保它们只访问了分配给该进程的存储空间。7.4允许两个或多个进程访问进程的某一特定区域的原因是什么？如果许多进程正在执行同一程序，则允许每个进程访问该程序的同一个副本要比让每个进程有自己单独的副本更有优势。同样，合作完成同一任务的进程可能需要共享访问同一个数据结构。7.5在固定分区方案中，使用大小不等的分区有什么好处？通过使用大小不等的固定分区：1.可以在提供很多分区的同时提供一到两个非常大的分区。大的分区允许将很大的进程全部载入主存中。2.由于小的进程可以被放入小的分区中，从而减少了内部碎片。7.6内部碎片和外部碎片有什么区别？内部碎片是指由于被装入的数据块小于分区大小而导致的分区内部所浪费的空间。外部碎片是与动态分区相关的一种现象，它是指在所有分区外的存储空间会变成越来越多的碎片的。7.7逻辑地址、相对地址和物理地址间有什么区别？逻辑地址是指与当前数据在内存中的物理分配地址无关的访问地址，在执行对内存的访问之前必须把它转化成物理地址。相对地址是逻辑地址的一个特例，是相对于某些已知点（通常是程序的开始处）的存储单元。物理地址或绝对地址是数据在主存中的实际位置。7.8页和帧之间有什么区别？在分页系统中，进程和磁盘上存储的数据被分成大小固定相等的小块，叫做页。而主存被分成了同样大小的小块，叫做帧。一页恰好可以被装入一帧中。7.9页和段之间有什么区别？分段是细分用户程序的另一种可选方案。采用分段技术，程序和相关的数据被划分成一组段。尽管有一个最大段长度，但并不需要所有的程序的所有段的长度都相等。第8章虚拟内存8.1简单分页与虚拟分页有什么区别？简单分页：一个程序中的所有的页都必须在主存储器中程序才能正常运行，除非使用覆盖技术。拟内存分页：不是程序的每一页都必须在主存储器的帧中来使程序运行，页在需要的时候进行读取。8.2解释什么是抖动。虚拟内存结构的震动现象，在这个过程中处理器大部分的时间都用于交换块，而不是执行指令。8.3为什么在使用虚拟内存时，局部性原理是至关重要的？可以根据局部性原理设计算法来避免抖动。总的来说，局部性原理允许算法预测哪一个当前页在最近的未来是最少可能被使用的，并由此就决定候选的替换出的页。8.4哪些元素是页表项中可以找到的元素？简单定义每个元素。帧号：用来表示主存中的页来按顺序排列的号码。存在位（P）：表示这一页是否当前在主存中。修改位（M）：表示这一页在放进主存后是否被修改过。8.5转移后备缓冲器的目的是什么？转移后备缓冲器（TLB）是一个包含最近经常被使用过的页表项的高速缓冲存储器。它的目的是为了减少从磁盘中恢复一个页表项所需的时间。8.6简单定义两种可供选择的页读取策略。在请求式分页中，只有当访问到某页中的一个单元时才将该页取入主存。在预约式分页中，读取的并不是页错误请求的页。8.7驻留集管理和页替换策略有什么区别？驻留集管理主要关注以下两个问题：（1）给每个活动进程分配多少个页帧。（2）被考虑替换的页集是仅限在引起页错误的进程的驻留集中选择还是在主存中所有的页帧中选择。页替换策略关注的是以下问题：在考虑的页集中，哪一个特殊的页应该被选择替换。8.8FIFO和Clock页替换算法有什么区别？71 时钟算法与FIFO算法很接近，除了在时钟算法中，任何一个使用位为一的页被忽略。8.9页缓冲实现的是什么？（1）被替换出驻留集的页不久又被访问到时，仍在主存中，减少了一次磁盘读写。（2）被修改的页以簇的方式被写回，而不是一次只写一个，这就大大减少了I/O操作的数目，从而减少了磁盘访问的时间。8.10为什么不可能把全局替换策略和固定分配策略组合起来？固定分配策略要求分配给一个进程的帧的数目是确定的，当一个进程中取入一个新的页时，这个进程驻留页集中的一页必须被替换出来（保持分配的帧的数目不变），这是一种局部替换策略。8.11驻留集和工作集有什么区别？一个进程的驻留集是指当前在主存中的这个进程的页的个数。一个进程的工作集是指这个进程最近被使用过的页的个数。8.12请求式清除和预约式清除有什么区别？在请求式清除中，只有当一页被选择用于替换时才被写回辅存；在预约式清除中，将这些被修改的多个页在需要用到它们所占据的页帧之前成批的写回辅存。第9章单处理器调度9.1简要描述三种类型的处理器调度。长程调度：决定加入到待执行的进程池中；中程调度：决定加入到部分或全部在主存中的进程集合中；短程调度：决定哪一个可用进程将被处理器执行。9.2在交互式操作系统中，通常最重要的性能要求是什么？反应时间9.3周转时间和响应时间有什么区别？周转时间是一个要求花费在系统上的包括等待时间和服务时间的总的时间。响应时间对一个交互进程，这是指从提交一个请求到开始接受响应之间的时间间隔。通常进程在处理该请求的同时，就开始给用户产生一些输出。9.4对进程调度，较小的优先级值表示较低的优先级还是较高的优先级？在UNIX和许多其他系统中，大的优先级值表示低优先级进程。许多系统，比如WINDOWS，刚好相反，大数值表示高优先级。9.5抢占式和非抢占式调度有什么区别？非抢占：在这种情况下，一旦进程处于运行态，他就不断执行直到终止，或者为等待I/O或请求某些操作系统服务而阻塞自己。抢占：当前正在运行的进程可能被操作系统中断，并转移到就绪态。关于抢占的决策可能是在一个新进程到达时，或者在一个中断发生后把一个被阻塞的进程置为就绪态时，或者基于周期性的时间中断。9.6简单定义FCFS调度。当每个进程就绪后，它加入就绪队列。当当前正在运行的进程停止执行时，选择在就绪队列中存在时间最长的进程运行。9.7简单定义轮转调度以一个周期性间隔产生时钟中断，当中断产生时，当前正在运行的的进程被置于就绪队列中，然后基于FCFS策略选择下一个就绪作业运行。9.8简单定义最短进程优先调度。这是一个非抢占的策略，其原则是下一次选择所需处理时间最短的进程。9.9简单定义最短剩余时间调度。71 最短剩余时间是针对SPN增加了抢占机制的版本。在这种情况下，调度器总是选择预期剩余时间最短的进程。当一个新进程加入到就绪队列时，他可能比当前运行的进程具有更短的剩余时间，因此，只有新进程就绪，调度器就可能抢占当前正在运行的进程。9.10简单定义最高响应比优先调度。在当前进程完成或被阻塞时，选择R值最大的就绪进程。R=(w+s)/s,w等待处理器的时间，s期待的服务时间。9.11简单定义反馈调度。调度基于抢占原则并且使用动态优先级机制。当一个进程第一次进入系统时，它被放置在RQ0。当它第一次被抢占后并返回就绪状态时，它被防止在RQ1。在随后的时间里，每当它被抢占时，它被降级到下一个低优先级队列中。一个短进程很快会执行完，不会在就绪队列中降很多级。一个长进程会逐级下降。因此，新到的进程和短进程优先于老进程和长进程。在每个队列中，除了在优先级最低的队列中，都使用简单的FCFS机制。一旦一个进程处于优先级最低的队列中，它就不可能再降低，但是会重复地返回该队列，直到运行结束。第10章多处理器和实时调度10.1列出并简单定义五种不同级别的同步粒度。细粒度：单指令流中固有的并行；中等粒度：在一个单独应用中的并行处理或多任务处理；粗粒度：在多道程序环境中并发进程的多处理；非常粗粒度：在网络节点上进行分布处理，以形成一个计算环境；无约束粒度：多个无关进程。10.2列出并简单定义线程调度的四种技术。加载共享：进程不是分配到一个特定的处理器，而是维护一个就绪进程的全局队列，每个处理器只要空闲就从队列中选择一个线程。这里使用术语加载共享来区分这种策略和加载平衡方案，加载平衡是基于一种比较永久的分配方案分配工作的。组调度：一组相关的线程基于一对一的原则，同时调度到一组处理器上运行。专用处理器分配：在程序执行过程中，每个程序被分配给一组处理器，处理器的数目与程序中的线程的数目相等。当程序终止是，处理器返回到总的处理器池中，可供分配给另一个程序。动态调度：在执行期间，进程中线程的数目可以改变。10.3列出并简单定义三种版本的负载分配。先来先服务（FCFS）：当一个作业到达时，它的所有线程都被连续地放置在共享队列末尾。当一个处理器变得空闲时，它选择下一个就绪线程执行，直到完成或阻塞。最少线程数优先：共享就绪队列被组织成一个优先级队列，如果一个作业包含的未调度线程数目最少，则给它指定最高的优先级。具有同等优先级的队列按作业到达的顺序排队。和FCFS一样，被调度的线程一直运行到完成或阻塞。可抢占的最少线程数优先：最高的的优先级给予包含的未被调度的线程数目最少的作业。刚到达的作业如果包含的线程数目少于正在执行的作业，它将抢占属于这个被调度作业的线程。10.硬实时任务和软实时任务有什么区别？硬实时任务指必须满足最后期限的限制，否则会给系统带来不可接受的破坏或者致命的错误。软实时任务也有一个与之相关联的最后期限，并希望能满足这个期限的要求，但是这并不是强制的，即使超过了最后期限，调度和完成这个任务仍然是有意义的。10.5周期性实时任务和非周期性实时任务有什么区别？非周期任务有一个必须结束或开始的最后期限，或者有一个关于开始时间和结束时间的约束。而对于周期任务，这个要求描述成“每隔周期T一次”或“每隔T个单位”。10.6列出并简单定义对实时操作系统的五方面的要求。可确定性：在某中程度上是指它可以按固定的、预先确定的时间或时间间隔执行操作。可响应性：它关注的是在知道中断之后操作系统未中断提供服务的时间71 用户控制：用户应该能够区分硬实时任务和软实时任务，并且在每一类中确定相对优先级。实时系统还允许用户指定一些特性，例如使用分页还是进程交换、哪一个进程必须常驻主存、使用何种磁盘算法、不同的优先级的进程各有哪些权限等。可靠性：可靠性必须提供这样一种方式，以继续满足实时最后期限。故障弱化操作：故障弱化操作指系统在故障时尽可能多的保存其性能和数据的能力。10.7列出并简单定义四类实时调度算法。静态表驱动法：执行关于可行调度的静态分析。分析的结果是一个调度，它用于确定在运行时一个任务何时必须开始执行。静态优先级驱动抢占法：同样，执行一个静态分析，但是没有制定调度，而且用于给任务指定优先级，使得可以使用传统的优先级驱动的抢占式调度器。基于动态规划调度法：在运行是动态地确定可行性，而不是在开始运行前离线的确定（静态）。一个到达的任务，只有当能够满足它的时间约束时，才可以被接受执行。可行性分析的结果是一个调度或规划，可用于确定何时分派这个任务。动态尽力调度法：不执行可行性分析。系统试图满足所有的最后期限，并终止任何已经开始运行但错过最后期限的进程。10.8关于一个任务的哪些信息在实时调度是非常有用？就绪时间：任务开始准备执行的时间。对于重复或周期性的任务，这实际上是一个事先知道的时间序列。而对于非周期性的任务，或者也事先知道这个时间，或者操作系统仅仅知道什么时候任务真正就绪。启动最后期限：任务必须开始的时间。完成最后期限：任务必须完成的时间。典型的实时应用程序或者有启动最后期限，或者有完成最后期限，但不会两者都存在。处理时间：从执行任务直到完成任务所需的时间。在某些情况下，可以提供这个时间，而在另外一些情况下，操作系统度量指数平均值。其他调度系统没有使用这个信息。资源需求：任务在执行过程中所需的资源集合（处理器以外的资源）。优先级：度量任务的相对重要性。硬实时任务可能具有绝对的优先级，因为如果错过最后期限则会导致系统失败。如果系统无论如何也要继续运行，则硬实时任务和软实时任务可以被指定相关的优先级，以指导调度器。子任务结构：一个任务可以分解成一个必须执行的子任务和一个可选的子任务。只有必须执行的子任务拥有硬最后期限。第11章I/O管理和磁盘调度11.1列出并简单定义执行I/O的三种技术。可编程I/O：处理器代表进程给I/O模块发送给一个I/O命令，该进程进入忙等待，等待操作的完成，然后才可以继续执行。中断驱动I/O：处理器代表进程向I/O模块发送一个I/O命令，然后继续执行后续指令，当I/O模块完成工作后，处理器被该模块中断。如果该进程不需要等待I/O完成，则后续指令可以仍是该进程中的指令，否则，该进程在这个中断上被挂起，处理器执行其他工作。直接存储器访问（DMA）：一个DMA模块控制主存和I/O模块之间的数据交换。为传送一块数据，处理器给DMA模块发送请求，只有当整个数据块传送完成后，处理器才被中断。11.2逻辑I/O和设备I/O有什么区别？逻辑I/O：逻辑I/O模块把设备当作一个逻辑资源来处理，它并不关心实际控制设备的细节。逻辑I/O模块代表用户进程管理的一般I/O功能，允许它们根据设备标识符以及诸如打开、关闭、读、写之类的简单命令与设备打交道。71 设备I/O：请求的操作和数据（缓冲的数据、记录等）被转换成适当的I/O指令序列、通道命令和控制器命令。可以使用缓冲技术，以提高使用率。11.3面向块的设备和面向流的设备有什么区别？请举例说明。面向块的设备将信息保存在块中，块的大小通常是固定的，传输过程中一次传送一块。通常可以通过块号访问数据。磁盘和磁带都是面向块的设备。面向流的设备以字节流的方式输入输出数据，其末使用块结构。终端、打印机通信端口、鼠标和其他指示设备以及大多数非辅存的其他设备，都属于面向流的设备。11.4为什么希望用双缓冲区而不是单缓冲区来提高I/O的性能？双缓冲允许两个操作并行处理，而不是依次处理。典型的，在一个进程往一个缓冲区中传送数据（从这个缓冲区中取数据）的同时，操作系统正在清空（或者填充）另一个缓冲区。11.5在磁盘读或写时有哪些延迟因素？寻道时间，旋转延迟，传送时间11.6简单定义图11.7中描述的磁盘调度策略。FIFO:按照先来先服务的顺序处理队列中的项目。SSTF:选择使磁头臂从当前位置开始移动最少的磁盘I/O请求。SCAN:磁头臂仅仅沿一个方向移动，并在途中满足所有未完成的请求，直到它到达这个方向上最后一个磁道，或者在这个方向上没有其他请求为止。接着反转服务方向，沿相反方向扫描，同样按顺序完成所有请求。C-SCAN:类似于SCAN，11.7简单定义图7层RAID。0：非冗余1：被镜像；每个磁盘都有一个包含相同数据的镜像磁盘。2：通过汉明码实现冗余；对每个数据磁盘中的相应都计算一个错误校正码，并且这个码位保存在多个奇偶校验磁盘中相应的文件。3：交错位奇偶校验；类似于第二层，不同之处在于RAID3为所有数据磁盘中同一位置的位的集合计算一个简单的奇偶校验位，而不是错误校正码。4：交错块分布奇偶校验；对每个数据磁盘中相应的条带计算一个逐位奇偶。5：交错块分布奇偶校验；类似于第四层，但把奇偶校验条带分布在所有磁盘中。6：交错块双重分布奇偶校验；两种不同的奇偶校验计算保存在不同磁盘的不同块中。11.8典型的磁盘扇区大小是多少？512比特第12章文件管理12.1域和记录有什么不同？域（field）是基本数据单位。一个域包含一个值。记录（record）是一组相关的域的集合，它可以看做是应用程序的一个单元。12.2文件和数据库有什么不同？文件（file）是一组相似记录的集合，它被用户和应用程序看做是一个实体，并可以通过名字访问。数据库（database）是一组相关的数据集合，它的本质特征是数据元素间存在着明确的关系，并且可供不同的应用程序使用。12.3什么是文件管理系统？文件管理系统是一组系统软件，为使用文件的用户和应用程序提供服务。12.4选择文件组织时的重要原则是什么？访问快速，易于修改，节约存储空间，维护简单，可靠性。12.5列出并简单定义五种文件组织。堆是最简单的文件组织形式。数据按它们到达的顺序被采集，每个记录由一串数据组成。71 顺序文件是最常用的文件组织形式。在这类文件中，每个记录都使用一种固定的格式。所有记录都具有相同的长度，并且由相同数目、长度固定的域按特定的顺序组成。由于每个域的长度和位置已知，因此只需要保存各个域的值，每个域的域名和长度是该文件结构的属性。索引顺序文件保留了顺序文件的关键特征：记录按照关键域的顺序组织起来。但它还增加了两个特征：用于支持随机访问的文件索引和溢出文件。索引提供了快速接近目标记录的查找能力。溢出文件类似于顺序文件中使用的日志文件，但是溢出文件中的记录可以根据它前面记录的指针进行定位。索引文件：只能通过索引来访问记录。其结果是对记录的放置位置不再有限制，只要至少有一个索引的指针指向这条记录即可。此外，还可以使用长度可变的记录。直接文件或散列文件：直接文件使用基于关键字的散列。12.6为什么在索引顺序文件中查找一个记录的平均搜索时间小于在顺序文件中的平均搜索时间？在顺序文件中，查找一个记录是按顺序检测每一个记录直到有一个包含符合条件的关键域值的记录被找到。索引顺序文件提供一个执行最小穷举搜索的索引结构。12.7对目录执行的典型操作有哪些？搜索，创建文件，删除文件，显示目录，修改目录。12.8路径名和工作目录有什么关系？路径名是由一系列从根目录或主目录向下到各个分支，最后直到该文件的路径中的目录名和最后到达的文件名组成。工作目录是一个这样的目录，它是含有用户正在使用的当前目录的树形结构。12.9可以授予或拒绝的某个特定用户对某个特定文件的访问权限通常有哪些？无（none），知道（knowledge），执行（execution），读(reading)，追加（appending），更新（updating），改变保护（changingprotection），删除（deletion）。12.10列出并简单定义三种组块方式。固定组块（fixedblocking）：使用固定长度的记录，并且若干条完整的记录被保存在一个块中。在每个块的末尾可能会有一些未使用的空间，称为内部碎片。可变长度跨越式组块（variable-lengthspannedblocking）：使用长度可变的记录，并且紧缩到块中，使得块中没有未使用空间。因此，某些记录可能会跨越两个块，通过一个指向后继块的指针连接。可变长度非跨越式组块（variable-lengthunspannedblocking）：使用可变长度的记录，但并不采用跨越的方式。如果下一条记录比块中剩余的未使用空间大，则无法使用这一部分，因此在大多数块中都会有未使用的空间。12.11列出并简单定义三种文件分配方法。连续分配是指在创建文件时，给文件分配一组连续的块。链式分配基于单个的块，链中的每一块都包含指向下一块的指针。索引分配：每个文件在文件分配表中有一个一级索引，分配给该文件的每个分区在索引中都有一个表项。第13章网络13.1网络访问层的主要功能是什么？网络层主要关注在两个端系统（服务器、工作站）之间的数据交换，以及端系统间的物理网络。13.2传输层的任务是什么？传输层关注的是数据的可靠性和保证数据能正确到达接收端应用程序。13.3什么是协议？协议是定义了用来管理两个单元间进行数据交换的一系列规则的集合。13.4什么是协议体系结构？这是一种实现通信功能的软件结构。典型地，协议结构包含了一个分层化的协议集，并且每个层中有一个或多个协议。13.5什么是TCP/IP？71 传输控制协议/互联网协议（TCP/IP）是两个最初为网际互连提供低层支持而设计的协议。TCP/IP协也被广泛应用于涉及由美国防卫部门和因特尔团体发展的比较广泛的协议集。13.6使用套接字接口的目的是什么？套接字接口是一个能够编写程序的API，从而利用TCP/IP协议程序建立一个用户端和服务器之间的通信。第14章分布式处理、客户/服务器和集群14.1什么是客户/服务器计算？客户/服务器计算是一个网络环境，在这个网络环境中包含着客户机和服务器，并由服务器来响应客户机的请求。14.2客户/服务器计算与任何其他形式的分布式数据处理的区别是什么？1、在用户的本地系统上为该用户提供界面友好的应用程序，这样做可使系统具有更高的可靠性。这使得用户可以在很大程度上控制对计算机的使用方式和时间，并使得部门级管理者具有响应本地需求的能力。2、尽管应用是分散开的，但仍然强调公司数据库的集中以及很多网络管理和使用功能的集中。这使公司的管理者能够对计算信息系统的投资总额进行总体控制，并提供互操作，以使多系统能够配合起来。同时，减少了各部门和单位在维护这些复杂的计算机设施时的开销，使他们能够选择他们需要的各种类型的机器和接口来访问那些数据和信息。3、对于用户组织和厂商来说，他们有一个共同的承诺事项，即使系统开放和模块化。这意味着用户在选择产品和混和使用来自众多厂商的设备时具有很多选择。4、网络互联是操作的基础，网络管理和网络安全在组织和操作信息系统中具有很高的优先权。14.3像TCP/IP这样的通信结构在客户/服务器计算环境中的作用是什么？它是使客户端和服务器能够协同工作的通信软件。14.4讨论将应用程序定位在客户上、服务器上或分开定位在客户和服务器上的基本原理。基于服务器的处理：这种配置的基本原理是用户工作站最适宜于提供良好的用户界面，并且数据库和应用程序很容易在中心系统上维护。尽管用户获得了良好界面的好处，但是，这种配置类型并不总能有效提高处理效率或系统支持的实际商业功能上有本质的改变。基于客户的处理：它使用户能够使用适应本地需要的应用。合作处理：这种配置类型可以比其他客户/服务器方式为用户提供更高的生产效率和更高的网络效率。14.5什么是胖客户和瘦客户，两种方法在基本原理上的差别是什么？胖客户：这是基于客户的处理，而大部分的软件都集中在客户端。胖客户模型的主要优点是它充分利用了桌面功能，分担了服务器上的应用处理并使它们更加有效，不容易产生瓶颈。瘦客户：这是基于服务器的处理，而大部分的软件都集中在服务器。这种方式更近似地模拟了传统的以主机为中心的方式，常常是使将公司范围的应用程序从大型机环境迁移到分布式环境的途径。14.6给出将pros和cons用于胖客户和瘦客户策略的建议。胖客户：胖客户模型的主要优点是它充分利用了桌面功能，分担了服务器上的应用处理并使它们更加有效，不容易产生瓶颈。新增加的功能很快就超出了桌面机器的处理能力，迫使公司进行升级。如果模型扩充超出了部门的界限，合并了很多用户，则公司必须安装高容量局域网来支持在瘦服务器和胖客户之间进行大量的传输。最后，维护、升级或替换分布于数十台或数百台桌面机的应用程序将变得非常困难。瘦客户：这种方式更近似地模拟了传统的以主机为中心的方式，常常是使将公司范围的应用程序从大型机环境迁移到分布式环境的途径。但是它不能提供和胖客户策略一样的灵活性。14.7解释三层客户/服务器体系结构的基本原理。中间层机器基本上是位于用户客户和很多后端数据库服务器之间的网关。中间层机器能够转换协议，将对一种类型的数据库查询映像为另一种类型数据库的查询。另外，中间层机器能够融合来自不同数据源的结果。最后，中间层机器因介于两个层次之间而可以充当桌面应用程序和后端应用程序之间的网关。71 14.8什么是中间件？中间件是在上层应用程序和下层通信软件和操作系统之间使用标准的编程接口和协议。它提供统一的方式和方法来跨越各种平台访问系统资源。14.9既然具有像TCP/IP这样的标准，为什么还需要中间件？TCP/IP不提供API和中间层协定来支持应用于不同的硬件和操作系统的多种应用程序平台。14.10列出消息传递的阻塞原语和无阻塞原语的优缺点。无阻塞原语为进程提供了对消息传递机制高效而灵活的使用，这种方法的缺点是难于测试和调试使用这些原语的程序。问题的不可再现性与时间顺序相关性往往导致产生很多奇怪而麻烦的问题。阻塞原语有与无阻塞原语相反的优缺点。14.11列出远程过程调用的非永久性和永久性绑定的优缺点。非永久绑定：因为连接需要维持两端的状态信息，因此需要消耗资源，非永久绑定类型用于保存这些资源。另一方面，建立连接所带来的开销使非永久绑定对同一个调用者频繁调用远程过程的情况不太适用。永久绑定：对于对远程过程进行多次重复调用的应用程序，永久绑定保持着逻辑连接，并支持使用同一连接进行一系列的调用和返回。14.12列出同步远程过程调用和异步远程过程调用的优缺点。同步远程过程调用易于理解和编程，因为它的行为是可以预期的。然而，它未能发挥分布式应用中固有的全部并行性。这就限制了分布式应用所能具有的交互性，降低了性能。为了提供更大的灵活性，各种异步远程过程调用机制已经得到实现，以获得更大程度的并行性而同时又保留了远程过程调用的通俗性和简易性。异步远程过程调用并不阻塞调用者，应答也可以在需要它们时接收到，这使客户在本地的执行可以与对服务器的调用并行进行。14.13列出并简短定义四种不同的构建集群的方法。被动等待：当主服务器出现故障时，由从服务器来接管。分离服务器：各服务器具有独自的磁盘，数据可连续地从主服务器复制至从服务器。各服务器连接到磁盘：所有服务器都连接到同一磁盘，但每台服务器仍拥有自己的磁盘，一旦某台服务器发生故障，则其磁盘被其他服务器接管。共享磁盘：多台服务器同时共享对磁盘的访问。第15章分布式进程管理15.1讨论实现进程迁移的原因。负载共享：通过将进程从负载较重的系统迁移到负载较轻的系统，负载就会得到平衡，从而提高整体性能。通信性能：可以将交互密集的多个进程移动到同一节点上，以减少因为它们之间的交互而带来的通信开销。同样，当一个进程在某些文件或某组文件上执行数据分析，且文件的大小比进程要大很多时，将该进程移动到数据端也许是更有利的。可用性：需要长时间运行的进程，在得到错误的预先通知时，或者在预定的关机时间之前，为了能够存活下来，可能需要迁移到其他机器中。如果操作系统提供了这样的通知，则那些需要继续运行的进程可以迁移到另一个系统上，或者保证在稍后的某个时间在当前系统上能重新启动。特殊功能的使用：进程的迁移可以充分利用特定节点上独特的硬件或软件功能。15.2在进程迁移过程中，进程地址空间是如何处理的？下列策略可能被采用：Eager（all）：在迁移时转移整个地址空间。预先复制（precopy）：进程继续在源节点上执行，而地址空间已经复制到了目标节点上。在预先复制的过程中，源节点上的某些页有可能又被修改，这些页必须被复制第二次。Eager（dirty）：仅仅转移那些位于主存中且已被修改了的地址空间的页。虚地址空间的所有其他块将在需要时才转移。71 基于引用的复制（copy-on-reference）：这是Eager（dirty）的变体，只有在引用某页时，该页才被取入。刷新（flushing）：通过把脏页写回磁盘，该进程的页可以从源机器的主存中清除。这样，在需要时可以从磁盘访问到页，而不是从源节点的存储器中访问。15.3抢占式和非抢占式进程迁移的动机是什么？非抢占式进程迁移对于负载平衡是很有用的，它的优点是能够避免全面性进程迁移的开销，缺点是该方法对于负载分布的突然变化反应不佳。15.4为什么不可能确定真正的全局状态？因为系统之间的通信延迟，不可能在系统范围内维护一个所有系统都随时可用的时钟。而且，维护一个中央时钟并让所有本地时钟与之保持精确同步，这在技术上也是不现实的，因为经过一段时间后，在各个本地时钟之间就会产生一些偏差，这将导致同步的丢失。15.5集中式算法和分布式算法所实行的分布式互斥有何区别？在完全集中式算法中，一个节点被指定为控制节点，它控制对所有共享对象的访问。当任何进程请求对一个临界资源进行访问时，就向本地资源控制进程发送一个请求，这个进程接着向控制节点发送一条请求消息，当共享对象可用时，将返回一条许可消息。当进程结束使用资源后，向控制节点发送一条释放消息。在分布式算法中，互斥算法涉及到每个离散的实体之间的同步合作。15.6定义两种类型的分布式死锁。在资源分配中产生的死锁以及由于消息通信而产生的死锁。第16章安全16.1计算机安全的基础要求是什么？机密性，完整性，可用性，可靠性。16.2主动安全攻击和被动安全攻击有什么不同？被动攻击在本质上是对传输进行窃听或监视。对方的目标是获取正在传输的信息。主动攻击包括对数据或数据流的更改或者生成错误的数据或数据流。16.3列出并简单定义主动安全攻击和被动安全攻击的分类。被动攻击：①释放消息内容：未被授权的人或程序了解了文件或消息的内容；②通信分析：通过分析数据传输模式来获取信息。主动攻击：①伪装：一个实体假装成另一个不同的实体；②重放：被动地捕获一个数据单元，然后再把它重发以产生未经授权的结果；③更改消息：改变合法消息的某些部分，或者消息被延迟或记录下来，产生未授权的结果；④拒绝服务：阻止或禁止对通信设施的正确使用或管理。16.4大多数通用的用户访问控制技术都要求有哪些元素？在共享系统或服务器上，用户访问控制的最普遍的技术是用户登录，这需要一个用户标识符（ID）和一个口令。16.5在访问控制中，主体和对象有什么区别？主体（subject）：能够访问对象的实体。一般地，主体概念等同于进程。任何用户或应用程序获取对一个对象的访问，实际上是通过一个代表该用户或应用程序的进程。对象（object）：访问控制所针对的一切。例如文件、文件的某些部分、程序、内存段以及软件对象。16.6解释图16.6中salt的目的。salt有三方面的作用：⑴防止在口令文件中出现相同的口令。即使有两个用户选择了相同的口令，那些口令也将被指定不同的时间，因此，两个用户的“扩展”口令是不同的。⑵有效地增加口令的长度，而不要求用户记住那两个额外的字符。因此，可能的口令个数增加了4096，从而增加了猜测口令的难度。⑶防止使用DES的硬件实现，硬件实现会使蛮力猜测攻击变得容易。16.7解释统计异常入侵检测和基于规则的入侵检测有什么不同？71 统计异常检测：包括收集在一段时间上与合法用户的行为有关的数据。然后对观察到的行为进行统计试验，以高度的信心来确定该行为是否是合法用户的行为。基于规则的检测：包括定义一组规则的工作，该组规则用于决定一个已知的行为是否是入侵者的行为。16.81999年和2000年开发的电子邮件附件和电子邮件VBS恶意软件（如Melissa、loveletter）称为电子邮件病毒。请问用术语电子邮件蠕虫是否更正确一些？这两种术语都合适。术语电子邮件蠕虫通常是一个独立的程序而不是嵌入其他程序的一个程序块，因此电子邮件病毒更正确一些。16.9加密在病毒设计中扮演着什么角色？加密技术将以如下方式被使用：有一部分病毒，一般称为变种引擎，它生成一个随机的密钥来加密病毒剩余的部分。该密钥与病毒一起存储，变种引擎自身却改变了。当受到感染的程序唤起执行时，病毒使用这个存储的随机密钥来解密病毒。当病毒复制时，选择另一个不同的随机密钥。16.10攻击常规加密方案的两种通用方法什么？密码分析：依靠算法的本质和关于明文一般特点的知识，甚至一些“明文-密文对”来进行攻击。这类攻击利用算法的特性，试图推导出具体的明文，或者推导出使用的密钥。强力攻击：它在一块密文上尝试每种可能的密钥，直到转换得到一个可理解的明文。16.11什么是DES和三重DEA？DES是被NIST标准化的一个广泛应用的传统编码标准。最初的DES指定了一个数据编码运算法则(DEA)。最近的标准的版本也包括使用三重DEA的选择项,用二或三个独立的密钥重复基本的DEA三次。16.12AES是如何改进三重DEA的？AES被期望在软件中运行得比TDEA更快。同时,AES使用更大的块尺寸,这可以提高安全性。16.13在评估AES候选者时，将使用什么评估原则？评估原则包括安全性、计算效率、需要的存储量、硬件和软件的适用性和灵活性。16.14解释常规加密和公钥加密有什么不同。在传统编码中，编码和解码使用相同的密钥。公钥编码中有一对密钥,一个用于编码而另一个用于解码。这二个密钥中只有一个需要被保留私用。16.15术语公钥、私钥和密钥的区别是什么？对称加密中的密钥通常称为密钥。公钥加密中使用的两个密钥称为公钥和私钥。私钥总是保密的，之所以将它称为私钥，是为了避免与对称加密中的密钥混淆。练习题答案第1章计算机系统概述1.1、图1.3中的理想机器还有两条I/O指令：0011=从I/O中载入AC0111=把AC保存到I/O中在这种情况下，12位地址标识一个特殊的外部设备。请给出以下程序的执行过程（按照图1.4的格式）：1.从设备5中载入AC。2.加上存储器单元940的内容。3.把AC保存到设备6中。假设从设备5中取到的下一个值为3940单元中的值为2。答案：存储器（16进制内容）：300：3005；301：5940；302：7006步骤1：3005－>IR；步骤2：3－>AC步骤3：5940－>IR；步骤4：3＋2＝5－>AC步骤5：7006－>IR：步骤6：AC－>设备671 1.2、本章中用6步来描述图1.4中的程序执行情况，请使用MAR和MBR扩充这个描述。答案：1.a.PC中包含第一条指令的地址300，该指令的内容被送入MAR中。b.地址为300的指令的内容（值为十六进制数1940）被送入MBR，并且PC增1。这两个步骤是并行完成的。c.MBR中的值被送入指令寄存器IR中。2.a.指令寄存器IR中的地址部分（940）被送入MAR中。b.地址940中的值被送入MBR中。c.MBR中的值被送入AC中。3.a.PC中的值（301）被送入MAR中。b.地址为301的指令的内容（值为十六进制数5941）被送入MBR，并且PC增1。c.MBR中的值被送入指令寄存器IR中。4.a.指令寄存器IR中的地址部分（941）被送入MAR中。b.地址941中的值被送入MBR中。c.AC中以前的内容和地址为941的存储单元中的内容相加，结果保存到AC中。5.a.PC中的值（302）被送入MAR中。b.地址为302的指令的内容（值为十六进制数2941）被送入MBR，并且PC增1。c.MBR中的值被送入指令寄存器IR中。6.a.指令寄存器IR中的地址部分（941）被送入MAR中。b.AC中的值被送入MBR中。c.MBR中的值被存储到地址为941的存储单元之中。1.4、假设有一个微处理器产生一个16位的地址（例如，假设程序计数器和地址寄存器都是16位）并且具有一个16位的数据总线。a.如果连接到一个16位存储器上，处理器能够直接访问的最大存储器地址空间为多少？b.如果连接到一个8位存储器上，处理器能够直接访问的最大存储器地址空间为多少？c.处理访问一个独立的I/O空间需要哪些结构特征？d.如果输入指令和输出指令可以表示8位I/O端口号，这个微处理器可以支持多少8位I/O端口？答案：对于(a)和(b)两种情况，微处理器可以直接访问的最大存储器地址空间为216=64Kbytes；唯一的区别是8位存储器每次访问传输1个字节，而16位存储器每次访问可以传输一个字节或者一个16位的字。对于(c)情况，特殊的输入和输出指令是必要的，这些指令的执行体会产生特殊的“I/O信号”（有别于“存储器信号”，这些信号由存储器类型指令的执行体产生）；在最小状态下，一个附加的输出针脚将用来传输新的信号。对于(d)情况，它支持28=256个输入和28=256个输出字节端口和相同数目的16位I/O端口；在任一情况,一个输入和一个输出端口之间的区别是通过被执行的输入输出指令所产生的不同信号来定义的。1.5、考虑一个32位微处理器，它有一个16位外部数据总线，并由一个8MHz的输入时钟驱动。假设这个微处理器有一个总线周期，其最大持续时间等于4个输入时钟周期。请问该微处理器可以支持的最大数据传送速度为多少？外部数据总线增加到21位，或者外部时钟频率加倍，哪种措施可以更好地提高处理器性能？请叙述你的设想并解释原因。答案：时钟周期＝1/（8MHZ）＝125ns总线周期＝4×125ns＝500ns每500ns传输2比特；因此传输速度＝4MB/s加倍频率可能意味着采用了新的芯片制造技术（假设每个指令都有相同的时钟周期数）；加倍外部数据总线，在芯片数据总线驱动/锁存、总线控制逻辑的修改等方面手段广泛（或许更新）。在第一种方案中，内存芯片的速度要提高一倍（大约），而不能降低微处理器的速度；第二种方案中，内存的字长必须加倍，以便能发送/接受32位数量。1.6、考虑一个计算机系统，它包含一个I/O模块，用以控制一台简单的键盘/打印机电传打字设备。CPU中包含下列寄存器，这些寄存器直接连接到系统总线上：71 INPR：输入寄存器，8位OUTR：输出寄存器，8位FGI：输入标记，1位FGO：输出标记，1位IEN：中断允许，1位I/O模块控制从打字机中输入击键，并输出到打印机中去。打字机可以把一个字母数字符号编码成一个8位字，也可以把一个8位字解码成一个字母数字符号。当8位字从打字机进入输入寄存器时，输入标记被置位；当打印一个字时，输出标记被置位。a.描述CPU如何使用这4个寄存器实现与打字机间的输入/输出。b.描述通过使用IEN，如何提高执行效率？答案：a.来源于打字机的输入储存在INPR中。只有当FGI＝0时，INPR才会接收来自打字机的数据。当数据接收后，被储存在INPR里面，同时FGI置为1。CPU定期检查FGI。如果FGI＝1，CPU将把INPR里面的内容传送至AC，并把FGI置为0。当CPU需要传送数据到打字机时，它会检查FGO。如果FGO＝0，CPU处于等待。如果FGO＝1，CPU将把AC的内容传送至OUTER并把FGO置为0。当数字符号打印后，打字机将把FGI置为1。b.（A）描述的过程非常浪费。速度远高于打字机的CPU必须反复不断的检查FGI和FGO。如果中断被使用，当打字机准备接收或者发送数据时，可以向CPU发出一个中断请求。IEN计数器可以由CPU设置（在程序员的控制下）。1.7、实际上在所有包括DMA模块的系统中，DMA访问主存储器的优先级总是高于处理器访问主存储器的优先级。这是为什么?答案：如果一个处理器在尝试着读或者写存储器时被挂起,通常除了一点轻微的时间损耗之外没有任何危害。但是，DMA可能从或者向设备(例如磁盘或磁带)以数据流的方式接收或者传输数据并且这是不能被打断的。否则，如果DMA设备被挂起（拒绝继续访问主存），数据可能会丢失。1.9、一台计算机包括一个CPU和一台I/O设备D，通过一条共享总线连接到主存储器M，数据总线的宽度为1个字。CPU每秒最多可执行106条指令，平均每条指令需要5个机器周期，其中3个周期需要使用存储器总线。存储器读/写操作使用1个机器周期。假设CPU正在连续不断地执行后台程序，并且需要保证95%的指令执行速度，但没有任何I/O指令。假设1个处理器周期等于1个总线周期，现在要在M和D之间传送大块数据。a.若使用程序控制I/O，I/O每传送1个字需要CPU执行两条指令。请估计通过D的I/O数据传送的最大可能速度。b.如果使用DMA传送，请估计传送速度。答案：a.处理器只能分配5％的时间给I/O.所以最大的I/O指令传送速度是10e6×0.05＝50000条指令/秒。因此I/O的传送速率是25000字/秒。b.使用DMA控制时，可用的机器周期下的数量是10e6（0.05×5＋0.95×2）＝2.15×10e6如果我们假设DMA模块可以使用所有这些周期，并且忽略任何设置和状态检查时间，那么这个值就是最大的I/O传输速率。1.10、考虑以下代码：for(i=0；i<20；i++)for(j=0；j<10；j++)a[i]=a[i]*ja.请举例说明代码中的空间局部性。b.请举例说明代码中的时间局部性。答案：a.读取第二条指令是紧跟着读取第一条指令的。b.在很短的间歇时间内，a[i]在循环内部被访问了十次。71 1.11、请将附录1A中的式（1.1）和式（1.2）推广到n级存储器层次中。答案：定义：Ci=存储器层次i上每一位的存储单元平均花销Si=存储器层次i的规模大小Ti=存储器层次i上访问一个字所需时间Hi=一个字在不高于层次i的存储器上的概率Bi=把一个数据块从层次i+1的存储器上传输到层次i的存储器上所需时间高速缓冲存储器作为是存储器层次1；主存为存储器层次2；针对所有的N层存储器层以此类推。有：Ts的引用更复杂，我们从概率论入手：所期望的值，由此我们可以写出：我们需要清楚如果一个字在M1（缓存）中，那么对它的读取非常快。如果这个字在M2而不在M1中，那么数据块需要从M2传输到M1中，然后才能读取。因此，T2=B1+T1进一步，T3=B2+T2=B1+B2+T1以此类推：所以，但是，最后，1.12、考虑一个存储器系统，它具有以下参数：Tc=100nsCc=0.01分/位Tm=1200nsCm=0.001分/位a.1MB的主存储器价格为多少？b.使用高速缓冲存储器技术，1MB的主存储器价格为多少？c.如果有效存取时间比高速缓冲存储器存取时间多10%，命中率H为多少？答案：a.价格=Cm×8×106=8×103￠=＄80b.价格=Cc×8×106=8×104￠=＄800c.由等式1.1知：1.1×T1=T1+(1-H)T2(0.1)(100)=(1-H)(1200)H=1190/120071 1.13、一台计算机包括包括高速缓冲存储器、主存储器和一个用做虚拟存储器的磁盘。如果要存取的字在高速缓冲存储器中，存取它需要20ns；如果该字在主存储器中而不在高速缓冲存储器中，把它载入高速缓冲存储器需要60ns（包括最初检查高速缓冲存储器的时间），然后再重新开始存取；如果该字不在主存储器中，从磁盘中取到内存需要12ms，接着复制到高速缓冲存储器中还需要60ns，再重新开始存取。高速缓冲存储器的命中率为0.9，主存储器的命中率为0.6，则该系统中存取一个字的平均存取时间是多少（单位为ns）？答案：有三种情况需要考虑：字所在的位置概率访问所需时间（ns）在缓存中0.920不在缓存，在主存中（0.1）（0.6）=0.0660+20=80不在缓存也不在主存中（0.1）（0.4）=0.0412ms+60+20=12,000,080所以平均访问时间是：Avg=(0.9)(20)+(0.06)(80)+(0.04)(12000080)=480026ns1.14、假设处理器使用一个栈来管理过程调用和返回。请问可以取消程序计数器而用栈指针代替吗？答案：如果栈只用于保存返回地址。或者如果栈也用于传递参数，这种方案只有当栈作为传递参数的控制单元而非机器指令时才成立。这两种情况下可以取消程序计数器而用栈指针代替。在后者情况中，处理器同时需要一个参数和指向栈顶部的程序计数器。第2章操作系统概述2.1假设我们有一台多道程序的计算机，每个作业有相同的特征。在一个计算周期T中，一个作业有一半时间花费在I/O上，另一半用于处理器的活动。每个作业一共运行N个周期。假设使用简单的循环法调度，并且I/O操作可以与处理器操作重叠。定义以下量：•时间周期=完成任务的实际时间•吞吐量=每个时间周期T内平均完成的作业数目•处理器使用率=处理器活跃（不是处于等待）的时间的百分比当周期T分别按下列方式分布时，对1个、2个和4个同时发生的作业，请计算这些量：a.前一般用于I/O，后一半用于处理器。b.前四分之一和后四分之一用于I/O，中间部分用于处理器。答：（a）和（b）的答案相同。尽管处理器活动不能重叠，但I/O操作能。一个作业时间周期=NT处理器利用率=50﹪两个作业时间周期=NT处理器利用率=100﹪四个作业时间周期=（2N-1）NT处理器利用率=100﹪2.2I/O限制的程序是指如果单独运行，则花费在等待I/O上的时间比使用处理器的时间要多的程序。处理器限制的程序则相反。假设短期调度算法偏爱那些在近期石油处理器时间较少的算法，请解释为什么这个算法偏爱I/O限制的程序，但是并不是永远不受理处理器限制程序所需的处理器时间？受I/O限制的程序使用相对较少的处理器时间，因此更受算法的青睐。然而，受处理器限制的进程如果在足够长的时间内得不到处理器时间，同一算法将允许处理器去处理此进程，因为它最近没有使用过处理器。这样，一个处理器限制的进程不会永远得不到处理器。2.3请对优化分时系统的调度策略和用于优化多道程序批处理系统的调度策略进行比较。分时系统关注的是轮转时间，时间限制策略更有效是因为它给所有进程一个较短的处理时间。批处理系统关心的是吞吐量，更少的上下文转换和更多的进程处理时间。因此，最小的上下文转换最高效。2.4系统调用的目的是什么?如何实现与操作系统相关的的系统调用以及与双重模式（内核模式和用户模式）操作相关的系统调用？系统调用被应用程序用来调用一个由操作系统提供的函数。通常情况下，系统调用最终转换成在内核模式下的系统程序。2.5在IBM的主机操作系统OS/390中，内核中的一个重要模块是系统资源管理程序（SystemResource71 Manager,SRM），他负责地址空间（进程）之间的资源分配。SRM是的OS/390在操作系统中具有特殊性，没有任何其他的主机操作系统，当然没有任何其他类型的操作系统可以比得上SRM所实现的功能。资源的概念包括处理器、实存和I/O通道，SRM累计处理器、I/O通道和各种重要数据结构的利用率，它的目标是基于性能监视和分析提供最优的性能，其安装设置了以后的各种性能目标作为SRM的指南，这会基于系统的利用率动态的修改安装和作业性能特点。SRM依次提供报告，允许受过训练的操作员改进配置和参数设置，以改善用户服务。现在关注SRM活动的一个实例。实存被划分为成千上万个大小相等的块，称为帧。每个帧可以保留一块称为页的虚存。SRM每秒大约接受20次控制，并在互相之间以及每个页面之间进行检查。如果页未被引用或被改变，计数器增1。一段时间后，SRM求这些数据的平均值，以确定系统中一个页面未曾被触及的平均秒数。这样做的目的是什么？SRM将采取什么动作？操作系统可以查看这些数据已确定系统的负荷，通过减少加在系统上的活跃作业来保持较高的平均利用率。典型的平均时间应该是两分钟以上，这个平均时间看起来很长，其实并不长。第3章进程描述和控制3.1.给出操作系统进行进程管理时的五种主要活动，并简单描述为什么需要它们。答：用户进程和系统进程创建及删除。系统中的进程可以为信息共享、运算加速、模块化和方便并发地执行。而并发执行需要进程的创建和删除机制。当进程创建或者运行时分配给它需要的资源。当进程终止时，操作系统需要收回任何可以重新利用的资源。进程的暂停和继续执行。在进程调度中，当进程在等待某些资源时，操作系统需要将它的状态改变为等待或就绪状态。当所需要的资源可用时，操作系统需要将它的状态变为运行态以使其继续执行。提供进程的同步机制。合作的进程可能需要共享数据。对共享数据的并行访问可能会导致数据冲突。操作系统必须提供进程的同步机制以使合作进程有序地执行，从而保证数据的一致性。提供进程的通信机制。操作系统下执行的进程既可以是独立进程也可以是合作进程。合作进程之间必须具有一定的方式进行通信。提供进程的死锁解决机制。在多道程序环境中，多个进程可能会竞争有限的资源。如果发生死锁，所有的等待进程都将永远不能由等待状态再变为运行态，资源将被浪费，工作永远不能完成。3.2.在[PINK89]中为进程定义了以下状态：执行（运行）态、活跃（就绪）态、阻塞态和挂起态。当进程正在等待允许使用某一资源时，它处于阻塞态；当进程正在等待它已经获得的某种资源上的操作完成时，它处于挂起态。在许多操作系统中，这两种状态常常放在一起作为阻塞态，挂起态使用本章中给出的定义。请比较这两组定义的优点。答：[PINK89]中引用了以下例子来阐述其中阻塞和挂起的定义：假设一个进程已经执行了一段时间，它需要一个额外的磁带设备来写出一个临时文件。在它开始写磁带之前，进程必须得到使用某一设备的许可。当它做出请求时，磁带设备可能并不可用，这种情况下，该进程就处于阻塞态。假设操作系统在某一时刻将磁带设备分配给了该进程，这时进程就重新变为活跃态。当进程重新变为执行态时要对新获得的磁带设备进行写操作。这时进程变为挂起态，等待该磁带上当前所进行的写操作完成。这种对等待某一设备的两种不同原因的区别，在操作系统组织其工作时是非常有用的。然而这并不能表明那些进程是换入的，那些进程是换出的。后一种区别是必需的，而且应该在进程状态中以某种形式表现出来。3.3.对于图3.9（b）中给出的7状态进程模型，请仿照图3.8（b）画出它的排队图。答：图9.3给出了单个阻塞队列的结果。该图可以很容易的推广到多个阻塞队列的情形。3.4.考虑图3.9（b）中的状态转换图。假设操作系统正在分派进程，有进程处于就绪态和就绪/挂起态，并且至少有一个处于就绪/挂起态的进程比处于就绪态的所有进程的优先级都高。有两种极端的策略：（1）总是分派一个处于就绪态的进程，以减少交换；（2）总是把机会给具有最高优先级的进程，即使会导致在不需要交换时进行交换。请给出一种能均衡考虑优先级和性能的中间策略。答：对于一个就绪/挂起态的进程，降低一定数量（如一或两个）优先级，从而保证只有当一个就绪/挂起态的进程比就绪态的进程的最高优先级还高出几个优先级时，它才会被选做下一个执行。3.5.表3.13给出了VAX/VMS操作系统的进程状态。a.请给出这么多种等待状态的理由。b.71 为什么以下状态没有驻留和换出方案：页错误等待、也冲突等待、公共事件等待、自由页等待和资源等待。a.请画出状态转换图，并指出引发状态装换的原因。答：a.每一种等待状态都有一个单独的队列与其相关联。当影响某一等待进程的事件发生时，把等待进程分成不同的队列就减少了定位这一等待进程所需的工作量。例如，当一个页错误完成时，调度程序就可以在页错误等待队列中找到等待的进程。b.在这些状态下，允许进程被换出只会使效率更低。例如，当发生页错误等待时，进程正在等待换入一个页从而使其可以执行，这是将进程换出是毫无意义的。c.可以由下面的进程状态转换表得到状态转换图。当前状态下一状态当前正在执行可计算（驻留）可计算（换出）各种等待状态（驻留）各种等待状态（换出）当前正在执行重调度等待可计算（驻留）调度换出可计算（换出）换入各种等待状态（驻留）事件发生换出各种等待状态（换出）事件发生3.1.VAM/VMS操作系统采用了四种处理器访问模式，以促进系统资源在进程间的保护和共享。访问模式确定：l指令执行特权：处理器将执行什么指令。l内存访问特权：当前指令可能访问虚拟内存中的哪个单元。四种模式如下：l内核模式：执行VMS操作系统的内核，包括内存管理、中断处理和I/O操作。l执行模式：执行许多操作系统服务调用，包括文件（磁盘和磁带）和记录管理例程。l管理模式：执行其他操作系统服务，如响应用户命令。l用户模式：执行用户程序和诸如编译器、编辑器、链接程序、调试器之类的实用程序。在较少特权模式执行的进程通常需要调用在较多特权模式下执行的过程，例如，一个用户程序需要一个操作系统服务。这个调用通过使用一个改变模式（简称CHM）指令来实现，该指令将引发一个中断，把控制转交给处于新的访问模式下的例程，并通过执行REI（ReturnfromExceptionorInterrupt，从异常或中断返回）指令返回。a.很多操作系统有两种模式，内核和用户，那么提供四种模式有什么优点和缺点？b.你可以举出一种有四种以上模式的情况吗？答：a.四种模式的优点是对主存的访问控制更加灵活，能够为主存提供更好的保护。缺点是复杂和处理的开销过大。例如，程序在每一种执行模式下都要有一个独立的堆栈。b.原则上，模式越多越灵活，但是四种以上的模式似乎很难实现。3.2.在前面习题中讨论的VMS方案常常称为环状保护结构，如图3.18所示。3.3节所描述的简单的内核/用户方案是一种两环结构，[SILB04]指出了这种方法的问题：环状（层次）结构的主要缺点是它不允许我们实施须知原理，特别地，如果一个对象必须在域Dj中可访问，但在域Di中不可访问，则必须有就jj:=i+1modn;while(j≠i)and(notwaiting[j])doj:=j+1modn;ifj=ithenlock:=falseelsewaiting:=false;Until这个算法用最普通的数据结构：varwaiting:array[0..n–1]ofbooleanLock：boolean这些数据结构被初始化成假的，当一个进程离开它的临界区，它就搜索waiting的循环队列5.8考虑下面关于信号量的定义：VoidsemWait(s){If(s.count>0){s.count--;}Else{Placethisprocessins.queue;Block;}}VoidsemSignal(s){If(thereisatliastoneprocessblockedonsemaphore){RemoveaprocessPfroms.queue;PlaceprocessPonreadylist;}Elses.count++;}比较这个定义和图5.3中的定义，注意有这样的一个区别：在前面的定义中，信号量永远不会取负值。当在程序中分别使用这两种定义时，其效果有什么不同？也就是说，是否可以在不改变程序意义的前提下，用一个定义代替另一个？答：这两个定义是等价的，在图5.3的定义中，当信号量的值为负值时，它的值代表了有多少个进程在等待；在此题中的定义中，虽然你没有关于这方面的信息，但是这两个版本的函数是一样的。5.9可以用二元信号量实现一般信号量。我们使用semWaitB操作和semSignalB操作以及两个二元信号量delay和mutex。考虑下面的代码VoidsemWait(semaphors){semWaitB(mutex);71 s--;if(s<0){semSignalB(mutex);semWaitB(delay);}ElseSemsignalb(mutex)}VoidsemSignal(semaphores);{semWaitB(mutex);s++;if(s<=0)semSignalB(delay);semSignalB(mutex);}最初。S被设置成期待的信号量值，每个semwait操作将信号量减1，每个semsignal操作将信号量加1.二元信号量mutex被初始化成1，确保在更新在更新s时保证互斥，二元信号量delay被初始化成0，用于挂起进程，上面的程序有一个缺点，证明这个缺点，并提出解决方案。提示：假设两个进程，每个都在s初始化为0时调用semwait（s）,当第一个刚刚执行了semsignalb（mutex）但还没有执行semwaitb（delay），第二个调用semwait（s）并到达同一点。现在需要做的就是移动程序的一行.答：假设两个进程，每个都在s被初始化成0时调用semWait（s），当第一个刚执行了semSignalB（mutex）但还没有执行semWaitB（delay）时，第二个调用semWait（s）并到达同一点。因为s=-2mutex没有锁定，假如有另外两个进程同时成功的调用semSignal（s），他们接着就会调用semsignalb（delay），但是第二个semsignalb没有被定义。解决方法就是移动semWait程序中end前的else一行到semSignal程序中最后一行之前。因此semWait中的最后一个semSignalB(mutex)变成无条件的，semSignal中的semSignalb(mutex)变成了有条件的。5.101978年，dijkstra提出了一个推测，即使用有限数目的弱信号量，没有一种解决互斥的方案，使用于数目未知但有限的进程且可以避免饥饿。1979年，j.m.morris提出了一个使用三个弱信号量的算法，反驳了这个推测。算法的行为可描述如下，如果一个或多个进程正在semwait（s）操作上等待，另一个进程正在执行semsignal（s），则信号量s的值未被修改，一个等待进程被解除阻塞，并且这并不取决于semwait（s）。除了这三个信号量外，算法使用两个非负整数变量，作为在算法特定区域的进程的计数器。因此，信号量A和B被初始化为1，而信号量M和计数器NA，NM被初始化成0.一个试图进入临界区的进程必须通过两个分别由信号量A和M表示路障，计数器NA和NM分别含有准备通过路障A以及通过路障A但还没有通过路障M的进程数。在协议的第二部分，在M上阻塞的NM个进程将使用类似于第一部分的串联技术，依次进入他们的临界区，定义一个算法实现上面的描述。答：这个程序由[RAYN86]提供：vara,b,m:semaphore;na,nm:0…+∞;a:=1;b:=1;m:=0;na:=0;nm:=0;semWait(b);na←na+1;semSignal(b);semWait(a);nm←nm+1;semwait(b);na←na–1;71 ifna=0thensemSignal(b);semSignal(m)elsesemSignal(b);semSignal(a)endif;semWait(m);nm←nm–1;;ifnm=0thensemSignal(a)elsesemSignal(m)endif;5.11下面的问题曾被用于一个测试中：侏罗纪公园有一个恐龙博物馆和一个公园，有m个旅客和n辆车，每辆车只能容纳一名旅客。旅客在博物馆逛了一会儿，然后派对乘坐旅客车。当一辆车可用时，它载入一名旅客，然后绕公园行驶任意长的时间。如果n辆车都已被旅客乘坐游玩，则想坐车的旅客需要等待；如果一辆车已经就绪，但没有旅客等待，那么这辆车等待。使用信号量同步m个旅客进程和n个进程。下面的代码框架是在教室的地板上发现的。忽略语法错误和丢掉的变量声明，请判定它是否正确。注意，p和v分别对应于semwait和semsignal。ResourceJurassic_Park()Semcar_avail:=0,car_taken:=0,car_fillde:=0.passenger_released:=0Processpassenger(i:=1tonum_passengers)Dotrue->nap(int(random(1000*wander_time)))P(caravail);V(car_taken);P(car_filled)P(passenger_released)OdEndpassengerProcesscar(j:=1tonum_cars)Dotrue->V(car_avail);P(car_taken);V(car_filled)Nap(int(random(1000*ride_time)))V(passenger_released)OdEndcarEndJurassic_Park答：这段代码有一个重要问题.在processcar中的代码V(passenger_released)能够解除下面一种旅客的阻塞,被阻塞在P(passenger_released)的这种旅客不是坐在执行V()的车里的旅客.5.12在图5.9和5.3的注释中，有一句话是“仅把消费者临界区（由s控制）中的控制语句移出还是不能解决问题，因为这将导致死锁”，请用类似于表5.3的表说明。答：ProducerConsumersndelay11002SemWaitB(S)0003n++0104If(n==1)(semSignalB(delay))0115semSignalB(s)1116semWaitB(delay)1107semWaitB(s)0108n--009semWaitB(s)If(n==0)(semWaitB(delay))71 10生产者和消费者都被阻塞。5.13考虑图5.10中定义的无限缓冲区生产者/消费者问题的解决方案。假设生产者和消费者都以大致相同的速度运行，运行情况如下：生产者：append;semSignal;produce;···append;semSignal消费者：consume;take;semWait;consume;take;semWait;生产者通常管理给换成区一个元素，并在消费者消费了前面的元素后发信号。生产者通常添加到一个空缓冲去中，而消费者通常取走缓冲区中的唯一元素。尽管消费者从不在信号量上阻塞，但必须进行大量的信号量调用，从而产生相当多的开销。构造一个新程序使得能在这种情况下更加有效。提示：允许n的值为-1，这表示不仅缓冲区为空，而且消费者也检测到这个事实并将被阻塞，直到生产者产生新数据。这个方案不需要使用图5.10中的局部变量m。答：这个程序来自于[BEN82]programproducerconsumer;varn:integer;s:(*binary*)semaphore(:=1);delay:(*binary*)semaphore(:=0);procedureproducer;beginrepeatproduce;semWaitB(s);append;n:=n+1;ifn=0thensemSignalB(delay);semSignalB(s)foreverend;procedureconsumer;beginrepeatsemWaitB(s);take;n:=n–1;ifn=-1thenbeginsemSignalB(s);semWaitB(delay);semWaitB(s)end;consume;semSignalB(s)foreverend;begin(*mainprogram*)71 n:=0;parbeginproducer;consumerparendend.5.14考虑图5.13.如果发生下面的交换，程序的意义是否会发生改变？a.semWait(e);semWait(s)b.semSignal(s);semSignal(n)c.semWait(n);semWait(s)d.semSignal(s);semSignal(e)答：只要交换顺序都会导致程序错误。信号量s控制进入临界区，你只想让临界区区域包括附加或采取功能。5.15在讨论有限缓冲区（见图5.12）生产者/消费者问题时，注意我们的定义允许缓冲区中最多有n-1个入口？a.这是为什么？b.请修改程序，以不久这种低调？答：如果缓冲区可以容纳n个入口，问题在于如何从一个满的缓冲区中区分出一个空的缓冲区，考虑一个有六个位置的缓冲区，且仅有一个入口，如下：AOutin然后，当一个元素被移出，out=in。现在假设缓冲区仅有一个位置为空：DEABCInout这样，out=in+1.但是，当一个元素被添加，in被加1后，out=in，当缓冲区为空时同理。b．你可以使用一个可以随意增加和减少的辅助的变量，count。5.16这个习题说明了使用信号量协调三类进程。圣诞老人在他北极的商店中睡眠，他只能被一下两种情况之一唤醒：（1）所有九头驯鹿都从南太平洋的假期回来了，或者（2）某些小孩在制作玩具时遇到了困难。为了让圣诞老人多睡会，这些孩子只有在是那个人都遇到困难时才唤醒他。当三个孩子的问题得到解决时，其他想访问圣诞老人的孩子必须等到那些孩子返回。如果圣诞老人醒来后发现在三个孩子在他的店门口等待，并且最后一头驯鹿已经从热带回来。则圣诞老人决定让孩子门等到圣诞节之后，因为准备最后一天哦iuxunlu必须与其他unlu在暖棚中等待并且还没有套上缰绳做成雪橇前回来。请用信号量解决这个问题。答：santa:圣诞老人reindeer:驯鹿elf:小孩子sleigh:雪橇toys:玩具71 5.17通过一下步骤说明消息传递和信号量具有同等的功能：a.用信号量实现消息传递。提示：利用一个共享缓冲区保存信箱，每个信箱由一个消息槽数组成的。b.用消息传递实现信号量。提示：引入一个独立的同步进程。答：b.这个方法来自于[TANE97].同步进程维护了一个计数器和一个等待进程的清单。进程调用相关用于向同步进程发送消息的生产者，wait或signal，来实现WAITHUOSIGNAL.然后生产者执行RECEIVE来接受来自于同步进程的回复。当消息到达时，同步进程检查计数器看需要的操作是否已经足够，SIGNALs总是可以完成，但是假如信号值为0时，WAITs将会被阻塞。假如操作被允许，同步进程就发回一个空消息，因此解除调用者的阻塞。假如操作是WAIT并且信号量的值为0时，同步进程进入调用队列，并且不发送回复。结果是执行WAIT的进程被阻塞。当SIGNAL被执行，同步进程选择一个进程在信号量上阻塞，要不就以先进先出顺序，要不以其他顺序，并且发送一个回复。跑步条件被允许因为同步进程一次只需要一个。71 第6章并发性：死锁和饥饿６.１写出图６.１（a）中死锁的四个条件。解：互斥：同一时刻只有一辆车可以占有一个十字路口象限。占有且等待：没有车可以倒退；在十字路口的每辆车都要等待直到它前面的象限是空的。非抢占:没有汽车被允许挤开其他车辆。循环等待:每辆汽车都在等待一个此时已经被其他车占领的十字路口象限。６.２按照６.１节中对图６.２中路径的描述，给出对图６.３中６种路径的简单描述。解：１.Q获得B和Ａ,然后释放B和A.当P重新开始执行的时候,它将会能够获得两个资源。2.Q获得B和Ａ，P执行而且阻塞在对A的请求上.Q释放B和Ａ。当P重新开始执行的时候，它将会能够获得两个资源。3.Q获得B，然后P获得和释放A.Q获得Ａ然后释放B和A.当P重新开始行的时候，它将会能够获得B。4.P获得Ａ然后Q获得B.P释放A.Q获得Ａ然后释放B.P获得B然后释放B。5.P获得，然后释放A.P获得B.Q执行而且阻塞在对Ｂ的请求上。Ｐ释放Ｂ。当Q重新开始执行的时候，,它将会能够获得两个资源。6.P获得Ａ而且释放Ａ然后获得并且释放B.当Q重新开始实行,它将会能够获得两个资源。６.３图６.３反映的情况不会发生死锁，请证明。证明：如果Q获得B和Ａ（在P之前请求Ａ）,那么Q能使用这些两类资源然后释放他们,允许Ａ进行。如果P在Q之前请求Ａ获得Ａ,然后Q最多能执行到请求Ａ然后被阻塞。然而,一旦P释放A，Q能进行。一旦Q释放B,Ａ能进行。６.４考虑下面的一个系统，当前不存在未满足的请求。可用r1r2r3r42100当前分配最大需求仍然需求r1r2r3r4r1r2r3r4r1r2r3r40012001220002750003466562354435603320652a计算每个进程仍然可能需要的资源，并填入标为“仍然需要”的列中。b系统当前是处于安全状态还是不安全状态，为什么。c系统当前是否死锁？为什么？d哪个进程（如果存在）是死锁的或可能变成死锁的？71 e如果Ｐ３的请求（0，1，0，0）到达，是否可以立即安全地同意该请求？在什么状态（死锁，安全，不安全）下可以立即同意系统剩下的全部请求？如果立即同意全部请求，哪个进程（如果有）是死锁的或可能变成死锁的？解：a.00000750662220020320b.系统当前处于安全状态，因为至少有一个进程执行序列，不会导致死锁，运行顺序是p1,p4,p5,p2,p3.c.系统当前并没有死锁，因为P1进程当前分配与最大需求正好相等，P1进程可以运行直至结束，接下来运行其他进程d.P2,P3,P4,P5可能死锁e.不可以，当进程P1,P4,P5执行完可用资源为（4，6，9，8），P2,P3将死锁，所以不安全，完全不可以立即同意系统剩下的全部请求。６.５请把６.４中的死锁检测算法应用于下面的数据，并给出结果。Available=(2100)20010010Request=1010Allocation=200121000120解：1.W=(2100)2.MarkP3;W=(2100)+(0120)=(2220)3.MarkP2;W=(2220)+(2001)=(4221)4.MarkP1;nodeadlockdetected没有死锁６.６一个假脱机系统包含一个输入进程Ｉ，用户进程进程Ｐ和一个输出进程Ｏ，它们之间用两个缓冲区连接。进程以相等大小的块为单位交换数据，这些块利用输入缓冲区和输出缓冲区之间的移动边界缓存在磁盘上，并取决于进程的速度。所使用的通信原语确保满足下面的资源约束：i+o≤max其中，max表示磁盘中的最大块数，i表示磁盘中的输入块数目，o表示磁盘中的输出块数目。I输入缓冲区P输出缓冲区o以下是关于进程的知识：１.只要环境提供数据，进程Ｉ最终把它输入到磁盘上（只要磁盘空间可用）。２.只要磁盘可以得到输入，进程Ｐ最终消耗掉它，并在磁盘上为每个输入块输出有限量的数据（只要磁盘空间可用）。３.只要磁盘可以得到输出，进程Ｏ最终消耗掉它。说明这个系统可能死锁。71 解：当I的速度远大于P的速度，有可能使磁盘上都是输入数据而此时P进程要处理输入数据，即要将处理数据放入输出数据区。于是P进程等待磁盘空间输出，I进程等待磁盘空间输入，二者死锁。６.７给出在习题６.６中预防死锁的附加资源约束，仍然通话输入和输出缓冲区之间的边界可以根据进程的要求变化。解：为输出缓冲区保留一个最小数目(称为reso)块,但是当磁盘空间足够大时允许输出块的数目超过这一个界限。资源限制现在变成Ｉ+Ｏ≤maxＩ≤max–reso当00;regionbuffer(j)doconsumeelement;regionavailabledobeginavailable(i):=available(i)–1;available(succ):=available(succ)+1;endj:=(j+1)modmax;foreverendb.死锁可以被解决通过P0waitsforPn-1ANDP1waitsforP0AND.....Pn-1waitsforPn-2因为(available(0)=0)AND(available(1)=0)AND.....(available(n-1)=0)但是如果max>0,这个条件不成立，因为临界域满足claim(1)+claim(2)+…+claim(n);get_forks(k);/*clientrequeststwoforksviamonitor*/;release_forks(k);/*clientreleasesforksviathemonitor*/}}６.１９在表６.１３中，Linux的一些原子操作不会涉及到对同一变量的两次访问。比如atomic_read(atomic_t*v).简单的读操作在任何体系结构中都是原子的。为什么该操作增加到了原子操作的指令表？解：原子操作是在原子数据类型上操作,原子数据类型有他们自己的内在的格式。因此，不能用简单的阅读操作,但是特别的阅读操作71 对于原子数据类型来说是不可或缺的。６.２０考虑Linux系统中的如下代码片断：read_lock(&mr_rwlock);write_lock(&mr_rwlock);mr_rwlock是读者写者锁。这段代码的作用是什么？解：因为写者锁将会自旋，所以这段代码会导致死锁,等待所有的读者解锁,包括唤醒这个线程。６.２１两个变量a和b分别有初始值１和２，对于Linux系统有如下代码：线程1线程2a=3；mb()；--------c=b；rmb()；d=a；使用内在屏障是为了避免什么错误？解：没有使用内存屏障,在一些处理器上可能c接到b的新值,而d接到b的旧值。举例来说,c可以等于4(我们期待的),然而d可能等于1.(不是我们期待的)。使用mb()确保a和b按合适的次序被写,使用rmb()确保c和d按合适的次序被读。第7章内存管理7.1.2.3节中列出了内存管理的5个目标，7.1节中列出了5中需求。请说明它们是一致的。答:重定位≈支持模块化程序设计;保护≈保护和访问控制以及进程隔离;共享≈保护和访问控制;逻辑组织≈支持模块化程序设计;物理组织≈长期存储及自动分配和管理.7.2.考虑使用大小相等分区的固定分区方案。分区大小为2e16字节，贮存的大小为2e24字节。使用一个进程表来包含每一个进程对应的分区。这个指针需要多少位？答:分区的数量等于主存的字节数除以每个分区的字节数：224/216=28.需要8个比特来确定一个分区大小为28中的某一个位置。7.3.考虑动态分区方案，说明平均内存中空洞的数量是段数量的一半。答:设n和h为断数量和空洞数量的个数.在主存中,每划分一个断产生一个空洞的概率是0.5,因为删除一个断和添加一个断的概率是一样的.假设s是内存中断的个数那么空洞的平均个数一定等于s/2.而导致空洞的个数一定小余断的数量的直接原因是相邻的两个断在删除是一定会产生一个空洞.7.4.在实现动态分区中的各种放置算法（见7.2节），内存中必须保留一个空闲块列表。分别讨论最佳适配、首次适配、临近适配三种方法的平均查找长度。答:通过上题我们知道，假设s是驻留段的个数，那么空洞的平均个数是s/2。从平均意义上讲，平均查找长度是s/4。7.5.动态分区的另一种放置算法是最坏适配，在这种情况下，当调入一个进程时，使用最大的空闲存储块。该方法与最佳适配、首次适配、邻近适配相比，优点和缺点各是什么？它的平均查找长度是多少？71 答：一种对最佳适配算法的评价即是为固定分配一个组块后和剩余空间是如此小以至于实际上已经没有什么用处。最坏适配算法最大化了在一次分配之后，剩余空间的大小仍足够满足另一需求的机率，同时最小化了压缩的概率。这种方法的缺点是最大存储块最早被分配，因此大空间的要求可能无法满足。7.1.如果使用动态分区方案，下图所示为在某个给定的时间点的内存配置：阴影部分为已经被分配的块；空白部分为空闲块。接下来的三个内存需求分别为40MB，20MB和10MB。分别使用如下几种放置算法，指出给这三个需求分配的块的起始地址。a.首次适配b.最佳适配c.临近适配（假设最近添加的块位于内存的开始）d.最坏适配答：a.40M的块放入第2个洞中,起始地址是80M.20M的块放入第一个洞中.起始地址是20M.10M的块的起始地址是120M。b.40M,20N,10M的起始地址分别为230M,20M和160M.c.40M,20M,10M的起始地址是80M,120160M.d.40M,20M,10M,的起始地址是80M,230M,360M.7.2.使用伙伴系统分配一个1MB的存储块。a.利用类似于图7.6的图来说明按下列顺序请求和返回的结果：请求70；请求35；请求80；返回A；请求60；返回B；返回D；返回C。b.给出返回B之后的二叉树表示。答：a.b.71 7.1.考虑一个伙伴系统，在当前分配下的一个特定块地址为011011110000.a.如果块大小为4，它的伙伴的二进制地址为多少？b.如果块大小为16，它的伙伴的二进制地址为多少？答：a.011011110100b.0110111000007.2.令buddyk(x)为大小为2k、地址为x的块的伙伴的地址，写出buddyk(x)的通用表达式。答：7.3.Fabonacci序列定义如下：F0=0,F1=1,Fn+2=Fn+1+Fn,n≧0a.这个序列可以用于建立伙伴系统吗？b.该伙伴系统与本章介绍的二叉伙伴系统相比，有什么优点？答：a.是。字区大小可以确定Fn=Fn-1+Fn-2.。b.这种策略能够比二叉伙伴系统提供更多不同大小的块，因而具有减少内部碎片的可能性。但由于创建了许多没用的小块，会造成更多的外部碎片。7.4.在程序执行期间，每次取指令后处理器把指令寄存器的内容（程序计数器）增加一个字，但如果遇到会导致在程序中其他地址继续执行的转跳或调用指令，处理器将修改这个寄存器的内容。现在考虑图7.8。关于指令地址有两种选择：l在指令寄存器中保存相对地址，并把指令寄存器作为输入进行动态地址转换。当遇到一次成功的转跳或调用时，由这个转跳或调用产生的相对地址被装入到指令寄存器中。l在指令寄存器中保存绝对地址。当遇到一次成功的转跳或调用时，采用动态地址转换，其结果保存到指令寄存器中。哪种方法更好？71 答：使用绝对地址可以减少动态地址转换的次数。但是，我们希望程序能够被重定位。因此，在指令寄存器中保存相对地址似乎就更好一些。也可以选择在进程被换出主存时将指令寄存器中的地址转换为相对地址。7.1.考虑一个简单分页系统，其物理存储器大小为232字节，页大小为210字节，逻辑地址空间为216个页。a.逻辑地址空间包含多少位？b.一个帧中包含多少字节？c.在物理地址中指定帧需要多少位？d.在页表中包含多少个页表项？e.在每个页表项中包含多少位？（假设每个页表项中包含一个有效/无效位）答：a.物理地址空间的比特数是216*210=226b.一个帧包含的字节跟一个页是一样的,210比特.c.主存中帧的数量是232/210=222,所以每个帧的定位要22个比特d.在物理地址空间,每个页都有一个页表项,所以有216项e.加上有效/无效位，每个页表项包含23位。7.2.分页系统中的虚地址a相当于一对（p，w），其中p是页号，w是页中的字节号。令z是一页中的字节总数，请给出p和w关于z和a的函数。答：关系是：a=pz+w，其中p=∟a/z,a/z的整数部分。w=Rz(a)，a除以z的余数7.3.在一个简单分段系统中，包含如下段表：起始地址长度（字节）6602481752442222198996604对如下的每一个逻辑地址，确定其对应的物理地址或者说明段错误是否会发生：a.0，198b.2，256c.1，530d.3，444e.0，222答：a.段0定位在660,所以我们有物理地址660+190=858.b.222+156=378c.段1长度为422,所以会发生错误d.996+444=1440e.660+222=882.7.4.在内存中，存在连续的段S1,S2,…，Sn按其创建顺序一次从一端放置到另一端，如下图所示：当段Sn+1被创建时，尽管S1,S2,…，Sn中的某些段可能已经被删除，段Sn+1仍被立即放置在段Sn之后。当段（正在使用或已被删除）和洞之间的边界到达内存的另一端时，压缩正在使用的段。a.说明花费在压缩上的时间F遵循以下的不等式：F≧(1-f)/1+kf),k=t/2s-1其中，s表示段的平均长度（以字为单位）；l标识段的平均生命周期，按存储器访问；f表示在平衡条件下，未使用的内存部分。提示：计算边界在内存中移动的平均速度，并假设复制一个字至少需要两次存储器访问。b.当f=0.2，t=1000，s=50时，计算F。71 答：a.很明显,在一个周期t内一些段会产生而一些段会被删除.因为系统是公平的,一个新的段会在t内被插入,此外,边界会医s/t的速度移动.假设t0是边界到达空洞的时间,t0=fmr/s,m=内存的长度,在对段进行压缩时会有(1-f)m个数被移动,压缩时间至少是2(1-f)m.则花在压缩上的时间F为F=1-t0/(t0+tc)。b.K=(t/2s)-1=9;F≧(1-0.2)/(1+1.8)=0.29第8章虚拟内存8.1假设在处理器上执行的进程的也表如下所示。所有数字均为十进制数，每一项都是从0开始记数的，并且所有的地址都是内存字节地址。页尺寸为1024个字节。虚拟页号有效位访问位修改位页帧号01104111172000—310024000—51010a．描述CPU产生的虚拟地址通常是如何转化成一个物理主存地址的。b．下列虚拟地址对应于哪个物理地址（不用考略页错误）？（i）1052（ii）2221（iii）5499解答a：由虚拟地址求得页号和偏移量，用虚拟页号作为索引页表，得到页帧号，联系偏移量得到物理地址b:(i)1052=1024+28查表对应的页帧号是7，因此物理地址为7*1024+28=7196(ii)2221=2*1024+173此时出现页错误(iii)5499=5*1024+379对应的页帧号为0因此物理地址是3798.2考虑一个使用32位的地址和1KB大小的页的分页虚拟内存系统。每个页表项需要32位。需要限制页表的大小为一个页。a．页表一共需要使用几级？b．每一级页表的大小是多少？提示：一个页表的大小比较小。c．在第一级使用的页较小与在最底下一级使用的页较小相比，那种策略使用最小个数的页？解答a：虚拟内存可以分为232/210=222页，所以需要22个bit来区别虚拟内存中的一页，每一个页表可以包含210/4=28项，因此每个页表可以包含22bit中的8个bit，所以需要三级索引。b：第二级页表有28个页表项，第一级页表有26个页表项。c：如果顶层有26个页表项将会减少使用空间，在这种情况下，中间层页表有26个并且每个都有28个页表项，底层有214个页并且每个都有28个页表项，因此共有1+26+214页=16,449页。如果中间层有26个页表项，那么总的页数有1+28+214页=16,641页。如果底层有26个页表项，那么总的页表数是1+28+216页=65,973页。8.3a：图8.4中的用户表需要多少内存空间？71 b：假设需要设计一个哈希反向页表来实现与图8.4中相同的寻址机制，使用一个哈希函数来将20位页号映射到6位哈希表。表项包含页号帧号和链指针。如果页表可以给每个哈希表项分配最多3个溢出项的空间，则哈希反向页表需要占用多大的内存空间？解答a：4Mbyteb：行数：26+2=128项。每项包含：20（页号）+20（帧号）+8bits（链索引）=48bits=6bytes。总共：128*6=768bytes8.4一个进程分配给4个页帧（下面的所有数字均为十进制数，每一项都是从0开始计数的）。上一次把一页装入到一个页帧的时间，上一次访问页帧中的页的时间，每个页帧中的虚拟页号以及每个页帧的访问位（R）和修改位（M）如下表所示（时间均为从进程开始到该事件之间的时钟时间，而不是从事件发生到当前的时钟值）。虚拟页号页帧加载时间访问时间R位M位2060161011113016010022616210332016311当虚拟页4发生错误时，使用下列内存管理策略，哪一个页帧将用于置换？解释原因。a.FIFO（先进先出）算法b.LRU（最近最少使用）算法c.Clock算法d.最佳（使用下面的访问串）算法e.在页错误之前给定上述内存状态，考虑下面的虚拟页访问序列：4,0,0,2,4,2,1,0,3,2如果使用窗口大小为4的工作集策略来代替固定分配，会发生多少页错误？每个页错误何时发生？解答a:页帧3，在时间20加载，时间最长。b:页帧1，在时间160访问距现在时间最长。c:清除页帧3的R位（最早加载），清除页帧2的R位，（次最早加载），换出的是页帧0因为它的R位为0。d:换出的是页帧3中的虚拟页3，因为它将最晚被访问到。e:一共有6个错误，如下8.5一个进程访问5页：A,B,C,D和E，访问顺序如下：A;B;C;D;A;B;E;A;B;C;D;E假设置换算法为先进后出，该进程在主存中有三个页帧，开始时为空，请查找在这个访问顺序中传送的页号。对于4个页帧的情况，请重复上面的过程。解答分别有9次和10次页错误，这被称之为“Belady′s现象”（"AnAnomalyinSpace-TimeCharacteristicsofCertainProgramsRunninginaPagingMachine,"byBeladyetal,CommunicationsoftheACM,June1969.）8.6一个进程在磁盘上包含8个虚拟页，在主存中固定分配给4个页帧。发生如下顺序的页访问：71 1,0,2,2,1,7,0,1,2,0,3,0,4,5,1,5,2,4,5,6,7,6,7,2,4,2,7,3,3,2,3a.如果使用LRU替换策略，给出相继驻留在这4个页帧中的页。计算主存的命中率。假设这些帧最初是空的。b.如果使用FIFO策略，重复问题（a）。c.比较使用这两种策略的命中率。解释为什么这个特殊的访问顺序，使用FIFO的效率接近于LRU。解答a:LRU：命中率=16/33b:FIFO：命中率=16/33c:这两种策略对这个特殊的页轨迹（执行顺序）是等效的。8.7在VAX中，用户页表以系统空间的虚拟地址进行定位。让用户页表位于虚存而不是主存中有什么好处？有什么缺点？解答最主要的优点是在物理内存空间上的节省。这主要是两方面的原因：（1）一个用户页表可以仅当使用时才取入内存。（2）操作系统可以动态的分配用户页表，产生一个页表仅当程序被创建时。当然，也有一个缺点：地址转换需要多余的工作。8.8假设在主存中执行下列程序语句：for(i=1;i≤n;i++)a[i]=b[i]+c[i];页尺寸为1000个字。令n=1000。使用一台具有所有寄存器指令并使用了索引寄存器的机器，写出实现上述语句的一个假想程序，然后给出在执行过程中的页访问顺序。解答由机器语言编写的程序，在主存中地址4000处开始运行。运行情况如下：4000（R1）←1建立索引记录i4001（R1）←n在R2中建立n4002比较R2，R1检查i﹥n4003如果大于则跳转到40094004（R3）←B（R1）使用索引记录R1到达B[i]4005（R3）←（R3）+C（R1）使用索引记录R1加上C[i]4006A（R1）←（R3）使用索引记录R1将总和存入A[i]中4007（R1）←（R1）+1i加一4008跳到40026000—6999存储A7000—7999存储B8000—8999存储C71 9000存储19001存储n由这个循环产生的参考串为494944（47484649444）1000包括11.000个参考，但仅包括5个不寻常的页8.9IBMSystem/370体系结构使用两级存储器结构，并且分别把这两级称为段和页，这里的分段方法缺少本章所描述的关于段的许多特征。对于这个基本的370体系结构，页尺寸可以是2KB或4KB，段大小固定为64KB或1MB。这种方案缺少一般分段系统的那些优点？370的分段方法有什么好处？解答S/370分段系统是固定的且对程序员是不可见的，因此没有一个分段系统的优点在S/370中实现（无保护情况下）每一个段表项的P位提供整个段表的保护。8.10假设页尺寸为4KB，页表项大小位4字节。如果要映射一个64位地址空间，并且最顶层的页表对应于一页，则需要几级页表？解答因为每个页表项有4bytes，每个页表有4Kbytes，所以每个页表可以映射1024=210个页，标识出210×212=222bytes的地址空间。然而，地址空间是264bytes。增加一个二层页表，顶层页表指向210个页表，标识出232个页表，将这个过程继续下去就得到：深度地址空间1222bytes2232bytes3242bytes4252bytes5262bytes6272bytes（﹥264bytes）我们可以看到5层是不够表示64位的地址空间，但是6层达到了要求。但是6层中只有2位被使用，而不是全部的10位。所以不是使用72位的虚拟地址空间，而是将除了最低两位外的其他位全部屏蔽忽略。这样将会得到一个64位地址空间，顶层页只有4个页表项。另外一种方法是修改规则将顶层页做成一个单独的物理页并且让它适合4个页。这样将会节省一个页。8.11考虑一个系统该系统采用基于页的内存映射，并使用一级页表。假设页表总是在主存中。a.如果一次存储器访问需要200ns，那么一次需要调页的存储器访问要多长时间？b.现在增加一个MMU，在命中或未命中时有20ns的开销。如果假设有85%的存储器访问命中都在MMUTLB中，那么哪些是有效的存储器访问时间？c.解释TLB命中率如何影响有效的存储器访问时间。解答a.400ns。200ns用来得到页表项，200ns用来到达存储位置b.这是一个常见的有效时间计算公式：（220×0.85）+（420×0.15）=250两种情况：第一种，TLB中包含所需的页表项。在这种情况下在200ns外多了20ns的存储访问时间。第二种，TLB中不包含所需的页表项。这时我们会再多花200ns来把所需的页表项取入TLB。c.TLB命中率越高有效存储器访问时间就越短，因为额外的200ns来得到页表项的时间被节省了。8.12考虑一个进程的页访问序列，工作集为M帧，最初都是空的。页访问串的长度为P，包含N个不同的页号。对任何一种页替换算法，71 a.页错误次数的下限是多少？b.页错误次数的上限是多少？解答a.Nb.P8.13在论述一种页替换算法时，一位作者用一个在循环轨道上来回移动的雪犁机来模拟说明：雪均匀地落在轨道上，雪犁机一恒定的速度在轨道上不断的循环，轨道上被扫落的雪从系统中消失。a.8.2节讨论的哪一种页替换算法可以用它来模拟？b.这个模拟说明了页替换算法的那些行为？解答a.这是一个很好的时钟算法的类似。雪落在轨道上类似于页到达循环页缓存中。时钟算法时钟算法指针的移动类似于雪犁机的移动。b.注意到在时钟指针最近的前面可替换页的密度是最高的，就好像在雪犁机最近的前面的雪是最厚的一样。因此我们可以认为时钟算法在寻找替换页时是非常有效的。事实上可以看到雪犁机前雪的厚度是轨道上雪平均厚度的两倍。通过这种类似，在单循环中被时钟策略替换的页的号码是被随机替换的页的号码的两倍。这个近似不是最完美的，因为时钟指针并不是以一个确定的速率移动，但是直观意义还是有的。8.14在S/370体系结构中，存储关键字是与实存中每个页帧相关联的控制字段。这个关键字中与页替换有关的有两位：访问位和修改位。当在帧中的任何单元执行写操作时，修改位被置为1；当一个新页被装入到该帧中时，访问位被置为1。请给出一种方法，仅仅使用访问位来确定哪个页帧是最近最少使用的。解答处理器硬件置访问位为0当一个新页被加入到帧时，置为1当这个页帧的位置被访问到时。操作系统可以维护几个页帧表队列，一个页帧表项从一个队列移动到另一个队列取决于这个页帧的访问位被值为零的时间长短。当必须有页被替换时，被替换的页将从具有最长未被访问时间的页帧队列中选取。8.15考虑如下的页访问序列（序列中的每一个元素都是页号）：12345213323454511325定义经过k次访问后平均工作集大小为Sk（△）=1/k∑W（t，△）（t=1—k），并且定义经过k次访问后错过页的概率为Mk（△）=1/k∑F（t，△）（t=1—k），其中如果页错误发生在虚拟时间t，则F（t，△）=1，否则F（t，△）=0。a.当△=1，2，3，4，5，6时，绘制与图8.19类似的图标来说明刚定义的页访问序列的工作集。b.写出S20（△）关于△的表达式。b.写出M20（△）关于△的表达式。解答a.71 b.c.S20是一个△的增函数，M20是一个△的非增函数。8.16VSWS驻留集管理策略的性能关键是Q的值。经验表明，如果对于一个进程使用固定的的Q值，则在不同的执行阶段，页错误发生的频率有很大的差别。此外对不同的进程使用相同的Q值，则发生页错误的频率会完全不同。这些差别表明，如果有一种机制可以在一个进程的生命周期中动态的调整Q得知，则会提高算法的性能。请基于这种目标设计一种简单的机制。解答[PIZZ89]推荐使用如下策略。在窗口中使用一个机构在窗口时间调整Q的值作为实际页错误率的函数，页错误率被计算出并且同作为系统值的作业理想页错误率比较。Q的值被上调（下调）当实际的页错误率比理想值高（低）。使用这种调整机制的实验证明可以动态调整Q值的测试作业在每次运行时产生较少的页错误和减小的驻留集，相比于固定Q值的作业的运行（在很大程度上）。存储时间在相对于Q值使用可调整机制时也会产生一个固定且可观的改进，比较于使用固定的Q值。8.17假设一个任务被划分为4个大小相等的段，并且系统为每个段建立了一个有8项的页描述符表。因此，该系统是分段与分页的组合。假设页尺寸为2KB。a.每段的最大尺寸为多少？b.该任务的逻辑地址空间最大为多少？c.假设该任务访问到物理单元00021ABC中的一个元素，那么为它产生的逻辑地址的格式是什么？该系统的物理地址最大为多少？解答71 a.8×2K=16kb.16K×4=64Kc.232=4GBytes8.18考虑一个分页式的逻辑地址空间（由32个2KB的页组成），将它映射到一个1MB的物理内存空间。a.该处理器的逻辑地址空间格式是什么？b.页表的长度和宽度是多少（忽略“访问权限”位）？c.如果物理内存空间减少了一半，则会对页表有什么影响？解答a.页码（5）偏移量（11）71 b.32个页表项长，每个页表项9个bits宽c.如果页表项还是32个且页大小不变，那么每个页表项变为8bits宽8.19UNIX内核可以在需要时动态地在虚存中增加一个进程的栈，但却从不缩小这个栈。考虑下面的例子：一个程序调用一个C语言程序，这个子程序在栈中分配一个本地数组，一共需要10KB大小，内核扩展这个栈段来适应它。当这个子程序返回时，内核应该调整栈指针并释放空间，但它却未被释放。解释为什么可以缩小栈以及UNIX内核为什么没有缩小栈。解答可以通过释放再分配不使用的页来缩减栈的大小。按照惯例，在超出当前栈顶范围内内存中的值没有定义。在全部的体系结构中，标志栈顶部的指针在一个定义完好的记录中。因此可以读取栈的内容且按要求释放不使用的页。不缩小栈的原因是这样做的效果很小。如果用户程序重复调用子程序需要附加的空间来分配给局部变量（一个很可能的情况），然后许多时间会被浪费在释放重分配栈空间第9章单处理器调度9.1考虑下面的进程集合：进程名到达时间处理时间A03B15C32D95E125对这个集合，给出类似于表9.5和图9.5的分析。每格代表一个时间单位，方框中的数表示当前运行的进程AAABBBBBCCDDDDDEEEEEABABCABCBDBDEDEDEDEEAAABBBBCCBDDEDEEEEDEAAACCBBBBBDDDDDEEEEEAAACCBBBBBDDDDDEEEEEAAABBBBBCCDDDDDEEEEEABACBCABBDBDEDEDEDEEABAACBBCBBDDDDDEEDEE第一到第八行依次是FCFSRR,q=1RR,q=4SPNSRTHRRNFeedback,q=1Feedback,q=2(i)ABCDETa013912Ts35255FCFSTf38101520Tr3.007.007.006.008.006.20Tr/Ts1.001.403.501.201.601.74RRq=1Tf6.0011.008.0018.0020.00Tr6.0010.005.009.008.007.60Tr/Ts2.002.002.501.801.601.98RRq=4Tf3.0010.009.0019.0020.00Tr3.009.006.0010.008.007.20Tr/Ts1.001.803.002.001.601.8871 SPNTf3.0010.005.0015.0020.00Tr3.009.002.006.008.005.60Tr/Ts1.001.801.001.201.601.32SRTTf3.0010.005.0015.0020.00Tr3.009.002.006.008.005.60Tr/Ts1.001.801.001.201.601.32HRRNTf3.008.0010.0015.0020.00Tr3.007.007.006.008.006.20Tr/Ts1.001.403.501.201.601.74FBq=1Tf7.0011.006.0018.0020.00Tr7.0010.003.009.008.007.40Tr/Ts2.332.001.501.801.601.85FBTf4.0010.008.0018.0020.00q=2iTr4.009.005.009.008.007.00Tr/Ts1.331.802.501.801.601.819.2对下面的集合重复习题9.1的要求进程到达时处理时间A01B19C21D39ABBBBBBBBBCDDDDEEEEEABCBDBDBDBDBDBDDEDEEABBBBCBBBBDDDDBEEEDEABBBBBBBBBCDDDDEEEEEABCBBBBBBBBDDDDEEEEEABBBBBBBBBCDDDDEEEEEABCDBDBDBDBDBDBDEDEEABCDBBDDBBBBDDDEEDEEABCDTa0123Ts1919FCFSTf1.0010.0011.0020.00Tr1.009.009.0017.009.00Tr/Ts1.001.009.001.893.22RRq=1Tf1.0018.003.0020.00Tr1.0017.001.0017.009.00Tr/Ts1.001.891.001.891.44RRq=4Tf1.0015.006.0020.00Tr1.0014.004.0017.009.00Tr/Ts1.001.564.001.892.11SPNTf1.0010.0011.0020.00Tr1.009.009.0017.009.00Tr/Ts1.001.009.001.893.2271 SRTTf1.0011.003.0020.00Tr1.0010.001.0017.009.00Tr/Ts1.001.111.001.891.25HRRNTf1.0010.0011.0020.00Tr1.009.009.0017.009.00Tr/Ts1.001.009.001.893.22FBq=1Tf1.0019.003.0020.00Tr1.0018.001.0017.009.25Tr/Ts1.002.001.001.891.47FBTf1.0018.003.0020.00q=2iTr1.0017.001.0017.009.00Tr/Ts1.001.891.001.891.449.3证明在非抢占调度算法中，对于同时到达的批处理作业，SPN提供了最小平均等待时间。假设调度器只要有任务就必须执行。我们能够证明在一批n个作业同时到达且忽略以后到来的作业。试验会延伸包含以后的作业。假设各作业到来的顺序是：t1<=t2<=……<=tn.假设n个使用者必须等到工作1的完成：n-1个使用者必须等到工作2的完成，依次继续。那么，平均反应时间是[n*t1+(n-1)*t2+……+tn]/n。如果我们在这个时间表中做些改变，例如调换工作j和k（j=0。换句话说，如果SPN运算法则没被采用，平均反应时间只会增加。9.4假设一个进程的每一次瞬间执行时间（burst-time模式）为6，4，6，4，13，13，13，假设最初的猜测值为10。请画出类似于图9.9的图表。数据图如下：平均观察观测值平均值apha=0.8alpha=0.5160.000.000.00243.004.803.00363.334.163.50444.005.634.755134.004.334.386135.5011.278.697136.5712.6510.849.5考虑下面的公式，它可以替代Sn+1=αTn+(1-α)Sn,Xn+1=min[Ubound,max[Lbound,(βSn+1)]]其中，Ubound和Lbound是预先选择的估计值T的上限和下限。Xn+1的值用于最短进程优先的算法，并且可以代替Sn+1。α和β有什么功能，它们每个取最大值和最小值会产生什么影响？第一个等式等同于等式9.3，所以参数使指数起平滑作用。参数β是延迟变化参数。一个较小的β值将会时在观察次数里更快的适应改变，但估计上会产生更多的波动。一个诡辩的这种估计类型的程序收录于AppliedOptimalEstimation。9.6在图9.5下面的例子中，在控制权限转移到B之前，进程A运行2个时间单元，另外一个场景是在控制权限转移到B之前，进程A运行3个时间单元。在反馈调度算法中，这两种场景的策略有什么不同？关键要看进程A是否一开始就被放置在队列中。如果是，它在被抢占前就被赋予2个额外的时间单元。9.7在一个非抢占的单处理器系统中，在刚刚完成一个作业后的时间t，就绪队列中包含三个作业。这些作业分别在时间t1，t2，t3处到达，估计执行时间分别为r1，r2，r3。图9.18显示了它们的响应比随着时间线形增加。使用这个例子，设计一种响应比调度的变体，称为极小极大响应比调度算法，它可以使给定的一批作业的最大响应比最小。71 首先，调度器计算t+r1+r2+r3时刻的响应比，如果三个进程都结束，此时，进城3就有最高响应比，因此调度器就执行该进程，然后在t+r1+r2时刻继续执行进程1和2直到结束。因此，进程1的响应比最小，其次进程2在t时间被选中执行。这种算法在每个进程结束的时候重复一次并且考虑新加入的进程。但注意这种算法和最高响应比算法不完全相同。后者在t时刻会选择进程1。直觉上看，当前算法通过不断的推迟具有最少响应比增值的进程从而减小最高响应比9.8证明，对给定的一批作业，上一习题中的最大响应比调度算法能够使它们的最大响应时间最小这个证明，来自于P.Mondrup,isreportedin[BRIN73]。考虑在时间t时的队列，仅仅在前一个进程结束且忽略以后工作的到来。等待执行的作业被编号从1到n：作业：12……I……n到达时间：t1t2……ti……tn服务时间：r1r2……ri……rn我们假设作业i在完成前能达到最高的响应时间比。当作业1到n都执行结束，总时间为Ti=t+r1+r2+……+ri，作业i的响应比为Ri（Ti）+（Ti-ti）/ri执行作业i的原因是它的响应比将是以下作业在Ti时最小的：Ri(Ti)=min[R1(Ti),R2(Ti),……,Ri(Ti)]考虑不同序列中同样的n个作业的排序结果：作业：ab ……j……z到达时间：tatb……tj……tz服务时间：Rarb……rj……rz在新的序列中，我们选择最小的后继服务作业，从a到j，包括从1到i最初的后继。当作业a到j被执行结束，总时间为Tj=t+ra+rb+……+rj作业j的响应比是Rj(Tj)+(Tj-tj)/rj由于作业1到j是作业a到j的一个子集，那么总的服务时间Ti-t一定小于等于总的服务时间Tj-t.又响应比随着时间增加而增加，Ti<=Tj,意味Rj(Tj)>=Rj(Ti)人们还知道，作业J是其中的之一，作业j在时间Ti有最小的响应比。上述不平等的，因此可以延长如下：Rj(Tj)>=Rj(Ti)>=Ri(Ti).换言之，在调度算法改变后，会有作业j达到响应比Rj(Tj)，它会大于等于最高的响应比Ri(Ti).这证明有效期一般为优先考虑的都是非递减函数的时间。例如，在一个FIFO制度，优先增加线性与等候时间，在同样的速度，为所有作业机会。因此，目前的证据表明，该FIFO的算法最大限度地减少候车时间，对于给定了一批作业。9.9驻留时间Tr被定义成一个进程花费在等待和被服务上的总平均时间。说明对FIFO，若平均服务时间为Ts，则有Tr=Ts/（1-ρ），其中ρ为使用率。在我们开始以前，有一个结果，这是必要的，具体情况如下。假设一个项目拥有T服务时间，而实际服务了时间h。那么，预期的残留服务时间E[T/T>h]=Ts。那就是，无论多久，一个项目服务，预计剩余服务时间，只是平均服务时间为项目。这一结果，虽然反以直觉是正确的，正如我们现在查看，考虑到指数的概率分布函数：F(x)=Pr[X≤x]=1–e–ux，那么，我们有Pr[X>x]=e-ux。现在让我们看看X多于X+h的条件概率：，则因此，概率分布为服务时间给予确已送达期限x是相同的概率分布，总服务时间。因此，预期价值的剩余服务时间是一样的原来预期值的服务时间。与这一结果，我们现在可以着手将原问题。当一个项目展开服务以来，总的响应时间，该项目将包括它自己的服务时间，再加上服务的时候，所有的物品摆在它面前的，在排队。预期总体响应时间由三部分组成。l预计到达进程的服务时间=Ts。l预计所有目前正在等待服务的进程程的服务时间。值为w×Ts，w是平均等待服务时间。剩余等待服务时间，如果现在有一个进程正在执行。这个值可以表示成为ρ×Ts，ρ71 是利用，因此一个进程正在服务的概率。Ts正如我们已证明是预计等待服务的时间。，因此，我们有9.10一个处理器被就绪队列中的所有进程以无限的速度多路复用，且没有任何额外的开销（这是一个在就绪进程中使用轮转调度的理想模型，时间片相对于平均服务时间非常小）。说明对来自一个无限源的泊松输入和指数服务时间，一个进程的平均响应时间Rx和服务时间x由式Rx=x/(1-ρ)给出。让我们把时间片在轮转调度中记为δ。在这个问题中，δ相对于服务时间很小。现在，考虑一个新来的进程，它排在就绪队列的最后。我们假设这一特定的进程的服务时间为X，是δ的一些倍数：x=mδ。首先，让我们回答一个问题，多少时间花费在进程得到服务前的等待队列中。它必须等待所有排在它之前的q个进程结束服务后，从而初步等待时间=qδ。Q则是等待队列中的平均进程数目。现在，我们可以计算总时间花费在收到x秒钟的服务之前的等待时间。因为它必须经过队列m次，而每一次他们等待qδ秒，其总等待时间分列如下：然后，响应时间是指等待时间和总服务时间Rx=waittime+servicetime=qx+x=(q+1)x。谈到排队的公式，在附录A，是指物品的数量，该系统的Q可表示为：Q=ρ/(1-ρ),则Rx=[ρ/(1-ρ)+1]*x=(x/1-ρ)*Rx=[ρ/(1-ρ)+1]*x=x/(1-ρ)9.11大多数轮转调度器使用大小固定的时间片。给定支持小时间片的参数。现在给定一个支持大的时间片的参数。比较并对比两个参数所适用的系统和作业的类型。存在两种参数都合理的情况吗？一个论点主张一个小时间片：用一个小时间片会加强反应能力，多次运行的所有进程进行了短暂的时间片。当就绪队列有许多流程，这是互动性，反应能力是非常重要的如：一般用途的计算机系统。一个论点主张一个大的时间片：利用大型公司将提高吞吐量和CPU利用率测量方面的实际工作，因为那里是不足的背景下切换，从而减少开销。一个系统，其中既可能是适当的：有一些制度，即无论是中小企业还是大广，是合理的。例如：很长的行业，需要在短短数用户互动。虽然这种类型的工作可以被视为一个批处理工作，在某种意义上来说，它仍然需要与用户手中。因此，在时代的时候，有没有使用者之间的相互作用，时间片可能会增加优化，并在整个过程中的互动时间，时间片可能降至提供更好的应变能力。9.12在排队系统中，新作业在得到服务之前必须等待一会儿。当一个作业等待时，它的优先级从0开始以速度α线形增加。一个作业一直等待到它的优先级达到正在运行中的作业的优先级，然后它开始与其他正在运行的作业使用轮转法平等地共享处理器，与此同时，它的优先级继续以比较慢的速度β增长。这个算法称为自私轮转法，因为在运行中的作业试图通过不断地增加它的优先级来垄断处理器。首先，我们需要厘清意义的参数λ"。速度在项目到达第一盒（"队列"专栏）是λ。两个相邻的来港人士，以第二个选项（"服务"的框），将得出一个稍微减慢，因为第二项是延迟其追逐的第一个项目。我们可以计算出垂直偏移Y的数字，在两种不同方式的基础上，几何形状的图表：9.13一个使用轮转调度和交换的交互式系统，试图按如下方式对普通的请求给出有保证的响应：在所有就绪进程中完成一次轮转循环后，系统通过用最大响应时间除以需要服务的进程数目，确定在下一个循环中分配给每个就绪进程的时间片。请问是否是合理的解释？只是，只要有相对很少有用户在该系统内。当时间片变小，以满足更多用户迅速两件事情发生：（1）处理器利用率下降，以及（2）在某一个点，时间片变得太小，以满足最琐碎的请求。用户将经历一个突然增加的响应时间，因为他们的要求，必须经过轮转调度好几次。9.14多级反馈排队调度对哪种类型的进程有利，是受处理器限制的进程还是受I/O限制的进程？请简要说明原因。如果一个进程占用过多处理器时间，它将会被移到一个低优先级的队列中。这会使受I/O限制的进程留在优先级高的队列中。71 9.15在基于优先级的进程调度中，如果当前没有其他优先级更高的进程处于就绪状态，调度器将把控制给一个特定的进程。假设在进行进程调度决策时没有使用其他信息，还假设进程的优先级是在进程被创建是建立的，并且不会改变。在这样的系统中，为什么使用Dekker方法解决互斥问题是非常“危险”的？通过说明会发生什么和如何发生来解释该问题。dekker的算法依靠的是对公平性的硬件和操作系统。使用的优先次序的风险饥饿如下。可能有这样的情况，如果出生是一种很快速的反复过程，因为它不断地发现Flag[1]=虚假的，不断进入其关键路段，而在P1，离开内部回路，它正在等待它反过来又可以不设置Flag[1]为真实，阻止这样做出生的读变量（记得进入该变发生下相互排斥）9.165个批作业，从A到E，同时到达计算机中心。它们的估计运行时间分别为15，9，3，6和12分钟，它们的优先级（外部定义）分别为6，3，7，9和4（值越小，表示的优先级越高）。对下面的每种调度算法，确定每个进程的周转时间和所有作业的平均周转时间（忽略进程切换的开销），并解释是如何得到这个结果的。对于最后三种情况，假设一次只有一个作业运行直到它结束，并且所有作业都完全是受处理器限制的。a．时间片为1分钟的轮转法。b．优先级调度c．FCFS（按15，9，3，6和12顺序运行）。d．最短作业优先a:时间片为1分钟的轮转法：12345ElapsedtimeABCDE5ABCDE10ABCDE15ABDE19ABDE23ABDE27ABE30ABE33ABE36AE38AE40AE42A43A45每个进程的周转时间A=45min,B=35min,C=13min,D=26min,E=42min平均周转时间是(45+35+14+26+42)/5=32.2minb.PriorityJobTurnaroundTime3B94E9+12=216A21+15=367C36+3=399D39+6=45平均周转时间是(9+21+36+39+45)/5=30minc.JobTurnaroundTime71 A15B15+9=24C24+3=27D27+6=33E33+12=45平均周转时间是(15+24+27+33+45)/5=28.8mind.RunningJobTurnaroundTimeTime3C36D3+6=99B9+9=1812E18+12=3015A30+15=45平均周转时间是:(3+9+18+30+45)/5=21min第10章多处理器和实时调度10.1考虑一组周期任务（3个），表10.5给了它们的执行简表。按照类似与图10.5的形式，给出关于这组任务的调度图。表10.5习题10.1的执行简表进程到达时间执行时间完成最后期限A(1)01020A(2)201040....B(1)01050B(2)5010100....C(1)01550C(2)5015100....答：对于固定的优先级来说，我们以优先级是ABC来考虑这道题。每一方格代表五个时钟单元，方格里的字母是指现在正在运行的进程。第一行是固定的优先级；第二行表示的是使用完成最后期限的最早最后期限调度。表格如下：AABBAACCAABBAACCAAAABBACCACAABBAACCCAA对于固定优先级调度来说，进程C总是错过它的最后期限。10.2考虑一组非周期性任务（5个），表10.6给出了它们的执行简表。按照类似于图10.6的形式给出关于这组任务的调度图。表10.6习题10.2的执行简表进程到达时间执行时间启动最后期限A1020100B202030C402060D502080E60207071 答：每一方格代表10个时间单元。最早期限AACCEEDD有自愿空闲时间的最早期限BBCCEEDDAA先来先服AACCDD10.3这个习题用于说明对于速率单调调度，式（10.2）是成功调度的充分条件，但它并不是必要条件[也就是说，有些时候，尽管不满足式（10.2）也可能成功调度]。a.考虑一个任务集，它包括以下独立的周期任务：任务P1：C1=20;T1=100任务P2:C2=30;T2=145使用速率单调调度，这些任务可以成功地调度吗？b.现在再往集合里增加以下任务：任务P3:C3=68;T3=150式（10.2）可以满足吗？C．假设前述的三个任务的第一个实例在t=0是到达，并假设每个任务的第一个最后期限如下：D1=100;D2=145;D3=150如果使用速率单调调度，请问这三个最后期限都能得到满足吗？每个任务循环的最后想、期限是多少？答：a.P1,P2的总使用率是0.41，小于由方程10.2给出的对于两个任务的界限0.828，因此这两个任务是可以成功调度的。b.所有任务的使用率是0.86，已经超过界限0.779。c.可以观察到在P3执行前P1，P2必须至少执行一次。因此P3的第一次瞬间完成时间不低于20＋30＋68＝118。但是P1在一附加的时间区间（0，118）内初始化。因此P3直到118＋20＝138才完成他的第一次执行。在P3的期限内。继续这个过程，我们可以知道，这三个任务的所有期限都能实现。10.4画一个与图10.9（b）相似的图，用来显示队同一个例子使用优先级置顶的事件顺序。一旦T3进入他的临界区，他的优先级就被指定为高于T1。当T3离开他的临界区时，他被T1抢先。71 第11章I/O管理和磁盘调度11.1考虑一个程序访问一个I/O设备，并比较无缓冲的I/O和使用缓冲区的I/O。说明使用缓冲区最多可以减少2倍的运行时间。如果计算的时间正好等于它的I/O时间（它是最佳环境），操作者和外围设备同时运行。如果单独运行，只要花费他们的一半时间，设C是整个程序的计算时间，T为所要求总的I/O时间，因而寄存器最好的运行时间是max(C,T)，不需要寄存器的运行时间是C+T，显然（(C+T)/2）≤max(C,T)≤(C+T).11.2把习题11.1的结论推广到访问n个设备的程序中。最佳比是（n+1）﹕n11.3使用与表11.2类似的方式，分析下列磁道请求：27，129，110，186，147，41，10，64，120。假设磁头最初定位在磁道100处，并且沿着磁道号减小的方向移动。假设磁头沿着磁道增大的方向移动，请给出同样的分析。FIFOSSTFSCANC-SCAN下一个被访问的磁道27129110186147411064120平均寻道长度横跨的磁道数7310219763910631545661.8下一个被访问的磁道11012012914718664412710平均寻道长度横跨的磁道数10109183912223141729.1下一个被访问的磁道64412710110120129147186平均寻道长度横跨的磁道数36231417100109183929.6下一个被访问的磁道64412710186147129120110平均寻道长度横跨的磁道数36231417176391891038如果磁头沿着增大的方向，只有SCAN和C-SCAN的结果有变化SCANC-SCAN下一个被访问的磁道11012012914718664412710平均寻道长度横跨的磁道数10109183912223141729.1下一个被访问的磁道11012012914718610274164平均寻道长度横跨的磁道数10109183917617142335.171 1.4考虑一个磁盘，有N个磁道，磁道号从0到(N-1)，并且假设请求的扇区随机地均匀分布在磁盘上。现在要计算一次寻道平均跨越的磁道数。a.首先，计算当磁头当前位于磁道t时，寻道长度为j的可能性。提示：这是一个关于确定所有组合数目的问题，所有磁道位置作为寻道目标的可能性是相等的。b.接下来计算寻道长度为K的可能性。提示：这包括所有移动了K个磁道的可能性之和。c.使用下面计算期望值得公式，计算一次寻道平均跨越的磁道数目：N-1E[X]=∑i∑Pr[x=i]i=0d．说明档N比较大时，一次寻道平均跨越的磁道数接近N/3.（a）设P[j/t]表示位于磁道t，寻道长度为j的概率，知随机访问一个任何一个磁道的可能性为相等为1/N，因此我们有P[j/t]=1/N,t<=j-1或者t>=N-j;P[j/t]=2/N,j-1，C=V。a.一共可以产生多少口令？b.敌手正确地猜出口令的概率是多少？答案：a.T=(21×5×21)2=4862025b.p=≈2×10-716.4、假设口令被局限于使用95个可打印的ASCII字符，并且所有的口令长度均为10个字符。假设一个口令黑客以每秒6.4个密码的速度进行测试。在UNIX系统中，穷举测试所有可能的口令需要多长时间？答案：口令的可能性有9510≈6×1019种。穷举测试所有可能的口令需要时间：16.5、由于知道了UNIX口令系统的危险，SunOS-4.0文档建议移动口令文件并替换成一个称为/etc/publickey的公共可读文件。该文件中用户A的入口包括用户标识符IDA，该用户的公钥KUa，以及相应的私钥KRa。通过使用DES和从用户的登录口令Pa衍生的密钥对公钥进行加密。当A登录到系统时，通过解密EPa[KRa]得到KRa。Ex[a]表示使用密钥x的加密或解密。71 a.该系统可以验证提供的Pa是正确的，请问如何验证？b.如何攻击该系统？答案：a.因为公钥KUa和私钥KRa是互逆的，所以可以通过检验KRa的值来验证提供的Pa是正确的：只要简单地拿出一些任意的消息块X，然后确认X=DKra[EKUa[X]]。b.因为文件/etc/publickey是公共可读的，一个攻击者可以通过猜测口令P（即P"）并且计算KRa"=DP"[EP[KUa]]。然后他任意地选择一个任意的消息块Y来验证Y=DKRa[EKUa[Y]]是否正确。如果正确，那么极有可能P"=P成立。其他消息块可以验证这个等式的正确性。16.6、UNIX口令所使用的加密方案是单向的，不可能倒转。因此，是否可以这样说，这实际上是一个散列代码，而不是对口令的加密？答案：是的。16.7、前面曾经讲述过，在UNIX口令方案中包含salt将猜出口令的难度增加了4096倍。但是salt是以明文的形式与密码口令保存在同一项中的，因此，攻击者可以知道这两个字符而不需要猜测，那么为什么说salt可以增加安全性？答案：如果不使用salt，当攻击者猜测到口令并将其加密后，如果系统中每一个用户都是使用的这个口令的话，攻击者可以攻击任何一个用户。如果使用salt，攻击者必须针对系统中的每一个用户所使用的不同salt来进行猜测口令以及对口令加密。16.8、假设你已经成功地回答了前面的问题并且理解salt的重要性，现在还有一个问题：通过动态地增加salt的长度，例如增加到24位或48位，是否可以完全阻挡所有的口令攻击？答案：这有赖于用户群的规模大小而非salt的规模大小，因为攻击者可能已经访问过每一个用户的salt文件了。更长salt的优点是：salt越长，两个用户之间的salt越不可能相同。如果多个用户使用一个相同的salt，那么攻击者只需要给每个口令猜测做一次加密就可以测试出所有这些用户。16.9、是否可以开发出一个程序，通过分析软件的一部分来判断它是否是病毒。假设下面的程序D可以完成这样的功能。也就是说，对任意程序P，如果运行D（P），则结果返回TRUE或FALSE。现在考虑如下过程：ProgramCV：={…main-program：={ifD（CV）thengotonext：Elseinfect-executable；}next：}在这个处理过程中，infect-executable是扫描执行程序的内存并将自己复制到该执行程序中去的一个模块。请确定一下，D是否能正确地判断出CV是否是一个病毒。答案：D是用来判断程序P是否是病毒的，如果是，则结果返回TRUE；如果不是，则结果返回FALSE。CV调用D，如果D判断CV是病毒，CV将不感染可执行程序；如果D判断CV不是病毒，CV将感染可执行程序。D的判断总是错误，所以D不能正确地判断出CV是否是一个病毒。16.10、在一个多级安全系统中，规则“不向上读”的必要性是很显然的，那么规则“不向下写”的重要性是什么？答案：“不向下写”规则即*属性的目的是为了提出特洛伊木马的问题。根据*属性，通过木马使用过的信息不能被妥善处理。在这个属性之下，一个正在运行的程序代表着一个使用者不能给访问安全级比它低的或者是和它断层的使用者传递信息。16.11、图16.11中，特洛伊木马的复制并在以后观察的链断了。这时，Alice有两种从其他角度进行攻击的可能：Alice登录并试图直接读取字符串，或者Alice指定对“back-pocket”文件敏感的安全级。请问基准监视器是否可以阻拦这些攻击？答案：Drake没有被授权直接读取字符串，因此不向上读的规则禁止了这种企图。同样地，Drake71 没有授权指定对“back-pocket”文件敏感的安全级，所以这种企图也被禁止。16.12、假设有人提出了以下方法来证实你们两个人同时拥有同一个密钥。首先由你创建一个与密钥长度相同的随机位字符串，然后与密钥进行XOR（异或）运算，并把结果发送到通道。你的伙伴对到来的数据块与密钥（这个密钥应该与你的相同）进行XOR（异或）运算，把它送回，然后由你检测现在收到的是否是原来那个随机字符串。这样，不需要传送密码，就可以验证你和你伙伴是否拥有相同的密钥。请问这个方案有什么缺陷吗？答案：是的。偷听者会得到2个字符串，其中一个是向每个方向发送的，而这个字符串异或运算后所得到的值就是密钥。张翰兴整理71'