操作系统

操作系统的概述

操作系统的作用：通过资源管理提高计算机系统的效率；改善人机界面向用户提供友好的工作环境
操作系统的特征：
- 并发性
- 共享性
- 虚拟性
- 不确定性
操作系统的功能：
- 进程管理
- 存储管理
- 文件管理
- 设备管理
- 作业管理
操作系统的分类：
- 批处理操作系统
- 分时才做系统(轮流使用CPU工作片)
- 实时操作系统
- 网络操作系统
- 分布式操作系统(物理分散的计算机互联系统)
- 微机操作系统(Windows)
- 嵌入式操作系统
计算机启动的基本流程为：BIOS –> 主引导记录(CD、USB、硬盘等) –> 操作系统

进程管理

进程的组成和状态

进程是计算机中正在运行程序的实例。它是操作系统进行资源分配和管理的基本单位，包括代码、数据和执行状态等信息。

进程的组成:
- 进程控制块(PCB)
- 程序(描述进程要做什么)
- 数据(存放进程执行时所需数据)

进程基础的状态是下左图中的三态图，这是系统自动控制时只有三种状态，就绪态、运行态、等待态。
而下右图中的五态，是多了两种状态：静止就绪和静止阻塞，需要人为的操作才会进入对应状态，活跃就绪即就绪,活跃阻塞即等待。

可知，当人为干预后，进程将被挂起，进入静止状态，此时，需要人为激活，才能恢复到活跃状态，之后的本质还是三态图。

前趋图

前趋图：用来表示哪些任务可以并行执行，哪些任务之间有顺序关系，具体如下图：

可知，ABC可以并行执行，但是必须ABC都执行完成后，才能执行D，这就确定了两点：任务间的并行、任务间的先后顺序。

进程资源图

进程资源图：用来表示进程和资源之间的分配和请求关系，如下图所示：

P代表进程，R代表资源，R方框中有个圆球就表示有几个这种资源，
在图中，R1指向P1，表示R1有一个资源已经分配给了P1,
P1指向R2，表示P1还需要请求一个R2资源才能执行。

阻塞节点：
- 某进程所请求的资源已经全部分配完毕，无法获取所需资源，该进程被阻塞了无法继续。
- 如上图P2
非阻塞节点：
- 某进程所请求的资源还有剩余，可以分配给该进程继续运行。
- 如上图P1,P3.
- 当一个进程资源图中所有进程都是阻塞节点时，即陷入死锁状态。

例：在如下所示的进程资源图中，哪些是阻塞节点，那些是非阻塞节点;该进程资源图可以简化吗？

P1、P2是阻塞节点、P3是非阻塞节点
可以简化的,其化简顺序为：P3->P2->P1 OR P3->P1->P2
注意：只要每一个进程都进入阻塞即进入死锁状态
只要有非阻塞节点，就是可以化简的，非阻塞的在前(即最先运行，运行完释放资源给阻塞节点用)。

同步与互斥

互斥: 某资源(即临界资源)在同一时间内只能由一个任务单独使用，使用时需要加锁，使用完后解锁才能被其他任务使用；如打印机。
同步：多个任务可以并发执行，只不过有速度上的差异，在一定情况下停下等待，不存在资源是否单独或共享的问题；如自行车和汽车。
临界资源：各进程间需要以互斥方式对其进行访问的资源。
临界区：指进程中对临界资源实施操作的那段程序。本质是一段程序代码。
互斥信号量：对临界资源采用互斥访问，使用互斥信号量后其他进程无法访问，初值为1.
同步信号量：对共享资源的访问控制，初值一般是共享资源的数量。

信号量

P操作：申请资源，S = S - 1，若S >= 0,则执行P操作的进程继续执行；若S < 0,则置该进程为阻塞状态(因为无可用资源)，并将其插入阻塞队列。
V操作：释放资源，S = S + 1，代表此时资源有空余，没有阻塞的进程，则该进程继续执行；
- 若S <= 0，代表此时线程在被阻塞，所以需要从阻塞状态唤醒一个进程，并将其插入就绪队列(此时因为缺少资源被P操作阻塞的进程可以继续执行)，然后执行V操作的进程继续。

死锁

当一个进程在等待永远不可能发生的事件时，就会产生死锁，若系统中有多个进程处于死锁状态，就会造成系统死锁。

死锁产生的4个必要条件：

资源互斥
每个进程占有资源并等待其他资源
系统不能剥夺进程资源
进程资源图是一个环路

死锁产生后，解决措施是打破四大条件，有下列方法：

死锁预防：采用某种策略限制并发进程对资源的请求，破坏死锁产生的四个条件之一，使系统任何时刻都不满足死锁的条件。
死锁避免：一般采用银行家算法来避免，银行家算法，就是提前计算出一条不会死锁的资源分配方法，才会分配资源，否则不分配资源，
相当于借贷，要考虑对方还得起才会借钱，提前考虑好以后，就可以避免死锁。
死锁检测：允许死锁产生，但系统定时运行一个检测死锁的程序，若检查测到系统中发生死锁，则设法加以解除。
死锁解除：即死锁发生后的解除方法，如强制剥夺资源，撤销进程等。

