操作系统-408

一、操作系统概述

1、定义

负责协调软件和硬件的计算机资源的工作
为上层应用提供简易的服务
操作系统是系统软件

2、功能：

操作系统是系统资源的管理者
- 处理机管理
- 存储器管理
- 文件管理
- 设备管理
向上层提供方便易用的服务
- 命令接口
- 程序接口
对硬件机器的扩展

3、特征

并发
- 多个事件同一时间间隔内发生.实际上是交替发生,宏观上才是同时发生.
- 操作系统的并发性意思就是操作系统的程序交替执行
共享
- 资源共享,操作系统的资源能够提供给多个并发执行程序使用.
- 两种共享方式
  - 互斥共享：一个时间段只允许一个进程访问该资源
  - 同时共享：一个时间段允许多个进程同时访问
虚拟
- 把物理实体变成若干个逻辑对应物。物理实体存在，逻辑对应物是抽象出来的。
  - 空分复用技术（虚拟存储器）
  - 时分复用技术（虚拟处理机）
异步
- 多个程序不是一次性执行完的，而是走走停停的。比如两个进程，每个进程多个指令，那么这些执行不可能一次执行完，而是异步交替的执行的。

并发和共享是最基本的特征，没有这两个特征就没有虚拟和异步了。

4、操作系统的发展和分类

手工操作阶段
批处理阶段
- 单道批处理系统
- 多道批处理系统
分时操作系统
实时操作系统
网络操作系统
分布式操作系统
个人计算机操作系统

二、操作系统的运行机制和体系结构

1、运行机制

两种指令
- 指令：CPU翻译编程语句为二进制数，机器可以识别的。
  - 特权指令：如内存清零，不允许用户程序使用
  - 非特权指令：普通运算指令
- CPU根据处理机状态判断当前指令的类型
两种处理器状态
- 用户态：cpu只能执行非特权指令
- 内核态：特权指令、非特权指令都可执行
- 状态通过程序状态寄存器PSW中某个标志位进行标记。0是用户态，1是内核态
两种程序
- 内核程序：操作系统内核程序就是系统的管理者，可以执行特权指令，运行在核心态
- 应用程序：为了保证系统安全，只能执行非特权指令。运行在用户态

2、操作系统内核

下面4种就是大内核，后面3种加起来就是微内核体系结构。
- 系统资源管理
  - 进程管理，存储器管理，设备管理（有的操作系统不会把这部分划分到内核功能）
- 比如时钟管理：计时
- 中断处理：实现中断机制
- 原语（设备驱动、CPU切换）：最接近硬件的部分，程序运行具有原子性。
内核是计算机配置的底层软件，是操作系统最基本、最核心的部分。

3、OS体系结构

大内核
微内核

4、中断

中断机制的诞生：为了实现多道程序并发执行而引入的一种技术
概念与作用
- 发生中断，就意味着需要操作系统介入开展管理工作，CPU会立即进入核心态
- “中断”是CPU从用户态进入核心态的唯一途径
中断的分类
- 内中断（也称异常、例外、陷入）
  - 自愿中断—指令中断
  - 强迫中断—硬件故障、软件故障
- 外中断（中断）
  - 外设请求
  - 人工干预
另一种分类
- 陷阱、陷入trap：系统调用，主动中断
- 故障fault：比如缺页可以自己修复的中断。错误条件引起的，可能被故障处理程序修复
- 终止abort：不可修复的致命错误造成的结果，导致程序不再将控制返回引发终止的程序，比如整数/0
外中断的处理过程
- 每条指令执行完都需要检测是否有外设的中断信号
- 如果有那么就要保护当前进程状态并且中断（保存PSW,程序计数器，各种通用寄存器）
- 根据中断信号转入相应的中断处理程序

5、系统调用

