操作系统基本概念
1、操作系统的概念、功能和目标
（1）计算机系统的层次结构：
（2）操作系统的定义
- 操作系统是指控制和管理整个计算机系统的硬件和软件资源，并合理的组织调度计算机的工作和资源的分配，以提供用户和其他软件方便的接口和环境，它是计算机系统中最基本的软件。操作系统是管理硬件和软件的一种应用程序。
（3）操作系统的功能和目标
- ①作为系统资源的管理者：
提供的功能： 文件管理、存储器管理、处理机管理、设备管理
目标： 安全、高效 - ②作为用户和计算机硬件之间的接口：
命令接口： 联机命令接口、脱机命令接口
程序接口： 系统调用
图形用户界面： GUI - ③作为最接近硬件的层次
功能和目标： 实现对硬件机器的拓展
2、操作系统的特征
（1）并发：指两个或多个事件在同一时间间隔内发生。这些事件宏观上同时发生，但微观上交替发生的。
（2）共享：是指系统中的资源可供内存中多个并发执行的进程共同使用。
互斥共享方式： QQ和微信的摄像头资源
同时共享方式： QQ和微信同时发送文件
并发和共享的关系：
（3）虚拟：是指把一个物理上的实体变为若干个逻辑上的对应物。物理实体是实际存在，而逻辑上的对应物是用户感受到的。
空分复用技术：
时分复用技术：
（4）异步性：异步是指，在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进。
3、操作系统的发展和分类
（1）手工操作阶段：
缺点：用户独占全机，人机速度慢。
（2）批处理阶段： 引入脱机输入/输出技术（用磁带完成），并监督程序负责控制作业的输入和输出。
多道批处理系统：
- 优点：多道程序并发的执行，共享计算机的资源，资源利用率大幅度提升。
- 缺点：没有人机交互能力，用户响应时间长。
（3）分时操作系统： 计算机以时间片为单位轮流为各个用户/作业服务，各个用户可通过终端与计算机进行交互。
（4）实时操作系统： 在严格的时间内处理和完成事件。
- 特点：及时性和可靠性
硬实时操作系统和软实时操作系统
4、操作系统的运行机制和体系结构
（1）两种指令
指令：就是处理器能够识别的
特权指令：不允许普通的用户来使用的。如内存清零指令
非特权指令：
两种处理器状态：用户态（目态）、核心态（管理态）
两种程序：内核程序、应用程序
（2）操作系统的内核
内核、非内核功能
内核：是计算机配置的底层软件，是操作系统最基本、最核心的部分
（3）操作系统的体系结构
大内核：
微内核：
5、中断和异常
（1）中断机制的诞生
本质：只要发生了中断，就需要操作系统介入，开展管理工作
（2）中断的概念和作用
定义：中断是指CPU对系统发生的某个事件做出的一种反应，CPU暂停正在执行的程序，保存现场后自动去执行相应的处理程序，处理完该事件后再返回中断处继续执行原来的程序。
（3）中断的分类
①内中断：异常、例外、陷入。
自愿中断：指令中断
强迫中断：硬件故障、软件中断
②外中断 ：外设请求、人工干预
（4）外中断的处理过程
6、系统调用
（1）什么是系统调用，有何作用
例子：两位同学同时去打印店打印
作用：可以保证系统的稳定性和安全性
（2）系统调用和库函数的区别
7、进程的定义、组成、组织方式、特征
（1）进程的定义
单道程序：
多道程序：
PCB、程序段、数据段构成了进程实体（进程映像）。
PCB是进程存在的唯一标志！
定义：进程是程序的一次执行过程；是系统进行资源分配和调度的一个独立单位。
（2）进程的组成
程序段、数据段、PCB三部分组成
PCB：进程描述信息（进程标识符PID、用户标识符UID）、进程控制和管理信息、资源分配清单、处理机相关信息 [只要是和进程管理相关的信息都在PCB中]
（3）进程的组织
链接方式：执行指针、就绪队列指针、阻塞队列指针
索引方式：执行指针、就绪表指针、阻塞表指针
（4）进程的特征
①动态性：
②并发性：内存中由多个实体，各进程可并发执行
③独立性：
④异步性：
⑤结构性：
8、进程的状态和转换
（1）三种基本状态
运行态：占有CPU，并在CPU上运行
就绪态：已经具备运行条件，但没有CPU，而暂时不能运行
阻塞态：因等待某一事件而暂时不能运行
（2）另外两种状态
创建态：
终止态：
（3）进程状态的转换
创建态-----就绪态<----->运行态-----阻塞态
9、进程控制
（1）什么是进程控制？
用原语实现进程控制。原语的特点是执行期间不允许中断，只能一气呵成
（2）进程控制相关的原语
①更新PCB中的信息
②将PCB插入合适的队列
③分配/回收资源
创建原语：申请空白PCB、为新进程分配所需资源、初始化PCB、将PCB插入进程队列中
撤销原语：从PCB集合找到终止进程的PCB、
进程的阻塞：
进程的唤醒：
切换原语：
引起进程切换的事件：
10、进程通信
（1）什么是进程通信？
各个进程拥有的内存地址空间相互独立
（2）共享存储
对共享空间的访问是互斥的（P、V操作）
共享存储：基于数据结构的共享（低级的）、基于存储区的共享（高级的）
（3）管道通信
①管道只能采用半双工通信。如果要实现双向同时通信，则需要设置两个管道。
②各个进程要互斥的访问管道；
③当管道写满时，写进程的系统调用将被阻塞，等待读进程取走；
（4）消息传递
进程间的数据交换以格式化的消息为单位
消息传递：直接通信方式、间接通信方式
11、线程概念和多线程模型
（1）什么是线程，为什么要引入线程？
增加并发度。（QQ可以聊天、传文件）
同一个进程中分为多个线程
线程成为程序执行流的最小单位
（2）引入线程后，有什么变化？
资源分配、调度：进程是资源分配的基本单位，线程是调度的基本单位
并发性：
系统开销：
（3）线程的属性
①线程是处理机调度的单位；
②多CPU计算机中，各个线程可占用不同的CPU；
③每个线程都有一个线程ID、线程控制块TCB；
④线程也有就绪、阻塞、运行三种状态；
（4）线程的实现方式
用户级线程（ULT）：线程切换可以在用户态下完成
内核级线程（KLT）：内核级线程的切换必须在核心态下完成
重点：只有内核级线程才是处理机分配的单位
（5）多线程模型
多对一模型：多个用户级线程映射到一个内核级线程
一对一模型：一个用户级线程映射到一个内核级线程
优点：并发能力强
缺点：成本高、开销大
多对多模型：n用户级线程映射到m个内核级线程
12、处理机调度的概念和层次
（1）调度的基本概念
就是从调度序列中选择一个算法来执行
（2）调度的三个层次–高级调度
高级调度（作业调度）：外存与内存
（3）中级调度
提高内存利用率和系统通吐量
暂时调到外存等待的进程状态为挂起状态
中级调度（内存调度）：
（4）进程的挂起态与七状态模型
就绪挂起：
阻塞挂起：
（5）低级调度
低级调度（进程调度）：
（6）三种调度的联系、对比
高级调度：外存-----内存
中级调度：外存-----内存
低级调度：内存-----CPU
13、进程调度的时机、切换与过程、方式
（1）进程调度的时机
进程调度：低级调度，就是按某种算法从就绪队列中选择一个进程为其分配处理机
不能进行进程调度的情况：中断、原子操作过程中，操作系统内核程序临界中
（2）进程调度的方式
非剥夺方式：，非抢占方式
剥夺方式：抢占方式，适合分时操作系统、实时操作系统
（3）进程的切换与过程
进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程
14、调度算法的评价标准
（1）CPU利用率
利用率=忙碌的时间/总时间
（2）系统通吐量
系统通吐量=总共完成的作业/总共花了的时间
（3）周转时间
周转时间=作业完成时间-作业提交时间
平均周转时间=各作业周转时间和/作业数
带权周转时间=作业周转时间/作业实际运行的时间
平均带权周转时间
（4）等待时间
指进程/作业处于等待处理机状态的时间之和
平均等待时间
（5）响应时间
15、FCFS、SJF、HRRN调度算法
（1）先来先服务
算法规则：按照作业/进程到达的先后顺序进行服务
非抢占式算法
优点：公平、算法实现简单
缺点：对长作业有利，对短作业不利
不会导致饥饿
（2）短作业优先
作业：SJF
进程：SPF
非抢占式、抢占式（最短剩余时间优先算法[SRTN]）
缺点：不公平，对短作业有利，对长作业不利，会产生饥饿
（3）高响应比优先算法
在每次调度时，计算各个进程/作业的响应比，选择响应比高的作业/进程优先
响应比=（等待时间+要求服务时间）/要求服务时间
不会导致饥饿
16、调度算法：时间片轮转、优先级、多级反馈队列
（1）时间片轮转调度萨法（RR）
规则：按照各进程到达就绪队列的顺序，轮流的让各个进程执行一个时间片
抢占式的算法
时钟中断
优点：公平、响应快
不会导致饥饿
（2）优先级调度算法
调度时选择优先级高的罪业/进程
抢占式、非抢占式
（3）多级反馈队列调度算法
抢占式算法
用于进程调度
会导致饥饿
17、进程同步、进程互斥
（1）什么是进程同步？
同步亦称直接制约关系。
（2）什么是进程互斥？
一个时间段内只允许一个进程使用的资源称为临界资源
enrty section进入区
critical section临界区/临界段
exit section退出区
remainder section剩余区
遵循以下原则：空闲让进、忙则等待、有限等待、让权等待
18、进程互斥的软件实现方法
（1）单标志法
算法思想：两个进程在访问完临界区后会把使用的临界区的权限转交给另一个进程
int turn =0
该算法可以实现同一时间内有一个进程访问临界区
主要问题：违背空闲让进原则
（2）双标志先检查法
数组中的各个元素用来标志各进程想进入临界区的意愿
bool flag[2];
flag[0] = false;
flag[1] = false;
主要问题：违背了忙则等待的原则
（3）双标志后检查法
先上锁----后检查
主要问题：违背了空闲让进和有限等待的原则
（4）Peterson算法
bool flag[2];
int turn = 0;
主要问题：违背了让权等待的原则
19、进程互斥的硬件实现方法
（1）中断屏蔽方法
优点：简单、高效
缺点：不适合多处理机
20、信号量机制
整形信号量、记录型信号量
（1）信号量机制
可以通过操作系统提供的一对原语来对信号量进行操作，从而方便的解决了进程同步、互斥问题。
wait、signal简称为P、V操作
（2）整型信号量
用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。
（3）记录型信号量
typedef struct {
int value;
struct process *L;
}semaphore;
21、信号量机制实现进程互斥、同步、前驱关系
（1）信号量机制实现进程互斥
互斥信号量mutex，初值为1
注意：对不同的临界资源设置不同的互斥信号量
（2）信号量机制实现进程同步
semaphore S=0；
22、生产者、消费者问题
（1）问题描述
实现互斥的P操作一定要在实现同步的P操作之后
23、多生产者、多消费者问题
（1）问题描述
24、读者-写者问题
25、哲学家进餐问题
26、管程
（1）为什么引入管程？
管程—一种高级的
（2）管程的定义和特征
组成：
①局部于管程的共享数据结构的说明；
②对该数据结构进行操作的一组过程；
③对局部于管程的共享数据设置初始值的语句；
④管程有一个名字；
基本特征：
每次仅允许一个进程在管程内执行某个内部过程。
（3）用管程解决生产者和消费者问题
27、死锁的概念
（1）什么是死锁？
（2）死锁、饥饿、死循环的区别
至少有两个或者两个以上的进程同时发生死锁；
而发生饥饿可能只有一个进程发生。（短进程优先SPF）
（3）死锁产生的必要条件
互斥条件、不可剥夺条件、请求和保持条件、循环等待条件
注意：循环等待未必死锁、死锁一定有循环等待
（4）什么时候会发生死锁
对系统资源的竞争；进程推进顺序非法；信号量的使用不当也会造成死锁；
（5）死锁的处理策略
预防死锁；
避免死锁；
死锁的检测和解除；
28、预防死锁
互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁；
不剥夺条件：
29、避免死锁
（1）什么是安全序列？
（2）安全序列
（3）银行家算法
30、死锁的检测与解除
（1）死锁的检测
用某种数据结构和一种算法
（2）死锁的解除
资源剥夺法：
撤销进程法
进程回退法
如何决定对谁下手：
进程优先级、已执行多长时间、还要多久能完成、进程已经使用了多少资源、进程是交互式还是批处理是的
31、内存的基础知识
（1）装入模块装入内存
（2）绝对装入
32、内存管理的概念
（1）内存空间的分配和回收
操作系统负责内存空间的分配和回收
操作系统需要提供某种逻辑上对内存空间进行扩充
绝对装入、可重定位装入、动态运行时装入
（2）内存保护
33、覆盖和交换
（1）覆盖技术
（2）交换技术
34、连续分配管理方式
（1）单一连续分配
优点：实现简单、没有外部碎片
缺点：有内部碎片
（2）固定分区分配
固定分区分配：分区大小相等、分区大小不等
操作系统建立一个数据结构：分区说明表
优点：实现简单、没有外部碎片
缺点：会产生内部碎片
（3）动态分区分配
两种常用的数据结构：空闲分区表、空闲分区链
没有内部碎片、但是有外部碎片
35、动态分区分配算法
（1）首次适应算法：从头到尾找合适的分区
空闲分区链、空闲分区表
缺点：
（2）最佳适应算法：优先使用更小的分区，以保留更多大分区
缺点：会产生很多的碎片
（3）最坏适应算法：优先使用更大的分区，以防止产生太小的不可用的碎片
缺点：如果有大进程到达、没办法分配
（4）邻近适应算法：每次从上次查找结束位置开始查找
缺点：会使高地址的大分区也被用完
36、基本分页存储管理的基本概念
（1）连续分配方式的特点
（2）非连续分配的版本
（3）分页存储管理的基本概念
（4）如何实现地址的转换
37、基本地址变换机构
（1）基本地址变换机构
（2）对页表项大小的进一步探讨
38、基本分段存储管理方式
（1）段表
段号、段长、基址
39、虚拟内存的基本概念
（1）传统存储管理的方式的特征、缺点
传统存储管理：连续分配和非连续分配
一次性：作业必须一次性装入内存后才能开始运行
驻留性：
（2）局部性原理
时间局部性：
空间局部性：
|