操作系统 期末复习

如你所见，这是一篇操作系统的期末复习篇.

话不多说,一起来看看吧

操作系统概述

操作系统是一组主管并控制计算机操作、运用和运行硬件、软件资源管理和提供公共服务来组织用户交互的相互关联的系统软件程序.同时也是计算机系统的内核与基石。操作系统需要处理如管理与配置内存、决定系统资源供需的优先次序、控制输入与输出设备、操作网络与管理文件系统等基本事务，也提供一个让用户和系统交互的操作界面.

特征

• 并发：是指两个或多个活动在同一给定的时间间隔中进行
• 共享：是指计算机系统中的资源被多个进程所共用
• 异步：进程以不可预知的速度向前推进
• 虚拟：把一个物理上的实体变为若干个逻辑上的对应物

两个最基本的特征：并发和共享.

并发和并行

并发：计算机在宏观过程中执行多个程序，在微观过程中只同时执行一个程序.

并行：计算机在同一时刻执行两个或多个程序

同一时间间隔为并发，同一时刻为并行.

虚拟

把硬件抽象出来，转换出来为一个或多个电脑配置环境，更好配置系统资源.

功能

• 处理机管理:进程控制、进程同步、进程通信、死锁处理、处理机调度等等
• 存储器管理:内存分配、地址映射、内存保护与共享、内存扩充等
• 文件管理:文件存储空间管理、目录管理、文件读写管理与保护
• 设备管理:缓冲管理、设备分配、设备处理、虚拟设备等

操作系统的主要功能包括处理机管理、存储管理、设备管理、文件管理、用户接口.

历程

概念

• 特权指令:不允许用户程序使用，只允许操作系统使用（如IO指令、中断指令）
• 非特权指令:普通的运算指令
• 内核程序:系统的管理者，可执行一切指令，运行在核心态
• 应用程序:普通用户程序只能执行非特权指令，运行在用户态
• 处于核心态的CPU可以执行除了“访管”指令外的所有指令，作用代表用户自愿进入核心态.

处理机状态

• 用户态（目态）:CPU只能执行非特权指令
• 核心态（又称管态、内核态）:可以执行所有命令
• 用户态到核心态：通过中断实现（由硬件完成）
• 核心态到用户态：特权指令psw的标志位，0为用户态，1为核心态
• 常考谁在用户态执行，谁在核心态执行

原语

• 处在操作系统的最底层，最接近硬件的部分
• 这些程序的运行具有原子性，其操作只能一气呵成
• 这些程序的运行时间都比较短，而且调用频繁

中断

内中断

异常，信号来自内部

• 自愿中断：指令中断
• 强迫中断：硬件中断、软件中断（例如除以0）

外中断

中断，信号来自外部

• 外设请求（如打印机等）
• 人工干预

系统调用

• 系统调用是操作系统提供给程序员（应用程序）获取操作系统服务的唯一接口。
• 在用户态发生，在核心态进行处理。

体系结构

• 大内核
• 微内核

进程管理

概念

进程是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配的基本单位，是操作系统结构的基础，是指计算机中已执行的程序，曾经是分时系统的基本运作单位。在面向进程设计的系统中，是程序的基本执行实体；在面向线程设计的系统中，进程是线程的容器.

理论角度上是对正在运行的程序过程的抽象，实现角度上是一种数据结构，目的在于清晰地刻画动态系统中的内在规律，有效管理和调度进入计算机系统主存储器运行的程序.

性质

• 动态性:实质上是程序在多道程序系统中的一次执行过程，是动态产生动态消亡的程序.
• 并发性:任何进程都可以同其他进程一起并发执行.
• 独立性:进程是一个能独立运行的基本单位，同时也是系统分配资源和调度的基本单位
• 异步性:由于进程间的相互制约，进程具有执行的间断性，进程各自按各自独立、不可预知的速度向前推进.
• 结构特征:PCB(进程控制)保存进程运行期间相关的数据，是进程存在的唯一标志；程序段是能被进程调度到CPU的代码；数据段用于存放数据

状态

• 运行态：进程正在占用CPU
• 就绪态：进程已处于准备运行状态，进程获得了除了处理机外的一切所需资源一旦得到处理机即可运行.
• 阻塞态：进程由于等待某一事件不能享用CPU
• 创建状态：进程正在被创建
• 结束状态：进程正在从系统消失
• 就绪态->运行态：处于就绪态的进程被调度后获得处理机资源（分派处理机时间片）
• 运行态->就绪态：时间片用完或在可剥夺系统中有更高级的进程进入
• 运行态->阻塞态：进程需要的某一资源还没有准备好
• 阻塞态->就绪态：进程等待的事件到来时

