操作系统

记录一下《计算机操作系统》这本书，可能以后也会用到，所以一直会更新下去，直到读完

引论

操作系统的目标

1. 方便性
2. 有效性
   有效性的第一层含义是提高系统资源的利用率。另一层含义是，提高系统的吞吐量。OS可以通过合理地组织计算机的工作流程，加速程序的运行，缩短程序的运行周期，从而提高了系统的吞吐量。
3. 可扩充性
   OS从早期的无结构发展称模块化结构，进而发展成层次化结构，近年来广泛采用了微内核结构，具有良好的可扩充性。
4. 开放性
   指系统能遵循世界标准规范，特别是遵循开放系统互连OSI国际标准。

操作系统的作用

1. OS作为用户与计算机硬件系统之间的接口
   用户通过命令方式、系统调用方式和图标——窗口方式来实现与操作系统的通信
2. OS作为计算机系统资源的管理者
   OS中的资源分为四类：处理机、存储器、I/O设备以及文件（数据和程序）
3. OS实现了对计算机资源的抽象
   OS是铺设在计算机硬件上的多层软件的集合，不仅增强了系统的功能，还隐藏了对硬件操作的具体细节，实现了对计算机硬件操作的多个层次的抽象模型。

单道批处理系统

1. 处理过程
   简单来说就是将作业装在磁带上，一个一个单个处理，如图：
   
2. 缺点
   资源得不到充分利用，如图：
   

多道批处理系统

1. 处理过程
   用户所提交的作业先放在外存上，并排成一个队列，称为“后备队列”。然后由作业调度程序按一定的算法，从后备队列中选择若干个作业调入内存，使它们共享CPU和系统中的各种资源。
2. 优缺点
   （1）资源利用率高
   （2）系统吞吐量大
   （3）平均周转时间长
   （4）无交互能力

分时系统

1. 运行方式

• 作业直接进入内存
• 采用轮转运行方式（加入时间片）

2. 特征

• 多路性：系统允许将多台终端同时链接到一台主机上
• 独立性：系统提供了这样的用户各自独立环境
• 及时性：用户的请求很短时间内能得到相应
• 交互性：用户可通过终端进行人机对话

操作系统的种类

• 单用户单任务操作系统
• 单用户多任务操作系统
• 多用户多任务操作系统

基本特性

并发

1. 并行与并发

• 并行性是指两个或多个事件在同一时刻发生
• 并发性是指两个或多个事件在统一时间间隔内发生

2. 引入进程

• 进程是指：在系统中能独立运行并作为资源分配的基本单位，它是由一组机器指令、数据和堆栈等组成的，是一个能独立运行的活动实体。

共享

1. 互斥共享方式
   一个进程访问完资源后，资源才能被另一个进程访问。资源叫做临界资源
2. 同时访问方式

虚拟

在os中，把通过某种技术将一个物理实体变为若干个逻辑上的对应物的功能称为虚拟。

1. 时分复用技术（时间）
2. 空分复用技术（空间）

操作系统的功能

处理机管理功能

1. 进程控制：为作业创建进程、撤销（终止）已结束的进程，以及控制进程在运行过程中的状态转换。
2. 进程同步：

• 进程互斥方式：指诸进程在对临界资源进行访问时，应采用互斥方式
• 进程同步方式：指在相互合作去完成共同任务的诸进程间，由同步机构对它们的执行次序加以协调。

3. 进程通信：通常采用直接通信方式，由源进程利用发送命令直接将消息挂到目标进程的消息队列上，以后由目标进程利用接受命令从其消息队列中取出消息
4. 调度

• 作业调度：从后备队列中按一定算法取出若干队列。为其分配运行所需资源。
• 进程调度：从就绪队列中按照一定的算法选出一个进程，执行。

存储器管理功能

1. 内存分配

• 静态分配方式：每个作业的内存空间是在作业装入时确定的，在作业装入后的整个运行期间不允许该作业再申请新的内存空间。
• 动态分配方式：允许申请新的空间。

2. 内存保护：每个程序互不打扰，操作系统的程序和数据不允许访问。
3. 地址映射
4. 内存扩充

• 请求调入功能：将程序所需部分从存储器中调入内存
• 置换功能：将内存和磁盘的数据进行置换

进程的描述与控制

进程通信

进程通信的类型

1. 共享存储器系统

