计算机操作系统

进程管理

进程(Process)

进程的定义

狭义定义：进程是正在运行的程序的实例。

广义定义：进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动。它是操作系统动态执行的基本单元，在传统的操作系统中，进程既是基本的分配单元，也是基本的执行单元(是系统进行资源分配和调度的一个独立单位)。

描述进程的数据结构：进程控制块（Process Control Block,PCB），操作系统为每个进程都维护了一个PCB，用来保存与该进程有关的各种状态信息。

PCB是进程存在的唯一标志。

PCB含有的信息

1. 进程标识信息

   如本进程的标识，本进程的产生者标识（父进程标识）；用户标示

2. 处理机状态信息

   保存进程的运行现场信息：

   • 用户可见寄存器，用户程序可以使用的数据，地址等寄存器
   • 控制和状态寄存器，如程序计数器(PC)，程序状态字(PSW)
   • 栈指针，过程调用/系统调用/中断处理和返回时需要用到它

3. 进程调度信息/进程控制信息

   • 调度和状态信息，用于操作系统调度进程并占用处理机使用
   • 进程间通信信息，为支持进程间的与通信相关的各种标识、信号、信件等，这些信息存在接收方的进程控制块中
   • 存储管理信息，包含有指向本进程映像存储空间的数据结构
   • 进程所用资源，说明由进程打开、使用的系统资源，如打开的文件等
   • 有关数据结构连接信息，进程可以连接到一个进程队列中，或连接到相关的其他进程的PCB

使用PCB

• 进程的创建：为该进程生成一个PCB

• 进程的终止：回收他的PCB

• 进程的组织管理：通过对PCB的组织管理来实现

PCB的组织方式

• 线性表方式：不论进程的状态如何，将所有的PCB连续地存放在内存的系统区。这种方式适用于系统中进程数目不多的情况。
• 索引表方式：该方式是线性表方式的改进，系统按照进程的状态分别建立就绪索引表、阻塞索引表等。
• 链接表方式：系统按照进程的状态将进程的PCB组成队列，从而形成就绪队列、阻塞队列、运行队列等。

进程的组成

一个计算机系统进程包括下列资料

• 程序的代码
• 程序处理的数据
• 程序计数器中的值，指示下一条将运行的指令
• 一组通用的寄存器的当前值、栈
• 一组系统资源（如打开的文件）

总之，进程包含了正在运行的一个程序所有状态信息。

进程的特点

• 动态性：可动态地创建、结束进程
• 并发性：进程可以被独立调度并占用处理机运行
• 独立性：进程是一个能独立运行的基本单位，同时也是系统分配资源和调度的独立单位
• 异步性^1：由于进程间的相互制约，使进程具有执行的间断性，即进程按各自独立的、不可预知的速度向前推进

并行：一组程序按独立异步的速度执行，无论从微观还是宏观，程序都是一起执行的

并发：在同一个时间段内，两个或多个程序执行，有时间上的重叠(宏观上是同时,微观上仍是顺序执行)

进程与程序的联系

• 程序是产生进程的基础
• 程序的每次运行构成不同的进程
• 进程是程序功能的体现
• 通过多次执行，一个程序可对对应多个进程；用过调用关系一个进程可包括多个程序

进程与程序的区别

• 进程是动态的，程序时静态的：程序是有序代码的集合；进程是程序的执行，进程有核心态/用户态。

• 进程是暂时的，程序是永久的：进程是一个状态变化的过程，程序可长久保存。

• 进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程

  状态信息)

  

进程状态(State)

进程的生命期管理

• 进程创建

  引起进程创建的3个主要事件：

  • 系统初始化时
  • 用户请求创建一个新进程
  • 正在运行的进程执行了创建进程的系统调用

• 进程运行

  内核选择一个就绪的进程，让它占用处理机并执行

• 进程等待

  在以下情况下，进程等待（阻塞）

  • 请求并等待系统服务，无法马上完成
  • 启动某种操作，无法马上完成
  • 需要的数据没有到达

  进程只能自己阻塞自己，因为只有进程自身才能知道何时需要等待某种事件的发生

• 进程唤醒

  唤醒进程的原因：

  • 被阻塞进程需要的资源可被满足
  • 被阻塞进程等待的事件到达
  • 将该进程的PCB插入到就绪队列

  进程只能被别的进程或操作系统唤醒

• 进程结束

  在以下情况，进程结束：

  • 正常退出（自愿）
  • 错误退出（自愿）
  • 致命错误（强制）
  • 被其他进程所杀（强制）

进程状态变化模型

进程的三种基本状态：

• 运行状态(Running)

  当一个进程正在处理机上运行时

