08 第六章 存储管理（2）.pptx

第1页：6.4 外存管理技术外存逻辑划分

• 输入井,输出井:
  • 作业预输入/作业缓输出;
  • 虚拟设备。
• 文件空间:
  • 用于保存文件;
  • 文件系统。
• 交换空间:也叫对换空间。
  • 实现虚拟存储的外存空间;
  • 内存的扩充。

第2页：6.4.1 外存空间划分

• 静态等长, 2i,称为一块(block) ;
• 块由0开始依次编号,称为块号;
• 块是外存分配的基本单位;
• 也是I/O传输的基本单位。

第3页：6.4.2 外存空间分配

• 空闲块链(慢) ;
• 空闲块表(UNIX) ;
• 位示图(字位映像图):每位代表块状态。

第4页：6.4.2 外存空间分配（续）

1.界地址:块首址,块个数

每个进程占一组连续外存块;

每个进程占二组外存连续块(双对界)。

2.页式

内存一页,外存一块。

3.段式

每段占若干连续外存块。

4.段页式

内存一页,外存一块。进程与外存对应关系为实现外存管理，采用与内存同样的数据结构，并且这些数据结构在内存的系统区定义。

第5页：6.5 虚拟存储系统

• 无虚拟问题
  • 不能运行比内存大的程序;
  • 进程全部装入内存,浪费空间进程活动具有局部性:时间局部性和空间局部性。
• 虚拟存储
  • 进程部分装入内存,部分(或全部)装入外存;
  • 运行时访问在外存部分动态调入,内存不够淘汰。

第6页：6.5.1 虚拟页式存储管理

• 1.基本原理
• 进程运行前全部(或部分)装入外存，部分装入内存。
• 进程运行时:访问页面不在内存,则产生缺页中断,进程进入等待状态,系统页面动态调度:⑴找到被访问页面在外存的地址;⑵在内存找一空闲页框;
• ①如没有,按淘汰算法选择一个页面p ;
• ②(当页面P被修改时)将页面p写回外存,修改页表和总页表;⑶读入所需页面,修改页表及页框分配表;⑷重新启动进程(进程切换),执行被中断的指令。

第7页：6.5.1 虚拟页式存储管理（续）

6.5.1虚拟页式存储管理虚拟页式存储管理地址映射指令给出逻辑地址(p,d)由p查快表得到f查到f、d合并得到物理地址0≤p≤l-1越界中断由b、p查找页表该页在内存缺页中断保存现场有空闲页框选一页面淘汰该页面修改过写回外存读入所需页面更新页表和快表恢复现场FFFTTT( f,d)→快表如快表满，则淘汰一表项硬件完成软件完成结束T

第8页：6.5.1 虚拟页式存储管理（续3）

6.5.1虚拟页式存储管理对页表的改进:修改标志内外标志访问权限外存块号页框号逻辑页号……………………………｛1,0｝{1,0}{r,w,e}b’fp……………………………对快表的改进:修改标志访问权限页框号逻辑页号…………………｛1,0｝{r,w,e}fp

第9页：6.5.1 虚拟页式存储管理（续4）

2.内存页框分配策略(静态策略)⑴平均分配如内存128页框,进程25个,每个进程5个页框。⑵按进程长度比例分配系统有n个进程, pi共si个页面(i=1,…,n),内存共m个页框,则进程pi分配的页框数为:ai = (si/(∑sj ))→m⑶按进程优先级比例分配高优先级进程多分页架,公式中si改为优先级。⑷按进程长度和优先级别比例分配:公式中si改为“si +优先级”。j=1n静态策略没有反映:⑴程序结构;⑵程序在不同时刻的行为特性。

第10页：6.5.1 虚拟页式存储系统

3.外存块的分配策略

⒈静态分配

外存始终保存进程的全部页面。某页面调入内存时,外存页面也不释放;优点:速度快━淘汰时不必写回(未修改情况) ;缺点:外存浪费;

⒉动态分配

外存仅保存进程不在内存的页面。某页面调入内存时,释放外存页面;优点:节省外存;缺点:速度慢━淘汰时必须写回。

第11页：6.5.1 虚拟页式存储系统（续）

4.页面调入时机⑴请调(demand paging)upon page fault,发生缺页中断时调入。优点:不会发生无意义的页面调度;缺点:缺页中断时进程等待,影响进程推进。⑵预调(prepaging)before page fault,也叫先行调度。将要访问时调入(根据程序顺序行为,不一定准) ;预调必须辅以请调。优点:降低缺页故障率;缺点:实现开销大。

第12页：6.5.1 虚拟页式存储系统（续3）

5.置换算法(replacement algorithm)也叫淘汰算法(removing algorithm)

作用

页淘汰、段淘汰、快表淘汰。

目的

lowest page-fault rate.

分类

局部置换和全局置换。

局部置换:在缺页进程的页框集中选择淘汰页面。

全局置换:在内存所有页框集中选择淘汰页面。

第13页：6.5.1 虚拟页式存储系统（续4）

