操作系统原理知识知识点复习_梁光祥

2) 内核支持线程 3) 混合式线程 3. 线程有点

1) 用户级线程的切换速度高于支持内核线程的切换速度 2) 用户级线程可以在任何操纵系统上运行 3) 线程调度灵活

第三章 处理器调度与死锁

3.1．处理器调度

1. 定义

按一定的规则分配处理器

批处理作业：需要高级和低级调度 中断作业：低级调度 3. 作业

用户交给计算机所做的工作。由程序，数据和作业说明组成。 交换式作业又称终端作业或连击作业 批处理作业又称脱机作业 4. 选择调度算法的评判指标

（1） CPU的利用率 （2） 系统吞吐量

（3） 各类资源的平衡利用 （4） 周转时间 （5） 响应时间 （6） 截止时间 （7） 优先权原则 （8） 公平原则 5. 调度算法

（1） 先来先服务算法

调用后背队列中最先进入队列的一个或多个作业。属于非剥夺式调度。

特点：利于长作业，不利于短作业。简单易实现。效率低。只顾等待时间，不过执行时间。

（2） 短作业/短进程优先调度算法

调用运行时间短的作业，属于非剥夺式调度。 特点：

降低平均等待时间，提过系统吞吐量。 对长作业不利。

（3） 最高优先权调度算法

调度优先权高的作业，分为：

非抢占式：被调进程一直运行，直到结束或等待事件发生才主动放弃CPU。 抢占式：运行中的进程将CPU的使用权让给优先权高的

（4） 最高响应比算法

系统响应时间 作业等待时间+作业要求时间

6 / 16

R= =

作业要求运行时间 作业要求时间 属于非剥夺式调度。

（5） 时间片轮转调度算法

进程在规定的时间内没有结束，系统将产生一个中断。 属于剥夺式算法

（6） 最短剩余时间优先调度算法

短进程优先调度算法改造得到的剥夺式算法。

（7） 多级反馈队列调度算法

（1） 设置多个不同优先权队列，从上往下队列优先权依次降低。各队列时间

片不等。优先权越高，时间片越短。同一级进程，执行时间相同。

（2） 新进程进入队列时，首先排在第一个就绪队列队尾，按照先来先服务原

则等待调度。调度中，按时间片轮转调度算法执行。

（3） 仅当第一个就绪队列空闲时，才调用第二个就绪队列中进程执行。依次

类推。

（4） 执行中，按最高优先权剥夺式调度算法执行。

6. 实时调度

任务的空闲时间=任务的截止时间-任务剩余执行时间-当前时间 7. 进程切换

处理器模式切换：

（1） 保存中断进程的处理器现场 （2） 将处理器由用户态转向和心态 （3） 根据中断级别设置中断屏蔽位

（4） 根据系统调用号或中断号，调用相关处理程序。 进程切换模式：

（1） 保存CPU现场 （2） 修改PCB

（3） 给PCU挑选新进程

（4） 修改新进程PCB设置新进程地址空间，恢复存储管理信息

（5） 根据新进程PCB中保存的CPU环境，恢复CPU现场，执行新进程。

3.2．死锁

8. 死锁产生的必要条件

（1） 互斥条件

（2） 请求和保持条件 （3） 不剥夺条件 （4） 循环等待条件 9. 处理死锁的基本方法

预防：破坏4个必要条件

避免：分配资源前，进行安全性检查。 检测：根据资源分配图进行检测。 解除：

7 / 16

第四章 存储管理

4.1．程序的链接和装入

1.程序运行需经过的阶段 编译、链接和装入 2.物理地址和逻辑地址

逻辑地址空间：一个目标模块（程序）或装入模块（程序）的所有逻辑地址空间结合称为逻辑地址空间或相对地址空间

4. 将程序中的逻辑地址转换成机器能够直接寻址的物理地址，这种转换称为地址映射、地

址变换、重定位。

4.2．分区式存储管理

（1）单一连续存储管理

原理：内存空间分为系统区和用户区两部分，用户程序有装入程序从地地址开始装入，且一次只能装入一个程序。 （2）固定分区存储管理

原理：在单一连续存储管理基础上，将用户区划分成若干个固定大小的区域，系统允许同时装入多道程序进入内存使他们能够并行执行。 （3） 可变分区存储管理

