961操作系统知识总结

部分图片可能无法显示，参考这里：https://zhuanlan.zhihu.com/p/701247894

961操作系统知识总结

一 操作系统概述

1. 操作系统的基本概念

重要操作系统类型：批处理操作系统(批量处理作业，单道批处理/多道批处理系统，用户不能与之交互)，分时操作系统(时间片轮转，可以进行用户交互)，实时操作系统(相对分时操作系统，紧急任务无需排队等待)

并发与并行：并发性，又称共行性，是指能处理多个活动的能力。并行与并发是不同的，并行是指进程在CPU上同时执行，而并发只要求一段时间内进程同时能够运行，有可能是在这段时间内两者是串行执行的。
程序：放在外存中的程序代码
作业：正准备从外存调入内存的程序
进程：正在从内存中运行的程序

2. 操作系统的重要概念

用户态+核心态/管态
操作系统内核相关内容：时钟管理，中断机制，原语，系统控制的数据结构及处理
原语：处于计算机最底层，用来实现一些规定操作的指令，且不能被中断，需一次性执行完(一般执行时间也很短)。
系统控制的数据结构及处理：如进程控制块，设备控制块等。

二 进程管理

1. 进程、线程的基本概念以及两者的区别

在操作系统中引入进程的目的，是为了使多个程序并发执行，以改善资源利用率及提高系统的吞吐量;那么，在操作系统中再引入线程则是为了减少程序并发执行时所付出的时空开销，使操作系统具有更好的并发性。

支持线程的操作系统中，进程是资源分配的基本单位，线程是处理器调度的基本单位。

2. 进程控制块、进程的状态与转换

当遇到特殊情况，需要暂停进程，然后将进程会从内存调到外存，该过程就称为进程的挂起。被挂起的程序在解决了特定问题之后，可以恢复到内存继续运行。
注意，进程的挂起不是进程的阻塞，处于阻塞状态的进程依然在内存中，但处于挂起状态的进程已经不在内存了。
进程 = 程序 + 数据 + 进程控制块PCB

3. 进程调度算法

优先级算法
时间片轮转算法
短作业优先算法
先来先服务算法
最重要评估原则：周转时间，平均周转时间
其他比较次要的原则：

调度的层次：低级调度(作业调度，程序)，中级调度(内存调度，挂起)，高级调度(进程调度，进程)

4. 死锁的探讨与处理

死锁的预防

死锁发生的四个必要条件：循环等待条件，不可剥夺条件，请求保持条件，互斥使用条件

死锁的避免

银行家算法，安全性算法，资源分配矩阵，安全序列

死锁的检测

资源分配图的化简

死锁的解除

资源剥夺法，撤销进程法

死锁处理总览

从预防，避免，检测，解除四个角度出发，大题可能出银行家算法，安全性算法，资源分配图，其实本质都一样，思想都是试探性分配

5. 进程间通信

低级通信：交换少量信息，PV操作是低级通信方式，实现对临界资源的同步和互斥。
高级通信：以较高的效率交换大量数据的通信方式
高级通信方式：共享存储，消息传递系统，管道通信

6. 进程同步互斥的基本概念

临界资源：系统中一次只允许一个进程使用的资源
临界区：各个进程中对某个临界资源实施操作的程序片段
同步：一个进程执行到某一步时，必须等待另一个进程发来信息才能继续运行下去，这种关系叫同步。
互斥：由于各个进程需要使用共享资源，而这些资源需要排它性使用，各个进程之间竞争使用这些资源，这种关系叫互斥。
临界资源的访问代码分区：进入区，临界区，退出区，剩余区

7. 实现临界区互斥的基本方法

软件实现法
在进入区设置和检查一些标志来表明是否有进程进入临界区。若有，则循环检查一直等待，直到进入临界区。离开临界区后，在退出区修改标志。这种不断循环检查标志的值实质上，浪费了处理机资源。
硬件实现法
硬件实现主要两种方法：中断屏蔽法和硬件指令法
中断屏蔽法：一个进程进入临界区后，关中断。可以防止其他进程进入临界区。此方法限制了CPU交替执行程序的能力，有可能会使系统崩溃(如异常得不到中断处理)
硬件指令法：每条硬件指令都是原子操作，因为它们是硬件直接实现，因此执行硬件指令时不会被中断
信号量机制
一种十分有效，重要的同步方法，可以同时实现同步和互斥关系，实现灵活方便快捷

8. 信号量机制及P、V操作

信号量机制可用来解决同步和互斥问题，信号量semaphore只能被两个操作(P操作和V操作)来访问。
信号量的数据结构描述如下：

typedef struct {int value;struct process *L;
} semaphore;

说明：该数据结构由两个变量组成，value是当前状态可用资源的数量，L是存放因资源限制被阻塞的进程队列指针。
P操作：请求访问临界资源
V操作：请求释放临界资源

信号量机制原理简述

当一个进程需要临界资源时：

1. 进行P操作，value的值减1
2. 若value>=0，说明存在可用临界资源，进程继续执行，否则转3
3. 若value<0，说明不存在可用临界资源，将当前进程加入阻塞队列L
4. 阻塞进程，等待适当时机被唤醒

当一个进程释放临界资源时：

