408之操作系统概念记忆总结

• 1、绪论
• • 1.1、操作系统特征
  • 1.2、操作系统的发展和分类
  • 1.3、操作系统的运行机制
  • 1.4、中断和异常
  • 1.5、系统调用
  • 1.6、OS体系结构
• 2、进程管理
• • 2.1、进程五状态模型
  • 2.2、进程通信
  • 2.3、多线程模型
  • • 2.3.1、线程实现方式
  • 2.4、进程调度
  • 2.5、进程调度的时机
  • 2.6、性能指标
  • 2.7、调度算法
  • 2.8、死锁
  • 2.10、同步与互斥
  • 2.11、信号量
• 3、内存管理
• • 3.1、内存的分配与回收
  • 3.2、基本分页存储管理
  • • 3.2.1、页表
    • 3.2.2、两级页表
  • 3.3、基本分段存储管理
  • 3.4、分段和分页
  • 3.5、虚拟内存
  • 3.6、页面置换算法
  • 3.7、页面分配策略
• 4、文件管理
• • 4.1、文件保护
  • 4.2、文件共享
  • 4.3、文件分配
  • 4.4、文件存储空间管理
  • 4.5、文件的基本操作
• 5、I/O管理
• • 5.0、I/O控制方式
  • 5.1、中断处理程序
  • 5.2、I/O软件层次结构
  • 5.3、I/O核心子系统
  • 5.4、假脱机技术
  • 5.5、设备分配
  • 5.6、缓冲区管理
  • 5.7、磁盘
  • 5.8、磁盘读/写操作时间
  • 5.9、磁盘调度算法
  • 5.10、固态硬盘

1、绪论

• 联机命令接口的特点：用户说一句，系统跟着做一句 （例如：cmd）
• 脱机命令接口的特点：用户说一堆，系统跟着做一堆 (例如：.bat文件)

1.1、操作系统特征

• 并发：宏观上是同时发生的，但微观上是交替发生的。
• 并行：两个或多个事件在同一时刻同时发生。
  • 单核CPU同一时刻只能执行一个程序，多个程序只能并发地执行。
  • 多核CPU同一时刻可以同时执行多个程序，多个程序可以并行地执行。
• 两种资源共享方式：
  • 互斥共享方式：系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源(对摄像头设备的共享使用)
  • 同时共享方式：系统中的某些资源，允许一个时间段内由多个进程"同时"对它们进行访问。（对硬盘资源的共享使用）
• 虚拟技术分为：
  • 空分复用技术(如虚拟存储器技术) （电脑4GB的运行内存运行GTA+QQ+LOL+CF哈哈哈）
  • 时分复用技术(如虚拟处理器) (实际只有一个单核CPU，在用户看来似乎有好多CPU同时服务)

1. 并发和共享是操作系统的两个最基本的特征。
2. 进程和进程只能并发，不能并行。并发是指两个或多个事件在同一时间间隔内发生，并行是指两个或多个事件在同一时刻发生。进程是资源分配的基本单位，线程是调度的基本单位。同一进程中的各个线程拥有相同的地址空间
3. 操作系统给应用程序提供的接口是系统调用，系统调用 = 程序接口 = 广义指令，系统调用发生在用户态，执行在内核态。注意：并不是所有的库函数都会使用系统调用，有的库函数涉及系统调用，有的不涉及
4. 操作系统中，用户界面指的是命令接口、程序接口和操作环境
5. 操作系统主要向用户提供命令接口、程序接口(系统调用)、图形接口

6. 用户程序请求操作系统服务是通过**访管指令(trap指令、陷入指令)**来实现的。执行系统调用的过程如下?：

   1. 首先需要传递系统调用的参数

   2. 执行陷入(trap)指令，使系统进入内核态

   3. 在内核态下执行相应的服务程序

   4. 返回用户态

      注意：陷入(trap)指令是非特权指令，运行在用户态。返回指令是特权指令，运行在内核态

7. 操作系统是一种系统软件，系统软件包括操作系统、数据库管理系统等。操作系统的程序并不都是在内核态运行，操作系统的所有用户程序都是在用户态执行的。

8. DOS是一个单任务单用户的操作系统，就是没有界面的操作系统

9. 计算机开机后，操作系统最终被加载到RAM(SDRAM-主存里面)，BIOS(也叫固件)也是主存的一部分，BIOS是ROM

1.2、操作系统的发展和分类

• 手工操作阶段
  • 缺点：人机速度矛盾
• 批处理阶段
  • 单道批处理系统(只能装一道程序，引入脱机输入输出技术)
    • 优点：缓解人机速度矛盾
    • 缺点：资源利用率依然很低
  • 多道批处理系统(操作系统开始出现)
    • 优点：多道程序并发执行，资源利用率高，系统吞吐量大
    • 缺点：不提供人机交互功能，平均周转时间长
  • 分时操作系统
    • 优点：提供人机交互功能
    • 缺点：不能优先处理紧急任务
  • 实时操作系统
    • 硬实时系统：必须在绝对严格的规定时间内完成处理
    • 软实时系统：能接受偶尔违反时间规定
    • 优点：能优先处理紧急任务

1. 批处理系统都不具备交互性，无论是单道批处理系统还是多道批处理系统，并且用户不能控制作业的运行，一旦出错，作业重新提交，平均周转时间过长，所以引入分时操作系统，引入分时操作系统的主要目的是提高计算机系统的交互性。
2. 单道批处理系统的特点：
3. 多道批处理系统的特点：
4. 分时操作系统的时间片太小，CPU需要频繁切换进程，导致系统性能下降，若时间片太大，
5. 实时操作系统能及时响应外部发生的事件，对事件作出快速处理，并可在限定的时间内对外部的请求和信号作出响应

1.3、操作系统的运行机制

内核程序的指令我们称为特权指令，应用程序的指令我们称为非特权指令

CPU有两种状态：内核态和用户态

• 当CPU处于内核态时，说明此时正在运行的是内核程序，此时可以执行特权指令
• 当CPU处于用户态时，说明此时正在运行的是应用程序，此时只能执行非特权指令

如何区分CPU此时处于哪种状态呢？

• 在CPU中有一个寄存器叫 程序状态字寄存器(PSW)，其中有个二进制位，1表示内核态，0表示用户态。
• 别名： 内核态=核心态=管态，用户态=目态

如何实现内核态和用户态的切换呢？

• 内核态 -> 用户态：执行一条特权指令–修改PSW的标志位为"用户态"，这个动作意味着操作系统将主动让出CPU使用权
• 用户态 -> 内核态：由"中断"引发，硬件自动完成变态过程，触发中断信号意味着操作系统将强行夺回CPU的使用权。

1. 非特权指令是在用户态执行，如：trap指令、跳转指令、压栈指令

2. 特权指令是内核态使用的执行，如：I/O指令、设置中断屏蔽指令、清内存指令、存储保护指令、设置时钟指令

   • 只要是管理类指令都要在内核态执行，例如设备管理类指令：I/O输入输出指令
   • CPU处于内核态时，它可以执行的指令是：除访管指令的其他全部指令。因为访管指令是用来从用户态转换为内核态。

读时钟可以在用户态读，置(写)时钟要在内核态置(写)

1.4、中断和异常

• 中断
  • 内中断(也称异常、例外)：与当前执行的指令有关，中断信号来源于CPU的内部
    1. 试图在用户态下执行特权指令
    2. 执行除法指令时发现除数为0
    3. 执行陷入(trap)指令(**非特权指令)**请求操作系统内核的服务
  • 外中断(也称中断)：与当前执行的指令无关，中断信号来源于CPU外部。
    1. 时钟中断
    2. I/O中断
• 中断机制的基本实现原理：
  • 检查中断信号
    • 内中断：CPU在执行指令时会检查是否有异常发生
    • 外中断：每个指令周期末尾，CPU都会检查是否有外中断信号需要处理
  • 通过"中断向量表"找到相应的中断处理程序，中断处理程序一定是内核程序需要运行在内核态

1. 引入多道程序技术的前提条件是系统具有中断技术。
2. 常见的异常(内中断)有：非法操作码、地址越界、算数溢出、虚拟存储系统的缺页、陷入(trap)指令
   • 注意：异常无法被屏蔽，一旦出现异常必须立刻处理，所以异常的响应发生在指令执行过程中
3. 常见的外中断有：I/O中断、时钟中断

1.5、系统调用

一个应用程序运行在用户态，当它想要发出系统调用的时候，执行 陷入指令来发出内中断信号，CPU就会切换为内核态，来执行相应的系统调用指令。

