1.中央处理器

1.1 CPU：处理器由运算器、控制器、一系列的寄存器以及高速缓存构成

运算器实现指令中的算术和逻辑运算，是计算机计算的核心

控制器负责控制程序运行的流程，包括取指令、维护CPU状态、CPU与内存的交互等等

寄存器是指令在CPU内部作处理的过程中暂存数据、地址以及指令信息的存储设备。在计算机的存储系统中它具有最快的访问速度。包括用户可见寄存器，控制寄存器。

用户可见寄存器 高级语言编译器通过算法分配并使用之，以减少程序访问主存次数
包括通用寄存器、数据寄存器、地址寄存器
数据寄存器（data register） 主要用于存放操作数
地址寄存器（address register）用于存储数据及指令的物理地址、线性地址或者有效地址，用于某种特定方式的寻址。如index register、segment pointer、stack pointer
I/O地址寄存器
I/O缓冲寄存器

控制寄存器 用于控制处理器的操作,大部分对于用户是不可见的,一部分可以在某种特权模式（由OS使用）下访问

常见的控制和状态寄存器：

程序计数器（PC：Program Counter），记录将要取出的指令的地址
指令寄存器（IR：Instruction Register），包含最近取出的指令
程序状态字（PSW：Program Status Word），记录处理器的运行模式信息等等
中断寄存器
存储器和I/O模块控制的寄存器

