02326 操作系统 ✒️

题型	题量	分值	总分
单选	20	1	20
填空	10	2	20
简答	5	4	20
综合	4	10	40

一、概论

计算机系统概念

定义：计算机系统是一种可以按用户的要求接收和存储信息、自动进行数据处理并输出结果信息的系统

分类

广义：机械式系统和电子式系统
电子式系统：模拟式和数字式计算机系统

计算机系统组成

集中了资源管理功能和控制程序执行功能的一种软件，称为操作系统

操作系统的定义

定义：操作系统是计算机系统中的一个系统软件，它是这样一些程序模块的集合：它们能有效地组织和管理计算机系统中的硬件及软件资源，合理地组织计算机工作流程，控制程序的执行，并向用户提供各种服务功能，使得用户能够灵活、方便、有效地使用计算机，并使整个计算机系统能高效地运行

组织和管理计算机系统中的硬件资源和软件资源
- 在操作系统中，设计了各种表格或数据结构，将所有的软硬件资源都加以登记
- 比如：PCB、系统设备表等
有效
- 指操作系统在管理计算机资源时要考虑到系统运行的效率和利源的利用率。要尽可能提高中央处理器的利用率，让它尽可能少的空转，应该在保证访问效能的前提下尽可能有效地利用其它资源
- 比如：减少内存、硬盘空间的浪费等
合理
- 指操作系统要“公平”对待不同的用户程序，保证系统不发生“死锁”和“饥饿”的现象
方便
- 指操作系统的人机界面要考虑到用户使用界面和程序接口两个方面的易用性、易学性和易维护性

操作系统的特征

并发性：是指在计算机系统中同时存在着若干个运行着的程序，从宏观上看，这些程序在同时向前推进
共享性：操作系统需与多个用户程序共用系统中的各种资源，比如CPU、内存、外部设备等
随机性：操作系统不能对所运行的程序的行为以及硬件设备的情况作出任何事先的假定

研究操作系统的观点

软件的观点
- 操作系统是一种大型系统软件，它是多种功能程序的集合。有外在特性（接口）和内在特性（与硬件交互）
资源管理的观点
- 操作系统负责登记谁在使用什么样的资源，系统中还有哪些资源空闲，当前响应了谁对资源的请求，以及回收那些不再使用的资源等
进程的观点
- 把操作系统看做由多个可以同时独立运行的程序和一个对这些程序进行协调的核心
- 侧重于分析系统各部分的并行工作，研究处理各项管理任务的分割以及这些管理任务相互之间的关系比如：竞争资源、进程通信等
虚拟机的观点
- 在操作系统的支持下，用户不需要直接使用硬件机器（裸机），而是通过操作系统提供的各种手段来控制和使用计算机
服务提供的观点
- 从用户的角度，站在操作系统之外观察操作系统，认为该服务提供者为用户提供了比裸机功能更强、服务质量更高、更方便灵活的虚拟机

操作系统的功能

进程管理

进程管理的实质：对中央处理器进行管理。或者称为处理机管理
多道程序技术：多个程序同时放入内存，如果一个程序因为等待某个条件而不能运行，就把处理器专用权转交给另一个可运行程序
进程的引入：为了描述多道程序的并发而引入
进程的简单定义：一个程序的运行过程
进程管理的内容：进程控制、进程同步、进程间通信、调度

存储管理

任务：管理计算机内存的资源
功能：
- 内存的分配与回收：当多个程序共享有限的内存资源时，要考虑如何为多个程序分配有限的内存空间，以及程序运行完毕还需要内存回收
- 存储保护：存储在内存中的多个程序和数据应该彼此隔离、互不侵扰
- 内存扩充：将辅助存储器作为内存的扩充空间

文件管理

任务：有效地支持文件的存储、检索和修改等操作，解决文件的共享、保密和保护问题，以便用户方便、安全地访问文件
功能：
- 文件存储空间的管理
- 目录管理
- 文件系统的安全性

设备管理

含义：指计算机系统中除了处理器和内存以外的所有输入输出设备的管理
功能：负责外部设备的分配、启动和故障处理

用户接口

从用户观点看，操作系统是用户与计算机之间的接口
任务：为用户提供一个使用系统的良好环境，使用户能有效地组织自己的工作流程，并使整个系统高效地运行

操作系统的体系结构

Windows

内核
- 功能：线程调度、陷入处理和异常调度、中断处理和调度、多处理器同步、供执行体使用的基本内核对象
硬件抽象层HAL
- 系统可移植性的关键部分，为运行在Windows操作系统上的硬件平台低级接口，隐藏了各种与硬件有关的细节，如VO接口等专用的和依赖于计算机平台的函数
执行体
- 属于内核，以系统函数的形式提供了系统的服务，可通过Win32API进行访问
系统进程和系统线程
- 执行系统代码

UNIX

内核层
- 是操作系统管理和控制中心，常驻内存。有两种接口：内核与硬件的接口和内核与shell的接口
- 内核本身分为两部分：进程控制子系统和文件子系统
系统层
- 内核层与应用层之间，供程序员开发调用，包括进程管理、文件管理、中断状态
应用层
- 面向用户操作的界面

Linux

内核、shell、文件系统和应用程序

Android

从低到高：应用程序层、应用框架层、系统运行库层和Linux内核层

操作系统的发展

操作系统分类

批处理操作系统

基本工作方式：
- 用户将作业交给系统操作员，系统操作员在收到作业后，并不立即将作业输入计算机，而是收到一定数量的用户作业之后，组成一批作业，再把这批作业输入到计算机中。这批作业可在系统中形成一个连续的、自动转接的作业流
- 系统操作员然后启动操作系统，系统自动、依次执行每个作业
- 最后由操作员将执行完毕的作业交给用户
特点：成批处理，用户不能干预自己作业的运行
目标：系统资源利用率高，作业吞吐率高
分类：简单批处理和多道批处理
设计思想：
- 在监控程序启动之前，操作员有选择地把若干个作业合并成一批作业，将这批作业安装在输入设备上。然后启动监控程序，监控程序将自动控制这批作业的执行
- 作业的运行与衔接都由监控程序自动控制，从而有效地提高了作业运行的效率
作业控制说明书
- 作业控制说明书是由作业控制语言编写的一段程序它通常存储在被处理作业的前面
- 作业的运行由作业控制说明书来传递给监控程序，运行过程中，监控程序读入并解释作业说明书，以控制各个作业步的执行
一般指令和特权指令
- 操作系统的运行模式：用户模式和特权模式
- 处理器的状态：目态和管态
- 机器指令：一般指令和特权指令
- 系统调用：用户程序不能直接使用特权指令，它们必须向操作系统请求这些功能，这些功能通过系统调用完成
系统调用的过程
- 首先，当系统调用发生时，由中断或异常处理程序，把控制流程转移到监控程序内的一些特定位置，处理器模式变为特权模式
- 其次，由监控程序执行被请求的功能
- 最后，恢复现场，运行模式转变为用户模式，控制权交给用户程序
SPOOLing技术：是多道程序设计的关键技术之一，也称为假脱机技术

分时操作系统

基本工作方式
- 在分时系统中，一台主机连接了若干个终端，每个终端可由一个用户使用。用户通过终端交互式地向系统提出命令请求，系统接收用户命令之后，采用时间片轮转方式处理服务请求，并通过交互方式在终端上向用户显示结果
特点：多路性、交互性、独占性、及时性

实时操作系统

使计算机能在规定的时间内，及时响应外部事件的请求，同时完成对该事件的处理，并能够控制所有实时设备和实时任务协调一致地工作的操作系统
目标：在严格时间范围内，对外部请求做出反应，系统具有高可靠性
分类：硬实时系统和软实时系统
能力：除了多道程序系统的基本能力外，还有以下功能
- 实时时钟管理
- 过载防护
- 高可靠性

嵌入式操作系统

在各种电器、电子和智能机械上，嵌入安装着各种微处理器或微控制芯片
嵌入式操作系统就是运行在嵌入式芯片环境中，对整个芯片以及它所操作、控制的各种部件装置等资源进行统一协调、调度、指挥和控制的系统软件

其他操作系统

个人计算机操作系统
网络操作系统
分布式操作系统

操作系统设计

二、操作系统的运行环境

处理器

构成

处理器一般由运算器、控制器和一系列寄存器以及高速缓存构成

运算器实现算数与逻辑运算。控制器控制程序运行流程
寄存器用于处理器执行指令的过程中暂存数据地址及指令信息
高速缓存：为CPU和内存提供一个高速的数据缓存区域

