操作系统概述
操作系统的作用:通过资源管理提高计算机系统的效率;改善人机界面向用户提供友好的工作环境。
操作系统的特征:并发性、共享性、虚拟性、不确定性。
操作系统的功能: 进程管理、存储管理、文件管理、设备管理、作业管理。
操作系统的分类:
- 批处理操作系统、
- 分时操作系统（轮流使用CPU工作片)、
- 实时操作系统（快速响应）、
- 网络操作系统、
- 分布式操作系统（物理分散的计算机互联系统）、
- 微机操作系统（Windows）、
- 嵌入式操作系统。
计算机启动的基本流程为:BIOS->主引导记录->操作系统。
进程管理
进程的组成和状态
- 进程的组成:
- 进程控制块PCB(唯一标志）、
- 程序（描述进程要做什么）、
- 数据（存放进程执行时所需数据）。
- 进程基础的状态是下左图中的三态图，这是系统自动控制时只有三种状态，而下右图中的五态，是多了两种状态:静止就绪和静止阻塞，需要人为的操作才会进入对应状态,活跃就绪即就绪,活跃阻塞即等待。
- 可知，当人为干预后，进程将被挂起，进入静止状态，此时，需要人为激活，才能恢复到活跃状态,之后的本质还是三态图。
前趋图
前趋图:用来表示哪些任务可以并行执行，哪些任务之间有顺序关系，具体如下图:
可知，ABC可以并行执行，但是必须ABC都执行完后，才能执行D，这就确定了两点:任务间的并行、任务间的先后顺序。
进程资源图
进程资源图:用来表示进程和资源之间的分配和请求关系，如下图所示:
P代表进程,R代表资源,R方框中有几个圆球就表示有几个这种资源,在图中，R1指向P1，表示R1有一个资源已经分配给了P1，P1指向R2，表示P1还需要请求一个R2资源才能执行。
- 阻塞节点:某进程所请求的资源已经全部分配完毕，无法获取所需资源，该进程被阻塞了无法继续。如上图中P2。
- 非阻塞节点:某进程所请求的资源还有剩余，可以分配给该进程继续运行。如上图中P1、P3。
- 当一个进程资源图中所有进程都是阻塞节点时，即陷入死锁状态。
真题
在如下所示的进程资源图中,**P1、P2是阻塞节点**、P3是非阻塞节点 ;该进程资源图是可以化简的，顺序为P3->P1->P2或P3->P2->P1
同步与互斥
- 互斥:某资源（即临界资源）在同一时间内只能由一个任务单独使用，使用时需要加锁,使用完后解锁才能被其他任务使用;如打印机。
- 同步:多个任务可以并发执行，只不过有速度上的差异，在一定情况下停下等待，不存在资源是否单独或共享的问题;如自行车和汽车。
- 临界资源:各进程间需要以互斥方式对其进行访问的资源。
- 临界区:指进程中对临界资源实施操作的那段程序。本质是一段程序代码。
- 互斥信号量:对临界资源采用互斥访问，使用互斥信号量后其他进程无法访问，初值为1。
- 同步信号量:对共享资源的访问控制，初值一般是共享资源的数
量。
PV操作
- P操作:申请资源，S=S-1，若S>=o，则执行P操作的进程继续执行;
若s<0，则置该进程为阻塞状态（因为无可用资源），并将其插入阻塞队列。 - V操作:释放资源，S=S+1，若S>0，则执行V操作的进程继续执行;
若s<=0，则从阻塞状态唤醒一个进程，并将其插入就绪队列（此时因为缺少资源被P操作阻塞的进程可以继续执行），然后执行V操作的进程继续。
例题
进程调度
死锁
死锁产生的条件
- 当一个进程在等待永远不可能发生的事件时，就会产生死锁，若系统中有多个进程处于死锁状态,就会造成系统死锁。
- 死锁产生的四个必要条件:
- 资源互斥
- 每个进程占有资源并等待其他资源
- 系统不能剥夺进程资源
- 进程资源图是一个环路。
解决死锁的方法
死锁产生后,解决措施是打破四大条件，有下列方法:
- 死锁预防:采用某种策略限制并发进程对于资源的请求，破坏死锁产生的四个条件之一，使系统任何时刻都不满足死锁的条件。
- 死锁避免:一般采用银行家算法来避免，银行家算法，就是提前计算出一条不会死锁的资源分配方法，才分配资源，否则不分配资源，相当于借贷，考虑对方还得起才借钱,提前考虑好以后,就可以避免死锁。
- 死锁检测:允许死锁产生，但系统定时运行一个检测死锁的程序，若检测到系统中发生死锁，则设法加以解除。
- 死锁解除:即死锁发生后的解除方法，如强制剥夺资源，撤销进程等。
- 死锁计算问题:系统内有n个进程，每个进程都需要R个资源，那么其发生死锁的最大资源数为n*(R-1)。其不发生死锁的最小资源数为n*(R-1)+1。
线程
- 传统的进程有两个属性:可拥有资源的独立单位;可独立调度和分配的基本单位。
- 引入线程后，线程是独立调度的最小单位，进程是拥有资源的最小单位，线程可以共享进程的公共数据、全局变量、代码、文件等资源，但不能共享线程独有的资源，如线程的栈指针等标识数据。
存储管理
分区存储
页式存储
将进程空间分为一个个页，假设每个页大小为4K，同样的将系统的物理空间也分为一个个4K大小的物理块(页帧号)，这样，每次将需要运行的逻辑页装入物理块中，运行完再装入其他需要运行的页，就可以分批次运行完进程，而无需将整块逻辑空间全部装入物理内存中。
- 优点:利用率高、碎片小（只在最后一个页中有)、分配及管理简单。
- 缺点:增加了系统开销,可能产生抖动现象。
页面置换算法
- 有时候，进程空间分为100个页面，而系统内存只有10个物理块。无法全部满足分配，就需要将马上要执行的页面先分配进去，而后根据算法进行淘汰，使100个页面能够按执行顺序调入物理块中执行完。
- 缺页表示需要执行的页不在内存物理块中，需要从外部调入内存，会增加执行时间，因此，缺页数越多,系统效率越低。
- 最优算法:OPT，理论上的算法，无法实现，是在进程执行完后进行的最佳效率计算，用来让其他算法比较差距。原理是选择未来最长时间内不被访问的页面置换，这样可以保证未来执行的都是马上要访问的。
- 先进先出算法:FIFO，先调入内存的页先被置换淘汰，会产生抖动现象，即分配的页数越多，缺页率可能越多（即效率越低），缺页计算如下:
- 最近最少使用: LRU，在最近的过去，进程执行过程中，过去最少使用的页面被置换淘汰，根据局部性原理,这种方式效率高,且不会产生抖动现象。
快 表
- 是一块小容量的相联存储器，由快速存储器组成，按内容访问，速度快，并且可以从硬件上保证按内容并行查找，一般用来存放当前访问最频繁的少数活动页面的页号。
- 快表是将页表存于cache中;慢表示将页表存于内存上。
- 因此慢表需要访问两次内存才能取出页，而快表是访问一次Cache和一次内存，因此更快。
段式存储
- 将进程空间分为一个个段，每段也有段号和段内地址，与页式存储不同的是，每段物理大小不同，分段是根据逻辑整体分段的.
- 地址表示:(段号，段内偏移):其中段内偏移不能超过该段号对应的段长，否则越界错误，而此地址对应的真正内存地址应该是:段号对应的基地址+段内偏移
段页式存储
- 对进程空间先分段,后分页,具体原理图和优缺点如下:
- 优点:空间浪费小、存储共享容易、能动态连接。
- 缺点:由于管理软件的增加，复杂性和开销也增加,执行速度下降
文件管理
索引文件
- 计算机系统中采用的索引文件结构如下图所示:
- 系统中有13个索引节点，0-9为直接索引，即每个索引节点存放的是内容，假设每个物理盘大小为4KB，共可存4KB*10=4 0KB数据;
- 10号索引节点为一级间接索引节点，大小为4KB，存放的并非直接数据，而是链接到直接物理盘块的地址，假设每个地址占4B，则共有1024个地址，对应1024个物理盘，可存1024*4KB=4098KB数据。
- 二级索引节点类似,直接盘存放一级地址,一级地址再存放物理盘快地址,而后链接到存放数据的物理盘块,容量又扩大了一个数量级,
为102410244KB数据。
树形目录
空闲存储管理
- 空闲区表法:将所有空闲空间整合成一张表，即空闲文件目录。
- 空闲链表法:将所有空闲空间链接成一个链表，根据需要分配。
- 成组链接法:既分组，每组内又链接成链表，是上述两种方法的综合。
- 位示图法:对每个物理空间用一位标识，为1则使用，为0则空闲,形成一张位示图。
