仅适用于广工学生，其实同类型题型多找些题目做，直到完全明白如何解题基本考试就没啥问题了
目录第二章进程信号量第三章处理机调度和死锁进程调度轮换算法短作业优先作业调度算法第四章存储器管理分页存储管理求页大小和页表求起始地址（16/10）求逻辑地址转内存地址分段存储管理第五章虚拟存储器页面置换算法缺页率/缺页中断率第七章文件管理插入记录多级索引组织方式字节偏移量转换为物理地址查询文件
B —字节，1字节8位
1MB=1024KB=1024B*1024=1048576B；
8bit=1Byte；
1024KB=1MB；
1024MB=1GB；
1024GB=1TB；
第二章进程
信号量
步骤
先判断几个进程
判断进程间的先后要求关系，或者互斥关系
注意
信号量的变量定义必须写成 semaphore s;这样的形式
信号量的赋值取决于资源的数量
程序的parbegin与parend
进程要么中括号，要么begin，end
代码里必须有P V操作，也就是P（s）这样的
每个信号量必须注释！
第三章处理机调度和死锁
进程调度
轮换算法
将运行的时间平均分给正在运行的所有进程
短作业优先
有一个具有两道作业的批处理系统（最多可有两道作业同时装入内存执行），作业调度采用计算时间短的作业优先调度算法，进程调度采用以优先数为基础的抢占式调度算法，今有如下作业序列，作业优先数即为进程优先数，优先数越小优先级越高：
| 作业名 | 到达时间 | 估计运行时间 | 优先数 |
|---|---|---|---|
| J1 | 10 : 10 | 20分钟 | 5 |
| J2 | 10 : 20 | 30分钟 | 3 |
| J3 | 10 : 30 | 25分钟 | 4 |
| J4 | 10 : 50 | 20分钟 | 6 |
列出所有作业进入内存时间及结束时间， 计算平均周转时间。
分析：
作业调度是负责把作业调入内存
进程调度负责分配处理器给作业让作业运行
一次内存里最多进入两个，但在运行中的只能一个作业
作业调度算法
先来先服务调度算法（First-come First-served，FCFS）
短作业优先调度算法（Short Job First，SJF）
优先级调度算法（Priority-scheduling Algorithm，PSA）
高响应比优先调度算法
[优先权R_p=frac{等待时间+要求服务时间}{要求服务时间}=frac{响应时间}{要求服务时间}
]
周转时间=结束时间-进入时间
平均周转时间可以表示为：
[T=frac{1}{n}sum_{i=1}^nT_i=frac{总周转时间}{作业数}
]
为了更好地描述调度的性能，往往采用带权周转时间，即周转时间Ti和运行时间Ts的比值，平均带权周转时间可以表示为：
[ W=frac{1}{n}sum_{i=1}^nfrac{T_i}{T_s}
]
第四章存储器管理
分页存储管理
求页大小和页表
求起始地址（16/10）
如果是16进制表示则：4KB=4*1024B=2+10=12位，作为页内偏移地址
主存分为16块，故内存物理地址高4位为主存块号。
第0页被装入主存第2块，在内存中起始地址：0010 0000 0000 0000 B
转换为16进制=>2 0 0 0 H
求逻辑地址转内存地址
分段存储管理
第五章虚拟存储器
页面置换算法
缺页率/缺页中断率
假设进程逻辑空间为n页，系统分配内存物理块数位m，若运行过程中，访问页面成功(该页面在内存中)的次数S，访问失败次数为F，则总访问次数A=S+F
[缺页率f=frac{F}{A}=frac{F}{F+S}=frac{访问成功次数}{总访问次数}
]
先进先出置换算法FIFO
最近最久未使用置换算法LRU
赋予每个页面一个访问字段，用于记录一个页面自上次被访问以来所经历的时间t，每次需要淘汰页面时，选择t最大的
主存块数3，所以总共可以放入三页
若改为主存字数和页大小，如下面
在一个采用分页式虚拟存储管理的系统中，有一用户作业，它依次要访问的字地址序列是115，228，120，88，446，102，321，432，260，167。若分配给作业可使用的主存空间共300个字，作业页面大小为100个字
分析：作业页面大小为100个字，所以地址88对应的页号为0，。。。
依次要访问的字地址序列可化为页号序列：1，2，1，0，4，1，3，4，2，1
主存300字，300/100=3.所以共三页
第七章文件管理
插入记录
文件 F 由 200 条记录组成，记录从 1 开始编号，用户打开文件后，欲将内存中的一条记录插入文件 F 中，作为其第 30 条记录，请回答下列问题，并说明理由。
（1）若文件系统为顺序分配方式，每个存储块存放一条记录，文件 F 的存储区域前后均有足够空闲的存储空间，则要完成上述操作最少要访问多少存储块？ F 的文件控制区内容会有哪些改变？
（2）若文件系统为链接分配方式，每个存储块存放的一条记录和一个链接指针，则要完成上述操作最少要访问多少次存储块？若每个存储块大小为 1KB，其中 4 个字节存放指针，则该系统支撑文件的最大长度是多少？
顺序分配方式
因为要最少访问，所以选择向前移动文件的前 29 条记录，向前移动文件的前29 条记录，每条记录需先读一次，然后写到其前一块磁盘块需 29×2=58 次。
然后需要将新记录写到腾出的那个磁盘块中， 作为该文件的第 30 条记录。故总共需要 58+1=59 次。
由于文件的起始位置前移了一个磁盘块，同时文件也增加了一条记录，因此F 的文件控制块中的文件的起始位置和文件的大小会发生改变。
链接分配方式
这就需要先找到第29 条文件记录的磁盘块，然后获得第 30 条文件记录的磁盘块地址 （需读磁盘 29 次）。
再为该记录分配一个空闲磁盘块， 将该记录以及第 30 条文件记录的磁盘块地址写入其中，再将该块写入磁盘（需写磁盘 1 次）。
最后还需要修改第 29 块的链接指针，指向新的插入块，并将第 29 块写回磁盘（需写磁盘 1 次）。
故共需要 29+1+1=31 次。
由于每个磁盘块大小为 1KB，其中 4 个字节存放链接指针， 因此用于存放文件的空间为（ 1KB-4B）。 又由于4字节指针的地址空间为2^32(32位，则共有2^32个物理块)。 因此该文件系统支持的文件最大长度是
（1024-4） B×2^32=4080GB
多级索引组织方式
字节偏移量转换为物理地址
解题思路
文件索引磁盘地址表=直接块号+一级索引+二级索引+三级索引
若磁盘块大小512字节，每个磁盘地址占2字节，因此一个一级索引可容纳256个磁盘地址。同样地，一个二级索引表可容纳256个一级索引表地址，一个三级索引表可容纳256个二级索引表地址
逻辑块号=字节偏移量/1024
块内偏移量=字节偏移量%1024
判断在哪个块
直接块，逻辑块号<直接块号数量
一次间接索引块,一级索引块号+直接块号数量>逻辑块号>直接块号数量
2次间接索引块,一级索引块号*一级索引块号+(一级索引块号+直接块号数量)>逻辑块号>一级索引块号+直接块号数量
若二级间接寻块，则需用（逻辑块号-直接块号数量-一级索引块号）/一级索引块号=第几块一级索引块号
一.UNIX系统中，假定盘块大小为1KB，每个盘块号占4个字节，文件索引结点中的磁盘地址明细表如图6-11所示，如何将下列文件的字节偏移量转换为物理地址(盘块号和块内偏移)？
（1）9000；（2）14000；（3）350000；（4）680000
（1）
解：
(1)
字节偏移量为9000
逻辑块号为：9000/1024=8
块内偏移量：9000%1024=808
因逻辑块号小于10，因此该块为直接块。由图6-12可知，其物理块号为367，该块的第808字节即为文件的第9000字节。
(2)
字节偏移量为14000
逻辑块号为：14000/1024=13
块内偏移量：14000%1024=688
因逻辑块号10<13<266，因此该块为一次间接块。
由图6-12可知，一次间接索引块号为428，由于直接索引有10个块号，13-10=3。读出428#块，查得其中第3个索引项值为952。即是逻辑块号13对应的物理块号为952，物理块952中的第688字节即为文件的第14000字节。
(3)
字节偏移量为350000
逻辑块号为：350000/1024=341
块内偏移量：350000%1024=816
因逻辑块号266<341<65802，因此该块为二次间接块。
由图6-12可知，二次间接索引块号为9156。由于一个一次间接块中可容纳256个块号，直接索引有10个块号，341-(10+256)=75；75/256=0。
读出9156#盘块，查得其中的第0个索引项值为331。读331#盘块，查得其中第75个索引项的值为3333。.因此，字节偏移量350000对应的盘块号为3333，3333#物理块中的第816字节即为文件的第350000字节。
(4)
字节偏移量为680000
逻辑块号为：680000/1024=664
块内偏移量：680000%1024=64
因逻辑块号266<664<65802，因此该块为二次间接块。
由图6-12可知，二次间接块号位9156。由于一个一次间接块中可容纳256个块号，直接索引有10个块号，664-(10+256)=398；398/256=1；398%256=142。读出9156#盘块，查得其中的第1个索引项值为452。.读452#盘块，查得其中第142个索引项的值为5300。.因此，字节偏移量680000对应的盘块号为5300，5300#物理块中的第64字节即为文件的第680000字节。
查询文件
某文件系统的目录结构如图6-2所示，已知每个目录项占256B，磁盘的一块为512B。设当前目录为根目录。
（1）查询文件Wang的路径是什么？
（2）系统需要读取几个文件后才能查到Wang？
（3）计算系统找到Wang，至少读了几个盘块。
（4）给出一种加速文件查找速度的方案。
答：
(1) 查询文件Wang的路径是 /D/DC/DDC/Wang
(2) 系统需要读取D、DC、DDC等3个目录文件才能查到Wang
(3) 因1个盘块中可存储2个目录项，读取根目录的第2个盘块时才能找到文件D的目录项；读取文件D的第2个盘块时才能找到DC的FCB；读取文件DC的第2个盘块时才找到文件DDC的FCB；读取DDC的第1个盘块就能找到Wang。因此，系统找到Wang，至少读了7个盘块。
(4) 可以采用类似UNIX的方法，缩短目录项，例如，目录项中仅包含文件名(12个字节)和索引节点号(4个字节)，目录项长度为16字节，这样每个盘块可存放32个目录项。这样只需读4个盘块就可找到Wang。
