迦南地
所有文章 标签 分类 实验室 关于
迦南地

目录

进程同步

 收录于 技术
   约 2580 字   预计阅读 6 分钟    次阅读  

同步、互斥问题

什么是进程同步

知识点回顾：进程具有异步性的特征。异步性是指，各并发执行的进程以独立的、不可预知的速度向前推进。

https://gitee.com/lienhui68/picStore/raw/master/null/20200710231916.png

再来看一个例子：进程通信——管道通信

https://gitee.com/lienhui68/picStore/raw/master/null/20200710232048.png

什么是进程互斥

https://gitee.com/lienhui68/picStore/raw/master/null/20200710232136.png

对临界资源的互斥访问，可以在逻辑上分为如下四个部分：

https://gitee.com/lienhui68/picStore/raw/master/null/20200710232337.png

为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则：

  1. 空闲让进 临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。

  2. 忙则等待 当已有进程进入临界区时，其他试图进入临界区的进程必须等待。

  3. 有限等待 对请求访问的进程，应保证能在有限时间内进入临界区(保证不会饥饿)。

  4. 让权等待 当进程不能进入临界区，应立即释放处理机，防止进程忙等待。

小结

https://gitee.com/lienhui68/picStore/raw/master/null/20200710232841.png

进程同步又可称作进程之间的直接制约关系，也就是说这些进程之间有合作关系。

进程互斥又可称作进程之间的间接制约关系， 因为进程之间没有合作，只是想互斥使用临界资源才会产生这种制约关系。

同步和互斥有什么联系和区别

同步是一种更为复杂的互斥，而互斥是一种特殊的同步。 也就是说互斥是两个线程之间不可以同时运行，他们会相互排斥，必须等待一个线程运行完毕，另一个才能运行，而同步也是不能同时运行，但他是必须要安照某种次序来运行相应的线程（也是一种互斥）！

互斥：是指某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序，即访问是无序的。 同步：是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序访问。在大多数情况下，同步已经实现了互斥，特别是所有写入资源的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源。

进程互斥的软件实现方法

https://gitee.com/lienhui68/picStore/raw/master/null/20200710235608.png

单标志法

算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。

https://gitee.com/lienhui68/picStore/raw/master/null/20200711000054.png

https://gitee.com/lienhui68/picStore/raw/master/null/20200711000414.png

双标志先检查法

算法思想：设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如flag[0]=true意味着0号进程P0现在想进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[i]设为true，之后开始访问临界区。

https://gitee.com/lienhui68/picStore/raw/master/null/20200711000844.png

双标志后检查法

https://gitee.com/lienhui68/picStore/raw/master/null/20200711001009.png

Peterson算法

https://gitee.com/lienhui68/picStore/raw/master/null/20200711001111.png

https://gitee.com/lienhui68/picStore/raw/master/null/20200711001213.png

Peterson算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。

Peterson算法相较于前三种软件解决方案来说是最好的，但依然不够好。

小结

https://gitee.com/lienhui68/picStore/raw/master/null/20200711001430.png

进程互斥的硬件实现方法

中断屏蔽方法

https://gitee.com/lienhui68/picStore/raw/master/null/20200711002529.png

TestAndSet(TS指令/TSL指令)

https://gitee.com/lienhui68/picStore/raw/master/null/20200711002552.png

Swap指令(XCHG指令)

https://gitee.com/lienhui68/picStore/raw/master/null/20200711002609.png

小结

https://gitee.com/lienhui68/picStore/raw/master/null/20200711002632.png

信号量机制

复习回顾+思考：之前学习的这些进程互斥的解决方案分别存在哪些问题？

进程互斥的四种软件实现方式（单标志法、双标志先检查、双标志后检查、Peterson算法）

进程互斥的三种硬件实现方式（中断屏蔽方法、TS/TSL指令、Swap/XCHG指令）

  1. 在双标志先检查法中，进入区的“检查”、“上锁” 操作无法一气呵成，从而导致了两个进程有可能同时进入临界区的问题；
  2. 所有的解决方案都无法实现“让权等待”

1965年，荷兰学者Dijkstra提出了一种卓有成效的实现进程互斥、同步的方法——信号量机制

用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。

信号量其实就是一个变量 （可以是一个整数，也可以是更复杂的记录型变量） ，可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为 1 的信号量。

原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题。

一对原语：wait(S) 原语和 signal(S) 原语，可以把原语理解为我们自己写的函数，函数名分别为 wait 和 signal，括号里的信号量 S 其实就是函数调用时传入的一个参数。

wait、signal 原语常简称为 P、V操作（来自荷兰语 proberen 和 verhogen）。因此，做题的时候常把 wait(S)、signal(S) 两个操作分别写为 P(S)、V(S)

整型信号量

https://gitee.com/lienhui68/picStore/raw/master/null/20200711015547.png

记录型信号量

整型信号量的缺陷是存在“忙等”问题，因此人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量。

https://gitee.com/lienhui68/picStore/raw/master/null/20200711015718.png

举例：

https://gitee.com/lienhui68/picStore/raw/master/null/20200711015806.png

https://gitee.com/lienhui68/picStore/raw/master/null/20200711015902.png

小结

https://gitee.com/lienhui68/picStore/raw/master/null/image-20200711015927276.png

信号量机制的用处

Tips：不要一头钻到代码里，要注意理解信号量背后的含义，一个信号量对应一种资源

