操作系统预习笔记

操作系统概述

操作系统

1. 概念：操作系统是控制和管理计算机硬件和软件资源、合理地组织和管理计算机的工作流程以方便用户使用的程序的集合 。
2. 地位：位于硬件（裸机）之上，所有其他（应用）软件之下。它是对硬件系统功能的首次扩充（虚拟机）。

操作系统发展史

1. 串行处理（真空管）
2. 脱机批处理（晶体管）
3. 多道批处理（集成电路）
4. 个人计算机（大规模集成电路）

现代操作系统的特征

1. 并发：指两个或者多个事件在同一时间间隔内发生，是宏观上的并行和微观上的串行。
2. 共享：系统中软硬件资源不再为某个用户（程序）独占，而是可供多个程序共同使用。
3. 虚拟：指将一个物理实体变为若干逻辑单元。
4. 不确定性：也称为并发程序的异步执行性，主要指程序的执行过程存在高度动态的特征，从而可能引发执行结果的不确定，操作系统必须有效解决这一问题。

操作系统的分类

1. 分时系统：独立性，同时性，及时性，交互性。
2. 实时系统：响应速度快，可靠性和安全性高。
3. 主要区别

操作系统内核结构

微内核

• 内核保持尽量小，只实现操作系统的基本功能，而将更多功能放在内核之外运行，各模块之间通过消息进行通讯。
• 特点：内核简单，安全可靠，可移植性好。

单内核

• 内核容纳更多的功能，分为若干个模块，模块间的通信通过调用其它模块中的函数实现（直接调用）。
• 特点：执行效率高，但可移植性相对减弱。

混合内核

• 单内核和微内核的结合，取长补短，为大多数商业操作系统采用。

作业管理和用户接口

用户接口类型

1. 作业控制级接口——面向人
   1. 命令驱动
   2. 图形化驱动
2. 程序级接口——面向应用程序
   • 系统功能调用

系统功能调用

程序的管态和算态

1. 操作系统运行的状态称为管态（系统态， 核心态）
2. 用户程序运行的状态称为算态（用户态， 目态）

指令类型

1. 特权指令：一类只能在管态下执行而不能在算态下执行的特殊指令。
2. 访管指令：引发访管中断的指令，运行在算态。
3. 广义指令：操作系统提供的每一个子功能（系统调用程序）被抽象成的一个系统调用命令。

访管指令本身不是特权指令，它会引发访管中断，进而进入系统态执行系统调用（广义指令），在系统调用程序中可能会嵌入特权指令。

系统调用

概念：系统调用是指用户在程序中调用操作系统提供的一些子功能，是用户在程序级请求操作系统服务的一种手段。

过程

一般的过程调用和系统调用的区别

作业管理

作业

1. 脱机作业：用户不直接和计算机系统交互，其执行过程由操作员辅助完成。
2. 联机作业：用户在作业执行过程中可直接和计算机系统交互（人机对话），控制执行的过程。
3. 处理过程：输入、注册、调度、终止。

作业的输入/输出

1. 脱机输入/输出（人工干预）：输入输出机可以并行工作。
2. 联机输入/输出
3. SPOOLing系统（外围设备同时联机操作）
   • 兼具脱机和联机方式的优点， 可以实现联机方式下的主机和外围设备的同时工作，又称为假脱机，也即以联机的方式得到脱机的效果。
   • 将一台物理 I/O 设备虚拟出多个 I/O 设备，通过缓冲区来实现多设备的并行工作。

作业注册

作业控制块（JCB）

1. 标识信息
2. 状态信息
3. 调度参数

作业调度

1. 单道批处理系统作业调度

   1. 先来先服务调度算法（FCFS, First Come First Served）
   2. 最短作业优先调度算法（SJF, Shortest Job First）
   3. 最高响应比优先调度算法（HRP, Highest Ratio Priority）
      1. 响应比即优先级
      2. 响应比：作业响应时间 / 作业运行时间
         • 即 (作业等待时间 + 作业运行时间) / 作业运行时间
         • 即 1 + (作业等待时间 / 作业运行时间)

2. 多道批处理系统作业调度算法

   1. 一次可以选择多个作业同时执行（并发）。
   2. 优先级调度算法
   3. 均衡调度算法：分类和轮流服务。

