操作系统复习指导（ZML出品）

操作系统复习指导

[TOC]

第一章 操作系统引论

1.1操作系统目标、作用

操作系统目标：

• 方便性
  • 通过OS命令操纵计算机，方便用户
• 有效性
  • 提高系统资源的利用率
  • 提高系统吞吐量
• 可扩充性
  • OS必须具有很好的可扩充性
  • 与OS的结构有紧密的联系
• 开放性
  • 遵循世界标准规范。特别是开放系统互联OSI

操作系统作用：

• 用户与计算机硬件之间的接口
  • 命令方式（UNIX、DOS命令）
  • 系统调用方式（API）
  • GUI方式（Windows、LINUX）
• 计算机系统资源的管理者
  • CPU（处理机管理）
  • 内存（存储器管理）
  • I/O设备管理
  • 文件管理
• 实现对计算机资源的抽象
  • 裸机：无软件的计算机系统
  • 虚拟机：覆盖了软件的及其，向用户提供一个对硬件操作的抽象模型

1.2操作系统的基本特征

• 并发性
  • 并发：多个事件在同一时间间隔内发生
  • 并行：多个事件在同一时刻发生
  • 并发是并行的子集
• 共享：系统中的资源可供内存中多个并发执行的进程共同使用
  • 互斥共享方式（临界资源）
  • 同时共享方式（非临界资源）
• 虚拟性：把一个物理实体变为若干个逻辑上的对应物
  • 时分复用技术：虚拟处理机，虚拟设备
  • 空分复用技术：虚拟存储器
• 异步性：并发事件按照各自的速度向前推进，不会因为其他事件的阻塞而等待

1.3操作系统的功能

1. 处理机管理功能
   1. 进程控制：创建进程、撤销（终止）进程、状态转换
   2. 进程同步：信号量机制
   3. 进程通信：直接通信、间接通信
   4. 调度：处理机作业调度、处理机进程调度
2. 内存管理功能
   1. 内存分配和回收
      1. 内存分配
      2. 内存回收
   2. 内存保护：
      1. 确保每个用户程序仅在自己内存空间运行
      2. 绝不允许用户程序访问操作系统的程序和数据
   3. 地址映射：
      1. 逻辑地址转换为物理地址
   4. 内存扩充（虚拟存储技术）：
      1. 请求调入功能
      2. 置换功能
3. 设备管理功能：
   1. 完成I/O请求
   2. 提高CPU和I/O设备的利用率
4. 文件管理功能：
   1. 文件存储空间的管理
   2. 目录管理
      1. 按名存取
   3. 文件的读/写管理和保护
5. 操作系统与用户之间的接口：
   1. 用户接口：
      1. 联机用户接口：命令行，说一句指令，执行一句指令
      2. 脱机用户接口：批处理，说一堆指令，执行一堆指令
      3. 图形用户接口：GUI
   2. 程序接口：
      1. 系统调用：能完成特定功能的子程序
      2. 库函数
6. 现代OS的新功能：
   1. 系统安全：
      1. 认证技术、密码技术、访问控制技术、反病毒技术
   2. 网络功能和服务：
      1. 网络通信、资源管理、应用与操作
   3. 支持多媒体：
      1. 接纳控制技术、实时调度、多媒体文件的存储

1.4批处理系统、分时系统、实时系统的概念与特点

1.4.1批处理系统

概念： 在批处理系统中，用户所提交的作业都先存放在外存上并排成一个队列，称为“后备队列”。然后，由作业调度程序按一定的算法从后备队列中选择若干个作业调入内存，使它们共享CPU和系统中的各种资源。

特点：

• 多道： 在内存中同时存放多个作业，一个时刻只有一个作业运行，这些作业共享CPU和外部设备等资源。
• 成批： 用户和作业之间没有交互性。用户自己不能干预自己的作业的运行，发现作业错误不能及时改正。
• 批处理系统的目的是提高系统吞吐量和资源的利用率

1.4.2分时系统

概念： 分时系统是指，在一台主机上连接了多个带有显示器和键盘的终端，同时允许多个用户通过自己的终端，以交互方式使用计算机，共享主机中的资源。

特点：

