第二章 进程管理 【期末复习|考研复习】

计算机操作系统系列文章传送门：
第一章 计算机系统概述
第二章 进程管理
第三章 进程同步
第四章 内存管理
第五章 文件管理
第六章 输出输出I/O管理

---

---

前言

给大家整理了一下计算机操作系统中的重点概念，以供大家期末复习和考研复习的时候使用。
参考资料是王道的计算机操作系统和西电的计算机操作系统。

---

二、进程管理

2.1进程的定义，组成，组织方式，特征

引入多道程序（CPU可以并发执行多个程序，失去了封闭性，并且具有间断性和不可再现性）之后，为了方便操作系统进行管理，引入了进程，进程实体的概念，以便更好地的描述和控制程序的并发执行，实现操作系统的并发性和共享性（最基本的两个特性）。
PCB，程序段，数据段三部分构成了进程实体（也叫作进程映像）。一般情况下，我们把进程实体简称为进程。PCB是进程存在的唯一标识。
进程的组织方式分为链接方式和索引方式。链接方式为按照进程状态将PCB分为多个队列。索引方式为根据进程状态不同，建立几张索引表。
进程的特征是动态性（最基本的特征）、并发性、独立性（进程是资源分配、接受调度的基本单位）、异步性、结构性。

2.2 进程的转换

2.3 进程控制

进程控制由原语实现。所谓原语，一般是指由若干条指令组成的程序段，用来实现某个特定功能，在执行过程中不可被中断。原语采用 “关中断指令” 和 “开中断指令” 来实现。 注意： 原语运行在核心态。
进程创建过程：1、申请空白PCB。2、为新进程分配所需资源（若资源不足则处于阻塞态）。3、初始化PCB（包括标志信息、处理器状态信息、处理器控制信息、进程优先级等等）。4、将PCB插入就绪队列。
进程终止过程：1、从PCB集合中找到终止进程PCB。2、若在运行中则立刻剥夺CPU并分配给其他进程。3、终止其所有子进程。4、将其所拥有的资源还给父进程或操作系统。5、从PCB链表中删除其PCB。
进程阻塞过程：1、找到要阻塞的PCB。2、若在运行中则保护现场后转为阻塞态停止运行。3、将PCB插入阻塞队列中，将处理器资源分配给其他就绪进程。
进程唤醒过程：1、在等待队列中找到对应进程PCB。2、将其从阻塞队列中移出，并置其状态为就绪态。3、把PCB插入就绪队列，等待调度程序调度。
进程切换过程：1、保存处理机上下文，包括PC程序计数器和其他寄存器。2、更新PCB信息。3、把进程的PCB移入相应阻塞队列。4、选择另一个进程执行，并更新PCB。5、更新内存管理的数据结构。6、恢复处理及上下文。
进程切换与处理机模式切换不同，模式切换时处理机逻辑上可能在同一进程中运行，若进程因中断或异常进入核心态时，执行完又回到被中断的程序中运行，OS只需要恢复进程进入内核时的CPU现场即可，无需改变当前进程的环境信息。但若要切换进程，则当前进程的环境信息也会变化。“调度”是一种决策行为，“切换”是一种实际分配的执行行为，先有调度后又切换。

2.4进程通信

进程通信就是进程之间的信息交换。因为内存的地址相互独立，为了保证安全，一个进程不能直接访问另一个进程的地址空间。操作系统提供了三种方法：共享存储，消息传递，管道通信。

2.4.1 共享存储

对于共享空间的访问必须是互斥的，通过同步互斥工具来实现（P操作、V操作），低级的共享存储是数据结构的共享，高级的共享存储是基于存储区的共享。允许非血缘关系的进程间使用。

2.4.2 管道通信（pipe文件）

