操作系统

part one 操作系统引论

什么是操作系统？

操作系统是位于硬件层之上，其他软件层之下的一个系统软件，是管理和控制计算机的软硬件资源，合理组织计算机的工作流程，方便用户使用计算机系统的程序集合。

操作系统的历史

1. 穿孔卡片（无操作系统阶段，手工阶段）【纸带机】
2. 简单批处理系统（操作系统产生阶段）【磁带机】
3. 多道批处理系统（利用率，吞吐量，宏观并行，微观交替执行）
4. 分时系统（适合软件开发）
5. 实时系统（实时控制，实时信息处理）
   批处理系统，分时系统和实时操作系统构成了现代操作系统的基本类型。

多道批处理系统的特征？

1. 用户脱机使用计算机
2. 作业成批处理
3. 多道程序并行
   缺点是无交互性。

操作系统的功能

1. 进程管理
2. 内存管理
3. 信息管理

操作系统的基本特征

1. 并发性
2. 共享性
3. 虚拟性
4. 异步性

什么是并行性、并发性？

并行性：两个或多个事件在同一时刻发生

并发性：两个或多个事件在同一时间间隔发生

part two 进程管理

什么是进程？进程的五个特性 进程三要素

进程：一个具有独立功能的程序在一个数据集上的一次动态执行过程。

特性：

1. 动态性
2. 并发性
3. 独立性
4. 异步性
5. 结构性

进程三要素：进程 = 程序 + 数据 + PCB

进程和程序的区别？

1. 进程是一个动态的概念，程序是一个静态的概念
2. 进程是一个暂时性的概念，程序是一个永久性的概念
3. 进程具有数据结构-PCB
4. 进程和程序没有一一对应的关系。

进程的三个基本状态的转换？

进程的组成？

进程由程序、数据集合、进程控制块组成。

PCB是进程存在的唯一标志，且与进程一一对应。

什么是原语？

原语一般由若干条指令所组成，是用来完成某个特定功能，在执行过程中不可被分割的程序段，是原子操作，即一个操作中的所有动作，要么全做，要么全不做。 原语一旦执行，就要连续执行完，中间不允许中断。 原子操作在管态下执行，常驻内存，通过关中断来实现。

什么是临界资源？

系统中一次只允许一个进程使用的一类资源，称为临界资源或互斥资源。

什么是进程的互斥？

对于异步环境下并发执行的进程，某些进程要竞争某一临界资源，而这资源最多允许一个进程使用，其他要使用该资源的进程必须等待，直到该占用资源被释放为止，这就产生间接制约关系。把因间接制约而导致的交替执行的过程称为进程的互斥。

每个进程访问临界资源的那段代码称为临界区。

为禁止两个资源同时进入临界区，同步机制的规则因遵循什么？

空闲让进（多中选一），忙则等待，有限等待，让权等待。

什么是信号量？

整性信号量S表示某类临界资源实体，是一个数据结构，其值仅能由P、V操作来改变。S >= 0表示S个某类可用某类临界资源；S <= 0,则|S|表示S阻塞队列中等待资源的进程个数。

信号量的使用规则？

1. S必需置一次初值，且只能置一次初值。
2. 初值不能为负。
3. 只能对其执行P、V操作。
4. P、V操作必须成对操作。
5. 同步P必须在互斥P之前，V无所谓。

什么是同步？

多个相互合作的并发进程在执行次序上的协调，在一些关键点上可能需要相互等待或相互交换信息，以达到有效的资源共享和相互合作，这种相互制约的关系称为进程同步。

什么是进程通信？

进程之间的信息交换叫做进程通信。

什么是死锁？死锁产生的原因？

多道程序设计系统中，两个或两个以上并发执行的进程由于竞争资源而造成的一种互相等待的现象，如无外力协助，这些进程将永远分配不到必须的资源而继续向前推进，称这种现象为死锁。

死锁产生的原因即与资源分配的策略有关，又与进程执行效率有关。

产生死锁的必要条件

1. 互斥条件
2. 不剥夺条件
3. 请求和保持条件
4. 环路等待条件

死锁的预防策略

1. 破环互斥性条件
2. 分配策略
3. 资源可剥夺策略
4. 破环环路等待条件

系统的两种状态

系统由以下两种状态
安全状态：指系统能够按照某种顺序如<P1，P2，...，Pn>（称<P1，P2，...，Pn>为安全序列）为每个进程分配所需的资源，直至最大需求，使得每个进程都能顺利完成。
非安全状态：即在某个时刻系统中不存在一个安全序列，则称系统处于不安全状态或非安全状态。

非安全状态可能出现死锁，死锁是非安全状态的子集。

进程调度的层次

作业从提交到运行结束，要经历三级调度。