• 就绪状态(Ready)

  一个进程获得了除处理机之外的一切所需资源，一旦得到处理机即可运行

• 等待状态(又称阻塞状态Blocked)

  一个进程正在等待某一事件而暂停运行时。如等待某资源，等待输入/输出完成

  

进程的其他基本状态

• 创建状态(New)

  一个进程正在被创建，还没被转到就绪状态之前的状态

• 结束状态(Exit)

  一个进程正在从系统中消失时的状态，这是因为进程结束或由于其他原因所导致

  

  时间片（timeslice）又称为“量子（quantum）”或“处理器片（processor slice）”是分时操作系统分配给每个正在运行的进程微观上的一段CPU时间（在抢占内核中是：从进程开始运行直到被抢占的时间）。

进程挂起

进程在挂起状态时，意味着进程没有占用内存空间。处在挂起状态的进程映像在磁盘上。

挂起状态：

• 阻塞挂起状态（Blocked-suspend）

  进程在外存并等待某事件的出现

• 就绪挂起状态（Ready-suspend）

  进程在外存，但只要进入内存，即可运行

与挂起相关的状态转换：

• 挂起(Suspend)：把一个进程从内存转到外存，可能有以下几种情况

  • 阻塞到阻塞挂起

    没有进程处于就绪状态或就绪进程要求更多内存资源时，会进行这种转换，以提交新进程或运行就绪进程

  • 就绪到就绪挂起

    当有高优先级阻塞（系统认为会很快就绪的）进程和低优先就绪进程时，系统会选择挂起低优先级就绪进程

  • 运行到就绪挂起

    对抢先式分时系统，当有高优先级阻塞挂起进程因事件出现而进入就绪挂起时，系统可能会把运行进程转到就绪挂起状态

• 在外存时的状态转换

  • 阻塞挂起到就绪挂起

    当有阻塞挂起因相关事件出现时，系统会把阻塞挂起进程转换为就绪挂起进程

• 解挂/激活(Activate)：把一个进程从外存转到内存，可能有以下几种情况

  • 就绪挂起到就绪

    没有就绪进程或挂起进行优先级高于就绪进程时，会进行这种转换

  • 阻塞挂起到阻塞

    当一个进程释放足够内存时，系统会把一个高优先级阻塞挂起(系统会认为很快出现所等待事件)进程转换为阻塞进程

状态队列

• 由操作系统来维护一组队列，用来表示系统当中所有进程的当前状态
• 不同的状态分别用不同的队列来表示(就绪队列、各种类型的阻塞队列)
• 每个进程的PCB都根据它的状态加入到相应的队列当中，当一个进程的状态发生变化时，它的PCB从一个状态队列中脱离出来，加入到另外一个队列

线程(Thread)

线程的定义

线程是操作系统能够进行运算调度的最小单位。在大部分情况下，它被包含在进程之中，是进程中的实际运作单位。

线程的优缺点

优点：

• 一个进程中可以同时存在多个线程
• 各个线程之间可以并发地执行
• 各个线程之间可以共享地址空间和文件等资源

缺点：

• 一个线程崩溃，会导致其所属进程的所有线程崩溃

线程与进程的比较

• 进程是资源分配单元，线程是CPU调度单元
• 进程拥有一个完整的资源平台，而线程只独享必不可少的资源，如寄存器喝栈
• 线程同样具有就绪、阻塞和执行三种基本状态，同样具有状态之间的转换关系
• 线程能减少并发执行的时间和空间开销
  • 线程的创建时间比进程短
  • 线程的终止时间比进程短
  • 同一进程内的线程切换时间比进程短
  • 由于同一进程的各线程间共享内存和文件资源，可直接进行不通过内核的通信

线程的实现

• 用户线程：在用户空间实现

  用户线程:在用户空间实现的线程机制，它不依赖于操作系统的内核，由一组用户级的线程库函数来完成线程的管理，包括进程的创建、终止、同步和调度等。

  缺点：

  • 阻塞性的系统调用如何实现？如果一个线程发起系统调用而阻塞，则整个进程在等待
  • 当一个线程开始运行后，除非它主动地交出CPU的使用权，负责它所在的进程当中的其他线程将无法运行
  • 由于时间片分配给进程，故与其他进程比，在多线程执行时，每个线程得到的时间片较少，执行会较慢

• 内核线程：在内核中实现

  内核线程：在操作系统的内核当中实现的一种线程机制，由操作系统的内核来完成线程的创建、终止和管理

• 轻量级线程：在内核中实现，支持用户线程

  轻量级进程：它是内核支持的用户线程。一个进程可有一个或多个轻量级进程，每个量级进程由一个单独的内核线程来支持

