【操作系统】进程线程模型（二）

写在前面

• 关于文章
  操作系统中最核心的概念是进程,这是对正在运行程序的一个抽象。也可以说进程是程序的一次执行过程。操作系统的其他所有内容都是围绕着进程的概念展开的,所以,透彻地理解进程是非常重要的。即使可以利用的CPU只有一个,但是通过进程,可以使系统具有支持并发操作的能力,可将一个单独的CPU变换成多个虚拟的CPU。在这里主要学习进程控制块、进程控制、进程同步基础概念、临界资源等。

  • 上一篇文章：【操作系统】进程线程模型（一） - 编程那点事儿 (imyjs.cn)

• 我的站点
  网络云书签-理想 (imyjs.cn)理想智能云解析 (imyjs.cn)

  任务墙 (imyjs.cn)

  LiXiang's Blog (gitee.io) 不再更文

  学编程那点事儿 (imyjs.cn)

• 联系我
  🐧：2410685763WeChat：Super_Baby_00

  公众号：编程那点事儿

进程控制块（PCB）

为了便于系统控制和描述进程的活动过程,在操作系统核心中为进程定义了一个专门的数据结构,称为进程控制块(Process Control Block , PCB)。

PCB内容

• 进程标示符每个进程都必须有一个唯一的标识符：内部标示符or外部标示符
• 处理机状态主要由处理机的各种寄存器中的内容组成。处理机运行时的信息存放在寄存器中，当被中断时这些信息要存放在PCB中。
• 进程调度信息进程状态、进程优先级、进程调度所需的其他信息、事件
• 进程控制信息程序和数据的地址、进程通信和同步机制、资源清单、链接指针

进程的组成

进程由指令,数据和进程控制块三部分组成。PCB是进程的“灵魂”,由于进程控制块中保存有进程的地址信息,通过PCB可以得到进程程序的存储位置,也可以找到整个进程。指令和数据是进程的“躯体”。由于现代操作系统提供指令共享的功能,这就要求该段代码是可再入程序,且与数据分离。
可再入程序是指“纯”代码的程序,由指令组成,即在运行过程中不修改自身。

PCB组织

线性方式

将所有的PCB不分状态组织在一个连续表(称PCB表)中,该方式的优点是简单,且不需要额外的开销,适用于进程数目不多的系统，但缺点是往往需要扫描整个PCB表。

索引方式

对于具有相同状态的进程,分别设置各自的PCB索引表,表目为PCB在 PCB表(线性表)中的地址。于是就构成了就绪索引表和等待索引表。另外,在内存固定单元设置三个指针,分别指示就绪索引表和等待索引表的起始地址以及执行态PCB在PCB表中的地址。

链接方式

对于具有相同状态进程的PCB,通过PCB中的链接字构成一个队列。链接字指出本队列下一PCB在PCB表中的编号(或地址),编号为0表示队尾。队首由内存固定单元中相应的队列指针指示。如此便形成就绪队列和等待队列。

进程的队列

• 就绪队列
  整个系统一个,所有处于就绪状态的进程都按照某种原则排在该队列中。进程入队和出队的次序与处理机调度算法有关。在有些系统中,就绪队列可能有若干个。
• 等待队列
  每一个等待事件一个队列。当进程等待某一事件时,进入与该事件相应的等待队列。当某事件发生时,与该事件相关的一个或多个进程离开相应的等待队列。
• 运行队列
  在单CPU系统中整个系统有一个运行队列。实际上,一个运行队列中只有一个进程,可用一个指针指向该进程。

进程控制

进程有一个从创建到消亡的生命周期,进程控制的作用就是对进程在整个生命周期中各种状态之间的转换进行有效的控制。进程控制是通过原语来实现的。

用于进程控制的原语一般有:创建进程、撤销进程、挂起进程、激活进程、阻塞进程、唤醒进程以及改变进程优先级等。

进程创建原语

一个进程可以使用创建原语创建一个新的进程,前者称为父进程,后者称为子进程,子进程又可以创建新的子进程,构成新的父子关系。从而整个系统可以形成一个树形结构的进程家族。

