最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

今日播报!期末复习——同步、互斥、死锁

来源：博客园
  • 不同进程之间的关系
    • 同步 = 直接制约关系，相互之间协调顺序，进行阻塞等调整。
    • 互斥 = 间接制约关系，一个进程进入临界区，另一进程必须等待。

同步

临界区问题

多道程序环境中，进程并发执行，但不同进程之间会有联系和相互制约。临界资源一次只允许一个进程使用：打印机等所以需要互斥。

  • 临界资源访问过程
    1. 进入区：检查可否进入临界区。能：设置正在访问标志，阻止其他进程访问临界区。
    2. 临界区：访问临界资源的代码段
    3. 退出区：清除正在访问标志
    4. 剩余区：剩余代码部分
  • 临界区问题方案原则：
    1. 互斥：只有一个进程在临界区执行。
    2. 进步progress：临界区无进程在运行，有进程需要进入临界区-->只有不在剩余区内执行的进程可以参加选择。
    3. 有限等待：发出进入临界区请求-->被允许的时间有上限。在临界区运行的进程不能被调度或切换。

实现临界区互斥基本方法

软件实现方法

  1. 单标志法
  2. 双标志法-先检查
  3. 双标志法-后检查
4 Peterson"s Algorithm
  • 进程共享2个数据：
    • int turn;
    • boolean falg[2]：进程Piflag[i]=true表示想进入临界区。
      • 若Pj在临界区，Pi会在while中不进入临界区。
do {flag[i] = true;turn = j;while (flag[j] && turn == j);critical sectionflag[i] = false;remainder section} while (true);

硬件实现方法

通过锁来保护临界区。称为低级方法。


【资料图】

  • 缺点：进程等待进入临界区等待耗时，不能让权等待，很多进程一起等的时候，有些进程可能一直选不上-->
  • 单处理器：修改共享变量时禁止中断/关中断即可。
  • 多处理器：这样过于耗时不可行。
2 硬件指令方法
  • TestAndSet指令：检查lock值。lock=true表示不可中断，临界区执行；
  • Swap指令：交换两个字的内容

解决临界区问题工具

以下是构建好的软件工具。

1 互斥锁 mutex lock

最简单的同步工具。

  • 缺点：使用忙等待。其他进程在临界区时，其他进程要不断调用acquire()。不过这里等待锁时没有上下文切换。
  • bool available：表示锁是否可用；
  • acquire() 锁可用时获得锁，这个锁不会被其他的进程用了；一个原子操作
  • release() 一个原子操作

信号量 semaphore

定义两个标准原子操作：

  • P操作-申请资源：wait(S) 资源-- 减少信号量计数
  • V操作-释放资源：signal(S) 资源++
1 二进制信号量

二进制信号量-->值0 or 1。so类似于互斥锁，提供互斥。

2 整型信号量
  • 变量 value
    • value > 0 信号量可用资源数
    • value = 0 无空闲资源、无空闲进程，正在执行一个进程
    • value < 0 calue绝对值代表正在使用该资源的阻塞进程数量这里在临界区内忙等
wait(value){while(value<=0); /*没有可用资源时忙等*/value--; /*有可用资源时减少资源数 表示占用这个资源*/}signal(value){value++; /*释放资源 可用资源数++*/}
3 记录型信号量

不存在忙等的机制

  • 变量 value、链表List
