操作系统2

上一节课我们介绍了记录型信号机制的应用，这节课来介绍and型信号量和信号量集机制
先来回顾上节课提出的问题
有五个哲学家，他们的生活方式是交替地进行思考和进餐。他们共用一张圆桌，分别坐在五张椅子上。在圆桌上有五个碗和五支筷子，平时一个哲学家进行思考，饥饿时便试图取用其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐。进餐完毕，放下筷子又继续思考。

我们当时给出了记录型信号量的解决方案

分析过后也发现若五位哲学家每个人都同时饥饿而拿起了左边的筷子，这使五个信号量 chopstick 均为 0，当他们试图去拿起右边的筷子时，都将因无筷子而无限期地等待下去，即可能会引起死锁。

所以我们在记录型信号量基础上来学习and型信号量，来更好的解决这个问题
AND型信号量集是指同时需要多个资源且每种占用一个资源时的信号量操作。当一段处理代码需要同时获取两个或多个临界资源时，就可能出现由于各进程分别获得部分临界资源并等待其余的临界资源的局面。各进程都会“各不相让”，从而出现死锁。

解决这个问题的一个基本思路是：在一个原语中申请整段代码需要的多个临界资源，要么全部分配给它，要么一个都不分配给它。这就是AND型信号量集的基本思想。

