的物理块数M分别为3和4（且初始均为空）时，分别采用FIFO置换法和OPT置换法求缺页中断率，并比较得到的结果。（此类题要注意初始时，内存块是否为空？还是预先调入若干页。） 答案：（1）FIFO法(M=3):
注意：若初始时，预先调入4，3，2页，则前3次不缺页。（视具体调入的页号与访问序列而定）
（2）OPT法：(M=3)
（3）OPT法：m=3时，缺页中断7次，m=4时，缺页中断6次，可见，增加分配给作业
的内存块数，可降低缺页率。
FIFO法：m=3时，缺页中断9次，m=4时，缺页中断10次，可见，增加分配给作
业的内存块数，反而提高了缺页率。
FIFO页面淘汰算法会产生异常现象，对特定的访问序列，当分配给进程的物理页面数增加时，缺页次数反而也增加。称为Belady异常。
注：如何判断一个页是否在内存---根据扩充页表的状态位P。
可以计算每种算法下调页耗费的时间：次数*每页调入的时间。
6、 磁盘调度算法(FCFS/SSTF/SCAN/CSCAN 先来先服务/最短寻道时间优先/扫描算法/循环
扫描)
某一磁盘先后有4个进程提出了磁盘访问请求，按申请到达的先后顺序依次为：43，66，
26，88。系统中磁头停留在磁道号为68的磁道上，且移动臂正沿磁道号递减的方向移动。求出分别采用FCFS、SSTF和SCAN磁盘调度算法时，磁道的访问顺序及其所需寻道长度（走过多少柱面）。(会描述对应的算法思想) 答：1）FCFS磁盘调度算法：
顺序：43，66，26，88 寻道长度：（68-43）+（66-43）+（66-26）+（88-26）=150
2）SSTF算法：
顺序：66，88，43，26 寻道长度：（68-66）+（88-66）+（88-43）+（43-26）=86 3）SCAN算法：
顺序：66，43，26，88 寻道长度：（68-66）+（66-43）+（43-26）+（88-26）=104
7、 外存分配（显示连接 FAT/NTFS 索引分配）
(a)索引分配:存放在某个磁盘上的文件系统,采用混合索引分配方式(13个地址项,同UNIX系统的i结点结构),若每个盘块大小为512字节,磁盘块需用3个字节描述,则: 1)该文件系统允许文件的最大长度是多少?
析：512／3＝170余2，每个盘块最多存放170个盘块地址，所以索引表中表项最多
170个。文件限制最大长度（10＋170＋170^2＋170^3）块＊512字节＝2471040KB 2）将文件的字节偏移量5000，15000，150000转换为物理块号和块内偏移量。 析：5000／512＝9余392，所以字节偏移量5000对应逻辑块号为9（从0开始算的），块内偏移量为392，由于9<10，故可以直接从文件的FCB 的第9个地址项处得到物理盘块号，块内偏移量为392。
15000／512＝29余152，所以字节偏移量15000对应逻辑块号为29（从0开始算的），块内偏移量为1592，由于10<=29<10+170，而29-10=19，故可以直接从文件的FCB 的第10个地址项处得到一次间址块的地址，并从次间址块的第19项（即该块的第57~59这3个字节处）中获得对应得物理盘块号，块内偏移量为152。 （有关150000，略）
3)假定某文件的FCB已在内存,但其它信息均在外存，试分析:为访问该文件中某个位置的内容,最少需要几次启动磁盘?最多需要几次启动磁盘?
析：由于文件的FCB已在内存，为访问文件中的某个位置，最少需要1次启动磁盘（直
接地址）；最多需要4次启动磁盘（三次间址）。
注：若文件所有信息均在外存？则查找FCB操作也要算一次启盘。故最少需要2
次启动磁盘（直接地址）；最多需要5次启动磁盘（三次间址）。
(b)某文件系统中，如果磁盘容量为12GB，盘块大小为4KB，采用显式链接分配方式时，问：
（1）每个FAT表项需占几个字节（FAT表项的长度取字节的整数倍）？ 答：盘块数=12G/4KB=3M=3KKB每个FAT表项需占3个字节 （2）其FAT需占用多少存储空间？ 答：FAT需占用3B*3M=9MB
（3）如果文件A依次占用3、5、7号三个盘块，画出A中各盘块间的链接情况及FAT的情况。
P217页图（超简单必看）
8、 位示图法
某计算机系统采用位示图法（行号、列号和盘块号都从1开始编号）来管理文件存储空
间,且0表示盘块空闲。对于32MB的磁盘，每个盘块的大小为1KB，试具体说明如何为某文件分配一个盘块？（回收？）该系统的位示图容量有多大？（注意：行号、列号也可以从0开始）
答：为某文件分配一个盘块的过程如下：
1）顺序检索位示图，从中找到一个值为0的二进制位。 2）设行号i列号j，计算出相应的盘块号b为：b＝n×(i-1)+j 3）修改位示图，令Map[i，j]＝1，并将对应块分配给该文件。 位示图容量为：32MB/（1KB*8）=4KB
注：对具体的盘块号b，要会计算出具体的i和j
由于寝室马上要熄灯 今天的资料先写到这里 明天看看有改动带崽改 感谢辛苦带2418工作室 呵呵！
四、综合题（12分）
、操作系统在键盘管理中引入了键盘缓冲区，键盘缓冲区采用循环队列，键盘输入进程pin负责将用户键入的字符存入缓冲区，键盘输出进程pout负责从缓冲区取出字符。假设循环队列的长度为16，请给出利用信号量机制实现进程pin、pout同步及互斥使用键盘缓冲区的算法。要求：
（1）定义所使用的信号量，给出信号量的初值、含义。
（2）给出进程pin、pout的算法（用伪代码给出，不必给出循环队列操作代码）。 答：semaphore mutex=1 //互斥使用键盘缓冲区
semaphore empty=16 // 开始时键盘缓冲区为空的信号量为16 semaphore full=0 // 开始时键盘缓冲区为满的信号量为0 char buffer[16] // 键盘缓冲区 pin() {while(1)
{从键盘得到一个输入字符 wait(empty) wait(mutex) 将该字符存入buffer signal(mutex) signal(full) }}
pout() {while(1)
{wait(full) wait(mutex) 从buffer中取出一个字符 signal(mutex) signal(empty) }}
相关推荐：
loading