• 陷入指令是在用户态执行的，执行陷入指令之后立即引发一个内中断，使CPU进入核心态

• 发出系统调用请求是在用户态，而对系统调用的相应处理在核心态下进行

• 别名：陷入指令 = trap指令 = 访管指令

1.6、OS体系结构

• 大内核：将操作系统的主要功能模块都作为系统内核，运行在核心态
  • 优点：高性能
  • 缺点：内核代码庞大，结构混乱，难以维护
• 微内核：只把最基本的功能(与硬件关联紧密的模块)保留在内核
  • 优点：内核的功能少，结构清晰，方便维护
  • 缺点：需要频繁的在核心态和用户态之间切换，性能低

2、进程管理

进程实体的组成有三部分：PCB、程序段、数据段

• PCB是给操作系统用的，程序段、数据段是给进程自己用的

• 一个进程实体(进程映像)由PCB、程序段、数据段组成。进程是动态的，**进程实体(进程映像)是静态的。**可以把进程实体理解为进程在动态执行过程当中某一时刻的快照，也就是进程实体能够反映进程在某一时刻的状态。

• 动态性是进程最基本的特征，异步性会导致并发程序执行结果的不确定性

• 进程是进程实体的运行过程，是系统进行资源分配和调度(操作系统决定让进程上CPU)的一个独立单位

PCB是进程存在的唯一标志

1. 引起进程创建的典型事件
   • 用户登录：在分时系统中，终端用户输入登录命令后，经检测合法，则系统将为该终端用户创建一个进程，并把其插入就绪队列
   • 作业调度：将作业从后备区调入内存，系统便为其分配资源调用，创建进程源于创建进程并将创建成功的进程插入就绪队列
   • 系统提供服务：例如用户向系统请求服务，系统会创建一个进程来提供用户所需要的服务，用户需要文件打印，系统为其创建一个打印进程
   • 用户的应用请求：用户进程自己创建新进程，例如数据输入、数据处理、数据显示

设备分配不需要创建进程

2. 子进程只能使用父进程拥有资源的子集，当父进程被撤销时，子进程运行结束再撤销也是可以的。
   • 子进程和父进程可以并发执行
   • 子进程和父进程共享一部分资源，但是不能共享虚拟地址空间。进程之间不能共享虚拟地址空间，但同一进程内部不同线程可以共享进程的虚拟地址空间
   • 一个进程对应一个进程控制块PCB，但一个线程不一定对应一个线程控制块TCB，多个线程可以对应一个线程控制块
   • 同一个进程中的线程可以共享进程内的全部资源，但是线程的栈指针不能共享。
3. 操作系统是根据进程控制块PCB来对并发执行的进程进行控制和管理的。
4. 进程有它的生命周期，不会一直存在于系统中，也不一定需要用户撤销。进程在时间片结束后只是就绪，而不是撤销。阻塞和就绪是进程生存期的中间状态，并不是进程的撤销与建立。通常进程被建立后，随着进程运行的正常或不正常结束而撤销，也就是进程可在完成时撤销，或在出现内存错误等时撤销
5. 进程在处理器上执行时，各个进程之间可能是无关的，但也可能是有交互性的
6. 进程控制块PCB包含：PID、UID(父进程ID)、CPU使用事件、磁盘使用情况、网络流量等。但是不包含全局变量，全局变量与PCB无关，它是数据段。
7. 进程创建时，为其分配必要的资源，但是不需要为其分配CPU， CPU是运行态得到的
8. 进程和程序的本质区别在于进程是动态的，程序是静态的，进程可能独占CPU，而程序不存在占用CPU的事情

2.1、进程五状态模型

1. 进程运行之前需要被创建，在创建的过程中系统会完成一系列相应的工作，包括新建PCB、给进程分配一系列资源等，如果一个进程正在被创建的话，那么这个进程当前处于 创建态
2. 当进程被创建完成就有了上CPU的条件，这个时候进程就处于 就绪态，也就是说处于就绪态的进程只差处理机这种资源，其他资源全部具备
3. 处于就绪态的进程被操作系统调度这个进程就可以上处理机运行，当它在处理机上运行的时候它就处于 运行态，也就是说正在处理机上运行的进程既有其他全部资源也有了处理机这种资源
4. 有时正在运行的进程可能会等待某种事件的发生，在这个事件发生之前这个进程是没有办法继续向下执行，所以这个进程此时会被剥夺处理机资源以及其他全部资源，这个时候进程就处于 阻塞态
   • 运行态执行P操作申请资源，可能由于资源不够而进入阻塞态
   • P操作只有在进程执行的过程中执行，所以P操作只会从 运行态 -> 阻塞态，不会从 阻塞态 -> 就绪态
5. 若进程等待的事件发生了，那么这个进程就可以从 阻塞态 回到 就绪态
6. 处于 运行态的进程可以主动请求运行结束，或者运行过程中遇到不可修复的错误时，会从 运行态转变为 终止态

• 运行态->阻塞态 是一种进程自身做出的主动行为
• 阻塞态->就绪态 不是进程自身能控制的，是一种被动行为，需要其他相关进程的协助

注意：有的时候进程可以直接从运行态转换为 就绪态，比如说操作系统给进程分配的时间片用完了、或者处理机被更重要的进程抢占了的时候。所以等待时间片的进程处于就绪态，等待CPU调度的进程处于就绪态。

注意：不能由阻塞态直接转换为运行态，也不能由就绪态直接转换为阻塞态(因为进入阻塞态是进程主动请求的，必然需要进程在运行时才能发出这种请求)

1. I/O操作完成之前进程在等待结果，状态为阻塞态，完成后进程等待事件就绪，变为就绪态

2. 一个进程的基本状态可以从其他两种基本状态转变过去，这个基本状态一定是就绪态

3. 不属于进程现场信息的是：进程的就绪，阻塞执行等基本状态

   • 现场信息是指执行过程中能够表示当前执行结果的中间态信息，进程由运行态转入阻塞或者就绪态会进入相应的队列中，进程的状态不属于现场信息

2.2、进程通信

1. 共享存储：互斥的访问共享空间

   • 基于数据结构的共享：比如共享空间里只能放一个长度为10的数组。这种共享方式速度慢，限制多，是一种低级通信方式

   • 基于存储区的共享：在内存中画出一块共享存储区，数据的形式、存放位置都由进程控制，而不是操作系统。相比之下，这种共享方式速度更快，是一种高级通信方式。

2. 管道通信：写数据从一边写，读数据从另一边读。数据的传输只能是单向的，要么从左向右，要么从右到左。

   • 管道只能采用半双工通信,某一时间段内只能实现单向的传输。如果要实现双向同时通信,则需要设置两个管道。
   • 各进程要互斥地访问管道(由操作系统实现)
   • 写满时不能再写，读空时不能再读
   • 数据一旦被读出，就彻底消失，因此当多个进程读同一个管道时，可能会错乱。对此，通常有两种解决方案
     1. 一个管道允许多个写进程，一个读进程(标准答案，考研以这种方式为准!)
     2. **一个管道允许多个写进程，多个读进程，但是系统会让各个读进程轮流从管道中读数据(**Linux方案)

• 管道通信和共享存储是有区别的，共享存储随便存随便取，但是管道通信是先进先出的，先写进的数据先被读出。只有把前面的数据读了，才能读后面的数据
• 写进程往管道写数据，即使管道没被写满，只要管道没空，读进程就可以从管道读数据
  • 管道不空就可读
• 读进程从管道读数据，即使管道没被读空，只要管道没满，写进程就可以往管道写数据
  • 管道没满就可写

1. 管道通信是以 自然字符流 进行写入和读出

2.3、多线程模型

简单理解：QQ是一个进程，QQ发送文件、视频聊天这就是两个线程

• 进程是资源分配的基本单位，线程是调度的基本单位
• 同一个进程中的线程切换，不会引起进程切换。不同进程中的线程切换，会引起进程切换，切换同进程内的线程，系统的开销很小，而切换进程，系统开销较大

2.3.1、线程实现方式

1. 用户级线程由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责(包括线程切换)，并不需要操作系统管理干预。
2. 用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预，CPU并不需要变态。
3. 在用户看来,是有多个线程，但是在操作系统内核看来,并意识不到线程的存在。“用户级线程"就是"从用户视角能看到的线程”。
4. 优缺点：
   • 优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
   • 缺点：
     1. 当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。
     2. 多个进程不可在多核处理机上并行运行。因为在这种情况下，只是引入了逻辑上的线程，进程依然是系统调度的基本单位，因此即便我们的电脑是多核处理机，我们的进程还是只能被分配一个核心，所以多个进程不能在多核处理机上并行运行。