什么是系统调用，有何作用？（为了防止用户随便调用共享资源，保证系统的安全性）
- OS提供给应用程序使用的接口，应用程序通过操作系统调用请求操作系统的服务，系统中的各种共享资源都由操作系统统一掌管。因此在用户程序中凡是与资源有关的操作，都必须通过系统调用的方式向操作系统提出服务请求，由操作系统完成。
- 应用程序通过系统调用来请求获得操作系统的服务
- 系统调用会使处理器从用户态转内核态
- 分类
  - 设备管理
  - 文件管理
  - 进程控制
  - 进程通信
  - 内存管理
系统调用与库函数的区别
- 系统调用是OS向上次提供的接口
- 有的库函数是对系统调用的进一步封装
- 大多数是通过库函数间接的进行系统调用
系统调用背后的过程
- 传递系统调用参数
- 执行陷入指令（陷入指令在用户态下执行。陷入指令执行一个内中断，cpu进入核心态；陷入指令是唯一一个能够在用户态执行，而不能够在核心态上面执行）
- 执行系统调用相应服务程序
- 放回用户程序

三、进程

1、进程概述

定义：是进程实体的一次运行，是系统进行资源分配的基本单位。目的是为了更好描述和控制程序的并发执行。
- 为了方便管理各个程序执行，引入了进程和进程实体的概念
- 还引入了PCB、数据段+程序段组成了进程实体，PCB就是进程结构，用于定位数据段和程序段的位置
- PCB是进程存在的唯一标志
- 进程是进程实体的运行过程，是系统进行资源分配和调度的独立单位
- 进程实体是静态的，进程是动态的
组成
- PCB包含操作系统所需的各种信息（操作系统通过PCB管理进程）
- 程序段存放程序代码
- 数据段存放对应的全局、局部变量等（程序运行时使用、产生的运算数据）
组织方式
- 链接方式
  - 按照进程的状态把PCB划分为多个状态
  - 操作系统持有各个队列的指针
- 索引方式
  - 根据进程状态不同，建立索引表
  - 操作系统持有各个索引的指针
特征
- 动态性：程序执行是动态的
- 并发性：多个进程实体和各进程并发执行
- 独立性：进程独立运行，独立获取资源，独立接收调度的基本单位，进程是资源分配，接收调度的基本单位
- 异步性：各个进程独立，不可预知的速度执行
- 结构性：PCB+程序段+数据段

2、进程状态

状态
- 运行态：占用cpu，正在运行
- 就绪态：具备运行条件，但是没有抢到cpu。拥有了除了处理机之外的所有资源。
- 阻塞态：因为某个事件不能执行。等待打印机等外设的处理结果
- 创建态（新建）：系统为新的进程分配资源，比如PCB,程序段，数据段
- 终止态（结束）：进程从系统内撤销
状态转换
- 创建->就绪：系统完成创建进程的相关工作
- 就绪->运行：调度
- 运行->就绪：时间片结束，或者被优先级更高的进程抢占
- 运行->阻塞：等待资源分配或者是事件发生(主动行为)
- 阻塞->就绪：事件或者资源得到（被动），阻塞态唤醒之后就变成就绪态，但是就绪态是不能转换为阻塞态的，原因就是就绪态没有获取cpu无法执行系统调用
- 运行->终止：进程结束或者是遇到不可修复的错误

3、进程控制

进程控制的主要功能是对操作系统所有的进程实施有效的管理，可以创建进程，撤销进程，实现进程的状态装换。

原语：执行期间不能被中断，这里的原语的意思就是原子操作，原语实现依靠的就是关中断和开中断，防止原语代码被中断，影响了原子操作

进程控制
- 创建->就绪：修改PCB内容，相应队列
- 就绪->运行：恢复进程运行，修改PCB和相应的队列。
- 运行->就绪：保存进程的运行环境，修改PCB内容和相应的队列。
- 运行->阻塞：保存进程运行环境，修改PCB内容和响应的队列。
- 阻塞->就绪：修改PCB内容，和相应的队列。
进程原语类型
- 创建原语
  - 申请空白PCB，总不可能只申请一半
  - 为新的进程分配所需的资源
  - 初始化PCB
  - 将PCB插入到就绪队列
