本文主要来自《精髓与设计原理》一书，黑书作为补充，部分来自于PPT，发现PPT的相当多内容来自于《精髓与设计原理》，看来这书得反复看。

不知道为什么宫老师的课讲的和哪本书都不能完全对上，因此我也是串着看，串着写。

一些总结

进程主要是由于Timesharing(时分复用)的观念而产生，希望最大限度利用CPU。

进程的实现，主要由进程控制块解决。

进程的切换，主要涉及进程控制块PCB的内容。

进程的设计目标：

由全部寄存器打包组成“上下文”context，通过保存和恢复“上下文”，实现进程的无感知启停切换
通过对“触发慢操作”的函数的封装和指令权限限定，实现进程的运行与等待状态切换的感知
监控硬件事件，用以驱动“进程状态机的变化”，从而实现对多个进程正确分类，有效处理

CPU资源的时分复用：

进程切换：CPU资源的当前占用者切换
- 保存当前进程在PCB中的执行上下文(CPU状态)
- 恢复下一个进程的执行上下文
处理机调度
- 从就绪队列中挑选下一个占用CPU运行的进程
- 从多个可用CPU中挑选就绪进程可使用的CPU资源
调度程序：挑选就绪进程的内核函数
- 调度策略
- 调度时机

如何比较调度算法？定义指标:

CPU使用率
吞吐量
周转时间
等待时间
响应时间

进程

CPU其实就是在各个进程之间不停切换，因此每个进程都有自己的虚拟CPU。

定义

进程的如下几个定义：

一个正在执行的程序。
一个正在计算机上执行的程序实例。
能分配给处理器并由处理器执行的实体。
由一组执行的指令、一个当前状态和一组相关的系统资源表征的活动单元。

事实上，不太需要区分进程与程序。就是一段执行的代码

进程控制块（process control block）

为了实现下文的进程模型，操作系统维护着一张表（一个数据结构数组），即进程表(process table)，每个进程表占用一个进程表项（进程控制块），这个块，包含了进程状态的重要信息。

进程的两个基本元素是程序代码（program code,可能被执行相同程序的其他进程共享）和与代码相关联的数据集（set of data)

以下信息可以表征程序执行的任何时刻：

标识符：与进程相关的唯一标识符，用来区分其他进程。
状态：若进程正在执行，则进程处于运行态。
优先级：相对于其他进程的优先顺序。
程序计数器：程序中即将执行的下一条指令的地址。
内存指针：包括程序代码和进程相关数据的指针，以及与其他进程共享内存块的指针。
上下文数据：进程执行时处理器的寄存器中的数据。
I/O状态信息：包括显式1/0请求、分配给进程的1/0设备（如磁带驱动器）和被进程使用的文件列表等。
记账信息：包括处理器时间总和、使用的时钟数总和、时间限制、记账号等。

控制块由操作系统创建和管理。因此，我们可以说进程由程序代码和相关数据及进程控制块组成。

进程状态

轨迹(trace)

列出为进程执行的指令序列，可描述单个进程的行为，这样的序列称为进程轨迹（trace）。给出各个进程轨迹的交替方式，就可描述处理器的行为。然后有一个调度器负责按照轨迹调度。

进程状态模型

首先来看一下最简单的状态模型，这部分比较简单，不记笔记了。

未运行进程必须位于某种类型的队列中，并等待执行时机。
图3.5（b)给出了一个结构，该结构中有一个队列，队列中的每项都指向某个特定进程的指针，或队列可以由数据块构成的链表组成，每个数据块表示一个进程。我们可以用这个排队图来描述调度器的行为。被中断的进程转移到等待进程队列中，或在进程结束或取消时销毁它（离开系统）。在任何情形下，调度器均从队列中选择一个进程来执行。

进程的创建和终止

进程的创建

一个新进程添加到正被管理的进程集时.操作系统需要建立用于管理该进程的数据结构，并在内存中给它分配地址空间，这些行为构成了一个新进程的创建过程。

触发创建的情况

触发进程创建的事件通常有4个，如表所示。

事件	说明
新的批处理作业	磁带或磁盘中的批处理作业控制流通常会提供给操作系统。当操作系统准备接收新工作时，将读取下一个作业控制命令
交互登录	终端用户登录到系统
为提供服务而由操作系统创建	操作系统耵以创建一个进程，代表用户程序执行一个功能，使用户无须等待（如控制打印的进程）
由现有进程派生	基于模块化的考虑或开发并行性，用户程序可以指示创逑多个进程