1. 内核级线程的管理工作由操作系统内核完成。

2. 线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成。

3. 操作系统会为每个内核级线程建立相应的TCB(Thread Control Block,线程控制块),通过TCB对线程进行管理。“内核级线程"就是"从操作系统内核视角能看到的线程”

4. 优缺点

   • 优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。

   • 缺点：一个用户进程可能会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。

1. 一对一模型：一个用户级线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。

   • 优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。

   • 缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。

2. 多对一模型：多个用户级线程映射到一个内核级线程。且一个进程只被分配一个内核级线程。

   • 优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高

   • 缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行

重点：操作系统只"看得见"内核级线程，因此只有内核级线程才是处理机分配的单位，所以多个线程不可以在多核处理机上并行运行

3. 多对多模型：n个用户级线程映射到m个内核级线程(n>=m)。每个用户级进程对应m个内核级进程
   • 优点：克服了多对一模型并发度不高的缺点(一个阻塞全体阻塞)，又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点。

2.4、进程调度

1. 进程在操作系统内核程序临界区中不能进行调度与切换。 (√)

2. 进程处于临界区时不能进行处理机调度。(×)

   • 临界资源：一个时间段内只允许一个进程使用的资源，各进程需要互斥地访问临界资源。临界资源一次只能为一个进程所用。

     • 临界区：访问临界资源的那段代码。因此各个进程也只能 互斥地进入临界区，互斥地执行访问临界资源的代码

3. 决定一个程序能否占用处理机执行，是由进程调度决定，而不是作业调度决定。

   • 作业调度是使作业获得竞争处理机的机会，而进程调度是让某个就绪的进程在处理机上运行

4. 当进程调度的因素发生了，但是不能进行进程的调度与切换的情况有以下几种：

   1. 在处理中断的过程中，中断处理是系统工作的一部分，逻辑上不属于某一进程，不应被剥夺处理机资源，所以不能进行进程调度与切换
   2. 进程在操作系统内核程序临界区中，不能进行进程调度与切换
   3. 屏蔽中断的原子操作：如加锁、解锁、中断现场保护、恢复等原子操作。在原子操作过程中，所有的中断都要屏蔽，所以不能进行进程调度与切换

5. 在系统中进程优先权的设置基本原则：

   • 系统进程的优先权高于用户进程的优先权
   • I/O型进程的优先权高于计算型进程的优先权
   • 交互型进程的优先权高于非交互性进程的优先权

2.5、进程调度的时机

需要进行进程调度与切换的情况：

1. 当前运行的进程主动放弃处理机，例如进程中止、进程运行过程中发生异常而终止、进程主动请求阻塞(当等待某些资源时)
2. 当前运行的进程被动放弃处理机，例如分给进程的时间片用完了、有更紧急的进程需要上处理机、有优先级更高的进程进入就绪队列

不能进行进程调度与切换的情况:

1. 在处理机中断的过程中不能进行进程调度与切换。
2. 进程在 操作系统内核程序临界区中不能进行进程调度与切换。
   • 访问普通临界区时可以进行调度与切换
3. 在原子操作过程中不能进行进程调度与切换。

进程调度、切换是有代价的，所以不能说进程切换越频繁，系统的并发度越高

2.6、性能指标

CPU利用率: 指CPU “忙碌”的时间占总时间的比例。 利用率 = (忙碌的时间)/(总时间)
$$利用率=\frac{忙碌的时间}{总时间}$$
系统吞吐量:单位时间内完成作业的数量。系统吞吐量 = (总共完成了多少道作业)/总共花了多少时间
$$系统吞吐量=\frac{总共完成了多少道作业}{总共花了多少时间}$$

周转时间 = 作业完成时间 - 作业提交时间。

周转时间 = 等待时间 + 要求服务的时间(执行时间)。

• 这里的等待时间 = 进程调度时间 + 就绪队列等待时间，当然进程调度时间有时候忽略不计(2018年真题出现过)。

平均周转时间 = (各作业周转时间之和)/作业数。

等待时间：指进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低。

• 对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待I/O完成的期间其实进程也是在被服务的，所以不计入等待时间。

• 对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待被调度的时间。

所以作业的等待时间和进程的等待时间是不相同的

响应时间:指从用户提交请求到首次产生响应所用的时间。

2.7、调度算法

先来先服务调度算法FCFS：是先到达的先得到服务。

短作业优先SJF(非抢占式)：每次调度时选择当前已到达且运行时间最短的作业/进程。

高响应比优先HRRN：计算所有就绪进程的响应比，选择响应比最高的进程上处理机。
$$响应比=\frac{等待时间+要求服务时间}{要求服务时间}$$
时间片轮转调度算法：轮流让就绪队列中的进程依次执行一个时间片(每次选择的都是排在就绪队列队头的进程)

• 如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。(比如系统中有10个进程在并发执行，如果时间片为1s，则一个进程被响应可能需要等9s，也就是说，如果用户在自己的进程的时间片外通过键盘发出调试命令，可能需要等待9s才能被系统响应)
• 另一方面，进程调度、切换是有时间代价的(保存、恢复运行环境)，因此如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小。

优先级调度算法：每次调度时选择当前已到达且优先级最高的进程

• 非抢占式只需在进程主动放弃处理机时进行调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占。

1. 只要是短作业优先算法都会产生饥饿。

   • 时间片轮转算法不区分优先级

   • 实时调度算法是根据进程的紧迫程度为其设定执行的优先级，与作业本身的执行时间无关

   • 高响应比优先调度算法既有利于短作业，又兼顾长作业，还实现了先来先服务(作业等待时间越长，响应比就越高)

   • 分时系统中常采用时间片轮转来处理进程调度。

   • 进程调度主要负责选一个进程上CPU

2. 时间片轮转和多级反馈队列一定是抢占式的

2.8、死锁

• 死锁和饥饿肯定不可能是运行态，而死循环是可以是运行态的
• 死循环一般是由程序员导致的
• 循环等待 => 死锁(发生死锁时一定有循环等待，但是发生循环等待时未必死锁)

1. 死锁预防：破坏四个必要条件，不允许死锁发生

   1. 破坏互斥条件：把只能互斥使用的资源改造为允许共享使用，如 SPOOLing 技术
      • 缺点：可行性不高，但是很多时候都无法破坏互斥条件
   2. 破坏不剥夺条件：释放已经占有的资源
      • 方案一：申请的资源得不到满足时，立即释放所拥有的所有资源
      • 方案二：申请的资源被其他进程占用时，由操作系统协助剥夺(考虑优先级)
      • 缺点：实现复杂，剥夺资源可能导致大部分工作失效，反复申请和释放资源导致系统开销大，可能导致饥饿
   3. 破坏请求和保持条件：一次性申请完所需要的资源
      • 缺点：资源利用率低，可能导致饥饿
   4. 破坏循环等待条件：给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源
      • 缺点：不方便增加新设备，会导致资源浪费，用户编程麻烦

2. 死锁避免：银行家算法，不允许死锁发生

   • 如果系统处于安全状态，就一定不会发生死锁。
   • 如果系统进入不安全状态，就可能发生死锁(处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态)
   • 银行家算法不考代码，但是通常题中会给相应矩阵，要看懂矩阵表示含义

3. 死锁的检测和解除：资源分配图，允许死锁发生

   • 圆形表示进程结点，矩形表示资源结点
   • 进程结点指向资源结点的边是请求边，资源结点指向进程结点的边是分配边

4. 解除死锁的主要方法有：

   1. 资源剥夺法：挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
   2. 撤销进程法（或称终止进程法）：强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来
   3. 进程回退法：让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。

1. 操作系统产生死锁的根本原因是：
   1. 资源数量不足
   2. 进程推进顺序不当

2.10、同步与互斥

同步和互斥：

• 例如：缓冲区为空 -> 生产者生产，缓冲区不为空 -> 消费者消费，这种一前一后(前趋关系)就是同步
  • 缓冲区必须互斥的访问，这就是互斥
• 临界区是进程中访问临界资源的代码段。例如对打印机执行打印操作
  • 进入临界区 == 可以访问临界资源
  • 临界区是一段程序，但并不是只包含一个程序段
• 共享资源是可以同时被多个进程访问的资源，临界资源是同一时间只能一个进程访问
  • 磁盘、可重入的程度代码就是共享资源，公用队列是临界资源，公用队列一次只可供一个进程使用

