思维导图，不存在的

操作系统

看图，其他掠过
1 操作系统定位

2 操作系统作用

• 作为用户和计算机间的接口
• 作为实现计算机系统资源的管理者
• 实现了对计算机资源的抽象

3 操作系统分类
批处理系统、分时操作系统、实时操作系统、网络操作系统、分布式操作系统
4 操作系统的功能（2.2）
处理机管理功能、存储器管理功能、设备管理功能、文件管理功能、用户接口

处理机管理

又称进程管理（4.1）
进程
1 进程概念：程序关于某个数据集合的一次执行过程
2 进程特征
1）结构：进程控制块（PCB）+程序+数据=进程实体
2）动态性：进程是实体的一次执行过程，有生命周期
                    程序是一组有序指令的集合，是静态的
3 进程的三种基本状态
就绪态 万事俱备，只欠CPU
运行态 正在CPU执行
阻塞态/等待态 正执行的进程由于发生某事而无法执行

4 进程的互斥与同步
1）进程制约关系
  间接相互制约关系--资源共享(临界/独占资源，如打印机)
  直接相互制约关系--进程合作（访问同一变量，如仓库的卖生产者和消费者）
5 临界资源
1）临界资源：把一段时间内只允许一个进程访问的资源称为临界资源或独占资源
2）临界区：每个进程中访问临界资源的那段代码

信号量

6 信号量机制
1）信号量使所有的进程互斥的访问临界资源
2）信号量是当前可使用资源数（大于零时），小于零阻塞
7 信号量的应用
1）利用信号量实现进程互斥
信号量为资源个数
2）利用信号量实现前驱关系

• 信号量0
• 进程p1在p2前执行

进程p1 S1;
       signal(S);  V(S)
进程p2 wait(S);  P(S)
                 S2; 

3） 利用信号量实现同步
确保存取不同时执行，两个变量

进程调度

进程调度：决定哪个CPU获得处理机，所有操作系统都有
8 调度方式
1）非抢占方式
当前进程完成，才能执行其他进程
简单、开销小，仅适合批处理OS
2）抢占方式
根据某一原则，抢占正在执行的进程的CPU
抢占原则：时间片原则、短作业（进程）优先原则、优先权原则
9 调度算法
1）先来先服务FCFS
  永远给队首的作业，利于长作业，不利于短作业
2）短作业优先SJ（P）F
  同一时间谁短谁先来
  降低平均等待时间，对长作业不利，未考虑紧迫程度，估计的作业时间（不一定做到短作业优先）
3）高优先权优先
  静态优先权：创建进程时确定，值越小优先级越高
  动态优先权：创建进程时的优先级在运行过程中变化
  如 高响应比优先算法
    优先权=（等待时间+要求服务时间）^{即系统响应时间}/要求服务时间（值越大优先级越高）
等待时间相同，利于短作业；要求服务时间相等，先来先服务；长作业
4）时间片轮转
  时间片结束，进程未完成置于队尾；时间片内进程结束或阻塞，CPU切换。

死锁

10 死锁概念：运行过程中因争夺资源而造成的僵局，无外力作用则无法继续执行
11 死锁产生原因
1）竞争资源不足
  资源分类：
    可剥夺性资源：高优先级进程抢占，如CPU、主存
    不可剥夺性资源：（临界资源）必须进程用完后才能释放，如磁带、打印机
  只有不可剥夺性资源才会引起死锁
2）进程间推进顺序非法
12 产生死锁必要条件
1）互斥条件
  进程访问的是临界资源，其他进程只能等待当前进程完成
2）请求和保持条件
  进程在请求新资源的同时，保持对已有资源的占有
3）不剥夺条件
进程获得的资源，只能由进程使用完成后主动释放
4）环路等待条件
发生死锁时，必定存在一个进程-资源环（互相等待对方资源）
13 处理死锁
1）预防死锁
  事先预防，破坏产生思索的一个或几个条件（互斥条件除外）
