操作系统复习与总结

yuiyake 10/21/2021

# 操作系统

# 第一章操作系统引论

# 基本概念

操作系统的定义
- 操作系统是控制和管理计算机的软、硬件资源，合理地组织计算机的工作流程，以及方便用户的程序集合。

操作系统的特征
- 并发共享虚拟不确定

操作系统的功能
- 存储管理
  - 任务：提高内存利用率
  - 功能：内存分配，地址映射，内存保护，内存扩充
- 进程管理
  - 任务：对处理机的分配和运行进行有效管理
  - 功能：进程控制，进程同步，进程通信，进程调度
- 设备管理
  - 任务：完成用户程序请求的io操作，为程序分配io设备
  - 功能：设备分配，设备控制，设备无关性
- 文件管理
  - 任务：对文件的管理（放在外存）
  - 功能：文件存储空间管理，目录管理，文件读写管理，文件存取控制

# 操作系统的类型

批处理系统
- 单道批处理：内存只放一道作业，完成顺序跟进内存顺序相关
- 多道批处理：内存多道作业，完成顺序与进内存顺序无关 = 优缺点：
  1. 优点：资源利用率高，系统吞吐量大
  2. 缺点：平均周转时间长，无交互

分时系统
- 允许多终端用户使用计算机，用户感觉不到其他用户的存在，像独占。
- 简单分时
- 前后台分时
- 多道分时
- 特征：多路性，独立性，交互性，及时性

实时系统
- 对外部输入的信息，实时系统能在规定时间内处理完成并反应
- 闭环实时：实时控制系统
- 开环实时：实时信息处理系统
- 特殊要求：高可靠性，过载保护，对截止时间的要求

# 第二章进程管理

# 进程的引入

程序的顺序（串行）执行
- 特点
1. 封闭性
2. 顺序性
3. 可再现性
程序的并发执行
- 特点
  1. 间断性
  2. 失去封闭性
  3. 失去可再现性
并发执行的条件Bernstein：说白了就是读集与写集的交集为空，就可以并发执行。（再通俗点就是一个变量在不同程序段里没有同时被赋值/更改）
进程的定义：可并发执行的程序在一个数据集合上的执行过程(实质是过程)
进程的特点（属性）：动态和并发
进程的基本属性
- 进程是拥有资源的独立单位
- 进程是独立调度和分派的基本单位
进程与程序的关系

# 进程的状态及其组成

进程的三种基本状态：就绪，运行，阻塞
- 基本状态图
- 双挂起图
- 处于挂起状态的进程不在内存里，在外存。挂起状态的提出就是为了内外存对换的需要。
进程的组成
- 进程控制块PCB，程序段，数据段，堆栈。其中PCB是进程存在的唯一标识。
- 引入PCB的作用：就是使程序能成为独立运行的单位，并可和其他进程并发执行。
- PCB的内容
  1. 进程描述信息
  2. 处理机状态信息
  3. 进程调度信息（状态&优先级）
  4. 进程控制和资源占用信息（进程的内容，包括地址啥的）

# 进程的控制

操作系统的内核（运行在系统态）
- 核心态（系统态）：具有较高的特权，能执行一切命令，访问所有寄存器和存储区。
- 用户态：具有较低特权，只能执行规定的命令，访问指定的寄存器和存储区。
内核与原语
- 内核
  - 系统将一些与硬件紧密相关的模块放在内核
    - 中断处理
    - 时钟管理
  - 内核在执行某些基本操作时，往往是利用原语操作实现的。
- 原语
  - 原语由若干条指令构成、用于完成一定功能的过程。
  - 原语是“原子操作”。即一个操作中的所有动作，要么全做，要么全不做。换言之，原子操作是一个不可分割的操作。

# 线程

线程的定义：线程是进程中的一个实体，是系统独立调度和分派的基本单位
进程与线程比较：
- 进程是资源的拥有者
- 线程不拥有资源，只有TCB及堆栈
- 调度
  - 线程调度快，需要空间小。
  - 进程因拥有资源，调度时因负担过重而缓慢。
- 并发性
  - 在引入线程的操作系统中，不仅进程之间可以并发执行，一个进程中的多个线程之间亦可并发执行。