进程互斥的软件实现方法：

1. 单标志法：在进入区只检查，不上锁
   • 主要问题：不遵循 空闲让进 原则
2. 双标志先检查法：在进入区先检查，后上锁，退出区解锁
   • 主要问题：不遵循 忙则等待 原则
3. 双标志后检查法：在进入区先加锁，后检查，退出区解锁
   • 主要问题：不遵循 空闲让进、有限等待 原则，可能导致饥饿
4. Peterson算法：在进入区 主动争取 - 主动谦让 - 检查对方是否想进、己方是否谦让
   • 主要问题：不遵循 让权等待 原则，会发生忙等，不会产生饥饿
   • Peterson 算法的代码不需要会，但要能读懂?(真题考过)

进程互斥的硬件实现方法：

1. 中断屏蔽方法：利用"开/关中断指令"实现(与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况)
   • 优点：简单、高效
   • 缺点：不适用于多处理机；只适用于操作系统内核进程，不适用于用户进程(因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险)
2. TestAndSet指令：相比软件实现方法，TSL指令把"上锁"和"检查"操作用硬件的方式变成了一气呵成的原子操作。
   • 优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞，适用于多处理机环境
   • 缺点：不满足"让权等待"原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致"忙等"
   • TSL指令的代码也要能看懂?(真题考过)
3. Swap指令
   • 优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境
   • 缺点：不满足"让权等待"原则,暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致"忙等"

1. 在操作系统中要对并发进程进行同步的原因是：并发进程是异步的，同步最主要的目的是使得并发的程序能顺序的执行

2.11、信号量

• 整型信号量存在的问题：不满足让权等待原则

• 记录型信号量：

  • 一个信号量对应一种资源
  • 信号量的值 = 这种资源的剩余数量(信号量的值如果小于0，说明此时有进程在等待这种资源)
  • P(S)-申请一个资源S,如果资源不够就阻塞等待
  • V(S)-释放一个资源S,如果有进程在等待该资源,则唤醒一个进程

• 互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少

• 结论：互斥信号量的初值为1：代表同一时间只有一个进程进入互斥段

  • 若同一时间允许 n 个进程进入临界区(互斥段)，则互斥信号量的初值为 n ?

1. 管程中的是条件变量，信号量是数值，代表资源有多少；而条件变量是 true、false，可以理解为0个资源

   • wait() = P操作，对条件变量P一下，则该进程阻塞，并将其挂在对应的阻塞队列上
   • signal() = V操作，对条件变量V一下，则唤醒对应阻塞队列上的队首进程
   • 注意：条件变量不能根据值来判断该进程是否进入阻塞状态
   • 管程只能用于实现进程的同步。这句话是正确的，因为同步包括同步和互斥。?
   • 管程只能用于实现进程的互斥。这句话是错误的
   • 任何时候只能有一个进程在管程中执行，管程中定义的变量只能被管程内的过程访问，管程是由编程语言支持的进程同步机制

2. P操作前，进程变为阻塞态，则信号量的值 ≤ 0；P操作后，进程变为阻塞态，则信号量的值 ＜ 0

3. 当信号量为负时，信号量的绝对值表示等待该资源的进程数量

   • 例如 mutex = -1， 表示此时有1个进程在等待该资源

3、内存管理

将高级语言程序编译为若干个目标模块，然后将若干个目标模块链接成一个装入模块，链接后形成逻辑地址，之后再将装入模块再装入到内存运行，装入后形成物理地址。

链接步骤有三种方式：

1. 静态链接：在程序运行之前，就将各目标模块及它们所需的库函数链接成一个装入模块
2. 装入时动态链接：将各目标模块装入内存，边装入边链接的链接方式。将这些目标模块放入内存时才会将他们进行链接
3. 运行时动态链接：在程序执行中需要该目标模块时，才对它进行链接。只有用到某个目标模块时，才会将其装入内存，用不到的模块不需要装入内存。

将指令中的逻辑地址转换为正确的物理地址：

1. 绝对装入：在将程序放入内存之前就知道这个程序从内存哪个位置开始存放，就可以让编译程序把各个变量存放的那些地址直接把他修改成正确的物理地址
   • 绝对装入只适合单道程序环境，灵活性很差，换一台电脑就不行了
2. 静态重定位装入(可重定位装入)：装入时对地址进行重定位，将逻辑地址变换为物理地址
   • 给这个进程分配的地址空间必须是连续的，并且这个作业必须一次全部装入内存，也就是说在作业在装入内存时，就必须分配其要求的全部的内存空间。
   • 作业一旦进入内存后，在运行期间就不能再移动，也不能申请内存空间。(毕竟地址都已经被确定了，再移动地址又乱了)
   • 用于早期的多道批处理操作系统
3. 动态运行时装入(动态重定位)：装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟到程序真正要执行时才进行。因此装入内存后所有的地址依然是逻辑地址。这种方式需要一个重定位寄存器的支持。
   • 重定位寄存器：存放装入模块存放的起始位置。当程序执行时，CPU会将重定位寄存器里面的地址+逻辑地址=物理地址。
   • 采用动态重定位时允许程序在内存中发生移动。
   • 可将程序分配到内存地址不连续的存储区中，在程序运行前只需装入它的部分代码即可投入运行，然后在程序运行期间，根据需要动态申请分配内存，便于程序段的共享，可以向用户提供一个比存储空间大的多的地址空间。
   • 用于现代操作系统

逻辑地址到物理地址的转换，也就是装入，也叫做地址重定位

操作系统需要提供内存保护功能。保证各进程在各自存储空间内运行，互不干扰

内存保护可采取两种方法：

• 方法一：在CPU中设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令要访问某个地址
  时，CPU检查是否越界。
• 方法二：采用重定位寄存器（又称基址寄存器）和界地址寄存器（又称限长寄存器）进行越界检查。重定位寄存器中存放的是进程的起始物理地址。界地址寄存器中存放的是进程的最大逻辑地址。

1. 动态重定位是在作业的 执行过程 中装入的

2. 固定分区方式可以使用静态重定位：提前把物理地址算好

3. 对重定位存储管理方式，应为整个系统设置一个重定位寄存器

4. 固定分区管理中分区大小是在系统执行过程中 系统初始化 时建立的。

3.1、内存的分配与回收

1. 连续分配方式：系统指为用户进程分配的必须是一个连续的内存空间。
   1. 单一连续分配：内存被分为系统区和用户区，内存中只能有一道用户程序
      • 优点：无外部碎片
      • 缺点：有内部碎片，只能用于单用户、单任务的操作系统中
   2. 固定分区分配：将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业。固定分区分配分为定长分区和可变分区
      • 定长分区：分区大小相等，缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合
      • 可变分区：分区大小不等，增加了灵活性，可以满足不同大小的进程需求
      • 优点：无外部碎片
      • 缺点：会产生内部碎片
   3. 动态分区分配(可变分区分配)：根据进程的大小动态地建立分区
      • 优点：没有内部碎片
      • 缺点：有外部碎片

• 内部碎片，分配给某进程的内存区域中，如果有些部分没有用上，这些部分就称为内部碎片。
• 外部碎片，是指内存中的某些空闲分区由于太小而难以利用。因为各个进程需要的都是一整片连续的内存区域，所以空闲分区太小的话，那么任何一个空闲分区都不能满足进程的需求。

碎片可以通过紧凑技术来解决

分区分配管理中对每个作业分配的是若干地址不连续的内存单元

2. 动态分配方式：动态分配分区方式也是属于连续分配方式

1. 结论：但凡是固定长度都会产生内部碎片，例如分页式存储管理、固定分区式存储管理、虚拟分页存储管理

3.2、基本分页存储管理

• 页框=页帧=内存块=物理块=物理页面，指的是内存空间被分为一个个大小相等的分区。这个分区叫页框=页帧=内存块=物理块=物理页面
• 页框号=页帧号=内存块号=物理块号=物理页号，指的是内存被分为一个个大小相等的分区的编号。
• 页=页面，指的是进程的逻辑地址空间被分为与页框大小相等的一个个部分。这个部分叫页=页面
• 页号=页面号，指的是进程的逻辑地址空间被分为与页框大小相等的部分的编号。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TnlTNBEu-1661856919228)(操作系统精简版.assets/6.png)]

一个是将内存空间分区，一个是将进程的逻辑地址空间分区

操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系。各个页面不必连续存放，可以放到不相邻的各个页框中。

