简介
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系
银行家算法
统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。
要解释银行家算法，必须先解释操作系统安全状态和不安全状态。
安全序列是指一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。
安全状态
如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。
不安全状态
不存在一个安全序列。不安全状态不一定导致死锁。
[编辑本段]银行家算法的数据结构
1）可利用资源向量Available
是个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果Available［j］=K，则表示系统中现有Rj类资源K个。
2）最大需求矩阵Max
这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max［i,j］=K，则表示进程i需要Rj类资源的最大数目为K。
3）分配矩阵Allocation
这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果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) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客;
(2) 顾客可以分歧贷款,但贷款的总数不能超过最大需求量;
(3) 当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款;
(4) 当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金.
操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。
运行平台：Windows XP VS2005
编程语言：C#
[编辑本段]算法的实现
初始化
由用户输入数据，分别对可利用资源向量矩阵AVAILABLE、最大需求矩阵MAX、分配矩阵ALLOCATION、需求矩阵NEED赋值。
银行家算法
在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。
银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。
设进程cusneed提出请求REQUEST [i]，则银行家算法按如下规则进行判断。
(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，则转(2)；否则，出错。
(2)如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i]，则转(3)；否则，出错。
(3)系统试探分配资源，修改相关数据：
AVAILABLE[i]-=REQUEST[cusneed][i];
ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];
NEED[cusneed][i]-=REQUEST[cusneed][i];
(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。
安全性检查算法
(1)设置两个工作向量Work=AVAILABLE;FINISH
(2)从进程集合中找到一个满足下述条件的进程，
FINISH==false;
NEED<=Work;
如找到，执行(3)；否则，执行(4)
(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。
Work+=ALLOCATION;
Finish=true;
GOTO 2
(4)如所有的进程Finish= true，则表示安全；否则系统不安全。
[编辑本段]算法
/// 资源数
public static int resourceNumber;
/// 进程数
public static int processNumber;
/// 可用资源数组
public static int[] Available;
/// 工作向量
public static int[] work;
/// 它表示系统是否有足够的资源分配给进程
public static bool[] Finish;
/// 最大需求矩阵
public static int[][] Max;
/// 分配矩阵
public static int[][] Allocation;
/// 需求矩阵
public static int[][] Need;
/// 安全序列
public static int[] SafeSequence;
/// 资源请求向量
public static int[] Request;
算法思想：
主要是：递归+深度优先搜寻+回溯
算法源代码如下：
/// 深搜+回溯实现银行家算法
/// 已完成的进程数
public void DFS_searchSafeSequence(int n)
{
if (n == processNumber)
{
//找到一个安全序列,可以显示所有安全序列
//显示在richTextBoxshow.Text上
for (int i = 0; i < processNumber; i++)
{
richTextBoxshow.Text += SafeSequence[i] + " ";
}
richTextBoxshow.Text += "\n";
return;
}
for (int i = 0; i < processNumber; i++)
{
if (Finish[i] == false)//进程尚未完成
{
//判断现有资源是否可以满足这个进程
bool isOK = true;
for (int j = 0; j < resourceNumber; j++)
{
if (Need[i][j] > work[j])
{
isOK = false;
break;
}
}
//可以满足
if (isOK)
{
//先试探的将资源分配给这个进程
for (int j = 0; j < resourceNumber; j++)
{
work[j] += Allocation[i][j];
}
//已经完成
Finish[i] = true;
//加入安全序列
SafeSequence[n] = i;
//继续搜索
DFS_searchSafeSequence(n+1);
//回溯
Finish[i] = false;
SafeSequence[n] = -1;
for (int j = 0; j < resourceNumber; j++)
{
work[j] -= Allocation[i][j];
}
}
}
}
}
转载自：
http://baike.baidu.com/view/93075.htm
2010年6月24日星期四
中断处理过程
一个完整的中断处理过程应该包括：中断请求、中断排队或中断判优、中断响应、中断处理和中断返回等环节，下面分别进行讨论。
1．中断请求
中断请求是由中断源向CPU发出中断请求信号。外部设备发出中断请求信号要具备以下两个条件：
（1）外部设备的工作已经告一段落。例如输入设备只有在启动后，将要输入的数据送到接口电路的数据寄存器（即准备好要输入的数据）之后，才可以向CPU发出中断请求。
（2）系统允许该外设发出中断请求。如果系统不允许该外设发出中断请求，可以将这个外设的请求屏蔽。当这个外设中断请求被屏蔽，虽然这个外设准备工作已经完成，也不能发出中断请求。
2．中断排队
中民申请是随机的，有时会出现多个中断源同时提出中断申请。但CPU每次只能响应一断源的请求，那么究竟先响应哪一个中断源的请求呢？这就必须根据各中断源工作性质的轻重缓急，预先安排一个优先级顺序，当多个中断源同时申请中断时，即按此优先级顺序进行排队，等候CPU处理。一般是把最紧迫和速度最高的设备排在最优先的位置上。CPU首先响应优先级别最高的中断源。当中断处理完毕，再响应级别低的中断申请。
中断排队可以采用硬件的方法，也可以采用软件的方法。前者速度快，但需要增加硬设备；后者无需增加硬设备，但速度慢，特别是中断源很多时尤为突出。
软件优用查询技术。当CPU响应中断后，就用软件查询以确定是哪些外设申请中断，并判断它们的优先权。一个典型的软件优先权排队接口电路如图6－10所示，图中把8个外设的中断请求触发器组合起来，作为一具端口，并赋以设备号。把各个外设的中断请求信号相“或”后，作为INTR信号，故其中任一外设有中断请求，都可向CPU送出INTR信号。当CPU响应中断后，把中断寄存器的状态作为一个外设读入CPU，逐位检测它们的状态，若哪一位为1，则该位对应的外设有中断请求，应转到相应的服务程序的入口。其流程如图6－11所示。
相应的查询程序如下：
XOR AL，AL ；CF清0
IN AL，20H ；输入中断请求触发器的状态
RCL AL，1 ；左移一位，检测最高位是否有请求
JC POW ；有，转相应服务程序
RCL AL，1 ；否，检测下一位
JC DISS
…
查询方法的优点是：
（1）询问的次序，即优先权的次序。显然，最先询问的，优先权的级别最高。
（2）省硬件。不需要有判断与确定优先权的硬件排队电路。
缺点是：由询问转至相应的服务程序入口的时间长，尤其是在中断源较多的情况下。
硬件优先权排队电路，目前均采用专用中断管理接口芯片如8259A等。
3．中断响应
经中断排队后，CPU收到一个当前申请中断的中断源中优先级别最高的中断请求信号，如果允许CPU响应中断（IF＝1），在执行完一条指令后，就中止执行现行程序，而响应中断申请。此时首先由硬件电路保护断点，即将当前正在执行的程序的段地址（CS）和偏移地址（IP）以及标志寄存器（FR）压入堆栈；然后关闭CPU内的允许中断触发器IF（可屏蔽中断时）；接下来就是寻找中断服务程序的入口地址。
寻找中断服务程序入口地址的方法分软件和硬件两种。软件方法即为上述的查询方式。在硬件方式中，目前均采用矢量中断方式。所谓矢量中民即当CPU响应中断后，由提出中断请求的中断源向CPU发去一个中断矢量，CPU根据这个中断矢量找到中断程序的入口地址，而转到相应的中断服务程序。以Intel为CPU的PC系列微型计算机系统就采用矢量中断方式。
4．中断处理
中断响应后，进入中断处理，即执行中断服务程序。在中断服务程序中，首先要保护现场，把中断服务程序中所要使用到的寄存器内容保护起来，如将经们的内容压入堆栈，然后才进行与此次中断有关的相应服务处理。处理完毕要恢复现用到的寄存器内容保护起来，如将经们的内容压入堆栈，然后才进行与此次中断有关的相应服务处理。处理完毕要恢复现场，即恢复中断前各寄存器的内容。如果在中断服务程序中允许嵌套（可屏蔽中断方式时），还应用STI指令将IF＝1（即开中断）。
5．中断返回
通常，中断服务程序的最后一条指令是一条中断返回指令。当CPU执行这条指令时，把原来程序被中断的断点地址从堆栈中弹回CS和IP中，原来的FR弹回FR。这样，实中断的程序就可以从断点处继续执行下去。CPU从中断服务程序又回到了被中断的主程序。
在实际应用系统中，中断可以嵌套，即可以有多重中断。所谓多重中断，就是在CPU执行某一中断服务程序时，又有优先级别更高的中断源申请断，此时，CPU应当暂停止这个中断服务，而去处理优先级别比它高的中断申请。处理完毕再返回中断占，继续处理较低优先级别的中断。这种在低级中断中还嵌套有高级中断的多重中断方式，对实时处理系统是很有用的。
转载自：
http://202.116.0.161/wjyl/site/text/chapter6/6.3.2.htm
1．中断请求
中断请求是由中断源向CPU发出中断请求信号。外部设备发出中断请求信号要具备以下两个条件：
（1）外部设备的工作已经告一段落。例如输入设备只有在启动后，将要输入的数据送到接口电路的数据寄存器（即准备好要输入的数据）之后，才可以向CPU发出中断请求。
（2）系统允许该外设发出中断请求。如果系统不允许该外设发出中断请求，可以将这个外设的请求屏蔽。当这个外设中断请求被屏蔽，虽然这个外设准备工作已经完成，也不能发出中断请求。
2．中断排队
中民申请是随机的，有时会出现多个中断源同时提出中断申请。但CPU每次只能响应一断源的请求，那么究竟先响应哪一个中断源的请求呢？这就必须根据各中断源工作性质的轻重缓急，预先安排一个优先级顺序，当多个中断源同时申请中断时，即按此优先级顺序进行排队，等候CPU处理。一般是把最紧迫和速度最高的设备排在最优先的位置上。CPU首先响应优先级别最高的中断源。当中断处理完毕，再响应级别低的中断申请。
中断排队可以采用硬件的方法，也可以采用软件的方法。前者速度快，但需要增加硬设备；后者无需增加硬设备，但速度慢，特别是中断源很多时尤为突出。
软件优用查询技术。当CPU响应中断后，就用软件查询以确定是哪些外设申请中断，并判断它们的优先权。一个典型的软件优先权排队接口电路如图6－10所示，图中把8个外设的中断请求触发器组合起来，作为一具端口，并赋以设备号。把各个外设的中断请求信号相“或”后，作为INTR信号，故其中任一外设有中断请求，都可向CPU送出INTR信号。当CPU响应中断后，把中断寄存器的状态作为一个外设读入CPU，逐位检测它们的状态，若哪一位为1，则该位对应的外设有中断请求，应转到相应的服务程序的入口。其流程如图6－11所示。
相应的查询程序如下：
XOR AL，AL ；CF清0
IN AL，20H ；输入中断请求触发器的状态
RCL AL，1 ；左移一位，检测最高位是否有请求
JC POW ；有，转相应服务程序
RCL AL，1 ；否，检测下一位
JC DISS
…
查询方法的优点是：
（1）询问的次序，即优先权的次序。显然，最先询问的，优先权的级别最高。
（2）省硬件。不需要有判断与确定优先权的硬件排队电路。
缺点是：由询问转至相应的服务程序入口的时间长，尤其是在中断源较多的情况下。
硬件优先权排队电路，目前均采用专用中断管理接口芯片如8259A等。
3．中断响应
经中断排队后，CPU收到一个当前申请中断的中断源中优先级别最高的中断请求信号，如果允许CPU响应中断（IF＝1），在执行完一条指令后，就中止执行现行程序，而响应中断申请。此时首先由硬件电路保护断点，即将当前正在执行的程序的段地址（CS）和偏移地址（IP）以及标志寄存器（FR）压入堆栈；然后关闭CPU内的允许中断触发器IF（可屏蔽中断时）；接下来就是寻找中断服务程序的入口地址。
寻找中断服务程序入口地址的方法分软件和硬件两种。软件方法即为上述的查询方式。在硬件方式中，目前均采用矢量中断方式。所谓矢量中民即当CPU响应中断后，由提出中断请求的中断源向CPU发去一个中断矢量，CPU根据这个中断矢量找到中断程序的入口地址，而转到相应的中断服务程序。以Intel为CPU的PC系列微型计算机系统就采用矢量中断方式。
4．中断处理
中断响应后，进入中断处理，即执行中断服务程序。在中断服务程序中，首先要保护现场，把中断服务程序中所要使用到的寄存器内容保护起来，如将经们的内容压入堆栈，然后才进行与此次中断有关的相应服务处理。处理完毕要恢复现用到的寄存器内容保护起来，如将经们的内容压入堆栈，然后才进行与此次中断有关的相应服务处理。处理完毕要恢复现场，即恢复中断前各寄存器的内容。如果在中断服务程序中允许嵌套（可屏蔽中断方式时），还应用STI指令将IF＝1（即开中断）。
5．中断返回
通常，中断服务程序的最后一条指令是一条中断返回指令。当CPU执行这条指令时，把原来程序被中断的断点地址从堆栈中弹回CS和IP中，原来的FR弹回FR。这样，实中断的程序就可以从断点处继续执行下去。CPU从中断服务程序又回到了被中断的主程序。
在实际应用系统中，中断可以嵌套，即可以有多重中断。所谓多重中断，就是在CPU执行某一中断服务程序时，又有优先级别更高的中断源申请断，此时，CPU应当暂停止这个中断服务，而去处理优先级别比它高的中断申请。处理完毕再返回中断占，继续处理较低优先级别的中断。这种在低级中断中还嵌套有高级中断的多重中断方式，对实时处理系统是很有用的。
转载自：
http://202.116.0.161/wjyl/site/text/chapter6/6.3.2.htm
“操作系统概论”习题解答之引言
1.计算机系统由哪两大部分组成？
答：计算机系统是能按照人的要求接受和存储信息，自动进行数据处理和计算，并输出结果信息的机器系统。计算机系统由两大部分组成：硬件（子）系统和软件（子）系统，其中硬件子系统是系统赖以工作的实体，它是有关的各种物理部件的有机的结合。软件子系统由各种程序以及程序所处理的数据组成，这些程序的主要作用是协调各个硬件部件，使整个计算机系统能够按照指定的要求进行工作。
硬件子系统包括中央处理器、主存存储器、输人输出控制系统和各种外围设备。
软件子系统包括系统软件、支援软件和应用软件三个部分。
2.什么是计算机的操作系统？
答：操作系统（Operating System缩写 OS）是一种系统软件。它对程序的执行进行控制，还使用户能方便地使用硬件提供的计算机功能，也使硬件的功能发挥得更好。它是一种用于管理计算机系统资源和控制程序执行的系统软件，它扩充系统的功能，为用户提供方便的使用接口和良好的运行环境。
3.操作系统管理哪些资源？
答：操作系统管理计算机系统的资源，其中硬件资源主要包括中央处理器、主存储器和各种外围设备；软件资源包括了程序和数据，通常这些程序和数据是以文件的方式存储和使用的。它说明资源的使用情况，实现多用户共享计算机系统的各种资源。
4.为什么要把“I/O指令”等定义为特权指令？
答：若用户程序中直接使用 I／O指令，则可能引起冲突或由于某些意外而造成错误。例如，用户程序中要启动磁带后取磁带上的信息，但可能操作员错拿了另一用户的磁带，把它以磁带机上，这时用户程序启动磁带机后从磁带上得到的信息实际上不是自己需要的，就可能造成程序执行后得到结果不正确。更糟糕的是当用户程序启动磁带机的目的是要把一些信息记到磁带上，将可能覆盖已在磁带上的信息，即把另一用户磁带上的信息破坏了。为了防止类似于这样一类的错误启动外围设备的工作不是用户程序直接做，而是由操作系统来做。
5.操作系统是如何防止用户使用特权指令的？
答：为了防止用户程序中使用特权指令，计算机硬件结构区分两种操作模式：目态和管态，其中目态下只能使用除特权指令以外的指令，管态下可以使用全部指令。当在目态下使用特权指令时，硬件就发出信号：“程序使用非法指令”，且不允许程序继续执行下去。所以可以把用户程序置在目态下运行，而操作系统中必须使用特权指令的那部分程序可在管态下运行，这样可保证计算机系统的安全可靠。
6.操作系统为什么要提供“系统调用”？
答：系统调用是操作系统为用户程序提供的一种服务界面，也可以说是操作系统保证程序设计语言能正常工作的一种支持。在源程序一级，用户用程序设计语言描述算题任务的逻辑要求（如读文件、写文件等）。而这些要求的实现只通过调用操作系统提供的不同功能的子程序，即系统调用。
7.批处理操作系统、实时操作系统和分时操作系统各有什么特点？
答：批处理操作系统是将一批作业的程序和数据交给系统后，系统顺序控制作业的执行，当一个作业执行结束后自动转入下一个作业的执行。多道批处理操作系统，允许若干个作业同时装入主存储器，处理器轮流地执行各个作业，各个作业同时使用各自所需的外围设备。
实时操作系统接收到外部信号后及时进行处理，并且要在严格的时限内处理完接收的事件。实时操作系统要求要有比分时操作系统更强的及时性。可靠性是实时系统最重要的设计目标之一。
分时操作系统的主要特点是：①交互性。用户能够直接与计算机系统交互。②及时性。由于支持人机交互，所以主机应该尽快地对用户的要求给予响应。③独立性。这主要是指多个用户虽然在同时使用主机系统，但是他们相互之间是不干扰的。④多路性。分时操作系统在宏观上看，整个系统同时在为多个用户服务。
8.从资源管理的观点来看，操作系统有哪些基本功能？
答：从资源管理的观点看，操作系统的功能可分成五大部分，即：
①处理器管理。操作系统按照一定的调度算法分配处理机。
②存储管理。负责分配、回收和保护存储单元。
③文件管理。涉及到文件存储空间的分配与回收、文件目录管理、文件读写与保护。
④设备管理。对设备进行分配、回收与控制。
⑤作业管理。负责作业的调度和作业控制。
转载自：
http://www.zikao365.com/html/4_21_89_175/2007_4_27_sh8841275617247002654_0.htm
答：计算机系统是能按照人的要求接受和存储信息，自动进行数据处理和计算，并输出结果信息的机器系统。计算机系统由两大部分组成：硬件（子）系统和软件（子）系统，其中硬件子系统是系统赖以工作的实体，它是有关的各种物理部件的有机的结合。软件子系统由各种程序以及程序所处理的数据组成，这些程序的主要作用是协调各个硬件部件，使整个计算机系统能够按照指定的要求进行工作。
硬件子系统包括中央处理器、主存存储器、输人输出控制系统和各种外围设备。
软件子系统包括系统软件、支援软件和应用软件三个部分。
2.什么是计算机的操作系统？
答：操作系统（Operating System缩写 OS）是一种系统软件。它对程序的执行进行控制，还使用户能方便地使用硬件提供的计算机功能，也使硬件的功能发挥得更好。它是一种用于管理计算机系统资源和控制程序执行的系统软件，它扩充系统的功能，为用户提供方便的使用接口和良好的运行环境。
3.操作系统管理哪些资源？
答：操作系统管理计算机系统的资源，其中硬件资源主要包括中央处理器、主存储器和各种外围设备；软件资源包括了程序和数据，通常这些程序和数据是以文件的方式存储和使用的。它说明资源的使用情况，实现多用户共享计算机系统的各种资源。
4.为什么要把“I/O指令”等定义为特权指令？
答：若用户程序中直接使用 I／O指令，则可能引起冲突或由于某些意外而造成错误。例如，用户程序中要启动磁带后取磁带上的信息，但可能操作员错拿了另一用户的磁带，把它以磁带机上，这时用户程序启动磁带机后从磁带上得到的信息实际上不是自己需要的，就可能造成程序执行后得到结果不正确。更糟糕的是当用户程序启动磁带机的目的是要把一些信息记到磁带上，将可能覆盖已在磁带上的信息，即把另一用户磁带上的信息破坏了。为了防止类似于这样一类的错误启动外围设备的工作不是用户程序直接做，而是由操作系统来做。
5.操作系统是如何防止用户使用特权指令的？
答：为了防止用户程序中使用特权指令，计算机硬件结构区分两种操作模式：目态和管态，其中目态下只能使用除特权指令以外的指令，管态下可以使用全部指令。当在目态下使用特权指令时，硬件就发出信号：“程序使用非法指令”，且不允许程序继续执行下去。所以可以把用户程序置在目态下运行，而操作系统中必须使用特权指令的那部分程序可在管态下运行，这样可保证计算机系统的安全可靠。
6.操作系统为什么要提供“系统调用”？
答：系统调用是操作系统为用户程序提供的一种服务界面，也可以说是操作系统保证程序设计语言能正常工作的一种支持。在源程序一级，用户用程序设计语言描述算题任务的逻辑要求（如读文件、写文件等）。而这些要求的实现只通过调用操作系统提供的不同功能的子程序，即系统调用。
7.批处理操作系统、实时操作系统和分时操作系统各有什么特点？
答：批处理操作系统是将一批作业的程序和数据交给系统后，系统顺序控制作业的执行，当一个作业执行结束后自动转入下一个作业的执行。多道批处理操作系统，允许若干个作业同时装入主存储器，处理器轮流地执行各个作业，各个作业同时使用各自所需的外围设备。
实时操作系统接收到外部信号后及时进行处理，并且要在严格的时限内处理完接收的事件。实时操作系统要求要有比分时操作系统更强的及时性。可靠性是实时系统最重要的设计目标之一。
分时操作系统的主要特点是：①交互性。用户能够直接与计算机系统交互。②及时性。由于支持人机交互，所以主机应该尽快地对用户的要求给予响应。③独立性。这主要是指多个用户虽然在同时使用主机系统，但是他们相互之间是不干扰的。④多路性。分时操作系统在宏观上看，整个系统同时在为多个用户服务。
8.从资源管理的观点来看，操作系统有哪些基本功能？
答：从资源管理的观点看，操作系统的功能可分成五大部分，即：
①处理器管理。操作系统按照一定的调度算法分配处理机。
②存储管理。负责分配、回收和保护存储单元。
③文件管理。涉及到文件存储空间的分配与回收、文件目录管理、文件读写与保护。
④设备管理。对设备进行分配、回收与控制。
⑤作业管理。负责作业的调度和作业控制。
转载自：
http://www.zikao365.com/html/4_21_89_175/2007_4_27_sh8841275617247002654_0.htm
“操作系统概论”习题解答之存储管理
1.解释下列术语
逻辑地址；绝对地址；地址转换
答：逻辑地址：对于用户来说，他无须知道自己的作业究竟是在主存的什么位置，他们可以认为自己的程序和数据就是放在从0地址开始一组连续的地址空间中，这个地址空间是程序用来访问信息所用的一系列连续地址单元的集合，该地址空间就是逻辑地址空间。逻辑地址空间中，地址单元的编号称为逻辑地址。
绝对地址：主存也被按照连续的存储单元进行编号，绝对地址空间就是主存中一系列连续存储信息的物理单元的集合，也称绝对地址空间为存储地址空间或物理地址空间。绝对地址空间中物理单元的编号称为绝对地址。 地址转换：由于一个作业装入到与其逻辑地址空间不一致的绝对地址空间，使得逻辑地址与绝对地址不同，而引起的对有关地址部分的调整，即逻辑地址转换成绝对地址的过程称为重定位，也称为地址转换。
2.存储保护的目的是什么？怎样实现存储保护？
答：存储保护的目的就是为了保护主存中各区域内的信息不被破坏，它包括存储的权限，存储不可跨越区域等等。为实现存储保护，必须由硬件和软件配合实现。比如在页式管理中，要由操作系统提供页表，硬件机构确定页的使用必须是安全的，如不能访问不属于自己的页等。
3.什么叫重定位？重定位的方式有哪两种？比较它们的不同。
答：由于一个作业装入到与其逻辑地址空间不一致的绝对地址空间，使得逻辑地址与绝对地址不同，而引起的对有关地址部分的调整，即逻辑地址转换成绝对地址的过程称为重定位，也称为地址转换。
重定位有静态和动态两种情况。
所谓静态重定位是在装入一个作业的时候，把作业中的指令地址和数据地址全部一次性地转换成绝对地址。
所谓动态重定位是由软件和硬件相配合来实现的。地址重定位不再是装入的时候一次完成了，而是设置一个基址寄存器，装入作业的时候，将作业在主存区域的首地址放入到基址寄存器中。作业执行的时候，由硬件的地址转换机构动态地对地址进行转换，执行指令的时候，只要将逻辑地址加上基址寄存器的内容，就得到了绝对地址。
静态重定位和动态重定位的不同在于：①静态重定位是在作业装入的时候一次完成，动态重定位是在作业执行时再实现的。②静态重定位是软件支持的，动态重定位是硬件和软件合作实现的。③静态重定位不能实现主存的移动，而动态重定位可以。④动态重定位还可能提供虚拟存储空间。
4.比较固定分区、可变分区和页式存储管理的优缺点。
答：固定分区优点：
①能支持多道程序设计。
②无需专门的硬件地址转换机构。
缺点：
①主存利用率不算太高，分配中出现内部零头问题。
②分区大小固定不灵活，不能为程序动态申请内存。
③不具备虚拟存储能力。
可变分区优点：
①支持多道程序设计。
②没有内部零头问题，主存利用率比固定分区高。
③采用移动技术后可以满足正在执行的作业的主存扩充的要求。
缺点：
①动态重定位和保护措施需要硬件机构支持，成本高。
②由于有外部零头，所以主存利用率依然不算很高。
③移动技术开销很大。
④每次必须将作业完整调入并连续存放，主存利用率不高。
⑤不具备虚拟存储能力。
页式存储管理优点：
①支持多道程序设计
②解决了外部零头问题，内部零头大大减少（一个作业平均只有50％页面大小的内部零头）主存利用率比较高。
③用户作业无需在主存中连续存放，提高主存的利用率。
④如果是分页虚拟存储管理，可以提供大容量的多个虚拟存储器，主存利用率更高了。
缺点：
①动态重定位和保护措施需要硬件机构支持，成本高；
②采用页表，占用了一部分主存空间和处理机时间。
③分页虚拟存储管理中，增加了缺页中断的处理，增加了系统开销。
5.采用可变分区方式管理主存时，为什么要引人移动技术？
答：采用移动技术可以使分散的主存空闲区集中以满足分配要求，采用移动技术后可允许作业执行时动态扩充主存区域。
6.页式存储管理中为什么要设置页表？
答：因为页式管理时把作业分散在主存中的不连续块中存放，必须通过页表来建立逻辑地址中的页号到绝对地址中的块号的映射，作为硬件进行地址转换的依据。
7.页式存储管理中页面大小是根据什么决定的？页表的长度又是根据什么决定的？
答：页面的大小是由地址结构决定的。页表的长度是由作业的信息量决定的，作业有多少页，页表中就有多少个记录项。
8.叙述页式存储管理中地址转换过程。
答：首先，操作系统为每个作业创建一张页表，它建立了逻辑地址中的页号到绝对地址中的块号的映射。然后，借助于硬件地址转换机构，在作业执行过程中，每执行一条指令时，按逻辑地址中的页号查页表得到对应的块号，再根据公式“绝对地址=块号×块长+页内地址”换算出欲访问的主存单元的绝对地址。
9.什么叫虚拟存储器？
答：根据程序执行的互斥性和局部性两个特点，我们允许作业装入的时候只装入一部分，另一部分放在磁盘上，当需要的时候再装入到主存，这样以来，在一个小的主存空间就可以运行一个比它大的作业。同时，用户编程的时候也摆脱了一定要编写小于主存容量的作业的限制。也就是说，用户的逻辑地址空间可以比主存的绝对地址空间要大。对用户来说，好象计算机系统具有一个容量很大的主存储器，称为“虚拟存储器”。
10.叙述页式存储管理实现虚拟存储器的基本思想。
答：基本思想是：只需将作业的全部信息作为副本存放在磁盘上，作业被调度投入到运行时，至少把第一页信息装入主存储器，在作业执行过程中访问到不在主存储器的页的时候，再把它们装入到主存。
11.采用可变分区方式管理主存时，能实现虚拟存储器吗？为什么？
答：不可以，因为可变分区每次必须将作业完整调入并连续存放，这不适合虚拟存储的要求。同时，可变分区的硬件地址转换机构把绝对地址超出限定范围时作地址错处理，而不是产生“缺分区中断”。
12.什么叫“抖动”？怎样衡量页面调度算法的好坏？
答：如果选用了一个不合适的调度算法，就会出现这样的现象：刚被淘汰了的页面又立即要用，又要把它调入进来，而调入不久又被调出，调出不久再次被调入，如此反复，使得调度非常频繁，以至于大部分时间都花费在来回调度上。这种现象叫“抖动”。一个好的调度算法应减少和避免抖动现象。
13.假定某计算机系统的主存容量为32K，对主存采用动态定位可变分区分配算法。现在已经有3个作业在主存储器中（如图），当作业J2执行时，要求扩充3K作业，为了满足作业J2这一要求，应移动几道作业的信息？写出它们的次序、方向和距离。
答：因为采用可变分区的管理方式，要求作业的逻辑地址空间是连续的，并且主存空间也是连续的。因此，作业J2要求扩充的主存区域应该在原占有区域之后，于是必须通过移动来集中空闲区以供J2扩充之需。移动的方法有两种：
①先把J1向上移动1K再把J2向上移动2K.
②J3向下移动2K.
显然，第二种方法只要进行一次移动，明显比第一种方法好。
14.某采用页式存储管理的系统，接收了一共7页的作业，作业执行时依次访问的页为：l、2、3、4、2、1、5、6、2、1、2、3、7.若把开始4页先装入主存，若分别用先进先出（FIFO）调度算法和最近最少用（LRU）调度算法，作业执行时回产生多少次缺页中断？写出依次产生缺页中断后应淘汰的页。
答：采用先进先出调度算法会产生 6次缺页中断，依次淘汰的页是 1、2、3、4、5、6.
采用最近最少用调度算法会产生4次缺页中断，依次淘汰的页是3、4、5、6.
15.某采用页式存储管理的系统，把主页分成大小为128的相等长度的块。有一个用户要把一个 128 × 128的数组置成初值“0”，在分页时把数组中的元素每一行放在一页中，假定分给用户可用来存放数组信息的工作区只有一块（既只能放数组中的一行元素）。用户编制了如下两个不同的程序来实现数组的初始化：
l）var A：array[ 1.。128]of array［l.。128」of integer；
for j ：=1 to 128
do for i：=1 to 128
do A[j：]=0；
2）var A：array［1.。128」of array［1.。128」Of integer；
for i：=1 to 128
do for j：=1 to 128
do A[j]：=0；
当分别运行这两个程序时，在实现数组初始化的过程中各会产生多少次缺页中断？
答：假定数组的第一行元素已经存放在了一个主存块中，由于分页进把数组中的元数每一行放在一页中，所以每次i+1的时候都会产生缺页中断。这样一来，按1）编制的程序，每执行一次A[j]：=0 就会产生一次缺页中 断，于是总共产生（128×128-1）次缺页中断。而2）编制的程序执行时产生（128-1）次缺页中断。
转载自：
http://www.zikao365.com/html/4_21_89_175/2007_4_27_sh9613385971724700210730_0.htm
逻辑地址；绝对地址；地址转换
答：逻辑地址：对于用户来说，他无须知道自己的作业究竟是在主存的什么位置，他们可以认为自己的程序和数据就是放在从0地址开始一组连续的地址空间中，这个地址空间是程序用来访问信息所用的一系列连续地址单元的集合，该地址空间就是逻辑地址空间。逻辑地址空间中，地址单元的编号称为逻辑地址。
绝对地址：主存也被按照连续的存储单元进行编号，绝对地址空间就是主存中一系列连续存储信息的物理单元的集合，也称绝对地址空间为存储地址空间或物理地址空间。绝对地址空间中物理单元的编号称为绝对地址。 地址转换：由于一个作业装入到与其逻辑地址空间不一致的绝对地址空间，使得逻辑地址与绝对地址不同，而引起的对有关地址部分的调整，即逻辑地址转换成绝对地址的过程称为重定位，也称为地址转换。
2.存储保护的目的是什么？怎样实现存储保护？
答：存储保护的目的就是为了保护主存中各区域内的信息不被破坏，它包括存储的权限，存储不可跨越区域等等。为实现存储保护，必须由硬件和软件配合实现。比如在页式管理中，要由操作系统提供页表，硬件机构确定页的使用必须是安全的，如不能访问不属于自己的页等。
3.什么叫重定位？重定位的方式有哪两种？比较它们的不同。
答：由于一个作业装入到与其逻辑地址空间不一致的绝对地址空间，使得逻辑地址与绝对地址不同，而引起的对有关地址部分的调整，即逻辑地址转换成绝对地址的过程称为重定位，也称为地址转换。
重定位有静态和动态两种情况。
所谓静态重定位是在装入一个作业的时候，把作业中的指令地址和数据地址全部一次性地转换成绝对地址。
所谓动态重定位是由软件和硬件相配合来实现的。地址重定位不再是装入的时候一次完成了，而是设置一个基址寄存器，装入作业的时候，将作业在主存区域的首地址放入到基址寄存器中。作业执行的时候，由硬件的地址转换机构动态地对地址进行转换，执行指令的时候，只要将逻辑地址加上基址寄存器的内容，就得到了绝对地址。
静态重定位和动态重定位的不同在于：①静态重定位是在作业装入的时候一次完成，动态重定位是在作业执行时再实现的。②静态重定位是软件支持的，动态重定位是硬件和软件合作实现的。③静态重定位不能实现主存的移动，而动态重定位可以。④动态重定位还可能提供虚拟存储空间。
4.比较固定分区、可变分区和页式存储管理的优缺点。
答：固定分区优点：
①能支持多道程序设计。
②无需专门的硬件地址转换机构。
缺点：
①主存利用率不算太高，分配中出现内部零头问题。
②分区大小固定不灵活，不能为程序动态申请内存。
③不具备虚拟存储能力。
可变分区优点：
①支持多道程序设计。
②没有内部零头问题，主存利用率比固定分区高。
③采用移动技术后可以满足正在执行的作业的主存扩充的要求。
缺点：
①动态重定位和保护措施需要硬件机构支持，成本高。
②由于有外部零头，所以主存利用率依然不算很高。
③移动技术开销很大。
④每次必须将作业完整调入并连续存放，主存利用率不高。
⑤不具备虚拟存储能力。
页式存储管理优点：
①支持多道程序设计
②解决了外部零头问题，内部零头大大减少（一个作业平均只有50％页面大小的内部零头）主存利用率比较高。
③用户作业无需在主存中连续存放，提高主存的利用率。
④如果是分页虚拟存储管理，可以提供大容量的多个虚拟存储器，主存利用率更高了。
缺点：
①动态重定位和保护措施需要硬件机构支持，成本高；
②采用页表，占用了一部分主存空间和处理机时间。
③分页虚拟存储管理中，增加了缺页中断的处理，增加了系统开销。
5.采用可变分区方式管理主存时，为什么要引人移动技术？
答：采用移动技术可以使分散的主存空闲区集中以满足分配要求，采用移动技术后可允许作业执行时动态扩充主存区域。
6.页式存储管理中为什么要设置页表？
答：因为页式管理时把作业分散在主存中的不连续块中存放，必须通过页表来建立逻辑地址中的页号到绝对地址中的块号的映射，作为硬件进行地址转换的依据。
7.页式存储管理中页面大小是根据什么决定的？页表的长度又是根据什么决定的？
答：页面的大小是由地址结构决定的。页表的长度是由作业的信息量决定的，作业有多少页，页表中就有多少个记录项。
8.叙述页式存储管理中地址转换过程。
答：首先，操作系统为每个作业创建一张页表，它建立了逻辑地址中的页号到绝对地址中的块号的映射。然后，借助于硬件地址转换机构，在作业执行过程中，每执行一条指令时，按逻辑地址中的页号查页表得到对应的块号，再根据公式“绝对地址=块号×块长+页内地址”换算出欲访问的主存单元的绝对地址。
9.什么叫虚拟存储器？
答：根据程序执行的互斥性和局部性两个特点，我们允许作业装入的时候只装入一部分，另一部分放在磁盘上，当需要的时候再装入到主存，这样以来，在一个小的主存空间就可以运行一个比它大的作业。同时，用户编程的时候也摆脱了一定要编写小于主存容量的作业的限制。也就是说，用户的逻辑地址空间可以比主存的绝对地址空间要大。对用户来说，好象计算机系统具有一个容量很大的主存储器，称为“虚拟存储器”。
10.叙述页式存储管理实现虚拟存储器的基本思想。
答：基本思想是：只需将作业的全部信息作为副本存放在磁盘上，作业被调度投入到运行时，至少把第一页信息装入主存储器，在作业执行过程中访问到不在主存储器的页的时候，再把它们装入到主存。
11.采用可变分区方式管理主存时，能实现虚拟存储器吗？为什么？
答：不可以，因为可变分区每次必须将作业完整调入并连续存放，这不适合虚拟存储的要求。同时，可变分区的硬件地址转换机构把绝对地址超出限定范围时作地址错处理，而不是产生“缺分区中断”。
12.什么叫“抖动”？怎样衡量页面调度算法的好坏？
答：如果选用了一个不合适的调度算法，就会出现这样的现象：刚被淘汰了的页面又立即要用，又要把它调入进来，而调入不久又被调出，调出不久再次被调入，如此反复，使得调度非常频繁，以至于大部分时间都花费在来回调度上。这种现象叫“抖动”。一个好的调度算法应减少和避免抖动现象。
13.假定某计算机系统的主存容量为32K，对主存采用动态定位可变分区分配算法。现在已经有3个作业在主存储器中（如图），当作业J2执行时，要求扩充3K作业，为了满足作业J2这一要求，应移动几道作业的信息？写出它们的次序、方向和距离。
答：因为采用可变分区的管理方式，要求作业的逻辑地址空间是连续的，并且主存空间也是连续的。因此，作业J2要求扩充的主存区域应该在原占有区域之后，于是必须通过移动来集中空闲区以供J2扩充之需。移动的方法有两种：
①先把J1向上移动1K再把J2向上移动2K.
②J3向下移动2K.
显然，第二种方法只要进行一次移动，明显比第一种方法好。
14.某采用页式存储管理的系统，接收了一共7页的作业，作业执行时依次访问的页为：l、2、3、4、2、1、5、6、2、1、2、3、7.若把开始4页先装入主存，若分别用先进先出（FIFO）调度算法和最近最少用（LRU）调度算法，作业执行时回产生多少次缺页中断？写出依次产生缺页中断后应淘汰的页。
答：采用先进先出调度算法会产生 6次缺页中断，依次淘汰的页是 1、2、3、4、5、6.
采用最近最少用调度算法会产生4次缺页中断，依次淘汰的页是3、4、5、6.
15.某采用页式存储管理的系统，把主页分成大小为128的相等长度的块。有一个用户要把一个 128 × 128的数组置成初值“0”，在分页时把数组中的元素每一行放在一页中，假定分给用户可用来存放数组信息的工作区只有一块（既只能放数组中的一行元素）。用户编制了如下两个不同的程序来实现数组的初始化：
l）var A：array[ 1.。128]of array［l.。128」of integer；
for j ：=1 to 128
do for i：=1 to 128
do A[j：]=0；
2）var A：array［1.。128」of array［1.。128」Of integer；
for i：=1 to 128
do for j：=1 to 128
do A[j]：=0；
当分别运行这两个程序时，在实现数组初始化的过程中各会产生多少次缺页中断？
答：假定数组的第一行元素已经存放在了一个主存块中，由于分页进把数组中的元数每一行放在一页中，所以每次i+1的时候都会产生缺页中断。这样一来，按1）编制的程序，每执行一次A[j]：=0 就会产生一次缺页中 断，于是总共产生（128×128-1）次缺页中断。而2）编制的程序执行时产生（128-1）次缺页中断。
转载自：
http://www.zikao365.com/html/4_21_89_175/2007_4_27_sh9613385971724700210730_0.htm
订阅：
博文 (Atom)