跟学视频：学以致知Learning - 软件设计师 基础阶段|考点理论精讲
Chapter 4 - 操作系统基本原理
1 - 操作系统简介
概念（定义）
操作系统（Operating System，OS）是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配，以提供给用户和其他软件方便的接口和环境，它是计算机系统中最基本的系统软件
操作系统的功能和目标
- 作为系统资源的管理者
- 向上层提供方便易用的服务
- 作为最接近硬件的层次
操作系统的特征
- 并发
- 共享
- 虚拟
- 异步
操作系统的发展与分类
- 手工操作阶段
- 批处理阶段（单道批处理系统、多道批处理系统）
- 分时操作系统
- 实时操作系统
- 网络操作系统
- 分布式操作系统
- 个人计算机操作系统
2 - 进程管理
1、进程正在被创建时，它的状态是“创建态”，在这个阶段操作系统会为进程分配资源、初始化PCB
2、当进程创建完成后，便进入“就绪态”，处于就绪态的进程已经具备运行条件，但由于没有空闲CPU，就暂时不能运行
3、如果一个进程此时在CPU上运行，那么这个进程处于“运行态”，CPU会执行该进程对应的程序（执行指令序列）
4、在进程运行的过程中，可能会请求等待某个事件的发生（如等待某种系统资源的分配，或者等待其他进程的响应）。在这个事件发生之前，进程无法继续往下执行，此时操作系统会让这个进程下CPU，并让它进入“阻塞态”，当CPU空闲时，又会选择另一个“就绪态”进程上CPU运行
5、一个进程可以执行exit系统调用，请求操作系统终止该进程。此时该进程会进入“终止态”，操作系统会让该进程下CPU，并回收内存空间等资源，最后还要回收该进程的PCB。当终止进程的工作完成后，这个进程就彻底消失了
状态转换图
进程同步机制
进程具有异步性的特征，异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进
看一个例子：进程通信——管道通信
读进程和写进程并发地运行，由于并发必然导致异步性，因此“写数据”和“读数据”两个操作执行的先后顺序是不确定的。而实际应用中，又必须按照“写数据->读数据”的顺序来执行，如何解决这种异步问题，就是“进程同步机制”所讨论的内容
同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作
进程互斥机制
进程的“并发”需要“共享”的支持。各个并发执行的进程不可避免的需要共享一些系统资源（比如内存、打印机、摄像头等）
我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备（比如摄像头、打印机）都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源
对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源
对临界资源的互斥访问可以在逻辑上分为如下四个部分：
临界区是进程中访问临界资源的代码段
进入区和退出区是负责实现互斥的代码段
临界区也可称为“临界段”
为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则：
- 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
- 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待
- 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）
- 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待
信号量机制
用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步、进程的前驱关系
信号量其实就是一个变量（可以是一个整数，也可以是更复杂的记录型变量），可以用一个信号量来表示系统中某种资源的数量，比如系统中只有一台打印机，就可以设置一个初值为1的信号量
原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”，就能避免问题
一对原语：wait(S)原语和signal(S)原语，可以把原语理解为我们自己写的函数，函数名分别为wait和signal，括号里的信号量S其实就是函数调用时传入的一个参数
wait、signal原语常简称为P、V操作（来自于荷兰语proberen和verhogen），因此做题时常把wait(S)、signal(S)两个操作分别写为P(S)、V(S)
一个信号量对应一种资源信号量的值 = 这种资源的剩余数量（信号量的值如果小于0，说明此时有进程在等待这种资源）
- P(S)—申请一个资源S，如果资源不够就阻塞等待，即S-1
- V(S)—释放一个资源S，如果有进程在等待该资源，则唤醒一个进程，即S+1
PV操作
这保证了代码4一定是在代码2之后执行
PV操作实现前驱操作
进程P1中有句代码S1，P2中有句代码S2，P3中有句代码S3…P6中有句代码S6。这些代码要求按如下前驱图所示的顺序来执行：
其实每一对前驱关系都是一个进程同步问题（需要保证一前一后的操作），因此：
- 要为每一对前驱关系各设置一个同步信号量
- 在”前操作“之后对相应的同步信号量执行V操作（V操作释放资源）
- 在”后操作“之前对相应的同步信号量执行P操作（P操作锁定资源）
死锁产生的必要条件
产生死锁必须同时满足以下四个条件，只要其中任一条件不成立，死锁就不会发生：
- 互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁（如哲学家的筷子、打印机设备）。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的（因为进程不用阻塞等待这种资源）
- 不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放
- 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放
- 循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求
死锁的处理策略
1、预防死锁：破坏死锁产生的四个必要条件中的一个或几个
2、避免死锁：用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法）
3、死锁的检测和解除：允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁
银行家算法
安全序列：就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。安全序列可能有多个
如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去
如果系统处于安全状态，就一定不会发生死锁。不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态
因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。这也是“银行家算法”的核心思想
3 - 存储管理
操作系统负责内存空间的分配与回收，用虚拟技术从逻辑上对内存空间进行扩充
内存空间的分配与回收
动态分区分配 首次适应算法
算法思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区
如何实现：空闲分区以地址递增的次序排列，每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区
动态分区匹配 最佳适应算法
算法思想：由于动态分区分配是一种连续分配方式，为各进程分配的空间必须时连续的一整片区域，因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即优先使用更小的空闲区
如何实现：空闲分区按容量递增次序链接，每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区
动态分区匹配 最差适应算法
算法思想：为了解决最佳适应算法的问题，即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用
如何实现：空闲分区按容量递减次序链接，每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区
动态分区匹配 邻近适应算法
算法思想：首次适应算法每次都从链头开始查找，这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题
如何实现：空闲分区以地址递增的顺序排列（可排成一个循环链表），每次分配内存时从上次查找结束的位置开始查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区
分页存储管理
页表的作用是实现从页号到物理块号的地址映射
分段存储管理
段页式存储管理
优点：空间浪费小、存储共享容易、存储保护容易、能动态连接
缺点：由于管理软件的增加，复杂性和开销也随之增加，需要的硬件以及占用的内容也有所增加，使得执行速度大大下降
页面置换算法
不管使用哪种存储管理，最后内存都会被基本装满，而在后续程序执行过程中，当所需要的数据信息又不在内存时，应该怎么办呢？
由操作系统负责将内存中暂时用不到的信息换出到外存，而用页面置换算法来决定应该将哪个页面换出内存
页面置换算法 最佳置换算法OPT
最佳置换算法（OPT，Optimal）：每次选择淘汰的是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率
按最佳置换的规则，往后寻找，最后一个出现的页号就是要淘汰的页面
页面置换算法 先进先出置换算法FIFO
先进先出置换算法FIFO：每次选择淘汰的页面是最早进入内存的页面
页面置换算法 最近最久未使用置换算法LRU
最近最久未使用置换算法LRU：每次淘汰的页面是最近最久未使用的页面
可以往前找在内存中的几个页面号，最后一个出现的页号就是要淘汰的页面
4 - 文件管理
文件管理初识
文件目录
文件控制块：文件控制块（FCB）是系统为管理文件而设置的一个数据结构。FCB是文件存在的标志，它记录了系统管理文件所需要的全部信息
目录结构：一级目录结构、二级目录结构、多级目录（树形目录结构）（绝对路径、相对路径）
绝对路径：是从盘符开始的路径
相对路径：是从当前路径开始的路径
文件结构
索引分配
空闲存储空间的管理
- 空闲区表
将外存空间上的一个连续未分配区域称为空闲区，操作系统为外存上所有空闲区建立一张空闲表来管理空闲存储空间
- 位示图
这种方法是在外存上建立一张位示图，记录文件存储器的使用情况。每一位对应文件存储器上的一个物理块，取值0和1分别表示空闲和占用
- 空闲块链
每个空闲物理块中都有指向下一个空闲物理块的指针，所有空闲物理块构成一个链表，链表的头指针放在文件存储器的特定位置（如管理块中）
- 成组链接法
在UNIX系统中，将空闲块分成若干组，每100个空闲块为一组，每组的第一个空闲块登记下一组空闲块的物理盘块号和空闲块总数，假如一个组的第一个空闲块号等于0，就意味着该组是最后一组，无下一组空闲块
5 - 设备管理
I/O设备基本概念
I/O控制方式
6 - 微内核操作系统