注意：进程的最后一个页面可能没有一个页框那么大。也就是说，分页存储有可能产生内部碎片，因此页框不能太大，否则可能产生过大的内部碎片造成浪费

3.2.1、页表

为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表。页表通常存在PCB（进程控制块）中。

1. 一个进程对应一张页表
2. 进程的每个页面对应一个页表项(页表项可以理解为页表当中的一行)
3. 每个页表项(也就是页表中的每行)由 页号 和 块号 组成
4. 页表记录进程页面和实际存放的内存块(页框)之间的映射关系
5. 每个页表项的长度是相同的

1. 每个页表项多大？占几个字节？

假设某系统物理内存大小为4GB，页面大小为4KB，则每个页表项至少应该为多少字节？

• 内存块大小(页框大小)=页面大小=4KB= 2¹² B
• 4GB的内存总共会被分为2³² / 2¹² = 2²⁰个内存块(页框大小)
• 内存块号的范围应该是0 ~ 2²⁰ -1 ，编号是从0开始的
• 内存块号至少要用20 bit来表示，也就是20个二进制位才能表示 0 ~ 2²⁰-1
• 计算机分配空间是以字节为单位分配的，2个字节才16bit，所以至少要用3B来表示块号（也就是3*8=24bit）
• 页表中的页号并不需要占存储空间，因为页表项是连续存放，因此页号可以是隐含的，不占存储空间。如同数组的下标并不需要占存储空间的道理类似。也就是说至少要用3B来存储一个页表项。
• 如果进程有n+1个页面，n+1个页面对应n+1个页表项，则存储这个进程的页表至少需要 3×(n+1)B

页表项在逻辑上包含了页号和块号，但是在物理上只需要存放块号，只有块号需要占据存储空间。

2. 实现逻辑地址到物理地址的转换?

若页面大小是2的整数次幂，我们可以把逻辑地址分为==(页号，页面偏移量)==两部分：

• 一个页面的大小是2^K个内存单元，则有K位表示页内偏移量

• 如果有M位表示页号，则说明在该系统中，一个进程最多允许有2^M个页面

• 只要知道页内偏移量的位数，就可以推出页面大小，从而确定逻辑地址的结构

物理地址的计算更加迅速：根据逻辑地址得到==(页号，页内偏移量)，根据页号查询页表(页号，内存块号)==，从而找到页面存放的内存块号，将二进制表示的内存块号和页内偏移量拼接起来，就可以得到最终的物理地址

有些奇葩题目中页面大小有可能不是2的整数次幂，这种情况还是得用最原始的方法计算：
$$\begin{gathered} 页号=\frac{逻辑地址}{页面长度}(取除法的整数部分) \\ 页内偏移量=逻辑地址\%页面长度(取除法的余数部分) \end{gathered}$$

3.2.2、两级页表

单级页表存在的问题：

1. 页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框。 采用两级页表

2. 没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面 采用标志位

两级页表的逻辑结构为==(一级页号，二级页号，页内偏移量)==，一级页号也称页目录表/顶级页表/外层页表。

注意：

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

2. 两级页表访问内存要进行3次

   • 单级页表访问内存要2次

   • 三级页表访问内存要进行4次

   • 四级页表访问内存要进行5次

   • 结论：没有快表结构，n级页表访问内存次数是n+1次

快表TCL和普通高速缓存Cache的区别：

• 快表TLB中只有页表项的副本
• 普通Cache中可能会有其他各种数据的副本

3.3、基本分段存储管理

分段系统的逻辑地址结构由段号(段名)和段内地址(段内偏移量)所组成。==(段号，段内地址)==如：

• 段号的位数决定了每个进程最多可以分几个段
  • 段号有n位，则进程最多分为 2ⁿ 个段
• 段内地址位数决定了每个段的最大长度是多少
  • 段内地址有n位，则每个段的最大长度为 2ⁿB

用段表记录各个逻辑段在内存中的存放位置

• 页表建立了各个逻辑页面到实际物理页框之间的关系
• 段表建立个各个逻辑段到实际物理内存存放位置之间的关系

1. 每个段对应一个段表项(也就是段表中的一行)，其中记录了==(段号、段长、该段在内存中的起始位置)==

   • 相比于页表，段表多了段长，因为每个分段的长度可能是不一样的，而在分页存储管理当中，每个页面的大小都是一样的，所以页面长度就不需要显示记录。

2. 各个段表项的长度是相同的(也就是说段表中的每行在内存当中占据相同的空间)

   • 例如：某系统按字节寻址，采用分段存储管理，逻辑地址结构为(段号16位,段内地址16位)，则每个段的最大长度为 2¹⁶B，所以在段表中用16位就可以表示最大段长，
   • 物理内存大小为4GB(也就是2³²个字节，范围是0 ~ 2³²-1，可用32位二进制表示整个物理内存地址空间)，所以，基址我们只需要用32位就可以表示，因此，可以让每个段表项占16+32 = 48位，即6B。
     • 因为段号不占存储空间，和页号类似。
   • 若段表存放的起始地址为M，则K号段对应的段表项存放的地址为M + K*6

内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。

段页式管理分段：段页式管理的逻辑地址结构由==(段号、页号、页内偏移量)==组成

• 段号的位数决定了每个进程最多可以分为几个段
  • 段号占16位，因此在该系统中，每个进程最多有2¹⁶ = 64K个段
• 页号的位数决定了每个段最大有多少页
  • 页号占4位，因此每个段最多有2⁴ = 16页
• 页内偏移量决定了页面大小、内存块大小是多少
  • 页内偏移量占12位，因此每个页面大小为2¹² = 4096 = 4KB

在段页式存储管理系统中，地址映射表是：每个进程一张段表，每段一张页表(了解概念就行)

访问一个逻辑地址需要几次访存？

• 分页（单级页表）：第一次访存——查内存中的页表，第二次访存——访问目标内存单元。总共两次访存
• 分段：第一次访存——查内存中的段表，第二次访存——访问目标内存单元。总共两次访存

与分页系统类似，分段系统中也可以引入快表机构，将近期访问过的段表项放到快表中，这样可以少一次访问，加快地址变换速度。

3.4、分段和分页

• 分页对用户是不可见的，分段对用户是可见的(但是不能说被用户所感知)

• 页的大小固定且由系统决定。段的长度却不固定，决定于用户编写的程序。

• 分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。

• 分页管理当中，用户自己看来自己进程的地址空间是连续的。分段管理当中，用户也知道自己进程的地址空间是被分为一个一个段，并且每个段占据一连串的地址空间。

• 分段比分页更容易实现信息的共享和保护。要想实现信息共享，只需要让各个进程的段表项指向同一个段即可实现共享，可以被共享的代码称为纯代码或可重入代码(不属于临界资源)

1. 分段管理中，各段之间不要求连续，并且各个段的大小也不同
2. 页式的逻辑地址是连续的，段式的逻辑地址可以不连续
3. 各页可以分散存放在主存，每段必须占用连续的主存空间，分页和分段都是操作系统确定和执行的
4. 分页和分段都是采用动态重定位的方式

3.5、虚拟内存

传统存储管理：

• 连续分配：单一连续分配、固定分区分配、动态分区分配

• 非连续分配：基本分页存储管理、基本分段存储管理、基本段页式存储管理

• 传统存储管理的缺点：

  • 一次性：作业必须一次性全部装入内存后才能开始运行。
  • 驻留性：一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。

虚拟内存就是应用了局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。

虚拟内存有一下三个主要特征：

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

虚拟内存的实现需要建立在离散分配的内存管理方式基础上。

3.6、页面置换算法

缺页时未必发生页面置换，若还有可用的空闲内存块，就不用进行页面置换。

• 当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。-> Belady异常(贝拉迪异常)，只有FIFO算法会产生Belady异常。

3.7、页面分配策略

驻留集：指的是请求分页存储管理中给进程分配的物理块的集合。在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。

• 若驻留集太小，会导致缺页频繁
• 若驻留集太大，又会导致多道程序并发度下降，资源利用率极低

驻留集大小的分配有两种方式：

1. 固定分配：驻留集大小不变。

2. 可变分配：驻留集大小可变

置换页面范围又分为两种：

1. 局部置换：发生缺页时只能选进程自己的物理块进行置换
   • 当某个进程发送缺页，并且需要置换出某个页面，置换出的页面只能是自己的
2. 全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。
   • 当某个进程发送缺页，并且需要置换出某个页面，置换出的页面可以是自己的，也可以是别人的