高速缓存(内、外）处于CPU和物理内存之间  一般由控制器中的内存管理单元（MMU：Memory Management Unit）管理 访问速度快于内存，低于寄存器。

1.2 特权指令

特权指令：只能由操作系统使用的指令，如启动I/O设备、设置时钟、控制中断屏蔽位、清内存、建立存储键，加载PSW等。常引起处理器状态的切换。CPU如何知道当前运行的是操作系统还是一般应用软件？有赖于处理器状态的标识。

1.3 处理器状态

多数系统将处理器工作状态划分为管态和目态。

管态：操作系统管理程序运行的状态，较高的特权级别，又称为特权态（特态）、系统态。

目态：用户程序运行时的状态，较低的特权级别，又称为普通态（普态）、用户态。

处理器处于管态时：全部指令（包括特权指令）可以执行可使用所有资源并具有改变处理器状态的能力
处理器处于目态时：只有非特权指令能执行

1.4 程序状态字

处理器状态是在PSW中专门设置一位，根据运行程序使用指令的权限而设置，PSW (Program Status Word )。
PSW用来控制指令执行顺序并保留和指示与程序有关的系统状态，主要作用是实现程序状态的保护和恢复。
每个进程都有一个与其执行相关的PSW，每个处理器都设置一个PSW寄存器。进程占有处理器执行，它的PSW将占有PSW寄存器。

PSW寄存器包括以下内容：
程序基本状态：(1)程序计数器；(2)条件码；(3）处理器状态位。
中断码。保存程序执行时当前发生的中断事件。
中断屏蔽位。指明程序执行中发生中断事件时，是否响应出现的中断事件。

2.中断

中断：指CPU对系统中或系统外发生异步事件的响应异步事件是指无一定时序关系的随机发生事件。CPU暂停正在执行的程序，保留现场后自动转去执行相应事件的处理程序，处理完成后返回断点，继续执行被打断的程序。如外部设备完成数据传输，实时设备出现异常等。

分类：

——从中断的性质和激活的手段来分(IBM)：强迫性中断（正在运行的程序所不期望的，由于某种硬件故障或外部请求引起的）、自愿性中断（用户在程序中有意识安排的中断，是由于用户在编制程序时因为要求操作系统提供服务，有意使用“访管”指令或系统调用，使中断发生）。

——按事件来源和实现手段分类(MS/LINUX)：硬中断（中断和异常要通过硬件设施来产生中断请求），软中断（利用硬中断的概念，用软件方法对中断机制进行模拟，实现宏观上的异步执行效果。）硬中断又分为外中断(中断、异步中断)和内中断（异常、同步中断），软中断分为信号和软件中断。

——按事件来源和实现手段分类(MS/LINUX)：

“中断”(硬中断)用于外部设备对CPU的中断(中断的是正在运行的任何程序)，转向中断处理程序上半部分执行；
“异常”(硬中断)因指令执行不正常而中断CPU(中断的是正在执行这条指令的程序)，转向异常处理程序；
“软件中断”(软中断)用于硬中断服务程序对内核的中断，在上半部分中发出软件中断(即标记下半部分)，使得中断下半部分在适当时刻获得处理；
“信号”(软中断)用于内核或进程对某个进程的中断，通知进程某个特定事件发生或迫使进程执行信号处理程序。

外中断(中断或异步中断)--是指来自处理器之外的中断信号，包括时钟中断、键盘中断、它机中断和设备中断等；外中断又分可屏蔽中断和不可屏蔽中断，每个不同中断具有不同的中断优先级，表示事件的紧急程度，在处理高一级中断时，往往会屏蔽部分或全部低级中断。

内中断(异常或同步中断)--是指来自处理器内部，通常由于程序执行中，发现与当前指令关联的、不正常的、或是错误的事件。

中断是由与现行指令无关的中断信号触发的(异步的)，且中断的发生与CPU处在用户模式或内核模式无关，在两条机器指令之间才可响应中断，一般来说，中断处理程序提供的服务不是为当前进程所需的；
异常是由处理器正在执行现行指令而引起的，一条指令执行期间允许响应异常，异常处理程序提供的服务是为当前进程所用的。异常包括很多方面，有出错(fault)，也有陷入(trap)等。

3. 进程及其实现

3.1进程的定义

进程是为了描述程序在并发执行时对系统资源的共享，所需的一个描述程序执行时动态特征的概念。

定义：Process(“任务”（task）或“活动”（active）)。进程是具有独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配、调度和保护的独立单位。

为什么引入进程概念？“可再用” 程序 、“可再入” 程序

原因1-刻画系统的动态性，发挥系统的并发性，提高资源利用率。
原因2-它能解决系统的“共享性”，正确描述程序的执行状态。

3.2进程的类型和特性

分类：系统进程、用户进程。

属性：结构性、共享性、动态性、独立性、制约性、并发性。

进程与程序的区别：

（1）进程更能真实地描述并发，而程序不能

（2）进程是由程序和数据和控制块三部分组成的

（3）程序是静态的，进程是动态的

（4）进程有生命周期，有诞生有消亡，短暂的；而程序是相对长久的。
（5）一个程序可对应多个进程，反之亦然。
（6）进程具有创建其他进程的功能，而程序没有。

状态和转换：

三种进程状态：

运行态（Running）：进程占有CPU，并在CPU上运行
就绪态（Ready）：一个进程已经具备运行条件，但由于无CPU暂时不能运行的状态（当调度给其CPU时，立即可以运行）
等待态（Blocked）：又叫阻塞态、封锁态、睡眠态指进程因等待某种事件的发生而暂时不能运行的状态（即使CPU空闲，该进程也不可运行）

就绪 --> 运行：调度程序选择一个新的进程运行
运行 --> 就绪：运行进程用完了时间片。运行进程被中断，因为一高优先级进程 处于就绪状态。
运行 --> 等待：当一进程必须等待时。OS尚未完成服务。对一资源的访问尚不能进行。初始化I/O且必须等待结果。等待某一进程提供输入 (IPC)。
等待 --> 就绪：当所等待的事件发生时。

进程控制块：

定义：进程控制块（Process Control Block）是系统为了管理进程设置的一个专门的数据结构，用它来记录进程的外部特征，描述进程的运动变化过程。系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志。进程与PCB是一一对应的。

构成：进程描述信息、进程控制信息、进程控制信息、所拥有的资源和使用情况、CPU现场保护信息。

组织：系统把所有PCB组织在一起，并把它们放在内存的固定区域，就构成了PCB表。PCB表的大小决定了 系统中最多可同时 存在的进程个数， 称为系统的并发度。

进程要素：

构成：进程程序、进程数据、栈（用于系统调用、过程调用时的参数存储和传递）、进程控制块PCB（进程属性）。

进程上下文：进程本身＋运行环境对进程执行活动全过程的静态描述。

上下文切换：让处于运行态的进程中断运行，让出处理器，这时要做一次进程上下文切换、即保存老进程状态而装入被保护了的新进程的状态，以便新进程运行。 

4.进程的控制

概述：进程控制是系统使用一些具有特定功能的程序段来创建、撤消进程以及完成进程各状态间的转换，从而达到多进程高效率并发执行和协调、实现资源共享的目的。 包括：创建进程、阻塞进程、唤醒进程、挂起进程、激活进程、终止进程和撤销进程等。

原语：这些控制和管理功能是由操作系统的原语来实现。原语(Primitive)是在管态下执行、完成系统特定功能的过程。 原语和机器指令类似，其特点是执行过程中不允许被中断，是一个不可分割的基本单位，原语的执行是顺序的而不可能是并发的。一种原语的实现方法是以系统调用方式提供原语接口，且采用屏蔽中断的方式来实现原语功能，以保证原语操作不被打断的特性。

4.1进程的创建：略
4.2进程的阻塞和唤醒：略
4.3进程的撤销 略
4.4 进程的挂起和激活 略

5.进程切换和模式切换

5.1执行模式

两种：特权模式、用户模式。

特权模式又称核心模式、系统模式或控制模式，操作系统核心程序在这种模式下运行。某些指令只能在特权模式下执行，如读写处理机状态字PSW等控制寄存器以及存储管理相关的一些指令。
用户模式就是非特权的模式，用户程序在这个模式下运行。现代操作系统有许多系统功能也由运行在用户模式的程序实现。如Linux操作系统的1号进程，它在用户态运行INIT程序，负责所有用户终端进程的创建。

目的：为了保护操作系统和操作系统的数据表格不被可能出错的用户程序破坏。当进程运行系统内核程序时，系统只是保存了用户程序的运行现场，包括所有处理机状态、现场信息，保留原用户程序用数据栈。核心工作状态时处理机执行任何特权指令或访问系统的虚空间都不会报错，待到返回用户态程序时，原保护的程序状态字被恢复，处理机模式又转到用户态下，这以后如果执行了特权指令，处理机即会报错。

5.2 模式切换

CPU模式切换定义：当中断发生时，暂时中断正在执行的用户进程，把进程从用户状态切换到内核状态，去执行操作系统例行程序以获得服务，这就是一次模式切换。内核在被中断了的进程的上下文中对这个中断事件作处理，即使该中断可能不是此进程引起的。被中断进程可以是正在用户态下执行的，也可以是正在核心态下执行的，内核都要保留足够信息以便在后来能恢复被中断了的进程执行。

CPU模式切换过程：1、保存被中断进程的处理器现场信息。2.根据中断号置程序计数器。3、把用户状态切换到内核状态，以便执行中断处理程序。

CPU模式切换与进程上下文切换比较：

模式切换不同于进程切换，它并不引起进程状态变化，也不一定引起进程的切换。在完成了中断调用之后，完全可以再通过一次逆向的模式切换来继续执行用户进程

6、处理器调度 

高级调度（作业调度）、中间调度（平衡负载调度，中程调度）、低级调度（进程调度、短程调度）。

7、作业的管理和调度

7.1 作业及调度

作业：用户在一次计算过程中，或者一次事务处理过程中，要求计算机系统所做工作的总称。

作业流：若干个作业进入系统并存放于主存储中形成作业流

作业步：一个作业可划分成若干部分，每部分称一个作业步

作业的状态及转换：一个作业从进入系统到运行结束经历四个不同的状态：“进入”“后备”“运行”“完成” 。

作业调度的功能：审查系统能否满足用户作业的资源要求、按照一定的算法从输入井中的后备作业中选取作业（ 调度的关键在选择恰当的算法）

7.2 作业与进程

（1）作业是用户向计算机提交任务的任务实体，而进程则是完成用户任务的执行实体，是向系统申请分配资源的基本单位。（2）一个作业可由多个进程组成。且必须至少由一个进程组成，但反过来不成立。（3）作业的概念主要用在批处理系统中，像Linux这样的分时系统中，则没有作业概念，而进程的概念则用在几乎所有的多道程序系统中。

7.3调度原则

目标：单位时间内运行尽可能多的作业、使处理器尽可能保持“忙碌”、响应时间和周转时间能够尽可能短、使各种I/O设备得以充分利用、对所有的作业都是公平合理的。

7.4 调度算法

调度算法性能衡量：作业平均周转时间、平均带权周转时间。

常见的批处理作业调度算法：先来先服务算法（FCFS）、最短作业优先算法（SJF）、最短剩余时间优先算法（SRTF）

（SRTF把SJF算法改为抢占式。 一个新作业进入就绪状态，如果新作业需要的CPU时间比当前正在执行的作业剩余下来还需的CPU时间短，SRTF强行赶走当前正在执行作业。称最短剩余时间优先算法）

最高响应比优先算法：响应比R = 作业周转时间 / 作业处理时间=（作业处理时间+作业等待时间）/ 作业处理时间 = 1 +（作业等待时间 / 作业处理时间）。

基于优先数调度算法、均衡调度算法(分类排队算法)

7.5 单道程序环境下的作业调度算法

假设在单道批处理环境下有四个作业，已知它们进入系统的时间、估计运行时间 应用先来先服务、最短作业优先和最高响应比优先作业调度算法，分别计算出作业的平均周转时间和带权的平均周转时间：

先来先服务调度算法计算结果：

最短作业优先作业算法计算结果：

最高响应比优先作业算法计算结果：

7.6 多道程序环境下的作业调度算法

在两道环境下有四个作业，已知它们进入系统的时间、估计运行时间系统采用短作业优先作业调度算法，作业被调度运行后不再退出
当一新作业投入运行后，可按照作业运行时间长短调整作业执行的次序请给出这四个作业的执行时间序列，并计算出平均周转时间及带权平均周转时间：

最短作业优先作业算法计算结果

算法分析过程
10：10，JOB3到达输入井，内存已有两作业
        JOB3不能马上进入内存；
10：20，JOB4也不能进入内存
10：25，JOB2运行结束，退出，内存中剩下JOB1
     输入井中有两作业JOB3和JOB4，如何调度？
作业调度算法：最短作业优先
因此JOB3进入内存，比较JOB1和JOB3运行时间，JOB3运行时间短，故JOB3运行，同样，JOB3退出后，下一个是JOB4
JOB4结束后，JOB1才能继续运行。

四个作业的执行时间序列为：
JOB1：10：00—10：05，10：40—11：05
JOB2：10：05—10：25
JOB3：10：25—10：30
JOB4：10：30—10：40

8、低级调度

8.1 低级调度功能

概述：低级调度负责动态地把处理器分配给进程或内核级线程。操作系统中实现低级调度的程序称为进程(线程)调度程序，或分派程序(Dispatcher)。进程调度算法多数适用于线程调度。

时间：当一个进程从运行态切换成等待态时；
当一个进程从运行态切换成就绪态时；
当一个进程从等待态切换成就绪态时；
当一个进程中止时。

低级调度的功能：

记录系统中所有进程的执行情况：

作为进程调度的准备，进程管理模块必须将系统中各进程的执行情况和状态特征记录在各进程的PCB表中。根据各进程的状态特征和资源需求等、进程管理模块还将各进程的PCB表排成相应的队列并进行动态队列转接。进程调度模块通过PCB变化来掌握系统中存在的所有进程的执行情况和状态特征，并在适当的时机从就绪队列中选择出一个进程占据处理机。

选择占有处理机的进程：

进程调度的主要功能是按照一定的策略选择一个处于就绪状态的进程，使其获得处理机执行。根据不同的系统设计目的，有各种各样的选择策略，例如系统开销较少的静态优先数调度法，适合于分时系统的时间片轮转法等。

进行进程上下文切换：

系统要首先检查是否允许做上下文切换（在有些情况下，上下文切换是不允许的，例如系统正在执行某个不允许中断的原语时）。然后，系统要保留有关被切换进程的足够信息，以便以后切换回该进程时，顺利恢复该进程的执行。在系统保留了CPU现场之后，调度程序选择一个新的处于就绪状态的进程、并装配该进程的上下文，使CPU的控制权掌握在被选中进程手中。

小结：

记住进程的状态。决定某个进程什么时候获得处理器。决定某个进程占用处理器多长时间。把处理器分配给进程。收回处理器。

8.2 低级调度的方式

可剥夺式（可抢占式Preemptive）：当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的CPU，提供给具有更高优先级的进程使用,或是当运行进程/线程时间片用完后被剥夺。win98/2000/xp
不可剥夺式（不可抢占式 Non-preemptive ）： 某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去，win3.1
折衷方式

8.3低级调度算法

先来先服务算法
时间片轮转调度算法
优先权调度
多级反馈队列调度
保证调度算法
彩票调度算法

9 、线程及其基本概念

9.1 基本概念

概念：引入线程（Thread）的基本目的是将进程以更细的粒度加以切分，以低开销进一步提高系统的并发度。所谓线程，有的系统中也称之为轻量级进程，是进程中的一个运行实体，作为CPU的调度单位。在多线程系统中，资源分配的单位，或是资源的拥有者还是进程。多线程程序设计是指使单个程序中包含并发执行的多个线程。

内容：线程是进程的一条执行路径，它包含独立的堆栈和CPU寄存器状态，每个线程共享其所附属的进程的所有的资源，包括打开的文件、页表（因此也就共享整个用户态地址空间）、信号标识及动态分配的内存等等。
线程是属于进程的，线程运行在进程空间内，同一进程所产生的线程共享同一物理内存空间，当进程退出时该进程所产生的线程都会被强制退出并清除。 
线程有生命周期，即它由创建而产生，由撤消而消亡。在线程的生命期中，它总是从一种状态变迁到另一种状态。
以JAVA语言为例，线程可分为创建状态（new Thread）、可运行状态（Runnable）、不可运行状态（Not Runnable）和死亡状态（Dead）。 

9.2 结构

传统进程与多线程模型：

在传统进程模型中，进程控制块（PCB）记录进程的所有信息，进程拥有一个虚地址空间，一个用户栈用于执行用户程序，一个核心栈用于执行核心程序。

在多线程进程模型中， 除了进程控制块和进程 虚空间外，每个线程拥 有一个线程控制块TCB， 每个线程都有一个用户 栈和核心栈。

线程控制块：

① 线程标识信息。
② 线程运行状态（如运行、就绪等）和调度优先级等调度信息。
③ 分别在用户态和核心态下使用的两个栈。用于保存现场信息、子程序局部变量等。
④ 一个线程关联的私有存储区。
⑤ 与进程描述信息的连接信息。进程内的每个线程都共享进程描述信息，如地址空间、使用资源等。

9.3 进程与线程

联系与区别：

① 进程是资源分配的基本单位。进程也是抢占处理机的调度单位，它拥有一个完整的虚拟地址空间。而线程与资源分配无关，它属于某一个进程，并与进程内的其他线程一起共享进程的资源。
② 当进程发生调度时，不同的进程拥有不同的虚拟地址空间，而同一进程内的不同线程共享同一地址空间。
③ 线程只由相关堆栈寄存器和线程控制块组成。寄存器可被用来存储线程内的局部变量，但不能存储其他线程的相关变量。
④ 进程切换时涉及到有关资源指针的保存以及地址空间的变化等问题；线程切换时，由于同不进程内的线程共享资源和地址空间，将不涉及资源信息的保存和地址变化问题，从而减少了操作系统的开销时间。而且，进程的调度与切换都是由操作系统内核完成，而线程则既可由操作系统内核完成，也可由用户程序进行。
⑤ 进程间的关系比较疏远。各个进程是在自己独有的地址空间内执行，不但寄存器和堆栈是独有的，动态数据堆、静态数据区和程序代码也相互独立。而线程间的关系则要紧密得多，虽然各线程为保持自己的控制流而独有寄存器和堆栈，但由于两线程从属于同一进程，它们共享同一地址空间，所以动态堆、静态数据区及程序代码为各线程共享。

线程优势：

① 快速的关联切换
     由于操作系统级的进程独占自己的虚地址空间，调度进程时，系统必须交换地址空间，因而进程切换时间长。在同一程序内的多个线程共享同一地址空间，因而能使线程快速切换。
② 系统额外开销小
      对多个进程的管理（创建、调度等）有比较大的系统开销。在需要动态创建新进程的应用中，这种开销比较显著。而对线程的管理虽然也会有系统开销，但比进程的小得多。
③ 通信很容易实现
     为了实现协作，进程或线程之间需要进行数据交换。对于自动共享同一地址空间的各线程来说，所有的全局数据都可以访问，因而不需要什么特殊手段就能自动实现数据共享。而进程之间的通信则要复杂得多。
④ 线程个数比进程个数多得多
     许多多任务操作系统限制用户进程总数，这对许多并发应用来说远远不够。在多线程系统中，虽存在线程总数限额，但个数多得多。

9.4 线程的实现

用户级线程：用户级线程是在没有操作系统内核的支持下，完全在用户级提供一个库程序来实现多线程。这些库提供了创建、同步、调度与管理线程的所有功能，无需操作系统特别支持。
由于对线程的所有操作都不涉及内核，因此，用户级线程的创建、结束、调度、现场保护与切换开销非常少。
与线程相关的控制结构TCB保存在目态空间并由运行系统维护，由于线程对操作系统不可见，系统调度仍以进程为单位。

核心级线程：核心级线程是由操作系统支持实现的线程，操作系统维护核心级线程的各种管理表格，负责线程在处理机上的调度和切换，线程是CPU调度的基本单位。

操作系统提供了一系列系统调用界面，让用户程序请求操作系统进行线程创建、结束、同步等操作。

混合级线程：略

10、Linux中的进程管理

Linux中的进程描述

Linux中任务 (Task) 和进 程 (Process) 是两个相同的术语；
Linux 中的每个进程由一个 task-struct 数据结构来描述
task-struct其实就是通常所说的 “ 进程控制块 ” 即 PCB。 task-struct容纳了一个进程的所有信息 , 是系统对进程进行控制的唯一手段
在 Linux2.4 中 ,Linux 为每个新创建的进程动态地分配一个 task-struct结构。
系统所允许的最大进程数是由机器所拥有的物理内存的大小决定的 , 例如 , 在 IA32 的体系结构中 , 一个 512M 内存的机器 , 其最大进程数可以达到 32K

【操作系统】知识点总结之进程管理与调度