寄存器

用户可见寄存器，由编译程序分配，减少程序运行时访问内存的次数
- 一般包括数据寄存器，地址寄存器、条件码寄存器
控制和状态寄存器，用来控制处理器的操作
- 常见的寄存器是程序计数器（PC）、指令寄存器（IR）、程序状态字（PSW）

指令

执行的基本过程
- 读取指令，并将程序计数器的值变成下一条指令的地址
- 指令放入指令寄存器中，处理器解释并执行该指令
分类：访问存储器指令、I/O指令、算数逻辑指令、控制转移指令、控制器控制指令
- 特权指令：
  - 在操作系统中那些只能由操作系统使用的指令
  - 不允许一般用户使用
  - 比如：设置程序状态字、启动某设备、设置中断屏蔽字等
- 非特权指令：
  - 普通用户使用的指令

处理器的工作状态

管态：操作系统管理程序运行时的状态，又称内核态、系统态等，具有较高特权
目态：一般用户程序运行时的状态，又称用户态、普通态，具有较低特权
目态-》管态：唯一途径是通过中断。中断响应时交换中断向量，新的中断向量的PSW的处理器状态标志位管态
管态-》目态：可通过设置PSW指令，实现从操作系统到用户程序的转换
限制用户程序执行特权指令
- 当用户程序执行时，如果取到了一条特权指令，则处理器拒绝执行该指令，并形成一个“非法操作”事件。然后操作系统通知用户程序--程序中有非法指令

程序状态字

定义：为了解决处理器当前工作状态的问题，所有的处理器都有一些特殊寄存器，用以表明处理器当前的工作状态。用来指示处理器状态的寄存器
- 比如CF：进位标志、ZF：结果为零标志等
包括
- CPU的工作状态代码：指明当前的工作状态是管态还是目态
- 条件码：反映指令执行后的结果特征，比如结果为0等
- 中断屏蔽码：指出是否允许中断

计算机系统硬件部件

存储系统

类型
- 读写型存储器（RAM），用来存储随机存取的程序和数据
- 只读存储器（ROM），存放一些固化的程序
存储分块
- 存储的最小单位：位（bit）
- 最小编制单位：字节
- 分块：为了分配和管理方便，将内存划分为大小相等的块（物理页Page），以块为单位分配内存空间大小一般为512B，1KB、4KB、8KB等
层次结构：寄存器-》高速缓存 -》内存储器 -》磁盘存储器 -》远程存储（云存储）
- 局部性原理
  - 程序执行时，除了少部分的转移和过程调用指令外，在大多数情况下是顺序执行的
  - 过程调用将会使程序的执行轨迹，由一部分区域转至另一部分区域。即程序将会在一段时间内，都局限在这些过程的范围内运行
  - 程序中存在许多循环结构，这些虽然只由少数指令构成，但是它们将多次执行
  - 程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往都局限于很小的范围内
存储器保护
- 多道程序设计系统中，保证每个程序独立运行互不干扰，称为存储器保护
- 方法：界地址寄存器

I/O部件

1/O结构
通道
DMA技术
缓冲技术

时钟部件

发现死循环，防止机时的浪费
分时系统中，时钟间隔实现时间片轮转执行
实时系统中，按要求的时间间隔控制设备
定时唤醒各个外部事件
记录各种设备的使用时间和某外部事件发生的时间间隔
记录用户和系统所需的绝对时间，即年、月、日
分类：
- 硬件时钟和软件时钟
- 用途分：绝对时钟和相对时钟

中断机制

中断&异常

中断
- 指处理器对系统中或系统外发生的异步事件的响应
- 异步事件：指无一定时序关系的随机发生的事件，如外部设备完成了数据传输任务，某一实时控制设备出现异常情况等
- 中断源：引起中断的事件称为中断事件或中断源
- 中断请求：中断源向处理器发出的请求信号
- 中断处理程序：处理中断事件的程序
- 断点：发生中断时正在执行的程序的暂停点。
- 中断响应：处理器暂停当前程序转而处理中断的过程
- 中断返回：中断处理程序结束后恢复原来程序的执行
- 中断向量表：为了使得中断装置可以找到恰当的中断处理程序，专门设计了中断处理程序的入口地址映射表，又称中断向量表
异常
- 由正在执行的指令引|发的中断

典型的中断	典型的异常
时钟中断、输入输出中断、控制台中断、硬件故障中断	程序性中断，访管指令异常

中断系统

中断请求的接收
- 中断系统如何接受中断源的中断请求，因机器而异。一般由中断逻辑线路和中断寄存器实现
中断响应
- 处理器的控制部件中有中断信号扫描结构，它在每条指令执行周期内的最后时刻扫描中断寄存器，查看是否有中断信号到来。若无中断信号，处理器就继续执行下一条指令。若有中断到来，处理器接收由硬件中断装置发来的中断向量代号，准备中断处理准备工作
- 中断请求响应过程
  - 处理器接收中断信号
  - 保护现场
  - 分析中断向量
  - 将处理器的PC值置为中断程序的入口地址
  - 调用中断处理程序
中断处理
- 接收和响应中断
- 保护中断断点现场
- 分析中断向量，调用中断处理程序
- 中断处理结束恢复现场，原有程序继续执行
几种典型中断的处理
- I/O中断
- 时钟中断
- 硬件故障中断
- 程序性中断
- 系统服务请求

中断优先级、中断屏蔽与中断嵌套

多级中断与中断优先级
- 对各类中断信号依据其紧急程度和重要性划分级别，系统优先处理最紧急或最重要的任务
- 解决如果有多个中断信号同时到达，如何选择首个被处理的中断信号的问题
中断屏蔽
- 整个中断系统中，允许或者禁止中断系统对某些类别中断的响应。PSW中设计有中断屏蔽位
中断嵌套
- 一般的计算机系统都有多个中断源，如果一个中断处理的过程中又发生了中断，有两种策略处理
  - 当处理一个中断时禁止其他中断
  - 中断嵌套。即中断按照优先级划分，允许优先级别高的中断优先级低的中断处理过程，优先进行处理

系统调用

概述

系统调用概念
- 就是用户在程序中调用操作系统提供的一些子功能，是操作系统提供给编程人员的唯一接口
- 是一种特殊的过程调用，由特殊的机器指令实现，这条指令将系统转入管态
分类
- 进程控制类
- 文件操作类
- 进程通信类
- 设备管理类
- 信息维护类

	系统调用	函数调用
运行的不同状态	管态	目态
状态转换	目->管->目	--
返回问题	不一定运行原本程序	运行原本程序
嵌套调用	允许	允许

系统调用的处理过程

在系统中为控制系统调用服务的机构称为陷入或异常处理机构
把由于系统调用引起处理器中断的指令称为陷入或异常指令（或称访管指令）

三、进程&线程

多道程序设计

程序的顺序执行

顺序程序设计
- 程序是在一个时间上按严格次序前后相继的操作序列
- 我们把一个具有独立功能的程序独占处理器直到得到最终结果的过程称为程序的顺序执行
特点
- 顺序性：程序所规定的动作在机器上严格地按顺序执行
- 封闭性：程序运行后，其计算结果只取决于程序自身，程序执行得到的最终结果由给定的初始条件决定，不受外界因素影响
- 程序执行结果的确定性：程序执行的结果与其执行速度无关
- 程序执行结果的可再现性：如果程序在不同的时间执行，只要初始条件相同则结果就会相同

程序并发执行

说明
- 指两个或两个以上程序在计算机系统中，同时处于已开始执行且尚未结束的状态
- 能够参与并发执行的程序称为并发程序。并发程序的执行和程序顺序执行的特征不同
特点
- 在执行期间并发程序相互制约
- 程序与计算不再一一对应
  - 允许多个程序共享一个程序段
- 并发程序的执行结果不可再现
  - 并发程序与其执行的相对速度以及并发执行的多道程序之间的相互关系有关
- 程序的并行执行和程序的并发执行
  - 程序的并发执行是宏观上的同时，微观是顺序。并行则是微观上是同时的

多道程序设计

概述
- 是允许多个程序同时进入内存并运行。根本目的是提高整个系统的效率
- 吞吐量：是指单位时间内系统所处理进程的道数，是衡量系统效率的尺度
特点
- 独立性
  - 在多道环境下执行的每道程序都是逻辑上独立的，且执行速度与其他程序无关，执行的起止时间也是独立的
- 随机性
  - 程序和数据的输入与执行开始时间都是随机的