我们称AND型信号量集P原语为Swait(Simultaneous Wait)，V原语为Ssignal(Simultaneous Signal)。
来看一下Swait和Ssignal的定义
![`IS4@HP0D%~1N444RAKTCK.jpg

在Swait时，各个信号量的次序并不重要，虽然会影响进程归哪个阻塞队列，但是因为是对资源全部分配或不分配，所以总有进程获得全部资源并在推进之后释放资源，因此不会死锁。

S1到Sn都表示所需资源，资源数都大于1，可以对每个资源进行申请，分配好资源之后跳出循环，wait操作结束。如果其中某个资源Si得不到满足，会执行else中的内容：把进程放进Si关联的阻塞队列中，然后程序计数器把指针移向wait操作开始。（wait操作是原语，遵循要执行都执行，执行不了就从头重新执行）

signal操作表示的是释放资源，把S1到Sn全部资源释放，并且把S1到Sn关联的阻塞队列全部置空，阻塞队列中的进程直接调度到就绪队列中。
接下来我们就可以用and型信号量很简单的解决哲学家用餐问题了

没有死锁的and信号量解决方法：
semaphore chopstick chopstick[5] = {1,1,1,1,1};

do
{
//think
Sswait(chopstick[i],chopstick[(i+1)%5]);
//eat
Ssignal(chopstick[i],chopstick[(i+1)%5]);
}while(true)

AND型信号量满足了 “多种资源，数量为1”的使用情景，但是实际上还会有多种资源数量不固定的情景，AND型信号量显然处理不了这种情况的进程调度。为了解决多资源多数量的情况，就出现了信号量集。

一般“信号量集”是指同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的信号量处理。由于—次需要n个某类临界资源，因此如果通过n次wait操作申请这n个临界资源，操作效率很低，并可能出现死锁。

—般信号量集的基本思路就是在AND型信号量集的基础上进行扩充，在一次原语操作中完成所有的资源申请。进程对信号量Si的测试值为ti(表示信号量的判断条件，要求Si>ti即当资源数量低于ti时，便不予分配)，占用值为di（表示资源的申请量，即Si=Si—di)。对应的P、V原语格式为：

一般“信号量集”可以用于各种情况的资源分配和释放。下面是几种特殊的情况：
1)Swait(S，d，d)表示每次申请d个资源，当资源数量少于d个时，便不予分配。

2)Swait(S，1，1)表示互斥信号量。

3)Swait(S，1，0)可作为一个可控开关(当S≥1时，允许多个进程进入临界区；当S=0时禁止任何进程进入临界区)。

大家可以看到记录型信号量和and型都是信号量集的一种特例

信号量我们就介绍这些

下面我们来学习本章的最后一部分死锁

2.8

请结合课本一起学习
死锁这部分大家应该学习完了
这部分也是这章里的一个重点，里面有一个银行家算法需要重点掌握
我们下次课就来给大家加深讲解一下银行家算法，做一些相关题目
这节课布置一个pv的课下作业，大家回家练习

这节课先把上次慕课死锁和银行算法给大家归纳总结一下

死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。

产生死锁的必要条件

① 互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。

② 请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。

③ 不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。

④ 环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。

注意是必要条件
理解了死锁的原因，尤其是产生死锁的四个必要条件，就可以最大可能地避免、预防和解除死锁。所以，在系统设计、进程调度等方面注意如何能够不让这四个必要条件成立，如何确定资源的合理分配算法，避免进程永久占据系统资源。此外，也要防止进程在处于等待状态的情况下占用资源,在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配 。因此，对资源的分配要给予合理的规划。

Dijkstra在1965年提出的银行家算法是著名的死锁避免算法，这个用于一个银行家给多个顾客贷款的算法可以直接用于操作系统给进程分配资源，这时只要把银行家换成操作系统，把顾客换成进程，把资金换成资源，把银行家决定是否放贷时所用的判断过程（即判断顾客是否有信誉和偿还能力）换成操作系统决定是否分配资源时所用的判断过程（即判断进程是否能及时归还资源）即可。为了描述银行家算法，下面先介绍一下系统的安全状态的概念。

需要注意：

（1）系统在某一时刻的安全状态可能不唯一，但这不影响对系统安全性的判断。
（2）安全状态是非死锁状态，而不安全状态并不一定是死锁状态。即系统处于安全状态一定可以避免死锁，而系统处于不安全状态则仅仅可能进入死锁状态。

银行家算法的实质就是要设法保证系统动态分配资源后不进入不安全状态，以避免可能产生的死锁。即没当进程提出资源请求且系统的资源能够满足该请求时，系统将判断满足此次资源请求后系统状态是否安全，如果判断结果为安全，则给该进程分配资源，否则不分配资源，申请资源的进程将阻塞。

具体的说就是：每一个新进程进入系统时，必须声明需要每种资源的最大数目，其数目不能超过系统所拥有的的资源总量。当进程请求一组资源时，系统必须首先确定是否有足够的资源分配给该进程，若有，再进一步计算在将这些资源分配给进程后，是否会使系统处于不安全状态如果不会才将资源分配给它，否则让进程等待。

基本流程大家了解了 接下来我们看一下相关数据结构和实现的步骤

相关数据结构如下：

1) 可利用资源向量Available。这是一个含有m个元素的数组，其中的而每一个元素代表一类可利用资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态的改变。如果Available[j]=K,则表示系统中现有Rj类资源K个。
2) 最大需求矩阵Max。这是一个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K；则表示进程i需要Rj类资源的最大数目为K。

3) 分配矩阵Allocation。这也是一个nm的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的数目为K。
4) 需求矩阵Need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K,则表示进程i还需要Rj类资源K个，方能完成任务。

上述三个矩阵间存在下述关系：Need[i,j]=Max[i,j]-Allocation[i,j]

算法思路分两部分

第一部分：银行家算法模块

1．如果Request<=Need,则转向2;否则,出错

2．如果Request<=Available,则转向3,否则等待

3．系统试探分配请求的资源给进程

4．系统执行安全性算法

第二部分:安全性算法模块

1. 设置两个向量

① 工作向量:Work=Available(表示系统可提供给进程继续运行所需要的各类资源数目)

② Finish:表示系统是否有足够资源分配给进程(True:有;False:没有).初始化为False

1. 若Finish[i]=False&&Need<=Work,则执行3;否则执行4(i为资源类别)

2. 进程P获得第i类资源,则顺利执行直至完成，并释放资源: Work=Work+Allocation; Finish[i]=true;转2

3. 若所有进程的Finish[i]=true,则表示系统安全;否则,不安全
   

   详细设计如下：在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配 。因此，对资源的分配要给予合理的规划。
   

   设Request i是进程Pi的申请向量，如果Request i[j]=K,则表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：

   1) 如果Request i[j]<=Need[i,j]，便转向步骤2）；否则认为出错，因为它所需要的资源数已经超过它所宣布的最大值。

2) 如果Request i[j]<=Available[i,j]，便转向步骤3）；否则，表示尚无足够资源，Pi需等待。

3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：

Available[j]:=Available[j]-Request i[j];

Allocation[i,j]:=Allocation[i,j]+Request i[j];

Need[i,j]:=Need[i,j]-Request i[j];

4) 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

系统所执行的安全性算法可描述如下：

1) 设置两个向量

① 工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work：=Available。

② Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]:=false;当有足够资源分配给进程时，再令Finish[i]:=ture.

大家需要注意的是work的含义和初值

2) 从进程集合中找到一个满足下述条件的进程：

① Finish[i]=false;

② Need[i,j]<=Work[j];若找不到，执行步骤3），否则，执行步骤4）。

3） 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

Work[j]:=Work[j]+Allocation[i,j];

Finish[i]:=true;

Go to step 2;

4) 如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

整个算法的流程图大家可以看一下

书本上面的算法介绍太过书面化，这里就不再介绍，直接用一个例子来说明：
假定系统中有五个进程{p0,p1,p2,p3,p4}和三类资源{A,B,C}各类资源的数目分别是10,5,7，已知T0时刻资源分配情况如下：

![R`U7V29%%C1ZD{{2~R@}~T.jpg

先来计算一下T0时刻是否安全

如上图所示是我们的已知条件也就是我们开始时候的资源分配状态，接下来我们要求这个状态下的安全序列，也就是将可利用的资源分配给某个需要资源小于可利用资源的进程，让这个进程运行完成，进程运行完成之后已分配的资源就会被释放，然后继续执行上述操作，只要能找到满足Need小于Available，就分配资源，让该进程运行完成，最后将资源释放，也就是将已分配的资源加到可利用的资源，如果最后每一个进程都能运行完成就得到了我们的安全序列，所以系统就是安全的，如果存在一个进程，可利用资源不能满足需求就不再分配

具体过程如下
（1）将Available和Need对比，P0的Need>Available,不满足，往后找，
（2）P1的need小于available，分配给P1，P1就能运行完成，最后释放资源{2,0,0}
所以现在的资源就是{3,3,2}+{2,0,0}={5,3,2}
（3）然后继续向下找，P3满足条件，将资源分配给P3，让其运行完成，并释放空间{2,1,1}，所以现在的资源就是{5,3,2}+{2,1,1}={7，4,3}
（4）依次类推得到安全序列为{P1,P3,P4,P2,P0}
过程如下图，其中finish表示进程运行完成

![)KD2Y@YRP}K)Q4K~P6HX)V.jpg

