操作系统概念(第七版-翻译版)复习题

2011-12操作系统复习题(一)进程同步进程同步1进程P1和进程P2并发执行时满足一定的时序关系，P1的代码段S1执行完后，才能执行P2的代码段S2.为描述这种同步关系，：试设计相应的信号量，：给出信号量的初始值，：给出进程P1和P2的结构进程同步2问题描述：(理发店问题)一个理发店有一间配有n个椅子的等待室和一个有理发椅的理发室。如果没有顾客，理发师就睡觉；如果顾客来了二所有的椅子都有人，顾客就离去；如果理发师在忙而有空的椅子，顾客就会坐在其中一个椅子；如果理发师在睡觉，顾客会摇醒他。①给出同步关系②设计描述同步关系的信号量；③给出满足同步关系的进程结构(请完成满足同步关系的进程结构)。进程同步2设公共汽车上，司机和售票员的活动分别为：司机的活动为启动车辆，正常行车，到站停车；售票员的活动为关车门，售票，开车门。给出在汽车不断地到站、停车、行驶过程中，司机和售票员的活动的同步关系。用信号量和wait,signal操作实现他们间的协调操作。进程同步3：某高校计算机系开设网络课并安排上机实习，假设机房共有2m台机器，有2n名学生选该课，规定：(1)每两个学生组成一组，各占一台机器，协同完成上机实习；(2)只有凑够两个学生，并且此时机房有空闲机器，门卫才允许该组学生进入机房；(3)上机实习由一名教师检查，检查完毕，一组学生才可以离开机房。试用信号量机制实现它们的同步关系。进程同步4：多个进程对信号量S进行了5次wait操作，2次signal操作后，现在信号量的值是-3，与信号量S相关的处于阻塞状态的进程有几个？信号量的初值是多少？进程同步5：使用两个进程计算Y=F1(X)+F2(X).在这个问题中，F1(X)和F2(X)的计算是可以并行处理的，因此F1(X)和F2(X)可以分别出现在两个进程中。在F1(X)+F2(X)中，必须在F1(X)和F2(X)计算完毕，才能进行加法运算，因此本问题是同步问题。(1)确定并发和顺序操作(2)确定互斥或同步的规则(3)同步的操作流程(4)确定信号量的个数和含义(5)确定进程的程序结构进程同步6：如下图所示，有多个PUT操作同时向BUFF1放数据，有一个MOVE操作不断地将BUFF1的数据移到Buff2，有多个GET操作不断地从Buff2中将数据取走。BUFF1的容量为m，BUFF2的容量是n,PUT、MOVE、GET每次操作一个数据，在操作的过程中要保证数据不丢失。试用wait、signal原语协调PUT、MOVE的操作，并说明每个信号量的含义和初值。(1)确定并发操作的规则(2)设计信号量、初始值及用途含义(3)给出进程的程序结构GETPUTBuff1Buff2MOVE进程同步7：一售票厅只能容纳300人，当少于300人时，可以进入；否则，需在外等候。若将每一个购票者作为一个进程，请用wait、signal操作给出进程程序结构，并写出信号量及初值。进程同步8：针对如下所示的优先图，使用信号量给出正确的程序结构。S1S4S2S3S5S6(二)进程调度与死锁进程调度与死锁1：5个进程，3种资源，某个时刻，资源分配情况如下：AllocationMaxAvailableABCABCABCP0010753,332P1200322P2302902P3211222P4002433问：系统是否处于安全状态？如果P1再提出请求1个A类，2个C类资源，是否该批准？进程调度与死锁2：假设一个系统有某类资源m个，被n个进程共享，进程每次只请求和释放一个资源，证明只要系统满足下面两个条件，就不会发生死锁：(1)每个进程需求资源的最大值在1到m之间；(2)所有进程需要资源的最大值的和小于m+n。证明：设每个进程最多申请资源x个（1≤x≤m），最坏情况下，为进程分配资源数为n（x-1）。系统剩余资源为m-n（x-1）。只要m-n（x-1）≥1；则系统不会出现死锁。整理得：nx≤m+n-1，所以nx≤m+n时，不会引起死锁进程调度与死锁3：和死锁1相同，系统的资源数量为：（10，5，7）。经过一段时间的分配后，资源分配与占用情况见下表所示。进程MAXABCAllocationABCNeedABCAvailableABCP0753010743332P1322200122P2902302600P3222211011P4433002431分析进程P0的请求(0,1,0)能否满足？进程调度与死锁4：假设系统有4个相容类型的资源被3个进程共享，每个进程最多需要2个资源，证明这个系统不会死锁。假设每个进程都需要2个资源，3个进程先每个进程分一个资源，共需3个资源，这时候只需要再有一个资源就能保证至少有一个进程能够执行，系统即不会死锁进程调度与死锁5：有三个进程P1、P2和P3并发工作。进程P1需要资源S3和S1；进程P2需用资源S1和S2；进程P3需用资源S2和S3，回答：(1)若对资源分配不加限制，会发生什么情况？为什么？(2)为保证进程正确地工作，应采用怎样的资源分配策略？为什么？1)若对进程间的资源分配不加限制，可能会发生死锁。若进程P1、P2和P3分别获得资源S3、S1和S2，后再继续申请资源时会导致进程间的“循环等待”，并且这种状态将永远持续下去。(2)为保证系统处于安全状态，应采用下面列举3种资源分配策略：1)采用静态资源分配：由于执行前已获得所需全部资源，故不会出现占有资源又等待资源的现象，从而避免资源的循环等待。2)采用资源按序分配，避免出现循环等待资源的现象。3)采用银行家算法进行分配资源前的检测。进程调度与死锁6：有5个任务A，B，C，D，E，它们几乎同时到达，预计它们的运行时间为10，6，2，4，8min。其优先级分别为3，5，2，1和4，这里5为最高优先级。对于下列每一种调度算法，计算其平均进程周转时间（进程切换开销可不考虑）。(1)先来先服务（按A，B，C，D，E）算法。(2)优先级调度算法。(3)时间片轮转算法。进程调度与死锁7：设某系统进程的状态有创建状态、运行状态、阻塞状态、延迟状态和完成状态。试画出系统的进程状态变迁图，并说明状态变迁可能的原因。进程调度与死锁8：一个计算机系统中拥有6台打印机，现有N个进程竞争使用，每个进程要求两台，试问，N的值如何选取时系统中绝对不会出现死锁？为什么？(三)内存管理内存管理1：在分页存储管理系统中，存取一次内存的时间是8us，查询一次快表的时间是1us，缺页中断的时间是20us，假设页表的查询与快表的查询同时进行。当查询页表时，如果该页在内存但快表中没有页表项，系统将自动把该页页表项送入快表。(1)求对某一数据进行一次次存取可能需要的时间？(2)现连续对同一页面上的数据进行4次连续读取，求每次读取数据可能需要的时间?内存管理2：若在一分页存储管理系统中，某作业的页表如下所示。已知页帧大小为1024字节，试将逻辑地址1011，2148，3000，5012转化为相应的物理地址（注：此处块号即为页帧号）。页号块号01232316内存管理3：假设一个请求分页系统具有一个平均访问和传输时间为20ms的分页磁盘。地址转换时通过在主存中的页表来进行的，每次内存访问时间为1s。为了提供性能，加入一个快表，当页表项在快表中，可以减少内存的访问次数。假设80%的访问发生在快表汇总，而且剩下中的10%会导致页错误，内存的有效访问时间是多少？（假设快表的查找时间可以忽略）内存管理4：假设有下面也引用序列1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6.LRU页面置换算法会导致多少次页错误？假设内存帧数分别为2,3,4内存管理5：有一计算机系统，内存容量为512K，辅存容量为2G，逻辑地址形式如下：段号段内地址2920190求其虚拟存储器的实际容量？内存管理6：有这样一种页面置换算法，它给每一个内存块(块与页大小相等)设置一个计数器，以计数曾经装入过该块的页面数。当需要置换一个页面时，该算法总是将其计数值最小的那个块内的页面换掉，当有多个最小值时，按FIFO执行。若某进程分得4个内存块，现对1、2、3、4、5、3、4、1、6、7、8、7、8、9、7、8、9、5、4、5、4、2，页面引用串，解答如下问题：(1)求在上述算法下的页面错误数；(2)求在最优置换算法下的页面错误数。(四)文件系统文件系统1：设想一个在磁盘上的文件系统的块大小为512B，假设每个文件的信息已经在内存中。对三种分配方法：连续分配、链接分配(假设链接指针占1个字节)和索引分配，假设文件的线性逻辑地址从0开始线性增长，分别回答下面的问题：(1)逻辑地址到物理盘块地址的映射是怎样进行的？(对于索引分配，假设文件总是小于512Blocks)(2)假设现在处于盘块10，现在想访问盘块4，那么必须从磁盘上读多少个物理块？文件系统2：在有些系统中，一个子目录可以被一个授权用户读和写，就像一个普通文件一样。(1)描述可能产生的文件保护问题。(2)给出你认为的保护处理方案。文件系统3：假定一个盘组共有100个柱面，每个柱面上有16个磁道，每个盘面分成4个扇区，问：(1)整个磁盘空间共有多少个存储块？(2)如果用字长为32位的单元来构造位示图，共需要多少个字？(3)位示图中第18个字的第16位对应的块号是多少？.（1）4*16*100＝6400（2）6400/32＝200（3）18*32+16＝592文件系统4：假设一个系统支持连续分配、连接分配和索引分配，应依据什么标准决定哪个方法最适合一个特定的文件？文件系统5：假定有一个磁盘组共有100个柱面，每个柱面有8个磁道，每个盘面划分成8个扇区。现有一个5000个逻辑记录的文件，逻辑记录的大小与扇区大小相等，该文件以顺序结构被存放在磁盘组上，柱面、磁道、扇区均从0开始编址，逻辑记录的编号从0开始，文件信息从0柱面、0磁道、0扇区开始存放。请问：(1)该文件的3468个逻辑记录应存放在哪个柱面的第几个磁道的第几个扇区上。(2)第56柱面上的第8磁道的第5扇区中存放的是该文件的第几个逻辑记录。（1）柱面号：3468/64＝54磁道号：（3468%64）/8＝1扇区号：（3468%64）％8＝4（2）56*64+8*8+5＝3652(五)I/O系统I/O系统1：假定在某移动臂磁盘上，刚刚处理了访问60号柱面的请求，目前正在73号柱面上读信息，并有下列请求序列等待访问磁盘：请求序列欲访问的柱面号：150、50、178、167、87、43、23、160、85。试用最短任务优先算法和电梯调度算法，分别排出实际上处理上述请求的次序。I/O系统2：I/O软件一般分为4个层次，用户层I/O软件、I/O内核子系统、设备驱动程序以及中断处理程序。请说明以下各工作是在哪一层完成的？(1)向设备寄存器写命令；(2)检查用户是否有权使用设备；(3)将二进制整数转换成ASCII码以便打印。I/O系统3：内核I/O子系统的功能职责是什么？系统采用什么方法来协调内核I/O组件的活动，它们各有什么优劣？I/O系统4：RAID的哪个级别使用奇偶校验来实现冗余？它们是如何恢复破坏的数据的？(六)概念复习1.当时引入多道程序的目的在于（C）。A.有利于代码共享，减少主、辅存信息交换量B．充分利用存储器C.充分利用CPU，减少CPU等待时间D．提高实时响应速度2.在单处理机计算机系统中，（B）是并行操作的。A.程序与程序B.处理机的操作与通道的操作C.主程序与子程序D.用户程序与操作系统程序3.当线程处于阻塞状态时，线程(B)。A.正在占用处理机B.没有占用处理机C.将进入执行状态D.将进入结束状态4.当多道程序系统中发生死锁时，（C）。1.计算机系统不能处理任何事情2.某个进程不能够执行3.一组进程相互等待，并进入阻塞状态4.不能进行输入和输出5.下面哪一个不是程序在并发系统内执行的特点（B）。A.产生死锁的必然性B.资源分配的动态性C.程序执行的间断性D.相互通信的可能性6.进程和程序的一个本质区别是(D)。A