- 资源共享性
缺陷
- 可能延长程序的执行时间
- 系统效率的提高有一定限度

进程

进程的定义

进程是具有一定独立功能的程序在某个数据集合上的一次运行活动，是系统进行资源分配和调度的一个独立单位。
分类：系统进程和用户进程
进程与程序的联系和区别
- 联系
  - 程序是构成进程的组成部分之一，一个进程的运行自标是执行它所对应的程序
  - 进程=程序+数据+进程控制块
- 区别
  - 程序是静态的，进程是动态的
  - 二者是多对多的关系
可再入程序
- 一个能够被多个用户同时调用的程序称作是可再入程序
- 可再入程序必须是纯代码，程序在执行过程中不会修改自己的代码，必须与数据区隔离
特征
- 并发性
- 动态性
- 独立性
- 交往性
- 异步性
- 结构性

进程的状态与转换

三状态进程模型
- 运行状态
- 就绪状态
- 等待状态
五状态进程模型
- 运行状态
- 就绪状态
- 阻塞状态
- 创建状态
- 结束状态

进程控制块

为了便于系统控制和描述进程的活动过程，在操作系统核心中定义了一个专门的数据结构，称为PCB（Process Control Block）
作用
- 描述进程的基本情况以及进程的运行变化过程
- 是进程存在的唯一标志，当系统创建一个进程时，为进程设置一个PCB，再利用PCB对进程进行控制和管理。撤销进程时，系统收回PCB，进程也随之消亡
内容
- 调度信息
  - 供进程调度时使用，包括进程名、进程号、地址空间信息、优先级、当前状态、资源清单、家族关系、消息队列指针、进程队列指针和当前打开文件等
- 现场信息
  - 刻画了进程的运行情况，主要是CPU寄存器的信息，如程序状态字、时钟、界地址寄存器等。当程序中断时，需要保存现场信息
组织
- 线性方式
- 索引方式
- 链接方式
进程的队列
- 就绪队列
- 等待队列
- 运行队列

进程控制

对进程整个生命周期中各种状态之间的转换进行的控制
原语
- 创建原语
  - 一个进程可以使用创建原语创建一个新的进程，前者称为父进程，后者称为子进程，子进程又可以创建新的进程，从而形成一个进程家族
  - 主要任务：建立进程控制块PCB
  - 过程：先申请一空闲PCB，然后将有关信息填入PCB，置进程状态为就绪状态，插入就绪队列
- 撤销原语
  - 当一个进程完成任务后，就应当撤销它，以便及时释放它所占用的资源。
  - 撤销的实质：撤销进程控制块PCB
  - 过程：找到要被撤销进程的PCB，将它从所在队列中消去，撤销属于该进程的一切“子进程”，释放所占全部资源，并消去被撤销进程的PCB。
- 阻塞原语
  - 若某个进程的执行过程中需要I/O操作，则该进程调用阻塞原语将其从运行状态转换为阻塞状态
  - 过程：产生中断，把处理器的当前状态保存在PCB的现场信息中，当前进程置为等待态，插入等待队列
- 唤醒原语
  - 一个进程因为等待某事件的发生而处于等待状态，当该事件发生后，就用唤醒原语将其转换为就绪状态
  - 过程：在等待队列中找到该进程，将进程的当前状态置为就绪状态，然后将它从等待队列中撤出并插入到就绪队列中排队，等待调度执行

线程

概述

进程的属性
- 一个可拥有资源的独立单位
- 一个可独立调度和分派的基本单位
程序并发执行所需付出的时空开销
- 创建进程的开销：内存空间、IVO设备、PCB
- 撤销进程的开销：对其资源作回收
- 进程切换的开销：保留CPU环境，设置新进程CPU环境
引入线程的目的
- 引入进程是为了使多个进程并发执行
- 引入线程是为了减少程序并发执行时所付出的时空开销
线程：是进程中的一个实体，是处理器调度和分配的基本单位
- 一个线程可以创建和撤销另一个线程；同一个进程中的多个线程可以并发执行
- 属性
  - 每个线程有一个唯一的标识和一张线程描述表（TCB）
  - 不同的线程可以执行相同的程序
  - 同一个进程中的各个线程共享该进程的内存地址空间
  - 线程是处理器的独立调度单位，多个线程可以并发执行一个线程具有生命周期，经历等待、就绪、运行等状态变化
- 优势
  - 创建一个新线程花费时间少
  - 线程之间的切换花费时间少
  - 线程之间通信无需调用内核，不需要额外的通信机制，使通信简单、信息传送速度快

进程 & 线程

调度
- 线程作为调度的基本单位，同进程中线程切换不引起进程切换，当不同进程的线程切换时才引起进程切换
并发性
- 一个进程间的多个线程可并发，不同进程的多个线程也可以并发执行
拥有资源
- 线程仅拥有隶属进程的资源；进程是拥有资源的独立单位
系统开销
- 线程低，进程高

线程实现机制

用户级线程
- 仅存在于用户空间，由用户层中的线程库提供对线程的创建、撤销、切换，以及线程之间的同步与通信等的支持，而无须内核的支持
内核级线程
- 由OS直接支持，更灵活，方便
混合方式
- 结合用户级线程和内核级线程的优点，在用户空间实现线程的创建、撤销、切换，而在内核空间实现线程的调度和管理

进程调度

概述

主要功能
- 记录系统中所有进程的执行状况
- 根据一定的调度算法，从就绪队列中选出一个进程，准备把处理器分配给它
- 分配处理器
时机
- 正在执行的进程运行完毕
- 正在执行的进程由于某种错误而终止运行
- 时间片完
- 正在执行的进程调用阻塞原语将自己阻塞起来
- 创建了新的进程
- 正在执行的进程调用了唤醒原语操作激活了等待资源的进程
处理器的调度方式
- 非抢占式
  - 一旦把处理机分配给某进程后，就一直让它运行下去，决不会因为时钟中断，或任何其它原因，去抢占该正在运行进程的处理机，直至该进程完成，或发生某事件而被阻塞时，才把处理机分配给其它进程
- 抢占式
  - 允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机，重新分配给另一进程
  - 抢占方式能满足实时任务的需求。但抢占方式比较复杂，所需付出统开销也较大

调度算法设计原则

进程行为：I/O密集型、计算密集型
系统分类：批处理、交互式、实时系统
设计目标
- 共同目标：资源利用率高、公平、平衡、强制执行策略
- 批处理目标：平均周转时间短、系统吞吐量高、处理机利用率好
- 分时系统目标：响应时间快、均衡性
- 实时系统目标：截止时间的保证、可预测性

进程调度算法

先来先服务
- 思想：总是把处理机分配给最先进入就绪队列的进程，一个进程一旦分得处理机，便执行下去，直到该进程完成或阻塞时，才释放处理机
- 优点：实现简单
- 缺点：没考虑进程的优先级
最短进程优先
- 思想：该算法从就绪队列中选出“下一个CPU执行期”最短的进程，为之分配处理机
- 优点：所有进程都同时可运行时算法最优
最短剩余时间优先算法
- 思想：总是选择剩余时间最短的那个进程运行。当一个新的进程到达时，其整个时间同当前进程的剩余时间做比较，如果新进程时间更少，则当前进程被挂起，运行新进程
最高响应比优先算法
- 思想：总是优先调度响应比最大的进程
- 性能：先来先服务和最短进程优先算法的折中
- 响应比 = (等待时间 + 服务时间) / 服务时间 = 1 + 等待时间/服务时间
轮转算法
- 思想：将处理器的处理时间划分成一个个时间片，就绪队列中的诸进程轮流运行一个时间片，当时间片结束时就强迫运行进程让出处理器，该进程进入就绪队列，等待下一次调度
- 影响时间片设置的因素
  - 系统响应时间
  - 就绪进程数目
  - 计算机的处理能力
最高优先级算法
- 思想：为每个进程设立一个优先级，每次将处理器分配给具有最高优先级的就绪进程
多级反馈队列算法
- 思想要点
  - 被调度队列的设置
  - 在同一个队列内的调度原则
  - 在不同调度队列之间的调度原则
  - 进程优先级的调整原则

系统内核

定义：为了提高系统的运行效率、保护系统的关键部分不被破坏，一般把操作系统中提供支持系统运行的各种基本操作和基础功能的一组程序模块集中安排，形成一个操作系统的核心
位置：内核本身不是进程，是系统进程和用户进程赖以活动的基础，一般内核常驻内存，操作系统其它部分则根据需要调进或调出内存
功能：
- 中断处理程序
- 进程同步与互斥
- 进程调度
- 进程控制与通信
- 存储管理
- 时钟管理