3. 性能分析

   1. CPU 利用率
   2. 吞吐量：单位时间内CPU完成作业的数量。（SJF 擅长）
   3. 周转时间：$T_i=T_\text{完成}-T_\text{提交}$
   4. 周转系数：$W_i=\frac{T_i}{T_\text{执行}}$
   5. 平均周转时间：$T=\frac{T_1+T_2+\cdots+T_n}{n}=\frac{1}{n}\sum_{i=1}^{n}T_i$
   6. 平均周转系数：$W=\frac{W_1+W_2+\cdots+W_n}{n}=\frac{1}{n}\sum_{i=1}^{n}W_i$

进程管理

进程

1. 进程是程序的一次执行，该进程可与其它进程并发执行；它 是一个动态的实体，是资源的基本分配单元。

2. 与程序的区别和联系

   1. 区别

      1. 程序是静态的，是有序代码的集合；进程是动态的，是程序的一次执行。

      2. 程序的永久的，没有生命周期，可长久保存；进程是暂时的，有生命周期，是一个动态不断变化的过程。

      3. 进程是操作系统资源分配和保护的基本单位；程序没有此功能。

      4. 进程与程序的结构不同。

   2. 联系

      1. 通过多次执行，一个程序可对应多个进程；
      2. 通过调用关系，一个进程可包括多个程序。

3. 组成（内存映像）

   • PCB
   • 程序
   • 数据
   • 工作区

进程控制块（PCB）

1. 定义：是操作系统用来记录进程详细状态和相关信息的基本数据结构，它和进程是一一对应的，是进程存在的唯一标识。

2. 作用

   1. 提供进程的各种信息，以便操作系统查询、控制和管理。
   2. 进程的档案，描述进程的特征，记载进程的历史，决定进程的命运。

3. 结构

   1. 标识信息：唯一的标识一个进程，主要包含进程标识、用户标识、父进程标识。
   2. 现场信息：记录进程使用处理器时的各种现场信息。主要有 CPU 通用寄存器的内容、CPU 状态寄存器内容及栈指针等信息。
   3. 控制信息：操作系统对进程进行调度管理时用到的信息，主要有进程状态、调度信息、数据结构信息、队列指针、位置信息、通信信息、特权信息、存储信息等。

4. 进程控制块PCB在内存中是以表的形式存在的，操作系统对PCB进行集中统一的管理，所有的 PCB 集中在一个固定的存储空间上，形成了PCB表。PCB之间是以双向链式队列的形式关联的。

进程的产生与消失

1. 进程的产生
   1. 系统初始化
   2. 用户执行程序（命令，双击）
   3. 程序启动程序（子进程）
   4. 批处理系统：作业初始化
2. 进程的消失
   1. 寿终：运行结束而退出
   2. 自杀：因错误而自行终止
   3. 他杀：被其他进程/用户强行终止
   4. 处决：因异常而被系统强行终结

进程的执行与控制

1. 进程的基本状态及其转换

2. 进程控制
   • 系统对进程的控制和管理是通过操作系统内核中的原语实现的。

进程调度

1. 交互式系统（分时系统）下的调度策略
   1. 时间片轮转法（RR, Round Robin）
   2. 优先级调度算法：为系统中的每个进程规定一个优先数，就绪队列中具有最高优先数的进程有优先获得处理机的权利；如果几个进程的优先数相同，可则对它们实行 RR 调度策略。
   3. 多级反馈队列调度算法
      • 系统中维持多个不同优先级的就绪队列，每个就绪队列具有不同长度的时间片。
      • 优先级高的就绪队列里的进程，获得的时间片短；优先级低的就绪队列里的进程，获得的时间片长。
      • 新进程进入时加入优先级最高的就绪队列的末尾。

进程间的相互作用

1. 两种相互作用

   1. 同步：进程之间相互合作、协同工作的关系称为进程的同步。（直接制约）

   2. 互斥：多个进程因为争夺临界资源而相互排斥执行的过程。（间接制约）

      • 临界资源：也称独占资源，是指 在一段时间内只允许一个进程访问的资源。
      • 临界区：使用临界资源的程序段。