- 拥有资源
  - 进程是资源的拥有者
- 系统开销
  - 进程切换的开销远远大于线程切换的开销，线程的切换省去了资源的回收。

# 第三章进程同步与通信

# 进程同步与互斥

进程同步的基本概念
- 临界资源：某段时间内仅允许一个进程使用的资源。
- 临界区：每个进程中访问临界资源的那段代码。
同步机制遵循的准则
- 空闲让进，忙着等待，有限等待，让权等待
- 临界区访问描述
软件互斥的方法
- 硬件：TS（Test and Set）指令 / 禁止中断
- 软件：
  - 单标志算法，双标志、先检查算法，双标志、先修改后检查算法，先修改、后检查、后修改算法

信号量和PV操作

semaphore a = 0 声明信号量,必须给初始值
pv操作必须成对出现
p操作(阻塞)

void  wait(semaphore  s) {   
    s.value = s.value - 1;
    if  (s.value < 0)
    block(s.queue);  
    /* 将进程阻塞，并将其投入等待队列s.queue */
}

1
2
3
4
5
6

v操作(唤醒)

void  signal(semaphore  s) {   
    s.value = s.value + 1;
    if  (s.value <= 0)
    wackup(s.queue);      
    /* 唤醒阻塞进程，将其从等待队列s.queue 取出，投入就绪队列*/
}

1
2
3
4
5
6

pv操作解决互斥同步问题

互斥：进去之前+p，出来后+v ,互斥锁
如果有多个资源，则设多个信号量

如果有n端抢一个资源，在信号量初始化的时候给n

semaphore mutex=1;
P1:                       P2:
while (1){       	      while (1){
	P(mutex);     		      P(mutex);
	临界区;		              临界区
	V(mutex);		          V(mutex);
	剩余区;		              剩余区;
    };	                      };

1
2
3
4
5
6
7
8

同步：先执行的后面+v，后执行的前面+p

semaphore a,b=0,0;

{s1; V(a); V(b)}

{P(a); s2}

{P(b); s3}

1
2
3
4
5
6
7

# 经典进程同步问题

生产者-消费者问题
读者-写者问题
哲学家进餐问题
打瞌睡的理发师问题

# AND信号量

基本思想：将进程在整个运行期间所需要的所有临界资源一次性全部分配给进程，待进程使用完后再一起释放。
解决同步互斥问题。

# 进程通信

进程通信类型
- 共享存储器系统（高耦合）
- 消息传递系统、
  - 直接通信方式
  - 间接通信方式
- 管道通信
常用的通信方式：
- 命名管道
- 套接字
- 远程过程调用

# 第四章调度与死锁

调度类型与准则
- 调度的类型
  - 高级调度：决定哪个程序可以进入系统中处理
  - 中级调度：管理挂起与解挂。实质是内存管理中的对换功能
  - 低级调度：最基本的调度，管理谁能拿到处理机
- 调度的性能准则
  - 面向用户
    1. 响应时间快
    2. 周转时间短
    3. 优先权准则
  - 面向系统
    1. 系统吞吐量
    2. 处理机利用率
    3. 各类资源平衡利用
周转时间

# 调度算法

先来先服务FCFS
- 没啥好说的，就是谁先来谁先做。。
- 特点：有利于长作业，对短作业不利
短作业优先算法SJF
- 从后备队列中选择估计时间最短的，一直做直到做完或有什么被终止
- 特点：不利于长作业，紧急事件得不到处理。
时间片轮转算法
- 进程按FCFS在就绪队列排队，调度程序把CPU分配给队首进程，令其执行一个时间片，一个时间片执行完毕将进程排在队尾。
- 保证用户键入的常用命令能在一个时间片内处理完毕
优先权调度算法
- 从后备队列中选择若干优先权最高的作业，将它们调入内存。
- 或从就绪队列中选择优先权最高的进程，将处理机分配给它。
- 特点：综合考虑各种情况
多级反馈队列
死锁的基本概念
- 一组竞争系统资源or相互通信的进程互相“永久”阻塞（参考哲学家问题）
- 死锁的产生原因：
  - 资源数 < 要求该种资源的进程数
  - 进程的推进顺序非法