四、进程同步 & 互斥

进程间相互作用

相关进程：在逻辑上具有某种联系的进程
- 三个进程，分别是读数据进程、处理数据进程、打印结果进程，它们相互依赖、相互合作，是一组相关进程
无关进程：在逻辑上没有联系的进程
- 为两个不同的源程序进行编译的进程，它们可以并发执行，但它们之间无关
有时间有关的错误
- 对于相关进程来说，可能有若干并发进程同时使用共享资源，即一个进程一次使用未结束，另一进程也开始使用，形成交替使用共享资源

进程同步与互斥

同步（直接制约）
- 是指进程之间一种直接的协同工作关系，一些进程相互合作共同完成一项任务
互斥（间接制约）
- 在系统中，许多进程常常需要共享资源，而这些共享资源往往需要排他性的使用，即一次只能为一个进程服务，因此，各进程间只能互斥使用这些资源
临界资源
- 若在系统中的某些资源一次只允许一个进程使用，则这类资源称为临界资源或共享变量
临界区
- 访问临界资源的那段代码
相关临界区
- 如果有若干进程共享某一临界资源，则该临界区称为相关临界区
相关临界区的调度使用原则
- 当临界资源空闲时，若有一个进程要求进入临界区，应充许它立即进入【有空让进】有效利用资源
- 若有一个进程已在临界区，其他要求进入临界区的进程必须等待【无空等待】互斥进入
- 当没有进程在临界区，而同时有多个进程要求进入临界区，选择其一进入，其他等待【多种择一】
- 任一进程进入临界区的要求应在有限时间满足【有限等待，避免死等】
- 处于等待状态的进程应放弃占用处理器【让权等待，避免忙等】

信号量及P、V操作

为保证进程的同步与互斥，系统中应该有解决这些问题的机制，称为同步机制
实际上，同步是并发进程之间的执行时序上的一种相互制约关系
进程互斤的实质也是同步，可把进程互斥看做是一种特殊的进程同步
同步机制有两类：硬件同步机制、软件同步机制

信号量

1965年，荷兰学者Dijkstra首先提出，除初始化外，仅能通过两个标准的操作P操作和V操作来访问

信号量与P、V操作的物理含义

信号量S表示某类可用的资源。对于不同的资源，用不同的信号表示
- $S>0$ ，S表示某类资源的可用数量
- $S<0$ ，其绝对值表示排在S等待队列中进程的数目
- 执行一次P操作，表示请求一个资源
- 执行一次V操作，表示进程释放一个资源

用P、V操作实现进程之间的互斥

假设有进程A、B竞争进入临界区，用P、V操作实现进程之间的互斥，首先定义互斥型信号量S，并使之初值为1

用P、V操作实现进程之间的同步

S1=0，S2=0

有三个进程，进程get从输入设备上不断读取数据，并放入缓冲区buffer1；进程copy不断地将缓冲区buffer1中的内容复制到缓冲区buffer2；进程put坝j不断将buffer2中的内容在打印机上输出

S1：初始值为1，保证get进程能够从设备读数据到buffer1
S2：初始值为0，copy进程能否将buffer1的内容复制到buffer2
S3：初始值为0，put进程能否将buffer2的内容
打印输出S4：初始值为1，保证buffer2缓冲区可以使用

PV操作总结

P、V操作必须成对出现
互斥操作时，P、V操作出现在同一个进程
同步操作时，P、V操作出现在不同进程
既有同步，又有互斥操作时，同步信号量P操作在前，互斥信号量P操作在后，V操作顺序不限

经典的进程同步问题

简单生产者--消费者问题

制约关系
- 每次只能放置一个产品，缓存区容量为1
- P进程不能往已经满的缓冲区放产品， Q进程不放从空缓冲中取产品

信号量设置
- empty，初值为1，用于指示空缓冲区数量
- full，初值为0，用于指示满缓冲区数量

多个生产者--消费者问题

设有若干个生产者P1、P2若干个消费者Q1、Q2他们通过一个环形缓冲池联系起来

生产者不能往“满”缓冲区中放产品，设置信号量empty，初始值为k，指示缓冲池中空缓冲区数目
消费者不能从“空”缓冲区中取产品，设置信号量full，初始值为0，指示缓冲池中的满缓冲区数目
缓冲池必须互斥访问，设置信号量mutex，初值为1
整型量ij，初值为0，分别用于指示空缓冲区和满缓冲区位置

读者--写者问题

问题描述
- 多个进程可以同时读文件F
- 当一个进程在对文件F进行写时，不允许其他进程对文件进行读或写
- 当有进程正在读文件时不允许任何进程去写文件
变量设定
- read_count：整型量，当前正在读的读者进程个数来一个读者，数量加1，走一个读者，数量减1
- mutex：互斤信号量，对read_count互斥访问
- write：互斥信号量，写者与写者的互斥，写者与读者之间的互斥

读者进程写者进程

while(1){
    P(mutex)
    read_count++
    if(read_count == 1){
        P(write)
    }
    V(mutex)
    读文件
    P(mutex)
    read_count--
    if(read_count == 0){
        V(write)
    }
    V(mutex)
}

while(1){
    P(write)
    写文件
    V(write)
}

管程

信号量及PV操作的缺点
- 程序易读性差
- 程序不利于修改和维护
- 正确性难以保证
定义
- 是一个由过程变量及数据结构等组成的一个集合，它们组成一个特殊的模块或软件包。进程可在任何需要的时候调用管程中的过程
组成
- 管程名称、共享数据说明、对数据进行操作的组过程、对共享数据赋初值的语句

进程通信

共享内存原理
- 在相互通信的进程之间设有一个公共内存区，一组进程向该公共内存中写，另一组进程从公共内存中读，通过这种方式实现两组进程之间的信息交换
消息缓冲通信原理
- 进程间的数据交换，是以格式化的消息（也称为报文）为单位的。程序员直接利用操作系统提供的一组通信命令（原语），实现大量数据的传递，通信过程对用户是透明的
信箱通信原理
- 为了实现进程间的通信，可以设计一个通信机构【信箱】，以发送信件和接收信件为进程间通信的基本方式
管道
- 是指用于连接一个读进程和一个写进程以实现他们之间通信的一个共享文件，又名pipe文件

五、死锁

死锁的产生

死锁
- 指在多道程序系统中，一组进程中的每一个进程均无限期地等待被该组进程中的另一个进程所占用且永远不会释放的资源
- 处于死锁状态的进程称为死锁进程
资源分类
- 永久性资源（可重用资源）
  - 如内存、外部设备、处理器等硬件资源。各种数据文件、表格、共享程序代码等软件资源
- 临时性资源（消耗性资源）
  - 指由某个进程产生、只为另一个进程使用一次或经过短暂时间后便不再使用的资源
产生死锁的原因
- 竞争资源
  - 系统在资源分配时出现失误、进程间对资源的相互争夺而造成僵局
- 进程推进顺序不合理
产生死锁的必要条件
- 互斥条件
- 不可剥夺条件
- 请求和保持条件
- 循环等待条件
解决死锁的方法
- 预防死锁
- 避免死锁
- 检测与解除死锁
- 忽略死锁

死锁预防

是指在任何系统操作前（如分配资源、调度进程等），事先评估系统的可能情况，严格采取措施，使得产生死锁的四个必要条件不成立
基本思想：防惠于未然
具体做法：破坏产生死锁的四个必要条件之一
静态的资源分配策略
- 分配原则：一个进程在申请新资源的要求得不到满足时，便处于等待状态，而处于等待状态的进程的全部资源可以被剥夺
  - 破坏不可剥夺条件
    - 若一个进程已占用了某些资源，又要申请新的资源，在得不到新资源的同时释放原有资源，然后等待
    - 若一个进程申请新资源，首先系统检查该资源是否可用，如果可用则分配。否则从其他等待进程剥资源分配给该进程，如果没有等待进程占有该资源，该程必须等待，在等待过程中，资源也可能被剥夺
  - 破坏请求和保持条件
    - 每个进程必须在开始执行前就申请它所需要的全部资源，仅当系统能满足进程的资源请求且把资源一次性分配给进程后，该进程才能开始执行
资源的有序分配法
- 策略：破坏循环等待条件
- 方法：对系统所有资源类型进行线性排序，并赋予不同的序号。进程申请资源时，必须严格按照资源编号的顺序进行。即一个进程先得到编号小的资源，才能申请编号大的资源。释放资源时，次序相反
- 一般原则：较为紧缺、稀少的资源的编号较大

