操作系统★号为必考.doc

1_1 如何定义一个操作系统?答：操作系统是整个计算机系统的管理和控制中心(原创答案，原答案太长) 1_2 早期操作系统设计的主要目标是什么?答：1 方便性：向用户提供方便、简单的使用计算机的环境。 2有效性：使计算机系统高效地工作，提高系统资源的利用率。2_1何谓进程？是从动态性、并发性和独立性比较进程与程序。答：在多道程序环境下，程序的执行属于并发执行，此时它们将失去其封闭性，并具有间断性及不可再现性的特征。这就决定了通常的程序是不能参与并发过程。为此引入“进程”进程又叫任务，至今没有一个明确的定义。从动态性上比较进程和程序：程序是静态的代码序列，进程是程序的一次执行。是动态的过程。进程支持并发过程，而程序是不支持并发执行的。进程是资源分配和调度的基本单位。具有独立性。而程序不是如多用户系统中一个编译程序可以为多个用户服务。资源分配以进程为单位，不以程序为单位。 2_2 进程控制块PCB的作用是什么？它主要包括哪几部分内容？答：作为独立运行基本单位的标志 ，它包含了进程的描述信息和管理控制信息，操作系系统通过进程控制块管理和调度系统中的进程。主要包括：1.进程标识数2.进程的状态以及调度和存储管理信息。3.进程使用的资源信息4CPU现场保护区5.记账信息6.进程家族关系7.进程的链接指针。2._3 试说明进程在三个基本状态之间转换的典型原因？19 假定用一个信号量表示一把叉子，由5个信号量组成一个信号量组：semaphore fork5;所有的信号量初值为1，第i个哲学家的活动可描述为：2_10下面哪种调度算法可能导致出现进程饿死现象的发生？B, DA先来先服务 B 短作业优先 C轮转法 D 优先级法2_11就下面的问题，应由处理机的哪级调度完成？（1）在处理机即将空闲时，应为他分配一个就绪进程。 进程（低级）调度（2）在内存负载繁重的情况下，应设法减轻系统负载，以提高系统的运行效率。 交换（中级）调度 2_12假定系统有四道作业，它们的提交时间和运行时间（以小时为单位）如下表所示。在单道批处理系统中，采用先来先服务、最短作业优先的调度算法。分别计算下表作业的平均周转时间。假定系统有n个进程，共享m个单位资源。进程对资源的申请和释放遵守15题的原则，即进程每次只申请或释放一个资源。每个进程最大需求不超过m个所有进程的需求总和小于m+n。为什么这种情况不会发生死锁。证明之。解：假定系统是死锁的，这时M个资源都已分配给进程。由进程资源图可知，系统死锁时，进程和资源节点组成的有向图形成环路。因此，有M+N条边。由题意可知，N个进程最大资源需求量M+N,也就是说，进程与资源组成的有向图的边小于M+N，不可能构成环路，因此不会产生死锁。 （1）当前系统是安全的。这是因为： 剩余资源向量：1502 剩余请求矩阵为： 已分配矩阵： 0 0 0 0 0 0 1 2 0 7 5 0 1 0 0 0 1 0 0 2 1 3 5 4 0 0 2 0 0 6 3 2 0 6 4 2 0 0 1 4 判断系统是否安全，只要检查系统剩余向量能否对各进程的剩余请求向量中能否找到一个进程完成序列，当按照这个序列为各进程分配资源时，各进程都能成功完成，若能找到，则系统是安全的，否则，为不安全。先找到p0, 因为p0已满足最大资源请求，它可以完成，释放其占有的资源，使系统剩余资源向量为：1514之后，系统剩余资源向量（1514），可满足进程p2, 使p2 可以完成，释放其占有的资源，使系统剩余资源向量为： 2868 之后无论选哪一个进程都可成功完成,故找到的进程序列可为：p0,p2,p4,p3,p1; 或p2, p0,p3,p1,p4 等，故系统是安全的。（2）当p4提出（0302）请求时，因系统剩余可用向量为1502，同样应该按照要求，顺序检查，看能否找到一个进程完成序列。首先进行假分配，1502-0302=1200。由于p0不再申请资源，它最终释放资源，使系统变为1212。之后满足P2，。，故系统是安全的。1。下列几种对进程的描述，（ A ）最不符合操作系统对进程的理解。A。进程是在多程序并行环境中的完整程序。 B.进程可以由程序、数据和进程控制块描述。C.线程（thread）是一种特殊的进程。 D。进程是程序在一个数据集合上的运行过程，它是系统进行资源分配和调度的独立单位。3_1并发执行的进程在系统中通常表现为几种关系？各在什么情况下发生的？答：表现为互斥关系，同步关系和前序关系。互斥关系是进程之间共享资源的情况下发生的；同步关系：一个用户作业涉及到一组进程，这些进程相互协作共同完成一项任务，情况下发生的。前序关系：由于进程之间存在互斥和同步关系，才使得并发进程具有了前序关系。这些关系决定了各个进程创建和终止的时间。3_2什么叫临界资源？什么叫临界区？对于临界区使用应符合哪些规则？l 临界资源：一次仅允许一个进程使用的资源。 l 临界区(critical section)：就是并发执行的进程访问临界资源的那个必须互斥执行的程序段。l 任何时刻最多只有一个进程位于临界区。有空让进l 当已有进程处于其临界区时，后到达的进程只能在外等待。无空等待l 不应该使要进入临界区的进程无限期地等待在临界区之外。有限等待l 不能进入临界区的进程，应先释放处理机，转换到阻塞状态。让权等待3_3若信号量S表示某类资源，则对S执行P、V操作的直观含义是什么？Answer :P操作消耗某种资源；V释放某种资源3_4在用P、V操作实现进程通讯时应根据什么原则对信号量赋初值？资源的数量3_5程序段S1,S2,S3,和S4之间存在着如3.14所示的前序关系，试说明那些程序可以并发执行？3_7 系统有n+1个进程，其中有n个发送进程和一个接受进程，如图2。15所示。A1,A2,An通过一个缓冲区分别不断的向B进程发消息，B不断的从缓冲区取走消息，而且必须取走发来的每一个消息。刚开始时，缓冲区为空。试用P,V操作正确实现进程之间的同步。答案：系统中有n+1个进程。其中A1、A2、An分别通过缓冲区向进程B发送消息。相互之间的制约关系为：发送进程A1、A2、An要互斥地向BUF中送消息，当接收进程B还未将消息接收完之前，任何一个发送不能再送。同样，B不能重复接收同一个消息。 为此，应设置两个信号量s1和s2。设系统只有容纳一个消息的缓冲区，用信号量s1表示，其初值为1，它用来制约发送进程。信号量s2用来制约接收进程，其初值为0。3-7有一个容量为100的缓冲区，有多个并发进程通过缓冲区进行通讯。为正确的管理缓冲区，系统设置了两个读/写指针，分别为In和OUT,IN和OUT的值如何反映缓冲区为空还是满？设IN为写指针，OUT为读指针buffers系统初始化时，使IN=OUT，说明缓冲区为空。随着进程的不断向缓冲区送和取，IN和OUT进行动态修改：IN=(IN+1)MOD 100;OUT=(OUT+1)MOD 100;IF (IN=(IN+1)MOD 100)=OUT THEN 缓冲区为满。IF(OUT=(OUT+1)MOD 100=IN) THEN缓冲区为空。3_13. 有6个磁带机和n个进程。每个进程的最大申请为2，问n最大取什么值时，系统不会死锁？答：为了使系统不发生死锁，应该满足： n=6-1=5 3_14. 假定系统有n个进程，共享m个单位资源。规定进程对资源的申请和释放每次只申请或释放一个资源。每个进程最大需求不超过m个所有进程的需求资源总和小于m+n。为什么这种情况不会发生死锁。证明之。解：假定系统是死锁的，这时M个资源都已分配给进程。由进程资源图可知，系统死锁时，进程和资源节点组成的有向图形成环路。因此，有M+N条边。由题意可知，N个进程最大资源需求量M+N,也就是说，进程与资源组成的有向图的边小于M+N，不可能构成环路，因此不会产生死锁。 l 解：设有信号量, S2, ,S26,S3,S36,S38,S78;l 并且初值均为0；l 进程M1: M1,V(S2), V(S3),V( S4)l 进程M2: P(S2), M2,V(S26)l 进程M3: P(S3),M3,V(S36), V(S38)l 进程M4: P(S4),M4, V(S47)l 进程M5：M5, V(S57)l 进程M6: P(S26), P(S36),M6l 进程M7: P(S47), P(S57), M7,V(S78)l 进程M8: P(S38), P(S78),M81。下列几种对进程的描述，（ A ）最不符合操作系统对进程的理解。A.进程是在多程序并行环境中的完整程序。 B.进程可以由程序、数据和进程控制块描述。C.线程（thread）是一种特殊的进程。 D进程是程序在一个数据集合上的运行过程，它是系统进行资源分配和调度的独立单位。2 某进程被唤醒后立即投入运行，我们就说这个系统采用的是剥夺式调度方式，对吗？答：不对，当进程被唤醒前，如果CPU处于空闲状态时，某进程被唤醒后系统会使他立即投入运行，但这不是剥夺式调度方式。仅当它被唤醒后，立即抢占当前正在运行的进程的CPU时，才说系统采用剥夺式调度方式。3。进程之间存在哪几种制约关系？各是什么原因引起的？下列活动各属于哪种制约关系？A。若干学生去图书馆借书 B。两个队进行篮球比赛 C。流水线生产的各道工序 D。商品生产和社会消费答：进程之间存在的制约关系为：同步与互斥。同步是由于并发进程之间需要协调完成同一个任务时引起的一种关系，为一个进程等待令个进程向他直接发送消息或数据时的一种制约关系。互斥是由于并行进程之间竞争系统的临界资源引起的，为一个进程等待另一个进程已经占有的必须互斥使用的资源时发生的一种制约关系。A，B是互斥关系C，D是同步关系（4）有多个并发进程的进程资源分配图出现_环路_时一定存在死锁。（5）进程资源轨迹图使我们可以更容易理解系统是否处于_安全状态_的概念。 4_15 有如下图所示的页表中的虚地址与物理地址之间的关系，即该进程分得6个内存块。页大小为4096B。给出对应下面虚地址的物理地址： (1)20； (2)5100； (3) 8300； (4) 47000 04k (0) 主存空间 4k8k (1) 8k12k (2) 12k16k(3) 16k20k(4) 20k24k(5) 24k28k(6) 28k32k(7) 32k36k(8) 36k40k(9) 40k44k(10) 44k48k(11) 48k52k(12) 52k56k(13) 56k60k(14) 60k64k(15) 解：（1） 虚地址 20变为页号0 和页内偏移20 由页号查页表得0页对应内存块号为2 ，可计算得 物理地址=块号*页的大小+页内偏移=2*4096+20=8212 （2）虚地址 5100变为页号1 和页内偏移1004（5100/4096） 由页号查页表得1页对应内存块号为1 ，可计算得 物理地址=块号*页的大小+页内偏移=1*4096+1004=5100 （3）虚地址 8300变为页号2 和页内偏移108 由页号查页表得2页对应内存块号为6 ，可计算得 物理地址=块号*页的大小+页内偏移=6*4096+108=24684 （4）虚地址 47000变为页号11 和页内偏移1944 由页号查页表得11页对应内存块号为7 ，可计算得 物理地址=块号*页的大小+页内偏移=7*4096+1944=30616 17.(不讲)一台计算机。若采用老化算法，采用8位计数器，请给出最后一个周期的四个计数器的值。解：老化算法要求为每一页设置一个计数器，并初始化为零。每当时钟中断时，操作系统扫描贮存中所有的页，并将每一页引用位R的值加入到相应计数器中。每加一次，计数器的值右移一位，R位总是加到计数器的最高位上。具有4个页面的老化算法工作过程如图所示：第一个时钟周期时，第03页的引用位R依次为0111；第二个时钟周期为1011，1010，1101，0010，1010，1100，0001.4_18.一台计算机含有65536B字节的存储空间这个存储空间被分成许多长度为4096B的页面。有一个程序，其代码段为32768B，数据段为16386B，栈段为15870.问该机器的主贮存空间适合这个进程吗？如果每页改为512B，适合吗？当存储空间每页为4096字节时，整个存储空间可分为：65536/4096=16页，各段分配：程序代码段占： 32768/4096=8页；数据段： 16386/4096=5页；堆栈段： 15870/4096=4页；共8+5+4 =17页，故该机主存不适合运行该作业。当存储空间每页为512B时，存储器可分为128页：其中：代码段占：32768/512=64页数据段占：16386/512=32页堆栈段占：15780/512=31页共用： 64+32+32=127则该计算机可以运行该做业。 4_20有一个虚存系统，按行存储矩阵元素，一个进程要为矩阵进行清零操作系统为该进程分配物理主存3页，系统用其中一页存储程序，且已经调入，其他两页空闲。按需调入矩阵数据。若进程按下列两种方式编程： Var A:arry1.100, 1.100of integer; 程序A: for i:=1 to 100 do for j:=1 to 100 do AI,j:=0; 程序B: for j:=1 to 100 do for i:=1 to 100 do AI,j:=0; (1)若每页存放200个整数，问采用A程序和B程序方式时，个执行过程分别会发生多少次缺页？ （2）若每页只能存放100个整数时，会是什么情况？ 答：若每页存放200个整数，即每两行产生一次中断，程序A会发生50次缺页中断。程序B运行时，每页存放两列元素，内层循环每两次产生一次中断，共50次。外循环类似产生50次中断，共产生2500次中断。 若每页只能放100个整数，A程序产生100次中断：B程序产生10000次中断。3 什么是页表，页表的作用是什么？答：页表列出了作业的逻辑地址与其在主存中的物理地址间的对应关系。一个页表中包含若干个表目，表目的自然序号对应于用户程序中的页号，表目中的块号是该页对应的物理块号。页表的每一个表目除了包含指向页框的指针外，还包括一个存取控制字段。 4为实现分页管理，需要那些硬件支持？答：在系统中一般只是设置一个页表寄存器（PTR Page Table Register） （或称控制寄存器）其中存放页表在内存中的开始地址和页表的长度。 5在段页式管理方式中，逻辑地址有哪几部分？答：由段号，段内页号，和页内地址三部分组成。 6. 用数学方法分析只考虑页表和碎片时，每一页的最佳尺寸为多少？答：用数学方法分析页面大小的影响：假设进程大小的平均尺寸为S字节，每页大小为p字节，每个页表项占e个字节，每个进程所需页数近似s/p,则页表空间为es/p,进程由于内部碎片浪费的存储空间为平p/2.因此碎片和页表引起的系统总开销为 es/p+p/2第一项是页表开销，页面越小，开销越大，第二项是碎片开销，页面越大，开销也越大。对上面的式子优化，对p求导。得方程： -se/p2+1/2=0解方程得因此在只考虑页表和碎片是页面的最佳尺寸为： 根号下2se 7. 填空（1）在页式存储管理系统中，必须提供硬件_高速缓冲寄存器_，以保正寻址速度。（2）把作业装入主存时随时进行地址变幻的方式称为_静态从新定位 _，而在作业执行期间，当访问到指令或数据时才进行地址变换的方式称为_动态从新定位_. （3）设有8页的逻辑空间，每页有1024字节，那么逻辑地址的有效位是_ 13 _位。（4）程序经编译或汇编后形成目标程序，其中的指令顺序是以0作为参考地址进行编址的，这些地址称为相对地址或逻辑地址_。（5）在存储器的可变分区管理中，作业的地址转换采用的是_动态_重新定位方式。(6)虚拟存储器管理主要有_页式虚存管理_和_段式虚存管理 两种。 (7)在页式虚存管理页表中有效为为_ 1 _表示该页在主存贮器中。(8)当操作系统提供给用户程序的有效寻址范围与主存大小无关时，称该机器提供了_虚存管理_管理技术 14考虑一个可变分区系统，内存有如下顺序排列的空闲块：10K，40K，20K，18K，7K，9K，12K和15K，有如下的请求序列：12K，10K，9K。如果采用首次适应法，最佳适应法，和最坏适应法。将分配到那些分区内？答：若采用首次适应法： 12K的请求，将分配40K的空闲块， 40K变为剩余的（40-12）K=28空闲队列变为：10K，28K，20K，18K，7K，9K，12K和15K；10K的请求，将分配10K的空闲块，空闲队列变为：28K，20K，18K，7K，9K，12K和15K；9K的请求，将分配28K的空闲块，（28-9）=18K，空闲队列变为：18k, 20K，18K，7K，9K，12K和15K；若采用最佳适应法：12K的请求，将分配12K的空闲块，空闲队列变为：10K，40K，20K，18K，7K，9K和15K；10K的请求，将分配10K的空闲块，空闲队列变为：40K，20K，18K，7K，9K和15K；9K的请求，将分配9K的空闲块，空闲队列变为： 40K，20K，18K，7K和15K；若采用最坏适应法：12K的请求，将分配40K的空闲块，40-12=28k,空闲队列变为：10K，28K，20K，18K，7K，9K, 12k和15K；10K的请求，将分配28K的空闲块，28-10=18k,空闲队列变为： 10k,18k, 20K，18K，7K，9K，12K和15K；9K的请求，将分配20K的空闲块，20-9=11k,空闲队列变为：10K，18K，11K， 18K，7K，9k, 12K和15K 5_1什么是文件？答：从用户角度看，文件是存储在外部存储器的具有符号名的相关信息的集合。5_3.文件在文件存储器上有几种组织形式？对于不同的组织形式，文件系统是如何管理的？答：有连续存储文件，链接文件，和索引文件。对于连续文件采用目录表管理；对于链式文件采用盘文件映射表或称文件分配表；对于索引文件建立出目录之外还为每个文件建立一个索引表。 5_4.文件目录的作用是什么？文件目录通常包含哪些内容？答：文件目录是指一张记录所有文件的名字及其存放物理地址的映照表。它建立了逻辑文件与物理文件的映射关系。每个文件占用表中的一项。 每个目录项（又叫文件控制块FCB），包括文件的说明信息和管理控制信息。它是文件存在的唯一标志 5-9. 文件存贮空间管理可采用成组自由块链表或位示图。若一磁盘有B个盘块，其中有F个自由块。若盘空间用D位表示。试给出使用