固定分配局部置换：进程运行前就分配一定数量的物理块，缺页时只能换出进程自己的某一页

可变分配全局置换：只要缺页就分配新物理块，可能来自空闲物理块，也可能需换出别的进程页面

可变分配局部置换：频繁缺页的进程，多分配一些物理块

何时调入页面：

• 预调页策略：一般用于进程运行前
• 请求调页策略：进程运行时，发现缺页再调页

从何处调入：

• 对换区：采用连续存储方式，速度更快。文件区：采用离散存储方式，速度更慢
• 对换区足够大：运行将数据从文件区复制到对换区，之后所有的页面调入、调出都是在内存与对换区之间进行
• 对换区不够大：不会修改的数据每次都从文件区调入，会修改的数据调出到对换区，需要时再从对换区调入
• UNIX方式：第一次使用的页面都从文件区调入，调出的页面都写回对换区，再次使用时从对换区调入

抖动(颠簸)现象：页面频繁换入换出的现象。主要原因是分配给进程的物理块不够(置换算法选择不当)

驻留集：指请求分页存储管理中给进程分配的存储块的集合

工作集：只在某段时间间隔里进程实际访问页面的集合

如上图访问到23，由于窗口尺寸为4，那么就会从当前位置开始，向前寻找4个页面号，由此来确定工作集的内容。

工作集大小可能小于窗口尺寸，实际应用中操作系统可以统计进程的工作集大小，根据工作集大小给进程分配若干内存块。

如：窗口尺寸为5，经过一段时间的监测，发现某进程的工作集最大为3，那么说明该进程有很好的局部性，可以给这个进程分配3个以上的内存块即可满足进程的运行需要。一般来说驻留集大小不能小于工作集大小，否则进程运行过程中将频繁缺页。

4、文件管理

• 无结构文件（如文本文件）——由一些二进制或字符流组成，又称流式文件
• 有结构文件（如数据库表）——由一组相似的记录组成，又称记录式文件，这一条条记录可以是定长记录也可以是不定长记录

文件的逻辑结构分为无结构文件和有结构文件，有结构文件又分为顺序文件、索引文件、索引顺序文件。

根据各个记录是否按照关键字排列，可以把顺序文件分为串结构和顺序结构

• 串结构：记录之间的顺序与关键字无关，通常是按照记录存入的时间决定记录的顺序
• 顺序结构：记录之间的顺序按照关键字顺序排列

1. 若顺序文件采用链式存储，无论是定长还是可变长记录，都无法实现随机存取，每次只能从第一个记录开始依次向后查找。因为并不能直接计算出某一个记录的物理地址。

   • 若顺序文件采用顺序存储
     • 对于可变长记录，无法实现随机存取
     • 对于定长记录，可以实现随机存取，记录长度为L，则第 i 个记录存放的相对位置是 i × L
       • 若采用串结构，也就是记录之间的顺序和关键字无关，则无法快速找到某关键字对应的记录
       • 若采用顺序结构，也就是记录之间的顺序按照关键字顺序排列，则可以快速找到某关键字对应的记录

2. 索引文件：为每个文件建立一张索引表，每个索引表的一条表项会对应文件的一条记录。文件的各个记录可以在物理上离散地存放，但是索引表的各个表项需要在物理上连续地存放。每个索引表的表项大小都是相等的，因此我们可以说索引表本身是定长记录的顺序文件(支持随机访问)

   • 优点：索引文件的检索速度很快，支持随机存取
   • 缺点：索引表可能占有太多空间

3. 索引顺序文件：将记录分组，每组对应一个索引表项

4.1、文件保护

1. 口令保护：为文件设置一个口令，口令一般存放在文件对应的FCB或索引结点中
   • 优点：保存口令的空间开销不多，验证口令的时间开销也很小。
   • 缺点：正确的口令存放在系统内部，不够安全。
2. 加密保护：使用某个密码对文件进行加密
   • 优点：保密性强，不需要在系统中存储密码
   • 缺点：编码/译码，或者说加密/解密要花费一定时间
3. 访问控制：在每个文件的FCB（或索引结点）中增加一个访问控制列表
   • 优点：实现灵活，可以实现复杂的文件保护功能

4.2、文件共享

1. 硬链接：基于索引结点的共享方式，各个用户的目录项指向同一个索引结点
   • 索引结点中需要有链接计数 count
   • 某用户想删除文件时，只是删除该用户的目录项
   • 只有 count == 0 时才能真正删除文件数据和索引结点，否则会导致指针悬空
   • 上图User1和User2在使用硬链接的方式共享的使用文件1
2. 软链接：基于符号链的共享方式，User3用户想要使用软链接的方式来共享文件1，那么User3会建立一个新的文件，这个文件是Link类型的文件，记录了文件1的存放路径C:/User/aaa(类似于Windows系统中的快捷方式)
   • 在一个 Link 型的文件中记录共享文件的存放路径
   • 当User3访问aaa时，操作系统判断文件aaa属于Link类型文件，于是会根据其中记录的路径层层查找目录，最终找到User1的目录表中的aaa表项，于是就找到了文件1的索引结点。
   • 即使软链接指向的共享文件已经被删除，Link型文件依然存在，只是通过 Link 型文件中的路径去查找共享文件会失败
   • 由于用软链接的方式访问共享文件时，要查询多级目录会有多次磁盘I/O，因此用软链接访问共享文件的速度要比硬链接更慢

4.3、文件分配

文件分配方式分为：连续分配，链接分配，索引分配

1. 链接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。
   • 缺点：若文件很大，索引表很长，就需要将很多个索引块链接起来。想要找到i号索引块，必须先依次读入0~i-1号索引块，这就导致磁盘I/O次数过多，查找效率低下。
2. 多层索引：建立多层索引（原理类似于多级页表）。使第一层索引块指向第二层的索引块。还可根据
   文件大小的要求再建立第三层、第四层索引块。采用K层索引结构，且顶级索引表未调入内存，则访问
   一个数据块只需要K + 1次读磁盘操作。
   • 缺点：即使是小文件，访问一个数据块依然需要K+1次读磁盘。
3. 混合索引：多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引表）、还包含两级间接索引（指向两层索引表）。
   • 优点：对于小文件来说，访问一个数据块所需的读磁盘次数更少。

若采用多层索引，则各层索引表大小不能超过一个磁盘块

采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K+1次读磁盘操作

1. 链接分配均不支持随机访问
2. 连续分配顺序存取速度快，代表其查询速度最快
3. 连续分配不支持变长文件，索引分配支持变长文件

4.4、文件存储空间管理

• 空闲表法：适用于连续分配方式
• 空闲链表法：离散分配、连续分配都适用
• 位示图法：连续分配，离散分配都适用

位示图法：如何从(字号,位号)推出盘块号，如何从盘块号推出(字号,位号)

• 盘块号、字号、位号都是从0开始，若n表示字长，则
  • (字号i，位号j)=(i，j)的二进制位对应的盘块号 b = ni + j
  • 盘块号b对应的字号i=b/n，位号j=b%n
• 例如字号为0，位号为1所对应的盘块号是1号块：(0，1) -> b = 16×0+1 = 1
• 例如字号为1，位号为10所对应的盘块号是26号块：(1，10) -> b = 16×1+10 = 26
• 例如盘块号为13，则对应的字号i=13/16=0，对应的位号j=13%16=13

采用位示图法如何进行分配呢？若某个文件需要K个空闲块：

1. 顺序扫描位示图找到K个相邻或不相邻的"0"
2. 根据字号、位号算出对应的盘块号，将相应的盘块分配给文件
3. 将相应二进制位设置为"1"

如何回收磁盘块呢？

1. 根据回收的盘块号计算出对应的字号、位号
2. 将相应二进制位设为"0"

4.5、文件的基本操作

1. 创建文件：操作系统在处理Create系统调用时，主要做了两件事：

   1. 在外存中找到文件所需的空间
   2. 根据文件存放路径的信息找到该目录对应的目录文件，在目录中创建该文件对应的目录项。目录项中包含了文件名、文件在外存中的存放位置等信息。

2. 删除文件：操作系统在处理Delete系统调用时，主要做了几件事：

   1. 根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项，从目录表中删除文件对应的目录项，删除文件对应的文件控制块

   2. 根据该目录项记录的文件在外存的存放位置、文件大小等信息，回收文件占用的磁盘块。