6.5.1虚拟页式存储系统⑴最佳淘汰算法(OPT--optimal)淘汰将来最长时间以后才用到的页面。效率最高，not feasible。例[OPT淘汰算法]:设进程P分配3个内存页框。10510212303240302105页面访问序列55522222222222222555页框f10000000000444000000页框f2111111133333333111页框f3234015淘汰页面×××××××××缺页故障缺页故障9次

第14页：6.5.1 虚拟页式存储系统（续5）

6.5.1虚拟页式存储系统⑵先进先出(FIFO):淘汰最先调入的页面。

依据

先进入的可能已经使用完毕; (如:初始化段)

实现

记录装入时间；队列。

negative case

有些代码和数据可能整个程序运行中用到。例[FIFO淘汰算法]:设进程P分配3个内存页框。10510212303240302105页面访问序列55500000004442222555页框f10011111222223330000页框f2122222333330001111页框f3210324032105淘汰页面×××××××××××××××缺页故障缺页故障15次

第15页：6.5.1 虚拟页式存储系统（续6）

Belady异常

采用FIFO淘汰算法时,如果某进程未分配它所需要的全部页框,有时会出现分配的页框数增多但缺页率反而提高的异常现象。

Belady异常描述

进程P要访问M个页面,OS分配N (N<M)个内存页框给进程P ;对一个访问序列S,发生缺页次数为PE (S, N)。当N增大时, PE (S, N)时而增大时而减小。

第16页：6.5.1 虚拟页式存储系统（续7）

例子[Belady异常]设进程P页面访问序列为: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 56.5.1虚拟页式存储系统543215214321页面访问序列分配页框数555555444111页框f1333311111222页框f24422222333页框f3214321淘汰页面9×××××××××缺页故障543215214321页面访问序列分配页框数445555111111页框f1451111222222页框f22222333333页框f3333444444页框f

第17页：6.5.1 虚拟页式存储系统（续8）

6.5.1虚拟页式存储系统⑶最近最少使用的先淘汰(Least-Recently-Used, LRU):淘汰最后一次访问时间距当前时间间隔最长的页面。

实现

①计时法:对每个页面增设访问时间计时器。

当页面被访问时,把绝对时间记录到页面计时器中;

淘汰时选页面计时器中时间值最小的页面淘汰。

②栈

设置页面访问“栈”(非真正意义的LIFO栈)。

页面p被访问时,删除栈内的p ,再将p压入栈;

淘汰时选栈底的页面淘汰。OPT用于S的页故障率=LRU用于R(S)的页故障率。

第18页：6.5.1 虚拟页式存储系统（续9）

6.5.1虚拟页式存储系统例[LRU淘汰算法]:设进程P分配3个内存页架。10510212303240302105页面访问序列11111110004442222555页框f10000033333300000000页框f2555222222222333111页框f3230003215淘汰页面××××××××××××缺页故障105102123032403

第19页：6.5.1 虚拟页式存储系统（续10）

• 6.5.1虚拟页式存储系统⑷最近不用的先淘汰(Not-Used-Recently, NUR):淘汰最近一段时间内未用过的页面。效率:流行、低开销、接近LRU效果。
• 实现:
  • 每个页面增设两个硬件位:0 ,此页未被访问过引用位=1 ,此页曾被访问过0 ,此页未被修改过修改位=1 ,此页曾被修改过
  • 位的修改:
• ①页面调入内存时,引用位、修改位均为0;
• ②页面执行写操作,引用位、修改位均置为1;
• ③页面执行读操作,引用位置为1;
• ④每隔一段固定时间(最近),将所有引用位都清0。

第20页：6.5.1 虚拟页式存储系统（续11）

• 淘汰次序:
• ①引用位=0、修改位=0,直接淘汰;
• ②引用位=0、修改位=1,淘汰前写回外存;
• ③引用位=1、修改位=0,直接淘汰;
• ④引用位=1、修改位=1,淘汰前写回外存。1520403232012105页面访问序列5533333335555555页框f1000000000000000页框f214444111111111页框f32222222222222页框f44315淘汰页面××××××××缺页故障1100111010001111f1访问标志1111110011101110f2访问标志1000100011111100f3访问标志1110111111001000f4访问标志

第21页：6.5.1 虚拟页式存储系统（续12）

• ⑸最不经常使用的先淘汰(LFU):淘汰使用次数最少的。依据:活跃访问页面应有较大的访问次数.不足:
• ①前期使用多,但以后不用,难换出;
• ②刚调入的页面,引用少,被换出可能大。实现:
• ①每个页面设访问次数计数器;
• ②调入页面,其页面计数器清0,访问增1 ;
• ③淘汰选取计数器值最小的页面。⑹最频繁使用的先淘汰(MFU):淘汰使用次数最多的。依据:使用多的可能已经用完了。不足:程序有些成分是在整个程序运行中都使用的。

第22页：6.5.1 虚拟页式存储系统（续13）

• 6.5.1虚拟页式存储系统⑺二次机会算法(second chance)淘汰装入最久且最近未被访问的页面。
• 实现：采用链式队列数据结构。例:某进程分配8个页框，访问页面2时发生缺页中断。6/13/14/08/05/19/00/01/18/05/19/00/01/16/03/02/13/14/08/05/19/00/01/16/04/08/05/19/00/01/16/03/0

第23页：6.5.1 虚拟页式存储系统（续14）

