操作系统小tips

操作系统小tips

进程管理

程序的并发执行

程序是描述计算机所要完成的具有特定功能的，并在时间上按严格次序前后相继的计算机操作序列集合(一个静态的概念)

程序顺序执行的特点：

1. 顺序性
2. 封闭性
3. 可再现性

程序在执行时应考虑的环境

1. 独立性
2. 随机性
3. 资源共享性

进程

并发执行的程序在执行过程中分配和管理资源的基本单位

特点：

1. 动态概念
2. 并发特征(程序没有)
3. 竞争计算机系统资源的基本单位
4. 不同的进程可以包含同一个程序

进程的组成：

进程控制块PCB：

信息	含义
状态	说明进程当前的状态
进程标识符	标明系统中各个进程
位置信息	指明程序及数据在主存或外存的位置
控制信息	参数、信 量、消息等
队列指针	连接统一状态的进程
优先级	进程调度的依据
现场保护区	将处理机的现场保护到该区域
其他

程序

数据

进程的状态

运行态、就绪态、阻塞态/等待态、新建态、退出态

进程切换

切换的时机

1. 时钟中断
2. I/O中断
3. 内存失效
4. 遇到陷阱
5. 系统调用

空->创建：新的批处理作业、交互登录、为提供服务而由操作系统创建、由现有进程派生

新建->就绪态：操作系统做好准备再接纳一批新进程时

就绪->运行态：需要选择一个新进程时

运行->就绪：正在运行的进程达到“允许不中断执行”的最大时间段、被优先级更高的进程抢占、进程自愿释放处理器(周期性的进程)

运行->阻塞：对于进程请求的服务，操作系统无法立即予以服务、请求一个无法得到的资源、需要进行初始化的时候、进程通信时，一个进程等待另一个进程的信息。从磁盘读数据时（可能）

阻塞->就绪：等待的时间发生时

一个读磁盘操作完成以后，操作系统会修改进程状态为就绪态

进程的创建

1. 由系统程序模块统一创建
2. 有父进程创建

用户登录成功后需要创建新进程
启动程序执行创建新进程

---

设备分配是通过在系统中设置相应的数据结构实现的，不必创建新进程。

进程的撤销

1. 该进程已完成所要求的功能而正常终止
2. 由于某种错误导致非正常终止
3. 祖先进程要求撤销某个子进程

进程的通信

主从式

1. 主进程可自由使用从进程的资源或数据
2. 从进程的动作受主进程的控制
3. 主进程和从进程的关系是固定的

会话式

1. 使用进程在服务进程所提供的服务之前，必须得到许可
2. 服务进程所提供的服务的控制由自身完成
3. 使用进程和服务进程在通信时有固定的链接关系

消息或邮箱机制

1. 只要存在空缓冲区或邮箱，发送进程就可以发送消息
2. 发送进程和接受进程无直接连接关系
3. 两进程之间存在缓冲区或邮箱

共享存储区方式

不要求数据移动

管道通信

类似于半双工
大小为内存上的一页

临界区

不允许多个并发进程交叉执行的一段程序
禁止两个进程同时进入临界区的准则：

1. 空闲让进
2. 忙则等待
3. 有限等待
4. 让权等待

实现互斥

软件方法

1. 单标志法
   违背空闲让进
2. 双标志法先检查
   违背忙则等待
3. 双标志法后检查
   导致互相谦让，谁也进不了临界区
   最终饥饿
4. Peterson算法
   代码语句中设置了turn
   无法实现让权等待

硬件实现方法

1. 中断屏蔽法
   限制了处理机交替执行程序的能力
2. 硬件指令法
   TestAndSet指令（原子操作）（不会主动放弃CPU，完成时会唤醒处于就绪态的进程，在开中断下运行）、Swap指令
   硬件方法不能实现让权等待

信 量

条件变量与信 量的比较

• 相同点
  条件变量的wait/signal操作类似于信 量的p/v操作，可实现进程的阻塞/唤醒
• 不同点
  条件变量是没有值的，仅实现了“排队等待”功能；而信 量是“有值”的，信 量的值反应了剩余资源数，而在管程中，剩余资源数用共享数据结构记录。

管程

代表共享资源的数据结构，以及由对该共享资源数据结构实施操作的一组过程所组成的资源管理程序。

实现共享资源封装
每次只允许一个进程进入管程

经典同步问题

生产者消费者问题

读者-写者问题

哲学家问题

死锁

死锁的原因

1. 系统资源的竞争
2. 进程推进顺序非法
3. 死锁产生的必要条件：

• 互斥条件
• 不剥夺条件
• 请求并保持条件
• 循环等待条件

死锁的预防

1. 破坏互斥条件
   不可行
2. 破坏不剥夺条件
   用于状态易于保存和恢复的资源 如CPU的寄存器及内存资源，不适用于打印机