3. 打开文件：操作系统在处理open系统调用时，主要做了几件事(如下图)：

   1. 根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的的目录项，并检查该用户是否有指定的操作权限。
   2. 将目录项复制到内存中的“打开文件表”中。并将打开文件表的索引号(文件描述符)返回给用户。之后用户使用打开文件表的编号来指明要操作的文件。
      • 将目录项复制到内存中，之后用户进成A再操作文件，就不需要每次都重新查目录，这样可以加快文件的访问速度
      • 注意有两种打开文件表：一种是系统的打开文件表(整个系统只有一张)，这个文件表会记录所有的正在被使用的文件的信息。另一种是每个进程会有自己的进程打开文件表，这张表记录了进程此时打开的文件等信息。

4. 关闭文件：操作系统在处理Close的系统调用时，主要做了几件事：

   1. 将进程的打开文件表相应的表项删除
   2. 回收分配给该文件的内存空间等资源
   3. 系统打开表的打开计数器count减1，若count=0，则删除对应的表项

5. 读文件：操作系统在处理read系统调用时，会从读指针指向的外存中，将用户指定大小的数据读入用户指定的内存区域中

6. 写文件：操作系统在处理write系统调用时，会从用户指定的内存区域中，将指定大小的数据写回写指针指向的外存

读/写文件用 “文件描述符"即可指明文件，不再需要用到"文件名”

1. 打开文件会把文件的文件控制块FCB调入内存，而不会把文件内容读入内存
2. 逻辑文件是 从用户观点来看 的文件组织形式，逻辑地址就是从0开始编号，但是对应的物理地址并不一定是从0开始编号。
3. 文件目录的主要作用是：按名存取
4. 绝对路径是从根目录开始，相对路径是从当前目录开始
5. 在多级目录结构中，同一级目录中不能有相同的文件名，但在不同级的目录中可以有相同的文件名
6. 对一个文件的访问，常由 用户访问权限和文件属性 共同限制
7. 文件的顺序存取是按文件的逻辑号逐一存取

5、I/O管理

• 块设备【传输速率较高，可寻址，即对它可随机地读/写任一块】

  • 如磁盘等——数据传输的基本单位是块，磁盘是典型的块设备，磁盘设备的I/O控制主要采取DMA方式

• 字符设备【传输速率较慢，不可寻址，在输入/输出时常采用中断驱动方式】

  • 鼠标、键盘等——数据传输的基本单位是字符。

5.0、I/O控制方式

1. 程序直接控制方式：当用户进程需要输入或输出数据时，它通过CPU发出启动设备的指令，然后用户进程进入测试等待状态，在等待时间内，CPU不断地用一条测试指令，通过测试一台设备的忙/闲标志来获得外设的工作状态

   • 优点：实现简单。在读/写指令之后，加上实现循环检查的一系列指令即可（因此才称为"程序直接控制方式"）
   • 缺点：CPU和I/O设备只能串行工作，CPU需要一直轮询检查，长期处于"忙等"状态，CPU利用率低。

2. 中断驱动方式：仅当I/O操作正常或异常结束时，才中断中央处理机

   • 优点：与"程序直接控制方式"相比，在"中断驱动方式"中，I/O控制器会通过中断信号主动报告I/O已完成，CPU不再需要不停地轮询。CPU和I/O设备可并行工作，CPU利用率得到明显提升。
   • 缺点：每个字在I/O设备与内存之间的传输，都需要经过CPU。而频繁的中断处理会消耗较多的CPU时间。
   • CPU会在每个指令周期的末尾检查中断(也就是每个指令执行结束CPU就检查一次中断)
   • 中断处理过程中需要保存、恢复进程的运行环境。这个过程是需要一定时间开销的。可见，如果中断发生
     的频率太高，也会降低系统性能。

3. DMA方式：在外围设备和内存之间开辟直接的数据交换通路

   • 优点：数据传输以块为单位，CPU介入频率进一步降低。数据的传输不再需要先经过CPU再写入内
     存，数据传输效率进一步增加。CPU和I/O设备的并行性得到提升。
   • 缺点：CPU每发出一条I/O指令，只能读/写一个或多个连续的数据块。如果要读/写多个离散存储的数据块，或者要将数据分别写到不同的内存区域时，CPU要分别发出多条I/O指令，进行多次中断处理才能完成。
   • 数据的传送单位是块。不再是一个字、一个字的传送
   • 数据的流向是从设备直接放入内存，或者从内存直接到设备。不再需要CPU作为"快递小哥"。
   • 仅在传送一个或多个数据块的开始和结束时，才需要CPU干预。

5.1、中断处理程序

当I/O任务完成时，I/O控制器会发送一个中断信号，系统会根据中断信号类型找到相应的中断处理程序并执行。

中断处理程序会从I/O控制器当中读出设备的状态来判断这次的I/O是不是正常的结束，如果此时正常的结束，接下来中断处理程序会从I/O控制器的数据寄存器当中读出一个字的数据，并且经由CPU放到内存缓冲区当中，这就完成了一个字的读入。若这次的I/O是非正常的结束，那么系统会根据异常原因做相应的处理。这就是中断处理程序所需要做的事情。

当中断处理程序做完后，接下来又会交由设备驱动程序处理，再交给设备独立性软件处理，最终反映给用户。所以对于数据的处理是从下向上依次层层处理的。

5.2、I/O软件层次结构

• 设备独立性软件，也称为设备无关性软件，也称为 系统调用处理层，设备独立性的基本含义是指应用程序独立于具体使用的物理设备，用户编程时使用的设备与实际使用的设备无关。设备独立性软件的功能：
  • 向上层提供统一的系统调用接口（如read/write系统调用）
  • 设备的保护：原理类似与文件保护。设备被看做是一种特殊的文件，不同用户对各个文件的访问权限是不一样的，同理，对设备的访问权限也不一样。
  • 差错处理
  • 设备的分配与回收
  • 数据缓冲区管理
  • 建立逻辑设备名到物理设备名的映射关系，根据设备类型选择调用相应的驱动程序
    • 设备独立性软件需要通过"逻辑设备表(LUT)"来确定逻辑设备对应的物理设备**，并找到该设备对应的**设备驱动程序

直接涉及到硬件具体细节、且与中断无关的操作肯定是在设备驱动程序层完成的；没有涉及硬件的、对各种设备都需要进行的管理工作都是在设备独立性软件层完成的

5.3、I/O核心子系统

5.4、假脱机技术

假脱机技术，又称 SPOOLing技术，是用软件的方式模拟脱机技术。SPOOLing系统的组成如下：

• SPOOLing系统主要包括三部分，即输入井和输出井，输入缓冲区和输出缓冲区以及输入进程和输出进程。这三部分由预输入程序，井管理程序和缓输出程序管理

• SPOOLing技术是为了缓和CPU与I/O设备之间速度不匹配的矛盾

• 输入进程是先接收输入设备的数据，然后把这些数据先放到输入缓冲区里，之后再把输入缓冲区的数据放到磁盘的输入井当中。输出进程是先从输出井当中取出数据放到输出缓冲区，再将输出缓冲区的数据放到输出设备。

• SPOOLing技术需要外存的支持，需要多道程序技术的支持

• SPOOLing技术是以空间换时间

SPOOLing技术可以把一台物理设备虚拟成逻辑上的多台设备，可将独占式设备改造成共享设备。

SPOOLing技术不需要等待I/O操作完成

• SPOOLing技术中，用户进程实际分配到的是设备的一部分存储区。

5.5、设备分配

设备的固有属性可分为三种：独占设备、共享设备、虚拟设备

• 独占设备 —— 一个时段只能分配给一个进程（如打印机）

  • 分配共享设备可能引起死锁，分配独占设备不会引起死锁

• 共享设备 —— 可同时分配给多个进程使用（如磁盘），各进程往往是宏观上同时共享使用设备，而微观上交替使用。

  • 共享设备在某一时刻仍然只允许一个进程访问 (√)
  • 共享设备在同一时间内允许多个进程同时访问 (×)
  • 因为共享分为同步共享和异步共享

• 虚拟设备 —— 采用SPOOLing技术将独占设备改造成虚拟的共享设备，可同时分配给多个进程使用（如采用SPOOLing技术实现的共享打印机）

  • 虚拟设备是指把一个物理设备变换为多个对应的逻辑设备

独占设备采用静态分配方式，共享设备采用动态分配方式

从进程运行的安全性上考虑，设备分配有两种方式：

