What is an operating system?
Layer between application and hardware
Primitive Operating Systems
- Just a library of standard services
Multitasking
想法：当一个进程阻塞（等待磁盘、网络、用户输入等）运行另一个进程时，可以同时运行多个进程
问题：行为不良的进程能做什么？
操作系统提供了抢占机制来解决这些问题，使CPU远离循环进程；保护进程彼此的内存
Multi-user OSes
Protection
Typical OS structure
System calls
Example
UNIX file system calls
Error returns
Operations on file descriptors
File descriptor numbers
Protection example: CPU preemption
Address translation
More memory protection
Threads & Processes
Processes
A processis an instance of a program running
Why processes?
- Simplicity of programming
- Speed: Higher throughput, lower latency
Speed
Multiple processes can increase CPU utilization
Multiple processes can reduce latency
A process’s view of the world
How can processes interact in real time?
- By passing messages through the kernel
- By sharing a region of physical memory
- Through asynchronous signals or alerts
(UNIX-centric) User view of processes
Creating processes
Deleting processes
Running programs
Manipulating file descriptors
Pipes
Kernel view of processes
Implementing processes
Threads
Thread implementation details
Concurrency & Synchronization（并发与同步）
Scheduling（调度）
Virtual Memory
I/O
Disks, File systems
Protection & Security
Virtual machines
操作系统
1 绪论
1.1 操作系统概述
1.1.1 计算机系统构成的认识
计算机系统 = 硬件系统 + 软件系统。
硬件资源：中央处理器、存储器、输入输出设备（通道和控制器）。
软件资源：文件（系统软件 应用软件 均以文件方式存放）。
微型机的硬件组织：总线结构。
大中小型计算机的硬件结构：非总线结构。
1.1.2 命令、任务、进程、作业
命令：从命令窗口发给系统的指示。
任务：系统中的应用程序做的事情。
进程：程序的一次执行过程。
作业：用户提交给计算机进行加工处理的一个完整的任务。
1.1.3 操作系统的定义和地位
操作系统：管理系统资源并向用户提供服务接口的程序集合，是最基本的系统软件。
操作系统的目标：方便用户、提高资源利用率、改善系统性能。
另一种定义：计算机系统中的一个系统软件，是一些程序模块的集合——它管理和控制计算机系统的软硬件资源，合理的组织计算机的工作流程，以便有效利用这些资源为用户提供一个功能强大、使用方便和可扩展的工作环境，在计算机和其用户之间起到接口作用。
简要定义：用于控制和管理系统资源，方便用户使用计算机的程序的集合。
1.1.4 研究操作系统的四种观点
资源管理的观点（静态观点）。
操作系统是由对系统资源进行管理的四个内核模块（进程管理、存储管理、设备管理、文件管理）和向用户提供服务接口的一个外壳模块（作业管理或其命令处理）组成。
资源管理包括三个方面：资源使用情况记录、资源的分配策略、资源的分配与回收等。
用户（界面）观点。
操作系统是用户和计算机之间的接口。用户不必关心操作系统的内部结构，只关心如何利用其功能使用计算机，因此，提供什么样的界面成为关键问题。
命令级的接口：联机命令接口（交互式用户接口）、脱机命令接口（批处理用户接口）。
程序级的接口（系统调用）：程序通过系统调用来调用操作系统的功能，这种调用由特殊的机器指令实现，执行时将引起中断，称为软中断。汇编语言级别上提供全部的系统调用，其它语言以自己的形式全部或部分的提供。
进程观点（动态观点）。
操作系统是由若干个可以同时独立运行的进程和一个对它们进行管理、协调的系统核心组成。
进程：一个具有独立功能的程序对某个数据集在处理机上的运行过程。
进程的构成：程序、数据、进程控制块。
进程控制块：简称PCB。是包含进程描述信息和控制信息的数据结构，是进程动态特性的集中反映，是进程存在的唯一标志。
进程构成的物理表示：程序和数据混合、程序和数据分离、基本共享模式。
▲ 进程基本状态转换图。
分层观点（虚拟机观点）。
通过一层层软件扩充，操作系统把裸机扩展为功能更强大使用更方便的虚拟机。
1.2 操作系统的发展历程
1.2.1 操作系统的形成
手工操作阶段、批处理阶段、执行系统阶段。
1.2.2 手工操作阶段
操作过程：用户将程序和数据纸带装上输入机，启动输入机，通过控制开关启动程序运行。
特点：用户直接与计算机硬件打交道，靠控制台面板来控制主机和外设；用户独占全机资源；用户既是程序员又是操作员 。
主要缺点：慢速设备输入输出是联机的，浪费CPU时间；作业之间的转接有由手工操作，浪费时间。
1.2.3 早期批处理阶段
作业处理步骤：操作员把若干纸带合成一批，通过输入设备将它们存入磁带；监督程序读一个系统资源能满足其要求的作业进入内存；将程序编译；装配成可执行程序；执行程序 ；善后处理程序输出计算结果；处理下一个作业。
特点：配备专门的操作员；进行批处理，每一批作业由专门编制的监督程序自动一次处理；多个步骤之间的转接自动完成不需要人工干预。
联机批处理：CPU直接控制慢速输入输出设备。
脱机批处理：慢速输入输出设备由外围处理机控制。
1.2.4 多道批处理系统
多道批处理系统的特征
多道：内存中同时存放多个作业或者程序。
宏观上并行 ：内存中的多个程序都处于运行状态。
微观上串行：各道程序轮流使用CPU，交替执行。
在当前运行的程序需作I/O处理时，CPU转而执行另一个程序。
多道程序系统必备的硬件基础是中断技术。
1.2.5 分时系统操作
批处理系统的显著缺点：没有交互能力，用户无法干预自己作业的运行，使用起来不方便；用户作业可能需要等待很长时间才能得到运行。
分时系统的主要特征：
多路性/同时性：宏观上同时有多个用户在运行。
交互性：在终端上编辑、运行程序，或其它操作。
独占性：每个用户一个终端，独立操作，互不干扰。
1.2.6 实时操作系统
能对随机发生的外部事件作出及时响应和处理。
对响应事件和可靠性有很高要求和严格限度的系统。
1.2.7 通用操作系统
是在实时系统之后，为使系统应用范围更广泛，处理能力更强，有些系统兼有实时、分时和批处理的两种，或三种处理能力，从而形成通用操作系统。
当代同时具备两种以上功能的系统有很多，例如：
UNIX操作系统：SUN公司的Solaris。
Microsoft公司的Windows系列。
Linux操作系统：Redhat，红旗Linux等。
1.4 操作系统的特性
并发性：存在许多同时或并行的活动。
CPU与外设之间。
内存中的多道程序在宏观上并行。
外设之间。
共享性：并发的程序共同使用系统的软硬件资源。
虚拟性：把一个物理上的实体变成了若干个逻辑上的对应物。
不确定性：系统中同时存在的多个程序的执行次序及每个程序的执行所花费的时间一般是不可再现的。
1.5 操作系统的性能
可靠性：平均无故障时间长 MTBF。
可修复性：平均故障修复时间段 MTRF。
可用性：正常使用率高 A=MTBF/(MTBF+MTRF)A=MTBF/(MTBF+MTRF)。
效率
吞吐量：单位时间内所处理的平均类型作业数量。
响应时间：从给定系统输入到开始输出这段时间间隔平均作业周转时间。
系统资源利用率。
可维护性：排除故障、改进和扩充功能。
方便性（友好的用户界面）：操作使用简单易学，给出尽可能多的提示信息。
2 用户界面和作业管理
2.1 作业的基本概念
2.1.1 作业的定义
作业：用户要求计算机完成的一次业务处理的全部工作。
作业步：作业处理的一个步骤，通常是执行一条操作系统的简单命令。
”编译——链接——执行“是一个典型的作业。
早期DOS系统下一个扩展名为bat的批处理文件的内容，相当于一个作业说明书。
2.1.2 作业的组织
作业的组成：一批程序、一批数据、一个作业说明书。
作业说明书的核心内容是作业步的操作顺序（类似于.bat文件）。
2.1.3 作业的状态及其转换
进入状态：从作业输入请求到进入输入井并建立作业控制块JCB。
后备状态：从建立作业控制块到被作业调度选中。
运行状态：从被作业调度选中进入内存到作业运行结束。
完成状态：从作业运行结束到作业被撤销。
2.2 作业的建立
作业的建立包括作业的输入和作业控制块的建立。
作业的输入：作业的程序、数据和作业说明书从输入设备输入到外存。
2.2.1 作业的输入方式
联机输入方式：由慢速输入设备输入作业到主机外设 ，该设备由主机控制。
脱机输入方式：在低档的个人计算机上把作业输入到磁盘或磁带上，然后把盘或带放在主机上输入到主机外存上。
直接耦合输入方式：在外围处理机上把作业直接输入到主机直接相连的外存上。
Spooling输入方式：由一个进程通过执行Spooling的预输入程序控制通道来模拟外围处理机负责作业输入工作。
由通道控制外设的输入输出，很大程度上达到了“脱机”的效果，但通道受主机控制，这与脱机方式下的外围处理机独立工作不同，所以Spooling技术又称为假脱机输入输出技术。
网络输入方式：一台主机上输入的信息通过网络传输到另一台主机上。
2.2.2 作业控制块的建立
作业控制块：JCB（Job Control Block）。
JCB是内存中的一个数据结构，与作业一一对应，包含了系统对作业进行管理所必须的信息。
2.3 作业的建立
JCB通常包含下列信息：
用户名：作业所属的用户作业名称。
作业建立时间：为作业调度算法提供参数。
作业估计运行时间：为作业调度算法提供参数同时避免作业死循环时无限占用CPU。
优先数：表示作业的紧迫程度，它可以由用户给出，也可以由系统根据某种原则设定。
作业说明书文件：作业说明书是控制作业执行的依据。
程序语言类型：为了更有效地调用有关子系统。
作业状态：进入、后备、运行、完成。
资源要求：用户可在作业说明书中提出资源要求，也可由作业执行时在程序中提出。
作业类型：I/O型、CPU型、均衡型。
2.4 Spooling技术
Spooling通常包含下列程序：预输入、取输入、存输出、缓输出、井管理。
预输入：预先把作业（数据）从慢速输入设备传输到输入井。
取输入：作业调度时或运行时从输入井中取作业（数据）。
存输出：作业运行中把向慢速输出设备的输出存入输出井。
缓输出：作业终止后把作业在输出井的输出结果集中输出。
虚拟设备：利用某种技术（例如SPOOLing 技术）把一台独享的物理设备变换成若干台逻辑上的对应物，称这些对应物为虚拟设备。
被虚拟化的设备：经过SPOOLing技术处理的设备。
2.5 作业调度
作业调度也叫高级调度，其任务是选择后备作业将其调入内存。
作业调度的关键是选择适当的算法。
2.5.1 工作过程
按调度算法从后备作业队列中选择一个作业。
为选中作业分配必要的资源，创建相应的作业控制过程。
内存：用于装载作业说明书。
外设（静态分配）：作业说明书中申请的独享设备。
将该作业的状态从后备改为运行，相应作业控制进程就绪。
2.5.2 调度算法的选择
选择的调度算法要与系统的整个目标一致。
注意系统资源的均衡使用（I/O型、CPU型作业搭配）。
应保证提交的作业在规定的截止时间完成。
2.5.3 单道批处理系统的作业调度算法
先来先服务 FCFS。
最短作业优先 SJF。
优先级高者优先。
相应比高者优先 HRN。
响应比=作业相应时间/作业估计运行时间=（作业后备等待时间+作业估计运行时间）/作业估计运行时间响应比=作业相应时间/作业估计运行时间=（作业后备等待时间+作业估计运行时间）/作业估计运行时间
2.6 作业控制
作业控制就是控制作业的运行，由作业控制程序完成。
作业控制程序——通过解释执行作业说明书来控制作业的运转过程的程序。又可称为作业控制语言解释程序。
作业说明书——用 JCL 语言编写的程序，是比一般用户程序高一级的程序。
2.7 作业终止和作业撤销
作业终止：当作业控制程序解释执行完作业说明书后，调用作业终止程序，该程序回收作业调度时分给作业的资源，并把其状态改为完成。
作业撤销：当作业的所有输出结果从输出井向输出设备输出完成后，作业撤销程序被调用，它通过释放作业控制块等来撤销作业。
2.8 分时作业的管理
可以说，分时系统中作业的概念已很淡化了，对分时作业的管理也很简化。分时作业JCB与分时进程的PCB表合而为一了，对分时作业的管理已简化为对终端进程的管理，对分时作业的控制是靠命令语言解释程序实施的。
2.9 操作系统与用户之间的接口
2.9.1 命令级接口
联机命令接口（交互式用户接口）
联机命令接口由联机命令（终端命令）、终端字符处理程序和命令处理程序组成。
用户键入的终端命令由命令处理程序解释执行，其相应的程序代码，可以包含在命令处理程序，也可以放在一个可执行文件。
按照终端命令对应的程序代码的所属分类：内部命令、外部命令、批处理命令。
按命令的功能分类：系统访问命令、文件管理命令、编辑编译链接和执行命令、调试命令、其它。
DOS系统中的命令的优先顺序为内部命令、外部命令、批处理命令。
脱机命令接口（批处理用户接口）
操作系统的用户看到的脱机命令接口就是JCL。
2.9.2 程序级接口（系统调用）
在程序级上调用操作系统功能。
系统调用：与文件有关的系统调用、与I/O设备有关的系统调用、与进程有关的系统调用、其它系统调用。
3 进程管理
3.1 顺序程序和并发程序
顺序程序的特性：
顺序性：每一个操作都在前一个操作执行完后才能开始。处理机的操作是严格按照程序所规定的次序进行的。
封闭性：程序执行得到的最终结果由给定的初始条件决定，不受外界因素的影响。
可再现性：程序执行得到的最终结果与执行速度无关。只要输入的初始条件相同，则无论何时重复执行该程序都会得到相同的结果。
并发程序的特性：
非可再现性：并发程序的执行结果与它们的相对速度有关。
共享性：共享同一段程序；共享系统资源。
通信性：并发程序之间相互依赖和制约。
3.2 进程及其状态变化
3.2.1 进程的定义及其特征
进程：一个具有独立功能的程序对某个数据集在处理机上的一次运行过程。
进程具有两个基本特征：动态性、并发性。
3.3 进程构成及进程控制块
3.3.1 进程的构成
进程构成：程序、数据、进程控制块。
进程控制块（PCB）：是包含进程的描述信息和控制信息的数据结构，是进程动态特性的集中反映，是进程存在的唯一标志。
每一个进程都有一个进程控制块，进程与进程控制块一一对应。
所有进程的控制块构成了系统的进程控制块表。
进程控制表可以定义为一个结构数组，系统初始时均为空闲。
每当创建一个进程，操作系统就为此进程分配一个空闲的进程控制块并填写相应信息。
每当撤销一个进程，操作系统就释放此进程占用的进程控制块并把其置为空闲。
3.4 进程调度
3.4.1 调度的基本概念
高级调度（作业调度）：从后备作业中选取若干个作业到内存投入运行。
中级调度（交换调度）：将进程的程序和数据在内存和外存交换区之间的调入调出。
低级调度（进程调度、线程调度）：按照某种策略和方法选取一个处于就绪状态的进程或线程占用处理机。
3.4.2 进程调度算法
先进先出（FIFO）调度算法。
最高优先权（FPF）调度算法。
静态优先级算法：进程的优先级在被创建时确定，在整个运行期间不再改变。
动态优先级算法：基于某种原则，使进程的优先级随着时间而改变。
时间片轮转算法。
多级队列算法。
3.5 进程互斥
系统中本来没有逻辑关系的多个进程因为竞争使用资源而产生的间接制约关系。
临界资源：只允许进程依次地（互斥地）使用的资源。
临界区：只允许进程依次地（互斥地）进入的程序段，其中含有对共享的变量、表格、队列等临界资源的访问操作。
同类临界区：含有对同一临界资源进行访问操作的不同程序段。
3.5.1 实现临界区互斥的几种方法
开关中断法：关中断、临界区、开中断。
锁操作法 ：Lock w、临界区、Unlock w。
PV操作法：P(m)、临界区、V (m)。
3.5.2 PV操作及其原理
3.7 死锁及其对策
3.7.1 死锁及其产生条件
死锁：若干进程循环等待对方所占资源，并且无休止地等待下去。
产生死锁的四个必要条件：
互斥条件：即每一个资源每次只能分配给一个进程。
非剥夺式分配：即只能由获得资源进程自己释放所占用的资源。
部分分配：即进程每次只申请其最大资源需求量的一部分。
循环等待：发生死锁时，必然存在一个进程—资源的循环链。
3.7.2 死锁的对策
死锁的预防：系统设计时的对策。
资源的先释放再分配法（破坏第二个必要条件）。
资源的静态分配法（破坏第三个必要条件）。
资源的顺序使用法（破坏第四个必要条件）。
死锁的避免：系统运行过程中避免死锁的发生。
每次系统处理进程申请资源的请求时，都根据一定的算法（死锁避免算法）判断是否许可这次申请，使得在以后一段时间内不会因本次资源分配而产生死锁。
死锁的检测与恢复：定期检测有无死锁发生，如发现死锁则恢复之。
银行家算法：
银行家拥有一笔周转资金。
客户要求分期贷款，如果客户能够得到各期贷款，就一定能够归还贷款，否则就一定不能归还贷款。
银行家应谨慎的贷款，防止出现坏帐。
用银行家算法避免死锁
操作系统（银行家）。
操作系统管理的资源(周转资金)。
进程（要求贷款的客户）
3.7.3 死锁的对策
死锁的检测与恢复
系统不对资源的分配和使用进行限制，允许死锁的发生（可能性很小），系统定期检测有无死锁的发生，若有则恢复之。
死锁的几种解除方法
终止所有死锁的进程。
依次终止死锁的进程，直至死锁不存在。
依次强迫释放死锁的进程所占用的资源，直至死锁不存在。