• 同时性：计算机系统能被多个用户同时使用
• 独立性：用户和用户之间都是独立操作系统的，在同时操作时并不会发生冲突，破坏，混淆等现象
• 及时性：系统能以最快的速度将结果显示给用户；
• 交互作用性：用户能和电脑进行人机对话。

1.4.3实时系统

概念： 实时系统是指系统能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致的运行。

特点：

• 高精度计时系统：计时精度是影响实时性的一个重要因素。在实时应用系统中，经常需要精确确定实时地操作某个设备或执行某个任务，或精确的计算一个时间函数。这些不仅依赖于一些硬件提供的时钟精度，也依赖于实时操作系统实现的高精度计时功能。
• 多级中断机制：一个实时应用系统通常需要处理多种外部信息或事件，但处理的紧迫程度有轻重缓急之分。有的必须立即作出反应，有的则可以延后处理。因此，需要建立多级中断嵌套处理机制，以确保对紧迫程度较高的实时事件进行及时响应和处理。
• 实时调度机制：实时操作系统不仅要及时响应实时事件中断，同时也要及时调度运行实时任务。但是，处理机调度并不能随心所欲的进行，因为涉及到两个进程之间的切换，只能在确保“安全切换”的时间点上进行，实时调度机制包括两个方面，一是在调度策略和算法上保证优先调度实时任务；二是建立更多“安全切换”时间点，保证及时调度实时任务。

---

第二章 进程的描述与控制

2.1前趋图

首先了解程序顺序执行：

• 一个较大的程序通常由若干个程序段组成
• 程序在执行时，必须按照某种先后次序逐个执行，仅当前一个操作执行完毕后，才能执行后续操作

前趋图：

1. 是一个有向无循环图，用于描述进程之间执行的先后顺序。
2. 节点表示进程或者程序段，有向边表示前趋关系。

• 程序并发执行：采用多道程序技术，将多个程序同时装入内存，使之并发运行。

这时候前趋关系：

2.2进程的概念

• 进程是程序的一次执行
• 进程是一个程序及其数据在处理机上顺序执行所发生的活动
• 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位

2.3进程的特征

• 动态性（最基本的特征）：进程是一个动态的概念，进程的创建、撤销、切换、挂起、唤醒等都是动态的（声明周期）。
• 并发性：进程是并发执行的，多个进程可以同时在处理机上运行。
• 独立性：进程是一个独立的单位，拥有自己的地址空间，进程间相互独立，不会相互影响。
• 异步性：按各自独立的、不可预知的速度向前推进。

2.4进程与程序的区别

• 程序是静态的，进程是动态的
• 进程是程序的一个实例，是程序的一次执行
• 程序是进程的代码部分
• 进程在内存中，程序在外存中

2.5进程的三种基本状态以及转换

• 就绪状态：
  • 一个较大的程序通常都由若干个程序段组成
  • 程序在执行时，必须按照某种先后次序逐个执行，仅当迁移操作执行完毕后，才能执行后续操作
• 执行状态：已经获得CPU，正在执行的状态
  • 单处理机：一个进程处于执行状态
  • 多处理机：多个进程处于执行状态
• 阻塞状态
  • 正在执行的进程由于发生某事件而展示无法继续执行的状态
  • 典型事件：请求I/O、申请缓冲区、等待子进程结束、等待信号量等
  • 根据阻塞原因，设置多个阻塞队列，如：I/O阻塞队列、等待子进程结束阻塞队列、等待信号量阻塞队列等

三者的转换：

---

第三章 处理机调度与死锁

3.1高、中、低级调度的概念

调度其实就是对处理机进行一个分配。分配的目的是为了让进程尽快的执行完毕，从而提高系统的吞吐量。在处理机调度的时候可以分为三个级别：

• 高级调度（长程调度/作业调度）：
• 中级调度（中程调度/内存调度）：
• 低级调度（短程调度/进程调度）：

3.1.1高级调度

作业：是一个比程序更加广泛的一个概念。不仅包含了我们所讲的程序，还有数据，以及还配有一个作业说明书。

• 调度对象：作业
• 根据某种算法，决定将外存上处于后备队列中的作业调入内存，并为他们创建进程和分配必要的资源。然后将新线程排在就绪队列上等待调度。（把它从外存等待的一个状态取出来变成一个进程）
• 主要用于多道批处理系统中

3.1.2中级调度