- 撤销原语（阻塞/就绪/运行->终止）
  - 从PCB集合中查找终止进程的PCB
  - 进程如果在执行，立刻剥夺CPU分配给其它进程
  - 终止其它所有进程
  - 将该进程的所有资源归还给父进程和操作系统。
  - 删除PCB
- 阻塞原语（运行->阻塞）
- 唤醒原语（阻塞->唤醒）
- 切换原语

4、进程通信

进程之间的信息交换；进程是分配系统资源的单位，各个进程内存空间是独立的；但是防止两个进程之间的内存直接访问。

共享内存
- 两个进程对于共享区的访问是互斥的。
- 共享存储
  - 基于数据结构的共享
  - 基于存储区的共享：存放的数据格式，内容都是进程决定的。
管道通信
- 管道只能使用半双工，某个时间段只能实现单向传输。如果要双向，那么就需要两个管道。
- 各个进程对管道也是互斥的。
- 数据以字符流写入管道，写满之后写进程write系统调用就会被阻塞，读完之后read也会被阻塞。
- 没写满不允许读。没读空不允许写
- 最多只能有一个读进程
消息传递
- 进程数据交换以格式化的消息为单位，操作系统通过发送消息和接收消息两个原语进行数据交换
- 消息格式
  - 消息头
    - 发送进程id+接收进行id+消息类型+消息长度
  - 消息体
- 直接通信
- 间接通信

5、线程（进只是资源分配的基本单位，线程才是调度的基本单位）

线程的使用：能够提高并发度。多个事件可以并发执行；线程成为程序执行流的最小单位

线程使用
- 线程是基本的cpu执行单位，程序执行流最小单位
- 进程内的各个线程可以并发执行。
- 进程只作为除cpu之外的系统资源的分配单位
线程属性
- 线程是处理机的调度单位
- 各个线程可以占用不同cpu，在多核情况
- 每个线程有线程id和TCB
- 线程也有就绪阻塞，运行三种基本状态
- 线程几乎不拥有系统资源
- 同一个进程的不同线程共用同样的系统资源
- 同一进程的线程通信不需要系统调用，因为有同样的共享资源
实现方式
- 用户线程
  - 用户级线程由应用程序通过线程库实现。所有线程管理工作都是应用程序负责
  - 在用户看来是多线程，但是对于操作系统内核是无法感知到的
- 内核线程
  - 内核级线程通过操作系统内核管理
  - 内核级线程才是处理机分配单位
多线程模型
- 多对一
  - 用户级线程切换在用户空间可以完成，不需要切换到核心态。开销小
  - 如果一个用户级线程被阻塞，整个进程就会被阻塞。那么多个线程不能在多核处理机上执行
- 一对一
  - 并发度高，一个线程被阻塞，其它线程还能够继续运行
  - 一个进程占用多个内核级线程，线程切换交给了操作系统内核，需要切换到核心态，线程管理成本很大。
- 多对多
  - 介于二者之间

6、处理机调度

调度
- 任务太多，但是资源有限，这个时候就需要指定规则决定处理任务的顺序，这个就是调度。
- 处理机调度，就是从就绪队列按照一定算法选择一个进程并将处理机分配给它运行。
层次
- 高级调度（作业调度）
  - 内存有限不能把所有进程加载进内存。
  - 高级调度按照一定规则选择一个，并且分配内存，创建PCB
  - 作业调入创建PCB，调出撤销PCB
  - 从后备队列选择一个调入内存
- 中级调度（内存调度）
  - 引入虚拟存储技术，可以把暂时不能运行的进程调到外存，当又具备条件，并且有内存的时候才会调入内存执行。提高内存的利用率和系统吞吐量。
  - 这个时候进程的状态就是挂起。但是PCB仍然是常驻在内存。只是程序段和数据段这些存入了外存。
  - 中级调度就是把哪个挂起的进程重新调入内存。可能发生多次。
- 低级调度（进程调度）
  - 从就绪队列选择进程
  - 进程调度是最基本的调度。调度频率非常高。