• ⑻时钟算法(clock algorithm)
• 将页面组织成环形，有一个指针指向当前位置。
• 每次需要淘汰页面时，从指针所指的页面开始检查:
  • 如果当前页面访问位为0，即从上次检测到目前,该页没有访问过,则将该页淘汰;
  • 如果当前页面的访问位为1,则将其清0,顺时针移动指针到下一个位置。
  • 重复上述步骤直至找到一个访问位为0的页面。6.5.1虚拟页式存储系统
• 时钟算法与二次机会算法的淘汰效果基本相同；
• 采用的数据结构不同：二次机会使用的是链表，需要额外存储空间，摘链入链速度很慢；时钟算法可直接利用页表中的引用位，外加一个指针，速度快且节省空间。

第24页：6.5.1 虚拟页式存储系统页

6/r=1页3/r=1页4/r=0页8/r=0页10/r=1页9/r=0页0/r=0页1/r=1框12框23框51框6框81框96框60框5访问第18页时钟算法

第25页：6.5.1 虚拟页式存储系统时钟算法

页6/r=0页3/r=1页4/r=0页8/r=0页10/r=1页9/r=0页0/r=0页1/r=1框12框23框51框6框81框96框60框5访问第18页

第26页：6.5.1 虚拟页式存储系统页

6/r=0页3/r=0页4/r=0页8/r=0页10/r=1页9/r=0页0/r=0页1/r=1框12框23框51框6框81框96框60框5访问第18页时钟算法

第27页：6.5.1 虚拟页式存储系统页（续）

6/r=0页3/r=0页18/r=1页8/r=0页10/r=1页9/r=0页0/r=0页1/r=1框12框23框51框6框81框96框60框5替换第4页

第28页：6.5.1 虚拟页式存储系统

• ⑼改进的时钟算法考虑修改标志m
  • r=0, m=0：最佳淘汰页面
  • r=0, m=1：淘汰前回写
  • r=1, m=0：不淘汰
  • r=1, m=1：不淘汰

第29页：6.5.1 虚拟页式存储系统（续）

• 改进的时钟算法S1:由指针当前位置开始扫描,将第一个遇到的r=0且m=0的页面作为淘汰页面;扫描过程中不改变引用位;S2:若S1失败,再次从原位置开始扫描,将第一个遇到的r=0且m=1的页面作为淘汰页面;扫描过程中将扫描过的页面的r位清0;S3:若S2失败,指针再次回到原位置, goto S1。

第30页：6.5.1 虚拟页式存储系统改进的时钟算

页6/r=1m=1页3/r=1m=1页18/r=1m=0页8/r=1m=0页10/r=1m=0页9/r=0m=1页0/r=0m=1页1/r=1m=0框12框23框51框6框81框96框60框5访问第15页

第31页：6.5.1 虚拟页式存储系统

页6/r=1m=1页3/r=1m=1页18/r=1m=0页8/r=0m=0页10/r=1m=0页9/r=0m=1页0/r=0m=1页1/r=1m=0框12框23框51框6框81框96框60框5访问第15页改进的时钟算法

第32页：6.5.1 虚拟页式存储系统（续）

页6/r=1m=1页3/r=1m=1页18/r=1m=0页8/r=0m=0页10/r=0m=0页9/r=0m=1页0/r=0m=1页1/r=1m=0框12框23框51框6框81框96框60框5访问第15页改进的时钟算法

第33页：6.5.1 虚拟页式存储系统（续3）

页6/r=1m=1页3/r=1m=1页18/r=1m=0页8/r=0m=0页10/r=0m=0页15/r=1m=0页0/r=0m=1页1/r=1m=0框12框23框51框6框81框96框60框5改进的时钟算法

第34页：6.5.1 虚拟页式存储系统（续4）

6.抖动/颠簸(thrashing)页面在内存与外存之间频繁换入换出。原因:⑴分给进程物理页框过少;⑵淘汰算法不合理;⑶程序结构:跳转指令,全局变量分散定义。处理:⑴增加分给进程物理页框数;⑵改进淘汰算法。⑶改进程序结构;思考题:在某些虚拟页式存储管理系统中,内存中总保持一个空闲的物理页框,这样做有什么好处？

第35页：6.5.1 虚拟页式存储系统（续5）

7.工作集模型(working set model)淘汰算法的效果与进程运行的页面走向有关;进程访问页面的局部化程度愈高,进程运行效率愈高。

时间局部化

一旦某条指令或数据被访问,经常很快又被访问,如程序中的循环体部分和循环控制变量。

空间局部化

一旦某个位置被访问到,附近的位置也可能很快要用到,如程序中的顺序指令串、数组。局部化反映在页面走向上,就是在任何一小段时间里,进程运行只集中于访问某几页。

第36页：6.5.1 虚拟页式存储系统（续6）

• 工作集(working set):进程在一段时间内所访问页面(活动页面)的集合。某进程从时刻(t-△)到时刻t之间所访问页面的集合WS (t ,△)称作该进程的工作集。△称作窗口尺寸(windows size)。
• 可利用工作集动态调整(增加或减少)进程的页框分配数。访问页面: 2 , 3 , 3 , 3 , 2 , 3 , 2 , 5 , 5 , 8 , 5△Tt-△tWS(t ,△)=(2,3,5,8)Denning认为:为使程序有效运行,工作集应能放入内存。

