绪论部分
一些名词解释
硬件：计算机系统的基本计算资源。
应用程序：用户要使用计算资源解决问题，应用程序决定了使用资源的方式。
操作系统：控制硬件、协调各个应用程序、确保程序对硬件的真确使用且互不干扰。
内核：操作系统中最基本的部分（并不是I/O的全部），除此以外还有系统程序和用户程序。
引导程序：计算机开机时运行的第一个程序。
引导程序通常位于计算机的ROM或EEPROM中。初始化系统各个组件（CPU寄存器、设备控制器、内存……），加载并执行操作系统。
以上阶段完成后，系统就启动完成，等待事件发生。
中断：事件通过中断来通知。
硬件通过系统总线向CPU发送信 ；
软件通过系统调用实现。
发生中断时，停止当前工作，控制转给中断处理程序。程序结束后再继续被中断的计算。
控制转移的实现：
通过一个通用程序检查中断信息，再由该程序调用中断处理程序。
改进：
为了加快中断响应，可通过一张指针表快速调用中断处理程序。
中断请求可以设备 作为索引，从而查到中断处理程序的地址。
内存
所有形式的内存都是字节数组的形式，每个字节都有地址，交互通过CPU对特定的地址执行一系列load、store指令实现。
I/O结构
通用计算机由CPU和多个设备控制器组成，它们通过总线连接。
每个设备控制器维护一定量的本地缓存和一组寄存器。并提供有设备驱动程序。
计算机系统的体系结构
单处理器系统
只有一个主CPU。
通常还有多种处理器分担任务。如针对某设备的特定处理器和功能泛用性较强的通用处理器（如负责传输I/O数据的处理器）。
这些辅助的处理器不执行用户进程。
有时由OS管理；有时自主完成任务，OS无法干涉。
如果系统只有一个通用CPU，那就是单处理器分配系统。
多处理器系统
也称为并行系统或多核系统。
有多个紧密通信的CPU，共享计算机总线，有时还共享时钟、内存、设备。
优点：
吞吐量高，高效。
便宜，多种硬件资源可以共享。
可靠性增加。
多个CPU之间的资源竞争和协调运行会需要额外的开销。使得实际工作效率低于理论值。
多处理器系统类型：
非对称处理：一个主处理器控制系统，向其他的处理器分配任务。
对称多处理（SMP）：没有主从关系，每个处理器都能参与系统的所有任务。都有自己的寄存器、私有缓存。
SMP多处理器各个CPU相互独立，可能会导致一个CPU负载严重、而另一个CPU在摸鱼。可通过共享数据结构避免。
均匀内存访问（UMA）：所有CPU对内存的访问时间都相同。
非均匀内存访问（NUMA）：一个CPU对不同内存的访问有快有慢。可通过虚拟内存管理提升访问效率。
集群系统
另一种类型的多核处理器。多个处理器通常不在一台计算机上，而是通过 络连接的多台计算机处理器的集合。
OS的执行
现代OS是中断驱动的。如果没有进程要执行、没有I/O要服务、没有用户要响应，则OS就保持空闲等待事件发生。
事件总是由中断或陷阱（也称为异常）引起。
-
陷阱：陷阱是用户态使用系统调用时触发，使执行流程从用户态**“陷入”**内核态，从而调用只有在内核态才能执行的内核函数。
因为陷阱是由程序调用触发的，所以发生时间某种程度可预测。
-
中断：中断由外部时间导致，且发生时间不可预测。
外部时间主要指时钟中断、硬件中断等。
时钟中断：进程用完时间片 ，将CPU交给新的进程；
硬件中断：由硬件产生。
中断主要作用是完成进程间切换。
中断处理过程通常会屏蔽中断。
-
异常：由程序代码导致的异常行为，如除零、内存溢出等。
OS 得确保程序的中断只影响自己。
双重模式
将代码区分为 OS 代码和用户代码；系统拥有 2 种独立运行模式：用户模式和内核模式（或监视模式、或系统模式、或特权模式）。
计算机硬件通过模式位来切换模式。例如内核模式-0；用户模式-1。
计算机刚启动时处于内核模式，在用户模式下运行用户程序。在发生中断、系统调用（陷入）、异常，硬件就切换回用户模式。
（先切换模式，再交换控制权）
双重模式如何提供保护/strong>
将可能引起机器错误的指令设为特权指令，只有在系统处于内核模式时才能执行。用户模式对特权指令的执行视为非法。
（基本可以把特权指令看做系统调用）
没有双重模式保护的例子：
MS-DOS（微软的软盘操作系统）中，多个程序可以同时写入一个设备。
对之后内容的一些概括
进程
执行的程序称为进程。
程序≠进程。程序是被动实体（passive entity）；进程是主动实体（active entity）。
进程是系统的工作单元。
系统由多个进程组成，有操作系统进程（执行系统代码），其他的是用户进程（执行用户代码）。
内存
内存是管理现代计算机系统执行的中心。
内存是一个规模从数十万到数十亿大的字节数组，每个字节都有地址。
CPU所执行的指令、访问的数据，都在内存中，内存是CPU能直接寻址访问的唯一一个大容量存储器。
数据存储
文件
OS 对存储设备的物理属性进行抽象，文件就是其定义的逻辑存储单元。
文件是个极其宽泛的内容，不一定要有格式。
大容量存储器
内存容量较小且掉电会失去数据。所以需要大容量外存备份数据。
大多数程序、数据都保存在外存，需要时才调入内存。
高速缓存
设置在内存和外存之间，弥补二者的缺点。
（个人理解，介于两个容量、访问速度差距较大的存储设备之间的设备，似乎都能叫做缓存。）
-
数据同步
在层次存储结构中，同一数据（设为A）可能在多个层次中存在多个副本。例如：硬盘->内存->高速缓存->硬件寄存器。
在数据被CPU修改后，被修改的数据会重新写回硬盘。
对于多任务环境，CPU会在多个进程间切换，所以某进程对数据A做出修改后，应尽快让所有进程获得更新后的数据A。
在多处理器环境中，每个CPU都有各自的内存寄存器、高速缓存。
分布式环境中，一个数据的多个副本可能会出现在多个不同的计算机中。
保护和安全
保护
一种机制，控制进程或用户访问计算机系统的资源。确保系统正常运行。
安全
防止系统受外部或内部的攻击。防范恶意攻击。
内核数据结构
数组
最简单的数据结构，元素可以直接访问，内存就是一个数组。
列表
除了数组外，最重要的数据结构。需要按特定次序访问。最常用的实现是链表。
栈（栈堆）、队列、树、哈希函数与哈希表
（略，没什么好记的）
位图
为 n 个二进制位的串。
例如 0 表示资源可用，1 表示资源不可用。有如下位图：
001011101
第0、1、3、7资源可用，2、4、5、6、8资源不可用。
空间效率高，常用于表示大量资源的可用性。
磁盘驱动器就是这么工作的，每个磁盘块的可用性用位图表示。
第二章 操作系统的结构
与用户交互的界面
命令解释程序（shell）
2种实现方法：
- shell自带代码，接收命令后执行。程序大小与能执行的指令数量相关。
- 命令由系统程序实现，shell解释命令，通过命令确定文件并执行。
图形用户界面（GUI）
一直在用的就是。
shell更容易执行重复的任务。
系统调用
提供 OS 服务接口。
应用程序开发人员根据应用编程接口（API）间接使用系统调用。而API函数通过 OS 的库函数提供。
直接使用系统调用会涉及到更多的细节，且可移植性较差。
传递给系统调用的参数通过寄存器来传递。
如果参数过多，就将参数说在的内存地址通过寄存器传入。
系统调用类型
6类：
- 进程控制
- 文件管理
- 设备管理
- 信息维护
- 通信
- 保护
系统程序
也称为系统工具，为程序开发和执行提供环境。
（个人理解：介于 OS 和应用程序之间
一些对 OS 运行的理解不太有帮助的知识
系统引导
加载内核以启动计算机的过程。
大多数计算机系统都有一小块代码（引导程序），这段代码定位内核，加载到内存执行。
有的计算机系统（如PC）会家在一个更复杂的引导程序，再由后者加载内核。
引导程序都保存在ROM中，无法修改。
固件（EPROM，Erasable Programmable Read-Only-Memory，可擦可编程只读存储器）
对于大型OS，引导程序放在固件上，OS放在磁盘上。
只有当OS内核加载到内存中并开始执行后，才能说系统在运行（running）。
第三章 进程
现在的计算机都是将多个程序加载到内存并发执行。为了对运行的程序进行控制和划分，就有了进程的概念。
进程概念
可看做是执行的程序。除了代码外，还包括当前活动，如程序计数器的值、处理器寄存器的内容等。
在内存中：
文本段：进程的代码。
栈区：临时数据，如局部变量、函数参数、返回地址等。
数据段：全局变量……
堆区：进程运行时分配的内存。
进程与程序的区别
- 程序是被动实体；进程是活动实体，有程序计数器和一组相关资源。
- 2个进程可以与同一个程序相关联：进程的文本段相同，数据、栈、堆不同。
- 进程本身可以作为一个环境，用于执行其他代码。如虚拟机。
进程状态
新的（new）：进程正在创建。
运行（running）：进程正在执行。
等待（waiting）：进程等待某个事件发生。
就绪（ready）：进程等待分配处理器。
终止（terminated）：进程已执行完毕。
以上随意的状态名随OS变化。
进程控制块（PCB）
包含与某个特定进程相关的信息。
- 进程状态：（上一节）
- 程序计数器：表示进程要执行的下一个指令地址。
- CPU寄存器：累加器、索引寄存器、栈堆指针、通用寄存器等，在发生中断时要与程序计数器一起保存。
- CPU调度信息(用于被CPU调度的信息)：优先级、调度队列的指针、其他调度参数。
- 内存管理信息：包括基地址和界限寄存器的值、页表或段表。根据OS使用的内存系统而定。
- 记账信息（个人理解：状态监控信息）：CPU时间、实际使用时间、时间期限、作业或进程数量等。
- I/O状态信息：记录分配给进程的I/O设备、打开文件列表等。
线程
多线程进程一次能执行多个任务。PCB也进行了扩展以保存线程信息。
进程调度
多道程序设计：在计算机内存中同时存放多个相互独立的程序，在管理程序控制下，交替运行。
多道程序设计的目的：无论何时都有进程运行，从而最大化CPU利用率。
调度队列
进程进入系统时，PCB加载到作业队列，这个队列包括系统内所有进程。
就绪队列（ready queue）：保存驻留在内存中的、就绪的、等待运行的进程。这个队列通常由链表实现，头结点有2个指针分别指向队头和队尾。
设备队列（device queue）：等待指定I/O设备的进程列表。每个设备都有自己的设备队列。
进程状态的转换：
新进程被加到就绪队列；在就绪队列中等待，直到被选中执行。当进程分配到CPU并执行时，可能会发生：
进程发出I/O请求，被放到I/O队列；
进程创建一个新的子进程，等待其终止；
由于中断被强制释放CPU，回到就绪队列。
前两种状态，进程最终会从等待状态切换到就绪状态，回到就绪队列。进程一直重复这循环直到终止。最后从所有队列中删除，PCB和资源被释放。
调度程序
进程在队列间的迁移通过**调度程序(scheduler)**来执行。
长期调度程序（或称为 作业调度程序）
从缓冲池（通常为磁盘等大容量存储设备）中选择程序，加载到内存执行。
短期调度程序（或称为 CPU调度程序）
从准备执行的进程中选择进程并分配CPU。
二者的区别
调度频率：
二者的区别主要在于执行频率。短期调度100ms左右间隔，长期调度几分钟间隔。
执行的任务：
短期调度主要用于切换 CPU 执行的进程。
长期调度控制多道程序程度，即内存中的进程数量。
#### 中期调度
分时系统中引入。用于交换操作，将进程换入、换出内存。减轻内存压力。
上下文切换
切换CPU到另一个进程需要保存当前进程状态和恢复另一个进程的状态，这个任务称为上下文切换（context switch）。
切换上下文涉及到的进程状态信息保存在PCB中，包括CPU寄存器的值、进程状态、内存管理信息等。
上下文切换的时间：
上下文切换的时间是纯粹的开销，系统没有做任何工作。
上下文切换速度与机器和硬件有关。不同机器决定了指令数量、涉及到的寄存器等；有的硬件支持则提供多个寄存器组，在切换时只需修改寄存器指针即可。
系统越复杂，上下文切换所要做的就越多。
进程运行
进程创建
大多数 OS 通过唯一的**进程标识符（pid）**识别进程，通常为一个整数。
Linux系统中所有的用户进程构成一棵树，树根进程为 init，pid 总是1。在系统启动后由 init 创建各种用户进程。
创建新进程后父进程的行为：
父进程与子进程并发执行。
父进程等待子进程执行完毕。
新进程的地址空间：
子进程是父进程的复制品（相同的程序和数据）。
子进程加载另一个新程序。
进程终止
子进程执行完后通过系统调用 exit() 请求 OS 删除自身。子进程可以返回状态值到父进程，相关的资源由 OS 释放。
父进程可通过子进程标识符终止自己的子进程。
级联终止：由 OS 启动，当一个进程终止时，得先终止它的所有子进程。
父进程调用wait()
当一个进程终止时，OS会释放资源，但它位于进程表中的条目还存在，直到它的父进程调用wait()；这是因为进程表包含了进程的退出状态。
僵尸进程：进程已终止，但其父进程还未调用wait()。
所有进程终止时都会过渡到这种状态。在父进程调用了wait()后，僵尸进程的进程标识符和它在进程表中的条目都会被释放。
父进程没有调用wait()就终止，使得子进程称为孤儿进程（orphan process），Linux和UNIX的处理方法是： init进程定期调用wait()收集孤儿进程的退出状态，并释放最后的进程残留。
进程间通信
协作的进程需要与其他进程共享数据，需要**进程间通信（IPC）**机制。
IPC有两种基本模型：内存共享（shared memory）和消息传递（massage passing）。如同字面意义：开辟一个共享内存区域向该区域存取数据；进程间交换消息。
以上两种模型在大部分OS中都实现了。
多核处理系统不需要考虑高速缓存的一致性，使用消息传递更高效。
内存共享
快于消息传递，因为不需要经常使用系统调用，只在建立共享内存区域时才会用到，共享内存区建立好后就没有内核的事了，所有进程都向访问自己的内存一样访问共享进程。
具体实现：
一片共享内存区域驻留在创建共享内存段的进程的地址空间内，其他希望使用这个共享内存段进行通信的进程将其附加到自己的地址空间。
注意事项：
共享内存区的数据类型和位置取决于参与的进程，也由这些进程保证不向同一个位置同时写入数据。
总之，共享内存的实现需要靠应用程序的程序员明确编写出来。
协作进程的通用范例：生产者-消费者模型
生产者（producer）进程产生信息，以供消费者（consumer）进程消费。
解决这一问题的方法之一是采用共享内存，为了允许生产者进程和消费者进程并发执行，应有一个缓冲区，以被生产者填充和消费者清空。
消息传递系统
消息传递系统主要靠OS提供的机制实现。
消息传递工具至少要提供发送、接收两种操作。
两个进程在进行通信前，得先建立通信链路（communication link）。
直接通信
通信的每个进程都必须明确指定通信的接收者或发送者。
对应关系
这种方案属于寻址的对称性：每个链路只与两个进程相关；每对进程之间只有一个链路。
变体：寻址的非对称性
只有发送者需要指定接收者，接收者不需要指定发送者。
间接通信
通过邮箱或端口来发送和接收消息，邮箱是一个抽象对象，进程可以向其存取数据。每个邮箱都有一个唯一的标识符。
对应关系
只有当两个进程共享一个邮箱时才能通信。一个链路可以与多个进程相关联；一对进程间可以有多个不同链路，每个链路对应一个邮箱。
邮箱
邮箱可以为进程或OS所拥有，如果邮箱为进程拥有，则邮箱就是进程地址空间的一部分。进程终止，邮箱消失。
OS拥有的邮箱独立存在，此时OS必须提供机制，以允许进程进行：创建邮箱、使用邮箱、删除邮箱的操作。
第四章 线程
概述
CPU 使用的基本单元。
包括：线程id、程序计数器、寄存器组、栈堆。
与同一进程的其他线程共享代码段、数据段和其他 OS 资源。
动机
以 Web 服务器为例。
“进程的创建很耗时间和资源，如果新进程与原来的进程执行相同的任务，那么为什么要承担这些开销
使用了包含线程的进程更有效。可以用创建线程来处理请求。
优点
-
响应性：一个多线程的进程中部分线程阻塞，整个进程仍能继续运行，增加对用户的响应程度。这对用户界面设计尤其有用。
-
资源共享：进程只能通过共享内存或消息传递之类的技术共享资源。这些技术由程序员显式地安排。
线程默认共享所属进程的内存和资源。代码和数据共享的优点：它允许一个应用程序在同一地址空间内有多个不同活动进程。
-
**经济：**进程创建所需的内存和资源分配非常昂贵。因为线程的共享性，创建和切换线程更加经济。虽然测量二者的区别很困难。
-
可伸缩性：在多处理器体系结构中，线程可在多处理器上并行运行。
多核编程
将多个计算核放到单个芯片，只要是多核，无论是单个芯片还是多个芯片，都称之为**多核（multicore）或多核处理器（multiprocessor）**系统。
并行类型
数据并行
将数据分布到多个计算核，每个核执行相同任务。
任务并行
将任务分布到多个核，每个核执行不同任务。
实践中混合使用，不严格区分。
多线程模型
有两种方法来提供线程支持：用户层的用户级线程（user thread）或内核层的内核线程（kernel thread）。
用户线程在内核之上，它的管理无需内核支持；
内核线程由OS直接支持与管理。
二者的联系：多对一、一对一、多对多。
多对一编程
多个用户级线程映射到一个内核线程。
优点：线程管理由用户空间的线程库来完成，因此效率更高。
缺点：如果有一个线程执行阻塞系统调用，整个进程都会阻塞。且任一时间只有一个线程可以访问内核，所以多个线程不能运行在多核系统上。
? 现在几乎没有OS继续使用这个模型了。
一对一模型
每个用户级线程映射到一个内核线程。
优点：当一个线程执行阻塞系统调用时，允许其他的线程继续执行，提供了更好的并发功能；也允许多个线程并行运行在多核系统上。
缺点：每创建一个用户线程就得创建一个相应的内核线程。创建内核线程的开销会影响应用程序的性能，所以这种模型的大多数实现限制了系统支持的线程数量。
Linux和Windows家族，都实现了一对一模型。
多对多模型
多路复用多个用户级线程到同样数量或更少数量的内核线程。
内核线程的数量可能与特定应用或特定机器有关。
总结
- 多对一允许开发人员创建任意多的用户线程，但并没有增加并发性；
- 一对一提供了更大的并发性，但创建线程太多会影响性能；
- 多对多拥有前两者的优点且克服了两者的缺点。
线程库
**线程库（thread library）**为程序员提供创建和管理线程的API。实现方式有2种。
? 1、在用户空间中提供一个没有内核支持的库。库的所有代码和数据结构都位于用户空间。这使得调用库的一个函数并不是系统调用。
? 2、OS 直接支持的内核级的库。库的代码和数据结构都位于内核空间。调用库的一个API会导致对内核的系统调用。
创建多线程常用的策略
异步线程：父线程创建了一个子线程后，父线程就恢复自身的运行。父线程与子线程并发执行，每个线程的运行相互独立，无需知道对方何时终止，所以线程间很少有数据共享。
同步线程：父线程创建一个子线程后，在恢复执行之前等待所有子线程的终止。父线程创建的子线程并发执行，在完成工作后终止，与父线程连接。所有子线程都连接后，父线程才恢复执行。同步线程通常涉及大量数据的共享。
隐式多线程
将多线程的创建和管理交给编译器和运行时库来完成。
线程池
多线程有一些潜在问题：创建线程所需的时间程完成后会被丢弃；如果允许所有并发请求都能通过新线程来处理，无限制的线程可能耗尽系统资源，如CPU时间和内存。
解决这一问题的方法之一：线程池（thread pool）。
线程池的主要思想
在进程开始时创建一定数量的线程，加到池中等待工作。当服务器收到请求时，唤醒池内一个线程（如果有可用的），将需要服务的请求传递给它。一旦线程完成了服务，它会返回到池中在等待工作。如果线程池没有可用线程，服务器会等待，知道有空线程为止。
优点：
使用现有线程比创建一个线程更快；
线程池限制了线程数量；
将要执行任务从创建任务的机制中分离出来，允许我们采用不同策略运行任务。例如：安排任务延时或定期执行。
池内线程数量可根据一些因素来估算：系统CPU数量、物理内存大小、并发客户请求数量的期望值等。
多线程问题
信 处理
（自己理解：线程用于通知进程的机制）
UNIX信 用于通知进程某个事件已经发生。信 的接收可以是同步的或是异步的。
两种信 都遵循相同的模式：
信 是由特定事件触发的。
信 被传递给某个进程。
信 一收到就进行处理。
信 类型
同步信 （自己理解：进程内的线程触发的）
例子包括非法访问内存或被0所除。某个运行程序执行这类非法动作，就会产生信 。
同步信 发送到由于执行操作导致这个信 的同一进程。
异步信
由进程以外的事件产生，进程异步接收这一信 。
通常异步信 发送到另一个进程。
信 处理程序
信 的处理可分为两种：默认的信 处理程序和用户自定义的信 处理程序。
每个信 都有一个默认信 处理程序（default signal handler），在处理信 时由内核来运行。默认动作可以通过**用户定义信 处理程序（user-defined signal handler）**修改。
有的信 可以忽略（如改变窗口大小），有的信 要通过终止程序来处理（如非法内存访问）。
线程撤销
在线程完成之前终止线程。例如多个线程并发搜索数据库时，若有一个线程得到了结果，其他线程就可以撤销。
要撤销的线程通常称为目标线程，有两种撤销情况：
异步撤销：一个线程立即终止目标线程；
通常OS回收撤销线程的系统资源，但不回收所有资源，异步撤销线程可能不会释放必要的系统资源。
延迟撤销：目标线程不断检查它是否应该终止，这允许目标线程有序终止自己。
延迟撤销仅当目标线程检测到标志确定它应撤销时，撤销才会发生。线程可以检查它是否处于安全的撤销点。
线程本地存储
? 某些情况下，每个线程可能需要拥有自己的数据，这种数据称为线程本地存储（Thread-Local Storage，TLS）。
? TLS不同于局部变量，TLS类似于静态数据，但是每个线程独有的。
调度程序激活（LWP）
许多系统实现多对多和双层模型时，在用户和内核线程之间增加一个中间数据结构，称为轻量级进程（LightWeight Process，LWP）。
对于用户级线程，LWP表现为虚拟处理器。每一个LWP与一个内核线程连接，只有内核线程才能通过 OS 调度运行在物理处理器上。如果内核线程阻塞，与之连接的LWP阻塞，与LWP连接的所有用户级线程也都阻塞。
工作过程：
内核提供一组LWP给应用程序，用户程序可以调度用户线程到任何一个可用的LWP。内核将有关特定事件通知应用程序，这个步骤称为回调（upcall），它由线程库通过**回调处理程序（upcall handler）**来处理。
当一个用户线程要阻塞时，一个触发回调的事件发生，内核向应用程序发出一个回调，通知它有一个线程将会阻塞并标识该线程。
然后，内核分配一个新的LWP给应用程序，应用程序在这个新的LWP上运行回调处理程序，它保存阻塞线程的状态，释放阻塞线程运行的LWP。
接着，回调处理程序调度另一个适合在新的LWP上运行的线程。
(阻塞的线程仍占有LWP，新的线程是在原来用于运行回调处理程序的LWP上运行
当阻塞线程等待的事件发生时，内核向线程库发出另一个回调，通知它先前阻塞的线程可以运行了。
该事件的回调处理程序也需要一个LWP，内核可能分配一个新的，或抢占一个用户线程，并在其LWP上执行回调处理程序。
第五章 进程调度
CPU调度是多道程序设计的基础。
对于支持线程的OS，OS实际调度的是内核级线程而非进程。
基本概念
单处理器系统，同一时间只有一个进程运行，该进程等待时，CPU闲置。
多道程序使多个进程同时处于内存，一个运行的进程等待时，OS从该进程接管CPU控制，将CPU交给另一进程。
- 几乎所有计算机资源在使用前都要调度。CPU是最重要的资源之一。
CPU 调度程序
每当 CPU 空闲，OS 通过短期调度程序或 CPU调度程序选择一个合适的进程，分配 CPU ，执行。
抢占调度
需要CPU调度的4种情况：
运行→等待；（I/O请求，调用wait()等）
运行→就绪；（中断）
等待→就绪；（I/O完成）
终止。
1、4情况只进行调度，没有对进程做选择。(即，执行系统调用的进程被调度)
2、3可以选择具体是哪个进程被调度。（由调度程序决定）
非抢占或协作调度只能触发1、4情况；抢占调度能触发所有情况。
抢占调度可能会导致竞争情况，如一个进程正在更新数据时被抢占，而第二个进程刚好要读该数据，这就使得数据处于不一致的状态。（第六章详解）
如果正在修改的数据是重要的内核数据，则会导致严重后果。有的OS这么处理：在上下文切换前，等待系统调用完成或I/O阻塞发生。
调度程序
将CPU控制交给短期调度程序选择的进程，功能包括：
切换上下文。
切换到用户模式。
跳转到用户程序的合适位置，以便将其启动。
调度程序停止一个进程而启动另一个进程的时间称为调度延迟（dispatch latency）。
调度准则
CPU使用率：对于实际系统，应是40%~90%。
吞吐量（throughput）：一个单元时间内进程完成的数量。
周转时间（turnaround time）：从进程提交到完成的时间段。包括等待进入内存、在就
绪队列等待、在CPU上执行、I/O执行。
等待时间：在就绪队列所花时间之和。CPU调度算法所影响的时间。
相应时间：从提交请求到产生第一响应的时间。
调度算法
先到先服务（FCFS，First-Come First-Served）
字面意思，先请求CPU的进程先分配到，执行完后再交给下一个进程。可通过FIFO队列轻松实现。
缺点：平均等待时间很长。
护航效果（convoy effect）：FCFS中的现象。像舰队航行一样，整个OS因为某个（或某些）进程而变慢。起因是一个执行时间较长的进程先获得CPU，导致大量晚到的进程在后面等待。
最短作业优先调度（SJF，Shortest-Job-First）
将每个进程与其下次CPU执行的长度关联，CPU空闲时，优先赋予最短CPU执行的进程。如果两个进程执行时间同样长，则用FCFS处理。
平均等待时间最小，是最优的调度算法。但如何知道下次CPU执行的长度很困难。
对于批处理系统的长期调度，可以将用户提交作业时指定的进程时限作为长度，这就需要用户精确估计进程时间。所以SJF常用于长期调度。
SJF在短期CPU调度上无法实现，只能使用近似的方法。
SJF可以是抢占的或非抢占的。抢占SJF称为**最短剩余时间优先（shortest-remaining-time-first）**调度。
优先级调度（priority-scheduling）
SJF算法是通用优先级调度算法的一个特例。
每个进程都有一个优先级与其关联，最高优先级的进程获得CPU，同优先级按FCFS调度。
优先级通常为固定区间的数字，0~x。对于0表示最高还是最低的优先级没有定论。
优先级的定义可以分为内部的和外部的。
内部优先级采用一些系统测量数据来计算。
如时限、内存要求、打开的文件数量、平均I/O执行时间、平均CPU执行时间等。
外部优先级是与计算机学科无关的外界因素。
如进程重要性、支付使用计算机的费用类型和数量、赞助部门、政治等。
进程可以是抢占的或非抢占的。非抢占的优先级调度算法只是将新的进程加入到就绪队列的头部。
优先级调度算法会导致饥饿（starvation）:低优先级的进程一直处于就绪状态无法运行。要么在系统负荷减轻后能获得运行权，要么在系统关闭后仍未能运行。
解决低级进程无穷等待的方案之一：老化（aging）。逐渐增加在系统中等待很长时间的进程的优先级，最终会使得进程在系统内拥有最高优先级，得以运行。
轮转调度（RR，Round-Robin）
将一个较小时间单元定义为时间片（time slice）或时间量（time quantum），大小通常为10~100ms。
就绪队列为循环队列，CPU调度程序轮流为队列中的每个进程分配不超过一个时间片的CPU。
专门为分时系统设计。类似于FCFS调度，但增加了抢占。
RR算法的性能很大程度取决于时间片的大小。时间片太大会演变为FCFS；时间片太小会导致大量的上下文切换，拖慢进程执行时间。
多级队列调度（multilevel queue）
将就绪队列分成多个单独队列（根据进程属性，如内存大小、进程优先级、进程类型等），一个进程永久被分配到一个队列，每个队列有自己的调度算法。
优点开销低、缺点不灵活。
队列之间也有调度，通常用固定优先级的抢占调度。
每个队列与优先级更低的队列相比有绝对的优先级。即只有当优先级更高的队列都为空时，低优先级队列的进程才能有资格获得CPU。
也可以在队列之间划分时间片。
注意！：这里提到的“时间片”与RR调度的“时间片”概念不同，指的是将一个CPU的执行时间按比例分配给不同的队列，如队列A有80%的CPU时间，队列B有20%的CPU时间。
多级反馈队列调度（multilevel feedback queue）
多级反馈队列基础上，允许进程在队列之间迁移。
如果进程使用过多的CPU时间，就会被转移到优先级更低的队列；使得I/O密集型和交互进程在更高优先级的队列上。
在低优先级队列中等待过长的进程会被转移到更高优先级队列；阻止饥饿发生。
例子：
每个进程进入就绪队列后，就被添加到优先级最高的队列0内，队列内每个进程都能获得8ms的时间片；
如果进程没有在8ms时间片内完成，就被移到队列1尾部，队列1的时间片为16ms；
如果进程还不能完成，被抢占，添加到队列2，队列2内根据FCFS执行。
多级反馈队列调度要考虑到有：
队列数量。
每个队列的调度算法。
确定进程何时升级到更高优先级队列的方法；
确定进程何时降级到更低优先级队列的方法；
用以确定进程在需要服务时将会进入哪个队列的方法。
多级反馈队列调度是最通用的CPU调度算法。通过配置，能适应特定系统。但也是最复杂的算法。
线程调度
在支持线程的 OS 上，内核级线程才是 OS 所调度的（而不是进程）。
用户级线程由线程库管理，内核并不知道它们。用户级线程为了在CPU上运行，通过轻量级线程LWP映射到相关的内核级线程。
使用多对一和多对多模型的系统线程库会调度用户级线程，以便在LWP上运行。线程库的调度方案称为进程竞争范围（Process-Contention Scope，PCS），因为竞争CPU发生在同一进程的不同线程之间。
决定哪个内核级线程调度到一个处理器上，内核采用系统竞争范围（System-Contention Scope，SCS），SCS发生在系统内的所有线程之间。
采用一对一模型的系统，只采用SCS调度。
通常情况下，PCS采用优先级调度，允许抢占，用户级线程的优先级由程序员设置。
多处理器调度
以上都是单处理器系统的CPU调度问题。如果有多个CPU，就能实现负载分配（load sharing）。调度问题也会变得更复杂。
主要关注同构系统，这类系统的处理器从功能上来说形同。可用任何一个处理器来运行队列内的任何进程。但有时也会有一些调度限制：假如有一个系统，它有一个I/O设备与某个处理器通过私有总线相连，希望使用该设备的进程应调度到该处理器上运行。
多处理器调度的方法
非对称多处理（asymmetric multiprocessing）
让一个处理器处理所有调度决定、I/O处理及其他系统活动，其他的处理器只执行用户代码。
这种结构较简单，因为只有主处理器访问系统的数据结构，减少了共享的需要。
对称多处理（Symmetric MultiProcessing，SMP）
每个处理器自我调度。
所有进程可能处于一个共同的就绪队列中，或每个处理器都有它自己的私有就绪队列。
如果是前者，可能会这样调度：每个处理器的调度程序都检查共同的就绪队列，选择一个进程执行。每个处理器都得仔细编程，确保两个处理器不会选择同一个进程。
几乎所有现代OS都支持SMP。
处理器亲和性
进程在一个处理器上运行时会在缓存中存放内存信息，方便下次内存访问。如果这时将进程移到其他处理器上，缓存会这么处理：原处理器缓存的内容设为无效；新处理器的缓存重新填充。
由于缓存的无效或重新填充代价高，大多数SMP系统避免进程在处理器间的转移，尽可能让一个进程保持在一个处理器上运行。这称为处理器亲和性（processor affinity）。
软亲和性：OS尽量保持进程运行在统一处理器上，但该进程仍能迁移到其他处理器。
硬亲和性：允许某个进程运行在某个处理器子集上。（子集
系统的内存架构可以影响处理器的亲和性。下图为采用非统一内存访问（Non-Uniform Memory Access，NUMA）的一种架构，通常这类系统包括组合CPU和内存的板卡，每个板卡的CPU访问本版内存快于其他板的内存。
如果OS的CPU调度和内存分配算法一起工作，那么当进程分配到一个CPU上时，应分配到同一板上的内存中。
负载平衡
对于SMP系统，重要的是保持所有处理器的负载平衡，以便充分利用多处理器的优点。**负载平衡（load balance）**设法将负载平均分配到SMP系统的所有处理器。
对于具有公共队列的系统，负载平衡通常没有必要，因为一旦处理器空闲，它就立刻从公共队列中取走一个可执行的进程。
负载平衡的主要方法：推迁移（push migration）、拉迁移（pull migration）。
个人理解：
推迁移——由一个特定的任务周期性地检查每个处理器负载，将进程超载的处理器推到空闲或不太忙的处理器上。处理器被动接受。
拉迁移——空闲的处理器主动从忙的处理器上拉一个等待任务。
负载平衡处理会抵消处理器亲和性的好处。何时该转移进程，具体情况具体分析。
(剩下的对理解帮助不大，或理解不了)
第六章 同步
协作进程（cooperating process）：与系统内其他执行进程互相影响。直接共享逻辑地址空间（代码和数据），或通过文件或消息来共享数据。
共享数据的并发访问会导致数据不一致，于是创造了多种机制，确保共享同一逻辑地址空间的协作进程的有序执行，从而维护数据一致性。
背景
一个进程在它的指令流上的任何一点都可能会被中断；中断后 CPU 可能会用于处理其它进程的指令。
并发执行如何导致错误生产者-消费者模型为例：
生产者进程代码：
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！