• 调度对象：进程
• 作用：
  • 将暂不运行的进程，调至外存等待
  • 将处于外存上急需运行的进程，调入内存运行

3.1.3低级调度

• 调度对象：进程
• 根据某种调度算法，决定就绪队列中的哪个进程应获得处理机
• 应用与多道批处理、分时和实时OS中

3.1.4进程/作业调度的主要任务

进程/作业调度任务

• 保存处理机的现场信息
• 按照某种算法选取进程
• 把处理机分配给进程

• 排队器：用于将就绪进程插入相应的就绪队列
• 分派器：用于将选定的进程移除就绪队列
• 上下文切换器：进行新旧进程之间的上下文切换

3.2进程调度算法

• 先来先服务调度算法FCFS
• 短作业优先调度算法SJF
• 优先级调度算法PR
• 高响应比优先调度算法HRRN

FCFS、SJF、PR既可以用于作业调度，又可以用于进程调度

3.2.1先来先服务调度算法FCFS

按照作业到达的先后顺序来进行调度，哪个作业先来，那就先调度哪个作业。这种调度算法的优点是简单，缺点是不够公平，因为长作业会占用处理机的时间过长，而短作业则会一直等待。

3.2.2短作业优先调度算法SJF

SJF算法：既可以用于作业，也可以用于进程

• 对作业：从后备队列中选择若干个估计运行时间最短的作业
• 对进程：关联到每个进程下次运行CPU的区间长度，调度最短的进程

对于进程调度，SJF有两种模式

• 非抢占式SJF
• 抢占式SJF–抢占式发生在有比当前进程剩余时间片更短的进程到达是，当前进程会被抢占。也被叫做最短剩余时间优先调度。

对于一组指定的进程而言，SJF是最优的，因为它给出了最短平均等待时间。

SJF比FCFS算法有明显改进，但是也有缺点：

• 只能估算进程的运行时间（估值不准确）,所以通常用于作业调度
• 对于长作业不利
• 采用SJF算法时，人机无法实现交互
• 完全未考虑作业的紧迫程度

3.2.3优先级调度算法PR

PR算法：既可以用于作业，也可以用于进程

基于作业/进程的紧迫程度，由外部赋予作业相应的优先级，调度算法根据优先级进行调度

• 每个进程都有一个优先级，优先级为整数
• 默认：小的优先级数具有高优先级
• 目前主流的操作系统调度算法

高响应比优先调度算法是一种优先级调度算法，用于作业调度。

优先级调度算法的类型：

• 非抢占式
• 抢占式

优先级类型：

• 静态优先级：
  • 创建进程是确定优先级数（整数），在进程的整个运行期间保持不变
  • 简单易行，系统开销小
  • 不够精确，可能会出现优先级低的进程长期没有被调度的情况
• 动态优先级：
  • 创建进程时先赋予其一个优先级，然后其值随进程的推进或者等待时间的增加而改变。

优点：

• 实现简单，考虑了进程的紧迫程度
• 灵活，可以模拟其他算法

存在问题：

• 饥饿：低优先级的进程可能永远的不到执行

解决办法：

• 老化–视进程等待时间的延长提高其优先级数

3.2.4高响应优先比优先调度算法HRRN

HRRN算法：既可以用于作业，也可以用于进程

• 既考虑作业的等待时间，又考虑作业的运行时间
• 优先级：优先级=（等待时间+运行时间）/运行时间
• 响应比：响应比=（等待时间+运行时间）/运行时间=响应时间/运行时间
• 如果等待时间相同，运行时间越短，类似于SJF
• 如果运行时间相同，取决于等待时间，类似于FCFS
• 长作业可以随其等待时间的增加而提高其优先级，从而使其尽快得到调度
• 缺点：每次调度之前，都需要计算响应比，增加系统开销

3.3死锁

3.3.1死锁的概念

死锁：一组等待的进程，其中每一个进程都持有资源，并且等待着由这个组其他进程所持有的资源。

死锁是指多个进程在运行过程中因为争夺资源而造成的一种僵局，当进程处于这种僵持状态的时候，若无外力作业，这些进程将永远不会向前推进。

计算机中的资源问题：

• 可重用性资源和可消耗性资源：
  • 可重用性资源：一次只能分配给一个进程，不允许多个进程共享，遵循：请求资源–>使用资源–>释放资源(大部分资源)
  • 可消耗性资源：由进程动态创建和消耗（进程间通信的消息）
