《操作系统OS》期末复习笔记（引论、进程描述与控制、处理机调度与死锁、存储器管理、虚拟存储器、系统调用概念及UNIX系统命令）

足够小的内核，只装入：
- 与硬件处理紧密相关的部分
- 一些较基本的功能
- 客户和服务器之间的通信
基于客户/服务器模式
- 最基本的部分放入内核
- 绝大部分功能放在内核外的一组服务器（进程）中实现，如进程(线程)管理服务器、虚拟存储器管理服务器
应用“机制与策略分离”原理
- 将机制（实现某一功能的具体执行机构）放入内核中
采用面向对象技术

基本功能：

进程（线程）管理：最基本的功能
- 核内：进程通信、切换、调度、多处理机间的同步（机制）
- 核外：对进程类型和优先级的确认（策略）
低级存储器管理
- 核内：依赖于硬件的页表机制和地址变换机制（机制）
- 核外：页面置换算法、内存分配和回收策略（虚拟存储器管理策略）
中断和陷入处理
- 核内：捕获所发生的中断和陷入事件，并进行相应的前期处理如：现场保护、识别类型、转换为消息并发送给服务器
- 核外：根据类型调用程序做后期处理

优点：

可扩充性强：许多功能是由相对独立的服务器软件来实现的
可靠性强：微内核经过精心设计和严格测试
可移植性强：除核内的与特定CPU、I/O相关的代码，各种服务器与硬件平台无关
支持分布式系统（和网络系统）：客户与服务器、服务器与服务器之间采用消息传递通信机制
融入了面向对象技术：“封装”、“继承”、“对象类”、“多态性” -> 正确性、可靠性、易修改性、易扩展性

缺点：

运行效率低下，原因：

利用消息实现多次交互
需要多次上下文切换
- 传统OS结构两次上下文切换：
  第一次：执行系统调用后由用户态转为系统态
  第二次：系统完成用户请求后，由系统态返回用户态
- 微内核OS结构四次（1.客户发送的请求消息给内核、2.内核把该请求消息发往服务器、3.服务器把响应消息发给内核、4.内核把该响应消息发给客户）或八次（实际情况中更多，如图，当某个服务器自身无法完成请求时）上下文切换：

目前绝大部分都使用的是速度更快的宏内核。

四大基本特性

并发：两个或多个事件在同一时间间隔内发生（v.s.并行：同一时刻同时）
共享：系统中的资源可供内存中多个并发执行的进程共同使用
- 互斥共享方式
- 同时访问方式
虚拟：通过某种技术将一个物理实体变为若干个逻辑上的对应物的功能
- 时分复用
  - 虚拟处理机技术
  - 虚拟设备技术
- 空分复用：为提高存储空间的利用率
异步：进程以不可预知的速度向前推进，多次执行，结果相同

并发和共享是（多任务）操作系统最基本的特征、他们又是互为存在的条件，虚拟以并发和共享为前提，异步是并发和共享的必然结果。

进程的描述与控制

进程=程序段+相关数据段+PCB，进程是程序的一次执行。

进程的基本状态和转换

三种基本状态：

就绪：已分配到除CPU以外的所有必要资源，只要再获得CPU，便可立即执行
执行
阻塞：缺少CPU、内存、外部资源。

挂起操作引入的原因：终端用户的需要/父进程请求/调节负载需要/操作系统需要
静止就绪状态：缺cpu、内存
静止阻塞状态：缺cpu、内存、I/O

PCB

PCB：process control block，进程控制块，是操作系统中最重要的记录型数据结构。

作用：使一个在多道环境下不能独立运行的程序（含数据）成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。

作为独立运行基本单位的标志：创建进程时创建PCB，结束时回收PCB。PCB是进程存在于系统的唯一标志。
能实现间断性运行方式：实现CPU现场保护
提供进程管理所需要的信息：PCB记录程序和数据在内存或者外存中的始址指针
提供进程调度所需要的信息：进程当前状态、优先级、等待时间、执行时间
实现与其它进程的同步与通信：信号量机制

信息：

