计算机操作系统尚未解决的问题

1、1/13有有4个并发进程个并发进程P1、P2、P3、P4，它们之间的关系如图所示，试用它们之间的关系如图所示，试用P、V操作描述它们之间的制约关系。操作描述它们之间的制约关系。P1P2P3P4P1P2P3P4s12s13s24s34Sij：进程：进程i对进程对进程j的控制信号量的控制信号量 (i=1,2,3，j=2,3,4)Begin P1; V(s12); V(s13); End;Begin P(s12); P2; V(s24); End;Begin P(s13); P3; V(s34); End;Begin P(s24); P(s34); P4; End;2/13设设A、B两个进程公用一两

2、个进程公用一个缓冲区个缓冲区Q，A向向Q写入写入信息，信息，B从从Q读出信息，读出信息，算法框图如图所示，判算法框图如图所示，判断其正确否。若有错，断其正确否。若有错，指出原因并予以改正。指出原因并予以改正。向向Q写入信息写入信息V(s)P(s)从从Q读出信息读出信息进程进程A 进程进程B 进程进程A向向Q写入信息前未测试，一方面会导致进写入信息前未测试，一方面会导致进程程B尚未取出信息前重复写，另一方面会破坏尚未取出信息前重复写，另一方面会破坏临界资源临界资源Q的互斥操作。的互斥操作。设置两个信号量设置两个信号量s1、s2，代表代表Q的空、满状态，的空、满状态，初始初始s1=1，s2=0A：

3、P(s1); 向向Q写写; V(s2);B：P(s2); 从从Q读读; V(s1);beginend3/13例题例题请求分页管理系统中，假设某进程的页表内容如下表所示：请求分页管理系统中，假设某进程的页表内容如下表所示：页号页号页框页框(page frame)号号有效位有效位(存在位存在位)0101H11-02254H1页面大小为页面大小为4KB，一次内存的访问时间是，一次内存的访问时间是100ns，一次快表（，一次快表（TLB）的访）的访问时间是问时间是10ns，处理一次缺页的平均时间为，处理一次缺页的平均时间为108ns（已含更新（已含更新TLB和页表和页表的时间），进程的驻留集大小固定为

4、的时间），进程的驻留集大小固定为2，采用最近最少使用置换算法，采用最近最少使用置换算法（LRU）和局部淘汰策略。假设，）和局部淘汰策略。假设，TLB初始为空；初始为空；地址转换时先访地址转换时先访问问TLB，若，若TLB未命中，再访问页表（忽略访问页表之后的未命中，再访问页表（忽略访问页表之后的TLB更新时更新时间）；间）；有效位为有效位为0表示页表不在内存，产生缺页中断，缺页中断处理后，表示页表不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H、1565H、25A5H，请问：，请问：(

5、1) 依次访问上述三个虚地址，各需要多少时间，给出计算过程；依次访问上述三个虚地址，各需要多少时间，给出计算过程；(2) 基于上述访问序列，虚地址基于上述访问序列，虚地址1565H的物理地址是多少？请说明理由。的物理地址是多少？请说明理由。4/13例题例题页面大小为页面大小为4KB，所以，所以2362H、1565H、25A5H对应的页号对应的页号分别为分别为2、1、2， 根据页表内容，根据页表内容，2362H、25A5H在内存，在内存， 1565H不在内存。初始快表为空，故不在内存。初始快表为空，故2362H需装入快表，需装入快表， 25A5H直接访问快表，直接访问快表， 1565H需装入内存

6、，再装入快表。需装入内存，再装入快表。据此：据此： 2362H：10(访访TLB)+100(访页表访页表)+100(访主存单元访主存单元)=210ns 1565H：10 (访访TLB)+100 (访页表访页表)+108 (调页调页)+10 (访访TLB) +100(访主存单元访主存单元)=100000220ns 25A5H： 10(访访TLB)+100(访主存单元访主存单元)=110ns根据页表，第根据页表，第0、2页在内存中，由于第页在内存中，由于第2页刚刚被访问（访页刚刚被访问（访问问2362H），根据），根据LRU算法，将第算法，将第0页替换，因此对应页框页替换，因此对应页框号为号为10

