例如：
m=5,n＝3,k=3,若系统采用的分配策略是轮流地为每个进程分配资源,则第一轮系统先为每个进程分配1台,还剩下2台;第二轮系统再为2个进程各分配1台,此时,系统中已无可供分配的资源,使得各个进程都处于等待状态,导致系统发生死锁。
问题，若要绝对不发生死锁，最少的资源数量应为多少？
应为
3.死锁产生的条件
1）互斥条件：
进程对其要求的资源进行排他性控制，即一次只允许一个进程使用，如果又有其他进程要求该资源，请求者只能组赛，直到占有该资源的进程用完释放。
2）请求保持条件：
零星地请求资源，即已获得部分资源后，又请求新的资源，而该资源被其他进程占有，此时请求被阻塞，但对已获得的资源保持不放。
3）不可剥夺条件：
进程已获得的资源在未使用完之前不能被剥夺，只能在使用完时由自己释放。
4）环路条件：
发生死锁时，在进程资源有向图中必构成环路，其中每个进程占有一个进程申请的一个或多个资源。
4.死锁的处理
避免策略：
精心地分配资源，动态地回避死锁。
在避免死锁的方法中，把系统的状态分为安全状态和不安全状态，所谓安全状态，是指系统能按某种顺序（如）来为每个进程分配其所需要的资源，直到最大需求，使每个进程都可顺利完成。
称为安全序列；若系统不存在安全序列，则系统处于不安全状态。
只要能使系统始终处于安全状态，便可以避免死锁的发生。
例子：
假定系统有三个进程P1，P2，P3，，系统共有12台磁带机，进程P1总共需要10台磁带机，P2P3分别要求4台和9台。
设在T0时刻，进程P1、P2和P3分别获得5台、2台和2台，尚有3台未分配，如下表所示：
进程
最大需求
已分配
可用
P1
10
5
3
P2
4
2
P3
9
2
试分析T0时刻的安全序列。
银行家算法:
该算法对于进程发出的每一个系统可以满足的资源请求命令加以检测，如果发现分配资源后，系统可能进入不安全状态，则不予分配；若分配资源后系统仍处于安全状态，则分配。
设P表示进程，R表示系统所拥有的资源，进程P请求某类资源Request[j]＝k，表示进程需要k个Rj类型的资源。
在T0时刻存在一个安全序列，系统处于安全状态，当进程P再次发出资源的请求后，系统按下述步骤进行检查：
（1）Requesti<=Needi，则转向步骤
（2），否则认为出错，因为它请求的资源数已经超过它所宣布的最大值。
（2）如果Requesti<＝Available，则转向步骤（3）；否则，表示系统中尚无足够的资源，Pi必须等待。
（3）系统试探把要求的资源分配给进程Pi，并修改系统中的各数值。
Available：
＝Available－Requesti；
Allocation：
＝Allocationi＋Requesti；
Needi：
＝Needi－Requesti；
（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态，若安全，才正式将资源分配给该进程，否则，将试探分配作废，恢复原来的资源分配状态，让该进程Pi等待。
例子：
操作系统分配资源时的一个重要考虑是避免死锁的发生。
若系统中有同类资源16个，由四个进程P1、P2、P3、P4共享。
P1、P2、P3、P4所需的资源总数分别为8、5、9、6.各进程请求资源的次序如下，若系统采用银行家算法为他们分配资源，那么___依次申请分配会使系统进入不安全状态。
序号
进程
申请量
1
P1
6
2
P2
4
3
P3
5
4
P4
1
5
P1
1
6
P2
1
供选择答:
A.3.4B.3.5C.4.5D.5.6
4.2.4进程的同步与互斥
1.进程同步的基本概念
在计算机系统中,多个进程可以并发执行,在这些进程之间存在以下两种关系：
1）资源共享关系2）相互合作关系。
进程间的互斥：
当进程间存在资源共享关系时，如共享CPU等，系统就需要统一的分配资源，保证进程间能互斥的访问这些资源，这种关系就是进程间的互斥。
进程间的同步：
在相互合作关系的进程间，相互合作的进程需要在某些确定点上协调它们的工作,当一个进程到达了这些点后,除非另一进程已经完成了某些操作,否则就不得不停下来等待这些操作结束。
2.临界资源与临界区管理
临界资源：
在多道程序系统中,一次只能供-个进程使用的资源,称为临界资源（criticalresource，CR），如打印机。
临界区：
（criticalsection,CS）是进程中对临界资源实施操作的那段程序。
互斥临界区管理的原则是：
（1）有空即进。
无进程处于临界区时,允许进程进入临界区,并且只能在临界区运行有限的时间。
（2）无空则等。
临界区中有进程时,其他欲进入临界区的进程必须等待,以保证进程互斥地访问临界资源。
（3）有限等待。
对要求访问临界资源的进程,应保证进程能在有限时间进入临界区,以免陷入"饥饿"状态。
（4）让权等待。
当进程不能进入自己的临界区时,应立即释放处理机。
3.信号量机制和PV操作
1）信号量是一个整型变量,根据控制对象的不同赋不同的值。
信号量可分为两类。
●公用信号量：
实现进程间的互斥,初值为资源的数目。
●私用信号量：
实现进程间的同步,初值=0或某个整数。
2）PV操作
PV操作是低级通信原语,在执行期间不可分割。
其中,P操作表示申请一个资源,V操作表示释放一个资源。
P操作可用如下过程表示:
ProcedureP（VarS:
Semaphore）;
Begin
S:
=S-1;
IfS<0thenW（s）{执行P操作的进程插入阻塞队列}
End;
V操作可用如下过程表示:
ProcedureV（VarS:
Semaphore）;
Begin
S:
=S+1;
IfS<=0thenR（s）{从阻塞队列中唤醒一个进程}
End;
4.进程同步与互斥实例
1）信号量实现进程互斥
令信号量的s初值为资源数量,当进程进入临界区时执行P操作,退出临界区时执行V操作。
则进入临界区的代码段如下所示。
P（s）
临界区
V（s）
例
（1）系统中只有一个打印机s＝1
P1（S）
申请得到该打印机
V1（S）
P2（S）
.
.
V2（S）
（2）系统中N个打印机
设S＝N；
P1（S）
申请得到该打印机
V1（S）
....
Pn（S）
申请得到该打印机
Vn（S）
Pn+1（S）被阻塞,至任一完成后唤醒该进程
申请得到该打印机
Vn+1（S）
2）利用信号量实现前趋执行
我们希望执行语句的次序如图，则可以在具有前趋关系的语句间设置信号量，设置信号量初始值为0，写出如下可并发执行的语句，如下：
Begin
BeginS1；V（a）；V（a）；end；
BeginP（a）；S2；V（c）；V（d）；end；
BeginP（b）；S3；V（e）；end；
BeginP（c）；S4；V（f）；end；
BeginP（d）；S5；V（g）；end；
BeginP（e）；P（f）；P（g）；S6；end；
End4-4前趋图
3）利用信号量实现进程同步
进程的同步是由于进程间合作而引起的相互制约的问题。
要实现进程的同步,可用-个信号量与消息联系起来。
当信号量的值为"0"时表示希望的消息未产生,当信号量的值为非“0”时表示希望的消息已经存在。
（1）例，在单缓冲区系统中，生产者进程PI不断地生产产品送入缓冲区,消费者进程P2不断地从缓冲区中提取消费。
为了实现Pl与P2进程间的同步,需要设置一个信号量S1,表示缓冲区空，初值应为__?
可以将产品送入缓冲区;设另一个信号量S2,表示缓冲区有无产品,初值为__?
同步过程如图。
图4-5（a）单缓冲区同步例1
若信号量Sl的初值可以设为0,此时同步过程如图所示。
图4-5（b）单缓冲区例2
例：
设有一个生产者、一个缓冲区和一个消费者,缓冲区可存放n件物品。
生产者不断地生产产品,消费者不断地消费产品。
如何用PV操作实现生产者和消费者的同步。
可以设置3个信号量S、S1和S2,其中,S是个互斥信号量且初值为1,因为缓冲区是一个互斥资源,所以需要进行互斥控制,S1表示是否可以将物品放人缓冲区,初值为n,S2表示缓冲区是否存有物品,初值为0。
同步过程如图2-8所示
图4-6缓冲区容量为n时的同步图
4.3存储管理
存储管理的对象是主存储器（简称主存或内存）。
4.3.1基本概念
将一个用户源程序变为一个可在内存中执行的程序，通常要经过以下几步：
（1）编译。
由编译程序将用户源代码编译成若干个目标模块；
（2）链接。
由链接程序将编译后形成的目标模块以及他们所需要的库函数，链接在一起，形成一个装入模块；
（3）装入。
由装入程序将装入模块装入内存。
图4-7对用户程序的处理步骤
图4-8符号地址、绝对地址、相对地址
（1）虚拟地址:
程序员编写源程序的地址，它从0号单元开始编址,并顺序分配所有地址单元,所以它不是主存中的真实地址,故称为相对地址、程序地址、逻辑地址。
（2）物理地址:
源程序经过汇编或编译后,最后装入到内存中的地址叫绝对地址或物理地址。
4.3.2分区存储管理
存储器管理有两个基本目的:
一是方便用户;二是充分发挥内存的利用率。
按内存分区的划分方式不同可以分为单一连续分区、固定分区、可变分区、可重定位分区。
1.单一连续分区
仅用在早期单用户单任务操作系统中。
将内存分为系统区和用户区。
2.固定分区
固定分区是一种静态分区方式。
在系统生成时已将主存划分为若干个分区,每个分区的大小可不等。
图3-3（a）为分区说明表，图图3-3（b）为存储空间分配情况。
图4-9固定分区
3.可变分区
已分配表：
记录已分配分区的情况；未分配表：
记录未分配区的情况。
为把一个新作业装入内存，需要按照一定的分配算法，从空闲分区表中选出一个分区给该作业。
请求分区主要有如下4种算法.
l）最佳适应算法
假设系统中有n个空白区（自由区）,每当用户申请-个空间时,将从这n个空白区中找到一个最接近用户需求的分区。
这种算法能保留较大的空白区。
但缺点是空闲区不可能刚好等于用户要求的区,所以必然要进行再次分割，会产生许多小到无法再继续分配的小分区，称为外碎片。
2）最差适应算法:
系统总是将用户作业装入最大的空白分区。
这种算法将一个最大的分区一分为二，所以剩下的空白区通常也大,不容易产生外碎片。
但以留下大的空间。
3）首次适应算法:
每当用户作业申请一个空间时,系统总是从主存的低地址开始选择一个能装入作业的空白区。
4）循环首次适应算法:
每次分配都是从刚分配的空白区开始寻找一个能满足用户要求的空白区，减少了查找空闲分区的开销，但是缺少大的空闲分区。
4.可重定位分区
可重定位分区是解决碎片问题的简单而又行之有效的方法。
基本思想是：
移动所有已分配好的分区，使之成为连续区域。
5.覆盖技术
思想：
一个程序不需要一开始把全部指令和数据全部装入内存中再执行。
为有效利用宝贵的内存空间，可把程序分为若干独立的程序段，按照程序的逻辑结构让一些不同时执行的程序段共享同一块内存区，让一部份程序段先驻留在外存，当先头程序已执行完毕的时候，再把后续程序段调入内存覆盖前面的程序段，从逻辑上扩大内存。
但覆盖结构要求程序员在编程时就得划分程序模块，并确定模块之间的调用关系，使不存在调用关系的模块占用相同的主存区进行覆盖。
4.3.3分页存储管理
1．分页原理
将一个进程的逻辑地址空间划分成若干大小相等的区域,称为页。
将主存空间划分成与页相同大小的若干物理块,称为块或页框。
在为进程分配主存时,将进程中若干页分别装入多个不邻接的块中。
2.页表
系统为了保证能在主存中找到每个页面所对应的物理块，系统为每个进程建立一张页面映射表,简称页表。
每个页在页表中占一个表项,记录该页在主存中对应的物理块号。
进程执行时,通过查找页表,就可以找到每页所对应的物理块号。
3.地址结构
分页系统的用户进程的逻辑地址结构如图所示,它由两部分组成前一部分为页号；后一部分图4-10分页存储管理
3112110
页号
页内地址
为页内地址。
图中的地址长度为32位,其中0－11位为页内地址，每个页面多大？
12－31位为页号,所以允许地址空间的大小为多少个页？
4.地址变换机构
图4-11分页存储系统地址变换机构
地址变换机构的基本任务是利用页表把用户程序中的逻辑地址变换成主存中的物理地址，实际上就是将用户程序中的页号变换成主存中的物理块号。
在进行地址变换时,系统对页号与页表长度进行比较,如果页号大于等于页表寄存器中的页表长度L〈页号从0开始〉,则访问越界,产生越界中断。
若未出现越界,则根据页表寄存器中的页表基址和页号计算出该页在页表项中的位置,得到该页的物理块号,将此物理块号装人物理地址寄存器中。
与此同时,将有效地址（逻辑地址）寄存器中的页内地址直接装人物理地址寄存器的块内地址字段中,这样便完成了从逻辑地址到物理地址的变换。
●页式存储系统的逻辑地址是由页号和页内地址两部分组成。
假定页面的大小为4K，地址变换过程如图所示，图中逻辑地址用十进制表示。
图4-12地址变换过程
图中有效地址经过变换后，十进制物理地址a应为___（17）____。
A.33220B.8644C.4548D.2500
5.快表
页式存储管理至少需要2次访存，第一次读取页表，得到数据的物理地址，第二次访存存取数据，若是间接地址，还需要再次访存。
为了提高访存速度，可在地址变换机构中，设置一个小容量的联想存储器，由高速存储器组成，称为快表，用来保存当前访问频率较高的活动页的相关信息，工作方式和高速缓冲存储器相似。
4.3.4分段存储管理
1.分段存储管理方式的引入
1．方便编程；2．分段共享；3．分段保护；4.动态增长；
2.分段系统的基本原理
一、分段
作业的地址空间被划分为若干个段。
每段是一组比较完整的信息单元。
如主程序段、子程序段、数据段。
每个段都从0号单元开始编址，并采用一段连续的地址空间。
段的长度由相应的逻辑信息组长度来决定。
逻辑地址由段号（名）和段内地址所组成。
3116150
段号
段内地址
二、段表
进程中各个段离散的放入内存的分区中。
系统为每个进程建立一张段映射表，为段表。
每个段在段表中占一个表项。
记录该段在内存中的起始地址和该段的长度，实现从逻辑地址到物理内存区的映射。
图4-13段表
三、地址变换机构
设置段表寄存器，存放段表起始地址和段表长度。
在地址变换时，系统将逻辑地址中的段号S与段表程度进行比较，若段号>=段表长度时，表示越界。
若未越界，则根据段表的起始地址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存中的起始地址。
再检查段内地址是否超过该段的段长。
若超过，则越界。
若未越界，则讲该段的基址与段内地址相加，形成最终要访问的内存地址。
如图。
图4-14分段系统的地址变换过程
四、分段和分页的主要区别
（1）页是物理单位，提高内存利用率；
段是信息的逻辑单位，是一组意义相对完整的信息，是为了满足用户的需要。
（2）页的大小是固定的，由系统确定。
段的长度不固定，决定于用户编写的程序。
（3）分页系统的地址变换简单，只需比较页号是否越界。
分段系统需要进行两次越界比较，变换复杂。
4.3.5虚拟存储管理
1.虚拟存储原理
基于程序的局限性：
（l）时间局限性:
如果程序中的某条指令一旦执行,则不久的将来该指令可能再次执行；如果某个存储单元被访问,则不久以后该存储单元可能再次被访问。
产生时间局限性的原因是在程序中存在着大量的循环操作。
（2）空间局限性：
一旦程序访问了某个存储单元,则在不久的将来,其附近的存储单元也最有可能被访问.即程序在一段时间内访问的地址可能集中在一定的范围内,其原因是程序的顺序执行。
2.虚拟存储器定义
基于局部性原理，一个作业在运行之前，没有必要全部装入内存，而仅将那些当前要运行的那部分页面或段，先装入内存便可启动运行，其余部分暂时留在磁盘上。
程序在运行时如果它要访问的页（段）已调入内存，便可继续执行下去；如果程序所要访问的页尚未调入内存（称为缺页或断页），此时程序应利用OS所提供的请求调页（段）功能，将他们调入内存，以使进程能继续执行下去，如果内存已满，还需利用页面置换功能，将暂时不用的页面调至磁盘上，腾出空间后，再将页面装入内存，继续运行。
所谓虚拟存储器，是指仅把作业的一部分装入内存便可运行作业的存储器系统，具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。
3.请求分页的硬件支持
请求分页是在纯分页系统的基础上，增加了请求调页的功能，页面置换的功能等形成的页式虚拟存储系统。
1）请求分页的页表机制。
在纯分页的页表机制中增加若干项，如状态位，辅存地址等。
升级会员 