第一章 操作系统引论

操作系统的概念

操作系统是配置在计算机硬件上的第一层软件, 是对硬件系统的首次扩充, 其主要作用是管理硬件设备, 提高它们的利用率和系统吞吐量, 并为用户和应用程序提供简单的接口, 以便于用户和应用程序使用硬件设备

操作系统的目标

操作系统的主要目标是实现:

  1. 方便性
  2. 有效性
  3. 开放性
  4. 可扩充性

操作系统的发展动力

  1. 不断提高计算机系统资源的利用率
  2. 方便用户
  3. 器件不断更新换代
  4. 计算机体系结构不断发展
  5. 不断提出新的应用需求

操作系统的发展过程

操作系统经历简单的批处理系统, 到多道批处理系统, 不久后推出分时系统和实时系统, 然后相继开发出微机OS, 多处理OS, 网格系统和分布式OS

操作系统的基本特性

操作系统具有并发, 共享, 虚拟, 异步这4个基本特性

  1. 并发: 一段时间内宏观有多个程序同时运行
  2. 共享: 系统中的资源可供内存中多个并发执行的进程共同使用
  3. 虚拟: 将一个物理实体分为诺干个逻辑上的对应功能
  4. 异步: 进程是以人们不可预知的速度向前推进的

操作系统的主要功能

  1. 处理机管理功能
  2. 存储器管理功能
  3. 设备管理功能
  4. 文件管理功能
  5. 接口管理功能

操作系统的结构

  1. 简单结构
  2. 模块化结构
  3. 分层式结构
  4. 微内核结构
  5. 外核结构

第二章 进程描述与控制

前趋图和程序执行

前趋图

根据前趋关系绘制前趋图

1

程序执行

①顺序执行：是把一个具有独立功能的程序独占处理机直至最终结束的过程称为程序的顺序执行

②并发执行：一组在逻辑上相互独立的程序或程序段在执行过程中其执行时间在客观上相互重叠，即一个程序尚未结束、另一个程序的执行已经开始的执行方式。

根据程序执行关系找出前趋关系

1

然后绘制出前趋图

image-20221103220655106

进程

进程定义

进程是程序的执行过程, 是系统进行资源分配和调度的一个独立单位

进程特征

进程的特征有:

  1. 动态性: 进程有一定的生命周期
  2. 并发性: 进程能并发执行
  3. 独立性: 进程是一个能独立运行、获取资源、接受调度的基本单位
  4. 异步性: 进程按照不可预知的速度向前推进

进程基本状态与转换

进程的三个基本状态:

  1. 就绪状态: 进程已处于准备好执行的状态
  2. 执行状态: 进程获得cpu后, 其程序”正在执行”这一状态
  3. 阻塞状态: 正在执行的进程由于某事件而暂时无法继续执行的状态

进程状态间的转换

image-20221103222006593

阻塞状态→ I/O完成→ 就绪状态

执行状态→ I/O请求→ 阻塞状态

执行状态→ 时间片完→ 就绪状态

就绪状态→ 时间片完→ 执行状态

进程挂起操作

当挂起操作作用于某个进程时，该进程将被挂起，意味着该进程此时处于静止状态。

如果进程正在执行，它将暂停执行；如果原本处于就绪状态，它将暂不接受调度。

与挂起对应的是激活操作

引入挂起后增加的进程状态的转换

活动就绪→ 挂起→ 静止就绪

活动阻塞→ 挂起→ 静止阻塞

静止就绪→ 激活→ 活动就绪

静止阻塞→ 激活→ 活动阻塞

进程控制块PCB

PCB定义

PCB是操作系统为进程定义的一种数据结构, 记录了操作系统用于进程描述当前状况以及管理进程运行状态的全部信息, 是操作系统最重要的记录型数据结构

PCB具体作用

pcb的作用时使一个在多道程序环境下不能独立运行的程序(含数据), 成为一个能独立运行的基本单位, 可进一步划分为

  1. 作为独立运行的基本单位
  2. 实现间断性运行方式
  3. 提高进程管理所需要的信息
  4. 提高进程调度所需要的信息
  5. 实现与其他进程的同步与通信

PCB中的信息

PCB主要包含下述4方面的信息

  1. 进程标识符
  2. 处理机状态
  3. 进程调度信息
  4. 进程控制信息