1. 作业调度（分钟，小时或天）
2. 进程调度（毫秒级）
3. 中级调度

分时系统和时时系统一般不存在作业调度，批处理系统同时存在作业调度和进程调度。

周转时间 = 完成时间 - 就绪时间 = 等待时间 + 运行时间

加权周转时间 = 周转时间/运行时间

进程调度的算法

1. 先来先服务（简单，不公平，无优先级）
2. 短作业优先（时间短，”饿死”，一般用于作业调度）
3. 轮转法（公平，无优先级，效率低，时间不易确定）
4. 优先级算法（有优先级，“饿死”）
5. 多级反馈队列算法（复杂，性能好，应用广）

什么是线程？

线程是进程的一个实体，是被系统独立调度和分派的基本单位。

part three 存储管理

地址重定位（地址映射）

把用户进程装入内存时，对有关指令的地址部分的修改定义为从逻辑地址到物理地址的过程。

什么是交换技术

即把一个进程完整调入内存，在该进程运行一段时间后，再把它存回磁盘。空闲进程只要存储磁盘上，所以当它们不运行时就不会占用内存（尽管它们的一些进程会周期性地被唤醒以完成相关工作，然后又进入睡眠状态）。

什么是碎片

内存中若干不连续的，很小的空闲分区，小到以至于绝大多数程序都无法利用。

空闲内存管理

1. 使用位图的存储管理（固定分区，支持多道，无虚拟存储，初装有碎片）
2. 使用链表的存储管理（动态分区，没有彻底解决碎片问题）

什么是页框

虚拟地址空间按照固定大小划分成称为页面的若干单元。在物理内存中对应的单元称为页框，又称为页架。

设某指令地址 W,页面大小 L,

则页号 P = (int)W/L 偏移量 D = W mod

页表

将进程的每个页面离散地装入到内存的各个页架中，为保证进程的正确运行，即能在内存中找到该进程的各个页面所对应的每个页架，系统记录每个页面对应页架而形成的一张对应表。

颠簸

又称为”抖动“，由于缺少页面过于频繁，反复将页面调入调出内存的现象。

抖动产生的原因

1. 为进程分配的页架过少
2. 页面置换算法选择不当
3. 程序结构不合理

抖动的预防

1. 增加为进程分配的页架数
2. 改进页面置换算法
3. 编程时，充分考虑局部性原理

part four 设备管理

设备的共享性分类

1. 独占设备
2. 共享设备
3. 虚拟设备

设备独立性

应用程序独立于具体使用的物理设备。

I/O数据控制方式的发展阶段

1. 程序直接控制方式
2. 中断控制方式
3. DMA控制方式
4. 通道方式

中断

计算机系统内发生了某一急需处理的事件，使得CPU暂时中止当前正在执行的程序而转去执行相应的事件处理程序，待处理完毕后又返回到原来被中断出继续执行。

引起中断发生的事件称为中断源。

中断源向CPU发出的请求中断处理的信号称为中断请求。

CPU收到中断请求后转向相应事件处理程序的过程称为中断相应。

考试：硬件故障中断>自愿性中断>程序性中断>外部中断>I/O中断

缓冲技术，缓冲技术的分类

引入缓冲可以进一步改善CPU和I/O设备之间的速度不匹配的情况。

缓冲的种类:

1. 单缓冲
2. 双缓冲
3. 循环缓冲
4. 缓冲池

循环缓冲（环形缓冲）没有缓冲队列。

磁盘访问时间包含那三部分

1. 寻道时间：磁头移动到指定柱面的机械运动时间
2. 旋转延迟时间：磁盘旋转到指定扇区的机械运动时间
3. 数据传输时间: 从指定扇区读/写数据的时间

磁盘调度

1. 先来先服务（公平，简单，寻道时间长）
2. 最短寻道时间优先（寻道时间短，”饥饿“）
3. 扫描算法（避免”饥饿“，不利于两端的请求）
4. 循环扫描算法（消除了两端访问的不公平）

part five 文件管理

文件和文件系统

文件：具有符号名的一组相关元素的有序序列，是一段程序或数据的集合。
文件系统：管理文件的数据结构和相应的管理软件以及访问文件的一组操作。

按名存取的物理结构分类

物理结构：从系统的角度考察文件在实际存储设备上的存放形式。

按文件的逻辑存储结构分类

1. 有结构文件：又称为记录式文件。（数据库，数据结构，文档）
2. 无结构文件：又称为流式文件。（源程序，可执行文件，库函数）

文件结构

又称文件的组织形式，如何将记录构成一个文件，以及如何将一个文件存储在外存上。

文件目录

为了便于
文件目录分为一级目录，二级目录和多级目录。多级目录也称为树状结构。