7、1H，故，故1565H的物理地址为的物理地址为101565H。5/13例题例题在一采取局部置换策略的请求分页系统中，分配给某个作在一采取局部置换策略的请求分页系统中，分配给某个作业的内存块数为业的内存块数为4，其中存放的，其中存放的4个页面的情况如表所示：个页面的情况如表所示：物理块物理块 虚页号虚页号 装入时间装入时间最后一次访问时间最后一次访问时间访问位访问位 修改位修改位 0 2 60 157 0 1 1 1 160 161 1 0 2 0 26 158 0 0 3 3 20 163 1 1上面所有时间均是从进程开始运行时从上面所有时间均是从进程开始运行时从0开始计时的时钟数，开始计时的

8、时钟数，如果系统采用：如果系统采用：(1) FIFO算法；算法；(2) LRU算法；算法；(3) 改进的改进的Clock算法，将选择哪一页换出？算法，将选择哪一页换出？ (1) 物理物理3、虚拟、虚拟3 (2) 物理物理0、虚拟、虚拟2 (3) 物理物理2、虚拟、虚拟06/13例题例题设某计算机的逻辑地址设某计算机的逻辑地址空间和物理地址空间均空间和物理地址空间均为为64KB，按字节编址。，按字节编址。若进程最多需要若进程最多需要6页存储页存储空间，页的大小为空间，页的大小为1KB，操作系统若采用固定分操作系统若采用固定分配局部置换策略为次进配局部置换策略为次进程分配程分配4个页面。在时刻个页

9、面。在时刻260前的该进程访问情况前的该进程访问情况如表所示（访问位即使如表所示（访问位即使用位）用位）页号页号页面号页面号装入时间装入时间访问位访问位071301142301222001391601当该进程执行到时刻当该进程执行到时刻260时，要时，要访问逻辑地址为访问逻辑地址为17CAH的数据，的数据，请回答：请回答：1、逻辑地址对应的页号是多少、逻辑地址对应的页号是多少2、若采用先进先出置换算法，、若采用先进先出置换算法，该逻辑地址对应的物理地址是该逻辑地址对应的物理地址是多少？给出计算过程。多少？给出计算过程。1、5 2、1FCAH000101 1111001010 B000111 1

10、111001010 B7/13例题例题设某计算机的逻辑地址设某计算机的逻辑地址空间和物理地址空间均空间和物理地址空间均为为64KB，按字节编址。，按字节编址。若进程最多需要若进程最多需要6页存储页存储空间，页的大小为空间，页的大小为1KB，操作系统若采用固定分操作系统若采用固定分配局部置换策略为次进配局部置换策略为次进程分配程分配4个页面。在时刻个页面。在时刻260前的该进程访问情况前的该进程访问情况如表所示（访问位即使如表所示（访问位即使用位）用位）页号页号页面号页面号装入时间装入时间访问位访问位0713011423012220013916013、若采用时钟置换算法，该逻、若采用时钟置换算法

11、，该逻辑地址对应的物理地址是多少？辑地址对应的物理地址是多少？给出计算过程。设顺时针搜索给出计算过程。设顺时针搜索下一页，且当前指向下一页，且当前指向2号页面，号页面，示意图如下。示意图如下。2号页号页3号页号页1号页号页0号页号页2号页面号页面9号页面号页面4号页面号页面7号页面号页面000101 1111001010 B000010 1111001010 B3、0BCAH8/13某请求分页系统的局部页面值环策略如下：某请求分页系统的局部页面值环策略如下：系统从系统从0时刻开始扫时刻开始扫描，每隔描，每隔5个时间单位扫描一轮驻留集（扫描时间忽略不计），个时间单位扫描一轮驻留集（扫描时间忽略不

12、计），本轮没有被访问过的页框将被系统回收，并放入空闲页框链尾，本轮没有被访问过的页框将被系统回收，并放入空闲页框链尾，其中内容在下一次被分配之前不被清空。当发生缺页时，如果该其中内容在下一次被分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页框链表中，则重新放回进程的驻留集页曾被使用过且还在空闲页框链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。中；否则，从空闲页框链表头部取出一个页框。假设不考虑其他进程的影响和系统开销，初始时进程驻留集为空。假设不考虑其他进程的影响和系统开销，初始时进程驻留集为空。目前空闲页框链表中页框号依次为目前空闲页框链表中页框号依次

13、为32、15、21、41。进程。进程P依次依次访问的访问的是：是：、 、 、 、 、 、。请回答下列问题。请回答下列问题。1) 访问访问时，对应的页框号是多少？时，对应的页框号是多少？2) 访问访问时，对应时，对应的页框号是多少？说明理由。的页框号是多少？说明理由。3) 访问访问时，对应的页框号是时，对应的页框号是多少？说明理由。多少？说明理由。4) 该策略是否适合于时间局部性能好的程序？该策略是否适合于时间局部性能好的程序？说明理由。说明理由。9/13 思考：思考：空闲页框链表：空闲页框链表：32、15、21、41访问序列：访问序列： 、 、 、 、 、 、 ：空闲页框链表：空闲页框链表：1