• 可抢占性与不可抢占性资源：
  • 可抢占性资源：某进程在获得这类资源后，该资源可以再被其他进程或者系统抢占，（比如CPU处理机和主存区）
  • 不可抢占资源：当系统把这类资源分配给某些进程后，再不能强行收回，只能在进程用完之后自行释放，（比如打印机，磁带机）

死锁原因：

• 竞争不可抢占性资源引起死锁：
  • 系统中的不可抢占性资源，由于他们的数量不能满足诸进程运行的需要，会使进程在运行过程中，因争夺这些资源而陷入僵局
• 竞争可消耗性资源引起死锁
• 进程推进顺序不放引起死锁
  • 进程推进顺序不当，会使进程在运行过程中，因争夺这些资源而陷入僵局

3.3.2死锁的必要条件

1. 互斥
   • 一段时间内某资源只能被一个进程占用
2. 请求和保持
   • 一个至少持有一个资源的进程等待获得额外的由其他进程所持有的资源
3. 不可抢占
   • 一个资源只有当持有它的进程使用完毕后才能被其他进程使用
4. 循环等待
   • 等待资源的进程之间存在环{p0,p1,p2,…,pn}，其中p0等待p1所占有的资源，p1等待p2所占有的资源，…，pn等待p0所占有的资源

3.3.3预防死锁

破坏死锁的四个必要条件中的一个或者几个

• 互斥：互斥条件是共享资源必须的，不仅不能改变，还应该加以保证
• 请求和保持：必须保证进程申请资源的时候没有占有其他资源
  • 要求进程在执行前一次性申请全部的资源，只有没有占有资源是才可以分配资源
  • 这样做法可能导致资源利用率低，可能出现饥饿现象
  • 改进：进程只获得运行初期所需的资源后，便开始运行；其后在运行过程中逐步释放已分配的且使用完毕的全部资源，然后在请求新资源。
• 非抢占：
  • 如果一个进程的申请没有实现，它要释放所占有的资源
  • 先占的资源放入进程等待资源列表中
  • 进程在重新得到旧的资源的时候可以重新开始
• 循环等待：对所有的资源类型排序，进行线性排序，并赋予不同的序号，要求进程按照递增顺序申请资源
  • 如何规定每种资源的序号是十分重要的
  • 限制新类型设备的增加
  • 作业使用资源的顺序与系统规定的顺序不同
  • 限制用户简单、自主的编程。

破坏死锁就是破坏死锁的四个必要条件中的一个或者几个

3.3.4避免死锁

死锁避免算法动态检查资源分配状态以确保不会出现循环等待的情况。

银行家算法：

针对资源有多个实例，每个进程必须事先声明使用的最大量，当一个进程请求资源，他可能要等待；当一个进程得到所有的资源，他必须在优先的时间释放这些资源。

3.3.5检测死锁与解除

资源分配图：

在资源分配图中，找出一个既不阻塞又非独立的进程节点Pi，在顺利的情况下，Pi可以获得所需资源而继续运行，直到运行完毕，再释放其所占的全部资源，这相当于想去Pi的所有请求边和分配边，使之成为一个孤立 的节点。

P1释放资源之后，便可以使P2获得资源继续运行，直到P2完成后又释放出它占有的所有全部资源。

在进行一系列的简化之后，若能消去途中所有的边，则称该图是可完全简化的；若不能通过任何过程使该图完全简化，则称该图是不可完全简化的。

---

第四章 进程同步

4.1临界资源

系统中某些资源一次只允许一个进程使用，我们把这样的资源叫做临界资源或者互斥资源或者共享变量

诸进程之间应该采取互斥的方式，来实现对这种资源的共享。

4.2临界区

临界区就是进程中设计临界资源的代码片段。

4.3进程同步机制应该遵循的准则

• 空闲让进
  • 当无进程处于临界区，应允许一个请求进入临界区的进程立即进入自己的临界区
• 忙则等待
  • 已有进程处于其临界区，其他试图进入临界区的进程必须等待
• 有限等待
  • 等待进入临界区的进程不能’死等’
• 让权等待
  • 不能进入临界区的进程，应释放CPU，以便其他进程进入临界区