Chapter 2. 进程与线程

公式与性质

• 进程的特征：动态性、并发性、独立性、异步性、（相互制约性）。

• Process Control Block, PCB 通常包含的内容：

  1. 进程描述信息
     • 进程标识符：标志各个进程，每个进程都有一个唯一的标识号。
     • 用户标识符：进程所归属的用户，用户标识符主要为共享和保护服务。
  2. 进程控制和管理信息
     • 进程当前状态：描述进程的状态信息，作为 CPU 分配调度的依据。
     • 进程优先级：描述进程抢占 CPU 的优先级，优先级高的进程可优先获得 CPU 。
  3. 资源分配清单
     • 说明有关内存地址空间或虚拟地址空间的状况，所打开文件的列表和所使用的输入/输出设备信息。
  4. 处理机相关信息
     • 也称 CPU 的上下文。主要指 CPU 中各寄存器的值。当进程处于执行态时，CPU 的许多信息都在寄存器中。当进程被切换时，CPU 状态信息都必须保存在相应的 PCB 中，以便在该进程重新执行时能从断点继续执行。

• CPU 调度的层次（类型）

  1. 高级调度（作业调度、长程调度）：内存与辅存之间的调度。每个作业只调入调出一次。
  2. 中级调度（内存调度、中程调度）：将暂时不能运行的进程调至外存等待（挂起）。（存储器管理中的对换）。
  3. 低级调度（进程调度、短程调度）：按某种算法从就绪队列中选择一个进程将 CPU 分配给它。

• CPU 调度的目标

  • CPU 利用率：
    CPU利用率=\frac{CPU有效工作时间}{CPU有效工作时间+CPU空闲等待时间}
  • 系统吞吐量：单位时间内 CPU 完成作业的数量。
  • 周转时间：作业提交到作业完成的时间。
    带权周转时间=\frac {作业周转时间}{作业实际运行时间}
  • 等待时间：进程处于就绪队列中等待 CPU 的时间之和。
  • 响应时间：进程到达到第一次开始执行的时间。

• 临界资源：一次仅允许一个进程使用的资源。

• 临界区：访问临界资源的程序段。

• 死锁产生的必要条件

  1. 互斥条件
  2. 不可剥夺条件
  3. 请求并保持条件
  4. 循环等待条件

概念

• 在支持多线程的系统中，进程 P 创建的若干线程能共享的有进程 P 的代码段、进程 P 的全局变量、进程 P 中打开的文件等。进程 P 中某线程的堆栈不能共享。

  堆栈存储局部变量和函数调用，不能共享。

• 在单处理器系统中，如果同时存在 10 个进程，则处于运行状态的进程最多为 1 个。

  在单处理器系统中，即使并发，某一时刻也只能有一个进程处于运行状态。

• 程序状态字一般包含程序基本状态、中断屏蔽位、中断码。

• 产生死锁的基本原因是系统资源不足和进程推进顺序非法。

• 当每类资源只有一个个体时，有环必死锁。

• 安全状态一定不死锁，不安全状态不一定死锁。

考点

• 导致创建新进程的操作有

  1. 用户登录。
  2. 高级调度。
  3. 系统处理用户程序的请求。
  4. 用户程序的应用请求。
     \ldots

• 全局变量只能在线程间共享。进程间通信可以使用共享内存、共享文件（管道的 pipe 文件）、消息传递、信号量等。

• 进程中的所有线程共享该进程的状态和资源。进程与线程共享虚拟地址空间，线程与线程之间的虚拟地址空间不完全独立，堆栈独立。 每个线程都有线程执行状态。进程挂起会影响线程的执行。

• 多对一的线程模型：

  1. 一个线程阻塞，整个线程阻塞。
  2. 同一时刻只有一个线程能访问内核。
  3. 多个线程不能同时在多个 CPU 上运行。

• 对于任意 n 个作业，他们的带权平均周转时间最小值为 1 。

  前一个作业结束紧接着后一个作业到达。

• 采用时间片轮转调度算法时，对不同的进程可以规定不同的时间片。一般来说对需经常启动外设的进程，给一个较小的时间片比较合适。

  需经常启动外设的进程比较浪费 CPU ，给较少的时间片。

• 按照作业到达的先后次序调度作业，排队等待时间够长的作业被优先调度，这是指先来先服务调度算法。

  按照作业到达的先后次序调度作业实际上就是排队等待时间够长的作业被优先调度。切勿被迷惑为高响应比优先。

• 先来先服务进程调度算法有利于 CPU 繁忙型作业，而不利于 I/O 繁忙型作业。

• 时间片轮转调度算法一定是抢占式调度算法。

• 进程同步的机制：硬件同步、软件同步、信息量同步。

• Test and SetLock, TSL 只是由硬件实现，具有原子操作而适于并发，但不满足让权等待，不会主动放弃 CPU 。互斥锁和信号量机制才具有让权等待的特性。

• 在由 9 个生产者， 6 个消费者，共享容量为 8 的缓冲器组成的生产者-消费者问题中，互斥使用缓冲器的信号量 mutex 的初值应该为 1 。

  注意是互斥的信号量，不是剩余资源的信号量。

• 信号量用于解决互斥问题时，其初值必须为 1 。

• 管程是由一组数据以及定义在这组数据上的对这组数据的操作组成的软件模块，是由编程语言支持的进程同步机制，可以用于实现进程的同步和互斥。