补充
- 进程的挂起与七状态模型
  - 就绪如果发现内存不够就会把程序存到外存就绪挂起，内存空间空闲，那么就会转换回就绪态。
  - 运行态可以在某种系统调用下进入就绪挂起。
  - 创建如果发现内存不足，那么就会进入到就绪挂起。或者是阻塞到阻塞挂起。也是把内存的进程映像存入到外存。
  - 阻塞挂起是不满足条件，而且内存不够的时候进程存入外存，PCB仍然在内存，所以当接收到阻塞IO完成的中断信号的时候就能够进入到激活到就绪挂起。
- 挂起和阻塞的区别
  - 挂起和阻塞都是暂时无法使用cpu
  - 挂起把进程的映像存到外存（映像就是程序段+数据段。但是PCB仍然存在内存）
  - 但是阻塞状态的时候并没有把映像存入外存
总结

调度时机

可以调度
- 运行的进程主动放弃处理机
  - 进程正常终止
  - 发生异常
  - 主动请求IO阻塞
- 被动放弃
  - 分给进程的时间片用完
  - 有更紧急的任务需要处理
  - 有更高优先级的进程进入就绪队列
不能调度
- 处理中断过程
- 进程在操作系统内核程序临界区。内核的程序临界区，通常是访问内核的数据结构就绪队列，如果这个时候发生进程调度，那么就绪队列被锁住是无法使用的。因为访问内核临界区是不能够切换和调度。
- 原子操作的过程中。原语，状态改变。

进程调度的方式

非抢占式
- 允许进程主动放弃处理机
- 虽然系统开销小，但是问题是无法处理紧急任务
抢占式
- 可以被更紧急任务优先调用cpu

进程切换与过程

狭义的进程切换指的是从就绪队列选中一个要运行的进程
进程切换指的一个进程让出处理机，由另一个进程占用处理机的过程。
广义进程调度选择一个进程和进程切换

进程切换的过程

对原来运行的各种数据保存
对新进程恢复

调度算法

FCFS先来先服务
SJF短作业优先
HRRN高相应比优先
时间片轮转
- 算法思想：公平，轮转为每个进程服务，每进程在每个时间都能得到响应
- 算法规则：每个进程有一个执行时间片（100ms），执行完就要切换
- 通常只用于进程调度，这里的时间片是处理机的
- 是否抢占：抢占，通过时钟中断来阻断进程运行，切换下一个
- 优缺点
  - 公平，响应快，适合分时操作系统。
  - 高频率进程切换，有一定的开销。不区分任务紧急程度
- 不会饥饿
优先级
- 算法思想：实时操作系统，更多场景需要根据任务的紧急程度决定处理任务的顺序。
- 算法规则：调度选择优先级更高的任务
- 可以用于作业和进程
- 是否抢占：两种都具备。如果是非抢占，那么只需要等待进程放弃处理机，如果是抢占
- 那么就绪队列发生变化的时候需要检查是否发生抢占
- 优缺点
  - 区分紧急度，重要程度，适合实时操作系统
  - 如果经常有高优先级的进程到来可能导致饥饿
- 会导致饥饿
多级反馈队列
- 算法思想：对前四种算法优点折中
- 算法规则
  - 设计多级就绪队列，优先级从高到低，时间片从小到大
  - 新进程进入到第一级队列，并且按照FCFS等待分配，如果用完时间片进程进入下一级的优先级队列
  - 只有k级队列为空，才会为k+1队头分配时间片。
- 只是用于进程调度
- 是否抢占：是抢占式的算法。
- 优缺点
  - 相对公平（FCFS优点），新到达的进程可以快速响应（RR时间片调度优点），短进程可以快速完成，不需要估计运行时间，可以灵活调整偏好程度。
- 会导致饥饿

进程同步与互斥

同步
- 完成进程同步其实就是让指令按照某种顺序执行。同步也是直接制约关系，它指的是按成某个任务的一个或者多个进程，这些进程需要在某些位置协调他们的工作次序产生的制约关系。
互斥
- 一个时间段只允许一个进程使用的共享资源就是临界资源。对于临界资源的访问是互斥的。互斥就是每次只能有一个进程访问，其它进程不得访问
- 进程互斥的四个部分
  - 进入区：负责给访问资源设置正在访问标志，阻止其他进程进来
  - 临界区：访问临界资源的代码
  - 退出区：接触这个访问标志
  - 剩余区：其他处理
  - 注：
    - 进入区和退出区实现的是进程互斥
    - 临界区是进程访问临界资源的代码