• 基于共享数据结构的通信方式。

处理机调度与死锁

处理机调度的层次和调度算法的目标

处理机调度的层次

1. 高级调度
   调度对象是作业，其主要功能是根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存，为其创建进程、分配资源，放入就绪队列，主要应用于多道批处理系统
2. 低级调度
   又称为进程调度或短程调度，其调度对象是进程(或内核级线程)。其主要功能是根据某种算法决定就绪队列中的哪个进程应获得处理机。
3. 中级调度
   提高内存利用率和系统吞吐量，把暂时不能运行的进程调至外存，把能运行的调至内存。

处理机调度算法的目标

1. 处理机调度算法的共同目标
   (1)资源利用率 CPU的利用率 = CPU的有效工作时间/(CPU的有效工作时间+CPU的空闲等待时间)
   (2)公平性 每个进程都应该获得合理的CPU时间
   (3)平衡性 尽可能保持系统资源使用的平衡性
   (4)策略强制执行 对所制订的策略，保证其准确执行
2. 批处理系统的目标
   (1)平均周转时间短
   (2)系统吞吐量高
   (3)处理机利用率高
3. 分时系统的目标
   (1)响应时间快
   (2)均衡性
4. 实时系统的目标
   (1)截止时间的保证
   (2)可预测性

作业与作业调度

1. 作业与作业步
   (1)作业。不仅包含通常的程序和数据，还包括一份作业说明书，再批处理系统中，作业为基本单位从外存调入内存
   (2)作业步。每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果。每个步骤叫做一个作业步。
2. 作业的三种状态和三个阶段

• 收容阶段，操作员把用户提交的作业通过某种输入方式输入到硬盘上，再为该作业建立JCB，并把它放入作业后备队列中。(后备状态)
• 运行阶段(运行阶段)
• 完成阶段(完成阶段)

3. 先来先服务和短作业优先调度算法

• 先来先服务调度算法(FCFS)
• 短作业优先调度算法(SJF):作业越短优先级越高
• 优先级调度算法(PSA):外部赋予作业优先级
• 高响应比优先调度算法(HRRN):优先权 = (等待时间+要求服务时间)/要求服务时间

进程调度

进程调度方式

1. 非抢占方式
   一旦处理机分配给某进程后，就一直让它运行下去，不会因为时钟中断而被抢占。
   可能引起进程调度的因素：

• 程序执行完毕，或发生某种事件使程序无法执行
• I/O请求
• 原语操作如Block
  不适用于分时系统和大多数实时系统

2. 抢占方式
   允许调度程序根据某一原则暂停执行中的程序，分配处理机给新的进程
   原则：

• 优先权原则：高优先级先运行
• 短进程优先原则
• 时间片原则：时间片用完就暂停执行

  轮转调度算法

  就绪队列上的每个进程每次仅运行一个时间片。

1. 原理
   系统将所有的就绪进程按FCFS策略排成一个就绪队列。
2. 进程切换时机

• 执行完成
• 时间片用完，计时器中断处理程序被激活

3. 时间片大小的确定
   略大于典型交互时间

   优先级调度算法

4. 类型

• 非抢占式优先级调度算法：一旦处理机分配给了优先级最高的进程，则一直执行下去直至完成。
• 抢占式优先级调度算法：出现了更高优先级的进程，中断当前执行进程，转而去执行更高优先级的进程。

2. 优先级的类型

• 静态优先级：进程运行过程中优先级保持不变
• 动态优先级：随着时间增加而改变

  多队列调度算法

  将系统中的进程就绪队列从一个拆分成若干个，将不同类型或性质的进程固定分配在不同的就绪队列，不同的就绪队列采用不同的算法。

  多级反馈队列调度算法

1. 调度机制

• 设置多个就绪队列，每个队列不同的优先级不同的时间片大小，在优先级愈高的队列中，其时间片就越小。
• 每个队列采用FCFS算法。
• 按队列优先级调度。

  基于公平原则的调度算法

1. 保证调度算法
   这里的保证并不是优先运行，而是性能保证。

• 跟踪计算每个进程自创建以来已经执行的处理时间
• 计算每个进程应获得的处理机时间，即自创建以来的时间除以n
• 计算进程获得处理机时间的比率，即进程实际执行的处理时间和应获得的处理机时间之比
• 比较各进程获得处理机时间的比率
• 选择比率最小的进程将处理机分配给它，知道超过最接近它的进程比率