1. 进行V操作，value的值加1
2. 若value>0，说明不存在阻塞的进程，否则转3
3. 若value<=0，说明存在阻塞的进程等待临界资源，唤醒一个阻塞进程

只需要将临界区代码置于P，V操作之间，即可实现同步与互斥
分析：此时，P操作相当于进入区，临界区依然是临界区，V操作相当于退出区，剩余区依然不变；P,V操作为原语，执行过程中不能被中断。

9. 经典同步问题

主要三个问题：生产者消费者问题，读者写者问题，哲学家进餐问题，前两个问题相对更重要，是实际做题的思路来源
生产者消费者问题



读者写者问题



哲学家进餐问题

三 内存管理

1. 程序从外存调入内存细节

程序从外存到内存，实现了外存中作业到内存中进程的转变，大体经过编译，链接，装入三大过程。
编译
编译过程主要有编译和汇编两个阶段。编译阶段主要将高级语言转换为汇编语言，汇编阶段主要将汇编语言翻译成机器语言。
链接
由链接程序将编译后形成的目标模块以及所需要的库函数链接在一起，形成一个完整的装入模块。链接主要在编译时，加载时，运行时进行。链接若发生在编译时，就是静态编译，程序运行前完全确定链接；而运行时链接，表示程序运行到需要的函数库才链接对应对象，为动态编译。
装入
由装入程序将装入模块装入内存运行，此时会创建对应进程。装入分为静态重定位和动态重定位。涉及的主要问题是程序中的逻辑地址与实际内存的物理地址之间如何映射。静态重定位在装入时一次性完成逻辑地址与物理地址的映射关系，而动态重定位需要运行时动态确定逻辑地址与物理地址的映射关系。

2. 内存保护的基本方法

内存保护的关键在于检查进程是否有内存地址越界行为。
上下限寄存器
在CPU中设置上下限寄存器，用于分别存放作业在主存中的上限和下限地址，当CPU要访问地址时，与这两个寄存器的值进行比较即可判断是否越界，适合逻辑地址即对应相应物理地址的情形(如物理地址与逻辑地址事先就确定只差一个固定的偏移量)
界地址寄存器
界地址寄存器存有进程的最大逻辑地址(通过分配内存后由起始物理地址与分配空间大小计算得出)，可通过逻辑地址是否大于该界地址寄存器的值比较是否发生越界，若不越界，加上重定位寄存器(存有进程的起始物理地址)的值即为物理地址。

3. 分区管理存储

可细分两种：固定式分区存储管理和动态式分区存储管理

固定式分区分配方法：单一队列分配方式，多队列分配方式
可变式分区分配方法：首次适应算法，下次适应算法，最佳适应算法，最坏适应算法
碎片方面：固定式分区产生内碎片，可变式分区产生外碎片

4. 交换覆盖技术

覆盖技术

交换技术

5. 分页存储管理(重点内容，展开比较详细)

作业在请求内存空间的分配时，一般按照页为单位来分配，每个进程记住自己分得哪些页(一般记录页号)形成页表，页表数据存储在进程控制块PCB中。






地址变换过程


多级页表

6. 分段存储管理

7. 段页存储管理

8. 虚拟存储管理

虚拟存储技术的实现依赖于局部性原理，即进程往往会不均匀地高度局部性地访问内存。局部性原理表现在时间局部性和空间局部性。

9. 页面置换算法

如果进程在运行中发生缺页现象，需要进入缺页中断机构进行处理，请求操作系统将所缺页面调入内存。此时进程被阻塞，等待调页完成时的唤醒。

重要算法

OPT
LRU
FIFO
CLOCK

四 设备管理

1. 设备管理基本概念

设备按传输分类：块设备(数据块为单位)，字符设备(字符为单位)
设备按用途分类：存储设备，传输设备，人机交互设备
设备按共享分类：共享设备，独占设备(临界资源)，虚设备(虚拟技术上的逻辑设备)

设备控制方式：程序控制，中断驱动，DMA方式，通道方式

2. 直接控制方式

3. 中断驱动方式

4. DMA方式

5. 通道方式

6. 缓冲技术

当缓冲区的数据非空时，不能往缓冲区注入数据；当缓冲区数据为空时，才能注入数据。
当缓冲区的数据不满时，不能获取缓冲区数据；当缓冲区数据为满时，才能获取数据。
主要缓冲技术有：单缓冲技术，双缓冲技术，循环缓冲技术，缓冲池技术

7. 假脱机技术

五 文件管理

1. 文件系统概念

文件由文件体和文件控制块FCB构成

文件分两种：普通文件(正常意义下的文件)，特殊文件(目录，本质上为文件)，磁盘里面存储的都是文件，以文件为逻辑单位进行组织

对文件的不同组织方式，就构成了不同的文件系统，常见的文件系统有：FAT，NTFS

2. 普通文件基础

文件结构分为逻辑结构和物理结构
逻辑结构：文件在操作系统角度的组织方式，主要为用户所看到
物理结构：文件在物理磁盘角度的组织方式，主要为系统所看到

3. 目录文件基础

4. 文件系统实现

5. 磁盘调度算法

6. 冗余磁盘阵列

RAID0：条带化存储
RAID1：镜像存储
RAID2：汉明码存储

RAID3:校验码-字节存储
RAID4：校验码-数据块存储
RAID5：校验码-交叉存储