数据库作业第二章第三章.doc

第二章一、思考题1. 什么是PSW，它有何作用？psw:操作系统将程序运行时的一组动态信息会聚在一起，称为程序的状态字 作用：实现程序状态的保护和恢复3.为什么要把机器指令分成特权指令和非特权指令？应用程序在执行有关资源管理的机制指令时易于导致系统混乱，造成系统或用户信息被破坏，因此在多道程序设计环境中，从资源管理和控制程序执行的角度出发，必须把指令系统中的指令分成这两类。4.试分别从中断事件的性质、来源和实现角度对其进行分类从中断事件的性质和激活的手段来说，可以分成两类： （1）强迫性中断事件强迫性中断事件不是正在运行的程序所期待的，而是由于某种事故或外部请求信息所引起的，分为：机器故障中断事件。程序性中断事件。外部中断事件。输入输出中断事件。（2）自愿性中断事件自愿性中断事件是正在运行的程序所期待的事件。按事件来源和实现手段分类：（1） 硬中断；硬中断分为外中断（中断、异步中断）和内中断（异常、同步中断）；（2） 软中断；软中断分为信号和软件中断。9.什么是系统调用？试述API、库函数及系统调用间的关系。叙述系统调用执行流程。由操作系统实现的所有系统调用所构成的集合即程序接口或应用编程接口(Application Programming Interface，API)。系统调用是一种API，是应用程序同系统之间的接口。库函数是语言本身的一部分，可以调用多个系统调用；系统调用（函数）是内核提供给应用程序的接口，属于系统的一部分，可以认为是某种内核的库函数；操作系统API是有系统调用（函数）的集合（也就是将许多的系统调用封装在了一起）。一是编写系统调用服务例程；二是设计系统调用入口地址表，每个入口地址都指向一个系统调用的服务例程，有的还包括系统调用自带的参数个数；三是陷阱处理机制，需要开辟现场保护区，以保存发生系统调用时应用程序的处理器现场。应用程序执行系统调用，产生中断指向内核态，进入陷阱处理程序，它将按功能查询入口地址表，并转至对应服务例程执行，完成后退出中断，返回应用程序断点继续运行。14.简述Linux的快中断和慢中断快中断：快中断处理仅要保存被常规C函数修改的寄存器；中断处理时会屏蔽所有其他中断；中断处理完毕后，通常恢复现场返回被中断的进程继续执行(是非抢先式调度)。慢中断：处理慢中断前需保存所有寄存器的内容，中断处理时，不屏蔽其他中断信号，慢中断处理完毕后，通常不立即返回被中断的进程，而是进入调度程序重新调度，调度结果未必是被中断的进程运行(是抢先式调度)。17.讨论Linux系统的tasklet、work queue和softirq任务延迟处理进制。（1）tasklet：能更好支持SMP，它基于软中断来实现，但比软中断接口简单，锁保护要求低；softirq保留给执行频率及时间要求特高的下半部分使用(如网络和SCSI)，多数场合下可使用tasklet。使用tasklet的步骤：声明 、编程、调度 。 BH全局串行处理，不适应SMP环境，而不同tasklet可同时运行于不同CPU上，当然，系统保证相同tasklet不会同时在不同CPU上运行，在这种情形下，tasklet就不需要是可重入的。在新版Linux中，tasklet是建议的异步任务延迟执行机制。（2）work queue：Linux 2.5内核引入-工作队列，它把一个任务延迟，并交给内核线程去完成，且该任务总是在进程上下文中执行，通过工作队列执行的代码能占尽进程上下文的优势，最重要的是工作队列允许重新调度及阻塞。默认的工作者线程:event/n如果延迟执行的任务需要阻塞，需要获取信号量或需要获得大量主存时，那么，可选择工作队列，否则可使用tasklet或softirq。(3) Sorfirq：（软中断）是一种软中断机制，亦即是一种信号机制，中断处理程序在其返回前标记下半部分，让其稍后执行；它又是一个框架，纳入了tasklet及为网络操作专门设计的软中断。18.什么是进程？计算机系统中为什么要引入进程？（1）进程定义：进程是可并发执行的程序在某个数据集合上的一次计算活动，也是操作系统进行资源分配和保护的基本单位（2）刻画系统的动态性，发挥系统的并发性，提高资源利用率。程序是并发执行的，即不是连续而是走走停停的。程序的并发执行引起资源共享和竞争问题，执行的程序不再处在封闭环境中。“程序”自身只是计算任务的指令和数据的描述，是静态概念无法刻画程序的并发特性，系统需要寻找一个能描述程序动态执行过程的概念，这就是进程。它能解决系统的“共享性”，正确描述程序的执行状态。程序与程序的执行不再一一对应19.进程有哪些主要属性？试解释之共享性：同一程序同时运行于不同数据集合上时构成不同进程，即多个不同进程可执行相同的程序，所以进程和程序不是一一对应的。动态性：进程是程序在数据集合上的一次执行过程，是动态概念，同时它有生命周期，由创建而产生、由调度而执行、由事件而等待、由撤销而消亡；而程序是一组有序指令序列，是静态概念，所以程序作为系统中的一种资源是永远存在的独立性：每个进程是操作系统中的一个独立实体，有自己的虚存空间，程序计数器和内部状态；制约性：进程因共享进程资源或协同工作产生相互制约关系，造成进程执行速度的不可预测，必须对进程的执行次序或相对执行速度加以协调；并发性：多个进程的执行在时间上可以重叠，在单处理器系统中可并发执行；在多处理器环境中可并发执行。因此，并发的执行是可被打断的，或者说，进程执行完一条指令后在执行下一条指令前可能被迫让出处理器，由其它若干个进程执行若干条指令后才能再次获得处理器执行。20.进程最基本的状态有哪些？哪些事件可能引起不同状态间的转换？运行态、就绪态、等待态（1）运行态-等待态：运行进程等待使用某种资源或者某事件发生（2）等待态-就绪态：所需资源得到满足或某事件已经完成（3）运行态-就绪态：运行时间片到时或出现更高优先级的进程，当前进程被迫让出处理器。（4）就绪态-运行态：当CPU空闲时，调度程序选中一个就绪进行执行21.五态模型的进程中，新建态和终止态的主要作用是什么？新建态：对应于进程被创建时的状态，进程尚未进入就绪队列，对于进程管理非常有用。终止态：进程完成任务到达正常结束点或者因错误而终止，或被操作系统及有终止权的进程时所处的状态。进入终止态程序不再执行，等待操作系统进行善后处理。24.什么是进程的挂起状态？列出挂起进程的主要特征。（1）为了让某些进程暂时不参与低级调度，释放它占有的资源，将其置于磁盘对换区中，以平滑系统负荷的目的而需引入挂起态；（2）特征：该进程不能立即被执行。挂起进程可能会等待事件，但所等待事件是独立于挂起条件的，事件结束并不能导致进程具备执行条件。进程进入挂起状态是由于操作系统、父进程或进程本身阻止它的运行。结束进程挂起状态的命令只能通过操作系统或父进程发出25.试述组成进程的基本要素，并说明其作用。控制块：存储进程的标志信息，现场信息和控制信息；程序块：规定进程的一次运行所应完成的功能；核心块：用来保护中断/异常现场，保存函数调用的参数和返回地址；数据块：存放各种私有数据26.何谓进程控制块（PCB）？它包含哪些基本信息？（1）进程控制块P C B ，是操作系统用于记录和刻划进程状态及有关信息的数据结构。也是操作系统掌握进程的唯一资料结构，它包括进程执行时的情况，以及进程让出处理器后所处的状态、断点等信息。 （2）进程控制块包含三类信息 标识信息 现场信息 控制信息28.请列举组织进程队列的各种方法通用队列组织方式： 线性方式 链接方式 索引方式30.什么是进程上下文？简述其主要内容操作系统中把进程物理实体和支持进程运行的环境合称为进程上下文。当系统调度新进程占有处理器时，新老进程随之发生上下文切换。进程的运行被认为是上下文中执行。 进程上下文组成用户级上下文系统级上下文寄存器上下文31.什么是进程切换？试述进程切换的主要步骤（1）进程切换是让处于运行态的进程中断运行，让出处理器，这时要做一次进程上下文切换、即保存老进程状态而装入被保护了的新进程的状态，以便新进程运行（2）保存被中断进程的处理器现场信息修改被中断进程的进程控制块有关信息，如进程状态等把被中断进程的PCB加入有关队列选择下一个占有处理器运行的进程修改被选中进程的PCB的有关信息根据被选中进程设置操作系统用到的地址转换和存储保护信息根据被选中进程恢复处理器现场32.什么是模式切换？它与进程切换之间有何区别？模式切换即CPU模式切换，是从用户态到核心态或者核心态到用户态的转换是CPU模式切换，此时仍然在同一个进程中运行。模式切换不同于进程切换，它不一定会引起进程状态的转换，也不一定会引起进程切换，在完成系统调度服务或中断处理之后，可通过逆向模式来恢复被中断进程的运行。35.在操作系统引入进程概念后，为什么还有引入线程的概念？操作系统中再引入线程，则是为了减少程序并发执行时所付出的时空开销，使得并发粒度更细、并发性更好。38.试从调度、并发性、拥有资源和系统开销等四个方面对传统进程和多线程进程进行比较。40.试对下列系统任务进行比较：（1）创建一个线程和创建一个进程（2）两个进程间通信与同一进程中的两个线程间通信 （3）同一进程中的两个线程的上下文切换和不同进程中两个线程的上下文切换。43.列举线程的组织方式和应用场合。答：线程组织方式：（1）调度员/工作者方式（2）组模式（3）流水线模式应用场合：（1）前台和后台工作（2）C/S应用模式（3）异步处理（4）加快执行速度（5）设计用户接口45.试分析Linux系统的进程和线程。进程描述符task_struct中包含：进程标识、链接信息、调度信息、文件信息、虚存空间信息、信号处理信息等。Linux中认为线程就是共享地址空间及其他资源的进程，故并没有单独为线程定义数据结构，有一套在用户模式下运行的线程库-pthread，但每个线程都拥有惟一隶属于自己的task_struct48.处理器调度分为哪几种类型？简述各种调度的主要任务。答：（1）高级调度：在多道处理操作系统中，从输入系统的一批作业中按照预定的调度策略挑选若干个作业进入主存，为其分配所需资源，并创建作业的相应用户进程后便完成启动阶段的高级调度任务；（2）中级调度：根据主存资源决定主存中所能容纳的进程数目，并根据进程的当前状态来决定辅助存储器和主存中的进程的对换；（3）低级调度：根据某种原则决定就绪队列中的哪个进程或内核级线程获得处理器，并将处理器让出给它使用。49.试述衡量一个处理器调度算法优劣的主要任务。根据调度机制 的三个逻辑功能程序模块组成来评判：（1）队列管理程序（2）上下文切换程序（3）分派程序52.解释：（1）作业周转时间；（2）作业带权周转时间；（3）相应时间；（4）吞吐率。答：（1）作业周转时间：批处理用户从系统提交作业开始，到作业完成为止的时间间隔；（2）作业带权周转时间：在操作系统中，带权周转时间反映作业（或进程）长短问题，带权周转时间越大，作业（或进程）越短；带权周转时间越小，作业（或进程）越长。（3）响应时间：从交互式进程提交一个请求至得到响应之间的时间间隔称为响应时间。（4）吞吐率：单位时间CPU处理作业的个数。53.试述作业、进程、线程和程序之间的关系。进程是操作系统结构的基础；是一个正在执行的程序；计算机中正在运行的程序实例；可以分配给处理器并由处理器执行的一个实体；由单一顺序的执行显示，一个当前状态和一组相关的系统资源所描述的活动单元。 线程（thread, 台湾称 执行绪）是进程中某个单一顺序的控制流。也被称为轻量进程（lightweight processes）。计算机科学术语，指运行中的程序的调度单位。作业：用户在一次运算过程中，或一次事务处理中要求计算机所做的全部工作的总和。进程是在自身的虚拟地址空间正在运行的一个程序 程序运行产生进程 程序是一组静态的指令集，不占用系统运行资源 进程是随时都可能发生变化的，动态的。占用系统运行资源的程序 一个程序可以产生多个进程 作业嘛，是一个或多个正在执行的相关进程。一般来讲当进程与作业控制相关联时才被称为作业55.在时间片轮转低度调级算法中，根据哪些因素确定时间片的长短？答：进程数目、切换开销、系统效率及响应时间等多方面因素。57.为什么多级反馈队列算法能较好地满足各种用户的需求？答：高级调度的主要任务是根据某种算法，把外存上处于后备队列中的那些作业调入内存。低级调度是保存处理机的现场信息，按某种算法先取进程，再把处理器分配给进程。引入中级调度的主要目的是为了提高内存利用率和系统吞吐量。使那些暂时不能运行的进程不再占用内存资源，将它们调至外存等待，把进程状态改为就绪驻外存状态或挂起状态。58.分析静态优先数和动态优先数低级调度算法各自的优缺点。答：静态优先级在进程或线程创建时确定，且生命周期中不再改变，可按照外部指定和内部指定方法计算静态优先级。静态优先级算法的实现简单，但会产生饥饿现象，使某些低优先级进程或线程无限期对的被推迟进行。动态优先级使各进程或线程优先级随时间而改变，克服了静态优先级的饥饿问题，等待时间足够长的进程或线程会因其优先级不断提高而被调度运行。62.在多级反馈队列中，对不同的队列分配大小不同的时间片值，其意义何在?应用题1.下列指令中，哪些只能在内核态运行？（1）读时钟日期 （2）访管指令 （3）设时钟日期 （4）加载PSW（5）置特殊寄存器 （6）改变存储器映像图 （7）启动I/O指令4.在按照动态优先数调度进程的系统中，每个进程的优先数需定时重新计算。在处理器不断在进程之间交替的情况下，重新计算进程优先数的时间从何而来？许多操作系统重新计算进程的优先数在时钟中断处理例程中进行，由于中断是随机碰到哪个进程，就插入哪个进程中运行处理程序，并把处理时间记在这个进程的账上。7. 8.10. 按照最短作业优先的算法可以使平均响应时间最短。X取值不定，按照以下情况讨论： 1） x3 次序为：x，3，5，6，9 2） 3x5 次序为：3，x，5，6，9 3） 5x6 次序为：3，5，x，6，9 4） 6x9 次序为：3，5，6，x，9 5） 90表示还有共享资源可供使用。S=0表示共享资源正被进程使用但没有进程等待使用资源。Sn时，如果m/n不整除，每个进程最多可以请求”商+1”个这类资源，否则为”商”个资源，使系统一定不会发生死锁。19：N个进程共享M个资源，每个进程一次只能申请/释放一个资源，每个进程最多需要M个资源，所有进程总共的资源需求少于M+N个，证明该系统此时不会产生死锁。答：设max（i）表示第i个进程的最大资源需求量，need(i)表示第i个进程还需要的资源量，alloc(i)表示第i个进程已分配的资源量。由题中所给条件可知：max(1)+max(n)=(need(1)+need(n)+(alloc(1)+alloc(n)m+n如果在这个系统中发生了死锁，那么一方面m个资源应该全部分配出去，alloc(1)+alloc(n)=m,另一方面所有进程将陷入无限等待状态。可以推出need(1)+need(n)n上式表示死锁发生后，n个进程还需要的资源量之和小于n，这意味着此刻至少存在一个进程i,need(i)=0,即它已获得了所需要的全部资源。既然该进程已获得了它所需要的全部资源，那么它就能执行完成并释放它占有的资源，这与前面的假设矛盾，从而证明在这个系统中不可能发生死锁。21：Jurassic公园有一个恐龙博物馆和一个花园，有m个旅客和n辆车，每辆车仅能乘一个旅客。旅客在博物馆逛了一会，然后，排队乘坐旅行车，当一辆车可用时，它载入一个旅客，再绕花园行驶任意长的时间。若n辆车都已被旅客乘坐游玩，则想坐车的旅客需要等待。如果一辆车已经空闲，但没有游玩的旅客了，那么，车辆要等待。试用信号量和P、V操作同步m个旅客和n辆车子。答：23：设当前的系统状态如下，系统此时Available=(1，1，2)：Claim Allocation进程, R1 R2 R3 R1 R2 R3P1 3 2 2 1 0 0P2 6 1 3 5 1 1P3 3 1 4 2 1 1P4 4 2 2 0 0 2(1) 计算各个进程还需要的资源数Cki-Aki?(2) 系统是否处于安全状态，为什么?(3) P1发出请求向量request2(1，0，1)，系统能把资源分给它吗？(4) 若在P2申请资源后，若P1发出请求向量request1(1，0，1)，系统能把资源分给它吗？(5) 若在P1申请资源后，若P3发出请求向量request3(0，0，1)，系统能把资源分给它吗？答：(1)P1，P2，P3，P4的Cki-Aki分别为：(2，2，2)、(1，0，2)、(1，0，3)、(4，2，0)(2)系统处于安全状态，存在安全序：P2，P1，P3，P4(3)可以分配，存在安全序列：P2，P1，P3，P4。(4)不可以分配。(5)不可以分配。24：系统有A、B、C、D共4种资源，在某时刻进程P0、P1、P2、P3和P4对资源的占有和需求情况如表，试解答下列问题：Allocation Claim Available进程 A B C D A B C D A B C DP0 0 0 3 2 0 0 4 4 1 6 2 2P1 1 0 0 0 2 7 5 0P2 1 3 5 4 3 6 10 10P3 0 3 3 2 0 9 8 4P4 0 0 1 4 0 6 6 10(1)系统此时处于安全状态吗？(2) 若此时P1发出request1(1、2、2、2)，系统能分配资源给它吗？为什么？答：(1)系统处于安全状态，存在安全序列：P0，P3，P4，P1，P2。(2)不能分配，否则系统会处于不安全状态。25：把死锁检测算法用于下面的数据，并请问：Available=(1，0，2，0)1 1 0 03 0 1 10 1 1 2 Allocation= 0 1 0 0Need=3 1 1 1 1 0 0 01 1 0 10 0 1 0=2 1 1 0 0 0 0 0(1)此时系统此时处于安全状态吗？(2)若第二个进程提出资源请求request2(0，0，1，0)，系统能分配资源给它吗？(3)若第五个进程提出资源请求request5(0，0，1，0)，系统能分配资源给它吗？答：(1)此时可以找出进程安全序列：P4，P1，P5，P2，P3。故系统处于安全状态。(2)可以分配，存在安全序列：P4，P1，P5，P2，P3。(3)不可分配，系统进入不安全状态。26:考虑一个共有150个存储单元的系统，如下分配给三个进程，P1最大需求70,己占有25；P2最大需求60,己占有40；P3最大需求60,己占有45。使用银行家算法，以确定下面的任何一个请求是否安全。(1)P4进程到达，P4最大需求60,最初请求25个。(2)P4进程到达，P4最大需求60,最初请求35。如果安全，找出安全序列；如果不安全，给出结果分配情况。答：29：进程A1、A2、An1通过m个缓冲区向进程B1、B2、Bn2不断地发送消息。发送和接收工作符合以下规则：(1) 每个发送进程每次发送一个消息，写进一个缓冲区，缓冲区大小与消息长度相等；(2) 对每个消息，B1、B2、Bn2都需接收一次，并读入各自的数据区内；(3) 当M个缓冲区都满时，则发送进程等待，当没有消息可读时，接收进程等待。试用信号量和PV操作编制正确控制消息的发送和接收的程序。答：30：某系统有R1设备3台，R2设备4台，它们被P1、P2、P3和P4进程共享，且已知这4个进程均按以下顺序使用设备：申请R1申请R2申请R1释放R1释放R2释放R1(1) 系统运行中可能产生死锁吗？为什么？(2) 若可能的话，请举出一种情况，并画出表示该死锁状态的进程资源图。答：39：一组生产者进程和一组消费者进程共享九个缓冲区，每个缓冲区可以存放一个整数。生产者进程每次一次性向3个缓冲区写入整数，消费者进程每次从缓冲区取出一个整数。请用：(1)信号量和P、V操作；(2)管程，写出能够正确执行的程序。答：41：下述流程是解决两进程互斥访问临界区问题的一种方法。试从“互斥”(mutual exclusion)、“空闲让进”(progress)、“有限等待”(bounded waiting)等三方面讨论它的正确性。如果它是正确的，则证明之；如果它不正确，请说明理由。program attemp;var c1,c2:integer;procedure p1; (/* 对第一个进程p1 */)beginrepeatRemain Section 1;repeatc1:=1-c2until c20;Critical Section; (/* 临界区 */)c1:=1until falseend;procedure p2; (/* 对另一个进程p2 */)beginrepeatRemain Section 2;repeatc2:=1-c1until c10;Critical Section; (/* 临界区 */)c2:=1until falseend;begin (/* 主程序 */)c1:=1;c2:=1;cobeginp1;p2 (/* 两进程p1, p2开始执行 */)coendend.答：52：在一个分页存储管理系统中，用 freeindex数组记录每个页框状态，共有 n 个页框(index=0，n-1)。当freeindex=true时，表示第index个页框空闲，freeindex=false时，表示第index个页框。试设计一个管程，它有两个过程acquire和release分别负责分配和回收一个页框。59：试利用一般信号量机制解决读者-写者问题。答：设置互斥信号量wmutex 表示写者间、读者和写者间互斥 用readcount变量来记录读者数：Var rmutex,wmut