2. 公平分享调度方法
   对用户公平

实时调度

实现实时调度的基本条件

1. 提供必要的信息
   (1)就绪时间
   (2)开始截止时间和完成截止时间
   (3)处理时间
   (4)资源要求
   (5)优先级
2. 系统处理能力强
3. 采用抢占式调度机制
4. 具有快速切换机制
   (1)对中断的快速响应能力
   (2)快速的任务分派能力

   实时调度算法的分类

5. 非抢占式调度算法

• 非抢占式轮转调度算法
• 非抢占式优先调度算法

2. 抢占式调度算法

• 基于时钟中断的抢占式优先级调度算法
• 立即抢占的优先级调度算法

最早截止时间优先算法(EDF)

任务的截止时间愈早，其优先级愈高，具有最早截止时间的任务排在队列的队首。

最低松弛度优先算法(LLF)

松弛度 = 必须完成的时间 - 其本身的运行时间 - 当前时间
松弛度低的先运行

优先级倒置(priority inversion problem)

低优先级和高优先级的共享一临界资源，就会导致如果低优先级的先执行，高优先级在得到处理机后，因为临界资源被占用而被堵塞，导致低优先级的先执行

• 解决方法：
  1 低优先级在进入临界区后不允许被抢占
  2 低优先级继承高优先级的优先级，率先执行完

死锁概述

资源问题

1. 可重用资源和消耗性资源

• 可重用资源：一种可供用户重复使用多次的资源，有如下性质：
  (1)每一个可重用资源中的单元只能分配给一个进程使用，不能共享
  (2)进程在使用可重用性资源时，必须先请求再使用
  (3)数目固定，进程在运行期间既不能创建也不能删除
• 可消耗资源：在进程运行期间，由进程动态创建和消耗

2. 可抢占性资源和不可抢占资源

计算机中的死锁

• 竞争不可抢占性资源引起死锁
• 竞争可消耗资源引起死锁
• 进程推进顺序不当引起死锁

死锁的定义、必要条件和处理方法

1. 定义：如果一组进程中的每一个进程都在等待仅有该组进程中的其他进程才能引发的事件，那么该组进程是死锁的
2. 产生死锁的必要条件
   (1)互斥条件。进程对所分配道德资源进行排他性使用
   (2)请求和保持条件。进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有
   (3)不可抢占条件
   (4)循环等待条件
3. 处理死锁的方法
   (1)预防死锁：通过设置某些限制条件，去破坏一个进程
   (2)避免死锁：用某种方法防止系统进入不安全状态，从而可以避免发生死锁
   (3)检测死锁：通过检测机构及时检测出死锁发生，采取适当措施
   (4)解除死锁：撤销进程，回收资源

预防死锁

破坏“请求和保持”条件

1. 第一种协议：所有进程在开始运行之前，必须一次性地申请其在整个运行过程中所需地全部资源。这样就避免了资源”请求”条件。
2. 第二种协议：允许一个进程只获得运行储器所需资源后，便开始运行。进程运行过程中在逐步释放已分给自己的、且已用毕地全部资源，然后再请求新的所需资源

   破坏“不可抢占”条件

   当一个已经保持了某些不可被抢占资源地进程，提出新的资源请求而得不到满足时，它必须释放已经保持地所有资源，待以后需要时再重新申请

   破坏“循环等待”条件

   对系统所有资源类型进行线性排序，并赋予不同的序号。规定每个进程必须按序号递增地顺序请求资源。一个进程在开始时可以请求Ri的资源，以后当且仅当F(Rj)>F(Ri)的时候才可以请求Rj的资源

避免死锁

系统安全状态

• 安全状态
  所谓的安全状态是指系统能按某种进程推进顺序(P1,P2,···,Pn)为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成

  银行家算法

  银行家算法

存储器管理

存储器的层次结构

多层结构的存储器结构

可执行存储器：寄存器和主存储器
主存储器：内存或主存，用于保存进程运行时的程序和数据
寄存器：具有与处理机相同的速度

程序的装入和链接

程序要在系统中运行，必须先将它装入内存，然后再将其转变为一个可执行的程序，需经过如下步骤：