typedef struct{int value;struct process *List;/*连接等待该资源的进程*/}semaphore; /*一个信号量拥有的数据*/void wait(semaphore sema){sema.value--; /*申请资源时*/if(sema.value < 0){/*没有可用资源了*/add this process to sema.List;block(sema.List);/*自我阻塞 等待唤醒*/}}void signal(semaphore sema){sema.value++; /*释放资源时*/if(sema.value <= 0){/*释放前是没有可用资源的*/remove a process P from sema.List;wakeup(P);/*唤醒其中一个自我阻塞的进程*/}}
4 导致的死锁与饥饿
一个死锁的例子：S、Q资源 进程P0、P11. P0：wait(S)  -->  P1：wait(Q)  -->2. P0：wait(Q) 这里要等P1 signal(Q)之后才能到下一步/*！！已经开始无线等待了*/# 死锁！！！死！！！/* because要等到`5`才释放，同时`4`也在后面，等也等不到 */3. P1：wait(S) 这里要等P0释放S之后才能到下一步4. P0：signal(S) 释放S5. P1：signal(Q) 释放Q6. P0：signal(Q) 释放Q7. P1：signal(S) 释放S
5 优先级反转问题

意思是H等M完成才能运行，但是理应当是H先运行嘛。这是因为临界资源R被L先占用了。

三个进程：L低、M中、H高进程资源R0. 进程L正在访问R1. H请求访问R，H阻塞等待L使用完2. 这是L被M抢占，M执行，L没办法及时释放资源R3. 等待M运行完，L运行完，H才运行
解决
  1. 给资源R也设置优先级，高于所有进程的优先级，这样不会出现优先级反转的问题。
  2. pintos采用的是进行优先级捐赠。就是让L临时继承H的优先级，这样M就不会抢占了，等L运行完，释放R之后交还优先级给H，然后H立即执行。最后才到M。

管程

利用ADT 抽象数据类型封装了数据and一系列函数，管程的类型就是ADT类型。(管程很像一个类class)

  • 把对共享资源的操作封装
  • 只有一个进程在管程内处于活动状态。-->实现互斥。
条件变量

条件变量condition...pintos既视感管程中设置了多个condition条件变量，每个condition保存了一个等待队列，指向因这个condition变量阻塞的所有进程。

  • 对condition条件变量的操作
    • x.wait()：当资源不满足，正在管程中的进程调用x.wait()加入这个condition的队列中，释放管程，进程阻塞。然后其他进程可使用管程。
    • x.signal()：对应的condition发生了变化，调用x.signal()，唤醒正好一个阻塞的进程
  • ！当执行signal操作但无对应的阻塞线程时，系统会认为signal没有发生过。
对比信号量操作
  • 类似：类似P/V操作，对进唤醒/阻塞
  • 不同：condition没有值，只是一个等待功能。信号量有一个值体现共享资源数量。

经典同步问题

1 生产者/消费者模型

。。。

2 读者-写者问题

共享一个文件，又读又写

  • 要求：
    1. 允许多读者一起读
    2. 允许1个写者写入
    3. 写入完成前不允许读
    4. 写之前所有读者要退出

3 哲学家进餐问题

。。。

死锁

分析信号量的时候提到了，互相等待，没有外力介入的话，等等等永无尽头。

  • 产生死锁4个必要条件，一个都不可以少
    1. 互斥：这个资源一次只能被一个进程使用，其他进程只能阻塞着等。
    2. 非抢占：进程主动释放资源。进程占用资源执行时，不允许其他进程抢占资源。
    3. 占有等待：进程0正在占用资源A时又申请资源B，若资源B被进程1占用ing，阻塞进程0等等等，但是不释放资源A。
    4. 循环等待：信号量那里举的例子就是。
  • 可以用系统资源分配图表示。
    • 申请边Pi-->Ri：Pi申请使用资源Ri
    • 分配边Ri-->Pi：Pi获得资源Ri
  • ！要注意资源有几个实例哦

处理死锁策略

  1. 预防死锁：用协议预防，确保系统不会进入死锁状态。至少一个必要条件不成立。
  2. 避免死锁：允许进入死锁状态，检测然后恢复。
  3. 忽略死锁：Linux、Windows采用这个策略。要自己开发程序进行死锁检测解除

1 死锁预防

事先预防破坏：互斥or非抢占or占有等待or循环等待 至少一个条件。

  1. 互斥条件肯定破坏不了，排除

1.2 非抢占

