第二章：处理机管理：第三节：同步与互斥
🌈个人主页：小新_-
🎈个人座右铭：“成功者不是从不失败的人，而是从不放弃的人！”🎈
🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝
🏆所属专栏：操作系统 欢迎订阅，持续更新中~~~
✨让小新带着你快乐的学习吧~✨
目录
一、进程同步、进程互斥
1、进程同步
知识点回顾:进程具有异步性的特征。异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进。
再看另一个例子:进程通信--管道通信
读进程和写进程并发地运行，由于并发必然导致异步性，因此“写数据”和“读数据”两个操作执行的先后顺序是不确定的。而实际应用中，又必须按照“写数据→读数据”的顺序来执行的。如何解决这种异步问题，就是“进程同步”所讨论的内容。
同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。
2、进程互斥
1）概念
进程的“并发”需要“共享”的支持。各个并发执行的进程不可避免的需要共享一些系统资源(比如内存，又比如打印机、摄像头这样的/0设备)
我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备(比如摄像头、打印机)都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。
对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。
2）四个部分
对临界资源的互斥访问，可以在逻辑上分为如下四个部分:
3）原则
为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则:
- 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区;
- 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待;
- 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区(保证不会饥饿);
- 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。
【总结】
二、互斥的软件实现方法
进程A、进程B在系统中并发地运行
先调度A上处理机运行当A在使用打印机的过程中，分配给它的时间片用完了，接下来操作系统调度B让它上处理机运行进程B也在使用打印机
结局:A、B的打印内容混在一起了
如何实现进程互斥?
1、单标志法
算法思想:两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予
turn 的初值为0，即刚开始只允许0号进程进入临界区。
若 P1先上处理机运行，则会一直卡在⑤。直到 P1 的时间片用完，发生调度，切换 P0 上处理机运行。代码 ① 不会卡住 PO，P0 可以正常访问临界区，在 P0访问临界区期间即时切换回 P1，P1依然会卡在 ⑤.只有 P0 在退出区将 turn 改为1后，P1才能进入临界区。
因此，该算法可以实现“同一时刻最多只允许一个进程访问临界区”
2、双标志先检查
算法思想:双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查的方法，来避免上述问题。
若按照 ①➁➅③⑦...的顺序执行，P0 和 P1将会同时访问临界区。
因此，双标志先检查法的主要问题是:违反“忙则等待”原则。
原因在于，进入区的“检查”和“上锁”两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换。
3、双标志后检查
算法思想:双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查的方法，来避免上述问题。
若按照 ①⑤➁⑥..的顺序执行，P0和 P1将都无法进入临界区
因此，双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待原则，会因各进程都长期无法访问临界资源而产生“饥饿”现象。
两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。
4、Peterson算法
算法思想:结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”(谦让)。做一个有礼貌的进程。
Peterson 算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待 三个原则，但是依然未遵循让权等待的原则。
Peterson 算法相较于之前三种软件解决方案来说，是最好的，但依然不够好。
【总结】
三、互斥的硬件实现方法
1、中断屏蔽方法
利用“开/关中断指令”实现(与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况)
优点:简单、高效
缺点:不适用于多处理机:只适用于操作系统内核进程，不适用于用户进程(因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险)
2、TestAndSet（TS指令/TSL指令）
简称 TS 指令，也有地方称为TestAndSetLock指令，或TSL指令
TSL指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用C语言描述的逻辑
若刚开始lock是 false，则 TSL返回的 old值为false，while 循环条件不满足，直接跳过循环，进入临界区。若刚开始lock是true，则执行TLS后old返回的值为true，whie 循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行“解锁”。
相比软件实现方法，TSL指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。
优点:实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞:适用于多处理机环境
缺点:不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”
3、Swap指令（XCHG指令）
有的地方也叫 Exchange 指令，或简称XCHG 指令。
Swap 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用C语言描述的逻辑
逻辑上来看Swap和TSL并无太大区别，都是先记录下此时临界区是否已经被上锁(记录在 old变量上)，再将上锁标记lock设置为true，最后检查old，如果old为false则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区。
优点:实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞:适用于多处理机环境
缺点:不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。
【总结】
四、锁
1、互斥锁
解决临界区最简单的工具就是互斥锁(mutex1ock)。一个进程在进入临界区时应获得锁:在退出临界区时释放锁。函数acquireO获得锁，而函数release()释放锁。
每个互斥锁有一个布尔变量 available，表示锁是否可用。如果锁是可用的，调用 acqiureO会成功，且锁不再可用。当一个进程试图获取不可用的锁时，会被阻塞，直到锁被释放。
acquire()或release0)的执行必须是原子操作，因此互斥锁通常采用硬件机制来实现。
互斥锁的主要缺点是忙等待，当有一个进程在临界区中，任何其他进程在进入临界区时必须连续循环调用 acquire()。当多个进程共享同一CPU时，就浪费了CPU周期。因此，互斥锁通常用于多处理器系统，一个线程可以在一个处理器上等待，不影响其他线程的执行。
需要连续循环忙等的互斥锁，都可称为自旋锁(spinlock)，如TSL指令、swap指令、单标志法
2、特性
- 需忙等，进程时间片用完才下处理机，违反“让权等待”
- 优点:等待期间不用切换进程上下文，多处理器系统中，若上锁的时间短，则等待代价很低
- 常用于多处理器系统，一个核忙等，其他核照常工作，并快速释放临界区
- 不太适用于单处理机系统，忙等的过程中不可能解锁
五、信号量机制
复习回顾+思考:之前学习的这些进程互斥的解决方案分别存在哪些问题?
进程互斥的四种软件实现方式(单标志法、双标志先检查、双标志后检查、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)
1、整型信号量
2、记录型信号量
【总结】
六、用信号量机制实现同步、互斥、前驱关系
Tips:不要一头钻到代码里，要注意理解信号量背后的含义，一个信号量对应一种资源
信号量的值=这种资源的剩余数量(信号量的值如果小于0，说明此时有进程在等待这种资源)
P(S)-- 申请一个资源S，如果资源不够就阻塞等待
V(S)--释放一个资源S，如果有进程在等待该资源，则唤醒一个进程
1、实现进程互斥
2、实现进程同步
3、实现进程的前驱关系
【总结】
七、经典同步互斥问题
1、生产者消费者问题
2、多生产者多消费者问题
【总结】
总结:在生产者-消费者问题中，如果缓冲区大小为1，那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的功能。当然，这不是绝对的，要具体问题具体分析。
建议:在考试中如果来不及仔细分析，可以加上互斥信号量，保证各进程一定会互斥地访问缓冲区。但需要注意的是，实现互斥的P操作一定要在实现同步的P操作之后，否则可能引起“死锁”。
PV 操作题目的解题思路:
- 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系
- 整理思路。根据各进程的操作流程确定P、V操作的大致顺序。
- 设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。(互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少)
解决“多生产者-多消费者问题”的关键在于理清复杂的同步关系。
在分析同步问题(一前一后问题)的时候不能从单个进程行为的角度来分析，要把“一前一后”发生的事看做是两种“事件”的前后关系。
比如，如果从单个进程行为的角度来考虑的话，我们会有以下结论:
如果盘子里装有苹果，那么一定要女儿取走苹果后父亲或母亲才能再放入水果
如果盘子里装有橘子，那么一定要儿子取走橘子后父亲或母亲才能再放入水果
这么看是否就意味着要设置四个同步信号量分别实现这四个“一前一后”的关系了?
正确的分析方法应该从“事件”的角度来考虑，我们可以把上述四对“进程行为的前后关系”抽象为一对“事件的前后关系”盘子变空事件→放入水果事件。“盘子变空事件”既可由儿子引发，也可由女儿引发;“放水果事件”既可能是父亲执行，也可能是母亲执行。这样的话，就可以用一个同步信号量解决问题了
3、吸烟者问题
4、读者写者问题
5、哲学家进餐问题
八、管程
1、为什么引入管程
2、管程的定义和基本特征
3、拓展1：用管程解决生产者消费者问题
4、拓展2：Java中类似于管程的机制
【总结】
最后，感谢大家的观看！
原文地址：https://blog.csdn.net/2302_76674204/article/details/142722246
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！