Linux教程

操作系统笔记(二)进程管理

本文主要是介绍操作系统笔记(二)进程管理,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

进程管理

  • 一、进程与线程基本知识
  • 二、处理机调度
  • 三、进程的同步与互斥
  • 四、死锁

一、进程与线程基本知识

进程是资源分配、接收调度的基本单位。

在多道程序技术下,由于程序并发执行,导致他们失去封闭性,由此,引入进程。

1.PCB

1.1、PCB的概念

PCB是一种特殊的数据结构,来描述进程的基本情况和运行状态,进而控制和管理进程。
程序段、数据段和PCB三部分构成进程映像,进程映像是静态的,而进程是动态的。
PCB是进程存在的唯一标志!

1.2、PCB的组成
(1)PID:进程标识符,每个进程有唯一的标识号。
(2)UID:用户标识符,进程归属的用户,主要为了共享和保护。
(3)进程控制和管理信息:包括进程当前状态、进程优先级、进入内存时间等。
(4)处理及相关信息:状态字以及各种寄存器的值。

2.进程的组织

进程的组织方式常用的有链接方式和索引方式。

2.1链接方式
根据进程的PCB中的状态链接成队列,分为就绪队列、阻塞队列等。

2.2索引方式
将同一状态的进程组织在同一索引表中,表项指向PCB,分为就绪索引表和阻塞索引表。

3.进程的状态与转换

3.1进程的状态
(1)运行态:进程正在处理机上运行。
(2)就绪态:进程得到了处理机外的一切资源,只要处理机选中了它,便可立即运行。
(3)阻塞态:进程正在等待某一事件发生而暂停运行(如等待输入输出完成),此时即使处理机空闲也不能运行。
(4)创建态:进程正在被创建,尚未到就绪态。
(5)终止态:进程正在从系统中消失,可能是正常结束或者因为中断而退出运行。

3.2进程的转换

在这里插入图片描述

4.进程的控制

进程的控制主要功能是对系统中的所有进程实施有效的管理,主要包括进程创建、撤销进程、进程状态的转换等。一般吧进程控制的程序成为原语。

5.进程的通信

由于进程的内存地址空间相互独立,一个进程不能直接访问另一个进程的地址空间,所以需要共享。进程通信是指进程之间的信息交换,PV操作是低级操作,这里指高级操作。

5.1、共享存储
低级方式的共享是基于数据结构的,高级方式的共享是基于存储区的。
在这种共享方式下,操作系统会提供一个存储区和同步互斥工具,通过特殊的系统调用让两个进程共享空间。
两个进程要互斥地访问共享空间。

5.2、消息传递
发送进程把消息发到某个中间实体,接收进程从中间实体取得消息,中间实体称为信箱。

5.3、管道通信
“管道”指连接读写进程的一个pipe文件,其实就是内存中一个到小固定的缓冲区。
管道只能采用半双工通信,若想实现全双工通信需要建立两个管道。
各进程要互斥地访问管道。
管道不满不读,管道不空不写。

6.线程

Q:为什么要引入线程?
A:因为有的进程要执行很多事情,如QQ既要传送文件,又要视频聊天,如果没有线程,这两个功能只能一个个地执行,引入线程可以使多道程序并发执行,还可以减少程序在并发执行时所付出的时空开销(如切换进程的运行环境)。

6.1、线程与进程
引入线程后,进程只是系统资源的分配单元,而线程是处理机的分配单元
用于各个线程共享进程的地址空间,所以线程的同步与通信容易实现。

6.2、线程的属性
由于进程是资源的分配单位,所以线程是不具有系统资源的。线程也有一个唯一的标识符和线程控制块。

6.3、线程的实现方式
线程分为(1)内核级线程 (2)用户级线程
简单的说,内核级线程是操作系统能看到的,用户级线程是用户能看到的。
用户级线程的管理由应用程序来完成,线程切换等可以在用户态下完成。
内核级线程的管理是操作系统内核完成的,线程切换等在核心态下完成。
由于操作系统只能看见内核级线程,所以内核级线程才是处理机分配的单位!
在这里插入图片描述
7.多线程模型

(1)多对一模型:将多个用户级线程映射到一个内核级线程,线程管理在用户空间完成,但是一个停了,所有都要停,而且这些线程不能同时运行在多处理机上(因为在OS看来他们是一个线程)。
(2)一对一模型:将用户级线程和内核级线程一一对应,一个线程阻塞不会影响其他线程,并发度高,开销也大。
(3)多对多模型:将n个用户级线程对应到m个内核级线程中,中和了一对一模型和一对多模型的优点。


二、处理机调度

1.调度的概念

