进程管理

进程与线程

进程的概念与特征

进程的概念

1. 引入

   为实现操作系统的并发性和共享性，引入进程。

2. 概念

   进程是具有独立功能的程序在某个数据集合上的一次执行过程。

   进程是进程实体（进程映像）的运行过程，是系统进行资源调度和分配的独立单位。

3. 进程映像/进程实体

   由程序段，相关数据段，进程控制块PCB构成进程映像。进程映像是反应了进程在某一时刻的状态，因此进程映像是静态的；进程是动态的。

4. PCB是进程的唯一标识

   在进程的整个生命周期中，系统总是利用PCB描述进程的基本情况和运行状态，进而控制和管理进程。即系统根据PCB感知进程的存在。因此称PCB是进程存在的唯一标识。

进程的特征

1. 动态性

   动态性是进程最基本的特征。

2. 并发性

   注意：并发使进程失去封闭性。所谓封闭性是指程序执行结果只取决于程序本身，不受外界影响；失去封闭性则在不同的外界因素下（如执行速度不同）结果也不同。

3. 独立性

4. 异步性

   异步性导致执行结果不可再现。为此必须配置进程同步机制。

5. 结构性

   每个进程都配置一个PCB。结构上由程序段，相关数据段，进程控制块组成。

进程组织

进程内部，进程由下列部分组成：

1. PCB
   1. 进程描述信息 PID、UID
   2. 进程控制管理信息 进程当前状态、进程优先级
   3. 资源分配清单 内存地址指针、IO设备信息
   4. 处理机相关信息 处理机中各寄存器值
2. 程序段
3. 数据段

C语言编写的程序使用内存时分为三个段、正文段、数据堆段核数据栈段。代码和静态赋值在正文段，动态分配的数据在堆段，临时使用的变量（实参、未赋值的变量）在栈段。

进程之间，进程组织方式如下：

1. 链接方式
   1. 按照进程状态将PCB分为多个队列
   2. OS持有指向各个队列的指针
2. 索引方式
   1. 根据进程状态将PCB分为多个索引表
   2. OS持有指向各个索引表的指针。

进程的状态与转换

进程五状态模型：创建态（新建态）、就绪态、运行态、阻塞态、结束态（终止态）。

1. 基本三状态

   1. 运行态

   2. 就绪态

      资源分配完毕准备就绪，等待上处理机运行。调度则变为运行态。

   3. 阻塞态

      缺乏所需资源或正在等待事件发生，不具备上处理机运行资格。得到所需资源或事件发生后转为就绪态。

2. 状态切换

   1. 运行→就绪

      发生调度，如时间片到，或高优先级进程抢占处理机。

   2. 运行→阻塞

      进程需要等待资源或产生事件，例如系统调用，缺页故障等。

      运行→阻塞是进程的主动行为。

   3. 就绪→运行

      发生调度，如分配时间片。

   4. 阻塞→就绪

      进程所需资源或所等待事件已满足，如系统调用返回，内存中已获得新页。

      阻塞→就绪是进程的被动行为。

进程控制

进程控制由不允许中断的程序实现，称该程序段为进程控制原语。原语是不可分割的基本单位。

原语利用关中断和开中断两个特权指令实现其原子性。

进程控制原语的执行内容不外乎下列三种：

1. 检索或申请、分配、更新、删除PCB
2. 将PCB插入相关队列
3. 分配或回收系统资源

进程控制原语实现下列功能：

1. 进程创建

   创建事件：终端用户登录、作业调度、系统提供服务、用户程序请求等事件都会创建进程。

   干扰项：设备分配，只需要设置相应的数据结构即可实现。

   1. 申请和分配PCB（PCB是有限的）
   2. 分配资源
   3. 初始化PCB
   4. 将PCB插入就绪队列

2. 进程撤销

   撤销事件：进程运行正常结束、异常结束、外界干预等。

   1. 检索将被终止的PCB

   2. 若尚在运行，立刻剥夺CPU，分配CPU给其他进程

   3. 终止其所有子进程

      注：该步一般情况下执行，但也存在不终止任何子进程的可能（如创建守护进程），也存在未终止所有进程的可能（如子进程转为孤儿进程被init进程收养）

   4. 回收资源，或归还父进程，或归还操作系统

   5. 从所在队列中删除该进程PCB