2. 实现同步与互斥

   1. 加锁法
   2. 信号量和 P、V 操作
      1. 信号量
         1. 公用信号量：用于进程间的互斥，初值通常为 1；
         2. 私有信号量：用于进程间的同步，初值通常为 0 或 n。
      2. P 操作：请求分配一个单位的资源。
      3. V 操作：释放/增加一个单位的资源。
   3. 管程
      1. 关于共享资源的一组数据结构和在这组数据结构上的一组相关操作。
      2. 工作原理
         1. 条件变量（c）
         2. wait(c)
         3. signal(c)

进程通信

1. 共享内存
2. 消息传递
3. 共享文件模式：管道（pipe）

死锁

死锁产生的必要条件

1. 互斥使用（资源独占）
2. 非剥夺控制（不可强占）
3. 零散请求
4. 循环等待

死锁的解决策略

1. 置之不理法：鸵鸟政策
2. 事后处理法：让死锁发生，事后处理
3. 积极防御法：不让死锁发生

死锁的预防

即破坏必要条件。

死锁的避免

允许死锁产生的条件存在。

安全状态：在这种状态下，存在一种资源分配顺序，使得所有进程顺利完成。

1. 单银行家算法：满足最大需求后释放所有资源。
2. 多银行家算法：多个资源的单银行家算法。
   1. sum 向量：系统资源总量
   2. allocation 向量：当前系统已分配资源
   3. available 向量：系统剩余资源
   4. sum(i)：第 i 个进程资源需求总量
   5. allocation(i)：第 i 个进程已分配资源总量
   6. claim(i)：第 i 个资源仍需申请资源数

死锁的检测和解除

资源分配图

两类资源

1. 永久性资源

   1. 圆（椭圆）表示一个进程。
   2. 方块表示一个资源类，其中的圆点表示该类型资源中的单个资源。
   3. 从资源指向进程的箭头表示资源被分配给了这个进程。
   4. 从进程指向资源的箭头表示进程申请一个这类资源。

2. 临时性资源

   1. 圆（椭圆）表示一个进程。
   2. 方块表示一个资源类，其中的圆点表示该类型资源中的单个资源。
   3. 由进程指向资源的箭头表示该进程申请这种资源，一个箭头只表示申请一个资源。
   4. 由资源类指向进程的箭头表示该进程产生这种资源，一个箭头可表示产生一到多个资源，每个资源类至少有一个生产者进程。

化简

对于临时性资源，如果其生产者进程不被阻塞，就可以认为其数量是无穷的。

从那些没有阻塞的进程入手，删除那些没有阻塞的进程的请求边，并使资源类中资源数（黑点的数目）减 1，删至直到图中不存在无阻塞的进程。

如果图中仍有请求边且无法再化简，则系统死锁。

死锁的解除

1. 重新启动
2. 撤消进程
3. 剥夺资源
4. 进程回退

存储管理

程序的转化过程

1. 链接
   1. 静态链接
   2. 装入时动态链接
   3. 运行时动态链接
2. 程序的装入（涉及到地址重定位）
   1. 绝对装入（Absolute loading）/ 固定地址再定位
   2. 可重定位装入（Relocatable Loading）/ 静态重定位
   3. 运行时重定位 / 动态重定位

分区存储管理方案

• 内碎片：指占用分区之内未被利用的空间。
• 外碎片：指占用的分区之间难以利用的狭小空闲分区。

连续分配方式

1. 单一连续分区管理：内存中一次只能装入一个用户程序，程序独占整个用户区。
2. 固定分区管理
   1. 优点：内存的利用率提高了；可以支持多道程序。
   2. 缺点：存在内碎片，造成存储空间的浪费；分区总数固定，限制了并发执行的程序数目。
3. 动态分区管理（可变分区）

分区分配算法

1. 最先（首次）适应算法（first-fit）：顺序查找

   • 倾向于使用内存中低地址部分的空闲分区，在高地址部分的空闲分区很少被利用，从而保留了高地址部分的大空闲区，可为以后到达的大作业分配大的内存空间创造了条件。

   • 缺点：低址部分不断被划分，留下许多难以利用、很小的空闲区（外碎片），而每次查找又都从低址部分开始，会增加查找的开销。

