*** 作系统知识梳理

*** 作系统知识梳理 第一章 *** 作系统引论 *** 作系统主要目标

方便性，有效性，可扩充性，开放性

*** 作系统作用

1. 用户与计算机硬件系统之间的接口
2. 计算机系统资源的管理者
3. 计算机资源的抽象

*** 作系统的基本特性

1. 并发
   • 并发：两个或多个事件在同一时间间隔内发生，宏观上同时发生，微观上交替发生。 *** 作系统并发性指计算机系统同时运行着多个程序，宏观上同时发生，微观上交替发生
   • 并行：两个或多事件在同一时刻同时发生
2. 共享
   • 共享：资源共享，系统中的资源可供内存中多个并发执行的进程共同使用
   • 共享分为两种，互斥共享方式，同时共享方式
     • 互斥共享:系统内的资源可以提供给多个进程使用，但是一个时间段内只允许一个进程访问该资源
     • 同时共享：系统允许一个时间段内由多个进程同时对共享资源进行访问
   • 并发性和共享性互为存在条件
3. 虚拟
   • 是指把一个物理实体变为若干个逻辑上的对应物。物理实体是实际存在的，逻辑实体是用户感受到的
   • 虚拟技术
     • 空分复用技术（虚拟存储技术）
     • 时分复用技术（虚拟处理器技术）
4. 异步
   • 异步：在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的，而是走走停停，以不可知的速度向前推进，这就是进程异步性

---

第二章处理机管理 前趋图

前驱图：一个有向无循环图，用于表示进程之间的执行的先后顺序

进程同步

进程同步：让并发进程按要求有序推进

同步机制应遵守的规则

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

信号量机制 记录型信号量

//记录型信号量数据结构定义
typedef struct{
    //记录当前资源数目，初始值为最大值
    int value ;
    //记录访问该资源处于等待的进程链表
    struct process_control_block *list;
}semaphore;

//P *** 作
wait(semaphore *S){
   S->value--;
    if(S->value<0)
        //如果处于等待状态，则会将该进程添加到进程等待链表中，并且停止改进程，让处理机调度其他进程，实现了让权等待
        block(S->list);
}

//V *** 作
signal(semaphore *S){
   S->value++;
    if(S->value<=0)
        //此进程从临界区执行完成，此时如果共享资源数目<=0说明有进程在等待资源访问，此时在等待链表中唤醒一个进程，让唤醒的进程进入临界区访问临界区资源
        wakeup(S->list);
}

进程

进程：进程是进程实体的运行过程，是系统资源分配和调度的一个独立单位

进程实体：进程控制块，程序段，数据段组成

进程特征：

• 动态性：进程是程序的一次执行，动态的产生，变化，消亡
• 并发性：内存中有多个并发实体，各进程可并发执行
• 独立性: 进程能独立运行，独立分配资源，独立接受调度的基本单位
• 异步性：各个进程按照自己独立的，不可知的速度向前推进
• 结构性： 每个进程都是由PCB，程序段，数据段组成

线程

什么是线程？为什么要引入线程？

线程：线程是处理机调度的基本单位，是一个基本CPU执行单元，也是程序执行流的最小单位

线程特点

• 内核级线程是处理机调度的基本单位，进程是资源分配的基本单位
• 同一进程的不同线程共享该进程拥有的资源
• 同一进程内的线程切换不会影响进程切换
• 并发所带来的空间开销减小

用户级线程：由应用程序通过线程库实现，从用户视角可以看到的线程

内核级线程：由 *** 作系统内核完成线程的管理，从 *** 作系统视角看到的线程

多线程模型

• 多对一模型

  多个用户级线程只对应一个内核级线程

• 一对一模型

  每个用户级线程对应一个内核级线程

• 多对多模型

  n个用户线程对应m个内核级线程（n>=m）

中断

中断：让CPU由用户态转为内核态，使 *** 作系统重新夺回对CPU控制权