进程标识符
- 外部标识符：方便用户(进程)对进程的访问，通常由字母和数字组成
- 内部标识符：方便系统对进程的使用，通常就是进程的序号
处理机状态：保证进程重新执行时是从断点继续执行
- 通用寄存器：用户可视寄存器，用于暂存信息
- 指令计数器：存放要访问的下一条指令的地址
- 程序状态字PSW：状态信息
- 用户栈指针：存放用户进程参数和调用地址
进程调度信息
- 进程状态：是进程调度和对换的依据，不属于处理机状态
- 进程优先级
- 进程调度所需的其他信息（与调度算法有关）：如等待CPU时间总和
- 事件：即阻塞原因
进程控制信息
- 程序和数据的地址
- 进程同步和通信机制
- 资源清单：所需全部资源(CPU除外)、已分配到的资源
- 链接指针：本进程(PCB)所在队列的下一个进程的PCB的首地址

组织方式：

线性方式
链接方式
索引方式

进程的创建与终止

shell进程无父进程（不是所有进程都是由父进程创建的）

引起进程创建的事件：

用户登录：在分时系统中，用户登陆成功系统即为该用户建立一个进程兵将它插到就绪队列中
作业调度
提供服务：当运行中的用户程序提出某种请求后，专门创建一个进程来提供用户所需的服务。如：打印进程与用户进程并发执行
应用请求：以上三种都是系统内核为用户建立一个新进程，这类事件是由用户进程自己创建新进程。如：键盘输入进程、显示器输出进程并发执行

进程创建过程：

申请空白PCB
为新进程分配其运行所需的资源，包括各种物理和逻辑资源，如内存、文件、I/O设备和CPU时间等
初始化进程控制块(PCB)
1. 初始化标识信息
2. 初始化处理机状态信息：程序计数器指向程序入口地址、栈指针指向栈顶
3. 初始化处理机控制信息：就绪或静止就绪状态，通常设置为最低优先级
如果进程就绪队列能够接纳新进程，就将其插入就绪队列

引起进程终止的事件：

正常结束：进程的任务已完成
异常结束（记）
- 越界错
- 保护错：试图访问一个不被允许访问的文件
- 非法指令：试图执行一条不存在的指令
- 特权指令错：用户程序试图执行一条只允许OS执行的指令
- 运行超时
- 等待超时
- 算术运算错
- I/O故障
外界干预
- 操作员或操作系统干预
- 父进程请求：子进程已完成父进程的要求的任务
- 因父进程终止：父进程终止时，他的所有子孙进程也都应当结束

进程终止过程：

根据被终止进程的标识符，检索出PCB并从读出该进程状态
若正处于执行状态，应立即终止，并置调度标志为真
若还有子孙进程，应一并终止，防止他们成为不可控的进程
将被终止的进程拥有的所有资源或归还给父进程，或归还给操作系统
将被终止进程(PCB)从所在队列(或链表)中移出，等待其他程序来搜集信息

进程同步（机制）

临界资源：许多硬件资源如打印机、磁带机等，逐进程间应采取互斥方式实现对这种资源的共享

临界区：访问临界资源的一段代码

进入区：检查本进程是否能进入临界区的代码
退出区：将临界区正被访问的标志恢复为未被访问的标志

同步机制应遵循的规则：（记）

空闲让进：若干进程要求进入空闲临界区时，应尽快使一进程进入临界区。
忙则等待：临界区正在访问，则等待。以保证对临界资源的互斥访问。
有限等待：对要求访问临界资源的进程，应保证有限时间内能进入自己的邻接区，以避免陷入“死等”状态。
让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态。

进程同步机制：

硬件同步机制
- 关中断
- 使用Test-and-Set指令实现互斥：硬件指令“测试并建立”进行原子操作
- 使用Swap指令实现互斥，但2.3.硬件同步指令都不符合“让权等待”原则，当临界资源忙碌时，其他访问进程都必须不断地进行测试，造成处理机时间的浪费，也不适用于复杂的进程同步问题。
信号量机制：1965年荷兰学者迪杰斯特拉提出
- 整型信号量：P（通信）、V（同步），wait和signal操作成对出现，解决“忙则等待”
- 记录型信号量：增加一个进程链表指针，用于链接所有等待进程，解决“让权等待”
- AND型信号量：将进程在整个运行过程中需要的所有资源，一次性的分配给进程，待进程使用完后再一起释放。前面两者容易进入“死等”。
- 信号量集：当进程申请某类临界资源时，在每次分配之前，都必须测试资源的数量，判断是否大于可分配的下限值，决定是否予以分配。

