2、3_2_进程互斥的软件实现方法.pdf

《2、3_2_进程互斥的软件实现方法.pdf》由会员分享，可在线阅读，更多相关《2、3_2_进程互斥的软件实现方法.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2019/5/16王道考研/1本节内容进程互斥的软件实现方法王道考研/CSKAOYAN.COM王道考研/CSKAOYAN.COM知知识识总总览览学习提示：1. 理解各个算法的思想、原理2. 结合上小节学习的“实现互斥的四个逻辑部分”，重点理解各算法在进入区、退出区都做了什么3. 分析各算法存在的缺陷（结合“实现互斥要遵循的四个原则”进行分析）2019/5/16王道考研/2王道考研/CSKAOYAN.COM如如果果没没有有注注意意进进程程互互斥斥？进程A：其他代码；使用打印机；其他代码；进程B：其他代码；使用打印机；其他代码；如何实现进程互斥？进程A、进程B在系统中并发地运行先调度A上处理机运行

2、当A在使用打印机的过程中，分配给它的时间片用完了，接下来操作系统调度B让它上处理机运行进程B也在使用打印机结局：A、B 的打印内容混在一起了王道考研/CSKAOYAN.COM单单标标志志法法算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予turn 的初值为 0，即刚开始只允许 0 号进程进入临界区。若 P1 先上处理机运行，则会一直卡在 。直到 P1 的时间片用完，发生调度，切换 P0 上处理机运行。代码 不会卡住 P0，P0 可以正常访问临界区，在 P0 访问临界区期间即时切换回 P1，P1依然会卡在 。只有 P0

3、在退出区将 turn 改为 1 后，P1才能进入临界区。因此，该算法可以实现“同一时刻最多只允许一个进程访问临界区”turn 变量背后的逻辑：表达“谦让”2019/5/16王道考研/3王道考研/CSKAOYAN.COM单单标标志志法法turn 变量背后的逻辑：表达“谦让”马桶是否轮到自己用？（检查）访问临界资源，啦啦啦下次让老渣用（表达谦让）做其他事情是否轮到自己用？（检查）访问临界资源，拉拉拉下次让小渣用（表达谦让）做其他事情只能按 P0 P1 P0 P1 这样轮流访问。这种必须“轮流访问”带来的问题是，如果此时允许进入临界区的进程是 P0，而 P0 一直不访问临界区，那么虽然此时临界区空闲

4、，但是并不允许 P1 访问。因此，单标志法存在的主要问题是：违背“空闲让进”原则。王道考研/CSKAOYAN.COM双双标标志志先先检检查查法法算法思想：设置一个布尔型数组 flag，数组中各个元素用来标记各进程想进入临界区的意愿，比如“flag0 = ture”意味着 0 号进程 P0 现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志 flagi 设为 true，之后开始访问临界区。理解背后的含义：“表达意愿”马桶老渣是否想用（检查）我小渣要用（表达意愿，上锁）访问临界资源，啦啦啦小渣不用了（解锁）小渣是否想用（检查）我老渣要用（

5、表达意愿，上锁）访问临界资源，拉拉拉老渣不用了（解锁）进入区2019/5/16王道考研/4王道考研/CSKAOYAN.COM双双标标志志先先检检查查法法算法思想：设置一个布尔型数组 flag，数组中各个元素用来标记各进程想进入临界区的意愿，比如“flag0 = ture”意味着 0 号进程 P0 现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志 flagi 设为 true，之后开始访问临界区。若按照 .的顺序执行，P0 和 P1 将会同时访问临界区。因此，双标志先检查法的主要问题是：违反“忙则等待”原则。原因在于，进入区的“检查”和

6、“上锁” 两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换。理解背后的含义：“表达意愿”进入区王道考研/CSKAOYAN.COM双双标标志志后后检检查查法法算法思想：双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查”的方法，来避免上述问题。马桶我小渣要用（表达意愿，上锁）老渣是否想用（检查）访问临界资源，啦啦啦小渣不用了（解锁）我老渣要用（表达意愿，上锁）小渣是否想用（检查）访问临界资源，拉拉拉老渣不用了（解锁）理解背后的含义：“表达意愿”进入区2019/5/16

7、王道考研/5王道考研/CSKAOYAN.COM双双标标志志后后检检查查法法算法思想：双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查”的方法，来避免上述问题。若按照 .的顺序执行，P0 和 P1 将都无法进入临界区因此，双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待”原则，会因各进程都长期无法访问临界资源而产生“饥饿”现象。两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。理解背后的含义：“表达意愿”进入区王道考研/CSKAO

8、YAN.COMPeterson算算法法算法思想：结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”（谦让）。做一个有礼貌的进程。进入区背后的含义：“表达意愿”表达“谦让”马桶我小渣要用（表达意愿）我愿意优先让老渣用（谦让）老渣想用？且最后是自己表示了谦让？我就等待（检查）访问临界资源，啦啦啦我小渣不想用了我老渣要用（表达意愿）我愿意优先让小渣用（谦让）小渣想用？且最后是自己表示了谦让？我就等待（检查）访问临界资源，拉拉拉我老渣不想用了动手推导：按不同的顺序穿插执行会发生什么？2019/5/16王道考研/6王道考研/CSKAOYAN.COMPeterson算算

9、法法算法思想：结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”（谦让）。做一个有礼貌的进程。背后的含义：“表达意愿”表达“谦让”谁最后说了“客气话”，谁就失去了行动的优先权。Eg: 过年了，某阿姨给你发压岁钱。场景一阿姨：乖，收下阿姨的心意你：不用了阿姨，您的心意我领了阿姨：对阿姨来说你还是个孩子，你就收下吧结局进入区: 1. 主动争取；2. 主动谦让；3. 检查对方是否也想使用，且最后一次是不是自己说了“客气话”王道考研/CSKAOYAN.COMPeterson算算法法算法思想：结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试“

10、孔融让梨”（谦让）。做一个有礼貌的进程。背后的含义：“表达意愿”表达“谦让”谁最后说了“客气话”，谁就失去了行动的优先权。Eg: 过年了，某阿姨给你发压岁钱。场景二阿姨：乖，收下阿姨的心意你：不用了阿姨，您的心意我领了阿姨：对阿姨来说你还是个孩子，你就收下吧你：真的不用了阿姨，我已经成年了结局进入区: 1. 主动争取；2. 主动谦让；3. 检查对方是否也想使用，且最后一次是不是自己说了“客气话”2019/5/16王道考研/7王道考研/CSKAOYAN.COMPeterson算算法法进入区: 1. 主动争取；2. 主动谦让；3. 检查对方是否也想使用，且最后一次是不是自己说了“客气话”Peterson 算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待 三个原则，但是依然未遵循让权等待的原则。Peterson 算法相较于之前三种软件解决方案来说，是最好的，但依然不够好。算法思想：结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”（谦让）。做一个有礼貌的进程。动手推导：按不同的顺序穿插执行会发生什么？王道考研/CSKAOYAN.COM知知识识回回顾顾与与重重要要考考点点