2. 邻近（下次/循环）适应算法（next-fit）：从最近处顺序查找

   • 能使空闲中的内存分区分布得更加均匀，但将会缺乏大的空闲分区。

3. 最佳适应算法（best-fit）：按从小到大顺序

   • 在存储器中将留下许多难以利用的小空闲区（外碎片）。每次分配后必须重新排序，这也带来了一定的开销。

4. 最坏适应算法（worst-fit）：按从大到小顺序

   • 克服了最佳适应算法留下的许多小的碎片的不足，但保留大的空闲区的可能性减小了。

分区释放方式：相邻合并，否则插入。

离散分配方式

页式存储管理：等分内存空间

页表：记录每一个作业的页号到页框号（实页号）之间的映射关系。

1. 优点
   1. 程序不必连续存放
   2. 没有外碎片
2. 缺点
   1. 程序要一次全部装入内存
   2. 页表体积庞大，维护麻烦
   3. 依然存在内碎片（大小平均为半个页面）
3. 局限性
   1. 不便于实现共享
   2. 一个程序只有一个虚拟地址空间

段式存储管理：按逻辑分段

1. 优点
   1. 程序不必连续存放
   2. 没有内碎片
   3. 程序尺寸几乎不受限制
   4. 便于实现共享
   5. 段表很小（段数量很少）
2. 缺点
   1. 作业要一次全部装入内存（至少一个段要全部加载到连续内存）
   2. 存在外碎片

段页式存储管理

结合了页式和段式，段里存页。

为了获得一条指令或者数据，需要访问内存三次（访问表两次，访问物理地址一次）。

内存扩充技术

1. 覆盖技术（Overlay）（作业内部，对程序结构有影响）
2. 交换技术（Swapping）（作业之间，对程序结构无影响）

虚拟页式存储技术

工作原理

页面淘汰算法

1. 先进先出页面淘汰算法（FIFO）
   • 可用页面数增大，缺页率反而升高（Belady 现象）。
2. 最近最少使用页面淘汰算法（LRU, Least Recently Used）
   • 无 Belady 现象。

颠簸 / 抖动

1. 页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象称为颠簸或抖动。

2. 原因

   1. 页面淘汰算法不合理。
   2. 分配给进程的物理页面数太少。

3. 解决办法

   1. 给定更合适的页面淘汰算法（不一定奏效）
   2. 分配给个更多的物理内存页面（一般会有效果，而且效果较好，但给多了并发度就会降低）
   3. 较好的方法是使用工作集机制处理。

工作集

• 常驻集：实际给进程分配的内存页面的集合。

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

• 活跃页面：在某段时间间隔里，进程频繁访问的页面。

文件管理

文件的结构

逻辑结构

1. 是用户所观察到的文件内容组织形式，它独立于物理存储设备。
2. 分类
   1. 有结构的文件（关系导向型结构）
   2. 无结构的文件（非关系导向型结构）

物理结构

1. 物理存储方式
   1. 连续存储（顺序结构）
   2. 链接结构
   3. 索引结构
2. 索引表的组织方式
   1. 链接文件方式：将多个索引表块按链接文件的方式串联起来。
   2. 多重索引方式：将一个大文件的所有索引表的地址放在另一个索引表中。（UNIX 三级索引）
   3. Hash 文件：采用计算寻址结构，它由主文件和溢出文件组成。

文件的目录

1. 文件的目录结构

   1. 一级目录结构
   2. 二级目录结构
   3. 多级目录结构（UNIX树形）

2. 文件的查找——线性检索法

文件共享

1. 硬链接
   • 不能链接目录、无法跨文件系统
   • 会增加链接计数
2. 软链接（符号链接）
   • 可链接目录、可跨文件系统甚至网络
   • 不会增加链接计数

文件的操作

打开文件机构

1. 内存文件控制块（内存索引节点）
2. 系统打开文件控制块
   • 用于记录所有打开文件的控制信息。
3. 用户打开文件表
   • 每一个进程可打开多个文件，都有一张打开文件表。

外存空间管理

外存空闲空间管理的数据结构通常称为磁盘分配表（Disk Allocation Table）。

空闲空间管理方法