3. 破坏请求并保持条件
   采用预先静态分配方法
   会导致饥饿
4. 破坏循环等待条件
   采用顺序资源分配算法
   限制了新设备的增加
   造成资源浪费
   给用户编程带来麻烦

死锁避免

1. 系统安全状态
2. 银行家算法

死锁的检测和排除

1. 资源分配图
2. 死锁定理
3. 死锁解除

• 资源剥夺法
• 撤销进程法
• 进程回退法

线程

线程是调度的基本单位
线程控制块TCB
用户级线程只可在用户空间中进行，所以在不支持内核级线程的系统中也可以实现管理。
用户级线程的切换效率更高。

典型应用

1. 服务器中的文件管理或通信控制
2. 前后台处理
3. 异步处理

多线程模型

多对一

多个用户映射到一个内核级线程，用户线程对操作系统不可见
多个线程不能并行运行在多处理机上

一对一

每个用户级线程映射到一个内核级线程
线程开销大

多对多

n个用户级映射到m个内核级线程上，要求m

中断技术

在程序执行过程中遇到急需处理的事件时，暂时中止现行程序在CPU上的执行，转而执行相应的事件处理程序，待处理完成后返回中断点或调用其他程序。

外中断（中断或者异步中断）

来自处理器之外的中断
分为可屏蔽中断和不可屏蔽中断
既发生在用户态又发生在内核态

1. 时钟中断
2. 键盘中断
3. 它机中断
4. 外部设备中断

内中断（异常或同步中断）

1. 访管中断->执行系统调用引起
2. 硬件故障中断->电源失效、奇偶校验错误、总线超时
3. 程序性异常->非法操作、地址越界、页面故障、调试指令、除数为零、浮点溢出
   大部分异常都发生在用户态，只有“缺页异常“发生在内核态

中断的执行过程

1. 关中断 此时不能响应更高级的中断请求
2. 保存断点 即PC
3. 引出中断服务程序 将地址送入PC
4. 保存现场和屏蔽字
5. 开中断 此时允许更高级的的中断
6. 执行中断服务程序
7. 关中断
8. 恢复现场和屏蔽字
9. 开中断、中断返回
   PC由硬件保存，通用寄存器由操作系统保存
   1～3由硬件（中断隐指令）完成，4～9 软件完成

中断事件处理

硬件故障中断

硬件故障导致

处理过程

1. 中断处理程序 保护现场
2. 停止设备工作
3. 停止处理及运行
4. 向操作员 告

程序性中断

语法错误、逻辑错误、运行中异常

处理过程

1. 因人而异
2. 借助于信 机制
3. 操作系统将中断事件捕获交给应用程序

I/O中断

处理原则

1. I/O正常结束 待传输的下一个进程设置为就绪态
2. I/O发生故障 向设备发命令索取状态字、分析故障的确切原因、复执或转人工
3. I/O异常 告操作员
4. 设备 到或设备结束 操作系统修改系统数据结构中相应设备的状态

访管中断

表示当前运行程序对操作系统功能的调用

处理过程

1. 程序执行访管指令,并通过适当方式指明系统调用 。
2. 通过中断机制进入访管中断处理程序,现场信息被保护到核心栈,按功能 实现跳转。
3. 通过系统调用人口地址表找到相应中断服务例程的入口地址。
4. 执行中断服务例程,正常情况下在结束后返回系统调用的下一条指令继续
   执行。

时钟中断

处理和时间有关的信息及决定是否程序调度
和时间有关的信息：系统时间、进程的时间片、延时、使用CPU的时间、各种定时器。
时钟分绝对时钟和间隔时钟

间隔定时器：

1. real 永远在计时（包括进程挂起时）
2. virtual 只在用户态计时
3. profile 在用户态和内核态都计时

系统调用

分类

• 设备管理
• 文件管理
• 进程管理
• 进程通信
• 内存管理

要运行在核心态

由内核程序负责完成
用户通过trap 来发起系统调用请求

用户态转向核心态

1. 用户程序要求操作系统的服务，如系统调用
2. 发生一次中断
3. 用户程序产生了一次错误状态
4. 用户程序企图执行一条特权指令
   用中断返回指令返回用户态

主要过程

1. 传递系统调用参数
2. 执行trap指令
3. 执行相应的服务程序
4. 返回用户态

大内核与微内核

大内核的好处

可充分利用模块之间有效特性，无可比拟的性能优势

微内核的特点

1. 添加系统服务时，不必修改内核
2. 有效分离接口
3. 微内核结构没有单一内核稳定

处理机调度

分级调度

1. 作业调度 又称宏观调度或者高级调度
2. 交换调度 又称中级调度或者内存调度
3. 进程调度 又称微观调度或者低级调度
4. 线程调度
   作业调度次数少，中级次数略多，进程调度频率最高
   进程调度和切换程序是操作系统内核程序