所以我们知道该系统是安全的 ，当然安全序列不是唯一的。下来再来一个问题假设P1请求资源Request{1,0,2},要怎样处理呢 ？

首先要检测看请求资源是不是比可利用资源和需要资源小，如果其中一个或两个条件都不满足，进程等待，如果满足进行下面操作，
这里{1,0,2}是满足这两个条件的
我们进行的操作就是将请求资源加到Allocation上面，也就是已分配的资源得到扩充，同样的请求的资源一定是来自可利用资源的，所以可利用资源要减上一个请求资源数目，因为Need和Allocation的和是一个固定值max所以相应的Allocation加上一个数值，Need就要减上一个数值，变化之后如下图所示：

然后再像前面一样，把这个表当成T0时刻的资源分配状态，再来找安全序列，判断系统是不是安全的。

大家可以自己按流程计算一下

这部分我们一会再留一个课后作业大家自己回去进一步练习一下

上次课的留的信号量集的作业大家来看一下

![U@B~F}4%1WF%EL~XCVH6L6.jpg

这里我增加了一个限制就是最多允许RN个读者一起读 ，所以信号量L就是控制读者数量的

L初值为RN，每进去一个读者L减1

就是swait（L，1，1）

再看writer进程 、

swait（mx，1，1；L，RN，0）

