计算机操作系统试题库

举例说明，只有被操作系统管理和控制的资源才能被用户使用。答：在没有操作系统的时候，计算机系统的资源完全由用户和用户程序来控制和管理，使用非常不便。有了操作系统，计算机系统的资源由操作系统控制和管理，用户通过操作系统的服务接口使用这些资源。如果操作系统没有控制和管理某些资源，用户就不能通过操作系统的服务接口使用这些资源。例如，DOS只能管理1MB的内存，装上再多的内存，一般用户也无法使用。举例说明，多道程序的引入提高了系统资源的利用率，同时也使操作系统复杂化。答：多道程序系统中存在着并发和并行操作。例如,在内存中同时装入几个用户程序，I/O操作与CPU计算机并行。由并发和并行而产生一系列问题：如何从一个活动切换到领一个；怎样保护一个活动使其另外一些活动的影响；如何实现相互依赖的活动间的同步等。用于国家导弹防御系统的计算机系统是一个什么样的系统？答：用于国家导弹防御系统的计算机系统是实时过程控制系统与实时信息处理系统相结合的系统。为什么中断机构对于多道操作系统是必不可少的？答：很多进程的切换是由中断引起的，如时钟中断,尤其是分时系统。用户程序进行系统调用时通过软中断来实现，如TRAP。通道和外设的操作也要向操作系统发送中断网络操作系统和分布式操作系统的区别？答：网络OS中的用户使用自己的机器可以访问网络上别的机器的资源,通过网络将很多机器连接起来,共享硬件资源，但是，整个系统对用户来说是分散的,不透明的。分布式OS的用户也是通过网络将多台机器连接起来，但是整个系统对用户是透明的，用户对整个OS就好像使用一个自己的机器一样。评价一个操作系统的主要因素有哪些？答：评价一个操作系统的主要因素有方便性、有效性、扩充性、开放性、可用资源的数量。多用户分时系统如何克服多道批处理系统的缺点？答：尽管多道批处理系统已经大大地提高了计算机系统的资源利用率,但是它的致命缺点是缺少交互性。怎样才能使系统既具有交互性又不使资源的利用率降低？资源利用率和交互性是一对矛盾。如果一台计算机能够连接多个操作台(终端)，允许多个用户同时在操作台上操作，每个操作台上的拥护执行一个程序，形成多个程序的并发执行。通过并发程序的分时执行,确保每个用户操作的计算机终端就好象单独一台计算机一样。这样就避免了只有一个操作台时，大量的计算机时间被一个用户浪费，同时又克服了多道批处理系统非交互性的缺点。将手工操作、单道批处理、多道批处理、多用户分时系统按CPU的有效利用率，由小到大进行排列。答：手工操作、单道批处理系统、多用户分时系统、多道批处理系统。(1)手工操作没有操作系统，属于单道程序系统,大量的处理机时间被人工操作所浪费，因此CPU的利用率很低。(2)单道批处理系统在一定程度上克服了手工操作的缺点，但仍属于单道程序系统，大量的CPU时间浪费在等待I/O操作的完成上。因此它的CPU利用率比手工操作的系统要高，但比多道程序系统要低。(3)多用户分时系统是多道程序系统，具有交互性。但是程序的分时运行需CPU不断地在多个程序之间进行切换，这种切换需要占用CPU时间。(4)多道批处理系统是多道程序系统，没有交互性。CPU在执行一道程序时一般切换到其他程序，只有在需要等待某种事件发生时，才切换到另一程序执行。因此，它的CPU切换次数远远低于分时系统，而CPU的有效利用率高于批处理系统。Windows这样的多任务系统和Unix这样的多进程系统在调度上有何不同？答：从调度上讲，在Windows这样的多任务系统中，当前执行哪个任务是由用户决定的，是用户可控制的；而在Unix这样的多进程系统中，当前运行哪个进程是由内部的调度算法决定，是对用户透明的，用户是不可直接控制的。进程和线程的主要区别是什么？答：在有进程和线程的系统中，进程是系统资源分配的独立单位，而线程是可调度运行的独立单位。程序的并发执行为什么会有间断性？答：并发执行是指系统内有多道程序在宏观上”同时”执行，但系统内往往只有一台处理机(CPU),因此只能分时地为多个程序服务。就一道程序而言，往往不是一次能够运行完成，而是以“走走停停”的方式完成其运行，这就是并发系统内程序执行的间断性。进程能自己将自己唤醒吗？进程能自己将自己撤销吗？答：唤醒进程和撤消进程都是要通过CPU上运行程序来实现的。一个进程入睡了，它就不可能被调度到CPU上运行；一个进程在撤消前必须先进入终止状态，而处于终止状态的进程不可能被调度到CPU上运行。因此，进程被唤醒、被撤消都不能由自己来完成，只能由别的进程实现。什么是原语？原语的主要特点是什么？答：原语是指由若干条机器指令构成的，并用以完成特定功能的一段程序。这段程序在执行期间是不可分割的。其主要特点是不可分割性。程序并发执行与顺序执行时相比产生哪些新特征？答：程序并发执行与顺序执行时产生的特性有：可分割性、失去封闭性、失去可再现性。程序并发执行的主要特点是什么？此题答案为：答：程序并发执行的主要特点是并发程序间具有相互制约的关系，程序并发执行失去了程序的封闭性和再现性，程序和机器执行程序的活动不再—对应。一个因等待I/O操作结束而进入阻塞状态的进程,何时被唤醒？答：是在别的进程执行相应的I/O中断处理程序时唤醒的。在什么情况下，可以一次唤醒一个进程和一次唤醒多个进程？答：在I/O中断处理程序中，当唤醒进程时，只唤醒等待该I/O结束的那一个进程；当一个进程释放一个系统资源（如I/O缓存）时,将要唤醒所有因等待使用该资源而进入阻塞状态的进程。进程的就绪状态和阻塞状态有何不同？答：阻塞状态的进程还不具务执行的条件，即使放到处理机上能执行；就绪状态的进程具备了执行的所有条件，放在处理机上就能执行。程序的并发执行将导致运行结果失去封闭性，这对所有的程序都成立吗？答：并不是所有程序的并行执行都会导致运行结果失去封闭性。例如，当程序中都使用内部变量，不可能被外部程序访问时，程序的运行不会受到环境的影响。父进程创建子进程之后，父子进程间的关系是什么？答：一个进程创建子进程之后，进程与产生的进程之间的关系是父子关系，分别成为进程和子进程。子进程一经产生就与你进程并发执行，子进程共享父进程和子进程。子进程一经产生就与你进程并发执行，子进程共享父进程的正文段和已经打开的文件。什么是线程？进程和线程的关系是什么？答：线程可定义为进程内的一个执行单位，或者定义为进程内的一个可调度实体。在具有多线程机制的操作系统中，处理机调度的基本单位不是进程而是线程。一个进程可以有多个线程，而且至少有一个可执行线程。进程和线程的关系是：⑴线程是进程的一个组成部分。(2)进程的多个线程都在进程的地址空间活动。(3)资源是分给进程的，而不是分给线程的，线程在执行中需要资源时，系统从进程的资源分配额中扣除并分配给它。(4)处理机调度的基本单位是线程，线程之间竞争处理机，真正在处理机上运行的是线程。(5)线程在执行过程中，需要同步。简述引进线程的好处。答：引进线程的好处为：(1)以线程作为系统调度的基本单位，减少了系统的时空开销。以进程为系统调度的基本单位的系统中，进程的切换是很频繁的。在切换中由于要保留当时的运行环境，还要设置新选中的进程的运行环境，这既花费了处理机的时间，又增加了主存的空间，从而也限制了系统进程的数量和进程的切换速度。(2)引进线程提高了系统的并行能力。线程作为进程内的一个可执行实体，减少了并行粒度。线程作为调度的基本单位而不是资源分配的基本单位，调度更为容易，而且采用线程提高系统的并行能力比采用进程更为有效。(3)同一进程的线程共享进程的用户地址空间，所以同一进程的线程间的通信更容易实现。当系统内所有的进程都进入睡眠之后，系统还有可能复活吗？答：只有两种情况下系统可以复活：一种情况是有因等待I/O操作完成而进入睡眠的进程，当相应的I/O操作完成后，I/O中断处理程序唤醒等待本次I/O的进程，而该进程在运行过程中又可能通过释放资源、发送消息等事件而唤醒其他进程，这样整个系统就又活跃起来了；另一种情况是没有等待I/O操作完成的进程，但有定时睡眠的进程，当睡眠时间到期，会由时钟中断将该入睡进程唤醒，从而获得可运行进程，并有可能使系统重新活跃起来。当一个进程的父进程被撤销时，该进程是撤销好还是不撤销好？答：在实际系统中，两种处理办法都是可行的，且各有优缺点。若撤消，则该进程的任务可能还没有完成，这显然是不利的，特别是当该进程的运行结果对其他进程的运行很重要(如该进程是其他进程的前趋进程，没有它的运行结果其他进程无法运行)时；若不撤消，则该进程又可能成为不可控的“孤儿”，从而产生不可预测的结果。比较好的做法是，当一个进程的父进程被撤消时，可以将该进程“过继”给系统内一个级别较高的进程（如Unix中的1#进程），让它有一个”新的父亲”，这样既可以继续完成其任务又不会成为不可控的。当一个进程的父进程被撤销时，该进程是撤销好还是不撤销好？答：最主要的不同是“入睡”是进程的主动行为，而”挂起”可以是系统的强制行为；此处，只有在CPU上运行的进程才能执行“入睡”操作，而不管进程处于什么状态，系统都可对其执行“挂起”操作。它们的相同点是：这两个操作都导致一个正在CPU上运行的进程从CPU上退下来。简述进程为什么不能从就绪状态直接变成阻塞（睡眠）状态？答：一个进程要进入阻塞（睡眠）状态，必须通过执行相应的程序才能实现，如Sleep。或Block。。就绪进程当前不在CPU上运行，不能执行任何程序，当然不能使自己直接进入阻塞状态。在一个分时操作系统中，进程可能出现下面所示的变化。请将产生每一种变化的具体原因填写在下面横线上。A：运行B：就绪C：数据资源D：等待I/O传输⑴A-—B(2)A-C(3)C-A⑷A--D⑸D-B答：(1)时间片用完(2)请求资源⑶I/O请求(4)分配资源(5)1/0操作完成为什么说互斥也是一种同步？答：互斥指的是某种资源一次只允许一个进程使用，即你在使用的时候我不能使用；我在使用的时候你不能使用。这就是一种协调，一种“步伐”上的一致,因而也就是一种同步。但是，为了求解实际问题，将”同步“与“互斥”加以区别是有好处的，因为这两种问题的求解方法是不同的。为什么说进程同步问题关系到QS的成败？答：这是因为，进程同步问题若处理不当，有可能会产生种种”与时间有关性错误”，特别是当两个或多个进程共享了公共变量而又没有互斥地使用这些变量时，极有可能导致用户程序运行结果的不正确，这量种灾难性的后果。这种OS显然是不成功的，是用户不敢使用的。同步机制应遵循的准则是什么？答：有以下四条准则：空闲让进、忙则等待、有限等待、让权等待。进程通信有那三种基本类型？答：基于共享存储器的通信、基于消息传递系统的通信和基于管理文件的通信。简述解互斥问题的软、硬件方法的异同。答：软件方法是通过互斥地进入同类临界区来解互斥问题的，而硬件方法是设计相应的机器指令和机器指令执行的不可中断性来解互斥问题的。什么是原语？它与广义指令有什么区别？答：原语是由若干条机器指令构成的用以完成特定功能的一段程序，而这段程序在系统态下执行，且在执行期间是不可分割的。它与广义指令的区别主要体现在两个方面：(1)原语的执行是不可分割的，而广义指令所包含的程序段是允许被中断的，不要求具有不可分割性。(2)广义指令的功能可以在用户态下实现，而原语只能在系统态下执行。对临界区管理的要求是什么？答：对临界区管理的要求是：(1)当有若干个进程要求进入它们的临界区时，应在有限的时间内使一个进程进入临界区，进程之间不应相互等待而使谁都不能进入临界区。(2)每次只允许一个进程进入临界区内。(3)进程在临界区内逗留应在有限的时间范围内。设有n个进程共享一个互斥段，对于如下两种情况使用信号量，信号量的值的变化怎样？(1)如果每次只允许一个进程进入互斥段。(2)如果每次最多允许m个进程(mvn)同时进入互斥段。答(1)信号量的初值为1。信号量的变化范围是1,0,-1,…，-(n-1)o(2)信号量的初值为m。信号量的变化范围是试述引起多道程序系统程序执行不确定性的内部原因？答：程序执行不正确性，有两个方面：(1)程序执行结果不正确，即程序执行结果不能再现。同一个程序，对给定相同的初始数据，在相同的环境下运行，多次运行可能得到完全不同的结果。(2)多道程序环境下，程序按异步方式运行，每个程序在何时执行，各个程序执行的顺序，以及每个程序所需要的时间都是不确定的，也是不可预知的。例如，有三个程序P1,P2,P3,这次运行共花了10min,完成的次序是P2,P1,P3,下次运行可能要花15min,完成的次序是P3,P1,P2,等等。这种表现在外部的不确定性是由OS内部复杂的并发事件造成的。例如，随即产生的中断可改变一个进程的运行时间(因为中断处理时间记在被中断进程的账上)，而进程调度的不确定性导致程序完成先后次序的不确定性，没有正确的同步和互斥导致执行结果的不确定性，等等。如何理解原语的原子性，在单机环境下如何实现原语的原子性，实现时应注意哪些问题？答：所谓原语操作是指一个操作中的所有动作，要么成功完成，要么全不做。也就是说，原语操作是一个不可分割的整体。为了保证原语操作的正确性，必须保证原语具有原子性。在单机环境下，操作的原子性一般是通过关中断来实现的。由于中断是计算机与外设通信的重要手段，关中断会对系统产生很大的影响，所以在实现时一定要避免原语操作花费时间过长,绝对不允许原语中出现死循环。进程之间存在哪几种相互制约关系？各是什么原因引起的？下列活动分别属于哪种制约关系？(1)若干同学去图书馆借书。(2)两队举行篮球比赛。(3)流水线生产的各道工序。(4)商品生产和消费。答：进程间存在着两种相互制约的关系：直接制约关系(即同步问题)和间接制约关系(即互斥问题)。同步问题是存在逻辑关系的进程之间相互等待产生的制约关系，互斥问题是相互无逻辑关系的进程间竞争使用相同的资源所发生的制约关系。(1)属于互斥关系，因为书的个数是有限的，一本书只能借给一个同学。(2)属于互斥关系，篮球只有一个，两队都要争夺。(3)属于同步关系，各道工序的开始都依赖前道工序的完成。(4)属于同步关系，商品没生产出来，消费无法进行，商品未消费完，生产也无需进行。高级调度和低级调度的主要任务是什么？为什么引入中级调度？答(1)高级调度又称为作业调度。它是批处理系统中使用的一种调度。其主要任务是按照某种算法从外存的后备队列上选择一个或多个作业调入内存，并为其创建进程、分配必要的资源，然后再将所创建的进程控制块插入就绪队列中。(2)低级调度又称进程调度。它是距离硬件最近的一级调度。其主要任务是按照某种算法从就绪队列上选择一个(或多个)进程，使其获得CPU。(3)引入中级调度的目的是为了提高内存利用率和系统吞吐量。其功能是，让那些暂时不能运行的进程不再占用宝贵的内存资源，而是调其到外存上等候。此时的进程状态为挂起状态。当这些进程重新具备运行条件且内存空闲时，由中级调度选择一部分挂起状态的进程调入内存并将其状态变为就绪状态。在作业调度中需作出哪些决定？答（1）作业调度需要按照多道程序度（最大道数）决定一次接纳多少作业进入内存。如果太少将导致系统资源利用率低，且系统吞吐量低；太多将导致内存空间紧张，系统服务质量下降，作业运行周期过长。（2）作业调度需要决定接纳哪些作业进入内存。常用的算法有：先来先服务、短作业优先、最高优先级调度、响应比高者优先等。在剥夺调度中，有哪些剥夺原则？答（1）时间片原则。在轮转算法中，CPU轮流为诸多进程服务，每个进程运行完自己的时间片后，系统就将CPU剥夺过来，交给下一个进程使用。（2）优先级原则。为紧迫的作业赋予较高的优先级，这种作业到达系统或由阻塞状态被唤醒后，若其优先级高于当前运行的进程的优先级，可以剥夺当前运行进程的CPU。（3）短作业（进程）优先原则。若一个作业（进程）到达系统，其运行长度比当前运行的进程长度明显的短，则剥夺当前运行的进程CPU。文件、文件系统的概念？答：文件是具有符号名的、在逻辑上具有完整意义的一组相关信息项的有序序列。文件系统就是操作系统中实现文件统一管理的一组软件、被管理的的文件以及为实施文件管理所需的一些数据结构的总称。文件从不同角度（性质和用途、信息的保存期限、保护方式、逻辑结构、物理结构、存取方式、内容，特别是逻辑结构和物理结构），可以分哪几类？答:可以将文件划分为不同类别：1、按性质和用途可分为：系统文件；库文件；用户文件；2、按信息的保存期限可分为：临时文件；永久性文件；档案文件；3、按文件的保护方式可分为：只读文件；读写文件;可执行文件；无保护文件；4、按文件的逻辑结构可分为：流式文件；记录式文件；5、按文件的物理结构可分为：顺序文件；链接文件；索引文件；Hash文件；索引顺序文件6、按文件的存取方式可分为：顺序存取文件；随机存取文件；7、按文件内容可分为：普通文件；目录文件；特殊文件文件系统的功能和优点？答：文件系统的功能：1、统一管理文件存储空间（即外存），实施存储空间的分配与回收；2、确定文件信息的存放位置及存放形式；3、实现文件从名字空间到外存地址空间的映射，即实现文件的按名存取；4、有效实现对文件的各种控制操作（如建立、撤消、打开、关闭文件等）和存取操作（如读、写、修改、复制、转储等）；5、实现文件信息的共享，并且提供可*的文件保密和保护措施。文件系统的优点：1、按名存取文件，以对用户透明的方式实现对名字空间的管理和信息浮动，使用方便灵活；2、采取保护、保密措施，安全可靠；3、实现文件共享，节省空间和时间开销。具体阐述常用的几种文件物理结构及其优缺点。答：常见的文件物理结构有以下几种：1、顺序结构又称连续结构。这是一种最简单的物理结构，它把逻辑上连续的文件信息依次存放在连续编号的物理块中。只要知道文件在存储设备上的起始地址（首块号）和文件长度（总块数），就能很快地进行存取。这种结构的优点是访问速度快，缺点是文件长度增加困难。2、链接结构这种结构将逻辑上连续的文件分散存放在若干不连续的物理块中，每个物理块设有一个指针，指向其后续的物理块。只要指明文件第一个块号，就可以按链指针检索整个文件。这种结构的优点是文件长度容易动态变化，其缺点是不适合随机访问。3、索引结构采用这种结构，逻辑上连续的文件存放在若干不连续的物理块中，系统为每个文件建立一张索引表，索引表记录了文件信息所在的逻辑块号和与之对应的物理块号。索引表也以文件的形式存放在磁盘上。给出索引表的地址，就可以查找与文件逻辑块号对应的物理块号。如果索引表过大，可以采用多级索引结构。这种结构的优点是访问速度快，文件长度可以动态变化。缺点是存储开销大，因为每个文件有一个索引表，而索引表亦由物理块存储，故需要额外的外存空间。另外，当文件被打开时，索引表需要读入内存，否则访问速度会降低一半，故又需要占用额外的内存空间。4、Hash结构又称杂凑结构或散列结构。这种结构只适用于定长记录文件和按记录随机查找的访问方式。Hash结构的思想是通过计算来确定一个记录在存储设备上的存储位置，依次先后存入的两个记录在物理设备上不一定相邻。按Hash结构组织文件的两个关键问题是：定义一个杂凑函数;解决冲突；5、索引顺序结构索引表每一项在磁盘上按顺序连续存放在物理块中。什么是文件目录、目录文件与当前目录？答：文件控制块的有序集合构成文件目录，每个目录项即是一个文件控制块。为了实现文件目录的管理，通常将文件目录以文件的形式保存在外存空间，这个文件就被称为目录文件。目录文件是长度固定的记录式文件。系统为用户提供一个目前正在使用的工作目录，称为当前目录。文件目录结构有哪几种，各有什么优缺点？答：文件目录结构一般有一级目录结构、二级目录结构和多级目录结构。一级目录结构的优点是简单，缺点是文件不能重名，限制了用户对文件的命名。二级目录结构实现了文件从名字空间到外存地址空间的映射：用户名，文件名立文件内容。其优点是有利于文件的管理、共享和保护；适用于多用户系统；不同的用户可以命名相同文件名的文件，不会产生混淆，解决了命名冲突问题。缺点是不能对文件分类；当用文件较多时查找速度慢。多级目录结构的优点是便于文件分类，可为每类文件建立一个子目录；查找速度快，因为每个目录下的文件数目较少；可以实现文件共享；缺点是比较复杂。为了提高检索速度，对文件目录应做怎样的改进？答：可以利用目录项分解法解决这一问题，即把目录项（文件控制块）分为两部分：名号目录项，包含文件名以及相应的文件内部号；基本目录项，包含了除文件名外文件控制块的其他全部信息。目录文件也分为名号目录文件和基本目录文件。查找一个目录项就分成两步：首先访问名号目录文件，根据文件名查找相应的文件内部号；然后访问基本目录文件，根据文件内部号，可直接计算出相应基本目录项所在基本目录文件中的相对位置和物理位置，并将它直接读入内存。目录项分解法的优点是提高了文件目录检索的速度。为实现设备的有效管理，应采用怎样的数据结构?答：为实现设备、控制器、通道资源的分配与回收，系统需要记录有关的信息。通常设备管理要建立以下数据结构，以实施有效的管理。1、设备控制块2、控制器控制块3、通道控制块4、系统设备表什么是设备的独立性？根据设备的类型，设备的分配策略有哪些？（独占设备、共享设备、虚拟设备与SPOOLing系统）。以磁盘为例，有哪些优化调度算法？应考虑哪些因素？答：进程申请设备时，应当指定所需设备的类别，而不是指定某一台具体的设备，系统根据当前请求以及设备分配情况在相应类别的设备中选择一个空闲设备并将其分配给申请进程，这称作设备的独立性。磁盘调度一般可采用以下几种算法：1、先来先服务磁盘调度算法（FCFS）2、最短寻道时间优先磁盘调度算法（SSTF）3、扫描算法（SCAN）设计磁盘调试算法应考虑两个基本因素：1公平性2、高效性设备分配的任务是什么？设备分配应坚持的原则是什么？答：设备分配的任务是按照一定的策略为申请设备的进程分配合适的设备、控制器和通道。设备的独立性：不能因物理设备的更换而影响用户程序的正常运行；系统的安全性：设备分配不能导致死锁现象发生。简述通道控制的设备采用何种连接方式？其优点是什么？答：一般设备的连续采用交*连接，其好处是：1、提高系统的可*性：当某条通路因控制器或通道故障而断开时，可使用其他通路。2、提高设备的并行性：对于同一个设备，当与它相连的某一条通路中的控制器或通道被占用时，可以选择另一条空闲通路，减少了设备因等待通路所需要花费的时间。简述通道及通道控制结构。答：通道是一个用来控制外部设备工作的硬件机构，相当于一个功能简单的处理机。在一般大型计算机系统中，主机对外部设备的控制可以分成三个层次来实现，即通道、控制器和设备。一旦CPU发出启动通道的指令，通道就可以独立于CPU工作。通道控制控制器工作，控制器用来控制设备的电路部分。这样，一个通道可以连接多个控制器，而一个控制器又可以连接若干台同类型的外部设备。最终，设备在控制器控制下执行操作。外部设备的输入、输出方式有哪些？答：主要有以下四种：1、循环测试I/O方式；2、中断处理方式；3、直接内存存取（DMA）方式；4、通道方式设备管理的目标和功能是什么？答：设备管理的目标：1、向用户提供外部设备的方便、统一的接口，按照用户的要求和设备的类型，控制设备工作，完成用户的输入输入请求。2、充分利用中断技术、通道技术和缓冲技术，提高CPU与设备、设备与设备之间的并行工作能力，以充分利用设备资源，提高外部设备的使用效率。3、设备管理就是要保证在多道程序环境下，当多个进程竞争使用设备时，按照一定的策略分配和管理设备，以使系统能有条不紊地工作。设备管理的功能：1、设备分配和回收；2、管理输入输入缓冲区；3、设备驱动，实现物理I/O操作；4、外部设备中断处理；5、虚拟设备及其实现。设备可以按照何种方式分类，每种分类方式又包括哪些？答：1、按设备的工作特性分类（1）存储设备；（2）输入输出设备2、按设备上数据组织方式分类1）块设备；（2）字符设备3、按资源分配的角度分类（1）独占设备；（2）共享设备；（3）虚拟设备什么是操作系统管理的设备管理？答：设备管理是指计算机系统中除了CPU和内存以外的所有输入、输出设备的管理。在虚存中，页面在内存与外存中频繁地调试，系统效率急剧下降，称为颠簸。试说明产生颠簸的原因。通过什么方式可以防止颠簸的发生？答：颠簸是由缺页率高而引起的。系统规定缺页率的上界和下界。当运行进程缺页率高于上界时，表明所分给它的物理页面数过少，应当增加;反之，当运行进行缺页率低于下界时，表明所分给它的物理页面数过多，可以减少。这样，根据缺页率反馈可动态调整物理页面的分配，以防止颠簸的发生。以虚拟页式存储管理为例介绍虚拟存储管理的实现过程。答：虚拟页式存储管理的基本思想是，在进程开始执行之前，不是装全部页面，而是只装一个（甚至0个）页面，然后根据进程执行的需要，动态地装入其它页面。1、页表2、缺页中断处理3、页面淘汰。虚拟存储技术的理论基础（局部性原理）是什么？答：程序局部性原理：虚拟存储管理的效率与程序局部性程序有很大关系。根据统计，进程运行时，在一段时间内，其程序的执行往往呈现出高度的局限性，包括时间局部性和空间局部性。1、时间局部性：是指若一条指令被执行，则在不久，它可能再被执行。2、空间局部性：是指一旦一个存储单元被访问，那它附近的单元也将很快被访问。试述段页式存储管理的基本思想。答：段页式存储管理的基本思想是：1、用页式方法来分配和管理内存空间，即把内存划分成若干大小相等的页面；2、用段式方法对用户程序按照其内在的逻辑关系划分成若干段；3、再按照划分内存页面的大小，把每一段划分成若干大小相等的页面；4、用户程序的逻辑地址由三部分组成，形式如下：段号页号页内地址5、内存是以页为基本单位分配给每个用户程序的，在逻辑上相邻的页面内存不一定相邻。为了提高存取速度，可以使用快表技术。试述这一技术是如何实现的？答：快表技术是在地址映射机构中增加一个小容量的联想寄存器（相联存储器），它由高速寄存器组成，成为一张快表，快表用来存放当前访问最频繁的少数活动页的页号。在快表中，除了逻辑页号、物理页号对应外，还增加了几位。特征位表示该行是否为空，用0表示空，用1表示有内容；访问位表示该页是否被访问过，用0表示未访问，1表示已访问，这是为了淘汰那些用得很少甚至不用的页面而设置的。快表只存放当前进程最活跃的少数几页，随着进程的推进，快表内容动态更新。当用户程序需要存取数据时，根据该数据所在逻辑页号在快表中找出对应的物理页号，然后拼接页内地址，以形成物理地址；如果在快表中没有相应的逻辑页号，则地址映射仍然通过内存中的页表进行，得到物理页号后须将该物理页号填到快表的空闲单元中。有无空闲单元，则根据淘汰算法淘汰某一行，再填入新得到的页号。实际上查找快表和查找内存页表是并行进行的，一旦发现快表中有与所查页号一致的逻辑页号就停止查找内存页表。试述页式存储管理的基本原理。答：①内存划分。②逻辑地址空间划分。③页面大小。④内存分配。什么是固定分区？什么是可变分区？各有什么优缺点？答：固定分区：系统将内存划分为若干固定的分区，当作业申请内存时，系统为其选择一个适当的分区，并装入内存运行。由于分区大小是事先固定的，因而可容纳作业的大小受到限制，而且当用户作业的地址空间小于分区的存储空间时，浪费了一些存储空间。可变分区：是指在作业装入内存时建立分区，使分区的大小正好与作业要求的存储空间相等。引入可变分区方法，使内存分配有较大的灵活性，也提高了内存利用率。什么叫碎片？（零散的小空闲区）怎样解决碎片问题？（紧凑技术）。答：所谓碎片是指内存中出现的一些零散的小空闲区域。解决碎片的方法是移动所有占用区域，使所有的空闲区合并成一片连续区域。这一过程称为紧凑，这一技术就是紧凑技术。怎样对内存进行分区？（静态、动态；等长、不等长）答：对内存空间的划分是可以静态的，也可以动态的；可以是等长的，也可以不等长。静态划分是指系统运行之前就将内存空间划分成若干区域，通常，分配给进程的内存可能比进程实际所需的区域长。动态划分是在系统运行过程中才划分内存空间。这样，系统可按进程所需要的存储空间大小为其分配恰好满足要求的一个或多个区域。等长分区是将存储空间划分为若干个长度相同的区域。不等长分区则是将存储空间划分若干个长度不同的区域。什么叫物理地址？什么叫逻辑地址？什么叫地址映射？地址映射分哪几类？（静态、动态）答：物理地址是内存中各存储单元的编号，即存储单元的真实地址，它是可识别、可寻址并实际存在的。用户程序经过编译或汇编形成的目标代码，通常采用相对地址形式,其首地址为零，其余指令中的地址都是相对首地址而定。这个相对地址就称为逻辑地址或虚拟地址。逻辑地址不是内存中的物理地址，不能根据逻辑地址到内存中存取信息。为了保证CPU执行程序指令时能正确访问存储单元，需要将用户程序中的逻辑地址转运行时可由机器直接寻址的物理地址，这一过程称为地址映射或地址重定位。地址映射可分为两类：1、静态地址映射2、动态地址映射虚存储器的含义是什么？（两层含义）答：虚存储器有两层含义，一是指用户程序的逻辑地址构成的地址空间；二是指当内存容量不满足用户要求时，采用一种将内存空间与外存空间有机地结合在一起，利用内外存自动调度的方法构成一个大的存储器，从而给用户程序提供更大的访问空间。如何实现存储保护？答：在多道程序系统中，内存中既有操作系统，又有许多用户程序。为使系统正常运行，避免内存中各程序相互干扰，必须对内存中的程序和数据进行保护。1、防止地址越界对进程所产生的地址必须加以检查,发生越界时产生中断，由操作系统进行相应处理。2、防止操作越权对属于自己区域的信息，可读可写；对公共区域中允许共享的信息或获得授权可使用的信息，可读而不可修改；对未获授权使用的信息，不可读、不可写。存储保护一般以硬件保护机制为主，软件为辅，因为完全用软件实现系统开销太大，速度成倍降低。当发生越界或非法操作时，硬件产生中断，进入操作系统处理作业调度算法是按照什么样的原则来选取作业并投入运行，调试算法的合理性直接影响系统的效率，作业调度算法有哪些？对算法的选择要考虑哪些问题？答：作业调度算法：1、先来先服务算法；2、短作业优先算法；3、最高响应比作业优先算法；4、资源搭配算法；5、多队列循环算法对算法的选择要考虑三个目标：1、尽量提高系统的作业吞吐量，即每天处理尽可能多的作业；2、尽量使CPU和外部设备保持忙碌状态，以提高资源利用率；3、对各种作业公平合理，使用有用户都满意。以批处理方式下作业的管理为例，说明作业调度的主要任务、目标、计价作业调度算法优劣的性能指标、主要作业调度算法及作业调度的时机是什么？答：作业调度的主要任务是：按照某种调试算法，从后备作业中挑选一批合理搭配的作业进入运行状态；同时，为选中的作业分配内存和外部设备资源，为其建立相关的进程；当作业执行结束进入完成状态时，做好释放资源等善后工作。作业调度的目标：1、响应时间快；2、周转时间或加权周转时间短;3、均衡的资源利用率；4、吞吐量大；5、系统反应时间短。评价作业调度算法优劣的性能指标：1、作业平均周转时间；2、作业平均带权周转时间主要作业调度算法有：1、先来先服务法；2、短作业优先算法；3、最高响应比优先算法；4、资源搭配算法；5、多队列循环算法。作业调试时机：一般当输入井中有一道作业建立，或内存中的一道作业运行结束时，系统启动作业调试工作。算法题在信号量机制中，若P(S)操作是可中断的，则会有什么问题？答：P(S)的操作如下：BeginS.Value:=S.Value-1;①IfS.Value<0Then②Beginlnsert(*,S.L);Block(*)③EndEnd.若P(S)可中断的，例如进程A在执行了语句①之后从CPU上退下了，假定此时S.Value=O；这时换另一进程B,B又将S.Value的值减1使之为一1,在执行语句③时，B被阻塞；然后又换回A执行，由于A的"断点"是语句①之后，当它执行语句②时，由于这时S.Value已经是一1,故进程继续执行而被阻塞。这就出现了错误：本来A操作P(S)操作后，S.Value=O,是不应该被阻塞的，现在却被阻塞了。何谓临界区？下面给出的两个进程互斥的算法是安全的吗？为什么？definetrue;definefalse;Intflag[2];flag[1]=flag[2]=false;enter-crtsec(i)inti;(While(flag[1-i])flag[i]=true;)feave-crtsec(i)Inti;(flag[i]=false;}processI;Enter-crtsec(i);Incriticalsection;Leave-crtsec(i);答：一次仅允许一个进程使用的资源称为临界资源，在进程中对临界资源访问的程序段称为临界区。从概念上讲，系统中各进程在逻辑上是独立的，它们可以按各自的速度向前推进。但由于它们共享某些临界资源，因而产生了临界区问题。对于具有临界区问题的并发进程，它们之间必须互斥，以保证不会同时进入临界区。这种算法不是安全的。因为，在进入临界区的enter-crtsec()不是一个原语操作，如果两个进程同时执行完其循环(此前两个flag均为false),则这两个进程可同时进入临界区。当进程X和进程丫共享某个资源r,进程并发执行时的程序如下：BeginS:semaphore:=1;CobeginProcessXBeginL1:P(S);使用资源r;V(S);GotoL1;End;ProcessYBeginL2:P(S);使用资源r;V(S);GotoL2;End;Coend;End;请回答:(1)两个进程并发执行时，能否保证互斥地使用资源？为什么？(2)若要使用两个进程交替使用资源，仍使用P、V操作来进行管理，写出应定义的信号量及其初值。(3)修改上述程序，使两个进程能交替使用资源r。答：当进程X和进程Y共享某个资源r,(1)能保证互斥使用资源。因为在两个进程中，"使用资源r”都是作为临界区，由于P(S)和V(S)操作保证了互斥执行，S的初值定义为1,符合要求。(2)要使两个进程交替使用资源，仅仅保证互斥使用是不够的，必须要两个进程互相等待互相通知。为此，必须定义新的信号量。定义两个私有信号量S1和S2。假定进程X先使用资源，那么进程X的私有信号量S1的初值定义为1,进程丫的私有信号量S2的初值定义为0。轮流使用可以保证互斥，因此信号量S可以不要。(3)两个进程可以改写为：BeginS1:semaphore:=1;S2:semaphore:=1;CobeginProcessXBeginL1:P(S1);使用资源r;V(S2);GotoL1;End;ProcessY某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作个进程，请回答下列问题：(1)用P、V操作管理这些并发进程时，应怎样定义信号量？写出信号量的初值以及信号量各种取值的含义。(2)根据所定义的信号量，把应执行的P、V操作填入下述程序中，以保证进程能够正确地并发执行。CobeginPROCESSPi(i=1,2,„.)Begin进入售票厅；购票；退出；End;Coend(3)若欲购票者最多为n个人，写出信号量可能的变化范围(最大值和最小值)。答：售票厅问题解答如下：(1)定义一信号量S,初始值为20。S>0S的值表示可继续进入售票厅的人数：S=0表示售票厅中已有20名购票者；S<0|S|的值为等待进入售票厅中的人数。(2)上框为P(S),下框为V(S)。(3)S的最大值为20,S的最小值为20-N,N为某一时刻需要进入售票厅的最多人数。已经系统中有四个缓冲池M0,M1,M2,M3。其容量分别为3、2、3、2,现各缓冲区分别存在0、1、0、2个数据。现同时有四个进程P0、P1、P2、P3分别在各缓冲区间不断地移动数据(见图3.5)。例如，P0进程从M0向M1移动数据。试用信号量及其P、V(或signal,wait)操作及类Pasic/C语言描述各进程之间的同步关系，并给出各信号量的含义和初值。答：缓冲池各问题解答如下：(1)互斥信号量和初值M(0)=1,M(1)=1,M(2)=1,M(3)=1,(2)同步信号量Full(i)表示buffer(i)是否有数据；初值为full(O)=O,full⑴=1,full(2)=0,full(3)=2；Empty(i)表示buffer(i)是否有空间；初值为empty(0)=3,empty(1)=1,empty(2)=3,empty(3)=0(3)进程i的程序ProcessProc(i){P(full(i))；p(empty(i+1)mod5);P(m(i));move;v(m(i));v(m(full(i+1)mod5));v(empty(i));)设有两个优先级相同的进程P1和P2如下，信号量S1和S2的初值均为0。试问P1、P2并发执行结束后，x=?,y=?,z=?〈进程P1>Y:=1;Y:=y+2;V(S1);Z:=y+1;P(S2);Y:=z+y;〈进程P2>X:=1;X:=x+1;P（S1）；X:=x+y;V（S2）;Z:=x+z;答：因为P1和P2是两个并发进程，所以进程调度程序调度P1和P2的顺序是不确定的。这里不妨假设P1先执行。进程P1执行到语句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=12,最终结果是：x=5,y=12,z=91>如果当P2进程执行到V（S2）时，将P1唤醒，然后P2进程被中断，此时x=5,y=3,z=4。P1进程开始执行然后执行最后一个语句y：=z+y,此时x=5,y=3,z=7。然后P2进程被调度，执行z:=x+z,此时x=5,y=3,z=12»如果P2先执行，则执行结果与上面相同。在批处理系统、分时系统和实时系统中，各采用哪几个进程（作业）调度算法？答（1）批处理系统中的作业调度算法有：先来先服务算法（FCFS）、短作业优先算法（SJF）、优先级调度算法（HPF）和高响应比优先算法（RF）。批处理系统的进程调度算法有：先进先出算法（FIFO）,短进程优先算法（SPF）、优先级调度算法（HPF）和高响应比优先算法（RF）。（2）分时系统中只设有进程调度（不设作业调度），其进程调度算法只有轮转法（RR）一种。（3）实时系统中只设有进程（不设作业调度），其进程调度算法调度有：轮转法、优先级调度算法。前者适用于时间要求不严格的实时系统;后者用于时间要求严格的实时系统。后者又可细分为：非抢占式优先级调度、抢占式优先级调度、基于时钟中断的抢占式优先级调度。假设系统中有5个进程，它们的到达时间和服务时间见下表1,忽略I/O以及其他开销时间，若按先来先服务（FCFS）、非抢占的短作业优先和抢占的短作业优先三种调度算法进行CPU调度，请给出各个进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间，完成表2。表1进程到达和需要服务时间进程到达时间服务时间B26C44D65E82表2进程的完成时间和周转时间进程ABCDE平均FCFS完成时间周转时间带权周转时间SPF（非抢占）完成时间周转时间带权周转时间SPF（抢占）完成时间周转时间带权周转时间答：表2进程的完成时间和周转时间进程ABCDE平均FCFS完成时间39131820周转时间37912128.6带权周转时间1Q01.172.252.406.002.56SPF（非抢占）完成时间39152011周转时间37111437.6带权周转时间1.001.171.752.801.501.84SPF（抢占）完成时间31582010周转时间31341427.2带权周转时间1.002.161.002.801.001.59一个逻辑空间最多可有64个页，每页1KB字节。若把它映射到由32个物理块组成的存储器。间（1）有效的逻辑地址由多少位？（2）有效的物理地址由多少位？答：一个逻辑空间有64个页，每页1KB字节。若把它映射到由32个物理块组成的存储嚣。64=26,则（1）逻辑地址有16位（2）物理地址有15位。在某分页系统中，测得CPU和磁盘的利用率如下，试指出每种情况下的问题和措施。CPU的利用率为15%,磁盘利用率为95%。CPU的利用率为88%,磁盘利用率为3%。CPU的利用率为13%,磁盘利用率为5%。答：在某分页虚存系统中，在题中的CPU和磁盘的利用率的情况下，出现的问题和应采取的措施如F：（1）可能已出现了抖动现象，应减少系统的进程数。（2）系统比较正常，可考虑适当增加进程数以提高资源利用率。（3）CPU和磁盘的利用率都较低，必须增加并发进程数。对访问串：1,2,3,4,1,2,5,1,2,3,4,5,指出在驻留集大小分别为3,4时，使用FIFO和LRU替换算法的缺页次数。结果说明了什么？答：首先采用FIFO,当m=3时，缺页次数=9,当m=4时，缺页次数=10。采用LRU算法，当m=3时，缺页次数=10：当m=4时，缺页次数=8。结果说明：FIFO有Belady奇异现象，即不满足驻留集增大，缺页次数一定减小的规律；另外在m=3时，LRU的缺页次数比FIFO要多，所以LRU算法并不总优于FIFO,还要看当前访问串的特点。一个分页存储器的页表存放在内存。（1）若内存的存取周期为0.6ms,则CPU从内存取一条指令（或一个操作数）需多少时间？（2）若使用快表且快表的命中率为75%,则内存的平均存取周期为多少？答：一个分页存储器的页表存放在内存（1）因为页表放在内存，故取一条指令（或一个操作数）须访问两次内存，所以需0.6msx2=1.2ms的时间。（2）这里家假设访问快表的时间忽略不计，命中快表时，取数只要一次访问，故此时的平均存取周期为0.6msx0.75+1.2msx（1-0.75）=0.75ms在一个请求分页系统中，采用LRU页面置换算法时，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5,当分配给该作业的物理内存块数M分别为3和4时，分别计算在访问过程中所发生的缺页次数和缺页率，并画出页面置换图。解：访问过程中缺页情况（M=3）页面走向432143543215最近最长时间未使用的页面433243543243214354321最近刚使用过的页面432143543215缺页当M=3时，缺页次数为10次，缺页率为10/12=0.83=83%。访问过程中缺页情况(M=4)页面走向432143543215最近最长时间未使用的页面432111543432143543243214354321最近刚使用过的页面432143543215缺页W«W当M=4时，缺页次数为8次，缺页率为8/12=0.66=66%。可见，增加分配给作业的内存块数可以减少缺页次数，从而降低缺页率。对于一个使用快表的页式虚存，设快表的命中率为70%,内存的存取周期为1ns；缺页处理时，若内存有可用空间或被置换的页面在内存未被修改过，则处理一个缺页中断需8000ns,否则需20000ns。假定被置换的页面60%是属于后一种情况，为了保证有效存取时间不超过2ns,问可接受的最大缺页率是多少？答：设可接受的最大缺页率位P，则有1nsx0.7+2nsx(1-0.7-p)+0.4px8000ns+0.6px20000ns=2ns即0.7+0.6-2p+3200p+12000p=215198p=0.7P=0.000046在分页存储管理系统中，存取一次内存的时间是8ns,查询一次快表的时间是1ns,缺页中断的时间是20ns。假设页表的查询与快表的查询同时进行，当查询页表时，如果该页在内存但快表中没有页表项，系统将自动把该页页表项送入快表。一个作业最多可保留3个页面在内存。现在开始执行一作业，系统连续对作业的2,4,5,2,7,6,4,8页面的数据进行一次存取，如分别采用FIFO算法和最优页面置换算法，求每种上存取这些数据需要的总时间。答(1)FIFO第2页面：20+8x3第4页面：20+8x3第5页面：20+8x3第2页面：8+1第7页面：20+8x3第6页面：20+8x3第4页面：20+8x3第8页面：20+8x3因此总的时间是（20+8x3）x7+（8+1）ns（2）OPT第2页面：20+8x3第4页面：20+8x3第5页面：20+8x3第2页面：8+1第7页面：20+8x3第6页面：20+8x3第4页面：8+1第8页面：8+1因此总的时间是（20+8x3）x5+（8+1）x3ns在一个请求分页系统中，采用LRU页面置换算法时，假如一个作业的页面走向为1、3、2、1、1、3、5、1、3、2、1、5,当分配给该作业的物理内存块数M分别为3和4时，分别计算在访问过程中所发生的缺页次数和缺页率，并画出页面置换图。解：访问过程中缺页情况（M=3）页面走向132113513215最近最长时间未使用的页面133213513213221351321最近刚使用过的页面132113513215缺页777777当M=3时，缺页次数为6次，缺页率为6/12=0.5=50%。访问过程中缺页情况（M=4）页面走向132113513215最近最长时间未使用的页面222553133213513213221351321最近刚使用过的页面132113513215缺页“4Y当M=4时，缺页次数为4次，缺页率为4/12=0.33=33%。可见，增加分配给作业的内存块数可以减少缺页次数，从而降低缺页率。在一个请求分页系统中，采用OPT页面置换算法时，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5,当分配给该作业的物理内存块数M分别为3和4时，分别计算在访问过程中所发生的缺页次数和缺页率，并画出页面置换图。解：访问过程中缺页情况（M=3）页面走向432143543215最近最长时间未使用的页面2111544/33/21/23334335最近刚使用过的页面44443443555缺页7777777当M=3时，缺页次数为7次，缺页率为7/12=0.583=58.3%。访问过程中缺页情况（M=4）页面走向432143543215最近最长时间未使用的页面111544/34/3/21/3/222222533343325最近刚使用过的页面44443443255缺页«««7««当M=4时，缺页次数为8次，缺页率为6/12=0.5=50%。可见，增加分配给作业的内存块数可以减少缺页次数，从而降低缺页率。在•个请求分页系统中，采用FIFO页面置换算法时，假如•个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5,当分配给该作业的物理内存块数M分别为3利4时，分别计算在访问过程中所发生的缺页次数和缺页率，并画出页面置换图。解：访问过程中缺页情况（M=3）页面走向432143543215最近最长时间未使用的页面432144435543214333522最近刚使用过的页面432143555211缺页当M=3时，缺页次数为9次，缺页率为9/12=0.75=75%。访问过程中缺页情况(M=4)页面走向432143543215最近最长时间未使用的页面444321543433321543243222154321最近刚使用过的页面432111543215缺页当M=4时，缺页次数为10次，缺页率为10/12=0.86=83%。可见，增加分配给作业的内存块数并不能减少缺页次数，降低缺页率，这种现象叫抖动现象(Belady).利用信号量机制描述前趋关系：S={S1,S2,S3,S4,S5,S6,S7}={(S1,S2),(S1,S3),(S2,S4),(S2,S5),(S3,S5),(S3,S6),(S4,S7),(S5,S7),(S6,S7)}解：Vara,b,c,d,e,f,g,h,i,:semaphore:=0,0,0,0,0,0,0,0,0,0;BeginParbeginBeginS1;signal(a);signal(b);end;Beginwait(a);S2;signal(c);signal(d);end;Beginwait(b);S3;signal(e);signal(f);end;Beginwait(c);S4;signal(g);end;Beginwait(d);wait(e);S5;signal(h);end;Beginwait(f);S6;signal(i);end;Beginwait(g);wait(h);wait(i);S7;end;Parend利用记录型信号量解决经典同步问题：生产者——消费者解：Varmutex,empty,full:semaphore:=1,n,0;buffer:array[0,...,n-1]ofitem;in,out:integer:=0,0;beginparbeginproceducer:beginrepeatproduceranitemnextp;wait(empty);wait(mutex);buffer(in):=nextp;in:=(in+1)modn;signal(mutex);signal(full);untilfalse;endconsume匚beginrepeatwait(full);wait(mutex);nextp:=buffer(out);out:=(out+1)modn;signal(mutex);signal(empty);consumertheiteminnextc;untilfalse;endpatendend利用记录型信号量解决经典进程同步问题：读者——写者解：Varrmutex,wmutex:semaphore:=1,1;Readcount:integer:=0;BeginparbeginReader:beginrepeatwait(rmutex)ifReadcount=0thenwait(wmutex);Readcount:=Readcount+1;signal(rmutex)performreadoperation;wait(rmutex);Readcount:=Readcount-1;ifReadcount=0thensignal(wmutex);signal(rmutex);untilfalse;endWriter:beginrepeatwait(wmutex);performwriteoperation;signal(wmutex);untilfalseendparendEnd有一个车间不断取A和B进行装配，每次各取一个。为避免零件锈蚀，遵循先入库者先出库的原则。有两组供应商分别不断供应A和B(每次1个)。为保证齐套和合理库存，当某种零件的数量比另一种零件的数量多得超过n(n<m)时，暂停对数量大的零件的供货，集中补充数量少的零件。试用Wait和Signal原语正确实现。解：varmutex,emptya,emptyb,fulla,fullb,sa,sb:semaphore:=1,m,m,0,0,n,n;Begincobeginprovider_A();provider_B();assembiling_shop();coendprovider_A()beginrepeatwait(emptya);wait(sa);wait(mutex);putAintothestorehouse;signal(mutex);signal(fulla);signal(sb);untilfalse;provider_B()beginrepeatwait(emptyb);wait(sb);wait(mutex);putBintothestorehouse;signal(mutex);signal(fullb);signal(sa);untilfalse;endasemmbling_shop()beginrepeatwait(fulla);wait(fullb);wait(mutex);asemmblingAandB;signal(mutex);signal(emptya);signal(emptyb);untilfalse;endcorendEnd一个主修动物行为学，辅修计算机科学的学生参加了一个课题，调查花果山的猴子能否被教会理解死锁。他找到一处峡谷，横跨峡谷拉了一根绳索(假设为南北方向)，这些猴子就可以攀登着绳索跨过峡谷。只要它们朝着相同的方向，同一-时刻可以有多个猴子通过。但是如果在相反方向商同时有猴子通过则会发生死锁(这些猴子卡在绳子中间，假设这些猴子无法在绳索商从另一只猴子身上翻过去）。如果一只猴子想跨越峡谷，他必须看当前是否有别的猴子在逆向通过。请使用信号量写一个避免思索的程序来解决该问题。解：BeginvarSmutex^mutex^MonkeyCount^MonkeyCount^emaphore;SMonkeyCount:=0;NMonkeyCount:=0;Smutex:=1;Nmutex:=1;mutex:=1;ParBeginSouthi(i=192,3,...)Beginwait(Smutex);ifSMonkeyCount=0thenwait(mutex);SMonkeyCount:=SMonkeyCount+1;signal(Smutex);Crossthecordage;wait(Smutex);SMonkeyCount:=SMonkeyCount-1;ifSMonkeyCount=0thensignal(mutex);signal(Smutex);EndNorthi(i=1,2,3,...)Beginwait(Smutex);ifNMonkeyCount=0thenwait(mutex);NMonkeyCount:=NMonkeyCount+1;signal(Nmutex);Crossthecordage;wait(Nmutex);NMonkeyCount:=NMonkeyCount-1;ifNMonkeyCount=0thensignal(mutex);signal(Nmutex);EndparEndEnd设有两个生产者进程A和B和一个销售进程C,它们共享一个无限大的仓库，生产者每次循环生产一个产品，然后入库供销售者销售；销售者每次循环从仓库中取出一个产品销售。如果不允许同时入库，也不允许同时出库；而且要求生产和销售A产品和B产品数量都满足以下关系：・nv=A的件数・B的件数v=m,其中n,m是正整数。请用信号量机制写出A,B,C三个进程的工作流程。解：Vardifference:integer:=O;SAB,SBA,S,SA,SB,mutex:semaphore:=m,n,0,0,0,1;BeginparbeginprocessA:beginrepeatwait(SAB);produceaproductA;signal(SBA);wait(mutex);addtheproductAtothestorehouse;signal(mutex);signal(SA);signal(S);untilfalse;endprocessB:beginrepeatwait(SBA);producebproductB;signal(SAB);wait(mutex);addtheproductBtothestorehouse;signal(mutex);signal(SB);signal(S);untilfalse;processC:beginrepeatwait(S);ifdifference<=-nthenbeginwait(SA);wait(mutex);takeaproductAfromstorehouse;signal(mutex);difference:=difference+1;endelseifdifference>=mthenbeginwait(SB);wait(mutex);takeaproductBfromstorehouse;signal(mutex);difference:=difference-1;endelsewait(mutex);takeaproductAorBfromstorehouse;signal(mutex);if(product_type=A)thenbeginwait(SA);difference:=difference+1;endelsebeginwait(SB);difference:=difference-1;endselltheproduct;untilfalse;parendEnd试证明：如果系统作业几乎同时到达,则使系统平均作业周转时间最短的算法是短作业优先。解：设有n个作业j1J2J3,…Jn,其运行时间分别为不妨假设t1<=t2<=t3<=...<=tn,则短作业优先的作业调度算法的平均周转时间为：T=(t1+(t1+t2)+(t1+t2+t3)+....(t1+t2+t3+...+tn))/n=(n*t1+(n-1)*t2+...+tn)/n考虑其他不同调度算法，设在此调度算法下的作业调度次序为ji1Ji2,…jin,其中(i1,i2,...,in)是(1,2,3,・.・,n)的一个排列，则类似上面可以得出：T1=((n*ti1+(n-1)*ti2+...+tin)/n)根据不等式结论：如果有a1v=a2v=...v=an且b1v=b2v=...v=bn,则a1bn+a2bn-1+...+anb1<=a1bi1+a2bi2+...+anbn<=a1b1+a2b2+...+anbn其中(i1,i2，…,in)是(1,2,3，…,n)的一个排列，不难得出T<=T1。采用银行家算法防止死锁，用Pi-n表示Pi进程申请n个资源，用Pi-n表示Pi进程占有n个资源。如果占有n个资源的进程被阻塞，可以用Pi*-n来表示，假设系统中有某类资源10个，进程P1,P2,P3各自的最大需求量为3,7,10个,各进程T0时刻开始运行：T1时刻发生:P1-2,P2T3,P3T3T2时刻发生：P2—1,P3T2T3时刻发生：P1—1,P2Tl根据银行家算法，填写三个时刻的进行占有和阻塞情况.进程TOT1T2T3P1P2P3P2P3解：进程T0T1T2T3P1P1—0P1—2P1—2P1-3P2P2—0P2—3P2-4P2*-4P3P3—0P3-3P3*—3P3*-3有两个用户进程A和B,在运行过程中都要使用系统中的一台打印机输出计算结果。(1)试说明A、B两进程之间存在什么样的制约关系？答：A、B两进程之间存在互斥的制约关系。因为打印机属于临界资源，必须一个进程使用完之后另一个进程才能使用(2)为保证这两个进程能正确地打印出各自的结果，请用信号量和P、V操作写出各自的有关申请、使用打印机的代码。要求给出信号量的含义和初值。答：mutex：用于互斥的信号量，因为只有一台打印机，所以初值为1进程A进程BP(mutex)；P(mutex)；申请打印机；申请打印机;使用打印机；使用打印机；V(mutex)；V(mutex)；设input进程不断向缓冲区Q写入信息，output进程不断地将刚由input进程写入的信息读出。试问：(1)这两个进程有何相互制约关系？答：这两个进程的相互制约关系为同步关系：(2)试用P、V操作写出这两个进程完成这项任务的代码段和信号量的含义及初值。答：设两个信号量S1和S2。其中S1表示Q是否为空，初值为1,表示Q是空的：S2表示Q中是否有信息，初值为0,表示Q中无信息。两进程的代码段如下：input进程output进程While信息未处理完毕While信息未处理完毕｛加工一个信息；｛P(S2)：P(S1)；从Q中读出一个信息；将信息放入Q中；V(S1)；｝V(S2)；｝……假定在单道批处理环境下有5个作业，各作业进入系统的时间和估计运行时间如下表所示：作业进入系统时间估计运行时间/分钟8:00408:20308:30129:00189:105(1)如果应用先来先服务的作业调度算法，试将下面表格填写完整。作业进入系统时间估计运行时间/分钟开始时间结束时间周转时间/分钟作业平均周转时间T=（2）如果应用最短作业优先的作业调度算法，试将下面表格填写完整。作业进入系统时间估计运行时间/分钟开始时间结束时间周转时间/分钟2345作业平均周转时间T=（1）如果应用先来先服务的作业调度算法，试将下面表格填写完整。作业进入系统时间估计运行时间/分钟开始时间结束时间周转时间/分钟18:00408：008：404028:20308：409：105038:30129：109：225249:00189：229：404059:1059：409：4535作业平均周转时间T=43.4217（2）如果应用最短作业优先的作业调度算法，试将下面表格填写完整。作业进入系统时间估计运行时间/分钟开始时间结束时间周转时间/分钟18:00408：008：404028:20308：529：226238:30128：408：522249:00189：279：454559:1059：229：2717作业平均周转时间T=37.2186在请求分页系统中，某用户的编程空间为16个页面，每页1K,分配的内存空间为8K。假定某时刻该用户的页表如下图所示，试问:(1)逻辑地址084B(H)对应的物理地址是多少？(用十六进制表示)(2)逻辑地址5000(十进制)对应的物理地址是多少？(用十进制表示)(3)当该用户进程欲访问24A0H单元时，会出现什么现象？页号块号031724112596120⑴答:104B(H)(2)答：13192(3)答：24A0(H)的页号为9,而其页面当前不在内存，所以会发一个缺页中断，请求系统调页。两个并发执行的进程A和B的程序如卜：进程ARepeatN=N+5;Untilfalse;进程BRepeat打印N的值；N=0；Untilfalse;其中N为整数，初值为4。若进程A先执行了三个循环后，进程A和进程B又并发执行了一个循环，写出可能出现的打印值。正确的打印值应该是多少？请用P、V操作进行管理,使进程A和B并发执行时不会出现与时间有关的错误。答：因为N初值为4,若进程A先执行了三个循环，此时N的值为19。当进程A和进程B并发执行时可能会有如下两种执行次序，即进程A先执行一次循环，然后再进程B执行一次循环，此时打印的是正确值24,执行后N中的值为0。但若进程B先执行一次循环，然后再进程A执行一次循环，则打印的值是19,执行后N中的值是5。这是错误的，即发生了与时间有关的错误。用P、V操作进行管理，使进程A和B并发时不会出现与时间有关的错误的程序如下：(S为互斥信号量，初值为1),进程ARepeatP(S)；N=N+5;V(S);Untilfalse;进程BRepeatP(S)；打印N的值；N=0；V(S);Untilfalse;根据如下段表：段号基地址长度合法(0)/非法(1)03002001750054023000101032000100(1)求出逻辑地址为0,100的物理地址并将其的合法性填入上表适当位置；(2)求出逻辑地址为3,100的物理地址并将其的合法性填入上表适当位置；答：⑴答:物理地址为：300+100=400（2）答：物理地址为：2000+100=2100段号基地址长度合法（0）俳法（1）0300200017500540230001010320001001引起进程调度的主要因素有：答（1）一个进程运行完毕。（2）一个正在运行的进程被阻塞。（3）在抢占式调度中，一个高优先级的进程被创建。（4）在抢占式调度中，一个高优先级进程由阻塞唤醒。（5）在轮转式调度中，正垢进程运行完一个时间片。在选择调度方式和调度算法时，应遵循的原则是什么？答（1）面向用户准则。对于用户的紧迫性作业，系统能够及时地处理,不至于运行延误；批处理系统追求作业的周转时间短；分时系统追求作业的响应时间快；实时系统中作业的截止时间要有保证。（2）面向系统准则。系统的吞吐量要高，处理机的利用率要高，各类系统资源能够得到平衡利用。为什么说多级反馈队列能较好的满足各种用户的需要？答：终端用户的作业一般比较短小精悍，大多数在进入多级队列的第