理解操作系统之进程和线程

在操作系统中，设定了进程和线程的概念去描述程序并发执行逻辑。本文属于研究进程和线程的入门级文章。主要从以下五个方面介绍进程以及线程的相关概念。

• 进程和线程的定义
• 操作系统中对进程和线程的描述
• 进程的多层调度
• 进程/线程之间的同步机制
• 进程/线程之间的通信机制
• 如何避免进程和线程之间的死锁

一丶进程和线程的定义

• 进程: 进程是操作系统中定义拥有资源和调度基本单位
• 线程:线程是操作系统中调度的基本单位，线程不能拥有资源，可以看成轻量级的线程。

二丶操作系统中对进程和线程的描述

1. 进程和线程实体描述
进程和线程均是OS中的运行实体，都是调度和分派的基本单位。

• OS定义了PCB(Proccess control block，进程控制块)描述进程实体
• OS定义TCP(Thread control block，线程控制块)描述线程实体
  OS在创建进程/线程的时候必须创建对应的PCB以及TCP。PCB和TCP中存储的内容高低相似，本文仅描述PCB的具体内容，TCP的相关的内容可类比。
  PCB的主要内容:
  (1)进程标识符，主要用于操作系统以及用户定位不同的进程，是进程的唯一标识
  (2)处理机状态，在发生进程切换时保存当前处理器寄存器相关信息。处理机状态信息也用于进程调度时恢复现场信息。
  (3)进程调度信息，主要保存服务进程调度的相同统计值。比如当前进程状态，进程优先级，已执行CPU时间，已等待CPU时间等信息，进程阻塞原因等信息内容。
  (4)进程控制信息：主要保存进程执行相关的信息，比如:(1)程序和数据的内存地址(2) 同步和通信机制(3)进程和线程运行所需要的资源清单

2. 进程和线程的状态描述

进程状态

• 创建状态:进程刚创建的时候的状态，此时操作系统刚给线程分配完PCB等空间
• 就绪状态:进程创建完毕后，获取了除CPU外，需要的所有资源
• 执行状态:处于就绪状态的进程获取了CPU时间片后切换至执行状态。当进程所获时间片消耗完毕后，将切换至就绪状态等待下一次时间片分配。
• 阻塞状态:处于执行状态的进程，发生了某种使进程暂停执行的事件，放弃CPU的执行时间，进入阻塞状态。比如竞争临界资源，等待IO等事件。位于阻塞状态的进程，获取到等待资源后，将进入就绪状态等待CPU分配时间片。
• 销毁状态:进程完成执行逻辑后，进入销毁状态，回收内存以及分配的资源。

三丶进程的多层调度
从硬盘上的可执行文件摇身转为内存中的执行进程涉及到如下两层调度
(1)作业调度:作业调度是将硬盘上执行文件调度到内存中成为进程的过程，经历过该调度的进程处于就绪状态等待分配CPU资源。当有多个作业请求调度时，有许多经典算法可以采用

• 先来先服务算法： 按照作业请求调度的先后顺序执行调度
• 优先级调度算法：每个作业均存在优先级，按照作业的的优先级进行调度
• 短作业有限算法：有限调度执行时间比较短的作业。

(2)进程调度:进程调度是指在就绪队列中排队的就绪进程获取CPU时间片资源的过程。进程调度算法是需要介绍的重点,从较大的方向上分，其主要包括两类:

1. 基于优先权调度的算法，该调度算法主要区分以下四种概念

   • 静态优先权调度:静态优先权是指，该进程所分配的优先权在运行的过程中是不可变化的，从始至终就是初始化的大小。
   • 动态优先权调度:进程调度的优先权可以依据运行时的情况动态改变。比如提高排队时间过长的进程优先权。这样能避免饥饿进程。
   • 抢占式调度:当前执行进程的优先权若小于排队进程进程的优先权，当前执行进程将让出CPU时间，退出执行。
   • 非抢占式调度:当前进程一旦获取了CPU执行时间后，便不会因为优先权的原因让出CPU时间。除非主动结束执行或者遇见异常情况。

2. 基于时间片轮转调度算法
   基于时间片的调度算法将就绪进程排列成一个队列，为队列中每个就绪进程分配指定的时间片资源。若在规定的时间片内进程未执行完毕，那么该进程将再次加入队列的尾部等待下一次时间片资源分配。上述只是基于时间片的调度算法的一般思想，在实际工业场景下过于粗糙。下面介绍一种较为常用的多级反馈队列调度算法具有更大的实用价值

• 多级反馈调度算法:
  image.png

1. 从图中可知，该算法拥有N个用于调度的就绪队列。当进程刚进入就绪状态时时，首先进入1级就绪队列等待CPU分配时间片资源。若未在当前时间片资源内执行完毕，那么进入2级就绪队列。后续调度过程以此类推。
2. 只有1级就绪队列中没有任何进程时，2级就绪队列中的进程才能调度之CPU。
3. 从高级就绪队列中调度到CPU时，会获取更多的时间片资源。TN>T3>T2>T1.

多级反馈调度算法，其优越性一般体现在如下三点:

1. 适用于较短的交互型任务。交互型任务一般只需要较短的执行时间能在1级队列中完成，需要极低的响应延迟
2. 在多级调度的过程中，短作业最多在1-2个时间片轮转中可以调度完成。周转时间任然较短
3. 长作业，可以轮转到高级就绪队列中，这样或许更多CPU执行时间。不至于因为短作业过程，长作业分配不到CPU资源而导致饥饿。

