定义:前趋图是一个有向无环图(DAG),用于描述进程之间执行的前后关系,其实就是一个拓扑排序。
– 结点:表示一个程序段或进程,或一条语句
– 有向边:结点之间的偏序或前序关系“→”
注意:前趋图中禁止存在循环!
一个程序由若干个程序段组成,而这些程序段的执行必须是顺序的,这种程序执行的方式就称为程序的顺序执行。
(1) 顺序性
处理机的操作严格按照程序所规定的顺序执行。
(2) 封闭性
程序一旦开始执行,其计算结果不受外界因素的影响。
(3) 可再现性
程序执行的结果与它的执行速度无关(即与时间无关),而只与初始条件有关。
上图中可以抽象出四个程序,列出其前趋图,发现S1和S2互不干扰,可以并发执行。
(1)间断性
在多道程序设计的环境下,程序的并发执行,以及为完成一项任务而相互合作,这些程序之间要共享系统的资源,形成了相互制约的关系,即形成了一定的先后顺序。相互制约导致并发程序具有“执行—暂停—执行”这种间断性的活动规律。
(2)失去封闭性
程序在并发执行时,系统的资源状态由多道程序来改变,程序运行失去封闭性。程序的运行受到其他程序的影响。
(3)不可再现性
程序在并发执行时,多次运行初始条件相同的同一程序会得出不同的运行结果。
- 进程:在一个数据集合上的运行过程,是系统进行资源分配和调度的一个独立单位,是可并发执行的程序在一个数据集合上的运行过程。
- 进程的结构: 程序+数据+PCB
blockquote>
进程控制块(Processing Control Block)是系统为了管理进程设置的一个专门的数据结构。系统用它来记录进程的外部特征,描述进程的运动变化过程。同时,系统可以利用PCB来控制和管理进程,所以说,PCB是系统感知进程存在的唯一标志。
/blockquote>
联系:
区别:
(1)就绪状态(Ready)
进程已获得除CPU之外的所有必需的资源,一旦得到CPU控制权,立即可以运行。
(2)运行状态(Running)
进程已获得运行所必需的资源,它正在处理机上执行。
(3)阻塞状态(Blocked)
正在执行的进程由于发生某事件(如等待I/O)而暂时无法执行时,便放弃处理机而处于暂停状态,称该进程处于阻塞状态或等待状态。
当我们刚开始运行程序的时候,操作系统需要为该进程分配所需的内存空间等系统资源,并为其创建、初始化PCB。(如 分配进程标识符PID),此时,该进程就处于创建态。而当进程结束时 (正常结束或者由于bug导致进程无法继续执行下去,如 整数除0错误),操作系统会回收分配给该进程的系统资源以及撤销该进程的PCB…,目的是为了撤销该进程,此时,该进程就处于终止态。
进程正在被创建,操作系统为该进程分配系统资源、初始化PCB。
进程正在被撤销,操作系统会回收该进程拥有的系统资源、撤销PCB。
– NULL→创建
一个新进程被产生出来执行一个程序。
– 创建→就绪
当进程被创建完成并初始化后,一切就绪准备运行时,变为就绪状态。
– 就绪→运行
处于就绪状态的进程被进程调度程序选中后,就分配到处理机上来运行
1.挂起操作的引入虚拟存储中交换的需要(挤死了,还轮不到你用CPU,别占着茅坑不拉屎,滚到外存去)
2.引起挂起源于操作后三个进程状态的转换
操作系统管理控制进程运行所用的信息集合,如图:
同一状态的进程其PCB成一链表,多个状态对应多个不同的链表
同一状态的进程归入一个索引表(由索引指向PCB),多个状态对应多
个不同的索引表
内核:把常用的或与硬件关联度高的模块打包放到离硬件进的地方,常驻内存,提高效率。
OS的内核运行在
处理机的内核模式下,并在该模式下提供所有OS应具备的功能。
问:什么是处理机的内核模式?
> 原语(Primitive),由若干指令组成,用于完成一定功能的过程。一个原语,是一个原子操作,是一个不可分割的执行单位,执行过程不允许被中断。其中的所有指令,要么全部执行,要么全不执行,运行在系统态,常驻内存。(两“全部”特性)
在OS中,允许一个进程创建另一个进程,通常把创建进程的进程称为父进程,而把被创建的进程称为子进程。子进程可继续创建更多的孙进程,由此便形成了一个进程的层次结构。
找出被终止进程的PCB —– 若进程状态为运行态,置CPU调度标志为真,若其有子孙进程,终止其子孙进程并回收其资源 —– 回收终止进程的资源 —– 回收终止进程的PCB。
请求并等待系统服务,无法马上完成
启动某种操作,无法马上完成
需要的数据没有到达
被阻塞进程需要的资源可被满足
被阻塞进程等待的事件到达
- 若为静止就绪,则改为活动就绪;
- 若为静止阻塞,则改为活动阻塞。
并发进程之间因相互争夺独占性资源而产生的竞争性制约关系(间接相互制约关系)
并发进程之间为完成共同任务,基于某个条件来协调执行先后关系而产生的协作制约关系(直接相互制约关系)
这样,进程的代码就组织成了下面的形式:
blockquote>
中断:中断是指计算机运行过程中,出现某些意外情况需主机干预时,机器能自动停止正在运行的程序并转入处理新情况的程序,处理完毕后又返回原被暂停的程序继续运行。
/blockquote>
之所以会引发临界区的冲突访问,其根源在于一个进程在访问临界区时发生了进程的调度,使得另一个进程也进入了临界区进行访问。因此,在进程访问临界区时禁止调度就可以解决这个问题。
进入临界区:禁止所有中断,并保存标志;
离开临界区:使能所有中断,并恢复标志
- 禁用中断后,进程无法被停止:整个系统都会为此停下来,可能导致其他进程处于饥饿状态
- 临界区可能很长,无法确定响应中断所需的时间(可能存在硬件影响)
- 不适用多处理器系统,在一个处理器上关闭中断,不能防止进程在其它处理器上执行相同的临界区代码
“非常谦让的代码”,准备进入了(flag[i] = true),则先让别人进入(turn =j)。
a. 概念:
锁是一个抽象的数据结构,一个二进制变量(锁定/解锁),使用锁来控制临界区访问。
一共有两个操作:
Lock::Acquire()锁被释放前一直等待,然后得到锁。
Lock::Release()释放锁,唤醒任何等待的进程。
使用锁机制的临界区访问伪代码如下:
b. 实现方式:
原子操作指令:现代CPU体系结构提供一些特殊的原子操作指令,实现了两个或两个以上动作的原子性,当这种指令执行时,被它访问的内存位置将不允许被其它指令同时访问。常见的比如测试和置位(Test-and-Set )指令和交换指令(exchange)。
伪代码分别如下:
lock赋值为1,返回lock的初始值。
交换ab的值。
实现自旋锁(spin lock)自旋锁这个概念是相对于互斥锁而言的。对于自旋锁,当一个进程不能得到锁资源时,并不会放弃CPU而进入阻塞状态,而是不断地在那里进行循环检测,因此称它为自旋锁。
解释:最初的时候value为0,ts返回值为0,并且value变为1表示锁已经被获取,并且退出循环。如果有第二个进程,就会一直执行ts语句(value为1,返回1),直到第一个进程release之后立即获取锁。
利用ts指令实现无忙等待锁无忙等待锁的基本思想和自旋锁是一样的,只是一旦进程不能进入临界区,则将它加入等待队列,并且进入阻塞状态。在一个进程释放了锁资源后,再挑选等待队列中的一个阻塞进程,并将它唤醒。
c. 优缺点
适用于单处理器或者共享主存的多处理器中任意数量的进程同步
简单并且容易证明
支持多临界区
忙等待消耗处理器时间
可能导致饥饿,进程离开临界区时有多个等待进程的情况
死锁,拥有临界区的低优先级进程,请求访问临界区的高优先级进程获得处理器并等待临界区
为了解决同步互斥问题,操作系统会提供一些高级抽象方法供应用进程调用,这样应用进程就不需要自己利用繁琐的软件方法来解决同步互斥了。存在三种高级抽象方法,分别是锁,信号量与条件变量,其中锁也在上面那篇中讨论过了,这里主要是讨论信号量机制。
信号量代表了当前剩余系统资源数量。如果有某个进程申请占用资源,信号量的值-1,反之有进程释放资源,信号量的值+1。要实现上述的两个过程需要有两个原子操作:P操作和V操作,分别表示
尝试减少和
增加信号量的值。这两个原子操作连同表示剩余资源数的值封装在一起称为信号量,所以,信号量就是一种
抽象数据类型。
当一个进程释放资源时,将表示当前空余资源+1,若,说明有进程在阻塞队列中等待资源的释放,则将队列中相应的进程取出将其唤醒;若,说明当前没有进程在队列中,直接结束程序即可。
伪代码如下:
两者区别就是记录型信号量多了一个阻塞队列(一般为链表形式链接全部阻塞进程),相比于整数型,记录型不会出现“忙等”现象,上述的伪代码也是采用记录型信号量。
即要么把它所请求的资源全部分配给进程,要不一个也不。
br /> 伪代码如下:
为了实现两进程之间的同步,信号量必须成对地出现在两个不同的进程中,并且其位置也要相互匹配。
进入管程的进程因资源被占用而进入等待状态
每个条件变量表示一种等待原因,对应一个等待队列
核心:
生产者和消费者对缓冲区互斥访问是互斥关系(异步的),同时生产者和消费者又是一个相互协作的关系,只有生产者生产之后,消费者才能消费,他们也是同步关系。
br />
br /> 写者:读取和修改数据
br /> 要求:“读 – 读”允许,“读 – 写”互斥, “写- 写”互斥
br /> 读者计数readcount:正在进行读的读者数目,初始化为0,共享变量,用于读写互斥的控制。
br /> 信号量rmutex:控制对读者计数的互斥修改,初始化为1。
只要有读者正在读状态,后来的读者都能直接进入,如读者持续不断进入,则写者就处于饥饿。
只要有写者就绪,写者应尽快执行写操作,如写者持续不断就绪,则读者就处于饥饿。
低级通信:进程间仅交换一些状态和少量数据。如:进程之间的互斥和同步。缺点:(1)效率低 (2)通信对用户不透明
高级通信:进程间可交换大量数据。用户可直接利用操作系统提供的一组通信命令,高效地传送大量数据的一种通信方式。操作系统隐藏了进程通信的细节,对用户透明,减少了通信程序编制上的复杂性。
数据结构
或
共享存储区
,通过这些空间进行通信。
进程公用某些数据结构,借以实现诸进程间的信息交换。如生产者-消费者问题的有界缓冲区。由程序员负责公用数据结构的设置及对进程间同步的处理,操作系统只提供共享存储器。通信效率低,只适合传递相对少量的数据,属于低级通信。
在存储器中划出一块共享存储区,诸进程可通过对共享存储区中数据的读或写来实现通信。通过共享存储分区实现进程之间的信息交换。共享内存是把
同一个物理内存区域同时映射到
多个进程的内存地址空间的通信机制。
通信过程:
(1)申请共享存储分区;
(2)将共享存储分区映射到本进程地址空间中;
(3)进行数据读写;
(4)解除共享存储分区映射;
(5)删除共享存储分区;
特点:
最快的方法,一个进程写另外一个进程立即可见,没有系统调用干预没有数据复制,不提供同步,由程序员提供同步。
管道:
指用于连接一个读进程和一个写进程以实现他们之间通信的一个共享文件,又名pipe文件。
br />
管道机制提供的协调能力:
互斥(读写互斥);同步(管道空停止读,管道满停止写);确定对方是否存在,只有对方存在的时候才能通信。
通信命令(原语)进行通信
。
通信原语:Send(Receiver, message); 发送一个消息给接收进程
Receive(Sender, message); 接收Sender发来的消息
消息格式:单机系统环境:环境相同,消息格式简单
网络环境:环境不同,传输距离很远,消息格式比较复杂。
进程同步方式:在进程之间进行通信时,辅以进程同步机制,使诸进程间能协调通信。发送进程或接收进程在完成消息的发送或接收后,都存在两种可能性:进程或者继续发送(接收)或者阻塞,出现三种情况:
发送进程阻塞、接收进程阻塞
发送进程不阻塞、接收进程阻塞
发送进程和接收进程均不阻塞
通信链路:为使在发送进程和接受进程之间能进行通信,必须在两者之间建立一条通信链路。
显示连接:先用 “建立连接”命令(原语) 建立一条通信链路; 通信;用显式方式拆除链路。——用于计算机网络
隐式连接:发送进程无须明确提出建立链路的要求,直接利用系统提供的发送命令(原语),系统会自动地为之建立一条链路。——用于单机系统
进程的资源分配角色:
br /> 进程由一组相关资源构成,包括地址空间(代码段、数据段)、打开的文件等各种资源。
线程的处理机调度角色:
br /> 线程描述在进程资源环境中的指令流执行状态,线程间各自独立。
线程的特性:
线程间并发执行,共享相同的地址空间。
线程的优点:
br /> 一个进程中可以同时存在多个线程。
br /> 各个线程之间可以并发地执行,切换效率高。
br /> 各个线程之间可以共享地址空间和文件等资源。
线程的缺点:
br /> 一个线程崩溃,会导致其所属进程的所有线程崩溃。
OS独立调度和分派的基本单位
,线程是
CPU调度的基本单位
。
br /> https://blog.csdn.net/Shine__Wong/article/details/101453197
br /> https://blog.csdn.net/Shine__Wong/article/details/101108284
到此这篇进程控制块是描述进程状态和特性的数据结构一个进程(进程控制块是专为用户进程设置的私有数据结构)的文章就介绍到这了,更多相关内容请继续浏览下面的相关推荐文章,希望大家都能在编程的领域有一番成就!版权声明:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符,请将相关资料发送至xkadmin@xkablog.com进行投诉反馈,一经查实,立即处理!
转载请注明出处,原文链接:https://www.xkablog.com/sjkxydsj/20106.html