2）避免死锁
  银行家算法、采取事先预防的策略，防止系统进入不安全状态
3）检测死锁（检查）
4）解除死锁（有则改之）
  撤销或挂起一些进程再将这些进程分配给阻塞状态的进程
  有可能是系统获得较好的资源利用率和吞吐率，但难度较大

内存管理

1 主要指对内存的管理，负责内存分配和回收，内存的保护和扩充
2 目的：尽量提高内存的使用率
3 分配方式

• 连续的分配方式
  用户程序分配在连续的内存空间

1）单一连续分配
DOS 分为操作系统和用户，且只能分配给一个作业（单用户单任务）
2）固定分区分配
分为操作系统和若干个大小不等的区域（按作业大小分配，每个区域存在浪费（内缺陷））
3）动态分区分配
分为操作系统和用户区域，来一个划出一部分空间
首次适应算法（从低地址开始找能盛下作业的空闲分区，划出）
循环首次适应算法（从上次分配过的地方往下搜寻）
最佳适应算法（找出与作业差值相差最小的（把分区按从小到大的顺序排序），太小会无法分配，产生外缺陷）
最坏适应算法（找出与作业差值相差最大的）
4）可重新定位分区分配
把内存中所有作业向低地址移动，使他们全部临界，原来的小分区变成大分区（拼接）
对换
1 概念：把内存中暂时不能运行的进程或暂时不能使用的程序、数据，调到外存，把具备运行条件的从外存调用内存
2 分类
1 整体对换：整个进程为单位对换
2 页内对换/分段对换 以页或段为单位
离散分配方式
允许将一个进程直接分散的装入许多不相邻的分区中
1 分类
分页存储管理方式
1 分页式存储管理的原理
页面
将一个进程分为若干个大小相等的片称为页面或页（暑假数学作业，有5张卷子）；加以编号（从0开始）（分别为数学1、数学2..）；把内存空间分配成与页面相同大小的若干个存储块，称为块或页框(页和块大小相同)（里面为许多透明袋档案袋（一个透明袋可以装一份卷子））
将卷子随机装入这些透明袋中（多个不相邻的物理块），进程的最后一页经常装不满一块而形成页内碎片
地址变换

实现
页表 实现了从页号到物理块号的地址映射

地址变换机构实现了从逻辑地址到物理地址的转换

所以物理地址= b x 页大小/块大小+页内地址
具有块表的地址变换机构
访问两次内存（访问页面，计算物理地址；根据物理地址找数据）
存取器利用率高，CPU处理速度低

分段存储管理方式
段表 作用类似页表，区别（组成）：段号；段在业内中的起始地址；段长

段页式存储管理方式

页面置换算法

• 最佳置换算法
  性能最好，最难实现：选以后再也不用的或未来最长时间不用的

可以用来衡量其他算法，与此算法越接近越好

• 先进先出（FIFO）置换算法 最直观，性能最差，可能会出现踢出先进（经常使用的页面）的
• 最近最久未使用（LRU）
  过去预测未来，为每个页面增加一个访问字段，访问一次，字段值加1

设备管理

I/O系统组成：输入、输出设备；存储功能的设备；设备控制器
1 设备管理概念

• 设备管理程序功能
  1）提供和进程管理系统的接口

2）进行设备分配
3）实现设备和设备之间、设备和CPU之间的并行操作
4）进行缓冲区管理
2 I/O控制方式
1）程序I/O方式
2）中断控制方式
3）直接存储器访问（DMA）方式 分块传
4）I/O通道（专门小型CPU）控制方式

       字节多路通道
       选择通道
       成组多路通道

3 缓冲管理
1）单缓冲 类似 生产者-消费者
2）双缓冲
要求输入输出速度匹配 两个桶（始终有桶在接水）交替倒水
常用3 4
3）循环缓冲
n个大小相同的缓冲区，分为

   装入数据的空缓冲区R
   装满数据的缓冲区G
   正在输出的缓冲区C(绕成圈)