原理：内核使用环形队列机制，借助内核缓冲区（大小为4K）实现。只允许有血缘关系的进程间使用。
1、管道只能采用半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道。2、各进程要互斥地访问管道。3、数据以字符流的形式写入管道，当管道写满时，写进程的write()系统调用将被阻塞，等待读进程将数据取走。当读进程将数据全部取后，管道变空，此时读进程的read()系统调用将被阻塞。4、如果没写满，就不允许读。如果没读空，就不允许写。5、数据一旦被读出，就从管道中被抛弃，这就意味着读进程最多只能有一个，否则可能会有读错数据的情况。

2.4.3 消息传递

进程间的数据交换以格式化的消息为单位。进程通过操作系统提供的“发送消息/接收消息” 两个原语进行数据交换。分为直接通信方式和间接通信方式，直接通信方式直接将消息发送给接收进程，间接通信方式则是发送到某个中间实体（电子邮件系统）。

2.5线程

2.5.1 线程概念

引入进程是更好的使多道程序并发执行，提高资源利用率和系统吞吐量。引入线程使减少程序在并发执行时所付出的时空开销，提高操作系统的并发性能。
线程由线程ID、程序计数器、寄存器集合和堆栈组成。线程是一个基本的CPU执行单元，也是程序执行流的最小单位，线程使进程中的一个实体，是被系统独立调度和分派的基本单位，线程自己不拥有系统资源。线程之间也可以创建和撤销，即相互制约。线程也有就绪、阻塞、运行三种基本状态。
线程共享的资源：1、文件描述符表。2、每种信号的处理方式。3、当前工作目录。4、用户ID和组ID。5、内存地址空间。
线程间非共享资源：1、线程ID。2、处理器现场和栈指针（内核栈）。3、独立的栈空间（用户空间栈）。4、errno变量（errno为全局变量在data段）。5、信号屏蔽字（不同线程对信号的处理）。6、调度优先级。
线程的优点：1、提高程序的并发性。2、开销更小。3、数据间通信共享数据方便。缺点：1、线程为库函数，不稳定。2、调试、编写困难且gbd不支持。3、对信号的支持不好。

进程、程序、线程、作业之间的区别

进程与程序：
1、进程是程序在其数据在计算机上的一次运行活动是一个动态的概念，进程的运行实体是程序，离开了程序的进程没有任何意义。从静态的角度看，进程是由程序数据和进程控制块PCB组成。而程序是一个有序的指令集合是一个静态概念。2、进程是程序一次执行的过程，它是动态的创建和消亡，具有一定的生命周期，是暂时存在的，而程序是一组代码的集合，可以长期保留。3、一个进程可以执行一个或几个程序，一个程序可以构建多个进程。进程可以创建进程，而程序不可能创建新的程序。进程和程序的组成不同，进程的组成包括程序数据和PCB。
作业与进程
进程是系统资源的使用者，系统的资源的大部分都是以进程为单位分配的。而用户使用计算机是为了实现一连串的任务，通常把用户要求计算机完成的这一串任务称为作业。

2.5.2 线程分类

用户级线程由应用程序通过线程库实现。所有的线程管理工作都由应用程序负责（包括线程切换)。用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预。用户级线程对用户不透明，对操作系统透明。
内核级线程的管理工作由操作系统内核完成。线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成。
内核级线程是处理机分配的单位。

2.5.3 多线程模型

多对一模型：多个用户及线程映射到一个内核级线程。每个用户进程只对应一个内核级线程。优点:用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高。缺点:当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。
一对一模型：一个用户级线程映射到一个内核级线程。优点:当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。缺点:一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。
多对多模型：n用户级线程映射到m个内核级线程(n >=m)。每个用户进程对应m个内核级线程。克服了多对一模型并发度不高的缺点，又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点。

2.6 处理器调度的概念及层次

处理机调度就是对处理机进行分配，从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程的并发执行。调度分为三个层次，分别为高级调度，中级调度，初级调度。调度是多道程序的基础，是操作系统设计的核心问题。

2.6.1 高级调度