内核态转为用户态：执行一条特权指令–修改PSW的标志位为“用户态”，这就意味着 *** 作系统主动让出CPU

用户态转为内核态：由中断引发，硬件自动完成变态过程，触发中断信号意味着系统将强行夺回CPU的使用权

中断分类

• 内中断（也称异常）:与当前·的指令有关，中断信号来自CPU内部
  • 陷阱，陷入：由陷入指令发出，是应用程序故意引发的
  • 故障: 由错误条件引起，可能被内核程序修复。内核程序修复后会把CPU使用权还给应用程序。如：缺页中断
  • 终止：由致命错误引起，内核程序无法修复该错误。CPU将终止该应用程序
• 外中断：与当前执行的指令无关，中断信号来自CPU外部

系统调用

系统调用： *** 作系统对应用程序和程序员提供的接口

函数调用：有的函数调用没有使用到系统调用，有的函数调用是对系统调用进一步封装

进程控制 进程的工作状态 创建态

• 创建原语： *** 作系统创建一个进程所使用的原语

  1. 申请空白PCB
  2. 为新进程分配所需资源
  3. 初始化PCB
  4. 将PCB插入就绪队列：此时进程由创建完成由创建态转为就绪态

• 引起进程创建的事件

  • 用户登录
  • 作业调度
  • 提供服务
  • 应用请求

终止态

• 撤销原语
  1. 从PCB集合中找到PCB终止进程PCB
  2. 若进程正在运行，立即剥夺CPU，将CPU分配给其他进程
  3. 终止其所有的子进程
  4. 将该进程所有的资源还给非进程或 *** 作系统
  5. 删除PCB
• 引起进程终止对事件
  • 正常结束
  • 异常结束
  • 外界干预

进程的阻塞和唤醒

• 进程的阻塞
  • 阻塞原语（运行态到阻塞态）
    • 找到要阻塞的进程对应PCB
    • 保护进程运行现场，将PCB状态信息设置为“阻塞态”，暂时停止进程运行
    • 将PCB插入相应事件的等待队列
  • 引起进程阻塞的事件
    • 需要系统分配某种资源
    • 需要等待相互合作的其他进程完成工作
• 进程的唤醒
  • 唤醒原语（阻塞态到就绪态）
    • 在事件等待队列中找到PCB
    • 将PCB从等待队列移除，设置进程为就绪态
    • 将PCB插入就绪队列，等待被调度
  • 引起进程唤醒的事件
    • 等待的事件发生（因何事阻塞，就应由何事唤醒）

进程切换

• 切换原语（运行态到就绪态，或者就绪态到运行态）
  • 将运行环境存入PCB
  • PCB移入相应队列
  • 选择另一个进程执行，并更新其PCB
  • 根据PCB恢复进程所需的运行环境
• 引起进程切换的事件
  • 当前进程时间片到
  • 有更高优先级的进程达到
  • 当前进程主动阻塞
  • 当前进程终止

挂起

为减轻系统负担，提高资源利用率，暂时不执行的进程会被调到外存从而变成“挂起态”

七状态模型：在五状态基础上加入了，“就绪挂起”和“阻塞挂起”两种状态

进程通信

进程通信：进程之间进行信息交换

进程通信有哪些：

1. 共享存储
   • 基于数据结构的共享，是一种低级通信
   • 基于存储区共享，是一种高级共享
2. 消息传递
   • 数据交换以格式化的消息为单位。通过 *** 作系统提供的”发送消息，接收消息“两个原语进行数据交换
   • 直接通信方式
     • 消息直接挂到接收进程的的消息缓冲队列上
   • 间接通信方式
     • 消息先发送到中间实体（信箱中）
3. 管道通信
   • 管道只能采用半双工，如果实现全双工需要设置两个管道
   • 写满时，不能在写。读空时，不能在读
   • 没写满，不能读。没读空，不能写

处理机调度

