操作系统高级议题:并发控制与进程互斥技术

简介: 操作系统高级议题:并发控制与进程互斥技术


进程的同步和互斥

由于进程的异步性,在争用资源时,常会出现以下的问题:

系统混乱、数据处理的不可再现性。

为了使并发执行的诸进程之间能有效地共享资源和相互合作,从而使程序的执行具有可再现性,必须提供进程同步机制。

进程的相互关系主要分为如下三种形式:

① 互斥:竞争关系

② 同步:协作关系

③ 通信:信息交流

竞争条件

分析两个进程共用同一表格的情况:假定进程Pa负责为用户作业分配打印机,进程Pb负责释放打印机。系统中设立一个打印机分配表,由各个进程共用。

分配表中相关信息项的值是与两个进程运行的时间顺序直接相关。

两个或多个进程同时访问和操纵相同的数据时,最后的执行结果取决于进程运行的精确时序,这种情况称做竞争条件(Race Condition)

随着内核数目的增加,并行性增加了,于是竞争条件也变得更常见。

为保障执行结果的唯一性,必须采取另外的措施。

临界资源和临界区

1.临界资源和临界区

一次仅允许一个进程使用的资源称为临界资源(Critical Resource)。

如:进程A、B共享一台打印机,若让它们交替使用, 则得到的结果肯定不是我们希望的。

临界资源可能是硬件,也可能是软件:变量,数据,表格,队列等。

并发进程对临界资源的访问必须作某种限制,否则就可能出与时间有关的错误,如:联网售票。

临界区

在每个进程中访问临界资源的那段程序叫做临界区(Critical Section),简称CS区。

各进程要互斥地进入自己的临界区。

【注意】:临界区是对某一临界资源而言的,对于不同临界资源的临界区,它们之间不存在互斥。

例如:有程序段A、B是关于变量X的临界区,而C、D是关于变量Y的临界区,那么,A、B之间需要互斥执行,C、D之间也要互斥执行,而A与C、B与D之间不用互斥执行。

2.进程进入临界区的一般结构

进程互斥进入临界区都要遵循一种通用模式:

进入前要申请, 获准后方可进入; 执行后要退出 (释放) , 然后才可以执行其他代码

3.临界区进入准则(安全使用临界资源)

① 单个进入。如果若干进程要求进入空闲的临界区,一次仅允许一个进程进入。(空闲让进)

② 独自占用。任何时候,处于临界区内的进程不可多于一个。 (忙则等待)

③ 尽快退出。进入临界区的进程要在有限时间内退出。 (有限等待)

④ 避免忙等。如果进程不能进入自己的临界区,则应让出CPU,避免进程出现“忙等”现象。(让权等待)

进程互斥与同步的概念

1.同步(接力赛、工业生产流水线)

定义 :逻辑上相关的一组并发进程为完成一项任务,通过协调活动来使用共有资源而产生的执行时序的约束关系。

  • 相互合作关系
  • 直接相互制约

2.互斥

定义:逻辑上无关的多个进程由于竞争临界资源而发生的相互制约的关系。

它们的运行不具有时间次序的特征:谁先向系统提出申请,谁就先执行

  • 相互竞争关系,其资源具有独占型
  • 间接相互制约    

同步和互斥的实质都是对进程在执行时序上的某种限制 ,广义上,互斥是一种特殊的同步。

进程同步:指多个相关进程在执行次序上协调。用于保证这种关系的相应机制称为进程同步机制。

小练

说明下列活动是属于哪些制约关系?(同步/互斥)

1)若干同学去图书馆借书
这项活动通常可以同步进行,因为多个同学可以同时在图书馆选择和借阅不同的书籍,除非特定书籍的数量有限,此时可能出现互斥关系,即一位同学正在借阅的书籍不能被其他同学同时借阅。但在大多数情况下,这属于同步关系。

2)两队进行篮球比赛
篮球比赛中的两队是在同一时间进行比赛的,他们之间的活动是同步的。但场上的队员之间存在互斥关系,比如同一时刻一个篮球只有一个队员可以控制。

3)流水线生产中的各道工序
流水线上的各道工序通常是设计为连续和同步进行的,每一道工序完成后,产品会移动到下一个工序。这里的制约关系是同步的,因为每个工序都需要前一个工序完成后才能开始。

