操作系统作业题(1)参考答案.doc

操作系统作业题（1）参考答案一、判断题 （1） （2） （3） （4） （5） （6） （7） （8） （9） （10）二、 （1） 答：1955-1965年是第二代计算机系统时代，这时候的计算机硬件非常昂贵，人们想尽了一切办法来减少机时的浪费，其中最好的方式是批处理系统。因为这时计算机主要处理的问题是像解偏微分方程之类的科学计算。程序与用户之间的交互性不强，程序在运行过程中，基本上不需要用户干预，适合于批处理系统。而分时系统主要是为共享计算机系统的软硬件资源而设计的，用于程序系统与用户之间的交互性较强的场合。其次分时系统相对批处理系统来说较为耗时，因为进程之间的切换是需要花费一定时间的，不能充分发挥这个时期非常昂贵的硬件资源。因此在第二代计算机系统中没有广泛采用分时系统。（2）答：多道系统中，进程的运行是走走停停的，它在处理器上的交替运行，使它的运行状态不停地变化着，最基本的状态有三种：运行、就绪和阻塞。运行状态就是进程正在处理器上运行，就绪状态就是进程只要获得处理器就可以运行，阻塞状态就是进程正在等待某个件的发生，现代操作系统中，还有进程的挂起状态。状态之间的转换如下图所示：（3）答：若一个进程集合中的每一个进程都在等待只能由本集合中的另一个进程才能引发的事件，则把这种情况称之为死锁。如果一个进程正在等待一个不可能发生的事件，则称该进程处于死锁状态。系统发生死锁是指一个或多个进程处于死锁状态。死锁发生的条件：产生死锁的主要原因是供共享的系统资源不足，资源分配策略和进程的推进顺序不当。系统资源既可能是可重用的永久性资源，也可能是消耗的临时资源。关于可重用资源死锁存在四个必要条件，他们是：（1）互斥条件：又称独占条件，即一个资源每次只能被一个进程使用。（2）保持和等待条件：又称部分分配条件：即一个进程已获得一些资源，又因请求其他资源而被阻塞等待。（3）不剥夺条件：进程已获得的资源，不经进程释放，不能剥夺这个资源。（4）环路等待条件：若干进程形成一个环形链，其中每一个进程占有链中下一个进程所申请的一个或多个资源。（4）答：连续分配存储空间存在的许多存储碎片和空间管理较复杂的问题，其原因在于连续分配要求把作业放在主存的一片连续区域中。页式管理能够避开这种连续性需求。页式管理系统工作原理如下图所示，图中显示了从逻辑地址LA到物理地址PA的映射过程。下图是一个虚地址的例子，是16个4K页的情况下MMU的内部操作。虚地址8196（二进制为：0010000000000100），输入的16位虚地址被分为4位的页号和12位的偏移量，4位的页号可以表示16个页面，12位的偏移可以为一个页内的全部4096个字节编址。页号用作页表的索引，以得出对应于这个虚页的页框号。如果在/不在位是0，则将引发一个操作系统的陷入；如果这个位是1，在页表中查到的页框号将被复制到输出寄存器的高三位中，加上输入地址中的12位偏移量，就构成了15位的物理地址。输出寄存器的内容随即被作为物理地址送到内存总线。 三、设TLB的访问时间为TC，页表的访问时间为TP，TLB的命中率为h，平均开销时间TM。则TM=h*（TC）+（1-h）*（TC+TP），解得 h=（TC+TP-TM）/TP=（100+500-200）/500=0.8。四、读取一个块的时间为：寻道延迟+旋转延迟/2+传送时间。（1）在第一种情况下传输100块的文件需要的时间为：（13*6+100/2+25）*100=15300ms。 （2）在第一种情况下传输100块的文件需要的时间为：（2*6+100/2+25）*100=8700ms。五、块2在两个文件中出现，如果删除任何一个文件，磁盘块2会加到空闲表中，导致一个磁盘块同时出现在文件和空闲表中。两个文件都删除后，这个磁盘块会在空闲表中出现两次。文件系统可以这样处理，先分配一个空闲块，把磁盘块2中的内容复制到空闲块中，然后把它插入到其中一个文件中。这样，文件中的内容未改变，而文件系统的结构保持了一致。 块5既出现在使用表中，又出现在空闲表中。只需重新建立空闲表。 块6不出现在任何一张表中，这时报告块丢失。尽管块丢失不会造成任何损坏，但浪费了磁盘空间，减少了磁盘容量。解决块丢失问题是比较简单的，只需要重新建立空闲表。六、把64K的文件从这样的磁盘上装入内存需要的时间计算如下：一般来说，页的大小与块的大小是一样的，取块的大小为4K。则共有64/4=16个块，每块的装入时间为：寻道延迟+旋转延迟+传送时间=30+20/2+（4/32）*20=42.5ms整个文件的装入时间为: 42.5*16=680ms。操作系统作业题（2）参考答案一、（1）为用户提供一个虚拟机，管理系统的各种资源 （2）页式管理，段式管理，段页式管理 (3) 寻道时间，旋转延迟，实际的数据传输时间（4）SEND调用， RECEIVE调用二、1、答：不一定。发生死锁需要满足四个条件：（1）互斥条件，每一个资源或者分配给一个进程，或者空闲。（2）保持和等待条件，已经分配到了一些资源的进程可以申请新的资源。（3）非剥夺条件，已分配给一个进程的资源不可剥夺，只能被占有它的进程明确地释放。（4）循环等待条件，系统必然有两个或两个以上的进程组成的循环链，链中的每一个进程都在等待相临进程占用的资源。这四个条件是发生四锁的必要条件，只要其中的一条或多条不成立，就不会发生死锁。因此当多个进程同时对几个有限的资源进行互斥访问，是否发生死锁要看它是否满足以上四个条件。2、答：三级存储结构主要由高速缓存（CACHE）、主存储器（RAM）和磁盘组成。高速缓存（CACHE）相对于主存储器（RAM）来说，价格昂贵，存储速度非常快，容量很小。主存储器（RAM）相对于磁盘来说，价格较贵，存储速度较快，容量较小。磁盘的价格便宜，存储速度慢，但容量非常大。3、 答：FIFO算法选择淘汰在主存驻留时间最长的页。这似乎比较合理，但可能淘汰立即要使用的页。另外，使用FIFO算法时，在未给予进程分配足够的页面时，有时会出现给予进程的页面数越多，缺页次数反而增加的异常现象，这称为Belady现象。二次机会算法所做的就是寻找从上一次检查以来有没有引用过的页面。如果所有的页面被引用过了，它就降级为纯粹的FIFO算法。显然二次机会算法要优于FIFO算法。4、 答：进程是指一个正在执行的程序，包括计数器、寄存器和变量的当前值。每个进程拥有他自己的虚拟CPU，有一个地址空间和单线程控制。线程像微小进程，每个线程按顺序执行，并有自己的程序计数器和堆栈来记录运行到什么地方。线程能够创建子线程也能阻塞以等待系统调用来完成。通常，多个线程共享一个进程的地址空间。一个进程拥有一个或多个线程。线程相对于进程，犹如进程相对于机器。三、 这五个作业的预计运行时间是确定的，因此用最短作业优先是最优的，即平均周转时间最短。答案取决于X的值。X可在3，6，9，10这个顺序间的任何位置，保持这个顺序是由小到大的顺序。四、设TLB的访问时间为TC，页表的访问时间为TP，TLB的命中率为h，平均开销时间TM。则TM=h*TC+（1-h）*（TC+TP），解得 h=（TC+TP-TM）/TP=4/5=0.8。五、(1) FIFO（先进先出算法）： （1，2，3，4，5，1）；(2) LRU（最近最少使用算法）：（3, 4，5，3）；(3) NRU（最近不使用算法）： （4，5，4）；六、设TLB的访问时间为TC，页表的访问时间为TP，TLB的命中率为h，平均开销时间TM。则TM=h*（TC）+（1-h）*（TC+TP），解得 TM=0.8*（100）+(1-0.8)*(100+2000)=500微妙。操作系统作业题（3）参考答案一、(1)B,D (2)A,B,C,D (3)A (4)C (5) B (6)D (7)A,B,C，D (8)C (9)A,B,C (10)A,B,C,D二、1、答：上图中方形表示资源，圆形表示进程。共有两个进程和两个资源。从进程到资源的有向箭头表示进程当前正申请该资源并处于阻塞状态。从资源节点到进程的有向箭头表示该资源已被进程占用。上图就表示这两个资源出现了死锁。进程C等待资源T，资源T又被进程D占用，进程D又在等待被进程C占用的资源U。于是两个进程都将等待下去。2、 答：在分页系统中，由于页表尺寸较大，因此许多分页方案都只能把它保存在内存中，但这种设计对性能有很大的影响。例如一条把寄存器的内容复制到另一个寄存器中的指令，在不使用分页时只需要访问内存一次以获取指令，而在使用分页时需要额外的内存访问去读取页表。因为系统的运行速度一般都是受CPU从内存中取得指令和数据的速率所限制的，因而在每次访问内存时都要访问两次页表会使机器的性能降低2/3，这样的系统是没有人愿意使用的。因此在分页系统中，如何提高对页表的查询速度就成为研究的焦点。解决的办法是，为计算机装备一个不需要经过页表就能把虚地址映射成为物理地址的小的硬件设备，这个设备就是转换后援存储器TLB。当一个虚地址被送到MMU进行转换时，硬件首先把它和TLB中的所有条目同时进行比较，看它的页号是否在TLB中，如果找到了并且这个访问没有违反保护位，则它的页框号将直接从TLB中取出而不用去查页表。3、答：（1）要使a，b两个进程互斥，只需设定一个信号量mutex，该信号量mutex的取值为0、1和-1三个值，若Mutex=1表示没有进程进入临界区；当Mutex=0表示有一个进程进入临界区；当Mutex=-1表示有一个进程进入临界区，另一个进程等待进入。设定Mutex的初始值为1。当a进程预进入临界区时，首先检查Mutex的值，如果Mutex0，进程a把Mutex做减一操作后，进入临界区。当Mutex=0时，进程a被阻塞并等待。当进程a退出临界区时，把Mutex做加一操作。当进程a已进入临界区时，如果进程B也想进入临界区，它也要首先检查Mutex的值，此时发现Mutex的值小于等于0，则进程b被阻塞并等待。（2）要使a，b两个进程同步，需设定两个信号量SA和SB。假设a进程表示计算进程，b表示打印进程。信号量SA用来表示缓冲区中是否已有可供打印的计算结果，其初值为0。每当计算进程a把所得之结果送入缓冲区后，便对SA执行V（SA）操作，表示已有可打印的计算结果。打印进程在执行前须先对SA执行P（SA）操作，若SA0，表示缓冲区中尚无可供打印之计算结果，打印进程阻塞。若P操作SA=0，则打印进程可执行打印操作。信号量SB用以表示缓冲区中的计算结果是否已被打印进程取走，其初值为0。每当计算进程a把所得之结果送入缓冲区后，便对SB执行P（SB）操作，若结果SB=2 then wait(db); /如果有读写进程数大于等于2，则写进程应阻塞V(mutex);write_data_base();P(mutex);Rc:=rc-1;V(mutex);end;end monitor;procedure readerbegin while true do begin ReaderWriter.read; Use_data_read(); /使用所读的数据end;end;procedure writerbegin while true dobegin think_up_data(); /准备要写的数据ReaderWriter.write;end;end;操作系统作业题（5）参考答案一、（1）答：V操作的次序无关紧要，颠倒次序后不会发生死锁。因为它不会出现一个进程在临界区保持，而另一个进程不能进入临界区的情况。（2）答：当N取1，2，3时，系统均不会发生死锁。因为在这种情况下，六台打印机是足够使用的，也就是说，资源是充足的。但当N取值大于等于4时系统就有可能发生死锁。（3）答：我们通过一个例子来看从虚地址到物理地址的映射过程。下图是一个虚地址的例子，是16个4K页的情况下MMU的内部操作。虚地址8196（二进制为：0010000000000100），输入的16位虚地址被分为4位的页号和12位的偏移量，4位的页号可以表示16个页面，12位的偏移可以为一个页内的全部4096个字节编址。页号用作页表的索引，以得出对应于这个虚页的页框号。如果在/不在位是0，则将引发一个操作系统的陷入；如果这个位是1，在页表中查到的页框号将被复制到输出寄存器的高三位中，加上输入地址中的12位偏移量，就构成了15位的物理地址。输出寄存器的内容随即被作为物理地址送到内存总线。 （4）答：程序具有顺序性特征，处理机严格地顺序执行程序所规定的动作，即每一个动作都必须在前一个动作结束以后开始。程序与其执行过程一一对应。静态地看，程序是指令的有序集合。程序在处理机上一次动态地执行活动称为程序的执行过程。显然，程序被启动运行后，它唯一地对应一个执行过程。同理，程序的动态执行过程也唯一地对应一个静态程序。同时，程序还具有封闭性和可再现性特征。进程是可以并行运行的计算部分，是一个可以独立调度的活动。具有动态性、并发性、独立性和相互制约等特征。它是程序在处理机上执行时的一个活动。二、monitor ReaderWritercondition dbinteger rc, mutex /正在读写或想要读写的进程数rc:=0;mutex:=1;procedure readP(mutex);rc:=rc+1;V(mutex);read_data_base();P(mutex);rc:=rc-1;if rc=0 then signal(db);V(mutex);end;procedure writeP(mutex);rc:=rc+1if rc=2 then wait(db); /如果有读写进程数大于等于2，则写进程应阻塞V(mutex);write_data_base();P(mutex);Rc:=rc-1;V(mutex);end;end monitor;procedure readerbegin while true do begin ReaderWriter.read; Use_data_read(); /使用所读的数据end;end;procedure writerbegin while true dobegin think_up_data(); /准备要写的数据ReaderWriter.write;end;end;三、图中第一个接点A20表示以当前时间4000秒为基准，经过20秒后触发A事件；图中第二个接点BC10表示以当前时间4000秒为基准，经过30秒后触发B和C事件；图中第三个接点A10表示以当前时间4000秒为基准，经过40秒后再次触发A事件；图中第四个接点C15表示以当前时间4000秒为基准，经过55秒后触发C事件；图中第一个接点D10表示以当前时间4000秒为基准，经过65秒后触发D事件；四、（1）时间片轮转法作业的平均周转时间为：（10+6+2+4+8）/5=6分钟。（2）优先级调度作业的平均周转时间为：T=。=（4+0+24+26+6）+（10+6+2+4+8）/5=18分钟。（3）SJF作业的平均周转时间为：T=。=（20+6+0+2+12）+（10+6+2+4+8）/5=14分钟。五、 这两个并发执行的程序的执行是不正确的，因为这两个并发程序都访问了公共变量X，如果不设置临界区，程序的执行结果可能不正确。例如，P1进程和P2进程同时运行，P1进程先执行到X：=1这条语句，在将要执行IF X=1 THEN Y：=Y+1时，这时P2进程已执行到X：=0；所以P1进程执行IF X=1 THEN Y：=Y+1时就不是既定的执行路径了。只需对临界区施加PV操作就可以确保这两个程序互斥运行。设定一个信号量为mutex，并令初始值为1。修改后的程序如下：Cobeginvar x integer;mutex： semaphore；mutex：=1；Procedure p1 /并发进程p1 var y, z: integer; beginP（mutex）；x:=1;y:=0;if x=1 then y:=y+1;z:=y;V（mutex）；end.Procedure p2 /并发进程p2Var t, u : integer;Begin P（mutex）；X:=0; T:=0; If x=1 then T:=t+1; U:=t;V（mutex）；End.Coend.六、 这两个进程可能会发生死锁。比如进程A执行了P（S1）后，S1=0，而进程B执行了P（S2），使得S2=0；当进程B继续执行P（S1）时，进程B阻塞，当进程A执行P（S2）时，也将阻塞。从而系统进入死锁状态。可修改为：A: P(S1);MP(S2);V(S2);MV(S1);MB: V(S1);MV(S2);P(S2);MP(S1);M操作系统作业题（6）参考答案一、选择题（1） D （2） C （3） C （4） B （5） D（6） C （7） A （8） D （9） C （10）A（11） D （12） B （13） C （14） D （15）D（16） D （17） C （18） D （19） D （20）C二、简答题 （1）答：1、进程是资源管理的基本单位，拥有自己独立的地址空间和各种资源，而线程只是处理机的调度单位，共享进程中的资源。2、多线程可以减少用户的等待时间，提高响应速度。3、以进程为调度单位时，处理机切换时间长，资源利用率低；以线程为处理机调度单位时，由于不发生地址空间变换，因而处理机的效率较高。4、进程是指一个正在执行的程序，包括计数器、寄存器和变量的当前值。每个进程拥有他自己的虚拟CPU，有一个地址空间和单线程控制。线程像微小进程，每个线程按优先级顺序执行，并有自己的程序计数器和堆栈来记录运行到什么地方。5、线程能够创建子线程也能阻塞以等待系统调用来完成。通常，多个线程共享一个进程的地址空间。一个进程拥有一个或多个线程。线程相对于进程，犹如进程相对于机器。 （2）答：时间片大小的选择对计算机系统性能有很大影响。所以时间片大小的选择要满足系统设计的目标。如果时间片选择过大，该算法就退化为先来先服务算法。如果选择过小，进程切换次数增大，系统开销也相应地增大。所以，在选择时间片大小时要考虑以下几个因素：1、系统响应时间的要求：分时系统必须满足系统对响应时间的要求。当系统进程的数量一定时，时间片的长短将与系统的响应时间成正比；当系统的终端数一定时，时间片的大小与终端数成反比。2、系统处理能力：时间片大小的选择应能保证用户常用命令的能够在一个时间片内完成，以缩短平均周转时间。 （3）答：只要破坏产生死锁的四个必要条件之一便可预防死锁。常用的预防死锁的方法有：1、资源静态分配方法。用于破坏请求和保持条件，即在某一个进程运行之前一次申请它所需要的全部资源；在它的资源未满足之前，不投入运行；一旦投入运行后，这些资源一直归它占用，也不再申请其他资源。2、资源顺序分配方法。用于破坏环路等