处理机调度：就是从就绪队列中按照一系列算法选择一个进程并将处理机分配给它运行，以实现进程的并发执行

高级调度

• 按一定原则从外存上处于后备队列的作业中挑选一个作业，给他们分配内存等必要资源，并建立相应的进程（PCB），是他们获得竞争处理机的权力。
• 高级调度是处理机和内存之间调度。每个作业只调入一次，调出一次,调入时建立相应的PCB，调出时撤销PCB
• 高级调度主要指调入问题，因为只有调入时机需要 *** 作系统来确定，但调出时机必然是运行结束才调出

中级调度（内存调度）

• 就是要决定将那个处于挂起状态的进程重新调入内存
• 一个进程可能被多次调入，调出内存，因此中级调度发生的频率比高级调度更高

低级调度

• 主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它
• 最基本的一种调度

调度算法评价指标 CPU利用率

利用率 = 忙碌时间/总时间

系统吞吐量

单位时间内完成作业的数量

系统吞吐量 = 总共完成了多少道作业/总共花了多少时间

周转时间

• 周转时间：作业被提交给 *** 作系统开始，到作业完成为止的这段时间间隔
• 周转时间组成：作业在后备队列等待高级调度时间，进程在就绪队列上等待低级调度时间，进程在CPU执行时间，进程等待I/O *** 作完成时间
• 周转时间 = 作业完成时间 - 作业提交时间
• 平均周转时间 = 各作业周转时间之和/作业数
• 带权周转时间 = 作业周转时间/作业实际运行的时间
• 平均带权周转时间 = 各个作业带权周转时间之和/作业数

等待时间

指进程/作业处于等待处理机状态时间之和

响应时间

用户提交请求到首次产生响应所用的时间

进程调度（低级调度）

就绪态转为运行态

进程调度任务

1. 保存处理机现场
2. 按照某种算法选取进程
3. 把处理器分配给进程

进程调度机制

1. 排队器：当有一个进程转变为就绪状态时，排队器按一定策略将它们插入到相应的就绪队列中，提高进程调度效率
2. 分配器：依据进程调度程序所选定的进程，将他们从就绪队列中取出，然后进行从分配器到新选出进程间的上下文切换，将处理机分配给选出的进程
3. 上下文切换器：对处理机切换时会发生两对上下文的切换 *** 作
   • 第一对上下文切换时，OS保存当前进程的上下文，即把当前进程的处理机寄存器内容保存到相应的PCB中的相应单元。然后装入分派程序的上下文，以便分派程序运行。
   • 第二对上下文切换时，移出分派程序的上下文，把新选进程的CPU现场信息转入到处理机相应的寄存器中，以便新选进程运行。

调度算法 先来先服务FCFS 算法思想

“公平”的角度考虑

算法规则

按照作业/进程到达的先后顺序进行执行，先来的先执行

适用范围

用于高级调度，考虑那个作业先到达后备队列；用于进程调度，考虑那个进程先到达就绪队列

是否可以抢占

非抢占的算法

优缺点

• 优点
  • 公平，算法实现简单
• 缺点
  • 对短作业不利，短作业带权周转时间很大对短作业来说用户体验不好，对长作业有利

是否会导致饥饿

不会

短作业优先（SJF，ShortestJobFirst） 算法思想

追求最少的平均等待时间，最少的平均周转时间，最少的平均带权周转时间

算法规则

最短作业/进程优先得到服务（所谓“最短”，是指要求服务时间最短）

使用范围

可以用于高级调度和低级调度，用于进程调度称为短进程优先

是否可抢占

SJF和SPF是非抢占式算法。也有抢占式的版本–最短剩余时间优先

优缺点

• 优点
  • “最短的”平均等待时间，平均周转时间，平均带权周转时间
• 缺点
  • 不公平。对短作业有利，长作业不利。
  • 可能产生饥饿现象
  • 作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先

是否会导致饥饿