• 编译，有编译程序对用户源程序进行编译，形成若干个目标模块
• 链接，由链接程序将编译后形成的一组目标模块以及他们所需要的库函数链接在一起，形成一个完整的装入模块
• 装入，由装入程序将装入模块装入内存

  程序的装入

  有三种装入方式：

1. 绝对装入方式
2. 可重定位装入方式
3. 动态运行时的装入方式
   装入程序把装入模块装入后，并不立即把装入模块中的逻辑地址转换为物理地址，而是等到运行时才进行

程序的链接

1. 静态链接方式
   在程序运行之前，先将各目标模块及他们所需的库函数链接成一个完整的装配模块，以后不在拆开。
   (1)对相对地址进行修改。在编译程序所产生的所有目标模块中，使用的都是相对地址。
   (2)变换外部调用符号
2. 装入时动态链接方式
   指将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式。
   有以下优点：
   (1)便于修改和更新
   (2)便于实现对目标模块的共享
3. 运行时动态链接
   对某些模块的链接推迟到程序执行时才进行

   连续分配存储管理方式

   为一个用户程序分配一个连续的内存空间，即程序中代码或数据的逻辑地址相邻，体现在内存空间分配时物理地址的相邻

   单一连续分配

   把内存分为系统区和用户区两部分，系统区仅提供给OS使用，它通常时放在内存的低址部分。而在用户区中，仅装有一道用户程序

   固定分区分配

   将整个用户空间划分为若干个固定大小的区域，在每个分区中只装入一道作业
4. 划分分区的方法
   (1)分区大小相等
   (2)分区大小不等
5. 内存分配
   为了便于内存分配，通常将分区按其大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态

动态分区分配

1. 动态分区分配中的数据结构

• 空闲分区表：在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。每个空闲分区占一个表目，表目中包括分区号，分区大小和分区始址等数据项
• 空闲分区链：每个分区的起始部分设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针，在分区尾部则设置一后向指针

2. 分区分配操作

• 分配内存
• 回收内存

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

1. 首次适应算法(FF)
   FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止，然后再按作业大小，从该分区划出一块内存空间，分配给请求者，余下的空闲分区仍留在空闲链中
   该算法倾向于优先利用内存中的低址部分的空闲分区，从而保留高址部分的大空闲区
2. 循环首次适应算法(NF)
   为了避免低址部分留下许多很小的空闲分区，以及减少查找可用空闲分区的开销，循环首次适应算法在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找
3. 最佳适应算法(BF)
   将所有空闲分区按其容量以从小到大的顺序形成一空闲分区链
4. 最坏适应算法(WF)
   将所有空闲分区按其容量以从大到小顺序形成一空闲分区链，每次挑选最大的从中分割一部分给作业使用

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

1. 快速适应算法(QF)
   分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表。同时，在内存中设立一张管理索引表，其中的每一个索引表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针
   搜索时分为两步：(1)根据进程长度，从索引表中寻找能容纳它的最小空闲区链表;(2)从链表中取下第一块进行分配即可
   缺点是在分区归还主存时算法复杂，一个分区只给一个进程容易浪费
2. 伙伴系统(buddy system)
   无论已分配分区或空闲分区，其大小均为2的k次幂。分配时找2的i次方，合并时一样
3. 哈希算法
   利用哈希快速查找的优点，以及空闲分区在可利用空闲区表中的分布规律，建立哈希函数，构造一张一空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表表头指针

动态可重定位分区分配

1. 动态重定位
   程序在执行时，真正访问的内存地址时相对地址与重定位寄存器中的低址相加而形成的，动态重定位分区与动态分区算法除了增加了”紧凑”功能外基本上相同

对换(Swapping)

多道程序环境下的对换技术

1. 对换技术：
   在系统中设置一个对换进程，由它将内存中暂时不能运行的进程调出到磁盘的对换区;同样也由该进程将磁盘上已具备运行条件的进程调入内存
2. 对换的类型：

• 整体对换:以整个进程为单位对换
• 页面(分段)对换:以一个”页面”或”分段”为单位进行对换

  对换空间的管理

1. 对换空间管理的主要目标
   (1)对文件区管理的主要目标
   提高文件存储空间的利用率，然后提高对分及的访问速度，因此，对文件区空间的管理采取离散分配方式
   (2)对对换空间管理的主要目标
   提高进程换入和换出速度，然后提高文件存储空间的利用率，因此对对换空间的管理采取连续分配方式