这条一句描述了两个条件

即里面没有写者

也就是mx大于等于1

L大于等于RN，说明里面也没有读者

两个条件都满足，写者进去写，做mx减1
swait（…L，RN，0），这条只起条件判断，执行语句其实是无意义的

下面时间我们来学习下一章存储器

3.1

我们布置个课后作业

上一节课我们通过慕课学习了存储管理3.1基本概念这一节
这节课我们在慕课的基础上先把3.1的知识点归纳总结一下，然后学习3.2页式管理

分区存储管理是把主存储器中的用户区作为一个连续区或分成若干个连续区进行管理，每个连续区中可装入一个作业。多道程序系统一般都采用多个分区的存储管理，具体可分为固定分区和可变分区两种方式。
3.1中我们就重点介绍了这两种分区方式

我们先来归纳总结一下固定分区管理模式

固定分区存储管理就是把主存中可分配的用户区域预先划分成若干个连续的分区，每个连续区的大小可以相同，也可以不同。但是，一旦划分好分区之后，主存中分区的个数就固定了，且每个分区的大小也固定不变。所以叫固定分区，显然这是一种静态分区法。

每个分区用来装入一个作业，由于主存中有多个分区，就可同时在每个分区中装入一个作业。所以，这种存储管理方式是适用于多道程序系统的