现代操作系统中,不能进行进程的调度与切换的情况有以下几种:1. 在处理中断的过程中,中断处理过程复杂,在实现上很难做到进程程切换,而且中断处理是系统工作的一部分,逻辑上不属于某一进程,不应被剥夺处理机资源。
2. 进程在操作系统内核程序临界区中。进入临界区后,需要独占式地访问共享数据,理论上必须加锁,以防止其他并行程序进入,在解锁前不应切换到其他进程运行,以加快该共享数据的释放。
3. 其他需要完全屏蔽中断的原子操作过程中。如加锁、解锁、中断现场保护、恢复等原子操作。在原子过程中,连中断都要屏蔽,更不应该进行进程调度与切换。

进程调度方式

• 非抢占（剥夺）式
• 抢占（剥夺）式

调度的基本准则

1. CPU利用率
2. 系统吞吐量 单位时间内CPU完成作业的数量 作业数量/时间
3. 周转时间
   周转时间=作业完成时间-作业提交时间
   平均周转时间=（作业1的周转时间+…+作业n的周转时间）/n
   带权周转时间=作业周转时间/作业实际运行时间
   平均带权周转时间=n个带权周转时间/n
4. 等待时间 进程处于等处理机状态的时间之和
5. 响应时间 用户提交到系统首次响应的时间

进程调度

功能

1. 记录系统中所有进程执行的的情况
2. 选择占有处理机的过程
3. 进行进程上下文的切换

进程调度的时机

1. 正在执行的进程执行完毕，或者进程被创建时
2. 执行中进程自己调用阻塞原语将自己阻塞起来，进入睡眠等待状态
3. 执行中进程提出IO请求后被阻塞
4. 在分时系统中时间片已经用完
5. 在执行完系统调用，系统程序返回用户程序时
6. 进程处于临界区时也可以调度
   以上是不可剥夺方式下的原因
7. 就绪队列中的某进程的优先级变得高于当前执行进程的优先级

UNIX中

1. 进程自己调用sleep和wait进入睡眠
2. 由于系统调用结束返回用户态，调度标志被置位
3. 完成中断或trap
4. 时间片用完
5. 调用exit自我终止

调度算法

先来先服务算法FIFS

算法简单效率低
对长作业有利对短作业不利
有利于CPU繁忙型作业，不利于IO繁忙型

短作业优先调度算法SJF

对于长作业不利
未考虑作业的紧迫程度
作业的长短根据用户的估计而定（不准）
SJF的平均等待时间、平均周转时间最少

优先级调度算法

1. 非剥夺式
2. 剥夺式
3. 静态优先级 创建进程时决定的
4. 动态优先级 进程运行过程中调整

优先级的设置参照原则

1. 系统进程>用户进程

2. 交互型进程 >非交互型进程

3. IO型进程 >计算型进程

高响应比优先调度算法

响应比Rp=（等待时间+要求服务时间）/要求服务时间
因此

1. 作业的等待时间相同时，要求服务时间越短，响应比越高，有利于短作业
2. 要求时间相同时，作业的响应比由其等待时间决定，（FCFS）
3. 对长作业，等待时间足够长时，其响应比便可升的很高

时间片轮转调度算法

适用于分时系统
剥夺式
当一个处于运行态的进程用完一个时间片后它的状态处于就绪态

多级反馈队列调度算法

1. 设置多个就绪队列，每个队列优先级不同
2. 每个队列中进程执行的时间片的大小各不相同
3. 队列中FCFS，队列间时间片轮转
4. 允许抢占

优势

1. 终端型作业用户：短作业优先
2. 短批处理作业用户：周转时间较短
3. 长批处理作业用户：不会长期得不到处理

实时调度

分为软实时调度和硬实时调度
实时操作系统的特点：

1. 有限等待时间（决定性）
2. 有限响应时长
3. 用户控制
4. 可靠性高
5. 系统出错处理能力强

要求：

1. 很快的进程或线程切换速度
2. 快速的外部中断响应能力
3. 基于优先级的随时抢占式调度策略：

• 优先级+时间片轮转调度
• 基于优先级的非抢占式调度
• 基于优先级的固定抢占式调度
• 基于优先级的随时抢占式调度

分类：

1. 静态表格法
   静态分析——直接产生调度结果
   多用于处理周期性任务
2. 静态优先级驱动抢占式调度算法
   也进行静态分析——不直接产生调度结果——只用来指定优先级
3. 动态计划调度算法
   在执行调度任务前排调度计划
4. 尽力而为调度算法
   不进行可能性分析

实现调度算法

所包涵的内容信息：

1. 任务就绪时间或事件到达时间
   周期性事件可预知，但非周期性事件大部分时间不可预知