2. 对换区空闲盘块管理中的数据结构
   可以用空闲分区表或空闲分区链，每个表目中包含两项:对换区的首地址及其大小，分别用盘块号和盘块数表示
3. 对换空间的分配与回收
   与动态分区一样

   进程的换出与换入

4. 进程的换出
   (1)选择被换出的进程
   (2)进程换出过程
5. 进程的换入
   对换进程将定时执行换入操作，首先查看PCB集合中所有进程的状态，从中找出”就绪”状态但已换出的进程。当有许多这样的进程时，它将选择其中已换出到磁盘上时间最久的进程作为换入进程

分页存储管理方式

分页存储管理的基本方法

1. 页面与物理块
   (1)页面
   分页存储管理将进程的逻辑地址空间分成若干页，并为各页加以编号，内存的物理低址空间分为若干块，同样也为它们加以编号。为进程分配内存时，以块为单位，将进程中的若干个页分别装入到若干个可以不相邻接的物理块中。
   (2)页面大小

2. 地址结构
   分页地址包含两部分内容：前一部分为页号P，后一部分为位(偏)移量W，即页内地址

3. 页表
   分页系统中，允许将进程的各个页离散地存储在内存的任一物理块中，为保证进程仍然能够正确运行，即能在内存中找到每个页面所对应的物理块，系统又为每个进程建立了一张页面映像表，简称页表

地址变换机构

地址变换机构的任务实际上只是将逻辑地址中的页号转换为内存中的物理块号

1. 基本的地址变换机构
   当进程要访问某个逻辑地址中的数据时，分页地址变换机构会自动地将有效地址(相对地址)分为页号和页内地址两部分，再以页号为索引去检索页表。在执行检索之前，先将页号与页表长度进行比较，如果页号大于或等于页表长度，则表示本次所访问的地址已超越进程的地址空间，若未出现错误，则将页表始址与页号和页表项长度的成绩相加，则得到该表项在页表中的位置
2. 具有快表的地址变换机构
   为了提高地址变换速度，可在地址变换机构中增设一个具有并行查寻能力的特殊高速缓冲寄存器，又称为”联想寄存器”，或称为”快表”
   在CPU给出有效地址后，由地址变换机构自动地将页号P送入高速缓冲寄存器，并将此页号与高速缓存中的所有页号进行比较，若其中有与此相匹配的页号，便表示所要访问的页表项在快表中

访问内存的有效时间

从进程发出指定逻辑地址的访问请求，经给地址变换，到在内存中找到对应的实际物理地址单元并取出数据，所需要花费的总时间，称为内存的有效访问时间(EAT)

两级和多级页表

32位系统中页表可能会很大，所以有两个方法解决问题:
(1)对于页表所需的内存空间，可采用离散分配方式，以解决难以找到一块连续的大内存空间的问题
(2)只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入

1. 两级页表
   将页表进行分页，使每个页面的大小与内存物理块的大小相同，并为它们进行编号，然后离散地将各个页面分别存放在不同的物理块中
   为离散分配的页表再建立一张页表，称为外层页表，在每个页表项中记录了页表页面的物理块号
2. 多级页表

反置页表

为每一个物理块设置一个页表项，并将它们按物理块的序号排序，其中的内容则是页号和其所隶属进程的标识符
在利用反置页表进行地址变换时，是根据进程标识符和页号，取检索反置页表。如果检索到与之匹配的页表项，则该页表项(中)的序号i便是该页所在的物理块号，可用该块号与页内地址一起构成物理地址送内存地址寄存器

分段存储管理方式

分段存储管理方式的引入

• 方便编程
• 信息共享
• 信息保护
• 动态增长
• 动态链接

  分段系统的基本原理

1. 分段
   在分段存储管理方式中，作业的地址空间被划分为若干段，每个段定义了一组逻辑信息，即每个段既包含了一部分地址空间，又标识了逻辑关系，其逻辑地址由段号和段内地址所组成
2. 段表
   在分段式存储管理系统中，为每个分段分配一个连续的分区，进程中的各个段，可以离散地装入内存中不同的分区中，然后建立一个段映射表，段表
3. 地址变换机构
   段表寄存器和联想寄存器
4. 分页和分段的区别