信号量的应用：

实现进程互斥 赋初值1
实现前驱关系 赋初值0

经典进程同步问题

生产者-消费者问题
哲学家进餐问题
读者-写者问题：允许多个进程同时读一个共享对象，因为读操作不会使数据文件混乱，但不允许一个写进程和其他读进程或写进程同时访问共享对象。readcount=0：无读者or有写者

独木桥（有载重）
int countA = 0、countB = 0; //分别表示AB两个方同过桥的行人数量
semaphore bridge = 1; //用来实现两边行人对桥的互斥共享
semaphore mutexA = 1、mutexB = 1 //分别用来实现对countA.countB的互斥共享
semaphore mA =n, mB = n; //对桥上负载的人的数量控制
void PA()
{
	do
	{
		wait(mA);
		wait(mutexA);
		if(countA==0) wait(bridge);
		countA++;
		signal(mutexA);
		// 过桥 //
		wait(mutexA);
		countA--;
		if(countA==0) signal(bridge);
		signal(mutexA);
		signal(mA)
	}while(TRUE)
}
void PB()
{
	do
	{
		wait(mB);
		wait(mutexB);
		if(countAB==0) wait(bridge);
		countB++;
		signal(mutexB);
		// 过桥 //
		wait(mutexB);
		countB--;
		if(countB==0) signal(bridge);
		signal(mutexB);
		signal(mB)
	}while(TRUE)
}

进程通信

进程通信：进程之间的信息交换。

低级进程通信：

效率低
对用户不透明

进程通信的类型：

共享存储器系统：两个进程对共享空间的访问一定是互斥的
管道通信系统：创建一个特殊的共享文件：管道
- 管道只能采用半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道。
- 各进程要互斥地访问管道。
- 数据以字符流的形式写入管道，当管道写满时，写进程的write()系统调用将被阻塞，等待读进程将数据取走。当读进程将数据全部取走后，管道变空，此时读进程的read()系统调用将被阻塞。
- 如果没写满，就不允许读。如果没读空，就不允许写。(严格意义上是这样，有些情况会放松)
- 数据一旦被读出，就从管道中被抛弃，这就意味着读进程最多只能有一个，否则可能会有读错数据的情况。
消息传递系统：以格式化的消息为单位，把通信的数据封装在消息中，属于高级通信方式
- 直接通信方式：直接利用OS所提供的发送原语
- 间接通信方式：通过共享中间实体（邮箱）
客户机-服务器系统

线程（Thread）的基本概念

线程拥有TCB。

其中：

资源分配的基本单位：进程
同一个进程中的多个线程也可并发执行
同一进程中的不同线程共享进程的内存地址和资源，即同一进程中的两段代码若引入线程，就可同时执行了

（a）用户级线程ULT：模式切换开销小
（b）内核支持线程KST：内核支持多个线程并行执行
（c）组合方式

处理机调度与死锁

调度的层次和目标

处理机调度的层次：

高级调度：对象是作业，将作业从后备队列(外存)调入内存，主要运用于多道批处理系统
低级调度：对象是进程(或内核级线程)，主要运用于多道批、分时、实时系统
中级调度：目的是提高内存利用率和系统吞吐量

处理机调度算法的目标：

共同目标
1. 资源利用率：CPU有效工作时间/（有效工作时间+空闲时间）
2. 公平性：相对的，指逐进程都获得合理的CPU时间
3. 平衡性：保持资源使用的平衡性
4. 策略强制执行
批处理系统的目标
1. 平均周转时间短：从任务进入到完成，带权平均周转时间短：
2. 系统吞吐量高：单位时间内完成的作业数多
3. 处理机利用率高
分时系统的目标
1. 响应时间快
2. 均衡性：系统响应时间的快慢与用户所请求服务的复杂性相适应
实时系统的目标
1. 截止时间的保证
2. 可预测性

调度算法

作业和作业调度

作业运行的三个阶段和三种状态：（v.s.进程的三种基本状态：就绪、执行、阻塞）

收容阶段、后备状态
运行阶段、运行状态
完成阶段、完成状态