进程控制

进程控制包含

  1. 进程创建
  2. 进程终止
  3. 进程阻塞与唤醒
  4. 进程挂起与激活

进程创建

进程创建的步骤:

  1. 申请空白PCB
  2. 为新进程分配运行所需的资源
  3. 初始化PCB
  4. 判断是否能将进程插入就绪队列

进程终止

进程的终止过程

  1. 根据被终止进程的标识符, 检索出对应的PCB, 从PCB中读出该进程的状态
  2. 如果被终止的进程处于执行状态, 立即终止进程的执行
  3. 终止该进程的子孙进程
  4. 将被终止进程的资源释放
  5. 将被终止进程的PCB移除

进程的阻塞与唤醒,挂起与激活

引起进程阻塞与唤醒的事件

  1. 向系统请求共享资源失败
  2. 等待某种操作的完成
  3. 新数据尚未到达

**进程阻塞过程: **正在执行的进程发生阻塞事件，进程便会通过调用阻塞原语block将自己阻塞，阻塞是进程自身的一种主动行为

**进程唤醒过程: **当被阻塞进程所期待的事件发生时，有关进程就会调用唤醒原语wakeup以将等待该事件的进程唤醒

**挂起: **当系统中出现引发进程挂起的事件时，OS就会利用挂起原语suspend将指定进程或处于阻塞状态的进程挂起

**激活: **当系统中出现激活进程的事件时，OS就会利用激活原语active将指定进程激活

进程通信

指进程之间的信息交换，通常有低级和高级之分。

通信机制可归结为4类：

​ ①共享存储器系统

​ ②管道通信系统

​ ③消息传递系统

​ ④客户机-服务器系统

线程

线程是比进程更小的基本单位, 为了减少程序在并发执行时所付出的时空开销, 使得操作系统具有更好的并发性

线程与进程的区别

线程是具有传统进程所具有的很多特征，因此被称为轻型进程, 而传统进程称为重型进程,区别比较:

  1. 调度的基本单位：传统OS中，进程在被调度时上下文切换的开销较大；引入线程的OS中，切换代价小于进程
  2. 引入线程的OS中，不仅进程之间可以并发执行，同一进程中的多个线程也可以并发执行，甚至允许同一进程中的所有线程都能并发执行
  3. 进程可以拥有资源，并可作为系统中拥有资源的一个基本单位，而线程几乎不可以拥有资源
  4. 独立性：线程之间的独立性比进程之间的独立性低得多
  5. 系统开销: 创建（撤销）进程时, 线程的开销比进程的少
  6. 支持多处理机系统: 在多处理机系统中单线程进程只能运行在一个处理机上, 而多线程进程可以将它的多个线程分配到多个处理机上

线程状态

线程的三个基本状态(与进程的没有区别):

  1. 就绪状态: 线程已处于准备好执行的状态
  2. 执行状态: 线程获得cpu后, 其程序”正在执行”这一状态
  3. 阻塞状态: 正在执行的线程由于某事件而暂时无法继续执行的状态

线程控制块TCB

每个进程中都有一个PCB一样，系统为每个线程也配置了一个TCB

TCB中通常包含：

  1. 线程标识符
  2. 一组寄存器
  3. 线程执行状态
  4. 优先级
  5. 线程专有存储区
  6. 信号屏蔽
  7. 堆栈指针

线程的实现方式

  1. 内核支持线程: 内核支持线程的创建、阻塞、撤销和切换都是在内核空间实现的；
  2. 用户级线程：用户级线程是在用户空间中实现的，其对线程的创建、撤销、同步与通信等功能都无须内核支持，即用户级线程与内核无关

第三章 处理机调度与死锁

处理机调度的层次

处理机调度的层次有三种:

  1. 进程调度: 是低级调度, 调度的对象是进程, 是最基本的一种调度
  2. 内存调度: 是中级调度, 引入目的是提高内存利用率和系统吞吐量
  3. 作业调度: 是高级调度, 它的调度对象是作业, 多用于多道批处理系统

处理机调度算法

  1. 先来先服务调度算法
  2. 短作业优先调度算法
  3. 优先级调度算法（非抢占式、抢占式）
  4. 高响应比优先调度算法
  5. 轮转调度算法
  6. 多级队列调度算法
  7. 多级反馈队列调度算法
  8. 适用于实时系统中最早截止时间优先算法
  9. 最低松弛度优先算法

