操作系统习题课1.doc

1、什么是进程？它与程序有什么不同？ 进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动。 进程和程序的区别：进程是程序处理数据的过程，而程序是一组指令的有序集合；进程具有动态性、并发性、独立性和异步性，而程序不具有这些特性；从进程的结构特性上看，它包含程序；进程和程序并非一一对应。2、为什么要引入进程的概念？ 程序并发执行时产生了一系列程序顺序执行时所没有的新的特点，传统的“程序”概念已不足以描述和刻画他们，为此引入“进程”的概念，以实现程序在多道系统中的并发执行。3、什么叫进程同步和互斥？举例说明 进程同步是指一个进程的执行会因为等待另一个进程的某个事件而受到影响。例如消息发送原语与消息接收原语的执行。 进程互斥是指一个进程正在使用某个系统资源，另一个想用该资源的进程就必须等待，而不能同时使用。例如死锁现象，正是由于进程的互斥，同一个系统资源不能同时被多个进程使用，才会出现互相等待的状态，造成死锁。5、请求分页技术和简单分页技术之间的根本区别是什么？根本区别是：（1）请求分页技术在作业运行之前，只要求把作业当前所需要的一部分页面装入主存，其它部分放入辅存，当需要其它的页面时，再把所需页面调入主存，从而实现了存储扩充，使得小内存可以运行大作业。（2）简单分页技术在作业运行之前，要把全部作业都装入主存，没有实现存储扩充。6、什么是死锁？造成死锁的根本原因是什么？在系统中某个进程提出资源请求后，使得若干进程在无外力作用下永远不能前进（继续运行），系统处于停滞状态，这种现象称为死锁。处于死锁状态的进程称为死锁进程。死锁大多是由于并发进程共享临界资源引起的，死锁与时间相关。产生死锁的根本原因是：（1）系统资源不足；（2）进程运行推进的顺序不合适；（3）资源分配不当之处。7、什么是分页？什么是分段？二者有何主要区别？ 分页是将一个进程的逻辑地址空间分成若干个大小相等的页（或称页面），内存空间分成与页相同大小的物理块（或称页框）。在为进程分配内存时，以块为单位进行分配，每页分配一块。系统为每个进程建立一张页面映射表（简称页表），记录相应页在内存中对应的物理块号。 分段是将程序的地址空间被分成若干个段，每段采用连续的地址空间。这样程序的逻辑地址就形成一个二维地址，由段号和段内地址两部分组成。系统为每段分配一个连续区域（相当于一个分区），各段可以存放在不同的分区中，即段与段之间的地址是不连续的。系统为每个进程建立一张段表，记录该段在内存中的起始地址和段长。 区别：页是信息的物理单位，页的内容通常无完整意义；而段是信息的逻辑单位，段的内容具有完整的逻辑意义页的大小固定且由操作系统决定；而段的长度不固定，取决于用户所写的程序。分页的作业地址空间是一维线性连续的；而分段的作业地址空间是二维的。分页的活动对用户是透明的；而分段是用户可见的活动。8、什么是操作系统的基本功能？9、什么是请求分页存储管理？其最大的优点是什么？（1）请求页式管理是动态页式内存管理的一种，它在作业或进程开始执行之前，不把作业或进程的程序段和数据段一次性的全部装入内存，而只装入被认为是经常反复执行和调用的工作区部分。其他部分则在执行过程中动态装入。（2）请求页式管理的调入方式是，当需要执行某条指令而又发现它不在内存时，或当执行某条指令需要访问其他数据或指令时，而这些数据和指令又不在内存中，从而发生缺页中断，系统将外存中相应的页面调入内存。（3）请求页式管理的最大优点就是实现了对主存的虚拟扩充，从而解决了小内存运行大作业问题。10、什么是缓冲？为什么要引入缓冲？ 缓冲：缓冲即是使用专用硬件缓冲器或在内存中划出一个区域用来暂时存放输入输出数据的器件。 原因：为了缓解CPU与I/O设备速度不匹配的矛盾、为了减少外设中段CPU的次数、为了提高CPU与I/O设备之间的并行性。11、文件系统主要功能有哪些？ 文件系统的主要功能有：文件的读/写管理；文件目录管理；文件存储空间管理；文件保护与共享；提供方便的接口；文件系统的可靠性和一致性。12、存储管理主要有哪些功能？存储管理主要有：管理和分配内存；地址映射；内存的保护和共享；提高内存使用效率和提高内存访问时间13、什么叫地址再定位？在什么情况下要采用地址再定位？地址再定位：即把逻辑地址转换为物理地址的过程。14、简述缓冲池的管理方法。15、试述UNIX系统文件存储空间的管理。五、问答题/计算题/证明题/算法设计题（每题10分，共20分）。1、 在一个盒子里，混装了数量相等的围棋白子和黑子，现在要用自动分拣系统把白子和黑子分开。该系统设有两个进程P1和P2，其中P1拣白子，P2拣黑子。规定每个进程每次只拣一子，当一进程正在拣子时，不允许另一个进程去拣，当一进程拣了一子时，必须让另一进程去拣，试写出两个并发进程能正确执行的算法。解：main() int S1=1; /进程P1的私有信号量，初始值为1 int S2=0; /进程P1的私有信号量，初始值为0 int n=1000;/围棋所有黑子和白子总数while(n!=0) P1(); /拣白子进程P2(); /拣黑子进程 P1( ) p(S1); 拣白子； n=n-1 V(S2); P2() p(S2); 拣黑子； n=n-1; V(S1);2、某段式存储管理中采用如下表所示的段表。 段表段号段的长度/B内存起始地址06602191143330210090358012374961952（1）给定段号和段内地址，说明段式管理中的地址变换过程。（2）计算0，430，110，2，500，3，400，4，20，5，100的内存地址，其中方括号内的第一元素是段号，第二元素是段内地址。（3）说明存取主存中的一条指令或数据至少要访问几次主存。答：（1）为了实现从逻辑地址到物理地址的变换，在系统中需要设置段表寄存器，存放段表起站地址和段表长度TL。在进行地址变换时，系统将逻辑地址中的段号S与段表长度TL进行比较。若STL，则表示段号太大，是访问越界（段号越界），产生越界中断。若未越界，则根据段表的起始地址和段号，计算出该段对应段表项的位置，从中读出该段在内存中的起始位置和段长SL，再检查段内地址d是否超过该段的段长SL。若超过，即dSL，则同样发出越界中断信号（段内地址越界）；若未越界，则将该段的起始地址与段内地址d相加，即得要访问的内存物理地址。（2）0，430的物理地址是219430=649。 1，10的物理地址是330010=3310。 因 500100，所以2，500越界（段内地址越界）。 3，400的物理地址是1237400=1637。 4，20的物理地址是195220=1972。 因 54，所以5，100越界（段号越界）。（3）存取主存中的一条指令或数据至少要访问2次主存。一次是访问段表，另一次是访问需要的指令或数据。3、假设某系统中有4种资源（R1，R2，R3，R4），在某时刻系统中共有5个进程。进程P1，P2，P3，P4，P5的最大资源需求数向量和此时已分配到的资源数向量分别为进程当前已分配到资源最大资源需求P1（0，0，1，2） （0，0，1，2）p2（2，0，0，0 ） （2，7，5，0 ）P3（0，0，3，4） （6，6，5，6）P4（2，3，5，4） （4，3，5，6）P5（0，3，3，2） （0，6，5，2）系统中当前可用资源向量为（2，1，0，0）。问：（1）当前系统是否是安全的？（2）如果进程3已发出资源请求向量（0，1，0，0），系统能否将资源分配给它？4、考虑下述页面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6当内存块数量分别为4，5时，试问LRU，FIFO，OPT这三种置换算法的缺页次数各是多少？（初始内存块中无页面）解：当内存块数量分别为4时，（1）LRU置换算法的缺页次数是：101234215621237632123612342156212376321236123421562123763212312342156612376331211342155612276661当内存块数量分别为5时，（1）LRU置换算法的缺页次数是：8123421562123763212361234215621237632123612342156212376321231234215661237633121134215561227666134444561117777当内存块数量分别为4时，（2）FIFO置换算法的缺页次数是：141234215621237632123612344456211376621133123334562213776221112223456621337662211123455621137766当内存块数量分别为5时，（2）FIFO置换算法的缺页次数是：10123421562123763212361234445661237777777712333455612333333331222344561222222221112334561111111112234566666666当内存块数量分别为4时，（3）OPT置换算法的缺页次数是：81234215621237632123612344456666677771111123333333336666666612222222223333333311111111122222222当内存块数量分别为5时，（3）OPT置换算法的缺页次数是：71234215621237632123612344456666677777777123334555556666666612223333333333333311122222222222222111111111111115、页系统，主存容量为64KByte 页面大小为1K Byte ,对一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中。将十进制逻辑地址1023、2500、3500、4500转换成物理地址。每个页为1KB即1024B，由1023/1024可得页号为0，内地址为1023，查页表可知主存块号为2，因此1023的物理地址为2102410233071由2500/1024得页号为2，内地址为452，主存块号为6，2500的物理地址为610244526596由3500/1024得页号为3内地址为428，主存块号为73500的物理地址为7102442875966、考虑由n个进程共享的具有m个同类资源的系统，证明：如果对i=1，2，3，n，有Needi0（即n个进程中的任一进程的资源需求数都大于0），而且所有进程的最大资源需求量之和小于m+n，那么该系统是死