第37页：6.5.1 虚拟页式存储系统（续7）

工作集与时间有关

访问页面: 2, 3, 3, 3, 2, 3, 2, 5, 5, 8, 5, 5, 8, 5, 3, 9, 8, 9, 5, 8, 7,8T△△t1-△t1t2WS(t1,△)=(2,3,5,8)WS(t2,△)=(5,8,3,9,7)

工作集与窗口尺寸有关

WS窗口尺寸△程序大小0

第38页：6.5.1 虚拟页式存储系统（续8）

• △周期内确定工作集大小的实现
  • 页表、快表增加页面引用位；
  • 每个△周期开始时，引用位都清0；
  • 每当访问一个页面，其引用位置1；
  • 当△周期结束时，标记为1的页面个数即为工作集的大小。
• 第n+1个△周期工作集大小的估算公式：τn+1=αWn+(1-α)τn其中：Wn为第n个△周期实际工作集大小；τn为第n个△周期工作集估算值；α通常取值为0.5。

第39页：6.5.1 虚拟页式存储系统（续9）

• 8.页故障率反馈模型:PFFB(Page Fault Feed Back)
• 页故障率＝访问内存缺页次数/访问内存总次数
• 思想:利用页故障率反馈信息,动态调整页框的分配。
• 实现:
  • 规定页故障率上界、下界;
  • 页故障率高(达到某上界阈值):内存页面少,增加页框。
  • 页故障率低(达到某下界阈值):内存页面多,减少页框。

第40页：6.5.1 虚拟页式存储系统（续10）

9.例子:某虚拟页式系统，进程空间和内存空间都是64k，页长1K。某进程6个页面，内存分配4个页框，采用局部置换。280时刻页表和Clock数据结构如下：0页2页3页5页框5框12框8框3(顺时针)访问标志装入时间页框号逻辑页号111050---11160122123083---

第41页：时刻

：(1)访问13B7H，逻辑页号是多少？(2)采用FIFO置换算法，物理页框号是多少？物理地址是多少？(3)采用CLOCK置换算法，页框号是多少？物理地址是多少？6.5.1虚拟页式存储系统

第42页：6.5.1 虚拟页式存储系统

解：（1）逻辑地址13B7H化为二进制数为0001,0011,1011,0111其中低10位为页内地址，高6位为逻辑页号，即逻辑页号为4。4号页面不在内存，发生缺页中断，（2）按FIFO置换算法，应置换第5页，所得页框号3，形成物理地址：0000,1111,1011,0111划成16进制为：0FB7H（3）采用CLOCK置换算法，淘汰第0页，得页框5，形成物理地址：0001,0111,1011,0111划成16进制为17B7H。

第43页：6.5.2 虚拟段式存储系统

1.基本原理

进程运行前

全部装入外存,部分(主程序)装入内存;

进程运行时

访问段不在内存,发生缺段中断,动态调入。

调入时如果内存空间不足,采用方法

⑴紧凑:空闲区合并;⑵淘汰:按淘汰算法将内存中某段移至外存。

第44页：6.5.2 虚拟段式存储系统（续）

6.5.2虚拟段式存储系统虚拟段式存储管理地址映射指令确定逻辑地址(s,d)由s查快表得到b’和l’查到b’+d得到物理地址0≤s≤l-1越界中断由b、s查找段表该段在内存缺段中断保存现场内存可满足选一段淘汰该段修改过写回外存读入该段修改段表和快表恢复现场FFFTTT( s, b’,l’)→快表如快表满，则淘汰一表项硬件完成软件完成结束T0≤d≤l’-1T越界中断F0≤d≤l’-1越界中断Fb’+d得到物理地址找到该段在外存的位置紧凑够紧凑T修改段表

第45页：6.5.2 虚拟段式存储系统（续3）

段表的改进

修改标志内外标识访问权限外存首址内存首址段长段号…………………………………{0,1}{0,1}{rwe}b"b’l’S…………………………………

快表的改进

修改标志访问权限内存首址段长段号………………………{0,1}{rwe}b’l’S

第46页：6.5.2 虚拟段式存储系统（续4）

2.段的动态连接(dynamic linking)⑴动态连接的提出

静态连接

运行前连接,由link完成;

动态连接

运行需要时连接,由OS完成。

静态连接的缺点:

连接时间长;

目标代码长;

连接段可能并不执行(未用到)。

第47页：6.5.2 虚拟段式存储系统（续5）

6.5.2虚拟段式存储系统⑵动态连接的实现(Multics为例)静态连接:程序段个数固定,段名、段号转换直接由连接装配程序完成。动态连接:程序段个数不确定,段名、段号转换由操作系统完成。实现所需表:段号段名…………s_numbs_name…………段内偏移符号名A1S1…………AkSk符号表目标代码或数据(每进程一个)(每段一个)段结构段名/段号对照表符号表

第48页：6.5.2 虚拟段式存储系统（续6）