14、5、21、41；驻留集：；驻留集：32:1 ：空闲页框链表：空闲页框链表：21、41；驻留集：；驻留集：32:1, 15:3 ：空闲页框链表：空闲页框链表：41；驻留集：；驻留集：32:1, 15:3, 21:0时刻时刻5（扫描）：空闲页框链表：（扫描）：空闲页框链表：41；驻留集：；驻留集：32:1, 15:3, 21:0 ：空闲页框链表：空闲页框链表：41；驻留集：；驻留集：32:1, 15:3, 21:0时刻时刻10 （扫描）（扫描） ：空闲页框链表：空闲页框链表：41, 32:1, 15:3 ；驻留集：；驻留集：21:0 ：空闲页框链表：空闲页框链表：41, 15:3 ；驻留集：；驻留

15、集：21:0, 32:1 ：空闲页框链表：空闲页框链表：41, 15:3 ；驻留集：；驻留集：21:0, 32:1 ：空闲页框链表：空闲页框链表：15:3 ；驻留集：；驻留集：21:0, 32:1, 41:210/131) 访问访问时，对应的页框号是多少？时，对应的页框号是多少？2) 访问访问时，时，对应的页框号是多少？说明理由。对应的页框号是多少？说明理由。3) 访问访问时，对应的时，对应的页框号是多少？说明理由。页框号是多少？说明理由。4) 该策略是否适合于时间局部该策略是否适合于时间局部性能好的程序？说明理由。性能好的程序？说明理由。 ：空闲页框链表：空闲页框链表：15、21、41；驻留

16、集：；驻留集：32:1 ：空闲页框链表：空闲页框链表：21、41；驻留集：；驻留集：32:1, 15:3 ：空闲页框链表：空闲页框链表：41；驻留集：；驻留集：32:1, 15:3, 21:0 ：空闲页框链表：空闲页框链表：41；驻留集：；驻留集：32:1, 15:3, 21:0 ：空闲页框链表：空闲页框链表：41, 15:3 ；驻留集：；驻留集：21:0, 32:1 ：空闲页框链表：空闲页框链表：41, 15:3 ；驻留集：；驻留集：21:0, 32:1 ：空闲页框链表：空闲页框链表：15:3 ；驻留集：；驻留集：21:0, 32:1, 41:211/13答案答案1) 页框号为页框号为21（

17、1分）分）2) 页框号为页框号为32（1分）；理由：因分）；理由：因1110故发生第三轮故发生第三轮扫描，页号为扫描，页号为1的页框在第二轮已处于空闲链表中，的页框在第二轮已处于空闲链表中，此刻该页又被重新访问，因此应被重新放回驻留集此刻该页又被重新访问，因此应被重新放回驻留集中，其页框号为中，其页框号为32（1分）分）3) 页框号为页框号为41（1分）；理由：因第分）；理由：因第2页从来没被访问页从来没被访问过，它不再驻留集中，因此从空闲页框链表中取出过，它不再驻留集中，因此从空闲页框链表中取出链表头的页框链表头的页框41，页框号为，页框号为41（1分）分）4)适合（适合（1分）；理由：如果

18、程序的时间局部性能越分）；理由：如果程序的时间局部性能越好，从空闲页框表中重新取回的机会越大，该策略好，从空闲页框表中重新取回的机会越大，该策略的优势越明显。的优势越明显。12/13某文件系统空间的最大容量为某文件系统空间的最大容量为4TB（1T=240），），以磁盘块为基本分配单位，磁盘块大小为以磁盘块为基本分配单位，磁盘块大小为1KB。文件控制块（文件控制块（FCB）包含一个）包含一个512B的索引表区。的索引表区。请回答下列问题。请回答下列问题。(1) 假设索引表区仅采用直接索引结构，索引表区存放假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号。索引表中块号最少占多少字节？文件占用的磁盘块号。索引表中块号最少占多少字节？可支持的单个文件最大长度是多少？可支持的单个文件最大长度是多少？(2) 假设索引表区采用如下结构：第假设索引表区采用如下结构：第07字节采用字节采用格式表示文件创建时预分配的连续存储空间，格式表示文件创建时预分配的连续存储空间，其中起始块号占其中起始块号占6B