操作系统笔记
导论and引论
什么是操作系统
OS的基本模块
进程管理、内存管理、文件系统、IO系统四大块
这四个部分就能使操作系统运转起来
OS的目标
作用
3、OS实现了对计算机资源的抽象
操作系统定义
指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配，以提供给用户和其他软件方便的接口和环境。他是计算机系统中最基本的系统软件。
基本类型
三种操作系统基本类型批处理系统、分时系统、实时系统
分时系统：多个用户分时（按时间划分轮流）的使用同一计算机的系统称为为分时系统。
分时系统中，为使多个用户能够同时与系统交互，最关键的问题是 能在一短的时间内，使所有用户程序都能运行；
分时特点：
– 同时性或多路性：多用户同时操作、使用计算机
– 独占性：各终端用户感觉到自己独占了计算机；
– 及时性：用户的请求能在较短时间内相应；
– 交互性：用户能与计算机进行人——机对话。
响应时间为用户发出一条指令到系统处理完这条指令并做出回答所需要的时间
实时操作系统主要用于过程控制、事务处理等有实时要求的领域，其主要特征是 实时性和可靠性
在设计分时操作系统时，首先要考虑的是 交互性和响应时间 ；在设计实时操作系统时，首先要考虑的是 实时性和可靠性 ；在设计批处理系统时，首先要考虑的是 周转时间和系统吞吐量
目前的操作系统，通常具有分时、实时和批处理功能，又称作通用操作系统。
操作系统的基本特征
现代操作系统主要特征：
1 ）并发性
单处理机、多道程序 处理时，宏观上并发，微观上 交替执行。并发指的是进程，操作系统是一个并发系统。
2 ）共享性
多个进程共享有限的计算机系统资源，系统合理分配，资源在一个时间段内 交替被多个进程所用。
3 ）虚拟性
一个 物理实体映射为若干个 对应的逻辑实体（分时或分空间）。虚拟是操作系统 管理 系统资源的 重要手段，可提高资源利用率。
4 ）异步性
异步性也称不确定性，指进程的执行顺序和执行时间及执行 结果的不确定性：A程序执行结果不确定，不可再现 B多道程序设计环境下， 程序按异步方式运行。
第二章进程描述与控制
前驱图和程序的执行
程序的顺序执行及其特征
顺序执行：仅当当前操作（程序段）执行完，才能执行后续操作。
在单道批处理系统中，对于多个用户程序来说，所有程序是依次执行的。(外部顺序性)
对于一个程序来说，在若干个程序段之间，必须按照某种先后次序顺序执行；对同一个程序段中的多条指令，也是按某种顺序执行的。(内部顺序性)
程序的并发执行及其特征
进程
进程定义
经典进程定义
- 进程是程序一次定义
- 进程是一个程序及其数据在处理机上顺序执行时发生的活动
- 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位
传统os进程定义：
进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
进程的特征：
进程的特征：
1.结构特征 程序段+相关数据+PCB=进程实体
2.动态性 进程的实质是进程实体的一次执行过程。
3.并发性 多个进程实体同存于内存中，且能在一段时间内同时运行。
4.独立性 进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位。
5.异步性 是指进程按各自独立的、不可预知的速度向前推进
进程和线程的区别
进程与程序的区别
进程是程序的一次执行，该程序可以与其它程序并发执行。
) 进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。通常进程不可在计算机之间迁移；而程序通常对应着文件、静态和可以复制。
) 进程是暂时的，程序是永久的：进程是一个状态变化的过程，程序可长久保存
) 进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。
) 进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）
挂起操作
进程控制块 pcb
PCB进程控制块：进程存在的唯一标识，操作系统管理控制进程运行所用的信息集合，描述进程的基本情况和运行变化的过程。
用PCB的生成，回收，组织管理来完成进程的创建、终止和管理。
PCB含有三大类信息：
（1） 进程标识，哪个程序在执行，执行了几次（本进程的标识），产生者标识（父进程标识），用户标识
（2） 处理机状态信息保存区，主要就是寄存器，保存进程的运行现场信息：
- 用户可见寄存器，程序使用的数据，地址
- 控制和状态寄存器，程序计数器pc，程序状态字PSW
- 栈指针，过程调用/系统调用/中断处理和返回时需要用到
（3） 进程控制信息
- 调度和状态信息，用于操作系统调度进程并占用处理机使用。运行状态？等待？进程当前的执行现状
- 进程间通信信息，各种标识、信号、信件等
- 进程本身的存储管理信息，即指向本进程映像存储空间的数据结构，内存信息，占了多少？要不要回收？
- 进程所用资源，打开使用的系统资源，如文件
- 有关数据结构连接信息，父进程，子进程，构成一个链，进程可以连接到一个进程队列，或链接到其他进程的PCB
进程控制
)
进程同步
同步与互斥：
互斥：进程-资源-进程
同步：进程-进程
如何区分：只要是同类进程即为互斥关系，不同类进程即为同步关系。
临界资源和临界区：
临界资源：属于系统资源
临界区：属于进程，是进程访问临界资源的代码块。
同步应遵循的准则：
- 空闲让进
- 忙则等待
- 有限等待
- 让权等待（当一个进程不能进入自己的临界区时，则释放处理器给其他进程）
经典同步问题：
- 生产者-消费者问题：设置一个空缓冲区数目，一个满缓冲区数目，一个互斥信号量。
- 读者-写者问题
- 哲学家进餐问题：分成奇数号和偶数号，奇数号的哲学家先拿左边筷子，然后拿右边筷子；偶数号的哲学家则相反
- 理发师问题：把店内的所有椅子看做一个变量，只要有空椅子就留下，没有就离开。
进程通信
进程通信——进程之间的信息交换。
进程之间的互斥和同步，交换的信息量少——低级通信。
信号量机制作为通信工具不够理想，表现在：
效率低；
通信对用户不透明。
进程高级通信——是指用户可直接利用OS所提供的一组通信命令，高效地传送大量数据的一种通信方式。
高级通信过程对用户是透明;。
大大减少了通信程序编制的复杂性。
- 共享存储器系统 ：设置一个共享存储区
- 消息传递系统：直接通信方式、间接通信方式（设置一个中间实体-信箱）
- 管道通信系统：管道是用于连接读写进程以实现它们直接通信的共享文件，所以管道是共享文件。
进程和线程 比较
线程（thread）管理
线程的定义：进程内一个执行单元或一个可调度实体
资源拥有单元称为进程（或任务），调度的单位称为线程。在具有多线程的操作系统中，处理机调度的基本单位是线程。一个进程可以有多个线程，而且至少有一个可执行线程。
处理机调度与死锁
处理机调度的基本概念
作业进入系统驻留在外存的后备队列上，再至调入内存运行完毕，可能要经历下述三级调度。
- 高级调度（High Scheduling）
- 中级调度（Intermediate-Level Scheduling）
- 低级调度（Low Level Scheduling）
处理机调度的层次
高级调度
主要任务
高级调度又称为长程调度或者作业调度，它的调度对象是作业。主要功能是根据某种算法，决定将外存上处于后备队列中那几个作业调入内存，为它们创建进程，分配必要的资源，并将它们放入就绪队列。高级调度主要用于多道批处理系统，而在分时和实时系统中不设置高级调度。作用调度的频率很低，周期很长，大于几分钟一次。
两个决定
在每次执行作业调度时，都须作出两个决定：
- 接纳多少作业——取决于多道程序度。应根据系统的规模和运行速度等情况综合考虑。
- 接纳哪些作业——取决于采用的调度算法。如先来先服务，短作业优先等
系统运行并不一定存在高级调度
- 批处理系统：作业进入系统后先驻留外存，故需要有作业调度。
- 分时系统：为及时响应，作业由终端直接送入内存，故不需作业调度。
- 实时系统中，通常也不需作业调度。
低级调度
也称为进程调度、微观调度或短程调度（Short-Term Scheduling）
决定内存就绪队列中的哪个进程获得处理机，进行分配工作。是最基本的一种调度，在三种基本OS中都有。
进程调度方式
1）非抢占方式（Non-preemptive Mode）
一旦处理机分配给某进程，该进程一直执行。决不允许其他进程抢占已分配运行进程的处理机。
2）抢占方式（Preemptive Mode）
允许调度程序根据某种原则，暂停某个正在执行的进程，将处理机重新分配给另一进程。
中级调度（Intermediate-Level Scheduling）
又称交换调度或中程调度（Medium-Term Scheduling）
引入目的：提高内存利用率和系统吞吐量。根据条件将一些进程调出或再调入内存
三种调度的频率和复杂度
- 进程调度：运行频率最高，算法不能太复杂，以免占用太多的CPU时间。分时系统通常10~100ms便进行一次。
- 作业调度：一个作业运行完毕退出系统时即触发重新调度一个新作业入内存，周期较长，大约几分钟一次。因而也允许作业调度算法花费较多的时间。
- 中级调度：运行频率基本上介于上述两种调度之间。
三级调度比较
进程调度（低级调度）的运行频率最高
作业调度（高级调度）频率最低
中级调度（内存调度）界于之间
调度队列模型
不论高级、中级或者低级调度，都涉及到进程队列，由此形成了三类调度队列模型。从这三种方式中体验调度的过程。
- 仅有进程调度的调度队列模型
- 具有高级和低级调度的调度队列模型
- 同时具有三级调度的调度队列模型
选择调度方式和调度算法的若干准则
- 面向用户的准则
周转时间短：
针对批处理系统的性能指标。作业从提交到完成所经历的时间。
CPU执行用时Ts
总的等待时间Tw = 在后备队列中等待 + 就绪队列上等待 + 阻塞队列中等待（等待I/O操作用时）
周转时间T=Ts+Tw
带权周转时间W= T/Ts
平均周转时间
平均带权周转时间
- 响应时间快：针对分时系统。用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间
- 均衡性：系统响应时间的快慢与用户所请求的复杂性相适应。
- 截止时间的保证：针对实时系统的性能指标。开始截止时间和完成截止时间。任务必须按规定的时间开始或完成，调度方式和算法必须能保证该要求。
- 优先权准则：三大基本OS在调度算法的选择时都可遵循。可以使关键任务达到更好的指标。
- 面向系统的准则
- 系统吞吐量高：批处理系统的重要指标。
单位时间内所完成的作业数，跟作业本身（与作业平均长度密切相关）和调度算法都有关系；
- 处理机利用率好(主要针对大中型主机)
- 各类资源的平衡利用(主要针对大中型主机)
调度算法
FCFS 算法 是一种先来先服务的的算法，根据先后顺序依次执行，它是一种非抢占式的调度算法，相对来说比较公平。
同时适用于高级和低级调度
优点：实现简单
缺点：没考虑优先级
SJF 算法
即短作业优先算法，可用于进程调度，称为短进程优先算法，SPF，也是非抢占式算法，但是他们也有抢占式的版本：最短剩余时间算法 SRTN。
同时适用于高级和低级调度
优点：系统吞吐量
缺点：不利于作业
高响应比优先调度算法
这是一个非抢占式的算法，只有当前运行的作业主动放弃处理机时才需要调度，才需要计算响应比。
一般来说，进程优先级的设置使用以下规则：
- 系统进程 优先于 用户进程；
- 交互型进程 优先于 非交互型进程；
IO 型进程优先于 计算型进程；
高优先权优先调度算法
1) 非抢占式优先权算法
2) 抢占式优先权调度算法
轮转调度算法
多级反馈队列调度算法
多个就绪队列
每个队列都采用FCFS算法
按照队列优先级调度
死锁
死锁：产生原因是几个进程因竞争系统资源或相互通信而处于永久阻塞状态。
根本原因：竞争资源 重要原因：进程推进顺序不当
处理死锁的四种方法：
- 鸵鸟算法：对死锁视而不见
- 预防死锁：设置限制条件，破坏产生死锁的4个必要条件之一或几个
- 避免死锁：资源动态分配过程中，用某种方法防止系统进入不安全状态，比如不给某个进程分配资源。
- 检测和解除死锁：采取措施解除死锁，比如剥夺某个进程的资源。
饿死：因为等待时间过长而饿死，比如在优先级分配算法中，不断的有高优先级的进程产生，则低优先级的进程总是分配不到处理器，则会饿死。 饿死是有机会分配到处理器，只是时间比较长，而死锁是相互缺乏资源不能分配处理器。
存储器管理
存储器的层次结构
多层结构的存储器系统
- 存储器的多层结构。
存储层次至少应具有三级：最高层为 CPU 寄存器，中间为主存，最底层是辅存。还可以根据具体的功能分工细划为寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等 6 层。在存储层次中越往上，存储介质的访问速度越快，价格也越高，相对存储容量也越小。
寄存器、高速缓存、主存储器和磁盘缓存均属于操作系统存储管理的管辖范畴，掉电后它们存储的信息不再存在。固定磁盘和可移动存储介质属于设备管理的管辖范畴，它们存储的信息将被长期保存。 - 可执行存储器。
寄存器和主存储器又被称为可执行存储器。
主存储器与寄存器
- 主存储器。
主存储器简称内存或主存。由于主存储器的访问速度远低于 CPU 执行指令的速度，为缓和这一矛盾，在计算机系统中引入了寄存器和高速缓存。 - 寄存器。
寄存器具有与处理机相同的速度。主要用于存放处理机运行时的数据。如用寄存器存放操作数，或用作地址寄存器加快地址转换速度等。
高速缓存和磁盘缓存
- 高速缓存。
高速缓存是介于寄存器和存储器之间的存储器，主要用于备份主存中较常用的数据。其容量远大于寄存器，而比内存约小两到三个数量级左右。
根据程序执行的局部性原理(即程序在执行时将呈现出局部性规律，在一较短的时间内，程序的执行仅局限于某个部分)，将主存中一些经常访问的信息存放在高速缓存中。当 CPU 访问一组特定信息时，首先检查它是否在高速缓存中，在则直接取出使用，否则再从主存中读取。 - 磁盘缓存。
由于目前磁盘的 I/O 速度远低于对主存的访问速度，因此将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数。但磁盘缓存与高速缓存不同，它本身并不是一种实际存在的存储介质，而是利用主存中的部分存储空间暂存从磁盘中读出(或写入)的信息。
程序的装入和链接
用户程序要在系统中运行，必须先将它装入内存，然后再将其转变为一个可以执行的程序，通常都要经过以下几个步骤：
1）编译，由编译程序将用户源代码编译成若干个目标模块。
2）链接，由链接程序将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成一个完整的装入模块。
3）装入，由装入程序将装入模块装入内存。
程序的装入
- 绝对装入方式。
仅能运行单道程序时可以采用该种方式。装入模块被装入内存后，程序中的逻辑地址与实际内存地址完全相同。 - 可重定位装入方式。
采用可重定位装入方式，根据内存的当前情况，将装入模块装入到内存的适当位置。值得注意的是，在采用可重定位装入程序将装入模块装入内存后，会使装入模块中的所有逻辑地址与实际装入内存的物理地址不同。通常是把在装入时对目标程序中指令和数据地址的修改过程称为重定位。又因为地址变换通常是在装入时一次完成的，以后不再改变，故称为静态重定位。 - 动态运行时装入方式。
动态运行时的装入程序在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相对地址。为使地址转换不影响指令的执行速度，这种方式需要一个重定位寄存器的支持。
内存分区和分页
连续分配存储管理方式
为了能将用户程序装入内存，必须为它分配一定大小的内存空间。
单一连续分配
只能用于单道程序环境下，整个内存的用户空间由一个程序独占。
固定分区分配
将内存用户空间划分为若干个固定大小的区域，在每个分区中只装入一道作业。
- 划分分区的方法。
分区大小相等、分区大小不等。 - 内存分配。
通常将分区按大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态(是否已分配)。当有一用户程序要装入时，由内存分配程序检索该表，从中找出一个能满足要求的、尚未分配的分区，将之分配给该程序，然后将该表项中的状态置为“已分配”。
动态分区分配
又称可变分区分配。
- 动态分区分配中的数据结构。
常用的数据结构有以下两种形式：
空闲分区表，表目：分区号、分区大小、分区始址、状态。
空闲分区链，在每个分区的起始部分设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针；在分区尾部则设置一后向指针，以及前后都重复设置状态位和分区大小表目。通过前、后向链接指针，可将所有的空闲分区链接成一个双向链。 - 动态分区分配算法。
顺序式搜索算法、索引式搜索算法。 - 分区分配操作。
1）分配内存：
系统应利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。设请求的分区大小为 u.size，表中每个空闲分区的大小可表示为 m.size。若 m.size-u.size≤size(size 是事先规定的不再切割的剩余分区的大小)，说明多余部分太小，可不再切割，将整个分区分配给请求者；否则(即多余部分超过 size)，从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区链(表)中。然后，将分配区的首址返回给调用者。
2）回收内存：
当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点，此时可能出现以下四种情况之一：
①回收区与插入点的前一个空闲分区相邻接，此时应将回收区与插入点的前一分区合并。
②回收分区与插入点的后一空闲分区相邻接，此时也可将两分区合并。
③回收区同时与插入点的前、后两个分区邻接，此时将三个分区合并。
④回收区既不与前一个邻接，又不与后一个邻接，这时应为回收区单独建立一新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。
基于顺序搜索的动态分区分配算法
顺序搜索，是指依次搜索空闲分区链上的空闲分区，去寻找一个其大小能满足要求的分区。
碎片：内存空间不断被划分，会留下许多难以利用的、很小的空闲分区。
- 首次适应算法。
要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止，缺点是低址部分会不断被划分，形成碎片。 - 循环首次适应算法。
在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找。实现可通过设置一起始查寻指针，用于指示下一次起始查寻的空闲分区，并采用循环查找方式。缺点缺乏大的空闲分区。 - 最佳适应算法。
总是把能满足要求、又是最小的空闲分区分配给作业，为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。缺点产生许多碎片。 - 最坏适应算法。
在扫描整个空闲分区表或链表时，总是挑选一个最大的空闲区，分割一部分空间给作业使用。要求将所有的空闲分区按其容量以从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求即可。缺点缺乏大的空闲分区。
基于索引搜索的动态分区分配算法
- 快速适应算法。
又称为分类搜索法。是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。
该算法仅需要根据进程的长度，寻找到能容纳它的最小空闲区链表，并取下第一块进行分配即可。在分配过程中，不会对任何分区产生分割。 - 伙伴系统。
规定，无论已分配分区或空闲分区，其大小均为 2 的 k 次幂（k 为整数，l≤k≤m）。通常 2^m是整个可分配内存的大小。
对于每一类具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。
当需要为进程分配一个长度为 n 的存储空间时，首先计算一个 i 值，使 2^(i-1) < n ≤ 2^i，然后在空闲分区大小为 2^i 的空闲分区链表中查找。若找到则直接分配。否则，则在分区大小为 2^(i+1) 的空闲分区链表中寻找。若存在 2^(i+1) 的一个空闲分区，则把该空闲分区分为相等的两个分区，这两个分区称为一对伙伴，其中的一个分区用于分配，而把另一个加入分区大小为 2^i 的空闲分区链表中。若仍然找不到，依次类推去寻找更高1次幂的分区。
与一次分配可能要进行多次分割一样，一次回收也可能要进行多次合并，如回收大小为 2^i的空闲分区时，若事先已存在回收块所对应的2^i伙伴块的空闲分区时，则应将其与伙伴分区合并为大小为2^(i+1)的空闲分区，若事先已存在新合并空闲块对应的2^(i+1)伙伴块的空闲分区时，依次类推合并。
对于一个大小为2^k，地址为x的内存块，其伙伴块的地址则用buddy k (x)表示，其通式为：if(x MOD 2^(k+1) == 0) {buddy k (x) = x + 2^k;}else if(x MOD 2^(k+1) == 2^k) {buddy k (x) = x - 2^k;} - 哈希算法。
构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表表头指针。
动态可重定位分区分配
- 紧凑。
在连续分配方式中，必须把一个系统或用户程序装入一连续的内存空间。当一台计算机运行了一段时间后，它的内存空间将会被分割成许多小的分区，而缺乏大的空闲分区。
通过移动内存中作业的位置，以把原来多个分散的小分区拼接成一个大分区的方法，称为“拼接”或“紧凑”。由于经过紧凑后的某些用户程序在内存中的位置发生了变化。为此，在每次“紧凑”后，都必须对移动了的程序或数据进行重定位。 - 动态重定位。
在动态运行时装入的方式中，作业装入内存后的所有地址都仍然是相对(逻辑)地址，将相对地址转换为物理地址的工作，被推迟到程序指令要真正执行时进行。
地址变换过程是在程序执行期间，随着对每条指令或数据的访问借助重定位寄存器自动进行的，故称为动态重定位。当系统对内存进行了“紧凑”而使若干程序从内存的某处移至另一处时，不需对程序做任何修改，只要用该程序在内存的新起始地址，去置换原来的起始地址即可。 - 动态重定位分区分配算法。
动态重定位分区分配算法与动态分区分配算法基本上相同，差别仅在于：在这种分配算法中，增加了紧凑的功能。
分页存储管理方式
基于允许将一个进程直接分散地装入到许多不相邻接的分区中，则无须再进行“紧凑” 的思想而产生了离散分配方式。分为以下三种：
1）分页存储管理方式：将用户程序的地址空间分为若干个固定大小的区域，称为“页”或者“页面”。也将内存空间分为若干个物理块或页框，页和框的大小相同。
2）分段存储管理方式：把用户程序的地址空间分为若干个大小不同的段。分配以段为单位。
3）段页式存储管理方式：是分页和分段两种存储方式相结合的产物。
两级和多级页表
如果进程有1M个页表项，则该进程页表（含1M个页表项，每个页表项占1个字节）就要占用1MB的连续内存空间。解决办法：①+②
①采用离散分配方式——>增加外层页表及外层页表寄存器，实现两级和多级页表；
②将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入；
段页式存储管理方式
引入原因：
分页和分段管理方式各有其优缺点，分页系统能有效提高内存的利
用率，而分段则能更好地满足用户的需要，因此可以将两者结合成一种新
的存储管理方式系统称为“段页式系统”。
基本原理
结合分段和分贝思想，先将用户程序分成若干段并分别赋予段名，再将这些段分为若干页
地址结构:由段号、段内页号和页内地址三项共同构成地址
| 段号(S) | 段内页号（P) | 页内地址(W) |
|---|---|---|
虚拟存储器
所谓“虚拟存储器”，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。
虚拟的实现建立在离散分配存储管理基础上
方式：请求分页/请求分段系统
细节：分页/段机构、中断机构、地址变换机构、软件支持
虚拟存储器的特征:
1.多次性：一个作业被分成多次调入内存运行
2.对换性：允许在作业的运行过程中进行换进、换出。（进程整体对换不算虚拟）
3.最终体现虚拟性：能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。
请求分页存储管理方式
由基本分页 + “请求调页”和“页面置换”功能组成。换入和换出基本单位都是长度固定的页面.
- 页表基本功能不变：逻辑地址映射为物理地址,增加虚拟功能后需记录的页表项信息有变化：
页号+物理块号/外存地址(存储何种地址取决于P)+状态位P+访问字段A+修改位M
状态位P ：指示该页是否已调入内存。
访问字段A ：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问。(置换时考量的参数)
修改位M ：该页在调入内存后是否被修改过。(关系到置换时调出的具体操作)
外存地址：用于指出该页在外存上的地址。 - 缺页中断机构:
每当要访问的页面不在内存时，便产生一缺页中断通知OS，OS则将所缺之页调入内存。作为中断，需经历几个步骤：
–“保护CPU环境”
–“分析中断原因”
–“转入缺页中断处理程序”
–“恢复CPU环境”等。
作为一种特殊中断，与一般中断有明显区别：
(1) 在指令执行期间产生和处理中断信号。
(2) 一条指令在执行期间，可能产生多次缺页中断。 - 地址变换机构:
分页系统地址变换机构的基础上增加分页系统地址变换机构的基础上增加
产生和处理缺页中断（请求调入）
从内存中换出一页的功能（置换）
内存分配
最小物理块数的确定
取决于指令的格式、功能和寻址方式
内存分配策略 （固定和可变，全局和局部）
固定分配局部置换
可变分配全局置换
最易于实现的物理块分配和置换策略，已用于若干OS中
可变分配局部置换
物理块分配算法
平均分配算法——显然不太合理
按比例分配算法
考虑优先权的分配算法
一部分按比例；另一部分根据各进程的优先权——合理
页面调入策略
- 请求调页策略：一个页面只有在被用到时才被调入到内存中，否则就放在外存中。这种调页方式容易产生较多的缺页中断，时间开销大，容易产生抖动现象。
- 预调页策略：是指将预计不久之后会被用到的页面一并调入到内存，尽管暂时它们还没被用到。这是一种基于局部性原理的预测，通常用于程序的首次调入。
从何处调入页面
- 系统拥有足够的对换区空间：这时可以全部从对换区调入所需页面，以提高调页速度。
- 系统缺少足够的对换区空间：这时凡是不会被修改的文件，都直接从文件区调入；而当置换出这些页面时，由于它们未被修改而不必再将它们换出，以后再调入时，仍从文件区直接调入。但对于那些可能被修改的部分，在将它们换出时，便需调到对换区，以后需要时再从对换区调入。
- 方式：由于与进程有关的文件都放在文件区，因此凡是未运行过的页面都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应从对换区调入。
页面置换算法详解
页面置换算法的功能：当出现缺页异常，需调入新页面而内存已满时，置换算法选择被置换的物理页面。
页面置换算法的设计目标：尽可能减少页面的调入调出次数，把未来不再访问或短期内不访问的页面调出。
先进先出算法（First-In First-Out, FIFO）
思路：选择在内存驻留时间最长的页面进行置换
实现：维护一个记录所有位于内存中的逻辑页面链表，链表元素按驻留内存的时间排序，链首最长，链尾最短，出现缺页时，选择链首页面进行置换，新页面加到链尾
特点：实现简单；性能较差，调出的页面可能是经常访问的
最近最久未使用算法 (Least Recently Used, LRU)
思路：选择最长时间没有被引用的页面进行置换，因为如果某些页面长时间未被访问，则它们在将来还可能会长时间不会访问
实现：缺页时，计算内存中每个逻辑页面的上一次访问时间，选择上一次使用到当前时间最长的页面
特点：可能达到最优的效果，维护这样的访问链表开销比较大
\最不常用算法（Least Frequently Used, LFU）**
思路：缺页时，置换访问次数最少的页面
实现：每个页面设置一个访问计数，访问页面时，访问计数加1，缺页时，置换计数最小的页面
特点：算法开销大，开始时频繁使用，但以后不使用的页面很难置换
时钟置换算法（Clock）
思路：仅对页面的访问情况进行大致统计
实现：在页表项中增加访问位，描述页面在过去一段时间的内访问情况，将各页面组织成环形链表，指针指向最先调入的页面，访问页面时，在页表项记录页面访问情况，缺页时，从指针处开始顺序查找未被访问的页面进行置换
特点：时钟算法是LRU和FIFO的折中
影响缺页率的因素 缺页率=缺页次数/页面访问总页数
1、进程所分配的物理块数目 2、页面尺寸
3、页面替换算法 4、程序固有特性
输入输出系统
除了提供抽象(例如，进程（和线程）、地址空间和文件）以外，操作系统还要控制计算机的所有I/O（输入/输出）设备。
设备分类（按照信息交换基本单位分类）
块设备：
块设备把信息存储在固定大小的块中，每个块有自己的地址。通常块的大小在512字节至32 768字节之间。所有传输以一个或多个完整的（连续的）块为单位。块设备的基本特征是每个块都能独立于其他块而读写（可寻址）。硬盘、CD-ROM和USB盘是最常见的块设备。
字符设备：
字符设备以字符为单位发送或接收一个字符流，而不考虑任何块结构。字符设备是不可寻址的，也没有任何寻道操作。打印机、网络接口、鼠标（用作指点设备）、老鼠（用作心理学实验室实验），以及大多数与磁盘不同的设备都可看作是字符设备。在输入/输出的时候一般采用中断驱动的方式。
设备控制器
I/O设备一般由机械部件和电子部件两部分组成。通常可以将这两部分分开处理，以提供更加模块化和更加通用的设计。电子部件称作设备控制器（device controller）或适配器（adapter）。设备控制器用于控制机械部件工作。
设备控制器的功能
- 接受和识别CPU发出的命令（控制寄存器中存放CPU命令的参数）
- 向CPU报告设备的状态（设置状态寄存器）
- 数据交换（数据寄存器）
- 地址识别（有两种编址方式：内存映射I/O、单独分配）
控制器与设备之间的接口通常是一个很低层次的接口。例如，磁盘可以按每个磁道10 000个扇区，每个扇区512字节进行格式化。
控制器的任务是把串行的位流转换为字节块，并进行必要的错误校正工作。字节块通常首先在控制器内部的一个缓冲区中按位进行组装，然后在对校验和进行校验并证明字节块没有错误后，再将它复制到主存中。
磁盘存储器的性能和调度
如何在磁盘中读/写数据？
磁盘的物理地址
一次磁盘读/写操作需要的时间
磁盘调度算法
1、先来先服务FCFS
2、最短寻找时间优先SSTF
3、扫描算法SCAN
4、循环扫描算法C-SCAN
文件管理
文件管理，由于系统的内存有限并且不能长期保存，故平时总是把它们以文件的形式存放在外存中，需要时再将它们调入内存。如何高效的对文件进行管理是操作系统实现的目标。
现代OS几乎都是通过文件系统来组织和管理在计算机中所存储的大量程序和数据的。文件系统的管理功能是通过把它所管理的程序和数据组织成一系列文件的方法来实现的。而文件则是指具有文件名的若干相关元素的集合。元素通常是记录，而记录是一组有意义的数据项的集合。可以把数据组成分为数据项、记录、文件。
①数据项，数据项是最低级数据组织形式。分为基本数据项（用于描述一个对象某种属性的字符集，是数据组织中可以明明的最小逻辑数据单位，即原子数据，又称为数据元素或字段）和组合数据项（由若干个基本数据项组成）
② 记录，是一组相关数据项的集合，用于描述一个对象在某方面的属性，为了能够唯一标识一个记录，需要在一个记录的各个数据项中确定一个或几个数据项，把他们的集合称为关键字，关键字是能够唯一标识一个记录的数据项。
③ 文件，文件是具有文件名的一组相关元素的集合，分为有结构文件（又称记录式文件：文件由一组相似记录组成 。如报考某学校的所有考生的报考信息记录）和无结构文件（又称流式文件：被看成是一个字符流。比如一个二进制文件或字符文件）。有结构文件由若干个相关记录组成，无结构文件则被看成一个字符流。文件是文件系统的最大数据单位。文件应该具有自己的属性，包括文件类型（如源文件、目标文件、可执行文件等），文件长度（文件的当前长度，也可能是最大允许长度），文件的物理位置（指示文件在哪一个设备上及在该设备的哪个位置的指针），文件的建立时间（文件最后一次修改时间）。
文件的属性
①名称：文件名称唯一，以容易读取的形式保存。
②标识符：标识文件系统内文件的唯一标签,通常为数字，它是对人不可读的一种内部名称。
③类型：被支持不同类型的文件系统所使用。
④位置：指向设备和设备上文件的指针。
⑤大小：文件当前大小（用字节、字或块表示），也可包含文件允许的最大值。
⑥保护：对文件进行保护的访问控制信息。
⑦时间、日期和用户标识：文件创建、上次修改和上次访问的相关信息，用于保护、 安全和跟踪文件的使用
文件类型
①按用途分类：系统文件、用户文件、库文件。
②按文件中数据的形式分类：源文件、目标文件、可执行文件。
③按存取控制属性分类：只执行文件、只读文件、读写文件。
④按组织形式和处理方式分类：普通文件、目录文件、特殊文件。
文件操作
（1）基本文件操作：创建文件、删除文件、读文件、写文件、设置文件的读/写位置（可以改顺序存取为随机存取）
（2）文件的“打开”“关闭”操作：
①打开：系统将指名文件的属性从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号（索引号）返回给用户。即在用户和指定文件之间建立一个连接。
②关闭：断开用户与指定文件之间的连接。
（3）其他文件操作：允许用户直接设置和获得文件的属性、进行有关目录的操作等。
文件结构
分为：逻辑结构、物理结构。
（1）文件的逻辑结构：即文件组织，从用户观点出发所观察到的文件组织形式。
（2）文件的物理结构：即文件的存储结构，指系统将文件存储在外存上所形成的一种存储组织形式，用户不可见。
文件逻辑结构
分类：文件是否有结构、文件的组织方式。
（1）是否有结构：有结构文件、无结构文件。
①有结构文件：定长记录（相同的顺序和长度）、变长记录（长度不同：数据项数目不同、数据项本身长度不定）。
②无结构文件：即流式文件，文件的长度以字节为单位，一个记录仅有一个字节。举例：源程序、可执行文件、库函数等采用流式文件。
（2）文件的组织方式：顺序、索引、索引顺序。
①顺序文件：由一系列记录按某种顺序排列所形成的的文件，可定长记录可变长记录。
②索引文件：为可变长记录文件建立一张索引表，为每个记录设置一个表项，加速对记录的检索速度。
③索引顺序文件：顺序文件与索引文件相结合，为一组记录中的第一个建立索引表项。
顺序文件
：顺序文件按排列方式分串结构（按存入时间先后排序）和顺序结构（按关键字排序）。顺序文件的优点是适用于记录的批量存取，所有逻辑文件中顺序文件存取效率最高；缺点是增删记录困难以及应用交互时性能差。顺序文件查找记录地址的方式有：隐式寻址方式和显式寻址方式，后者可实现对定长记录文件的直接或随机访问，却不适用于定长记录。
索引文件
：按关键字建立索引，把对变长记录顺序文件的顺序检索转变为对定长记录索引文件的随机检索。
索引顺序文件特征
：克服了变长记录的顺序文件不能随机访问及记录不便删插的缺点；记录是按关键字的顺序组织的；引入文件索引表实现对索引顺序文件的随机访问；增加了溢出文件来记录新的增删改记录。
接口
系统调用基本概念
在OS的核心中，都设置了一组用于实现各种系统功能的子程序（过程或函数），并将它们提供给用户应用程序调用。
系统调用本质上是应用程序请求OS内核完成某项功能时的一种过程调用。
系统调用与一般的过程调用的区别：
运行在不同的系统状态
通过软中断进入
返回问题——返回时，CPU可能被别的进程抢占。
嵌套调用——在一个系统调用执行期间，可以利用系统调用命令去调用另一个系统调用。
系统调用的类型
1．进程控制类系统调用
创建和终止进程的系统调用
获得和设置进程属性的系统调用
等待某事件出现的系统调用
2．文件操纵类系统调用
创建和删除文件
打开和关闭文件
读和写文件
3．进程通信类系统调用
- 设备管理类系统调用
- 信息维护类系统调用