死锁计算问题：系统内有n个进程，每个进程都需要R个资源，那么发生死锁的最大资源数为n * (R - 1)。其不发生死锁的最小资源数为n * (R - 1) + 1。

例：某系统中有3个并发进程竞争资源R，每个进程都需要5个R，那么至少有 3 * (5 - 1) + 1 = 13 个进程才能避免发生死锁。

线程

传统的进程有两个属性：可拥有资源的独立单位；可独立调度和分配的基本单位。
引入线程后，线程是独立调度的最小单位，进程是拥有资源的最小单位，线程可以共享进程的公共数据、全局变量、代码、文件等资源，
但不能共享线程独有的资源，如线程的栈指针等标识数据。

页式存储

页式存储是操作系统的一种存储管理方式。

因为我们的程序往往是远远大于内存的，所以程序在执行的时候，是不会一次性把所有内润都装入到内存中，它会把程序分为若干个页,
每个页固定大小，一般是4k,然后把这些页离散存入到内存中，而内存是按块来划分的，所以就通过页表来进行映射程序中页在内存中的块的存储。

进程(程序)中的地址，我们称之为逻辑地址(虚地址)，而内存中的地址我们称之为物理地址(实地址)

每个页分为页号和页内地址，页号用来和块号对应，代表存储的位置，大小可以代表页的数量，页内地址代表的是存储的数据内容，大小可以代表数据大小

优点:利用率高、碎片小(旨在最后一个页中有)、分配及管理简单。
缺点:增加了系统开销，可能产生抖动现象。

页面置换算法

有时候，进程空间分为100个页面，而系统内存只有10个物理块，无法全部满足分配，就需要将马上要执行的页面先分配出去，
而后根据算法进行淘汰，使100个页面能够按执行顺序调入物理块中执行完。

缺页表示需要执行的页不在内存物理块中，需要从外部调入内存，会增加执行时间，因此，缺页数越多，系统效率越低。

最优算法: OPT,理论上的算法，无法实现，是在进程执行完后进行的最佳效率计算，用来让其他算法比较差距。
原理是选择未来最长时间内不被访问的页面置换，这样可以保证未来执行的都是马上要访问的。
先进先出算法：FIFO，先调入内存的页先被置换淘汰，会产生抖动现象，即分配的页数越多，缺页率可能越多(即效率越低)
最近最少使用：LRU，在最近的过去，进程执行过程中，过去最少使用的页面被置换淘汰，根据局部性原理，这种方式效率高，且不会产生抖动现象。

快表

快表是一块小容量的相联存储器，由快速存储器组成，按内容访问，速度快，并且可以从硬件上保证按内容并行查找，
一般用来存放当前访问最频繁的少数活动页面的页号(可以看成是页表的频繁访问数据的副本)

快表是将页表存于Cache中；慢表是将页表存于内存上。因此慢表需要访问两次内存才能取出数据，而快表是访问一次Cache和一次内存，因此更快。

段式存储

段式存储是将进程空间分为一个个段，每段也有短号和段内地址，与页式存储不同的是，每段物理大小不同，分段是根据逻辑整体分段的。

地址表示：(段号,段内偏移):其中段内偏移不能超过该段号对应的段长，否则越界错误，
而此地址对应的正真内存地址应该是：段号对应的基地址 + 段内偏移。

优点：程序逻辑完整，修改互不影响内存利用率低。
缺点：内存碎片浪费大

段页存储

对进程空间先分段，后分页，具体原理图和优缺点如下：
优点：空间浪费小、存储共享容易、能动态连接，程序逻辑完整，修改互不影响。
缺点：由于管理软件的增加，复杂性和开销也增加，执行速度下降，内存利用率低，内存碎片大。

设备分类

设备的分类方式：

按数据组织分类：块设备、字符设备。
资源分配角度分类：独占设备、共享设备和虚拟设备。
数据传输速率分类：低速设备、中速设备、高速设备。

I/O软件层次结构：

输入输出

程序控制(查询)方式：CPU主动查询外设是否完成数据传输，没传输完，CPU就一直等待，效率极低。
程序中断方式：外设完成数据传输后，向CPU发送中断，等待CPU处理数据，比如一个1G的数据，每次传输32k就向CPU发起中断，
让CPU来处理，效率相对较高。适用于键盘等实时性较高的场景。
- 中断响应时间指的是从发出中断请求到开始进入中断处理程序；
- 中断处理时间指的是从中断处理开始到中断处理结束。
DMA方式(直接主存存取)：CPU只需完成必要的初始化等操作，数据传输的整个过程都由DMA控制器来完成，在主存和外设之间建立直接的数据通路，效率很高。适用于硬盘等高速设备。

在一个总线周期结束后，CPU会响应DMA请求开始读取数据；CPU响应程序中断方式请求是在一条指令执行结束时；
区分指令执行结束和总线周期结束。
注意：还有两种方式分别是通道和IO处理机，基本不考，了解即可。