当操作系统为另一个进程的显式请求创建一个进程时，这个动作就称为进程派生(process spawning)这个操作很有用处。

当一个进程派生另一个进程吋，前一个称为父进程(parent process),被派生的进程称为子进程 (child process)。

创建的过程

这里可能需要一些后面的知识步骤如下：

为新进程分配一个唯一的进程标识符。
为进程分配空间。
初始化进程控制块。
设置正确的链接。
创建或扩充其他数据结构。

进程终止

黑砖给出了四种终止情况：

正常退出（自愿的）
出错退出（自愿的）
严重错误（非自愿）
被其他进程杀死（非自愿）

《精髓与设计原理》的表概括了更加详细的进程终止的典型原因。

事件	说明
正常完成	进程自行执行一个操作系统服务调用，表示它己经结束运行
超过时限	进程运行时闾超过规定的时限可以测星多种类型的时间，包括总运行时间(“挂钟时间”)、花费在执行上的吋间.以及对于交互进程从上一次用户输入到当前时刻的时间总量
无可用内存	系统无法满足进程需要的内存空间
超出范围	进程试图访问不允许访问的内存单元
保护错误	进程试图使用不允许使用的资源或文件.或试图以一种不正确的方式使用，如往只读文件中写
算术错误	进程试图进行被禁止的计算，如除以零或存储大于硬件可以接纳的数字
时问超出	进程等待某一事件发生的时间超过了规定的最大值
I/O失败	在输入或输出期间发生错误，如找不到文件、在超过规定的最多努力次数后仍然读/写失败(如遇到磁带上的一个坏区时)或无效操作(如从行式打印机中读)
无效指令	进程试图执行一个不存在的指令(通常是由于转移到了数据区并企图执行数裾)
特权指令	进程试图使用为操作系统保留的指令
数据误用	错误类型或未初始化的一块数据
操作员或操作系统干涉	由于某些原因.操作员或操作系统终止进程(如出现死锁时)
父进程终止	当一个父进程终止时，操作系统可能会自动终止该进程的所有子进程
父进程请求	父进程通常具有终止其任何子进程的权力
（了解即可，感觉作用不大）

状态模型

黑砖上称为三状态模型：运行态、就绪态、阻塞态。《精髓》上称五状态模型，即还有新建态、退出态。PPT上介绍了更多，比如挂起进程模型。

挂起进程模型

挂起

由于处理器远快于I/O,会出现内存中的所有进程都在等待I/O的现象。因此，即便是多道程序设计，处理器多数时间仍可能处于空闲状态。解决方案之一是交换，即把内存中某个进程的一部分或全部移到磁盘中。有时需要对进程做分级处理，引入优先级会使某进程等待时间过长而被换至外存，这被称为进程挂起，其目的：

提高处理机效率：就绪进程表为空时，要提交新进程，以提高处理机效率；
为运行进程提供足够内存：资源紧张时，暂停某些进程，如CPU繁忙（或实时任务执行）时内存会比较紧张；
便于调试：在调试时，挂起被调试进程对其地址空间进行读写。

队列

可以看到，进程是在状态之间不停切换。那么，每个状态，可以给一个队列。

图3.8(a)给出了可能实现的排队规则，此时有两个队列：就绪队列和阻塞队列。进入系统的每个进程都放置在就绪队列中，当操作系统选择另一个进程运行时，将从就绪队列中进行选择。对于无优先级的方案，这可以是一个简单先进先出队列。当一个正在运行的进程被移出处理器时，它根据情况要么终止，要么放置在就绪或阻塞队列中。最后，当一个事件发生时，所有位于阻塞队列中等待该事件的进程都被放到就绪队列中。

后一种方案意味着当一个事件发生时，操作系统必须扫描整个阻塞队列，搜索那些等待该事件的进程。在大型操作系统中，队列中可能有几百甚至几千个进程，此吋拥有多个队列将会很有效，一个事件可以对应一个队列。因此，事件发生时，相应队列中的所有进程都将转换到就绪态［见图3.8(b)］。最后一种改进是，如果按照优先级方案分派进程.，那么维护多个就绪队列，每个优先级一个队列.将会带來很大的便利。操作系统很容易就可确定哪个就绪进程具有最高优先级且等待时间最长。