3. 进程阻塞和唤醒

   阻塞事件：等待分配资源、等待其他进程完成工作等。

   1. 检索将被阻塞的PCB
   2. 保护现场，转为阻塞态，暂停运行
   3. 将PCB插入对应事件的等待队列

   唤醒事件：等待的事情已发生。

   1. 检索PCB，在对应事件的等待队列中
   2. 从等待队列中移除PCB，设为就绪态
   3. 将PCB插入就绪队列

   特别注意：由何事阻塞，就由何事被唤醒。“解铃还须系铃人”。

4. 进程切换

   切换事件：时间片到，更高优先级抢占，进程请求服务或请求资源而阻塞，进程终止。

   1. 将运行环境信息存入PCB

      具体包括保存处理机上下文（或进程上下文，包括必要的寄存器数据等），更新PCB信息等

   2. 将PCB移入相应的队列

   3. 选择另一个进程执行，并更新PCB

   4. 根据PCB恢复新进程所需的运行环境

表：僵尸进程、孤儿进程、守护进程的区分

表：处理机模式转换与进程状态切换以及调度的区别

进程通信

必要性：各进程拥有的地址空间相互独立，且为了保证安全，相互不能访问其他地址空间。

进程通信分为低级通信方式和高级通信方式。

低级通信

即进程同步，其中的信号量同步称为PV操作。

高级通信

共享存储

图：进程←→共享空间←→进程

通信进程间存在一块可以直接访问的共享空间，进程可以使用同步互斥工具进行互斥访问、读写。

共享存储分为两种：

1. 低级共享方式：基于数据结构的共享；数据结构受操作系统控制。
2. 高级共享方式：基于存储区的共享；数据形式、存放位置由进程控制。

消息传递

进程间通信的内容是格式化的消息。通过发送消息和接受消息两个原语进行数据交换。

1. 直接通信方式

   发送进程直接把消息直接发送给接受进程，挂到接受进程的消息缓冲队列上。

   图：进程←→进程

2. 间接通信方式

   发送进程把消息发送到某个中间实体（称之为信箱）接受进程从中间实体取得消息。

   该通信方式又称为信箱通信方式。

管道通信

管道：用于连接一个读进程和一个写进程以实现它们之间通信的共享文件，又称pipe文件。

1. 半双工通信

   因此为实现双向同时传输需要设置2个管道。

2. 各进程互斥访问

3. 管道写满，写阻塞，且未满不许读；管道读空，读阻塞，且未空不许写。

4. 读后即弃，阅后即焚。读进程最多只能有一个，防止数据读错的情况。

管道通信需要提供互斥、同步以及确定对方存在。

线程概念和多线程模型

线程概念

线程：基本的CPU执行单元，程序执行的最小单元。

传统进程机制中，进程是资源分配、调度的基本单位。

引入线程后，进程是资源分配的基本单位，线程是调度的基本单位。

线程与进程

表：进程与线程的比较

线程属性

线程拥有线程控制块TCB，同一进程的多个不同内核级线程可以各自独立占用多个CPU从而缩短进程整体的处理时间。

线程在生命周期内也有阻塞态、就绪态和运行态三种基本状态。

同一个系统的进程/线程可以由系统调用的方式被不同的进程/线程多次使用。

线程实现方式

1. 用户级线程

   实现：由应用程序通过线程库实现，对操作系统透明，即操作系统不知道用户级线程的存在。因此操作系统无从对其进行调度。

2. 内核级线程

   实现：线程管理的所有工作由操作系统内核完成

   严谨地说，内核级线程是处理机调度的单位。

3. 多线程模型

   1. 多对一模型

      多个用户级线程映射到一个内核级线程管理。

      优点：开销小，效率高；线程切换不需要CPU变态。

      缺点：单个线程阻塞会导致整个进程阻塞，且多个线程不可在多核上并行运行。

   2. 一对一模型

      一个用户级线程映射到一个内核级线程管理。

      优点：单个线程阻塞，其他线程仍可继续执行，并发能力强。

      缺点：成本高，开销大，线程切换需要CPU变态。

   3. 多对多模型

      n个用户级线程映射到m个内核级线程上，要求m≤n。

      优点：见1与2，同时又克服了1与2的缺点。

处理机调度

作业：用户在一次解题或一个事务处理过程中，要求计算机系统所做工作的集合，包括用户程序所需数据及命令等。

进程同步

死锁