死锁避免

基本思想
- 系统对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源；如果分配后系统不会发生死锁，则予与分配，否则，不予分配
和死锁预防的区别
- 死锁预防是破坏产生死锁的四个必要条件之一，严格地防止死锁的出现。而死锁避免是在系统运行过程中注意避免死锁的发生，即使死锁的必要条件存在也不一定发生死锁
安全状态
- 如果操作系统能保证所有的进程在有限时间内得到所需的全部资源，则称系统处于安全状态，否则说系统是不安全的
安全序列
- 系统能按某种进程推进顺序{P1，P2，Pn}，为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。此时称{P1，P2，Pn}为安全序列
银行家算法
- 保证系统不会进入不安全状态的算法

死锁的检测与解除

假如系统为进程分配资源时，不采取任何限制性措施来避免和预防死锁，而是在操作系统运行过程中，不断地监督程序的执行和资源占用情况，判断是否发生死锁，一旦发生死锁，采取专门的措施解除死锁，并以最小代价使系统恢复正常
检测的实质：检测算法检测是否存在“循环等待”条件
时机
- 一次资源分配后
- 每次调度后
- 定时器定时运行检测程序
- 当某个进程长期处于阻塞状态或阻塞程序过多时
算法规则
- 当进程Pj申请一个已被占用的资源Ri时，进行死锁检测，反复查找资源分配表和等待进程表，来确定Pj对资源Ri的请求是否导致形成环路，若是，出现死锁
解除死锁的方法
- 剥夺资源
  - 一旦死锁，挂起一些进程，剥夺它们占有的资源给死锁进程，以解除死锁
- 撤销进程
  - 撤销部分死锁进程，将它们占有的资源分配给另一些死锁进程，直到死锁解除为止
  - 可以一次撤销所有死锁进程，也可以逐个撤销

资源分配图

作用
- 描述系统中资源分配和申请情况，对死锁进行分析并采取对策
SRAG定义
- 有向图，可定义为一个二元组，即 $SRAG=(V,E)$ ，其中V是顶点的集合，包括进程集合、资源集合E是有向边的集合，是一个有序对 $< Pi,ri>$
作用：判定死锁的法则
死锁定理
- 如果资源分配图中没有环路，则系统无死锁
- 如果资源分配图中出现了环路，则可能存在死锁
  - 如果处于环路中的每个资源类中均包含一个资源实例则环路存在意味着死锁的存在。此时，环路是死锁的充分必要条件
  - 如果处于环路中的每个资源类中实例的个数不全为1，则环路存在是死锁的必要条件而非充分条件
资源分配图简化方法
- 找出一个既不阻塞又非独立的进程结点Pi。在顺利的情况下，Pi可获得所需资源而继续运行，直至运行完毕，再释放其所占有的全部资源，这相当于消去pi的请求边和分配边，使之成为孤立的结点
- 将P释放的资源分配给申请它的进程，若该进程能顺利运行完，释放资源，再次成为孤立结点
- 重复上面两步，直到找不到符合条件的进程结点

哲学家就餐问题

有五个哲学家围坐在一圆桌旁，每人面前有一只碗，碗里有面条，每两人之间放一只筷子
每个哲学家的行为是思考，感到饥饿，然后吃饭
为了吃饭，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子

六、存储管理

概述

内存空间一般分为两个区域
- 系统区：存放操作系统常驻内存部分，用户不能占用这部分空间
- 用户区：分配给用户使用，用于装入和存储用户程序和数据，随时变化
  - 存储管理的实质：用户空间的管理
内存管理问题主要包括
- 内存管理方法
- 内存的分配与释放算法
- 虚拟存储器的管理
- 控制内存和外存之间的数据流动方法
- 地址变换技术
- 内存数据保护和共享技术

存储管理的任务

内存的分配与回收
- 功能
  - 记住每个存储区域的状态：空闲与否
  - 实施分配：用户提出请求，分配内存
  - 回收：回收用户释放的区域
- 内存分配表
  - 位示图表示法
  - 空闲页面法
  - 空闲块表法
- 内存分配方式
  - 静态分配：程序运行前分配内存，不允许搬家
  - 动态分配：程序运行时允许动态分配内存，且允许搬家
存储共享
- 所谓存储共享是指两个或多个进程共用内存中相同区域
- 包括：代码共享和数据共享
- 目的：节省内存空间，提高内存利用率；通过内存共享实现进程通信
存储保护
- 目的：为多个程序共享内存提供保障，使在内存中的各道程序，只能访问它自己的区域，避免各道程序间相互干扰
- 方法：
  - 地址越界保护
  - 权限保护
扩充内存容量
- 用户在编制程序时，不应该受内存容量的限制，所以要采用一定技术来扩充内存的容量，使得用户得到比实际内存容量大得多得内存空间
- 借助虚拟存储技术或交换技术完成，达到在逻辑上扩充内存容量的目的

地址转换

地址重定位
- 绝对地址：存储器以字节为单位编址，每个字节都有对应的地址。假定内存容量为n，则编号顺序为0,1,2,n-1，该地址称为物理地址或绝对地址
- 物理地址空间：由绝对地址对应的内存空间
- 逻辑地址：在多道程序系统中，内存中同时存储了多个用户程序，每个用户不能预先知道他的程序被存储到了什么地方。为了方便，每个用户都可认为自己的程序和数据存储在一组“0”地址开始的连续空间中，用户程序中使用的地址，称为逻辑地址或相对地址
- 逻辑地址空间：由逻辑地址对应的存储空间
- 当用户把程序装入内存时，存储管理为他分配的内存空间可能是从某一单元开始的一组连续的地址空间，它的起始地不固定，即逻辑地址与物理地址经常不一致，这就是地址重定位
静态重定位：内存在装入一个程序时，把程序中的指令和数据地址全部装换为绝对地址，该过程在程序运行前进行，程序运行过程中无需再转换
动态重定位：内存在装入程序时，不进行地址转换，而是直接把程序装入到分配的内存中，程序在执行过程中完成地址的转换

分区管理方案

固定分区

基本思想
- 多道程序环境下，整个用户空间划分为若千个固定大小的区域，每个分区中只装入一道作业。分区大小可以相同也可以不同
内存分配表与分区的分配、回收
- 内存分配表是一张分区说明表，记录分区号、分区大小、分区起始地址及使用状态等
- 分配时按照进程的内存需求，按一定策略从分区表中找到空闲分区进行分配
- 回收时，将内存分区登记在分区说明表中，并将其状态置为空闲状态

可变分区

基本思想
- 系统不预先划分固定分区，而是在装入程序时划分内存分区，使为程序分配的内存区的大小正好等于程序的需求量，且分区的个数是可变的
紧缩技术
- 注意点：增加系统开销、移动是有条件的
实现过程
- 硬件支持
  - 两个专用控制寄存器：基址寄存器和限长寄存器
- 绝对地址形成
  - 程序装入内存后，分区的起始地址和长度装入两个寄存器，程序执行后，取出指令中的逻辑地址，绝对地址=逻辑地址+基址寄存器内容
- 地址越界
  - 当逻辑地址>限长寄存器值时，产生地址越界中断
分配策略
- 首次适应算法
  - 思想：当接到内存申请时，查找分区说明表，直到找到一个大小能满足要求的空闲分区为止，将其分割并分配
  - 优点：简单，可以快速做出分配决定
- 最优适应算法
  - 思想：当接到内存申请时，查找分区说明表，找到一个大小能满足要求的最小空闲分区，将其分割并分配
  - 优点：节约空间
  - 缺点：形成许多碎片
- 最坏适应算法
  - 思想：当接到内存申请时，查找分区说明表直到找到一个大小能满足要求的最大空闲分区，将其分割并分配
  - 优点：碎片少
  - 缺点：分割了大的空间，遇到较大申请，无法满足
分区回收
- 回收区与插入点的上邻空闲分区F1相邻接
- 回收分区与插入点的下邻空闲分区F2相邻接
- 回收区同时与插入点的上、下两个空闲分区相邻接
- 回收区既不与F1邻接，又不与F2邻接
分区保护
- 系统设置界限寄存器，包括：上、下界寄存或基址、限长寄存器
- 保护键方法
优点：
- 简单、表格不多，实现起来容易，内存额外开销小，保护措施也简单
- 在内存利用率方面可变分区比固定分区高
缺点：
- 碎片多，不能为用户提供虚存，每个用户程序的存储受物理存储的限制

