1。什么是流程？进程是正在运行的程序的实例。程序启动时，程序从磁盘读入内存，CPU从内存中读取指令，译码，执行指令（如两个数相加，访问内存，检查条件，跳转函数等）。完成这条指令后，CPU继续重复上述操作。这样，CPU就可以一对一地读取和执行进程的指令。我们把操作系统抽象成一个概念，称之为任务。一个进程可以对应一个任务，也可以对应多个任务。早期的计算机只有一个CPU，如果需要运行多个任务怎么办？需要一个一个排队等待，串行执行。一个任务执行完后，就可以执行下一个任务了。这种方法有明显的缺点。假设前排的任务A执行需要5个小时，后排的任务B只需要1分钟，那么任务B必须等待任务A完成5个小时才能执行。这种方法显得极其死板。后来就有了多任务系统。在CPU一次只能处理一个任务的前提下，每个任务都有一定的执行时间。比如任务A执行0.001s，切换到任务B0.05s，再切换到任务C，执行0.01s...不断循环。这种机制在一定程度上也可以解决上述任务B需要等待较长时间的问题。由于CPU速度很快，多个任务的不断切换会给用户一种任务是并行执行的错觉，也称为伪并行调度。既然有伪并行，就会有真并行。在现代计算机中，常见的CPU核心数可以达到8核甚至更多，而操作系统可以把每个核心都当作一个CPU，所以8核CPU可以真正并行执行8个任务。还有一种，就是一台电脑有多个CPU。至于多CPU和多核的区别，有兴趣的读者可以参考多核CPU和多CPU的区别是什么？.那么我们继续基于伪并行进一步探索。虽然伪并行可以解决上面的任务等待问题，但是还有一系列未解之谜：每个任务应该执行多长时间？我如何找到下一个要执行的任务？一些任务涉及资源操作。执行到一半，任务被切换。这些资源呢？...为了解决上述一系列难题，我们需要一个详细描述任务的模型。一个进程可以对应一个任务，也可以对应多个任务。目前不涉及多线程。我们可以先把流程和任务看成是一对一的关系（这不是为了理解而创建的，暂时错误的假设）。下面我们将进一步探讨有关该过程的更多细节，这将有助于解释上述问题。2.进程模型2.1PCB对于一个被执行的程序，操作系统会为该程序创建一个进程。作为一个抽象的概念，进程可以看作是一个容器，里面汇集了相关的资源，包括地址空间、线程、打开的文件、保护权限等。操作系统本身就是一个程序。有一句经典的话，程序=算法+数据结构。因此，对于单个进程，可以基于数据结构来表示。这种数据结构称为进程控制块（PCB）。教科书也称其为时间表。根据不同的操作系统，PCB包含的信息不同，一般都会包含这些信息（图片来自《现代操作系统》）。2.2进程状态那么是什么原因导致创建进程产生PCB呢？有几种常见的系统初始化类型。用户通过系统提供的API创建一个新的进程。批处理作业初始化（什么是批处理作业）从现有进程派生子进程。如果由于某种原因创建了一个进程，它可以按照以下步骤进行一系列的初始化，为新进程分配一个进程ID，分配内存空间，初始化PCB，进入就绪队列。2.2.1五态模型如图所示。当进入就绪队列时，它的状态就会变为就绪。各个状态之间的关系描述如下：Ready->Running：当操作系统中有一个调度器，当需要运行一个新的进程时，调度器选择一个处于就绪状态的进程，让其进入运行状态.Running->Ready：正在运行的进程会占用CPU（参考最开始的饼图）。每个进程都会被分配一定的执行时间，当时间结束后，又会回到就绪状态。Running->Blocking：进程请求调用系统的一些服务，但是操作系统不能立即给它（比如这样的服务可能需要时间初始化，比如I/O资源需要等待），那么它就会进入阻塞状态。Blocking->Ready：当等待结束后，从阻塞状态进入就绪状态。Run->Terminate：当一个进程指示它完成时，它被操作系统终止。这是单个进程的经典五态模型。当有多个进程时，由于同时只能执行一个进程，那么如何管理这一系列处于阻塞态和就绪态的进程呢？一般来说，就绪队列和阻塞队列是用来让处于阻塞状态和就绪状态的进程进入队列和执行队列。下图是单阻塞队列模型。基于此，还可以扩展多个就绪队列，每个优先级对应一个队列，这样子操作系统在选择调度哪个进程时可以有更大的灵活性。下面将进一步探讨如何组织和管理队列和进程。也可以有多个阻塞队列，每个事件对应一个阻塞队列。当事件发生时，队列中的所有进程进入就绪状态。2.2.2七态模型上面提到的进程状态有一个前提：每个进程都必须完全加载到内存中。一旦排队的进程多了，对有限的内存空间是一个很大的考验。为了解决内存使用问题，可以将内存中的一些进程交换到磁盘上。这些交换到磁盘的进程会进入挂起状态，挂起状态又可以细分为就绪/挂起、阻塞/挂起。单个进程的状态转换如下图所示。总的来说，pendingqueue的转换关系如下图所示。图中的几个时间表将在下面的第4章中进一步描述。2.2.3进程切换当一个正在运行的进程被中断时，操作系统指定另一个处于就绪状态的进程进入运行状态。这个过程就是进程切换，也叫上下文切换。切换过程一般包括以下几个步骤：1.保存处理器上下文：将CPU程序计数器和寄存器的值保存到当前进程的私有栈中2.更新当前进程的PCB（包括状态changes)3.保存当前进程移至就绪队列或阻塞队列4.根据调度算法，在就绪队列中选择一个合适的新进程，使其变为运行状态5.更新内存管理的数据结构6.在新进程中加载??保存在栈中的上下文信息进入CPU的寄存器和程序计数器，占用CPU2.3的进程组织每个PCB代表一个进程，当多个进程同时存在时，需要以某种方式组织这些PCB，以便于操作系统访问。存在三种常见的组织方式。2.3.1线性表所有PCB都存储在一个线性表中，每次查找都需要遍历线性表。比较适合进程不多的情况。如果有数百个或数千个进程，遍历每个操作将非常耗时。2.3.2链表上面提到的就绪队列和阻塞队列都可以用链表的形式来组织。从图中可以看出就绪队列指向PCB1，PCB1右边的数字“2”表示链表指向的下一个节点PCB2。以此类推，PBC以如下链表的形式串联起来。执行指针->PCB4就绪队列指针->PCB1->PCB2->PCB3->PCB5阻塞队列指针->PCB7->PCB8->PCB6优点：非常直观，方便查找进程调度。缺点：查找的时候需要从链表的头部开始遍历。如果进程的状态发生变化，链表中指向进程节点的指针也需要改变。2.3.3索引优势：基于链表进一步优化，通过索引查找过程，查找的时间复杂度可以从O(n)优化到O(1)。如果进程状态发生变化，只需要操作索引表，比操作整个链表方便。缺点：建立索引表，需要额外的内存空间。相当于用空间来交换时间。3.线程3.1线程结构根据前面的描述，进程有两个特征：资源所有权：进程是一个容器，它聚集了内存、I/O设备和文件等资源，并且对这些资源具有控制权或所有权。调度/执行：它有一个执行状态（运行、就绪、阻塞等），可以被操作系统的调度器调度。在早期的操作系统中，一个进程中一般只有一个线程，属于单线程进程模型。如下图所示，其中包含的用户栈和内核栈用于管理调度和返回的行为。当进程没有运行时，CPU的寄存器的内容会被保存下来，以便下次运行进程时恢复当前状态。那么为什么需要多线程呢？很多应用程序有多个活动同时发生，其中一些活动会被阻塞，进一步将进程分解为多个线程可以更灵活地处理各种类型的活动。线程更轻量级，创建和终止更快，线程之间的切换会比进程切换更快。对于一些I/O密集型任务，多线程可以让这些任务并行执行，从而加快整体速度。多线程对于CPU密集型任务没有这个优势，因为本质上CPU一次只做一件事（什么是CPU密集型，I/O密集型？）。线程间通信比进程间通信更有效。一般进程间通信需要内核介入，同一进程内的线程共享进程的内存和文件，无需调用内核即可实现通信。上图展示了一个多线程的进程模型，其中线程控制块也称为TCB（ThreadControlBlock）。对于进程来说，进程=线程+资源。一开始我们提到，操作系统底层有一个调度器，可以调度任务，单线程进程，每个进程可以对应一个任务。现在，对于一个多线程进程来说，每个线程最终都是调度器的一个任务，如下图（Linux系统）。因此，也流行一种说法，线程是CPU调度的基本单位3.2线程状态类似于进程状态模型，线程的状态也有new、running、ready、blocked、terminated。与进程状态类似，线程终止时进入终止状态。但是与进程不同的是，当一个进程终止时，它里面的所有线程都会被终止。由于线程之间的并行关系，如果一个线程在同一个进程中被阻塞，不会影响到其他线程。4.进程调度处理器调度按相对时间长短可分为远程调度、中程调度和短程调度。（普通调度也包括I/O调度，但不包括处理器调度）。几种调度与进程状态转移的关系如图4.1几种调度方法4.1.1远程调度远程调度也称为高级调度、作业调度。它控制系统的并发性，决定哪个批处理作业或用户程序可以进入系统进行处理。一旦运行，批处理作业或用户程序将成为一个进程并进入就绪队列。4.1.2中程调度中程调度也称为交换调度、中间调度。核心思想是将进程从内存或CPU竞争中移除，然后进程可以调回内存。这样就可以控制内存中的进程数。如图所示，从就绪队列挂起的进程进入就绪挂起队列，从阻塞队列挂起的进程进入阻塞挂起队列。当就绪挂起队列中的进程被激活后，进入就绪队列。4.1.3短程调度短程调度也称为低级调度。大多数时候，进程调度指的是短程调度。短程调度将就绪队列中的进程调度到CPU执行。其中，CPU按照一定的策略分配给处于就绪状态的进程，分为抢占式调度和非抢占式调度。非抢占式调度：非抢占式调度就是选择一个进程，并为它分配CPU。进程一直运行到终止或因等待事件而进入阻塞状态（图中红色标记）。显然，这种调度方式有一个缺陷：如果正在运行的进程需要运行很长时间，后面的进程只能等到它结束或者阻塞。抢占式调度：抢占式调度就是让进程执行到一半就停止，把CPU分配给其他进程。4.2进程调度算法常见的进程调度算法有：先来先服务、时间片轮转、最短作业优先级、最短剩余时间优先级、优先级调度、多级反馈队列调度，限于篇幅，本文仅供参考对各个调度算法做了简单的介绍，想了解更多的可以参考上篇参考。4.2.1先到先得（FirstComeFirstServerd，FCFS）。高级就绪队列先被调度，先来先服务是最简单的调度算法。先来先服务存在上面讨论的问题：当前面的任务执行时间很长时，即使后面的任务只需要执行很短的时间，也必须一直等待下去。属于非抢占式4.2.2时间片轮转调度时间片轮转调度，即上面第一章介绍的方法。每个进程都会被分配一个时间片，也就是说允许进程在这个时间段内运行。如果时间到了，进程还没有运行完，会通过抢占式调度的方式将CPU分配给其他进程，进程回到就绪队列。这是最简单、最公平的调度算法，但也可能存在问题。由于进程的切换，需要时间。如果时间片太短，频繁切换会影响效率。如果进程时间片过长，可能会导致队列后面的进程等待时间过长。因此，时间片的长度需要有一个大致合理的值。（《现代操作系统》的观点是建议时间片长度为20ms~50ms）。4.2.3最短作业优先最短作业优先（ShortestJobFirst，SJF），顾名思义，进程按照作业时间的长短排队，作业时隙最前面的先执行，如图下图。4.2.4最短剩余时间优先最短剩余时间优先（ShortestRemainingTimeNext），从就绪队列中选择剩余时间最短的进程进行调度。该算法理解最短作业优先和时间片循环法的组合。如果没有时间片，那么最短的剩余时间实际上就是最短的作业时间，因为每个进程都是从头到尾执行的。4.2.5优先级调度假设就绪队列中有如下进程。进程执行时间优先级p151p223p332根据优先级进行调度，执行顺序为p1->p3->p2。如果多个进程具有相同的优先级，它们将按照先到先得的原则依次执行。优先级调度可以进一步细分为抢占式和非抢占式。非抢占式：和上面说的非抢占式类似，一旦进程占用了CPU，就会继续执行，直到结束或者block。抢占式：在进程执行过程中，一旦有更高优先级的进程进入就绪队列，该进程就会被挂起并返回到就绪队列中，让更高优先级的进程执行。但是为了不让最高优先级的进程一直运行，每个进程还是有自己的时间片。每个时间片结束后，进程的优先级会按照一定的规则降低，避免一些优先级最高的longjob进程一直占用CPU。4.2.6多级反馈队列调度多级反馈队列调度是基于时间片轮换和优先级调度的。设置多个就绪队列，每个就绪队列分配一个优先级。优先级越高，排队进程的时间片越短。如下图所示，1级就绪队列的优先级最高，进程的时间片长度最短，其次是2级就绪队列，依次类推。当一个新进程创建时，首先进入一级就绪队列，如果在时间片结束前运行完毕则终止，否则进入二级队列等待下一次调度。在n级队列之前，按照先到先得的规则顺序调度进程，在调度n级队列（最后一级）时，采用时间片轮询调度。只有当一级队列为空时，才会调度二级队列的进程。如果第i级队列的进程正在运行，此时有更高优先级的进程进入，则停止第i级进程，让它回到第i级队列的尾部，转而执行更高优先级的进程-优先进程，满足优先调度算法的原则。5、进程间通信进程间通信的目的一般包括共享数据、数据传输、消息通知、进程控制等。以Unix/Linux为例，介绍几种重要的进程间通信方式：共享内存、pipeline,message,sharedmemory,semaphore,signal5.1共享内存多个进程可以读写同一块内存区域，这是最高效的进程通信方式。由于多个进程可以读写内存，因此需要一定的同步机制来保证数据读写的安全。关于这个机制，要花很多篇幅。这里读者可以根据文末提供的参考资料进行查看。笔者后续会另行专门介绍。5.2Pipeline首先简单介绍一下什么是生产者/消费者问题。一个或多个生产者生产一些数据，放入共享缓冲区，消费者从缓冲区中取出数据。同一个缓冲区只允许生产者或消费者同时访问，不能同时访问。当缓冲区满时，生产者不再向其中添加数据，当缓冲区为空时，消费者不再从中读取数据。管道是基于生产者/消费者模型来实现通信的。最基本的管道通信由一端的读进程、管道和另一端的写进程组成。通信介质是共享文件，也称为管道文件。管道分为匿名管道和命名管道，这里主要介绍命名管道。管道有一个特点：一旦数据被读取，它就会从管道中删除，以腾出空间来写入更多的数据。如下图所示，如果需要双端通信，则需要两条管道，如下图所示。这里需要注意一下：第二张图是半双工通信，即虽然可以双向通信，但同时只能在一个方向上传输。pipeline可以理解为一种优化的共享存储方式（磁盘存储而不是内存存储），保证同一个buffer中的数据只能写入一端，另一端读取，不能同时写入多端同一时间。5.3Signals信号一般用于一些异常情况下的进程间通信。它是一种异步通信。它的数据结构一般是一个数字。例如，Unix提供了以下信号（来自《操作系统精髓与设计原理》6thEdition第6.7.5章）值名称说明01SIGHUB阻塞：当内核认为进程正在做无用工作时发送给进程02SIGINT中断03SIGQUIT停止：由进程发送用户，导致进程停止并产生信息转储进程需要对信号设置相应的监听处理，当接收到特定信号时，执行相应的操作，类似于很多编程语言中的通知机制。5.4消息消息可以用作在两个不相关的进程之间传输数据的一种方式。至少一对原语由send(destination,message)receive(source,message)组成什么是原语：由几条指令组成的程序段，用来执行特定的动作。消息通信可分为直接通信和间接通信。直接通信：发送进程直接向接收进程发送消息，将消息挂在接收进程的消息队列中，接收进程从消息队列中获取消息，是一对一的通信关系。间接通信：消息不是直接发送给接收者，而是发送给一个共享的数据结构，即消息队列，也称为邮箱。这种方式比直接通信更加灵活，可以一对一，一对多，多对一，多对多。进程的标识由消息格式中指定的id确保。下面是一个常见的消息数据格式（来自《操作系统精髓与设计原理》5.5.3）。消息按照先进先出的原则进入消息队列。如果有紧急消息，发送方可以指定消息的类型，接收方在查询消息队列时可以根据消息类型读取，不一定按照先进先出的顺序。与管道相比，消息有以下区别：在传输上，管道基于字节流，而消息基于格式化文本。介质上的管道是文件，消息是内存管道，只能按照先进先出的顺序，而消息不一定。可以根据消息类型有选择地接收和处理，更加灵活。5.5信号量信号量本质上是一个计数器。当多个进程共享内存时，用于保护共享内存，保证同一时间只有一个进程独占使用共享内存。信号量需要初始化为某个值。当进程访问共享内存时，信号量减1。如果信号量值不为负，则访问共享内存。当此时新进程也想访问共享内存时，信号量又减一。如果信号量的值为负，则新进程被阻塞并等待。6.小结进程是操作系统最重要的概念之一。可以介绍的细节比较多，每个点都可以横向纵向展开。笔者阅读了大部分主流操作系统书籍中关于进程管理的章节，对本文的介绍进行了总结。其中，用户进程、内核进程、调度算法评价指标、进程和内存管理等，限于篇幅，这里不再赘述。.同步、并发、锁等相对复杂和重要的部分，计划在后面单独的章节单独讲述。谢谢阅读。7.参考资料Linux操作系统趣谈操作系统：本质与设计原理（原书第6版）操作系统概论现代操作系统（第3版）2019操作系统研究生复习指导操作系统概念Linux内核设计与实现操作SystemTruthRestoration深入理解计算机系统操作系统原理理解User和KernelMode操作系统CPU（处理器）调度优先级调度算法及其优缺点进程间通信IPC
