第二章大题考察同步互斥,PV问题
生产者消费者问题
- 特点
- 进程与进程之间是生产资源-消费资源的关系
- 解决步骤
- 确定有几类进程,每个进程对应一个函数
- 在函数内部用中文描述动作
- 只做一次(不加while)
- 不断重复(加while)
- 在每一个动作之前确定需要什么(注意隐含的互斥条件,如对缓冲区的访问),如有P操作,则必定有V操作
- 所有PV写完之后再定义信号量
- 检查多个P操作连续出现的地方,是否有死锁产生可能
- 某个信号量的PV连续出现(中间没有夹杂着其他的P),不可能产生死锁,连续多个P导致死锁时,可尝试调整P顺序
|
|
|
|
理发师问题
- 特点
- 进程之间是服务与被服务的关系
- 主要解法
|
|
|
|
哲学家问题
- 特点
- 只有一类进程,要占用多种资源才能运行
- 关键点
- 限制申请资源的顺序(不通用,不建议使用)
- 如规定单号哲学家先取左筷子,双号先取右筷子
- 限制并发进程数(通用,但并发度不高,不建议使用)
- 如规定同一时间只能有一个哲学家就餐(禁止并行)
- 让进程一口气取得所有资源,再开始运行(很通用且并发度高,建议使用)
- 如哲学家只有能够取得两个筷子的时候才会就餐
- 限制申请资源的顺序(不通用,不建议使用)
- 解法
- 定义大锁
- 定义资源数
- 一口气拿所有资源
- 做进程该做的事
- 一口气归还所有资源
|
|
通常解
|
|
暴力解(考试建议解法)
|
|
读者写者问题
- 特点
- 同类进程不互斥,异类进程互斥
- 避免写者饥饿
- 读写公平法
- 写者优先法
- 如何实现
- 第一进程用之前负责上锁,最后一个进程用完之后负责解锁
|
|
实现同类互斥,异类也互斥
|
|
(1)
|
|
(2)
|
|
|
|
第三章大题,考察请求分页,基本分页,页面置换问题
- 各概念间的推导计算
- 一级页表+TLB+请求分页
- 二级页表+请求分页+TLB
- 页目录号的位数表示的大小(表示有多少个目录项)* 每个目录项的大小 = 页目录表的大小
- 页目录表的起始地址 + 页目录号 * 页目录项的长度 = 页目录项的物理地址
- 示例图中挖掘隐藏信息
- 熟悉各类常见图示
- 注意:TLB组相联映射、全相联映射的图示画法
- 深入理解组相联映射,全相联映射方式下查询TLB的原理区别
- 基于地址转化过程的分析
- 熟悉各种状况下地址转化的过程
- 一级页表+虚拟内存+TLB
- 二级页表+虚拟内存+TLB
- 熟悉各种状况下地址转化的过程
TLB+二级页表+Cache(全相联映射)
TLB+二级页表+Cache(2路组相联映射)
TLB + 二级页表 + Cache(直接映射)
(1)
页的大小 = 块的大小 = $2^{12}$ = 4 KB
页表的大小 = $2^{20} \times 4B$ = 4 MB
(2)
页目录号 = (((unsigned int)(LA))>>22) & 0x3FF
页表索引 = (((unsigned int)(LA))>>12) & 0x3FF
(3)
00008000H其页号为0008 $\rightarrow$ 页号为8 $\rightarrow$ 对应页表第8个页表项
第8个页表项物理地址 = 00200000H + 8 $\times$ 页表项的字节数
= 00200000H + 8 $\times$ 4 = 00200020H
第9个页表项及其物理地址 = 00200000H + 8 $\times$ = 00200024H
页框号1 = 00900000H,页框号2 = 00900000H + 8KB = 00901000H
代码2起始物理地址 = 00901000H
页的大小 = 4KB = $2^{12}$B,页面位移比虚拟地址低12位
访问2362H即 0010 0011 0110 0010 其对应页号为2
访问快表10ns $\rightarrow$初始快表空$\rightarrow$访问页表100ns得到页框号$\rightarrow$ 合成物理地址后访问主存100ns
共 10 + 100 + 100 = 210 ns
访问1565H即 0001 0101 0110 0101 其对应页号为2
访问快表10ns ,空$\rightarrow$访问页表100ns,空$\rightarrow$ 缺页中断处理$10^8$ns $\rightarrow$访问快表10ns$\rightarrow$合成物理地址后访问主存100ns
共 10 + 100 + $10^8$ + 10 + 100 = 100000220 ns
访问25A5H即 0010 0101 1010 0101 其对应页号为2 访问快表10ns $\rightarrow$合成物理地址后访问主存100ns
共 10 + 100 = 110 ns
(2)
1565H = 0001 0101 0110 0101
页号为1,产生缺页中断,驻留集 = 2,从页表淘汰1个页面
使用LRU淘汰页号0 $\rightarrow$ 1565H对应页框号为101H 物理地址 = 101565H
(1)
页的大小 = 1KB = $2^{10}$B
逻辑地址低10位为页偏移
17CAH $\rightarrow$ 0001 0111 1100 1010
页号为 000101 = 5
(2)
根据FIFO,置换页号0,对应页框号7
物理地址为 0001 1111 1100 1010 = 1FCAH
(3)
根据clock 置换页号2,对应页框号2
物理地址为 0000 1011 1100 1010 = 0BCAH
(1)
0页对应空闲页第3个,即页框号 = 1
(2)
11>10,说明此时发生第三轮扫描
第二轮中32,15,41,均未被访问,处于空闲页表中
此时重新访问第一页,则页框号32被重新放回驻留集
(3)
2页从未被访问,此时空闲链为41,15,取其头41,即页框号41
(4)
适合,程序的时间局部性越好,从空闲页框链表中重新取回的机会越大,该策略优势越明显
(1)
页的大小 = $2^{12}$B
页框大小 = $2^{12}$B
虚拟地址空间大小 = $2^{10} \times 2^{10}$ = $2^{20}$页
(2)
页目录所占页数 = $\frac{2^{10} \times 4B}{2^{12}} = 1$
页表所占页数 = $\frac{2^{10} \times 2^{10} \times 4B}{2^{12}} = 2^{10}$
共占 $2^{10} + 1 = 1025$页
(3)
0100 0000H对应页目录号 0000 0001 00 = 4
0111 2048H对应页目录号 0000 0001 00 = 4
访问的是同一个二级页表,即供访问一个二级页表
(1)
页目录号 = 6(10位) 页内索引 = 6(10位)偏移 = 8(12位)
所以十六进制为 0000 0001 1000 0000 0110 0000 0000 1000
= 01806008H
(2)
物理地址
进程切换时,地址空间发生了改变,对应页目录块及始址也改变 $\rightarrow$ PDBR改变
同一进程线程切换时,地址空间不变,线程的页目录不变$\rightarrow$ PDBR不改变
(3)
使用位$\rightarrow$访问字段
修改位$\rightarrow$修改字段
(1)
页面大小 = $2^{12} = 4KB$
一个页可以存$\frac{4KB}{4} = 1024$个数组 = a数组的一行
a按行优先方式存放,10800000H,虚页号为10800H
a[0]行存放在10800H的页面中 a[1]行存放在10801H的页面中
a[1][2]的虚拟地址为 10801000H + 4 $\times$ 2 = 10801008H
10801008H = 0001 0000 1000 0000 0001 0000 0000 1000
页目录号 = 0001000010 = 042H
页号 = 0000000001 = 001H
页目录项物理地址 = 00201000H + 4 $\times 42$H = 00201108H
物理地址 003010000 + 001H $\times 4$ = 00301004H
(2)
必须连续,不一定连续
(3)
按行遍历局部性更好。每个页面正好放一整行的元素
按行存放说明一行元素存放在同一页面中,局部性也就更好
第四章大题:混合文件索引
显式链表分配法(FAT文件系统,即DOS)
混合索引法(Unix文件系统)
考题
(1)
连续存放更合适,磁盘寻道时间更短,文件随机访问效率更高
加入字段<起始块号,块数>
(2)
FCB集中存放,文件数据集中存放
这样在随机查找文件名时,只需访问FCB对应的块,可减少磁头移动和磁盘IO访问次数
(1)
磁盘块总数 = $\frac{4TB}{1KB} = \frac{4 \times 2^40}{2^10} = 2^32$
块号至少占 $\frac{32}{8} = 4B$
512B的索引区能够容纳$\frac{512B}{4B} = 128$个索引项
文件最大长度 = 1KB $\times$ 128 = 128KB
(2)
索引项 = $\frac{504B}{6B} = 84$个
单个文件最大长度 = $2^{16} \times 1KB + 84 \times 1KB = 84KB + 2^{26}B$
起始块号占4B,块数占4B
起始块号可寻址$2^{32}$个块,共4TB即整个系统空间
块数可表示$2^{32}$个块,共4TB
(1)
dir目录文件
文件名 | 簇号 |
---|---|
dir1 | 48 |
dir1 目录文件
文件名 | 簇号 |
---|---|
file1 | 100 |
file2 | 200 |
(2)
簇号2B = 16位 $\rightarrow$ FAT表允许$2^{15}$个表项
FAT最大长度 = $2^{16} \times 2B = 128KB$
文件最大长度 = $2^{16} \times 4KB = 256MB$
(3)
106存放在100号表项中
108存放在106号表项中
(4)
先访问dir1,即第48个簇
得到file1的第一个簇号,在FAT中查找file1的第5000个字节所在簇号,最后访问该簇号(4KB = 4096B < 5000B)
即访问48号簇,106号簇
(1)
把文件前29条前移,移动一条记录读出和存回磁盘各一次访盘
共访盘 $29 \times 2 +1 = 59$次
F的文件控制区的起始块号和文件长度内容会发生改变
(2)
找到系统第29块,访盘29次
把29的下块地址给新块,把新块存回磁盘,访盘一次,
修改内存第29块的下块地址字段,再存回磁盘,访盘一次
共29 + 1 + 1 = 31 次
4B即32位,可寻址$2^{32} = 4G$块存储块,每块大小1KB = 1024B
其中4B为指针,1020B为数据
文件长度为$1020B \times 4G = 4080GB$
(1)
1个簇最多有$\frac{4KB}{4B} = 1024$个地址项
直接地址8个:$8 \times 4KB$ 二级地址1个:$2^{20}\times4KB$
一级地址1个:$2^{10} \times 4KB$ 三级地址1个:$2^{30} \times 4KB$
最大文件长度 = 32KB + 4MB + 4GB + 4TB
(2)
最多索引结点数 = $\frac{2^20 \times 4KB}{64B} = 2^{26} = 64M$个
$\frac{5600B}{4KB} > 1 \rightarrow $ 一个图像占两个簇
$\frac{512M}{2} = 256M \rightarrow $可存放256M个文件
但索引结点数64M < 256M
所以最多存放64M个图像文件
(3)
$6KB < 8\times 4KB$
$F_1$采用直接索引$\rightarrow$只要访问索引结点的直接地址项
$32KB < 40KB < 32KB + 4MB$
$F_2$采用一级索引$\rightarrow$ 还需读一级索引表
所以两者不相同
第五章
大题
(1)
用位图表示磁盘的空闲空间,每位表示一个磁盘块的空闲状态
共需$\frac{16384}{32} = 512$个字$=512 \times 4B = 2KB$,正好可以放在系统提供的内存中
(2)
磁盘访问序列为$120 \rightarrow 30 \rightarrow 50 \rightarrow 90$
移动磁道数分别为 20,90,20,40
移动磁道时间 = $1ms \times (20 + 90 + 20 + 40) = 170ms$
一次旋转时间 = $\frac{60}{6000} = 0.01s = 10ms$
总的旋转延迟 = $4 \times \frac{1}{2} \times(一次旋转时间) = 4\times 5ms = 20ms$
总读取时间 = $4 \times \frac{10ms}{100} = 4 \times 0.1ms = 0.4ms$
总时间 = 170ms+20ms+0.4ms = 190.4ms
(3)
FCFS(先来先服务调度算法)更高效
Flash半导体存储器不需要考虑寻道时间和旋转延迟
可直接按IO请求的先后顺序服务
(1)
容量 = $300 \times 10 \times 200 \times 512B = 3 \times 10^5KB$
(2)
85号柱面对应簇号 85000~85999(一个簇有2个扇区)
访问次序为 $100260 \rightarrow 101660 \rightarrow 110560 \rightarrow 60005$
(3)
$\frac{200 \times 10}{2} = 1000$
$100 \times 1000 = 100000$
$100530 - 100000 = 530$
$\frac{530}{100} = 5$
$30 \times 2 = 60$
柱面号1000,磁头号5,扇区号60
将簇号转换成磁盘物理地址的过程由磁盘驱动程序完成
(1)
ROM中的引导程序$\rightarrow$磁盘引导程序$\rightarrow$分区引导程序$\rightarrow$OS的初始化程序
(2)
磁盘的物理格式化$\rightarrow$对磁盘分区$\rightarrow$逻辑格式化$\rightarrow$OS的安装
(3)
磁盘扇区的划分$\rightarrow$磁盘的物理格式化$\rightarrow$文件根目录的建立$\rightarrow$逻辑格式化操作