线程、进程、程序的区别

线程：线程是操作系统能够进行计算调度的最小单位，被包含在进程之中，是实际进行运算调度的最小单位.

进程：进程是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配的基本单位，是操作系统结构的基础，是指计算机中已执行的程序，曾经是分时系统的基本运作单位.

程序：程序是静态的、永久的、有序代码的集合.一个程序可对应多个进程，一个进程也可以包括多个程序.

调度

是对处理机进行分配，即从就绪队列中按照给定的算法（公平、高效）选择一个进程并将处理机分配给它运行，以实现进程并发地执行.

分类

• 高级调度（作业调度）
• 中级调度（内存置换）
• 低级调度（进程调度）

调度方式

剥夺式调度

非剥夺式调度

调度准则

• CPU利用率
• 系统吞吐量
• 周转时间
• 等待时间
• 响应时间

调度算法

调度概念

• 周转时间 = 完成时间 - 到达时间
• 带权周转时间 = 周转时间 / 运行时间
• 等待时间 = 周转时间 - 运行时间

先来先服务（FCFS）

非抢占式算法，在进程运行完成后进行调度.根据到达时间顺序进行调度,先来先服务.

缺点是会导致短作业周转时间较长.

短作业优先（SJF）

非抢占式算法，在进程运行完成后进行调度.优先调度已到达且运行时间最短的作业.

缺点是会导致长作业饥饿.

高响应比优先（HRRN）

非抢占式算法,每次调度时计算响应比（等待时间+运行时间/运行时间），选择最大响应比作业进行调度.响应比相同时优先调度短作业.

时间片轮转(Round-Robin)

抢占式算法，按照到达顺序轮流让各个进程执行一定时间片.

优先级调度算法

抢占式调度算法，每次调度时选择已到达且优先级最高的进程.优先级数字越大，优先级越高

多级反馈队列调度算法

根据优先级进行队列分类，在队列内部应用先来先服务算法.

时间片从上到下依次增大，优先级由上到下依次减小，新进程到达时先进入第一级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程仍然未结束，则进程进入下一级队列队尾；如果此时已经在最下级队列，则重新放回最下级队列队尾.

可以看成优先级、时间片等算法的综合体.

异步

进程各自以不可预知的速度向前推进.

临界区

• 保护共享资源
• 防止竞态条件
• 提高程序稳定性

实现依赖于同步机制，如互斥锁、信号量或条件变量。

互斥锁

一个线程进入临界区时，它会获取一个互斥锁；它退出临界区时

信号量

信号量是一种更通用的同步机制，可以用来控制多个进程对多个资源的访问.

条件变量

用于在多个线程之间传递信号.虽然条件变量本身不直接用于实现临界区，但它可以在线程等待进入临界区时提供有效的等待和唤醒机制.

临界区互斥

原则

• 空闲让进
• 忙则等待
• 有限等待
• 让权等待

基本方法

信号量利用PV操作实现互斥，可以使用操作系统提供的一对原语来进行操作实现进程互斥和进程同步.

PV操作

P操作主要动作

• S减1
• S减1后仍大于等于0，则进程继续执行
• S减1后小于0，则该进程被阻塞后放入该信号量的等待队列，然后转进程调度

V操作主要动作

• S加1
• S加1后仍大于0，则进程继续执行
• S加1后小于等于0，则从该信号的等待队列中释放一个等待进程，然后转进程调度

死锁

定义

多个进程因竞争资源而造成的一种僵局，如果没有外力这些进程将无法推进

产生原因

非剥夺资源的竞争和进程的不恰当推进顺序，至少两个任务中的每一个都等待另一个任务持有的锁的情况

解决方法

预防死锁

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

避免死锁

安全状态、银行家算法

检测死锁

利用死锁定理

解除死锁

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

计算公式

进程数小于资源数，则不会发生死锁的公式为：

1.最多申请资源数=资源总数/进程数（可以整除的条件下）

2.最多申请资源数=（资源总数/进程数）+1（不可以整除的条件下）

银行家算法

当一个进程申请使用资源的时候，银行家算法通过先试探分配给该进程资源，然后通过安全性算法判断分配后的系统是否处于安全状态，若不安全则试探分配作废，让该进程继续等待.

【题】在银行家算法中，出现了以下资源分配情况：

注：题中共四种资源，P0 的 Allocation 为（0，0，3，2）表示已分配给P0的第一种资源和第二种资源为0个，第三种资源 3 个，第四种资源 2 个.

1.该状态是否安全？

2.找到一个安全序列

3.若进程P2提出请求Request（1，2，2，2）后，系统能否将资源分配给它？

【解答】

1.安全