- 产生死锁的四个必要条件
  - 互斥，请求保持，不剥夺，环路条件

# 死锁的预防与避免

预防
- 资源有序分配：要求进程一次性申请所有所需资源。缺：延迟，资源浪费，未知性
- 占有某些资源的进程请求被拒绝之后，立即停止运行并释放所有资源。缺：延迟巨大，增加系统开销
- 令所有进程排队并赋予序号，顺序执行。缺：不利于插入新进程
避免
- 安全状态的引入：指系统至少存在一个安全序列，按照这个序列为进程分配资源，直到满足最大需求，每个进程都能顺利完成。
- 反之，如果资源不够，系统则处于不安全状态。

# 银行家算法（死锁的避免）

首先明确几个变量的语义：
- Resource[] 系统中每种资源的总量
- Available[] 未分配的煤种资源总量
- Need[][] 每个进程还需要的各类资源数
- Allocation[][] 当前分配情况
死锁的检测与解除
- 检测
  - 资源分配图
- 解除
  - 发现死锁时，要么剥夺资源，要么撤销进程。撤销进程的代价比较小。

# 第五章存储管理

# 程序装入和链接

装入
- 重定位：把用户程序中的逻辑地址换成主存中的物理地址。
- 静态重定位：编译时产生逻辑地址，装入程序的时候进行重定位，直接写入全部的物理地址。
- 动态重定位：编译时产生逻辑地址，装入的时候先装入逻辑的，等真正要执行的时候再转成物理地址。
链接
- 静态链接：对逻辑地址修改
- 装入动态链接：装入内存的时候边装边链接
- 运行动态链接：运行到哪个模块再链接

# 连续分配存储管理方式

单一连续分配
固定分区分配
可变分区分配
- 首次适应法
- 下次适应法
- 最佳适应法
- 最坏适应法

# 页式存储管理（重点）

页表组成：页号+块号
在为进程分配内存时，以块为单位，将进程中的若干页分别装入多个可以不相邻的块中。
页的大小由机器的地址结构决定，且是固定的。
逻辑地址分为3两个部分：页号和页内位移。页号占6位，页内位移占10位
逻辑地址和物理地址的关系：(逻辑地址)a*1024+b, 转物理地址，只需要把a换成这一页对应的块号即可。
快表（了解）：其实本质就是缓存

# 段式存储管理（重点）

短标组成：段长+基址
整个作业的地址空间被分成若干个段，每个段采用一段连续的地址空间，段的长度由相应的逻辑信息的长度决定。
逻辑地址里分两个部分，段表始址和段长。
逻辑地址和物理地址：逻辑地址转物理地址，只需要基址+段始址就好。

# 分页和分段的区别

分页和分段的目的
- 页是信息的物理单位，分页是系统管理的需要，而不是用户的需要。
- 段是信息的逻辑单位，它含一组意义完整的信息。分段是为了更好地满足用户的要求。
页和段长度
- 页的大小固定，由系统确定。
- 段的长度不固定，决定于用户所编写的程序。
地址空间
- 分页的作业地址空间是一维的，即单一的线性地址空间。
- 分段的作业地址空间是二维的，程序员在标识一个地址时，需给出段名和段内地址。

# 段页式存储管理

分页系统能有效地提高内存的利用率——解决外部碎片问题。
分段系统则能更好地满足用户编程的需要——解决段的共享、动态连接等问题。
将两者结合起来，汲取两着的优点，产生段页式存储管理

# 第六章虚拟程序管理

# 概念和引入

虚拟存储器特征
- 离散性多次性对换性虚拟性

# 请求页式存储管理

缺页中断机构
地址变换机构
驻留集管理
- 定义：即在某段时间间隔内，进程实际要访问的页面的集合。
- 固定分配、局部置换
- 可变分配、全局置换
- 可变分配、局部置换
置换算法
- 最佳置换算法OPT
- 先进先出置换算法FIFO
  - 先进入内存的页被先置换出去
- 最近最久未使用置换算法LRU
- CLOCK置换算法
  - LRU的改进版（LRU实现困难）