用户线程与内核线程的对应关系

• 多对一
• 一对一
• 多对多

进程间通信(Inter-process communication)

进程互斥与同步

基础知识

临界区

**临界区(Critical section)**是指进程中的一段需要访问共享资源并且的当另一个进程处于相应代码区域时便不会被执行的代码区域

互斥

当一个进程处于临界区并访问共享资源时，没有其他进程会处于临界区并且访问任何相同的共享资源

死锁

两个或以上的进程，在相互等待完成特定的任务，而最终没法将自身任务进行下去

饥饿

一个可执行的进程，被调度器持续忽略，以至于虽然处于可执行状态却不被执行

实现临界区互斥的基本方法

• 禁用中断(仅限于单处理器)

  当一个进程正在使用处理机执行它的临界区代码时，防止其他进程进入其临界区的进行访问的最简单的方法是：禁止一切中断发生，称之为屏蔽中断或关中断。
  因为CPU只在发生中断时引起进程切换，因此屏蔽中断能够保证当前运行的进程可以一直占据处理机直到临界区代码执行完，从而完成了互斥访问临界区。
  典型模式为：关中断、临界区、开中断

  缺点

  这种方法限制了处理机交替执行程序的能力，因此系统并发度和吞吐量都会下降。而且将关中断的权利交给用户则很不明智，若一个进程关中断以后，不再开中断，系统可能会因此终止。

• 软件方法(复杂)

  Peterson算法

  Peterson 算法是基于双线程互斥访问的LockOne与LockTwo算法而来。LockOne 算法使用一个 flag 布尔数组，LockTwo 使用一个 turn的整型量，都实现了互斥，但是都存在死锁的可能。Peterson 算法把这两种算法结合起来，完美地用软件实现了双线程互斥问题。

  算法使用两个控制变量flag与turn. 其中flag[n]的值为真，表示ID号为n的进程希望进入该临界区. 变量turn保存有权访问共享资源的进程的ID号.

  // flag[]是bool数组，turn为int
  flag[0] = false
  flag[1] = false;
  int turn;
  
  //P1
  flag[0] = true;
  turn = 1;
  // flag[1] == true时说明另外一个也想运行，
  while(flag[1] == true && trun == 1)
  {
      // 忙等待
  }
  // 临界区
  ...
  // 退出临界区
  flag[0] = false;
  
  //同理P2为
  flag[1] = true;
  turn = 0;
  while (flag[0] == true && turn == 0)
  {
      // 忙等待
  }
  // 临界区
  ...
  // 退出临界区
  flag[1] = false;

  该算法满足临界区问题的三个必须标准：互斥访问, 进入（即不死锁）, 有限等待（即不饿死）

  缺点

  • 复杂：需要两个进程间的共享项
  • 需要忙等待：浪费CPU时间
  • 没有硬件保证的情况下无真正的软件的解决方案：算法需要原子的Load和Store指令

• 原子操作指令(单处理器或多处理器均可)

  TestAndSet指令：这条指令是原子操作。及执行该代码是不允许被中断。其功能是独处制定标志后把该标志设置为真。

  bool TestAndSet(bool *lock)
  {
  	bool rv = *lock;
      *lock = true;
      return rv;
  }
  
  //共享变量lock,true表示正在被占用，false表示没被占用
  bool lock = false;
  
  //进入
  //如果锁被占用(忙状态)，那么TestAndSet读取true并将lock设置为true->锁的状态不被改变并且需要循环
  //如果锁没被占用(被释放)，那么TestAndSet读取false并将lock设置为true->锁被设置为被占用状态，并且需要等待完成
  while(TestAndSet(&lock));
  //临界区
  //离开
  lock = false;

  Exchange(Swap)指令：交换两个变量的内容

  void Exchange(bool *a, bool *b)
  {
  	bool temp = *a;
  	*a = *b;
  	*b = temp;
  }
  
  //共享变量lock，初始化为false
  bool lock = false;
  
  //进入
  bool key;
  key = true;
  while(key == true)
     Exchange(lock, key);
  //临界区
  //离开
  lock = false;

  优点

  • 适用于单处理器或者共享主存的多处理器中任意数量的进程
  • 简单并且容易证明
  • 可以用于支持多临界区

  缺点

  • 忙等待消耗处理器时间

  • 当进程离开临界区并且多个进程在等待时候可能导致饥饿

  • 死锁：如果一个低优先级的进程拥有临界区并且一个高优先级进程页需求，那么高优先级进程会获得处理器并等待临界区

    ps : 优先级反转来解决

死锁(Deadlock)