挂起状态模型

有单挂起态和双挂起态的区别，不同操作系统差别非常大。

其状态大致可分为：

就绪状态(Ready)：进程在内存且可立即进入运行状态；
阻塞状态(Blocked)：进程在内存并等待某事件的出现；
阻塞挂起状态（Blocked, suspend）：进程在外存并等待某事件的出现；
就绪挂起状态（Ready, suspend）：进程在外存，但只要进入内存，即可运行；

进程描述

操作系统的控制结构

操作系统为了管理进程和资源，必须掌握每个进程和资源的当前状态。普遍采用的方法是，操作系统构造并维护其管理的每个实体的信息表。阍3.11给出了这种方法的大致范围，即操作系统维护的4种不同类型的表：内存、I/O、文件和进程。尽管不同操作系统的实现细节不同，但所有操作系统维护的信息基本都可以分为这4类。

进程控制结构

主要就是进程表的内容

进程位置

因此，一个进程至少应有足够的内存空间来保存其的程序和数据；此外，程序的执行通常涉及用于跟踪过程调用和过程间参数传递的栈。最后，还有与每个进程相关的许多属性，以便操作系统控制该进程。通常，属性集称为进程控制块（process control block）'。程序、数据、栈和属性的集合称为进程映像（process image）（见表）。

项目	说明
用户数据	用户空间中的吋修改部分，包括程序数据、用户栈区域和吋修改的程序
用户程序	待执行的程序
栈	毎个进程有一个或多个后进先出（LIFO）栈，栈用于保存参数、过程调用地址和系统调用地址
进程控制块	操作系统控制进程所需的数据
进程映像的位置取决于所用的内存管理方案。在最简单的情形下，进程映像保存在相邻的内存块中或连续的内存块中。存储块位于外存（通常是磁盘）中，因此在操作系统管理进程时，其进程映像至少应有一部分位于内存中。而要执行该进程，则必须将整个进程映像载入内存中或至少载入虚存中。因此，操作系统需要知道每个进程在磁盘中的位置，并知道每个进程在内存中的位置。

现代操作系统假定分页硬件允许使用不连续的物理内存来支持部分常驻内存的进程气在任意时刻，进程映像的一部分可在内存中，剩余部分可在外存中气因此，操作系统维护的进程表必须给出每个进程映像中的每页的位置。

有一个主进程表，每个进程在表中都有一个表项，每个表项至少包含一个指向进程映像的指针。如果进程映像包括多个块，则这些信息直接包含在主进程表中，或通过交叉引用内存表中的表项得到。当然，这种描述是一般性描述，不同操作系统会按自身的方式来组织位置信息。

进程属性

进程控制块信息分为三类：

进程标识信息
进程状态信息
进程控制信息

标识信息

对于所有操作系统中的进程标识符（process identification）来说，每个进程都分配了一个唯一的数字标识符。进程标识符可以简单地表示为主进程表中的一个索引；否则，就必须有一个映射，以便操作系统可以根裾进程标识符定位相应的表。

状态信息

处理器状态信息（processor state information）由处理器寄存器的内容组成。运行某个进程时，进程的信息一定会出现在寄存器中。中断进程时，必须保存该寄存器的所有信息，以便进程恢复执行时可以恢复所有这些信息。所涉寄存器的性质和数量取决于处理器的设计。

所有处理器设计都包括一个或一组称为程序状态字（Program Status Word, PSW）的寄存器，它包含有状态信息。PSW通常包含条件码和其他状态信息。Intel x86处理器中的处理器状态字就是一个很好的例子，它称为EFLAGS寄存器（见图3.12和表3.6）,能被运行在x86 处理器上的任何操作系统（包括UNIX和 Windows）使用。

控制信息

它是操作系统控制和协调各种活动进程所需的额外信息。

映像在虚存中

图3.13给出了进行映像在虚存中的结构。每个进程映像都由进程控制块、用户栈、进程专用地址空间以及与其他进程共享的其他地址空间组成。图中每个进程映像的地址范围看起来是连续的，但实际情况可能并非如此，具体取决于内存管理方案和操作系统组织控制结构的方式。

进程控制块的作用

