2.进程控制

一、程序的并发:

并发

并发性:指两个或多个事件在同一时间间隔内发生。 程序的并发性是宏观上一段时间内多道程序同时运行。

单处理器的并发性:

每一时刻点只能执行一道程序,进程走走停停。 微观上多道程序交替执行。 (并发:是指一个时间段中有几个程序都处于已启动运行到运行完毕之间,且这几个程序都是在同一个处理机上运行,但任一个时刻点上只有一个程序在处理机上运行。)

1.单道程序的顺序执行及特征

(1)程序执行有固定的时序:

输入进程1 -> 计算进程1 - 输出进程1 -输入进程2 -计算进程2 -输出进程2 ......

(2)特征

顺序性、封闭性、可再现性。

2.多道程序的并发执行

(1)

多个程序的并发执行1.png

多个程序的并发执行2.png

(2)特征:

间断性、失去封闭性:主要由共享资源引起、不可再现性。

(3)思考?

有2个循环程序A和B,它们共享一个变量N,程序A每执行一次时,都要做N:=N+1; B则每次要执行Print(N), 然后再做N:=0. 若程序A,B以不同的速度运行有以下三种不同的结果. ​ N:=N+1在print(N)和N:=0之前,则N值分别为 n+1,n+1,0. N:=N+1在print(N)和N:=0之后,则N值分别为 n,0,1. N:=N+1在print(N)和N:=0之间,则N值分别为 n,n+1,0.

但这不是我们要的。

(3)如何保证并发执行的顺序性特征?

答案:引入同步控制机制进程的并发执行,协同工作就是进程同步

3.前驱图 : 必须不存在循环

前趋图是一个有向无循环图,记为DAG(Directed Acyclic Graph),用于描述进程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程,乃至一条语句;结点间的有向边则用于表示两个结点之间存在的偏序(Partial Order)或前趋关系。 →={(Pi, Pj)|Pi must complete before Pj may start}, 如果(Pi, Pj)∈→,可写成Pi→Pj,称Pi是Pj的直接前趋,而称Pj是Pi的直接后继。在前趋图中,把没有前趋的结点称为初始结点(Initial Node),把没有后继的结点称为终止结点(Final Node)。 每个结点还具有一个权重(Weight),用于表示该结点所含有的程序量或结点的执行时间。

前趋图.png

对于图 (a)所示的前趋图, 存在下述前趋关系:
 P1→P2, P1→P3, P1→P4, P2→P5, P3→P5, P4→P6, P4→P7, P5→P8, P6→P8, P7→P9, P8→P9
或表示为:
 P={P1, P2, P3, P4, P5, P6, P7, P8, P9}
→={ (P1, P2), (P1, P3), (P1, P4), (P2, P5), (P3, P5), (P4, P6), (P4, P7),
 (P5, P8), (P6, P8), (P7, P9), (P8, P9)} 
​
应当注意,前趋图中必须不存在循环,但在图b中却有着下述的前趋关系:S2→S3, S3→S2 

二、进程同步

1.基本概念

(1)同步:

并发进程在执行次序上的协调,以达到有效的资源共享和相互合作,使程序执行有可再现性。

(2)互斥:

两个并行的进程A、B,如果当A进行某个操作时,B不能做这一操作,进程间的这种限制条件称为进程互斥,这是引起资源不可共享的原因。 互斥是一种特殊的同步。

(3)进程两种形式的制约关系

进程间接制约关系:源于资源共享,需互斥地访问临界资源。 进程直接制约关系:源于相互合作

2.临界资源、临界区

(1)临界资源:

在一段时间内只允许一个进程访问的资源称为临界资源或独占资源。 打印机等物理设备;软件使用的栈、变量。引起不可再现性是因为临界资源没有互斥访问。

(2)临界区:(critical section)

临界区:进程中访问临界资源的那段代码

临界区.png

临界区1.png

3.解决同步问题的工具:信号量机制

(1)整型信号量 : PV操作

整型信号量定义为一个整型量,除初始化外,仅能通过两个标准的原子操作wait(S)和signal(S)来访问。这两个操作一直被分别称为P、V操作。 wait和signal操作可描述为: wait(S): while S≤0 do no-op S∶=S-1; signal(S): S∶=S+1; 弊端分析:不符合让权等待原则