虚设备和SPOOLING技术

一台实际的物理设备，例如打印机，在同一时间只能由一个进程使用，其他进程只能等待，且不知道什么时候打印机空闲，此时，极大的浪费了外设的工作效率。

引入SPOOLING技术，就是在外设上建立两个数据缓冲区，分别称为输入井和输出井，这样无论多少进程，
都可以公用这一台打印机，只需要将打印命令发出，数据就会排队存储在缓冲区中，打印机会自动按顺序打印，
实现了物理外设的共享，是每个进程都感觉在使用一个打印机，这就是物理设备的虚拟化。
如下图：

磁盘结构

磁盘有正反两个盘面，每个盘面有多个同心圆，每个同心圆是一个磁道，每个同心圆又被划分多个扇区，数据就被存放在一个个扇区中。
读取数据时，磁头首先要寻找到对应的磁道，然后等待磁盘进行周期旋转，旋转到指定的扇区，才能读取到对应的数据，
因此，会产生寻道时间和等待时间，就是磁头移动到磁道所需的时间和等待读写的扇区转到磁头的下方所用的时间。
其中寻道时间耗时最长，寻道时间的的调度算法如下：

先来先服务FCFS：根据进程请求访问磁盘的先后顺序进行调度。
最短寻道时间优先SSTF：请求访问的磁道与当前磁道最近的进程优先调度，使得每次的寻道时间最短。会产生饥饿现象，即远处进程可能永远无法访问。
扫描算法SCAN：又称电梯算法，磁头在磁盘上双向移动，其会选择离磁头当前所在磁道最近的请求访问的磁道，并且与磁头移动方向一致，
磁头永远都是从里向外或者从外向里一直移动完才掉头，与电梯类似。
单向扫描调度算法CSCAN：与SCAN不同的是，其只做单向移动，即只能从里向外或者从外向里。

文件管理

文件结构

计算机系统中采用的索引文件结构如下图所示：
系统中有13个索引节点，0-9为直接索引，即每个索引节点存放的是内容，假设每个物理盘大小为4KB，共可存4KB*10=40KB的数据;
10号索引节点为一级间接索引节点，大小为4KB，存放的并非直接数据，而是链接到直接物理盘块的地址，假设每个地址占4B,
则共有1024个地址，对应1024个物理盘，可存1024*4KB=4098KB数据。

二级索引节点类似，直接盘存放一级地址，一级地址再存放物理盘快地址，而后链接到存放数据的物理盘快，容量又扩大了一个数量级，为102410244KB数据

树形文件

相对路径：是从当前路径开始的路径。
绝对路径：是从根目录开始的路径。
全文件名 = 绝对路径 + 文件名。要注意，绝对路径和相对路径是不加最后的文件名的，只是单纯的路径序列。
树形结构主要是区分相对路径和绝对路径，如下图所示：

空间存储

空闲区表法：将所有空闲空间整合成一张表，即空闲文件目录。
空闲链表法：将所有空闲空间链接成一个链表，根据需要分配。
成组链接法：即分组，每组内又链接成链表，是上述两种方法的综合。
位示图法：对每个物理空间用一位表示，为1则使用，为0则空闲，形成一张位示图。

作业状态

作业：系统为完成一个用户的计算任务（或一次事务处理）所做的工作总和。例如，对用户编写的源程序，需要经过
编译、连接、装入以及执行等步骤得到结果，这其中的每一个步骤称为作业步。在操作系统中用来控制作业进入、执行和撤销的一组程序称为作业管理程序。

作业状态分为4种：提交、后备、执行和完成。

提交：作业提交给计算机中心，通过输入设备送入计算机系统的过程状态为提交状态。
后备：通过Spooling系统将作业输入到计算机系统的后备存储器（磁盘）中，随时等待作业调度程序调度时的状态。
执行：一旦作业被作业调度程序选中，为其配了必要的资源，并为其建立相应的进程后，该作业便进入了执行状态。
完成：当作业正常结束或异常终止时，作业进入完成状态。此时，由作业调度程序对该作业进行善后处理。如撤销作业的作业控制块，收回作业所占的系统资源，
将作业的执行结果形成输出文件放到输出井中，由Spooling系统控制输出。

作业调度算法

常用的作业调度算法如下：

先来先服务：按作业到达的先后进行调度，即启动等待时间最长的作业。
短作业优先：以要求运行时间的长短进行调度，即启动要求运行时间最短的作业。
响应比高优先：以作业的响应比（周转时间/要求运行时间）进行调度，即启动响应比最高的作业。
优先级度算法：可由用户指定作业优先级，优先级高的作业先启动。也可由系统根据作业要求的紧迫程度，或者照顾“I/O繁忙”的作业，以便充分发挥外设的效率等。
均调度算法：这种算法的基本思想是根据系统的运行情况和作业本身的特性对作业进行分类。作业调度程序轮流地从这些不同类别的作业中挑选作业执行。这种算法力求均衡地使用系统的各种资源，即注意发挥系统效率，又使用户满意。