4)商品生产和社会消费
商品生产和社会消费是相互依赖的活动,它们可以同步进行。生产出的商品需要消费者购买和使用,而消费者的消费需求又促进商品的生产。然而,在某些情况下,如果商品供不应求或者过剩,可能会出现制约(比如生产速度跟不上消费速度,或消费能力不足以吸纳生产出的商品),但这些更多是由市场供需关系决定的,而不是活动本身的制约关系。因此,这通常也属于同步关系。

综上所述,活动的制约关系如下:

1)若干同学去图书馆借书 —— 无特定制约关系。

2)两队进行篮球比赛 —— 同步。

3)流水线生产中的各道工序 —— 互斥。

4)商品生产和社会消费 —— 同步。

实现互斥的方式

实现机制方面来说,分为:

  • 硬件方法
  • 软件方法

1.利用硬件方法解决进程互斥问题

(1)禁止中断:进程进入临界区后立即关闭中断,即将离开之前开放中断。

(2)专用机器指令:利用TSL指令解决进程互斥进入临界区问题

2.利用软件方法解决进程互斥问题    

为每类临界区设置一把锁(W),该锁有打开和关闭两种状态。

  • 关锁原语lock (W):      

          while (W==1);      

          W=1;

  • 开锁原语unlock (W):    

          W =0;

A、B两个进程互斥使用一台打印机,W初值为0

3.原语

是机器指令的延伸,往往是为完成某些特定的功能而编制的一段系统程序。原语操作也称做“原子操作”(atomic action),即一个操作中的所有动作要么全做,要么全不做。

执行原语操作时,要屏蔽中断,以保证其操作的不可分割性。

如P、V操作等。

信号量

1965年,荷兰学者E.W.Dijkstra提出。  

  1. 整型信号量 (多用于进程互斥, 忙式等待)  
  2. 结构型信号量(多用于进程同步,让权等待)
  3. 二值信号量(只有0、1两个值)    

现在,信号量机制已广泛应用于单处理机、多处理机及计算机网络中。

1.整型信号量

除初始化外,仅能通过两个标准的原子操作来访问。 两个原子操作为:P操作、 V操作

P操作最初源于荷兰语proberen,表示测试;

V操作源于荷兰语verhogen,表示增加。

有些书上将P操作称做wait或者DOWN操作,将V操作称做signal或者UP操作。

典型的P和V操作的伪代码如下

以上操作均为不可中断的原语操作

利用信号量实现互斥

设置一互斥信号量mutex,初值为1,然后将各进程的CS置于P(mutex)V(mutex)之间即可。

2.结构型信号量(记录型信号量)

因其采用了结构型的数据结构而得名。

整型信号机制使进程处于“忙式等待”状态,消耗CPU时间。结构型信号量采取“让权等待”策略

没有特殊说明,凡称信号量就指结构型信号量。

结构型信号量一般是由两个成员组成的数据结构。其中一个成员是整型变量,表示该信号量的值;另一个是指向PCB的指针。

P操作的定义如下:

V操作的定义如下:

在具体实现时应注意,P, V操作都应作为一个整体实施,不允许分割或相互穿插执行

设结构型信号量S

物理意义:   S.Value的初值为系统中某类资源的总数(资源信号量),为1时即临界资源                   (此时的信号量为互斥信号量)

S.Value>0: 某类可用资源的数量。

S.Value<=0: 无资源可用,|S.Value|表示等待队列中的进程数。  

P(S):请求分配一个单位的资源。  

V(S):释放一个单位资源、唤醒等待队列中的进程。

信号量的值与相应资源的使用情况有关

对信号量的操作有如下严格限制:

1. 信号量可以赋初值,且初值为非负数。

2. 信号量的值可以修改,但只能由P和V操作来访问

3.二值信号量

  • 结构型信号量的取值可以是正数、0或者负数
  • 二值信号量的值只能是0或1

信号量的一般应用

1.用信号量实现进程互斥

利用信号量实现互斥的一般模型是:

使用P, V操作实现互斥时应注意两点:

① 在每个程序中用于实现互斥的P(mutex)和V(mutex)必须成对出现,即先做P,进入临界区;后做V,退出临界区。

② 互斥信号量mutex的初值一般为1。

2.用信号量实现进程简单同步

供者和用者间要交换两个消息:缓冲区空和缓冲区满的状态。

设置两个信号量:

  • S1表示缓冲区是否空(0表示不空,1表示空)。
  • S2表示缓冲区是否满(0表示不满,1表示满)。

规定S1和S2的初值分别为1和0

用P和V操作实现同步时应注意