Q:什么是处理机调度?
A:处理及调度是对处理机进行分配,即从就绪队列按照一定算法选择一个进程并将处理机分配给它运行。实现程序并发执行。
处理机调度是多道程序操作系统的基础,是操作系统设计的核心问题。

2.调度的层次

(1)作业调度:称为高级调度,由于内存有限,无法将所有作业都调入内存,按一定算法从使其从后备队列到内存中,从外存到内存,并创建对应的PCB。(主要是调入,只会调入调出一次)。
(2)内存调度:可将暂时不能运行的进程调至外存等待,调到外存的进程状态为挂起态。被挂起的进程的PCB不会被调到外存,而是会常住在内存中,并且他们会在挂起队列中。被挂起的进程要按照一定算法重新调入内存(频率高于高级调度)。
在这里插入图片描述

(3)进程调度:按某种算法从就绪队列中选择一个进程分配处理机。

调度作用发生在对进程影响
作业调度从后备队列选择作业调入内存并创建PCB外存->内存无->创建态->就绪态
内存调度从挂起队列选择进程调回内存外存->内存挂起态->就绪态,挂起态->阻塞态
进程调度从就绪队列选择进程获得处理机内存->CPU就绪态->运行态

3.调度的时机及方式

3.1调度发生的情况
(1)当前进程主动放弃处理机(如正常结束,请求IO阻塞)。
(2)当前进程被动放弃处理机(如更高优先级进程进入就绪队列)。

3.2不能进行调度调度的情况
(1)处理中断的过程中。
(2)进程在操作系统内核的临界区。
(3)在原子操作中。

4.调度方式
(1)非剥夺式方式:即进程主动放弃处理机,即使有更重要的进程进入就绪队列,也得等当前进程处理完毕后才能上处理机。不能应用于分时和实时系统即不能优先处理紧急任务或人机交互。
(2)剥夺式方式:当一个高优先级的进程进入队列后,当前占有处理机的进程会被迫放弃处理机,把处理机分配给高优先级的进程。

5.调度的基本准则

(1)CPU利用率:计算公式为 【忙碌时间/总时间】。
(2)系统吞吐量:指单位时间内CPU完成作业的数量,长短作业不做区别。
(3)周转时间:周转时间指提交到作业完成所经历的时间,它包括:

  • 作业在后备队列等待高级调度的时间
  • 作业在就绪队列等待的时间
  • 进程在处理机上的执行时间
  • 进程等待IO操作的时间

周转时间=作业完成时间-作业提交时间
平均周转时间=所有作业周转时间/作业数量
带权周转时间=作业周转时间/作业实际上运行时间
(4)等待时间:指进程/作业处于等处理机状态的时间。进程的等待时间与作业的等待时间不同,另外不能把IO时间算进等待时间。
(5)响应时间:指用户从提出请求到被首次响应所经历的时间

6.调度算法

饥饿:指一个进程或者作业长时间得不到服务。
非剥夺式算法人机交互能力差,不关注响应时间等。

(1)先来先服务算法(FCFS):按照进程/作业到达的顺序来执行

适用于是否可抢占优点缺点是否饥饿
作业/进程不可剥夺算法简单,有利于CPU繁忙型作业对长作业有利效率低,不利于短作业,不利于IO繁忙型不会

(2)短作业/进程优先算法(SJF):选择估计运行时间最短的算法优先运行,默认是非剥夺式,也有剥夺版本

适用于是否可抢占优点缺点是否饥饿
作业/进程不可剥夺/可剥夺最短的平均等待时间平均周转时间可能会导致饥饿

严格来讲,抢占式的SJF算法平均等待时间和平均周转时间最少。

(3)高响应比优先算法(SJF):要综合考虑进程/作业的等待时间和要求服务时间,响应比=(等待时间+要求服务时间)/要求服务时间

适用于是否可抢占优点缺点是否饥饿
作业/进程 ,主要用于作业不可剥夺有利于短作业,又兼顾长作业/不会

由于不可剥夺,所以即使有高响应比的进来也要等当前进程主动放弃处理机。

(4)时间片调度算法:处理机选择就绪队列中第一个进程执行,但是仅能运行一个时间片,在时间片结束后即使没有运行完,处理机也会分配给下一个进程,被剥夺的进程回到队尾。

适用于是否可抢占优点缺点是否饥饿
作业可剥夺公平,响应快由于进程切换,会有额外开销,不能区别紧急任务不会

当P1结束走到队尾时,此时P2进程刚进入,默认新的进程上处理机,即P2。
主要适用于分时系统所以,关心响应时间,不在意周转时间。
如果时间片过大,变成先来先服务,如果时间片过小,则CPU利用率低。
时钟装置会发出时钟中断来告诉操作系统时间片已到。

(5)优先级调度算法:按照优先级来调度。既有抢占式也有非抢占式。