覆盖与交换技术

覆盖技术

概念
- 是指一个程序的若干程序段，或几个程序的某些部分共享某一个存储空间
实现
- 把程序划分为若干个功能上相对独立的程序段，按照其自身逻辑结构使那些不会同时执行的程序段共享同一块内存区域
解决的问题
- 从用户级彻底解决内存小装不下程序的问题
优点
- 打破了需要将一个程序的全部信息装入内存后程序才能运行的限制
- 在逻辑上扩充了内存空间，从而在某种程度上实现了在小容量内存上运行较大程序的功能
缺点
- 对用户不透明，增加了用户的负担

交换技术

交换的含义
- 进程从内存移到磁盘，并再移回内存
适用场合
- 分时系统和大多数现在操作系统，是虚拟存储系统的基础
主要内容
- 换出进程的选择
- 交换时机的确定
- 交换空间的分配
- 换入进程换回内存时位置的确定

虚拟页式存储管理方案

虚拟存储技术

基本思想
- 利用大容量外存来扩充内存，产生一个比有限的实际内存空间大的多的、逻辑的虚拟内存空间，简称虚存
- 采用二级存储器方式
- 是一种设计技巧，受外存容量的限制
硬件支持
- 系统有容量足够大的外存
- 系统有一定容量的内存
- 实现虚-实转换的地址映射机制
工作原理
- 程序部分装入内存便可运行，其他部分需要运行时再装入内存
与交换技术的区别
- 交换技术交换单位是进程
- 虚拟内存以页为单位进行交换

虚拟页式存储管理

物理页面和页面
- 物理页面：将内存分成大小相等的许多区，每个区称为一个物理页面（物理块、页帧）
- 页面：将程序中的逻辑地址也进行分页，页的大小和物理页面大小一致
虚拟地址组成
- 虚拟页号
- 页内地址

物理内存的分配与回收

位示图
- 位示图中的每一位与一个物理块对应，其值为0/1，表示空闲/占用
- 分配：在位示图中找出空闲物理页面数，如果能满足，则分配，并把相应位置为1，计算物理页面号
  - 物理页面号=字号×字长+位号
- 回收，当归还物理页面时，计算归还页面在位示图中对应的位置，将1改为0
  - 字号=i/字长，位号=i mod 字长

虚拟页式存储地址转换过程

页式存储管理的地址转换
- 页表：记录装入内存的逻辑页面与物理页面的对应关系
- 是硬件进行地址转换的依据
地址转换过程
- 在执行检索前，先将页号与页表长度进行比较，若页号大于或等于页表长度，则地址越界
- 若未出现越界错误，则将页表始址与页号和页表项长度的乘积相加，则找到该表项在页表中的位置，找到该页的物理页号
- 将有效地址的页内地址送入物理地址寄存器的块内地址字段中
计算方式
- 十进制：物理地址=物理页面号*块长+页内地址
- 二进制：物理页面号作为绝对地址的高位地址，页内地址作为它的地址部分

在一分页存储管理系统中，逻辑地址长度为16位，页面大小为4096字节，现有一逻辑地址为2F6AH，且第0、1、2页依次存放在物理块5、10、11中，问相应的物理地址为多少？
逻辑地址：2F6AH转二进制 0010 1111 0110 1010B
逻辑地址长度为16，页面大小为4096 = 2^12，故页内位移12位，页号占4位（前4位，值为2）
页号2对应的物理页面号为11，11转成二进制为1011 即B
1011 1111 0110 1010B = BF6AH

页表项
- 物理页面号：页面在内存对应的物理页面号
- 有效位：页面是在内存还是外存
- 访问位：页面在内存中是否被访问过
- 修改位：页面在内存中是否被修改过
- 保护位：页面能否读/写
转换检测缓冲区（TLB）
- 高速缓存，也称为快表，登记了页表中的部分页号和物理页面的对应关系
缺页异常处理
- 缺页异常：若在页表中发现所要访问的页面不在内存，则产生缺页异常
- 处理：查看有无空闲页面，若有，把要访问的页面调入内存；若无，选择一页换出内存，再把要访问的页面调入内存
页面调度策略
- 调入策略：决定什么时候将一个页由外存调入内存。两种方法：请求调页和预调页
- 置页策略：当产生缺页时，将所调入的页面置于何处
- 置换策略：如果内存已满，确定哪个页面从内存中移出，为新的页面腾出空位。三种方法：固定分配局部置换、可变分配全局置换、可变分配局部置换
页面置换算法
- 抖动或颠簸：刚被换出的页面又立即要用，把它装入内存后，不久又被换出，换出不久又被调入内存，如此反复，使调度非常频繁
- 算法
  - OPT 理想页面置换算法
    - 在未来的一段时间内，每个页面被访问的顺序
  - FIFO 先进先出
    - 总是选择最先装入内存的页面调出，或者说把驻留在内存中时间最长的那一页调出
  - 第二次机会页面置换算法
  - CLOCK
  - LRU 最近最少使用
    - 总是选择距离现在最长时间内没有被访问过的页面先调出
缺页率：
- f=F/A（F为缺页次数，A为页面总访问次数）
- 影响其的因素
  - 分配给程序的物理页面数
  - 页面的大小
  - 程序编制方法
  - 页面调度算法
优点：不要求进程的程序段和数据段在内存中连续存放，有效解决了碎片问题，提高了内存利用率
缺点：存在页面空间的浪费，程序的最后一页往往有一部分得不到利用

七、文件系统

概述

文件 & 文件系统

文件
- 定义：一组带标识的、在逻辑上有完整意义的信息项的序列
- 读写指针：读指针用来记录文件当前的读取位置，写指针用来记录文件当前的写入位置
- 特点：存储在磁盘，可长期保存
文件系统
- 是操作系统中统一管理信息资源的一种软件。它管理文件的存储、检索、更新，提供更安全的共享和保护手段，并且方便用户使用
- 功能
  - 统一管理文件的存储空间，实施存储空间的分配与回收
  - 实现文件按名存取，以对用户透明的方式管理名字空间
  - 实现文件信息的共享，并提供文件的共享和保密措施
  - 向用户提供一个方便使用的接口
  - 系统维护及向用户提供有关信息
  - 保持文件系统的执行效率
  - 提供与I/O的统一接口

文件的存储介质及存取方式

外存储设备的特点
- 特点：容量大、断电后仍可保存信息
- 组成：驱动部分和存储介质部分
- 种类
  - 磁带：容量大，存取速度慢，适合顺序存储
  - 磁盘：容量大，成本低，适合随机存储
  - 光盘：是利用在激光的作用下特性发生变化的一些材料制成的非磁性记录介质
    - 特点：容量大、速度快、价格便宜
  - 闪存：电擦除，随机存取、可靠性高、寿命长
存取方式
- 顺序存取
- 随机存取

文件分类

按文件的用途分类
- 系统文件
- 库函数文件
- 用户文件
按文件的组织方式分类
- 普通文件
- 目录文件
- 特殊文件
UNIX类操作系统中文件的分类
- 普通文件
- 目录文件
- 特殊文件

文件的逻辑结构和物理结构

逻辑结构：从用户观点出发所观察到的文件组织形式
- 原则：易于操作、查找快捷、修改方便、空间紧凑
- 分类
  - 流式文件
  - 记录式文件
    - 定长记录文件和变长记录文件
物理结构
- 又称为文件的存储结构。是指系统将文件存储在外存上所形成的一种存储组织形式，是用户不能看见的
- 顺序结构：又称连续结构，它把逻辑上连续的文件信息依次存放在连续编号的物理块中
  - 优点
    - 存取速度快，一旦知道了文件在存储设备上的起始块号和文件长度，便能快速进行存取
    - 支持顺序存放和随机存取
  - 缺点
    - 文件不能动态增长
    - 要求为一个文件分配连续的存储空间
    - 不能灵活地删除和插入记录
    - 出现碎片
- 链接结构：将逻辑上连续的文件分散存储在若干个不连续的物理块中。每个物理块中都设有一个指针，指向其后续的物理块
  - 优点
    - 解决了碎片问题，提高了磁盘空间利用率
    - 文件可以动态扩充
  - 缺点
    - 存取速度慢，不适于随机存取
    - 可靠性差
