18.进程调度的功能
1）记录系统中所有进程的执行情况
作为进程调度的准备，进程管理模块必须将系统中各进程的执行情况和状态特征记录在各进程的PCB表中。
并且，根据各进程的状态特征和资源需求等、进程管理模块还将各进程的PCB表排成相应的队列并进行动态队列转接。
进程调度模块通过PCB变化来掌握系统中存在的所有进程的执行情况和状态特征，并在适当的时机从就绪队列中选择出一个进程占据处理机。
2）选择占有处理机的进程
进程调度的主要功能是按照一定的策略选择—个处于就绪状态的进程，使其获得处理机执行。
根据不同的系统设计目的，有各种各样的选择策略，例如系统开销较少的静态优先数调度法，适合于分时系统的轮转法（RoundRoLin）和多级互馈轮转法（RoundRobinwithMultip1efeedback）等。
这些选择策略决定了调度算法的性能。
3）进行进程上下文切换
—个进程的上下文（context）包括进程的状态、有关变量和数据结构的值、机器寄存器的值和PCB以及有关程序、数据等。
一个进程的执行是在进程的上下文中执行。
当正在执行的进程由于某种原因要让出处理机时，系统要做进程上下文切换，以使另一个进程得以执行。
当进行上下文切换时点统要首先检查是否允许做上下文切换（在有些情况下，上下文切换是不允许的，例如系统正在执行某个不允许中断的原语时）。
然后，系统要保留有关被切换进程的足够信息，以便以后切换回该进程时，顺利恢复该进程的执行。
在系统保留了CPU现场之后，调度程序选择一个新的处于就绪状态的进程、并装配该进程的上下文，使CPU的控制权掌握在被选中进程手中。
19.作业调度算法（FCFS和短作业优先）
先来先服务（FCFS）调度算法
FCFS是最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。
当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行时间的长短从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程。
然后把它们放入就绪队列。
当在进程调度中采用FCFS算法时，每次调度是从就绪的进程队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。
该进程一直运行到完成或发生某事件而阻塞后，进程调度程序才将处理机分配给其它进程。
优点：
1）简单可靠
2）容易理解，实现方便
3）非抢占式的
缺点：
1）有利于长的作业和进程，不利于短的
2）有利于CPU繁忙型的作业或进程，不利于I/O繁忙型的
短作业优先（SJF）的调度算法
SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。
作业的长短是以作业所要求的运行时间来衡量的。
SJF算法可以分别用于作业调度和进程调度。
班在短作业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存运行。
缺点：
1）必须预知作业的运行时间
2）对长作业非常不利，长作业的周转时间会明显地增长
3）在采用SJF算法时，人-机无法实现交互
4）该调度算法完全未考虑作业的紧迫程度，故不能保证紧迫性作业能得到及时处理
20.存储管理的对象
存储管理的对象是主存储器（简称内存或主存） 。
分区管理的分配算法
基于顺序搜索的的动态分配算法：
1首次适应算法2循环首次适应算法3最佳适应算法4最坏适应算法
基于索引搜索的动态分配算法
1快速适应算法2伙伴系统3哈希算法
21.分页存储管理的基本思想和页表的作用
将用户程序的地址空间分为若干个固定大小的区域，称为“页”或“页面”。
典型的页面大小为1KB。
相应的，也将内存空间分为若干个物理块或页框，页和块的大小相同。
这样可将用户的程序的任一页放入任一物理块中，实现了离散分配。
页表的作用：
能在内存中找到每一个页面所对应的物理块。
22.段式存储的基本思想
把用户程序的地址空间分为若干个大小不同的段，每段可定义一组相对完整的信息。
在存储器分配时，以段为单位，这些段在内存中可以不相邻接，所以也同样实现了离散分配。
23.分页与分段的区别
分页和分段系统有许多相似之处，但在概念上两者完全不同，主要表现在：
1、页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率；或者说，分页仅仅是由于系统管理的需要，而不是用户的需要。
段是信息的逻辑单位，它含有一组其意义相对完整的信息。
分段的目的是为了能更好的满足用户的需要。
2、页的大小固定且由系统确定，把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而一个系统只能有一种大小的页面。
段的长度却不固定，决定于用户所编写的程序，通常由编辑程序在对源程序进行编辑时，根据信息的性质来划分。
3、分页的作业地址空间是维一的，即单一的线性空间，程序员只须利用一个记忆符，即可表示一地址。
分段的作业地址空间是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。
24.页面置换的算法，FIFO,LRU
FIFO：
LRU：
25.输入输出四种控制方式
1）程序直接控制方式
2）中断驱动方式
3）DMA（直接存储器存取）方式
4）通道控制方式
26.输入输出I/O重定向的概念
I/O重定向是一个过程，这个过程捕捉一个文件、或命令、或程序、或脚本、甚至代码块（codeblock）的输出，然后把捕捉到的输出，作为输入发送给另外一个文件、或命令、或程序、或脚本。
I/O重定向最常用的方法是管道（管道符"|"）。
27.设备独立性
设备独立性，即应用程序独立于具体使用的物理设备。
为了实现设备独立性而引入了逻辑设备和物理设备这两个概念。
在应用程序中，使用逻辑设备名称来请求使用某类设备;而系统在实际执行时，还必须使用物理设备名称。
因此，系统须具有将逻辑设备名称转换为某物理设备名称的功能，这非常类似于存储器管理中所介绍的逻辑地址和物理地址的概念。
28.中断的定义
中断是指CPU对I/O发来的中断信号的一中响应。
CPU暂停正在执行的程序，保留CPU环境后，自动地转去执行该I/O设备的中断处理程序。
执行完后，在回到断点，继续执行原来的程序。
I/O设备可以是字符设备，也可以是块设备，通信设备等。
由于中断是由外部设备引起的，故又称为外中断。
29.中断处理程序的处理过程
1）测定是否有未响应的中断信号
2）保护被中断进程的CPU环境
3）转入相应的设备处理程序
4）中断处理
5）恢复CPU的现场并退出中断
30.假脱机（Spooling）系统的作用
1）提高了I/O速度.从对低速I/O设备进行的I/O操作变为对输入井或输出井的操作,如同脱机操作一样,提高了I/O速度,缓和了CPU与低速I/O设备速度不匹配的矛盾.
2）设备并没有分配给任何进程.在输入井或输出井中,分配给进程的是一存储区和建立一张I/O请求表.
3）实现了虚拟设备功能.多个进程同时使用一独享设备,而对每一进程而言,都认为自己独占这一设备,不过,该设备是逻辑上的设备.
31.磁盘调度的算法
早期的磁盘调度算法
1）先来先服务（FCFS）
2）最短寻道时间优先（SSTF）
基于扫描的磁盘调度算法
1）扫描（SCAN）算法
2）循环扫描（CSCAN）算法
3）NStepSCAN和FSCAN调度算法
32.文件逻辑结构，物理结构的定义
1）文件的逻辑结构。
这是从用户观点出发所观察到的文件组织形式，即文件是由一系列的逻辑记录组成的，是用户可以直接处理的数据及其结构，它独立于文件的物理特性，又称为文件组织。
2）文件的物理结构，又称为文件的存储结构。
这是指系统将文件存储在外存上所形成的一种存储组织形式，是用户不能看见的。
文件的物理结构不仅与存储介质的存储性能有关，而且与所采用的外存分配方式有关。
无论是文件的逻辑结构，还是其物理结构，都会影响对文件的检索速度。
33.目录文件存放的信息
该目录中所有子目录文件和数据文件的目录
34.文件多级目录结构的特点
多级（树形）目录结构的优点是便于文件分类，可为每类文件建立一个子目录；查找速度快，因为每个目录下的文件数目较少；可以实现文件共享；缺点是比较复杂。
35.保护域的定义
为了对系统中的资源进行保护而引入了保护域的概念，保护域简称“域”。
“域”是进程对一组对象访问权的集合，进程只能在制定域内执行操作。
这样，“域”也就规定了进程所能访问的对象和能执行的操作。
36.访问权的定义
为了对系统中的对象加以保护，应由系统来控制进程对对象的访问。
对象可以是硬件对象，如磁盘驱动器，打印机；也可以是软件对象，如文件，程序。
对对象所施加的操作也有所不同，如对文件可以是读，也可以是写或执行操作。
我们把一个进程能对某对象执行操作的权力，称为访问权。
每个访问权可以用一个有序对（对象名，权集）来表示。
例如，某进程有对文件F1执行读和写操作的权力，则可将该进程的访问权表示成（F1，{R/W}）。
37.位示图进行盘块，回收的过程
位示图是利用二进制的一位来表示磁盘中的一个盘块的使用情况。
当其值为"0"时，表示对应的盘块空闲;为"1"时，表示已经分配。
有的系统把"0"作为盘块已分配的标记，把"1"作为空闲标志。
（它们的本质上是相同的，都是用一位的两种状态标志空闲和已分配两种情况。
）磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，称为位示图。
通常可用m*n个位数来构成位示图，并使m*n等于磁盘的总块数。
位示图也可描述为一个二维数组map[m,n]。
盘块的分配
根据位示图进行盘块分配时，可分三步进行：
1）顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位（“0”表示空闲时）。
2）将所找到的一个或一组二进制位转换为与之对应的盘块号。
假定找到的其值为“0”的二进制位位于位示图的第i行，第j列，则其相应的盘块号应按下式计算：
b=n（i-1）+j，式中，n代表每行的位数。
3）修改位示图，令map[I,j]=1。
盘块的回收
1）将回收盘块的盘块号转换为位示图中的行号和列号。
转换公式为：
I=（b-1）DIVn+1
J=（b-1）MODn+1
2）修改位示图。
令map[I,j]=0.。
38.CPU指令的分类
常见的特权指令有以下几种:
（1）有关对I/O设备使用的指令如启动I/O设备指令、测试I/O设备工作状态和控制I/O设备动作的指令等。
（2）有关访问程序状态的指令如对程序状态字（PSW）的指令等。
（3）存取特殊寄存器指令如存取中断寄存器、时钟寄存器等指令。
（4）其他指令
39.CPU运行状态的分类
40.网络操作系统的互操作功能
为了了实现多个网络之间的通信和资源共享，不仅需要将他们从物理上连接在一起，而且还应使不同网络的计算机系统之间能进行通信（信息互通）和实现资源共享（信息互用）。
为此网络OS中必须提供应用互操作功能，以实现“信息互通性”及“信息互用性”。
（1）信息互通性。
为了避免在不同网络中，因采用了不同的协议而不能识别和通信，在互连网络的每一个网络中都应配置同一类型的传输协议，以实现各个网络之间的通信。
（2）信息的互用性。
所谓信息的互用性，是指在不同的网络中的站点之间能实现信息的互用，亦即一个网络中的用户能够访问另一个网络文件系统（或数据库系统）中的文件（数据）。
不能实现信息的互用性的原因是在不同网络中所配置的网络文件系统（或数据库系统），通常使用了各不相同的结构、各不相同的文件命名方式和存取文件的命令，于是便发生了有一个源网络中的用户发往一个目标网络的文件访问命令不能被目标网络的节点所识别的情况。
对此，一个当前相对比较流行的解决方案是由SUN公司推出的网络文件系统协议NFS
41.网络协议的三要素
1）语义
2）语法
3）时序
42.加密算法的分类
对称加密算法
非对称加密算法
43.身份认证的依据
当前身份验证主要依据下述三个方面的信息来确认：
1）所知，即基于用户所知道的信息，如系统的登录名，口令等。
2）所有，指用户所具有的东西，如身份证，信用卡等。
3）用户特征，指用户所具有的特征，特别是生理特征，如指纹，声纹，DN等。
1.某杂技团进行走钢丝表演。
在钢丝的A、B两端各有n名演员（n>1）在等待表演。
只要钢丝上无人时便允许一名演员从钢丝的一端走到另一端。
现要求两端的演员交替地走钢丝，且从A端的一名演员先开始。
请问，把一名演员看作一个进程时，怎样用WAIT,SIGNAL操作来进行控制？
请写出能进行正确管理的程序。
2.有—阅览室，读者进入时必须先在一张登记表中进行登记，该表为每一座位列一表目，包括座号和读者姓名，读者离开时要消掉登记信息，阅览室中共有100个座位，试问：
试用信号量和wait，signal原语写出这些进程间的同步算法。
3.请用信号量解决以下的“过独木桥”问题：
同一方向的行人可连续过桥，当某一方向有人过桥时，另一方向的行人必须等待；当某一方向无人过桥时，另一方向的行人可以过桥。
4.假定系统有三个并发进程read,move和print共享缓冲器B1和B2。
进程read负责从输入设备上读信息，每读出一个记录后把它存放到缓冲器B1中。
进程move从缓冲器B1中取出一记录，加工后存入缓冲器B2。
进程print将B2中的记录取出打印输出。
缓冲器B1和B2每次只能存放一个记录。
要求三个进程协调完成任务，使打印出来的与读入的记录的个数，次序完全一样。
请用WAIT（）和SIGNAL（）原语操作，写出它们的并发程序。
1、某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。
假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：
页号物理块号
05
110
24
37
则逻辑地址0A5C（H）所对应的物理地址是什么？
解：
程序空间的大小为32KB，因此逻辑地址的有效位数是15位。
内存储空间的大小是16KB，因此物理地址至少需要14位。
2、某段表内容如下：
段号段首地址段长度
0120K40K
1760K30K
2480K20K
3370K20K
一逻辑地址为（2，154）的实际物理地址为多少？
答：
逻辑地址（2,154）表示段号为2，即段手地址为480K，154为单元号，则实际物理地址为480K+154。
3、考虑下述页面走向：
1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6
当内存块数量分别为3时，试问FIFO、LRU、OPT这三种置换算法的缺页次数各是多少？
答：
缺页定义为所有内存块最初都是空的，所以第一次用到的页面都产生一次缺页。
当内存块数量为3时：
发生缺页中断的次数为16。
在FIFO算法中，先进入内存的页面被先换出。
当页6要调入时，内存的状态为4、1、5，考查页6之前调入的页面，分别为5、1、2、4，可见4为最先进入内存的，本次应换出，然后把页6调入内存。
发生缺页中断的次数为15。
在LRU算法中，最近最少使用的页面被先换出。
当页6要调入时，内存的状态为5、2、1，考查页6之前调入的页面，分别为5、1、2，可见2为最近一段时间内使用最少的，本次应换出，然后把页6调入内存。
发生缺页中断的次数为11。
在OPT算法中，在最远的将来才被访问的页面被先换出。
当页6要调入时，内存的状态为1、2、5，考查页6后面要调入的页面，分别为2、1、2、…，可见5为最近一段时间内使用最少的，本次应换出，然后把页6调入内存。
OPT算法因为要知道后面请求的页框，因此我觉得这个算法有个小小的bug,如果在某个请求中，若在该请求的页框之后的页框序列中至少存在一个和当前内存块中不匹配的页框，则按照内存块的顺序（从上往下）替换没有出现的页框。
比如上面那个OPT例子。
对于最后一个页框请求，因为6未命中，且6之后没有请求的序列，因此应该替换3，所以替换后的序列为6，2，1。
4.．假设一个磁盘有200个磁道，编号从O～199。
当前磁头正在143道上服务，并且刚刚完成了125道的请求。
如果寻道请求队列的顺序是：
86，147，9l，177，94，150，102，175，130问：
为完成上述请求，使用最短寻道时间优先磁盘调度算法SSTF时，磁头移动的总量是多少?
（要求写出分析过程）
（147-143）+（150-147）+（150-130）+（130-102）+（102-94）+（94-91）+（91-86）=162
5.银行家算法（操作系统）
在银行家算法中，某T0时刻的资源分配情况如下：
（有三类资源A、B、C，五
个进程P0、P1、P2、P3、P4）
MaxAllocationNeedAvailable
ABCABCABCABC
P0753010743332
P1322200122
P2902302600
P3222211011
P4433002431
试问：
1.该状态是否安全？
2.在T0时刻，P1发出请求Request（1，1，2），系统能否满足？
为什么？
答案：
1、这是安全状态：
P1的需求小于可用资源数，先满足P1的请求，然后回收P1资源：
可用资源变为（3,3,2）＋（2,0,0）＝（5,3,2）；
这时P3可分配，P3结束后回收资源，可用资源为（5,3,2）＋（2,1,1）＝（7,4,3）
这时P0可分配，P0结束后回收资源，可用资源为（7,4,3）＋（0,1,0）＋（7,5,3）
接下来是P2，结束后可用资源为（7,5,3）＋（3,0,2）＝（10,5,5）
最后分配P4，结束后可用资源为（10,5,5）＋（0,0,2）＝（10,5,7）
这样得到一个安全序列：
P1－P3－P0－P2－P4，所以T0状
升级会员 