- 进程互斥的遵循规则
  - 空闲让进，临界区空闲允许一个请求访问
  - 忙则等待，如果有进程已经进入临界区，那么另一个进程就需要等待。
  - 有限等待。保证进程有限的时间内进入临界区。
  - 让权等待，当进程无法进入临界区，立刻让出处理机

信号量

用户可以通过操作系统提供的原语对信号量进行操作。
信号量表示的是某种资源的数量。
原语是一种特殊的程序段，通过关中断和开中断实现，解决原子操作问题。
分为wait(S)和signal（S）也可以被称为PV操作。

死锁：互相等待对方的资源，导致进程都阻塞无法推进

饥饿：进程长期得不到资源，导致的等待无法推进，只有一个进程饥饿可能是阻塞或者是就绪

死锁条件

互斥条件：对必须互斥使用资源争抢才会导致死锁
不剥夺条件：进程未使用完资源之前，不能被其它进程抢走
请求和保持条件：进程保持至少一个资源，但是提出新的资源请求，这个资源又被其它进程占用。请求的资源的进程被阻塞，但是对自己的资源又不释放。
循环等待链：链中的每一个进程获取资源，但是同时被下一个的进程请求。

预防死锁

银行家算法

分配资源之前判断这次分配是不是会导致系统进入不安全状态。
为了避免死锁

小结

死锁检测需要两种数据结构，两个边
- 进程节点，进程指向资源表示请求
- 资源节点，资源指向进程表示分配
死锁检测算法
- 依次消除不阻塞进程相连的边，知道没有边可以消除
- 如果资源分配图无法完全简化，那么就会发生死锁。
解除的方法
- 资源剥夺，就是直接抢占，并且让该进程进入到外存
- 撤销进程，成本太大
- 进程回退，也是成本太大。

四、内存管理

1、基础知识

1.1、什么是内存

存储单元：内存用于存放数据的硬件，程序执行前需要加载进内存。
内存地址
- 按字节编址，说明每个存储单元就是1个字节
- 按字编址，每个存储单元是1个字也就是两个字节

1.2、进程运行的基本单位

指令的工作原理：操作码+若干参数（可能包含地址参数）
逻辑地址：每个目标从0开始编址，相对地址
物理地址：内存中物理单元的集合，地址转换的最终地址
从写程序到程序运行
- 编辑源代码文件（程序员写代码）
- 编译：由代码文件生成目标模块（高级语言翻译机器语言）
- 链接：由目标模块生成装入模块，链接后形成完整的逻辑地址
- 装入：将装入模块装入内存，转入后形成物理地址
三种链接方式
- 静态链接：装入前链接成一个完整模块
- 装入时动态链接：运行前边装入边链接
- 运行时动态链接：运行时需要目标模块才装入并链接
三种装入方式
- 绝对装入：编译时产生绝对地址
- 静态重定位装入：装入时将逻辑地址转为物理地址
- 动态重定位装入：运行时将逻辑地址转为物理地址，需设定重定位寄存器

2、内存扩充

覆盖（同一进程）
- 固定区：常用的段
- 覆盖区：不常用的段，需要时再调入内存
交换（不同进程）
- 内存空间紧张时，系统将内存中某些进程暂时换到外存，把外村中某些具备运行条件的进程换进内存。
- 逻辑上扩充内存
虚拟内存：在用户看来似乎有一个比实际大的内存。在程序装入时，可以将程序中很快用到的部分装入内存，暂时用不到的部分留在外存中。程序运行时，当访问的信息不在内存，OS将信息从外村调入，内存空间不足时，os负责将内存用不到的信息换到外存。
补充
- 局部性原理
  - 时间局部性：某条指令一旦执行，不久后可能再次执行
  - 空间局部性：访问某个存储单元，不久后将访问附近