- 索引结构：为每个文件分配一个索引块（表），把分配给该文件的所有盘块号，都记录在该索引块中
  - 多级索引
  - 优点
    - 文件动态增长
    - 不要求为一个文件分配连续的存储空间
    - 能灵活地删除和插入记录
    - 能顺序存取和随机存取
  - 缺点
    - 引起较多的寻道次数和寻道时间
    - 索引表本身增加了存储空间的开销

文件目录

文件控制块

文件控制块
- 为文件设置的用于描述和控制文件的数据结构文件管理程序可借助于文件控制块中的信息，对文件施以各种操作
- 内容
  - 基本信息类：文件名、文件物理位置、文件逻辑结构、文件的物理结构
  - 存取控制信息类：文件主的存取权限、核准用户的存取权限以及一般用户的存取权限
  - 使用信息类：文件的建立日期和时间、文件上一次修改的日期和时间、当前已打开该文件的进程数是否被其它进程锁住、文件在内存中是否已被修改但尚未拷贝到盘上等
文件目录
- 文件控制块的有序集合（文件与文件控制块一一对应）称为文件目录，一个文件控制块就是一个文件目录项

一级目录结构
- 优点：简单且能实现目录管理的基本功能——按名存取
- 缺点：查找速度慢、不允许重名
二级目录结构
- 优点：解决了文件的重名问题和文件共享问题，提高搜索速度，查找时间降低
- 缺点：不太适合大量用户和大量文件的大系统，增加了系统开销
多级目录
- 优点：层次结构清晰，便于管理和保护、有利于文件分类、解决重名问题、提高文件检索速度、能进行存取权限的控制
- 缺点：查找一个文件按路径名逐层检查，由于每个文件都放在外存，多次访盘影响速度
当前目录：当前正在使用的目录（也称工作目录或值班目录）
目录检索：用户访问文件时，需要进行目录检索这时用户给出文件名，系统按名寻找目录项
检索方法：全路径名（绝对路径名），相对路径

目录项
- 一个文件控制块做成一个定长记录，这个记录称为目录项
目录文件
- 多个文件的文件控制块集中在一起组成了文件的目录。文件目录以文件的形式保存，该文件称为目录文件

目录项分解法

目的
- 加快目录检索速度
分解
- 目录项分解成两部分：符号目录项（次部）和基本目录项（主部）
- 符号目录项：包含文件名和文件号
- 基本目录项：除文件名以外的FCB的其他全部信息
优点
- 减少磁盘的访问次数，提高文件目录检索速度

文件存储空间管理

磁盘空间管理
- 基本思想：对于磁盘空间的分配和回收的方法
磁盘空间的分配与回收算法
- 位示图
- 空闲块表
- 空闲块链

实现文件系统的表目

系统打开文件表
- 专门用来保存已打开文件的文件控制块，通常放在内存
- 共享计数：记录有多少个进程同时打开该文件
- 修改标志：指文件控制块或结点的内容是否被修改过，如果修改过，则关闭文件时要将文件控制块写回磁盘
用户打开文件表
- 每个用户都有一个用户打开文件表，其位置记录在PCB中

文件及目录的操作

文件及目录的性能

磁盘高速缓存
- 基本思想：系统在内存中保存一些磁盘块，这些磁盘块在逻辑上属于磁盘，内存的这一区域被称为块高速缓存
- 文件系统一致性问题
  - 如果在修改过的磁盘块写回磁盘之前，系统出现故障，则文件系统有可能会处于不一致状态。特别是一些未被写会的块是结点、目录块或者包含空闲表的磁盘块时，问题尤为严重
- 记录的成组
  - 把若干个逻辑记录合成一组存储到一个物理块的工作，称为记录的成组。每块中的逻辑记录个数称为块因子
  - 实现原理：信息交换以块为单位，故成组需要使用内存缓冲区来完成。缓冲区的长度=记录的长度*块因子
  - 优点：提高了磁盘利用率，减少了启动磁盘的次数，提高系统工作效率
  - 要考虑的因素：定长记录和不定长记录
- RAID 独立余磁盘阵列
  - 是一种把多块独立的硬盘（物理硬盘）按不同的方式组合起来形成一个硬盘组（逻辑硬盘），从而提供比单个硬盘更高的存储性能和提供数据备份技术

文件共享、保护和保密

文件共享
- 是指一个文件可以充许多个用户共同使用
- 共享时间段（分类）
  - 文件可以同时使用文件
  - 不充许同时使用
- 在文件共享具体方式上，有三种共享方式
  - 文件被多个用户使用，由存取权限控制
  - 文件被多个用户使用，但分别用自己的读写指针
  - 文件被多个程序使用，但共享读写指针
- 实现方法（连接法）
  - 充许目录项连接到任一表示文件目录的结点上
  - 只允许连接到表示普通文件的节点上
文件保护
- 影响文件安全性的主要因素（人为、系统、自然）
文件保密的目的
- 是防止不经文件拥有者授权而窃取文件
常用的文件保密措施
- 隐蔽文件目录
- 设置口令
- 使用密码
- 病毒防范

八、I/O设备管理

概述

任务
- 解决I/O设备和CPU速度不匹配的矛盾
- 提供简单易用的接口，实现对设备的统一管理
- 保证设备的安全性
分类
- 使用特性：输入设备、输出设备、交互式设备、存储设备
- 组织方式：字符设备和块设备
- 可共享性：独占设备、共享设备、虚拟设备
I/O设备管理对象
- IO设备，是对资源的管理，提供标准接口供用户用这些设备
文件管理对象
- 设备里面存储的数据和信息，提供一整套对这些资源的管理规则，并且以文件及其配套的概念来具体实施UNIX系统中
- 所有设备都当做文件对象来管理

I/O硬件 & I/O软件

硬件
- I/O硬件由物理设备和电子部件两部分组成
- 物理设备是达成I/O硬件功能的基础，对操作系统而言更注重的是其电子部件的控制方式
软件
- I/O软件组成一系列层次，较低的层次处理与硬件有关的细节，并将硬件的特征与较高的层隔离，较高的层则向用户提供一个友好的、清晰而规整的I/O接口
- 四层：中断处理程序、设备驱动程序、设备独立层软件、用户层软件
设备独立性
- 除了直接与设备打交道的底层软件之外，其他部分的软件并不依赖于硬件。即应用程序中所使用的设备不局限于使用某个具体的物理设备，也称为设备无关性
- 优点：当I/O设备更新时，没有必要重新编写全部I/O软件。实际应用只要安装了驱动程序，可以方便地安装好新的I/O设备
- 设备保护：防止未授权用户对设备的非法使用
控制方式：取决于I/O设备硬件与处理器和内存的连接方式以及设备的驱动程序
- 程序控制方式（PIO）
  - 由用户进程直接控制处理器或内存和外围设备之间进行信息传送的方式（轮询）
  - 优点：处理器和外设的操作能通过状态信息得到同步，而且硬件结构比较简单
  - 缺点：处理器效率较低，传输完全在处理器控制下完成，对外部出现的异常事件无实时响应能力
- 中断控制方式
  - 过程
    - 处理器通过数据总线发出命令，启动外设工作，当前进程阻塞，调度程序调度其他进程
    - 外设数据准备好，置位中断请求触发器
    - 若此时接口中断屏蔽器状态为非屏蔽状态，则接口向处理器发送中断请求（IR）
    - 处理器接收中断请求，且中断为允许中断状态，则中断判优电路工作
    - 中断判优电路对优先级最高的中断请求给予响应（INTR），处理器中断正在执行的其他进程，转而执行中断服务程序
  - 优点
    - 处理器与外设并行工作，提高计算机的利用率
    - 具有实时响应能力
    - 可及时处理异常情况，提高计算机的可靠性
- DMA控制方式（直接访问内存）
  - 是一种完全由硬件执行I/O数据交换的工作方式，数据交换不经过处理器，而直接在内存和I/O设备之间进行
  - 优点
    - 操作均由硬件完成，传输速度快；处理器只在初始化和结束时参与，对数据传输基本不干预，可以减少大批量数据传送时处理器的开销；处理器与外设并行工作，效率高
- 通道控制方式
  - 通道是一个特殊功能的处理器，它有自己的指令和程序，可以实现对外围设备的统一管理和外围设备与内存之间的数据传送
  - 优点
    - 与DMA方式相比，通道方式增加了处理器与通道操作的并行处理能力；增加了通道之间或同一通道内各设备的并行操作能力；为用户提供了灵活增加外设的可能性
  - 通道的分类：选择通道、数组多路通道、字节多路通道
  - 通道的功能
    - 接收处理器的指令，按指令要求与指定的外围设备进行通信
    - 从内存读取属于该通道的指令并执行通道程序，向设备控制器和设备发送各种命令
    - 组织外围设备和内存之间进行数据传送，并根据需要提供数据缓存的空间，以及提供数据存入内存的地址和传送的数据量
    - 从外围设备得到设备的状态信息，形成并保存通道本身的状态信息，根据要求将这些状态信息送到内存的指定单元，供处理器使用
    - 将外围设备的中断请求和通道本身的中断请求按序及时报告处理器