高级调度也叫作业调度，由于内存空间有限，有时无法将用户提交的作业全部放入内存，因此就需要确定某种规则来决定将作业调入内存的顺序。按一定的原则从外存上处于后备队列的作业中挑选一个(或多个）作业，给他们分配内存等必要资源，并建立相应的进程（建立PCB)，以使它（们）获得竞争处理机的权利。
高级调度面向作业，从外存到内存，从无进程到开辟进程。对于每个作业只调入一次调出一次，只有当作业运行结束才调出，通常几分钟一次。

2.6.2 中级调度

中级调度也叫内存调度，可将暂时不能运行的进程调至外存等待。等它重新具备了运行条件且内存又稍有空闲时，再重新调入内存。这么做的目的是为了提高内存利用率和系统吞吐量。暂时调到外存等待的进程状态为挂起状态。值得注意的是，PCB并不会一起调到外存，而是会常驻内存。PCB中会记录进程数据在外存中的存放位置，进程状态等信息，操作系统通过内存中的PCB来保持对各个进程的监控、管理。被挂起的进程PCB会被放到的挂起队列中。中级调度（内存调度），就是要决定将哪个处于挂起状态的进程重新调入内存。
中级调度面向进程，决定将哪个处于挂起状态的进程重新调入内存，即挂起态到就绪态或者阻塞挂起态到阻塞态。
挂起与阻塞的区别：两个都是暂时不能获取到CPU的服务，挂起态是将进程映像调到外存去了，而阻塞态下的进程映像还在内存中。（进程映像就是进程实体，包括PCB、程序段、数据段）

2.6.3 低级调度

低级调度也叫进程调度，其主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。
进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。

2.6.4 三种调度对比

2.7 进程调度的时机，切换过程和方式

2.7.1 进程调度的时机

临界资源： 一个时间段内只允许一个进程使用的资源。各进程需要互斥的访问临界资源。临界区：访问临界资源的那段代码。内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列。

2.7.2 进程调度的方式

分为非剥夺调度方式和剥夺调度方式。
非剥夺调度方式，又称非抢占方式。即，只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。优点：实现简单,系统开销小但是无法及时处理紧急任务，适合于早期的批处理系统。
剥夺调度方式，又称抢占方式。当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。优点：可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能（通过时钟中断），适合于分时操作系统、实时操作系统。
狭义的进程调度指的是从就绪队列中选中一个要运行的进程，进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。广义的进程调度包含了选择一个进程和进程切换两个步骤。进程切换的过程主要完成了：1、对原来运行进程各种数据的保存。2、对新的进程各种数据的恢复(如:程序计数器、程序状态字、各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块)。

2.8 调度评价标准

等待时间：指进程/作业处于等待处理机状态时间之和。对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待I/O完成的期间其实进程也是在被服务的，所以不计入等待时间。

2.9 调度算法

2.9.1 先来先服务调度算法（FCFS，First Come First Serve）

2.9.2 短作业优先调度算法（SJF，Shortest Job First）

2.9.3 高响应比优先（HRRN，Highest Response Ratio Next）

2.9.4 时间片轮转调度（RR，Round-Robin）

如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。另一方面，进程调度、切换是有时间代价的(保存、恢复运行环境)，因此如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小。一般来说，设计时间片要让切换进程的开销占比不超过1%。

2.9.5 优先级调度算法

可以设置多个就绪队列，或者根据优先级是否可以动态改变分为静态优先级和动态优先级两种。静态优先级创建进程后就不改动，动态优先级有个初始值，之后会动态的进行调整优先级。
系统进程高于用户进程，前台进程高于后台进程，操作系统更偏好I/O型进程（优先让I/O进程运行可以让I/O设备尽早投入工作），以调高资源利用率和系统吞吐量。

2.9.6 多级反馈队列调度算法

优点：短作业优先，对于短批处理作业用户，周转时间较短，长批处理作业用户，经过前面几个队列得到部分执行，不会长期得不到处理。

下一章 第三章 进程同步

第三章 进程同步