1. 空闲区表
   • 其缺点是当外存中有大量的空闲区时，空闲区表会变得很大，分配效率降低。
2. 位示图
   • 大小由磁盘空间的大小（物理块数）决定，位示图的描述能力强，适应各种物理结构。
3. 空闲块链
   • 释放和分配都从链头处进行，主要问题是要修改几个有关的链接字，需要反复读写磁盘和分配物理块，系统开销大。
4. 成组链接法（UNIX）
   • 将空闲块分成若干组，每 100 个空闲块为一组。每组的第一个空闲块登记了下一组空闲块的物理盘块号和本组空闲块总数。
   • 专用块，空闲块索引表 filsys

磁盘调度

移臂调度

1. 先来先服务算法（FCFS, First Come First Served）
2. 最短寻道时间优先算法（SSF, Shortest Seek First）
   • 会发生「饥饿」现象。
3. 电梯调度算法（SCAN）

旋转调度

优先级：柱面 > 扇区 > 磁头

信息分布

设备管理

外设的分类

按数据组织方式分类

1. 块设备：指以数据块为单位来组织和传送数据信息的设备。属于有结构设备。
   1. 传输速率较高
   2. 可寻址
   3. 采用 DMA 方式控制
2. 字符设备：以单个字符为单位来传送数据信息的设备。
   1. 传输速率较低
   2. 不可寻址
   3. 常采用中断驱动方式

按数据传输率分类

1. 低速设备（Byte 级别）：键盘、鼠标
2. 中速设备（KB 级别）：打印机
3. 高速设备（MB 级别）：硬盘、磁带、光盘

I/O系统及结构

结构

1. 单总线结构
2. 多总线结构
3. 通道系统

控制方式

1. 程序控制 I/O（直接控制方式、可编程I/O模式）
   • 效率低下
2. 中断驱动 I/O
   • 数据仍然需要通过CPU进行传输，由于CPU每次处理的数据量少，因此这种方式只适于数据传输率较低的设备。
3. 直接存储访问 I/O（DMA, Direct Memory Access）
   • CPU只需干预I/O操作的开始和结束，而其中的数据读写无需CPU控制，适 于高速设备。
4. 通道控制方式 I/O
   • 一个CPU可以连接若干个通道，一个通道可以连接若干个控制器，一个控制器可以连接若干个设备。

I/O 软件

组成成分

1. I/O 交通管制程序
2. I/O 调度程序
3. I/O 设备处理程序

设计目标

设备独立、统一命名、错误处理、数据传输、缓冲管理、设备共享……

结构

1. 设备驱动程序：内核软件模块

   • 向上：接受来自与设备无关的上层软件的抽象请求；

   • 向下：进行与设备相关的操作。

2. 设备无关系统软件：负责实现对所有设备都具有共性的功能，并向上提供一个统一的接口。

3. 用户空间 I/O 软件：具有 I/O 功能但在用户态下运行的软件（函数）或功能模块。

具有通道的设备管理

1. 通道命令（Channel Command Word, CCW）：I/O 处理机的指令
2. 通道程序：用通道命令编写的程序
3. 通道地址字（Channel Address Word, CAW）：通道程序首地址的内存单元
4. 通道状态字（Channel Status Word, CSW）

缓冲技术

1. 设置目的
   1. 缓解缓冲两端设备（程序）速度的差异
   2. 协调数据大小的不一致性
   3. 实现应用程序 I/O 的语义拷贝
2. 分类
   1. 单缓冲（single buffer）：输出输出速率相差大时可用
   2. 双缓冲（double buffer）
   3. 环形缓冲
   4. 缓冲池（buffer pool）：可供多个进程共享的双向缓冲技术。
3. 缓冲管理队列
   1. 自由 buf 队列（FIFO）
   2. 设备 buf 队列
   3. NODEV 设备队列
4. 字符设备的缓存管理
   • 解决 CPU 与字符设备间速度不匹配的矛盾
   • 自由字符缓存队列：由空闲的字符缓存构成自由队列。
   • I/O 字符缓存队列

设备管理数据结构

1. 设备控制表（DCT）
2. 控制器控制表（COCT）
3. 通道控制表（CHCT）
4. 系统设备表（SDT）