• 页是信息的物理单位
• 页的大小固定且由系统决定
• 分页的用户程序地址空间是一维的

段页式存储管理方式

1. 基本原理
   先将程序分成若干段，再把每个段分成若干页，并为每一个段赋予一个段名，系统中需要同时配置段表和页表，段表的内容与分段系统略有不同，是页表始址和页表长度
2. 地址变换过程
   首先利用段号S，将它与段长TL进行比较。若S < TL, 表示未越界，于是利用段表始址和段号来求出该段所对应的段表项在段表中的位置，从中得到该段的页表始址，并利用逻辑地址中的段内页号P来获得对应页的页表项位置，从中读出该页所在的物理块号b，再利用块号b和页内地址来构成物理地址

虚拟存储器

因为实际运行作业的时候可能会出现:

1. 有的作业很大
2. 有大量作业要求运行
   出现上述情况的原因都是内存容量不够大，所以从逻辑上扩充内存容量

   虚拟存储器概述

   常规存储管理方式的特征和局部性原理

3. 常规存储器管理方式的特征

• 一次性，是指作业必须一次性地全部装入内存后方能开始运行
• 驻留性，是指作业被装入内存后，整个作业都一直驻留再内存中，其中任何部分都不会被换出，直至作业运行结束

2. 局部性原理
   程序在执行时将呈现出局部性规律，即在一较短地时间内，程序的执行仅局限于某个部分，相应地，它访问的存储空间也局限于某个区域

   虚拟存储器地定义和特征

3. 定义
   虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充地一种存储器系统
4. 虚拟存储器的特征

• 多次性：指一个作业中的程序和数据无需在作业运行时一次性地全部装入内存，而是允许被分成多次调入内存运行
• 对换性：指一个作业中地数据和程序，无须在作业运行时一直常驻内存，而是允许在作业的运行过程中进行换进、换出
• 虚拟性：指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量

  虚拟存储器地实现方法

1. 分页请求系统
   是在分页系统的基础上增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统
   (1)硬件支持：请求分页的页表机制、缺页中断机制、地址变换机构
   (2)实现分页请求的软件：包括有用于实现请求调页的软件和实现页面置换的软件
2. 请求分段系统
   是在分段系统的基础上，增加了请求调段及分段置换后所形成的段式虚拟存储系统

   请求分页存储管理方式

   请求分页中的硬件支持

3. 请求页表机制
   每个页表应该包含页号、物理块号、状态位、访问字段A、修改位M、外存地址

• 状态位P:用于指示该页是否已经调入内存
• 访问字段A:用于记录本页在一段时间内被访问的次数
• 修改位M:标识该页在调入内存后是否被修改过
• 外存地址:用于指出该页在外存上的地址

2. 缺页中断机构
   每当要访问的页面不存在时，便产生一缺页中断，请求OS将所缺之页调入内存，有两个特点:
   (1)在指令执行期间产生和处理中断信号
   (2)一条指令在执行期间可能产生多次缺页中断
3. 地址变换机构
   

请求分页中的内存分配

1. 最小的物理块数的确定
   指能保证进程正常运行所需的最小物理块数，当系统为进程分配的物理块数少于此值时，进程将无法运行
2. 内存分配策略

• 固定分配局部置换:为每个进程分配一组固定数目的物理块，在进程运行期间不再改变，如果进程在运行中发现缺页，则只能从分配给该进程的n个页面中选出一页换出，如何再调入一页，然后再调入一夜，以保证分配给该进程的内存空间不变
• 可变分配全局置换:指先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当地增加或减少。如果在进程运行中发现缺页，则将OS所保留的空闲物理块取出一块分配给该进程，或者以所有进程的全部物理块中选出一块换出
• 可变分配局部置换:只允许在该进程的内存页面选择一页换出，若频繁缺页，则增加进程页面

3. 物理块分配算法

• 平均分配
• 按比例分配
• 优先权分配

  页面调入策略

1. 何时调入页面

• 预调页策略
• 请求调页策略

2. 从何处调入页面
   外存分为两部分:用于存放文件的文件区和用于存放对换页面的对换区
   对换区一般采用连续分配方式，文件区一般采用离散分配方式
   (1)系统拥有足够的对换区空间:
   这时可以全部从对换区调入所需页面
   (2)系统缺少足够的对换区空间:
   不会被修改的文件，直接从文件区调入，会被修改的，须先调到对换区
   (3)UNIX方式:
   未运行过的页面，都从文件区调入，对于曾经运行过但又被换出的页面，从对换区调入