三丶进程/线程之间同步机制

进程与进程之间的同步，线程和线程之间的同步基本一致。本文以线程和线程之间的同步为例子介绍同步概念。

• 线程同步的概念:线程之间并不是孤立的执行，而是有序协作的向前推进执行。
• 经典的进程同步问题:
  1. 消费者与生产者问题
  消费者线程和生产者线程同时访问一个总大小为N的临界资源池。当资源池中资源数目为N时，生产者线程不能往其中添加数据，此时临界资源池记为满状态。当资源池中资源数目为0时，消费者线程不能从资源池中拿去数据，此时临界资源池记为空状态。在这样一个场景下，需要实现三个点:
  - 消费者线程和生产者线程临界资源池的访问是互斥的。
  - 临界资源池在满状态时，生产者线程放入数据操作必须阻塞，等待资源池非满状态时才能继续放入
  - 临界资源池空状态时，消费者线程取数据的操作必须阻塞，等待资源池非空状态时才能继续取出。
  解决方法:互斥锁以及条件变量
  2. 哲学家就餐问题
  哲学家就餐
  从上图可知，五个哲学家们围坐在一个圆桌上，每个哲学家左右两侧都放了一只筷子。当哲学家们想要就就餐时，会试图拿起离自己最近的筷子。一只一只这样拿筷子。当哲学家拿齐一双筷子后，就开始就餐。就餐完毕后将所有筷子放回原处，开始思考哲学。
  那么为什么要构造出这样一个关于哲学家就餐的场景呢？
  主要是构建出一个因为线程同步不当而造成死锁的场景，倘若哲学家门同时拿起来自己左侧的筷子后，当哲学再次试图去拿右侧筷子时，所有哲学家都无法获取就餐机会，陷入僵局。这也是进程同步中的死锁问题。上述哲学家问题中死锁情况存在下述解决方案
  (1) 至多只能允许最多四个哲学家同时去拿同一侧的筷子
  (2) 哲学家同时拿起两只筷子，而不一只只拿。
  可以看出上述解决方法，都是通过设置限制条件，避免死锁情况发生。

3. 读者-写者问题
对于一个文件，存在多个线程同时读取以及多个线程同时写入。在这种条件下要求对文件的访问不能混乱。那么要求读线程和写线程必须满足如下要求:

• 读线程和写线程之间对文件的访问是互斥的
• 写线程之间对文件的访问是互斥的
• 读线程之间对文件的访问不需要互斥
  解决方法: 读写锁

四丶如何避免进程/线程之间的死锁

本节从线程的角度来介绍死锁。线程死锁是线程同步不当导致的问题。本节将从线程死锁原因，线程死锁的必要条件，以及规避线程死锁的三个方面来分析。
1. 线程死锁产生的原因
以哲学家就餐问题，来研究线程死锁原因

• 竞争共享资源：哲学家所需要的筷子就是共享资源。倘若哲学家们存在一双私有的筷子那么变不存在死锁问题。
• 进程间推进顺序不合理: 竞争共享资源并不一会导致死锁。在哲学家就餐问题中，如果能够避免同时拿起同一侧筷子这种运行顺序。那么不会发生死锁。尽管进程之间存在共享资源竞争，但是只要推进顺序合理便能避免死锁。

2. 线程死锁产生的必要条件
死锁发生具有四个必备条件，当能够同时满足这四个条件时，便有可能发生死锁。

• 互斥条件，线程对资源的获取具有排他性，在获取资源的同时独占资源，不允许其他线程访问共享资源
• 请求和保持条件，线程在获取某个资源之后，若再次申请或许新的资源但被阻塞时，并不释放已占有的资源
• 不剥夺条件，线程获取资源之后，不会因为其他线程竞争而放弃资源。只能等到使用完毕或者主动释放
• 环路条件,当线程之间发生死锁的时候，必然存在一个线程->资源之间的环形链路。比如线程P1等到线程P2占用的某个资源，线程P2等待线程P1占用的谋和资源

3. 避免死锁的方法

• 预防死锁:通过破坏死锁产生的必要条件，在预防死锁的发生
• 避免死锁:在对线程分配资源的时候，计算该次资源分配之后线程是否处于安全状态。处于安全状态则分配资源，否则并不分配资源。避免死锁具有代表性的算法便是银行家算法。这是一种非常经典的预防死锁的方法
• 检测和接触死锁:该种方法在进程竞争资源的时候，并不任何预防或者避免死锁的方法。它仅仅提供对死锁的发现机制，在产生死锁之后，通过杀死死锁线程达到接触死锁的目的。

五丶进程/线程之间通信机制

进程/线程之间的同步其实是一种通信机制，但是同步机制只是一种小规模的数据通信。此处介绍的通信机制是应对较大规模的数据传输。此处以进程之间的通信机制为例介绍

• 共享存储系统
  共享存储系统比较容易理解，就是多个进程拥有共同存储空间，通过修改/读取同一块区域达到通信目的。
• 消息传递系统
  消息传递系统是指进程之间通过格式化数据报文交换信息，最容易理解的便是计算机网络数据报文交换。位于不同计算机上应用的通信也是进程通信的一种场景
• 管道通信
  所谓"管道"是指用于连接一个读进程和一个写进程以实现他们之间的通信的一个文件。向管道(共享文件)输入的发送进程，以字符流的形式输入大量数据到管道中，从管道接收输出的接收进程，将读取大量数据。