抢占式和非抢占式的可能发生调度的点分别是:当前进程运行完毕和新进程进入就绪队列。

适用于是否可抢占优点缺点是否饥饿
作业 /进程,甚至IO不可剥夺/可剥夺适用于实时操作系统可能会饥饿

静态优先级:给一个优先级后,就不会再变了。
动态优先级:随着进程的情况动态的调整优先级。
系统进程优先级>用户进程优先级
IO型进程优先级(IO繁忙性进程)>计算型进程(CPU繁忙性进程)
(个人理解:IO设备与CPU可以并行运行,让IO先运行会增加利用率)

(6)多级反馈队列调度算法:
结构:有多个就绪队列组成,就绪队列分优先级高低,优先级高的队列的时间片小。
行为:
当新进程到达时,先到优先级最高的队列,按FCFS原则分配时间片,时间片运行结束之,进入下一队列的队尾。
只有当优先级高的队列为空时,优先级较低的队列才会开始分配时间片。
如果优先级低的队列中有进程正在执行,此时一个新进程到达优先级较高的队列,则正在执行的进程回到所在队列队尾。
如果进程已经在优先级最低的队列中了,当时间片结束时,回到队尾即可(因为已经没有优先级更低的队列了)。

适用于是否可抢占优点缺点是否饥饿
进程可剥夺集结了所有算法的优点/

UNIX系统使用的就是这种。

三、进程的同步与互斥

1.进程同步

进程同步:即使多道并发程序具有异步性,但是某些程序在执行过程中应该有先后顺序,进程同步就是让异步性的进程也要按一定次序来执行(直接制约关系)。

2.进程互斥

计算机的某些资源在一个时间段内只允许一个进程访问,这类资源称为临界资源,对临界资源的访问只能互斥地进行(间接制约关系)

对临界资源的访问逻辑上分为四个部分:
(1)进入区:负责检查是否有进程访问临界资源,若自己可进入,则表示“自己正在访问临界区”即(上锁)防止其他进程进入。
(2)临界区:访问临界资源的代码。
(3)退出区:解除自己正在访问临界资源的标志,即(解锁)。
(4)剩余区:做其他处理(不重要)。

在这里插入图片描述

3.软件实现进程互斥

(1)单标志法
在这里插入图片描述
这种算法对临界区的访问一定是轮流交替的,如果P0不访问临界区,由没有把turn改成1,则此时临界区空闲,P1却无法进入。

(2)双标志先检查法

在这里插入图片描述通俗的理解为“你用不用,不用我用”,两个进程同时这么以为,由于最开始设定的都是不用,导致两个进程同时进入临界区
可能会出现两个进程同时访问临界区的状况。
1,2不是一气呵成的,先检查后上锁,如果1,2是原子操作不会发生进程切换的,那么这个算法没毛病。

(3)双标志后检查法

在这里插入图片描述

通俗理解为“我要用,你用吗”,两个进程最开始初始化为自己要用,每个进程都一位对方要用,所以两者都不进入临界区。

(4)Peterson算法

在这里插入图片描述
通俗的理解为“我想用,但你先来吧”,turn代表允许哪个进程进入,而lag表示自己进入的意愿。

4.硬件实现进程互斥

通过硬件实现临界段的方法成为低级方法或元方法。

(1)中断屏蔽算法:当一个进程要访问临界区时,最简单的方法是禁止一切中断发生即关中断,在访问临界区之后,再开中断。
(2)TestAndSet指令:也称为TS或TSL指令。这条指令是由硬件实现的,这个指令是一个原子操作,即执行期间不能被中断。

在这里插入图片描述
通俗地理解为:lock是否为true,表示是否临界区正在被使用,如果正在被使用,lock为true,其他进程一检查,进不来,之后访问临界区的代码执行完毕之后会自己把lock设置为false让其他进程进来。
左边的函数就是“是否有锁啊,有的话,返回有,然后lock=true依旧有,如果没有的话,那lock=true这回有了”。
优点:实现简单,一气呵成,适用于多处理及操作系统。
缺点类似于单标志法。
(3)Swap指令:也称Exchange指令或XCHG指令

在这里插入图片描述

与TSL指令在逻辑上是一样的。

5.信号量机制

信号量机制是一种功能较强用来解决进程同步和互斥问题的机制,他只能被两个标准的原语wait(S)和signal(S)访问,也可记为P操作和V操作。原语是由关中断和开中断实现的。
信号量其实际上是一个变量,用来表示系统中某种资源的数量。
wait(S)相当于进入区,signal(S)相当于退出区。
(1)整型信号量
在这里插入图片描述
(2)记录性信号量
在这里插入图片描述
这个阻塞条件与唤醒条件可以这么理解:
进入区表示我要用这类资源,所以我先把它的剩余资源总数减一,如果此时正好为0,说明它是原来有一,被我占用了之后变为0,所以我被分配到了资源,那么阻塞条件应该是“S.value<0”即原来是小于等于0的,我申请后,变成负数了。
退出区表示我用完了这类资源,如果此时“S.value<=0”那么肯定是有进程等着用呢,所以我把阻塞队列唤醒一个。