3. 调入过程
   先找物理块位置，如果内存未满，调入；已满，置换。被置换的若被修改过，重写进磁盘
4. 缺页率
   访问失败次数/总访问次数

   页面置换算法

   置换算法

   访问内存的有效时间

   (1)被访问页在内存中，且其对应的页表项在快表中
   EAT = 查找快表的时间+访问实际物理地址的时间
   (2)被访问页在内存中，且其对应的页表项不在快表中
   EAT = 查找快表的时间+查找页表的时间+修改快表的时间+访问实际物理地址的时间
   (3)被访问页不在内存中
   EAT = 查找快表的时间+查找页表的时间+修改快表的时间+访问实际物理地址的时间+处理断页中断的时间+更新快表的时间+访问实际物理地址的时间

   “抖动”与工作集

   多道程序度和”抖动”

5. 多道程序度和处理机的利用率
   处理机的实际利用率随着进程数的增加而提高，但达到一定数目时开始下降
6. 抖动
   在系统中运行的进程太多，由此分配给每一个进程的物理块太少，不能满足进程正常运行的基本要求

   工作集

   工作集是指，在某段时间间隔里，进程实际所要访问页面的集合

   “抖动”的预防办法

7. 采用局部置换策略
8. 把工作集算法融入到处理机调度中
9. 利用”L=S”准则调节缺页率
   L是缺页之间的平均时间，S是平均缺页服务时间，即用于置换一个页面的时间

• L >> S，说明很少缺页，磁盘未充分利用
• L << S,说明频繁缺页
• L = S，完美

4. 选择暂停的进程

   请求分段存储管理方式

   

• 缺段中断机构
  一条指令不可能被分割在两个分段中
  
• 地址变换机构
  

  分段的共享与保护

1. 共享段表
   配置一张共享段表，所有各共享段表中占有一表项。在表项上面记录了共享段的段号、段长、内存始址、状态(存在)位、外存始址以及共享计数等信息

• 共享进程数:显示当前共享该分段的进程数
• 存取控制字段:赋予不同进程不同权限
• 段号:不同的进程有不同的段号

2. 共享段的分配与回收
   (1)共享段的分配
   对第一个请求使用该共享段的进程，系统为该共享段分配一物理区，再把共享段调入该区。同时将该区的始址填入请求进程的段表的相应项中，还须在共享段表中添加一表项，填写请求使用该共享段的进程名、段号和存取控制等有关数据，把count置为1，之后的count+1，再添加表项
   (2)共享段的回收
   撤销进程段表中共享段所对应的表项,count-1
3. 分段保护

• 越界检查
• 存取控制检测
• 环保护机构

  输入输出系统

  中断机构和中断处理程序

  中断简介

1. 中断和陷入

• 中断是指CPU对I/O设备发来的中断信号的一种响应，中断是由外部设备引起的，叫做外中断
• 陷入是CPU内部事件引发的中断，如运算溢出，程序出错，称为内中断

2. 中断向量表和中断优先级

• 中断向量表是为每种设备配以中断的不同类，处理的时候直接查表找处理程序
• 中断优先级，为每个中断规定不同的优先级

3. 多中断源的处理方式

• 屏蔽中断
  当处理机在处理一个中断时，将屏蔽其他所有中断
• 嵌套中断
  (1)当同时有多个不同优先级的中断请求时，CPU优先响应最高优先级的中断请求
  (2)高优先级的中断请求可以抢占正在运行的低优先级中断的处理机

  中断处理程序

• 测定是否有未响应的中断信号
• 保护被中断进程的CPU环境
• 转入相应的设备处理程序
• 中断处理
• 恢复CPU的现场并退出中断：
  是否会返回到被中断的进程取决于哪个阶段：
• 是否采用屏蔽中断方式，若采用则返回
• 采用的是中断嵌套方式，若没有更高优先级的中断，仍被返回被中断进程

  对I/O设备的控制方式

1. 采用轮询的可编程I/O方式
   设置busy标志，输入未完成时为1，完成时为0
2. 使用中断的可编程I/O方式
   CPU和I/O设备可以并行操作
3. 直接存储器访问方式