① 分析进程间的制约关系,确定信号量种类。

② 信号量的初值与相应资源的数量有关,也与P, V操作在程序代码中出现的位置有关。

③ 同一信号量的P, V操作要“成对”出现,但是,它们分别出现在不同的进程代码中。

希望对你有帮助!加油!

若您认为本文内容有益,请不吝赐予赞同并订阅,以便持续接收有价值的信息。衷心感谢您的关注和支持!

目录
相关文章
|
4天前
|
安全 Python
告别低效编程!Python线程与进程并发技术详解,让你的代码飞起来!
【7月更文挑战第9天】Python并发编程提升效率:**理解并发与并行,线程借助`threading`模块处理IO密集型任务,受限于GIL;进程用`multiprocessing`实现并行,绕过GIL限制。示例展示线程和进程创建及同步。选择合适模型,注意线程安全,利用多核,优化性能,实现高效并发编程。
18 3
|
4天前
|
Python
解锁Python并发新世界:线程与进程的并行艺术,让你的应用性能翻倍!
【7月更文挑战第9天】并发编程**是同时执行多个任务的技术,提升程序效率。Python的**threading**模块支持多线程,适合IO密集型任务,但受GIL限制。**multiprocessing**模块允许多进程并行,绕过GIL,适用于CPU密集型任务。例如,计算平方和,多线程版本使用`threading`分割工作并同步结果;多进程版本利用`multiprocessing.Pool`分块计算再合并。正确选择能优化应用性能。
|
1天前
|
存储 缓存 安全
【Linux】冯诺依曼体系结构与操作系统及其进程
【Linux】冯诺依曼体系结构与操作系统及其进程
9 1
|
3天前
|
数据库 数据安全/隐私保护 C++
Python并发编程实战:线程(threading)VS进程(multiprocessing),谁才是并发之王?
【7月更文挑战第10天】Python并发对比:线程轻量级,适合I/O密集型任务,但受GIL限制;进程绕过GIL,擅CPU密集型,但通信成本高。选择取决于应用场景,线程利于数据共享,进程利于多核利用。并发无“王者”,灵活运用方为上策。
|
3天前
|
算法 安全 调度
深入理解操作系统:进程调度与内存管理
【7月更文挑战第10天】本文将深入探讨操作系统的核心机制,即进程调度和内存管理。我们将从理论和实践的角度出发,解释这些机制如何影响系统性能和用户体验。通过分析不同的调度算法和内存分配策略,我们旨在揭示操作系统设计背后的复杂性和精妙之处。
|
1天前
|
存储 监控 安全
探索现代操作系统中的内存管理技术
【7月更文挑战第12天】在数字世界的心脏,操作系统扮演着至关重要的角色。本文将深入探讨内存管理技术,这一操作系统中的核心组件。我们将从基础的内存结构入手,逐步解析虚拟内存、分页和分段等高级概念。文章旨在为读者提供一个清晰的内存管理机制视图,并讨论其在性能优化和系统安全中的应用。通过分析现代操作系统如Linux和Windows的内存管理策略,我们可以更好地理解这些复杂系统的内部工作原理及其对计算领域的影响。
|
4天前
|
算法 Linux 调度
深入理解操作系统之进程调度
【7月更文挑战第9天】在数字世界的复杂舞台上,操作系统的进程调度宛如一位精心编排剧本的导演,确保每一个“演员”——即进程——都能得到恰到好处的表演机会。本文将揭开进程调度的神秘面纱,从理论到实践,详细解读其背后的原理与策略,以及它们对系统性能和用户体验所产生的深远影响。
5 0
|
5天前
|
消息中间件 Java 调度
线程和进程的区别及其在操作系统中的实现机制
线程和进程的区别及其在操作系统中的实现机制
|
8天前
|
安全 Linux 网络安全
部署07--远程连接Linux系统,利用FinalShell可以远程连接到我们的操作系统上
部署07--远程连接Linux系统,利用FinalShell可以远程连接到我们的操作系统上
|
8天前
|
Linux 虚拟化 数据安全/隐私保护
部署05-VMwareWorkstation中安装CentOS7 Linux操作系统, VMware部署CentOS系统第一步,下载Linux系统,/不要忘, CentOS -7-x86_64-DVD
部署05-VMwareWorkstation中安装CentOS7 Linux操作系统, VMware部署CentOS系统第一步,下载Linux系统,/不要忘, CentOS -7-x86_64-DVD