作业调度算法：

先来先服务(FCFS)算法：按作业到达的先后次序来进行调度，平均周转时间长，且不适合解决紧急任务
短作业优先(SJF)算法：作业越短(运行时间短)，优先级越高，但必须预知作业的运行时间，且对长作业非常不利、无法实现人机交互、完全未考虑作业的紧迫程度
高响应比优先(HRRN)调度算法：既考虑了作业的等待时间，又考虑了作业的运行时间。优先权=响应比=（等待时间+要求服务时间）/要求服务时间=响应时间/要求服务时间。
- 等待时间相同：要求服务时间越短，优先权越高，类似于SJF
- 要求服务时间相同：等待时间越长，优先权越高，类似于FCFS
- 对于长作业的优先级，随等待时间的增加而提高，等待时间足够长时也可以获得处理机

进程调度

进程调度的任务：

保存处理机现场信息
按某种算法选取进程
把处理机分配给进程

进程调度机制：

进程调度方式：

非抢占方式：不会因为时钟中断或任何其他原因去抢占当前正在运行进程的处理机，直至该进程完成或发生某事件而被阻塞。不适用于分时系统和大多数的实时系统。
抢占方式：对于批处理系统，提供更公平的服务。主要原则有：
- 优先权原则
- 短进程优先原则
- 时间片原则

进程调度算法：

作业调度的三个算法在进程调度中同样适用
基于时间片的轮转(RR)调度算法：根据FCFS策略，并设置每隔一定的时间间隔产生一次中断，完成一次调度，将CPU分配给队首进程。隐含假设：系统中所有进程的紧迫性是相同的。
- 进程切换时机：
  - 若一个时间片尚未用完，正在运行的进程已经完成，就立即激活调度程序
  - 在一个时间片用完时，计时器中断程序被激活，若进程尚未执行完毕，就将其送往就绪队列的队尾。
- 时间片大小的选择：
  - 若小：则利于短作业，但会频繁执行进程调度和上下文切换，增大系统开销
  - 若大：则退化为FCFS算法，无法满足短作业和交互式用户的需求
- 例（已知到达时间、服务时间、时间片长度，带权周转时间=周转时间/服务时间）
优先级调度算法
- 非抢占式优先级调度算法：一次分配，直至运行结束。
- 抢占式优先级调度算法：一次分配，若有更高优先级的进程出现，则让出处理机。
  - 优先级的类型：
    - 静态优先级：在创建进程时确定的，在进程的整个运行期间保持不变
      - 进程类型：系统进程 > 用户进程
      - 进程对资源的需求：资源少 > 资源多
      - 用户要求：紧迫程度、是否付费
    - 动态优先级：指在创建进程之初，先赋予其一个优先级，然后其值随进程的推进或等待时间的增加而改变
多队列调度算法：不同的就绪队列采用不同的调度算法
多级反馈队列调度算法：不必事先知道各种进程所需的执行时间
- 1.设置多个就绪队列，第一个队列的优先级最高，第二个次之，其余队列优先级依次降低。优先级越高的队列时间片越短，时间片一般是2的n次方（n=0,1,2......）
- 2.每个队列采用FCFS算法，将其一次放在每个队列的末尾，运行不完就降级，当被降到最后一个队列时，采用时间片轮转(RR)算法
- 3.按队列优先级调度：仅当第1~i-1所有队列均为空时，才调度第i个队列中的进程运行。若处理机正在第i队列中为某进程服务时又有新进程进入任一优先级高的队列，须立即把正在运行的进程放回当前队列末尾，并重新分配处理机给优先级更高的进程。
基于公平原则的调度算法：
- 保证调度算法：如果在系统中有n个相同类型的进程同时运行，为公平起见，须保证每个进程都获得相同的处理机时间1/n。
- 公平分享调度算法：解决各个用户所拥有的进程数不同，对用户的不公平问题。
实时调度：（任务处理时间/任务周期时间）求和小于等于处理机核数
- 最早截止时间优先算法（非抢占式主要用于非周期任务、抢占式主要用于周期任务）
- 最低松弛度优先算法：主要用于可抢占式，松弛度 = 必须完成的时间-本身运行的时间-当前时间
- 优先级倒置：即高优先级进程(或线程)被低优先级进程(或线程)延迟或阻塞，解决：优先级继承，在实时操作系统中是必须的。

