操作系统-习题课-0614课件

操作系统习题课By2011-06-14第二章 OperatingSystemStructures2.5 操作系统关于文件管理的五个主要活动是什么？答案： 1) 创建和删除文件 2) 创建和删除目录 3) 提供操作文件和目录的原语 4) 将文件映射到二级存储器（辅存）上 5) 在稳定（非易失的）的存储媒介上备份文件分析：

许多同学会把文件管理的五个功能写成“打开文件、读

写重定位文件、关闭文件、读取文件属性、设置文件属

性等”。这些都属于“提供操作文件和目录的原语”。第二章 OperatingSystemStructures2.8 通信的两种模式是什么？这两种模式的优点和缺点是

什么？答案：

通信的两种模式是1）共享内存，2）消息传递。

<消息传递>

优点：

可以用作同步机制来处理进程间的通信；交换

的数据量少时，不必避免冲突；也比用于计算

机间通信的共享内存更容易实现。

缺点：

信息传递通常包含系统调用。

<共享内存>

优点：

允许通信的最大速度和方便性；进程间通信不

需要内核的协助

缺点：

在保护和同步方面仍存在一定问题；没有提供

协调通信进程同步的进程。第三章 Processes3.5 下面设计的优点和缺点分别是什么? b) 自动和显式缓冲答案：

自动缓冲：提供了一个无限容量的缓冲，即队列长度可

以无限。因此不管多少消息都可以在其中等待，从而保

证了发送者在复制消息时不会因为缓冲区已满而遇到阻

塞。然而这种方法往往会为了保留足够大的内存而导致

资源的浪费。

显式缓冲：队列长度为有限的n，因此最多只能有n个消

息驻留其中。若发送消息时队列未满则发送者不必等待

不过若队列已满发送者则必须阻塞直到队列中的空间可

用为止。但是，这种方法会使得内存被浪费的可能性大

大的降低。第三章 Processes附加题

改写生产者消费者伪代码，允许在缓冲内最多有 BUFFER_SIZE项。两种简单的方法：方法A：使用标志flag，记录对队列最后的操作是删除还是插入。当头尾指针相等时，如果标志记录的是删除，则队列空。如果记录的是插入，则队列满。intflag=0;//0代表空，1代表满，2代表未空未满while(1){//生产者

/*produceaniteminnextProduce*/

while(flag==1)//队列满，等待

;/*donothing*/buffer[in]=nextProduce;in=(in+1)%BUFFER_SIZE;

if(in==out)flag=1;//若在生产之后in==out，则队列满

elseflag=2；}第三章 Processeswhile(1){//消费者

while(flag==0);/*donothing*/nextProduce=buffer[out];out=(out+1)%BUFFER_SIZE;if(in==out)flag=0;//若在消费之后in==out，则队列空

elseflag=2;/*consumeaniteminnextProduce*/}第三章 Processes方法B：增加一个计数器counter，每次向缓冲区增加一个新项时，counter就递增；每次从缓冲中移去一项时，counter就递减。intcounter=0;while(1){//生产者

/*produceaniteminnextProduce*/

while(counter==BUFFER_SIZE)//队列满，等待

;/*donothing*/buffer[in]=nextProduce;in=(in+1)%BUFFER_SIZE;

counter++;}第四章 Threads主要考察内容：1）线程基本概念2）多线程模型（多对一、一对一、多对多）第五章 CPUScheduling主要考察内容：1）基本概念（可抢占式等）2）调度准则（CPU使用率、周转时间、等待时间等）3）调度算法（FCFS、SJF、优先权调度等等）第五章 CPUSchedulingPriority调度算法（不少同学没按照“同等优先级按照FCFS”的算法来执行）

016161819P2P5P1P3P4b.在a里每个进程在每种调度算法下的周转时间是多少？周转时间：从进程提交到进程完成的时间间隔。c.在a里每个进程在每种调度算法下的等待时间是多少？等待时间：在就绪队列中等待所花时间之和。第六章 ProcessSynchronization主要考察内容：1）基本概念2）临界区问题的解答（三个条件）3）信号量4）经典同步问题（有限缓冲问题、读者-写者问题等）第六章 ProcessSynchronization6.1 第一个著名的正确的解决了两个进程的临界区域问题的软件解决方案是由Dekker提出的。P0、P1两个进程，共享以下的变量：booleanflag[2];/*initiallyfalse*/intturn;进程Pi(i==0or1)和另一进程为Pj(j==1or0)的结构见下面代码。证明这个算法满足临界区问题的三个条件。第六章 ProcessSynchronization进程Pi的结构：do{ flag[i]=true; while(flag[j]){ if(turn==j){ flag[i]=false;

while(turn==j); flag[i]=true; } }

临界区 turn=j; flag[i]=false;

剩余区}while(1);临界区必须满足以下三个条件：互斥、有空让进、有限等待。（1）互斥：只有当flag[j]=false或者turn==i时，进程Pi才进入临界区。如果两个进程同时在临界区执行，那么flag[i]==flag[j]==true，可是由于turn不可能同时等于0和1，Pi、Pj互斥。（2）有空让进：若Pi跳出临界区，则必定会执行flag[i]=false，从而使进程Pj跳出循环而进入临界区，从而达到是Pj前进的目的。（3）有限等待：从（2）可知，Pj最多在Pi进入临界区一次后就可进入，因此Pj的等待次数有限。第六章 ProcessSynchronization6.3 忙等待的含义是什么？在操作系统中还有哪些其他形式的等待？忙等待能完全避免吗？给出你的答案。分析：