• 动态连接的实现步骤①编译(汇编)时:遇到访问外段指令,采用间接寻址,指向一个间接字:DL符号地址：“[X]|<Y>”逻辑地址(段号,段内偏移)1:未连接,段号未定0:已连接,段号已定L也叫障碍指示位！

第49页：6.5.2 虚拟段式存储系统（续7）

遇到间接指令,且L = 1,发生连接中断,处理程序:⒜由D取出符号地址”[X]|<Y>” ;⒝由段名”[X]”查找<段名-段号对照表>,如查到表项([X], Sx),则已分配段号:I.取出段号Sx ,并用Sx查段表,找到该段;II.由符号地址<Y>查段名[X]的<符号表>得段内地址Ax;III.逻辑地址(Sx, Ax)⇒D, 0⇒L ;IV.转段式<(逻辑地址⇒物理地址)转换程序>。否则未分配段号: [X]段未连接过。I.将[X]段读入内存,分配段号;II.填写<段表>,填写<段名-段号对照表>,转⒝。6.5.2虚拟段式存储系统②执行时:

第50页：6.5.2虚拟段式存储系统例子

6.5.2虚拟段式存储系统例子:设有两个段[W], [X]。①汇编前:[W]段...Load 1, [X]|<Y>…Load 2, [X]|<Z>...[X]段…1234…5678...Y:Z:

第51页：6.5.2虚拟段式存储系统例子（续）

6.5.2虚拟段式存储系统②汇编后:[W]段已连接并在内存,段号为2 ; [X]段未连接。段首址…段号0123……段表Load *1, 2|100……Load *2, 2|150………… 2 2001100:………… 2 2501150:……“7[X]|<Y>”200:……“7[X]|<Z>”250:[W]段(段号=2)段号段名0[MAIN]1[A]2[W]…………段名/段号对照表……300<Y>……400<Z>…………1234300……5678400……[X]段100, 150为间接字;浅蓝色为符号表。

第52页：6.5.2虚拟段式存储系统例子（续3）

6.5.2虚拟段式存储系统③第一次连接:执行指令Load *1, 2|100;将[X]段连接到内存.段首址…段号0123……段表Load *1, 2|100……Load *2, 2|150………… 3 3000100:………… 2 2501150:……“7[X]|<Y>”200:……“7[X]|<Z>”250:[W]段(段号=2)段号段名0[MAIN]1[A]2[W]3[X]段名/段号对照表300<Y>……400<Z>…………1234300……5678400……[X]段(段号=3)

第53页：6.5.2虚拟段式存储系统例子（续4）

6.5.2虚拟段式存储系统④第二次连接:执行指令Load *2, 2|150。段首址…段号0123……段表Load *1, 2|100;……Load *2, 2|150;………… 3 3000100:………… 3 4000150:……“7[X]|<Y>”200:……“7[X]|<Z>”250:[W]段(段号=2)段号段名0[MAIN]1[A]2[W]3[X]段名/段号对照表300<Y>……400<Z>…………1234300……5678400……[X]段(段号=3)

第54页：6.5.2 虚拟段式存储系统

• ⑶动态连接的问题
• 动态连接与共享的矛盾
  • 多道程序环境下要求代码段共享中不能被修改;
  • 动态连接:修改间接字(代码);
  • 段的共享:要求纯代码(pure code)。
• 解决方法:共享代码分为”纯段”和”杂段”
  • 纯段共享;
  • 杂段私用:间接字等可修改内容放在杂段中。

第55页：6.5.3 虚拟段页式存储系统

• 虚拟页式:
  • 存储空间静态划分等长区域;
  • 无碎片;
  • 进程空间不能动态扩充,不能动态连接;
  • 共享不方便。
• 虚拟段式:
  • 存储空间动态划分不等长区域(程序单位);
  • 有碎片;
  • 段的动态连接;
  • 便于存储共享和保护;
  • 段长度可动态变化。

第56页：6.5.3 虚拟段页式存储系统（续）

1.基本原理⑴所需表目

①段表

每个进程一个。共享段表入口扩充标志访问权限页表首址页表长度段号leab’l’s

②页表

每个段一个。修改标志内外标志外存块号页框号逻辑页号mibfp

③共享段表

整个系统一个,记录所有共享段。共享计数扩充标志页表首址页表长度段名ceb’l’name

④段名/段号对照表

每个进程一个。

⑤总页表

内、外存各一个。

第57页：6.5.3 虚拟段页式存储系统（续3）

6.5.3虚拟段页式存储系统⑵各表之间联系……段号Si……Sj……P1段表段号Sk……SrP2段表……共享段表……………………页表(私用)页表(共享)……15161718192021……存储空间

第58页：6.5.3 虚拟段页式存储系统（续4）

• 6.5.3虚拟段页式存储系统⑶所需寄存器
• ①段表首址寄存器b:保存正运行进程段表首址;
• ②段表长度寄存器l:保存正运行进程段表长度;
• ③快表修改标志访问权限页框号逻辑页号段号mafps⑷地址映射:: (s, p, d)→(f, d)∪{→}逻辑地址(s, p, d)→物理地址(f, d)

第59页：6.5.3 虚拟段页式存储系统（续5）