2. 开始时限
3. 完成时限
4. 处理时间
5. 资源要求
6. 优先级

算法思想：按用户的时限要求顺序设置处理机
抢占式的
可用于非周期性任务调度

频率单调调度算法

广泛应用于多周期性实时处理
原理：
频率越低优先级越低

内存管理基本原理

功能

1. 虚拟存储器

进程中的目标代码、数据等的虚存地址组成的虚拟空间称为虚拟存储器

2. 地址变换

内存地址（物理单元）的集合成为内存空间或物理地址空间
物理地址空间是地址转换的最终地址

• 静态地址重定位
  要求执行前完成链接
  必须占用连续的内存空间
• 动态地址重定位
  依靠硬件地址变换机构
  该机构需要一个或多个基地址寄存器BR和一个或多个程序虚拟地址寄存器VR
  内存地址MA=BR+VR
  优点：

1. 可以对内存进行非连续分配
2. 提供了实现虚拟存储器的基础
3. 有利于程序段的共享

3. 内外存数据传输的控制

用户控制：覆盖
系统控制：交换、请求调入+预调入
一个进程正在IO时，不能交换出内存

4. 内存的分配与回收

连续分配方式

• 单一连续分配
  无外部碎片、可采用覆盖技术
  只能用于单用户、有内部碎片
• 固定分区分配
  多道
  分区大小相等。用于一台计算机控制多个相同对象
  分区大小不等。多个较小，适量中分区，少量大分区
  程序太大就放不进任何分区了
  内存利用率低，会产生内部碎片
  无外部碎片
  有关管理通过分区说明表进行
• 动态分区分配
  旗下的几种算法：

1. 首次适应算法
   空闲地址递增的顺序链接
   具有最佳性能
2. 最佳适应算法
   容量递增方式链接
3. 最坏适应算法
   容量递减方式链接
4. 邻近适应算法
   首次适应的演变，在上次查找的位置开始查找

5. 内存信息的共享与保护

常用的内存信息保护方法：

1. 上下界保护法（硬件）
2. 保护键法
3. 界限寄存器与CPU的用户态或核心态工作方式相结合

源程序转换为在内存中执行的程序步骤：

1. 编译
2. 链接 逻辑地址——>物理地址
3. 装入

程序链接的三种方式：

1. 静态链接
2. 装入时动态链接
3. 运行时动态链接

装入的的三种方法：

1. 绝对装入
2. 可重定位装入
3. 动态运行时装入

页式管理

为了减少碎片以及为了只在内存存放那些反复利用的或即将执行的程序段与数据部分，而把那些不经常执行的程序段和数据存储在外存。
不会产生外部碎片

名词

每个进程平均产生半个块大小的内部碎片（页内碎片）
进程的虚拟空间被划分为若干个等长的页（Page）
每个页1～4K（旧）
内存空间按页的大小分为片或页面/帧/框（Page framework）
外存也以同样的单位划分，成为块（block）

地址结构

分为两部分
页 P——页内偏移量W

页表

记录页面在内存中对应的物理块
一般存于内存中
页表由页表项
页表项的结构：页 ——物理内存中的块
页表项的第二部分与地址的第二部分共同组成物理地址
加入中断处理后的页表

页	页面	中断位	外存始址

| 页 | 页面 | 中断位 | 外存始址 |
加入改变位后的页表
| 页 | 页面 | 中断位 | 外存始址 | 改变位 |

计算过程

页 P=逻辑地址A/页面大小L
页内偏移量W=A%L
如果页 P>=页表长度M，产生越界中断
页表项地址=页表始址F+页 P页表项长度
页表长度一般指有多少页
页表项长度一般指页地址占多大的存储空间
物理地址E=块内内容b页面大小L+页内偏移量W
注：
页表项的确定：
n位逻辑地址空间对应的2^nB除以一页的大小mB
得到的u=2^n/m页，页表项以字节编址，因此页表项大于等于log(u)/8

快表

在地址转换机构中添加一个具有并行查找能力的高速缓冲存储器。

段式管理

分段

按进程中的自然段划分逻辑空间
其逻辑地址由段 s——段内偏移量w组成
段内连续，段间不要求连续

段表

| 段 | 段长 | 本段在主存中的地址 |
| 段 | 始址 | 长度 | 存取方式 | 内外 | 访问位 |

地址变换结构

• 逻辑地址A中前几位为段 S，后几位为段内偏移量W
• 比较段 S和段表长度M，if（S>=M）越界中断
• 段 S对应的段表项地址=段表始址F+段 S*段表项长度
• 取出段表中该段的始址b，计算物理地址E=b+W

段的共享与保护

都指向被共享的段的同一个物理副本。不能修改的代码成为纯代码或可重入代码（不属于临界资源）
保护方法一般有两种：

1. 存取控制
2. 地址越界保护

段业式管理

| 段