![XL5JU]V8U[QACK8F$$W94F.jpg

看图可以更好地理解这种分区的原理

显然为了管理主存空间的使用，必须设置一张“主存分配表”（分区说明表），用来说明各分区的分配情况。
![){}82TBF{2}{BAVQHK1EZC.jpg
当作业队列中有作业要装入主存时，存储管理可采用“顺序分配算法”进行主存空间的分配。顺序查看主存分配表，找到一个标志为“0”的并且长度大于或等于欲装入作业的地址空间长度的分区就可以了
这种固定分区模式的地址转换一般采用静态重定位技术

如果内存需要扩充则采用覆盖技术

固定分区的优缺点也很明显，优点：实现简单，无外部碎片。缺点：a.当用户程序太大时，可能所有的分区都不能满足需求，此时不得不采用覆盖技术解决，但这又会降低性能。b.会产生内部碎片，碎片大，存在小分区占用大作业的情况，内存利用率低。

目前已经基本上没有什么场合使用固定分区模式了
接下来我们来总结一下可变分区

它与固定分区的区别就是：动态的划分分区。
具体地说就是这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要，因此系统分区的大小和数目是可变的。
所以又称变长分区模式、动态分区分配模式

在理解可变分区模式的时候需要注意几点：
1.可变分区模式下，刚开始，OS就绪，但任何用户程序未进入内存前整个用户内存区是一大空间。已占用区和空闲分区并不是绝对的。
2.必须有表来记录分区的情况。
3.程序进入内存时的例行工作就是分配空闲区和装入程序，并修改相应的空闲表和已分配区表。
4.一旦一个内存分区被分配给一个进程，该进程可以被装入该块中执行，装入时需重定位。

可变分区的实现过程同样的系统要相应的数据结构来记录内存的使用情况

大家在慕课里已经对这种表结构学习过了
可以通过图浏览加深一下记忆

可变分区的分配方式就是当有作业要装入内存时，在空闲区表中找一找“ 未分配 ”的栏目，从中找出一个能容纳作业的空闲区。若空闲区大于作业的长度时则被分成两部分，一部分分配给作业；另一部分仍作为空闲区登记在表中。若找到的空闲区等于作业长度时,分配后该栏目状态改为“空”状。

显然这种动态的按需分配模式有效地解决了固定分区方式中由于分区内部剩余内存空置所形成的内部碎片的问题。
当一个新作业装入内存时，我们也看到是需要按照一定的算法，从空闲分区表（或空闲分区链）中选出一个分区分配给该作业的
慕课里也介绍了常用几种分区算法，我们也在这里简单总结对比一下
最先（首次）适应分配算法：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。

这种算法优点是实现简单，缺点是可能将低地址处大的空闲区分割成许多小的空闲区，形成许多不连续的“碎片”。碎片长度可能不能满足作业要求，降低了内存利用率。

最佳适应算法：空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区表，找到大小能够满足要求的第一个空闲分区。

这种算法貌似最佳，尽可能地选择了最适合的分区空间，但也因此产生大量的不能被使用的很小的空闲区。因此这种方法会产生很多的外部碎片。所以该算法分配效果不一定是最佳的。

为了解决最佳适应算法的问题——即留下太多难以利用的小碎片，我们转换思路考虑可以在每次分配时，优先使用最大的连续空闲区，这样分配后的空闲区就不会太小，更方便使用。这就是最坏适应算法

显然这种算法分割后产生的空闲区一般仍可以供以后分配使用。但工作一段时间后，也不能满足大作业对空闲区的请求。

三种分区算法总结如下图

![T3HUKSOLSJQ@DO$)@)P23F.jpg

供大家留存参考

动态分区的回收这里我就不再说了，书上和慕课已经阐述的比较清晰

继续看一下动态分区的地址转换模式

显然，采用可变分区方式时，一般采用动态重定位方式装入作业

它的内存扩充方面，虽然消除了固定分区造成的“内碎片”，但是不可避免的在内存空间造成“外碎片”。我们一般采用移动（紧缩）技术进行内存扩充，定时的或在内存紧张时，将内存中所有作业移到内存的一端，使其相邻。

那么我们也看到经过紧缩后的进程在内存中的位置发生了变化，若不对程序和数据的地址进行修改，在进程就无法运行。要使其运行，必须进行“动态重定位”

3.1我们就归纳总结这些，供大家参考整理课堂笔记
接下来我们继续学习3.2页式存储管理

3.2

我们还是在慕课基础上对页式存储管理归纳总结一下。

前面的分区分配是基于连续分配模式的，就是为用户进程分配的必须是一个连续的内存空间。而分页是基于非连续分配模式，就是为用户进程分配的是一些分散的内存空间。

我们就先来看一下这种分页存储的基本思路

我们举个例子，假设进程A的大小为23MB，但是每个分区的大小只有10MB，如果进程只能占用一个分区，显然是放不下的。
给出一个解决思路：如果允许进程占用多个分区，那么可以把进程拆分成10MB + 10MB + 3MB三个部分，再把这三个部分别放在三个分区中（这些分区不要求连续）…
细节考虑一下，进程A最后的一部分只有3MB，放入分区会产生一个7MB大小的内部碎片。如果将每个分区的设为2MB，那么进程A就会拆成11 * 2MB + 1MB共12个部分。最后一个部分1MB不会占满分区，会产生1MB碎片。

显然，如果把分区设置的更小一点，内部碎片会更小，内存利用率会更高。

基本分页存储管理的思想就是把内存划分为一个个相等的小分区，再按照分区的大小将进程拆分成一个个小部分。

我们今天就先大概看一下分页的基本思路，具体实现下一次课总结

将内存空间分为一个个大小相等的分区，将用户进程的地址空间也分为与页框大小相等的一个个区域，称为页面或页。页框的大小不能太大，否则可能会产生过大的内存碎片。

操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中，即进程的页面和内存的页框有一一对应的关系。

大家稍等 图片传的有点慢

![PGD)NK43]1$SPWO43KKME1.jpg
![]LN~QNQFUB41`GCQ_FSH%P.jpg

显然这种方式各个页面不必连续存放，也不必按先后顺序，可以放在不相邻的各个页框中。

那么要想实现这种页式离散存储，就要涉及到逻辑地址结构、页表的映射，地址转换等细节问题

下次课我们就来总结一下页式存储管理的实现细节

我们今天来归纳总结一下页式存储管理实现的一些细节问题

上节课大家通过慕课这部分的学习已经对分页这种方式有了一些了解

我们先来看一下页表

页表是记录逻辑空间（虚拟内存）中每一页在内存中对应的物理块号。但并非每一页逻辑空间都会实际对应着一个物理块，只有实际驻留在物理内存空间中的页才会对应着物理块。

关于页表总结如下几点

(1) 一个进程对应一张页表。
(2) 进程的每一页对应一个页表项。
(3) 每个页表项由页号和块号组成。
(4) 页表记录进程页面和实际存放的内存块之间的对应关系。
(5) 每个页表项的长度都是相同的，页号是隐含的

通常页表是需要一直驻留在物理内存中的（多级页表除外），进程在未执行时，页表的起址和页表长度放在进程控制块（PCB）中，当进程被调度时，操作系统内核会把它们放在页表寄存器中。

接下来了解一下逻辑地址结构 。页式存储管理中，逻辑地址可以解读成页号+地址偏移量（页内地址）。如下图所示：

图中是一个 32 位的逻辑地址，高 20 位是页号，低 12 位是页内地址。

一般来说已知逻辑空间地址为2^m个字节（也就是说逻辑地址的长度是m位），已知页大小是2^n字节。

那么页内地址就为n位；页号m-n位，意味着该进程一共可以有2^(m-n)个页面

或者如果给的逻辑地址是十进制，逻辑地址为 A，页面大小为 L，则页号 P 和页内地址 d 计算公式如下：

也就是说如果逻辑地址给的是二进制，可以通过页面大小或者页数来划分页号和页内地址；而如果给的逻辑地址是十进制就可以通过上面的公式计算分割出页号和页内地址 。
接下来我们重点看地址转换
就是分页中一个逻辑地址如何让转化成物理地址
![]S87J%O0U)VTN$4E%C1AK4.jpg

这个图慕课里面已经和大家讲过

我们总结一下转换的步骤

1、进程访问某个逻辑地址时，分页地址机构自动将逻辑地址分为页号和页内地址

2、页号大于页表长度，越界错误

3、若不越界，则页表项的地址 p = 页表起始地址 F + 页号 P * 表项大小 S，从而找到页表项里页号对应的物理块号 B
页和物理块的大小是一致的，所以 页内地址=块内地址

4、得到物理块号后，如果是二进制，物理地址 = 物理块号B + 页内地址（+为组合的意思，不是做加法）
如果是十进制，物理地址 = 物理块号 B * 页大小 L + 页内地址（+为做加法）

大家可以观察转换时这种映射关系

我们举一个十进制，一个二进制的例子来看一下具体转换的计算

例：某系统采用分页式存储管理，页大小为 2KB。已知进程 A 的逻辑地址空间为 4 个页，内存分配如下页表所示，求逻辑地址 4832 对应的物理地址。（所有数据都是十进制）

所有数据都是十进制，所以我们用十进制的转化公式

首先页面大小2KB=2048B，所以：

页号 P=逻辑地址/页大小=4832/2048=2

页内地址 F=逻辑地址%页大小=4832%2048=736

根据页表查得 2 号页对应着 25 号物理块

物理地址 A=物理块号页大小 + 页内地址=252048+736=51936

再来看一个二进制转化的例子

例：某用户编程空间共64个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：

页号 物理块号

0 3

1 7

2 9

3 5

则逻辑地址0A5C(H)所对应的物理地址是什么？

十六进制的逻辑地址

显然十六进制转化成二进制最方便

用户编程空间共64个页面，２ˆ6＝64，所以页号部分占6位，由“每页为1KB，1K=2^10，可知内页地址占10位。

逻辑地址0A5C（H）所对应的二进制表示形式是：００００１０１００１０１１１００，后十位１００１０１１１００是页内地址，那么0 0０００１０即为页号

页号化为十进制是２，在对照表中找到页号２对应的物理块号是9。

9转换二进制是1 0 0１，物理地址 = 物理块号B + 页内地址（+为组合的意思，不是做加法），组合之后即可求出物理地址为１０ 0１１００１０１１１００，再化成十六进制为２6５Ｃ

也就是逻辑地址0A5C(H)所对应的物理地址是２6５Ｃ

分页的地址变换我们就介绍这么多 ，关于分页其他知识点慕课里已经介绍的很详细了，我们就不再重复了。

接下来我们做课堂练习，做几个地址转换的题目练习一下

1、考虑一个由8个页面，每页有1024个字节组成的逻辑空间，把它装入到有32个物理块的存储器中，问：

（1）逻辑地址需要多少二进制位表示？

（2）物理地址需要多少二进制位表示？

2、若在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为1024字节，试将逻辑地址1011，2148，4000，5012转化为相应的物理地址。

3、某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：

![PDV[8CY09}(JDVYN0G(0D5.jpg

则逻辑地址0A5C（H）所对应的物理地址是什么？

@全体成员 这三个练习题大家现在抓紧时间做，20分钟后我来讲一下

先来看第一题：因为页面数为8=2^3，故需要3位二进制数表示页号。每页有1024个字节，1024=2^10，于是页内地址需要10位二进制数表示页内地址；32个物理块，需要5位二进制数表示块号（32=2^5）。

所以（1）页的逻辑地址由页号和页内地址组成，所以需要3+10=13位二进制数表示。
（2）页的物理地址由块号和页内地址的拼接，所以需要5+10=15位二进制数表示。

第二题：为了描述方便，设页号为p，页内位移为d

（1）对于逻辑地址1011，p＝int（1011/1024）＝0，d＝1011 mod 1024＝1011。查页表第0页在第2块，所以物理地址为1024′2＋1011＝3059。

2）对于逻辑地址2148，p＝int（2148/1024）＝2，d＝2148 mod 1024＝100。查页表第2页在第1块，所以物理地址为1024＋100＝1124。

3）对于逻辑地址4000，p＝int（4000/1024）＝3，d＝4000 mod 1024＝928。查页表第3页在第6块，所以物理地址为1024′6＋928＝7072。

（4）对于逻辑地址5012，p＝int（5012/1024）＝4，d＝5012 mod 1024＝916。因页号超过页表长度，该逻辑地址非法。

第三题和例题基本一样，页表有一些变化

第三题：由已知条件“用户编程空间共32个页面”，可知页号部分占5位；由“每页为1KB”，1K=2^10，可知内页地址占10位。由“内存为16KB”，可知有16块，块号为4位。

逻辑地址0A5C（H）所对应的二进制表示形式是：000 1010 0101 1100，根据上面的分析，10位页内地址，则编码“000 10”为页号，表示该逻辑地址对应的页号为2。查页表，得到物理块号是4（十进制），即物理块地址为：01 00 ，拼接块内地址10 0101 1100，得01 0010 0101 1100，即125C（H）。

解逻辑地址0A5C（H）所对应的物理地址是125C（H）。
分页我们就介绍这些 ，下面我们来学习分段的存储管理模式

3.3

前面学习的分页的主要目的是为了实现离散分配,提高内存利用率。分页仅是系统管理上的需要，完全是系统行为，对用户是不可见的。这小节学习的分段中段是信息的逻辑单位。分段的主要目的是更好地满足用户需求.一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。

时间关系，我们先了解一下分段的基本概念， 下小节课再详细总结分段实现的细节