6.5.3虚拟段页式存储系统虚拟段页式地址转换l :段表长度b :段表首地址l’ :页表长度b’ :页表首地址逻辑地址(s, p, d)由(s,p)查快表找页框号f找到f?F0≤s≤l-1T访问权限合法?T形成物理地址(f,d)F越权中断间接指令?T有障碍位?F继续执行T连接中断F该页在内存?F缺页中断T(s,p,f)→快表地址转换结束T0≤p≤l’-1T由s和b查段表得页表F逻辑地址(s,p,d)→物理地址(f,d)F越界中断由b’和p查页表得f

第60页：6.5.3 虚拟段页式存储系统（续6）

• 6.5.3虚拟段页式存储系统⑴连接中断:由段名查本进程的段名/段号对照表及共享段表,可能的三种情形:①所有进程都未连接过(共享段表,段名/段号对照表均无)
  • 查文件目录找到该段,为该段建立页表,将该段由文件全部读入swap空间,部分读入内存,填写页表;
  • 为该段分配段号,填写段名/段号对照表;
  • 如该段可共享,填写共享段表,共享记数置1;
  • 填写段表;
  • 根据段号及段内地址形成无障碍指示位的一般间接地址。
• 2.中断处理

第61页：6.5.3 虚拟段页式存储系统（续7）

• ②其它进程连接过但本进程未连接过(共享段表有,段名-段号对照表无)
  • 为该段分配段号;
  • 填写段名/段号对照表,填写段表(指向共享段表),共享段表中共享记数加1;
  • 根据段号及段内地址形成无障碍指示位的一般间接地址。
• ③本进程已连接过(共享段表无,段名/段号对照表有)根据段号及段内地址形成无障碍指示位的一般间接地址。段内地址由两部分构成,即逻辑页号和页内地址。

第62页：6.5.3 虚拟段页式存储系统（续8）

• ⑵缺页中断:调入所需页面,更新页表和总页表。⑶越界中断:
• ①段号越界:访问不存在的段，地址错误处理。
• ②页号越界:如可扩展,扩展该段(增加页),修改页表和段表(页表长度);如不可扩展,错误处理。⑷越权中断:违反段的访问权限，错误处理。

第63页：6.5.3 虚拟段页式存储系统（续9）

各种虚拟存储管理系统特性比较动态连接动态扩充存储保护存储共享存储碎片存储分配地址空间不可不可不便不便无简单一维虚拟页式可以可以方便方便有复杂二维虚拟段式可以可以方便方便无简单二维虚拟段页式特性管理方式

第64页：6.6 系统举例

6.6.1 Linux存储管理6.6.2 Windows Vista存储管理

第65页：6.6 系统举例（续）

• 6.6.1Linux存储管理⑴Physical memory management
  • 页框:静态等长, 4KB;
  • 块组:连续的2i( i = 0, 1, 2,…, 9 )个页框构成一个块组;共10个块组,长度为2i的块组叫作块组i ;
  • 空闲区表:free_area[i]表示页框数为2i的块组,其结构为:
  • 分配/释放:Buddy heap algorithm以2i个页框(块祖)为分配/释放单位( 2i-1＜fn≤2i),fn为要申请的页框数;块组位图指针空闲块组指针
• 1.伙伴堆存储分配算法

第66页：6.6.1Linux存储管理

• 6.6.1Linux存储管理
• 块组位图:
  • 对于块组2i按前后顺序两两结合成一对Buddy,如: 21块组的0、1页框和2、3页框是一对Buddy;
  • 块组位图的1位表示对应的一对Buddy页框块组的使用情况;
  • 对于一对buddy:
• ①若一个空闲,另一个全部或部分占用,则位图相应位置1;
• ②当两个都空闲,或都被全部或部分占用,则位图相应位置0。
• 伙伴条件:
• ①两个块大小相同,即具有相同的页框数b;
• ②两个块的物理地址相连;
• ③位于后面块组的最后页框编号+1必须是2b的整数倍。位图主要用于释放时，位图“异或”判断是否合并块组

第67页：6.6.1Linux存储管理（续）

• 6.6.1Linux存储管理
• 空闲区链表组织结构:假设6个块组块组号块组位图指针空闲块组指针543→210页框号物理内存151413121110987654321001000011110102104page1page12page3page4page14page8map………free_area[i]

第68页：6.6.1Linux存储管理（续3）

• 6.6.1Linux存储管理⑵Buddy heap algorithm
  • 分配:申请fn个页框
• ①从小到大，找到第一个满足fn≤2j的空闲块组j ;
• ②在块组j的第一个空闲块分配2i个页框( 2i-1＜fn≤2i);
• ③调整块组j的空闲块链表;
• ④若2j> 2i,则把2j-2i个空闲页框加入到相应块组空闲链中;(若2j-2i不是2的整数次幂,则将其拆分成不同的整数次幂。)
• ⑤修改位图。
  • 释放:释放2i个页框
• ①释放的2i个页框与相邻的空闲区按伙伴关系合并,即两个相邻的伙伴合并为一个大的空闲区;
• ②把得到的空闲区加入到不同块组的空闲链中;
• ③修改位图。

第69页：6.6.1Linux存储管理（续4）