死锁概述

死锁：每个进程所等待的事件是该组中其它进程释放所占有的资源。

引起死锁的原因：（记）

竞争不可抢占性资源
- 形成环路等待
竞争可消耗资源
- 始终阻塞在各自的receive进程上
程序推进顺序不当
- 进程占有了一些资源，又不释放，再去申请其他资源

产生死锁的必要条件：（记）（必须同时具备以下四个条件）

互斥条件：进程对分配到的资源进行排他性使用，即在一段时间内，某资源只能被一个进程所占有
请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，该资源已经被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源又保持不放
不可抢占条件：进程已获得的资源在未使用完之前不能被抢占，只能等进程使用完自己释放
循环等待条件：必然存在一个进程--资源循环链，即{P0,P1,P2......Pn}中的P0在等待一个P1占用的资源，P1在等待一个P2占用的资源，......，Pn在等待一个P0占用的资源。

避免死锁

银行家算法（迪杰斯特拉）

数据结构
算法概述
安全性算法（注：是找到任意一个满足分配的，而不是按请求资源的顺序）

例题（书后）：

死锁的检测：资源分配图。找出一个既不阻塞又非独立的进程结点Pi。在顺利的情况下，Pi可获得所需资源而继续运行，直至运行完毕，再释放其所占有的全部资源，这相当于消去Pi的请求边和分配边，使之成为孤立的结点。若能消去图中所有的边，使所有的进程结点都成为孤立结点，则称该图是可完全简化的。

存储器管理

程序的装入和链接

程序的装入：

绝对装入方式：当计算机系统很小，且仅能运行单道程序时。用户程序经编译后，将产生绝对地址(即物理地址)。只能将目标模块装入到内存中事先指定的位置。
可重定位装入方式：在多道程序环境下，模块的起始地址通常都是从0开始。根据内存的具体情况将装入模块装入到内存的适当位置。不允许程序运行时在内存中移动位置。
动态运行时的装入方式：在具有对换功能的系统中，一个进程可能被多次患处，又多次被换入，每次换入后的位置通常都是不同的。

程序的链接：

功能：将编译得到的这组目标模块以及它们所需要的库函数装配成一个完整的装入模块。

静态链接方式：在程序运行之前，先将各目标模块及他们所需的库函数链接成一个完整的装配模块，以后不再拆开，必须解决如下两个问题：
- 对相对地址进行修改
- 变换外部调用符号
装入时动态链接：采用边装入内存边链接的链接方式，有以下两个优点：
- 便于修改和更新
- 便于实现对目标模块的共享
运行时动态链接：在执行过程中，若发现一个被调用模块尚未装入内存时，立即由OS去找到该模块，并将之装入内存，将其链接到调用者的模块上。

连续分配存储管理方式

单一连续分配：在单道程序环境下
固定分区分配：必然存在浪费的情况
- 分区大小相等：不灵活
- 分区大小不等
动态分区分配：
- 常用的数据结构：空闲分区表or空闲分区链
- 分配内存：（设请求分区的大小是u.size，每个表中空闲的是m.size，若剩余的小于预先指定的size，就不再进行分割）
- 回收内存
  - 回收区与前一个空闲分区F1相邻接，只需修改F1的大小（a）
  - 回收区与后一个空闲分区F2相邻接，首址用新空闲区的首址，大小为两者之和（b）
  - 回收区同时与前、后两个空闲分区相邻接，首址用F1的首址，取消F2的表项，大小为三者之和（c）
  - 回收区前后没有邻接空闲区，则建立一个新表项，填写首址和大小，并根据其首址插入空闲链的适当位置

基于顺序搜索的动态分区分配算法

比较适用于不太大的系统。