周转时间、平均周转时间、带权周转时间、平均带权周转时间计算

先来先服务调度算法FCFS

按照作业到达的先后顺序(作业提交时间)进行处理

例题:

image-20221104213757438

image-20221104214011794

  1. 按照先来先服务, 最先到达的最先执行, 因此作业1在提交后立即执行, 作业1的完成时间是提交时间+运行时间=9.0simage-20221104214144517
  2. 因为是单道批处理系统, 一段时间只能由一个作业执行, 因此即使作业2在8.5s时提交, 也只能在作业1完成后, 也就是9.0s时开始运行image-20221104214352413
  3. 同理, 按照提交时间的先后顺序, 作业3要在作业2完成后开始运行, 作业4要在作业3完成后开始运行image-20221104214753813
  4. 计算周转时间, 周转时间=作业的完成时间-提交时间, 也就是进程从进来到离开一共花费多少时间如作业3的周转时间=9.7-9.0=0.7s, 平均周转时间就ysjx了image-20221104215155050
  5. 计算带权周转时间, 带权周转时间=周转时间/运行时间, 如作业4的带权周转时间为0.7/0.1=7.0s, 带权平均周转时间也ysjximage-20221104215602507

短作业优先调度算法SJF

按照作业的长短(比较作业的运行时间)排序进行处理

例题:

image-20221104213757438

image-20221104214011794

  1. 在8.0s时刻, 只有作业1到达, 因此作业1进行调度image-20221104214144517

  2. 作业1执行完成后处于9.0s时刻, 此时已经由两个作业提交了, 分别是提交时间为8.5s的作业2和提交时间为9.0s的作业3, 它们的提交时间均小于作业1完成时间因此提交成功, 而作业3的运行时间比作业2短, 根据短作业优先调度, 对作业3进行调度image-20221104220800288

  3. 作业3调度完成后处于9.2s时刻, 此时作业4的提交时间为9.1s, 作业4提交成功, 这时候比较作业2和作业4的运行时间, 作业4运行时间短, 根据短作业优先调度, 作业4先进行调度, 作业2最后调度image-20221104221303228

  4. 周转时间和带权周转时间是一样的算法, 详细看先来先服务那里

    ​ 周转时间=作业的完成时间-提交时间

    ​ 带权周转时间=周转时间/运行时间

优先级调度算法

优先级进程调度算法，是把处理机分配给就绪中优先级最高的进程。这时又可进一步把该算法分成如下两种。

  1. 非抢占式优先级调度算法
  2. 抢占式优先级调度算法
非抢占式优先级调度算法

调度过程：正在处理的进程处理结束，接下来每次调度时选择当前已到达且优先级最高的进程

例题:

image-20221104222752486

下面求进程到达顺序就行, 相信周转时间完成时间带权周转时间对我已经有手就行了

  1. 0时刻(P1): 只有P1到达, P1上处理机
  2. 7时刻(P2、P3，P4):P1运行完成主动放弃处理机, 其余进程都已到达, P3优先级最高, P3上处理机
  3. 8时刻(P2、P4):P3完成，P2P4优先级相同，由于P2先到达，因此P2优先上处理机

进程到达时间图示:

image-20221104223325314

抢占式优先级调度算法

调度过程：每次调度时选择当前已到达且优先级最高的进程. 进程会主动放弃处理机时发生调度, 就是在运行进程的过程中，放弃当前进行，去进行优先级高的进程

例题:

image-20221104222752486

下面求进程到达顺序就行, 相信周转时间完成时间带权周转时间对我已经有手就行了

  1. 0时刻(P1): 只有P1到达, P1上处理机
  2. 2时刻(P2): P2到达就绪队列, 优先级比P1更高, 发生抢占. P1回到就绪队列, P2上处理机
  3. 4时刻(P1、P3): P3到达, 优先级比P2更高, P2回到就绪队列, P3抢占处理机
  4. 5时刻(P1、P2、P4): P3完成，主动释放处理机，同时，P4也到达, 由于P2比P4更先进入就绪队列，因此选择P2上处理机
  5. 7时刻(P1、P4): P2完成，就绪队列只剩P1、P4, P4上处理机
  6. 11时刻(P1): P4完成, P1上处理机
  7. 16时刻(): P1完成, 所有进程均完成