• 6.6.1Linux存储管理
• 分配例:申请页框数fn=3块组号块组位图指针空闲块组指针543→210页框号物理内存151413121110987654321001000011110102104page1page12page3page4page14page8map………∵21<fn<22∴在块组2的空闲块中分配22个页框。

第70页：6.6.1Linux存储管理（续5）

6.6.1Linux存储管理块组2分配4个页框(8,9,10,11)后,空闲链及位图变化情况如图。块组号块组位图指针空闲块组指针543→210页架号物理内存151413121110987654321001000011110102004page1page3page4page14map………page12page8

第71页：6.6.1Linux存储管理（续6）

• 6.6.1Linux存储管理
• 释放例:释放页框13块组号块组位图指针空闲块组指针543→210页架号物理内存151413121110987654321000000011100102104page1page3page4map……page12释放13后:12,13是伙伴,14,15是伙伴,这两个伙伴构成页框数为4的空闲区,将该空闲区加到块组2。

第72页：6.6.1Linux存储管理（续7）

• 6.6.1Linux存储管理
• Buddy heap algorithm:
  • 问题:internal fragmentation.例如:申请17个页架,由于24＜17≤25,按Buddy heap algorithm,要在块组5的空闲区分配32个页框,造成15个页框的浪费,即internal fragmentation.
  • 解决办法:
• ①second memory allocator当实际申请页框数fn＜2i时,将2i-fn按2的整数次幂切分(carves slabs),由second memory allocator单独管理。
• ②third memory allocator进程物理空间不要求连续时,内存分配由third memory allocator完成。

第73页：6.6.1Linux存储管理（续8）

• 6.6.1Linux存储管理2.虚拟存储管理：请求式虚拟页式存储管理方法。
  • Three level page table:
  • page directory;
  • page middle directory;
  • page table。
  • 虚拟地址:
  • Demand paging:no pre-paging, no working set.
  • Page replacement: two daemons
  • page daemon: kswapdruns once a second ,keep enough free pages in memory.
  • flush daemon: bdflushwakes up periodically, ”dirty page out”.页内偏移页表页中间目录页目录

第74页：6.6.1Linux存储管理（续9）

• 6.6.2Windows Vista存储管理
  • 虚拟存储管理器(Virtual Memory Manager, VMM)负责存储管理;
  • Win32提供一组与存储管理相关的调用;
  • 核心中有6个专门负责存储管理的线程。
• 1.进程地址空间
  • 虚拟地址空间32位地址码，寻址范围4GB；
  • 用户空间:低地址端2GB；
  • 系统空间:高地址端2GB。

第75页：6.6.1Linux存储管理（续10）

6.6.2Windows Vista存储管理Windows Vista虚拟存储空间地址映像非交换区系统空间(2GB)FFFFFFFFH页交换区直接映射区操作系统驻留代码80000000H页交换区用户代码和数据(2GB)7FFFFFFFH00000000H

第76页：6.6.1Linux存储管理（续11）

• 6.6.2Windows Vista存储管理2.存储管理方式:虚拟页式⑴页面尺寸:4KB～64KB;⑵可交换页面:用户空间2GB以页为单位均可交换;系统空间部分页面(动态链接库)可交换。⑶页表结构：二级页表
  • 页目录(Page Directory: PD)每个进程一个,最多210个表项,每个表项存放指向一个页表入口;
  • 页表(Page Table)页表最多210个表项,每个表项存该页号分配的页框号或原型页表表项。

第77页：6.6.1Linux存储管理（续12）

⑷32位虚拟地址6.6.2Windows Vista存储管理11 021 1231 22dPTEPDE页内偏移页表入口页目录入口⑸地址映射dPTEPDECR3+页目录+页表f+4KB

第78页：6.6.1Linux存储管理（续13）

• 6.6.2Windows Vista存储管理3.存储共享及保护
  • 原型页表(Prototype Page Table):对于共享页,页表表项不指向物理页框,而是指向原型页表,原型页表的表项指向实际物理页框号。
  • 页为保护单位，只读、读写、执行、不可操作、写时复制。P页目录0……511512……1023P页表f01f02……………系统页表…………原型页表……共享页…………各表之间的关系

第79页：6.6.1Linux存储管理（续14）

6.6.2Windows Vista存储管理4.内存优先级空闲页框指针内存优先级0123∧4567∧…∧…∧…∧…待机列表standbylist∧

第80页：6.6.1Linux存储管理（续15）

• 6.6.2Windows Vista存储管理进程虚拟页面状态
  • 闲置(free)状态:未分配内存的页面。对闲置状态页面的访问,将导致缺页中断;
  • 预定(reserved)状态：已分配内存,但不可立即使用;只有显示地解除预订状态才可使用,通常用来存储区的预留;
  • 确认(committed)状态:已分配内存并且可访问的页面。
• 5.页面调度

第81页：3 个工人的合作，要求解中不含死锁

习题讲解：P14320.设自行车生产线上有一只箱子,其中有N个位置(N≥3),每个位置可以存放一个车架或一个车轮;又设有3个工人,其活动分别为:工人1活动:do{加工一个车架;车架放入箱中;} while (1)工人2活动:do{加工一个车轮;车轮放入箱中;} while (1)工人3活动:do{箱中取一个车架;箱中取两个车轮;组装为一台车;} while (1)试分别用信号灯与p/v操作、管程、会合实现

