操作系统
Last updated on January 27, 2023 pm
操作系统
一、操作系统概论
1. 基本特征
软件中最基础的部分是 ，运行在 ，具有对硬件的完全访问权，可以执行机器能够运行的任何指令。
操作系统基本特征：并发（同时存在多个运行的程序）、共享（系统资源供多个并发执行的进程共同使用）（并发和共享是最基本的）、虚拟（时分复用，如虚拟处理器；空分复用，如虚拟存储器）、异步。
2. 功能
操作系统作为计算机系统资源的管理者（处理机管理，可归结为进程管理、存储器管理、设备管理，完成 I/O 请求等、文件管理）；操作系统作为用户与计算机硬件系统之间的接口（命令接口，程序接口如 GUI 调用的系统调用命令）；操作系统实现了对计算机资源的扩充
3. 操作系统发展历程
阶段（无操作系统）：用户独占全机，CPU 等待手工操作
阶段：单道批处理系统：磁带上作业自动按顺序调入内存运行，内存中只有一道程序
多道批处理系统：宏观并行，微观串行，资源利用率高，但不提供人机交互能力，用户无法了解程序运行状态
分时操作系统：按时间片把处理机分给各作业，多用户，实时人机交互
实时操作系统：需要在某个时间限制内完成某些紧急任务。硬实时系统：绝对地在规定的时刻完成（eg. 飞行控制）；软实时系统：能偶尔违规（eg. 飞机订票系统）
4. 操作系统概念
系统调用是什么？
答：程序与操作系统之间的接口，一般由汇编语言写成。
执行系统调用，需要传递系统调用参数，执行陷入指令（也就是说，要切换到内核态），执行相应的服务程序，返回用户态。
什么是 IPC（进程间通信）？
答：进程间协调和同步的通信称为进程间通信。
进程与程序间的不同？
进程是动态的，程序是静态的；进程有一定的生命周期；一个程序可以对应多个进程，但一个进程只对应单一程序；进程除了包括程序代码，还包括运行该程序所需要的资源。
二、进程与线程
1. 进程
什么是多道程序设计？
答：各个任务轮流使用 CPU，每个进程跑几十或几百毫秒。
什么是伪并行？
答：某一瞬间，CPU 只能执行一个进程，CPU 由一个进程快速切换至另一进程给人以并行的假象。
多道程序设计的目的？
- 提高 CPU 的利用率；
- 提高内存和 I/O 设备的利用率；
- 改进系统的吞吐率；
- 充分发挥系统的并行性。
多道程序设计的缺点？
作业的周转时间延长。
导致进程创建的事件有：
- 系统初始化
- 由正在运行的进程创建
- 用户请求创建
- 批处理作业的初始化
前台进程是什么？
与用户交互并完成相应工作的进程。
后台进程是什么？
非前台进程，具有某些专门的功能。
守护进程（daemons）是什么？在后台处理各种请求服务的进程。
UNIX 进程：父进程调用 Wait 可以等待子进程退出。
导致进程终止的条件？
- 正常退出（自愿）
- 出错退出（自愿）eg: 输入文件不存在
- 严重错误（非自愿）eg: 内存越界
- 被其他进程杀死（非自愿）
Unix 有进程组，Windows 无。
进程三种可能状态？
- 运行态：正在使用 CPU
- 就绪态：在等待队列，随时可运行
- 阻塞态：无法运行，直到某些条件满足
OS 中最核心的概念是进程。进程是 的基本单位。什么是进程？
答：一个进程就是一个正在执行程序的实例，是包含运行一个程序所需要的所有信息的容器。
进程的信息保存在一个进程表中，进程表的表项为 （PCB），包括什么？进程从 P1 切换到 P2 时，将 P1 运行状态保存到 P1 的 PCB 中，从 P2 的 PCB 中读出相应的状态。
答：进程控制块 用户 ID（UID）、进程 ID（PID）、组 ID（GID）
2. 线程
线程是什么？
答：线程是操作系统能够调度的最小单位。
线程间可以共享数据、内存。每个线程维护自己的程序计数器、寄存器、堆栈、状态。
为什么需要线程？
答：多个任务可以同时进行；可以共享变量等资源；线程比进程更经济，容易创建和销毁；在多核架构计算机上有用。
线程有哪两种实现方式？有什么优劣？
答：用户级线程：在用户空间实现线程，速度快、可扩展，但阻塞一个进程将阻塞该进程的所有线程，且无法在多核处理器上实现线程级别的并行；内核级线程：在内核空间实现线程，可以单独阻塞某个进程的一个线程，可以在多核处理器上实现线程级别的并行，但线程管理速度慢，线程表非常大，占内存。
还有混合实现方式。
3. 进程间通信（IPC）
什么是竞争条件？
答：多个进程访问一个共享数据，数据的值由进程访问的先后顺序决定。
什么是临界资源？
答：互斥共享变量所代表的资源，即一次只能被一个进程使用的资源。
什么是临界区？
答：并发程序中与共享互斥变量相关的程序段，访问临界资源的程序片段。
实现互斥的方法？
答：严格轮换法（进程 A 退出临界区时把共享变量 turn 赋值 1，仅在 turn = 0 时进入临界区；进程 B 正相反，实现轮换执行。缺点是效率不高，必须轮换），Peterson’s 解法（双标志后检查法的改进，turn 避免相互谦让导致的饥饿；仍然有忙等待），硬件方案（测试并加锁 (TSL) 指令，将内存值保存到 CPU 寄存器并将此值赋 1）
忙等待不仅浪费 CPU，还可能导致优先级反转（优先级高的进程等优先级低的退出临界区）。
信号量原子操作：UP(V)，DOWN(P)。互斥量是特殊的信号量。
4. 进程间同步与互斥的关系
同步是什么？互斥是什么？同步与互斥的关系是什么？
答：多个相互合作的进程，在一些关键节点上互相等待或互相交换信息，这种相互制约关系称为同步。
当一个进程进入临界区使用临界资源时，另一个进程必须等待其退出临界区后才可以访问，这种相互制约关系叫互斥。
互斥是同步的一种特殊情况。
使用信号量实现互斥时，互斥信号量初值常常为 1，实现同步时同步信号量初值一般为 0。
此部分应当看考研题。
5. 进程调度
调度程序是什么？调度算法是什么？调度算法的目标是什么？
答：用于决定哪个进程使用 CPU 的操作系统模块叫调度程序；调度程序使用的算法叫调度算法；调度算法的目标有公平性（每个进程获得相同的 CPU 使用时间）、效率性（CPU 忙碌）、响应时间（指的是从发出命令到得到响应的时间）、周转时间（指的是从提交任务到任务执行完的时间）、吞吐量。
FCFS 先来先服务
SJF 最短作业优先，分为抢占式、非抢占式；平均周转时间最小，但难以预知进程的 CPU 用时
轮转调度
优先级调度（将 CPU 用时短视作优先级高则得到 SJF），可能有饥饿问题，对此可以引入老化技术，让等待进程的优先级随着时间推移而增大（eg. 响应比：(等待时间+要求服务时间)/要求服务时间）
6. 管程
管程是由过程、变量、数据结构组成的集合，进程可以随意调用管程中的过程，但不能在管程外访问管程内的数据结构。编译器确保任一时刻管程中只能有一个活跃的进程。
条件变量允许一个进程在某个变量上等待，只有 wait（挂起调用的进程）、signal（唤醒在该变量上挂起的一个进程）两个操作。
管程的优缺点？
- 编程方便
- 实现困难，难以在编程语言中引入
7. 消息传递
消息传递可能阻塞（同步）或非阻塞（异步）。最受欢迎的是不阻塞发送者，阻塞接受者。
三、内存管理
1. 克服内存容量限制（暂时不知道叫什么）
克服内存容量限制的两个办法？
答：交换技术，虚拟内存
2. 交换技术
把一个程序完整调入内存，使该进程运行一段时间，然后把它存回磁盘。
需要为可能增长的数据段和堆栈段预留空间。
在内存中产生多个空洞时，可以通过什么技术合并空闲区？
答：内存紧缩技术
3. 虚拟内存
覆盖把程序划分成多个片段，能解决程序所需的内存大于内存空间的问题，但程序员所要做的非常复杂。虚拟内存把工作交给计算机去做。（只能基于非连续分配技术）
谁负责把虚拟地址映射成物理地址？
答：MMU（内存管理单元）
虚拟地址空间按固定大小划分为（虚拟）页面，物理内存中对应的单元称为（页）框。
页表实际上是把虚拟页映射成页框的函数。大部分操作系统为每个进程分配一个页表。
页表有哪两种保存方式？各有什么优劣？
- 用寄存器矩阵构成页表：简单，但每次进程切换时都要把整个页表重新加载，代价十分高，严重影响性能；
- 把页表放在内存里，用一个单独的寄存器指向这个页表：上下文切换代价低，但读页表项时要访问一个或多个内存单元。
页表项结构：页框号 在/不在（指示是否有效） 保护位（指明权限） 修改位（是否修改过，供页面置换使用） 访问位 高速缓存禁止位（禁止该页面被高速缓存）
TLB（Translation Lookaside Buffer）（转换检测缓冲器，快表，相联存储器）
多级页表能减小页表大小。
倒排页表是什么？
答：每个实际物理页框对应一个表项。这样节约存储表的内存，但增加了页访问时搜索表所需的时间。
4. 存储管理
使用位图：查找位图中指定长度的连续 0 串较为耗时
使用链表的存储管理：分配空闲内存时有首次适配、下次适配、最佳适配、最大适配四种算法。
5. 页面置换算法
OPT，NRU，FIFO，第二次机会页面置换算法，时钟页面置换算法，LRU，NFU，NFU 老化，工作集模型，工作集时钟算法
最优页面置换算法（OPT，OPTimal replacement）：替换最长时间内不再被访问的页面，性能最优，不可能实现
NRU（最近未使用）的思想？
答：每个页面有访问位（R）和修改位（M），其中访问位会定期清零；将页面分为 Class 0: 未访问，未修改 - Class 1: 未访问，已修改 - Class 2: 已访问，未修改 - Class 3: 已访问，已修改 四大类，NRU 随机从类别序号最低的页面中选择一个页面。
FIFO：维护装入内存中的页面的链表，每次置换最老的，容易实现。
第二次机会页面置换算法（Second Chance）：FIFO 中设置访问位 R，如果 R = 0，替换；R = 1，将其移动到链表尾部并令 R = 0。
时钟页面置换算法：环形链表，R = 1 时向前移动表针
LRU（最近最少使用）：假设最近被使用的页面有很大可能短期内还会被使用。软件方案：用链表将页面链接起来，每次内存请求更新链表，开销巨大；硬件方案：采用 64 位计数器硬件，将值保存到页表中，这样页表会更大。
NFU（最不经常使用）：是 LRU 的近似实现，每个时钟中断时增加相应页面的计数器。带老化技术的 NFU：每次计数器右移一位，最左端置 1。
6. 工作集模型
什么是局部性访问？
答：进程运行的任何阶段都只访问较少的一部分页面。
什么是请求调页：
答：页面在请求时才调入。
什么是颠簸（抖动）？
答：进程每执行几条指令就发生一次缺页中断。
什么是工作集？
答：进程最近一段时间访问的页面集合。
什么是工作集模型？
答：在进程运行之前，系统保持进程的工作集在内存中。
工作集模型页面置换：让一个进程的工作集是该进程在过去的 τ 虚拟时间内访问的页面集，则扫描页表，依次寻找直到找到满足条件的：R = 0，年龄大于 τ 的；R = 0，年龄不大于 τ 但最大的；R = 1，随机选择一个。工作集模型开销大。
WSClock（工作集时钟算法）：有一个定期的时钟中断（假设 τ 横跨多个时钟滴答）清除 R 位；扫描所有页面，若 R = 1，设置 上次使用时间 为 当前时间；若 R = 0 且生存时间大于 τ，替换之；若 R = 0 且生存时间小于等于 τ，看看它是不是生存时间最长的（扫描完就知道了），替换生存时间最长的 R = 0 页面；如果是最坏情况（不存在 R = 0 页面，所有页面都读过了），随机选择一个页面替换（最好是干净页面）。[1]
7. 页面置换算法建模
什么是 Belady 异常现象？
答：采用更多的页框并不总使得缺页次数减少。（我认为，Belady 发生的原因是当页框数增加时，页框中的页面并不是增加前的超集）
LRU 算法建模：当页面被访问时移到表格的最顶端。
什么是栈置换算法？
答：基于 K 个页框的页面集合总是属于基于 (K + 1) 个页框的页面集合，这样的页面置换算法是栈置换算法。
全局分配策略对所有可运行的进程动态分配页框，局部分配策略只对单个进程分配。
全局分配策略可以防止颠簸并保持页命中率在一定范围内。
小页面优点是内部碎片小，缺点是进程需要大量的页，页表大。
8. 杂项
具有相同程序的两个进程可以共享页表
分页守护进程大部分时间处于睡眠状态，当唤醒时会检查内存状态，当空闲页框很少时换出一些页面。
读取数据到缓冲区（我觉得可以类比 DMA）时可以锁住（钉住，pinning）缓冲区页面。
后备存储：在磁盘上分配空间两种方法（此部分我没有详细地看）
9. 缺页中断处理
陷入内核 -> 保存通用寄存器等信息 -> 发现需要哪个虚拟页面 -> 检查地址是否有效，检查存取与保护是否一致；无错则检查是否有空闲页框，如果无，页面置换算法淘汰一个页面 -> 如果选择的页框“脏”，写回磁盘 -> 页框干净后查找所需页面在磁盘地址并装入 -> 更新页表 -> 恢复发生缺页中断以前的状态，程序计数器重新指向这条指令 -> 调度引发缺页中断的进程 -> 返回到用户空间继续执行
10. 分段
段是逻辑上独立的地址空间。段使用二维内存地址，由 段号，段偏移量 两部分组成。（是二维的，所以要相加；而分页则是一维的）
11. 分区存储管理
固定分区，可变分区
连续分配管理方式：单一连续分配，固定分区分配，动态分区分配；
非连续分配管理方式：基本分页存储管理，基本分段存储管理，段页式存储管理
12. 内存管理
内存管理的主要功能？
- 内存空间的分配与回收
- 地址转换
- 内存空间的扩充
- 存储保护
什么是地址重定位？
答：将用户程序中的逻辑地址转换为运行时可由机器直接寻址的物理地址，这一过程称为地址重定位。
四、文件系统
1. 文件
常见的三种文件结构有字节序列（Windows、Linux）、记录序列（已过时，很少使用）、树（大型机）。
文件类型分为普通文件和目录文件，Unix 还有字符设备文件、块设备文件等。普通文件一般分为 ASCII 文件和二进制文件。
文件访问可以分顺序访问和随机访问。
2. 目录
文件系统用目录记录文件的位置，一级目录只有一个目录（root），二级目录包含 root 和用户目录，层次目录包含 root 目录、用户目录和任意多的子目录。绝对路径包含从 root 目录到该文件的路径，相对路径包含从当前目录到该文件的路径。. 指当前目录，.. 指父目录。
3. 文件系统的实现
文件由哪两部分组成？
答：文件由文件控制块（FCB，保存文件属性，如文件名、存取控制，在 Unix 中称为 i-node）和文件体两部分构成。open 系统调用：读的是控制信息。
磁盘分为主引导记录：磁盘 0 号扇区，记录分区表；分区表给出每个分区的起始和结束地址；磁盘分区，每个分区都包含引导块（用于引导装载 OS）、超级块（文件系统参数）、空闲空间。
文件系统可以采取什么分配方式？其优缺点是什么？
连续分配（每个文件作为一连串的数据块存储，实现简单，读取性能好，但容易产生碎片，且要预先知道文件大小，如 CD-ROM）、链表分配（为每个文件构造磁盘块链表，但随机访问速度慢，且每个物理块中存储的数据不是 2 的整数幂次方）、文件分配表（FAT，把每个物理块的指针集中记录到一个表，放在内存中索引，优点是整个物理块可用于存储数据，且信息访问在内存中，访问快，缺点是需要占用大量内存（所有物理块都有个数组项））、I-节点（I-node）（记录文件属性以及文件内容的存储地址；索引节点下可以挂间接块）
4. 目录的实现
当一个文件被打开时，文件系统首先用用户给出的路径信息找到相应的目录项，目录项提供了查找文件物理块所需的信息（eg: i-节点的值）
文件属性可以存放在什么位置？
- 简单目录：目录项中存储文件属性和地址；
- 引用 i-节点的目录：把文件属性存在 i-节点中。
有哪些方法处理长文件名？缺点？ - 目录项中固定长度（浪费空间）
- 目录项中记录可变长的文件名（删除文件产生空隙）
- 文件名放入目录后面的堆中（管理堆产生开销）
如何搜索文件？ - 从目录中线性搜索（慢）
- 哈希表（速度快，但有额外开销，文件多时才考虑）
- 将查找结果存入高速缓存
5. 共享文件
目录与共享文件的联系称为链接。
传统树形目录共享：将不同的 FCB 设为同一物理地址，但新增内容无法共享。
基于索引节点的共享方式（硬链接）：目录项指向相同的索引节点，需要增加一个计数值统计指向该索引节点的目录项的个数。优点是不需要多次访问磁盘，不需要额外空间存储文件路径名。
用符号链接实现文件共享（软链接）：符号链接文件包含该文件的路径，需要读取包含路径的文件再一级一级扫描，有额外磁盘开销。优点是符号链接可以指向其他机器文件。
6. 虚拟文件系统
抽象出文件系统共有的部分。优点是对不同的文件系统使用相同的 API，将文件操作与具体的文件系统实现分开，具有更好的灵活性。
7. 磁盘空间管理
磁盘块大：内部碎片，空间效率降低；块小：时间效率降低。
记录空闲块的方法？
- 磁盘块链表（每个块都保存指向下一个空闲块的指针）
- 位图（空闲块用 1，已分配块用 0 表示）
8. 文件系统备份
哪两种备份策略？优缺点？
- 物理转储：全部磁盘块复制，简单快速，但无法增量转储，不能满足对特定文件的恢复请求。
- 逻辑转储：从一个或几个指定的目录开始，递归地转储其自给定基准日期后更改的文件和目录。满足恢复特定文件或目录的请求。
逻辑转储算法四步骤？ - 将修改过的文件和全部目录标记；
- 去掉不包含任何修改过的文件或目录的目录上的标记；
- 转储所有标记为需转储的目录
- 转储被标记的文件
9. 文件系统一致性
一致性检查分为块一致性检查和文件一致性检查。
块一致性检查步骤？
答：构建两张表，第一张表记录块在文件中出现的次数，第二张表记录块在空闲列表中的使用情况；然后通过扫描 i-node/FAT 更新第一张表的值，扫描空闲列表/位图更新第二张表的值；每一块或者在第一张表中为 1，或者在第二张表中为 1，如果都是 0（块丢失），添加到空闲列表，如果空闲列表中的值大于 1（空闲块重复），重新建立空闲表，如果数据块重复，则分配一个空闲块，复制重复的内容到该块，插入到其中一个文件中。
文件一致性检查步骤？
维护一张表，其中一个文件对应一个计数器；扫描文件系统，对目录中每个文件，计数器加一；比较计数值和 i-node 中的值，如果不相等，把 i-node 中的链接计数设为目录项个数。
10. 文件系统性能
什么是块高速缓存？
答：一系列逻辑上属于磁盘，但实际上保存在内存中的块。
页面置换算法可用于管理高速缓存。
为了减少磁盘臂运动，可以把有可能顺序读取的数据放在一起。（i-node 放在磁盘开始位置）
五、输入/输出
1. I/O 设备
块设备：传输以一个或多个完整的块为单位（如磁盘）
字符设备：以字符为单位发送或接收一个字符流（如键盘、鼠标、打印机）
其他设备：时钟
每个 I/O 设备有两个组成部分：物理部件与电子部件（即设备控制器，其任务是？）
答：控制设备的物理运行；将序列字位转化为字节块流；纠错
控制器与 CPU 的数据交互通过设备寄存器进行，为提高效率，设备通常还有数据缓冲区。
2. 访问 I/O 方式
每个控制寄存器被分配一个 I/O 端口号（不干扰内存操作，增加程序设计难度）
内存映射 I/O：所有控制寄存器映射到内存空间（与内存访问统一，增大系统设计难度）
混合方案：数据缓冲区用内存映射 I/O，控制寄存器用单独的 I/O 端口
3. I/O 实现方式
程序控制 I/O（忙等待）：CPU 与外围设备间的数据传送由 CPU 完成
中断驱动 I/O：CPU 初始化 I/O 并启动第一次 I/O 操作 -> CPU 处理其他任务 ->当 I/O 完成时产生中断 -> CPU 处理中断 -> CPU 恢复被中断的程序
使用 DMA 的 I/O：DMA 控制器进行数据交换
4. I/O 软件层次
I/O 软件有哪四个层次？
- 用户级 I/O 软件（库过程（printf、scanf），假脱机（spooling）：如打印机守护进程打印假脱机目录下的文件）
- 与设备无关的操作系统软件（执行对所有设备公共的 I/O 功能，并且向用户层软件提供一个统一的接口；缓冲，提高数据传输率，防止溢出：无缓冲，用户空间缓冲（页面被调出的话会出问题）、内核空间缓冲接着复制到用户空间（效率高得多，但缓冲区满了调入内存时无法接收数据）、内核空间双缓冲（一个缓冲区正在被复制时另一个可以收集输入））
- 设备驱动程序（直接驱动 I/O 进行输入输出操作的软件，通常是内核的一部分；驱动程序阻塞自己，直到 I/O 操作完成并产生一个中断；禁止在驱动程序中调用系统调用）
- 中断处理程序（常常要唤醒设备驱动程序）
用户发出 I/O 请求后，用户程序 -> 系统调用 -> 设备驱动 -> 中断处理
5. 磁盘
分为硬盘、软盘。磁盘被组织成柱面、盘面和扇区的层次。（磁盘的硬件结构包括磁头、磁道、扇区）
磁盘读写时间由 、 、 三部分组成。通常寻道时间占主要部分。
答：寻道时间、旋转延迟、实际数据传输时间。
错误验证由磁盘控制器完成。
对磁盘读写信息的最小单位是物理块。
为了隐藏每个磁道有多少扇区的细节，大多数现代磁盘除了物理几何规格外有一个虚拟几何规格呈现给操作系统。
磁盘在使用前，盘片必须低级格式化。一个磁盘扇区包括哪些部分？前导码包含柱面、扇区号等用以识别扇区，ECC 用于恢复错误。
答：前导码、数据部分（通常为 512 字节）、ECC。
柱面斜进的目的：让磁盘在一次连续的操作中读取多个磁道而不丢失数据。
由于读出扇区后要做 ECC 计算后才能传送数据，无法连着读取多个扇区，可以采用磁盘交错编号，如单交错、双交错。
6. 磁盘臂调度算法
磁盘臂的调度由驱动程序调用处理。
常用的调度算法：
- 先来先服务（FCFS）
- 最短寻道优先（SSF，Shortest Seek First）
- 电梯算法（要知道初始移动的方向，否则要讨论）
7. 坏扇区处理
可以将磁盘中的一个备用扇区映射为对应的坏扇区，也可以顺序移动坏扇区后续的扇区。
8. 稳定存储器
稳定存储器的目标是不惜一切代价保证磁盘数据的正确性。稳定存储器使用一对相同的磁盘。
稳定写的步骤是：驱动器 1 上写一个块，然后读并验证，若验证错误，则继续写并验证，直到正确；若 n 次后仍不正确，则将该块映射到备用块上。之后用同样的方法将数据备份到驱动器 2 上。
稳定读的步骤：从驱动器 1 上读块，若产生错误 ECC 则再次读，经过 n 次连续的失败后，从驱动器 2 上读取对应的数据块。
9. 廉价磁盘冗余阵列
10. 时钟
可编程时钟有哪两种操作模式？
答：一次完成模式（类似倒计时）与方波模式（周期性的时钟中断）。
时钟驱动功能：维护日时间；防止进程超时运行；处理用户进程提出的 alarm 系统调用等。
维护日时间的三种方法？
答：64 位寄存器保存时钟滴答；保存秒数和当前一秒中的时钟滴答；保存开机时间和从开机时间之后的时钟滴答。
11. 键盘
每次按键或释放均产生一个中断，键盘驱动从 I/O 端口提取键盘产生的扫描码，转为 ASCII 码。
处理方式：规范模式（驱动程序行内编辑并传给用户程序）、非规范模式（原始模式）。
12. 鼠标
带跟踪球；光电鼠标。
13. 输出软件
一个图形用户界面有哪四个基本要素？
答：窗口、图标、菜单、定点设备。
14. 电源管理
省电的最常用办法是将设备设计成具有多种状态，如工作、睡眠、休眠、关闭。
电压减半，时钟速度减半，功耗减少到 1/4。
六、死锁
1. 资源与死锁
什么是资源？
答：资源指的是一种能够被请求、被使用和被释放的对象。
资源分为哪两类？
答：可抢占资源、不可抢占资源
请求失败，请求资源的进程常常会被阻塞
死锁的定义是？（注意其主语）
答：一个程序集处于死锁状态，当集合中的每个进程都在等待一个资源，而该资源又被集合中的另一个进程占有。
2. 死锁的条件
死锁需要哪四个必要条件？
- 互斥条件：进程拥有的资源不能被共享，只能由一个进程使用；
- 占有和等待条件：已得到资源的进程可以再请求新的资源
- 不可抢占条件：分配给进程的资源不可强制抢占，只能被拥有它的进程释放
- 环路等待条件：存在一条环路，环路中每个进程都在等待下一个进程所占有的资源。（这里的表述是“下一个”）
3. 死锁建模
利用有向图建模：资源用方形，进程用圆形表示；从资源节点到进程节点的有向边代表该资源被请求、授权并占用；从进程节点指向资源节点的有向边表示当前进程正在请求该资源，并且该进程已经被阻塞。（怎么记忆呢？男的向女的伸手只是追求，女的向男的伸手才是追到；资源虽然有个“源”，但它并不是圆的）资源中的圆点或方块表示其实例
4. 处理死锁的策略
鸵鸟算法，死锁检测与死锁恢复，死锁避免，死锁预防
鸵鸟算法：忽略死锁；如果概率非常小的话，预防死锁的代价非常高
死锁检测与恢复：每种类型一个资源的死锁检测：若从资源分配图中找到一个环，则说明存在死锁；每种类型多个资源的死锁检测：需要现有资源向量 E（资源总数）、当前分配矩阵 C（第 n 行是进程 n 已分配到的资源数）、可用资源向量 A、请求矩阵 R，具体算法是找到一行未标记的 R，其每个分量小于 A 中的值，将其标记为完成，然后把 C 中对应的值加入 A 中。（我叙述的，可能不规范）最后存在没有标记的进程，说明存在死锁；死锁恢复：利用抢占恢复（eg. 人工把打印机的文件拿出来），利用回滚恢复（周期性地对检查点检查，发现死锁则将进程恢复到一个更早的状态），通过杀死进程恢复。
死锁避免：动机是判断满足某个请求是否安全。什么是安全状态？安全状态和不安全状态的区别是？不安全状态并不必然转化为死锁状态（有进程提前终止）银行家算法理论上完美，实际上不实用，因为进程很难预知所需的资源，仅用于少量特殊系统。
答：一个状态是安全的，如果存在某种调度顺序使得每个进程都可以结束，即使所有进程都请求其所需的全部资源。（不存在时称为不安全状态）区别：在一个安全状态，系统可以保证（注意是“可以”）所有进程都能结束；在不安全状态，系统不保证所有进程都能结束。
死锁预防：能否破坏互斥条件？占有并等待呢？不可抢占呢？循环等待呢？
答：破坏互斥条件几乎不可能。破坏占有并等待条件可以要求进程在执行前获得所有资源，但进程可能在开始执行时无法知道所需的资源。破坏不可抢占条件可以在请求另外资源被拒绝时释放掉已有的资源，但不适用于打印机等。破坏循环等待条件可以让进程申请资源必须按资源编号升序提出，但难以确定资源编号顺序，且资源数目太多，难以一一编号。
5. 非资源死锁
通信死锁
6. 两阶段加锁
阶段一：进程对所需的所有记录加锁，一次锁一个，如果某个记录已经被锁，则释放它加锁所有的记录，重新开始。
阶段二：完成更新，释放锁。
（类似一次请求所有的资源）
7. 饥饿
什么是饥饿？
答：一个进程总是被剥夺处理其工作所必需的资源。
饥饿与死锁的比较？
- 死锁会导致饥饿，但饥饿不一定死锁；
- 饥饿有可能自动结束，但死锁不会。
七、安全
1. 环境安全
信息系统的安全分解为哪三个部分？
答：数据机密性（数据暴露；PPT 上写的是生成一份未授权的软件副本也算）、数据完整性（数据篡改）、系统可用性（系统瘫痪或拒绝服务）
入侵者：闯入与自己毫不相干区域的人
2. 密码学原理
柯克霍夫原则：加密算法应该公开，加密的安全性由独立于加密算法之外的密钥决定。
私钥（对称密钥）：密钥量大，速度快
公钥加密，私钥解密，运算速度慢
数字签名：文档->散列值->私钥加密
3. 保护机制：保护域
域是（对象，权限）对的集合，通常域相当于单个用户和用户组。
权限：对某个操作的执行许可
访问控制表：对每个对象给出任意用户的访问权限
权能字列表：对每个进程给出可访问对象
4. 用户验证
常用使用口令验证（可以用“盐”克服加密口令的预计算）、基于实际物体的验证、生物识别验证。
5. 内部攻击
后门陷阱（插入额外代码）、欺骗登录
6. 外部攻击
缓冲溢出
7. 恶意代码
定义：在未被授权的情况下，以破坏软硬件设备、窃取用户信息、扰乱用户心理、干扰用户正常使用为目的编制的软件或代码片段。
特征：目的性、传播性、破坏性
分类：传统计算机病毒和其他恶意代码（木马、蠕虫）
蠕虫是利用系统漏洞自我传播的恶意程序，由引导程序和蠕虫本身组成
8. 可信计算
可信计算：形式上申明了安全要求并满足了这些安全要求
可信计算基：包含了实施所有安全规则所必须的硬件和软件
9. 多级安全
Bell-LaPadula 模型：进程既可下读（简易安全规则）又可上写（* 规则）。（机密，但不完整）
Biba 模型：没有往上写（简单完整性规则），不能向下读（完整性 * 规则）