操作系统发现要求创建新进程的事件后，调用进程创建原语Creat()创建新进程。

创建一个进程的主要任务是建立进程控制块 PCB。具体操作过程是:先申请一空闲PCB区域,将有关信息填入PCB,置该进程为就绪状态,最后把它插人就绪队列中。

进程撤销原语

当一个进程完成任务后,应当撤销它,以便及时释放它所占用的资源。撤销进程的实质是撤销PCB。一旦PCB撤销,进程就消亡了。

具体操作过程是:找到要被撤销进程的PCB,将它从所在队列中消去,撤销属于该进程的一切“子孙进程”,释放被撤销进程所占用的全部资源,并消去被撤销进程的PCB。

进程阻塞原语

某进程执行过程中,需要执行IO操作,则由该进程调用阻塞原语把进程从运行状态转换为阻塞状态。

具体操作过程是:由于进程正处于运行状态,因此首先应中断CPU执行,把CPU的当前状态保存在 PCB的现场信息中,把进程的当前状态置为等待状态,并把它插人到该事件的等待队列中去。

进程唤醒语句

一个进程因为等待事件的发生而处于等待状态,当等待事件完成后,就用唤醒原语将其转换为就绪状态。

具体操作过程是:在等待队列中找到该进程,置进程的当前状态为就绪状态,然后将它从等待队列中撤出并插入到就绪队列中排队，等待调度执行。

UNIX系统中的进程控制

在UNIX类操作系统中,父进程通过调用fork()函数创建子进程。典型的步骤包括:

• (1)为子进程分配一个空闲的proc结构(进程描述符)﹔
• (2)赋予子进程唯一标识pid;
• (3)以一次一页的方式复制父进程用户地址空间;
• (4)获得子进程继承的共享资源的指针,如打开的文件和当前工作目录等;
• (5)子进程就绪,加人调度队列;

• (6)对子进程返回标识符0;向父进程返回子进程的 pid。

以上步骤说明新创建的子进程基本与父进程相同:子进程得到与父进程用户地址空间相同的一份拷贝,包括文本﹑数据和 bss 段、堆以及用户栈;子进程还获得与父进程任何打开文件描述符相同的拷贝,这就意味着当父进程调用fork()函数时,子进程可以读写父进程中打开的任何文件。父进程和新建子进程的区别在于它们有不同的pid。

在UNIX中父进程与子进程的执行是异步的,因此,父进程可能早于子进程结束,如此一来，子进程的资源,例如内存,就有可能无法归还给父进程,引起内存泄漏等问题。wait()函数就是父进程用来获取子进程的结束状态并回收资源的,父进程调用wait()函数自我阻塞,等候子进程结束发来信号,该信号唤醒父进程后由父进程回收子进程的各项资源、清理表格及回收内存等;若子进程先于父进程结束,此时,子进程会暂时变为僵尸状态,继续占有部分资源,直到父进程运行wait()时资源才被回收(此时父进程不需要阻塞)。

如果子进程不等父进程回收,而是在程序末尾直接调用函数exit()退出,那么,在标准UNIX系统上,由于子进程调用了exit() ,会刷新关闭所有标准IО流,包括标准输出。虽然这是由子进程执行的,但却是在父进程的地址空间中进行的,所以所有受到影响的标准I/О对象都是在父进程中的。当父进程再调用标准输出时,标准输出已被关闭了,于是出错返回-1。因此一般子进程不使用exit()函数,而是用内核的_exit()函数,并等待父进程回收。

线程模型

引入背景

在操作系统中引入进程的目的是为了使多个程序并发执行,以改善资源利用率及提高系统效率,那么,在操作系统中再引入线程,则是为了减少程序并发执行时所付出的时间和空间开销,使操作系统具有更好的并发性。

进程具有两个基本属性,即进程是一个可拥有资源的独立单位;同时又是一个可以独立调度和分派的基本单位。正是由于进程具有这两个基本属性,才使之成为一个能独立运行的基本单位,从而也构成了进程并发执行的基础。