信号量的值 = 这种资源的剩余数量（信号量的值如果小于0，说明此时有进程在等待这种资源）

P( S ) —— 申请一个资源S，如果资源不够就阻塞等待

V( S ) —— 释放一个资源S，如果有进程在等待该资源，则唤醒一个进程

实现进程互斥

https://gitee.com/lienhui68/picStore/raw/master/null/20200711021702.png

实现进程同步

https://gitee.com/lienhui68/picStore/raw/master/null/20200711021734.png

https://gitee.com/lienhui68/picStore/raw/master/null/20200711021822.png

实现进程的前驱关系

https://gitee.com/lienhui68/picStore/raw/master/null/20200711021856.png

小结

https://gitee.com/lienhui68/picStore/raw/master/null/20200711021959.png

生产者消费者问题

问题描述

https://gitee.com/lienhui68/picStore/raw/master/null/20200711024414.png

问题分析

https://gitee.com/lienhui68/picStore/raw/master/null/20200711024741.png

https://gitee.com/lienhui68/picStore/raw/master/null/20200711024821.png

https://gitee.com/lienhui68/picStore/raw/master/null/20200711024857.png

如何实现

https://gitee.com/lienhui68/picStore/raw/master/null/20200711025027.png

思考：能否改变相邻P、V操作的顺序

https://gitee.com/lienhui68/picStore/raw/master/null/20200711025212.png

小结

https://gitee.com/lienhui68/picStore/raw/master/null/20200711025348.png

多类生产者多类消费者问题

问题描述

https://gitee.com/lienhui68/picStore/raw/master/null/20200711031654.png

问题分析

https://gitee.com/lienhui68/picStore/raw/master/null/20200711032005.png

如何实现

https://gitee.com/lienhui68/picStore/raw/master/null/20200711032315.png

问题：可不可以不用互斥信号量？

https://gitee.com/lienhui68/picStore/raw/master/null/20200711032434.png

原因在于：本题中的缓冲区大小为1，在任何时刻，apple、orange、plate 三个同步信号量中最多只有一个是1。因此在任何时刻，最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区…

https://gitee.com/lienhui68/picStore/raw/master/null/20200711032628.png

小结

总结：在生产者-消费者问题中，如果缓冲区大小为1，那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的功能。当然，这不是绝对的，要具体问题具体分析。

建议：在考试中如果来不及仔细分析，可以加上互斥信号量，保证各进程一定会互斥地访问缓冲区。 但需要注意的是，实现互斥的P操作一定要在实现同步的P操作之后，否则可能引起“死锁”。

PV 操作题目的解题思路：

  1. 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。

  2. 整理思路。根据各进程的操作流程确定P、V操作的大致顺序。

  3. 设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。（互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少）

https://gitee.com/lienhui68/picStore/raw/master/null/20200711033216.png

吸烟者问题

问题描述

https://gitee.com/lienhui68/picStore/raw/master/null/20200711034342.png

问题分析

https://gitee.com/lienhui68/picStore/raw/master/null/20200711034458.png

https://gitee.com/lienhui68/picStore/raw/master/null/20200711034526.png

如何实现

https://gitee.com/lienhui68/picStore/raw/master/null/20200711034601.png

小结

https://gitee.com/lienhui68/picStore/raw/master/null/20200711034835.png

读者写者问题

问题描述

https://gitee.com/lienhui68/picStore/raw/master/null/20200711040822.png

分析问题

https://gitee.com/lienhui68/picStore/raw/master/null/20200711040841.png

如何实现

https://gitee.com/lienhui68/picStore/raw/master/null/20200711040906.png

https://gitee.com/lienhui68/picStore/raw/master/null/20200711040951.png

小结

https://gitee.com/lienhui68/picStore/raw/master/null/20200711041021.png

哲学家进餐问题

问题描述

https://gitee.com/lienhui68/picStore/raw/master/null/20200711042845.png

问题分析

https://gitee.com/lienhui68/picStore/raw/master/null/20200711042924.png

如何实现

方式一

https://gitee.com/lienhui68/picStore/raw/master/null/20200711043042.png

设置一个初始值为4的同步信号量

方式二

https://gitee.com/lienhui68/picStore/raw/master/null/20200711043158.png

方式三

https://gitee.com/lienhui68/picStore/raw/master/null/20200711043559.png

https://gitee.com/lienhui68/picStore/raw/master/null/20200711043623.png

https://gitee.com/lienhui68/picStore/raw/master/null/20200711043705.png

https://gitee.com/lienhui68/picStore/raw/master/null/20200711043943.png

小结

https://gitee.com/lienhui68/picStore/raw/master/null/20200711044017.png

管程

为什么要引入管程

https://gitee.com/lienhui68/picStore/raw/master/null/20200711051258.png

管程的定义和基本特征

https://gitee.com/lienhui68/picStore/raw/master/null/20200711051338.png

拓展1：用管程解决生产者消费者问题

https://gitee.com/lienhui68/picStore/raw/master/null/20200711051507.png

https://gitee.com/lienhui68/picStore/raw/master/null/20200711051533.png

拓展2：Java中类似于管程的机制

https://gitee.com/lienhui68/picStore/raw/master/null/20200711051553.png

小结

https://gitee.com/lienhui68/picStore/raw/master/null/20200711051619.png

更新于 2020-07-09
 操作系统
返回 | 主页