操作系统题目共享

操作系统复习题选讲开篇说明题目是从程序设计团队群里下载下来的估计是08软件之前的复习题，但我也不确定因此大家自己看着复习，本人不负任何法律责任呵呵！•1、假设有一种低级调度算法是让“最近使用处理器较少的进程”运行，试解释这种算法对“I/O繁重”型作业有利，但并不是永远不受理“处理器繁重”型作业。•答：因为I/O繁忙型作业忙于I/O，所以它CPU用得少，按调度策略能优先执行。同样原因一个进程等待CPU足够久时，由于它是“最近使用处理器较少的进程”，就能被优先调度，故不会饥饿。•2、设有n个进程共享一个互斥段，如果：(1）每次只允许一个进程进入互斥段；(2）每次最多允许m个进程同时进入互斥段。试问：所采用的信号量初值是否相同？信号量值的变化范围如何？•答：所采用的互斥信号量初值不同。1）互斥信号量初值为1，变化范围为［-n＋l,1］。当没有进程进入互斥段时，信号量值为1；当有1个进程进入互斥段但没有进程等待进入互斥段时，信号量值为0；当有1个进程进入互斥段且有一个进程等待进入互斥段时，信号量值为-1；最多可能有n-1个进程等待进入互斥段，故此时信号量的值应为-（n-1）也就是-n+1。•2）互斥信号量初值为m，变化范围为［-n＋m,m］。当没有进程进入互斥段时，信号量值为m；当有1个进程进入互斥段但没有进程等待进入互斥段时，信号量值为m-1：当有m个进程进入互斥段且没有一个进程等待进入互斥段时，信号量值为0：当有m个进程进入互斥段且有一个进程等待进入互斥段时，信号量值为-1；最多可能有n-m个进程等待进入互斥段，故此时信号量的值应为-(n-m)也就是-n+m.•3、设公共汽车上，司机和售票员的活动分别如下：司机的活动：启动车辆：正常行车；到站停车。售票员的活动：关车门；售票；开车门。在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用信号量和P、V操作实现它们的同步。•答：在汽车行驶过程中，司机活动与售票员活动之间的同步关系为：售票员关车门后，向司机发开车信号，司机接到开车信号后启动车辆，在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开门让乘客上下车。因此，司机启动车辆的动作必须与售票员关车门的动作取得同步；售票员开车门的动作也必须与司机停车取得同步。应设置两个信号量：S1、S2;S1表示是否允许司机启动汽车（其初值为0);S2表示是否允许售票员开门（其初值为0）。•用P、v原语描述如下：•varS1,S2:semaphore;S1=0；S2=0；cobegin{driver();busman();}coend•driver()beginwhile(1){P(S1)启动车辆；正常行车；到站停车；V(S2);}endbusman()beginwhile(1){关车门；V(S1)售票;P(S2)开车门；上下乘客；}end•4、在信号量S上作P、v操作时，S的值发生变化，当S0、S=0、S0时，它们的的物理意义是什么？•答：S的值表示它代表的物理资源的使用状态：S0表示还有共享资源可供使用。S阅表示共享资源正被进程使用但没有进程等待使用资源。•S0表示资源已被分配完，还有进程等待使用资源。•5、试利用记录型信号量和P、V操作写出一个不会出现死锁的五个哲学家进餐问题的算法。•答：varforki:array[0…4]ofsemaphore;forki:=1;cobegin{processPi/*i=0,1,2,3*/beginL1:思考：P(fork[i]);/*i=4,P(fork[0])*/P(fork[i+1]mod5)/*i=4P（fork[4]）*/吃通心面；V(fork[i];V(fork([i+1]mod5);gotoL1;end;}coend;•6、系统有同类资源m个，被n个进程共享，问：当mn和m≤n时，每个进程最多可以请求多少个这类资源时，使系统一定不会发生死锁？•答：当m≤n时，每个进程最多请求1个这类资源时，系统一定不会发生死锁。当mn时，如果m/n不整除，每个进程最多可以请求“商＋1”个这类资源，否则为“商”个资源，系统一定不会发生死锁。•7、系统有A、B、C、D共4种资源，在某时刻进程P0、P1、P2、P3和P4对资源的占有和需求情况如表，试解答下列问题：系统此时处于安全状态吗？若此时P1发出request1(1、2、2、2)，系统能分配资源给它吗？为什么？•答：•(1）系统处于安全状态，存在安全序列：P0,P3,P4,P1,P2。(2）不能分配，否则系统会处于不安全状态。•8、某系统有R1设备3台，R2设备4台，它们被P1、P2、P3和P4进程共享，且己知这4个进程均按以下顺序使用设备：一申请R1一申请R2一申请R1一释放R1一释放R2一释放R1(1）系统运行中可能产生死锁吗？为什么？(2）若可能的话，请举出一种情况，并画出表示该死锁状态的进程一资源图．•答：1）系统四个进程需要使用的资源数为R1各2台，R2各1台。可见资源数不足，同时各进程申请资源在先，有可能产生死锁发生的四个条件，故系统可能产生死锁。•2）当三个进程执行完申请资源R1，开始执行申请资源R2时，第四个进程会因没有资源R1而被阻塞。当三个进程执行完申请资源R2后，系统还剩1个R2资源。而这三个进程因执行申请第二个资源R1而全部被阻塞，系统进入死锁。•9、某寺庙有小和尚和老和尚各若干人，水缸一只，由小和尚提水入缸给老和尚饮用。水缸可容水10桶，水取自同一口水井中。水井径窄，每次仅能容一只水桶取水，水桶总数为3个。若每次入、取水仅为1桶，而且不可同时进行。试用一种同步工具写出小和尚和老和尚入水、取水的活动过程。•互斥资源有水井和水缸，分别用mutex1和mutex2来互斥。水桶总数仅3只，由信号量count控制，信号量empty和full控制入水和出水量。varmutex1,mutex2:semaphore;empty，full:semaphore;count:integer;mutex1:mutex2:=1;count:=3;empty:=10；full：=0;•cobegin{process小和尚（打水）i(i=1,2，…）beginrepeatP(empty);/＊水缸满否？P(count);/＊取得水桶P(mutexl);/＊互斥从井中取水从井中取水；V(mutex1);P(mutex2);/＊互斥使用水缸倒水入缸；V(mutex2);V(count);/＊归还水桶v(full);/＊多了一桶水untilefalse;end•process老和尚（取水）j(j=1,2，…）beginrepeatP(full);/＊有水吗？P(count);/＊申请水桶P(inutex2);/＊互斥取水从缸中取水；V(mutex2);V(count);/＊归还水桶V(empty);/＊水缸中少了一桶水untilefalse;end}coend.•10、一个UNIX/Linux文件，如果一个盘块的大小为1KB，每个盘块占4个字节，那么，若进程欲访问偏移为263168字节处的数据，需经过几次间接寻址？•UNIX/Linux文件系统中，直接寻址为10块，一次间接寻址为256块，二次间接寻址为2562三次间接寻址为2563块。偏移为263168字节的逻辑块号是：263168/1024==257．块内偏移量＝263168-257*l024=0。由于10257256+10，故263168字节在一次间接寻址内．•11、试说明在UNIX缓冲管理算法中，极为精确的最久未使用淘汰算法(LRU)是如何实现的？•（1）UNIX的缓冲管理算法很有特色，它以极简单的办法实现了极为精确的最久未使用淘汰算法。当一个缓冲区被送入空闲缓冲区队尾时，它还是保留在该设备的缓冲区队列上。当需要一个缓冲区时，总是从空闲缓冲区队列中取第一个元素，而一个被使用过的缓冲区释放时放在队尾。•（2）当核心从空闲缓冲区不断地摘下缓冲区时，一个装有有效数据的缓冲区会越来越近的移动到空闲队列头部。因此，离队列头近的缓冲区与离队列头远的缓冲区相比，前者是最久未使用的，这正是LRU算法。•12、某系统有输入机和打印机各一台，今有两个进程都要同时使用它们，如果采用P、V操作来实现请求使用和归还释放，试问还会产生死锁吗？若不会，请说明理由；若会产生死锁，请给出一种防止死锁的方法。•如果P、V操作设计不当，还会产生死锁，如下所示，依然会产生死锁。•intS1=1,S2=1;//分别控制输入机和打印机的使用•A1()•{P(S1);•使用输入机；•P(S2);•使用打印机；•V(S2);•V(S1);•}•A2()•{P(S2);•使用打印机；•P(S1);•使用输入机；•V(S2);•V(S1);•}•可以采用给资源编序号，按序申请，则不会产生死锁。•A1()•{P(S1);•使用输入机；•P(S2);•使用打印机；•V(S2);•V(S1);•}•A2()•{P(S1);•使用输入机；•P(S2);•使用打印机；•V(S2);•V(S1);•}•13、某车站售票厅，任何时刻最多可容纳30名购票者进入，当售票厅中少于30名购票者时，则厅外的购票者立即可进入，否则需在外面等待。若把一个购票者看作一个进程，请给出使进程正确并发执行的算法。若购票者最多为M个人，请写出算法中信号量可能的变化范围。•定义信号量S，初值为30。S0表示可以继续进入售票厅人数；S＝0表示厅内人数已满；S0，|S|表示等待人数。•cobegin•P(S);•进入大厅；•购票；•退出；•V(S);•coend•经过分析，信号量的变化范围为：30-M=S=30•14、设某文件A有10个逻辑记录（R0－R9，逻辑记录大小与物理块大小相等，都为512KB）。要求用连续文件、串联文件和索引文件结构来构造。回答以下问题：•分别画出这三种文件的物理结构图（物理块号由考生确定）。•当文件A打开后，要随机读取R9记录，在这三种结构下各需多少次磁盘I/O操作（分别加以说明）？•连续文件：通过计算可得R9记录所在磁盘块号，读1次。•串连文件：从R0到R8依次读记录所在磁盘块号，得指针，最后得到R9记录所在磁盘块号，共读10次。•索引文件：因为索引表已在内存，可查得R9记录所在磁盘块号，共读1次。•15、某系统采用分页存储管理方式，拥有逻辑空间32页，每页2KB，拥有物理空间1MB。•写出逻辑地址格式。•若不考虑访问权限等，进程的页表项有多少项？每项至少有多少位？•逻辑空间32页，故逻辑地址中页号5位，每页2KB，故页内地址用11位表示。•因为有32页，所以有32项；不考虑访问权限，页表中只需要给出物理块号，又因为物理空间1MB，所以需要每项9位。•16、有一个仓库，可以存放X和Y两种产品，仓库的存储空间足够大，要求（1）每次只能存入一种产品（X或Y）；（2）-N（X产品的数量-Y产品的数量）M。其中，N和M为正整数。试用“存放X”、“存放Y”和P，V操作描述产品X和Y的入库过程•设三个信号灯，•Intmutex=1,sa=m-1,sb=n-1;2分•Cobegin•L:getproductx;•If(x==X)4分•{P(sa);•P(mutex);•存放X;•V(mutex);•V(sb);•}•Elseif(x==Y)4分•{P(sb);•P(mutex);•存放Y;•V(mutex);•V(sa);•}•GotoL;•Coend•17、在分页虚拟存储管理系统中，假定系统为某进程分配了四个主存块（将开始4页先装入主存），页的引用顺序为：7，1，2，0，3，0，4，2，3，0，3，2，7，0，1，若采用FIFO调度算法、LRU调度算法时分别产生多少次缺页中断？依次淘汰的页是什么？•18、存放在某个磁盘上的文件系统采用混合索引分配方式，其FCB中共有13个地址项，第0－9个地址项为直接地址，第10个地址项为一次间接地址，第11个地址项为二次间接地址，第12个地址项为三次间接地址。如果每个盘块的大小为512