然而为使程序能并发执行,系统还必须进行以下的一系列操作:

• (1）创建进程。系统在创建一个进程时,必须为其分配所需的所有资源(除CPU外),包括内存空间、I/О设备以及建立相应的数据结构PCB。
• (2）撤销进程。系统在撤销进程时必须先对这些资源进行回收操作,然后再撤销PCB。
• (3）进程切换。在对进程进行切换时,由于要保留当前进程的CPU环境和设置新选中进程的CPU环境,为此需花费不少CPU时间。

总而言之,由于进程是一个资源拥有者,因而在进程的创建、撤销和切换中,系统必须为之付出较大的时空开销。也正因为如此,在系统中所设置的进程数目不宜过多,进程切换的频率也不宜过高,但这也就限制了并发程度的进一步提高。

如何能使多个程序更好地并发执行,同时又尽量减少系统的开销,可否将进程的上述两个属性分开,由操作系统分开进行处理。即将作为调度和分派的基本单位不同时作为独立分配资源的单位,以使之轻装运行;而对拥有资源的基本单位,又不频繁地对之进行切换。正是在这种思想的指导下,产生了线程的概念。

基本概念

线程是进程中的一个实体,是CPU调度和分派的基本单位。

一个线程可以创建和撤销另一个线程;同一个进程中的多个线程之间可以并发执行。由于线程之间的相互制约,致使线程在运行中也呈现出间断性。相应地,线程也同样有就绪、等待和运行三种基本状态。在有的系统中,线程还有终止状态。

线程属性

• 每个线程有一个唯一的标识符和一张线程描述表,线程描述表记录了线程执行的寄存器和栈等现场状态。
• 不同的线程可以执行相同的程序,即同一个服务程序被不同用户调用时操作系统为它们创建不同的线程。
• 同一进程中的各个线程共享该进程的内存地址空间。
• 线程是处理器的独立调度单位,多个线程是可以并发执行的。在单CPU的计算机系统中,各线程可交替地占用CPU;在多CPU的计算机系统中,各线程可同时占用不同的CPU ,若各个CPU同时为一个进程内的各线程服务则可缩短进程的处理时间。
• 一个线程被创建后便开始了它的生命周期,直至终止,线程在生命周期内会经历等待、就绪和运行等各种状态变化。

线程优点

• 创建一个新线程花费时间少(结束亦如此)。创建线程不需另行分配资源,因而创建线程的速度比创建进程的速度快,且系统的开销也少。
• 两个线程的切换花费时间少。
• 由于同一进程内的线程共享内存和文件,线程之间相互通信无须调用内核,故不需要额外的通信机制,使通信更简便,信息传送速度也快。
• 线程能独立执行,能充分利用和发挥处理器与外围设备并行工作能力。

线程进程比较

线程具有许多传统进程所具有的特征,故又称为轻量级进程(Light-Weight Process)或进程元;而把传统的进程称为重量级进程(Heavy-Weight Process ) ,它相当于只有一个线程的任务。

在引入了线程的操作系统中,通常一个进程都有若干个线程,至少也需要有一个线程。

调度

在传统的操作系统中,拥有资源的基本单位和独立调度、分派的基本单位都是进程。而在引人线程的操作系统中,则把线程作为调度和分派的基本单位,把进程作为资源拥有的基本单位，从而使传统进程的两个属性分开,线程便能轻装运行,这样可以显著地提高系统的并发程度。在同一进程中,线程的切换不会引起进程切换;而在由一个进程中的线程切换到另一进程中的线程时,将会引起进程切换。

并发性

在引入线程的操作系统中,不仅进程之间可以并发执行,而且在一个进程中的多个线程之间也可以并发执行,因而使操作系统具有更好的并发性,能更有效地使用系统资源和提高系统的吞吐量。

拥有资源

不论是传统的操作系统,还是设有线程的操作系统,进程都是拥有资源的一个独立单位,它可以拥有自己的资源。一般地说,线程自己不拥有系统资源(也有一点必不可少的资源),但它可以访问其隶属进程的资源。亦即一个进程的代码段、数据段以及系统资源(如已打开的文件、I/O设备等)。可供同一进程的其他所有线程共享。

系统开销

由于在创建或撤销进程时,系统都要为之分配或回收资源,如内存空间,I/O设备等。因此，操作系统所付出的开销将显著地大于在创建或撤销线程时的开销。类似地,在进行进程切换时,涉及整个当前进程CPU环境的保存以及新被调度运行的进程的CPU环境的设置。而线程切换只需保存和设置少量寄存器的内容,并不涉及存储器管理方面的操作。可见,进程切换的开销也远大于线程切换的开销。

此外,由于同一进程中的多个线程具有相同的地址空间,致使它们之间的同步和通信的实现也变得比较容易。在有的系统中 ,线程的切换、同步和通信都无需操作系统内核的干预。

线程实现机制

用户级线程

用户级线程(User-Level Threads) ,这种线程不依赖于内核。
用户级线程只存在于用户态中,对它的创建、撤销和切换不会通过系统调用来实现,因而这种线程与内核无关。相应地,内核也并不知道有用户级线程的存在,从内核角度考虑,就是按正常的方式管理,即单线程进程。

支持用户级线程的典型操作系统是Linux。
这种方法最明显的优点是,用户级线程包可以在不支持线程的操作系统上实现。过去所有的操作系统都属于这个范围,即使现在也有一些操作系统还是不支持线程。通过这一方法,可以用函数库实现线程。

用户级线程还有另一个优点,即它允许每个进程有自己定制的调度算法。

内核级线程

内核级线程(Kernel-Supported Threads) ,这种线程依赖于内核。
内核级线程依赖于内核,即无论是在用户进程中的线程,还是系统进程中的线程,它们的创建、撤销和切换都由内核实现。在内核中保留了一个线程控制块,系统根据该控制块而感知该线程的存在并对线程进行控制。

支持内核级线程的典型操作系统是Windows。

用户级、内核级线程比较

• 线程的调度与切换速度
  核心级线程的调度和切换与进程的调度和切换十分相似。例如,在线程调度时的调度方式，同样也是采用抢占方式和非抢占方式两种。在线程的调度算法上,也同样可采用时间片轮转法、优先权算法等。当线程调度选中一个线程后,再将处理机分配给它。当然,线程在调度和切换上所花费的开销要比进程小得多。

  用户级线程的切换通常是发生在一个应用进程的诸线程之间,这时,不仅无需通过中断进入操作系统的内核,而且切换的规则也远比进程调度和切换的规则来得简单。例如,当一个线程封锁后会自动切换到下一个具有相同功能的线程。因此,用户级线程的切换速度特别快。

• 系统调用
  当传统的用户进程调用一个系统调用时,要由用户状态转入核心状态,用户进程将被封锁。当内核完成系统调用而返回时,才将该进程唤醒,继续执行。

  在用户级线程调用一个系统调用时,由于内核并不知道有该用户级线程的存在,因而把系统调用看作是整个进程的行为,于是使该进程等待,而调度另一个进程执行。

  而在内核完成系统调用而返回的,进程才能继续执行。如果系统中设置的是内核支持线程,则调度是以线程为单位。当一个线程调用一个系统调用时,内核把系统调用只看作是该线程的行为,因而封锁该线程,于是可以再调度该进程中的其他线程执行。

• 线程执行时间
  对于只设置了用户级线程的系统,调度是以进程为单位进行的。在采用轮转调度算法时,各个进程轮流执行一个时间片,这对诸进程而言似乎是公平的。

  假如在进程A中包含了一个用户级线程,而在另一个进程B中含有100个线程,这样,进程A中线程的运行时间,将是进程B中各线程运行时间的100倍;相应地,进程A的运行速度比进程B的运行速度快100倍。

  假如系统中设置的是核心级线程,其调度是以线程为单位进行的,这样,进程B可以获得的CPU时间是进程A的100倍,进程B可使100个系统调用并发工作。

混合实现方式

内核只识别内核级线程,并对其进行调度。其中一些内核级线程会被多个用户级线程多路复用。如同在没有多线程能力操作系统中某个进程中的用户级线程一样,可以创建,撤销和调度这些用户级线程。在这种模型中,每个内核级线程有一个可以轮流使用的用户级线程集合。

进程（线程）调度

调度是分层次的,操作系统中,一般将调度分为高级调度、中级调度和低级调度。

• 高级调度也称作业调度,其主要任务是按一定的原则,对磁盘中处于后备状态的作业进行选择并创建为进程;
• 中级调度的主要任务是按照给定的原则和策略,将处于磁盘对换区中且具备运行条件的就绪进程调人内存,或将处于内存就绪状态或内存阻塞状态的进程交换到对换区;
• 低级调度即进程(线程)调度,是决定就绪队列中哪个进程将获得处理机,并实际将处理机分配给该进程的操作。

主要功能

记录系统中所有进程(线程)的执行状况;根据一定的调度算法,从就绪队列中选出一个进程(线程)来,准备把CPU分配给它;把CPU分配给进程(线程),即把选中进程(线程)的进程(线程)控制块内有关的现场信息,如程序状态字、通用寄存器等内容送入处理器相应的寄存器中,从而让它占用CPU运行。

调度时机

执行进程调度一般是在下述情况下发生的:

• 正在执行的进程(线程)运行完毕;
• 正在执行的进程(线程)调用阻塞原语将自己阻塞起来进入等待状态;
• 正在执行的进程(线程)调用了阻塞原语操作,并且因为资源不足而被阻塞;或调用了唤醒原语操作激活了等待资源的进程(线程);
• 时间片用完;

以上都是在CPU为不可抢占方式下的引起进程调度的原因。在CPU方式是可抢占方式时,还有下面的原因:

• 就绪队列中的某个进程(线程)的优先级高于当前运行进程(线程)的优先级时,引发进程(线程)调度。

调度算法

先来先服务

在所有调度算法中,最简单的是非抢占式的先来先服务(First-Come First-Severed , FCFS)算法。使用该算法,进程按照它们请求CPU的顺序使用CPU。

基本上,有一个就绪进程的单一队列。早上,当第一个作业从外部进入系统,就立即开始并允许运行它所期望的时间。不会中断该作业,因为它需要很长的时间运行。当其他作业进入时,它们就被安排到队列的尾部。当正在运行的进程被阻塞时,队列中的第一个进程就接着运行。在被阻塞的进程变为就绪时,就像一个新来到的作业一样,排到队列的末尾。

这个算法的主要优点是易于理解并且便于在程序中运用。

最短作业优先

适用于运行时可以预知的另一个非抢占式的批处理调度算法。

有必要指出,只有在所有的作业都同时可运行的情形下,最短作业优先算法才是最优化的。

最短剩余时间优先

最短作业优先的抢占式版本是最短剩余时间优先( Shortest Remaining Time Next , SRTN)算法。使用这个算法,调度程序总是选择其剩余运行时间最短的那个进程运行。

再次提醒,有关的运行时间必须提前掌握。当一个新的作业到达时,其整个时间同当前进程的剩余时间做比较。如果新的进程比当前运行进程需要更少的时间,当前进程就被挂起,而运行新的进程。

这种方式可以使新的短作业获得良好的服务。

最高响应比优先算法

在批处理系统中,最高响应比优先算法(Highest Response Rate First ,HRRF)的性能是介于先来先服务和最短作业优先算法之间的折中算法。

• 先来先服务算法在调度中最为公平,但是一旦出现计算密集型的长作业则会对其他进程造成较长时间的等待;
• 最短作业优先算法又偏好短作业,当短作业源源不断进入后备池时,长作业将会长时间滞留在后备池中,其运行将得不到保证，出现这种现象我们称为长作业处于“饥饿( starvation)”。

响应比的计算式为:
响应比 Rp=(等待时间+预计运行时间)/预计运行时间=周转时间/预计运行时间
每个作业随着在后备池等待时间的增长其响应比也不断增长,而且,预计运行时间越短的作业响应比增长越快。

最高响应比优先算法在每次调度时选择响应比最高的作业投入运行,这种算法较好地适应了长短作业混合的系统,使得调度的性能指标趋于合理。

最高响应比优先算法在一定程度上改善了调度的公平性和调度的效率,响应比在每次调度前进行计算,作业运行期间不计算。计算需要消耗系统的资源,存在一定的系统开销。

轮转法

轮转(Round-Robin,RR)算法最早来自分时系统。

轮转法的基本思想是：

将CPU的处理时间划分成一个个时间片,就绪队列中的诸进程轮流运行一个时间片。当时间片结束时,就强迫运行进程让出CPU,该进程进入就绪队列,等待下一次调度。同时,进程调度又去选择就绪队列中的一个进程,分配给它一个时间片,以投入运行。如此轮流调度,使得就绪队列中的所有进程在一个有限的时间T内都可以依次轮流获得一个时间片的处理机时间,从而满足了系统对用户分时响应的要求。

在轮转法中,时间片Q长度的选取非常重要,将直接影响系统开销和响应时间。

• 如果时间片长度很小,则调度程序剥夺处理机的次数频繁,加重系统开销;
• 如果时间片长度选择过长,比方说一个时间片就能保证就绪队列中所有进程都执行完毕,则轮转法就退化成先进先出算法,

下面是影响时间片值设置的几个主要因素:

• (1)系统响应时间:当进程数目一定时,时间片Q值的大小正比于系统对响应时间的要求，例如进程数目为N ,要求的响应时间为T,则Q=T/N,Q值随T值的大或小而大或小;
• (2)就绪进程的数目:当系统响应时间T一定时,时间片Q值的大小反比于就绪进程数;
• (3)计算机的处理能力:计算机的处理能力直接决定了每道程序的处理时间,显然,处理速度越高,时间片值就可以越小。

可以归结如下结论:

最高优先级算法

最高优先级(Highest Priority First , HPF)进程(线程)调度每次将处理机分配给具有最高优先级的就绪进程(线程)。进程(线程)的优先级由进程(线程)优先数决定。进程(线程)优先数的设置可以是静态的,也可以是动态的。

• 静态优先数是在进程(线程)创建时根据进程(线程)初始特性或用户要求而确定的,在进程(线程)运行期间不能再改变。
• 动态优先数则是指在进程(线程)创建时先确定一个初始优先数,以后在进程(线程)运行中随着进程(线程)特性的改变(如等待时间增长) ,不断修改优先数。在有的系统中,优先数小的进程(线程)优先级高。

最高优先级算法还可以和不同的CPU调度方式结合起来,从而形成可抢占式最高优先级算法和不可抢占式最高优先级算法。显然,抢占式算法更好地反映了优先级的特征,可以使高优先级进程尽可能快地完成其任务的目标,从而获得了较好的服务质量。但是抢占式算法无疑也增加了系统的开销。

多级反馈队列算法

在实际的计算机系统中,进程(线程)的调度模式往往是几种调度算法的结合。例如：

• 可以以最高优先级算法作为主要的调度模式,但对于具有相同优先数的进程(线程)则按先进先出调度算法处理。
• 可以将时间片轮转算法和最高优先级算法结合,对于具有相同优先数的进程(线程)按时间片轮转调度算法处理。

多级队列反馈法就是综合了先进先出调度算法、时间片轮转算法和可抢占式最高优先级算法的一种进程(线程)调度算法。

最短进程优先

对于批处理系统而言,由于最短作业优先常常伴随着最短响应时间,所以如果能够把它用于交互进程,那将是非常好的。交互进程通常遵循下列模式:等待命令,执行命令,等待命令,执行命令,如此不断反复。如果将每一条命令的执行看作是一个独立的“作业”,则可以通过首先运行最短的作业来使响应时间最短。

微信关注

WeChat