第一章 计算机系统概述
操作系统：控制和管理整个计算机系统的硬件与软件资源，合理地组织、调度计算机的工作与资源的分配，进而为用户和其他软件提供方便接口与环境的程序集合。
并发：同一时间内间隔发生
并行：同一时刻发生
最基本的特征：并发和共享
虚拟：把一个物理上的实体变为若干逻辑上的对应物
进程的异步性：由于资源有限，进程的执行走走停停，以不可预知的速度向前推进。
中断机制：为了提高多道程序运行环境中CPU的利用率，有一小部分属于内核，负责保护和恢复中断现场的信息，转移控制权到相关处理程序。减少中断的处理时间，提高系统的并行处理能力。
原语：内核的组成部分
- 处于操作系统最底层，最接近硬件的部分；
- 运行具有原子性，一气呵成；
- 运行时间短，调用频繁。
中断（外中断）：指来自CPU执行指令外部的事件。（信息输入输出、I/O结束中断等）
异常（内中断）：来自CPU执行指令内部的事件（程序的非法操作码、地址越界、运算溢出）
系统调用：用户在程序中调用操作系统所提供的一些子功能，系统调用可视为特殊的公共子程序。
虚拟机：逻辑计算机，通过隐藏特定计算平台的实际物理特性，为用户提供抽象的、统一的、模拟的计算环境。
第二章 进程与线程
进程的引入
为了更好地描述和控制程序的并发执行，实现操作系统的最基本特性：并发性和共享性。
进程控制块（PCB）：描述进程的基本情况和运行状态，进而控制和管理进程。
进程实体（进程映像）：由程序段、相关数据段和PCB构成。
创建和撤销进程指的是PCB；进程是动态的；PCB是进程存在的唯一标志。
进程的定义：
- 程序的一次执行过程；
- 一个程序及其数据在处理机上顺序执行时所发生的活动；
- 具有独立功能的程序在一个数据集合上运行的过程，是系统进行资源分配和调度的独立单位；
- 是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。
进程的特点：
- 动态性：具有一定周期性，动态产生、变化和消亡；最基本特征；
- 并发性：多个进程实体同存于内存中，能在一段时间内同时运行。
- 独立性：进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位；
- 异步性：由于进程的相互制约，使得进程按个字独立、不可预知的速度向前推进；由于异步性会导致执行结果的不可再现性，为此OS中必须配置相应的进程同步机制
进程的状态及转换：
- 运行态：进程在处理机上运行；
- 就绪态：进程获得了除了处理机以外的一切所需资源，一旦得到处理机可立即运行；
- 阻塞态（等待态）：进程正在等待某一事件而暂停运行；（阻塞队列）
- 创建态：正在被创建，尚未转到就绪态；
- 结束态：进程正从系统中消失，可能是正常结束或其他原因退出。
PCB
- 进程描述信息：
- 进程标识符（PID）：标志各个进程，每个进程都有唯一的标识号；
- 用户标识符（UID）：进程归属的用户，用户标识符主要为共享和保护服务；
- 进程控制和管理信息：
- 进程当前状态
- 进程优先级
- 资源分配清单：说明有关内存地址空间和虚拟地址空间的状况
- 处理机相关信息：处理机中各寄存器的值
进程控制
对系统中的所有进程实施有效的管理，具有创建、撤销进程以及实现进程状态转换等功能
进程的创建
允许一个进程创建另一个进程，此时创建者称为父进程，被创建的进程称为子进程，子进程可以继承父进程所拥有的资源，当子进程被撤销时，应将其从父进程那里获得的资源归还。撤销父进程时，通常也会同时撤销其所有子进程。
进程的终止
- 正常结束 2. 异常结束 3. 外界干预
进程的阻塞和唤醒：
正在执行的进程由于期待的某些事件未发生，如请求资源失败，进程便通过调用阻塞原语（Block），使自己由运行态变为阻塞态（主动行为）
1）找到将要被阻塞进程的标识号对应的 PCB。
2）若该进程为运行态，则保护其现场，将其状态转为阻塞态，停止运行。
3）把该PCB 插入相应事件的等待队列，将处理机资源调度给其他就绪进程。
被阻塞进程所期待的事件出现时，由有关进程调用唤醒原语（Wakeup），将等待该事件的进程唤醒。
1）在该事件的等待队列中找到相应进程的 PCB。
2）将其从等待队列中移出，并置其状态为就绪态。
3）把该 PCB 插入就绪队列，等待调度程序调度。
两种原语应当成对使用，否则阻塞进程会因不能被唤醒而永久地处于阻塞状态。
进程通信
进程通信：进程之间的信息交换。
PV操作是低级通信方式，高级通信方式是指以较高的效率传输大量数据的通信方式。
高级通信方式：
- 共享存储
在通信的进程之间存在一块可直接访问的共享空间，通过对这片共享空间进行写/读操作实现进程之间的信息交换。
2. 消息传递
进程间的数据交换以格式化的消息（Message）为单位。若通信的进程之间不存在可直接访问的共享空间，则必须利用操作系统提供的消息传递方法实现进程通信。
- 直接通信方式：发送进程直接把消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列中取得消息；
- 间接通信方式：发送进程把消息发送到某个中间实体，接收进程从中间实体取得消息，这种中间实体一般称为信箱。（广泛应用于计算机网络）
3. 管道通信
消息传递的一种特殊方式。“通道”指用于连接一个读进程和一个写进程以实现它们之间的通信的一个共享文件（pipe）文件。向管道提供输入的发送进程（写进程），以字符流形式将大量的数据送入（写）管道；而接收管道输出的接收进程（读进程）则从管道中接收（读）数据。为了协调双方的通信，管道机制必须提供以下三方面的协调能力：互斥、同步和确定对方的存在。
Linux中使用非常频繁。从本质上说管道也是一种文件，管道可以克服使用文件进行通信的两个问题：
限制管道的大小：实际上管道是个固定大小的缓冲区（Linux中为4KB）
读进程也可能工作得比写进程快。
*通过管道控制
管道读数据是一次性操作，一旦被读取就是放空间以便写更多数据。管道只能采用半双工通信，即某一时刻只能单向传输。要实现父子进程互动通信，需要定义两个管道。管道可以理解为共享存储的优化和发展。
线程和多线程模型
线程的基本概念
引入进程的目的是更好地使多道程序并发执行，提高资源利用率和系统吞吐量，而引入线程的目的则是减小程序在并发执行时所付出的时空开销，提高操作系统的并发性能。
线程是一个基本的CPU执行单元，也是程序执行流的最小单位，由线程ID、程序计数器、寄存器集合和堆栈组成。
线程是进程中的一个实体，是被系统独立调度和分派的基本单位，线程自己不拥有系统资源，只拥有一点儿在运行中必不可少的资源，但它可与同属于一个进程的其他线程共享进程所拥有的全部资源。
一个线程可以创建和撤销另一个线程，同一进程中的多个线程之间可以并发执行。
线程有就绪、阻塞和运行三种基本状态。
由于一个进程内部有多个线程，若线程的切换发生在同一个进程内部，则只需要很少的时空开销。
线程和进程的比较
- 调度：线程切换的代价远低于进程。同一进程中，线程的切换不会引起进程切换。但从一个进程中的线程切换到另一个进程中的线程时会引起进程切换。
- 并发性：同/不同进程之间的线程可以并发执行。
- 拥有资源：进程是系统中拥有资源的基本单位，而线程不拥有系统资源（仅有一点必不可少、能保证独立运行的资源），但线程可以访问其隶属进程的系统资源：表现在属于同一进程的所有线程有相同的地址空间。
- 独立性：每个进程都拥有独立的地址空间和资源，除了共享全局变量，不允许其他进程访问。
- 系统开销：创建/撤销进程时，系统要为之分配/回收PCB及其他资源，开销远大于创建/撤销线程。同一进程的所有线程有相同的地址空间，所以这些线程之间的同步和通信非常容易实现。
- 支持多处理机系统：单线程进程只能运行在一个处理机上，多线程进程可以把进程中的多个线程分配到多个处理机上执行。
线程的属性
略
线程的实现方式
- 用户级线程
- 内核级线程
- 组合方式
多线程模型
- 多对一模型
- 一对一模型
- 多对多模型
处理机调度
调度的基本概念
处理机调度：对处理机进行分配，从就绪队列中按一定的算法（公平、高效）选择一个进程并将处理机分配给他运行，以实现进程并发地执行。
调度的层次
- 高级调度（作业调度）少 为进程活动做准备，进程调度使进程正常活动起来。
- 中级调度（内存调度）略多 将暂时不能运行的进程挂起，中级调度处于两者之间。
- 低级调度（进程调度）最多 最基本的、不可或缺。
调度评价算法：1. CPU利用率；2. 系统吞吐量；3. 周转时间；4. 等待时间；5。 响应时间
满足特定系统用户的需求（如实时交互进程的快速响应）；
考虑系统整体效率（如减少整个系统的进程平均周转时间）；
考虑调度算法的开销；
调度的实现
调度程序：用于调度和分派CPU的组件。
- 排队器：将系统中的所有就绪进程按照一定的策略拍成一个或多个队列，以便调度程序选择。
- 分派器：一句调度程序所选择的进程，将其从就绪队列中取出，将CPU分配给新进程。
- 上下文切换器：对处理机进行切换时，会发生两对上下文的切换操作：
- 将当前进程的上下文保存到其PCB中，再装入分派程序的上下文，以便分派程序运行；
- 移出分派程序的上下文，将新选进程的CPU现场信息装入处理机的各个相应寄存器；
不能进行进程的调度和切换的情况：
- 处理中断的过程中；
- 进程在操作系统内核临界区中；
- 其他需要完全屏蔽中断的院子操作过程中；
进程调度方式
- 非抢占调度方式（非剥夺方式）：当一个进程正在处理机上执行时，即使有某个更为重要或紧迫的进程进入就绪队列，仍然让正在执行的进程继续执行，直到该进程运行完成或法师某种事件而进入阻塞态时，才把处理机分配给其他进程。
- 抢占调度方式（剥夺方式）：当一个进程正在处理机上执行时，若有某个更为重要或紧迫的进程进入就绪队列，则允许调度程序根据某种原则去暂停正在执行的进程，将处理机分配给这个更为重要或紧迫的进程。 抢占调度方式对提高系统吞吐率和响应效率有明显好处。
两种线程的调度：
- 用户级线程调度。由于内核不知道线程的存在，所以内核还是和以前一样，选择一个进程，并给予时间控制。由进程中的调度程序决定哪个线程运行。
- 内核级线程调度。内核选择一个特定线程运行，通常不考虑该线程属于哪个进程。对被选择的线程赋予一个时间片，如果超过时间片则强制挂起该队列。用户级线程的线程切换在同一个进程中进行，仅需少量机器指令； 内核级线程的线程切换需要完整的上下文切换、修改内存映像、使高速缓存失效，导致了若干数量级的延迟。
调度算法
- 先来先服务（FCFS）
- 短作业优先（SJF）
- 优先级
- 高响应比优先
- 时间片轮转
- 多级队列
- 多级反馈队列
| 先来先服务 | 短作业优先 | 高响应比优先 | 时间片轮转 | 多级反馈队列 | |
|---|---|---|---|---|---|
| 能否是可抢占 | 否 | 能 | 能 | 能 | 队列内算法不一定 |
| 能否是不可抢占 | 能 | 能 | 能 | 否 | 兼顾长短作业，有较好的响应时间，可行性强 |
| 优点 | 公平，实现简单 | 平均等待时间最少，效率最高 | 兼顾长短作业 | 兼顾长短作业 | 兼顾长短作业，有较好的响应时间，可行性高 |
| 缺点 | 不利于短作业 | 长作业会饥饿，估计时间不易确定 | 计算响应比的开销大 | 平均等待时间较长，上下文切换浪费时间 | 无 |
| 适用于 | 无 | 作业调度，批处理系统 | 无 | 分时系统 | 通用 |
| 默认决策模式 | 非抢占 | 非抢占 | 非抢占 | 抢占 | 抢占 |
进程切换
上下文切换：切换CPU到另一个进程需要保存当前进程状态并恢复另一个进程的状态。（只能发生在内核态） 上下文：某一时刻CPU寄存器和程序计数器的内容。 进行上下文切换时，内核会将旧进程保存在其PCB中，然后加载经调度而要执行的新进程的上下文。
实质：处理机从一个进程的运行转到另一个进程上运行
流程：
- 挂起一个进程，保存CPU上下文，包括程序计数器和其他寄存器
- 更新PCB信息
- 进程的PCB移入相应的队列（就绪、在某事件阻塞等队列）
- 选择另一个进程执行，更新其PCB
- 跳转到新进程PCB中的程序计数器所指向的位置执行
- 恢复处理机上下文
*调度和切换的区别：调度是指决定资源分配给哪个进程的行为（决策行为）；切换时指实际分配的行为（执行行为）。先资源调度后进程切换。
同步与互斥
临界资源：一次仅允许一个进程使用的资源。
临界代码：访问临界资源的代码。
同步
直接制约关系，指为完成某种任务而建立的两个或多个进程，需要在某些位置上协调工作次序而等待、传递信息。
同步机制
- 空闲让进
- 忙则等待
- 有限等待
- 让权等待
互斥
间接制约关系，当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源。
死锁
死锁：指多个进程因竞争资源二造成的一种僵局（互相等待）
产生原因：
- 系统资源的竞争 对不可剥夺资源的竞争可能陷入僵局
- 进程推进顺序非法
(i) 进程运行过程中，亲求和释放资源顺序不当
(ii) 信号量使用不当 - 死锁产生必要条件 需同时满足4个条件
(i) 互斥条件
(ii) 不剥夺条件
(iii) 请求并保持条件
(iv) 循环等待条件
死锁处理策略：
- 死锁预防。（破坏产生死锁的必要条件）
- 避免死锁。（资源动态分配过程中，用某种方法防止系统进入不安全状态）
银行家算法思想：把操作系统视作要回家，操作系统管理的资源相当于银行家管理的资金，进程像操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源。进程运行之前先声明对各种资源的最大需求量，当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过该进程声明的最大需求量。 - 死锁的检测与解除。
死锁定理；
解除：1. 资源剥夺；2. 撤销进程；进程回退；
第三章 内存管理
内存管理主要功能：
- 内存空间的分配与回收。
- 地址转换。（逻辑地址转换为相应物理地址 「地址重定位」）
- 内存空间的扩充。（虚拟存储技术/自动覆盖技术）
- 内存共享。（允许多个进程访问内存的同一部分）
- 存储保护。（互不干扰）
