操作系统题目共享.ppt

《操作系统题目共享.ppt》由会员分享，可在线阅读，更多相关《操作系统题目共享.ppt（41页珍藏版）》请在优知文库上搜索。

1、操作系统复习题选讲操作系统复习题选讲开篇说明 题目是从程序设计团队群里下载下来的估计是08软件之前的复习题，但我也不确定因此大家自己看着复习，本人不负任何法律责任呵呵！ 1、假设有一种低级调度算法是让“最近使用处理器较少的进程”运行，试解释这种算法对“I/O 繁重”型作业有利，但并不是永远不受理“处理器繁重”型作业。 答：因为I/O繁忙型作业忙于I/O，所以它CPU 用得少，按调度策略能优先执行。同样原因一个进程等待CPU 足够久时，由于它是“最近使用处理器较少的进程”，就能被优先调度，故不会饥饿。 2、设有n 个进程共享一个互斥段，如果：( 1 ）每次只允许一个进程进入互斥段；( 2 ）每次

2、最多允许m 个进程同时进入互斥段。试问：所采用的信号量初值是否相同？信号量值的变化范围如何？答：所采用的互斥信号量初值不同。1 ）互斥信号量初值为1 ，变化范围为-nl , 1 。当没有进程进入互斥段时，信号量值为1 ；当有1 个进程进入互斥段但没有进程等待进入互斥段时，信号量值为0 ；当有1 个进程进入互斥段且有一个进程等待进入互斥段时，信号量值为-1 ；最多可能有n -1 个进程等待进入互斥段，故此时信号量的值应为-（n - 1 ）也就是-n+1 。 2 ）互斥信号量初值为m ，变化范围为-nm , m 。当没有进程进入互斥段时，信号量值为m ；当有1 个进程进入互斥段但没有进程等待进入互

3、斥段时，信号量值为m - 1 ：当有m 个进程进入互斥段且没有一个进程等待进入互斥段时，信号量值为0 ：当有m 个进程进入互斥段且有一个进程等待进入互斥段时，信号量值为- 1 ；最多可能有n - m 个进程等待进入互斥段，故此时信号量的值应为-(n-m)也就是-n+m. 3、设公共汽车上，司机和售票员的活动分别如下：司机的活动：启动车辆：正常行车；到站停车。售票员的活动：关车门；售票；开车门。在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用信号量和P 、V 操作实现它们的同步。 答：在汽车行驶过程中，司机活动与售票员活动之间的同步关系为：售票员关车门后，向司机发开车信号，司机接

4、到开车信号后启动车辆，在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开门让乘客上下车。因此，司机启动车辆的动作必须与售票员关车门的动作取得同步；售票员开车门的动作也必须与司机停车取得同步。应设置两个信号量：S1 、S2 ;S1 表示是否允许司机启动汽车（其初值为0 ) ;S2 表示是否允许售票员开门（其初值为0 ）。 用P 、v 原语描述如下： var S1 , S2 : semaphore ; S1=0；S2=0；cobegin driver ( ) ; busman ( ) ; coend driver ( ) begin while ( 1 ) P ( S1 )启动车辆；

5、正常行车；到站停车； V ( S2 ) ; end busman ( ) begin while ( 1 ) 关车门； V ( S1 ) 售票; P ( S2 ) 开车门； 上下乘客； end 4、在信号量S上作P 、v 操作时，S的值发生变化，当S 0、S=0、S 0 表示还有共享资源可供使用。S 阅表示共享资源正被进程使用但没有进程等待使用资源。 S n 和mn 时，每个进程最多可以请求多少个这类资源时，使系统一定不会发生死锁？ 答：当mn 时，每个进程最多请求1 个这类资源时，系统一定不会发生死锁。当m n 时，如果m/n 不整除，每个进程最多可以请求“商1 ”个这类资源，否则为“商”个

6、资源，系统一定不会发生死锁 。 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 一申

7、请R1一释放R1 一释放R2 一释放R1 ( 1 ）系统运行中可能产生死锁吗？为什么？( 2 ）若可能的话，请举出一种情况，并画出表示该死锁状态的进程一资源图 答： 1）系统四个进程需要使用的资源数为R1 各2 台，R2 各1 台。可见资源数不足，同时各进程申请资源在先，有可能产生死锁发生的四个条件，故系统可能产生死锁。 2 ）当三个进程执行完申请资源R1 ，开始执行申请资源R2 时，第四个进程会因没有资源R1 而被阻塞。当三个进程执行完申请资源R2 后，系统还剩1 个R2 资源。而这三个进程因执行申请第二个资源R1 而全部被阻塞，系统进入死锁。 9、某寺庙有小和尚和老和尚各若干人，水缸一只，

8、由小和尚提水入缸给老和尚饮用。水缸可容水10 桶，水取自同一口水井中。水井径窄，每次仅能容一只水桶取水，水桶总数为3 个。若每次入、取水仅为1 桶，而且不可同时进行。试用一种同步工具写出小和尚和老和尚入水、取水的活动过程。 互斥资源有水井和水缸，分别用mutex1和mutex2来互斥。水桶总数仅3 只，由信号量count 控制，信号量empty 和full 控制入水和出水量。var mutex1 , mutex2 : semaphore ; empty ，full : semaphore ; count : integer ; mutex1 : mutex2 : = 1 ; count : =

9、 3 ; empty : = 10 ；full ：=0 ; cobegin process 小和尚（打水）i ( i = 1 , 2 ， ）begin repeat P ( e mpty ) ; / 水缸满否？P ( count ) ; / 取得水桶P ( mutexl ) ; / 互斥从井中取水从井中取水；V ( mutex1) ; P ( mutex2) ; / 互斥使用水缸倒水入缸；V ( mutex2 ) ; V ( count ) ; / 归还水桶v ( full ) ; / 多了一桶水untile false ; end process 老和尚（取水）j(j=1 , 2 ， ）be

10、gin repeat P ( full ) ; / 有水吗？P ( count ) ; / 申请水桶P ( inutex2 ) ; / 互斥取水从缸中取水；V ( mutex2 ) ; V ( count ) ; / 归还水桶V ( empty ) ; / 水缸中少了一桶水untile false ; end coend . 10、一个UNIX/Linux 文件，如果一个盘块的大小为1KB ，每个盘块占4 个字节，那么，若进程欲访问偏移为263 168 字节处的数据，需经过几次间接寻址？ UNIX /Linux 文件系统中，直接寻址为10 块，一次间接寻址为256 块，二次间接寻址为2562三

11、次间接寻址为2563 块。 偏移为263 168 字节的逻辑块号是：263168 / 1024 = = 257 块内偏移量263168 -257*l024 = 0 。由于10 257 0表示可以继续进入售票厅人数；S0表示厅内人数已满；S0，|S|表示等待人数。 cobegin P(S); 进入大厅； 购票； 退出； V(S); coend 经过分析，信号量的变化范围为：30-M=S=30 14、设某文件A有10个逻辑记录（R0R9，逻辑记录大小与物理块大小相等，都为512KB）。要求用连续文件、串联文件和索引文件结构来构造。回答以下问题： 分别画出这三种文件的物理结构图（物理块号由考生确定）

12、。 当文件A打开后，要随机读取R9记录，在这三种结构下各需多少次磁盘I/O操作（分别加以说明）？ 连续文件：通过计算可得R9记录所在磁盘块号，读1次。 串连文件：从R0到 R8依次读记录所在磁盘块号，得指针，最后得到R9记录所在磁盘块号，共读10次。 索引文件：因为索引表已在内存，可查得R9记录所在磁盘块号，共读1次。 15、某系统采用分页存储管理方式，拥有逻辑空间32页，每页2KB，拥有物理空间1MB。 写出逻辑地址格式。 若不考虑访问权限等，进程的页表项有多少项？每项至少有多少位？ 逻辑空间32页，故逻辑地址中页号5位，每页2KB， 故页内地址用11位表示。 因为有32页，所以有32项；不

13、考虑访问权限，页表中只需要给出物理块号，又因为物理空间1MB，所以需要每项9位。 16、有一个仓库，可以存放X和Y两种产品，仓库的存储空间足够大，要求（1）每次只能存入一种产品（X或Y）；（2）-N（X产品的数量-Y产品的数量）M。其中，N和 M为正整数。试用“存放X”、“存放Y”和P，V操作描述产品X和Y的入库过程 设三个信号灯，Int mutex=1, sa=m-1, sb=n-1; 2分Cobegin L: get product x; If(x=X) 4分 P(sa); P(mutex); 存放X; V(mutex); V(sb);Else if(x=Y) 4分 P(sb); P(mu

14、tex); 存放Y; V(mutex); V(sa);Goto L;Coend 17、在分页虚拟存储管理系统中，假定系统为某进程分配了四个主存块（将开始4页先装入主存），页的引用顺序为：7，1，2，0，3，0，4，2，3，0，3，2，7，0，1，若采用FIFO调度算法、LRU调度算法时分别产生多少次缺页中断？依次淘汰的页是什么？ 18、存放在某个磁盘上的文件系统采用混合索存放在某个磁盘上的文件系统采用混合索引分配方式，其引分配方式，其FCB中共有中共有13个地址项，第个地址项，第09个地址项为直接地址，第个地址项为直接地址，第10个地址项为一次间个地址项为一次间接地址，第接地址，第11个地址项

15、为二次间接地址，第个地址项为二次间接地址，第12个地址项为三次间接地址。如果每个盘块的大个地址项为三次间接地址。如果每个盘块的大小为小为512字节，且盘块号需要用字节，且盘块号需要用3个字节来描述个字节来描述，而每个盘块最多存放，而每个盘块最多存放170个盘块地址，则：个盘块地址，则： （1）该文件系统允许文件的最大长度是多少？）该文件系统允许文件的最大长度是多少？ （2）假设某个文件的）假设某个文件的FCB已在内存，但其他信已在内存，但其他信息均在外存，为了访问该文件中某个位置的内息均在外存，为了访问该文件中某个位置的内容，最少需要几次访问磁盘？最多需要几次访容，最少需要几次访问磁盘？最多需

16、要几次访问磁盘？问磁盘？ （1）该文件系统中一个文件的最大长度可达： 101701701701701701704942080块4942080512B2471040KB （2）最少需要1次访问磁盘（通过直接地址直接读文件盘块），最多需要4次访问磁盘（分别读三次间接块、二次间接块、一次间接块、文件盘块）。 19、一组合作进程，执行顺序如图所示一组合作进程，执行顺序如图所示，请用，请用P，V操作原语实现各进程的同步操作原语实现各进程的同步操作操作 关于LRU和LFU LRU：最久未使用淘汰算法。选择最长时间未被使用的那一页淘汰。从时间长短上来考察。 LFU：最不经常使用淘汰算法。选择最近使用次数最少的页面淘汰。从使用次数上考察。 两者选择淘汰的页面不一定相同。