2. 进程
2.1 进程概念
进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动,它是系统进行资源分配的一个独立单位。例如,用户运行自己的程序,系统就创建一个进程,并为它分配资源,包括各种表格、内存空间、磁盘空间、I/O设备等,然后该进程被放入到进程的就绪队列,进程调度程序选中它,为它分配CPU及其他相关资源,该进程就被运行起来。
2.2 进程特征与基本状态
2.2.1 特征
1:动态性,2:并发性,3:独立性,4:异步性。
2.2.2. 状态以及切换
1、就绪状态;
2、执行状态;
3、阻塞状态
基本状态的切换:
- 处于就绪状态的进程,在调度程序为之分配了处理机之后便开始执行, 就绪 -> 执行
- 正在执行的进程如果因为分配他的时间片已经用完,而被剥夺处理机, 执行 -> 就绪
- 运行进程因某事件致使当前的进程执行受阻,使之不能执行,如资源被占用、I/O未完成。 执行 -> 阻塞
- 当所等待的事件发生时,如得到申请资源、I/O传输完成 ,阻塞 -> 就绪
创建状态和终止状态图:
2.3 进程的组成
进程是操作系统的资源分配和独立运行的基本单位。它一般由以下三个部分组成。
2.3.1 进程控制块
进程控制块(Processing Control Block),是操作系统核心中一种数据结构,主要表示进程状态。其作用是使一个在多道程序环境下不能独立运行的程序(含数据),成为一个能独立运行的基本单位或与其它进程并发执行的进程。
PCB的作用
- 作为独立运行基本单位的标志
- 能实现间断性运行方式
- 提供进程通信管理所需要的信息
- 提供进程调度所需要的信息
2.3.2 程序段
程序段就是能被进程调度程序调度到CPU执行的程序代码段。注意,程序可以被多个进程共享,就是说多个进程可以运行同一个程序。
2.3.3 数据段
一个进程的数据段,可以是进程对应的程序加工处理的原始数据,也可以是程序执行时产生的中间或最终结果。
2.4 进程通信(同步)
进程间通信(IPC,Interprocess communication)是一组编程接口,让程序员能够协调不同的程序进程,使之能在一个操作系统里同时运行。
linux下进程间通信的几种主要手段简介:
- 管道(Pipe)及有名管道(named pipe):管道可用于具有亲缘关系进程间的通信,有名管道克服了管道没有名字的限制,因此,除具有管道所具有的功能外,它还允许无亲缘关系进程间的通信;
- 信号(Signal):信号是比较复杂的通信方式,用于通知接受进程有某种事件发生,除了用于进程间通信外,进程还可以发送信号给进程本身;linux除了支持Unix早期信号语义函数sigal外,还支持语义符合Posix.1标准的信号函数sigaction(实际上,该函数是基于BSD的,BSD为了实现可靠信号机制,又能够统一对外接口,用sigaction函数重新实现了signal函数);
- Message(消息队列):消息队列是消息的链接表,包括Posix消息队列system V消息队列。有足够权限的进程可以向队列中添加消息,被赋予读权限的进程则可以读走队列中的消息。消息队列克服了信号承载信息量少,管道只能承载无格式字节流以及缓冲区大小受限等缺点。
- 共享内存:使得多个进程可以访问同一块内存空间,是最快的可用IPC形式。是针对其他通信机制运行效率较低而设计的。往往与其它通信机制,如信号量结合使用,来达到进程间的同步及互斥。
- 信号量(semaphore):主要作为进程间以及同一进程不同线程之间的同步手段。
- 套接口(Socket):更为一般的进程间通信机制,可用于不同机器之间的进程间通信。起初是由Unix系统的BSD分支开发出来的,但现在一般可以移植到其它类Unix系统上:Linux和System V的变种都支持套接字。
2.5 进程同步与互斥
2.5.1 进程同步
进程同步也是进程之间直接的制约关系,是为完成某种任务而建立的两个或多个进程,这个进程需要在某些位置上协调他们的工作次序而等待、传递信息所产生的制约关系。进程间的直接制约关系来源于他们之间的合作。
比如说进程A需要从缓冲区读取进程B产生的信息,当缓冲区为空时,进程B因为读取不到信息而被阻塞。而当进程A产生信息放入缓冲区时,进程B才会被唤醒。概念如图1所示。
上面这个模型也就是生产者消费者模型:
在实际的软件开发过程中,经常会碰到如下场景:某个模块负责产生数据,这些数据由另一个模块来负责处理(此处的模块是广义的,可以是类、函数、线程、进程等)。产生数据的模块,就形象地称为生产者;而处理数据的模块,就称为消费者。
单单抽象出生产者和消费者,还够不上是生产者/消费者模式。该模式还需要有一个缓冲区处于生产者和消费者之间,作为一个中介。生产者把数据放入缓冲区,而消费者从缓冲区取出数据。大概的结构如下图。
优点:
- 解耦:假设生产者和消费者分别是两个类。如果让生产者直接调用消费者的某个方法,那么生产者对于消费者就会产生依赖(也就是耦合)。将来如果消费者的代码发生变化,可能会影响到生产者。而如果两者都依赖于某个缓冲区,两者之间不直接依赖,耦合也就相应降低了。
- 支持并发:生产者直接调用消费者的某个方法,还有另一个弊端。由于函数调用是同步的(或者叫阻塞的),在消费者的方法没有返回之前,生产者只好一直等在那边。
- 支持忙闲不均:缓冲区还有另一个好处。如果制造数据的速度时快时慢,缓冲区的好处就体现出来了。当数据制造快的时候,消费者来不及处理,未处理的数据可以暂时存在缓冲区中。等生产者的制造速度慢下来,消费者再慢慢处理掉。
可以利用信号量来解决生产者和消费者问题:
信号量(semaphore)的数据结构为一个值和一个指针,指针指向等待该信号量的下一个进程。信号量的值与相应资源的使用情况有关。当它的值大于0时,表示当前可用资源的数量;当它的值小于0时,其绝对值表示等待使用该资源的进程个数。注意,信号量的值仅能由PV操作来改变。
执行一次P操作意味着请求分配一个单位资源,因此S的值减1;当S<0时,表示已经没有可用资源,请求者必须等待别的进程释放该类资源,它才能运行下去。而执行一个V操作意味着释放一个单位资源,因此S的值加1;
2.5.2 临界资源
虽然多个进程可以共享系统中的各种资源,但其中许多资源一次只能为一个进程所使用,我们把一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源,如打印机等。此外,还有许多变量、数据等都可以被若干进程共享,也属于临界资源。
对临界资源的访问,必须互斥地进行,在每个进程中,访问临界资源的那段代码称为临界区。为了保证临界资源的正确使用,可以把临界资源的访问过程分成四个部分:
- 进入区。为了进入临界区使用临界资源,在进入区要检查可否进入临界区,如果可以进入临界区,则应设置正在访问临界区的标志,以阻止其他进程同时进入临界区。
- 临界区。进程中访问临界资源的那段代码,又称临界段。
- 退出区。将正在访问临界区的标志清除。
- 剩余区。代码中的其余部分。
2.5.3 互斥
互斥亦称间接制约关系。当一个进程进入临界区使用临界资源时,另一个进程必须等待, 当占用临界资源的进程退出临界区后,另一进程才允许去访问此临界资源。
为禁止两个进程同时进入临界区,同步机制应遵循以下准则:
- 空闲让进。临界区空闲时,可以允许一个请求进入临界区的进程立即进入临界区。
- 忙则等待。当已有进程进入临界区时,其他试图进入临界区的进程必须等待。
- 有限等待。对请求访问的进程,应保证能在有限时间内进入临界区。
- 让权等待。当进程不能进入临界区时,应立即释放处理器,防止进程忙等待。
2.6 进程切换
进程切换是指处理机从一个进程的运行转到另一个进程上运行,这个过程中,进程的运行环境产生了实质性的变化。
进程切换的过程如下:
- 保存处理机上下文,包括程序计数器和其他寄存器。
- 更新PCB信息。
- 把进程的PCB移入相应的队列,如就绪、在某事件阻塞等队列。
- 选择另一个进程执行,并更新其PCB。
- 更新内存管理的数据结构。
- 恢复处理机上下文。
2.7 进程调度
1. 先来先服务算法(FSFS)
最简单的调度算法,既可用于作业调度也可用于进程调度,系统按照作业到达的先后顺序进行调度,或者是优先考虑在系统中等待时间最长的作业
2. 短作业优先调度算法(SJF)
实际情况短作业占有比例很大,为了使他们比长作业优先执行,而产生了短作业优先的调度算法 ,作业越短优先级越高,
缺点:是必须知道作业的运行时间,对长作业不利,人机无法实现交互,未完全考虑作业的紧迫程度
3. 优先级调度算法(PSA)
优先级:对于先来先服务算法,作业的等待时间就是他的优先级,等待时间越长优先级越高,对于短作业优先级作业的长短就是他的优先级。在优先级算法中,基于作业的紧迫程度。
4. 高响应比优先调度算法(HRRN)
在FSFS中只是考虑作业的等待时间而忽略作业的运行时间,SJF算法正好相反,高响应比算法既考虑作业的等待时间有考虑作业的运行时间,
优先权 = (等待时间+要求服务时间)/要求服务时间
5. 时间片轮转调度算法
在早期的时间片轮转法中,系统将所有的就绪进程按先来先服务的原则排成一个队列,每次调度时,把CPU 分配给队首进程,并令其执行一个时间片。时间片的大小从几ms 到几百ms。当执行的时间片用完时,由一个计时器发出时钟中断请求,调度程序便据此信号来停止该进程的执行,并将它送往就绪队列的末尾;然后,再把处理机分配给就绪队列中新的队首进程,同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。换言之,系统能在给定的时间内响应所有用户的请求。
6. 多级反馈队列调度算法
(1) 应设置多个就绪队列,并为各个队列赋予不同的优先级。第一个队列的优先级最高,第二个队列次之,其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同,在优先权愈高的队列中,为每个进程所规定的执行时间片就愈小。例如,第二个队列的时间片要比第一个队列的时间片长一倍,……,第i+1个队列的时间片要比第i个队列的时间片长一倍。
(2) 当一个新进程进入内存后,首先将它放入第一队列的末尾,按FCFS原则排队等待调度。当轮到该进程执行时,如它能在该时间片内完成,便可准备撤离系统;如果它在一个时间片结束时尚未完成,调度程序便将该进程转入第二队列的末尾,再同样地按FCFS原则等待调度执行;如果它在第二队列中运行一个时间片后仍未完成,再依次将它放入第三队列,……,如此下去,当一个长作业(进程)从第一队列依次降到第n队列后,在第n 队列便采取按时间片轮转的方式运行。
(3) 仅当第一队列空闲时,调度程序才调度第二队列中的进程运行;仅当第1~(i-1)队列均空时,才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时,又有新进程进入优先权较高的队列(第1~(i-1)中的任何一个队列),则此时新进程将抢占正在运行进程的处理机,即由调度程序把正在运行的进程放回到第i队列的末尾,把处理机分配给新到的高优先权进程。
2.7.1 Linux内核的进程调度
linux内核的三种调度方法:
- SCHED_OTHER:分时调度策略
- SCHED_FIFO:实时调度策略,先到先服务
- SCHED_RR:实时调度策略,时间片轮转
SHCED_RR和SCHED_FIFO的不同:
当采用SHCED_RR策略的进程的时间片用完,系统将重新分配时间片,并置于就绪队列尾。放在队列尾保证了所有具有相同优先级的RR任务的调度公平。SCHED_FIFO一旦占用cpu则一直运行。一直运行直到有更高优先级任务到达或自己放弃。如果有相同优先级的实时进程(根据优先级计算的调度权值是一样的)已经准备好,FIFO时必须等待该进程主动放弃后才可以运行这个优先级相同的任务。而RR可以让每个任务都执行一段时间。
所有任务都采用linux分时调度策略时:
- 创建任务指定采用分时调度策略,并指定优先级nice值(-20~19)。
- 将根据每个任务的nice值确定在cpu上的执行时间(counter)。
- 如果没有等待资源,则将该任务加入到就绪队列中。
- 调度程序遍历就绪队列中的任务,通过对每个任务动态优先级的计算(counter+20-nice)结果,选择计算结果最大的一个去运行,当这个时间片用完后(counter减至0)或者主动放弃cpu时,该任务将被放在就绪队列末尾(时间片用完)或等待队列(因等待资源而放弃cpu)中。
- 此时调度程序重复上面计算过程,转到第4步。
- 当调度程序发现所有就绪任务计算所得的权值都为不大于0时,重复第2步。
所有任务都采用FIFO时:
- 创建进程时指定采用FIFO,并设置实时优先级rt_priority(1-99)。
- 如果没有等待资源,则将该任务加入到就绪队列中。
- 调度程序遍历就绪队列,根据实时优先级计算调度权值(1000+rt_priority),选择权值最高的任务使用cpu,该FIFO任务将一直占有cpu直到有优先级更高的任务就绪(即使优先级相同也不行)或者主动放弃(等待资源)。
- 调度程序发现有优先级更高的任务到达(高优先级任务可能被中断或定时器任务唤醒,再或被当前运行的任务唤醒,等等),则调度程序立即在当前任务堆栈中保存当前cpu寄存器的所有数据,重新从高优先级任务的堆栈中加载寄存器数据到cpu,此时高优先级的任务开始运行。重复第3步。
- 如果当前任务因等待资源而主动放弃cpu使用权,则该任务将从就绪队列中删除,加入等待队列,此时重复第3步。
所有任务都采用RR调度策略时:
- 创建任务时指定调度参数为RR,并设置任务的实时优先级和nice值(nice值将会转换为该任务的时间片的长度)。
- 如果没有等待资源,则将该任务加入到就绪队列中。
- 调度程序遍历就绪队列,根据实时优先级计算调度权值(1000+rt_priority),选择权值最高的任务使用cpu。
- 如果就绪队列中的RR任务时间片为0,则会根据nice值设置该任务的时间片,同时将该任务放入就绪队列的末尾。重复步骤3。
- 当前任务由于等待资源而主动退出cpu,则其加入等待队列中。重复步骤3。
相关概念:
时间片:分时操作系统分配给每个正在运行的进程微观上的一段CPU时间, 当进程的执行时间用完时, 系统使用调度程序停止该程序的运行, 把 CPU 分配给下一个需要运行的进程.
- 不同进程的时间片可能是不同的
- 进程切换对进程来讲是透明的, 进程是感知不到的(对进程来讲, 进程可以认为整个系统就运行了自己一个进程).
- 时间片在 kernel 中记录在进程描述符的counter中(Linux2.4默认为5, 换算成时间为50ms)
nice 值: 系统中运行的每个进程都有一个优先级, 其范围从 -20 (最高优先级)到 19 (最低优先级), 这个值就是进程优先级. ( top 命令中的 NI 列就是这个值 )
- 默认情况下, 进程的优先级是 0 ( “基本”调度优先级 )
- 优先级比较大的进程相对优先级比较小的进程将比较频繁地被调度运行, 因此就拥有更多的进程周期
- 优先级比较大的进程有更长的时间片初值
- 一般用户只能降低它们自己进程的优先级别, 并限于 0 到 19 之间, 超级用户(root)可以将任何进程的优先级设定为任何值
2.8 进程关系
2.8.1 进程组 (process group)
个进程都会属于一个进程组(process group),每个进程组中可以包含多个进程。进程组会有一个进程组领导进程 (process group leader),领导进程的PID (PID见Linux进程基础)成为进程组的ID (process group ID, PGID),以识别进程组。
2.8.2 会话 (session)
在shell支持工作控制(job control)的前提下,多个进程组还可以构成一个会话 (session)。bash(Bourne-Again shell)支持工作控制,而sh(Bourne shell)并不支持。
会话是由其中的进程建立的,该进程叫做会话的领导进程(session leader)。会话领导进程的PID成为识别会话的SID(session ID)。会话中的每个进程组称为一个工作(job)。会话可以有一个进程组成为会话的前台工作(foreground),而其他的进程组是后台工作(background)。每个会话可以连接一个控制终端(control terminal)。当控制终端有输入输出时,都传递给该会话的前台进程组。由终端产生的信号,比如CTRL+Z, CTRL+\,会传递到前台进程组。会话的意义在于将多个工作囊括在一个终端,并取其中的一个工作作为前台,来直接接收该终端的输入输出以及终端信号。 其他工作在后台运行。
2.8.3 系统进程和用户进程
系统进程:可以执行内存资源分配和进程切换等管理工作;而且,该进程的运行不受用户的干预,即使是root用户也不能干预系统进程的运行。
用户进程:通过执行用户程序、应用程序或内核之外的系统程序而产生的进程,此类进程可以在用户的控制下运行或关闭。
2.9 死锁
2.9.1 死锁定义
在两个或多个并发进程中,如果每个进程持有某种资源而又都等待别的进程释放它或它们现在保持着的资源,在未改变这种状态之前都不能向前推进,称这一组进程产生了死锁。通俗地讲,就是两个或多个进程被无限期地阻塞、相互等待的一种状态。
2.9.2 产生条件
互斥条件 – 一个资源一次只能被一个进程使用
请求保持条件 – 一个进程因请求资源而阻塞时,对已经获得资源保持不放
不可抢占条件 – 进程已获得的资源在未使用完之前不能强行剥夺
循环等待条件 – 若干进程之间形成一种头尾相接的循环等待资源的关系
2.9.3 避免死锁的条件
1:破坏“请求和保持”条件:规定所有进程在开始运行之前,都必须一次性的申请其在整个运行过程所需要的全部资源。
优点:简单,安全。 缺点:资源严重浪费,恶化了系统的利用率;
2:破坏“不剥夺”条件:进程逐个的提出资源请求,当一个已经保持了某些资源的进程,再提出新的资源请求而不能立即得到满足时,必须释放它已经保持了的所有资源,待以后需要时再重新申请。
缺点:实现复杂,代价大,反复地申请和释放资源,而使进程的执行无限的推迟、延长了进程的周转时间增加系统开销、降低系统吞吐量。
3:破坏“环路等待”条件:将所有的资源按类型进行线性排队,并赋予不同的序号。所有进程请求资源必须按照资源递增的次序提出,防止出现环路。
缺点:1、序号必须相对稳定,限制了新设备类型的增加
2、作业(进程)使用资源顺序和系统规定的顺序不同而造成资源的浪费
3、限制了用户编程
注意:由于互斥条件是非共享设备所必需的,不能改变
2.9.4 银行家算法
银行家算法是一种常见的避免死锁的方法。
数据结构:
可利用资源向量Available
。这是一个含有m个元素的数组,其中的每一个元素代表一类可利用的资源数目,其初始值是系统中所配置的该类全部可用资源的数目,其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K,则表示系统中现有Rj类资源K个。最大需求矩阵Max
。这是一个n×m的矩阵,它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K,则表示进程i需要Rj类资源的最大数目为K。分配矩阵Allocation
。这也是一个n×m的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K,则表示进程i当前已分得R j类资源的数目为K。需求矩阵Need
。这也是一个n×m的矩阵,用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K,则表示进程i还需要R j类资源K个,方能完成其任务。
上述三个矩阵间存在下述关系:Need[i, j]=Max[i, j]-Allocation[i, j]
算法过程:
设Request i是进程Pi的请求向量,如果Request i[j]=K,表示进程P i需要K个R j类型的资源。当P i发出资源请求后,系统按下述步骤进行检查:
- 如果Request i[j]≤Need[i,j],便转向步骤(2);否则认为出错,因为它所需要的资源数已超过它所宣布的最大值。
- 如果Request i[j]≤Available[j],便转向步骤(3);否则,表示尚无足够资源,Pi须等待。
- 系统试探着把资源分配给进程P i,并修改下面数据结构中的数值:
Available[j]:= Available[j]-Request i[j];
Allocation[i,j]:= Allocation[i,j]+Request i[j];
Need[i,j]:= Need[i,j]-Request i[j]; - 系统执行
安全性算法
,检查此次资源分配后系统是否处于安全状态。若安全,才正式将资源分配给进程Pi,以完成本次分配;否则,将本次的试探分配作废,恢复原来的资源分配状态,让进程Pi等待。
安全性算法:
- 设置两个向量:
① 工作向量Work,它表示系统可提供给进程继续运行所需的各类资源数目,它含有m个元素,在执行安全算法开始时,Work:=Available。
② Finish,它表示系统是否有足够的资源分配给进程,使之运行完成。开始时先做Finish[i]:=false;当有足够资源分配给进程时,再令Finish[i]:=true。
- 从进程集合中找到一个能满足下述条件的进程:
① Finish[i]=false;
② Need[i,j]≤Work[j];若找到,执行步骤(3),否则,执行步骤(4)。
- 当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行:
Work[j]:= Work[j]+Allocation[i,j];
Finish[i]:=true;
go to step 2;
2.10 父进程、子进程
2.10.1 fork函数
在Unix/Linux中用fork函数创建一个新的进程。进程是由当前已有进程调用fork函数创建,分叉的进程叫子进程,创建者叫父进程。
该函数的特点是调用一次,返回两次,一次是在父进程,一次是在子进程。两次返回的区别是子进程的返回值为0,父进程的返回值是新子进程的ID。子进程与父进程继续并发运行。如果父进程继续创建更多的子进程,子进程之间是兄弟关系,同样子进程也可以创建自己的子进程,这样可以建立起定义关系的进程之间的一种层次关系。
fork之后,操作系统会复制一个与父进程完全相同的子进程,虽说是父子关系,但是在操作系统看来,他们更像兄弟关系,这2个进程共享代码空间,但是数据空间是互相独立的,子进程数据空间中的内容是父进程的完整拷贝,指令指针也完全相同,子进程拥有父进程当前运行到的位置。
2.10.2 系统进程
在UNIX里,除了进程0(即PID=0的交换进程,Swapper Process)以外的所有进程都是由其他进程使用系统调用fork创建的,这里调用fork创建新进程的进程即为父进程,而相对应的为其创建出的进程则为子进程,因而除了进程0以外的进程都只有一个父进程,但一个进程可以有多个子进程。
操作系统内核以进程标识符(Process Identifier,即PID)来识别进程。进程0是系统引导时创建的一个特殊进程,在其调用fork创建出一个子进程(即PID=1的进程1,又称init)后,进程0就转为交换进程(有时也被称为空闲进程),而进程1(init进程)就是系统里其他所有进程的祖先。
2.10.3 僵死进程与孤儿进程
当一个子进程结束运行(一般是调用exit、运行时发生致命错误或收到终止信号所导致)时,子进程的退出状态(返回值)会回报给操作系统,系统则以SIGCHLD信号将子进程被结束的事件告知父进程,此时子进程的进程控制块(PCB)仍驻留在内存中。一般来说,收到SIGCHLD后,父进程会使用wait系统调用以获取子进程的退出状态,然后内核就可以从内存中释放已结束的子进程的PCB;而如若父进程没有这么做的话,子进程的PCB就会一直驻留在内存中,也即成为僵尸进程。
孤儿进程则是指父进程结束后仍在运行的子进程。在类UNIX系统中,孤儿进程一般会被init进程所“收养”,成为init的子进程。
为避免产生僵尸进程,实际应用中一般采取的方式是:
- 将父进程中对SIGCHLD信号的处理函数设为SIG_IGN(忽略信号);
- fork两次并杀死一级子进程,令二级子进程成为孤儿进程而被init所“收养”、清理。
本文由『后端精进之路』原创,首发于博客 http://teckee.github.io/ , 转载请注明出处
搜索『后端精进之路』关注公众号,立刻获取最新文章和价值2000元的BATJ精品面试课程。