不允许抢占已分配的资源。如何破？

进程A占有资源，然后申请其他无法立即分配的资源(意味着进程要阻塞了)，那进程A的所有资源都可被抢占。隐式释放这些原占有的资源。

1.3 占有等待

进程运行前，一次性申请完所有需要到的资源。一旦开始执行，不再申请资源。

  • 会造成系统资源的眼中浪费
  • 导致饥饿现象，个别资源被其他进程长期占用时，等待的那个进程饿饿饿

1.4 循环等待

采用顺序资源分配法。给系统中资源编号，规定进程按照这个编号顺序申请资源。

  • 编号要相对稳定，so限制了新设备添加。

2 死锁避免

事先预防，在资源动态分配过程中，防止进入不安全状态，避免发生死锁。

2.1 系统安全状态

如果系统能按照一定顺序为每个进程分配资源，同时避免死锁，说明系统状态安全。能找到至少一个安全序列，才说明系统安全。

系统总共有12个资源。3个进程，下表表示在t0时间点内进程的资源分配情况。

最大需求当前占用
P0105
P142
P292

可见，12-5-2-2=3个资源空闲可用。

  1. 假设安全序列先是P0，肯定不行 5>3。
  2. 假设安全序列先是P1，要2有3 PASSP1运行完，系统共5个闲资源然后运行P0，要5有5 PASSP0运行完，系统共5个闲资源然后运行P2，要7有10 PASS得到一个成立的安全序列1，P0，P2>
2.1.1 银行家算法

  • 几个数据

    • Available = (R0...Rm)，表示m中资源目前各自可用的数量。
    • Max[i][j] = k：最大需求。进程Pi最多可申请资源Rj的k个实例。
    • Allocation[i][j] = k： 当前进程Pi已被分配、已占用的资源Rj的k个实例。
    • Need[i][j] = k：进程Pi剩余还需要Rj资源k个实例。

  • if Requseti> Needi：生成出错条件

  • if Requseti> Available：进程Pi等待可用资源，当前可用无法满足它。

  • 排除了上述两种情况之后：

    • Available -= Requseti
    • Allocationi+= Requseti
    • Needi-= Requseti

系统内5个进程，A、B、C三种资源，分别有10、5、7个实例。T0时情况：Available = 3 3 2

AllocationMaxNeed
A B CA B CA B C
P00 1 07 5 37 4 3
P12 0 03 2 21 2 2
P23 0 29 0 26 0 0
P32 1 12 2 20 1 1
P40 0 24 3 34 3 1

可见Need = Max-Allocation= 3 3 2

  1. 假设安全序列先是P0，Need>Available
  2. 假设安全序列先是P1，Available=5 3 2 PASS然后运行P3，Available=7 4 3 PASS然后运行P0，Available=7 5 3 PASS然后运行P2，Available=10 5 5 PASS然后运行P4，Available=10 5 7 PASS找到了1个安全序列即可，不过13420顺序也行，懒得写了。

3 忽略死锁、死锁检验

死锁可能出现，出现了再说

  • 有检查是否死锁的算法
  • 从死锁状态恢复的算法。
  • 方法：
    • 每种资源只有单个实例
    • 多个实例：类似银行家算法
    • 应用检查算法

4 死锁恢复

  • 进程终止
    • 终止所有死锁进程
    • 一次终止一个进程，直到消除死循环
  • 资源抢占，把资源转移给其他进程。直到打破死锁，然后要处理下面的问题：
    • 选择牺牲的进程，进程终止+确定顺序，减小代价
    • 回滚：将进程状态恢复到能够不产生死锁的情况，从这个状态重启这个进程
    • 处理饥饿情况：确保一个进程只能有限次被选中牺牲，免得每次都砍了他，那份工作永远没有完成。

嗯当时上课的时候就没怎么明白是怎么回事，欠下来的债终归是躲不掉的。

关键词： 释放资源 条件变量