2.从p0开始，结束后变为1 6 5 4；满足P3的Need，结束后变为2 9 9 10；此后满足任意need，可以进行任意调度，参考安全序列为{P0，P3，P4，P1，P2}.

3.不能，分配完后剩余0 4 0 0，无法再找到一个符合条件的安全序列.

内存管理

目的

更好的支持多道程序的并发执行，提高系统性能

主要功能

（1）内存空间的分配与回收

（2）存储的保护和共享：保证各道作业在各自的存储空间内运行，互不干扰

（3）地址转换：在多道程序环境下，程序中的逻辑地址和内存中的物理地址不可能一致，因此存储管理必须提高地址变换功能，把逻辑地址转换成相应的物理地址.

（4）内存扩充：利用虚拟存储技术或自动覆盖技术，从逻辑上扩充内存.

用户程序的主要处理阶段

（1）编辑阶段：创建源文件

（2）编译阶段：由编译程序将用户源代码编译成若干目标模块，生成目标文件

（3）链接阶段：由链接程序将编译后形成的一组目标模块及所需的库函数链接到一起，形成一个完整的装入模块，生成可执行文件

（4）装入阶段：由装入程序将装入模块装入内存运行

（5）运行阶段：得到结果

程序的装入

绝对装入

在编译时如果知道程序将驻留在内存的什么位置，那么编译程序将产生绝对地址的目标代码，即按照物理内存的位置赋予实际的物理地址.

优点

在时间效率上很高

缺点

1. 由于内存大小限制，能装入内存并发执行的进程数大大减少
2. 编译程序必须知道内存当前的空闲地址部分和其地址，而在多通道程序下，编译程序根本不可能知道当前空闲地址的部分，因此绝对装入方式只适用于单道程序环境.

静态重定位

即在程序装入对目标代码装入内存的过程中完成，是指在程序开始运行前，程序中指令和数据的各个地址均已完成重定位，即完成虚拟地址到内存地址映射。地址变换通常是在装入时一次完成的，以后不再改变.

优点

不需要硬件支持

缺点

1. 静态重定位后不能在内存中搬动
2. 要求程序的内存空间连续

动态重定位

把地址转换推迟到程序真正要执行时才进行，但这种方式需要硬件支持，也就是重定位寄存器的支持，否则会影响指令的执行速度.

优点

可以解决碎片问题.

缺点

需要硬件支持.

程序的链接

静态链接

在程序运行之前先将各目标模块以及它们所需库函数链接为一个完整的可执行程序，之后不再拆开.

装入时链接

将用户源程序编译后得到的一组目标模块，在装入内存后采用边装入边链接的链接方式.

运行时链接

对某些目标模块的链接，是在程序执行中需要该目标模块时，才对它进行的链接.其优点是便于修改和更新，便于实现对目标模块的共享.

地址

逻辑地址

给人看的地址

物理地址

给计算机看的地址

内存空间的分配与回收

连续分配管理方式

• 单一连续分配：分配到内存固定的区域（单用户/单任务的操作系统），无外部碎片，有内部碎片
• 固定分区分配：分配到内存不同的固定区域，分区可以相等可以不等，但要求一定要是固定的。支持多道程序，内存用户空间分为若干个固定大小分区，每个分区装入一个作业
• 动态分区分配：
• （1）可变分区存储管理：按照程序的需要进行动态的划分
• （2）动态分区的分配策略算法：
• 首次适应：空闲分区以地址递增的次序链接。分配内存时顺序查找，找到一个大小能满足要求的一个空闲分区。
• 最佳适应：空闲分区按容量递增的方式形成分区链，找到第一个能满足要求的空闲分区。
• 最坏适应：空闲分区以容量递减的次序链接。找到第一个能满足要求的空闲分区，即挑选出最大的分区。
• 邻近适应：由首次适应算法演变而成。不同之处是，分配内存时从上次查找结束的位置开始继续查找。
• 无内部碎片，有外部碎片，外部碎片可用紧凑技术来解决（自动合并相邻碎片）

非连续分配管理方式

解决了动态分区、连续分区、单一分区中必须要连续分配的弊端，因为连续分配可能会出现那很多的外部碎片，导致空间不能够充分利用。

（1）基本分页式存储管理将内存空间分为一个个大小相等的分区（比如每个分区4KB），每个分区就是一个“页框”，或称“页帧”、“内存块”、“物理块”，每个页框有一个编号，即“页框号”；页框号从0开始。将用户进程的地址空间也分为与页框大小相等的一个个区域，称为“页”或“页面”。每个页面也有一个编号，即“页号”，页号也是从0开始。

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

快表查询

快表命中访问一次内存一次高速缓存，未命中访问两次内存一次高速缓存

文件系统

设备管理