操作系统中的很多例程需要访问进程控制块中的信息。直接访问这些表并不困难。每个进程都有一个唯一的ID号，它可用作进程控制块的指针表的索引。困难不是访问而是保护，具体表现为两个问题：

一个例程(如中断处理程序)中的错误可能会破坏进程控制块，进而破坏系统对受影响进程的管理能力。
进程控制块结构或语义中的设计变化可能会影响到操作系统中的许多模块。

这些问题可要求操作系统中的所有例程都通过一个处理程序例程来解决，即处理程序例程的任务仅是保护进程控制块，且是读写这些块的唯一仲裁程序。使用这类进程时，需要在性能和其他系统软件结其的信任度之间进行折中。

进程控制

执行模式

这玩意应该被讲烂了。。。某些指令只能在特权模式下运行，包括读取或改变诸如程序状态字之类的控制寄存器的指令、原始I/O指令和与内存管理相关的指令。另外，部分内存区域仅能在特权模式下访问。

非特权模式通常称为用户模式(user mode),因为用户程序通常在该模式下运行；特权模式称为系统模式（system mode）、控制模式（control mode）或内核模式（kernel mode）,内核模式指的是操作系统的内核，它是操作系统中包含重要系统功能的部分。

使用两种模式的原因是保护操作系统和重要的操作系统表（如进程控制块〉不受用户程序的千扰。在内核模式下，软件会完全控制处理器及其所有指令、寄存器和内存。

处理器如何才能知道它正在什么模式下执行？模式如何变化？

程序状态字中通常存在一个指示执行模式的位，该位会因事件的改变而变化。典型情况下，当用户调用一个操作系统服务或中断来触发系统例程的执行时，执行模式将被置为内核模式；而当从系统服务返回到用户进程时，执行模式则置为用户模式。

比如UCORE的LAB1，就有一个包含2位CPL （Current Privilege Level,当前特权级别）字段的处理器状态寄存器（PSR）o级别0是最高特权级别，级别3是最低特权级別。多数操作系统（如Linux）为内核模式使用级别0,为用户模式使用其他级别。发生中断时，处理器会清空PSR中的大部分位，包括CPL字段。这会自动地将CPL设置为级别0。中断处理例程末尾的最后一个指令是IRT （Interrupt Return,中断返回），它会使得处理器恢复中断程序的PSR,即恢复该程序的特权级别。应用程序进行系统调用时，会出现类似的顺序。对于Itanium而言，应用程序通过如下方式实现系统调用：将系统调用标识符和参数放到一个预定义的区域，然后执行一个特殊指令中断用户模式下的程序执行，将控制权交给内核。

进程切换

何时切换进程

系统中断：分为中断和陷阱。中断就是与外部事件相关，陷阱就是错误。对于普通中断（interrupt），控制权首先转给中断处理器，中断处理器完成一些基本的辅助工作后，再将控制权转给与已发生的特定中断相关的操作系统例程。

进程状态的变化

完整的进程切换步骤如下：

保存处理器的上下文，包括程序计数器和其他寄存器。
更新当前处于运行态进程的进程控制块，包括把进程的状态改变为另一状态（就绪态、阻塞态、就绪/挂起态或退出态〉。还须更新其他相关的字段，包括退出运行态的原因和记账信息。
把该进程的进程控制块移到相应的队列（就绪、在事件/处阻塞、就绪/挂起）。
选择另一个进程执行，详见第四部分的讨论。
更新所选进程的进程控制块，包括把进程的状态改为运行态。
更新内存管理数据结构。是否需要更新取决于管理地址转换的方式。
载入程序计数器和其他寄存器先前的值，将处理器的上下文恢复为所选进程上次退出运行态时的上下文。

调度

主要介绍单处理器调度多道程序设计的关键是调度。实际上典型的调度有4种（见表9.1〉，其中I/O调度将在第11章介绍（讲述有关I/O的问题）。其他三种调度类型属于处理器调度。

种类	描述
长程调度	决定加入待执行进程池
中程调度	决定加入部分或全部位于内存中的进程集合
短程调度	决定处理器执行哪个可运行进程
I/O调度	决定可用I/O设备处埋哪个进程挂起的I/O请求

这里直接放一个表，因为累了。。。后面的内容下一篇再写
大概就是这么集中经典算法，在知道的情况下，理解并掌握优缺点即可。