进程到达时间图示:

image-20221104223535976

高响应比优先调度算法HRRN

如果题目说”要求服务时间”, 记住这就是运行时间

按优先权(等待时间和运行时间的比率)顺序进行调度

等待时间 = 上一个进程的完成时间 - 本进程的提交时间

优先权 = (运行时间+等待时间)/运行时间

​ = 1 + (等待时间/运行时间)

例题:

image-20221104213757438

image-20221104214011794

  1. 8.0s时刻只有作业1到达, 作业1进行调度image-20221104214144517

  2. 9.0s时刻有作业2和作业3到达, 作业2的优先权= 1+[(9.0-8.5)/0.5 = 2, 作业3的优先权= 1+(9.0-9.0/0.2) = 1, 作业2的优先权大于作业1的优先权, 因此作业2优先调度image-20221104231044987

  3. 9.5s时刻有作业3和作业4到达, 作业3的优先权= 1+[(9.5-9.0)/0.2] = 3.5, 作业4的优先权= 1+[(9.5-9.1)/0.1] = 5, 作业4优先权大于作业3, 因此作业四优先调度image-20221104231521756

  4. 周转时间和带权周转时间是一样的算法, 详细看先来先服务那里

    ​ 周转时间=作业的完成时间-提交时间

    ​ 带权周转时间=周转时间/运行时间

轮转调度算法RR

时间片轮转算法, 自己不知道该怎么解释, 就挂两个b站视频(讲的真的非常通俗易懂)

顺便再感慨以下b站为受众如此窄的用户(程序员)开发了视频分析的嵌入式代码功能

进程到达时间相同

视频链接

进程到达时间不同

视频链接

如果进程的运行时间全部小于时间片长度, 那么算法就会退化为先来先服务FCFS

直接按先来先服务处理就行

死锁

死锁的概念

有两个进程P1和P2, P1占用资源R1想获得资源R2, P2占用资源R2想获得资源R1, 像这样几个进程都因为不能获得自己所需资源, 而继续运行而无法释放自己当下占有的资源, 且一直处于这样的僵持状态, 就形成了死锁

死锁产生的必要条件：

  1. 互斥条件
  2. 请求和保持条件
  3. 不可抢占条件
  4. 循环等待条件

死锁的处理方法

  1. 预防死锁：通过设置某些限制条件，破坏产生死锁的条件；
  2. 避免死锁：在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而避免死锁
  3. 允许进程发生死锁，但可以通过检测机构及时地检测出死锁，然后采取适当措施把进程从死锁中解脱
  4. 解除死锁：当检测到系统中已发生死锁时就采取相应措施将进程从死锁状态中解脱出来

安全状态

系统能按某种进程推进顺序，为每个进程Pi分配其所需的资源，直至满足每个进程对资源的最大需求，进而使每个进程都可顺利完成的一种系统状态

银行家算法

银行家算法中有下面几个类型的数组, 表示各类资源的数量

下面假设计算机中有四类资源A B C D

Max: 最大需求数

表示一个进程运行时所需各类资源的最大需求数

P1的Max为(0 0 1 2),

表示P1运行所需的A类最大资源数为0, B类最大资源数为0, C类最大资源数为1, D类最大资源数为2

MAX
进程 A B C D
P1 0 0 1 2
P2 1 7 5 0
P3 2 3 5 6
P4 0 6 5 2
P5 0 6 5 6

这张表格里的信息为

进程P1对ABCD四类资源的最大需求数分别为0 0 1 2

进程P2对ABCD四类资源的最大需求数分别为1 7 5 0

进程P3对ABCD四类资源的最大需求数分别为2 3 5 6

进程P4对ABCD四类资源的最大需求数分别为0 6 5 2

进程P5对ABCD四类资源的最大需求数分别为0 6 5 6

Allocation: 已占有(分配)资源

表示进程目前已经占有的资源

P2的Allocation为(1 0 0 0),

表示P1目前占有A类资源数为1, B类资源数为0, C类资源数为0, D类资源数为0

MAX Allocation
进程 A B C D A B C D
P1 0 0 1 2 0 0 1 2
P2 1 7 5 0 1 0 0 0
P3 2 3 5 6 1 3 5 4
P4 0 6 5 2 0 6 3 2
P5 0 6 5 6 0 0 1 4

这张表里的信息为(举例)

进程P4已占有的ABCD四类资源的数分别为0 6 3 2

Need: 还需要的资源

表示支持进程运行完成, 还需要的各类资源数

P1的Need(0 0 0 0)表示: P1为了运行完成还需要A类资源0个, B类资源0个, C类资源0个, D类资源0个,

支持进程运行完成还需要的资源数 = 进程运行时所需各类资源的最大需求数 - 进程目前已经占有的资源

即 Need = Max - Allocation

根据上面的表我们可以计算出各个进程的Need向量

MAX Allocation Need
进程 A B C D A B C D A B C D
P1 0 0 1 2 0 0 1 2 0 0 0 0
P2 1 7 5 0 1 0 0 0 0 7 5 0
P3 2 3 5 6 1 3 5 4 1 0 0 2
P4 0 6 5 2 0 6 3 2 0 0 2 0
P5 0 6 5 6 0 0 1 4 0 6 4 2

Available: 计算机中各类资源剩余数

表示计算机(不是各个进程)目前剩余的各类资源数

Available(1 5 2 0)表示: 系统剩余A类资源1个, B类资源5个, C类资源2个, D类资源1个

Available题目中一般有两种途径求得

  1. 题目直接给你几个Available向量, 让你判断这几个Available向量下系统是否安全
  2. 题目会先给出系统总共对着四类资源的拥有量Resource向量, 需要通过计算机中**各类资源剩余数 = 系统对四类资源的拥有量 - 以分配给进程的各类资源量之和, **即 Available = Resource - Allocation中各进程资源和

假设当前系统有A B C D四种资源, 资源拥有量分别为A类3个, B类14个, C类12个, D类12个

Allocation
进程 A B C D
P1 0 0 1 2
P2 1 0 0 0
P3 1 3 5 4
P4 0 6 3 2
P5 0 0 1 4

可以计算:

A类资源已分配数为 P2的1个+ P3的1个 = 2个

B类资源已分配数为 P3的3个+ P4的6个 = 9个

C类资源已分配数为 P1的1个+ P3的5个 +P4的3个 + P5的1个= 10个

D类资源已分配数为 P1的2个+ P3的4个 + P4的2个 + P5的4个 = 12个

通过Available = Resource - Allocation中各进程资源和计算得

当前系统资源剩余数Available为(1 5 2 0)

安全序列求法

引入Work与Work+Allocation

工作向量Word就是在调度进程过程中, 系统持有的剩余资源量

Work+Allocation就是进程结束,并释放掉自己被分配的资源Allocation后, 系统资源拥有量

以上一节的系统资源剩余数Available为(1 5 2 0)为例

将工作向量初始值置为系统资源剩余量Available

当前工作向量Work(1 5 2 0)

将Word与各个进程运行完成还需要的资源Need进行对比

只要有一个进程满足Need<Work说明该进程可以运行完成, 此时在此进程的Word向量处进行填写

如: P1的Need为(0 0 0 0), P1进程的运行完成所需的资源量小于系统拥有的资源量, 依次可以运行

如果没有任何进程满足Work>Need, 则说明系统此时不存在一个安全队列

Work Allocation Need Work+Allocation
进程 A B C D A B C D A B C D A B C D
P1 1 5 2 0 0 0 1 2 0 0 0 0
P2 1 0 0 0 0 7 5 0
P3 1 3 5 4 1 0 0 2
P4 0 6 3 2 0 0 2 0
P5 0 0 1 4 0 6 4 2
计算满足Work>Need的进程运行完成时, 系统的剩余资源量Work+Allocation

进程运行完成后会释放资源, 此时系统的剩余资源量会扩大为工作向量+该进程分配资源量

如P1运行结束后, Work+Allocation为(1 5 3 2), 运行完成后, 设置Finish向量为Ture, 说明进程执行完成

Work Allocation Need Work+Allocation Finish
进程 A B C D A B C D A B C D A B C D
P1 1 5 2 0 0 0 1 2 0 0 0 0 1 5 3 2 True
P2 1 0 0 0 0 7 5 0
P3 1 3 5 4 1 0 0 2
P4 0 6 3 2 0 0 2 0
P5 0 0 1 4 0 6 4 2
将上一个进程的Work+Allocation复制给下一个进程的Work向量, 继续寻找满足Work>Need的进程(重复第四步)

如此时P4进程满足Work>Need, 填写P4的Work向量, 计算P4的Work+Allocation向量

Work Allocation Need Work+Allocation Finish
进程 A B C D A B C D A B C D A B C D
P1 1 5 2 0 0 0 1 2 0 0 0 0 1 5 3 2 True
P2 1 0 0 0 0 7 5 0
P3 1 3 5 4 1 0 0 2
P4 1 5 3 2 0 6 3 2 0 0 2 0 1 11 6 4 True
P5 0 0 1 4 0 6 4 2
就这样一直循环, 直到所有进程执行完成

并且按照Finish向量赋值为True的时间先后顺序, 找出进程完成的先后顺序列

这个列就是系统的安全序列, 只要找到任一安全序列, 系统就是安全的

当一个进程请求资源时, 求是否能满足请求

如果进程P2提出一个Request(0 4 2 0) ,表示进程P2提出需要A类资源0个, B类资源4个, C类资源2个, D类资源0个, 问是否满足请求(资源分配情况如下)

MAX Allocation Need
进程 A B C D A B C D A B C D
P1 0 0 1 2 0 0 1 2 0 0 0 0
P2 1 7 5 0 1 0 0 0 0 7 5 0
P3 2 3 5 6 1 3 5 4 1 0 0 2
P4 0 6 5 2 0 6 3 2 0 0 2 0
P5 0 6 5 6 0 0 1 4 0 6 4 2

懒得算了,自己意会吧

判断请求的资源量是否≤进程运行完成还需要的资源量

一个进程请求的资源量不能大于运行完成还需要的资源量

即判断 Request ≤ Need, 如果成立则进行下一步

判断请求的资源量是否≤系统剩余的资源量

一个进程请求的资源量不能大于系统剩余的资源量

即判断 Request ≤ Available, 如果成立说明进程的请求能够被满足

满足进程的请求后

进程运行完成还需要的资源量 Need = Need - Request

系统剩余的资源量 Available = Available - Request

第四章 进程同步

进程同步概念

我们把异步环境下一组并发进程, 因直接制约而互相发送消息, 互相合作, 互相等待, 使得各进程按照一定速度执行的过程, 成为进程同步

临界资源

进程在使用时需要采用互斥方式, 一次只允许一个进程使用的资源

实现进程同步的机制

实现进程同步的机制分为软件同步机制和硬件同步机制量大类

其中硬件同步机制又可划分为

  1. 关中断: 在进入锁测试之前, 闭关中断, 知道完成锁测试并上锁之后, 才能打开中断
  2. 利用Test-and-set指令实现互斥: 借助硬件TS来实现互斥
  3. 利用Swap指令实现进程互斥: 利用swap指令, 交换两个字的内容

信号量机制

信号量机制分为

  1. 整型信号量: 只有一个表示资源的数量的整形量S，wait操作只要信号量S≤0，就会不断测试
  2. 记录型信号量: 增加了一个进程的链表指针List用于记录等待的进程
  3. AND型信号量: 将进程在整个运行过程中所需要的所有资源, 一次性全部分配给进程, 待进程使用完后再一起释放
  4. 信号量集: 对AND型信号量机制加以扩充，即针对进程所申请的所有资源以及每类资源不同的需求量，在一次wait(S)或signal(S)操作中完成它们的申请或释放

管程机制

管程是一个资源管理模块, 其中包含了共享资源的数据结构, 以及由对该共享数据结构实施操作的一组方法所组成的资源管理程序, 对临界资源的操作封装了起来, 管程由四部分组成

  1. 管程的名称
  2. 共享数据结构数目
  3. 对数据结构进行操作的一组过程
  4. 初始化语句

P, V操作

P操作(wait操作):

①P 操作一次，信号量 –

②如果 S ≥0 表示有资源，当前进程可执行

③如果 S＜0 无资源，则当前进程进入队列的队尾等待，等另一进程执行 V（S）操作后

释放资源。此时，|S| 绝对值表示等待资源进程的个数要求

V操作(signal操作)：

①V 操作一次，信号量 S++

②如果 S ＞ 0（有资源，告诉其它进程可以继读）

③如果 S ≤ 0（等待队列中另一进程释放资源后才能执行）,

生产者消费者

伪代码模板如下

semaphore 翻译就是 信号量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
semaphore mutex=1; //这个是信号量,理解为锁: P(mutex)表示上锁, V(mutex)表示解锁
semaphore empty=n; //缓冲池中空缓冲区的数量(empty个空位置)
semaphore full=0;  //缓冲池中满缓冲区的数量(生产了full个产品)

void produce(){
	while(true){
        P(empty);		//后面会生产产品所以把空位置减一,empty--
        P(mutex);		//上锁
        
         //生产了.....(根据题目自己编)
        
        //这两行代码表示生产了一个产品, 看书上例题貌似可以省略
        buffer[in] = nextp;		//放入生产的产品
        in = (in+1)%n;			//移动如队列的指针
        
        V(mutex); 		//解锁  
        V(full);		//生产完一个产品 产品数加一,full++
	}

}

void consumer(){
	while(true){
		P(full);		//后面会消费产品所以把生产产品数减一,full--
		P(mutex);		//加锁
		
        //消费了...(根据题目自己编)
        
        //这两行表示消费了一个产品, 看书上例题貌似可以省略
        nextc = buffer[out];	//取出消费的产品
        out = (out+1)%n;		//移动出队列的指针
        
		V(mutex);		//解锁
		V(empty); 		//消费了一个产品空位置加一,empty++
	}
}

empty和full的名称随题目自己命名

例题:

某银行提供了一个服务窗口和10个供顾客等待时使用的座位，顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许以为顾客使用，当营业员空闲时，通过较好选取一位顾客，并为其服务, 顾客和营业员的活动过程描述如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
Cobegin{
    Process顾客{
        从取号机上获得一个号码；
        等待叫号；
        获得服务；
    }
    Process  营业员{
        while（TRUE）{
            叫号；
            为顾客服务；
        }
    }
}coend

请添加必要的信号和p, v操作或wait(), signal()操作，实现上述过程中的互斥和同步，要求写出完整的过程，说明信号量的涵义并赋初值

解答:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Semaphore num=1,seats=10,custom=0;
//num是关于取号机互斥的信号量；seats是座位的个数；custom是顾客的个数。
Process 顾客{
    P(seats);
    P(num);		//上锁
    从取号机上获得一个号码；
    V(num);		//解锁
    V(custom);
    等待叫号；
    V(seats);
    获得服务；
    }
Process 营业员{
   	P(custom);	//为一个顾客进行服务
    叫号；
    为顾客服务；     
}

第五章 存储器管理

程序的装入与链接

要在系统中运行用户程序, 就必须先将其装入内存中, 然后将其转变为一个可执行的程序，需要3个步骤

  1. 编译：由编译程序对用户源程序进行编译，形成若干个目标模块
  2. 链接：由链接程序将编译后形成的一组目标模块以及它们所需要的库函数链接在一起，形成一个完整的装入模块
  3. 装入：由装入程序将装入模块装入内存

逻辑地址和物理地址

CPU生成的地址通常称为逻辑地址或相对地址，而内存单元看到的地址（即装入内存地址寄存器的地址），通常称为物理地址或绝对地址

程序装入方式

  1. 绝对装入方式：装入模块在内存中物理地址在程序中直接指出
  2. 可重定位装入方式（静态重定位）：装入时对目标程序中指令和数据的修改过程称为重定位, 地址便会通常是在装入时一次完成的，所以又称静态重定位
  3. 动态运行时装入方式（动态重定位）：装入程序把装入模块装入内存后，并不立即把装入模块中的相对地址转化为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行

程序链接

  1. 静态链接: 在程序运行之前，先将各目标模块及它们所需的库函数链接成一个完整的装配模块，以后不再拆开
  2. 装入时动态链接：指将用户源程序编译后所得的一组目标模块，在装入内存时，采用边装入边链接的链接方式
  3. 运行时动态链接：在执行过程中，当发现一个“被调用模块”尚未被装入内存时，立即由OS去找到该模块，将其装入内存，并链接到装入模块上

连续分配存储管理方式

连续分配存储管理方式可分为.单一连续分配、固定分区分配、动态分区划分、动态重定位分区分配, 而动态分区划分又可细分为:

  1. 顺序分配算法的首次适应算法, 循环首次适应算法, 最佳适应算法, 最坏适应算法
  2. 索引分配方式的快速适应算法, 伙伴系统, 哈希算法

离散存储管理方式

根据在离散分配时所分配地址空间的基本单位的不同，可将离散分配方式分为3种

  1. 分页存储管理方式: 将用户程序的地址空间分为若干个固定大小的区域称为页，也将内存空间分为块
  2. 分段存储管理方式: 把用户程序的地址空间分为若干个大小不同的段，每段可定义一组相对完整的信息
  3. 段页式存储管理方式: 分页和分段相结合使用

地址变换

image-20221106221406421

解题步骤:

  1. 转换二进制: 先将逻辑地址的16进制03b7(16)转换为2进制1110110111(2)
  2. 找出页号和页内地址: 每页大小为1KB, 即2^10, 所以转换为逻辑地址的后10位1110110111是页内地址, 而前几位则为页号
  3. 根据页号查找块号: 如页号为0的块号为0x1C
  4. 前几位页号直接换成块号, 页内地址不变,: 03b7的页号为0, 将页号换成块号1c(16),
  5. 将块号与页内地址进行拼接形成物理地址: 1c(16) -> 11100, 拼接后为111001110110111
  6. 物理地址转为16机制: 111001110110111(2) ->73b7(16)

如果求出的页号对应页表没有块号, 说明发生了缺页

如果求出的页号页号对应页表找不到这个页号, 说明发生越界中断

第六章 虚拟存储器

虚拟存储器的定义

是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统

虚拟存储器的特征

  1. 多次性: 允许程序和数据分成多次调入内存运行
  2. 对换性: 允许程序和数据在作业运行时进行换入、换出
  3. 虚拟性：指能够从逻辑上扩大内存容量,使用户所看到的内存容量远大于实际内存容量

虚拟存储器的实现方式

  1. 请求分页系统: 在分页系统的基础上，增加了请求调页功能和页面置换功能
  2. 请求分段系统: 在分段系统的基础上，增加了请求调段功能和分段置换功能
  3. 段页式虚拟存储系统: 段页式系统的基础上，增加请求调页和页面置换功能

请求分页系统的内存有效访问时间计算

抖动

抖动的定义

刚被淘汰出内存的页面，过后不久又要访问它，需要再次将其调入，而该页调入内存后不入又再次被淘汰出内存，然后又要访问它，如此反复，使得系统把大部分时间用在了页面的调进换出上，而几乎不能完成任何有效的工作，这种现象称为抖动

抖动产生原因

发生“抖动”的根本原因是，同时在系统中运行的进程太多，由此分配给每一个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时，频繁地出现缺页，必须请求系统将所缺之页调入内存

抖动预防措施

  1. 采取局部置换策略
  2. 把工作集算法融入处理机制度中
  3. 利用“L=S”准则调节缺页率
  4. 选择暂停的进程

下面是还没归纳的

试题类型

(1) 名词解释：进程、线程、临界资源、带权周转时间、静态重定位、动态重定位、死锁、页表、虚拟存储器。

(2) 简答题

A. 若信号量S的初值定义为5，则在S上调用了6次P操作和5次V操作后S的值应该为

B. 什么是进程控制块？包含哪些信息？

C. 解释可变分区连续内存分配中的首次适应算法或循环首次适应算法或最佳适应算法或最坏适应算法

(3) 应用题

A. 进程之间的关系如下图所示，试用P、V操作描述他们之间的同步

B．有以下两个程序段判断能否并发执行

c.系统有5个进程，它们的到达时间和服务时间给出表所示，如系统采用时间片轮转调度算法或短作业优先或先到先服务进程调度算法进程执行顺序图，并计算进程的周转时间和带权周转时间。

D一个请求分页系统中，若系统分配一个作业的物理块数给出，给出一个页面走向顺序序列，请给出采用最佳置换算法、先进先出置换算法、最近最久未使用置换算法的内存驻留各页面的变化情况、缺页次数、换页次数、以及缺页率。

E、已知某页式存储管理系统，内存大小为128KB，被分成64块，块号为0-63.设某进程有5页，页号0、1、2、3、4被分别装入主存的第6、9、16、3，10块。

（1）该进程大小是多少？

（2）写出该进程每一页在主存中的起始地址。

（2）若给出逻辑地址9872，计算出相应的内存物理地址