1) 原理：程序装入前不建立分区，而是在程序运行时很据内存空间的需要而动态

建立。 2) 分配算法

a) 最先适应算法：有低地址找到能够满足程序要求的空闲分区。

b) 最佳适应算法：按空虚分区的长度从小到大组织空虚分区，然后从小的开

始寻找能够满足程序要求的空虚分区。

c) 最差适应算法：将内存中最大的分区分配给请求装入的程序。 3) 回收

4) 覆盖于交换技术

覆盖技术：程序内部的内存扩充技术

除了跟程序外，其余的所有程序有属于可覆盖程序。 交换技术：程序间的内存扩充技术

一般情况下，人们所说的交换是指进程交换。

4.3．分页式存储管理

采用离散分配内存的方式，基本单位时页面。 1) 原理

一个进程的逻辑地址空间分为若干个大小相等的区域，称为页。 并对进程的所有页面从0开始进行编号

物理地址空间也按同样的方法换分与页面长度相同的区域 内存地址的所有页框也从0依次进行编号

8 / 16

2) 页内碎片

由于最后一页往往不能装满物理块，于是会有一定的内存空间浪费现象，我们称为页内碎片。 3) 逻辑地址结构

31 12 11 0 页号 页内地址 由图可知：

每个页面大小是212=4K

地址空间最多允许有220=1M个页面 逻辑地址=页号X页长+页内地址

4) 地址变换

a) 地址变换机构自动将一维逻辑地址划分成页号和页内地址 b) 将页号和页表寄存器中的页长进行比较

若页号大于页表长度，系统产生中断

否则继续根据页表寄存器中页表在内存中的起始地址

c) 在找到的页表中找到对应的物理块号，从而形成物理地址。 5) 快表

一般允许存放32~1024个页表项 6) 两级页表

对一个大页表进行分页，分的的各个页面称为页表页面或页表分页

每个越帮越忙在外层表中有一个外层页表项，用来记录页表页面在内存中所存放的物理块的块号。

31 22 21 12 11 0

页内地址 页号 页号

4.4．分段式存储管理

1) 实现原理

将程序的逻辑地址划分才若干个子程序，每个子程序为一个段，每个段从0开始编址，一段为单位将程序存放于不相邻的内存空间。 2) 二位逻辑地址

31 24 23 0 页号 页号

每个段的长度：224=16M

一个作业最得多允许28=256个段

3) 段表 段号 段长 基址

4.5．段页式存储管理

9 / 16

1) 原理

将程序的逻辑地址分成若干个段，每个段分成若干个页。 2) 逻辑地址结构

31 24 23 12 11 0

段号 段内地址 页内地址 4.6．虚拟存储管理

1.虚拟存储管理的基本特征

1)离散性 2）多次行 3）部分装入 4）逻辑扩充 5) 交换性

2.虚拟存储器的大小由内存和外存容量之和决定。 3.请求分页虚拟存储管理

在分也是存储管理的基础上，增加了支持虚拟存器而形成的一种存储管理方式。 1) 页表结构 物理块修改位页号 中断位 外存地址 访问位 号号址 址 2) 分页式存储管理和请求分页式虚拟存储管理的区别 i. 页表机制不同 ii. 请求分页虚拟存储管理是在分也是存储管理的基础上，增加了支持虚拟存器而形成的

一种存储管理方式 iii. 地址变换机构不同

3) 缺页中断结构与中断的异同

相同点：有CPU保护现场环境、分析中断原因、转中断处理和CPU恢复现场等几个过

程

不同点：在却也中断结构中

中断的产生和处理时在指令执行期间

程序运行过程中，一条指令执行期间可能会产生多次中断。 4) 页面置换算法

A. 最佳置换算法

淘汰将来再也不访问或长时间不访问的页面； B. 先进先出置换算法

选择驻留主存时间最长的页面进行置换 C. 最近未使用置换算法

淘汰最近未使用的页面 具体分为： i. 最不经常使用

页面被访问时，计数器加1，淘汰页面时，选择计数器里面值最小的那个 ii. 最近没有使用

页面别访问时，访问位加1，系统在规定的时间将所有的访问位重新置0，淘

10 / 16