《操作系统原理》习题及参考答案.pdf

操作系统原理习题及参考答案操作系统的定义。操作系统的五大基本功能。网络操作系统相对单机操作系统还应具备什么功能？解：操作系统是计算机系统的一种系统软件，由它统一管理计算机系统中的软硬件资源，合理地组织工作流程，以便有效地为用户提供一个功能强大、使用方便的工作环境，从而在计算机与用户之间起到接口的作用。操作系统的五大基本功能是：处理机管理、存储器管理、设备管理、文件系统管理和用户接口。网络操作系统还应具备的功能：网络通信、资源共享、网络服务、网络用户接口。设有三个进程A、B、C，进程A需8毫秒处理时间，B需2毫秒处理时间，C需24毫秒处理时间，分别考虑在就绪队列中的顺序为ABC时及CBA时，用先来先服务算法进行调度时的平均等待时间。解：当顺序为ABC时：Wa=0Wb=8Wc=10Mw=(0+8+10)3=6ms当顺序为CBA时：Wc=0Wb=24Wc=26Mw=(0+24+26)3=17ms设在内存中有三道程序：A、B、C，并按照A、B、C的优先次序运行，其内部计算和IO操作时间由下图给出。程序A程序B程序C要求：（1）试画出按多道程序运行的时间关系图（调度程序的执行时间忽略不计）。完成这三道程序共花多少时间？比单道运行节省多少时间？（2）若处理机调度程序每次进行程序状态转换的时间为1ms，试画出在处理机调度程序管理下各程序状态转换的时间关系图。完成这三道程序共花多少时间？解：(1)在调度程序执行时间忽略不计的情况下，这三道程序的执行时间如下图所示：IO40ms计算10ms计算30msIO30ms计算10ms计算60ms计算20msIO40ms计算20ms1总的执行时间为180ms.如果单道执行这三个程序共需80+100+80=260ms.所以节约260180ms.(2)若处理机调度程序每次进行程序状态转换的时间为1ms，这三道程序的执行时间如下图所示：总共花费180+6=186ms.系统调用（陷入）处理过程。解：系统调用（陷入）处理过程和中断处理过程是一样的，只是中断源是执行了访管指令（MSDOS的INT或UNIX的trap）。CPU检查响应中断的条件是否满足。如果CPU响应中断，则CPU关中断，使其进入不可再次响应中断的状态。保存被中断的现场。分析中断原因，调用中断处理子程序。执行中断处理子程序。退出中断，恢复被中断进程的现场或调度新进程占据处理器。开中断，CPU继续执行。有5个中断源D1、D2、D3、D4和D5，它们的中断优先级从高到低依次是1-5级别。这些中断源的中断优先级、正常情况下的中断屏蔽码和改变后的中断屏蔽码如下表所示。每个中断源有5位中断屏蔽码，其中0表示该中断源开放，1表示该中断源被屏蔽。2正常的中断屏蔽码正常的中断屏蔽码改变后的中断屏蔽码改变后的中断屏蔽码中断源中断源中断优先级中断优先级D1D2D3D4D5D1D2D3D4D5D111111110000D220111111000D330011111100D440001111111D550000111101(1)当使用正常的中断屏蔽码时，处理器响应各中断源的中断请求的先后顺序是什么？实际上中断处理的先后次序是什么？(2)当使用改变后的中断屏蔽码时，处理器响应各中断源的中断请求的先后顺序是什么？实际上中断处理的先后次序是什么？(3)如果采用改变后的中断屏蔽码，D1、D2、D3、D4和D5同时请求中断时，画出处理器响应各中断源的中断请求和实际运行中断服务程序过程的示意图。解：(1)当使用正常的中断屏蔽码时，处理器响应各中断源的中断请求的先后顺序是D1、D2、D3、D4、D5。实际上中断处理的先后次序是D1、D2、D3、D4、D5。(2)当使用改变后的中断屏蔽码时，处理器响应各中断源的中断请求的先后顺序是D1、D2、D3、D4、D5。实际上中断处理的先后次序是D4、D5、D3、D2、D1。(3)如果采用改变后的中断屏蔽码，D1、D2、D3、D4和D5同时请求中断时，处理器响应各中断源的中断请求和实际运行中断服务程序过程如下图所示：进程有哪几种基本状态？作业有哪几种基本状态？画出作业进程基本状态关系图。解：进程有三种基本状态：就绪态、运行态、等待态。作业有四种基本状态：输入态（提交态）、后备态（收容态）、执行态、完成态。3系统调用fork()工作过程。（1）为子进程在proc结构表中分配一个空项；（2）为子进程赋一个唯一的PID（3）复制父进程上下文的逻辑副本。（4）增加与父进程相关联的有关文件系统的进程引用技术。（5）对父进程返回子进程的PID，对子进程返回为0.语法：pid=fork()一个fork()系统调用程序实例#include#include#includemain()pid_tvalprintf(PIDbeforefork():%d(int)getpid()val=fork()if(val!=0)printf(parentprocessPID:%dn(int)getpid()elseprintf(childprocessPID:%dn(int)getpid()执行结果：PIDbeforefork():2000parentprocessPID:2000childprocessPID:2001什么是进程？简述进程与程序、线程的区别和联系。解：进程是一个具有独立功能的程序对某个数据集在处理机上的执行过程和分配资源的基本单位。进程与程序的区别和联系是：1)进程是一个动态概念，程序是一个静态概念。2)进程具有并行特征，程序没有并行特征。43)进程是竞争计算机系统资源的基本单位。4)不同的进程可以包含同一程序，只要该程序所对应的数据集不同。进程和线程的区别和联系是：1)线程是进程的一个组成部分。2)进程的多线程都在进程的地址空间活动。3)资源是分给进程的，而不是线程的。4)调度的基本单位是线程。5)线程在执行过程中，需要同步。常用的进程调度算法和作业调度算法有哪些？哪些适用于作业调度？哪些适用于进程调度？解：常用的作业调度算法有：先来先服务算法（FCFS）、最短作业优先算法（SJF）、最高响应比优先算法（HRRN）、优先级调度算法、均衡调度算法等。常用的进程调度算法有：先来先服务算法（FCFS）、优先级调度算法、时间片轮转调度算法（RR）、分级调度算法、多级反馈轮转算法（MultiLevelFeedbackQueue）等。处理机调度的目的是什么？有哪几种类型？每种调度的主要任务是什么？解：处理机调度的目的是使处理机在满足系统要求的响应时间、吞吐量和处理机利用率的前提下及时地运行进程。调度有4种类型：长程调度：决定欲增加执行的进程池；中程调度：决定增加部分或全部位于内存中进程数；短程调度：决定哪个就绪进程被处理机执行；IO调度：决定哪个进程未完成的IO请求可被IO设备处理。对于下列三个作业，采用不可抢占的调度方式：先来先服务算法和短作业优先算法，当第一个作业进入系统后开始调度，填写下面的表格。先来先服务算法：作业号周转时间进入输入井时间需运行时间（小时）开始运行时间完成时间带权周转时间A8:006.4B8:243.2C9:001短作业优先算法：作业号周转时间进入输入井时间需运行时间（小时）开始运行时间完成时间带权周转时间A8:006.4B8:243.2C9:001解：先来先服务算法：作业号周转时间进入输入井时间需运行时间（小时）开始运行时间完成时间带权周转时间A8:00(8.0)6.48.014.46.41B8:24(8.4)3.214.417.69.22.9C9:00(9.0)117.618.69.69.6短作业优先算法：作业号周转时间进入输入井时间需运行时间（小时）开始运行时间完成时间带权周转时间A8:00(8.0)6.48.014.46.415B8:24(8.4)3.215.418.610.23.2C9:00(9.0)114.415.46.46.4什么是进程同步？解：进程同步是指并发进程之间存在一种直接制约关系，一个进程的执行依赖另一个进程的消息，当一个进程没有得到另一个进程的消息时应等待，直到消息到达才被唤醒。设有两个优先级相同的进程P1、P2如下。令信号量S1、S2的初值均为0，试问P1、P2并发执行结束后x=y=z=写出并发执行的细节。（10分）进程P1进程P2y:=1x:=0y:=y+2x:=x+2V(S1)P(S1)z:=2y+1x:=x+zP(S2)V(S2)y:=z+yz:=x+z解：假设P1先执行，P2后执行：xyzS1S2P1x:=0000P1x:=x+22000P1P(S1)2-10P2y:=121-10P2y:=y+2230-10P2V(S1)23000P2z:=2y+123700P2P(S2)2370-1P1x:=x+z9370-1P1V(S2)93700P1z:=x+z931600P2y:=z+y9191600所以x=9y=19z=16假设P2先执行，P1后执行：xyzS1S2P2y:=1100P2y:=y+2300P2V(S1)310P2z:=2y+13710P2P(S2)371-1P1x:=00371-1P1x:=x+22371-1P1P(S1)2370-1P1x:=x+z9370-1P1V(S2)93700P1z:=x+z931600P2y:=z+y9191600所以x=9y=19z=166利用PV操作，怎样才能保证进程Pi能按下面两图的次序正确执行，其中S表示开始，F表示结束。解：（1）设信号量S2:=0S3:=0S4:=0P1:P2:P3:P4:.P(S2)P(S3)P(S4).P(S4)V(S2).V(S3)V(S4)V(S4).（2）设信号量S3:=0S4:=0S5:=0S6:=0P1:P2:P3:P4:P5:P6:.P(S3)P(S4)P(S5)P(S6).P(S3).V(S3)V(S3)V(S4).V(S5)V(S6)设一个飞机航班售票系统有n个售票处，每个售票处通过终端访问系统的公共数据区。假定公共数据区中的一些单元Aj(j=123)分别存放某月某日某次航班的余票数。用P1P2Pn表示个售票处为旅客服务时的处理进程；R1R2R3Rn为各进程执行时所用的工作单元。用PV操作和信号量保证售票系统的正确并发执行。解：实现A、B进程间同步应设置2个信号量S1S2.信号量S1表示缓冲区是否为空；信号量S2表示缓冲区是否为满。S1的初值为1；S2的初值为0.同步算法Beginmutex:semaphoreAj:integermutex:=1S2:=0Cobegin7ProcessPi(i=123n)Begin按旅客定票要求找到AjP(mutex)R=AijifR=1thenR=R-1iiiAj=Ri输出一张票；V(mutex)else输出“票已售完”；V(mutex)EndCoendEnd.设有两个进程A、B，它们是一对相互合作的进程，共用一个缓冲区。进程A负责从输入设备读一个记录送入缓冲区；进程B负责取走缓冲区中的记录并进行加工处理。问：（1）用信号量机制实现A和B进程间同步应设置几个信号量？（2）信号量的初值是什么？（3）写出实现两进程共享缓冲区的同步算法。解：实现A、B进程间同步应设置2个信号量S1S2.信号量S1表示缓冲区是否为空；信号量S2表示缓冲区是否为满。S1的初值为1；S2的初值为0.同步算法BeginS1S2:semaphoreS1:=1S2:=0CobeginProcessPProcessPABBL2:P(S2)L1:输入设备读一记录；取走缓冲区中的记录；P(S1)V(S1)送入缓冲区；送入缓冲区；V(S2)GotoL2GotoL1CoendEnd.什么是死锁？列出死锁的四个必要条件。解：若系统中存在一组进程（两个或多个进程），它们中的每一个进程都占用了某种资源而又在等待该组中的别的进程所占用的资源，在获得自己所需要的对方资源之前决不释放自己所占用的资源，这种等待永远不能结束的状态称为死锁。死锁的四个必要条件是：1)互斥使用资源2)占有且等待资源3)非抢占式分配4)循环等待资源8某系统有ABCD四类资源供5个进程共享，进程对资源的要求和分配情况如表所示，现在系统剩余资源A类1个，B类5个，C类2个，D类0个。根据银行家算法判定：现在系统是否处于安全状态？为什么？已占资源数最大需求数进程ABCDABCDP100120012P210001756P313542356P406320652P500140656解：银行家此时拥有的资源为(ABCD)=(1520)P1距离最大需求为：(0012)-(0012)=(0000)P2距离最大需求为：(1756)-(1000)=(0756)P3距离最大需求为：(2356)-(1354)=(1002)P4距离最大需求为：(0652)-(0632)=(0020)P5距离最大需求为：(0656)-(0014)=(0642)根据银行家算法，如果按下面的顺序分配资源：(1520)-P1-(1520)+(0012)=(1532)-P3-(1532)+(1354)=(2886)-P2-(2886)+(1000)=(3886)-P4-(3886)+(0632)=(314118)-P5-(314118)+(0014)=(3141212).可以回收全部资源。所以现在系统处于安全状态。若系统中有同类资源37个，每个进程至多允许申请5个资源，问最多允许多少个进程并发执行而且确保必定不会发生死锁。解：9个。【更泛化的问题是：若系统中有同类资源m个，被n个进程共享（mn0），问每个进程至多允许申请多少个资源时必定不会发生死锁。思路：设每个进程申请资源的最大个数为x(11489017895152102175130总磁道数=566SSTF(最短寻道时间优先算法)14014815213010295908817517819总磁道数=166SCAN(扫描算法)140148152175178199130102959088总磁道数=170电梯算法140148152175178130102959088总磁道数=128旋转型存储设备上信息的优化分布能减少若干个输入输出服务的总时间。现有8个记录A，B，G，H，存放在某磁盘上的某个磁道上。假定这个磁道被划分为8块，每块存放一个记录，安排如下表所示。现要顺序处理这些记录，如果磁盘旋转速度为16ms1周，处理程序每读出一个记录后要用4ms进行处理。试问处理完8个记录的总时间是多少？为了缩短处理时间，应如何安排这些记录实现优化分布，并计算处理的总时间。12345678块号ABCDEFGH记录号解：(1)因为磁盘旋转一周的时间为16ms，所以读取一个记录的时间为16ms8=2ms处理一个记录的时间为4ms。设读写磁头指向A记录，由2ms+4ms=6ms可知读出并处理完A后，读写磁头已停在D记录的位置。要读B记录需要2ms6=12ms延迟时间。有7个记录都需要延迟时间。因此处理完8个记录的总时间是：8(2ms+4ms)+7(2ms6)=132ms或：6ms+7(2ms6+2ms+4ms)=132ms2ms6为等待时间；2ms为读取时间；4ms为处理时间。(2)若进行优化分布，则记录的安排如下表所示：12345678块号ADGBEHCF记录号当处理完A记录后，B记录停在磁头位置，无需延迟时间。因此处理完这8个记录的总时间是：8(2ms+4ms)=48ms假定某文件系统把文件存储到磁盘上时采用链接结构，磁盘分