操作系统

概述

  • 管理系统的硬件、软件、数据资源
  • 控制程序运行
  • 人机之间的接口
  • 应用软件与硬件之间的接口

系统分类

批处理操作系统

分时操作系统

实时操作系统

网络操作系统

分布式操作系统

微型计算机操作系统

嵌入式操作系统

进程管理

进程的状态

进程状态

三态模型

  • 运行
  • 等待
  • 就绪（静止就绪、活跃就绪）
    其他所有资源已经配足了，只欠缺CPU资源

五态模型

  • 运行
  • 活跃就绪
  • 静止就绪
  • 静止阻塞
  • 活跃阻塞

前趋图

试图表达进程间的先后约束关系

进程的同步与互斥

互斥

两个或两个以上的进程，不能同时进入关于同一组共享变量的临界区域，否则可能发生与时间有关的错误，这种现象被称作进程互斥· 也就是说，一个进程正在访问临界资源，另一个要访问该资源的进程必须等待。

同步

进程之间速度有差异，需要在一定情况停下等待

PV操作（生产者、消费者）

P(S)指消费者操作，请求分配一个资源
V(S)指生产者操作，释放一个资源
临界资源：诸进程间需要互斥对其进行共享的资源，如打印机、磁带机
临界区：每个进程中访问临界资源的那段代码成为临界区
信号量：是一种特殊的变量

死锁问题

进程管理是操作系统的核心，如果设计不当，就会出现死锁的问题。如果一个进程在等待一件不可能发生事，则进程
就死锁了。而如果一个或多个进程产生死锁，就会造成系统死锁。

死锁的预防

  • 打破四大条件：互斥、环路等待、不剥夺、保持和等待

死锁的避免

  • 有序资源分配法

  • 银行家算法
    分配资源的原则：当一个进程对资源的最大需求量不超过系统中的资源数时可以接纳该进程
    进程可以分期请求资源，但请求的总数不能超过最大需求量
    当系统现有的资源不能满足进程尚需资源数时，对进程的请求可以推迟分配，但总能使进程在有限的时间里得到资源

需先计算出系统在给所有进程分配完之后，还剩下多少资源，并计算每个进程还需多少资源数，然后进行比较

进程调度算法

批处理时代

FCFS

（First Come FIrst Serve）先来先服务算法
缺陷：短进程响应时间太长，用户交互体验较差。

SPN

（Shortest Processer Next）短任务优先
缺陷：短进程一直加入队列，长进程永远得不到执行的机会。

HRRN

（Highest Response Ratio Next）高响应比优先
公式：响应比=（等待时间+要求服务时间）/要求服务时间
每次调度前都要重新计算所有等待进程的响应比，工作量增加，但是进程可以公平执行了。

并发时代

RR

（Round Robin）时间片轮转算法
每个进程轮流使用CPU算法，每个进程都有相同的时间片，指定时间到后，进程将被迫下机。
缺陷：时间片越短，固定时间里可运行的进程就越多，但是切换进程也需要消耗CPU的指令周期，因此时间片过短会导致大量CPU资源浪费在切换上下文上。时间片

存储管理

分区存储组织

动态分区分配

首次适应算法

从空闲分区链首开始查找，直至找到一个能满足其大小的分区。

最佳适应算法

先将空闲区按照大小排序，找到能满足其要求的最小的空闲分区。

最差适应算法

将所有空闲分区按照大小排序，将作业放至与作业所需空间相差最大的空间的空闲分区。

循环首次适应算法

不从空闲区链首开始查找，而是从上一次查找的位置的下一个空闲开始查找，直到找到一个能满足其大小的分区。

快速适应算法

段页式存储

页式存储

  • 优点：利用率高，碎片小，分配及管理简单
  • 缺点：增加了系统开销，可能产生抖动现象
    高级程序语言使用逻辑地址；运行状态，内存中使用物理地址。

页面置换算法

缺页中断：进程线性地址空间里的页面不必常驻内存，在执行一条指令时，如果发现他要访问的页中没有在内存中，那么停止该指令的执行，并产生一个页不存在的一场，对应的故障处理程序可以通过从外存加载该页的方法来排除故障，之后，原先引起异常的指令就可以继续执行，而不再产生异常。
需要的页不在内存中时，即为缺页中断

页面置换最佳淘汰算法(OPT)

从主存中移除永远不再需要的页面；如无这样的页面存在，则选择最长时间不需要访问的页面，这样可以保证最低的缺页率。但是因为要预测之后最长时间不再访问的页面，因此需要有个东西。

随机算法

随即淘汰一个页面

先进先出淘汰算法(FIFO)

淘汰最先进入内存的页面。

最近久未使用淘汰算法(LRU)

淘汰内存中最久未使用的页面。观察之前最久未使用的页面

文件管理

文件结构

索引结构

标准结构十三个索引结点（0~12）
0~9 前十个节点为直接索引
10 结点存物理盘块地址
11 结点

设备管理

数据传输控制方式

程序控制方式

优点：过程简单。
缺点：CPU利用率相当低。由于CPU速度远远快于I/O设备，致使绝大部分时间都在测试I/O设备是否已经完成数据传输，从而造成CPU的极大浪费。

程序中断方式

优点：有了中断硬件的支持后，CPU与I/O设备之间可以并行工作，CPU只需要收到中断后处理即可，大大提高了CPU利用率。

缺点：如果每台设备每输入/输出一个数据，都要求中断CPU，这样在一次数据传送过程中的中断次数太多，从而耗费大量CPU时间。
I/O完成时发出的中断处理程序的处理过程如下：
1、唤醒被阻塞的驱动（程序）进程；
2、保护被中断进程的CPU环境；
3、转入想要的设备处理程序；
4、中断处理，执行中断处理程序；
5、恢复被中断进程的现场。

DMA方式

优点：设备和CPU可以并行工作，同时设备与内存的数据交换速度更快，并且不需要CPU干预。

缺点：数据传送的方向、存放输入数据的内存起始地址及传送数据的长度等都由CPU控制，并且每台设备都需要一个DMA控制器，当设备增加时，多个DMA控制器的使用也不经济。

通道控制方式

虚设备与SPOOLING技术

对于多个输入设备，将输入的任务放到输入缓冲区当中，并以输入进程，输入到输入井，再从输入井一次输出。

作业管理