公式速查

教材导航

公式用于定位复习,推导、适用条件和原书例题请进入相应知识点。

处理机调度

T周转=t完成−t到达,W带权周转=T周转T运行.T_{周转}=t_{完成}-t_{到达},\qquad W_{带权周转}=\frac{T_{周转}}{T_{运行}}.

平均周转时间与平均带权周转时间分别对各作业的对应值求算术平均。高响应比优先的响应比:

R=T等待+T服务T服务=1+T等待T服务.R=\frac{T_{等待}+T_{服务}}{T_{服务}}=1+\frac{T_{等待}}{T_{服务}}.

关联:2.2.3 调度的目标、2.2.5 CPU调度算法。

银行家算法

Need=Max−Allocation.Need=Max-Allocation.

请求需同时满足Request≤Need与Request≤Available,试分配后还必须通过安全性检查。安全检查令Work=Available,寻找Need≤Work的未完成进程,模拟完成后令Work=Work+Allocation。所有进程均能依次完成才得到安全序列。

关联:2.4.3 死锁避免。

分页与地址转换

对逻辑地址A、页面大小B:

p=⌊AB⌋,d=A mod B,PA=fB+d.p=\left\lfloor\frac AB\right\rfloor,\qquad d=A\bmod B,\qquad PA=fB+d.

其中p为页号,d为页内偏移,f为页表查得的页框号。B=2ᵇ时,低b位为页内偏移。页号至少应小于页表长度;分段还必须检查段内偏移小于段长。

页表项占e字节,页大小B时,一页最多容纳⌊B/e⌋个页表项;多级页表逐级按这个容量划分页号。

若一次访存tₘ,TLB查询tₜ,命中率α,单级页表、TLB与内存串行查询且不发生缺页,则:

EAT=α(tt+tm)+(1−α)(tt+2tm)=tt+(2−α)tm.EAT=\alpha(t_t+t_m)+(1-\alpha)(t_t+2t_m)=t_t+(2-\alpha)t_m.

多级页表、并行TLB查询、缓存页表项或缺页时需要重新建立时间模型。

关联:3.1.3 基本分页存储管理、3.1.4 基本分段存储管理、3.2.9 地址翻译。

缺页与有效访问时间

EAT=(1−p)T正常+pT缺页路径.EAT=(1-p)T_{正常}+pT_{缺页路径}.

p为缺页概率;缺页路径可能包括陷入、选择牺牲页、脏页写回、调入、恢复并重试。若题目给的是“额外缺页代价”,则应使用T正常+p×额外代价,避免重复或漏计重试。

关联:3.2.2 请求分页管理方式、3.2.4 页面置换算法、3.2.8 虚拟存储器性能影响因素。

文件索引与空间

块大小B,块地址占a字节,每个索引块有m=⌊B/a⌋个指针。若inode有d个直接块地址,以及一级、二级、三级间接地址各一个,则数据容量:

Lmax=B(d+m+m2+m3).L_{max}=B(d+m+m^2+m^3).

只计算题目实际存在的地址项;文件实际占用空间还应另算已使用的索引块、inode及分配粒度。长度L的文件数据块数为⌈L/B⌉,最后一块的内部碎片为⌈L/B⌉B−L。

关联:4.1.2 文件控制块和索引节点、4.1.5 文件的物理结构。

位示图

N个被管理物理块,需要N位,即⌈N/8⌉字节。行列、块号均从1开始且每行n位:

b=n(i−1)+j,i=⌊b−1n⌋+1,j=(b−1) mod n+1.b=n(i-1)+j,\quad i=\left\lfloor\frac{b-1}{n}\right\rfloor+1,\quad j=(b-1)\bmod n+1.

三者均从0开始时:b=ni+j,i=⌊b/n⌋,j=b mod n。位图不从磁盘第0块开始存放时,要再加位图自身的起始物理块号;位号与字节号相差8倍。

关联:4.3.3 文件存储空间管理。

缓冲时序与中断开销

T为输入一块到系统缓冲区的时间,M为复制到工作区的时间,C为CPU处理时间。大量连续数据的稳态平均每块时间:

T单缓冲=max⁡(T,C)+M,T双缓冲=max⁡(T,M+C).T_{单缓冲}=\max(T,C)+M,\qquad T_{双缓冲}=\max(T,M+C).

有限块总时间应画时序图,包含开始与结束阶段。每秒f次中断、每次占用CPU时间t时,占用比例约为f×t,注意统一秒、毫秒、微秒。

关联:5.2.2 高速缓存与缓冲区、5.1.2 I/O控制方式。

机械磁盘

转速r转/秒,或rpm转/分钟时r=rpm/60:

T转一圈=1r,T平均旋转延迟=12r.T_{转一圈}=\frac1r,\qquad T_{平均旋转延迟}=\frac1{2r}.

每磁道N字节、传输b字节,跨n条磁道、每条耗时m、启动耗时s:

Ts=mn+s,Tt=brN,Ta=Ts+12r+Tt.T_s=mn+s,\qquad T_t=\frac b{rN},\qquad T_a=T_s+\frac1{2r}+T_t.

磁头移动轨迹x₀,x₁,…,xₖ的总移动量为:

D=∑i=1k∣xi−xi−1∣.D=\sum_{i=1}^{k}|x_i-x_{i-1}|.

平均寻道长度用总移动量除以请求数量;SCAN的端点、回程以及LOOK的折返规则须先明确。容量单位和传输率单位按题目约定区分二进制与十进制。

关联:5.3.1 磁盘、5.3.3 磁盘调度算法、5.3.4 固态硬盘。