设备分配与回收

数据结构：系统设备表、设备控制表、控制器控制表通道控制表
分配原则
- 要充分发挥设备的使用率，尽可能让设备忙碌，但又要避免由于不合理的分配方法造成的死锁
- 要做到把用户程序和具体物理设备隔离开来，即用户面对的是逻辑设备，而分配程序将在系统把逻辑设备转换成物理设备之后，再根据要求的物理设备号进行分配
- 设备分配方式：静态分配和动态分配
  - 静态分配效率低，动态分配可能死锁
分配策略
- 主要考虑的因素：IyO设备的固有属性、分配算法
- 设备分配的安全性以及设备独立性
- 设备固有属性：独占设备、共享设备、虚拟设备分配算法：先来先服务、高优先级优先

独占设备的分配

设备的绝对号与相对号
- 绝对号：系统为每一台设备确定的一个编号，用来区分和识别各种不同类型的外部设备，以便进行管理
- 相对号：由用户在程序中定义的设备编号称为设备的相对号
- 二者的对应关系：规定用户使用设备类相对号来提出使用设备的要求，而系统在为用户分配具体设备的同时，建立设备的绝对号与用户使用的设备类相号的对应关系
设备的指定方式
- 两种方式：绝对号，设备类相对号
- 使用绝对号的缺点，当指定的设备出现故障，即使还有其他同类设备，作业的请求仍然得不到满足，必须等待
- 使用设备类相对号的好处：实现了设备的独立性，即用户程序使用的逻辑设备与程序实际执行时使用的物理设备无关
  - 111

共享设备的分配

共享设备可被多个进程共享，但在每个IO传输的单位时间内只由一个进程所占用，以块为传输单位，可以交叉进行，没有明显的申请和释放活动
使用方法：
- 申请设备，如设备被占用，则进入设备等待队列，否则分配设备
- 启动设备。I/O传输
- 释放设备。当设备结束，发出中断信号，系统唤醒一个等待设备的进程

磁盘调度策略

信息传输时间
- 信息在磁盘上按柱面存储，同一柱面的各磁道存储满，再放到下一个柱面
- 启动磁盘执行输入输出操作时，要把移动臂移到指定的柱面，再等待指定扇区旋转到磁头位置下，然后让指定的磁头进行读写
位置计算
- 块号计算：b=k+s*（j+i*t）
  - t：每个柱面上的磁道数
  - s：每个盘面上的扇区数
  - i：柱面
  - j：磁头
  - k: 扇区
移臂调度：
- 根据访问者指定的柱面位置来决定执行次序的调度
- 目的：尽可能减少操作中的寻找时间
- 常用算法
  - 先来先服务调度算法
    - 根据进程访问磁盘的先后次序进行调度
    - 优点：公平和简单
    - 缺点：效率低
  - 最短寻找时间
    - 选择这样的进程，其要求访问的柱面号，与当前磁头所在的柱面距离最近，以使每次的寻找时间最短
    - 优点：平均每次磁头移动距离明显低于FCFS的距离，固有较好的寻道性能，过去曾一度被广泛使用
  - 优先调度算法
  - 电梯调度算法
    - 从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱面访问，如果沿臂的移动方向无请求，就改变臂的移动方向再选择
  - 单向扫描调度算法
    - 不考虑访问者等待的先后次序，总是从0号柱面开始向里扫描，按照各自所需要访问的柱面位置的次序去选择访问者。当移臂到达最后一个柱面后，立即返回0号柱面，再次进行扫描
旋转调度：
- 在移动臂定位后，若有若干个访问者等待访问该柱面的情况下，若从减少输入输出操作总时间为目标出发，应该优先选择延退时间最短的访问者去执行
信息的优化分布
- 记录在磁道上的排列方式也会影响磁盘的输入输出操作时间

缓冲技术

缓冲
- 缓和CPU与I/O设备间速度不匹配的矛盾
- 减少外部中断次数和处理器进行中断处理所花费的时间
- 解决DMA或通道出现的瓶颈问题
缓冲分类：单缓冲、双缓冲、多缓冲、缓冲池

虚拟设备技术

虚拟设备技术，又称为SPOOLing技术，其含义是同时外部设备联机操作，也称假脱机技术
三部分组成：输入程序模块、输出程序模块、作业调度
工作原理
- 输入程序模块，在作业执行前就利用慢速设备将作业预先输入到后援存储器（女井），称为预输入，如磁盘、磁鼓成为输入
- 作业进入内存后，数据直接从输入井取出 -作业输出数据时，把数据写入输出井，称为缓输出。待作业全部完成后，再由外部设备输出全部数据

02326 操作系统 ✒️ ​

一、概论 ​

计算机系统概念 ​

操作系统的定义 ​

操作系统的特征 ​

研究操作系统的观点 ​

操作系统的功能 ​

进程管理 ​

存储管理 ​

文件管理 ​

设备管理 ​

用户接口 ​

操作系统的体系结构 ​

Windows ​

UNIX ​

Linux ​

Android ​

操作系统的发展 ​

操作系统分类 ​

批处理操作系统 ​

分时操作系统 ​

实时操作系统 ​

嵌入式操作系统 ​

其他操作系统 ​

操作系统设计 ​

二、操作系统的运行环境 ​

处理器 ​

构成 ​

寄存器 ​

指令 ​

处理器的工作状态 ​

程序状态字 ​

计算机系统硬件部件 ​

存储系统 ​

I/O部件 ​

时钟部件 ​

中断机制 ​

中断&异常 ​

中断系统 ​

中断优先级、中断屏蔽与中断嵌套 ​

系统调用 ​

概述 ​

系统调用的处理过程 ​

三、进程&线程 ​

多道程序设计 ​

程序的顺序执行 ​

程序并发执行 ​

多道程序设计 ​

进程 ​

进程的定义 ​

进程的状态与转换 ​

进程控制块 ​

进程控制 ​

线程 ​

概述 ​

进程 & 线程 ​

线程实现机制 ​

进程调度 ​

概述 ​

调度算法设计原则 ​

进程调度算法 ​

系统内核 ​

四、进程同步 & 互斥 ​

进程间相互作用 ​

进程同步与互斥 ​

信号量及P、V操作 ​

信号量 ​

信号量与P、V操作的物理含义 ​

用P、V操作实现进程之间的互斥 ​

用P、V操作实现进程之间的同步 ​

PV操作总结 ​

经典的进程同步问题 ​

简单生产者--消费者问题 ​

多个生产者--消费者问题 ​

读者--写者问题 ​

管程 ​

进程通信 ​

五、死锁 ​

死锁的产生 ​

死锁预防 ​

02326 操作系统 ✒️

一、概论

计算机系统概念

操作系统的定义

操作系统的特征

研究操作系统的观点

操作系统的功能

进程管理

存储管理

文件管理

设备管理

用户接口

操作系统的体系结构

Windows

UNIX

Linux

Android

操作系统的发展

操作系统分类

批处理操作系统

分时操作系统

实时操作系统

嵌入式操作系统

其他操作系统

操作系统设计

二、操作系统的运行环境

处理器

构成

寄存器

指令

处理器的工作状态

程序状态字

计算机系统硬件部件

存储系统

I/O部件

时钟部件

中断机制

中断&异常

中断系统

中断优先级、中断屏蔽与中断嵌套

系统调用

概述

系统调用的处理过程

三、进程&线程

多道程序设计

程序的顺序执行

程序并发执行

多道程序设计

进程

进程的定义

进程的状态与转换

进程控制块

进程控制

线程

概述

进程 & 线程

线程实现机制

进程调度

概述

调度算法设计原则

进程调度算法

系统内核

四、进程同步 & 互斥

进程间相互作用

进程同步与互斥

信号量及P、V操作

信号量

信号量与P、V操作的物理含义

用P、V操作实现进程之间的互斥

用P、V操作实现进程之间的同步

PV操作总结

经典的进程同步问题

简单生产者--消费者问题

多个生产者--消费者问题

读者--写者问题

管程

进程通信

五、死锁

死锁的产生

死锁预防