第82页：3 个工人的合作，要求解中不含死锁（续）

• 3个工人合作信号灯与p/v操作的实现分析:
  • 工人1放到箱子中的车架数最大为k-2,即至少留出两个车轮的位置;
  • 工人2放到箱子中的车轮数最大为k-1,即至少留出一个车架的位置;
  • 工人1和工人2从箱子两端分别放车架和车轮,两者的存放指针向箱子中间位置移动;
  • 工人3取车架和车轮分别从工人1和工人2的存放位置向箱子两边位置移动;
  • 由于工人1、工人2存放的部件不同,所以其存放位置不能循环、交叉。

第83页：3 个工人的合作，要求解中不含…（续3）

3个工人合作信号灯与p/v操作的实现变量定义:Var B : array [ 0 .. k-1 ] of object ;i : 0 .. k-1;

第84页：3 个工人的合作，要求解中不含

W1:loopProduce a frame;P(S4);P(S1);P(mutex);B[i]:=frame;i:=i+1;V(mutex);V(S2);end;W2:loopProduce a wheel ;P(S5);P(S1);P(mutex);B[j]:=wheel;j:=j-1;V(mutex);V(S3);end;W3:loopP(S2);P(mutex);i:=i-1;f:=B[i];V(mutex);V(S4);V(S1);P(S3);P(S3);P(mutex);j:=j+1;c1:=B[j];j:=j+1;c2:=B[j];V(mutex);V(S5);V(S5);V(S1);V(S1);make a bikeend;3个工人合作信号灯与p/v操作的实现

第85页：3 个工人的合作，要求解中不含（续）

3个工人合作管程的实现typebike= MONITOR;var B: array [ 0 .. k-1 ] of object ;i , j : integer ;count , f_count , w_count : integer ;count_q , f_count_q, w_count_q : condition;f_num_q , w_num_q : condition ;define putin_f , putin_w , getout_f , getout_w ;

第86页：3 个工人的合作，要求解中不含（续3）

procedure putin_w (item : object ) ;beginif w_count = k-1 then wait (w_count_q) ;if count = k then wait ( count_q ) ;B [ j ] := item ; j--;count++; w_count++ ; signal (w_num_q) ;end;3个工人合作管程的实现procedure putin_f (item : object ) ;beginif f_count = k-2 then wait (f_count_q) ;if count = k then wait ( count_q ) ;B [ i ] := item ; i++ ;count++; f_count++ ; signal (f_num_q) ;end;

第87页：3 个工人合作管程的实现

procedure getout_f ( var item : object )beginif f_count = 0 then wait ( f_num_q ) ;i--; item := B [ i ] ;f_count--; count--;signal (f_count_q) ; signal ( count_q ) ;end;procedure getout_w ( var item : object )beginif w_count = 0 then wait ( w_num_q ) ;j++; item := B[j] ;w_count--; count--;signal (w_count_q) ; signal ( count_q ) ;end;

第88页：3 个工人合作管程的实现（续）

begin i:=0; j:=k-1; count:=0; f_count:=0; w_count:=0; end;var work: bike;工人1活动：do{加工一个车架frame;work.putin_f (frame);} while ( 1 )工人3活动：do{ work.getout_f (frame);work.getout_w (wh1);work.getout_w (wh2);make a bike;} while ( 1 )工人2活动：do{加工一个车轮wheel;work.putin_w (wheel);} while ( 1 )

第89页：3 个工人合作管程的实现（续3）

3个工人合作会合的实现taskbikeisentryputin_f , putin_w ;entrygetout_f , getout_w ;endbike ;taskbodybikeisb :array[ 0 .. k-1 ]ofobject;i : 0 .. k-2 ; j : 0 .. k-1 ;count : integer ;begini := 0 ; j := k-1 ; count := 0;loop

第90页：3 个工人合作管程的实现（续4）

3个工人合作会合的实现selectwhen(count < k ) and (i < k-2)=>acceptputin_f ( item :inobject)dob [ i ] := item ;i := i + 1 ;count := count + 1 ;endputin_f ;orwhen(count < k ) and (j > 0) =>acceptputin_w ( item :inobject)dob [ j ] := item ;j := j-1 ;count := count + 1 ;endputin_w ;or

第91页：3 个工人合作管程的实现（续5）

3个工人合作会合的实现when(i > 0) =>acceptgetout_f ( item :outobject)doi := i-1 ;item := b [ i ] ;count := count-1 ;endgetout_f ;orwhen(j < k-1 ) =>acceptgetout_w ( item :outobject)doj := j +1 ;item := b [ j ] ;count := count–1 ;endgetout_w ;endselectendloopendbike ;

第92页：3 个工人合作会合的实现工人

1活动:do {加工一个车架frame ;bike.putin_f(frame) ;} while ( 1 )工人2活动:do {加工一个车轮wheel ;bike.putin_w(wheel) ;} while ( 1 )工人3活动:do { bike.getout_f(frame) ;bike.getout_w(wheel1) ;bike.getout_w(wheel2) ;make a bike by (frame, wheel1, wheel2);} while ( 1 )