许多同学认为采用了PV信号量，忙等待就能完全避免，其实忙等待并不能完全避免的。只是尽量的减少了。只是将应用程序临界区的忙等限制到wait()和signal()操作的临界区，这些区比较短。因此几乎不占用临界区，忙等很少发生，且所需的时间很短。详细可参考英文版教科书P203最下面一段。第七章 Deadlocks7.5 下面哪些变化是安全的，不会发生死锁？a)增加可用资源Available（新的资源被添加到系统）b)减少可用资源Available（资源被从系统中永久性地移出）21安全性第二条b资源请求算法第二条23e)增加进程的数量f)减少进程的数量7.5 下面哪些变化是安全的，不会发生死锁？第七章 Deadlocks第八章 MemoryManagement主要考察内容：1）基本概念（物理地址、逻辑地址、内/外部碎片等）2）连续内存分配（首次/最佳/最差适应）3）分页（逻辑地址映射成物理地址）4）分段（逻辑地址映射成物理地址）第八章 MemoryManagement8.3 按顺序给出5个部分的内存，分别是100KB,500KB,200KB,300KB和600KB，用first-fit,best-fit和worst-fit算法，能够怎样按顺序分配进程212KB,417KB,112KB和426KB？哪个算法充分利用了内存空间？首次适应最差适应8.9 考虑一个分页系统在内存中存储着一张页表。a.如果内存的查询需要200毫秒，那么一个分页内存的查询需要多长时间？b.如果我们加上相关联的寄存器，75%的页表查询可以在相关联的寄存器中找到，那么有效的查询时间是多少？（假设如果入口存在的话，在相关的寄存器中找到页表入口不花费时间）第八章 MemoryManagement答案： a.400毫秒：200毫秒进入页表，200毫秒进入内存中的字

b.在寄存器中查询到的时间：寄存器中查询页表入口时间（0）+读取内存时间（200ms）

在寄存器查询不到的时间：查询页表时间（200ms）+读取内存时间（200ms）

有效访问时间=0.75*200毫秒+0.25*400毫秒=250毫秒第九章 VirtualMemory主要考察内容：1）基本概念2）页面调度的性能（计算有效访问时间）3）页面置换算法（FIFO、LRU等）4）系统颠簸原因以及解决办法第九章 VirtualMemory9.10 问：假设一个具有下面时间度量利用率的请求调页系统：

CPU利用率20％，分页磁盘97.7％，其他I/O设备，5％

说明下面哪一个（可）能提高CPU的利用率，为什么？

G对页面调度算法添加预取页 H增加页面大小答案：

G：有可能。关键问题是采用预约式页面调度的成本是否小于处理相应页错误的成本，有可能通过预约式页面调度而调回内存的许多页可能没有被使用。（P357）

H：如果数据访问是顺序进行的，增加页面大小将会减少页面错误，因为每一页的内容增加了，可读取更少的页来获取更多的内容。但是，如果数据访问是随机的，当发生页错误需要调入页的时候，增加页面的大小反而会浪费更多时间在调入页面上。9.14 假设一个请求调页系统具有一个平均访问和传输时间为20ms的分页磁盘。地址转换是通过在主存中的页表来进行的，每次内存访问时间为1µs。这样，每个通过页表进行的内存引用都要访问内存两次。为了提高性能，加入一个相关内存，当页表项在相关内存中时，可以减少内存引用的访问次数。

假设80%的访问发生在相关内存中，而且剩下中的10%（总量的2%）会导致页错误。内存的有效访问时间是多少？第九章 VirtualMemory答案： 80%的访问在相关存储器中，耗时1µs. 18%（剩下的90%*20%）的访问需在页表和内存中进行，两次共2µs. 2%的访问在页表中产生了页错误，经调页系统工作后再访问内存，共20ms+2µs=20002µs.

有效访问时间=(0.8)×(1µs)+(0.18)×(2µs)+(0.02)×(20002µs)=401.2µsec第九章 VirtualMemory第十章 Interface10.9 有些系统文件提供文件共享时候只保留文件的一个副本，而有些则是保留多个副本，对共享文件的每一个用户提供一个副本，论述这种方法的相对优点。答案：

只保留一份副本：占用的空间少，管理的开销也少。但是这样也会导致数据的不一致。若多个用户同时更新了一个文件，就可能会导致用户获得不正确的信息，而文件也处在了不正确的状态。

多份副本：能够灵活处理多用户访问的问题。但是它会浪费存储空间，而且由于每个用户都是用单独的副本，所以可能导致副本之间的内容不一致，这样更新和维护起来更加复杂。第十一章 Implementation主要考察内容：1）基本概念2）分配方法（连续分配、链接分配、索引分配）3）空闲空间管理（位向量、链表、组等）第十一章 Implementation11.3 假设有一个系统，它的空闲空间保存在空闲空间列表中： b.假设一个类似于UNIX的使用索引分配的文件系统，要读一个很小的本地文件/a/b/c需要多少I/O操作？答案：

算上访问目标文件的话，一共是6次。

abc文件索引块文件root11.6 设想一个在磁盘上的文件系统的逻辑块和物理块的大小都为512B。假设每个文件的信息已经在内存中，对3种分配方法（连续分配，链接分配和索引分配），分别回答下面的问题： A.逻辑地址到物理地址的映射在系统中怎么样进行的？（对于索引分配，假设文件总是小于512块长）第十一章 Implementation答案：

链接分配：

逻辑地址/（512B—指针所占空间）=X………Y

从链表中查找第X+1块，（Y+指针所占空间）是最后一块物理块的块内偏移地址

分析：

对应每一块的分配如上图，指针和data共同占有了一个块