6.信号量实现同步、互斥

(1)信号量实现进程互斥:
在这里插入图片描述
只要有进程访问临界区了,互斥信号量就<=0,其他进程就进不来,很轻松就实现了互斥。
不同的临界资源要设置不同的互斥信号量

(2)信号量实现进程同步
在这里插入图片描述

个人理解:之所以在前代码后加V,在后代码加P,后代码想要执行,P之前,必须标志位得是大于0的(因为P还会减1),而初始标志位就是0,所以后代码必须得等V操作结束后才能运行。
而V操作在前代码后是保证前代码在后代码之前就执行完毕,V操作就是让后代码执行的钥匙,所以V应该在前代码之后。

(3)进程的前驱关系
进程的前驱关系本质上就是进程同步。

7.管程

管程其实也是一种同步机制(跟PV操作一样),就是一种代表共享资源的数据结构,以及由对该共享数据结构实施操作的一组过程所组成的ziyu7an管理程序。

管程的特性(管程其实类似于java中的类)
(1)管程把对共享资源的操作封装起来,管程内的数据结构只能被管程中的过程所访问。
(2)每次仅允许一个进程进入管程,从而实现进程互斥(由编译器实现)

管程有一个条件变量机制,就是当一个进程被阻塞时,将该阻塞原因定义为条件变量condition,此时其他进程无法进入管程。
条件变量与信号量的区别在于,信号量是有值的,而管程只是一个状态位。


四、死锁

1.死锁的定义

死锁:是指多个进程因竞争资源导致互相等待,若没有外力进入,这些进程都无法推进。

2.死锁产生的原因

只要这四个条件有一个不成立,死锁就不会发生。
(1)互斥条件:指临界区资源同一时间内只能互斥地被访问。
(2)不剥夺条件:指一个进程在占有CPU资源时,不能被其他进程抢走,只能等该进程主动放弃。
(3)请求并保持条件:指一个资源在等待其他资源时,对自己已有的资源不会放弃。
(4)循环等待:存在一种进程资源的循环等待链,每个进程手上已有的资源都是另外的进程所请求的。
循环等待不一定有死锁,但死锁一定存在循环等待。
可以理解为循环等待中,可能会有可替代的资源。

3.死锁的预防

死锁预防即破坏以上四个条件之一。
(1)破坏互斥条件:不太可行,因为有些资源注定要互斥访问,如打印机、摄像头。
(2)破坏不可剥夺条件:反复的进行资源抢夺可能会增加系统开销。
(3)破坏请求并保持条件:这种采用静态分配方式,即一个进程要运行之前,要把所有他所需要的资源分配给它,它才会执行,这样做会严重浪费系统资源。
(4)破坏循坏等待条件:给系统资源编号,使每一个进程必须按编号递增的顺序请求资源。

4.银行家算法

Q:什么是系统安全状态?
A:指系统按某种进程推进顺序可以满足每个进程对资源的需求,使每个进程都可以顺利完成,如果能找到这样的一个安全序列,则系统处于安全状态。
不安全状态可能进入死锁,安全状态一定不会死锁,死锁系统一定处于不安全状态。

银行家算法通俗易懂地理解就是:当一个进程申请资源时,先看它是否超过它的最大需求量,若超过则拒绝分配,若没超过,进行下面分析。
看看当前系统能否满足进程所需要资源,能的话则试探性地分配给它,否则延后处理。

5.死锁的检测和解除

资源分配图:圆圈表示进程,框表示一类资源,从进程到资源的有向边叫请求边,从资源到进程的叫分配边。

死锁定理:简单地讲就是对资源分配图进行简化,若改图能消去所有的边,说明该图是可以简化的。系统发生死锁的条件是当且仅当资源分配图是不可完全简化的,这就是死锁定理。
在这里插入图片描述如图,R1资源一共有仨,分配了三个,这是P2向他请求是满足不了的。

死锁解除方法:
(1)资源剥夺法:挂起某些进程,抢占他的资源,但应该注意避免饥饿。
(2)撤销进程法:直接撤销部分或全部死锁进程,并剥夺这些资源。
(3)进程回退法:让一个或多个进程回退到能避免死锁的时候,这种方法需要寄存器来记录历史信息。

这篇关于操作系统笔记(二)进程管理的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!