首次适应（FF）算法：空闲分区链以地址递增的次序链接，每次分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的分区位置，然后再按作业大小从该分区中划分出一块内存空间，余下的空闲分区仍留在空闲链中。该算法倾向于优先利用内存中低地址部分的空闲分区，从而保留了高地址部分的大空闲区，这为以后达到的大作业创造了条件。但缺点是低地址部分会被不断划分，留下许多碎片，而每次查找又是从低地址部分开始的，增加了查找开销。
循环首次适应（NF）算法：从上次找到的空闲分区的下一个空闲分区开始查找，若链尾仍不满足，则返回第一个空闲分区。使内存中的空闲分区更均匀，减少查找开销，但会缺乏大的空闲分区。
最佳适应（BF）算法：将每次分配后的分区链重新按其容量大小从小到大排序。这样，第一次找到的能满足的一定是最佳的，孤立的看确实如此。但宏观上不一定，因为增加了管理分区链的开销，且会留下许多难以利用的碎片。
最坏适应（WF）算法：与最佳适应策略恰好相反，每次都挑选最大空闲分区。产生碎片的可能性最小，对中、小作业有利，且查找效率很高(只用检查第一个分区能否满足作业要求即可)。但存储器中缺乏大的空闲分区。
例：

基于索引搜索的动态分区分配算法

适用于大、中型系统。

快速适应（quick fit）算法：又称分类搜索法，是将空闲分区根据其容来农大小进行分类。这样系统中就拥有多个空闲分区链。分类的依据是根据进程常用的空间大小，如2KB、4KB、8KB等。缺点：有效合并分区时系统开销较大，且分配分区是以进程为单位的，以空间换时间。
伙伴系统（buddy system）：规定无论已分配分区或空闲分区，大小均为2的k次幂（k为大于等于1的整数）。对于具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表，形成k个空闲分区链表。拆解的空间的一对分区称为一对伙伴。
哈希算法：利用哈希快速查找的优点。

动态可重定位分区分配：

紧凑：把原来分散的多个空闲小分区拼成一个大分区
动态重定位：在系统中设立一个重定位寄存器（硬件）

对换

一个进程不是所有的指令和数据都调入内存才可执行。

分时系统中的对换系统：外存的后备队列与内存中的作业对换，现在已很少使用。

对文件区管理的主要目标：提高文件存储空间的利用率，故常用离散分配方法
对兑换空间管理的主要目标：提高进程换入和换出的速度，采用连续分配方式，较少考虑外存中的碎片问题

目前主要广泛使用在多道程序环境下。按所对换的数量分类：

整体对换
页面（分段）对换--（部分对换）

离散分配存储管理方式

为提高内存利用率。

分页存储管理方式

对用户完全不透明。教材中默认页表项长度为4B(即地址结构总共32位)。页面大小固定，且每一页的大小都一样。页面大小应选择适中，且应是2的幂，通常为1-8KB。

进程的各个页离散的存储在内存的任一物理块中，在内存中找到每页对应的物理块--页面映像表，简称页表--实现页号到物理块号的映射。一个进程对应一个页表。

地址变换机构：

由于页内地址和物理块地址是一一对应的（页面大小是1KB的页内地址是0~1023，其对应的物理块内的地址也是0~1023，无需再进行转换），地址变换机构的任务实际上就是将页号转为内存中的物理块号，借助页面映射表，即页表来实现。执行一次指令访问两次内存：1.访问页表；2.根据物理地址访问数据。

基本的地址变换机构 EAT(Effective Access Time，有效访问时间)=t+t=2t
具有快表的地址变换机构 (快表又称为联想寄存器、TLB，用于存放当前访问的页表项)提高速度，但不能提高利用率，也不能实现存储扩充。EAT=а×λ+(1-а)(λ+t)+t=2t+λ-t×а，λ表示查找快表所需要的时间，а表示命中率，t表示访问一次内存所需要的时间。

两级和多级页表

针对难于找到大的连续的内存空间来存放页表的问题，可利用将页表进行分页的方法，，每个页面的大小与内存物理块大小相同。要访问（页表级数+1）次内存（无快表的情况下）。

若采用多级页表机制，则各级页表的大小不能超过一个页面。

还介绍了反置页表

分段存储管理方式

目的：主要是为了满足用户(程序员)在编程和适应上多方面需求。

段是以信息的逻辑单位为基础的，而“页”并无完整的逻辑意义，是信息的物理单位。每个段通常都从0开始编址，并采用一段连续的地址空间，各段的长度并不相等（v.s.页：大小固定长度相等）。

段表：格式、功能类似于页表

地址变换机构：