PV操作1.png

//semaphore:只是用来记录有多少个线程正在使用他(他并没有互斥的性质,他可以被多个线程拥有)。
//Parbegin 和 Parend中间会来夹着几个进程:process1、process2...,意思是这里面的进程  是可以并发执行的,里面的进程就需自要利用到信号量机制了。
// Begin 、 End :
例1:

设系统中有两个进程P1、P2,P1进程负责计算数据,将结果放入缓冲区Buf,P2进程从缓冲区Buf中取数据输出。试写出两个进程的同步算法。

semaphore be=1,bf=0;
 //semaphore只是用来记录有多少个线程正在使用他(他并没有互斥的性质,他可以被多个线程拥有)
Parbegin
 //parbegin和parend中间会来夹着几个进程:process1、process2...,意思是这里面的进程  是可以并发执行的,里面的进程就需自要利用到信号量机制了。
 P1: Begin
 *************************************
 Repeate
 计算数据Data;
 Wait(be);
 Data=>Buf;
 Signal(bf);
 Until false;
 ***********************************      //临界区 
 End 

 P2: Begin
 ************************************* 
 Repeate
 Wait(bf);
 取Data;
 Signal(be);
 Until false;
 ************************************* 
 End
Parend.

PV操作.png

同步机制应遵循的规则 :

进程执行结果可再现性的保证: (1) 空闲让进。进入临界区 (2) 忙则等待。 临界资源 (3) 有限等待。不死等 公平性 (4) 让权等待。不能进入临界区放权 效率

4.改进的信号量机制

(1)记录型信号量

(2)AND型信号量

(3)集合型信号量

6.锁机制

在多线程编程中,操作系统引入了锁机制。通过锁机制,能够保证在多核多线程环境中,在某一个时间点上,只能有一个线程进入临界区代码,从而保证临界区中操作数据的一致性。 大部分同步方案均采用某个物理实体(如锁、信号灯等)实现通信,进程通信原语中关锁(lock)和开锁(unlock)是最简单的原语。在这两个原语中设置一个公共变量x代表某个临界资源的状态。如: x=0,表示资源可用(开锁) x=1,表示资源正在使用。(上锁)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 1.进程管理

    11、对进程的描述错误的是( d) A.进程是动态的概念 B.进程执行需要处理机 C.进程是有生命期的 D.进程是指令的集合

    见贤思齊
  • 10-1 进程如何工作

    见贤思齊
  • 05-命令的使用

    见贤思齊
  • Linux系列教程(二十一)——Linux的bash基本功能

      上篇博客我们介绍了什么是shell,以及编写shell脚本的两种执行方式。我们知道在敲命令的时候,有很多快捷键,比如tab键能补全命令,在比如为什么我们直接...

    IT可乐
  • 并发篇-python进程

    >>> 并发是指,程序在运行的过程中存在多于一个的执行上下文。这些执行上下文一般对应着不同的调用栈。

    小团子
  • 网络基础入门3

    路由器的工作原理: 1、路由器仅仅关心数据中的 “ 目标IP 地址” ; 2、路由器提取 目标IP地址,与 路由表中的条目进行匹配: 如果匹配成功,则转发; ...

    py3study
  • 【GPLT】L1-003【PAT乙级】个位数统计

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 吴恩达晒妻又晒车,顺便宣布了一个重大消息

    昨日晚间(5 月 7 日),吴恩达在 Twitter 上晒出了自己和妻子 Carol Reiley 的合照,并表示接下来会有重大消息宣布。(这个狗粮撒的猝不及防...

    AI科技大本营
  • 8、单选按钮(JRadioButton)和复选框(JCheckBox)

    单选按钮(JRadioButton)和复选框(JCheckBox)       实现一个单选按钮(或复选框),此按钮项可被选择或取消选择,并显示其状态。JRad...

    YGingko
  • 48-实现Linux系统中unix2dos功能

    凯茜的老爸

扫码关注云+社区

领取腾讯云代金券