4）缓冲池
既可输入又可输出的公用缓冲池，分为

   空缓冲区
   装满输入数据的缓冲区
   装满输出数据的缓冲区

4 引入缓冲目的
1）缓和CPU与I/O设备之间的速度不匹配
2）减少CPU的终端频率，放宽对CPU中断响应的时间限制
3）提高CPU和I/O设备之间的并行性
5 设备分配
1）设备分配原则
静态分配 运行前分配好，不会造成死锁
动态分配 需要时提出申请（按需分配），易造成死锁
2）设备分配策略
先请先分配、优先级高者先分配

磁盘管理

6 磁盘

存储位置：由柱面号（磁道号）、盘面号（第几个磁盘）（磁头号）、扇区组成
7 磁盘访问时间（1+2+3）
1）寻道时间Ts：把磁臂从当前位置移到指定磁道上所经历的时间
2）旋转延迟时间Tr：市面流通10000转/min 7200转/min 5200转/min，指定扇区移动到磁头下面所经历的时间
1 2 机械结构时间，占比大；集中有利于减少此时间
3）传输时间Tt：数据从磁盘都出或向磁盘写u他数据所经历的时间 电气时间
8 磁盘调度算法
1）先来先服务（FCFS）
2）最短寻道时间优先SSTF
优先满足与磁头最近，会出现进程饥饿（离磁头远的得不到满足），平均时间不一定最短
3）扫描（SCAN）算法（电梯调度算法）
从初始磁道开始，向磁道号递增方向访问（上楼）。然后再从大向小（下楼）
错过电梯，只能等待下来时带上自己
4）CSAN 循环扫描算法
电梯向上，降到最低，循环
9 虚设备与SPOOLing技术/假脱机技术

1）作用：提高I/O速度、将独占设备改为共享设备、实现了虚拟设备功能

文件管理

1 文件：具有文件名的若干相关元素的集合
2 文件系统
1）负责管理文件的系统软件
2）被管理的对象-文件
3 文件的结构
1）文件的逻辑结构

1 有结构的文件
    由一条条数据构成
    包括：顺序文件、索引文件、索引顺序文件、直接文件
2 无结构的文件
    由字符流构成（如mp3）
    源程序、可执行文件、库函数、mp3等，UNIX系统把所有文件都看作流式文件

2）文件的物理结构
磁盘可直接访问
外存分配方法（一个系统通常只采用一种）：

1 连续分配
   顺序文件存储，每个文件分配一组相邻的盘块，紧凑消除建立删除善生的碎片
2 链接分配
  链接文件：通过每个盘块上的链接指针，将一个文件的多个离散的盘块链接成一链表
  缺点：不支持高效存取、FAT占用内存较大
3 索引分配
   单级索引
   多级索引
   混合索引

3 磁盘的空间管理
1）空闲表法 空闲链表法
2）位视图法
用一个位表示磁盘块的空闲状态
如 用0表示未使用，1表示已使用

0-31是第一个字
4096/32=128
200 x 1024x1024/1 x 1024 x 32 =6400
3）成组链接法

作业管理

1 作业状态
批处理型作业经历：提交 后备 执行 完成
2 调度层次
1）高级调度/作业调度/长程调度
决定后备队列中哪几个作业调用内存，仅用于多道批处理系统，周期最长
2）中级调度/对换调度
提高内存利用率和系统吞吐率。将不用的从 内存调出外存，用的调回来
3）低级调度/进程调度/短程调度
根据某种算法，决定就绪队列中的哪个进程应获得CPU，分给他，基本调度，应用于所有系统（多道批处理系统、分时、实时），周期最短
3 调度算法
先来先服务、短作业优先、高优先权优先、高响应比优先
4 用户接口
操作系统接口：命令接口、程序接口