段表始址与段表长度从PCB转移到控制寄存器中。访问两次内存

段表始址：段表存放的初始地址；
段表长度：段表项的数量。

分页和分段的主要区别：

页是信息的物理单位。段是信息的逻辑单位。
页的大小固定且由系统决定。段的长度不固定。
分页的用户程序地址空间是一维的。需要同时给出段名与段内地址。

段页式存储管理方式

一个进程可具有一个段表+多个页表，若段表项过长，就退化为连续分配方式了。

虚拟存储器

从逻辑上扩充内存容量。虚拟存储器的特征：

多次性
对换性：多次性和对换性建立在离散分配的基础上
虚拟性：以多次性和对换性为基础

请求分页存储管理方式

请求页表：基本作用仍是将用户地址中的逻辑地址映射为内存空间中的物理地址。

缺页中断

缺页中断：每当要访问的页面不在内存时，便产生一次缺页中断，请求OS将所缺之页调入内存。

步骤：

保护CPU环境
分析中断原因
转入缺页中断处理程序处理
恢复CPU环境

与一般中断的区别：

在指令执行期间产生和处理中断信号（v.s.一般中断在指令执行完后才检查并处理）
一条指令在执行期间可能产生多次缺页中断（如图，6次）硬件机构应能保存多次中断时的状态，并保证能返回到中断前产生缺页中断指令处继续执行。

缺页率：假设一个进程的逻辑空间为n页，系统为其分配的内存物理块数为m(m≤n)。如果在进程的运行过程中，访问页面成功(即所访问页面在内存中)的次数为S，访问页面失败(即所访问页面不在内存中，需要从外存调入)的次数为F，则该进程总的页面访问次数为A = S + F，那么该进程在其运行过程中的缺页率即为：f = F/A，影响缺页率的因素有：

页面大小：页面越大，缺页率越低
进程所分配物理块的数目：物理块数目越多，缺页率越低
页面置换算法：算法越好，缺页率越低
程序固有特性：程序编制的局部化程度越高，缺页率越低

地址变换机构：在分页方式的基础上修改

页面置换算法

好的置换算法应将以后不再访问的页面换出，或将较长时间不会再访问的页面调出。

最佳置换算法（理论值）：其所选择的被淘汰页面将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法通常可保证获得最低的缺页率。但由于人们目前还无法预知，一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用该算法去评价其它算法。
先进先出（FIFO）页面置换算法：该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。
最近最久未使用LRU(Least Recently Used)置换算法：v.s.FIFO算法，LRU根据页面调入内存后的使用情况做出决策的。
- LRU算法的硬件支持：
最少使用(Least Frequently Used，LFU)置换算法：在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。该置换算法选择在最近时期使用最少的页面作为淘汰页。
CLOCK置换算法：设置访问位，刚进入时访问位置1，从队首的下一位开始检查，若命中，队首不变，命中元素的访问位置1。

访问内存的有效时间

教材中还介绍了抖动与工作集

对磁盘的有效访问时间也随之急剧增加，造成每个进程的大部分时间都用于页面的换进/换出，而几乎不能再去做任何有效的工作，从而导致发生处理机的利用率急剧下降并趋于0的情况。我们称此时的进程是处于“抖动”状态。
所谓工作集，是指在某段时间间隔Δ里，进程实际所要访问页面的集合。

请求分段存储管理方式

请求段表机制：

缺段中断机构：

由于分段是信息的逻辑单位，因而不可能出现一条指令被分割在两个分段中，和一组信息被分割在两个分段中的情况。

地址变换机构：

因为被访问的段并非全在内存，所以在地址变换时，若发现所要访问的段不在内存，必须先将所缺的段调入内存，并修改段表，然后才能再利用段表进行地址变换。为此，在地址变换机构中又增加了某些功能，如缺段中断的请求及处理等。

分段有利于共享和保护。共享段表：count为0时，回收该段表内存空间。

系统调用的概念、类型和命令

进程控制类：
- fork：创建进程
- exit：终止进程
- exec：执行一个文件
- wait：等待子进程结束
文件操纵类：
- create：创建文件
- open、close：打开、关闭文件
- read、write：读、写文件
- link、unlink：链接、去链接
进程通信类：
- msgget、msgsend
设备管理类
内存管理类