操作系统
关于操作系统
概念与目标
概念：配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充。
目标：方便性、有效性、可扩充性、开放性
作用：用户与计算机硬件系统之间的接口；计算机系统资源的管理者；实现了对计算机资源的抽象。
计算机资源的抽象
所谓资源抽象，是指通过创建软件来屏蔽硬件资源物理特性和接口细节，简化对硬件资源的操作、控制和使用的一类技术。
因此，OS是铺设在硬件上的多层软件集合，隐藏了对硬件操作的细节，实现了对硬件操作的多个层次的抽象模型。
发展
人工操作–脱机输入/输出–单道批处理–多道批处理
基本特征
并发：一段时间内，宏观上有多个程序在同时运行，微观上程序分时运行。
共享：系统中的资源可供内存中多个并发执行的进程同时使用
- 互斥共享
- 同时访问
虚拟：通过某种技术将一个物理实体变为若干逻辑上的对应物
- 时分复用
- 空分复用
异步：进程的运行“停停走走”
主要功能
处理机管理：进程控制、进程同步、进程通信、调度
存储器管理：内存分配、内存保护、地址映射、内存扩充
设备管理：缓冲管理、设备分配、设备处理
文件管理：文件存储空间管理、目录管理、文件的读写管理和保护
OS与用户的接口
操作系统与用户的接口
用户接口：联机用户接口、脱机用户接口、图形用户接口
程序接口：由一系列系统调用组成
进程与线程
并发执行的特征
间断性：进程间相互制约
失去封闭性：资源共享，运行的环境受其他程序影响
不可在现性：程序多次执行，得到的结果不再相同
进程定义、PCB定义
进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
PCB–进程控制块，为使每个参与并发执行的程序能独立运行，OS为之配置的数据结构
进程特征
动态性：由创建产生，由调度执行，由撤销消亡
并发性：多个进程同时存在于内存中，能在一段时间内同时运行
独立性：能独立运行、独立获得资源、独立接受调度的基本单位
异步性：每个进程按照各自独立的不可预知的速度前进
进程的三种状态以及三种状态的转换
系统内核，系统态，用户态
系统内核：与硬件紧密相关的模块、各种常用设备的驱动程序、运行频率较高的模块，都安排在紧靠硬件的软件层中常驻内存。
系统态/管态：具有较高特权，能执行一切指令，访问所有寄存器和存储区–OS在系统态运行
用户态/目态：具有较低特权的执行状态，只能执行规定的指令，访问指定的寄存器和存储区
进程同步
对执行次序进行调节，使并发的进程按一定时序关系共享资源，使程序的执行具有可再现性
间接相互制约关系：互斥共享
直接相互制约关系：为了完成同一个任务
临界资源
临界区：在每个进程中访问临界资源的代码片段
经典问题：生产者-消费者问题
线程的定义、要引入线程原因
线程：调度和分派的基本单位
为了减少程序在并发执行时所付出的时空开销，使OS具有更好的并发性
线程与进程的比较
进程使独立调度和分派的基本单位
同一个或不同的进程内多个线程可以并发执行
进程是拥有资源的基本单位，多个线程共享该进程拥有的资源
同一个进程里不同线程的独立性比不同进程间的独立性低得多
线程的系统开销小
支持多处理机系统
调度的概念、处理机调度算法的层次
调度：资源分配
高级调度：作业
低级调度：进程
中级调度：内存
处理机调度算法的共同目标
提高资源利用率
公平性
平衡性
策略强制执行
作业控制块–JCB
作业在系统中存在的标志，保存了系统对作业管理和调度所需的全部信息
作业调度算法
先来先服务–FCFS
短作业优先–SJF
优先级调度算法–PSA
高响应比优先调度算法–HRRN
为什么需要高响应比优先算法、优缺点
同时考虑了作业的等待时间和执行时间
优点：实现了较好的折中；
缺点：计算响应比，增加了系统开销；
进程调度算法
抢占/非抢占
暂停某个正在执行的程序，重新分配处理机给另一个进程
轮转调度算法–RR
用时间片切换的方式执行FCFS策略
优先级调度算法
实时调度：抢占/非抢占，最早截至时间有限算法、最低松弛度优先算法
最早截止时间优先EDF算法
- 抢占式调度算法基于周期实时任务
其中A周期20ms，每个周期处理时间10ms
B周期50ms，每个周期处理时间25ms
- 非抢占式调度算法基于非周期实时任务
最低松弛度优先LLF算法
松弛度是实时变化的，即任务的距离截止时间的距离
优先级倒置
即高优先级进程(或线程)被低优先级进程(或线程)延迟或阻塞
死锁
资源
- 可抢占资源
这类资源可以被系统从当前持有它的进程中强制收回，而不会对系统或进程造成灾难性影响。
- 不可抢占资源
这类资源一旦被某个进程占用，除非发生错误或异常，否则不能被其他进程抢占。
死锁
因此，当一组进程中额每个进程都在等待一个事件，而这个事件只能由该组中的另一个进程来触发时，就发生了死锁
操作系统处理死锁的方法是什么都不做，由用户决定——鸵鸟算法
资源死锁的条件
互斥条件：每个资源在任意时刻只能被一个进程占用，或者处于可用状态等待被分配
保持和等待条件：已经持有至少一个资源的进程，还可以请求获取新的资源，并且在新资源被分配给它之前，不会释放已经持有的资源
不可抢占条件：资源只能由持有它的进程释放，而不能被其他进程强制抢占
循环等待条件：系统中必然存在一个或多个进程组成的循环连，其中每个进程都在等待下一个进程持有的资源，而最后一个进程又在等待第一个进程持有的资源
破坏死锁
即破坏以上四个条件，但实际上不会采用
避免死锁
- 单个资源的银行家算法
死锁检测与恢复
死锁检测：构建资源分配表
死锁恢复：抢占式恢复、回滚恢复
程序的装入、链接方式
绝对装入方式：物理地址=逻辑地址
可重定位装入方式：物理地址=逻辑地址+offset，地址变换在装入时完成
动态运行时的装入方式：程序真正执行时才进行地址转换，装入内存后的所有地址仍是逻辑地址
静态链接：程序运行前
装入时动态链接：边装入边链接
运行时动态链接：在程序运行时链接
动态分区分配算法
基于顺序搜索
首次适应算法–First Fit：空闲分区链从地址递增的次序链接
循环首次适应–NF：从上次找到的空闲分区的下一个分区开始找，直到找到一个空闲分区
最佳适应–BF：要求按照容量从小到大的顺序排列空闲分区形成空闲分区链
最坏适应–WF：要求按照容量从大到小的顺序排列空闲分区形成空闲分区链
基于索引搜索
快速适应算法–分类搜索法
伙伴系统
分页存储管理方式
页面/物理块
地址结构：若逻辑地址为A，页面大小L。则页号=INT[A/L]，页内地址=A MOD L
页表
访问内存的有效时间
访问一次内存的时间为t
没有快表：2t
有快表：a为命中率，λ为访问一次快表的时间。有效访问时间EAT=t+aλ+(1-a)(λ+t)
分段和分页的区别
页是信息的物理单位；段是信息的逻辑单位。
页的大小固定且取决于系统；段长度不定取决于程序。
页是一维的；段是二维的。
虚拟存储器
局部性原理定义、表现在哪几个方面
局部性原理：在一段较短时间内，程序的执行仅局限于某个部分。相应地，它所访问地存储空间也局限于某个区域。
表现在：
时间局部性：一段时间内
空间局部性：一旦程序访问了某个存储单元，不久之后，其附近存储单元将被访问
虚拟存储器定义
具有请求调入和置换功能，能从逻辑上对内存的容量加以扩充的一种存储器系统。其容量由内存容量和外存容量之和决定，速度接近于内存。
页面置换算法
最佳置换算法
先进先出页面置换算法FIFO：先淘汰先进入内存的页面
最近最久未使用LRU置换算法
最少使用LFU
clock置换算法：链成循环队列；设置访问位，被访问置为1，转一圈置为0；换走访问位为0的页面
页面缓冲算法PBA：系统为每个进程分配一定数目的物理块，自己保留一部分。空闲页面链表，修改页面链表。
IO
IO系统的基本功能
隐藏物理设备细节，与设备的无关性，提高处理机和IO设备的利用率，对IO设备进行控制，确保对设备的正确共享和错误处理。
IO软件的层次结构
IO系统接口类型
块设备接口、流设备接口、网络通信接口
对IO设备的控制方式
轮询的可编程I/O方式
中断的可编程I/O方式
直接存储器访问方式
I/O通道控制方式
与设备无关的IO软件定义
应用程序中所用的设备，不局限于使用某个具体的物理设备，应用程序为实现设备独立性引入了逻辑设备和物理设备，在应用程序中使用逻辑设备名，系统执行时使用物理设备名
什么是假脱机技术–SPOOLING系统
缓和CPU和I/O的速度矛盾
引入缓冲区的原因
缓和CPU与I/O设备速度不匹配的矛盾
减少对CPU的中断效率，放宽对CPU中断响应时间的限制
解决数据粒度不匹配的问题
提高CPU和I/O设备之间的并行性
磁盘管理
磁盘调度算法
先来先服务FCFS
最短寻道时间优先SSTF
扫描SCAN
循环扫描CSCAN
文件系统
文件扩展名
文件的逻辑结构：按文件组织方式分类
顺序文件，索引文件，索引顺序文件
顺序文件记录寻址方式
隐式寻址：指针+偏移量
显式寻址：
- n*偏移量，随机访问
- 关键字，逐个比较
文件控制块FCB
用于描述和控制文件。包含基本信息、存取控制信息、使用信息。
树形目录、当前目录定义
树形目录：数据文件称为树叶，其他目录作为结点
当前目录（工作目录）：从树根到树叶的路径名
外存的组织方式
连续组织方式：连续的磁盘空间
链接组织方式：用指针链在一起
索引组织方式：索引式文件结构
连续方式的优缺点
优点：顺序访问容易、速度快
缺点：要求为一个文件分配连续的存储空间；必须事先知道文件长度；不能灵活删除和插入记录；对于动态增长的文件难以分配
链接方式(隐式和显式)的优缺点
优点：消除磁盘外部碎片，提高外存利用率；对插入删除修改记录都很容易；适应文件的动态增长，无需事先知道文件大小
缺点：隐式只适合顺序访问，随机访问极其低效；可靠性较差；增大了内部碎片；
windows常用组织方式:FAT12、FAT16、FAT32、NTFS
文件存储空间的管理
空闲表法：空闲盘号+空闲盘块数
空闲链表法：空闲盘块链、空闲盘区链
位视图法
利用二进制的一位来表示磁盘中一个盘块的使用情况
RAID定义
廉价磁盘冗余阵列：并行交叉存取、磁盘镜像、校验
系统调用
用户程序获取OS服务的唯一途径。
提供了用户程序和操作系统内核间的接口。
本质上是应用程序请求OS内核完成某种功能时的一种特殊的过程调用。