会。如果一直有短作业/进程到来，可能使长进程/作业长时间得不到服务，产生饥饿现象。如果一直得不到服务，则称为"饿死"

高响应比优先（HRRN） 算法思想

要综合考虑作业/进程的等待时间和要求服务的时间

算法规则

在每次调度时先计算各个作业/进程的相应比，选择响应比最高的作业/进程为其服务

响应比 = 等待时间+要求服务时间/要求服务时间

使用范围

作业调度和进程调度

是否可抢占

非抢占式的算法。只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算相应比

优缺点

综合考虑了等待时间和运行时间（要求服务时间）等待时间相同时，要求服务时间短的优先（SJF优点）要求服务时间相同，等待时间越长的优先（FCFS优点）。对于长作业来说，等待时间越大，其相应比也会越大，从而避免了长时间饥饿的问题。

是否会导致饥饿

不会

时间片轮转法 算法思想

公平地，轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应

算法规则

按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。

使用范围

用于进程调度，只有作业放入内存建立了相应的进程后，才能被分配处理机时间片

是否可抢占

可抢占式

优缺点

优点：

• 公平；响应快，适用于分时 *** 作系统

缺点：

• 由于高频率的进程切换，因此有一定开销，不区分任务紧急程度

是否会导致饥饿

不会

优先级调度算法 算法思想

根据任务紧急程度来决定处理顺序

算法规则

调度时选择优先级最高作业/进程

适用范围

可用于作业调度，进程调度，I/O调度中

是否可抢占

可抢占

优缺点

优点：

1. 适用于实时 *** 作系统，通过优先级区分紧急程度

缺点：

1. 若源源不断有高优先级进程到来，会导致低优先级进程饥饿

是否会导致饥饿

会

多级反馈队列调度算法 算法思想

对其他调度算法折中权衡

算法规则

1. 设置设置多级队列，各级队列优先级从高到低，时间片从大到小
2. 新进程到达时先进入第一级队列，按FCFS原则排队等待被分配时间片，若用于时间片进程还未结束，则进程进入下一级队列队尾。若此时已经是在最下级的队列，则重新放回该队列队尾
3. 只有第k级队列为空时，才会为K+1级头的进程分配时间片

是否可抢占

可抢占算法

使用范围

进程调度

优缺点

优点：

1. 相对公平
2. 每个进程可以很快相应
3. 短进程只用较少时间就可以响应
4. 不需要实现进程估计时间
5. 可灵活调整进程的偏好程度，如CPU密集型进程，I/O密集型进程

是否会导致饥饿

会

死锁

什么是死锁？

各进程互相等待对方手里的资源，导致各进程阻塞，无法向前推进

什么时候会发生死锁？

对不可剥夺资源不合理分配，可能导致死锁

死锁产生的必要条件

• 互斥条件：必须互斥的使用的资源的争抢才会导致互斥
• 不剥夺条件：进程保持的资源只能主动释放，不可强行剥夺
• 请求和保持条件： 保持着某些资源不放，同时请求别的资源
• 循环等待条件：
  • 存在一种进程资源的循环等待链
  • 循环等待未必死锁，死锁一定循环等待

死锁处理策略

• 预防死锁：破坏死锁产生的四个必要条件
• 避免死锁：避免系统进入不安全状态（银行家算法）
• 死锁检测和解除：允许死锁发生，系统负责检测出死锁并解除

预防死锁

只要一个或者几个死锁产生的条件不满足，死锁就不会发生

破坏互斥条件

互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁

临界资源改造为共享使用的资源（SPOOLing技术）

缺点：并不是所有的资源都可以改造成可共享使用的资源。可行性不高

破坏不剥夺条件

不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放

实现方式

• 方式一：申请的资源得不到满足时，立即释放拥有的所有资源
• 方式二：当申请的资源被其他进程占有时，由 *** 作系统协助剥夺（考虑优先级）

缺点：