# 请求段式存储管理

段表的补充
动态链接：
- 装入时动态链接：在装入内存时，边装入边链接
- 运行时动态链接：运行时，用到哪个模块，再链接哪个模块，用不到的模块可不装入内存。

# 抖动

产生：同一程序系统被系统多次吞吐
预防
- 加载控制
- L=S准则
- 局部置换
- 挂起若干进程

# 第七章设备管理

# IO设备管理概述

IO管理功能：监视设备状态，进行设备分配，完成IO操作，缓冲管理

# IO控制方式

程序直接控制：忙-等待方式
中断驱动：缺点：中单次数增加会造成cpu无法及时处理，数据丢失
DMA控制：
- 特点：
  1. 传输基本单位是数据块
  2. 传送数据直接送入内存
  3. 只在传送开始或结束时需要cpu干预
通道方式：
- 通道是DMA PLUS
- 当需要一次读多个离散数据块并送往不同内存区域时，通道一次就可以完成。
- 通道由一系列通道指令构成。

# 磁盘管理

磁盘的访问
磁盘调度算法
- 先来先服务FCFS
  - 优点：简单，公平
  - 缺点：平均寻道时间长
- 寻道最短SSTF
  - 优点：寻道优化
  - 缺点：饥饿现象
- 扫描算法SCAN和CSCAN
  - SCAN：SSTF PLUS，优先考虑磁盘移动方向，再考虑移动距离。又称电梯调度算法
  - CSCAN：解决SCAN进程严重延迟。

# 文件管理

文件
- 定义：具有文件名的一组相关信息集合
- 结构：有结构文件，无结构文件
文件类型：
- 用途分：系统文件，用户文件，库文件
- 性质分：普通文件，目录文件，特殊文件
- 属性分：可执行文件，只读文件，读/写文件
- 数据形式分：源文件，目标文件，可执行文件
- 逻辑结构分：有结构，无结构
- 物理结构分：连续文件，链接文件，索引文件
文件系统
- 定义：含有大量文件及其属性说明、对文件进行操纵和管理的软件，以及向用户提供的使用文件接口的集合。
- 结构
目录
- 类型：
  - 单极目录：查找速度慢，不允许重名，不便于共享
  - 二级目录：提高文件检索速度，允许重名，不易共享。
  - 树形目录：主目录为根结点，数据文件为叶子节点。
- 功能：
  1. 按名存取
  2. 提高目录检索速度
  3. 允许文件同名
  4. 文件共享
文件存储结构
- 外存分配
  1. 连续分配：优：便于顺序访问且快。缺：要有连续的存储空间
  2. 链接分配：优：解决文件动态增长。缺：随机访问低效
  3. 索引分配：优：解决动态增长，支持文件随机访问。缺：增加存储空间开销
  4. 混合分配：优：
空闲存储空间的管理
- 空闲表
- 空闲链
- 位示图
- 成组链接法：空闲表+空闲链

yuiyake

操作系统复习与总结

操作系统复习与总结

# 操作系统

# 第一章 操作系统引论

# 基本概念

# 操作系统的类型

# 第二章 进程管理

# 进程的引入

# 进程的状态及其组成

# 进程的控制

# 线程

# 第三章 进程同步与通信

# 进程同步与互斥

# 经典进程同步问题

# AND信号量

# 进程通信

# 第四章 调度与死锁

# 调度算法

# 死锁的预防与避免

# 银行家算法（死锁的避免）

# 第五章 存储管理

# 程序装入和链接

# 连续分配存储管理方式

# 页式存储管理（重点）

# 段式存储管理（重点）

# 分页和分段的区别

# 段页式存储管理

# 第六章 虚拟程序管理

# 概念和引入

# 请求页式存储管理

# 请求段式存储管理

# 抖动

# 第七章 设备管理

# IO设备管理概述

# IO控制方式

# 磁盘管理

# 文件管理

# 第一章操作系统引论

# 第二章进程管理

# 第三章进程同步与通信

# 第四章调度与死锁

# 第五章存储管理

# 第六章虚拟程序管理

# 第七章设备管理