• 安全分配方式：为进程分配一个设备后就将进程阻塞，直到进程释放I/O设备后才将进程唤醒。(例如考虑进程请求打印机打印输出的例子)，一个进程被分配打印机之后，这个进程就必须先阻塞等待，虽然说进程只需要把数据丢给打印机然后就不用管打印机的打印输出过程，继续向下执行后面代码。但是采用安全分配方式就必须阻塞，直到打印结束之后进程才会被再次唤醒。

  • 一个时段内每个进程只能使用一个设备
    • 优点：破坏了"请求和保持"条件，不会死锁
    • 缺点：对于一个进程来说，CPU和I/O设备只能串行工作

• 不安全分配方式：进程发出I/O请求后，系统为其分配I/O设备，进程可继续执行，之后还可以发出新的I/O请求。只有某个I/O请求得不到满足时才将进程阻塞。(一个进程被分配打印机之后，这个进程把数据丢给打印机，然后自己继续向下执行，甚至再向下执行的过程中还可以继续申请其他I/O设备)

  • 一个进程可以同时使用多个设备
    • 优点：进程的计算任务和I/O任务可以并行处理，使进程迅速推进
    • 缺点：有可能发生死锁（死锁避免、死锁的检测和解除）

• 静态分配：进程运行前为其分配全部所需资源，运行结束后归还资源。(破坏了"请求和保持"条件，不会死锁)

• 动态分配：进程运行过程中动态申请设备资源

设备分配步骤：

1. 根据进程请求的逻辑设备名查找系统设备表SDT(注：用户编程时提供的逻辑设备名其实就是设备类型)

2. 查找系统设备表SDT，找到用户进程指定类型的、并且空闲的设备，将其分配给该进程。操作系统在逻辑设备表(LUT)中新增一个表项。

3. 根据通道控制表DCT找到控制器控制表COCT，若控制器忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配给进程

4. 根据控制器控制表COCT找到设备控制表CHCT，若通道忙碌则将进程PCB挂到通道等待队列中，不忙碌则将通道分配给进程。

逻辑设备表(LUT)建立了逻辑设备名与物理设备名之间的映射关系。

设备分配程序为用户进程分配设备的过程通常是

1. 先分配设备
2. 再分配设备控制器
3. 最后分配通道

• 设备分配主要先来先服务、优先级高者优先、短任务优先等等算法
• 设备分配策略与I/O设备的固有属性、系统所采用的分配策略、系统分配中的安全性、设备的无关性有关。
  • I/O设备的固有属性：该设备仅适合于某进程独占，还是可供多个进程共享
  • 系统所采用的分配策略：采用先请求先分配方式，还是按优先级数最高者优先的方式
  • 系统分配中的安全性：不合理的设备分配，有可能导致死锁的发生
  • 设备的无关性：

5.6、缓冲区管理

缓冲区是一个存储区域，一般情况下，更多的是利用内存作为缓冲区

1. 单缓冲：采用单缓冲策略，处理一块数据平均耗时Max(C, T)+M

   • T：将块设备输入到缓冲区时间
   • C：缓冲区到用户工作区时间
   • M：工作区处理数据时间

2. 双缓冲：采用双缓冲策略，处理一个数据块的平均耗时为Max (T, C+M)

若两台主机只设置单缓冲区，在任意时刻只能实现数据的单向传输。为了实现双向传输，我们可以给两台机器配置双缓冲区，其中一个缓冲区用来暂存即将发送的数据，另一个缓冲区用于接收输入的数据。

当缓冲区数据非空时，不能往缓冲区冲入数据，只能从缓冲区把数据传出；当缓冲区为空时，可以往缓冲区冲入数据，但必须把缓冲区充满以后，才能从缓冲区把数据传出

• 缓冲区是为了缓和CPU和外部设备速度不匹配的矛盾，提高CPU和外部设备工作的并行性

• 缓冲技术中的缓冲池是在主存中，文件系统中的交换区是在外存中

• 缓冲区管理者需要考虑的重要问题是同步问题，因为缓冲区是一种临界资源

5.7、磁盘

一片磁盘就是一个盘面，盘面上一圈就是磁道，每个磁道分为若干扇区，每个扇区就是一个磁盘块，各个扇区存放的数据量相同。

• 最内侧磁道上的扇区面积最小，因此数据密度最大。

可用（柱面号，盘面号，扇区号）来定位任意一个“磁盘块”，可根据该地址读取一个“块”：

1. 根据“柱面号”移动磁臂，让磁头指向指定柱面
2. 激活指定盘面对应的磁头
3. 磁盘旋转的过程中，指定的扇区会从磁头下面划过，这样就完成了对指定扇区的读/写

按照磁头是否可以移动分为：

• 磁头可以移动的称为活动头磁盘。磁臂可以来回伸缩来带动磁头定位磁道
• 磁头不可移动的称为固定头磁盘。这种磁盘中每个磁道有一个磁头

按照盘片是否可更换分为：

• 盘片可以更换的称为可换盘磁盘
• 盘片不可更换的称为固定盘磁盘

根据柱面号大小的优先级来进行调度，柱面号最大的最先调度

5.8、磁盘读/写操作时间

**寻找时间（寻道时间）**T_S：在读/写数据前，将磁头移动到指定磁道所花的时间。

1. 启动磁头臂是需要时间的。假设耗时为s
2. 移动磁头也是需要时间的。假设磁头均匀移动，每跨越一个磁道耗时为m，总共需要跨越n条磁道

则寻道时间：T_s = s + m×n

延迟时间T_R：通过旋转磁盘，使磁头定位到目标扇区所需要的时间。设磁盘转速为r（单位：转/秒，或转/分），则平均所需的延迟时间T_R=(1/2)×(1/r)=1/2r

• 1/r就是转一圈需要的时间。找到目标扇区平均需要转半圈，因此再乘以1/2

传输时间T_t：从磁盘读出或向磁盘写入数据所经历的时间，假设磁盘转速为r，此次读/写的字节数为b，每个磁道上的字节数为N。则：传输时间T_t=(1/r)×(b/N)=b(rN)

• 每个磁道要可存N字节的数据，因此b字节的数据需要b/N个磁道才能存储。而读/写一个磁道所需的时间刚好又是转一圈所需要的时间1/r

则总的平均存取时间T_a = T_s + 1/2r +b/(rN)

• 延迟时间和传输时间都与磁盘转速相关，且为线性相关。而转速是硬件的固有属性，因此操作系统也无法优化延迟时间和传输时间。
  • 采用交替编号的策略减少延迟时间
  • 采用错位命名的策略减少延迟时间
• 但是操作系统的磁盘调度算法会直接影响寻道时间

5.9、磁盘调度算法

1. 先来先服务算法(FCFS)：根据进程请求访问磁盘的先后顺序进行调度。

   • 优点：公平；如果请求访问的磁道比较集中的话，算法性能还算过的去
   • 缺点：如果有大量进程竞争使用磁盘，请求访问的磁道很分散，则FCFS在性能上很差，寻道时间长。

2. 最短寻找时间优先(SSTF)：SSTF算法会优先处理的磁道是与当前磁头最近的磁道。可以保证每次的寻道时间最短，但是并不能保证总的寻道时间最短。

   • 优点：性能较好，平均寻道时间短
   • 缺点：可能产生“饥饿”现象

3. 扫描算法：磁头有可能在一个小区域内来回来去地移动。为了防止这个问题，可以规定，只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移动。这就是扫描算法（SCAN）的思想。由于磁头移动的方式很像电梯，因此也叫电梯算法。

   • 优点：性能较好，平均寻道时间较短，不会产生饥饿现象
   • 缺点：
     • 只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了184号磁道的访问请求之后就不需要再往右移动磁头了。
     • SCAN算法对于各个位置磁道的响应频率不平均

4. LOOK调度算法：如果在磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向。（边移动边观察，因此叫LOOK）

   • 优点：比起SCAN算法来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间进
     一步缩短

5. 循环扫描算法(C-SCAN)：SCAN算法对于各个位置磁道的响应频率不平均，而C-SCAN算法就是为了解决这个问题。规定只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至起始端而不处理任何请求。

   • 优点：比起SCAN来，对于各个位置磁道的响应频率很平均。

     缺点：只有到达最边上的磁道时才能改变磁头移动方向，比起SCAN算法来，平均寻道时间更长。

6. C-LOOK算法：C-SCAN算法的主要缺点是只有到达最边上的磁道时才能改变磁头移动方向，并且磁头返回时不一定需要返回到最边缘的磁道上。C-LOOK算法就是为了解决这个问题。如果磁头移动的方向上已经没有磁道访问请求了，就可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置即可。

5.10、固态硬盘