1. 实现复杂
2. 释放已获得资源可能导致前一阶段工作失效。此适用于易保存和恢复转态资源。如CPU
3. 反复申请和释放资源会增加系统开销，降低系统吞吐量。
4. 若采用方案一，暂时得不到某个资源，之前获取的资源全部需要放弃，以后在重新申请。如果一直发生这样情况，就会导致进程饥饿

破坏请求和保持条件

请求和保持条件：进程已经保持至少一个资源，但又提出新的资源请求，而该资源又被其它进程占有，此时进程被阻塞，但又对自己已有的资源保持不放。

运行前分配好所有需要资源，之后一直保持

缺点：资源利用率低；可能导致饥饿

破坏循环等待条件

循环等待条件：存在一种进程资源循环等待链，链中每一个进程已获得的资源同时被下一个进程所请求

采用顺序资源分配法，给资源编号，必须按编号从小到大顺序申请资源

缺点：不方便增加新设备，会导致资源浪费，用户编程麻烦

避免死锁

• 安全序列

  就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出安全序列，系统就是安全状态。

• 如果系统处于安全序列一定不会发生死锁

• 银行家算法核心思想：在系统分配之前预先判断这次分配会不会导致系统进入不安全状态

• 银行家算法步骤

  1. 检查此次申请是否超过了之前声明的最大需求数
  2. 检查此时系统剩余的可用资源是否还能满足这次请求
  3. 试探着分配，更改各数据结构
  4. 用安全性算法检查此次是否会导致系统进入不安全状态

• 安全算法步骤

  检查当前剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入到安全序列，并把该进程持有资源全部收回

• 系统处于安全序列一定不会死锁。死锁一定处于不安全序列，处于不安全序列不一定会发生死锁

死锁的检测与解除

• 死锁检测算法：用于检测系统状态，以确定系统中是否发生了死锁
• 死锁解除算法：当认定系统中已经发生了死锁，利用该算法可将系统状态中解脱出来

死锁检测

资源分配图

• 两种结点

  • 进程结点：对应一个进程
  • 资源结点：对应一类资源，一类资源可能有多个

• 两种边

  • 进程结点——>资源结点：表示进程想申请几个资源（每条边代表一个）
  • 资源结点——>进程结点：表示已经为进程分配了几个资源（每天边代表一个）

检测死锁算法

• 可完全简化：若能消去途中所有的边，则称改图是可完全简化的
• 死锁定理：如果某时刻系统资源分配图是不可完全简化的，那么此时系统死锁

死锁解除

1. 资源剥夺法：剥夺某些死锁进程资源并挂起，将资源分配给其他死锁进程。
2. 撤销进程法：终止部分或者全部死锁进程，并剥夺这些进程资源
3. 进程回退法：将死锁进程回退到足以避免死锁的地步

---

第三章存储器管理 内存管理的概念 内存空间的分配与回收 连续分配管理方式 单一连续分配

• 内存分为系统区和用户区。系统区，用于存放 *** 作系统相关数据；用户区用于存放用户进程相关数据。内存中只能有一道用户程序，独占整个用户区空间
• 优点
  1. 实现简单
  2. 无外部碎片
  3. 可以采用覆盖技术扩充内存
  4. 不一定需要采取内存保护
• 缺点
  1. 只能用于单用户，单任务的 *** 作系统中
  2. 有内部碎片
  3. 存储器利用率极低

固定分区分配

• 将用户区划分为若干个大小的分区，每个分区中只装入一道作业

• 两种分配方式

  • 分区大小相等
  • 分区大小不等

• 分区说明表：实现各个分区的分配与回收。每个表项对应一个分区。每个表项包括分区号，分区大小，起始位置，状态

  分区号大小（MB）起始地址（M）状态128未分配…………

• 优点：

  1. 实现简单
  2. 无外部碎片

• 缺点

  1. 当用户程序太大时，可能所有的分区都不能满足需求，此时采用覆盖技术，但会降低性能
  2. 会产生内部碎片，内存利用率低